Copy-Move Forgery Detection Using Cellular Automata - Cellular Automata in Image Processing and Geometry - page 106

1. First the image is pre-processed because most algorithms require only the lu-
minance component information, and so it is necessary to convert images to
grayscale space. Sometimes a Gaussian pyramid decomposition is also applied
(for example, in [25]).
2. After pre-processing, an image is divided into overlapping blocks by sliding a
predefined window by one pixel through the whole image. The size of the win-
dow is usually small (for example, 8 × 8, 16 × 16, 24 × 24 pixels) to assure de-

tection of areas of all sizes. Dividing an N × M image into overlapping blocks

of size b b leads to a very large number of different blocks according to equa-

tion (6.1) (for illustration: dividing a 512

×

× 512 image using a 8 × 8 window pro-

duces 255,025 different blocks).

N b =( N − b + 1 ) × ( M − b + 1 ) (6.1)

3. For every defined block a feature vector f is calculated by same method. The
feature vector is used as a reduced description of a block because it contains
information about shape, texture, orientation or some other properties of a block.
The size of the feature vector depends on the selected method for its calculation.
4. Applying brute-force search to find similar blocks by mutual comparison of all
pairs of blocks requires a lot of computational time and resources. Therefore,
all feature vectors are stored in one matrix that is sorted by some algorithm (for
example, lexicography sorting) to accomplish grouping of similar blocks. Be-
side sorting, some other methods for finding similar blocks can be applied, for
example, kd-tree.
5. Neighbor feature vectors in the sorted matrix are than compared by analyzing the
similarity between them, using the Euclidean distances between feature vector
elements according to equation (6.2). All pairs of blocks with distance v higher
than some predefined threshold T s are removed from the set of possible results.
Selection of threshold T s depends on the type of forgery, for example, it can be
set to zero for plain CMF, or it has to be adjusted to some higher values if any
transformations/post-processing methods are applied. After this step only similar
pairs of blocks are kept as possible results.

size ( f )
i = 1 ( f 1 ( i ) − f 2 ( i ))

v =

2

(6.2)

6. The set of possible results is analyzed again and Euclidean distance d is calcu-
lated between coordinates of blocks of every pair according to equation (6.3).
All pairs with distance d smaller than predefined threshold T d are removed from
the set of possible results. Threshold T d is usually defined according to selected
block size (for example, k b ,where k is some small positive constant) to remove

all close blocks (it can be assumed that a block is moved more than T d pixels).
After this step only similar pairs of blocks that are not close to each other are
kept as possible matches.

×