基元樹建筑物圖像偽造組件檢測算法

吳冰潔，杜振龍

（南京工業(yè)大學(xué)電子與信息工程學(xué)院，江蘇 南京 211800）

0 引 言

隨著數(shù)字獲取技術(shù)的發(fā)展，利用攝像機、數(shù)碼相機、智能手機等設(shè)備能方便、快捷地獲取生活、旅游等方面的圖像資料。這些數(shù)字媒體文檔為豐富現(xiàn)代人們的精神生活提供了影像物料，其中，以地標(biāo)建筑、歷史建筑物為背景的生活圖像占了相當(dāng)大的比重。然而，不斷發(fā)展的圖像編輯技術(shù)為人物生活照的編輯和合成提供了強有力的支持，使得普通用戶可以容易地更改圖像中的建筑物圖像而不被察覺，從而產(chǎn)生充斥互聯(lián)網(wǎng)的“移花接木”圖像。為了保證圖像內(nèi)容的真實性，可通過鑒定圖像中的建筑物部分是否被修改來判斷圖像真?zhèn)巍Ｒ虼耍ㄖ飯D像的檢測具有一定的現(xiàn)實需求和意義。同時，李滿滿等[1]指出，圖像合成處理后的偽造圖像是難以檢測出來的。

眾所周知，建筑物圖像的主要組成部分是窗戶、陽臺等基本建筑構(gòu)成單元，即建筑物基元。建筑物圖像變形是改變一個或多個基元數(shù)量或位置信息，本質(zhì)是改變基元之間的空間關(guān)系。通過將基元進行新的空間組合，構(gòu)造出新基元組件，整合多個基元組件偽造出“莫須有”的圖像。由于建筑物圖像在三維重建中的重要性，對建筑物圖像的研究已經(jīng)成為近年來的熱點。而傳統(tǒng)的逐像素[2-4]或逐塊的檢索方法[5-7]通過將圖像分塊，提取圖像塊或像素點特征，進行相關(guān)性檢測，從而搜尋到匹配區(qū)域，但忽略了圖像內(nèi)容上的語義聯(lián)系以及空間結(jié)構(gòu)特征，且計算量大，使得這些圖像特征檢測方法難以鑒別圖像真?zhèn)巍Ｈ鏢hivakumar等[2]提出使用基于SURF特征的檢測算法，聯(lián)合K-d樹與SURF特征，來實現(xiàn)多維特征匹配，以檢測偽造區(qū)域，實驗結(jié)果顯示其算法具有較好的魯棒性。但該算法在圖像全局屬性表達方面較弱，影響了檢測結(jié)果的準(zhǔn)確性。Amerini等[4]提出使用SIFT特征提取圖像特征點與特征向量，可調(diào)整特征匹配時仿射變換參數(shù)從而減少特征點對的誤配。但該方法計算量較大，匹配效率低。Cao等[5]提出使用離散余弦變換DCT表示圖像塊單元特征，通過與閾值進行比較篩選出疑似偽造圖像塊。但該方法忽略了圖像塊之間的語義聯(lián)系與空間關(guān)系，對經(jīng)過加噪與模糊處理的偽造圖像塊檢測效率較差。

對此，研究人員開發(fā)了新的針對建筑圖像偽造檢測技術(shù)。Martinovic等[8]提出使用遞歸神經(jīng)網(wǎng)絡(luò)（RNN）與馬爾科夫隨機場（MRF）構(gòu)成的三層模型，并從其語義上提取了建筑物基元；但該方法在使用RNN進行訓(xùn)練時，需要先將圖像進行過度分割，生成許多塊區(qū)域，這將占據(jù)大量內(nèi)存空間。Teboul等[9]提出使用自定義的建筑結(jié)構(gòu)規(guī)則，結(jié)合監(jiān)督分類與隨機過程方法分割出建筑物基元。但是該方法需要對基元形狀進行過程學(xué)習(xí)，訓(xùn)練樣本的差異會影響最終基元檢測結(jié)果。Fan等[10]提出通過將實驗圖像可見部分的建筑物基元表示成包絡(luò)盒，即剛好容納基元區(qū)域的外接矩形，并結(jié)合圖像數(shù)據(jù)庫訓(xùn)練得到的建筑物布局候選項，補齊實驗圖像未知部分基元，從而構(gòu)造出完整的建筑物圖像。但是該方法需要依賴圖像數(shù)據(jù)庫，數(shù)據(jù)庫中不完備的圖像種類將導(dǎo)致可能無法產(chǎn)生布局候選項，繼而降低了其檢測準(zhǔn)確度。

