# PatchMatch: a dense displacement field to spot copy-move forgery

### Introducing dense displacement field approach

PatchMatch is part of a class of algorithms which derive a dense

nearest-neighbor field from an image. For each pixel of the original image, we computes the pairwise distance to obtain the nearest neighbor. Therefore, we need to find the mapping function **f**, that associates each pixel **z**=(**x**,**y**) to its vector of displacement Φ:

such that :

A brute force approach cannot be considered. If **N** is the size of the image, the complexity of the algorithm is **O(N²)**. Thus, the main challenge of such methods is to find a near-optimal solution with a reduced complexity.

### PatchMatch algorithm

PatchMatch starts by splitting an image in small squares of the same size, which is called a patch. Instead of using a brute force approach, one can use the special regularity of natural images by expecting a smooth nearest-neighbors field. To use this property, the algorithm tries to propagate locally the best displacement vectors.

The algorithm is composed of several steps :

1 — Random initialization of the nearest neighbors field (NNF):

2 — Propagation procedure: the image is scanned top-down and left-to-right to update the displacement vector of each pixel by looking at the optimal vector in its neighborhood. To further reduce the complexity, we alternatively update the displacement vector from :

- the pixel on the left or above;

- the pixel on the right or under.

3 —Random search to avoid being trapped in local optimum: we draws random candidates to escape the potential suboptimum

The chosen candidates is therefore the one which minimises the Euclidean distance with the current pixel

### A more robust approach: an alternative to Generalized PatchMatch

The propagation procedure is looking at direct pixel neighbors, which is a zero-order prediction. As a matter of fact, it cannot produce good performance with rotations as the nearest neighbors field would be linealy varying. We need a one order prediction and thus, consider two other alternatives, alternatively

or,