﻿ 低频快速切比雪夫矩的篡改图像检测算法
 计算机系统应用  2020, Vol. 29 Issue (3): 194-199 PDF

Tamper Image Detection Algorithm for Low Frequency Fast Tchebichef Moment
ZHENG Jia-Wen, ZHANG Wei-Hu
College of Communication and Information Engineering, Xi’an University of Science and Technology, Xi’an 710054, China
Foundation item: Natural Science Foundation of Shaanxi Province (2017JM6102)
Abstract: Aiming at the research of image copying and tampering detection and tampering area localization, a tamper image detection algorithm for low frequency fast Tchebichef moment is proposed. Firstly, the image is decomposed by non-sampling wavelet transform, and the low-frequency part of the image is selected for overlapping segmentation. The improved low frequency fast Tchebichef moment is extracted as the feature vector. Then the PatchMatch algorithm is used to match the extracted block features. Finally, the dense linear fitting algorithm is used to remove the mismatch and the morphological operation is used to complete the final tamper region localization. Compared with the existing tampering image detection algorithm, the proposed algorithm has better positioning effect for single-region tampering, multiple tampering and multi-region tampering, and reduces the running time of the algorithm, and improves the real-time performance.
Key words: image tamper detection     unsampled wavelet     fast Tchebichef moment     feature matching     morphology