為了解決上述難題，本文提出一種圖像基元樹表示法，即對建筑物圖像進行基元提取，根據(jù)建筑物對稱性特點[11]生成基元樹，通過檢索基元樹結(jié)點對應(yīng)的非聚合組件的對稱因子和聚合組件的密集度差異值，快速定位疑似偽造組件，并測試了本文算法的檢測速度與準(zhǔn)確度。

1 建筑物圖像的基元樹表示

首先對建筑物圖像進行基元提取，再依據(jù)對稱性原則，構(gòu)造出基元樹。

1.1 基元提取

建筑物由于其人工構(gòu)建特性，具有基元重復(fù)性和規(guī)整性。利用這些人為特性，將建筑物圖像中重復(fù)構(gòu)建的門、窗等基元作標(biāo)記，然后采用包絡(luò)盒替代細(xì)節(jié)復(fù)雜的基元區(qū)域，從而提取出基元，得到清晰的基元空間分布圖。

輸入一幅建筑物圖像，交互式地將門、窗、陽臺等建筑物外表形狀規(guī)整的元素作為基元予以標(biāo)記，如圖1（b）所示。定義基元的集合表示，設(shè)e={門|窗|陽臺|…}表示建筑物圖像的基元。由于基元類型不同，故定義了標(biāo)簽集合L={l1|l2|l3|…}代表不同類別的基元，其中，li是標(biāo)識不同類別基元的標(biāo)簽，i=1，2，3，…，n。空間分布不同的多種類別基元可以組成空間結(jié)構(gòu)不同的基元組件，故基元組件S為基元e的并集，定義S=∪e為由基元e組裝成的組件。不同結(jié)構(gòu)的組件通過不同的拼接方式可以構(gòu)造出多樣基元樹，故基元樹為組件的并集，定義T=∪S是由組件構(gòu)成的基元樹。

在建筑物圖像中，由于個別基元邊緣模糊以及基元之間的拍攝光強不一致等外界因素，使得同類基元區(qū)域各方面呈現(xiàn)差異。為了消除這些干擾因素，本文引入包絡(luò)盒，利用不同顏色的包絡(luò)盒來替代表示不同類別的基元，忽略非基元區(qū)域，將各類基元進行提取，從而得到空間結(jié)構(gòu)明朗的包絡(luò)盒表示圖，見圖 1（c）。

設(shè)包絡(luò)盒 bos=（l，x，h，left，right，parent）， 式中l(wèi)表示基元類別，x、h分別表示包絡(luò)盒寬度和高度，（left，right，parent）∈N3代表左右基元及所屬組件的信息。

1.2 組件拆分

圖像經(jīng)過基元提取后得到的包絡(luò)盒表示圖，需以此為跟結(jié)點，進行組件拆分操作，從而構(gòu)造基元樹。

根據(jù)建筑物對稱特性，可以發(fā)現(xiàn)在建筑物圖像中，基元之間的空間關(guān)系是聚合或者嵌入。因此，根據(jù)不同的空間關(guān)系，對組件進行不同的拆分操作，從而簡化組件的基元組合關(guān)系。

圖1 基元提取

圖2 組件分割操作

聚合，即同一類基元聚集在某一區(qū)域，且該區(qū)域不包含其他類別的基元。若沿著中軸線把該區(qū)域分成空間相等的兩個部分，則每個部分所包含的基元數(shù)目是相等的。當(dāng)組件中包含聚合組件時，為了保存聚合區(qū)域的對稱性，采用分割的方式將聚合組件從原組件中分離出來，從而得到兩個新組件，如圖2所示。

嵌入，即不同類別基元在空間上間隔地分布，通常是在聚合組件中插入其他類別的基元，從而導(dǎo)致組件中的基元類別不統(tǒng)一，不同的基元錯落排列，組件不具備對稱性，則稱該組件為非聚合組件。為了保存部分聚合區(qū)域的結(jié)構(gòu)完整性，而采用嵌入的方式，使用聚合類別的基元虛擬取代非本類基元，并將非本類基元從該區(qū)域中剔除，如圖3所示。

