Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-02-22
2003-07-01
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Transform coding
C708S402000
Reexamination Certificate
active
06587590
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to calculating the 2-Dimensional 8×8 Discrete Cosine Transform (2-D DCT) and the Inverse Discrete Cosine Transform (2-D IDCT), and its very large scale integrated (VLSI) implementation. Specifically, the present invention is well suited to meet the real time digital processing requirements of digital High-Definition Television (HDTV)
2. Related Art
OUTLINE OF RELATED ART SECTION
1.0 Overview of Video Coding and MPEG Implementations
1.1 Video Compression
1.2 MPEG Video Compression: A Quick Look
1.2.1 MPEG Video Sequences, Groups and Pictures
1.2.2 MPEG Video Slice, Macroblock and Block
1.2.3 The Motion Estimation/Compensation in MPEG
1.2.4 The Discrete Cosine Transform in MPEG
1.2.5 The Quantization in MPEG
1.2.6 The Zigzag Scan and Variable Length Coding in MPEG
1.2.7 MPEG Video Encoding Process
1.2.8 MPEG Video Decoding Process
1.3 MPEG-1 Video Standard
1.4 MPEG-2 Video Standard
1.4.1 Fields, Frames and Pictures
1.4.2 Chrominance Sampling
1.4.3 Scalability
1.4.4 Profiles and Levels
1.5 Hybrid Implementation Scheme for MTEG-2 Video System
2.0 DCT/IDCT Algorithms and Hardware Implementations
2.1 Introduction
2.2 1-D DCT/IDCT Algorithms and Implementations
2.2.1 Indirect 1-D DCT via Other Discrete Transforms
2.2.2 1-D DCT via Direct Factorizations
2.2.3 1-D DCT Based on Recursive Algorithms
2.2.4 1-D DCT/IDCT Hardware Implementations
2.3 2-D DCT/IDCT Algorithms and Implementations
2.3.1 2-D DCT via Other Discrete Transforms
2.3.2 2-D DCT by Row-Column Method (RCM)
2.3.3 2-D DCT Based on Direct Matrix Factorization/Decomposition
2.3.4 2-D DCT/IDCT Hardware Implementations
2.4 Summary
1.0 OVERVIEW OF VIDEO CODING AND MPEG IMPLEMENTATIONS
In this section, a brief overview of video compression, Moving Pictures Experts Group (MPEG) video protocols and different implementation approaches are presented. A list of references cited in this application is included in an Appendix. Each of these reference listed is incorporated herein by reference in its entirety.
1.1 Video Compression
The reduction of transmission and storage requirements for digitized video signals has been a research and development topic all over the world for more than 30 years.
Many efforts have been made trying to deliver or store digital television signals, which have a bit-rate of more than 200 Mbit/s in an uncompressed format and must be brought down to a level that can be handled economically by current video processing technology. For example, suppose the pictures in a sequence are digitized as discrete grids or arrays with 360 pels (picture elements) per raster line, 288 lines/picture (a typical resolution for MPEG-1 video compression), three-color separation and sampled with 8-bit precision for each color, the uncompressed video sequence at 24 pictures/second is roughly 60 Mbit/s, and a one-minute video clip requires 448 Mbytes of storage space.
The International Standardization Organization (ISO) started its moving picture standardization process in 1988 with a strong emphasis on real-time decoding of compressed data stored on digital storage devices. A Moving Pictures Experts Group (MPEG) was formed in May 1988 and a consensus was reached to target the digital storage and real-time decoding of video with bit-rates around 1.5 Mbit/s (MPEG-1 protocol) [MPEG1]. At the MPEG meeting held in Berlin, Germany on December 1990, a MPEG-2 proposal was presented that primarily targeted for higher bit-rates, larger picture sizes, and interlaced frames. The MPEG-2 proposal attempted to address a much more broader set of applications than MPEG-I (such as television broadcasting, digital storage media, digital high-definition TV (HDTV) and video communication) while maintaining all of the MPEG-1 video syntax. Moreover, extensions were adopted to add flexibility and functionality to the standard. Most importantly, a spatial scalable extension was added to allow video data streams with multiple resolutions to provide support for both normal TV and HDTV. Other scalable extensions allow the data stream to be partitioned into different layers in order to optimize transmission and reception over existing and future networks [MPEG2].
An overview of MPEG video compression techniques, MPEG-1's video layers and MPEG-2's video layers is presented in section 1.2, 1.3 and 1.4, respectively. A proposed hybrid implementation scheme for MPEG-2 video codec is shown in section 1.5. An outline of rest of the thesis is presented in section 1.6.
1.2 MPEG Video Compression: A Quick Look
An MPEG video codec specifically designed for compression of video sequences. Because a video sequence is simply a series of pictures taken at closely spaced time intervals, these pictures tend to be quite similar from each other except for when a scene change takes place. The MPEG1 and MPEG2 codecs are designed to take advantage of this similarity using both past and future temporal information (inter-frame coding). They also utilize commonality within each frame, such as a uniform background, to lower the bit-rate (intra-frame coding) [MPEG1, MPEG2].
1.2.1 MPEG Video Sequences, Groups and Pictures
An MPEG video sequence is made up of individual pictures occurring at fixed time increments. Except for certain critical timing information in the MPEG systems layers, an MPEG video sequence bitstream is completely self-constrained and is independent of other video bitstreams.
Each video sequence is divided into one or more groups of pictures, and each group of pictures is composed of one or more pictures of three different types: I-, P- and B-type. I-pictures (intra-coded pictures) are coded independently, entirely without reference to other pictures. P- and B-pictures are compressed by coding the differences between the reference picture and the current one, thereby exploiting the similarities from the current to reference picture to achieve high compression ratio. One example of a typical MPEG I-, P- and B-pictures arrangement in display order is illustrated in FIG.
1
.
The first coded picture in each video sequence must be an I-picture. I-pictures may be occasionally inserted in different positions of a video sequence to prevent the coding error propagation. For I-pictures, the coding method used by MPEG is similar to that defined by JPEG [JPEG].
P-pictures (predictive-coded pictures) obtain predictions from temporally preceding I- or P-pictures in the sequence and B-pictures (bidirectionally predictive-coded pictures) obtain predictions from the nearest preceding and/or upcoming I- or P-pictures in the sequence. B-pictures may predict from preceding pictures, upcoming pictures, both, or neither. Similarly, P-pictures may predict from a preceding picture or use intra-coding.
A given sequence of pictures is encoded in a different order which they are displayed when viewing the sequence. An example of the encoding sequence of MPEG I-, P- and B-pictures is illustrated in FIG.
2
.
Each component of a picture is made up of a two-dimensional (2-D) array of samples. Each horizontal line of samples in this 2-D grid is called a raster line, and each sample in a raster line is a digital representation of the intensity of the component at that point on the raster line. For color sequences, each picture has three components: a luminance component and two chrominance components. The luminance provides the intensity of the sample point, whereas the two chrominance components express the equivalent of color hue and saturation at the sample point. They are mathematically equivalent to RGB primaries representation but are better suited for efficient compression. RGB can be used if less efficient compression is acceptable.
The equivalent counterpart of a picture in broadcast video (for example analog NTSQ) is a frame, which is further divided into two fields. Each field has half the raster lines of the full frame and the fields are interleaved such that alternate raster lines in the frame belong to alternate fields.
1.2.2 MPEG Video Slice
Sterne Kessler Goldstein & Fox P.L.L.C.
The Trustees of the University of Pennsylvania
Tran Phuoc
LandOfFree
Method and system for computing 8×8 DCT/IDCT and 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 Method and system for computing 8×8 DCT/IDCT and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for computing 8×8 DCT/IDCT and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000807