Back to index...

	/*
	* 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;
	}
	}
	}

Back to index...