圖3 組件嵌入操作

1.3 對稱性計算

對組件進行拆分操作時，由于存在聚合與嵌入兩種選擇，故提出對兩種選擇分別進行對稱性計算，選取對稱性大者為拆分選擇。

在構(gòu)造基元樹過程中，需要對結(jié)點所代表的組件進行對稱性計算。由于基元樹的組成單元為基元或者組件，故本文定義了基元或組件對稱性。

定義基元對稱性：提取基元時，為得到清晰的基元空間分布，使用包絡(luò)盒替代基元進行表示。為了抽取本質(zhì)特征，應(yīng)將包絡(luò)盒表示法應(yīng)用于對稱性計算。假設(shè)A為基元對應(yīng)的包絡(luò)盒，將其置于二維直角坐標(biāo)系上，使其水平范圍為[0，λ]，即寬x∈[0，λ]，高為h，PA（x）定義為與A關(guān)于位于坐標(biāo)x的垂直直線做鏡像對稱A′的重復(fù)面積。故基元對稱性PA（x）的計算模型為

定義組件對稱性：由于組件中包含多個基元，所以對稱性關(guān)系包括基元自身對稱性以及基元之間對稱性。基元自身對稱性使用上述的基元對稱性模型進行計算。 基元之間對稱性，則使用模型PA1，A2（x）表示。兩個空間位置相鄰的基元A1、A2可能屬于同一類別或者不同類別。A1、A2類別相同時，PA1，A2（x）代表基元A1與基元A2關(guān)于橫坐標(biāo)為x垂直直線做鏡像對稱A2′的重復(fù)面積。A1、A2類別不同時，則對應(yīng)的包絡(luò)盒面積大小不同，不存在對稱關(guān)系，PA1，A2（x）值為0。綜上所述，則組件對稱性PS（x）計算模型為

式中S表示組件。

式中：Φ（S）——組件整體對稱性；

[-λS/2，+λS/2]——組件對應(yīng)包絡(luò)盒的寬度；

g（x）——高斯權(quán)重函數(shù)。

在選擇組件拆分方式時，需計算拆分后的兩個子組件或者基元的對稱性之和，由于不同類別基元對應(yīng)的包絡(luò)盒面積大小不同，為了對不同面積的基元進行統(tǒng)一衡量并求和，本文對對稱性計算進行歸一化操作。設(shè)β（S）為組件S對應(yīng)的包絡(luò)面積，S1，S2為拆分后的兩個子組件或者基元。則定義歸一化函數(shù)NS（S1，S2）為

式中：S1，S2——拆分后的兩個子組件或者基元；

NS（S1，S2）——S1，S2的歸一化函數(shù)；

β（S1），β（S2）——組件S1，S2對應(yīng)的包絡(luò)面積；

Φ（S1），Φ（S2）——組件S1，S2的整體對稱性；

Φ（β（S1）），Φ（β（S2））——組件S1，S2對應(yīng)的包絡(luò)盒整體對稱性。

1.4 基元樹的構(gòu)造

建筑物圖像通過基元提取，得到包絡(luò)盒表示圖，為了進一步剖析基元的空間分布結(jié)構(gòu)，需將包絡(luò)盒表示圖作為首個非聚合組件進行自上而下的拆分。拆分過程中，每步應(yīng)擇優(yōu)選擇拆分方式進行拆分，逐步拆分至產(chǎn)生基元或聚合組件，從而生成基元樹。然后，通過自下而上遍歷基元樹，可重構(gòu)出基元如何組合成組件以及組件如何組合成上一層組件，從而得到清晰的基元空間搭配關(guān)系。

對基元樹結(jié)點對應(yīng)的非聚合組件進行拆分時，有分割與嵌入兩種拆分方式，需要計算每種拆分方式的對稱性NS的數(shù)值，最終選擇對稱性NS的數(shù)值較大的拆分方式。如圖4所示，圖4（b）采用的方式是分割，其NS值為 0.34，圖 4（c）采用的方式是嵌入，其值為0.19。因分割方式的NS值大于嵌入方式的NS值，所以對圖4（a）中的組件采用分割方式進行拆分。

