快速的基于小波的圖像檢索方法

摘要：該文描述一種基于小波的圖像檢索方法。該方法使用小波分解提取圖像“簽名”，然后使用該文構(gòu)建的檢索方法進(jìn)行檢索。該方法已應(yīng)用于某紀(jì)念幣檢索系統(tǒng)中，具有查詢速度快、存儲空間小和實(shí)現(xiàn)簡單等優(yōu)點(diǎn)。

關(guān)鍵詞：小波；Haar；小波分解；基于內(nèi)容的圖像檢索；圖像數(shù)據(jù)庫

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)35-2218-02

Fast Wavelet-based Image Retrieval

CHEN Kang， SU Xiao-long， WANG Xiang-ting

(China University of Mining and Technology， School of Computer Science and Technology， Xuzhou 221008， China)

Abstract: The paper presents a method for wavelet-based image retrieval. It extracts image \"signature\" by wavelet decomposition， then searching by using the method of the paper. The method has been applied in the Commemorative Coins Retrieval System. The method is very fast and needs a little storage and is implemented easily.

Key words: wavelet; haar; wavelet decomposition; content-based image retrieval; image database

1 引言

圖像檢索系統(tǒng)[1]是一種計(jì)算機(jī)系統(tǒng)，用于在大型的數(shù)字圖像數(shù)據(jù)庫中進(jìn)行圖像的瀏覽與檢索。傳統(tǒng)的圖像檢索方法主要是通過人工向圖像中添加關(guān)鍵字等元數(shù)據(jù)對圖像進(jìn)行索引。這種方法存在以下兩個(gè)問題。首先，這是一個(gè)非常耗時(shí)的工作，隨著圖像數(shù)量的急劇增長，人工處理的方法將很難滿足要求。其次，由于視覺方面的差異，不同的人對同一圖像可能存在不同的描述，這將導(dǎo)致查詢結(jié)果很不可靠。目前使用的方法主要是基于內(nèi)容的圖像檢索方法[1]。

本文描述的方法是：首先對數(shù)據(jù)庫中的圖像進(jìn)行Haar小波分解[2]提取圖像特征，稱之為“簽名”，然后對輸入的圖像進(jìn)行相同的Haar小波分解，最后使用本文構(gòu)建的檢索方法在圖像數(shù)據(jù)庫中進(jìn)行檢索，并返回最相似的若干圖像。該方法允許多尺度查詢[3]，運(yùn)行時(shí)間和存儲空間都獨(dú)立于圖像數(shù)據(jù)庫[4]的圖像的尺度，并且圖像的簽名信息可以從圖像的小波壓縮版本中直接抽取。最后，該方法非常容易實(shí)現(xiàn)和使用。

2 檢索方法的構(gòu)建

我們的目標(biāo)是構(gòu)建一種圖像檢索方法，該方法可以快速計(jì)算并且僅需要少量的存儲空間。因此，我們猜測圖像的二維小波分解對于構(gòu)建這種方法可能提供一種比較好的途徑，原因如下：

1） 小波分解可以使用較少的系數(shù)較好的描述圖像。這種特性已經(jīng)被應(yīng)用于圖像的有隕壓縮[5]中。

2） 小波分解可以用于抽取和編碼圖像邊緣信息。這種特性對于圖像檢索具有非常重要的意義。

3） 小波分解的系數(shù)提供的信息獨(dú)立于原始圖像的尺度。因此，基于小波的檢索方法允許查詢圖像與目標(biāo)圖像的具有不同的尺度。

4） 小波分解非?？焖俨⑶胰菀子?jì)算，線性時(shí)間復(fù)雜度，編碼實(shí)現(xiàn)也非常簡單。

2.1 相關(guān)問題

下面是本文檢索方法的一些相關(guān)問題：

1） 顏色空間：我們需要選擇一個(gè)顏色空間來表示圖像，實(shí)現(xiàn)分解。我們實(shí)驗(yàn)了以下三種顏色空間：RGB，HSV和YIQ。最終，通過實(shí)驗(yàn)得出YIQ在這三種顏色空間中最為有效。

