基元树建筑物图像伪造组件检测算法

吴冰洁，杜振龙

（南京工业大学电子与信息工程学院，江苏 南京 211800）

0 引 言

随着数字获取技术的发展，利用摄像机、数码相机、智能手机等设备能方便、快捷地获取生活、旅游等方面的图像资料。这些数字媒体文档为丰富现代人们的精神生活提供了影像物料，其中，以地标建筑、历史建筑物为背景的生活图像占了相当大的比重。然而，不断发展的图像编辑技术为人物生活照的编辑和合成提供了强有力的支持，使得普通用户可以容易地更改图像中的建筑物图像而不被察觉，从而产生充斥互联网的“移花接木”图像。为了保证图像内容的真实性，可通过鉴定图像中的建筑物部分是否被修改来判断图像真伪。因此，建筑物图像的检测具有一定的现实需求和意义。同时，李满满等[1]指出，图像合成处理后的伪造图像是难以检测出来的。

众所周知，建筑物图像的主要组成部分是窗户、阳台等基本建筑构成单元，即建筑物基元。建筑物图像变形是改变一个或多个基元数量或位置信息，本质是改变基元之间的空间关系。通过将基元进行新的空间组合，构造出新基元组件，整合多个基元组件伪造出“莫须有”的图像。由于建筑物图像在三维重建中的重要性，对建筑物图像的研究已经成为近年来的热点。而传统的逐像素[2-4]或逐块的检索方法[5-7]通过将图像分块，提取图像块或像素点特征，进行相关性检测，从而搜寻到匹配区域，但忽略了图像内容上的语义联系以及空间结构特征，且计算量大，使得这些图像特征检测方法难以鉴别图像真伪。如Shivakumar等[2]提出使用基于SURF特征的检测算法，联合K-d树与SURF特征，来实现多维特征匹配，以检测伪造区域，实验结果显示其算法具有较好的鲁棒性。但该算法在图像全局属性表达方面较弱，影响了检测结果的准确性。Amerini等[4]提出使用SIFT特征提取图像特征点与特征向量，可调整特征匹配时仿射变换参数从而减少特征点对的误配。但该方法计算量较大，匹配效率低。Cao等[5]提出使用离散余弦变换DCT表示图像块单元特征，通过与阈值进行比较筛选出疑似伪造图像块。但该方法忽略了图像块之间的语义联系与空间关系，对经过加噪与模糊处理的伪造图像块检测效率较差。

对此，研究人员开发了新的针对建筑图像伪造检测技术。Martinovic等[8]提出使用递归神经网络（RNN）与马尔科夫随机场（MRF）构成的三层模型，并从其语义上提取了建筑物基元；但该方法在使用RNN进行训练时，需要先将图像进行过度分割，生成许多块区域，这将占据大量内存空间。Teboul等[9]提出使用自定义的建筑结构规则，结合监督分类与随机过程方法分割出建筑物基元。但是该方法需要对基元形状进行过程学习，训练样本的差异会影响最终基元检测结果。Fan等[10]提出通过将实验图像可见部分的建筑物基元表示成包络盒，即刚好容纳基元区域的外接矩形，并结合图像数据库训练得到的建筑物布局候选项，补齐实验图像未知部分基元，从而构造出完整的建筑物图像。但是该方法需要依赖图像数据库，数据库中不完备的图像种类将导致可能无法产生布局候选项，继而降低了其检测准确度。

为了解决上述难题，本文提出一种图像基元树表示法，即对建筑物图像进行基元提取，根据建筑物对称性特点[11]生成基元树，通过检索基元树结点对应的非聚合组件的对称因子和聚合组件的密集度差异值，快速定位疑似伪造组件，并测试了本文算法的检测速度与准确度。

1 建筑物图像的基元树表示

首先对建筑物图像进行基元提取，再依据对称性原则，构造出基元树。

1.1 基元提取

建筑物由于其人工构建特性，具有基元重复性和规整性。利用这些人为特性，将建筑物图像中重复构建的门、窗等基元作标记，然后采用包络盒替代细节复杂的基元区域，从而提取出基元，得到清晰的基元空间分布图。

