-
摘要: 提出了一种快速的骨架提取算法.该方法首先在轮廓离散曲线演化的基础上，根据显著凸顶点的类型将轮廓多边形进行分块，得到一个主分支轮廓和多个水平分支轮廓；然后分别利用水平截线法和垂直截线法提取骨架的主分支和水平分支；最后将水平分支拼接在主分支上，得到完整的骨架.实验结果表明，该骨架提取算法可以得到连通的骨架，并在Kimia数据集上取得了较好的效果.此外，算法在自然图像上的效果也很好，尤其适用于视频中的行人骨架提取.与经典骨架提取算法相比，该算法的时间复杂度较低，可以满足实时处理的要求.Abstract: A fast skeleton extraction algorithm is proposed in this paper. Firstly, some vertices of the polygon contour are labeled as salient convex vertices by using discrete curve evolution, then the polygon contour is partitioned into a main branch and several horizontal branches according to the types of these salient convex vertices. Secondly, the horizontal secant lines method is used to get the skeleton of the main branch and the vertical secant line method is used to obtain the skeletons of horizontal branches separately. Finally, by connecting the skeletons of horizontal branches to main branch skeleton, the final skeleton of a given contour is obtained. Experimental results show that the proposed skeleton extraction algorithm has good performance on Kimia data set. In addition, results on pedestrian video are presented to show that the proposed algorithm performs well on natural images, too. Furthermore, the time complexity of the algorithm is lower than those of other classical algorithms and it satisfies the requirement of real-time processing of videos.
-
图 7 不同的K0值得到的原始轮廓和顶点个数N
Fig. 7 Original contour with different vertices number N according to different K0
图 11 放大1, 5, 10倍实验结果
Fig. 11 Results of skeletonization with original image, magnified 5 times and magnified 10 times
表 1 图像骨架提取的运行时间
Table 1 The running time of skeletonization
图片大小 原始轮廓顶点数 轮廓提取 轮廓简化 离散曲线演化 截线法提取骨架 1 560×2 250 875 0.0171 s 0.0305 s 0.0045 s 0.1294 s 
下载: 导出CSV
表 2 不同尺寸图片骨架提取的运行时间对比
Table 2 The comparison of running time of skeletonization of different image sizes
图片大小 本文算法 文献[32]算法运行时间 原始轮廓顶点数 运行时间 1 156×225 51 0.0036 s 8.0328 s 2 312×450 100 0.0089 s 18.6070 s 3 468×675 100 0.0125 s 38.2181 s 4 624×900 309 0.0506 s 64.4884 s 5 780×1 125 327 0.0643 s 111.5206 s 6 936×1 350 412 0.0741 s 218.3063 s 7 1 092×1 575 437 0.0922 s 267.5379 s 8 1 248×1 800 598 0.1348 s 410.8053 s 9 1 404×2 025 783 0.1572 s 545.5659 s 10 1 560×2 250 875 0.2128 s 733.5245 s
下载: 导出CSV
-
[1] 郑丹晨, 韩敏.基于期望首达时间的形状距离学习算法.自动化学报, 2014, 40(1):92-99 http://www.aas.net.cn/CN/abstract/abstract18270.shtmlZheng Dan-Chen, Han Min. Learning shape distance based on mean first-passage time. Acta Automatica Sinica, 2014, 40(1):92-99 http://www.aas.net.cn/CN/abstract/abstract18270.shtml [2] 杨亚飞, 郑丹晨, 韩敏.一种基于多尺度轮廓点空间关系特征的形状匹配方法.自动化学报, 2015, 41(8):1405-1411 http://www.aas.net.cn/CN/abstract/abstract18715.shtmlYang Ya-Fei, Zheng Dan-Chen, Han Min. A shape matching method using spatial features of multi-scaled contours. Acta Automatica Sinica, 2015, 41(8):1405-1411 http://www.aas.net.cn/CN/abstract/abstract18715.shtml [3] 郑丹晨, 杨亚飞, 韩敏.一种基于广义期望首达时间的形状距离学习算法.自动化学报, 2016, 42(2):246-254 http://www.aas.net.cn/CN/abstract/abstract18814.shtmlZheng Dan-Chen, Yang Ya-Fei, Han Min. A shape distance learning algorithm based on generalized mean first-passage time. Acta Automatica Sinica, 2016, 42(2):246-254 http://www.aas.net.cn/CN/abstract/abstract18814.shtml [4] Bai X, Wang X G, Latecki L J, Liu W, Tu Z. Active skeleton for non-rigid object detection. In:Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto, Japan:IEEE, 2009. 575-582 http://cn.bing.com/academic/profile?id=2116482297&encoded=0&v=paper_preview&mkt=zh-cn [5] Bai X, Latecki L J. Path similarity skeleton graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7):1282-1292 doi: 10.1109/TPAMI.2007.70769 [6] Bai X, Yang X W, Yu D G, Latecki L J. Skeleton-based shape classification using path similarity. International Journal of Pattern Recognition and Artificial Intelligence, 2008, 22(4):733-746 doi: 10.1142/S0218001408006405 [7] Bai X, Liu W, Tu Z. Integrating contour and skeleton for shape classification. In:Proceedings of the 12th IEEE International Conference on Computer Vision Workshops (ICCV Workshops). Kyoto, Japan:IEEE, 2009. 360-367 http://cn.bing.com/academic/profile?id=2116663904&encoded=0&v=paper_preview&mkt=zh-cn [8] Wang B, Shen W, Liu W Y, You X, Bai X. Shape classification using tree-unions. In:Proceedings of the 20th International Conference on Pattern Recognition (ICPR). Istanbul, Turkey:IEEE, 2010. 983-986 http://cn.bing.com/academic/profile?id=2170467231&encoded=0&v=paper_preview&mkt=zh-cn [9] Zhou Yu, Liu Jun-Tao, Bai Xiang. Research and perspective on shape matching. Acta Automatica Sinica, 2012, 38(6):889-910(周瑜, 刘俊涛, 白翔.形状匹配方法研究与展望.自动化学报, 2012, 38(6):889-910) doi: 10.3724/SP.J.1004.2012.00889 [10] Chacko B P, Babu A P. Discrete curve evolution based skeleton pruning for character recognition. In:Proceedings of the 7th International Conference on Advances in Pattern Recognition (ICAPR09). Kolkata, India:IEEE, 2009. 402-405 http://cn.bing.com/academic/profile?id=2138738684&encoded=0&v=paper_preview&mkt=zh-cn [11] Rockett P I. An improved rotation-invariant thinning algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10):1671-1674 doi: 10.1109/TPAMI.2005.191 [12] Blum H. Biological shape and visual science (Part I). Journal of Theoretical Biology, 1973, 38(2):205-287 doi: 10.1016/0022-5193(73)90175-6 [13] Krinidis S, Chatzis V. A skeleton family generator via physics-based deformable models. IEEE Transactions on Image Processing, 2009, 18(1):1-11 doi: 10.1109/TIP.2008.2007351 [14] Xie W J, Thompson R P, Perucchio R. A topology-preserving parallel 3D thinning algorithm for extracting the curve skeleton. Pattern Recognition, 2003, 36(7):1529-1544 doi: 10.1016/S0031-3203(02)00348-5 [15] Leymarie F, Levine M D. Simulating the grassfire transform using an active contour model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(1):56-75 doi: 10.1109/34.107013 [16] Aurenhammer F. Voronoi diagrams——a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 1991, 23(3):345-405 doi: 10.1145/116873.116880 [17] Brandt J W, Algazi V R. Continuous skeleton computation by Voronoi diagram. CVGIP:Image Understanding, 1992, 55(3):329-338 doi: 10.1016/1049-9660(92)90030-7 [18] Brady M, Asada H. Smoothed local symmetries and their implementation. The International Journal of Robotics Research, 1984, 3(3):36-61 doi: 10.1177/027836498400300302 [19] Martínez-Pérez M P, Jiménez J, Navalón J L. A thinning algorithm based on contours. Computer Vision, Graphics, and Image Processing, 1987, 39(2):186-201 doi: 10.1016/S0734-189X(87)80165-2 [20] Yu Z, Bajaj C. A segmentation-free approach for skeletonization of gray-scale images via anisotropic vector diffusion. In:Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Rewgnition. San Diego, USA:IEEE, 2004. DOI: 10.1109/CVPR.2004.1315062 [21] Choi W P, Lam K M, Siu W C. Extraction of the Euclidean skeleton based on a connectivity criterion. Pattern Recognition, 2003, 36(3):721-729 doi: 10.1016/S0031-3203(02)00098-5 [22] Ge Y R, Fitzpatrick J M. On the generation of skeletons from discrete Euclidean distance maps. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(11):1055-1066 doi: 10.1109/34.544075 [23] Niblack C W, Gibbons P B, Capson D W. Generating skeletons and centerlines from the distance transform. CVGIP:Graphical Models and Image Processing, 1992, 54(5):420-437 doi: 10.1016/1049-9652(92)90026-T [24] Arcelli C, di Baja G S. A one-pass two-operation process to detect the skeletal pixels on the 4-distance transform. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989, 11(4):411-414 doi: 10.1109/34.19037 [25] Arcelli C, di Baja G S. Euclidean skeleton via centre-of-maximal-disc extraction. Image and Vision Computing, 1993, 11(3):163-173 doi: 10.1016/0262-8856(93)90055-L [26] Dimitrov P, Damon J N, Siddiqi K. Flux invariants for shape. In:Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Madison, WI, USA:IEEE, 2003. I-835-I-841 http://www.computer.org/csdl/proceedings/cvpr/2003/1900/01/index.html [27] Dimitrov P, Phillips C, Siddiqi K. Robust and efficient skeletal graphs. In:Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head Island, SC:IEEE, 2000. 417-423 http://cn.bing.com/academic/profile?id=2171820417&encoded=0&v=paper_preview&mkt=zh-cn [28] Vasilevskiy A, Siddiqi K. Flux maximizing geometric flows. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12):1565-1578 doi: 10.1109/TPAMI.2002.1114849 [29] Latecki L J, Lakämper R. Convexity rule for shape decomposition based on discrete contour evolution. Computer Vision and Image Understanding, 1999, 73(3):441-454 doi: 10.1006/cviu.1998.0738 [30] Bai X, Latecki L J. Discrete skeleton evolution. Energy Minimization Methods in Computer Vision and Pattern Recognition. Berlin Heidelberg:Springer, 2007. 362-374 http://cn.bing.com/academic/profile?id=16018152&encoded=0&v=paper_preview&mkt=zh-cn [31] Bai X, Latecki L J, Liu W Y. Skeleton pruning by contour partitioning with discrete curve evolution. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(3):449-462 doi: 10.1109/TPAMI.2007.59 [32] Shen W, Bai X, Yang X W, Latecki L J. Skeleton pruning as trade-off between skeleton simplicity and reconstruction error. Science China Information Sciences, 2013, 56(4):1-14 http://cn.bing.com/academic/profile?id=2099673295&encoded=0&v=paper_preview&mkt=zh-cn [33] Torsello A, Hancock E R. A skeletal measure of 2D shape similarity. Computer Vision and Image Understanding, 2004, 95(1):1-29 doi: 10.1016/j.cviu.2004.03.006 [34] Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(5):550-571 doi: 10.1109/TPAMI.2004.1273924 -
图(12) / 表(3)
计量
- 文章访问数: 2221
- HTML全文浏览量: 650
- PDF下载量: 1809
- 被引次数: 0
