基于相關(guān)反饋的一種加權(quán)距離法

趙文霞，周海英

（中北大學(xué) 電子與計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，太原 030051）

0 引言

現(xiàn)有的特征提取算法中沒(méi)有一個(gè)能很好地將視覺(jué)上相似的圖像映射到最近的位置。在圖像檢索結(jié)果中常見(jiàn)一些現(xiàn)象：有時(shí)一些圖像是與待查詢(xún)的圖像很大程度上是不相關(guān)的，僅僅因?yàn)檫@些圖像在特征空間中與待查詢(xún)的圖像是接近的就被檢索出來(lái)。因此，需要采用改進(jìn)權(quán)值的方法來(lái)改善檢索結(jié)果。

底層特征也要表示出高層概念的相似度和人的視覺(jué)的主觀性。為了讓用戶(hù)更多地參與檢索過(guò)程，有些檢索系統(tǒng)已經(jīng)允許用戶(hù)衡量這些底層特征。由于普通用戶(hù)對(duì)專(zhuān)家設(shè)計(jì)的底層特征并不是很了解，所以通常來(lái)說(shuō)這種方法是不可取的。

最近，修改權(quán)值的方法已經(jīng)在相關(guān)反饋技術(shù)中得到了廣泛的應(yīng)用。其主要思想是將用戶(hù)考慮在檢索循環(huán)中。首先把用戶(hù)輸入的原始查詢(xún)圖像在數(shù)據(jù)庫(kù)中進(jìn)行初始搜索，再在初始搜索結(jié)果的基礎(chǔ)上，用戶(hù)根據(jù)自己的實(shí)際需要把圖像分為相關(guān)圖像和不相關(guān)圖像。這樣就根據(jù)交互檢索把反饋的信息參與到數(shù)據(jù)庫(kù)的搜索中。

在圖像數(shù)據(jù)庫(kù)檢索中,相關(guān)反饋方法常用一些信息檢索文獻(xiàn)中已成型的思想。一種常用的思想是向量空間模型，原始特征向量和由用戶(hù)標(biāo)記的相關(guān)或不相關(guān)圖像的特征向量的加權(quán)線(xiàn)性組合構(gòu)成了一個(gè)新的查詢(xún)特征向量。其他的方法包括使用關(guān)鍵詞、創(chuàng)建概率用戶(hù)模型、修改距離測(cè)量、重組檢索結(jié)果、特征密度估計(jì)和交互權(quán)值更新等。

檢索算法依賴(lài)于直接從圖像中計(jì)算出的特征。但是我們僅想使用用戶(hù)反饋回來(lái)的信息而不是使用人工關(guān)鍵詞或者啟發(fā)式的假設(shè),而且我們也不能假設(shè)用戶(hù)的一切信息要求,更不能假設(shè)用戶(hù)要搜索圖像的分類(lèi),相關(guān)或不相關(guān)。因此, 在K-近鄰搜索中根據(jù)用戶(hù)的反饋得到一些特征，我們賦予這些特征權(quán)值。其特征值與整個(gè)數(shù)據(jù)庫(kù)和用戶(hù)選擇的相關(guān)圖像的標(biāo)準(zhǔn)偏差的比率既適用于相互獨(dú)立的權(quán)值之間，也適用于增量更新的權(quán)值之間。

本文對(duì)一個(gè)含有1000幅圖像的數(shù)據(jù)庫(kù)進(jìn)行了實(shí)驗(yàn)，其檢索性能也采用平均查準(zhǔn)率進(jìn)行評(píng)價(jià)。我們還定義了一個(gè)新的測(cè)量值“增進(jìn)”來(lái)測(cè)量其性能。

1 加權(quán)距離法

1.1 定義

首先，給出了文中用到的一些定義。

K：交互搜索的次數(shù)。

Q：一個(gè)特征向量中特征的個(gè)數(shù)。

Rk={第k次搜索后的檢索集合}，k=0，…，K，其中R0表示整個(gè)數(shù)據(jù)庫(kù)。

