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.
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[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 1stIn-
ternational IEEE Conference on Circuits，Sys- tems, Comunications and Computers，2001，350 ~354.
{{custom_fnGroup.title_en}}
Footnotes
{{custom_fn.content}}
PDF(610323 KB)
