source: trunk/JPGPROC/source/gbmsrc/gbmmcut.c@ 41

Last change on this file since 41 was 2, checked in by stevenhl, 8 years ago

Import sources from cwmm-full.zip dated 2005-03-21
File size: 8.0 KB
Line 
1/*
2
3gbmmcut.c - Median Cut colour reductions
4
5*/
6
7/*...sincludes:0:*/
8#include <stdio.h>
9#include <stddef.h>
10#include <stdlib.h>
11#include <string.h>
12#include "gbm.h"
13
14/*...vgbm\46\h:0:*/
15/*...e*/
16
17#define DIV_R 4
18#define DIV_G 2
19#define DIV_B 1
20
21typedef struct
22 {
23 dword freq;
24 byte r0,r1,g0,g1,b0,b1;
25 byte dividable;
26 } CELL;
27
28typedef struct
29 {
30 dword freqs[0x20][0x20][0x20]; /* 128Kb */
31 dword total;
32 int n_cells;
33 CELL cells[0x100];
34 } GBMMCUT;
35
36/*...sgbm_create_mcut \45\ create empty mcut:0:*/
37GBMMCUT *gbm_create_mcut(void)
38 {
39 GBMMCUT *mcut;
40
41 if ( (mcut = malloc((size_t) sizeof(GBMMCUT))) == NULL )
42 return NULL;
43
44 memset(mcut->freqs, 0x00, sizeof(mcut->freqs));
45 mcut->total = 0;
46 return mcut;
47 }
48/*...e*/
49/*...sgbm_delete_mcut \45\ delete mcut:0:*/
50void gbm_delete_mcut(GBMMCUT *mcut)
51 {
52 free(mcut);
53 }
54/*...e*/
55/*...sgbm_add_to_mcut \45\ add statistics from file data:0:*/
56void gbm_add_to_mcut(
57 GBMMCUT *mcut,
58 const GBM *gbm, const byte *data24
59 )
60 {
61 int stride24 = ((gbm->w * 3 + 3) & ~3);
62 int step24 = stride24 - gbm->w * 3;
63 int x, y;
64
65 for ( y = 0; y < gbm->h; y++, data24 += step24 )
66 for ( x = 0; x < gbm->w; x++ )
67 {
68 byte b = (byte) (*data24++ >> 3);
69 byte g = (byte) (*data24++ >> 3);
70 byte r = (byte) (*data24++ >> 3);
71
72 ( mcut->freqs[b][g][r] )++;
73 }
74 mcut->total += ( gbm->w * gbm->h );
75 }
76/*...e*/
77/*...sgbm_pal_mcut \45\ build median palette via median cut:0:*/
78/*...sshrink:0:*/
79/* Apologies for use of 'goto'
80 In this case, its considered appropriate. */
81
82static void shrink(GBMMCUT *mcut, CELL *c)
83 {
84 byte r, g, b;
85
86 for ( ;; c->r0++ )
87 for ( g = c->g0; g < c->g1; g++ )
88 for ( b = c->b0; b < c->b1; b++ )
89 if ( mcut->freqs[b][g][c->r0] )
90 goto quit_r0;
91quit_r0:
92
93 for ( ; c->r1-c->r0 > 1; c->r1-- )
94 for ( g = c->g0; g < c->g1; g++ )
95 for ( b = c->b0; b < c->b1; b++ )
96 if ( mcut->freqs[b][g][c->r1-1] )
97 goto quit_r1;
98quit_r1:
99
100 for ( ;; c->g0++ )
101 for ( r = c->r0; r < c->r1; r++ )
102 for ( b = c->b0; b < c->b1; b++ )
103 if ( mcut->freqs[b][c->g0][r] )
104 goto quit_g0;
105quit_g0:
106
107 for ( ; c->g1-c->g0 > 1; c->g1-- )
108 for ( r = c->r0; r < c->r1; r++ )
109 for ( b = c->b0; b < c->b1; b++ )
110 if ( mcut->freqs[b][c->g1-1][r] )
111 goto quit_g1;
112quit_g1:
113
114 for ( ;; c->b0++ )
115 for ( r = c->r0; r < c->r1; r++ )
116 for ( g = c->g0; g < c->g1; g++ )
117 if ( mcut->freqs[c->b0][g][r] )
118 goto quit_b0;
119quit_b0:
120
121 for ( ; c->b1-c->b0 > 1; c->b1-- )
122 for ( r = c->r0; r < c->r1; r++ )
123 for ( g = c->g0; g < c->g1; g++ )
124 if ( mcut->freqs[c->b1-1][g][r] )
125 goto quit_b1;
126quit_b1:
127
128 c->dividable = ( ( c->r1-c->r0 > 1 ) ? DIV_R : 0 ) +
129 ( ( c->g1-c->g0 > 1 ) ? DIV_G : 0 ) +
130 ( ( c->b1-c->b0 > 1 ) ? DIV_B : 0 ) ;
131 }
132/*...e*/
133
134void gbm_pal_mcut(
135 GBMMCUT *mcut,
136 GBMRGB gbmrgb[],
137 int n_cols_wanted
138 )
139 {
140 CELL *c = mcut->cells;
141 int i, j;
142 byte reorder[0x100];
143
144 if ( n_cols_wanted > 0x100 )
145 n_cols_wanted = 0x100;
146
147 /* Initially, a single cell covers the whole colour cube */
148
149 c->r0 = c->g0 = c->b0 = 0;
150 c->r1 = c->g1 = c->b1 = 0x20;
151 c->freq = mcut->total;
152 shrink(mcut, c);
153 mcut->n_cells = 1;
154
155 /* Do the following until got as many colours (cells) as reqd. */
156
157 while ( mcut->n_cells < n_cols_wanted )
158 {
159 CELL *cmax = NULL;
160
161/*...sfind cell with most pixels in it\44\ that can be divided:16:*/
162{
163int j;
164dword freqmax = 1;
165
166for ( j = 0; j < mcut->n_cells; j++ )
167 if ( c[j].freq > freqmax && c[j].dividable )
168 {
169 cmax = &(c[j]);
170 freqmax = cmax->freq;
171 }
172}
173/*...e*/
174 if ( cmax == NULL )
175 break;
176
177 while ( cmax->dividable )
178 {
179 byte split;
180 CELL *cnew = &(c[mcut->n_cells]);
181
182/*...scalculate way to do the split:24:*/
183{
184int dr = (cmax->dividable&DIV_R) ? cmax->r1 - cmax->r0 : 0;
185int dg = (cmax->dividable&DIV_G) ? cmax->g1 - cmax->g0 : 0;
186int db = (cmax->dividable&DIV_B) ? cmax->b1 - cmax->b0 : 0;
187
188if ( dg >= dr && dg >= db )
189 split = DIV_G;
190else if ( dr >= db )
191 split = DIV_R;
192else
193 split = DIV_B;
194}
195/*...e*/
196 switch ( split )
197 {
198/*...sDIV_R:32:*/
199case DIV_R:
200 {
201 byte r, g, b;
202 dword slice, total = 0;
203
204 for ( r = cmax->r0; total < (cmax->freq>>1); r++ )
205 {
206 slice = 0;
207 for ( g = cmax->g0; g < cmax->g1; g++ )
208 for ( b = cmax->b0; b < cmax->b1; b++ )
209 slice += mcut->freqs[b][g][r];
210 total += slice;
211 }
212
213 if ( r == cmax->r1 && total > slice )
214 {
215 r--;
216 total -= slice;
217 }
218
219 cnew->r1 = cmax->r1;
220 cnew->r0 = cmax->r1 = r;
221 cnew->g0 = cmax->g0;
222 cnew->g1 = cmax->g1;
223 cnew->b0 = cmax->b0;
224 cnew->b1 = cmax->b1;
225 cnew->freq = cmax->freq - total;
226 cmax->freq = total;
227 }
228 break;
229/*...e*/
230/*...sDIV_G:32:*/
231case DIV_G:
232 {
233 byte r, g, b;
234 dword slice, total = 0;
235
236 for ( g = cmax->g0; total < (cmax->freq>>1); g++ )
237 {
238 slice = 0;
239 for ( r = cmax->r0; r < cmax->r1; r++ )
240 for ( b = cmax->b0; b < cmax->b1; b++ )
241 slice += mcut->freqs[b][g][r];
242 total += slice;
243 }
244
245 if ( g == cmax->g1 && total > slice )
246 {
247 g--;
248 total -= slice;
249 }
250
251 cnew->r0 = cmax->r0;
252 cnew->r1 = cmax->r1;
253 cnew->g1 = cmax->g1;
254 cnew->g0 = cmax->g1 = g;
255 cnew->b0 = cmax->b0;
256 cnew->b1 = cmax->b1;
257 cnew->freq = cmax->freq - total;
258 cmax->freq = total;
259 }
260 break;
261/*...e*/
262/*...sDIV_B:32:*/
263case DIV_B:
264 {
265 byte r, g, b;
266 dword slice, total = 0;
267
268 for ( b = cmax->b0; total < (cmax->freq>>1); b++ )
269 {
270 slice = 0;
271 for ( r = cmax->r0; r < cmax->r1; r++ )
272 for ( g = cmax->g0; g < cmax->g1; g++ )
273 slice += mcut->freqs[b][g][r];
274 total += slice;
275 }
276
277 if ( b == cmax->b1 && total > slice )
278 {
279 b--;
280 total -= slice;
281 }
282
283 cnew->r0 = cmax->r0;
284 cnew->r1 = cmax->r1;
285 cnew->g0 = cmax->g0;
286 cnew->g1 = cmax->g1;
287 cnew->b1 = cmax->b1;
288 cnew->b0 = cmax->b1 = b;
289 cnew->freq = cmax->freq - total;
290 cmax->freq = total;
291 }
292 break;
293/*...e*/
294 }
295 if ( cnew->freq > 0 )
296 {
297 mcut->n_cells++;
298 shrink(mcut, cmax);
299 shrink(mcut, cnew);
300 break;
301 }
302 cmax->dividable &= ~split;
303 }
304 }
305
306 /* I would like to return the palette sorted by frequency of use */
307 /* This isn't technically a requirement of this algorithm */
308 /* If I do though, it allows me to do other things afterwards */
309
310 for ( i = 0; i < mcut->n_cells; i++ )
311 reorder[i] = (byte) i;
312
313 for ( j = mcut->n_cells; j > 0; j-- )
314 {
315 BOOLEAN noswaps = TRUE;
316 for ( i = 0; i < j - 1; i++ )
317 if ( c[reorder[i]].freq < c[reorder[i+1]].freq )
318 {
319 byte t = reorder[i];
320 reorder[i] = reorder[i+1];
321 reorder[i+1] = t;
322 noswaps = FALSE;
323 }
324 if ( noswaps )
325 break;
326 }
327
328
329 /* Now set up the palette array passed in */
330 /* Note: ( ((x+y)/2) << 3 ) == ( (x+y) << 2 ) */
331 /* Also, label each point in the cell as being a member of that cell */
332
333 for ( i = 0; i < mcut->n_cells; i++ )
334 {
335 int inx = reorder[i];
336 byte r, g, b;
337
338 gbmrgb[i].r = ( (c[inx].r0 + c[inx].r1) << 2 );
339 gbmrgb[i].g = ( (c[inx].g0 + c[inx].g1) << 2 );
340 gbmrgb[i].b = ( (c[inx].b0 + c[inx].b1) << 2 );
341
342 for ( r = c[inx].r0; r < c[inx].r1; r++ )
343 for ( g = c[inx].g0; g < c[inx].g1; g++ )
344 for ( b = c[inx].b0; b < c[inx].b1; b++ )
345 mcut->freqs[b][g][r] = i;
346 }
347
348 /* Unused palette entries will be medium grey */
349 for ( ; i < 0x100; i++ )
350 {
351 gbmrgb[i].r = 0x80;
352 gbmrgb[i].g = 0x80;
353 gbmrgb[i].b = 0x80;
354 }
355 }
356/*...e*/
357/*...sgbm_map_mcut \45\ map to median cutted palette:0:*/
358void gbm_map_mcut(
359 GBMMCUT *mcut,
360 const GBM *gbm, const byte *data24, byte *data8
361 )
362 {
363 int stride24 = ((gbm->w * 3 + 3) & ~3);
364 int step24 = stride24 - gbm->w * 3;
365 int stride8 = ((gbm->w + 3) & ~3);
366 int step8 = stride8 - gbm->w;
367 int x, y;
368
369 /* Now transform the image data */
370
371 for ( y = 0; y < gbm->h; y++, data24 += step24, data8 += step8 )
372 for ( x = 0; x < gbm->w; x++ )
373 {
374 byte b = (*data24++ >> 3);
375 byte g = (*data24++ >> 3);
376 byte r = (*data24++ >> 3);
377
378 *data8++ = (byte) ( mcut->freqs[b][g][r] );
379 }
380 }
381/*...e*/
382/*...sgbm_mcut \45\ map single bitmap using median cut:0:*/
383BOOLEAN gbm_mcut(
384 const GBM *gbm, const byte *data24,
385 GBMRGB gbmrgb[],
386 byte *data8,
387 int n_cols_wanted
388 )
389 {
390 GBMMCUT *mcut;
391
392 if ( (mcut = gbm_create_mcut()) == NULL )
393 return FALSE;
394 gbm_add_to_mcut(mcut, gbm, data24);
395 gbm_pal_mcut(mcut, gbmrgb, n_cols_wanted);
396 gbm_map_mcut(mcut, gbm, data24, data8);
397 gbm_delete_mcut(mcut);
398 return TRUE;
399 }
400/*...e*/
Note: See TracBrowser for help on using the repository browser.