南昌航空大学科技学院学士学位论文
3 骨架树描述及有关识别算法研究
3.1骨架树的基本概念
图像识别是计算机视觉的重要组成部分，图像的识别过程就是将目标图像的描述与模型库中模型的描述进行相似性度量，通过数值化的差值决定匹配结果的过程。图像识别系统中用于匹配的方法很多，它主要由图像描述的方法来决定。因此骨架的描述是骨架应用中的重点和难点问题之一。
从国内外的研究方面来看，大部分的侧重点是基于图的相似性匹配。这些方法通过人为的指定骨架间的对应位置，评估骨架枝的变形程度，从而得到骨架枝的相似程度。过多的人为因素，使得这类方法只能成为一种研究性的探索活动，无法真正应用到实际的机器识别活动中。
论文对于骨架描述问题进行了较为全面的研究，在有效分析了相关的描述里。第一种是基于不变矩的骨架描述，第二种是基于骨架树的描述方式，利用树的金字塔式结构特点组织骨架的拓扑、形状信息。基于几何特征的树结构匹配方法用于图像描述时，物体几何特征尤其是基本的拓扑特征表达效果突出明显，并且简单容易操作，在识别系统的应用中有着得天独厚的优势。因此我们对此进行了进一步的研究，在宋婷骨架树[33]研究的基础上改进了形状相似性度量方法,使得拓扑相似性度量和形状相似性度量实现有效结合,建立起一个由上到下、由粗到精的图像相似度匹配度量策略。
3.2骨架树模型的建立
骨架表征了物体的拓扑特性和形状特性，形状特性描述物体的轮廓形状，拓扑特性可认为是物体各部分间的连接关系。我们将骨架的拓扑特性映射到一个树状结构中，称之为“骨架树”。
为了建立骨架树，将骨架上的点分为三类：分叉点、端点和连接点。仅有一个邻接点的骨架点称为端点；有两个以上邻接点的骨架点称为分叉点；骨架上除分支点和端点外的点称为连接点。如果两个骨架点之间仅含有连接点则称这两个点是直接相连的。直接相连的两个骨架点之间的所有连接点的集合称为骨架枝。
对于大部分仿射状物体，我们把最大内切圆半径最大并且靠近物体重心的骨架点作为根节点。这样，根节点尽量位于物体的中心且代表了最重要的形状信息。确定了
18
南昌航空大学科技学院学士学位论文
根节点后，把与根节点直接相连分叉点或端点作为根节点的子节点。之后，对每个子节点用同样的方法找到各自的子节点，直到骨架上所有的分叉点和端点都在骨架树中。此时，骨架就转化为一个骨架树(骨架有环的情况参考相关文献[33])。骨架树的层次和节点间的连接关系反映了骨架的拓扑特性，对骨架树的匹配计算可以实现物体拓扑相似性的度量。此外,骨架枝代表了物体某个部分的形状信息，在骨架提取中计算出骨架点的特征信息（如骨架点的分支数、最大半径等）。使骨架树的节点包含形状的信息，还可以进行物体形状相似性的度量。
3.3 骨架树形状描述及有关识别算法
在一般二维物体的匹配中，只要拓扑骨架的提取足够精确，基于骨架树的拓扑相似性度量已能对大部分的二维物体进行有效的拓扑分类。但对于拓扑相同而形状不同的物体，由拓扑匹配算法所得的拓扑距离均为零，这说明仅仅对其进行拓扑匹配还无法区分这些物体，还需要进一步的形状匹配加以区分。
对于那些形状特征较为复杂的物体，骨架的小分支数较多，如果仅仅考虑其拓扑信息，有时会给匹配结果带来偏差。为了对物体进行更为精确的匹配，要求在骨架匹配中既抓住其最主要的拓扑特征也要考虑其形状的信息，不仅对其拓扑相似性进行度量，还要对其形状相似形进行度量。
3.3.1形状特征描述
对于二维图像，物体的形状特征一般包括物体的面积、长短、边界弯曲程度，骨架是骨架枝的集合，骨架枝包含着物体中轴的位置和最大圆半径，相当于代表着物体的面积、长短、弯曲程度等形状信息，所以骨架基本上可以表征物体绝大部分的形状特征。
这样可以利用骨架枝匹配距离度量骨架枝对应的性状的相似程度。为了能够计算骨架枝间的匹配距离，消除尺度变换对形状匹配结果的影响，需要对骨架枝进行归一化处理。下面介绍详细的方法：
设一骨架枝为v=(x,y,r)，x、y为该骨架枝上点的坐标，r是该x、y点对应的最大内切圆半径。归一化的基本思想是通过骨架枝坐标平移、旋转、拉伸等操作将骨架枝曲线的两个端点的连线变换到x轴正向上，其起点置于原点，终点置于点(l，0)
19
南昌航空大学科技学院学士学位论文
处。通过这些操作，将骨架枝化为以同一坐标为参数的形式，从而方便在相同的坐标区间和参数下对两个骨架枝进行比较，通过拉伸系数来度量骨架枝曲线在长度上的差异。同时，对半径的归一化可以消除尺度变换对匹配结果的影响，使得形状相似度计算忽略缩放的因素。
3.3.2 基于拓扑和形状相似度结合的识别算法
在形状匹配中，两个骨架枝的匹配距离表示了骨架枝的近似程度，也即是各自代表的形状间的相似性。距离越小则表明两个形状间越相似。在两个骨架的骨架枝之间建立最佳匹配关系，则骨架的形状匹配距离定义为建立最佳匹配关系的骨架枝的匹配距离之和。如果在建立最佳匹配关系时，考虑的是拓扑相似性的最佳匹配结果，则可以建立基于拓扑和形状相似度结合的最佳匹配结果，有效度量物体间的相似性。
3.4 结论
本部分在宋婷骨架树研究的基础上重新整理分析了相关内容，结合本课题的研究结果给出了骨架树模型的建立规则和过程，将物体的骨架映射为可以很好的反映骨架拓扑和形状信息的骨架树。在度量方法上做了很大的修正，不但在物体的拓扑相似性度量和形状相似性度量中简化了相关计算量，而且将二者的度量方法有机的结合起来，符合了实际事物的测量规律，提高了识别的可靠性。
在骨架树建立方面，给出了骨架树建立的方法和过程。对于建立过程常见的一些问题，作了一些说明。例如：对于拓扑较为复杂的物体，可以建立多尺度骨架树：第一级骨架树滤除大部分的细节，保持同时最主要的拓扑结构；下一级的骨架树都是在上一级的骨架树上增加子节点。骨架根节点的选取是骨架树建立的基础关键部分，本部分通过对骨架收缩各种情况的讨论，建立了一套合理的根节点选取准则，保证了多尺度匹配结果的准确性，对于复杂物体的相似性度量必将起到很大的促进作用，提高识别的正确率。
20
南昌航空大学科技学院学士学位论文
4 基于MATLAB的实现步骤及分析
4.1 MATLAB图像分析方法简介
MATLAB具有强大的图像处理功能，提供了简便的函数调用来实现许多经典的图像处理方法。MATLAB的图像处理工具包是由一系列支持图像处理操作的函数组成的，所支持的图像处理操作有：几何操作区域操作和块操作；线性滤波和滤波器设计;变换(DCT变换)；图像分析和增强；二值图像操作等。图像处理工具包的函数，按功能可以分为以下几类：图像显示，图像文件输入与输出;几何操作；像素值统计;图像分析与增强；图像滤波；性二维滤波器设计；图像变换;领域和块操作；二值图像操作;颜色映射和颜色空间转换；图像类型和类型转换；工具包参数获取和设置等。与其他工具包一样,用户还可以根据需要书写自己的函数，以满足特定的需要，也可以将这个工具包和信号处理工具包或小波工具包等其他工具包联合起来使用。 不仅是图像的边缘检测,在变换域处理、图像增强、数学形态学处理等方面的研究中,用MATLAB可大大提高实验效率,快速实现研究中的新构想。
4.2算法实现步骤流程图
基于MATLAB的骨架提取技术实现流程重点在于调用函数提取骨架，细化的实质是将一个曲线形物体化为一条单象素宽的线，从而图像化显示出拓扑性质，从而得到物体的主骨架体，其具体流程图如下所示。
21
南昌航空大学科技学院学士学位论文
开始
读入原始图像 图像预处理 图像转换为二值化图像 得到骨架点 得到主骨架
结束
（a）形态学骨架化算法流程图
开始 读入原始图像 获取图像行宽列高（象素值）及每字节象素值 将原始图像送入工作区 得到骨架点 输出结果 得到主骨架 结束 （b）细化算法流程图
22