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