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