figure 8. constraints. the original image (a) is retargeted without constraints (b). constraints indicated by colored lines produce straight lines and the circle is scaled down to fit the limited space (c).

(a) Original
(b) Retargeted
(c) With constraints

figure 9. example using local scale tool. the user marks a source polygon (a), and then applies a nonuniform scale (b) to the polygon, while preserving texture.

(a) Building marked by user (b) Scaled up, preserving texture

arbitrary descriptors, that is, vectors computed at each pixel (useful for matching features, e.g., SIFT features that are robust to camera and lighting changes). These generalizations are simple and natural extensions of our original algorithm.

In Figure 11 we show an example of object detection. The algorithm accepts a template image to be found within a large target image. The template is then located by breaking both images into small square patches, then running our matching algorithm across all rotations and scales, with a patch descriptor that compensates for changes in lighting. Then for each template object, the resulting NNF is used to estimate the pose, after rejecting outliers due to occlusions and poor matches.

We show a second application of detecting digital forgeries made by the “clone brush” in Figure 12. When a user forges an image in this way, he or she removes an object by manually replacing it with a different region of the same image. Therefore, in the forged image some patches are duplicated in large coherent regions. We detect these by using our matching algorithm to find, for each patch, its k-nearest neighbors within the same image. Then we detect cloned regions by locating large regions in the NNF that are roughly coherent.

We finally present our video summarization system, 5 shown in Figure 13. This system automatically selects and collages b Note that Liu and Freeman13 also investigated k-NN search based on our algorithm.

figure 10. modifying architecture with reshuffling. the images contain many repetitions, so the algorithm can often produce plausible output even when subject to extreme constraints.

figure 11. Detecting objects. templates, left, are matched to the image, right. square patches are matched, searching over all rotations and scales.

video frames to produce a seamlessly zoomable visual timeline. This timeline can be used as an alternative to the simple scrollbars typically used in video players. The user can select a desired scene to move to with the mouse. Or, to see more details from a given part of the film, the user can smoothly zoom in to expose more details from that part of the film. We produce our collages using patch-based synthesis, and because of the speed of our algorithm, we can produce timelines interactively.

5. futuRe WoRk

We believe our algorithm can be extended to different search domains such as 1D (e.g., audio) and 3D geometry, and allow