Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2002-09-25
2004-01-06
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C375S240190
Reexamination Certificate
active
06674911
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates in general to data compression techniques. More specifically, the present invention relates to a compressed data stream generated in accordance with data compression technique using hierarchical subband decomposition of a data set and set partitioning of data points within the hierarchical subband decomposition using hierarchical trees. Moreover, the present invention relates to a data structure facilitating decoding and encoding of a subband decomposition of data points and compressed data containing that data structure. In particular, the present invention relates to N-dimensional data compression and recovery using set partitioning in hierarchical trees.
As the amount of information processed electronically increases, the requirement for o information storage and transmission increases as well. Certain categories of digitally processed information involve large amounts of data, which translates into large memory requirements for storage and large bandwidth requirements for transmission. Accordingly, such storage and/or transmission can become expensive in terms of system resource utilization, which directly translates into economic expense. It will be appreciated that the digitally processed information can be one dimensional (1-D) information, e.g., audio data, two dimensional (2-D) information, e.g., image data, or three dimensional (3-D) information, e.g., video data. These examples are illustrative, rather than limiting.
With respect to 2-D data, many data compression techniques have been employed to decrease the amount of data required to represent certain digitized information. For example, compression techniques have been applied to the data associated with a bit-mapped image. One prior data compression technique devoted to image data is the ISO/JPEG (International Standards Organization/Joint Photographic Experts Group) data compression standard. Although the ISO/JPEG technique has been adopted as an industry standard, its performance is not optimal.
Recently, techniques using hierarchical subband decomposition, also known as wavelet transforms, have emerged. These techniques achieve a hierarchical multi-scale representation of a source image. For example, subband decomposition of video'signals, i.e., 3-D information, is disclosed in U.S. Pat. No. 5,223,926 to Stone et al. and U.S. Pat. No. 5,231,487 to Hurley et al., each of which is incorporated herein by reference in its entirety. However, once subband decomposition of a source image has been performed, the succeeding techniques of coding the resultant data for transmission and/or storage have yet to be fully optimized. Specifically, for example, both the computational efficiency and coding efficiency of the prior techniques may be further improved. One prior technique has been disclosed by A. Said and W. Pearlman in “Image Compression Using the Spatial-Orientation Tree.” IEEE Int. Symp. on Circuits and Systems, Vol. 1, pp.279-282, May 1993, which is also incorporated herein by reference in its entirety.
With respect to 3-D data, the demand for video for transmission and delivery across both high and low bandwidth channels has accelerated. The high bandwidth applications include digital video by satellite (DVS) and high-definition television (HDTV), both based on MPEG-2 compression technology. The low bandwidth applications are dominated by transmission over the Internet, where most modems transmit at speeds below 64 kilobits per second (Kbps). Under these stringent conditions, delivering compressed video at an acceptable quality level becomes a challenging task, since the required compression ratios are quite high. Nonetheless, the current test model standards of H.263 and H.263+ do a creditable job in providing video of acceptable quality for certain applications at high bit rates sought by ISO's MPEG-4, which also seeks low bit rates, and ITU's H.26L standards groups, but better schemes with increased functionality are actively being sought by the MPEG-4 and MPEG-7 standards committees.
The current and developing standards of MPEG-2, H.263, H.263+, MPEG-4, and H.26L are all based on block DCT coding of displaced frame differences, where displacements or motion vectors are determined through block-matching estimation methods. Although reasonably effective, these standards lack the inherent functionality now regarded as essential for emerging multimedia applications. In particular, resolution and fidelity (rate) scalability, the capability of progressive transmission by increasing resolution and increasing fidelity, is considered essential for emerging video applications to multimedia. Moreover, if a system is truly progressive by rate or fidelity, then it can presumably handle both the high-rate and low-rate regimes of digital satellite and Internet video, respectively. The current and emerging standards use a hybrid motion-compensated differential discrete cosine transform (DCT) coding loop, which must use a base layer of reasonable fidelity and add layers of increasing fidelity upon it to achieve progressive fidelity. By its very nature, this kind of scheme allows no scalability or progressivity of the base layer and must suffer in accuracy compared to single layer coding at the same bit rate.
Subband coding has been shown to be a very effective coding technique. It can be extended naturally to video sequences due to its simplicity and non-recursive structure that limits error propagation within a certain group of frames (GOF). Three-dimensional (3-D) subband coding schemes have been designed and applied for mainly high or medium bit-rate video coding. Karlsson and Vetterli in their article entitled Three Dimensional Subband Coding of Video (Proc. ICASSP, pages 1100-1103, April 1988.), took the first step toward 3-D subband coding using a simple 2-tap Haar filter for temporal filtering. Podilchuk, Jayant, and Farvardin in the article Three-Dimensional Subband Coding of Video (IEEE Transactions on Image Processing, 4(2):125-139, February 1995), described the use of the same 3-D subband coding (SBC) framework without motion compensation. It employed adaptive differential pulse code modulation (DPCM), and vector quantization to overcome the lack of motion compensation.
Furthermore, Kronander, in his article entitled New Results on 3-Dimensional Motion Compensated Subband Coding (Proc. PCS-90, March 1990), presented motion compensated temporal filtering within the 3-D SBC framework. However, due to the existence of pixels not encountered by the motion trajectory, he needed to encode a residual signal. Based on the previous work, motion compensated 3-D SBC with lattice vector quantization was introduced by Ohm in his article entitled Advanced Packet Video Coding Based on Layered VQ and SBC Techniques (IEEE Transactions on Circuit and System for Video Technology, 3(3):208-221, June 1993). Ohm introduced the idea for a perfect reconstruction filter with the block-matching algorithm, where 16 frames in one GOF are recursively decomposed with 2-tap filters along the motion trajectory. He then refined the idea to better treat the connected/unconnected pixels with arbitrary motion vector field for a perfect reconstruction filter, and extended to arbitrary symmetric (linear phase) QMF's. See Three-Dimensional Subband Coding with Motion Compensation (IEEE Transactions on Image Processing, 3(5):559-571, September 1994). Similar work by Choi and Woods, described in their article Motion-Compensated 3-D Subband Coding of Video (Submitted to IEEE Transactions on Image Processing, 1997), employed a different way of treating the connected/unconnected pixels; this sophisticated hierarchical variable size block matching algorithm has shown better performance than MPEG-2.
Due to the multiresolutional nature of SBC schemes, several scalable 3-D SBC schemes have appeared. Bove and Lippman, in their article entitled Scalable Open-Architecture Television (
SMPTE J
., pages 2-5, January 1992) proposed multiresolutional video coding with a 3-D subban
Pearlman William A.
Said Amir
Johnson Timothy M.
Powell Raymond
Westerlund Robert
LandOfFree
N-dimensional data compression using set partitioning in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with N-dimensional data compression using set partitioning in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N-dimensional data compression using set partitioning in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3240908