張榮華，柳忠彬，廖紅華，楊大志

(1.四川理工學(xué)院 機(jī)械工程學(xué)院，四川 自貢 643000；2.湖北民族學(xué)院 信息工程學(xué)院，湖北 恩施 445000)

基于角點(diǎn)檢測和NMF的圖像Hash算法

張榮華1，柳忠彬1，廖紅華2，楊大志1

(1.四川理工學(xué)院 機(jī)械工程學(xué)院，四川 自貢 643000；2.湖北民族學(xué)院 信息工程學(xué)院，湖北 恩施 445000)

為了有效地實(shí)現(xiàn)圖像Hash函數(shù)在圖像認(rèn)證檢索中的應(yīng)用，提出了結(jié)合Harris角點(diǎn)檢測和非負(fù)矩陣分解(NMF)的圖像Hash算法，首先提取圖像中的角點(diǎn)，對角點(diǎn)周圍圖像塊信息進(jìn)行非負(fù)矩陣分解得到表征圖像局部特征的系數(shù)矩陣，進(jìn)一步量化編碼產(chǎn)生圖像Hash。實(shí)驗(yàn)結(jié)果表明，得到的圖像Hash對視覺可接受的操作如圖像縮放、高斯低通濾波和JPEG壓縮具有良好的穩(wěn)健性，同時能區(qū)分出對圖像大幅度擾動或修改的操作。

圖像認(rèn)證檢索；Harris角點(diǎn)檢測；非負(fù)矩陣分解(NMF)；圖像Hash

鑒于數(shù)字媒體傳播的廣泛性和交互性，對其內(nèi)容的防偽、篡改、完整性認(rèn)證等問題越來越引起用戶的關(guān)注，尤其是數(shù)字圖像已成為最重要的媒體信息之一，如何有效地實(shí)現(xiàn)圖像的管理、認(rèn)證及檢索已成為亟待解決的問題。針對這一現(xiàn)象，本文研究穩(wěn)健圖像摘要[1]或哈希(Hash)算法，即通過分析提取圖像的顏色、形狀、紋理、空間關(guān)系等特征并進(jìn)一步編碼，用一個較短的固定長度的數(shù)字序列標(biāo)識該圖像。圖像摘要在完整性認(rèn)證、圖像檢索、數(shù)字水印等方面有廣泛的應(yīng)用前景。

目前，圖像Hash算法大致可分為4大類[2]?；诳臻g統(tǒng)計特性[3-4]，文獻(xiàn)[4]中先對圖像進(jìn)行小波分解，接著把每個頻帶隨機(jī)分塊，對每個塊統(tǒng)計量化構(gòu)造哈希序列，該算法對JPEG壓縮、幾何失真有較好的穩(wěn)健性；基于變換域系數(shù)相關(guān)性，Lefebvre[5]等用Radon變換構(gòu)造圖像Hash，該方法對基本圖像攻擊如壓縮、濾波、模糊等穩(wěn)定性較好；基于粗略特征描述，F(xiàn)ridrich[6]等指出圖像在發(fā)生顯著變化后，其DCT低頻系數(shù)也會改變，由此提出將圖像DCT系數(shù)矩陣投影到隨機(jī)平滑模板上，計算每塊投影的內(nèi)積，并將其量化映射成固定長度的數(shù)字序列，進(jìn)而得到圖像哈希，該摘要算法對一般圖像攻擊有較好的魯棒性，但對幾何變換效果不佳；基于視覺特性，在計算圖像Hash時引入人眼視覺特性(Human Visual System，HVS)[7-8]，使圖像Hash能更好地反映圖像視覺特征，文獻(xiàn)[8]中增大人眼敏感的頻域系數(shù)在計算圖像Hash時的權(quán)重，首先將原始圖像的分塊DCT系數(shù)乘以由密鑰控制生成的偽隨機(jī)矩陣，接著進(jìn)行基于分塊的Watson人眼視覺特性處理，最后進(jìn)行量化以產(chǎn)生圖像Hash，該算法提高了對JPEG壓縮和高斯濾波的魯棒性。近年來，也出現(xiàn)了融合多種圖像特征提取方法來構(gòu)建圖像Hash的方法，文獻(xiàn)[9]中提出了結(jié)合尺度不變特征變換(SIFT)和主成分分析(PCA)的感知哈希方法，對圖像旋轉(zhuǎn)、光照變化、圖像濾波等攻擊具有一定的穩(wěn)健性。