在檢索過(guò)程中，通過(guò)計(jì)算特征空間中特征向量的距離來(lái)得出圖像之間的相似度。給定特征向量x和y，加權(quán)向量w，用加權(quán)后的L1距離：

和加權(quán)后的 L2距離：

1.2 算法目的

從模式識(shí)別的角度來(lái)看，如果描述圖像內(nèi)容的一個(gè)特征很好，那么在數(shù)據(jù)庫(kù)的所有圖像中它的方差可能很大但是在所有相關(guān)的圖像中它的方差應(yīng)該很小。所有這種特征中也許并不是每一個(gè)都是相互獨(dú)立的，但是當(dāng)與其他特征結(jié)合時(shí)就會(huì)表現(xiàn)出這個(gè)特征是個(gè)好的特征,能夠很好地描述圖像的內(nèi)容。

給出這些定義之后，我們就可以用wkj=σ0j/σkrel,j,這里σ0j=std（F0j），σkrel,j=std（Fkrel,j），作為第k+1次迭代中第j個(gè)特征的權(quán)值。一方面,對(duì)于給定的一幅圖像，對(duì)于整個(gè)數(shù)據(jù)庫(kù)來(lái)說(shuō)它的相關(guān)圖像集只是一個(gè)很小的集合；另一方面，其他的圖像就會(huì)歸類(lèi)為不相關(guān)的圖像。這里我們只用相關(guān)的圖像集，因?yàn)橛捎脩?hù)選擇的相關(guān)和不相關(guān)的反饋圖像都是個(gè)較小的集合,這樣可能就更好地概括了前面的檢索情況。

對(duì)于σ0j和σkrel,j，表1中列出了4種可能出現(xiàn)的情況。

表1 權(quán)值的選擇

由表1可以看到表中越向上面移動(dòng)的值更接近其目的。

(a)當(dāng)σ0j越大，σkrel,j小時(shí)，wkj就會(huì)很大。這也就意味著數(shù)據(jù)庫(kù)中圖像的特征有多種集合，但是這些相關(guān)圖像的特征值卻是相似的。這也是一種預(yù)期情況而且還表明了在區(qū)分某個(gè)特定的相關(guān)圖像集時(shí)這個(gè)特征是非常有效的，所以就要賦予這個(gè)有效的特征更大的權(quán)重。

(b)當(dāng)σ0j和σkrel,j都大時(shí)，wkj接近于1。這表明數(shù)據(jù)庫(kù)中的這個(gè)特征可能也是個(gè)很好的特征，但是對(duì)于某些特定的相關(guān)圖像集來(lái)說(shuō)它就不一定是有效的，因而也就沒(méi)

必要賦予這個(gè)特征特殊的權(quán)重。

(c)當(dāng)σ0j和σkrel,j都小時(shí)，wkj也會(huì)接近于1。這與當(dāng)σ0j和σkrel,j都大時(shí)wkj接近于1的情況類(lèi)似，但比上面的情形略微差一些。對(duì)于圖像數(shù)據(jù)庫(kù)來(lái)說(shuō),這個(gè)特征一般是沒(méi)有多大作用的，對(duì)于相關(guān)圖像集也是沒(méi)有多大作用的,所以也就不用重視這個(gè)圖像特征。

(d)當(dāng)σ0j小，σkrel,j大時(shí)，wkj就會(huì)很小。這種情況是4種可能情況中最差的一種。這個(gè)特征一般來(lái)說(shuō)對(duì)圖像檢索是沒(méi)有作用的,甚至?xí)?dǎo)致增大了相關(guān)圖像之間的距離。因此要賦予這個(gè)特征很小的權(quán)重進(jìn)而可以忽略掉這個(gè)特征的作用。

在理想的檢索中，可以證明這四種情況中所有結(jié)果種類(lèi)的權(quán)重與預(yù)期情況都是一致的。

1.3 交互檢索

下面給出了基于相關(guān)反饋的加權(quán)距離法進(jìn)行圖像檢索的算法：

