一种距离场约束下的普适细化算法*

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (2): 189–195.

一种距离场约束下的普适细化算法*

颜廷秦^1·2**，周昌雄¹，刘淑芬¹

出版日期:2015-10-30 发布日期:2015-10-30
作者简介: (1.苏州市职业大学电子信息工程系，苏州，215104;2.苏州市数字化设计与制造技术重点实验室，苏州，215104)
基金资助:
国家自然科学基金(60970058)，江苏省自然科学基金(BK2009131) ,苏州市科技基础设施建设计划
(SZS201009),苏州市职业大学创新团队建设项日(3100125),苏州市职业大学校级课题(2012SZDYY04 )，江苏省青蓝工程

A universal thinning algorithm restricted by distance

Yan Ting一Qin^1.2，Zhou Chang一Xiong¹,Liu Shu一Fen¹

Online:2015-10-30 Published:2015-10-30
About author: (1 .Department of Electronic and Information Engineering,Suzhou Vocational University,Suzhou,215104,China
2. Suzhou Key Laboratory of Digital Design and Manufacturing Technology, Suzhou, 215104 , China)

摘要/Abstract

摘要： 骨架提取方法可分为两类:一是基于距离场的方法，其次是细化算法.距离场方法提取的骨架
由离散的极值点组成，能够准确定位图像中心，但是骨架是不连续的;细化算法提取的骨架连续性好，但
是容易偏离图像的中心.K3M算法是一种优秀的细化算法，能够提取不同类型图像的骨架，为了提高这
一算法提取骨架的居中性质，引入距离场概念，提出距离场约束的K3M骨架提取算法.对目标图像进行
距离转换，形成距离场;依据距离场的等高线，按从小到大的顺序依次进行K3M算法细化;最后，把骨架
处理为1个像素宽度.通过不同类型图像的大量实验，可以看出，这种方法提取的骨架与距离场脊线的
吻合度高，更加符合最大内切圆的骨架定义，具有一定的理论研究意义;同时算法能够很好地完成多种
类型图像的骨架提取，实用价值上也具有普遍意义.

Abstract: Skeleton describes the topological structure of objects,and it is located at the geometric center of objects，
which is a simple representation of the original object, image skeleton can be defined as the trajectory of the maxi-
mum inscribed circle center,which is recognized as the most accurate description method. Skeleton extraction method
is mainly divided into two categories;one is based on the distance field，and the other is based on thinning. Skeleton
extracted with distance field method is composed of discrete maximum points,which is not continuous. On the other
side,the skeleton extracted with thinning algorithm is easy to deviate from the original center of the image，which is
not in conformity with the definition of largest inscribed circle trajectory. Our work is based on the advantage of
these two kinds of algorithm. The algorithm of K3M is the most excellent one in thinning field. This algorithm can
get a skeleton with a pixel width,and the process of iterative is clcar,whosc result can maintain the same angle of in-
tersecting line as the original image at junctions. So it is widely used to extract skeleton for various types of image.
The K3M algorithm is essentially a iterative thinning algorithm. Because the image data is discrete, so the iterative
process cannot be strictly in accordance with the image contraction direction, and the skeleton locating is not accurate
enough. Distance transform is an effective method to indicate image center. For a binary image,define a distance value
for each internal pixel of the object，which is the shortest distance of this pixel to the target edge, such that the dis-
tance values corresponding to all object pixels form a distance field.The calculation of chessboard distance is simple，
and it can satisfy general applications, so it is usually used for distance transform. For improving the centralization
property of skeleton for K3M algorithm,distance transformation is introduced，and the K3M skeleton extraction al-
gorithm is proposed in this article.lmplementing distance transformation on the object image, get the distance field;
running the K3M algorithm on the contours of distance field，according to the order from little to large; as the last
step,make the width of the skeleton is 1 pixel. Experiments of this algorithm with lots of different kinds of images
have been finished，the skeleton extracted with which fit the spine of distance field more closely than K3M algo-
rithm,and satisfy the skeleton definition of maximum incircle.The results of the experiments indicate that this algo-
rithm will play an important role in both theoretical research and practical application.

颜廷秦^1·2**，周昌雄¹，刘淑芬¹
. 一种距离场约束下的普适细化算法*[J]. 南京大学学报(自然科学版), 2013, 49(2): 189–195.

