|
In designing digital cameras and other consumer devices incorporating camera functionality, with ever improving performance, memory and power often prove to be the major constraints. Consumers expect instantaneous display of captured images, creating further demand on performance. The capture, storage and transfer of still images is central to digital camera functionality. Improving the efficiency of these processes can help the embedded industry to increase battery life, consume less storage and transfer data at faster rates. One approach to solving these problems is to optimize the algorithms for data compression and decoding. In this article we'll look at algorithm-level optimization techniques that can be used at various stages in decoding still images.
Some of the algorithms very commonly used for encoding and decoding still images are: JPEG (Joint Picture Experts Group), GIF (Graphics Interchange Format) and BMP (Bit Map). Bit Mapped (BMP) images are used for high quality resolution, but they require more memory, JPEG images are used in most of the low resolution digital camera and mobile phones due to constraints in the storage size.
Algorithms like JPEG and GIF contain compressed data and so consume less memory with higher bit-rates. But JPEG images loose information. The diagram below describes the overall flow used for decoding compressed data algorithms.
View full size
Figure 1: Decoding Block Diagram
Still images contain headers that are partitioned by markers that convey information for the Quantization table, the Huffman table, start of scan and other image related information. Before the compressed data can be read, the image header must be extracted. Still images are entropy encoded to remove the redundant data. Entropy decoding on the compressed data is done with the help of the Huffman table. Run length decoding is also done to get quantized data. The extracted quantization table from the image header is used to perform de-quantization of an 8x8 data block of MCU (Minimum Coded Unit).
The de-quantized block of data is then fed to an inverse transform module to convert the frequency domain data into time domain data followed by Inverse Transform Interleaving and Color Conversion. Color conversion uses standard pixel data formats such as 4:4:4, 4:2:2, 4:1:1, 4:2:0. Interleaving is done block by block on the MCUs. After the data format conversion, the YCbCr is converted into a RGB format. Once the raw RGB data of the image block is available, this block is sent for display.
Optimizations at Huffman decoding stage
Three techniques are used for Huffman decoding namely Binary Tree Search method, Look-up Table method and N-level Look-up table method.
In the binary tree search method, a bit at a time is extracted from the input data stream. This bit is then compared with the Huffman symbols generated from the Huffman table. If the bits do not match, then the next bit is extracted. The symbol formed by two bits is then compared with the Huffman symbols. If these symbols match, the Huffman code corresponding to the symbols is considered valid data.
In the look up table method, the tables extracted from the image header are converted into look up tables containing Huffman symbols and Huffman code lengths. Depending on the maximum Huffman code length, bits are extracted from the bit stream. Huffman symbols are decoded with one search as the extracted bits from the bit-stream correspond to respective addresses to the symbol in the table.
The N-level lookup table is an extension of the Look-Up Table method. Based on the requirements of the Huffman symbol search, Huffman codes can be split into N Level of Look-Up Tables. Tables used for this technique contain symbol entries and the next table index with its corresponding Huffman code lengths. It also contains number of bits required for next level look-up
The table below explains the MIPS/memory trade off for different methods of Huffman decoding.
View full size
Table 1: MIPS – Memory tradeoffs
Based on the type of image, engineers are able to predict that the Huffman code length for any symbol will not exceed some particular limit. In this scenario, memory consumption can be reduced through a combination of Look up Table and the Binary tree search method. For example, if we know that the Huffman code length is seldom going beyond 10-bits for 16-bit maximum Huffman table then both the look up table and binary search tree method can be used, and a look up table of 2 10 values is calculated.
As compared to Lookup table method using the method that employs both look-up and binary methods, further increase MIPS slightly for images having Huffman code higher than 10 bits but helps in reducing the memory size by 216 – 2 10 = 63K for the Huffman table.
Next: Dropping 8x8, 4x4 pixels for smaller displays
|
