Abstract:
A method and a system is provided for deinterlacing interlaced video containing an interlaced image field f including scan lines of multiple pixels. Such deinterlacing involves detecting the one or more edge directions in the image field f using principal component analysis (PCA), and performing spatial interpolation to reconstruct a missing pixel value in the image field f substantially along each of the one or more detected edge directions.

Description:
FIELD OF THE INVENTION 
     The present invention relates to image processing, and more particularly to edge directed deinterlacing in video image processing. 
     BACKGROUND OF THE INVENTION 
     In television systems, a specific scan format called “interlaced scan format” is widely utilized. Due to the advent of digital television (DTV) signals, deinterlacing is utilized for converting from the interlaced scan format into a progressive scan format for DTV applications. There are two main deinterlacing techniques: an inter-field (or motion-compensated) interpolation technique and an intra-field (or spatial) interpolation technique. The inter-field technique requires more than one field as an input while the intra-field technique requires only one field to process. 
       FIG. 1  illustrates an example interlaced scan format  100  including a “top” field  102  and a “bottom” field  104 , which are scanned in an alternate manner on the TV screen to form the whole picture. Each “field” is formed by a stack of the “existing scan lines” as shown in  FIG. 1 . Each field (either top or bottom) contains only half the numbers of scan lines of the whole picture, while the other half of scan lines, denoted by “missing scan line” in  FIG. 1 , are missing from that field. 
     In  FIG. 1 , the symbols ◯ denote the pixels on the existing scan lines in both the top and bottom fields  102  and  104 . Further, the symbols x denote the pixels on the missing scan lines, in both the top and bottom fields  102  and  104 . The main object of the intra-field deinterlacing technique is to interpolate each missing pixel x in both the top and bottom fields from its neighboring existing pixels ◯. 
     An existing implementation for intra-field deinterlacing includes simple line doubling and vertical line averaging. However, the video qualities of these two implementations produce various artifacts, such as edge jaggedness or edge blurring, making them unsuitable for DTV applications. 
     A more advanced intra-field deinterlacing technique utilizes edge directed interpolation (EDI). Conceptually, the EDI intra-field deinterlacing technique takes advantage of the direction of edges in an image represented by the two fields, to interpolate the missing pixels. More specifically, the direction of edges associated with each missing pixel is calculated and the set of existing pixels along that calculated edge direction is used to interpolate a missing pixel. The edge detections in many implementations of the EDI intra-field deinterlacing technique are usually determined based on the maximum correlation of a pair of vectors formed by the set of existing pixels immediately above and below the missing pixel. 
     However, there are many drawbacks to the conventional EDI intra-field deinterlacing technique. First, noise can complicate proper detection of edge direction. Though setting a wider vector can help reduce this effect, it also increases the probability of misdetection in certain areas. Second, in certain areas, such as thin lines and complex detail areas, the vector correlation tends to result in incorrect direction detection. Third, the number of possible directions are limited to a preset number, and directions such as steep angles (close to vertical direction), are usually inaccessible. There is, therefore, a need for a deinterlacing technique that performs edge directed deinterlacing that addresses the above drawbacks. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention provides a method and a system for deinterlacing interlaced video comprising an interlaced image field f including scan lines of multiple pixels. In one embodiment, such deinterlacing involves detecting the one or more edge directions in the image field f using principal component analysis (PCA), and performing spatial interpolation to reconstruct a pixel value in the image field f substantially along a detected edge direction. The pixel value corresponds to a missing pixel in the interlaced field f. Performing interpolation further includes performing directional interpolation on existing pixels neighboring the missing pixel in the field f to obtain an interpolated signal f d  as the reconstructed missing pixel. 
     In addition, existing pixels neighboring the missing pixel in the field f are filtered, to obtain a filtered signal f v , and one of the signals f v  and f d  is selected as an output signal f p  representing the reconstructed missing pixel. The selection is based on the mean value of existing pixels neighboring the missing pixel. 
     Detecting one or more edge directions includes determining a set of horizontal gradients and vertical gradients associated with existing pixels neighboring the missing pixel and then determining a covariance matrix from the horizontal gradients and the vertical gradients, wherein the principal component of the covariance matrix is based on PCA. Then, based on the covariance matrix, an eigenvector is determined which represents a detected edge direction. 
     In addition, eigenvalues are determined based on the covariance matrix, and are used to calculate a reliability factor that indicates the level of reliability of said eigenvector as the direction of a detected edge. Then, the interpolated signal f d  is determined by mixing the directional interpolated value and the filtered signal f v  as a function of the reliability factor. 
     These and other features, aspects and advantages of the present invention will become understood with reference to the following description, appended claims and accompanying figures. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates an example of top and bottom fields in an interlaced scan format. 
         FIG. 2  shows a functional block diagram of an example system implementing a PCA-based edge directed deinterlacing method, according to an embodiment of the present invention. 
         FIG. 3  shows an example set of existing pixels grouped by a rectangular window for vertical filtering and grouped by a square window for PCA-based calculation, according to an embodiment of the present invention. 
         FIG. 4  shows a functional block diagram of an example of a PCA based edge directed interpolator, according to an embodiment of the present invention. 
         FIG. 5  shows an example of a set of edge directions associated with a missing pixel. 
         FIG. 6  shows a functional block diagram of an example of a bisection and strong edge detector, according to an embodiment of the present invention. 
     
    
    
     In the drawings, like references refer to similar elements. 
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention provides an intra-field interpolation deinterlacing technique that utilizes an edge directed deinterlacing technique based on PCA. PCA provides for the representation of shape, orientation and appearance. Application of PCA to the edge direction detection in deinterlacing provides accurate edge direction detection even when the edges are in noisy image areas. The detected edge directions are denoted by eigenvectors which can represent infinite number of directions including those at very steep angles. 
       FIG. 2  shows a functional block diagram of an example system  200  implementing a PCA-based edge directed deinterlacing technique, according to an embodiment of the present invention. An interlaced input field f is processed by: (1) a V-Filter  210  that performs vertical filtering on the field f to obtain a vertical filtered signal f v , (2) a PCA-based edge directed interpolator  220  that performs directional interpolation on the field f to obtain a signal f d , and (3) a bisection and strong edge detector  230  that performs bisection and strong edge detection on the field f to generate a binary map bMap. 
     The V-Filter  210  interpolates the missing pixels along the vertical direction only. It is applied to the missing pixels belonging to image areas that do not include strong edges or bisection (e.g., textured) areas (i.e., bMap=0). 
     As is known to those skilled in the art, principal component analysis is a technique for simplifying a data set, by reducing multidimensional data sets to lower dimensions for analysis. The PCA-based EDI  220  performs interpolation on missing pixels along a detected edge direction. PCA-based EDI is applied only to the missing pixels belonging to image areas that include strong edges but no bisection (i.e., bMap=1). In effect, the missing pixels that belong to strong edges but not to bisection areas, are represented by f d , while the other remaining missing pixels are represented by f v . 
     The binary map bMap is used by a multiplexer  240  to determine which of the resulting signals f v  or f d  is selected as an output signal f p  of the system  200 .  FIG. 3  shows an example field  300  (e.g., either top field  102  or bottom field  104  in  FIG. 1 ), which is of size M*N (e.g., height by width) pixels, wherein indices y and x denote the scan line number and pixel location, respectively, in the input field f  300 . For each missing scan line y=1, 3, 5, . . . , M−1, and missing pixel locations x=0, 1, . . . , N−1, the multiplexer  240  generates an output according to relation (1) below: 
     
       
         
           
             
               
                 
                   
                     
                       
                         f 
                         p 
                       
                       ⁡ 
                       
                         [ 
                         y 
                         ] 
                       
                     
                     ⁡ 
                     
                       [ 
                       x 
                       ] 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   f 
                                   v 
                                 
                                 ⁡ 
                                 
                                   [ 
                                   y 
                                   ] 
                                 
                               
                               ⁡ 
                               
                                 [ 
                                 x 
                                 ] 
                               
                             
                           
                           
                             if 
                           
                           
                             
                               
                                 
                                   bMAp 
                                   ⁡ 
                                   
                                     [ 
                                     y 
                                     ] 
                                   
                                 
                                 ⁡ 
                                 
                                   [ 
                                   x 
                                   ] 
                                 
                               
                               == 
                               0 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   f 
                                   d 
                                 
                                 ⁡ 
                                 
                                   [ 
                                   y 
                                   ] 
                                 
                               
                               ⁡ 
                               
                                 [ 
                                 x 
                                 ] 
                               
                             
                           
                           
                             if 
                           
                           
                             
                               
                                 
                                   bMap 
                                   ⁡ 
                                   
                                     [ 
                                     y 
                                     ] 
                                   
                                 
                                 ⁡ 
                                 
                                   [ 
                                   x 
                                   ] 
                                 
                               
                               == 
                               1 
                             
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     In  FIG. 3 , a missing pixel  302  is represented by f[y][x]in the field f  300 . The window  304  includes a group of neighboring existing pixels for the missing pixel  302 . The window  306  contains another group of neighboring existing pixels for the missing pixel  302 . Existing pixels in the rectangular window  304  are for filtering by the V-Filter  210 , and the existing pixels in the square window  306  are for PCA-based calculation by the PCA-based EDI  220 . An example size for the window  306  is 6-by-11 pixels and an example size for the window  304  is 6-by-1 pixels. Other sizes for the windows  304  and  306  are also possible. 
     An example of calculating f v  or f d  by the V-Filter  210  and the PCA-based EDI  220 , respectively, are now described. A vertical filtered result f v [y][x] is calculated by applying the V-Filter  210  to the existing neighbors of the missing pixel  302  in the window  304 . The resulting vertical filtered signal f v [y][x] can be represented by relation (2) below:
 
 f   v   [y][x ]=( f[y −5 ][x ]−12 f[y −3 ][x ]+75 f[y 1 ][x ]+75 f[y +1 ][x ]−12 f[y +3 ][x]+f[y +5 ][x ])/128.  (2)
 
     In this example, the V-Filter  210  utilizes a set of filter coefficients that comprise: 1/128[1 −12 75 75 −12 1]. Conceptually, a value f v [y][x] for the missing pixel  302  is calculated by the V-Filter  210  from a weighted average (according to V-Filter coefficients) of the neighboring existing pixels along a vertical direction (i.e., window  304 ). The set of V-Filter coefficients used in relation (2) has 6 taps for low-pass filtering, but other examples are possible. Other sets of coefficients with shorter or longer numbers of taps can be used in the same manner. Another example of the V-Filter  210  may be a Vertical-Temporal (VT) filter such as described by N. Seth-Smith and G. Walker, “Flexible upconversion for high quality TV and multimedia displays,” in Proc. ICCE, Chicago, Ill., June 1996, pp. 338-339, and G. de Haan and E. B. Bellers, “Deinterlacing—An Overview,” Proceedings of the IEEE, Vol. 86, No. 9, September 1998, pp. 1839-1857. 
       FIG. 4  shows a functional block diagram of an embodiment of the PCA-based EDI  220  for calculating f d , according to a preferred embodiment of the present invention. First, based on the window  306  associated with the missing pixel f[y][x], a set of horizontal gradients g H  and vertical gradients g v  associated with each existing pixel within the window  306  are calculated using a horizontal gradient calculator  402  and a vertical gradient calculator  404 , respectively. 
     The horizontal gradient calculator  402  implements relation (3) below for each existing pixel:
 
 g   H   [i][j]=f[i][j]−f[i][j −1],
 
