Author: damjan Date: Wed Sep 26 05:39:31 2012 New Revision: 1390281 URL: http://svn.apache.org/viewvc?rev=1390281&view=rev Log: Palette cleanup. Finish the fancy exact palette algorithm, document everything, and use clearer names.
Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/bmp/BmpImageParser.java commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/gif/GifImageParser.java commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/ico/IcoImageParser.java commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/pcx/PcxWriter.java commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/xpm/XpmImageParser.java commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutQuantizer.java commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/PaletteFactory.java Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/bmp/BmpImageParser.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/bmp/BmpImageParser.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/bmp/BmpImageParser.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/bmp/BmpImageParser.java Wed Sep 26 05:39:31 2012 @@ -772,7 +772,7 @@ public class BmpImageParser extends Imag throw new ImageWriteException("Unknown parameter: " + firstKey); } - final SimplePalette palette = new PaletteFactory().makePaletteSimple( + final SimplePalette palette = new PaletteFactory().makeSimpleRgbPalette( src, 256); BmpWriter writer = null; Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/gif/GifImageParser.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/gif/GifImageParser.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/gif/GifImageParser.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/gif/GifImageParser.java Wed Sep 26 05:39:31 2012 @@ -812,13 +812,13 @@ public class GifImageParser extends Imag int max_colors = hasAlpha ? 255 : 256; - Palette palette2 = new PaletteFactory().makePaletteSimple(src, + Palette palette2 = new PaletteFactory().makeSimpleRgbPalette(src, max_colors); // int palette[] = new PaletteFactory().makePaletteSimple(src, 256); // Map palette_map = paletteToMap(palette); if (palette2 == null) { - palette2 = new PaletteFactory().makePaletteQuantized(src, + palette2 = new PaletteFactory().makeQuantizedRgbPalette(src, max_colors); if (verbose) System.out.println("quantizing"); Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/ico/IcoImageParser.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/ico/IcoImageParser.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/ico/IcoImageParser.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/ico/IcoImageParser.java Wed Sep 26 05:39:31 2012 @@ -730,7 +730,7 @@ public class IcoImageParser extends Imag final PaletteFactory paletteFactory = new PaletteFactory(); final SimplePalette palette = paletteFactory - .makePaletteSimple(src, 256); + .makeSimpleRgbPalette(src, 256); final int bitCount; final boolean hasTransparency = paletteFactory.hasTransparency(src); if (palette == null) { Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/pcx/PcxWriter.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/pcx/PcxWriter.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/pcx/PcxWriter.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/pcx/PcxWriter.java Wed Sep 26 05:39:31 2012 @@ -130,7 +130,7 @@ public class PcxWriter implements PcxCon throws ImageWriteException, IOException { final PaletteFactory paletteFactory = new PaletteFactory(); final SimplePalette palette = paletteFactory - .makePaletteSimple(src, 256); + .makeSimpleRgbPalette(src, 256); BinaryOutputStream bos = new BinaryOutputStream(os, BinaryOutputStream.BYTE_ORDER_INTEL); if (palette == null || bitDepth == 24 || bitDepth == 32) { Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/xpm/XpmImageParser.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/xpm/XpmImageParser.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/xpm/XpmImageParser.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/xpm/XpmImageParser.java Wed Sep 26 05:39:31 2012 @@ -661,7 +661,7 @@ public class XpmImageParser extends Imag int maxColors = writePalette.length; int charsPerPixel = 1; for (; palette == null;) { - palette = paletteFactory.makePaletteSimple(src, + palette = paletteFactory.makeSimpleRgbPalette(src, hasTransparency ? maxColors - 1 : maxColors); if (palette == null) { maxColors *= writePalette.length; Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutQuantizer.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutQuantizer.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutQuantizer.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutQuantizer.java Wed Sep 26 05:39:31 2012 @@ -256,69 +256,65 @@ public class MedianCutQuantizer { List<ColorGroup> color_groups = new ArrayList<ColorGroup>(); ColorGroup root = new ColorGroup(new ArrayList<ColorCount>( color_map.values())); - { - color_groups.add(root); + color_groups.add(root); - final Comparator<ColorGroup> comparator = new Comparator<ColorGroup>() { - public int compare(ColorGroup cg1, ColorGroup cg2) { - if (cg1.max_diff == cg2.max_diff) - return cg2.diff_total - cg1.diff_total; - return cg2.max_diff - cg1.max_diff; - } - }; + final Comparator<ColorGroup> comparator = new Comparator<ColorGroup>() { + public int compare(ColorGroup cg1, ColorGroup cg2) { + if (cg1.max_diff == cg2.max_diff) + return cg2.diff_total - cg1.diff_total; + return cg2.max_diff - cg1.max_diff; + } + }; - while (color_groups.size() < max_colors) { - Collections.sort(color_groups, comparator); + while (color_groups.size() < max_colors) { + Collections.sort(color_groups, comparator); - ColorGroup color_group = color_groups.get(0); + ColorGroup color_group = color_groups.get(0); - if (color_group.max_diff == 0) - break; - if (!ignoreAlpha - && color_group.alpha_diff > color_group.red_diff - && color_group.alpha_diff > color_group.green_diff - && color_group.alpha_diff > color_group.blue_diff) { - doCut(color_group, ALPHA, color_groups); - } else if (color_group.red_diff > color_group.green_diff - && color_group.red_diff > color_group.blue_diff) { - doCut(color_group, RED, color_groups); - } else if (color_group.green_diff > color_group.blue_diff) { - doCut(color_group, GREEN, color_groups); - } else { - doCut(color_group, BLUE, color_groups); - } + if (color_group.max_diff == 0) + break; + if (!ignoreAlpha + && color_group.alpha_diff > color_group.red_diff + && color_group.alpha_diff > color_group.green_diff + && color_group.alpha_diff > color_group.blue_diff) { + doCut(color_group, ALPHA, color_groups); + } else if (color_group.red_diff > color_group.green_diff + && color_group.red_diff > color_group.blue_diff) { + doCut(color_group, RED, color_groups); + } else if (color_group.green_diff > color_group.blue_diff) { + doCut(color_group, GREEN, color_groups); + } else { + doCut(color_group, BLUE, color_groups); } } - { - int palette_size = color_groups.size(); - if (verbose) - Debug.debug("palette size: " + palette_size); + int palette_size = color_groups.size(); + if (verbose) + Debug.debug("palette size: " + palette_size); - int palette[] = new int[palette_size]; + int palette[] = new int[palette_size]; - for (int i = 0; i < color_groups.size(); i++) { - ColorGroup color_group = color_groups.get(i); + for (int i = 0; i < color_groups.size(); i++) { + ColorGroup color_group = color_groups.get(i); - palette[i] = color_group.getMedianValue(); + palette[i] = color_group.getMedianValue(); - color_group.palette_index = i; + color_group.palette_index = i; - if (color_group.color_counts.size() < 1) - throw new ImageWriteException("empty color_group: " - + color_group); + if (color_group.color_counts.size() < 1) + throw new ImageWriteException("empty color_group: " + + color_group); - // if(color_group.) - // Debug.debug("color_group", color_group); - // Debug.debug("palette[" + i + "]", palette[i] + " (" - // + Integer.toHexString(palette[i]) + ")"); - } + // if(color_group.) + // Debug.debug("color_group", color_group); + // Debug.debug("palette[" + i + "]", palette[i] + " (" + // + Integer.toHexString(palette[i]) + ")"); + } - if (palette_size > discrete_colors) - throw new ImageWriteException("palette_size>discrete_colors"); + if (palette_size > discrete_colors) + throw new ImageWriteException("palette_size>discrete_colors"); - return new MedianCutPalette(root, palette); - } + return new MedianCutPalette(root, palette); } private static final int ALPHA = 0; @@ -377,45 +373,42 @@ public class MedianCutQuantizer { } color_groups.remove(color_group); + List<ColorCount> color_counts1 = new ArrayList<ColorCount>( + color_group.color_counts.subList(0, median_index + 1)); + List<ColorCount> color_counts2 = new ArrayList<ColorCount>( + color_group.color_counts.subList(median_index + 1, + color_group.color_counts.size())); + + ColorGroup less, more; { - List<ColorCount> color_counts1 = new ArrayList<ColorCount>( - color_group.color_counts.subList(0, median_index + 1)); - List<ColorCount> color_counts2 = new ArrayList<ColorCount>( - color_group.color_counts.subList(median_index + 1, - color_group.color_counts.size())); - - ColorGroup less, more; - { - less = new ColorGroup(new ArrayList<ColorCount>(color_counts1)); - color_groups.add(less); - } - { - more = new ColorGroup(new ArrayList<ColorCount>(color_counts2)); - color_groups.add(more); - } - - ColorCount median_value = color_group.color_counts - .get(median_index); - int limit; - switch (mode) { - case ALPHA: - limit = median_value.alpha; - break; - case RED: - limit = median_value.red; - break; - case GREEN: - limit = median_value.green; - break; - case BLUE: - limit = median_value.blue; - break; - default: - throw new Error("Bad mode."); - } - color_group.cut = new ColorGroupCut(less, more, mode, limit); + less = new ColorGroup(new ArrayList<ColorCount>(color_counts1)); + color_groups.add(less); + } + { + more = new ColorGroup(new ArrayList<ColorCount>(color_counts2)); + color_groups.add(more); + } + ColorCount median_value = color_group.color_counts + .get(median_index); + int limit; + switch (mode) { + case ALPHA: + limit = median_value.alpha; + break; + case RED: + limit = median_value.red; + break; + case GREEN: + limit = median_value.green; + break; + case BLUE: + limit = median_value.blue; + break; + default: + throw new Error("Bad mode."); } + color_group.cut = new ColorGroupCut(less, more, mode, limit); } private static class ColorGroupCut { Modified: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/PaletteFactory.java URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/PaletteFactory.java?rev=1390281&r1=1390280&r2=1390281&view=diff ============================================================================== --- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/PaletteFactory.java (original) +++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/PaletteFactory.java Wed Sep 26 05:39:31 2012 @@ -26,10 +26,19 @@ import java.util.HashSet; import java.util.List; import java.util.Set; +import org.apache.commons.imaging.ImageWriteException; + public class PaletteFactory { private static final boolean debug = false; - public void makePaletteFancy(BufferedImage src) { + /** + * Builds an exact complete opaque palette containing all the colors in {@code src}, + * using an algorithm that is faster than {@linkplain #makePaletteSimple} for large images + * but uses 2 mebibytes of working memory. Treats all the colors as opaque. + * @param src the image whose palette to build + * @return the palette + */ + public Palette makeExactRgbPaletteFancy(BufferedImage src) { // map what rgb values have been used byte rgbmap[] = new byte[256 * 256 * 32]; @@ -37,7 +46,7 @@ public class PaletteFactory { int width = src.getWidth(); int height = src.getHeight(); - for (int y = 0; y < height; y++) + for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { int argb = src.getRGB(x, y); int rggbb = 0x1fffff & argb; @@ -45,19 +54,12 @@ public class PaletteFactory { int mask = 1 << highred; rgbmap[rggbb] |= mask; } + } int count = 0; for (int i = 0; i < rgbmap.length; i++) { int eight = 0xff & rgbmap[i]; - if ((i < 3) || ((i - rgbmap.length) > -3)) { - } - for (int j = 0; j < 8; j++) { - int mask = 1 << (7 - j); - int bit = eight & mask; - if (bit > 0) - count++; - - } + count += Integer.bitCount(eight); } if (debug) @@ -67,29 +69,21 @@ public class PaletteFactory { int mapsize = 0; for (int i = 0; i < rgbmap.length; i++) { int eight = 0xff & rgbmap[i]; - + int mask = 0x80; for (int j = 0; j < 8; j++) { - int mask = 1 << (7 - j); int bit = eight & mask; + mask >>>= 1; if (bit > 0) { int rgb = i | ((7 - j) << 21); - if (mapsize < colormap.length) - colormap[mapsize] = rgb; - mapsize++; + colormap[mapsize++] = rgb; } } } - if (debug) - System.out.println("mapsize: " + mapsize); - - // for (int i = 0; i < colormap.length; i++) - // { - // int rgb = colormap[i]; - // } - + Arrays.sort(colormap); + return new SimplePalette(colormap); } private int pixelToQuantizationTableIndex(int argb, int precision) { @@ -323,13 +317,13 @@ public class PaletteFactory { } /** - * Builds an inexact palette of at most {@code max} colors in {@code src} + * Builds an inexact opaque palette of at most {@code max} colors in {@code src} * using the Median Cut algorithm. * @param src the image whose palette to build * @param max the maximum number of colors the palette can contain * @return the palette of at most {@code max} colors */ - public Palette makePaletteQuantized(BufferedImage src, int max) { + public Palette makeQuantizedRgbPalette(BufferedImage src, int max) { int precision = 6; // in bits int table_scale = precision * components; @@ -385,15 +379,27 @@ public class PaletteFactory { return new QuantizedPalette(subsets, precision); } + + /** + * Builds an inexact possibly translucent palette of at most {@code max} colors in {@code src} + * using the Median Cut algorithm. + * @param src the image whose palette to build + * @param transparent whether to consider the alpha values + * @param max the maximum number of colors the palette can contain + * @return the palette of at most {@code max} colors + */ + public Palette makeQuantizedRgbaPalette(BufferedImage src, boolean transparent, int max) throws ImageWriteException { + return new MedianCutQuantizer(!transparent).process(src, max, false); + } /** - * Builds an exact and complete palette containing all the colors in {@code src}, + * Builds an exact complete opaque palette containing all the colors in {@code src}, * and fails by returning {@code null} if there are more than {@code max} colors necessary to do this. * @param src the image whose palette to build * @param max the maximum number of colors the palette can contain * @return the complete palette of {@code max} or less colors, or {@code null} if more than {@code max} colors are necessary */ - public SimplePalette makePaletteSimple(BufferedImage src, int max) { + public SimplePalette makeSimpleRgbPalette(BufferedImage src, int max) { // This is not efficient for large values of max, say, max > 256; Set<Integer> rgbs = new HashSet<Integer>();