“Decomposing Images into Layers via RGB-Space Geometry”

  • ©Jianchao Tan, Jyh-Ming Lien, and Yotam Gingold




    Decomposing Images into Layers via RGB-Space Geometry



    In digital image editing software, layers organize images. However, layers are often not explicitly represented in the final image, and may never have existed for a scanned physical painting or a photograph. We propose a technique to decompose an image into layers. In our decomposition, each layer represents a single-color coat of paint applied with varying opacity. Our decomposition is based on the image’s RGB-space geometry. In RGB-space, the linear nature of the standard Porter-Duff [1984] “over” pixel compositing operation implies a geometric structure. The vertices of the convex hull of image pixels in RGB-space correspond to a palette of paint colors. These colors may be “hidden” and inaccessible to algorithms based on clustering visible colors. For our layer decomposition, users choose the palette size (degree of simplification to perform on the convex hull), as well as a layer order for the paint colors (vertices). We then solve a constrained optimization problem to find translucent, spatially coherent opacity for each layer, such that the composition of the layers reproduces the original image. We demonstrate the utility of the resulting decompositions for recoloring (global and local) and object insertion. Our layers can be interpreted as generalized barycentric coordinates; we compare to these and other recoloring approaches.


    1. Cristina Amati and Gabriel J. Brostow. 2010. Modeling 2.5D Plants from Ink Paintings. In Sketch-Based Interfaces and Modeling (SBIM’10). 41–48. Google ScholarDigital Library
    2. Jean-Fran Aujol and Sung Ha Kang. 2006. Color image decomposition and restoration. Journal of Visual Communication and Image Representation 17, 4 (2006), 916–928.Google ScholarCross Ref
    3. C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. 1996. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software 22, 4 (Dec. 1996), 469–483. Google ScholarDigital Library
    4. William V. Baxter, Jeremy Wendt, and Ming C. Lin. 2004. IMPaSTo: A realistic, interactive model for paint. In Non-Photorealistic Animation and Rendering (NPAR’04). 45–56. Google ScholarDigital Library
    5. Leonardo Bonanni, Xiao Xiao, Matthew Hockenberry, Praveen Subramani, Hiroshi Ishii, Maurizio Seracini, and Jurgen Schulze. 2009. Wetpaint: Scraping Through Multi-layered Images. In Proceedings of ACM SIGCHI. 571–574. Google ScholarDigital Library
    6. Adrien Bousseau, Sylvain Paris, and Frédo Durand. 2009. User-assisted Intrinsic Images. ACM Transactions on Graphics 28, 5, Article 130 (Dec. 2009), 130:1–130:10. Google ScholarDigital Library
    7. Jeffrey B. Budsberg. 2007. Pigmented Colorants: Dependency on Media and Time. Master’s thesis. Cornell Univrsity, Ithaca, New York, NY.Google Scholar
    8. Vladimir Bychkovsky, Sylvain Paris, Eric Chan, and Frédo Durand. 2011. Learning photographic global tonal adjustment with a database of input / output image pairs. In Computer Vision and Pattern Recognition (CVPR). Google ScholarDigital Library
    9. Huiwen Chang, Ohad Fried, Yiming Liu, Stephen DiVerdi, and Adam Finkelstein. 2015. Palette-based Photo Recoloring. ACM Transactions on Graphics 34, 4 (Aug. 2015), 139:1–139:11. Google ScholarDigital Library
    10. Richard M Dudley. 1974. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory 10, 3 (1974), 227–236.Google ScholarCross Ref
    11. Zeev Farbman, Raanan Fattal, Dani Lischinski, and Richard Szeliski. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Transactions on Graphics 27, 3 (2008), 67:1–67:10. Google ScholarDigital Library
    12. Hany Farid and Edward H Adelson. 1999. Separating reflections from images by use of independent component analysis. Journal of the Optical Society of America A 16, 9 (1999), 2136–2145.Google ScholarCross Ref
    13. Michael S. Floater, Géza Kós, and Martin Reimers. 2005. Mean value coordinates in 3D. Computer Aided Geometric Design 22, 7 (2005), 623–631. DOI:http://dx.doi.org/10.1016/j.cagd.2005.06.004 Google ScholarDigital Library
    14. Hongbo Fu, Shizhe Zhou, Ligang Liu, and Niloy J. Mitra. 2011. Animated construction of line drawings. ACM Transactions on Graphics 30, 6 (2011), 133. Google ScholarDigital Library
    15. Michael Garland and Paul S. Heckbert. 1997. Surface Simplification Using Quadric Error Metrics. In Proceedings of ACM SIGGRAPH. 209–216. Google ScholarDigital Library
    16. Timothy Gerstner, Doug DeCarlo, Marc Alexa, Adam Finkelstein, Yotam Gingold, and Andrew Nealen. 2013. Pixelated image abstraction with integrated user constraints. Computers 8 Graphics 37, 5 (2013), 333–347. Google ScholarDigital Library
    17. GNU Project. 2015. GNU Linear Programming Kit. (2015). http://www.gnu.org/software/glpk/glpk.html Version 4.57.Google Scholar
    18. Roger Grosse, Micah K. Johnson, Edward H. Adelson, and William T. Freeman. 2009. Ground truth dataset and baseline evaluations for intrinsic image algorithms. In International Conference on Computer Vision (ICCV’09). 2335–2342.Google Scholar
    19. Sariel Har-Peled. 1999. Geometric Approximation Algorithms and Randomized Algorithms for Planar Arrangements. Ph.D. Dissertation. Tel-Aviv University.Google Scholar
    20. Shi-Min Hu, Kun Xu, Li-Qian Ma, Bin Liu, Bi-Ye Jiang, and Jue Wang. 2013. Inverse image editing: Recovering a semantic editing history from a before-and-after image pair. ACM Transactions on Graphics 32, 6 (2013), 194. Google ScholarDigital Library
    21. Tao Ju, Scott Schaefer, and Joe Warren. 2005. Mean value coordinates for closed triangular meshes. ACM Transactions on Graphics 24, 3 (2005), 561–566. Google ScholarDigital Library
    22. Paul Kubelka. 1948. New contributions to the optics of intensely light-scattering materials. part I. Journal of the Optical Society of America 38, 5 (1948), 448–448.Google ScholarCross Ref
    23. Paul Kubelka and Franz Munk. 1931. An article on optics of paint layers. Zeitschrift für Technische Physik 12, 593–601 (1931).Google Scholar
    24. Jason Lawrence, Aner Ben-Artzi, Christopher DeCoro, Wojciech Matusik, Hanspeter Pfister, Ravi Ramamoorthi, and Szymon Rusinkiewicz. 2006. Inverse shade trees for non-parametric material representation and editing. ACM Transactions on Graphics 25, 3 (July 2006), 735–745. Google ScholarDigital Library
    25. Anat Levin, Dani Lischinski, and Yair Weiss. 2008a. A closed-form solution to natural image matting. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 2 (2008), 228–242. Google ScholarDigital Library
    26. Anat Levin, Alex Rav-Acha, and Dani Lischinski. 2008b. Spectral matting. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 10 (2008), 1699–1712. Google ScholarDigital Library
    27. Anat Levin, Assaf Zomet, and Yair Weiss. 2004. Separating reflections from a single image using local features. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR’04). 306–313.Google ScholarCross Ref
    28. Sharon Lin and Pat Hanrahan. 2013. Modeling how people extract color themes from images. In Proceedings of ACM SIGCHI. Google ScholarDigital Library
    29. Jingwan Lu, Stephen DiVerdi, Willa A. Chen, Connelly Barnes, and Adam Finkelstein. 2014. RealPigment: Paint compositing by example. In Non-Photorealistic Animation and Rendering (NPAR’14). 21–30. Google ScholarDigital Library
    30. James McCann and Nancy Pollard. 2009. Local layering. ACM Transactions on Graphics 28, 3 (2009), 84. Google ScholarDigital Library
    31. James McCann and Nancy Pollard. 2012. Soft stacking. Computer Graphics Forum 31, 2 (2012), 469–478. Google ScholarDigital Library
    32. Mathieu Nancel and Andy Cockburn. 2014. Causality: A conceptual model of interaction history. In Proceedings of ACM SIGCHI. 1777–1786. Google ScholarDigital Library
    33. Peter O’Donovan, Aseem Agarwala, and Aaron Hertzmann. 2011. Color Compatibility from Large Datasets. ACM Transactions on Graphics 30, 4, Article 63 (2011), 63:1–63:12. Google ScholarDigital Library
    34. Thomas Porter and Tom Duff. 1984. Compositing Digital Images. ACM SIGGRAPH Computer Graphics 18, 3 (1984), 253–259. Google ScholarDigital Library
    35. Christian Richardt, Jorge Lopez-Moreno, Adrien Bousseau, Maneesh Agrawala, and George Drettakis. 2014. Vectorising bitmaps into semi-transparent gradient layers. Computer Graphics Forum (Proceedings of EGSR) 33, 4 (2014), 11–19.Google ScholarDigital Library
    36. Pedro V. Sander, Xianfeng Gu, Steven J. Gortler, Hugues Hoppe, and John Snyder. 2000. Silhouette clipping. In Proceedings of ACM SIGGRAPH. 327–334. Google ScholarDigital Library
    37. Bernard Sarel and Michal Irani. 2004. Separating transparent layers through layer information exchange. In Proceedings of the European Conference on Computer Vision (ECCV’04).Google ScholarCross Ref
    38. Li Shen, Tan Ping, and Stephen Lin. 2008. Intrinsic image decomposition with non-local texture cues. In Computer Vision and Pattern Recognition (CVPR’08).Google Scholar
    39. Alvy Ray Smith and James F. Blinn. 1996. Blue screen matting. In ACM SIGGRAPH Conference Proceedings. 259–268. Google ScholarDigital Library
    40. Kartic Subr, Cyril Soler, and Frédo Durand. 2009. Edge-preserving multiscale image decomposition based on local extrema. ACM Transactions on Graphics 28, 5, Article 147 (2009), 147:1–147:9. Google ScholarDigital Library
    41. Richard Szeliski, Shai Avidan, and P. Anandan. 2000. Layer extraction from multiple images containing reflections and transparency. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR’00).Google Scholar
    42. Jianchao Tan, Marek Dvorožňák, Daniel Sýkora, and Yotam Gingold. 2015. Decomposing Time-Lapse Paintings into Layers. ACM Transactions on Graphics 34, 4 (2015), 61:1–61:10. Google ScholarDigital Library
    43. Ole Tange. 2011. GNU Parallel: The command-line power tool. Login: The USENIX Magazine 36, 1 (Feb. 2011), 42–47. http://www.gnu.org/s/parallel.Google Scholar
    44. Andrew P. Witkin. 1983. Scale-space filtering. In International Joint Conference on Artificial Intelligence. Palo Alto, 1019–1022. Google ScholarDigital Library
    45. Songhua Xu, Yingqing Xu, Sing Bing Kang, David H. Salesin, Yunhe Pan, and Heung-Yeung Shum. 2006. Animating Chinese paintings through stroke-based decomposition. ACM Transactions on Graphics 25, 2 (2006), 239–267. Google ScholarDigital Library
    46. Juyong Zhang, Bailin Deng, Zishun Liu, Giuseppe Patanè, Sofien Bouaziz, Kai Hormann, and Ligang Liu. 2014. Local barycentric coordinates. ACM Transactions on Graphics 33, 6, Article 188 (Nov. 2014), 188:1–188:12. Google ScholarDigital Library
    47. Ciyou Zhu, Richard H. Byrd, Peihuang Lu, and Jorge Nocedal. 1997. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Transactions on Mathematical Software 23, 4 (Dec. 1997), 550–560. Google ScholarDigital Library
    48. Douglas E. Zongker, Dawn M. Werner, Brian Curless, and David H. Salesin. 1999. Environment Matting and Compositing. In ACM SIGGRAPH Conference Proceedings. 205–214. Google ScholarDigital Library

ACM Digital Library Publication: