·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 dis￾tance, 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