Color Quantization using Median Cut

hardPROColor SpacesComputer Vision 2

Given a list of RGB pixels and a target number of colors K, reduce the color palette using the median cut algorithm.

Algorithm:

Start with all pixels in one bucket
While the number of buckets < K:
- Find the bucket with the most pixels
- Determine which color channel (R=0, G=1, B=2) has the greatest range (max minus min) in that bucket. If channels tie, pick the lowest-numbered one (R before G before B)
- Sort the bucket by that channel (a stable sort: pixels with equal values keep their current order)
- Split at the median index $\lfloor n/2 \rfloor$ into two halves (the first half gets $\lfloor n/2 \rfloor$ pixels)
- If several buckets tie for the most pixels, split the one created earliest (a lower half counts as created before its upper half)
For each bucket, compute the representative color as the per-channel mean of all its pixels, rounded to the nearest integer using Python's built-in rounding (an exact half goes to the nearest even integer, so $0.5 \to 0$ and $127.5 \to 128$ )
Sort output colors by R, then G, then B (ascending)

Return the list of K representative colors.

Example

Input

pixels = [[255, 0, 0], [0, 255, 0], [0, 0, 255], [255, 255, 0]]
K = 2

Output

[[0, 128, 128], [255, 128, 0]]

Reasoning

Input: pixels holds 4 colors, each a triple of channel values in $[0, 255]$ : red, green, blue and yellow. K = 2 means the palette must end with exactly two buckets, so one split.
Choosing the channel: in the single starting bucket every channel spans $255 - 0 = 255$ . All three tie, so R wins the tie.
Splitting: ordered by R the bucket reads green $(0,255,0)$ , blue $(0,0,255)$ , red $(255,0,0)$ , yellow $(255,255,0)$ , with the two R = 0 pixels keeping their original order. With $n = 4$ the cut falls after $\lfloor 4/2 \rfloor = 2$ pixels: {green, blue} and {red, yellow}.
Averaging: {green, blue} gives $\left(\frac{0+0}{2}, \frac{255+0}{2}, \frac{0+255}{2}\right) = (0, 127.5, 127.5)$ , which rounds to $(0, 128, 128)$ . {red, yellow} gives $(255, 127.5, 0)$ , which rounds to $(255, 128, 0)$ .
Output: ordered by R, the result is [[0, 128, 128], [255, 128, 0]].
Notice the tie rule matters here: splitting on G instead would pair {red, blue} and {green, yellow}, giving $(128, 0, 128)$ and $(128, 255, 0)$ , a different palette.

Constraints

pixels is a list of [R, G, B] lists
K >= 1 and K <= len(pixels)
Return K colors as [R, G, B] lists (integer values)
Sort output by R, then G, then B

More from Computer Vision 2

1D Bilateral Filterhard Image Sharpening with Unsharp Maskmedium Gaussian Blurmedium Gaussian Kernel Generationeasy 2D Image Convolutioneasy

Concept primerPREVIEW

Background Knowledge

The problem of color quantization is a fundamental concept in computer vision, where the goal is to reduce the number of colors in an image while maintaining its visual integrity. The median cut algorithm is a popular method for achieving this. It works by iteratively dividing the color space into smaller regions, or "buckets," based on the distribution of pixel colors. This process involves understanding color spaces, such as RGB, and how to manipulate and analyze them.

In the context of color quantization, a color space is a mathematical model that describes the way colors are created and represented. The RGB color model, used in this problem, is an additive color model where red, green, and blue light are combined to produce a wide range of colors. Each pixel in an image is represented by a set of three values (R, G, B), which correspond to the intensity of each color channel. Understanding how to work with these color channels and how to calculate metrics like the range of values in each channel is crucial for implementing the median cut algorithm.

The concept of range in a color channel refers to the difference between the maximum and minimum values of that channel within a set of pixels. For example, if the red channel values in a bucket range from 50 to 200, the range is $200 - 50 = 150$ . Identifying the channel with the greatest range helps in deciding how to split the pixels into two groups, as it maximizes the visual distinction between the resulting groups. This is a key step in the median cut algorithm, as it aims to reduce the color palette while preserving the visual characteristics of the image.

Algorithm/Approach

The median cut algorithm follows a pattern of iterative refinement, starting with all pixels in a single bucket and repeatedly dividing the largest bucket until the desired number of colors (K) is reached. This approach involves:

Identifying the most populous bucket
Analyzing the color channels to determine the best split point
Dividing the bucket into two based on the chosen channel and split point
Repeating the process until the target number of buckets (K) is achieved

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.