source: trunk/libdjvu/DjVuPalette.cpp @ 101

Last change on this file since 101 was 17, checked in by Eugene Romanenko, 16 years ago

update makefiles, remove absolute paths, update djvulibre to version 3.5.17

File size: 15.2 KB
Line 
1//C-  -*- C++ -*-
2//C- -------------------------------------------------------------------
3//C- DjVuLibre-3.5
4//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
5//C- Copyright (c) 2001  AT&T
6//C-
7//C- This software is subject to, and may be distributed under, the
8//C- GNU General Public License, Version 2. The license should have
9//C- accompanied the software or you may obtain a copy of the license
10//C- from the Free Software Foundation at http://www.fsf.org .
11//C-
12//C- This program is distributed in the hope that it will be useful,
13//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
14//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15//C- GNU General Public License for more details.
16//C-
17//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library
18//C- distributed by Lizardtech Software.  On July 19th 2002, Lizardtech
19//C- Software authorized us to replace the original DjVu(r) Reference
20//C- Library notice by the following text (see doc/lizard2002.djvu):
21//C-
22//C-  ------------------------------------------------------------------
23//C- | DjVu (r) Reference Library (v. 3.5)
24//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
25//C- | The DjVu Reference Library is protected by U.S. Pat. No.
26//C- | 6,058,214 and patents pending.
27//C- |
28//C- | This software is subject to, and may be distributed under, the
29//C- | GNU General Public License, Version 2. The license should have
30//C- | accompanied the software or you may obtain a copy of the license
31//C- | from the Free Software Foundation at http://www.fsf.org .
32//C- |
33//C- | The computer code originally released by LizardTech under this
34//C- | license and unmodified by other parties is deemed "the LIZARDTECH
35//C- | ORIGINAL CODE."  Subject to any third party intellectual property
36//C- | claims, LizardTech grants recipient a worldwide, royalty-free,
37//C- | non-exclusive license to make, use, sell, or otherwise dispose of
38//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
39//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
40//C- | General Public License.   This grant only confers the right to
41//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
42//C- | the extent such infringement is reasonably necessary to enable
43//C- | recipient to make, have made, practice, sell, or otherwise dispose
44//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
45//C- | any greater extent that may be necessary to utilize further
46//C- | modifications or combinations.
47//C- |
48//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
49//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
50//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
51//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
52//C- +------------------------------------------------------------------
53//
54// $Id: DjVuPalette.cpp,v 1.12 2006/02/21 16:10:29 docbill Exp $
55// $Name:  $
56
57#ifdef HAVE_CONFIG_H
58# include "config.h"
59#endif
60#if NEED_GNUG_PRAGMAS
61# pragma implementation
62#endif
63
64#include "GException.h"
65#include "ByteStream.h"
66#include "BSByteStream.h"
67#include "DjVuPalette.h"
68#include <stdlib.h>
69#include <math.h>
70
71
72#ifdef HAVE_NAMESPACES
73namespace DJVU {
74# ifdef NOT_DEFINED // Just to fool emacs c++ mode
75}
76#endif
77#endif
78
79
80#define CUBEBITS  4
81#define CUBESIDE  (1<<CUBEBITS)
82#define CUBESIZE  (CUBESIDE*CUBESIDE*CUBESIDE)
83
84#define RMUL 5
85#define GMUL 9
86#define BMUL 2
87#define SMUL (RMUL+GMUL+BMUL)
88
89#define MAXPALETTESIZE 65535 // Limit for a 16 bit unsigned read.
90
91
92inline unsigned char 
93umax(unsigned char a, unsigned char b) 
94{ return (a>b) ? a : b; }
95
96inline unsigned char 
97umin(unsigned char a, unsigned char b) 
98{ return (a>b) ? b : a; }
99
100inline float 
101fmin(float a, float b) 
102{ return (a>b) ? b : a; }
103
104
105
106// ------- DJVUPALETTE
107
108
109DjVuPalette::DjVuPalette()
110  : mask(0), hist(0), pmap(0)
111{
112}
113
114DjVuPalette::~DjVuPalette()
115{
116  delete hist;
117  delete pmap;
118}
119
120DjVuPalette& 
121DjVuPalette::operator=(const DjVuPalette &ref)
122{
123  if (this != &ref)
124    {
125      delete hist;
126      delete pmap;
127      mask = 0;
128      palette = ref.palette;
129      colordata = ref.colordata;
130    }
131  return *this;
132}
133
134DjVuPalette::DjVuPalette(const DjVuPalette &ref)
135  : mask(0), hist(0), pmap(0)
136{
137  this->operator=(ref);
138}
139
140
141
142// -------- HISTOGRAM ALLOCATION
143
144void
145DjVuPalette::allocate_hist()
146{
147  if (! hist)
148    {
149      hist = new GMap<int,int>;
150      mask = 0;
151    }
152  else
153    {
154      GMap<int,int> *old = hist;
155      hist = new GMap<int,int>;
156      mask = (mask<<1)|(0x010101);
157      for (GPosition p = *old; p; ++p)
158        {
159          int k = old->key(p);
160          int w = (*old)[p];
161          (*hist)[k | mask] += w;
162        }
163      delete old;
164    }
165}
166
167
168// -------- PALETTE COMPUTATION
169
170
171#ifndef NEED_DECODER_ONLY
172
173struct PData
174{
175  unsigned char p[3];
176  int w;
177};
178
179struct PBox
180{
181  PData *data;
182  int colors;
183  int boxsize;
184  int sum;
185};
186int
187DjVuPalette::bcomp (const void *a, const void *b)
188{
189  return ((PData*)a)->p[0] - ((PData*)b)->p[0];
190}
191
192int
193
194DjVuPalette::gcomp (const void *a, const void *b)
195{
196  return ((PData*)a)->p[1] - ((PData*)b)->p[1];
197}
198
199int
200DjVuPalette::rcomp (const void *a, const void *b)
201{
202  return ((PData*)a)->p[2] - ((PData*)b)->p[2];
203}
204
205int
206DjVuPalette::lcomp (const void *a, const void *b)
207{
208  unsigned char *aa = ((PColor*)a)->p;
209  unsigned char *bb = ((PColor*)b)->p;
210  if (aa[3] != bb[3])
211    return aa[3]-bb[3];
212  else if (aa[2] != bb[2])
213    return aa[2]-bb[2];
214  else if (aa[1] != bb[1])
215    return aa[1]=bb[1];
216  else
217    return aa[0]-bb[0];
218}
219
220int
221DjVuPalette::compute_palette(int maxcolors, int minboxsize)
222{
223  if (!hist)
224    G_THROW( ERR_MSG("DjVuPalette.no_color") );
225  if (maxcolors<1 || maxcolors>MAXPALETTESIZE)
226    G_THROW( ERR_MSG("DjVuPalette.many_colors") );
227 
228  // Paul Heckbert: "Color Image Quantization for Frame Buffer Display",
229  // SIGGRAPH '82 Proceedings, page 297.  (also in ppmquant)
230 
231  // Collect histogram colors
232  int sum = 0;
233  int ncolors = 0;
234  GTArray<PData> pdata;
235  { // extra nesting for windows
236    for (GPosition p = *hist; p; ++p)
237    {
238      pdata.touch(ncolors);
239      PData &data = pdata[ncolors++];
240      int k = hist->key(p);
241      data.p[0] = (k>>16) & 0xff;
242      data.p[1] = (k>>8) & 0xff;
243      data.p[2] = (k) & 0xff;
244      data.w = (*hist)[p];
245      sum += data.w;
246    }
247  }
248  // Create first box
249  GList<PBox> boxes;
250  PBox newbox;
251  newbox.data = pdata;
252  newbox.colors = ncolors;
253  newbox.boxsize = 256;
254  newbox.sum = sum;
255  boxes.append(newbox);
256  // Repeat spliting boxes
257  while (boxes.size() < maxcolors)
258    {
259      // Find suitable box
260      GPosition p;
261      for (p=boxes; p; ++p)
262        if (boxes[p].colors>=2 && boxes[p].boxsize>minboxsize) 
263          break;
264      if (! p)
265        break;
266      // Find box boundaries
267      PBox &splitbox = boxes[p];
268      unsigned char pmax[3];
269      unsigned char pmin[3];
270      pmax[0] = pmin[0] = splitbox.data->p[0];
271      pmax[1] = pmin[1] = splitbox.data->p[1];
272      pmax[2] = pmin[2] = splitbox.data->p[2];
273      { // extra nesting for windows
274        for (int j=1; j<splitbox.colors; j++)
275        {
276          pmax[0] = umax(pmax[0], splitbox.data[j].p[0]);
277          pmax[1] = umax(pmax[1], splitbox.data[j].p[1]);
278          pmax[2] = umax(pmax[2], splitbox.data[j].p[2]);
279          pmin[0] = umin(pmin[0], splitbox.data[j].p[0]);
280          pmin[1] = umin(pmin[1], splitbox.data[j].p[1]);
281          pmin[2] = umin(pmin[2], splitbox.data[j].p[2]);
282        }
283      }
284      // Determine split direction and sort
285      int bl = pmax[0]-pmin[0]; 
286      int gl = pmax[1]-pmin[1];
287      int rl = pmax[2]-pmin[2];
288      splitbox.boxsize = (bl>gl ? (rl>bl ? rl : bl) : (rl>gl ? rl : gl));
289      if (splitbox.boxsize <= minboxsize)
290        continue;
291      if (gl == splitbox.boxsize)
292        qsort(splitbox.data, splitbox.colors, sizeof(PData), gcomp);
293      else if (rl == splitbox.boxsize)
294        qsort(splitbox.data, splitbox.colors, sizeof(PData), rcomp);
295      else
296        qsort(splitbox.data, splitbox.colors, sizeof(PData), bcomp);
297      // Find median
298      int lowercolors = 0;
299      int lowersum = 0;
300      while (lowercolors<splitbox.colors-1 && lowersum+lowersum<splitbox.sum)
301        lowersum += splitbox.data[lowercolors++].w;
302      // Compute new boxes
303      newbox.data = splitbox.data + lowercolors;
304      newbox.colors = splitbox.colors - lowercolors;
305      newbox.sum = splitbox.sum - lowersum;
306      splitbox.colors = lowercolors;
307      splitbox.sum = lowersum;
308      // Insert boxes at proper location
309      GPosition q;
310      for (q=p; q; ++q)
311        if (boxes[q].sum < newbox.sum)
312          break;
313      boxes.insert_before(q, newbox);
314      for (q=p; q; ++q)
315        if (boxes[q].sum < splitbox.sum)
316          break;
317      boxes.insert_before(q, boxes, p);
318    }
319  // Fill palette array
320  ncolors = 0;
321  palette.empty();
322  palette.resize(0,boxes.size()-1);
323  { // extra nesting for windows
324    for (GPosition p=boxes; p; ++p)
325    {
326      PBox &box = boxes[p];
327      // Compute box representative color
328      float bsum = 0;
329      float gsum = 0;
330      float rsum = 0;
331      for (int j=0; j<box.colors; j++)
332        {
333          float w = (float)box.data[j].w;
334          bsum += box.data[j].p[0] * w;
335          gsum += box.data[j].p[1] * w;
336          rsum += box.data[j].p[2] * w;
337        }
338      PColor &color = palette[ncolors++];
339      color.p[0] = (unsigned char) fmin(255, bsum/box.sum);
340      color.p[1] = (unsigned char) fmin(255, gsum/box.sum);
341      color.p[2] = (unsigned char) fmin(255, rsum/box.sum);
342      color.p[3] = ( color.p[0]*BMUL + color.p[1]*GMUL + color.p[2]*RMUL) / SMUL;
343    }
344  }
345  // Save dominant color
346  PColor dcolor = palette[0];
347  // Sort palette colors in luminance order
348  qsort((PColor*)palette, ncolors, sizeof(PColor), lcomp);
349  // Clear invalid data
350  colordata.empty();
351  delete pmap;
352  pmap = 0;
353  // Return dominant color
354  return color_to_index_slow(dcolor.p);
355}
356
357
358
359int 
360DjVuPalette::compute_pixmap_palette(const GPixmap &pm, int ncolors, int minboxsize)
361{
362  // Prepare histogram
363  histogram_clear();
364  { // extra nesting for windows
365    for (int j=0; j<(int)pm.rows(); j++)
366    {
367      const GPixel *p = pm[j];
368      for (int i=0; i<(int)pm.columns(); i++)
369        histogram_add(p[i], 1);
370    }
371  }
372  // Compute palette
373  return compute_palette(ncolors, minboxsize);
374}
375
376
377#endif
378
379
380
381
382// -------- QUANTIZATION
383
384
385void
386DjVuPalette::allocate_pmap()
387{
388  if (! pmap)
389    pmap = new GMap<int,int>;
390}
391
392int 
393DjVuPalette::color_to_index_slow(const unsigned char *bgr)
394{
395  PColor *pal = palette;
396  const int ncolors = palette.size();
397  if (! ncolors)
398    G_THROW( ERR_MSG("DjVuPalette.not_init") );
399  // Should be able to do better
400  int found = 0;
401  int founddist = 3*256*256;
402  { // extra nesting for windows
403    for (int i=0; i<ncolors; i++)
404    {
405      int bd = bgr[0] - pal[i].p[0];
406      int gd = bgr[1] - pal[i].p[1];
407      int rd = bgr[2] - pal[i].p[2];
408      int dist = (bd*bd)+(gd*gd)+(rd*rd);
409      if (dist < founddist)
410        {
411          found = i;
412          founddist = dist;
413        }
414    }
415  }
416  // Store in pmap
417  if (pmap && pmap->size()<0x8000)
418    {
419      int key = (bgr[0]<<16)|(bgr[1]<<8)|(bgr[2]);
420      (*pmap)[key] = found;
421    }
422  // Return
423  return found;
424}
425
426
427#ifndef NEED_DECODER_ONLY
428
429void 
430DjVuPalette::quantize(GPixmap &pm)
431{
432  { // extra nesting for windows
433    for (int j=0; j<(int)pm.rows(); j++)
434    {
435      GPixel *p = pm[j];
436      for (int i=0; i<(int)pm.columns(); i++)
437        index_to_color(color_to_index(p[i]), p[i]);
438    }
439  }
440}
441
442int 
443DjVuPalette::compute_palette_and_quantize(GPixmap &pm, int maxcolors, int minboxsize)
444{
445  int result = compute_pixmap_palette(pm, maxcolors, minboxsize);
446  quantize(pm);
447  return result;
448}
449
450void 
451DjVuPalette::color_correct(double corr)
452{
453  const int palettesize = palette.size();
454  if (palettesize > 0)
455    {
456      // Copy colors
457      int i;
458      GTArray<GPixel> pix(0,palettesize-1);
459      GPixel *r = pix;
460      PColor *q = palette;
461      for (i=0; i<palettesize; i++) 
462        {
463          r[i].b = q[i].p[0];
464          r[i].g = q[i].p[1];
465          r[i].r = q[i].p[2];
466        }
467      // Apply color correction
468      GPixmap::color_correct(corr, r, palettesize);
469      // Restore colors
470      for (i=0; i<palettesize; i++) 
471        {
472          q[i].p[0] = r[i].b;
473          q[i].p[1] = r[i].g;
474          q[i].p[2] = r[i].r;
475        }
476    }
477}
478
479#endif
480
481
482// -------- ENCODE AND DECODE
483
484#define DJVUPALETTEVERSION 0
485
486void
487DjVuPalette::encode_rgb_entries(ByteStream &bs) const
488{
489  const int palettesize = palette.size();
490  { // extra nesting for windows
491    for (int c=0; c<palettesize; c++)
492    {
493      unsigned char p[3];
494      p[2] = palette[c].p[0];
495      p[1] = palette[c].p[1];
496      p[0] = palette[c].p[2];
497      bs.writall((const void*)p, 3);
498    }
499  }
500}
501
502void 
503DjVuPalette::encode(GP<ByteStream> gbs) const
504{
505  ByteStream &bs=*gbs;
506  const int palettesize = palette.size();
507  const int datasize = colordata.size();
508  // Code version number
509  int version = DJVUPALETTEVERSION;
510  if (datasize>0) version |= 0x80;
511  bs.write8(version);
512  // Code palette
513  bs.write16(palettesize);
514  { // extra nesting for windows
515    for (int c=0; c<palettesize; c++)
516    {
517      unsigned char p[3];
518      p[0] = palette[c].p[0];
519      p[1] = palette[c].p[1];
520      p[2] = palette[c].p[2];
521      bs.writall((const void*)p, 3);
522    }
523  }
524  // Code colordata
525  if (datasize > 0)
526    {
527      bs.write24(datasize);
528      GP<ByteStream> gbsb=BSByteStream::create(gbs, 50);
529      ByteStream &bsb=*gbsb;
530      for (int d=0; d<datasize; d++)
531        bsb.write16(colordata[d]);
532    }
533}
534
535void 
536DjVuPalette::decode_rgb_entries(ByteStream &bs, const int palettesize)
537{
538  palette.resize(0,palettesize-1);
539  { // extra nesting for windows
540    for (int c=0; c<palettesize; c++)
541    {
542      unsigned char p[3];
543      bs.readall((void*)p, 3);
544      palette[c].p[0] = p[2];
545      palette[c].p[1] = p[1];
546      palette[c].p[2] = p[0];
547      palette[c].p[3] = (p[0]*BMUL+p[1]*GMUL+p[2]*RMUL)/SMUL;
548    }
549  }
550}
551
552void 
553DjVuPalette::decode(GP<ByteStream> gbs)
554{
555  ByteStream &bs=*gbs;
556  // Make sure that everything is clear
557  delete hist;
558  delete pmap;
559  hist = 0;
560  pmap = 0;
561  mask = 0;
562  // Code version
563  int version = bs.read8();
564  if ( (version & 0x7f) != DJVUPALETTEVERSION)
565    G_THROW( ERR_MSG("DjVuPalette.bad_version") );
566  // Code palette
567  const int palettesize = bs.read16();
568  if (palettesize<0 || palettesize>MAXPALETTESIZE)
569    G_THROW( ERR_MSG("DjVuPalette.bad_palette") );
570  palette.resize(0,palettesize-1);
571  { // extra nesting for windows
572    for (int c=0; c<palettesize; c++)
573    {
574      unsigned char p[3];
575      bs.readall((void*)p, 3);
576      palette[c].p[0] = p[0];
577      palette[c].p[1] = p[1];
578      palette[c].p[2] = p[2];
579      palette[c].p[3] = (p[0]*BMUL+p[1]*GMUL+p[2]*RMUL)/SMUL;
580    }
581  }
582  // Code data
583  if (version & 0x80)
584    {
585      int datasize = bs.read24();
586      if (datasize<0)
587        G_THROW( ERR_MSG("DjVuPalette.bad_palette") );
588      colordata.resize(0,datasize-1);
589      GP<ByteStream> gbsb=BSByteStream::create(gbs);
590      ByteStream &bsb=*gbsb;
591      { // extra nesting for windows
592        for (int d=0; d<datasize; d++)
593        {
594          short s = bsb.read16();
595          if (s<0 || s>=palettesize)
596            G_THROW( ERR_MSG("DjVuPalette.bad_palette") );       
597          colordata[d] = s;
598        }
599      }
600    }
601}
602
603
604
605
606#ifdef HAVE_NAMESPACES
607}
608# ifndef NOT_USING_DJVU_NAMESPACE
609using namespace DJVU;
610# endif
611#endif
612
Note: See TracBrowser for help on using the repository browser.