gimpimage-convert.c 135 KB
Newer Older
1
/* GIMP - The GNU Image Manipulation Program
Elliot Lee's avatar
Elliot Lee committed
2
 * Copyright (C) 1995 Spencer Kimball and Peter Mattis
3
 * Copyright (C) 1997-2004 Adam D. Moss <adam@gimp.org>
Elliot Lee's avatar
Elliot Lee committed
4 5 6 7 8 9 10 11 12 13 14 15 16
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
17
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
Elliot Lee's avatar
Elliot Lee committed
18 19 20
 */

/*
21 22 23 24
 * 2005-09-04 - Switch 'positional' dither matrix to a 32x32 Bayer,
 *  which generates results that compress somewhat better (and may look
 *  worse or better depending on what you enjoy...).  [adam@gimp.org]
 *
25 26 27 28
 * 2004-12-12 - Use a slower but much nicer technique for finding the
 *  two best colours to dither between when using fixed/positional
 *  dither methods.  Makes positional dither much less lame.  [adam@gimp.org]
 *
29 30 31 32 33 34 35 36 37 38
 * 2002-02-10 - Quantizer version 3.0 (the rest of the commit started
 *  a year ago -- whoops).  Divide colours within CIE L*a*b* space using
 *  CPercep module (cpercep.[ch]), colour-match and dither likewise,
 *  change the underlying box selection criteria and division point
 *  logic, bump luminance precision upwards, etc.etc.  Generally
 *  chooses a much richer colour set, especially for low numbers of
 *  colours.  n.b.: Less luminance-sloppy in straight remapping which is
 *  good for colour but a bit worse for high-frequency detail (that's
 *  partly what fs-dithering is for -- use it).  [adam@gimp.org]
 *
39 40 41 42 43 44 45 46
 * 2001-03-25 - Define accessor function/macro for histogram reads and
 *  writes.  This slows us down a little because we avoid some of the
 *  dirty tricks we used when we knew that the histogram was a straight
 *  3d array, so I've recovered some of the speed loss by implementing
 *  a 5d accessor function with good locality of reference.  This change
 *  is the first step towards quantizing in a more interesting colourspace
 *  than frumpy old RGB.  [Adam]
 *
47 48
 * 2000/01/30 - Use palette_selector instead of option_menu for custom
 *  palette. Use libgimp callback functions.  [Sven]
49
 *
50 51
 * 99/09/01 - Created a low-bleed FS-dither option.  [Adam]
 *
52 53 54 55 56
 * 99/08/29 - Deterministic colour dithering to arbitrary palettes.
 *  Ideal for animations that are going to be delta-optimized or simply
 *  don't want to look 'busy' in static areas.  Also a bunch of bugfixes
 *  and tweaks.  [Adam]
 *
57 58 59 60
 * 99/08/28 - Deterministic alpha dithering over layers, reduced bleeding
 *  of transparent values into opaque values, added optional stage to
 *  remove duplicate or unused colour entries from final colourmap. [Adam]
 *
61 62 63 64 65 66 67 68 69
 * 99/02/24 - Many revisions to the box-cut quantizer used in RGB->INDEXED
 *  conversion.  Box to be cut is chosen on the basis of posessing an axis
 *  with the largest sum of weighted perceptible error, rather than based on
 *  volume or population.  The box is split along this axis rather than its
 *  longest axis, at the point of error mean rather than simply at its centre.
 *  Error-limiting in the F-S dither has been disabled - it may become optional
 *  again later.  If you're convinced that you have an image where the old
 *  dither looks better, let me know.  [Adam]
 *
70 71
 * 99/01/10 - Hourglass... [Adam]
 *
72
 * 98/07/25 - Convert-to-indexed now remembers the last invocation's
73
 *  settings.  Also, GRAY->INDEXED is more flexible.  [Adam]
74
 *
75 76 77 78 79 80
 * 98/07/05 - Sucked the warning about quantizing to too many colours into
 *  a text widget embedded in the dialog, improved intelligence of dialog
 *  to default 'custom palette' selection to 'Web' if available, and
 *  in this case not bother to present the native WWW-palette radio
 *  button.  [Adam]
 *
81
 * 98/04/13 - avoid a division by zero when converting an empty gray-scale
82
 *  image (who would like to do such a thing anyway??)  [Sven ]
83
 *
84
 * 98/03/23 - fixed a longstanding fencepost - hopefully the *right*
85
 *  way, *again*.  [Adam]
86
 *
87 88 89
 * 97/11/14 - added a proper pdb interface and support for dithering
 *  to custom palettes (based on a patch by Eric Hernes) [Yosh]
 *
90 91 92 93 94 95 96
 * 97/11/04 - fixed the accidental use of the colour-counting case
 *  when palette_type is WEB or MONO. [Adam]
 *
 * 97/10/25 - colour-counting implemented (could use some hashing, but
 *  performance actually seems okay) - now RGB->INDEXED conversion isn't
 *  destructive if it doesn't have to be. [Adam]
 *
Elliot Lee's avatar
Elliot Lee committed
97 98 99 100 101 102 103 104
 * 97/10/14 - fixed divide-by-zero when converting a completely transparent
 *  RGB image to indexed. [Adam]
 *
 * 97/07/01 - started todo/revision log.  Put code back in to
 *  eliminate full-alpha pixels from RGB histogram.
 *  [Adam D. Moss - adam@gimp.org]
 */

