3.13. The Median Cut Algorithm   

By Paul Heckbert from Heckbert (1982)

The concept behind the median cut algorithm is to use each of the colours in the synthesised colourmap to represent an equal number of pixels in the original image. This algorithm repeatedly subdivides colour space into smaller and smaller rectangular boxes. We start with one box which tightly encloses the colours of all NI x NJ pixels from the original image. The number of different colours in the first box is dependent on the colour resolution used. Experimental results have shown that 15 bits per colour (the resolution of the histogram) is sufficient in most cases.

An iterative step - splitting a box - is applied. The box is shrunk to fit tightly around the colours it encloses, by finding the minimum and maximum values of each of the colour coordinates. Next, the process described as adaptive partitioning ( Bentley [1979]) is used to decide which way to split the box. The enclosed points are sorted along the longest dimension of the box, and segregated into two halves at the median point. Approximately equal numbers of points will fall on each side of the cutting plane.

The above step is applied recursively until K boxes are generated. (If an attempt is made to split a box containing only one point, the spare box - otherwise unused - can be reassigned to split the largest box that can be found.

Subjective tests have shown that the median cut algorithm produces better quantisers than the popularity algorithm. In some cases the difference is quite remarkable.