一種基于MD5的近似圖像檢測算法研究

摘 要:在WWW圖像搜索引擎中，如何快速而準確地檢測出近似或重復圖像已經成為亟待解決的問題，提出一種基于MD5的近似圖像檢測算法。該算法選取圖像分塊灰度均值為特征，經過拉普拉斯特征值降維，矢量量化后，圖像特征被轉換為MD5值，然后根據生成的MD5值進行近似或重復圖像檢測。實驗結果表明該算法是有效的。

關鍵詞:圖像檢索; 近似圖像; MD5; 拉普拉斯特征值降維

中圖法分類號:TP391

文獻標志碼:A

文章編號:1001-3695(2010)02-0788-03

doi:10.3969/j.issn.1001-3695.2010.02.109

Research of similar images detection algorithm based on MD5

YE Zhi-wei1， XIA Bin1， WANG Da-zhen1， ZHANG Yan-chao2

(1. School of Computer Science， Hubei University of Technology， Wuhan 430068， China;

2 .School of Computer Science， Wuhan University of Technology， Wuhan 430070， China)

Abstract: There are many similar or duplicate images in the World Wide Web， how to efficiently and accurately find those images has become an issue in search engine research area. This paper presented a similar images detection algorithm based on MD5， which selected the average of gray-block for feature. MD5 was generated by the feature after Laplacian eigenmap dimensionality reduction and vector quantization， then it detected the similar or duplicate images by the MD5. Experimental results show that the algorithm is effective.

Key words: image retrieval; similar image; MD5; Laplacian eigenmap

目前，大量的圖像以數字化的方式進行存儲和傳輸，而Internet的快速發展更加大了圖像的傳播范圍與傳播速度，從而帶來了近似或重復圖像的問題，即一幅圖像存在多個不同版本。用戶越來越多地使用圖像搜索引擎檢索圖像，圖像搜索引擎一般會返回與查詢詞相關的多幅圖像。但是，在返回的圖像中往往包含有大量近似或重復圖像。如圖1所示，該圖是2009年2月9日使用Live Search圖像搜索引擎輸入檢索詞apple得到的第一頁結果，可以看到，其中包含有相當數量的近似圖像。這種近似圖像給用戶的瀏覽帶來了信息冗余，同時也浪費了網絡帶寬。另外，近似圖像檢測也是基于內容的圖像檢索(content-based image retrieval， CBIR)的關鍵技術[1，2]。因此，如何快速而準確地檢測出近似或重復圖像[3]已經成為亟待解決的問題。

一般來講，對于具有n幅圖像的數據集，尋找出所有的近似圖像需要進行O(n2)次比較。當n較大時，所需比較次數會快速增加。一些已有的具有較高計算復雜度的方法[4~7]難以應用到大規模數據集中的近似圖像檢測中。針對上述問題，本文提出一種基于MD5的近似圖像檢測算法，通過MD5值的匹配來實現近似或重復圖像的快速檢測。

1基于MD5的近似圖像檢測算法

本文描述了一種能夠在大規模圖像數據庫中快速而準確地尋找近似圖像的方法?；贛D5的近似圖像檢測算法由三個主要部分組成，分別是圖像特征提取、特征降維以及MD5值的生成。算法步驟如圖2所示。

每幅圖像首先轉換為對應的特征，表示為高維矢量;然后該矢量被映射到一個維數較低的子空間中。在此映射過程中，特征矢量的主要信息仍然得到了保留。降維后的矢量通過矢量量化的方式轉換為二進制字符串，該字符串被稱為是這幅圖像對應的MD5值;最后，利用這些MD5值之間的匹配關系進行近似或重復圖像的檢測。由于MD5值的二進制特性，其索引和搜索均可以快速地進行。

1.1 圖像的特征表示

數字圖像本身具有較大的數據量，為了便于處理，一般都采用從圖像中提取出的特征信息表示圖像內容的關鍵信息。在近似圖像檢測中，所選擇的圖像特征信息要能夠表達圖像的主要視覺信息，同時包括表達顏色信息以及空間結構信息;另外，該特征還需要有一定的健壯性。據此，本文采用分塊灰度均值特征。如圖3所示，圖像首先被均勻分割為N×N塊。對于每一塊，計算該塊內所有像素的平均灰度值，即

fk=1Nk∑i，j∈BkI(i，j); k=1，2，…，n2(1)

其中:Bk代表第k個塊;Nk是該塊中像素的數目;I(i，j)是位于坐標(i，j)處的像素灰度值。因此，一幅圖像可以表示為矢量Fi=(f1，f2，…，fn×n)T。該矢量的維數為N2，但在一般情況下圖像表示為高維矢量。另外，圖像的灰度均值特征矢量計算較為簡單，對于每個塊只需要簡單的加法和一次除法就可以完成，有利于大規模圖像數據的快速處理。

