Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2003-03-13
2004-10-12
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S243000
Reexamination Certificate
active
06804404
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the coding of shape information, a process carried out in the coding and decoding of still and moving pictures.
When still or moving pictures are coded and decoded, a coding or decoding operation must sometimes be restricted to the picture elements in an irregular area. This occurs when hierarchical coding methods such as wavelet methods are employed. It then becomes necessary to furnish information specifying the shape of the area. The shape information can be represented in the form of a bi-level image, which must also be coded and decoded.
When a picture is coded hierarchically, it is convenient to code the accompanying shape information hierarchically as well. A known way to do this is to generate a series of bi-level images of decreasing resolution, and code the difference between each successive pair of images in the series by, for example, an entropy coding technique.
Typically, each bi-level image in the series has half the vertical and horizontal resolution of the preceding image. Thus each picture element or pixel in one image in the series derives from four pixels in the preceding image. In
FIG. 1
, for example, pixel A is derived from higher-resolution pixels a, b, c, d by a majority-decision rule. In some conventional coders, to improve the quality of the reduced image, the set of higher-resolution pixels is expanded to include more than four pixels.
A problem when shape information is coded in this way is that the wavelet transform and other hierarchical coding methods employ a decimating type of subsampling to reduce image resolution. To reduce the resolution by half, for example, they discard every second pixel in the horizontal and vertical directions. This subsampling method differs from the majority-decision methods employed in conventional hierarchical methods of coding shape information, leading to inconsistencies between the shape information and picture information. In wavelet coding, the result may be that the wavelet transform is applied to the wrong pixels, leading to image defects when the coded picture is decoded.
A further problem is that in the decoding process, each pixel can be decoded only with reference to pixels that have already been decoded. In conventional coding and decoding methods, the reference pixels are therefore disposed on only two sides of the pixel being coded or decoded. Use of this type of reference-pixel context does not lead to compression ratios as high as could be achieved if a more complete context were available. Some coders attempt to improve the context by increasing the number of reference pixels, but the resulting increase in the number of context states can actually lower the coding compression ratio.
SUMMARY OF THE INVENTION
It is accordingly an object of the present invention to obtain hierarchically coded and decoded shape information that is consistent with hierarchically coded and decoded picture information.
Another object of the invention is to improve the compression ratio of coded shape information.
The invented shape information coder has resolution converting means that processes input shape information by dividing the pixels in the shape information into mutually exclusive subsets, each subset representing a different subsampling of the input shape information and having a lower resolution than the input shape information. The subsets of pixels are stored in a memory means.
A context generating means selects reference pixels from the memory means and generates context information. Preferably, the context information generated for a pixel in one of the subsets is obtained from reference pixels selected from at least two of the subsets, including reference pixels disposed on all sides of the pixel. The context information may be simplified by assigning different combinations of reference-pixel values to the same context-information value. A coding means codes the subsets of pixels according to the context information.
The memory means may include a separate memory for each subset of pixels. The coding means and context generating means may include a separate coder for each memory, and a separate context generator for each coder, so that different subsets can be coded concurrently.
A hierarchical shape information coder according to the invention comprises a plurality of cascaded stages, each separately structured as described above. As input shape information, each stage (except the first) receives one of the subsets of pixels generated in the preceding stage. Context information may be supplied from each stage to the preceding stage, so that the subset of pixels received from the preceding stage does not have to be stored in the preceding stage.
The invention also provides a shape information decoder and a hierarchical shape information decoder analogous to the above shape information coder and hierarchical shape information coder, using similar context generating means.
The context generating means may comprise a reference pixel generator, a reference pixel position and context simplification memory, and a context converter.
REFERENCES:
patent: 4430670 (1984-02-01), Netravali
patent: 5598214 (1997-01-01), Kondo et al.
patent: 5808683 (1998-09-01), Tong et al.
patent: 5883978 (1999-03-01), Ono
patent: 5973745 (1999-10-01), Kondo
patent: 6014463 (2000-01-01), Hirabayashi
patent: 2610169 (1997-02-01), None
U.S. patent application Ser. No. 09/112,199, filed Jul. 9, 1998, Zhixiong Wu, “Method and Apparatus for Image Encoding.”
Johnson Timothy M.
Oki Electric Industry Co. Ltd.
Sartori Michael A.
Swindell W. Russell
Venable LLP
LandOfFree
Shape information coder and decoder dividing shape... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shape information coder and decoder dividing shape..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shape information coder and decoder dividing shape... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318914