（信号与信息处理专业论文）骨架的层次性分解和求取方法研究.pdf

华中科技大学硕士学位论文 摘要 图形图像识别是计算机视觉、人工智能、图像处理等领域的关键问题，在军事、 生产和生活的许多领域有着广泛的应用前景，而选择合适的特征空间则是决定识别 成功与否的重要步骤。图像的形状包含了大量的视觉信息，是最常用的特征空间。 骨架是一种保留了拓扑信息的全局形状变换，其结果直观，意义明确，且便于进行 相似性计算，是物体表示和识别的有力工具。为了解决骨架自身固有的对噪声敏感 问题，方便进行匹配，建立一种层次性的骨架结构是有意义的，也是本文主要的目 标和工作。 本文首先介绍和分析了骨架求取中的两种基本方法：距离变换和细化，它们骨 架都有密切的连系。距离面的脊线轨迹就是骨架点的位置，细化准则下所保留的像 素恰好是保留了对象拓扑结构的中心线。基于距离变换的骨架连通性难以保证，细 化的骨架虽然连续但是对局部信息敏感。因此，如果能把由距离变换得到的全局信 息应用在细化过程中，则可以得到拓扑保留、连续、而且较稳定的骨架，这无疑是 有吸引力和实用价值的。 接下来，本文对人类视觉系统( h v s ) 进行了简单介绍，给出了视觉识别过程 的生理学和心理学的相关理论和解释，提出了识别所遵循的一些重要规则。对象的 重要性和所占据的空间存在正关系：物体识别是一个从粗到精的分层的过程：物体 的尖锐突起在识别中具有更重要的作用；这些规则是建立骨架层次性结构的理论基 础。然后将视觉识别的规律引入骨架描述中，使用骨架及骨架参数来定量描述识别 准则。建立了骨架点的面积模型，说明了骨架半径与骨架点局部信息量的关系；建 立了骨架枝与连续边界的对应关系，给出了信息量分布与骨架角的定量关系；为下 一步进行多尺度骨架求取奠定了基础。 基于上面的工作，本文将细化和距离变换相结合，提出了计算多尺度骨架的算 法。该算法将距离值融入细化过程，利用了距离信息构造识别函数进行多尺度筛选， 得到的骨架保留了原始图像的拓扑结构，同时避免了不连续的问题。本算法在识别 华中科技大学硕士学位论文 函数中加入角度信息，增强了对边界特征的描述能力；算法具有开放的框架，并不 依赖于具体的细化和距离变换方法，可以采用更优越的算法提高性能；而且算法结 构使得构造一个反馈式的识别系统成为可能。 然后，本文对三维空间的骨架求取进行了介绍，分析实现了一种性能较优的细 化算法，给出了实验结果：并对算法在三维空间的推广进行了讨论。 最后；对全文工作和今后的研究重点进行了总结和说明。 关键词：图像识别，骨架，多尺度，三维。 华中科技大学硕士学位论文 a b s t r a c t a st h ek e yt e c h n o l o g yo f c o m p u t e rv i s i o n ，a r t i f i c i a li n t e l l i g e n c e ，i m a g ep r o c e s s i n g a n ds o o n ，i m a g er e c o g n i t i o nc a nb ea p p l i e d i nm a n yf i e l d so f m i l i t a r y , i n d u s t r ya n d l i v e s s e l e c t i n gr i g h t f e a t u r ei so n eo ft h em o s t i m p o r t a n t f a c t o r st om a k er e c o g n i t i o n s u c c e s s f u l ，a n ds h a p e ，w h i c hi n c l u d e sl o t si n f o r m a t i o no fo b j e c t s ，i ss t u d i e dd e e p l ya n d b r o a d f i r s t l y , d i s t a n c et r a n s f o r ma n dt h i n n i n ga r ei n t r o d u c e da n da n a l y z e d t h er i d g e so f d i s t a n c em a pa r ep o s i t i o n so fs k e l e t o n s ，a n dt h er e s u l t so f t h i n n i n ga r ej u s tt h em i d l i n e s o fo b j e c t b u t ，s k e l e t o n sb a s e do nd i s t a n c em a pc a nn o tg u a r a n t e et h ec o n n e c t i v i t ya n d s k e l e t o n so ft h i n n i n ga r es e n s i t i v et ob o u n d a r yd i s t u r b s s ot h ec o n t i n u o u sa n ds t a b l e s k e l e t o n sm a yb ec o m p u t e d b yc o m b i n i n g t h ed i s t a n c em a pa n d t h i n n i n g t h e n ，t h eh u m a nv i s u a ls y s t e m ( h v s ) i si n t r o d u c e d b a s e do nr e l a t i v et h e o r yo f p h y s i o l o g ya n dp s y c h o l o g y , s o m ed i s c i p l i n e so fr e c o g n i t i o na r ep r e s e n t e d t h em o r e s p a c eh e l dt h em o r ei m p o r t a n tt h eo b j e c t ；r e c o g n i t i o ni sah i e r a r c h i cp r o g r e s sf r o mt h e w h o l et od e t a i l s ；t h es h a r pp a r th a sm o r es i g n i f i c a n c e t h e s ed i s c i p l i n e sa r e a p p l i e di n t o s k e l e t o n sa n de x p r e s s e db y p a r a m e t e r so fs k e l e t o n s t h ea r e am o d e lo fs k e l e t o np i x e li s c o n s t r u c t e dt oe s t a b l i s ht h er e l a t i o n s h i pb e t w e e ns k e l e t o nr a d i u sa n dl o c a li n f o r m a t i o n t h em o d e lo fi n f o r m a t i o nd i s t r i b u t i o ni sa l s og o t t e nb yi n t r o d u c i n gs k e l e t o na n g l e t h e a l g o r i t h mo f m u l t i - s c a l es k e l e t o n sw i l lr i s ea b o v et w om o d e l s f o l l o w i n g ，am u l t i - s c a l e s k e l e t o n a l g o r i t h mi sp r e s e n t e db yc o m b i n i n gd i s t a n c e t r a n s f o r ma n dt h i n n i n g d i f f e r e n tr e c o g n i t i o nf u n c t i o n sb a s e do nd i s t a n c em a pa r eu s e d t oc o n t r o lt h ee x t e n to ft h i n n i n gt o g e ts k e l e t o n so fd i f f e r e n ts c a l e s k e l e t o n so ft h e a l g o r i t h ma r et o p o l o g y p r e s e r v i n ga n dc o n t i n u e b ya p p l y i n ga n g l et h ea l g o r i t h mc a n d e s c r i b es h a p em o r e v a r i e d l y d u et ot h eo p e ns y s t e m ，n e wm e t h o d so fd i s t a n c em a p a n d t h i n n i n gc a nb ea p p l i e dt or e d u c et h ea l g o r i t h mc o m p l e x i t y a n daf e e d b a c ks y s t e mb a s e d i j i 华中科技大学硕士学位论文 o nt h ea l g o r i t h mi sa l s op r o b a b l e i na d d i t i o n t h ec o m p u t a t i o no fs k e l e t o n si nt h r e e d i m e n s i o n a ls p a c ei sd i s c u s s e d a 3 d t h i n n i n ga l g o r i t h mi sr e a l i z e d t h ee x t e n s i o no f t h ep r e s e n t e da l g o r i t h mt o3 d o b j e c t s i sd i s c u s s e dt o o f i n a l l y , c o n c l u s i o no n t h e s i si sm a d ea n ds o m ei d e a sf o rf u t u r ew o r ka r eg i v e n k e yw o r d s ：i m a g er e c o g n i t i o n ；s k e l e t o n ；m u l t i - s c a l e ；t h r e e d i m e n s i o n i v 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：象7 弓肛 日期：7 中年 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本论文属于 保密口，在年解密后适用本授权书。 不保密刚。 ( 请在以上方框内打“4 ”) 学位论文作者签名：胬豸亿 日期：7 中年y 月日 指导刻嗽：分支彳 日期：浏年厂月 目 华中科技大学硕士学位论文 1 1 引言 1 绪论 图形图像识别是计算机视觉、人工智能、图像处理等领域的关键问题，在c a d 、 集成电路设计、机器人路径规划、数字化城市、医疗诊断以及军事目标识别等领域 有着广泛的应用前景1 1 _ 3 】。一般来说，图像识别的过程包括预处理、特征提取、特征 值计算、相似性匹配等环节，有时会根据实际情况加入反馈调整参数空间。预处理 主要对识别的对象进行去噪、平滑和增强等处理：特征提取是在特定的特征参数空 间内对目标进行特征变换，抽取最能反映目标唯一性的性质：特征变换的结果常常 转化为某种形式的数值表示，即特征值，如实数、向量和矩阵等；比较不同目标特 征值间的距离就可筛选出需要的对象；在许多情况下，参数的选取并非一开始就是 合适的，这时可引入反馈的过程，由用户或者系统对识别结果进行评价，调整参数 空间以逼近最佳。在整个过程中，特征的选择和提取是最重要的一步，预处理的内 容因不同类型特征而不同，不同特征也会产生不同形式的特征值。实际上，根据应 用场合的差异，会选取不同的特征，如颜色、纹理、形状等，或者综合使用。对于 颜色和纹理主要运用统计的方法进行分析，已有许多相关研究。形状特征作为物体 的一个基本特征，尤其在识别方面有独特的效果，一直是研究的重点。本文主要考 察物体形状特征的表示，而不涉及到颜色纹理等其他视觉特性。 物体的形状通常是指封闭边界及其所包围的空间的总和。一般来说，形状描述 方法应该满足平移、旋转不变性，因为在这两种变换下物体的形状没有发生变化； 如果认为同一物体的不同比例表示具有相同形状的话，还应该满足缩放不变性。 根据不同的标准【4 j ，形状描述子可分为不同的类别。根据是否存在信息丢失， 分为无损描述和有损描述：由描述子可完全重建原物体的为无损描述，否则为有损 描述。根据描述形式不同可分为数值描述和非数值描述：非数值描述常常是对原图 像进行某种变换，结果为新的图或图像，数值描述的结果则为集合、数组和向量等。 根据源信息的不同分为外部描述和内部描述：外部描述即是边界描述，内部描述又 华中科技大学硕士学位论文 称为全局描述。 边界描述( 简称b r e p 法，b o u n d a r yr e p r e s e n t a t i o n ) 是用物体的边界来表示物体 的形状，它的基本元素是面、边、顶点。它以欧拉公式作为理论基础，要求物体的 基本拓扑结构符合欧拉公式。目前采用的比较多的数据结构是翼边数据结构和半边 数据结构( 又称对称数据结构) 。边界表示法采用“坐标值一点边一面一物体”的 方式表示物体，能提供较全面的关于点、边、面的信息。边界拟合、链码表示以及 各种边界f o u r i e r 变换都属于此类方法。 全局描述中最常见的是结构元素表示法，基本思想是将简单的基本元素通过集 合运算( 相加、相减、相交) 组成所需要的物体。其中，集合运算的实现过程由一 棵二叉树来描述，二叉树的叶子节点表示体素或者几何变换的参数，非终端节点表 示施加于其子结点的正则集合算子或几何变换的定义。此法的缺点是建模速度慢、 生成的物体模型文件大，信息表示不完整。 全局描述中还包含一类基于变换的方法，首先对图形进行一定的变换，得到较 为简化的结构，如果此简化结构能够完整地反映三维图形的信息，这样可以减少匹 配误差、提高匹配精度、并解决传统方法中难以解决的解不唯一等问题。其中最常 见的就是对称集( s y m m e t r i cm o m e n t ) 的方法，中轴骨架( m e d i a l a x i st r a n s f o r m ) 是研究最广泛的对称集之一。 1 2 物体的骨架表示和求取 通俗地，对于图像，图像的骨架是指图像中央的骨骼部分，动物的骨骼决定了 动物的外形，与此相似，图像的骨架是描述图像的拓扑结构和集合性质的重要性质 之一，利用骨架表示原始图像，可以在保持图像重要拓扑性质的前提下，减少图像 中的冗余信息，突出图像的形态特征。 用骨架描述形态的方法最早是b l u m “j 提出来的，他使用了中轴( m e d i a la x i s ) 的概念。中轴的概念可以用下面的两个例子来说明。设想在t = o 时刻，将目标边界 各点处同时用火点燃，火的前沿以匀速向目标内部蔓延，当前沿相交时火焰熄灭， 2 华中科技大学硕士学位论文 火焰熄灭点的集合就构成了中轴，前沿到达中轴的时间构成了中轴函数。如图1 1 中a 所示，火焰从边界上的两点向内部推进，轨迹随时间形成等距的同心圆，两圆 即火焰前沿交会处就是骨架点。 另外一种描述骨架的方法使用了最大圆( m a x i m a ld i s k s ) 概念。目标x 的骨架 5 c 豳由x 内所有最大内切圆的圆心组成。以骨架上点为圆心的圆满足两个条件：1 这些圆位于图像内部( 即被图像完全包容) 。2 这些圆都是最大的，从图像内部不 可能再找到另一个圆能完全包容这个圆。从这个定义也可以得出两个结论：1 每一 个以骨架上的点为圆心的最大圆至少与图像轮廓相交于两个点。2 所有以骨架上的 点为圆心的最大圆的并构成了原来整个图像的边界。这一点可以应用于图像的重 建。如图1 - 1 中b 所示，骨架上每点都对应一个最大内切圆，这些圆沿骨架积分就 恰好填满物体内部。 威4 【 火种传播骨架【b 最大圆盘骨架 图1 - 1 骨架的定义 骨架自从最初被b l u m 提出后啷，它已得到广泛的发展。骨架有如下几个性质： 1 骨架保留了原物体各部分间的连通关系，具有拓扑不变性；2 骨架使用皓线抽 象物体的形状特征，具有降维和数据压缩的效果；例如：它将一个三维物体变成了 一组相连的点、线、面，这些点、线、面和它们对应的半径函数就能描述出物体的 具体信息。3 骨架含有物体的表面信息，可以从骨架恢复重构物体。当一个物体用 它的骨架表示后，骨架和它对应的半径可由人来控制，物体的轮廓就会非常自然的 跟着变换，这一陛质可用在计算机动画上。最后，骨架变换还可应用在文档的编码 和其他一些图像处理中。 由于骨架的重要性，许多学者对此进行了深入的研究，提出了许多方法和概念。 3 华中科技大学硕士学位论文 目前的骨架算法主要分为两类：一类处理基于连续模型的对象【7 9 】，如多边形模型， 使用严格的数学方法求解，得到的骨架较精确，但是此类方法适用的范围较窄，对 于某些物体，特别是在三维空间中，精确骨架的计算十分复杂，而且存在多解、无 解的情况；另一类处理的对象是离散域的二值图像，通过对像素或体素的操作得到 骨架，但是结果不可避免的受到离散化对精确度的影响。本文主要讨论离散二值图 像的骨架求取问题。 1 2 1 连续模型的骨架求取 在b l u m 提出骨架并进行了一番探讨后不久，计算一些特殊平面图的连续骨架 算法相继给出，主要包括两类：基于方程和基于v o m n o i 图。m o n t a n a f i 1 0 】提出了一 种对多个相连多边形的骨架算法，他的算法沿着内轮廓，确定一些骨架的关键分叉 点，然后近似的用直线或者抛物线将这些分叉点连起来。p r c p a r a t a 1 1 蛤出了一种更 有效的凸多边形的骨架算法，其算法复杂度为d m l o g n ) 。同时他也给出了针对凹多 边形的复杂度为o ( n 2 1 的算法。l e e 1 2 l 给出了针对有凹角的多边形，复杂度为 0 m l o g n ) 的算法。先求关键点再拟合骨架的方法通常要根据边界点、线、面的组合 解多元方程组，并确定它们的连接关系，计算比较复杂，存在关键点被遗漏的可能， 精度也因为拟合收到限制。s r i n i v a s a n 和n a c k m a n 1 3 】给出了对多个多边形相连，有 h 个洞这样图形求骨架的算法，其算法复杂度为o ( n h + n l o g n ) 。对于多个相连的平 面图，它们的边界是由线段和圆弧构成，g u r s o y 和p a t r i k a l a k i s l l 4 】- 【1 6 1 给出计算其骨 架的算法，并把它应用于网格的自动生成，它能够确定图形的整体特征。g u i b a s 和 s t o l f i 1 7 】研究了v o m n o i 图和d e l a u n a y 三角剖分之间的关系，提出了用“四边”数据结 构来描述它们。v o r o n o i 图是骨架的超集，计算和剪枝都比较复杂，尤其对于非凸 情况，还需要区分内外骨架。 4 华中科技大学硕士学位论文 1 2 2 离散模型的骨架求取 骨架的另一部分工作主要集中在用离散空间中，方法主要有四类：一类是细化 的方法f 协删，在保持拓扑不变性的条件约束下，不断的剥离表层的像素或体素，直 到最后的骨架，此类方法得到的骨架可保证连通性：第二类方法基于距离变换【2 1 - 2 2 1 。 首先对图像进行距离变换，使用不同的距离标准如欧式距离、棋盘距离等可产生不 同的距离分布；然后寻找距离值梯度脊线，即局部距离极值，也是距离梯度发生突 变的点来形成骨架，但此类方法难以保证骨架的连续性，特别是在三维空间中；第 三类是活动边界法，又称活动围道、蛇形曲线，此法将物体边界看作封闭的弹性曲 线，图像的内部为一能量场，曲线在内外力的作用下在场内运动，当曲线能量达到 最小时其形态即为骨架，此法需要对物体边界的先验知识：第四类是基于v o r o n o i ( v d ) 图的方法f 2 3 。2 4 1 。v d 是图形学和几何学中划分空间点集关系的经典问题，而 且已证明骨架是v d 的子集。但是生成的骨架不可避免的需要剪枝，复杂度较高。 1 2 3 骨架的改进 精确骨架有着严格完备的定义，但是直接将精确骨架引入实际应用却面临着某 些困难。其中最大的阻碍在于精确骨架对物体的边界噪声非常敏感。边界轮廓上的 轻微扰动就会造成骨架拓扑结构的严重改变。这一因素显然是我们应该尽量避免 的，因此如何找到一种计算骨架的方法，使求出的非精确骨架对边界噪声有较强的 鲁棒性，将是一项非常有意义的研究工作。 如图1 2 所示，矩形的边界由于噪声发生微小扰动，骨架却产生了新的分支， 拓扑结构发生了变化。 图1 - 2 噪声对骨架的影响 华中科技大学硕士学位论文 最直接解决骨架不稳定的方法是对原图像进行平滑和边界修正，但是阈值难以 控制，可能会改变原图的拓扑。 解决这一问题的常采用一种间接的“剪支”方法：首先求出图形的精确骨架，然 后根据不同的目的要求采取不同的剪支策略，修剪掉被认为是由噪声b l 起的假分 支，达到去除噪声影响的目的。这种方法首先要求出物体的精确骨架，显然不够直 接，若是能直接求出一种对噪声不敏感的骨架将会非常有诱惑力。剪枝的准则往往 比较复杂，且缺乏通用性，需要人工干预。 g o l l a i l d i 冽提出了“固定拓扑骨架”的概念，为这种问题开辟了一种新的思路，这 种固定拓扑骨架分析在物体的整体结构特征已知的情况下，如何利用这些已知的信 息直接计算不包含噪声分支的拓扑骨架。这种方法需要物体整体结构的先验知识， 适用于人体跟踪、手势识别、医学器官识别等情况的骨架提取。若是没有关于整体 结构的先验知识，如何做到对噪声不敏感的拓扑骨架的直接提取，目前还没有有效 的办法。 1 3 论文的主要工作和内容安排 本章首先给出了图像识别的一般过程，指出选择合适的特征空间是识别成功的 关键步骤。图像的形状包含了重要的视觉信息，是本文的研究重点。物体形状描述 根据不同的标准可划分为不同的类别，骨架是一种保留了拓扑信息的全局变换，其 结果直观，意义明确，且便于进行相似性计算，在国内外得到了广泛的研究。根据 原始物体表述形式的不同，骨架求取算法分为基于连续模型和离散模型两种。基于 连续模型的算法主要运用几何分析的方法，得到精确骨架，但是存在方法复杂，时 间开销大的问题。基于离散模型的方法各有特点，也都存在不足。 从识别尤其是相似性度量的要求出发，我们希望骨架既能保持物体拓扑结构信 息，又能够具有一定的边界稳定性。从目前的研究状况看来，普遍意义上的骨架求 取已经被广泛地研究，但是骨架自身固有的对噪声敏感问题，并没有得到很好的解 决。一类方法是根据对物体的先验知识，先确定骨架的拓扑结构，再计算骨架的具 华中科技大学硕士学位论文 体位置：此类方法对特定对象如人体等有较好的效果，难以推广到一般情况。边界 平滑、剪枝等方法都需要进行繁琐的检测和判别过程，算法复杂度很高。进一步地， 骨架作为一种全局变换，包含了物体边界的所有信息，从整体到细节。这些信息在 识别中的重要性并不相同，当不同对象在整体拓扑上具有一定程度相似后，细节的 比较才有意义；如果将整体和细节信息同等对待，不仅会增加相似性度量的复杂程 度，还会得到不准确的结果。因此，骨架最好具有层次性，反映出从整体到细节的 差异；在进行整体比较时可以免除细小噪声的影响，在需要时也能加入足够的细节 信息。综上所述，一种层次性的骨架结构对于识别无疑是有意义的，也是本文主要 的目标和工作。 论文第二部分主要讨论了骨架求取中的重要基本操作，为后面讨论提供基础； 第三部分讨论骨架与形状特征的关系，初步探讨骨架分层的准则；第四部分给出层 次性骨架的算法、实现、实验结果和讨论：总结在第五部分。 7 华中科技大学硕士学位论文 2 1 像素及邻域 2 骨架的基本理论和方法 在离散域中，像素是构成图像的基本单元，也是实施运算的基本单元。像素点 的值及其相邻像素的值构成了该点的像素特征，图像所包含的像素和像素间的连接 关系则构成了此区域的形状特征。 定义2 - 1 ：1 ( m ，h ，o ) 为离散域二值图像，其中柳表示物体像素的连接关系，n 表示背景像素的连接撩石为背景。对于像素如办咖) = 话塞鬻， 即物体值为1 ，背景为o 。 一般情况下，取m = 8 ，n = 4 ，意味图像中物体即前景像素连接关系为8 邻域连 通，背景像素为4 邻域连通。 定义2 - 2 ：对于像素p ( x ，y ，) ，存在像素鼋瓴， ) ， 若o c k x 。l s l ，且o c l y ，一y 。i - ：1 ，则q 为p 的八邻域点； 若k 一1 + l y ，一y ，l 一1 ，且k x q l y ，一y q t 一0 ，则q 为p 的四邻域点。 显然地，p 也是q 相应的八邻域点和四邻域点。 如图2 - 1 所示，x 1 至x 8 为p 的8 邻域像素点，x l ，x 3 ，x 5 ，x 7 为p 的4 邻域像 素。 图2 - 1 像素p 的4 邻域和8 邻域 8 华中科技大学硕士学位论文 2 2 距离变换 2 2 1 距离变换的定义 距离变换于1 9 6 6 年由r o s e n f i e l d 和p f a l t l 2 7 】首次提出，经过多年发展，被广泛 应用于图像分析与模式识别领域【4 1 砘1 。 定义2 - 3 ：离散域二值图像l ( m ，n ，0 ) 的距离变换定义为： d r p ) ：j 骝d 纽p ，口p e o ，其中d i s t ( p , q ) 表示p 、q 问的距离。取不同 1 0p c o 1 的计算方法，就得到不同的距离变换。 城市( c i t y b l o c k ) 距离：d i s t c b ( p ，口) = x p 一i + l y p - y 4 i 棋盘( c h e s s b o a r d ) 距离：d i s t “。( p ，q ) = 触 1 咋一l ，l y ，一y q l ； 欧氏( e u c l i d e a n ) 距离：d 括f 。( p ，口) 一( 一) 2 + ( y ，一儿) 2 ； 距离变换可以看作一个波浪推进的过程，背景点是声源，每个声源同时向外发 出速度为1 的圆形声浪，物体的每个像素点被声浪触及的时间就是该点的距离值。 显然，物体的距离值仅与物体边界相邻的声源点有关。背景点的距离值自然为一。 从声浪模拟的角度来看，欧氏距离是最优变换，城市距离和棋盘距离都是其不 同程度的近似，它们所产生的声浪轨迹都不是直线。但是在离散情况下，非欧氏距 离变换的计算相对简单，因此在图像处理的许多领域得到了应用。 2 2 2 距离变换的计算 距离变换是图像处理中的经典问题，许多文献已有描述。在离散域计算距离变 换，由于方向离散化和距离离散化，会不可避免的存在误差。 计算距离变换的方法主要可分为两类：第一类方法先根据局部的邻域关系构造 模版【2 9 | ，然后让模版在图像中移动得到距离值。模版的规格因近似的距离和移动路 径而不同。第二类方法类似光栅扫描【3 0 】，使用模值不同的矢量对图像进行扫描来计 9 华中科技大学硕士学位论文 算距离值。 值得注意的是，距离变换过程中，除了得到物体像素到边界的最小距离 m i n d ( p ，q ) 之外，切点q 的位置也随之被确定。如图2 - 2 所示，0 表示背景像素， 欲求物体像素( i ，) 左侧的切点。首先沿i 轴正方向进行扫描，得到第j 列物体像素 沿i 轴方向到背景的最短距离序列为： 一x l i s , ( i ，+ 七) ，d i s ，( f ，j + 1 ) ，d 也( f ，j ) ，d 峨( f ，j - 1 ) ， 根据勾股余弦定理，( i ，j ) 到左侧背景点的摄短距离为： m i n i ，属磊万可了，扭磊了丽i ，d i s , q ，n 扭丽再面可可，) 若最小值为4 d i s ，( i ，j + 七) 2 + 七2 ，则切点坐标为( f d 括，( f ，j + ) ，j + 女) 。 2 2 3 距离变换与骨架 ， -_f-_ 0 、 ( i j + k ) 刘( 巧) 0 图2 - 2 切点位置的求取 从前面的声浪解释就可以看出距离变换与骨架有着内在的联系。根据骨架的火 烧模型，沿物体边界分布的火焰以恒定速度向内部蔓延，火焰相遇处即为骨架点， 这些骨架点既是最大内切圆的圆心，同时也是距至少两个边界点的欧氏距离最大的 点。 如果将火烧模型用时间方程来表示，则可产生一个三维的时空面，t 为时间轴， x y 平面表示某一时刻火焰烧到的位置，如图2 - 3 所示。如果将时间轴换为距离轴， 华中科技大学硕士学位论文 此平面称为距离变换面或距离面( d i s t a n c es u r f a c e ) i z s l ，可以看出，距离面上除去 脊线处，各处梯度都为1 ，脊线处梯度方向发生突变，脊线位置就是骨架。而将时 间轴换为距离轴也实际上说明了，火烧模型和距离变换对原始图像所进行的变换是 一致的，距离轴的值也就是距离变换的值。 基于距离变换求取骨架的方法实质上就是寻找脊线的过程，其判别准则主要就 是根据梯度的变化。某点梯度主要是根据其相邻区域内点的信息来计算，在这个意 义上，每个脊线点也就是骨架点的判断依据是局部信息，故各个骨架点间的连续性 难以保证，这也是基于距离变换的方法最大的问题，而距离值这个全局计算的结果 没有得到充分和用。 图2 3 距离面 如图2 4 所示，左边是一个矩形的距离变换效果图，亮度越大的部分代表距离 值也越大，可以看到有些点的亮度值明显高于其周围点的亮度，这些局部极值点的 轨迹形成了所谓脊线；在右图中是该矩形的骨架显示，可以看出骨架点位置与脊线 轨迹很好的吻合在一起。 1 1 华中科技大学硕士学位论文 2 3 细化 2 3 1 细化的定义 图2 4 距离脊线与骨架 细化( t h i n n i n g ) 是模式识别和图像分析的常用基本技术，被广泛应用于字符辨 别、图像压缩、细胞提取、指纹识别及电路板设计等领域。细化可以看成是一个连 续剥离表面元素，直到获得中心连通线的过程。细化结果相比原型更适于进行拓扑 分析和形状分类。关于细化，目前还没有精确的数学定义，其方法和准则也根据对 象场合的不同而存在差异。按照拓扑连续性有四邻域、八邻域和混合连通算法，按 照扫描顺序有单方向、双方向和多方向算法，按照执行过程有串行、并行和串并混 合算法。 细化是一个迭代的过程，每一次细化依赖于前次操作的结果。在串行细化中， 边界元素被逐一判定剥除，第n 次迭代不仅与第n - 1 次迭代相关，而且与第n 次 迭代中已处理的元素也有关。并行细化算法对所有像素使用相同的判别准则，每次 迭代仅与前次结果相关，可同时对边界所有元素进行操作，执行速度较快，效率高。 细化操作就是根据像素及其邻域像素的分布特征，采用一定的准则，构造模版， 对图像进行扫描过滤，将冗余像素变为背景，保留中心像素，如此反复，直到没有 冗余。一般图像对象保持8 邻域连通，背景为4 邻域连通，因此通常使用为3 * 3 模 版，根据像素与其8 邻域的联结关系作为判别准则。也有的算法为了获得更快的速 度而采用更大规格的模版，但是从图像本身来讲，8 邻域信息即可充分判定中心像 素的性质。 1 2 华中科技大学硕士学位论文 2 3 2 细化与骨架 细化法的思想是一层一层的去掉物体的边界，直到最后剩下的厚度为1 的骨架， 其本质就是模仿火烧模型，不断删除对象边界点，最后不可去除的点就构成了骨架。 细化法适用于离散空间的骨架提取，并已发展得较为成熟。一般的实现方法是基于 点的邻域特征对点进行分类，通常可以分为普通点( r e g u l a rp o i n t ) 、衔接点( j o i n t p o i n o 、末梢点( e n dp o i n t ) 。所谓普通点就是当该像素点由前景变为背景后，其所在 图像的前景和背景的连通关系不会发生改变。前景物体的8 连通不会发生断裂而使 欧拉数改变，背景的4 连通也不会改变而出现孤立空洞。在重复进行的去皮过程中， 每次抛掉的都是上次去皮结果中的普通点，而衔接点和末梢点则保留不抛掉。这样 重复进行，最后再无普通点可抛时，得到的点集就是骨架。 一个理想细化算法得到的骨架应具有如下特点：1 拓扑保留，细化后的骨架保 留了原始对象的分支和连接特点；2 连续性，细化骨架在空间可表示为连续的图， 其结点关系可用树形结构表示；3 稳定性，细化骨架反映对象拓扑结构特点而不受 边界局部噪声的扰动影响。 细化算法依据像素邻域信息设定准则，采用迭代的方法逐步得到骨架。可以看 出，由于细化依赖于局部信息，其必然受到边界像素分布情况的影响。换句话说， 如果噪声引起的像素分布满足细化的准则也将被保留，这显然是不希望的结果。 2 4 本章小结 本章简单介绍了图像处理中的两种基本操作：距离变换和细化。采用不同的距 离定义会产生不同的距离变换，欧氏距离变换是最精确的。在计算像素点距离值的 同时，其最小距离对应的边界点位置也随之获得。细化通过一定准则反复迭代，剥 去冗余像素而得到骨架。并行细化具有判别简单、速度快、便于硬件实现等特点， 成为主要采用的方法。 距离变换和细化与骨架都有密切的连系。距离面的脊线轨迹就是骨架点的位 置，细化准则下所保留的像素恰好是保留了对象拓扑结构的中心线。基于距离变换 华中科技大学硕士学位论文 的骨架连通性难以保证，细化的骨架虽然连续但是对局部信息敏感。因此，如果能 把由距离变换得到的全局值应用在细化过程中，则可以得到拓扑保留、连续、而且 较稳定的骨架，这无疑是有吸引力和实用价值的。 1 4 华中科技大学硕士学位论文 3 1 视觉识别规律 3 骨架的层次性分解研究 3 1 1 人类视觉系统( h u m a nv i s u a ls y s t e m ) 人类视觉系统，简称h v s ，是一套复杂而多变的系统。多年来，为了发展具有 人工智能的识别系统，建立对h v s 有合理解释的模型一直是研究者们努力的方向。 从生理角度来看，光线穿过瞳于l 会在视网膜上产生电信号，相邻的电信号聚集成簇， 然后通过光路在大脑视觉皮层上转化为可识别的如颜色、纹理、边界等信息。值得 注意的是，现实中的三维物体是以投影的方式在视网膜上形成二维信息的，故二维 识别具有基本的意义。 w o l f e 3 2 1 将整个识别过程分为两部分：前注意( p r e a t t e n t i v e ) 和注意( a t t e n t i v e ) 阶段。在前注意阶段，视觉系统捕捉场景分布，下一个阶段才进行目标分析和识别， 在此过程中还存在与头脑中先验知识的交互过程。 h e b b 3 3 1 分析了神经结构在视觉体系中的运作机制，提出了神经元的逻辑理论。 他的理论直接影响了后来蓬勃发展的人工神经网络技术。h e b b 认为视觉识别不是作 为整体进行的，而是各个独立的组织分别学习和整合的结果，学习演化是他理论的 核心。 直到现在，h v s 的机理并未完全被认识。但是随着生物学、医学、电子学等相 关学科的发展，对视觉系统必将有更深入的理解。 3 1 2 视觉的分层准则 根据前人的研究，我们认为视觉识别过程具有如下重要性质：1 物体的重要性 与其占据的空间成正比。2 视觉在分辨物体时遵循着由粗到精的分级过程。3 物 体凸起越尖锐的部分含有更重要的信息。 华中科技大学硕士学位论文 在视觉上，占据空间大的物体重要性高于小的物体。这点容易理解，面积大的 物体投射在视网膜上所对应的视细胞数目也较多，其重要性自然越高。在一幅画面 中，占据面积大的部分首先引起人的注意也是同样的道理。 生理学和心理学的实验都证明，人类观察时遵循由粗到精，先整体后细节的过 程。即首先识别较为明显，几何尺度较大的形体特征，然后才注意到局部信息。例 如观察一棵树，首先我们把它作为概念中的树的整体来看，进一步看到枝干的分布 伸展情况，最后才注意到叶子的形状。b r u c e ”j 认为在视网膜上由光信号转化而来 的电信号在刺激视觉皮层时，每个视细胞会在皮层中映射多个像，形成多个接收区 域，这些区域含有相同信息但尺度不同，从而引起不同尺度的识别过程。 物体边界的起伏凸凹不平，许多学者认为尖锐的凸起在识别中有更重要的作 用。a t t n e a v e 和a m o u r 3 5 j 通过实验证明了拐角在识别中的显著作用，在著名的笔画 猫的实验中保留了凸点的简化图最好的符合了辨识的要求。当使用多边形拟合物体 时，实验【3 6 】证明保留了凸点的拟合收到了好的效果。实际上，凸起往往代表了拓扑 结构的变化，如动物头上角的生长，新树枝的伸出，因而有更重要的意义。 3 2 骨架与形状特征 作为物体形状特征的一种表示方法，我们希望骨架在形式上能够反映出前面所 讨论的视觉准则，以提供更加简洁、有效的特征表达，为接下来的特征匹配和相似 性度量打好基础。因此，我们首先分析骨架结构和特点，然后寻找视觉准则的骨架 表达形式，通过骨架参数对准则进行量化描述，最后将结果用于骨架的简化和改进。 3 , 2 1 骨架的结构 为了方便和简洁，本文重点讨论二维离散图像，三维的情况会给出相应说明。 骨架反映了物体的拓扑结构和形状特征，根据不同的位置关系，可以把骨架上 的点分为三类：第一类为顶点( e n d p o i n t ) ，其8 邻域中有且仅有一个骨架点；第二 类为过渡点( v i a p o i n t ) ，其8 邻域中有且仅有两个骨架点；第三类为联结点 华中科技大学硕士学位论文 ( j u n c t i o n p o i n t ) ，其8 邻域中有大于两个骨架点。 图3 1 骨架点的分类 如图3 1 所示，a 点为顶点，其最大圆与物体边界有且仅有一个切点，即为本 身；b 点为过渡点，其最大圆与边界有且仅有两个切点：c 点为联结点，其最大圆 与边界有三个切点。 定义3 - 1 ：s 品，s 2 一) 为骨架点集合，若存在子序列b ，s t + 1 ) o , j j - 1 , s j ) s ，且、 s ，为顶点或者磺结点，则称 s i ，s i 。，j h ，s ，j 为一支骨架枝。 般地，一副骨架中包含有多于一支骨架枝。 定义3 - 2 ：s 为骨架枝上一点，p 、q 为物体边界上的点，对于任意q ，若 d i s ，p i = a l s ，q l ，则称p 为s 对应的切点，其中d i s ，p l 表示s 和p 间的距离，r = a l s ，p i 为s 对应的骨架半径，s p 为s 对应的半径向量。 定义3 - 3 ： s p ，s p 2 为s 对应的一对半径向量，一l s p t s p 2 为两向量间夹角，且 s 石，称矿为s 对应的骨架角，见图3 。2 。 图3 - 2 骨架半径和骨架角 1 7 华中科技大学硕士学位论文 根据骨架角的定义，从图3 - 2 可以得到，骨架点s 与切点p 。、p ：构成一个等腰 三角形。若能求得p 1 、p ：的位置，则三角形三边均可知，其顶角即口也可知。 对于骨架点s ，骨架半径r 和骨架角毋联合描述了s 所对应的边界的形状特征。 对于物体的主干部分，r 的值较大，r 和毋变化都较缓陧；对于微小的突起，如 噪声，r 的值相应较小。如图3 - 3 。 图3 - 3 主干和噪声的骨架对比 对于尖锐的分支，值较大，对于平缓的分支，庐值较小：因此妒可起到区分 尖锐和平滑分支的作用。如图3 4 。 图3 _ 4 不同分支的骨架对比 由此可以看出，骨架半径r 和骨架角毋联合描述了物体的边界形状特征，但是 单独的r 或者描述物体边界的特征都是不完备的，两个参数必须以合适的方式联 华中科技大学硕士学位论文 合描述对象的形状特征。 3 2 2 骨架的分层准则 从骨架半径和骨架角的定义可以看出，某点的骨架半径表征了该点骨架的宽度 信息，大的半径对应宽的分支，小的半径对应窄的分支；而骨架角则反应了沿骨架 方向上物体外形变化的尖锐程度，大的骨架角对应尖锐的表面，小的骨架角对应钝 的表面。 因此，我们根据前面提到的视觉分层的标准，使用骨架半径和骨架角作为参数， 寻找出骨架的分层标准。 首先物体的视觉重要性与其占据的空间有关，占据空间越多，意味着所包含的 信息量越大，也就越重要。怎样度量对象所包含的信息量呢，对于二维空间来说， 一个很直观也有效的方法就是物体所包含的面积。( 三维空间可以推广到体积的概 念。) 物体面积越大，其信息量也越大。 第二，物体识别遵循从粗到精的过程。从频