Here’s a module I’ve been working on. Post a reply if there is anything that can be made better/faster.
This class quantizes an image into 256 colors (generating a palette) and makes the image pixels become indices into the palette.
It’s a very naive approach using vector quantization but I thought it was the simplest to understand and I did not want to implement an octree.
The REFERENCE_PALETTE is an array of 256 colors that are essentially “waypoint” colors in the entire 0-0xffffff range. There is an exponential curve applied to it, similar to gamma.
The program maps the colors in the image into one of these 256 waypoints, then calculates the final palette by averaging all the values in the waypoints into one color per waypoint. The color distance is influenced by a ‘weight’ per channel which just adjusts the results so that green is given more priority than red and red is given more priority than blue (since we can see shades of green the best and blue the worst).
class Quantize256 {
private static final int[] REFERENCE_PALETTE = new int[256];
private static int[] palette = new int[256];
private static int[][] map = new int[256][16];
private static int[] sizes = new int[256];
private static float[] channel_weight = { 0.30f, 0.59f, 0.11f };
static {
for (int i = 0; i < 256; i++) {
REFERENCE_PALETTE[i] = (int) Math.pow(i << 3, 2.18293872);
}
}
static int[] quantize8Bit(int[] image) {
for (int i = 0; i < 256; i++) {
sizes[i] = 0;
}
for (int i = 0; i < image.length; i++) {
int color = image[i];
int min = dist(REFERENCE_PALETTE[0], color);
int closest = 0;
for (int j = 1; j < 256; j++) {
int dst = dist(REFERENCE_PALETTE[j], color);
if (dst < min) {
min = dst;
closest = j;
}
}
add(closest, color);
}
for (int i = 0; i < 256; i++) {
palette[i] = avg(i);
}
for (int i = 0; i < image.length; i++) {
int color = image[i];
int min = dist(palette[0], color);
int closest = 0;
for (int j = 1; j < 256; j++) {
int dst = dist(palette[j], color);
if (dst < min) {
min = dst;
closest = j;
}
}
image[i] = closest;
}
return palette;
}
private static int dist(int x, int y) {
int r = (x >> 16 & 0xff) - (y >> 16 & 0xff);
int g = (x >> 8 & 0xff) - (y >> 8 & 0xff);
int b = (x & 0xff) - (y & 0xff);
return (int) ((r * r) * channel_weight[0] + (g * g) * channel_weight[1] + (b * b) * channel_weight[2]);
}
private static int avg(int v) {
int size = sizes[v];
if (size == 0) {
return 0;
}
int r = 0;
int g = 0;
int b = 0;
for (int i = 0; i < size; i++) {
int c = map[v][i];
r += c >> 16 & 0xff;
g += c >> 8 & 0xff;
b += c & 0xff;
}
return (r / size) << 16 | (g / size) << 8 | (b / size);
}
public static void add(int i, int n) {
int next = sizes[i] + 1;
if (next > map[i].length) {
int nc = map[i].length << 1;
if (next > nc) {
nc = next;
}
int[] copy = new int[nc];
System.arraycopy(map[i], 0, copy, 0, Math.min(map[i].length, nc));
map[i] = copy;
}
map[i][sizes[i]++] = n;
}
}