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.jingle.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