Leptonica  1.83.1
Image processing and image analysis suite
colorquant2.c File Reference
#include <string.h>
#include <math.h>
#include "allheaders.h"

Go to the source code of this file.

Data Structures

struct  L_Box3d
 

Macros

#define DEBUG_MC_COLORS   0
 
#define DEBUG_SPLIT_AXES   0
 

Typedefs

typedef struct L_Box3d L_BOX3D
 

Functions

static PIXCMAPpixcmapGenerateFromHisto (PIX *pixs, l_int32 depth, l_int32 *histo, l_int32 histosize, l_int32 sigbits)
 
static PIXpixQuantizeWithColormap (PIX *pixs, l_int32 ditherflag, l_int32 outdepth, PIXCMAP *cmap, l_int32 *indexmap, l_int32 mapsize, l_int32 sigbits)
 
static void getColorIndexMedianCut (l_uint32 pixel, l_int32 rshift, l_uint32 mask, l_int32 sigbits, l_int32 *pindex)
 
static L_BOX3DpixGetColorRegion (PIX *pixs, l_int32 sigbits, l_int32 subsample)
 
static l_int32 medianCutApply (l_int32 *histo, l_int32 sigbits, L_BOX3D *vbox, L_BOX3D **pvbox1, L_BOX3D **pvbox2)
 
static PIXCMAPpixcmapGenerateFromMedianCuts (L_HEAP *lh, l_int32 *histo, l_int32 sigbits)
 
static l_int32 vboxGetAverageColor (L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits, l_int32 index, l_int32 *prval, l_int32 *pgval, l_int32 *pbval)
 
static l_int32 vboxGetCount (L_BOX3D *vbox, l_int32 *histo, l_int32 sigbits)
 
static l_int32 vboxGetVolume (L_BOX3D *vbox)
 
static L_BOX3Dbox3dCreate (l_int32 r1, l_int32 r2, l_int32 g1, l_int32 g2, l_int32 b1, l_int32 b2)
 
static L_BOX3Dbox3dCopy (L_BOX3D *vbox)
 
PIXpixMedianCutQuant (PIX *pixs, l_int32 ditherflag)
 
PIXpixMedianCutQuantGeneral (PIX *pixs, l_int32 ditherflag, l_int32 outdepth, l_int32 maxcolors, l_int32 sigbits, l_int32 maxsub, l_int32 checkbw)
 
PIXpixMedianCutQuantMixed (PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh)
 
PIXpixFewColorsMedianCutQuantMixed (PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 maxncolors, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh)
 
l_int32 * pixMedianCutHisto (PIX *pixs, l_int32 sigbits, l_int32 subsample)
 

Variables

static const l_int32 DefaultSigBits = 5
 
static const l_int32 MaxItersAllowed = 5000
 
static const l_float32 FractByPopulation = 0.85
 
static const l_int32 DifCap = 100
 

