基于哈希算法的圖像拷貝檢測＊

馬慶貞 王云飛 曾宇鵬 鄭創偉 陳宇輝 謝志成

（1．華中科技大學計算機科學與技術學院 武漢 430074）（2．深圳報業集團福田區深南大道6008號報業大廈 深圳 518009）

1 引言

多媒體數據的快速傳播和共享使得媒體數據的版權保護成為當前亟待解決的問題。拷貝檢測技術是版權保護的一種有效手段。目前廣泛使用的拷貝檢測技術主要有數字水印和基于內容拷貝檢測兩大類方法。

數字水印有以下缺點：對未嵌入水印的作品無法進行拷貝檢測；受到攻擊的水印不能有效地用于拷貝檢測和版權認證。對多媒體作品進行攻擊的重要前提是不能影響其商業價值，也就是作品的內容不能有很多的變化，這使得基于內容的拷貝檢測成為了最有應用前景的版權保護技術之一。本文主要研究基于哈希算法的圖像拷貝檢測。

在圖像拷貝檢測中，圖像特征一般維度較高，并且大多圖像庫擁有海量數據，使得現有的拷貝檢測技術性能低下。鑒于上訴分析，本文提出了：1）基于局部保持投影的降維算法的優化，將高維特征映射到低維空間中，在解決維度災問題同時避免了過擬合；2）基于最大熵模型的二值化處理；3）最優的哈希碼的長度和漢明距離選擇策略。

1．1 局部保持投影（LPP）

局部保持投影（LPP）［1，10］用譜圖理論［2］來 闡述，其基本思想是用譜圖G＝（V，E）模擬空間中樣本點的局部幾何結構，在一定程度上保持了數據集中樣本間的內在局部位置結構。

給定子流型結構中的m個樣本點組成的數據集X＝｛x1，x2，…，xm｜xi∈Rn｝，尋找變換矩陣A將其映射到低維空間Y＝｛y1，y2，…，ym｜yi∈Rl｝。保持局部幾何結構的最佳映射的優化準則為

其中wij表示xi和xj間的邊權重。通過簡單的代數變換，式（1）可以轉化為

其中拉普拉斯矩陣L＝D-W，D為對角矩陣，Dii＝∑jwij，Tr（．）表示矩陣的跡。限定條件：

式（2）在約束條件下的最優問題轉化為廣義特征值分解：

按升序排列特征值λ0≤λ1≤…≤λl-1，對應的特向量組成最優投影矩陣A＝（a0，a1，…，al-1）。

1．2 最大熵模型（EM）

最大熵理論［3～4，8］指出當根據不完整的信息推斷最吻合樣本數據分布的解時，應該由滿足分布限制條件的具有最大熵的概率分布推得。對于訓練數據集D＝｛（x1，y1），…，（xn，yn）｝，隨機事件的不確定性可用條件熵來衡量：

使得熵最大的概率分布p必須受到特征函數的限制，其一般形式為

最大熵模型有其他模型無法比擬的優點［5，11］：首先，最大熵統計模型獲得滿足約束條件的信息熵極大的模型；其次，最大熵統計模型可靈活地設置約束條件，通過約束條件調節模型對未知數據的適應度和對已知數據的擬合度；最大熵模型解決了統計模型中參數平滑問題。

2 哈希算法

基于哈希算法的圖像拷貝檢測的流程如圖1所示。先從原始圖像庫提取全局特征并進行降維處理；然后將特征序列轉換為哈希碼；最后為特征序列建立索引。對于查詢圖像，根據相同的方法用哈希碼表示圖像，然后在索引中查詢相似的特征序列，并返回查詢結果。其關鍵技術有高維向量降維的優化、二進制向量編碼及檢索。

圖1 基于哈希算法的圖像拷貝檢測流程圖

2．1 局部保持投影優化

在拷貝檢測中，先在訓練集得到LPP 的映射矩陣，然后利用映射矩陣將新樣本映射到低維空間。由于此映射矩陣可能產生過擬合，在原有LPP算法的基礎上加入正則化：

利用廣義特征值分解可求解式（7）。通過調節參數α可得到很好描述新數據集的特征映射矩陣。圖2為α取不同值的PR 曲線，從圖中可知，當α＝-1000時，系統有較好的查詢性能，表明我們得到的投影矩陣有較好的泛化能力。

該降維算法具有如下優點：

· 適用于信息檢索應用。在投影前后保持數據內在的結構信息，便于創建索引結構。

· 拉普拉斯特征映射的線性逼近（LE）［6］，相比非線性的降維技術計算速度更快。

· 在LPP的基礎上加入正則化，可防止產生過擬合。

圖2 不同參數下的PR 曲線

2．2 基于EM 的二值化處理

二值化處理將低維特征映射至海明空間，生成便于計算和存儲的二進制哈希碼。相鄰的特征能夠被映射為相似的哈希碼。下面介紹如何將低維空間特征轉化為二進制哈希碼。

給定N維特征向量x＝（x1，x2，…，xN），計算特征向量的均值然后將特征向量的每一維與均值進行比較：

經過上述處理，低維空間的特征被轉換為二進制哈希碼。在海明空間內進行檢索時一般采用遍歷方法展開近鄰搜索，查找查詢半徑以內的所有碼字，然后返回對應容器中的對象。

這種處理的最大優勢在于：數據間的海明距離可通過計算機硬件的“異或”操作實現，計算千萬數量級數據的海明距離所需的時間只在毫秒級。此外，低維的哈希碼大大降低了存儲開銷，千萬級數據所對應的索引信息可全部載入內存，保證了檢索算法的高效性。

