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