毛玉妃 王 斌，2 舒華忠

(1東南大學(xué)影像科學(xué)與技術(shù)實(shí)驗(yàn)室，南京 210096)

(2南京財(cái)經(jīng)大學(xué)江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室，南京 210046)

基于變換域形狀描述子的圖像檢索方法的比較與分析

毛玉妃1王 斌1，2舒華忠1

(1東南大學(xué)影像科學(xué)與技術(shù)實(shí)驗(yàn)室，南京 210096)

(2南京財(cái)經(jīng)大學(xué)江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室，南京 210046)

為了更好地了解變換域方法在圖像檢索中的檢索效果，比較分析了Zernike矩、GFD、PCET、RCFT和RFMT等現(xiàn)有的5種基于變換域的形狀描述方法.分別在不變性、計(jì)算復(fù)雜性、噪聲魯棒性、有效特征數(shù)的選取方面對(duì)其進(jìn)行了深入的分析和比較.選用MPEG7 CE Shape-1 Part B中的1 400幅圖像構(gòu)成的圖像庫對(duì)這些方法進(jìn)行檢索和性能測(cè)試，并實(shí)際應(yīng)用于由500幅病例圖構(gòu)成的圖像庫的醫(yī)學(xué)圖像檢索.在研究噪聲影響時(shí)，對(duì)各測(cè)試集圖片加上不同程度的高斯噪聲.通過比較分析及實(shí)驗(yàn)結(jié)果驗(yàn)證，Zernike矩和GFD方法的檢索性能最好，有良好的抗噪性，因而適合于醫(yī)學(xué)圖像檢索的實(shí)際應(yīng)用.

圖像檢索;形狀描述;變換域分析;醫(yī)學(xué)圖像檢索

在基于內(nèi)容的圖像檢索中形狀特征是一個(gè)很重要的方面.因?yàn)樾螤钍强坍嬑矬w最本質(zhì)及最難描述的圖像特征之一.形狀特征又可分為空間域特征和變換域特征.變換域具有把握?qǐng)D像全局特性及抵抗圖像噪聲等天然優(yōu)點(diǎn)，如 DCT(discrete cosine transform)域和 DFT(discrete Fourier transform)域的能量分布集中、DWT(discrete wavelet transform)域的多分辨率分析和Zernike變換的RST(rota-tion，scale and translation)不變性等.能量分布集中意味著只需用較少的特征就能大致表示一幅圖像，RST不變意味著它能很好地應(yīng)用于圖像檢索中.目前常見的用于圖像檢索的變換域方法有矩技術(shù)(包括幾何矩［1］、Zernike 矩［2］、Legendre 矩［3］及Fourier-Mellin 矩［4］)、DWT［5］、傅里葉算子(包括一維 FD［6］(Fourier descriptor)和二維 GFD［6］)、Radon、ART［7］(angular radial transform)等.矩技術(shù)(除幾何矩)有很好的旋轉(zhuǎn)不變性，而平移不變性和尺度不變性可通過對(duì)圖像進(jìn)行預(yù)處理實(shí)現(xiàn).單獨(dú)的小波和Radon變換很難實(shí)現(xiàn)RST不變性，但可通過將小波和Radon變換與其他變換結(jié)合使用實(shí)現(xiàn)RST不變性.

本文詳細(xì)分析比較了Zernike矩、GFD、PCET、RCFT和RFMT等5種具有RST不變性的變換域方法.將這5種方法應(yīng)用于圖像檢索上，并且在RST不變性、噪聲魯棒性、時(shí)間復(fù)雜度和有效特征數(shù)等方面詳細(xì)比較了這5種方法在圖像檢索中的檢索效果.最后將這些檢索方法應(yīng)用在醫(yī)學(xué)圖像檢索上，驗(yàn)證其在醫(yī)學(xué)圖像檢索上的有效性.

1 5種變換域形狀描述方法簡介

一種特征能否用于圖像檢索主要取決于其有無RST不變性.也就是圖像經(jīng)過平移、旋轉(zhuǎn)及尺度變換后，該圖像計(jì)算出的特征值與原圖像計(jì)算出的特征值的一致程度.下面主要圍繞5種方法的RST不變性上展開研究.

1.1 Zernike矩

