# New approach development for solution of cloning results detection problem in lossy saved digital image.

UDC 004.932:004.052.42Introduction. One of the program tools implemented in all modern graphic editors (Adobe Photoshop, Gimp, etc.) which are most often used for falsifications of the digital images (DI) is the cloning at which the part of DI called a prototype is copied and moves to another area of the same image, replacing with itself his original part and forming a clone. The cloning is used in case when an "undesirable" object is removed from the image, the existing objects are duplicated, their location changes within the image scene.

Taking into account the modern level of information technologies development, the implemented capabilities of graphic editors the changes on DI, in particular cloning, can be made so qualitatively that their detection is the problem needed for the solution of the attraction of the widest mathematical apparatus, the methods considering various tricks of falsification "authors" for the purposes of masking of the main results of their work, including, post-processing of DI after cloning executed in it.

In spite of the fact that the problem of detection of cloning results in the conditions of post-processing, in particular, of lossy DI compression isn't new [1 ... 4], it is not completely solved. In particular, efficiency of clone/prototype areas detection needs improvement under conditions of lossy compression in case when the cloning aims the hiding of an object (objects) using the prototype which is a part of the DI background area. It is possible to assume that one of the main reasons for this is the widely known approach for the solution of such problems is based on technology of use of characteristic points of the image [2, 5 ... 7] and is effective in case if objects are cloned.

In [8] authors of the work have offered theoretical bases of new approach to the solution of results of cloning detection problem in a digital image saved after change in a lossy format. Approach is based on the considering of a small change of a cylindrical body volume with generatrix during the compression process. That generatrix is parallel to OZ axis and limited from above by the plot of the interpolating function g(x,y) for the image brightness matrix F, from below--by the XOY plane. Indicator of existence of clone areas of prototype is the proximity of double integrals values from function g (x, y) on the corresponding subareas of definition range of the function which is originally set the initial image.

New approach gives the principle possibility based on it in providing of the effective solution of viewed problem that is irrespective of performed cloning specifics, used during compression algorithm and parameters, that has not been fully provided in [8].

The aim of the work is to further develop of proposed in [8] approach to solve the problem of cloning detection in conditions of lossy saving of the DI.

To accomplish the aims, such problems are solved in this work:

1. Adaptation of the approach offered in [8] to conditions of cloned DI compression with any quality offered in [8] (compression ratio);

2. Providing (providing check) a solvency of the offered approach in the conditions of compression of cloned DI according to algorithms other than the JPEG standard.

Materials and Methods. Without limiting of verbal proofs collectivity, to simplify the statement, the DI are further considered in gradation of gray which formal representation is one twodimensional matrix. In case of the color image, all following verbal proofs can be carried to each of color component separately, participating in its formal representation (RGB scheme), or to a brightness matrix (YUV scheme).