基于以上分析，提出一種采用Harris角點(diǎn)檢測結(jié)合非負(fù)矩陣分解，提取特征點(diǎn)周圍圖像信息的摘要算法。該方法考慮到圖像中邊緣、角點(diǎn)、斑點(diǎn)、直線段、圓等基元包含了圖像的特征信息，而其中圖像角點(diǎn)的局部具有較好的穩(wěn)健性，實(shí)驗(yàn)結(jié)果表明，該方法具有較好的視覺穩(wěn)定性和區(qū)分內(nèi)容不同圖像的能力。

1 Harris角點(diǎn)檢測原理

角點(diǎn)是兩個邊緣的連接點(diǎn)，圖像梯度有很大的變化，Harris角點(diǎn)檢測[10]使用特征點(diǎn)來描述圖像的內(nèi)容。設(shè)計一個局部窗口(高斯函數(shù))沿圖像各方向移動，窗口的平均能量會發(fā)生明顯改變，即圖像局部曲率突變，當(dāng)能量改變值大于設(shè)定的閾值時，則選取該窗口的中心像素點(diǎn)為角點(diǎn)。

(1)

為了尋找包含角點(diǎn)的窗口，則需要找出像素灰度變化較大的窗口，即

max[I(x+u,y+v)-I(x,y)]2

(2)

使用泰勒展開得

(3)

式中：Ix,Iy表示圖像一階灰度梯度。

2 非負(fù)矩陣分解

非負(fù)矩陣分解(Nonnegative Matrix Factorization，NMF)[11]，是當(dāng)矩陣中全部元素均為非負(fù)數(shù)時的一種矩陣分解方法，適合圖像的非負(fù)性質(zhì)，有助于處理大規(guī)模數(shù)據(jù)，占用存儲空間少，矩陣分解得到的低秩可大大降低矩陣維數(shù)。

對于非負(fù)矩陣V，存在W≥0,U≥0，滿足：Vn×m≈Wn×r·Ur×m，其中r為特征維數(shù)，nm>(n+m)r，即將一個非負(fù)的矩陣分解為兩個非負(fù)矩陣相乘，W稱為基矩陣，U稱為系數(shù)(權(quán)重)矩陣，這種基于基向量組合的表示形式反映了人類思維中“局部構(gòu)成整體”的概念。

定義目標(biāo)函數(shù)來描述V≈WU的近似效果，用分解前后兩個非負(fù)矩陣V和WU之間的距離來度量。第一種方法為歐氏距離，即

(4)

第二種方法是利用V與WU間的廣義K-L散度，即

(5)

由此，NMF的問題就轉(zhuǎn)化為使目標(biāo)函數(shù)最小化的優(yōu)化問題，可以通過迭代運(yùn)算求解，為保證非負(fù)矩陣分解結(jié)果的非負(fù)性，采用文獻(xiàn)[12]提出的K-L散度下迭代法則

(6)

(7)

隨機(jī)初始化W和U，通過50～100次迭代運(yùn)算得到分解結(jié)果。

3 圖像Hash算法

密碼學(xué)中代表性的Hash算法有MD5和SHA-1，目的是找到數(shù)據(jù)內(nèi)容和存放地址之間的映射關(guān)系，其對輸入數(shù)據(jù)的變化很敏感，這樣的摘要算法并不適用于圖像。因?yàn)樵趯?shí)際應(yīng)用中常需要對圖像進(jìn)行如濾波、壓縮、增強(qiáng)、加噪、縮放等多種操作，并未改變圖像特征，此時哈希序列應(yīng)保持不變。另一方面，如果圖像內(nèi)容被大幅度修改后，應(yīng)使哈希序列完全改變，才能實(shí)現(xiàn)防偽認(rèn)證的目的。設(shè)圖像為I，H(I)為哈希函數(shù)，h=H(I)即為提取對象I得到的Hash值，由此圖像Hash應(yīng)具備以下特點(diǎn)：

