O2Plib.image
Class MedianCut

java.lang.Object
  extended by O2Plib.image.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
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, toString, wait, wait, wait
 

Field Detail

MAXCOLORS

static final int MAXCOLORS
maximum # of output colors

See Also:
Constant Field Values

HSIZE

static final int HSIZE
max size of image histogram

See Also:
Constant Field Values

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.