郭倩 楊紅菊 梁新彥

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

關(guān)鍵詞：

空間結(jié)構(gòu)；特征向量；相似性矩陣；特征空間；圖像檢索

中圖分類號： TP391.413 文獻標(biāo)志碼：A

0引言

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

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

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

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

1新的空間關(guān)系特征

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

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

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

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

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

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

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

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

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

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

將圖像的特征向量通過新的空間關(guān)系特征映射到一個歐氏空間后，圖像的新維度就對應(yīng)著符號對象的新維度，圖像的新的空間關(guān)系特征向量就對應(yīng)著符號對象的新維度集合。沒有清晰空間結(jié)構(gòu)的特征向量之間的相似性問題就轉(zhuǎn)化為新特征空間下有清晰空間結(jié)構(gòu)的新的空間關(guān)系特征向量之間的相似性問題，通過圖像在新特征空間下的幾何關(guān)系就可以得到圖像的相似圖像。

2基于新的空間關(guān)系特征的圖像檢索

2.1圖像檢索的查詢方式

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

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

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

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

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

1）特征提取。假設(shè)圖像庫中有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）。

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

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

3實驗過程與結(jié)果分析

3.1實驗過程分析

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

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

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

3.2實驗結(jié)果分析

3.2.1ARP評價

設(shè)mi為查詢的圖像，B（mi）為檢索結(jié)果的相似圖像集和不相似圖像集之和，A（mi）為檢索結(jié)果中的相似圖像集，則查詢圖像mi的查準(zhǔn)率P（mi）為：

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

平均檢索查準(zhǔn)率定義為：

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

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

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

3.2.2查全率查準(zhǔn)率評價

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

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

3.2.3可視化評價

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

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

4結(jié)語

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

參考文獻：

[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]

黃祥林，沈蘭蓀.基于內(nèi)容的圖像檢索技術(shù)研究[J].電子學(xué)報，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]

陳秀新，賈克斌.三維量化顏色直方圖在彩色圖像檢索中的應(yīng)用[J].計算機應(yīng)用與軟件，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]

周明全，韋娜，耿國華.交互信息理論及改進的顏色量化方法在圖像檢索中的應(yīng)用研究[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.