《快速超复数傅氏变换和超复数互相关的新算法及应用.doc》由会员分享，可在线阅读，更多相关《快速超复数傅氏变换和超复数互相关的新算法及应用.doc（22页珍藏版）》请在三一办公上搜索。
1、快速超复数傅氏变换和超复数互相关的新算法及应用第1期2008年1月电子学报ACrAELECrRONICASINICAV01.36No.1Jan.2008快速超复数傅氏变换和超复数互相关的新算法及应用江淑红,郝明非,张建秋,胡波(复旦大学电子工程系,二海200433)摘要:超复数把彩色图像作为一个矢量整体进行处理,与传统算法相比,它能更好地描述图像的色彩关联,超复数互相关已广泛应用到彩色图像处理的各个领域.本文首先分析和介绍了目前的实现二维超复数傅氏变换和超复数互相关的快速方法,然后通过把超复数按实部和各个虚部展开,分别进行传统的快速傅氏变换,再把对应的单位虚向量还原,从而为超复数傅氏变换和超复
2、数互相关提出了一种新的快速算法.分析表明:本文提出的方法比目前现有的方法更简单易行,且计算量更小.最后,本文介绍了我们把超复数互相关技术应用到彩色目标跟踪上获得的一些新结果.关键词:超复数;图像处理;超复数傅氏变换;超复数互相关;目标跟踪中图分类号:TP391.4文献标识码:A文章编号:0372.2112(2008)01010006NovelAlgorithmsforFastHypercomplexFourierTransformandHypercomplexCorrelationwithApplicationsJIANGShuhong,HAOMing-fei,ZHANGJian-qiu,HU
3、Bo(DepartmentofElectronicEngineering,FudanUniversity,Shanghai200433,China)Abstract:Hypercomplexsencodethered,greenandbluechannelsofacolorimageasawholevectorforthefollowprocessing.Comparingwiththetraditionalmethods,thehypercomplexprocsingmethodsCanbetterdescribetheintrinsiccolorrelationshipsofimages.
4、Hypercomplexcorrelationtechniqueshavebeenwidelyusedinmanyapplicationsofcolorimageprocessing.”finispaperanalyzesandintroducesthefastalgorithmsofthe2-DhypercomplexFouriertransformandhypercomplexcorrelationbyusingthetraditionalcomplexfastFouriertransforms.And01117novelalgorithmsateproposed,whichrespect
5、ivelycalculateeachpartFouriertrasforlnbyFFralgorithmbymeansofseparatingahypercomplexintoarealpartandotherimaginaryparts.WhenrevertingthecorrespondingunitimagyoperatorsandcombiningtheresultsoftherealandimaginarypartsFouriertransforms,wecangetthehlexresults.Theanalyticalresultsshowthatouralgorithmsale
6、easiertoimplementandhavelesscomputingcomplexitythantheknownfastalgorithms.Finallysomenewresultsbyapplyinghypercomplexcorrelationintoobjecttrackingaleintroduced.Keywords:hypercomplex;imageprocessing;hypercomplexFouriertransform;hypercomplexcorrelationandobjecttracking1引言过去的一个世纪以来,互相关作为一种信号匹配技术,几乎应用到所
7、有的数字信号处理领域,但是其中大多数都局限于标量信号处理.而很多信号处理的应用都涉及到多维矢量,过去的算法常常是对各维信号进行标量处理,然后再简单合成,这样往往达不到很好的信号处理效果.近年来,超复数的应用就是针对多维矢量信号处理问题的.例如,在彩色图像处理方面,超复数在多维空间上把彩色图像作为一个矢量整体进行描述,提供了更准确的色彩信息.如今,超复数互相关技术已经应收稿日期:2006”07.12;修回日期:200708.12基金项目:国家自然科学基金(No.605720231用到彩色图像的图像配准,光谱分析2J,图像数据压缩和边缘检测E3等多个领域.因为超复数的一些特殊的数学性质(如:不满足
8、乘法交换律),所以.过去在使用超复数傅氏变换来快速计算超复数互相关时,需要应用超复数的运算规则重新进行超复数傅氏变换算法,而不能应用传统的复数快速傅氏变换()工具,很不方便.2000年,T.A.Ell等人提出了对超复数傅氏变换进行分解变换的方法4J,把它变成了两个传统复数傅氏变换对,这样就可以应用现在的FFr工具了.对于超复数互相关,由于不满足相关定律,所以T.A.Ell等人又提出一种方法,通过把超复数傅第1期江淑红:快速超复数傅氏变换和超复数互相关的新算法及应用101氏变换分解成平行和垂直的分量,来计算超复数互相关.本文分析和介绍了T.A.Eu等人的方法,同时提出了一种新的快速算法,把超复数
9、按实部和各个虚部展开,分别进行传统的快速傅氏变换,然后把对应的虚向量还原,该方法比目前现有的方法更简单易行,且计算量更小.最后,本文介绍了我们把超复数互相关应用到彩色目标跟踪上的一些工作.很多目标跟踪算法都是提取彩色目标的灰度信息作为跟踪特征,丢失了目标的色彩信息;而目前几乎所有的彩色目标跟踪方法都是对灰度图像处理方法的简单扩展,大多数都是对RGB,YIQ或HSI空间各分量的简单合成,例如,取各分量的平均值或把各分量分别处理的结果进行相加,这样的处理方法不能代表彩色图像的色彩关联.而使用超复数互相关的方法,把彩色图像作为一个矢量整体进行处理,则提供了目标的完整色彩特征,对目标的匹配提供了更多有
10、用信息,可以达到更好的跟踪效果.2超复数傅氏变换的快速计算超复数可以看成是复数的推广,它的表达式为:al+a2i1+a3i2+aninl(1)其中,a1,a,a为实数,il,i2,i一l为虚数单位.超复数把彩色图像作为一个矢量整体进行描述,彩色图像的RGB模型可以表示为如下的无实部的纯超复数:.厂(m,n)=R(m,n)i+G(m,n)j+B(m,n)k(2)规定:i2=j2=,k.l-一材:f,:一政:_(3)超复数乘法满足结合律和分配律,不满足交换律.超复数的二维傅氏变换和逆变换l6J为:=篓胁(4)f(mIt)=F-R=(5)其中为单位虚向量,可以取强度图像矢量,I=(f+)/3.在超复
11、数图像空间,任何色彩向量与轴的平行分量代表该向量的亮度,与该轴的垂直分量代表该向量的色度L4J.(m,n)和(,u)分别为时域和频域中的坐标.因为超复数的相乘不满足交换律,所以将式(4)中的指数项移到厂(m,n)左边时得到的结果是不同的,对应的左变换形式为和F一.我们以右变换为例,介绍一下如何利用现在的传统复数的快速傅氏变换(设复数傅氏变换为FFTr,实数傅氏变换为R兀1)工具来计算超复数傅氏变换.设四元超复数(称为四元数)为:q(m,n):a(m,n)+b(m,n)i+C(m,n)j+d(m,n)k(6)其中实部S(q):a,虚部V(q):bi+cj+般.它的傅氏右变换为:u)=N-I6f+
12、cjet(7)2.1分解变换法T.A.Ell等人提出了一种分解变换方法,通过另取三个正交的单位虚向量,Il,I2,I3,变换四元超复数的表达式,从而把超复数傅氏变换,转变成2次复数FFr运算.q:a+,Ilb+,I2C+,I3d(8)令,I3=,I2l,则:q=(a+,Ilb)+,I2(c+,Ild)=ql+2q2(9)根据文献4,可以取:,Il:(i+.,+)/32=(一)/2(10),I3:2,Il:(2ik)/46计算得:a,=ab=(b+C+d)c,_(cd)(11)d=(2bcd)这样,超复数傅氏右变换为:=N-!(qlg2)e-Itj2t(12)由于;=i=一1,而q1,q2都可以
13、看作含有虚数单位,I的二元复数,所以可以把式中的单位虚向量,I先用i替换,用传统的复数FFTr工具计算出a+的傅氏变换ql,然后把它的虚部乘以,Il,即可得到:Q1(V,u).T-real(ql胛)+,I1?imag(qlFFr)(13)这样,超复数傅氏变换转变成复数ql和q2的复数FFTr运算:(V,u)=Q1(V,u)+2Q2(V,u)=real(ql)+1imag(ql)+2real(q2)+,Il?imag(q2FFr)(14)因为,Il:,I=(i+)/3,各个虚部相等,所以计算(.?实数)只要进行1次实数乘法.而,I2=(.,一)/2,所以计算2与四元数相乘,要进行24=8次实数乘
14、法.计算式(14)共需要2次复数FFTr和IOMN次实数乘法.式(14)给出的是超复数的傅氏右变换,文献4给102电子学报2008正出的是左变换,左变换时,式(14)要右乘:,即:rL=Q1(,u)+Q2(,u)2(15)值得注意的是,此时3:,所以对同样的,p,d的符号相反,有d:(一2b+c+d)/6.类似地,可由传统复数傅氏逆变换(IFFr)得到超复数傅氏逆变换.由于计算二维F丌和IF丌均需要MN?loge(删)次实数乘法【,而计算式(11)的”分解变换”需要3MN次实数乘法,所以”分解变换法”计算超复数傅氏变换和超复数傅氏逆变换的计算量均为:MN?(21og2(MN)+13)(16)对
15、于彩色图像RGB模型,因为无实部,所以式(9)中g:btt,则计算Q(,”)只要进行b的实数傅氏变换(RFF):Q1(u):real(6)+limag(6)(17)由于二维实数傅氏变换的算法复杂度为(0.5MN)?log2(删)【,所以采用”分解变换法”计算彩色图像的超复数傅氏变换的计算量为:MN?(1.5log2(MN)+13)(18)而采用彩色图像进行超复数傅氏变换后的结果是四元数,所以用”分解变换法”对其频域的结果进行超复数傅氏逆变换的计算量仍然为式(16).2.2一种更简单的转换方法根据分配律,可以把式(7)展开成四个傅氏变换项,例如,其中第二个傅氏变换项为:(m=0n=0)(19)b
16、为实数,而=i=一1,与式(13)类似的,可以用传统实数傅氏变换RYI”来计算式(19):式(19)=i(real(bavr)+?imag(bavr)(20)这样,就利用RYI”得到了超复数傅氏右变换:(,u)=(real(口RFr)+imag(口RFr)+i(real(bRvr)+imag(bRvr)+J(real(cRFr)+imag(cRFr)+k(real(dRvr)+imag(dRvr)(21)类似的,可利用实数的快速傅氏逆变换(tarr)得到超复数傅氏右逆变换:F(,u)=(real(Amrr)+imag(Amrr)+i(real(BIRVr)+imag(Bmvr)+J(real(
17、Cmvr)+imag(Cmvr)+k(real(Diavr)+imag(Dmvr)(22)而要得到超复数的傅氏左变换和左逆变换F,只要把式(21)和式(22)中左乘i,.,k变成右乘i,.,露,即可.计算(?实数)只要进行1次实数乘法,所以,用本文方法的计算一个超复数傅氏变换(或逆变换),需要4次RFT运算和4MN次乘法,计算量为:MN?(21og2(MN)+4)(23)对于彩色图像RGB模型,因为无实部,则对其时域进行傅氏变换(或逆变换)只要3次肿(或唧)运算和3MN次乘法.用本文方法的计算量为:MN?(1.5log2(MN)+3)(24)而用该方法对彩色图像经过变换后在频域内的结果进行超复
18、数傅氏变换(或逆变换)的计算量仍然为式(23).本文方法不需要式(10)的单位虚向量替换和式(11)的分解变换,要比T.A.Ell等人的”分解变换法”更加简单易行,而且计算量更小.在进行图像处理时,若图像尺寸为?N:320240,loge(320240):16.2288,则本文方法与”分解变换法”的计算量的比值为:731815162288(25)式()一.+13一,或者:80(26)3超复数互相关的快速计算两幅彩色图像的超复数互相关的形式为:cr(myn):_,*g=,(,),)=0=0(表示g的共轭)(27)它比传统互相关更能体现图像的色彩关联,它表达了两帧图像色彩之问的映射和旋转,找到超复
19、数互相关的模值最大值,可以进行图像配准,同时得到色彩的旋转轴和旋转角度信息n,减少光照变化等的影响,还可以反向旋转,进行图像色彩校正.下面介绍如何利用传统F丌工具来计算超复数互相关.3.1分解垂直平行向量法超复数乘法不满足交换律,所以彩色图像超复数互相关不满足相关定律,不能由两幅图像各自的傅氏变换相乘的逆变换得到.对于纯四元数g,可以把它分解为:与另一纯四元数P平行和垂直的向量Is:g=(q+PqP)/2,q上Pg:(g一)/2gP(28)对于实部不为0的四元数,把它的虚部(q)按式(28)分解为V(g)和V(口),而把其实部S(口)加在平行分量上:g=V(q)q=S(q)+.(q)(29分解
20、向量的乘法运算满足如下关系:第l期江淑红:快速超复数傅氏变换和超复数互相关的新算法及应用103Pql=qP,Pq【=q【P(30)计算,需要33+43=21次实数乘法,所以一次分解垂直平行向量需要21次实数乘法.T.A.E和S.J.Sangwine等人提出一种方法,通过把超复数傅氏变换分解成和强度图像矢量平行和垂直的分量,来计算超复数互相关1.5.8,以下给出两种形式:cr(m,n)=FR(,u)(,u)+(,u)丽)(31)cr(m,n):F一(FR(v,u)【v,u)+Fv,u)lv,u)(32)(其中G【(,)llp,G一_(,)J_p)式(31)一共要进行2次彩色图像的超复数傅氏变换(
21、计算量为式(18),对频域结果进行傅氏变换和傅氏逆变换各1次(计算量为式(16),2MN次四元数乘法和MN次”分解向量”运算,而两个四元数相乘(FRGR),要进行4X4=16次实数乘法,综上得,式(31)计算量为:MN(216+21)+MN(71og(MN)+52)=MN.(7log2(MN)+105)(33)式(32)要进行2次彩色图像的超复数傅氏变换,1次彩色图像的超复数逆傅氏变换m,Yn)igo(m,Yn).,一gs(m,Yn)(35)一l一lcr=(,y)gR(m,Yn)+,c(,y)?gc(m,Yn)+(,y)gs(m,Yn)+iEA(,Y)gc(m,Yn)一fc(,y)gs(m,Y
22、n)+EA(,Y)gs(m,Yn)(,y)gR(m,Yn)+kEft(,Y)gn(m,Yn)=OY=O一(,y)gc(m,Yn)(36)对上述的每一个求和项,可以先用传统实数傅氏变换RfTr,再进行复数傅氏逆变换IFFr快速求解.以第2项为例:第2项:l?IFFr踟一.厂cR(37)两个复数相乘(G),要进行22:4次实数乘法.用本文方法求解两幅彩色图像的超复数互相关,需要6次RFT,4次IFFT运算和9MN次复数乘法,计算量为:MN(71og(MN)+36)一(38)本文方法比”分解垂直平行向量法”简单得多,计算量也更少,若图像的尺寸为MN=320240,则两种方法算法计算量的比值为:形式一
23、:萎籍=716.2288而+36=68.4%(39)形式二:羹=董=71.1%()4目标跟踪的应用超复数互相关技术已经应用到彩色图像的图像配准l,光谱分析,图像数据压缩和边缘检测等多个领域.而我们第一次把超复数互相关应用到彩色目标跟踪上来.我们用以目标中心位置(,Yc)为中心的椭圆表示目标j.跟踪过程中若发生部分遮挡,总是目标的边缘被阻挡,为了增强对部分遮挡的抗干扰能力,越远离目标中心就应该赋予越小的权值,所以对每一点进行中心距离加权:Wd()()=1一dj(41)为了保证特征具有各向同性,所以把椭圆内各像素的距离归一化到单位圆内,则有:d=(Xc)/Lx).+(YYc)/).(42)(其中和
24、为目标椭圆的横轴和纵轴)设图像目标模板为.厂(),=(,y)表示目标像素的坐标,第k帧图像待匹配图像为g(+),=(m,n)表示匹配点在图像中的相对移动.厂()和g(+)都是彩色图像的RGB超复数形式.因为互相关的配准曲面过于平滑,没有明显的峰值,所以在图像匹配中使用”超复数相位互相关”l,即在频域中把互相关的结果除以模值,表示为:(,g)=F-Ri特j(43)找到(.厂,g)的模值最大值,即为图像匹配点.由于可以使用快速傅氏运算,大大提高了运算速度,所以在目标跟踪中可以在一定的搜索区域内采用”遍历搜索”进行目标模板匹配,同时满足实时性要求.第k帧图像中,图像匹配的搜索区域以第k一1帧的目标位
25、置为中心.做”相关”运算,要求两幅图像必须尺寸一样,我们通过把模板椭圆之外的像素补零,把目l04电子学报2008正标模板从椭圆尺寸扩充到搜索区域尺寸.所以目标图像的权值为:,f()=1一,(椭圆内,中心距离加权)a.r10,(其他像素不参与匹配,权值为0)(44)对于待匹配图像,g()在搜索范围内的每一个像素都要参与图像匹配,所以对所有像素a()=1;如图1所示:()目标模板(6)待匹配图像图1目标模板和待匹配图像的权值值得注意的是,由于第帧图像待配图像为g(+m,Y+n),所以匹配的是CI”(一m,一n),在运算中以下面所示矩阵的右下角为起点.出了一个车辆跟踪的实验例图2相关函数的示意图子.
26、跟踪目标为蓝色小车,而在第.i帧图像中又有一辆与蓝色小车形状相同的红色小车.我们把色彩度转化为灰度:厂(,Y)=(,Y)+G(,Y)+(,Y)/3(45)然后采用传统的实数互相关匹配进行目标跟踪,则得到归一化的相位互相关的曲面如图3(d)所示,相位互相关的最大值为红色小车所在位置,发生了误匹配.而如果我们采用本文提出的中心距离加权的超复数互相关匹配进行目标跟踪,彩色图像表示为超复数形式,则归一化的超复数相位互相关的曲面如图3(e)所示,最大值为蓝色小车所在位置,跟踪目标正确.而)跟踪目标(6)填充补0后的跟踪目标模板(c)待匹配的第k帧图像,方框内为搜索区域(a9传统的相位互相关匹配(=(+G
27、+)/3(P)中心距离加权的”超复数相位互相关匹配图3目标跟踪实验且可以看出,图3(e)的曲面比图3(f)平坦得多,这是因为应用了”中心距离加权”,增强了抗干扰能力的缘故.分析该跟踪实验的色彩数据表明,红色小车的红色()分量值很大,但绿色(G)和蓝色(分量的值较小,使得经过式(45)进行RGB分量平均后,灰度值和蓝色小车的目标模板就差不多了,而第k帧图像中的蓝色150小车的每一个分量值都比目标模板小一些,所以采用传统的实数互相关匹配,会导致目标的误匹配.而超复数互相关匹配,就可以避免这种情况.“超复数互相关”只是作为一个目标跟踪的匹配准则,该方法还可以和其它一些目标跟踪的策略相结合,以达到更好
28、的跟踪效果.如:可以对目标的色彩和形状186420,01864200,0第l期江淑红:快速超复数傅氏变换和超复数互相关的新算法及应用105信息进行数据融合,可以对跟踪目标进行运动估计,也可以插值比较分析进行目标模板的变尺度更新,一些实数空间中的目标模板的更新策略和方法同样也可以应用到超复数空间来.5结束语超复数的应用主要是针对多维矢量信号处理问题的.在彩色图像处理方面,超复数互相关技术已经应用到图像配准等多个彩色图像处理领域.本文分析和介绍目前的利用传统FFT工具实现超复数傅氏变换和互相关的方法,同时提出了另外的快速算法,该方法比目前的快速算法更加简单易行,而且计算量更小:对于320240的彩
29、色图像,分析的结果表明:本文方法分别比目前的超复数傅氏变换和超复数互相关快速算法的计算量减少了20%和30%.本文还介绍了如何把超复数互相关应用到彩色目标跟踪上的一些工作.该方法把彩色图像作为一个矢量整体进行处理,提供了目标的完整色彩特征,同时与”目标中心距离加权”相结合来提高目标跟踪的抗干扰能力,更好地实现了对彩色目标的准确跟踪.参考文献:1CEMoxey,SJSangwine,TAEl1.HypercomplexcorrelationtechniquesforvectorimagesJ.1EFF.TransonSignalProcessing,2003,51(7):19411953.2Ja
30、-HanChang,Soo-ChangPei,JianJiunDing.2Dquaternion作者简介江淑红女,1977年l2月生,1999年毕业于北京邮电大学通信1程专业,现为复旦大学电子工程系博士研究生.主要从事数字信号与图像处理,智能仪器等研究.Email:041021019张建秋男,1962年生,博士生导师,IEEE高级会员,现任复旦大学电子工程系教授.主要研究方向:信息处理理论及其在新型传感器,仪器和测量,图像处理中的应用.Email:jqang0l(本文通信作者)FourierspectralanalysisanditsapplicationsA.Proceedingsof匹EI
31、nternationalSymposiumonCircuitsandSystems(ISCAS04)C.皿Press,2326May2004,3:11I-2414.3sJSangwine.ColorimageedgedetectorbasedonQcvlJJ.IEE日ectron.Letter,1998,34(10):969971.4TAEH,sJsangwine.Decomtxitionof2DhypercomplexFouriertransformsintopairsofcomplexFouriertransformsA.EuropeanSignalPlxssingConference(E
32、US)C_2000,151154.5TAEU,SJSangwine.HypercomplexWiener-KhintchinetheoremwithapplicationtocolorimagecorrelationAJ.皿InternationalConferenceonImageProcessing(IC200o)lCJ.皿Press,Sept1013,2000,2:792795.6sJSangwine,TA助,111ediscreteFouriertransformofacolourimageA.JMBlackledge,MJTumer.ImageprocessingIImathemat
33、icalmethods,algorithmsandapplicationsC.Chichester.U.K.:EmSHorwood,2000:430441.7PDuhame1.ImplementationofsNt-mdixFFFalgorithmsforcomplex,realandreal-symmetricdatalJJ.皿TransonAcoust,Speech,SignalProcessing,1986,ASSP-34(2):285295.8cEMoxey,TAEu,sJSangwine.HypercomplexoperatorsandvectorcorrelationA.Europ
34、eanSignalProcessingConfer-ence(EUs)C.Toulouse,France,Sept0306,2002.247250.9DComaniciu,PMeer.Kernel-basedobjecttrackinglJJ.啦TransonPatternAnalysisandMachineIntelligence,20O3,25(5):564577.郝明非男,1980年l2月生,2003年和2007年毕业于复旦大学电子工程系,分别获工学学士和理学硕士学位.主要从事图像拼接方面研究.胡波男,1968年生,博士生导师,IEEE电路与系统分会肓信号处理技术委员会委员,现任复旦大学电子工程系教授.主要研究方向:数字信息处理,数字通信等方面的算法和实际应用.
