【摘要】 提出一種在區(qū)域復(fù)制圖像篡改檢測中的塊匹配檢測的效率提高方法。將待匹配的圖像分塊進行簡單分類，被劃分為不同類的分塊之間具有明顯的區(qū)別，根據(jù)不同分類將所有的圖像分塊劃分為多個分塊隊列。在分塊相似度匹配的過程中，只有分類一致或接近的分塊隊列才進行匹配計算，避免了具有明顯區(qū)別的圖像分塊匹配過程，從而大量降低分塊匹配的次數(shù)，提高算法運行效率。實驗結(jié)果表明，提出的改進方法與原算法的檢測結(jié)果基本一致，而算法運行時間有較大幅度減少。

【關(guān)鍵詞】 圖像篡改 區(qū)域復(fù)制 篡改檢測 效率改進

一、引言

隨著當今網(wǎng)絡(luò)技術(shù)的快速發(fā)展，以及攝像器件的小型化和便捷化，數(shù)字影像已經(jīng)成為我們獲取信息的主要方式之一。然而，伴隨著數(shù)字圖像處理算法和編輯軟件的迅速發(fā)展和普及，數(shù)字圖像或視頻很容易通過圖像處理軟件被篡改。被篡改的圖像有時候人眼不容易辨別出來，導致人們?nèi)菀妆淮鄹暮蟮挠跋袼`導[1-2]。

數(shù)字圖像篡改檢測技術(shù)作為被動圖像認證的技術(shù)存在很多種檢測方式，包括區(qū)域復(fù)制的檢測、圖像重采樣檢測技術(shù)、多次JPEG壓縮圖像的檢測、基于噪聲分布不一致性的檢測、圖像模糊潤飾檢測等，這些方法都有其優(yōu)點和局限性[1-2]。

區(qū)域復(fù)制篡改是通過同一圖像上的復(fù)制-粘貼操作，將圖像中原有的某些信息遮蓋隱藏的一種常用的篡改手段。針對該篡改方式，F(xiàn)ridrich等人首先提出了對圖像進行分塊，然后對圖像分塊DCT系數(shù)量化后進行字典排序，尋找相似塊從而找出復(fù)制區(qū)域的算法[3]。Farid等人對圖像分塊進行PCA降低維度與量化，再使用字典排序方法尋找相似圖像區(qū)域[4]。Li G H等人先對圖像進行DWT變換再進行分塊，提取分塊的奇異值進行字典排序檢測相似圖像分塊[5]。魏為民等人將圖像進行兩種不同的分塊：不重疊分塊和單像素滑動重疊分塊，對兩組分塊進行haar小波變換，在兩組小塊之間使用小波變換的低頻子帶進行Pearson相關(guān)系數(shù)的計算進行相似分塊的匹配檢測[6]。劉潘梅等人提出在文獻[6]的基礎(chǔ)上對haar小波變換后的低頻子帶再次進行PCA降維，得到的1結(jié)果作為分塊特征向量進行Pearson相關(guān)系數(shù)的計算[7]。

本文針對魏為民等人提出的算法進行改進，將該算法中兩組分塊隊列中的重疊分塊隊列進行分類，形成多個子隊列。不重疊分塊隊列中的分塊不需要與所有的重疊分塊進行比較，而是與部分子隊列中的分塊進行比較。從而可以較大的提高算法運行速度。

二、基于分類比較的算法描述

2.1 原始算法

首先對魏為民等人提出的算法進行簡要描述：

（1）將圖像按兩種分塊方式分別分塊，形成2組分塊隊列。分塊方式分別為不重疊分塊和單像素滑動重疊分塊，如圖1所示：

假設(shè)待測圖像大小為M×N，分塊大小為b×b。那么不重疊分塊數(shù)量為（M/b）×（N/b）（M，N不是b的整數(shù)倍則取整）單像素滑動重疊分塊數(shù)量為（M-b+1）×（N-b+1）。如此就形成2組分塊隊列，不重疊分塊隊列中的分塊用Bj表示，另一個隊列的分塊用Bi表示。

（2）對每一個分塊Bj和Bi進行haar小波變換，使用低頻子帶cAj或cAi作為分塊Bj或Bi的特征向量：

[cAi， cHi， cVi， cDi]=dwt2（Bi ，‘haar‘）；

（3）將2組隊列分塊的特征向量進行匹配檢測，匹配算法使用Pearson相關(guān)系數(shù)檢測方法：

上式中X和Y分別表示兩組隊列分塊的特征向量cAj和cAi，計算結(jié)果為兩個特征向量的相關(guān)系數(shù)，當相關(guān)系數(shù)超過門限值就認為兩個分塊相似，可能是復(fù)制篡改區(qū)域。匹配過程的復(fù)雜度可以從下圖看出：

上圖中，可以看到每個不重疊分塊的特征向量都要與所有重疊分塊的特征向量進行匹配運算。匹配的次數(shù)為（M/b）×（N/b）×（M-b+1）×（N-b+1）。分塊尺寸會影響復(fù)雜度，分塊越大匹配次數(shù)越低，但是分塊太大容易超出篡改區(qū)域的尺寸，所以一般分塊尺寸大小選擇為16×16。

2.2 基于分類比較的改進算法

我們觀察一副圖像可以發(fā)現(xiàn)，圖像的所有分塊中，很多的分塊具有很明顯的區(qū)別，如下圖所示，圖中A、B、C三個分塊具有很明顯的區(qū)別：

那么對于前一小節(jié)所述的不重疊分塊組中的分塊是否需要與另一個隊列的所有重疊小塊進行匹配運算呢？答案是否定的。因此，可以根據(jù)某種分類依據(jù)，屬于同一類的分塊才進行Pearson相關(guān)系數(shù)計算進行匹配。即可以將重疊分塊隊列按分類標準分成幾個子隊列，而每個不重疊分塊選擇其中分類接近的部分子隊列進行匹配計算，而不是與所有重疊分塊進行匹配計算，從而大大減少了匹配的次數(shù)。如下圖所示：

對于分類方式，本文使用分塊的低頻子帶所有像素數(shù)值之和來進行分類。依據(jù)主要有三點：首先相似分塊的像素和會比較接近；其次所有像素值之和對均值為零的噪聲具有較好的抵抗能力；最后是該分類計算比較簡單。不同的分類方式具有各自優(yōu)缺點，當然有其他分類方式會具有更好性能，但可能計算比較復(fù)雜。

根據(jù)分塊大小為16×16來進行分類設(shè)計：

（1）16×16分塊的小波變換的低頻子帶為8×8像素，對每個像素值除2后，其值范圍為[0，255]，其所有像素之和范圍是[0，16320]。將該范圍分為32個區(qū)間，每個區(qū)間的范圍大小是510。即可以將重疊分塊劃為32個子隊列。

（2）重疊分塊組中的分塊根據(jù)低頻子帶的像素值之和分別劃分到32個子隊列中。而每個不重疊分塊也根據(jù)低頻子帶的像素值之和標識其對應(yīng)子隊列。這里要注意的是，不重疊分塊子帶的像素值之和可能落在區(qū)間邊緣，所以不重疊分塊不僅要與對應(yīng)的子隊列進行匹配，還要與其前后兩個子隊列即共三個子隊列進行匹配計算。這樣就能保證所有低頻子帶像素和的距離在510以內(nèi)的分塊都能進行匹配計算。如下圖所示，對應(yīng)子隊列4的分塊要與子隊列3，4，5里的分塊進行匹配計算：

上述分類將重疊分塊劃分為32個子隊列，其中隊列的數(shù)量對復(fù)雜度和性能有一定的影響。劃分的隊列越多，隊列里的分塊越少，因此算法速度就越快。但是隊列多表示隊列的數(shù)值范圍減少，就容易導致漏判的情況出現(xiàn)。本文采用32個隊列，每個隊列范圍510，經(jīng)過測試發(fā)現(xiàn)，兩個復(fù)制分塊的低頻子帶像素和的差值很少超過510的值。

三、實驗結(jié)果

采用以下兩張纂改后的圖像對本文提出的改進算法與文獻[6]中的原算法進行比較：

在算法實現(xiàn)的過程中，考慮到2.1節(jié)中的式（1）里的以下部分只與分塊一一對應(yīng)：

所以可以在建立隊列的時候就將所有分塊計算好式（2）和式（3）并保存。在分塊匹配的過程中就可以減少這部分的重復(fù)計算?？梢砸欢ǔ潭壬咸岣咚惴ㄟ\行效率。原方法與本文提出的方法在仿真過程中都采用了該方式提高運行效率。

仿真測試的平臺是intel CPU酷睿雙核主頻2.2GHz、內(nèi)存2G、WindowsXP系統(tǒng)與Matlab 7.0。測試結(jié)果如下：

運行時間：

從檢測結(jié)果來看，原算法和改進算法的結(jié)果基本一致，都可以檢測出復(fù)制區(qū)域。但是也都存在誤判的情況。而從運行時間來看改進后的算法耗時是原算法的1/3左右，運行效率有較大提升。

四、結(jié)束語

本文在文獻[6]的算法基礎(chǔ)上設(shè)計了一種利用分類比較的方法，將圖像分塊分為多個不同分類的子隊列，通過只比較分類接近的分塊子隊列來大幅度的降低分塊匹配次數(shù)。該方法可以適用于其他基于塊相似度匹配的算法，可以在基本保持性能的前提下，提高算法效率。