Abstract:
A confidence map for optical flow gradients is constructed calculating a set of census texture gradients for each pixel of an image, filtering said gradients and extracting confidence values from said gradients using a plurality of decision tree classifiers. A confidence map is then generated from said confidence values.

Description:
CLAIM OF PRIORITY 
       [0001]    This application claims priority under 35 U.S.0 119(e)(1) to Indian Provisional Application No. 201641001331 filed Jan. 14, 2016 
     
    
     TECHNICAL FIELD OF THE INVENTION 
       [0002]    The technical field of this invention is optical flow estimation. 
       BACKGROUND OF THE INVENTION 
       [0003]    Optical flow or optic flow is the pattern of apparent motion of objects, surfaces, and edges in a visual scene caused by the relative motion between an observer (an eye or a camera) and the scene. The concept of optical flow was introduced by the American psychologist James J. Gibson in the 1940s to describe the visual stimulus provided to animals moving through the world. Subsequently the term optical flow has been co-opted in the computer vision domain to describe pixel motion in between two temporally ordered images of the scene, and incorporate related techniques of estimation of pixel motion. The optical flow estimation techniques are further integrated in related techniques of image processing and navigation control. 
         [0004]    Methods of navigation control are of special interest in advanced driver assistance systems (ADAS). Motion detection in ADAS is fundamental to solving various problems such as object segmentation, time-to-contact information, depth estimation, structure from motion and focus of expansion calculations etc. One of the most widely used techniques for motion detection is the optical flow estimation. Thus, when used in ADAS, accuracy and speed of the optical flow estimation is a critical component in guaranteeing overall reliability of the ADAS. Accordingly, there is a need for a real-time optical flow estimation system having sufficient accuracy in all possible scenarios. 
         [0005]    Optical flow estimation is a challenging problem. There are many scenarios where the flow estimation can go wrong such as occlusions, a new object coming into the camera&#39;s field of view, or an object going out of the camera&#39;s field of view. Camera rotations can make it difficult (or sometimes impossible) to estimate the correct optical flow. Low visibility (night vision, rain or fog), noise in the image, high rates of motion etc., are some other difficult scenarios for optical flow estimation. Flow estimation can also be challenging around moving object boundaries. 
         [0006]    The estimated optical flow algorithm is typically used by a higher level algorithm such as the object tracking algorithm. It is important for the higher level algorithm to know where the optical flow estimation is correct and where it is likely to be wrong - so that the higher level algorithm can either discard the potentially incorrect flow estimates or assign proper weight based on the estimated correctness of the optical flows. Accordingly there is a need for computing a confidence map associated with the optical flow. This confidence map then indicates the confidence in the optical flow estimation—whether the flow estimation is likely to be correct or not. 
       SUMMARY OF THE INVENTION 
       [0007]    A method for estimating a score or measure for optical flow is shown that generates a confidence map indicating confidence limits or weights on a pixel by pixel basis. This allows higher level algorithms to assign lesser importance, or to ignore altogether areas of a frame that have defective optical flow values. 
         [0008]    The census texture gradient is a powerful feature to handle low light or low texture regions. In low light or low texture regions, the flow vector may be incorrect. The census texture gradient and the smoothened version of it is capable to detect such regions. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    These and other aspects of this invention are illustrated in the drawings, in which: 
           [0010]      FIG. 1  shows a high level block diagram of the invention; 
           [0011]      FIG. 2  shows a block diagram of the smoothening operation; 
           [0012]      FIG. 3  shows the decision tree; 
           [0013]      FIG. 4  shows a processor that the invention may be implemented on; and 
           [0014]      FIG. 5  shows a comparison of this invention and prior art methods. 
       
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
       [0015]    This invention shows a dense optical flow estimation algorithm using a quasi-parametric approach, capable of accurate, highly precise and efficient optical flow estimation over a large range of relative pixel motions. 
         [0016]    While there has been optical flow algorithms developed in the prior art, there has not been an attempt to generate a confidence map in real time, along with the optical flow. The estimated confidence map helps to understand which of the flow values are correct and which of them are potentially wrong. 
         [0017]    The described optical flow confidence map generation algorithm shown on  FIG. 1  is implemented as follows: 
         [0018]    For every pixel, a set of features are computed. The features include image features  101  and flow features  102 . Smoothened versions  103  of the features are also computed. 
         [0019]    These features are sent to a decision tree classifier  104  that outputs a classifier score. This classifier score is then converted to a confidence value. 
         [0020]    The features used are gradients of flow, matching cost measures and gradients of the image for computation of the confidence measure. These are defined as: 
         [0021]    Gradient of the U component of the optical flow (Gu) 
         [0022]    Gradient of the V component of the optical flow (Gv) 
         [0023]    Cost (or distance) corresponding to the best match (C0) 
         [0024]    Delta matching cost=Second_best_cost-best_cost Cd=(C1-C0) 
         [0025]    Gradient magnitude of the input image (Gm)
   1. Cg=Census Texture Gradient   
 
         [0027]    Su=Smoothened version of Gu 
         [0028]    Sv=Smoothened version of Gv 
         [0029]    S0=Smoothened version of C 
         [0030]    Sd=Smoothened version of Cd 
         [0031]    Sm=Smoothened version of Gm
   2. Sg=Smoothened version of Cg   
 
         [0033]    Using the above features, a feature vector is constructed for every pixel. However some implementations may use only a subset of these features in the feature vector. Other implementations may use all 12 features:
   Gu, Gv, C0, Cd, Gm, Cg, Su, Sv, S0, Sd, Sm, Sg   
 
         [0035]    This feature vector is then processed by a decision tree classifier to derive the confidence measure. 
         [0036]    Gradients are computed as follows. Let X be the input to the gradient function, and for any location (i,j), a simplified form of the backward gradient is defined as:
   g=[abs(X(i,j)−X(i-1,j))+abs(X(i,j)−X(i,j-1))] G(i,j)=min((g&lt;&lt;GRADIENT_SHIFT),GRADIENT_MAX)   
 
         [0038]    Typical range of GRADIENT SHIFT is between 0 to 8 and that of GRADIENT MAX 255 to 65535. The value of GRADIENT MAX also depends on range of X itself. 
         [0039]    The above gradient method is used to compute the gradients of the flow values (Gu, Gv), and the gradient of the image (Gm). 
         [0040]    Census Texture Gradient Computation (Cg) 
         [0041]    Census texture gradient is not sensitive to intensity variations. 
         [0042]    Let C(i,j) denote the census transform at row i, column j This is a binary string of certain length (depending on the exact nature of the census transform used) 
         [0043]    Let H(c1, c2) denote the hamming distance between census signatures c1 and c2 
         [0044]    Census gradient to be used is:
   Cg(i,j)=H(C(i,j), C(i-1,j))+H(C(i,j), C(i,j-1))   
 
         [0046]    The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. It indicates the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. 
         [0047]    A smoothening operation is performed by a 2 dimensional separable combination of FIR and IIR filters as shown on  FIG. 2 . FIR filtering  201  is implemented in the horizontal direction followed by IIR filtering  202  in the vertical direction. FIR filters are more controllable and are seen to be best for this application from a quality point of view. However, using an FIR filter in vertical direction adds to the delay and increases the line size of the buffers required—therefore an IIR filter is used in the vertical direction. 
         [0048]    For any location (i,j), a simplified form of the smoothening operation may be implemented as follows:
   X is the input to the smoothening function, SmoothH(i,j)=sum(X(i,j-8+m)); m=0,1, . . . 17 where SmoothH(i,j) is the horizontally filtered version (intermediate value).   
 
         [0050]    This is followed by IIR filtering vertically with the previous line of output as follows:
   S(i,j)=(SmoothH(i,j)*SMOOTH_ALPHA+S(i-1,j)*SMOOTH_BETA) where S(i,j) is the output of the smoothening operation and S(i-1,j) is the corresponding output from the previous line.   The above smoothening method is used to compute Su, Sv, S0, Sd, Sm and Sq.   
 
         [0053]    The 2 level decision tree shown in  FIG. 3  then selects a weight based on input features and thresholds. Several decision trees are used in the implementation shown and weights are accumulated from each of them. 
         [0054]    In  FIG. 3 , subscript ‘i’ indicates the ith decision tree. 
         [0055]    FV indicates the Feature Vector array of size M. 
         [0056]    Fidx represents an index into the Feature Vector, taking values from 0 to (M-1). 
         [0057]    The entries Thx are threshold values for comparisons. 
         [0058]    Wxx are weight values used to generate scores. 
         [0059]    In the example configuration shown, a set 16 decision trees are used to convert the feature vectors into a score value. The values of the decision trees can be represented in Table 1: 
         [0000]    
       
         
               
               
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                   
                   
                 Tree Number 
               
             
          
           
               
                   
                   
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
               
               
                 Node 
                 Fid 0   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 0 
                 Th 0   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 Node 
                 Fid 1   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 1 
                 Th 1   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                   
                 W 10   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 Node 
                 Fid 2   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 2 
                 Th 2   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                   
                 W 20   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                   
                 W 21   
               
               
                   
               
             
          
         
       
     
         [0060]    For each column, the partial score Vi is computed that corresponds to one column of the above table:
       Vi=((FV[Fid0[i]]&lt;Th0[i])&amp;&amp;(FV[Fid1[i]]&lt;Th1[i]))*W10[i]+((FV[Fid0[i]]&lt;Th0[i])&amp;&amp;(FV[Fid1[i]]&gt;=Th1[i]))*W11[i]+((FV[Fid0[i]]&gt;=Th0[i])&amp;&amp;(FV[Fid2[i]]&lt;Th2[i]))*W20[i]+((FV[Fid0[ 1 ]]&gt;=Th0[i])&amp;&amp;(FV[Fid2[ 1 ]]&gt;=Th2[i]))* W21[i];       
 
         [0062]    The accumulated score V=(V1+V1+ . . . +V15) is the sum of the scores of 16 decision trees. This accumulated score V can exceed 16 bits. 
         [0063]    The entries in the table are usually produced by a heuristic training algorithm with manually selected values. 
         [0064]    The confidence map is calculated from the accumulated score V by scaling the accumulated score and clipping it to a suitable range—for example between 0 and 15. This can be done as follows:
   CS=(V*OUTPUT_MULT_FACTOR_LINEAR)&gt;&gt;OUTPUT_SHIFT_FACTOR C=min(max(CS, −8), +7)+8   
 
         [0066]    The confidence map, C, is thus quantized to discrete levels, for example 0,1, . . . , 15 (4 bits) so it can be represented in fixed bit precision. 
         [0067]      FIG. 4  shows a processor that may be used to implement the methods of this invention. The processor consists of a general purpose processing unit  401 , a digital signal processor  402 , a graphics processing unit  403 , one or more video output ports  404 , internal memory  405 , a display controller subsystem  406 , one or more peripherals  407 , an external memory controller  408 , and external memory  410 . These system blocks are operable to communicate through bus  409 . 
         [0068]      FIGS. 5  shows the performance of the method described in this invention, compared to methods used in the prior art. In this figure, matching cost  504  and the cost ratio  503  is compared to the performance  502  of this invention and to GT, the ground truth  501 —this is the actual correctness of the optical flow. The methods are evaluated by looking at the AUC—the area under the curve. The better the match, the lower the AUC, as shown on  FIG. 5 . 
         [0069]    Left-right consistency check is typically used in the prior art for confidence map estimation for stereo disparity computation. Similarly, for optical flow confidence estimation, one could use a forward-backward check - however the optical flow confidence map estimation shown in this invention is are able to generate accurate confidence estimates without need for explicit forward/backward check. This helps in reducing computation complexity significantly as performing the check would have roughly doubled computational complexity. 
         [0070]    Variance or central gradient of flow has been seen to be used as features for optical flow confidence estimation in the prior art - this requires several neighboring pixels/lines and hence requires several line buffers for storage, with a delay in the output. However, in the approach shown a simple backward gradient is used with no additional delay - and only one previous line is required for the gradient computation. 
         [0071]    Confidence estimation in the prior art uses either features obtained while running the optical flow for a smaller resolution, or features scaled by FIR filtering/resizing. Both these approaches are complex to implement in hardware. The first approach needs data from the smaller resolution to be transported via external memory to the stage were the higher resolution optical flow is computed. The second approach needs several lines of features for the filtering operation.