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