基于單應(yīng)性矩陣剔除SURF 錯(cuò)誤匹配點(diǎn)的復(fù)制-移動(dòng)偽造圖像檢測

宋 凱，吳建華

（沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 110159）

圖像偽造檢測方法分為兩大類：數(shù)字圖像主動(dòng)取證和數(shù)字圖像被動(dòng)取證（盲數(shù)字圖像盲取證）［1］。數(shù)字圖像被動(dòng)取證主要針對(duì)拼接圖像和復(fù)制-移動(dòng)偽造圖像。

復(fù)制-移動(dòng)偽造［2］是一種常見的篡改形式，通常是從圖像中的某一部分復(fù)制一個(gè)區(qū)域來覆蓋某一對(duì)象，從而使該對(duì)象從圖像中消失。被復(fù)制-移動(dòng)偽造所改變的區(qū)域通常是肉眼無法分辨的。因此，檢測這些行為的證據(jù)是圖像取證中的一個(gè)重要問題。復(fù)制-移動(dòng)偽造檢測的根本是檢測偽造圖像中各部分之間存在的特定聯(lián)系，可以通過窮舉搜索［3］方法直接檢測。大多數(shù)的復(fù)制-移動(dòng)偽造檢測方法主要是檢測偽造區(qū)域的邊界變化。SHIVA‐KUMAR B L［4］提出了一種利用SURF 識(shí)別重復(fù)區(qū)域的方法，通過匹配測試圖像中的兩個(gè)關(guān)鍵點(diǎn)子集來獲得匹配的關(guān)鍵點(diǎn)。然而，匹配之后的圖像中存在錯(cuò)誤匹配點(diǎn)。對(duì)偽造圖像進(jìn)行檢測操作，如圖1所示。

圖1 圖像偽造檢測

HERBERT B 等人［5］提出了快速檢測器和描述符，稱為改進(jìn)的SURF 算法。此算法在提高檢測器和描述符速度的基礎(chǔ)上，保留了良好的性能，如對(duì)噪聲、位移幾何變換等具有魯棒性。

1 SURF算法

SURF算法是基于積分圖像和Hessian矩陣，用來描述關(guān)鍵點(diǎn)檢測器和描述符。該算法利用積分圖像對(duì)給定圖像中的像素點(diǎn)的強(qiáng)度進(jìn)行計(jì)算，求得矩形區(qū)域像素強(qiáng)度，并通過快速Hessian 矩陣提取特征點(diǎn)。對(duì)于每個(gè)特征點(diǎn)，計(jì)算Haar 小波變換以確定其主方向，并確定特征點(diǎn)描述子，再根據(jù)描述向量之間的歐式距離實(shí)現(xiàn)圖像間的特征點(diǎn)的匹配［6］。該方法計(jì)算速度快，匹配精確度高。

1.1 興趣點(diǎn)檢測

SURF 是基于Hessian 矩陣來檢測特征點(diǎn)的。在圖像中給定一個(gè)像素點(diǎn)X=（x，y），則尺度為σ的Hessian矩陣H（x，σ）的定義為

式中，Lxx(x,σ)是經(jīng)過高斯濾波器、二階微分在點(diǎn)X=（x，y）處和圖像的卷積，類似的還有Lxy(x,σ)和Lyy(x,σ)。

在此基礎(chǔ)上，計(jì)算出圖像中每個(gè)像素的Hessian行列式，并用這些值找到興趣點(diǎn)。SURF 采用方型濾波器，借此近似達(dá)到高斯糢糊。使用方型濾波器可使積分圖像大幅提高運(yùn)算速度，僅需計(jì)算位于濾波器方型的4 個(gè)角落值即可。采用不同尺寸的方型濾波器掩模對(duì)整幅圖像中不同尺度層的所有強(qiáng)度值進(jìn)行卷積。通過濾波后的圖像相互相減，得到高斯（DoG）近似的差值。SURF 使用9×9 方型濾波器（圖2）作為初始規(guī)模層（最底層），相當(dāng)于高斯導(dǎo)數(shù)σ=1.2 的濾波器，越往上層的尺度濾波器的大小也就跟著增加。用Dxx、Dyy和Dxy近似表示斑點(diǎn)的響應(yīng)映射。圖2a 和圖2b 分別為在y方向和xy方向上帶盒型濾波器的二階高斯偏導(dǎo)數(shù)。

圖2 興趣點(diǎn)檢測

Hessian行列式的精確近似公式如下：

式中，ω≈0.9，保證了近似的能量守恒。

在確定了DoG 的近似值后，下一步是構(gòu)造函數(shù)來選擇極值點(diǎn)。

1.2 興趣點(diǎn)描述符

SURF提取圖像的描述符分為兩步：

