How to Extract Image Theme Colors in Real-Time with Canvas: Median Cut vs Octree

1. Introduction

Theme colors in images improve visual harmony on pages and are useful for image classification and search. Traditionally the extraction runs on the backend, but the latency of uploading, processing, and returning results can be noticeable.

2. Theme Color Algorithms

Common algorithms include minimum‑difference, median‑cut, octree, clustering, and color‑modeling. The article focuses on median‑cut and octree because they can be implemented in JavaScript without heavy numerical libraries.

Median‑Cut Algorithm

The algorithm treats each pixel as a point in a 3‑D RGB space, repeatedly splits the longest color dimension at its median, and stops when the desired number of boxes is reached; the box centers become the theme colors.

To avoid boxes with large volume but few pixels, boxes are prioritized by

volume * pixelCount

before splitting.

Octree Algorithm

The octree method converts each RGB component to binary, builds an 8‑branch tree, and merges nodes until the required number of colors is obtained. It generally yields higher accuracy but is slower due to recursive insertion.

3. Implementation (JavaScript)

<code>function themeColor(img, callback) {
  var canvas = document.createElement('canvas'),
      ctx = canvas.getContext('2d'),
      width = img.width,
      height = img.height,
      imageData = ctx.getImageData(0,0,width,height).data,
      total = imageData.length/4;
  // ... median‑cut implementation ...
  // ... octree implementation ...
  callback(colorArray);
}
window.themeColor = themeColor;</code>

The code defines a

ColorBox

class, a quick‑sort helper, and functions for cutting boxes, building the octree, and extracting median colors. It processes the pixel data obtained from the canvas and returns an array of RGB triples.

4. Practical Results

After testing 10,000 images, the median‑cut method averaged 70‑130 ms per image, while the octree method took 160‑400 ms. Image loading time (~450 ms) dominates the total latency.

Color accuracy was about 76 % compared with the CGI results; some images showed distinct but equally valid theme colors.

5. Conclusion

Canvas‑based median‑cut extraction provides results close to server‑side algorithms with considerably lower latency. Octree offers higher fidelity at the cost of speed. Further optimizations such as down‑sampling, reduced canvas size, and smarter cut‑point selection can improve performance.

References

http://acm.nudt.edu.cn/~twcourse/ColorQuantization.html https://xcoder.in/2014/09/17/theme-color-extract/ http://blog.rainy.im/2015/11/24/extract-color-themes-from-images/ https://xinyo.org/archives/66115 https://xinyo.org/archives/66352 https://github.com/lokesh/color-thief/ http://y.qq.com/m/demo/2018/magic_color.html