Graph Cut

[59], proposed by Kwatra et al., introduces a non-causal synthesis procedure that could find arbitrary-shaped optimal cuts in a 2D image plane. Non-causal synthesis gives more flexibility than the causal one, because it allows to place a new patch onto an output location independent of previous ones and results in arbitrary-shaped overlapping areas. Hence, an optimum cut can separate patches more freely and often has an encircled arbitrary shape. In this case, only the portion inside the cut remains as part of the synthetic image (See Fig 5.8 ). In determining a new cut, this methods also accounts for old cuts in the overlapping area [59].

The synthesis procedure is similar to a best-first search problem, which selects and cuts the patch that has currently the best evaluation according to a heuristic function. Since the approach doesn't necessarily yield the best global solution, an iterative scheme should also be considered to refine the result towards a optimal global function.

Finding an optimal cut has been formulated by a well established technique of graph cut in graph theory. Image quilting [28] exploits one-dimensional graph cut, i.e. each cut only goes one direction, while this method involves a two-dimensional case, i.e. each cut goes arbitrarily on a 2D plane. The graph cut algorithm have a worst-case computational complexity of $O(n^2)$ and an average of $O(n\log n)$ for a graph with $n$ nodes [59].

Three methods for selecting patches are investigated in [59]. The simplest and the fastest method is random placement, which places the entire input image into the output image lattice with a random shift each time. The second method, entire patch matching, finds the best transition of the input image by minimising a normalised SSD of the overlapping area between an input and an output images. The third method, sub-patch matching, searches an input image for the best match that minimises a certain distance function between two patches, which is similar to both the patch-based method [65] and image quilting [28].