Median Cut Algorithm
What is Median Cut?
Median cut is an algorithm to sort data of an arbitrary number of dimensions into series of sets by recursively cutting each set of data at the median point along the longest dimension. Median cut is typically used for color quantization.
Reducing the color space using median cut provides a reduction in size for some image formats. From the example below we can see the quality vs size trade-off for the PNG image.
What is Color Quantization?
Color Quantization is the process of reducing the number of distinct colors used in an image. Color quantization is critical for displaying images with many colors on devices that can only display a limited number of colors, it also enables efficient compression of certain types of images.
Color Quantization and GIF
The Graphical Interchange Format (GIF) image we use only supports 8bits per pixel that is 256 colors while something like JPEG supports 16 million colors. Color Quantization algorithms like the Median Cut Algorithm helps us to reduce the color space from 16 million to 256.
Median Cut Algorithm
- Find the smallest box containing all the colors in the image.
- Sort the color codes along the longest axis of the box (Sort the pixels on the color axis with the highest range).
- Split the box into two regions at the median of the sorted list.
- Repeat the above process until the original color space has been divided into desired regions (Eg 64).
- Replace each pixel with the color with least euclidean distance from the generated color pallet.
Code
The following github repository contains the Code for a Java application that takes a “P6” PPM(Portable Pixel Map) image as an input and generates a color pallet of desired size and reduces the color space of the image using it. https://github.com/manasjain0405/median-cut
