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.