Image Quilting

[28], proposed by Efros and Freeman, improves the patch-based non-parametric sampling by developing a more sophisticated technique to handle the boundary conditions between overlapped image patches. Instead of using the oversimplified blending technique [65], image quilting exploits a minimum error boundary cut to find an optimal boundary between two patches. An optimal cut defines an irregular path separating overlapping patches, so that each patch provides the synthetic texture only image signals on its side of the path (See Fig 5.7 (b)).

Formally an optimal cut is found by using dynamic programming or Dijkstra's algorithm which minimises the minimum cumulative matching error $E$ along the path [28],

$$E_{i,j}= e_{i,j}+min( E_{i-1,j-1},E_{i-1,j},E_{i-1,j+1}),$$

where $E_{i,j}$ is the cumulative error until the pixel $(i,j)$ along the path, and $e_{i,j}$ is the matching error at pixel $(i,j)$ which is given by the Euclidean distance of signal values at the pixel between two overlapping patches.

In image quilting, since the overlapping area between two rectangular patches is always along one of four sides, the optimal cut only goes either vertically or horizontally through the overlapping area. This limitation might prevent the algorithm from finding a global optimal cut.

Figure 5.8: Graph cut algorithm.