1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.imaging.palette;
18
19 import java.util.ArrayList;
20 import java.util.List;
21
22 import org.apache.commons.imaging.ImagingException;
23
24 public class MostPopulatedBoxesMedianCut implements MedianCut {
25
26 @Override
27 public boolean performNextMedianCut(final List<ColorGroup> colorGroups, final boolean ignoreAlpha) throws ImagingException {
28 int maxPoints = 0;
29 ColorGroup colorGroup = null;
30 for (final ColorGroup group : colorGroups) {
31 if (group.maxDiff > 0) {
32 if (group.totalPoints > maxPoints) {
33 colorGroup = group;
34 maxPoints = group.totalPoints;
35 }
36 }
37 }
38 if (colorGroup == null) {
39 return false;
40 }
41
42 final List<ColorCount> colorCounts = colorGroup.getColorCounts();
43
44 double bestScore = Double.MAX_VALUE;
45 ColorComponent bestColorComponent = null;
46 int bestMedianIndex = -1;
47 for (final ColorComponent colorComponent : ColorComponent.values()) {
48 if (ignoreAlpha && colorComponent == ColorComponent.ALPHA) {
49 continue;
50 }
51 colorCounts.sort(new ColorCountComparator(colorComponent));
52 final int countHalf = (int) Math.round((double) colorGroup.totalPoints / 2);
53 int oldCount = 0;
54 int newCount = 0;
55 int medianIndex;
56 for (medianIndex = 0; medianIndex < colorCounts.size(); medianIndex++) {
57 final ColorCount colorCount = colorCounts.get(medianIndex);
58
59 newCount += colorCount.count;
60
61 if (newCount >= countHalf) {
62 break;
63 }
64 oldCount = newCount;
65 }
66 if (medianIndex == colorCounts.size() - 1) {
67 medianIndex--;
68 } else if (medianIndex > 0) {
69 final int newDiff = Math.abs(newCount - countHalf);
70 final int oldDiff = Math.abs(countHalf - oldCount);
71 if (oldDiff < newDiff) {
72 medianIndex--;
73 }
74 }
75
76 final List<ColorCount> lowerColors = new ArrayList<>(colorCounts.subList(0, medianIndex + 1));
77 final List<ColorCount> upperColors = new ArrayList<>(colorCounts.subList(medianIndex + 1, colorCounts.size()));
78 if (lowerColors.isEmpty() || upperColors.isEmpty()) {
79 continue;
80 }
81 final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
82 final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
83 final int diff = Math.abs(lowerGroup.totalPoints - upperGroup.totalPoints);
84 final double score = diff / (double) Math.max(lowerGroup.totalPoints, upperGroup.totalPoints);
85 if (score < bestScore) {
86 bestScore = score;
87 bestColorComponent = colorComponent;
88 bestMedianIndex = medianIndex;
89 }
90 }
91
92 if (bestColorComponent == null) {
93 return false;
94 }
95
96 colorCounts.sort(new ColorCountComparator(bestColorComponent));
97 final List<ColorCount> lowerColors = new ArrayList<>(colorCounts.subList(0, bestMedianIndex + 1));
98 final List<ColorCount> upperColors = new ArrayList<>(colorCounts.subList(bestMedianIndex + 1, colorCounts.size()));
99 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 }