001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  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.apache.commons.imaging.palette;
018
019import java.io.Serializable;
020import java.util.ArrayList;
021import java.util.Collections;
022import java.util.Comparator;
023import java.util.List;
024
025import org.apache.commons.imaging.ImageWriteException;
026
027public class MostPopulatedBoxesMedianCut implements MedianCut {
028
029    @Override
030    public boolean performNextMedianCut(final List<ColorGroup> colorGroups,
031            final boolean ignoreAlpha) throws ImageWriteException {
032        int maxPoints = 0;
033        ColorGroup colorGroup = null;
034        for (final ColorGroup group : colorGroups) {
035            if (group.maxDiff > 0) {
036                if (group.totalPoints > maxPoints) {
037                    colorGroup = group;
038                    maxPoints = group.totalPoints;
039                }
040            }
041        }
042        if (colorGroup == null) {
043            return false;
044        }
045
046
047
048        double bestScore = Double.MAX_VALUE;
049        ColorComponent bestColorComponent = null;
050        int bestMedianIndex = -1;
051        for (final ColorComponent colorComponent : ColorComponent.values()) {
052            if (ignoreAlpha && colorComponent == ColorComponent.ALPHA) {
053                continue;
054            }
055            Collections.sort(colorGroup.colorCounts, new ColorComparer(colorComponent));
056            final int countHalf = (int) Math.round((double) colorGroup.totalPoints / 2);
057            int oldCount = 0;
058            int newCount = 0;
059            int medianIndex;
060            for (medianIndex = 0; medianIndex < colorGroup.colorCounts.size(); medianIndex++) {
061                final ColorCount colorCount = colorGroup.colorCounts.get(medianIndex);
062
063                newCount += colorCount.count;
064
065                if (newCount < countHalf) {
066                    oldCount = newCount;
067                } else {
068                    break;
069                }
070            }
071            if (medianIndex == colorGroup.colorCounts.size() - 1) {
072                medianIndex--;
073            } else if (medianIndex > 0) {
074                final int newDiff = Math.abs(newCount - countHalf);
075                final int oldDiff = Math.abs(countHalf - oldCount);
076                if (oldDiff < newDiff) {
077                    medianIndex--;
078                }
079            }
080
081            final List<ColorCount> lowerColors = new ArrayList<>(
082                    colorGroup.colorCounts.subList(0, medianIndex + 1));
083            final List<ColorCount> upperColors = new ArrayList<>(
084                    colorGroup.colorCounts.subList(medianIndex + 1,
085                            colorGroup.colorCounts.size()));
086            if (lowerColors.isEmpty() || upperColors.isEmpty()) {
087                continue;
088            }
089            final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
090            final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
091            final int diff = Math.abs(lowerGroup.totalPoints - upperGroup.totalPoints);
092            final double score = diff / (double) Math.max(lowerGroup.totalPoints, upperGroup.totalPoints);
093            if (score < bestScore) {
094                bestScore = score;
095                bestColorComponent = colorComponent;
096                bestMedianIndex = medianIndex;
097            }
098        }
099
100        if (bestColorComponent == null) {
101            return false;
102        }
103
104        Collections.sort(colorGroup.colorCounts, new ColorComparer(bestColorComponent));
105        final List<ColorCount> lowerColors = new ArrayList<>(
106                colorGroup.colorCounts.subList(0, bestMedianIndex + 1));
107        final List<ColorCount> upperColors = new ArrayList<>(
108                colorGroup.colorCounts.subList(bestMedianIndex + 1,
109                        colorGroup.colorCounts.size()));
110        final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
111        final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
112        colorGroups.remove(colorGroup);
113        colorGroups.add(lowerGroup);
114        colorGroups.add(upperGroup);
115
116        final ColorCount medianValue = colorGroup.colorCounts.get(bestMedianIndex);
117        int limit;
118        switch (bestColorComponent) {
119            case ALPHA:
120                limit = medianValue.alpha;
121                break;
122            case RED:
123                limit = medianValue.red;
124                break;
125            case GREEN:
126                limit = medianValue.green;
127                break;
128            case BLUE:
129                limit = medianValue.blue;
130                break;
131            default:
132                throw new Error("Bad mode.");
133        }
134        colorGroup.cut = new ColorGroupCut(lowerGroup, upperGroup, bestColorComponent, limit);
135        return true;
136    }
137
138    private static class ColorComparer implements Comparator<ColorCount>, Serializable {
139        private static final long serialVersionUID = 1L;
140
141        private final ColorComponent colorComponent;
142
143        ColorComparer(final ColorComponent colorComponent) {
144            this.colorComponent = colorComponent;
145        }
146
147        @Override
148        public int compare(final ColorCount c1, final ColorCount c2) {
149            switch (colorComponent) {
150                case ALPHA:
151                    return c1.alpha - c2.alpha;
152                case RED:
153                    return c1.red - c2.red;
154                case GREEN:
155                    return c1.green - c2.green;
156                case BLUE:
157                    return c1.blue - c2.blue;
158                default:
159                    return 0;
160            }
161        }
162    }
163
164}