Median cut is an
algorithm to sort data of an arbitrary number of dimensions into series of sets by
recursively
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
cutting each set of data at the
median
The median of a set of numbers is the value separating the higher half from the lower half of a Sample (statistics), data sample, a statistical population, population, or a probability distribution. For a data set, it may be thought of as the “ ...
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 ...
. 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 graphics, raster image, or the smallest addressable element in a dot matrix display device. In most digital display devices, p ...
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 that is attached to a semicircular carrying handle (grip), handle ...
. 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
The median of a set of numbers is the value separating the higher half from the lower half of a Sample (statistics), data sample, a statistical population, population, or a probability distribution. For a data set, it may be thought of as the “ ...
of the list of pixels.) This process can be repeated to further subdivide the set of pixels: choose a bucket to divide (e.g., the bucket with the greatest range in any color channel) and divide it into two. After the desired number of buckets have been produced, average the pixels in each bucket to get the final color palette.
See also
*
''k''-d tree
References
{{reflist
External links
Image quantizationMedian cut + variationsImage::Pngslimmer Perl module at CPANColor image quantization for frame buffer display
Sorting algorithms