Non-linear video sharpening filter

[0002] The present invention relates to filtering video signals to sharpen their appearance when displayed.

[0003] Various techniques have been proposed to sharpen the appearance of video when displayed. The need for an effective and robust sharpening filter will be particularly apparent as higher definition video begins to become a household standard and users wish to view older, lower definition recordings on higher definition monitors.

[0004] One known technique for enhancing the sharpness of video is to apply a high-frequency boosting spatial filter to the video signals to thus enhance the edges in the video. However, this technique has proven less than satisfactory for the reason that linear filters having a high-boost characteristic also exhibit ringing in their step response. This ringing will manifest as regions of luminance or color variation near to the edges of an object when placed against a background of substantially different luminance or color.

[0005] Various nonlinear filters have also been proposed for video sharpening, which for example compare the luminance values within a region and determine statistical properties Such as the minimum, maximum, average and median luminance values, from which a new value for pixels within the region can be derived. However, despite the efforts that have been applied to developing a nonlinear sharpening filter, known filters continue to display unwanted artifacts that make those filters less than completely desirable for all applications.

[0006] The present invention provides a nonlinear filter which overcomes these difficulties, and provides an output of increased sharpness with reduced artifacts as compared to prior art filters.

[0007] In one aspect, a method of filtering according to the invention proceeds by identifying a “pivot” value at a pixel based on the value of pixels neighboring that pixel. Then, a new value for the pixel is computed by adding to the pivot value, an amount based on the difference between the original pixel value and the pivot value.

[0008] In the specific embodiment described below, the pixel values are luminance values. The pivot value is computed as the average of the original values for a number, e.g., 2ⁿ, neighboring pixels, where n is, for example, equal to 3. Alternatively, the pivot value may be computed as the average of the maximum and minimum original pixel values among the 2ⁿneighboring pixels.

[0009] To compute the new value for a pixel, the difference between the original pixel value and the pivot value is multiplied by a factor k, and then added to the pivot value. For computational simplicity, the factor k is selected to be a power of two. Filtering for k=2, k=4 and k=16 are illustrated.

[0010] The new value may be limited to the maximum and minimum original pixel values among the 2ⁿoriginal pixel values.

[0011] The invention also features filtering hardware for carrying out the filtering methods described above.

[0012] The above and other objects and advantages of the present invention shall be made apparent from the accompanying drawings and the description thereof.

[0013] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and, together with a general description of the invention given above, and the detailed description of the embodiments given below, serve to explain the principles of the invention.

[0014] FIG. 1 is an illustration of a custom hardware embodiment for performing filtering in accordance with principles of the present invention;

[0015] FIG. 2 is an illustration of a hardware embodiment of a 2ⁿpixel sorter and shift register for facilitating filtering in accordance with principles of the present invention;

[0016] FIGS. 3A, 3B and 3C are illustrations of pixel luminance value inputs and outputs exemplifying the filtering achieved with the present invention using the respective filtering parameter values k=2, k=4 and k=8.

[0017] In accordance with principles of the present invention, video filtering is performed on pixel luminance values by computing, for a set of adjacent pixels, various features such as the maximum luminance value and minimum luminance value. In the exemplary embodiment described below, a set of 2ⁿhorizontally adjacent pixels are analyzed to determine maximum and minimum values and for other calculations, so that filtering is performed in one dimension horizontally. Principles of the present invention, however, can also be applied to filtering in the vertical dimension, by applying the described techniques to a set of 2ⁿvertically adjacent pixels. Filtering can also be done in accordance with the present invention, in both the vertical and horizontal directions. Furthermore, principles of the present invention could also be applied to sharpening of other video parameters than luminance, for example, color values could be processed.

[0018] Based on an input set of 2ⁿadjacent pixels, in accordance with principles of the present invention, a maximum luminance value and minimum luminance value for the pixels in the set is determined. Having these values, the intensity of an edge in the video, i.e., a transition from a region of low luminance to high luminance or vice-versa, can be accentuated.

