“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