3.1 Hash提取

Hash提取算法的流程圖如圖1所示。

圖1 Hash提取流程圖

具體步驟描述如下：

1)預(yù)處理：Harris角點(diǎn)檢測算法對圖像的縮放敏感，因此，采用雙三次插值將輸入圖像規(guī)格化到統(tǒng)一大小512×512，減少圖像縮放操作對Harris角點(diǎn)位置的影響。

2)對圖像進(jìn)行Harris角點(diǎn)檢測。

3)Harris角點(diǎn)檢測得到的是像素點(diǎn)，以該點(diǎn)為中心，設(shè)定g×g大小的窗口，對邊緣點(diǎn)窗口大小可能不足g×g，再次雙三次插值規(guī)格化為g×g窗口大小。

4)對包含角點(diǎn)的窗口圖像塊信息，進(jìn)行非負(fù)矩陣分解。

5)生成特征向量：經(jīng)過NMF后得到系數(shù)(權(quán)重)矩陣Ur×g，它表征了圖像的局部特征，對U矩陣計算每一列均值x(i)， 并把每一個元素與均值進(jìn)行比較，得到矩陣Cr×g，其中

(8)

(9)

6)生成Hash序列：將g個特征向量轉(zhuǎn)化為二進(jìn)制序列，生成圖像Hash序列。

3.2 相似性度量

采用歸一化Hamming(漢明)距離表征圖像的相似程度，即

(10)

式中：L為Hash序列的長度；H(I1)，H(I2)分別為圖像I1，I2提取的哈希序列。

歸一化Hamming距離具有以下特性：圖像內(nèi)容之間越相似，歸一化Hamming距離越趨近于0；當(dāng)圖像之間不相似的程度逐漸增大時，歸一化Hamming距離也隨之增大；當(dāng)感知兩個內(nèi)容不相關(guān)的圖像時，歸一化Hamming距離的期望值越趨向于0.5。

4 實(shí)驗(yàn)結(jié)果

4.1 魯棒性分析

采用常見的視覺可接受的保持圖像內(nèi)容不變的操作來測試圖像Hash算法的魯棒性。選取大小為512×512的標(biāo)準(zhǔn)圖像Lena，Boat，Tank，Airplane和House進(jìn)行實(shí)驗(yàn)，分別對其進(jìn)行縮放變換，高斯低通濾波和JPEG壓縮處理，計算操作前后圖像哈希間的Hamming距離，結(jié)果如圖2～4所示。圖中縱坐標(biāo)為原標(biāo)準(zhǔn)圖像與受攻擊后圖像的歸一化Hamming距離，橫坐標(biāo)分別表示縮放比例，高斯濾波3×3掩模的標(biāo)準(zhǔn)差σ，JPEG壓縮質(zhì)量因子。圖2說明了哈希序列受圖像縮放變換影響的情況，當(dāng)縮放比例小于1時，圖像質(zhì)量下降，此時Hamming距離有較為明顯的增大趨勢，而縮放比例大于1時，則對哈希序列的影響較??；圖3表明隨著標(biāo)準(zhǔn)差σ增大，Hamming距離也相應(yīng)增大；圖4表明隨著JPEG壓縮質(zhì)量因子增大，Hamming距離下降。從圖2～圖4可以看出，該圖像Hash方法對適度的圖像縮放、高斯低通濾波、JPEG壓縮具有魯棒性。

圖2 圖像縮放

圖3 高斯低通濾波

圖4 JPEG壓縮

4.2 區(qū)分性分析

