commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dam...@apache.org
Subject svn commit: r1420371 - in /commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging: formats/png/ palette/
Date Tue, 11 Dec 2012 20:03:59 GMT
Author: damjan
Date: Tue Dec 11 20:03:51 2012
New Revision: 1420371

URL: http://svn.apache.org/viewvc?rev=1420371&view=rev
Log:
Extensive rework of the palette code.

The Median Cut algorithm is now pluggable,
and 2 implementations have been added, the old being
the longest axis cutting and the new is similar to
the one used by the PaletteFactory's own version of
Median Cut (which seems to give much better results).

static final constants in MedianCutPalette have been
converted to an enum.

Various cleanups.


Added:
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorComponent.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorCount.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroup.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroupCut.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutImplementation.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutLongestAxisImplementation.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutMostPopulatedBoxesImplementation.java   (with props)
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutPalette.java   (with props)
Modified:
    commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/png/PngWriter.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/png/PngWriter.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/png/PngWriter.java?rev=1420371&r1=1420370&r2=1420371&view=diff
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/png/PngWriter.java (original)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/formats/png/PngWriter.java Tue Dec 11 20:03:51 2012
@@ -28,7 +28,6 @@ import java.util.zip.DeflaterOutputStrea
 import org.apache.commons.imaging.ImageWriteException;
 import org.apache.commons.imaging.PixelDensity;
 import org.apache.commons.imaging.common.ZLibUtils;
-import org.apache.commons.imaging.palette.MedianCutQuantizer;
 import org.apache.commons.imaging.palette.Palette;
 import org.apache.commons.imaging.palette.PaletteFactory;
 import org.apache.commons.imaging.util.Debug;
@@ -490,8 +489,7 @@ public class PngWriter implements PngCon
 
             final int max_colors = hasAlpha ? 255 : 256;
 
-            palette = new MedianCutQuantizer(true).process(src, max_colors,
-                    verbose);
+            palette = new PaletteFactory().makeQuantizedRgbPalette(src, max_colors);
             // Palette palette2 = new PaletteFactory().makePaletteSimple(src,
             // max_colors);
 

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorComponent.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorComponent.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorComponent.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorComponent.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,46 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+enum ColorComponent {
+    ALPHA {
+        @Override
+        public int argbComponent(int argb) {
+            return (argb >> 24) & 0xff;
+        }
+    },
+    RED {
+        @Override
+        public int argbComponent(int argb) {
+            return (argb >> 16) & 0xff;
+        }
+    },
+    GREEN {
+        @Override
+        public int argbComponent(int argb) {
+            return (argb >> 8) & 0xff;
+        }
+    },
+    BLUE {
+        @Override
+        public int argbComponent(int argb) {
+            return (argb & 0xff);
+        }
+    };
+    
+    public abstract int argbComponent(int argb);
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorComponent.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorCount.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorCount.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorCount.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorCount.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+class ColorCount {
+    public final int argb;
+    public int count = 0;
+    public final int alpha, red, green, blue;
+
+    public ColorCount(final int argb) {
+        this.argb = argb;
+
+        alpha = 0xff & (argb >> 24);
+        red = 0xff & (argb >> 16);
+        green = 0xff & (argb >> 8);
+        blue = 0xff & (argb >> 0);
+    }
+
+    @Override
+    public int hashCode() {
+        return argb;
+    }
+
+    @Override
+    public boolean equals(final Object o) {
+        if (o instanceof ColorCount) {
+            final ColorCount other = (ColorCount) o;
+            return other.argb == this.argb;
+        }
+        return false;
+    }
+
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorCount.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroup.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroup.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroup.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroup.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,144 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+import java.util.List;
+
+import org.apache.commons.imaging.ImageWriteException;
+
+class ColorGroup {
+    // public final ColorGroup parent;
+    public ColorGroupCut cut = null;
+    // public final List children = new ArrayList();
+    public int palette_index = -1;
+
+    public final List<ColorCount> color_counts;
+    public final boolean ignoreAlpha;
+    public int min_red = Integer.MAX_VALUE;
+    public int max_red = Integer.MIN_VALUE;
+    public int min_green = Integer.MAX_VALUE;
+    public int max_green = Integer.MIN_VALUE;
+    public int min_blue = Integer.MAX_VALUE;
+    public int max_blue = Integer.MIN_VALUE;
+    public int min_alpha = Integer.MAX_VALUE;
+    public int max_alpha = Integer.MIN_VALUE;
+
+    public final int alpha_diff;
+    public final int red_diff;
+    public final int green_diff;
+    public final int blue_diff;
+
+    public final int max_diff;
+    public final int diff_total;
+    public final int totalPoints;
+
+    public ColorGroup(final List<ColorCount> color_counts, final boolean ignoreAlpha)
+            throws ImageWriteException {
+        this.color_counts = color_counts;
+        this.ignoreAlpha = ignoreAlpha;
+
+        if (color_counts.size() < 1) {
+            throw new ImageWriteException("empty color_group");
+        }
+
+        int totalPoints = 0;
+        for (int i = 0; i < color_counts.size(); i++) {
+            final ColorCount color = color_counts.get(i);
+            totalPoints += color.count;
+
+            min_alpha = Math.min(min_alpha, color.alpha);
+            max_alpha = Math.max(max_alpha, color.alpha);
+            min_red = Math.min(min_red, color.red);
+            max_red = Math.max(max_red, color.red);
+            min_green = Math.min(min_green, color.green);
+            max_green = Math.max(max_green, color.green);
+            min_blue = Math.min(min_blue, color.blue);
+            max_blue = Math.max(max_blue, color.blue);
+        }
+        this.totalPoints = totalPoints;
+
+        alpha_diff = max_alpha - min_alpha;
+        red_diff = max_red - min_red;
+        green_diff = max_green - min_green;
+        blue_diff = max_blue - min_blue;
+        max_diff = Math.max(
+                ignoreAlpha ? red_diff : Math.max(alpha_diff, red_diff),
+                Math.max(green_diff, blue_diff));
+        diff_total = (ignoreAlpha ? 0 : alpha_diff) + red_diff + green_diff
+                + blue_diff;
+
+    }
+
+    public boolean contains(final int argb) {
+        final int alpha = 0xff & (argb >> 24);
+        final int red = 0xff & (argb >> 16);
+        final int green = 0xff & (argb >> 8);
+        final int blue = 0xff & (argb >> 0);
+
+        if (!ignoreAlpha && (alpha < min_alpha || alpha > max_alpha)) {
+            return false;
+        }
+        if (red < min_red || red > max_red) {
+            return false;
+        }
+        if (green < min_green || green > max_green) {
+            return false;
+        }
+        if (blue < min_blue || blue > max_blue) {
+            return false;
+        }
+        return true;
+    }
+
+    public int getMedianValue() {
+        long count_total = 0;
+        long alpha_total = 0, red_total = 0, green_total = 0, blue_total = 0;
+
+        for (int i = 0; i < color_counts.size(); i++) {
+            final ColorCount color = color_counts.get(i);
+
+            count_total += color.count;
+            alpha_total += color.count * color.alpha;
+            red_total += color.count * color.red;
+            green_total += color.count * color.green;
+            blue_total += color.count * color.blue;
+        }
+
+        final int alpha = ignoreAlpha ? 0xff : (int) Math
+                .round((double) alpha_total / count_total);
+        final int red = (int) Math.round((double) red_total / count_total);
+        final int green = (int) Math.round((double) green_total / count_total);
+        final int blue = (int) Math.round((double) blue_total / count_total);
+
+        return (alpha << 24) | (red << 16) | (green << 8) | blue;
+    }
+
+    @Override
+    public String toString() {
+        return "{ColorGroup. min_red: " + Integer.toHexString(min_red)
+                + ", max_red: " + Integer.toHexString(max_red)
+                + ", min_green: " + Integer.toHexString(min_green)
+                + ", max_green: " + Integer.toHexString(max_green)
+                + ", min_blue: " + Integer.toHexString(min_blue)
+                + ", max_blue: " + Integer.toHexString(max_blue)
+                + ", min_alpha: " + Integer.toHexString(min_alpha)
+                + ", max_alpha: " + Integer.toHexString(max_alpha)
+                + ", max_diff: " + Integer.toHexString(max_diff)
+                + ", diff_total: " + diff_total + "}";
+    }
+
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroup.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroupCut.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroupCut.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroupCut.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroupCut.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+class ColorGroupCut {
+    public final ColorGroup less, more;
+    public final ColorComponent mode;
+    public final int limit;
+
+    public ColorGroupCut(final ColorGroup less, final ColorGroup more, final ColorComponent mode,
+            final int limit) {
+        this.less = less;
+        this.more = more;
+        this.mode = mode;
+        this.limit = limit;
+    }
+
+    public ColorGroup getColorGroup(final int argb) {
+        int value = mode.argbComponent(argb);
+        if (value <= limit) {
+            return less;
+        }
+        return more;
+    }
+
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/ColorGroupCut.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutImplementation.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutImplementation.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutImplementation.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutImplementation.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,26 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+import java.util.List;
+
+import org.apache.commons.imaging.ImageWriteException;
+
+public abstract class MedianCutImplementation {
+    public abstract boolean performNextMedianCut(final List<ColorGroup> colorGroups, final boolean ignoreAlpha)
+            throws ImageWriteException;
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutImplementation.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutLongestAxisImplementation.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutLongestAxisImplementation.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutLongestAxisImplementation.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutLongestAxisImplementation.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,141 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+import org.apache.commons.imaging.ImageWriteException;
+
+public class MedianCutLongestAxisImplementation extends MedianCutImplementation {
+    private static final Comparator<ColorGroup> comparator = new Comparator<ColorGroup>() {
+        public int compare(final ColorGroup cg1, final ColorGroup cg2) {
+            if (cg1.max_diff == cg2.max_diff) {
+                return cg2.diff_total - cg1.diff_total;
+            }
+            return cg2.max_diff - cg1.max_diff;
+        }
+    };
+
+    @Override
+    public boolean performNextMedianCut(final List<ColorGroup> color_groups, final boolean ignoreAlpha)
+            throws ImageWriteException {
+        Collections.sort(color_groups, comparator);
+        final ColorGroup color_group = color_groups.get(0);
+
+        if (color_group.max_diff == 0) {
+            return false;
+        }
+        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, ColorComponent.ALPHA, color_groups, ignoreAlpha);
+        } else if (color_group.red_diff > color_group.green_diff
+                && color_group.red_diff > color_group.blue_diff) {
+            doCut(color_group, ColorComponent.RED, color_groups, ignoreAlpha);
+        } else if (color_group.green_diff > color_group.blue_diff) {
+            doCut(color_group, ColorComponent.GREEN, color_groups, ignoreAlpha);
+        } else {
+            doCut(color_group, ColorComponent.BLUE, color_groups, ignoreAlpha);
+        }
+        return true;
+    }
+    
+    private void doCut(final ColorGroup color_group, final ColorComponent mode,
+            final List<ColorGroup> color_groups, final boolean ignoreAlpha) throws ImageWriteException {
+
+        final Comparator<ColorCount> comparator = new Comparator<ColorCount>() {
+            public int compare(final ColorCount c1, final ColorCount c2) {
+                switch (mode) {
+                case ALPHA:
+                    return c1.alpha - c2.alpha;
+                case RED:
+                    return c1.red - c2.red;
+                case GREEN:
+                    return c1.green - c2.green;
+                case BLUE:
+                    return c1.blue - c2.blue;
+                default:
+                    return 0;
+                }
+            }
+        };
+
+        Collections.sort(color_group.color_counts, comparator);
+        final int count_half = (int) Math.round((double) color_group.totalPoints / 2);
+        int old_count = 0, new_count = 0;
+        int median_index;
+        for (median_index = 0; median_index < color_group.color_counts.size(); median_index++) {
+            final ColorCount color_count = color_group.color_counts.get(median_index);
+
+            new_count += color_count.count;
+
+            if (new_count < count_half) {
+                old_count = new_count;
+                continue;
+            }
+            break;
+        }
+
+        if (median_index == color_group.color_counts.size() - 1) {
+            median_index--;
+        } else if (median_index > 0) {
+            final int new_diff = Math.abs(new_count - count_half);
+            final int old_diff = Math.abs(count_half - old_count);
+            if (old_diff < new_diff) {
+                median_index--;
+            }
+        }
+
+        color_groups.remove(color_group);
+        final List<ColorCount> color_counts1 = new ArrayList<ColorCount>(
+                color_group.color_counts.subList(0, median_index + 1));
+        final 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), ignoreAlpha);
+        color_groups.add(less);
+        more = new ColorGroup(new ArrayList<ColorCount>(color_counts2), ignoreAlpha);
+        color_groups.add(more);
+
+        final 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);
+    }
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutLongestAxisImplementation.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutMostPopulatedBoxesImplementation.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutMostPopulatedBoxesImplementation.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutMostPopulatedBoxesImplementation.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutMostPopulatedBoxesImplementation.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,160 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+
+import org.apache.commons.imaging.ImageWriteException;
+
+public class MedianCutMostPopulatedBoxesImplementation extends MedianCutImplementation {
+    @Override
+    public boolean performNextMedianCut(final List<ColorGroup> colorGroups,
+            boolean ignoreAlpha) throws ImageWriteException {
+        int maxPoints = 0;
+        ColorGroup colorGroup = null;
+        for (int i = 0; i < colorGroups.size(); i++) {
+            if (colorGroups.get(i).max_diff > 0) {
+                ColorGroup c = colorGroups.get(i);
+                if (c.totalPoints > maxPoints) {
+                    colorGroup = c;
+                    maxPoints = c.totalPoints;
+                }
+            }
+        }
+        if (colorGroup == null) {
+            return false;
+        }
+        
+        
+        
+        double bestScore = Double.MAX_VALUE;
+        ColorComponent bestColorComponent = null;
+        int bestMedianIndex = -1;
+        for (ColorComponent colorComponent : ColorComponent.values()) {
+            if (ignoreAlpha && colorComponent == ColorComponent.ALPHA) {
+                continue;
+            }
+            Collections.sort(colorGroup.color_counts, new ColorComparer(colorComponent));
+            final int count_half = (int) Math.round((double) colorGroup.totalPoints / 2);
+            int old_count = 0, new_count = 0;
+            int median_index;
+            for (median_index = 0; median_index < colorGroup.color_counts.size(); median_index++) {
+                final ColorCount color_count = colorGroup.color_counts.get(median_index);
+    
+                new_count += color_count.count;
+    
+                if (new_count < count_half) {
+                    old_count = new_count;
+                    continue;
+                }
+                break;
+            }
+            if (median_index == colorGroup.color_counts.size() - 1) {
+                median_index--;
+            } else if (median_index > 0) {
+                final int new_diff = Math.abs(new_count - count_half);
+                final int old_diff = Math.abs(count_half - old_count);
+                if (old_diff < new_diff) {
+                    median_index--;
+                }
+            }
+
+            final List<ColorCount> lowerColors = new ArrayList<ColorCount>(
+                    colorGroup.color_counts.subList(0, median_index + 1));
+            final List<ColorCount> upperColors = new ArrayList<ColorCount>(
+                    colorGroup.color_counts.subList(median_index + 1,
+                            colorGroup.color_counts.size()));
+            if (lowerColors.size() == 0 || upperColors.size() == 0) {
+                continue;
+            }
+            ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
+            ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
+            int diff = Math.abs(lowerGroup.totalPoints - upperGroup.totalPoints);
+            double score = diff / (double)Math.max(lowerGroup.totalPoints, upperGroup.totalPoints);
+            if (score < bestScore) {
+                bestScore = score;
+                bestColorComponent = colorComponent;
+                bestMedianIndex = median_index;
+            }
+        }
+
+        if (bestColorComponent == null) {
+            return false;
+        }
+        
+        Collections.sort(colorGroup.color_counts, new ColorComparer(bestColorComponent));
+        final List<ColorCount> lowerColors = new ArrayList<ColorCount>(
+                colorGroup.color_counts.subList(0, bestMedianIndex + 1));
+        final List<ColorCount> upperColors = new ArrayList<ColorCount>(
+                colorGroup.color_counts.subList(bestMedianIndex + 1,
+                        colorGroup.color_counts.size()));
+        ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
+        ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
+        colorGroups.remove(colorGroup);
+        colorGroups.add(lowerGroup);
+        colorGroups.add(upperGroup);
+        
+        final ColorCount median_value = colorGroup.color_counts
+                .get(bestMedianIndex);
+        int limit;
+        switch (bestColorComponent) {
+        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.");
+        }
+        colorGroup.cut = new ColorGroupCut(lowerGroup, upperGroup, bestColorComponent, limit);
+        return true;
+    }
+    
+    private static class ColorComparer implements Comparator<ColorCount> {
+        private ColorComponent colorComponent;
+        
+        public ColorComparer(ColorComponent colorComponent) {
+            this.colorComponent = colorComponent;
+        }
+        
+        public int compare(final ColorCount c1, final ColorCount c2) {
+            switch (colorComponent) {
+                case ALPHA:
+                    return c1.alpha - c2.alpha;
+                case RED:
+                    return c1.red - c2.red;
+                case GREEN:
+                    return c1.green - c2.green;
+                case BLUE:
+                    return c1.blue - c2.blue;
+                default:
+                    return 0;
+            }
+        }
+    };
+
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutMostPopulatedBoxesImplementation.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutPalette.java
URL: http://svn.apache.org/viewvc/commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutPalette.java?rev=1420371&view=auto
==============================================================================
--- commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutPalette.java (added)
+++ commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutPalette.java Tue Dec 11 20:03:51 2012
@@ -0,0 +1,37 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.imaging.palette;
+
+class MedianCutPalette extends SimplePalette {
+    private final ColorGroup root;
+
+    public MedianCutPalette(final ColorGroup root, final int palette[]) {
+        super(palette);
+        this.root = root;
+    }
+
+    @Override
+    public int getPaletteIndex(final int rgb) {
+        ColorGroup cg = root;
+
+        while (cg.cut != null) {
+            cg = cg.cut.getColorGroup(rgb);
+        }
+
+        return cg.palette_index;
+    }
+}

Propchange: commons/proper/imaging/trunk/src/main/java/org/apache/commons/imaging/palette/MedianCutPalette.java
------------------------------------------------------------------------------
    svn:eol-style = native

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=1420371&r1=1420370&r2=1420371&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 Tue Dec 11 20:03:51 2012
@@ -18,8 +18,6 @@ package org.apache.commons.imaging.palet
 
 import java.awt.image.BufferedImage;
 import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -34,156 +32,7 @@ public class MedianCutQuantizer {
         this.ignoreAlpha = ignore_alpha;
     }
 
-    private static class ColorCount {
-        public final int argb;
-        public int count = 0;
-        public final int alpha, red, green, blue;
-
-        public ColorCount(final int argb) {
-            this.argb = argb;
-
-            alpha = 0xff & (argb >> 24);
-            red = 0xff & (argb >> 16);
-            green = 0xff & (argb >> 8);
-            blue = 0xff & (argb >> 0);
-
-            // super.hashCode();
-        }
-
-        @Override
-        public int hashCode() {
-            return argb;
-        }
-
-        @Override
-        public boolean equals(final Object o) {
-            if (o instanceof ColorCount) {
-                final ColorCount other = (ColorCount) o;
-                return other.argb == this.argb;
-            }
-            return false;
-        }
-
-    }
-
-    private class ColorGroup {
-        // public final ColorGroup parent;
-        public ColorGroupCut cut = null;
-        // public final List children = new ArrayList();
-        public int palette_index = -1;
-
-        public final List<ColorCount> color_counts;
-        public int min_red = Integer.MAX_VALUE;
-        public int max_red = Integer.MIN_VALUE;
-        public int min_green = Integer.MAX_VALUE;
-        public int max_green = Integer.MIN_VALUE;
-        public int min_blue = Integer.MAX_VALUE;
-        public int max_blue = Integer.MIN_VALUE;
-        public int min_alpha = Integer.MAX_VALUE;
-        public int max_alpha = Integer.MIN_VALUE;
-
-        public final int alpha_diff;
-        public final int red_diff;
-        public final int green_diff;
-        public final int blue_diff;
-
-        public final int max_diff;
-        public final int diff_total;
-
-        public ColorGroup(final List<ColorCount> color_counts)
-                throws ImageWriteException {
-            this.color_counts = color_counts;
-
-            if (color_counts.size() < 1) {
-                throw new ImageWriteException("empty color_group");
-            }
-
-            for (int i = 0; i < color_counts.size(); i++) {
-                final ColorCount color = color_counts.get(i);
-
-                min_alpha = Math.min(min_alpha, color.alpha);
-                max_alpha = Math.max(max_alpha, color.alpha);
-                min_red = Math.min(min_red, color.red);
-                max_red = Math.max(max_red, color.red);
-                min_green = Math.min(min_green, color.green);
-                max_green = Math.max(max_green, color.green);
-                min_blue = Math.min(min_blue, color.blue);
-                max_blue = Math.max(max_blue, color.blue);
-            }
-
-            alpha_diff = max_alpha - min_alpha;
-            red_diff = max_red - min_red;
-            green_diff = max_green - min_green;
-            blue_diff = max_blue - min_blue;
-            max_diff = Math.max(
-                    ignoreAlpha ? red_diff : Math.max(alpha_diff, red_diff),
-                    Math.max(green_diff, blue_diff));
-            diff_total = (ignoreAlpha ? 0 : alpha_diff) + red_diff + green_diff
-                    + blue_diff;
-
-        }
-
-        public boolean contains(final int argb) {
-            final int alpha = 0xff & (argb >> 24);
-            final int red = 0xff & (argb >> 16);
-            final int green = 0xff & (argb >> 8);
-            final int blue = 0xff & (argb >> 0);
-
-            if (!ignoreAlpha && (alpha < min_alpha || alpha > max_alpha)) {
-                return false;
-            }
-            if (red < min_red || red > max_red) {
-                return false;
-            }
-            if (green < min_green || green > max_green) {
-                return false;
-            }
-            if (blue < min_blue || blue > max_blue) {
-                return false;
-            }
-            return true;
-        }
-
-        public int getMedianValue() {
-            long count_total = 0;
-            long alpha_total = 0, red_total = 0, green_total = 0, blue_total = 0;
-
-            for (int i = 0; i < color_counts.size(); i++) {
-                final ColorCount color = color_counts.get(i);
-
-                count_total += color.count;
-                alpha_total += color.count * color.alpha;
-                red_total += color.count * color.red;
-                green_total += color.count * color.green;
-                blue_total += color.count * color.blue;
-            }
-
-            final int alpha = ignoreAlpha ? 0xff : (int) Math
-                    .round((double) alpha_total / count_total);
-            final int red = (int) Math.round((double) red_total / count_total);
-            final int green = (int) Math.round((double) green_total / count_total);
-            final int blue = (int) Math.round((double) blue_total / count_total);
-
-            return (alpha << 24) | (red << 16) | (green << 8) | blue;
-        }
-
-        @Override
-        public String toString() {
-            return "{ColorGroup. min_red: " + Integer.toHexString(min_red)
-                    + ", max_red: " + Integer.toHexString(max_red)
-                    + ", min_green: " + Integer.toHexString(min_green)
-                    + ", max_green: " + Integer.toHexString(max_green)
-                    + ", min_blue: " + Integer.toHexString(min_blue)
-                    + ", max_blue: " + Integer.toHexString(max_blue)
-                    + ", min_alpha: " + Integer.toHexString(min_alpha)
-                    + ", max_alpha: " + Integer.toHexString(max_alpha)
-                    + ", max_diff: " + Integer.toHexString(max_diff)
-                    + ", diff_total: " + diff_total + "}";
-        }
-
-    }
-
-    public Map<Integer, ColorCount> groupColors1(final BufferedImage image, final int max,
+    private Map<Integer, ColorCount> groupColors1(final BufferedImage image, final int max,
             final int mask) {
         final Map<Integer, ColorCount> color_map = new HashMap<Integer, ColorCount>();
 
@@ -234,8 +83,9 @@ public class MedianCutQuantizer {
         }
         throw new Error("");
     }
-
-    public Palette process(final BufferedImage image, final int max_colors, final boolean verbose)
+    
+    public Palette process(final BufferedImage image, final int max_colors,
+            final MedianCutImplementation medianCutImplementation, final boolean verbose)
             throws ImageWriteException {
         final Map<Integer, ColorCount> color_map = groupColors(image, max_colors);
 
@@ -266,39 +116,13 @@ public class MedianCutQuantizer {
 
         final List<ColorGroup> color_groups = new ArrayList<ColorGroup>();
         final ColorGroup root = new ColorGroup(new ArrayList<ColorCount>(
-                color_map.values()));
+                color_map.values()), ignoreAlpha);
         color_groups.add(root);
 
-        final Comparator<ColorGroup> comparator = new Comparator<ColorGroup>() {
-            public int compare(final ColorGroup cg1, final 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);
-
-            final ColorGroup color_group = color_groups.get(0);
-
-            if (color_group.max_diff == 0) {
+            if (!medianCutImplementation.performNextMedianCut(color_groups, ignoreAlpha)) {
                 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, ColorComponent.ALPHA, color_groups);
-            } else if (color_group.red_diff > color_group.green_diff
-                    && color_group.red_diff > color_group.blue_diff) {
-                doCut(color_group, ColorComponent.RED, color_groups);
-            } else if (color_group.green_diff > color_group.blue_diff) {
-                doCut(color_group, ColorComponent.GREEN, color_groups);
-            } else {
-                doCut(color_group, ColorComponent.BLUE, color_groups);
-            }
         }
 
         final int palette_size = color_groups.size();
@@ -327,163 +151,4 @@ public class MedianCutQuantizer {
 
         return new MedianCutPalette(root, palette);
     }
-
-    private static enum ColorComponent {
-        ALPHA {
-            @Override
-            public int argbComponent(int argb) {
-                return (argb >> 24) & 0xff;
-            }
-        },
-        RED {
-            @Override
-            public int argbComponent(int argb) {
-                return (argb >> 16) & 0xff;
-            }
-        },
-        GREEN {
-            @Override
-            public int argbComponent(int argb) {
-                return (argb >> 8) & 0xff;
-            }
-        },
-        BLUE {
-            @Override
-            public int argbComponent(int argb) {
-                return (argb & 0xff);
-            }
-        };
-        
-        public abstract int argbComponent(int argb);
-    }
-
-    private void doCut(final ColorGroup color_group, final ColorComponent mode,
-            final List<ColorGroup> color_groups) throws ImageWriteException {
-        int count_total = 0;
-        for (int i = 0; i < color_group.color_counts.size(); i++) {
-            final ColorCount color_count = color_group.color_counts.get(i);
-            count_total += color_count.count;
-        }
-
-        final Comparator<ColorCount> comparator = new Comparator<ColorCount>() {
-            public int compare(final ColorCount c1, final ColorCount c2) {
-                switch (mode) {
-                case ALPHA:
-                    return c1.alpha - c2.alpha;
-                case RED:
-                    return c1.red - c2.red;
-                case GREEN:
-                    return c1.green - c2.green;
-                case BLUE:
-                    return c1.blue - c2.blue;
-                default:
-                    return 0;
-                }
-            }
-        };
-
-        Collections.sort(color_group.color_counts, comparator);
-        final int count_half = (int) Math.round((double) count_total / 2);
-        int old_count = 0, new_count = 0;
-        int median_index;
-        for (median_index = 0; median_index < color_group.color_counts.size(); median_index++) {
-            final ColorCount color_count = color_group.color_counts.get(median_index);
-
-            new_count += color_count.count;
-
-            if (new_count < count_half) {
-                old_count = new_count;
-                continue;
-            }
-            break;
-        }
-
-        if (median_index == color_group.color_counts.size() - 1) {
-            median_index--;
-        } else if (median_index > 0) {
-            final int new_diff = Math.abs(new_count - count_half);
-            final int old_diff = Math.abs(count_half - old_count);
-            if (old_diff < new_diff) {
-                median_index--;
-            }
-        }
-
-        color_groups.remove(color_group);
-        final List<ColorCount> color_counts1 = new ArrayList<ColorCount>(
-                color_group.color_counts.subList(0, median_index + 1));
-        final 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);
-
-        final 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 {
-        public final ColorGroup less, more;
-        public final ColorComponent mode;
-        public final int limit;
-
-        public ColorGroupCut(final ColorGroup less, final ColorGroup more, final ColorComponent mode,
-                final int limit) {
-            this.less = less;
-            this.more = more;
-            this.mode = mode;
-            this.limit = limit;
-        }
-
-        public ColorGroup getColorGroup(final int argb) {
-            int value = mode.argbComponent(argb);
-            if (value <= limit) {
-                return less;
-            }
-            return more;
-        }
-
-    }
-
-    public static class MedianCutPalette extends SimplePalette {
-        private final ColorGroup root;
-
-        public MedianCutPalette(final ColorGroup root, final int palette[]) {
-            super(palette);
-            this.root = root;
-        }
-
-        @Override
-        public int getPaletteIndex(final int rgb) {
-            ColorGroup cg = root;
-
-            while (cg.cut != null) {
-                cg = cg.cut.getColorGroup(rgb);
-            }
-
-            return cg.palette_index;
-        }
-    }
-
 }

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=1420371&r1=1420370&r2=1420371&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 Tue Dec 11 20:03:51 2012
@@ -408,7 +408,8 @@ public class PaletteFactory {
      * @return the palette of at most {@code max} colors
      */
     public Palette makeQuantizedRgbaPalette(final BufferedImage src, final boolean transparent, final int max) throws ImageWriteException {
-        return new MedianCutQuantizer(!transparent).process(src, max, false);
+        return new MedianCutQuantizer(!transparent).process(src, max,
+                new MedianCutLongestAxisImplementation(), false);
     }
 
     /**



Mime
View raw message