source: trunk/libdjvu/ZPCodec.h @ 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: 34.4 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: ZPCodec.h,v 1.9 2003/11/07 22:08:22 leonb Exp $
55// $Name:  $
56
57#ifndef _ZPCODEC_H
58#define _ZPCODEC_H
59#ifdef HAVE_CONFIG_H
60#include "config.h"
61#endif
62#if NEED_GNUG_PRAGMAS
63# pragma interface
64#endif
65
66// From: Leon Bottou, 1/31/2002
67// Almost equal to my initial code.
68
69#include "GContainer.h"
70
71#ifdef HAVE_NAMESPACES
72namespace DJVU {
73# ifdef NOT_DEFINED // Just to fool emacs c++ mode
74}
75#endif
76#endif
77
78class ByteStream;
79
80
81
82/** @name ZPCodec.h
83   
84    Files #"ZPCodec.h"# and #"ZPCodec.cpp"# implement a fast binary adaptive
85    quasi-arithmetic coder named ZP-Coder.  Because of its speed and
86    convenience, the ZP-Coder is used in several parts of the DjVu reference
87    library (See \Ref{BSByteStream.h}, \Ref{JB2Image.h}, \Ref{IW44Image.h}).
88    The following comments avoid the theory (see the historical remarks for
89    useful pointers) and concentrate on the user perspective on the ZP-Coder.
90
91    {\bf Introduction} ---
92    Encoding consists of transforming a sequence of {\em message bits} into a
93    sequence of {\em code bits}. Decoding consists of retrieving the message
94    bits using only the code bits.  We can make the code smaller than the
95    message as soon as we can predict a message bit on the basis of a {\em
96    coding context} composed of previously encoded or decoded bits. If the
97    prediction is always correct, we do not even need to encode the message
98    bit. If the prediction is totally unreliable, we need to generate one code
99    bit in order to unambiguously specify the message bit.  In other words,
100    the more reliable the prediction, the more compression we get.
101
102    The ZP-Coder handles prediction by means of {\em context variables} (see
103    \Ref{BitContext}).  There must be a context variable for each possible
104    combination of context bits.  Both the encoder and the decoder use same
105    context variable for coding each message bit.  For instance, we can code a
106    binary image by successively coding all the pixels (the message bits) in
107    row and column order.  It is reasonable to assume that each pixel can be
108    reasonably well predicted by looking at a few (say 10) neighboring pixels
109    located above and to the left of the current pixel.  Since these 10 pixels
110    make 1024 combinations, we need 1024 context variables. Each pixel is
111    encoded using the context variable corresponding to the values of the 10
112    neighboring pixels.  Each pixel will be decoded by specifying the same
113    context variable corresponding to the values of these 10 pixels. This is
114    possible because these 10 pixels (located above and to the left) have
115    already been decoded and therefore are known by the decoder program.
116
117    The context variables are initially set to zero, which mean that we do not
118    know yet how to predict the current message bit on the basis of the
119    context bits. While coding the message bits, the ZP-Coder automatically
120    estimates the frequencies of #0#s and #1#s coded using each context
121    variable.  These frequencies actually provide a prediction (the most
122    probable bit value) and an estimation of the prediction reliability (how
123    often the prediction was correct in the past).  All this statistical
124    information is stored into the context variable after coding each bit.  In
125    other words, the more we code bits within a particular context, the better
126    the ZP-Coder adapts its prediction model, and the more compression we can
127    obtain.
128
129    All this adaptation works indeed because both the encoder program and the
130    decoder program are always synchronized. Both the encoder and the decoder
131    see the same message bits encoded (or decoded) with the same context
132    variables.  Both the encoder and the decoder apply the same rules to
133    update the context variables and improve the predictors.  Both the encoder
134    and the decoder programs use the same predictors for any given message
135    bit.  The decoder could not work if this was not the case.
136   
137    Just before encoding a message bit, all the context variables in the
138    encoder program contain certain values. Just before decoding this message
139    bit, all the context variables in the decoder program must contain the same
140    values as for the encoder program.  This is guaranteed as long as
141    each prediction only depends on already coded bits: {\em the coding context,
142    on which the each prediction is based, must be composed of message bits which
143    have already been coded. }
144
145    {\bf Usage} ---
146    Once you know how to organize the predictions (i.e. which coding context
147    to use, how many context variables to initialize, etc.), using the
148    ZP-Coder is straightforward (see \Ref{ZPCodec Examples}):
149    \begin{itemize}
150    \item The {\em encoder program} allocates context variables and
151    initializes them to zero. It then constructs a \Ref{ZPCodec} object for
152    encoding. For each message bit, the encoder program retrieves the context
153    bits, selects a context variable on the basis of the context bits and
154    calls member function \Ref{ZPCodec::encoder} with the message bit and a
155    reference to the context variable.
156    \item The {\em decoder program} allocates context variables and
157    initializes them to zero. It then constructs a \Ref{ZPCodec} object for
158    decoding. For each message bit, the decoder program retrieves the context
159    bits, selects a context variable on the basis of the context bits and
160    calls member function \Ref{ZPCodec::decoder} with a reference to the
161    context variable. This function returns the message bit.
162    \end{itemize}
163    Functions #encoder# and #decoder# only require a few machine cycles to
164    perform two essential tasks, namely {\em coding} and {\em context
165    adaptation}.  Function #decoder# often returns after two arithmetic
166    operations only.  To make your program fast, you just need to feed message
167    bits and context variables fast enough.
168
169    {\bf History} --- The ZP-Coder is similar in function and performance to
170    the seminal Q-Coder (Pennebaker, Mitchell, Langdon, Arps, IBM J. Res
171    Dev. 32, 1988). An improved version of the Q-Coder, named QM-Coder, has
172    been described in certain parts of the JPEG standard.  Unfortunate patent
173    policies have made these coders very difficult to use in general purpose
174    applications.  The Z-Coder is constructed using a new approach based on an
175    extension of the Golomb codes (Bottou, Howard, Bengio, IEEE DCC 98, 1998
176    \URL[DjVu]{http://www.research.att.com/~leonb/DJVU/bottou-howard-bengio/}
177    \URL[PostScript]{http://www.research.att.com/~leonb/PS/bottou-howard-bengio.ps.gz})
178    This new approach does not infringe the QM-Coder patents.  Unfortunately
179    the Z-Coder is dangerously close to the patented Arithmetic MEL Coder.
180    Therefore we wrote the ZP-Coder (pronounce Zee-Prime Coder) which we
181    believe is clear of legal problems.  Needless to say, AT&T has patents
182    pending for both the Z-Coder and the ZP-Coder, licenced to LizardTech.
183    The good news however is that we can grant a license to use the ZP-Coder
184    in ``free software'' without further complication. See the Copyright
185    for more information.
186   
187    @memo
188    Binary adaptive quasi-arithmetic coder.
189    @version
190    #$Id: ZPCodec.h,v 1.9 2003/11/07 22:08:22 leonb Exp $#
191    @author
192    L\'eon Bottou <leonb@research.att.com> */
193//@{
194
195
196/** Context variable. 
197    Variables of type #BitContext# hold a single byte describing how to encode
198    or decode message bits with similar statistical properties.  This single
199    byte simultaneously represents the current estimate of the bit probability
200    distribution (which is determined by the frequencies of #1#s and #0#s
201    already coded with this context) and the confidence in this estimate
202    (which determines how fast the estimate can change.)
203
204    A coding program typically allocates hundreds of context variables.  Each
205    coding context is initialized to zero before encoding or decoding.  Value
206    zero represents equal probabilities for #1#s and #0#s with a minimal
207    confidence and therefore a maximum adaptation speed.  Each message bit is
208    encoded using a coding context determined as a function of previously
209    encoded message bits.  The decoder therefore can examine the previously
210    decoded message bits and decode the current bit using the same context as
211    the encoder.  This is critical for proper decoding. 
212*/
213typedef unsigned char  BitContext;
214
215
216/** Performs ZP-Coder encoding and decoding.  A ZPCodec object must either
217    constructed for encoding or for decoding.  The ZPCodec object is connected
218    with a \Ref{ByteStream} object specified at construction time.  A ZPCodec
219    object constructed for decoding reads code bits from the ByteStream and
220    returns a message bit whenever function \Ref{decoder} is called.  A
221    ZPCodec constructed for encoding processes the message bits provided by
222    function \Ref{encoder} and writes the corresponding code bits to
223    ByteStream #bs#.
224
225    You should never directly access a ByteStream object connected to a valid
226    ZPCodec object. The most direct way to access the ByteStream object
227    consists of using the "pass-thru" versions of functions \Ref{encoder} and
228    \Ref{decoder}.
229
230    The ByteStream object can be accessed again after the destruction of the
231    ZPCodec object.  Note that the encoder always flushes its internal buffers
232    and writes a few final code bytes when the ZPCodec object is destroyed.
233    Note also that the decoder often reads a few bytes beyond the last code byte
234    written by the encoder.  This lag means that you must reposition the
235    ByteStream after the destruction of the ZPCodec object and before re-using
236    the ByteStream object (see \Ref{IFFByteStream}.)
237
238    Please note also that the decoder has no way to reliably indicate the end
239    of the message bit sequence.  The content of the message must be designed
240    in a way which indicates when to stop decoding.  Simple ways to achieve
241    this consists of announcing the message length at the beginning (like a
242    pascal style string), or of defining a termination code (like a null
243    terminated string).  */
244
245class ZPCodec : public GPEnabled {
246protected:
247  ZPCodec (GP<ByteStream> gbs, const bool encoding, const bool djvucompat=false);
248public:
249  class Encode;
250  class Decode;
251
252  /// Non-virtual destructor.
253  ~ZPCodec();
254  /** Constructs a ZP-Coder.  If argument #encoding# is zero, the ZP-Coder
255      object will read code bits from the ByteStream #bs# and return a message
256      bit whenever function #decoder# is called.  If flag #encoding# is set
257      the ZP-Coder object will process the message bits provided by function
258      #encoder# and write code bits to ByteStream #bs#.  Optional flag
259      #djvucompat# selects a slightly less efficient adaptation table which is
260      used by the DjVu project.  This is required in order to ensure the
261      bitstream compatibility.  You should not use this flag unless you want
262      to decode JB2, IW44 or BZZ encoded data. */
263  static GP<ZPCodec> create(
264     GP<ByteStream> gbs, const bool encoding, const bool djvucompat=false);
265
266  /** Encodes bit #bit# using context variable #ctx#.  Argument #bit# must be
267      #0# or #1#. This function should only be used with ZP-Coder objects
268      created for encoding. It may modify the contents of variable #ctx# in
269      order to perform context adaptation. */
270  void encoder(int bit, BitContext &ctx);
271
272  /** Decodes a bit using context variable #ctx#. This function should only be
273      used with ZP-Coder objects created for decoding. It may modify the
274      contents of variable #ctx# in order to perform context adaptation. */
275  int  decoder(BitContext &ctx);
276
277  /** Encodes bit #bit# without compression (pass-thru encoder).  Argument
278      #bit# must be #0# or #1#. No compression will be applied. Calling this
279      function always increases the length of the code bit sequence by one
280      bit. */
281  void encoder(int bit);
282
283  /** Decodes a bit without compression (pass-thru decoder).  This function
284      retrieves bits encoded with the pass-thru encoder. */
285  int  decoder(void);
286#ifdef ZPCODEC_BITCOUNT
287  /** Counter for code bits (requires #-DZPCODEC_BITCOUNT#). This member
288      variable is available when the ZP-Coder is compiled with option
289      #-DZPCODEC_BITCOUNT#.  Variable #bitcount# counts the number of code
290      bits processed by the coder since the construction of the object.  This
291      variable can be used to evaluate how many code bits are spent on various
292      components of the message. */
293  int bitcount;
294#endif
295  // Table management (advanced stuff)
296  struct Table { 
297    unsigned short p;
298    unsigned short m;
299    BitContext     up;
300    BitContext     dn;
301  };
302  void newtable(ZPCodec::Table *table);
303  BitContext state(float prob1);
304  // Non-adaptive encoder/decoder
305  void encoder_nolearn(int pix, BitContext &ctx);
306  int  decoder_nolearn(BitContext &ctx);
307  inline int  IWdecoder(void);
308  inline void IWencoder(const bool bit);
309protected:
310  // coder status
311  GP<ByteStream> gbs;           // Where the data goes/comes from
312  ByteStream *bs;               // Where the data goes/comes from
313  const bool encoding;          // Direction (0=decoding, 1=encoding)
314  unsigned char byte;
315  unsigned char scount;
316  unsigned char delay;
317  unsigned int  a;
318  unsigned int  code;
319  unsigned int  fence;
320  unsigned int  subend;
321  unsigned int  buffer;
322  unsigned int  nrun;
323  // table
324  unsigned int  p[256];
325  unsigned int  m[256];
326  BitContext    up[256];
327  BitContext    dn[256];
328  // machine independent ffz
329  char          ffzt[256];
330  // encoder private
331  void einit (void);
332  void eflush (void);
333  void outbit(int bit);
334  void zemit(int b);
335  void encode_mps(BitContext &ctx, unsigned int z);
336  void encode_lps(BitContext &ctx, unsigned int z);
337  void encode_mps_simple(unsigned int z);
338  void encode_lps_simple(unsigned int z);
339  void encode_mps_nolearn(unsigned int z);
340  void encode_lps_nolearn(unsigned int z);
341  // decoder private
342  void dinit(void);
343  void preload(void);
344  int  ffz(unsigned int x);
345  int  decode_sub(BitContext &ctx, unsigned int z);
346  int  decode_sub_simple(int mps, unsigned int z);
347  int  decode_sub_nolearn(int mps, unsigned int z);
348private:
349  // no copy allowed (hate c++)
350  ZPCodec(const ZPCodec&);
351  ZPCodec& operator=(const ZPCodec&);
352#ifdef ZPCODEC_FRIEND
353  friend ZPCODEC_FRIEND;
354#endif
355};
356
357
358
359
360
361
362// INLINE CODE
363
364inline void 
365ZPCodec::encoder(int bit, BitContext &ctx) 
366{
367  unsigned int z = a + p[ctx];
368  if (bit != (ctx & 1))
369  {
370    encode_lps(ctx, z);
371  }else if (z >= 0x8000)
372  {
373    encode_mps(ctx, z);
374  }else
375  {
376    a = z;
377  }
378}
379
380inline int
381ZPCodec::IWdecoder(void)
382{
383  return decode_sub_simple(0,0x8000 + ((a+a+a) >> 3));
384}
385
386inline int
387ZPCodec::decoder(BitContext &ctx) 
388{
389  unsigned int z = a + p[ctx];
390  if (z <= fence) 
391    { a = z; return (ctx&1); } 
392  return decode_sub(ctx, z);
393}
394
395inline void 
396ZPCodec::encoder_nolearn(int bit, BitContext &ctx) 
397{
398  unsigned int z = a + p[ctx];
399  if (bit != (ctx & 1))
400    encode_lps_nolearn(z);
401  else if (z >= 0x8000)
402    encode_mps_nolearn(z);
403  else
404    a = z;
405}
406
407inline int
408ZPCodec::decoder_nolearn(BitContext &ctx) 
409{
410  unsigned int z = a + p[ctx];
411  if (z <= fence) 
412    { a = z; return (ctx&1); } 
413  return decode_sub_nolearn( (ctx&1), z);
414}
415
416inline void 
417ZPCodec::encoder(int bit)
418{
419  if (bit)
420    encode_lps_simple(0x8000 + (a>>1));
421  else
422    encode_mps_simple(0x8000 + (a>>1));
423}
424
425inline int
426ZPCodec::decoder(void)
427{
428  return decode_sub_simple(0, 0x8000 + (a>>1));
429}
430
431inline void
432ZPCodec::IWencoder(const bool bit)
433{
434  const int z = 0x8000 + ((a+a+a) >> 3);
435  if (bit)
436  {
437    encode_lps_simple(z);
438  }else
439  {
440    encode_mps_simple(z);
441  }
442}
443
444// ------------ ADDITIONAL DOCUMENTATION
445
446/** @name ZPCodec Examples
447   
448    Binary adaptive coders are efficient and very flexible.  Unfortunate
449    intellectual property issues however have limited their popularity.  As a
450    consequence, few programmers have a direct experience of using such a
451    coding device.  The few examples provided in this section demonstrate how
452    we think the ZP-Coder should be used.
453   
454    {\bf Encoding Multivalued Symbols} ---
455    Since the ZP-Coder is a strictly binary coder, every message must be
456    reduced to a sequence of bits (#0#s or #1#s).  It is often convenient to
457    consider that a message is a sequence of symbols taking more than two
458    values.  For instance, a character string may be a sequence of bytes, and
459    each byte can take 256 values.  Each byte of course is composed of eight
460    bits that we can encode in sequence.  The real issue however consists of
461    deciding how we will use context variables in order to let the ZP-Coder
462    learn the probability distribution of the byte values.
463
464    The most significant bit #b0# decides whether the byte is in range 0..127
465    or in range 128..255.  We let the ZP-Coder learn how to predict this bit
466    by allocating one context variable for it.  The second most significant
467    byte #b1# has two distinct meanings depending of bit #b0#.  If bit #b0# is
468    #0#, bit #b1# decides whether the byte is in range 0..63 or 64..127.  If
469    bit #b0# is #1#, bit #b1# decides whether the byte is in range 128..191 or
470    192..255.  The prediction for bit #b1# must therefore depend on the value
471    of #b0#.  This is why we will allocate two context variables for this bit.
472    If bit #b0# is #0#, we will use the first variable; if bit #b0# is #1#, we
473    will use the second variable.  The next bit #b2# has four meanings and
474    therefore we will use four context variables, etc.  This analysis leads to
475    a total of #1+2+4+...+128# = #255# context variables for encoding one
476    byte.  This encoding procedure can be understood as a binary decision
477    tree with a dedicated context variable for predicting each decision.
478    \begin{verbatim}
479    [>=128]----n---[>=64?]----n----[>31?]  ...
480           \              `---y----[>95?]  ...
481            \
482             `--y---[>=192?]----n---[>=160?] ...
483                            `---y---[>=224?] ...
484    \end{verbatim}
485    The following decoding function illustrates a very compact way to
486    implement such a decision tree.  Argument #ctx# points to an array of 255
487    #BitContext# variables.  Macro #REPEAT8# is a shorthand notation for eight
488    repetitions of its argument. 
489    \begin{verbatim}
490    int decode_8_bits(ZPCodec &zp, BitContext *ctx )
491    {
492      int n = 1;
493      REPEAT8( { n = (n<<1) | (zp.decoder(ctx[n-1])); } );
494      return n & 0xff;
495    }
496    \end{verbatim}
497    The binary representation of variable #n# is always composed of a #1#
498    followed by whichever bits have been decoded so far. This extra bit #1# in
499    fact is a nice trick to flatten out the tree structure and directly
500    address the array of context variables.  Bit #b0# is decoded using the
501    first context variable since #n# is initially #1#.  Bit #b1# is decoded
502    using one of the next two variables in the array, since #n# is either #2#
503    (#10# in binary) or #3# (#11# in binary).  Bit #b2# will be decoded using
504    one of the next four variables, since #n# ranges from #4# (#100# in
505    binary) to #7# (#111# in binary).  The final result is given by removing
506    the extra #1# in variable #n#.
507
508    The corresponding encoding function is almost as compact. Argument #ctx#
509    again is an array of 255 #BitContext# variables.  Each bit of byte #x# is
510    encoded and shifted into variable #n# as in the decoding function.
511    Variable #x# in fact contains the bits to be encoded. Variable #n#
512    contains a #1# followed by the already encoded bits.
513    \begin{verbatim}
514    void encode_8_bits(ZPCodec &zp, int x, BitContext *ctx )
515    {
516      int n = 1;
517      REPEAT8( { int b=((x&0x80)?1:0);  x=(x<<1);
518                 zp.encoder(b,ctx[n-1]);  n=(n<<1)|(b); } );
519    }
520    \end{verbatim}
521    The ZP-Coder automatically adjusts the content of the context variables
522    while coding (recall the context variable argument is passed to functions
523    #encoder# and #decoder# by reference).  The whole array of 255 context
524    variables can be understood as a "byte context variable".  The estimated
525    probability of each byte value is indeed the product of the estimated
526    probabilities of the eight binary decisions that lead to that value in the
527    decision tree.  All these probabilities are adapted by the underlying
528    adaptation algorithm of the ZP-Coder.
529
530    {\bf Application} ---
531    We consider now a simple applications consisting of encoding the
532    horizontal and vertical coordinates of a cloud of points. Each coordinate
533    requires one byte.  The following function illustrates a possible
534    implementation:
535    \begin{verbatim}
536    void encode_points(const char *filename, int n, int *x, int *y)
537    {
538       StdioByteStream bs(filename, "wb");
539       bs.write32(n);             // Write number of points.
540       ZPCodec zp(bs, 1);         // Construct encoder and context vars.
541       BitContext ctxX[255], ctxY[255];
542       memset(ctxX, 0, sizeof(ctxX));
543       memset(ctxY, 0, sizeof(ctxY));
544       for (int i=0; i<n; i++) {  // Encode coordinates.
545          encode_8_bits(zp, x[i], ctxX);
546          encode_8_bits(zp, y[i], ctxY);
547       }
548    }
549    \end{verbatim}
550    The decoding function is very similar to the encoding function:
551    \begin{verbatim}
552    int decode_points(const char *filename, int *x, int *y)
553    {
554       StdioByteStream bs(filename,"rb");
555       int n = bs.read32();      // Read number of points.
556       ZPCodec zp(bs, 0);        // Construct decoder and context vars.
557       BitContext ctxX[255], ctxY[255];
558       memset(ctxX, 0, sizeof(ctxX));
559       memset(ctxY, 0, sizeof(ctxY));
560       for (int i=0; i<n; i++) { // Decode coordinates.
561         x[i] = decode_8_bits(zp, ctxX);
562         y[i] = decode_8_bits(zp, ctxY);
563       }
564       return n;                 // Return number of points.
565    }
566    \end{verbatim}
567    The ZP-Coder automatically estimates the probability distributions of both
568    the horizontal and vertical coordinates. These estimates are used to
569    efficiently encode the point coordinates.  This particular implementation
570    is a good option if we assume that the order of the points is significant
571    and that successive points are independent.  It would be much smarter
572    otherwise to sort the points and encode relative displacements between
573    successive points.
574
575
576    {\bf Huffman Coding Tricks} ---
577    Programmers with experience in Huffman codes can see the similarity in the
578    ZP-Coder.  Huffman codes also organize the symbol values as a decision
579    tree. The tree is balanced in such a way that each decision is as
580    unpredictable as possible (i.e. both branches must be equally probable).
581    This is very close to the ZP-Coder technique described above.  Since we
582    allocate one context variable for each decision, our tree need not be
583    balanced: the context variable will track the decision statistics and the
584    ZP-Coder will compensate optimally.
585
586    There are good reasons however to avoid unbalanced trees with the ZP-Coder.
587    Frequent symbol values may be located quite deep in a poorly balanced
588    tree.  This increases the average number of message bits (the number of
589    decisions) required to code a symbol.  The ZP-Coder will be called more
590    often, making the coding program slower.  Furthermore, each message
591    bit is encoded using an estimated distribution.  All these useless message
592    bits mean that the ZP-Coder has more distributions to adapt.  This
593    extra adaptation work will probably increase the file size.
594
595    Huffman codes are very fast when the tree structure is fixed beforehand.
596    Such {\em static Huffman codes} are unfortunately not very efficient
597    because the tree never matches the actual data distribution.  This is why
598    such programs almost always define a data dependent tree structure.  This
599    structure must then be encoded in the file since the decoder must know it
600    before decoding the symbols.  Static Huffman codes however become very
601    efficient when decisions are encoded with the ZP-Coder.  The tree
602    structure represents a priori knowledge about the distribution of the
603    symbol values.  Small data discrepancies will be addressed transparently
604    by the ZP-Coder.
605
606
607    {\bf Encoding Numbers} ---
608    This technique is illustrated with the following number encoding example.
609    The multivalued technique described above is not practical with large
610    numbers because the decision tree has too many nodes and requires too many
611    context variables.  This problem can be solved by using a priori knowledge
612    about the probability distribution of our numbers.
613
614    Assume for instance that the distribution is symmetrical and that small
615    numbers are much more probable than large numbers.  We will first group
616    our numbers into several sets.  Each number is coded by first coding which
617    set contains the number and then coding a position within the set.  Each
618    set contains #2^n# numbers that we consider roughly equiprobable.  Since
619    the most probable values occur much more often, we want to model their
620    probability more precisely. Therefore we use small sets for the most
621    probable values and large sets for the least probable values, as
622    demonstrated below.
623    \begin{verbatim}
624    A---------------- {0}                                 (size=1)
625     `------B---C---- {1}            or {-1}              (size=1)
626             \   `--- {2,3}          or {-2,-3}           (size=2)
627              D------ {4...131}      or {-4...-131}       (size=128)
628               `----- {132...32899}  or {-132...-32899}   (size=32768)
629    \end{verbatim}
630    We then organize a decision tree for coding the set identifier.  This
631    decision tree is balanced using whatever a priori knowledge we have about
632    the probability distribution of the number values, just like a static
633    Huffman tree.  Each decision (except the sign decision) is then coded
634    using a dedicated context variable.
635    \begin{verbatim}
636        if (! zp.decoder(ctx_A)) {             // decision A
637           return 0;
638        } else {
639           if (! zp.decoder(ctx_B)) {          // + decision B
640             if (! zp.decoder(ctx_C)) {        // ++ decision C
641               if (! zp.decoder())             // +++ sign decision
642                 return +1;
643               else
644                 return -1;
645             } else {
646               if (! zp.decoder())             // +++ sign decision
647                 return + 2 + zp.decoder();
648               else
649                 return - 2 - zp.decoder();
650             }
651           } else {
652             if (! zp.decoder(ctx_D)) {        // ++ decision D
653               if (! zp.decoder())             // +++ sign decision
654                 return + 4 + decode_7_bits(zp);
655               else
656                 return - 4 - decode_7_bits(zp);
657             } else {
658               if (! zp.decoder())             // +++ sign decision
659                 return + 132 + decode_15_bits(zp);
660               else
661                 return - 132 - decode_15_bits(zp);
662             }
663           }
664        }
665   \end{verbatim}
666   Note that the call #zp.decoder()# for coding the sign decision does not use
667   a context variable.  This is a "pass-thru" variant of \Ref{decoder} which
668   bypasses the ZP-Coder and just reads a bit from the code sequence.  There
669   is a corresponding "pass-thru" version of \Ref{encoder} for encoding such
670   bits.  Similarly, functions #decode_7_bits# and #decode_15_bits# do not
671   take an array of context variables because, unlike function #decode_8_bits#
672   listed above, they are based on the pass-thru decoder instead of the
673   regular decoder.
674
675   The ZP-Coder will not learn the probabilities of the numbers within a set
676   since no context variables have been allocated for that purpose.  This
677   could be improved by allocating additional context variables for encoding
678   the position within the smaller sets and using the regular decoding
679   functions instead of the pass-thru variants.  Only experimentation can tell
680   what works best for your particular encoding problem.
681
682
683   {\bf Understanding Adaptation} ---
684   We have so far explained that the ZP-Coder adaptation algorithm is able to
685   quickly estimate of the probability distribution of the message bits coded
686   using a particular context variable.  It is also able to track slow
687   variations when the actual probabilities change while coding.
688   
689   Let us consider the ``cloud of points'' application presented above.
690   Suppose that we first code points located towards the left side and then
691   slowly move towards points located on the right side.  The ZP-Coder will
692   first estimate that the X coordinates are rather on the left side. This
693   estimation will be progressively revised after seeing more points on the
694   right side.  Such an ordering of the points obviously violates the point
695   independence assumption on which our code is based.  Despite our inexact
696   assumptions, the tracking mechanism allows for better prediction of the X
697   coordinates and therefore better compression.
698
699   However, this is not a perfect solution. The ZP-Coder tracks the changes
700   because every point seems to be a little bit more on the right side than
701   suggested by the previous points.  The ZP-Coder coding algorithm is always
702   slightly misadjusted and we always lose a little on possible compression
703   ratio.  This is not much of a problem when the probabilities drift slowly.
704   On the other hand, this can be very significant if the probabilities change
705   drastically.
706
707   Adaptation is always associated with a small loss of efficiency.  The
708   ZP-Coder updates the probability model whenever it suspects, {\em after
709   coding}, that the current settings were not optimal.  The model will be
710   better next time, but a slight loss in compression has occurred.  The
711   design of ZP-Coder of course minimizes this effect as much as possible.
712   Yet you will pay a price if you ask too much to the adaptation algorithm.
713   If you have millions of context variables, it will be difficult to train
714   them all.  If the probability distributions change drastically while
715   coding, it will be difficult to track the changes fast enough.
716
717   Adaptation on the other hand is a great simplification.  A good data
718   compression program must (a) represent the data in order to make its
719   predictability apparent, and (b) perform the predictions and generate the
720   code bits.  The ZP-Coder is an efficient and effortless solution for
721   implementing task (b).
722
723
724   {\bf Practical Debugging Tricks} ---
725   Sometimes you write an encoding program and a decoding program.
726   Unfortunately there is a bug: the decoding program decodes half the file
727   and then just outputs garbage.  There is a simple way to locate the
728   problem.  In the encoding program, after each call to #encoder#, print the
729   encoded bit and the value of the context variable.  In the decoding
730   program, after each call to #decoder#, print the decoded bit and the value
731   of the context variable.  Both program should print exactly the same thing.
732   When you find the difference, you find the bug.
733   
734   @memo Suggestions for efficiently using the ZP-Coder.  */
735//@}
736
737// ------------ THE END
738
739#ifdef HAVE_NAMESPACES
740}
741# ifndef NOT_USING_DJVU_NAMESPACE
742using namespace DJVU;
743# endif
744#endif
745#endif
746
747
Note: See TracBrowser for help on using the repository browser.