US2006039477A1PendingUtilityA1

Method and apparatus for fast block motion detection

45
Individually held — no corporate assignee on recordPriority: Mar 25, 2002Filed: Oct 18, 2005Published: Feb 23, 2006
Est. expiryMar 25, 2022(expired)· nominal 20-yr term from priority
Inventors:Bernd Oliver Christiansen
G06T 9/004H04N 19/543G06T 7/246H04N 19/54H04N 19/51
45
PatentIndex Score
0
Cited by
0
References
0
Claims

Abstract

A method, system, and/or apparatus for quickly detecting blocks or regions in an image whose pixels that can be coded efficiently by a pointer to the same block occurring in a reference image. The reference image is shared between an encoder and a corresponding decoder. One embodiment of the encoder quickly detects such blocks in an image by: (a) defining features such that substantially fewer features occur in an image than pixels, (b) correlating features in an image to a corresponding feature in the reference image, (c) estimating a displacement vector representative of the displacement of the correlated features, (d) estimating a seed point within the displaced block from which to grow the block, and (e) growing the displaced block to determine its size, shape, and/or dimensions.

Claims

exact text as granted — not AI-modified
1 . A method comprising: 
 correlating at least a first instance of a first feature in a first image to an instance of the first feature in a reference image; and    determining a first region, that occurs in both the first image and the reference image, based on at least the correlation of the first instance of the first feature in the first image to the instance of the first feature in the reference image to code changes between the first image and the reference image.    
   
   
       2 . The method of  claim 1  wherein a feature is defined such that substantially fewer instances of features occur in an image than there are pixels in the image.  
   
   
       3 . The method of  claim 1  wherein a feature is defined as a value hashed from a pixel template.  
   
   
       4 . The method of  claim 1  wherein a feature is defined as a value calculated from a fixed-length horizontal run of pixels.  
   
   
       5 . The method of  claim 1  wherein a feature is defined based on a template of pixels that occurs in a context of a particular arrangement of pixel values.  
   
   
       6 . The method of  claim 5  wherein the first feature occurs in a context in which the pixels defining the context have the same first color, and the first feature's first pixel has a different color than the first color.  
   
   
       7 . The method of  claim 1  further comprising: 
 scanning the first image for one or more instances of one or more features.    
   
   
       8 . The method of  claim 1  wherein the first region that occurs in both the first image and the reference image is possibly displaced between the first image and the reference image.  
   
   
       9 . The method of  claim 1  wherein determining the first region that occurs in both the first image and the reference image is either a verbatim, probabilistic, or approximate determination process.  
   
   
       10 . The method of  claim 1  further comprising:  
     correlating an instance of a second feature in the first image to an instance of the second feature in the reference image, wherein determination of the first region is based on at least the correlation of the first instance of the first feature and the instance of the second feature found in the first image and the reference image.  
   
   
       11 . The method of  claim 1  further comprising: 
 correlating one or more other instances of one or more other features in the first image to instances of the one or more features in one or more reference images, wherein determination of the first region is based on some of the one or more correlated instances of the first feature and the one or more other features found in the first image and the one or more reference images.    
   
   
       12 . The method of  claim 1  wherein the first instance of the first feature is correlated to an arbitrary instance of the same first feature such that a larger region surrounding the instances in the changed image and reference image are likely to match.  
   
   
       13 . The method of  claim 12  wherein the larger regions surrounding the first instance in the changed image and the arbitrary instance in the reference image are likely to match if the number of instances of the first feature in the reference image is less than a particular threshold number.  
   
   
       14 . The method of  claim 1  further comprising:  
     maintaining a table that includes the locations of one or more instances of features in the reference image to expedite the identification of features that occur infrequently.  
   
   
       15 . The method of  claim 14  further comprising: 
 incrementally updating the table as the reference image changes to expedite the correlation process.    
   
   
       16 . The method of  claim 1  wherein correlating features includes 
 comparing the number of instances of the first feature that occur in the reference image to a threshold number, and looking up an arbitrary instance of the first feature in a table that maps features in the reference image if the number of instances of the first feature is less than the threshold number.    
   
   
       17 . The method of  claim 1  wherein correlating features includes 
 comparing pixels underlying the first instance of the first feature to pixels underlying an arbitrary instance of the first feature in the reference image if the number of instances of the first feature is less than a threshold number.    
   
   
       18 . The method of  claim 1  wherein the first region that occurs in both the first image and the reference image is identified by a shape, location, and displacement.  
   
   
       19 . The method of  claim 1  wherein the first region includes one or more blocks, the one or more blocks defining the shape of the region.  
   
   
       20 . The method of  claim 1  wherein determining the first region includes, 
 maximizing the size of the first region by iteratively growing the size of one or more blocks that can be found in both the first image and the reference image.    
   
   
       21 . The method of  claim 20  wherein iteratively growing the size of one or more blocks includes incrementally matching pixels in both the first image and reference image.  
   
   
       22 . The method of  claim 21  wherein the process of matching pixels in both the first image and reference image only some of the pixels for each block are matched.  
   
   
       23 . The method of  claim 1  wherein a first displacement vector of the first region is determined based on at least a displacement of the first instance of the first feature in the first image relative to its correlated instance in the reference image.  
   
   
       24 . The method of  claim 23  wherein the first displacement vector is representative of a threshold percentage of relative displacement vectors for one or more correlated instances of features found in both the first image and the reference image.  
   
   
       25 . The method of  claim 1  wherein the shape of the first region is grown from a selected seed point.  
   
   
       26 . The method of  claim 25  wherein the seed point is determined from the first displacement of the first region and one or more instances of one or more features that support the first displacement vector.  
   
   
       27 . The method of  claim 1  further comprising: 
 selecting a reference image for each instance of a feature, from among multiple reference images, by determining which reference image has the fewest number, but greater than zero, of instances of that feature.    
   
   
       28 . The method of  claim 27  wherein features in the multiple reference images are indexed in one or more tables to expedite the identification of features that occur infrequently.  
   
   
       29 . An apparatus comprising: 
 a feature matching unit configured to detect motion in regions found in both a current image and a reference image by correlating one or more instances of one or more features in the current image to instances of the same features in the reference image; and    a block rendering unit coupled to the feature matching unit, the block rendering unit configured to define a first region that occurs in both the current image and the reference image based on at least the correlation of one or more instances of one or more features found in both the current image and the reference image to code changes between the current image and the reference image.    
   
   
       30 . The apparatus of  claim 29  wherein the feature matching unit is configured to generate a displacement vector for one or more correlated instances of a feature corresponding to a possible displacement of the instances of the features between the reference image and the current image.  
   
   
       31 . The apparatus of  claim 29  wherein a first instance of a first feature is correlated to an arbitrary instance of the same first feature such that a larger region surrounding the instances in the changed image and reference image are likely to match.  
   
   
       32 . The apparatus of  claim 29  wherein the feature matching unit detects motion of a region by 
 comparing the number of instances of a correlated first feature in a feature table of features in the reference image to a threshold number, and    looking up an arbitrary instance of the first feature in the feature table if the number of instances of the first feature in the reference image is less than the threshold number.    
   
   
       33 . The apparatus of  claim 29  wherein the feature matching unit detects motion of a region by 
 comparing pixels underlying an arbitrary instance of a first feature in the reference image to pixels underlying a first instance of the first feature in the current image if the number of instances of the first feature in the reference image is less than a threshold number.    
   
   
       34 . The apparatus of  claim 29  further comprising: 
 a feature extractor to extract instances of features from the current image and provide the instances to the feature matching unit.    
   
   
       35 . The apparatus of  claim 29  further comprising: 
 a feature manager to maintain a feature table of instances of features found in the reference image and provide access to the feature table to the feature matching unit.    
   
   
       36 . The apparatus of  claim 35  wherein for one or more instances of a feature in the feature table a location for that instance is maintained.  
   
   
       37 . The apparatus of  claim 35  wherein the feature table is incrementally updated as the reference image changes to expedite the correlation of instances of features.  
   
   
       38 . The apparatus of  claim 29  wherein the block rendering unit estimates 
 a predominant displacement vector representative of a threshold percentage of displacement vectors for correlated features in the current and reference images.    
   
   
       39 . The apparatus of  claim 29  wherein the block rendering unit estimates 
 a seed point based on one or more instances of features that support a predominant displacement vector.    
   
   
       40 . The apparatus of  claim 29  wherein defining the first region the block rendering unit 
 grows one or more blocks from a seed point location, wherein the one or more blocks can be found in both the current image and the reference image, and    grows the first region by iteratively increasing the size of each of the one or more blocks.    
   
   
       41 . The apparatus of  claim 40  wherein growing one or more blocks includes incrementally matching pixels in both the current image and reference image starting from the seed point.  
   
   
       42 . The apparatus of  claim 29  further comprising: 
 a feature manager to manage the features present in one or more reference images; and    a reference image library coupled to the feature manager, the reference image library to store multiple images, wherein for each instance of a feature in the current image a reference image is selected.    
   
   
       43 . The apparatus of  claim 29  further comprising: 
 an image encoder coupled to the block rendering unit to identify the first region in terms of a shape, location, and displacement.    
   
   
       44 - 48 . (canceled)  
   
   
       49 . An encoder comprising: 
 means for detecting motion of one or more regions found in both a current image and a reference image by correlating instances of one or more features in the current image to instances of the same features in the reference image; and    means for identifying a first region that occurs in both the current image and the reference image, but possibly displaced between the current image and the reference image, based on the correlation of instances of one or more features in the current image to instances of the same features in the reference image to code changes between the current image and the reference image.    
   
   
       50 . The encoder of  claim 49  further comprising: 
 means for extracting instances of features from the current image and provide the instances to the motion detecting means; and    means for maintaining a feature table of instances of features found in the reference image and provide access to the feature table to the motion detecting means.    
   
   
       51 . The encoder of  claim 50  further comprising: 
 means for incrementally updating the feature table as the reference image changes.    
   
   
       52 . The encoder of  claim 49  wherein the means for defining the first region include 
 means for estimating a predominant displacement vector representative of a threshold percentage of displacement vectors corresponding to the displacement of correlated instances of features in the current image and reference image.    
   
   
       53 . The encoder of  claim 49  wherein the means for defining the first region include 
 means for determining a seed point based on one or more features supporting a predominant displacement vector.    
   
   
       54 . The encoder of  claim 49  wherein the means for identifying a first region includes 
 means for growing one or more blocks from a seed point location, wherein the one or more blocks can be found in both the current image and the reference image, and    means for rendering the first region from the union of the one or more blocks.    
   
   
       55 . The encoder of  claim 49  further comprising: 
 means for storing a reference image library to store multiple images, wherein for each instance of a feature in the current image a reference image is selected.    
   
   
       56 . The encoder of  claim 49  further comprising: 
 means for identifying the first region in terms of a shape, location, and displacement between the current image and the reference image.

Join the waitlist — get patent alerts

Track US2006039477A1 — get alerts on status changes and closely related new filings.

We store only your email — no account needed. See our privacy policy.