基于新的空間關系特征的圖像檢索方法

郭倩 楊紅菊 梁新彥

摘要：圖像與圖像之間沒有清晰的空間結構，這樣就不能有效利用圖像間空間結構上的相關性信息，針對此問題提出一種基于新的空間關系特征的圖像檢索方法。首先，提取待查詢圖像在內的全部圖像的特征向量。然后，計算特征向量每兩個之間的相似性，形成相似性矩陣。將相似性矩陣的列集合作為新特征向量，命名為新的空間關系特征向量，從而將原來的特征向量映射到一個歐氏空間上。最后，在新特征空間上計算相似性，特征向量之間的相似性問題就轉化為新的空間關系特征向量之間的相似性問題。在新特征空間上，圖像與圖像之間的空間結構變得清晰了，有利于圖像檢索準確度的提高。在Corel數(shù)據(jù)庫上進行實驗，所提方法在平均檢索查準率、查全率查準率和可視化評價指標上都優(yōu)于基于顏色直方圖的圖像檢索方法。結果表明，基于新的空間關系特征的圖像檢索方法有效利用了圖像間空間結構上的相關性信息，具有更好的檢索效果。

關鍵詞：

空間結構；特征向量；相似性矩陣；特征空間；圖像檢索

中圖分類號： TP391.413 文獻標志碼：A

0引言

隨著互聯(lián)網時代的到來，圖像數(shù)量飛速增長，要從數(shù)以萬計的圖像中尋找需要的圖像是一件困難的事情，這就促進了圖像檢索相關技術的飛速發(fā)展。圖像檢索可分為基于文本的圖像檢索[1]和基于內容的圖像檢索[2]?；谖谋镜膱D像檢索技術是通過人工對圖像進行標注，然后通過這些標注來實現(xiàn)圖像檢索的過程。此方法由于人工工作量大及標注的因人而異，使用起來具有很大的局限性?；趦热莸膱D像檢索技術則通過提取圖像的顏色、紋理以及形狀等底層特征[3]形成特征庫，將查詢圖像的特征提取出來與特征庫里的特征進行匹配，返回匹配的圖像，從而實現(xiàn)圖像的自動化查詢檢索。基于內容的圖像檢索技術由于其自動化的檢索過程，越來越多地受到人們的青睞。

特征提取是圖像檢索的重要過程，現(xiàn)有的特征提取方法一般是提取圖像的顏色、紋理及形狀等底層特征[3]。顏色直方圖作為常用的顏色特征，可以表現(xiàn)圖像的全局顏色分布，因其平移、旋轉和縮放不變性被廣泛應用于圖像檢索中，文獻[4]提出一種模糊空間顏色直方圖，這種特征包括圖像內部的顏色和空間兩種信息，其特點是模糊量化，當精確分割不可用時可以選擇性集成前景圖像。Yu等[5]在2013年提出了尺度不變特征轉換（ScaleInvariant Feature Transform， SIFT）局部二值模式（Local Binary Pattern， LBP）的特征表征方法。該方法使底層紋理特征與SIFT結合，具有較好的檢索效果。方向梯度直方圖（Histogram Of Gradient， HOG）是經典的形狀特征提取方法之一，Dalal等[6]在2005年經典方法HOG+支持向量機（Support Vector Machine， SVM）中首次提出了HOG。Kato等[7]于2015年提出Segmental HOG描述子，其靈活的模板可以自動適應輸入圖像從而使檢測更加魯棒。除了單獨提取顏色、紋理和形狀等底層特征[3]作為特征向量，不少方法還將三者中至少兩者相結合，并得到了不錯的效果。Sandhu等[8]提出將顏色、紋理和形狀特征相結合的方法，從而可以充分利用圖像內部顏色、紋理的空間分布進行圖像檢索。以上方法雖然有些利用了圖像內部的空間分布信息，但未利用圖像間空間結構上的相關性信息。

符號數(shù)據(jù)與數(shù)值型數(shù)據(jù)不同，符號數(shù)據(jù)缺乏一個清晰的空間結構，針對這種情況，Qian等[9]提出了空間結構與符號數(shù)據(jù)聚類的方法。該方法提出一種新的數(shù)據(jù)表示方式，它將一系列的符號對象映射到一個歐氏空間，在這個新特征空間上，就可以計算符號數(shù)據(jù)之間的距離，從而進行符號數(shù)據(jù)的聚類。

