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