Mercurial > hg > xemacs-beta

comparison src/imgproc.c @ 265:8efd647ea9ca r20-5b31

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r20-5b31
author cvs
date Mon, 13 Aug 2007 10:25:37 +0200
parents
children 966663fcf606
comparison
equal deleted inserted replaced
264:682d2a9d41a5 265:8efd647ea9ca
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
43 #include "config.h"
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 }