圖像與圖像之間沒有清晰的空間結構，本文利用文獻[9]的方法，提出一種基于新的空間關系特征的圖像檢索方法。首先，計算特征向量兩兩之間的相似性，形成相似性矩陣，將相似性矩陣歸一化到[0，1]，相似性矩陣的列集合作為新特征向量即新的空間關系特征向量，這樣就將沒有清晰空間結構的特征向量映射到一個歐氏空間上；最后，在新特征空間上重新計算相似性，特征向量之間的相似性問題就轉化為新的空間關系特征向量之間的相似性問題。在新特征空間上，圖像與圖像之間的空間結構變得清晰了，這樣做有利于圖像檢索準確度的提高。

1新的空間關系特征

Qian等[9]提出的空間結構與符號數(shù)據(jù)聚類的方法，其具體過程如下：

給定一個符號數(shù)據(jù)集，如表1所示。其中U={x1，x2，…，xn}是n個符號對象，A={a1，a2，…，am}是m個權重為W={w1，w2，…，wm}的符號特征，ai（xj）是對象xj的特征ai的符號值?，F(xiàn)給出符號對象的一種新的數(shù)據(jù)描述方式，計算符號對象兩兩之間的相似性，其定義為：

本文得到一種通過描述符號對象之間相似性的新的空間結構。為討論方便，假設各特征的權重相等（雖然這樣會使其失去一般性），用新維度{ci=xi，1≤i≤n}描述對象，xi（cj）是映射到新維度cj上的對象xi，如表2所示。

空間結構與符號數(shù)據(jù)聚類方法[9]的工作原理在例1中闡明。

例1給出一個包括3個六面體的符號數(shù)據(jù)集，每個六面體包括6個特征，如表3所示。

假設這些特征有相同的權重w1=w2=…=w6=1/6，使用經典集合理論，可以獲得三個對象之間的六個特征的集合關系，它可以描述數(shù)據(jù)集在每個特征上的類結構，如圖1（a）所示。然而，在整個特征空間上，這種方法不能很好地發(fā)現(xiàn)潛在的類結構。在下文中，建立它的空間結構。首先，通過表3，可以計算符號數(shù)據(jù)集中任意兩個對象xi=xj的概率，通過計算，它們的結果如表4所示。

通過空間結構矩陣，原始結構數(shù)據(jù)集通過三個新特征c1=x1、c2=x2和c3=x3轉換到一個歐氏空間，如圖1（b）所示，從這三個對象的幾何結構可以看出對象x1和對象x2之間的距離比起對象x1和對象x3之間的距離、對象x2和對象x3之間的距離都近多了。

將Qian等[9]提出的空間結構與符號數(shù)據(jù)聚類的思想應用到圖像檢索上，每幅圖像對應著一個符號對象，圖像的特征向量維數(shù)對應著符號對象的特征個數(shù)，則圖像的特征向量就對應著符號對象的特征集合。

現(xiàn)給出圖像的一種新的數(shù)據(jù)描述方式即新的空間關系特征，其定義為：

計算圖像的特征向量兩兩之間的相似性，形成相似性矩陣，稱相似性矩陣的列集合為新的空間關系特征，某圖像的新的空間關系特征向量表示的是該圖像與全部圖像之間的相似性關系。

將圖像的特征向量通過新的空間關系特征映射到一個歐氏空間后，圖像的新維度就對應著符號對象的新維度，圖像的新的空間關系特征向量就對應著符號對象的新維度集合。沒有清晰空間結構的特征向量之間的相似性問題就轉化為新特征空間下有清晰空間結構的新的空間關系特征向量之間的相似性問題，通過圖像在新特征空間下的幾何關系就可以得到圖像的相似圖像。

2基于新的空間關系特征的圖像檢索

2.1圖像檢索的查詢方式

由于圖像特征本身的復雜性，圖像的查詢方式也有多種[10]。特征查詢指的是查詢時用戶可以選擇顏色、形狀以及紋理等單個特征或按某權值的特征組合，如單一特征“檢索40%綠色、50%紅色、10%藍色的圖像”，如多個特征“檢索包含綠色和花朵紋理的圖像，其中藍色的權重為15%、紋理為85%”。草圖查詢指的是用戶畫出與查詢的圖像顏色、形狀或紋理相似的草圖。瀏覽檢索指的是用戶瀏覽圖像庫中的圖像，找到與自己的目標圖像相近的圖像后再把其作為要查詢圖像的例子，這種方式適用于用戶檢索目的不明確或對圖像庫中的信息結構、類型等不太了解的情況。示例查詢指的是用戶給出要查詢圖像的例子，提取特征后與圖像庫中圖像比較，找出和要查詢圖像特征相似的圖像。示例查詢既方便又簡單，所以大部分圖像檢索系統(tǒng)都采用這種查詢方式，這也是本文采用的查詢方式。

2.2本文方法與一般圖像檢索方法的區(qū)別

圖像檢索一般分為兩個步驟，如圖2（a）所示。一般圖像檢索方法步驟中，在原始特征空間上，圖像之間的空間結構不夠清晰。本文方法是在圖像檢索步驟中增加了一步，如圖2（b）所示，將提取后的特征映射到一個歐氏空間上，在新特征空間上，可以清晰地看出圖像之間的空間結構，從而有利于圖像檢索準確度的提高。

2.3本文方法的具體實現(xiàn)過程

基于新的空間關系特征的圖像檢索方法的具體過程如下。

1）特征提取。假設圖像庫中有n幅圖像，分別命名為m1，m2，…，mn，使用該方法對n幅圖像進行特征提取，提取出來的特征向量分別為F1，F(xiàn)2，…，F(xiàn)n，每個特征向量的維數(shù)是相等的。

2）將特征向量映射到一個新特征空間（歐氏空間）上。任取圖像庫中的第i（i∈（1，n））幅圖像mi作為查詢圖像，計算查詢圖像mi的特征向量Fi與圖像庫中各圖像的特征向量之間的相似性，記作Wi={wi，1，wi，2，…，wi，n}，其中wi， j表示查詢圖像mi的特征向量Fi與圖像庫中第j（j∈（1，n））幅圖像mj的特征向量Fj之間的相似性，則每幅圖像的特征向量與圖像庫中各圖像的特征向量之間的相似性可形成n×n此處的大寫N，與后面的小寫n，是否需要保持一致？請明確。的相似性矩陣W，將W歸一化到[0，1]區(qū)間。

W=w1，1w1，2…w1， j…w1，n

w2，1w2，2…w2， j…w2，n

wi，1wi，2…wi， j…wi，n

wn，1wn，2…wn， j…wn，n（2）

其中i， j∈（1，n）。

當數(shù)據(jù)庫較大時，相似性矩陣采用分塊存儲的方法，相似性計算過程則采用并行計算以縮短檢索時間。此時，圖像的特征向量就映射到一個歐氏空間，相似性矩陣的每列為圖像的一個新維度，稱圖像的新維度集合為圖像的新的空間關系特征向量，相似性矩陣的每行就是相應圖像的新的空間關系特征向量Wi={wi，1，wi，2，…，wi，n}（i∈（1，n））。

3）在新特征空間上特征匹配。當待查詢圖像mi與圖像庫中的某幅圖像mj具有相近的相似圖像集和不相似圖像集時，則這兩幅圖像是相似圖像的可能性很大。沒有清晰空間結構的特征向量之間的相似性問題就轉化為新特征空間下有清晰空間結構的新的空間關系特征向量之間的相似性問題，查詢圖像mi與圖像mj是否相似的問題則轉換為計算圖像mi的新的空間關系特征向量Wi={wi，1，wi，2，…，wi，n}與圖像mj的新的空間關系特征向量Wj={wj，1，wj，2，…，wj，n}是否相似的問題（i， j∈（1，n））。返回此特征匹配結果，當本文方法檢索準確度高于在原始特征空間上的檢索準確度時，說明本文方法有效。

3實驗過程與結果分析

3.1實驗過程分析

實驗以顏色直方圖為例，說明本文方法的有效性。顏色直方圖是在各圖像檢索系統(tǒng)中被廣泛使用的顏色特征，它描述了一幅圖像中不同顏色所占的比例情況。相似內容的圖像一般會有相似的顏色比例，顏色直方圖就是將顏色空間按某種規(guī)律分為若干區(qū)間，每個區(qū)間為一個柄，對柄內像素個數(shù)進行統(tǒng)計并歸一化處理后得到的。

