lbjpeg_src(JPEG库的C源码)

/* * jquant2.c * * Copyright (C) 1991-1996, Thomas G. Lane. * This file is part of the Independent JPEG Group's software. * For conditions of distribution and use, see the accompanying README file. * * This file contains 2-pass color quantization (color mapping) routines. * These routines provide selection of a custom color map for an image, * followed by mapping of the image to that color map, with optional * Floyd-Steinberg dithering. * It is also possible to use just the second pass to map to an arbitrary * externally-given color map. * * Note: ordered dithering is not supported, since there isn't any fast * way to compute intercolor distances; it's unclear that ordered dither's * fundamental assumptions even hold with an irregularly spaced color map. */ #define JPEG_INTERNALS #include "jinclude.h" #include "jpeglib.h" #ifdef QUANT_2PASS_SUPPORTED /* * This module implements the well-known Heckbert paradigm for color * quantization. Most of the ideas used here can be traced back to * Heckbert's seminal paper * Heckbert, Paul. "Color Image Quantization for Frame Buffer Display", * Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304. * * In the first pass over the image, we accumulate a histogram showing the * usage count of each possible color. To keep the histogram to a reasonable * size, we reduce the precision of the input; typical practice is to retain * 5 or 6 bits per color, so that 8 or 4 different input values are counted * in the same histogram cell. * * Next, the color-selection step begins with a box representing the whole * color space, and repeatedly splits the "largest" remaining box until we * have as many boxes as desired colors. Then the mean color in each * remaining box becomes one of the possible output colors. * * The second pass over the image maps each input pixel to the closest output * color (optionally after applying a Floyd-Steinberg dithering correction). * This mapping is logically trivial, but making it go fast enough requires * considerable care. * * Heckbert-style quantizers vary a good deal in their policies for choosing * the "largest" box and deciding where to cut it. The particular policies * used here have proved out well in experimental comparisons, but better ones * may yet be found. * * In earlier versions of the IJG code, this module quantized in YCbCr color * space, processing the raw upsampled data without a color conversion step. * This allowed the color conversion math to be done only once per colormap * entry, not once per pixel. However, that optimization precluded other * useful optimizations (such as merging color conversion with upsampling) * and it also interfered with desired capabilities such as quantizing to an * externally-supplied colormap. We have therefore abandoned that approach. * The present code works in the post-conversion color space, typically RGB. * * To improve the visual quality of the results, we actually work in scaled * RGB space, giving G distances more weight than R, and R in turn more than * B. To do everything in integer math, we must use integer scale factors. * The 2/3/1 scale factors used here correspond loosely to the relative * weights of the colors in the NTSC grayscale equation. * If you want to use this code to quantize a non-RGB color space, you'll * probably need to change these scale factors. */ #define R_SCALE 2 /* scale R distances by this much */ #define G_SCALE 3 /* scale G distances by this much */ #define B_SCALE 1 /* and B by this much */ /* Relabel R/G/B as components 0/1/2, respecting the RGB ordering defined * in jmorecfg.h. As the code stands, it will do the right thing for R,G,B * and B,G,R orders. If you define some other weird order in jmorecfg.h, * you'll get compile errors until you extend this logic. In that case * you'll probably want to tweak the histogram sizes too. */ #if RGB_RED == 0 #define C0_SCALE R_SCALE #endif #if RGB_BLUE == 0 #define C0_SCALE B_SCALE #endif #if RGB_GREEN == 1 #define C1_SCALE G_SCALE #endif #if RGB_RED == 2 #define C2_SCALE R_SCALE #endif #if RGB_BLUE == 2 #define C2_SCALE B_SCALE #endif /* * First we have the histogram data structure and routines for creating it. * * The number of bits of precision can be adjusted by changing these symbols. * We recommend keeping 6 bits for G and 5 each for R and B. * If you have plenty of memory and cycles, 6 bits all around gives marginally * better results; if you are short of memory, 5 bits all around will save * some space but degrade the results. * To maintain a fully accurate histogram, we'd need to allocate a "long" * (preferably unsigned long) for each cell. In practice this is overkill; * we can get by with 16 bits per cell. Few of the cell counts will overflow, * and clamping those that do overflow to the maximum value will give close- * enough results. This reduces the recommended histogram size from 256Kb * to 128Kb, which is a useful savings on PC-class machines. * (In the second pass the histogram space is re-used for pixel mapping data; * in that capacity, each cell must be able to store zero to the number of * desired colors. 16 bits/cell is plenty for that too.) * Since the JPEG code is intended to run in small memory model on 80x86 * machines, we can't just allocate the histogram in one chunk. Instead * of a true 3-D array, we use a row of pointers to 2-D arrays. Each * pointer corresponds to a C0 value (typically 2^5 = 32 pointers) and * each 2-D array has 2^6*2^5 = 2048 or 2^6*2^6 = 4096 entries. Note that * on 80x86 machines, the pointer row is in near memory but the actual * arrays are in far memory (same arrangement as we use for image arrays). */ #define MAXNUMCOLORS (MAXJSAMPLE+1) /* maximum size of colormap */ /* These will do the right thing for either R,G,B or B,G,R color order, * but you may not like the results for other color orders. */ #define HIST_C0_BITS 5 /* bits of precision in R/B histogram */ #define HIST_C1_BITS 6 /* bits of precision in G histogram */ #define HIST_C2_BITS 5 /* bits of precision in B/R histogram */ /* Number of elements along histogram axes. */ #define HIST_C0_ELEMS (1<<HIST_C0_BITS) #define HIST_C1_ELEMS (1<<HIST_C1_BITS) #define HIST_C2_ELEMS (1<<HIST_C2_BITS) /* These are the amounts to shift an input value to get a histogram index. */ #define C0_SHIFT (BITS_IN_JSAMPLE-HIST_C0_BITS) #define C1_SHIFT (BITS_IN_JSAMPLE-HIST_C1_BITS) #define C2_SHIFT (BITS_IN_JSAMPLE-HIST_C2_BITS) typedef UINT16 histcell; /* histogram cell; prefer an unsigned type */ typedef histcell FAR * histptr; /* for pointers to histogram cells */ typedef histcell hist1d[HIST_C2_ELEMS]; /* typedefs for the array */ typedef hist1d FAR * hist2d; /* type for the 2nd-level pointers */ typedef hist2d * hist3d; /* type for top-level pointer */ /* Declarations for Floyd-Steinberg dithering. * * Errors are accumulated into the array fserrors[], at a resolution of * 1/16th of a pixel count. The error at a given pixel is propagated * to its not-yet-processed neighbors using the standard F-S fractions, * ... (here) 7/16 * 3/16 5/16 1/16 * We work left-to-right on even rows, right-to-left on odd rows. * * We can get away with a single array (holding one row's worth of errors) * by using it to store the current row's errors at pixel columns not yet * processed, but the next row's errors at columns already processed. We * need only a few extra variables to hold the errors immediately around the * current column. (If we are lucky, those variables are in registers, but * even if not, they're probably cheaper to access than array elements are.) * * The fserrors[] array has (#columns + 2) entries; the extra entry at * each end saves us from special-casing the first and last pixels. * Each entry is three values long, one value for each color component. * * Note: on a wide image, we migh