Cut-Primed Smart Copying

Image quilting [28] and graph cut[59] first select a patch and then decide which portion of a patch should be merged into the output texture accord to an optimal cut. A technique, namely, cut-primed smart copy reverses the order, which cuts the training image into tiles first followed by tessellating tiles in generating a new texture [78].

Considering an image as a graph with each pixel being a vertex, a cut is a path running through between vertices on the graph. Each cut creates a seam consisting of all the pairs of corresponding vertices separated by the cut either vertically or horizontally, as illustrated in Fig 5.9. An optimal cut should create the lest visible seam. The visibility of a seam is measured by the sum of difference of intensity between each vertex pair along the cut. So, finding an optimal cut is formulated as a shortest path search problem with seam visibility being the cost function. The problem is solved using the classical Dijkstra algorithm [78].

The optimal cuts tessellate an image into small tiles of the same shape. As shown in [78], each tile has both left-to-right and top-to-bottom symmetry, resulted from two different cuts. Therefore, two tiles can be stitched together along one of the four sides resulted from an identical cut. In the synthesis (smart copy) stage, at each step, a tile is selected from the training image and is then stitched into the output image to match existing tiles. Since the cuts minimise the seam visibility between tiles, the resulting texture should also have the minimal seam visibility.

Figure 5.9: Cut and seam: Each box represents a pixel. A cut separates every two neighbouring pixels along its path either vertically or horizontally. The pixels along the cut create a seam (grey boxes).