mirror of
https://github.com/spiffcode/hostile-takeover.git
synced 2025-12-16 12:08:36 +00:00
512 lines
12 KiB
C#
512 lines
12 KiB
C#
using System;
|
|
using System.Drawing;
|
|
using SpiffLib;
|
|
using System.Collections;
|
|
|
|
/** Converts an RGB image to 8-bit index color using Heckbert's median-cut
|
|
color quantization algorithm. Based on median.c by Anton Kruger from the
|
|
September, 1994 issue of Dr. Dobbs Journal.
|
|
*/
|
|
namespace m {
|
|
public class MedianCut {
|
|
|
|
static int MAXCOLORS = 256; // maximum # of output colors
|
|
#if false
|
|
// Histogram size for 5 bit color
|
|
static int HSIZE = 32768; // size of image histogram
|
|
#else
|
|
// Histogram size for 6 bit color
|
|
static int HSIZE = 256 * 1024; // size of image histogram
|
|
#endif
|
|
private int[] hist; // RGB histogram and reverse color lookup table
|
|
private int[] histPtr; // points to colors in "hist"
|
|
private Cube[] list; // list of cubes
|
|
#if false
|
|
private int[] pixels32;
|
|
private int width, height;
|
|
#endif
|
|
private Palette m_pal;
|
|
|
|
public MedianCut() {
|
|
}
|
|
|
|
#if false
|
|
public MedianCut(int[] pixels, int width, int height) {
|
|
int color16;
|
|
|
|
pixels32 = pixels;
|
|
this.width = width;
|
|
this.height = height;
|
|
|
|
//build 32x32x32 RGB histogram
|
|
hist = new int[HSIZE];
|
|
for (int i=0; i<width*height; i++) {
|
|
color16 = rgb(pixels32[i]);
|
|
hist[color16]++;
|
|
}
|
|
}
|
|
#endif
|
|
|
|
public MedianCut(ArrayList alsColors) {
|
|
// build histogram
|
|
|
|
hist = new int[HSIZE];
|
|
foreach (Color clr in alsColors) {
|
|
int nColor24 = ((int)clr.R << 16) + ((int)clr.G << 8) + (int)clr.B;
|
|
int nColor = rgb(nColor24);
|
|
hist[nColor]++;
|
|
}
|
|
}
|
|
|
|
int getColorCount() {
|
|
int count = 0;
|
|
for (int i=0; i<HSIZE; i++)
|
|
if (hist[i]>0) count++;
|
|
return count;
|
|
}
|
|
|
|
|
|
Color getModalColor() {
|
|
int max=0;
|
|
int c = 0;
|
|
for (int i=0; i<HSIZE; i++)
|
|
if (hist[i]>max) {
|
|
max = hist[i];
|
|
c = i;
|
|
}
|
|
return Color.FromArgb(red(c), green(c), blue(c));
|
|
}
|
|
|
|
|
|
#if false
|
|
// Coverters for 5 bit color
|
|
// Convert from 24-bit to 15-bit color
|
|
private int rgb(int c) {
|
|
int r = (c&0xf80000)>>19;
|
|
int g = (c&0xf800)>>6;
|
|
int b = (c&0xf8)<<7;
|
|
return b | g | r;
|
|
}
|
|
|
|
// Get red component of a 15-bit color
|
|
private int red(int x) {
|
|
return (x&31)<<3;
|
|
}
|
|
|
|
// Get green component of a 15-bit color
|
|
private int green(int x) {
|
|
return (x>>2)&0xf8;
|
|
}
|
|
|
|
// Get blue component of a 15-bit color
|
|
private int blue(int x) {
|
|
return (x>>7)&0xf8;
|
|
}
|
|
#else
|
|
// Converters for 6 bit color
|
|
// Convert from 24-bit to 18-bit color
|
|
private int rgb(int c) {
|
|
int r = (((c & 0x00fc0000) >> 16) >> 2) << 0;
|
|
int g = (((c & 0x0000fc00) >> 8) >> 2) << 6;
|
|
int b = (((c & 0x000000fc) >> 0) >> 2) << 12;
|
|
return b | g | r;
|
|
}
|
|
|
|
// Get red component of a 18-bit color
|
|
private int red(int x) {
|
|
return ((x >> 0) << 2) & 0xfc;
|
|
}
|
|
|
|
// Get green component of a 18-bit color
|
|
private int green(int x) {
|
|
return ((x >> 6) << 2) & 0xfc;
|
|
}
|
|
|
|
// Get blue component of a 18-bit color
|
|
private int blue(int x) {
|
|
return ((x >> 12) << 2) & 0xfc;
|
|
}
|
|
#endif
|
|
|
|
public Palette GetPalette() {
|
|
return m_pal;
|
|
}
|
|
|
|
/** Uses Heckbert's median-cut algorithm to divide the color space defined by
|
|
"hist" into "maxcubes" cubes. The centroids (average value) of each cube
|
|
are are used to create a color table. "hist" is then updated to function
|
|
as an inverse color map that is used to generate an 8-bit image. */
|
|
public void convert(int maxcubes) {
|
|
|
|
int lr, lg, lb;
|
|
int i, median, color;
|
|
int count;
|
|
int k, level, ncubes, splitpos;
|
|
int longdim=0; //longest dimension of cube
|
|
Cube cube, cubeA, cubeB;
|
|
|
|
// Create initial cube
|
|
list = new Cube[MAXCOLORS];
|
|
histPtr = new int[HSIZE];
|
|
ncubes = 0;
|
|
cube = new Cube();
|
|
for (i=0,color=0; i<=HSIZE-1; i++) {
|
|
if (hist[i] != 0) {
|
|
histPtr[color++] = i;
|
|
cube.count = cube.count + hist[i];
|
|
}
|
|
}
|
|
cube.lower = 0; cube.upper = color-1;
|
|
cube.level = 0;
|
|
Shrink(cube);
|
|
list[ncubes++] = cube;
|
|
|
|
//Main loop
|
|
while (ncubes < maxcubes) {
|
|
|
|
// Search the list of cubes for next cube to split, the lowest level cube
|
|
level = 255; splitpos = -1;
|
|
for (k=0; k<=ncubes-1; k++) {
|
|
if (list[k].lower == list[k].upper) {
|
|
// single color; cannot be split
|
|
} else if (list[k].level < level) {
|
|
level = list[k].level;
|
|
splitpos = k;
|
|
}
|
|
}
|
|
if (splitpos == -1) // no more cubes to split
|
|
break;
|
|
|
|
// Find longest dimension of this cube
|
|
cube = list[splitpos];
|
|
lr = cube.rmax - cube.rmin;
|
|
lg = cube.gmax - cube.gmin;
|
|
lb = cube.bmax - cube.bmin;
|
|
if (lr >= lg && lr >= lb) longdim = 0;
|
|
if (lg >= lr && lg >= lb) longdim = 1;
|
|
if (lb >= lr && lb >= lg) longdim = 2;
|
|
|
|
// Sort along "longdim"
|
|
reorderColors(histPtr, cube.lower, cube.upper, longdim);
|
|
quickSort(histPtr, cube.lower, cube.upper);
|
|
restoreColorOrder(histPtr, cube.lower, cube.upper, longdim);
|
|
|
|
// Find median
|
|
count = 0;
|
|
for (i=cube.lower;i<=cube.upper-1;i++) {
|
|
if (count >= cube.count/2) break;
|
|
color = histPtr[i];
|
|
count = count + hist[color];
|
|
}
|
|
median = i;
|
|
|
|
// Now split "cube" at the median and add the two new
|
|
// cubes to the list of cubes.
|
|
cubeA = new Cube();
|
|
cubeA.lower = cube.lower;
|
|
cubeA.upper = median-1;
|
|
cubeA.count = count;
|
|
cubeA.level = cube.level + 1;
|
|
Shrink(cubeA);
|
|
list[splitpos] = cubeA; // add in old slot
|
|
|
|
cubeB = new Cube();
|
|
cubeB.lower = median;
|
|
cubeB.upper = cube.upper;
|
|
cubeB.count = cube.count - count;
|
|
cubeB.level = cube.level + 1;
|
|
Shrink(cubeB);
|
|
list[ncubes++] = cubeB; // add in new slot */
|
|
}
|
|
|
|
// We have enough cubes, or we have split all we can. Now
|
|
// compute the color map, the inverse color map, and return
|
|
// an 8-bit image.
|
|
makeInverseMap(hist, ncubes);
|
|
//return makeImage();
|
|
}
|
|
|
|
|
|
void Shrink(Cube cube) {
|
|
// Encloses "cube" with a tight-fitting cube by updating the
|
|
// (rmin,gmin,bmin) and (rmax,gmax,bmax) members of "cube".
|
|
|
|
int r, g, b;
|
|
int color;
|
|
int rmin, rmax, gmin, gmax, bmin, bmax;
|
|
|
|
rmin = 255; rmax = 0;
|
|
gmin = 255; gmax = 0;
|
|
bmin = 255; bmax = 0;
|
|
for (int i=cube.lower; i<=cube.upper; i++) {
|
|
color = histPtr[i];
|
|
r = red(color);
|
|
g = green(color);
|
|
b = blue(color);
|
|
if (r > rmax) rmax = r;
|
|
if (r < rmin) rmin = r;
|
|
if (g > gmax) gmax = g;
|
|
if (g < gmin) gmin = g;
|
|
if (b > bmax) bmax = b;
|
|
if (b < bmin) bmin = b;
|
|
}
|
|
cube.rmin = rmin; cube.rmax = rmax;
|
|
cube.gmin = gmin; cube.gmax = gmax;
|
|
cube.gmin = gmin; cube.gmax = gmax;
|
|
}
|
|
|
|
|
|
void makeInverseMap(int[] hist, int ncubes) {
|
|
// For each cube in the list of cubes, computes the centroid
|
|
// (average value) of the colors enclosed by that cube, and
|
|
// then loads the centroids in the color map. Next loads
|
|
// "hist" with indices into the color map
|
|
|
|
int r, g, b;
|
|
int color;
|
|
float rsum, gsum, bsum;
|
|
Cube cube;
|
|
byte[] rLUT = new byte[256];
|
|
byte[] gLUT = new byte[256];
|
|
byte[] bLUT = new byte[256];
|
|
|
|
for (int k=0; k<=ncubes-1; k++) {
|
|
cube = list[k];
|
|
rsum = gsum = bsum = (float)0.0;
|
|
for (int i=cube.lower; i<=cube.upper; i++) {
|
|
color = histPtr[i];
|
|
r = red(color);
|
|
rsum += (float)r*(float)hist[color];
|
|
g = green(color);
|
|
gsum += (float)g*(float)hist[color];
|
|
b = blue(color);
|
|
bsum += (float)b*(float)hist[color];
|
|
}
|
|
|
|
// Update the color map
|
|
r = (int)(rsum/(float)cube.count);
|
|
g = (int)(gsum/(float)cube.count);
|
|
b = (int)(bsum/(float)cube.count);
|
|
#if false
|
|
if (r==248 && g==248 && b==248)
|
|
r=g=b=255; // Restore white (255,255,255)
|
|
#endif
|
|
rLUT[k] = (byte)r;
|
|
gLUT[k] = (byte)g;
|
|
bLUT[k] = (byte)b;
|
|
}
|
|
#if false
|
|
cm = new IndexColorModel(8, ncubes, rLUT, gLUT, bLUT);
|
|
#else
|
|
Color[] aclr = new Color[ncubes];
|
|
for (int iclr = 0; iclr < ncubes; iclr++)
|
|
aclr[iclr] = Color.FromArgb(rLUT[iclr], gLUT[iclr], bLUT[iclr]);
|
|
m_pal = new Palette(aclr);
|
|
#endif
|
|
|
|
// For each color in each cube, load the corre-
|
|
// sponding slot in "hist" with the centroid of the cube.
|
|
for (int k=0; k<=ncubes-1; k++) {
|
|
cube = list[k];
|
|
for (int i=cube.lower; i<=cube.upper; i++) {
|
|
color = histPtr[i];
|
|
hist[color] = k;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
void reorderColors(int[] a, int lo, int hi, int longDim) {
|
|
#if false
|
|
// Change the ordering of the 5-bit colors in each word of int[]
|
|
// so we can sort on the 'longDim' color
|
|
|
|
int c, r, g, b;
|
|
switch (longDim) {
|
|
case 0: //red
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c & 31;
|
|
a[i] = (r<<10) | (c>>5);
|
|
}
|
|
break;
|
|
case 1: //green
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c & 31;
|
|
g = (c>>5) & 31;
|
|
b = c>>10;
|
|
a[i] = (g<<10) | (b<<5) | r;
|
|
}
|
|
break;
|
|
case 2: //blue; already in the needed order
|
|
break;
|
|
}
|
|
#else
|
|
// Change the ordering of the 6-bit colors in each word of int[]
|
|
// so we can sort on the 'longDim' color
|
|
|
|
int c, r, g, b;
|
|
switch (longDim) {
|
|
case 0: //red
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c & 0x3f;
|
|
a[i] = (r<<12) | (c>>6);
|
|
}
|
|
break;
|
|
case 1: //green
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c & 0x3f;
|
|
g = (c>>6) & 0x3f;
|
|
b = c>>12;
|
|
a[i] = (g<<12) | (b<<6) | r;
|
|
}
|
|
break;
|
|
case 2: //blue; already in the needed order
|
|
break;
|
|
}
|
|
#endif
|
|
}
|
|
|
|
|
|
void restoreColorOrder(int[] a, int lo, int hi, int longDim) {
|
|
#if false
|
|
// Restore the 5-bit colors to the original order
|
|
|
|
int c, r, g, b;
|
|
switch (longDim){
|
|
case 0: //red
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c >> 10;
|
|
a[i] = ((c&1023)<<5) | r;
|
|
}
|
|
break;
|
|
case 1: //green
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c & 31;
|
|
g = c>>10;
|
|
b = (c>>5) & 31;
|
|
a[i] = (b<<10) | (g<<5) | r;
|
|
}
|
|
break;
|
|
case 2: //blue
|
|
break;
|
|
}
|
|
#else
|
|
// Restore the 6-bit colors to the original order
|
|
|
|
int c, r, g, b;
|
|
switch (longDim){
|
|
case 0: //red
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c >> 12;
|
|
a[i] = ((c&0xfff)<<6) | r;
|
|
}
|
|
break;
|
|
case 1: //green
|
|
for (int i=lo; i<=hi; i++) {
|
|
c = a[i];
|
|
r = c & 0x3f;
|
|
g = c>>12;
|
|
b = (c>>6) & 0x3f;
|
|
a[i] = (b<<12) | (g<<6) | r;
|
|
}
|
|
break;
|
|
case 2: //blue
|
|
break;
|
|
}
|
|
#endif
|
|
}
|
|
|
|
|
|
void quickSort(int[] a, int lo0, int hi0) {
|
|
// Based on the QuickSort method by James Gosling from Sun's SortDemo applet
|
|
|
|
int lo = lo0;
|
|
int hi = hi0;
|
|
int mid, t;
|
|
|
|
if ( hi0 > lo0) {
|
|
mid = a[ ( lo0 + hi0 ) / 2 ];
|
|
while( lo <= hi ) {
|
|
while( ( lo < hi0 ) && ( a[lo] < mid ) )
|
|
++lo;
|
|
while( ( hi > lo0 ) && ( a[hi] > mid ) )
|
|
--hi;
|
|
if( lo <= hi ) {
|
|
t = a[lo];
|
|
a[lo] = a[hi];
|
|
a[hi] = t;
|
|
++lo;
|
|
--hi;
|
|
}
|
|
}
|
|
if( lo0 < hi )
|
|
quickSort( a, lo0, hi );
|
|
if( lo < hi0 )
|
|
quickSort( a, lo, hi0 );
|
|
|
|
}
|
|
}
|
|
|
|
#if false
|
|
public Image makeImage() {
|
|
// Generate 8-bit image
|
|
|
|
#if false
|
|
Image img8;
|
|
#endif
|
|
byte[] pixels8;
|
|
int color16;
|
|
|
|
pixels8 = new byte[width*height];
|
|
for (int i=0; i<width*height; i++) {
|
|
color16 = rgb(pixels32[i]);
|
|
pixels8[i] = (byte)hist[color16];
|
|
}
|
|
#if false
|
|
img8 = Toolkit.getDefaultToolkit().createImage(new MemoryImageSource(width, height, cm, pixels8, 0, width));
|
|
#else
|
|
Bitmap img8 = new Bitmap(width, height);
|
|
for (int y = 0; y < height; y++) {
|
|
for (int x = 0; x < width; x++) {
|
|
img8.SetPixel(x, y, m_pal[pixels8[y * width + x]]);
|
|
}
|
|
}
|
|
#endif
|
|
return img8;
|
|
}
|
|
#endif
|
|
|
|
} //class MedianCut
|
|
|
|
|
|
public class Cube { // structure for a cube in color space
|
|
public int lower; // one corner's index in histogram
|
|
public int upper; // another corner's index in histogram
|
|
public int count; // cube's histogram count
|
|
public int level; // cube's level
|
|
public int rmin, rmax;
|
|
public int gmin, gmax;
|
|
public int bmin, bmax;
|
|
|
|
public Cube() {
|
|
count = 0;
|
|
}
|
|
|
|
public String toString() {
|
|
String s = "lower=" + lower + " upper=" + upper;
|
|
s = s + " count=" + count + " level=" + level;
|
|
s = s + " rmin=" + rmin + " rmax=" + rmax;
|
|
s = s + " gmin=" + gmin + " gmax=" + gmax;
|
|
s = s + " bmin=" + bmin + " bmax=" + bmax;
|
|
return s;
|
|
}
|
|
}
|
|
}
|