|
265
|
1 /* Image processing functions
|
|
|
2 Copyright (C) 1998 Jareth Hein
|
|
|
3
|
|
|
4 This file is a part of XEmacs
|
|
|
5
|
|
|
6 XEmacs is free software; you can redistribute it and/or modify it
|
|
|
7 under the terms of the GNU General Public License as published by the
|
|
|
8 Free Software Foundation; either version 2, or (at your option) any
|
|
|
9 later version.
|
|
|
10
|
|
|
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
|
|
|
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with XEmacs; see the file COPYING. If not, write to
|
|
|
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
|
|
|
19 Boston, MA 02111-1307, USA. */
|
|
|
20
|
|
|
21 /* Synched up with: Not in FSF. */
|
|
|
22
|
|
|
23 /* Original author: Jareth Hein */
|
|
|
24
|
|
|
25 /* Parts of this file are based on code from Sam Leffler's tiff library,
|
|
|
26 with the original copywrite displayed here:
|
|
|
27
|
|
|
28 Copyright (c) 1988-1997 Sam Leffler
|
|
|
29 Copyright (c) 1991-1997 Silicon Graphics, Inc.
|
|
|
30
|
|
|
31 Permission to use, copy, modify, distribute, and sell this software and
|
|
|
32 its documentation for any purpose is hereby granted without fee, provided
|
|
|
33 that (i) the above copyright notices and this permission notice appear in
|
|
|
34 all copies of the software and related documentation, and (ii) the names of
|
|
|
35 Sam Leffler and Silicon Graphics may not be used in any advertising or
|
|
|
36 publicity relating to the software without the specific, prior written
|
|
|
37 permission of Sam Leffler and Silicon Graphics. */
|
|
|
38
|
|
|
39 /* Quantizing code based off of the paper
|
|
|
40 Color Image Quantization for Frame Buffer Display, Paul Heckbert,
|
|
|
41 Siggraph '82 proceedings, pp. 297-307 */
|
|
|
42
|
|
267
|
43 #include <config.h>
|
|
265
|
44 #include "lisp.h"
|
|
|
45 #include "imgproc.h"
|
|
|
46
|
|
|
47 static void get_histogram(quant_table *qt, unsigned char *pic,
|
|
|
48 int width, int height, Colorbox* box)
|
|
|
49 {
|
|
|
50 register unsigned char *inptr;
|
|
|
51 register int red, green, blue;
|
|
|
52 register unsigned int j, i;
|
|
|
53
|
|
|
54 box->rmin = box->gmin = box->bmin = 999;
|
|
|
55 box->rmax = box->gmax = box->bmax = -1;
|
|
|
56 box->total = width * height;
|
|
|
57
|
|
|
58 {
|
|
|
59 register int *ptr = &(qt->histogram[0][0][0]);
|
|
|
60 for (i = B_LEN*B_LEN*B_LEN; i-- > 0;)
|
|
|
61 *ptr++ = 0;
|
|
|
62 }
|
|
|
63 inptr = pic;
|
|
|
64 for (i = 0; i < height; i++) {
|
|
|
65 for (j = width; j-- > 0;) {
|
|
|
66 red = *inptr++ >> COLOR_SHIFT;
|
|
|
67 green = *inptr++ >> COLOR_SHIFT;
|
|
|
68 blue = *inptr++ >> COLOR_SHIFT;
|
|
|
69 if (red < box->rmin)
|
|
|
70 box->rmin = red;
|
|
|
71 if (red > box->rmax)
|
|
|
72 box->rmax = red;
|
|
|
73 if (green < box->gmin)
|
|
|
74 box->gmin = green;
|
|
|
75 if (green > box->gmax)
|
|
|
76 box->gmax = green;
|
|
|
77 if (blue < box->bmin)
|
|
|
78 box->bmin = blue;
|
|
|
79 if (blue > box->bmax)
|
|
|
80 box->bmax = blue;
|
|
|
81 qt->histogram[red][green][blue]++;
|
|
|
82 }
|
|
|
83 }
|
|
|
84 }
|
|
|
85
|
|
|
86 static Colorbox *
|
|
|
87 largest_box(quant_table *qt)
|
|
|
88 {
|
|
|
89 register Colorbox *p, *b;
|
|
|
90 register int size;
|
|
|
91
|
|
|
92 b = NULL;
|
|
|
93 size = -1;
|
|
|
94 for (p = qt->usedboxes; p != NULL; p = p->next)
|
|
|
95 if ((p->rmax > p->rmin || p->gmax > p->gmin ||
|
|
|
96 p->bmax > p->bmin) && p->total > size)
|
|
|
97 size = (b = p)->total;
|
|
|
98 return (b);
|
|
|
99 }
|
|
|
100
|
|
|
101 static void
|
|
|
102 shrinkbox(quant_table *qt, Colorbox* box)
|
|
|
103 {
|
|
|
104 register int *histp, ir, ig, ib;
|
|
|
105
|
|
|
106 if (box->rmax > box->rmin) {
|
|
|
107 for (ir = box->rmin; ir <= box->rmax; ++ir)
|
|
|
108 for (ig = box->gmin; ig <= box->gmax; ++ig) {
|
|
|
109 histp = &(qt->histogram[ir][ig][box->bmin]);
|
|
|
110 for (ib = box->bmin; ib <= box->bmax; ++ib)
|
|
|
111 if (*histp++ != 0) {
|
|
|
112 box->rmin = ir;
|
|
|
113 goto have_rmin;
|
|
|
114 }
|
|
|
115 }
|
|
|
116 have_rmin:
|
|
|
117 if (box->rmax > box->rmin)
|
|
|
118 for (ir = box->rmax; ir >= box->rmin; --ir)
|
|
|
119 for (ig = box->gmin; ig <= box->gmax; ++ig) {
|
|
|
120 histp = &(qt->histogram[ir][ig][box->bmin]);
|
|
|
121 ib = box->bmin;
|
|
|
122 for (; ib <= box->bmax; ++ib)
|
|
|
123 if (*histp++ != 0) {
|
|
|
124 box->rmax = ir;
|
|
|
125 goto have_rmax;
|
|
|
126 }
|
|
|
127 }
|
|
|
128 }
|
|
|
129 have_rmax:
|
|
|
130 if (box->gmax > box->gmin) {
|
|
|
131 for (ig = box->gmin; ig <= box->gmax; ++ig)
|
|
|
132 for (ir = box->rmin; ir <= box->rmax; ++ir) {
|
|
|
133 histp = &(qt->histogram[ir][ig][box->bmin]);
|
|
|
134 for (ib = box->bmin; ib <= box->bmax; ++ib)
|
|
|
135 if (*histp++ != 0) {
|
|
|
136 box->gmin = ig;
|
|
|
137 goto have_gmin;
|
|
|
138 }
|
|
|
139 }
|
|
|
140 have_gmin:
|
|
|
141 if (box->gmax > box->gmin)
|
|
|
142 for (ig = box->gmax; ig >= box->gmin; --ig)
|
|
|
143 for (ir = box->rmin; ir <= box->rmax; ++ir) {
|
|
|
144 histp = &(qt->histogram[ir][ig][box->bmin]);
|
|
|
145 ib = box->bmin;
|
|
|
146 for (; ib <= box->bmax; ++ib)
|
|
|
147 if (*histp++ != 0) {
|
|
|
148 box->gmax = ig;
|
|
|
149 goto have_gmax;
|
|
|
150 }
|
|
|
151 }
|
|
|
152 }
|
|
|
153 have_gmax:
|
|
|
154 if (box->bmax > box->bmin) {
|
|
|
155 for (ib = box->bmin; ib <= box->bmax; ++ib)
|
|
|
156 for (ir = box->rmin; ir <= box->rmax; ++ir) {
|
|
|
157 histp = &(qt->histogram[ir][box->gmin][ib]);
|
|
|
158 for (ig = box->gmin; ig <= box->gmax; ++ig) {
|
|
|
159 if (*histp != 0) {
|
|
|
160 box->bmin = ib;
|
|
|
161 goto have_bmin;
|
|
|
162 }
|
|
|
163 histp += B_LEN;
|
|
|
164 }
|
|
|
165 }
|
|
|
166 have_bmin:
|
|
|
167 if (box->bmax > box->bmin)
|
|
|
168 for (ib = box->bmax; ib >= box->bmin; --ib)
|
|
|
169 for (ir = box->rmin; ir <= box->rmax; ++ir) {
|
|
|
170 histp = &(qt->histogram[ir][box->gmin][ib]);
|
|
|
171 ig = box->gmin;
|
|
|
172 for (; ig <= box->gmax; ++ig) {
|
|
|
173 if (*histp != 0) {
|
|
|
174 box->bmax = ib;
|
|
|
175 goto have_bmax;
|
|
|
176 }
|
|
|
177 histp += B_LEN;
|
|
|
178 }
|
|
|
179 }
|
|
|
180 }
|
|
|
181 have_bmax:
|
|
|
182 ;
|
|
|
183 }
|
|
|
184
|
|
|
185 static void
|
|
|
186 splitbox(quant_table *qt, Colorbox* ptr)
|
|
|
187 {
|
|
|
188 int hist2[B_LEN];
|
|
|
189 int first, last;
|
|
|
190 register Colorbox *new;
|
|
|
191 register int *iptr, *histp;
|
|
|
192 register int i, j;
|
|
|
193 register int ir,ig,ib;
|
|
|
194 register int sum, sum1, sum2;
|
|
|
195 enum { RED, GREEN, BLUE } axis;
|
|
|
196
|
|
|
197 /*
|
|
|
198 * See which axis is the largest, do a histogram along that
|
|
|
199 * axis. Split at median point. Contract both new boxes to
|
|
|
200 * fit points and return
|
|
|
201 */
|
|
|
202 i = ptr->rmax - ptr->rmin;
|
|
|
203 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
|
|
|
204 axis = RED;
|
|
|
205 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
|
|
|
206 axis = GREEN;
|
|
|
207 else
|
|
|
208 axis = BLUE;
|
|
|
209 /* get histogram along longest axis */
|
|
|
210 switch (axis) {
|
|
|
211 case RED:
|
|
|
212 histp = &hist2[ptr->rmin];
|
|
|
213 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
|
|
|
214 *histp = 0;
|
|
|
215 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
|
|
|
216 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
|
|
|
217 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
|
|
|
218 *histp += *iptr++;
|
|
|
219 }
|
|
|
220 histp++;
|
|
|
221 }
|
|
|
222 first = ptr->rmin;
|
|
|
223 last = ptr->rmax;
|
|
|
224 break;
|
|
|
225 case GREEN:
|
|
|
226 histp = &hist2[ptr->gmin];
|
|
|
227 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
|
|
|
228 *histp = 0;
|
|
|
229 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
|
|
|
230 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
|
|
|
231 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
|
|
|
232 *histp += *iptr++;
|
|
|
233 }
|
|
|
234 histp++;
|
|
|
235 }
|
|
|
236 first = ptr->gmin;
|
|
|
237 last = ptr->gmax;
|
|
|
238 break;
|
|
|
239 case BLUE:
|
|
|
240 histp = &hist2[ptr->bmin];
|
|
|
241 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
|
|
|
242 *histp = 0;
|
|
|
243 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
|
|
|
244 iptr = &(qt->histogram[ir][ptr->gmin][ib]);
|
|
|
245 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
|
|
|
246 *histp += *iptr;
|
|
|
247 iptr += B_LEN;
|
|
|
248 }
|
|
|
249 }
|
|
|
250 histp++;
|
|
|
251 }
|
|
|
252 first = ptr->bmin;
|
|
|
253 last = ptr->bmax;
|
|
|
254 break;
|
|
|
255 }
|
|
|
256 /* find median point */
|
|
|
257 sum2 = ptr->total / 2;
|
|
|
258 histp = &hist2[first];
|
|
|
259 sum = 0;
|
|
|
260 for (i = first; i <= last && (sum += *histp++) < sum2; ++i)
|
|
|
261 ;
|
|
|
262 if (i == first)
|
|
|
263 i++;
|
|
|
264
|
|
|
265 /* Create new box, re-allocate points */
|
|
|
266 new = qt->freeboxes;
|
|
|
267 qt->freeboxes = new->next;
|
|
|
268 if (qt->freeboxes)
|
|
|
269 qt->freeboxes->prev = NULL;
|
|
|
270 if (qt->usedboxes)
|
|
|
271 qt->usedboxes->prev = new;
|
|
|
272 new->next = qt->usedboxes;
|
|
|
273 qt->usedboxes = new;
|
|
|
274
|
|
|
275 histp = &hist2[first];
|
|
|
276 for (sum1 = 0, j = first; j < i; j++)
|
|
|
277 sum1 += *histp++;
|
|
|
278 for (sum2 = 0, j = i; j <= last; j++)
|
|
|
279 sum2 += *histp++;
|
|
|
280 new->total = sum1;
|
|
|
281 ptr->total = sum2;
|
|
|
282
|
|
|
283 new->rmin = ptr->rmin;
|
|
|
284 new->rmax = ptr->rmax;
|
|
|
285 new->gmin = ptr->gmin;
|
|
|
286 new->gmax = ptr->gmax;
|
|
|
287 new->bmin = ptr->bmin;
|
|
|
288 new->bmax = ptr->bmax;
|
|
|
289 switch (axis) {
|
|
|
290 case RED:
|
|
|
291 new->rmax = i-1;
|
|
|
292 ptr->rmin = i;
|
|
|
293 break;
|
|
|
294 case GREEN:
|
|
|
295 new->gmax = i-1;
|
|
|
296 ptr->gmin = i;
|
|
|
297 break;
|
|
|
298 case BLUE:
|
|
|
299 new->bmax = i-1;
|
|
|
300 ptr->bmin = i;
|
|
|
301 break;
|
|
|
302 }
|
|
|
303 shrinkbox(qt, new);
|
|
|
304 shrinkbox(qt, ptr);
|
|
|
305 }
|
|
|
306
|
|
|
307
|
|
|
308 static C_cell *
|
|
|
309 create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue)
|
|
|
310 {
|
|
|
311 register int ir, ig, ib, i;
|
|
|
312 register C_cell *ptr;
|
|
|
313 int mindist, next_n;
|
|
|
314 register int tmp, dist, n;
|
|
|
315
|
|
|
316 ir = red >> (COLOR_DEPTH-C_DEPTH);
|
|
|
317 ig = green >> (COLOR_DEPTH-C_DEPTH);
|
|
|
318 ib = blue >> (COLOR_DEPTH-C_DEPTH);
|
|
|
319 ptr = (C_cell *)xmalloc(sizeof (C_cell));
|
|
|
320 *(qt->ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
|
|
|
321 ptr->num_ents = 0;
|
|
|
322
|
|
|
323 /*
|
|
|
324 * Step 1: find all colors inside this cell, while we're at
|
|
|
325 * it, find distance of centermost point to furthest corner
|
|
|
326 */
|
|
|
327 mindist = 99999999;
|
|
|
328 for (i = 0; i < num_colors; ++i) {
|
|
|
329 if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir ||
|
|
|
330 qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig ||
|
|
|
331 qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
|
|
|
332 continue;
|
|
|
333 ptr->entries[ptr->num_ents][0] = i;
|
|
|
334 ptr->entries[ptr->num_ents][1] = 0;
|
|
|
335 ++ptr->num_ents;
|
|
|
336 tmp = qt->rm[i] - red;
|
|
|
337 if (tmp < (MAX_COLOR/C_LEN/2))
|
|
|
338 tmp = MAX_COLOR/C_LEN-1 - tmp;
|
|
|
339 dist = tmp*tmp;
|
|
|
340 tmp = qt->gm[i] - green;
|
|
|
341 if (tmp < (MAX_COLOR/C_LEN/2))
|
|
|
342 tmp = MAX_COLOR/C_LEN-1 - tmp;
|
|
|
343 dist += tmp*tmp;
|
|
|
344 tmp = qt->bm[i] - blue;
|
|
|
345 if (tmp < (MAX_COLOR/C_LEN/2))
|
|
|
346 tmp = MAX_COLOR/C_LEN-1 - tmp;
|
|
|
347 dist += tmp*tmp;
|
|
|
348 if (dist < mindist)
|
|
|
349 mindist = dist;
|
|
|
350 }
|
|
|
351
|
|
|
352 /*
|
|
|
353 * Step 3: find all points within that distance to cell.
|
|
|
354 */
|
|
|
355 for (i = 0; i < num_colors; ++i) {
|
|
|
356 if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir &&
|
|
|
357 qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig &&
|
|
|
358 qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
|
|
|
359 continue;
|
|
|
360 dist = 0;
|
|
|
361 if ((tmp = red - qt->rm[i]) > 0 ||
|
|
|
362 (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
|
|
|
363 dist += tmp*tmp;
|
|
|
364 if ((tmp = green - qt->gm[i]) > 0 ||
|
|
|
365 (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
|
|
|
366 dist += tmp*tmp;
|
|
|
367 if ((tmp = blue - qt->bm[i]) > 0 ||
|
|
|
368 (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 )
|
|
|
369 dist += tmp*tmp;
|
|
|
370 if (dist < mindist) {
|
|
|
371 ptr->entries[ptr->num_ents][0] = i;
|
|
|
372 ptr->entries[ptr->num_ents][1] = dist;
|
|
|
373 ++ptr->num_ents;
|
|
|
374 }
|
|
|
375 }
|
|
|
376
|
|
|
377 /*
|
|
|
378 * Sort color cells by distance, use cheap exchange sort
|
|
|
379 */
|
|
|
380 for (n = ptr->num_ents - 1; n > 0; n = next_n) {
|
|
|
381 next_n = 0;
|
|
|
382 for (i = 0; i < n; ++i)
|
|
|
383 if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
|
|
|
384 tmp = ptr->entries[i][0];
|
|
|
385 ptr->entries[i][0] = ptr->entries[i+1][0];
|
|
|
386 ptr->entries[i+1][0] = tmp;
|
|
|
387 tmp = ptr->entries[i][1];
|
|
|
388 ptr->entries[i][1] = ptr->entries[i+1][1];
|
|
|
389 ptr->entries[i+1][1] = tmp;
|
|
|
390 next_n = i;
|
|
|
391 }
|
|
|
392 }
|
|
|
393 return (ptr);
|
|
|
394 }
|
|
|
395
|
|
|
396 static int
|
|
|
397 map_colortable(quant_table *qt, int num_colors)
|
|
|
398 {
|
|
|
399 register int *histp = &(qt->histogram[0][0][0]);
|
|
|
400 register C_cell *cell;
|
|
|
401 register int j, tmp, d2, dist;
|
|
|
402 int ir, ig, ib, i;
|
|
|
403
|
|
|
404 for (ir = 0; ir < B_LEN; ++ir)
|
|
|
405 for (ig = 0; ig < B_LEN; ++ig)
|
|
|
406 for (ib = 0; ib < B_LEN; ++ib, histp++) {
|
|
|
407 if (*histp == 0) {
|
|
|
408 *histp = -1;
|
|
|
409 continue;
|
|
|
410 }
|
|
|
411 cell = *(qt->ColorCells +
|
|
|
412 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
|
|
|
413 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
|
|
|
414 (ib>>(B_DEPTH-C_DEPTH))));
|
|
|
415 if (cell == NULL )
|
|
|
416 cell = create_colorcell(qt, num_colors,
|
|
|
417 ir << COLOR_SHIFT,
|
|
|
418 ig << COLOR_SHIFT,
|
|
|
419 ib << COLOR_SHIFT);
|
|
|
420 if (cell == NULL) /* memory exhausted! punt! */
|
|
|
421 return -1;
|
|
|
422 dist = 9999999;
|
|
|
423 for (i = 0; i < cell->num_ents &&
|
|
|
424 dist > cell->entries[i][1]; ++i) {
|
|
|
425 j = cell->entries[i][0];
|
|
|
426 d2 = qt->rm[j] - (ir << COLOR_SHIFT);
|
|
|
427 d2 *= d2;
|
|
|
428 tmp = qt->gm[j] - (ig << COLOR_SHIFT);
|
|
|
429 d2 += tmp*tmp;
|
|
|
430 tmp = qt->bm[j] - (ib << COLOR_SHIFT);
|
|
|
431 d2 += tmp*tmp;
|
|
|
432 if (d2 < dist) {
|
|
|
433 dist = d2;
|
|
|
434 *histp = j;
|
|
|
435 }
|
|
|
436 }
|
|
|
437 }
|
|
|
438 return 0;
|
|
|
439 }
|
|
|
440
|
|
|
441 quant_table *EImage_build_quantable(unsigned char *eimage, int width, int height, int num_colors)
|
|
|
442 {
|
|
|
443 quant_table *qt;
|
|
|
444 Colorbox *box_list, *ptr;
|
|
|
445 int i,res;
|
|
|
446
|
|
|
447 qt = (quant_table*)xmalloc(sizeof(quant_table));
|
|
|
448 if (qt == NULL) return NULL;
|
|
|
449
|
|
|
450 assert (num_colors < 257 && num_colors > 2);
|
|
|
451 /*
|
|
|
452 * STEP 1: create empty boxes
|
|
|
453 */
|
|
|
454 qt->usedboxes = NULL;
|
|
|
455 box_list = qt->freeboxes = (Colorbox *)xmalloc(num_colors*sizeof (Colorbox));
|
|
|
456 qt->freeboxes[0].next = &(qt->freeboxes[1]);
|
|
|
457 qt->freeboxes[0].prev = NULL;
|
|
|
458 for (i = 1; i < num_colors-1; ++i) {
|
|
|
459 qt->freeboxes[i].next = &(qt->freeboxes[i+1]);
|
|
|
460 qt->freeboxes[i].prev = &(qt->freeboxes[i-1]);
|
|
|
461 }
|
|
|
462 qt->freeboxes[num_colors-1].next = NULL;
|
|
|
463 qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]);
|
|
|
464
|
|
|
465 /*
|
|
|
466 * STEP 2: get histogram, initialize first box
|
|
|
467 */
|
|
|
468 ptr = qt->freeboxes;
|
|
|
469 qt->freeboxes = ptr->next;
|
|
|
470 if (qt->freeboxes)
|
|
|
471 qt->freeboxes->prev = NULL;
|
|
|
472 ptr->next = qt->usedboxes;
|
|
|
473 qt->usedboxes = ptr;
|
|
|
474 if (ptr->next)
|
|
|
475 ptr->next->prev = ptr;
|
|
|
476 get_histogram(qt, eimage, width, height, ptr);
|
|
|
477
|
|
|
478 /*
|
|
|
479 * STEP 3: continually subdivide boxes until no more free
|
|
|
480 * boxes remain or until all colors assigned.
|
|
|
481 */
|
|
|
482 while (qt->freeboxes != NULL) {
|
|
|
483 ptr = largest_box(qt);
|
|
|
484 if (ptr != NULL)
|
|
|
485 splitbox(qt, ptr);
|
|
|
486 else
|
|
|
487 qt->freeboxes = NULL;
|
|
|
488 }
|
|
|
489
|
|
|
490 /*
|
|
|
491 * STEP 4: assign colors to all boxes
|
|
|
492 */
|
|
|
493 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
|
|
|
494 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
|
|
|
495 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
|
|
|
496 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
|
|
|
497 qt->um[i] = ptr->total;
|
|
|
498 }
|
|
|
499 qt->num_active_colors = i;
|
|
|
500
|
|
|
501 /* We're done with the boxes now */
|
|
|
502 xfree(box_list);
|
|
|
503 qt->freeboxes = qt->usedboxes = NULL;
|
|
|
504
|
|
|
505 /*
|
|
|
506 * STEP 5: scan histogram and map all values to closest color
|
|
|
507 */
|
|
|
508 /* 5a: create cell list as described in Heckbert */
|
|
|
509 qt->ColorCells = (C_cell **)xmalloc(C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
|
|
|
510 memset(qt->ColorCells, 0, C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
|
|
|
511 /* 5b: create mapping from truncated pixel space to color
|
|
|
512 table entries */
|
|
|
513 res = map_colortable(qt, num_colors);
|
|
|
514
|
|
|
515 /* 5c: done with ColorCells */
|
|
|
516 for (i = 0; i < C_LEN*C_LEN*C_LEN; i++) if (qt->ColorCells[i]) xfree(qt->ColorCells[i]);
|
|
|
517 xfree(qt->ColorCells);
|
|
|
518
|
|
|
519 if (res) {
|
|
|
520 /* we failed in memory allocation, so clean up an leave */
|
|
|
521 xfree(qt);
|
|
|
522 return NULL;
|
|
|
523 }
|
|
|
524
|
|
|
525 return qt;
|
|
|
526 }
|
