基于MATLAB的骨架提取算法的研究实现

毕业设计（论文）

系 别 信息工程系

专业名称 通信工程

班级学号 098204232

学生姓名 俞浩然

指导教师 欧巧凤

二O一三年五月

毕业设计（论文）任务书

I、毕业设计(论文)题目：

基于MATLAB的骨架提取算法的研究实现

II、毕 业设计(论文)使用的原始资料(数据)及设计技术要求：

学习数字图像处理技术，深入研究中轴变换的各种算法原理，采用MATLAB编程， 完成中轴变换，要求算法效率较高，且能较好的抑制噪声。

具体要求如下：

1﹑充分了解数字图像处理原理

2、熟悉MATLAB开发环境，图像转换、骨架提取等相关算法 3、采用Matlab实现图像二值化和中轴变换 3、比较各种算法的处理效果；并进行算法性能分析

III、毕 业设计(论文)工作内容及完成时间：

第1周-第3周： 查找资料，翻译英文文献，撰写开题报告。

第4周-第8周： 程序流程框图编制、源程序设计，系统软件设计及调试。 第9周-第13周： 实验数据分析。

第14周-第16周： 撰写毕业论文，准备答辩。

Ⅳ 、主 要参考资料：

[1]. [美]恩格尔 W K. Digital Signal Processing Using MATLAB [M]. 西安:西安交 通大学出版社，2002

[2]. [美] Nakamura S. Numerical Analysis and Graphic Visualization with MATLAB(Second Edition) [M].北京:电子工业出版社，2002

[3]. [美]冈萨雷斯. 数字图像处理（MATLAB版）[M]. 北京：电子工业出版社，2005

[4]. [美]冈萨雷斯. 数字图像处理（第二版）[M]. 北京：电子工业出版社，2007 2007

[5]. 张化光,刘鑫蕊,孙秋野.MATLAB/SIMULINK实用教程[M].北京:人民邮电出版社, 2011

[6].秦筱威一种有效的骨架毛刺去除算法[J].华中科技大学学报,2004,(12): 28-31

[7]. 杨承磊, 孟祥旭等. 带状图像交叉区域的骨架求解算法[J]. 计算机辅助设计 与图形学学报, 2000, (9): 677-681.

信息工程 系 通信工程 专业类 0982042 班

学生（签名）：

填写日期： 自 2013 年 2 月 21 日至 2013 年 5 月 28 日

指导教师（签名）：

助理指导教师(并指出所负责的部分)：

通信工程 系主任（签名）

学士学位论文原创性声明

本人声明，所呈交的论文是本人在导师的指导下独立完成的研究成果。除了文中特别加以标注引用的内容外，本论文不包含法律意义上已属于他人的任何形式的研究成果,也不包含本人已用于其他学位申请的论文或成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式表明。本人完全意识到本声明的法律后果由本人承担。

作者签名： 日期：

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权南昌航空大学科技学院可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

作者签名： 日期：

导师签名： 日期：

基于MATLAB的骨架提取算法的研究实现

学生姓名：俞浩然 班级：0982042

指导老师：欧巧凤

摘要：骨架作为二维、三维数据在计算机辅助设计、数字博物馆、医学图像处理、科学数据可视化、计算机图形学、虚拟现实和游戏等领域的迅猛发展，使之成为继图像、音频、视频以来又一种重要的多媒体数据形式。其中最常用的一种简化表示方式就是使用一维曲线，一般称为骨架。利用物体的骨架来描述对象是一种既能强调物体的结构特征，也能提高内存使用率与数据压缩率的好方法。

在本文首先详尽讨论了骨架的各种定义及骨架提取算法的研究现状，通过对不同类别的骨架算法的分析比较，得出不同类别的骨架算法的优缺点。接下来研究了生成三维体素模型的问题，分析比较现有体素化方法的优缺点，重点采用最小包围盒改进了基于欧式距离测度网格模型的体素化算法，在Matlab平台上实现其加速算法并集成到三维模型骨架提取可视化实验平台，实验证实了该算法的高效性，满足课题的需要。最后系统地分析了我们需要开发的模型骨架算法，重点探讨并实现了几种代表性的骨架提取算法，给出实验结果比较各自的特点，分析并提出改进建议。 关键词：中轴，线性骨架，骨架算法

