北京生物医学工程

基于距离变换与路径规划的骨架提取算法

Extraction of skeleton based on distance transform and path planning

作者：张超芦勤罗述谦

单位：首都医科大学生物医学工程学院(北京100069)

分类号：

出版年·卷·期（页码）：2012·31·6（551-555）

摘要：

目的骨架具有与原始物体相同的拓扑与形状信息，能够有效地描述物体，在医学图像处理中有很好的应用前景，但传统基于距离变换的骨架提取难以保证骨架的连续性，因此引入骨架候选点概念以解决连续性问题。本文提出一种基于距离变换和路径规划的骨架提取算法。方法首先利用距离变换后的约束条件（局部距离变换最大值和局部距离变换梯度的模的最小值），选择骨架候选点，利用动态规划中最短路径原理连接骨架候选点。结果本文算法产生的结果与标准骨架对比，平均相似度达94%以上。结论基于距离变换和路径规划的骨架提取算法很好地保护了骨架的拓扑性和连续性，无需过多的后处理，并引入了相似度的概念来评价骨架算法。

Objective The topology and shape information of the skeleton are similar with the original object.The skeleton can effectively describe the object and has great application prospect in medical image processing.Traditional skeletonization based on distance transform cannot guarantee the connectivity of the skeleton,so we introduce candidate skeleton points (CSP) to solve the connectivity problem.In this paper,we propose a well-connected skeleton algorithm based on distance transform and path planning.Methods According to the constraints of distance transform (local maximum value of distance transform and local minimum points of the norm of distance transform gradient),candidate skeleton points are located,and the shortest path between CSPs can be determined using path planning theory.Results The comparison between the results of our proposed method and the standard centerline of the test images shows that the average of similarity measurement (SM) is above 94%.Conclusions The proposed algorithm based on distance transform and path planning can generate a connected skeleton with well preserved original object’s topology without requiring a post-processing step,and SM is defined to evaluate the accuracy of the skeleton.

参考文献：

［1］Blum H. A transformation for extracting new descriptors of shape［M］//Wathen-Dunn W,eds. Models for the Perception of Speech and Visual Form. Cambridge，MA:MIT Press,1967：362-380.
［2］Xu Y,Zhang H,Li H,et al. An improved algorithm for vessel centerline tracking in coronary angiograms［J］. Comput Meth Prog Bio，2007,88:131-143.
［3］廖志武. 2-D骨架提取算法研究进展［J］. 四川师范大学学报:自然科学版,2009，32(5):676-688.
Liao Zhiwu. A survey of 2-D skeletonization algorithm［J］. Journal of Sichuan Normal University：Natural Science,2009，32(5):676-688.
［3］Liao Z.A survey of 2-D skeletonization algorithm［J］. Journal of Sichuan Normal University:Natural Science,2009，32(5):676-688.
［4］Xia H,Tucker PG. Fast equal and biased distance fields for medial axis transform with meshing in mind［J］. Appl Math Model，2011，35(12):5804-5819.
［5］Ramanathan M,Gurumoorthy B. Interior medial axis transform computation of 3D objects bound by free-form surfaces［J］. Comput Aided Design,2010,42(12):1217-1231.
［6］Ding M,Tong R,Liao S,et al. An extension to 3D topological thinning method based on LUT for colon centerline extraction［J］. Comput Meth Prog Bio，2009，94(1):39-47.［7］Palágyi K. A 3D fully parallel surface-thinning algorithm［J］. Theor Comput Sci，2008，405:119-135.
［8］Lam L,Lee S. Thinning methodologies:a comprehensive survey ［J］. IEEE T Pattern Anal,1992,14(9):869-885.
［9］Jaishankar S,Pralhad RN. 3D off-Line path planning for aerial vehicle using distance transform technique［J］. Procedia Computer Science,2011，4:1306-1315.
［10］Couprie M,Coeurjolly D,Zrour R. Discrete bisector function and Euclidean skeleton in 2D and 3D［J］. Image and Vision Computing,2007，25:1543-1556.
［11］Boxer L. Efficient Computation of the euclidean distance transform［J］. Comput Vis Image Und,2000，80:379-383.
［12］Fu Y,Liu H,Wang S,et al. Skeleton-based active catheter navigation［J］. Int J Med Robot,2009,5(2):125-135.
［13］刘大鹏,孟晓林,张煜,等. 虚拟结肠镜的快速中心路径提取算法［J］. 中国医学物理学杂志,2010，27（3）:2254-2257.
Liu Dapeng,Meng Xiaolin,Zhang Yu,et al. Fast centerline extraction algorithm in virtual colonoscopy［J］. Chinese Journal of Medical Physics,2010，27(3):2254-2257.
［14］Sabry Hassouna M,Abdel-Hakim AE,Farag AA. PDE-based robust robotic navigation［J］. Image Vision Comput，2009，27(1-2):10-18.
［15］Malandain G,Fernhdez-Vidal S. Euclidean skeletons ［J］. Image and Vision Computing，1998，16:317-327.
［16］Hassouna MS,Farag AA. Variational curve skeletons using gradient vector flow［J］. IEEE Trans Pattern Anal Mach Intell,2009,31(12):2257-2274.
［17］Bellman RE. Dynamic Programming［M］. New York:Courier Dover Publication,2003.
［18］Dijkstra EW. A note on two problems in connexion with graphs ［J］. Numer Math，1959，1(1):269-271.
［19］Rutgers University. Rutgers university tool image database［EB/OL］. ［2012-01-12］. http://www. cs. rutgers. edu/pub/sven/rutfers-tools/.
［20］芦勤,罗述谦. 基于MR图像的人脑尾状核定量分析方法研究［J］. 北京生物医学工程,2010,29(2):120-124.
Lu Qin,Luo Shuqian. Caudate nucleus volume analysis of human brain based on MR images［J］. Beijing Biomedical Engineering,2010,29(2):120-124.

服务与反馈：

【文章下载】【加入收藏】

提示：您还未登录，请登录！点此登录