Method and apparatus for fast block motion detection

• US 6,983,020 B2
• Filed: 03/25/2002
• Issued: 01/03/2006
• 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.
• Primary Examiner(s): Le, Vu
• Application Number:
  US10/107,981
• Publication Number:
  US 20030179951A1
• Time in Patent Office: 1,380 Days
• Field of Search: 37524012-24017, 348699-700, 348/416.1, 386/109, 386/111, 382/236, 382/243, 345/473
• US Class Current: 375/240.16
• 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, by an encoder, at least a first instance of a first feature in a first image to an instance of the first feature in a reference image;

determining, by the encoder a first region, that occurs in both the first image and the reference image, based on in 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;

receiving, by a decoder, information from the encoder; and

updating, by the decoder, a second image by employing a copy of the reference image to reconstruct the first region.

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 1 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, by the encoder, 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, by the encoder, 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, by the encoder, 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, by the encoder, 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, by the encoder, the table as the reference image changes to expedite the correlation process.

16. The method of claim 1 wherein correlating features includes

comparing, by the encoder, 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, by the encoder, 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, by the encoder, 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, by the encoder, 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 further comprising determining, by the encoder, a first displacement vector of the first region 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 further comprising growing, by the encoder, the shape of the first region from a selected seed point.

26. The method of claim 25 further comprising determining, by the encoder, the seed point 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, by the encoder, 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 further comprising indexing, by the encoder, features in the multiple reference images in one or more tables to expedite the identification of features that occur infrequently.

29. 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.

30. The system of claim 29 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.

31. The system of claim 29 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.

32. The system of claim 29 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 die reference image if the number of instances of the first feature in the reference image is less than a threshold number.

33. The system of claim 29 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.

34. A system comprising:

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; and

a decoder comprising

means for receiving information from the encoder; and

means for updating a second image by employing a copy of the reference image to reconstruct the first region.

35. The system of claim 34 further comprising an encoder further comprises:

means for extracting instances of features from the current image and for providing the instances to the motion detecting means; and

means for maintaining a feature table of instances of features found in the reference image and for providing access to the feature table to the motion detecting means.

36. The system of claim 35 further comprising an encoder further comprising:

means for incrementally updating the feature table as the reference image changes.

37. The system of claim 34 wherein the encoder further comprises:

means for defining the first region including 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.

38. The system of claim 34 wherein the encoder further comprises:

means for defining the first region including means for determining a seed point based on one or more features supporting a predominant displacement vector.

39. The system of claim 34 wherein the encoder further comprises:

means for identifying a first region including 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.

40. The system of claim 34 further comprising an encoder 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.

41. The system of claim 34 further comprising an encoder further comprising:

means for identifying the first region in terms of a shape, location, and displacement between the current image and the reference image.