palette.java

private static void maxMinQuantize(int[] inbuf, int width, int height, Color[] palette) {
		final int HISTSIZE = 64 * 64 * 64;

		// Allocate histogram
		int[] hist = new int[HISTSIZE];

		// Fill histogram
		final int l = width * height;
		for (int i = 0; i < l; i++) {
			int red = (inbuf[i] >> 16) & 0xFF;
			int green = (inbuf[i] >> 8) & 0xFF;
			int blue = inbuf[i] & 0xFF;
			++hist[((red & 0xFC) << 10) + ((green & 0xFC) << 4) + (blue >> 2)];
		}

		// Find the most frequent color
		int j = 1, k = 1;
		for (int i = 0; i < HISTSIZE; i++) {
			if (hist[i] <= k)
				continue;
			j = i;
			k = hist[i];
		}

		int r, g, b;

		// Make it first
		palette[0] = new Color(r = j >> 12, g = (j >> 6) & 0x3F, b = j & 0x3F);

		int dr, dg, db;

		// Find distances from all others to it
		if (palette.length > 1) {
			for (int i = 0; i < HISTSIZE; i++) {
				if (hist[i] == 0)
					continue;
				dr = (i >> 12) - r;
				dg = ((i >> 6) & 0x3F) - g;
				db = (i & 0x3F) - b;
				hist[i] = dr * dr + dg * dg + db * db;
			}
		}

		int ii;

		// Add more colors
		for (ii = 1; ii < palette.length; ii++) {
			// Find farthest color
			j = -1;
			for (int i = k = 0; i < HISTSIZE; i++) {
				if (hist[i] <= k)
					continue;
				j = i;
				k = hist[i];
			}
			// No more colors?
			if (j < 0)
				break;

			// Store into palette
			palette[ii] = new Color(r = j >> 12, g = (j >> 6) & 0x3F, b = j & 0x3F);

			// Update distances
			for (int i = 0; i < HISTSIZE; i++) {
				if (hist[i] == 0)
					continue;
				dr = (i >> 12) - r;
				dg = ((i >> 6) & 0x3F) - g;
				db = (i & 0x3F) - b;
				k = dr * dr + dg * dg + db * db;
				if (k < hist[i])
					hist[i] = k;
			}
		}

		// Upconvert colors
		for (int i = 0; i < ii; i++) {
			Color oldColor = palette[i];
			palette[i] = new Color((oldColor.getRed() << 2) + (oldColor.getRed() >> 4),
					(oldColor.getGreen() << 2) + (oldColor.getGreen() >> 4),
					(oldColor.getBlue() << 2) + (oldColor.getBlue() >> 4));
		}

		// Clear empty slots
		for (int i = ii; i < palette.length; i++) {
			palette[i] = Color.BLACK;
		}
	}