105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
  /* TODO for Convert:
   *
   * . Tweak, tweak, tweak.  Old RGB code was tuned muchly.
   *
   * . Re-enable Heckbert locality for matching, benchmark it
   *
   * . Try faster fixed-point sRGB<->L*a*b* pixel conversion (see cpercep.c)
   *
   * . Use palette of another open INDEXED image?
   *
   * . Do error-splitting trick for GREY->INDEXED (hardly worth it)
   */

  /* CODE READABILITY BUGS:
   *
   * . Most uses of variants of the R,G,B variable naming convention
   *   are referring to L*a*b* co-ordinates, not RGB co-ordinates!
   *
   * . Each said variable is usually one of the following, but it is
   *   rarely clear which one:
   *     - (assumed sRGB) raw non-linear 8-bit RGB co-ordinates
   *     - 'full'-precision (unshifted) 8-bit L*a*b* co-ordinates
   *     - box-space (reduced-precision shifted L*a*b*) co-ordinates
   */

130
#include "config.h"
Elliot Lee's avatar
Elliot Lee committed
131 132

#include <stdlib.h>
133
#include <stdio.h>
Elliot Lee's avatar
Elliot Lee committed
134
#include <string.h>
135

136
#include <gegl.h>
Sven Neumann's avatar
Sven Neumann committed
137

138
#include "libgimpcolor/gimpcolor.h"
139
#include "libgimpmath/gimpmath.h"
140

Michael Natterer's avatar
Michael Natterer committed
141
#include "core-types.h"
Sven Neumann's avatar
Sven Neumann committed
142

143
#include "base/cpercep.h"
Michael Natterer's avatar
Michael Natterer committed
144 145 146
#include "base/pixel-region.h"
#include "base/tile-manager.h"

147
#include "gimp.h"
148
#include "gimpcontainer.h"
149
#include "gimpdrawable.h"
150
#include "gimpdrawable-convert.h"
151
#include "gimpimage.h"
152
#include "gimpimage-colormap.h"
153
#include "gimpimage-undo.h"
154
#include "gimpimage-undo-push.h"
155
#include "gimplayer.h"
156
#include "gimplayer-floating-sel.h"
157
#include "gimppalette.h"
158
#include "gimpprogress.h"
Michael Natterer's avatar
Michael Natterer committed
159

160 161 162
#include "gimpimage-convert-fsdither.h"
#include "gimpimage-convert-data.h"
#include "gimpimage-convert.h"
163

164
#include "gimp-intl.h"
165

166

167 168
/* basic memory/quality tradeoff */
#define PRECISION_R 8
169 170 171 172 173 174 175 176 177 178 179 180 181
#define PRECISION_G 6
#define PRECISION_B 6

#define HIST_R_ELEMS (1<<PRECISION_R)
#define HIST_G_ELEMS (1<<PRECISION_G)
#define HIST_B_ELEMS (1<<PRECISION_B)

#define BITS_IN_SAMPLE 8

#define R_SHIFT  (BITS_IN_SAMPLE-PRECISION_R)
#define G_SHIFT  (BITS_IN_SAMPLE-PRECISION_G)
#define B_SHIFT  (BITS_IN_SAMPLE-PRECISION_B)

182 183 184 185 186 187 188
/* we've stretched our non-cubic L*a*b* volume to touch the
   faces of the logical cube we've allocated for it, so re-scale
   again in inverse proportion to get back to linear proportions.
*/
#define R_SCALE 13              /*  scale R (L*) distances by this much  */
#define G_SCALE 24              /*  scale G (a*) distances by this much  */
#define B_SCALE 26              /*  and B (b*) by this much              */
189 190


Elliot Lee's avatar
Elliot Lee committed
191 192 193
typedef struct _Color Color;
typedef struct _QuantizeObj QuantizeObj;
typedef void (* Pass1_Func) (QuantizeObj *);
194
typedef void (* Pass2i_Func) (QuantizeObj *);
195
typedef void (* Pass2_Func) (QuantizeObj *, GimpLayer *, TileManager *);
Elliot Lee's avatar
Elliot Lee committed
196 197
typedef void (* Cleanup_Func) (QuantizeObj *);
typedef unsigned long ColorFreq;
Manish Singh's avatar
Manish Singh committed
198
typedef ColorFreq *CFHistogram;
Elliot Lee's avatar
Elliot Lee committed
199

200
typedef enum {AXIS_UNDEF, AXIS_RED, AXIS_BLUE, AXIS_GREEN} axisType;
201

202
typedef double etype;
203 204


