基于凸包Graham扫描法的多系统融合精密单点定位快速选星算法

鉴于传统选星算法不能快速获得理想的卫星空间构型,在讨论定位精度计算模型、多系统融合GDOP值影响因素和分析基于凸包Graham扫描的选星算法原理的基础上,编程实现了基于凸包Graham扫描法的多系统融合精密单点定位快速选星算法,并对该算法的选星效果及定位效率进行仿真实验。结果表明,该算法的选星数能够稳定在8~10颗,其星座GDOP得到明显优化,空间构型得到明显改善;与传统方法相比,X、Y、H方向收敛时间的优化率分别达到40%、20%和7%,且定位精度更高,对于促进模糊度快速固定和改善定位效率有重要意义。

结合二叉树和Graham扫描技术的高效Delaunay三角网构建算法

为了提高不规则三角网的构建速度,提出了一种高效构建Delaunay三角网算法。首先对平面上的离散点集按一定的阈值进行分块,建立子块索引二叉树,然后利用Graham扫描技术对各子块构建Delaunay三角网,最后自底向上合并具有相同父节点的子块。通过具体实验与其他构网算法比较,该算法在构网速度上具有明显的优越性。

一种基于Graham扫描算法的空间点云结构化算法研究

在过度包装检测过程中,针对商品三维重建后的散乱点云无法进行后续空隙率判定的问题,提出一种基于Denaunay三角化和凸包算法的散乱点云结构化方法。首先,因为空间点云结构复杂,所以将空间点云进行切片和投影操作,也就是降维操作;其次,对投影数据点进行结构化处理,寻找初始点,依次对投影点按照极角大小进行排序;最后利用所构造的扫描线对数据点进行筛选和结构化。实验表明,基于Denaunay三角化和凸包算法的散乱点云结构化方法处理时间短,稳定性和精度高、适用性强,完全满足过度包装检测系统。与目前方法相比,该方法有更好的适用性,能够满足大多数平台的需求。

改进的Graham扫描三角形化简单多边形算法及其实现

Graham 扫描在计算几何中是一种基本的后追踪技术.Graham 扫描三角形化简单多边形算法三角形化一个,1个顶点的简单多边形 P 的时间为 D(kn),k-1是多边形 P 的凹顶点数.在最坏的情况下,此算法为 O(n^2).其数据结构简单,运行速度快、极易应用.改进后的算法进一步简化了检测“耳朵”的步骤,使之更严谨、简明,并用 C 语言编程实现了改进后的算法.

一种基于Graham三角剖分生成Delaunay三角网的算法

目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.

一种3D眼镜虚拟试戴系统的实现

针对人脸图像试戴3D眼镜过程中存在的镜腿遮挡人脸问题,文中提出一种基于人脸图像的3D眼镜虚拟试戴技术。利用构建的人脸形状的三维模型,使其在虚拟试戴中对镜腿起到消隐作用,解决镜腿的遮挡问题。文中对输入的人脸图像进行关键点检测,结合Graham扫描法求得人脸形状的凸多边形,利用平移扫描构建人脸形状的三维模型。此外,文中根据定位人脸图像上的关键点以及姿态估计后对三维眼镜模型的变换,将眼镜模型佩戴到人脸图像上。实验结果表明,该方法对于多视角的人脸图像实现了虚拟试戴效果,解决了多种视角下人脸图像试戴过程中镜腿的遮挡问题,虚拟试戴中镜腿遮挡平均准确率为94.5%,遮挡精度较高。

实时手指交互系统的嵌入式实现

为满足便携式设备中人机交互的需要,设计了嵌入式手指交互系统。研究了系统所采用的肤色分割、凸包计算、指尖检测等算法,并完成了硬件设计。首先,根据肤色的聚类特征,在对比分析常用彩色空间特性的基础上建立肤色模型,对人手进行分割;提出射线扫描法对经典Graham扫描算法进行改进,快速计算人手凸点。然后,分析了利用手指轮廓弯曲特征检测指尖的算法。最后,介绍了以DSP和FPGA为微处理器构成的硬件系统。实验结果表明,设计的系统对自然伸展的单个手指正确检测率为95.2%,对弯曲手指的正确检测率为92.6%,对在非目标手指干扰下的正确检测率为90.1%;而对指尖的定位最大偏移量为2.12 mm;指尖定位总耗时约为23 ms。所设计的嵌入式手指交互系统稳定可靠、满足实时要求。

