Abstract:
The present disclosure relates generally to optical flow algorithms. Section 1 of the present disclosure describes an optical flow algorithm with real-time performance and adequate accuracy for embedded vision applications. This optical flow algorithm is based on a ridge estimator. Sections 2 and 3 describe an obstacle detection algorithm that utilizes the motion field that is output from the optical flow algorithm. Section 2 is focused on unmanned ground vehicles, whereas section 3 is focused on unmanned aerial vehicles.

Description:
PRIORITY CLAIM 
       [0001]    This application claims priority from U.S. Provisional Patent Application Ser. No. 61/265,293, filed Nov. 30, 2009, for “Real-Time Optical Flow Sensor Design And Its Application To Obstacle Detection,” with inventors Dah-Jye Lee and Zhaoyi Wei. 
     
    
     BACKGROUND 
       [0002]    The present disclosure relates generally to optical flow algorithms. Optical flow algorithms aim to measure a motion field from the apparent motion of a brightness pattern. Optical flow is widely used in 3D vision tasks such as egomotion estimation, Structure from Motion (SfM), motion segmentation, etc. One common limitation of optical flow is the computational power requirement. The calculation time of existing optical flow algorithms is typically on the order of seconds or even longer per frame. This long processing time thus prevents optical flow algorithms from many real-time applications such as autonomous navigation for unmanned vehicles. 
       SUMMARY 
       [0003]    Section 1 of the present disclosure describes an optical flow algorithm with real-time performance and adequate accuracy for embedded vision applications. This optical flow algorithm is based on a ridge estimator. Sections 2 and 3 describe an obstacle detection algorithm that utilizes the motion field that is output from the optical flow algorithm. Section 2 is focused on unmanned ground vehicles, whereas section 3 is focused on unmanned aerial vehicles. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0004]      FIG. 1  illustrates an example of an optical flow sensor that implements the ridge-regression tensor-based optical flow algorithm that is described in section 1.1 of the present disclosure; 
           [0005]      FIG. 2  illustrates a derivative calculation module from the optical flow sensor of  FIG. 1 ; 
           [0006]      FIG. 3  illustrates an optical flow calculation module from the optical flow sensor of  FIG. 1 ; 
           [0007]      FIG. 4  illustrates linked lists that may be utilized by software that is running on the optical flow sensor of  FIG. 1 ; 
           [0008]      FIG. 5  illustrates a point P=(X, Y, Z) T  in the camera frame being projected onto p=(x, y, f) T  on the image frame; 
           [0009]      FIG. 6  illustrates two parameters—namely (ω y , T Z )— that may be utilized for obstacle detection for a forward-looking camera mounted on a ground vehicle traveling on a planar surface; 
           [0010]      FIG. 7  illustrates that the residual motion components will ideally be zero for ground plane pixels and non-zero for obstacle pixels after the motion field is de-rotated and de-translated; 
           [0011]      FIG. 8  illustrates an example of an obstacle detection module that implements the obstacle detection algorithm that is described in section 2.1 of the present disclosure; 
           [0012]      FIG. 9  illustrates the de-rotation sub-module from the obstacle detection module of  FIG. 8 ; and 
           [0013]      FIG. 10  illustrates an example of a method for obstacle detection for an unmanned aerial vehicle (UAV). 
       
    
    
     DETAILED DESCRIPTION 
     1. Optical Flow Algorithm 
       [0014]    1.1 Algorithm Formulation 
         [0015]    The basic assumption of optical flow algorithms is the Brightness Constancy Constraint (BCC) which can be formulated as: 
         [0000]        I ( x,y,t )= I ( x+Δx,y+Δy,t+Δt )  (1.1)
 
         [0016]    where I(x, y, t) is the intensity of pixel (x,y) at frame t and I(x+Δx, y+Δy, t+Δt) is the intensity of the corresponding pixel at frame t+Δt. 
         [0017]    Based on the BCC, an equation regarding derivatives g x , g y , and g t  and velocity components ν x  and ν y  may be derived as: 
         [0000]        g   x ν x   +g   y ν y   +g   t +ε=0
 
         [0000]                − g   t   =g   x ν x   +g   y ν y +ε  (1.2)
 
         [0018]    where 
         [0000]    
       
         
           
             
               
                 v 
                 x 
               
               = 
               
                 
                   Δ 
                    
                   
                       
                   
                    
                   x 
                 
                 
                   Δ 
                    
                   
                       
                   
                    
                   t 
                 
               
             
             , 
             
               
 
             
              
             
               
                 v 
                 y 
               
               = 
               
                 
                   Δ 
                    
                   
                       
                   
                    
                   y 
                 
                 
                   Δ 
                    
                   
                       
                   
                    
                   t 
                 
               
             
             , 
           
         
       
     
         [0000]    and ε is the error accounting for the higher order terms and noise. Each pixel in the image has one set of observations g ti , g xi , g yi . In a small neighborhood of n pixels, it is assumed that they all have the same velocity ν x  and ν y . Then the n set of observations for these n pixels can be expressed as: 
         [0000]        g   t   =g   x (−ν x )+ g   y (−ν y )+ε  (1.3)
 
         [0019]    where g t =(g t1 , g t2 , . . . , g tn ) T , g x =(g x1 , g x2 , . . . g xn ) T , g y =(g y1 , g y2 , . . . g yn ) T , ε=(ε 1 , ε 2 , . . . ε n ) T . 
         [0020]    It is assumed that the expectation of ε j  satisfies E(ε j )=0 and the variance is σ 2 , i.e., ε˜(0,σ 2 ). Denoting Y nx1 =g t , X nx2 =(g x ,g y ), θ=−(ν x ,ν y ) T , the equation regarding the observation (g ti , g xi , g yi ) and the parameter θ can be written as: 
         [0000]        Y=Xθ+ε   (1.4)
 
         [0021]    A normal least squares solution of θ in equation (1.4) is: 
         [0000]      {circumflex over (θ)} LS =( X   T   X ) −1   X   T   Y   (1.5)
 
         [0022]    It can be shown that E({circumflex over (θ)} LS )=θ, and that its covariance matrix is Cov({circumflex over (θ)} LS )=σ 2 (X T X) −1 . If g x  and g y  exhibit near linear dependency (i.e., one vector is nearly a scale of the other), small amounts of noise in the observation will cause relatively large changes in the inversion (X T X) −1 , and produce very large and inaccurate motion vectors. For hardware-based algorithms, because of resource limitations, the vector length n is usually much smaller than in software-based algorithms. This, in turn, increases the possibility of a collinear (X T X) matrix. The resulting abnormal motion vectors will have a negative impact on neighboring motion vectors in the subsequent smoothing process. 
         [0023]    One simple solution is to simply restrict the magnitude of each motion vector, but this is not an optimal solution. In the present disclosure, a ridge estimator is proposed to address this: 
         [0000]      {circumflex over (θ)} RE =( X   T   X+kI   p ) −1   X   T   Y   (1.6)
 
         [0024]    In equation (1.6), I p  is a unit matrix of the same size as X T X where p equals two in this case. The term k is a weighting scalar for I p . It can be shown that the expectation and covariance matrices of {circumflex over (θ)} RE  are: 
         [0000]        E ({circumflex over (θ)} RE )=θ− k ( X   T   X+kI   p ) −1 θ  (1.7)
 
         [0000]        Cov ({circumflex over (θ)} RE )=σ 2   X   T   X ( X   T   X+kI   p ) −2   (1.8)
 
         [0025]    Although a ridge estimator is biased (i.e., E({circumflex over (θ)} RE )≠θ as shown in equation (1.7)), it is better than a least squares estimator if evaluated based on risk instead of observed loss. Risk is defined as the expectation of loss which is independent of the observed Y. 
         [0026]    As to the selection of k, an HKB estimator shown as 
         [0000]    
       
         
           
             
               
                 
                   k 
                   = 
                   
                     
                       p 
                        
                       
                           
                       
                        
                       
                         
                           σ 
                           ^ 
                         
                         2 
                       
                     
                     
                       
                         
                           θ 
                           ^ 
                         
                         N 
                         T 
                       
                        
                       
                         
                           θ 
                           ^ 
                         
                         N 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1.9 
                   ) 
                 
               
             
           
         
       
     
         [0027]    may be chosen. The term {circumflex over (θ)} N  is the estimate right above the current pixel and it is preset to (1,1) T  on the first row. The error variance is estimated as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       σ 
                       ^ 
                     
                     2 
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             Y 
                             - 
                             
                               X 
                                
                               
                                 
                                   θ 
                                   ^ 
                                 
                                 N 
                               
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         ( 
                         
                           Y 
                           - 
                           
                             X 
                              
                             
                               
                                 θ 
                                 ^ 
                               
                               N 
                             
                           
                         
                         ) 
                       
                     
                     
                       n 
                       - 
                       p 
                     
                   
                 
               
               
                 
                   ( 
                   1.10 
                   ) 
                 
               
             
           
         
       
     
         [0028]    There exist other methods to estimate the scalar (e.g., an iterative HK estimator, an LW estimator, etc.). The HKB estimator may be chosen for its efficiency and non-iterative property. After obtaining k, the optical flow is estimated using equation (1.6). 
         [0029]    An n-by-n weighting matrix W may be used to assign weights to each set of observations based on their distance to the central pixel. Equations (1.6) and (1.10) may be rewritten as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       θ 
                       ^ 
                     
                     RE 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           
                             
                               X 
                               T 
                             
                              
                             WX 
                           
                           + 
                           
                             kI 
                             p 
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       X 
                       T 
                     
                      
                     WY 
                   
                 
               
               
                 
                   ( 
                   1.11 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       σ 
                       ^ 
                     
                     2 
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             Y 
                             - 
                             
                               X 
                                
                               
                                 
                                   θ 
                                   ^ 
                                 
                                 N 
                               
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         W 
                          
                         
                           ( 
                           
                             Y 
                             - 
                             
                               X 
                                
                               
                                 
                                   θ 
                                   ^ 
                                 
                                 N 
                               
                             
                           
                           ) 
                         
                       
                     
                     
                       n 
                       - 
                       p 
                     
                   
                 
               
               
                 
                   ( 
                   1.12 
                   ) 
                 
               
             
           
         
       
     
         [0030]    The term kI p  in equation (1.11) can be replaced by a diagonal matrix which has different values along the diagonal compared to equation (1.11). 
         [0031]    To suppress noise, the derivatives g x , g y , and g t  may be spatiotemporally smoothed, respectively, before they are used in equation (1.3). Motion vectors may also be spatially smoothed to obtain a smooth motion field. 
         [0032]    The initial optical flow vector is smoothed in a local neighborhood to suppress noise further. The final optical flow vector is formulated as: 
         [0000]    
       
         
           
             
               
                 
                   
                     v 
                     _ 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 v 
                                 _ 
                               
                               x 
                             
                           
                         
                         
                           
                             
                               
                                 v 
                                 _ 
                               
                               y 
                             
                           
                         
                       
                       ) 
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                            
                           
                               
                           
                         
                         
                             
                         
                       
                        
                       
                           
                       
                        
                       
                         
                           m 
                           i 
                         
                          
                         
                           ( 
                           
                             
                               
                                 
                                   
                                     v 
                                     _ 
                                   
                                   xi 
                                 
                               
                             
                             
                               
                                 
                                   
                                     v 
                                     _ 
                                   
                                   yi 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1.13 
                   ) 
                 
               
             
           
         
       
     
         [0033]    The algorithm assumes a constant motion model. An affine motion model is often used to incorporate tensors in a small neighborhood where pixels in a neighborhood are assumed to belong to the same motion model. To conserve hardware resources, the constant model may be used in this design. The constant model performs almost as well as the affine motion model when operating in a small neighborhood. 
         [0034]    1.2 Optical Flow Sensor 
         [0035]    An example of an optical flow sensor  100  that implements the optical flow algorithm that was described in section 1.1 will now be described in relation to  FIGS. 1-4 . The optical flow sensor  100  may be implemented in a field-programmable gate array (FPGA). FPGAs provide low power, small size, and adequate computation capability. Therefore, implementing the optical flow sensor  100  in an FPGA allows the optical flow sensor  100  to be utilized for embedded vision applications (e.g., to be installed in an unmanned vehicle for real-time applications). Alternatively, the optical flow sensor  100  may be implemented using application specific integrated circuits (ASICs) for large volume production to lower the unit cost. 
         [0036]    As shown in  FIG. 1 , the optical flow sensor  100  may include two types of buses: a PLB (processor local bus)  101  and an OPB (on-chip peripheral bus)  102 . High-speed modules such as a DER (DERivatives calculation) module  103 , an OFC (optical flow calculation) module  104 , SDRAM  105 , a camera interface  106 , and a USB (universal serial bus) interface  107  may be coupled to the PLB  101 . Lower-speed modules such as a UART (universal asynchronous receiver/transmitter)  108 , an interrupt controller  109 , and a GPIO (general purpose input/output)  110  may be coupled to the OPB  102 . The PLB  101  and OPB  102  may be interconnected through a bridge  111 . 
         [0037]    The optical flow sensor  100  may incorporate temporal smoothing in the pipeline. The number of frames used for temporal smoothing may depend on the available hardware and memory resources and the processing speed requirement. With temporal smoothing, multiple (e.g., three) sets of derivative frames may be stored as they are calculated and then be reloaded during the smoothing process. 
         [0038]    To accommodate temporal smoothing, the hardware pipeline may be divided into two parts: the DER module  103 , and the OFC module  104 . The DER module  103  generates derivative frames and the OFC module  104  handles the rest of the calculations. Results from the DER module  103  may be stored in SRAM  112  and SDRAM  105 . The DER module  103  and the OFC module  104  may share the high-speed SRAM  112  through a multi-port SRAM arbiter  113 . The OFC module  104  may store the resulting motion vectors in SDRAM  105 . The intermediate or final results can be transferred to a host computer via the USB interface  107 . A graphical user interface may be utilized to observe and store the video and display status variables that are transferred from the optical flow sensor  100 . The DER module  103  and the OFC module  104  should be managed to synchronize their computation tasks and handle exceptions such as dropped frames. The optical flow sensor  100  includes one or more built-in, on-chip processors, and software running on the processor(s) that is used for this management task. 
         [0039]      FIG. 2  illustrates an example of the DER module  103 . The DER module  103  may be configured so that every cycle when a new image frame(t) is captured directly into the SDRAM  105  through the PLB  101 , reading logic  114  reads the captured image from the SDRAM  105  into a pipeline and stores it in the SRAM  112 . If three frames are used for temporal smoothing, then g x  and g y  may be calculated  115  from frame(t−2) and g t  may be calculated  116  from frame(t−4), frame(t−3), frame(t−1) and the current incoming frame(t). A series-designed first-order derivative operator of radius two, such as the one given by equation (1.14), may be utilized for these calculations. 
         [0000]    
       
         
           
             
               
                 
                   D 
                   = 
                   
                     
                       1 
                       12 
                     
                      
                     
                       ( 
                       
                         
                           
                             1 
                           
                           
                             
                               - 
                               8 
                             
                           
                           
                             0 
                           
                           
                             8 
                           
                           
                             
                               - 
                               1 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   1.14 
                   ) 
                 
               
             
           
         
       
     
         [0040]    Thus, whenever there are five consecutive image frames stored in the SRAM  112 , these frames may all be read out for computing the derivative frames g x , g y , and g t . The resulting derivative frames may be stored in the SRAM  112  as well as the SDRAM  105  for future usage. The duplicate copy stored in the SDRAM  105  may be used for temporal smoothing for future frames. If the hardware platform that is used has sufficient SRAM  112 , then all nine derivative frames (three sets of g x , g y  and g t ) could be stored in the SRAM  112  and take advantage of a high-speed multi-port memory interface. 
         [0041]      FIG. 3  illustrates an example of the OFC module  104 . The optical flow sensor  100  may be configured so that once a new set of derivative frames is calculated, software triggers the OFC module  104  to start the calculation of optical flow. In an implementation where the size of the temporal smoothing mask is three, derivative frames for the current frame in the SRAM  112  (g x (t), g y (t) and g t (t)) and the derivative frames already stored in the SDRAM  105  (g x (t−1), g y (t−1) and g t (t−1)) and (g x (t−2), g y (t−2) and g t (t−2)) may be read into the pipeline for temporal smoothing. Derivative frames at time t, t−1, t−2 may be temporally smoothed  117  and then spatially smoothed  118  to obtain the smoothed derivative frames for the current frame at time t. The smoothed derivative frames may be referred to as gx_t, gy_t, and gt_t. For temporal smoothing, a 1D Gaussian mask w 2 (t) may be convolved with the derivative frames. For spatial smoothing, a 2D Gaussian mask w 1 (x,y) may be used. The equation for gx_t may be shown as gx_t=Σ x,y w 1 (x,y)· gx_t(x,y) =Σ x,y w 1 (x,y)·(Σ t w 2 (x, y, t)·gx(x, y, t)). The equations for gy_t and gt_t may be similar to the equation for gx_t. 
         [0042]    The smoothed derivative frames gx_t, gy_t, and gt_t may be used to build  119  regression model components, i.e., construct a tensor for each pixel in the current frame. The tensor for a particular pixel may include elements t 1 -t 6  and may be formulated as: 
         [0000]    
       
         
           
             
               
                 
                   T 
                   = 
                   
                     ( 
                     
                       
                         
                           
                             t 
                             1 
                           
                         
                         
                           
                             t 
                             4 
                           
                         
                         
                           
                             t 
                             5 
                           
                         
                       
                       
                         
                           
                             t 
                             4 
                           
                         
                         
                           
                             t 
                             2 
                           
                         
                         
                           
                             t 
                             6 
                           
                         
                       
                       
                         
                           
                             t 
                             5 
                           
                         
                         
                           
                             t 
                             6 
                           
                         
                         
                           
                             t 
                             3 
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   1.15 
                   ) 
                 
               
             
           
         
       
     
         [0043]    The diagonal component in the tensor matrix (1.15) may be added with an offset k, as shown in (1.16). 
         [0000]    
       
         
           
             
               
                 
                   = 
                   
                     ( 
                     
                       
                         
                           
                             
                               t 
                               1 
                             
                             + 
                             k 
                           
                         
                         
                           
                             t 
                             4 
                           
                         
                         
                           
                             t 
                             5 
                           
                         
                       
                       
                         
                           
                             t 
                             4 
                           
                         
                         
                           
                             
                               t 
                               2 
                             
                             + 
                             k 
                           
                         
                         
                           
                             t 
                             6 
                           
                         
                       
                       
                         
                           
                             t 
                             5 
                           
                         
                         
                           
                             t 
                             6 
                           
                         
                         
                           
                             
                               t 
                               3 
                             
                             + 
                             k 
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   1.16 
                   ) 
                 
               
             
           
         
       
     
         [0044]    Spatial smoothing may be performed  120  on the tensor elements t 1 -t 6 . In addition, the scalar k may be estimated 182 (e.g., using equation (1.9)). The smoothed tensor elements and the scalar k may be used to calculate  121  optical flow values. The optical flow values may be calculated in accordance with equation (1.11) above. 
         [0045]    Smoothing mask parameters may be determined by factors such as mask shape, mask size, and mask kernel components. In one implementation, the size of the smoothing mask that is used to perform spatial smoothing  118  on the derivative frames is 5-by-5, the size of the smoothing mask that is used to perform spatial smoothing  120  on the tensor elements is 3-by-3, and the size of the smoothing mask that is used to perform spatial smoothing  123  on the optical flow values is 7-by-7. 
         [0046]    As for mask shape, a square mask may be used for the sake of simplicity and efficiency. Parameters of all the smoothing masks may be in the shape of a Gaussian function. To save hardware resources, a 2D Gaussian mask may be decomposed into two 1D Gaussian masks which are cascaded and convolved along the x and y directions separately. 
         [0047]    There may be three types of frames in the system: (1) image frames captured by the camera, (2) derivative frames calculated by the DER module  103 , and (3) optical flow fields calculated by the OFC module  104 . The DER module  103  may use the raw images as input and the OFC module  104  may use the output from the DER module  103  (derivative frames) as the input. As shown in  FIG. 4 , three linked lists may be used to store these frames and maintain their temporal correspondence. An FTE (frame table entry) linked list  125  may be used to store image frames, a DER_FTE linked list  126  may be used to store derivative frames, and an OFC_FTE linked list  127  may be used to store optical flow frames. In one implementation, there may be five corresponding pairs of frames in the FTE linked list  125  and the DER_FTE linked list  126 , and there may be three corresponding pairs of frames in the DER_FTE linked list  126  and the OFC_FTE linked list  127 . 
         [0048]    The software that is running on the optical flow sensor  100  may include an FTE interrupt handler and a DER_FTE interrupt handler. When a new raw image is captured (e.g., FTE7), the camera core may invoke an interrupt. This interrupt may be sensed by the FTE interrupt handler and a trigger signal may be generated and sent to the DER module  103  to initiate a derivative computation. When a new set of derivative frames is calculated (e.g., DER_FTE4), the DER module  103  may invoke an interrupt. This interrupt may be sensed by the DER_FTE interrupt handler and a trigger signal may be generated and sent to the OFC module  104  to initiate an optical flow computation. 
       2. Obstacle Detection for an Unmanned Ground Vehicle Using Optical Flow 
       [0049]    2.1 Algorithm Formulation 
         [0050]    The algorithm that is developed in this section relies on the following assumption: 
         [0051]    Assumption #1: The vehicle moves on a planar ground plane. This assumption is true for vehicle under most circumstances and it limits the degrees of freedom of the vehicle moving on this plane. 
         [0052]    2.1.1 Motion Model Deduction 
         [0053]    Optical flow is a 2D projection of 3D motion in the world on the image plane. The camera frame model depicts the spatial relationship between one point in the world and the camera. Suppose at time t, a point P=(X, Y, Z) T  in the camera frame is projected onto p=(x, y, f) T  on the image frame where f is the focal length as shown in  FIG. 5 . Three projection models can be used to model the projection from the camera frame to the image frame: the perspective projection model, the weak perspective projection model, and the pinhole camera model. In the present disclosure, a perspective projection model is used because it is the closest to the physical model of the three. In the perspective projection model: 
         [0000]    
       
         
           
             
               
                 
                   p 
                   = 
                   
                     f 
                      
                     
                       P 
                       Z 
                     
                   
                 
               
               
                 
                   ( 
                   2.1 
                   ) 
                 
               
             
           
         
       
     
         [0054]    At time t′, it will be assumed that a point P moves to P′=(X′, Y′,Z′) T  which is p′=(x′, y′, f) T  on the image frame. The motion vector in the 3D world is V=(P−P′) T =(X−X′, Y−Y′, Z−Z′) T . On the image plane, the 2D projected motion vector (optical flow) can be represented as v=(p−p′) T =(x−x′, y−y′, 0) T . Because the third component of v (the focal length f) is cancelled out, v=(p−p′)T=(x−x′, y−y′) T  is used instead. 
         [0055]    Rigid motion for one point in the camera frame could be formulated as: 
         [0000]        v=−T−ω×P   (2.2)
 
         [0056]    where T=(T x , T y , T z ) T  is the translational component and ω=(ω x , ω y , ω z ) T  is the rotational component. 
         [0057]    Each component of V can be represented as: 
         [0000]        V   x   =−T   x −ω y   Z+ω   z   Y  
 
         [0000]        V   y   =−T   y −ω z   X+ω   x   Z  
 
         [0000]        V   z   =−T   z −ω x   Y+ω   y   X   (2.3)
 
         [0058]    To convert the motion in the camera frame to optical flow, which is the projected motion on the image plane, the derivative of equation (2.1) can be calculated as: 
         [0000]    
       
         
           
             
               
                 
                   v 
                   = 
                   
                     
                       
                          
                         p 
                       
                       
                          
                         t 
                       
                     
                     = 
                     
                       f 
                        
                       
                         
                           ZV 
                           - 
                           
                             
                               V 
                               Z 
                             
                              
                             P 
                           
                         
                         
                           Z 
                           2 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.4 
                   ) 
                 
               
             
           
         
       
     
         [0059]    By combining equations (2.3) and (2.4), components of v are derived as: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             v 
                             x 
                           
                         
                       
                       
                         
                           
                             v 
                             y 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       
                         
                           ω 
                           x 
                         
                         f 
                       
                        
                       
                         ( 
                         
                           
                             
                               xy 
                             
                           
                           
                             
                               
                                 
                                   y 
                                   2 
                                 
                                 + 
                                 
                                   f 
                                   2 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         
                           ω 
                           y 
                         
                         f 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   - 
                                   
                                     x 
                                     2 
                                   
                                 
                                 - 
                                 
                                   f 
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 - 
                                 xy 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         ω 
                         z 
                       
                        
                       
                         ( 
                         
                           
                             
                               y 
                             
                           
                           
                             
                               
                                 - 
                                 x 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         1 
                         Z 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     T 
                                     z 
                                   
                                    
                                   x 
                                 
                                 - 
                                 
                                   
                                     T 
                                     x 
                                   
                                    
                                   f 
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     T 
                                     z 
                                   
                                    
                                   y 
                                 
                                 - 
                                 
                                   
                                     T 
                                     y 
                                   
                                    
                                   f 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.5 
                   ) 
                 
               
             
           
         
       
     
         [0060]    There are six motion parameters representing the rigid motion of one point in the camera frame. Retrieving all these six motion parameters from the two components (i.e., ν x  and ν y ) of the optical flow vector is an ill-conditioned problem. It would be even harder to classify based on these motion parameters. Therefore, to improve this situation, motion patterns are often restricted to a certain number of degrees of freedom for specific applications. For ground vehicle applications, it is usually assumed that the vehicle travels on a planar surface. It was determined that two parameters—namely (ω y ,T z ) as shown in FIG.  6 —could work well for obstacle detection for a forward-looking camera mounted on a ground vehicle traveling on a planar surface. More importantly, with this two-parameter setting, the obstacle detection algorithm only requires simple linear algebra which can be efficiently implemented in hardware for real-time performance. Equation (2.5) can be reorganized as: 
         [0000]    
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           
                             v 
                             x 
                           
                         
                       
                       
                         
                           
                             v 
                             y 
                           
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       
                         
                           ω 
                           y 
                         
                         f 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   - 
                                   
                                     x 
                                     2 
                                   
                                 
                                 - 
                                 
                                   f 
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 - 
                                 xy 
                               
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         1 
                         Z 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   T 
                                   z 
                                 
                                  
                                 x 
                               
                             
                           
                           
                             
                               
                                 
                                   T 
                                   z 
                                 
                                  
                                 y 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.6 
                   ) 
                 
               
             
           
         
       
     
         [0061]    This equation is composed of two parts, rotation and translation. The rotational component is associated with ω y  and the translational component is associated with T z . As seen in equation (2.6), the rotational component does not carry any depth information. The translational motion is the one containing the depth information. The translational component should be decoupled from the rotational component first so that the de-rotated motion field can be analyzed to determine the obstacle&#39;s distance to the camera. With the description above, the obstacle detection problem can be defined in the following manner: Given a sequence of optical flow fields, estimate the two motion parameters yaw ω y  and forward translation T z  according to the planar surface assumption and identify pixels with an inconsistent motion pattern as obstacles. This algorithm attempts to estimate the parameters one at a time and can be decomposed into three steps: de-rotation (estimate ω y ), de-translation (estimate T Z ) and post-processing (identify inconsistent points). 
         [0062]    Before proceeding, two more assumptions will be made. 
         [0063]    Assumption #2: The ground plane occupies a dominant region of the image. With this assumption, it can be assumed that the ground motion parameters can be extracted from the optical flow field that contains obstacle pixels with inconsistent motion. 
         [0064]    Assumption #3: The XZ plane of the camera frame is parallel to the ground plane. This assumption is valid if the camera is mounted on the vehicle correctly. 
         [0065]    2.1.2 De-Rotation 
         [0066]    The motion field is studied first without any obstacle. With assumptions #1 and #2, it is shown below that on the image plane, depth is related to the y coordinate and is independent of the x coordinate. Because the ground plane is in parallel with the XZ plane, in the camera frame the ground plane is formulated as: 
         [0000]      G:Y=Y 0   (2.7)
 
         [0067]    A line l 0  on the ground plane with the depth Z 0  is: 
         [0000]    
       
         
           
             
               
                 
                   L 
                    
                   
                     : 
                   
                    
                   
                       
                   
                    
                   
                     { 
                     
                       
                         
                           
                             Y 
                             = 
                             
                               Y 
                               0 
                             
                           
                         
                       
                       
                         
                           
                             Z 
                             = 
                             
                               Z 
                               0 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.8 
                   ) 
                 
               
             
           
         
       
     
         [0068]    and points on this line satisfy P=(X, Y 0 , Z 0 ) T . According to projection equation (2.1), mapping of P on the image plane is: 
         [0000]    
       
         
           
             
               
                 
                   p 
                   = 
                   
                     
                       f 
                        
                       
                         P 
                         
                           Z 
                           0 
                         
                       
                     
                     = 
                     
                       
                         ( 
                         
                           
                             f 
                              
                             
                               X 
                               
                                 Z 
                                 0 
                               
                             
                           
                           , 
                           
                             f 
                              
                             
                               
                                 Y 
                                 0 
                               
                               
                                 Z 
                                 0 
                               
                             
                           
                           , 
                           f 
                         
                         ) 
                       
                       T 
                     
                   
                 
               
               
                 
                   ( 
                   2.9 
                   ) 
                 
               
             
           
         
       
     
         [0069]    Equation (2.9) depicts that line L with depth Z 0  on the ground plane is mapped to 
         [0000]    
       
         
           
             
               l 
                
               
                 : 
               
                
               
                   
               
                
               y 
             
             = 
             
               f 
                
               
                 
                   Y 
                   0 
                 
                 
                   Z 
                   0 
                 
               
             
           
         
       
     
         [0000]    on the image plane if assumptions #1 and #2 are both satisfied. In other words, the depth of line L can be inferred solely based on its y coordinate on the image plane and its depth Z 0  is independent of x. 
         [0070]    With the above observation, by extracting the ν y  component in equation (2.6), the partial derivative of ν y  can be derived as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             ∂ 
                             
                               v 
                               y 
                             
                           
                           
                             ∂ 
                             x 
                           
                         
                         = 
                         
                           
                             
                               - 
                               
                                 
                                   ω 
                                   y 
                                 
                                 f 
                               
                             
                              
                             y 
                           
                           + 
                           
                             
                               ∂ 
                               
                                 ( 
                                 
                                   
                                     
                                       T 
                                       z 
                                     
                                      
                                     y 
                                   
                                   Z 
                                 
                                 ) 
                               
                             
                             / 
                             
                               ∂ 
                               x 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             
                               - 
                               
                                 
                                   ω 
                                   y 
                                 
                                 f 
                               
                             
                              
                             y 
                           
                           = 
                           β 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.10 
                   ) 
                 
               
             
           
         
       
     
         [0071]    where β is the slope ratio for ν y . β is fixed for each row, if depth Z is not a function of x. This is true if assumptions #1 and #2 are satisfied. Denoting (ν x     i,j   ,ν y     i,j   ) as the optical flow at pixel (i,j), one β j  can be calculated for each row of the optical flow fields while ω y     j    should be the same for all rows. Least squares (LS) estimation is used to correctly estimate β j . For row j: 
         [0000]      ν y     i,j   =β j   x   i +α j   (2.11)
 
         [0072]    where 
         [0000]    
       
         
           
             
               α 
               j 
             
             = 
             
               
                 
                   T 
                   z 
                 
                 
                   Z 
                   j 
                 
               
                
               
                 y 
                 j 
               
             
           
         
       
     
         [0000]    is the translational component which is constant for each row. Without loss of generality, it is assumed that i=1, 2, . . . , 2n+1 and x i =i−n−1ε[−n, n] and the LS solution for β j  is: 
         [0000]    
       
         
           
             
               
                 
                   
                     β 
                     j 
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             
                               2 
                                
                               n 
                             
                             + 
                             1 
                           
                           ) 
                         
                          
                         
                           ∑ 
                           
                             
                               x 
                               i 
                             
                              
                             
                               v 
                               
                                 y 
                                 
                                   i 
                                   , 
                                   j 
                                 
                               
                             
                           
                         
                       
                       - 
                       
                         ∑ 
                         
                           
                             x 
                             i 
                           
                            
                           
                             ∑ 
                             
                               v 
                               
                                 y 
                                 
                                   i 
                                   , 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           ( 
                           
                             
                               2 
                                
                               n 
                             
                             + 
                             1 
                           
                           ) 
                         
                          
                         
                           ∑ 
                           
                             x 
                             i 
                             2 
                           
                         
                       
                       - 
                       
                         
                           ( 
                           
                             ∑ 
                             
                               x 
                               i 
                             
                           
                           ) 
                         
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.12 
                   ) 
                 
               
             
           
         
       
     
         [0073]    For Σ i x i =0, equation (2.12) can be simplified as: 
         [0000]    
       
         
           
             
               
                 
                   
                     β 
                     j 
                   
                   = 
                   
                     
                       ∑ 
                       
                         
                           x 
                           i 
                         
                          
                         
                           v 
                           
                             y 
                             
                               i 
                               , 
                               j 
                             
                           
                         
                       
                     
                     
                       ∑ 
                       
                         x 
                         i 
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.13 
                   ) 
                 
               
             
           
         
       
     
         [0074]    Besides β j , a confidence index c j  can be calculated for each row of the optical flow fields which measures how well this linear model matches the local signal: 
         [0000]    
       
         
           
             
               
                 
                   
                     c 
                     j 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           ∑ 
                           
                             
                               s 
                               i 
                             
                              
                             
                               v 
                               
                                 y 
                                 
                                   i 
                                   , 
                                   j 
                                 
                               
                             
                           
                         
                         ) 
                       
                       2 
                     
                     
                       ∑ 
                       
                         
                           x 
                           i 
                           2 
                         
                          
                         
                           ∑ 
                           
                             v 
                             
                               y 
                               
                                 i 
                                 , 
                                 j 
                               
                             
                             2 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.14 
                   ) 
                 
               
             
           
         
       
     
         [0075]    When most pixels in one row belong to the ground plane, c j  will be close to one. When an obstacle is present, because its depth is different from the ground plane, the linear model in equation (2.11) will not hold and c j  will be smaller. The term c j  is a good indicator of the presence of an obstacle in one row. 
         [0076]    2.1.3 De-Translation 
         [0077]    After the rotation parameter ω y  is obtained, the rotational component can be removed from ν y . From equations (2.9) and (2.11), the resulting de-rotated ν y  component 
         [0000]    
       
         
           
             
               
                 
                   
                     v 
                     
                       y 
                       
                         i 
                         , 
                         j 
                       
                     
                     R 
                   
                   = 
                   
                     
                       α 
                       j 
                     
                     = 
                     
                       
                         
                           
                             T 
                             z 
                           
                           
                             z 
                             j 
                           
                         
                          
                         
                           y 
                           j 
                         
                       
                       = 
                       
                         f 
                          
                         
                           
                             Y 
                             0 
                           
                           
                             Z 
                             j 
                             2 
                           
                         
                          
                         
                           T 
                           z 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.15 
                   ) 
                 
               
             
           
         
       
     
         [0078]    is fixed for each row as well. Again, the true value of the translation parameter T z  is not needed for obstacle detection. Instead, the goal is to identify pixels with depth values different from other pixels on each row. These pixels are considered to be part of the obstacle. 
         [0079]    To simplify the algorithm and make it fit for hardware implementation, the mean of the de-rotated ν y  components is used as the translational component and the de-translated ν y  component for pixel (i,j) in the de-rotated optical flow fields is derived as: 
         [0000]    
       
         
           
             
               
                 
                   
                     v 
                     
                       y 
                       
                         i 
                         , 
                         j 
                       
                     
                     D 
                   
                   = 
                   
                     
                       
                         v 
                         
                           y 
                           
                             i 
                             , 
                             j 
                           
                         
                         R 
                       
                       - 
                       
                         
                           v 
                           _ 
                         
                         
                           y 
                           j 
                         
                         R 
                       
                     
                     = 
                     
                       
                         v 
                         
                           y 
                           
                             i 
                             , 
                             j 
                           
                         
                         R 
                       
                       - 
                       
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               
                                 j 
                                 - 
                                 m 
                               
                             
                             
                               k 
                               = 
                               
                                 j 
                                 + 
                                 m 
                                 - 
                                 1 
                               
                             
                           
                            
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 
                                   - 
                                   n 
                                 
                               
                               
                                 i 
                                 = 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                             
                              
                             
                               ( 
                               
                                 v 
                                 
                                   y 
                                   
                                     i 
                                     , 
                                     k 
                                   
                                 
                                 R 
                               
                               ) 
                             
                           
                         
                         
                           4 
                            
                           m 
                            
                           
                               
                           
                            
                           n 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.16 
                   ) 
                 
               
             
           
         
       
     
         [0080]    ν y   D  may be calculated for each pixel in the de-rotated optical flow fields. After de-translation, if one pixel belongs to the ground plane, its de-translated motion component ν y     i,j     D  should be very close to zero. In comparison, a pixel on the obstacle should have a larger de-translated motion component. The post-processing step in the next section shows how obstacles can be located based on the de-translated motion component value. 
         [0081]    2.1.4 Post-Processing 
         [0082]    Ideally, after the motion field is de-rotated and de-translated, the residual motion components will be zero for ground plane pixels and non-zero for obstacle pixels. This is illustrated in  FIG. 7 . G is a visible point on the ground plane if there is no obstacle. O is the point on the obstacle that blocks point G. Based on equations (2.6) and (2.15), the projected ν y  motion component difference which can be measured from the optical flow estimation is formulated as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           v 
                           y 
                           Δ 
                         
                         = 
                         
                           
                             
                               v 
                               y 
                               G 
                             
                             - 
                             
                               v 
                               y 
                               O 
                             
                           
                           = 
                           
                             
                               ( 
                               
                                 
                                   1 
                                   
                                     Z 
                                     G 
                                   
                                 
                                 - 
                                 
                                   1 
                                   
                                     Z 
                                     O 
                                   
                                 
                               
                               ) 
                             
                              
                             
                               T 
                               z 
                             
                              
                             y 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           f 
                            
                           
                               
                           
                            
                           
                             
                               T 
                               z 
                             
                             ( 
                             
                               
                                 
                                   Y 
                                   G 
                                 
                                 
                                   Z 
                                   
                                     G 
                                     2 
                                   
                                 
                               
                               - 
                               
                                 
                                   Y 
                                   O 
                                 
                                 
                                   Z 
                                   
                                     O 
                                     2 
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           c 
                            
                           
                               
                           
                            
                           f 
                            
                           
                               
                           
                            
                           
                             
                               T 
                               z 
                             
                             ( 
                             
                               
                                 1 
                                 
                                   Z 
                                   G 
                                 
                               
                               - 
                               
                                 1 
                                 
                                   Z 
                                   O 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.17 
                   ) 
                 
               
             
           
         
       
     
         [0083]    where 
         [0000]    
       
         
           
             c 
             = 
             
               
                 
                   Y 
                   G 
                 
                 
                   Z 
                   G 
                 
               
               = 
               
                 
                   Y 
                   O 
                 
                 
                   Z 
                   O 
                 
               
             
           
         
       
     
         [0000]    is the slope ratio for the line passing through point G and O. In equation (2.17), Z G  is the depth for point G and Z O  the depth for point O. As in equation (2.17), the motion difference is proportional to T z  (the translational motion of the camera) and c (the line slope ratio), and the depth difference item. From equation (2.17), it can be concluded as follows. If T Z =0 (no translational motion), the obstacle will not be detectable which agrees with the basic idea of using a single camera for depth estimation. Also, assuming other parameters are fixed, the closer the obstacle is to the camera (smaller Z O ), the bigger the absolute value of equation (2.17) will be. 
         [0084]    In practice, a threshold δ is used to convert the motion component difference image into a binary image indicating the initial obstacle detection result as shown in equation (2.18). Detecting obstacles in this manner has two advantages. First, the operations can be efficiently implemented in hardware. Second, it avoids estimating the obstacle depth Z O  which is not a trivial task in many circumstances. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       b 
                       init 
                     
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 
                                   
                                     v 
                                     y 
                                     Δ 
                                   
                                    
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                     
                                     ) 
                                   
                                 
                               
                               ≥ 
                               δ 
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                 
                                   v 
                                   y 
                                   Δ 
                                 
                                  
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                             
                             &lt; 
                             
                               δ 
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.18 
                   ) 
                 
               
             
           
         
       
     
         [0085]    2.2 Obstacle Detection Module 
         [0086]    An example of an obstacle detection module  200  that implements the algorithm that was described in section 2.1 will now be described in relation to  FIGS. 8-10 . The obstacle detection module  200  may be implemented in an FPGA or an ASIC, so that the obstacle detection module  200  may be installed in an unmanned vehicle for real-time applications. 
         [0087]    As shown in  FIG. 8 , the obstacle detection module may be divided into three sub-modules: a de-rotation sub-module  228 , a de-translation sub-module  229 , and a post-processing sub-module  230 . The de-rotation sub-module  228  may perform the operations of rotation estimation  231  and de-rotation  232 . In addition, the de-rotation sub-module  228  may include a line buffer  233 . The de-translation sub-module  229  may perform the operations of translation estimation  234  and de-translation  235 . In addition, the de-translation sub-module  229  may include a line buffer  236 . The post-processing sub-module  230  may perform a first thresholding operation  237 , a neighborhood census operation  238 , and a second thresholding operation  239 . The output of the post-processing sub-module  230  is the detection result  245 . 
         [0088]    As shown in  FIG. 8 , the ν y  components of the optical flow fields are used by the de-rotation sub-module  228 , the de-translation sub-module  229 , and the post-processing sub-module  230 . The ν x  components of the optical flow fields are not used by the de-rotation sub-module  228 , the de-translation sub-module  229 , or the post-processing sub-module  230 . 
         [0089]    The de-rotation sub-module  228 , the de-translation sub-module  229 , and the post-processing sub-module  230  may be fully pipelined and concatenated in the pipeline. A detailed explanation of each sub-module will be presented in the following subsections. 
         [0090]    2.2.1 De-Rotation Sub-Module 
         [0091]    To obtain an accurate rotation estimation, rotation parameters across multiple rows may be averaged to obtain an averaged parameter. The confidence index in equation (2.14) may be used as weights in averaging. The averaged slope ratio  β  may be expressed as: 
         [0000]    
       
         
           
             
               
                 
                   
                     β 
                     _ 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                         
                           β 
                           j 
                         
                          
                         
                           c 
                           j 
                         
                       
                     
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           1 
                         
                         N 
                       
                        
                       
                         c 
                         j 
                       
                     
                   
                 
               
               
                 
                   ( 
                   2.19 
                   ) 
                 
               
             
           
         
       
     
         [0092]    The de-rotation sub-module  228  is illustrated in  FIG. 9 . The de-rotation sub-module  228  performs a rotation parameter estimation operation  244 . The de-rotation sub-module  228  also includes N line buffers, where N is configurable. A first line buffer  246 , line buffer (N−1)  247 , and line buffer N  248  are shown in  FIG. 9 . 
         [0093]    Pixelwise motion estimation ν y  is the input and it is fed into rotation parameter estimation  244  and the line buffer at the same time. Depending on the number of lines (N) to be averaged, the same number of line buffers are concatenated before ν y  is de-rotated. At the same time, the slope ratio β j  and confidence index c j  for each row are registered and shifted in synchronization with the line buffer. Once the N sets of β j  and c j  are ready, they are averaged as shown in equation (2.19) to obtain  β . Selection of N is a tradeoff between accuracy and processing speed. If N is small, e.g., two,  β  will be sensitive to noise or even corrupted when there are many obstacle pixels in the row. This will cause a bias in the translational component α as shown in equation (2.11) and this bias will be carried into subsequent calculations. The bias is worse for the left-most and right-most regions in the image because x i  has much bigger magnitude along the image boundary as shown in equation (2.11). If N is large, e.g., twenty, it will require hardware resources for line buffering and averaging β j  across twenty rows. Also, when N is too big, β j  will be over-smoothed because of the difference of y as shown in equation (2.10). In one possible implementation, N may be chosen to be eight. 
         [0094]    The de-rotation sub-module  228  also performs an averaging operation  255 . The N slope ratios and N confidence indices are provided as input to the averaging operation  255 . The result of the averaging operation is  β . With  β  estimation, ν y  can be de-rotated to obtain ν y   R .  β  and the output of the first line buffer  246  are provided as input to the de-rotation operation  256 . The result of the de-rotation operation  256  is ν y   R . 
         [0095]    2.2.2 De-Translation Sub-Module 
         [0096]    Similar to the de-rotation sub-module, de-translated motion is calculated in equation (2.16). The averaged translational motion is estimated by averaging the de-rotated motion component across a certain number of rows. There is also a tradeoff which is similar to the de-rotation setting. In one possible implementation, the row number is set to be eight to achieve a balance between accuracy and speed. 
         [0097]    2.2.3 Post-Processing Sub-Module 
         [0098]    The main purpose of post-processing is to filter out the false positives. After the ν y  motion component is de-rotated and de-translated, as shown in  FIG. 8 , it may be binarized by applying a threshold to obtain the initial detection result  245  as shown in equation (2.18). A detection result  245  may be determined for each pixel. 
         [0099]    The binary image b init  may be smoothed in the spatial domain and the temporal domain separately. This smoothing is shown as a neighborhood census operation  238  in  FIG. 8 . The assumption behind spatial and temporal smoothing is that the obstacle is coherent both spatially and temporally. By counting the initial detection results in the spatiotemporal domain, random false positives can be detected. The spatial smoothing calculates the number of initial deleted pixels in a local neighborhood. The temporal smoothing updates the number of overall initial detected pixels in the temporal domain. To efficiently calculate the sum of the detected pixels, the following equation may be applied: 
         [0000]        S   c   =S   l   +S   p   −S   f   (2.20)
 
         [0100]    where S c  is the sum of the current frame (the current frame census  240  in  FIG. 9 ), S l  is the spatial sum of the current frame (i.e., the original sum  241  in  FIG. 9 ), S p  is the sum of the previous frame (i.e., the previous frame census  242  in  FIG. 9 ), and S f  is the spatial sum of the first frame in the temporal volume (i.e., the updated sum  243  in  FIG. 9 ). 
       3. Obstacle Detection for an Unmanned Aerial Vehicle Using Optical Flow 
       [0101]      FIG. 10  illustrates an example of a method for obstacle detection for an unmanned aerial vehicle (UAV). A ridge-regression tensor-based algorithm may be used to calculate  1057  optical flow values to generate a motion field  1059 . An example of such an algorithm was described above in section  1 . 
         [0102]    Texture analysis  1058  may be used to segment video  1060  into regions that have similar image texture. Some examples of these types of regions  1061 ,  1062 ,  1063 ,  1064 ,  1065 ,  1066  are shown in  FIG. 10 . 
         [0103]    Statistical analysis  1067  may be used to segment the motion field  1059  into regions that have similar optical flow characteristics (e.g., vector length and orientation). Some examples of these types of regions  1068 ,  1069 ,  1070 ,  1071 ,  1072 ,  1073  are shown in  FIG. 10 . 
         [0104]    The segmented video  1074  may be merged with the segmented motion field  1075  to generate zones at different distances from the UAV. Some examples of these types of zones  1076 ,  1077 ,  1078 ,  1079 ,  1080 ,  1081  are shown in  FIG. 10 . 
         [0105]    Sometimes, the motion measurement is not accurate due to image noise, brightness change, occlusion, etc. Under these circumstances, other clues such as texture can be incorporated into the analysis in order to improve the accuracy. A cost function can be derived to evaluate the certainty of motion measurement. A statistical framework can be devised to measure the distribution of the measurement and infer a classification from an objective perspective. 
         [0106]    An obstacle detection module for a UAV may be configured to perform the operations that are shown in  FIG. 10 . Such an obstacle detection module may be implemented in an FPGA or an ASIC. This would allow the obstacle detection module to be installed in the UAV in order to perform obstacle detection in real time. 
         [0107]    It is to be understood that the claims are not limited to the precise configuration and components illustrated above. Various modifications, changes and variations may be made in the arrangement, operation and details of the systems, methods, and apparatus described herein without departing from the scope of the claims.