优化的梯度最短路径骨架提取算法.pdf

《优化的梯度最短路径骨架提取算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第53卷第2期厦门大学学报(自然科学版)Vo1．53No．22014年3月JournalofXiamenUniversity(NaturalScience)Mar．2O14优化的梯度最短路径骨架提取算法杨晨晖，刘聪(厦门大学信息科学与技术学院，福建厦门361005)摘要：计算二维图像的距离变换图，在距离图的基础上求出梯度图，综合0。、45。、90。和135。4个方向的梯度图，形成新的包含所有潜在骨架点的梯度图．通过预设的阈值消除大部分非骨架点；利用轮廓法、拓扑细化得到“细”中脊线．最后，利用“细”中脊线构建最短路径算法所需的邻接矩阵，大大地减少骨架提取算法的运行时间．关键词：距离变换；骨

2、架提取；梯度；关键点中图分类号：TP391文献标志码：A文章编号：0438—0479(2014)02—0201—05骨架的概念最早是由Blum在1967年提出的，当距离变换，然后利用一阶微分形象化的定义，在行和时他称骨架为“中轴”(medialaxis)[1]，Blum还分别给列方向上各自构建卜1，O。个1简单防行一『的3×3算子(如图1所出了2种骨架典型定义口]．二维图像的骨架提取方法示)，计算图像的梯度．向大体可分为4大类：1O。1r方1)基于拓扑和几何分析的方法；2)细化的方法；一向3)基于距离场的方法；4)基于广义势场的方法．这些]●J算方法提取的结果依然不理想，主要表现在骨架的

3、不稳子定性和骨架的连通性方面，Bai等【3引入边界离散曲线演化(discretecurveevolution)在保证骨架连通性b图1自定义的行方向和列方向上的算子的前提下，剪除对视觉不重要的骨架分枝；GollandFig．1Custo一moperatorsintherOWandcolumn～一一一方一一一等]利用物体模型的拓扑先验知识，提出用固定拓扑111可骨架(fixedtopologyskeleton)来减少骨架的冗余分如图2(C)O可知O，O距离变换(DT)的梯度图(1DT1)突出显示了图2(方b)中灰度值变化比较显著枝，消除骨架的不稳定性．Choi等[5]引入尺度因子，提像素点(

4、图2(c)中前0景点中黑色的部分)．实际这些像出距离场内基于连续准则的骨架提取算法，在一定程算素点的集合已经组成了原人子体图的中脊线．由于梯度度上解决了骨架的连通性问题；丁颐等r6]提出一种基化的结果也突出模型轮廓边缘的像素点，很难用阈值于种子生长的方法来连接断裂的骨架．来消除非脊点的影响；即使消除这些影响，提取出的本文引入刘俊涛等[7]提出的梯度最短路径的算法，骨架也难以保证单像素性和连通性．因此单纯依靠梯得到连通的、准确的物体模型骨架，并在此基础上提出度图来获取模型的骨架不能满足要求．基于梯度的优化方法，大大地减少了程序运行的时间．1基于距离变换的梯度最短路径算法1．1图像梯度本文利

5、用欧氏距离变换对二值化的人体图进行(a)二值化人体图(b)距离变换图(c)梯度图(d)局部极大值点图2二值化人体、距离变换、梯度和局部极大值点示意图Fig．2Thebinaryimageofhumanbody，theimageof收稿日期：2013—06—26distancetransformation，thegradsimage，基金项目：福建省高校产学合作重大项目(2012H6024)thelocalmaximumpointsimage*通信作者：chyang@xmu．edu．cn厦门大学学报(自然科学版)1．2关键点找到一种方法，在保证最终骨架效果的前提下，减少前景点的数量，降低邻

6、接矩阵的大小，从而提高算法设声是物体A内的任意一个像素点(或体素点)，运行效率．表示点的距离变换值，s是点P邻域点组成的集合．由1．1中的图像的梯度可知，对图像求梯度能突对任意的像素点(或体素点)，都有DT(q)≤DT(p)，则出图像的边缘．针对距离变换图，能突出潜在骨架点．称P为物体A的距离变换局部极大值点_7]．根据梯度的这一特性，可以对距离图求多个方向的梯本文是基于8邻域搜索得到的距离变换局部极度，找出所有潜在的骨架点，以达到减少搜索点的数值点．量．这种方法特别在细节较多的情况时，更能起到好的观察图2(b)发现，潜在骨架点的距离变换值应该效果．比邻域的距离值大．因此通过寻找距离图中

7、的局部极根据实际效果和时间开销的考虑，本文只从0。、大值点，可以得到潜在的骨架点．如图2(d)所示，粗点45。、9O。和135。4个方向求距离图的梯度．然后结合4表示距离变换图的局部极大值点，而且可以看到，局个方向的梯度图，取每个梯度图对应位置灰度值最大部极大值点全部落在梯度图的脊线上．的值作为当前像素点灰度值，形成新的梯度图．由于最短路径算法是按照梯度方向连接每个骨对比图3和图2(d)容易发现，图3包括了所有潜架点，局部极大值点必