The invention relates motion estimation in video and film signal processing, in particular, to a technique for assessing the reliability of motion vectors.
Gradient motion estimation is one of three or four fundamental motion estimation techniques and is well known in the literature (references 1 to 18). More correctly called xe2x80x98constraint equation based motion estimationxe2x80x99 it is based on a partial differential equation which relates the spatial and temporal image gradients to motion.
Gradient motion estimation is based on the constraint equation relating the image gradients to motion. The constraint equation is a direct consequence of motion in an image. Given an object, xe2x80x98object(x, y)xe2x80x99, which moves with a velocity (u, v) then the resulting moving image, I(x, y, t) is defined by Equation 1;
I(x, y, t)=object(xxe2x88x92ut, yxe2x88x92vt)xe2x80x83xe2x80x83Equation 1
This leads directly to the contraint equation, Equation 2;                                           u            ·                                                            ∂                  I                                ⁢                                  xe2x80x83                                ⁢                                  (                                      x                    ,                    y                    ,                    t                                    )                                                            ∂                x                                              +                      v            ·                                                            ∂                  I                                ⁢                                  xe2x80x83                                ⁢                                  (                                      x                    ,                    y                    ,                    t                                    )                                                            ∂                y                                              +                                                    ∂                I                            ⁢                              xe2x80x83                            ⁢                              (                                  x                  ,                  y                  ,                  t                                )                                                    ∂              t                                      =                                                            ∂                object                            ⁢                              xe2x80x83                            ⁢                              (                                  x                  ,                  y                                )                                                    ∂              t                                =          0                                    Equation        ⁢                  xe2x80x83                ⁢        2            
where, provided the moving object does not change with time (perhaps due to changing lighting or distortion) then ∂object/∂t=0. This equation is, perhaps, more easily understood by considering an example. Assume that vertical motion is zero, the horizontal gradient is +2 grey levels per pixel and the temporal gradient is xe2x88x9210 grey levels per field. Then the constraint equation says that the ratio of horizontal and temporal gradients implies a motion of 5 pixels/field. The relationship between spatial and temporal gradients is summarised by the constraint equation.
To use the constraint equation for motion estimation it is first necessary to estimate the image gradients; the spatial and temporal gradients of brightness. In principle these are easily calculated by applying straightforward linear horizontal, vertical and temporal filters to the image sequence. In practice, in the absence of additional processing, this can only really be done for the horizontal gradient. For the vertical gradient, calculation of the brightness gradient is confused by interlace which is typically used for television pictures; pseudo-interlaced signals from film do not suffer from this problem. Interlaced signals only contain alternate picture lines on each field. Effectively this is vertical sub-sampling resulting in vertical aliasing which confuses the vertical gradient estimate. Temporally the situation is even worse, if an object has moved by more than 1 pixel in consecutive fields, pixels in the same spatial location may be totally unrelated. This would render any temporal gradient estimate meaningless. This is why gradient motion estimation cannot, in general, measure velocities greater than 1 pixel per field period (reference 8).
Prefiltering can be applied to the image sequence to avoid the problem of direct measurement of the image gradients. If spatial low pass filtering is applied to the sequence then the effective size of xe2x80x98pixelsxe2x80x99 is increased. The brightness gradients at a particular spatial location are then related for a wider range of motion speeds. Hence spatial low pass filtering allows higher velocities to be measured, the highest measurable velocity being determined by the degree of filtering applied. Vertical low pass filtering also alleviates the problem of vertical aliasing caused by interlace. Alias components in the image tend to be more prevalent at higher frequencies. Hence, on average, low pass filtering disproportionately removes alias rather than true signal components. The more vertical filtering that is applied the less is the effect of aliasing. There are, however, some signals in which aliasing extends down to zero frequency. Filtering cannot remove all the aliasing from these signals which will therefore result in erroneous vertical gradient estimates and, therefore, incorrect estimates of the notion vector. One advantage of this invention is its ability to detect erroneous motion estimates due to vertical aliasing.
Prefiltering an image sequence results in blurring. Hence small details in the image become lost. This has two consequences, firstly the velocity estimate becomes less accurate since there is less detail in the picture and secondly small objects cannot be seen in the prefiltered signal. To improve vector accuracy hierarchical techniques are sometimes used. This involves first calculating an initial, low accuracy, motion vector using heavy prefiltering, then refining this estimate to higher accuracy using less prefiltering. This does, indeed, improve vector accuracy but it does not overcome the other disadvantage of prefiltering, that is, that small objects cannot be seen in the prefiltered signal, hence their velocity cannot be measured. No amount of subsequent vector refinement, using hierarchical techniques, will recover the motion of small objects if they are not measured in the first stage. Prefiltering is only advisable in gradient motion estimation when it is only intended to provide low accuracy motion vectors of large objects.
Once the image gradients have been estimated the constraint equation is used to calculate the corresponding motion vector. Each pixel in the image gives rise to a separate linear equation relating the horizontal and vertical components of the motion vector and the image gradients. The image gradients for a single pixel do not provide enough information to determine the motion vector for that pixel. The gradients for at least two pixels are required. In order to minimise errors in estimating the motion vector it is better to use more than two pixels and find the vector which best fits the data from multiple pixels. Consider taking gradients front 3 pixels. Each pixel restricts the motion vector to a line in velocity space. With two pixels a single, unique, motion vector is determined by the intersection of the 2 lines. With 3 pixels there are 3 lines and, possibly, no unique solution. This is illustrated in FIG. 1. The vectors E1 to E3 are the error from the best fitting vector to the constraint line for each pixel.
One way to calculate the best fit motion vector for a group of neighbouring pixels is to use a least mean square method, that is minimising the sum of the squares of the lengths of the error vectors E1 to E3 FIG. 1). The least mean square solution for a group of neighbouring pixels is given by the solution of Equation 3;   "AutoLeftMatch"                                                                        [                                                                                                    σ                        xx                        2                                                                                                            σ                        xy                        2                                                                                                                                                σ                        xy                        2                                                                                                            σ                        yy                        2                                                                                            ]                            ·                              [                                                                                                    u                        0                                                                                                                                                v                        0                                                                                            ]                                      =                          -                              [                                                                                                    σ                        xt                        2                                                                                                                                                σ                        yt                        2                                                                                            ]                                              ⁢                      
                    ⁢          where          ⁢                      xe2x80x83                    ⁢                      
                    ⁢                      xe2x80x83                    ⁢                                                    σ                xx                2                            =                              ∑                                  xe2x80x83                                ⁢                                                                            ∂                      I                                                              ∂                      x                                                        ·                                                            ∂                      I                                                              ∂                      x                                                                                            ,                          xe2x80x83                        ⁢                                          σ                xy                2                            =                              ∑                                                                                                    ∂                        I                                                                    ∂                        x                                                              ·                                                                  ∂                        I                                                                    ∂                        y                                                                              ⁢                                      xe2x80x83                                    ⁢                  etc                                                                                          Equation          ⁢                      xe2x80x83                    ⁢          3                    