2） 小波類型：我們選擇Haar小波，因?yàn)樗?jì)算非?？焖俨⑶乙子趯?shí)現(xiàn)。

3） 截?cái)啵簩τ?28×128的圖像每個(gè)顏色通道共有1282=16，384種不同的小波系數(shù)，而本文方法只使用最大的小波系數(shù)。這種截?cái)嗖粌H加速搜索并且減少存儲空間。通過實(shí)驗(yàn)發(fā)現(xiàn)存儲40個(gè)最大系數(shù)效果最佳。

4） 量化：像截?cái)嘁粯樱瑢τ诿總€(gè)小波系數(shù)進(jìn)行量化主要為了加速搜索和減少存儲空間。我們將系數(shù)量化為二個(gè)級別：+1（代表正系數(shù)）和-1（代表負(fù)系數(shù)）。

2.2 相似度計(jì)算

圖像檢索的過程就是比較查詢圖像與目標(biāo)圖像的相似度。下面介紹本文如何計(jì)算圖像相似度。首先，Q和T分別代表查詢圖像和目標(biāo)圖像單個(gè)顏色通道的小波分解。Q[0，0]和T[0，0]代表相應(yīng)顏色通道的顏色平均值。更進(jìn)一步Q[i，j]和T[i，j]代表第[i，j]個(gè)截?cái)嗟?、量化的小波系?shù)，這些值可能為：-1，0和+1。Q與T的相似度計(jì)算等式如下：

（1）

上式中bin(i，j)是由索引[i，j]選擇權(quán)重的函數(shù)。上式中(Q[i，j]==T[i，j])的計(jì)算方法為：當(dāng)Q[i，j]等于T[i，j]時(shí)為1，否則為0。注意：上式的值越小代表Q與T越相似。

3 算法

本文的檢索算法的復(fù)雜度是線性的。算法描述為：在預(yù)處理階段，我們對圖像數(shù)據(jù)庫中的每個(gè)圖像進(jìn)行標(biāo)準(zhǔn)的二維小波分解，存儲顏色平均值和m個(gè)最大的小波系數(shù)的索引和符號。然后，對每個(gè)查詢圖像，執(zhí)行相同的小波分解，獲取顏色平均值和m個(gè)最大量級的小波系數(shù)。然后利用式(1)對目標(biāo)圖像T進(jìn)行評分（相似度計(jì)算）。

3.1 預(yù)處理

圖像的標(biāo)準(zhǔn)的二維Haar小波分解非常容易編碼實(shí)現(xiàn)。首先對圖像的每一行進(jìn)行一維小波分解，然后對分解結(jié)果的每一列進(jìn)行一維小波分解。

下面的偽代碼對數(shù)組A[h]執(zhí)行一維的小波分解，h必須是2的冪：

proc DecomposeArray(A : array[0..h-1] of color) :

A ← A/?h

while h > 1 do :

h ← h/2

for i ← 0 to h-1 do :

A`[i] ← (A[2i]+A[2i+1])/

A`[h+i] ← (A[2i]-A[2i+1])/ ?2

end for