[0019] A simplified embodiment of a nonlinear filter in accordance with the present invention, further computes a median and average value for the pixels in the input set. Using the median and average values, an output for a pixel is then computed according to the formula

[0020] Output=IF(Average>Median) THEN Minimum ELSE Maximum, (1)

[0021] i.e., the output value for a pixel is set equal to the minimum value when the average of the 2ⁿneighboring pixels is greater than the median (indicating that the current pixel is before the middle of a rising edge or after the middle of a falling edge), and set equal to the maximum value when the average of the 2ⁿneighboring pixels is less than or equal to the median (indicating that the current pixel is after the middle of a rising edge or before the middle of a falling edge).

[0022] This filter has the desired effect of enhancing edges, however, not without some noticeable artifact, in particular, loss of detail in relatively low-contrast areas of the image.

[0023] To reduce this loss of detail in low-contrast areas, a second embodiment of a nonlinear filter in accordance with the present invention, computes an edge strength value indicative of whether there is a sharp edge within the input set of 2ⁿpixels, so that in areas with low edge strength, the modification of the pixel value from its original value is minimized. The edge strength value can be computed from the difference between median and average values, since the median and average values will only substantially deviate when there is a substantial change in the luminance values within the input set of 2ⁿpixels. This difference is normalized by dividing by the gap between maximum and minimum values in the input set of 2ⁿpixels. Thus, in this second embodiment, the strength value is computed at a pixel according to the formula

[0024] Strength=|Average−Median|/(Maximum−Minimum). (2)

[0025] Then, an output for a pixel is then computed according to the formula

[0026] Output=IF(Average>Median)

[0027] THEN Strength×Minimum+(1−Strength)×Input

[0028] ELSE Strength×Maximum+(1−Strength)×Input. (3)

[0029] This second embodiment of a filter according to the present invention exhibits good enhancement of edges with few noticeable artifacts. However, this embodiment has a disadvantage that computation of a pixel output value requires a floating point divide (to compute the Strength value) as well as two floating point multiplies (to multiply the Strength value by the Minimum/Maximum and by the Input value). This makes the filter computationally intensive and also expensive in terms of hardware required for implementation in custom circuitry.

[0030] To alleviate these disadvantages, in accordance with a third embodiment of a nonlinear filter in accordance with the present invention, nonlinear filtering is performed without requiring floating point multiplication or division operations. In this embodiment, a pivot value is computed for each input pixel. The pivot value is representative of whether the pixel is “above” or “below” any identifiable edge in the neighboring pixels. Once a pivot value is determined, then the output value for a pixel can be computed according to the formula

[0031] Output=K×(Input−Pivot)+Pivot. (4)

[0032] The resulting Output value is then limited to the Maximum and Minimum input values to prevent overshoot or “ringing” artifacts. K is a filtering parameter and is adjustable between, for example, values of 1 and 20. It will be noted that the K value can be chosen to be an integer power of two, i.e., K=2^x, where x is a positive integer; doing so simplifies the product K×(Input−Pivot) to an x-bit binary shift to the left. Thus, an Output value can be computed from an input value without any floating point divides or multiplications.

[0033] The pivot value can be computed, for example, as the average of a given number of neighboring pixel values. If the given number of neighboring pixel values is chosen to be an integer power of two, i.e., 2ⁿpixels, then the pivot value can be computed without a floating point divide, by simply adding the 2ⁿpixel values and shifting the binary result to the right by n bits. Alternatively, the pivot value can be computed as the average of the maximum and minimum values of the neighboring pixels. This pivot value can also be computed without a floating point divide, by simply adding the maximum and minimum values and shifting the binary result one bit to the right.

[0034] Referring now to FIG. 1, an explanation can be provided for one hardware implementation of a one-dimensional, horizontal pixel filter 10 in accordance with this third embodiment of the present invention. Filter 10 receives input pixel values on bus 12, synchronized to a pixel synchronization clock signal on line 14. Filter 10 produces output pixel values on bus 16. Filter 10 is pipelined and has a latency of 2ⁿ⁻¹periods of the pixel synchronization clock signal on bus 14, so that an output pixel value for a given location in a scan line is produced on bus 16 2ⁿ⁻¹pixel clock periods after an input value for the same location is received on bus 12.