指导老师签名：

Study on skeleton extraction algorithm realization based on

MATLAB

Student name : Yu Haoran Class: 0982042

Supervisor : Ou Qiaofeng

Abstract：Prevailing in the world of Computer-Aided Design, digital museum, medical imaging, scientific visualization, virtual reality, computer graphics and gaming environment, Three-dimensional (3D) data become more and more a common feature of nowadays multimedia. The line-like representation is a one-dimensional (ID) abstraction of a three-dimensional (3D) object, consisting of a set of curves embedded in 3D space. This line-like representation of a 3D object is also known as the centerline or the curve-skeleton. As a reduced representation, the curve-skeleton capture the essential shape (topology and geometry) of the underlying 3D object in an easy to understand and very compact form, also increase the efficiency of memory usefulness and compress ratio. In this paper firstly discussed the research status of all kinds of definitions and skeleton extraction algorithm framework, through analysis and comparison of different categories of skeleton algorithm, advantages and disadvantages of the different categories of skeleton algorithm. The next generation of 3D voxel model, compares the advantage and disadvantage of existing voxelization method, focusing on the use of the minimum bounding box of Euclidean distance measure grid model voxelization algorithm based on improved, the acceleration algorithm and integrated into the 3D model visualization platform skeleton extraction on the Matlab platform, the experiment proved efficiency of the algorithm, to meet the need of task. Finally, systematic analysis of the model skeleton algorithm we need to develop, mainly discusses and implements several representative skeleton extraction algorithm, the respective characteristics of comparative experimental results are given, analysis and improvement suggestions.

Keywords: medial axis curve-skeleton Skeleton algorithm

Signature of Supervisor :

目 录

1 绪论 .................................................. 1

1.1研究背景与意义 .................................................. 1

1.2国内外研究现状 .................................................. 2

1.2.1基于拓扑与几何分析的方法 ................................. 2

1.2.2拓扑细化的方法 ............................................. 4

1.2.3基于距离变换的方法 ........................................ 5

1.2.4 广义势场方法 ............................................. 6

1.2.5各种骨架化算法的比较 ....................................... 7

1.3 论文主要工作与内容安排 ......................................... 8

2 物体骨架提取方法研究 .................................. 9

2.1 骨架提取的基本概念 .............................................. 9

2.1.1物体骨架与物体边界/轮廓的关系 .............................. 9

2.1.2提取物体骨架的基本要求 .................................... 10

2.2 经典的物体骨架提取算法 ......................................... 10

2.2.1细化骨架提取算法 .......................................... 10

2.2.2距离变换骨架提取算法 ...................................... 11

2.2.3 Voronoi图骨架化算法 ...................................... 12

2.2.4偏微分方程骨架化算法 ...................................... 12

2.2.5形态学骨架提取算法 ........................................ 13

2.3当前骨架提取算法面临的重点和难点 ............................... 13

2.4构建物体视觉主骨架 ............................................. 14

2.4.1视觉主部分概念 ............................................ 15

2.4.2 提取视觉主骨架 ........................................... 15

2.5 结论 ........................................................... 17

3 骨架树描述及有关识别算法研究 ......................... 18

3.1骨架树的基本概念 ............................................... 18

3.2骨架树模型的建立 ............................................... 18

3.3 骨架树形状描述及有关识别算法 ................................... 19

3.3.1形状特征描述 .............................................. 19

3.3.2 基于拓扑和形状相似度结合的识别算法 ....................... 20

3.4 结论 ........................................................... 20

4 基于MATLAB的实现步骤及分析 .......................... 21

4.1 MATLAB图像分析方法简介 ........................................ 21

4.2算法实现步骤流程图 ............................................. 21

4.3 算法实现骨架提取 ............................................... 23

4.3.1 形态学骨架化算法实现骨架提取 ............................. 23

4.3.2 二值图像细化算法实现骨架提取 ............................. 24

4.4 图像对比分析 ................................................... 25

5 结论与展望 ........................................... 26

参考文献 ............................................... 27

致 谢 ................................................. 29

