1 /****************************************************************
2 * aoctree.c:
3 *
4 * Copyright (C) 1995-2002 Klaus Ehrenfried
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 *
20 *************************************************************************/
21
22 /*******
23 This program is based on the Octree algorithm described
24 by Michael Gervautz and Werner Purgathofer (Technical University
25 Vienna, Austria) in the article "A Simple Method for Color Quantization:
26 Octree Quantization" published in Graphic Gems edited by Andrew Glassner
27 pp. 287 ff.
28 *******/
29
30 #include <stdio.h>
31 #include <math.h>
32 #include <string.h>
33 #include <stdlib.h>
34 #include "apro.h"
35
36 #define BIGVAL 0x10000000
37
38 typedef struct node *OCTREE;
39
40 struct node
41 {
42 UBYTE leaf;
43 UBYTE level;
44 UBYTE color;
45 UBYTE rgb[3];
46 UBYTE sub_count;
47 ULONG pixels_low;
48 ULONG pixels_high;
49 ULONG red_sum_low;
50 ULONG red_sum_high;
51 ULONG green_sum_low;
52 ULONG green_sum_high;
53 ULONG blue_sum_low;
54 ULONG blue_sum_high;
55 OCTREE sub[8];
56 OCTREE next_reduceable;
57 OCTREE next_alloc;
58 };
59
60 static void search_colors(OCTREE tree);
61 static void scan_large_tree(OCTREE tree);
62 static void reduce_large_octree();
63 static void norm_tree(OCTREE tree);
64 static void shorten_list();
65
66 #define RED 0
67 #define GREEN 1
68 #define BLUE 2
69
70 #define TRUE 1
71 #define FALSE 0
72
73 static LONG palette[FLI_MAX_COLORS];
74
75 static int octree_size;
76 static int reduce_level;
77 static int leaf_level;
78 static int reduce_start;
79
80 static OCTREE basetree;
81 static OCTREE reduce_list;
82 static int node_count[MAXDEPTH + 2];
83 static int reduce_count[MAXDEPTH + 1];
84 static int tree_count;
85 static OCTREE alloc_list=NULL;
86 static UBYTE b_field[]={128,64,32,16,8,4,2,1};
87
88 /*static double color_factor;*/
89 static int color_count;
90
91 /************************************************************************
92 * clr_quantize
93 ************************************************************************/
94
clr_quantize(PMS * input,UBYTE * p_output,LONG * color)95 int clr_quantize(PMS *input, UBYTE *p_output, LONG *color)
96 {
97 UBYTE b_red, b_green, b_blue, branch, btest;
98 UBYTE *pp;
99 OCTREE tree, next_tree, sub_tree;
100 int i,j,jmin,d1,d2,d3,dtest,dmin,unexpected;
101 double ratio;
102
103 pp = input->pixels;
104
105 unexpected=0;
106
107 for (i=0; i < input->len; i++)
108 {
109 b_red = *(pp++);
110 b_green = *(pp++);
111 b_blue = *(pp++);
112
113 tree=basetree;
114 next_tree=NULL;
115
116 while (tree->leaf == 0)
117 {
118 btest=b_field[tree->level];
119 branch=((b_red & btest) == 0) ? (UBYTE) 0 : (UBYTE) 4;
120 if ((b_green & btest) != 0) branch += (UBYTE) 2;
121 if ((b_blue & btest) != 0) branch += (UBYTE) 1;
122 next_tree=tree->sub[branch];
123 if (next_tree == NULL) break;
124 tree=next_tree;
125 }
126
127 if (next_tree == 0)
128 {
129 unexpected++;
130 while (tree->leaf == 0)
131 {
132 jmin=-1;
133 dmin=0;
134 for (j=0; j < 8; j++)
135 {
136 sub_tree=tree->sub[j];
137 if (sub_tree == NULL) continue;
138
139 d1=abs((int)sub_tree->rgb[RED] - (int)b_red);
140 d2=abs((int)sub_tree->rgb[GREEN] - (int)b_green);
141 d3=abs((int)sub_tree->rgb[BLUE] - (int)b_blue);
142
143 dtest=(d1 > d2) ? d1 : d2;
144 dtest=(d3 > dtest) ? d3 : dtest;
145
146 if ((jmin == -1) || (dtest < dmin))
147 {
148 dmin=dtest;
149 jmin=j;
150 }
151 }
152 if (jmin == -1)
153 {
154 fprintf(stdout,"Warning: %d\n",i);
155 break;
156 }
157 tree=tree->sub[jmin];
158 }
159 }
160
161 *(p_output++) = tree->color;
162 }
163
164 if (unexpected > 0)
165 {
166 ratio = 100.0 * unexpected/input->len;
167 fprintf(stdout," Quantize: %d non-fitting pixel(s) = %.4f %%\n",
168 unexpected, ratio);
169 }
170
171 for (i=0; i < FLI_MAX_COLORS; i++)
172 color[i]=palette[i];
173
174 return(color_count);
175 }
176
177 /************************************************************************
178 * prepare_quantize *
179 ************************************************************************/
180
prepare_quantize()181 void prepare_quantize()
182 {
183 int i;
184
185 /* final reduction */
186 for (i=0; i <= MAXDEPTH; i++)
187 {
188 reduce_count[i]=0;
189 }
190
191 reduce_start = leaf_level - 1;
192 for (i = 1; i < leaf_level; i++)
193 {
194 if (node_count[i] >= max_colors)
195 {
196 reduce_start = i - 1;
197 break;
198 }
199 }
200
201 reduce_level = reduce_start + reduce_dynamics;
202 if (reduce_level >= leaf_level)
203 {
204 reduce_level = leaf_level - 1;
205 reduce_start = reduce_level - reduce_dynamics;
206 if (reduce_start < 0) reduce_start = 0;
207 }
208 else
209 {
210 leaf_level = reduce_level + 1;
211 }
212
213 /*
214 if (verbose_flag > 1)
215 {
216 fprintf(stdout," octree reduction in levels %d to %d\n",
217 reduce_start,
218 reduce_level);
219 }
220 */
221
222 octree_size=0;
223 reduce_list=NULL;
224 scan_large_tree(basetree);
225 shorten_list();
226 while (octree_size > max_colors)
227 {
228 /* fprintf(stderr,"%d\n",octree_size); */
229 reduce_large_octree();
230 }
231 /***
232 if (verbose_flag > 1)
233 {
234 fprintf(stdout," Octree - reduce count:");
235 for (i=0; i <= MAXDEPTH; i++)
236 {
237 if ((i >= reduce_start) && (i <= reduce_level))
238 {
239 fprintf(stdout," %d", reduce_count[i]);
240 }
241 else
242 {
243 fprintf(stdout," -");
244 }
245 }
246 fprintf(stdout,"\n");
247 }
248 ****/
249
250 /* now the colors */
251
252 for (i = 0; i < FLI_MAX_COLORS; i++) /* init palette */
253 palette[i] = 0;
254
255 color_count = 0;
256 /* color_factor = (double) ((1 << color_depth) - 1) / 0xFF; */
257
258 for (i=0; i <= (MAXDEPTH+1); i++)
259 {node_count[i] = 0;}
260
261 search_colors(basetree);
262 if (verbose_flag > 0)
263 fprintf(stdout," Number of colors: %d\n",color_count);
264 if (verbose_flag > 1)
265 {
266 fprintf(stdout," Octree - leaf count (%d):", leaf_level);
267 for (i=0; i <= (MAXDEPTH + 1); i++)
268 {
269 fprintf(stdout," %d",node_count[i]);
270 }
271 fprintf(stdout,"\n");
272 }
273
274
275 for (i = color_count; i < FLI_MAX_COLORS; i++) /* no extra 0 0 0 */
276 palette[i] = palette[0];
277 }
278
279 /************************************************************************
280 * scan_rgb_image *
281 ************************************************************************/
282
scan_rgb_image(char * file_name)283 void scan_rgb_image(char *file_name)
284 {
285 PMS input;
286
287 fprintf(stdout,"Scanning '%s'\n",file_name);
288
289 input.pixels = (UBYTE *) NULL;
290 if (!read_image(&input, file_name))
291 {
292 fprintf(stderr,"Error processing '%s'\n",file_name);
293 exitialise(1);
294 exit(1);
295 }
296
297 add_to_large_octree(&input);
298 tree_count = 0;
299 norm_tree(basetree);
300 if (verbose_flag > 1)
301 {
302 fprintf(stdout," Octree - total size: %d\n",tree_count);
303 }
304
305 free_pms(&input);
306 }
307
308 /************************************************************************
309 * add_to_large_octree
310 ************************************************************************/
311
add_to_large_octree(PMS * image)312 void add_to_large_octree(PMS *image)
313 {
314 UBYTE b_red, b_green, b_blue, branch, btest;
315 UBYTE b_mask;
316 UBYTE *pp;
317 OCTREE tree, *p_tree;
318 int i, depth, new_flag;
319
320 pp = image->pixels;
321
322 b_mask = 0xFF << (8 - color_depth);
323
324 for (i=0; i < image->len; i++)
325 {
326 b_red = *(pp++) & b_mask;
327 b_green = *(pp++) & b_mask;
328 b_blue = *(pp++) & b_mask;
329
330 p_tree = &basetree;
331 new_flag = 0;
332
333 for (depth = 0; depth <= leaf_level; depth++)
334 {
335 if (*p_tree == NULL) /* init new node */
336 {
337 tree = (OCTREE) calloc(1, sizeof(struct node));
338 if (tree == NULL)
339 {
340 printf("Out of memory");
341 exit(1);
342 }
343 tree->next_alloc=alloc_list;
344 alloc_list=tree;
345 tree->level = depth;
346 (node_count[depth])++;
347 new_flag = 1;
348 *p_tree = tree;
349 }
350 else
351 tree = *p_tree;
352
353 tree->pixels_low++;
354 tree->red_sum_low += b_red;
355 tree->green_sum_low += b_green;
356 tree->blue_sum_low += b_blue;
357
358 if (depth < leaf_level)
359 {
360 btest=b_field[depth];
361 branch=((b_red & btest) == 0) ? (UBYTE) 0 : (UBYTE) 4;
362 if ((b_green & btest) != 0) branch += (UBYTE) 2;
363 if ((b_blue & btest) != 0) branch += (UBYTE) 1;
364
365 if (tree->sub[branch] == NULL)
366 tree->sub_count++;
367 p_tree=&(tree->sub[branch]);
368 }
369 }
370
371 if (new_flag)
372 {
373 for (depth = 0; depth < leaf_level; depth++)
374 {
375 if (node_count[depth] >= node_limit) /* reduce octree */
376 {
377 leaf_level=depth;
378 break;
379 }
380 }
381 }
382 }
383
384 for (depth = (leaf_level+1); depth <= (MAXDEPTH+1) ;depth++)
385 node_count[depth] = 0;
386
387 if (verbose_flag > 1)
388 {
389 fprintf(stdout," Octree - node count (%d):", leaf_level);
390 for (i=0; i <= (MAXDEPTH + 1); i++)
391 {
392 fprintf(stdout," %d",node_count[i]);
393 }
394 fprintf(stdout,"\n");
395 }
396
397 }
398
399 /************************************************************************
400 * clear_octree *
401 ************************************************************************/
402
clear_octree()403 void clear_octree()
404 {
405 OCTREE next_node;
406 int i;
407
408 for (i=0; i <= MAXDEPTH+1; i++)
409 {
410 node_count[i]=0;
411 }
412 leaf_level = MAXDEPTH + 1;
413
414 basetree=NULL;
415
416 while (alloc_list != NULL)
417 {
418 next_node=alloc_list->next_alloc;
419 free(alloc_list);
420 alloc_list=next_node;
421 }
422 }
423
424 /************************************************************************
425 * output_palette
426 ************************************************************************/
427
output_palette()428 int output_palette()
429 {
430 LONG rgb_value;
431 int i, red, green, blue;
432
433 fprintf(output,"P3\n");
434 fprintf(output,"%d 1\n",color_count);
435 fprintf(output,"255\n");
436 fprintf(output,"# r g b index\n");
437 fprintf(output,"#---------------------\n");
438
439 for (i = 0; i < color_count; i++)
440 {
441 rgb_value = palette[i];
442 red=rgb_value % 256;
443 rgb_value=(rgb_value - red)/256;
444 green=rgb_value % 256;
445 rgb_value=(rgb_value - green)/256;
446 blue=rgb_value % 256;
447
448 fprintf(output," %3d %3d %3d # %d\n",red, green, blue, i);
449 }
450
451 return(1);
452 }
453
454 /************************************************************************
455 * search_colors
456 ************************************************************************/
457
search_colors(OCTREE tree)458 static void search_colors(OCTREE tree)
459 {
460 int j;
461 LONG rgb_value;
462 double dhelp0, dhelp1;
463
464 if (tree == NULL) return;
465
466 dhelp0=(double) tree->pixels_high * (double) BIGVAL
467 +(double) tree->pixels_low;
468
469 /*dhelp0=color_factor / dhelp0;*/
470 dhelp0=1.0 / dhelp0;
471
472 dhelp1=
473 (double) tree->red_sum_high * (double) BIGVAL
474 +(double) tree->red_sum_low;
475 tree->rgb[RED] = (char) (dhelp0 * dhelp1 + 0.5);
476
477 dhelp1=
478 (double) tree->green_sum_high * (double) BIGVAL
479 +(double) tree->green_sum_low;
480 tree->rgb[GREEN] = (char) (dhelp0 * dhelp1 + 0.5);
481
482 dhelp1=
483 (double) tree->blue_sum_high * (double) BIGVAL
484 +(double) tree->blue_sum_low;
485 tree->rgb[BLUE] = (char) (dhelp0 * dhelp1 + 0.5);
486
487 if (tree->leaf || tree->level == leaf_level)
488 {
489 rgb_value=(long int) tree->rgb[BLUE];
490 rgb_value=256L * rgb_value + (long int) tree->rgb[GREEN];
491 rgb_value=256L * rgb_value + (long int) tree->rgb[RED];
492
493 palette[color_count] = rgb_value;
494
495 tree->color = color_count;
496 tree->leaf = TRUE;
497 color_count++;
498 (node_count[tree->level])++;
499 }
500 else
501 {
502 for (j = 0; j < 8; j++)
503 search_colors(tree->sub[j]);
504 }
505 }
506
507 /************************************************************************
508 * scan_large_tree *
509 ************************************************************************/
510
scan_large_tree(OCTREE tree)511 static void scan_large_tree(OCTREE tree)
512 {
513 int j;
514
515 if (tree == NULL) return;
516 if ((tree->level <= reduce_level) &&
517 (tree->level >= reduce_start))
518 {
519 if (tree->sub_count > 0)
520 {
521 tree->next_reduceable = reduce_list;
522 reduce_list = tree;
523 }
524 }
525
526 if (tree->level == leaf_level)
527 {
528 tree->leaf = TRUE;
529 octree_size++;
530 }
531 else
532 {
533 tree->leaf = FALSE;
534 for (j = 0; j < 8; j++)
535 scan_large_tree(tree->sub[j]);
536 }
537 }
538
539 /************************************************************************
540 * shorten_list()
541 ************************************************************************/
542
shorten_list()543 static void shorten_list()
544 {
545 int i, flag, depth, n;
546 OCTREE tree, sub_tree, *p_tree;
547
548 p_tree = &reduce_list;
549 n = 0;
550
551 while ((tree = *p_tree) != NULL)
552 {
553 if (tree->sub_count == 1)
554 {
555 flag = 1;
556 for (i=0; i < 8; i++)
557 {
558 sub_tree=tree->sub[i];
559 if (sub_tree != NULL)
560 { if (sub_tree->leaf == 0) {flag = 0;} }
561 }
562
563 if (flag == 1)
564 {
565 tree->leaf = 1;
566 depth = tree->level;
567 (reduce_count[depth])++;
568 *p_tree=tree->next_reduceable;
569 n++;
570 }
571 else
572 {
573 p_tree=&(tree->next_reduceable);
574 }
575 }
576 else
577 {
578 p_tree=&(tree->next_reduceable);
579 }
580 }
581
582 /***
583 if ((verbose_flag > 1) && (n > 0))
584 {
585 fprintf(stdout," Octree - drop count:");
586 for (i=0; i <= MAXDEPTH; i++)
587 {
588 if ((i >= reduce_start) && (i <= reduce_level))
589 { fprintf(stdout," %d", reduce_count[i]);}
590 else
591 { fprintf(stdout," -");}
592 }
593 fprintf(stdout,"\n");
594 }
595 ****/
596 }
597
598 /************************************************************************
599 * reduce_large_octree
600 ************************************************************************/
601
reduce_large_octree()602 static void reduce_large_octree()
603 {
604 int i, flag, depth;
605 ULONG min_high, min_low;
606 OCTREE tree, sub_tree, *p_tree, *p_min;
607
608 if (reduce_list == NULL)
609 {
610 fprintf(stderr,"Internal error: ZERO reduce\n");
611 exit(1);
612 }
613
614 p_min = &reduce_list;
615 min_high = reduce_list->pixels_high;
616 min_low = reduce_list->pixels_low;
617 p_tree = &(reduce_list->next_reduceable);
618
619 while ((tree = *p_tree) != NULL)
620 {
621 flag = 1;
622 for (i=0; i < 8; i++)
623 {
624 sub_tree=tree->sub[i];
625 if (sub_tree != NULL)
626 { if (sub_tree->leaf == 0) {flag = 0;} }
627 }
628 if (flag == 1)
629 {
630 if ((tree->pixels_high < min_high) ||
631 ((tree->pixels_high == min_high) &&
632 (tree->pixels_low < min_low)))
633 {
634 p_min = p_tree;
635 min_high=tree->pixels_high;
636 min_low=tree->pixels_low;
637 }
638 }
639 p_tree=&(tree->next_reduceable);
640 }
641
642 tree = *p_min;
643 *p_min=tree->next_reduceable;
644 tree->leaf = 1;
645 octree_size = octree_size - tree->sub_count + 1;
646 depth = tree->level;
647 (reduce_count[depth])++;
648 }
649
650 /************************************************************************
651 * norm_tree *
652 ************************************************************************/
653
norm_tree(OCTREE tree)654 static void norm_tree(OCTREE tree)
655 {
656 OCTREE subtree;
657 int i;
658
659 tree_count++;
660
661 while (tree->pixels_low >= BIGVAL)
662 {
663 tree->pixels_low -= BIGVAL;
664 tree->pixels_high++;
665 }
666
667 while (tree->red_sum_low >= BIGVAL)
668 {
669 tree->red_sum_low -= BIGVAL;
670 tree->red_sum_high++;
671 }
672
673 while (tree->green_sum_low >= BIGVAL)
674 {
675 tree->green_sum_low -= BIGVAL;
676 tree->green_sum_high++;
677 }
678
679 while (tree->blue_sum_low >= BIGVAL)
680 {
681 tree->blue_sum_low -= BIGVAL;
682 tree->blue_sum_high++;
683 }
684
685 if (tree->leaf == FALSE && tree->level < leaf_level)
686 {
687 for (i=0; i < 8; i++)
688 {
689 subtree=tree->sub[i];
690 if (subtree != NULL)
691 norm_tree(subtree);
692 }
693 }
694 }
695
696
697 /*** - FIN - ****************************************************************/
698