1）以檢測到的興趣點(diǎn)為中心構(gòu)建圓形區(qū)域。根據(jù)檢測圓形區(qū)域的信息來確定唯一方向，從而實(shí)現(xiàn)圖像旋轉(zhuǎn)不變性。通過計(jì)算x和y方向上的Haar小波響應(yīng)求出方向。以興趣點(diǎn)為中心計(jì)算Haar 小波響應(yīng)，將計(jì)算出的響應(yīng)用高斯（σ=2.5）加權(quán)。在下一步中，通過對(duì)旋轉(zhuǎn)扇形的水平和垂直小波響應(yīng)求和來估計(jì)主導(dǎo)方向，該旋轉(zhuǎn)扇形在小波響應(yīng)空間中覆蓋π/3的角度。然后選擇得到的最大值來描述興趣點(diǎn)描述符的方向。

2）在選定特征點(diǎn)方向后，其周圍像素點(diǎn)需要以此方向?yàn)榛鶞?zhǔn)來建立描述子。該區(qū)域被均勻地分割［7］成更小的正方形子區(qū)域，以5×5 個(gè)像素點(diǎn)為一個(gè)子區(qū)域，對(duì)每個(gè)子區(qū)域的水平和垂直小波響應(yīng)進(jìn)行求和，形成特征向量的第一組分量。為了提高對(duì)幾何變形的魯棒性，計(jì)算子區(qū)域內(nèi)的x、y方向（此時(shí)以平行特征點(diǎn)方向?yàn)閤，垂直特征點(diǎn)方向?yàn)閥）的Haar 小波變換總和及向量長度總和共4 個(gè)量值，共可產(chǎn)生一個(gè)64 維特征描述符。將這4 個(gè)值作為每個(gè)子塊區(qū)域的特征向量，一共有4×4×4=64 維向量作為SURF 特征的描述符。

2 算法實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果分析

該系統(tǒng)應(yīng)用SURF 算法提取特征，然后利用KD-tree 對(duì)重復(fù)區(qū)域進(jìn)行識(shí)別，最后利用相似三角形求出基準(zhǔn)單應(yīng)性矩陣，通過設(shè)定閾值剔除錯(cuò)誤的匹配對(duì)。在復(fù)制-移動(dòng)偽造中，被復(fù)制的部分與原部分的外觀基本相同。因此，偽造區(qū)域提取的關(guān)鍵點(diǎn)與原始區(qū)域的關(guān)鍵點(diǎn)非常相似。SURF特征之間的匹配可以用于確定篡改區(qū)域。圖3 為系統(tǒng)框圖，第一步用SURF 提取特征，第二步進(jìn)行關(guān)鍵點(diǎn)匹配，第三步剔除錯(cuò)誤的匹配點(diǎn)。

圖3 系統(tǒng)概覽

2.1 描述符匹配

在該系統(tǒng)中，采用KD-tree 算法對(duì)復(fù)制區(qū)域進(jìn)行識(shí)別［8］，并對(duì)關(guān)鍵點(diǎn)進(jìn)行匹配。KD-tree 是搜索最近鄰的常用結(jié)構(gòu)。KD-tree將數(shù)據(jù)預(yù)處理成數(shù)據(jù)結(jié)構(gòu)，以便能夠進(jìn)行有效的范圍查詢。它是一個(gè)二叉樹，在葉節(jié)點(diǎn)中存儲(chǔ)k維空間的點(diǎn)，在每個(gè)空間點(diǎn)上，用k-1 維超平面將k維空間劃分為兩部分。假設(shè)KD-tree 由N個(gè)特征向量組成，需要構(gòu)造O（Nlog2N）操作，搜索O（log2N）。

給定一個(gè)測試圖像，一組關(guān)鍵點(diǎn)X={x1，…，xn}及其對(duì)應(yīng)的SURF描述符{f1，…，fn}。在SURF空間中對(duì)每個(gè)關(guān)鍵點(diǎn)的fi向量進(jìn)行匹配操作，識(shí)別出測試圖像中相似的局部塊。在SURF 空間中，利用最小歐幾里得距離確定每個(gè)關(guān)鍵點(diǎn)X的最近鄰，從而找到每個(gè)關(guān)鍵點(diǎn)X最佳候選匹配。KD-tree用閾值Th搜索最近的鄰域。

2.2 剔除錯(cuò)誤匹配

在尋找到描述符的最佳候選匹配后，通過相似三角形與單應(yīng)性矩陣結(jié)合［9］，剔除錯(cuò)誤的匹配對(duì)。

首先，利用正確匹配點(diǎn)形成相似三角形的特點(diǎn)選取出正確匹配對(duì)（至少4 對(duì)）。對(duì)任意一對(duì)匹配點(diǎn)Ri和Si，利用KD-tree 找到相鄰的兩對(duì)匹配點(diǎn)Ri+1、Ri+2和Si+1、Si+2。判斷三角形RiRi+1Ri+2和 三角形SiSi+1Si+2對(duì)邊夾角是否近似相同，只需計(jì)算對(duì)邊夾角的余弦值之差是否小于閾值C，如小于閥值C，則認(rèn)為三角形相似。即對(duì)邊夾角滿足：

式中，閾值C=0.05。

如果滿足式（4），就保留Ri+1、Ri+2和Si+1、Si+2作為基準(zhǔn)點(diǎn)。在剩余匹配對(duì)中繼續(xù)尋找滿足相似三角形條件的匹配對(duì)，直到所有滿足相似三角形的正確匹配點(diǎn)對(duì)被找到為止。

然后，根據(jù)已找到的正確匹配點(diǎn)對(duì)，估計(jì)幾何變換的單應(yīng)矩陣H，作為基準(zhǔn)單應(yīng)性矩陣。從剩余的匹配點(diǎn)對(duì)中找到滿足歐式距離小于閾值的正確匹配對(duì)，選擇對(duì)稱轉(zhuǎn)移誤差作為距離函數(shù)d。

式中，x和x'分別為圖像中的對(duì)應(yīng)匹配點(diǎn)的矩陣；‖·‖為兩點(diǎn)之間的歐式距離。

對(duì)于一對(duì)匹配點(diǎn)Rk和Sk，如果d（Rk，Sk）＜δ，則認(rèn)為Rk、Sk是一對(duì)正確的匹配點(diǎn)，否則將這對(duì)匹配點(diǎn)剔除。其中，根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)取值，δ=1.8。

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

該方法已在計(jì)算機(jī)上通過Matlab R2016 a 版本實(shí)現(xiàn)，該計(jì)算機(jī)的CPU為2.80 GHz，內(nèi)存為8 GB。利用SURF 算法對(duì)關(guān)鍵字進(jìn)行檢測，得到關(guān)鍵字的描述符。實(shí)驗(yàn)中獲取64-d SURF 描述符，采用KD-tree 算法進(jìn)行關(guān)鍵點(diǎn)匹配，利用單應(yīng)性矩陣對(duì)錯(cuò)誤匹配點(diǎn)進(jìn)行剔除。

實(shí)驗(yàn)圖像來源于CHRISTLEIN V 等人［10］提出的數(shù)據(jù)集。對(duì)于不同分辨率的圖像，考慮對(duì)其提取特征的個(gè)數(shù)也不同。對(duì)于高于3 000×2 000 像素的圖像，提取特征點(diǎn)要更多，因此匹配錯(cuò)誤塊的概率要高得多。

如圖4 所示，該方法可以檢測從圖像中提取的SURF關(guān)鍵點(diǎn)后的重復(fù)區(qū)域。本次實(shí)驗(yàn)閾值Th固定為0.045。當(dāng)閾值相同時(shí)，高分辨率圖像的匹配點(diǎn)更多。通過本實(shí)驗(yàn)的方法剔除錯(cuò)誤匹配點(diǎn)后，動(dòng)物的匹配點(diǎn)仍然多于建筑物的匹配點(diǎn)。

圖4 單應(yīng)性矩陣對(duì)錯(cuò)誤匹配點(diǎn)進(jìn)行剔除

從魯棒性的角度對(duì)該方法的檢測性能進(jìn)行了測試，研究了旋轉(zhuǎn)、縮放和噪聲對(duì)建筑物性能的影響?？紤]不同角度的旋轉(zhuǎn)，對(duì)魯棒性檢測性能進(jìn)行測試，如圖5所示。

圖5 魯棒性檢測性能測試

對(duì)在復(fù)制區(qū)域加入高斯噪聲后產(chǎn)生畸變的圖像進(jìn)行了實(shí)驗(yàn)，檢測結(jié)果如圖6所示。

圖6 高斯噪聲的檢測結(jié)果

對(duì)復(fù)制區(qū)域做縮放比例為90%和115%的圖像進(jìn)行檢測，檢測結(jié)果如圖7所示。

圖7 對(duì)縮放后的篡改圖像進(jìn)行檢測

3 結(jié)論

本文提出了一種基于單應(yīng)性矩陣剔除錯(cuò)誤匹配的方法。通過SURF 算法對(duì)偽造圖像進(jìn)行檢測，測試了SURF 的魯棒性。實(shí)驗(yàn)結(jié)果表明，該方法能夠剔除經(jīng)過SURF 算法檢測的錯(cuò)誤匹配點(diǎn)，對(duì)高分辨率圖像中的匹配點(diǎn)更加有效，同時(shí)保留更多的匹配對(duì)。