基于IPDSH興趣點空間區(qū)域劃分的圖像檢索

張 旭，郭寶龍，孟繁杰，孫 偉

（西安電子科技大學 智能控制與圖像工程研究所，西安 710071）

利用局部特征的圖像檢索主要分為基于圖像分割的方法和基于興趣點的方法。由于目前尚未找到一個通用的算法來有效分割圖像中的目標區(qū)域和背景，且易受到來自于光照、背景、仿射變換等許多因素的干擾，導致檢索準確度下降。而興趣點作為認知心理學中的注視焦點，可以對物體形狀粗略表征。另外它具有計算量小、信息含量高的特點，可以靈活地描述圖像的細節(jié)。將其應用于圖像檢索技術中，利用局部特征描述方法對其局部區(qū)域進行特征提取，最后再進行相似度匹配，可以有效提高檢索精度，且具有很好的通用性和穩(wěn)定性［1-4］。符祥等［5］在興趣點局部計算Zernike矩，通過比較興趣點局部Zernike矩的歐氏距離來提取最優(yōu)匹配點對，在去除不匹配的興趣點后利用興趣點的空間離散度來估計圖像內容的相似度；陳綿書等［6］將MPDD算法應用于圖像檢索，先將圖像均勻細分成小塊，然后用圖像的顏色特征和紋理特征表示圖像塊內容，采用K均值法對圖像塊進行聚類，產生包示例，最后應用MPDD算法對圖像進行檢索；Zheng等［7］在對圖像的每個區(qū)域檢測出興趣點后，結合興趣點的邊緣類型直方圖和不變量進行檢索；陳慧婷等人［8］將紋理概率統(tǒng)計模型和全局主顏色方法有機地結合起來，在對紋理和顏色特征線性加權的基礎上對組合后的紋理和顏色特征進行二次檢索；曾智勇等［9］以顯著興趣點為線索，設計了一種基于顯著興趣點的環(huán)形顏色直方圖，在利用興趣點局部特征的同時，又考慮了興趣點的空間分布結構。

以上研究成果更多地考慮到興趣點的空間分布信息，大大提高了圖像檢索的準確度，但是終究不能達到理想狀況，因為面對各式各樣的圖片種類時，某種單一的算法往往失去了通用性，因此距其實際應用還有很大差距。為了進一步提高圖像檢索準確度，本文提出了一種新的基于IPDSH和區(qū)域劃分的圖像檢索方法，該方法降低了傳統(tǒng)算法提取出的不穩(wěn)定興趣點對圖像檢索結果產生的干擾，考慮了圖像中感興趣區(qū)域的內部顏色特征和該區(qū)域在圖像中所處的空間位置，將其劃分為凸包和環(huán)形區(qū)域，提高了區(qū)域劃分方法的可靠性。

1 系統(tǒng)描述

首先對圖像在尺度空間中采用IPDSH算法檢測興趣點，然后按照興趣點的分布將圖像劃分成一系列同心圓環(huán)和凸包，最后統(tǒng)計每個圓環(huán)內部興趣點鄰域內的偽澤尼克矩（Pseudo－Zernike moments）和凸包內像素的顏色直方圖（Color histogram），并經(jīng)過加權處理生成特征向量。

圖像數(shù)據(jù)庫中每幅圖像的特征向量只需要計算一次，方法與查詢圖像相同，得到的集合就組成了特征數(shù)據(jù)庫。查詢圖像只需要與特征數(shù)據(jù)庫進行特征相似度匹配即可。經(jīng)過計算查詢圖像特征向量與圖像數(shù)據(jù)庫中每幅圖像的特征向量的相似度，并按照歐氏距離的大小進行排序，最后將相似度高的圖像顯示出來，就得到了相應的檢索結果。檢索流程如圖1所示。由于IPDSH興趣點和偽澤尼克矩的幅度都具有旋轉不變的性質，且環(huán)形區(qū)域劃分的方法也具有幾何對稱性，因此這種方法也具有旋轉、平移不變性。

