基于Spark的K-means改进算法的并行化实现

针对传统K-means算法在处理海量数据时,存在计算复杂度高和计算能力不足等问题,提出了SKDk-means （Spark based kd-tree K-means）并行聚类算法.该算法通过引入kd-tree改善初始中心点的选择,克服传统K-means算法因初始点的不确定性,易陷入局部最优解的问题,同时利用kd-tree的最近邻搜索减少K-means在迭代中的距离计算,加快聚类速度,并在Spark平台上实现了该算法的并行化,使其适用于海量数据聚类,最后通过实验验证了算法具有良好的准确率和并行计算性能.     

在游戏中利用邻域特性扩展的kd-tree及其查找算法

处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作。将kd-tree用于组织场景,提高了这类计算的效率。传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显。提出了邻域特性概念以扩展传统kd-tree结构,增添了树节点间的平面部接关系,且考虑了游戏对kd-tree的一些限定,设计了从起始节点向四周扩展的查找算法。经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定。     

光子映射在CUDA中的研究与实现

通过修改光子映射算法的实现过程,使得该算法能够通过CUDA完全运行在最新的GPU上,从而能够充分利用GPU强大的并行计算能力,加速光子映射的实现。光子映射在CUDA中的实现主要通过两个方面来完成：构建光子图和估计辐射能。同时为了提高对光子图中的光子信息的查找速度,采用了kd-tree结构来存储光子信息,使得可以通过KNN（K-Nearest Neighbor）快速搜索光子图。在所测试环境中,渲染速度是CPU中的近1O倍。     

CPU-GPU混合平台上动态场景光线跟踪的研究

提出了一种动态场景光线跟踪新方法,能有效地调度CPU和GPU的运行,提高渲染速度。根据加速结构kd-tree的特点,将其分成上层部分和下层部分,上层部分由于并行性较小,由CPU创建;而下层部分并行性较大,由GPU创建,提高动态场景加速结构的创建速度。同时充分利用CPU和GPU两个运算平台的特点,有效调度两者的运行,隐藏部分运算时间,进一步提高动态场景的渲染速度。实验结果表明,在安装了GeForce285GTX的PC机上,高真实感地交互渲染了包含11k三角面片的Kitchen动态场景。     

基于VR和Kinect的定制鞋设计

针对传统制鞋业定制化程度低,无法适应足部多样性、舒适性,造成鞋业资源的浪费,无法满足当代顾客追求个性化的心里等问题,提出了一种基于VR和Kinect的定制鞋设计方法。对个体足部特征进行测量分析,利用三维建模以及VR技术,实现个体鞋的定制设计。首先,使用Kinect3D摄像机进行足部三维扫描,获取足部深度信息数据并转换成点云数据,利用kd-tree算法及贪婪投影三角化算法进行足部点云的去噪处理和点云重构,在Meshlab软件中测量数据并结合MAYA软件完成三维鞋的建模。最后,结合Unity引擎,设计虚拟交互界面,实现纹理贴图和更换,完成定制鞋系统。结果证明,该系统可以快速的进行人机交互,实现鞋的三维定制,满足顾客个性化的心理需求,会对鞋业的发展产生很大的推进作用。     

一种基于散乱点云的边界提取算法

点云边界是曲面的重要特征之一,边界线的快速准确提取对于提高曲面重构的效率和质量具有重要意义。首先,采用基于kd-tree搜索的方法建立点云空间拓补关系,进行K邻域快速搜索,以采样点及其K邻域作为局部型面参考依据拟合微切平面,将其向微切平面投影;其次,在微切平面上建立局部坐标系,并对投影点进行参数化,根据邻域点集在采样点处的场力大小之和可以表示点集的平均作用来识别点云的边界特征点;最后,从提高边界线连续性的角度,利用NURBS曲线插值方法连接边界线。实验结果表明,该算法可以快速、有效地提取出点云的边界特征点,并得到C2连续的边界线,满足曲面重构的要求。     

耳廓三维网格去补丁合并算法

针对耳廓多角度扫描获取的三维网格合并问题,提出了一种新的三维网格合并方法—去补丁合并法.首先基于kd-tree算法将三维耳廓配准后的两幅网格快速分割为重叠区域与非重叠区域;然后根据连通性对重叠区域和非重叠区域进行分块,并从重叠区域分块中去除冗余的补丁块、构建边界点;最后基于边界点将保留的重叠区域网格与邻接的非重叠区域网格缝合.实验结果表明,与同类算法相比,本文方法具有较好的合并效果与较高的计算效率.     

光线追踪的kd-tree构造

针对kd—tree的结构会直接影响光线追踪的渲染速度,结合SAH思想,设计和实现了一种引入光线的构造kd—tree的方法,简化构造过程巾的计算,并生成优于用普通二分法及原始SAH思想构造的kd—tree。实验证明,该方法可加快渲染速度且场景效果不会变差,适用于游戏型学习软件及游戏。     

基于二维Gamma分布的激光点云去噪

利用地面激光扫描仪测量时,由于空气中尘埃等因素会产生噪声点,对后期三维建模等应用带来不利影响。在现有研究成果基础上,深入分析散乱点云的近邻域特性,采用基于二维Gamma分布实现点云去噪,并在kd-tree索引支持下对其进行优化,通过邻域均值和邻域距离变化斜率两个约束条件共同移除噪声点。实验结果表明,本文算法能自动识别噪声点,降低人工设置阈值的影响,并与传统的基于正态分布的邻域点去噪算法进行对比,实验效果较优,达到了预期效果。