“Video recoloring via spatial-temporal geometric palettes” by Du, Lei, Xu, Tan and Gingold

Color correction and color grading are important steps in film production. Recent palette-based approaches to image recoloring have shown that a small set of representative colors provide an intuitive set of handles for color adjustment. However, a single, static palette cannot represent the time-varying colors in a video. We introduce a spatial-temporal geometry-based approach to video recoloring. Specifically, its core is a 4D skew polytope with a few vertices that approximately encloses the video pixels in color and time, which implicitly defines time-varying palettes through slicing of the 4D skew polytope at specific time values. Our geometric palette is compact, descriptive, and provides a correspondence between colors throughout the video, including topological changes when colors merge or split. Experiments show that our method produces natural, artifact-free recoloring.

1. Farhad Moghareh Abed. 2014. Pigment identification of paintings based on Kubelka-Munk theory and spectral images. Rochester Institute of Technology.Google Scholar
2. Adobe. 2020. Premiere Pro CC. https://www.adobe.com/products/premiere.htmlGoogle Scholar
3. M Afifi. 2019. Dynamic length colour palettes. Electronics Letters 55, 9 (2019), 531–533.Google ScholarCross Ref
4. Elad Aharoni-Mack, Yakov Shambik, and Dani Lischinski. 2017. Pigment-Based Recoloring of Watercolor Paintings. In NPAR (Los Angeles, USA).Google Scholar
5. Yağiz Aksoy, Tunç Ozan Aydin, Aljoša Smolić, and Marc Pollefeys. 2017. Unmixing-based soft color segmentation for image manipulation. ACM Transactions on Graphics (TOG) 36, 2 (2017), 19.Google ScholarDigital Library
6. Xiaobo An and Fabio Pellacini. 2008. AppProp: All-pairs Appearance-space Edit Propagation. ACM Trans. Graph. 27, 3, Article 40 (Aug. 2008), 9 pages.Google ScholarDigital Library
7. Raja Balasubramanian and Jan P Allebach. 1991. New approach to palette selection for color images. In Human Vision, Visual Processing, and Digital Display II, Vol. 1453. International Society for Optics and Photonics, 58–69.Google Scholar
8. Delos Baptiste, Mellado Nicolas, Vanderhaeghe David, and Cozot Remi. 2019. RGB Point Cloud Manipulation with Triangular Structures for Artistic Image Recoloring. arXiv preprint arXiv:1912.04583 (2019).Google Scholar
9. Nicolas Bonneel, Kalyan Sunkavalli, Sylvain Paris, and Hanspeter Pfister. 2013. Example-based video color grading. ACM Trans. Graph. 32, 4 (2013), 39–1.Google ScholarDigital Library
10. Ying Cao, Antoni B Chan, and Rynson WH Lau. 2017. Mining probabilistic color palettes for summarizing color use in artwork collections. In SIGGRAPH Asia 2017 Symposium on Visualization. 1–8.Google ScholarDigital Library
11. M Emre Celebi. 2011. Improving the performance of k-means for color quantization. Image and Vision Computing 29, 4 (2011), 260–271.Google ScholarDigital Library
12. Huiwen Chang, Ohad Fried, Yiming Liu, Stephen DiVerdi, and Adam Finkelstein. 2015. Palette-based Photo Recoloring. ACM Trans. Graph. 34, 4 (July 2015).Google ScholarDigital Library
13. Xiaowu Chen, Dongqing Zou, Qinping Zhao, and Ping Tan. 2012. Manifold preserving edit propagation. ACM Transactions on Graphics (TOG) 31, 6 (2012), 1–7.Google ScholarDigital Library
14. Wengang Cheng, Pengli Dou, and Dengwen Zhou. 2020. An Illumination Insensitive and Structure-Aware Image Color Layer Decomposition Method. In International Conference on Multimedia Modeling. Springer, 163–175.Google Scholar
15. Wan-Fung Cheung and Yuk-Hee Chan. 2003. Color quantization of compressed video sequences. IEEE transactions on circuits and systems for video technology 13, 3 (2003), 270–276.Google Scholar
16. Stephen DiVerdi, Jingwan Lu, Jose Echevarria, and Maria Shugrina. 2019. Generating playful palettes from images. In Proceedings of the 8th ACM/Eurographics Expressive Symposium on Computational Aesthetics and Sketch Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering. Eurographics Association, 69–78.Google Scholar
17. Sylvain Duchêne, Carlos Aliaga, Tania Pouli, and Patrick Pérez. 2017. Mixed Illumination Analysis in Single Image for Interactive Color Grading. In Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (Los Angeles, California) (NPAR ’17). ACM, New York, NY, USA, Article 10, 10 pages.Google ScholarDigital Library
18. D Duque-Arias, Santiago Velasco-Forero, Francois Goulette, Jean-Emmanuel Deschaud, and Beatriz Marcotegui. 2019. A graph-based color lines model for image analysis. In International Conference on Image Analysis and Processing. Springer, 181–191.Google ScholarDigital Library
19. Zunlei Feng, Wolong Yuan, Chunli Fu, Jie Lei, and Mingli Song. 2018. Finding intrinsic color themes in images with human visual perception. Neurocomputing 273 (2018), 395–402.Google ScholarDigital Library
20. Michael S. Floater, Geza Kos, and Martin Reimers. 2005. Mean value coordinates in 3D. Computer Aided Geometric Design (2005).Google Scholar
21. Michael Gervautz and Werner Purgathofer. 1988. A simple method for color quantization: Octree quantization. In New trends in computer graphics. Springer, 219–231.Google Scholar
22. Gary R Greenfield and Donald H House. 2003. Image recoloring induced by palette color associations. (2003).Google Scholar
23. Gary R Greenfield and Donald H House. 2005. A palette-driven approach to image color transfer. In Proceedings of the First Eurographics conference on Computational Aesthetics in Graphics, Visualization and Imaging. 91–99.Google ScholarDigital Library
24. Mairéad Grogan and Aljosa Smolic. 2020. Image Decomposition using Geometric Region Colour Unmixing. In European Conference on Visual Media Production. 1–10.Google ScholarDigital Library
25. Mingming He, Jing Liao, Dongdong Chen, Lu Yuan, and Pedro V Sander. 2019. Progressive color transfer with dense semantic correspondences. ACM Transactions on Graphics (TOG) 38, 2 (2019), 1–18.Google ScholarDigital Library
26. Hao-Zhi Huang, Kun Xu, Ralph R. Martin, Fei-Yue Huang, and Shi-Min Hu. 2016. Efficient, Edge-Aware, Combined Color Quantization and Dithering. IEEE Transactions on Image Processing 25, 3 (2016), 1152–1162.Google ScholarDigital Library
27. Yifei Huang, Sheng Qiu, Changbo Wang, and Chenhui Li. 2020. Learning Representations for High-Dynamic-Range Image Color Transfer in a Self-Supervised Way. IEEE Transactions on Multimedia (2020).Google ScholarCross Ref
28. Taehong Jeong, Myunghyun Yang, and Hyun Joon Shin. 2019. Succinct Palette and Color Model Generation and Manipulation Using Hierarchical Representation. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 1–10.Google Scholar
29. Steven G. Johnson. [n.d.]. The NLopt nonlinear-optimization package. http://github.com/stevengj/nloptGoogle Scholar
30. T Ju, S Schaefer, and J Warren. 2005. Mean value coordinates for closed triangular meshes. ACM Transactions on Graphics 24, 3 (2005), 561–566.Google ScholarDigital Library
31. Suzi Kim and Sunghee Choi. 2020. Automatic Color Scheme Extraction from Movies. In Proceedings of the 2020 International Conference on Multimedia Retrieval. 154–163.Google ScholarDigital Library
32. Yuki Koyama and Masataka Goto. 2018. Decomposing images into layers with advanced color blending. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 397–407.Google Scholar
33. Daniel C Kusswurm. 1998. Color quantizer for video sequences. In Very High Resolution and Quality Imaging III, Vol. 3308. International Society for Optics and Photonics, 105–113.Google ScholarCross Ref
34. Anat Levin, Dani Lischinski, and Yair Weiss. 2004. Colorization Using Optimization. ACM Trans. Graph. 23, 3 (Aug. 2004), 689–694.Google ScholarDigital Library
35. Sharon Lin, Matthew Fisher, Angela Dai, and Pat Hanrahan. 2017. LayerBuilder: Layer Decomposition for Interactive Image and Video Color Editing. CoRR abs/1701.03754 (2017). arXiv:1701.03754 http://arxiv.org/abs/1701.03754Google Scholar
36. Sharon Lin and Pat Hanrahan. 2013. Modeling how people extract color themes from images. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 3101–3110.Google ScholarDigital Library
37. Dani Lischinski, Zeev Farbman, Matt Uyttendaele, and Richard Szeliski. 2006. Interactive Local Adjustment of Tonal Values. ACM Trans. Graph. 25, 3 (July 2006), 646–653.Google ScholarDigital Library
38. Fujun Luan, Sylvain Paris, Eli Shechtman, and Kavita Bala. 2017. Deep photo style transfer. In Proceedings of the IEEE conference on computer vision and pattern recognition. 4990–4998.Google ScholarCross Ref
39. Abhimitra Meka, Mohammad Shafiei, Michael Zollhoefer, Christian Richardt, and Christian Theobalt. 2019. Live Illumination Decomposition of Videos. arXiv preprint arXiv:1908.01961 (2019).Google Scholar
40. Nicolas Mellado, David Vanderhaeghe, Charlotte Hoarau, Sidonie Christophe, Mathieu Brédif, and Loic Barthe. 2017. Constrained palette-space exploration. ACM Transactions on Graphics (TOG) 36, 4 (2017), 60.Google ScholarDigital Library
41. RMH Nguyen, B Price, S Cohen, and MS Brown. 2017. Group-Theme Recoloring for Multi-Image Color Consistency. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 83–92.Google Scholar
42. Peter O’Donovan, Aseem Agarwala, and Aaron Hertzmann. 2011. Color Compatibility from Large Datasets. ACM Trans. Graph. 30, 4, Article 63 (2011).Google ScholarDigital Library
43. Michael T Orchard, Charles A Bouman, et al. 1991. Color quantization of images. IEEE transactions on signal processing 39, 12 (1991), 2677–2690.Google Scholar
44. Celal Ozturk, Emrah Hancer, and Dervis Karaboga. 2014. Color image quantization: a short review and an application with artificial bee colony algorithm. Informatica 25, 3 (2014), 485–503.Google ScholarDigital Library
45. Fabio Pellacini and Jason Lawrence. 2007. AppWand: Editing Measured Materials Using Appearance-driven Optimization. ACM Trans. Graph. 26, 3, Article 54 (July 2007).Google ScholarDigital Library
46. E. Reinhard, M. Adhikhmin, B. Gooch, and P. Shirley. 2001. Color transfer between images. IEEE Computer Graphics and Applications 21, 5 (July 2001), 34–41.Google ScholarDigital Library
47. Christian Richardt, Jorge Lopez-Moreno, Adrien Bousseau, Maneesh Agrawala, and George Drettakis. 2014. Vectorising bitmaps into semi-transparent gradient layers. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 11–19.Google Scholar
48. Evgeny Roytman and Craig Gotsman. 1995. Dynamic color quantization of video sequences. IEEE Transactions on Visualization and Computer Graphics 1, 3 (1995), 274–286.Google ScholarDigital Library
49. Maria Shugrina, Amlan Kar, Sanja Fidler, and Karan Singh. 2020. Nonlinear color triads for approximation, learning and direct manipulation of color distributions. ACM Transactions on Graphics (TOG) 39, 4 (2020), 97–1.Google ScholarDigital Library
50. Jianchao Tan, Stephen DiVerdi, Jingwan Lu, and Yotam Gingold. 2019. Pigmento: Pigment-Based Image Analysis and Editing. Transactions on Visualization and Computer Graphics (TVCG) 25, 9 (2019). Google ScholarCross Ref
51. Jianchao Tan, Marek Dvorožňák, Daniel Sýkora, and Yotam Gingold. 2015. Decomposing Time-Lapse Paintings into Layers. ACM Transactions on Graphics (TOG) 34, 4 (July 2015), 61:1–61:10.Google ScholarDigital Library
52. Jianchao Tan, Jose Echevarria, and Yotam Gingold. 2018a. Efficient palette-based decomposition and recoloring of images via RGBXY-space geometry. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–10.Google ScholarDigital Library
53. Jianchao Tan, Jose Echevarria, and Yotam Gingold. 2018b. Palette-based image decomposition, harmonization, and color transfer. arXiv preprint arXiv:1804.01225 (2018).Google Scholar
54. Jianchao Tan, Jyh Ming Lien, and Yotam Gingold. 2016. Decomposing Images into Layers via RGB-Space Geometry. Acm Transactions on Graphics 36, 1 (2016), 1–14.Google ScholarDigital Library
55. Yili Wang, Yifan Liu, and Kun Xu. 2019. An Improved Geometric Approach for Palette-based Image Decomposition and Recoloring. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 11–22.Google Scholar
56. Tomihisa Welsh, Michael Ashikhmin, and Klaus Mueller. 2002. Transferring Color to Greyscale Images. ACM Trans. Graph. 21, 3 (July 2002), 277–280.Google ScholarDigital Library
57. Quan Wen and M Emre Celebi. 2011. Hard versus fuzzy c-means clustering for color quantization. EURASIP Journal on Advances in Signal Processing 2011, 1 (2011), 1–12.Google ScholarCross Ref
58. Wikipedia. 2020. Regular skew polyhedron. https://en.wikipedia.org/wiki/Regular_skew_polyhedronGoogle Scholar
59. Xiaolin Wu. 1992. Color quantization by dynamic programming and principal analysis. ACM Transactions on Graphics (TOG) 11, 4 (1992), 348–372.Google ScholarDigital Library
60. Kun Xu, Yong Li, Tao Ju, Shi-Min Hu, and Tian-Qiang Liu. 2009. Efficient Affinity-based Edit Propagation using K-D Tree. ACM Transactions on Graphics 28, 5, Article 118(2009), 118:1–118:6 pages.Google ScholarDigital Library
61. C. Yang and L. Peng. 2008. Automatic Mood-Transferring between Color Images. IEEE Computer Graphics and Applications 28, 2 (2008), 52–61. Google ScholarDigital Library
62. Q. Zhang, Y. Nie, L. Zhu, C. Xiao, and W.-S. Zheng. 2021. A Blind Color Separation Model for Faithful Palette-based Image Recoloring. IEEE Transactions on Multimedia (2021), 1–1. Conference Name: IEEE Transactions on Multimedia. Google ScholarDigital Library
63. Qing Zhang, Chunxia Xiao, Hanqiu Sun, and Feng Tang. 2017. Palette-Based Image Recoloring Using Color Decomposition Optimization. IEEE Transactions on Image Processing 26, 4 (2017), 1952–1964.Google ScholarDigital Library