本文采用文獻[11]提出的（16∶4∶4）非均勻量化方案對六角錐體模型HSV（Hue Saturation Value）顏色空間的圖像進行量化，即先將圖像轉化到HSV顏色空間，將圖像的色調（Hue， H）分量量化成16個值，飽和度（Saturation， S）和亮度（Value， V）分量分別量化成4個值。量化后可以獲得16×4×4=256種顏色，將三維顏色直方圖沿H分量方向將相鄰的兩個值相加，將相加的和作為新的三維顏色直方圖。由于人眼對HSV顏色空間的色彩有較好的感知和鑒別力，現(xiàn)有方法很多都將圖像先換轉到HSV顏色空間，再對其3個分量分別量化，這樣對顏色的輕微變化會具有魯棒性，而且HSV顏色空間可以方便地與三原色RGB（Red Green Blue）顏色空間進行相互轉換，如文獻[12]和文獻[13]。故先將圖像轉換到HSV顏色空間，然后通過顏色直方圖特征提取方法提取待查詢圖像在內的全部圖像的顏色特征向量，在全局相似性圖像檢索基準數(shù)據(jù)庫Corel[14]數(shù)據(jù)庫上進行實驗。本文選取Corel 5k數(shù)據(jù)庫，該數(shù)據(jù)庫有50類圖像，每類圖像都有100張，這100張圖像相互之間就是相似圖像。

本文的所有實驗都在基于Windows 7操作系統(tǒng)上的Matlab R2012b編程平臺上進行實驗，并采用平均檢索查準率（Average Retrieval Precision， ARP）[5]評價、查全率查準率評價和可視化評價3個評價指標來驗證，以證明本文提出方法的有效性。

3.2實驗結果分析

3.2.1ARP評價

設mi為查詢的圖像，B（mi）為檢索結果的相似圖像集和不相似圖像集之和，A（mi）為檢索結果中的相似圖像集，則查詢圖像mi的查準率P（mi）為：

P（mi）=A（mi）∩B（mi）/B（mi）（3）

平均檢索查準率定義為：

ARP（IDk）=1N∑id（mi）=IDkP（i）（4）

其中：IDk是圖像的類別，k在全局相似性圖像檢索基準數(shù)據(jù)庫Corel 5k數(shù)據(jù)庫的取值范圍為1到50，分別表示這50類圖像；id（mi）為查詢圖像mi的類別；N為IDk類的圖像總數(shù)，取值為100。在本文中，B（mi）取100，恰好為50類中每類圖像的總數(shù)。假設某類圖像的ARP等于0.6，則表示把該類圖像的每張圖像都作為查詢圖像后返回相似性最高的前100張圖像，將返回結果中正確的張數(shù)相加取平均值，則這個平均值是60幅。

實驗結果如表5所示，由表可知采用新的空間關系特征的50類圖像平均ARP值要高于采用顏色直方圖特征的50類圖像平均ARP值。

3.2.2查全率查準率評價

僅從ARP的角度來說明檢索效果的好壞缺乏全面性，本文采取查全率查準率評價來說明本實驗方法的優(yōu)越性。查準率衡量的是檢索出的相似圖像集與檢索出的全部圖像集（相似圖像集與不相似圖像集之和）的百分比率。查全率衡量的是檢索出的相似圖像集與圖像庫中全部相似圖像集的百分比率。查全率和查準率之間是互逆的：如果將圖像庫中的所有圖像返回為結果集合，則查全率為100%，但查準率很低；如果檢索結果只返回唯一的相似圖像，則查準率為100%，但查全率很低。以此評價指標評價算法時，先按照查全率查準率繪制曲線，假定查全率為某合適值，按照查準率的高低情況來衡量算法是否有效。

實驗在每類圖像中隨機抽取2幅共100幅圖像，將50類圖像查準率、查全率的平均值作為實驗的最終結果。由圖3可知：1）在查全率相同時，采用新的空間關系特征比采用顏色直方圖特征有更高的查準率。2）從整體看，采用新的空間關系特征比采用顏色直方圖特征有更高的圖像檢索準確率。

3.2.3可視化評價

檢索結果的可視化可反映檢索結果的空間排列，使用可視化評價可以更直觀地展現(xiàn)檢索結果，確認檢索結果是否符合人們需要。本文取檢索返回結果的前15幅作為評價圖像，來評價基于新的空間關系特征的圖像檢索方法的優(yōu)劣。

