形状匹配综述

　第 27 卷　第 5 期2001 年 9 月 自　动　化　学　报 A CTA AU TOM A T ICA S IN ICA V o l127,N o15 Sep t. , 2001 综述与评论 形状匹配综述 丁险峰1　　吴　洪1　　张宏江2　　马颂德1 1 (中国科学院自动化研究所模式识别国家重点实验室　北京　100080) 2 (微软中国研究院　北京　100080) (E2m ail: hw u@nlp r. ia. ac. cn) 摘　要　本文对形状匹配的方法进行了回顾. 介绍了一些形状表示方法, 其中主要是形状简化 的方法. 形状匹配的方法可以分为基于各种变换不变量的形状匹配方法和基于局部特征的形状 匹配方法, 并根据这一分类介绍了很多有代表性的匹配方法. 关键词　形状匹配, 形状简化, 模式识别, 变形模板. 收稿日期　2000203215　　收修改稿日期　　2000206225 REV IEW ON SHAPE M ATCH ING D IN G X ian2Feng1　W U Hong1　ZHAN G Hong2J iang2　M A Song2D e1 1 ( Institu te of A u tom ation, Ch inese A cad emy of S ciences, B eij ing　100080) 2 (M icrosof t R esearch Ch ina, B eij ing　100080) (E2m ail: hw u@nlp r. ia. ac. cn) Abstract　T h is paper p rovides a review of shape m atch ing m ethods. Som e shape rep2 resen tat ion m ethods are p resen ted, m ain ly the shape simp lificat ion m ethods. Shape m atch ing m ethods can be classified in to two group s, m atch ing by k inds of invarian ts and m atch ing by local featu res, and acco rding to types, an overview of the mo st rep ren tat ive m ethods is p resen ted. Key words　Shape m atch ing, shape simp lificat ion, pat tern recognit ion, defo rm able model. 1　引言 形状匹配是计算机视觉和模式识别的一个基本问题, 它被应用到很多领域, 如目标识 别、基于的图像检索、文字识别、医疗诊断等. 在过去的几十年中, 人们研究和开发了很 多形状匹配算法, 每种算法各有其优点和缺陷, 将这些方法和归类就变得十分重要了. 本文介绍了形状匹配的基本概念和一些有代表性的形状匹配方法, 希望对读者进一步的研 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 究工作有帮助. 2　形状匹配的基本概念 当观察周围环境时, 人们首先注意到的是物体及其周围环境的颜色、纹理、形状和空间 关系等等, 形状是物体最基本的有感觉意义的特征之一. 在计算机视觉和模式识别中, 形状 是对目标范围的二值图像表示, 可以看成是目标的轮廓, 它是用于目标识别的重要特征. 为 了节省存储空间、易于特征计算, 需要对形状作进一步的表示, 这些表示通常可以分为两类: 编码方式, 如链码、游程码、freem an 码等; 简化方式, 如样条 (B 样条, 3 次, 5 次样条)、插值、 多项式、多边形逼近、和特征点检测等. 另外还可以使用形状的骨架来描述形状, 由于篇幅所 限, 本文对此不做介绍, 感兴趣的读者可参见文献[1～ 3 ]. 形状描述是通过一些方法生成数值的描述子来描述形状, 描述子应在尽可能区别不 同目标的基础上对目标的平移、旋转和尺度变化不敏感. 下面列出了一些常用的形状描 述子. 1) 基于几何特征: 紧密度、实心度、偏心率、不规则度等; 2) 基于统计特征: 粗糙度、均值、方差等; 3) 变换域特征: 矩、Fou rier 描绘子、小波描绘子、形态描绘子等; 4) 仿射不变量: 简比等; 5) 射影不变量: 交比等. 形状匹配就是通过按一定的度量准则来衡量形状间的相似性. 在进行形状匹配时必须 处理各种各样的形状变化. M um fo rd [ 4 ]概括了一些引起变化的原因 1) 成像系统中的噪声; 　　2) 成像系统中的不同视角引起的变化; 3) 部分遮掩, 包括自遮掩和互遮掩; 　　4) 一个目标各部分的连接运动(如: 人的四肢) ; 5)“软”物体所具有的复杂的运动 (如: 衣服) ; 6) 同类对象间的变化. 这些原因的表述可以概括为计算机视觉的术语: 信号中的噪声; 各种变换 (相似变换, 仿 射变换, 射影变换, 以及各种高阶变换) ; 遮挡 (自遮挡, 互遮挡) ; 变形 (局部变形和全局变 形). 显然, 图像系统中的噪声可以用信号处理的方法来处理. 在传统计算机视觉中已经获得 了许多很好的关于变换 (包括仿射变换、射影变换)的结果. 最近十年中变形模板受到了很大 的关注, 在一定情形下获得了很多良好的结果, 本文对此做了较详细的介绍. 人们对有遮掩 情况下的形状匹配进行了大量实验, 但由于该问题的本质是病态的, 所以在目前的方法框架 下, 如果没有额外的先验知识, 人们是无法处理很严重的遮掩问题的. 形状匹配可以根据不同标准进行分类, 如: 形状匹配是基于形状的边界还是内部. 本文 根据匹配方法处理形变的能力将形状匹配方法分为两大类. 一类只能处理各种变换引起的 形状变化, 它们通过搜索在不同变换下的不变量: 1) 相似不变量——距离、矩、角度、圆度、Fou rier 描述子; 2) 仿射不变量——简比、弧长、包围面积、改进型 Fou rier 描绘子; 3) 透视不变量——交比及其延伸. 另一类方法可以处理更加复杂的形变, 它们通过寻找目标和模型之间局部特征的对应来使 9765 期 　丁险峰等: 形状匹配综述 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 得匹配误差最小. 为了获得最小值, 人们使用了很多方法, 诸如广义Hough 变换[ 5, 6 ]、动态规 划[ 7～ 9 ]、神经网络[ 10, 11 ]、变形模板[ 12～ 16 ]、遗传算法[ 17 ]、以及解析方法[ 18 ]等. 3　形状表示 本文讨论的形状表示方法分为两类, 一类是编码方式, 一类是对轮廓的简化表示形式. 简化轮廓就是提取一些重要的有意义的关键点. 当今两大最流行的曲线近似方法是多边形 近似和样条近似, 另外基于多尺度的特征点提取在最近二十年中得到了密切的关注和 研究. 3. 1　链码 链码是一种非常常见的形状表示方式, 它不能简化形状, 但是能有效的表示形状. 用链 码表示形状是 F reem an [ 19 ]在 1961 年引入的, 并且推广了原来的定义获得了广义链码[ 20 ]. F reem an [ 21 ]还利用链码来抽取关键点从而生成一种相对于平移、旋转、尺度不变的旋转表示 方法, 他还总结了链码的各种方法与算法[ 22 ]. 链码在第二代图像编码[ 23 ]中获得了广泛的应 用. Ro senfeld [ 24 ]也提出了一系列关于链码的算法. 人们利用链码来计算各种不同形状特 征[ 25 ] , 轮廓平滑和相关也因此变得简单了, F isch ler [ 26 ]用它来检测关键点,M cKee [ 27 ]甚至利 用链码来识别目标. 3. 2　样条 样条曾经在函数插值和曲线近似方面是非常流行的. Ikebe 和M iyam o to 在文献[28 ]中 详尽的描述了样条在形状、表示和恢复上的应用. 关于样条的数学描述可以参考文献 [ 29 ], 样条在计算机图形学中应用可以参考文献[30 ]. 样条有最小化曲率的优点, 也就是用 最小平均曲率的曲线近似给定的函数曲线. 样条函数在插值问题上的缺点是局部函数值的 修改会影响整个样条表示. B 样条的提出就是为了不将局部函数值的改变传播到其它间隔 中去. 它也可以用作由参数方程确定的平面曲线间的插值, 这样每一条参数方程都可以独立 插值. Cohen [ 31 ]等人提出了一种基于B 样条的曲线表示和匹配方法. IBM A lm aden 研究中 心QB IC 研究小组, 提出了基于伪正交样条基和最小均方误差的曲线拟合方法[ 32 ]. Sa in t2 M arc[ 33 ]等人使用四次B 样条表示形状, 并且由此判断形状的对称性. H annu O lkkonen [ 34 ]提 出了离散B 样条. L. A. Ferrari[ 35 ]等人实现了广义B 样条的快速算法. M ichael U n ser [ 36 ]提 出了快速B 样条变换. 基于多项式的形状简化方法也得到了广泛的应用, 很多工作使用隐多项式来表示形状, 然后用代数或几何不变量来识别形状. 开始时隐多项式被用来描述三维光滑曲面的仿射不 变量[ 37 ]. G. T aub in 开创性的概括了关于如何利用隐多项式提取形状特征的关键技术. 当 这些特征值和另一条曲线的特征值相匹配时, 就确定了一个“内蕴参考帧”, 两条曲线的多项 式系数可在这个参考帧下比较. 文献[38 ]提出了基于二次因子的新的因式分解的方法, 从而 解决了曲线之间的关键点对应问题. D an iel Keren 等人[ 39 ]提出了高次隐多项式的概念, 增 强了隐多项式描述复杂形状的能力. 因为正交多项式不能提供平移、旋转、尺度不变量, 所以 Xu 等人[ 40 ]提出了广义正交多项式, 获得了相似变换不变量. 实际上用其他函数拟合曲线的 方法还有很多, 如文献[41 ]就使用了高斯函数拟合曲线. 086 自　　动　　化　　学　　报　 27 卷 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 插值既可以简化形状, 也可以增加形状的边缘点数, 从而达到调整数据的目的. 插值一 般可以分成如下几大类: 基于 FFT 的插值、最近邻插值、样条插值、线性插值等. 插值是几何 学的经典理论, 读者可参看有关几何书籍[ 42 ]. 3. 3　多边形逼近 多边形逼近是用多边形线段来近似形状边缘, 即: 是以最小误差、最小多边形周长、最小 多边形内部面积, 或最小多边形外部面积作为近似准则. 这些误差度量中最常用的是最大误 差和平方积分误差. 这类方法中最常用的是分裂和合并法[ 43 ]. 在这个方法中, 曲线分裂由几 个线段来表示直到误差达到可以接受. 同时分裂的线段又有可能融合, 如果融合后的线段同 原始曲线的误差在允许的最大误差范围内, 线段即融合. Pavlid is[ 44 ]使用平方和误差函数的 偏导数来引导牛顿法搜索最佳断点. W u 和L eou 提出了另一种不同的准则来获取多边形逼 近, 他们使用的多边形逼近准则是最大内部面积、最小外部面积、最小面积偏差. Bengtsson 和 Ek lundh [ 45 ]提出了一种层次化的多边形逼近方法. 分裂合并方法经常用于多边形逼近, 尺度空间的方法[ 46 ]则常常用于跟踪曲线上的特征点. 不随尺度变化的特征才是稳定的形状 特征. W ithk in 使用多项式近似来估计边缘点上的切线方向, 从而生成了曲线的多尺度表 示. Chung [ 47 ]等人开发了一种基于 Hopfield 神经网络的形状多边形逼近方法. 这种方法是 将多边形逼近定义为对神经网络能量函数的最小化问题, 就是最小化曲线和多边形的弧与 弦之间的偏差. 3. 4　基于尺度空间特征点提取技术 基于尺度空间的特征点提取方法是一种流行的形状简化方法. 最常用的尺度空间主要 有: 高斯尺度空间、小波尺度空间、形态尺度空间. 另外 Schw arz[ 48 ]尺度空间也是值得注 意的. W itk in [ 46 ]提出的基于 Guassian 尺度空间表示突出目标特征的方法, 通过跟踪不同尺度 下特征点的位置而给出形状的简化形式, 依然存在于简化表示形式中的特征点被认为是目 标显著的特征. Babaud [ 49 ]等人证明了 Gau ssian 核是唯一的线性核, 具有非常良好的保留本 征特征点的特性, 当尺度增加时, 即滤波器带宽增加时, 那些本征特征点依然存在. Gau ssian 滤波器是唯一具有这一特性的滤波器. A sada 和B rady [ 50 ]基于M arr 提出的想法提出了一种 称为曲率指纹图的新方法, 轮廓经过不同带宽的 Gau ssian 滤波器滤波从而获得形状边缘的 多尺度表示, 然后在不同尺度计算曲率并且获得曲率指纹图. M okh tarian 和M ackw o rth [ 51 ] 将尺度空间的方法应用到形状描述子中, 沿着形状的轮廓, 用不同带宽的 Gau ssian 核来平 滑轮廓, 然后计算曲率. 曲率函数在尺度空间中的图像被用作形状多层描述子, 它具有平移、 旋转、尺度不变性. 多尺度的概念在形态学中也提出过. 基于形态学的形状简化方法主要分为两大类, 一类是 形态分解, 另一类是形态细化. Cheng 和 Yan [ 52 ]使用可变尺寸的结构基元对图像进行各种形 态操作. A nelli[ 53 ]等人运用了遗传算法, 并且试图解决结构基元的选择问题. L agan iere [ 54 ]则成 功使用形态分解提取了角点. M o isan [ 55 ]提出的仿射形态尺度空间, 并且用仿射腐蚀来简化 形状. R einhard t [ 56 ]等人比较了形态分解和形态细化之间的差别. 相对于四种不同的代价函 数, 形态分解的效率比形态细化的效率高四倍. 基于小波尺度空间的形状简化方法和高斯尺度空间的原理一样, 对曲线进行不同尺度 1865 期 　丁险峰等: 形状匹配综述 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 的滤波. 不同之处在于小波尺度空间不是线性尺度空间, 因此它无法保证因果性, 所以经常 会出现奇异的角点, 因而得不到广泛的应用. Schw arz 尺度空间[ 48 ]近年来也受到了关注, 虽然不是线性尺度空间, 但它的卷积和类似 高斯核可以在频域中进行操作, 因而速度非常快. 尤其值得一提的是它的内在几何度量表征 了不同程度的光滑度, 因而在尺度的自动选取方面有其优势. 4　基于各种不变量的形状匹配方法 在几何学和拓扑理论中, 给出了很多关于各种变换的结果, 据此人们提出了许多处理各 种变换的不变量. 4. 1　基于全局性几何特征 在经典的几何理论中, 面积、周长、长轴、短轴、主轴方向、凹凸面积、紧密度、实心度、偏 心率这些特征得到了广泛的应用[ 57 ]. 在此简单介绍紧密度、实心度、偏心率. 紧密度是在一 定程度上描述区域紧凑型的全局性形状测度, 当形状为圆时, 紧密度为最小值 1. 它是一个 旋转、尺度、平移不变量, 又是一个非矢量的数值. 区域形状的偏心率定义为它的主轴和次轴 的比, 它区分不同宽度目标的能力比较强, 长而窄的物体和短而宽的物体偏心率差别很大. 当形状有一个或多个明显的凸凹时, 实心度就是一个非常有用的特征, 可以刻划一个区域的 凸凹性. 任意集合O 的凸壳H 就是包含集合O 的最小凸包. 实心度定义为在 H 同时也在 集合O 中像素的数目的比例. 实心的目标和空心的目标在实心率上差别很大. 4. 2　基于变换域特征 人们喜欢将信号转换到变换域, 分解成对于不同的频率或基来分析特征. 作为最经典的 变换方法, 有各种不同的矩和 Fou rier 描绘子, 小波描绘子、形态描绘子在过去的二十年中 得到了广泛的研究. 4. 2. 1　矩 图像的矩函数在模式识别、目标分类中得到了广泛的应用. H u [ 58 ]在 1961 年首先基于代 数不变量引入矩不变量. 通过对几何矩的非线性组合, 导出了一组对于图像平移、旋转、尺度 变化不变的矩, 但是这种矩不能恢复图像. T egue [ 59 ]基于正交多项式提出用正交矩来恢复形 状, 并且引入 Zern ike 矩, 而且可以构建任意高阶的独立的矩不变量. 也有人[ 60 ]提出基于 L egendre 多项式的L egendre 正交矩. 在文献 [ 61 ]中旋转矩保证了高阶矩的幅度不随着阶 数的增加而明显降低, 从而把矩的定义扩展到了任意阶. 复数矩是一种获得矩不变量的简单 而又直接的方法. 矩方法的优点即: 它是一种简练的数学表示; 缺点是要建立起高阶矩和形 状特征间的联系是困难的, 另外它不能检测形状的局部特征. 4. 2. 2　Fou rier 描绘子 Fou rier 描绘子 (FD )是经典的形状描述方法. 早在文献[62 ]中就已给出 Fou rier 描绘子 的详细定义, 后来 Persoon [ 63 ]作了改进. 该方法先用角累加函数表示形状边界, 然后对角累 加函数进行 Fou rier 变换, 用得到的系数来描述形状, 就是 Fou rier 描述子. 在一定条件[ 62 ] 下, 它具有位移、旋转、大小、起点等不变性质. 用 FD 可以对 22D 曲线进行编码、重建、或者 分类. 它的主要优点是易于实现, 并且建立在 Fou rier 分析的成熟理论之上; 缺点是 Fou rier 286 自　　动　　化　　学　　报　 27 卷 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 变换不提供局部形状信息, 角累加函数的表示对噪声很敏感. 4. 2. 3　小波描绘子 在很多计算机视觉应用中, 为了改善准确率和提高对噪声的鲁棒性经常采用多分辨率 分析方法. 形状的小波表示方式在粗尺度给出形状的全局信息, 在细尺度上给出局部信息. 由于小波变换提供了多分辨率表示, 因此匹配或识别可以根据输入图像或者目标而灵活调 整. 小波变换的最大缺点就是依赖于目标曲线的起始点. 也就是说, 同一目标的两条不同采 样曲线的小波表示可能因为起始点的不同而有很大差异. 在模式识别应用中, 尽管起始点可 能会引起严重的问题, 但是在任何文献中都没有完全阐述过这个问题. Chuang 和 Kuo [ 64 ]假 定输入图像已经经过校正,L i 和 Kuo [ 65 ]通过简单的最小化曲线幅值函数的质心来获得起始 点. T ieng 和Bo les[ 66 ]使用小波系数的零交叉点来匹配模型和未知目标. 他们使用冗余小波 变换, 即非十进小波变换来克服对起始点的依赖. 由于非十进小波表示方法需要的计算量很 大, 系数的数目也非常大, 所以用非十进小波进行形状匹配非常慢. 在文献[ 67 ]中将形状先 转换到极坐标中, 作 Fou rier 变换抽取 Fou rier 系数, 然后对 Fou rier 系数的幅值抽取小波系 数作为特征用于分类. 文献[68 ]介绍了一种判断起始点的方法, 从而保证了小波变换不受起 点约束. 章毓晋教授等人[ 69 ]研究了小波描绘子在图像查询中的应用. 4. 2. 4　形态描绘子 最近十年, 基于形态学的形状描述方法得到了广泛的研究. M arago s 首先提出了模式谱 的概念, Sh ih 和 Pu [ 70 ] 拓展了 Gou tsias 和 Schonfeld 的工作, 并且提出了另外一种称为 G2谱的谱变换. 另一类方法是从形态协方差的概念中得出来的. L ou i[ 71 ]等使用几何相关函 数 (Geom etrica l Co rrela t ion Funct ion, GCF) 表示二维形状. GCF 是基于形态协方差的. 文 献 [71 ]也使用 GCF 进行形状描述和匹配. 这种表示方法是旋转平移不变的, 加上预处理还 可以获得尺度不变性. L oncaric 和D haw an [ 72 ]开发了一种称为形态特征变换 (M o rpho log ica l Signa tu re T ran sfo rm ,M ST ) 的形状描述方法. M ST 方法主要使用基于结构基元的多分辨 率形态图像处理方法. 这个方法试图把多分辨率图像处理和数学形态学的优势相结合. M ST 形状表示方法把复杂的形状分解为多个简单的特征形状, 然后提取多个分解后的形状 的特征, 而不是原始形状的特征. 分解后的形状之所以被称为特征形状, 是因为在特征分解 过程中, 这些特征形状保留了原始形状的信息. 文献[73 ]给出了一种基于M ST 的形状匹配 算法, 并使用遗传算法来挑选一个次优的结构基元来计算M ST 形状描述子. 对于来自同一 类的形状, 这个被选中的次优结构基元可以给出很好的分类结果. 5　基于局部特性的形状匹配方法 上一节主要介绍了基于全局特征进行匹配的方法, 但是如果形状发生形变或者受到遮 掩, 那么全局特征就变得不可靠了. 为了处理更加广泛的形变问题和遮掩问题, 学者们提出 了很多基于形状局部特征的形状匹配算法. 这类方法主要是通过搜索最优点对应或特征对 应来判断形状是否匹配. 它们的原始雏形就是广义Hough 变换, 而传统的动态规划等优化 算法得到了广泛的应用, 现代优化算法如神经网络、遗传算法的应用, 使得许多有遮挡问题 和变形问题得到了解决. 当今解决形变问题最流行的方法是变形模板. 实际上形状也可看作 3865 期 　丁险峰等: 形状匹配综述 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 一维随机信号, 所以在语音识别中得到成功的许多算法也被广泛地应用到了形状匹配中, 如 动态时间规整、隐M arkov 模型、自回归模型等. 形状的凹凸结构也是决定形状的视觉特征, 也受到了广泛的关注. 5. 1　广义 Hough 变换 (GHT) Hough 首先提出了称为 Hough 变换的区域外形边界变换的形状描述方法. Hough 变 换的目标是寻找一种从区域边界 (空间域) 到参数空间的变换, 用大多数边界点所满足的对 应参数来描述这个区域的边界. 文献 [ 74 ]提出了对于任意形状曲线的广义 Hough 变换 (GH T ) 方法, 并推广了这一结果, 经典的广义Hough 变换是抽取曲线和对曲线建模的传统 方法. 因为这类方法是基于投票数的累积, 所以它们相对于噪声和遮掩不敏感. 实际上, 如果 噪声是加性噪声, 如高斯白噪声, 广义Hough 变换可以通过模板匹配来实现, 根据检测误差 而言模板匹配是最优的. 在复杂场景且外点很多的情况下, 这些方法对尺度变化处理得不太 好. GH T 只考虑全局匹配函数, 动态规划则被广泛地用于寻找点对应. 5. 2　基于神经网络和遗传算法匹配方法 神经网络和遗传算法是近年发展起来的优化方法. 并被广泛的应用到有遮掩形状的匹 配问题中, 其中Hopfield 神经网络是形状匹配中最常用的. 预处理以后的形状是由一组关 键点表示, 目标的每个点和模型的每个点结成点对, 每个点对由一个神经元表示, 那么每个 目标点只能和一个模型点匹配就是行约束, 每个模型点只能与一个目标点匹配就是列约束, 整体的几何不变量就作为能量. Songde M a 和N A n sari[ 10 ]先后独立的提出了基于Hopfield 神经网络的形状匹配方法, 它在一定程度上解决了部分遮掩问题. 黎倩[ 75 ]等人提出了双 Hopfield 神经网络来解决遮掩问题. Young [ 76 ]等人提出了多层 Hopfield 网来更一步挖掘神 经网络关于遮挡问题的潜力. R a jpa l[ 77 ]等人使用了多层感知网和索引的方法来匹配部分遮 挡的形状. Beb is[ 78 ]等人用曲率尺度空间提取形状的特征点, 并且把不同尺度下的特征点用 BP 算法学习, 从而融合了各个尺度下的信息. 5. 3　变形模板 在计算机视觉中基于模板的形状匹配是个非常经典的问题. 早期关于这个领域的研究 主要集中在刚体形状匹配, 其中待匹配图像相对于模板图像只经过平移、旋转、尺度变换和 仿射变换, 所有这些都可以通过相关匹配或Hough 变换来获得. 在大多数场合, 因为在图像 处理中的变化和存在的类内差异, 任何目标都没有一个严格的几何模型可以利用, 所以上述 方法的应用十分有限. 变形模板的概念几乎是随着W idrow [ 79 ]的橡皮模板和 F isch ler 的弹 性模板[ 80 ]而进入计算机视觉领域. 因为变形模板能够发生变形以匹配到显著的图像特征, 因此是一个有力的形状匹配工具. 近些年计算机视觉界开展了很多关于变形模板的研究. 在这些研究中, 变形模板可以分 为两大类: 自由式 (free2fo rm ) 和参数式. 对于自由式变形模板, 没有全局结构, 只要求满足 某些一般的正则化约束, 可以表示任何形状. 当几何形状的先验知识已知, 并可用少量的参 数表示时, 则可以采用参数化变形模板. 5. 3. 1　自由式变形模板 自由式变形模板中最有代表性的是由 Kass[ 81 ]等人提出的称为 snake 的主动轮廓模型 (act ive con tou r m odel). 在这个方法中, 一个被称为 snake 的能量最小化样条, 由以下三种 486 自　　动　　化　　学　　报　 27 卷 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 力的组合来控制和约束 1) 控制平滑度的轮廓内部能量; 2) 吸引轮廓到特定特征的图像力量; 3) 外部约束力. 一条 snake 可以弹性变形, 但是任何变化将增加内部能量而产生将它拉回原来位置的 力. 同时 snake 处于一个能量场 (由图像产生) 中, 它产生外力作用在 snake 上的, 在这两种 力作用下, 轮廓调整自己的位置和形状直到它达到能量的最小值. 能量函数表示为 E snake =∫10E in t (v (s) ) + E im age (v (s) ) + E con (v (s) ) ds, 其中 s 是轮廓的参数, v (s) 是轮廓上的点; 轮廓的内部能量 E in t (v (s) ) 表示由于弯曲而产生 的样条的内部能量; 图像能量 E im age (v (s) )代表由图像力产生的势能; E con (v (s) ) 代表外部能 量, 诸如弹力或排斥力. 先给定一个合适的初始化轮廓, snake 通过梯度下降法收敛到最近的局部极小值. 但这 个方法非常依赖于局部信息, 最初实现的 snake 模型对它的初始位置和图像噪声是非常敏 感的, 轮廓经常会收敛到能量函数的某个局部极小值. 人们提出了许多方法来解决这个问 题, N euen schw ander[ 82 ]等人允许用户点出理想轮廓上的两个端点, 在最优化过程中边缘信 息从端点向中心传播. Fua 和B rechbuh ler[ 83 ]提出, 为获得最理想的效果, 必须加上吸引子和 切线方向上的硬约束, 其中吸引子和约束可以让轮廓通过图像某些特定点, 切线约束力强迫 轮廓在这些特定点有一定的斜率. Cohen [ 84 ]提出了主动轮廓线的气球模型, 他在外力中增加 了膨胀力, 可以帮助 snake 侵入某些孤立的、弱边缘的图像区域. 这种 snake 对起始点和图 像噪声的变化更加鲁棒. 这个模型非常适合局部一致光滑的目标, 但是不适合有多个部分或 多种颜色组成的目标. Am in i[ 85 ]等人提出使用动态规划来最小化能量函数, 它们搜索所有可 以接受的解和在每个局部最优轮廓上的迭代解. Geiger [ 86 ]提出了一种非迭代的方法, 它允许 轮廓搜索起始点周围很大一块区域的所有地方. 通过加上不同的正则化约束, 还可以获得有 各种不同特征的变形模型. Ch risten sen [ 87 ]提出了一种基于扩张粘滞液体的正则化约束的变 形模板, 它融合变形的动力学信息, 用从流体力学中导出的偏微分方程来约束模型的演化. 大多数主动轮廓模型或者 snake 方法基于外部边缘的代价来优化代价函数, 也有一些人使 用轮廓内部代价来优化代价函数. Ronfard [ 88 ]引入了基于背景和目标区域统计模型的能量 函数. 他们的策略是当轮廓上像素的邻域属于背景的模型分布, 就推这像素; 反之属于目标 的分布, 就拉该像素. F igueiredo [ 89 ]等人在最小化过程中决定背景和目标的分布. Cox [ 90 ]等 人在图像分割中同时利用边缘和内部信息. 他们的算法通过一个快速的分图算法来最小化 外部边缘代价和内部区域收益的比值. 在图中的闭合路径相当于图像中闭合轮廓. 还有一些 方法先获得基于区域的图像分割, 然后和主动轮廓方法相结合. 采用B 样条来表达轮廓更加结构化, 因为轮廓由一组基函数线性组成, 它的形状由基 函数的系数调节, 线性组合可以是任意的, 这种方式也不像参数化模型需要一个缺省形状. M enet [ 91 ]等人提出B 2snake, 目标轮廓用B 样条来表达, 轮廓的表达更加有效, 同时也能隐 式地表达角点. F lickner [ 92 ]等人定义了一个类似的能量函数, 但是他们用一个启发式搜索方 法来求解控制点. 该方法很快, 可以通过移动鼠标来交互给出目标的轮廓. F igueiredo [ 93 ]等 5865 期 　丁险峰等: 形状匹配综述 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 人用Bayesian 方法来描述此问题, 并且提出一种迭代的 EM 算法来解这个问题. 5. 3. 2　参数化变形模板 当几何形状的一些先验知识已知, 并且可以用少量参数表述时, 人们经常采用参数化变 形模型. 一般有两种方法可以参数化形状和它的形变, 解析变形模板由一群解析函数确定, 模板的几何形状可以通过参数的变化而变化, 形状的变化确定在参数的一个合理分布中; 和 主动轮廓模型一样, 目标函数由一个内部能量和一个外部能量加权组合而成, 它表征了变形 模板和图像之间的吻合度. 变形模板和图像特征之间交互作用是根据图像力来动态的调整 参数而实现的. 这种方法要求几何形状的结构化非常好. 另一种方法是基于模型的变形模 型, 一般会定义一个原形模板, 它可以刻划该类目标最可能的、平均的、有特色的形状. 该类 的其他形状都通过原形和参数映射获得, 不同的参数给出不同的形状, 形状的变化也可以由 映射参数分布决定. W idrow 在文献[79 ]中给出了一个典型的解析参数化变形模型, 这个称为橡皮模具的 参数化模板用于描述二维不规则形状. 参数用于描述尺寸和形状的各个部分之间的相互关 系. Yu ille [ 94 ]等人使用变形模板抽取面部特征. 他们给嘴和眼睛分别设计了以圆和抛物线为 基础的变形模板. 控制模板形状的参数分别是圆的圆心、半径和抛物线的系数. 此外根据面 部特征给这些参数加上一些正则化约束, 如眼睛和嘴的大小以及相互关系 (如嘴的中心在两 只眼睛中心的中垂线上). 图像能量是根据输入灰度图像与眼睛和嘴的特征相关的边缘、波 峰、波谷来决定的. L ak shm anan [ 95 ]等人使用参数化变形模型来确定雷达图像中的飞机跑道 的边缘. 两条平行直线构成了跑道的全局形状模型, 它由几个参数控制: 两条边缘的斜率和 起点. 首先假设跑道将图像分成三个相对一致的区域, 然后建立雷达图像处理的物理模型, 跑道边缘检测问题就变成了一个贝叶斯估计问题. Sta ib [ 96 ]等人使用椭圆 Fou rier 描述子来 代表闭合或开的边缘模板, 变形模板的参数是 Fou rier 系数. 他们给定了 Fou rier 系数的一 个概率分布, 可以允许形状朝某些特殊形状作灵活的变化. 这个分布由这类目标中的各个样 本间的变化控制. Bayesian 决策准则用来得到对边缘的最优估计, 它的似然函数由模板和输 入图像的边缘强度来决定. 这类方法因为要求所研究的形状必须是可以由一簇曲线 (而且参 数不能太多)良好定义的, 所以它的应用范围是有限的. 比参数化变形模板更加灵活的方法就是从原形中提取变形模板. 由 Grenander [ 97, 98 ]提 出的模式理论描述了一种表示形状的一般性框架, 这个框架不但可以允许有多种变化, 而且 有非常明确的结构. 它的形状模型可以表示为一个描述形状整体结构的原形模板和一组在 形状积木之间表示映射的参数. 模型和参数合在一起可以表示一类形状的全局和局部的几 何特性. 原形模板一般是基于目标的先验知识而确定的, 有的通过高层知识来指定, 有的是 从训练样本中提取. 那些统计得出的参数化映射可以反映在某个应用领域中的所有特殊 变形. 通过选取不同的原形模板和变形过程, 可以得到各种形式的模型. Chow 等人[ 99 ]使用多 边形来近似人手的轮廓. 在这个形状模型中的形状积木是多边形边缘, 因为多边形简单而且 相互连接, 很容易满足正则化条件. 不同手之间的变化由基于边缘的M arkov 随机过程表 示. 也有人使用类似的方法来对树叶、三维的椅子、三维的人类器官建模. Am it [ 100 ]等人在噪 声图像中恢复手时, 用灰度图像来代表一个典型的手. 同类的手都是通过对理想手图像进行 686 自　　动　　化　　学　　报　 27 卷 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 连续变换而获得. Coo tes[ 101, 102 ]等人采用主元分析方法在“主动形状模型”中来学习线条画的 变形模板的模型.“主动形状模型”是通过对正确标注过的形状的学习得出原形形状和变形 参数. 他们一般用多边形表示形状模型, 通过手工校正训练样本, 也就是在同类训练样本间 建立对应点, 就可以从训练的形状中计算出平均位置和变化. 这个平均形状就用作这类形状 的一般模板, 一些变化参数, 也就是协方差矩阵的特征值, 用来描述样本形状和一般形状之 间的主要变化. 该方法的主要贡献在于通过学习这类形状中的某些特色模式, 从而可以像训 练样本中的变化一样变形. 它的主要缺陷是对局部遮掩敏感, 而且不能处理大的尺度和方向 变化. D u ta 和 Sonka [ 103 ]指出了这些局限, 然后设计了一个新模型并且成功将它应用于鉴别 核磁共振脑图像中的神经元结构的实验中. 他们的方法中的拟合策略和 Coo tes、T aylo r 的 方法主要不同点表现在两个方面: 搜索过程完全由模型控制, 也就是说分割假设不受图像数 据的误导, 另外他们不使用任何预处理. 在拟合过程中首先使用刚体变换将平均图像移动到 最合适的位置, 然后用与平均图像重叠的形状确定局部信息. 他们还研究了一套外点检测和 替换算法, 并且根据暗含在形状模型中的顶点之间的相对关系来推断这些外点的正确位置. Kervrann 和 H eitz[ 104 ]提出了一套和 Coo tes 等人方法非常类似的变形模板的方法, 即在定 长序列图像中用无监督学习方法学习二维多边形目标的变形模板和参数的方法. 他们同时 也使用局部和全局变形模型来描述形状. 局部信息, 包括从新的图像帧中获得的附加信息, 用一个连续M arkov 随机过程来描述, 它同时也考虑相邻像素点之间的交互作用. 在训练阶 段, 从每个图像帧中获得的局部信息都用来更新全局平均模板和变形参数. 给定一组有代表性的形状, Scla roff 和 Pen t land [ 105 ]提出了一种基于有限元方法的新的 形状模型. 他们使用像三维弹性粘土一样的三维有限元模型来描述三维形状. 从一个适当的 基形状 (诸如椭圆)来获取振荡模型, 然后用不同的形状振荡模型来重建形状. 他们用一个交 互过程把模型拟合到距离图像上, 然后通过参数拟合来比较模型化后的目标. 5. 4　基于形状凹凸结构的匹配方法 形状的凹凸结构是形状的一个非常重要的特征, 人们已经将它广泛地应用到了形状匹 配中. M in sky 和 Papert [ 106 ] 以及 Sk lan sky [ 107 ] 等人首先描述了形状的凹凸结构. 十年后 K im [ 108 ]定义了“面积特征”, 并且证明了如果- 个八连通区域满足“面积特征”就是凸的. 简 单修改一下数字化方法后, 就可以证明凸数字集合满足几种等价的几何特征[ 108～ 110 ]. 其中一 个值得注意的特征是线特征, K im 研究了数字凸多边形的特征, 并且扩展了线特征这个概 念[ 109 ]. Ron se [ 111 ]继续了这项工作, 他把数字凸形状分成两大类, 一类是 T 形凸区域, 一类是 L 形凸区域. 和凸性相关的概念是凸壳. 一个形状 S 的凸壳 S H 就是所有包含 S 的凸区域的 交集. 在计算几何中寻找凸壳是一个非常热门的课题[ 112～ 114 ], 也提出了许多算法. 计算凸壳 的方法也可用来测试该区域是否是凸区域, 因为如果是凸区域, 那么这个区域和它的凸壳等 价. 如果已经获得某区域的凸壳, 那么该区域的形状就可以用凹度树[ 115 ]来表示. 一旦获得形 状的凹度树表示以后, 形状就是一个图结构, 形状匹配用传统的图匹配算法就可以解决. 最 早W in ston [ 116 ]提出了一种描述简单块结构的凹凸表示方法. M icha lsk i[ 117 ] 和L angley 与 Carbonell[ 118 ]提出了学习结构描述子的算法. 但是这些算法给出了一些大体的概念, 不能处 理实际形状. Connell 和B rady [ 119 ]改进了W in ston 的算法, 提出了一种可以利用形状先验知 识的学习算法. Segen [ 120 ]提出一个学习非刚体形状的模型学习算法. 但是图模型的方法有很 7865 期 　丁险峰等: 形状匹配综述 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 多缺点, 学习和识别算法非常慢, 并难于达到最优值[ 121 ]. U eda [ 122 ]等人提出了一种多尺度凹 凸结构学习方法. 有兴趣的读者可参考Ron se [ 123 ]关于这方面的综述. 5. 5　动态规划 动态时间规整在语音识别中获得了很大的成功, Ro ss M cConnedll[ 8 ] 应用它来识别 SA R 图像. 首先他们改进了轮廓的 Η2s 曲线表示方法, 使之成为连续 Ω2s 的曲线, 然后设计 了动态规划标来简化动态规划的回归算法. H anqin L u [ 124 ]改进了动态规划算法提出动态匹 配的概念, 在匹配形状时, 他们不断分裂合并形状的方向角函数. 在文献[7 ]中动态规划也被 用来识别被遮掩形状, 他们首先提出了基于 Fou rier 描绘子的线段表示方法, 每个形状被分 成几个线段, 每个线段由一个长度为 2 的 Fou rier 描绘子表示, 然后计算模型与待识别目标 之间的动态匹配表, 最后根据匹配的线段数来判断是否匹配. 串匹配是另一种形式的动态规 划, 假定 s, t 是两个串, 然后给定编辑代价函数, 三种不同的弧代表串操作插入、删除、和修 改. W agner 和 F isher[ 125 ]通过加权图定义了一种编辑图. 这样就将 s, t 之间的串匹配变成了 寻找 v (0, 0) 到 v (n , m ) 的最短路径. T sa i 和 Fu 将统计决策理论引入到这个理论中, 然后提 出了一种强有力的编辑操作2合并, 大大提高了识别率. 后来他们还将“分裂”引入进来. 为了 解决线性串匹配技术对起始点的依赖性,M ae 提出了一种圆周串匹配技术用于多边形匹 配. W u [ 126 ]等人提出了一种两个阶段的串匹配技术, 在第一阶段他们应用多边形匹配抽取一 些特征点, 用这些特征点获得一个粗匹配, 在第二个阶段对每条边进行细调. H aim J W o lf2 son [ 9 ]也将串匹配用于有遮掩形状的匹配中, 但是他们通过寻找匹配度最高的子串来确定起 始点. 5. 6　基于自回归模型和隐M arkov 模型 两维的形状可以用一维的实数或复数函数表示, 把这个函数看成一个随机过程实现, 通 过估计得到的模型参数就可以作为形状描述子. 用自回归模型[ 127 ]分析闭合形状是 Kashyap 和 Chellappa 在 1981 年首先提出来的, 他 们用自回归系数作特征矢量来刻划形状. 在D ubo is 和 Glanz[ 128 ]的实验中得到了很好的结 果, 在质心与轮廓之间以等角间距采样得到径向量的长度序列, 然后对此序列应用A R 模 型. Kart ikeyan [ 129 ]等人认为线性A R 模型只适用于识别那些形状明显不同的图形而对形状 差别较小的图形识别能力较差, 为此构造了非因果二次V o lterra 模型. 但是这种模型的计 算量很大, 模型阶数不易选择, 从而使特征集的形式很难统一并增大了模式分类的难度. D as[ 130 ]等人采用了二维双变量A R 模型, 这种方法要估计的模型系数是相应同阶次一维模 型的四倍, 冗余性大. 另外, 此模型只是简单地将直角坐标 x , y 作为双变量来处理, 忽视了 它们之间的正交特性, 导致模型系数并不直接具备旋转不变性. 为了克服双变量A R 模型的 固有缺点, Sek ita [ 131 ]等人提出了复数域A R (CA R )模型, 实验研究表明识别效果优于不变矩 和傅立叶描述符方法, 尤其在有噪声的情况下. 但是由于该模型是线性的, 它不能反映图形 轮廓的二维非线性封闭循环特性和局部特性, 所以在识别某些相似图形时效果不好. 自回归模型的主要缺点就是它只使用一个预测参数集来描述整个形状, 如果形状中有 很多角点或者形状变化非常剧烈, 那么这个形状就变得难以预测. 为此, H e 和 Kundu [ 132 ]把 A R 模型和隐M arkov 模型结合起来用于形状分析, 把形状边界分成若干段, 每一段用A R 模型描述, 所得到的向量再用隐M arkov 模型分析. 886 自　　动　　化　　学　　报　 27 卷 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 6　结束语 在计算机视觉和模式识别领域, 形状匹配是一个很重要的问题, 至今尚未得到充分解 决. 在过去的几十年中, 人们对此进行了大量的研究工作, 提出了很多方法, 人们在使用时要 根据这些方法的特点和具体的应用需要做出选择. 本文对一些有代表性的方法做了简短的 讨论, 试图介绍该方向的一些主要方法及其特点, 并给出了一些参考文献, 希望对读者进一 步的研究工作有帮助. 参 考 文 献 1 Ro senfeld A. A xial rep resen tations of shape. CV G IP , 1986, 2 (33) : 156～ 173 2 O gniew icz R L , Kubler O. H ierarch ic vo rono i skeletons. P attern R ecog n ition, 1995, 28 (3) : 343～ 359 3 T ari Z S G, Shah J , P ien H. Extraction of shape skeletons from grayscale im ages. CV IU , 1997, 66 (2) : 133～ 146 4 M um fo rd D avid. M athem atic theo ries of shape: Do they model percep tion? In: P roc. Geom etric M ethods in Com 2 puter V ision, SP IE, 1991. 1570: 2～ 10 5 Grim son W E ric, H utten lcher D aniel P. O n the sensit ivity of Hough transfo rm fo r object recognit ion. IE E E T rans. PA M I , 1990, 12 (3) : 255～ 274 6 D erek C W Pao, Hon F L i, Jayakum ar R. Shape recognit ion using the straigh t line Hough transfo rm: T heo ry and generalization. IE E E T rans. PA M I , 1992, 14 (11) : 1076～ 1089 7 Go rm an J W , M irchell O R , Kuh l F P. Part ial shape recognit ion using dynam ic p rogramm ing. IE E E T rans. PA 2 M I , 1988, 10 (2) : 257～ 266 8 M cConnell Ro ss, Kwok Ronald, Curlander John C, Kober W , Pang Sh irley S. Ω2s co rrelat ion and dynam ic tim e w arp ing: Two m ethods fo r track ing ice floes in sar im age. IE E E T rans. Geoscience and R em ote S ensing , 1991, 29 (6) : 1004～ 1012 9 W o lfson H aim J. O n curve m atch ing. IE E E T rans. PA M I , 1990, 12 (5) : 483～ 489 10 A nsari N , D elp E J. O n the distribu tion of a defo rm ing triangle. P attern R ecog n ition, 1990, 23 (12) : 1333～ 1341 11 L am dan Y, Schw arz J T , W o lfson H J. A ffine invarian t model2based object recognit ion. IE E E T ra