205 206 207 208 209 210 211 212 213 214 215 216
/*
  We provide two different histogram access interfaces.  HIST_LIN()
  accesses the histogram in histogram-native space, taking absolute
  histogram co-ordinates.  HIST_RGB() accesses the histogram in RGB
  space.  This latter takes unsigned 8-bit co-ordinates, internally
  converts those co-ordinates to histogram-native space and returns
  the access pointer to the corresponding histogram cell.

  Using these two interfaces we can import RGB data into a more
  interesting space and efficiently work in the latter space until
  it is time to output the quantized values in RGB again.  For
  this final conversion we implement the function lin_to_rgb().
217

218 219 220 221 222
  We effectively pull our three-dimensional space into five dimensions
  such that the most-entropic bits lay in the lowest bits of the resulting
  array index.  This gives significantly better locality of reference
  and hence a small speedup despite the extra work involved in calculating
  the index.
223

224 225 226 227 228 229 230
  Why not six dimensions?  The expansion of dimensionality is good for random
  access such as histogram population and the query pattern typical of
  dithering but we have some code which iterates in a scanning manner, for
  which the expansion is suboptimal.  The compromise is to leave the B
  dimension unmolested in the lower-order bits of the index, since this is
  the dimension most commonly iterated through in the inner loop of the
  scans.
231

232
  --adam
233

234
  RhGhRlGlB
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
*/
#define VOL_GBITS  (PRECISION_G)
#define VOL_BBITS  (PRECISION_B)
#define VOL_RBITS  (PRECISION_R)
#define VOL_GBITSh (VOL_GBITS - 3)
#define VOL_GBITSl (VOL_GBITS - VOL_GBITSh)
#define VOL_BBITSh (VOL_BBITS - 4)
#define VOL_BBITSl (VOL_BBITS - VOL_BBITSh)
#define VOL_RBITSh (VOL_RBITS - 3)
#define VOL_RBITSl (VOL_RBITS - VOL_RBITSh)
#define VOL_GMASKh (((1<<VOL_GBITSh)-1) << VOL_GBITSl)
#define VOL_GMASKl ((1<<VOL_GBITSl)-1)
#define VOL_BMASKh (((1<<VOL_BBITSh)-1) << VOL_BBITSl)
#define VOL_BMASKl ((1<<VOL_BBITSl)-1)
#define VOL_RMASKh (((1<<VOL_RBITSh)-1) << VOL_RBITSl)
#define VOL_RMASKl ((1<<VOL_RBITSl)-1)
/* The 5d compromise thing. */
#define REF_FUNC(r,g,b) \
( \
 (((r) & VOL_RMASKh) << (VOL_BBITS + VOL_GBITS)) | \
 (((r) & VOL_RMASKl) << (VOL_GBITSl + VOL_BBITS)) | \
 (((g) & VOL_GMASKh) << (VOL_RBITSl + VOL_BBITS)) | \
 (((g) & VOL_GMASKl) << (VOL_BBITS)) | \
 (b) \
)
/* The full-on 6d thing. */
/*
#define REF_FUNC(r,g,b) \
( \
 (((r) & VOL_RMASKh) << (VOL_BBITS + VOL_GBITS)) | \
 (((r) & VOL_RMASKl) << (VOL_GBITSl + VOL_BBITSl)) | \
 (((g) & VOL_GMASKh) << (VOL_RBITSl + VOL_BBITS)) | \
 (((g) & VOL_GMASKl) << (VOL_BBITSl)) | \
 (((b) & VOL_BMASKh) << (VOL_RBITSl + VOL_GBITSl)) | \
 ((b) & VOL_BMASKl) \
)
*/
/* The boring old 3d thing. */
/*
#define REF_FUNC(r,g,b) (((r)<<(PRECISION_G+PRECISION_B)) | ((g)<<(PRECISION_B)) | (b))
*/

/* You even get to choose whether you want the accessor function
   implemented as a macro or an inline function.  Don't say I never
   give you anything. */
/*
281
#define HIST_LIN(hist_ptr,r,g,b) (&(hist_ptr)[REF_FUNC((r),(g),(b))])
282
*/
283
static inline
284
ColorFreq* HIST_LIN(ColorFreq *hist_ptr,
285
                    const int r, const int g, const int b)
286 287
{
  return (&(hist_ptr)[
288
                      REF_FUNC(r,g,b)
289 290 291 292
  ]);
}


293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
#define LOWA (-86.181F)
#define LOWB (-107.858F)
#define HIGHA (98.237F)
#define HIGHB (94.480F)

#if 1
#define LRAT (2.55F)
#define ARAT (255.0F / (HIGHA - LOWA))
#define BRAT (255.0F / (HIGHB - LOWB))
#else
#define LRAT (1.0F)
#define ARAT (1.0F)
#define BRAT (1.0F)
#endif

static inline
void rgb_to_unshifted_lin(const unsigned char r,
310 311 312
                          const unsigned char g,
                          const unsigned char b,
                          int *hr, int *hg, int *hb)
313 314 315 316
{
  double sL, sa, sb;
  int or, og, ob;

Adam D. Moss's avatar
Adam D. Moss committed
317
  cpercep_rgb_to_space(r,g,b, &sL, &sa, &sb);
318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338

  /* fprintf(stderr, " %d-%d-%d -> %0.3f,%0.3f,%0.3f ", r, g, b, sL, sa, sb);*/

  or = RINT(sL * LRAT);
  og = RINT((sa - LOWA) * ARAT);
  ob = RINT((sb - LOWB) * BRAT);

  /*  fprintf(stderr, " %d-%d-%d ", or, og, ob); */

#if 0
  if (or < 0 || or > 255)
    fprintf(stderr, " \007R%d ", or);
  if (og < 0 || og > 255)
    fprintf(stderr, " \007G%d ", og);
  if (ob < 0 || ob > 255)
    fprintf(stderr, " \007B%d ", ob);
#endif

  *hr = CLAMP(or, 0, 255);
  *hg = CLAMP(og, 0, 255);
  *hb = CLAMP(ob, 0, 255);
339

340 341 342 343 344 345
  /*  fprintf(stderr, " %d:%d:%d ", *hr, *hg, *hb); */
}