3 實驗結果及分析

3．1 拷貝檢測質量評價標準

對于圖像拷貝檢測，我們感興趣的是檢測到的對象數量和檢測錯誤的概率，因此用P-R 曲線作為檢測質量的評價指標。P-R 曲線［7］以查準率為縱坐標，查全率為橫坐標繪制。查準率反映檢索系統拒絕非相關信息的能力，用公式表示為

查全率反映的是檢索系統和檢索者檢出相關信息的能力，用公式表示為

其中C為圖像庫中拷貝圖像集合，Cq表示被認為是拷貝圖像集合，‖‖代表集合中元素個數。

為了確定哈希碼的長度，我們利用F1-measure［7，9］指標。F1-Measure是對準確率和召回率的綜合評價指標，表示在不同的漢明距離下，查全率和查準率隨編碼長度變化的趨勢。

其中r為recall，p為precision。

3．2 碼字長度及漢明距離

對于一幅圖像，我們最終將其特征轉化為二進制哈希碼。哈希碼的長度L是第一步要確定的問題。當L太小時，不同的特征序列會轉換成相似的01序列，使得系統的查全率和查準率較小；而當L太長時，雖然能獲得較好的性能，但構建索引需較大的內存。

我們從1～195改變編碼長度，漢明距離從0～3。圖3為F1-Measure在隨編碼長度變化而呈現的變化趨勢。從圖中可知，隨著漢明距離的變大，F1-Measure的峰值會變大；并且在達到峰值之前，F1-Measure逐漸變大，隨后逐漸變小。

圖3 F1-Measure隨編碼長度和漢明距離的變化趨勢

下面在不同的編碼長度下測試的最佳查全率和查準率。各PR 曲線的最優檢測結果如表1所示。綜合查詢性能與空間復雜度，將編碼長度設置為40，此編碼長度可以使系統具有較好的查詢性能并且具有較低的空間復雜度。

表1 不同編碼長度下的最優檢測結果

下面通過虛警率和漏警率來測試在編碼長度為40的情況下，如何選擇漢明距離使得系統具有較高的查全率和查準率。虛警率是指誤檢的圖像個數與檢測出的圖像數目的比例；漏警率是指沒有檢測出的拷貝數目與全部拷貝數目的比例。其公式如下：

其中，FP為誤檢的圖像數目，TP為正確檢測出的圖像數目，FN為漏檢的圖像數目。

通過分析可知，拷貝圖像與原始圖像的漢明距離較小，并且當漢明距離等于零時，檢測出的拷貝圖像所占比例應該是最多的；非拷貝圖像與原始圖像的漢明距離較大。

我們用2W 的測試數據集，包括1W 幅拷貝和1W 幅非拷貝圖像。其中的1W 幅拷貝是通過對原始圖像進行stirkmark攻擊后得到的。我們計算原始圖像的特征序列與拷貝圖像和非拷貝圖像特征序列間的漢明距離，然后統計各漢明距離中圖像個數占全部圖像數目的比例。

從圖4可知，當漢明距離等于0時，拷貝圖像的個數比例最高；隨著漢明距離的變大，拷貝圖像的個數所占的比例逐漸變小。當漢明距離等于20時，非拷貝圖像所占的比例達到峰值。使得虛警率和漏警率組成的面積最小的漢明距離即為最優的漢明距離。可以看出，當漢明距離為10時，可以得到較高的查全率和查準率。

圖4 漢明距離優化

4 結語

本文介紹了LPP 的優化算法，實現了將高維特征線性映射到低維空間，同時保持數據的局部內部結構。最后，對得到的低維特征進行二值化處理，得到特征的哈希碼。為了平衡查詢性能和查詢效率，我們通過實驗選擇最優哈希碼長度，并在此基礎上確定漢明距離。

［1］He，Xiaofei，Partha Niyogi．Locality preserving projections［C］／／NIPS，2003，16：234-241．

［2］Cvetkovic，D．M．，et al．Recent results in the theory of graph spectra［J］．North Holland，1988，36：193-211．

［3］Smadja，F．Retrieving collocations from text：Xtract［J］．Computational linguistics，1993，19（1）：143-177．

［4］Church，K．W．，P．Hanks．Word association norms，mutual information，and lexicography［J］．Computational linguistics，1990，16（1）：22-29．

［5］Berger，A．L．，Pietra，V．J．D．，Pietra，S．A．D．A maximum entropy approach to natural language processing［J］．Computational linguistics，1996，22（1）：39-71．

［6］Belkin，M．，P．Niyogi．Laplacian eigenmaps and spectral techniques for embedding and clustering［J］．Advances in neural information processing systems，2001，14：585-591．

［7］Powers，D．M．Evaluation：From precision，recall and f-factor to roc，informedness，markedness ＆correlation［J］．School of Informatics and Engineering，Flinders University，Adelaide，Australia，2007，Tech．Rep．SIE-07-001．

［8］S．Baluja，M．Covell．Learning to hash：forgivinghash functions and applications［C］／／Data Mining and Knowledge Discovery，2008，17（3）：402-430．

［9］C．D．Manning，P．Raghavan，H．Sch¨utze．Introduction to information retrieval［M］．volume 1．London：Cambridge University Press，2008．

［10］Zhang，L．，Qiao，L．，Chen，S．Graph-optimized locality preserving projections［C］／／Pattern Recognition，2010，43（6）：1993-2002．

［11］Ratnaparkhi，Adwait．Maximum entropy models for natural language ambiguity resolution［D］．Pennsylvania：University of Pennsylvania，1998．