基于热方法的骨架提取算法

计算机与现代化 ›› 2022, Vol. 0 ›› Issue (03): 59-63.

基于热方法的骨架提取算法

(河海大学理学院,江苏南京211100)

出版日期:2022-04-29 发布日期:2022-04-29
作者简介:苏辰耀(1997—),男,江苏苏州人,硕士研究生,研究方向:图像及曲面分析,E-mail: scyhhu10019@163.com; 通信作者:刘向阳(1977—),男,副教授,博士,研究方向:图像与视频分析,数据分析,机器学习,E-mail: liuxy@hhu.edu.cn。
基金资助:
国家自然科学基金资助项目(61001139)

Skeleton Extraction Algorithm Based on Heat Method

(College of Science, Hohai University, Nanjing 211100, China)

Online:2022-04-29 Published:2022-04-29

摘要/Abstract

摘要： 骨架提取是形状表示的重要分支，在图像压缩、模式识别和形状匹配等领域中都有着广泛应用。本文提出一种基于热方法的骨架提取算法。该方法首先对目标区域构建三角网格，通过求解热传导方程找到距离增加的方向，再利用泊松方程还原测地距离。然后引入投票法的思想来确定骨架端点，通过路径回溯得到目标形状的连续骨架线。最后对终点聚类，检测并提取环形骨架。算法只需要求解2个稀疏线性方程组，因而具有鲁棒性强、精度高且易于操作等优点。同时，预计算中的一些信息可以被重复使用，减少内存占用和时间消耗。实验结果表明，该算法可将目标形状的骨架准确地提取出来。

关键词: 骨架提取, 热方法, 测地距离, 投票法

Abstract: Skeleton extraction is an important branch of shape representation and has a wide range of applications in the image compression, pattern recognition and shape matching. This paper proposes a skeleton extraction algorithm based on heat method. The algorithm first constructs triangle meshes for the target region, finds the direction of increasing distance by solving the heat conduction equation, and uses the Poisson equation to restore the geodesic distance. Then the endpoints of the skeletons are determined by using the voting method, and the continuous skeleton lines are obtained by the paths backtracking. Finally, the skeletons of loops are detected and extracted by clustering the end points. The algorithm is robust, accurate and simple to implement since it only needs to solve a pair of standard sparse linear systems. In addition, some information in the pre-calculated can be reused, which reduce memory footprint and time consumption. The experimental results show that the algorithm can extract the skeleton of target shape accurately.

Key words: skeleton extraction, heat method, geodesic distance, voting method

苏辰耀, 刘向阳. 基于热方法的骨架提取算法[J]. 计算机与现代化, 2022, 0(03): 59-63.

SU Chen-yao, LIU Xiang-yang. Skeleton Extraction Algorithm Based on Heat Method[J]. Computer and Modernization, 2022, 0(03): 59-63.

参考文献

［1］ GAYATHRI S, SRIDHAR V. An improved fast thinning algorithm for fingerprint image［J］. International Journal of Engineering Science and Innovative Technology, 2013,2(1):264-270.
［2］ LI C, YIN Y, WU P, et al. Pattern recognition and correction method for skeleton lines at small patch boundaries［J］. Transactions in GIS, 2020,24(5):1402-1426.
［3］刘砚菊,宋鑫,宋建辉,等. 基于图像中物体骨架形状特征的目标匹配［J］. 沈阳理工大学学报, 2019,38(3):73-77.
［4］ CHEN H W, ZHU R D, LI M C, et al. Pixel-by-pixel local dimming for high-dynamic-range liquid crystal displays［J］. Optics Express, 2017,25(3):1973-1984.
［5］ MA J, REN X, YUREVICH T V. A novel fast iterative parallel thinning algorithm［C］// Proceedings of the 2020 4th International Conference on Vision, Image and Signal Processing. 2020:1-5.
［6］袁良友,周航,韩丹,等. 引入平滑迭代的骨架提取改进算法［J］. 计算机工程与应用, 2020,56(24):194-199.
［7］ CHAO X, XIAO X, LUO Y, et al. New skeleton extraction method based on distance transform［J］. Chinese Journal of Scientific Instrument, 2012,33(12):2851-2856.
［8］ TELEA A， VAN WIJK J J. An augmented fast marching method for computing skeletons and centerlines［C］// Proceedings of the Symposium on Data Visualisation. 2002:251-259.
［9］ GUO Y H, SENGUR A. A novel 3D skeleton algorithm based on neutrosophic cost function［J］. Applied Soft Computing, 2015,36:210-217.
［10］KOTSUR D, TERESHCHENKO V. Optimization heuristics for computing the Voronoi skeleton［C］// International Conference on Computational Science. 2019:96-111.
［11］SUREZ A J F, HUBERT E. Scaffolding skeletons using spherical Voronoi diagrams［J］. Electronic Notes in Discrete Mathematics, 2017,62:45-50.
［12］HASSOUNA M S, FARAG A A. Robust centerline extraction framework using level sets［C］// 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2005:458-465.
［13］SZWEDOWSKI T D, FIALKOV J, PAKDEL A, et al. An optimized process flow for rapid segmentation of cortical bones of the craniofacial skeleton using the level-set method［J］. Dentomaxillofacial Radiology, 2013,42(4):1-6.
［14］YANG Z H, GUO F F, DONG P. Robust skeleton extraction of gray images based on level set approach［J］. Journal of Multimedia, 2013,8(1):24-31.
［15］SETHIAN J A, VLADIMIRSKY A. Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes［J］. Proceedings of the National Academy of Sciences, 2000,97(11):5699-5703.
［16］MIREBEAU J M, PORTEGIES J. Hamiltonian fast marching: A numerical solver for anisotropic and non-holonomic Eikonal PDEs［J］. Image Processing on Line, 2019,9:47-93.
［17］CRANE K, WEISCHEDEL C, WARDETZKY M. Geodesics in heat: A new approach to computing distance based on heat flow［J］. ACM Transactions on Graphics (TOG), 2013,32(5):1-11.
［18］YANG J M, STERN F. A highly scalable massively parallel fast marching method for the Eikonal equation［J］. Journal of Computational Physics, 2017,332:333-362.
［19］CRANE K, WEISCHEDEL C, WARDETZKY M. The heat method for distance computation［J］. Communications of the ACM, 2017,60(11):90-99.
［20］SHARP N, CRANE K. A laplacian for nonmanifold triangle meshes［J］. Computer Graphics Forum, 2020,39(5):69-80.
［21］YANG F, COHEN L D. Geodesic distance and curves through isotropic and anisotropic heat equations on images and surfaces［J］. Journal of Mathematical Imaging and Vision, 2016,55(2):210-228.
［22］ROUCHDY Y, COHEN L D. Geodesic voting for the automatic extraction of tree structures. Methods and applications［J］. Computer Vision and Image Understanding, 2013,117(10):1453-1467.
［23］BOUIX S, MARTIN-FERNANDEZ M, UNGAR L, et al. On evaluating brain tissue classifiers without a ground truth［J］. Neuroimage, 2007,36(4):1207-1224.