where (u0, v0) is the best fit motion vector and the summations are over a suitable region. This is an example of the well known technique of linear regression analysis detailed, for example, in reference 19 and many other texts. The (direct) solution of equation 3 is given by Equation 4;                               [                                                                      u                  0                                                                                                      v                  0                                                              ]                =                              1                                                            σ                                      xx                    ⁢                                          xe2x80x83                                                        2                                ⁢                                  σ                                      yy                    ⁢                                          xe2x80x83                                                        2                                            -                              σ                                  xy                  ⁢                                      xe2x80x83                                                  4                                              ⁡                      [                                                                                                                              σ                        xy                        2                                            ⁢                                              σ                        yt                        2                                                              -                                                                  σ                        yy                        2                                            ⁢                                              σ                        xt                        2                                                                                                                                                                                                            σ                        xy                        2                                            ⁢                                              σ                        xt                        2                                                              -                                                                  σ                        xx                        2                                            ⁢                                              σ                        yt                        2                                                                                                                  ]                                              Equation        ⁢                  xe2x80x83                ⁢        4            
Analysing small image regions produces detailed vector fields of low accuracy and vice versa for large regions. There is little point in choosing a region which is smaller than the size of the prefilter since the pixels within such a small region are not independent.
Typically, motion estimators generate motion vectors on the same standard as the input image sequence. For motion compensated standards converters, or other systems performing motion compensated temporal interpolation, it is desirable to generate motion vectors on the output image sequence standard. For example when converting between European and American television standards the input image sequence is 625 line 50 Hz (interlaced) and the output standard is 525 line 60 Hz (interlaced). A motion compensated standards converter operating on a European input is required to produce motion vectors on the American output television standard.
The direct implementation of gradient motion estimation, discussed herein in relation to FIGS. 2 and 3, can give wildly erroneous results. Such behaviour is extremely undesirable. These problems occur when there is insufficient information in a region of an image to make an accurate velocity estimate. This would typically arise when the analysis region contained no detail at all or only the edge of an object. In such circumstances it is either not possible to measure velocity or only possible to measure velocity normal to the edge. It is attempting to estimate the complete motion vector, when insufficient information is available, which causes problems. Numerically the problem is caused by the 2 terms in the denominator of equation 4 becoming very similar resulting in a numerically unstable solution for equation 3.
A solution to this problem of gradient motion estimation has been suggested by Martinez (references 11 and 12). The matrix in equation 3 (henceforth denoted xe2x80x98Mxe2x80x99) may be analysed in terms of its eigenvectors and eigenvalues. There are 2 eigenvectors, one of which points parallel to the predominant edge in the analysis region and the other points normal to that edge. Each eigenvector has an associated eigenvalue which indicates how sharp the image is in the direction of the eigenvector. The eigenvectors and values are defined by Equation 5;                                          M            ·                          e              t                                =                                                    λ                t                            ⁢                              e                i                            ⁢                              xe2x80x83                            ⁢              i                        ∈                          {                              1                ,                                  xe2x80x83                                ⁢                2                            }                                      ⁢                  
                ⁢                                            where;                        ⁢                          xe2x80x83                        ⁢            M                    =                      [                                                                                σ                    xx                    2                                                                                        σ                    xy                    2                                                                                                                    σ                    xy                    2                                                                                        σ                    yy                    2                                                                        ]                                              Equation        ⁢                  xe2x80x83                ⁢        5            
The eigenvectors ei are conventionally defined as having length l, which convention is adhered to herein.
In plain areas of the image the eigenvectors have essentially random direction (there are no edges) and both eigenvalues are very small (there is no detail). In these circumstances the only sensible vector to assume is zero. In parts of the image which contain only an edge feature the eigenvectors point normal to the edge and parallel to the edge. The eigenvalue corresponding to the normal eigenvector is (relatively) large and the other eigenvalue small. In this circumstance only the motion vector normal to the edge can be measured. In other circumstances, in detailed parts of the image where more information is available, the motion vector may be calculated using Equation 4.
The motion vector may be found, taking into account Martinez"" ideas above, by using Equation 6;                               [                                                                      u                  0                                                                                                      v                  0                                                              ]                =                              -                          (                                                                                          λ                      1                                                                                      λ                        1                        2                                            +                                              n                        1                        2                                                                              ⁢                                      xe2x80x83                                    ⁢                                      e                    1                                    ⁢                                      e                    1                    t                                                  +                                                                            λ                      2                                                                                      λ                        2                        2                                            +                                              n                        2                        2                                                                              ⁢                                      xe2x80x83                                    ⁢                                      e                    2                                    ⁢                                      e                    2                    t                                                              )                                ·                      [                                                                                σ                    xt                    2                                                                                                                    σ                    yt                    2                                                                        ]                                              Equation        ⁢                  xe2x80x83                ⁢        6            
where superscript t represents the transpose operation. Here n1 and n2 are the computational or signal noise involved in calculating xcexE1 and xcex2 respectively. In practice n1≈n2, both being determined by, and approximately equal to, the noise in the coefficients of M. When xcex1 and xcex2,  less than  less than n then the calculated motion vector is zero; as is appropriate for a plain region of the image. When xcex11 less than  less than n and xcex2 less than  less than n then the calculated motion vector is normal to the predominant edge in that part of the image. Finally if xcex1, xcex2 greater than  greater than n then equation 6 becomes equivalent to equation 4. As signal noise, and hence n, decreases then equation 6 provides an increasingly more accurate estimate of the motion vectors as would be expected intuitively.
In practice calculating motion vectors using the Martinez technique involves replacing the apparatus of FIG. 3, below, with more complex circuitry. The direct solution of equation 6 would involve daunting computational and hardware complexity. It can, however, be implemented using only two-point, pre-calculated, look up tables and simple arithmetic operations.
A block diagram of a direct implementation of gradient motion estimation is shown in FIGS. 2 and 3.
The apparatus shown schematically in FIG. 2 performs filtering and calculation of gradient products and their summations. The apparatus of FIG. 3 generates motion vectors from the sums of gradient products produced by the apparatus of FIG. 2. The horizontal (10) and vertical (12) low pass filters in FIG. 2 perform spatial prefiltering as discussed above. The cut-off frequencies of {fraction (1/32)}nd band horizontally and {fraction (1/16)}th band vertically allow motion speeds up to (at least) 32 pixels per field to be measured. Different cut-off frequencies could be used if a different range of speeds is required. The image gradients are calculated by three temporal and spatial differentiating filters (16,17,18).
The vertical/temporal interpolation filters (20) convert the image gradients, measured on the input standard, to the output standard. Typically the vertical/temporal interpolators (20) are bilinear interpolators or other polyphase linear interpolators. Thus the output motion vectors are also on the output standard. The interpolation filters are a novel feature (subject of the applicant""s co-pending UK Patent Application filed on identical date hereto) which facilitates interfacing the motion estimator to a motion compensated temporal interpolator. Temporal low pass filtering is normally performed as part of (all 3 of) the interpolation filters. The temporal filter (14) has been re-positioned in the processing path so that only one rather than three filters are required. Note that the filters prior (10,12,14) to the multiplier array can be implemented in any order because they are linear filters. The summation of gradient products, specified in equation 3, are implemented by the low pass filters (24) following the multiplier array. Typically these filters (24) would be (spatial) running average filters, which give equal weight to each tap within their region of support. Other lowpass filters could also be used at the expense of more complex hardware. The size of these filters (24) determines the size of the neighbourhood used to calculate the best fitting motion vector. Examples of filter coefficients which may be used can be found in the example.
A block diagram of apparatus capable of implementing equation 6 and which replaces that of FIG. 3, is shown in FIGS. 4 and 5.
Each of the xe2x80x98eigen analysisxe2x80x99 blocks (30), in FIG. 4, performs the analysis for one of the two eigenvectors. The output of the eigen-analysis is a vector (with x and y components) equal to si=ei{square root over (xcexi+L /(xcexi2+L +n2+L ))}. These xe2x80x98sxe2x80x99 vectors are combined with vector ("sgr"xt2, "sgr"yt2) (denoted c in FIG. 4), according to equation 6, to give the motion vector according to the Martinez technique.
The eigen analysis, illustrated in FIG. 5, has been carefully structured so that it can be implemented using lookup tables with no more than 2 inputs. This has been done since lookup tables with 3 or more inputs would be impracticably large using today""s technology. The implementation of FIG. 5 is based on first normalising the matrix M by dividing all its elements by ("sgr"xx2+"sgr"yy2). This yields a new matrix, N, with the same eigenvectors (e1 and e2) and different (but related) eigenvalues (X1 and X2). The relationship between M, N and their eigenvectors and values is given by Equation 7.   "AutoLeftMatch"                                          N            =                                                            1                                                            σ                      xx                      2                                        +                                          σ                      yy                      2                                                                      ⁢                                  xe2x80x83                                ⁢                M                            =                              [                                                                                                                              σ                          xx                          2                                                                                                      σ                            xx                            2                                                    +                                                      σ                            yy                            2                                                                                                                                                                                        σ                          xy                          2                                                                                                      σ                            xx                            2                                                    +                                                      σ                            yy                            2                                                                                                                                                                                                                            σ                          xy                          2                                                                                                      σ                            xx                            2                                                    +                                                      σ                            yy                            2                                                                                                                                                                                        σ                          yy                          2                                                                                                      σ                            xx                            2                                                    +                                                      σ                            yy                            2                                                                                                                                              ]                                              ⁢                      
                    ⁢                                    M              ·                              e                i                                      =                                          λ                i                            ·                              e                i                                              ⁢                      
                    ⁢                                    N              ·                              e                i                                      =                                          χ                i                            ·                              e                i                                              ⁢                      
                    ⁢                                    λ              i                        =                                          (                                                      σ                    xx                    2                                    +                                      σ                    yy                    2                                                  )                            ⁢                              xe2x80x83                            ⁢                              χ                i                                              ⁢                      
                    ⁢                                    n              λ                        =                                          (                                                      σ                    xx                    2                                    +                                      σ                    yy                    2                                                  )                            ⁢                              xe2x80x83                            ⁢                              n                χ                                                                          Equation          ⁢                      xe2x80x83                    ⁢          7                    
