libit

00001 /*
00002    libit - Library for basic source and channel coding functions
00003    Copyright (C) 2005-2008 Francois Cayre, Vivien Chappelier, Herve Jegou
00004 
00005    This library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Library General Public
00007    License as published by the Free Software Foundation; either
00008    version 2 of the License, or (at your option) any later version.
00009 
00010    This library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Library General Public License for more details.
00014 
00015    You should have received a copy of the GNU Library General Public
00016    License along with this library; if not, write to the Free
00017    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 
00020 /*
00021   Base class for quantization.
00022   Vivien Chappelier <vivien.chappelier@irisa.fr>
00023 */
00024 
00025 #ifndef __it_quantizer_h
00026 #define __it_quantizer_h
00027 
00028 #include <it/types.h>
00029 #include <it/vec.h>
00030 #include <it/mat.h>
00031 #include <it/convcode.h>  /* needed for TCQ */
00032 
00033 /*---------------------------------------------------------------------------*/
00034 /*! \defgroup quantization Quantization                                      */
00035 /* @{                                                                        */
00036 /*---------------------------------------------------------------------------*/
00037 
00038 /* Generic vector quantizer class */
00039   typedef struct _quantizer_ {
00040     it_extends (it_object_t);
00041 
00042     /* Quantize a vector v to a vector of indexes */
00043     ivec (*quantize) (struct _quantizer_ * quantizer, vec v);
00044 
00045     /* Dequantize the indices to the reconstruction vector */
00046     vec (*dequantize) (struct _quantizer_ * quantizer, ivec Q);
00047 
00048     /* Return the cardinal of the codebook (0 means infinite or too large) */
00049     unsigned int (*get_cardinal) (struct _quantizer_ * quantizer);
00050 
00051   } it_quantizer_t;
00052 
00053 #define IT_QUANTIZER(q) IT_CAST(it_quantizer_t, q)
00054 
00055   static inline it_instanciate (it_quantizer_t) {
00056     it_construct (it_object_t);
00057     it_set_magic (it_this, it_quantizer_t);
00058     return (it_this);
00059   }
00060 #define it_quantizer_quantize(it_this, v) __it_quantizer_quantize(IT_QUANTIZER(it_this), v)
00061   static inline ivec __it_quantizer_quantize (it_quantizer_t * it_this, vec v) {
00062     return (it_this->quantize (it_this, v));
00063   }
00064 
00065 #define it_quantizer_dequantize(it_this, i) __it_quantizer_dequantize(IT_QUANTIZER(it_this), i)
00066   static inline vec __it_quantizer_dequantize (it_quantizer_t * it_this,
00067                  ivec i) {
00068     return (it_this->dequantize (it_this, i));
00069   }
00070 
00071 #define it_quantizer_get_cardinal(it_this) __it_quantizer_get_cardinal(IT_QUANTIZER(it_this))
00072   static inline unsigned int __it_quantizer_get_cardinal (it_quantizer_t *
00073                 it_this) {
00074     return (it_this->get_cardinal (it_this));
00075   }
00076 
00077 /* Scalar quantizer */
00078   typedef struct _scalar_quantizer_ {
00079     it_extends (it_quantizer_t);
00080 
00081     /* overload the virtual destructor */
00082     void (*it_overloaded (destructor)) (it_object_t * it_this);
00083 
00084     /* set a new codebook for the scalar quantizer */
00085     void (*set_codebook) (struct _scalar_quantizer_ * quantizer,
00086         vec codebook, int first);
00087 
00088     /* return the quantizer codebook from index start to index end */
00089 
00090 
00091        
00092        vec (*get_codebook_range) (struct _scalar_quantizer_ * quantizer,
00093           int start, int end);
00094 
00095     /* get/set/clear the quantizer index range (inclusive) */
00096     void (*get_index_range) (struct _scalar_quantizer_ * quantizer,
00097            int *_imin, int *_imax);
00098     void (*set_index_range) (struct _scalar_quantizer_ * quantizer,
00099            int _imin, int _imax);
00100 
00101     /* quantize a scalar */
00102     int  (*scalar_quantize) (struct _scalar_quantizer_ * quantizer, double v);
00103 
00104     /* dequantize an index */
00105     double (*scalar_dequantize) (struct _scalar_quantizer_ * quantizer,
00106          int i);
00107 
00108     /* quantizer codebook */
00109     vec  codebook;
00110 
00111     /* valid index range */
00112     int  imin;
00113     int  imax;
00114     int  first;
00115 
00116   } it_scalar_quantizer_t;
00117 
00118 #define IT_SCALAR_QUANTIZER(q) IT_CAST(it_scalar_quantizer_t, q)
00119 
00120   it_instanciate (it_scalar_quantizer_t);
00121 
00122 /* create a new quantizer from a codebook and the index corresponding to the first value in the codebook */
00123   static inline it_scalar_quantizer_t
00124     * it_scalar_quantizer_new_start_index (vec codebook, int first) {
00125     return (it_new_va (it_scalar_quantizer_t) (it_va, codebook, first));
00126   }
00127 
00128 #define it_scalar_quantizer_new(codebook) it_scalar_quantizer_new_start_index(codebook, 0)
00129 
00130 /* set a new codebook for the scalar quantizer */
00131 #define it_scalar_quantizer_set_codebook(it_this, codebook, first) \
00132           __it_scalar_quantizer_set_codebook(IT_SCALAR_QUANTIZER(it_this), codebook, first)
00133   static inline void
00134    
00135     
00136     
00137     
00138     __it_scalar_quantizer_set_codebook (it_scalar_quantizer_t * it_this,
00139           vec codebook, int first) {
00140     it_this->set_codebook (it_this, codebook, first);
00141   }
00142 
00143 /* get the codebook of the quantizer from index 'start' to index 'end' */
00144 #define it_scalar_quantizer_get_codebook_range(it_this, start, end) \
00145           __it_scalar_quantizer_get_codebook_range(IT_SCALAR_QUANTIZER(it_this), start, end)
00146   static inline vec
00147     __it_scalar_quantizer_get_codebook_range (it_scalar_quantizer_t *
00148                 it_this, int start, int end) {
00149     return (it_this->get_codebook_range (it_this, start, end));
00150   }
00151 
00152 #define it_scalar_quantizer_get_codebook(it_this) \
00153           it_scalar_quantizer_get_codebook_range(it_this, INT_MIN, INT_MAX)
00154 
00155 #define it_scalar_quantizer_get_index_range(it_this, imin, imax) \
00156           __it_scalar_quantizer_get_index_range(IT_SCALAR_QUANTIZER(it_this), imin, imax)
00157   static inline void
00158 
00159 
00160 
00161 
00162    
00163     
00164     
00165     
00166     __it_scalar_quantizer_get_index_range (it_scalar_quantizer_t * it_this,
00167              int *imin, int *imax) {
00168     it_this->get_index_range (it_this, imin, imax);
00169   }
00170 
00171 #define it_scalar_quantizer_set_index_range(it_this, imin, imax) \
00172           __it_scalar_quantizer_set_index_range(IT_SCALAR_QUANTIZER(it_this), imin, imax)
00173   static inline void
00174 
00175 
00176 
00177 
00178    
00179     
00180     
00181     
00182     __it_scalar_quantizer_set_index_range (it_scalar_quantizer_t * it_this,
00183              int imin, int imax) {
00184     it_this->set_index_range (it_this, imin, imax);
00185   }
00186 
00187 #define it_scalar_quantizer_clear_index_range(it_this) \
00188           it_scalar_quantizer_set_index_range(it_this, INT_MIN, INT_MAX)
00189 
00190 #define it_scalar_quantizer_scalar_quantize(it_this, v) \
00191           __it_scalar_quantizer_scalar_quantize(IT_SCALAR_QUANTIZER(it_this), v)
00192   static inline int
00193 
00194 
00195 
00196 
00197    
00198     
00199     
00200     
00201     __it_scalar_quantizer_scalar_quantize (it_scalar_quantizer_t * it_this,
00202              double v) {
00203     return (it_this->scalar_quantize (it_this, v));
00204   }
00205 
00206 #define it_scalar_quantizer_scalar_dequantize(it_this, i) \
00207           __it_scalar_quantizer_scalar_dequantize(IT_SCALAR_QUANTIZER(it_this), i)
00208   static inline double
00209 
00210 
00211 
00212 
00213    
00214     
00215     
00216     
00217     __it_scalar_quantizer_scalar_dequantize (it_scalar_quantizer_t * it_this,
00218                int i) {
00219     return (it_this->scalar_dequantize (it_this, i));
00220   }
00221 
00222 /* Uniform scalar quantizer */
00223   typedef struct _uniform_quantizer_ {
00224     it_extends (it_scalar_quantizer_t);
00225 
00226     /* quantizer step size */
00227     double step;
00228 
00229     /* quantizer center */
00230     double center;
00231 
00232     /* range */
00233     double min;
00234     double max;
00235 
00236     /* dead zone scale factor */
00237     double factor;
00238 
00239     /* dead zone step size (=factor*step) */
00240     double deadzone;
00241 
00242   } it_uniform_quantizer_t;
00243 
00244   it_instanciate (it_uniform_quantizer_t);
00245 
00246 #define IT_UNIFORM_QUANTIZER(q) IT_CAST(it_uniform_quantizer_t, q)
00247 
00248 /* constructor from center and step size */
00249   static inline it_uniform_quantizer_t
00250     * it_uniform_quantizer_new_from_center (double center, double step,
00251               double factor) {
00252     return (it_new_va (it_uniform_quantizer_t)
00253       (it_va, center, step, factor));
00254   }
00255 
00256 /* constructor from number of codewords and range */
00257   static inline it_uniform_quantizer_t
00258     * it_uniform_quantizer_new_from_range (int n, double min, double max) {
00259     double center;
00260     double step;
00261     it_uniform_quantizer_t *quantizer;
00262 
00263     step = (max - min) / n;
00264     center = min + step / 2;
00265     quantizer = it_uniform_quantizer_new_from_center (center, step, 1.0);
00266     it_scalar_quantizer_set_index_range (IT_SCALAR_QUANTIZER (quantizer),
00267            0, n - 1);
00268 
00269     return (quantizer);
00270   }
00271 
00272 /* get the step size of the quantizer */
00273 #define it_uniform_quantizer_get_step(q) (IT_UNIFORM_QUANTIZER(q)->step)
00274 
00275 /* get the center of the quantizer */
00276 #define it_uniform_quantizer_get_center(q) (IT_UNIFORM_QUANTIZER(q)->center)
00277 
00278 /* get the dead zone step factor */
00279 #define it_uniform_quantizer_get_deadzone_factor(q) (IT_UNIFORM_QUANTIZER(q)->factor)
00280 
00281 /* get the dead zone step */
00282 #define it_uniform_quantizer_get_deadzone_step(q)   (IT_UNIFORM_QUANTIZER(q)->deadzone)
00283 
00284 /* TCQ class */
00285   typedef struct _trellis_coded_quantizer_ {
00286     it_extends (it_quantizer_t);
00287 
00288     /* convolutional code used for set partitioning */
00289     it_convolutional_code_t *code;
00290 
00291     /* scalar quantizers for each coset */
00292     it_scalar_quantizer_t **coset_quantizers;
00293 
00294     /* overload the virtual destructor */
00295     void (*it_overloaded (destructor)) (it_object_t * it_this);
00296 
00297   } it_trellis_coded_quantizer_t;
00298 
00299   it_instanciate (it_trellis_coded_quantizer_t);
00300 
00301 #define IT_TRELLIS_CODED_QUANTIZER(q) IT_CAST(it_trellis_coded_quantizer_t, q)
00302 
00303 /* Initialize a TCQ from a quantizer by partitioning it */
00304 #define it_trellis_coded_quantizer_new_partition(code, quantizer) \
00305           __it_trellis_coded_quantizer_new_partition(IT_CONVOLUTIONAL_CODE(code), IT_SCALAR_QUANTIZER(quantizer))
00306   static inline it_trellis_coded_quantizer_t
00307     * __it_trellis_coded_quantizer_new_partition (it_convolutional_code_t *
00308               code,
00309               it_scalar_quantizer_t *
00310               quantizer) {
00311     return (it_new_va (it_trellis_coded_quantizer_t)
00312       (it_va, code, quantizer));
00313   }
00314 
00315 /* Matrix quantization: each line is quantized independently */
00316 #define it_quantize_mat(q, m) __it_quantize_mat(IT_QUANTIZER(q), m)
00317   imat __it_quantize_mat (it_quantizer_t * q, mat m);
00318 #define it_dequantize_mat(q, m) __it_dequantize_mat(IT_QUANTIZER(q), m)
00319   mat  __it_dequantize_mat (it_quantizer_t * q, imat m);
00320 
00321 /* shortnames for some functions */
00322 #define it_quantize(q, v) it_scalar_quantizer_scalar_quantize(q, v)
00323 #define it_dequantize(q, i) it_scalar_quantizer_scalar_dequantize(q, i)
00324 #define it_quantize_vec(q, v) it_quantizer_quantize(q, v)
00325 #define it_dequantize_vec(q, v) it_quantizer_dequantize(q, v)
00326 
00327 #define it_quantizer_set_codebook(q, codebook, start) \
00328           it_scalar_quantizer_set_codebook(q, codebook, start)
00329 #define it_quantizer_get_codebook_range(q, start, end) \
00330           it_scalar_quantizer_get_codebook_range(q, start, end)
00331 #define it_quantizer_get_codebook(q) \
00332           it_scalar_quantizer_get_codebook(q)
00333 #define it_quantizer_get_index_range(q, imin, imax) \
00334           it_scalar_quantizer_get_index_range(q, imin, imax)
00335 #define it_quantizer_set_index_range(q, imin, imax) \
00336           it_scalar_quantizer_set_index_range(q, imin, imax)
00337 #define it_quantizer_clear_index_range(q) \
00338           it_scalar_quantizer_clear_index_range(q)
00339 #define it_quantizer_scalar_quantize(q, v) \
00340           it_scalar_quantizer_scalar_quantize(q, v)
00341 #define it_quantizer_scalar_dequantize(q, i) \
00342           it_scalar_quantizer_scalar_dequantize(q, i)
00343 #define it_quantizer_get_step(q) it_uniform_quantizer_get_step(q)
00344 #define it_quantizer_get_center(q) it_uniform_quantizer_get_center(q)
00345 #define it_quantizer_get_deadzone_factor(q) \
00346           it_uniform_quantizer_get_deadzone_factor(q)
00347 #define it_quantizer_get_deadzone_step(q) \
00348           it_uniform_quantizer_get_deadzone_step(q)
00349 
00350 /* helper functions (to be moved to quantizer_func.h */
00351 
00352 /* generate the codebook for the Lloyd-Max quantizer on N levels  */
00353 /* This is the optimal codebook for a stationnary i.i.d. source.  */
00354 /* [a,b] is the interval where to expect the pdf to be non-zero   */
00355 /* a good guess is [ mean - std_dev, mean + std_dev ].            */
00356 /* Note that returned centroids may lie outside this interval     */
00357 /* The algorithm stops when the relative difference in distortion */
00358 /* is smaller than IT_EPSILON.                                    */
00359 
00360 vec  lloyd_max (it_function_t function, it_args_t args,
00361     double a, double b, int N);
00362 
00363 /* @} */
00364 
00365 
00366 #endif
include/it/quantizer.h