圖4 組件對稱性值比較

圖5 建筑物圖像的基元樹

大量實驗研究證實[12-14]，使用上述的基元樹構(gòu)造方法，最終可得到符合建筑物對稱性設(shè)計思想的基元樹，如圖5所示。

2 疑似偽造組件的檢測

對于包含偽造組件的這類圖像，按照基元空間分布信息，將其大致分成兩類，對稱性被破壞的圖像以及密集度被破壞的圖像。當(dāng)圖像基元樹結(jié)點對應(yīng)的非聚合組件與相鄰組件的對稱因子差異大于閾值WC，其中下標(biāo)C表示非聚合組件，稱該圖像為對稱性被破壞的圖像。當(dāng)圖像基元樹結(jié)點對應(yīng)的的聚合組件與其他聚合組件密集度差異大于閾值Wd，其中下標(biāo)d表示非聚合組件時，稱該圖像為密集度被破壞的圖像。

2.1 對稱因子檢測

圖像中的建筑物基元分布不均勻，不同類別的基元交錯排列，在視覺上不具備協(xié)調(diào)性，稱這類圖像為對稱性被破壞的圖像，如圖6（b）所示，圖中上面兩層窗戶區(qū)域的對稱性被破壞。

針對此類圖像，本文提出使用對稱因子進行檢測。在非聚合組件S中，如果S的一部分區(qū)域M經(jīng)過仿射變換T能夠與S的鏡像對稱區(qū)域M′重疊，則稱S中M與M′對稱，且S具有對稱性。定義對稱因子α，若M與M′完全重合，則α=1，表示M與M′完全對稱，則對稱因子α的定義為式（5），以計算部分重合區(qū)域的面積φ（M∩M′）與M、M′中面積最大的比值：

圖6 對稱性被破壞的圖像

通過計算圖像基元樹結(jié)點對應(yīng)的非聚合組件與其相鄰組件的對稱因子差異值Δα來快速定位疑似區(qū)域：

式中：αi——非聚合組件i的對稱因子值；

ai，left、ai，right——該 非 聚 合 組 件 的 相 鄰 組 件 對 稱因子值。

2.2 密集度檢測

當(dāng)圖像中的建筑物基元過于擁擠，密集的基元緊密排列會造成壓抑與混亂的感覺，稱此類圖像為密集度被破壞的圖像，如圖7（b）所示。

針對此類圖像，本文提出通過檢測圖像基元樹結(jié)點對應(yīng)的聚合組件與其他聚合組件密集度差異值來定位疑似區(qū)域。

由 1.1節(jié)的e、S和T的定義可知，e?S?T，S和T都包含著一些基元e。基元e的密集程度反映了基元的組合形式和緊湊程度。故本文定義聚合組件對應(yīng)的包絡(luò)盒面積密集度d1，數(shù)量密集度d2：

式中：μ1——基元樹的組件包絡(luò)盒的面積函數(shù)；

圖7 密集度被破壞的圖像

δ1——基元樹根結(jié)點對應(yīng)的組件包絡(luò)盒的面積函數(shù)；

∪e——基元樹根結(jié)點對應(yīng)的組件包含的所有基元。

式中：μ2——基元樹的組件包含的基元個數(shù)函數(shù)；

δ2——基元樹根結(jié)點對應(yīng)的組件包含的基元個數(shù)函數(shù)。

通過將d1、d2進行線性加權(quán)，得到聚合組件密集度d的表達式為

式中：d——聚合組件密集度；

w1、w2——加權(quán)系數(shù)，且w1+w2=1。加權(quán)系數(shù)

w1、w2綜合考慮基元的面積信息和數(shù)量信息。

2.3 疑似偽造組件定位算法

首先對建筑物圖像進行基元提取，然后將輸出的包絡(luò)盒圖像作為輸入信息，構(gòu)造基元樹，得到圖像對應(yīng)的基元樹表示，最后通過計算非聚合組件的對稱因子差異以及聚合組件的密集度差異，從而實現(xiàn)疑似區(qū)域的快速定位。

