Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1998-08-31
2003-02-25
Johns, Andrew W. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C370S389000
Reexamination Certificate
active
06526175
ABSTRACT:
The invention relates to a packet format in the field of digital multimedia communications. More particularly, the invention relates to a packet format for packetizing “significance-based” information to improve error resilience.
BACKGROUND OF THE DISCLOSURE
In the field of digital multimedia communications, data streams carrying video, audio, timing and control data are packaged into various “packets”. Generally, a packet is a group of binary digits that include data and control elements which are switched and transmitted as a composite whole. The data, control elements and other information are arranged in various specific formats.
Examples of such formats are disclosed in the ISO/IEC international Standards 11172 and 13818 (generally referred to as MPEG-1 and MPEG-2). In general, MPEG defines a packet as consisting of a header followed by a number of contiguous bytes (payload) from an “elementary data stream”. An elementary stream is simply a generic term for one of the coded video, coded audio or other coded bitstreams. More specifically, an MPEG-2 “transport stream” packet comprises a header, which may be four (4) or more bytes long with a payload having a maximum length of 184 bytes. Transport stream packets are part of one or more programs which are assembled into a transport stream. The transport stream is then transmitted over a channel with a particular transfer rate.
However, transmission of packets over a noisy communication channel, e.g., wireless communication, may cause corruption in the packets received by a receiver/decoder. Furthermore, some data streams or bitstreams carry compressed data that are correlated in a manner such that partial loss of a packet may cause the receiver/decoder to discard the entire packet. Namely, compression methods are useful for representing information as accurately as possible with a minimum number of bits and thus minimizing the amount of data that must be stored or transmitted. To further increase compression efficiency, some compression methods employ “significance-based” information, e.g., a significance map-value model, to indicate to a receiver/decoder the significance of the transmitted information or absence of transmitted information. The “significance-based” information is often previously defined, e.g., using symbols, such that the receiver/decoder is able to decipher additional information from the transmitted information. However, the loss of compressed data such as “significance-based” information often results in substantial errors when a receiver/decoder attempts to decompress or decode the corrupted data.
For example, a useful compression technique appears in the Proceedings of the International Conference on Acoustics, Speech and Signal Processing, San Francisco, Calif. March 1992, volume IV, pages 657-660, where there is disclosed a signal compression system which applies a hierarchical subband decomposition, or wavelet transform, followed by the hierarchical successive approximation entropy-coded quantizer. A wavelet pyramid, also known as critically sampled quadrature-mirror filter (QMF) subband representation, is a specific type of multiresolution hierarchical subband representation of an image. A wavelet pyramid was disclosed by Pentland et al. in Proc. Data Compression Conference Apr. 8-11, 1991, Snowbird, Utah. A QMF subband pyramid has been described in “Subband Image Coding”, J. W. Woods ed., Kluwer Academic Publishers, 1991 and I. Daubechies,
Ten Lectures on Wavelets,
Society for Industrial and Applied Mathematics (SIAM): Philadelphia, Pa., 1992.
Wavelet transforms are applied to an important aspect of image coding: the coding of a binary map (a wavelet tree) indicating the locations of the non-zero values, otherwise known as the significance map of the transform coefficients. Typically, a large fraction of the bit budget must be spent on encoding the significance map. It follows that a significant improvement in encoding the significance map translates into a significant improvement in the compression of information preparatory to storage or transmission.
To accomplish this task, a new structure called a zerotree has been developed. A wavelet coefficient is said to be insignificant with respect to a given threshold T, if the coefficient has a magnitude less than T. The zerotree is based on the hypothesis that if a wavelet coefficient at a coarse scale is insignificant with respect to a given threshold T, then all wavelet coefficients of the same orientation in the same spatial location at finer scales are likely to be insignificant with respect to T.
More specifically, in a hierarchical subband system, with the exception of the highest frequency subbands, every coefficient at a given scale can be related to a set of coefficients at the next finer scale of similar orientation according to a structure called a wavelet tree. The coefficients at the coarsest scale will be called the parent nodes, and all coefficients corresponding to the same spatial or temporal location at the next finer scale of similar orientation will be called child nodes.
Given a threshold level to determine whether or not a coefficient is significant, a node is said to be a ZEROTREE ROOT if 1) the coefficient at a node has an insignificant magnitude, 2) the node is not the descendant of a root, i.e., it is not completely predictable from a coarser scale, and 3) all of its descendants are insignificant. A ZEROTREE ROOT is encoded with a special symbol indicating that the insignificance of the coefficients at finer scales is completely predictable. To efficiently encode the binary significance map, a plurality of symbols are entropy coded: ZEROTREE ROOT, VALUED ZEROTREE ROOT, ISOLATED ZERO, and two non-zero symbols, POSITIVE SIGNIFICANT and NEGATIVE SIGNIFICANT.
Unfortunately, the loss of data in a packet associated with the significance map, i.e., the loss of a symbol for a node in a wavelet tree, will often cause a significant error or loss of data. Therefore, there is a need in the art for an apparatus and method for packetizing significance-based information to improve error resilience, regardless of the packet protocol that is employed.
SUMMARY OF THE INVENTION
The present invention is an apparatus and a concomitant method of packetizing significance-based information to improve error resilience. More specifically, in one embodiment, the significance-based information is wavelet-based information that comprises “coefficient significance information” (e.g., zerotree symbols) and “coefficient values”. Within each packet, the “coefficient significance information” are coded first into a first or front portion of the packet and then the “coefficient values” are coded into a second or back portion of the packet.
More specifically, the present invention organizes the bitstream in a manner such that the “coefficient significance information” for all pixels in the same packet (or within a texture unit) are coded first, followed by a resynchronization marker (e.g., RESYNCH), and then the coefficient values of all nonzero pixels in the packet (or a texture unit).
Alternatively, in a second embodiment, the “coefficient significance information” and the signs (positive or negative) of the coefficient values are coded first, followed by a resynchronization marker (e.g., RESYNCH), and then the absolute coefficient values of all nonzero pixels in the packet (or a texture unit).
The present coding method and packet structures provide error resilience. Namely, if an error occurs in the “value portion” of the packet (or a texture unit), the receiver/decoder can still recover at least the coefficient significance information, e.g., the zerotree symbols, for all pixels in the packet (or a texture unit).
REFERENCES:
patent: 5315670 (1994-05-01), Shapiro
patent: 5321776 (1994-06-01), Shapiro
patent: 5412741 (1995-05-01), Shapiro
patent: 5563960 (1996-10-01), Shapiro
patent: 5598415 (1997-01-01), Nuber et al.
patent: 5856973 (1999-01-01), Thompson
patent: 5995146 (1999-11-01), Rasmussen
patent: 6011587 (2000-01-01), Sakazawa et al.
patent: 0 860
Chai Bing-Bing
Sodagar Iraj
Burke W. J.
Dang Duy M.
Johns Andrew W.
Sarnoff Corporation
LandOfFree
Apparatus and method for packetizing significance-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for packetizing significance-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for packetizing significance-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3157237