Patent Publication Number: US-7907210-B2

Title: Video de-interlacing with motion estimation

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This is a divisional of co-pending prior U.S. patent application Ser. No. 11/091,853 entitled “Gradient Adaptive Video De-Interlacing” filed Mar. 28, 2005 to be issued as U.S. Pat. No. 7,567,294, which application is incorporated herein by reference. 
    
    
     BACKGROUND 
     For a variety of applications, it is necessary to convert conventional interlaced video signal frames into a progressive scan format. For example, it may be necessary to convert an interlaced signal received over the air into a progressive scan format for display on a digital video monitor. 
     A number of de-interlacing techniques have been proposed. According to an inter-field technique known as “weave”, the pixel to be generated is taken from the corresponding pixel in the previous field. This technique may result in artifacts when there is motion in the video signal at the point of interpolation. 
     According to an intra-field technique know as “bob”, the pixel value to be generated is interpolated from the two pixels in the same field which are respectively directly above and directly below the pixel to be generated. This technique may result in loss of resolution and creation of certain artifacts. 
     In another technique, sometimes referred to as “motion adaptive” de-interlacing, motion detection is applied at the point where interpolation is occurring. If there is no motion, a “weave” approach is applied. If there is motion at the current point, a “bob” approach is applied. In another proposed motion adaptive de-interlacing technique, the pixel value to be generated is obtained as a weighted average of the pixel values that would be obtained by the “bob” and “weave” approaches, and the weights applied to the bob and weave pixel values vary depending on the degree of motion. Even with these approaches, however, goals for image quality may not be met. 
     Another technique is known as “motion compensated” de-interlacing. In this approach, motion between the current field and the previous field is estimated to produce motion vectors at, for example, each pixel location. Then interpolation is performed using pixels from the previous frame that have been relocated in accordance with the motion vectors. Motion compensated de-interlacing generally produces superior results in terms of image quality, but requires a high degree of processing complexity, and may still fall short of the desired level of image quality. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of an apparatus which performs a de-interlacing process in accordance with some embodiments. 
         FIG. 2  is a flow chart that illustrates a de-interlacing process provided according to some embodiments. 
         FIG. 3  schematically illustrates an aspect of the process of  FIG. 2 . 
         FIG. 4  schematically illustrates another aspect of the process of  FIG. 2 . 
         FIG. 5  is a flow chart that illustrates a de-interlacing process provided according to some other embodiments. 
         FIG. 6  is a flow chart that illustrates some details of the process of  FIG. 5 . 
         FIGS. 7-9  schematically illustrate aspects of the process of  FIGS. 5-6 . 
         FIG. 10  is a block diagram of an embodiment of the de-interlacing component of the apparatus of  FIG. 1 . 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a block diagram of an apparatus  100  which performs a de-interlacing process in accordance with some embodiments. 
     The apparatus  100  includes a tuner  102  or other source of interlaced video signal. Though not separately shown, the tuner  102  may include, if necessary, suitable circuitry for converting the interlaced video signal into a digital interlaced video signal. 
     The apparatus  100  may also include a noise reduction filtering block  104  which is coupled to the tuner  102  and which performs noise reduction filtering on the digital signal provided by the tuner  102 . 
     In addition, the apparatus  100  includes a de-interlacing process block  106  which is coupled to the noise reduction filtering block  104  and which performs de-interlacing of the digital video signal in accordance with some embodiments. (It will be appreciated that the de-interlacing process block  106  may be considered to be coupled to the tuner  102  via the noise reduction filter block  104 .) 
     Further, the apparatus  100  may include one or more other image signal processing blocks (indicated at  108 ) to perform one or more other processes on the de-interlaced video signal, such as sharpness enhancement, color correction, gamma correction, etc. 
     The apparatus  100  may also include a scaling block  110  (shown in phantom) to perform resizing of the image for display on a digital display component  112 , which is also included in the apparatus  100 . 
     Except for the de-interlacing process block  100 , the components of the apparatus  100  may be configured and may operate in accordance with conventional practices. 
       FIG. 2  is a flow chart that illustrates a de-interlacing process provided according to some embodiments. The process may be performed at some or all of the locations of pixels that are to be interpolated to supply missing lines of a video signal field and thus to de-interlace the video signal field. This process may be considered to be an intra-field de-interlacing process, since the interpolation of missing pixels relies only on pixel data from other pixels in the same field. Each process stage illustrated at  FIG. 2  may be performed at a single pixel location for a pixel to be interpolated, and may be repeated at each pixel location. 
     (At top, bottom and/or side edges, needed pixel values may be generated by processes such as filling with black pixels, filling with duplicates of edge pixel values, or mirroring pixel values from the edge. Alternatively at the edges a de-interlacing process such as “bob” or “weave” may be used in place of the process illustrated in  FIG. 2 .) 
     At  202  in  FIG. 2 , an interpolation direction is determined to be the best direction in which to perform interpolation at the current pixel location. That is, the edge gradient, if any, is measured in a number of different directions. More specifically, a score is calculated for each of a number of possible interpolation directions and the interpolation direction which has the lowest score is determined.  FIG. 3  schematically illustrates an example of a set of possible interpolation directions that may be scored in accordance with some embodiments to detect edge gradients. In  FIG. 3 , shaded circle  302  indicates the location for a pixel for which the pixel value is currently being interpolated. Pixels  304 - 1  to  304 - 9  are pixels that make up part of a video signal line that is immediately above current pixel location  302 . It will be understood that the pixel values for pixels  304 - 1  to  304 - 9  are available, since the line that includes those pixels is included in the current field, whereas the line that includes pixel location  302  is a missing line that is to be supplied by interpolation in order to de-interlace the current field. Pixel  304 - 5  is the pixel that is immediately above the current pixel location  302 . Pixel  304 - 4  is the pixel that is immediately to the left of pixel  304 - 5 ; pixel  304 - 3  is the pixel that is immediately to the left of pixel  304 - 4 ; pixel  304 - 2  is the pixel that is immediately to the left of pixel  304 - 3 ; pixel  304 - 1  is the pixel that is immediately to the left of pixel  304 - 2 . Pixel  304 - 6  is the pixel that is immediately to the right of pixel  304 - 5 ; pixel  304 - 7  is the pixel that is immediately to the right of pixel  304 - 6 ; pixel  304 - 8  is the pixel that is immediately to the right of pixel  304 - 7 ; pixel  304 - 9  is the pixel that is immediately to the right of pixel  304 - 8 . 
     Pixels  306 - 1  to  306 - 9  are pixels that make up part of a video signal line that is immediately below current pixel location  302 . Again, the pixel values for pixels  306 - 1  to  306 - 9  are available since the line that includes those pixels is included in the current field. Pixel  306 - 5  is the pixel that is immediately below the current pixel location  302 . Pixel  306 - 4  is the pixel that is immediately to the left of pixel  306 - 5 ; pixel  306 - 3  is the pixel that is immediately to the left of pixel  306 - 4 ; pixel  306 - 2  is the pixel that is immediately to the left of pixel  306 - 3 ; pixel  306 - 1  is the pixel that is immediately to the left of pixel  306 - 2 . Pixel  306 - 6  is the pixel that is immediately to the right of pixel  306 - 5 ; pixel  306 - 7  is the pixel that is immediately to the right of pixel  306 - 6 ; pixel  306 - 8  is the pixel that is immediately to the right of pixel  306 - 7 ; pixel  306 - 9  is the pixel that is immediately to the right of pixel  306 - 8 . 
     In the embodiments illustrated by  FIG. 3 , nine possible interpolation directions are examined (scored) and one of the nine directions is selected. The nine possible directions include: (a) direction  308 - 1 , which runs from pixel  304 - 1  through pixel location  302  to pixel  306 - 9 ; (b) direction  308 - 2 , which runs from pixel  304 - 2  through pixel location  302  to pixel  306 - 8 ; (c) direction  308 - 3 , which runs from pixel  304 - 3  through pixel location  302  to pixel  306 - 7 ; (d) direction  308 - 4 , which runs from pixel  304 - 4  through pixel location  302  to pixel  306 - 6 ; (e) direction  308 - 5 , which runs from pixel  304 - 5  through pixel location  302  to pixel  306 - 5 ; (f) direction  308 - 6 , which runs from pixel  304 - 6  through pixel location  302  to pixel  306 - 4 ; (g) direction  308 - 7 , which runs from pixel  304 - 7  through pixel location  302  to pixel  306 - 3 ; (h) direction  308 - 8 , which runs from pixel  304 - 8  through pixel location  302  to pixel  306 - 2 ; (i) direction  308 - 9 , which runs from pixel  304 - 9  through pixel location  302  to pixel  306 - 1 . 
     In accordance with some embodiments, the examination or scoring for each direction may include calculating a sum of absolute differences between (i) a rectangular group of pixels that is centered at the one of pixels  304  which corresponds to the direction in question and (ii) a rectangular group of pixels that is centered at the one of pixels  306  which corresponds to the direction in question. To illustrate, in the case of scoring the direction  308 - 3 , the sum of absolute differences (SAD) is calculated between a rectangular group of pixels that is centered at pixel  304 - 3  and a rectangular group of pixels that is centered at pixel  306 - 7 .  FIG. 4  schematically illustrates such a rectangular group of pixels  400 , centered at pixel  402  (which may be pixel  304 - 3  or pixel  306 - 7  as the case may be, when the direction  308 - 3  is being scored). The group  400  may include only pixels that were originally in the field being processed, and not interpolated pixels. In this example, the rectangular group of pixels, or window, has the dimensions 3 pixels down by 7 pixels across. 
     For each of the nine possible interpolation directions, let Window  1  be the window centered at the corresponding pixel  304  for the direction in question (e.g., pixel  304 - 3  in the case of direction  308 - 3 ) and let Window  2  be the window centered at the corresponding pixel  306  for the direction in question (e.g., pixel  306 - 7  in the case of direction  308 - 3 ). Let P 1 (i,j) be the pixel value for the i&#39;th pixel in the j&#39;th row of Window  1  and let P 2 (i,j) be the pixel value for the i&#39;th pixel in the j&#39;th row of Window  2 . 
     For each possible interpolation direction, the SAD, which is the score for the direction, may be calculated as follows: 
     
       
         
           
             
               ∑ 
               
                 
                   1 
                   ≤ 
                   i 
                   ≤ 
                   7 
                 
                 , 
                 
                   1 
                   ≤ 
                   j 
                   ≤ 
                   3 
                 
               
             
             ⁢ 
             
                
               
                 
                   
                     P 
                     1 
                   
                   ⁡ 
                   
                     ( 
                     
                       i 
                       , 
                       j 
                     
                     ) 
                   
                 
                 - 
                 
                   
                     P 
                     2 
                   
                   ⁡ 
                   
                     ( 
                     
                       i 
                       , 
                       j 
                     
                     ) 
                   
                 
               
                
             
           
         
       
     
     The direction which is found to have the lowest score (i.e., the lowest SAD) is determined to be the best interpolation direction. In other words, the direction which shows the least edge gradient is selected as the direction along which interpolation occurs. At  204  in  FIG. 2 , interpolation along the selected direction is performed by taking the arithmetic mean of the respective values for the pixel  304  and the pixel  306  which correspond to the selected direction. For example, if direction  308 - 3  is selected (as having the lowest SAD score), then the arithmetic mean is taken of the values of pixels  304 - 3  and  306 - 7 . The resulting mean value is considered to be a candidate pixel value and is taken as one input of a median function which is applied at  206  in  FIG. 2 . In some embodiments, the median function has six other inputs, namely the six pixel values of pixels  304 - 4 ,  304 - 5 ,  304 - 6 ,  306 - 4 ,  306 - 5  and  306 - 6 . The output of the median function is taken as the interpolated pixel value for the current pixel location  302 . 
     Instead of examining nine possible interpolation directions, as in the example above, in other embodiments the number of possible interpolation directions to be examined may be three, five, seven, eleven or more, or other numbers of interpolation directions. 
     The window dimensions for the SAD calculation need not be three pixels by seven pixels; other dimensions may be used. In some embodiments, effectively the window may only be a single pixel, namely the pixel  304  or  306  associated with the interpolation direction that is being examined (i.e., scored). To be more explicit, in these embodiments the score for each interpolation direction may be the absolute value of the difference between the respective values for the pixel  304  and the pixel  306  associated with the interpolation direction in question. 
     In some embodiments, the number of inputs to the median function may be other than seven. For example, in some embodiments the number of inputs to the median function may be three, namely the candidate pixel value calculated at  204  plus the respective values for pixels  304 - 5  and  306 - 5 . 
     The intra-field de-interlacing process described with reference to  FIGS. 2-4  may produce quite good image quality while requiring a rather modest degree of calculating complexity. Consequently, the process of  FIGS. 2-4  may embody a favorable trade-off between complexity and image quality. 
     In other embodiments, a motion-compensated de-interlacing process as described below in connection with  FIGS. 5-9  may be performed. 
       FIG. 5  is a flow chart that illustrates a motion-compensated de-interlacing process provided according to some embodiments. At  502  in  FIG. 5 , a sequence of interlaced video signal fields is received. The sequence includes a current field (sometimes referred to as “field N”) that is being subjected to motion compensated de-interlacing, a previous field (sometimes referred to as “field N−1”) which immediately precedes field N in the sequence of video signal fields, and a succeeding field (sometimes referred to as “field N+1”) which immediately follows field N in the sequence of video fields. 
     At  504  in  FIG. 5 , an initial de-interlacing process is performed with respect to each one of fields N−1, N and N+1. For example, in each case the initial de-interlacing process may be an intra-field de-interlacing process such as the edge gradient adaptive process described above in connection with  FIGS. 2-4  (which, as indicated above includes detecting edge gradients at the locus of the pixel to be interpolated). In other embodiments, the initial de-interlacing process may be a conventional “bob” de-interlace. 
     At  506  in  FIG. 5 , motion estimation is performed with respect to field N to determine motion vectors for field N.  FIG. 6  is a flow chart that illustrates details of the motion estimation performed at  506 . Let {right arrow over (D)}(x,y,N,N−1) denote the motion vector which indicates motion from field N−1 to field N for the pixel location (x,y) in field N. At  602  in  FIG. 6 , {right arrow over (D)}(x,y,N,N−1) is initialized to zero for each pixel location. Then, at  604 , field N is zig-zag scanned from the upper left hand corner to the lower right hand corner, as schematically illustrated in  FIG. 7 . At each pixel location encountered during the scan of  604 , the loop  606 - 608  is performed. The scan may visit only locations for which pixel values are to be interpolated. At  606 , a base motion vector {right arrow over (D)} 0  is selected from the candidate set {{right arrow over (D)}(x−1,y,N,N−1), {right arrow over (D)}(x,y−1,N,N−1)}, where {right arrow over (D)}(x−1,y,N,N−1) is the motion vector currently assigned to the pixel location (x−1,y) which is immediately to the left of the current pixel location (x,y) and {right arrow over (D)}(x,y−1,N,N−1) is the motion vector currently assigned to the pixel location (x, y−1) which is immediately above the current pixel location. The selection is performed on the basis of a score assigned to each motion vector in the candidate set, where the score is calculated with respect to a window win(x,y) of pixel locations centered at the current pixel location (x,y). In some embodiments, the dimensions of win(x,y) may be three pixels by three pixels, as illustrated in  FIG. 8 . Windows of other dimensions may be used. In general it may be desirable to increase the size of the window, subject to constraints on complexity and/or size of the processing circuitry and/or processing time. The score for each motion vector in the candidate set of motion vectors may be calculated according to the following sum of absolute difference formula: 
                 ∑       (       x   ′     ,     y   ′       )     ∈     win   ⁡     (     x   ,   y     )           ⁢     (             α   ⁢              P   N     ⁡     (       x   ′     ,     y   ′       )       -       P     N   -   1       ⁢     (         x   ′     +   dx     ,       y   ′     +   dy       )                +               β   ⁢              P     N   +   1       ⁡     (         x   ′     -   dx     ,       y   ′     -   dy       )       -       P     N   -   1       ⁡     (         x   ′     +   dx     ,       y   ′     +   dy       )                      )       ,         
