基于K-D树的润饰篡改图像盲鉴别算法

陈 佳，姬凤英

（1.武汉纺织大学 数学与计算机学院，湖北 武汉 430073；2.湖北省档案局，湖北 武汉 430071）

基于K-D树的润饰篡改图像盲鉴别算法

陈 佳1，姬凤英2

（1.武汉纺织大学 数学与计算机学院，湖北 武汉 430073；2.湖北省档案局，湖北 武汉 430071）

文章针对修复刷的润饰原理提出了基于K-D树的修复刷篡改图像盲鉴别算法，当修复刷被应用于图像时，采用K-D树以及层次聚类算法精确识别图像是否经过篡改，并找出篡改位置。实验表明，准确度高。

图像鉴别；复制粘贴篡改；K-D树

档案资料的保存形式由纸介保存发展到电子化保存是科技发展的必然，“数字档案馆”的概念由此而生，其中，图像档案是数字化档案很重要的一个组成部分，包括由数码技术转换的照片、图形、图片、摄像、图表等。同时，随着信息技术的高速发展，各种数字图像编辑软件使得图像处理更为便捷，很多软件采用了各种信息处理技术，比如修复刷等，通过这些技术对图像进行润饰或者改变。改变后的图像往往从肉眼上很难看出痕迹，甚至专家也不能鉴别真伪，但实际应用中却需要原始图像，因此需要对图像的内容进行真伪鉴别。目前很多软件采用的润饰方法不难被检测到其修改的区域，比如康丽[1]直接复制从而组成图像的某部分，陈海鹏等[2]利用光照不一致现象检测复制部分，王波[3]利用的颜色不一致现象以及Cui等[4]和曹刚等[5]所针对的锐化操作。在各种技术中，修复刷能够在图像的边界处平稳过渡，保持了各像素点的特征，因而颜色和源区域具备稳健性。

本文针对修复刷的润饰原理提出了基于K-D树的修复刷篡改图像盲鉴别算法，当修复刷应用于图像时，图像的像素会发生改变，利用其存在的精确的衍生信息来识别图像的润饰修改，如果图像的大区域被修改，该方法则以高压缩率工作，基于这种思想，人们可以用K-D树的修复刷篡改图像盲鉴别算法进行鉴别。

1 国内外研究现状

保证档案的原始性、真实性是档案管理的核心部分，只有这样才能保证其权威性从而被社会广泛利用。目前，在信息化社会中，数字档案同样需要具备这样的特性。因此，在数字化档案开发和利用中，如何对数字档案进行真伪识别，以及如何保护数字化档案的版权和对其进行原始性鉴别，都是开发和使用中至关重要的步骤。而随着信息化技术的高速发展，图像处理技术的日益改进，很多图像处理软件，如Photoshop等，很容易对数字图像进行修改和编辑。在带来各种益处的同时，很多不法分子也利用这些技术对数字档案、司法证据等大量制造伪造图像。因此，国内外研究学者对其进行大量研究。

著名的Dartmouth学院、Binghamton大学、Columbia大学和Polytechnic大学等都成立了专门的数字媒体取证研究小组。美国Dartmouth大学的Hany Farid教授领导的科研队伍用对图像进行多尺度小波分解和高阶统计建模的方法进行分析，对数码照片图像、扫描图像和计算机生成图像进行盲检测。这种小波分析方法利用不同来源的数字图像上的各种不一致性进行图像的真伪鉴别，开启了这种不一致性鉴别技术的探索之路，也成了档案图像鉴别技术的主流和主要研究方向。然而，这种方法缺乏实际应用，主要还处在理论基础阶段，需要建立完备的技术路线。在档案图像的众多篡改技术中，修复刷技术最具隐蔽性，其能够在图像边缘处平稳过渡，因此很难从图像的结构信息以及颜色的跳跃来进行判断，一般情况下很难辨别，但是由于被修护的图层和本身的图层色数有一定的差距，基于这种思想，本文提出了改进的检测算法—基于K-D树的润饰篡改图像盲鉴别算法。

2 基于K-D树的润饰篡改图像盲鉴别算法

2.1 图像的块配对（找出用修复刷修复过的地方）

首先，对待检测的图像，要确定是否使用过修复刷，也就是找出修复刷使用过的位置。具体算法如下所示。

输入：待检测图像P；

输出：若干匹配块。

第1步，将待检测图像P分成若干个小块p1，p2，…，pn，其中每块大小为N×N；

第2步，依次将p1，p2，…，pn的像素块插入到K-D树中；

第3步，采用广度遍历方法在K-D树中查找具有近似值小块。

