gfs@abvax.UUCP (Greg F. Shay) (03/14/88)
Relating to the question of how to choose a 256 entry colormap to best represent a 24bit full color image, the algorithm to use was published by Paul Heckbert in the following: "Color image quantization for frame buffer display," SIGGRAPH 1982 Proceedings, pp.297-307. I have this reference through another paper, but do not have a copy of the paper itself. I have posted a request for details from anyone who knows of this. As soon as I find out, I can post my findings. For a rough outline of the algorithm, which is very similiar to clustering algorithms in pattern recognition I think, see my previous posting. If anyone has the above paper, I would appreciate perhaps an address to get a copy. I will be checking the university library later. Greg Shay mandrill | decvax |..!abvax!gfs pyramid |
falk@sun.uucp (Ed Falk) (03/26/88)
In article <221@abvax.UUCP>, gfs@abvax.UUCP (Greg F. Shay) writes: > > Relating to the question of how to choose a 256 entry colormap to best > represent a 24bit full color image, the algorithm to use was published > by Paul Heckbert in the following: > > "Color image quantization for frame buffer display," SIGGRAPH 1982 > Proceedings, pp.297-307. > OK, since everybody else wants to show how they do it, I'll submit my own work. This is my implementation of the median cut algorithm. It does all of the optimizations suggested by Heckbert in his paper. It will dither a 1152x900x24 image in 1.5 minutes. Floyd-Steinberg dithering is available as an option. You can choose the size of your target color-table to be anything you want. This should not be too hard to port to other image formats besides the sun rasterfile format. I have made a couple of improvements over the original algorithm. In this version, the subdivision is always performed based on the largest box rather than arbitrarily dividing them all down. Issues: these are some improvements I've been meaning to make, but haven't gotten around to it: Currently, the largest box is chosen based purely on its volume r*g*b. This should be biased according to perceptual rules. volume = r*.3 + g*.59 + b*.11 this may produce a better image. Also, gamma-correction should be applied on the output, and inversely on the input. Dithering remains a problem. Dithering only works if you have two values to dither between. For instance, if you're dithering a blue field, and you only have one shade of blue in the color table, and the nearest other color is white, then a slightly lighter area of blue will produce blue with undesirable white specs in the middle of it. We need a method of either making sure the color table contains reasonable bracketing or of making sure that the accumulated error in F-S dithering does not go beyond a certain limit. Many images look better *without* dithering, try it both ways. -ed falk, falk@sun ================================== /* quantize stuff: * * median [-csize n] [-fsd] [ifile [ofile]] * * -csize n - set colortable size. Default is 256. * -fsd - use Floyd-Steinberg dithering. * */ #include <stdio.h> #include <sys/types.h> #include <pixrect/pixrect_hs.h> #define MAX_CMAP_SIZE 256 #define COLOR_DEPTH 8 #define MAX_COLOR 256 #define B_DEPTH 5 /* # bits/pixel to use */ #define B_LEN (1<<B_DEPTH) #define C_DEPTH 2 #define C_LEN (1<<C_DEPTH) /* # cells/color to use */ typedef struct colorbox { struct colorbox *next, *prev ; int rmin,rmax, gmin,gmax, bmin,bmax ; int total ; } Colorbox ; typedef struct { int num_ents ; int entries[MAX_CMAP_SIZE][2] ; } C_cell ; static struct rasterfile rh; static colormap_t colormap, ocmap ; static unsigned char rm[MAX_CMAP_SIZE], gm[MAX_CMAP_SIZE], bm[MAX_CMAP_SIZE] ; static int bytes_per_pixel ; static int num_colors ; static int histogram[B_LEN][B_LEN][B_LEN] ; static Colorbox *freeboxes ; static Colorbox *usedboxes ; static Colorbox *largest_box() ; static C_cell **ColorCells ; static char *usage = "usage: median [-csize n] [-fsd] [ifile [ofile]]\n" ; main(argc, argv) int argc; char **argv; { static struct rasterfile outheader ; int i, j ; int dither = 0 ; char *ifile_name = NULL, *ofile_name = NULL ; Colorbox *box_list, *ptr ; num_colors = MAX_CMAP_SIZE ; while(--argc) { ++argv ; if(strcmp(*argv,"-fsd") == 0) dither = 1 ; else if(strcmp(*argv,"-csize") == 0) { if(argc < 2) { fprintf(stderr,"-csize requires 2 arguments, %s",usage) ; exit(1) ; } else { argc -= 1 ; num_colors = atoi(*++argv) ; if(num_colors > MAX_CMAP_SIZE) { fprintf(stderr,"-csize specifies colormap greater than %d\n%s", MAX_CMAP_SIZE,usage) ; exit(1) ; } } } else if(**argv == '-') { fprintf(stderr,"unknown argument '%s'\n%s",*argv,usage) ; exit(1) ; } else if(!ifile_name) { ifile_name = *argv ; } else if(!ofile_name) { ofile_name = *argv ; } else { fprintf(stderr, "Too many file names\n%s",usage) ; exit(1) ; } } if(ifile_name) if (freopen(ifile_name, "r", stdin) == NULL) { fprintf(stderr,"Cannot open input file %s\n%s", ifile_name,usage); exit(1); } if(ofile_name) if (freopen(ofile_name, "w", stdout) == NULL) { fprintf(stderr,"Cannot open output file %s\n%s", ofile_name,usage); exit(1); } if (pr_load_header(stdin, &rh) != 0 || pr_load_colormap(stdin, &rh, &colormap) != 0 ) { fprintf(stderr,"Error reading rasterfile header.\n"); exit(1); } switch( rh.ras_depth ) { case 24: bytes_per_pixel = 3 ; break ; case 32: bytes_per_pixel = 4 ; break ; default: fprintf(stderr, "Image is %d bits deep, median only works with 24 or 32\n"); exit(1) ; } /* * STEP 1: create empty boxes */ usedboxes = NULL ; box_list = freeboxes = (Colorbox *) malloc( num_colors * sizeof(Colorbox) ) ; freeboxes[0].next = &freeboxes[1] ; freeboxes[0].prev = NULL ; for(i=1; i<num_colors-1; ++i) { freeboxes[i].next = &freeboxes[i+1] ; freeboxes[i].prev = &freeboxes[i-1] ; } freeboxes[num_colors-1].next = NULL ; freeboxes[num_colors-1].prev = &freeboxes[num_colors-2] ; /* * STEP 2: get histogram, initialize first box */ ptr = freeboxes ; freeboxes = ptr->next ; if(freeboxes) freeboxes->prev = NULL ; ptr->next = usedboxes ; usedboxes = ptr ; if(ptr->next) ptr->next->prev = ptr ; get_histogram(ptr) ; if( fseek(stdin, 0L, 0) != 0) { fprintf(stderr, "median: input must be from file\n") ; exit(1) ; } /* * STEP 3: continually subdivide boxes until no more free * boxes remain */ while(freeboxes != NULL) { ptr = largest_box() ; splitbox(ptr) ; } /* * STEP 4: assign colors to all boxes */ for(i=0, ptr=usedboxes; i<num_colors; ++i, ptr=ptr->next) assign_color(ptr,&rm[i],&gm[i],&bm[i]) ; /* We're done with the boxes now */ free(box_list) ; box_list = freeboxes = usedboxes = NULL ; /* * STEP 5: scan histogram and map all values to closest color */ /* 5a: create cell list as described in Heckbert[2] */ { register C_cell **ptr ; register int n = C_LEN*C_LEN*C_LEN ; ptr = ColorCells = (C_cell **) malloc(C_LEN*C_LEN*C_LEN * sizeof(C_cell *)); while( n-- > 0 ) *ptr++ = NULL ; } /* 5b: create mapping from truncated pixel space to color table entries */ map_colortable() ; /* * STEP 6: scan image, match input values to table entries */ pr_load_header(stdin, &rh) ; pr_load_colormap(stdin, &rh, &colormap) ; pr_read_init(&rh) ; outheader.ras_magic = RAS_MAGIC ; outheader.ras_width = rh.ras_width ; outheader.ras_height = rh.ras_height ; outheader.ras_depth = COLOR_DEPTH ; outheader.ras_length = ((outheader.ras_width+1) & ~1) * outheader.ras_height ; outheader.ras_type = RT_STANDARD ; outheader.ras_maptype = RMT_EQUAL_RGB ; outheader.ras_maplength = num_colors*3 ; ocmap.type = RMT_EQUAL_RGB ; ocmap.length = num_colors ; ocmap.map[0] = rm ; ocmap.map[1] = gm ; ocmap.map[2] = bm ; pr_dump_header(stdout, &outheader, &ocmap) ; if(dither) quant_fsdither() ; else quant() ; fclose(stdout) ; } static get_histogram(box) register Colorbox *box ; { unsigned char *inline ; register unsigned char *inptr ; int i ; register int j ; pr_read_init(&rh) ; inline = (unsigned char *) alloca( rh.ras_width * bytes_per_pixel ) ; box->rmin = box->gmin = box->bmin = 999 ; box->rmax = box->gmax = box->bmax = -1 ; box->total = rh.ras_height*rh.ras_width ; { register int *ptr = &histogram[0][0][0] ; for(i=B_LEN*B_LEN*B_LEN; --i >= 0;) *ptr++ = 0 ; } for(i=rh.ras_height; --i >= 0;) { pr_get_bytes(stdin, &rh, rh.ras_width * bytes_per_pixel, inline) ; inptr = inline ; for(j=rh.ras_width; --j >= 0;) { register int red,green,blue ; if(rh.ras_depth == 32) ++inptr ; blue = *inptr++ ; green = *inptr++ ; red = *inptr++ ; if (rh.ras_maplength > 0) { red = *(colormap.map[0]+red) ; green = *(colormap.map[1]+green) ; blue = *(colormap.map[2]+blue) ; } red >>= (COLOR_DEPTH-B_DEPTH) ; green >>= (COLOR_DEPTH-B_DEPTH) ; blue >>= (COLOR_DEPTH-B_DEPTH) ; if(red < box->rmin) box->rmin = red ; if(red > box->rmax) box->rmax = red ; if(green < box->gmin) box->gmin = green ; if(green > box->gmax) box->gmax = green ; if(blue < box->bmin) box->bmin = blue ; if(blue > box->bmax) box->bmax = blue ; ++histogram[red][green][blue] ; } } } static Colorbox * largest_box() { register Colorbox *tmp = usedboxes, *ptr ; register int size = -1 ; while(tmp != NULL) { if( (tmp->rmax > tmp->rmin || tmp->gmax > tmp->gmin || tmp->bmax > tmp->bmin) && tmp->total > size ) { ptr = tmp ; size = tmp->total ; } tmp = tmp->next ; } return(ptr) ; } static splitbox(ptr) register Colorbox *ptr ; { int hist2[B_LEN] ; int first, last ; register Colorbox *new ; register int *iptr, *histp ; register int i, j ; enum {RED,GREEN,BLUE} which ; /* * see which axis is the largest, do a histogram along that * axis. Split at median point. Contract both new boxes to * fit points and return */ if( (i = ptr->rmax - ptr->rmin) >= (ptr->gmax - ptr->gmin) && i >= (ptr->bmax - ptr->bmin) ) which = RED ; else if( (ptr->gmax - ptr->gmin) >= (ptr->bmax - ptr->bmin) ) which = GREEN ; else which = BLUE ; /* get histogram along longest axis */ { register int ir,ig,ib ; switch(which) { case RED: histp = &hist2[ptr->rmin] ; for(ir = ptr->rmin; ir <= ptr->rmax; ++ir) { *histp = 0 ; for(ig = ptr->gmin; ig <= ptr->gmax; ++ig) { iptr = &histogram[ir][ig][ptr->bmin] ; for(ib = ptr->bmin; ib <= ptr->bmax; ++ib) { *histp += *iptr ; ++iptr ; } } ++histp ; } first = ptr->rmin; last = ptr->rmax ; break ; case GREEN: histp = &hist2[ptr->gmin] ; for(ig = ptr->gmin; ig <= ptr->gmax; ++ig) { *histp = 0 ; for(ir = ptr->rmin; ir <= ptr->rmax; ++ir) { iptr = &histogram[ir][ig][ptr->bmin] ; for(ib = ptr->bmin; ib <= ptr->bmax; ++ib) { *histp += *iptr ; ++iptr ; } } ++histp ; } first = ptr->gmin; last = ptr->gmax ; break ; case BLUE: histp = &hist2[ptr->bmin] ; for(ib = ptr->bmin; ib <= ptr->bmax; ++ib) { *histp = 0 ; for(ir = ptr->rmin; ir <= ptr->rmax; ++ir) { iptr = &histogram[ir][ptr->gmin][ib] ; for(ig = ptr->gmin; ig <= ptr->gmax; ++ig) { *histp += *iptr ; iptr += B_LEN ; } } ++histp ; } first = ptr->bmin; last = ptr->bmax ; break ; } } /* find median point */ { register int sum, sum2 ; histp = &hist2[first] ; sum2 = ptr->total/2 ; histp = &hist2[first] ; sum = 0 ; for( i=first; i<=last && (sum += *histp++) < sum2; ++i) ; if( i == first ) ++i ; } /* Create new box, re-allocate points */ new = freeboxes ; freeboxes = new->next ; if(freeboxes) freeboxes->prev = NULL ; if(usedboxes) usedboxes->prev = new ; new->next = usedboxes ; usedboxes = new ; { register int sum1,sum2,j ; int total ; total = ptr->total ; histp = &hist2[first] ; sum1 = 0 ; for( j = first; j < i; ++j) sum1 += *histp++ ; sum2 = 0 ; for( j = i; j <= last; ++j) sum2 += *histp++ ; #ifdef DEBUG if( sum1+sum2 != total || sum1 == 0 || sum2 == 0 ) fprintf(stderr, "??? splitbox: sum1=%d, sum2=%d, total=%d\n", sum1,sum2,total) ; #endif DEBUG new->total = sum1 ; ptr->total = sum2 ; } new->rmin = ptr->rmin ; new->rmax = ptr->rmax ; new->gmin = ptr->gmin ; new->gmax = ptr->gmax ; new->bmin = ptr->bmin ; new->bmax = ptr->bmax ; switch(which) { case RED: new->rmax = i-1 ; ptr->rmin = i ; break ; case GREEN: new->gmax = i-1 ; ptr->gmin = i ; break ; case BLUE: new->bmax = i-1 ; ptr->bmin = i ; break ; } shrinkbox(new) ; shrinkbox(ptr) ; } static shrinkbox(box) register Colorbox *box ; { register int *histp ; register int ir,ig,ib ; if(box->rmax > box->rmin) { for(ir = box->rmin; ir <= box->rmax; ++ir) for(ig = box->gmin; ig <= box->gmax; ++ig) { histp = &histogram[ir][ig][box->bmin] ; for(ib = box->bmin; ib <= box->bmax; ++ib) if( *histp++ != 0 ) { box->rmin = ir ; goto have_rmin ; } } have_rmin: if(box->rmax > box->rmin) for(ir = box->rmax; ir >= box->rmin; --ir) for(ig = box->gmin; ig <= box->gmax; ++ig) { histp = &histogram[ir][ig][box->bmin] ; for(ib = box->bmin; ib <= box->bmax; ++ib) if( *histp++ != 0 ) { box->rmax = ir ; goto have_rmax ; } } } have_rmax: if( box->gmax > box->gmin ) { for(ig = box->gmin; ig <= box->gmax; ++ig) for(ir = box->rmin; ir <= box->rmax; ++ir) { histp = &histogram[ir][ig][box->bmin] ; for(ib = box->bmin; ib <= box->bmax; ++ib) if( *histp++ != 0 ) { box->gmin = ig ; goto have_gmin ; } } have_gmin: if( box->gmax > box->gmin ) for(ig = box->gmax; ig >= box->gmin; --ig) for(ir = box->rmin; ir <= box->rmax; ++ir) { histp = &histogram[ir][ig][box->bmin] ; for(ib = box->bmin; ib <= box->bmax; ++ib) if( *histp++ != 0 ) { box->gmax = ig ; goto have_gmax ; } } } have_gmax: if( box->bmax > box->bmin ) { for(ib = box->bmin; ib <= box->bmax; ++ib) for(ir = box->rmin; ir <= box->rmax; ++ir) { histp = &histogram[ir][box->gmin][ib] ; for(ig = box->gmin; ig <= box->gmax; ++ig) { if( *histp != 0 ) { box->bmin = ib ; goto have_bmin ; } histp += B_LEN ; } } have_bmin: if( box->bmax > box->bmin ) for(ib = box->bmax; ib >= box->bmin; --ib) for(ir = box->rmin; ir <= box->rmax; ++ir) { histp = &histogram[ir][box->gmin][ib] ; for(ig = box->gmin; ig <= box->gmax; ++ig) { if( *histp != 0 ) { box->bmax = ib ; goto have_bmax ; } histp += B_LEN ; } } } have_bmax: return ; } static assign_color(ptr,rp,gp,bp) register Colorbox *ptr ; unsigned char *rp,*gp,*bp ; { register int *histp ; register int ir,ig,ib ; register long red = 0, green = 0, blue = 0 ; *rp = ((ptr->rmin + ptr->rmax) << (COLOR_DEPTH - B_DEPTH)) / 2 ; *gp = ((ptr->gmin + ptr->gmax) << (COLOR_DEPTH - B_DEPTH)) / 2 ; *bp = ((ptr->bmin + ptr->bmax) << (COLOR_DEPTH - B_DEPTH)) / 2 ; #ifdef COMMENT #ifdef DEBUG if( ptr->total <= 0 ) { fprintf(stderr,"??? assign_color: total = %d\n",ptr->total) ; return ; } #endif DEBUG for( ir = ptr->rmin; ir <= ptr->rmax; ++ir) for( ig = ptr->gmin; ig <= ptr->gmax; ++ig) { histp = &histogram[ir][ig][ptr->bmin] ; for( ib = ptr->bmin; ib <= ptr->bmax; ++ib) { if( *histp != 0 ) { red += ir * *histp ; green += ig * *histp ; blue += ib * *histp ; } ++histp ; } } *rp = (red << (COLOR_DEPTH - B_DEPTH)) / ptr->total ; *gp = (green << (COLOR_DEPTH - B_DEPTH)) / ptr->total ; *bp = (blue << (COLOR_DEPTH - B_DEPTH)) / ptr->total ; #endif COMMENT } static C_cell * create_colorcell(red,green,blue) int red,green,blue ; { register int ir,ig,ib, i ; int mindist ; register C_cell *ptr ; ir = red >> (COLOR_DEPTH-C_DEPTH) ; ig = green >> (COLOR_DEPTH-C_DEPTH) ; ib = blue >> (COLOR_DEPTH-C_DEPTH) ; red &= ~1 << (COLOR_DEPTH-C_DEPTH) ; green &= ~1 << (COLOR_DEPTH-C_DEPTH) ; blue &= ~1 << (COLOR_DEPTH-C_DEPTH) ; ptr = (C_cell *) malloc( sizeof(C_cell) ) ; *( ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib ) = ptr ; ptr->num_ents = 0 ; /* step 1: find all colors inside this cell, while we're at it, find distance of centermost point to furthest corner */ mindist = 99999999 ; for(i=0; i<num_colors; ++i) if( rm[i]>>(COLOR_DEPTH-C_DEPTH) == ir && gm[i]>>(COLOR_DEPTH-C_DEPTH) == ig && bm[i]>>(COLOR_DEPTH-C_DEPTH) == ib) { register int tmp, dist ; ptr->entries[ptr->num_ents][0] = i ; ptr->entries[ptr->num_ents][1] = 0 ; ++ptr->num_ents ; tmp = rm[i] - red ; if( tmp < (MAX_COLOR/C_LEN/2) ) tmp = MAX_COLOR/C_LEN-1 - tmp ; dist = tmp*tmp ; tmp = gm[i] - green ; if( tmp < (MAX_COLOR/C_LEN/2) ) tmp = MAX_COLOR/C_LEN-1 - tmp ; dist += tmp*tmp ; tmp = bm[i] - blue ; if( tmp < (MAX_COLOR/C_LEN/2) ) tmp = MAX_COLOR/C_LEN-1 - tmp ; dist += tmp*tmp ; if( dist < mindist ) mindist = dist ; } /* step 3: find all points within that distance to box */ for( i=0; i<num_colors; ++i ) { register int dist, tmp ; if( rm[i] >> (COLOR_DEPTH-C_DEPTH) != ir || gm[i] >> (COLOR_DEPTH-C_DEPTH) != ig || bm[i] >> (COLOR_DEPTH-C_DEPTH) != ib) { dist = 0 ; if( (tmp = red - rm[i]) > 0 || (tmp = rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) dist += tmp*tmp ; if( (tmp = green - gm[i]) > 0 || (tmp = gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) dist += tmp*tmp ; if( (tmp = blue - bm[i]) > 0 || (tmp = bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 ) dist += tmp*tmp ; if( dist < mindist ) { ptr->entries[ptr->num_ents][0] = i ; ptr->entries[ptr->num_ents][1] = dist ; ++ptr->num_ents ; } } } /* sort color cells by distance, use cheap exchange sort */ { register int n, tmp, i ; int next_n ; n = ptr->num_ents - 1 ; while( n > 0 ) { next_n = 0 ; for( i=0; i<n; ++i) { if( ptr->entries[i][1] > ptr->entries[i+1][1] ) { tmp = ptr->entries[i][0] ; ptr->entries[i][0] = ptr->entries[i+1][0] ; ptr->entries[i+1][0] = tmp ; tmp = ptr->entries[i][1] ; ptr->entries[i][1] = ptr->entries[i+1][1] ; ptr->entries[i+1][1] = tmp ; next_n = i ; } } n = next_n ; } } return( ptr ) ; } static map_colortable() { int ir,ig,ib ; register int *histp = &histogram[0][0][0] ; register C_cell *cell ; for(ir = 0; ir < B_LEN; ++ir) for(ig = 0; ig < B_LEN; ++ig) for(ib = 0; ib < B_LEN; ++ib) { if( *histp == 0 ) *histp = -1 ; else { int i ; register int j, tmp, d2, dist ; cell = *( ColorCells + ( ((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) + ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH ) + (ib>>(B_DEPTH-C_DEPTH)) ) ) ; if(cell == NULL ) cell = create_colorcell( ir<<(COLOR_DEPTH-B_DEPTH), ig<<(COLOR_DEPTH-B_DEPTH), ib<<(COLOR_DEPTH-B_DEPTH) ) ; dist = 9999999 ; for(i = 0; i < cell->num_ents && dist > cell->entries[i][1] ; ++i) { j = cell->entries[i][0] ; d2 = rm[j] - (ir << (COLOR_DEPTH-B_DEPTH)) ; d2 *= d2 ; tmp = gm[j] - (ig << (COLOR_DEPTH-B_DEPTH)) ; d2 += tmp*tmp ; tmp = bm[j] - (ib << (COLOR_DEPTH-B_DEPTH)) ; d2 += tmp*tmp ; if( d2 < dist ) { dist = d2 ; *histp = j ; } } #ifdef DEBUG if( dist == 9999999 ) fprintf(stderr,"??? map_colortable: dist=9999999\n") ; #endif DEBUG } ++histp ; } } /* * straight quantization. Each pixel is mapped to the colors * closest to it. Color values are rounded to the nearest color * table entry. */ static quant() { unsigned char *outline ; unsigned char *inline ; register unsigned char *outptr ; register unsigned char *inptr ; register int i, j ; inline = (unsigned char *) alloca( rh.ras_width * bytes_per_pixel ) ; outline = (unsigned char *) alloca( rh.ras_width ) ; for(i=0; i < rh.ras_height; ++i) { pr_get_bytes(stdin, &rh, rh.ras_width * bytes_per_pixel, inline) ; inptr = inline ; outptr = outline; for(j=0; j < rh.ras_width; ++j) { register int tmp,red,green,blue ; if(rh.ras_depth == 32) ++inptr ; blue = *inptr++ ; green = *inptr++ ; red = *inptr++ ; if (rh.ras_maplength > 0) { red = *(colormap.map[0]+red) ; green = *(colormap.map[1]+green) ; blue = *(colormap.map[2]+blue) ; } red >>= (COLOR_DEPTH-B_DEPTH) ; green >>= (COLOR_DEPTH-B_DEPTH) ; blue >>= (COLOR_DEPTH-B_DEPTH) ; *outptr++ = histogram[red][green][blue] ; } fwrite(outline, 1, rh.ras_width, stdout) ; } } static quant_fsdither() { unsigned char *outline, *inline ; short *thisline, *nextline, *tmpptr ; unsigned char *inptr ; register unsigned char *outptr ; register short *thisptr, *nextptr ; register int i, j ; int imax, jmax ; int lastline, lastpixel ; imax = rh.ras_height - 1 ; jmax = rh.ras_width - 1 ; inline = (unsigned char *) alloca( rh.ras_width * bytes_per_pixel ) ; thisline = (short *) alloca( rh.ras_width * 3 * sizeof(short)) ; nextline = (short *) alloca( rh.ras_width * 3 * sizeof(short)) ; outline = (unsigned char *) alloca( rh.ras_width ) ; /* * get first line */ pr_get_bytes(stdin, &rh, rh.ras_width * bytes_per_pixel, inline) ; { register int tmp ; inptr = inline ; nextptr = nextline ; for(j=0; j < rh.ras_width; ++j) { if(rh.ras_depth == 32) ++inptr ; if( rh.ras_maplength > 0) { *nextptr++ = *(colormap.map[0]+*inptr++) ; *nextptr++ = *(colormap.map[1]+*inptr++) ; *nextptr++ = *(colormap.map[2]+*inptr++) ; } else { *nextptr++ = *inptr++ ; *nextptr++ = *inptr++ ; *nextptr++ = *inptr++ ; } } } for(i=0; i < rh.ras_height; ++i) { tmpptr = thisline ; thisline = nextline ; nextline = tmpptr ; lastline = (i == imax) ; pr_get_bytes(stdin, &rh, rh.ras_width * bytes_per_pixel, inline) ; { register int tmp ; inptr = inline ; nextptr = nextline ; for(j=0; j < rh.ras_width; ++j) { if(rh.ras_depth == 32) ++inptr ; if( rh.ras_maplength > 0) { *nextptr++ = *(colormap.map[0]+*inptr++) ; *nextptr++ = *(colormap.map[1]+*inptr++) ; *nextptr++ = *(colormap.map[2]+*inptr++) ; } else { *nextptr++ = *inptr++ ; *nextptr++ = *inptr++ ; *nextptr++ = *inptr++ ; } } } thisptr = thisline ; nextptr = nextline ; outptr = outline; for(j=0; j < rh.ras_width ; ++j) { int red,green,blue ; register int oval, r2,g2,b2 ; lastpixel = (j == jmax) ; b2 = *thisptr++ ; g2 = *thisptr++ ; r2 = *thisptr++ ; if( r2 < 0 ) r2 = 0 ; else if( r2 >= MAX_COLOR ) r2 = MAX_COLOR-1 ; if( g2 < 0 ) g2 = 0 ; else if( g2 >= MAX_COLOR ) g2 = MAX_COLOR-1 ; if( b2 < 0 ) b2 = 0 ; else if( b2 >= MAX_COLOR ) b2 = MAX_COLOR-1 ; red = r2 ; green = g2 ; blue = b2 ; r2 >>= (COLOR_DEPTH-B_DEPTH) ; g2 >>= (COLOR_DEPTH-B_DEPTH) ; b2 >>= (COLOR_DEPTH-B_DEPTH) ; if( (oval = histogram[r2][g2][b2]) == -1) { int ci ; register int cj, tmp, d2, dist ; register C_cell *cell ; cell = *( ColorCells + ( ((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) + ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH ) + (b2>>(B_DEPTH-C_DEPTH)) ) ) ; if(cell == NULL ) cell = create_colorcell( red, green, blue ) ; dist = 9999999 ; for(ci = 0; ci < cell->num_ents && dist > cell->entries[ci][1] ; ++ci) { cj = cell->entries[ci][0] ; d2 = (rm[cj] >> (COLOR_DEPTH-B_DEPTH)) - r2 ; d2 *= d2 ; tmp = (gm[cj] >> (COLOR_DEPTH-B_DEPTH)) - g2 ; d2 += tmp*tmp ; tmp = (bm[cj] >> (COLOR_DEPTH-B_DEPTH)) - b2 ; d2 += tmp*tmp ; if( d2 < dist ) { dist = d2 ; oval = cj ; } } histogram[r2][g2][b2] = oval ; #ifdef DEBUG if( dist == 9999999 ) fprintf(stderr,"??? quant: dist=9999999\n") ; #endif DEBUG } *outptr++ = oval ; red -= rm[oval] ; green -= gm[oval] ; blue -= bm[oval] ; if( !lastpixel ) { thisptr[0] += blue * 7 / 16 ; thisptr[1] += green * 7 / 16 ; thisptr[2] += red * 7 / 16 ; } if( !lastline ) { if( j != 0 ) { nextptr[-3] += blue * 3 / 16 ; nextptr[-2] += green * 3 / 16 ; nextptr[-1] += red * 3 / 16 ; } nextptr[0] += blue * 5 / 16 ; nextptr[1] += green * 5 / 16 ; nextptr[2] += red * 5 / 16 ; if( !lastpixel ) { nextptr[3] += blue / 16 ; nextptr[4] += green / 16 ; nextptr[5] += red / 16 ; } nextptr += 3 ; } } fwrite(outline, 1, rh.ras_width, stdout) ; } } #ifdef DEBUG showboxes() { Colorbox *ptr ; printf("boxes:\n") ; ptr = usedboxes ; while(ptr != NULL) { printf(" %d<r<%d, %d<g<%d, %d<b<%d\n", ptr->rmin,ptr->rmax, ptr->gmin,ptr->gmax, ptr->bmin,ptr->bmax) ; ptr = ptr->next ; } } showcell(ptr) register C_cell *ptr ; { int i ; int j ; fprintf(stderr, "n=%d\n", ptr->num_ents) ; for(i=0; i<ptr->num_ents; ++i) { j = ptr->entries[i][0] ; fprintf(stderr, "(%d,%d): (%d,%d,%d)\n", j, ptr->entries[i][1], rm[j],gm[j],bm[j]) ; } } int testbox(box) register Colorbox *box ; { register int ir,ig,ib, total ; total = 0 ; for(ir=box->rmin; ir<=box->rmax; ++ir) for(ig=box->gmin; ig<=box->gmax; ++ig) for(ib=box->bmin; ib<=box->bmax; ++ib) total += histogram[ir][ig][ib] ; return total ; } #endif DEBUG /* pr_stream routines: allow images to be read in stream * fasion rather than loading them into memory. * * These routines are used in conjunction with the pr_io routines. It * is the application's responsibility to read the header and * colormaps * * * routines: * * pr_read_init(header) * struct rasterfile *header ; * * sets up to read an image * * * pr_get_bytes(file, header, len, buffer) * FILE *file ; * struct rasterfile *header ; * int len ; * char *buffer ; * * read data from input * * * int * pr_get_byte(file, header) * FILE *file ; * struct rasterfile *header ; * * read and return one byte from input * */ #include <stdio.h> #include <sys/types.h> #include <pixrect/pixrect.h> #include <pixrect/memvar.h> #include <pixrect/pr_io.h> #include <rasterfile.h> #define ESCAPE 128 static unsigned char icvalue ; static int icount ; int pr_read_init(header) struct rasterfile *header ; { icount = 0 ; } int pr_get_bytes(file, header, len, buffer) register FILE *file ; register struct rasterfile *header ; register int len ; register unsigned char *buffer ; { if(header->ras_type != RT_BYTE_ENCODED) return( fread(buffer, 1, len, file) ) ; else while(len-- > 0) { if(icount > 0) { --icount ; *buffer++ = icvalue ; } else { if( (icvalue = getc(file)) != ESCAPE ) *buffer++ = icvalue ; else { if( (icount = getc(file)) == 0 ) *buffer++ = ESCAPE ; else { *buffer++ = icvalue = getc(file) ; } } } } return 0 ; } unsigned char pr_get_byte(file, header) FILE *file ; struct rasterfile *header ; { unsigned char rval ; pr_get_bytes(file, header, 1, &rval) ; return( rval ) ; } -- -ed falk, sun microsystems sun!falk, falk@sun.com terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.