]>
Commit | Line | Data |
---|---|---|
1 | #include <stdio.h> | |
2 | #include <stdlib.h> | |
3 | #include "medcut.h" | |
4 | ||
5 | #define RED 0 | |
6 | #define GREEN 1 | |
7 | #define BLUE 2 | |
8 | ||
9 | #define FindHash(red, green, blue, h_ptr) \ | |
10 | h_ptr = Hash[((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256]; \ | |
11 | while(h_ptr != NULL) \ | |
12 | { \ | |
13 | if ((h_ptr->pixel[RED] == red)&& \ | |
14 | (h_ptr->pixel[GREEN] == green)&& \ | |
15 | (h_ptr->pixel[BLUE] == blue)) \ | |
16 | { \ | |
17 | break; \ | |
18 | } \ | |
19 | h_ptr = h_ptr->hash_next; \ | |
20 | } | |
21 | ||
22 | struct color_rec { | |
23 | int pixel[3]; | |
24 | int box_num; | |
25 | struct color_rec *hash_next; | |
26 | struct color_rec *next; | |
27 | } *Hash[256]; | |
28 | struct c_box_rec { | |
29 | int min_pix[3]; | |
30 | int max_pix[3]; | |
31 | int count; | |
32 | struct color_rec *c_data; | |
33 | } C_boxes[256]; | |
34 | ||
35 | int BoxCount; | |
36 | struct color_rec *hash_ptr; | |
37 | struct color_rec *tptr; | |
38 | static int Width, Height; | |
39 | int ColorCnt; | |
40 | int NCells; | |
41 | struct color_rec *Tptr; | |
42 | ||
43 | ||
44 | void | |
45 | InitMinMax(boxnum) | |
46 | int boxnum; | |
47 | { | |
48 | C_boxes[boxnum].min_pix[RED] = 256; | |
49 | C_boxes[boxnum].max_pix[RED] = 0; | |
50 | C_boxes[boxnum].min_pix[GREEN] = 256; | |
51 | C_boxes[boxnum].max_pix[GREEN] = 0; | |
52 | C_boxes[boxnum].min_pix[BLUE] = 256; | |
53 | C_boxes[boxnum].max_pix[BLUE] = 0; | |
54 | } | |
55 | ||
56 | ||
57 | struct color_rec * | |
58 | AddHash(red, green, blue) | |
59 | int red, green, blue; | |
60 | { | |
61 | int lum; | |
62 | ||
63 | lum = ((red * 299) + (green * 587) + (blue * 114)) / 1000 * NCells / 256;; | |
64 | hash_ptr = (struct color_rec *) malloc(sizeof(struct color_rec)); | |
65 | if (hash_ptr == NULL) { | |
66 | fprintf(stderr, "Cannot malloc %dth color\n", ColorCnt); | |
67 | exit(1); | |
68 | } | |
69 | hash_ptr->pixel[RED] = red; | |
70 | hash_ptr->pixel[GREEN] = green; | |
71 | hash_ptr->pixel[BLUE] = blue; | |
72 | hash_ptr->box_num = 0; | |
73 | hash_ptr->next = NULL; | |
74 | hash_ptr->hash_next = Hash[lum]; | |
75 | Hash[lum] = hash_ptr; | |
76 | return (hash_ptr); | |
77 | } | |
78 | ||
79 | ||
80 | void | |
81 | AddColor(cptr, boxnum) | |
82 | struct color_rec *cptr; | |
83 | int boxnum; | |
84 | { | |
85 | struct color_rec *ptr; | |
86 | ||
87 | while (cptr != NULL) { | |
88 | ptr = cptr; | |
89 | cptr = cptr->next; | |
90 | ptr->box_num = boxnum; | |
91 | ptr->next = C_boxes[boxnum].c_data; | |
92 | C_boxes[boxnum].c_data = ptr; | |
93 | if (ptr->pixel[RED] < C_boxes[boxnum].min_pix[RED]) | |
94 | C_boxes[boxnum].min_pix[RED] = ptr->pixel[RED]; | |
95 | if (ptr->pixel[RED] > C_boxes[boxnum].max_pix[RED]) | |
96 | C_boxes[boxnum].max_pix[RED] = ptr->pixel[RED]; | |
97 | if (ptr->pixel[GREEN] < C_boxes[boxnum].min_pix[GREEN]) | |
98 | C_boxes[boxnum].min_pix[GREEN] = ptr->pixel[GREEN]; | |
99 | if (ptr->pixel[GREEN] > C_boxes[boxnum].max_pix[GREEN]) | |
100 | C_boxes[boxnum].max_pix[GREEN] = ptr->pixel[GREEN]; | |
101 | if (ptr->pixel[BLUE] < C_boxes[boxnum].min_pix[BLUE]) | |
102 | C_boxes[boxnum].min_pix[BLUE] = ptr->pixel[BLUE]; | |
103 | if (ptr->pixel[BLUE] > C_boxes[boxnum].max_pix[BLUE]) | |
104 | C_boxes[boxnum].max_pix[BLUE] = ptr->pixel[BLUE]; | |
105 | } | |
106 | } | |
107 | ||
108 | ||
109 | void | |
110 | CountColors(data, colrs) | |
111 | unsigned char *data; | |
112 | struct colr_data *colrs; | |
113 | { | |
114 | unsigned char *dptr; | |
115 | register int i, j; | |
116 | int red, green, blue; | |
117 | register struct color_rec *tptr; | |
118 | ||
119 | InitMinMax(0); | |
120 | C_boxes[0].c_data = NULL; | |
121 | tptr = C_boxes[0].c_data; | |
122 | ColorCnt = 0; | |
123 | ||
124 | dptr = data; | |
125 | ||
126 | for (j = 0; j < Height; j++) { | |
127 | for (i = 0; i < Width; i++) { | |
128 | red = colrs[(int) *dptr].red; | |
129 | green = colrs[(int) *dptr].green; | |
130 | blue = colrs[(int) *dptr].blue; | |
131 | FindHash(red, green, blue, tptr); | |
132 | if (tptr == NULL) { | |
133 | tptr = AddHash(red, green, blue); | |
134 | tptr->next = NULL; | |
135 | AddColor(tptr, 0); | |
136 | ColorCnt++; | |
137 | } | |
138 | dptr++; | |
139 | } | |
140 | } | |
141 | } | |
142 | ||
143 | ||
144 | int | |
145 | FindTarget(tptr) | |
146 | int *tptr; | |
147 | { | |
148 | int range, i, indx; | |
149 | ||
150 | range = 0; | |
151 | for (i = 0; i < BoxCount; i++) { | |
152 | int rr, gr, br; | |
153 | ||
154 | rr = C_boxes[i].max_pix[RED] - C_boxes[i].min_pix[RED]; | |
155 | gr = C_boxes[i].max_pix[GREEN] - C_boxes[i].min_pix[GREEN]; | |
156 | br = C_boxes[i].max_pix[BLUE] - C_boxes[i].min_pix[BLUE]; | |
157 | if (rr > range) { | |
158 | range = rr; | |
159 | *tptr = i; | |
160 | indx = RED; | |
161 | } | |
162 | if (gr > range) { | |
163 | range = gr; | |
164 | *tptr = i; | |
165 | indx = GREEN; | |
166 | } | |
167 | if (br > range) { | |
168 | range = br; | |
169 | *tptr = i; | |
170 | indx = BLUE; | |
171 | } | |
172 | } | |
173 | return (indx); | |
174 | } | |
175 | ||
176 | ||
177 | void | |
178 | SplitBox(boxnum, color_indx) | |
179 | int boxnum, color_indx; | |
180 | { | |
181 | struct color_rec *low, *high; | |
182 | struct color_rec *data; | |
183 | int med_cnt, split_val; | |
184 | int low_cnt, high_cnt; | |
185 | int Low_cnt, High_cnt; | |
186 | int Greater, Lesser; | |
187 | ||
188 | Greater = BoxCount++; | |
189 | Lesser = boxnum; | |
190 | InitMinMax(Lesser); | |
191 | InitMinMax(Greater); | |
192 | data = C_boxes[boxnum].c_data; | |
193 | med_cnt = C_boxes[boxnum].count / 2; | |
194 | C_boxes[Lesser].c_data = NULL; | |
195 | C_boxes[Greater].c_data = NULL; | |
196 | Low_cnt = 0; | |
197 | High_cnt = 0; | |
198 | while (med_cnt > 0) { | |
199 | if (data->pixel[color_indx] < data->next->pixel[color_indx]) { | |
200 | low = data; | |
201 | high = data->next; | |
202 | data = high->next; | |
203 | } else { | |
204 | high = data; | |
205 | low = data->next; | |
206 | data = low->next; | |
207 | } | |
208 | low->next = NULL; | |
209 | high->next = NULL; | |
210 | low_cnt = 1; | |
211 | high_cnt = 1; | |
212 | split_val = low->pixel[color_indx]; | |
213 | while (data != NULL) { | |
214 | tptr = data; | |
215 | data = data->next; | |
216 | if (tptr->pixel[color_indx] > split_val) { | |
217 | tptr->next = high; | |
218 | high = tptr; | |
219 | high_cnt++; | |
220 | } else { | |
221 | tptr->next = low; | |
222 | low = tptr; | |
223 | low_cnt++; | |
224 | } | |
225 | } /* end while data->next != NULL */ | |
226 | if (low_cnt <= med_cnt) { | |
227 | AddColor(low, Lesser); | |
228 | Low_cnt += low_cnt; | |
229 | med_cnt -= low_cnt; | |
230 | if (med_cnt == 0) { | |
231 | AddColor(high, Greater); | |
232 | High_cnt += high_cnt; | |
233 | } | |
234 | data = high; | |
235 | } else { | |
236 | AddColor(high, Greater); | |
237 | High_cnt += high_cnt; | |
238 | data = low; | |
239 | } | |
240 | } /* end while med_cnt */ | |
241 | C_boxes[Lesser].count = Low_cnt; | |
242 | C_boxes[Greater].count = High_cnt; | |
243 | ||
244 | } | |
245 | ||
246 | ||
247 | void | |
248 | SplitColors(e_cnt) | |
249 | int e_cnt; | |
250 | { | |
251 | if (ColorCnt < e_cnt) { | |
252 | int i; | |
253 | ||
254 | tptr = C_boxes[0].c_data; | |
255 | for (i = 0; i < ColorCnt; i++) { | |
256 | hash_ptr = tptr; | |
257 | tptr = tptr->next; | |
258 | C_boxes[i].c_data = hash_ptr; | |
259 | C_boxes[i].count = 1; | |
260 | hash_ptr->box_num = i; | |
261 | hash_ptr->next = NULL; | |
262 | } | |
263 | BoxCount = ColorCnt; | |
264 | } else { | |
265 | BoxCount = 1; | |
266 | while (BoxCount < e_cnt) { | |
267 | int target, color_indx; | |
268 | ||
269 | target = 0; | |
270 | color_indx = 0; | |
271 | color_indx = FindTarget(&target); | |
272 | SplitBox(target, color_indx); | |
273 | } | |
274 | } | |
275 | } | |
276 | ||
277 | ||
278 | /* | |
279 | * Colors passed in 0-65535, internally are 0-255 | |
280 | */ | |
281 | void | |
282 | ConvertColor(rp, gp, bp) | |
283 | int *rp, *gp, *bp; | |
284 | { | |
285 | struct color_rec *cptr; | |
286 | register struct color_rec *hash_ptr; | |
287 | int indx; | |
288 | int red, green, blue; | |
289 | int Tred, Tgreen, Tblue; | |
290 | int c_cnt; | |
291 | ||
292 | red = *rp / NCells; | |
293 | green = *gp / NCells; | |
294 | blue = *bp / NCells; | |
295 | FindHash(red, green, blue, hash_ptr); | |
296 | if (hash_ptr == NULL) { | |
297 | fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue); | |
298 | hash_ptr = Hash[0]; | |
299 | } | |
300 | indx = hash_ptr->box_num; | |
301 | cptr = C_boxes[indx].c_data; | |
302 | c_cnt = 0; | |
303 | Tred = Tgreen = Tblue = 0; | |
304 | while (cptr != NULL) { | |
305 | Tred += cptr->pixel[RED]; | |
306 | Tgreen += cptr->pixel[GREEN]; | |
307 | Tblue += cptr->pixel[BLUE]; | |
308 | c_cnt++; | |
309 | cptr = cptr->next; | |
310 | } | |
311 | if (c_cnt) { | |
312 | red = Tred / c_cnt; | |
313 | green = Tgreen / c_cnt; | |
314 | blue = Tblue / c_cnt; | |
315 | } | |
316 | ||
317 | *rp = red * NCells; | |
318 | *gp = green * NCells; | |
319 | *bp = blue * NCells; | |
320 | } | |
321 | ||
322 | ||
323 | void | |
324 | ConvertData(data, colrs) | |
325 | unsigned char *data; | |
326 | struct colr_data *colrs; | |
327 | { | |
328 | unsigned char *dptr; | |
329 | register int i, j; | |
330 | int red, green, blue; | |
331 | register struct color_rec *hash_ptr; | |
332 | ||
333 | dptr = data; | |
334 | ||
335 | for (j = 0; j < Height; j++) { | |
336 | for (i = 0; i < Width; i++) { | |
337 | red = colrs[(int) *dptr].red; | |
338 | green = colrs[(int) *dptr].green; | |
339 | blue = colrs[(int) *dptr].blue; | |
340 | FindHash(red, green, blue, hash_ptr); | |
341 | if (hash_ptr == NULL) { | |
342 | fprintf(stderr, "Unknown color (%d,%d,%d)\n", red, green, blue); | |
343 | hash_ptr = Hash[0]; | |
344 | } | |
345 | *dptr++ = (unsigned char) hash_ptr->box_num; | |
346 | } | |
347 | } | |
348 | } | |
349 | ||
350 | ||
351 | void | |
352 | PrintColormap(e_cnt, colrs) | |
353 | int e_cnt; | |
354 | struct colr_data *colrs; | |
355 | { | |
356 | int i; | |
357 | ||
358 | for (i = 0; i < BoxCount; i++) { | |
359 | int Tred, Tgreen, Tblue; | |
360 | int c_cnt; | |
361 | ||
362 | c_cnt = 0; | |
363 | Tred = Tgreen = Tblue = 0; | |
364 | tptr = C_boxes[i].c_data; | |
365 | while (tptr != NULL) { | |
366 | Tred += tptr->pixel[RED]; | |
367 | Tgreen += tptr->pixel[GREEN]; | |
368 | Tblue += tptr->pixel[BLUE]; | |
369 | c_cnt++; | |
370 | tptr = tptr->next; | |
371 | } | |
372 | colrs[i].red = Tred / c_cnt; | |
373 | colrs[i].green = Tgreen / c_cnt; | |
374 | colrs[i].blue = Tblue / c_cnt; | |
375 | } | |
376 | for (i = BoxCount; i < e_cnt; i++) { | |
377 | colrs[i].red = 0; | |
378 | colrs[i].green = 0; | |
379 | colrs[i].blue = 0; | |
380 | } | |
381 | } | |
382 | ||
383 | ||
384 | void | |
385 | MedianCut(data, w, h, colrs, start_cnt, end_cnt) | |
386 | unsigned char *data; | |
387 | int *w, *h; | |
388 | struct colr_data *colrs; | |
389 | int start_cnt, end_cnt; | |
390 | { | |
391 | int i; | |
392 | ||
393 | Width = *w; | |
394 | Height = *h; | |
395 | NCells = start_cnt; | |
396 | BoxCount = 0; | |
397 | ColorCnt = 0; | |
398 | for (i = 0; i < 256; i++) { | |
399 | Hash[i] = NULL; | |
400 | C_boxes[i].c_data = NULL; | |
401 | C_boxes[i].count = 0; | |
402 | } | |
403 | CountColors(data, colrs); | |
404 | C_boxes[0].count = ColorCnt; | |
405 | SplitColors(end_cnt); | |
406 | ConvertData(data, colrs); | |
407 | PrintColormap(end_cnt, colrs); | |
408 | for (i = 0; i < 256; i++) { | |
409 | hash_ptr = Hash[i]; | |
410 | while (hash_ptr != NULL) { | |
411 | tptr = hash_ptr; | |
412 | hash_ptr = hash_ptr->hash_next; | |
413 | free((char *) tptr); | |
414 | } | |
415 | } | |
416 | } | |
417 | ||
418 | ||
419 | void | |
420 | MedianInit() | |
421 | { | |
422 | int i; | |
423 | ||
424 | NCells = 256; | |
425 | BoxCount = 0; | |
426 | ColorCnt = 0; | |
427 | for (i = 0; i < 256; i++) { | |
428 | Hash[i] = NULL; | |
429 | C_boxes[i].c_data = NULL; | |
430 | C_boxes[i].count = 0; | |
431 | } | |
432 | InitMinMax(0); | |
433 | C_boxes[0].c_data = NULL; | |
434 | Tptr = C_boxes[0].c_data; | |
435 | } | |
436 | ||
437 | ||
438 | /* | |
439 | * colrs are passed on 0-65535, but this median cut only deals with | |
440 | * 0-255. | |
441 | */ | |
442 | void | |
443 | MedianCount(data, w, h, colrs) | |
444 | unsigned char *data; | |
445 | int w, h; | |
446 | struct colr_data *colrs; | |
447 | { | |
448 | unsigned char *dptr; | |
449 | register int i, j; | |
450 | int red, green, blue; | |
451 | ||
452 | Width = w; | |
453 | Height = h; | |
454 | dptr = data; | |
455 | ||
456 | for (j = 0; j < Height; j++) { | |
457 | for (i = 0; i < Width; i++) { | |
458 | red = colrs[(int) *dptr].red / NCells; | |
459 | green = colrs[(int) *dptr].green / NCells; | |
460 | blue = colrs[(int) *dptr].blue / NCells; | |
461 | FindHash(red, green, blue, tptr); | |
462 | if (tptr == NULL) { | |
463 | tptr = AddHash(red, green, blue); | |
464 | tptr->next = NULL; | |
465 | AddColor(tptr, 0); | |
466 | ColorCnt++; | |
467 | } | |
468 | dptr++; | |
469 | } | |
470 | } | |
471 | } | |
472 | ||
473 | ||
474 | void | |
475 | MedianSplit(end_cnt) | |
476 | int end_cnt; | |
477 | { | |
478 | C_boxes[0].count = ColorCnt; | |
479 | SplitColors(end_cnt); | |
480 | } | |
481 | ||
482 | ||
483 | void | |
484 | MedianConvert(data, w, h, colrs) | |
485 | unsigned char *data; | |
486 | int w, h; | |
487 | struct colr_data *colrs; | |
488 | { | |
489 | Width = w; | |
490 | Height = h; | |
491 | ConvertData(data, colrs); | |
492 | } | |
493 | ||
494 | ||
495 | void | |
496 | MedianMerge(colrs, end_cnt) | |
497 | struct colr_data *colrs; | |
498 | int end_cnt; | |
499 | { | |
500 | int i; | |
501 | ||
502 | PrintColormap(end_cnt, colrs); | |
503 | for (i = 0; i < 256; i++) { | |
504 | hash_ptr = Hash[i]; | |
505 | while (hash_ptr != NULL) { | |
506 | tptr = hash_ptr; | |
507 | hash_ptr = hash_ptr->hash_next; | |
508 | free((char *) tptr); | |
509 | } | |
510 | } | |
511 | } |