Mercurial > hg > xemacs-beta
diff src/imgproc.c @ 269:b2472a1930f2 r20-5b33
Import from CVS: tag r20-5b33
author | cvs |
---|---|
date | Mon, 13 Aug 2007 10:27:19 +0200 |
parents | 966663fcf606 |
children | c5d627a313b1 |
line wrap: on
line diff
--- a/src/imgproc.c Mon Aug 13 10:26:31 2007 +0200 +++ b/src/imgproc.c Mon Aug 13 10:27:19 2007 +0200 @@ -44,8 +44,9 @@ #include "lisp.h" #include "imgproc.h" -static void get_histogram(quant_table *qt, unsigned char *pic, - int width, int height, Colorbox* box) +static void +get_histogram(quant_table *qt, unsigned char *pic, + int width, int height, Colorbox* box) { register unsigned char *inptr; register int red, green, blue; @@ -55,32 +56,29 @@ box->rmax = box->gmax = box->bmax = -1; box->total = width * height; - { - register int *ptr = &(qt->histogram[0][0][0]); - for (i = B_LEN*B_LEN*B_LEN; i-- > 0;) - *ptr++ = 0; - } inptr = pic; - for (i = 0; i < height; i++) { - for (j = width; j-- > 0;) { - red = *inptr++ >> COLOR_SHIFT; - green = *inptr++ >> COLOR_SHIFT; - blue = *inptr++ >> COLOR_SHIFT; - 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; - qt->histogram[red][green][blue]++; + for (i = 0; i < height; i++) + { + for (j = width; j-- > 0;) + { + red = *inptr++ >> COLOR_SHIFT; + green = *inptr++ >> COLOR_SHIFT; + blue = *inptr++ >> COLOR_SHIFT; + 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; + qt->histogram[red][green][blue]++; + } } - } } static Colorbox * @@ -103,81 +101,98 @@ { register int *histp, 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 = &(qt->histogram[ir][ig][box->bmin]); - for (ib = box->bmin; ib <= box->bmax; ++ib) - if (*histp++ != 0) { - box->rmin = ir; - goto have_rmin; + if (box->rmax > box->rmin) + { + for (ir = box->rmin; ir <= box->rmax; ++ir) + for (ig = box->gmin; ig <= box->gmax; ++ig) + { + histp = &(qt->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 = &(qt->histogram[ir][ig][box->bmin]); - ib = box->bmin; - for (; ib <= box->bmax; ++ib) - if (*histp++ != 0) { - box->rmax = ir; - goto have_rmax; + have_rmin: + if (box->rmax > box->rmin) + for (ir = box->rmax; ir >= box->rmin; --ir) + for (ig = box->gmin; ig <= box->gmax; ++ig) + { + histp = &(qt->histogram[ir][ig][box->bmin]); + ib = box->bmin; + for (; 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 = &(qt->histogram[ir][ig][box->bmin]); - for (ib = box->bmin; ib <= box->bmax; ++ib) - if (*histp++ != 0) { - box->gmin = ig; - goto have_gmin; + if (box->gmax > box->gmin) + { + for (ig = box->gmin; ig <= box->gmax; ++ig) + for (ir = box->rmin; ir <= box->rmax; ++ir) + { + histp = &(qt->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 = &(qt->histogram[ir][ig][box->bmin]); - ib = box->bmin; - for (; ib <= box->bmax; ++ib) - if (*histp++ != 0) { - box->gmax = ig; - goto have_gmax; + have_gmin: + if (box->gmax > box->gmin) + for (ig = box->gmax; ig >= box->gmin; --ig) + for (ir = box->rmin; ir <= box->rmax; ++ir) + { + histp = &(qt->histogram[ir][ig][box->bmin]); + ib = box->bmin; + for (; 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 = &(qt->histogram[ir][box->gmin][ib]); - for (ig = box->gmin; ig <= box->gmax; ++ig) { - if (*histp != 0) { - box->bmin = ib; - goto have_bmin; + if (box->bmax > box->bmin) + { + for (ib = box->bmin; ib <= box->bmax; ++ib) + for (ir = box->rmin; ir <= box->rmax; ++ir) + { + histp = &(qt->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; + } } - 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 = &(qt->histogram[ir][box->gmin][ib]); - ig = box->gmin; - for (; ig <= box->gmax; ++ig) { - if (*histp != 0) { - box->bmax = ib; - goto have_bmax; + have_bmin: + if (box->bmax > box->bmin) + for (ib = box->bmax; ib >= box->bmin; --ib) + for (ir = box->rmin; ir <= box->rmax; ++ir) + { + histp = &(qt->histogram[ir][box->gmin][ib]); + ig = box->gmin; + for (; ig <= box->gmax; ++ig) + { + if (*histp != 0) + { + box->bmax = ib; + goto have_bmax; + } + histp += B_LEN; + } } - histp += B_LEN; - } - } - } + } have_bmax: ; } @@ -207,52 +222,60 @@ else axis = BLUE; /* get histogram along longest axis */ - switch (axis) { - 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 = &(qt->histogram[ir][ig][ptr->bmin]); - for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) - *histp += *iptr++; - } - histp++; + switch (axis) + { + 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 = &(qt->histogram[ir][ig][ptr->bmin]); + for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) + *histp += *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 = &(qt->histogram[ir][ig][ptr->bmin]); + for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) + *histp += *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 = &(qt->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; } - 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 = &(qt->histogram[ir][ig][ptr->bmin]); - for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) - *histp += *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 = &(qt->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 */ sum2 = ptr->total / 2; histp = &hist2[first]; @@ -286,22 +309,23 @@ new->gmax = ptr->gmax; new->bmin = ptr->bmin; new->bmax = ptr->bmax; - switch (axis) { - 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(qt, new); - shrinkbox(qt, ptr); + switch (axis) + { + 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 (qt, new); + shrinkbox (qt, ptr); } @@ -325,71 +349,76 @@ * it, find distance of centermost point to furthest corner */ mindist = 99999999; - for (i = 0; i < num_colors; ++i) { - if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir || - qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig || - qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib) - continue; - ptr->entries[ptr->num_ents][0] = i; - ptr->entries[ptr->num_ents][1] = 0; - ++ptr->num_ents; - tmp = qt->rm[i] - red; - if (tmp < (MAX_COLOR/C_LEN/2)) - tmp = MAX_COLOR/C_LEN-1 - tmp; - dist = tmp*tmp; - tmp = qt->gm[i] - green; - if (tmp < (MAX_COLOR/C_LEN/2)) - tmp = MAX_COLOR/C_LEN-1 - tmp; - dist += tmp*tmp; - tmp = qt->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; - } + for (i = 0; i < num_colors; ++i) + { + if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir || + qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig || + qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib) + continue; + ptr->entries[ptr->num_ents][0] = i; + ptr->entries[ptr->num_ents][1] = 0; + ++ptr->num_ents; + tmp = qt->rm[i] - red; + if (tmp < (MAX_COLOR/C_LEN/2)) + tmp = MAX_COLOR/C_LEN-1 - tmp; + dist = tmp*tmp; + tmp = qt->gm[i] - green; + if (tmp < (MAX_COLOR/C_LEN/2)) + tmp = MAX_COLOR/C_LEN-1 - tmp; + dist += tmp*tmp; + tmp = qt->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 cell. */ - for (i = 0; i < num_colors; ++i) { - if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir && - qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig && - qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib) - continue; - dist = 0; - if ((tmp = red - qt->rm[i]) > 0 || - (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) - dist += tmp*tmp; - if ((tmp = green - qt->gm[i]) > 0 || - (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) - dist += tmp*tmp; - if ((tmp = blue - qt->bm[i]) > 0 || - (tmp = qt->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; + for (i = 0; i < num_colors; ++i) + { + if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir && + qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig && + qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib) + continue; + dist = 0; + if ((tmp = red - qt->rm[i]) > 0 || + (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 ) + dist += tmp*tmp; + if ((tmp = green - qt->gm[i]) > 0 || + (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 ) + dist += tmp*tmp; + if ((tmp = blue - qt->bm[i]) > 0 || + (tmp = qt->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 */ - for (n = ptr->num_ents - 1; n > 0; n = next_n) { - 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; - } - } + for (n = ptr->num_ents - 1; n > 0; n = next_n) + { + 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; + } + } return (ptr); } @@ -403,48 +432,53 @@ for (ir = 0; ir < B_LEN; ++ir) for (ig = 0; ig < B_LEN; ++ig) - for (ib = 0; ib < B_LEN; ++ib, histp++) { - if (*histp == 0) { - *histp = -1; - continue; + for (ib = 0; ib < B_LEN; ++ib, histp++) + { + if (*histp == 0) + { + *histp = -1; + continue; + } + cell = *(qt->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 (qt, num_colors, + ir << COLOR_SHIFT, + ig << COLOR_SHIFT, + ib << COLOR_SHIFT); + if (cell == NULL) /* memory exhausted! punt! */ + return -1; + dist = 9999999; + for (i = 0; i < cell->num_ents && + dist > cell->entries[i][1]; ++i) + { + j = cell->entries[i][0]; + d2 = qt->rm[j] - (ir << COLOR_SHIFT); + d2 *= d2; + tmp = qt->gm[j] - (ig << COLOR_SHIFT); + d2 += tmp*tmp; + tmp = qt->bm[j] - (ib << COLOR_SHIFT); + d2 += tmp*tmp; + if (d2 < dist) + { + dist = d2; + *histp = j; + } + } } - cell = *(qt->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(qt, num_colors, - ir << COLOR_SHIFT, - ig << COLOR_SHIFT, - ib << COLOR_SHIFT); - if (cell == NULL) /* memory exhausted! punt! */ - return -1; - dist = 9999999; - for (i = 0; i < cell->num_ents && - dist > cell->entries[i][1]; ++i) { - j = cell->entries[i][0]; - d2 = qt->rm[j] - (ir << COLOR_SHIFT); - d2 *= d2; - tmp = qt->gm[j] - (ig << COLOR_SHIFT); - d2 += tmp*tmp; - tmp = qt->bm[j] - (ib << COLOR_SHIFT); - d2 += tmp*tmp; - if (d2 < dist) { - dist = d2; - *histp = j; - } - } - } return 0; } -quant_table *EImage_build_quantable(unsigned char *eimage, int width, int height, int num_colors) +quant_table * +build_EImage_quantable(unsigned char *eimage, int width, int height, int num_colors) { quant_table *qt; Colorbox *box_list, *ptr; int i,res; - qt = (quant_table*)xmalloc(sizeof(quant_table)); + qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table)); if (qt == NULL) return NULL; assert (num_colors < 257 && num_colors > 2); @@ -452,13 +486,14 @@ * STEP 1: create empty boxes */ qt->usedboxes = NULL; - box_list = qt->freeboxes = (Colorbox *)xmalloc(num_colors*sizeof (Colorbox)); + box_list = qt->freeboxes = (Colorbox *)xmalloc (num_colors*sizeof (Colorbox)); qt->freeboxes[0].next = &(qt->freeboxes[1]); qt->freeboxes[0].prev = NULL; - for (i = 1; i < num_colors-1; ++i) { - qt->freeboxes[i].next = &(qt->freeboxes[i+1]); - qt->freeboxes[i].prev = &(qt->freeboxes[i-1]); - } + for (i = 1; i < num_colors-1; ++i) + { + qt->freeboxes[i].next = &(qt->freeboxes[i+1]); + qt->freeboxes[i].prev = &(qt->freeboxes[i-1]); + } qt->freeboxes[num_colors-1].next = NULL; qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]); @@ -473,54 +508,57 @@ qt->usedboxes = ptr; if (ptr->next) ptr->next->prev = ptr; - get_histogram(qt, eimage, width, height, ptr); + get_histogram (qt, eimage, width, height, ptr); /* * STEP 3: continually subdivide boxes until no more free * boxes remain or until all colors assigned. */ - while (qt->freeboxes != NULL) { - ptr = largest_box(qt); - if (ptr != NULL) - splitbox(qt, ptr); - else - qt->freeboxes = NULL; - } + while (qt->freeboxes != NULL) + { + ptr = largest_box(qt); + if (ptr != NULL) + splitbox (qt, ptr); + else + qt->freeboxes = NULL; + } /* * STEP 4: assign colors to all boxes */ - for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) { - qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2; - qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2; - qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2; - qt->um[i] = ptr->total; - } + for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) + { + qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2; + qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2; + qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2; + qt->um[i] = ptr->total; + } qt->num_active_colors = i; /* We're done with the boxes now */ - xfree(box_list); + xfree (box_list); qt->freeboxes = qt->usedboxes = NULL; /* * STEP 5: scan histogram and map all values to closest color */ /* 5a: create cell list as described in Heckbert */ - qt->ColorCells = (C_cell **)xmalloc(C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); - memset(qt->ColorCells, 0, C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); + qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*)); /* 5b: create mapping from truncated pixel space to color table entries */ - res = map_colortable(qt, num_colors); + res = map_colortable (qt, num_colors); /* 5c: done with ColorCells */ - for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) if (qt->ColorCells[i]) xfree(qt->ColorCells[i]); - xfree(qt->ColorCells); + for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) + if (qt->ColorCells[i]) xfree (qt->ColorCells[i]); + xfree (qt->ColorCells); - if (res) { - /* we failed in memory allocation, so clean up an leave */ - xfree(qt); - return NULL; - } + if (res) + { + /* we failed in memory allocation, so clean up an leave */ + xfree(qt); + return NULL; + } return qt; }