输入一幅建筑物图像，交互式地将门、窗、阳台等建筑物外表形状规整的元素作为基元予以标记，如图1（b）所示。定义基元的集合表示，设e={门|窗|阳台|…}表示建筑物图像的基元。由于基元类型不同，故定义了标签集合L={l1|l2|l3|…}代表不同类别的基元，其中，li是标识不同类别基元的标签，i=1，2，3，…，n。空间分布不同的多种类别基元可以组成空间结构不同的基元组件，故基元组件S为基元e的并集，定义S=∪e为由基元e组装成的组件。不同结构的组件通过不同的拼接方式可以构造出多样基元树，故基元树为组件的并集，定义T=∪S是由组件构成的基元树。

在建筑物图像中，由于个别基元边缘模糊以及基元之间的拍摄光强不一致等外界因素，使得同类基元区域各方面呈现差异。为了消除这些干扰因素，本文引入包络盒，利用不同颜色的包络盒来替代表示不同类别的基元，忽略非基元区域，将各类基元进行提取，从而得到空间结构明朗的包络盒表示图，见图 1（c）。

设包络盒 bos=（l，x，h，left，right，parent）， 式中l表示基元类别，x、h分别表示包络盒宽度和高度，（left，right，parent）∈N3代表左右基元及所属组件的信息。

1.2 组件拆分

图像经过基元提取后得到的包络盒表示图，需以此为跟结点，进行组件拆分操作，从而构造基元树。

根据建筑物对称特性，可以发现在建筑物图像中，基元之间的空间关系是聚合或者嵌入。因此，根据不同的空间关系，对组件进行不同的拆分操作，从而简化组件的基元组合关系。

图1 基元提取

图2 组件分割操作

聚合，即同一类基元聚集在某一区域，且该区域不包含其他类别的基元。若沿着中轴线把该区域分成空间相等的两个部分，则每个部分所包含的基元数目是相等的。当组件中包含聚合组件时，为了保存聚合区域的对称性，采用分割的方式将聚合组件从原组件中分离出来，从而得到两个新组件，如图2所示。

嵌入，即不同类别基元在空间上间隔地分布，通常是在聚合组件中插入其他类别的基元，从而导致组件中的基元类别不统一，不同的基元错落排列，组件不具备对称性，则称该组件为非聚合组件。为了保存部分聚合区域的结构完整性，而采用嵌入的方式，使用聚合类别的基元虚拟取代非本类基元，并将非本类基元从该区域中剔除，如图3所示。

图3 组件嵌入操作

1.3 对称性计算

对组件进行拆分操作时，由于存在聚合与嵌入两种选择，故提出对两种选择分别进行对称性计算，选取对称性大者为拆分选择。

在构造基元树过程中，需要对结点所代表的组件进行对称性计算。由于基元树的组成单元为基元或者组件，故本文定义了基元或组件对称性。

定义基元对称性：提取基元时，为得到清晰的基元空间分布，使用包络盒替代基元进行表示。为了抽取本质特征，应将包络盒表示法应用于对称性计算。假设A为基元对应的包络盒，将其置于二维直角坐标系上，使其水平范围为[0，λ]，即宽x∈[0，λ]，高为h，PA（x）定义为与A关于位于坐标x的垂直直线做镜像对称A′的重复面积。故基元对称性PA（x）的计算模型为

定义组件对称性：由于组件中包含多个基元，所以对称性关系包括基元自身对称性以及基元之间对称性。基元自身对称性使用上述的基元对称性模型进行计算。 基元之间对称性，则使用模型PA1，A2（x）表示。两个空间位置相邻的基元A1、A2可能属于同一类别或者不同类别。A1、A2类别相同时，PA1，A2（x）代表基元A1与基元A2关于横坐标为x垂直直线做镜像对称A2′的重复面积。A1、A2类别不同时，则对应的包络盒面积大小不同，不存在对称关系，PA1，A2（x）值为0。综上所述，则组件对称性PS（x）计算模型为

式中S表示组件。

式中：Φ（S）——组件整体对称性；

[-λS/2，+λS/2]——组件对应包络盒的宽度；

g（x）——高斯权重函数。

在选择组件拆分方式时，需计算拆分后的两个子组件或者基元的对称性之和，由于不同类别基元对应的包络盒面积大小不同，为了对不同面积的基元进行统一衡量并求和，本文对对称性计算进行归一化操作。设β（S）为组件S对应的包络面积，S1，S2为拆分后的两个子组件或者基元。则定义归一化函数NS（S1，S2）为

式中：S1，S2——拆分后的两个子组件或者基元；

NS（S1，S2）——S1，S2的归一化函数；