一种平面点集的高效凸包算法

凸包问题是计算几何的基本问题之一。为实时计算平面点集的凸包,近年来许多学者提出很多优秀的算法,但依然不能满足实际中的实时性需求。为此,本文提出一种简单但高效快速的凸包算法。由于凸包点必然位于平面点集边缘,本文算法能够快速地筛选出极少量的凸包点候选点集,这是本算法的核心优势。然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或其他任何已有的凸包检测方法,即可快速而准确地计算出点集的凸包。经典的Graham扫描算法使用一个基点计算凸包,本文的改进算法则是根据凸包候选点的分布情况,将点集分成4个子块,也即使用4个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包。实验中,采用一组公开的动物骨骼点云数据作为一次测试集。在凸包计算完全正确的情况下,当点数约为3×1 0~5左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为3×10~6时,本算法的计算时间比其他方法减少5.42倍。点数越多,所提出算法就表现出越明显的优势。

两维区域三角剖分的新算法

提出一种两维区域三角剖分的新算法,算法首先递归应用求两维点集凸包的Graham扫描法,在原始区域的点集中求出一系列的凸包,同时原始两维区域也被这些凸包划分为多个独立的子区域,然后对相邻两个凸包之间的子区域进行三角剖分,从而实现对整个原始两维区域的三角剖分。和以往得算法相比,提出的算法的时间效率大大提高了,并且在作者参与的军队2110建设项目应用中也体现了良好的效果。

PostScript文件文字块多边形生成算法

针对利用PostScript文件制作数字报刊的实际应用,提出并实现了PostScript文件文字块多边形的生成算法。先对Post-Script文件进行解析,提取出文字的二维坐标,每一个文字块对应有一个二维点集。运用Graham扫描法,按顺时针方向构造出二维点集对应的凸包。对射线交叉法进行改进,降低运算复杂性,并运用该算法,对凸包进行整形。生成文字块的多边形,结果与文字块的形状准确重合。

一种凸包的改进算法设计与实现

给出一种求解多边形凸包的改进算法,该算法采取构造一个四边形并删除其内部的点集,从而达到减少扫描次数、提高运算速度的目的。该算法的时间复杂度为O(nlogn),具有实现简单,且比Graham扫描算法性能更好的特点。实验结果表明,改进后算法进一步提高了运算性能,效果更好。

长廊最短路径的最优算法

定义了长廊为平面上由一序列凸四边形构成的有界连通区域 ,提出长廊最短路径问题 ,并给出求长廊最短路径的一个算法 ,最后证明该算法的正确性和在最坏情况下的最优性 .

计算平面点集凸包的实时插入算法

讨论平面点集的凸包实时插入算法。算法基于Graham扫描算法,对3个点检测顺序的转向。本文证明,当S的N个点以流的形式进入系统,计算S的凸包所需的检测次数小于3N。

一种两维三角剖分的新算法

提出一种两维三角剖分的新算法,算法首先应用求两维点集凸包的Graham扫描法,求出两维点集的凸包,然后将凸包包含的点从原有点集中去掉,求出剩余点集的凸包.如此递归应用Graham扫描法求出一系列凸包,并将原始区域划分为多个独立的子区域,然后利用本文中提出的方法对2个凸包之间的子区域进行三角剖分,从而实现对整个原始区域的三角剖分.

测定简单多边形凸包的快速算法

计算凸包问题不仅是计算几何的基本工具之一,而且在实际应用中也是很重要的,本文运用Graham扫描技术及双动线检验的方法,构造了测定简单多边形凸包的O(n)快速算法。

基于牛顿迭代法的WC晶体界面能函数规则化算法

