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