[0035] Pixel values received from bus 12, and the pixel synchronization clock signal on line 14 are delivered to a 2ⁿpixel sorter and shift register circuit 20. Circuit 20 responds to these inputs by producing outputs on busses 22, 24, 26 and 28. Circuit 20 produces a Maximum signal output on bus 22 which corresponds to the largest pixel value of the 2ⁿpixel values that were most recently received by circuit 20. Similarly, circuit 20 produces a Minimum signal output on bus 24 which corresponds to the smallest pixel value of the 2ⁿpixel values that were most recently received by circuit 20. Circuit 20 also produces a 2ⁿ⁻¹delayed signal on bus 26 which corresponds to the pixel input value that was received 2ⁿ⁻¹periods (of the pixel synchronization clock) earlier. Finally, circuit 20 produces a 2ⁿdelayed signal on bus 28 which corresponds to the pixel input value that was received 2ⁿperiods (of the pixel synchronization clock) earlier. Details of the internal operations of circuit 20 can be understood by reference to FIG. 2, discussed below.

[0036] The Maximum and Minimum signal outputs of busses 22 and 24 from circuit 20 are fed to an adder 30 which adds these signals together. The output of adder 30 is fed to a 1-bit right shift circuit 32, which has the effect of dividing the sum of the Minimum and Maximum values by two, without rounding, to produce a result on line 34 representative of the average of those Minimum and Maximum values, which is the first alternative pivot value that can be used by filter 20, as discussed above.

[0037] To compute the second alternative pivot value discussed above, an accumulator circuit 35 is used. Accumulator circuit includes a register 36 for storing a current accumulated value for 2ⁿpreviously received pixels. To compute a new accumulated value within adder 38, the output of register 36 is added to the new input value on bus 12. Then, in adder 40, the 2ⁿdelayed pixel value produced on bus 28 by circuit 20, is subtracted from the output of adder 38. The resulting output of adder 40 is the next accumulated value, which is clocked into register 36 by the next pixel synchronization clock transition on line 14.

[0038] The output of register 36, which is the current accumulated value of the most recently received 2ⁿpixels, is delivered to an n-bit right shift circuit 42, which produces an output on line 44 equal to the output of register 36 shifted n places to the right, which has the effect of dividing the accumulated value of the neighboring 2ⁿpixels by 2ⁿ, without rounding, thus producing on line 44 the average of the 2ⁿmost recently received pixels, which is the second alternative pivot value that can be used by filter 20, as discussed above.

[0039] It will be noted that the “window” of 2ⁿpixel values used in computing Maximum, Minimum, and pivot values according to the present filtering technique, includes pixel values that are received before and after the pixel value being filtered, i.e. are spatially positioned on both sides of the location of the pixel for which an output value is being computed. This is the reason for the 2ⁿ⁻¹pixel latency of the filtering circuit 10. To compute an output value for a pixel, the input value for that pixel is combined with the input values of 2ⁿ⁻¹previously received and 2ⁿ⁻¹−1 subsequently received pixels to determine Minimum, Maximum and pivot values. These values are then combined with the original pixel value in accordance with formula (4) provided above, to compute an output value for the pixel. Accordingly, it will be appreciated that the Minimum, Maximum and pivot values that are based on the window of 2ⁿpixel values accumulated in circuit 20, should be used in conjunction with the pixel value on line 26, which is delayed by 2ⁿ⁻¹periods of the pixel synchronization clock, to produce an output value which is also delayed by 2ⁿ⁻¹periods of the pixel synchronization clock.

[0040] The first and second pivot values generated by the hardware described above, are delivered to a multiplexer 50 which selects a pivot value based upon a filter type selection bit in a register 52. Thus, the appropriate pivot value is delivered to bus 54 at the output of multiplexer 50.

