Communications - November 2011

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.