Matrix N is simpler than H as it contains only two independent values, since the principle diagonal elements (N1,1, N2,2) sum to unity and the minor diagonal elements (N1,2, N2,1) are identical. The principal diagonal elements may be coded as ("sgr"xx2xe2x88x92"sgr"yy2)/("sgr"xx2+"sgr"yy2) since Equation 8;   "AutoLeftMatch"                                                                                          N                                      1                    ,                    1                                                  =                                                      1                    2                                    ⁢                                      xe2x80x83                                    ⁢                                      (                                          1                      +                                              (                                                                                                            σ                              xx                              2                                                        -                                                          σ                              yy                              2                                                                                                                                          σ                              xx                              2                                                        +                                                          σ                              yy                              2                                                                                                      )                                                              )                                                                                                                                            N                                      2                    ,                    2                                                  =                                                      1                    2                                    ⁢                                      xe2x80x83                                    ⁢                                      (                                          1                      -                                              (                                                                                                            σ                              xx                              2                                                        -                                                          σ                              yy                              2                                                                                                                                          σ                              xx                              2                                                        +                                                          σ                              yy                              2                                                                                                      )                                                              )                                                                                                            Equation          ⁢                      xe2x80x83                    ⁢          8                    
Hence lookup tables 1 and 2 have all the information they require to find the eigenvalues and vectors of N using standard techniques. It is therefore straightforward to precalculate the contents of these lookup tables. Lookup table 3 simply implements the square root function. The key features of the apparatus shown in FIG. 5 are that the eigenanalysis is performed on the normalised matrix, N, using 2 input lookup tables (1 and 2) and the eigenvalue analysis (from table 2) is rescaled to the correct value using the output of table 3.
The gradient motion estimator described above is undesirably complex. The motion estimator is robust to images containing limited information but FIGS. 4 and 5 show the considerable complexity involved. The situation is made worse by the fact that many of the signals have a very wide dynamic range making the functional blocks illustrated much more difficult to implement.
A technique which yields considerable simplifications without sacrificing performance based on normalising the basic constraint equation (equation 2) to control the dynamic range of the signals is the subject of the applicant""s co-pending application filed on identical date hereto. As well as reducing dynamic range this also makes other simplifications possible.
Dividing the constraint equation by the modulus of the gradient vector yields a normalised constraint equation i.e. Equation 9:   "AutoLeftMatch"                                                                                          u                  ⁢                                      xe2x80x83                                    ⁢                                                            ∂                      I                                                              ∂                      x                                                                      +                                  v                  ⁢                                      xe2x80x83                                    ⁢                                                            ∂                      I                                                              ∂                      y                                                                                                  "LeftBracketingBar"                                  ▽                  ⁢                                      xe2x80x83                                    ⁢                  I                                "RightBracketingBar"                                      =                          -                                                                    ∂                    I                                                        ∂                    t                                                                    "LeftBracketingBar"                                      ▽                    ⁢                                          xe2x80x83                                        ⁢                    I                                    "RightBracketingBar"                                                              ⁢                      
                    ⁢                                    where              ⁢                              :                            ⁢                              xe2x80x83                            ⁢              ▽              ⁢                              xe2x80x83                            ⁢              I                        =                                                                                [                                                                                                                                                      ∂                              I                                                                                      ∂                              x                                                                                                                                                                                                                                      ∂                              I                                                                                      ∂                              y                                                                                                                                            ]                                    ⁢                                      xe2x80x83                                    and                                ⁢                                  xe2x80x83                                ⁢                                  "LeftBracketingBar"                                      ▽                    ⁢                                          xe2x80x83                                        ⁢                    I                                    "RightBracketingBar"                                            =                                                                                          (                                                                        ∂                          I                                                                          ∂                          x                                                                    )                                        2                                    +                                                            (                                                                        ∂                          I                                                                          ∂                          y                                                                    )                                        2                                                                                                            Equation          ⁢                      xe2x80x83                    ⁢          9                    
