001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041: package org.netbeans.modules.mobility.svgcore.export;
042:
043: public final class ShrinkPalette {
044: private static final int MAX_RGB = 255;
045: private static final int MAX_NODES = 266817;
046: private static final int MAX_TREE_DEPTH = 8;
047: private static final int[] SQUARES;
048: private static final int[] SHIFT;
049:
050: static {
051: SQUARES = new int[MAX_RGB + MAX_RGB + 1];
052: for (int i = -MAX_RGB; i <= MAX_RGB; i++) {
053: SQUARES[i + MAX_RGB] = i * i;
054: }
055:
056: SHIFT = new int[MAX_TREE_DEPTH + 1];
057: for (int i = 0; i < MAX_TREE_DEPTH + 1; ++i) {
058: SHIFT[i] = 1 << (15 - i);
059: }
060: }
061:
062: public static int[] quantizeImage(int[][] pixels, int max_colors) {
063: ColorCube cube = new ColorCube(pixels, max_colors);
064: cube.clasify();
065: cube.reduce();
066: cube.assign();
067: return cube.getColorMap();
068: }
069:
070: private static class Search {
071: private int distance;
072: private int color_number;
073: }
074:
075: private static class Node {
076: private ColorCube m_cube;
077: private Node m_parent;
078: private Node[] m_child;
079: private int m_nchild;
080: private int m_id;
081: private int m_level;
082: private int m_mid_red;
083: private int m_mid_green;
084: private int m_mid_blue;
085: private int m_number_pixels;
086: private int m_unique;
087: private int m_total_alpha;
088: private int m_total_red;
089: private int m_total_green;
090: private int m_total_blue;
091: private int m_color_number;
092:
093: Node(ColorCube cube) {
094: m_cube = cube;
095: m_parent = this ;
096: m_child = new Node[8];
097: m_id = 0;
098: m_level = 0;
099: m_number_pixels = Integer.MAX_VALUE;
100: m_mid_red = (MAX_RGB + 1) >> 1;
101: m_mid_green = (MAX_RGB + 1) >> 1;
102: m_mid_blue = (MAX_RGB + 1) >> 1;
103: }
104:
105: Node(Node parent, int id, int level) {
106: m_cube = parent.m_cube;
107: m_parent = parent;
108: m_child = new Node[8];
109: m_id = id;
110: m_level = level;
111:
112: ++m_cube.m_nodes;
113: if (level == m_cube.m_depth) {
114: ++m_cube.m_colors;
115: }
116:
117: ++parent.m_nchild;
118: parent.m_child[id] = this ;
119:
120: int bi = (1 << (MAX_TREE_DEPTH - level)) >> 1;
121: m_mid_red = parent.m_mid_red + ((id & 1) > 0 ? bi : -bi);
122: m_mid_green = parent.m_mid_green
123: + ((id & 2) > 0 ? bi : -bi);
124: m_mid_blue = parent.m_mid_blue + ((id & 4) > 0 ? bi : -bi);
125: }
126:
127: void removeChild() {
128: --m_parent.m_nchild;
129: m_parent.m_unique += m_unique;
130: m_parent.m_total_alpha += m_total_alpha;
131: m_parent.m_total_red += m_total_red;
132: m_parent.m_total_green += m_total_green;
133: m_parent.m_total_blue += m_total_blue;
134: m_parent.m_child[m_id] = null;
135: --m_cube.m_nodes;
136: m_cube = null;
137: m_parent = null;
138: }
139:
140: void removeLevel() {
141: if (m_nchild != 0) {
142: for (int id = 0; id < 8; id++) {
143: if (m_child[id] != null) {
144: m_child[id].removeLevel();
145: }
146: }
147: }
148: if (m_level == m_cube.m_depth) {
149: removeChild();
150: }
151: }
152:
153: int reduce(int threshold, int next_threshold) {
154: if (m_nchild != 0) {
155: for (int id = 0; id < 8; id++) {
156: if (m_child[id] != null) {
157: next_threshold = m_child[id].reduce(threshold,
158: next_threshold);
159: }
160: }
161: }
162: if (m_number_pixels <= threshold) {
163: removeChild();
164: } else {
165: if (m_unique != 0) {
166: m_cube.m_colors++;
167: }
168: if (m_number_pixels < next_threshold) {
169: next_threshold = m_number_pixels;
170: }
171: }
172: return next_threshold;
173: }
174:
175: void fillColorMaps() {
176: if (m_nchild != 0) {
177: for (int id = 0; id < 8; id++) {
178: if (m_child[id] != null) {
179: m_child[id].fillColorMaps();
180: }
181: }
182: }
183: if (m_unique != 0) {
184: int a = (m_total_alpha + (m_unique >> 1)) / m_unique;
185: int r = (m_total_red + (m_unique >> 1)) / m_unique;
186: int g = (m_total_green + (m_unique >> 1)) / m_unique;
187: int b = (m_total_blue + (m_unique >> 1)) / m_unique;
188: m_cube.m_colormap[m_cube.m_colors] = (((a & 0xFF) << 24)
189: | ((r & 0xFF) << 16) | ((g & 0xFF) << 8) | ((b & 0xFF) << 0));
190: m_color_number = m_cube.m_colors++;
191: }
192: }
193:
194: void findNearestColor(int red, int green, int blue,
195: Search search) {
196: if (m_nchild != 0) {
197: for (int id = 0; id < 8; id++) {
198: if (m_child[id] != null) {
199: m_child[id].findNearestColor(red, green, blue,
200: search);
201: }
202: }
203: }
204:
205: if (m_unique != 0) {
206: int color = m_cube.m_colormap[m_color_number];
207: int distance = getDistance(color, red, green, blue);
208: if (distance < search.distance) {
209: search.distance = distance;
210: search.color_number = m_color_number;
211: }
212: }
213: }
214:
215: static final int getDistance(int color, int r, int g, int b) {
216: return SQUARES[((color >> 16) & 0xFF) - r + MAX_RGB]
217: + SQUARES[((color >> 8) & 0xFF) - g + MAX_RGB]
218: + SQUARES[((color >> 0) & 0xFF) - b + MAX_RGB];
219: }
220: }
221:
222: private static class ColorCube {
223: private final Node m_root;
224: private final int[][] m_pixels;
225: private final int m_max_colors;
226: private int[] m_colormap;
227: private int m_depth;
228: private int m_colors;
229: private int m_nodes;
230:
231: ColorCube(int[][] pixels, int max_colors) {
232: m_pixels = pixels;
233: m_max_colors = max_colors;
234: m_colors = 1;
235:
236: int i = max_colors;
237: for (m_depth = 1; i != 0; m_depth++) {
238: i /= 4;
239: }
240: if (m_depth > 1) {
241: --m_depth;
242: }
243: if (m_depth > MAX_TREE_DEPTH) {
244: m_depth = MAX_TREE_DEPTH;
245: } else if (m_depth < 2) {
246: m_depth = 2;
247: }
248: m_root = new Node(this );
249: }
250:
251: void clasify() {
252: int[][] pixels = m_pixels;
253:
254: int width = pixels.length;
255: int height = pixels[0].length;
256:
257: for (int x = width; x-- > 0;) {
258: for (int y = height; y-- > 0;) {
259: int pixel = pixels[x][y];
260: int alpha = (pixel >> 24) & 0xFF;
261: int red = (pixel >> 16) & 0xFF;
262: int green = (pixel >> 8) & 0xFF;
263: int blue = (pixel >> 0) & 0xFF;
264:
265: if (alpha > 0) {
266: if (m_nodes > MAX_NODES) {
267: m_root.removeLevel();
268: --m_depth;
269: }
270:
271: Node node = m_root;
272: for (int level = 1; level <= m_depth; ++level) {
273: int id = ((red > node.m_mid_red ? 1 : 0) << 0)
274: | ((green > node.m_mid_green ? 1
275: : 0) << 1)
276: | ((blue > node.m_mid_blue ? 1 : 0) << 2);
277: if (node.m_child[id] == null) {
278: new Node(node, id, level);
279: }
280: node = node.m_child[id];
281: node.m_number_pixels += SHIFT[level];
282: }
283:
284: ++node.m_unique;
285: node.m_total_alpha += alpha;
286: node.m_total_red += red;
287: node.m_total_green += green;
288: node.m_total_blue += blue;
289: }
290: }
291: }
292: }
293:
294: void reduce() {
295: int threshold = 1;
296: while (m_colors > m_max_colors) {
297: m_colors = 1;
298: threshold = m_root.reduce(threshold, Integer.MAX_VALUE);
299: }
300: }
301:
302: void assign() {
303: m_colormap = new int[m_colors];
304: m_colormap[0] = 0x00800000;
305: m_colors = 1;
306: m_root.fillColorMaps();
307:
308: int[][] pixels = m_pixels;
309: int width = pixels.length;
310: int height = pixels[0].length;
311:
312: Search search = new Search();
313:
314: for (int x = width; x-- > 0;) {
315: for (int y = height; y-- > 0;) {
316: int pixel = pixels[x][y];
317: int alpha = (pixel >> 24) & 0xFF;
318: int red = (pixel >> 16) & 0xFF;
319: int green = (pixel >> 8) & 0xFF;
320: int blue = (pixel >> 0) & 0xFF;
321:
322: if (alpha > 0) {
323: Node node = m_root;
324: for (;;) {
325: int id = ((red > node.m_mid_red ? 1 : 0) << 0)
326: | ((green > node.m_mid_green ? 1
327: : 0) << 1)
328: | ((blue > node.m_mid_blue ? 1 : 0) << 2);
329: if (node.m_child[id] == null) {
330: break;
331: }
332: node = node.m_child[id];
333: }
334:
335: search.distance = Integer.MAX_VALUE;
336: node.m_parent.findNearestColor(red, green,
337: blue, search);
338: pixels[x][y] = search.color_number;
339: } else {
340: pixels[x][y] = 0;
341: }
342: }
343: }
344: }
345:
346: public int[] getColorMap() {
347: return m_colormap;
348: }
349: }
350: }
|