圖像灰度均值特征可以較好地適應圖像尺度變化、顏色變化以及存儲格式不同而引起的失真。因此，分塊灰度均值特征不但計算簡單，同時能夠適應近似或重復圖像中可能出現的多種變化。

1.2特征降維

高維矢量給數據的索引和搜索帶來了困難，所以需要將其維數降低到一個合理的范圍內。對于近似圖像檢測而言，特征降維的目的有兩個:a)將原來高維的特征降低到一個合理的、易于處理的子空間內;b)由于降維會濾除部分原始信息，期望通過降維過程去除一定的噪聲信息。為了在維數劇烈縮減的情況下保留圖像的非線性結構，不丟失圖像特征，提高識別準確度，本文使用拉普拉斯特征值映射(Laplacian eigenmap，LE)降維算法[8]。對于高維數縮減的圖像檢索系統來說，LE算法可以獲得更佳效果[9]。

gi=AF(2)

其中:gi為降維后的特征矢量;A為投影矩陣。

利用LE進行降維的主要目標就是確定將高維矢量投影到其子空間的投影矩陣，而該矩陣是與實際數據相關的，這就造成對圖像的遍歷需要進行兩次。當數據量增大時，每次遍歷數據庫操作會耗時較多。為了節省這些不必要的操作，采取將投影矩陣預先固定的做法。首先構造一個足夠大的圖像集合，包含約10萬張來自網絡的各種圖像;然后利用這些圖像得到分塊灰度均值特征對應的投影矩陣。對于所有圖像，都使用該投影矩陣進行降維。這樣，只需要對圖像數據庫進行一次遍歷就可以得到降維之后的結果，提高了系統的運行速度。

1.3MD5值生成

從降維之后的特征向量gi產生MD5值mi={Mi，k ，k=1，2，3，…，k}實際上是一種矢量量化過程。假設最終生成的二進制字符串總共有K bit，本文采用各維之間獨立量化，并且每一維被固定分配1 bit。具體量化方法如下:

Mi，k=1 if Gi，k>meank0 if Gi，k≤meank(3)

其中:meank代表了該維的均值。通過矢量量化，K維的特征值被量化成K bit，將這K bit組成的有序二進制字符串mi稱為這幅圖像的MD5值。從上面的生成過程可見，該MD5值來自于圖像的視覺內容信息，但是經過一系列的處理后變成了簡潔的表現形式。由于MD5值的二進制特性，其索引和搜索均可以快速地進行。

1.4 通過MD5值進行近似圖像檢測

在傳統的基于MD5的檢索方法中，當給定目標的MD5值后，系統在數據庫中尋找與其具有相同MD5值的數據并將其呈現給用戶。由于搜索過程基于MD5值的精確匹配，這個過程中可以利用多種快速的索引和存儲算法，但是利用式(3)生成的圖像MD5值本身就可能受到一定的噪聲影響，另外，圖像矢量量化過程也可能帶來信息的損失。處于量化邊界兩邊的點，雖然實際距離很近，但是經過量化后的距離會較大;而處于量化邊界同側的點，雖然其實際距離可能很遠，但是經過量化后其距離很近。

為了提高系統性能，不能只尋找與目標圖像具有相同MD5值的圖像，而應尋找與其MD5值距離較近的圖像。由于MD5值是有序的二進制字符串，定義MD5之間的距離為

Hammin g(Mi，Mj)=∑kk=1(Mi，kMi，k) (4)

其中:表示異或操作。距離較近意味著兩幅圖像之間的Hamming距離小于某一閾值T。所以規定圖像的MD5值之間近似條件為

定義 Mi與Mj相似，當且僅當 ∑Lk=1(Mi，kMi，k)=0，并且

∑kk=L+1(Mi，kMi，k)≤T。

也就是說，要求前L bit具有相同的二進制值，而在其余的K-L bit中允許有小的誤差T。這一定義不僅可以使系統的查全率得到一定的提高，而且由于在尋找近似圖像過程中前Lbit要求是相同的，也給建立快速索引提供了方便。另外，近似圖像的檢測性能可以通過設置閾值T來調整。具體地，當T較小時，意味著圖像之間的匹配程度較高，從而準確率會上升，同時查全率就有可能下降;相反，當T較大時，意味著有較高的查全率，但是準確度可能會下降。因此，可以用來檢測近似或重復圖像。

2 近似圖像檢測實驗

2.1 數據集

