Method and apparatus for fast block motion detection

• US 20030179951A1
• Filed: 03/25/2002
• Published: 09/25/2003
• Est. Priority Date: 03/25/2002
• Status: Active Grant

• Current Assignee: GOTO Group Incorporated (LogMeIn, Inc.)
• Original Assignee: Citrix Online LLC (Cloud Software Group)
• Inventors: Christiansen, Bernd O.
• Granted Patent: US 6,983,020 B2
• Time in Patent Office: Days
• US Class Current: 382/278
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/543 using regions

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

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. A system comprising:

an encoder configured to

correlate one or more instances of one or more features in a first image to instances of the same features in a reference image,

determine a first region, which occurs in both the first image and the reference image but possibly displaced between the first image and the reference image, based on the correlation of features in the first image to instances of the same features in the reference image; and

a decoder configured to

receive information from the encoder, and

update a second image by employing a copy of the reference image to reconstruct the first region.

45. The system of claim 44 wherein the encoder is further configured to

extract instances of features from the current image, and

maintain a feature table of instances of features found in the reference image.

46. The system of claim 44 wherein the encoder correlates instances of features by

comparing the number of instances of a correlated first feature in the reference image to a threshold number, and

looking up an arbitrary instance of the first feature in a feature table for the reference image if the number of instances of the first feature in the reference image is less than the threshold number.

47. The system of claim 44 wherein the encoder verifies correlated instances of features by

comparing pixels underlying a first instance of a first feature in the first image to pixels underlying an arbitrary instance of the first feature in the reference image if the number of instances of the first feature in the reference image is less than a threshold number.

48. The system of claim 44 wherein

the encoder is further configured to identify the possibly displaced first region by a shape, a location, and a displacement to code and output changes between the first image and the reference image, and

the decoder is further configured to receive the shape, location, and displacement and use them to reconstruct the first region.

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.