Combined vertical filter for graphic displays

[0002] 1. Field of the Invention

[0003] The present invention relates to video displays. More particularly, the present invention relates to a combined vertical filter for processing computer graphic images.

[0004] 2. The Background Art

[0005] A desirable feature for a multimedia computer system is the ability to display computer graphics on a standard television (TV) screen. However, the format and characteristics of the two systems differ. Some of the differences are listed in Table 1.

[0006] Omitted from Table 1, and this disclosure, are details particular to the various formats of TV such as National Television Standards Committee (NTSC), Phase Alternative Line (PAL) and Sequential Couleur Avec Mémoire (SECAM). Those of ordinary skill in the art are familiar with conversions between the various TV formats and the present invention is not intended to be limited to use with any particular format.

[0007] Computer graphics images are typically noninterlaced. That is, the entire frame is stored, and displayed, line-by-line from top to bottom. The process repeats and the entire frame is re-scanned at a given refresh rate, for example 75 Hz. In contrast, TV formats typically use two interlaced fields to store and display an image. Each of the two frames contains every other line of the image, such as one with the even numbered lines and the other with the odd. The two fields are consecutively scanned, so that the viewer perceives the resulting image as a blend of the two individual fields. The technique of interlacing was originally developed, in the early days of television, to present a pleasing graphic image while allowing a lower data transfer rate than needed to update the entire image with each scan. Although modern computer systems are not constrained by data transfer rates to the same extent as were early TV systems, interlaced display formats for TV are unlikely to disappear soon.

[0008] Overscan is also a remnant of early systems that is now firmly embedded in TV formats. Because it was costly to build TV picture tubes that accurately displayed an image along the outside border, overscan was developed to hide the image border. Typically, 10% to 20% of the image is cropped, or not displayed. For example, the NTSC format contains 486 active horizontal lines per frame but only approximately 430 lines are visible on a TV. Overscan compensation, which makes these hidden lines visible, may be needed when displaying computer graphics on a TV. For example, the “Start” icon displayed in Microsoft® Windows® that typically appears in the lower left corner of the computer monitor may be outside the displayed area of a TV screen without overscan compensation.

[0009] Computer graphics often contain images with high vertical frequency. That is, adjacent horizontal lines may have a high contrast, such as a light rectangular window displayed on a dark background. High vertical frequency is less common in “natural images” created for display on a TV. High vertical frequency may lead to a “flicker” effect when the image is displayed in an interlaced format on a TV. The flicker effect is caused by the location of the horizontal edge shifting slightly as the two interlaced fields, the even lines and the odd lines, are consecutively scanned. The present invention uses a flicker filter to reduce this effect. Most TV displays do not include a flicker filter.

[0010] Another issue when displaying computer graphics on a TV is that of the multiple resolutions often used in computer displays and the fixed resolution of a given TV display format. That is, a computer system may be capable of generating, and displaying graphic images in multiple resolution, such as 640×480, 800×600, 1024×768 and 1280×960. However, a TV display format is typically defined around a single resolution such as the 486 active horizontal lines used by the NTSC format. In order to display a wide range of computer graphic images on a TV, a multimedia computer system would preferably not be limited to any one image resolution.

[0011] The present invention is directed at noninterlaced to interlaced conversion, vertical overscan compensation, vertical scaling, filtering high vertical frequency images and accepting computer graphic images in a variety of resolutions for display on a TV. While there are prior art techniques for individually performing these processes, the present invention efficiently combines the processes.

[0012] The last line of Table 1 describes two different color space formats that may be used by computer graphics and TV. These formats are well known to those of ordinary skill in the art, as are the formulas for converting between RGB and YUV color spaces. This conversion is not done by the present invention, although, the present invention may be used in conjunction with hardware or software that performs such a conversion. The present invention may be used with computer graphics using either RGB or YUV color spaces.

[0013] An apparatus and method for converting computer graphics images into a format suitable for display on a TV. A flicker filter is combined with a vertical scaling filter and/or vertical overscan compensation filter to produce an interlaced image formatted for display on a TV, more efficiently than if the processes occurred sequentially. The apparatus and method are not limited to any particular filter sizes or set of filter coefficient values. The apparatus and method may be used as part of a multimedia computer system.

