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    @SuppressWarnings({"JdkObsolete", "this-escape"})
080    public OctTreeQuantizer() {
081        setup(256);
082        colorList = new ArrayList<>(MAX_LEVEL + 1);
083        for (int i = 0; i < MAX_LEVEL + 1; i++)
084            colorList.add(i, new Vector<OctTreeNode>());
085        root = new OctTreeNode();
086    }
087
088    /**
089     * Initialize the quantizer. This should be called before adding any pixels.
090     * @param numColors the number of colors we're quantizing to.
091     */
092    @Override
093    public void setup(int numColors) {
094        maximumColors = numColors;
095        reduceColors = Math.max(512, numColors * 2);
096    }
097
098    /**
099     * Add pixels to the quantizer.
100     * @param pixels the array of ARGB pixels
101     * @param offset the offset into the array
102     * @param count the count of pixels
103     */
104    @Override
105    public void addPixels(int[] pixels, int offset, int count) {
106        for (int i = 0; i < count; i++) {
107            insertColor(pixels[i + offset]);
108            if (colors > reduceColors)
109                reduceTree(reduceColors);
110        }
111    }
112
113    /**
114     * Get the color table index for a color.
115     * @param rgb the color
116     * @return the index
117     */
118    @Override
119    public int getIndexForColor(int rgb) {
120        int red = (rgb >> 16) & 0xff;
121        int green = (rgb >> 8) & 0xff;
122        int blue = rgb & 0xff;
123
124        OctTreeNode node = root;
125
126        for (int level = 0; level <= MAX_LEVEL; level++) {
127            OctTreeNode child;
128            int bit = 0x80 >> level;
129
130            int index = 0;
131            if ((red & bit) != 0)
132                index += 4;
133            if ((green & bit) != 0)
134                index += 2;
135            if ((blue & bit) != 0)
136                index += 1;
137
138            child = node.leaf[index];
139
140            if (child == null)
141                return node.index;
142            else if (child.isLeaf)
143                return child.index;
144            else
145                node = child;
146        }
147        LOGGER.fine("getIndexForColor failed");
148        return 0;
149    }
150
151    private void insertColor(int rgb) {
152        int red = (rgb >> 16) & 0xff;
153        int green = (rgb >> 8) & 0xff;
154        int blue = rgb & 0xff;
155
156        OctTreeNode node = root;
157
158//      LOGGER.fine("insertColor="+Integer.toHexString(rgb));
159        for (int level = 0; level <= MAX_LEVEL; level++) {
160            OctTreeNode child;
161            int bit = 0x80 >> level;
162
163            int index = 0;
164            if ((red & bit) != 0)
165                index += 4;
166            if ((green & bit) != 0)
167                index += 2;
168            if ((blue & bit) != 0)
169                index += 1;
170
171            child = node.leaf[index];
172
173            if (child == null) {
174                node.children++;
175
176                child = new OctTreeNode();
177                child.parent = node;
178                node.leaf[index] = child;
179                node.isLeaf = false;
180                nodes++;
181                colorList.get(level).addElement(child);
182
183                if (level == MAX_LEVEL) {
184                    child.isLeaf = true;
185                    child.count = 1;
186                    child.totalRed = red;
187                    child.totalGreen = green;
188                    child.totalBlue = blue;
189                    child.level = level;
190                    colors++;
191                    return;
192                }
193
194                node = child;
195            } else if (child.isLeaf) {
196                child.count++;
197                child.totalRed += red;
198                child.totalGreen += green;
199                child.totalBlue += blue;
200                return;
201            } else
202                node = child;
203        }
204        LOGGER.fine("insertColor failed");
205    }
206
207    private void reduceTree(int numColors) {
208        for (int level = MAX_LEVEL - 1; level >= 0; level--) {
209            Vector<OctTreeNode> v = colorList.get(level);
210            if (v != null && v.size() > 0) {
211                for (int j = 0; j < v.size(); j++) {
212                    OctTreeNode node = v.elementAt(j);
213                    if (node.children > 0) {
214                        for (int i = 0; i < 8; i++) {
215                            OctTreeNode child = node.leaf[i];
216                            if (child != null) {
217                                if (!child.isLeaf)
218                                    LOGGER.fine("not a leaf!");
219                                node.count += child.count;
220                                node.totalRed += child.totalRed;
221                                node.totalGreen += child.totalGreen;
222                                node.totalBlue += child.totalBlue;
223                                node.leaf[i] = null;
224                                node.children--;
225                                colors--;
226                                nodes--;
227                                colorList.get(level + 1).removeElement(child);
228                            }
229                        }
230                        node.isLeaf = true;
231                        colors++;
232                        if (colors <= numColors)
233                            return;
234                    }
235                }
236            }
237        }
238
239        LOGGER.fine("Unable to reduce the OctTree");
240    }
241
242    /**
243     * Build the color table.
244     * @return the color table
245     */
246    @Override
247    public int[] buildColorTable() {
248        int[] table = new int[colors];
249        buildColorTable(root, table, 0);
250        return table;
251    }
252
253    /**
254     * A quick way to use the quantizer. Just create a table the right size and pass in the pixels.
255     * @param inPixels the input colors
256     * @param table the output color table
257     */
258    public void buildColorTable(int[] inPixels, int[] table) {
259        int count = inPixels.length;
260        maximumColors = table.length;
261        for (int i = 0; i < count; i++) {
262            insertColor(inPixels[i]);
263            if (colors > reduceColors)
264                reduceTree(reduceColors);
265        }
266        if (colors > maximumColors)
267            reduceTree(maximumColors);
268        buildColorTable(root, table, 0);
269    }
270
271    private int buildColorTable(OctTreeNode node, int[] table, int index) {
272        if (colors > maximumColors)
273            reduceTree(maximumColors);
274
275        if (node.isLeaf) {
276            int count = node.count;
277            table[index] = 0xff000000 |
278                ((node.totalRed / count) << 16) |
279                ((node.totalGreen / count) << 8) |
280                node.totalBlue / count;
281            node.index = index++;
282        } else {
283            for (int i = 0; i < 8; i++) {
284                if (node.leaf[i] != null) {
285                    node.index = index;
286                    index = buildColorTable(node.leaf[i], table, index);
287                }
288            }
289        }
290        return index;
291    }
292
293}
294