Patent Publication Number: US-6700623-B1

Title: Video signal processing using triplets of pixels

Description:
FIELD OF THE INVENTION 
     This invention relates to video signal processing and especially to processes of interpolation, particularly spatial interpolation, whether horizontal, vertical or two dimensional. The invention applies in an important example to the process of de-interlacing by which a video frame is derived for each field of an interlaced video signal. 
     BACKGROUND 
     A known de-interlacing technique derives the “missing” lines through a weighted sum of neighbouring sample points. The location of the sample points to be employed and the values of the weighting coefficients are chosen to minimise visual artefacts and certain design principles have been established. 
     Adaptive techniques have emerged by which the characteristics of the de-interlacing filter are changed in the face of—for example—motion. 
     SUMMARY OF THE INVENTION 
     It is an object of aspects of the present invention to provide improved video signal processing by which the appearance of visual artefacts on spatial interpolation is further minimised. 
     It is a further object of one aspect of the present invention to provide improved video signal processing by which a video frame is derived for each field of an interlaced video signal. 
     Accordingly, the present invention consists in one aspect in a video process wherein a weighted sum of pixels from at least one input picture is taken in a filter aperture to generate a pixel in an output picture, characterised in that the weighted sum includes products of triplets of pixels. 
     Suitably, a video frame is derived through spatial interpolation from each video field of an interlaced input signal. 
     In one form of the invention, the weighted sum comprises pixels and products of triplets of pixels. 
     In another aspect, the present invention consists in a video process of interpolation, wherein adaption is provided between a process of spatial interpolation in which a weighted sum of products of pixels from an input picture is taken in a filter aperture to generate a pixel in an output picture, and a process of temporal interpolation which a weighted sum of pixels from two or more input pictures is taken in a filter aperture to generate a pixel in an output picture. 
     In yet another aspect, the present invention consists in video signal processing apparatus for interpolation, comprising an interpolation filter taking a weighted sum of pixels from at least one input picture in a filter aperture, to generate a pixel in an output picture, characterised in that the weighted sum includes products of triplets of pixels. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     This invention will now be described by way of example with reference to the accompanying drawings, in which: 
     FIG. 1 is a diagram of a de-interlacing circuit according to the present invention; 
     FIG. 2 is a diagrammatical representation of a four tap third order filter useful in accordance with the present invention; 
     FIG. 3 is a diagram illustrating a process for designing a filter according to the present invention; 
     FIG. 4 is a series of diagrams illustrating filter apertures for use in the present invention; 
     FIG. 5 is a diagram of an interpolating circuit according to one embodiment of the present invention; and 
     FIG. 6 is a diagram of an interpolating circuit according to a further embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION 
     In one embodiment of this invention, the aim is to interpolate one field of a video frame from another. This is known as de-interlacing. 
     There is shown in FIG. 1, a de-interlacing circuit in which an interlaced video signal at input terminal  10  is operated upon to form a progressive signal at output terminal  12 . A filter  14  receives one field of a video frame and from it interpolates the other field of the frame. A multiplexer  16  receives these “new” fields, as well as the original fields (appropriately delayed at  18 ). The output of the multiplexer is a progressive scan video signal. 
     In a traditional de-interlacing circuit, the filter  14  is linear, each filter tap (derived by appropriate delay elements from the input video) is multiplied by a filter weight and the resulting products are summed to give the filter output. In contrast, the present invention proposes a polynomial non-linear filter. This includes, in addition to the linear terms, the sum of filter coefficients multiplied by products of pixel values, triplets of pixel values, etc. For example, a four tap filter for use in the present invention will contain four filter coefficients which are multiplied by single pixel values, ten filter coefficients which are multiplied by products of pixel values, twenty filter coefficients which are multiplied by triplets of pixel values, etc. 
     In any practical embodiment, the polynomial series must be truncated at some point. A filter truncated at the third order is convenient and there is shown diagrammatically in FIG. 2, a four tap third order filter for use as filter  14  of FIG.  1 . The polynomial filter is illustrated graphically as the combination of a linear filter  100 , a quadratic filter  102  and a cubic filter  103 . The linear filter utilises three delay elements  104  to generate four taps from the input signal. Each tap is multiplied by a coefficient in a respective multiplier  105  and a weighted sum generated in summing device  106 . In the quadratic filter  102 , similar delay elements  114  provide four taps from the input video signal and ten multipliers  115  generate all ten possible products, again weighted by respective coefficients. A sum is formed in summing device  116 . The cubic filter has twenty multipliers  125  operating on the taps from delay elements  124  to generate all possible combinations of triplets of taps and a weighted sum is formed in summing device  126 . Although the delay elements  104 ,  114  and  124  have been shown separately in the three filters, one set of delay elements would usually suffice. 
     It will be understood that in any practical circuit there are very many ways of embodying the described filter. Typically, a single processing element will receive the four taps and with appropriate multipliers, coefficient stores and one or more summing devices, output directly the sum of the linear, quadratic and 
     To understand the technique of constructing a filter according to the present invention, it is helpful to look at FIG.  3 . The object is to design an N point digital finite impulse response filter, h, to modify the input, x(n), in such a way as to minimise the mean square error, e(n), between the filter output and the desired signal, y(n). In the case of de-interlacing, x(n) is field f 1 , and y(n) is field f 2 . The aim is to create a filter h(n) that when operated on f 1 , gives the best possible estimate of f 2  such that the mean squared error between the estimate of f 2  and actual f 2  is minimised. In FIG. 3, a progressive input is proved to block  30  which separates the fields of a video frame and outputs field f 1  and field f 2 . Field f 1 , that is to say x(n) is provided to the filter  32  to generate an estimate of f 2 . This is then compared in block  34  with the actual f 2 , that is to say y(n). 
     The filter impulse response which minimises the sum of the squared errors of data of length L, is given by the solution of the over-determined (assuming L&gt;N) system of equations          Xh   =     y                 where                                       X   =       [           x                   (   L   )             x                   (     L   -   1     )           ⋯         x                   (     L   -   N   +   1     )                 x                   (     L   -   1     )             x                   (     L   -   2     )           ⋯         x                   (     L   -   N     )               ⋮       ⋮                   ⋮             x                   (   2   )             x                   (   1   )           ⋯       0             x                   (   1   )           0       ⋯       0         ]                   and                                       y   =       [           y        (   L   )                 y                   (     L   -   1     )               ⋮             y                   (   2   )                 y                   (   1   )             ]     .                       
     the least squares solution of which is, 
     
       
           h =( X   T   X ) −1   X   T   Y.   
       
     
     where X T X=R is known as the auto-correlation matrix and X T y=p is known as he cross correlation vector. Note X T X and X T y are usually much smaller than X. Hence, it is much more efficient to compute X T X and X T y directly from x(n) and (n) rather than to form X. 
     The extension of this to a more general non-linear model is in principle simply a matter of modifying the data matrix X. Below we show the data matrix for a second order polynomial non-linear filter, in which a constant (DC) term has also been included. A symmetric form for the non-linear components of the filter has been assumed so this matrix has dimension        L   ×       (     N   +       N        (     N   +   1     )       2       )     .                           X   =     [                    1         x        (   L   )             x        (     L   -   1     )           ⋯         x        (     L   -   N   +   1     )               x        (   L   )       2             x        (   L   )                       x        (     L   -   1     )             ⋯           x        (   L   )                       x        (     L   -   N   +   1     )                 x        (     L   -   1     )       2         ⋯           x        (     L   -   N   +   1     )       2             1         x        (     L   -   1     )             x        (     L   -   2     )           ⋯         x        (     L   -   N     )               x        (     L   -   1     )       2             x        (     L   -   1     )                       x        (     L   -   2     )             ⋯           x        (     L   -   1     )                       x        (     L   -   N     )                 x        (     L   -   2     )       2         ⋯           x        (     L   -   N     )       2             1         x        (     L   -   2     )             x        (     L   -   3     )           ⋯         x        (     L   -   N   -   1     )               x        (     L   -   2     )       2             x        (     L   -   2     )                       x        (     L   -   3     )             ⋯           x        (     L   -   1     )                       x        (     L   -   N   -   1     )                 x        (     L   -   3     )       2         ⋯           x        (     L   -   N   -   1     )       2             ⋮       ⋮       ⋮                   ⋮       ⋮       ⋮                   ⋮       ⋮                   ⋮           1         x        (   3   )             x        (   2   )           ⋯       0           x        (   3   )       2             x        (   3   )                       x        (   2   )             ⋯       0           x        (   2   )       2         ⋯       0           1         x        (   2   )             x        (   1   )           ⋯       0           x        (   2   )       2             x        (   2   )                       x        (   1   )             ⋯       0           x        (   1   )       2         ⋯       0           1         x        (   1   )           0       ⋯       0           x        (   1   )       2         0       ⋯       0       0       ⋯       0                    ]                     
     The optimal filter, in the least squares sense, can then be estimated by solving h=R −1 p. The filter will contain three separate components; the DC term, the standard linear coefficients which should be multiplied by single pixel values, and the quadratic coefficients which will be multiplied by product of pixel values. 
     The present invention recognises that if the mean square error is chosen for optimisation of the filter, it is possible to calculate the filter coefficients h without forming a trial filter and iterating. The training process then represents not an iterative improvement in a trial or prototype filter, but the collection of sufficient data from real picture material for which both x and y are known, to enable calculation of meaningful auto-correlation matrix and cross correlation vector. 
     A polynomial model truncated at the third order is preferred according to this invention. This will contain linear, quadratic, and cubic filters and so is able to model systems which contain both quadratic and cubic non-linear elements. These generate both skewed and symmetric distortions of the probability density function. Higher order models can be used and are shown to give improved results but the size of the filter and the computation required in its estimation rise exponentially and there are rapidly diminishing returns. For example, the fifth order, six pixel cubic non-linear filter does perform better than the third order, six pixel filter but there are over five times as many terms. 
     For the linear case, it is found that neither increasing the number of taps in the vertical direction, of a six point vertical filter nor utilising pixels in the horizontal direction, significantly reduces the mean squared error. However, for a filter according to the present invention, the choice of aperture has much more dramatic results. For example, a two dimensional aperture does give a significant improvement over a one dimensional one. This is thought to be due to the ability of the non-linear filter to deal with sloping edges and lines and utilise gradient information. 
     However, as can be seen in Table 1, the number of filter coefficients rises exponentially with the number of pixels. Due to computational constraints a sensible maximum size is presently taken for a cubic filter of 20 pixels and for a fifth order filter, 6 pixels. 
     
       
         
           
               
            
               
                   
               
               
                 Total number of filter coefficients for third and fifth order 
               
               
                 non-linear filters containing 4,6,8,12 and 20 pixels. 
               
            
           
           
               
               
            
               
                   
                 Number of filter coefficients 
               
            
           
           
               
               
               
            
               
                 No. of pixels 
                 Third order non-linear filter 
                 Fifth order non-linear filter 
               
               
                   
               
            
           
           
               
               
               
            
               
                 4 
                 35 
                 126 
               
               
                 6 
                 84 
                 462 
               
               
                 8 
                 165 
                 1287 
               
               
                 12 
                 445 
                 6178 
               
               
                 20 
                 1770 
                 53129 
               
               
                   
               
            
           
         
       
     
     As the number of pixels available is limited it is important to choose the correct shape of aperture. Best results seem to occur from apertures that contain four vertical pixels and then a number of horizontal pixels. The apertures used for the 4, 6, 8 and 20 pixel filters are shown in FIG. 4 (X denotes the pixels used in field, f 1 , to estimate the pixel denoted by O in field, f 2 ). The use of horizontal information helps to cope with the near horizontal lines and edges that often cause problems due to jagging in de-interlacing. 
     Table 2 shows the mean squared error between the estimated field and actual field for a particular reference picture, for a series of different filters. It can be seen that in all cases, the non-linear filters perform better than standard linear filters. 
     
       
         
           
               
             
               
                 TABLE 2 
               
             
            
               
                   
               
               
                 Mean squared errors for various filters used on EBU 
               
               
                 reference picture “Girl”. 
               
            
           
           
               
               
               
            
               
                   
                 Mean squared 
                   
               
               
                   
                 error between the 
                   
               
               
                   
                 estimate of the 
                 Number of 
               
               
                   
                 field and the actual 
                 coefficients 
               
               
                 Filter type 
                 field 
                 in filter 
               
               
                   
               
            
           
           
               
               
               
            
               
                 2 pixel linear filter (0.5/0.5) 
                 23.15 
                 2 
               
               
                 4 pixel linear filter (optimum) 
                 18.61 
                 4 
               
               
                 8 pixel linear filter (optimum) 
                 18.58 
                 8 
               
               
                 36 pixel linear filter (optimum) 
                 18.55 
                 36 
               
               
                 4 pixel cubic filter (optimum) 
                 16.14 
                 35 
               
               
                 6 pixel cubic filter (optimum) 
                 15.67 
                 84 
               
               
                 6 pixel fifth order filter (optimum) 
                 14.88 
                 462 
               
               
                 8 pixel cubic filter (optimum) 
                 15.21 
                 165 
               
               
                 12 pixel cubic filter (optimum) 
                 14.69 
                 445 
               
               
                 20 pixel cubic filter (optimum) 
                 13.50 
                 1770 
               
               
                   
               
            
           
         
       
     
     It is found that the non-linear filter produces much smoother edges and curves than its linear counterpart, with reduced jagging. 
     Finally, the mean square error is given for a series of pictures for a linear, and two non-linear filters, (Table 3). It can be seen that in all cases the non-linear filters perform as well as or better than the linear filters. 
     
       
         
           
               
             
               
                 TABLE 3 
               
             
            
               
                   
               
               
                 Mean squared error for standard EBU 
               
               
                 pictures 
               
            
           
           
               
               
               
               
               
            
               
                   
                   
                 Error for 
                 Error for 
                 Error for 
               
               
                   
                 Picture 
                 4 pixel linear 
                 4 pixel cubic 
                 12 pixel cubic 
               
               
                   
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 Blackboard 
                 49 
                 43 
                 43 
               
               
                   
                 Boats 
                 73 
                 67 
                 66 
               
               
                   
                 Boy 
                 73 
                 64 
                 57 
               
               
                   
                 Clown 
                 23 
                 20 
                 20 
               
               
                   
                 Girl 
                 19 
                 17 
                 17 
               
               
                   
                 Pond 
                 166 
                 153 
                 140 
               
               
                   
                 Tree 
                 313 
                 303 
                 303 
               
               
                   
                 couple 
                 91 
                 87 
                 86 
               
               
                   
                 Kiel 
                 135 
                 128 
                 128 
               
               
                   
                 Latin 
                 363 
                 289 
                 234 
               
               
                   
                   
               
            
           
         
       
     
     Non-linear polynomial filters in accordance with the present invention can give dramatically improved performance over conventional linear predictors when used for spatial de-interlacing. Polynomial non-linear filters are generally more complex than their linear equivalents, although only using spatial information reduces the complexity significantly as compared to conventional spatio-temporal filters. The increased performance seems to occur mainly along edges; whereas linear filters often produce jagging on diagonal lines and curves, the nonlinear filters described here considerably reduce such artifacts. 
     A non-linear filter for use in the present invention can be implemented directly as a set of multipliers and an adder as so far described or the same charateristic can be achieved using a lookup table. 
     A de-interlacing circuit can operate independently or the de-interlacing function can be incorporated within a circuit operating on an interlaced signal for the purposes of standards conversion, upconversion, downconversion, aspect ratio conversion, digital video effects and so on. 
     Thus, turning to FIG. 5, there is shown a circuit which operates on an interlaced video signal received at input terminal  500  to provide through interpolation an output video signal at terminal  502 . This may be an interlace or a progressive signal and may have different numbers of lines per field, different numbers of fields per second and so on, depending upon the specific function of the circuit. One example would be an interlaced output in a different television broadcast standard to the input. 
     The input signal of FIG. 5 is passed to a polynomial filter  504  that in one example takes the form illustrated symbolically in FIG.  2 . The output of filter  504 , comprising the “new” fields, passes through a FIFO  506  to a series chain of delay elements  508 . The original fields are taken through a delay  514  to a similar FIFO  516  and delay elements  518 . 
     A weighted sum of the filter taps generated by the delay elements  508  and  518  is taken by means of multipliers  520  and summing device  522 . The output of the summing device  522  is taken through a FIFO  524 , to the output terminal. The coefficients of the multipliers are set through control unit  526 , which also serves to control the rates at which data is read into and read out of the FIFO&#39;s  506 ,  516  and  524 . 
     The skilled man will recognize that through appropriate choice of the delay elements and control of the FIFO&#39;s and multipliers, a wide variety of interpolation procedures can be conducted. 
     In another arrangement, the interpolation process is “folded into” the polynomial filter. Thus as shown in FIG. 6, an interpolating circuit has the interlaced video input signal at terminal  600  passing through FIFO  602  to a polynomial filter  604 . This may be of the same general form as FIG. 2 but with each of the multipliers receiving its multiplication coefficient dynamically from a control unit  606 . The output of the filter  604  passes through a further FIFO  608  with the control unit  606  controlling the rates at which data is read into and read out of the FIFO&#39;s  602  and  608 . 
     In still a further modification, selecting at least some of the delay elements of the filter to be field delays rather than pixel or line delays, a temporal interpolator can be produced. It is known that the performance of a de-interlacer can be improved for still material by employing temporal interpolation. It is then necessary to detect motion and to adapt or switch on detection of motion from temporal interpolation. This motion adaption is preferably conducted With prior art techniques, this switching or adaptation produces adaption artefacts that can be visually disturbing. It is found that by using a spatial interpolator according to the present invention, and preferably also a temporal interpolator using a similar polynomial filter, the visibility of adaption artefacts is considerably reduced. It is believed that the described non-linear behaviour of an interpolator according to the present invention provides a “fine” adaption, inasmuch as the value of a pixel in a product of two pixels can be regarded as varying the multiplication coefficient applied to the other pixel. Adaption in the conventional sense from temporal to spatial interpolation can in this sense be regarded as “coarse” adaption. Taking numerals as an illustration, coarse adaption might be regarded as switching from +5 to −5, which is a step large enough to produce switching artefacts. Consider now that the two values of +5 and −5 are both subject to fine adaption in the range 0,1,2,3,4,5,6,7,8,9 in the case of the +5 value, and −9,−8,−7,−6,−5,−4,−3,−2−1,0 in the case of the −5 value. Now, in face of a tendency dictating a switch from +5 to −5, it is to be expected that fine adaption will have occurred in the +5 value towards 0, thus minimising the switch step. If the −5 value has similarly undergone fine adaption towards  0 , the step will be further reduced. 
     Whilst an important example, de-interlacing is not the only application for apparatus according to the present invention. It may be more regarded as useful with an input video signal which is undersampled, de-interlacing being then only one example.