Detailed Description


 Modified median cut color quantization

     High level
         PIX              *pixMedianCutQuant()
         PIX              *pixMedianCutQuantGeneral()
         PIX              *pixMedianCutQuantMixed()
         PIX              *pixFewColorsMedianCutQuantMixed()

     Median cut indexed histogram
         l_int32          *pixMedianCutHisto()

     Static helpers
         static PIXCMAP   *pixcmapGenerateFromHisto()
         static PIX       *pixQuantizeWithColormap()
         static void       getColorIndexMedianCut()
         static L_BOX3D   *pixGetColorRegion()
         static l_int32    medianCutApply()
         static PIXCMAP   *pixcmapGenerateFromMedianCuts()
         static l_int32    vboxGetAverageColor()
         static l_int32    vboxGetCount()
         static l_int32    vboxGetVolume()
         static L_BOX3D   *box3dCreate();
         static L_BOX3D   *box3dCopy();

  Paul Heckbert published the median cut algorithm, "Color Image
  Quantization for Frame Buffer Display," in Proc. SIGGRAPH '82,
  Boston, July 1982, pp. 297-307.  See:
  http://delivery.acm.org/10.1145/810000/801294/p297-heckbert.pdf

  Median cut starts with either the full color space or the occupied
  region of color space.  If you're not dithering, the occupied region
  can be used, but with dithering, pixels can end up in any place
  in the color space, so you must represent the entire color space in
  the final colormap.

  Color components are quantized to typically 5 or 6 significant
  bits (for each of r, g and b).   Call a 3D region of color
  space a 'vbox'.  Any color in this quantized space is represented
  by an element of a linear histogram array, indexed by rgb value.
  The initial region is then divided into two regions that have roughly
  equal pixel occupancy (hence the name "median cut").  Subdivision
  continues until the requisite number of vboxes has been generated.

  But the devil is in the details of the subdivision process.
  Here are some choices that you must make:
    (1) Along which axis to subdivide?
    (2) Which box to put the bin with the median pixel?
    (3) How to order the boxes for subdivision?
    (4) How to adequately handle boxes with very small numbers of pixels?
    (5) How to prevent a little-represented but highly visible color
        from being masked out by other colors in its vbox.

  Taking these in order:
    (1) Heckbert suggests using either the largest vbox side, or the vbox
        side with the largest variance in pixel occupancy.  We choose
        to divide based on the largest vbox side.
    (2) Suppose you've chosen a side.  Then you have a histogram
        of pixel occupancy in 2D slices of the vbox.  One of those
        slices includes the median pixel.  Suppose there are L bins
        to the left (smaller index) and R bins to the right.  Then
        this slice (or bin) should be assigned to the box containing
        the smaller of L and R.  This both shortens the larger
        of the subdivided dimensions and helps a low-count color
        far from the subdivision boundary to better express itself.
    (2a) One can also ask if the boundary should be moved even
        farther into the longer side.  This is feasible if we have
        a method for doing extra subdivisions on the high count
        vboxes.  And we do (see (3)).
    (3) To make sure that the boxes are subdivided toward equal
        occupancy, use an occupancy-sorted priority queue, rather
        than a simple queue.
    (4) With a priority queue, boxes with small number of pixels
        won't be repeatedly subdivided.  This is good.
    (5) Use of a priority queue allows tricks such as in (2a) to let
        small occupancy clusters be better expressed.  In addition,
        rather than splitting near the median, small occupancy colors
        are best reproduced by cutting half-way into the longer side.

  However, serious problems can arise with dithering if a priority
  queue is used based on population alone.  If the picture has
  large regions of nearly constant color, some vboxes can be very
  large and have a sizeable population (but not big enough to get to
  the head of the queue).  If one of these large, occupied vboxes
  is near in color to a nearly constant color region of the
  image, dithering can inject pixels from the large vbox into
  the nearly uniform region.  These pixels can be very far away
  in color, and the oscillations are highly visible.  To prevent
  this, we can take either or both of these actions:

    (1) Subdivide a fraction (< 1.0) based on population, and
        do the rest of the subdivision based on the product of
        the vbox volume and its population.  By using the product,
        we avoid further subdivision of nearly empty vboxes, and
        directly target large vboxes with significant population.

    (2) Threshold the excess color transferred in dithering to
        neighboring pixels.

  Doing either of these will stop the most annoying oscillations
  in dithering.  Furthermore, by doing (1), we also improve the
  rendering of regions of nearly constant color, both with and
  without dithering.  It turns out that the image quality is
  not sensitive to the value of the parameter in (1); values
  between 0.3 and 0.9 give very good results.

  Here's the lesson: subdivide the color space into vboxes such
  that (1) the most populated vboxes that can be further
  subdivided (i.e., that occupy more than one quantum volume
  in color space) all have approximately the same population,
  and (2) all large vboxes have no significant population.
  If these conditions are met, the quantization will be excellent.

  Once the subdivision has been made, the colormap is generated,
  with one color for each vbox and using the average color in the vbox.
  At the same time, the histogram array is converted to an inverse
  colormap table, storing the colormap index in every cell in the
  vbox.  Finally, using both the colormap and the inverse colormap,
  a colormapped pix is quickly generated from the original rgb pix.

  In the present implementation, subdivided regions of colorspace
  that are not occupied are retained, but not further subdivided.
  This is required for our inverse colormap lookup table for
  dithering, because dithered pixels may fall into these unoccupied
  regions.  For such empty regions, we use the center as the rgb
  colormap value.

  This variation on median cut can be referred to as "Modified Median
  Cut" quantization, or MMCQ.  Overall, the undithered MMCQ gives
  comparable results to the two-pass Octcube Quantizer (OQ).
  Comparing the two methods on the test24.jpg painting, we see:

    (1) For rendering spot color (the various reds and pinks in
        the image), MMCQ is not as good as OQ.

    (2) For rendering majority color regions, MMCQ does a better
        job of avoiding posterization.  That is, it does better
        dividing the color space up in the most heavily populated regions.

