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}