Abstract:
Presented herein are system(s), method(s), and apparatus for motion adaptive directional deinterlacing. In one embodiment, there is presented a method for interpolating a pixel for a pixel position. The method comprises receiving a plurality of pixels above the pixel position; receiving a plurality of pixels below the pixel position; and measuring gradients in a plurality of directions between the pixels above the pixel position and the pixels below the pixel position.

Description:
PRIORITY CLAIM 
     This application claims priority to Provisional Application Ser. No. 60/681,667, “Motion Adaptive Directional Deinterlacing in a Video Decoder”, by Pranav Gambhire. filed May 16, 2005. 
    
    
     FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     [Not Applicable] 
     MICROFICHE/COPYRIGHT REFERENCE 
     [Not Applicable] 
     BACKGROUND OF THE INVENTION 
     In interlacing, the pictures forming the video are captured at two distinct time intervals. The pictures forming the video comprise a plurality of ordered lines. During one of the time intervals, video content for the even-numbered lines is captured. During the other time interval, video content for the odd-numbered lines is captured. The even-numbered lines are collectively known as the top field, while the odd-numbered lines are collectively known as the bottom field. 
     On an interlaced display, the even-numbered lines are displayed on the even-numbered lines of the display during one time interval, while the odd-numbered lines are displayed on the odd-numbered lines of the display during another time interval. 
     With progressive displays, however, all of the lines of the display are displayed at one time interval. As noted above, the interlaced video pictures include even-numbered lines captured at one time interval, and odd-numbered lines captured at a second time interval. The deinterlacing process generates pictures for display during a single time interval from the interlaced video. 
     Deinterlacing by combining content from adjacent fields (known as weaving) is suitable for regions of the picture that are characterized by less object motion or lighting changes (known as inter-field motion). Displaying both the top field and bottom field at the same time interval can be problematic in cases where the video content with high-speed motion or lighting changes. Objects that are in motion are at one position when the top field is captured and another position when the bottom field is captured. If the top field and the bottom field are displayed together, a comb-like, or jagged edge affect will appear with the object. This is referred to as an artifact. 
     Alternatively, deinterlacers can generate a picture for progressive display by interpolating missing lines in a field from adjacent and surrounding lines. This is known as spatial interpolation, or “bobbing”. While spatial interpolation avoids artifacts in regions with high inter-field motion, spatial interpolation loses vertical detail and results in a blurry picture. 
     Median based deinterlacers use median tests to detect motion for each interpolated pixel. For example, where A and B denote the pixels directly above and below the interpolated pixel in the current field, and where C is the pixel in the exact spatial location in the complimentary field, median interlacers examine the median of A, B, and C. Where the median is C, the median based deinterlacers deduce a monotonic pixel gradient. The monotonic gradient is unlikely if the interpolated pixel and C are part of a moving object. Thus, the median based deinterlacers set the interpolated pixel to C. Where the median is not equal to C, median based deinterlacers set the interpolated pixel to the average of A and B. 
     The median test can be performed either independently for luma and chroma pixels. Alternatively, a median based deinterlacer can perform the median test on just the luma pixels and use the results to update both the luma and chroma components. Median based algorithms use three lines of storage and simple comparators with integer averaging. 
     However, the foregoing can introduce some unpleasant artifacts. At the edge of a moving object a hard transition is made from pixel copying to pixel averaging. Due to unequal object motion between fields and due to noise, the exact location of this transition is not constant. A pixel on the edge, which was spatially averaged in one field, could be simply copied in the next field and vice versa. This causes a buzzing flicker artifact along the edge. Additionally, the averaging function of vertically adjacent pixel implicitly assumes that the pixel gradients are vertically oriented. This is not always true at object edges where the gradients are oriented along the object&#39;s edge. This can cause a stair step pattern pixel reconstruction. 
     Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art, through comparison of such systems with embodiments of the present invention as set forth in the remainder of the present application with reference to the drawings. 
     BRIEF SUMMARY OF THE INVENTION 
     Presented herein are system(s), method(s), and apparatus for motion adaptive directional deinterlacing. 
     In one embodiment, there is presented a method for interpolating a pixel for a pixel position. The method comprises receiving a plurality of pixels above the pixel position; receiving a plurality of pixels below the pixel position; and measuring gradients in a plurality of directions between the pixels above the pixel position and the pixels below the pixel position. 
     In another embodiment, there is presented a circuit for interpolating a pixel for a pixel position. The circuit comprises a processor and a memory. The memory is connected to the processor and stores a plurality of instructions that are executable by the processor. Execution of the instructions causes receiving a plurality of pixels above the pixel position; receiving a plurality of pixels below the pixel position; and measuring gradients in a plurality of directions between the pixels above the pixel position and the pixels below the pixel position. 
     These and other advantages and novel features of the present invention, as well as details of an illustrated embodiment thereof, will be more fully understood from the following description and drawings. 
    
    
     
       BRIEF DESCRIPTION OF SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  is a block diagram of an exemplary interlaced video; 
         FIG. 2  is a block diagram of a progressive display in accordance with an embodiment of the present invention; 
         FIG. 3  is a block diagram describing luma pixels in a field; 
         FIG. 4  is a block diagram describing chroma pixels in a field; 
         FIG. 5  is a flow diagram for spatially interpolating a pixel in accordance with an embodiment of the present invention; 
         FIG. 6  is a block diagram describing pixels for spatially interpolating pixels; 
         FIG. 7  is a flow diagram for spatially interpolating a pixel in accordance with an embodiment of the present invention; 
         FIG. 8  is a block diagram describing pixels for temporally interpolating a pixel; and 
         FIG. 9  is a flow diagram for interpolating a pixel in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to  FIG. 1  is a block diagram of an exemplary video  105 . A video  105  is generated by a video camera  110  and represents images captured by the camera  110  at specific time intervals. A picture  115  represents each image. The pictures  115  comprise two-dimensional grids of pixels  120 , wherein each pixel in the grid corresponds to a particular spatial location of an image captured by the camera. The grids include chroma red pixels Cr, chroma blue pixels Cb, and luma pixels Y. 
     Each pixel  120  stores a color value describing the spatial location corresponding thereto. Accordingly, each pixel  120  is associated with two spatial parameters (x,y) as well as a time parameter. An interlaced camera, scans the rows  120 (−,y) of a picture  115  in odd/even alternating order. The even numbered lines are scanned at one time, t 0 , followed by the odd numbered lines scanned at another time, t 1 . The partial images of the even number lines are known as top fields  115   a , while the partial images of the odd numbered lines are referred to as bottom fields  115   b.    
     Referring now to  FIG. 2 , there is illustrated a block diagram describing an exemplary progressive display  200 , in accordance with an embodiment of the present invention. The progressive display  200  comprises a video decoder  205 , a deinterlacer  210 , and a screen  215 . When the top field  115   a  and bottom field  115   b  are displayed at the rate of capture, motion picture is simulated. For example, where the fields  115   a / 115   b  are captured at times t 0  . . . tn, an interlaced display device can display the fields  115   a / 115   b  at corresponding times td+0 . . . td+n. The foregoing simulates the motion appearing from the vantage point of the camera at the times t 0  . . . tn. 
     The progressive display displays all of the lines  120 (−, y) of a picture  115  during each display interval on the screen  115 , and may have a display rate that is half the field capture rate of the video camera. For example, the progressive display  200  may display an entire picture  115  at time intervals td, td+2, td+4, . . . . Where an interlaced video is to be displayed by the progressive display  200 , it is possible that only one field  115   a / 115   b  corresponds to the display time. For example, at display time td+2, top field  115   a  captured at t 2  is the only field corresponding to the time. Accordingly, the deinterlacer  210  generates the pixels for the odd-numbered lines  120 (−, 2y+1) for the picture  115  to be displayed at td+2. 
     The deinterlacer  210  generates the pixel for the odd-numbered lines using the top field  115   a , the bottom field  115   b ′ immediately preceding the top field  115   a , and/or the bottom field  115   b ″ immediately following the top field  115   a . The deinterlacer  210  generates the pixels for the odd-numbered lines using a blended average between spatial and temporal interpolations. Alternatively, the deinterlacer  210  can generate even-numbered lines where a bottom field corresponds to the time period of display. 
     Directional Spatial Averaging: 
     Referring now to  FIG. 3 , there is illustrated a block diagram describing luma pixels in a field  115   a / 115   b .  FIG. 4  is a block diagram describing chroma pixels in a field  115   a / 115   b . Object edges through the reconstructed pixel can be at any angle to horizontal. The spatial averaging mechanism estimates the edge angle by comparing pixel values at several orientations through the reconstructed pixel. Five pixels are examined from the line above and below the pixel as shown in  FIGS. 3-4 . Both luma and chroma components are used to determine the direction of the spatial averaging. 
     The solid lines are the edge orientations that pass through the center of the interpolated pixel. The dotted lines are the edge orientations that graze the interpolated pixel without passing through its center. The algorithm identifies the most likely edge orientation by examining absolute pixel differences along each of these (both solid and dotted) lines. 
     Let A i  (i=−2, 2) denote the five pixels from the line below the reconstructed line that surround the reconstructed point. Similarly let B i  (i=−2, 2) denote the five pixels from the line above the reconstructed line that surround the reconstructed point. The absolute pixel difference between a point A i  and B −j  is denoted as d ij . If the object edge passes through or close to A m B −n  then d mn  will have the smallest magnitude among all d ij . The reconstructed point will hence be a good approximation if it is a spatial average of the points A m  and B −n . If the reconstructed point is not on an edge, then all the d ij s will be very close to each other and a spatial average between A 0  and B 0  will produce an acceptable result for the reconstructed point. 
     Referring now to  FIG. 5 , there is illustrated a flow diagram for spatially interpolating a pixel. The flow diagram will be described with reference to  FIGS. 3 and 4 . 
     At  505 , the luma values and chroma values for the five pixels above A and below B the reconstructed pixel are read in. If the reconstructed pixel is in the first line, the above line B is used twice. If the reconstructed line is the last line, the bottom line A is used twice. 
     At  510 , the absolute differences d ij =|A i −B −j| for all (i&lt; 0 and j&gt;0) and for (i&gt;0 and j&lt;0) i.e., along all the lines (both solid and dotted) of  FIGS. 3 and 4 . At the left vertical edge set A −2 , A −1  both equal A 0  and B −2 , B −1  both equal B 0 . Similarly at the right vertical edge set A 1 , A 2  both equal A 0  and B 1 , B 2  both equal B 0 . 
     At  515 , the orientation mn is found, such that d mn  is the smallest. At  520 , a weighted average of pixels in multiple directions is calculated. The weighted average is calculated as follows:
         a. m==−2: If n==2, calculate the reconstructed pixel luma value as Y=(A −2 +A −1 +B 1 +B 2 +1)/4. Otherwise n==1 calculate Y=3((A −2 +B 1 +1)/2+(A −1 +B 0 +1)/2+3)/4.   b. m==−1: If n==1 then Y=(A −1 +B 1 +1)/2. Otherwise n==2, Y=(A −1 +B 2 +1)/2.   c. m==0: Y=(A 0 +B 0 +1)/2.   d. m==1: If n==−1 then Y=(A 1 +B− 1 +1)/2. Otherwise n==2, Y=(A 1 +B− 2 +1)/2.   e. m==2: If n==−2, calculate the reconstructed pixel luma value as Y=(A 2 +A 1 +B− 1 +B− 2 +1)/4. Otherwise n==−1 calculate Y=3(A 2 +B− 1 +1)/2+(A 1 +B 0 +1)/2+3)/4.       

     At  525 , the vertical average pixel value is calculated, Y vert =(A 0 +B 0 +1)/2. At  530 , if the pixel being reconstructed is chroma,  520 - 525  are repeated. At  535 , spatial interpolation value for the reconstructed pixel is the weighted average: I sp =(3Y+Y vert )/4. If the reconstructed pixel is a chroma sampling position, the chroma values using chroma components from  525  in this equation are calculated. 
     Four Line Spatial Interpolation 
     Alternatively, four-line spatial interpolation can be performed. An edge can be making any angle between 0 and 90 degrees to the horizontal. This entire scale can be partitioned into four non-uniform ranges (0-11.5), (11.5-44.5), (44.5-57.5), (57.5-80.5), and (80.5-90). Each range of angles is associated with a separate two or four tap directional spatial filter. The results of the directional filters are a weighted averaged with the vertical pixel interpolation to prevent the buzz from hard filtering decisions. 
     Referring now to  FIG. 6 , there is illustrated a block diagram describing pixels for spatially interpolating a reconstructed pixel. The pixels include five pixels A −2  . . . A 2  in the line above the reconstructed pixel, another pixel that is three lines above the reconstructed pixel P 0 , five pixels B −2  . . . B 2  that are below the reconstructed pixel, and another pixel that is three lines below the reconstructed pixel, Q 0 . 
     Referring now to  FIG. 7 , there is illustrated a flow diagram for spatial interpolation using four lines. At  705 , the pixel gradients in the horizontal and vertical directions around a pixel to be reconstructed are examined. The gradients are calculated as:
 
 dx= ( A   −1   −A   1 )/2+( B   −1   −B   1 )/2
 
 dy= ( A   −1 /2 +A   0   +A   1 /2)/2−( B   −1 /2 +B   0   +B   1 /2)/2
 
     At  710 , a particular range is selected. The exact angle made with the horizontal is given be arctan (|dy|/|dx|), when dx is non-zero. If dx is zero, the edge is vertical. Rather than the actual value of the angle, which of the non-uniform ranges that the angle belongs to is determined. By determining tan(a) for all the a&#39;s that form the range boundaries, the following decision procedure is arrived at: 
                                               GradientSign = sign(dx*dy)           scaledDy = 500*dy;           If (scaledDy &lt; 99*dx)             direction = North;           Else if (scaledDy &lt; 334*dx)             direction = (gradientSign &gt; 0) ? NorthNorthEast :           NorthNorthWest;           Else if (scaledDy &lt; 748*dx)             direction = (gradientSign &gt; 0) ? NorthEast :           NorthWest;           Else if (scaledDy &lt; 2514*dx)             direction = (gradientSign &gt; 0) ? NorthEastEast :           NorthWestWest;           Else             direction = East;                        