(1)統(tǒng)一初始化所有權(quán)值:w0j=1/Q，j=1，…，Q。并且計(jì)算σ0j，j=1，…，Q。

(2)for k=1，…，K，

（a）用wk-1j搜索數(shù)據(jù)庫(kù)，得到Rk。

（b）當(dāng)Rkrel，得到用戶(hù)的反饋信息。

（c）計(jì)算σkrel,j，j=1，…，Q。

(3)用wKj進(jìn)行最后搜索，j=1，…，Q。

其中,檢索算法過(guò)程2(c)中的σkrel,j的計(jì)算有兩種方法：

特征權(quán)重是相互獨(dú)立地更新：在每次迭代過(guò)程中只用迭代得檢索集合相互獨(dú)立地估計(jì)標(biāo)準(zhǔn)偏差。例如：

這里E（Fk

rel，j）2和E（（Fkrel，j）2）分別是樣本的一階和二階期望。

特征權(quán)重是增量更新：我們假設(shè)隨著迭代過(guò)程用戶(hù)對(duì)于相似的概念保持不變，在之后的迭代過(guò)程中也保持不變。這樣，在每次迭代過(guò)程中增量更新的標(biāo)準(zhǔn)偏差的計(jì)算為：

當(dāng)Fkrel中所有值都相同時(shí)，所有的圖像對(duì)于同一個(gè)特征都有相同的特征值，就賦予wkj一個(gè)大的權(quán)重常數(shù)。

2 實(shí)驗(yàn)和結(jié)果

2.1 數(shù)據(jù)庫(kù)大小

定義了一個(gè)有1000（256×384）幅圖像的數(shù)據(jù)庫(kù)，其中包括自然景觀圖像和人物圖像等。選取了340幅圖像構(gòu)成7類(lèi)基本圖像：海濱風(fēng)光、恐龍、建筑物、花、冰川雪山、馬和人。文獻(xiàn)[1]中已經(jīng)采用文本描述來(lái)表示圖像。第一種特征集合是線(xiàn)角概率統(tǒng)計(jì)，主要使用了空間關(guān)系和線(xiàn)性屬性；第二種特征集合是特定空間關(guān)系中像素的差異共生統(tǒng)計(jì)。

2.2 檢索性能

本文采用平均查準(zhǔn)率來(lái)測(cè)量算法的檢索性能，查準(zhǔn)率是指檢索出的圖像是相關(guān)圖像的百分比。圖1中給出了一些基本圖像檢索結(jié)果的平均差準(zhǔn)率。每次迭代搜索引擎都在數(shù)據(jù)庫(kù)中進(jìn)行一次新的檢索，而且每次檢索12幅圖像。L1和L2距離也都可以用在相互獨(dú)立地更新。

表2中總結(jié)出了檢索結(jié)果。可以看到用L2距離可以得到更高的平均查準(zhǔn)率。我們用了5次迭代，每次迭代后平均查準(zhǔn)率最大改善了19%。這種預(yù)期情況也證明了其快速收斂性。表2中還給出了每次迭代后較前一次迭代改善情況。

表2 檢索12幅圖像的平均查準(zhǔn)率

如果每次迭代都要搜索整個(gè)數(shù)據(jù)庫(kù),一般很少能再搜索到其他的相關(guān)圖像,并且原始查詢(xún)后的檢索集合中的圖像也會(huì)以一種新的圖像集顯示,而不是必須進(jìn)行反饋或者更多次的搜索才能顯示。另一種方法是對(duì)于某個(gè)特定的圖像集，相關(guān)反饋性能的好壞可以根據(jù)“增進(jìn)值”來(lái)比較迭代搜索的性能和最初搜索的性能。在得到反饋信息之后，搜索引擎就會(huì)對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次新的搜索，但是不再未反饋前 第一次反饋 第二次反饋‘－’:L1相互獨(dú)立更新; ‘－－’: L2相互獨(dú)立更新; ‘…’: L1未反饋; ‘﹎’L2未反饋考慮已經(jīng)在前面迭代過(guò)程中檢索到的所有圖像。因此，每次迭代只需檢索一個(gè)新的12幅圖像的集合。其性能可以用原始搜索的檢索集合中的另外12幅圖像的集合（用戶(hù)界面中顯示的下一頁(yè)）進(jìn)行比較。假如檢索到的圖像有n幅，定義“Progress”是兩次準(zhǔn)確率的比，

