source: golgotha/src/i4/quantize/median.cc @ 80

Last change on this file since 80 was 80, checked in by Sam Hocevar, 12 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 5.8 KB
Line 
1/********************************************************************** <BR>
2  This file is part of Crack dot Com's free source code release of
3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for
4  information about compiling & licensing issues visit this URL</a>
5  <PRE> If that doesn't help, contact Jonathan Clark at
6  golgotha_source@usa.net (Subject should have "GOLG" in it)
7***********************************************************************/
8
9#include "arch.hh"
10#include "quantize/median.hh"
11#include "quantize/histogram.hh"
12#include <stdlib.h>
13#include "memory/malloc.hh"
14
15// counts for each color, global so that it can be accessed by qsort function
16static w32 *counts;   
17
18
19static int red_compare(const void *a, const void *b)
20{
21  w16 color1=counts[*((w16 *)a)],
22      color2=counts[*((w16 *)b)];
23
24  return ((sw32) ((color1 & (  (1 | 2 | 4 | 8 | 16) << 11))>>11))-
25    ((sw32) ((color2 & (  (1 | 2 | 4 | 8 | 16) << 11))>>11));
26}
27
28
29static int green_compare(const void *a, const void *b)
30{
31  w16 color1=counts[*((w16 *)a)],
32      color2=counts[*((w16 *)b)];
33
34  return ((sw32) (color1 & (  (1 | 2 | 4 | 8 | 16 | 32) << 5)))-
35         ((sw32) (color2 & (  (1 | 2 | 4 | 8 | 16 | 32) << 5)));
36}
37
38
39static int blue_compare(const void *a, const void *b)
40{
41  w16 color1=counts[*((w16 *)a)],
42      color2=counts[*((w16 *)b)];
43
44  return ((sw32) (color1 & (  (1 | 2 | 4 | 8 | 16) << 0)))-
45         ((sw32) (color2 & (  (1 | 2 | 4 | 8 | 16) << 0)));
46}
47
48
49struct box
50{
51  w32 index;
52  w32 colors;
53  w32 sum;
54};
55
56static int box_compare(const void *a, const void *b)
57{
58  return ((box *)b)->sum-((box *)a)->sum;
59}
60
61inline void _16_to_rgb(w32 rgb, w8 &r, w8 &g, w8 &b)
62{
63  b=(rgb & (1 | 2 | 4 | 8 | 16))<<3;
64  rgb>>=5;
65
66  g=(rgb & (1 | 2 | 4 | 8 | 16 | 32))<<2;
67  rgb>>=6;
68
69  r=(rgb & (1 | 2 | 4 | 8 | 16))<<3;
70}
71
72void i4_median_cut(i4_histogram_class *hist,
73                   w32 skip_colors,
74                   w32 t_colors,
75                   w32 *return_palette)
76                                 
77{
78  enum { HIST_SIZE=0x10000,  // 16 bit histogram table
79         MAX_COLORS=256 };
80 
81  counts=hist->counts;
82
83  box *box_list=(box *)i4_malloc(sizeof(box) * MAX_COLORS, "boxes");
84
85  // setup the initial box
86  w32 total_boxes    = 1;
87  box_list[0].index  = 0;
88  box_list[0].colors = hist->tcolors;
89  box_list[0].sum    = hist->total_pixels;
90
91  w32 box_index;
92  w32 loop_count;
93
94  // split boxes until we have all the colors
95  while ( total_boxes < t_colors-skip_colors )
96  {
97    // Find the first splittable box.
98    for ( box_index = 0; box_index < total_boxes; ++box_index )
99      if (box_list[box_index].colors >= 2)
100        break;
101
102    if ( box_index == total_boxes)
103      break;    /* ran out of colors! */
104
105
106    w32 start = box_list[box_index].index;
107    w32 end   = start + box_list[box_index].colors;
108
109    w8  min_r=0xff, max_r=0x00,
110        min_g=0xff, max_g=0x00,
111        min_b=0xff, max_b=0x00,
112        r,g,b;
113
114   
115    // now find the minimum and maximum r g b values for this box
116    for (loop_count = start; loop_count<end; loop_count++)
117    {
118      _16_to_rgb(hist->reference[loop_count],r,g,b);
119
120      if (r>max_r) max_r=r;
121      if (r<min_r) min_r=r;
122     
123      if (g>max_g) max_g=g;
124      if (g<min_g) min_g=g;
125
126      if (b>max_b) max_b=b;
127      if (b<min_b) min_b=b;
128    }
129
130
131    // Find the largest dimension, and sort by that component.
132    if (((max_r - min_r) >= (max_g - min_g)) && ((max_r - min_r) >= (max_b - min_b)))
133      qsort(hist->reference + start,
134          end-start,             // total elements to sort
135          sizeof(w16),
136          red_compare);
137    else if ( (max_g - min_g) >= (max_b - min_b) )
138      qsort(hist->reference + start,
139          end-start,             // total elements to sort
140          sizeof(w16),
141          green_compare);
142    else
143      qsort(hist->reference + start,
144          end-start,             // total elements to sort
145          sizeof(w16),
146          blue_compare);
147
148
149
150    // now find the division which closest divides into an equal number of pixels
151    w32 low_count= counts[hist->reference[start]];
152    w32 mid_number=box_list[box_index].sum/2;
153
154    for (loop_count = start+1; loop_count<end-1 && low_count<mid_number ; loop_count++)
155      low_count+=counts[hist->reference[loop_count]];
156
157
158    // now split the box
159    box_list[total_boxes].index  = loop_count;
160    box_list[total_boxes].colors = end-loop_count;
161    box_list[total_boxes].sum    = box_list[box_index].sum-low_count;
162    total_boxes++;
163
164    box_list[box_index].colors= loop_count-start;
165    box_list[box_index].sum   = low_count;
166
167    // sort to bring the biggest boxes to the top
168    qsort(box_list, total_boxes, sizeof(box), box_compare );   
169
170    /*    for (int z=0;z<total_boxes;z++)
171    {
172      printf("box #%d : index = %d, colors= %d, sum=%d\n",z,
173             box_list[z].index, box_list[z].colors, box_list[z].sum);
174    } */
175
176  }
177
178
179  // we should have 256 boxes, we now need to choose a color for each box
180  // we do this by averaging all the colors within the box
181  w32 r_tot, g_tot, b_tot;
182  for (box_index = 0; box_index<total_boxes-skip_colors; box_index++)
183  {
184    r_tot = g_tot = b_tot = 0;
185
186    w32 start = box_list[box_index].index;
187    w32 end   = start + box_list[box_index].colors;
188
189    w8 r,g,b;
190    for (loop_count = start; loop_count < end; loop_count++)
191    {
192      _16_to_rgb(hist->reference[loop_count],r,g,b);
193     
194      r_tot+=r;
195      g_tot+=g;
196      b_tot+=b;
197    }
198
199    r_tot/=(end-start);
200    g_tot/=(end-start);
201    b_tot/=(end-start);
202
203    return_palette[box_index+skip_colors] = (r_tot<<16)|
204      (g_tot<<8) |
205      b_tot;
206  }
207
208  for (;box_index + skip_colors<t_colors; box_index++)
209    return_palette[box_index+skip_colors] = 0;
210
211
212  i4_free(box_list);
213
214}
215
Note: See TracBrowser for help on using the repository browser.