附录 ................................................... 30

1 绪论

1.1研究背景与意义

随着扫描技术和计算机图形学的发展以及计算机性能的提高，模型己成为继声音、图像和视频之后的第四种多媒体数据类型。对模型的使用与研究在娱乐、医学、机械工程、计算机仿真和虚拟现实，工业应用等领域得到了认间，日益发达的互联网技术为人们对三维模型的共享和处理提供 了条件，这些都导致对维模型应用需求的增长。但是三维模型的信息量很大，同时三维模型的描述方法多样，如点集合表示法、多边形网格表示法和体素表示法等，这也使得三维模型在许多应用中发生占用存储空间过大、运行计算负载过重 、达不到时计算的情形。所以需要一种"紧凑的 " 表示方式来尽可能完整，全面地表示描述三维模型的结构特征信息等。其中最常用一种简 化的表示方式就是使用一维曲线 ，一般称为中心线或者线性骨架。利用物体的骨架来捕述对象是一种既能强调物体的结构特征，也能提高内存使用率与数据压缩率的好方法。骨架作为计算机图形学、计算几何学、点集拓扑学和图论等跨学科专业的研究内容，有丰富的理论支撑和很多成熟的数学工具可以利用。自从Blum[1]的开创性研究以来 ，数十年来研究者们从不同的角度研究了骨架的各个侧面，并且将它应用到越来越广泛的领域之中。这些领悟几乎涉及到计算机视觉和图像理解领域的方方面面。

骨架是原始图形的一种压缩表示 ，与原始图形保持了相同 的拓扑结构， 并且存在于图形的对称轴上，能够同时反映图形的拓 扑与形状信息，减少原始 图形的冗余信息，是在二维或三维空间里描述物体基本拓扑的有力抽象化手段。三维模型的骨架是该物体的直观图或中心线的表示。应用中它可以代替原三维模型参与许多运算，从而大大减少计算开销，可广泛用于医学可视 化、模式识别、计算机动画等领域。近年来，随着体可视化技术的发展以及体图形学的出现，使得三维骨架提取成为了一个研究热点。

在过去的二十年里，科研工作者在三维骨架提取领域已经开发了很多的算法，并且新的算法也正在不断出现。2006年美国Rutgers大学的Cornea等人详尽综述了三维线性骨架提取的应用与研究，并在网站上公开了部分算法的源代码供大家使用。可以说这极大方便了研究者，但Cornea提供的源代码读取数据格式不统一，同时缺乏可视化显示，非常不便于重复使用。为避免重复使用，非常有必要充分利用各种已有算法，开发二维、三维骨架提取平台。

1.2国内外研究现状

骨架是表示物体的一种很自然的形式，三维模型的骨架可以看成是由物体中所有的最大内接球中心所在位置点构成。三维模型的骨架在计算机视觉、医学图像可视化、特征提取与表示、模型匹配跟踪等诸多领域有着广泛的应用。

骨架算法的研究工作已经开展了三十多年，其中二维图形的骨架算法研究比三维情况下要成熟许多。最初三维物体骨架提取算法使用人 工指定的方法。人工指定算法要求用户一张张地在切片上直接指定中心点，然后再将点连成线。这种方法耗时费力，己很少采用。当前的研究主要可以分为以下四类。第一类是基于拓扑与几何分析的方法，通过构造模型的Voronoi图或Reeb图来得到骨架；第二类是拓扑细化法(Topology Thinning) ，又称为模拟烧草模型算法，此类算法从边界开始，反复迭代地逐层剥离离散后的模型， 直 至剩下一维的骨架；第三类方法是基于距离场的方法 ，它们先生成关于模型的距离场，再提取距离场中的局部极值点，然后连接这些点，并作一些细化调整得到骨架；第四类是广义势场方法，假设模型的边界上聚集了均匀分部的同种电荷电源，采用牛顿静电力学模型建立立场，让种子点逐步移动到达力学平衡点，然后依据种子点的相邻关系连接这些平衡点得到骨架。下面分别详细介绍各类算法的研究情况。

1.2.1基于拓扑与几何分析的方法

基于拓扑与几何分析的方法又主要包括两方面 :Voronoi图和Reed图。

