source: trunk/libdjvu/DjVuPalette.cpp @ 206

Last change on this file since 206 was 206, checked in by Eugene Romanenko, 14 years ago

DJVU plugin: djvulibre updated to version 3.5.19

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