圖1 圖像檢索流程圖Fig.1 Image retrieval structure system title

2 基于IPDSH興趣點的檢測

興趣點主要的一類是角點，其中，Harris角點檢測［10］是一種比較有效的方法，但是它對尺度變化非常敏感，這樣在對角點響應函數(shù)執(zhí)行非極大值抑制確定局部極大值時，角點提取的效果就完全依賴于閾值的設定。閾值大會丟失角點信息，閾值小又會提取出偽角點。針對這些問題，本文利用IPDSH興趣點檢測算法可以提高興趣點檢測的快速性和準確性。

對于輸入圖像f（x，y），利用二維高斯核對其進行卷積，得到多尺度空間序列：

其中，二維高斯核為

再使用DoG（Difference of Gaussian）函數(shù)對圖像卷積求取尺度空間極值，函數(shù)表達式為

定義尺度空間的自相關矩陣A為

式中：δi為積分尺度；δd為微分尺度；fx和fy分別為x和y方向上的導數(shù)；為對f做高斯濾波。記A的兩個特征值λ1和λ2為自相關函數(shù)的主曲率，則不同尺度空間的興趣點檢測公式為

圖2 IPDSH和SIFT興趣點檢測結果比較Fig.2 Comparison of detecting results of IPDSH and SIFT

若C的局部極大值坐標落在多尺度空間極值點鄰域內，則保留該極值點，否則剔除。然后檢測興趣點鄰域是否存在Harris角點，若存在，則保留該點且將其看作穩(wěn)定興趣點。其中，α為常數(shù)（一般取0.04～0.06），C的局部極大值計算方法是根據(jù)λ1和λ2的大小來確定的。圖2是一副Lena圖像的IPDSH和SIFT算法結果比較。從圖中可以看出，IPDSH算法有效地剔除了不穩(wěn)定的興趣點。使用IPDSH方法可以有效減少不穩(wěn)定興趣點對檢索結果的影響，提高了興趣點區(qū)域劃分和特征檢測的速度及準確度。

3 區(qū)域劃分和特征提取

3.1 凸包顏色直方圖

凸包是包圍一個平面興趣點集所有點的最小凸多邊形，應用于圖像處理、模式識別等諸多領域。凸包計算方法很多，考慮到運行速度，本文采用格雷厄姆掃描法來獲取興趣點凸包［11］。凸包內部區(qū)域即注視焦點的集中所在。由于興趣點本身具有形狀特征屬性，因此興趣點凸包可以實現(xiàn)感興趣物體和圖像背景的分割。圖3（a）是區(qū)域劃分的示意圖，圖3（b）是一副鮮花圖像區(qū)域劃分的結果。圖3（a）中的黑點代表興趣點，多邊形代表興趣點凸包。從圖3（b）中可以看出，圖像的興趣點凸包接近物體的輪廓，具有理想的提取感興趣區(qū)域能力。

圖3 空間區(qū)域劃分示意圖Fig.3 Schematic diagram to annular division

考慮到圖像中被關注物的整體顏色特征一般會有別于背景，而凸包可以有效描述出事物的大致外形，故本文采用顏色直方圖對凸包內像素進行處理。顏色直方圖具有旋轉，平移和縮放不變性。具體方法為：首先使用非等間隔量化方法對圖像HSV空間顏色進行量化，再將色調H空間分成8份，飽和度空間S和亮度空間V分成3份，然后將3個分量合成一個一維特征矢量I，且I＝9 H＋3S＋V。取值范圍是［0，71］，每個值都代表一種主要顏色。按照公式Hk＝numk／num（k＝0，1，…，L－1）對凸包內的顏色做直方圖統(tǒng)計，可以得到凸包顏色直方圖特征向量。其中numk為感興趣區(qū)域顏色為k的像素數(shù)量，num為區(qū)域內全部像素的數(shù)量，L為量化后顏色柄數(shù)。