Voronoi图是计算几何领域里的一项重要工具。Voronoi 图的概念是俄国数学家G Voronoi 在 1908年提出 的，是计算几何学上非常著名的工具，被广泛的应用于各个行业。在二维平面M上给定一个包含 n个点的集合S {Pi M,1 i n}，与S关联的Voronoi图为覆盖整个平面 M 的一个凸多边形的集合VD {(Pi)|Pi S}， 其中：

v(Pi) {p|d(p,Pi) d(p,Pj),i j,1 i n,1 j n} （1-1），

v(pi)包含了 M 中所有到点pi的距离小子点集 S内任何其他点距离的空间区域。式

（1-1）给出点pi的Voronoi多边形，点集S的Voronoi多边形集合就构成了S

的Voronoi图。图1-1给出了平面内的一组点及由这组点集 生成的 Voronoi 图。这个概念也可以扩展到三维空间上，这样的Voronoi图就是Voronoi多面体的集合。

图1-1平面内的点集和其Voronoi图

骨架及Voronoi图都基于最短距离约束，Voronoi图的生成是一个由点到区域的扩张过程，骨架的提取是 一个区域到线的细化过程 ，可以以火的蔓延为例进行分析。假如在某一区域M中存在一点集，在t= O时点燃点集中的点，着火点以同样的速度向四周扩散，燃烧前沿相交时熄灭，燃烧区域对 M的分割就是 Voronoi分割。边界点具有特殊性，其燃烧前沿不能够完全相交，因此 Voronoi图边界的多边形是无限向外扩展的。同理假如对某一区域边界线上的所有点，在t= 0时点燃，火的前沿以相同的速度向内部扩散，燃烧前沿相遇时熄灭，熄灭火焰点的集合便是区域的骨架。

骨架实际上是物体内部相对于物体边界的最大内切圆的中心的集合，而内切圆的圆心至少与物体边界上的两个点具有相等的距离。同时，与物体边界点所关联的Voronoi图所生成的靠近物体中心的Voronoi边与 至少两个边界点具有相同的距离。因此，图形边界点集的 Voronoi图能够给出部分的骨架。不完备之处在于Voronoi图计算的是空间内到给定点集距离最小的区域，因而不区分图形内外部分，在遇到有凹点的图形时与精确骨架有差别，可以说物体的骨架点集是Voronoi图的子集。

Voronoi图方法只适合计算简单多面体的骨架，不适用于离散模型，同 时处理内部有空洞的物体也有困难。对于复杂的物体实体，理论上可以先用表面网格模型

表达，然后计算 Voronoi图，但是若原始物体表面太光滑，则表面多边形太小，Voronoi图的计算量将十分庞大，因此Voronoi图方法的适用范围目前还比较狭窄。此类方法也便于生成多尺度骨架描述，但是 需要剪枝 的过程，而且规则很复杂。对于边界噪声的影响，此类方法也表现得特别敏感，这一点对于识别系统是非常不利的。

另外一些方法基于Reeb图思想。该类算法首先在模型上定义一个连续函数 ，计算每个模型顶点的函数值，将具有同样函数值的顶点聚合成一个顶点，得到模型的骨架。

一般采用Reeb图进行骨架抽取的思路，都将计算对象放在模型的顶点上，而后根据顶点的函数值计算其所在面片落入的各个函数值区间，进行骨架创建。而黄坤武提出一种针对模型面片进行直接骨架抽取的算法框架，首先定义模型面片之间的距离计算方法，创建模型的对偶图，然后在该对偶图上应用Reeb图的计算思想，在对偶顶点上定义一个连续函数并计算每个顶点的函数值，最终根据计算得到的函数值以及顶点对应的面片之间的邻接关系创建模型的骨架。

1.2.2拓扑细化的方法

拓扑细化方法是一种受到广泛关注的算，这类方法模拟烧草模型的物理过程，由图像的边界开始向内演化，逐步搜索到中轴骨架的位置。基本思想是逐层均匀的剥掉图形的边界点，剩下最里层的不能在剥掉（否则会影响连通性）的部分就得到了图形的骨架。

