Image Compositing and Editing - Computer Vision for Visual Effects - page 91

(a) (b) (c)

Figure 3.36. Reshuffling an image using bidirectional similarity. (a) An original image. (b) Con-
straints fixing certain pixels (note that the trays in the center are in new positions). (c) The
automatically created recomposition.

The result effectively synthesizes realistic texture around the original, similar to the
patch-based inpainting methods in Section 3.4.2 . If two separate images are used to
provide patches for I , the retargeted image I will resemble a seamless montage of
the inputs, similar to Section 3.3 .
However, this algorithm has one serious drawback: it is highly computation-
ally time-consuming, as well as memory-intensive, to search for the minimum-cost
patches in Equation ( 3.40 ). The algorithm can be substantially accelerated — by
factors of 20 to 100 — using an approximate nearest-neighbor algorithm proposed
by Barnes et al. called PatchMatch [ 30 ]. The approximate algorithm is based on ran-
domsampling and exploits the coherence of natural images to find good approximate
matches for the bidirectional similarity algorithm(but which could apply to any of the
block-matching algorithms discussed throughout this topic). Barnes et al. performed
several experiments on real and synthetic data to show that PatchMatch substan-
tially outperformed other algorithms conventionally used for approximate nearest
neighbors (such as [ 19 ]), to the extent that image reshuffling can be performed at
interactive rates. By restricting the search areas for the nearest neighbors, Patch-
Match also allows new effects that were difficult to obtain with the other methods in
this section, such as preserving long straight lines.
Cho et al. [ 93 ] proposed an algorithm for retargeting and reshuffling called
the patch transform at the same time as Simakov et al.'s bidirectional similarity
approach; the two methods share a similar philosophy and produce similar-looking
results. However, the patch transform uses loopy belief propagation as its optimiza-
tion engine, and explicitly constrains the output image to be composed of a disjoint
set of patches from the original image, each of which is only used once.
In the extreme case where we only consider patches of size 1 1 pixel, a retargeted

image can be thought of as a collection of pixels from the input image. That is, I (

×

x , y )

such that I ( is defined by a label . From this perspec-

tive, retargeting the image can be thought of as a label assignment problem. Pritch
et al. [ 376 ] proposed an algorithm called shift-map editing based on this concept. If
L is a labeling, that is, an assignment

(δ x , δ y ) x , y ) = I ( x + δ x , y + δ y )

at each pixel of the retargeted image,
then a cost function over labelings is defined in the same way as Equation ( 3.25 ); that
is, we create a data term E data (

(δ x , δ y )

L ( i )) that encapsulates retargeting constraints, and a

smoothness term E smoothness ( that encapsulates neighborhood constraints

for each pair of 4-neighbors. For example, to perform inpainting, the data term at

L ( i ) , L ( j ))