001: /*
002: * $RCSfile: PaletteBuilder.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * - Redistribution of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * - Redistribution in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * Neither the name of Sun Microsystems, Inc. or the names of
019: * contributors may be used to endorse or promote products derived
020: * from this software without specific prior written permission.
021: *
022: * This software is provided "AS IS," without a warranty of any
023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
026: * EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
034: * POSSIBILITY OF SUCH DAMAGES.
035: *
036: * You acknowledge that this software is not designed or intended for
037: * use in the design, construction, operation or maintenance of any
038: * nuclear facility.
039: *
040: */
041: package org.vfny.geoserver.wms.responses.palette;
042:
043: import java.awt.Transparency;
044: import java.awt.image.BufferedImage;
045: import java.awt.image.ColorModel;
046: import java.awt.image.IndexColorModel;
047: import java.awt.image.Raster;
048: import java.awt.image.RenderedImage;
049: import java.awt.image.WritableRaster;
050:
051: import javax.imageio.ImageTypeSpecifier;
052:
053: /**
054: * This class implements the octree quantization method as it is described in
055: * the "Graphics Gems" (ISBN 0-12-286166-3, Chapter 4, pages 297-293)
056: *
057: * @author Simone Giannecchini - GeoSolutions
058: */
059: public final class CustomPaletteBuilder {
060: /**
061: * Default value for the threshold to decide whether a pixel is opaque (>=)
062: * or transparent (<). Default is 1 to try to preserve antialising
063: */
064: public static final int DEFAULT_ALPHA_TH = 1;
065:
066: /**
067: * maximum of tree depth
068: */
069: protected int maxLevel;
070:
071: protected RenderedImage src;
072:
073: protected ColorModel srcColorModel;
074:
075: protected int requiredSize;
076:
077: protected ColorNode root;
078:
079: protected int numNodes;
080:
081: protected int maxNodes;
082:
083: protected int currLevel;
084:
085: protected int currSize;
086:
087: protected ColorNode[] reduceList;
088:
089: protected ColorNode[] palette;
090:
091: protected int transparency;
092:
093: protected ColorNode transColor;
094:
095: protected int subsampleX;
096:
097: protected int subsampley;
098:
099: protected int numBands;
100:
101: protected int alphaThreshold;
102:
103: /**
104: * Returns <code>true</code> if PaletteBuilder is able to create palette
105: * for given image type.
106: *
107: * @param type
108: * an instance of <code>ImageTypeSpecifier</code> to be
109: * indexed.
110: *
111: * @return <code>true</code> if the <code>PaletteBuilder</code> is
112: * likely to be able to create palette for this image type.
113: *
114: * @exception IllegalArgumentException
115: * if <code>type</code> is <code>null</code>.
116: */
117: public static boolean canCreatePalette(ImageTypeSpecifier type) {
118: if (type == null) {
119: throw new IllegalArgumentException("type == null");
120: }
121:
122: return true;
123: }
124:
125: /**
126: * Returns <code>true</code> if PaletteBuilder is able to create palette
127: * for given rendered image.
128: *
129: * @param image
130: * an instance of <code>RenderedImage</code> to be indexed.
131: *
132: * @return <code>true</code> if the <code>PaletteBuilder</code> is
133: * likely to be able to create palette for this image type.
134: *
135: * @exception IllegalArgumentException
136: * if <code>image</code> is <code>null</code>.
137: */
138: public static boolean canCreatePalette(RenderedImage image) {
139: if (image == null) {
140: throw new IllegalArgumentException("image == null");
141: }
142:
143: ImageTypeSpecifier type = new ImageTypeSpecifier(image);
144:
145: return canCreatePalette(type);
146: }
147:
148: public RenderedImage getIndexedImage() {
149: // //
150: //
151: // Create the destination image
152: //
153: // //
154: final IndexColorModel icm = getIndexColorModel();
155: final WritableRaster destWr = icm
156: .createCompatibleWritableRaster(src.getWidth(), src
157: .getHeight());
158: final BufferedImage dst = new BufferedImage(icm, destWr, false,
159: null);
160:
161: // //
162: //
163: // Filter the image out
164: //
165: // //
166:
167: // //
168: //
169: // Collecting info about the source image
170: //
171: // //
172: final int numBands = src.getSampleModel().getNumBands();
173: final int rgba[] = new int[numBands];
174: final boolean sourceHasAlpha = (numBands % 2 == 0);
175: final int alphaBand = sourceHasAlpha ? numBands - 1 : -1;
176: final int minx_ = src.getMinX();
177: final int miny_ = src.getMinY();
178: final int srcW_ = src.getWidth();
179: final int srcH_ = src.getHeight();
180: final int maxx_ = minx_ + srcW_;
181: final int maxy_ = miny_ + srcH_;
182: final int minTileX = src.getMinTileX();
183: final int minTileY = src.getMinTileY();
184: final int tileW = src.getTileWidth();
185: final int tileH = src.getTileHeight();
186: final int maxTileX = minTileX + src.getNumXTiles();
187: final int maxTileY = minTileY + src.getNumYTiles();
188: int dstTempX = 0;
189: int dstTempY = 0;
190: for (int ty = minTileY; ty < maxTileY; ty++) {
191: dstTempX = 0;
192: int actualWidth = 0;
193: int actualHeight = 0;
194: for (int tx = minTileX; tx < maxTileX; tx++) {
195: // get the source raster
196: final Raster r = src.getTile(tx, ty);
197:
198: int minx = r.getMinX();
199: int miny = r.getMinY();
200: minx = minx < minx_ ? minx_ : minx;
201: miny = miny < miny_ ? miny_ : miny;
202: int maxx = minx + tileW;
203: int maxy = miny + tileH;
204: maxx = maxx > maxx_ ? maxx_ : maxx;
205: maxy = maxy > maxy_ ? maxy_ : maxy;
206: actualWidth = maxx - minx;
207: actualHeight = maxy - miny;
208: for (int j = miny, jj = dstTempY; j < maxy; j++, jj++) {
209: for (int i = minx, ii = dstTempX; i < maxx; i++, ii++) {
210: r.getPixel(i, j, rgba);
211:
212: destWr.setSample(ii, jj, 0, findColorIndex(
213: root, rgba, alphaBand));
214:
215: }
216: }
217: dstTempX += actualWidth;
218:
219: }
220: dstTempY += actualHeight;
221: }
222: return dst;
223: }
224:
225: public CustomPaletteBuilder(RenderedImage src) {
226: this (src, 256, 1, 1, DEFAULT_ALPHA_TH);
227: }
228:
229: public CustomPaletteBuilder(RenderedImage src, int size, int subsx,
230: int subsy, int alpha_th) {
231: if ((subsx <= 0) || (subsx >= src.getWidth())) {
232: throw new IllegalArgumentException(
233: "Invalid subsample x size");
234: }
235:
236: if ((subsy <= 0) || (subsy >= src.getWidth())) {
237: throw new IllegalArgumentException(
238: "Invalid subsample y size");
239: }
240:
241: this .alphaThreshold = alpha_th;
242: this .src = src;
243: this .srcColorModel = src.getColorModel();
244: this .numBands = srcColorModel.getNumComponents();
245: this .subsampleX = subsx;
246: this .subsampley = subsy;
247: this .transparency = srcColorModel.getTransparency();
248: if (transparency != Transparency.OPAQUE) {
249: transparency = Transparency.BITMASK;
250: // make room for the transparent color
251: this .requiredSize = size - 1;
252: transColor = new ColorNode();
253: transColor.isLeaf = true;
254: } else {
255: this .requiredSize = size;
256: }
257:
258: if (this .requiredSize > 256) {
259: throw new IllegalArgumentException(
260: "Unvalid number of colors require.");
261: }
262:
263: this .maxLevel = (int) Math.ceil(Math.log(requiredSize)
264: / Math.log(2));
265: }
266:
267: protected int findColorIndex(ColorNode aNode, int[] rgba,
268: int transpBand) {
269: if ((transparency != Transparency.OPAQUE)
270: && (rgba[transpBand] < alphaThreshold)) {
271: return 0; // default transparent pixel
272: }
273:
274: try {
275: if (aNode.isLeaf) {
276: return aNode.paletteIndex;
277: } else {
278: int childIndex = getBranchIndex(rgba, aNode.level);
279:
280: if (aNode.children[childIndex] == null) {
281: int i = 1;
282: for (; i < 8; i++) {
283: if (((childIndex + i) < 8)
284: && (aNode.children[childIndex + i] != null)) {
285: childIndex += i;
286:
287: break;
288: }
289:
290: if (((childIndex - i) >= 0)
291: && (aNode.children[childIndex - i] != null)) {
292: childIndex -= i;
293:
294: break;
295: }
296: }
297: }
298: return findColorIndex(aNode.children[childIndex], rgba,
299: transpBand);
300: }
301: } catch (Exception e) {
302: }
303: return 0;
304: }
305:
306: public CustomPaletteBuilder buildPalette() {
307: reduceList = new ColorNode[maxLevel + 1];
308:
309: for (int i = 0; i < reduceList.length; i++) {
310: reduceList[i] = null;
311: }
312:
313: numNodes = 0;
314: maxNodes = 0;
315: root = null;
316: currSize = 0;
317: currLevel = maxLevel;
318:
319: // //
320: //
321: // Collecting info about the source image
322: //
323: // //
324: final int numBands = src.getSampleModel().getNumBands();
325: final int rgba[] = new int[numBands];
326: final boolean discriminantTransparency = transparency != Transparency.OPAQUE;
327: final int transpBand = numBands - 1;
328: final int minx_ = src.getMinX();
329: final int miny_ = src.getMinY();
330: final int srcW_ = src.getWidth();
331: final int srcH_ = src.getHeight();
332: final int maxx_ = minx_ + srcW_;
333: final int maxy_ = miny_ + srcH_;
334: final int minTileX = src.getMinTileX();
335: final int minTileY = src.getMinTileY();
336: final int tileW = src.getTileWidth();
337: final int tileH = src.getTileHeight();
338: final int maxTileX = minTileX + src.getNumXTiles();
339: final int maxTileY = minTileY + src.getNumYTiles();
340: for (int ty = minTileY; ty < maxTileY; ty++) {
341: for (int tx = minTileX; tx < maxTileX; tx++) {
342: // get the source raster
343: final Raster r = src.getTile(tx, ty);
344:
345: int minx = r.getMinX();
346: int miny = r.getMinY();
347: minx = minx < minx_ ? minx_ : minx;
348: miny = miny < miny_ ? miny_ : miny;
349: int maxx = minx + tileW;
350: int maxy = miny + tileH;
351: maxx = maxx > maxx_ ? maxx_ : maxx;
352: maxy = maxy > maxy_ ? maxy_ : maxy;
353: for (int j = miny; j < maxy; j++) {
354: if ((subsampley > 1) && ((j % subsampley) != 0)) {
355: continue;
356: }
357:
358: for (int i = minx; i < maxx; i++) {
359: if ((subsampleX > 1) && ((i % subsampleX) != 0)) {
360: continue;
361: }
362: r.getPixel(i, j, rgba);
363: /*
364: * If transparency of given image is not opaque we
365: * assume all colors with alpha less than 1.0 as fully
366: * transparent.
367: */
368: if (discriminantTransparency
369: && (rgba[transpBand] < alphaThreshold)) {
370: transColor = insertNode(transColor, rgba, 0);
371: } else {
372:
373: root = insertNode(root, rgba, 0);
374: }
375:
376: if (currSize > requiredSize) {
377: reduceTree();
378: }
379:
380: }
381: }
382:
383: }
384: }
385: return this ;
386: }
387:
388: protected ColorNode insertNode(ColorNode aNode, int[] rgba,
389: int aLevel) {
390: if (aNode == null) {
391: aNode = new ColorNode();
392: numNodes++;
393:
394: if (numNodes > maxNodes) {
395: maxNodes = numNodes;
396: }
397:
398: aNode.level = aLevel;
399: aNode.isLeaf = (aLevel > maxLevel);
400:
401: if (aNode.isLeaf) {
402: currSize++;
403: }
404: }
405:
406: aNode.colorCount++;
407: aNode.red += rgba[0];
408: aNode.green += rgba[1];
409: aNode.blue += rgba[2];
410:
411: if (!aNode.isLeaf) {
412: int branchIndex = getBranchIndex(rgba, aLevel);
413:
414: if (aNode.children[branchIndex] == null) {
415: aNode.childCount++;
416:
417: if (aNode.childCount == 2) {
418: aNode.nextReducible = reduceList[aLevel];
419: reduceList[aLevel] = aNode;
420: }
421: }
422:
423: aNode.children[branchIndex] = insertNode(
424: aNode.children[branchIndex], rgba, aLevel + 1);
425: }
426:
427: return aNode;
428: }
429:
430: public IndexColorModel getIndexColorModel() {
431: int size = currSize;
432:
433: if (transparency == Transparency.BITMASK) {
434: size++; // we need place for transparent color;
435: }
436:
437: final byte[] red = new byte[size];
438: final byte[] green = new byte[size];
439: final byte[] blue = new byte[size];
440:
441: int index = 0;
442: palette = new ColorNode[size];
443:
444: if (transparency == Transparency.BITMASK) {
445: index++;
446: }
447: findPaletteEntry(root, index, red, green, blue);
448: if (transparency == Transparency.BITMASK) {
449: return new IndexColorModel(8, size, red, green, blue, 0);
450: }
451: return new IndexColorModel(8, currSize, red, green, blue);
452: }
453:
454: protected int findPaletteEntry(ColorNode aNode, int index,
455: byte[] red, byte[] green, byte[] blue) {
456: if (aNode == null) {
457: return index;
458: }
459:
460: if (aNode.isLeaf) {
461: red[index] = (byte) (aNode.red / aNode.colorCount);
462: green[index] = (byte) (aNode.green / aNode.colorCount);
463: blue[index] = (byte) (aNode.blue / aNode.colorCount);
464: aNode.paletteIndex = index;
465:
466: palette[index] = aNode;
467:
468: index++;
469: } else {
470: for (int i = 0; i < 8; i++) {
471: if (aNode.children[i] != null) {
472: index = findPaletteEntry(aNode.children[i], index,
473: red, green, blue);
474: }
475: }
476: }
477:
478: return index;
479: }
480:
481: protected int getBranchIndex(int[] rgba, int aLevel) {
482: if ((aLevel > maxLevel) || (aLevel < 0)) {
483: throw new IllegalArgumentException(
484: "Invalid octree node depth: " + aLevel);
485: }
486:
487: int shift = maxLevel - aLevel;
488: int red_index = 0x1 & ((0xff & rgba[0]) >> shift);
489: int green_index = 0x1 & ((0xff & rgba[1]) >> shift);
490: int blue_index = 0x1 & ((0xff & rgba[2]) >> shift);
491: int index = (red_index << 2) | (green_index << 1) | blue_index;
492:
493: return index;
494: }
495:
496: protected void reduceTree() {
497: int level = reduceList.length - 1;
498: while ((reduceList[level] == null) && (level >= 0)) {
499: level--;
500: }
501:
502: ColorNode this Node = reduceList[level];
503:
504: if (this Node == null) {
505: // nothing to reduce
506: return;
507: }
508:
509: // look for element with lower color count
510: ColorNode pList = this Node;
511: int minColorCount = pList.colorCount;
512:
513: int cnt = 1;
514:
515: while (pList.nextReducible != null) {
516: if (minColorCount > pList.nextReducible.colorCount) {
517: this Node = pList;
518: minColorCount = pList.colorCount;
519: }
520:
521: pList = pList.nextReducible;
522: cnt++;
523: }
524:
525: // save pointer to first reducible node
526: // NB: current color count for node could be changed in future
527: if (this Node == reduceList[level]) {
528: reduceList[level] = this Node.nextReducible;
529: } else {
530: pList = this Node.nextReducible; // we need to process it
531: this Node.nextReducible = pList.nextReducible;
532: this Node = pList;
533: }
534:
535: if (this Node.isLeaf) {
536: return;
537: }
538:
539: // reduce node
540: int leafChildCount = this Node.getLeafChildCount();
541: this Node.isLeaf = true;
542: currSize -= (leafChildCount - 1);
543:
544: final int aDepth = this Node.level;
545: for (int i = 0; i < 8; i++) {
546: this Node.children[i] = freeTree(this Node.children[i]);
547: }
548: this Node.childCount = 0;
549: }
550:
551: protected ColorNode freeTree(ColorNode aNode) {
552: if (aNode == null) {
553: return null;
554: }
555:
556: for (int i = 0; i < 8; i++) {
557: aNode.children[i] = freeTree(aNode.children[i]);
558: }
559:
560: numNodes--;
561:
562: return null;
563: }
564:
565: /**
566: * The node of color tree.
567: */
568: protected class ColorNode {
569: public boolean isLeaf;
570:
571: public int childCount;
572:
573: public ColorNode[] children;
574:
575: public int colorCount;
576:
577: public long red;
578:
579: public long blue;
580:
581: public long green;
582:
583: public int paletteIndex;
584:
585: public int level;
586:
587: public ColorNode nextReducible;
588:
589: public ColorNode() {
590: isLeaf = false;
591: level = 0;
592: childCount = 0;
593: children = new ColorNode[8];
594:
595: for (int i = 0; i < 8; i++) {
596: children[i] = null;
597: }
598:
599: colorCount = 0;
600: red = green = blue = 0;
601:
602: paletteIndex = 0;
603: }
604:
605: public int getLeafChildCount() {
606: if (isLeaf) {
607: return 0;
608: }
609:
610: int cnt = 0;
611:
612: for (int i = 0; i < children.length; i++) {
613: if (children[i] != null) {
614: if (children[i].isLeaf) {
615: cnt++;
616: } else {
617: cnt += children[i].getLeafChildCount();
618: }
619: }
620: }
621:
622: return cnt;
623: }
624:
625: public int getRGB() {
626: int r = (int) red / colorCount;
627: int g = (int) green / colorCount;
628: int b = (int) blue / colorCount;
629:
630: int c = (0xff << 24) | ((0xff & r) << 16)
631: | ((0xff & g) << 8) | (0xff & b);
632:
633: return c;
634: }
635: }
636:
637: public int findNearestColorIndex(int[] rgba, int transparentBand) {
638: return findColorIndex(root, rgba, transparentBand);
639: }
640:
641: }
|