Accurate averaging of elements using integer averaging

Details Accurate averaging of elements using integer averaging Accurate averaging of elements using integer averaging

2000-03-27

2003-01-28

Brier, Jeffery (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Attributes

C382S264000, C708S445000

Reexamination Certificate

active

06512523

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention pertains generally to computer processing. In particular, it pertains to obtaining accurate results when using integer averaging instructions that are inherently inaccurate because they round off the results.
2. Description of the Related Art
Many applications have been found in the computer field that involve averaging multiple numbers together. One such application is in the motion compensation (MC) algorithms used for encoding and decoding compressed digital data in the processing of moving video images. Basically, the MC operation includes a way to generate various pixels in a video frame being constructed, called the destination frame, based on related pixels from one or more reference frames. Averaging pixel values from the reference frame(s) is part of that process. Such averaging may reduce the information content in the resulting image, but this loss is more than compensated for by greatly reducing the amount of storage space required to store the video images and the amount of bandwidth required to transmit the video images.
FIG. 1
shows an example of representative pixel averaging. Block
11
is a block of pixels (also called pels) in a larger reference frame. Close-up view
12
shows an enlargement of four pixels a, b, c and d in the upper left corner of block
11
. The values of these four pixels are averaged together to produce a single pixel e, shown in close-up view
13
, which becomes the upper left pixel in block
16
of the destination frame. Typically, the values of all these pixels are represented as unsigned integers. Blocks
11
and
16
may contain different numbers of pixels.
This motion mode process is frequently referred to as “half-pel horizontally and half-pel vertically”, or simply “half-half pel”. In general, other averaging modes can be used such as “half-pel horizontal” prediction that averages two horizontally adjacent pixels, and “half-pel vertical” prediction that averages two vertically adjacent pixels.
A commonly used averaging operation can be defined as follows:
1. Half-pel: result=(value1+value2)//2
2. Half-half-pel: result=(value1+value2+value3+value4)//4
where “//” is defined as integer division with rounding to the nearest integer. Half-integer values are rounded away from zero. For example, a result of 3.5 would be rounded to 4. Since the results must be integers, the round off error from any single averaging function can produce a result that is inaccurate by as much as 0.5. This is acceptable, and even unavoidable, in the final result. But in multi-stage averaging operations, round off errors from each stage can accumulate, leading to errors in the final results that are significantly greater. Various conventional approaches have been tried to reduce the amount and/or frequency of occurrence of these errors.
Some computer instruction sets have an instruction that performs an integer averaging function between two numbers, thus permitting easy implementation of the pixel averaging function. If more than two pixels are being averaged, the operation must proceed in successive stages, potentially leading to the aforementioned accumulation of round off errors. In conventional approaches to reducing the final error, a tradeoff must be made between speed and accuracy.
One conventional approach is shown in the code and flow chart of
FIGS. 2A and 2B
, respectively. In a first stage, elements a and b are averaged to produce a first intermediate result ave
—
1, and elements c and d are averaged to produce a second intermediate result ave
—
2. In a second stage, the first and second intermediate results are averaged to produce a final result. This method is fast, but can produce an error of +0.5 in the first stage and an additional error of +0.5 in the second stage, resulting in an error of +1.0 in approximately 37% of the final results. The term ‘simd’ indicates the use of a Single Instruction Multiple Data (SIMD) instruction which simultaneously performs the same function on multiple parallel data elements in a packed format.
FIGS. 3A and 3B
show the code and flow chart, respectively, of a second conventional approach that modifies the first approach by subtracting the value “1” from one of the intermediate results before averaging those two results together in the second stage. This artificial method of blindly compensating for expected errors reduces the probability of getting an error of +1.0 to about 13%.
FIGS. 4A and 4B
show the code and flow chart, respectively, of a conventional brute force approach. All four pixel values are unpacked, added together, and divided by 4 (shifted to the right by two bits). A constant of ‘2’ (const
—
2
—
4_words) is also added to compensate for the fact that shifting to the right rounds down by truncating rather than rounding up as required. This approach is accurate but slow, since it requires eight unpack operations, eight add operations, two shift operations, and one pack operation.
Thus, each of the conventional approaches to averaging pixel values is either fast but inaccurate, or accurate but slow.
SUMMARY OF THE INVENTION
An embodiment of the invention includes a method of averaging pixel values, which includes performing a first stage operation by averaging first and second pixel values to produce a first intermediate integer result, and also by averaging third and fourth pixel values to produce a second intermediate integer result. A second stage operation is performed by averaging the first and second intermediate integer results to produce a third intermediate integer result. It is detected whether the first stage operation produced an error and whether the second stage operation produced an error. If both the first and second stages produced an error, a correction value is applied to the third intermediate integer result to produce a final pixel value.


REFERENCES:
patent: 4941190 (1990-07-01), Joyce
patent: 5271095 (1993-12-01), Yamada
patent: 5774600 (1998-06-01), Strongin et al.
patent: 5883824 (1999-03-01), Lee et al.
patent: 5886794 (1999-03-01), Kondo et al.
patent: 5917739 (1999-06-01), Wong
patent: 5940132 (1999-08-01), Kondo et al.
patent: 5982373 (1999-11-01), Inman et al.
patent: 6007232 (1999-12-01), Wong
patent: 6295376 (2001-09-01), Nakaya
patent: 6320593 (2001-11-01), Sobel et al.

Affiliated with

Also associated with

Rating

Accurate averaging of elements using integer averaging does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Accurate averaging of elements using integer averaging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accurate averaging of elements using integer averaging will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3029888