At  715 , a filter corresponding to the direction selected during  710  is applied. The filters for each of the directions is as follows:
 
     
       
         
               
               
             
           
               
                   
               
             
             
               
                   
                 North: 
               
               
                   
                  dirInterpolation = (35A 0  + 35B 0  − 3P 0  − 3Q 0  ) / 64 
               
               
                   
                 East: 
               
               
                   
                  dirInterpolation = (A 0  + B 0 ) / 2 
               
               
                   
                 NorthEast: 
               
               
                   
                  dirInterpolation = (A 1  + B −1 ) / 2 
               
               
                   
                 NorthWest: 
               
               
                   
                  dirInterpolation = (A −1  + B 1 ) / 2 
               
               
                   
                 NorthNorthEast: 
               
               
                   
                  dirInterpolation = (A 1  + A 0  + B 0  + B −1 ) / 4 
               
               
                   
                 NorthNorthWest: 
               
               
                   
                  dirInterpolation = (A 0  + A −1  + B 0  + B 1 ) / 4 
               
               
                   
                 NorthEastEast: 
               
               
                   
                  dirInterpolation = (A 2  + A 1  + B −1  + B −2 ) / 4 
               
               
                   
                 NorthWestWest: 
               
               
                   
                  dirInterpolation = (A −2  + A −1  + B 1  + B 2 ) / 4 
               
               
                   
               
             
          
         
       
     
     At  720 , the final spatial interpolation is a weighted average of the directional filter and the north filter:
 
 I   SP =(3*dirInterpolation+((35 A   0 +35 B   0 −3 P   0 −3 Q   0 )/64))/4
 