The significance of this normalisation step becomes more apparent if equation 9 is rewritten as Equation 10;   "AutoLeftMatch"                                                                                          u                  ·                  cos                                ⁢                                  xe2x80x83                                ⁢                                  (                  θ                  )                                            +                                                v                  ·                  sin                                ⁢                                  xe2x80x83                                ⁢                                  (                  θ                  )                                                      =            vn                    ⁢                      
                    ⁢                      where            ⁢                          :                                ⁢                      xe2x80x83                    ⁢                      
                    ⁢                                                    cos                ⁢                                  xe2x80x83                                ⁢                                  (                  θ                  )                                            =                                                                    ∂                    I                                                        ∂                    x                                                                    "LeftBracketingBar"                                      ▽                    ⁢                                          xe2x80x83                                        ⁢                    I                                    "RightBracketingBar"                                                      ,                          xe2x80x83                        ⁢                                          sin                ⁢                                  xe2x80x83                                ⁢                                  (                  θ                  )                                            =                                                                    ∂                    I                                                        ∂                    y                                                                    "LeftBracketingBar"                                      ▽                    ⁢                                          xe2x80x83                                        ⁢                    I                                    "RightBracketingBar"                                                      ,                          xe2x80x83                        ⁢                          vn              =                              -                                                                            ∂                      I                                                              ∂                      t                                                                            "LeftBracketingBar"                                          ▽                      ⁢                                              xe2x80x83                                            ⁢                      I                                        "RightBracketingBar"                                                                                                            Equation          ⁢                      xe2x80x83                    ⁢          10                    