β（S1），β（S2）——组件S1，S2对应的包络面积；

Φ（S1），Φ（S2）——组件S1，S2的整体对称性；

Φ（β（S1）），Φ（β（S2））——组件S1，S2对应的包络盒整体对称性。

1.4 基元树的构造

建筑物图像通过基元提取，得到包络盒表示图，为了进一步剖析基元的空间分布结构，需将包络盒表示图作为首个非聚合组件进行自上而下的拆分。拆分过程中，每步应择优选择拆分方式进行拆分，逐步拆分至产生基元或聚合组件，从而生成基元树。然后，通过自下而上遍历基元树，可重构出基元如何组合成组件以及组件如何组合成上一层组件，从而得到清晰的基元空间搭配关系。

对基元树结点对应的非聚合组件进行拆分时，有分割与嵌入两种拆分方式，需要计算每种拆分方式的对称性NS的数值，最终选择对称性NS的数值较大的拆分方式。如图4所示，图4（b）采用的方式是分割，其NS值为 0.34，图 4（c）采用的方式是嵌入，其值为0.19。因分割方式的NS值大于嵌入方式的NS值，所以对图4（a）中的组件采用分割方式进行拆分。

图4 组件对称性值比较

图5 建筑物图像的基元树

大量实验研究证实[12-14]，使用上述的基元树构造方法，最终可得到符合建筑物对称性设计思想的基元树，如图5所示。

2 疑似伪造组件的检测

对于包含伪造组件的这类图像，按照基元空间分布信息，将其大致分成两类，对称性被破坏的图像以及密集度被破坏的图像。当图像基元树结点对应的非聚合组件与相邻组件的对称因子差异大于阈值WC，其中下标C表示非聚合组件，称该图像为对称性被破坏的图像。当图像基元树结点对应的的聚合组件与其他聚合组件密集度差异大于阈值Wd，其中下标d表示非聚合组件时，称该图像为密集度被破坏的图像。

2.1 对称因子检测

图像中的建筑物基元分布不均匀，不同类别的基元交错排列，在视觉上不具备协调性，称这类图像为对称性被破坏的图像，如图6（b）所示，图中上面两层窗户区域的对称性被破坏。

针对此类图像，本文提出使用对称因子进行检测。在非聚合组件S中，如果S的一部分区域M经过仿射变换T能够与S的镜像对称区域M′重叠，则称S中M与M′对称，且S具有对称性。定义对称因子α，若M与M′完全重合，则α=1，表示M与M′完全对称，则对称因子α的定义为式（5），以计算部分重合区域的面积φ（M∩M′）与M、M′中面积最大的比值：

图6 对称性被破坏的图像

通过计算图像基元树结点对应的非聚合组件与其相邻组件的对称因子差异值Δα来快速定位疑似区域：

式中：αi——非聚合组件i的对称因子值；

ai，left、ai，right——该 非 聚 合 组 件 的 相 邻 组 件 对 称因子值。

2.2 密集度检测

当图像中的建筑物基元过于拥挤，密集的基元紧密排列会造成压抑与混乱的感觉，称此类图像为密集度被破坏的图像，如图7（b）所示。

针对此类图像，本文提出通过检测图像基元树结点对应的聚合组件与其他聚合组件密集度差异值来定位疑似区域。

由 1.1节的e、S和T的定义可知，e⊆S⊆T，S和T都包含着一些基元e。基元e的密集程度反映了基元的组合形式和紧凑程度。故本文定义聚合组件对应的包络盒面积密集度d1，数量密集度d2：

式中：μ1——基元树的组件包络盒的面积函数；

图7 密集度被破坏的图像

δ1——基元树根结点对应的组件包络盒的面积函数；

∪e——基元树根结点对应的组件包含的所有基元。

式中：μ2——基元树的组件包含的基元个数函数；

δ2——基元树根结点对应的组件包含的基元个数函数。

通过将d1、d2进行线性加权，得到聚合组件密集度d的表达式为

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

w1、w2——加权系数，且w1+w2=1。加权系数

w1、w2综合考虑基元的面积信息和数量信息。

2.3 疑似伪造组件定位算法

首先对建筑物图像进行基元提取，然后将输出的包络盒图像作为输入信息，构造基元树，得到图像对应的基元树表示，最后通过计算非聚合组件的对称因子差异以及聚合组件的密集度差异，从而实现疑似区域的快速定位。

