对离散序列到:
进行一维离散傅里叶变换(DFT),得
傅里叶系数
组成的一维行向量就是傅里叶描述
子,可以代表目标形状边界所具有的特征。将傅里叶系数进行DFT反变换,就可以还原表示形状边界的复数序列
通常,我们只保留傅里叶系数的前K个系数作为傅里叶描述子就可以近似的表示目标形状,换言之,傅里叶系数的低频系数决定了目标的整体形状,高频系数描述的是形状的细节部分但是,傅里叶描述子中存在的主要问题是应该保留多少个傅里叶系数来表示形状,或者说特征向量的维数应该怎样选取。通常來说,保留的傅里叶系数越少,描述子的鲁棒性越好,但其形状之间的区分能力越弱;反之,如果保留的傅里叶描述子越多,则反应形状细节部分特征的能力越强,但对噪声也越敏感。所以,目前没有一个通用的选择标准,需要在实验中根据具体的应用来进行特征向量维数的最优选择。
一维傅里叶描述子的不变性构造
利用傅里叶系数组成的特征向量并不具有形状的平移、旋转和尺度变换不变性。由于边界的起始点是任意选择的,所以描述子也需要具备对起始点变化的不变性。
当形状发生平移变换时,复数坐标序列在水平和垂直方向上都附加一个位移 常量,变为
根据傅里叶
变换的性质,当函数加上一个常量后,傅里叶变换的结果除直流分量a(0)以外,对其他傅里叶系数没有影响,如下式所示,我们可以通过舍弃a(0)项的方法解决。
4
当形状发生旋转变换,旋转角为θ时,复数坐标序列变为
同
样根据傅里叶变换的性质,此时的傅里叶变换结果为如下式所示,因此,旋转变换只是带给每一个傅里叶系数都乘上一个常数项的影响,所以我们可以通过选取傅里叶系数的幅度值,忽略其相位值的方法解决。
当形状发生尺度变换,尺度变换因子为λ时,复数坐标序列变为
。
此时DFT变换结果也是将每一个傅里叶系数都乘以一个λ因子,如下式所示,我们可以通过将傅里叶系数的每一项都除以a(l)项,消除尺度因子对傅里叶系数的影响。
当形状轮廓的起始点移位
。
此时DFT变换结果下式所示。此时傅里叶系数的变化也可以通过只选取傅里叶系数的幅度值解决,或者也可以将起始点的变换看作形状边界进行了一定角度的旋转变换。
个像素点时,复数坐标序列变为
因此,进行平移、旋转和尺度变换归一化后的一维傅里叶描述子表示为:
5
其中,K为选取的傅里叶描述子的个数。
傅里叶分析的理论始于1822年,当时是由法国数学家傅里叶(Fourier J)提出的傅里叶级数的概念。目前,傅里叶理论已经发展了近二百年,作为一种有力的信号分析处理工具,广泛应用在各个领域,但在20世纪六十年代初,才被Cosgriff引用到形状分析领域中来目前,基于一维傅里叶变换的1-D傅里叶描述子和基于二维傅里叶变换的2-D傅里叶描述子已经成为形状分析领域的经典算法。
3 二维傅里叶描述子
一维傅里叶描述子是基于轮廓的形状描述子,它只利用形状图像边界上的像素信息,所以1-DFD依赖于边缘检测算子对形状边界曲线的准确提取,但是由于其算法简单,计算速度快,适用于形状比较简单和对检索速度要求比较高的情况,但是其平均检索精度还有待进一步提高。二维傅里叶描述子是基于区域的形状描述子,它利用了图像整个形状区域的像素信息,因此应用范围广,检索准确率高并且形状区分能力强,但是由于其信息量大,算法复杂,所以对形状图像的特征提取比较长_。可以说,1-DFD和2-DFD有各自的优缺点,需要根据具体的应用要求进行选择。 经典的2-D傅里叶描述子 如果对一幅离散的形状图像离散傅里叶变换,得到:
直接进行二维
其中U和V分别代表频域图像中的第U行和第V列的频域信息,对形状图像应用二维傅里叶变换可以完全不用考虑形状的边界信息,但是这样得到的傅里叶描述子是不具有旋转不变性的。经典的2-D FD是由Zhang和Lu在2002年提出的,也称作GFD(GenericFourier Descriptorp],他们首先想到的是将二维DFT变换应用在极坐标系下采样的图像中,得到
其中,
6
R 和T 分别
为径向频率和角频率。然而由于式中的使得
存在于正弦函数中,
的物理意义不再是第m个角频率,因此提取出的特征向量PF失去了
在环向方向上的物理意义。为了解决这个问题,Zhang和Lu提出了一个修正的极坐标傅里叶变换。即首先将形状图像
放在极坐标空间中进行重新采
样得到置在形状的质心其中:
,其中极坐标的原点放
.上 R是区域形状内的半径。
然后将
重新放回至二维笛卡尔坐标系中进行表示,得到一幅横坐标为θ,
纵坐标为r的矩形图像。对其进行二维DFT变换,得到:
其中
R和 T 同样分
别为径向频率和角度频率。接下来需要考虑特征向量的平移、旋转和尺度变换的不变性。首先得到的特征向量FD2是具有平移不变性的,因为在极坐标中是以图像的质心为坐标原点的。为了得到尺度不变性,我们需要将特征向量中的第一个系数除以区域形状内部的面积,而其他的系数除以第一个系数
7
来进行尺度归一化。旋转不变性可以通过忽略傅里叶系数的相位信息,只保留其幅值信息来得到保证。因此,具有平移、旋转和尺度变换不变性的特征向量FD2为:
其中area为区域形状内部的面积,m为选取的径向频率系数的个数,n为选取的环向频率系数的个数。与一维傅叶描述子相同,一般根据其体情况来选取FD2其中的一部分低频系数组成二维傅里叶描述子特征向量。
8
参考文献
[1]章毓晋等.阁像工程[M].北京:洁华大学出版社,2005.
[2] 丁险峰,吴洪,张宏江等.形状匹配综述[J].自动化学报,2001' 27(5): 678-694. [3] Zhang D S, Lu G Review of shape representation and description techniques [J].Pattern Recognition, 2004, 37(1): 1-19. [4]Conell
J H,Brady M. Learning shape descriptions[C]// Proceedings
ofInternational Joint Conference on Artificial Intelligence, 1985: 922-925.
[5]周瑜,刘俊涛,白翔.形状匹配方法研究与展望[J].自动化学报,2012,28(6):879-910.
[6]赵小川.现代数字图像处理技术提高及应用案例详解[M],北京?.北京航空航天大学出版社,2012.
[7]Bartolini L, Ciaccia P, Patella M. WARP:Accurate retrieval of shapes using phaseof Fourier descriptors and time warping distance [J]. IEEE Transactions on PatternAnalysis and Machine Intelligence, 2005, 27(1):142-147 [8]冈萨雷斯.数字图像处理(第二版)[M].北京:电子工业出版社,2010.
9