3.2 環(huán)形區(qū)域偽澤尼克矩

將圖像空間按照興趣點的空間分布劃分成n個同心圓環(huán)，然后以每個興趣點為中心展開其周圍3×3鄰域統(tǒng)計每個圓環(huán)內部興趣點領域的偽澤尼克矩。圖3（b）中同心圓環(huán)表示環(huán)形區(qū)域劃分示意圖，圖中藍色“＋”號表示興趣點，綠色“＋”號表示同心圓的圓心，即興趣點的質心。具體劃分方法參考文獻［12］。由于這n個同心圓環(huán)具有對稱性，因此這種方法在提取顏色空間信息的同時也具有旋轉、平移不變性。偽澤尼克矩是不變矩的一種，具有比澤尼克矩更強的抗噪性。

圖像的偽澤尼克矩是將圖像映射到一組基函數(shù)上得到的，稱為偽澤尼克矩的基，記為｛Vnm（x，y）｝，這組基構成了單位圓（x2＋y2≤1）內的一組完備正交集，其定義為

這些多項式相互正交，滿足關系：

圖像f（x，y）的 （n，m）階偽澤尼克矩定義為

對于數(shù)字圖像，在極坐標下式（9）變?yōu)?/p>

計算圖像的偽澤尼克矩時，選圖像的興趣點為極坐標的原點，將單位圓內的像素映射為極坐標，單位圓外的像素在計算時不予考慮。

4 相似性度量

設Q為待查詢圖像，I為圖像庫中的一副圖像，使用加權特征距離來度量它們內容的相似度。用S1（Q，I）和S2（Q，I）分別表示Q 和I 的顏色特征和偽澤尼克矩的特征向量相似度，kc和kp表示權值（kc＋kp＝1），則相似度度量公式可以寫為

式中：N為興趣點總數(shù)目；ωk為第k個圓環(huán)興趣點的數(shù)目；H為顏色直方圖表達式；P為偽澤尼克矩。

S的值越大，則視為越相似。一般來說，圖像的形狀信息對于圖像檢索更為關鍵，所以通常取kp＞kc，本文通過大量實驗發(fā)現(xiàn)，當kp＝0.7、kc＝0.3時，檢索效果較好。

5 實驗結果

本文使用的圖像庫是SIMPLIcity測試集，它是從Corel圖像庫中抽取的1000幅圖像，這些圖像分屬10個類，編號為：1－土著居民和村莊；2－海灘；3－建筑和雕塑；4－公共汽車；5－恐龍；6－大象；7－花卉；8－馬；9－山地和冰川；10－食物。每類100幅，共1000幅圖（后續(xù)實驗中將以此編號作為種類編號）。圖4是從每類圖像中隨機抽取的一張圖片作為示意圖。

圖4 圖像數(shù)據(jù)庫示例Fig.4 Examples Images in the Database

為了驗證本文算法的檢索性能，在相同的軟硬件平臺下（軟件環(huán)境：Matlab7.1；硬件環(huán)境：Core 2Q8200CPU為2.33GHz，4.0GB內存），分別用本文算法與基于凸包和基于環(huán)形區(qū)域劃分的算法做了比較。實驗時提取的興趣點數(shù)為150個，顏色特征量化為HSV空間中的72維。興趣點環(huán)形劃分數(shù)為6。在1000幅圖像的測試集中對每一類圖像隨機抽取20幅，計算出返回圖像總數(shù)為20幅時的檢索準確度為

式中：T為輸出圖像總數(shù)；n為查準圖像數(shù)目。

圖5為三種算法的準確度比較曲線圖。從圖中可以看出，相對于單獨地使用凸包算法或環(huán)形區(qū)域劃分算法，將二者結合處理得到的檢索準確度更高。

圖5 不同算法檢索準確度比較Fig.5 Comparison of different algorithms’precision

圖6 不同方法對鮮花的檢索結果Fig.6 Retrieval result of flower using different methods

圖6（a）是使用凸包顏色直方圖進行檢索的結果，圖6（b）是使用環(huán)形區(qū)域中穩(wěn)定興趣點鄰域內的偽澤尼克矩進行檢索的結果，圖6（c）是本文算法檢索的結果。每幅圖中左上角的圖像為查詢圖像，其余圖像是查詢結果。從左到右，從上到下，相似度依次減小。分析發(fā)現(xiàn)，當返回的圖像數(shù)為20時，采用本文方法的20幅圖像都是花卉圖像，準確度為100%，如圖6（c）所示；凸包顏色直方圖的檢索結果有3幅圖像不正確，檢索準確度為85%，如圖6（a）所示；環(huán)形區(qū)域中穩(wěn)定興趣點鄰域內的偽澤尼克矩的檢索結果中有4幅圖像不正確，檢索準確度為80%，如圖6（b）所示。證明本文算法將凸包內的顏色直方圖與穩(wěn)定興趣點環(huán)形區(qū)域中興趣點鄰域內偽澤尼克矩有效結合，并將加權特征作為特征向量進行檢索，能獲得更高的準確度。

為了進一步說明本文方法的檢索性能，還將本文算法與文獻［13］和文獻［14］中算法做了實驗對比，其具體步驟為：隨機抽取20幅圖像作為查詢圖像，在圖像庫中進行相似度檢索，統(tǒng)計返回圖像數(shù)分別為10、20、30幅時的檢索準確度P10、P20、P30，然后對每一類圖像分別計算平均檢索準確度、，得到的結果見表1。

從表1中可以看出，利用本文算法進行圖像檢索的平均檢索準確度較文獻［13］的方法提高了7.0%，較文獻［14］的方法提高了15.1%，本文方法明顯較優(yōu)。

為了檢驗算法的復雜度，本文從特征提取時間復雜度和圖像檢索時間復雜度兩個方面將本文算法與文獻［13－14］中算法進行比較。

（1）特征提取時間復雜度。實驗中在Corel圖像庫中任意取100幅圖像，利用本文方法提取特征所需的平均時間為24.43s，采用文獻［13］提取特征所需的平均時間為42.58s，采用文獻［14］提取特征所需的平均時間為44.68s。

（2）圖像檢索時間復雜度。實驗中在Corel圖像庫中檢索出與查詢圖像相似度最大的20幅圖像并顯示，本文算法的平均檢索時間為1.72s；文獻［13］算法的平均檢索時間為2.35s；文獻［14］算法的平均檢索時間為3.59s。從實驗結果可以看出，本文算法的特征提取時間復雜度和檢索時間復雜度都小于其他兩種算法。

表1 本文算法與其他算法的檢索性能比較Table 1 Precision of different methods

6 結束語

使用IPDSH方法可以有效提取尺度空間穩(wěn)定的興趣點。通過這些興趣點集合來求取凸包和劃分環(huán)形區(qū)域，并在此基礎上提取凸包顏色直方圖和圖像的環(huán)形區(qū)域中穩(wěn)定興趣點鄰域內的偽澤尼克矩，加權處理后得到圖像的特征向量，最后利用相似度檢索方法來檢索圖片。該檢索方法計算簡單，并且具有旋轉、平移和縮放不變性。實驗結果表明，該方法與傳統(tǒng)的基于興趣點的檢索方法相比，算法的復雜度小，檢索速度快，并能大幅度提高圖像檢索的準確度。在今后的工作中，將把相關反饋的技術結合到本算法中，從而更有效地提高檢索精度。另外，使用數(shù)量更大、種類更全的數(shù)據(jù)庫來進行檢索，也將是下一步工作的重點。

［1］Schmid C，Mohr R.Local gray value invariants for image retrieval［J］.IEEE Transaction on PAMI，1997，19（5）：530－535.

［2］Mikoljczyk K，Schmid C.Indexing based on scale－Invariant feature［C］∥Proc of International Conference on Computer Vision，Vancouver，2001.

