001/** 002 * 003 * Copyright 2006 Jerry Huxtable 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.jivesoftware.smackx.jingleold.mediaimpl.sshare.api; 018 019import java.io.PrintStream; 020import java.util.Vector; 021import java.util.logging.Logger; 022 023/** 024 * An image Quantizer based on the Octree algorithm. This is a very basic implementation 025 * at present and could be much improved by picking the nodes to reduce more carefully 026 * (i.e. not completely at random) when I get the time. 027 */ 028public class OctTreeQuantizer implements Quantizer { 029 030 private static final Logger LOGGER = Logger.getLogger(OctTreeQuantizer.class.getName()); 031 032 /** 033 * The greatest depth the tree is allowed to reach 034 */ 035 final static int MAX_LEVEL = 5; 036 037 /** 038 * An Octtree node. 039 */ 040 class OctTreeNode { 041 int children; 042 int level; 043 OctTreeNode parent; 044 OctTreeNode[] leaf = new OctTreeNode[8]; 045 boolean isLeaf; 046 int count; 047 int totalRed; 048 int totalGreen; 049 int totalBlue; 050 int index; 051 052 /** 053 * A debugging method which prints the tree out. 054 */ 055 public void list(PrintStream s, int level) { 056 String indentStr = ""; 057 for (int i = 0; i < level; i++) 058 indentStr += " "; 059 if (count == 0) 060 LOGGER.fine(indentStr + index + ": count=" + count); 061 else 062 LOGGER.fine(indentStr + index + ": count=" + count + " red=" + (totalRed/count) + " green=" + (totalGreen / count) + " blue=" + (totalBlue / count)); 063 for (int i = 0; i < 8; i++) 064 if (leaf[i] != null) 065 leaf[i].list(s, level+2); 066 } 067 } 068 069 private int nodes = 0; 070 private OctTreeNode root; 071 private int reduceColors; 072 private int maximumColors; 073 private int colors = 0; 074 private Vector<OctTreeNode>[] colorList; 075 076 public OctTreeQuantizer() { 077 setup(256); 078 colorList = new Vector[MAX_LEVEL+1]; 079 for (int i = 0; i < MAX_LEVEL+1; i++) 080 colorList[i] = new Vector<OctTreeNode>(); 081 root = new OctTreeNode(); 082 } 083 084 /** 085 * Initialize the quantizer. This should be called before adding any pixels. 086 * @param numColors the number of colors we're quantizing to. 087 */ 088 public void setup(int numColors) { 089 maximumColors = numColors; 090 reduceColors = Math.max(512, numColors * 2); 091 } 092 093 /** 094 * Add pixels to the quantizer. 095 * @param pixels the array of ARGB pixels 096 * @param offset the offset into the array 097 * @param count the count of pixels 098 */ 099 public void addPixels(int[] pixels, int offset, int count) { 100 for (int i = 0; i < count; i++) { 101 insertColor(pixels[i+offset]); 102 if (colors > reduceColors) 103 reduceTree(reduceColors); 104 } 105 } 106 107 /** 108 * Get the color table index for a color. 109 * @param rgb the color 110 * @return the index 111 */ 112 public int getIndexForColor(int rgb) { 113 int red = (rgb >> 16) & 0xff; 114 int green = (rgb >> 8) & 0xff; 115 int blue = rgb & 0xff; 116 117 OctTreeNode node = root; 118 119 for (int level = 0; level <= MAX_LEVEL; level++) { 120 OctTreeNode child; 121 int bit = 0x80 >> level; 122 123 int index = 0; 124 if ((red & bit) != 0) 125 index += 4; 126 if ((green & bit) != 0) 127 index += 2; 128 if ((blue & bit) != 0) 129 index += 1; 130 131 child = node.leaf[index]; 132 133 if (child == null) 134 return node.index; 135 else if (child.isLeaf) 136 return child.index; 137 else 138 node = child; 139 } 140 LOGGER.fine("getIndexForColor failed"); 141 return 0; 142 } 143 144 private void insertColor(int rgb) { 145 int red = (rgb >> 16) & 0xff; 146 int green = (rgb >> 8) & 0xff; 147 int blue = rgb & 0xff; 148 149 OctTreeNode node = root; 150 151// LOGGER.fine("insertColor="+Integer.toHexString(rgb)); 152 for (int level = 0; level <= MAX_LEVEL; level++) { 153 OctTreeNode child; 154 int bit = 0x80 >> level; 155 156 int index = 0; 157 if ((red & bit) != 0) 158 index += 4; 159 if ((green & bit) != 0) 160 index += 2; 161 if ((blue & bit) != 0) 162 index += 1; 163 164 child = node.leaf[index]; 165 166 if (child == null) { 167 node.children++; 168 169 child = new OctTreeNode(); 170 child.parent = node; 171 node.leaf[index] = child; 172 node.isLeaf = false; 173 nodes++; 174 colorList[level].addElement(child); 175 176 if (level == MAX_LEVEL) { 177 child.isLeaf = true; 178 child.count = 1; 179 child.totalRed = red; 180 child.totalGreen = green; 181 child.totalBlue = blue; 182 child.level = level; 183 colors++; 184 return; 185 } 186 187 node = child; 188 } else if (child.isLeaf) { 189 child.count++; 190 child.totalRed += red; 191 child.totalGreen += green; 192 child.totalBlue += blue; 193 return; 194 } else 195 node = child; 196 } 197 LOGGER.fine("insertColor failed"); 198 } 199 200 private void reduceTree(int numColors) { 201 for (int level = MAX_LEVEL-1; level >= 0; level--) { 202 Vector<OctTreeNode> v = colorList[level]; 203 if (v != null && v.size() > 0) { 204 for (int j = 0; j < v.size(); j++) { 205 OctTreeNode node = v.elementAt(j); 206 if (node.children > 0) { 207 for (int i = 0; i < 8; i++) { 208 OctTreeNode child = node.leaf[i]; 209 if (child != null) { 210 if (!child.isLeaf) 211 LOGGER.fine("not a leaf!"); 212 node.count += child.count; 213 node.totalRed += child.totalRed; 214 node.totalGreen += child.totalGreen; 215 node.totalBlue += child.totalBlue; 216 node.leaf[i] = null; 217 node.children--; 218 colors--; 219 nodes--; 220 colorList[level+1].removeElement(child); 221 } 222 } 223 node.isLeaf = true; 224 colors++; 225 if (colors <= numColors) 226 return; 227 } 228 } 229 } 230 } 231 232 LOGGER.fine("Unable to reduce the OctTree"); 233 } 234 235 /** 236 * Build the color table. 237 * @return the color table 238 */ 239 public int[] buildColorTable() { 240 int[] table = new int[colors]; 241 buildColorTable(root, table, 0); 242 return table; 243 } 244 245 /** 246 * A quick way to use the quantizer. Just create a table the right size and pass in the pixels. 247 * @param inPixels the input colors 248 * @param table the output color table 249 */ 250 public void buildColorTable(int[] inPixels, int[] table) { 251 int count = inPixels.length; 252 maximumColors = table.length; 253 for (int i = 0; i < count; i++) { 254 insertColor(inPixels[i]); 255 if (colors > reduceColors) 256 reduceTree(reduceColors); 257 } 258 if (colors > maximumColors) 259 reduceTree(maximumColors); 260 buildColorTable(root, table, 0); 261 } 262 263 private int buildColorTable(OctTreeNode node, int[] table, int index) { 264 if (colors > maximumColors) 265 reduceTree(maximumColors); 266 267 if (node.isLeaf) { 268 int count = node.count; 269 table[index] = 0xff000000 | 270 ((node.totalRed/count) << 16) | 271 ((node.totalGreen/count) << 8) | 272 node.totalBlue/count; 273 node.index = index++; 274 } else { 275 for (int i = 0; i < 8; i++) { 276 if (node.leaf[i] != null) { 277 node.index = index; 278 index = buildColorTable(node.leaf[i], table, index); 279 } 280 } 281 } 282 return index; 283 } 284 285} 286