CraGL: Computational Reality, Creativity and Graphics Lab

Efficient palette-based decomposition and recoloring of images via RGBXY-space geometry

Jianchao Tan, Jose Echevarria, Yotam Gingold
ACM Transactions on Graphics (TOG) 37(6). Presented at SIGGRAPH Asia 2018.

Paper: PDF, 600dpi images (24 MB) | PDF, full size images (42 MB)

Code: decomposition algorithm (single Python file) | full code [GitHub]

Presentation: Keynote (100M) | PDF (40M) | PDF with notes (40M)

Videos of interactive layer decomposition by palette editing:

Supplementary materials:

Our approach automatically decomposes an input color image into a sparse set of uniformly-colored additive mixing layers. Our algorithm splits decomposition into a two-level geometric problem. The first level computes the 5D RGBXY convex hull and Delaunay tessellation of the input image pixels, which simultaneously considers color and spatial relationships. Its vertices are outlined in black; the 5D simplices are difficult to visualize. Any color in the image can be reproduced via a convex combination of these vertices. The second level computes an automatically-simplified RGB convex hull whose vertices serve as a color palette. Since the RGBXY convex hull vertices lie inside the RGB convex hull, we can find mixing weights that control the color of the RGBXY vertices, and therefore the entire image. Because the RGBXY vertices are unrelated to the palette, users can edit the palette and instantly obtain new additive mixing layers. These layers can be used to reconstruct or recolor the input image. Example image from Cohen-Or et al. [2006].

Abstract:

We introduce an extremely scalable and efficient yet simple palette-based image decomposition algorithm. Given an RGB image and set of palette colors, our algorithm decomposes the image into a set of additive mixing layers, each of which corresponds to a palette color applied with varying weight. Our approach is based on the geometry of images in RGBXY-space. This new geometric approach is orders of magnitude more efficient than previous work and requires no numerical optimization. We provide an implementation of the algorithm in 48 lines of Python code. We demonstrate a real-time layer decomposition tool in which users can interactively edit the palette to adjust the layers. After preprocessing, our algorithm can decompose 6 MP images into layers in 20 milliseconds.

Fast Forward Video MP4 (1 MB) | YouTube:

BibTeX (or see the ACM Digital Library entry): 

@article{Tan:2018:EPD,
 author    = {Tan, Jianchao and Echevarria, Jose and Gingold, Yotam},
 title     = {Efficient palette-based decomposition and recoloring of images via RGBXY-space geometry},
 journal   = {ACM Transactions on Graphics (TOG)},
 volume    = {37},
 number    = {6},
 month     = dec,
 year      = {2018},
 articleno = {262},
 pages     = {262:1--262:10},
 numpages  = {10},
 issn = {0730-0301},
 doi = {10.1145/3272127.3275054},
 publisher = {ACM Press},
 address   = {New York, NY, USA},
 keywords  = {images, layers, painting, palette, generalized barycentric coordinates, convex hull, RGB, color space, recoloring, compositing, mixing}
}

Copyrighted artwork:

Funding: This work was supported in part by the United States National Science Foundation (IIS-1453018), a Google research award, and a gift from Adobe Systems Inc.