Zernike矩因其具有優(yōu)良的旋轉(zhuǎn)不變性而在模式識(shí)別等領(lǐng)域得到廣泛的應(yīng)用.在圖像分析中，由于Zernike多項(xiàng)式的正交性，可以使信息冗余達(dá)到最優(yōu).雖然Zernike矩具有旋轉(zhuǎn)不變性，但卻不具備尺度不變性，因此在采用Zernike矩描述形狀時(shí)，首先需要進(jìn)行歸一化處理［2］.MPEG-7標(biāo)準(zhǔn)中已將Zernike矩列為一種標(biāo)準(zhǔn)的區(qū)域描述符.

對(duì)H×W的圖像f(x，y)，Zernike矩定義如下:

式中，p，q為整數(shù)，且為偶數(shù);r為點(diǎn)(x，y)到形狀質(zhì)心的半徑;θ為r與x軸的夾角.

Zernike矩RST不變性的實(shí)現(xiàn)方法如下:

1)旋轉(zhuǎn)不變性 通過取Zpq模實(shí)現(xiàn)旋轉(zhuǎn)不變.

2)平移不變性 通過將圖像的質(zhì)心移到圖像的中點(diǎn)實(shí)現(xiàn)平移不變.

3)尺度不變性 通過除以圖像的質(zhì)量(即幾何矩［1］m00)，實(shí)現(xiàn)尺度不變.

1.2 GFD

對(duì)圖像直接進(jìn)行二維離散傅里葉變換不具有旋轉(zhuǎn)不變性，故需對(duì)圖像進(jìn)行一定處理.首先將GFD極坐標(biāo)下的圖像展開為笛卡爾坐標(biāo)下的矩形圖像［6］，進(jìn)行極坐標(biāo)變換后將圖像的旋轉(zhuǎn)轉(zhuǎn)化為平移.然后對(duì)展開后的圖像進(jìn)行二維離散傅里葉變換，即可實(shí)現(xiàn)旋轉(zhuǎn)不變.二維離散傅里葉變換式為

式中，R，T分別為徑向頻率分辨率和角向頻率分辨率，0≤r＜R，0≤x＜T;η，φ 分別為徑向頻率和角向頻率.

GFD方法RST不變性的實(shí)現(xiàn)方法如下:

1)旋轉(zhuǎn)不變性 極坐標(biāo)上的旋轉(zhuǎn)反應(yīng)在直角坐標(biāo)上是平移，而平移表現(xiàn)在傅里葉變換上是相位的改變，故可通過取模實(shí)現(xiàn)旋轉(zhuǎn)不變.

2)平移不變性 通過在計(jì)算時(shí)將質(zhì)心設(shè)置為原點(diǎn)，實(shí)現(xiàn)平移不變.

3)尺度不變性 對(duì)計(jì)算得出的系數(shù)進(jìn)行如下歸一化處理，就可實(shí)現(xiàn)尺度不變

式中，A為轉(zhuǎn)換為極坐標(biāo)前的面積.

1.3 PCET

PCET方法的變換式定義［8］為

式中，Hnl(r，θ)=Rn(r)ejlθ，Rn(r)=ej2πnr2;n為階數(shù);l為重復(fù)度.

PCET的定義與GFD相似，僅是內(nèi)核有差異.從式(4)可以看出，隨著階數(shù)的增大，GFD的特征值G趨于0，而高階PCET特征值并不趨于0.

PCET方法實(shí)現(xiàn)平移不變、旋轉(zhuǎn)不變與尺度不變的處理方法與GFD方法相同.

1.4 RCFT

RCFT方法是通過幾種變換的組合實(shí)現(xiàn)RST的不變性.首先通過倒角距離變換［9］(chamfer distance transform)將一幅圖像分成多幅相似的圖像.然后對(duì)倒角距離變換后的每幅圖像f(x，y)進(jìn)行Radon變換，即

式中，δ(·)為狄拉克函數(shù)(當(dāng)x=0 時(shí)，δ(x)=1，否則δ(x)=0);ρ為投影線到原點(diǎn)的距離;φ為投影線的方向.在Radon變換的基礎(chǔ)上再進(jìn)行RTransform［10］，即

最后，對(duì)每個(gè)Rf(φ)進(jìn)行一維傅里葉變換.

由于直接對(duì)圖像進(jìn)行Radon變換和R-Transform，圖像的許多信息會(huì)丟失.而進(jìn)行倒角距離變換后，可以通過取不同的灰度得到多幅圖像，這樣既可以提取到輪廓信息，又能提取到內(nèi)部結(jié)構(gòu)信息.

RCFT方法RST不變性的實(shí)現(xiàn)方法如下:

1)旋轉(zhuǎn)不變性 旋轉(zhuǎn)表現(xiàn)在R-Transform上是平移變換，通過取一維傅里葉變換的模消除旋轉(zhuǎn)的影響.

2)平移不變性 通過Radon變換與R-Transform共同作用實(shí)現(xiàn)平移不變.

3)尺度不變性 由于圖像放大/縮小α倍，RTransform放大/縮小α3倍，故可實(shí)現(xiàn)尺度不變.

1.5 RFMT

RFMT方法［11］也是通過幾種變換的組合來實(shí)現(xiàn)RST不變.首先將圖像的質(zhì)心移到圖像中心以實(shí)現(xiàn)平移不變，然后對(duì)圖像進(jìn)行Radon變換(見式(5)).

在Radon變換的基礎(chǔ)上進(jìn)行Fourier-Mellin變換，即

RFMT方法RST不變性的實(shí)現(xiàn)方法如下:

1)旋轉(zhuǎn)不變性 經(jīng)Radon變換后可將旋轉(zhuǎn)變換轉(zhuǎn)變成平移變換，平移變換經(jīng)過Fourier-Mellin計(jì)算后只表現(xiàn)在相位的改變上，所以可通過取模消除圖像旋轉(zhuǎn)的影響.

2)平移不變性 通過將圖像的質(zhì)心移到圖像的中點(diǎn)，實(shí)現(xiàn)平移不變.

3)尺度不變性 經(jīng)Radon和Fourier-Mellin變換后，尺度變換只表現(xiàn)在系數(shù)的改變上，故通過除以該系數(shù)就能實(shí)現(xiàn)尺度不變.

2 性能比較分析

以下從RST、噪聲、時(shí)間復(fù)雜度、有效特征數(shù)等方面分析比較5種變換域形狀描述方法的性能.

2.1 RST不變性

前面對(duì)于Zernike矩、GFD、RFMT及PCET的RST不變性分析主要是針對(duì)二值圖像.對(duì)于非二值圖像，灰度值的變化很容易導(dǎo)致圖像質(zhì)心的偏移，所以本文在醫(yī)學(xué)圖像的檢索上不預(yù)先進(jìn)行圖像平移處理.平移不變性關(guān)鍵在于2幅圖像的質(zhì)心與圖像中心的相對(duì)位置的一致，因此只要醫(yī)學(xué)圖像在存儲(chǔ)時(shí)遵循一定的規(guī)范，就可以保證平移不變.

對(duì)于RCFT方法的圖像平移和尺度變換表現(xiàn)在Radon變換上只是每個(gè)投影方向上的變化.而通過R-Transform可消除投影方向上的變化.由此可見，RCFT并不要求對(duì)圖像進(jìn)行事先平移，也不要求針對(duì)質(zhì)心進(jìn)行計(jì)算.因此RCFT方法在這方面具有獨(dú)特優(yōu)勢(shì).

2.2 噪聲魯棒性

對(duì)于Zernike矩和RFMT方法，噪聲會(huì)引起圖像質(zhì)心的偏移，由此會(huì)對(duì)圖像的檢索產(chǎn)生影響.

對(duì)于GFD方法，由于其本質(zhì)上是傅里葉變換，而傅里葉變換系數(shù)中的低階反映圖像的整體信息，高階反映圖像的細(xì)節(jié)信息(包括噪聲)，因?yàn)楸疚倪x取的是低階特征，所以對(duì)噪聲不敏感.PCET方法與GFD方法類似，對(duì)噪聲也不敏感.

RCFT方法需先對(duì)圖像進(jìn)行倒角距離變換，而倒角變換會(huì)受到噪聲的影響.從圖1可以看出，RCFT受噪聲的影響較大.

圖1 噪聲對(duì)倒角距離變換的影響

