Computer graphics processing and selective visual display system – Display driving control circuitry – Physically integral with display elements
Reexamination Certificate
2000-02-16
2001-04-03
Chauhan, Ulka J. (Department: 2671)
Computer graphics processing and selective visual display system
Display driving control circuitry
Physically integral with display elements
C345S205000, C382S166000, C382S232000
Reexamination Certificate
active
06211864
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to an image processing system and method for image data compression. In particular, the invention relates to an image processing system with improved utilization of available memory for storing compressed images.
BACKGROUND OF THE INVENTION
Image compression techniques reduce the memory required for storage of large or complex images, permitting storage of images in devices with limited memory. For example, image compression techniques used in digital copiers and scanners assist in storage of complex images for subsequent printing. Similarly, image compression benefits communication links where bandwidth limitations would otherwise render transmission of image data impractical. Image compression also offers substantial benefits for archiving large image libraries.
JPEG (Joint Photographic Experts Group) is a standardized image compression technique that can be used with either full-color or gray-scale images. This technique performs a Discrete Cosine Transform (DCT) on each block of pixels in an image. The result of the DCT for each block of pixels is an array of frequency components. Low frequency components correspond to slowly varying intensities between neighboring pixels. High frequency components represent rapidly varying intensities across small clusters of pixels. Information represented by the higher frequency components is reduced by quantization, i.e., the restriction of actual values to a limited set of values. The compressed image size is related to the quantization level specified by the user. The frequency components are encoded in order from the lowest frequency to the highest. If there are no frequency components beyond a specific frequency, then no further data from that block is encoded. Instead, an end of block symbol is emitted to indicate to a decoder that the block is complete.
Application of the above technique to blocks of pixels having high spatial frequencies may result in data represented by more bits than can be stored in a memory device or transmitted over a communication link in a limited time. One technique used to overcome this problem is to count the total number of bits used to represent the block of pixels and compare the total with a maximum allowable value. If the total exceeds the maximum value, the highest non-zero frequency component is decreased in absolute value and the total number of bits is recalculated and compared with the maximum. This process is repeated until the total number of bits is no greater than the maximum value. Generally, human perception of images is more affected by amplitude changes in the lower frequency components than higher frequency components, therefore this technique typically has negligible impact on perceived image quality. However, an image stored under the JPEG standard and subsequently recalled is reduced in quality from the original image. Multiple applications of JPEG compression on an image can result in a significant reduction in the image quality. It is therefore desirable to store as many of the higher frequency components as possible in the available memory.
One known storage technique for JPEG compressed images, described in U.S. Pat. No. 5,321,522, provides fixed memory allocation for each block of pixels. Therefore, a block of pixels that has no high frequency components may not require all the bits available in a block of memory. As a result, there can be “gaps” in memory. Subsequent processing, however, may include blocks of pixels with high frequency information that exceeds the available memory allocated to individual blocks, thereby requiring the loss of some information.
SUMMARY OF THE INVENTION
A method for optimizing the storage of compressed images has been developed which is useful for a wide variety of applications, including but not limited to, storage of digital images in limited memory devices.
The method requires the image to be compressed be divided into a series of smaller images or pixel blocks. The values corresponding to the pixel blocks are then processed, one block at a time, by a processor module. Processing can include performing a transform function on each pixel block. The transform function can be one that generates frequency space coefficients representative of the pixel block data (e.g., a discrete cosine transform (DCT)). Processing can include further operations such as ordering the frequency space coefficients, recalling quantization values from memory and creating quantized frequency space coefficients by dividing the frequency space coefficients by the corresponding quantization values. Additional processing can be used to create a data packet for each quantized frequency space coefficient and to encode each data packet (i.e., a symbol or sequence of bits).
A cumulative memory allocation, which defines the current allowable memory, is determined each time a new pixel block is processed. The cumulative memory allocation can be based on the number of pixel blocks currently processed and an average memory allocation for each pixel block. The processor module generates a series of data packets for each processed pixel block. The bits contained in each data packet are counted and the result is added to the number of bits previously stored in memory to yield a current memory total. The current memory total is compared to the cumulative memory allocation to determine whether the current data packet should be written to memory. If the current memory total does not exceed the cumulative memory allocation, the current data packet is written to memory. If the current memory total exceeds the cumulative memory allocation, no further data packets for the present pixel block are written to memory and processing begins on the next pixel block.
This method avoids the “memory gaps” that can result from existing methods, such as described in U.S. Pat. No. 5,321,522, which provide a fixed memory allocation for each block of pixels. The present invention is more flexible in its allocation of memory. If earlier processed blocks do not fill the average memory available for each block, later processed blocks containing more information can take advantage of the excess memory for the earlier blocks. In effect, each block of pixel data is packed into memory serially rather than being restricted to a block of memory, thereby permitting more information to be stored for a given image. This method can be implemented as the data packets are generated, thereby avoiding the need to later process each data block.
The invention also features an apparatus for optimally compressing a digital image into a memory module. The apparatus includes a processor module to process pixel blocks and generate data packets. The processor can perform various functions, including transforms (e.g., a DCT), on each pixel block. Processor output can include spatial frequency coefficients for each pixel block which can be quantized and formatted into data packets. The apparatus includes a counter which receives the processor output, determines the number of bits in each data packet and adds the result to generate a current memory total. A comparator compares the current memory total to a reference signal representative of the cumulative memory allocation. The cumulative memory allocation, for example, can be based upon the number of pixel blocks processed for the image and an average memory allocation per pixel block. An output device, such as a buffer, temporarily stores the data packet generated by the processor. The comparator output enables the output device to write the data packet to memory when the current memory total does not exceed the cumulative memory allocation.
REFERENCES:
patent: 5253078 (1993-10-01), Balkanski et al.
patent: 5530478 (1996-06-01), Sasaki et al.
patent: 5585931 (1996-12-01), Juri et al.
patent: 5699457 (1997-12-01), Adar et al.
patent: 5761345 (1998-06-01), Saito et al.
patent: 5818529 (1998-10-01), Asamura et al.
Chauhan Ulka J.
Oak Technology, Inc.
LandOfFree
Method and apparatus for optimizing storage of compressed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for optimizing storage of compressed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing storage of compressed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2495444