| 1 |
#ifndef lint
|
| 2 |
static const char RCSid[] = "$Id: cut.c,v 2.4 2004/03/28 20:33:13 schorsch Exp $";
|
| 3 |
#endif
|
| 4 |
/*
|
| 5 |
CUT - Median bisection (k-d tree) algorithm for color image quantization
|
| 6 |
|
| 7 |
flaw: doesn't always create as many colors as requested
|
| 8 |
because the binary subdivision is always done in a balanced tree and when a box
|
| 9 |
contains only one color it's unsplittable
|
| 10 |
|
| 11 |
Paul Heckbert
|
| 12 |
*/
|
| 13 |
|
| 14 |
#include "ciq.h"
|
| 15 |
|
| 16 |
struct index {short *o; int freq;};
|
| 17 |
/* offset and pixel count for a box */
|
| 18 |
|
| 19 |
struct pail {struct plum *first; int freak;};
|
| 20 |
/* each pail is a bucket containing plums */
|
| 21 |
|
| 22 |
struct plum {struct plum *next; int code;};
|
| 23 |
/* a color in a pail's linked list */
|
| 24 |
|
| 25 |
static short off[len];
|
| 26 |
/* color codes: offsets of colors in hist array */
|
| 27 |
|
| 28 |
static void splitbox(struct index *ii, struct index *io);
|
| 29 |
|
| 30 |
|
| 31 |
int
|
| 32 |
makecm( /* subdivide colorspace to generate a colormap*/
|
| 33 |
int nw,
|
| 34 |
int *na /* number of colors wanted, actual */
|
| 35 |
)
|
| 36 |
{
|
| 37 |
int i,m,n,freq,weight,sr,sg,sb;
|
| 38 |
short *o;
|
| 39 |
struct index index[257]; /* pointers into off */
|
| 40 |
/* index[i].o is pointer to code for first color in box i */
|
| 41 |
|
| 42 |
for (o=off, *na=i=0; i<len; i++)
|
| 43 |
if (hist[i]) {
|
| 44 |
(*na)++;
|
| 45 |
*o++ = i; /* initialize offsets */
|
| 46 |
}
|
| 47 |
index[0].o = off; /* start with one big box which contains all *na colors */
|
| 48 |
index[0].freq = xmax*ymax; /* and (sum of hist[i]) pixels */
|
| 49 |
index[1].o = off+*na;
|
| 50 |
|
| 51 |
/* breadth-first binary subdivision: try to make nw boxes */
|
| 52 |
for (m=1; m<nw; m<<=1) {
|
| 53 |
/*printf("%d ",m);*/
|
| 54 |
index[m<<1].o = index[m].o;
|
| 55 |
for (i=m-1; i>=0; --i) splitbox(index+i,index+(i<<1));
|
| 56 |
}
|
| 57 |
for (n=i=0; i<m && n<nw; i++) if (index[i+1].o>index[i].o) {
|
| 58 |
sr = sg = sb = (freq = index[i].freq)>>1;
|
| 59 |
for (o=index[i].o; o<index[i+1].o; o++) {
|
| 60 |
weight = hist[*o];
|
| 61 |
/* find weighted average of colors in box i */
|
| 62 |
sr += red(*o)*weight;
|
| 63 |
sg += gre(*o)*weight;
|
| 64 |
sb += blu(*o)*weight;
|
| 65 |
}
|
| 66 |
color[0][n] = sr/freq;
|
| 67 |
color[1][n] = sg/freq;
|
| 68 |
color[2][n] = sb/freq;
|
| 69 |
/* printf("color[%d]=(%3d,%3d,%3d) freq=%d\n",
|
| 70 |
n,color[0][n],color[1][n],color[2][n],freq); */
|
| 71 |
n++;
|
| 72 |
}
|
| 73 |
/*printf("[%d empty boxes] from %d to %d colors\n",nw-n,*na,n);*/
|
| 74 |
return n;
|
| 75 |
}
|
| 76 |
|
| 77 |
static void
|
| 78 |
splitbox( /* split a box in two: half of the pixels from */
|
| 79 |
struct index *ii, /* box ii will go into io, the other half into io+1 */
|
| 80 |
struct index *io
|
| 81 |
)
|
| 82 |
{
|
| 83 |
register short *o,*o1,*o2;
|
| 84 |
register int shift,count,k,freq,r,g,b,r1,g1,b1,r2,g2,b2;
|
| 85 |
struct pail pail[32],*p,*q; /* buckets for sorting colors */
|
| 86 |
struct plum plum[len],*pl=plum,*u; /* colors */
|
| 87 |
|
| 88 |
o1 = ii[0].o;
|
| 89 |
o2 = ii[1].o;
|
| 90 |
freq = ii[0].freq; /* number of pixels with color in this box */
|
| 91 |
r1 = g1 = b1 = 256; r2 = g2 = b2 = -1;
|
| 92 |
for (o=o1; o<o2; o++) {
|
| 93 |
r = red(*o);
|
| 94 |
g = gre(*o);
|
| 95 |
b = blu(*o);
|
| 96 |
if (r<r1) r1 = r; if (r>r2) r2 = r; /* find min&max r, g, and b */
|
| 97 |
if (g<g1) g1 = g; if (g>g2) g2 = g;
|
| 98 |
if (b<b1) b1 = b; if (b>b2) b2 = b;
|
| 99 |
}
|
| 100 |
|
| 101 |
/* adaptive partitioning: find dominant dimension */
|
| 102 |
shift = r2-r1>g2-g1?r2-r1>=b2-b1?10:0:g2-g1>=b2-b1?5:0;
|
| 103 |
/* printf("splitbox %3d-%3d %3dx%3dx%3d %c ",
|
| 104 |
o1-off,o2-off,r2-r1,g2-g1,b2-b1,shift==10?'R':shift==5?'G':'B'); */
|
| 105 |
|
| 106 |
for (p=pail, k=0; k<32; k++, p++) { /* start with empty pails */
|
| 107 |
p->first = 0;
|
| 108 |
p->freak = 0;
|
| 109 |
}
|
| 110 |
for (o=o1; o<o2; o++) {
|
| 111 |
p = pail+(*o>>shift&31); /* find appropriate pail */
|
| 112 |
pl->code = *o;
|
| 113 |
pl->next = p->first;
|
| 114 |
p->first = pl++; /* add new plum to pail */
|
| 115 |
p->freak += hist[*o];
|
| 116 |
}
|
| 117 |
|
| 118 |
/* find median along dominant dimension */
|
| 119 |
for (count=freq>>1, p=pail; count>0; p++) count -= p->freak;
|
| 120 |
|
| 121 |
if (p>pail && count+(p-1)->freak<-count) /* back up one? */
|
| 122 |
count += (--p)->freak;
|
| 123 |
|
| 124 |
io[1].o = o1; /* in case of empty box */
|
| 125 |
for (o=o1, q=pail; o<o2;) { /* dump the pails to reorder colors in box */
|
| 126 |
for (u=q->first; u; u=u->next) *o++ = u->code;
|
| 127 |
if (++q==p) io[1].o = o; /* place partition at offset o */
|
| 128 |
}
|
| 129 |
io[0].o = o1;
|
| 130 |
io[0].freq = (freq>>1)-count;
|
| 131 |
io[1].freq = ((freq+1)>>1)+count;
|
| 132 |
/* printf(" at %3d %d=%d+%d\n",io[1].o-off,freq,io[0].freq,io[1].freq); */
|
| 133 |
}
|
