南昌航空大学科技学院学士学位论文
2 物体骨架提取方法研究
2.1 骨架提取的基本概念
2.1.1物体骨架与物体边界/轮廓的关系
骨架提取方法属于骨架应用于图像处理领域的基础研究阶段，领先于其它相关研究，该部分突破性研究成果对此领域的发展具有巨大的作用。
骨架是基于物体形状特征的简化对象描述方式，得到理想的物体骨架具有重要的意义。简洁准确的骨架能够突出物体的整体结构，反映物体的边界形状，其二简洁的特征,简化了其后期的描述和度量的困难,为物体的形状特征匹配实现带来方便。再者，骨架提取研究一个重要的目标是将图像提炼成反映其本质的简化表示，可以在保持重要的拓扑和几何结构特征的情况下清除这样那样因素引起的轮廓失真影响，在识别技术上可以引导出一种终点、结点和各子部分连接关系的特征描述方式，从而实现一种应用模糊理论于图像识别领域的智能识别算法。因此是图像识别领域研究的重点，是计算机视觉、人工智能、图像处理等领域的关键技术和研究的热点之一。 在数字图像处理领域，边界与轮廓没有本质区别，是图像的一种特征。它是由图像的部分边缘点连接起来的集合图形，用来表示图像中某一目标的形状。
物体骨架是物体边界或轮廓的一种简化形状表示方式，可以充分描述物体的形状和实现物体的识别。
骨架作为物体形状的一种表示方式，与采用轮廓描述形状相比，拥有许多优点。譬如，骨架可以表述出物体的整体结构特征，很多物体仅仅从结构上就可以很容易的区分，这点基于轮廓的形状描述是不能清晰表达的。骨架可以通过最大圆半径和骨架枝信息关联物体的轮廓形状特征，很容易的实现物体形状的保存和重建。因为骨架能够描述物体的整体特征，这使得骨架可以处理那些轮廓不准确的物体的识别问题。另外，骨架可以描述一些结构复杂的物体。如物体内部含有空洞等形状的;这些基于形状的轮廓描述是根本不能解决的。其它的优点诸如图像压缩比例大,可以实现多尺度选择等非常多，这里不再一一赘述。
9
南昌航空大学科技学院学士学位论文
2.1.2提取物体骨架的基本要求
研究者普遍认可的提取骨架的标准有五个：其一，提取骨架的连通性问题；其二，提取骨架枝的单像素问题；其三，提取骨架逼近物体的“中轴”问题；其四，边界噪声对物体骨架的影响问题；其五，提取骨架方法的效率的问题。
2.2 经典的物体骨架提取算法
以上诸多的优点，引起学者广泛的研究。人们己经提出的骨架提取方法，大致分为两类：一类处理的对象是离散域中的物体模型(如位图等)。通过对像素的操作得到骨架，但结果不可避免的受到离散化对精度的影响，此类方法得到的骨架一般用于图形的匹配和相似性度量；另一类处理基于连续域模型的对象，如多边形模型，使用严格的数学方法求解骨架的数值解，结果精度高。但此类方法适用范围窄，对于复杂三维物体，计算过程十分复杂，难以保证其稳定性。此类方法往往用于几何建模和物体重建。
本文研究的范围是离散域图像识别。在离散域下，提取骨架的方法大致分为细化骨架提取算法、距离变换骨架提取算法、Voronoi图骨架化算法、偏微分方程骨架化算法以及形态学骨架提取算法五类
2.2.1细化骨架提取算法
拓扑细化的方法在解决细节性较多、形状多为线状长条状等这些规则性强的结构的物体形状方面效果较好，例如电路图、字体，医学图像等。如图2-1(a)所示，细化能准确提取汉字的骨架。算法的中心思想是在保持拓扑结构不变性的条件约束下，不断地剥离表层的像素，直到最后剩余的骨架。这类方法通过制定大量的约束条件，判断像素的去留问，往往执行效率较低。此类方法得到的骨架可保证连通性和单像素性，但对边界噪声非常敏感，不能得到简化的整体形状重要的的拓扑结构，容易产生不必要的分支，且造成骨架点的位置不准确。如图2-1(b)所示，边界的小噪声产生了很多多余的骨架枝，并且骨架的位置不是准确地靠近物体的中心。
10
南昌航空大学科技学院学士学位论文
(a) 汉字细化 (b) 鱼的细化结果
图2-1 细化骨架
文献[17]提出了一种边缘点删除和内点保留细化方法相结合的新思想，即首先保留内点及图像中绝对不能被删除的特殊点(如交叉点,拐角点等)；其次，删除多余的像素点；最后，去除多余枝线。实验结果表明，该算法在细化的同时很好的保持了原图像的连通性，所得的骨架图像对称性好且为单像素宽。也一定程度改善了较多多余分支的问题。在三维情况下，细化方法受到了限制，如何消除细化结果中带面的情况成为研究的难点。
2.2.2距离变换骨架提取算法
距离变换的方法，如最大圆法，最大正方形法等，在解决整体性比较好。细节性不多的物体形状方面效果较好，比如人体轮廓、大型的动物轮廓、整体性较好的汽车等轮廓。算法首先对图像进行距离变换，使用不同的距离标准如欧氏距离、棋盘距离、街区距离等可产生不同的距离分布；然后寻找距离值梯度脊线，即局部距离极值,也是距离梯度发生突变的点来形成骨架，此类方法最大的缺陷是在离散域中，难以保证骨架的连通性。这方面文献集中解决的就是在欧几里德距离图的基础上，增加连通判决条件或连通方法使得得到连通的骨架。
文献[18,19]对传统的距离变换的方法进行改进，提出了一种新的算法。算法保证了骨架的连通性及单像素性。算法复杂度与文献[7]相比，减少了很大的运算量。算法的主要思想是选择一个骨架种子点，然后以单像素宽度生长出其余的骨架点，算法中可以给定权值控制生长精度，实现骨架的多尺度控制。这样算法提取的骨架保证了骨架的单像素性和连通性，同时该算法也具有良好的抗边界噪声鲁棒性。文献提出的算法分三步:
1)对二值图作距离变换(这里采用欧氏距离变换)，得到图像每一点距离场值和距
11
南昌航空大学科技学院学士学位论文
其最近的边界点坐标。选择距离场值最大的点作为种子点。
2)通过离散曲线演化把物体边界分成了很多曲线段，分别加上离散演化标记对曲线段加以区别。
3)以骨架种子点为起点，以单像素方式生长出其它骨架点。这个过程是不断对骨架点的八邻域像素点做判断，判断量是当前判断点的距离场值、距其最近的边界点坐标(最大圆边界切点)和边界曲线标一记，从而一点点得出整个骨架图。例如，假设点P是前沿骨架点，Pi(其中i=l,2,,,8)为P点的八邻域象素点。当Pi中至少有一个点和点P满足公式(1)，并且这两点的最近边界点的离散演化标记不同，那么Pi点就是一个骨架点。
这里r1.r2为p,pi的最大圆半径,(x1,y1),(x2,y2)为p,pi的坐标,w为骨架像素宽度。证明见文献〔18]。
从这个过程中不难看出,按照这种算法得到的骨架确实可以保证骨架的单像素、连通性和中轴性。加上离散曲线演化条件的控制，减弱了边界噪声的影响，消除造成信息冗余的骨架枝，保留视觉上重要的骨架枝，保证物体的拓扑结构不变形。
2.2.3 Voronoi图骨架化算法
Voronoi图的方法是基于采样点的离散方法通过多面体表面侯选点集的Voronoi图计算中轴，通常结果是中轴的近似。当所有相邻关系被揭示后，Sheepy等人重新定义了采样点，由此，精确骨架也是可以构建的。然而，算法整体的复杂性难以预料。通过计算多面体表面采样点的Voronoi图来求取中轴，通常只是中轴的近似值。随着精度的提高，算法的复杂度急剧增加，且Voronoi图是中轴变换的包集，如何确定其非中轴变换的部分也是较复杂的问题。
2.2.4偏微分方程骨架化算法
偏微分方程的骨架化方法往往要结合距离场，通过初始曲线在距离场下外力和内力的共同作用下移动到骨架的位置，因此该方法结果精度高、抗噪性能好，不足在于计算开销大，难以处理拓扑结构复杂的三维物体，甚至需要一定的先验知识来求解。
(2?1)
12