基于角點檢測和NMF的圖像Hash算法

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

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

基于角點檢測和NMF的圖像Hash算法

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

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

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

圖像認證檢索；Harris角點檢測；非負矩陣分解(NMF)；圖像Hash

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

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

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

1 Harris角點檢測原理

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

(1)

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

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

(2)

使用泰勒展開得

(3)

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

2 非負矩陣分解

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

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

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

(4)

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

(5)

由此，NMF的問題就轉化為使目標函數最小化的優化問題，可以通過迭代運算求解，為保證非負矩陣分解結果的非負性，采用文獻[12]提出的K-L散度下迭代法則

(6)

(7)

隨機初始化W和U，通過50～100次迭代運算得到分解結果。

3 圖像Hash算法

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

3.1 Hash提取

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

圖1 Hash提取流程圖

具體步驟描述如下：

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

2)對圖像進行Harris角點檢測。

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

4)對包含角點的窗口圖像塊信息，進行非負矩陣分解。

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

(8)

(9)

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

3.2 相似性度量

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

(10)

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

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

4 實驗結果

4.1 魯棒性分析

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

圖2 圖像縮放

圖3 高斯低通濾波

圖4 JPEG壓縮

4.2 區分性分析

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

表1 標準測試圖像間的歸一化Hamming距離

測試圖像LenaBoatTankAirplaneHousePepperSplashLena0036610513704099047620453006798Boat0366100407802982036290562107550Tank0513704078003595029280678208273Airplane0409902982035950032140594807801House0476203629029280321400651108118Pepper0453005621067820594806511005095Splash0679807550082730780108118050950

4.3 性能對比

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

TPR=TP/(TP+FN)

(11)

FPR=FP/(FP+TN)

(12)

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

圖5 本文哈希算法與文獻[13]算法ROC曲線

5 小結

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

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

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

[3] 王瑋.基于小波域濾波的迭代硬閾值壓縮感知重構[J].電視技術，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，France：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] 張慧， 張海濱，李瓊，等.基于人類視覺系統的圖像感知哈希算法[J]. 電子學報，2008，36(12A)：30-34.

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

[9] 孫銳，閆曉星，高雋.基于SIFT和PCA的圖像感知哈希方法[J]. 電路與系統學報，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— )，女，碩士，研究方向為圖像處理、機器視覺；

柳忠彬(1972— )，教授，碩士生導師，研究方向為機械設計、逆向工程、仿真分析；

廖紅華(1972— )，博士，副教授，碩士生導師，研究方向為圖像處理、嵌入式系統；

楊大志(1976— )，副教授，研究方向為嵌入式系統、信息獲取及處理。

責任編輯：時 雯

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

國家自然科學基金項目(61263030)

TN911.73

A

10.16280/j.videoe.2015.17.008

2015-01-15

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