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