基于超像素和游程直方图的对比度修改检测算法

高铁杠 杨 亮 宣 妍 佟 静



基于超像素和游程直方图的对比度修改检测算法

高铁杠 杨 亮*宣 妍 佟 静

(南开大学软件学院 天津 300071)

该文提出一种基于超像素和游程直方图的图像对比度修改检测取证算法。算法首先对图像进行超像素分割，并提取每个分割区域的游程直方图特征值，然后将不同方向的特征值进行融合，并进行归一化处理；再计算处理后的特征值数值突变量；最后将区域的数值突变量用支持向量机(SVM)进行分类识别。实验结果表明，和现有的一些算法相比，该文提出的算法计算复杂度低，在多种不同的测试数据库上都具有良好的识别性能。此外，在区域篡改检测实验中，该算法不仅可以定位出篡改区域，还能准确地描绘出篡改区域的轮廓形状。

图像处理；对比度修改；超像素；游程直方图；数值突变量；支持向量机(SVM)

1 引言

随着信息技术的发展，许多图像编辑软件得到了广泛普及与应用，使得对图像的操作变得更加得心应手，一些非法篡改的图像进而也得以在互联网迅速传播，由于人们无法对经过篡改的图像从视觉感官上进行分辨，因此，这必然会带来涉及到法律取证、图像媒体版权、个人隐私保护等相关问题，所以如何鉴别图像的真伪性成为了当前最热门的研究课题之一[1]。

图像真伪鉴别即鉴别图像是原始的，还是经过人为篡改的。常见的图像篡改包括拼接、压缩、滤波和对比度修改等操作。目前，鉴别图像真伪的手段主要分为主动认证和被动认证两种方式[2,3]。主动认证即运用数字水印或数字指纹技术提前在原始图像中隐秘地写入验证信息，通过验证写入的信息即可鉴别图像真伪性；被动认证是指在图像没有任何预处理的情况下直接对图像进行鉴别，通过检测篡改操作可能留下的统计特征和痕迹达到判断真伪的目的。当前大部分图像真伪鉴别操作都是被动认证的。

对比度修改是一种最常见的图像篡改手段，可以分为全局对比度修改和局部对比度修改两种方式[4]。局部对比度修改操作主要用于不同图像间进行拼接和复制粘贴操作后，调整拼接粘贴块的对比度使得篡改区域色度与原始图像色度相近，从而达到以假乱真的目的。全局对比度修改是指篡改者对整张图像进行对比度修改操作，强化或者弱化该图像内容，从而影响人们对图像的视觉感受，无法对图像内容进行客观判断。对比度修改的实质是对图像的像素值进行转换，将原始图像的像素值转换成其他数值，经过转换后获得的图像即为对比度修改后的图像。最常见的修改方法包括直方图拉伸，伽马调整等[5]。由于对比度修改只调整图像色度，不改变图像内容和尺寸，所以无法直接进行观察分辨。由于这个原因，使得经过对比度修改的区域与原始图像非常相近，给图像的篡改的检测工作带来了极大困难。对比度修改检测即为解决这个问题提供了途径，利用对比度修改后留下的异常数据，对拼接图像进行检测。这对图像篡改检测具有非常重要的实用价值。

无论使用何种对比度修改方法都会在图像中留下异样的统计规律，例如直方图中的波峰波谷效应等[6]。利用对比度修改后留下的统计特征的变化，人们提出了多种识别对比度修改的方法。其中，Stamm等人[7]将图像直方图进行傅里叶变换，通过计算直方图在频域的高频分量鉴别图像是否经过对比度修改。Alessia等人[8]利用2维共生矩阵，计算矩阵标准差然后进行训练分类，从而达到识别对比度修改的目的。Lin等人[9]分析并利用了RGB 3个不同通道高频分量之间关系进行对比度修改检测。Cao等人[10]通过计算图像直方图波谷数量检测图像是否经过对比度修改，该算法首先计算图像直方图；再判断直方图波谷位置，判断依据为该位置数值是否为0，并且相邻位置数值是否大于,为自定义阈值；最后计算图像直方图波谷数量，如果波谷数量大于自定义阈值则可认为该检测图像经过对比度修改。虽然相关文献中提出的算法识别率不断提高，但算法复杂度也随之提高，并且算法对于小尺寸图像检测以及图像对比度修改区域定位效果较差。而且现有的图像区域篡改识别算法多数基于重叠分块，只能简单识别出篡改区域位置，无法准确描述出篡改区域轮廓，形状，范围。本文使用超像素分割[11]，将图像按照一定特征相似性划分为多个不相交的有意义的连通区域，而后对每个区域单独进行识别，能有效提取图像局部区域轮廓，提高图像真伪鉴别准确率。

