Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-12-24
2001-10-16
Kelley, Chris (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06304604
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to computer systems and more specifically to efficient data transmission between MPEG video compression stages.
Decompression and compression of video and audio data is used for video playback and for teleconferencing applications. Video playback and teleconferencing applications require compression methods that are capable of reducing video frame data to the smallest number of bits that can accurately represent the original signal. The main reasons for this are to enable real-time transmission of the compressed files across integrated services data networks (ISDN) lines and across standard telephone (POT) lines, and to reduce the required amount of data storage space.
There are many types of video compression and decompression techniques provided in the art. Seven of these techniques include the MPEG, MPEG-2 and MPEG-4 standards developed by the Moving Pictures Experts Group, the IPEG standard, the JPEG standard developed by the Joint Picture Experts Group, the P×64 standards, and the H.26× video teleconferencing standards. Each standard uses a variety of encoding methods for encoding frames of sound and video data. For example, the MPEG standards use a combination of Huffman run-level encoding, quantization, discrete cosine transfer (DCT), and motion compensation to compress, or encode, sound and video data Regardless of the standard that is used, the procedures used to compress a file are simply reversed to uncompress, or decode, that file.
The MPEG procedures used during decompression of compressed data would be performed in a pipeline manner as follows. First, a compressed data file is accessed by the system that is to perform the decompression. The compressed file is comprised of variable length codes, referred to as Huffman run-level codes, which represent patterns of logical ones and zeroes. The Huffman run-level codes enable those patterns to be represented in a manner that occupies a significantly smaller amount of memory than the patterns otherwise would. For example, the shortest Huffman run-level codes represent patterns of logical ones and zeroes that are most frequently encountered. Likewise, the longest Huffman run-level codes represent patterns of logical ones and zeroes that are least frequently encountered. Accordingly, the most frequently encountered patterns are replaced with the shortest Huffman run-level codes, thereby producing a significant reduction in storage space.
When the system accesses a compressed file, it is parsed to extract the Huffman run-level codes. The Huffman run-level codes are then reconverted into the patterns of logical ones and zeroes that they represent. Those patterns will be referred to as coefficients. Typically the coefficients are arranged in groups of sixty four, and further arranged in eight-by-eight matrices organized in the order in which they are translated from the run-level codes. Such a matrix is comprised of storage locations in a memory storage unit. Those storage locations are logically arranged in a row and column configuration and are accessed with respect to their relative position with the matrix.
It should be noted that although eight-by-eight matrices of coefficients are typically used in the art, four-by-four matrices will be used for simplicity of illustration. One of ordinary skill in the art will be able to scale the illustrations appropriately to the eight-by-eight implementation.
For illustration purposes, consider a group of sixteen coefficients (C
n
), each having eight bits of data. The coefficients are arranged in the following four-by-four coefficient matrix where C
1
is the first coefficient translated:
&LeftBracketingBar;
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
C13
C14
C15
C16
&RightBracketingBar;
&AutoRightMatch;
The second stage of the decompression pipeline is the inverse quantization stage wherein an element-wise multiplication is performed. The element-wise multiplication multiplies each of the coefficients in the four-by-four matrix by corresponding quantization factors (Qf
n
) stored in a quantization matrix. The quantization matrix is the same size as the coefficient matrix, in this case 4×4. The multiplication is performed as follows:
&LeftBracketingBar;
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
C13
C14
C15
C16
&RightBracketingBar;
×
&LeftBracketingBar;
QF1
QF2
QF3
QF4
QF5
QF6
QF7
QF8
QF9
QF10
QF11
QF12
QF13
QF14
QF15
QF16
&RightBracketingBar;
=
&LeftBracketingBar;
Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9
Q10
Q11
Q12
Q13
Q14
Q15
Q16
&RightBracketingBar;
For example, Q1 is the product of coefficient C1 and quantization factor QF1. Therefore inverse quantization operation scales each coefficient by the associated quantization factor. In this manner, coefficients can be stored using a smaller representative number of bits and, upon inverse quantization, the coefficients are returned to their original representation.
Upon completion of the inverse quantization operation, the coefficients are each represented by a sixteen bit word The resulting sixteen-bit coefficients are packed into eight longwords (32 bit words) in the following arrangement:
&LeftBracketingBar;
Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9
Q10
Q11
Q12
Q13
Q14
Q15
Q16
&RightBracketingBar;
&AutoRightMatch;
The coefficients in the above mentioned matrix are input to the third stage of the decompression pipeline, referred to as the inverse discrete cosine transfer stage. When the files are compressed, a discrete cosine function is applied to each eight-by-eight block of coefficients using the following equation:
F
(
u
,
v
)
=
1
4
C
(
u
)
C
(
v
)
∑
x
=
0
7
∑
y
=
0
7
f
(
x
,
y
)
×
cos
[
(
2
x
+
1
)
μπ
16
]
cos
[
(
2
y
+
1
)
v
π
16
]
To reverse the effects of the discrete cosine transfer an inverse discrete cosine function is performed, thereby restoring the original data. The inverse cosine function is applied using the following equation:
f
(
u
,
v
)
=
1
4
∑
x
=
0
7
∑
y
=
0
7
C
(
u
)
C
(
v
)
F
(
u
,
v
)
×
cos
[
(
2
x
+
1
)
μπ
16
]
cos
[
(
2
y
+
1
)
v
π
16
]
Because the two-dimensional discrete cosine transfer is an orthogonal function with orthonormal basis vectors, it can be performed as a series of one-dimensional row transforms followed by a series of one-dimensional column transforms. Accordingly, the inverse discrete cosine transform operation is also performed in two one-dimnensional portions, i.e. a series of row transforms followed by a series of column transforms. The row operation portion is typically performed first. The sixteen-bit data in the matrix of the inverse quantization stage is re-ordered in the following manner and input to the inverse discrete cosine transform row operation:
&LeftBracketingBar;
Q1
Q2
Q5
Q6
Q9
Q10
Q13
Q14
&LeftBracketingBar;
Q3
Q4
Q7
Q8
Q11
Q12
Q15
Q16
&RightBracketingBar;
&AutoRightMatch;
Because each of the elements typically include sixteen bits of data, each row of the matrix represents two longwords. The coefficients are output from the inverse quantization stage in the same order that the row transform operation requires. Therefore the individual words are not re-ordered but are simply packed into the two-longword pairs.
Conversely, the column operation portion of the inverse discrete cosine transfer requires a significantly different configuration of coefficients from that which is required for the row operation portion. Specifically, the rows and columns of the matrix used in the row operations need to be exchanged, or transposed. Typically a transpose operation is required to arrange the coefficients output from the inverse quantization stage into the following order:
&LeftBracketingBar;
Q1
Q5
Q2
Q6
Q3
Q7
Q4
Q8
&LeftBracketingBar;
Q9
Q13
Q10
Q14
Q11
Q15
Q12
Q16
&RightBracketingBar;
&AutoRightMatch;
The transpose operation is performed by copyin
Adiletta Matthew
Meng Teresa
Stepanian Robert
Compaq Computer Corporation
Hamilton Brook Smith & Reynolds P.C.
Kelley Chris
Vo Tung
LandOfFree
Method and apparatus for configuring compressed data... 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 apparatus for configuring compressed data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for configuring compressed data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2603574