[0041] In accordance with formula (4) provided above, an adder 56 subtracts the pivot value on bus 54 from the 2ⁿ⁻¹delayed pixel value on bus 26. The resulting (possibly negative) value is represented, for example, as a two's complement binary number. This number is then multiplied by the filter parameter K as set forth in formula (4) above. As noted above, K is advantageously selected to be an integer power of 2, i.e., K=2^xwhere x is a positive integer. When K is chosen as an integer power of 2, then multiplication by K can be achieved by a bit shift. In the hardware embodiment illustrated in FIG. 1, a value for x is stored in a register 57, and supplied to an x-bit left shift circuit 58 which produces an output on bus 60 that is equal to K(Input−Pivot) as set forth in formula (4) above.

[0042] In accordance with formula (4) above, an adder 62 adds the two's complement formatted result on bus 60 to the pivot value on bus 54 to produce an output pixel value on bus 64. This output pixel value is then delivered to a limiter 66. Limiter 66 limits the output pixel value to no greater than the Maximum value on bus 22 and no less than the Minimum value on bus 24, producing a limited output on bus 68 for the pixel. The output on bus 68 is fed to an input of a multiplexer 70. The second input to multiplexer 70 receives the 2ⁿ⁻¹delayed pixel value on bus 26. Multiplexer 70 produces a final output on bus 16. Multiplexer 70 is controlled by a control signal on line 72. Filtering can be disabled by controlling multiplexer 70 via line 72 to deliver the 2ⁿ⁻¹delayed pixel value from bus 26 to output bus 16. Also, since the filtering technique described herein requires the use of 2ⁿneighboring pixels, pixels at the edges of the displayed image are not filtered; accordingly, during output of the first 2ⁿ−1 pixels or the last 2ⁿpixels of a filtered line of pixels, multiplexer 70 is controlled to deliver the 2ⁿ⁻¹delayed pixel value from bus 26 to output bus 16.

[0043] Referring now to FIG. 2, details of the 2ⁿsample sorter and shift register circuit 20 can be explained. This circuit includes a plurality of ranking circuits 100 and a plurality of pixel value registers 102. Ranking circuits 100 and pixel value registers 102 are each synchronously clocked in response to the pixel clock synchronization signal on line 14. Pixel value registers 102 are connected in series to form a shift register to store and output delayed pixel values. Pixel value register 1, labeled 102-1, receives the input pixel value from bus 12, and delivers a one clock period delayed pixel value to pixel value register 2 (not shown). Pixel value registers 102 are connected in this serial fashion through pixel value register 2ⁿ−1, labeled 102-2ⁿ−1, which receives a 2ⁿ−2 clock period delayed pixel value and delivers a 2ⁿ−1 clock period delayed pixel value to pixel value register 2ⁿ, labeled 102-2ⁿ. Pixel value register 2ⁿdelivers a 2ⁿclock period delayed pixel value to output bus 28. Intermediate the pixel value registers 102 shown in FIG. 2, is a pixel value register 2ⁿ⁻¹(not shown), which delivers a 2ⁿ⁻¹clock period delayed pixel value to output bus 26.

[0044] Adjacent to each pixel value register is an associated ranking circuit 100. Ranking circuits 100 perform the function of ranking the pixel values stored in the adjacent pixel value circuits with a rank value from 0 to 2ⁿ−1. The ranking circuits 100 are serially connected in a manner analogous to the pixel value circuits 102. Each ranking circuit 100 is synchronously clocked by the clock signal on line 14, and in synchrony with this clock signal, receives and latches a current rank from the immediately preceding ranking circuit, simultaneously with the receipt of the corresponding pixel value by the associated pixel value register 102.

