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