Pulse or digital communications – Bandwidth reduction or expansion
Reexamination Certificate
1997-08-01
2001-11-06
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
C382S236000, C382S221000, C382S272000, C382S162000, C382S166000
Reexamination Certificate
active
06314136
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of graphics and image processors. More particularly, the present invention relates to a system and method for performing lossless wavelet-based image transformations with minimal bit precision.
2. Description of Related Art
Due to continuing advancements and use of digital imaging, systems are now experiencing difficulties in supporting the processing, transmission and storage of digital images in a cost-effective manner. For example, in order to display a non-compressed, color digital image on an archaic 640×480 pixel display screen, an enormous amount of data is required, approximately 921,600 bytes of storage when three (3) bytes are assigned for each pixel of the color digital image. Recently developed display screens are capable of displaying a 2000×2000 pixel image which would require about twelve (12) megabytes of storage. The amount of data required to transfer and store digital images, especially digital color images, is difficult to support and expensive to maintain. As a result, image compression, which reduces the amount of data required to represent a digital image, has become an integral part in the transmission and storage of digital images.
Typically, image compression is performed by an input image (e.g., a 640×480 color digital image) initially undergoes color space conversion. This involves converting Red, Green, Blue (RGB) information associated with each pixel of the input image into luminance and chrominance referred to as “YUV” values. Such conversion usually is usually performed on each pixel resulting in the conversion of successive blocks of pixels (individually referred to as a “pixel block”) associated with the input image. These pixel blocks may be configured with any selected sizing (e.g., 8×8 pixel blocks).
For an 8×8 pixel block, each Y, U, and V value undergoes a compaction frequency transformation. This results in matrices of sixty-four (64) transmission coefficients including (a) a primary transmission coefficient and (b) sixty-three (63) secondary transmission coefficients for each of the Y, U and V values. The primary transmission coefficient (referred to herein as a “DC coefficient”) constitutes the lowest spatial frequency associated with the pixel block. The secondary transmission coefficients (individually referred to as “AC coefficients”) constitute higher spatial frequencies necessary to show degrees of contrast. Examples of compaction frequency transformations include a well-known Discrete Cosine Transform (DCT) and a wavelet-based image transformation.
Referring to
FIGS. 1A-1C
, an example of a conventional wavelet-based image transformation is described below. If supporting conversion of successive pixel blocks, each pixel block
100
(e.g., an 8×8 pixel block in this example) is sub-divided into sixteen 2×2 pixel blocks
110
-
125
. For clarity sake, the operations performed by the conventional wavelet-based image transmission scheme will be discussed in reference to calculating the luminance (Y-value) for pixel block
100
starting with first pixel block
110
. First pixel block
110
includes Y-values referred to as P
00
, P
01
, P
10
and P
11
in which each Y-value is a data byte (i.e., 8-bits) representing an unsigned number ranging in value from 0-255. The calculation of chrominance (U-values and V-values) may be performed in a similar manner, but these values would be represented as signed numbers ranging from −127 to 128.
First, P
00
, P
01
, P
10
and P
11
are added together to produce a preliminary DC coefficient (referred to as “C
1
”) of first pixel block
110
. The preliminary DC coefficient would require 10-bits of memory because 2-bit precision is required to support the addition of four (4) 8-bit values. In this example, three (3) first-level AC coefficients (referred to as D
1
-D
3
) of first block
110
are also produced as set forth in FIG.
1
B. Each first-level AC coefficient requires 10-bits of memory. This process is continued for each of the other 2×2 pixel blocks
111
-
113
which, along with first pixel block
110
, form a 4×4 pixel block
130
. As a result, four (4) preliminary DC coefficients (C
1
-C
4
) and twelve (12) first-level AC coefficients (D
1
-D
12
) are produced, where preliminary DC coefficients (C
2
-C
4
) and their respective first-level AC coefficients D
4
-D
12
are calculated in the same fashion as C
1
and D
1
-D
3
associated with first pixel block
110
.
Next, preliminary DC coefficients (C
1
-C
4
) would be grouped together as a 2×2 pixel block to produce a DC coefficient of 4×4 pixel block
130
(referred to herein as a “second-level DC coefficient” C
1
2d
) and three (3) second-level AC coefficients (D
13
-D
15
) as shown in FIG.
1
C. The memory space required to support each second-level DC coefficient and second-level AC coefficients would be 12-bits since 4-bit precision is necessary.
Thereafter, as an iterative process, other second-level DC coefficients each 4×4 pixel block
130
-
133
of 8×8 pixel block
100
are calculated, and thereafter, are grouped in order to produce a single DC coefficient being a maximum 14-bits in length (i.e., 6-bit precision) and sixty-three (63) AC coefficients including three (3) third-level AC coefficients being 14-bits in length, twelve (12) second-level AC coefficients being 12-bits in length, and forty-eight (48) first-level AC coefficients being 10-bits in length. The increasing bit size of the coefficients poses two disadvantages.
A first disadvantage is that this scheme of wavelet-based image transformation does not perform efficient compression. This is due to the fact that AC/DC coefficients representative of larger pixel blocks require extra bits, causing lower spatial frequency coefficients to contain more bits than necessary.
A second disadvantage is that if compression is performed in hardware, adder circuitry supporting larger and larger bit widths is needed for each iteration in calculating DC and AC coefficients. Alternatively, adders supporting a universal bit width may be implemented, provided this bit width supports the maximum bit precision needed. However, such an architecture would unnecessarily increase processing time and overall cost of the system.
Accordingly, there exists a need for a system and method for improving the performance of losses, memory-efficient wavelet-based image transformation caused by substantial reduction in bit precision requirements.
SUMMARY OF THE INVENTION
A system and method used to perform lossless wavelet-based image transformations. In one embodiment, the method utilizes a bit precision reduction technique during the compaction frequency transformation. The method features producing at least luminance value for each row of pixels of a selected pixel block. The selected pixel block is a portion of an image upon which graphics operations are to be performed. Next, at a minimum, a determination is made as to whether a luminance value associated with a particular row of pixels of the selected pixel block is positive. Thereafter, a reduced luminance value is produced when the luminance value is determined to be positive, the reduced luminance value is represented by a lesser number of bits than the luminance value. These operations are performed on each luminance value associated with each row of the selected pixel block. Of course, in combination with these operations, further operations may be performed on the chrominance values in an identical manner.
As a result, an iterative process may be established to produce multiple transmission coefficients representative of low and high spatial frequencies. These transmission coefficients are calculated with reduced bit width requirements by reducing bit size of coefficients used to calculate the primary transmission coefficients and secondary transmission coefficients of an image.
REFERENCES:
patent: 4819061 (1989-04-01), Lang
patent: 5146324 (1992-09-01), Miller et a
An Shawn
Blakely , Sokoloff, Taylor & Zafman LLP
Creative Technology Ltd.
Kelley Chris
LandOfFree
Method for performing wavelet-based image compaction... 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 for performing wavelet-based image compaction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for performing wavelet-based image compaction... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2602031