![]() |
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.
[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().