Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-08-19
2002-11-26
Moore, David (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S248000, C382S250000
Reexamination Certificate
active
06487319
ABSTRACT:
The invention relates to data processing in the field of digital multimedia communications. More particularly, the invention relates to a data locating method that rapidly identifies the location of a coding unit, e.g., a texture unit.
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 various International Standards. These standards include, but are not limited to, the Moving Picture Experts Group Standards (e.g., MPEG-1 (11172-*), MPEG-2 (13818-*) and MPEG-4 (14496-*)), H.261 and H.263. For example, 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 that 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 the loss of packets or corruption in the packets received by a receiver/decoder. Some data streams or bitstreams may carry compressed data that are so correlated such that partial loss of a packet may cause the receiver/decoder to discard the entire packet.
Additionally, the transmission channel may also forward the packets within a “connectionless network”, e.g., in accordance with Transmission Control Protocol/Internet Protocol(TCP/IP), where relevant packets may not be forwarded in successive order. Although packets are not lost or corrupted in a connectionless transfer environment, the packets that are representative of an encoded image may not arrive in the coding or scanning order in which the image was encoded.
This random reception of packets or loss of packets, require the decoder to quickly decode and then locate the decoded data as to its relative spatial location in the decoded image. The speed of the decoder in identifying the location of the data is important for several reasons.
First, low bit rate application, e.g., real time application, requires the display of the decoded image with low latency. Thus, it is important that the decoder is able to quickly map the data in accordance with its spatial location.
Second, if error recovery is necessary, e.g., implementing error concealment methods, then it is advantageous to quickly locate and map the uncorrupted data. This allows error concealment methods that are designed to exploit uncorrupted data to generate concealment data, to immediately compensate for missing data in the decoded image.
To illustrate, a compression technique may involve the transformation of an input image into transform coefficients using hierarchical subband decomposition. 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.
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.
A typical method of coding these transform coefficients is in tree depth scan order as shown in
FIG. 1
, where an image is decomposed into three levels of resolution. Specifically, the wavelet coefficients are coded in tree blocks fashion, where each tree block is represented by three separate coding units called “texture units” shown with different shadings. Each texture unit is representative of a tree structure starting from the lowest or coarsest AC band to the highest or finest AC band coefficients.
In operation, the packets carrying the texture units are randomly received, lost or corrupted. Since each packet may not be received in successive order that originally generated the packets, the decoder must properly identify the decoded texture unit's relative spatial location. Thus, noisy communication channel and connectionless transfer of packets require a decoder to rapidly de-packetize and decode the data stored in the payload of the packet and to implement error recovery method, if necessary.
Therefore, there is a need in the art for an apparatus and method for quickly identifying the spatial location of a coding unit, e.g., a texture unit, in a decoded image.
SUMMARY OF THE INVENTION
An embodiment of the present invention is an apparatus and a method for identifying the spatial location of a coding unit, e.g., a texture unit (TU), in a decoded image. Specifically, the present invention quickly computes and identifies the “starting point” of a texture unit, i.e., the location of the first coefficient of the texture unit. Although there are different texture unit structures (e.g., a tree block as a TU, a slice in a subband as a TU, slices in a decomposition layer as a TU, or a square block as a TU and the like), knowing the starting point of an k
th
texture unit will allow the decoder to quickly identify and map the k
th
texture unit across one or more subbands.
More specifically, the decoder first obtains information from the packet that identifies the texture unit number, i.e., the “k
th
” texture unit. The texture unit number is used to compute which color component the texture unit is located. Namely, if the input image is a color image, then each input image can be represented in three separate color components: luminance (Y), C
r
(U), and C
b
(V).
In turn, within each color component, the texture unit number is also used to compute which “subband” the texture unit is located. Namely, each decomposition level of the hierarchically decomposed image has a plurality of subbands, e.g., an HH band, an HL band and an LH band.
Finally, once a subband is identified for the texture unit, the texture unit number is used in junction with the width and height of the “DC” band to compute the starting point of the texture unit within the identified subband. In this fashion, the texture unit can be quickly identified and mapped by executing a plurality of uncomplicated arithmetic operations such as division, summation and the like.
REFERENCES:
patent: 5231487 (1993-07-01), Hurley et al.
patent: 5604824 (1997-02-01), Chui et al.
patent: 5764802 (1998-06-01), Simon
patent: 5764805 (1998-06-01), Martucci et al.
patent: 6137915 (2000-10-01), Chai
patent: 6269192 (2001-07-01), Sodagar et al.
patent: 6301222 (2001-10-01), Kovacevic et al.
patent: 2 303 031 (1997-02-01), None
Redmill et al., “The RREC: An Error Resilient Technique for Coding Varibale-Lenght Blocks of Data”, IEEE Transactions on Image Procesing, vol. 5, No. 4, Apr. 1996, pps. 565-574.*
Nosratinia et al., “Multi-Resolution Backward Video Coding”, IEEE International Conference on Image Processing, 1995, vol. 2, pps. 563-566.*
I
Burke William J.
Do Anh Hong
Moore David
Sarnoff Corporation
LandOfFree
Apparatus and method for identifying the location of a... 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 identifying the location of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for identifying the location of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2951201