Class MedianCut

java.lang.Object
  |
  +--MedianCut

class MedianCut
extends java.lang.Object

MedianCut converts an RGB image to 8-bit index color using Heckbert's median-cut color quantization algorithm. Based on median.c by Anton Kruger from the September, 1994 issue of Dr. Dobbs Journal. Notes on the algorithm: 1. It takes the 24-bit (r,g,b) pixel, clips the bottom 3 bits of each color to make a packed 15-bit pixel (2**15=32768). 2. It then builds a build 32x32x32 RGB histogram hist15[0:32768]. 3. Calling code invokes cvtImg24toImg8() to cvt color space defined by hist15[] into maxcubes cubes. 3.1 Create initial cube from hist15[] data. 3.2 Search cubeList[] for next cube to split, lowest level cube. 3.2.1 Check if split cubes 3.2.2 Find longest dimension of this cube 3.2.3 Sort along "longdim" by: reorderColors(), quickSort(), restoreColorOrder(). 3.2.4 Find median 3.2.5 Now split "cube" at the median and add the two new cubes to the list of cubes. 3.3 Compute the color map, inverse color map. 3.4 Convert 24-bit RGB image to an 8-bit image. 4. The caller gets the return data from the MedianCut instance: pixels8[], rLUT[], gLUT[], and bLUT[].


Field Summary
(package private)  byte[] bLUT
          [0:255] Blue Color map look up table
(package private)  int colorMax
          # of non-zero bins in hist15[]
private  MC_Cube[] cubeList
          list of cubes
(package private)  byte[] gLUT
          [0:255] Green Color map look up table
(package private)  int height
          width size of image
private  int[] hist15
          [0:32K] 15-bit RGB hist.
private  int[] histPtr
          [0:colorMax-1] points to colors in "hist15[]"
(package private) static int HSIZE
          max size of image histogram
(package private) static int MAXCOLORS
          maximum # of output colors
(package private)  int ncubes
          # of color cubes
private  int[] pixels32
          32-bit image[width*height] (Alpha,Red,Green,Blue) pixels
(package private)  byte[] pixels8
          8-bit image[width*height] using LUTs
(package private)  byte[] rLUT
          [0:255] Red Color map look up table
(package private)  int width
          width size of image
 
Constructor Summary
(package private) MedianCut(int[] pixels, int width, int height)
          MedianCut() - Constructor Then call cvtImg24toImg8() to get the 8-bit image.
 
Method Summary
private  int blueBits(int x)
          blueBits() - Get 8-bit blue component of a 15-bit color 8-bit pixel with low 3 bits zero.
(package private)  boolean cvtImg24toImg8(int maxcubes)
          cvtImg24toImg8() - Uses Heckbert's median-cut algorithm to divide the color space defined by "hist15[]" into "maxcubes" cubes.
private  int greenBits(int x)
          greenBits() - Get 8-bit green component of a 15-bit color 8-bit pixel with low 3 bits zero.
(package private)  void make8BitImage()
          make8BitImage() - Generate 8-bit image from interla 15-bit image.
(package private)  void makeInverseMap(int[] hist15, int ncubes)
          makeInverseMap() - for all cubes, compute centroid of colors in cube.
(package private)  void quickSort(int[] a, int lo0, int hi0)
          quickSort() - sort the map Based on the QuickSort method by James Gosling from Sun's SortDemo applet
private  int redBits(int x)
          redBits() - Get 8-bit red component of a 15-bit color 8-bit pixel with low 3 bits zero.
(package private)  void reorderColors(int[] histP, int lo, int hi, int longDim)
          reorderColors() - Change ordering of 5-bit colors in each word of int[] so we can sort on the 'longDim' color
(package private)  void restoreColorOrder(int[] histP, int lo, int hi, int longDim)
          restoreColorOrder() - Restore the 5-bit colors to original order
private  int rgb15(int c)
          rgb15() - convert from 24-bit (ignore alpha) to 15-bit color.
private  void shrinkCube(MC_Cube cube)
          shrinkCube() - Encloses "cube" with a tight-fitting cube by updating the (rmin,gmin,bmin) and (rmax,gmax,bmax) members of "cube".
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

MAXCOLORS

static final int MAXCOLORS
maximum # of output colors