2.3 時(shí)間復(fù)雜度

1)Zernike矩 由于涉及階乘運(yùn)算，直接計(jì)算會(huì)很耗時(shí)，故本文采用文獻(xiàn)［12］的Zernike矩快速算法，對(duì)于N×N大小的圖像，需計(jì)算O(n2×N)次乘法，O(n2×N2)次加法.

2)GFD 需計(jì)算O(N2)次乘法，O(N2)次加法.

3)PCET 需計(jì)算O(N2)次乘法，O(N2)次加法.

4)RCFT 倒角距離變換需計(jì)算O(N2)次加法，Radon變換需計(jì)算O(N2)次加法(Radon變換后圖像大小為U×V).R-Transform需計(jì)算O(U×V)次乘法，V次加法.Fourier變換需計(jì)算O(U)次乘法，O(U)次加法.故RCFT的時(shí)間復(fù)雜度為O(U×V)+O(U)次乘法，O(N2)+O(U)次加法.

5)RFMT Radon需計(jì)算O(N2)次加法(Radon變換后圖像大小為U×V).Fourier-Mellin矩需計(jì)算O(U×V)次乘法，O(U×V)次加法.故RFMT的時(shí)間復(fù)雜度為O(U×V)次乘法，O(N2)+O(U×V)次加法.

由上述分析可以看出，PCET的時(shí)間復(fù)雜度與GFD相同，但比Zernike矩快速算法的計(jì)算復(fù)雜度要高.對(duì)于單幅圖像，RCFT與RFMT的時(shí)間復(fù)雜度相似，由Radon變換后的圖像大小決定.但是由于RCFT中的倒角距離變換將圖像拆分為多幅計(jì)算，因此RCFT的時(shí)間復(fù)雜度會(huì)比RFMT高幾倍.

2.4 有效特征數(shù)

1)Zernike矩 當(dāng)高于一定階數(shù)后，Zernike矩的計(jì)算就不再準(zhǔn)確，且高階矩對(duì)噪聲要比低階矩敏感得多，所以一般使用低階矩.本文取低于10階的36個(gè)特征值.

2)GFD 由于GFD本質(zhì)上是傅里葉變換，具有傅里葉變換的性質(zhì)，因此在特征選取上階數(shù)不能太高.本文取4個(gè)幅度頻域和9個(gè)角頻域，共36個(gè)頻域系數(shù).

3)PCET 由于PCET的高階特征都可以使用，所以可以構(gòu)造無窮多個(gè)RST不變的特征值.本文取階數(shù)小于3、重復(fù)度小于12的36個(gè)特征值.

4)RCFT 經(jīng)過R-Transform后，對(duì)所得值進(jìn)行一維傅里葉變換.本文取倒角變換后的4幅圖像(因運(yùn)行時(shí)間會(huì)因圖像數(shù)而明顯變化，故對(duì)倒角距離變換后的圖，本文只取了4個(gè)灰度級(jí)的圖像)，每幅取9個(gè)傅里葉變換系數(shù)，共36個(gè)特征值.

5)RFMT 隨著階數(shù)的增加不會(huì)增加時(shí)間復(fù)雜度，因此理論上可以任選一組特征值.本文取Fourier-Mellin變換后階數(shù)小于4、重復(fù)度小于9的36個(gè)特征值.

3 實(shí)驗(yàn)結(jié)果和分析

目前，常用的圖像檢索評(píng)估方法為由查全率和查準(zhǔn)率定義的PVR曲線.查全率為R=a/(a+c)，查準(zhǔn)率為P=a/(a+b).其中，a為查詢到的相關(guān)圖像的數(shù)目;b為查詢到的不相關(guān)圖像的數(shù)目;c為與檢測(cè)圖像相關(guān)，但沒有檢索到的數(shù)目.當(dāng)計(jì)算出圖像的查全率和查準(zhǔn)率后，將查全率作為x軸，查準(zhǔn)率作為y軸，則可繪制出圖像檢索結(jié)果的PVR曲線.

3.1 檢索結(jié)果及噪聲魯棒性

圖2為5種變換域方法在該測(cè)試集的平均PVR曲線圖.其中選用的測(cè)試集為 MPEG7 CE Shape-1 Part B中的1 400幅圖像.

