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.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.imaging.ImagingException;
023
024public class MostPopulatedBoxesMedianCut implements MedianCut {
025
026    @Override
027    public boolean performNextMedianCut(final List<ColorGroup> colorGroups, final boolean ignoreAlpha) throws ImagingException {
028        int maxPoints = 0;
029        ColorGroup colorGroup = null;
030        for (final ColorGroup group : colorGroups) {
031            if (group.maxDiff > 0) {
032                if (group.totalPoints > maxPoints) {
033                    colorGroup = group;
034                    maxPoints = group.totalPoints;
035                }
036            }
037        }
038        if (colorGroup == null) {
039            return false;
040        }
041
042        final List<ColorCount> colorCounts = colorGroup.getColorCounts();
043
044        double bestScore = Double.MAX_VALUE;
045        ColorComponent bestColorComponent = null;
046        int bestMedianIndex = -1;
047        for (final ColorComponent colorComponent : ColorComponent.values()) {
048            if (ignoreAlpha && colorComponent == ColorComponent.ALPHA) {
049                continue;
050            }
051            colorCounts.sort(new ColorCountComparator(colorComponent));
052            final int countHalf = (int) Math.round((double) colorGroup.totalPoints / 2);
053            int oldCount = 0;
054            int newCount = 0;
055            int medianIndex;
056            for (medianIndex = 0; medianIndex < colorCounts.size(); medianIndex++) {
057                final ColorCount colorCount = colorCounts.get(medianIndex);
058
059                newCount += colorCount.count;
060
061                if (newCount >= countHalf) {
062                    break;
063                }
064                oldCount = newCount;
065            }
066            if (medianIndex == colorCounts.size() - 1) {
067                medianIndex--;
068            } else if (medianIndex > 0) {
069                final int newDiff = Math.abs(newCount - countHalf);
070                final int oldDiff = Math.abs(countHalf - oldCount);
071                if (oldDiff < newDiff) {
072                    medianIndex--;
073                }
074            }
075
076            final List<ColorCount> lowerColors = new ArrayList<>(colorCounts.subList(0, medianIndex + 1));
077            final List<ColorCount> upperColors = new ArrayList<>(colorCounts.subList(medianIndex + 1, colorCounts.size()));
078            if (lowerColors.isEmpty() || upperColors.isEmpty()) {
079                continue;
080            }
081            final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
082            final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
083            final int diff = Math.abs(lowerGroup.totalPoints - upperGroup.totalPoints);
084            final double score = diff / (double) Math.max(lowerGroup.totalPoints, upperGroup.totalPoints);
085            if (score < bestScore) {
086                bestScore = score;
087                bestColorComponent = colorComponent;
088                bestMedianIndex = medianIndex;
089            }
090        }
091
092        if (bestColorComponent == null) {
093            return false;
094        }
095
096        colorCounts.sort(new ColorCountComparator(bestColorComponent));
097        final List<ColorCount> lowerColors = new ArrayList<>(colorCounts.subList(0, bestMedianIndex + 1));
098        final List<ColorCount> upperColors = new ArrayList<>(colorCounts.subList(bestMedianIndex + 1, colorCounts.size()));
099        final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
100        final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
101        colorGroups.remove(colorGroup);
102        colorGroups.add(lowerGroup);
103        colorGroups.add(upperGroup);
104
105        final ColorCount medianValue = colorCounts.get(bestMedianIndex);
106        int limit;
107        switch (bestColorComponent) {
108        case ALPHA:
109            limit = medianValue.alpha;
110            break;
111        case RED:
112            limit = medianValue.red;
113            break;
114        case GREEN:
115            limit = medianValue.green;
116            break;
117        case BLUE:
118            limit = medianValue.blue;
119            break;
120        default:
121            throw new IllegalArgumentException("Bad mode: " + bestColorComponent);
122        }
123        colorGroup.cut = new ColorGroupCut(lowerGroup, upperGroup, bestColorComponent, limit);
124        return true;
125    }
126}