Temporal Interpolation
 
     In the absence of object motion, a pixel can be accurately reconstructed by copying over its value from a complementary field. Object motion can be deduced at the pixel level by examining the median of: (1) the pixel directly above the reconstructed pixel; (2) the pixel at the same location as the reconstructed pixel in the complementary field; and (3) the pixel directly below the reconstructed pixel. 
     Where T i  denotes the pixel being reconstructed, A i  denotes the pixel on the scan line immediately below T i , B i  denotes the pixel immediately above T i  and C i  denotes the pixel at the same location as T i  but in the other field, if median (A i , B i , C i ) is equal to C i  the pixel T i  is not likely to be on a moving object edge and C i  is a good approximation for T i . However if median (A i , B i , C i ) does not equal C i , then T i  is likely to be on a moving edge and is best approximated using spatial interpolation. 
     The median is calculated for both luma and chroma components. If the median test indicates motion for ANY component, the reconstructed pixel is taken to be on a moving edge and is spatially interpolated. 
     It is likely that the reconstructed pixel to the left of T i , T i−1 , was a copy of C i−1  and T i  is a spatial average and vice versa. On slow moving object edges, the same pixel may alternate between spatial and temporal interpolations on successive fields. This causes the edges to be blurred on some reconstructed frames and sharp on others, thus causing a flickering artifact. Avoiding a hard transition between spatial and temporal interpolation can minimize this flicker. Examining the medians at two neighboring pixels on each side of reconstructed pixel and then taking a weighted average of the motion detection decisions, avoids these hard transitions. 
     Referring now to  FIG. 8 , there is illustrated a block diagram describing an exemplary pixels from a current field a complimentary field. The pixels A −2 , . . . A 2 , and B −2 , . . . B 2  are from the current field, while pixels C −2 , . . . C 2  are from the complimentary field. 
       FIG. 9  is a flow diagram for temporal interpolation in accordance with an embodiment of the present invention.  FIG. 9  will be described with reference to  FIG. 8 . At  905 , the luma and chroma values of the five pixels above A −2 , . . . A 2  and below B −2 , . . . B 2  the pixel to be reconstructed from the current field are read in, as well as the values of the two pixels C 0  on either side from the complementary field. At  910 , i is set equal to −2 and score is set equal to 0. At  915 , for each i=−2, . . . 2, the medians (A i , B i , C i ) for each component are examined. If at  915 , (A i , B i , C i ) do not exist because of the vertical edge of the picture, at  917 , the Score i  is set equal to Score 0 . If at  920 , the median (A i , B i , C i ) is equal to C i  for either the luma component or any one of the chroma components, then Score i =1 at  925 . Otherwise at  930  Score i =0. At  940 , the weighted average of the motion scores is calculated based on the formula below:
 
Motion=[Score −2 +4Score −1 +6Score 0 +4Score 1 +Score 2 ]
 
     At  945 , the pixel value is then reconstructed as the blended average between the C i  and I sp  according to the formula below:
 
Recon=[Motion*I sp +(16−Motion)*C i ]/16
 
     The embodiments described herein may be implemented as a board level product, as a single chip, application specific integrated circuit (ASIC), or with varying levels of the decoder system integrated with other portions of the system as separate components. The degree of integration of the decoder system will primarily be determined by the speed and cost considerations. Because of the sophisticated nature of modern processor, it is possible to utilize a commercially available processor, which may be implemented external to an ASIC implementation. Alternatively, if the processor is available as an ASIC core or logic block, then the commercially available processor can be implemented as part of an ASIC device wherein certain functions can be implemented in firmware. In one embodiment, a deinterlacer can be incorporated into a single integrated circuit. 
     Although the embodiments described herein are described with a degree of particularity, it should be noted that changes, substitutions, and modifications can be made with respected to the embodiments without departing from the spirit and scope of the present application. Accordingly, the present application is only limited by the following claims and equivalents thereof.