Let F--nxm-DI matrix with elements [f.sub.ij, i = [bar.1,n], j = [bar.1,m].

Let set, as in the [8], [B.sub.ij]--q x q F matrix block, for which at position (1,1) is situated the element [f.sub.ij]. To each such block, according to [8], we will associate (n-q+1)x(m-q+1)-[M.sup.(i,j)] matrix, each element [m.sup.(i,j).sub.k,l], k = [bar.1, n - q + 1], [bar.l = 1, m - q + 1] of it shows the difference of [B.sub.ij] block from [B.sub.kl] block in such sense: [m.sup.(i,j).sub.k,l] = [q.summation over (t,p=1)] [r.sub.tp], where [r.sub.tp],t,p = [bar.1,q],--elements of matrix R = [absolute value of ([B.sub.ij] - [B.sub.kl])], where the last equality is understood as element-by-element method.

The approach offered in [8] is essentially not connected with the value of DI compression ratio after performed cloning. For the blocks [B.sub.ij] and [B.sub.kl] of clone and the prototype image respectively shown, that min [M.sup.(i,j)] = min [M.sup.(k,l)] and reached in corresponding elements, that correspond to the prototype and clone image. So, if to define (n-q+1) x (m-q+1)-G matrix with elements [g.sub.ij] in such way: [g.sub.ij] = min [M.sup.(i,j)], then for the blocks [B.sub.ij] and [B.sub.kl] of clone and the prototype image the elements [g.sub.ij] = [g.sub.kl], at that in this elements the global minimum of the G is reached practically certain. At this, the [g.sub.tp] element is called as global minimum of the G, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Such conclusion was made in [8] allowing for additional perturbation actions, that are applied to DI after cloning process. i.e. lossy saving, cannot be great, because otherwise violation of image perception is possible--artifact appearance. However, in practice the use of low quality factors (high compression ratios) often doesn't lead to appearance of visible artifacts on the compressed image, so such parameters can be essentially used at unauthorized change of DI for the subsequent masking of these changes. Therefore, to eliminate the restrictions of the applicability domain of the developed approach its adaptation is needed to ensure its viability, regardless of the quality factor used during DI compression.

Considerable compression (with low quality factor) will significantly change all elements of DI matrix. Here, the option is essentially possible when change of the DI blocks which weren't coinciding among themselves by values before compression can lead to the fact that their difference after compression will be comparable (or even smaller), than for the corresponding blocks of a clone and prototype image which were originally coinciding on values. However, taking into account the way of formation of blocks [B.sub.ij] of DI matrix, it is obviously, that in small neighborhood of the corresponding blocks of a clone/prototype image their difference among themselves will be the smallest. Thus, at any quality factor used for lossy compression of the cloned image, an indicator of the corresponding blocks of clone and prototype images [B.sub.ij] and [B.sub.kl] will be the coincident elements [g.sub.ij] = [g.sub.kl] of the matrix, in which not only the global, but also local minimum of the G can be reached (in element [g.sub.tp] the local minimum is reached if in the G matrix such neighborhood U([g.sub.tp]) exist for element [g.sub.tp], that for any matrix element [g.sub.ij] [member of] ([g.sub.tp]), [g.sub.ij] [not equal to] [g.sub.tp] the condition [g.sub.ij] > [g.sub.tp] is true). This, as a rule, can be reached, when the cloning is used to remove an object from DI using prototype image, being the part of image background. This conclusion provides the possibility of the new approach using at DI compression with any quality factor.

Illustration for the told is the example given in Fig. 1 where the global minimum of the function which is an interpolation spline for G matrix elements is reached in the elements of the G corresponding to the DI blocks different from clone/prototype image blocks. At the same time the areas of a clone and a prototype image correspond to the local minima of the G coinciding by value, resulting in characteristics of the plot: to existence of comparable in a form cone-shaped surfaces (the neighborhood of clone/prototype image blocks), which z-coordinates of tops have identical values (marked in Fig. 1).

Confirmation of effective recognition of cloning in DI in conditions of considerable compression using the approach [8] which has gained further development in this work, were results of the computing experiment were made with an experimental set of images (ES) which consisted of 300 DI of the NRCS base [9], which is traditional for testing of the algorithms working with images.

During the experiment an original DI was exposed to cloning and then was saved in JPEG format with quality factors QF [member of] {25,35,45,55,65,75,85,95}. Compressed DI were analyzed using the advanced approach: for the received G matrix (q [member of] {16,24,32}) the function plot was built, interpolating its elements, which showed the presence of characteristic areas corresponding to the elements of the G, where its local minima coinciding on values were reached. Expert assessment of characteristic properties of the plot has yielded the positive result for 98.7 % of DI used in experiment: for them the areas of a clone/prototype image corresponding to real have been found. The comparable result (98.1 % of DI) has been received in case when images after cloning were saved in JPEG2000 format with quality factors QF [member of] {25,35,45,55,65,75,85,95} .

As one more option of DI lossy compression implementation we will consider a way which is not the accepted standard, but it is often used during the work with images [10]. This way is based on lowrank approximations of a matrix (matrix blocks) of DI and consists in the following.

For nxm-matrix F (n [greater than or equal to] m) of DI its singular decomposition is built [10]:

F = U[SIGMA][V.sup.T], (1)

where U, V--orthogonal matrixes of sizes nxm and mxm accordingly, which columns are the left and right singular vectors of F, E = diag([[sigma].sub.1], [[sigma].sub.2], ..., [[sigma].sub.m])--diagonal matrix of singular numbers, for which [[sigma].sub.1] [greater than or equal to] [[sigma].sub.2] [greater than or equal to] ... [greater than or equal to] [[sigma].sub.m] [greater than or equal to] 0. If n [less than or equal to] m then singular decomposition of a matrix Fr is considered. Decomposition (1) of a matrix F can be presented in the form of external products: F = [m.summation over (i=1)] [[sigma].sub.i][u.sub.i][v.sub.i.sup.T], where [u.sub.i], [v.sub.i], i = [bar.1, m],--columns of matrixes U, V accordingly.

Approximation of a matrix F of a rank k [less than or equal to] m is called the matrix [F.sub.k] = [m.summation over (i=1)] [[sigma].sub.i][u.sub.i][v.sub.i.sup.T], that is nearest to F (in sense of spectral matrix norm) by matrix of range ? [10]. The substitution of F to [F.sub.k] leads to image compression is greater, the less k.

Let's check a solvency of the offered approach of cloning detection in the conditions of compression of the cloned DI using low-rank approximations of a matrix of whole image.

During the computing experiment the DI from ES were exposed to cloning and then compressed using k-rank approximations with various values of k. As results of the experiment show, the offered approach remains well-founded up to k = m/10. We will notice that at k < m/10 there are obvious artifacts in DI.

The illustration of typical results of testing for the offered approach (detection of characteristic properties of the function that is interpolating G matrix elements) for specific DI is presented in Fig. 2 (results are yielded for ? = 100 and ? = 20; for values 20 < ? < 149 qualitative picture is similar). It should be noted also obvious localization of a clone/prototype image areas on the projection of the plot of functions interpolating G to the XOYplane (Fig. 2, c, e--the respective areas are specified by arrows).

Let's consider use of low-rank approximations during processing the separate 8 x8-blocks of a matrix of DI obtained by standard splitting (just as it performed in JPEG and JPEG2000). Such way of compression will be more preferable before use of low-rank approximation of all matrix in sense of computing complexity as here the costs of singular decomposition construction of the block won't depend on the size of initial DI matrix, and will be a constant concerning the size of input data. Computing complexity of DI compression process using low-rank approximations of blocks of its n x m-matrix will be defined by blocks quantity equal [O.bar](nm) .

Let's establish how the rank of blocks approximation influences on reliability of perception of compressed DI, that is quantitatively estimated standardly [4]: using the peak "signal noise" relation PSNR. The computational experiment has been made for this purpose, during which DI from ES were exposed to compression using k-rank approximations of 8 x 8-blocks, where k [member of] {1, ..., 7} then PSNR value was calculated. Results are given in Fig. 3.

As computational experiment shows, already for k = 3 the average value of PSNR < 40 dB that can be expressed in appearance of artifacts on DI [11], however even at small value of rank of the used blocks approximations of DI the subjective ranging can not reveal any artifacts in compressed DI. The illustration to told is given in Fig. 4. Taking it into account is essentially possible the using of approximations of blocks of any rank k [member of] {1, ..., 7} to mask performed cloning. It leads to need for ensure (providing check) operability of the offered approach of cloning detection in conditions of use for compression of the cloned image of any rank k [member of] {1, ..., 7} blocks approximations.

When carrying out a computational experiment, it has been established by subjective estimation that characteristics of a function plot, that interpolate elements of G matrix, stated above were present for all DI, subjected to cloning with the subsequent compression using any rank of approximation blocks: k = [bar.1,7]. Illustration of this is in Fig. 5, where DI was exposed to compression, presented in Fig. 2, a.

Thus, the offered new approach to detect areas of a clone/prototype in DI in the conditions of lossy compression of the cloned image is well-founded in case for compression the low-rank approximations of matrix (matrix blocks) of DI are used.

Conclusions. In work the further development of new approach offered by authors earlier to the solution of a problem of a cloning/prototype image areas detection in the digital image in the conditions of his subsequent lossy saving is carried out.

The main object of the analysis is the matrix G which elements reflect the smallest difference of the corresponding block of the image matrix from any other incoincident with him. It is shown that the corresponding blocks of a clone/prototype image in matrix G correspond coincide by value its local minima, which generally can differ from value of a global minimum. The obtained conclusion has allowed to provide a solvency of the offered approach in conditions of compression of the cloned DI with any quality factor (compression ratio) when using for compression not only the JPEG standard, but also other algorithms other than JPEG, in particular JPEG2000, algorithms based on low-rank approximations of an image matrix (matrix blocks).

Given the fact that the digital video sequence may be considered as a sequence of DI, there are no fundamental restrictions on the use of this method to identify a cloning in a digital video under additional attacks.

DOI 10.15276/opu.2.49.2016.10

References

[1.] Thajeel, S.A., & Sulong, G.B. (2013). State of the art of copy-move forgery detection techniques: A Review. International Journal of Computer Science, 10(6), 174-183.

[2.] Kotkar, P.S., & Shriramwar, S.S. (2014). Detecting region duplication forgery in digital image using SIFT features. International Journal of Current Engineering and Technology, 4(3), 1437-1440.

[3.] Pan, X., & Lyu, S. (2010). Region duplication detection using image feature matching. IEEE Transactions on Information Forensics and Security, 5(4), 857-867. DOI:10.1109/TIFS.2010.2078506

[4.] Amerini, I., Ballan, L., Caldelli, R., Del Bimbo, A., Del Tongo, L., & Serra, G. (2013). Copy-move forgery detection and localization by means of robust clustering with J-Linkage. Signal Processing: Image Communication, 28(6), 659-669. DOI:10.1016/j.image.2013.03.006

[5.] Huang, H., Guo, W., & Zhang, Y. (2008). Detection of copy-move forgery in digital images using SIFT algorithm. In Y. Zhang, H. Tan, Q. Luo (Eds.), Proceedings of the Pacific-Asia Workshop on Computational Intelligence and Industrial Application (PACIIA '08) (Vol. 2, pp. 272-276). Los Alamitos: IEEE. DOI:10.1109/PACIIA.2008.240

[6.] Xu, B., Wang, J., Liu, G., & Dai, Y. (2010). Image copy-move forgery detection based on SURF. In S. Gritzalis, S. Lian, X. Chen (Eds.), Proceedings of the Second International Conference on Multimedia Information Networking and Security (MINES'2010) (pp. 889-892). Los Alamitos: IEEE. DOI:10.1109/MINES.2010.189

[7.] Amerini, I., Ballan, L., Caldelli, R., Del Bimbo, A., & Serra, G. (2011). A SIFT-based forensic method for copy-move attack detection and transformation recovery. IEEE Transactions on Information Forensics and Security, 6(3), 1099-1110. DOI:10.1109/TIFS.2011.2129512

[8.] Kobozeva, A.A., & Grygorenko, S.N. (2015). Theoretical basis for a new approach to the problem of identifying the results of cloning in digital images stored in lossy formats. Data Rec., Storage & Processing, 17(4), 21-30.

[9.] USDA: United States Department of Agriculture (n.d.). NRCS Photo Gallery. Retrieved from http://photogallery.nrcs.usda.gov/res/sites/photogallery/

[10.] Demmel, J.W. (1997). Applied Numerical Linear Algebra. Philadelphia: SIAM.

[11.] Konahovich, G.F., & Puzyrenko, A.Yu. (2006). Computer Steganography: Theory and Practice. Kyiv: MK-Press.

[TEXT NOT REPRODUCIBLE IN ASCII]

[1.] Thajeel, S.A. State of the art of copy-move forgery detection techniques: A Review / S.A. Thajeel, G.B. Sulong // International Journal of Computer Science.--2013.--Vol. 10, Issue 6.--PP. 174-183.

[2.] Kotkar, P.S. Detecting region duplication forgery in digital image using SIFT features / P.S. Kotkar, S.S. Shriramwar // International Journal of Current Engineering and Technology.--2014.--Vol. 4, No. 3.--PP. 1437-1440.

[3.] Pan, X. Region duplication detection using image feature matching / X. Pan, S. Lyu // IEEE Transactions on Information Forensics and Security.--2010.--Vol. 5, Issue 4.--PP. 857-867. DOI:10.1109/TIFS.2010.2078506

[4.] Copy-move forgery detection and localization by means of robust clustering with J-Linkage / I. Amerini, L. Ballan, R. Caldelli, et al. // Signal Processing: Image Communication.--2013.--Vol. 28, Issue 6.--PP. 659-669.

[5.] Huang, H. Detection of copy-move forgery in digital images using SIFT algorithm / H. Huang, W. Guo, Y. Zhang // Proceedings of the Pacific-Asia Workshop on Computational Intelligence and Industrial Application (PACIIA'08), 19-20 December 2008, Wuhan, China.--Los Alamitos: IEEE, 2008.--Vol. 2.--PP. 272-276.

[6.] Image copy-move forgery detection based on SURF / B. Xu, J. Wang, G. Liu, Y. Dai // Proceedings of 2010 International Conference on Multimedia Information Networking and Security (MINES'2010), 4-6 November 2010, Nanjing, Jiangsu.--Los Alamitos: IEEE, 2010.--PP. 889-892.

[7.] A SIFT-based forensic method for copy-move attack detection and transformation recovery / I. Amerini, L. Ballan, R. Caldelli, et al. // IEEE Transactions on Information Forensics and Security.--2011.--Vol. 6, Issue 3.--PP. 1099-1110.

[8.] [TEXT NOT REPRODUCIBLE IN ASCII].

[9.] NRCS Photo Gallery . [TEXT NOT REPRODUCIBLE IN ASCII] / United States Department of Agriculture. Washington, USA.--[TEXT NOT REPRODUCIBLE IN ASCII]: http://photogallery.nrcs.usda.gov . [TEXT NOT REPRODUCIBLE IN ASCII]: 26.07.2012).

[10.] [TEXT NOT REPRODUCIBLE IN ASCII].

[11.] [TEXT NOT REPRODUCIBLE IN ASCII].

Received May 31, 2016

Accepted July 10, 2016

A.A. Kobozeva, DSc, Prof., S.M. Grigorenko

Odessa National Polytechnic University, 1 Shevchenko Ave., 65044 Odessa, Ukraine; e-mail: alla_kobozeva@ukr.net

Caption: Fig. 1. A plot of function, interpolating the G matrix elements, for DI after cloning with the subsequent saving using JPEG format with QF = 25

Caption: Fig. 2. Results of identification of areas of a clone/prototype in the conditions of the compression cloned DI with use low-rank approximations of his matrix: a--the part DI (the size of pixels) containing areas of a clone and a prototype, kept after cloning in a format without loss (TIFF); b--a function plot, interpolating elements of G matrix in case k = 100; c--projection of G to XOY-plane having k = 100; d--function plot, interpolating elements of G matrix in case k = 20; e--projection of G to XOY-plane having k = 20

Caption: Fig. 3. Dependence of PSNR value on the approximation rank k of 8x8-blocks of a DI matrix at its compression: 1--average PSNR value of DI of ES; 2--minimum PSNR value; 3--the maximum PSNR value of all DI of ES

Caption: Fig. 4. Illustration of DI compression result using low-rank approximations of DI matrix blocks: a--initial DI; b--result of compression using 1-rank approximations of 8x8-blocks of DI

Caption: Fig. 5. Function plots, approximating the elements of DI matrix G, subjected to cloning with the subsequent compression having k-range approximations of 8x8-blocks: a--k = 1; b--k = 2; c--k = 3; d--k = 4; e--k = 5; f--k = 6

Printer friendly Cite/link Email Feedback | |

Title Annotation: | COMPUTER AND INFORMATION NETWORKS AND SYSTEMS. MANUFACTURING AUTOMATION |
---|---|

Author: | Kobozeva, A.A.; Grigorenko, S.M. |

Publication: | Odes'kyi Politechnichnyi Universytet. Pratsi |

Article Type: | Report |

Date: | Jul 1, 2016 |

Words: | 3567 |

Previous Article: | Research of the sediment formation intensity at the run-around cooling systems equipment with water cooling towers. |

Next Article: | Costs evaluation methodic of energy efficient computer network reengineering. |

Topics: |