| 1 |
#ifndef lint |
| 2 |
static const char RCSid[] = "$Id$"; |
| 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 |
|
| 29 |
makecm(nw,na) /* subdivide colorspace to generate a colormap*/ |
| 30 |
int nw,*na; /* number of colors wanted, actual */ |
| 31 |
{ |
| 32 |
int i,m,n,freq,weight,sr,sg,sb; |
| 33 |
short *o; |
| 34 |
struct index index[257]; /* pointers into off */ |
| 35 |
/* index[i].o is pointer to code for first color in box i */ |
| 36 |
|
| 37 |
for (o=off, *na=i=0; i<len; i++) |
| 38 |
if (hist[i]) { |
| 39 |
(*na)++; |
| 40 |
*o++ = i; /* initialize offsets */ |
| 41 |
} |
| 42 |
index[0].o = off; /* start with one big box which contains all *na colors */ |
| 43 |
index[0].freq = xmax*ymax; /* and (sum of hist[i]) pixels */ |
| 44 |
index[1].o = off+*na; |
| 45 |
|
| 46 |
/* breadth-first binary subdivision: try to make nw boxes */ |
| 47 |
for (m=1; m<nw; m<<=1) { |
| 48 |
/*printf("%d ",m);*/ |
| 49 |
index[m<<1].o = index[m].o; |
| 50 |
for (i=m-1; i>=0; --i) splitbox(index+i,index+(i<<1)); |
| 51 |
} |
| 52 |
for (n=i=0; i<m && n<nw; i++) if (index[i+1].o>index[i].o) { |
| 53 |
sr = sg = sb = (freq = index[i].freq)>>1; |
| 54 |
for (o=index[i].o; o<index[i+1].o; o++) { |
| 55 |
weight = hist[*o]; |
| 56 |
/* find weighted average of colors in box i */ |
| 57 |
sr += red(*o)*weight; |
| 58 |
sg += gre(*o)*weight; |
| 59 |
sb += blu(*o)*weight; |
| 60 |
} |
| 61 |
color[0][n] = sr/freq; |
| 62 |
color[1][n] = sg/freq; |
| 63 |
color[2][n] = sb/freq; |
| 64 |
/* printf("color[%d]=(%3d,%3d,%3d) freq=%d\n", |
| 65 |
n,color[0][n],color[1][n],color[2][n],freq); */ |
| 66 |
n++; |
| 67 |
} |
| 68 |
/*printf("[%d empty boxes] from %d to %d colors\n",nw-n,*na,n);*/ |
| 69 |
return n; |
| 70 |
} |
| 71 |
|
| 72 |
splitbox(ii,io) /* split a box in two: half of the pixels from */ |
| 73 |
struct index *ii,*io; /* box ii will go into io, the other half into io+1 */ |
| 74 |
{ |
| 75 |
register short *o,*o1,*o2; |
| 76 |
register int shift,count,k,freq,r,g,b,r1,g1,b1,r2,g2,b2; |
| 77 |
struct pail pail[32],*p,*q; /* buckets for sorting colors */ |
| 78 |
struct plum plum[len],*pl=plum,*u; /* colors */ |
| 79 |
|
| 80 |
o1 = ii[0].o; |
| 81 |
o2 = ii[1].o; |
| 82 |
freq = ii[0].freq; /* number of pixels with color in this box */ |
| 83 |
r1 = g1 = b1 = 256; r2 = g2 = b2 = -1; |
| 84 |
for (o=o1; o<o2; o++) { |
| 85 |
r = red(*o); |
| 86 |
g = gre(*o); |
| 87 |
b = blu(*o); |
| 88 |
if (r<r1) r1 = r; if (r>r2) r2 = r; /* find min&max r, g, and b */ |
| 89 |
if (g<g1) g1 = g; if (g>g2) g2 = g; |
| 90 |
if (b<b1) b1 = b; if (b>b2) b2 = b; |
| 91 |
} |
| 92 |
|
| 93 |
/* adaptive partitioning: find dominant dimension */ |
| 94 |
shift = r2-r1>g2-g1?r2-r1>=b2-b1?10:0:g2-g1>=b2-b1?5:0; |
| 95 |
/* printf("splitbox %3d-%3d %3dx%3dx%3d %c ", |
| 96 |
o1-off,o2-off,r2-r1,g2-g1,b2-b1,shift==10?'R':shift==5?'G':'B'); */ |
| 97 |
|
| 98 |
for (p=pail, k=0; k<32; k++, p++) { /* start with empty pails */ |
| 99 |
p->first = 0; |
| 100 |
p->freak = 0; |
| 101 |
} |
| 102 |
for (o=o1; o<o2; o++) { |
| 103 |
p = pail+(*o>>shift&31); /* find appropriate pail */ |
| 104 |
pl->code = *o; |
| 105 |
pl->next = p->first; |
| 106 |
p->first = pl++; /* add new plum to pail */ |
| 107 |
p->freak += hist[*o]; |
| 108 |
} |
| 109 |
|
| 110 |
/* find median along dominant dimension */ |
| 111 |
for (count=freq>>1, p=pail; count>0; p++) count -= p->freak; |
| 112 |
|
| 113 |
if (p>pail && count+(p-1)->freak<-count) /* back up one? */ |
| 114 |
count += (--p)->freak; |
| 115 |
|
| 116 |
io[1].o = o1; /* in case of empty box */ |
| 117 |
for (o=o1, q=pail; o<o2;) { /* dump the pails to reorder colors in box */ |
| 118 |
for (u=q->first; u; u=u->next) *o++ = u->code; |
| 119 |
if (++q==p) io[1].o = o; /* place partition at offset o */ |
| 120 |
} |
| 121 |
io[0].o = o1; |
| 122 |
io[0].freq = (freq>>1)-count; |
| 123 |
io[1].freq = (freq+1>>1)+count; |
| 124 |
/* printf(" at %3d %d=%d+%d\n",io[1].o-off,freq,io[0].freq,io[1].freq); */ |
| 125 |
} |