Definition in file colorquant2.c.

Function Documentation

◆ box3dCopy()

static L_BOX3D * box3dCopy ( L_BOX3D vbox)
static

box3dCopy()

Parameters
[in]vbox
Returns
vboxc copy of vbox
Notes:
     Don't copy the sortparam.

Definition at line 1654 of file colorquant2.c.

References box3dCreate().

Referenced by medianCutApply().

◆ box3dCreate()

static L_BOX3D * box3dCreate ( l_int32  r1,
l_int32  r2,
l_int32  g1,
l_int32  g2,
l_int32  b1,
l_int32  b2 
)
static

box3dCreate()

Parameters
[in]r1,r2,g1,g2,b1,b2initial values
Returns
vbox

Definition at line 1622 of file colorquant2.c.

Referenced by box3dCopy().

◆ getColorIndexMedianCut()

static void getColorIndexMedianCut ( l_uint32  pixel,
l_int32  rshift,
l_uint32  mask,
l_int32  sigbits,
l_int32 *  pindex 
)
static

getColorIndexMedianCut()

Parameters
[in]pixel32 bit rgb
[in]rshiftof component: 8 - sigbits
[in]maskover sigbits
[in]sigbits
[out]pindexrgb index value
Returns
void
Notes:
     (1) This is used on each pixel in the source image.  No checking
         is done on input values.

Definition at line 1190 of file colorquant2.c.

◆ medianCutApply()

static l_int32 medianCutApply ( l_int32 *  histo,
l_int32  sigbits,
L_BOX3D vbox,
L_BOX3D **  pvbox1,
L_BOX3D **  pvbox2 
)
static

medianCutApply()

Parameters
[in]histoarray; in rgb colorspace
[in]sigbits
[in]vboxinput 3D box
[out]pvbox1,pvbox2vbox split in two parts
Returns
0 if OK, 1 on error

Definition at line 1277 of file colorquant2.c.

References box3dCopy(), lept_stderr(), vboxGetCount(), and vboxGetVolume().

◆ pixcmapGenerateFromHisto()

static PIXCMAP * pixcmapGenerateFromHisto ( PIX pixs,
l_int32  depth,
l_int32 *  histo,
l_int32  histosize,
l_int32  sigbits 
)
static

pixcmapGenerateFromHisto()

Parameters
[in]pixs32 bpp; rgb color
[in]depthof colormap
[in]histo
[in]histosize
[in]sigbits
Returns
colormap, or NULL on error
Notes:
     (1) This is used when the number of colors in the histo
         is not greater than maxcolors.
     (2) As a side-effect, the histo becomes an inverse colormap,
         labeling the cmap indices for each existing color.

Definition at line 899 of file colorquant2.c.

◆ pixcmapGenerateFromMedianCuts()

static PIXCMAP * pixcmapGenerateFromMedianCuts ( L_HEAP lh,
l_int32 *  histo,
l_int32  sigbits 
)
static

pixcmapGenerateFromMedianCuts()

