+++ /dev/null
-#include <stdio.h>
-#include <stdlib.h>
-#include "medcut.h"
-
-#define RED 0
-#define GREEN 1
-#define BLUE 2
-
-#define FindHash(red, green, blue, h_ptr) \
- h_ptr = Hash[((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256]; \
- while(h_ptr != NULL) \
- { \
- if ((h_ptr->pixel[RED] == red)&& \
- (h_ptr->pixel[GREEN] == green)&& \
- (h_ptr->pixel[BLUE] == blue)) \
- { \
- break; \
- } \
- h_ptr = h_ptr->hash_next; \
- }
-
-struct color_rec {
- int pixel[3];
- int box_num;
- struct color_rec *hash_next;
- struct color_rec *next;
-} *Hash[256];
-struct c_box_rec {
- int min_pix[3];
- int max_pix[3];
- int count;
- struct color_rec *c_data;
-} C_boxes[256];
-
-int BoxCount;
-struct color_rec *hash_ptr;
-struct color_rec *tptr;
-static int Width, Height;
-int ColorCnt;
-int NCells;
-struct color_rec *Tptr;
-
-
-void
-InitMinMax(boxnum)
-int boxnum;
-{
- C_boxes[boxnum].min_pix[RED] = 256;
- C_boxes[boxnum].max_pix[RED] = 0;
- C_boxes[boxnum].min_pix[GREEN] = 256;
- C_boxes[boxnum].max_pix[GREEN] = 0;
- C_boxes[boxnum].min_pix[BLUE] = 256;
- C_boxes[boxnum].max_pix[BLUE] = 0;
-}
-
-
-struct color_rec *
-AddHash(red, green, blue)
-int red, green, blue;
-{
- int lum;
-
- lum = ((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256;;
- hash_ptr = (struct color_rec *) malloc(sizeof(struct color_rec));
- if (hash_ptr == NULL) {
- fprintf(stderr, "Cannot malloc %dth color\n", ColorCnt);
- exit(1);
- }
- hash_ptr->pixel[RED] = red;
- hash_ptr->pixel[GREEN] = green;
- hash_ptr->pixel[BLUE] = blue;
- hash_ptr->box_num = 0;
- hash_ptr->next = NULL;
- hash_ptr->hash_next = Hash[lum];
- Hash[lum] = hash_ptr;
- return (hash_ptr);
-}
-
-
-void
-AddColor(cptr, boxnum)
-struct color_rec *cptr;
-int boxnum;
-{
- struct color_rec *ptr;
-
- while (cptr != NULL) {
- ptr = cptr;
- cptr = cptr->next;
- ptr->box_num = boxnum;
- ptr->next = C_boxes[boxnum].c_data;
- C_boxes[boxnum].c_data = ptr;
- if (ptr->pixel[RED] < C_boxes[boxnum].min_pix[RED])
- C_boxes[boxnum].min_pix[RED] = ptr->pixel[RED];
- if (ptr->pixel[RED] > C_boxes[boxnum].max_pix[RED])
- C_boxes[boxnum].max_pix[RED] = ptr->pixel[RED];
- if (ptr->pixel[GREEN] < C_boxes[boxnum].min_pix[GREEN])
- C_boxes[boxnum].min_pix[GREEN] = ptr->pixel[GREEN];
- if (ptr->pixel[GREEN] > C_boxes[boxnum].max_pix[GREEN])
- C_boxes[boxnum].max_pix[GREEN] = ptr->pixel[GREEN];
- if (ptr->pixel[BLUE] < C_boxes[boxnum].min_pix[BLUE])
- C_boxes[boxnum].min_pix[BLUE] = ptr->pixel[BLUE];
- if (ptr->pixel[BLUE] > C_boxes[boxnum].max_pix[BLUE])
- C_boxes[boxnum].max_pix[BLUE] = ptr->pixel[BLUE];
- }
-}
-
-
-void
-CountColors(data, colrs)
-unsigned char *data;
-struct colr_data *colrs;
-{
- unsigned char *dptr;
- register int i, j;
- int red, green, blue;
- register struct color_rec *tptr;
-
- InitMinMax(0);
- C_boxes[0].c_data = NULL;
- tptr = C_boxes[0].c_data;
- ColorCnt = 0;
-
- dptr = data;
-
- for (j = 0; j < Height; j++) {
- for (i = 0; i < Width; i++) {
- red = colrs[(int) *dptr].red;
- green = colrs[(int) *dptr].green;
- blue = colrs[(int) *dptr].blue;
- FindHash(red, green, blue, tptr);
- if (tptr == NULL) {
- tptr = AddHash(red, green, blue);
- tptr->next = NULL;
- AddColor(tptr, 0);
- ColorCnt++;
- }
- dptr++;
- }
- }
-}
-
-
-int
-FindTarget(tptr)
-int *tptr;
-{
- int range, i, indx;
-
- range = 0;
- for (i = 0; i < BoxCount; i++) {
- int rr, gr, br;
-
- rr = C_boxes[i].max_pix[RED] - C_boxes[i].min_pix[RED];
- gr = C_boxes[i].max_pix[GREEN] - C_boxes[i].min_pix[GREEN];
- br = C_boxes[i].max_pix[BLUE] - C_boxes[i].min_pix[BLUE];
- if (rr > range) {
- range = rr;
- *tptr = i;
- indx = RED;
- }
- if (gr > range) {
- range = gr;
- *tptr = i;
- indx = GREEN;
- }
- if (br > range) {
- range = br;
- *tptr = i;
- indx = BLUE;
- }
- }
- return (indx);
-}
-
-
-void
-SplitBox(boxnum, color_indx)
-int boxnum, color_indx;
-{
- struct color_rec *low, *high;
- struct color_rec *data;
- int med_cnt, split_val;
- int low_cnt, high_cnt;
- int Low_cnt, High_cnt;
- int Greater, Lesser;
-
- Greater = BoxCount++;
- Lesser = boxnum;
- InitMinMax(Lesser);
- InitMinMax(Greater);
- data = C_boxes[boxnum].c_data;
- med_cnt = C_boxes[boxnum].count / 2;
- C_boxes[Lesser].c_data = NULL;
- C_boxes[Greater].c_data = NULL;
- Low_cnt = 0;
- High_cnt = 0;
- while (med_cnt > 0) {
- if (data->pixel[color_indx] < data->next->pixel[color_indx]) {
- low = data;
- high = data->next;
- data = high->next;
- } else {
- high = data;
- low = data->next;
- data = low->next;
- }
- low->next = NULL;
- high->next = NULL;
- low_cnt = 1;
- high_cnt = 1;
- split_val = low->pixel[color_indx];
- while (data != NULL) {
- tptr = data;
- data = data->next;
- if (tptr->pixel[color_indx] > split_val) {
- tptr->next = high;
- high = tptr;
- high_cnt++;
- } else {
- tptr->next = low;
- low = tptr;
- low_cnt++;
- }
- } /* end while data->next != NULL */
- if (low_cnt <= med_cnt) {
- AddColor(low, Lesser);
- Low_cnt += low_cnt;
- med_cnt -= low_cnt;
- if (med_cnt == 0) {
- AddColor(high, Greater);
- High_cnt += high_cnt;
- }
- data = high;
- } else {
- AddColor(high, Greater);
- High_cnt += high_cnt;
- data = low;
- }
- } /* end while med_cnt */
- C_boxes[Lesser].count = Low_cnt;
- C_boxes[Greater].count = High_cnt;
-
-}
-
-
-void
-SplitColors(e_cnt)
-int e_cnt;
-{
- if (ColorCnt < e_cnt) {
- int i;
-
- tptr = C_boxes[0].c_data;
- for (i = 0; i < ColorCnt; i++) {
- hash_ptr = tptr;
- tptr = tptr->next;
- C_boxes[i].c_data = hash_ptr;
- C_boxes[i].count = 1;
- hash_ptr->box_num = i;
- hash_ptr->next = NULL;
- }
- BoxCount = ColorCnt;
- } else {
- BoxCount = 1;
- while (BoxCount < e_cnt) {
- int target, color_indx;
-
- target = 0;
- color_indx = 0;
- color_indx = FindTarget(&target);
- SplitBox(target, color_indx);
- }
- }
-}
-
-
-/*
- * Colors passed in 0-65535, internally are 0-255
- */
-void
-ConvertColor(rp, gp, bp)
-int *rp, *gp, *bp;
-{
- struct color_rec *cptr;
- register struct color_rec *hash_ptr;
- int indx;
- int red, green, blue;
- int Tred, Tgreen, Tblue;
- int c_cnt;
-
- red = *rp / NCells;
- green = *gp / NCells;
- blue = *bp / NCells;
- FindHash(red, green, blue, hash_ptr);
- if (hash_ptr == NULL) {
- fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue);
- hash_ptr = Hash[0];
- }
- indx = hash_ptr->box_num;
- cptr = C_boxes[indx].c_data;
- c_cnt = 0;
- Tred = Tgreen = Tblue = 0;
- while (cptr != NULL) {
- Tred += cptr->pixel[RED];
- Tgreen += cptr->pixel[GREEN];
- Tblue += cptr->pixel[BLUE];
- c_cnt++;
- cptr = cptr->next;
- }
- if (c_cnt) {
- red = Tred / c_cnt;
- green = Tgreen / c_cnt;
- blue = Tblue / c_cnt;
- }
-
- *rp = red * NCells;
- *gp = green * NCells;
- *bp = blue * NCells;
-}
-
-
-void
-ConvertData(data, colrs)
-unsigned char *data;
-struct colr_data *colrs;
-{
- unsigned char *dptr;
- register int i, j;
- int red, green, blue;
- register struct color_rec *hash_ptr;
-
- dptr = data;
-
- for (j = 0; j < Height; j++) {
- for (i = 0; i < Width; i++) {
- red = colrs[(int) *dptr].red;
- green = colrs[(int) *dptr].green;
- blue = colrs[(int) *dptr].blue;
- FindHash(red, green, blue, hash_ptr);
- if (hash_ptr == NULL) {
- fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue);
- hash_ptr = Hash[0];
- }
- *dptr++ = (unsigned char) hash_ptr->box_num;
- }
- }
-}
-
-
-void
-PrintColormap(e_cnt, colrs)
-int e_cnt;
-struct colr_data *colrs;
-{
- int i;
-
- for (i = 0; i < BoxCount; i++) {
- int Tred, Tgreen, Tblue;
- int c_cnt;
-
- c_cnt = 0;
- Tred = Tgreen = Tblue = 0;
- tptr = C_boxes[i].c_data;
- while (tptr != NULL) {
- Tred += tptr->pixel[RED];
- Tgreen += tptr->pixel[GREEN];
- Tblue += tptr->pixel[BLUE];
- c_cnt++;
- tptr = tptr->next;
- }
- colrs[i].red = Tred / c_cnt;
- colrs[i].green = Tgreen / c_cnt;
- colrs[i].blue = Tblue / c_cnt;
- }
- for (i = BoxCount; i < e_cnt; i++) {
- colrs[i].red = 0;
- colrs[i].green = 0;
- colrs[i].blue = 0;
- }
-}
-
-
-void
-MedianCut(data, w, h, colrs, start_cnt, end_cnt)
-unsigned char *data;
-int *w, *h;
-struct colr_data *colrs;
-int start_cnt, end_cnt;
-{
- int i;
-
- Width = *w;
- Height = *h;
- NCells = start_cnt;
- BoxCount = 0;
- ColorCnt = 0;
- for (i = 0; i < 256; i++) {
- Hash[i] = NULL;
- C_boxes[i].c_data = NULL;
- C_boxes[i].count = 0;
- }
- CountColors(data, colrs);
- C_boxes[0].count = ColorCnt;
- SplitColors(end_cnt);
- ConvertData(data, colrs);
- PrintColormap(end_cnt, colrs);
- for (i = 0; i < 256; i++) {
- hash_ptr = Hash[i];
- while (hash_ptr != NULL) {
- tptr = hash_ptr;
- hash_ptr = hash_ptr->hash_next;
- free((char *) tptr);
- }
- }
-}
-
-
-void
-MedianInit()
-{
- int i;
-
- NCells = 256;
- BoxCount = 0;
- ColorCnt = 0;
- for (i = 0; i < 256; i++) {
- Hash[i] = NULL;
- C_boxes[i].c_data = NULL;
- C_boxes[i].count = 0;
- }
- InitMinMax(0);
- C_boxes[0].c_data = NULL;
- Tptr = C_boxes[0].c_data;
-}
-
-
-/*
- * colrs are passed on 0-65535, but this median cut only deals with
- * 0-255.
- */
-void
-MedianCount(data, w, h, colrs)
-unsigned char *data;
-int w, h;
-struct colr_data *colrs;
-{
- unsigned char *dptr;
- register int i, j;
- int red, green, blue;
-
- Width = w;
- Height = h;
- dptr = data;
-
- for (j = 0; j < Height; j++) {
- for (i = 0; i < Width; i++) {
- red = colrs[(int) *dptr].red / NCells;
- green = colrs[(int) *dptr].green / NCells;
- blue = colrs[(int) *dptr].blue / NCells;
- FindHash(red, green, blue, tptr);
- if (tptr == NULL) {
- tptr = AddHash(red, green, blue);
- tptr->next = NULL;
- AddColor(tptr, 0);
- ColorCnt++;
- }
- dptr++;
- }
- }
-}
-
-
-void
-MedianSplit(end_cnt)
-int end_cnt;
-{
- C_boxes[0].count = ColorCnt;
- SplitColors(end_cnt);
-}
-
-
-void
-MedianConvert(data, w, h, colrs)
-unsigned char *data;
-int w, h;
-struct colr_data *colrs;
-{
- Width = w;
- Height = h;
- ConvertData(data, colrs);
-}
-
-
-void
-MedianMerge(colrs, end_cnt)
-struct colr_data *colrs;
-int end_cnt;
-{
- int i;
-
- PrintColormap(end_cnt, colrs);
- for (i = 0; i < 256; i++) {
- hash_ptr = Hash[i];
- while (hash_ptr != NULL) {
- tptr = hash_ptr;
- hash_ptr = hash_ptr->hash_next;
- free((char *) tptr);
- }
- }
-}