D0L:10.13374.issn1001-053x2013.09.017 第35卷第9期 北京科技大学学报 Vol.35 No.9 2013年9月 Journal of University of Science and Technology Beijing Sep.2013 基于多级三角形面积函数的傅里叶形状描述子 徐国清，穆志纯凶 北京科技大学自动化学院，北京100083 ☒通信作者，E-mail:mu@ies.ustb.edu.cm 摘要提出了一种用于形状检索的基于多级三角形面积函数的傅里叶描述子.对形状轮廓上任一点，多级三角形面积 函数通过轮廓的非等弧长分割计算得出，可以很好地描述形状的整体特征和局部细节特征.形状特征向量由多级三角形 面积函数的低频傅里叶变换系数构成.在标准的MPEG7形状图像库上对该方法进行了图像检索实验，并与己有的分 别基于中心距离函数、面积函数、最远点距离函数、角度半径复函数、拱高半径复函数的傅里叶描述子以及混合傅里叶 描述子进行了检索性能比较.实验结果表明，所提出的方法在相同查全率时具有最高的查准率，且具有较低的计算复杂 度，证明该方法的有效性 关键词基于内容的检索：图像检索：几何学：形状描述：傅里叶变换 分类号TP391.4 Fourier shape descriptor based on multi-level triangular area func- tions XU Guo-qing,MU Zhi-chun School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:mu@ies.ustb.edu.cn ABSTRACT A novel Fourier descriptor based on multi-level triangular area functions (MTA)was proposed for shape retrieval.For each point on the shape contour,MTA values were derived from unequal-arc-length partitions of the shape contour.The MTA can finely capture the global features and local contour variations of the contour and their low- frequency Fourier coefficients were regarded as the feature vector for shape description.The image retrieval performance of the proposed method was evaluated on the standard MPEG-7 shape database and compared with those of Fourier descriptors derived from the centroid distance function,area function,farthest point distance function,angular radius function,arc-height radius complex function,and the combined Fourier descriptor.Experimental results demonstrate that the proposed method reaches the highest precision at the same recall value and has low complexity among these descriptors,showing its effectiveness. KEY WORDS content based retrieval;image retrieval;geometry;shape description;Fourier transforms 基于内容的图像检索是近些年来模式识别和 直是它的研究热点同 信息检索领域的一个热点问题-习.它使用图像的 已有的形状描述方法大致分为两类，即基于形 低层内容特征对图像进行自动的索引和检索，例如 状区域的和基于形状轮廓的同.基于形状区域的形 颜色、形状和纹理.形状作为图像的主要视觉特征 状描述方法使用图像中整个目标的区域来提取形状 之一，在目标检测和识别中具有重要作用3，人们 的特征，而基于形状轮廓的描述方法则仅利用目标 通常仅从目标的形状特征就能识别出目标4.因此， 轮廓.基于轮廓的形状描述方法易于实施，因此研 形状的描述，即如何有效地抽取目标的形状特征一 究者提出了许多基于轮廓的形状描述方法，例如曲 收稿日期：2012-08-07 基金项目：国家自然科学基金资助项目(61170116,61005009,60973064)
第 35 卷 第 9 期 北 京 科 技 大 学 学 报 Vol. 35 No. 9 2013 年 9 月 Journal of University of Science and Technology Beijing Sep. 2013 基于多级三角形面积函数的傅里叶形状描述子 徐国清，穆志纯 北京科技大学自动化学院, 北京 100083 通信作者，E-mail: mu@ies.ustb.edu.cn 摘 要 提出了一种用于形状检索的基于多级三角形面积函数的傅里叶描述子. 对形状轮廓上任一点，多级三角形面积 函数通过轮廓的非等弧长分割计算得出，可以很好地描述形状的整体特征和局部细节特征. 形状特征向量由多级三角形 面积函数的低频傅里叶变换系数构成. 在标准的 MPEG-7 形状图像库上对该方法进行了图像检索实验，并与已有的分 别基于中心距离函数、面积函数、最远点距离函数、角度半径复函数、拱高半径复函数的傅里叶描述子以及混合傅里叶 描述子进行了检索性能比较. 实验结果表明，所提出的方法在相同查全率时具有最高的查准率，且具有较低的计算复杂 度，证明该方法的有效性. 关键词 基于内容的检索；图像检索；几何学；形状描述；傅里叶变换 分类号 TP391.4 Fourier shape descriptor based on multi-level triangular area functions XU Guo-qing, MU Zhi-chun School of Automation and Electrical Engineering, University of Science and Technology Beijing, Beijing 100083, China Corresponding author, E-mail: mu@ies.ustb.edu.cn ABSTRACT A novel Fourier descriptor based on multi-level triangular area functions (MTA) was proposed for shape retrieval. For each point on the shape contour, MTA values were derived from unequal-arc-length partitions of the shape contour. The MTA can finely capture the global features and local contour variations of the contour and their lowfrequency Fourier coefficients were regarded as the feature vector for shape description. The image retrieval performance of the proposed method was evaluated on the standard MPEG-7 shape database and compared with those of Fourier descriptors derived from the centroid distance function, area function, farthest point distance function, angular radius function, arc-height radius complex function, and the combined Fourier descriptor. Experimental results demonstrate that the proposed method reaches the highest precision at the same recall value and has low complexity among these descriptors, showing its effectiveness. KEY WORDS content based retrieval; image retrieval; geometry; shape description; Fourier transforms 基于内容的图像检索是近些年来模式识别和 信息检索领域的一个热点问题[1−2] . 它使用图像的 低层内容特征对图像进行自动的索引和检索，例如 颜色、形状和纹理. 形状作为图像的主要视觉特征 之一，在目标检测和识别中具有重要作用[3]，人们 通常仅从目标的形状特征就能识别出目标[4] . 因此， 形状的描述，即如何有效地抽取目标的形状特征一 直是它的研究热点[5] . 已有的形状描述方法大致分为两类，即基于形 状区域的和基于形状轮廓的[6] . 基于形状区域的形 状描述方法使用图像中整个目标的区域来提取形状 的特征，而基于形状轮廓的描述方法则仅利用目标 轮廓. 基于轮廓的形状描述方法易于实施，因此研 究者提出了许多基于轮廓的形状描述方法，例如曲 收稿日期：2012–08–07 基金项目：国家自然科学基金资助项目 (61170116, 61005009, 60973064) DOI:10.13374/j.issn1001-053x.2013.09.017
·1202 北京科技大学学报 第35卷 率尺度空间法、傅里叶描述子、自回归模型和结 的鲁棒性，但不能很好地反映出形状边界细节信息： 构的方法可.其中傅里叶描述子(Fourier descriptor,. 形状的局部特征可以较好地描述边界的细节，但易 FD)是一种经典的形状描述方法，它具有较低的计 受到噪声的影响刂.事实上，形状的全局特征和局 算复杂度和由粗到细的描述能力，兼顾了检索效率 部细节在形状描述中具有同等重要的作用.一个好 和准确率，因而一直是研究者关注的热点 的形状描述子应当同时包含形状的全局特征和局部 傅里叶描述子方法首先将二维形状轮廓表示成 细节信息 一维的轮廓线函数，又称形状签名，用轮廓线函 本文使用多级三角形面积函数进行形状描述， 数的傅里叶变换系数构成形状特征向量.由于一 其傅里叶变换系数构成形状特征向量.多级三角形 个形状轮廓可以产生多个不同的轮廓线函数，因此 面积函数通过形状轮廓的非等间隔划分构成形状的 该方法涉及多个形状签名，例如常用的中心距离函 多级描述，从而使用一种特征函数同时描述形状的 数(centroid distance,CD)、复坐标函数(complex 全局特征和局部细节信息.在MPEG-7标准形状图 coordinates,CC)、面积函数(area function,AF)) 像库上的检索实验表明，与基于中心距离、三角形 以及新提出的最远点距离函数(farthest point dis- 面积、最远点距离、角度半径、拱高半径复函数以 tance,.FPD)闷、拱高半径复函数(arc-height radius 及混合的傅里叶描述子相比，该方法在同一查全率 complex function,AHRC)、周横截三角形面积函 下具有最高的查准率，表明基于多级三角形面积函 数(perimeter area function,PAF)lol.而且不同形状 数的傅里叶形状描述子的有效性 签名所产生的傅里叶描述子具有不同的形状描述能 力，在基于形状的图像检索中也表现出不同的检索 1多级三角形面积函数 性能.Zhang和Lu可通过充分的实验比较了多种不 将闭合的目标轮廓线沿逆时针方向表示为有 同轮廓线函数的检索性能：结果显示，与复坐标函 序点集，即C={p:=(x,),i=0,1,…,N-1},其 数、曲率函数、累加角度函数和弦长函数相比，基 中x:和：分别是点p:的横、纵坐标，N是轮廓线 于中心距离和面积函数的傅里叶描述子具有更优的 上的点的个数，p0是轮廓线的起始点.由于目标轮 检索性能.这主要得益于中心距离和面积函数可以 廓是闭合的，有序点集可看作是周期的信号.定义 很好地描述形状的整体特征.但是，这两种函数在 轮廓线周长L等于轮廓线上点的个数 描述形状的局部特征方面具有一定的不足， 对于轮廓线的任一点P,从该点开始沿逆时针 为了提高傅里叶描述子对形状特征的描述能 方向依次在轮廓线上找到K个点，并且满足第k 力，近些年来研究者提出了一些新的形状签名，并 个点与：之间的弧长为(2k+1-2k-1)×L/2K+2,其 取得了有价值的研究结果.为了描述形状轮廓的角 中=0,1，…，N-1,k=1,2,…,K.然后沿相反方 点信息，E-ghazal等)提出了一种最远点距离函 向再依次定位K个点，并且满足相同的弧长条件 数来产生傅里叶描述子.对轮廓线上的任一点，在 这样总共定位2K个点，并且可以构成K对点，每 轮廓线上找出距离其最远的点，这两个点到形状中 对点与P:之间的弧长相等，这三点可形成一个三 心点的距离之和定义为最远点距离函数在该点的取 角形.图1给出了一个K=6时在轮廓上一点p: 值.该函数在MPEG-7形状库上取得了比Zernike矩 所构成的六个三角形的例子.图中距离p弧长相等 和曲率尺度空间法更好的检索性能.但是，从产生 的点用相同颜色的星号标出. 过程可以看出，该函数仍然受到中心距离函数的影 对于这K个三角形，使用海伦公式分别计算 响.为了使得傅里叶描述子能同时描述形状的全局 它们的面积.第k个三角形面积S.即为 特征和局部细节，Wang9-1o提出了拱高半径复函 数和混合傅里叶描述方法.拱高半径复函数利用中 lk1=V(工-xk1)2+(:-hk1)2, (1) 心距离和带正负号的拱高来分别描述形状的全局特 lk2=V(x-xk2)2+(h-k2)2, (2) 征和局部细节，其傅里叶变换系数构成描述形状的 特征向量.混合傅里叶描述方法使用带符号的周横 L3=V(zk1-Tk2)2+(1-2)2, (3) 截三角形面积函数和中心距离函数导出的傅里叶系 1 lik=(lik1+lik2+lik3), (4) 数共同构成特征向量.这两种方法均利用不同特性 的轮廓线函数来克服单一函数的不足，在一定程度 Sik Vlik(lik lik1)(lik lik2)(lik -lik3). (5) 上提高了形状检索的性能 式中，工、班、工k1、工k2、1和k2是第个三角 一般地，形状的全局特征对边界噪声具有较高 形三个顶点坐标，k=1,2,·,K
· 1202 · 北 京 科 技 大 学 学 报 第 35 卷 率尺度空间法、傅里叶描述子、 自回归模型和结 构的方法[7] . 其中傅里叶描述子 (Fourier descriptor, FD) 是一种经典的形状描述方法，它具有较低的计 算复杂度和由粗到细的描述能力，兼顾了检索效率 和准确率，因而一直是研究者关注的热点. 傅里叶描述子方法首先将二维形状轮廓表示成 一维的轮廓线函数，又称形状签名，用轮廓线函 数的傅里叶变换系数构成形状特征向量. 由于一 个形状轮廓可以产生多个不同的轮廓线函数，因此 该方法涉及多个形状签名，例如常用的中心距离函 数 (centroid distance, CD)、复坐标函数 (complex coordinates, CC)、面积函数 (area function, AF)[7] 以及新提出的最远点距离函数 (farthest point distance, FPD)[8]、拱高半径复函数 (arc-height radius complex function, AHRC)[9]、周横截三角形面积函 数 (perimeter area function, PAF)[10] . 而且不同形状 签名所产生的傅里叶描述子具有不同的形状描述能 力，在基于形状的图像检索中也表现出不同的检索 性能. Zhang 和 Lu[7] 通过充分的实验比较了多种不 同轮廓线函数的检索性能；结果显示，与复坐标函 数、曲率函数、累加角度函数和弦长函数相比，基 于中心距离和面积函数的傅里叶描述子具有更优的 检索性能. 这主要得益于中心距离和面积函数可以 很好地描述形状的整体特征. 但是，这两种函数在 描述形状的局部特征方面具有一定的不足[9] . 为了提高傅里叶描述子对形状特征的描述能 力，近些年来研究者提出了一些新的形状签名，并 取得了有价值的研究结果. 为了描述形状轮廓的角 点信息，El-ghazal 等[8] 提出了一种最远点距离函 数来产生傅里叶描述子. 对轮廓线上的任一点，在 轮廓线上找出距离其最远的点，这两个点到形状中 心点的距离之和定义为最远点距离函数在该点的取 值. 该函数在 MPEG-7 形状库上取得了比 Zernike 矩 和曲率尺度空间法更好的检索性能. 但是，从产生 过程可以看出，该函数仍然受到中心距离函数的影 响. 为了使得傅里叶描述子能同时描述形状的全局 特征和局部细节，Wang[9−10] 提出了拱高半径复函 数和混合傅里叶描述方法. 拱高半径复函数利用中 心距离和带正负号的拱高来分别描述形状的全局特 征和局部细节，其傅里叶变换系数构成描述形状的 特征向量. 混合傅里叶描述方法使用带符号的周横 截三角形面积函数和中心距离函数导出的傅里叶系 数共同构成特征向量. 这两种方法均利用不同特性 的轮廓线函数来克服单一函数的不足，在一定程度 上提高了形状检索的性能. 一般地，形状的全局特征对边界噪声具有较高 的鲁棒性，但不能很好地反映出形状边界细节信息； 形状的局部特征可以较好地描述边界的细节，但易 受到噪声的影响[11] . 事实上，形状的全局特征和局 部细节在形状描述中具有同等重要的作用. 一个好 的形状描述子应当同时包含形状的全局特征和局部 细节信息. 本文使用多级三角形面积函数进行形状描述， 其傅里叶变换系数构成形状特征向量. 多级三角形 面积函数通过形状轮廓的非等间隔划分构成形状的 多级描述，从而使用一种特征函数同时描述形状的 全局特征和局部细节信息. 在 MPEG-7 标准形状图 像库上的检索实验表明，与基于中心距离、三角形 面积、最远点距离、角度半径、拱高半径复函数以 及混合的傅里叶描述子相比，该方法在同一查全率 下具有最高的查准率，表明基于多级三角形面积函 数的傅里叶形状描述子的有效性. 1 多级三角形面积函数 将闭合的目标轮廓线沿逆时针方向表示为有 序点集，即 C= {pi=(xi , yi), i= 0, 1, · · · , N −1}，其 中 xi 和 yi 分别是点 pi 的横、纵坐标，N 是轮廓线 上的点的个数，p0 是轮廓线的起始点. 由于目标轮 廓是闭合的，有序点集可看作是周期的信号. 定义 轮廓线周长 L 等于轮廓线上点的个数. 对于轮廓线的任一点 pi，从该点开始沿逆时针 方向依次在轮廓线上找到 K 个点，并且满足第 k 个点与 pi 之间的弧长为 (2k+1−2 k−1 ) × L/2K+2，其 中 i=0, 1, · · · , N−1，k=1，2, · · · , K. 然后沿相反方 向再依次定位 K 个点，并且满足相同的弧长条件. 这样总共定位 2K 个点，并且可以构成 K 对点，每 对点与 pi 之间的弧长相等，这三点可形成一个三 角形. 图 1 给出了一个 K ＝ 6 时在轮廓上一点 pi 所构成的六个三角形的例子. 图中距离 pi 弧长相等 的点用相同颜色的星号标出. 对于这 K 个三角形，使用海伦公式分别计算 它们的面积. 第 k 个三角形面积 Sik 即为 lik1 = p (xi − xik1) 2 + (yi − yik1) 2, (1) lik2 = p (xi − xik2) 2 + (yi − yik2) 2, (2) lik3 = p (xik1 − xik2) 2 + (yik1 − yik2) 2, (3) lik = 1 2 (lik1 + lik2 + lik3), (4) Sik = p lik(lik − lik1)(lik − lik2)(lik − lik3). (5) 式中，xi、yi、xik1、xik2、yik1 和 yik2 是第 k 个三角 形三个顶点坐标，k=1,2, · · · , K
第9期 徐国清等：基于多级三角形面积函数的傅里叶形状描述子 ·1203· 一个好的形状描述子应当同时包含形状的全 局特征和局部细节信息，这两部分信息对于形状描 述和识别具有同样重要的作用.多级三角形面积函 数是在形状轮廓的不等弧长分割基础上产生的，不 同级别的面积函数描述了相距不同弧长的点所构成 的三角形面积.函数的级越小，对应的三角形顶点 间的弧长越小，倾向于描述形状的局部信息，而相 距较大弧长的点构成的三角形倾向于描述形状的全 局信息，对应函数的级较大 图2中a和b两形状是MPEG7图像库中的 属于同一类形状的两个样本，两形状的轮廓存在比 仿射形变更复杂的不规则形变，整体上相似而在局 部细节上存在较大差别.计算参数K=6时轮廓a和 b的多级三角形面积函数，可得到6级三角形面积 函数，该形状签名归一化后如图3所示 图1K=6时形成的三角形示例 Fig.1 Demonstration of triangles generated when K=6 对于轮廓线上的每一个点p,i=0,1,·,N-1, 均可以从轮廓的起始点po出发，走过长度为1的弧 米 米 到达该点，并且每点所对应的弧长1是唯一的，且每 点均可通过上述步骤构造出K个三角形.因此Sk 可以看作弧长的函数，其中=0,1，…，N-1,k=1, 2,·,K.按照三角形顶点之间的弧长大小，可以将 S分成K个函数，即S:={S0k,S1k,·,S(N-1)k}, 指 k=1,2,·,K,称之为多级三角形面积函数(mmti- level triangular area functions,MTA).与周横截三角 a的轮廓 b的轮廓 形面积函数不同，多级三角形面积函数不受中心距 图2MPEG-7形状库中同一种形状的两个样本 离函数的影响 Fig.2 Two samples of one category in the MPEG-7 shape 图像中形状发生平移和旋转时，形状轮廓线上 database 的任一点对应的多级三角形面积不发生改变，因此 从图3中可以看出，两形状的第1级和第2级 多级三角形面积函数对平移和旋转这两种仿射形变 三角形面积函数的曲线差异较大，很好地反映出形 具有不变性.为了使多级三角形面积函数在形状发 状a和b的局部细节差异：第3级函数的曲线较前 生缩放、错切等仿射形变时仍保持不变性，引入文 两级差异性减小：第46级所对应的函数曲线变得 献[12]中的轮廓归一化方法.轮廓归一化方法在提 非常接近，表明两形状的整体特征的相似性.因此 取多级三角形面积函数之前计算出轮廓坐标的协方 多级三角形面积函数可以很好地反映出两形状的局 差矩阵，利用所得的协方差矩阵对轮廓坐标进行变 部细节特征和全局特征，能够由粗到细地描述形状 换，将变换后的形状轮廓作为形状轮廓坐标的标准 特征，且能表示出存在复杂不规则形变的两形状的 形式.该轮廓归一化方法可消除不同轮廓之间的缩 差异性和相似性，具有较强的形状描述能力. 放和错切变换12.因此在轮廓标准形式基础上提取 从上述分析也可以看出，多级三角形函数的描 的多级三角形面积函数满足仿射形变不变性.由于 述能力受到参数K的影响.当K较小时，函数的 形状轮廓是闭合的，轮廓线的起始点位置可以发生级数较少，对形状的整体特征描述较强，描述不够 改变，此时多级三角形面积函数也随之改变，这给 细致：当K较大时，可以对轮廓线的划分较细，可 形状的匹配带来困难.为了消除轮廓线的起始点位 以较好地反映形状的细节特征.但是，K过大会减 置的影响，对多级三角形面积函数进行傅里叶变换. 少各级函数之间的差异性，增加计算复杂度
第 9 期 徐国清等：基于多级三角形面积函数的傅里叶形状描述子 1203 ·· 图 1 K =6 时形成的三角形示例 Fig.1 Demonstration of triangles generated when K=6 对于轮廓线上的每一个点 pi , i= 0, 1, · · · , N−1， 均可以从轮廓的起始点 p0 出发，走过长度为 l 的弧 到达该点，并且每点所对应的弧长 l 是唯一的，且每 点均可通过上述步骤构造出 K 个三角形. 因此 Sik 可以看作弧长的函数，其中 i= 0, 1, · · · , N −1，k=1, 2, · · · , K. 按照三角形顶点之间的弧长大小，可以将 Sik 分成 K 个函数，即 Si={S0k, S1k, · · · , S(N−1)k}, k=1, 2, · · · , K, 称之为多级三角形面积函数 (multilevel triangular area functions，MTA). 与周横截三角 形面积函数不同，多级三角形面积函数不受中心距 离函数的影响. 图像中形状发生平移和旋转时，形状轮廓线上 的任一点对应的多级三角形面积不发生改变，因此 多级三角形面积函数对平移和旋转这两种仿射形变 具有不变性. 为了使多级三角形面积函数在形状发 生缩放、错切等仿射形变时仍保持不变性，引入文 献 [12] 中的轮廓归一化方法. 轮廓归一化方法在提 取多级三角形面积函数之前计算出轮廓坐标的协方 差矩阵，利用所得的协方差矩阵对轮廓坐标进行变 换，将变换后的形状轮廓作为形状轮廓坐标的标准 形式. 该轮廓归一化方法可消除不同轮廓之间的缩 放和错切变换[12] . 因此在轮廓标准形式基础上提取 的多级三角形面积函数满足仿射形变不变性. 由于 形状轮廓是闭合的，轮廓线的起始点位置可以发生 改变，此时多级三角形面积函数也随之改变，这给 形状的匹配带来困难. 为了消除轮廓线的起始点位 置的影响，对多级三角形面积函数进行傅里叶变换. 一个好的形状描述子应当同时包含形状的全 局特征和局部细节信息，这两部分信息对于形状描 述和识别具有同样重要的作用. 多级三角形面积函 数是在形状轮廓的不等弧长分割基础上产生的，不 同级别的面积函数描述了相距不同弧长的点所构成 的三角形面积. 函数的级越小，对应的三角形顶点 间的弧长越小，倾向于描述形状的局部信息，而相 距较大弧长的点构成的三角形倾向于描述形状的全 局信息，对应函数的级较大. 图 2 中 a 和 b 两形状是 MPEG-7 图像库中的 属于同一类形状的两个样本，两形状的轮廓存在比 仿射形变更复杂的不规则形变，整体上相似而在局 部细节上存在较大差别. 计算参数 K=6 时轮廓 a 和 b 的多级三角形面积函数，可得到 6 级三角形面积 函数，该形状签名归一化后如图 3 所示. 图 2 MPEG-7 形状库中同一种形状的两个样本 Fig.2 Two samples of one category in the MPEG-7 shape database 从图 3 中可以看出，两形状的第 1 级和第 2 级 三角形面积函数的曲线差异较大，很好地反映出形 状 a 和 b 的局部细节差异；第 3 级函数的曲线较前 两级差异性减小；第 4∼6 级所对应的函数曲线变得 非常接近，表明两形状的整体特征的相似性. 因此 多级三角形面积函数可以很好地反映出两形状的局 部细节特征和全局特征，能够由粗到细地描述形状 特征，且能表示出存在复杂不规则形变的两形状的 差异性和相似性，具有较强的形状描述能力. 从上述分析也可以看出，多级三角形函数的描 述能力受到参数 K 的影响. 当 K 较小时，函数的 级数较少，对形状的整体特征描述较强，描述不够 细致；当 K 较大时，可以对轮廓线的划分较细，可 以较好地反映形状的细节特征. 但是，K 过大会减 少各级函数之间的差异性，增加计算复杂度
.1204· 北京科技大学学报 第35卷 1.0 1.0 1.0 U.0 0.8 06 06 0. 0.4 0.4 0.2 09 0.2 0.5 0.5 0.5 弧长 弧长 弧长 10 1.0 1.0 0.8 0.8 0.8 0.6 0.6 0.4 0.6 0.2 02 11 1 0.4 0.5 0.5 0 0.5 长 弧长 弧长 图3K=6时样本a和b的多级三角形面积函数 Fig.3 Multi-level triangular area functions of the two samples at K=6 2基于多级三角形面积函数的傅里叶形状 D(D<M)个系数构造特征向量{Zol,Z1,·, 描述子 |Z(D-11,1Zo2,1Z12,…,|Z(D-1)2l,…,1Z0K, |Z1Kl,,Z(D-1)k},这即为基于多级三角形面 由于轮廓线函数存在对轮廓线始点位置的依 积函数的傅里叶形状描述子(multi--level triangular 赖性，因此不能直接用于形状识别.通过对其作快 area Fourier descriptor,MTAFD).由于归一化后的 速傅里叶变换，使用低频系数来描述形状特征，这 多级三角形面积函数满足仿射（平移、旋转、缩放 同时也可以消除噪声的干扰，且描述子更紧致间. 和错切)不变性，所以基于多级三角形面积函数的 对于多级三角形面积函数S:={Sok,S1k,…, 傅里叶形状描述子也具有这些特性，且不受轮廓线 SN-1)k},k=1,2,…,K,N是轮廓线上的点的个 的起始点位置的影响.两个形状的相似性可以由它 数.对该函数直接使用一般的离散傅里叶变换的时 们相应的傅里叶描述子之间的欧氏距离决定 间复杂度较高，为了提高傅里叶算法计算效率，使 用快速傅里叶变换(fast Fourier transform,FFT), 3实验结果和讨论 将原始轮廓点采样为M个，满足M=2T,其中T 为了检验所提方法在图像检索中的性能，采用 为整数.采样后的轮廓对应的多级三角形面积函数 标准的MPEG-7形状图像库)进行检索实验，并 S,={S0k,S1k,…,S(M-1)k},k=1,2,…,K.对其 与其他的傅里叶描述子进行比较. 进行快速傅里叶变换，得到傅里叶变换系数如下： 3.1MPEG-7形状测试集 M-1 MPEG-7图像库包括70类形状图像，如图4 Sike-j2x(m-1)i/M M (6) 所示，每类有20个形状样本，共计1400幅图像.该 库形状类型较多，类内样本差异比较大，涵盖了旋 式中，Zmk为第k级三角形面积函数变换后的系 转、缩放、平移、缺失、伸长、噪声等多种变化，因 数，k=1,2,·,K,m为频域变量. 此常用于测试图像检索性能或多种变化下形状描述 当轮廓线的起始点位置可以发生改变时，相当 子的鲁棒性. 于多级三角形面积函数发生了平移，对应的傅里 3.2其他傅里叶形状描述子 叶变换系数幅度值不变，相位发生相应变化.因 为了对比基于多级三角形面积函数的傅里叶 此仅使用傅里叶系数的幅值作为形状特征，以消除 形状描述子与其他形状描述子的性能，选择文献中 起始点位置对傅里叶形状描述子的影响.同时，为 经典及新近提出的傅里叶描述子在同一数据库上进 使描述子更加紧致并增强对噪声的鲁棒性，使用前 行对比实验.基于中心距离函数和面积函数的傅里
· 1204 · 北 京 科 技 大 学 学 报 第 35 卷 图 3 K=6 时样本 a 和 b 的多级三角形面积函数 Fig.3 Multi-level triangular area functions of the two samples at K=6 2 基于多级三角形面积函数的傅里叶形状 描述子 由于轮廓线函数存在对轮廓线始点位置的依 赖性，因此不能直接用于形状识别. 通过对其作快 速傅里叶变换，使用低频系数来描述形状特征，这 同时也可以消除噪声的干扰，且描述子更紧致[9] . 对于多级三角形面积函数 Si={S0k, S1k, · · · , S(N−1)k}，k=1, 2, · · · , K, N 是轮廓线上的点的个 数. 对该函数直接使用一般的离散傅里叶变换的时 间复杂度较高，为了提高傅里叶算法计算效率，使 用快速傅里叶变换 (fast Fourier transform, FFT)， 将原始轮廓点采样为 M 个，满足 M=2T，其中 T 为整数. 采样后的轮廓对应的多级三角形面积函数 Si={S0k, S1k, · · · , S(M−1)k}，k=1, 2, · · · , K. 对其 进行快速傅里叶变换，得到傅里叶变换系数如下: Zmk = 1 M M X−1 i=0 Sike −j2π(m−1)i/M. (6) 式中，Zmk 为第 k 级三角形面积函数变换后的系 数，k=1, 2, · · · , K，m 为频域变量. 当轮廓线的起始点位置可以发生改变时，相当 于多级三角形面积函数发生了平移，对应的傅里 叶变换系数幅度值不变，相位发生相应变化. 因 此仅使用傅里叶系数的幅值作为形状特征，以消除 起始点位置对傅里叶形状描述子的影响. 同时，为 使描述子更加紧致并增强对噪声的鲁棒性，使用前 D(D < M) 个系数构造特征向量{|Z01|, |Z11|, · · · , |Z(D−1)1|, |Z02|, |Z12| , · · · , |Z(D−1)2|, · · · , |Z0K|, |Z1K|, · · · , |Z(D−1)K|}，这即为基于多级三角形面 积函数的傅里叶形状描述子 (multi-level triangular area Fourier descriptor, MTAFD). 由于归一化后的 多级三角形面积函数满足仿射 (平移、旋转、缩放 和错切) 不变性，所以基于多级三角形面积函数的 傅里叶形状描述子也具有这些特性，且不受轮廓线 的起始点位置的影响. 两个形状的相似性可以由它 们相应的傅里叶描述子之间的欧氏距离决定. 3 实验结果和讨论 为了检验所提方法在图像检索中的性能，采用 标准的 MPEG-7 形状图像库[13] 进行检索实验，并 与其他的傅里叶描述子进行比较. 3.1 MPEG-7 形状测试集 MPEG-7 图像库包括 70 类形状图像，如图 4 所示，每类有 20 个形状样本，共计 1400 幅图像. 该 库形状类型较多，类内样本差异比较大，涵盖了旋 转、缩放、平移、缺失、伸长、噪声等多种变化，因 此常用于测试图像检索性能或多种变化下形状描述 子的鲁棒性. 3.2 其他傅里叶形状描述子 为了对比基于多级三角形面积函数的傅里叶 形状描述子与其他形状描述子的性能，选择文献中 经典及新近提出的傅里叶描述子在同一数据库上进 行对比实验. 基于中心距离函数和面积函数的傅里
第9期 徐国清等：基于多级三角形面积函数的傅里叶形状描述子 .1205· 叶描述子已被验证是优于复坐标函数、弦长函数和 性能 曲率函数的描述子冈.基于最远点距离函数和拱高 3.5实验结果 半径复函数的傅里叶描述子以及基于周横截三角形 对MPEG-7图像库中的每一个形状作为一个 面积函数和中心距离函数(PAF+CD)的混合方法 查询图，计算它与所有形状相似性，然后按照相似 是近年来被提出的.本文对比的七种傅里叶描述 性大小进行排序，共进行1400次检索.检索中返 子包括基于中心距离函数、面积函数、最远点距离 回的形状图像个数m1的变化对应不同水平的查全 函数阁、角度半径复函数(angular radius function, 率和查准率，对于每一个查询图，统计出查全率从 ARF)14、拱高半径复函数间和多级三角形面积的 10%100%所对应的查准率.将1400幅图像对应同 傅里叶描述子以及混合傅里叶描述子PAF+CDIo]. 一查全率的查准率进行平均，可得查准率-查全率 H8A0X浓4 曲线，如图5所示 100 V雨量《写+E口 90 ●喜事可求大率米■ 80 70 4十⑧米七卡●章 60 50 ◆中才wPL国C 40 MTAFD 30 AHRFD 香雪女餐漫0为司 CD 30 PAf-cD 已/的心%米章n晋 10 -ARF 图4MPEG-7形状图像库 0 102030405060708090100 查全率/% Fig.4 MPEG-7 shape database 图5七种描述方法在MPEG-7形状图像库中查准率-查全 3.3性能评价方法 率曲线 为了评估形状描述方法的检索性能，文献中常 Fig.5 Precision-recall curves using seven methods on the 用查全率/查准率(recall and precision pair)对检索 MPEG-7 database 进行性能评估.查准率P和查全率R的定义为 从图中可以看出，MTAFD在MPEG-7图像 库上取得了很好的检索性能，在相同查全率条件 P =T/m1,R=T/m2. (7) 下，MTAFD具有最高的查准率.例如，当查全率为 式中，m1是一次检索中返回的形状图像的个数，r 50%时，MTAFD的查准率比经典的CD函数高出 是一次检索中返回的形状图像中与查询形状相似的 14%,说明与单纯的整体特征相比，形状细节特征的 个数，m2是形状图像库中与查询形状相似的形状 融入可以显著提高傅里叶描述子的描述能力.与排 总个数.查准率是表征了查询的精度，查全率反映 名第2、第3的PAF+CD和基于拱高半径复函数的 了查询的鲁棒性.一般随着查全率的增加查准率会 傅里叶描述子(arc-height radius Fourier descriptor, 随之降低.一个好的形状描述子在较高的查全率下 AHRFD)方法相比，MTAFD在查全率为0%时查 应仍具有较高的查准率. 准率分别高出约5%和13%，这表明ITAFD不但 3.4实验平台和参数设置 包含了形状的细节和全局特征，能由粗到细的描述 实验平台采用一台CPU为奔腾3.07GHz的 形状特征，对于形状的仿射形变、缺失、噪声等多 计算机，编程工具为Matlab(版本7.9).对图像 种复杂变化也有较强的鲁棒性.从而证明了多级三 库中的所有图像，提取形状的轮廓线后，重新采样 角形面积函数的有效性. 为256个点，并分别计算七种轮廓线函数及其快 为了比较MTAFD与其他傅里叶形状描述子 速傅里叶变换.多级三角形面积函数参数K=6,每 的计算复杂度，在同一实验平台下分别统计了不 级傅里叶描述子的长度D取为8，即多级傅里叶同描述子完成轮廓线函数提取、轮廓线函数的傅 描述子总长为48.每个用于比较的轮廓线函数对里叶变换以及形状匹配所需的时间.将MPEG-7 应的傅里叶描述子长度取为32，文献[7-10]已验 图像库中1400幅图像全部完成上述过程作为一组 证在这个长度下傅里叶形状描述子具有良好的检索 实验，每个描述子均进行20组实验，每个阶段
第 9 期 徐国清等：基于多级三角形面积函数的傅里叶形状描述子 1205 ·· 叶描述子已被验证是优于复坐标函数、弦长函数和 曲率函数的描述子[7] . 基于最远点距离函数和拱高 半径复函数的傅里叶描述子以及基于周横截三角形 面积函数和中心距离函数 (PAF+CD) 的混合方法 是近年来被提出的. 本文对比的七种傅里叶描述 子包括基于中心距离函数、面积函数、最远点距离 函数[8]、角度半径复函数 (angular radius function, ARF)[14]、拱高半径复函数[9] 和多级三角形面积的 傅里叶描述子以及混合傅里叶描述子 PAF+CD[10] . 图 4 MPEG-7 形状图像库 Fig.4 MPEG-7 shape database 3.3 性能评价方法 为了评估形状描述方法的检索性能，文献中常 用查全率/查准率 (recall and precision pair) 对检索 进行性能评估. 查准率 P 和查全率 R 的定义为 P = r/m1, R = r/m2. (7) 式中，m1 是一次检索中返回的形状图像的个数，r 是一次检索中返回的形状图像中与查询形状相似的 个数，m2 是形状图像库中与查询形状相似的形状 总个数. 查准率是表征了查询的精度，查全率反映 了查询的鲁棒性. 一般随着查全率的增加查准率会 随之降低. 一个好的形状描述子在较高的查全率下 应仍具有较高的查准率. 3.4 实验平台和参数设置 实验平台采用一台 CPU 为奔腾 3.07 GHz 的 计算机，编程工具为 Matlab (版本 7.9). 对图像 库中的所有图像，提取形状的轮廓线后，重新采样 为 256 个点，并分别计算七种轮廓线函数及其快 速傅里叶变换. 多级三角形面积函数参数 K=6，每 级傅里叶描述子的长度 D 取为 8，即多级傅里叶 描述子总长为 48. 每个用于比较的轮廓线函数对 应的傅里叶描述子长度取为 32，文献 [7-10] 已验 证在这个长度下傅里叶形状描述子具有良好的检索 性能. 3.5 实验结果 对 MPEG-7 图像库中的每一个形状作为一个 查询图，计算它与所有形状相似性，然后按照相似 性大小进行排序，共进行 1400 次检索. 检索中返 回的形状图像个数 m1 的变化对应不同水平的查全 率和查准率，对于每一个查询图，统计出查全率从 10%∼100% 所对应的查准率. 将 1400 幅图像对应同 一查全率的查准率进行平均，可得查准率 - 查全率 曲线，如图 5 所示. 图 5 七种描述方法在 MPEG-7 形状图像库中查准率 - 查全 率曲线 Fig.5 Precision-recall curves using seven methods on the MPEG-7 database 从图中可以看出，MTAFD 在 MPEG-7 图像 库上取得了很好的检索性能，在相同查全率条件 下，MTAFD 具有最高的查准率. 例如，当查全率为 50%时，MTAFD 的查准率比经典的 CD 函数高出 14%，说明与单纯的整体特征相比，形状细节特征的 融入可以显著提高傅里叶描述子的描述能力. 与排 名第 2、第 3 的 PAF+CD 和基于拱高半径复函数的 傅里叶描述子 (arc-height radius Fourier descriptor, AHRFD) 方法相比，MTAFD 在查全率为 50%时查 准率分别高出约 5%和 13%，这表明 MTAFD 不但 包含了形状的细节和全局特征，能由粗到细的描述 形状特征，对于形状的仿射形变、缺失、噪声等多 种复杂变化也有较强的鲁棒性. 从而证明了多级三 角形面积函数的有效性. 为了比较 MTAFD 与其他傅里叶形状描述子 的计算复杂度，在同一实验平台下分别统计了不 同描述子完成轮廓线函数提取、轮廓线函数的傅 里叶变换以及形状匹配所需的时间. 将 MPEG-7 图像库中 1400 幅图像全部完成上述过程作为一组 实验，每个描述子均进行 20 组实验，每个阶段
·1206 北京科技大学学报 第35卷 所需时间为20组实验的平均值.七个描述子在各 参考文献 阶段所需的处理时间如表1所示.从表中可以看 出，七种傅里叶描述子完成匹配所需的时间差异很 [1]Datta R,Joshi D,Li J,et al.Image retrieval:ideas,in- 小.在三个阶段中，傅里叶变换所需时间最短，如 fluences,and trends of the new age.ACM Comput Surv, 2008,40(2):1 MTAFD进行傅里叶变换不到其匹配阶段所用时间 的2%.这得益于快速傅里叶变换的使用.七种傅里 [2]Huang W,Gao Y,Chan K L.A review of region-based image retrieval.J Signal Process Syst,2010,59(2):143 叶描述子完成轮廓线函数提取时间差别较明显，如 [3 Wang CZ,Yang Y D,Feng Y L,et al.Identification and MTAFD完成轮廓线函数提取需2.927ms,远小于 detection of deep-sea obstacles and terrains based on im- AHRFD、AF、PAF+CD以及FPD所需的时间.这 age processing.J Univ Sci Technol Beijing,2011,33(7): 主要是由于FPD每个点所对应的最远点不同，增 777 加了提取最远点函数的计算量.AHRFD在计算拱 (王财政，杨耀东，冯雅丽，等。基于图像处理的深海底障 高半径复函数时，轮廓线上每个点的拱高都通过计 碍物和地形识别及检测.北京科技大学学报，2011,33(7)： 算该点的半径及相应长度的弧线来确定，且拱高符 777) 号的判断也增加了AHRFD的计算复杂度，PAF的 [4]Adamek T,O'Connor N E.A multiscale representation method for nonrigid shapes with a single closed contour. 计算中也存在类似的情况.MTAFD在计算多级三 IEEE Trans Circuits Syst Video Technol,2004,14(5):742 角形面积时，所需参数少且原理相对简单，因而计 5]Wang B.A Fourier shape descriptor based on multi-level 算复杂度较小 chord length function.Chin J Comput,2010,33(12):2387 表1七种描述子在轮廓线函数提取、傅里叶变换及匹配阶 (任斌.一种基于多级弦长函数的傅立叶形状描述子.计算 段平均所需时间 机学报，2010,33(12)：2387) Table 1 Average processing time required in the feature (6]Zhang D,Lu G.Review of shape representation and de function extraction stage,Fourier transform stage and match- scription techniques.Pattern Recognit,2004,37(1):1 ing stage for seven descriptors ms [7 Zhang D,Lu G.Study and evaluation of different Fourier 描述子轮廓线函数提取时间傅里叶变换时间匹配时间 methods for image retrieval.Image Vis Comput,2005, MTAFD 2.927 0.020 1.736 23(1):33 AHRFD 15.200 0.036 1.713 8 El-ghazal A,Basir O,Belkasim S.Farthest point distance: CD 0.010 0.003 1.680 a new shape signature for Fourier descriptors.Signal Pro- PAF+CD 15.162 0.007 1.714 cess:Image Commun,2009,24(7):572 FPD 30.497 0.003 1.733 AF 1.703 9 Wang B.Shape description using arc-height radius com- 27.933 0.005 ARF 1.660 0.017 1.721 plex function.Acta Electron Sin,2011,39(4):831 (王斌.一种用于形状描述的拱高半径复函数.电子学报 由此可以看出，与其他傅里叶描述子相比， 2011,39(4:831) MTAFD进行形状描述和匹配所需的计算时间较 [10]Wang B.Shape retrieval using combined Fourier features. 少，在复杂度上具有明显的优势 Opt Commun.2011,284(14):3504 [11]Alajlan N,Rube I E,Kamel M S,et al.Shape retrieval us- 4结论 ing triangle-area representation and dynamic space warp- 提出了一种用于形状检索的基于多级三角形 ing.Pattern Recognit,2007,40(7):1911 面积函数的傅里叶描述子.它产生于轮廓的非等弧 [12]Bandera A,Marfil R,Antuinez E.Affine-invariant con- 长分割，可以很好地描述形状的整体特征和局部细 tours recognition using an incremental hybrid learning ap- 节特征，且具有仿射不变性.在标准的MPEG-7形 proach.Pattern Recognit Lett,2009,30(14):1310 状图像库上进行的形状图像检索实验结果表明，与 [13 Latecki L J,Lakamper R,Eckhardt T.Shape descriptors for non-rigid shapes with a single closed contour /Pro- 中心距离函数、面积函数、最远点距离函数、角度 ceedings of the IEEE Conference on Computer Vision and 半径复函数、拱高半径复函数以及混合傅里叶描述 Pattern Recognition.South Carolina,2000:424 子相比，基于多级三角形面积函数的傅里叶描述子 [14 Kunttu I,Lepist L.Shape-based retrieval of industrial 取得了最优的检索性能，且在计算复杂度上具有较 surface defects using angular radius Fourier descriptor 明显的优势 IET Image Process,2007,1(2):231
· 1206 · 北 京 科 技 大 学 学 报 第 35 卷 所需时间为 20 组实验的平均值. 七个描述子在各 阶段所需的处理时间如表 1 所示. 从表中可以看 出，七种傅里叶描述子完成匹配所需的时间差异很 小. 在三个阶段中，傅里叶变换所需时间最短，如 MTAFD 进行傅里叶变换不到其匹配阶段所用时间 的 2%. 这得益于快速傅里叶变换的使用. 七种傅里 叶描述子完成轮廓线函数提取时间差别较明显，如 MTAFD 完成轮廓线函数提取需 2.927 ms，远小于 AHRFD、AF、PAF+CD 以及 FPD 所需的时间. 这 主要是由于 FPD 每个点所对应的最远点不同，增 加了提取最远点函数的计算量. AHRFD 在计算拱 高半径复函数时，轮廓线上每个点的拱高都通过计 算该点的半径及相应长度的弧线来确定，且拱高符 号的判断也增加了 AHRFD 的计算复杂度，PAF 的 计算中也存在类似的情况. MTAFD 在计算多级三 角形面积时，所需参数少且原理相对简单，因而计 算复杂度较小. 表 1 七种描述子在轮廓线函数提取、傅里叶变换及匹配阶 段平均所需时间 Table 1 Average processing time required in the feature function extraction stage, Fourier transform stage and matching stage for seven descriptors ms 描述子 轮廓线函数提取时间 傅里叶变换时间 匹配时间 MTAFD 2.927 0.020 1.736 AHRFD 15.200 0.036 1.713 CD 0.010 0.003 1.680 PAF+CD 15.162 0.007 1.714 FPD 30.497 0.003 1.733 AF 27.933 0.005 1.703 ARF 1.660 0.017 1.721 由此可以看出，与其他傅里叶描述子相比， MTAFD 进行形状描述和匹配所需的计算时间较 少，在复杂度上具有明显的优势. 4 结论 提出了一种用于形状检索的基于多级三角形 面积函数的傅里叶描述子. 它产生于轮廓的非等弧 长分割，可以很好地描述形状的整体特征和局部细 节特征，且具有仿射不变性. 在标准的 MPEG-7 形 状图像库上进行的形状图像检索实验结果表明，与 中心距离函数、面积函数、最远点距离函数、角度 半径复函数、拱高半径复函数以及混合傅里叶描述 子相比，基于多级三角形面积函数的傅里叶描述子 取得了最优的检索性能，且在计算复杂度上具有较 明显的优势. 参 考 文 献 [1] Datta R, Joshi D, Li J, et al. Image retrieval: ideas, in- fluences, and trends of the new age. ACM Comput Surv, 2008, 40(2): 1 [2] Huang W, Gao Y, Chan K L. A review of region-based image retrieval. J Signal Process Syst, 2010, 59(2): 143 [3] Wang C Z, Yang Y D, Feng Y L, et al. Identification and detection of deep-sea obstacles and terrains based on image processing. J Univ Sci Technol Beijing, 2011, 33(7): 777 (王财政, 杨耀东, 冯雅丽, 等. 基于图像处理的深海底障 碍物和地形识别及检测. 北京科技大学学报, 2011, 33(7): 777) [4] Adamek T, O’Connor N E. A multiscale representation method for nonrigid shapes with a single closed contour. IEEE Trans Circuits Syst Video Technol, 2004, 14(5): 742 [5] Wang B. A Fourier shape descriptor based on multi-level chord length function. Chin J Comput, 2010, 33(12): 2387 (王斌. 一种基于多级弦长函数的傅立叶形状描述子. 计算 机学报, 2010, 33(12): 2387) [6] Zhang D, Lu G. Review of shape representation and description techniques. Pattern Recognit, 2004, 37(1): 1 [7] Zhang D, Lu G. Study and evaluation of different Fourier methods for image retrieval. Image Vis Comput, 2005, 23(1): 33 [8] El-ghazal A, Basir O, Belkasim S. Farthest point distance: a new shape signature for Fourier descriptors. Signal Process: Image Commun, 2009, 24(7): 572 [9] Wang B. Shape description using arc-height radius complex function. Acta Electron Sin, 2011, 39(4): 831 (王斌. 一种用于形状描述的拱高半径复函数. 电子学报, 2011, 39(4): 831) [10] Wang B. Shape retrieval using combined Fourier features. Opt Commun, 2011, 284(14): 3504 [11] Alajlan N, Rube I E, Kamel M S, et al. Shape retrieval using triangle-area representation and dynamic space warping. Pattern Recognit, 2007, 40(7):1911 [12] Bandera A, Marfil R, Ant´unez E. Affine-invariant contours recognition using an incremental hybrid learning approach. Pattern Recognit Lett, 2009, 30(14): 1310 [13] Latecki L J, Lakamper R, Eckhardt T. Shape descriptors for non-rigid shapes with a single closed contour // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. South Carolina, 2000: 424 [14] Kunttu I, Lepist L. Shape-based retrieval of industrial surface defects using angular radius Fourier descriptor. IET Image Process, 2007, 1(2): 231