根據(jù)圖4可知，采用顏色直方圖特征的查詢結果中有五幅是錯誤的，并且從第2幅圖像就開始出錯，而采用新的空間關系特征的查詢結果中有兩幅是錯誤的，出錯圖像從第7幅開始。由可視化結果可知，本文方法更有效。

4結語

本文提出一種基于新的空間關系特征的圖像檢索方法，該方法在一般圖像檢索步驟的基礎上，增加了將提取后的特征映射到一個歐氏空間上這一步，在新特征空間上再進行特征匹配，返回檢索結果。在新特征空間上，可以充分利用圖像間空間結構上的相關性信息，實驗結果表明本文的圖像檢索方法比在原始特征空間上的圖像檢索方法更有效。下一步考慮繼續(xù)從更多方面使用合適的機器學習思想完善圖像檢索的各個步驟，使得檢索準確度有更進一步的提高。

參考文獻：

[1]

BACH J R， FULLER C， GUPTA A， et al. Virage image search engine： an open framework for image management [C]// Storage and Retrieval for Image and Video Databases IV. San Jose， CA： SPIE， 1996， 2670： 76-87.

[2]

DATTA R， JOSHI D， LI J， et al. Image retrieval： ideas， influences， and trends of the new age [J]. ACM Computing Surveys， 2008， 40（2）： 2007.

[3]

YONG R， HUANG T S， CHANG S F. Image retrieval： current techniques， promising directions， and open issues [J]. Journal of Visual Communication & Image Representation， 1999， 10（1）： 39-62.

[4]

XIANG Z J， CHEN Q， LIU Y. Person reidentification by fuzzy space color histogram [J]. Multimedia Tools and Applications， 2014， 73（1）： 91-107.

[5]

YU J， QIN Z， WAN T， et al. Feature integration analysis of bagoffeatures model for image retrieval [J]. Neurocomputing， 2013， 120（10）： 355-364.

[6]

DALAL N， TRIGGS B. Histograms of oriented gradients for human detection [C]// CVPR 2005： Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2005： 886-893.

[7]

KATO T， RELATOR R， NGOUV H， et al. Segmental HOG： new descriptor for glomerulus detection in kidney microscopy image [J]. BMC Bioinformatics， 2015， 16（1）： 1-16.

[8]

SANDHU A， KOCHHAR A. Content based image retrieval using texture， color and shape for image analysis [J]. International Journal of Computers & Technology， 2012， 3（1）： 149-152.

[9]

QIAN Y， LI F， LIANG J， et al. Space structure and clustering of categorical data [J]. IEEE Transactions on Neural Networks & Learning Systems， 2015， PP（99）： 1-13.

[10]

黃祥林，沈蘭蓀.基于內容的圖像檢索技術研究[J].電子學報，2002，30（7）：1065-1071.（HUANG X L， SHEN L S. Research on contentbased image retrieval techniques [J]. Acta Electronica Sinica， 2002， 30（7）： 1065-1071.）

[11]

陳秀新，賈克斌.三維量化顏色直方圖在彩色圖像檢索中的應用[J].計算機應用與軟件，2012，29（9）：31-32.（CHEN X X， JIA K B. Application of threedimensional quantised color image retrieval [J]. Computer Applications and Software， 2012， 29（9）： 31-32.）

[12]

周明全，韋娜，耿國華.交互信息理論及改進的顏色量化方法在圖像檢索中的應用研究[J].小型微型計算機系統(tǒng)，2006，27（7）：1331-1334.（ZHOU M Q， WEI N， GENG G H. Research to the application of mutual information and improved color quantization method in content based image retrieval [J]. Journal of Chinese Computer Systems， 2006， 27（7）： 1331-1334.）

[13]

張水利，鄭秀萍，雷文禮.基于量化顏色空間的彩色圖像檢索算法[J].計算機仿真，2011，27（10）：194-196.（ZHANG S L， ZHENG X P， LEI W L. Method of color image retrieval based on quantified color space [J]. Computer Simulation， 2011， 27（10）： 194-196）.

[14]

WANG J Z， LI J， WIEDERHOLD G. SIMPLIcity： semanticssensitive integrated matching for picture libraries [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（9）： 947-963.