cgit.sxemacs.org Git - sxemacs/blob - src/ui/imgproc.c

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