“Dynamic closest color warping to sort and compare palettes” by Kim and Choi

A color palette is one of the simplest and most intuitive descriptors that can be extracted from images or videos. This paper proposes a method to assess the similarity between color palettes by sorting colors. While previous palette similarity measures compare only colors without considering the overall palette combination, we sort palettes to minimize the geometric distance between colors and align them to share a common color tendency. We propose dynamic closest color warping (DCCW) to calculate the minimum distance sum between colors and the graph connecting the colors in the other palette. We evaluate the proposed palette sorting and DCCW with several datasets and demonstrate that DCCW outperforms previous methods in terms of accuracy and computing time. We validate the effectiveness of the proposed sorting technique by conducting a perceptual study, which indicates a clear preference for the results of our approach. We also demonstrate useful applications enabled by DCCW, including palette interpolation, palette navigation, and image recoloring.

1. Yağız Aksoy, Tunç Ozan Aydın, Aljoša Smolić, and Marc Pollefeys. 2017. Unmixing-Based Soft Color Segmentation for Image Manipulation. ACM Trans. Graph. 36, 2 (2017), 19:1–19:19.Google ScholarDigital Library
2. Saeed Aligholi, Gholam Reza Lashkaripour, Reza Khajavi, and Morteza Razmara. 2017. Automatic mineral identification using color tracking. Pattern Recognit. 65 (2017), 164–174.Google ScholarDigital Library
3. Leonardo Barriga-Rodríguez, Hugo Jiménez-Hernández, Alberto Soto-Cajiga, Luciano Nava-Balanzar, José-Joel González-Barbosa, Alfonso Gómez-Espinosa, and Carlos Pedraza-Ortega. 2017. A Linear Criterion to sort Color Components in Images. Ingeniería e Investigación 37 (04 2017), 91–98.Google Scholar
4. Sebastiano Battiato, Giovanni Gallo, Gaetano Impoco, and Filippo Stanco. 2004. An efficient Re-indexing algorithm for color-mapped images. IEEE Trans. Image Processing 13, 11 (2004), 1419–1423.Google ScholarDigital Library
5. Sebastiano Battiato, Francesco Rundo, and Filippo Stanco. 2007. Self Organizing Motor Maps for Color-Mapped Image Re-Indexing. IEEE Trans. Image Processing 16, 12 (2007), 2905–2915.Google ScholarDigital Library
6. Yuk-Hee Chan, Ka-Chun Lui, and Daniel Pak-Kong Lun. 2008. Compressing color-indexed images by dynamically reordering their palettes. In 2008 16th European Signal Processing Conference. IEEE, 1–5.Google Scholar
7. Huiwen Chang, Ohad Fried, Yiming Liu, Stephen DiVerdi, and Adam Finkelstein. 2015. Palette-based photo recoloring. ACM Trans. Graph. 34, 4 (2015), 139:1–139:11.Google ScholarDigital Library
8. Peng Chang and John Krumm. 1999. Object Recognition with Color Cooccurrence Histograms. In Proceedings. 1999 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 2498–2504.Google ScholarCross Ref
9. Marc Chaumont, William Puech, and Christian Lahanier. 2013. Securing color information of an image by concealing the color palette. J. Syst. Softw. 86, 3 (2013), 809–825.Google ScholarDigital Library
10. Aura Conci and Carlos Kubrusly. 2017. Distance between sets: A survey. Advances in Mathematical Sciences and Applications 26 (2017), 1–18.Google Scholar
11. Gabriela Csurka, Sandra Skaff, Luca Marchesotti, and Craig Saunders. 2010. Learning moods and emotions from color combinations. In Proceedings of the Seventh Indian Conference on Computer Vision, Graphics and Image Processing. ACM, 298–305.Google ScholarDigital Library
12. Yining Deng, B. S. Manjunath, Charles S. Kenney, Michael S. Moore, and Hyundoo Shin. 2001. An efficient color representation for image retrieval. IEEE Trans. Image Processing 10, 1 (2001), 140–147.Google ScholarDigital Library
13. Marie-Pierre Dubuisson and Anil K. Jain. 1994. A modified Hausdorff distance for object matching. In Proceedings of 12th International Conference on Pattern Recognition. IEEE, 566–568.Google Scholar
14. Hasan Sheikh Faridul, Tania Pouli, Christel Chamaret, Jürgen Stauder, Alain Trémeau, and Erik Reinhard. 2014. A Survey of Color Mapping and its Applications. In Eurographics 2014 – State of the Art Reports. The Eurographics Association, 43–67.Google Scholar
15. Dean Farnsworth. 1943. The Farnsworth-Munsell 100-Hue and Dichotomous Tests for Color Vision*. Journal of the Optical Society of America 33, 10 (Oct. 1943), 568–578.Google ScholarCross Ref
16. Pedro F. Felzenszwalb. 2001. Learning Models for Object Recognition. In Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001, Vol. 1. IEEE, 1056–1062.Google ScholarCross Ref
17. Timothy Gerstner, Doug DeCarlo, Marc Alexa, Adam Finkelstein, Yotam Gingold, and Andrew Nealen. 2012. Pixelated image abstraction. In Proceedings of the Symposium on Non-Photorealistic Animation and Rendering, NAPR. Eurographics Association, 29–36.Google ScholarDigital Library
18. Michael Gervautz and Werner Purgathofer. 1988. A Simple Method for Color Quantization: Octree Quantization. In New Trends in Computer Graphics. Springer Berlin Heidelberg, 219–231.Google Scholar
19. Oliver Giudice, Dario Allegra, Filippo Stanco, Giorgio M. Grasso, and Sebastiano Battiato. 2018. A Fast Palette Reordering Technique Based on GPU-Optimized Genetic Algorithms. In 2018 25th IEEE International Conference on Image Processing (ICIP). IEEE, 1138–1142.Google ScholarCross Ref
20. Connor Gramazio, David H. Laidlaw, and Karen B. Schloss. 2017. Colorgorical: Creating discriminable and preferable color palettes for information visualization. IEEE Trans. Vis. Comput. Graph. 23, 1 (2017), 521–530.Google ScholarDigital Library
21. Zhenyu Gu and Jian Lou. 2016. Data driven webpage color design. Comput. Aided Des. 77 (2016), 46–59.Google ScholarDigital Library
22. Andrew C. Hadenfeldt and Khalid Sayood. 1994. Compression of color-mapped images. IEEE Trans. Geoscience and Remote Sensing 32, 3 (1994), 534–541.Google ScholarCross Ref
23. Paul Heckbert. 1982. Color image quantization for frame buffer display. In Proceedings of the 9th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH. ACM, 297–307.Google ScholarDigital Library
24. Keld Helsgaun. 2000. An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126, 1 (2000), 106–130.Google ScholarCross Ref
25. Keld Helsgaun. 2009. General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1, 2-3 (2009), 119–163.Google ScholarCross Ref
26. Guosheng Hu, Zhigeng Pan, Mingmin Zhang, De Chen, Wenzhen Yang, and Jian Chen. 2014. An interactive method for generating harmonious color schemes. Color Research & Application 39, 1 (2014), 70–78.Google ScholarCross Ref
27. Ali Jahanian, Jerry Liu, Qian Lin, Daniel R. Tretter, Eamonn O’Brien-Strain, Seungyon Lee, Nic Lyons, and Jan P. Allebach. 2013. Automatic design of colors for magazine covers. In Imaging and Printing in a Web 2.0 World IV, Vol. 8664. International Society for Optics and Photonics, SPIE, 55 — 63.Google Scholar
28. Ali Jahanian, S. V. N. Vishwanathan, and Jan P. Allebach. 2015. Autonomous color theme extraction from images using saliency. In Imaging and Multimedia Analytics in a Web and Mobile World 2015, Vol. 9408. International Society for Optics and Photonics, SPIE, 940807.Google Scholar
29. Suzi Kim and Sunghee Choi. 2020. Automatic Color Scheme Extraction from Movies. In Proceedings of the 2020 International Conference on Multimedia Retrieval. ACM, 154–163.Google ScholarDigital Library
30. S. Kobayashi and L. Matsunaga. 1991. Color Image Scale. Kosdansha International.Google Scholar
31. Ayaka Kojima and Tomoko Ozeki. 2015. Color palette generation for image classification by bag-of-colors. In 2015 21st Korea-Japan Joint Workshop on Frontiers of Computer Vision (FCV). IEEE, 1–5.Google ScholarCross Ref
32. Yuki Koyama and Masataka Goto. 2018. Decomposing Images into Layers with Advanced Color Blending. Comput. Graph. Forum 37, 7 (2018), 397–407.Google ScholarCross Ref
33. Jean-Philippe Lenclos and Dominique Lenclos. 2004. Colors of the world: the geography of color. WW Norton & Company.Google Scholar
34. Vladimir I Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics doklady 10, 8 (1966), 707–710.Google Scholar
35. Munan Li. 2015. Efficiency improvement of ant colony optimization in solving the moderate LTSP. Journal of Systems Engineering and Electronics 26, 6 (2015), 1300–1308.Google ScholarCross Ref
36. Zhengqing Li, Zhengjun Zha, and Yang Cao. 2020. Deep Palette-Based Color Decomposition for Image Recoloring with Aesthetic Suggestion. In MultiMedia Modeling. Springer International Publishing, 127–138.Google Scholar
37. 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
38. Chun-Chi Lo, Yu-Chen Hu, Wu-Lin Chen, and I-Cheng Chang. 2014. Probability-based image authentication scheme for indexed color images. J. Electronic Imaging 23, 3 (2014), 033003.Google ScholarCross Ref
39. Ka-Chun Lui and Yuk-Hee Chan. 2006. An adaptive palette reordering method for compressing color-indexed image. In TENCON 2006 – 2006 IEEE Region 10 Conference. IEEE, 1–4.Google ScholarCross Ref
40. M. R. Luo, G. Cui, and B. Rigg. 2001. The development of the CIE 2000 colour-difference formula: CIEDE2000. Color Research & Application 26, 5 (2001), 340–350.Google ScholarCross Ref
41. Nicolas Mellado, David Vanderhaeghe, Charlotte Hoarau, Sidonie Christophe, Mathieu Brédif, and Loïc Barthe. 2017. Constrained palette-space exploration. ACM Trans. Graph. 36, 4 (2017), 60:1–60:14.Google ScholarDigital Library
42. Nasir D. Memon and Ayalur Venkateswaran. 1996. On ordering color maps for lossless predictive coding. IEEE Trans. Image Processing 5, 11 (1996), 1522–1527.Google ScholarDigital Library
43. Satoru Miura and Hiroaki Nishino. 2017. A Color Scheme Explorer Based on a Practical Color Design Framework. In Complex, Intelligent, and Software Intensive Systems (Advances in Intelligent Systems and Computing, Vol. 611). Springer International Publishing, 752–761.Google Scholar
44. Aleksandra Mojsilovic, Jianying Hu, and Emina Soljanin. 2002. Extraction of perceptually important colors and similarity measurement for image matching, retrieval and analysis. IEEE Trans. Image Processing 11, 11 (2002), 1238–1248.Google ScholarDigital Library
45. P. Niraimathi, M. S. Sudhakar, and K. Bhoopathy Bagan. 2012. Efficient reordering algorithm for color palette image using adaptive particle swarm technique. Appl. Soft Comput. 12, 8 (2012), 2199–2207.Google ScholarDigital Library
46. Pere Obrador. 2006. Automatic color scheme picker for document templates based on image analysis and dual problem. In Digital Publishing, Vol. 6076. SPIE, 64–73.Google Scholar
47. Peter O’Donovan, Aseem Agarwala, and Aaron Hertzmann. 2011. Color compatibility from large datasets. ACM Trans. Graph. 30, 4 (2011), 63.Google ScholarDigital Library
48. Peter O’Donovan, Aseem Agarwala, and Aaron Hertzmann. 2014. Collaborative filtering of color aesthetics. In Proceedings of the Workshop on Computational Aesthetics. ACM, 33–40.Google ScholarDigital Library
49. Michael T. Orchard and Charles A. Bouman. 1991. Color quantization of images. IEEE Trans. Signal Processing 39, 12 (1991), 2677–2690.Google ScholarDigital Library
50. Aniza Othman, Tengku Siti Meriam Tengku Wook, and Shereena M. Arif. 2016. Quantization Selection of Colour Histogram Bins to Categorize the Colour Appearance of Landscape Paintings for Image Retrieval. International Journal on Advanced Science, Engineering and Information Technology 6, 6 (2016), 930–936.Google ScholarCross Ref
51. Qianqian Pan and Stephen Westland. 2018. Comparative Evaluation of Color Differences between Color Palettes. In 26th Color and Imaging Conference Final Program and Proceedings. Society for Imaging Science and Technology, 110–115.Google ScholarCross Ref
52. Greg Pass and Ramin Zabih. 1996. Histogram refinement for content-based image retrieval. In Proceedings Third IEEE Workshop on Applications of Computer Vision. WACV’96. IEEE, 96–102.Google ScholarCross Ref
53. Huy Q. Phan, Hongbo Fu, and Antoni B. Chan. 2018. Color Orchestra: Ordering Color Palettes for Interpolation and Prediction. IEEE Trans. Vis. Comput. Graph. 24, 6 (2018), 1942–1955.Google ScholarCross Ref
54. Lai-Man Po and Ka-Man Wong. 2004. A new palette histogram similarity measure for mpeg-7 dominant color descriptor. In 2004 International Conference on Image Processing, 2004. ICIP ’04. IEEE, 1533–1536.Google Scholar
55. Jonathan Poore and Sandra L Ragan. 1994. Interior color by design: A design tool for architects, interior designers, and homeowners. Rockport Pub.Google Scholar
56. Jan Puzicha, Marcus Held, Jens Ketterer, Joachim M. Buhmann, and Dieter W. Fellner. 2000. On spatial quantization of color images. IEEE Trans. Image Processing 9, 4 (2000), 666–682.Google ScholarDigital Library
57. Yossi Rubner and Carlo Tomasi. 2001. Perceptual Metrics for Image Database Navigation. Kluwer Academic Publishers, USA.Google Scholar
58. Stan Salvador and Philip Chan. 2007. FastDTW: Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis 11, 5 (2007), 561–580.Google ScholarCross Ref
59. Francesca Samsel, Lyn Bartram, and Annie Bares. 2018a. Art affect and color: Creating engaging expressive scientific visualization. In 2018 IEEE VIS Arts Program (VISAP). IEEE, 1–9.Google Scholar
60. Francesca Samsel, Sebastian Klaassen, and David H. Rogers. 2018b. ColorMoves: Realtime Interactive Colormap Construction for Scientific Visualization. IEEE Computer Graphics and Applications 38, 1 (2018), 20–29.Google ScholarCross Ref
61. Gerald Schaefer and Lars Nolle. 2006. Quality Metric Based Colour Palette Optimisation. In 2006 International Conference on Image Processing. IEEE, 1793–1796.Google Scholar
62. Gerald Schaefer and Lars Nolle. 2009. An Optimisation Approach to Palette Reordering for Indexed Image Compression. In Applications of Soft Computing. Springer Berlin Heidelberg, 178–185.Google Scholar
63. Gerald Schaefer and Huiyu Zhou. 2009. Fuzzy clustering for colour reduction in images. Telecommunication Systems 40, 1-2 (2009), 17–25.Google ScholarDigital Library
64. Klaus Schoeffmann, David Ahlström, and Laszlo Böszörmnyi. 2012. 3D Storyboards for Interactive Visual Search. In 2012 IEEE International Conference on Multimedia and Expo. IEEE, 848–853.Google ScholarDigital Library
65. Klaus Schoeffmann, David Ahlström, and Marco A. Hudelist. 2014. 3-D Interfaces to Improve the Performance of Visual Known-Item Search. IEEE Trans. Multimedia 16, 7 (2014), 1942–1951.Google ScholarCross Ref
66. M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J.J. Merelo, and H.P. Schwefel. 2007. Parallel Problem Solving from Nature-PPSN VI: 6th International Conference, Paris, France, September 18-20 2000 Proceedings. Springer Berlin Heidelberg.Google Scholar
67. Maria Shugrina, Amlan Kar, Sanja Fidler, and Karan Singh. 2020. Nonlinear color triads for approximation, learning and direct manipulation of color distributions. ACM Trans. Graph. 39, 4 (2020), 13.Google ScholarDigital Library
68. Maria Shugrina, Jingwan Lu, and Stephen DiVerdi. 2017. Playful palette: an interactive parametric color mixer for artists. ACM Trans. Graph. 36, 4 (2017), 61:1–61:10.Google ScholarDigital Library
69. Maria Shugrina, Wenjia Zhang, Fanny Chevalier, Sanja Fidler, and Karan Singh. 2019. Color Builder: A Direct Manipulation Interface for Versatile Color Theme Authoring. In Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems. ACM, 456.Google ScholarDigital Library
70. Dong-Gyu Sim, Oh-Kyu Kwon, and Rae-Hong Park. 1999. Object matching algorithms using robust Hausdorff distance measures. IEEE Trans. Image Processing 8, 3 (1999), 425–429.Google ScholarDigital Library
71. Sandra Skaff, Luca Marchesotti, Gabriela Csurka, and Craig Saunders. 2011. A Study on Perceptually Coherent Distance Measures for Color Schemes. In 19th Color and Imaging Conference, CIC. Society for Imaging Science and Technology, 247–252.Google Scholar
72. Martin Solli and Reiner Lenz. 2010. Color Semantics for Image Indexing. In 5th European Conference on Colour in Graphics, Imaging, and Vision and 12th International Symposium on Multispectral Colour Science, CGIV. Society for Imaging Science and Technology, 353–358.Google Scholar
73. A. Spira and David Malah. 2001. Improved lossless compression of color-mapped images by an approximate solution of the traveling salesman problem. In 2001 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings. IEEE, 1797–1800.Google ScholarDigital Library
74. Elena Stepanova. 2019. The impact of color palettes on the prices of paintings. Empirical Economics 56, 2 (2019), 755–773.Google ScholarCross Ref
75. Siti Noraini Sulaiman and Nor Ashidi Mat Isa. 2010. Adaptive fuzzy-K-means clustering algorithm for image segmentation. IEEE Trans. Consumer Electronics 56, 4 (2010), 2661–2668.Google ScholarDigital Library
76. Shamik Sural, Gang Qian, and Sakti Pramanik. 2002. Segmentation and histogram generation using the HSV color space for image retrieval. In Proceedings of the 2002 International Conference on Image Processing, ICIP, Vol. 2. IEEE, 589–592.Google ScholarCross Ref
77. Jianchao Tan, Jose I. Echevarria, and Yotam I. Gingold. 2018. Efficient palette-based decomposition and recoloring of images via RGBXY-space geometry. ACM Trans. Graph. 37, 6 (2018), 262:1–262:10.Google ScholarDigital Library
78. Jianchao Tan, Jyh-Ming Lien, and Yotam I. Gingold. 2017. Decomposing Images into Layers via RGB-Space Geometry. ACM Trans. Graph. 36, 1 (2017), 7:1–7:14.Google ScholarDigital Library
79. Khang Siang Tan and Nor Ashidi Mat Isa. 2011. Color image segmentation using histogram thresholding – Fuzzy C-means hybrid approach. Pattern Recognition 44, 1 (2011), 1–15.Google ScholarDigital Library
80. Masataka Tokumaru, Noriaki Muranaka, and Shigeru Imanishi. 2002. Color design support system considering color harmony. In 2002 IEEE World Congress on Computational Intelligence. 2002 IEEE International Conference on Fuzzy Systems. FUZZIEEE’02. Proceedings, Vol. 1. IEEE, IEEE, 378–383.Google ScholarCross Ref
81. Baoyuan Wang, Yizhou Yu, Tien-Tsin Wong, Chun Chen, and Ying-Qing Xu. 2010. Data-driven image color theme enhancement. ACM Trans. Graph. 29, 6 (2010), 146.Google ScholarDigital Library
82. Ming-Ni Wu, Chia-Chen Lin, and Chin-Chen Chang. 2006. A Color Re-Indexing Scheme Using Genetic Algorithm. In Proceedings of the 6th WSEAS International Conference on Multimedia Systems & Signal Processing. World Scientific and Engineering Academy and Society (WSEAS), 125–131.Google Scholar
83. Jie Yang, Yun Chen, Stephen Westland, and Kaida Xiao. 2020. Predicting visual similarity between colour palettes. Color Research & Application 45, 3 (2020), 401–408.Google ScholarCross Ref
84. Wei-tao You, Lingyun Sun, Zhi-Yuan Yang, and Chang-yuan Yang. 2019. Automatic advertising image color design incorporating a visual color analyzer. Journal of Computer Languages 55 (2019), 100910.Google ScholarCross Ref
85. André Zaccarin and Bede Liu. 1993. A novel approach for coding color quantized images. IEEE Trans. Image Processing 2, 4 (1993), 442–453.Google ScholarDigital Library
86. Wenjun Zeng, Jin Li, and Shawmin Lei. 2000. An Efficient Color Re-Indexing Scheme for Palette-Based Compression. In Proceedings 2000 International Conference on Image Processing, Vol. 3. IEEE, 476–479.Google Scholar
87. Qing Zhang, Chunxia Xiao, Hanqiu Sun, and Feng Tang. 2017. Palette-Based Image Recoloring Using Color Decomposition Optimization. IEEE Trans. Image Processing 26, 4 (2017), 1952–1964.Google ScholarDigital Library