HSIZE

static final int HSIZE
max size of image histogram

hist15

private int[] hist15
[0:32K] 15-bit RGB hist. & reverse color LUT

histPtr

private int[] histPtr
[0:colorMax-1] points to colors in "hist15[]"

pixels32

private int[] pixels32
32-bit image[width*height] (Alpha,Red,Green,Blue) pixels

cubeList

private MC_Cube[] cubeList
list of cubes

ncubes

int ncubes
# of color cubes

colorMax

int colorMax
# of non-zero bins in hist15[]

width

int width
width size of image

height

int height
width size of image

pixels8

byte[] pixels8
8-bit image[width*height] using LUTs

rLUT

byte[] rLUT
[0:255] Red Color map look up table

gLUT

byte[] gLUT
[0:255] Green Color map look up table

bLUT

byte[] bLUT
[0:255] Blue Color map look up table
Constructor Detail

MedianCut

MedianCut(int[] pixels,
          int width,
          int height)
MedianCut() - Constructor Then call cvtImg24toImg8() to get the 8-bit image.
Parameters:
pixels - array of 32-bit Java Color pixel
width - is the image size
height - is the image size
Method Detail

rgb15

private final int rgb15(int c)
rgb15() - convert from 24-bit (ignore alpha) to 15-bit color. Use top 5-bits of the 8-bit color components, ignores low 3-bits of each component. ----------------------------- |Alpha | Red | Green | Blue| Java Color layout (8-bit pixels) ----------------------------- 31-17 23-16 15-8 7-0 ----------------------------- | free | Red | Green | Blue| 15-bit color Layout (5-bit pixels) ----------------------------- 31-15 14-10 9-5 4-0
Parameters:
c - is the RGB 24-bit Java Color pixel
Returns:
15-bit color.

redBits

private final int redBits(int x)
redBits() - Get 8-bit red component of a 15-bit color 8-bit pixel with low 3 bits zero.
Parameters:
x - 15-bit color component
Returns:
value

greenBits

private final int greenBits(int x)
greenBits() - Get 8-bit green component of a 15-bit color 8-bit pixel with low 3 bits zero.
Parameters:
x - 15-bit color component
Returns:
value

blueBits

private final int blueBits(int x)
blueBits() - Get 8-bit blue component of a 15-bit color 8-bit pixel with low 3 bits zero.
Parameters:
x - 15-bit color component
Returns:
value

cvtImg24toImg8

boolean cvtImg24toImg8(int maxcubes)
cvtImg24toImg8() - Uses Heckbert's median-cut algorithm to divide the color space defined by "hist15[]" into "maxcubes" cubes. The centroids (average value) of each cube are are used to create a color table. "hist15[]" is then updated to function as an inverse color map that is used to generate an 8-bit image.
Parameters:
maxcubes - to use
Returns:
true if succeed. Return data is in pixels8[], rLUT, gLUT[], bLUT[].

shrinkCube

private void shrinkCube(MC_Cube cube)
shrinkCube() - Encloses "cube" with a tight-fitting cube by updating the (rmin,gmin,bmin) and (rmax,gmax,bmax) members of "cube".
Parameters:
cube - is the cube to use

makeInverseMap

void makeInverseMap(int[] hist15,
                    int ncubes)
makeInverseMap() - for all cubes, compute centroid of colors in cube. For each cube in the list of cubes, computes the centroid (average value) of the colors enclosed by that cube, and then loads the centroids in the color map. Next loads "hist15[]" with indices into the color map.
Parameters:
hist15 - is the histogram to compute
ncubes - is the number of cubes to use

reorderColors

void reorderColors(int[] histP,
                   int lo,
                   int hi,
                   int longDim)
reorderColors() - Change ordering of 5-bit colors in each word of int[] so we can sort on the 'longDim' color

restoreColorOrder

void restoreColorOrder(int[] histP,
                       int lo,
                       int hi,
                       int longDim)
restoreColorOrder() - Restore the 5-bit colors to original order

quickSort

void quickSort(int[] a,
               int lo0,
               int hi0)
quickSort() - sort the map Based on the QuickSort method by James Gosling from Sun's SortDemo applet

make8BitImage

void make8BitImage()
make8BitImage() - Generate 8-bit image from interla 15-bit image.