wherein  iεI={y −5 ,y −3 ,y −1 ,y +1 ,y +3 ,y +5}, and
 
 jεJ={x −5 ,x −4 ,x −3 , . . . ,x +5}.  (3)
 
     Relation (3) calculates the set of horizontal gradients at each existing pixel location (i, j) relative to the missing pixel f[y][x] (i and j denote vertical and horizontal indices, respectively). The gradients represent differences between pixel values along the horizontal direction. Therefore, at a location (i, j), the horizontal gradient is calculated by subtracting the immediate left neighboring existing pixel f[i] [j−1] from the existing pixel f[i] [j]. 
     The vertical gradient calculator  404  determines the vertical gradients by implementing relation (4) below for each existing pixel:
 
 g   v   [i][j]=f[i][j]−f[i −1 ][j].   (4)
 
     For the vertical gradients, at each location (i, j), the vertical gradient is calculated by subtracting the immediate above neighboring existing pixel f[i−1] [j] from the existing pixel f[i] [j]. 
     Next, a matrix A, which is the covariance matrix of the horizontal and vertical gradients, is determined. The matrix AεR 2×2  is formed by a matrix formation unit  406  according to relation (5) below: 
     
       
         
           
             
               
                 
                   A 
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               A 
                               11 
                             
                           
                           
                             
                               A 
                               12 
                             
                           
                         
                         
                           
                             
                               A 
                               21 
                             
                           
                           
                             
                               A 
                               22 
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         [ 
                         
                             
                         
                         ⁢ 
                         
                           
                             
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     ∈ 
                                     I 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       ∈ 
                                       J 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       ( 
                                       
                                         
                                           
                                             g 
                                             H 
                                           
                                           ⁡ 
                                           
                                             [ 
                                             i 
                                             ] 
                                           
                                         
                                         ⁡ 
                                         
                                           [ 
                                           j 
                                           ] 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     ∈ 
                                     I 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       ∈ 
                                       J 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       
                                         
                                           g 
                                           H 
                                         
                                         ⁡ 
                                         
                                           [ 
                                           i 
                                           ] 
                                         
                                       
                                       ⁡ 
                                       
                                         [ 
                                         j 
                                         ] 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           g 
                                           V 
                                         
                                         ⁡ 
                                         
                                           [ 
                                           i 
                                           ] 
                                         
                                       
                                       ⁡ 
                                       
                                         [ 
                                         j 
                                         ] 
                                       
                                     
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     ∈ 
                                     I 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       ∈ 
                                       J 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       
                                         
                                           g 
                                           H 
                                         
                                         ⁡ 
                                         
                                           [ 
                                           i 
                                           ] 
                                         
                                       
                                       ⁡ 
                                       
                                         [ 
                                         j 
                                         ] 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           g 
                                           V 
                                         
                                         ⁡ 
                                         
                                           [ 
                                           i 
                                           ] 
                                         
                                       
                                       ⁡ 
                                       
                                         [ 
                                         j 
                                         ] 
                                       
                                     
                                   
                                 
                               
                             
                             
                               
                                 
                                   ∑ 
                                   
                                     i 
                                     ∈ 
                                     I 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       ∈ 
                                       J 
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       ( 
                                       
                                         
                                           
                                             g 
                                             V 
                                           
                                           ⁡ 
                                           
                                             [ 
                                             i 
                                             ] 
                                           
                                         
                                         ⁡ 
                                         
                                           [ 
                                           j 
                                           ] 
                                         
                                       
                                       ) 
                                     
                                     2 
                                   
                                 
                               
                             
                           
                         
                         ] 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     After the resulting matrix A is formed, its eigenvalues λ 1  and λ 2  and an eigenvector v 1 =[v x  v y ] T  associated with the smaller eigenvalue λ 1  (assuming λ 1 ≦λ 2 ), are calculated by an eigen calculator  408 , according to relations (6) and (7) below: 
     
       
         
           
             
               
                 
                   
                     
                       λ 
                       1 
                     
                     = 
                     
                       
                         1 
                         2 
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             A 
                             11 
                           
                           + 
                           
                             A 
                             22 
                           
                           + 
                           r 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       λ 
                       1 
                     
                     = 
                     
                       
                         1 
                         2 
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             A 
                             11 
                           
                           + 
                           
                             A 
                             22 
                           
                           - 
                           r 
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       v 
                       1 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 v 
                                 x 
                               
                             
                           
                           
                             
                               
                                 v 
                                 y 
                               
                             
                           
                         
                         ] 
                       
                       = 
                       
                         [ 
                         
                           
                             
                               
                                 2 
                                 ⁢ 
                                 
                                   A 
                                   12 
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   A 
                                   22 
                                 
                                 - 
                                 
                                   A 
                                   11 
                                 
                                 - 
                                 r 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 where 
               
               
                 
                     
                 
               
             
             
               
                 
                   r 
                   = 
                   
                     
                       
                         
                           
                             ( 
                             
                               
                                 A 
                                 11 
                               
                               - 
                               
                                 A 
                                 22 
                               
                             
                             ) 
                           
                           2 
                         
                         - 
                         
                           4 
                           ⁢ 
                           
                             A 
                             12 
                           
                           ⁢ 
                           
                             A 
                             21 
                           
                         
                       
                     
                     . 
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Relations (6) and (7) are standard closed form relations for calculating eigenvalue and eigenvectors when the input covariance matrix is of size 2×2 as in relation (5). As such, the gradient calculators  402 ,  404 , the matrix formation unit  406  and the eigen calculator  408 , together implement an edge detector that performs edge detection including edge direction detection which in this example provides the eigenvector v 1  that is proportional to the direction of a detected edge. 
     Once both eigenvalues λ 1  and λ 2  are obtained, a reliability factor α is calculated by a reliability calculator  410  according to relation (8) below: 
     
       
         
           
             
               
                 
                   
                     α 
                     = 
                     
                       min 
                       ⁡ 
                       
                         ( 
                         
                           1.0 
                           , 
                           
                             max 
                             ⁡ 
                             
                               ( 
                               
                                 0.0 
                                 , 
                                 
                                   
                                     
                                       
                                         λ 
                                         2 
                                       
                                       / 
                                       
                                         λ 
                                         1 
                                       
                                     
                                     - 
                                     
                                       RE_THR 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       1 
                                     
                                   
                                   
                                     RE_THR2 
                                     - 
                                     RE_THR1 
                                   
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     wherein the thresholds RE_THR 1  and RE_THR 2  are used for limiting the reliability factor a within the range from 0.0 to 1.0. The ratio λ 2 /λ 1  in relation (8) indicates how reliable eigenvector v 1  is as the direction of a detected edge. The reliability factor α ranges from 0.0 (not reliable) to 1.0 (very reliable). If the ratio λ 2 /λ 1  is less than or equal to RE_THR 1 , the reliability factor α is set to 0.0 (not reliable). If the ratio λ 2 /λ 1  is greater than or equal to RE_THR 2 , the reliability factor α is set to 1.0 (very reliable). When the ratio λ 2 /λ 1  is in-between RE_THR 1  and RE_THR 2 , the reliability factor α is proportional to the ratio λ 2 /λ 1  and has a value from 0.0 to 1.0. 
     The typical values for RE_THR 1  and RE_THR 2  are set to e.g., 4.0 and 12.0, respectively. If the ratio λ 2 /λ 1 , is less than or equal 4.0, then the detected edge direction according to eigenvector v 1  is not reliable (α=0). On the other hand, if the ratio λ 2 /λ 1  is greater than or equal to 12.0, the detected edge direction according to eigenvector v 1  is highly reliable (α=1). When the ratio λ 2 /λ 1  is in between 4.0 and 12.0, the reliability factor is proportional to the ratio and has a value from 0.0 to 1.0. The two threshold values were selected by the inventors as default values, based on extensive experimentation. 
     It is noted that when λ 1 ≦λ 2 , the orientation of the eigenvector v 1 =[v x  v y ] T  associated with the smaller eigenvalue λ 1  is proportional to the dominant edge direction in the window  306  whose center is the missing pixel f[y][x]( 302  in  FIG. 3 ). 
     The directional interpolator  412  determines an edge direction proportional to v 1 =[v x  v y ] T  and generates a directional interpolated value d (i.e., d[y][x]) associated with the missing pixel f[y][x] along the edge direction. At the final stage, the vertical filtered signal f v [y][x] from the V-Filter  210  ( FIG. 2 ) and the directional interpolated signal d[y][x] are mixed together using a mixer  414  based on the reliability factor α to obtain a mixed directional interpolated signal f d [y][x], according to relation (9) below:
 
 f   d   [y][x]=α·d[y][x ]+(1−α) f   v   [y][x].   (9)
 
     As such, the signal f d [y][x] is calculated by mixing between d[y][x] and f v [y][x] with a contribution ratio of αand its complement, 1−α, respectively. 
       FIG. 5  shows another view of the field  300  including a set of 13 edge direction candidates { 510 ,  511 , . . . ,  522 }associated with the missing pixel  302  in the window  306 . A method of selecting the edge direction closest to the direction of eigenvector v 1 , by the directional interpolator  412  is now described by example. Suppose an eigenvector  502  is the vector pointing to the same direction as the eigenvector v 1  whose starting point is at the missing pixel  302 . Among the set of all edge directions { 510 ,  511 , . . . ,  522 }, the edge direction  515  is the closest direction to the direction of eigenvector  502 . Therefore, the edge directed interpolated value d[y][x] in accordance with the edge direction  515 , is calculated by averaging between the existing pixels at both ends the edge direction  515  (i.e., pixels  530  and  540 ). 
     The set of 13 edge directions { 510 ,  511 , . . . ,  522 } in  FIG. 5  is by way of example, and those skilled in the art recognize that other sets with smaller or larger number of edge directions can also be used wherein the method of selecting the edge direction closest to the direction of eigenvector is adjusted accordingly. 
       FIG. 6  shows a functional block diagram of an embodiment of the bisection and strong edge detector  230  of  FIG. 2  that generates the binary map bMap. The detector  230  includes a bisection detector  602  and a strong edge detector  604 . Bisection detection and strong edge detection functions are independent and can be performed in a parallel manner. 
     The bisection detector  602  generates a binary decision bBS (0 or 1) indicating whether or not the missing pixel f[y][x] ( 302  in  FIG. 3 ) belongs to a bisection area. The bisection area is defined as the area whose pixel values can be clearly separated into two sections. An example of detecting a bisection pattern for use in conjunction with the deinterlacing is briefly described. For each missing pixel in a current input field, a window W is constructed, whose center pixel is at the considered missing pixel. A binary map is generated which includes rows of values corresponding to pixels in the window, wherein the values indicate if each element of the window is greater than the sample mean of the area surrounding the missing pixel. The number of value changes in the values in each row of the binary map is counted. It is then determined whether or not the missing pixel is within the bisection pattern based on said counts (there are two sets of value change counts corresponding to two rows). In order to maintain both the low angle edge direction detection capability and low misdetection probability, complicated areas are identified by the bisection pattern detection method. Then deinterlacing is performed. Bisection detection examples are described in the related U.S. patent application Ser. No. 11/121,815, entitled “A Method for Detecting Bisection Pattern In Deinterlacing,” filed on May 2, 2005, incorporated herein by reference. 
     Suppose the sample mean of all existing pixels within the window  306  ( FIG. 3 ) is denoted by μ. Then, a binary matrix B =[b ij ] of the same size as the window  306  is determined by comparing each pixel value to mean μ, according to relation (10) below: 
     
       
         
           
             
               
                 
                   
                     b 
                     ij 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   1 
                                 
                                 
                                   
                                     
                                       if 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         
                                           f 
                                           ⁡ 
                                           
                                             [ 
                                             i 
                                             ] 
                                           
                                         
                                         ⁡ 
                                         
                                           [ 
                                           j 
                                           ] 
                                         
                                       
                                     
                                     ≥ 
                                     μ 
                                   
                                 
                               
                               
                                 
                                   0 
                                 
                                 
                                   otherwise 
                                 
                               
                             
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             wherein 
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             i 
                           
                           ∈ 
                           I 
                         
                         = 
                         
                           { 
                           
                             
                               y 
                               - 
                               5 
                             
                             , 
                             
                               y 
                               - 
                               3 
                             
                             , 
                             
                               y 
                               - 
                               1 
                             
                             , 
                             
                               y 
                               + 
                               1 
                             
                             , 
                             
                               y 
                               + 
                               3 
                             
                             , 
                             
                               y 
                               + 
                               5 
                             
                           
                           } 
                         
                       
                       , 
                       
                         
 
                       
                       ⁢ 
                       
                         
                           
                             and 
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             j 
                           
                           ∈ 
                           J 
                         
                         = 
                         
                           
                             { 
                             
                               
                                 x 
                                 - 
                                 5 
                               
                               , 
                               
                                 x 
                                 - 
                                 4 
                               
                               , 
                               
                                 x 
                                 - 
                                 3 
                               
                               , 
                               … 
                               ⁢ 
                               
                                   
                               
                               , 
                               
                                 x 
                                 + 
                                 5 
                               
                             
                             } 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     As such, for each existing pixel location (i,j) within the window  306 , the associated binary value b ij  is set to 1 if f[i][j] is greater than or equal to the mean value of at least a plurality of the existing pixel values within the window  306  neighboring the missing pixel  302 , otherwise b ij  is set to 0. 
     For each row iεI in binary matrix B, the number of sign changes are counted along the horizontal direction according to relation (11) below: 
     
       
         
           
             
               
                 
                   
                     
                       nbSC 
                       h 
                     
                     ⁡ 
                     
                       [ 
                       i 
                       ] 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         ∈ 
                         J 
                       
                     
                     ⁢ 
                     
                       
                          
                         
                           
                             b 
                             
                               i 
                               , 
                               j 
                             
                           
                           - 
                           
                             b 
                             
                               i 
                               , 
                               
                                 j 
                                 - 
                                 1 
                               
                             
                           
                         
                          
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     Similarly, for each column jεJ, the number of sign changes are counted along the vertical direction according to relation (12) below: 
     
       
         
           
             
               
                 
                   
                     
                       nbSC 
                       v 
                     
                     ⁡ 
                     
                       [ 
                       j 
                       ] 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         ∈ 
                         I 
                       
                     
                     ⁢ 
                     
                       
                          
                         
                           
                             b 
                             
                               i 
                               , 
                               j 
                             
                           
                           - 
                           
                             b 
                             
                               
                                 i 
                                 - 
                                 1 
                               
                               , 
                               j 
                             
                           
                         
                          
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     Then, the binary decisions BS h  and BS v  in the horizontal and vertical directions are obtained in accordance to relations (13) and (14), respectively: 
     
       
         
           
             
               
                 
                   
                     BS 
                     h 
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     nbSC 
                                     h 
                                   
                                   ⁡ 
                                   
                                     [ 
                                     i 
                                     ] 
                                   
                                 
                               
                               ≤ 
                               1 
                             
                             , 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 for 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 all 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 row 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 i 
                               
                               ∈ 
                               
                                 I 
                                 ′ 
                               
                             
                             , 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     BS 
                     v 
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     nbSC 
                                     v 
                                   
                                   ⁡ 
                                   
                                     [ 
                                     j 
                                     ] 
                                   
                                 
                               
                               ≤ 
                               1 
                             
                             , 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 for 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 all 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 column 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 j 
                               
                               ∈ 
                               
                                 J 
                                 ′ 
                               
                             
                             , 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     wherein the sets I′ and J′ can be equal to, or a subset of, respectively, I={y−5,y−3,y−1,y+1,y+3,y+5} and J={x−5,x−4,x−3, . . . ,x+5}. In this description, I′={y−1,y+1} and J′={x−1,x+1}. If the number of sign changes in every row i in set I′ is not greater than 1, then the missing pixel at location (x, y) belongs to a bisection area along the horizontal direction (i.e., BS h =1). Otherwise, the missing pixel does not belong to the bisection area (i.e., BS h =0). In a similar fashion, if the number of sign changes in every column j in set J′ is not greater than 1, then the missing pixel at location (x, y) belongs to a bisection area along the vertical direction (i.e., BS v =1). Otherwise, the missing pixel does not belong to the bisection area (i.e., BS v =0). 
     In this example, the set I′ contains row indices immediately above and below the missing pixel, and the set J′ contains column indices immediately to the left and right of the missing pixel. 
     Once both the horizontal binary decision BS h  and the vertical binary decision BS v  are determined, the binary decision bBS in both directions is determined by the bisection detector  602  according to relation (15) below:
 
 bBS =AND( BS   h   , BS   v )  (15)
 
     where the AND( ) is the logical AND operation. 
     Preferably, in parallel to operation of the bisection detector  602  described above, the strong edge detector  604  detects strong edges in the input field f. Suppose the mean and approximated local variance of the window  306  whose center pixel  302  is f[y][x], are denoted by μ and σ, respectively. The approximate local variance σ is determined according to relation (16) below: 
     
       
         
           
             
               
                 
                   σ 
                   = 
                   
                     
                       1 
                       66 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           i 
                           ∈ 
                           I 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             j 
                             ∈ 
                             J 
                           
                         
                         ⁢ 
                         
                           
                              
                             
                               
                                 
                                   f 
                                   ⁡ 
                                   
                                     [ 
                                     i 
                                     ] 
                                   
                                 
                                 ⁡ 
                                 
                                   [ 
                                   j 
                                   ] 
                                 
                               
                               - 
                               μ 
                             
                              
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     Relation (16) provides calculation of an approximate local variance for the missing pixel  302 , by averaging the absolute difference between the pixel values within the window  306  and the sample mean of the missing pixel  302 . In this example, the window  306  is of size 6-by-11 pixels, such that the total number of pixels within the window  306  is 66. 
     The binary decision bSE from the strong edge detector  604  indicates whether or not the missing pixel  302  belongs to a strong edge area. The binary decision bSE is determined according to relation (17) below: 
     
       
         
           
             
               
                 
                   bSE 
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                           
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   σ 
                                 
                                 ≥ 
                                 SE_THR 
                               
                               , 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             otherwise 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     As such, the binary decision bSE is determined by using a hard threshold SE_THR. That is, if the local variance σis greater than or equal to SE_THR, then the missing pixel  302  is considered to belong to the strong edge area (bSE=1), otherwise, it is not (bSE=0). 
     After both binary decisions from detectors  602  and  604  are determined, they are input to a combiner (e.g., logical AND gate)  606  to obtain the final resulting binary decision map bMap from the detector  230 . 
     As is known to those skilled in the art, the aforementioned example architectures described above, according to the present invention, can be implemented in many ways, such as program instructions for execution by a processor, as logic circuits, as an application specific integrated circuit, as firmware, etc. 
     The present invention has been described in considerable detail with reference to certain preferred versions thereof; however, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein.