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