Abstract

We present an algorithm for extracting color themes from digital images, which is crucial for automating the design process. The algorithm uses the HSV color space and a bucket sort with binary search to achieve up to 98% accuracy on a dataset of 113 images with a runtime of 157 milliseconds per image, representing a 63x gain in runtime compared to human processing.

1. Introduction

Color is a primary factor in product design and significantly impacts various areas, including sales, marketing, and customer emotions ( Citation: Sigh, 2006 Sigh, S. (2006). Impact of color on marketing. Management decision, 44(6). 783–789. ) . While it may seem like a color palette is subjective and only related to personal preference, designers actually rely heavily on color theory to make their decisions.

Modern color theory is largely based on Isaac Newton’s color wheel ( Citation: Newton, 1730 Newton, I. (1730). Opticks: Or, A Treatise of the Reflections, Refractions, Inflections and Colours of Light. William Innys at the West-End of St.Paul's. ) , which illustrates the relationship between colors. Unlike RGB, the color wheel is in the HSV color space, which is essentially a cylindrical coordinate system where hue, saturation, and value are related to degree, radius, and height, respectively. The cross-section of the cylinder represents the color wheel.

Color themes are combinations of colors on the color wheel. For example, as shown in Fig. 1, an analogous color theme can be created by selecting adjacent colors, while a complementary color theme consists of two colors that are directly across from each other.

2. Main challenge

When designing a product composed of different fabrics, the designer relies on color themes of each fabric, as shown in Fig. 2, which are manually extracted by other workers. This process is time-consuming and costly. To expedite the design process, it is crucial to find a way to extract color themes automatically.

Although the theory behind color themes is mature and there are commercial tools available, such as Adobe Color Wheel and Pantone Connect, that can generate color themes or extract colors from imported images, these tools are still unable to identify color themes directly from images and do not provide an API. As a result, automating the design process with these tools is impossible.

When designing a product, the designer should consider the color theme of the fabric. In this example, the complementary colors are dark green and pink. Therefore, the strap, zipper, and other fabric of the product should also match this color theme.

3. Program

To implement our own algorithm, the first step is to analyze the problem. This can be broken down into three parts:

1. Converting the RGB channels of the digital image into HSV format.
2. Defining color themes quantitatively.
3. Implementing a search algorithm to check if colors match the defined themes.

3.1. Color Conversion

While it is possible to implement the conversion algorithm based on recent work ( Citation: Chernov, 2015 Chernov, V. (2015). Integer-based accurate conversion between RGB and HSV color spaces. Computers & Electrical Engineering, 46. 328–337. ) , which claims to be faster and more accurate than classical methods. Conversion using an image processing package like OpenCV is already fast enough for our purposes.

3.2. Quantitative definition of a theme

Since visual artwork rarely consists of only a single color, it is more appropriate to use intervals to describe a range of colors. By considering the relative position of each interval, we can define a theme. As a result, a color theme can be described using three parameters:

• The number of intervals
• The range of each interval
• The relative position of each interval

For example, in Fig. 1, the triadic theme consists of three intervals, each with a relative position of 120 degrees and a range that can start from 15 to 100.

3.3. Search algorithm

Before delving into the algorithm, it is important to consider the constraints of the problem. According to the HSV color space, colors are confined to a range between 0 and 359. Additionally, in our dataset, we resize all images to 100 x 140 pixels, striking a balance between runtime and accuracy. Taking monochrome, analogous, complementary, and triadic themes into account, there are 22,680 possible themes when considering all combinations of numbers and ranges in intervals.

Constraints:

• 0 ≤ color ≤ 359
• 1 ≤ len(color) ≤ 14000
• len(theme) = 22680

In the following analysis, we use the notations $N$ and $K$ to represent the lengths of the “colors” and “themes” lists, respectively.

3.3.1. Naive approach

A naive approach would be to iterate through all colors and theme until finding the correct one. Here’s how the algorithm works:

• Iterate through all themes.
  • At each iteration, we iterate through all colors.
  • Check if theme covers all colors.
    • If it does, return it.
    • Otherwise, we move on to the next one.

The time complexity is $O(NK)$. Although we need extra memory to store the number of colors in each interval during each iteration, the space complexity remains $O(1)$ since it only depends on the number of intervals in each theme.

3.3.2. Optimized approach using Bucket sort

Since there are upper and lower bound of color, the problem can be optimized using a bucket sort with binary search.

Here’s the basic idea of the algorithm:

• To divide the range of colors (0~360) into “buckets”, select a bucket size. For example, if the bucket size is 10, there will be 36 buckets in total.
• Iterate through each color and use binary search to find the correct bucket.
• Merge adjacent and non-empty buckets.
• Iterate through all themes.
  • At each iteration, iterate through all merged buckets.
  • Check if the theme covers all buckets.
    • If it does, return it.
    • Otherwise, move on to the next one.

Assuming that $B$ represents the number of buckets, the time complexity of this algorithm is $O(NlogB + BK)$, where $NlogB$ comes from bucket sort with binary search. The space complexity is $O(B)$. The bucket size is considered a hyperparameter. In practice, a bucket size of 5 or 10 is sufficient to obtain accurate results. As a result, this algorithm significantly improves speed compared to a naive approach.

4. Experiment

4.1. Dataset

To test the speed and accuracy of our algorithm, we collected 113 digital images of fabric with dimensions of 3500 x 4900 pixels, as shown in Fig. 4. For the algorithm, we resized the images to 100 x 140 pixels and used a bucket size of 10.

The dataset is used in experiments involving monochrome, analogous, complementary, and triadic color themes.

To evaluate speed, we had humans judge the theme of each image using a commercial color picker and measured the time taken for each judgment. For accuracy evaluation, we used the human judgment results as the ground truth, as shown in Fig. 5.

To evaluate accuracy, we use human judgement as the ground truth. For instance, the algorithm extracted analogous, complementary, and triadic color themes from the following images, which match the result obtained from human judgement using a color picker.

4.2. Result

The algorithm only failed on 2 images, resulting in an accuracy of 98%. The reason for these failures is that the images are composed of multiple color themes. For example, the image in Fig. 6 is considered to be both complementary and analogous.

The algorithm fails to extract if the image is composed of multiple color themes.

The comparison of runtime is shown in Fig. 7. Excluding the time for importing images, the average runtime for processing a single image is 157 milliseconds for the algorithm and 10 seconds for a human. This represents a 63x gain in runtime compared to human processing. For reference, a naive approach could take up to 30 seconds, which is even slower than human processing.

5. Conclusion

We have presented an algorithm for identifying color themes that does not require any training or human annotations. The algorithm is 63 times faster than human processing and achieves up to 98% accuracy on our dataset.

Reference