基于欧氏距离及向量内积的骨架提取算法

戴凌震，荣 晔，史有群

基于欧氏距离及向量内积的骨架提取算法

戴凌震，荣 晔，史有群

对骨架算法进行研究，提出一种骨架提取算法。通过对图像内部像素点进行距离变换得到其最近边界点的位置，将内部像素点到最近边界点的向量定义为边界向量，根据物体内部相邻边界向量的方向，计算每个像素点的内积值和其8邻域的最小内积值，得到的最小内积点，以确定的阈值从最小内积点中选取骨架种子点，再对骨架种子点进行处理，得到连通的骨架。试验证明这种算法能保证骨架具的完整性和连通性，正确反映物体的拓扑结构。

骨架；边界向量；内积；距离变换

0 引言

描述物体形状的重要工具是骨架，它包含物体的拓扑结构和形状特征，是描述物体形状的方式，由骨架所体现的物体轮廓和区域信息，可以方便地进行物体的特征匹配，在计算机图形学、图像检索、图像处理、模式识别和生物医学等领域得到了广泛的应用，物体骨架的概念最早由 Blum 提出[1]。

近年来，骨架提取算法一直是图像处理研究的一个热门课题，许多学者都提出了不同的骨架算法。这些算法大致分为 3 类。第一类是细化和边界扩展算法，文献[2]综述了各种细化算法的实现及应用。火烧模型[3]和波形推进面[4]方法是最常用的细化算法。第二类是基于区域的中轴算法。包括Voronoi图及其应用[5]，数学形态学[6]和最大圆盘[7]等。细化算法和中轴算法都对边界噪声敏感，微小的边界噪声干扰会出现较多的骨架分支，需要对骨架进行剪枝处理，以简化骨架的拓扑结构。第三类是基于距离变换的算法[8]，通过对象内部像素点到边界的距离图确定对象的脊线。这种方法对于一些狭长的对象形状无法得到清晰的脊线，骨架的连通性通常难以保证。

基于欧氏距离和向量内积的骨架提取算法。首先计算图像内部每一个像素点到对应边界点的欧式距离，由欧氏距离变换的结果求出相应最近边界点的位置，定义将从内部像素点指向最近边界点的向量定义为边界向量，根据相邻边界向量的方向，计算每个像素点的内积值，并且求出其8邻域的最小内积值，由设定的内积阈值在最小内积值中选取骨架种子点，通过对骨架种子点的向外延伸和向内连接，将骨架连通起来。得到的骨架完整并且连通，能正确描述物体的拓扑结构。

1.基本定义

文中物体定义为闭合曲线所包围的部分，物体的边界即为闭合曲线。物体的内部像素点是边界内部的像素，边界上的像素称为物体的边界点。距离变换是图像内部像素点到边界点的最近距离。

通过距离变换确定物体内部每一个像素点的最近边界点。边界向量是这样一段有向线段，它的起始于内部像素点、终止于与始于内部像素点最近的边界点，如图1中的所示：

图1 图像点和边界向量

在图1（a）中， L1， L2分别是两条平行边界线上的边界点。 L1L2线段上所有的点都是内部像素点。若 M 为L1L2线段的中点，则线段上每个像素点的边界向量方向一致，指向上像素点的边界向量一致，指向。在M点附近像素点的边界向量方向相反。中点M的位置可以根据边界向量方向变化确定。

边界向量的变化可以用相邻像素点的边界向量夹角φ表示，如图1（b）中的点和点。二维边界向量的夹角大小定义如公式（1）：

最小内积值 A由式（2）确定如公式（2）：

根据边界向量和最小内积点的定义，物体的中点两边的边界向量方向不同，中点边界和其邻近点的边界向量具有最大的向量夹角和最小的内积值，因此中点必为最小内积点，物体的骨架点就存在于最小内积点中。通过计算物体内部像素的内积值，可以绘制出物体的内积值图。图（2）是 MPEG7图形数据库中鹿的最小内积值图，图中线段的颜色越深，表示其内积值越小，颜色最深的点就是最小内积点。

图2 MPEG7 图形数据库中鹿的最小内积值图

2.基于内积骨架提取算法

图2的结果表明，每个最小内积点到对应边界的距离最远，因此，物体的骨架点包含在这些最小内积点中。但是，这些最小内积点不能直接作为物体的骨架，因为它们包含了过多的冗余分支。为了得到物体的主干骨架结构和良好的骨架连通性，本文提出一种基于内积的骨架提取算法。

首先，对给定的二值图像进行距离变换，计算每个内部像素点到边界的最近距离和最近边界点的位置，根据得到的数据计算每个内部像素点的边界向量。其次，对内部像素点边界向量及相邻的八邻域点边界向量进行内积计算，取出具有最小内积值的最小内积点及与之对应的最小配对点。根据最小内积值画出最小内积值图，在最小内积值图中选择骨架种子点。然后，对骨架种子点进行向外延伸和向内连接处理，最后，输出完整的骨架图。

其中骨架种子点选择和骨架的向外延伸和向内连接处理是算法的核心，下面将详细讨论。

2.1 骨架种子点选择

骨架种子点是最小内积值图中具有较高可信度的内部像素点，它要满足最小内积值条件，也就是说这个点必须为最小内积点。根据最大圆盘定理，以最小内积点为圆心的最大内切圆与边界的切点就是最小内积点的最近边界点，且有边界向量垂直边界切线的关系。如果两条边界切线平行，如图1（a）所示，那么边界向量夹角为π，两个边界切点连线的中点必定是骨架点。如果边界切线不平行，如图3 所示：

图3 边界向量夹角和边界切线夹角的关系

综上所述在最小内积值图中,满足最小内积值小于 0、边界向量夹角大于 °90 的像素点可能是骨架种子点。由此选定内积阈值等于0，最小内积值小于 0的最小内积点为骨架种子点。

在数字图像中斜边界线由于存在锯齿现象引起边界凸起部分，这些凸起部分的内积值也会满足骨架种子点的条件，造成多余骨架点的存在。为了避免虚假骨架点的干扰，对骨架种子点的选择加一个限定条件：骨架点与边界的距离必须大于一个像素。

由内积阈值确定的骨架种子点，可能是一些孤立的点，也可能组成连续的骨架线段，对图2的最小内积值图进行内积阈值处理后，得到的骨架种子点图如图4所示：

图4 MPEG7 图形数据库中鹿的骨架种子点图

出现了骨架断裂现象，需要辅以适当的方式连接这些种子点，以得到连通的骨架。

2.2 骨架向外延伸过程

要正确描述物体的形状，物体的骨架必须包含主骨架和骨架分支。物体的中轴表现物体主干部分的拓扑结构，是主骨架，在图2中就是鹿的身体部分的骨架。骨架分支表示的是物体的凸起部分，它们是主骨架延伸的部分，如图2中鹿的鹿角、四肢部分。在最小内积值图中，在主骨架种子的附近沿着其凸起部分存在另一个骨架种子，则在这两个种子点之间必定存在连通这两点、且内积值大于0的其他最小内积值点，如图4所示。这些点可能是骨架的部分分支，但是，不满足骨架种子点选择的原则，出现了骨架断裂现象，因此需要进行骨架向外延伸处理，将骨架分支延伸到凸起部分的终端。

为了实现骨架向外延伸，连接有效的骨架分支，需要给出骨架种子点和其最小配对点的最近边界点的位置、这些边界点在边界序列中的编号。通过边界序列编号，计算出每对点对应的边界长度。

沿着凸起部分连接骨架种子过程如图5所示：

图5 骨架向外延伸示意图

在图5中，设骨架种子点 A1和最小配对点A2对应的最近边界点的边界序列号分别为 a1 和 a2。另外一个骨架种子点 B1和最小配对点 B2对应的最近边界点的边界序列号分别为 b1 和 b2。骨架分支向外延伸（即向物体凸出部分延伸）时，如果在最小内积值图中能找到像 A1和 B1这样的两个骨架种子点，满足边界线段 b1b2 含在 a1 a2 边界线段中，且边界长度小于那么这两个骨架点之间内积值大于 0的最小内积点都可以表示为骨架点，由这些点来连通两个骨架种子。这个延伸处理可以得到物体凸起部分的骨架分支。

2.3 骨架内连接过程

经过以上两个骨架连通处理步骤，使得物体的所有骨架分支连接到主骨架上后，最后得到的连通的骨架结构如图6所示：

图6 MPEG7 图形数据库中鹿的骨架图

3.算法试验结果

用本文的算法对MPEG7图形数据库的所有样本进行了骨架提取试验，试验时，我们用本文的算法和文献[9]中的算法对 MPEG7 图形数据库中图形进行骨架提取，部分结果如图7所示：

图7 算法结果比较

在图7中，左边一列图像是本文算法的提取结果，右边一列是文献[9]算法的提取结果。文献[9]算法的提取结果虽然能很好地克服边界噪声对骨架的影响，但是也有物体局部特征遗漏现象，如图6-2(b)所示；或有冗余骨架分支存在现象，如图6-2(f)所示。试验结果表明用本文提出的算法提取物体的骨架结构，不仅能很好地保留物体的整体骨架结构，同时对物体的局部细节特征也能很好地描述。在表征物体的拓扑结构时，对于对象明显的视觉特征部分都有对应的骨架分支。

4 结论

本文研究了基于内积的物体骨架提取算法，距离变换求出物体中的像素点所对应的最近边界向量，再通过相邻边界向量的方向找出可能的骨架点位置，通过内积阈值确定骨架种子点，经过对骨架种子点的向外延伸和向内连接处理，得到连通的骨架。本文提出的算法具有简单有效的特点，通过本文算法提取的骨架不仅完整，而且连通性也得到保证，能够为后续图像处理提供物体的拓扑信息。

[1] Blum H., A Transformation for Extracting New Descriptors of Shape. Models for Perception of Speech and Visual Form[J], Cambridge: Data Sciences Laboratory, 1967, 45(18): 362-380.

[2] Lam L. and Lee S. W., Thinning Methodologies - a Comprehensive Survey[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14( 9): 869-885.

[3] Leymarie F. and Levine M. D., Simulating the Grassfire Transform Using an Active Contour Model[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(1): 56–75.

[4] Tang Y. Y. Skeletonization of Ribbon-like Shapes Based on a New Wavelet Function[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(9):1118–1133.

[5] Aurenhammer F.Voronoi Diagrams – A Survey of A Fundamental Geometric Data Structure[J], ACM Computing Surveys, 1991, 23(3): 345–405.

[6] Jang B. K. Analysis of Thinning Algorithms Using Mathematical Morphology[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990,12(6): 541-551.

[7] Ge Y. and Fitzpatrick J. M. On the Generation of Skeletons from Discrete Euclidean Distance Maps[J], IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 18(11): 1055-1066.

[8] Choi W. P. Lam K. M. and Siu W. C., Extraction of the Euclidean Skeleton Based on a Connectivity Criterion[J], Pattern Recognition, 2003,l(36): 721–729.

[9] Bai X. and Latecki L. J. Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution. [J]IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(3): 449-461.

A Euclidean Distance and Inner Production Based on Skeleton Extraction

Dai Lingzhen, Rong Ye, Shi Youqun
（School of Computer Science and Technology, Donghua University, Shanghai 201620, China）

In this paper, a skeleton calculation method is proposed. Distance transform is used to determine the nearest edge element for each pixel in a binary image. A vector from each pixel that stops at the nearest edge element is defined as edge vector. An inner-product for a pixel is calculated as the minimal value of the inner-products of edge vectors of the pixel and its 8 neighbor pixels. Seeds of the skeleton are determined by a threshold for the inner-product value. A well connected skeleton is obtained by growing calculation. It is demonstrated that the proposed algorithm produces a integrated and well connected skeleton that represents object’s topology.

Skeleton; Edge Vector; Inner Product; Distance Transform

TP 391.41

A

1007-757X(2014)02-0041-04

2013.11.10)

戴凌震（1987-）男，江苏太仓人，东华大学计算机科学与技术学院，硕士研究生，研究方向：计算机图像处理，上海，201620荣 晔（1985-）男，上海人，东华大学计算机科学与技术学院，硕士研究生，研究方向：计算机图像处理，上海，201620史有群（1985-）男，东华大学计算机科学与技术学院，教授，研究方向：计算机图像处理，上海，201620