该算法首先要确定所划分小块的大小，如果划得太大或太小，都不能准确计算使用过修复刷的区域值。经过实验，确定N值的取值范围为[10,20]的像素之间。另外，该算法所涉及的一个重要参数即匹配的设定值FMAX，太大或太小都找不到正确的匹配对。同样，这里采用实验法。实验发现，对于非压缩图像和压缩图像，该值取值不同，主要是由于修复刷所采用的过滤器对压缩图像的像素值产生了噪声。因此，对于非压缩图像，FMAX可以为较低值或者较高值，而对于压缩图像，FMAX需为较大值。对于所采用的数字档案图像，其值设定为6—10。

2.2 篡改区域定位

通过相似值找到的匹配块对中，由于有的区域被修复刷修饰过，造成源区域与邻近区域其他块误匹配。因此在得到匹配对后，还需要进行误匹配消除，再精确定位篡改区域。

本文采用分裂的层次聚类的方法对这些匹配块进行聚类，通过得到的类的大小来判断所包含的匹配块是否为误匹配块。这里将所需匹配的匹配块p1，p2，…，pn作为输入向量[n1,n2,…,nn]，算法描述如下所示。

输入：向量[n1,n2,…,nn]；

输出：k个簇，将小簇消除。

Step1. 将输入的向量[n1,n2,…,nn]看作一个初始簇；

Step2. For(i=1;i!=k;i++)

{计算所有簇的直径并找出最大直径簇；

计算每个点与其他簇的平均相异度；

将相异度最大的点分出作为新簇；}

Step3. END

对于此算法，首先要考虑参数k的大小，即分为几个簇合适。实验表明，k的大小随输入向量大小的变动而变动，但当簇中的向量数（即匹配块数）小于某个值时，即可停止分裂，并认为该小簇中的匹配对是误匹配对。通过实验发现，当簇中的匹配块个数为6—10时，即可认为该簇为小簇并确定该簇中的块为误匹配块。

删除误匹配区域后，就需要确定篡改的区域。实际上，对于修复刷操作的篡改，虽然图像边界能够平稳过渡，但会使得相邻区域之间的梯度长度具有强相关性，因此，将区域矩阵和其相邻的矩阵做差值得到绝对值矩阵，该绝对值矩阵会有多个相邻的零。换句话说，当存在多个差值的零分量连通集合时，这些块即为篡改块。通过实验发现，当该集合大小大于3时，该块为篡改块。

3 实验结果

本文采用的数据集为人的脸部皮肤，该数据集通过修复刷进行修饰，并采用K-D树算法进行检测。算法运行了一个大小为15的块，用至少5个相同转换的块对寻找区域对。实验结果显示，修复刷应用的大部分区域被检测并且没有误报。在这两种情况下，表面看着真实性的图像有许多被润色的区域。如图1所示，这些初步的实验表明了该方法对检测修复刷的使用是有效的。图1（a）为图像未处理前，图1（b）是图像是处理后，图1（c）是应用K-D树查找的经过修复后的内容。

图1 算法对一个人面部图像的运行结果

4 结语

本文针对修复刷篡改问题，采用K-D树及层次聚类法定位法，精确定位被篡改的区域，相对传统算法提高了准确性。通过实验证明，该方法对压缩图像和非压缩图像都能有效地找出即使边界平稳过渡的篡改区域，对我国的数字档案的真伪识别有一定贡献。

[1]康丽.数字图像内容人为篡改检测[D].重庆：西南大学，2011.

[2]陈海鹏，申铉京，吕颖达，等.基于Lambert光照模型的图像真伪盲鉴别算法[J].计算机研究与发展，2011（7）：1237-1245.

[3]王波.利用成像引入特征的数字图像被动盲取证研究[D].大连：大连理工大学，2010.

[4]GUI Z，LIU Y.An image sharpening algorithm based on fuzzy logic[J].Optik-International Journal for Light and Electron Optics，2011（8）：697-702.

[5]曹刚，赵耀，倪蓉蓉.一种基于振铃效应分析的图像锐化取证算法[J].计算机研究与发展，2009（S1）：217-220.

[6]杜加玉.数字图像取证中的模糊与重采样检测研究[D].大连：大连理工大学，2010.

Blind identification for image authenticity based on K-D tree

Chen Jia1, Ji Fengying2
(1.Mathematics and Computer Science School, Wuhan Textile University, Wuhan 430073, China;2.Hubei Provincial Archives Bureau, Wuhan 430071, China)

In view of the retouch principle of repair brush, this paper proposes image blind identification algorithm of brush tamper based on K-D tree, which uses K-D tree and hierarchical clustering algorithm to accurately identify whether the image has been tampered with,and find out the tampering position. Experiments show that the accuracy is high.

identification for image authenticity; copy-move forgery; K-D tree

国家档案局科技计划项目；项目编号：2014-X-68。

陈佳（1982— ），女，湖北武汉人，副教授，博士；研究方向：图像处理与模式识别。