基于向量點積與相似聚類的圖像偽造檢測算法

劉琴琴，邱建林

(1.南通理工學院 計算機與信息工程學院，江蘇 南通 226000；2.南通大學 計算機學院，江蘇 南通 226000)

0 引 言

被篡改的數字圖像[1-3]會給人們帶來不可估量的后果，例如：在新聞傳播中，偽造的數字圖像將會把虛假的信息傳遞給人們、在目標跟蹤中，偽造的數字圖像將會使得跟蹤目標發生錯誤等[4,5]。因此，為了對偽造圖像中的篡改內容進行檢測，學者們提出了相應的圖像偽造檢測技術。

目前，數字圖像偽造檢測技術多種多樣，例如Pooja[6]提出了基于SIFT的復制-粘貼數字圖像偽造檢測算法，實驗結果驗證了其算法的有效性。又如李曉飛等[7]提出了基于SIFT的偽造圖像盲檢測算法，利用SIFT方法提取圖像特征，然后利用最近鄰搜索方法完成圖像匹配，最后利用歐氏距離對可疑塊進行判定完成圖像偽造檢測。然而，由于SIFT方法提取的特征點中存在較多的冗余點以及錯誤特征點，導致算法對偽造圖像的檢測正確度不高，而且檢測效率也不理想。對此，焦麗鑫等[8]提出了基于均值漂移的圖像復制粘貼偽造盲檢測，利用SURF對特征點進行提取，然后利用最近鄰匹配方法消除冗余點進行特征匹配，最后利用均值漂移方法進一步細化偽造檢測結果，但SURF算法中生成的特征描述子維度較高，導致算法效率不佳。又如楊仁青等[9]提出了基于分數傅里葉變換的數字圖像復制-粘貼篡改檢測算法，首先利用一級小波變換對圖像進行降維，然后對圖像進行分塊，最后通過求取相鄰塊之間的特征矢量差完成圖像的偽造檢測，但是該方法對經過旋轉等復雜篡改方法處理后的偽造圖像進行檢測時，檢測效果不理想。

對此，本文提出了基于向量點積耦合相似聚類的圖像偽造檢測算法的研究。利用Forstner算子來快速提取圖像特征。通過構建圓形區域與角度盤，求取梯度累計直方圖，從而改進了SURF機制，獲取特征描述符。利用特征描述符構成的向量點積，構造向量點積雙閥值匹配模型，對特征點進行匹配。采用歸一化互相關函數對匹配特征點進行相似性測量，完成特征點的聚類。最后，測試了所提技術的偽造檢測精度。

1 本文圖像偽造檢測算法設計

本文設計的圖像偽造檢測算法過程如圖1所示，主要由4部分組成：圖像特征點檢測、獲取特征點對應的特征描述符、特征點匹配、特征點的聚類。

圖1 本文圖像偽造檢測算法過程

1.1 圖像特征點的檢測

為了精確、快速獲取圖像的特征點，通過專家學者的研究涌現出了較多優秀的特征點檢測方法，例如：SIFT算子、Harris算子、FAST算子以及Forstner算子等[10]。在眾多的特征點檢測算子中，Forstner算子具有特征點檢測精度高以及檢測耗時少的特點。因此，本文將引用Forstner算子對圖像的特征點進行檢測。Forstner算子在檢測圖像特征點時，首先將對各個像素點的Robert梯度值進行計算，其計算過程如下[11]

(1)

(2)

獲取到Robert梯度值后，再從圖像中獲取尺寸為F×F的窗口，對該窗口的灰度協方差矩陣J進行計算[12]

(3)

令V表示J的逆矩陣，當V對應的行列式用trV表示，V對應的跡用DetV表示時，興趣值Q和H的計算過程為

(4)

(5)

然后對備選特征點判定閥值Pdf和Pdg進行設定，不失一般性可將設定規則定義如下

(6)

最后利用興趣值以及備選特征點判定閥值建立如下備選特征點判定規則

(7)

若某一像素點滿足式(7)，則該像素點就被判定為備選特征點。接著建立一個適當大小的窗口，比較窗口內的所有備選特征點，最大值對應的備選特征點則被視為特征點[13,14]。

