📘

Color Quantization using Median Cut

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 in that bucket
- Sort the bucket by that channel
- Split at the median index into two halves
For each bucket, compute the representative color as the mean of all pixels (rounded to integers)
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:

The algorithm starts with all 4 pixels in one bucket: [[255, 0, 0], [0, 255, 0], [0, 0, 255], [255, 255, 0]]
The bucket is split based on the color channel with the greatest range. Since the range of R (255-0) and G (255-0) is greater than B (0-255), and R has the greatest range, the pixels are sorted by R: [[0, 255, 0], [0, 0, 255], [255, 255, 0], [255, 0, 0]]
The bucket is split at the median index (2) into two halves: [[0, 255, 0], [0, 0, 255]] and [[255, 255, 0], [255, 0, 0]]. The mean of each half is computed: $[\frac{0+0}{2}, \frac{255+0}{2}, \frac{0+0}{2}] = [0, 128, 0]$ is not the mean of the first half, the actual mean is $[\frac{0+0}{2}, \frac{255+0}{2}, \frac{0+255}{2}] = [0, 128, 128]$ and $[\frac{255+255}{2}, \frac{255+0}{2}, \frac{0+0}{2}] = [255, 128, 0]$
The final output is sorted by R, then G, then B: [[0, 128, 128], [255, 128, 0]]

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

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

👑

Continue the full explanation

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

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.