Median cut is an
algorithm to sort data of an arbitrary number of dimensions into series of sets by
recursively
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
cutting each set of data at the
median
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...
point along the longest dimension. Median cut is typically used for
color quantization
In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as v ...
. For example, to reduce a 64k-colour image to 256 colours, median cut is used to find 256 colours that match the original data well.
Implementation of color quantization
Suppose we have an image with an arbitrary number of
pixel
In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device.
In most digital display devices, pixels are the smal ...
s and want to generate a
palette of 16 colors. Put all the pixels of the image (that is, their
RGB values) in a
bucket
A bucket is typically a watertight, vertical Cylinder (geometry), cylinder or Truncation (geometry), truncated Cone (geometry), cone or square, with an open top and a flat bottom, attached to a semicircular carrying handle (grip), handle called ...
. Find out which color channel (red, green, or blue) among the pixels in the bucket has the greatest range, then sort the pixels according to that channel's values. For example, if the blue channel has the greatest range, then a pixel with an RGB value of is less than a pixel with an RGB value of , because . After the bucket has been sorted, move the upper half of the pixels into a new bucket. (It is this step that gives the median cut algorithm its name; the buckets are divided into two at the
median
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic fe ...
of the list of pixels.) Repeat the process on both buckets, giving you 4 buckets, then repeat on all 4 buckets, giving you 8 buckets, then repeat on all 8, giving you 16 buckets. Average the pixels in each bucket and you have a palette of 16 colors.
Since the number of buckets doubles with each iteration, this algorithm can only generate a palette with a number of colors that is a
power of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negative ...
. To generate, say, a 12-color palette, one might first generate a 16-color palette and merge some of the colors in some way.
See also
*
k-d tree
In computer science, a ''k''-d tree (short for ''k-dimensional tree'') is a space-partitioning data structure for organizing points in a ''k''-dimensional space. ''k''-d trees are a useful data structure for several applications, such as search ...
References
{{reflist
External links
Image quantizationMedian cut + variationsImage::Pngslimmer Perl module at CPAN
Sorting algorithms