static inline
void rgb_to_lin(const unsigned char r,
346 347 348
                const unsigned char g,
                const unsigned char b,
                int *hr, int *hg, int *hb)
349 350 351 352 353 354 355 356 357 358 359 360 361
{
  int or, og, ob;

  /*
  double sL, sa, sb;
  {
    double low_l = 999.0, low_a = 999.9, low_b = 999.0;
    double high_l = -999.0, high_a = -999.0, high_b = -999.0;

    int r,g,b;

    for (r=0; r<256; r++)
      for (g=0; g<256; g++)
362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
        for (b=0; b<256; b++)
          {
            cpercep_rgb_to_space(r,g,b, &sL, &sa, &sb);

            if (sL > high_l)
              high_l = sL;
            if (sL < low_l)
              low_l = sL;
            if (sa > high_a)
              high_a = sa;
            if (sa < low_a)
              low_a = sa;
            if (sb > high_b)
              high_b = sb;
            if (sb < low_b)
              low_b = sb;
          }
379

380
    fprintf(stderr, " [L: %0.3f -> %0.3f / a: %0.3f -> %0.3f / b: %0.3f -> %0.3f]\t", low_l, high_l, low_a, high_a, low_b, high_b);
381

382 383 384 385 386
    exit(-1);
  }
  */

  rgb_to_unshifted_lin (r,g,b,
387
                        &or, &og, &ob);
388 389 390

#if 0
#define RSDF(r) ((r) >= ((HIST_R_ELEMS-1) << R_SHIFT) ? HIST_R_ELEMS-1 : \
391
                 ((r) + ((1<<R_SHIFT)>>1) ) >> R_SHIFT)
392
#define GSDF(g) ((g) >= ((HIST_G_ELEMS-1) << G_SHIFT) ? HIST_G_ELEMS-1 : \
393
                 ((g) + ((1<<G_SHIFT)>>1) ) >> G_SHIFT)
394
#define BSDF(b) ((b) >= ((HIST_B_ELEMS-1) << B_SHIFT) ? HIST_B_ELEMS-1 : \
395
                 ((b) + ((1<<B_SHIFT)>>1) ) >> B_SHIFT)
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413
#else
#define RSDF(r) ((r) >> R_SHIFT)
#define GSDF(g) ((g) >> G_SHIFT)
#define BSDF(b) ((b) >> B_SHIFT)
#endif

  or = RSDF(or);
  og = GSDF(og);
  ob = BSDF(ob);

  *hr = or;
  *hg = og;
  *hb = ob;
}


static inline
ColorFreq* HIST_RGB(ColorFreq *hist_ptr,
414
                    const int r, const int g, const int b)
415 416 417 418
{
  int hr, hg, hb;

  rgb_to_lin(r, g, b,
419
             &hr, &hg, &hb);
420 421 422 423 424 425 426

  return (HIST_LIN(hist_ptr,hr,hg,hb));
}


static inline
void lin_to_rgb(const double hr, const double hg, const double hb,
427 428 429
                unsigned char *r,
                unsigned char *g,
                unsigned char *b)
430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
{
  double sr,sg,sb;
  double ir,ig,ib;

  /*  fprintf(stderr, "%d.%d.%d ", hr,hg,hb); */

#if 0
  ir = (hr * ((double) (1 << R_SHIFT))) + (((double)(1<<R_SHIFT))*0.5);
  ig = (hg * ((double) (1 << G_SHIFT))) + (((double)(1<<G_SHIFT))*0.5);
  ib = (hb * ((double) (1 << B_SHIFT))) + (((double)(1<<B_SHIFT))*0.5);
#else
  /* w/ artificial widening of dynamic range */
  ir = ((double)(hr)) * 255.0F / (double)(HIST_R_ELEMS-1);
  ig = ((double)(hg)) * 255.0F / (double)(HIST_G_ELEMS-1);
  ib = ((double)(hb)) * 255.0F / (double)(HIST_B_ELEMS-1);
#endif

  ir = ir / LRAT;
  ig = (ig / ARAT) + LOWA;
  ib = (ib / BRAT) + LOWB;

  /*  fprintf(stderr, "%0.1f,%0.1f,%0.1f ", ir,ig,ib); */

Adam D. Moss's avatar
Adam D. Moss committed
453
  cpercep_space_to_rgb(ir, ig, ib,
454
                       &sr, &sg, &sb);
455 456 457 458 459 460 461 462 463 464

  *r = RINT(CLAMP(sr, 0.0F, 255.0F));
  *g = RINT(CLAMP(sg, 0.0F, 255.0F));
  *b = RINT(CLAMP(sb, 0.0F, 255.0F));

  /*  fprintf(stderr, "%d,%d,%d ", *r, *g, *b); */
}



Elliot Lee's avatar
Elliot Lee committed
465 466 467 468 469 470 471 472 473
struct _Color
{
  int red;
  int green;
  int blue;
};