where:
 
     (x′,y′) indicates a pixel location in win(x,y); 
     P N ( ) is the pixel value in field N at the indicated pixel location; 
     P N−1 ( ) is the pixel value in field N−1 at the indicated pixel location; 
     P N+1 ( ) is the pixel value in field N+1 at the indicated pixel location; 
     (dx,dy) is the value of the motion vector that is being scored; and 
     α,β are weighting factors. 
     In some embodiments α=β=1. 
     It will be appreciated that the first absolute value term in the above formula implements a comparison between fields N and N−1, whereas the second absolute value term implements a comparison between fields N−1 and N+1. Thus this formula implements motion estimation based on the immediate past field, the current field and the immediate future field. The motion vector from the candidate set which has the lowest score according to this formula is selected to be the base motion vector {right arrow over (D)} 0 . 
     At  608  an updated motion vector {right arrow over (D)} 1 (x,y,N,N−1) is selected from the candidate set {{right arrow over (D)} 0 +(0,0), {right arrow over (D)} 0 +(1,0), {right arrow over (D)} 0 +(0,1), {right arrow over (D)} 0 +(−1,0), {right arrow over (D)} 0 +(0,−1)}. The motion vectors in the latter set may be scored in accordance with the same formula set forth above in connection with  606 , and the motion vector from this set having the lowest score is selected to be the updated motion vector {right arrow over (D)} 1 (x,y,N,N−1). The motion vector {right arrow over (D)}(x,y,N,N−1) applicable to the current pixel location (x,y) in field N is then updated to equal {right arrow over (D)}(x,y,N,N−1). 
     At  610  field N is zig-zag scanned from the lower left hand corner to the upper right hand corner, as schematically illustrated in  FIG. 9 . At each pixel location encountered during the scan of  610 , the loop  612 - 614  is performed. At  612 , a base motion vector {right arrow over (D)} 2  is selected from the candidate set {{right arrow over (D)}(x,y,N,N−1), {right arrow over (D)}(x+1,y,N,N−1), {right arrow over (D)}(x,y+1,N,N−1)}, where {right arrow over (D)}(x+1,y,N,N−1) is the motion vector assigned to the pixel location (x+1,y) which is immediately to the right of the current pixel location (x,y) and {right arrow over (D)}(x,y+1,N,N−1) is the motion vector assigned to the pixel location (x,y+1) which is immediately below the current pixel location. The motion vectors in the latter set may be scored in accordance with the same formula set forth above in connection with  606 , and the motion vector from this set having the lowest score is selected to be the base motion vector {right arrow over (D)} 2 . 
     At  614  an updated motion vector {right arrow over (D)} 3 (x,y,N,N−1) is selected from the candidate set {{right arrow over (D)} 2 +(0,0), {right arrow over (D)} 2 +(1,0), {right arrow over (D)} 2 +(0,1), {right arrow over (D)} 2 +(−1,0), {right arrow over (D)} 2 +(0,−1)}. The motion vectors in the latter set may be scored in accordance with the same formula set forth above in connection with  606 , and the motion vector from this set having the lowest score is selected to be the updated motion vector {right arrow over (D)} 3 (x,y,N,N−1). The motion vector {right arrow over (D)}(x,y,N,N−1) applicable to the current pixel location (x,y) in field N is then updated to equal {right arrow over (D)} 3 (x,y,N,N−1). 
     (At top, bottom and/or side edges, needed pixel values may be generated by processes such as filling with black pixels, filling with duplicates of edge pixel values, or mirroring pixel values from the edge.) 
     With the completion of the upward scan at  610  and the associated loops of  612 - 614 , the motion estimation is complete, and all of the necessary motion vectors have been determined for field N. Referring again to  FIG. 5 , at  508  motion-compensated de-interlacing is performed with respect to field N, using the motion vectors determined at  506 . The motion-compensated de-interlacing performed at  508  may be in accordance with conventional practices, noting however that the motion estimation performed at  506  to obtain the motion vectors departs from conventional practices. In accordance with conventional practices, a pixel in the reference image (e.g., field N−1) is shifted by the motion vector obtained at  506  and then is filled in to the place required. The reference pixel may come, in some embodiments, either from field N−1 or from field N+1. Median filtering may also be applied to filter out errors. 
     The process of  FIG. 5  may be performed with respect to each field of the input video signal. This process, and particularly the motion estimation described in conjunction with  506 , may produce very superior results in terms of image quality. 
     In some embodiments, motion compensated de-interlaced pixels for field N−1 may be used in the motion-estimation process for field N instead of using intra-field de-interlaced pixels for field N−1. However, in such cases there may be a risk of propagation of errors in the event of a scene change. Thus it may be advisable to employ scene change detection if motion compensated de-interlaced pixels for field N−1 are used in performing motion estimation for field N. 
     In some embodiments, motion estimation and motion-compensated de-interlacing may be performed backwards from field N+1 to field N rather than forward from field N−1 to field N. In such cases, the motion vector scoring formula may be changed so that the first absolute value term compares a pixel value from field N to a pixel value from field N+1 rather than comparing the pixel value from field N to a pixel value from field N−1. 
     In some embodiments, the motion estimation for field N may be performed with reference to fields N−1 and N−2, or with reference to fields N+1 and N+2, instead of with reference to fields N−1 and N+1. For example, if the motion estimation is performed with reference to fields N−1 and N−2, the following sum of absolute difference formula may be used in place of the formula set forth above with reference to  606 : 
     
       
         
           
             
               ∑ 
               
                 
                   ( 
                   
                     
                       x 
                       ′ 
                     
                     , 
                     
                       y 
                       ′ 
                     
                   
                   ) 
                 
                 ∈ 
                 
                   win 
                   ⁡ 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                 
               
             
             ⁢ 
             
               
                 ( 
                 
                   
                     
                       
                         
                           α 
                           ⁢ 
                           
                              
                             
                               
                                 
                                   P 
                                   N 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       x 
                                       ′ 
                                     
                                     , 
                                     
                                       y 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 
                                   P 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         ′ 
                                       
                                       + 
                                       dx 
                                     
                                     , 
                                     
                                       
                                         y 
                                         ′ 
                                       
                                       + 
                                       dy 
                                     
                                   
                                   ) 
                                 
                               
                             
                              
                           
                         
                         + 
                       
                     
                   
                   
                     
                       
                         β 
                         ⁢ 
                         
                            
                           
                             
                               
                                 P 
                                 
                                   N 
                                   - 
                                   2 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     
                                       x 
                                       ′ 
                                     
                                     + 
                                     
                                       2 
                                       ⁢ 
                                       dx 
                                     
                                   
                                   , 
                                   
                                     
                                       y 
                                       ′ 
                                     
                                     + 
                                     
                                       2 
                                       ⁢ 
                                       dy 
                                     
                                   
                                 
                                 ) 
                               
                             
                             - 
                             
                               
                                 P 
                                 N 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     x 
                                     ′ 
                                   
                                   , 
                                   
                                     y 
                                     ′ 
                                   
                                 
                                 ) 
                               
                             
                           
                            
                         
                       
                     
                   
                 
                 ) 
               
               . 
             
           
         
       
     
     In some embodiments, the de-interlacing process block may be implemented in the form of application-specific integrated circuitry, configured to perform either or both of the de-interlacing processes described in connection with  FIGS. 2-4  and  FIGS. 5-9 . In other embodiments, the de-interlacing process block may be constituted at least in part by a processor  1002  ( FIG. 10 ) coupled to a memory  1004 . The processor  1002  may be, for example, a general purpose microprocessor or digital signal processor or other programmable processor. The memory  1004  may store software instructions to control the processor  1002  to perform one of the de-interlacing processes described above, and may also serve as working memory and/or input and/or output digital video signal storage memory. 
     The several embodiments described herein are solely for the purpose of illustration. The various features described herein need not all be used together, and any one or more of those features may be incorporated in a single embodiment. Therefore, persons skilled in the art will recognize from this description that other embodiments may be practiced with various modifications and alterations.