|
/Users/lyon/j4p/src/ip/color/MedianCut.java
|
1 package ip.color;
2
3 import j2d.ShortImageBean;
4
5 import java.awt.*;
6 import java.awt.image.IndexColorModel;
7 import java.awt.image.MemoryImageSource;
8 import java.awt.image.BufferedImage;
9
10 /**
11 * Converts an RGB image to 8-bit index color using Heckbert's median-cut
12 * color quantization algorithm. Based on median.c by Anton Kruger from the
13 * September, 1994 issue of Dr. Dobbs Journal.
14 */
15
16
17 // Thanks go to Wayne Rasband for his contribution
18 // of the MedianCut class.
19 // Also for putting his Image/J program,
20 // with source code, into the public domain
21 // (available at http://rsb.info.nih.gov/ij/).
22
23 public class MedianCut {
24
25 static final int MAXIMUM_NUMBER_OF_OUTPUT_COLORS = 256;
26
27
28 static final int SIZE_OF_THE_IMAGE_HISTOGRAM = 32768;
29
30 private int[] RGB_HISTOGRAM_AND_REVERSE_CLUT;
31
32 private int[] pointersToColorsInHistogram;
33
34 private MedianCube cubeList[];
35
36 private int[] pixels32;
37 private int width, height;
38 private IndexColorModel cm;
39
40 /**
41 * For a bufferedImage instance, this will give
42 * an instance of the <code>MedianCut</code>class.
43 *
44 * @param bi
45 * @return
46 */
47 public static MedianCut getMedianCut(BufferedImage bi) {
48 ShortImageBean sib = new ShortImageBean(bi);
49 return new MedianCut(sib.getPels(),
50 sib.getWidth(),
51 sib.getHeight());
52 }
53
54 public MedianCut(int pixels[], int width, int height) {
55 int color16;
56
57 pixels32 = pixels;
58 this.width = width;
59 this.height = height;
60
61 //build 32x32x32 RGB histogram
62 RGB_HISTOGRAM_AND_REVERSE_CLUT = new int[SIZE_OF_THE_IMAGE_HISTOGRAM];
63 for (int i = 0; i < width * height; i++) {
64 color16 = to15BitColor(pixels32[i]);
65 RGB_HISTOGRAM_AND_REVERSE_CLUT[color16]++;
66 }
67 }
68
69
70 // Convert from 24-bit to 15-bit color
71 private static final int to15BitColor(int color24Bit) {
72 int r = (color24Bit & 0xf80000) >> 19;
73 int g = (color24Bit & 0xf800) >> 6;
74 int b = (color24Bit & 0xf8) << 7;
75 return b | g | r;
76 }
77
78 // Get red component of a 15-bit color
79 private static final int getRed15BitColor(int color15Bit) {
80 return (color15Bit & 31) << 3;
81 }
82
83 // Get green component of a 15-bit color
84 private static final int getGreen15BitColor(int color15Bit) {
85 return (color15Bit >> 2) & 0xf8;
86 }
87
88 // Get blue component of a 15-bit color
89 private static final int getBlue15BitColor(int color15Bit) {
90 return (color15Bit >> 7) & 0xf8;
91 }
92
93
94 public Image convert(int maxcubes) {
95 // Uses Heckbert's median-cut algorithm
96 // to divide the color space defined by
97 // "hist" into "maxcubes" cubes.
98 // The centroids (average value) of each cube
99 // are are used to create a color table.
100 // "hist" is then updated to function
101 // as an inverse color map that is
102 // used to generate an 8-bit image.
103
104 int lr, lg, lb;
105 int i, median, color;
106 int count;
107 int k, level, ncubes, splitpos;
108 int longdim = 0; //longest dimension of cube
109 MedianCube cube, cubeA, cubeB;
110
111 // Create initial cube
112 cubeList = new MedianCube[MAXIMUM_NUMBER_OF_OUTPUT_COLORS];
113 pointersToColorsInHistogram = new int[SIZE_OF_THE_IMAGE_HISTOGRAM];
114 ncubes = 0;
115 cube = new MedianCube();
116 for (i = 0, color = 0; i <= SIZE_OF_THE_IMAGE_HISTOGRAM - 1; i++) {
117 if (RGB_HISTOGRAM_AND_REVERSE_CLUT[i] != 0) {
118 pointersToColorsInHistogram[color++] = i;
119 cube.count = cube.count + RGB_HISTOGRAM_AND_REVERSE_CLUT[i];
120 }
121 }
122 cube.lower = 0;
123 cube.upper = color - 1;
124 cube.level = 0;
125 Shrink(cube);
126 cubeList[ncubes++] = cube;
127
128 //Main loop
129 while (ncubes < maxcubes) {
130
131 // Search the list of cubes for next cube to split,
132 // the lowest level cube
133 level = 255;
134 splitpos = -1;
135 for (k = 0; k <= ncubes - 1; k++) {
136 if (cubeList[k].lower == cubeList[k].upper)
137 ; // single color; cannot be split
138 else if (cubeList[k].level < level) {
139 level = cubeList[k].level;
140 splitpos = k;
141 }
142 }
143 if (splitpos == -1) // no more cubes to split
144 break;
145
146 // Find longest dimension of this cube
147 cube = cubeList[splitpos];
148 lr = cube.rmax - cube.rmin;
149 lg = cube.gmax - cube.gmin;
150 lb = cube.bmax - cube.bmin;
151 if (lr >= lg && lr >= lb) longdim = 0;
152 if (lg >= lr && lg >= lb) longdim = 1;
153 if (lb >= lr && lb >= lg) longdim = 2;
154
155 // Sort along "longdim"
156 reorderColors(pointersToColorsInHistogram, cube.lower, cube.upper, longdim);
157 quickSort(pointersToColorsInHistogram, cube.lower, cube.upper);
158 restoreColorOrder(pointersToColorsInHistogram, cube.lower, cube.upper, longdim);
159
160 // Find median
161 count = 0;
162 for (i = cube.lower; i <= cube.upper - 1; i++) {
163 if (count >= cube.count / 2) break;
164 color = pointersToColorsInHistogram[i];
165 count = count + RGB_HISTOGRAM_AND_REVERSE_CLUT[color];
166 }
167 median = i;
168
169 // Now split "cube" at the median and add the two new
170 // cubes to the list of cubes.
171 cubeA = new MedianCube();
172 cubeA.lower = cube.lower;
173 cubeA.upper = median - 1;
174 cubeA.count = count;
175 cubeA.level = cube.level + 1;
176 Shrink(cubeA);
177 cubeList[splitpos] = cubeA; // add in old slot
178
179 cubeB = new MedianCube();
180 cubeB.lower = median;
181 cubeB.upper = cube.upper;
182 cubeB.count = cube.count - count;
183 cubeB.level = cube.level + 1;
184 Shrink(cubeB);
185 cubeList[ncubes++] = cubeB; // add in new slot */
186 }
187
188 // We have enough cubes, or we have split all we can. Now
189 // compute the color map, the inverse color map, and return
190 // an 8-bit image.
191 makeInverseMap(RGB_HISTOGRAM_AND_REVERSE_CLUT, ncubes);
192 return get8BitImage();
193 }
194
195
196 private void Shrink(MedianCube cube) {
197 // Encloses "cube" with a tight-fitting cube by updating the
198 // (rmin,gmin,bmin) and (rmax,gmax,bmax) members of "cube".
199
200 int r, g, b;
201 int color;
202 int rmin, rmax, gmin, gmax, bmin, bmax;
203
204 rmin = 255;
205 rmax = 0;
206 gmin = 255;
207 gmax = 0;
208 bmin = 255;
209 bmax = 0;
210 for (int i = cube.lower; i <= cube.upper; i++) {
211 color = pointersToColorsInHistogram[i];
212 r = getRed15BitColor(color);
213 g = getGreen15BitColor(color);
214 b = getBlue15BitColor(color);
215 if (r > rmax) rmax = r;
216 if (r < rmin) rmin = r;
217 if (g > gmax) gmax = g;
218 if (g < gmin) gmin = g;
219 if (b > bmax) bmax = b;
220 if (b < bmin) bmin = b;
221 }
222 cube.rmin = rmin;
223 cube.rmax = rmax;
224 cube.gmin = gmin;
225 cube.gmax = gmax;
226 cube.gmin = gmin;
227 cube.gmax = gmax;
228 }
229
230
231 private void makeInverseMap(int[] hist, int ncubes) {
232
233 // For each cube in the list of cubes, computes the centroid
234 // (average value) of the colors enclosed by that cube, and
235 // then loads the centroids in the color map. Next loads
236 // "hist" with indices into the color map
237
238 int r, g, b;
239 int color;
240 float rsum, gsum, bsum;
241 MedianCube cube;
242 byte rLUT[] = new byte[256];
243 byte gLUT[] = new byte[256];
244 byte bLUT[] = new byte[256];
245
246 for (int k = 0; k <= ncubes - 1; k++) {
247 cube = cubeList[k];
248 rsum = gsum = bsum = 0.0f;
249 for (int i = cube.lower; i <= cube.upper; i++) {
250 color = pointersToColorsInHistogram[i];
251 r = getRed15BitColor(color);
252 rsum += (float) (r * hist[color]);
253 g = getGreen15BitColor(color);
254 gsum += (float) (g * hist[color]);
255 b = getBlue15BitColor(color);
256 bsum += (float) (b * hist[color]);
257 }
258
259 // Update the color map
260 r = (int) (rsum / (float) cube.count);
261 g = (int) (gsum / (float) cube.count);
262 b = (int) (bsum / (float) cube.count);
263 // Now I have a cube centroid
264 if (r == 248 && g == 248 && b == 248)
265 r = g = b = 255; // Restore white (255,255,255)
266 rLUT[k] = (byte) (r & 0xff);
267 gLUT[k] = (byte) (g & 0xff);
268 bLUT[k] = (byte) (b & 0xff);
269 }
270
271 cm = new IndexColorModel(8, ncubes, rLUT, gLUT, bLUT);
272
273 // For each color in each cube, load the corre-
274 // sponding slot in "hist" with the centroid of the cube.
275 for (int k = 0; k <= ncubes - 1; k++) {
276 cube = cubeList[k];
277 for (int i = cube.lower; i <= cube.upper; i++) {
278 color = pointersToColorsInHistogram[i];
279 hist[color] = k;
280 }
281 }
282 }
283
284 // This method is never invoked.
285 // it is optimal,but slow...the search
286 // for the best map is exhaustive.. DL
287 private void makeInverseTable(int[] hist, int ncubes,
288 byte[] rLUT, byte[] gLUT, byte[] bLUT) {
289 // For each color, find the entry in the color map
290 // that has the smallest Euclidian distance from that
291 // color. Record this information in "hist".
292
293 int r, g, b;
294 int index, color;
295 int dr, dg, db, d, dmin;
296
297 index = 0;
298 for (int i = 0; i < SIZE_OF_THE_IMAGE_HISTOGRAM; i++) {
299 if (hist[i] > 0) {
300 color = i;
301 r = getRed15BitColor(color);
302 g = getGreen15BitColor(color);
303 b = getBlue15BitColor(color);
304 dmin = 999999999;
305 for (int j = 0; j < ncubes; j++) {
306 dr = (rLUT[j] & 0xff) - r;
307 dg = (gLUT[j] & 0xff) - g;
308 db = (bLUT[j] & 0xff) - b;
309 d = dr * dr + dg * dg + db * db;
310 if (d == 0) {
311 index = j;
312 break;
313 } else if (d < dmin) {
314 dmin = d;
315 index = j;
316 }
317 }
318 hist[color] = index;
319 }
320 }
321
322 }
323
324
325 private void reorderColors(int[] a, int lo, int hi, int longDim) {
326 // Change the ordering of the 5-bit colors in each word of int[]
327 // so we can sort on the 'longDim' color
328
329 int c, r, g, b;
330 switch (longDim) {
331 case 0: //red
332 for (int i = lo; i <= hi; i++) {
333 c = a[i];
334 r = c & 31;
335 a[i] = (r << 10) | (c >> 5);
336 }
337 break;
338 case 1: //green
339 for (int i = lo; i <= hi; i++) {
340 c = a[i];
341 r = c & 31;
342 g = (c >> 5) & 31;
343 b = c >> 10;
344 a[i] = (g << 10) | (b << 5) | r;
345 }
346 break;
347 case 2: //blue; already in the needed order
348 break;
349 }
350 }
351
352
353 private void restoreColorOrder(int[] a, int lo, int hi, int longDim) {
354 // Restore the 5-bit colors to the original order
355
356 int c, r, g, b;
357 switch (longDim) {
358 case 0: //red
359 for (int i = lo; i <= hi; i++) {
360 c = a[i];
361 r = c >> 10;
362 a[i] = ((c & 1023) << 5) | r;
363 }
364 break;
365 case 1: //green
366 for (int i = lo; i <= hi; i++) {
367 c = a[i];
368 r = c & 31;
369 g = c >> 10;
370 b = (c >> 5) & 31;
371 a[i] = (b << 10) | (g << 5) | r;
372 }
373 break;
374 case 2: //blue
375 break;
376 }
377 }
378
379
380 private static void quickSort(int a[], int lo0, int hi0) {
381 // Based on the QuickSort method by
382 // James Gosling from Sun's SortDemo applet
383
384 int lo = lo0;
385 int hi = hi0;
386 int mid, t;
387
388 if (hi0 > lo0) {
389 mid = a[(lo0 + hi0) / 2];
390 while (lo <= hi) {
391 while ((lo < hi0) && (a[lo] < mid))
392 ++lo;
393 while ((hi > lo0) && (a[hi] > mid))
394 --hi;
395 if (lo <= hi) {
396 t = a[lo];
397 a[lo] = a[hi];
398 a[hi] = t;
399 ++lo;
400 --hi;
401 }
402 }
403 if (lo0 < hi)
404 quickSort(a, lo0, hi);
405 if (lo < hi0)
406 quickSort(a, lo, hi0);
407
408 }
409 }
410 /**
411 * Using existing color lookup table, map
412 * image into a 256 color image.
413 * If the color is not present, you will have to search the table.
414 * @param bi
415 * @return
416 */
417 public Image get8BitImage(BufferedImage bi) {
418
419 Image img8;
420 byte[] pixels8;
421 int color16;
422 ShortImageBean sib = new ShortImageBean(bi);
423 pixels32 = sib.getPels();
424 width = sib.getWidth();
425 height = sib.getHeight();
426
427 pixels8 = new byte[width * height];
428 for (int i = 0; i < width * height; i++) {
429 color16 = to15BitColor(pixels32[i]);
430 pixels8[i] = (byte) (RGB_HISTOGRAM_AND_REVERSE_CLUT[color16] & 0xff);
431 }
432 img8 =
433 Toolkit.getDefaultToolkit().createImage(
434 new MemoryImageSource(width,
435 height,
436 cm,
437 pixels8,
438 0,
439 width));
440 return img8;
441 }
442 public Image get8BitImage() {
443
444 Image img8;
445 byte[] pixels8;
446 int color16;
447
448 pixels8 = new byte[width * height];
449 for (int i = 0; i < width * height; i++) {
450 color16 = to15BitColor(pixels32[i]);
451 pixels8[i] = (byte) (RGB_HISTOGRAM_AND_REVERSE_CLUT[color16] & 0xff);
452 }
453 img8 =
454 Toolkit.getDefaultToolkit().createImage(
455 new MemoryImageSource(width,
456 height,
457 cm,
458 pixels8,
459 0,
460 width));
461 return img8;
462 }
463
464
465 } //class MedianCut
466
467
468 class MedianCube {
469 // structure for a cube in color space
470 int lower; // one corner's index in histogram
471 int upper; // another corner's index in histogram
472 int count; // cube's histogram count
473 int level; // cube's level
474 int rmin, rmax;
475 int gmin, gmax;
476 int bmin, bmax;
477
478 MedianCube() {
479 count = 0;
480 }
481
482 public String toString() {
483 String s = "lower=" + lower + " upper=" + upper;
484 s = s + " count=" + count + " level=" + level;
485 s = s + " rmin=" + rmin + " rmax=" + rmax;
486 s = s + " gmin=" + gmin + " gmax=" + gmax;
487 s = s + " bmin=" + bmin + " bmax=" + bmax;
488 return s;
489 }
490
491 }
492
493