struct _QuantizeObj
{
474
  Pass1_Func first_pass;            /* first pass over image data creates colormap  */
475
  Pass2i_Func second_pass_init;     /* Initialize data which persists over invocations */
476
  Pass2_Func second_pass;           /* second pass maps from image data to colormap */
477 478 479 480
  Cleanup_Func delete_func;         /* function to clean up data associated with private */

  int desired_number_of_colors;     /* Number of colors we will allow    */
  int actual_number_of_colors;      /* Number of colors actually needed  */
481
  Color cmap[256];                  /* colormap created by quantization  */
482
  Color clin[256];                  /* .. converted back to linear space */
Manish Singh's avatar
Manish Singh committed
483 484
  gulong index_used_count[256];     /* how many times an index was used */
  CFHistogram histogram;            /* holds the histogram               */
485

486 487
  gboolean want_alpha_dither;
  int      error_freedom;           /* 0=much bleed, 1=controlled bleed */
488

489 490 491
  GimpProgress *progress;
  gint          nth_layer;
  gint          n_layers;
Elliot Lee's avatar
Elliot Lee committed
492 493 494 495 496 497
};

typedef struct
{
  /*  The bounds of the box (inclusive); expressed as histogram indexes  */
  int   Rmin, Rmax;
498
  int   Rhalferror;
Elliot Lee's avatar
Elliot Lee committed
499
  int   Gmin, Gmax;
500
  int   Ghalferror;
Elliot Lee's avatar
Elliot Lee committed
501
  int   Bmin, Bmax;
502
  int   Bhalferror;
Elliot Lee's avatar
Elliot Lee committed
503 504 505 506 507 508

  /*  The volume (actually 2-norm) of the box  */
  int   volume;

  /*  The number of nonzero histogram cells within this box  */
  long  colorcount;
509 510 511 512 513 514 515 516

  /* The sum of the weighted error within this box */
  guint64 error;
  /* The sum of the unweighted error within this box */
  guint64 rerror;
  guint64 gerror;
  guint64 berror;

Elliot Lee's avatar
Elliot Lee committed
517 518
} box, *boxptr;

519

520 521 522 523 524 525 526 527 528 529 530 531
static void zero_histogram_gray     (CFHistogram   histogram);
static void zero_histogram_rgb      (CFHistogram   histogram);
static void generate_histogram_gray (CFHistogram   hostogram,
                                     GimpLayer    *layer,
                                     gboolean      alpha_dither);
static void generate_histogram_rgb  (CFHistogram   histogram,
                                     GimpLayer    *layer,
                                     gint          col_limit,
                                     gboolean      alpha_dither,
                                     GimpProgress *progress,
                                     gint          nth_layer,
                                     gint          n_layers);
Elliot Lee's avatar
Elliot Lee committed
532

533 534 535 536 537 538 539 540 541 542 543
static QuantizeObj * initialize_median_cut (GimpImageBaseType      old_type,
                                            gint                   num_cols,
                                            GimpConvertDitherType  dither_type,
                                            GimpConvertPaletteType palette_type,
                                            gboolean               alpha_dither,
                                            GimpProgress          *progress);

static void          compute_color_lin8    (QuantizeObj           *quantobj,
                                            CFHistogram            histogram,
                                            boxptr                 boxp,
                                            const int              icolor);
544

545

546 547 548
static guchar    found_cols[MAXNUMCOLORS][3];
static gint      num_found_cols;
static gboolean  needs_quantize;
549

550
static GimpPalette *theCustomPalette = NULL;
551

552 553 554 555 556 557 558 559 560 561 562

/**********************************************************/
typedef struct
{
  signed long used_count;
  unsigned char initial_index;
} palentryStruct;

static int
mapping_compare (const void *a, const void *b)
{
563 564
  palentryStruct *m1 = (palentryStruct *) a;
  palentryStruct *m2 = (palentryStruct *) b;
565 566 567 568 569 570 571 572 573

  return (m2->used_count - m1->used_count);
}

/* FWIW, the make_remap_table() and mapping_compare() function source
   and palentryStruct may be re-used under the XFree86-style license.
   <adam@gimp.org> */
static void
make_remap_table (const unsigned char  old_palette[],
574 575 576 577
                  unsigned char        new_palette[],
                  const unsigned long  index_used_count[],
                  unsigned char        remap_table[],
                  int*                 num_entries)
