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