0N/A/*
2362N/A * Copyright (c) 2005, 2006, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage com.sun.imageio.plugins.common;
0N/A
0N/Aimport java.awt.Transparency;
0N/Aimport java.awt.image.BufferedImage;
0N/Aimport java.awt.image.RenderedImage;
0N/Aimport java.awt.image.ColorModel;
0N/Aimport java.awt.image.IndexColorModel;
0N/Aimport java.awt.image.Raster;
0N/Aimport java.awt.image.WritableRaster;
0N/Aimport java.awt.Color;
0N/Aimport javax.imageio.ImageTypeSpecifier;
0N/A
0N/A
0N/A/**
0N/A * This class implements the octree quantization method
0N/A * as it is described in the "Graphics Gems"
0N/A * (ISBN 0-12-286166-3, Chapter 4, pages 297-293)
0N/A */
0N/Apublic class PaletteBuilder {
0N/A
0N/A /**
0N/A * maximum of tree depth
0N/A */
0N/A protected static final int MAXLEVEL = 8;
0N/A
0N/A protected RenderedImage src;
0N/A protected ColorModel srcColorModel;
0N/A protected Raster srcRaster;
0N/A
0N/A protected int requiredSize;
0N/A
0N/A protected ColorNode root;
0N/A
0N/A protected int numNodes;
0N/A protected int maxNodes;
0N/A protected int currLevel;
0N/A protected int currSize;
0N/A
0N/A protected ColorNode[] reduceList;
0N/A protected ColorNode[] palette;
0N/A
0N/A protected int transparency;
0N/A protected ColorNode transColor;
0N/A
0N/A
0N/A /**
0N/A * Creates an image representing given image
0N/A * <code>src</code> using <code>IndexColorModel</code>.
0N/A *
0N/A * Lossless conversion is not always possible (e.g. if number
0N/A * of colors in the given image exceeds maximum palette size).
0N/A * Result image then is an approximation constructed by octree
0N/A * quantization method.
0N/A *
0N/A * @exception IllegalArgumentException if <code>src</code> is
0N/A * <code>null</code>.
0N/A *
0N/A * @exception UnsupportedOperationException if implemented method
0N/A * is unable to create approximation of <code>src</code>
0N/A * and <code>canCreatePalette</code> returns <code>false</code>.
0N/A *
0N/A * @see createIndexColorModel
0N/A *
0N/A * @see canCreatePalette
0N/A *
0N/A */
0N/A public static RenderedImage createIndexedImage(RenderedImage src) {
0N/A PaletteBuilder pb = new PaletteBuilder(src);
0N/A pb.buildPalette();
0N/A return pb.getIndexedImage();
0N/A }
0N/A
0N/A /**
0N/A * Creates an palette representing colors from given image
0N/A * <code>img</code>. If number of colors in the given image exceeds
0N/A * maximum palette size closest colors would be merged.
0N/A *
0N/A * @exception IllegalArgumentException if <code>img</code> is
0N/A * <code>null</code>.
0N/A *
0N/A * @exception UnsupportedOperationException if implemented method
0N/A * is unable to create approximation of <code>img</code>
0N/A * and <code>canCreatePalette</code> returns <code>false</code>.
0N/A *
0N/A * @see createIndexedImage
0N/A *
0N/A * @see canCreatePalette
0N/A *
0N/A */
0N/A public static IndexColorModel createIndexColorModel(RenderedImage img) {
0N/A PaletteBuilder pb = new PaletteBuilder(img);
0N/A pb.buildPalette();
0N/A return pb.getIndexColorModel();
0N/A }
0N/A
0N/A /**
0N/A * Returns <code>true</code> if PaletteBuilder is able to create
0N/A * palette for given image type.
0N/A *
0N/A * @param type an instance of <code>ImageTypeSpecifier</code> to be
0N/A * indexed.
0N/A *
0N/A * @return <code>true</code> if the <code>PaletteBuilder</code>
0N/A * is likely to be able to create palette for this image type.
0N/A *
0N/A * @exception IllegalArgumentException if <code>type</code>
0N/A * is <code>null</code>.
0N/A */
0N/A public static boolean canCreatePalette(ImageTypeSpecifier type) {
0N/A if (type == null) {
0N/A throw new IllegalArgumentException("type == null");
0N/A }
0N/A return true;
0N/A }
0N/A
0N/A /**
0N/A * Returns <code>true</code> if PaletteBuilder is able to create
0N/A * palette for given rendered image.
0N/A *
0N/A * @param image an instance of <code>RenderedImage</code> to be
0N/A * indexed.
0N/A *
0N/A * @return <code>true</code> if the <code>PaletteBuilder</code>
0N/A * is likely to be able to create palette for this image type.
0N/A *
0N/A * @exception IllegalArgumentException if <code>image</code>
0N/A * is <code>null</code>.
0N/A */
0N/A public static boolean canCreatePalette(RenderedImage image) {
0N/A if (image == null) {
0N/A throw new IllegalArgumentException("image == null");
0N/A }
0N/A ImageTypeSpecifier type = new ImageTypeSpecifier(image);
0N/A return canCreatePalette(type);
0N/A }
0N/A
0N/A protected RenderedImage getIndexedImage() {
0N/A IndexColorModel icm = getIndexColorModel();
0N/A
0N/A BufferedImage dst =
0N/A new BufferedImage(src.getWidth(), src.getHeight(),
0N/A BufferedImage.TYPE_BYTE_INDEXED, icm);
0N/A
0N/A WritableRaster wr = dst.getRaster();
0N/A for (int y =0; y < dst.getHeight(); y++) {
0N/A for (int x = 0; x < dst.getWidth(); x++) {
0N/A Color aColor = getSrcColor(x,y);
0N/A wr.setSample(x, y, 0, findColorIndex(root, aColor));
0N/A }
0N/A }
0N/A
0N/A return dst;
0N/A }
0N/A
0N/A
0N/A protected PaletteBuilder(RenderedImage src) {
0N/A this(src, 256);
0N/A }
0N/A
0N/A protected PaletteBuilder(RenderedImage src, int size) {
0N/A this.src = src;
0N/A this.srcColorModel = src.getColorModel();
0N/A this.srcRaster = src.getData();
0N/A
0N/A this.transparency =
0N/A srcColorModel.getTransparency();
0N/A
0N/A this.requiredSize = size;
0N/A }
0N/A
0N/A private Color getSrcColor(int x, int y) {
0N/A int argb = srcColorModel.getRGB(srcRaster.getDataElements(x, y, null));
0N/A return new Color(argb, transparency != Transparency.OPAQUE);
0N/A }
0N/A
0N/A protected int findColorIndex(ColorNode aNode, Color aColor) {
0N/A if (transparency != Transparency.OPAQUE &&
0N/A aColor.getAlpha() != 0xff)
0N/A {
0N/A return 0; // default transparnt pixel
0N/A }
0N/A
0N/A if (aNode.isLeaf) {
0N/A return aNode.paletteIndex;
0N/A } else {
0N/A int childIndex = getBranchIndex(aColor, aNode.level);
0N/A
0N/A return findColorIndex(aNode.children[childIndex], aColor);
0N/A }
0N/A }
0N/A
0N/A protected void buildPalette() {
0N/A reduceList = new ColorNode[MAXLEVEL + 1];
0N/A for (int i = 0; i < reduceList.length; i++) {
0N/A reduceList[i] = null;
0N/A }
0N/A
0N/A numNodes = 0;
0N/A maxNodes = 0;
0N/A root = null;
0N/A currSize = 0;
0N/A currLevel = MAXLEVEL;
0N/A
0N/A /*
0N/A from the book
0N/A
0N/A */
0N/A
0N/A int w = src.getWidth();
0N/A int h = src.getHeight();
0N/A for (int y = 0; y < h; y++) {
0N/A for (int x = 0; x < w; x++) {
0N/A
0N/A Color aColor = getSrcColor(w - x - 1, h - y - 1);
0N/A /*
0N/A * If transparency of given image is not opaque we assume all
0N/A * colors with alpha less than 1.0 as fully transparent.
0N/A */
0N/A if (transparency != Transparency.OPAQUE &&
0N/A aColor.getAlpha() != 0xff)
0N/A {
0N/A if (transColor == null) {
0N/A this.requiredSize --; // one slot for transparent color
0N/A
0N/A transColor = new ColorNode();
0N/A transColor.isLeaf = true;
0N/A }
0N/A transColor = insertNode(transColor, aColor, 0);
0N/A } else {
0N/A root = insertNode(root, aColor, 0);
0N/A }
0N/A if (currSize > requiredSize) {
0N/A reduceTree();
0N/A }
0N/A }
0N/A }
0N/A }
0N/A
0N/A protected ColorNode insertNode(ColorNode aNode, Color aColor, int aLevel) {
0N/A
0N/A if (aNode == null) {
0N/A aNode = new ColorNode();
0N/A numNodes++;
0N/A if (numNodes > maxNodes) {
0N/A maxNodes = numNodes;
0N/A }
0N/A aNode.level = aLevel;
0N/A aNode.isLeaf = (aLevel > MAXLEVEL);
0N/A if (aNode.isLeaf) {
0N/A currSize++;
0N/A }
0N/A }
0N/A aNode.colorCount++;
0N/A aNode.red += aColor.getRed();
0N/A aNode.green += aColor.getGreen();
0N/A aNode.blue += aColor.getBlue();
0N/A
0N/A if (!aNode.isLeaf) {
0N/A int branchIndex = getBranchIndex(aColor, aLevel);
0N/A if (aNode.children[branchIndex] == null) {
0N/A aNode.childCount++;
0N/A if (aNode.childCount == 2) {
0N/A aNode.nextReducible = reduceList[aLevel];
0N/A reduceList[aLevel] = aNode;
0N/A }
0N/A }
0N/A aNode.children[branchIndex] =
0N/A insertNode(aNode.children[branchIndex], aColor, aLevel + 1);
0N/A }
0N/A return aNode;
0N/A }
0N/A
0N/A protected IndexColorModel getIndexColorModel() {
0N/A int size = currSize;
0N/A if (transColor != null) {
0N/A size ++; // we need place for transparent color;
0N/A }
0N/A
0N/A byte[] red = new byte[size];
0N/A byte[] green = new byte[size];
0N/A byte[] blue = new byte[size];
0N/A
0N/A int index = 0;
0N/A palette = new ColorNode[size];
0N/A if (transColor != null) {
0N/A index ++;
0N/A }
0N/A
0N/A if (root != null) {
0N/A findPaletteEntry(root, index, red, green, blue);
0N/A }
0N/A
0N/A IndexColorModel icm = null;
0N/A if (transColor != null) {
0N/A icm = new IndexColorModel(8, size, red, green, blue, 0);
0N/A } else {
0N/A icm = new IndexColorModel(8, currSize, red, green, blue);
0N/A }
0N/A return icm;
0N/A }
0N/A
0N/A protected int findPaletteEntry(ColorNode aNode, int index,
0N/A byte[] red, byte[] green, byte[] blue)
0N/A {
0N/A if (aNode.isLeaf) {
0N/A red[index] = (byte)(aNode.red/aNode.colorCount);
0N/A green[index] = (byte)(aNode.green/aNode.colorCount);
0N/A blue[index] = (byte)(aNode.blue/aNode.colorCount);
0N/A aNode.paletteIndex = index;
0N/A
0N/A palette[index] = aNode;
0N/A
0N/A index++;
0N/A } else {
0N/A for (int i = 0; i < 8; i++) {
0N/A if (aNode.children[i] != null) {
0N/A index = findPaletteEntry(aNode.children[i], index,
0N/A red, green, blue);
0N/A }
0N/A }
0N/A }
0N/A return index;
0N/A }
0N/A
0N/A protected int getBranchIndex(Color aColor, int aLevel) {
0N/A if (aLevel > MAXLEVEL || aLevel < 0) {
0N/A throw new IllegalArgumentException("Invalid octree node depth: " +
0N/A aLevel);
0N/A }
0N/A
0N/A int shift = MAXLEVEL - aLevel;
0N/A int red_index = 0x1 & ((0xff & aColor.getRed()) >> shift);
0N/A int green_index = 0x1 & ((0xff & aColor.getGreen()) >> shift);
0N/A int blue_index = 0x1 & ((0xff & aColor.getBlue()) >> shift);
0N/A int index = (red_index << 2) | (green_index << 1) | blue_index;
0N/A return index;
0N/A }
0N/A
0N/A protected void reduceTree() {
0N/A int level = reduceList.length - 1;
0N/A while (reduceList[level] == null && level >= 0) {
0N/A level--;
0N/A }
0N/A
0N/A ColorNode thisNode = reduceList[level];
0N/A if (thisNode == null) {
0N/A // nothing to reduce
0N/A return;
0N/A }
0N/A
0N/A // look for element with lower color count
0N/A ColorNode pList = thisNode;
0N/A int minColorCount = pList.colorCount;
0N/A
0N/A int cnt = 1;
0N/A while (pList.nextReducible != null) {
0N/A if (minColorCount > pList.nextReducible.colorCount) {
0N/A thisNode = pList;
0N/A minColorCount = pList.colorCount;
0N/A }
0N/A pList = pList.nextReducible;
0N/A cnt++;
0N/A }
0N/A
0N/A // save pointer to first reducible node
0N/A // NB: current color count for node could be changed in future
0N/A if (thisNode == reduceList[level]) {
0N/A reduceList[level] = thisNode.nextReducible;
0N/A } else {
0N/A pList = thisNode.nextReducible; // we need to process it
0N/A thisNode.nextReducible = pList.nextReducible;
0N/A thisNode = pList;
0N/A }
0N/A
0N/A if (thisNode.isLeaf) {
0N/A return;
0N/A }
0N/A
0N/A // reduce node
0N/A int leafChildCount = thisNode.getLeafChildCount();
0N/A thisNode.isLeaf = true;
0N/A currSize -= (leafChildCount - 1);
0N/A int aDepth = thisNode.level;
0N/A for (int i = 0; i < 8; i++) {
0N/A thisNode.children[i] = freeTree(thisNode.children[i]);
0N/A }
0N/A thisNode.childCount = 0;
0N/A }
0N/A
0N/A protected ColorNode freeTree(ColorNode aNode) {
0N/A if (aNode == null) {
0N/A return null;
0N/A }
0N/A for (int i = 0; i < 8; i++) {
0N/A aNode.children[i] = freeTree(aNode.children[i]);
0N/A }
0N/A
0N/A numNodes--;
0N/A return null;
0N/A }
0N/A
0N/A /**
0N/A * The node of color tree.
0N/A */
0N/A protected class ColorNode {
0N/A public boolean isLeaf;
0N/A public int childCount;
0N/A ColorNode[] children;
0N/A
0N/A public int colorCount;
0N/A public long red;
0N/A public long blue;
0N/A public long green;
0N/A
0N/A public int paletteIndex;
0N/A
0N/A public int level;
0N/A ColorNode nextReducible;
0N/A
0N/A public ColorNode() {
0N/A isLeaf = false;
0N/A level = 0;
0N/A childCount = 0;
0N/A children = new ColorNode[8];
0N/A for (int i = 0; i < 8; i++) {
0N/A children[i] = null;
0N/A }
0N/A
0N/A colorCount = 0;
0N/A red = green = blue = 0;
0N/A
0N/A paletteIndex = 0;
0N/A }
0N/A
0N/A public int getLeafChildCount() {
0N/A if (isLeaf) {
0N/A return 0;
0N/A }
0N/A int cnt = 0;
0N/A for (int i = 0; i < children.length; i++) {
0N/A if (children[i] != null) {
0N/A if (children[i].isLeaf) {
0N/A cnt ++;
0N/A } else {
0N/A cnt += children[i].getLeafChildCount();
0N/A }
0N/A }
0N/A }
0N/A return cnt;
0N/A }
0N/A
0N/A public int getRGB() {
0N/A int r = (int)red/colorCount;
0N/A int g = (int)green/colorCount;
0N/A int b = (int)blue/colorCount;
0N/A
0N/A int c = 0xff << 24 | (0xff&r) << 16 | (0xff&g) << 8 | (0xff&b);
0N/A return c;
0N/A }
0N/A }
0N/A}