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.awt.image.BufferedImage;
20 import java.util.ArrayList;
21 import java.util.HashMap;
22 import java.util.List;
23 import java.util.Map;
24
25 import org.apache.commons.imaging.ImagingException;
26 import org.apache.commons.imaging.common.Allocator;
27 import org.apache.commons.imaging.internal.Debug;
28
29 public class MedianCutQuantizer {
30 private final boolean ignoreAlpha;
31
32 public MedianCutQuantizer(final boolean ignoreAlpha) {
33 this.ignoreAlpha = ignoreAlpha;
34 }
35
36 public Map<Integer, ColorCount> groupColors(final BufferedImage image, final int maxColors) {
37 final int max = Integer.MAX_VALUE;
38
39 for (int i = 0; i < 8; i++) {
40 int mask = 0xff & 0xff << i;
41 mask = mask | mask << 8 | mask << 16 | mask << 24;
42
43 Debug.debug("mask(" + i + "): " + mask + " (" + Integer.toHexString(mask) + ")");
44
45 final Map<Integer, ColorCount> result = groupColors1(image, max, mask);
46 if (result != null) {
47 return result;
48 }
49 }
50 throw new IllegalArgumentException();
51 }
52
53 private Map<Integer, ColorCount> groupColors1(final BufferedImage image, final int max, final int mask) {
54 final Map<Integer, ColorCount> colorMap = new HashMap<>();
55
56 final int width = image.getWidth();
57 final int height = image.getHeight();
58
59 final int[] row = Allocator.intArray(width);
60 for (int y = 0; y < height; y++) {
61 image.getRGB(0, y, width, 1, row, 0, width);
62 for (int x = 0; x < width; x++) {
63 int argb = row[x];
64
65 if (ignoreAlpha) {
66 argb &= 0xffffff;
67 }
68 argb &= mask;
69
70 ColorCount color = colorMap.get(argb);
71 if (color == null) {
72 color = new ColorCount(argb);
73 colorMap.put(argb, color);
74 if (colorMap.size() > max) {
75 return null;
76 }
77 }
78 color.count++;
79 }
80 }
81
82 return colorMap;
83 }
84
85 public Palette process(final BufferedImage image, final int maxColors, final MedianCut medianCut) throws ImagingException {
86 final Map<Integer, ColorCount> colorMap = groupColors(image, maxColors);
87
88 final int discreteColors = colorMap.size();
89 if (discreteColors <= maxColors) {
90 Debug.debug("lossless palette: " + discreteColors);
91
92 final int[] palette = Allocator.intArray(discreteColors);
93 final List<ColorCount> colorCounts = new ArrayList<>(colorMap.values());
94
95 for (int i = 0; i < colorCounts.size(); i++) {
96 final ColorCount colorCount = colorCounts.get(i);
97 palette[i] = colorCount.argb;
98 if (ignoreAlpha) {
99 palette[i] |= 0xff000000;
100 }
101 }
102
103 return new SimplePalette(palette);
104 }
105
106 Debug.debug("discrete colors: " + discreteColors);
107
108 final List<ColorGroup> colorGroups = new ArrayList<>();
109 final ColorGroup root = new ColorGroup(new ArrayList<>(colorMap.values()), ignoreAlpha);
110 colorGroups.add(root);
111
112 while (colorGroups.size() < maxColors) {
113 if (!medianCut.performNextMedianCut(colorGroups, ignoreAlpha)) {
114 break;
115 }
116 }
117
118 final int paletteSize = colorGroups.size();
119 Debug.debug("palette size: " + paletteSize);
120
121 final int[] palette = Allocator.intArray(paletteSize);
122
123 for (int i = 0; i < colorGroups.size(); i++) {
124 final ColorGroup colorGroup = colorGroups.get(i);
125
126 palette[i] = colorGroup.getMedianValue();
127
128 colorGroup.paletteIndex = i;
129
130 if (colorGroup.getColorCounts().isEmpty()) {
131 throw new ImagingException("Empty colorGroup: " + colorGroup);
132 }
133 }
134
135 if (paletteSize > discreteColors) {
136 throw new ImagingException("paletteSize > discreteColors");
137 }
138
139 return new MedianCutPalette(root, palette);
140 }
141 }