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 #ifndef _DJVUPALETTE_H_
57 #define _DJVUPALETTE_H_
58 #ifdef HAVE_CONFIG_H
59 #include "config.h"
60 #endif
61 #if NEED_GNUG_PRAGMAS
62 # pragma interface
63 #endif
64
65
66 #include "GContainer.h"
67 #include "GPixmap.h"
68 #include <string.h>
69
70
71 #ifdef HAVE_NAMESPACES
72 namespace DJVU {
73 # ifdef NOT_DEFINED // Just to fool emacs c++ mode
74 }
75 #endif
76 #endif
77
78
79 /** @name DjVuPalette.h
80 Files #"DjVuPalette.h"# and #"DjVuPalette.cpp"# implement a single class
81 \Ref{DjVuPalette} which provides facilities for computing optimal color
82 palettes, coding color palettes, and coding sequences of color indices.
83 @memo
84 DjVuPalette header file
85 @author:
86 L\'eon Bottou <leonb@research.att.com> */
87 //@{
88
89
90 /** Computing and coding color palettes and index arrays.
91 This class provides facilities for computing optimal color palettes,
92 coding color palettes, and coding sequences of color indices.
93
94 {\bf Creating a color palette} -- The recipe for creating a color palette
95 consists in (a) creating a DjVuPalette object, (b) constructing a color
96 histogram using \Ref{histogram_add}, and (c) calling function
97 \Ref{compute_palette}.
98
99 {\bf Accessing the color palette} -- Conversion between colors and color
100 palette indices is easily achieved with \Ref{color_to_index} and
101 \Ref{index_to_color}. There are also functions for computing a palette
102 and quantizing a complete pixmap.
103
104 {\bf Sequences of color indices} -- The DjVuPalette object also contains
105 an array \Ref{colordata} optionally containing a sequence of color
106 indices. This array will be encoded and decoded by functions \Ref{encode}
107 and \Ref{decode}. This feature simplifies the implementation of the ``one
108 color per symbol'' model in DjVu.
109
110 {\bf Coding color palettes and color indices} -- Two functions
111 \Ref{encode} and \Ref{decode} are provided for coding the color palette
112 and the array of color indices when appropriate. */
113 #ifdef _WIN32_WCE_EMULATION // Work around odd behavior under WCE Emulation
114 #define CALLINGCONVENTION __cdecl
115 #else
116 #define CALLINGCONVENTION /* */
117 #endif
118
119 class DJVUAPI DjVuPalette : public GPEnabled
120 {
121 protected:
122 DjVuPalette(void);
123 public:
124 /// Generic creator
create(void)125 static GP<DjVuPalette> create(void) {return new DjVuPalette();}
126
127 /// Non-virtual destructor
128 ~DjVuPalette();
129 // COPY
130 DjVuPalette(const DjVuPalette &ref);
131 DjVuPalette& operator=(const DjVuPalette &ref);
132 // PALETTE COMPUTATION
133 /** Resets the color histogram to zero. */
134 void histogram_clear();
135 /** Adds the color specified by #p# to the histogram.
136 Argument #weight# represent the number of pixels with this color. */
137 void histogram_add(const GPixel &p, int weight);
138 /** Adds the color specified by the triple #bgr# to the histogram.
139 Argument #weight# represent the number of pixels with this color. */
140 void histogram_add(const unsigned char *bgr, int weight);
141 /** Adds the color specified by the weighted triple #bgr# to the histogram.
142 Argument #weight# represent the number of pixels with this color. This
143 function will compute the actual color by dividing the elements of the
144 #bgr# array by #weight# and then use the unnormalized values to compute
145 the average color per bucket. This is all a way to avoid excessive loss
146 of accuracy. */
147 void histogram_norm_and_add(const int *bgr, int weight);
148 /** Computes an optimal palette for representing an image where colors
149 appear according to the histogram. Argument #maxcolors# is the maximum
150 number of colors allowed in the palette (up to 1024). Argument
151 #minboxsize# controls the minimal size of the color cube area affected
152 to a color palette entry. Returns the index of the dominant color. */
153 int compute_palette(int maxcolors, int minboxsize=0);
154 /** Computes the optimal palette for pixmap #pm#. This function builds the
155 histogram for pixmap #pm# and computes the optimal palette using
156 \Ref{compute_palette}. */
157 int compute_pixmap_palette(const GPixmap &pm, int ncolors, int minboxsize=0);
158 // CONVERSION
159 /** Returns the number of colors in the palette. */
160 int size() const;
161 /** Returns the best palette index for representing color #p#. */
162 int color_to_index(const GPixel &p);
163 /** Returns the best palette index for representing color #bgr#. */
164 int color_to_index(const unsigned char *bgr);
165 /** Overwrites #p# with the color located at position #index# in the palette. */
166 void index_to_color(int index, GPixel &p) const;
167 /** Overwrites #rgb[0..3]# with the color located at
168 position #index# in the palette. */
169 void index_to_color(int index, unsigned char *bgr) const;
170 /** Quantizes pixmap #pm#. All pixels are replaced by their closest
171 approximation available in the palette. */
172 void quantize(GPixmap &pm);
173 /** Calls \Ref{compute_pixmap_palette} and \Ref{quantize}. */
174 int compute_palette_and_quantize(GPixmap &pm, int maxcolors, int minboxsize=0);
175 // COLOR CORRECTION
176 /** Applies a luminance gamma correction factor of #corr# to the palette
177 entries. Values greater than #1.0# make the image brighter. Values
178 smaller than #1.0# make the image darker. The documentation of program
179 \Ref{ppmcoco} explains how to properly use this function. */
180 void color_correct(double corr);
181 // COLOR INDEX DATA
182 /** Contains an optional sequence of color indices.
183 Function \Ref{encode} and \Ref{decode} also encode and decode this
184 sequence when such a sequence is provided. */
185 GTArray<short> colordata;
186 /** Returns colors from the color index sequence. Pixel #out# is
187 overwritten with the color corresponding to the #nth# element of the
188 color sequence \Ref{colordata}. */
189 void get_color(int nth, GPixel &out) const;
190 // CODING
191 /** Writes the palette colors. This function writes each palette color as a
192 RGB triple into bytestream #bs#. */
193 void encode_rgb_entries(ByteStream &bs) const;
194 /** Reads palette colors. This function initializes the palette colors by
195 reading #palettesize# RGB triples from bytestream #bs#. */
196 void decode_rgb_entries(ByteStream &bs, const int palettesize);
197 /** Encodes the palette and the color index sequence. This function encodes
198 the a version byte, the palette size, the palette colors and the color
199 index sequence into bytestream #bs#. Note that the color histogram is
200 never saved. */
201 void encode(GP<ByteStream> bs) const;
202 /** Initializes the object by reading data from bytestream #bs#. This
203 function reads a version byte, the palette size, the palette and the
204 color index sequence from bytestream #bs#. Note that the color
205 histogram is never saved. */
206 void decode(GP<ByteStream> bs);
207
208 private:
209 // Histogram
210 int mask;
211 GMap<int,int> *hist;
212 // Quantization data
213 struct PColor { unsigned char p[4]; };
214 GTArray<PColor> palette;
215 GMap<int,int> *pmap;
216 // Helpers
217 void allocate_hist();
218 void allocate_pmap();
219 static int CALLINGCONVENTION bcomp (const void*, const void*);
220 static int CALLINGCONVENTION gcomp (const void*, const void*);
221 static int CALLINGCONVENTION rcomp (const void*, const void*);
222 static int CALLINGCONVENTION lcomp (const void*, const void*);
223 int color_to_index_slow(const unsigned char *bgr);
224 private: // dummy functions
225 static void encode(ByteStream *);
226 static void decode(ByteStream *);
227 };
228
229
230 //@}
231
232 // ------------ INLINES
233
234
235 inline void
histogram_clear()236 DjVuPalette::histogram_clear()
237 {
238 delete hist;
239 hist = 0;
240 mask = 0;
241 }
242
243 inline void
histogram_add(const unsigned char * bgr,int weight)244 DjVuPalette::histogram_add(const unsigned char *bgr, int weight)
245 {
246 if (weight > 0)
247 {
248 if (!hist || hist->size()>=0x4000)
249 allocate_hist();
250 int key = (bgr[0]<<16)|(bgr[1]<<8)|(bgr[2])|(mask);
251 (*hist)[key] += weight;
252 }
253 }
254
255 inline void
histogram_add(const GPixel & p,int weight)256 DjVuPalette::histogram_add(const GPixel &p, int weight)
257 {
258 histogram_add(&p.b, weight);
259 }
260
261 inline void
histogram_norm_and_add(const int * bgr,int weight)262 DjVuPalette::histogram_norm_and_add(const int *bgr, int weight)
263 {
264 if (weight > 0)
265 {
266 int p0 = bgr[0]/weight; if (p0>255) p0=255;
267 int p1 = bgr[1]/weight; if (p1>255) p1=255;
268 int p2 = bgr[2]/weight; if (p2>255) p2=255;
269 if (!hist || hist->size()>=0x4000)
270 allocate_hist();
271 int key = (p0<<16)|(p1<<8)|(p2)|(mask);
272 (*hist)[key] += weight;
273 }
274 }
275
276 inline int
size()277 DjVuPalette::size() const
278 {
279 return palette.size();
280 }
281
282 inline int
color_to_index(const unsigned char * bgr)283 DjVuPalette::color_to_index(const unsigned char *bgr)
284 {
285 if (! pmap)
286 allocate_pmap();
287 int key = (bgr[0]<<16)|(bgr[1]<<8)|(bgr[2]);
288 GPosition p = pmap->contains(key);
289 if ( p)
290 return (*pmap)[p];
291 return color_to_index_slow(bgr);
292 }
293
294 inline int
color_to_index(const GPixel & p)295 DjVuPalette::color_to_index(const GPixel &p)
296 {
297 return color_to_index(&p.b);
298 }
299
300 inline void
index_to_color(int index,unsigned char * bgr)301 DjVuPalette::index_to_color(int index, unsigned char *bgr) const
302 {
303 const PColor &color = palette[index];
304 bgr[0] = color.p[0];
305 bgr[1] = color.p[1];
306 bgr[2] = color.p[2];
307 }
308
309 inline void
index_to_color(int index,GPixel & p)310 DjVuPalette::index_to_color(int index, GPixel &p) const
311 {
312 index_to_color(index, &p.b);
313 }
314
315 inline void
get_color(int nth,GPixel & p)316 DjVuPalette::get_color(int nth, GPixel &p) const
317 {
318 index_to_color(colordata[nth], p);
319 }
320
321
322
323 // ------------ THE END
324
325 #ifdef HAVE_NAMESPACES
326 }
327 # ifndef NOT_USING_DJVU_NAMESPACE
328 using namespace DJVU;
329 # endif
330 #endif
331 #endif
332
333
334
335
336
337