这类算法的研究首先 开始于二维图像 ，后来又逐渐扩展到三维领域。这一类算 法的关键就是简单点 (Simple point)和端节点 (End point) 的判断。所谓简单点，就是那些被删除后不会改变图像拓扑结构的点。端节点也是一类简单点，但是对它的删除 可能会丢失一些物体末端信息，会造成过皮细化。为了保留物体形状有用的信息， 那些作为端节点的简单点就必须保留不变。这一类方法的过程实际上就是简单点的 判断与删除的过程。这个过程一直重复，直到没有点能够被删除，这样就产生了骨架，但是端节点在三维情况下的定义却不容易确定。根据对简单点的判断的不同方法，又可以分为基于模板的算法和基于边界的算法。

拓扑细化方法的优点就是能够保证所抽取的骨架的连通性，同时，容易平行实现，对于光滑的、规则的物体，是一种不错的细化选择。但是，它也存在着很多的缺点，比如会产生一些小突起，以及无关的枝桠。而且对于三维物体而言，

细化的过程比较复杂，从而需要给出大量的删除条件或者特殊的规则，以避免在细化过程中造成不连通的现象。而且，细化法只是考虑局部连通关系，无法对图形特征进行全局的把握，使它对噪声特别敏感，含有大量噪声的边界常常会导致许多点被误认为端节点。

1.2.3基于距离变换的方法

基于距离变换的方法是利用物体的连通性，对局部领域进行距离变换赋值，从而抽取出物体的骨架点。物体内的每一点的DT（Distance Transform）值被定义为这个点到边界点的最小距离。由于骨架点相对于物体的边界而言应当处于中心的位置，而从理论上讲 ，最接近于物体中心的点应该具有最大的 DT 值。因此，DT值就能为骨架点的确定提供有用的信息。

距离度量（Distance Metric）是衡量图像中两点间距离的方法，目前，有很多种距离规则可以用于计算距离变换值。例如两点 间的欧式距离就可以提供足够的信息来判断该点是否位于中心。但是在实际计算中，两点间的欧式距离为：

其中，和分别为两点的笛卡尔坐标，其计算代价是非常高的，如此精确的距离计算也是不必要的，在一些文献中，使用Manbattan距离或者Cbess-board距离来加快计算。根据体图形学的理论，在三维空间中，物体是以离散网格的形式采样的。因此可以用加权距离规则来近似欧式距离。这种规则被定义为 a-b-c 形式例，其中a为面相邻元之间的局部距离，b为边相邻元之间的局部距离，c 为点相邻之间的局部距离。

依据距离的参照据，提取骨架的距离场可分为两类：到源点的距离场，记为DFS（Distance Field from Source）,一般在模型表面上选取一个源点，然后计算模型表面上或内部的所有点到该源点的距离，得到的距离场即为DFS；到模型边界的距离场，记为DFB（Distance Field from Boundary），对于模型内部的某一点，计算该点到模型边界的最短距离，得到的距离场即为DFB。基于这两种距离场的骨架提取方法 分别称为DFS方法和DFB方法。距离场方法，一般需要先将模型离散为规则数据场的体素表达，再进行骨架提取的工作。

在这些方法中，它们大多使用 Dijkstra算法来构造距离场或者进行骨架节点的搜索。Dijkstra算法事先构造某特定权值来度量图中路径的长度，然后从图的某指

定源点出发，依据路径长度的递增次序，来产生到所有其它顶点的全局最短路径。于是，若把模型表面多边形的所有边和顶点看作一个连通图，多边形的边的欧式长度作为路径权值，那么运用 Dijkstra算法就可以在模型表面上建立DFS，若把DFB值看作是高度值，则模型的DFB就是一个高度位图，那么骨架分支就是该位图的“山脊线”。若构造某路径权值，使之随DFB值（高度值）单调递减，那么运用 Dijkstra算法得到的某两点间的最短路径，就是这两点间的“山脊线”，这样就得到了一条骨架分支。提取所有这样的分支，就可得到模型的完整骨架。

Gagvani提出一种基于距离变换的带参数控制的三维骨架提取方法。该方法比较每个点与其邻域点的距离变换值，满足一定局部最大条件的点被选为骨架点，再利用一个细化参数控 制骨架点的密度，并且可以由这些骨架点半自动地抽取出三维物体的中心线。