圖1 前兩次的平均查準(zhǔn)率

當(dāng)Progress大于1時(shí)，表明反饋算法有效而且收斂的很快。表3分別給出了未反饋前、第一次反饋和第二次反饋的平均Progress值。

表3 檢索了12、24、36幅圖像后的平均Progress

由表3可以看到距離增量更新比相互獨(dú)立更新的效果更好。較反饋前，反饋后的Progress最大改善了5.3%。

3 結(jié)論

文中給出了一種加權(quán)距離法，其權(quán)值就是整個(gè)數(shù)據(jù)庫(kù)和用戶(hù)選擇后的相關(guān)圖像的特征值的標(biāo)準(zhǔn)方差之比。論文討論了相互獨(dú)立的權(quán)值更新，在每次迭代中其權(quán)值是相互獨(dú)立的，僅使用本次迭代的反饋信息進(jìn)行評(píng)估。還討論了增量權(quán)值更新，在每次迭代中其權(quán)值是增量更新的，要使用本次迭代和前次迭代的反饋信息進(jìn)行評(píng)估。

對(duì)一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)用平均查準(zhǔn)率和Progress值評(píng)價(jià)檢索性能，而且每次迭代后平均性能都提高了19%，而且收斂速度也很快。

文中還有一個(gè)問(wèn)題需要進(jìn)行研究，就是研究權(quán)值更新方法的標(biāo)準(zhǔn)方差的其他作用。比如在數(shù)據(jù)庫(kù)中也考慮不相關(guān)圖像的反饋信息，檢索結(jié)果可能會(huì)更好。

[1] S.Aksory and R.M.Haralick.Textural fetures for image database retrieval[J].In Processing of IEEE Workshop on Content-Based Access of Image and Video Libraries,in conjunction with CPVR’98,Santa Barbara,CA,1998:45-49.

[2] P.Wu and B.S.Manjunath.Adaptive nearest neighbor search for Relevance Feedback in Large Image Databases[J]. Department of Electrical and Computer Engineering University of California,Santa Barbara,CA 93106-9560.

[3] 黃德才,胡嘉,鄭月鋒.交互式圖像檢索中相關(guān)反饋進(jìn)展研究[J].計(jì)算機(jī)應(yīng)用研究，2005,22(9):15-18.

[4] 李慶先.基于內(nèi)容的圖像檢索相關(guān)反饋算法的改進(jìn)[J].計(jì)算技術(shù)與自動(dòng)化，2002,26(2):38-41.

[5] 劉琳,李仁發(fā),李仲生,劉鈺峰.基于內(nèi)容圖像檢索中的相關(guān)反饋技術(shù)研究[J].計(jì)算機(jī)應(yīng)用研究,2009,26(7):27-31.

[6] 李云.特征選擇算法及其在基于內(nèi)容圖像檢索中的應(yīng)用研究[D].重慶:重慶大學(xué),2005.

[7] 賴(lài)欣.基于相關(guān)反饋和綜合特征的圖像內(nèi)容檢索系統(tǒng)研究和實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2008.

[8] 張潔婧,侯曉慧,劉志鏡.基于相關(guān)反饋特證權(quán)的綜合CBIR系統(tǒng)設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用研究，2007,24(12):365-369.

[9] 韋娜,王濤.一種具有相關(guān)反饋的圖像檢索方法[J].計(jì)算機(jī)應(yīng)用與軟件，2007,24(12):168-170.

[10] 姜楠楠,齊敏,郝重陽(yáng).一種基于SVM的相關(guān)反饋圖像檢索算法[J].計(jì)算機(jī)仿真，2009,26(1)：219-221.