本文提出了一种简单且高效的基于超像素分割和游程直方图特征融合的对比度修改检测算法。算法首先对图像进行超像素分割，并对每个分割区域提取游程直方图特征值，然后将不同方向的游程直方图特征值进行融合，并进行归一化处理，再计算处理后特征值数值突变量；最后将区域的数值突变量用支持向量机(SVM)进行分类识别。实验结果证明，和现有的一些算法相比，提出的方法计算复杂度低，在多种不同的测试数据库上都具有良好的识别性能，而且还能较准确识别出篡改区域的轮廓形状。

2 基于超像素和游程直方图的对比度修改检测方法

2.1 基于超像素的图像分割

超像素分割是指将图像分割为多个子区域(即超像素)的过程。超像素是由一系列位置相邻且有相似颜色、纹理、亮度等特征的像素点组成的区域。这些区域大多保留了图像纹理内容等有效信息，且不会破坏图像中物体的边界信息。近年来超像素技术被广泛应用，其生成方式也随即成为研究热点。

在图像复制粘贴篡改操作中粘贴区域内容多数包含完整物体并与周围区域形成明显对比，使用超像素分割可以较为准确地将篡改区域分割成一个或多个统一整体，有利于提高后续的鉴别操作准确度。

SLIC(Simple Linear Iterative Clustering)算法是文献[12]提出的一种简单线性迭代聚类超像素分割算法，该算法先将图像转换为CIELAB色彩空间，然后在图像中选取个聚类中心点，将聚类中心点附近×范围内的像素点聚合至聚类中心点，此时的聚类中心点即为超像素的中心点，其中表示像素数量/超像素数目。然后在中心点附近范围内进行加权距离测量，根据距离值不断更新临近像素点的聚合中心，并重新计算聚类中心点的位置，当中心点的位置不再改变时，停止迭代。为降低时间复杂度，SLIC算法在范围内进行低维向量的k-means聚类。

SLIC算法能将图像进行高质量分割，本文的图像分割基础即采用SLIC算法生成的超像素。

2.2 游程直方图

游程在图像中定义为具有相同灰度值的在某一方向 (通常为0o, 45o, 90o, 135o)的连续点的集合。每个游程中所含点数的数目则定义为游程长度。游程直方图的描述为[13]

游程直方图最初用于纹理检测，长游程反映了区域较平滑，短游程则表示像素值变化较快[14]。由于对比度修改会转换图像像素值，如图1所示，从而改变图像的游程长度分布，因此游程直方图可有效地作为一种对比度修改检测工具。

图1 对比度修改前后的图像及其游程直方图

2.3基于超像素和游程图的对比度修改检测方法

在自然图像中存在着某些统计上的性质，而对比度修改操作会改变图像潜在的统计上的规律，通过检测改变的统计规律即可鉴别图像是否经过对比度修改。

文献[15]中指出，对比度修改操作对数字图像灰度直方图所带来的影响可公式化地描述为

经过上述转换，修改后的图像直方图会产生波峰波谷效应。当多个不同的值转换到同一个值时，直方图该值处会成为波峰；当没有值转换到值时，直方图该值处会成为波谷[16]。

本文提出的融合不同方向经过加权累加的游程直方图能放大波峰波谷效应，使原始图像和经过对比度改变后的图像特征值差别更明显。如图1所示。

2.4 提出的对比度修改检测算法

本文算法具体步骤：

(1)使用SLIC超像素分割算法将图像分割为适当数量的图像块。

(2)处理步骤(1)中的每个图像块。提取并融合不同方向的游程直方图特征值，根据游程长度进行加权处理。然后根据像素值进行累加获得游程向量。

(3)将步骤(2)中提出的游程向量进行归一化操作。

(4)计算步骤(3)中归一化后的游程向量中波峰波谷数量，即数值突变量：

3 实验与结果分析

3.1实验图像库与实验方法

实验采用以下5种图像库：

图像库1：Uncompressed Colour Image Database(UCID)[18]。库中包含1338幅未压缩的真实图像，图像大小为512384。图像内容包括场景、物品，室内和室外等。

图像库2：CASIA[19]。该库由中国科学院提供，其V1.0版本包含800幅真实图像和921幅伪造图像，图像大小为384256，图像格式为JEPG格式。实验使用库中800幅真实图像。

图像库3: IEEE IFS-TC image forensics challenge[20]，库中包含1013张未压缩图像，图像格式为PNG格式，图像大小包括1024768, 1024683, 1024681, 1024575, 1024680等。

图像库4: IEEE IFS-TC image forensics challenge，库中包含1013张未压缩图像，每幅图像随机截取128128区域作为实验图像。

图像库5: IEEE IFS-TC image forensics challenge，库中包含1013张未压缩图像，每幅图像随机截取6464区域作为实验图像。

实验方法：

对每幅图像进行对比度修改操作，生成修改后图像库。随机选取真实图像的3/5和修改后图像的3/5作为训练数据，剩余2/5真实图像和修改后图像的2/5作为测试数据。

分类器采用LibSVM[21]，核函数为RBF。对比度修改方法采用伽马调整，和直方图均衡化，算法参数取值为1。

3.2实验结果

为测试本文所提出的对比度修改检测算法性能，对测试集中的每一幅图像进行分类，判别其是否经历过对比度增强操作。性能测度指标包括正检率和虚警率，分别定义为正确分类的篡改图像占篡改图像总数的百分比和错误分类的原始图像占原始图像总数的百分比。实验采取文献[7]和文献[8]算法作为对比算法，实验结果利用ROC曲线[22]显示。

3.2.1伽马值等于1.5时伽马调整检测实验 表1为本文算法在5个图像库上的实验结果。表中TP表示测试集中真实图像被正确分类的概率，TN表示测试集中篡改图像被正确分类的概率。识别率为二者的平均值。实验结果表明基于加权游程直方图的对比度修改检测算法能有效用于图像对比度修改检测。当图像大小为6464时，算法检测率达80.864%，其中真实图像正确检测率为85.47%，篡改图像正确检测率为76.26%。

图2 不同算法的ROC曲线比较

表1算法的实验结果(%)

图像库TPTN识别率(%) UCID 99.9699.6699.81 CASIA100.0099.0699.53 IEEE IFS-TC image forensics challenge 98.0799.2198.64 IEEE IFS-TC image forensics challenge (128128) 89.9288.3589.14 IEEE IFS-TC image forensics challenge (6464) 85.4776.2680.86

表2为不同算法特征维度以及算法在实验图像库中检测准确率对比。

3.2.3直方图均衡化检测实验 直方图均衡化是一种对图像中像素个数多的灰度级进行展宽，对图像中像素个数少的灰度进行压缩的操作，扩展像原取值的动态范围，提高了对比度变化，使图像更加清晰。

图4是对图像库1进行直方图均衡化操作后不同算法识别率ROC曲线图。其中本文提出的算法准确率为99.81%；文献[8]提出的算法准确率为94.58%；文献[7]提出的算法：当取值为96时，准确率为73.95%;取值为64时，准确率为57.617%;取值为32时，准确率为55.84%。通过ROC曲线以及准确率比较可以得出本文提出的算法实验结果明显优于其他算法。

3.2.4区域对比度修改检测实验 图5为图像复制粘贴区域检测实验，图5(a)左下角区域经过复制后粘贴到图5(b)中适当区域。由于图5(a)与图5(b)对比度不同，复制区域需经过对比度修改才可与被篡改图像保持视觉上的一致性。图5(c)为篡改后图像，图5(d)为基于超像素分割的检测结果，图5(e)为基于普通分块的检测结果。检测方法为先将图像进行分割，再计算每个分割块的游程直方图数值突变量；使用图像库4做实验图像库，随机选取库中1/2图像进行对比度修改；计算修改后图像库中图像的数值突变量，使用LibSVM进行学习；将图5(d)和图5(e)中的分割块的数值突变量作为测试数据进行分类，判断该块是否经过对比度修改。如果判断结果为该块经过修改则标记为黑色。图5(d)标记为黑色的块基本覆盖篡改区域，表明本文提出的算法对于图像复制粘贴区域有较好的检测效果。图5(e)是基于普通分割技术的对比度检测结果，先将图像均匀分割成大小一致的块，而后对每块单独检测。图5(e)中标记为黑色的块虽然基本覆盖了篡改区域，但由于每个网格块都是相同的矩形，覆盖的区域是不规则的多边体，无法准确显示出篡改区域形状以及轮廓范围，和图5(d)的检测结果形成明显对比。通过两图对比明显表明本文提出的基于超像素分割的区域检测结果的精准度明显高于基于传统分割技术的检测结果。

