Patent Publication Number: US-2016225161-A1

Title: Method and apparatus for hierachical motion estimation in the presence of more than one moving object in a search window

Description:
TECHNICAL FIELD 
     The invention relates to a method and to an apparatus for hierarchical motion estimation in which motion vectors are refined in successive levels of increasing search window pixel density and/or decreasing search window size. 
     BACKGROUND 
     Estimation of motion between frames of image sequences is used for applications such as targeted content and in digital video encoding. Known motion estimation methods are based on different motion models and technical approaches such as gradient methods, block matching, phase correlation, ‘optical flow’ methods (often gradient-based) and feature point extraction and tracking. They all have advantages and drawbacks. Orthogonal to and in combination with one of these approaches, hierarchical motion estimation allows a large vector search range and is typically combined with block matching, cf. [1],[2]. 
     In motion estimation generally a cost function is computed by evaluating the image signal of two image frames inside a measurement window. 
     Motion estimation faces a number of different situations in image sequences. A challenging one is when motion is estimated for an image location where there are different objects moving at different speed and/or direction. In this case the measurement window covers these different objects so that the motion estimator is distracted by objects other than the intended one. 
     In [3] a method of estimating correspondences between stereo pairs of images is presented. In determining the cost function, the method targets to weight pixels “in proportion of the probability that the pixels have the same disparity”. In order to approach this objective, pixels with similar color and located nearby are preferred by means of two kinds of weights (involving factors determined empirically): one related to color difference, the other related to spatial distance. Unfortunately that method has inherent problems with periodic structures because pixels with same or similar color but a certain distance apart may mislead the motion estimator. Also its concept does not attempt to consider different motion. 
     SUMMARY OF INVENTION 
     A problem to be solved by the invention is to provide reliable motion estimation for image sequences even in situations or locations where the measurement or search window of the motion estimator covers different objects with different motion. 
     Hierarchical motion estimation is used with several levels of hierarchy. In each level the image is prefiltered, e.g. by means of a 2D mean value filter of an appropriate search window size, the filtering strength being reduced from level to level, e.g. by reducing the window size. In each level a block matcher can be used for determining a motion vector for a marker position or a subset of pixels or every pixel of the whole frame in a certain pixel grid. Within the measurement window, the image signal for the related sections of the two frames compared is subsampled as allowed according to the strength of the prefilter. A motion vector (update) is computed, e.g. by log(D)-step search or full search, which optimizes a cost function, e.g. by minimizing SAD (sum of absolute differences) or SQD (sum of squared differences). Motion estimation is carried out with integer-pel resolution first, followed by sub-pel refinement, thereby also reducing computational complexity. The processing described provides a motion vector typically applying to the center pixel of the measurement window. 
     By evaluating the displaced frame differences in the measurement window—after finding an optimum vector at a certain pixel—a segmentation of the measurement window into different moving object regions is carried out. A corresponding segmentation mask is stored and used as an initial mask in the next level of the hierarchy, and a new mask is determined at the end of this level. Several embodiments further enhance the performance of the basic concept. 
     Advantageously, the described processing allows estimating motion and tracking of image content or points of interest with improved reliability and accuracy in situations or image locations where different objects are moving at different speed and/or direction. 
     In principle, the inventive method is adapted for hierarchical motion estimation in which motion vectors are refined in successive levels of increasing search window pixel density and/or decreasing search window size, including the steps:
         within each hierarchical level, after finding an optimum vector at at least one pixel, determining based on said optimum vector the displaced frame difference or absolute displaced frame difference for each pixel of the search window;   determining within said search window two or more groups of these pixels, wherein each of these pixel groups is characterized by a different range of displaced frame difference values or absolute displaced frame difference values for the pixels;   carrying out a segmentation of the search window into different moving object regions by forming pixel areas according to said groups, which areas represent a segmentation mask for the search window;   estimating for at least one of said segmentation areas a corresponding motion vector.       

     In principle, in the inventive hierarchical motion estimator motion vectors are refined in successive levels of increasing search window pixel density and/or decreasing search window size, said hierarchical motion estimator including means adapted to:
         within each hierarchical level, after finding an optimum vector at at least one pixel, determining based on said optimum vector the displaced frame difference or absolute displaced frame difference for each pixel of the search window;   determining within said search window two or more groups of these pixels, wherein each of these pixel groups is characterized by a different range of displaced frame difference values or absolute displaced frame difference values for the pixels;   carrying out a segmentation of the search window into different moving object regions by forming pixel areas according to said groups, which areas represent a segmentation mask for the search window;   estimating for at least one of said segmentation areas a corresponding motion vector.       

    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
       Exemplary embodiments of the invention are described with reference to the accompanying drawings, which show in: 
         FIG. 1  A foreground object moving relative to a background object, and examples where the measurement window of the motion estimator contains image information of one or more objects; 
         FIG. 2  Block diagram of a hierarchical motion estimator; 
         FIG. 3  Example of displacement estimation using four levels of hierarchy; 
         FIG. 4  Example for log(D)-step search in every level of the hierarchy; 
         FIG. 5  Principle of quasi-subsampling in a measurement window; 
         FIG. 6  Principle of quasi-subsampling in a measurement window containing an object boundary; 
         FIG. 7  Block diagram of a hierarchical motion estimator using segmentation; 
         FIG. 8  Hierarchical motion estimator with segmentation initialization; 
         FIG. 9  Further embodiment of a hierarchical motion estimator with segmentation initialization; 
         FIG. 10  Cost computation in motion estimation using segmentation information. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     Even if not explicitly described, the following embodiments may be employed in any combination or sub-combination. 
     If an image sequence contains two or more objects moving in different directions and/or at different speed, the measurement or search window of a (hierarchical) motion estimator—when lying at their edge—will contain image information of all these objects.  FIG. 1  shows foreground object  11  moving relative to a background object and examples where the measurement window of the motion estimator contains image information of one object ( 12 ,  13 ) or more objects ( 14 ,  15 ). Thus there are two or more image parts inside the measurement window moving in different directions and requiring an individual motion vector while known motion estimators can provide just one representative vector, whereby in practice the resulting vector is mostly good and applicable for only one part of the measurement window. 
     With every hierarchy level the hierarchical motion estimator provides true motion vectors closer towards object boundaries (e.g. of a truck on a road), due to the decreasing grid size (i.e. distance of pixels for which a vector is estimated) and/or decreasing size of the measurement window, but not at the boundaries themselves. In the motion compensated image, high ‘displaced frame differences’ (DFD) remain around moving objects, in structured areas of medium-size moving objects, in or around uncovered background regions, and throughout small moving objects, or at least at their front and rear if they are less textured (e.g. a car moving behind a bush). 
     During the motion estimation process—along the levels of the hierarchy or in the search steps of one level—the measurement window may contain well-matched pixels with a low absolute difference (AD) and other pixels with a high AD, all of which add to the sum of absolute differences (SAD) or the sum of differences for a certain test vector. If a vector is to be estimated for a specific pixel location—especially for point-of-interest tracking-, ideally that part of the measurement window should be evaluated only which belongs to the same object as that pixel. 
     In some situations the motion estimator may therefore be misled, e.g. where a foreground object passes by near a point of interest. In such case much of the measurement window is occupied by the misleading object. An improvement can be achieved by taking the vector estimated for the same point of interest in the preceding frame and using it as a candidate vector in the search in the present frame. 
     During the exposure time (which typically is longer under low-light conditions for instance) the sensor elements of a camera integrate the incoming light so that an object moving at high speed relative to the sensor may be blurred. The boundary of a foreground object moving relative to a background object may be smeared and wide, rather than being sharp and narrow. Such situation, however, might be similar in successive frames—a smeared boundary is estimated with respect to a smeared boundary—so that the location of the object boundary might not need to be known with the highest precision. 
     In cases where the foreground object is e.g. a fence through which a background object is seen (between its pickets), an ideal motion estimator would distinguish the two objects inside the measurement window. That is, the decision whether a pixel belongs to the one object or the other is to be taken based just on that sole pixel rather than on its spatial neighborhood which may belong to another object. 
     A. Distinguishing Different Object Areas in the Measurement Window 
     A.1 Basic Processing at the End of the First Level of Hierarchy 
     A first approach of distinguishing different object areas in the measurement window is this: for a vector found at a certain pixel location by the end of the first (i.e. coarsest) level of the hierarchy, the cost function of all pixels in the measurement window is analyzed. If the DFD or absolute DFD is low for the center pixel then all other picture elements in the measurement window that have a low DFD or absolute DFD are considered as belonging to the same object as that center pixel. Otherwise, if the DFD or absolute DFD is high for the center pixel then all other picture elements in the measurement window that have a high DFD or absolute DFD are considered as belonging to the same object as that center pixel. 
     DFDs or absolute DFDs can be related to or translated into probabilities of belonging to the same or another object, resulting in a more continuous decision than a binary one. Such probability, related to an object, reflects also the part of the exposure time for which the camera sensor element has seen that object as mentioned above. 
     As a first approach, a mask with three possible values ‘0’, ‘0.5’ and ‘1’ is computed by comparing the DFD or absolute DFD of each pixel (x,y) against two thresholds: 
     
       
         
           
             
               
                 
                   
                     mask 
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             0 
                           
                           
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 
                                    
                                   
                                     DFD 
                                      
                                     
                                       ( 
                                       
                                         x 
                                         , 
                                         y 
                                       
                                       ) 
                                     
                                   
                                    
                                 
                               
                               &lt; 
                               
                                 thr 
                                 low 
                               
                             
                           
                         
                         
                           
                             1 
                           
                           
                             
                               
                                 if 
                                  
                                 
                                     
                                 
                                  
                                 
                                    
                                   
                                     DFD 
                                      
                                     
                                       ( 
                                       
                                         x 
                                         , 
                                         y 
                                       
                                       ) 
                                     
                                   
                                    
                                 
                               
                               &gt; 
                               
                                 thr 
                                 high 
                               
                             
                           
                         
                         
                           
                             0.5 
                           
                           
                             otherwise 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     The ‘0’ and ‘1’ values denote different object areas while the value of (e.g.) ‘0.5’ expresses some uncertainty. A low absolute DFD thus turns into a mask value of ‘0’ which represents object number ‘0’. 
     mask(x,y) represents a finer and continuous function that translates the absolute DFD into a probability between ‘0’ and ‘1’. One example is the linear function. 
     
       
         
           
             
               
                 
                   
                     mask 
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       min 
                        
                       
                         ( 
                         
                           1 
                           , 
                           
                             max 
                              
                             
                               ( 
                               
                                 0 
                                 , 
                                 
                                   
                                     
                                        
                                       
                                         DFD 
                                          
                                         
                                           ( 
                                           
                                             x 
                                             , 
                                             y 
                                           
                                           ) 
                                         
                                       
                                        
                                     
                                     - 
                                     
                                       thr 
                                       low 
                                     
                                   
                                   
                                     
                                       thr 
                                       high 
                                     
                                     - 
                                     
                                       thr 
                                       low 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Again, a low absolute DFD turns into a mask value of ‘0’ and represents object number ‘0’. 
     A further improvement can be a function (continuously differentiable) with a smooth rather than sharp transition at thr low , and thr high . The following is an exponential function which starts steep and has a saturation towards higher values of |DFD(x,y)|: 
     
       
         
           
             
               
                 
                   
                     
                       mask 
                        
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                     
                     = 
                     
                       max 
                        
                       
                         ( 
                         
                           0 
                           , 
                           
                             1 
                             - 
                             
                                
                               
                                 - 
                                 
                                   
                                     
                                        
                                       
                                         DFD 
                                          
                                         
                                           ( 
                                           
                                             x 
                                             , 
                                             y 
                                           
                                           ) 
                                         
                                       
                                        
                                     
                                     - 
                                     
                                       thr 
                                       low 
                                     
                                   
                                   
                                     
                                       thr 
                                       high 
                                     
                                     - 
                                     
                                       thr 
                                       low 
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     wherein thr high  determines the gradient of the function at |DFD(x,y)|=thr low  which gradient is 1/(thr high −thr low ). For proper setting of the thr low , value, e.g. the noise level present in the image sequence can be taken into account. 
     A.2 Improvement of Initial Identification of Object Areas 
     Another motion estimation step may then be appended,
         either a complete same level of the hierarchy with its log(D)-step search,   or just some of its search steps,   or just the next level of the hierarchy,
 
evaluating just that part of the measurement window given by the above mask, in order to evaluate only that part of the window belonging to the first object.
       

     In case there still remain high absolute DFD values in this part of the window, this may indicate the presence of another object moving with a different speed and/or direction of motion, i.e. with a different motion vector. Therefore the process can be repeated with a further reduced part of the measurement window, and corresponding to further subdivision of the object area which has been identified first. 
     A.3 Initialization of Object Mask 
     A.3.1 First Level of the Hierarchy 
     Before starting motion estimation in the present frame, the information about the shape of the areas within the measurement window and the motion of the two (or more) areas of the measurement window in the previous frame (see above) can be used for predicting or deriving an initial segmentation of the measurement window in the present frame for use in its first (i.e. coarsest) level of the hierarchy. This will reduce the risk of arriving at a false motion estimate right in the beginning if the disturbing object is prominent in its influence, even though perhaps not big in size. 
     In a simplified alternative just one vector is estimated and provided. Before starting motion estimation in the present frame, the information about the shape of the area in the measurement window and maybe also the single motion vector of the window in the previous frame could be used to predict or derive an initial segmentation of the measurement window in the present frame for use in its first level of the hierarchy. Although the window could already contain a bit of a disturbing object which may have moved by a different amount, this portion will, when the object starts entering the window, be small enough to make this processing still successful. 
     An enhanced processing can modify the mask values in an appropriate way in case they are continuous. 
     The first approach is to use the mask derived in the previous frame, with the simplifying assumption that the other object is still at the same relative position. In fact, there will be a spatial offset resulting from the relative true motion of the two objects. 
     Because this initial mask is used (only) for the first level of the hierarchy of the present frame, it can be just the mask resulting from the first level of the hierarchy of the previous frame since this refers to the same sampling grid. 
     A.3.2 Second and Further Levels of the Hierarchy 
     There are challenging situations where the mask resulting from the first level of the hierarchy in the present frame is not useful for the second level as it masks off (far) less pixels than the initial mask obtained from the previous (prey) frame. To overcome such situations, the initial mask can be combined with the present (pres) mask resulting from the first level, e.g. by:
         averaging the two masks:       

       mask 2,pres ( x,y )=(mask 1,prev ( x,y )+mask 1,pres ( x, y ))/2 ;   (4)
         averaging the two masks in a weighted fashion, the weights relating e.g. to the relation of the sums of the mask entries (a high sum relates to a high number of pixels masked off which is supposed to mean a reliable mask):       

                       w   prev     =         Σ     x   ,   y              mask     1   ,   prev            (     x   ,   y     )               Σ     x   ,   y              mask     1   ,   prev            (     x   ,   y     )         +       Σ     x   ,   y              mask     1   ,   pres            (     x   ,   y     )               ;           (   5   )               mask 2,pres ( x,y )= w   prev ·mask 1,prev ( x,y )+(1 −w   prev )·mask 1,pres ( x,y );   (6)
         preferring the initial mask obtained from the previous frame and neglecting the new one if the sum of the initial mask&#39;s entries is higher:       

       mask 2,pres ( x,y )=mask 1,prev ( x, y ).   (7)
 
     Likewise, from the second level of the hierarchy onwards up to the finest level, the mask obtained from the previous level n-1 of the hierarchy in the previous frame can be used instead of the mask obtained from the previous level in the present frame, if the change in length of the present estimated vector compared to the length of the corresponding estimated vector of the previous frame is too large (e.g. by more than a safety factor of ‘4’): 
       mask n,pres ( x,y )=mask n-1,prev ( x,y ).   (8)
 
     In addition, also the vector obtained from the previous frame can be used instead of the present estimated vector if the change in the vector length is too large (e.g. by more than a safety factor of ‘4’): 
         {right arrow over ({circumflex over (d)})}   n,pres ( x,y )= {right arrow over ({circumflex over (d)})}   prev ( x,y ).   (9)
 
     A.4 Utilizing Location Information in Next Level of Hierarchy 
     In the next level of the motion estimation hierarchy, the sections of the measurement window identified in the previous level (and stored for every point of interest to be tracked, or for the complete image) is considered in the motion estimation from the beginning. Interpolation (or repetition of nearest neighbor) of this information to the mostly denser sampling inside the new measurement window is performed, as well as cutting away boundary areas in order to fit the new smaller window. 
     Because the location information relates to the reference image rather than the search image and therefore does not depend on the motion vector, interpolation to the original sampling grid of the image will probably not be necessary. 
     A useful segmentation mask is needed from the first level of the hierarchy in order to make further steps successful. This may be difficult in situations where another object enters and covers much (e.g. half) of the measurement window area while the motion estimator finds a match for the other object with significant DFDs only for a few remaining pixels in the window. 
     A.5 Update of Identification of Object Areas in Each Level 
     At the end of each hierarchical motion estimation level the cost function of all picture elements in the measurement window (without using a mask) using the newly determined vector is analyzed and segmented as above, and the shape of the part of the measurement window to be used for motion estimation of the center pixel is thus updated and refined. This is continued through the following levels of the hierarchy (maybe not through all of them) unless the search window becomes too small. 
     B. Using Probability Values in Cost Function 
     The mask or probability values defined above can be translated (by a given function) into weighting factors for the absolute DFDs inside the measurement window when computing the cost estimate. If a mask value of ‘0’ is supposed to relate perfectly to the intended object area (i.e. object number ‘0’), the mask values are ‘inverted’, i.e. subtracted from ‘1’ in order to derive a probability belonging to that object: 
         p   0 ( x,y )=1−mask( x,y )   (10)
 
       cost=Σ x,y   w ( p   0 ( x,y ))·|DFD( x,y )|.   (11)
 
     In a different embodiment, the probability values themselves are used as weighting factors: 
       cost=Σ x,y   p   0 ( x,y )·|DFD( x,y )|.   (12)
 
     Depending on the low or high value of the absolute DFD of the center pixel, or if motion estimation is carried out for the remaining part of the measurement window, the probability values can be ‘inverted’, i.e. subtracted from ‘1’ in order to derive their proper meaning: 
         p   1 ( x,y )=1 −p   0 ( x,y )=mask( x,y ).   (13)
 
     whereby a segmentation mask masking off disturbing pixels is used to make this method successful. 
     C. Signal-Based and Distance-Based Weights in Cost Function 
     In [3] a method of stereo matching (called “visual correspondence search”) is presented, i.e. an estimation of correspondences between stereo pairs of images. The application involves different perspectives and different depths. In determining the cost function (called “dissimilarity”) the method targets to weight pixels “in proportion of the probability that the pixels have the same disparity”. In order to achieve this objective, pixels with similar color and located nearby are preferred. A pixel q in the measurement window (called “support window”) is weighted by a factor 
         w ( p,q )= k·f   s (Δ c   pq )· f   p (Δ g   pq )   (14)
 
     that includes a constant k and two weights f s  and f p  which depend on the colour difference (Euclidean distance in color space) and the spatial distance of the pixels (and which weights are called “strength of grouping by color similarity” and “strength of grouping by proximity”, respectively)) with 
       Δ c   pq =√{square root over (( L   p   −L   q ) 2 +( a   p   −a   q ) 2 +( b   p   −b   q ) 2 )}  (15)
 
     defined in the CIE Lab color space (which uses L=0 . . . 100, a=−150 . . . +100, b=−100 . . . +150 and which is related to human visual perception) and 
     
       
         
           
             
               
                 
                   
                     
                       
                         f 
                         s 
                       
                        
                       
                         ( 
                         
                           Δ 
                            
                           
                               
                           
                            
                           
                             c 
                             pq 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       exp 
                        
                       
                         ( 
                         
                           - 
                           
                             
                               Δ 
                                
                               
                                   
                               
                                
                               
                                 c 
                                 pq 
                               
                             
                             
                               γ 
                               c 
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       f 
                       p 
                     
                      
                     
                       ( 
                       
                         Δ 
                          
                         
                             
                         
                          
                         
                           g 
                           pq 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     exp 
                      
                     
                       ( 
                       
                         - 
                         
                           
                             Δ 
                              
                             
                                 
                             
                              
                             
                               g 
                               pq 
                             
                           
                           
                             γ 
                             p 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     given without explanation, and probably (not given in the paper) with 
       Δ g   pq =√{square root over (( x   p   −x   q ) 2  +( y   p   −y   q ) 2 )}.   (18)
 
     The constants are given as y c =7 which is said to be a typical value (might refer to the CIELab signal value ranges, maybe to 100), and y p =36 is determined empirically (might refer to the pixel grid as in another paper by the same authors in which the window size is 35×35 pixels and y p =17.5 which is said to be the radius of the window). A measurement window e.g. of size 33×33 is used. The processing is not hierarchical. 
     That idea is transferred to motion estimation between successive frames by means of hierarchical motion estimation. 
     For simplicity, 
       cost=Σ x,y   w ( x,y )·|DFD( x,y )|.   (19)
 
     using luminance only (rather than R, G and B), k=1, and scaling y c  to the bit depth b of the image signal: 
     
       
         
           
             
               
                 
                   
                     
                       γ 
                       c 
                       ′ 
                     
                     = 
                     
                       
                         γ 
                         c 
                       
                       · 
                       
                         
                           
                             2 
                             b 
                           
                           - 
                           1 
                         
                         100 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
     and modifying y p  by considering the factor s of subsampling in the measurement window performed in combination with prefiltering the image signal in the levels of the hierarchy: 
         y′   p   =y   p   ·s .    (21)
 
     D. Description of Figures 
     The hierarchical motion estimator in  FIG. 2  can be used for forward or backward motion estimation (denoted ME). The image input signal is fed to a set of lowpass filters  21 ,  24 ,  27  with increasing pass bandwidth, and via a frame memory  20  to a corresponding set of lowpass filters  23 ,  26 ,  29  with correspondingly increasing pass bandwidth. The output signals of lowpass filters  21  and  23  are used for motion estimation  22  in the first (i.e. the coarsest) hierarchy level. The output signals of lowpass filters  24  and  26  are used for motion estimation  25  in the second hierarchy level, and so on. The output signals of lowpass filters  27  and  29  are used for motion estimation in the last (i.e. finest) hierarchy level. Motion estimator  22  passes its motion vector or vectors found to motion estimator  25  for update. Motion estimator  25  passes its motion vector found to motion estimator  28  for update, and motion estimator  28  outputs the final displacement vector or vectors. 
     An example parameter set for 6 levels of hierarchy is: 
     
       
         
           
               
               
             
               
                   
               
             
            
               
                 Lowpass filter window size: 
                 [17 9 9 5 5 3] 
               
               
                 Vector array grid size iGrid: 
                 [64 32 16 8 4 2] 
               
               
                 Search range (+/−): 
                 [63 31 15 7 3 1] 
               
               
                 Measurement window size iMeasWin: 
                 [257 209 129 65 25 13] 
               
               
                 Factor iSub of subsampling inside measurement 
                 [16 8 8 4 4 2] 
               
               
                 window: 
               
               
                   
               
            
           
         
       
     
       FIG. 3  shows a present frame and a past or future search frame. The present frame contains measurement windows  31  to  34  with decreasing size in corresponding hierarchy levels. The past or future search frame contains corresponding search windows  35  to  38  with decreasing size, and corresponding displacement vector updates  1  to  4 , summing to a corresponding final total motion vector. 
     For the motion of pixel  40  from the present frame to its search window position, a log(D)-step search is depicted in  FIG. 4 , D being the maximal displacement +1. For six levels: max. displacement (i.e. search range) ±63/31/15/7/3/1 pixel would require a 6/5/4/3/2/1-step search, respectively, with step sizes of 32, 16, 8, 4, 2, 1 pixels. 
     As an example a 4-step search is depicted with step sizes of 8, 4, 2, 1 pels or lines. The corresponding lowpass-filtered and subsampled pixels of the search window are marked by ‘1’ in the coarsest level, ‘2’ in the next level, ‘3’ in the following level, and ‘4’ in the finest level of the hierarchy. In the coarsest level motion vector  42  is found, in the next level motion vector update  43  is found, in the following level motion vector update  44  is found, and in the last level a motion vector update is found which adds up to motion vectors  42  to  44  to the total or final motion vector  41 . 
       FIG. 5  shows the principle of quasi-subsampling in the measurement window, and  FIG. 6  shows the principle of quasi-subsampling in a measurement window which contains an object boundary. The crossed pixels are used in ME in the 1st level, and their DFD values are used for segmentation. These pixels are interpolated to the ascending-dash pixels used in ME in the 2nd/3rd level, and their DFD values are used for segmentation. These pixels are interpolated to the descending-dash pixels used in ME in the 4th/5th level, and their DFD values are used for segmentation. These pixels are interpolated to the bold-marked pixels used in ME in the 6th level, and their DFD values are again used for segmentation. That is, the segmentation is coarse and available for a large area in the 1st level, while increasingly finer in an ever smaller part along the levels of the hierarchy. 
       FIG. 7  shows a hierarchical motion estimator with segmentation. The image input signal is fed to a set of lowpass filters  71 ,  74 ,  77  with increasing pass bandwidth, and via a frame memory  70  to a corresponding set of lowpass filters  73 ,  76 ,  79  with correspondingly increasing pass bandwidth. The output signals of lowpass filters  71  and  73  are used for motion estimation  72  in the coarsest, first hierarchy level. The output signals of lowpass filters  74  and  76  are used for motion estimation  75  in the second hierarchy level, and so on. The output signals of lowpass filters  77  and  79  are used for motion estimation in the last (i.e. finest) hierarchy level, and motion estimator  78  outputs the final displacement vector. 
     Motion estimator  72  passes its motion or displacement vector or vectors dv 1  found as well as the corresponding segmentation information si 1  found by the absolute pixel DFD values as described above to motion estimator  75  for update. Motion estimator  75  passes its motion or displacement vector or vectors dv 2  found as well as the corresponding segmentation information si 2  found to motion estimator  78  for update. Motion estimator  78  receives displacement vector or vectors dv N-1  as well as the corresponding segmentation information si N-1  and outputs the final displacement vector or vectors dv N  as well as the corresponding final segmentation information si N . 
       FIG. 8  shows a hierarchical motion estimator with segmentation initialization. The image input signal is fed to a set of lowpass filters  81 ,  84 ,  87  with increasing pass bandwidth, and via a frame memory  80  to a corresponding set of lowpass filters  83 ,  86 ,  89  with correspondingly increasing pass bandwidth. The output signals of lowpass filters  81  and  83  are used for motion estimation  82  in the coarsest, first hierarchy level. The output signals of lowpass filters  84  and  86  are used for motion estimation  85  in the second hierarchy level, and so on. The output signals of lowpass filters  87  and  89  are used for motion estimation in the last (i.e. finest) hierarchy level, and motion estimator  88  out-puts the final displacement vector. 
     Motion estimator  82  passes its motion or displacement vector dv 1  found as well as the corresponding segmentation information si 1  found by the absolute pixel DFD values as described above to motion estimator  85  for update. Motion estimator  85  passes its motion or displacement vector or vectors dv 2  found as well as the corresponding segmentation information si 2  found to motion estimator  88  for update. Motion estimator  88  receives displacement vector or vectors dv N-1  as well as the corresponding segmentation information si N-1  and outputs the final displacement vector or vectors dv N  as well as the corresponding final segmentation information si N . The segmentation information si 1  output from motion estimator  82  (and possibly the segmentation information si N  output from motion estimator  88 ) is fed to a frame delay  801 , which outputs the corresponding segmentation information si 1  from the previous-frame motion estimation as an initialisation segmentation information si init  to motion estimator  82  for evaluation. 
       FIG. 9  basically corresponds to  FIG. 8 , but the initialization segmentation information si init  fed to motion estimator  92  is also fed to (and evaluated in) motion estimator  95 . 
       FIG. 10  depicts cost computation in the motion estimation using segmentation information. The segmentation information si(x,y) is input to a mask-to-object probability calculation step or stage  101 , which outputs a corresponding probability value p 0 (x,y) for an image object in a search window, cf. eq. (10). According to eq. (13), p 0 (x,y) is subtracted from ‘1’ in an ‘inversion’ step or stage  102  if necessary, so as to out-put a corresponding probability value p 1 (x,y). Using a predetermined weighting characteristic for p 1 (x,y), corresponding weights w(x,y) are calculated in weight deriving step or stage  103 , cf. eq. (14). From w(x,y) and related DFD values DFD(x,y), a cost contribution of pixel (x,y), i.e. c(x,y)=p 1 (x,y)·|DFD(x,y)| is computed in step or stage  104 . In step or stage  105  an overall cost value cost is computed therefrom as defined in equations (11), (12) or (19). 
     The described processing can be carried out by a single processor or electronic circuit, or by several processors or electronic circuits operating in parallel and/or operating on different parts of the complete processing. The instructions for operating the processor or the processors according to the described processing can be stored in one or more memories. The at least one processor is configured to carry out these instructions. 
     REFERENCES 
     
         
         [1] M. Bierling, “Displacement Estimation by Hierarchical Blockmatching”, Proc. of 3rd SPIE Symposium on Visual Communications and Image Processing, Cambridge, USA, November 1988; SPIE, vol.1001, Visual Communications and Image Processing, pp.942-951. 
         [2] R. Thoma, M. Bierling, “Motion Compensating Interpolation Considering Covered and Uncovered Background”, Proc. of the 1st International Workshop on 64 kbit/s Coding of Moving Video, 18 Apr. 1989, Hanover, Germany. 
         [3] K. J. Yoon, I. S. Kweon, “Locally Adaptive Support-Weight Approach for Visual Correspondence Search”, Proc. of the International Conference on Ubiquitous Robots and Ambient Intelligence, pp. 506-514, 2004.