根據(jù)圖像Hash的區(qū)分性(抗碰撞性)條件，圖像Hash算法除需對保持圖像內(nèi)容不變的操作具有良好的魯棒性外，還需能夠區(qū)分兩幅內(nèi)容不同或者被惡意篡改過的圖像，即此時哈希序列值也應(yīng)有較大差別。選取大小為512×512的標(biāo)準(zhǔn)圖像Lena，Boat，Tank，Airplane，House，Pepper和Splash進(jìn)行實(shí)驗(yàn)，如表1所示，不同圖像間的漢明距離均較大，各標(biāo)準(zhǔn)測試圖像間歸一化漢明距離最大為0.827 3，最小為0.292 8，說明該哈希算法足以區(qū)分不同圖像，滿足抗碰撞性，對圖像大幅度擾動等攻擊敏感。

表1 標(biāo)準(zhǔn)測試圖像間的歸一化Hamming距離

測試圖像LenaBoatTankAirplaneHousePepperSplashLena0036610513704099047620453006798Boat0366100407802982036290562107550Tank0513704078003595029280678208273Airplane0409902982035950032140594807801House0476203629029280321400651108118Pepper0453005621067820594806511005095Splash0679807550082730780108118050950

4.3 性能對比

為了測試算法的分類性能，從華盛頓大學(xué)的CBIR圖像庫選取100幅圖像，分別對其進(jìn)行縮放變換，高斯低通濾波和JPEG壓縮處理，即每一幅圖都生成相似圖像，采用接收者操作特征曲線(Receiver Operating Characteristic Curve，ROC)，與文獻(xiàn)[13]基于NMF哈希方法對比，測試算法的分類性能，為此計算兩種方法的真正率TPR和假正率FPR

TPR=TP/(TP+FN)

(11)

FPR=FP/(FP+TN)

(12)

式中：TP(真正)表示被預(yù)測為相同圖像的相似樣本；FN(假負(fù))表示被預(yù)測為不同圖像的相似樣本，則把所有實(shí)際為相似圖像的樣本，正確地判斷為相似圖像的比率稱為TPR；FP(假正)表示被預(yù)測為相似圖像的不同樣本；TN(真負(fù))表示被預(yù)測為不同圖像的不同樣本，則把所有實(shí)際為不同圖像的樣本，錯誤地判斷為相似圖像的比率稱為FPR。ROC曲線從全局上反映算法的魯棒性和區(qū)分性，越靠近左上角的曲線算法性能越好。從圖5可以看出，基于角點(diǎn)檢測和NMF的圖像哈希算法優(yōu)于文獻(xiàn)[13]。

圖5 本文哈希算法與文獻(xiàn)[13]算法ROC曲線

5 小結(jié)

提出了一種穩(wěn)健圖像Hash算法。從圖像中提取的Harris角點(diǎn)對于視覺可接受的操作具有良好的抗干擾性，對以角點(diǎn)為中心g×g大小的窗口，應(yīng)用非負(fù)矩陣分解實(shí)現(xiàn)數(shù)據(jù)壓縮降維，而且圖像的主要內(nèi)容特征能通過系數(shù)矩陣提取出來，進(jìn)一步對系數(shù)矩陣進(jìn)行量化編碼實(shí)現(xiàn)了圖像與一個二進(jìn)制序列的映射。實(shí)驗(yàn)結(jié)果表明，該算法具有抵御圖像縮放、高斯低通濾波、JPEG壓縮攻擊的穩(wěn)健性，能區(qū)分不同圖像，具有對圖像惡意擾動或篡改等攻擊的敏感性。進(jìn)一步的研究將提取圖像中對視覺特性更穩(wěn)健的特征點(diǎn)，引入密鑰，以進(jìn)一步提高Hash性能。

[1] 牛夏牧，焦玉華.感知哈希綜述[J]. 電子學(xué)報，2008，36(7)：1405-1411.

[2] 葉衛(wèi)國，韓水華.基于內(nèi)容的圖像Hash算法及其性能評估[J].東南大學(xué)學(xué)報：自然科學(xué)版，2007，37(Z1)： 109-113.