本文基于牛顿迭代法,实现WC-Co硬质合金中WC晶体界面能函数的规则化。将WC晶体界面能函数γ=γ(θ)的规则化问题转化为求解曲线ρ=1/γ(θ)在区间[0,π/3]上的两个分割点的问题;构造求解两个分割点的非线性模型,运用牛顿迭代法求解,并考虑以Graham扫描法的计算结果作为迭代初值。通过牛顿迭代法求得曲线ρ=1/γ(θ)在区间[0,π/3]上的两个分割点的近似值,最终实现了WC晶体界面能函数的规则化。针对本文所研究的界面能函数,基于牛顿迭代法的规则化算法比基于Graham扫描法的规则化算法更高效。

基于点云凸包算法的输电线路树障面积与高度计算实现方法

输电线路走廊大部分都有植被,植被的树木生长会威胁到输电线路的安全运行,所以树障清障是输电线路一项重要的日常工作。为保证输电线路树障清障的工程有计划准确的统筹和执行。现有的科技进步已发展到能通过航测手段生成点云进行输电线路导线与树障之间的安全距离分析,解决了发现树障隐患的问题。但现有的方式只是分析出树障点和安全距离,后期还要花费大量人力到现场勘察树障高度和面积确认工程量。本文提出了一种利用Graham扫描算法计算树障高度与面积的方法方式,将工作量大的现场勘察转移到在计算机进行点云算法估算。

基于形态特征提取的中医齿痕舌客观化研究

针对目前中医齿痕舌诊断缺乏客观化和量化指标的问题,提出齿痕舌多指标客观化判别检测方法,以实现辅助中医临床对齿痕舌的综合性检测。首先对所采集到的舌象图片提取感兴趣的齿痕区域,并进行区域二值化预处理;然后使用Graham扫描法提取齿痕凹陷特征并通过支持向量机算法对齿痕有无进行分类判别;对于齿痕数量,通过改进的道格拉斯-普克算法拟合齿痕边缘曲线,将曲线满足条件的极小值个数作为齿痕个数;最后结合齿痕数量与齿痕深度对齿痕程度进行判别。该算法对齿痕有无的判别正确率为80.86%,对齿痕数量的检测正确率为80.00%,对齿痕程度的检测正确率为89.63%。实验结果表明,该算法能较好地实现齿痕舌的综合检测,并提供相应客观化参数辅助中医临床诊疗。

利用运动线索的单目深度测量

目的传统的单目视觉深度测量方法具有设备简单、价格低廉、运算速度快等优点,但需要对相机进行复杂标定,并且只在特定的场景条件下适用。为此,提出基于运动视差线索的物体深度测量方法,从图像中提取特征点,利用特征点与图像深度的关系得到测量结果。方法对两幅图像进行分割,获取被测量物体所在区域;然后采用本文提出的改进的尺度不变特征变换SIFT(scale-invariant feature transtorm)算法对两幅图像进行匹配,结合图像匹配和图像分割的结果获取被测量物体的匹配结果;用Graham扫描法求得匹配后特征点的凸包,获取凸包上最长线段的长度;最后利用相机成像的基本原理和三角几何知识求出图像深度。结果实验结果表明,本文方法在测量精度和实时性两方面都有所提升。当图像中的物体不被遮挡时,实际距离与测量距离之间的误差为2.60%,测量距离的时间消耗为1.577 s;当图像中的物体存在部分遮挡时,该方法也获得了较好的测量结果,实际距离与测量距离之间的误差为3.19%,测量距离所需时间为1.689 s。结论利用两幅图像上的特征点来估计图像深度,对图像中物体存在部分遮挡情况具有良好的鲁棒性,同时避免了复杂的摄像机标定过程,具有实际应用价值。

不规则多边形区域搜索航路规划算法

为提高无人机在山地等复杂区域实施搜索任务的效率,提出一种针对不规则多边形区域的搜索航路规划算法。首先,采用Graham扫描法解算出任务区域的凸多边形(凸包),根据凸包解算出最小外接矩形;然后,根据无人机所在位置及传感器实时采集的信息解算出搜索进入点,完成光栅式搜索航路规划;最后,根据任务区域形状对搜索进入点进行修正,减少不必要的搜索,以缩短航程。经验证,相比直接在外接矩形区域搜索航路的传统算法,不规则多边形区域搜索航路规划算法的航线长度减少了24.8%,在大幅提升搜索效率的前提下,规避了区域外扩带来的飞行风险,提升了无人机飞行的安全性。