578 579 580 581 582 583 584 585 586
{
  int i,j,k;
  unsigned char temppal[256 * 3];
  unsigned long tempuse[256];
  unsigned long transmap[256];
  palentryStruct *palentries;
  int used = 0;

  memset(temppal, 0, 256 * 3);
Sven Neumann's avatar
Sven Neumann committed
587 588
  memset(tempuse, 0, 256 * sizeof (unsigned long));
  memset(transmap, 255, 256 * sizeof (unsigned long));
589 590 591 592 593 594

  /* First pass - only collect entries which are marked as
     being used at all in index_used_count. */
  for (i = 0; i < *num_entries; i++)
    {
      if (index_used_count[i])
595 596 597 598
        {
          temppal[used*3 + 0] = old_palette[i*3 + 0];
          temppal[used*3 + 1] = old_palette[i*3 + 1];
          temppal[used*3 + 2] = old_palette[i*3 + 2];
599

600 601
          tempuse[used] = index_used_count[i];
          transmap[i] = used;
602

603 604
          used++;
        }
605 606 607 608 609 610
    }

  /* Second pass - remove duplicates. (O(n^3), could do better!) */
  for (i = 0; i < used; i++)
    {
      for (j = 0; j < i; j++)
611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
        {
          if ((temppal[i*3 + 1] == temppal[j*3 + 1]) &&
              (temppal[i*3 + 0] == temppal[j*3 + 0]) &&
              (temppal[i*3 + 2] == temppal[j*3 + 2]) &&
              tempuse[j] &&
              tempuse[i])
            {
              /* Move the 'used' tally from one to the other. */
              tempuse[i] += tempuse[j];
              /* zero one of them, deactivating its entry. */
              tempuse[j] = 0;

              /* change all mappings from this dead index
                 to the live one. */
              for (k = 0; k < *num_entries; k++)
                {
                  if (index_used_count[k] && (transmap[k] == j))
                    transmap[k] = i;
                }
            }
        }
632 633 634 635
    }

  /* Third pass - rank all used indicies to the beginning of the
     palette. */
Sven Neumann's avatar
Sven Neumann committed
636 637
  palentries = g_new (palentryStruct, used);

638 639 640 641 642
  for (i = 0; i < used; i++)
    {
      palentries[i].initial_index = i;
      palentries[i].used_count    = tempuse[i];
    }
Sven Neumann's avatar
Sven Neumann committed
643 644 645

  qsort (palentries, used, sizeof (palentryStruct), &mapping_compare);

646 647 648
  for (i = 0; i < *num_entries; i++)
    {
      if (index_used_count[i])
649 650 651 652 653 654 655 656 657 658 659
        {
          for (j = 0; j < used; j++)
            {
              if ((transmap[i] == palentries[j].initial_index)
                  && (palentries[j].used_count))
                {
                  remap_table[i] = j;
                  break;
                }
            }
        }
660 661 662 663
    }
  for (i = 0; i < *num_entries; i++)
    {
      if (index_used_count[i])
664 665 666 667 668
        {
          new_palette[remap_table[i]*3 + 0] = old_palette[i*3 + 0];
          new_palette[remap_table[i]*3 + 1] = old_palette[i*3 + 1];
          new_palette[remap_table[i]*3 + 2] = old_palette[i*3 + 2];
        }
669
    }
670

671
  *num_entries = 0;
672

673 674 675
  for (j = 0; j < used; j++)
    {
      if (palentries[j].used_count)
676 677 678
        {
          (*num_entries)++;
        }
679
    }
680

681 682 683 684
  g_free (palentries);
}

static void
685 686 687
remap_indexed_layer (GimpLayer    *layer,
                     const guchar *remap_table,
                     gint          num_entries)
688
{
689 690 691
  PixelRegion  srcPR, destPR;
  gpointer     pr;
  gboolean     has_alpha = gimp_drawable_has_alpha (GIMP_DRAWABLE (layer));
692

693
  pixel_region_init (&srcPR, gimp_drawable_get_tiles (GIMP_DRAWABLE (layer)),
694
                     0, 0,
695 696
                     gimp_item_get_width  (GIMP_ITEM (layer)),
                     gimp_item_get_height (GIMP_ITEM (layer)),
697
                     FALSE);
698
  pixel_region_init (&destPR, gimp_drawable_get_tiles (GIMP_DRAWABLE (layer)),
699
                     0, 0,
700 701
                     gimp_item_get_width  (GIMP_ITEM (layer)),
                     gimp_item_get_height (GIMP_ITEM (layer)),
702
                     TRUE);
703

704 705 706
  for (pr = pixel_regions_register (2, &srcPR, &destPR);
       pr != NULL;
       pr = pixel_regions_process (pr))
707
    {
708 709 710
      const guchar *src    = srcPR.data;
      guchar       *dest   = destPR.data;
      gint          pixels = srcPR.h * srcPR.w;
711

712 713
      if (has_alpha)
        {
714
          while (pixels--)
715
            {
716 717
              if (src[ALPHA_I])
                dest[INDEXED] = remap_table[src[INDEXED]];
718 719 720 721

              src += srcPR.bytes;
              dest += destPR.bytes;
            }
722
        }
723
      else
724 725
        {
          while (pixels--)
726
            {
727
              dest[INDEXED] = remap_table[src[INDEXED]];
728

729 730 731 732
              src += srcPR.bytes;
              dest += destPR.bytes;
            }
        }
733 734 735
    }
}

736
static int
737 738 739
color_quicksort (const void *c1,
                 const void *c2)
{
740 741
  Color *color1 = (Color *) c1;
  Color *color2 = (Color *) c2;
742

743 744
  double v1 = GIMP_RGB_LUMINANCE (color1->red, color1->green, color1->blue);
  double v2 = GIMP_RGB_LUMINANCE (color2->red, color2->green, color2->blue);
745

746 747 748 749 750 751 752
  if (v1 < v2)
    return -1;
  else if (v1 > v2)
    return 1;
  else
    return 0;
}
753