建筑物圖像偽造組件檢測算法如下：

輸入：圖像I

輸出：偽造區(qū)域檢測結(jié)果圖像Id

1）進行基元提取，得到圖像I對應(yīng)的包絡(luò)盒圖像Im。

2）以Im為根結(jié)點，拆分組件時，選擇對稱性值NS較大的拆分方式逐步拆分，構(gòu)造基元樹TI。

Ifi存在左相鄰非聚合組件

將可疑非聚合組件i壓入棧Ω

End If

Else Ifi存在右相鄰非聚合組件

將可疑非聚合組件i壓入棧Ω

End If

End If

Ifdk＞dj

將可疑聚合組件k壓入棧Ω

Else

將可疑聚合組件j壓入棧Ω

End If

End While

5）While棧 Ω 非空

①取棧頂元素c

②輸出棧頂元素代表的可疑圖像區(qū)域Id

③棧頂元素c出棧

End While

將輸入圖像經(jīng)過基元提取得到基元樹，在對基元樹進行檢索時，將可疑偽造組件壓入棧。檢索完成后，清空棧并輸出可疑偽造組件對應(yīng)的圖像區(qū)域。

3 實 驗

在Visual Studio C++10.0環(huán)境下來測試本文算法的檢測性能。為了體現(xiàn)該算法的優(yōu)越性，將偽造檢測性能較好的文獻[4]視為對照組。根據(jù)本課題組累積下來的經(jīng)驗值，選取聚合組件密集度中對稱因子閾值WC=0.17，密集度閾值Wd=0.46。同時，為了得到較好的檢測準(zhǔn)確度，在大型訓(xùn)練集（含有不同尺寸的200幅偽造建筑圖像）中對（基元面積加權(quán)w1，數(shù)量加權(quán)系數(shù)w2）的組合進行了優(yōu)化。借助接收機工作特征ROCs[15]來評估檢測精度。通過測試本文算法在（w1=0.1，w2=0.9）、（w1=0.3，w2=0.7）、（w1=0.5，w2=0.5）、（w1=0.7，w2=0.3）的 ROCs曲線來確定（w1，w2）的優(yōu)化值，結(jié)果見圖 8（a）。 從圖中可以看到，在（w1=0.3，w2=0.7）條件下，所提算法的檢測正確率最高。

圖 8 （w1，w2）的組合優(yōu)化結(jié)果

再對（w1=0.3，w2=0.7）進行左右劃分，測試了（w1=0.2，w2=0.8）、（w1=0.3，w2=0.7）、（w1=0.4，w2=0.6）3個條件的ROCs曲線，見圖8（b），從該圖中可知，所提算法在（w1=0.3，w2=0.7）條件下，仍然具有最高的檢測準(zhǔn)確度。因此，本文實驗數(shù)據(jù)采用（w1=0.3，w2=0.7）的組合條件。

圖9顯示了利用本文算法與文獻[4]技術(shù)進行圖像偽造組件檢測的結(jié)果，偽造圖像1、2在基元樹檢索過程中得到的可疑對稱因子差異值和可疑密集度差異值。從表中可知，表1為圖6、圖7中偽造圖像1中非聚合組件對稱因子差異值高于閾值，偽造圖像2中存在聚合組件密集度差異值高于閾值，從而定位可疑偽造圖像區(qū)域，見圖 9（a）、圖 9（f）。而利用文獻[4]算法對建筑物偽造組件進行檢測，使用SIFT特征點進行檢測，需源圖像與偽造圖像都存在，且會產(chǎn)生大量錯誤匹配點，使其檢測準(zhǔn)確度較低，存在誤配現(xiàn)象，見圖 9（g）。

圖9 各算法的偽造檢測結(jié)果

表1 本文算法的可疑對稱因子差異值和可疑密集度差異值計算

表2 本文算法與文獻[4，7，14]算法的比較

