Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-02-22
2002-04-16
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06374279
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of image processing and synthesis, and more particularly to decreasing line delay and other implementation resource requirements in finite impulse response (FIR) filters.
BACKGROUND OF THE INVENTION
In computers and other video processing systems, a utilized video output device (such as a monitor or television set) often has far lower resolution than the available video signal source. The data must therefore be re-formatted for the reduced output signal resolution. When re-formatting video images, it is necessary to filter and scale the image in both the vertical and horizontal dimensions. Filtering is normally performed prior to scaling to prevent the formation of aliasing artifacts, which would be introduced as a result of a scaling-induced decreased sampling rate. These and related terms are described and illustrated in chapter 14 of Computer Graphics, Principles and Practice, Foley, et al., published by Addison Wesley, 1996, incorporated herein by reference. The inventive system described herein improves the performance of the vertical filtering portion of this process.
FIG. 1
illustrates a system block diagram showing the placement of a vertical filter and scaler
110
and its position relative to other elements
120
-
150
of an image processing system. In the available art, the traditional method of filtering and scaling is to use a set of low pass Finite Impulse Response (FIR) filters to reduce image aliasing (also known as pre-filtering). Next, re-sampling the image at new sample positions scales the FIR filter output signal. Scaling is often accomplished with a simple bilinear interpolator, which creates a sample based on two adjacent source samples provided as input signals.
To provide a more detailed understanding of the available art, an available Vertical Filter and Scaler (VFS)
200
is illustrated in FIG.
2
. The incoming video stream arrives interlaced. An interlaced video signal represents a picture as two separate fields. Each field usually represents half the lines in a frame. A frame represents one complete picture out of a sequence of pictures that make up a moving image. Typically, the lines in the first field will represent all the odd numbered lines in the frame and the second field will contain all the even numbered lines. In this way, the lines from one field fall between the lines of the other field with which they are interlaced. Thus, two adjacent lines in a video signal are spatially two lines apart in a frame and the line between them already occurred in the previous field. Therefore, to allow three spatially consecutive lines to be processed simultaneously, the middle line must be delayed for the period of one field so that it is available contemporaneously with the other two lines. Thus, while i
n−1
visually precedes i
n
on the screen, because the input video signal is interlaced, input signal i
n−2
is derived from the line that arrived immediately before line i
n
, and line i
n−1
is actually from a corresponding line one “field” time before line i
n
. The interlaced input signals to VFS
200
arrive as i
n
, i
n−1
and i
n−2
. These three lines are processed by Adaptive De-interlace Filter
210
which forwards three de-interlaced lines d
n−2
, d
n−1
and d
n
. The incoming video stream is thereby de-interlaced and the output signal is a non-interlaced (also referred to in the art as “progressive”) video stream scaled to a desired height.
The three de-interlaced lines d
n−2
, d
n−1
and d
n
are fed to the input terminals of a 3-tap anti-aliasing FIR filter
230
, comprising a fixed coefficient filter having coefficients of whole powers of two. Having coefficients of whole powers of two allows for a simpler implementation of the filter over a “true” variable coefficient filter, since only additions need be performed instead of multiplications. FIR filter
230
thus produces a filtered version of d
n−1
, referred to as f
n−1
. While a fixed coefficient filter is easier to construct, it does not allow a variable amount of filtering to be applied to the signal. This function is performed by a cross-fader
250
which linearly mixes the filtered and non-filtered values of d
n−1
according to the value of the control K
f
according to the following equation:
m
n−1
=K
f
·f
n−1
+(1−
K
f
)·d
n−1
{Where 0
<=K
f
<=1}
Using this method, it is known in the art to create a variable low pass filter (LPF) without the need for the complexity of a variable coefficient filter.
However, since the input signal has been de-interlaced, there need to be two lines output for every new input line (i
n
is the only truly new input line—i
n−1
and in
n−2
are just older, delayed versions of the input lines). It is therefore necessary in the available art to have a second FIR/cross-fader pair, illustrated as elements
220
and
240
in FIG.
2
. Unfortunately, having a second FIR
240
raises a need for input line d
n−3
to be derived and forwarded to FIR filter
220
. Since signal d
n−3
is not coming from De-Interlace Filter
210
, signal d
n−3
is obtained by delaying d
n−1
by one (input) line.
It should be noted that a single input line delay is effectively the same as a two output-line delay. Since the output signal has been de-interlaced, a complete frame of video is produced on the output terminal for every field that is received at the input terminal. This results in twice as many lines being output as input. Thus, two lines are produced on the output terminal in the same time as a single line is input. This is achieved in the available art by including delay line
260
, illustrated in FIG.
2
.
There are now two de-interlaced and anti-alias filtered lines m
n−1
and m
n−2
coming from the low pass filter
205
. The last step is to vertically scale these output signals to the desired vertical resolution. Vertical scaling is achieved by using an additional pair of cross-faders
280
and
290
to linearly interpolate the LPF output signals to provide lines line
n−2
and line
n−3
. Scaling constants K
0
and K
1
effectively determine the positions of line
n−3
and line
n−2
with respect to lines m
n−3
, m
n−2
and m
n−1
. Therefore, signal m
n−3
, which is not available at the output terminal of the LPF, is obtained by again delaying one of the output signals of the previous stage (m
n−1
) with a second, one-line delay
270
.
Thus, the shortcomings of the available architecture become apparent. The biggest cost element in the existing architecture are the line delays, which consume significant physical resources in the form of storage capacity, and consume Memory Controller
130
resources in the form of memory access bandwidth. For example, for a typical digital video input signal with an image size of 487 lines of 720 pixels, 16 bits per pixel and 30 frames per second, the required resources are as follows:
Storage cost=720×16×2=23,040 bits of storage.
Bandwidth cost=487×720×30×16×4=673 million bits per second (where the factor of 4 is included to accommodate two cycles for reading and two for writing). Those skilled in the relevant art will understand that the cost of the logic to implement various filter components is small compared to the cost of implementing the delay lines.
There is therefore a need in the art for a circuit and method that reduces the delay line resource requirements found in the available art.
SUMMARY OF THE INVENTION
To address the shortcomings of the available art, the present invention provides a dual variable finite impulse response (“FIR”) filter (and method for filtering using such a circuit), comprising a filter element for receiving a data signal and generating a filtered signal, a first signal mixer mixing the data signal with the filtered signal
Malzahn David H.
nVidia U.S. Investment Company
Silicon Valley IP Group
Zilka Kevin J.
LandOfFree
System and method for increasing dual FIR filter efficiency does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for increasing dual FIR filter efficiency, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for increasing dual FIR filter efficiency will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2907770