Abstract:
A motion decision value provides a dependable estimate whether motion occurs in a given region of a video image in an interlaced video sequence. The motion detection is particularly applicable in the conversion from interlaced video to progressive video. An input first is fed to an absolute value former which computes a frame difference signal from a difference between the first field and the second field in one frame. A point-wise motion detection signal is computed based on the frame difference signal and noise in the video sequence, wherein the point-wise motion detection signal is noise-adaptive. The point-wise motion detection signal is then followed by a region-wise motion detection that combines the point-wise motion detection signal with an adjacent point-wise motion detection signal delayed by one field. The motion decision value is then computed from the region-wise motion detection signal and output for further processing in the video signal processing system, such as for choosing whether the spatially interpolated video signal value or the temporally interpolated video signal value should be used for the output.

Description:
FIELD OF THE INVENTION 
     The present invention relates generally to motion detection in video sequences, and in particular to noise-adaptive motion detection in interlaced video sequences. 
     BACKGROUND OF THE INVENTION 
     In the development of current Digital TV (DTV) systems, it is essential to employ video format conversion units because of the variety of the video formats adopted in many different DTV standards worldwide. For example, the ATSC DTV standard system of North America adopted 1080×1920 interlaced video, 720×1280 progressive video, 720×480 interlaced and progressive video, etc. as its standard video formats for digital TV broadcasting. 
     Video format conversion operation is to convert an incoming video format to a specified output video format to properly present the video signal on a display device (e.g., monitor, FLCD, Plasma display) which has a fixed resolution. A proper video format conversion system is important as it can directly affect the visual quality of the video of a DTV Receiver. Fundamentally, video format conversion operation requires advanced algorithms for multi-rate system design, poly-phase filter design, and interlaced to progressive scanning rate conversion or simply deinterlacing, where deinterlacing represents an operation that doubles the vertical scanning rate of the interlaced video signal. 
     Historically, deinterlacing algorithms were developed to enhance the video quality of NTSC TV receivers by reducing the intrinsic annoying artifacts of the interlaced video signal such as a serrate line observed when there is motion between fields, line flickering, raster line visibility, and field flickering. This also applies to the DTV Receiver. 
     Elaborate deinterlacing algorithms utilizing motion detection or motion compensation allow doubling the vertical scanning rate of the interlaced video signal especially for stationary (motionless) objects in the video signal. Motion detection based deinterlacing operation can be used for analog and digital TV receivers. 
     A number of deinterlacing algorithms exist. Such deinterlacing algorithms can be categorized into two classes: 2-D (spatial) deinterlacing algorithms and 3-D (spatio-termporal) deinterlacing algorithms depending on the use of motion information embedded in consecutive interlaced video sequence. It is well-known that a 3-D deinterlacing algorithm based on motion detection provides more pleasing performance than a 2-D deinterlacing algorithm. The key point of a 3-D deinterlacing algorithm is precisely detecting motion in the interlaced video signals. 
     Existing methods disclose estimating a motion decision factor based on the frame difference signal and the sample correlation in vertical direction. These methods provide a way of reducing the visual artifacts that can arise from false motion detection by utilizing the sample correlation in vertical direction of the sampling point where the value is to be interpolated. However, such methods may not provide a true motion detection method when there are high frequency components in vertical direction. As a consequence, such methods do not increase the vertical resolution even when there is no real motion between fields. In other methods, the filtering result of the frame difference is compared with a constant value to determine the motion detection signal. However, in such methods, performance deteriorates when noise in the video sequence increases. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention addresses the above shortcomings. In one embodiment the present invention provides a method of computing a motion decision value for a video processing system, comprising the steps of: inputting a video signal with an interlaced video sequence of fields; computing a frame difference signal from a difference between a previous field and a next field in the video sequence; computing a point-wise motion detection signal based on the frame difference signal and noise in the video sequence, wherein the point-wise motion detection signal is noise-adaptive; and computing the motion decision value as a function of the point-wise motion detection signal. 
     In another aspect, the present invention provides a method of processing interlaced video signals, comprising the steps of: spatially interpolating a value of the video: signal at a given location from a video signal of at least one adjacent location in a given video field; temporally interpolating the value of the video signal at the given location from a video signal at the same location in temporally adjacent video fields; forming a motion decision value for the same location as discussed above; and mixing an output signal for the video signal at the given location from the spatially interpolated signal and the temporally interpolated signal and weighting the output signal in accordance with the motion decision value. 
     The present invention further provides systems to implement the above methods. Other embodiments, features and advantages of the present invention will be apparent from the following specification taken in conjunction with the following drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is an example diagrammatic view of two juxtaposed fields of an interlaced video sequence. 
         FIG. 2  is an example diagrammatic illustration of three fields serving to describe the deinterlacing problem according to an embodiment the present invention. 
         FIG. 3  is a more detailed view illustrating the deinterlacing process according to an embodiment of the present invention. 
         FIG. 4 . shows an example distribution of a filtered frame difference according to the present invention. 
         FIGS. 5A-F  show examples of calculating a motion decision signal according to the present invention. 
         FIG. 6  shows a functional block diagram of an embodiment of a noise-adaptive motion detection that computes a motion decision parameter according to the present invention. 
         FIG. 7  shows a functional block diagram of a deinterlacing system according to an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In one embodiment the present invention provides a robust method of estimating a noise-adaptive motion decision parameter in an interlaced video sequence. Further, the present invention provides a deinterlacing system utilizing the motion decision parameter estimation method. 
     In order to systematically describe the deinterlacing problem and the methods of the present invention, in the following description let x n  denote the incoming interlaced video field at time instant t=n, and x n (v,h) denote the associated value of the video signal at the geometrical location (v,h) where v represents vertical location and h represents horizontal location. 
     Referring to the example in  FIG. 1 , an image at t=m represents a top field  10  and an image at t=m+1 represents a bottom field  20  of an interlaced video sequence. By the definition of a interlaced video signal, the signal values of x n  are available only for the even lines, i.e., v=0, 2, 4, . . . , if x n  is the top field  10 . Similarly, the signal values of X n  are available only for the odd lines of v (i.e., V=1, 3, 5, . . . ) if x n  is the bottom field  20 . Conversely, the signal values of x n  are not available for odd lines if x n  is a top field  10  signal and the signal values of x n  are not available for even lines if x n  is a bottom field  20 . 
     Top and bottom fields  10 ,  20  are typically available in turn in time. It is assumed that the input interlaced video is corrupted by independent, identically distributed additive and stationary zero-mean Gaussian noise with variance σ 0   2 , that is, each available signal value x n (v,h) can be denoted as x n (v,h)={circumflex over (x)} n (v,h)+δ n (v,h), where {circumflex over (x)} n (v,h) is the true pixel value without noise corruption and δ n (v,h) is the Gaussian distributed noise component. It is further assumed that the noise variance σ 0   2  is already known, manually set or pre-detected by a separated noise estimation unit. σ 0  represents noise standard deviation. 
     Based upon the above description of the interlaced video signal, a deinterlacing problem can be stated as a process to reconstruct or interpolate the unavailable signal values of in each field. That is, the deinterlacing problem is to reconstruct the signal values of x n  at odd lines (v=1, 3, 5, . . . ) for top field x n  and to reconstruct the signal values of x n  at even lines (v=0, 2, 4, . . . ) for bottom field x n . 
     For clarity of description herein, the deinterlacing problem is simplified as a process which reconstructs or interpolates the unavailable signal value of x n  at the ith line where the signal values of the lines at i±1, i±3, i±5, . . . are available. More simply, deinterlacing is to interpolate the value of x n (i,h), which is not originally available. Because x n−1  and x n+1  have different sampling phase from x n , the signal values of x n−1 (i,h) and x n+1 (i,h) are available, whereby motion detection can be incorporated with the deinterlacing problem. This relation is depicted by example in  FIG. 2 , where dotted lines (or, white circles) represent “no data available” 0  and the solid lines (or, black circles) represent “available data”. 
     Referring to  FIG. 3 , a method of estimating a motion decision parameter m n (i,h) according to the present invention is now described. Fundamentally, m n (i,h) is estimated from the incoming interlaced video sequence and associated with the point-to-point degree of motion in the interlaced video sequence. The importance of estimating m n (i,h) can be easily understood from  FIGS. 2 and 3 . Assume precise motion detection information is available when interpolating x n (i,h), and no motion is detected at the spatial location (i,h), then the best interpolation for x n (i,h) is to use the value of x n−1 (i,h). This is because no motion is introduced between t=n−1 and t=n+1 at the spatial location (i,h), implying that the value of x n (i,h) would be close to the value of x n−1 (i,h). The motion decision parameter allows utilizing motion information for deinterlacing, and properly mixing the temporal information described below. 
     First, the frame difference signal D n  is computed as the difference between the fields in one frame interval as D n =|x n+1 −x n−1 | which is associated with a scene change that occurred between the fields x n+1  and x n−1 . The frame difference signal is then low pass filtered as d n =LPF(D n ) where LPF( 108  ) represents a low pass filtering process over the input video signal. 
     The M×N kernel (W M×N ) of the low pass filter, LPF( 108  ), can be expressed as 
     
       
         
           
             
               W 
               
                 M 
                 × 
                 N 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       w 
                       11 
                     
                   
                   
                     
                       w 
                       12 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       w 
                       
                         1 
                         ⁢ 
                         N 
                       
                     
                   
                 
                 
                   
                     
                       w 
                       21 
                     
                   
                   
                     
                       w 
                       22 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       w 
                       
                         2 
                         ⁢ 
                         N 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋰ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       w 
                       
                         M 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                   
                   
                     
                       w 
                       
                         M 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       w 
                       MN 
                     
                   
                 
               
               ] 
             
           
         
       
     
     where (w 11 , . . . , w MN ) represents a set of predetermined normalized coefficients (i.e., 
     
       
         
           
             
               
                 ∑ 
                 
                   p 
                   = 
                   1 
                 
                 M 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     q 
                     = 
                     1 
                   
                   N 
                 
                 ⁢ 
                 
                   w 
                   
                     p 
                     , 
                     q 
                   
                 
               
             
             = 
             
               1 
               ⁢ 
               
                 
                   ) 
                 
                 . 
               
             
           
         
       
     
     Based on the analysis in the commonly assigned patent application titled “Methods to estimate noise variance from a video sequence,” filed Nov. 17, 2004, Ser. No. 10/991,265(incorporated herein by reference), it can be seen that any value D n  in the non-motion region is a random variable with probability density function (p.d.f): 
     
       
         
           
             
               
                 p 
                 D 
               
               ⁡ 
               
                 ( 
                 y 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         1 
                         
                           
                             
                               π 
                               ⁢ 
                               
                                   
                               
                             
                           
                           ⁢ 
                           
                             σ 
                             0 
                           
                         
                       
                       ⁢ 
                       exp 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         
                           - 
                           
                             
                               y 
                               2 
                             
                             
                               4 
                               ⁢ 
                               
                                 σ 
                                 0 
                                 2 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       y 
                       &gt; 
                       0 
                     
                   
                 
                 
                   
                     
                       1 
                       
                         
                           π 
                         
                         ⁢ 
                         2 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           σ 
                           0 
                         
                       
                     
                   
                   
                     
                       y 
                       = 
                       0 
                     
                   
                 
                 
                   
                     0 
                   
                   
                     
                       y 
                       &lt; 
                       0. 
                     
                   
                 
               
             
           
         
       
     
     The filtered result d n  in the non-motion region is also a random variable with a p.d.f. p d (z), satisfying: 
     
       
         
           
             
               
                 E 
                 ⁡ 
                 
                   ( 
                   
                     
                       d 
                       n 
                     
                     ⁡ 
                     
                       ( 
                       
                         v 
                         , 
                         h 
                       
                       ) 
                     
                   
                   ) 
                 
               
               = 
               
                 
                   2 
                   
                     π 
                   
                 
                 ⁢ 
                 
                   σ 
                   0 
                 
               
             
             , 
           
         
       
     
     
       
         
           
             
               Var 
               ⁡ 
               
                 ( 
                 
                   
                     d 
                     n 
                   
                   ⁡ 
                   
                     ( 
                     
                       v 
                       , 
                       h 
                     
                     ) 
                   
                 
                 ) 
               
             
             = 
             
               
                 
                   2 
                   ⁢ 
                   
                     ( 
                     
                       π 
                       - 
                       2 
                     
                     ) 
                   
                 
                 π 
               
               ⁢ 
               
                 σ 
                 0 
                 2 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     p 
                     = 
                     1 
                   
                   M 
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       q 
                       = 
                       1 
                     
                     N 
                   
                   ⁢ 
                   
                     
                       w 
                       pq 
                       2 
                     
                     . 
                   
                 
               
             
           
         
       
     
     In one example, if the noise standard deviation is σ 0 =3.0, and the kernel is 
     
       
         
           
             
               
                 W 
                 
                   3 
                   × 
                   3 
                 
               
               = 
               
                 [ 
                 
                   
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                   
                   
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       0 
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                   
                   
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                   
                 
                 ] 
               
             
             , 
           
         
       
     
     the p.d.f. p d (z) is as shown in  FIG. 4 . 
     It should be mentioned that LPF(•) can be an all-pass filter depending on the choice of the kernel W M×N . As such, if the kernel is set as M=N=1 and w 11 =1, the LPF(•) becomes the all-pass filter and, thus, d n =D n . 
     Next, a point-wise motion detection signal is computed as:
 
i f  n ( i,h )= T   K ( d   n ( i,h ))tm (1)
 
     where T K (•) denotes a threshold function. An example implementation of T K ( 108  ) can be represented as: 
     
       
         
           
             
               
                 
                   
                     
                       T 
                       K 
                     
                     ⁡ 
                     
                       ( 
                       y 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               y 
                             
                             &gt; 
                             
                               K 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 σ 
                                 0 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     in which K is a constant value. The above function T K (•) outputs hard-switching motion detection signals, illustrated by the example curve in  FIG. 5A . 
     The threshold Kσ 0  is automatically adjusted according to the noise standard deviation of the video sequence. Robust performance can thus be obtained against noise. The value K can be determined by the error probability of detecting a non-motion pixel as a motion pixel: 
     
       
         
           
             K 
             = 
             
               
                 
                   arg 
                   z 
                 
                 ⁢ 
                 
                   
                     ∫ 
                     
                       z 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         σ 
                         0 
                       
                     
                     ∞ 
                   
                   ⁢ 
                   
                     
                       
                         p 
                         d 
                       
                       ⁡ 
                       
                         ( 
                         z 
                         ) 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       ⅆ 
                       z 
                     
                   
                 
               
               = 
               
                 e 
                 . 
               
             
           
         
       
     
     Other noise-adaptive methods can also be used for computing soft-switching motion detection signals. From the stochastic characteristic of d n (v,h), a monotonically increasing curve can be used for implementing the function T K (•) as illustrated by examples in  FIGS. 5B-F . 
     Then, the point-wise motion detection signal is filtered in spatial and temporal domains to obtain the motion decision parameter m n (i,h):
 
 m   n ( i,h )= F ( f   n ( i,h )).
 
     An example implementation of the filter F(•) is shown in  FIG. 6  and described further below. In this example, hard-switching point-wise motion detection signal is used. First, the region-wise motion detection signal is computed by a non-linear method as
 
φ n ( i,h )=f  n ( i,h )∥f  n−1 ( i− 1, h )∥f  n−1 ( i+ 1, h ),
 
     where f  n−1 (•) denotes the one field delayed motion detection signal in relation (1), where the notation ∥ denotes the logical OR operation. Other methods can be used if soft-switching point-wise motion detection signal is used, such as
 
φ n ( i,h ) =max( f    n ( i,h ), f  n−1 ( i− 1,  h ), f  n−1 ( i+ 1, h )).
 
     The region-wise motion detection signal is then low-pass filtered to form the motion decision parameter m n (i,h). The A×B kernel, Θ A×B , of the low pass-filter can be expressed as 
     
       
         
           
             
               Θ 
               
                 A 
                 × 
                 B 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       θ 
                       11 
                     
                   
                   
                     
                       θ 
                       12 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       θ 
                       
                         1 
                         ⁢ 
                         B 
                       
                     
                   
                 
                 
                   
                     
                       θ 
                       21 
                     
                   
                   
                     
                       θ 
                       22 
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       θ 
                       
                         2 
                         ⁢ 
                         B 
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋰ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       θ 
                       
                         A 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         1 
                       
                     
                   
                   
                     
                       θ 
                       
                         A 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         2 
                       
                     
                   
                   
                     ⋯ 
                   
                   
                     
                       θ 
                       AB 
                     
                   
                 
               
               ] 
             
           
         
       
     
     where (θ 11 , . . . , θ AB ) represents a set of predetermined normalized coefficients (i.e., 
                 ∑     p   =   1     A     ⁢       ∑     q   =   1     B     ⁢     θ     p   ,   q           =     1   ⁢       )     .             
For example, the kernel θ A×B  can be
 
     
       
         
           
             
               Θ 
               
                 3 
                 × 
                 3 
               
             
             = 
             
               
                 [ 
                 
                   
                     
                       0 
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       0 
                     
                   
                   
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       
                         4 
                         / 
                         8 
                       
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                   
                   
                     
                       0 
                     
                     
                       
                         1 
                         / 
                         8 
                       
                     
                     
                       0 
                     
                   
                 
                 ] 
               
               . 
             
           
         
       
     
       FIG. 6  shows a function block diagram of a motion decision calculator  100  that computes the motion decision parameter m n (i,h) using the function F(•) as described above. The motion decision calculator includes field memories  102  that provide sequencing of the interlaced values x n+1 , x n  and x n−1 . A summing junction  104  is used along with an absolute value calculator  106  to compute D n  as the difference between the fields in one frame interval as D n =|x n+1 −x n−1 | which is associated with a scene change that occurred between the fields x n+1  and x n−1 . Then a spatial LPF filter  108  is used to low-pass filter D n  to obtain d n . Threshold value Kσ 0  is applied to d n  in the noise-adaptive threshold function  110  implementing T K  above. The function F(•) is implanted in a filter  112 , in which memories  114  allow sequencing of the values f n−1 (•), and an OR junction  116  provides the region-wise motion detection signal φ n (i,h) =f  n (i,h) ∥f  n−1 (i−1,h) ∥f  n−1 (i+1,h). The region-wise motion detection signal is low-pass filtered in the LPF filter  118  to generate the motion decision parameter m n (i,h). 
     The computed motion decision parameter m n (i,h) can then used to mix a spatially interpolated signal and a temporally interpolated signal.  FIG. 7  shows a block diagram of an embodiment of an interpolator  200  for interpolating the value of x n (i,h) for the interlaced video sequence. The interpolator  200  comprises filed memories  202 , a spatial interpolator  204 , a temporal interpolator  206 , a motion decision processor  208 , and a mixer  210 . Field memories  202  sequence the interlaced values x n+1 , x n , and x n−1 . 
     The spatial interpolator  204  spatially interpolates the value of x n (i,h) by using a predetermined algorithm. The temporal interpolator  206  temporally interpolates the value of x n (i,h) by using a predetermined algorithm. The motion decision processor  208  computes the motion decision value, m n (i,h), as described above (e.g.  FIG. 6 ), representing the degree of the motion at the interpolation location (i,h). 
     Conceptually, the value of the motion decision parameter is bounded as 0≦m n (i,h) ≦1, wherein m n (i,h) =0implies “no motion” and m n (i,h) =1 implies “motion”. The mixer  210  mixes the output signal of the spatial interpolator  204  and the output signal of the temporal interpolator  206  in accordance with the motion decision value m n (i,h). Denoting x n   s (i,h) and x n   t (i,h) as the output signals of the spatial interpolator  204  and the temporal interpolator  206 , respectively, then the output signal of the mixer  210  (i.e., the interpolated signal) is represented as
 
 x   n ( i,h ) =(1− m   n ( i,h )) · x   n   t ( i,h ) + m   n ( i,h ) · x   n   s ( i,h ).tm (3)
 
     Note that x n (i,h) =x n   t (i,h) when m n (i,h) =0 (no motion), and x n (i,h) =x n   s (v,h) when m n (i,h) =1 (motion). 
     In the example of  FIG. 7 , the spatial and temporal interpolating algorithms can be selected freely because the present invention is directed to estimating the motion decision value m n (i,h) based on the noise standard deviation, and mixing of a spatially interpolated signal and a temporally interpolated signal in accordance with the estimated motion decision value. 
     Examples of the spatially interpolated signal x n   s (v,h) are
 
 x   n   s ( i,h ) =( x   n ( i− 1,  h ) + x   n ( i+ 1 ,h ))/2,
 
     which corresponds to a line average, and
 
 x   n   s ( i,h ) = x   n ( i− 1, h )
 
     which corresponds to a method known as line doubling. 
     Examples of temporally interpolated signal x n   t (v,h) are
 
 x   n   t ( i,h ) =( x   n+1 ( i,h ) + x   n−1 ( i,h ))/2
 
and
 
 x   n   t ( i,h ) = x   n−1 ( i,h ).
 
     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.