figure 12. Detecting image regions forged using the clone brush:
(a) the original, untampered image, (b) the forged image, and
(c) the cloned regions detected by our algorithm. (imagery courtesy
of Popescu and farid.
17)
(a) Original
(b) Forged
(c) Detected forgery
figure 13. a multiscale tapestry represents an input video as
a seamless and zoomable summary image that can be used to
navigate through the video. this visualization eliminates hard
borders between frames, providing spatial continuity and also
continuous zooms to finer temporal resolutions. this figure depicts
three discrete scale levels for the film Elephants Dream (courtesy of
the Blender foundation). the lines between the scale levels indicate
the corresponding domains between scales.
for other new applications such as synthesis of 3D geometry
or stereo depth maps. For extensive detail on the matching
algorithms, image statistics, applications, and directions
for future work, consult Barnes.
4
Our research has led us to an important conclusion
about the design of image manipulation algorithms: by
understanding the natural statistics of a problem domain,
one can often customize a solution strategy around those
statistics. In our case, by understanding the correlations
between different nodes (pixels of an image), we designed
the search strategy to take advantage of these statistics. We
are excited about the potential of our techniques to accelerate search in many different domains, as well as the future
work it has opened up.
acknowledgments
We would like to thank the following Flickr users for Creative
Commons imagery: Sevenbrane (Greek temple), Wili (boys), Moi
of Ra (flowers), and Celie (pagoda). This work was sponsored in
part by Adobe Systems and the NSF grant IIS-0511965.
References
1. ashikhmin, m. synthesizing natural
textures. In I3D Proceedings (2001).
aCm, 217–226.
2. avidan, s., shamir, a. seam carving for
content-aware image resizing. ACM
Trans. Gr. (Proc. SIGGRAPH)
26, 3
(2007), 10.
3. baker, s., scharstein, d., lewis, J.,
roth, s., black, m., szeliski, r. a
database and evaluation methodology
for optical flow. In Proceedings of
ICCV, volume 5, 2007.
4. barnes, C. Patchmatch: a Fast
randomized matching algorithm with
application to Image and Video. Ph.d.
thesis. Princeton university, Princeton,
nJ. may 2011.
5. barnes, C., goldman, d.b., shechtman,
e., Finkelstein, a. Video tapestries
with continuous temporal zoom. ACM
Trans. Gr. (Proc. SIGGRAPH)
29, 3
(aug. 2010).
6. barnes, C., shechtman, e., Finkelstein,
a., goldman, d. Patchmatch: a
randomized correspondence algorithm
for structural image editing. ACM
Trans. Gr. (Proc. SIGGRAPH)
28, 3
(2009), 24.
7. barnes, C., shechtman, e., goldman,
d.b., Finkelstein, a. the generalized
Patchmatch correspondence
algorithm. In ECCV, sept. 2010.
8. Cho, t.s., butman, m., avidan, s.,
Freeman, w. the patch transform and
its applications to image editing. In
IEEE Computer Society Conference
on Computer Vision and Pattern
Recognition (CVPR), 2008.
9. efros, a.a., leung, t. K. texture
synthesis by non-parametric sampling.
IEEE ICCV 2 (1999), 1033.
10. hertzmann, a., Jacobs, C.e., oliver, n.,
Curless, b., salesin, d. Image analogies.
In ACM Transactions on Graphics (Proc.
SIGGRAPH) (2001), 327–340.
11. Jain, a., Zhong, y., dubuisson-Jolly,
m. deformable template models:
a review. Signal Process. 71, 2 (1998),
109–129.
12. Kumar, n., Zhang, l., nayar, s. K. what
is a good nearest neighbors algorithm
for finding similar patches in images?
In ECCV (2008), II, 364–378.
13. liu, C., Freeman, w. a high-quality
video denoising algorithm based
on reliable motion estimation. In
Proceedings of the ECCV, 2010.
Connelly Barnes, Princeton university,
Princeton, nJ.
Dan B Goldman, adobe systems,
seattle, wa.
14. mikolajczyk, K., schmid, C. a
performance evaluation of local
descriptors. IEEE Pattern Anal.
Mach. Intell. (PAMI)
27, 10 (2005),
1615–1630.
15. mount, d.m., arya, s. ann: a library
for approximate nearest neighbor
searching. oct. 28, 1997.
16. muja, m., lowe, d. Fast approximate
nearest neighbors with automatic
algorithm configuration. In
International Conference on
Computer Vision Theory and
Applications (VISAPP), 2009.
17. Popescu, a., Farid, h. Exposing Digital
Forgeries by Detecting Duplicated
Image Regions. technical report.
department of Computer science,
dartmouth College, 2004.
18. shapira, l., avidan, s., shamir, a.
mode-detection via median-shift.
In IEEE Computer Vision and Pattern
Recognition (CVPR) (2009), Ieee,
1909–1916.
19. simakov, d., Caspi, y., shechtman,
e., Irani, m. summarizing visual
data using bidirectional similarity.
In IEEE Computer Vision and Pattern
Recognition (CVPR), anchorage, aK,
2008.
20. sun, J., yuan, l., Jia, J., shum, h.-y.
Image completion with structure
propagation. In ACM Transactions on
Graphics (Proc. SIGGRAPH) (2005),
861–868.
21. tong, x., Zhang, J., liu, l., wang, x., guo,
b., shum, h.-y. synthesis of bidirectional
texture functions on arbitrary surfaces.
ACM Trans. Gr. (Proc. SIGGRAPH)
21, 3
(July 2002), 665–672.
22. wei, l.-y., han, J., Zhou, K., bao, h.,
guo, b., shum, h.-y. Inverse texture
synthesis. ACM Trans. Gr. (Proc.
SIGGRAPH)
27, 3 (2008).
23. wei, l.y., levoy, m. Fast texture
synthesis using tree-structured vector
quantization. In ACM Transactions on
Graphics (Proc. SIGGRAPH) (2000),
479–488.
24. wexler, y., shechtman, e., Irani, m.
space-time completion of video. IEEE
Pattern Anal. Mach. Intell. (PAMI)
29,
3 (2007), 463–476.
25. wolf, l., guttmann, m., Cohen-or, d.
non-homogeneous content-driven
video-retargeting. In IEEE ICCV,
2007.
Eli Shechtman, adobe systems,
seattle, wa.
Adam Finkelstein, Princeton university,
Princeton, nJ.