Yan Ting一Qin^1.2，Zhou Chang一Xiong¹,Liu Shu一Fen¹. A universal thinning algorithm restricted by distance[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(2): 189–195.

参考文献

[1]Li C, Peng F R，Lu J F. Skeleton extraction algo- rithm based on distance field thinning. Microeler
tronics and Computer, 201 1，28(10):114一117，121.(李川，彭甫铭，陆建峰.基于距离场细化
的骨架提取算法.微电子学与计算机，2011,28 (10):114一117，121).
[2]Liu W Y,Bai X,Zhu U X. A skclctorrgrowing algo- rithm based on boundary curve evolution. Acta Au-
tomatica Sinica,2006,32(2) ;256-262.(刘文予，白翔，朱光喜.基于边界曲线演化模型的生长骨架算法.自动化学报，2006,32(2):256-62).
[3]Kang W X,Deng F Q. A skcletonization method for vein patterns using template and neighborhood infor-
mation. Journal of Image and Graphics,2010，15(3): 378 -384.(康文雄，邓飞其.利用模板和邻域信息
的静脉骨架提取新算法.中国图像图形学报，2010，15(3):378一384).
[4]Wang S W, Li Y J ，Zhang K. 3D target recogni tion based on fast skeleton extraction. Acta Pho
tonica Sinica, 2010.39(7).1278一1283.
[5]Bai X，L J Latecki，Liu W Y. Skeleton pruning by contour partitioning with discrete curve evolu-
tion. IEEE Transactions on Pattern Analysis and Machine Intelligence,2007，29(3):449一462.
[6]Au O K C,Tai C L,Chu H K,et al. Skeleton extrac tion by mesh contraction. ACM Transactions on Graphics,2008,27(3),44:1一10.
[7]Wang Y S,Lee T Y. Curve skeleton extraction u-sing iterative least squares optimization, IEEE
Transactions on Visualization and Computer Graphics,2008,14(4):926~936.
[8]Blum H. Biological shape and visual science(pai- tI ).Journal of Theoretical Biology, 1973，38(2): 205一287.
[9]Sankari M，Meena C. Object matching using skel- etonization based on hamming distance. lnterna-
tional Journal of Computer Applications,2011，28 (7):46一50.
[10]Wong W T, Frank Y S, Su T F. Thinning algo- rithm s based on quadtree and octree representa-
dons. Journal of information Science，2006，176 (10):1379一1394.
[11]Shang L F, Zhang Y. A class of binary images thinning using two PCVNNs. Neurocomputing, 2007，70(4一6):1096一1101.
[12]Carlo A,Gabriela S di Baja,Luca S. A parallel al-gorithm to skcletonize the distance transform of
3D objects, Image and Vision Computing, 2009，27(6):666一672.
[13]Hu Y，Hou Y，Xu X H. A 3-D center path finding algorithm base on two distance fields. Journal of
Image and Graphics，2003，8(11):1272一1276. (胡英，侯悦，徐心和.基于双距离场的三维
中心路径提取算法.中国图像图形学报，2003,8 (11):1272一1276).
[14]Gao X, Liu C J，Feng J F. A novel algorithm of fingerprint thinning based on gabor phase. Acta
Scientiarum Naturalium Universitatis Pekinensis，2012,48(1);37-41.(高欣，刘重晋，封举富.
基于Gabor相位的指纹图像细化算法.北京大学学报(自然科学).2012,48(1);3741).
[15]Wang Y L，Ning X B,Yin Y L. Study on the fin- gerprint image thinning algorithm. Journal of
Nanjing University(Natural Sciences)2003，39 (4):468-475.(土业琳，宁新宝，尹义龙.指纹图
像细化算法的研究.南京大学学报(自然科学)，2003，39(4):468一475).
[16]Saeed K，Tabcdzki M, Rybnik M，et al. K3M; A universal algorithm for image skcletonization and
a review of thinning techniques. Applied Mathe- matics and Computer Science, 2010，20(2):317 -335.
[17]Saeed K, Nicdziclski R. Experiments on thinning of cursive-style alphabets, international Conference on
Information Technologics for Education,Science and Business, Minsk, Bclarus, 1999 , 45一49.
[18]Saeed K，Rybnik M，Tabedzki M, Implementation and advanced results on the norrinterrupted skel- etonization algorithm. Skarbek W. Computer A- nalysis of Images and Patterns, Lecture Notes in Computer Science,2001，212: 601一609.
[19]Saeed K.Text and image processing; Non-inter- rupted skcletonization. Proceedings of the 1^stIn-
ternational IEEE Conference on Circuits，Sys- tems, Comunications and Computers，2001，350 ~354.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed