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 && group.totalPoints > maxPoints) {
32 colorGroup = group;
33 maxPoints = group.totalPoints;
34 }
35 }
36 if (colorGroup == null) {
37 return false;
38 }
39
40 final List<ColorCount> colorCounts = colorGroup.getColorCounts();
41
42 double bestScore = Double.MAX_VALUE;
43 ColorComponent bestColorComponent = null;
44 int bestMedianIndex = -1;
45 for (final ColorComponent colorComponent : ColorComponent.values()) {
46 if (ignoreAlpha && colorComponent == ColorComponent.ALPHA) {
47 continue;
48 }
49 colorCounts.sort(new ColorCountComparator(colorComponent));
50 final int countHalf = (int) Math.round((double) colorGroup.totalPoints / 2);
51 int oldCount = 0;
52 int newCount = 0;
53 int medianIndex;
54 for (medianIndex = 0; medianIndex < colorCounts.size(); medianIndex++) {
55 final ColorCount colorCount = colorCounts.get(medianIndex);
56
57 newCount += colorCount.count;
58
59 if (newCount >= countHalf) {
60 break;
61 }
62 oldCount = newCount;
63 }
64 if (medianIndex == colorCounts.size() - 1) {
65 medianIndex--;
66 } else if (medianIndex > 0) {
67 final int newDiff = Math.abs(newCount - countHalf);
68 final int oldDiff = Math.abs(countHalf - oldCount);
69 if (oldDiff < newDiff) {
70 medianIndex--;
71 }
72 }
73
74 final List<ColorCount> lowerColors = new ArrayList<>(colorCounts.subList(0, medianIndex + 1));
75 final List<ColorCount> upperColors = new ArrayList<>(colorCounts.subList(medianIndex + 1, colorCounts.size()));
76 if (lowerColors.isEmpty() || upperColors.isEmpty()) {
77 continue;
78 }
79 final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
80 final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
81 final int diff = Math.abs(lowerGroup.totalPoints - upperGroup.totalPoints);
82 final double score = diff / (double) Math.max(lowerGroup.totalPoints, upperGroup.totalPoints);
83 if (score < bestScore) {
84 bestScore = score;
85 bestColorComponent = colorComponent;
86 bestMedianIndex = medianIndex;
87 }
88 }
89
90 if (bestColorComponent == null) {
91 return false;
92 }
93
94 colorCounts.sort(new ColorCountComparator(bestColorComponent));
95 final List<ColorCount> lowerColors = new ArrayList<>(colorCounts.subList(0, bestMedianIndex + 1));
96 final List<ColorCount> upperColors = new ArrayList<>(colorCounts.subList(bestMedianIndex + 1, colorCounts.size()));
97 final ColorGroup lowerGroup = new ColorGroup(lowerColors, ignoreAlpha);
98 final ColorGroup upperGroup = new ColorGroup(upperColors, ignoreAlpha);
99 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 }