[0014] FIG. 1 is a diagram depicting the filtering of an image with a 3-tap filter.

[0015] FIG. 2 is a data flow diagram of sequential flicker and scaling filters.

[0016] FIG. 3 is a data flow diagram in a combined filter in accordance with one embodiment of the present invention.

[0017] FIGS. 4A-C are timing diagrams of input and output for various scaling ratios.

[0018] FIG. 5 depicts scaling a noninterlaced input image and creating two scaled interlaced output frames.

[0019] Those of ordinary skill in the art will realize that the following description of the present invention is illustrative only and not in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled persons having the benefit of this disclosure.

[0020] The present invention converts computer graphic images into a format suitable for display on a standard television (TV) screen. It combines the processes of converting from noninterlaced to interlaced formats, vertical overscan compensation, flicker filtering and vertically scaling the size of an image. By combining these processes, the number of line buffers (memory) required, as well as the number of mathematical operations, are reduced compared to performing the operations separately. The invention thus allows the operations to be performed cheaper and faster. Alternatively, more sophisticated filtering could be performed on the image with same cost and speed as the prior art. The present invention does not provide horizontal overscan compensation or horizontal scaling. However, the present invention may be used in conjunction with horizontal image processing devices or methods.

[0021] Filtering digital signals with finite impulse response (FIR) filters is a common practice in digital signal processing, and it is known to those of ordinary skill in the art. An FIR filter can be described by the following transfer function:

[0022] H^z(z)=b_o+b₁z⁻¹+. . . +b_qz^−q

