2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于区域正交化分割的平面点集凸包算法

李可 高清维 卢一相 孙冬 竺德

李可, 高清维, 卢一相, 孙冬, 竺德. 基于区域正交化分割的平面点集凸包算法. 自动化学报, 2022, 48(12): 2972−2980 doi: 10.16383/j.aas.c190590
引用本文: 李可, 高清维, 卢一相, 孙冬, 竺德. 基于区域正交化分割的平面点集凸包算法. 自动化学报, 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
Citation: 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

基于区域正交化分割的平面点集凸包算法

doi: 10.16383/j.aas.c190590
基金项目: 国家自然科学基金(61402004, 61370110), 安徽省自然科学基金(2008085MF183, 2008085MF192)资助
详细信息
    作者简介:

    李可:安徽大学电气工程与自动化学院硕士研究生. 主要研究方向为图像处理. 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

A Convex Hull Algorithm for Plane Point Sets Based on Region Normalization Segmentation

Funds: Supported by National Natural Science Foundation of China (61402004, 61370110) and Natural Science Foundation of Anhui Province (2008085MF183, 2008085MF192)
More Information
    Author Bio:

    LI Ke Master student at the Sch-ool of Electrical Engineering and Automation, Anhui University. His main research interest is image processing

    GAO Qing-Wei Professor at the School of Electrical Engineering and Automation, Anhui University. His research interest covers digital signal processing, wavelet transform and applications, multi-scale geometric analysis, and chaos and fractal theory and applications. Corresponding author of this paper

    LU Yi-Xiang Professor at the School of Electrical Engineering and Automation, Anhui University. His research interest covers image processing, multi-scale geometric decomposition of signals, statistical signal processing and sparse representation

    SUN Dong Professor at the Sch-ool of Electrical Engineering and Automation, Anhui University. His research interest covers image processing, pattern recognition, nonlinear dynamic signal processing, computer graphics and deep learning

    ZHU De Ph.D. candidate at the School of Electrical Engineering and Automation, Anhui University. His research interest covers image processing and pattern recognition

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

    Fig.  1  Structure diagram of extreme points

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

    Fig.  2  Diagram of the second level orthogonalization of the subset of point sets

    图  3  算法并行化流程图

    Fig.  3  Parallel flow chart of the algorithm

    图  4  点集遍历示意图

    Fig.  4  Diagram of point sets traversal

    图  5  理想凸包极点分布图(h = 2, 3, 5, 9)和h = 5的遍历过程

    Fig.  5  Ideal convex hull pole map (h = 2, 3, 5, 9) and a traversal process with h = 5

    图  6  Iris数据集的部分凸包图形

    Fig.  6  Graphs of partial convex hull of Iris data set

    图  7  肺图像的修复

    Fig.  7  Restoration of lung image

    表  1  点集不同层级分割的子集点数

    Table  1  The number of points in the subset corresponding to different levels of segmentation

    层级 5000 1 万 5 万 10 万 20 万 50 万 100 万 200 万 500 万 800 万 1000 万
    1 438 873 4543 8893 17782 44541 88532 178749 449484 715181 885358
    2 65 123 644 1213 2404 6120 11861 24559 61273 97727 120068
    3 0 16 88 155 302 730 1398 3054 7967 12473 15307
    4 0 0 12 22 44 85 175 403 1032 1630 2053
    5 0 0 1 4 5 11 25 55 146 229 282
    下载: 导出CSV

    表  2  各算法运行时间 (s)

    Table  2  Runtime for different algorithms (s)

    点集点数 算法运行时间
    Graham Jarvis 文献 [19] 算法 1 本文算法
    5000 0.266 0.022 0.013 0.021 0.008
    10000 1.067 0.045 0.027 0.047 0.011
    50000 26.999 0.236 0.054 0.076 0.019
    100000 108.645 0.539 0.102 0.448 0.028
    150000 244.662 0.891 0.329 0.624 0.039
    200000 435.077 1.296 0.585 0.752 0.047
    下载: 导出CSV

    表  3  不同数量级点集的运行时间 (s)

    Table  3  Runtime comparison for different orders of magnitude point sets (s)

    类别 20 万 50 万 100 万 200 万 500 万
    0 0.586  0.048 1.574  0.102 3.315  0.197 6.964  0.384 18.509  0.989
    1 0.580  0.046 1.575  0.104 3.317  0.194 6.962  0.383 18.510  0.965
    2 0.589  0.047 1.574  0.103 3.312  0.201 6.962  0.386 18.506  1.021
    3 0.579  0.047 1.568  0.107 3.321  0.200 6.960  0.396 18.518  0.949
    4 0.581  0.045 1.574  0.106 3.312  0.202 6.963  0.392 18.509  0.959
    5 0.589  0.048 1.579  0.108 3.313  0.190 6.958  0.386 18.511  0.962
    6 0.585  0.048 1.573  0.105 3.317  0.197 6.988  0.390 18.513  0.970
    7 0.585  0.046 1.570  0.103 3.313  0.199 6.966  0.391 18.509  0.957
    8 0.591  0.050 1.574  0.105 3.315  0.200 6.963  0.405 18.518  0.959
    9 0.586  0.047 1.582  0.105 3.315  0.198 6.968  0.398 18.499  0.961
    10 0.584  0.046 1.575  0.105 3.313  0.196 6.962  0.385 18.510  1.019
    下载: 导出CSV
  • [1] Barber C B, Dobkin D P, Huhdanpaa H. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 1996, 22(4): 469−483 doi: 10.1145/235815.235821
    [2] Kim Y, Kim J. Convex hull ensemble machine for regression and classification. Knowledge and Information Systems, 2004, 6(6): 645−663 doi: 10.1007/s10115-003-0116-7
    [3] Ding S G, Nie X L, Qiao H, Zhang B. A fast algorithm of convex hull vertices selection for online classification. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(4): 792−806 doi: 10.1109/TNNLS.2017.2648038
    [4] Long P M, Servedio R A. Random classification noise defeats all convex potential boosters. Machine Learning, 2010, 78(3): 287−304 doi: 10.1007/s10994-009-5165-z
    [5] Chau A L, Li X O, Yu W. Convex and concave hulls for classification with support vector machine. Neurocomputing, 2013, 122: 198−209 doi: 10.1016/j.neucom.2013.05.040
    [6] Sadahiro Y. Number of polygons generated by map overlay: the case of convex polygons. Transactions in Gis, 2001, 5(4): 345−353 doi: 10.1111/1467-9671.00087
    [7] Chazelle B. An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry, 1993, 10(4): 377−409
    [8] Yao A C. A lower bound to finding convex hulls. Journal of the ACM, 1981, 28(4): 780−787 doi: 10.1145/322276.322289
    [9] Akl S G, Toussaint G T. A fast convex hull algorithm. Information Processing Letters, 1978, 7(5): 219−222 doi: 10.1016/0020-0190(78)90003-0
    [10] Kim Y J, Lee J, Kim M S, Elber G. Efficient convex hull computation for planar freeform curves. Computers & Graphics, 2011, 35(3): 698−705
    [11] Park M, Park C W, Park M, Lee C. Algorithm for detecting human faces based on convex-hull. Optics Express, 2002, 10(6): 274−279 doi: 10.1364/OE.10.000274
    [12] Zhou X F, Jiang W H, Tian Y J, Shi Y. Kernel subclass convex hull sample selection method for SVM on face recognition. Neurocomputing, 2010, 73(10−12): 2234−2246 doi: 10.1016/j.neucom.2010.01.008
    [13] Graham R L. An efficient algorith for determining the convex hull of a finite planar set. Information Processing Letters, 1972, 1(4): 132−133 doi: 10.1016/0020-0190(72)90045-2
    [14] Jarvis R A. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 1973, 2(1): 18−21 doi: 10.1016/0020-0190(73)90020-3
    [15] Andrew A M. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 1979, 9(5): 216−219 doi: 10.1016/0020-0190(79)90072-3
    [16] Stein A, Geva E, El-Sana J. CudaHull: fast parallel 3D convex hull on the GPU. Computers & Graphics, 2012, 36(4): 265−271
    [17] Tang M, Zhao J Y, Tong R F, Manocha D. GPU accelerated convex hull computation. Computers & Graphics, 2012, 36(5): 498−506
    [18] Brönnimann H, Iacono J, Katajainen J, Morin P, Morrison J, Toussaint G. Space-efficient planar convex hull algorithms. Theoretical Computer Science, 2004, 321(1): 25−40 doi: 10.1016/j.tcs.2003.05.004
    [19] 刘斌, 王涛. 一种高效的平面点集凸包递归算法. 自动化学报, 2012, 38(8): 1375−1379 doi: 10.3724/SP.J.1004.2012.01375

    Liu Bin, Wang Tao. An efficient convex hull algorithm for planar point set based on recursive method. Acta Automatica Sinica, 2012, 38(8): 1375−1379 doi: 10.3724/SP.J.1004.2012.01375
    [20] Beltran A, Mendoza S. SymmetricHull: a convex hull algorithm based on 2D geometry and symmetry. IEEE Latin America Transactions, 2018, 16(8): 2289−2295 doi: 10.1109/TLA.2018.8528248
    [21] 冯昌利, 张建勋, 梁睿, 代煜, 崔亮. 基于分形几何和最小凸包法的肺区域分割算法. 天津大学学报(自然科学与工程技术版), 2015, 48(10): 937−946

    Feng Chang-Li, Zhang Jian-Xun, Liang Rui, Dai Yu, Cui Liang. A lung region segmentation method based on the fractal theory and the minimal convex hull method. Journal of Tianjin University(Science and Technology), 2015, 48(10): 937−946
  • 加载中
图(7) / 表(3)
计量
  • 文章访问数:  396
  • HTML全文浏览量:  236
  • PDF下载量:  107
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-08-17
  • 录用日期:  2020-03-11
  • 网络出版日期:  2022-11-30
  • 刊出日期:  2022-12-23

目录

    /

    返回文章
    返回