Parameters
[in]lhpriority queue of pointers to vboxes
[in]histo
[in]sigbitsvalid: 5 or 6
Returns
cmap, or NULL on error
Notes:
     (1) Each vbox in the heap represents a color in the colormap.
     (2) As a side-effect, the histo becomes an inverse colormap,
         where the part of the array correpsonding to each vbox
         is labeled with the cmap index for that vbox.  Then
         for each rgb pixel, the colormap index is found directly
         by mapping the rgb value to the histo array index.

Definition at line 1455 of file colorquant2.c.

References lheapGetCount(), lheapRemove(), pixcmapAddColor(), pixcmapCreate(), and vboxGetAverageColor().

◆ pixFewColorsMedianCutQuantMixed()

PIX* pixFewColorsMedianCutQuantMixed ( PIX pixs,
l_int32  ncolor,
l_int32  ngray,
l_int32  maxncolors,
l_int32  darkthresh,
l_int32  lightthresh,
l_int32  diffthresh 
)

pixFewColorsMedianCutQuantMixed()

Parameters
[in]pixs32 bpp rgb
[in]ncolornumber of colors to be assigned to pixels with significant color
[in]ngraynumber of gray colors to be used; must be >= 2
[in]maxncolorsmaximum number of colors to be returned from pixColorsForQuantization(); use 0 for default
[in]darkthreshthreshold near black; if the lightest component is below this, the pixel is not considered to be gray or color; use 0 for default
[in]lightthreshthreshold near white; if the darkest component is above this, the pixel is not considered to be gray or color; use 0 for default
[in]diffthreshthresh for the max difference between component values; for differences below this, the pixel is considered to be gray; use 0 for default
Returns
pixd 8 bpp, median cut quantized for pixels that are not gray; gray pixels are quantized separately over the full gray range; null if too many colors or on error
Notes:
     (1) This is the "few colors" version of pixMedianCutQuantMixed().
         It fails (returns NULL) if it finds more than maxncolors, but
         otherwise it gives the same result.
     (2) Recommended input parameters are:
             maxncolors:  20
             darkthresh:  20
             lightthresh: 244
             diffthresh:  15  (any higher can miss colors differing
                                slightly from gray)
     (3) Both ncolor and ngray should be at least equal to maxncolors.
         If they're not, they are automatically increased, and a
         warning is given.
     (4) If very little color content is found, the input is
         converted to gray and quantized in equal intervals.
     (5) This can be useful for quantizing orthographically generated
         images such as color maps, where there may be more than 256 colors
         because of aliasing or jpeg artifacts on text or lines, but
         there are a relatively small number of solid colors.
     (6) Example of usage:
            // Try to quantize, using default values for mixed med cut
            Pix *pixq = pixFewColorsMedianCutQuantMixed(pixs, 100, 20,
                            0, 0, 0, 0);
            if (!pixq)  // too many colors; don't quantize
                pixq = pixClone(pixs);

Definition at line 767 of file colorquant2.c.

◆ pixGetColorRegion()

static L_BOX3D * pixGetColorRegion ( PIX pixs,
l_int32  sigbits,
l_int32  subsample 
)
static

pixGetColorRegion()

Parameters
[in]pixs32 bpp; rgb color
[in]sigbitsvalid: 5, 6
[in]subsampleinteger > 0
Returns
vbox minimum 3D box in color space enclosing all pixels, or NULL on error
Notes:
     (1) Computes the minimum 3D box in color space enclosing all
         pixels in the image.

Definition at line 1222 of file colorquant2.c.

References pixGetData(), and pixGetDimensions().

◆ pixMedianCutHisto()

l_int32* pixMedianCutHisto ( PIX pixs,
l_int32  sigbits,
l_int32  subsample 
)

pixMedianCutHisto()

Parameters
[in]pixs32 bpp; rgb color
[in]sigbitsvalid: 5 or 6
[in]subsampleinteger > 0
Returns
histo 1-d array, giving the number of pixels in each quantized region of color space, or NULL on error
Notes:
     (1) Array is indexed by (3 * sigbits) bits.  The array size
         is 2^(3 * sigbits).
     (2) Indexing into the array from rgb uses red sigbits as
         most significant and blue as least.

