==============================================================================
Q C C P A C K
Version 0.63, 04-jul-2021
Copyright (C) 1997-2021 James E. Fowler
------------------------------------------------------------------------------
*** Warning: this is pre-release code ***
*** There are probably bugs ***
------------------------------------------------------------------------------
==============================================================================
Contents:
- Overview
- Availability
- Changes
- Installation
- General Installation Notes
- General Installation Steps
- Platform-Specific Installation Instructions
- Notes on Use
- Platform-Specific Notes
- Example Usage
- Contact
- Acknowledgments
- Copyright and License Information
==============================================================================
OVERVIEW:
QccPack provides an open-source collection of library routines and
utility programs for quantization, compression, and coding of data. QccPack
has been written to provide very flexible and general implementations of
procedures commonly used in coding and compression applications.
The essential component of the QccPack collection is a library (a static
library, libQccPack.a, and, if supported on your system, a dynamic library,
libQccPack.so) of procedures implementing a large variety of compression
and coding algorithms. Application programs may make use of the QccPack
library routines by linking the application against the library during
compilation. Each library function is very general in its implementation
so to be useful in a large variety of applications.
Additionally, much of the functionality of the library routines has been
provided in the form of stand-alone executable programs. Probably the prime
importance these utility programs is that they provide examples of how to
interface with many of the QccPack library routines. The utility programs
could also be called from scripts to simulate the operation of complex
coding and compression systems before implementing all the system
functionality into one stand-alone program.
Now some caveats. The QccPack code is currently in BETA-release development
stage. That is to say, much desired functionality is still left to be
implemented, and documentation is spotty. Currently, all utility programs
are documented with man pages; however, only some of the library routines are
documented. A good starting point for examining the documentation that is
available would be to type "man QccPack" after QccPack is installed.
Documentation is also available in HTML form.
QccPack is intended for use in the development of prototypes of coding
and compression systems, and in academic research. Its main reason for
existence is to obviate the incessant re-implementation of common algorithms
for the sake of application-specific details. For example, we don't want
to re-implement arithmetic coding every time we change the symbol-alphabet
size or the number of contexts in the arithmetic-coder adaptive model. By
using QccPack, we use the same implementation of arithmetic coding regardless
of our application. The drawback of this library-based approach to
development is the fact that the generality required of the library routines
leads to a frequent use of dynamic memory allocation which, in turn, implies
that the routines execute slower than would a similar implementation that
hard-coded application-specific details. For this reason, QccPack is
intended for prototyping and proof-of-concept needs rather than for direct
use in applications requiring high-speed operation.
Currently, QccPack consists of over 55,000 lines of C code implementing over
500 library routines and over 50 stand-alone utility programs. The major
functionalities currently implemented include:
o Entropy coding
- Arithmetic coding including multiple-context adaptive and
nonadaptive models
- Huffman coding
- Golomb and adaptive Golomb coding
o Scalar Quantization (SQ)
- Uniform SQ
- Dead-zone SQ
- u-law and A-law SQ
- Lloyd algorithm for optimal SQ design
o Vector quantization (VQ)
- Generalized Lloyd algorithm (GLA) for VQ-codebook design
- Full-search VQ encoding and decoding
- Entropy-constrained-VQ (ECVQ) training, encoding, and decoding
- Multistage VQ (MSVQ) (also called residual VQ (RVQ)) training,
encoding, and decoding
o Adaptive vector quantization (AVQ)
- The generalized-threshold-replenishment (GTR) algorithm
- The Paul algorithm
- Gersho-Yano algorithm
- Coding of side information
o Wavelet transforms, wavelet-based subband coding
- Discrete wavelet transform (DWT) using first-generation filter banks
and popular orthonormal and biorthogonal wavelets
- Lifting implementations of DWT for popular wavelets
- Two-dimensional DWT in the form of dyadic subband pyramids
- Three-dimensional DWT in the form of dyadic subband pyramids as well
as a packet transform
- Shape-adaptive DWT (SA-DWT) for 1D and 2D signals
- Redundant DWT (RDWT), aka, the algorithme a trous
- The SR algorithm for wavelet-based image coding
- The SFQ algorithm for wavelet-based image coding
- The WDR algorithm for wavelet-based image coding
- The 3D-WDR algorithm for wavelet-based image-cube coding
- The tarp-filter algorithm for wavelet-based image coding
- The 3D-tarp algorithm for wavelet-based image-cube coding
- The TCE algorithm for wavelet-based image coding
- The BISK algorithm for wavelet-based shape-adaptive image coding
- The 3D-BISK algorithm for wavelet-based image-cube coding
- The SPIHT algorithm for wavelet-based shape-adaptive image coding
- The 3D-SPIHT algorithm for wavelet-based image-cube coding
- The SPECK algorithm for wavelet-based shape-adaptive image coding
- The 3D-SPECK algorithm for wavelet-based image-cube coding
o Error-correcting codes
- Field arithmetic, including Gaussian-elimination matrix inversion
- Reed-Solomon encoding and decoding
- CRC codes
- Trellis codes
- Hard and soft Viterbi decoding
o Image processing
- Routines for reading and writing gray and color still images and
sequences of images (via PGM and PPM formats)
- Routines for reading and writing image-cube volumes
- Image and image-sequence deinterlacing
- Image differential-pulse-code modulation (DPCM)
- Color-space conversions: RGB, YUV, CIE XYZ, CIE UCS, CIE modified UCS
- Block-based DCT and inverse DCT
o Video coding
- The spatial-block algorithm for image-sequence coding
- The RDWT-block algorithm for image-sequence coding
- The RWMH algorithm for image-sequence coding
- Block-based motion estimation and motion compensation
- Motion estimation and motion compensation using regular triangle meshes
- Encoding and decoding of motion-vector fields
o General routines
- Vector math (up/down sampling, sorting, dot product,
addition/subtraction, etc.)
- Matrix math (addition/subtraction, vector-matrix multiplication, etc.)
- Linked lists and associated operations
- Entropy estimation (first and second order)
- General file input and output, including automatic detection and
reading/writing of gzip-compressed files
- Character bit-packing for binary bitstream input/output
- Memory-based fifo for binary bitstreams
- Conversion between various file formats used by library routines
- Error-message tracking, formatting, and output
- Automatic command-line parameter parsing
==============================================================================
AVAILABILITY:
For updated versions of QccPack, or optional modules for QccPack,
consult the QccPack website:
http://qccpack.sourceforge.net
==============================================================================
CHANGES:
The file RELEASE_NOTES gives an overview of the major changes incorporated
into the current version of QccPack. The file CHANGELOG gives a very
detailed picture of the evolution of the code.
==============================================================================
INSTALLATION:
* General Installation Notes:
The following gives the steps for the building and installation of
QccPack. It should be a relatively straightforward process to get
QccPack to compile on any UNIX system, and should be thoroughly
operational on such systems, although it has only really been
tested on Linux. QccPack is supported on Microsoft Windows, but
only through use of Cygwin, a free UNIX emulation environment
for Windows.
The general procedure for installation of QccPack is described below.
Platform-specific installation instructions follow. Windows users,
in particular, be sure to read the instructions concerning
installation of Cygwin.
Refer to documentation accompanying optional QccPack modules for
information on the installation of those modules.
* General Installation Steps:
1. Untar the QccPack distribution to a directory in which building
is to be performed. The directory /usr/local/src/QccPack is
suggested, but use whatever location you want.
2. Copy the file QccPack.config.xxxx to QccPack.config, where "xxxx"
is the operating system that you are using. For example, if using
Linux, type
cp QccPack.config.linux QccPack.config
If a QccPack.config.xxxx file is not provided for your operating
system, use the QccPack.config.linux file and pay close
attention to the various configuration options during the
configuration-editing process which is the next step.
3. Edit the file QccPack.config :
3.1 Set QCCPACK to be the absolute path of directory into which
the files were untarred; the default for this path is
/usr/local/src/QccPack
3.2 Change QCCPACK_INSTALL so that QCCPACK_INSTALL_LIB_PATH,
QCCPACK_INSTALL_INCLUDE_PATH, QCCPACK_INSTALL_BIN_PATH,
QCCPACK_INSTALL_MAN_PATH, and QCCPACK_INSTALL_DATA_PATH
point to the desired location of the final installation of the
libraries, header files, binaries, man pages, and data files,
respectively. These default to lib, include, bin, man
directories in /usr/local, and /usr/local/share/QccPack for
the data files, but change them if you like.
3.3 QccPack comes with HTML versions of its man pages. By default,
these will be installed in $(QCCPACK_INSTALL)/doc/QccPack.
If you do not want these pages installed, comment out
(with XCOMM's) the definition of HTMLMAN.
3.4 Define CC and CFLAGS as needed for your desired ANSI C compiler
and associated flags. The GNU compiler, gcc, is recommended.
3.5 If your system/compiler supports the creation of shared objects
(i.e. dynamic libraries), set SHARED_OBJ_FLAGS and LD
appropriately. Alternatively, you can define NO_DYNAMIC_LIB to
suppress the creation of the dynamic library and cause the
static linking of the utility executables.
3.6 Set the definitions of QCCCOMPRESS and QCCUNCOMPRESS
to point to where gzip and gunzip reside on your system
(absolute path). Optionally, these definitions can be changed to
use compress and uncompress, if so desired.
4. Type "imake".
5. Type "make Makefiles".
6. Type "make".
7. When you're happy that things compiled OK, type "make install" to
put the libraries, header files, binaries, and man pages into their
final installation locations.
8. A "make clean" will perform a complete uninstallation of QccPack:
the build directory tree will be cleaned of all executables and object
files, AND the libraries, header files, binaries, and man pages
will be removed from the final installation locations. You can then
remove the build tree with "rm -rf <dir>".
9. Type "man QccPack" or point your browser to
file:$(QCCPACK_INSTALL)/doc/QccPack.3.html to view the available
documentation.
* Platform-Specific Installation Instructions:
- Microsoft Windows (all flavors)
QccPack can be installed on Microsoft Windows by using Cygwin, a free
software package emulating the UNIX environment under the Windows
platform. Consequently, you have to install Cygwin before
installing QccPack. Below, you will find a brief set of
instructions addressing the installation of Cygwin for supporting
the installation of QccPack. For full details about the Cygwin
software and its installation, please visit the official Cygwin
website at http://www.cygwin.org.
Note: QccPack is supported on Windows only through use of Cygwin;
in particular, QccPack will *not* compile with Microsoft Visual C++.
1. Download and install Cygwin by first downloading and running
the Cygwin "setup" program. This program can be downloaded from:
http://cygwin.org/setup-x86.exe (32-bit installation)
or
http://cygwin.org/setup-x86_64.exe (64-bit installation)
You need to get Cygwin version 1.3.11-3 or later.
2. The Cygwin "setup" program has three options for installing
the Cygwin software packages:
o Install from Internet: download the packages from a
selected mirror site and then install the packages on computer
o Download from Internet: download the packages without installing
o Install from local directory: install the packages from a
specified local directory
Select one installation options as appropriate (most likely the
first option), then follow the instructions given by the
"setup" program to install the software to a location of your
choosing. For further installation details, please refer to:
http://cygwin.com/faq.html
3. Applications included in your Cygwin download depend on the
packages you choose during the installation. For the installation
of QccPack, you will need to get 'gcc', 'make', and 'imake'
in the 'Devel' category.
4. Now, follow the above general instructions for installing QccPack.
It is recommended that you build a static library; i.e., define
the NO_DYNAMIC_LIB variable.
The usage of the Cygwin environment is similar to any other
UNIX system; see the Cygwin user's guide for details:
http://cygwin.com/cygwin-ug-net.html
==============================================================================
NOTES ON USE:
* Platform-Specific Notes:
- Microsoft Windows (all flavors)
It appears that there is a bug in the Cygwin implementation
of pclose() which causes a variety of QccPack programs to
crash when writing to gziped output files. Unfortunately, the
only workaround we can come up with is to not use gzip-compressed
output files on Cygwin until the pclose() problem is fixed in
Cygwin. In particular, do not use gziped output files in the
example below "EXAMPLE USAGE".
==============================================================================
EXAMPLE USAGE:
Here is an example that trains a codebook on an image and then
codes the image. We demonstrate both vector quantization and
adaptive vector quantization (the GTR algorithm).
Note: all programs can read and write gzipped files.
The original image is a 512x512 grayscale PGM file which can be found
in $(QCCPACK_INSTALL_DATA_PATH)/Images.
Encoding:
Convert from PGM image-file format to DAT file (extracts 2x2 blocks from
image and rearranges components into 4D vectors):
imgtodat -ts 4 lenna.pgm.gz lenna.4D.dat.gz
Train 256-codeword codebook on DAT file with GLA algorithm:
gla -s 256 -t 0.01 lenna.4D.dat.gz lenna.4D256.cbk
Vector quantize DAT to produce channel of VQ indices:
vqencode lenna.4D.dat.gz lenna.4D256.cbk lenna.vq.4D256.chn
Entropy coding of VQ-index channel:
Calculate first-order entropy of VQ indices (as bits/pixel):
chnentropy -d 4 lenna.vq.4D256.chn
Arithmetic-code channel:
chnarithmeticencode -d 4 lenna.vq.4D256.chn lenna.vq.4D256.chn.ac
rm lenna.vq.4D256.chn
Decoding:
Decode arithmetic-coded channel:
chnarithmeticdecode lenna.vq.4D256.chn.ac lenna.vq.4D256.chn
Inverse VQ channel to produce quantized data:
vqdecode lenna.vq.4D256.chn lenna.4D256.cbk lenna.vq.4D256.dat.gz
Convert from DAT to PGM format (convert 4D vectors into image blocks
and assemble into image array):
dattoimg 512 512 lenna.vq.4D256.dat.gz lenna.vq.4D256.pgm
Calculate distortion between original and coded images:
imgdist lenna.pgm.gz lenna.vq.4D256.pgm
Adaptive VQ:
Create scalar quantizer to act as the codebook coder:
squniform lenna.255.sq
Encode with the GTR AVQ algorithm (lambda = 16, omega = 100):
gtrencode -l 16 -w 100 -ic lenna.4D256.cbk lenna.4D.dat.gz \
lenna.255.sq lenna.gtr.4D256.chn.gz lenna.gtr.4D256.sid.gz
GTR decoding:
gtrdecode -ic lenna.4D256.cbk lenna.gtr.4D256.chn.gz \
lenna.gtr.4D256.sid.gz lenna.255.sq lenna.gtr.4D256.dat.gz
Estimate rate:
avqrate lenna.255.sq lenna.gtr.4D256.chn.gz lenna.gtr.4D256.sid.gz
Convert from DAT to PGM format:
dattoimg 512 512 lenna.gtr.4D256.dat.gz lenna.gtr.4D256.pgm
Calculate distortion between original and coded images:
imgdist lenna.pgm.gz lenna.gtr.4D256.pgm
==============================================================================
CONTACT:
For all inquires, contact James E. Fowler:
http://www.ece.msstate.edu/~fowler
fowler@ece.mssate.edu
==============================================================================
ACKNOWLEDGMENTS:
A large portion of the QccPack library was written while James E. Fowler
held a postdoctoral position at Laboratoire I3S, Université de Nice-Sophia
Antipolis, Sophia Antipolis, France, and was based upon work supported by
the National Science Foundation under Grant No. INT-9600260. Subsequent
support was provided by the National Science Foundation under Grant
Nos. ACI-9982344 and CCR-0310864.
==============================================================================
COPYRIGHT AND LICENSE INFORMATION:
Copyright (C) 1997-2021 James E. Fowler
The programs and library herein are free software; you can redistribute
them and/or modify them under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
The library and all programs herein are distributed in the hope that
they will be useful, but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
the full text of the appropriate license for more details.
==============================================================================
Download Latest Version
QccPack-0.63-1.tar.gz (2.7 MB)
