基于哈希算法的圖像拷貝檢測(cè)＊

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

（1．華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 武漢 430074）（2．深圳報(bào)業(yè)集團(tuán)福田區(qū)深南大道6008號(hào)報(bào)業(yè)大廈 深圳 518009）

1 引言

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

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

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

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

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

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

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

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

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

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

1．2 最大熵模型（EM）

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

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

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

2 哈希算法

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

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

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

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

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

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

· 適用于信息檢索應(yīng)用。在投影前后保持?jǐn)?shù)據(jù)內(nèi)在的結(jié)構(gòu)信息，便于創(chuàng)建索引結(jié)構(gòu)。

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3．1 拷貝檢測(cè)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

為了確定哈希碼的長(zhǎng)度，我們利用F1-measure［7，9］指標(biāo)。F1-Measure是對(duì)準(zhǔn)確率和召回率的綜合評(píng)價(jià)指標(biāo)，表示在不同的漢明距離下，查全率和查準(zhǔn)率隨編碼長(zhǎng)度變化的趨勢(shì)。

其中r為recall，p為precision。

3．2 碼字長(zhǎng)度及漢明距離

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

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

圖3 F1-Measure隨編碼長(zhǎng)度和漢明距離的變化趨勢(shì)

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

表1 不同編碼長(zhǎng)度下的最優(yōu)檢測(cè)結(jié)果

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

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

通過(guò)分析可知，拷貝圖像與原始圖像的漢明距離較小，并且當(dāng)漢明距離等于零時(shí)，檢測(cè)出的拷貝圖像所占比例應(yīng)該是最多的；非拷貝圖像與原始圖像的漢明距離較大。

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

從圖4可知，當(dāng)漢明距離等于0時(shí)，拷貝圖像的個(gè)數(shù)比例最高；隨著漢明距離的變大，拷貝圖像的個(gè)數(shù)所占的比例逐漸變小。當(dāng)漢明距離等于20時(shí)，非拷貝圖像所占的比例達(dá)到峰值。使得虛警率和漏警率組成的面積最小的漢明距離即為最優(yōu)的漢明距離。可以看出，當(dāng)漢明距離為10時(shí)，可以得到較高的查全率和查準(zhǔn)率。

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

4 結(jié)語(yǔ)

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

［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．