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