1.2 獲取特征描述符

生成特征點的特征描述符由兩部分組成，即特征點主方向的獲取以及特征向量的獲取。SURF機制生成的特征描述符具有尺度以及旋轉不變特性。在此，將采用SURF機制獲取特征點的主方向，然后構造同心圓區域以及角度盤，對SURF機制進行改進，以求取特征向量，從而獲取特征點對應的特征描述符，以降低特征描述符的維度，使得算法的計算效率得以提高[15]。SURF機制生成特征描述符的過程如下。

選取尺度因子為φ的特征點作為圓心，對以半徑為6φ的圓形鄰域中的點，采用尺寸為4r的Haar小波求取其X以及Y方向上的Haar小波響應值[16]。用π/3大小的扇形窗口，以圓心為起點旋轉扇形窗口，對窗口內所有的點進行Haar小波響應的向量求和運算，從而獲得一個向量集合，向量集合中最長的向量則被判定為特征點對應的主方向[17]。

SURF機制中獲取到特征點主方向后，將沿著主方向上構建一個尺度為20φ×20φ的矩形窗口，并將其均分為4×4個子域。對每個子域求取主方向上及與主方向垂直方向上的Haar小波響應，分別用dx和dy表示[17]。由此可得該子域的4個特征值： ∑dx、 ∑dy、 ∑|dx|、 ∑|dy|。 對應于4×4個子域就可形成4×4×4個向量。將這64個向量進行歸一化處理后即可得到64維的特征向量。從而完成特征描述符的生成。

為了獲取維度更低的特征向量，本文將對SURF機制進行改進，以提高算法的計算效率。具體過程如下。

首先，以任意一個特征點為中心構造一個如圖2所示的同心圓區域。由圖2可知，從內到外構建的同心圓的半徑分別為3,2,2,1。這是因為離特征點越近的圓形區域對特征點的干擾越大，而離特征點越近的圓形區域旋轉起來又會引起較大的旋轉誤差，為了平衡對特征點的干擾度以及圖像旋轉誤差，故而將構造的同心圓半徑設為3,2,2,1。

圖2 同心圓區域

然后，以30度角為步長構建圖3所示的角度盤。對每個同心圓計算角度盤所示的12個方向上的梯度累計直方圖，并對所求取的梯度累計直方圖進行高斯加權處理。

圖3 角度盤

最后，將每個同心圓對應的所有梯度累加值進行降序排列，從而獲得4×12個特征向量，對這些特征向量進行歸一化處理即可得到48維的特征向量。

1.3 特征點匹配

對于m維的特征描述符I=(x1,x2,…,xm)T和J=(y1,y2,…,ym)T形成的角度λ(I,J)對應的余弦可表示為[18]

(8)

由式(8)可見，對于特征描述符I和J夾角的余弦可通過I和J的向量點積而得到。

對于任意一個待匹配特征點，可采用點積搜索法[19]在所有特征點中搜索出與其對應的具有最大點積MAXD的特征點，以及具有次大點積CMAXD的特征點。對于預定的雙閥值KF1和KF2，可通過MAXD以及CMAXD構造如下向量點積雙閥值匹配模型

(9)

若最大點積MAXD以及次大點積CMAXD滿足式(9)，則判定最大點積MAXD對應的特征點與待匹配特征點為一對匹配特征點。通過實驗得出KF1=0.3以及KF2=0.6時特征點的匹配效果較理想。

1.4 相似聚類

通過對特征點進行聚類可以對偽造圖像中的篡改內容進一步精確定位，以提高圖像偽造檢測算法的檢測精度以及正確度。本文將采用相似聚類的方法對特征點進行聚類，具體過程如下。

首先，設置Si=ki, ?i∈H,H={i|i=1,2,…N}，Si表示聚類的集合，N表示樣本的總數，在初始狀態時，將每一個特征點都是為一個聚類樣本。

然后，利用歸一化互相關函數在集合Si中尋找與聚類樣本kj,j∈i相似的聚類樣本kp,p∈i且p≠j[20]

(10)

式中：kj(x,y)與kp(g,b)分別表示兩個特征點，在所有的特征點中，當kj(x,y)與kp(g,b)形成的NCC值最大且大于閥值KFNCC時，即表示kp(g,b)是kj(x,y)的相似聚類，可將這兩個聚類樣本進行合并成一個聚類。

