“Nautilus: recovering regional symmetry transformations for image editing”
Conference:
Type:
Title:
- Nautilus: recovering regional symmetry transformations for image editing
Session/Category Title: Image Texture & Completion
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Natural images often exhibit symmetries that should be taken into account when editing them. In this paper we present Nautilus — a method for automatically identifying symmetric regions in an image along with their corresponding symmetry transformations. We compute dense local similarity symmetry transformations using a novel variant of the Generalised PatchMatch algorithm that uses Metropolis-Hastings sampling. We combine and refine these local symmetries using an extended Lucas-Kanade algorithm to compute regional transformations and their spatial extents. Our approach produces dense estimates of complex symmetries that are combinations of translation, rotation, scale, and reflection under perspective distortion. This enables a number of automatic symmetry-aware image editing applications including inpainting, rectification, beautification, and segmentation, and we demonstrate state-of-the-art applications for each of them.
References:
1. Aseem Agarwala, Mira Dontcheva, Maneesh Agrawala, Steven M. Drucker, Alex Colburn, Brian Curless, David Salesin, and Michael F. Cohen. 2004. Interactive digital photomontage. ACM Transactions on Graphics 23, 3 (2004), 294–302. Google ScholarDigital Library
2. Dror Aiger, Daniel Cohen-Or, and Niloy J. Mitra. 2012. Repetition Maximization based Texture Rectification. Computer Graphics Forum 31, 2 (2012), 439–448. Google ScholarDigital Library
3. Simon Baker and Iain Matthews. 2004. Lucas-Kanade 20 Years On: A Unifying Framework. International Journal of Computer Vision 56, 3 (2004), 221–255. Google ScholarDigital Library
4. Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B Goldman. 2009. PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Transactions on Graphics 28, 3 (2009), 24.Google ScholarDigital Library
5. Connelly Barnes, Eli Shechtman, Dan B Goldman, and Adam Finkelstein. 2010. The Generalized PatchMatch Correspondence Algorithm. In Proceedings of European Conference on Computer Vision. 29–43.Google ScholarCross Ref
6. Yuri Boykov and Gareth Funka-Lea. 2006. Graph Cuts and Efficient N-D Image Segmentation. International Journal of Computer Vision 70, 2 (2006), 109–131. Google ScholarDigital Library
7. Yuri Boykov, Olga Veksler, and Ramin Zabih. 2001. Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 23, 11 (Nov. 2001), 1222–1239. Google ScholarDigital Library
8. P.J. Burt and E.H. Adelson. 1983. The laplacian pyramid as a compact image code. IEEE Transactions on Communication 31 (1983), 532–540. Google ScholarCross Ref
9. Hugo Cornelius, Michal Perd’och, Jiří Matas, and Gareth Loy. 2007. Efficient Symmetry Detection Using Local Affine Frames. In Proceedings of Scandinavian Conference on Image Analysis. 152–161. Google ScholarCross Ref
10. Corinna Cortes and Vladimir Vapnik. 1995. Support-Vector Networks. Machine Learning 20, 3 (1995). Google ScholarCross Ref
11. Soheil Darabi, Eli Shechtman, Connelly Barnes, Dan B. Goldman, and Pradeep Sen. 2012. Image Melding: Combining inconsistent images using patch-based synthesis. ACM Transactions on Graphics 31, 4 (2012), 82.Google ScholarDigital Library
12. Tali Dekel, Tomer Michaeli, Michal Irani, and William T. Freeman. 2015. Revealing and Modifying Non-local Variations in a Single Image. ACM Transactions on Graphics 34, 6 (2015), 227.Google ScholarDigital Library
13. James Hays, Marius Leordeanu, Alexei A. Efros, and Yanxi Liu. 2006. Discovering Texture Regularity as a Higher-Order Correspondence Problem. In Proceedings of European Conference on Computer Vision. Google ScholarDigital Library
14. Kaiming He and Jian Sun. 2012. Statistics of Patch Offsets for Image Completion. In Proceedings of European Conference on Computer Vision. 16–29. Google ScholarDigital Library
15. Jia-Bin Huang, Sing Bing Kang, Narendra Ahuja, and Johannes Kopf. 2014. Image Completion Using Planar Structure Guidance. ACM Transactions on Graphics 33, 4 (2014), 129.Google ScholarDigital Library
16. J. B. Huang, J. Kopf, N. Ahuja, and S. B. Kang. 2013. Transformation Guided Image Completion. In Proceedings of IEEE International Conference on Computational Photography. Google ScholarCross Ref
17. Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser. 2012. Symmetry-guided Texture Synthesis and Manipulation. ACM Transactions on Graphics 31, 3, Article 22 (June 2012), 14 pages.Google ScholarDigital Library
18. Nahum Kiryati and Yossi Gofman. 1998. Detecting Symmetry in Grey Level Images: The Global Optimization Approach. International Journal of Computer Vision 29, 1 (1998), 29–45. Google ScholarDigital Library
19. Seungkyu Lee and Yanxi Liu. 2010. Skewed Rotation Symmetry Group Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 9 (2010), 1659–1672. Google ScholarDigital Library
20. Seungkyu Lee and Yanxi Liu. 2012. Curved Glide-Reflection Symmetry Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 34, 2 (2012), 266–278. Google ScholarDigital Library
21. David Liebowitz and Andrew Zisserman. 1998. Metric Rectification for Perspective Images of Planes. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 482–488. Google ScholarCross Ref
22. D. C. Liu and J. Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming 45, 3 (1989), 503–528. Google ScholarDigital Library
23. Jingchen Liu, George Slota, Gang Zheng, Zhaohui Wu, Minwoo Park, Seungkyu Lee, Ingmar Rauschert, and Yanxi Liu. 2013. Symmetry Detection from RealWorld Images Competition 2013: Summary and Results. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops.Google ScholarDigital Library
24. S. Liu, T. T. Ng, K. Sunkavalli, M. N. Do, E. Shechtman, and N. Carr. 2015. PatchMatch-Based Automatic Lattice Detection for Near-Regular Textures. In Proceedings of IEEE International Conference on Computer Vision. 181–189. Google ScholarDigital Library
25. Yanxi Liu, Tamara Belkina, James Hays, and Roberto Lublinerman. 2008. Image Defencing. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Google Scholar
26. Yanxi Liu, Robert T. Collins, and Yanghai Tsin. 2004. A Computational Model for Periodic Pattern Perception Based on Frieze and Wallpaper Groups. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 3 (March 2004), 354–371. Google ScholarDigital Library
27. Yanxi Liu, Hagit Hel-Or, Craig S. Kaplan, and Luc Van Gool. 2009. Computational Symmetry in Computer Vision and Computer Graphics. Foundations and Trends in Computer Graphics and Vision 5, 1–2 (2009), 1–195.Google ScholarCross Ref
28. Yanxi Liu, Wen-Chieh Lin, and James Hays. 2004. Near-regular Texture Analysis and Manipulation. ACM Transactions on Graphics 23, 3 (Aug. 2004), 368–376. Google ScholarDigital Library
29. Anthony Lobay and D. A. Forsyth. 2006. Shape from Texture Without Boundaries. International Journal of Computer Vision 67, 1 (April 2006), 71–91. Google ScholarDigital Library
30. G. Loy and J.-O. Eklundh. 2006. Detecting Symmetry and Symmetric Constellations of Features. In Proceedings of European Conference on Computer Vision. 508–521. Google ScholarDigital Library
31. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 1953. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics 21, 6 (1953), 1087–1092. Google ScholarCross Ref
32. Niloy J. Mitra, Leonidas J. Guibas, and Mark Pauly. 2006. Partial and Approximate Symmetry Detection for 3D Geometry. ACM Transactions on Graphics 25, 3 (July 2006), 560–568. Google ScholarDigital Library
33. Niloy J. Mitra, Mark Pauly, Michael Wand, and Duygu Ceylan. 2012. Symmetry in 3D Geometry: Extraction and Applications. In Eurographics 2012 – State of the Art Reports, Marie-Paule Cani and Fabio Ganovelli (Eds.).Google Scholar
34. Jorge Nocedal. 1980. Updating quasi-Newton matrices with limited storage. Math. Comp. 35, 151 (1980), 773–782. Google ScholarCross Ref
35. Nobuyuki Otsu. 1979. A Threshold Selection Method from Gray-Level Histograms. IEEE Transactions on Systems, Man and Cybernetics 9, 1 (1979), 62–66. Google ScholarCross Ref
36. Minwoo Park, Kyle Brocklehurst, Robert T. Collins, and Yanxi Liu. 2009. Deformed Lattice Detection in Real-World Images Using Mean-Shift Belief Propagation. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 10 (2009), 1804–1816. Google ScholarDigital Library
37. Mark Pauly, Niloy J. Mitra, Johannes Wallner, Helmut Pottmann, and Leonidas J. Guibas. 2008. Discovering Structural Regularity in 3D Geometry. ACM Transactions on Graphics 27, 3, Article 43 (Aug. 2008), 43:1–43:11 pages.Google ScholarDigital Library
38. Patrick Pérez, Michel Gangnet, and Andrew Blake. 2003. Poisson image editing. In ACM Transactions on Graphics, Vol. 22. 313–318. Google ScholarDigital Library
39. Dan Piponi. 2004. Automatic Differentiation, C++ Templates, and Photogrammetry. Journal of graphics, GPU, and game tools 9, 4 (2004), 41–55.Google ScholarCross Ref
40. J. Pritts, O. Chum, and J. Matas. 2014. Detection, Rectification and Segmentation of Coplanar Repeated Patterns. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2973–2980.Google Scholar
41. C. Rother, V. Kolmogorov, and A. Blake. 2004. GrabCut: interactive foreground extraction using iterated graph cuts. ACM Transactions on Graphics 23, 3 (2004), 309–314. Google ScholarDigital Library
42. Yu Sun and Bir Bhanu. 2012. Reflection Symmetry-Integrated Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 34, 9 (2012), 1827–1841. Google ScholarDigital Library
43. Ching Lik Teo, Cornelia Fermüller, and Yiannis Aloimonos. 2015. Detection and Segmentation of 2D Curved Reflection Symmetric Structures.. In Proceedings of IEEE International Conference on Computer Vision. 1644–1652. Google ScholarDigital Library
44. Tinne Tuytelaars, Andreas Turina, and Luc J. Van Gool. 2003. Noncombinatorial Detection of Regular Repetitions under Perspective Skew. IEEE Transactions on Pattern Analysis and Machine Intelligence 25, 4 (2003), 418–432. Google ScholarDigital Library
45. Huisi Wu, Yu-Shuen Wang, Kun-Chuan Feng, Tien-Tsin Wong, Tong-Yee Lee, and Pheng-Ann Heng. 2010. Resizing by Symmetry-Summarization. ACM Transactions on Graphics 29, 6 (2010), 159:1–159:9.Google ScholarDigital Library
46. Z. Zhang, A. Ganesh, X. Liang, and Y. Ma. 2012. TILT: Transform Invariant Low-Rank Textures. International Journal of Computer Vision 99, 1 (2012), 1–24. Google ScholarDigital Library