［3］Shao H，F(xiàn)errari V，Svoboda T，et al.Fast indexing for image retrieval based on local appearance with re－ranking［C］∥Proceedings of IEEE International Conference on Image Processing，Barcelona，Spain，2003.

［4］汪華章，何小海，宰文姣.基于局部和全局特征融合的圖像檢索［J］.光學精密工程，2008，16（6）：1098－1104.Wang Hua－zhang，He Xiao－h(huán)ai，Zai Wen－jiao.Image retrieval based on combining local and global features［J］.Optics and Precision Engineering，2008，16（6）：1098－1104.

［5］符祥，曾接賢.基于興趣點匹配和空間分布的圖像檢索方法［J］.中國激光，2010，37（3）：774－778.Fu Xiang，Zeng Jie－xian.A novel image retrieval method based on interest points matching and distribution［J］.Chinese Journal of Lasers，2010，37（3）：774－778.

［6］陳綿書，楊樹媛，趙志杰，等.多點多樣性密度算法及其在圖像檢索中的應用［J］.吉林大學學報：工學版，2011，41（5）：1456－1460.Chen Mian－shu，Yang Shu－yuan，Zhao Zhi－jie，et al.Multi－points diverse density learning algorithm and its application in image retrieval［J］.Journal of Jilin University（Engineering and Technology Edition），2011，41（5）：1456－1460.

［7］Zheng X，Zhou M，Wang X C.Interest point based medical image retrieval［C］∥Lecture Notes in Computer Science.Beijing：Springer Verlag，2008.

［8］陳慧婷，覃團發(fā)，唐振華，等.綜合紋理統(tǒng)計模型與全局主顏色的圖像檢索方法［J］.北京郵電大學學報，2011，34：100－103，118.Chen Hui－ting，Qin Tuan－fa，Tang Zhen－h(huán)ua，et al.A method of image retrievals based on texture probability statistics and global dominant color［J］.Journal of Beijing University of Posts and Telecommunications，2011，34：100－103，118.

［9］曾智勇，張學軍，崔江濤，等.基于顯著興趣點顏色及空間分布的圖像檢索新方法［J］.光子學報，2006，35（2）：308－311.Zeng Zhi－yong，Zhang Xue－jun，Cui Jinag－tao，et al.A novel image retrieval algorithm based on color and distribution of prominent interest points［J］.Acta Photonica Sinca，2006，35（2）：308－311.

［10］全燕鳴，黎淑梅.大型工件測量系統(tǒng)中的快速圖像拼接方法［J］.華南理工大學學報：自然科學版，2011，39（8）：60－65.Quan Yan－ming，Li Shu－mei.Fast image mosaic method for large－scale workpiece measurement system［J］.Journal of South China University of Technology（Natural Science），2011，39（8）：60－65.

［11］Preparata F P，Shamos M I.Computational Geometry：an Introduction［M］.New York：Springer－Verlag，1985.

［12］孟繁杰，郭寶龍.一種基于興趣點顏色及空間分布的圖像檢索方法［J］.西安電子科技大學學報：自然科學版，2005，32（2）：256－259.Meng Fan－jie，Guo Bao－long.A novel image retrieval algorithm based on the color and distribution of interest points［J］.Journal of Xidian University（Natural Science），2005，32（2）：256－259.

［13］王向陽，陳景偉，于永健.一種基于彩色邊緣綜合特征的圖像檢索方法［J］.華南理工大學學報，2010，23（2）：216－221.Wang Xiang－yang，Chen Jing－wei，Yu Yong－jian.Edge－based color image retrieval by using multiple features［J］.Pattern Recognition and Artificial Intelligence，2010，23（2）：216－221.

［14］Wu J H，Wei Z R，Li C Y.Color and texture feature for content based image retrieval［J］.International Journal of Digital Content Technology and Its Applications，2010，4（3）：43－49.