“RepFinder: finding approximately repeated scene elements for image editing” by Cheng, Zhang, Mitra, Huang and Hu

  • ©Ming-Ming Cheng, Fang-Lue Zhang, Niloy J. Mitra, Xiaolei Huang, and Shi-Min Hu




    RepFinder: finding approximately repeated scene elements for image editing



    Repeated elements are ubiquitous and abundant in both manmade and natural scenes. Editing such images while preserving the repetitions and their relations is nontrivial due to overlap, missing parts, deformation across instances, illumination variation, etc. Manually enforcing such relations is laborious and error-prone. We propose a novel framework where user scribbles are used to guide detection and extraction of such repeated elements. Our detection process, which is based on a novel boundary band method, robustly extracts the repetitions along with their deformations. The algorithm only considers the shape of the elements, and ignores similarity based on color, texture, etc. We then use topological sorting to establish a partial depth ordering of overlapping repeated instances. Missing parts on occluded instances are completed using information from other instances. The extracted repeated instances can then be seamlessly edited and manipulated for a variety of high level tasks that are otherwise difficult to perform. We demonstrate the versatility of our framework on a large set of inputs of varying complexity, showing applications to image rearrangement, edit transfer, deformation propagation, and instance replacement.


    1. Adams, A., Gelfand, N., Dolson, J., and Levoy, M. 2009. Gaussian KD-trees for fast high-dimensional filtering. ACM Trans. Graph. 28, 3, 21:1–12. Google ScholarDigital Library
    2. Ahuja, N., and Todorovic, S. 2007. Extracting texels in 2.1D natural textures. In Proc. of ICCV, 1–8.Google Scholar
    3. An, X., and Pellacini, F. 2008. Appprop: all-pairs appearance-space edit propagation. ACM Trans. Graph. 27, 3, 40: 1–9. Google ScholarDigital Library
    4. Bai, X., Li, Q. N., Latecki, L. J., Liu, W. Y., and Tu, Z. W. 2009. Shape band: A deformable object detection approach. In Proc. of CVPR, 1335–1342.Google Scholar
    5. Bai, X., Wang, J., Simons, D., and Sapiro, G. 2009. Video SnapCut: robust video object cutout using localized classifiers. In ACM Trans. Graph., ACM, 70. Google ScholarDigital Library
    6. Barnes, C., Shechtman, E., Finkelstein, A., and Goldman, D. B. 2009. Patchmatch: A randomized correspondence algorithm for structural image editing. ACM Trans. Graph. 28, 3, 24:1–11. Google ScholarDigital Library
    7. Bay, H., Ess, A., Tuytelaars, T., and Gool, L. J. V. 2008. Speeded-up robust features (SURF). Computer Vision and Image Understanding 110, 3, 346–359. Google ScholarDigital Library
    8. Belongie, S., Malik, J., and Puzicha, J. 2002. Shape matching and object recognition using shape contexts. IEEE TPAMI 24, 4, 509–522. Google ScholarDigital Library
    9. Berg, A. C., Berg, T. L., and Malik, J. 2005. Shape matching and object recognition using low distortion correspondences. In Proc. of CVPR, I: 26–33. Google ScholarDigital Library
    10. Bookstein, F. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE TPAMI 11, 6, 567–585. Google ScholarDigital Library
    11. Boykov, Y. Y., and Lea, G. F. 2006. Graph cuts and efficient N-D image segmentation. IJCV 70, 2, 109–131. Google ScholarDigital Library
    12. Brox, T., Kleinschmidt, O., and Cremers, D. 2008. Efficient nonlocal means for denoising of textural patterns. IEEE Trans. Image Processing 17, 7, 1083–1092. Google ScholarDigital Library
    13. Chen, T., Cheng, M., Tan, P., Shamir, A., and Hu, S. 2009. Sketch2Photo: internet image montage. ACM Trans. Graph. 28, 5, 124: 1–10. Google ScholarDigital Library
    14. Cho, T. S., Butman, M., Avidan, S., and Freeman, W. T. 2008. The patch transform and its applications to image editing. In Proc. of CVPR, 1–8.Google Scholar
    15. Criminisi, A., Perez, P., and Toyama, K. 2004. Region filling and object removal by exemplar-based image inpainting. IEEE Trans. Image Processing 13, 9, 1200–1212. Google ScholarDigital Library
    16. Eisemann, E., and Durand, F. 2004. Flash photography enhancement via intrinsic relighting. ACM Trans. Graph. 23, 3, 673–678. Google ScholarDigital Library
    17. Ho, J., Peter, A., Rangarajan, A., and Yang, M.-H. 2009. An algebraic approach to affine registration of point sets. In Proc. of ICCV, 1–8.Google Scholar
    18. Hoiem, D., Efros, A. A., and Hebert, M. 2005. Automatic photo pop-up. ACM Trans. Graph. 24, 3, 577–584. Google ScholarDigital Library
    19. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. Asrigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3, 1134–1141. Google ScholarDigital Library
    20. Jia, Y., Hu, S., and Martin, R. 2005. Video completion using tracking and fragment merging. The Visual Computer 21, 8, 601–610.Google ScholarCross Ref
    21. Karni, Z., Freedman, D., and Gotsman, C. 2009. Energy-based image deformation. Comput. Graph. Forum 28, 5, 1257–1268. Google ScholarDigital Library
    22. Kilthau, S. L., Drew, M. S., and Moller, T. 2002. Full search content independent block matching based on the fast fourier transform. In Proc. of ICIP, I: 669–672.Google Scholar
    23. Koffka, K. 1935. Principles of Gestalt Psychology. Lund Humphries.Google Scholar
    24. Lalonde, J.-F., Hoiem, D., Efros, A. A., Rother, C., Winn, J. M., and Criminisi, A. 2007. Photo clip art. ACM Trans. Graph. 26, 3, 3:1–10. Google ScholarDigital Library
    25. Landes, P.-E., and Soler, C. 2009. Content-Aware Texture Synthesis. Research Report RR-6959, INRIA.Google Scholar
    26. Lempitsky, V., Kohli, P., Rother, C., and Sharp, T. 2009. Image segmentation with a bounding box prior. In Proc. of ICCV, 1–8.Google Scholar
    27. Leung, T., and Malik, J. 1996. Detecting, localizing and grouping repeated scene elements from an image. In Proc. of ECCV, I:546–555. Google ScholarDigital Library
    28. Levin, A., Lischinski, D., and Weiss, Y. 2008. A closed-form solution to natural image matting. IEEE TPAMI 30, 2, 228–242. Google ScholarDigital Library
    29. Liu, Y., Collins, R. T., and Tsin, Y. 2003. A computational model for periodic pattern perception based on frieze and wallpaper groups. IEEE TPAMI 26, 3, 354–371. Google ScholarDigital Library
    30. Lowe, D. G. 2004. Distinctive image features from scale-invariant keypoints. IJCV 60, 2, 91–110. Google ScholarDigital Library
    31. McCann, J., and Pollard, N. S. 2009. Local layering. ACM Trans. Graph. 28, 3, 84:1–7. Google ScholarDigital Library
    32. Paris, S., and Durand, F. 2007. A topological approach to hierarchical segmentation using mean shift. In Proc. of CVPR, 1–8.Google Scholar
    33. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. J. 2008. Discovering structural regularity in 3D geometry. ACM Trans. Graph. 27, 3, 43:1–11. Google ScholarDigital Library
    34. Rother, C., Kolmogorov, V., and Blake, A. 2004. Grab-Cut: Interactive foreground extraction using iterated graph cuts. ACM Trans. Graph. 23, 3, 309–314. Google ScholarDigital Library
    35. Sapiro, G., Kimmel, R., and Caselles, V. 1995. Geodesic active contours. In Proc. of ICCV, 694–699. Google ScholarDigital Library
    36. Schaefer, S., McPhail, T., and Warren, J. 2006. Image deformation using moving least squares. ACM Trans. Graph. 25, 3, 533–540. Google ScholarDigital Library
    37. Shamir, A., and Avidan, S. 2009. Seam carving for media retargeting. Commun. ACM 52, 1, 77–85. Google ScholarDigital Library
    38. Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. IEEE TPAMI 22, 8, 888–905. Google ScholarDigital Library
    39. Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In Proc. of CVPR, 1–8.Google Scholar
    40. Sun, J., Yuan, L., Jia, J., and Shum, H.-Y. 2005. Image completion with structure propagation. ACM Trans. Graph. 24, 3, 861–868. Google ScholarDigital Library
    41. Thayananthan, A., Stenger, B., Torr, P. H. S., and Cipolla, R. 2003. Shape context and chamfer matching in cluttered scenes. In Proc. of CVPR, I: 127–133. Google ScholarDigital Library
    42. Xu, K., Li, Y., Ju, T., Hu, S., and Liu, T. 2009. Efficient affinity-based edit propagation using KD tree. In ACM Trans. Graph., ACM, 118: 1–6. Google ScholarDigital Library
    43. Zhang, G.-X., Cheng, M.-M., Hu, S.-M., and Martin, R. R. 2009. A shape-preserving approach to image resizing. Comput. Graph. Forum 28, 7, 1897–1906.Google ScholarCross Ref
    44. Zheng, Q., Sharf, A., Wan, G., Li, Y., Mitra, N. J., Cohen-Or, D., and Chen, B. 2010. Non-local scan consolidation for 3d urban scene. ACM Trans. Graph. 29, 3, to appear. Google ScholarDigital Library

ACM Digital Library Publication: