引用本文

李可, 高清维, 卢一相, 孙冬, 竺德. 基于区域正交化分割的平面点集凸包算法. 自动化学报, 2022, 48(12): 2972−2980 doi: 10.16383/j.aas.c190590

Li Ke, Gao Qing-Wei, Lu Yi-Xiang, Sun Dong, Zhu De. A convex hull algorithm for plane point sets based on region normalization segmentation. Acta Automatica Sinica, 2022, 48(12): 2972−2980 doi: 10.16383/j.aas.c190590

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190590

关键词

平面点集，凸包，正交化分割，并行算法

摘要

为解决实际工程应用中具有超大规模的平面点集的凸包计算问题, 提出了一种基于点集所在区域正交化分割的新算法. 利用点集几何结构的部分极点对平面点集进行正交化分割, 以获取不相干的点集子集簇, 再对所有点集子集分别计算其凸包极点, 最后合并极点得到凸包点集. 在不同层级的正交化分割过程中, 根据已知极点的信息, 逐层舍去对于凸包极点生成没有贡献的无效点, 进而提高算法运行效率. 在与目前常用凸包算法的对比实验中, 该算法处理超大规模的平面点集时稳定性高且速度更快.

文章导读

一组点的凸包是指包含这些点的最小凸多边形[1], 凸包问题是计算几何和图形学中最基础的问题之一. 平面凸包可以用来处理聚类分析[2-5], 围栏问题和城市规划问题等等. 在GIS应用[6]中, 凸包可以快速获得区域地理的基本轮廓和最有效边界信息, 方便定位与数字化建模. 在模式识别学科的研究中, 凸包的应用对于优化数据结构和降低数据计算规模提供了新思路. 凸包算法[7-10]在人工智能、人脸识别[11-12]等前沿领域均有不同程度的应用.

常用的二维平面点集凸包算法有Graham算法[13]、Jarvis步进算法[14]和穷举算法等, 这些经典算法在处理少量数据时表现出色, 但是当平面点集数据量超过106数量级时效率较差, 所以不能推广到具有大规模数据集的工程中使用. 为解决实际工程应用中具有超大规模的平面点集的凸包计算问题, 出现了许多快速凸包算法的研究. 文献[15]中提出了一种提高排序效率的排序算法, 使得在理论上凸包算法的时间复杂度可以降低为排序算法的时间复杂度. 文献[1]提出将二维快速凸包算法与广义超越算法相结合, 当输入包含非极值点时, 算法运行更快, 并且占用内存更少, 但是当使用浮点算法时, 可能会导致严重的错误. 文献[16-17]提出了基于GPU加速的方式来提高凸包问题求解的效率. 文献[10]提出了一种计算平面自由曲面精确凸包的高效实时算法, 该算法建立在圆弧构造的近似凸包上, 通过对圆弧进行简单的几何检验, 来确定近似的凸壳线段. 文献[18]描述了平面点集凸包的四种空间效率算法, 这些算法的输出与输入位于同一位置, 并且只使用少量的额外内存. 文献[19]提出了使用主成分分析法对点集预处理来改善凸包算法效率的递归算法, 但计算过程中进行多次坐标变换, 使得该算法较为复杂. 文献[20]利用二维平面空间象限的几何和对称特性提出对称凸包算法, 对点集数较大的计算效果有明显的改善.

通过对平面点集所在区域进行正交化分割, 可以得到一种基于点集所在区域正交化分割的新算法, 该算法使得分割得到的点集子集的凸包极点生成过程可以在时间上同步进行. 对于大规模的点集数据, 分割的层次越深, 并行化的程度就越高, 运算的时间花销就会越低. 段落内容安排如下: 第1节详细介绍了该算法的原理, 包括点集区域正交化分割的规则和具体过程, 以及单个子集中凸包极点的生成步骤. 第2节在特殊情况和平均情况下分析了凸包极点生成算法的时间复杂度. 第3节给出一些实验数据, 比较了该算法与其他一些凸包算法的运行效率, 还测试了大规模平面点集数据计算凸包的时间花销. 第4节对全文进行了总结, 并提出进一步的研究方向.

图 1  极值点结构图

图 2  点集子集第二层级正交化分割图

图 3  算法并行化流程图

对于大规模平面点集凸包问题的求解, 本文提出了基于点集所在区域正交化分割的凸包极点生成算法. 算法前期对点集数据所在区域进行正交化分割, 可以避免数据冗余和无效计算, 后期凸包极点生成的过程中, 通过不断地剔除掉点集中的非凸包极点, 可以提高程序的运行效率. 当点集数据的规模在500万时该算法仍然可以在1秒内完成凸包问题的求解, 这对于工程应用有着重要的意义. 由大量实验得到的正交化分割层级设置的结论, 也为该算法在实际问题中的应用提供了重要的参考. 一系列的数值实验结果表明, 该算法准确、高效、实用性强, 并且正交化分割的层级参数设置具备很高的鲁棒性.

作者简介

李可

安徽大学电气工程与自动化学院硕士研究生. 主要研究方向为图像处理. E-mail: likea310@163.com

高清维

安徽大学电气工程与自动化学院教授. 主要研究方向为数字信号处理, 小波变换与应用, 多尺度几何分析, 混沌与分形理论与应用. 本文通信作者.E-mail: qingweigao@ahu.edu.cn

卢一相

安徽大学电气工程与自动化学院教授. 主要研究方向为图像处理, 信号的多尺度几何分解, 统计信号处理和稀疏表示.E-mail: lyxahu@ahu.edu.cn

孙冬

安徽大学电气工程与自动化学院教授. 主要研究方向为图像处理, 模式识别, 非线性动力学信号处理, 计算机图形学和深度学习.E-mail: sundong@ahu.edu.cn

竺德

安徽大学电气工程与自动化学院博士研究生. 主要研究方向为图像处理和模式识别.E-mail: sundong@ahu.edu.cn