A ← A`

end while

end proc

上面的偽代碼，假設(shè)數(shù)組A中每個(gè)元素代表的顏色具有三個(gè)通道，范圍為[0，1]。各種操作分別對每個(gè)顏色通道進(jìn)行。

一個(gè)r×r的圖片T可以進(jìn)行如下分解：

proc DecomposeImage(T : array[0..r-1， 0..r-1] of color) :

for row ← 1 to r do :

DecomposeArray(T[row， 0..r-1])

end for

for col ← 1 to r do :

DecomposeArray(T[0..r-1， col])

end for

end proc

在分解過程之后，T[0，0]代表整幅圖像的顏色平均值，而其它的值為小波系數(shù)。

最終，我們存儲T[0，0]和最大的m個(gè)小波系數(shù)的索引和符號。為了優(yōu)化搜索過程，保留的m個(gè)小波系數(shù)被組織成六個(gè)數(shù)組，稱為搜索數(shù)組，每個(gè)數(shù)組代表符號（+/-）和顏色通道（如YIQ）的每種組合。

檢索是非常直接的。對于特定的查詢圖像Q，我們執(zhí)行上一節(jié)描述的小波分解。然后，保留圖片的顏色平均值和每個(gè)顏色通道的最大的m個(gè)小波系數(shù)的索引和符號。然后根據(jù)查詢圖像Q分別對圖像數(shù)據(jù)庫中每個(gè)目標(biāo)圖像T進(jìn)行評分，計(jì)算過程如下：

func ScoreQuery(Q : array[0..r-1， 0..r-1] of color; m : int) :

DecomposeImage(Q)

Initialize scores[i] ← 0 for all i

for each color channel c do :

for each database image T do :

score[index(T)] += Wc[0]×|Qc[0，0]-Tc[0，0]|

end for

Q ← TruncateCoefficients(Q， m)

for each non-zero cefficient Qc[i，j] do :

if Qc[i，j] > 0 then

list ← Tc+[i，j]

else

list ← Tc-[i，j]

end if

for each element l of list do :

scores[index(l)] -= wc[bin(i，j)]

end for

end for

end for

return scores

end func

函數(shù)bin(i，j)提供了一種將不同的小波系數(shù)分組的方法，每一組使用不同的權(quán)重w[b]。在我們的實(shí)現(xiàn)中，使用的函數(shù)為：bin(i，j) = min{max{i， j}， 5}。

對于我們的圖像數(shù)據(jù)庫，一個(gè)比較好的使用YIQ顏色空間和標(biāo)準(zhǔn)Haar小波分解的權(quán)重集，如下：

wY[b] wI[b]wQ[b]

0 5.00 19.21 24.37

10.831.260.36

21.010.440.45

30.520.530.14

40.470.280.18

50.300.140.27

最后，我們的算法檢查分?jǐn)?shù)列表，這些得分可能為正也可能為負(fù)。最小的（通常是負(fù)的）得分被認(rèn)為是最接近的。我們使用堆排序算法查找前20幅最匹配的圖像。

4 應(yīng)用

本文描述的圖像檢索方法被應(yīng)用到某紀(jì)念幣網(wǎng)站的紀(jì)念幣檢索系統(tǒng)中。該系統(tǒng)要求用戶輸入查詢紀(jì)念幣的圖像（正面或背面），系統(tǒng)會輸出與其最匹配的前20個(gè)紀(jì)念幣的圖像及其資料。在實(shí)際的應(yīng)用中，本文描述的檢索方法具有檢索速度快、準(zhǔn)確性高和占用存儲空間小等優(yōu)點(diǎn)，完全滿足了該檢索系統(tǒng)的要求。

5 小結(jié)

本文描述的檢索方法具有檢索速度快，準(zhǔn)確性高，存儲空間小和實(shí)現(xiàn)簡單等優(yōu)點(diǎn)，具有一定的實(shí)用價(jià)值。但本文的檢索方法仍然存在著不足，比如不具有旋轉(zhuǎn)不變性，權(quán)重調(diào)整速度慢等缺點(diǎn)，需要進(jìn)一步完善，這也是下一步的工作內(nèi)容與研究方向。

參考文獻(xiàn)：

[1] 周明全.基于內(nèi)容圖像檢索技術(shù)[M].北京:清華大學(xué)出版社，2007.

[2] 孫延奎.小波分析及應(yīng)用[M].北京:機(jī)械工業(yè)出版社，2005.

[3] Lowe D. Object recognition from local scale-invariant features[M]. In Proc. ICCV，1999:1150-1157.

[4] Squire D M， Muller W， Muller H， et al. Content-based query of image database: inspiration from text retrieval[C]. Pattern Recognition Letters，2000(21):1193-1198.

[5] 曾文曲，文有為，孫煒，等.分形小波與圖像壓縮[M].遼寧:東北大學(xué)出版社，2002.