Definition at line 837 of file colorquant2.c.

◆ pixMedianCutQuant()

PIX* pixMedianCutQuant ( PIX pixs,
l_int32  ditherflag 
)

pixMedianCutQuant()

Parameters
[in]pixs32 bpp; rgb color
[in]ditherflag1 for dither; 0 for no dither
Returns
pixd 8 bit with colormap, or NULL on error
Notes:
     (1) Simple interface.  See pixMedianCutQuantGeneral() for
         use of defaulted parameters.

Definition at line 260 of file colorquant2.c.

References pixMedianCutQuantGeneral().

◆ pixMedianCutQuantGeneral()

PIX* pixMedianCutQuantGeneral ( PIX pixs,
l_int32  ditherflag,
l_int32  outdepth,
l_int32  maxcolors,
l_int32  sigbits,
l_int32  maxsub,
l_int32  checkbw 
)

pixMedianCutQuantGeneral()

Parameters
[in]pixs32 bpp; rgb color
[in]ditherflag1 for dither; 0 for no dither
[in]outdepthoutput depth; valid: 0, 1, 2, 4, 8
[in]maxcolorsbetween 2 and 256
[in]sigbitsvalid: 5 or 6; use 0 for default
[in]maxsubmax subsampling, integer; use 0 for default; 1 for no subsampling
[in]checkbw1 to check if color content is very small, 0 to assume there is sufficient color
Returns
pixd 8 bit with colormap, or NULL on error
Notes:
     (1) maxcolors must be in the range [2 ... 256].
     (2) Use outdepth = 0 to have the output depth computed as the
         minimum required to hold the actual colors found, given
         the maxcolors constraint.
     (3) Use outdepth = 1, 2, 4 or 8 to specify the output depth.
         In that case, maxcolors must not exceed 2^(outdepth).
     (4) If there are fewer quantized colors in the image than maxcolors,
         the colormap is simply generated from those colors.
     (5) maxsub is the maximum allowed subsampling to be used in the
         computation of the color histogram and region of occupied
         color space.  The subsampling is chosen internally for
         efficiency, based on the image size, but this parameter
         limits it.  Use maxsub = 0 for the internal default, which is the
         maximum allowed subsampling.  Use maxsub = 1 to prevent
         subsampling.  In general use maxsub >= 1 to specify the
         maximum subsampling to be allowed, where the actual subsampling
         will be the minimum of this value and the internally
         determined default value.
     (6) sigbits can be 5 or 6.  There are 2^24 colors in the color space.
             sigbits     # of volume elems    # of colors in a volume elem
             --------------------------------------------------------------
                5              2^15                  2^9 = 512
                6              2^18                  2^6 = 64
         Volume in color space is measured in the number of volume elements.
     (7) If the image appears gray because either most of the pixels
         are gray or most of the pixels are essentially black or white,
         the image is trivially quantized with a grayscale colormap.  The
         reason is that median cut divides the color space into rectangular
         regions, and it does a very poor job if all the pixels are
         near the diagonal of the color space cube.

Definition at line 317 of file colorquant2.c.

Referenced by pixMedianCutQuant().

◆ pixMedianCutQuantMixed()

PIX* pixMedianCutQuantMixed ( PIX pixs,
l_int32  ncolor,
l_int32  ngray,
l_int32  darkthresh,
l_int32  lightthresh,
l_int32  diffthresh 
)

pixMedianCutQuantMixed()