这种方法的优点是，能够由骨架点及其DT值重建出物体，而且它实现起来相对简单，能够抽取出不规则物体的骨架，使用面较广。另外基于距离变换的方法在骨架点的准确度上有明显的优势，且由此类方法求出的骨架具有完全重建原始图形的能力，并具备平移、旋转、比例变化的不变性。但是，用这种方法抽取出 的点集并不能保证得到一个连通的骨架。同时这类方法很难保证骨架的连通性，这将影响骨架拓扑特性的表达。此类方法也不保证骨架结果的单像素特性，这点与骨架定于是不符合的。

1.2.4 广义势场方法

广义势场方法假定物体的边缘上聚集了均匀分布的同种电荷，这些电荷在物体内部产生了一个稳定的电场。该方法首先选择物体边界上的凸点作为起始点，然后依照电场的方向移动到场强为0的地方。起始点的移动轨迹构成骨架的一个分支，最后连接所有分支得到骨架。广义势场方法利用了不同于距离变换的矢量场，取得了很好的结果。Ma等人提出过基于可见互斥力的骨架抽取算法，它应用了物理学上的互斥力的概念来计算模型上的平衡点，最终得到模型的骨架。Cornea等人对广义势场方法进行了改进，该方法将场强为0的点作为关键点，根据其文献所提出的力跟踪方法连接个个关键点，得到物体的核骨架，然后选择曲率较大的边界点继续生成骨架得到物体的层次骨架。

1.2.5各种骨架化算法的比较

在二维情况下，这些方法都能够保证所生成的骨架能很好地反映原模型的几何，拓扑特征。但对于三维模型，基于Voronoi图的方法很难保证骨架是一维的，且计算效率低，其他三类方法一般都能得到一维的线性骨架，对模型的每一个内部离散点，拓扑细化法需要迭代访问多次，所以相比于距离场方法，它效率较差。

拓扑细化类方法最大的优点是能保证优良的连通性能，即骨架结果保持与原始 图形相同的拓扑特征。拓扑特征是识别物体的关键特征，因此保留拓扑特征非常重要。但是细化算法大都需要进行迭代运算， 因此计算量相 当庞大。并且细化法得到的骨架结果位置不精确 。

基于距离变换的方法能够很好的解决细化法骨架位置不准确的问题，同时对运算量的要求也大大降低 ，并且可以通过设计各种参数降低对噪声的敏感度。此类方法的缺点在于不能保证骨架 的连通性和单像素性，其原因也是离散处理造成的 ，离散域内圆的定义和圆的包 含关系很难把握，并且有可能真实的骨架位置位于两离散点正中，于是两点皆被选为骨架点或丢失，破坏了单像素性和连通性。

广义势场方法不仅考虑骨架最近边界点的影响，还考虑了很多其他的边界点，使得该方法对边界噪声不敏感，而且得到的线性骨架具有很好的连通性。但是计算广义势场的计算复杂度较高。

值得注意的是物体通常不能从非常细的线性骨架准确地再生。因此在物体的骨架线性提取时一定要重视，理想的骨架算法应具有如下的性质：

1) 骨架结果保留原始图形的拓扑特征，即骨架的点集必须是连通的，最好 保持单像素宽度，只有这样，才能降低后续处理的复杂性;

2) 骨架带有一定的形状信息，例如骨架点处的距离变换值；

3）骨架应当位于相对物体边界的中心；

4）骨架结果对边界噪声的敏感度低，边界的轻微扰动不会产生骨架的明显 变化；

5）要保存初始物体的结构特征（拓扑结构）与结合性，并且一般要具备物 体的再形成能力。即由骨架可以重建出原始的物体，这就需要骨架化

程是可逆的。

1.3 论文主要工作与内容安排

本文所做的工作主要集中于模型骨架提取算法的实现，根据上节所述，骨架是一种特征突出、表达简单、有层次结构的图形几何特征。本文的主要工作就是实现具有如上优越性能的骨架算法。

主要内容安排如下：

