View Single Post
 14 April 2011, 03:13 #1 NovaCoder Registered User   Join Date: Sep 2007 Location: Melbourne/Australia Posts: 4,149 Hiya, I've got this code (not mine!) which is used to create an optimized 6 bit (EHB) palette from an 8 bit AGA palette. Although it works ok (and is nice a fast) it could be improved I think. Currently it seems to favour yellow over whites....not sure why? A look at the source code and it seems to give equal weight to all three colors (RGB), where as it should actually favour green. RGB565 uses five bits for the red and blue components, and six bits for the green component. This format reflects the fact that human vision is most sensitive to the green portions of the visible spectrum. If anyone could suggest some quality mapping improvements then I'll be a happy bunny Code: ```#include #include #include #include #define NBITS 4 /* for each r, g, b */ #define NSIDE (1<primaryhist, 0, 3 * NSIDE * sizeof(UWORD)); node->n = 0; for (r = node->box.start[R]; r <= node->box.end[R]; r++) for (g = node->box.start[G]; g <= node->box.end[G]; g++) for (b = node->box.start[b]; b <= node->box.end[b]; b++) { c = hist[r][g][b]; node->primaryhist[R][r] += c; node->primaryhist[G][g] += c; node->primaryhist[b][b] += c; node->n += c; } // (node->n == 0) //I_Error ("Empty box! This should never happen."); /* shrink the box */ for (primary = R; primary <= B; primary++) { i = node->box.start[primary]; while (node->primaryhist[primary][i] == 0) i++; node->box.start[primary] = i; i = node->box.end[primary]; while (node->primaryhist[primary][i] == 0) i--; node->box.end[primary] = i; } /* compute the badness & choose the primary with the greatest badness */ node->badness = 0; for (primary = R; primary <= B; primary++) { wsum = 0; for (i = node->box.start[primary]; i <= node->box.end[primary]; i++) wsum += (node->primaryhist[primary][i] * (ULONG)i); mean = ((wsum << 1) + node->n) / (node->n << 1); /* round(wsum/node->n) */ node->palette[primary] = (UBYTE)(mean << 4); bad = 0; for (i = node->box.start[primary]; i <= node->box.end[primary]; i++) { signed_diff = ((WORD)mean) - ((WORD)(i)); bad += node->primaryhist[primary][i] * (ULONG)(signed_diff * signed_diff); } if (bad >= node->badness) { node->badness = bad; node->long_primary = primary; } } } static void cut (struct node_type *node0, struct node_type *node1) /* cut node0 into 2 pieces in the node0->long_primary direction and store the 2 pieces back into node0 and node1 */ { ULONG sum, goal; UWORD split; //if (node0->badness == 0) // I_Error ("Badness == 0! This should never happen"); /* find the median */ goal = node0->n >> 1; /* how many we want on each side of the cut */ sum = 0; split = node0->box.start[node0->long_primary]; while (sum <= goal) sum += node0->primaryhist[node0->long_primary][split++]; /* go back a bit if necessary to get a better balance */ if ((sum - goal) > (goal - (sum - node0->primaryhist[node0->long_primary][split - 1]))) sum -= node0->primaryhist[node0->long_primary][--split]; /* copy box */ node1->box = node0->box; /* set new dimensions of boxes */ node0->box.end[node0->long_primary] = split - 1; node1->box.start[node0->long_primary] = split; /* update the nodes */ update_entry (node0); update_entry (node1); } static struct node_type node[32]; /* node list */ void median_cut (UBYTE *palette, ULONG *table, UBYTE *xlate) { UWORD idx, this_idx, worst_idx, c, r, g, b, best_idx, max_nodes; WORD dr, dg, db; ULONG max_badness, max_n, dist, best_dist, lr, lg, lb, *l; rgb_type primary; UBYTE *p; max_nodes = 32; /* 32 colours for EHB */ /* build histogram from palette (unlike conventional median split algorithm which uses pixels from image, but that would be too slow) */ memset (hist, 0, NSIDE * NSIDE * NSIDE * sizeof(UWORD)); p = palette; for (c = 0; c < NPALETTE; c++) { r = *p++ >> 4; g = *p++ >> 4; b = *p++ >> 4; p++; // Move the extra bit! if (r < 8 && g < 8 && b < 8) /* EHB if possible */ hist[r << 1][g << 1][b << 1]++; else hist[r][g][b]++; } /* set up an initial box containing the entire colour cube */ for (primary = R; primary <= B; primary++) { node[0].box.start[primary] = 0; node[0].box.end[primary] = NSIDE - 1; } update_entry (&node[0]); /* locate and subdivide the worst box until there are not enough palette entries for more boxes or all the boxes are too small to subdivide further */ for (this_idx = 1; this_idx < max_nodes; this_idx++) { max_badness = 0; max_n = 0; for (idx = 0; idx < this_idx; idx++) if (node[idx].badness > max_badness || (node[idx].badness == max_badness && node[idx].n > max_n)) { max_badness = node[idx].badness; max_n = node[idx].n; worst_idx = idx; } if (max_badness == 0) break; cut (&node[worst_idx], &node[this_idx]); } /* fill the output table */ l = table; for (idx = 0; idx < this_idx; idx++) { lr = node[idx].palette[R]; lr += (lr<<8); lr += (lr<<16); *l++ = lr; lg = node[idx].palette[G]; lg += (lg<<8); lg += (lg<<16); *l++ = lg; lb = node[idx].palette[b]; lb += (lb<<8); lb += (lb<<16); *l++ = lb; } /* calculate pixel translation table */ p = palette; for (c = 0; c < NPALETTE; c++) { r = *p++; g = *p++; b = *p++; p++; // Move the extra bit! best_dist = 32760; for (idx = 0; idx < this_idx; idx++) { dr = ((WORD)r) - (WORD)node[idx].palette[R]; dg = ((WORD)g) - (WORD)node[idx].palette[G]; db = ((WORD)b) - (WORD)node[idx].palette[b]; if ((dist = (dr * dr) + (dg * dg) + (db * db)) < best_dist) { best_dist = dist; best_idx = idx; } dr = ((WORD)r) - (WORD)(node[idx].palette[R] >> 1); dg = ((WORD)g) - (WORD)(node[idx].palette[G] >> 1); db = ((WORD)b) - (WORD)(node[idx].palette[b] >> 1); if ((dist = (dr * dr) + (dg * dg) + (db * db)) < best_dist) { best_dist = dist; best_idx = idx + 32; // EHB colour entry } } xlate[c] = best_idx; } }``` Last edited by TCD; 14 April 2011 at 03:30. Reason: Back to back posts merged. Use the edit function.
Page generated in 0.04442 seconds with 11 queries