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 #if defined(DEBUG_SXEMACS) && DEBUG_SXEMACS
  77                         if( red < 0 || green < 0 || blue < 0 ||
  78                             ! (red < B_LEN && green < B_LEN && blue < B_LEN) ) {
  79                                 abort();
  80                         } else
  81 #endif
  82                                 qt->histogram[red][green][blue]++;
  83                 }
  84         }
  85 }
  86
  87 static Colorbox *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 shrinkbox(quant_table * qt, Colorbox * box)
 102 {
 103         register int *histp, ir, ig, ib;
 104
 105         if (box->rmax > box->rmin) {
 106                 for (ir = box->rmin; ir <= box->rmax; ++ir)
 107                         for (ig = box->gmin; ig <= box->gmax; ++ig) {
 108                                 histp = &(qt->histogram[ir][ig][box->bmin]);
 109                                 for (ib = box->bmin; ib <= box->bmax; ++ib)
 110                                         if (*histp++ != 0) {
 111                                                 box->rmin = ir;
 112                                                 goto have_rmin;
 113                                         }
 114                         }
 115               have_rmin:
 116                 if (box->rmax > box->rmin)
 117                         for (ir = box->rmax; ir >= box->rmin; --ir)
 118                                 for (ig = box->gmin; ig <= box->gmax; ++ig) {
 119                                         histp =
 120                                             &(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 =
 145                                             &(qt->histogram[ir][ig][box->bmin]);
 146                                         ib = box->bmin;
 147                                         for (; ib <= box->bmax; ++ib)
 148                                                 if (*histp++ != 0) {
 149                                                         box->gmax = ig;
 150                                                         goto have_gmax;
 151                                                 }
 152                                 }
 153         }
 154       have_gmax:
 155         if (box->bmax > box->bmin) {
 156                 for (ib = box->bmin; ib <= box->bmax; ++ib)
 157                         for (ir = box->rmin; ir <= box->rmax; ++ir) {
 158                                 histp = &(qt->histogram[ir][box->gmin][ib]);
 159                                 for (ig = box->gmin; ig <= box->gmax; ++ig) {
 160                                         if (*histp != 0) {
 161                                                 box->bmin = ib;
 162                                                 goto have_bmin;
 163                                         }
 164                                         histp += B_LEN;
 165                                 }
 166                         }
 167               have_bmin:
 168                 if (box->bmax > box->bmin)
 169                         for (ib = box->bmax; ib >= box->bmin; --ib)
 170                                 for (ir = box->rmin; ir <= box->rmax; ++ir) {
 171                                         histp =
 172                                             &(qt->histogram[ir][box->gmin][ib]);
 173                                         ig = box->gmin;
 174                                         for (; ig <= box->gmax; ++ig) {
 175                                                 if (*histp != 0) {
 176                                                         box->bmax = ib;
 177                                                         goto have_bmax;
 178                                                 }
 179                                                 histp += B_LEN;
 180                                         }
 181                                 }
 182         }
 183       have_bmax:
 184         ;
 185 }
 186
 187 static void splitbox(quant_table * qt, Colorbox * ptr)
 188 {
 189         int hist2[B_LEN];
 190         int first = 0, last = 0;
 191         register Colorbox *new;
 192         register int *iptr, *histp;
 193         register int i, j;
 194         register int ir, ig, ib;
 195         register int sum, sum1, sum2;
 196         enum { RED, GREEN, BLUE } axis;
 197
 198         /*
 199          * See which axis is the largest, do a histogram along that
 200          * axis.  Split at median point.  Contract both new boxes to
 201          * fit points and return
 202          */
 203         i = ptr->rmax - ptr->rmin;
 204         if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
 205                 axis = RED;
 206         else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
 207                 axis = GREEN;
 208         else
 209                 axis = BLUE;
 210         /* get histogram along longest axis */
 211         switch (axis) {
 212         case RED:
 213                 histp = &hist2[ptr->rmin];
 214                 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
 215                         *histp = 0;
 216                         for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
 217                                 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
 218                                 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
 219                                         *histp += *iptr++;
 220                         }
 221                         histp++;
 222                 }
 223                 first = ptr->rmin;
 224                 last = ptr->rmax;
 225                 break;
 226         case GREEN:
 227                 histp = &hist2[ptr->gmin];
 228                 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
 229                         *histp = 0;
 230                         for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
 231                                 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
 232                                 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
 233                                         *histp += *iptr++;
 234                         }
 235                         histp++;
 236                 }
 237                 first = ptr->gmin;
 238                 last = ptr->gmax;
 239                 break;
 240         case BLUE:
 241                 histp = &hist2[ptr->bmin];
 242                 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
 243                         *histp = 0;
 244                         for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
 245                                 iptr = &(qt->histogram[ir][ptr->gmin][ib]);
 246                                 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
 247                                         *histp += *iptr;
 248                                         iptr += B_LEN;
 249                                 }
 250                         }
 251                         histp++;
 252                 }
 253                 first = ptr->bmin;
 254                 last = ptr->bmax;
 255                 break;
 256         default:
 257                 /* just crash */
 258                 abort();
 259                 break;
 260         }
 261         /* find median point */
 262         sum2 = ptr->total / 2;
 263         histp = &hist2[first];
 264         sum = 0;
 265         for (i = first; i <= last && (sum += *histp++) < sum2; ++i) ;
 266         if (i == first)
 267                 i++;
 268
 269         /* Create new box, re-allocate points */
 270         new = qt->freeboxes;
 271         qt->freeboxes = new->next;
 272         if (qt->freeboxes)
 273                 qt->freeboxes->prev = NULL;
 274         if (qt->usedboxes)
 275                 qt->usedboxes->prev = new;
 276         new->next = qt->usedboxes;
 277         qt->usedboxes = new;
 278
 279         histp = &hist2[first];
 280         for (sum1 = 0, j = first; j < i; j++)
 281                 sum1 += *histp++;
 282         for (sum2 = 0, j = i; j <= last; j++)
 283                 sum2 += *histp++;
 284         new->total = sum1;
 285         ptr->total = sum2;
 286
 287         new->rmin = ptr->rmin;
 288         new->rmax = ptr->rmax;
 289         new->gmin = ptr->gmin;
 290         new->gmax = ptr->gmax;
 291         new->bmin = ptr->bmin;
 292         new->bmax = ptr->bmax;
 293         switch (axis) {
 294         case RED:
 295                 new->rmax = i - 1;
 296                 ptr->rmin = i;
 297                 break;
 298         case GREEN:
 299                 new->gmax = i - 1;
 300                 ptr->gmin = i;
 301                 break;
 302         case BLUE:
 303                 new->bmax = i - 1;
 304                 ptr->bmin = i;
 305                 break;
 306         default:
 307                 /* just crash */
 308                 abort();
 309                 break;
 310         }
 311         shrinkbox(qt, new);
 312         shrinkbox(qt, ptr);
 313 }
 314
 315 static C_cell *create_colorcell(quant_table * qt, int num_colors, int red,
 316                                 int green, int blue)
 317 {
 318         register int ir, ig, ib, i;
 319         register C_cell *ptr;
 320         int mindist, next_n;
 321         register int tmp, dist, n;
 322
 323         ir = red >> (COLOR_DEPTH - C_DEPTH);
 324         ig = green >> (COLOR_DEPTH - C_DEPTH);
 325         ib = blue >> (COLOR_DEPTH - C_DEPTH);
 326         ptr = (C_cell *)xmalloc_atomic(sizeof(C_cell));
 327         *(qt->ColorCells + ir * C_LEN * C_LEN + ig * C_LEN + ib) = ptr;
 328         ptr->num_ents = 0;
 329
 330         /*
 331          * Step 1: find all colors inside this cell, while we're at
 332          *       it, find distance of centermost point to furthest corner
 333          */
 334         mindist = 99999999;
 335         for (i = 0; i < num_colors; ++i) {
 336                 if (qt->rm[i] >> (COLOR_DEPTH - C_DEPTH) != ir ||
 337                     qt->gm[i] >> (COLOR_DEPTH - C_DEPTH) != ig ||
 338                     qt->bm[i] >> (COLOR_DEPTH - C_DEPTH) != ib)
 339                         continue;
 340                 ptr->entries[ptr->num_ents][0] = i;
 341                 ptr->entries[ptr->num_ents][1] = 0;
 342                 ++ptr->num_ents;
 343                 tmp = qt->rm[i] - red;
 344                 if (tmp < (MAX_COLOR / C_LEN / 2))
 345                         tmp = MAX_COLOR / C_LEN - 1 - tmp;
 346                 dist = tmp * tmp;
 347                 tmp = qt->gm[i] - green;
 348                 if (tmp < (MAX_COLOR / C_LEN / 2))
 349                         tmp = MAX_COLOR / C_LEN - 1 - tmp;
 350                 dist += tmp * tmp;
 351                 tmp = qt->bm[i] - blue;
 352                 if (tmp < (MAX_COLOR / C_LEN / 2))
 353                         tmp = MAX_COLOR / C_LEN - 1 - tmp;
 354                 dist += tmp * tmp;
 355                 if (dist < mindist)
 356                         mindist = dist;
 357         }
 358
 359         /*
 360          * Step 3: find all points within that distance to cell.
 361          */
 362         for (i = 0; i < num_colors; ++i) {
 363                 if (qt->rm[i] >> (COLOR_DEPTH - C_DEPTH) == ir &&
 364                     qt->gm[i] >> (COLOR_DEPTH - C_DEPTH) == ig &&
 365                     qt->bm[i] >> (COLOR_DEPTH - C_DEPTH) == ib)
 366                         continue;
 367                 dist = 0;
 368                 if ((tmp = red - qt->rm[i]) > 0 ||
 369                     (tmp = qt->rm[i] - (red + MAX_COLOR / C_LEN - 1)) > 0)
 370                         dist += tmp * tmp;
 371                 if ((tmp = green - qt->gm[i]) > 0 ||
 372                     (tmp = qt->gm[i] - (green + MAX_COLOR / C_LEN - 1)) > 0)
 373                         dist += tmp * tmp;
 374                 if ((tmp = blue - qt->bm[i]) > 0 ||
 375                     (tmp = qt->bm[i] - (blue + MAX_COLOR / C_LEN - 1)) > 0)
 376                         dist += tmp * tmp;
 377                 if (dist < mindist) {
 378                         ptr->entries[ptr->num_ents][0] = i;
 379                         ptr->entries[ptr->num_ents][1] = dist;
 380                         ++ptr->num_ents;
 381                 }
 382         }
 383
 384         /*
 385          * Sort color cells by distance, use cheap exchange sort
 386          */
 387         for (n = ptr->num_ents - 1; n > 0; n = next_n) {
 388                 next_n = 0;
 389                 for (i = 0; i < n; ++i)
 390                         if (ptr->entries[i][1] > ptr->entries[i + 1][1]) {
 391                                 tmp = ptr->entries[i][0];
 392                                 ptr->entries[i][0] = ptr->entries[i + 1][0];
 393                                 ptr->entries[i + 1][0] = tmp;
 394                                 tmp = ptr->entries[i][1];
 395                                 ptr->entries[i][1] = ptr->entries[i + 1][1];
 396                                 ptr->entries[i + 1][1] = tmp;
 397                                 next_n = i;
 398                         }
 399         }
 400         return (ptr);
 401 }
 402
 403 static int map_colortable(quant_table * qt, int num_colors)
 404 {
 405         register int *histp = &(qt->histogram[0][0][0]);
 406         register C_cell *cell;
 407         register int j, tmp, d2, dist;
 408         int ir, ig, ib, i;
 409
 410         for (ir = 0; ir < B_LEN; ++ir)
 411                 for (ig = 0; ig < B_LEN; ++ig)
 412                         for (ib = 0; ib < B_LEN; ++ib, histp++) {
 413                                 if (*histp == 0) {
 414                                         *histp = -1;
 415                                         continue;
 416                                 }
 417                                 cell = *(qt->ColorCells +
 418                                          (((ir >> (B_DEPTH - C_DEPTH)) <<
 419                                            C_DEPTH * 2) +
 420                                           ((ig >> (B_DEPTH - C_DEPTH)) <<
 421                                            C_DEPTH) + (ib >> (B_DEPTH -
 422                                                               C_DEPTH))));
 423                                 if (cell == NULL)
 424                                         cell = create_colorcell(qt, num_colors,
 425                                                                 ir <<
 426                                                                 COLOR_SHIFT,
 427                                                                 ig <<
 428                                                                 COLOR_SHIFT,
 429                                                                 ib <<
 430                                                                 COLOR_SHIFT);
 431                                 if (cell == NULL)       /* memory exhausted! punt! */
 432                                         return -1;
 433                                 dist = 9999999;
 434                                 for (i = 0; i < cell->num_ents &&
 435                                      dist > cell->entries[i][1]; ++i) {
 436                                         j = cell->entries[i][0];
 437                                         d2 = qt->rm[j] - (ir << COLOR_SHIFT);
 438                                         d2 *= d2;
 439                                         tmp = qt->gm[j] - (ig << COLOR_SHIFT);
 440                                         d2 += tmp * tmp;
 441                                         tmp = qt->bm[j] - (ib << COLOR_SHIFT);
 442                                         d2 += tmp * tmp;
 443                                         if (d2 < dist) {
 444                                                 dist = d2;
 445                                                 *histp = j;
 446                                         }
 447                                 }
 448                         }
 449         return 0;
 450 }
 451
 452 quant_table *build_EImage_quantable(unsigned char *eimage, int width,
 453                                     int height, int num_colors)
 454 {
 455         quant_table *qt;
 456         Colorbox *box_list, *ptr;
 457         int i, res;
 458
 459         qt = (quant_table *)xmalloc_and_zero(sizeof(quant_table));
 460         if (qt == NULL)
 461                 return NULL;
 462
 463         assert(num_colors < 257 && num_colors > 2);
 464         /*
 465          * STEP 1:  create empty boxes
 466          */
 467         qt->usedboxes = NULL;
 468         box_list = qt->freeboxes = xnew_array(Colorbox, num_colors);
 469         qt->freeboxes[0].next = &(qt->freeboxes[1]);
 470         qt->freeboxes[0].prev = NULL;
 471         for (i = 1; i < num_colors - 1; ++i) {
 472                 qt->freeboxes[i].next = &(qt->freeboxes[i + 1]);
 473                 qt->freeboxes[i].prev = &(qt->freeboxes[i - 1]);
 474         }
 475         qt->freeboxes[num_colors - 1].next = NULL;
 476         qt->freeboxes[num_colors - 1].prev = &(qt->freeboxes[num_colors - 2]);
 477
 478         /*
 479          * STEP 2: get histogram, initialize first box
 480          */
 481         ptr = qt->freeboxes;
 482         qt->freeboxes = ptr->next;
 483         if (qt->freeboxes)
 484                 qt->freeboxes->prev = NULL;
 485         ptr->next = qt->usedboxes;
 486         qt->usedboxes = ptr;
 487         if (ptr->next)
 488                 ptr->next->prev = ptr;
 489         get_histogram(qt, eimage, width, height, ptr);
 490
 491         /*
 492          * STEP 3: continually subdivide boxes until no more free
 493          * boxes remain or until all colors assigned.
 494          */
 495         while (qt->freeboxes != NULL) {
 496                 ptr = largest_box(qt);
 497                 if (ptr != NULL)
 498                         splitbox(qt, ptr);
 499                 else
 500                         qt->freeboxes = NULL;
 501         }
 502
 503         /*
 504          * STEP 4: assign colors to all boxes
 505          */
 506         for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
 507                 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
 508                 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
 509                 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
 510                 qt->um[i] = ptr->total;
 511         }
 512         qt->num_active_colors = i;
 513
 514         /* We're done with the boxes now */
 515         xfree(box_list);
 516         qt->freeboxes = qt->usedboxes = NULL;
 517
 518         /*
 519          * STEP 5: scan histogram and map all values to closest color
 520          */
 521         /* 5a: create cell list as described in Heckbert */
 522         qt->ColorCells = xnew_array_and_zero(C_cell*, C_LEN * C_LEN * C_LEN);
 523         /* 5b: create mapping from truncated pixel space to color
 524            table entries */
 525         res = map_colortable(qt, num_colors);
 526
 527         /* 5c: done with ColorCells */
 528         for (i = 0; i < C_LEN * C_LEN * C_LEN; i++) {
 529                 if (qt->ColorCells[i])
 530                         xfree(qt->ColorCells[i]);
 531         }
 532         xfree(qt->ColorCells);
 533
 534         if (res) {
 535                 /* we failed in memory allocation, so clean up an leave */
 536                 xfree(qt);
 537                 return NULL;
 538         }
 539
 540         return qt;
 541 }