為了進一步說明本文算法在計算效率方面的改善程度，把文獻[4，7，14]特征與本文算法進行了比較。實驗圖像大小為 260×390。文獻[4]、文獻[7]、文獻[14]算法分別采用 SIFT、DCT、SURF 特征，特征維數(shù)分別為128維、64維、64維。本文算法用基元樹表示圖像，有別于傳統(tǒng)的圖像特征提取方法，SIFT、SURF算法需進行特征點的匹配，濾除錯誤匹配點等過程，檢測效率不高，而基元樹表示法無須進行匹配，僅需檢索結(jié)點的密集度以及對稱因子特征即可快速定位疑似偽造區(qū)域，故提高了檢測效率。從表2可以明顯地看出，本文提出的算法檢測時間少，檢測效率高。

4 結(jié)束語

為了解決當(dāng)前圖像偽造檢測技術(shù)因通過將圖像的每個區(qū)域塊特征或點特征進行相似性匹配，以完成檢測而導(dǎo)致耗時冗長，內(nèi)存空間消耗大，且準(zhǔn)確度不佳等不足。本文提出了基于基元樹的建筑物圖像偽造組件檢測算法。本文通過基元樹表示圖像，檢測非聚合組件對稱性因子差異值和聚合組件密集度差異值，從而快速定位疑似區(qū)域。實驗結(jié)果表明，該算法對建筑物圖像能達到比較理想的檢測效果，準(zhǔn)確率高。

建筑物圖像偽造組件檢測方法對于圖像中以二維形式呈現(xiàn)的建筑物檢測結(jié)果準(zhǔn)確。但檢測三維建筑物圖像時，會出現(xiàn)建筑基元提取困難的情況，擴展本文算法使其可以處理圖像中以三維形式呈現(xiàn)的建筑物偽造檢測是下一步研究的重點。

[1] 李滿滿，杜振龍，沈鋼綱.基于奇異值加權(quán)的圖像復(fù)制粘貼偽造盲檢測[J].計算機工程與設(shè)計，2012，32（12）：4125-4129.

[2] Shivakumar B L，Baboo L D S S.Detection of region duplication forgery in digital images using SURF[J].IJCSI International Journal of Computer Science，2011，8（4）：199-205.

[3] 杜振龍，楊凡，李曉麗.利用SIFT特征的非對稱匹配圖像拼接檢測[J].中國圖象圖形學(xué)報，2013，18（4）：442-449.

[4] Amerini I， Ballan L， Caldelli R.A SIFT-based forensic method for copy-move attack detection and transformation on recovery[J].IEEE Trans on Information Forensics and Security，2011，6（3）：1099-1110.

[5] Cao Y，Gao T，F(xiàn)an L.A robust detection algorithm for region duplication in digital images[J].International Journal of Digital Content Technology and its Applications，2011，5（6）：95-103.

[6] Kang X，Wei S.Identifying tampered regions using singular value decomposition in digital image forensics[C]∥ProceedingsofInternationalConference on Computer Science and Software Engineering.Washington DC：IEEE Compute Society，2012，35（13）：926-930.

[7] HuangY， LuW， SunW.ImprovedDCT-based detection of copy-move forgery in images[J].Forensic Science International，2011，206（13）：178-184.

[8] Martinovic A.A three-layered approach to facade parsing[J].Computer Vision-ECCV，2012，32（8）：416-429.

[9] Teboul O.Segmentation of building facades using proced ural shape priors[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition （CVPR），San Diego，2010，12（11）：3105-3112.

[10]Fan L B， Musialski P， Liu L G.Structure completion for gird layouts[J].ACM Transactions on Graphics，2014，33（6）：1-10.

[11]Zhang H， Xu K， Jiang.Layered analysis of irregular facades via symmetry maximization[J].ACM Transactions on Graphics，2013，32（4）：1-10.

[12]Hu S M， Zhang F， Wang M， et al.a patch-based image representation for interactive library-driven image editing[J].ACM Transactions on Graphics，2013，32（6）：2504-2507.

[13]Lin J， Cohen O D， Zhang H， et al.Structure-preserving retargeting of irregular 3D architecture[J].Journal of Computer-aided Design&Computer Graphics，2012，30（6）：61-64.

[14]Bay H， Ess A， Tuytelaars T.SURF： speed up robust features[J].Computer Vision and Image Understanding，2013，11（3）：346-359.

[15]Kang X，Li Y，Qu Z，et al.Enhancing source camera identification performance with a camera reference phase sensor pattern noise[J].Information Forensics and Security，2012，7（2）：393-402.