in which xcex8 is the angle between the spatial image gradient vector (∇I) and the horizontal; vn is the motion speed in the direction of the image gradient vector, that is, normal to the predominant edge in the picture at that point. This seems a much more intuitive equation relating, as it does, the motion vector to the image gradient and the motion speed in the direction of the image gradient. The coefficients of equation 10 (cos(xcex8) and sin(xcex8)) have a well defined range (0 to 1) and, approximately the same dynamic range as the input signal (typically 8 bits). Similarly vn has a maximum (sensible) value determined by the desired motion vector measurement range. Values of vn greater than the maximum measurement range, which could result from either noise or xe2x80x98cutsxe2x80x99 in the input picture sequence, can reasonably be clipped to the maximum sensible motion speed.
The normalised constraint equation 10 can be solved to find the motion vector in the same way as the unnormalised constraint equation 2. With normalisation, equation 3 becomes Equation 11;                                           [                                                                                ∑                                          xe2x80x83                                        ⁢                                                                  cos                        2                                            ⁢                                              xe2x80x83                                            ⁢                                              (                        θ                        )                                                                                                                                  ∑                                          xe2x80x83                                        ⁢                                          cos                      ⁢                                              xe2x80x83                                            ⁢                                                                        (                          θ                          )                                                ·                        sin                                            ⁢                                              xe2x80x83                                            ⁢                                              (                        θ                        )                                                                                                                                                              ∑                                          xe2x80x83                                        ⁢                                          cos                      ⁢                                              xe2x80x83                                            ⁢                                                                        (                          θ                          )                                                ·                        sin                                            ⁢                                              xe2x80x83                                            ⁢                                              (                        θ                        )                                                                                                                                  ∑                                          xe2x80x83                                        ⁢                                                                  sin                        2                                            ⁢                                              xe2x80x83                                            ⁢                                              (                        θ                        )                                                                                                                  ]                    ·                      [                                                                                u                    0                                                                                                                    v                    0                                                                        ]                          =                  "AutoLeftMatch"                                                    [                                                                                                    ∑                                                  xe2x80x83                                                ⁢                                                                              vn                            ·                            cos                                                    ⁢                                                      xe2x80x83                                                    ⁢                                                      (                            θ                            )                                                                                                                                                                                                  ∑                                                  xe2x80x83                                                ⁢                                                                              vn                            ·                            sin                                                    ⁢                                                      xe2x80x83                                                    ⁢                                                      (                            θ                            )                                                                                                                                              ]                            ⁢                              xe2x80x83                            ⁢              or              ⁢                              :                            ⁢                              xe2x80x83                            ⁢                              Φ                ·                                  [                                                                                                              u                          0                                                                                                                                                              v                          0                                                                                                      ]                                                      =            ψ                                              Equation        ⁢                  xe2x80x83                ⁢        11            
In fact matrix (xcfx86) has only 2 independent elements, since cos2(x)+sin2(x)=l. This is more clearly seen by rewriting cos2(x) and sin2(x) as xc2xd(lxc2x1cos(2x)) hence equation 11 becomes Equation 12                                          1            2                    ·                      (                                          N                ·                I                            +                              [                                                                                                    ∑                                                  xe2x80x83                                                ⁢                                                  cos                          ⁢                                                      xe2x80x83                                                    ⁢                                                      (                                                          2                              ⁢                                                              xe2x80x83                                                            ⁢                              θ                                                        )                                                                                                                                                              ∑                                                  xe2x80x83                                                ⁢                                                  sin                          ⁢                                                      xe2x80x83                                                    ⁢                                                      (                                                          2                              ⁢                                                              xe2x80x83                                                            ⁢                              θ                                                        )                                                                                                                                                                                                  ∑                                                  xe2x80x83                                                ⁢                                                  sin                          ⁢                                                      xe2x80x83                                                    ⁢                                                      (                                                          2                              ⁢                                                              xe2x80x83                                                            ⁢                              θ                                                        )                                                                                                                                                              -                                                  ∑                                                      xe2x80x83                                                    ⁢                                                      cos                            ⁢                                                          xe2x80x83                                                        ⁢                                                          (                                                              2                                ⁢                                                                  xe2x80x83                                                                ⁢                                θ                                                            )                                                                                                                                                                          ]                                      )                    ·                      [                                                                                u                    0                                                                                                                    v                    0                                                                        ]                          =                  "AutoLeftMatch"                      [                                                                                ∑                                          xe2x80x83                                        ⁢                                                                  vn                        ·                        cos                                            ⁢                                              xe2x80x83                                            ⁢                                              (                        θ                        )                                                                                                                                                              ∑                                          xe2x80x83                                        ⁢                                                                  vn                        ·                        sin                                            ⁢                                              xe2x80x83                                            ⁢                                              (                        θ                        )                                                                                                                  ]                    ⁢                      xe2x80x83                                              Equation        ⁢                  xe2x80x83                ⁢        12            
where I is the (2xc3x972) identity matrix and N is the number of pixels included in the summations. Again the motion vector can be found using equation 13:                               [                                                                      u                  0                                                                                                      v                  0                                                              ]                =                              (                                                                                λ                    1                                                                              λ                      1                      2                                        +                                          n                      1                      2                                                                      ⁢                                  xe2x80x83                                ⁢                                  e                  1                                ⁢                                  e                  1                  t                                            +                                                                    λ                    2                                                                              λ                      2                      2                                        +                                          n                      2                      2                                                                      ⁢                                  xe2x80x83                                ⁢                                  e                  2                                ⁢                                  e                  2                  t                                                      )                    ·                      "AutoLeftMatch"                          [                                                                                          ∑                                              xe2x80x83                                            ⁢                                                                        vn                          ·                          cos                                                ⁢                                                  xe2x80x83                                                ⁢                                                  (                          θ                          )                                                                                                                                                                                ∑                                              xe2x80x83                                            ⁢                                                                        vn                          ·                          sin                                                ⁢                                                  xe2x80x83                                                ⁢                                                  (                          θ                          )                                                                                                                                ]                                                          Equation        ⁢                  xe2x80x83                ⁢        13            
where now e and xcex are the eigenvectors and eigenvalues of xcfx86 rather than M. Now, because xcfx86 only has two independent elements, the eigen-analysis can now be performed using only three, two-point, lookup tables, furthermore the dynamic range of the elements of xcfx86 (equation 11) is much less than the elements of M thereby greatly simplifying the hardware complexity.
A block diagram of a gradient motion estimator using Martinez technique and based on the normalised constraint equation is shown in FIGS. 6 and 7.
The apparatus of FIG. 6 performs the calculation of the normalised constraint equation (equation 10) for each pixel or data value. Obviously, if prefiltering is performed the number of independent pixel values is reduced, the effective pixel size is greater. The filtering in FIG. 6 is identical to that in FIG. 2. The spatial image gradients converted to the output standard are used as inputs for a rectangular to polar co-ordinate converter (32) which calculates the magnitude of the spatial image vector and the angle xcex8. A suitable converter can be obtained from Raytheon (Co-ordinate transformer, model TMC 2330). A lookup table (34) is used to avoid division by very small numbers when there is no detail in a region of the input image. The constant term, xe2x80x98nxe2x80x99, used in the lookup table is the measurement noise in estimating |∇I| which depends on the input signal t noise ratio and the prefiltering used. A limiter (36) has also been introduced to restrict the normal velocity, vn, to its expected range (determined by the spatial prefilter) The normal velocity might, otherwise, exceed its expected range when the constraint equation is violated, for example at picture cuts. A key feature of FIG. 6 is that, due to the normalisation, that has been performed, the two outputs, vn and xcex8, have a much smaller dynamic range than the three image gradients in FIG. 2, thereby allowing a reduction in the hardware complexity.
In the apparatus of FIG. 6 the input video is first filtered using separate temporal, vertical and horizontal filters (10,12,14), the image gradients are calculated using three differentiating filters (16,18) and then converted, from the input lattice, to the output sampling lattice using three vertical/temporal interpolators (20), typically bilinear or other polyphase linear filters. For example, with a 625/50/2:1 input the image gradients night be calculated on a 525/60/2:1 lattice. The parameters of the normalised constraint equation, vn and xcex8, are calculated as shown.
The apparatus of FIG. 7 calculates the best fitting motion vector, corresponding to a region of the input image, from the constraint equations for the pixels in that region. The summations specified in equation 12 are implemented by the lowpass filters (38) following the polar to rectangular co-ordinate converter (40) and lookup tables 5 and 6. Typically these filters (38) would be (spatial) running average filters, which give equal weight to each tap within their region of support. Other lowpass filters could also be used at the expense of more complex hardware. The size of these filters (38) determine the size of the neighbourhood used to calculate the best fitting motion vector. Lookup tables 5 and 6 are simply cosine and sine lookup tables. Lookup tables 7 to 9 contain precalculated values of matrix xe2x80x98Zxe2x80x99 defined by Equation 14;                     Z        =                  (                                                                      λ                  1                                                                      λ                    1                    2                                    +                                      n                    1                    2                                                              ⁢                              xe2x80x83                            ⁢                              e                1                            ⁢                              e                1                t                                      +                                                            λ                  2                                                                      λ                    2                    2                                    +                                      n                    2                    2                                                              ⁢                              xe2x80x83                            ⁢                              e                2                            ⁢                              e                2                t                                              )                                    Equation        ⁢                  xe2x80x83                ⁢        14            
where e and xcex are the eigenvectors and eigenvalues of xcfx86. Alternatively Z could be xcfx86xe2x88x921 (i.e. assuming no noise), but this would not apply the Martinez technique and would give inferior results. A key feature of FIG. 7 is that the elements of matrix Z are derived using 2 input lookup tables. Their inputs are the output from the two lowpass filters (39) which have a small dynamic range allowing the use of small lookup tables.
The implementations of the gradient motion techniques discussed above seek to find the xe2x80x98bestxe2x80x99 motion vector for a region of the input picture. However it is only appropriate to use this motion vector, for motion compensated processing, if it is reasonably accurate. Whilst the determined motion vector is the xe2x80x98best fitxe2x80x99 this does not necessarily imply that it is also an accurate vector. The use of inaccurate motion vectors, in performing motion compensated temporal interpolation, results in objectionable impairments to the interpolated image. To avoid these impairments it is desirable to revert to a non-motion compensated interpolation algorithm when the motion vector cannot be measured accurately. To do this it is necessary to know the accuracy of the estimated motion vectors. If a measure of vector accuracy is available then the interpolation method can be varied between xe2x80x98full motion compensationxe2x80x99 and no motion compensation depending on vector accuracy, a technique known as xe2x80x98graceful fallbackxe2x80x99 described in reference 16.
It has been suggested (reference 16) to provide an indication of motion vector reliability in phase correlation systems determined from the relative height of the correlation peaks produced. In block matching systems, an error indication is given by the quality of the match between picture blocks. Neither of these options measures the actual error of the motion vectors but merely provide an indication thereof. In the latter case the xe2x80x9cconfidencexe2x80x9d in the motion vectors is given by a difference in grey levels between the blocks and is not, therefore, necessarily related to the motion vector error.
It is an object of the present invention to provide a technique for determining the accuracy of motion vectors. This method is based on the use of the constraint equation and hence is particularly suitable for use with gradient based motion estimation techniques as described above. The method, however, is more general than this and could also be used to estimate the accuracy of motion vectors measured in other ways, for example, using a block matching technique. The measurement of the accuracy of motion vectors is a new technique. Most of the literature on motion estimation concentrates almost wholly on ways of determining the xe2x80x98bestxe2x80x99 motion vector and pays scant regard to considering whether the resulting motion vectors are actually accurate. This may, in part, explain why motion compensated processing is, typically, unreliable for certain types of input image.
The invention provides video or film signal processing apparatus comprising motion estimation apparatus for generating motion vectors each corresponding to a region of an input video signal, means for calculating for each of said regions a plurality of spatial and temporal image gradients, and means for calculating for each motion vector a plurality of error values corresponding to said plurality of image gradients, the apparatus having as an output for each motion vector a corresponding indication of the motion vector measurement error derived from said plurality of error values.
The motion estimation apparatus preferably includes said means for calculating the image gradients.
The motion estimation apparatus preferably calculates the motion vectors from the normalised constraint equation of a plurality of image gradients and generates a corresponding plurality of outputs each equal to the angle (xcex8) corresponding to the orientation of the spatial image gradient vector and the speed (vn) in the direction of the spatial image gradient vector.
The means for calculating a plurality of error values includes sine and cosine lookup tables having the values of xcex8 as an input and an arithmetic having as inputs, each motion vector, a corresponding plurality of values of vn and the sines and cosines of xcex8.
The apparatus may comprise multiplier means for generating a plurality of error vectors and having said error values and the corresponding values of sin xcex8 and cos xcex8 as inputs.
The apparatus preferably comprises means for generating at least one parameter giving an indication of the extent of the distribution of motion vector measurement errors.
The invention also provides a method of processing video or film signals comprising generating motion vectors each corresponding to a region of an input signal, for each region calculating a plurality of spatial and temporal image gradients, calculating a plurality of error values corresponding to said plurality of image gradients, and generating for each motion vector a corresponding indication of the motion vector measurement error derived from said plurality of error values.
The motion vectors may be generated based on the constraint equations corresponding to said plurality of image gradients.
The method may comprise calculating for each plurality of image gradients corresponding to each of said regions, an angle (xcex8) corresponding to the orientation of the spatial image gradient vector and the motion speed (vn) in the direction of said spatial image gradient vector.
The method preferably comprises calculating a plurality of error vectors from said error values.
The indication of motion vector measurement error may be in the form of at least one parameter indicating, the extent of the distribution of motion vector measurement errors.
In an embodiment the said at least one parameter includes a scalar motion vector error signal. In a further embodiment the said at least one parameter includes four values representing the spread in motion vector measurement error. These four values may be comprised of two, two-component, vectors.