 |
Leptonica 1.82.0
Image processing and image analysis suite
|
|
Leptonica 1.82.0
Image processing and image analysis suite
|
#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 PIXCMAP * | pixcmapGenerateFromHisto (PIX *pixs, l_int32 depth, l_int32 *histo, l_int32 histosize, l_int32 sigbits) |
| static PIX * | pixQuantizeWithColormap (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_BOX3D * | pixGetColorRegion (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 PIXCMAP * | pixcmapGenerateFromMedianCuts (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_BOX3D * | box3dCreate (l_int32 r1, l_int32 r2, l_int32 g1, l_int32 g2, l_int32 b1, l_int32 b2) |
| static L_BOX3D * | box3dCopy (L_BOX3D *vbox) |
| PIX * | pixMedianCutQuant (PIX *pixs, l_int32 ditherflag) |
| PIX * | pixMedianCutQuantGeneral (PIX *pixs, l_int32 ditherflag, l_int32 outdepth, l_int32 maxcolors, l_int32 sigbits, l_int32 maxsub, l_int32 checkbw) |
| PIX * | pixMedianCutQuantMixed (PIX *pixs, l_int32 ncolor, l_int32 ngray, l_int32 darkthresh, l_int32 lightthresh, l_int32 diffthresh) |
| PIX * | pixFewColorsMedianCutQuantMixed (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 |
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.
| #define DEBUG_MC_COLORS 0 |
Definition at line 239 of file colorquant2.c.
| #define DEBUG_SPLIT_AXES 0 |
Definition at line 240 of file colorquant2.c.
Definition at line 194 of file colorquant2.c.
| [in] | vbox |
Notes:
Don't copy the sortparam.
Definition at line 1678 of file colorquant2.c.
References box3dCreate().
Referenced by medianCutApply().
|
static |
| [in] | r1,r2,g1,g2,b1,b2 | initial values |
Definition at line 1646 of file colorquant2.c.
Referenced by box3dCopy().
|
static |
| [in] | pixel | 32 bit rgb |
| [in] | rshift | of component: 8 - sigbits |
| [in] | mask | over sigbits |
| [in] | sigbits | |
| [out] | pindex | rgb index value |
Notes:
(1) This is used on each pixel in the source image. No checking
is done on input values.
Definition at line 1202 of file colorquant2.c.
|
static |
| [in] | histo | array; in rgb colorspace |
| [in] | sigbits | |
| [in] | vbox | input 3D box |
| [out] | pvbox1,pvbox2 | vbox split in two parts |
Definition at line 1291 of file colorquant2.c.
References box3dCopy(), lept_stderr(), vboxGetCount(), and vboxGetVolume().
|
static |
| [in] | pixs | 32 bpp; rgb color |
| [in] | depth | of colormap |
| [in] | histo | |
| [in] | histosize | |
| [in] | sigbits |
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 907 of file colorquant2.c.
|
static |
pixcmapGenerateFromMedianCuts()
| [in] | lh | priority queue of pointers to vboxes |
| [in] | histo | |
| [in] | sigbits | valid: 5 or 6 |
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 1471 of file colorquant2.c.
References lheapGetCount(), lheapRemove(), pixcmapAddColor(), pixcmapCreate(), and vboxGetAverageColor().
| PIX * pixFewColorsMedianCutQuantMixed | ( | PIX * | pixs, |
| l_int32 | ncolor, | ||
| l_int32 | ngray, | ||
| l_int32 | maxncolors, | ||
| l_int32 | darkthresh, | ||
| l_int32 | lightthresh, | ||
| l_int32 | diffthresh | ||
| ) |
pixFewColorsMedianCutQuantMixed()
| [in] | pixs | 32 bpp rgb |
| [in] | ncolor | number of colors to be assigned to pixels with significant color |
| [in] | ngray | number of gray colors to be used; must be >= 2 |
| [in] | maxncolors | maximum number of colors to be returned from pixColorsForQuantization(); use 0 for default |
| [in] | darkthresh | threshold near black; if the lightest component is below this, the pixel is not considered to be gray or color; use 0 for default |
| [in] | lightthresh | threshold near white; if the darkest component is above this, the pixel is not considered to be gray or color; use 0 for default |
| [in] | diffthresh | thresh for the max difference between component values; for differences below this, the pixel is considered to be gray; use 0 for default |
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 771 of file colorquant2.c.
| [in] | pixs | 32 bpp; rgb color |
| [in] | sigbits | valid: 5, 6 |
| [in] | subsample | integer > 0 |
Notes:
(1) Computes the minimum 3D box in color space enclosing all
pixels in the image.
Definition at line 1234 of file colorquant2.c.
References pixGetData(), and pixGetDimensions().
| l_int32 * pixMedianCutHisto | ( | PIX * | pixs, |
| l_int32 | sigbits, | ||
| l_int32 | subsample | ||
| ) |
| [in] | pixs | 32 bpp; rgb color |
| [in] | sigbits | valid: 5 or 6 |
| [in] | subsample | integer > 0 |
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 843 of file colorquant2.c.
| [in] | pixs | 32 bpp; rgb color |
| [in] | ditherflag | 1 for dither; 0 for no dither |
Notes:
(1) Simple interface. See pixMedianCutQuantGeneral() for
use of defaulted parameters.
Definition at line 260 of file colorquant2.c.
References pixMedianCutQuantGeneral().
| PIX * pixMedianCutQuantGeneral | ( | PIX * | pixs, |
| l_int32 | ditherflag, | ||
| l_int32 | outdepth, | ||
| l_int32 | maxcolors, | ||
| l_int32 | sigbits, | ||
| l_int32 | maxsub, | ||
| l_int32 | checkbw | ||
| ) |
| [in] | pixs | 32 bpp; rgb color |
| [in] | ditherflag | 1 for dither; 0 for no dither |
| [in] | outdepth | output depth; valid: 0, 1, 2, 4, 8 |
| [in] | maxcolors | between 2 and 256 |
| [in] | sigbits | valid: 5 or 6; use 0 for default |
| [in] | maxsub | max subsampling, integer; use 0 for default; 1 for no subsampling |
| [in] | checkbw | 1 to check if color content is very small, 0 to assume there is sufficient color |
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().
| PIX * pixMedianCutQuantMixed | ( | PIX * | pixs, |
| l_int32 | ncolor, | ||
| l_int32 | ngray, | ||
| l_int32 | darkthresh, | ||
| l_int32 | lightthresh, | ||
| l_int32 | diffthresh | ||
| ) |
| [in] | pixs | 32 bpp; rgb color |
| [in] | ncolor | maximum number of colors assigned to pixels with significant color |
| [in] | ngray | number of gray colors to be used; must be >= 2 |
| [in] | darkthresh | threshold near black; if the lightest component is below this, the pixel is not considered to be gray or color; uses 0 for default |
| [in] | lightthresh | threshold near white; if the darkest component is above this, the pixel is not considered to be gray or color; use 0 for default |
| [in] | diffthresh | thresh for the max difference between component values; for differences below this, the pixel is considered to be gray; use 0 for default |
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 597 of file colorquant2.c.
|
static |
| [in] | pixs | 32 bpp; rgb color |
| [in] | ditherflag | 1 for dither; 0 for no dither |
| [in] | outdepth | depth of the returned pixd |
| [in] | cmap | colormap |
| [in] | indexmap | lookup table |
| [in] | mapsize | size of the lookup table |
| [in] | sigbits | significant bits in output |
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 966 of file colorquant2.c.
|
static |
| [in] | vbox | 3d region of color space for one quantized color |
| [in] | histo | |
| [in] | sigbits | valid: 5 or 6 |
| [in] | index | if >= 0, assign to all colors in histo in this vbox |
| [out] | prval,pgval,pbval | average color |
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 1527 of file colorquant2.c.
References lept_stderr().
Referenced by pixcmapGenerateFromMedianCuts().
|
static |
| [in] | vbox | 3d region of color space for one quantized color |
| [in] | histo | |
| [in] | sigbits | valid: 5 or 6 |
Definition at line 1594 of file colorquant2.c.
Referenced by medianCutApply().
|
static |
| [in] | vbox | 3d region of color space for one quantized color |
Definition at line 1628 of file colorquant2.c.
Referenced by medianCutApply().
|
static |
Definition at line 226 of file colorquant2.c.
|
static |
Definition at line 235 of file colorquant2.c.
|
static |
Definition at line 231 of file colorquant2.c.
|
static |
Definition at line 227 of file colorquant2.c.
1.9.3