1 构造特征向量 1.1 Tchebichef矩

 \left\{\begin{aligned} & T_{n,m}^{p,q} = \sum\limits_{x = 0}^{N - 1} {\sum\limits_{y = 0}^{N - 1} {f\left( {p + x,q + y} \right)} } {t_n}\left( x \right){t_m}\left( y \right) \\ & n,m = 0,1,\cdots,N - 1 \end{aligned} \right. (1)

 \begin{aligned} {{t}_{n}}\left( x \right)=& \frac{\left( 1-N \right)!}{\sqrt{{}^{\left( N+{\rm n} \right)!}\!\!\diagup\!\!{}_{\left( 2n+1 \right)\left( N-n-1 \right)!}\;}} \\ & \sum\limits_{l=0}^{n}{\frac{{{(-n)}_{l}}{{\left( -x \right)}_{l}}{{\left( 1+n \right)}_{l}}}{{{\left( l! \right)}^{2}}{{\left( 1-N \right)}_{l}}}},\;n,x=0,1,\cdots,N-1 \end{aligned} (2)

 ${t_n}\left( {x + a} \right) = \sum\limits_{l = 0}^n {\sum\limits_{r = 0}^{n - l} {{g_r}\left( {n,l} \right)} } {\left( { - a} \right)_r}{t_l}\left( x \right)$ (3)

a=1时, 有:

 $t\left( {x + 1} \right) = {t_n}\left( x \right) - \sum\limits_{l = 0}^{n - 1} {{g_r}} \left( {n,l} \right){t_l}\left( x \right)$ (4)

 ${g_r}\left( {n,l} \right) = {\left( { - 1} \right)^n}\frac{{\left( {2l + 1} \right)\left( {N - 1 - l} \right)!}}{{r!\left( {N - 1 - n} \right)!}} \times \sqrt {\frac{{\rho \left( {l,N} \right)}}{{\rho \left( {n,n} \right)}}} \sum\limits_{s = l}^{n - r} {\frac{{{{\left( { - 1} \right)}^s}s!\left( {n + r + s} \right)!\left( {N - 1 - s - r} \right)!}}{{\left( {r + s} \right)!\left( {n - r - s} \right)!\left( {s + l + 1} \right)!\left( {s - l} \right)!\left( {N - 1 - s} \right)!}}} ,\;0 \le l \le n$ (5)
1.2 改进的低频快速Tchebichef矩

 \left\{\begin{aligned} & T_{n,m}^{p + 1,q} = \sum\limits_{x = 0}^{N - 1} {\sum\limits_{y = 0}^{N - 1} {f\left( {p + 1 + x,q + y} \right){t_n}(x){t_m}(y)} } \\ & n,m = 0,1,\cdots,N - 1 \end{aligned} \right. (6)

 $TC_m^{p,q} = \sum\limits_{y = 0}^{N - 1} {f\left( {p,q + y} \right)} {t_m}\left( y \right)$ (7)
 $TC_m^{p + N,q} = \sum\limits_{y = 0}^{N - 1} {f\left( {p + N,q + y} \right)} {t_m}\left( y \right)$ (8)

 \left\{\begin{aligned} & T_{n,m}^{p,q + 1} = \sum\limits_{x = 0}^{N - 1} {\sum\limits_{y = 0}^{N - 1} {f\left( {p + x,q + 1 + y} \right){t_n}(x){t_m}(y)} } \\ & n,m = 0,1,\cdots,N - 1 \end{aligned} \right. (9)

$TR_{\rm{m}}^{p,q}$ $TR_{\rm{m}}^{p + N,q}$ 分别表示输出行 $f\left( {p + x,q} \right),$ $0 \le {\rm{x}} \le$ $N - 1$ , m阶切比雪夫矩和输入行 $f\left( {p + x,q + N} \right),$ $0 \le {\rm{x}} \le$ $N - 1$ , m阶切比雪夫矩, 定义如下:

 $TR_n^{p,q} = \sum\limits_{x = 0}^{N - 1} {f\left( {p + x,q} \right)} {t_n}\left( x \right)$ (10)
 $TR_n^{p,q + N} = \sum\limits_{x = 0}^{N - 1} {f\left( {p + x,q + N} \right)} {t_n}\left( x \right)$ (11)

(1)对图像进行UWT二维分解, 提取其低频部分并进行重叠分块;

(2)计算切比雪夫多项式和系数矩阵;

(3)计算所有的行向量. 对于图像 $f\left( {x,y} \right)$ 每行的第一个行向量, 计算其切比雪夫矩, 每行的其余行向量计算其快速切比雪夫矩;

(4)计算所有的列向量的切比雪夫矩;

(5)计算图像 $f\left( {x,y} \right)$ 第一个块的矩特征, 基于步骤(4)的结果, 采用快速切比雪夫矩计算第一行的所有块的矩特征;

(6)基于步骤(2)和步骤(4)的结果, 采用快速切比雪夫矩计算其他块的矩特征.

2 PatchMatch算法匹配

(1)初始化. 对于每个像素s, 随机初始化偏移量:

 $\delta \left( s \right) = U\left( s \right) - s$ (12)

(2)传播. 在这个阶段, 图像按照从上到下、从左到右的顺序光栅扫描, 则每个像素s偏移量更新为:

 $\delta (s) = \arg \mathop {\min }\limits_{\phi \in {\Delta ^P}\left( s \right)} D\left( {f\left( s \right),f\left( {s + \phi } \right)} \right)$ (13)

(3)随机搜索. 由于传播过程依赖于随机初始的偏移量, 所以不能达到最优匹配. 为了尽量避免陷入局部最小值, 采用随机搜素, 在修正式(13)后, 对当前偏移量进行随机采样, 设候选偏移量 ${\delta _i}\left( {\rm{s}} \right),i = 1,\cdots,L$ 为:

 ${\delta _i}\left( {\rm{s}} \right) = \delta \left( s \right) + {R_i}$ (14)

 $\delta \left( s \right) = \arg \mathop {\min }\limits_{\phi \in {\Delta ^P}\left( s \right)} D\left( {f\left( s \right),f\left( {s + \phi } \right)} \right)$ (15)

3 后处理

 $\hat \delta \left( {{s_i}} \right) = A{s_i},\;i = 1,\cdots,N$ (16)

 ${\varepsilon ^2}\left( s \right) = {\sum\limits_{i = 1}^N {\left\| {\delta \left( {{s_i}} \right) - \hat \delta \left( {{s_i}} \right)} \right\|} ^2}$ (17)

 ${a^{opt}} = \arg \mathop {\min }\limits_a {\left\| {\delta - Sa} \right\|^2}$ (18)

 $S = \left[ {\begin{array}{*{20}{c}} 1&{s11}&{s12} \\ 1&{{s_{21}}}&{{s_{22}}} \\ {}&{...}&{} \\ 1&{{s_{N1}}}&{{s_{N2}}} \end{array}} \right]$ (19)

 $\hat \delta \left( {{s_i}} \right) = {a_0} + {a_1}{s_{i1}} + {a_2}{s_{i2}},\;i = 1,\cdots,N$ (20)

 ${a^{opt}} = {\left( {{S^{\rm T}}S} \right)^{ - 1}}{S^{\rm T}}\delta$ (21)

 \begin{aligned} {\varepsilon ^2}\left( s \right)& = {\left\| {\delta - S{{\left( {{S^{\rm T}}S} \right)}^{ - 1}}{S^{\rm T}}\delta } \right\|^2} \\ & = {\left\| {\left( {1 - H} \right)\delta } \right\|^2} = {\delta ^{\rm T}}\left( {1 - H} \right)\delta \\ \end{aligned} (22)

 $H = Q{Q^{\rm T}},\;Q = \left[ {{q_1},{q_2},{q_3}} \right]$ (23)

 ${\varepsilon ^2}\left( s \right) = \left( {{\delta ^{\rm T}}\delta } \right) - {\left( {{\delta ^{\rm T}}{q_1}} \right)^2} - {\left( {{\delta ^{\rm T}}{q_2}} \right)^2} - {\left( {{\delta ^{\rm T}}{q_3}} \right)^2}$ (24)

(1)对得到的偏移量进行中值滤波操作.

(2)通过最小二乘线性模型计算圆形邻域内的阈值为 $T_\varepsilon ^2$ 的拟合误差 ${\varepsilon ^2}$ .

(3)去除误匹配对, 包括较匹配区域对的距离像素更接近的匹配对, 或小于匹配区域面积像素的匹配对.

(4)映射检测到的区域.

(5)使用圆形的结构元素进行形态学操作, 实现篡改图像区域的定位完成检测.

 图 1 篡改图像后处理的检测结果

4 实验分析

 $precision = \frac{{TP}}{{TP + FP}}$ (25)
 $recall = \frac{{TP}}{{TP + FN}}$ (26)
 $F = 2 \cdot \frac{{precision \cdot recall}}{{precision + recall}}$ (27)

 图 2 单区域篡改图像的检测结果

 图 3 单区域多次篡改图像的检测结果

 图 4 多区域篡改图像的检测结果

5 结论与展望

 [1] 赖玥聪, 黄添强, 蒋仁祥. 采用指数矩的图像区域复制粘贴篡改检测. 中国图象图形学报, 2015, 20(9): 1212-1221. DOI:10.11834/jig.20150908 [2] 闫旭, 姜威, 贲晛烨. 基于改进Hu不变矩的图像篡改检测算法. 光学技术, 2018, 44(2): 171-176. [3] Ryu SJ, Kirchner M, Lee MJ, et al. Rotation invariant localization of duplicated image regions based on Zernike moments. IEEE Transactions on Information Forensics and Security, 2013, 8(8): 1355-1370. DOI:10.1109/TIFS.2013.2272377 [4] Dixit R, Naskar R. Copy-move forgery detection utilizing Fourier-Mellin transform log-polar features. Journal of Electronic Imaging, 2018, 27(2): 023007. [5] 谷宗运, 吕皖丽, 罗斌. 基于Tchebichef不变矩的数字图像被动认证算法. 合肥工业大学学报(自然科学版), 2011, 34(6): 848-852. [6] Li LD, Lin WS, Wang XS, et al. No-reference image blur assessment based on discrete orthogonal moments. IEEE Transactions on Cybernetics, 2016, 46(1): 39-50. DOI:10.1109/TCYB.2015.2392129 [7] Shu HZ, Zhang H, Chen BJ, et al. Fast computation of Tchebichef moments for binary and grayscale images. IEEE Transactions on Image Processing, 2010, 19(12): 3171-3180. DOI:10.1109/TIP.2010.2052276 [8] 柴新新, 邱晓晖. 基于提升小波变换的图像篡改检测算法. 计算机技术与发展, 2016, 26(4): 78-81. [9] 冯莉, 龚子华, 文远保. 非抽样小波变换耦合Zelnick矩的图像伪造检测算法. 计算机工程与设计, 2016, 37(6): 1588-1592. [10] Marcos JV, Cristóbal G. Texture classification using discrete Tchebichef moments. Journal of the Optical Society of America A, 2013, 30(8): 1580-1591. DOI:10.1364/JOSAA.30.001580 [11] Barnes C, Shechtman E, Finkelstein A, et al. PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Transactions on Graphics, 2009, 28(3): 24. [12] 甘玲, 王凯. 基于HSV和HE的复制粘贴篡改检测算法. 重庆邮电大学学报(自然科学版), 2019, 31(3): 400-406. [13] Cozzolino D, Poggi G, Verdoliva L. Efficient dense-field copy-move forgery detection. IEEE Transactions on Information Forensics and Security, 2015, 10(11): 2284-2297. DOI:10.1109/TIFS.2015.2455334 [14] Chen BJ, Coatrieux G, Wu JS, et al. Fast computation of sliding discrete Tchebichef moments and its application in duplicated regions detection. IEEE Transactions on Signal Processing, 2015, 63(20): 5424-5436. DOI:10.1109/TSP.2015.2451107