The Median Cut Algorithm for Color Quantization

Your eyes can see a massive range of possible colors, but computer images use reduced color palettes to represent most of the colors we can see in a reasonable amount of space. The median cut algorithm is a popular and simple way to reduce the number of colors in an image.

Images in JPEG format support 16 million colors, a good approximation to the natural range of human vision.

The same image in GIF format, which supports only 256 colors. You can see bands of flat color where regions have been reduced to an average for a range.

The color space of a computer image can be represented as a cube, with red, green and blue as axes. The color of a pixel in an image is represented by a coordinate within that cube. Median cut works by partitioning the cube into regions of similar colors. All pixels within a partition are assigned a common color.

The first step is to choose which dimension to partition. We want the colors that are closest together to end up in a group, so we choose the dimension with the greatest range between minimum and maximum value to split in two. The initial group of pixels is broken into its red, green and blue channel values, and the range of values and the average value of each channel is calculated. The channel with the greatest range is chosen to split.

A rectangular region is calculated from the existing minimum and maximum for each channel in the group, with the dimension being split fixed to the median value of that channel. The pixels with channel values greater than or less than the median are sorted into two new groups, replacing the original group.

This process is repeated until the desired number of colors is reached. Then the pixels in each group are assigned the average color of the group, and the image is redrawn.

The same image reduced to 16 colors.

The palette of the 16 color images with HTML color codes.

Thank you for coming to my TED talk.