US 5,019,904 AGrant
Scan Converter With Adaptive Vertical Filter for Single Bit Computer Graphics Systems
Issue Date:1991-05-28
•20 Claims
•2 Drawing Sheets
Abstract
A television scan conversion method receives and stores incoming pixel bits are stored in a pixel memory array at a first scan rate. Vertical columns of adjacent pixel bits of plural scan lines from the pixel memory array are read out at a second scan rate. A filter coefficient is generated by detecting a bit pattern located in each vertical column of pixel bits retrieved from the pixel memory array. Delay matched predetermined adjacent groups of pixel bits in each vertical column are adaptively low pass filtered in response to the filter coefficient so as to minimize video flicker artifacts in a resultant stream of interpolation pixels in accordance with the bit patterns detected by the pattern recognition filter coefficient generator. An interpolation coefficient is generated for each interpolation pixel, and plural-bit interpolation pixels are put out as a stream at the second scan rate.
Metadata
Inventor
- Jack J. Campbell
Application Information
Application Number:US 4453697
Filing Date:1989-12-04
Priority Date:1989-12-04
Art Unit:262
Classifications
IPC:
H04N 701H04N 704H04N 1120H04N 1106
Field of Search:
358340382364140;141;11;1272854;47521
Patent Drawings (2 sheets)
Description
Field of the Invention
The present invention relates to video signal processing methods and equipment. More particularly, the present invention relates to scan conversion with adaptive vertical filtering for flicker reduction for use with single bit per pixel computer graphics systems.
Background of the Invention
Single bit per pixel graphic image systems, such as those employed by popular personal computers such as the Apple MAC+and MAC SE (tm), are very limited in the types of pictures that can be displayed on the display device, usually a cathode ray tube. One of the techniques that one bit-per-pixel based images may be made to appear to have a gray scale is by "half toning". By half toning is meant the technique of controlling the arrangement and number of black (or white) pixels so as to create the appearance of shading. Another technique is "patterning". By patterning is meant the process of creating a vertical and/or horizontal small area pattern of pixels, and then repeating this stored pattern over and over again in both dimensions.
Computer graphics systems, particularly those of the single-bit-per-pixel variety, typically employ a progressive scan format and typically have a number of scan lines which does not correlate to the number of scan lines of the conventional NTSC interlaced scan format of the commercial broadcast television signal standard. While computer graphics systems typically come equipped with some display device, such as a nine-inch cathode ray tube, many emerging computer graphics applications are facilitated by or actually require scan conversion so that the computer graphics image may be displayed on conventional NTSC interlaced scan display devices.
When a one-bit-per-pixel graphic image is scan-converted into another scan rate, half tones and patterns can be very difficult to represent due to sampling limitations (i.e., Nyquist limit problems). One major problem arising from such scan conversion is flicker which is apparent in the scan-converted resultant image display. Flicker is a particularly severe problem when progressively scanned computer graphics images are converted into an interlaced scan format for display on conventional television signal format image display devices. If the energy at a location in the resultant scan-converted interlaced video image is unequal from field to field, flicker results, the intensity of which being dependent upon the energy differential from field to field.
While scan converters are known in the prior art, one prior solution to the flicker problem is simple vertical low pass filtering to eliminate or sharply curb the appearance of flicker. The apparent drawback of vertical low pass filtering is loss of vertical resolution in the scan converted display. Thus, a hitherto unsolved need has arisen for a scan converter which includes adaptive vertical low pass filtering to remove flicker while optimizing apparent resolution of the scan-converted television image.
Summary of the Invention With Objects
A general object of the present invention is to provide scan conversion methods and apparatus with adaptive vertical filtering for flicker reduction for use with single bit per pixel computer graphics systems in a manner which overcomes limitations and drawbacks of the prior art.
Accordingly, a television scan converter is provided for converting video generated by single bit per pixel computer graphics systems at a first scan rate into analog video at a second scan rate which is different than the first rate. The scan converter includes a pulse timing generator responsive to horizontal, vertical and pixel clock frequencies at the first scan rate; and to horizontal, vertical and pixel clock frequencies at the second scan rate, for generating clocking signals. A pixel memory array stores incoming pixel bits and retrieves vertical columns of pixel bits of plural scan lines at the first scan rate for each interpolation pixel to be generated. A memory address controller is responsive to the pulse timing generator, and it generates and puts out pixel bit storage and retrieval addresses to the pixel memory array. A pattern recognition filter coefficient generator generates a filter coefficient based upon detection of the incoming vertical pixel pattern. An adaptive vertical low pass filter structure, controlled by the filter coefficient, filters the incoming vertical pixel pattern. An interpolator interpolates the output from the vertical low pass filter structure and puts out an interpolated pixel at the second scan rate so as to minimize video flicker in the resultant interpolation pixels in accordance with the patterns recognized by the pattern recognition filter coefficient generator. An interpolation coefficient generator responsive to the pulse timing generator generates an interpolation coefficient C for each interpolation pixel for controlling operation of the interpolator. A digital to analog converter may be provided to convert the plural bit interpolation pixels into outgoing analog horizontal scan lines at the second scan rate.
In one aspect of the present invention, the first scan rate is 370 progressive scan lines per frame at approximately 60 Hz frame rate, and the second scan rate is 525 scan lines interlaced per frame at an approximate 30 Hz frame rate.
In another aspect of the present invention, the pattern recognition filter coefficient generator, the adaptive vertical low pass filter structure and the interpolator are preferably implemented in a programmable memory array.
In one more aspect of the present invention, the plural predetermined vertical pixel patterns include alternating black and white pixels (checkerboard pattern), single pixel (horizontal line), dual pixel (horizontal bar) and pixel step or window.
In still a further aspect of the present invention, the pixel memory reads at least six vertical pixel bits b[0], b[1], b[2], b[3], b[4], b[5] for each outgoing interpolation pixel i at the second scan rate, and the adaptive vertical low pass filter structure provides two outputs, R and S, to the interpolator in accordance with the following: ##EQU1##
In yet another aspect of the present invention, the interpolator receives the two filter outputs of the pattern recognition filter and puts out the interpolation pixel i at the second scan rate, in accordance with the following:
where the coefficient C is generated by the interpolation coefficient generator equals the distance between the position of pixel bit b[3] scan line and the position of interpolation pixel i, and lies in a range between zero and *** *** unity.
These and other objects, aspects, advantages and features of the present invention will become more apparent to those skilled in the art upon consideration of the following detailed description of a preferred embodiment, presented in conjunction with the accompanying drawings.
Detailed Description of a Preferred Embodiment
In the Drawings:
FIGS. 1A, 1B, 1C, 1D, and 1E illustrate four examples of one-bit-per-pixel graphics patterns which give rise to severe flicker artifacts when subjected to uncompensated scan conversion.
FIG. 2 illustrates a leftmost column of pixels at a first incoming progressive horizontal scan rate and a corresponding rightmost column of pixels at a second outgoing, interlaced scan rate which is approximately 1.4 times the scan rate of the incoming pixels.
FIG. 3 is a block diagram of a scan converter in accordance with the principles of the present invention.
Detailed Description of a Preferred Embodiment
FIGS. 1A, 1B, 1C, 1D and 1E set forth five specific instances of pixel patterns encountered within one specific personal computer type, Apple MAC +or MAC SE (tm), which tend to give rise to varying levels of flicker following scan conversion to an interlaced conventional NTSC signal format. In this particular personal computer graphics architecture, each picture element or "pixel" is accorded one bit, i.e. the pixel is either fully illuminated or it is completely dark. Its gray scale can therefore be completely characterized by a single binary bit, i.e. on or off.
In this particular computer graphics architecture, there are e.g. 370 scan lines which are generated progressively. FIGS. 1A-1E illustrate scan segments of six adjacent scan lines with three pixels per line shown. FIG. 1A illustrates a checkerboard pattern of pixels which is used to generate the appearance of a mid-range gray scale. When this pattern is converted to NTSC, a very objectionable visual flicker and vertical beat pattern accompanies this particular pattern. FIG. 1B illustrates a two-pixel horizontal bar. This pattern also is accompanied by very objectionable flicker when converted to NTSC interlaced scan format.
FIG. 1C illustrates a single pixel horizontal line. (It could also correspond to a diagonal line image forming some acute angle with the scan line locii). It has been observed by the inventor that scan conversion of a single pixel horizontal line results in perceptibly less flicker than results from the FIG. 1B two-pixel horizontal bar. Thus, less vertical filtering is needed for the FIG. 1C line pattern than is needed for the FIG. 1B horizontal bar. The FIG. 1D step function denoting a step or window also is characterized by less flicker and requires less vertical filtering.
FIG. 1E illustrates an alternating light and dark scan line pattern which presents the greatest flicker, and which requires the greatest filtering. The amount of adaptive vertical low pass filtering required to minimize unwanted flickering artifacts in the scan converted, interlaced video image may be determined as a general rule by the following general statement: the number of vertical level impulses within the six adjacent vertical pixels is directly related to the amount of vertical low pass filtering required to minimize flicker beat patterns and artifacts in the resultant scan converted picture image. By "vertical level impulse" is meant either a black to white to black vertical sequence, or a white to black to white vertical sequence of pixels.
For example, there are four vertical impulses in the pattern depicted in FIG. 1E. A first impulse is found in b[0] (white) to b[1] (black) to b[2] (white). A second impulse is found in b[1] (black) to b[2] (white) to b[3] (black). A third impulse is found in b[2] (white) to b[3] (black) to b[4] (white) And, a fourth impulse is found in b[3] (black) to b[4] (white) to b[5] (black). This situation calls for the most vertical low pass filtering. Three vertical impulses requires somewhat less vertical low pass filtering. Two vertical impulses require still less vertical low pass filtering. One vertical impulse requires the least amount of vertical low pass filtering, and no vertical impulse requires no vertical low pass filtering at all.
In accordance with the principles of the present invention, one presently preferred embodiment of which is depicted in FIG. 3, a pixel pattern recognition filter coefficient generator 17 is employed within a scan converter 10 in order to determine the nature of vertical pixel patterns and to generate a filter coefficient FC in order to control the amount of vertical low pass filtering applied to the particular pattern undergoing active scan conversion to the second scan rate.
With reference to FIG. 2, the left vertical column corresponds to pixels at the incoming scan rate Fl, at successive vertical locations displaced by successive scan lines. Pixels b[0], b[1], b[2], b[3], b[4] and b[5] are of particular interest The pixels are the product of progressive scanning at the F1 scan rate.
The right vertical column depicts an interpolation pixel i at a second scan rate F2. The second scan rate follows an interleave format, such as the conventional NTSC format, nominally 525 lines, and actually 485 video information scan lines. The pixels shown in the right column are spaced apart by one pixel distance, thereby denoting the interleaved scan format. It is apparent that the interpolation pixel i is most closely related in space to incoming pixels b[2] and b[3]. However, it is also apparent that interpolation pixel i is out of phase with incoming pixels b[2] and b[3].
In accordance with an aspect of the invention, the location of the interpolated pixel i is denoted C. In the scan converter 10, described hereinafter in conjunction with FIG. 3, the location C is a value in a range lying from zero to 15 (2.sup.4 or a 4-bit value). The location C of the interpolation pixel i shifts relative to adjacent incoming pixels at a phase shift or beat pattern between the incoming and outgoing scan frequencies. As the pixel i moves toward the incoming pixel b[3]and away from the incoming pixel b[2], for example, the gray level of the pixel i will increase from dark to light in the example shown in FIG. 2. It is to be understood that the scan converter 10 puts out scan converted pixels which have gray scales in a predetermined range greater than the incoming binary level (black or white) pixels.
With reference to FIG. 3, a scan converter 10 in accordance with the principles of the present invention includes a single bit per pixel input line 12 for incoming computer graphics video in which each successive pixel is accorded a single bit gray scale (black or white).
The incoming pixels are recorded in a pixel memory array 13 which is sized to contain a frame of lines of incoming video. The memory array 13 is written at the incoming progressive scan rate (SR-1) and is read out at the outgoing interleaved scan rate (SR-2). A pulse timing generator 14 receives horizontal, vertical and pixel clock signals at the incoming scan rate (SR-1) and the same signals at the outgoing rate (SR-2) and generates suitable timing signals. These timing signals are applied to a memory address controller 18 which controls addressing of the memory array 14 in a manner to be described. The pulse timing generator 14 also addresses an output line number lookup table array 16 for interpolation coefficient C. The memory array 16 contains a lookup table for the pixel location interpolation coefficient C which is determined by the output scan line number.
The pixel memory 13 provides a multi-bit output to a pattern recognition filter coefficient generator 17 which generates a four bit vertical low pass filter coefficient FC from the incoming vertical pixel pattern (b[0] through b[5]). The generator 17 functions to recognize sixty four possible pixel patterns within the six bits, such as the patterns depicted in FIGS. 1A-1E.
In the presently preferred embodiment, six bits are put out at a time from the pixel memory 13, namely bits b[0] through b[5]. Conceptually, the six bits being put out at a time for the interpolation of the pixel i correspond to the six incoming pixels b[0] through b[5] as depicted in the left vertical column of FIG. 2. Each vertical pixel pattern is thereupon evaluated for its a priorily known tendency to cause flicker in accordance with the general proposition stated above and in accordance with several special cases for which the filtering level is set empirically. The amount of vertical flicker reduction low pass filtering is controlled for each pattern by e.g. a four bit value FC.
Two delay matches 18 and 19 are provided to match the pixel transit delay caused by the generator 17. The delay 18 delays the incoming pixel bits b[1] through b[3] bits by the predetermined delay amount, and the delay 19 delays the incoming pixel bits b[2] through b[4] by the predetermined delay amounts.
Two adaptive vertical low pass filters 20 and 21 provide vertical low pass filtering which is controlled by the filter coefficient FC. The filter 20 filters the bits b[1] through b[3] from the delay 18, whereas the filter 21 filters the bits b[2] through b[4] from the delay 19. The outputs from the filters 20 and 21 are denoted R and S, and are each four bit values. The following formulas for R and S establish the structure of the transversal low pass filters 20 and 21: ##EQU2##
Notice that when FC equals zero, R is equal to b[2] and S is equal to b[3]; and that when FC is equal to unity, R is equal to 1/2 b[2]+1/4 b[1]+1/4 b[3]; and S is equal to 1/2b[3]+1/4 b[2]+1/4 b[4]. In the latter case the filters 20 and 21 are each a three tap transversal filter with tap coefficients of 1/2, 1/4 and 1/4.
The outputs R and S respectively enter multipliers 22 and 23. The multiplier 22 multiplies R by the interpolation coefficient C to produce a four bit product; and, the multiplier 23 multiplies S by the complementary interpolation coefficient BAR C to produce a four bit product. The interpolation coefficient C is delivered directly to the multiplier 22 from the look-up table 16 over a four bit line 31, whereas the complementary interpolation coefficient BAR C is generated by an inversion process 33 and then delivered to the multiplier 23. The products from the multipliers 22 and 23 are added together in a summing junction 24 to provide e.g. a multi-bit interpolation pixel i. Preferably, sixteen discrete levels, or more, are provided for the gray level range for each interpolation pixel i.
C equals the distance between the position of the pixel bit b[3] scan line and the position of the interpolation pixel i, and lies in a range between zero and unity. BAR C is the complement of C and also lies in a range between zero and unity. The interpolation pixel, i, is given by the following formula:
The pixel i is put out at the second scan rate SR-2, and may be converted into an analog video image stream by a digital to analog converter 26. An output 28 from the converter 26 provides the analog data stream in e.g. the conventional interlaced NTSC video signal format, for example.
Each outgoing pixel has a gray level on a gray scale from zero to fifteen, for example. The interpolation process provides suitable vertical filtering to minimize flicker, depending upon the presence or absence of flicker causing patterns in the incoming video stream. If the vertical pixels adjacent to the interpolation pixel i are all dark, or are all light, then the pixel i will be full dark or full light within the available gray scale range. If vertical patterns and vertical transitions are present at the vicinity of the interpolation pixel i, vertical filtering will be applied in an amount related to the particular pattern recognized. By vertical filtering is meant an adjustment of gray scale of the interpolation pixel i in a manner and to an extent required to minimize flicker artifacts in the interpolated video stream.
Preferably, the pattern recognition filter coefficient generator 17, delay matches 18 and 19, adaptive filters 20 and 21, multipliers 22 and 23, and summing junction 24 are contained within a single memory array 25. The lowest order incoming six bits 0-5 correspond to b[0] through b[5] on the line 29, while the four next incoming bits 6-9 correspond to C on the line 31. In the preferred PROM implementation, BAR C is generated from C within the PROM 25, so that the PROM has 10 bits in: 6 pixel bits and 4 C values. The following table in hexadecimal sets forth the bit values for the array 25, with each address corresponding to a sixteen bit outgoing pixel i, which is based upon the incoming bit pattern. Four adjacent rows (e.g. 00000-0003F) set forth 64 hexadecimal (base 16) characters which correspond to sixty four discrete, sixteen-gray-level pixel values i wherein C equals zero, for example.
The addresses for each of the sixteen C groups, each being of 64 pixel values, are set forth in the program listing as follows:
Here follows the program listing for the PROM 25 set forth in hexadecimal format: ##SPC1##
The following computer program, written in the C language, may be used to generate the value table set forth above for the array 25: ##SPC2##
Having thus described a presently preferred embodiment of the present invention, it will now be appreciated that the objects of the invention have been fully achieved, and it will be understood by those skilled in the art that many changes in construction and widely varying embodiments, techniques and applications of the invention will suggest themselves without departure from the spirit and scope of the present invention. The disclosures and the description given hereinbefore are therefore purely illustrative and are not intended to be in any sense limiting.
Claims
I claim:
1. A television scan converter for converting video generated by single pixel bit computer graphics systems at a first scan rate into analog video at a second scan rate which is different than the first rate, the converter comprising: clocking means responsive to horizontal, vertical and pixel clock frequencies at the first scan rate and horizontal, vertical and pixel clock frequencies at the second scan rate for generating clocking signals, pixel memory array means for storing incoming pixel bits at the first scan rate and for retrieving vertical columns of predetermined numbers of vertically adjacent pixel bits of plural scan lines at the second scan rate, memory address controller means responsive to the clocking means for generating and putting out pixel bit storage and retrieval addresses to the pixel memory array means, pattern recognition filter coefficient generator means for generating a filter coefficient by detecting a bit pattern of each said vertical column of pixel bits read out from the pixel memory array means, adaptive vertical low pass filter means connected to receive delay matched predetermined adjacent groups of pixel bits of said vertical column for adaptively low pass filtering the predetermined adjacent groups in response to the filter coefficient, so as to minimize video flicker artifacts in resultant interpolation pixels at the second scan rate in accordance with the bit patterns detected by the pattern recognition filter coefficient generator means, interpolator means connected to the adaptive vertical low pass filter means and responsive to an interpolation coefficient C, for generating and putting out as a stream the interpolation pixels at the second scan rate, and interpolation coefficient generator means responsive to the clocking means for generating the interpolation coefficient C for each interpolation pixel for controlling operation of the interpolator means.
2. The television scan converter set forth in claim 1 further comprising digital to analog converter means for converting the plural bit interpolation pixels put out by the interpolator means into an analog data stream comprising horizontal scan lines for display at the second scan rate.
3. The television scan converter set forth in claim 1 wherein the first scan rate is 370 progressive scan lines per frame at an approximate 60 Hz frame rate, and the second scan rate is 525 scan lines interlaced per frame at an approximate 30 Hz frame rate.
4. The television scan converter set forth in claim 1 wherein the pattern recognition filter coefficient generator means, the adaptive vertical low pass filter means and the interpolator means are implemented as a programmed read only memory array.
5. The television scan converter set forth in claim 1 wherein the pattern recognition filter coefficient generator means detects plural predetermined vertical pixel patterns including alternating black and white pixels, single pixel (horizontal line), dual pixel (horizontal bar) and pixel step or window from said bit pattern for each said vertical column read out from the pixel memory array means.
6. The television scan converter set forth in claim 1 wherein the pixel memory array means stores at least six vertical pixel bits b[0], b[1], b[2], b[3], b[4] and b[5] for each interpolation pixel i, and wherein the adaptive vertical low pass filter means provides two filter outputs R and S in accordance with the following relationship: ##EQU3##
7. The television scan converter set forth in claim 6 wherein the interpolator means receives the two filter outputs R and S and puts out the interpolation pixel i, in accordance with the following: wherein C and BAR C lie in a range between zero and unity, and wherein BAR C is the complement of C.
8. The television scan converter set forth in claim 7 wherein the pattern recognition filter coefficient generator means generates the filter coefficient as a value lying in a range between zero and fifteen.
9. The television scan converter set forth in claim 6 wherein the adaptive vertical low pass filter means comprises two adaptive transversal low pass filters, a first filter connected to receive from the pixel memory array means and to adaptively filter pixel bits b[1], b[2] and b[3] and put out R for each interpolation pixel i to be generated; and, a second filter connected to receive from the pixel memory array means and to adaptively filter pixel bits b[2], b[3] and b[4] and put out S for each interpolation pixel i to be generated.
10. The television scan converter set forth in claim 9 further comprising a delay match in each path between the pixel memory array means and the first and second filters, in order to match the delay incurred in the pattern recognition filter coefficient generator means.
11. The television scan converter set forth in claim 9 wherein the interpolator means comprises two multipliers, a first multiplier which receives the output R and a second multiplier which receives the output S, wherein the first multiplier multiplies R by the interpolation coefficient C, wherein the second multiplier multiplies S a complement interpolation coefficient BAR C, and wherein C and BAR C lie in a range between zero and unity, and further comprising summing means for summing outputs from the first and second multipliers.
12. The television scan converter set forth in claim 1 wherein the interpolator means generates and puts out each interpolation pixel having a plural-bit gray scale.
13. A method for converting video generated by single pixel bit computer graphics systems at a first scan rate into analog video at a second scan rate which is different than the first rate, the method comprising the steps of: generating clocking signals responsive to horizontal, vertical and pixel clock frequencies at the first scan rate and horizontal, vertical and pixel clock frequencies at the second scan rate, storing incoming pixel bits in a pixel memory array means at the first scan rate and retrieving vertical columns of predetermined numbers of vertically adjacent pixel bits of plural scan lines from the pixel memory array means at the second scan rate, generating and putting out pixel bit storage and retrieval addresses to the pixel memory array means in order to carry out the said storing and retrieving steps, generating a filter coefficient by detecting a bit pattern of each said vertical column of pixel bits retrieved from the pixel memory array means, adaptively low pass filtering delay matched predetermined adjacent groups of pixel bits in said vertical column in response to the filter coefficient so as to minimize video flicker artifacts in a resultant stream of interpolation pixels i in accordance with the bit patterns detected by the pattern recognition filter coefficient generator means, interpolating a scan converted pixel i by generating and putting out as a stream the interpolation pixels at the second scan rate in response to an interpolation coefficient C, and generating the interpolation coefficient C for each interpolation pixel for controlling the operation of the interpolation step.
14. The scan converting method set forth in claim 13 comprising the further step of converting the stream of interpolation pixels put out by the interpolation step into an analog data stream comprising horizontal scan lines for display at the second scan rate.
15. The scan converting method as set forth in claim 13 wherein the step of interpolating a scan converted pixel i by generating and putting out as a stream the interpolation pixels at the second scan rate includes the step of generating and putting out each interpolation pixel with a plural-bit gray scale.
16. The scan converting method set forth in claim 13 wherein the first scan rate is 370 progressive scan lines per frame at an approximate 60 Hz frame rate, and the second scan rate is 525 scan lines interlaced per frame at an approximate 30 Hz frame rate.
17. The scan converting method set forth in claim 13 wherein the storing step stores at least six vertical pixel bits b[0], b[1], b[2], b[3], b[4] and b[5] for each interpolation pixel i, and wherein the adaptive low pass filtering step results in two filter outputs R and S in accordance with the following relationship: ##EQU4##
18. The scan converting method set forth in claim 17 wherein the interpolating step receives the two filter outputs R and S and puts out the interpolation pixel i, in accordance with the following: wherein C and BAR C lie in a range between zero and unity, and wherein BAR C is the complement of C.
19. The scan converting method set forth in claim 13 wherein the generating a filter coefficient step comprises the step of generating the filter coefficient as a value lying in a range between zero and fifteen.
20. A method for controlling the amount of vertical low pass filtering within a scan converter for converting video generated by single pixel bit computer graphics systems at a first scan rate into analog video at a second scan rate comprising the steps of reading a bit pattern of a vertical column of pixel bits retrieved from a pixel memory array means, detecting a number of vertical impulses occurring in the read bit pattern and establishing the magnitude of a filter coefficient for controlling the amount of vertical low pass filtering in relation to the number of detected vertical impulses occurring within the vertical bit pattern.