獲取100個常用且無重復的圖像搜索查詢關鍵詞，分別將每一個關鍵詞提交到網絡搜索引擎Google的圖像檢索(http://images.google.cn)中，并下載其返回的前900幅圖像(每頁18幅圖像，前50頁)。去除部分無法下載的圖像，再對每幅下載的圖像進行處理，最終共得到了1 670 800幅圖像。其中每個查詢詞有16 708幅圖像。

考慮到數據集的大小，實驗中設定圖像分塊數目等參數分別為N=10，K=32，L=12，T=0.5。需要說明的是，近似圖像檢測都是在某一個查詢詞對應的結果集中進行;檢測實驗是在一臺Intel Xeon 3065服務器上進行的。

2.2 性能度量

由于近似圖像的檢測往往是在大規模數據集上進行，除了檢測有效性外，還需要有一定的實時處理要求。對算法的性能評估采用兩個準則，即效率(efficiency)和有效性(effectivity)，它們分別代表檢測速度和檢測近似圖像的成功率。檢測速度用時間來衡量，檢測的有效性用查全率(recall)和查準率(precision)[10]來評估。查全率也稱為召回率，查準率又稱做準確度，具體定義如下:

查全率=有關聯的正確檢索結果所有有關聯的結果×100%(5)

查準率=有關聯的正確檢索結果所有檢索到的結果×100%(6)

查準率是衡量檢測系統拒絕非相關信息的能力，查全率是衡量檢測系統檢出相關信息的能力。

2.3 實驗結果及分析

1)在檢測速度方面 算法的耗用時間極少，具體如圖4所示。當檢測范圍達到1萬張圖像時，所耗費的時間不超過0.1 s;而檢測范圍從5萬張增長到10萬張時，所耗費的間有了一個較快的增長，但是仍然沒有超過0.4 s。這說明當數據集增大時，算法尚需進一步地調整和改善。

2)在有效性方面 從表1可以看到，算法具有較高的查全率，平均查全率在94.19%以上;而檢測近似圖像也具有較高的準確性，平均查準率在86.10%以上。同時也可以看到，對于每一個查詢詞，檢測出的相關圖像越多，檢測到的正確結果呈現降低趨勢。

與相關近似圖像檢測算法的性能比較方面，選取文獻[4~7]提到的近似圖像檢測算法與本文算法在相同的測試環境下進行對比實驗。采用apple為檢索詞的數據集，共有圖像16 708張，其中近似圖像1 034張。通過表2可以看出，與文獻[4~7]算法相比，本文算法所用時間短，查全率、查準率高，這就表明采用灰度均值作為圖像特征以及使用MD5值檢索能夠提高系統的檢測速度。

可見，本文算法具有較高的效率和有效性。

3 結束語

本文主要討論了在大規模圖像集中快速進行近似或重復圖像檢測的方法。針對目前一些方法計算復雜度較高，難以應用到大規模數據集中的問題，提出一種基于MD5的近似圖像檢測算法。使用MD5值作為圖像內容的簡潔表達方式，每一幅圖像對應的特征在經過LE降維以及矢量量化后生成一組二進制字符串，成為該圖像的MD5值。利用該MD5值可以快速而準確地進行近似圖像的檢測。實驗結果表明，該算法計算復雜度低、準確度高，具有很好的性能。

由于圖像往往被表示為高維空間中的矢量，在現有的技術條件下對其索引和檢索都是較困難的，而且語義鴻溝問題同樣影響了圖像檢索結果。如何選取或提出更適合圖像的降維算法以及怎樣突破語義鴻溝，更加快速準確地檢測出近似圖像，將是今后研究的方向。

參考文獻:

[1] 溫泉徹，彭宏，黎瓊.基于內容的圖像檢索關鍵技術研究[J].微計算機信息，2007，23(3):278-280.

[2]向友君，謝勝利.圖像檢索技術綜述[J].重慶郵電學院學報:自然科學版，2006，18(3):348-354.

[3] 曹炬，馬杰，譚毅華.基于像素抽樣的快速互相關圖像匹配算法[J].宇航學報，2004，25(2):173-178.

[4] JAIMES A， CHANG S F， LOUI A C. Detection of non-identical duplicate consumer photographs[C]//Proc of the 4th IEEE Pacific Rim Conference on Multimedia. 2003:16-20.

[5]KE Yan，SUKTHANKAR R，HUSTON L.Efficient near-duplicate detection and sub-image retrieval[C]//Proc of the 12th Annual ACM International Conference on Multimedia. New York:ACM Press， 2004: 869-876.

[6]LIN Shu， OASU M T， ORIA V， et al. An extendible hash for multi-precision similarity querying of image databases[C]//Proc of the 27th International Conference on VLDB.2001: 221-230.

[7] ZHANG D ong-qing， CHANG S F. Detecting image near-duplicate by stochastic attributed relational graph matching with learning[C]// Proc of the 12th Annual ACM International Conference on Multimedia. New York:ACM Press， 2004: 877-884.

[8] BELKIN M， NIYOGI P. Laplacian eigenmaps and speetral techniques for embedding and clustering[C]//Proc of the 14th Advances in Neural Information Processing Systems.2001:585-591.

[9]魯坷，趙繼東，曾家智.一種適合Web圖像檢索的圖像降維算法研究

[J].計算機科學，2006，33(5):255-260.

[10]SMEULDERS A W M， SANTINI S， WORRING M， et al. Content based image retrieval at the end of the early years[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 2000， 22(12): 1349-1380.