============================================================================== 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 ". 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. ==============================================================================