Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
1998-04-10
2002-04-09
Boudreau, Leo (Department: 2721)
Image analysis
Image compression or coding
Including details of decompression
C382S248000, C382S234000, C358S438000
Reexamination Certificate
active
06370273
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital image data decompression, and more particularly to a method and system for tiled digital image data decompression.
BACKGROUND OF THE INVENTION
Digital image data normally requires large amounts of memory. Compression of image data attempts to reduce the amount of memory needed when storing and transferring image data. In compressing image data, typically images are broken up into blocks of image data. A standard for image data compression, JPEG (Joint Photographic Expert Group), produces variable length bitstreams from blocks of image data. Normally, JPEG compression operates on 8×8 or 16×16 blocks of pixel image data, scanned along the rows of an image. Some systems utilize tile-based data by breaking an image into large tiles which are then broken down into blocks for compression.
FIG. 1
a
illustrates an image
10
broken up into four rows of six tiles
12
. By way of example, each tile comprises 64×64 blocks, or 4×4 macroblocks of 16×16 blocks.
JPEG compressed tiled image data is typically decoded one tile at a time. Normal JPEG decompression is only interruptible after the completion of a well-defined unit of incoming compressed data and never halted in the middle of a bitstream. Thus, implementation is required to halt on boundaries defined by the incoming bitstream. In many imaging systems, entire rows of data are utilized, thus requiring decompression of multiple tiles. Usually, buffering of a band of data occurs, where the number of lines in the band equals the number of lines in a tile. However, each row in the band is usually processed only once, so that the extra buffering required to store all the lines of the tile at once is quite inefficient, since the extra buffering is only required to reorganize the incoming data.
FIG. 1
b
illustrates such extra buffering. A compressed stream of data
14
having variable length data segments and known tile boundaries is decompressed through a decoder
16
and stored in a band buffer
18
, the band buffer having a number of lines equal to the number of lines in a tile, e.g., 64. Each entire tile is decompressed and stored in the band buffer
14
before a next tile is decompressed through decoder
16
, band buffer
18
illustrating the storage of three tile's worth of data with three more tiles needing to be decoded before an entire row of data of image
10
is complete. However, usually the number of the lines in a tile necessary to produce an output of an entire row of the image
10
is smaller than the total number of lines in a tile, e.g., 16 lines. Thus, extra memory is used and wasted on storing the lines beyond the needed number of lines.
One method used to reduce the storage requirement for tiled image data decompression is to insert markers during compression. The markers, which are allowed but not required in the JPEG standard, identify chosen tile boundaries in the compressed data stream. For example,
FIG. 1
c
illustrates a compressed stream of data
20
having markers
22
positioned within the stream
20
during compression. Using these markers, a decoder
24
scans the incoming data stream to identify the edge of each tile and only decompresses a first segment in each tile as designated by the markers
22
. The memory requirements, i.e., the number of lines for band buffer
26
, are thereby reduced by only decompressing the first segment in each tile across a row, e.g. a first set of sixteen lines, rather than an entire tile, e.g., 64 lines, to determine the data for a row in the image. Unfortunately, the use of markers is limiting and problematic, since the JPEG standard does not require that markers be placed in the compressed data stream, nor does it require that such markers be placed on the edges of tiles. Thus, such decompression techniques are inapplicable with systems that do not utilize such markers and create more complicated image processing.
Accordingly, what is needed is a system and method for decompressing tiled image data that requires minimal memory and has broader application than the use of externally imposed markers in compressed data streams. The present invention addresses such a need.
SUMMARY OF THE INVENTION
The present invention provides method and system aspects for reducing memory storage requirements during decompression of tiled image data. Included in a method aspect, and system for achieving same, are identification of a number of tiles in each row of an image, and decompression of a bitstream of compressed image data from the number of tiles in parallel to fill a band buffer with a minimum number of lines needed for processing a scan line of the image.
With the present invention, any tile-based compressed stream of data is capably decompressed without requiring adequate memory for concurrent storage of each entire tile's decompressed data. Rather, minimal memory is utilized since a minimum number of lines of decompressed data needed to output a scan line of an image are stored during decompression. Further, the present invention successfully achieves the reduction in memory requirements without requiring the placement and reliance on restart markers within a compressed bitstream. These and other advantages of the aspects of the present invention will be more fully understood in conjunction with the following detailed description and accompanying drawings.
REFERENCES:
patent: 5477264 (1995-12-01), Sarbadhikari et al.
patent: 5568139 (1996-10-01), Yoon
patent: 5596423 (1997-01-01), Pritchard
patent: 5633678 (1997-05-01), Parulski et al.
patent: 5699460 (1997-12-01), Kopet et al.
patent: 5717197 (1998-02-01), Petrie
patent: 5717394 (1998-02-01), Schwartz et al.
patent: 5764801 (1998-06-01), Munemasa et al.
patent: 5872965 (1999-02-01), Petrick
patent: 5940585 (1999-08-01), Vondran, Jr. et al.
patent: 5995727 (1999-11-01), Wise et al.
Boudreau Leo
Flashpoint Technology, Inc.
Sawyer Law Group LLP
Sherali Ishrat
LandOfFree
Method and system for tiled image data decompression 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 system for tiled image data decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for tiled image data decompression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925782