754 755 756
gboolean
gimp_image_convert (GimpImage               *image,
                    GimpImageBaseType        new_type,
757
                    /* The following are only used for new_type == GIMP_INDEXED
758
                     */
759 760 761 762 763 764 765 766
                    gint                     num_cols,
                    GimpConvertDitherType    dither,
                    gboolean                 alpha_dither,
                    gboolean                 remove_dups,
                    GimpConvertPaletteType   palette_type,
                    GimpPalette             *custom_palette,
                    GimpProgress            *progress,
                    GError                 **error)
Elliot Lee's avatar
Elliot Lee committed
767
{
768
  QuantizeObj       *quantobj = NULL;
769 770
  GimpImageBaseType  old_type;
  GList             *list;
771
  const gchar       *undo_desc = NULL;
772
  gint               nth_layer, n_layers;
Elliot Lee's avatar
Elliot Lee committed
773

774 775 776 777
  g_return_val_if_fail (GIMP_IS_IMAGE (image), FALSE);
  g_return_val_if_fail (new_type != gimp_image_base_type (image), FALSE);
  g_return_val_if_fail (progress == NULL || GIMP_IS_PROGRESS (progress), FALSE);
  g_return_val_if_fail (error == NULL || *error == NULL, FALSE);
778

779
  if (palette_type == GIMP_CUSTOM_PALETTE)
780
    {
781 782
      g_return_val_if_fail (custom_palette == NULL ||
                            GIMP_IS_PALETTE (custom_palette), FALSE);
783 784
      g_return_val_if_fail (custom_palette == NULL ||
                            custom_palette->n_colors <= 256, FALSE);
785 786 787 788 789 790

      if (! custom_palette)
        palette_type = GIMP_MONO_PALETTE;

      if (custom_palette->n_colors < 1)
        {
791 792 793
          g_set_error (error, 0, 0,
                       _("Cannot convert image: palette is empty."));
          return FALSE;
794
        }
795 796
    }

797 798
  theCustomPalette = custom_palette;

799
  gimp_set_busy (image->gimp);
800

801
  n_layers = gimp_container_num_children (GIMP_CONTAINER (image->layers));
802

803 804 805 806 807 808 809 810 811 812 813 814 815 816 817
  switch (new_type)
    {
    case GIMP_RGB:
      undo_desc = _("Convert Image to RGB");
      break;

    case GIMP_GRAY:
      undo_desc = _("Convert Image to Grayscale");
      break;

    case GIMP_INDEXED:
      undo_desc = _("Convert Image to Indexed");
      break;
    }

818
  g_object_freeze_notify (G_OBJECT (image));
819

820
  gimp_image_undo_group_start (image, GIMP_UNDO_GROUP_IMAGE_CONVERT,
821
                               undo_desc);
Elliot Lee's avatar
Elliot Lee committed
822

823 824
  if (gimp_image_floating_sel (image))
    floating_sel_relax (gimp_image_floating_sel (image), TRUE);
825

826
  /*  Push the image type to the stack  */
827
  gimp_image_undo_push_image_type (image, NULL);
Elliot Lee's avatar
Elliot Lee committed
828 829

  /*  Set the new base type  */
830
  old_type = gimp_image_base_type (image);
831

832
  g_object_set (image, "base-type", new_type, NULL);
Elliot Lee's avatar
Elliot Lee committed
833

834
  /* initialize the colour conversion routines */
835
  cpercep_init ();
836

Elliot Lee's avatar
Elliot Lee committed
837
  /*  Convert to indexed?  Build histogram if necessary.  */
838
  if (new_type == GIMP_INDEXED)
Elliot Lee's avatar
Elliot Lee committed
839
    {
840
      gint i;
Elliot Lee's avatar
Elliot Lee committed
841

842 843
      /* fprintf(stderr, " TO INDEXED(%d) ", num_cols); */

844
      /* don't dither if the input is grayscale and we are simply
845 846 847 848
       * mapping every color
       */
      if (old_type     == GIMP_GRAY &&
          num_cols     == 256       &&
849 850 851 852
          palette_type == GIMP_MAKE_PALETTE)
        {
          dither = GIMP_NO_DITHER;
        }
Elliot Lee's avatar
Elliot Lee committed
853

854
      quantobj = initialize_median_cut (old_type, num_cols, dither,
855 856
                                        palette_type, alpha_dither,
                                        progress);
Elliot Lee's avatar
Elliot Lee committed
857

858
      if (palette_type == GIMP_MAKE_PALETTE)
859 860 861 862 863 864 865 866 867 868 869 870 871 872
        {
          if (old_type == GIMP_GRAY)
            zero_histogram_gray (quantobj->histogram);
          else
            zero_histogram_rgb (quantobj->histogram);

          /* To begin, assume that there are fewer colours in
           *  the image than the user actually asked for.  In that
           *  case, we don't need to quantize or colour-dither.
           */
          needs_quantize = FALSE;
          num_found_cols = 0;

          /*  Build the histogram  */
873
          for (list = gimp_image_get_layer_iter (image), nth_layer = 0;
874 875 876
               list;
               list = g_list_next (list), nth_layer++)
            {
877
              GimpLayer *layer = list->data;
878 879 880

              if (old_type == GIMP_GRAY)
                generate_histogram_gray (quantobj->histogram,
881
                                         layer, alpha_dither);
882 883
              else
                generate_histogram_rgb (quantobj->histogram,
884
                                        layer, num_cols, alpha_dither,
885
                                        progress, nth_layer, n_layers);
886 887 888 889 890 891 892
              /*
               * Note: generate_histogram_rgb may set needs_quantize if
               *  the image contains more colours than the limit specified
               *  by the user.
               */
            }
        }
Elliot Lee's avatar
Elliot Lee committed
893

894 895
      if (progress)
        gimp_progress_set_text (progress,
Sven Neumann's avatar
Sven Neumann committed
896
                                _("Converting to indexed colors (stage 2)"));
897

898 899 900
      if (old_type == GIMP_RGB &&
          ! needs_quantize     &&
          palette_type == GIMP_MAKE_PALETTE)
901 902 903 904 905 906 907 908 909 910
        {
          /* If this is an RGB image, and the user wanted a custom-built
           *  generated palette, and this image has no more colours than
           *  the user asked for, we don't need the first pass (quantization).
           *
           * There's also no point in dithering, since there's no error to
           *  spread.  So we destroy the old quantobj and make a new one
           *  with the remapping function set to a special LUT-based
           *  no-dither remapper.
           */
911

912 913 914
          quantobj->delete_func (quantobj);
          quantobj = initialize_median_cut (old_type, num_cols,
                                            GIMP_NODESTRUCT_DITHER,
915
                                            palette_type,
916
                                            alpha_dither,
917
                                            progress);
918 919 920 921 922 923 924 925 926 927
          /* We can skip the first pass (palette creation) */

          quantobj->actual_number_of_colors = num_found_cols;
          for (i = 0; i < num_found_cols; i++)
            {
              quantobj->cmap[i].red = found_cols[i][0];
              quantobj->cmap[i].green = found_cols[i][1];
              quantobj->cmap[i].blue = found_cols[i][2];
            }
        }
Elliot Lee's avatar
Elliot Lee committed
928
      else
929 930 931
        {
          (* quantobj->first_pass) (quantobj);
        }
932

933
      if (palette_type == GIMP_MAKE_PALETTE)
934 935
        qsort (quantobj->cmap,
               quantobj->actual_number_of_colors, sizeof (Color),
936
               color_quicksort);
937
    }
Elliot Lee's avatar
Elliot Lee committed
938

939 940
  if (progress)
    gimp_progress_set_text (progress,
Sven Neumann's avatar
Sven Neumann committed
941
                            _("Converting to indexed colors (stage 3)"));
942

943 944 945
  /* Initialise data which must persist across indexed layer iterations */
  switch (new_type)
    {
946
    case GIMP_INDEXED:
947
      if (quantobj->second_pass_init)
948
        (* quantobj->second_pass_init) (quantobj);
949 950 951
      break;
    default:
      break;
Elliot Lee's avatar
Elliot Lee committed
952 953 954
    }

  /*  Convert all layers  */
955 956 957
  if (quantobj)
    quantobj->n_layers = n_layers;

958
  for (list = gimp_image_get_layer_iter (image), nth_layer = 0;
959
       list;
960
       list = g_list_next (list), nth_layer++)
Elliot Lee's avatar
Elliot Lee committed
961
    {
962 963 964
      GimpLayer     *layer = list->data;
      GimpImageType  new_layer_type;
      TileManager   *new_tiles;
Elliot Lee's avatar
Elliot Lee committed
965

966 967
      new_layer_type = GIMP_IMAGE_TYPE_FROM_BASE_TYPE (new_type);

968
      if (gimp_drawable_has_alpha (GIMP_DRAWABLE (layer)))
969
        new_layer_type = GIMP_IMAGE_TYPE_WITH_ALPHA (new_layer_type);
970

971 972
      new_tiles = tile_manager_new (gimp_item_get_width  (GIMP_ITEM (layer)),
                                    gimp_item_get_height (GIMP_ITEM (layer)),
973
                                    GIMP_IMAGE_TYPE_BYTES (new_layer_type));
Elliot Lee's avatar
Elliot Lee committed
974 975

      switch (new_type)
976 977 978
        {
        case GIMP_RGB:
          gimp_drawable_convert_rgb (GIMP_DRAWABLE (layer),
Sven Neumann's avatar
Sven Neumann committed
979
                                     new_tiles, old_type);
980 981 982
          break;
        case GIMP_GRAY:
          gimp_drawable_convert_grayscale (GIMP_DRAWABLE (layer),
Sven Neumann's avatar
Sven Neumann committed
983
                                           new_tiles, old_type);
984 985
          break;
        case GIMP_INDEXED:
986
          quantobj->nth_layer = nth_layer;
Sven Neumann's avatar
Sven Neumann committed
987
          (* quantobj->second_pass) (quantobj, layer, new_tiles);
988 989 990 991
          break;
        default:
          break;
        }
Elliot Lee's avatar
Elliot Lee committed
992

993 994
      gimp_drawable_set_tiles (GIMP_DRAWABLE (layer), TRUE, NULL,
                               new_tiles, new_layer_type);
995
      tile_manager_unref (new_tiles);
Elliot Lee's avatar
Elliot Lee committed
996 997
    }

998
  switch (new_type)
999
    {
1000 1001
    case GIMP_RGB:
    case GIMP_GRAY: