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).
(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,
in Figure 13. This system automatically selects and collages
b Note that Liu and Freeman13 also investigated k-NN search based on our
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