圖2 各變換域方法在MPEG圖像上的平均PVR曲線

實(shí)驗(yàn)中，2幅圖像特征向量間的相似性比較采用市街區(qū)距離(city block distance).由圖2可以看出，Zernike矩和GFD方法的檢索效果最好，PCET次之，RFMT和 RCFT檢索效果稍差.這是因?yàn)镽FMT和RCFT需要幾種變換才能實(shí)現(xiàn)RST不變性，累積離散誤差比Zernike矩、GFD和PCET大.且RCFT經(jīng)過R-Transform變換后會(huì)丟失很多細(xì)節(jié)信息.

對(duì)MPEG7 CE Shape-1 Part B的1 400幅圖像測(cè)試集加上不同程度的高斯噪聲后，各種方法的平均查準(zhǔn)率結(jié)果見表1.

表1 加不同程度噪聲后各方法的平均查準(zhǔn)率 %

由表1可以看出，噪聲對(duì)RCFT方法影響最大，其次是 Zernike矩和 RFMT，對(duì) PCET和 GFD影響稍小.RCFT方法中由于倒角距離變換受噪聲影響很大，故檢索效果受噪聲影響明顯.由于噪聲會(huì)引起圖像質(zhì)心的改變，因此Zernike矩和RFMT在平移圖像時(shí)也易受噪聲影響.

3.2 運(yùn)行時(shí)間

表2為各種算法的運(yùn)行時(shí)間，其中，圖像為256×256像素，操作系統(tǒng)為Windows XP，實(shí)驗(yàn)平臺(tái)為Visual Studio 2008，從圖像提取的特征值存儲(chǔ)在SQL Server 2005數(shù)據(jù)庫中.

表2 5種變換域形狀描述方法的運(yùn)行時(shí)間

每種方法的運(yùn)行時(shí)間是計(jì)算一組特征值所需的總時(shí)間，如計(jì)算Zernike矩的36個(gè)特征值用的總時(shí)間.RFMT算法由于Radon變換后圖像變小了，因此總時(shí)間較少.而RCFT算法由于將一幅圖像拆為多幅圖像計(jì)算，因此所用的時(shí)間較多.

3.3 在醫(yī)學(xué)圖像檢索中的應(yīng)用

本實(shí)驗(yàn)的醫(yī)學(xué)圖像數(shù)據(jù)庫是從“醫(yī)影在線”網(wǎng)站上下載的病例，共有50種病例，每種病例包含10幅圖像.當(dāng)醫(yī)生不能確定病例時(shí)，可以使用基于內(nèi)容的圖像檢索，即由系統(tǒng)自動(dòng)從圖像數(shù)據(jù)庫中搜索與所給樣圖相似的圖像.這樣可以根據(jù)數(shù)據(jù)庫中的病例進(jìn)行輔助診斷.圖3為各變換域方法在醫(yī)學(xué)圖像上的平均PVR曲線圖.

圖3 各變換域方法在醫(yī)學(xué)圖像上的平均PVR曲線

從圖3可以看出，Zernike矩和GFD的醫(yī)學(xué)圖像檢索效果最好，而RFMT檢索效果比PCET好，RCFT檢索效果最差.這是因?yàn)獒t(yī)學(xué)圖像比較復(fù)雜，而RCFT在進(jìn)行倒角變換時(shí)對(duì)復(fù)雜圖像影響較大，所以RCFT不適用于醫(yī)學(xué)圖像檢索.

圖4為加高斯噪聲后的平均PVR曲線.從加噪聲與未加噪聲的對(duì)比實(shí)驗(yàn)可以看出，醫(yī)學(xué)圖像中的噪聲對(duì)Zernike矩、RFMT、PCET和GFD的影響較小，但對(duì)RCFT的影響較大.

圖4 加噪聲后各方法在醫(yī)學(xué)圖像上的平均PVR曲線

4 結(jié)語

本文詳細(xì)比較和分析了 Zernike矩、GFD、PCET、RFMT和RCFT 5種變換域圖像檢索方法，分析了它們的RST不變性、噪聲魯棒性及時(shí)間復(fù)雜度.并將這幾種變換域方法用于醫(yī)學(xué)圖像的檢索.實(shí)驗(yàn)結(jié)果表明，Zernike矩和GFD方法的檢索效果最好，有良好的抗噪性，因而適合于醫(yī)學(xué)圖像檢索的實(shí)際應(yīng)用.

［1］Hu M K.Visual pattern recognition by moment invariant［J］.IRE Trans Information Theory，1962，8(2):179-187.

［2］Ye B，Peng J X.Analysis and improvement of invariance of Zernike moments［J］.Infrared and Laser Engineering，2003，32(1):37-41.

［3］Teh C H，Chin R T.On image analysis by the method of moments［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1988，10(4):496-513.

［4］Chao K，Mandyam D S.Invariant character recognition with Zernike and orthogonal Fourier-Mellin moments［J］.Pattern Recognition，2002，35(1):143-154.

［5］ Khalil M I，Bayoumi M M.A dyadic wavelet affine invariant function for 2D shape recognition［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2001，23(10):1152-1164.

［6］ Zhang D，Lu G.A comparative study of Fourier descriptors for shape representation and retrieval［C］//Proc5th Asian Conference on Computer Vision.Melbourne，Australia，2002:646-651.

［7］ Ricard J，Coeurjolly D，Baskurt A.Generalizations of angular radial transform for 2D and 3D shape retrieval［J］.Pattern Recognition Letters，2005，26(14):2174-2186.

［8］Yap P T，Jiang X D，Kot A C.Two-dimensional polar harmonic transforms for invariant image representation［J］.Pattern Analysis and Machine Intelligence，2010，32(7):1259-1270.

［9］ Borgefors G.Distance transformations in digital images［J］.Computer Vision，Graphics，and Image Processing，1986，34(3):344-371.

［10］ Tabbone S，Wendling L，Salmon J P.A new shape descriptor defined on the radon transform［J］.Comp Vis and Image Under，2006，102(1):42-51.

［11］ Wang X，Xiao B，Ma J F，et al.Scaling and rotation invariant analysis approach to object recognition based on Radon and Fourier-Mellin transforms［J］.Pattern Recognition，2007，40(12):3503-3508.

［12］ Gu J，Shu H Z，Toumoulin C，et al.A novel algorithm for fast computation of Zernike moments［J］.Pattern Recognition，2002，35(12):2905-2911.

Comparative study of transform domain image retrieval

Mao Yufei1Wang Bin1，2Shu Huazhong1

(1Laboratory of Image Science and Technology，Southeast University，Nanjing 210096，China)
(2Jiangsu Key Laboratory of Electronic Business，Nanjing University of Finance and Economics，Nanjing 210046，China)

In order to better understand the effect of transform domain method in image retrieval，we give a comparison of the five transform-based shape descriptors，which are Zernike moments，generic Fourier descriptor(GFD)，polar complex exponential transform(PCET)，Radon chamfer Fourier transform(RCFT)and Radon Fourier-Mellin transform(RFMT)were compared.Besides，analyses on invariance，computation complexity，noise robustness and effective number of features were conducted in detail.The five descriptors were tested by using 1 400 images from MPEG7 CE Shape-1 Part B.Furthermore，these descriptors were practically used for the medical image database including 500 images.To study the effect of the noise on retrieval，the Gaussian noise was applied to the two databases.It can be seen from the comparative analysis and the experimental results that the performance of Zernike moments and GFD are the best.They have robust noise immunity and are suitable for the practical application of medical image retrieval.

image retrieval;shape description;transform domain analysis;medical image retrieval

TP391

A

1001－0505(2012)02-0254-05

10.3969/j.issn.1001 －0505.2012.02.012

2011-12-29.

毛玉妃(1986—)，女，碩士生;舒華忠(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，shu.list@seu.edu.cn.

國家自然科學(xué)基金資助項(xiàng)目(61073138，60911130370，61103141)、教育部博士點(diǎn)基金資助項(xiàng)目(20110092110023)、江蘇省高校自然科學(xué)研究重大資助項(xiàng)目(11KJA520004).

毛玉妃，王斌，舒華忠.基于變換域形狀描述子的圖像檢索方法的比較與分析［J］.東南大學(xué)學(xué)報(bào):自然科學(xué)版，2012，42(2):254-258.［doi:10.3969/j.issn.1001 －0505.2012.02.012］