建筑物图像伪造组件检测算法如下：

输入：图像I

输出：伪造区域检测结果图像Id

1）进行基元提取，得到图像I对应的包络盒图像Im。

2）以Im为根结点，拆分组件时，选择对称性值NS较大的拆分方式逐步拆分，构造基元树TI。

Ifi存在左相邻非聚合组件

将可疑非聚合组件i压入栈Ω

End If

Else Ifi存在右相邻非聚合组件

将可疑非聚合组件i压入栈Ω

End If

End If

Ifdk＞dj

将可疑聚合组件k压入栈Ω

Else

将可疑聚合组件j压入栈Ω

End If

End While

5）While栈 Ω 非空

①取栈顶元素c

②输出栈顶元素代表的可疑图像区域Id

③栈顶元素c出栈

End While

将输入图像经过基元提取得到基元树，在对基元树进行检索时，将可疑伪造组件压入栈。检索完成后，清空栈并输出可疑伪造组件对应的图像区域。

3 实 验

在Visual Studio C++10.0环境下来测试本文算法的检测性能。为了体现该算法的优越性，将伪造检测性能较好的文献[4]视为对照组。根据本课题组累积下来的经验值，选取聚合组件密集度中对称因子阈值WC=0.17，密集度阈值Wd=0.46。同时，为了得到较好的检测准确度，在大型训练集（含有不同尺寸的200幅伪造建筑图像）中对（基元面积加权w1，数量加权系数w2）的组合进行了优化。借助接收机工作特征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）的优化值，结果见图 8（a）。 从图中可以看到，在（w1=0.3，w2=0.7）条件下，所提算法的检测正确率最高。

图 8 （w1，w2）的组合优化结果

再对（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）条件下，仍然具有最高的检测准确度。因此，本文实验数据采用（w1=0.3，w2=0.7）的组合条件。

图9显示了利用本文算法与文献[4]技术进行图像伪造组件检测的结果，伪造图像1、2在基元树检索过程中得到的可疑对称因子差异值和可疑密集度差异值。从表中可知，表1为图6、图7中伪造图像1中非聚合组件对称因子差异值高于阈值，伪造图像2中存在聚合组件密集度差异值高于阈值，从而定位可疑伪造图像区域，见图 9（a）、图 9（f）。而利用文献[4]算法对建筑物伪造组件进行检测，使用SIFT特征点进行检测，需源图像与伪造图像都存在，且会产生大量错误匹配点，使其检测准确度较低，存在误配现象，见图 9（g）。

图9 各算法的伪造检测结果

表1 本文算法的可疑对称因子差异值和可疑密集度差异值计算

表2 本文算法与文献[4，7，14]算法的比较

为了进一步说明本文算法在计算效率方面的改善程度，把文献[4，7，14]特征与本文算法进行了比较。实验图像大小为 260×390。文献[4]、文献[7]、文献[14]算法分别采用 SIFT、DCT、SURF 特征，特征维数分别为128维、64维、64维。本文算法用基元树表示图像，有别于传统的图像特征提取方法，SIFT、SURF算法需进行特征点的匹配，滤除错误匹配点等过程，检测效率不高，而基元树表示法无须进行匹配，仅需检索结点的密集度以及对称因子特征即可快速定位疑似伪造区域，故提高了检测效率。从表2可以明显地看出，本文提出的算法检测时间少，检测效率高。

4 结束语

为了解决当前图像伪造检测技术因通过将图像的每个区域块特征或点特征进行相似性匹配，以完成检测而导致耗时冗长，内存空间消耗大，且准确度不佳等不足。本文提出了基于基元树的建筑物图像伪造组件检测算法。本文通过基元树表示图像，检测非聚合组件对称性因子差异值和聚合组件密集度差异值，从而快速定位疑似区域。实验结果表明，该算法对建筑物图像能达到比较理想的检测效果，准确率高。

建筑物图像伪造组件检测方法对于图像中以二维形式呈现的建筑物检测结果准确。但检测三维建筑物图像时，会出现建筑基元提取困难的情况，扩展本文算法使其可以处理图像中以三维形式呈现的建筑物伪造检测是下一步研究的重点。

[1] 李满满，杜振龙，沈钢纲.基于奇异值加权的图像复制粘贴伪造盲检测[J].计算机工程与设计，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].中国图象图形学报，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，Fan 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.