[0045] The ranking circuits 100, with the exception of the final ranking circuit 100-2ⁿ, each compute a new ranking for the pixel value in the associated pixel value circuit 102, based upon the latched prior ranking received from the immediately preceding ranking circuit, the pixel value, the rank of the 2ⁿdelayed pixel value, and the value of the new pixel being received on line 14. Specifically, each ranking circuit 100-1 to 100-2ⁿ−1, receives as inputs (a) the new pixel value on line 14, (b) the current rank of the 2ⁿclock period delayed pixel value, from bus 104 which connects to the output of ranking circuit 100-2ⁿ, (c) the value of the pixel stored in the associated pixel value register 102 and received on a bus 106, and (d) the latched pixel value rank received on a bus 108 from the immediately preceding ranking circuit. In response to these inputs, the ranking circuit generates a new pixel value rank for delivery on a bus 108 leading to the latched input of the next ranking circuit 100.

[0046] Each ranking circuit 100-i, i=0 to 2ⁿ−1, computes and produces a new pixel value rank on its output bus 108-i in accordance with the following rules, which are executed in parallel to increment, decrement, or leave unchanged the pixel value rank: (a.) if the rank of the 2ⁿdelayed pixel value on bus 104 is less than the current rank value latched into the ranking circuit 100-i from its input bus 108-i−1, then the current rank is decremented by 1 for production on the output bus 108-i; (b.) if the pixel value currently in the associated pixel value register 102 and delivered on bus 106-i, is greater than the new pixel value received on bus 12, then the current rank is incremented by 1.

[0047] Each ranking circuit 100-i, i=0 to 2ⁿ−1, also produces additional output signals to aid in the initial ranking of the new pixel value received on bus 12. Specifically, a ranking circuit 100-i produces a “1” valued “added below” signal on a line 110-i, if the pixel value currently in the associated pixel value register 102-i and delivered on bus 106-i, is greater than the new pixel value received on bus 12. Otherwise, a ranking circuit 100-i produces a “0” valued “added below” signal on a line 110-i.

[0048] The input on bus 108-0 to the first ranking circuit 100-1 is generated by a rank determiner circuit 111. Rank determiner produces an n-bit value on its output bus 108-0 which is equal to the number of “0” value “added below” signals received on lines 110 from the 2ⁿ−1 ranking circuits 100-1 through 100-2ⁿ−1. It will be appreciated that this n-bit value will reflect the initial rank of the newly-received pixel value on bus 12.

[0049] The foregoing describes the operations of the ranking circuits 100-1 through 100-2ⁿ−1. The last ranking circuit 100-2ⁿhas a more simple operation because it does not need to compute a new rank for the 2ⁿpixel clock period delayed pixel value, as that value will not be in the set of 2ⁿsamples to be ranked during the next clock cycle. Accordingly, the last ranking circuit 100-2ⁿsimply delivers to its output bus 104, the pixel rank most recently latched from its input bus 108-2ⁿ−1.

[0050] All of the ranking circuits 100-i, i=0 to 2ⁿ(i.e., including the last ranking circuit), produce appropriate control signals for generating the Maximum and Minimum pixel value signals on output busses 24 and 22. Specifically, each ranking circuit 100-i produces a “rank=0” signal on a line 112-i, if the latched pixel rank latched from its input bus 108-i−1 is equal to 0, otherwise not; each ranking circuit 100-i also produces a “rank=2ⁿ−1” signal on a line 114-i, if the latched pixel rank latched from its input bus 108-i−1 is equal to 2ⁿ−1, otherwise not. The “rank=0” and “rank=2ⁿ−1” signals on lines 112-i and 114-i are delivered to respective tri-state bus drivers 118-i and 116-i. The inputs for bus drivers 118-i and 116-i are connected to the respective output bus 106-i of the associated pixel value register 102-i. The outputs for bus drivers 118-i and 116-i are respectively connected to the minimum pixel value output bus 24 and the maximum pixel value output bus 22. A driver 118-i is enabled and delivers its input signal to the output bus 24 only when the “rank=0” signal on the associated line 112-i is asserted, otherwise not. A driver 116-i is enabled and delivers its input signal to the output bus 24 only when the “rank=2ⁿ−1” signal on the associated line 114-i is asserted, otherwise not. It will be appreciated that only one “rank=0” and one “rank=2ⁿ−1” signal will be asserted at any one time, and accordingly the minimum and maximum pixel values will be appropriately delivered to the output busses 24 and 22.

