（应用数学专业论文）对称集及其在形状识别中的应用研究.pdf

北方业大学硕士学位论文 摘要 计算枫视觉又常称为视器视觉，是一门通过研究图像或视频数据观察周围世界的学 科，主要以摄像机拍摄的图像或视频为原始数据，提取出在图像或视频中能观察到的事 物信息。多媒体信息处理技术已成为日常生活领域的迫切需求，而人们希望能用计算机 技术来处理视觉问题，例如利用入脸、虹膜、指纹等识别技术来处理与个人有关的事 务。计算机视觉技术越来越成为推动我国信息化进；步不可或缺的技术。 形状识别是计算机视觉中的一个基本问题，也是一个重要问题，广泛应用于图像分 析、计算机视觉和目标识别等应用领域。人类可以缀容易的识别物体的形状，但是对于 计算机来说，自动识别任意物体的形状却相当困难。当形状发生平移、旋转、放缩、遮 挡后，使计算机快速、准确的识别物体的形状仍然是一件相当困难的事情。本文在总结 前人工作的基础上，从两个方面进行了尝试。 l 、在变换域方法的基础上提出了v 描述子，本文提出了一类新的v 描述子，对二 维图形进行v 变换提取形状信息，定义归一化后的变换系数为描述子，具有旋转、平 移、放缩不变性，并通过形状主方向在一定程度上消除了起始点的影响。通过快速v 变换可以快速、有效地计算出v 描述子，并且采黑了加权欧氏距离，充分利用了v 描 述子的多分辨率分析特性，对轻微遮挡具有一定的抵抗力，可以根据实际情况达到较好 的识别。 2 、在学习奇点理论中对称集概念的基础上，提漱了一类与对称集和反对称集密切 相关的形状描述子。通过形状上具有相互对称性的点的几何性质产生一个二值内积图 表，该图表拓扑结构的变化同中轴、对称集和反对称集的变化密切相关。物体形状的变 化引起对称集和反对称集的变化，从丽弓l 起内积图表的变化。文章中通过三角域上 w 蕾斑蘧数来重新表示内积图表的上三角矩阵，得到一些系数，我们将这些系数定义为 描述子。通过对比不同类形状，其中包括一些遮挡或者被加噪的图形，得到理想的结 果，验证了该描述子具有旋转、平移、放缩不变性，并且对起始点不敏感，尤其是对轻 微遮挡具有较好的抵抗性。 关键词：对称集描述予形状识别v 系统三角域 北方工业人学硕十学位论文 s y m m e t r ys e ta n di t su s ei ns h a p er e c o g n i t i o n a b s 重r a 谯 c 0 r 叩眦e r 、，i s i o ni so r c l lr e 向m 缸t 0a sm 幽e 访s i o 玛i sa ni n ：t 醐i s c i p l i l l a r y 州e c t r e l a t e dm a n ys c i 饥c e6 e l d s ，州c hr e s e a l 埔m ew o r l d 釉u n dl l sb y i l t l a g c 锄d v i d e 0d a t a w i m 妞a g e o f 逊妇繇鸭脚l e 鼢幻麟c o 雌刚霞撇勰d m o 豫强e 戤o f c o 磁脚埝 d e 越w i mv i s i o ni sk 嬲em o f e 勰dm o 瓣妇p o r 拓随扭饿ei i l 南衄蕊o no f o u f c 0 磁m y s h 攀r 。c o 鲥t i o n i s a n e s s 硎a l 拍d i 瑚邵吨m t p a r t o f c o m p 懈v i s i o n ，i t i s u s e d m m a n y 蠢越南鼹矗弱妇鑫寥喇s ，铡撇访硼，鞠d 纨蟛湫砖鲥畦豫w 瓣e p e o p l e e 鼹 r e c o 鲫娩eo b j e c ：t se a s i l y ，i ti sd i 箍c u l t 衙唧咖t 0m 舀l i z es h a p l e sq u i c 坶雒da c 删e ! l y ， e s p e c i a l l yw h i 。nt l l e 蜥i st r a n s l 砌谢n lm t a t i o 玛觚l 撕。玛a n ds c a l e 仃a i l s f o m m 付l i s p a p e r w e 如c u so nt 、m d h o d s t os t l 正ys h a p ed e s 谢p t o r f i r s t l y ，w ep 潞e n tan o v dv s y s t 绷d e s c r i p t o ro fa2 dm o d e l ，w 轴c hi si i 】a r i a n ti l lt 1 1 e r o t 撕0 1 1 ，m m s l a t i o i l ，a n ds c a l e 仃a n s f o n 呜r c m o 询gt 1 1 ed 谂c to f t h es t a r tp o i n to f t h es h a p e 曲u g hm em a i n 嘶e n 谢o n w es ： 妁wm a tv s y s t e md e s c 嫡p t o rc a nb ec o 】m p u t e de 缳c i 咖l y 毋妇毓v - s 蹲懿曩a 燃删鸥剃k 倒戳e f m 痰矗鼢o l 澌麟恕a l y s 主s 峨糕廖 w e i 曲t c d 跏c l i d e 姐d i s t a n c e ，s of h en e wv - s y s t 锄d e s 嘶p t o rh 硒s o ：m er e s i s t 锄c et os l i 咖t l y b l o c k ，a n dm a y a 蜥e v ea9 0 _ o dr 。c o 鲥t i o na c c o r d i i l gt ot h e 删s i t u a t i o n s e c 黔f 话，an o v 或照a l ，cd 酬p 睡o fi s 妇打d ( 融e ，谢嫩馥运d o s d y 黼a l e d 童。氇es y 翔翔故疆 s e ta r l dm ea n t i s 舯酏哕s e t ad i 砸即姒w i 廿1b i n a d ，r e 西o i l si so l 比i i n 。db yp a 趣o f p o i n t s w h i c h 妇a g e o m 鼬r i c a l 舯p 积y b a s e do nm e i rm 删s 舯鼬哕t h ec o e 伍c i e n t 、) l ，m c hi s 氇ef q 瞬联瓣赫出e 瞰砸雒g u l 瑟搬麴矗o f t h ed i 鲫o n kw a l 姗f 珊蕊傩s 姗 o n 氍勰誊e d o m a 趣i s d e 蠢蒯缸龇s h 带d e s 舐p 鼢聪s d e s 蛳i s 删谢氇o b j 勰远 d i 行确tc l 龋s e s ，锄ds o m ed b j e c t sa r eo c c l u d e do rn o i s e d t h e 删t sa r ep i o n l i s 岵t 1 1 e d e s 谢p t o ri s 锄t i nm of d t a 6 0 玛咖1 a 石册，锄ds c a l e 咖胁a t i o n 阳m o v i l 唱吐1 e “f t o f 氇e 嘲瞧弦波o f 重量捡露a p e ，删a l l y 纛龋s o m e 溺i s 细c ct os l i 曲lo 翻璐i 陇。 k e yw o r d s ：s y n 姗e n 了s e 乞d 锚c “p t o r s h a p er e c o 印i t i o n ，v _ s y s t e i i l t r i a n g l ed o m a 】 2 _ 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北方工业大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名纵f ，设字日期；沙库卵准 学位论文版权使用授权书 本学位论文作者完全了解j 匕友王些太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权j e 友王些盔堂可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书) 糊姗虢孤凌 导师签名：锄膨夭 签字日期滞歹月调签字日期：d 净明诟 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 北方j 1 ：业大学硕士学位论文 第一章绪论 计算机视觉又常称为机器视觉，它是一门通过研究图像或视频数据观察周阂世界的 学科，主要以摄像机拍摄的图像或褫频为原始数据，提取出在图像或视频中能观察到的 事物。随着信息时代的到来，用计算机处理各种信息的需求越来越多。多媒体信息处理 技术已成为r 常生活各领域的迫切需求，而人们希望能用计算机技术来处理视觉问题， 例如剩用人脸、虹膜、指纹等识别技术来处理与个人有关的一切事务。利用自动识别技 术帮助盲人，利用视觉自动监控系统监视环境中发生的非常事件，如陌生人侵入、老年 人的异常行动等。再如智能交通管理系统、视频检索、用于军事目的的自动目标检测 等，都需要应用机器视觉技术来解决问题。正如视觉是人类在自然环境与社会环境中生 存不可缺少的最重要感知器官，计算机视觉技术也是信息技术中的一门不可缺少盼技 术，越来越成为推动我国信息化进步的重要技术。 l 。i 影状识别技术简介 形状识别是计算机视觉和模式识别的一个基本问题，是任何高层视觉的关键。它被 应用到很多领域，如目标识别、基于内容的图像检索、文字识别、医疗诊断等。人们观 察周围环境时，首先注意到的是物体的颜色、纹理、形状等等，其中形状是物体最重要 的、最基本的有感官意义的特征之一。因此通过形状识别物体是计算机视觉中的基本问 题，也是热点问题。图1 1 为一般形状识别方法的框架图。 i 物体图像i 薹量i 二维图形 挲彰参数表莉 ， 一4 盏跟踪 乙 一躐。一黝 l 萋 颡别结果要拦鬟：描述鞠翟：变揍享蚓 图1 1 形状识别框架图 北方工业火学硕士学位论文 1 2 形状识别技术的研究现状与发展 在计算机视觉和模式识别中，形状是对目标范围的二值图像表示，可以看成是目标 的轮廓或边缘，它是用于目标识别的重要特征。为了节省存储空间、易于特征计算，需 要对形状作进一步的表示，这些表示通常分为： 编码方式：如链码、游程码、丘e e n l a i l 码等； 简化方式：如样条、插值、多项式、多边形逼近、特征点检测等； 骨架描述：中轴等。 形状识别就是根据形状特征来衡量物体间的相似性。在进行形状识别时需要处理各 种各样的形状变化，m 啪f i ) r d 1 】概括了一些引起变化的原因： 信号中噪声； 各种变换( 相似变换、仿射变换、射影变换、以及各种高阶变换) ； 遮挡( 自遮挡、互遮挡) ； 变形( 局部变形、全局变形) 。 图像系统中的噪声可以用信号处理的方法来处理。在传统计算机视觉中已经获得了 一些关于变换( 包括仿射变换，射影变换) 的结果。 1 3 形状识别技术的分类 关于形状识别方法的分类方法有很多，我们根据所采用的形状特征的不同大体分为 两类：一类是基于全局特征的，我们称之为全局方法；一类是基于结构特征的，我们称 为结构方法，也就是局部特征方法。 1 3 1 基于全局特征的形状匹配方法 形状识别中的全局方法主要是寻找一种不变量，我们希望所选取的全局特征对于旋 转、平移、尺度放缩等变换具有不变性，并且对起始点变化不敏感。下面主要从几何不 变量、矩和描述子方法进行分析。 几何不变量方法 在经典的几何理论中，主要的几何特征包括：面积、周长、长轴、短轴、主轴方 向、凹凸面积、紧密度、实心度、偏心率。紧密度是在一定程度上描述区域紧凑型的全 局性形状测度，当形状为圆时，紧密度为最小值1 。它是一个旋转、尺度、平移不变 量，又是一个非矢量的数值。区域形状的偏心率定义为它的主轴和次轴的比，它区分不 同宽度目标的能力比较强，长而窄的物体和短而宽的物体偏心率差别很大。当形状有一 2 - 北方工业大学硕士学位论文 个或多个明显的凸凹时，实心度就是一个非常有用的特征，可以刻画一个区域的凸凹 性。任意集合o 的凸壳h 就是包含集合o 的最小凸包。实心度定义为既在集合h 同时 也在集合o 中像素的数目的比例。实心的目标和空心的目标在实心率上差别很大。 矩方法 图像的矩函数在模式识别、目标分类中得到了广泛的应用。h u 2 】在1 9 6 1 年首先基 于代数不变量引入矩不变量。通过对几何矩的非线性组合，导出了一组具有平移、旋 转、尺度变化不变特性的矩，但是这种矩不能恢复图像。咄 3 】基于正交多项式提出 用正交矩来恢复形状，并且引入z e m i l ( e 矩，而且可以构建任意高阶的独立的矩不变 量。也有人 4 提出基于l e g e n d r e 多项式的i 启g e l 】d r e 正交矩。在文献 5 】中旋转矩保证了 高阶矩的幅度不随阶数的增加而明显降低，从而把矩定义扩展到了任意阶。复数矩是一 种获得矩不变量的简单而又直接的方法。矩方法的优点：它是一种简练的数学表示；缺 点：要建立起高阶矩和形状特征间的联系是困难的，另外它不能检测形状的局部特征。 描述子方法 人们喜欢将信号转换到变换域，分解成对于不同的频率或基来分析特征。作为经典 的变换方法，f o 谢e r 描述子、小波描述子、形态描述子在过去的几十年中得到了广泛的 研究。 f o u r i e r 描述子 f o 删e r 描述子( f d ) 是经典的形状描述方法。早在文献 6 】中就已给出f o 谢e r 描述 子的详细定义，后来p 蹦；c i o n 【7 】作了改进，该方法先用角累加函数表示形状边界，然后 对角累加函数进行f o 谢e r 变换，用得到的系数来描述形状，就是f o 嘶e r 描述子。在一 定条件下，它具有平移、旋转、大小、起点等不变性质。用f d 可以对2 d 曲线进行编 码、重建、或者分类。它的主要优点是易于实现，并且建立在f o 谢e r 分析的成熟理论 之上；缺点是f o 嘶e r 变换不提供局部形状信息，角累加函数的表示对噪声很敏感。 小波描述子 在很多计算机视觉应用中，为了改善准确率和提高对噪声的鲁棒性经常采用多分辨 率分析方法。形状的小波表示方式在粗尺度给出形状的全局信息，在细尺度上给出局部 信息，由于小波变换提供了多分辨率表示，因此匹配和识别可以根据输入图像或者目标 而灵活调整。小波变换的最大缺点就是依赖于目标曲线的起始点。即同一目标的两条不 同采样曲线的小波表示可能因为起始点的不同而有很大差异。在模式识别应用中，尽管 起始点可能会引起严重的问题，但是在文献中很少完全阐述过这个问题。c ! h l l a n g 和 k u o 8 】假定输入图像已经过校正，“和k u o 9 】通过简单的最小化曲线幅值函数的质心来 _ 3 北方工业人学硕十学位论文 获得起始点。t i 趾g 和b o l 妫【1 0 】使用小波系数的零交叉点来匹配模型和未知目标，他们 使用冗余小波变换，即非十进制小波变换来克服对起始点的依赖，由于非十进制小波表 示方法需要计算量很大，系数数目也非常大，所以用非十进制小波进行匹配非常慢。在 文献【ll 】中将形状先转换捌极坐标中，傲面嚣变换抽取谢e f 系数，然后对f o 谢嚣 系数的幅值抽取小波系数作为特征用于分类。文献【1 2 】介绍了一种判断起始点的方法， 从而保证了小波变换不受超始点约束。 近年来一组新的正交系v 系统进入人们的视野，它同时具有完备、正交和多分辨 率分析的特征。我们在此基础上经过研究和大量试验发现，v 描述予在描述和识别物体 形状方面有着特殊的优势，既继承了小波描述子的优点，并且对于起始点并不敏感。 形态描述子 基于形态学的形状描述方法近年来得到了广泛的研究，m 戤l g o s 首先提出了模式谱 的概念，s h j l l 和p u 【1 3 】拓展了c b u t s 泌和s c h o n f e l d 的工作，并且提出了另外一个称为 g 谱的谱变换。另一类方法是从形态协方差的概念中得出来的。b u i 1 4 】等使用几何相 关函数( g 臻e 醛c a lc 峨蕊艟两蕊。觳，g c f ) 表示二维形状，粼f 是基于形态褥方差 的。文献 1 4 】中使用o c f 进行形状描述和匹配。这种表示方法是旋转平移不变的，加上 预处理还可以获得尺度不变性。l 舢c “c 和d l h a w a l l 【1 5 】开发了一种称为形态特征变换 ( m o f 曲o l o 落蕊s i 罄稳瓣囊鑫n s 奴氆，m s t ) 的形状描述方法。醚s 零方法主要使焉基于 结构基元的多分辨率形态图像处理方法。这个方法试图把多分辨率图像处理和数学形态 学的优势相结合。m s t 形状表示方法把复杂的形状分解为多个简单的特征形状，然后 提取多个分解后的形状的特征，丽不是原始形状的特征。分解后的形状之所以被称为特 征形状，是因为在特征分解过程中，这垡特征形状保留了原始形状的信息。文献【1 6 】给 出了一种基于m r s 的形状匹配算法，并使用遗传算法来挑选一个优化的结构基元来计 算m s t 形状描述子。对于来自同一类的形状，这个被选中的次优结构基元可以给出很 好的分类结果。 1 3 2 基于局部特征的形状匹配方法 为了处理形变问题和遮掩问题，学者们提出很多基于形状局部特征的形状匹配算 法。这类方法主要是逶过搜索最优点对应和特征对应来判断形状是否匹配。他们的原始 雏形就是广义h o u 曲变换，而传统的动态规划等优化算法得到了广发的应用，现代优 化算法如神经网络、遗传算法的应用，使得许多有遮挡问题和变形问题得到解决。当今 解决形变问题最流行的方法是变形模扳。实际上形状也可看作一维随机信号，所以在语 音识别中褥到成功的许多算法也被广泛地应用到了形状匹配中，如动态时闻规整、隐 4 北方工业火学硕士学能论文 m 砌【o v 模型、自回归模型等。形状的凹凸结构也是决定形状的视觉特征，也受到了广 泛的关注。 广义h 佣曲变换( g 掰【i ) 珏陇曲首先提出了称为h 锄醇变换的区域乡 形边界变换的形状攒述方法，薹重垂 变换的目标是寻找一种从区域边界( 空间域) 到参数空间的变换，用大多数边界点所满 足的对应参数来描述这个区域的边界。文献 1 7 】提出了对于任意形状曲线的广义h o u g h 交换( g l 玎) 方法，并摊广了这一结栗，经典豹广义h 渊垂变换时抽取盏线和对魏：线 建模的传统方法。因为这类方法是基于投票数的累积，所以相对予噪声和遮掩不敏感。 实际上，如果噪声是加性噪声，如高斯囱噪声，广义h o u 曲变换可以通过模板匹配来 实现，相对予检测误差丽畜模板匹配是最优的。在复杂场景且外点很多的情况下，这些 方法对尺度变化处理效果不太理想。g h t 只考虑全髑匹配函数，动态规划则被广泛地 用于寻找对应点。 基于神经网络和遗传算法的匹配方法 衲经网络和遗传算法是近年发展起来的优化方法，被广泛应嗣于有遮掩形状的匹配 问题中，其中h o p 矗e l d 神经网络是形状匹配中最常用的。s o n 鲥e m a 和n a 璐撕【18 】先后 独立的提出了基于h 0 p f i e l d 神经网络的形状匹配方法，它在一定程度上解决了部分遮掩 闽题。y 删1 9 】等人提出了多层珏印垂l d d 蹲来进一步挖掘神经网络关于遮挡溽题的潜 力。r a 6 p a l f 2 0 】等人使用了多层感知网和索引的方法来匹配部分遮挡的形状。b e b i s 【2 1 】等 人用曲率尺度空间提取形状的特征点，并且把不同尺度下的特征点用b p 算法学潮，从 两融合了各个尺度下的信息。 变形模板 在计算机视觉中基于模板的形状匹配是个非常经典的问题。早期关于这个领域的研 究主要集中在刚体形状匹配，其中待匹配图像相对于模板图像只经过平移、旋转、尺度 变换和仿射变换，所有这些都可以通过相关匹配或嚣渊醢变换来获得。在大多数场 合，因为在图像处理中的变化和存在的类内差异，任何目标都没有一个严格的几何模型 可以利用，所以上述方法的应用十分有限。变形模板的概念几乎是随着w i d r o w 2 2 】的橡 皮模板和k s c l l l 露的弹性模板【2 3 】丽进入计算机视觉领域。因为变形模板能够发生变形 以匹配到显著的图像特征，是一个有力的形状匹配工具。 - 5 北方工业大学硕士学位论文 近些年计算机视觉界开展了很多关于变形模板的研究。变形模板在某种程度上解决 了一定的形变问题，开始受到人们的广泛关注。大体分为两类：囱由变形模板和参数化 变形模板。 自由式变形模板中最具代表性的是国圣涵s 【2 4 】等入提出的s 瀚l ( e 主动轮廓模型。后 来人们对此进行了改进并且提出了很多新的模型，例如主动轮廓线的气球模型 2 5 】、扩 张粘滞液体的正则化约束的变形模板 2 6 】等等。 参数化变形模板一般基予一定的先验知识，并且形状可以嗣少量参数表述的情况下 使用。一般有两种方法可以参数化形状和它的形变，解析形变模板【2 7 】和基于模型的变 形模板 2 8 】等。 比参数化变形模扳更加灵活的方法就是从原形中提取变形模扳，通过选取不同的原 形模板和变形过程，可以得到各种形式的模型譬9 】f 3 翊。人们在此基础上提出了各种各 样的模版，适用不同的情况。 基于形状凹凸结构的匹配方法 形状的凹凸结构是形状的一个非常重要的特征，人们已经将它广泛地应用于形状识 别中。m 觚灯和p a p 耐 3 1 】以及s “a n s 坝3 2 】等人首先描述了形状的凹凸结构。十年后 鼬m 3 3 定义了“面积特征”，并且证明了如果一个八连通区域满足“面积特征 就是 凸的。w 泌阳n 【3 4 】提出了一种描述简单块结构的凹凸表示方法。砥涮豳【3 5 】和l 耱g l e y 与c a ) o n d l 【3 6 】提出了学习结构描述子的算法。但是这些算法给出了一些大体的概念， 不能处理实际形状。c o r h l e l l 和b r a i d y 3 7 】改进了、聃n s t o n 的算法，提出了一种可以利用 形状先验知识的学习算法。se _ g 趿 3 8 】提出了一个学习非刚体形状的模型学习算法。但是 图模型的方法有很多缺点，学习和识别算法非常慢，并难子达到最优值【3 9 】。u 酣a 豳闲 等人提出了一种多尺度凹凸结构学习方法。r o n s e 4 1 关于这方面进行了综合描述。 动态规划 动态时闻规整在语音识别中获得了缀大的成功，r d s sm e 戳硼l 【鸵】应焉它来识别 s a r 图像。首先他们改进了轮廓的曲线表示方法，使之成为连续的曲线，然后设计了动 态规划标来简化动态规划的回归算法。h a n q i nl u 4 3 】改进了动态规划算法提出动态匹配 的概念，在匹配形状时，他们不断分裂合并形状的方向角函数。为了解决线性串匹配技 术对起始点的依赖性，m a c 提出了一种圆周串匹配技术用于多边形匹配。w u 【4 4 】等人提 出了一种两个阶段的串匹配技术，在第一阶段他们应用多边形匹配抽取一些特征点，用 这些特征点获得一个粗匹配，在第二个阶段对每条边进行细调。h a 妇jw o l 6 a n 【4 5 】也将 串匹配雳予有遮掩形状的匹配中，但是他们逯过寻找匹配最高的子串来确定起始点。 6 。 北方工业大学硕士学位论文 基于自回归模型和隐m a r k o v 模型 两维的形状可以用一维的实数或复数函数表示，把这个函数看成一个随机过程实 现，通过估计得到的模型参数就可以作为形状描述子。用自回归模型 4 6 分析闭合形状 是h y a p 和c ! 1 1 e l l a p p a 在1 9 8 1 年首先提出的，他们用自回归系数作特征矢量来刻画形 状。自回归模型的主要缺点就是它只使用一个预测参数集来描述整个形状，如果形状中 有很多角点或者形状变化非常剧烈，那么这个形状就变得难以预测。为此，h e 和 k i m d u 【4 7 】把a r 模型和隐m 矾【o v 模型结合起来用于形状分析，把形状边界分成若干 段，每一段用a r 模型描述，所得到的向量再用隐m a r k o v 模型分析。 骨架方法 中轴最早被应用于形状识别是在1 9 7 3 年，由b l u m 4 8 提出，很快得到人们的关 注。但是仅仅由中轴传递的信息远远不够，于是1 9 8 7 年l e y t o n 4 9 】提出了改进方法一 _ s h o c k 方法，也就是根据半径变化的奇点给中轴增加方向的信息。目前这两种方法得 到了广泛的应用，有大量的文献见诸于著名的学术期刊和会议 5 0 5 1 】，并且算法非常 实用，尤其对于三维空间中物体的识别和重构具有很重要的启示意义。 对称集方法最近几年开始受到人们的热切关注。随着研究的慢慢深入，人们发现基 于中轴的两种方法提供的信息量不能满足实际应用的需求，于是很自然的想到了中轴的 一个超集一对称集，中轴是对称集中的一个子集。对称集就是与形状轮廓相切于两个 或者更多点的圆心轨迹的闭包。1 9 8 5 年b r u c e 5 2 】从微分几何的角度对对称集进行了描 述。虽然对称集在数学上很容易表达，但是并不直观，为此人们提出了很多尝试方法在 其他空间中表示对称集，目前比较流行的有参数化对称集 5 3 和弦结构【5 4 的方法，但 是算法还不能达到实用的需求。 1 9 9 3 年，b 1 a 1 ( e 【5 5 在研究物体抓取过程中提出了反对称集的概念，从实用角度扩 展了对称集的概念，并且得到了很好的应用。2 0 0 6 年蹦j p e r 【5 6 】在第八届e c c i v 上发 表了一篇利用对称集和反对称集进行形状识别的文章，该方法取得了很好的效果。 对称集方法在三维空间的扩展遇到了很多麻烦，原因是存在大量的奇点，使得情况 非常复杂，有很多学者在这方面进行了尝试 5 7 5 8 】，取得了一定的结果，但是不够理 想。这个问题的解决需要利用奇点理论中分类的思想和对现实中对称性的总结等进行分 类，将复杂的情况细化。 - 7 - 北方_ t 业大学硕士学位论文 1 4 本文工作及论文大纲 本课题在总结了目前形状识别方面常用的方法和一些较为前沿方法的基础上，在两 个方面进行了研究，拓展了v 描述子和对称集描述子，通过试验验证发现它们具有一 定的应用价值。 在变换域方法的基础上提出了一类新的v 描述子，对二维图形进行v 变换提取形 状信息，定义归一化后的变换系数为描述子，具有旋转、平移、放缩不变性，并通过形 状主方向在一定程度上消除了起始点的影响。通过快速v 变换可以快速、有效地计算 出v 描述子，并且采用了加权欧氏距离，充分利用了v 描述子的多分辨率分析特性， 对轻微遮挡具有一定的抵抗力，可以根据实际情况达到较好的识别。 在学习奇点理论中对称集概念的基础上，提出了一类与对称集和反对称集密切相关 的形状描述子。通过形状上具有相互对称性的点的几何性质产生一个二值的内积图表， 这个图表的拓扑结构的变化同中轴、对称集和反对称集的变化密切相关。物体形状的变 化引起对称集和反对称集结构的变化，从而引起内积图表的变化。文章中通过三角域上 w a l s h 函数来重新表示内积图表的上三角矩阵，得到一些系数，我们将这些系数定义为 描述子。通过对比不同类形状，其中包括一些遮挡或者被加噪的图形，得到理想的结 果，验证了该描述子具有旋转、平移、放缩不变性，并且对起始点不敏感，尤其是对轻 微遮挡具有较好的抵抗性。 8 - 北方工业大学硕士学位论文 第二章基于变换域的形状识别技术 2 1 正交函数系的基本知识 当今的时代是一个信息化的时代，是一个飞速发展的时代，现实中的许多实际问题 都与数学分不开，都可以用相关的数学知识解决。正交函数系统是数学的一个重要组成 部分，作为强有力的数学工具，其应用领域极其广泛，涉及信号处理、工程计算、频谱 分析、回归分析、遥测技术、信息技术及图形图像处理等方面，具有很好的应用前景。 正交函数的研究历史悠久，积累了丰富多彩的成果 5 9 6 2 ，这给我们以后的研究 工作提供了有利的参照条件。人们熟知的f o u r i e r 三角函数系、多项式正交系，已成为 频谱分析与工程计算不可或缺的主流工具，而且在电信工程、信息论、线性系统论、通 讯、电视等方面都有了很好地应用和发展。相对于高光滑性的正交函数系而言，具有高 间断性的正交函数系- w a1 s h 函数、h a a r 函数的研究，其热潮出现在二十世纪七、八 十年代，人们把w a l s h 函数应用到信号处理，取得实效；与w a l s h 函数等价的h a a r 函 数，则成为小波变换成为典型的波函数代表，得以普遍应用 6 3 6 4 。从而，以w a l s h 函 数、h a a r 函数为代表的具有高间断性的j 下交函数系，从原来数学上被认为仅仅是反例 ( c o u n t e re x 锄p l e ) 与“怪物 ( m o n s t e r ) 的地位，变成数字信号处理的强有力的数学 工具。 正交函数系就是由一系列正交基构成的一个正交系统。我们比较熟悉的正交函数系 有f o u r i e r 三角函数系、正交多项式系、w a l s h 函数系、h a a r 函数系等。本章按照正交 函数系的不同，来分别介绍着几种典型的函数系。 2 1 1 傅立叶三角函数系 傅立叶三角函数系的定义： 在物理学中，最简单的波是简谐振动产生的波，简称谐波，数学上表示为： 彳s i n ( 刃+ 缈) ( 3 1 ) 经分析，周期性波一般都可以用一系列谐波的叠加表示为： 鲁+ 窆( 口。c 。s h + 仇s i n h ) ( 3 2 ) 二 七= l 9 - 北方丁业大学硕士学位论文 一般称有限个谐波的叠加为三角多项式，无穷多个谐波的叠加就构成一个三角级 数，其表达式为： 等+ ( 口。c o s 缸+ 6 。s i n 缸) ( 3 3 ) 厶 一；1 由于法国数学家z 励盯，盯对三角级数曾做过较系统的研究，并得出了一些深刻的 结论，为纪念他，后人就把由某一函数展开成的三角级数称为傅立叶级数 三角函数系是指： 1 ，c o s x ，s i n x ，c o s 2 x ，s i n 2 工，c o s 腑，s i n 珊，) ，并称三角函数 系 1 ，c o s 煅，s i i l 册) 田- 。是 一万，万 上的正交函数系，也称为乃洲盯三角函数系。 傅立叶三角函数系的性质： ( 1 ) 任两个不同函数的积在 一万，万】上的积分为零。 ( 2 ) 任一个函数的平方在卜万，万】上的积分不为零。 这两条性质就是傅立叶三角函数系的正交性。 2 1 2 正交多项式函数系 正交多项式相关理论是经典分析中的一个既古老而又十分重要的分支，它一直被看 作是正交多项式的一个重要起源。 正交多项式的定义： 若厂( 工) ，g ( 石) c 【口，6 】，p ( 工) 为 口，6 】上的权函数且满足： 6 ( 厂( x ) ，g ( z ) ) = p ( 石) 厂( x ) g ( x ) 出= o ( 3 4 ) 则称厂( x ) 与g ( 石) 在 以，6 】上带权夕( x ) 正交。 设帆( 石) 是 口，6 】上首项系数口。o 的n 次多项式，p ( 石) 为【口，6 】上权函数，如果多 项式序列缈。( 石) ) ；满足关系式： c 晰，= 如州州出= z 篡“ 慨5 ， 则称为多项式序列缈。( x ) ) ；为在【口，6 上带权p ( x ) 正交，称1 i ，。( x ) 为 口，6 上带权 p ( x ) 的n 次多项式。 1 0 北方工业人学硕士学位论文 若首项系数o 的托次多项式纯，满足 ( 纺，依) = ep ( 功纺( 力饩( 矽d x = 羔 。；三乏 ( _ ，后= o ，l ，) ( 3 6 ) ( 注：若4 = 1 ，则为标准正交函数系) ，就称多项式序列，仍，纯，在 口，6 】上带权p ( z ) 正交，并称缈。( 石) 是 口，6 】上带权p ( 石) 的n 次正交多项式。 正交多项式的应用： 常见的正交多项式有勒让德多项式、切比雪夫多项式、拉盖尔多项式和埃尔米特多 项式。正交多项式的应用也是非常广泛的，可以用于回归分析【5 7 】、概率密度嘲】、精馏 塔静态仿真、谐波估计、对测试系统进行静态标定等方面。 2 1 3u 、v 正交函数系 1 9 8 3 年齐东旭和冯玉瑜建立了一类正交完备函数系 6 5 ，它由一系列k 次的分段多 项式组成，命名为k 次u 系统，k = 0 ，1 ，2 ，。这个函数系的组成既含有光滑性强的函 数，又含有各个层次的间断函数。w a l s h 函数就是u 系统在k = o 时的特例。u 系统在几 何图组形状分类识别、数字水印等方面具有较好的应用 6 6 。 2 0 0 5 年宋瑞霞提出了和u 系统紧密相联的另一类正交完备函数系，它也由分段k 次 多项式组成，取名为k 次v 系统 6 7 。在k = 0 时v 系统就是h a a r 函数系。v 系统不仅 完备正交并且具有多分辨率分析的特性，在形状识别方面也具有很好的应用。 2 2 v 描述子的定义与陛质 形状识别是模式识别中的一个基本问题，也是一个重要问题，广泛应用于图像分 析、计算机视觉和目标识别等应用领域。人类可以很容易的识别物体的形状，但是对于 计算机来说，自动识别任意物体的形状却相当困难。当形状发生平移、旋转、放缩、遮 挡后，使计算机快速、准确的识别物体的形状仍然是一件相当困难的事情。 描述子方法作为经典而实用的方法向来受到人们的关注，主要包括傅立叶描述子 【6 8 】、小波描述子 6 9 】、形态描述子 7 0 等。傅立叶描述子基于成熟的傅立叶分析理论得 到广泛应用，傅立叶变换的核心技术是关于正交函数系，正交函数系在图像处理中是非 常重要的工具。 通过研究发现，我们提出了一类改进的归一化v 描述子。对形状进行多边形近似表 示，消除冗余点和减少运算量，通过形状主方向消除了起始点的影响，利用快速v 变换 北方工业人学硕士学位论文 提高运算效率，通过加权距离有效地利用了v 变换的多分辨率分析的特性，算法速度 快、准确率高，具有一定的实用价值。 2 2 1 多边形近似与形状主方向 对任意给定的形状，一般用逆时针排列的像素点坐标p 。，p 。，p 来描述物体 的形状( 其中风= p ) 。为了去除冗余数据点减少运算量和消除噪声影响，在给定近 似精度d 的条件下，我们对形状做进一步表示，用数字曲线的多边形近似算法提取边界 特征点作为原始形状的近似表示 7 卜7 2 ，如图所示： 焱 ( a ) 图像分割 ( b ) 轮瘸跟踪后t c i 近 | ；c 届多j 形和 后的物体的形状边界形状书方向9 的确定 图i 形状边界的多边形近似及形状主方向的确定 通常近似后多边形的顶点数目n 为原始形状的结点数，可以大大减少形状边界信息 的存储量并降低v 变换的运算量。本文采用c h e n 和s u 的多边形近似算法 7 1 ，原理是 提取曲线上局部区域的最大曲率点作为近似多边形的特征点。 起始点对于形状识别具有一定的影响，但是很少有作者涉及这个方面的问题。一般 情况下都假定形状经过校正，并且选取相同的起始点。本文利用形状主方向矽消除了起 始点的影响。 形状主方向由物体的形状特征决定，位于过质心且倾角为的直线上，方向指向能 量较小的部分。是具有最大特征值的特征矢量的方向( 即物体最适椭圆的长轴方向) ： ：t 如一- ! 丝二丝地丝二型：垡， 2 “i l 关于方向的选取，本文采用了一种比较实用的方法，将形状顺时针旋转角度 一，然后由形状的三阶矩决定，见下式： 缈：p 坳， 0 ， 【 ， “3 0 o 1 2 北方工业大学硕士学位论文 其原理是比较形状工 0 与x 0 两部分的能量，选取能量小的部分对应得方向作为 形状的主方向。其中，“2 0 、掰0 2 、“l l 、“3 0 为所围区域的p + g 阶中心矩。 本文利用j 2 g l e u 的方法 7 3 ，由近似多边形的顶点快速计算出形状所围区域的 p + g 阶中心矩。该算法的原理是计算多边形每一条边与原点所围三角形区域的p + g 阶 中心矩，然后通过符号相加得到整个区域的p + g 阶中心矩。该算法仅与多边形的结点 数目有关，而与形状面积无关。由于物体形状的近似多边形的顶点数目很少，因此计算 形状区域矩的速度很快。 定义：设连续二值图像的p + g 阶几何矩为肌朋，p + g 阶中心矩为“胛， 赚 朋朋= e e 工，y 9 m ，y ) 螂 ”月2ll 一c ，) p ( j ，一c y ) 4 ( x ，y ) 螂 其中( c ，c ，) 为形状的质心，并且巳：盟，c ，：竺堕。 研聊 首先起始点的选取不影响最后矩的结果，其次由于平移不变性，可以选取坐标系使 得多边形位于第一象限，并且原点在每条边的左下方。 如下图所示， 把近似多边形的每个顶点与原点连接，这样任意两个相邻的顶点与坐标原点构成一 个三角形。记( 工，少，) 、( 石，+ l ，y 州) 和原点构成的三角形为乃。如( 而，y 。) 、( 而，少2 ) 和原 点构成的三角形为互。先计算每个互的p + g 阶中心矩，然后通过符号相加得到整个区 域的p + g 阶中心矩。 1 3 北方工业大学硕士学位论文 “= “艄s 柳( f ) f = l 下面来计算每个小三角形的p + g 阶中心矩，如图所示： 设三角形的顶点为( 口，6 ) 、( c ，d ) 和( 0 ，0 ) ，其中以c 。过( 口，6 ) ( c ，d ) 分别向z 轴作 垂线，交点为( 口，o ) 和( c ，o ) 。这样形成三个区域： 区域一：由( 0 ，0 ) 、( 口，6 ) 和( 口，0 ) 构成的三角形； 区域二：由( 口，6 ) 、( c ，d ) 、( 口，o ) 和( c ，0 ) 构成的梯形； 区域三：由( o ，0 ) 、( c ，d ) 和( c ，0 ) 构成的三角形。 设三角形的p + g 阶矩为小朋r ，区域一的p + g 阶矩为，l 胛 l ，区域二的p + g 阶矩 为肌朋2 ，区域三的p + g 阶矩为m 用，3 ，则： m 用，7 2 ，z 舟，l + 所j 口口，2 一所朋3 由三角形的p + 留阶矩可以方便的计算出三角形p + g 阶中心矩，例如： 聊函7 h 0 2 r2 ； 聊o o r 聊品r h 2 0 r5 。 m o o r 下面来定义每个三角形的符号值： 1 4 北方工业人学硕七学位论文 如图所示，假设相邻俩点为( ，y ，) 、( x 州，y 川) ，( ，咒) 与( 0 ，0 ) 的直线和石轴的夹 角为幺，( h 。，y m ) 与( o ，o ) 的直线和x 轴的夹角为b 。 用数学公式表达为： j f j 吵( f ) = + lt 锄一l 丝t a i l l 垃， tx ，+ l 2 2 2 快速v 变换 通过形状的多边形近似表示后，我们对近似多边形进行连续快速v 变换，即对各条 直线段进行连续的v 变换。记结点数为n ，顶点的坐标为( x 。，y 。) ，f ：表示多边形的 顶点到起点昂间的边长和l 为多边形的周长。为了方便计算，我们将多边形区间与 【o ，l 】作一映射，令f 。= f ：三。 记形状曲线为只，p ( f ) = x ( f ) + 耖( f ) = _ ( f ) + f 彬_ ( f ) j 卸j 卸 其中形= fz ( f ) y - ，( f ) 以，旯；= f 少( f ) ，( f ) 班，记五( _ ，) = + f 衫，称 名( ) 为尸( f ) 的第，个v 描述子。 对于k 次v 系统，我们可以用k 次多项式进行表示， 即( f ) = 口：f + 口土l f - 1 + + 口i ，f + 口；， 下面我们以一次v 系统为例， 1 5 北方工业人学硕士学位论文 砧：( x ) = 再【4 ，一3 2 n z ) ， 矛( 2 一x 一4 ，+ 1 ) ， o ， 曙? o ) = 州导，等， 州等舌， 其它 庐( - 3 2 州破x 售，等) 厅( 州- 3 2 州力，州等舌) o 其它 e 襄豪口赡 蛰勺毪。 b 咬= 岁脚舀v ：霉 对任意排列好( f ) ，由v 系统的图像及公式知，存在尼。，露2 ，后3 使得 o ，1 】区间 上y 以) 在阮，后：) 和陆：，屯) 上分别为单调非零函数，其余部分为零，其中 尼2 = ( 毛+ 尼：) 2 。对每一个经过多边形近似的形状，存在三个点，刀：，甩3 使得 f m 七l f m + l f 月2 七2 f h 2 + l f 码七3 f 一+ i 。 则积分分为四部分， 【0 ，毛) 和陆，1 ) 区间，由于( f ) 为o ，故积分为零； k 。，七：) 区间积分可求，且_ ( f ) 单调，记为0 ( f ) = 口+ 口于 k ：，后，) 区间积分可求，且匕( f ) 单调，记为巧( f ) = 口i ，：f + 口乎 则， 兄( ) = fp ( f ) 巧( f ) 出= 【f 2p ( f ) l ( f ) 出+ e p ( f ) 巧( f ) 出】 - rp ( f 蹦触+ 。姜。p 佻) 出+ 肌蹦触 - 1 6 北方工业大学硕士学位论文 + f 即蹦仳+