[3] 王瑋.基于小波域?yàn)V波的迭代硬閾值壓縮感知重構(gòu)[J].電視技術(shù)，2014，38(9)：32-35.

[4] VENKATESAN R， KOON S M， JAKUBOWSKI M H，et al. Robust image hashing[C]//Proc. IEEE International Conference on Image Processing.Vancouver BC，Canada：IEEE Press，2000：664-666.

[5] LEFEBVRE F，MACQ B，LEGAT J D. RASH：Radon soft hash algorithm[C]//Proc. European Signal Processing Conference. Toulouse，F(xiàn)rance：IEEE Press，2002：299-302.

[6] FRIDRICH J， GOLJAN M. Robust hash functions for digital watermarking[C]//Proc. IEEE International Conference on Information Technology：Coding and Computing. LasVegas，Nevada，USA：IEEE Press，2000：178-183.

[7] 張慧， 張海濱，李瓊，等.基于人類視覺系統(tǒng)的圖像感知哈希算法[J]. 電子學(xué)報，2008，36(12A)：30-34.

[8] 秦川，王朔中，張新鵬.一種基于視覺特性的圖像摘要算法[J].中國圖象圖形學(xué)報，2006，11(11)：1678-1681.

[9] 孫銳，閆曉星，高雋.基于SIFT和PCA的圖像感知哈希方法[J]. 電路與系統(tǒng)學(xué)報，2013，18(1)：274-278.

[10] HARRIS C，STEPHENS M. A combined corner and edge detector[C]//Proc. Alvey Vision Conference.[S.l.]：IEEE Press，1988：147-151.

[11] LEE D D，SEUNG H S. Learning the parts of objects by nonnegative matrix factorization[J]. Nature，1999(21)：788-791.

[12] LEE D D，SEUNG H S. Algorithms for non-negative matrix factorization[C]//Proc. Advances in Neural Information Processing Systems.[S.l.]：IEEE Press，2001：556-562.

[13] MONGA V，MIH?AK M K. Robust and secure image hashing via non-negative matrix factorizations[J].IEEE Trans. Information Forensics and Security，2007，2(3)：376-390.

張榮華(1987— )，女，碩士，研究方向?yàn)閳D像處理、機(jī)器視覺；

柳忠彬(1972— )，教授，碩士生導(dǎo)師，研究方向?yàn)闄C(jī)械設(shè)計、逆向工程、仿真分析；

廖紅華(1972— )，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)閳D像處理、嵌入式系統(tǒng)；

楊大志(1976— )，副教授，研究方向?yàn)榍度胧较到y(tǒng)、信息獲取及處理。

責(zé)任編輯：時 雯

Image Hashing Based on Harris Corners and NMF

ZHANG Ronghua1，LIU Zhongbin1，LIAO Honghua2，YANG Dazhi1

(1.SchoolofMechanicalEngineering，SichuanUniversityofScience&Engineering，SichuanZigong643000，China； 2.SchoolofInformationEngineering，HubeiUniversityforNationalities，HubeiEnshi445000，China)

In order to apply the image Hash in image authentication and retrieval effectively，a new image Hashing algorithm based on Harris corners and nonnegative matrix factorization (NMF) is proposed，firstly Harris corners are identified，around the Harris corners of image block information runs NMF to obtain the coefficient matrix that capture the local features of image. Then，these features are quantized and coded to generate the Hash vector. Test results indicate that the proposed method is robust against acceptable visual image scaling， Gaussian low-pass filtering and JPEG compression，at the same time is sensitive to image excessive changes or malicious tampering.

image authentication and retrieval；Harris corners detection；nonnegative matrix factorization(NMF)； image Hash

國家自然科學(xué)基金項(xiàng)目(61263030)

TN911.73

A

10.16280/j.videoe.2015.17.008

2015-01-15

【本文獻(xiàn)信息】張榮華，柳忠彬，廖紅華，等.基于角點(diǎn)檢測和NMF的圖像Hash算法[J].電視技術(shù),2015，39(17).