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

馬慶貞 王云飛 曾宇鵬 鄭創(chuàng)偉 陳宇輝 謝志成

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

1 引言

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

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

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

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

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

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

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

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

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

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

1．2 最大熵模型（EM）

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

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

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

2 哈希算法

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

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

2．1 局部保持投影優(yōu)化

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

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

該降維算法具有如下優(yōu)點：

· 適用于信息檢索應用。在投影前后保持數(shù)據(jù)內(nèi)在的結構信息，便于創(chuàng)建索引結構。

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

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

圖2 不同參數(shù)下的PR 曲線

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

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

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

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

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

3 實驗結果及分析

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

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

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

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

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

其中r為recall，p為precision。

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

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

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

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

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

表1 不同編碼長度下的最優(yōu)檢測結果

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

其中，F(xiàn)P為誤檢的圖像數(shù)目，TP為正確檢測出的圖像數(shù)目，F(xiàn)N為漏檢的圖像數(shù)目。

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

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

從圖4可知，當漢明距離等于0時，拷貝圖像的個數(shù)比例最高；隨著漢明距離的變大，拷貝圖像的個數(shù)所占的比例逐漸變小。當漢明距離等于20時，非拷貝圖像所占的比例達到峰值。使得虛警率和漏警率組成的面積最小的漢明距離即為最優(yōu)的漢明距離?？梢钥闯觯敐h明距離為10時，可以得到較高的查全率和查準率。

圖4 漢明距離優(yōu)化

4 結語

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

［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(xiàn)．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，F(xiàn)linders 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．