第一章：主要论述本文的研究背景和选题意义，根据现有的研究成果，分类别详尽归纳当前国内外三维骨架提取算法，确立了研究的理论和实验基础，进而引出本文的主要研究内容。

第二章：阐述骨架提取方法方面内容,分析国内外该方面研究进展,提出了视觉主骨架的概念和提取方法。

第三章：有关骨架树的描述和度量方面的内容，提出并完善了拓扑相似性度量和形状相似性度量。

第四章：基于MATLAB的骨架提取算法的研究实现。

第五章：对本文的工作予以回顾,对存在的问题和未来的工作作以展望。

2 物体骨架提取方法研究

2.1 骨架提取的基本概念

2.1.1物体骨架与物体边界/轮廓的关系

骨架提取方法属于骨架应用于图像处理领域的基础研究阶段，领先于其它相关研究，该部分突破性研究成果对此领域的发展具有巨大的作用。

骨架是基于物体形状特征的简化对象描述方式，得到理想的物体骨架具有重要的意义。简洁准确的骨架能够突出物体的整体结构，反映物体的边界形状，其二简洁的特征,简化了其后期的描述和度量的困难,为物体的形状特征匹配实现带来方便。再者，骨架提取研究一个重要的目标是将图像提炼成反映其本质的简化表示，可以在保持重要的拓扑和几何结构特征的情况下清除这样那样因素引起的轮廓失真影响，在识别技术上可以引导出一种终点、结点和各子部分连接关系的特征描述方式，从而实现一种应用模糊理论于图像识别领域的智能识别算法。因此是图像识别领域研究的重点，是计算机视觉、人工智能、图像处理等领域的关键技术和研究的热点之一。 在数字图像处理领域，边界与轮廓没有本质区别，是图像的一种特征。它是由图像的部分边缘点连接起来的集合图形，用来表示图像中某一目标的形状。

物体骨架是物体边界或轮廓的一种简化形状表示方式，可以充分描述物体的形状和实现物体的识别。

骨架作为物体形状的一种表示方式，与采用轮廓描述形状相比，拥有许多优点。譬如，骨架可以表述出物体的整体结构特征，很多物体仅仅从结构上就可以很容易的区分，这点基于轮廓的形状描述是不能清晰表达的。骨架可以通过最大圆半径和骨架枝信息关联物体的轮廓形状特征，很容易的实现物体形状的保存和重建。因为骨架能够描述物体的整体特征，这使得骨架可以处理那些轮廓不准确的物体的识别问题。另外，骨架可以描述一些结构复杂的物体。如物体内部含有空洞等形状的;这些基于形状的轮廓描述是根本不能解决的。其它的优点诸如图像压缩比例大,可以实现多尺度选择等非常多，这里不再一一赘述。

2.1.2提取物体骨架的基本要求

研究者普遍认可的提取骨架的标准有五个：其一，提取骨架的连通性问题；其二，提取骨架枝的单像素问题；其三，提取骨架逼近物体的“中轴”问题；其四，边界噪声对物体骨架的影响问题；其五，提取骨架方法的效率的问题。

2.2 经典的物体骨架提取算法

以上诸多的优点，引起学者广泛的研究。人们己经提出的骨架提取方法，大致分为两类：一类处理的对象是离散域中的物体模型(如位图等)。通过对像素的操作得到骨架，但结果不可避免的受到离散化对精度的影响，此类方法得到的骨架一般用于图形的匹配和相似性度量；另一类处理基于连续域模型的对象，如多边形模型，使用严格的数学方法求解骨架的数值解，结果精度高。但此类方法适用范围窄，对于复杂三维物体，计算过程十分复杂，难以保证其稳定性。此类方法往往用于几何建模和物体重建。

本文研究的范围是离散域图像识别。在离散域下，提取骨架的方法大致分为细化骨架提取算法、距离变换骨架提取算法、Voronoi图骨架化算法、偏微分方程骨架化算法以及形态学骨架提取算法五类

2.2.1细化骨架提取算法