表2 实验结果比较(%)

图3 不同图像库识别率ROC曲线        图4 图像库1直方图均衡化操作后的ROC曲线

图5 复制粘贴区域检测实验

3.3实验分析

(1)参数分析：经过对比度改变后的图像的游程直方图波峰处数值增大，使用非线性增长的加权系数能够放大波峰效应。

图6为式(3)采用不同加权系数时算法在图像库中识别率的ROC曲线，图6(a)显示在CASIA图像库中所有的加权系数均取得较高的识别率，图6(b)显示在尺寸为6464的图像中，加权系数为时算法识别率略高于其他加权系数。所以当图像尺寸较小时，加权系数应选取，图像尺寸较大时加权系数可自由选取，本文实验中使用作为识别尺寸较大的图像时的加权系数。

(2)性能分析：现存的对比度修改检测算法多数直接使用图像直方图，通过检测直方图中波峰波谷判断图像是否经过对比度修改。而波峰波谷效应在一些图像直方图中表现并不明显，尤其当图像尺寸较小时，原始图像中像素点数量较少，直方图中大量像素值对应的数量接近零，使得未经过对比度修改的图像直方图中存在多个波谷，导致检测准确率偏低。本文提出的算法使用加权累加的游程直方图，通过设置不同的非线性权重达到放大波峰波谷效应的目的。由于经过放大后的波峰波谷效应更加明显，所以检测准确率远远高于其他算法。

当图像进行伽马调整后，伽马值为1.5时，算法在图像库1，图像库2，图像库3中准确率分别为99.81%, 99.53%, 98.64%，略高于文献[7]提出的算法。在图像库4和图像库5中准确率分别为89.14%, 80.86%，远高于其他算法准确率。当伽马值任意选取时，本文提出的算法也取得较为理想的识别效果。并且在图像复制粘贴区域检测实验中，算法能准确的识别出复制粘贴区域。

实验结果表明，算法在对比度修改识别方面具有良好的性能，尤其是对于尺寸较小的图像，检测结果明显优于其他算法。由于加权的游程直方图能放大对比度修改产生的波峰波谷效应，所以直接计算游程直方图数值突变量即可达到准确检测图像真伪的目的。相比于其他算法，本文提出的算法检测准确率高，并能准确识别出图像复制粘贴区域形状。

图6 不同加权系数在CASIA图像库和6464图像中的识别曲线

4 结束语

本文提出了一种基于超像素分割和游程直方图融合的对比度修改检测算法。实验结果证明该算法对于图像整体对比度修改检测以及区域复制粘贴检测都有良好的检测效果，尤其是对于尺寸较小的图像检测结果明显优于其他算法，并且能检测出复制粘贴区域轮廓形状。但是经过对比度修改后的图像如果再经过其他篡改手段会破坏波峰波谷效应，导致算法检测无效。所以算法的鲁棒性较差，尤其对于对反取证或者压缩后的图像，检测效果不理想。因此下一步的工作是研究对比度修改在图像中留下的其他统计特征，而后融合本文提出的算法，以进一步提高图像对比度修改的综合检测性能。

[1] 骆伟祺, 黄继武, 丘国平. 鲁棒的区域复制图像篡改检测技术[J]. 计算机学报, 2007, 30(11): 1998-2007.

LUO Weiqi, HUANG Jiwu, and QIU Guoping. Robust detection of region-duplication forgery in digital image[J]., 2007, 30(11): 1998-2007.

[2] 李晓飞, 申铉京, 陈海鹏, 等. 基于数字签名方式的图像真伪鉴别算法[J]. 计算机研究与发展, 2012, 49(6): 1348-1356.

LI Xiaofei, SHEN Xuanjing, CHEN Haipeng,. An image identification algorithm based on digital signature method[J]., 2012, 49(6): 1348-1356.

[3] ANDALIBI M and CHANDLER D. Digital image watermarking via adaptive logo texturization[J]., 2015, 24(12):5060-5073.

[4] CAO G, ZHAO Y, NI R,. Contrast enhancement-based forensics in digital images[J]., 2014, 9(3): 515-525.

[5] ARICI T, DIKBAS S, and ALTUNBASAK Y. A histogram modification framework and its application for image contrast enhancement[J]., 2009, 18(9): 1921-1935.