[0023] where H^z(z) denotes the z-transform. The impulse response, h(n), of an FIR is $h\left(n\right)=\{\begin{array}{cc}{b}_n& \mathrm{if}0\le n\le q\\ 0& \mathrm{otherwise}\end{array}$

[0024] There are an infinite number of possible FIRs, each distinguished by the values assigned to the coefficients b_n. An FIR with a total of p non-zero coefficients is often referred to as a p-tap filter.

[0025] Generally, a higher number of taps allows more complex filtering at the cost of requiring more memory and arithmetic processes. In the context of video image processing, a p-tap vertical filter typically requires p-1 lines of an image to be held in memory. This may be referred to as requiring p-1 line buffers.

[0026] The present invention preferably uses an FIR as a flicker filter in situations where high vertical frequency is present in the computer graphics image. One form of such a flicker filter may be a three-tap low pass filter, although, the present invention is not intended to be limited to any particular form of the filter. Low pass filters, as is known to those of ordinary skill in the art, are designed to pass low frequencies and block high frequencies. Such a three-tap filter may take the form:

[0027] H₁(z)=c₁+c₂z⁻¹+c₃z⁻²

[0028] where the coefficients are positive numbers and satisfy the constraint:

[0029] c₁+c₂+c₃=1

[0030] The impulse response h₁(n) of the filter is $h_1\left(n\right)=\{\begin{array}{cc}{c}_1& \mathrm{if}n=0\\ c_2& \mathrm{if}n=1\\ c_3& \mathrm{if}n=2\\ 0& \mathrm{otherwise}\end{array}$

[0031] For example, an FIR with c₁=¼, c₂=½, and c₃=¼ is one embodiment of such a three-tap low pass flicker filter. There are many others.

[0032] Referring to FIG. 1, a three-tap flicker filter is shown operating on an image. The filter coefficients 10 and 12 operate vertically on horizontal lines of image n−1 through n+2, denoted by reference numbers 14, 16, 18 and 20. Although the filtering is typically performed for each location within a horizontal line, FIG. 1 concentrates on a single horizontal position denoted as x. First, filter coefficients 10 are applied to three vertically adjacent lines of the image, n−1 14, n 16, and n+1 18, to produce filtered line n 22. Next, filter coefficients 12 are applied to lines n 16, n+1 18, and n+2 20, to produce filtered line n+1 24. That is, filter coefficients 10 are “shifted down” one line where they become filter coefficients 12. The three-tap flicker filter uses a weighted average of three vertically adjacent of the unfiltered image to decrease any large differences between adjacent lines. Those of ordinary skill in the art will readily recognize that varying the values of the filter coefficients will vary the amount of smoothing between lines. For example, coefficients c₁=0, c₂=1, and c₃=0 would provide no smoothing.

[0033] The embodiment shown in FIG. 1 does not filter horizontally adjacent data, only those at location x. The procedure depicted in FIG. 1 is repeated for each x value in a horizontal line of image data, such as x−1 and x+1.

[0034] Other filtering techniques, such as five-tap low pass filters, could also be used to reduce flicker. As discussed above, increasing the complexity of a filter typically requires more memory and processing operations. While increasing the complexity of a filter may well increase the quality of the filtered image, there are typically diminishing returns. In one embodiment of the present invention, a three-tap flicker filter is chosen as a reasonable balance between image quality, memory requirements and processing speed. Those of ordinary skill in the art will readily recognize that such an engineering judgment in selecting a preferred filter size is subject to the current, and expected, costs of memory and processing.

[0035] Conversion of an image from noninterlaced to interlaced formats may also be performed with filters such as FIRs. The simplest form of noninterlaced to interlaced conversion would be to skip every other line while creating an interlaced video frame. For example, use odd numbered lines for the first frame and even numbered lines for the second. Of course, more complex conversions are also possible.

[0036] Vertical scaling and overscan compensation can be combined with the noninterlaced to interlaced conversion process, using a single filter. This disclosure will use the term scaling filter to describe noninterlaced to interlaced conversion, vertically scaling an image, and vertically compensating for overscan of an image. Such a scaling filter could perform any one, or any combination of two or more of the processes. The scaling filter, however, only operates in the vertical direction on an image. Horizontal scaling, such as compensating for horizontal overscan may be required, but will not be a part of the present invention. The present invention may, however, be adapted to work in conjunction with a horizontal scaling and the present invention is not intended to be limited to images that do not require horizontal scaling.

[0037] In one embodiment of the present invention a two-tap FIR scaling filter is used, taking the form:

[0038] H₂(z)=d_1,y+d_2,yz⁻²

[0039] The impulse response h₂(n), of the filter is $h_2\left(n\right)=\{\begin{array}{cc}{d}_{1,y}& \mathrm{if}n=0\\ d_{2,y}& \mathrm{if}n=2\\ 0& \mathrm{otherwise}\end{array}$

[0040] The coefficients include the subscript “y” to denote that they may take on different values, at different y-locations, or different image lines. The coefficients satisfy the constraints:

[0041] d_1,y+d_2,y−1

[0042] d_2,y=frac(Δ·y+d₀)

[0043] where d_ois the interpolation initial phase, Δ is the interpolation increment and y is an output line counter value. The term phase will be further described below. The function frac (x) returns the fractional portion of the argument X. For example,frac (5/4)=0.2.

[0044] FIG. 2 illustrates a prior art design of sequential flicker 26 and scaling 28 filters. A 3-tap flicker filter 26, with coefficients c₁, c₂and C₃, is followed by the application of a 2-tap scaling filter with coefficients d₁and d₂. Line buffers 30 and 32 provide temporary storage for two lines of video input data; multipliers 34, 36 and 38, along with adder 40, are used to combine the flicker filter coefficients with the video input data. The flicker filtered data is then processed by the scaling filter 28 utilizing line buffers 42 and 44, and multipliers 46 and 48. Temporary values are summed by adder 50 and placed in output line buffer 68, for display.

[0045] The present invention combines both the flicker and scaling filters. In one embodiment the resulting 5-tap filter requires only two line buffers, plus an output buffer. Using the above flicker filter H₁(z) and scaling filter H₂(z), the combined filter H(z) is found by the convolution, denoted as *, of H₁(z) and H₂(z). $\begin{array}{c}H\left(z\right)=H_1\left(z\right)*H_2\left(z\right)\\ =\left(c_1+c_2{z}^{-1}+c_3{z}^{-2}\right)\left(d_{1,y}+d_{2,y}{z}^{-2}\right)\\ =c_1{d}_{1,y}+c_2{d}_{1,y}{z}^{-1}+\left(c_3{d}_{1,y}+c_1{d}_{2,y}\right)z^{-2}+c_2{d}_{2,y}{z}^{-3}+c_3{d}_{2,y}{z}^{-4}\\ =C_1+C_2{z}^{-1}{C}_3{z}^{-2}+C_4{z}^{-3}+C_5{z}^{-4}\end{array}$

[0046] Where the subscript “y” has been dropped for simplicity, although the coefficients can take on different values at different y locations.

[0047] A diagram of one embodiment of the present invention, used to implement a combined 5-tap filter, is shown as FIG. 3. This embodiment uses two line buffers, 54 and 56, three multipliers 58, 60 and 62, two adders, 64 and 66, and output buffer 68. Those of ordinary skill in the art will readily recognize that eliminating two line buffers and two multipliers, compared with sequential flicker and scaling filters, results in significant savings in terms of both component cost and processing time. Although multiplexers 70, 72 and 74 are required by the combined filter, these components are relatively inexpensive and do not significantly slow the throughput of the filter.

[0048] The present invention, unlike conventional designs, uses line buffers 54 and 56 for temporary storage during filtering. It also exploits the inherent fact that interlaced output occurs at one-half the rate that noninterlaced data is input to efficiently order the processing. Table 2 lists an example of the data in line buffers 54 and 56 and to output buffer 68 with each line of input for the combined filter shown by FIG. 3. Preferably, the calculations are done for an entire horizontal line at one time. In Table 2, C₁×I(n) denotes that coefficient C₁is multiplied by the array of values presenting line “n.”

[0049] As discussed above, the values of the coefficients may vary with the input line. For example, the value of C₁used with I(1) may not be the same as the value of C₁used with I(9).

[0050] Those of ordinary skill in the art will readily recognize that combined flicker and scaling filters need not be limited to 5-taps, such as shown in FIG. 3. However, other embodiments, such as 7-tap combined filters would require minor modifications to the data path of FIG. 3 and the buffer values of Table 2. Such modifications are within the abilities of those of ordinary skill in the art. The present invention is not intended to be limited to any particular size combined filter.

[0051] A control scheme is required for a combined filter in order to synchronize the input data stream with the output. For example, noninterlaced to interlaced conversion produces output at one-half the rate of the input. Two other factors also affect the timing of input and output: differences in refresh rate and overscan compensation/scaling. The computer graphic image may have been created for a 75 Hz noninterlaced refresh rate, while the TV format is an interlaced 60 Hz. Similarly, as will be discussed in detail below, overscan compensation/scaling can effect the synchronization between the input and output data.

[0052] Many techniques are available for controlling and synchronizing, such as using separate timing generators for input and output, or using a single timing generator for the output and a demand based input stream with a throttling mechanism. The present invention, however, is not intended to be limited to any particular control technique. One embodiment of the present invention uses an output clock and a demand based input stream capable of supplying data at four times the rate of the output clock. As will be seen below, there is a maximum scaling factor (SF) equal to the maximum speed of the input divided by the output clock speed. ${\mathrm{SF}}_{\max }=\frac{\mathrm{Maximum}\mathrm{Input}\mathrm{Speed}}{\mathrm{Output}\mathrm{Clock}\mathrm{Speed}}$

[0053] The clock speed selected for a particular application would preferably be based on the range of anticipated scaling.

[0054] Timing diagrams for various scaling ratios are shown in FIGS. 4A-4C. In each, the input data 80 must be fast enough to “keep up with” the output data 82. Those of ordinary skill in the art will readily recognize that stalling of the input data 80 is one technique that could be used to keep the input data 80 and output date 82 synchronized. Each block of the output data 82 indicates a single line is sent to output buffer 68. Each block of the input data 80 indicates a single line of data is read, a “w” indicates a write to the output buffer.

[0055] Overscan compensation and scaling is somewhat similar to noninterlaced to interlaced data conversion. However, unlike noninterlaced to interlaced conversions, there is seldom a 2:1 ratio between the input and output data.

[0056] Overscan compensation can be handled in many ways. TV formats typically crop a fixed number of horizontal lines of image data. While this technique is easy to implement, it may not produce satisfactory displays of computer generated graphics. At the other extreme, using an n-tap filter, with n equal to the number of lines in the original image, for overscan compensation is costly. For example, a 1280×1024 resolution computer image would require a 1024-tap filter. The processing required for such a filter would be extremely difficult to accomplish in real time for a reasonable price.

[0057] One embodiment of the present invention uses a 5-tap filter for the combined flicker and overscan compensation filter. Other size filters could be used, and the present invention is not intended to be limited to any particular combined filter.

[0058] Those of ordinary skill in the art will readily recognize that vertically scaling a computer image is conceptually very similar to vertical overscan compensation. In both operations, X lines of input are converting to Y lines of output. The principal difference is that ratio of X to Y in scaling may well exceed the 1.10 to 1.20 range typical in overscan compensation.

[0059] Because scaling factors (SF) are not always integers, the concept of a “phase” is used to filter the input data and create output data. The phase is used to track a fractional position while mapping the input lines to the output lines. One embodiment of the present invention uses 16 phases, represented as 4 bits, when scaling. That is, non-integer mapping between input and output lines has an effective resolution of {fraction (1/16)} the distance between input lines. Filter coefficients C1 through C5 may change depending on the particular input line number. With 16 phases, there are 16 sets of filter coefficients. With a 5-tap filter, 5×16 phase gives a total of 80 coefficients. Because of symmetry, only 9 sets of coefficients are unique and are stored. The present invention is not intended to be limited to any particular number of phases, or sets of filter coefficients.

[0060] One embodiment of the present invention uses a digital differential analyzer (DDA) to determine which lines of input to use in the filter function for a particular line of output. The DDA is a counter that increments for every output line. The DDA indicates which input lines and filter phase to use. The DDA makes the following calculation: $\mathrm{Input}\mathrm{Pos}=\mathrm{Init}\mathrm{Phase}+\sum _{i=1}^n\mathrm{SF}$

[0061] Where InputPos is the input line position, with the integer portion representing the input line number and the fractional portion the filter phase. InitPhase is the initial phase. SF is the scale factor, the number of input lines divided by the number of output lines in a field. The variable n represents the current output line being produced. Odd and even output fields have differing initial phases. For even numbered output fields, the initial phase is adjusted by adding 0.5 times SF to the initial phase for odd output fields.

[0062] FIG. 5 depicts a mapping from a noninterlaced input frame 84 to two interlaced output frames 86 and 88 using a 5-tap filter.

[0063] The first output frame, or the “odd field”, is shown with solid lines 86. The even field is shown as broken lines 88.

[0064] In mapping from the input frame space to the output frame space, the distance between lines is scaled by SF/2. In the input frame, the initial line can be thought of being offset from the top of the frame by ½ line. In the output frame, this distance from the initial line to the top of the frame is scaled, and becomes ½ * SF/2=SF/4. If the first input line is at location 0, the top of the image starts at −0.5. So the initial output line is at SF/4−0.5. This is the initial phase for an odd output field. The initial phase for an even output field is (SF/4−0.5)+0.5 * SF, which is equal to 3 * SF/4−0.5.

[0065] Processing the input image with a 5-tap filter requires some adjustment at the top and bottom lines of the image. In accordance with one embodiment of the present invention, the top line is effectively duplicated and the filter coefficients are applied to the duplicate lines. That is, (c₁+c₂+c₃) is multiplied by I(1). Other “missing lines” are processed in a similar fashion. The present invention is not, however, intended to be limited to any particular method of filtering the boundaries of an image.

[0066] As will be readily recognized by those of ordinary skill in the art, the combined filter must be separately applied to each component of a video image, such as the three components of a color image. The present invention, however, may be used with any colorspace format, such as RGB or YUV, without modification.

[0067] Those of ordinary skill in the art will readily recognize that faster clock speeds will allow more “hardware efficient” embodiments of the present invention. For example, a single adder and a single multiplier could process the data flow of the embodiment of the present invention shown in FIG. 3, if the clock speed were fast enough. The present invention is not, however, intended to be limited to any particular clock speed or processor configuration.

[0068] While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art that many more modifications than mentioned above are possible without departing from the inventive concepts herein after a review of this disclosure. The invention, therefore, is not to be restricted except in the spirit of the appended claims.