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    &