[0051] It will be appreciated that upon start-up initialization of the circuitry described herein, pixel value registers 102 and ranking circuits 100 and accumulator register 36 must be initialized to appropriate and consistent values for proper operation. For example, accumulator register 36 may be initialized to a value of 0, in which ease all pixel value registers 102 must also be initialized to a value of 0. For proper operation, ranking circuits 100 must be initialized to contain each and every one of the values from 0 to 2ⁿ−1; for example, ranking circuit 1100-1 can be initialized to have a rank of 0, ranking circuit 2 can be initialized to have a rank of 1, and so on until ranking circuit 2ⁿ100-2ⁿis initialized to have a rank of 2ⁿ−1.

[0052] The results that can be produced in accordance with the filter of formula (4) and the hardware embodiment of FIGS. 1 and 2 has been simulated in software. Referring now to FIGS. 3A-3C, the results of this simulation on a simulated blurry step transition in luminance can be seen. Specifically, each figure illustrates thirteen pixel values 120 showing a slow transition from a minimum value (at pixels 120-1 through 120-3) to a maximum value (at pixels 120-11, 120-12 and 120-13). Illustrated in each figure are the average of eight neighboring pixel values at each point (curve 122) and the median value of eight neighboring pixels at each point (curve 124). Also illustrated are the output pixel values produced by filtering in accordance with formula (4) and the hardware shown in FIGS. 1-2, where n=3. Curve 126 shows output values produced for a pivot value equal to the average of the minimum and maximum values of the neighboring eight pixels, and curve 128 shows output values produced for a pivot value equal to the average of all of the neighboring eight pixels. FIG. 3A shows curves 126 and 128 for a filter parameter k=2, FIG. 3B shows curves 126 and 128 for a filter parameter k=4, and FIG. 3C shows curves 126 and 128 for a filter parameter k=16. It can be seen that in each figure, the output pixel values exhibit a much sharper transition from the minimum to maximum pixel values than the original pixel values, which will make the resulting picture output substantially sharper. The extent of the change is affected by the selected parameter value k, as can be seen by comparing the figures.

[0053] It should be noted that the various averaging calculations performed to generate FIGS. 3A to 3C, as simulated in software, included rounding and accordingly are more accurate than the nonrounded averaging that is performed by the hardware.

[0054] While the present invention has been illustrated by a description of various embodiments and while these embodiments have been described in considerable detail, it is not the intention of the applicants to restrict or in any way limit the scope of the appended claims to such detail. Additional advantages and modifications will readily appear to those skilled in the art.

[0055] For example, instead of using a right shift to divide by 2 or by 2ⁿwithout rounding when forming pivot values, a more complex circuit may be used that include a rounding feature; such a circuit would be more complex in terms of hardware but more accurate.

[0056] In another alternative embodiment, a window of 2ⁿ⁻¹pixels spaced on either side of the pixel being filtered can be used in generating minimum and maximum values and in generating an average original pixel value to become the pivot value. Doing so will ensure that the pixels used to form the pivot are evenly distributed on both sides of the original pixel location. This can be achieved by extending the shift register and sorter circuit 20 by one additional stage. In order to achieve the advantage of dividing by an integral power of two, the original pixel value at the original pixel location could be excluded from the original pixel values that arc averaged to form a pivot value, so that this average can be formed by dividing by 2ⁿ. (An alternative accumulator structure would be needed to sum the appropriate pixel values to accomplish this approach.)

[0057] In another alternative embodiment, a weighted average of neighboring original pixel values could be used to compute a pivot value. So long as the sum of the weights is chosen to be a power of two, division by a power of two can be used to form the weighted average pivot value. Here again, an alternative accumulator structure would be needed to sum the weighted original pixel values.

[0058] The invention in its broader aspects is therefore not limited to the specific details, representative apparatus and method, and illustrative example shown and described. Accordingly, departures may be made from such details without departing from the spirit or scope of applicant's general inventive concept.