拓扑细化的方法在解决细节性较多、形状多为线状长条状等这些规则性强的结构的物体形状方面效果较好，例如电路图、字体，医学图像等。如图2-1(a)所示，细化能准确提取汉字的骨架。算法的中心思想是在保持拓扑结构不变性的条件约束下，不断地剥离表层的像素，直到最后剩余的骨架。这类方法通过制定大量的约束条件，判断像素的去留问，往往执行效率较低。此类方法得到的骨架可保证连通性和单像素性，但对边界噪声非常敏感，不能得到简化的整体形状重要的的拓扑结构，容易产生不必要的分支，且造成骨架点的位置不准确。如图2-1(b)所示，边界的小噪声产生了很多多余的骨架枝，并且骨架的位置不是准确地靠近物体的中心。

(a) 汉字细化 (b) 鱼的细化结果

图2-1 细化骨架

文献[17]提出了一种边缘点删除和内点保留细化方法相结合的新思想，即首先保留内点及图像中绝对不能被删除的特殊点(如交叉点,拐角点等)；其次，删除多余的像素点；最后，去除多余枝线。实验结果表明，该算法在细化的同时很好的保持了原图像的连通性，所得的骨架图像对称性好且为单像素宽。也一定程度改善了较多多余分支的问题。在三维情况下，细化方法受到了限制，如何消除细化结果中带面的情况成为研究的难点。

2.2.2距离变换骨架提取算法

距离变换的方法，如最大圆法，最大正方形法等，在解决整体性比较好。细节性不多的物体形状方面效果较好，比如人体轮廓、大型的动物轮廓、整体性较好的汽车等轮廓。算法首先对图像进行距离变换，使用不同的距离标准如欧氏距离、棋盘距离、街区距离等可产生不同的距离分布；然后寻找距离值梯度脊线，即局部距离极值,也是距离梯度发生突变的点来形成骨架，此类方法最大的缺陷是在离散域中，难以保证骨架的连通性。这方面文献集中解决的就是在欧几里德距离图的基础上，增加连通判决条件或连通方法使得得到连通的骨架。

文献[18,19]对传统的距离变换的方法进行改进，提出了一种新的算法。算法保证了骨架的连通性及单像素性。算法复杂度与文献[7]相比，减少了很大的运算量。算法的主要思想是选择一个骨架种子点，然后以单像素宽度生长出其余的骨架点，算法中可以给定权值控制生长精度，实现骨架的多尺度控制。这样算法提取的骨架保证了骨架的单像素性和连通性，同时该算法也具有良好的抗边界噪声鲁棒性。文献提出的算法分三步:

1)对二值图作距离变换(这里采用欧氏距离变换)，得到图像每一点距离场值和距

其最近的边界点坐标。选择距离场值最大的点作为种子点。

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)

如图2-3所示，基于Level Sets 的AFFM算法结果含带面的情况。

图2-3基于Level Sets的AFFM算法无法消除二维骨架带面的情况

2.2.5形态学骨架提取算法

数学形态学的骨架化方法。是一门建立在数学图论基础上的学科，是几何形态学分析和描述的有力数学工具。它的基本思想是用具有一定形态的结构元素去量度和提取图像中的对应形状以达到对图像分析和识别的目的。用数学形态学处理图像可以简化图像数据，除去不相干的结构，保持它们基本的形状特性，并且有天然的并行实现的结构优点。

但是利用数学形态学理论提取物体骨架，存在一些问题：一是得到的骨架是非连通的；二是容易受边界噪声的影响。把目前形态学的骨架提取方法研究范围从二值图像推广到灰度图像、彩色图像、三维图像，可以提高骨架包含信息量，从而提高后期识别统计概率。另外提高提取效率，得到实时处理的效果成为今后的发展方向。

2.3当前骨架提取算法面临的重点和难点

骨架是物体的“中轴”，体现的是物体的整体拓扑结构和形状。然而，现有的骨架提取算法都未能很好的体现这一思想，不能有效处理骨架的噪声问题。这样提取的骨架含有很多的噪声，出现一些主次不分!结构混乱的现象，影响对物体的真实形状和连接关系的正确判断，严重的甚至会出现对物体错误的认识。无论是拓扑细化还是基于距离场的骨架算法，都面临这样的问题，如图2-4所示。

本文来源：https://www.bwwdw.com/article/2234.html