最后，迭代該求取相似聚類的過程就可完成特征點的聚類。

2 仿真實驗分析

仿真實驗硬件環境為：IntelI5-7500，3.5 GHz CPU，4 GB內存，500 GB硬盤。軟件環境為：Windows XP操作系統，MATLAB 7.0仿真軟件。實驗采用對比方法進行，將文獻[21,22]中的圖像偽造檢測算法設立為對照組，首先對本文算法以及對照著方法的圖像偽造檢測效果進行測試，然后再對不同算法的性能進行量化測試。

2.1 圖像偽造檢測效果測試

圖4到圖6分別為本文算法以及文獻[21,22]中方法的圖像偽造檢測效果圖，其中圖4為對簡單的復制-粘貼篡改方法偽造圖像檢測的效果圖，圖5為對縮放和噪聲疊加篡改方法偽造圖像檢測的效果圖，圖6為對旋轉和噪聲疊加篡改方法偽造圖像檢測的效果圖。從圖4到圖6可見，本文算法以及對照組算法對不同篡改方法偽造圖像的檢測都具有一定的成效，但是通過對比可見，本文算法的檢測效果較對照組方法檢測的效果較為優秀。具體表現為，在圖4中本文算法的檢測效果(如圖4(e)所示)，較對照組算法的檢測效果(如圖4(c)和圖4(d)所示)具有更高的檢測精度，正確特征匹配點的數量最多，而且錯誤檢測點或漏檢特征點最少，而文獻[21,22]兩種技術的錯誤檢測點的數量均要高于所提技術。尤其是在圖5至圖6中，本文算法的優勢更大，其檢測效果(如圖5(e)和圖6(e)所示)，較文獻[21]的檢測效果(如圖5(c)和圖6(c)所示)，以及文獻[22]的檢測效果(如圖5(d)和圖6(d)所示)具有更少的漏檢點以及錯誤檢測點。

圖4 復制-粘貼偽造圖像檢測效果

根據上述偽造檢測結果可知，本文算法具有更高的健壯性，對復制-粘貼篡改、縮放和噪聲疊加篡改，以及旋轉和噪聲疊加篡改都具有更高的檢測精度。因為本文采用了Forstner算子對特征點進行檢測，能精確提取圖像中的特征點，提高對噪聲的穩健性，同時，本文利用旋轉角度盤與同心圓區域來設計向量點積雙閥值匹配模型來實現特征點的魯棒匹配，提高其對旋轉、縮放偽造的識別精度，利用歸一化互相關函數對特征點進行了相似聚類，有效的提高了特征點的匹配正確度，以及魯棒性。文獻[21]中利用計算Hessian矩陣的方法提取特征點，然后利用歐氏度量的方法完成特征點匹配。由于Hessian矩陣提取的特征點中存在較多的偽特征點，對旋轉篡改的穩健性較差，而且利用歐氏度量完成特征點匹配會存在較多的錯誤匹配點，故而使得文獻[21]中圖像偽造檢測算法的檢測正確度較低。文獻[22]中利用提升小波變換獲取低頻分量，然后按像素特征對圖像進行分塊，最后利用偏移向量完成圖像的偽造檢測。由于按像素特征對圖像分塊會導致塊圖像的內容有重疊或者遺漏現象，導致算法的檢測正確度以及魯棒性下降。

圖5 縮放和噪聲疊加偽造圖像檢測效果

圖6 旋轉和噪聲疊加偽造圖像檢測效果

2.2 量化測試

在此將通過對本文算法以及對照組算法的檢測效率，以及檢測正確度進行量化測試來衡量算法的性能。測試對象如圖7所示。

圖7 量化測試對象

ROC曲線能良好的體現算法的檢測正確度，不同算法的ROC曲線如圖8所示。從圖8可見，本文算法較對照組算法具有更好的ROC曲線特性，說明本文算法的檢測正確度最理想。究其原因為本文采用了Forstner算子對特征點進行了精確地提取，而且還采用了向量點積雙閥值匹配模型對特征點進行了準確的匹配，最后還對特征點進行了相似聚類，從而使得算法的檢測正確度得以提升。

圖8 ROC曲線測試結果

表1為不同算法的檢測效率，通過對比表1可見，本文算法的檢測耗時為4.52 s，相對于對照組方法的檢測耗時為最少。說明了本文算法具有較好的檢測效率。因為本文采用了改進的SURF機制獲取了較低維度的特征描述符，有效降低了特征描述符獲取過程的計算復雜度，從而提高了算法的效率。文獻[21]中采用SIFT機制獲取的特征描述符維度較高，降低了算法的效率。文獻[22]中對圖像塊進行奇異值分解獲取特征向量矩陣，而且還需要進行字典排序。該過程計算復雜度較高，從而使得算法的效率下降。

表1 檢測效率測試結果

3 結束語

為了實現對偽造圖像中的篡改內容進行準確、快速的檢測，本文提出了基于向量點積耦合相似聚類的圖像偽造檢測算法的研究。采用Forstner檢測算子完成了對圖像特征點的檢測，由于Forstner算子對特征點的檢測具有精度高等特點，使得算法的檢測精度得以提升。利用構建的同心圓環以及角度盤求取梯度累計直方圖，對SURF機制進行改進，獲取低維度的特征描述符，使得算法的檢測效率得到提高。利用特征描述符形成向量點積，接著構造向量點積雙閥值匹配模型完成特征點的匹配。利用歸一化互相關函數對匹配特征點進行相似性度量，完成特征點的相似聚類，對圖像中的偽造內容進一步定位，提高了算法的檢測精度。仿真結果表明，本文所設計的圖像偽造檢測算法不僅具有較高的檢測正確度與效率，而且還具有較好的魯棒性能。

參考文獻：

[1]Mohammad Farukh Hashmi,Vijay Anand,Avinas G Keskar.Copy-move image forgery detection using an efficient and robust method combining un-decimated wavelet transform and scale invariant feature transform[J].AASRI Procedia,2014,3(9):84-91.

[2]Oussama Benrhouma,Houcemeddine Hermassi,Ahmed A Abd El-Latif.Chaotic watermark for blind forgery detection in images[J].Multimedia Tools and Applications,2016,75(14):8695-8718.

[3]Mahmoud Emam,Han Qi,Niu Xiamu.PCET based copy-move forgery detection in images under geometric transforms[J].Multimedia Tools and Applications,2016,75(18):11513-11527.

[4]ZHANG Ruifang,CHENG Xiaohui,SONG Zihang.Grey-Markov theory in blind detection of copy-move forgery in digital images by dyadic wavelet transforms[J].Journal of Guilin University of Technology,2014,34(4):775-781(in Chinese).[張瑞芳,程曉輝,宋子航.融合灰色馬爾科夫理論的二進小波圖像的復制-粘貼篡改檢測算法[J].桂林理工大學學報,2014,34(4):775-781.]

[5]WANG Haoming,YANG Xiaoyuan.Detection method for JPEG image based on the difference of DCT coefficient histograms[J].Journal of Sichuan University(Engineering Science Edition),2014,46(1):41-46(in Chinese).[王浩明,楊曉元.一種基于DCT系數直方圖差異的JPEG圖像篡改檢測[J].四川大學學報(工程科學版),2014,46(1):41-46.]

[6]Pooja Sharma.Detecting copy move forgery in digital image using sifts[J].International Journal of Latest Trends in Engineering and Technology,2016,3(7):1132-1138.

[7]LI Xiaofei,LI Pengfei.Blind detection algorithm for fake images based on SIFT[J].Journal of Changchun University,2014,24(10):1354-1357(in Chinese).[李曉飛,李鵬飛.基于SIFT的偽造圖像盲檢測算法[J].長春大學學報,2014,24(10):1354-1357.]

[8]JIAO Lixin,DU Zhenlong.Copy-paste image forgery blind detection based on mean shift[J].Journal of Computer Applications,2014,34(3):806-809(in Chinese).[焦麗鑫,杜振龍.基于均值漂移的圖像復制粘貼偽造盲檢測[J].計算機應用,2014,34(3):806-809.]

[9]YANG Renqing,BAI Zhengyao,YIN Liguo.Detecting of copy-move forgery in digital images using fractional Fourier transform[J].Journal of Yunnan University(Natural Scie-nces Edition),2016,38(1):18-22(in Chinese).[楊仁青,柏正堯,尹立國.基于分數傅里葉變換的數字圖像復制-粘貼篡改檢測算法[J].云南大學學報(自然科學版),2016,38(1):18-22.]

[10]Ma Chi,Zhu Yongyong,Tian Ying.Ear recognition based on Forstner and SIFT[J].TELKOMNIKA:Indonesian Journal of Electrical Engineering,2013,12(11):367-373.

[11]SHEN Xingxing,BAO Wenxing.The remote sensing image matching algorithm based on the normalized cross-correlation and SIFT[J].Journal of the Indian Society of Remote Senk-sing,2014,24(2):417-422.

[12]GUO Bingxuan,LUO Guangguang,XIAO Xiongwu.Forstner feature point classification and precise location method[J].Science Technology and Engineering,2016,16(16):73-78(in Chinese).[郭丙軒,羅光光,肖雄武.Forstner特征點分類和精確定位方法探討[J].科學技術與工程,2016,16(16):73-78.]

[13]HE Yinan,GENG Juan,QIN Jun.Forstner feature point classification and precise location method[J].Remote Sensing for Land & Resources,2015,27(1):48-54(in Chinese).[賀一楠,耿娟,秦軍.結合Forstner與NCC約束的UAV圖像配準研究[J].國土資源遙感,2015,27(1):48-54.]

[14]Ma Chi,Zhu Yongyong,Tian Ying.Ear recognition based on Forstner and SIFT[J].Telkomnika-Indonesian Journal of Electrical Engineering,2013,11(12):269-278.

[15]LI Yan,LIU Nian,ZHANG Bin.FI-SURF algorithm for image copy-flip-move forgery detection [J].Journal on Communications,2015,36(5):1-12(in Chinese).[李巖,劉念,張斌.圖像鏡像復制粘貼篡改檢測中的FI-SURF算法[J].通信學報,2015,36(5):1-12.]

[16]ZHANG Yong,WANG Zhifeng,MA Wen.Research image mosaic algorithm based on improved SIFT feature matching[J].Microelectronics & Computer,2016,33(3):60-64(in Chinese).[張勇,王志鋒,馬文.基于改進SIFT特征點匹配的圖像拼接算法研究[J].微電子學與計算機,2016,33(3):60-64.]

[17]Oliveira SAF,Rocha Neto AR,Bezerra FN.A novel genetic algorithms and SURF-based approach for image retargeting[J].Expert Systems with Applications,2016,44(8):332-343.

[18]YAN Zigeng,JIANG Jianguo,GUO Dan.Image matching based on SURF feature and Delaunay triangular meshes[J].Acta Automatica Sinica,2014,40(6):1216-1222(in Chinese).[閆自庚,蔣建國,郭丹.基于SURF特征和Delaunay三角網格的圖像匹配[J].自動化學報,2014,40(6):1216-1222.]

[19]Rajeev Kaushika,Rakesh Kumar Bajajb,Jimson Mathewc.On image forgery detection using two dimensional discrete cosine transform and statistical moments[J].Procedia Compu-ter Science,2015,70(1):130-136.

[20]OU Hongyu,CHEN Xi,SONG Yanhui.Detection of image duplication forgery based on local binary pattern[J].Computer Applications and Software,2013,30(9):170-172(in Chinese).[歐紅玉,陳曦,宋燕輝.基于LBP的圖像復制篡改檢測[J].計算機應用與軟件,2013,30(9):170-172.]

[21]Swapnil H Kudke,Avinash D Gawande.Copy-move attack forgery detection by using SIFT[J].International Journal of Innovative Technology and Exploring Engineering,2013,5(1):221-224.

[22]CHAI Xinxin,QIU Xiaohui.Image forgery detection algorithm based on lifting wavelet transform[J].Computer Technology and Development,2016,26(4):78-81(in Chinese).[柴新新,邱曉暉.基于提升小波變換的圖像篡改檢測算法[J].計算機技術與發展,2016,26(4):78-81.]