Parameters
[in]pixs32 bpp; rgb color
[in]ncolormaximum number of colors assigned to pixels with significant color
[in]ngraynumber of gray colors to be used; must be >= 2
[in]darkthreshthreshold near black; if the lightest component is below this, the pixel is not considered to be gray or color; uses 0 for default
[in]lightthreshthreshold near white; if the darkest component is above this, the pixel is not considered to be gray or color; use 0 for default
[in]diffthreshthresh for the max difference between component values; for differences below this, the pixel is considered to be gray; use 0 for default
Returns
pixd 8 bpp cmapped, or NULL on error
Notes:
     (1) ncolor + ngray must not exceed 255.
     (2) The method makes use of pixMedianCutQuantGeneral() with
         minimal addition.
         (a) Preprocess the image, setting all pixels with little color
             to black, and populating an auxiliary 8 bpp image with the
             expected colormap values corresponding to the set of
             quantized gray values.
         (b) Color quantize the altered input image to n + 1 colors.
         (c) Augment the colormap with the gray indices, and
             substitute the gray quantized values from the auxiliary
             image for those in the color quantized output that had
             been quantized as black.
     (3) Median cut color quantization is relatively poor for grayscale
         images with many colors, when compared to octcube quantization.
         Thus, for images with both gray and color, it is important
         to quantize the gray pixels by another method.  Here, we
         are conservative in detecting color, preferring to use
         a few extra bits to encode colorful pixels that push them
         to gray.  This is particularly reasonable with this function,
         because it handles the gray and color pixels separately,
         using median cut color quantization for the color pixels
         and equal-bin grayscale quantization for the non-color pixels.

Definition at line 595 of file colorquant2.c.

◆ pixQuantizeWithColormap()

static PIX * pixQuantizeWithColormap ( PIX pixs,
l_int32  ditherflag,
l_int32  outdepth,
PIXCMAP cmap,
l_int32 *  indexmap,
l_int32  mapsize,
l_int32  sigbits 
)
static

pixQuantizeWithColormap()

Parameters
[in]pixs32 bpp; rgb color
[in]ditherflag1 for dither; 0 for no dither
[in]outdepthdepth of the returned pixd
[in]cmapcolormap
[in]indexmaplookup table
[in]mapsizesize of the lookup table
[in]sigbitssignificant bits in output
Returns
pixd quantized to colormap, or NULL on error
Notes:
     (1) The indexmap is a LUT that takes the rgb indices of the
         pixel and returns the index into the colormap.
     (2) If ditherflag is 1, outdepth is ignored and the output
         depth is set to 8.

Definition at line 956 of file colorquant2.c.

◆ vboxGetAverageColor()

static l_int32 vboxGetAverageColor ( L_BOX3D vbox,
l_int32 *  histo,
l_int32  sigbits,
l_int32  index,
l_int32 *  prval,
l_int32 *  pgval,
l_int32 *  pbval 
)
static

vboxGetAverageColor()

Parameters
[in]vbox3d region of color space for one quantized color
[in]histo
[in]sigbitsvalid: 5 or 6
[in]indexif >= 0, assign to all colors in histo in this vbox
[out]prval,pgval,pbvalaverage color
Returns
cmap, or NULL on error
Notes:
     (1) The vbox represents one color in the colormap.
     (2) If index >= 0, as a side-effect, all array elements in
         the histo corresponding to the vbox are labeled with this
         cmap index for that vbox.  Otherwise, the histo array
         is not changed.
     (3) The vbox is quantized in sigbits.  So the actual 8-bit color
         components are found by multiplying the quantized value
         by either 4 or 8.  We must add 0.5 to the quantized index
         before multiplying to get the approximate 8-bit color in
         the center of the vbox; otherwise we get values on
         the lower corner.

Definition at line 1509 of file colorquant2.c.

References lept_stderr().

Referenced by pixcmapGenerateFromMedianCuts().

◆ vboxGetCount()

static l_int32 vboxGetCount ( L_BOX3D vbox,
l_int32 *  histo,
l_int32  sigbits 
)
static

vboxGetCount()

Parameters
[in]vbox3d region of color space for one quantized color
[in]histo
[in]sigbitsvalid: 5 or 6
Returns
number of image pixels in this region, or 0 on error

Definition at line 1574 of file colorquant2.c.

Referenced by medianCutApply().

◆ vboxGetVolume()

static l_int32 vboxGetVolume ( L_BOX3D vbox)
static

vboxGetVolume()

Parameters
[in]vbox3d region of color space for one quantized color
Returns
quantized volume of vbox, or 0 on error

Definition at line 1606 of file colorquant2.c.

Referenced by medianCutApply().