[6] CAO G, ZHAO Y, NI R,. Anti-forensics of contrast enhancement in digital images[C]. 12th ACM Workshop on Multimedia and Security, ACM, Rome, Italy,2010: 25-34.

[7] STAMM M C and LIU K J R. Forensic detection of image manipulation using statistical intrinsic fingerprints[J]., 2010, 5(3): 492-506.

[8] DE ALESSIA Rosa, FONTANI Marco, MASSAI Matteo,. Second-order statistics analysis to cope with contrast enhancement counter-forensics[J]., 2015, 22(8): 1132-1136.

[9] LIN X, LI C, and HU Y. Exposing image forgery through the detection of contrast enhancement[C]. 2013 20th IEEE International Conference on Image Processing (ICIP), Melbourne Australia, 2013: 4467-4471.

[10] CAO G, ZHAO Y, NI R,. Attacking contrast enhancement forensics in digital images[J]., 2014, 57(5): 1-13.

[11] SHEN J, DU Y, WANG W,. Lazy random walks for superpixel segmentation[J]., 2014, 23(4): 1451-1462.

[12] RADHAKRISHNA A, APPU S, KEVIN S,. SLIC superpixels compared to state-of-the-Art superpixel methods[J]., 2012, 34(11): 2274-2282.

[13] GOLOMB S W. Run-length encodings[J]., 1966, 12(3): 317-319.

[14] TANG X. Texture information in run-length matrices[J]., 1998, 7(11): 1602-1609.

[15] STAMM M C and LIU K J R. Forensic estimation and reconstruction of a contrast enhancement mapping[C]. IEEE International Conference on Acoustics Speech & Signal Processing, Dallas, TX, USA 2010, 23(3): 1698-1701.

[16] YANG Liang, GAO Tiegang, XUAN Yan,. Contrast modification forensics algorithm based on merged weight histogram of run length[J]., 2016, 8(2): 27-35.

[17] SHALEV S S and SREBRO N. SVM optimization: inverse dependence on training set size[C]. Proceedings of the 25th International Conference on Machine Learning, ACM, Helsinki, Finland, 2008: 928-935.

[18] SCHAEFER G and STICH M. UCID - An uncompressed color image database[C]. Storage & Retrieval Methods & Applications for Multimedia 2004, San Jose, CA, USA, 2003, 5307: 472-480.

[19] CASIA ITDE Database. http://forensics.idealtest.org. 2016.

[20] IEEE IFS-TC image forensics challenge. http://ifc.recod. ic.unicamp.br/fc.website/index.py?sec=0. 2016.

[21] CHANG C and LIN C. LIBSVM: a library for support vector machines[J].&, 2001, 2(3): 389-396.

[22] FAWCETT T. An introduction to ROC analysis[J]., 2006, 27(8): 861-874.

Contrast Modification Forensic Algorithm Based on Superpixel and Histogram of Run Length

GAO Tiegang YANG Liang XUAN Yan TONG Jing

(,,300071,)

A novel image forensic algorithm against contrast modification based on superpixel and histogram of run length is proposed. In the proposed algorithm, images are firstly divided by superpixel, then run length histogram features of each block are extracted, and those of different orientation are subsequently merged. After normalization of the prior features, the leaps in the histogram are calculated numerically. Lastly, the generated features of blocks are trained by Support Vector Machin (SVM) classifier. Large amounts of experiments show that, the proposed algorithm has low cost of computation complexity. And compared with some state-of-the-art algorithms, it has better performance with many test databases. Furthermore, the proposed algorithm can not only located the tempered area, but also can exactly describe the shape of tempered area.

Image processing; Contrast modification; Superpixel; Run length histogram; Leaps in the histogram numerically; Support Vector Machin (SVM)

TN911.73

A

1009-5896(2016)11-2787-08

10.11999/JEIT160161

2016-02-19；改回日期：2016-08-01；

2016-09-30

杨亮 yangliang.nkcs@gmail.com

天津市自然科学基金(16JCYBJC15700)

Tianjin Natural Science Foundation (16JCYBJC 15700)

高铁杠： 男，1966年生，博士，教授，研究方向为数字图像取证、多媒体信息安全以及信号处理等.

杨 亮： 男，1992年生，硕士生，研究方向为数字图像取证，信息安全等.

宣 妍： 女，1993年生，硕士生，研究方向是数字图像取证、信息安全等.

佟 静： 女，1993年生，硕士生，研究方向为多媒体信息安全等.