Apparatus for and method of robust motion estimation using line averages

• US 8,059,915 B2
• Filed: 11/20/2007
• Issued: 11/15/2011
• Est. Priority Date: 11/20/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: VideoSurf, Inc. (Microsoft Corporation)
• Inventors: Brandt, Achiezer, Sharon, Eitan
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US11/984,670
• Publication Number:
  US 20080159630A1
• Time in Patent Office: 1,456 Days
• Field of Search: 382/266, 382/274, 382/275, 382/286, 382/291, 358/3.26, 358/3.27, 358/463
• US Class Current: 382/286
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments

Abstract

A method of processing an image includes the steps of computing a plurality of line averages for a first image; identifying a set of pairs of line averages having high edge strengths; identifying a set of maximal pairs of line averages from among the set of line averages having high edge strength; expanding each of the maximal pairs of line averages into line stacks to form a set of line stacks; applying the set of line stacks to a second image so as to compute lines averages for the second image; shifting the line stacks to center the stacks on areas of highest edge strength and computing a distance between line stacks of the first and second images.

Claims

1. A method of processing an image comprising the steps of:

computing a plurality of line averages for a first image;

identifying a set of pairs of line averages having high edge strengths;

identifying a set of maximal pairs of line averages from among said set of line averages having high edge strength;

expanding each of said maximal pairs of line averages into line stacks to form a set of line stacks;

applying said set of line stacks to a second image so as to compute lines averages for said second image; and

computing a distance between line stacks of said first and second images.

2. The method according to claim 1 wherein:

said step of identifying said set of pairs of line averages having high edge strength forms clusters of said pairs of line averages having high edge strength; and

said step of identifying a set of maximal pairs of line averages includes eliminating from each of said clusters line averages having adjacent pairs with a higher edge strength.

3. The method according to claim 1 wherein said step of identifying said set maximal pairs of line averages includes suppressing non-maximal pairs of said set of pairs of line averages having high edge strengths by eliminating pairs having any adjacent pairs with higher edge strength.

4. The method according to claim 1 wherein said first and second images are part of a sequence of video images.

5. The method according to claim 1 further comprising a step of translating each of said line stacks of said second image in a direction corresponding to said computed distances.

6. The method according to claim 5 wherein said step of translating includes shifting each of said line stacks in a direction orthogonal to lines of said line stack by a distance equal to respective computed distances to center each of said line stacks on respective areas of highest edge strength

7. The method according to claim 5 wherein said step of translating includes centering said line stacks of said second image on respective areas of highest edge strength.

8. The method according to claim 5 further comprising a step of verifying that all line averages fit to true object motion by compensating for edge movement internal to an object.

9. The method according to claim 1 wherein said step of computing said plurality of line averages includes implementing a Brandt-Dym method to compute said line averages.

10. The method according to claim 1 wherein said step of computing a plurality of line averages for said first image includes computing line averages for sets of line averages, each set having line averages of different geometries.

11. The method according to claim 10 wherein said different geometries include differences based on line length, width, angular orientation or relative position of lines of said pairs of line averages of said first image.

12. The method according to claim 1 wherein said step of computing a plurality of line averages for said first image includes computing line averages across different geometries of lines selected from the group consisting of different line (i) lengths, (ii) widths, (iii) angular orientations, and (iv) positions.

13. The method according to claim 1 wherein said step of computing a plurality of line averages for said first image includes computing an average color intensity value for a plurality of pixels defined by each of said line averages.

14. The method according to claim 1 wherein said step of computing a plurality of line averages for said first image includes computing line averages each spanning a plurality of pixel elements arranged in a rectangular array.

15. The method according to claim 1 wherein said step of identifying said set of pairs of line averages having high edge strengths includes a step of determining an intensity difference between line averages of each of said pairs of line averages.

16. The method according to claim 15 wherein said step of determining an intensity difference includes steps of determining an average pixel intensity of each line average of a pair of said line averages and subtracting said average pixel intensities to produce an edge intensity corresponding to each of said pairs of said line averages.

17. The method according to claim 1 wherein said step of identifying said set of pairs of line averages having high edge strengths includes a step of determining whether a difference in average pixel intensity of neighboring lines satisfies a threshold condition.

18. The method according to claim 1 wherein said step of computing distance between line stacks of said first and second images includes generating a set of motion vectors describing a movement of edges between said first and second images.

19. The method according to claim 1 wherein said step of expanding each of said maximal pairs of line averages into said line stacks to form said set of line stacks includes:

identifying, for each of said maximal pairs, a set of 2ⁿ adjacent line averages wherein n is an integer value great than 1.

20. The method according to claim 19 wherein each of said sets of 2ⁿ adjacent line averages include line averages taken over regions each having a major axis that is substantially parallel to that of the other regions of a set.

21. The method according to claim 1 wherein said step of expanding each of said maximal pairs of line averages into said line stacks to form said set of line stacks includes:

outwardly expanding from a centralized one of said maximal pairs to include, within each of said line stacks, line averages of immediately adjacent lines.

22. A method of calculating motion vectors of an object included in a video comprising the steps of:

identifying, within a first image of said video, pairs of line averages having strong differences indicating high edge strengths;

suppressing non-maximal pairs of said pairs of line averages by eliminating ones of said pairs having adjacent pairs with higher edge strength leaving a plurality of remaining pairs of line averages;

maximizing differences of said remaining pairs of said line averages to obtain local maximum edginess by adjusting line parameters length, width, angular orientation and location of pairs;

expanding said remaining pairs of said line averages into line stacks of lines;

applying said line stacks to a another image of said video;

identifying, for each line stack within said other image, a line pair having maximum differences indicating highest edge strength within line stack;

translating said line stacks within said other image in direction orthogonal to said line stack lines to center line stacks on respective areas of highest edge strength; and

calculating motion vectors between original and translated line stack positions.

23. An apparatus for processing an image, the apparatus comprising:

a line averaging engine configured to compute a plurality of line averages for a first image;

an edge detection engine configured to identify a set of pairs of line averages having high edge strengths;

an edge extraction engine configured to identify a set of maximal pairs of line averages from among said set of line averages having high edge strength;

a stack creation engine configured to expand each of said maximal pairs of line averages into line stacks to form a set of line stacks;

a stack overlay engine configured to apply said set of line stacks to a second image so as to compute lines averages for said second image; and

a motion detection engine configured to compute a distance between line stacks of said first and second images.

26. The apparatus according to claim 23 wherein:

said edge detection engine is further configured to form clusters of said pairs of line averages having high edge strength; and

said edge extraction engine is further configured to eliminate from each of said clusters line averages having adjacent pairs with a higher edge strength.

27. The apparatus according to claim 23 wherein said edge extraction engine is further configured to suppress non-maximal pairs of said set of pairs of line averages having high edge strengths by eliminating pairs having any adjacent pairs with higher edge strength.

28. The apparatus according to claim 23 wherein said first and second images are part of a sequence of video images.

29. The apparatus according to claim 23 further comprising a translating engine configured to translate each of said line stacks of said second image in a direction corresponding to said computed distances.

30. The apparatus according to claim 27 wherein said translating engine is further configured to shift each of said line stacks in a direction orthogonal to lines of said line stack by a distance equal to respective computed distances to center each of said line stacks on respective areas of highest edge strength

31. The apparatus according to claim 27 wherein said translating engine is further configured to center said line stacks of said second image on respective areas of highest edge strength.

32. The apparatus according to claim 27 wherein said translating engine is further configured to verify that all line averages fit to true object motion by compensating for edge movement internal to an object.

33. The apparatus according to claim 23 wherein said line averaging engine is further configured to implement a Brandt-Dym method to compute said line averages.

34. The apparatus according to claim 23 wherein said line averaging engine is further configured to compute line averages for sets of line averages, each set having line averages of different geometries.

35. The apparatus according to claim 32 wherein said different geometries include differences based on line length, width, angular orientation or relative position of lines of said pairs of line averages of said first image.

36. The apparatus according to claim 23 wherein said line averaging engine is further configured to compute line averages across different geometries of lines selected from the group consisting of different line (i) lengths, (ii) widths, (iii) angular orientations, and (iv) positions.

37. The apparatus according to claim 23 wherein said line averaging engine is further configured to average color intensity values for a plurality of pixels defined by each of said line averages.

38. The apparatus according to claim 23 wherein said line averaging engine is further configured to compute line averages each spanning a plurality of pixel elements arranged in a rectangular array.

39. The apparatus according to claim 23 wherein said edge detection engine is further configured to calculate an intensity difference between line averages of each of said pairs of line averages.

40. The apparatus according to claim 37 wherein said edge detection engine is further configured to calculate an average pixel intensity of each line average of a pair of said line averages and subtract said average pixel intensities to produce an edge intensity corresponding to each of said pairs of said line averages.

41. The apparatus according to claim 23 wherein said edge detection engine is further configured to determine a difference in average pixel intensity of neighboring lines satisfies a threshold condition.

42. The apparatus according to claim 23 wherein said motion detection engine is further configured to generate a set of motion vectors describing a movement of edges between said first and second images.

43. The apparatus according to claim 23 wherein said stack creation engine is further configured to identify, for each of said maximal pairs, a set of 2ⁿ adjacent line averages wherein n is an integer value great than 1.

44. The apparatus according to claim 41 wherein each of said sets of 2ⁿ adjacent line averages include line averages taken over regions each having a major axis that is substantially parallel to that of the other regions of a set.

45. The apparatus according to claim 23 wherein said stack creation engine is further configured to outwardly expand from a centralized one of said maximal pairs to include, within each of said line stacks, line averages of immediately adjacent lines.

24. An apparatus for calculating motion vectors of an object included in a video, the apparatus comprising:

a line averaging engine configured to identify, within a first image of said video, pairs of line averages having strong differences indicating high edge strengths;

an edge extraction engine configured to suppressing non-maximal pairs of said pairs of line averages by eliminating ones of said pairs having adjacent pairs with higher edge strength leaving a plurality of remaining pairs of line averages;

a stack creation engine configured to expand said remaining pairs of said line averages into line stacks of lines;

a stack overlay engine configured to apply said line stacks to a another image of said video; and

a motion detection engine configured to;

identify, for each line stack within said other image, a line pair having maximum differences indicating highest edge strength within line stack,

translate said line stacks within said other image in direction orthogonal to said line stack lines to center line stacks on respective areas of highest edge strength, and

calculate motion vectors between original and translated line stack positions.

25. A non-transitory computer usable medium having computer readable program code embodied therein for processing images, the computer readable program code including:

computer readable program code for causing the computer to compute a plurality of line averages for a first image;

computer readable program code for causing the computer to identify a set of pairs of line averages having high edge strengths;

computer readable program code for causing the computer to identify a set of maximal pairs of line averages from among said set of line averages having high edge strength;

computer readable program code for causing the computer to expand each of said maximal pairs of line averages into line stacks to form a set of line stacks;

computer readable program code for causing the computer to apply said set of line stacks to a second image so as to compute lines averages for said second image; and

computer readable program code for causing the computer to compute a distance between line stacks of said first and second images.

46. The computer usable medium according to claim 25 wherein:

said computer readable code for causing the computer to identify said set of pairs of line averages having high edge strength include computer readable code for causing said computer to form clusters of said pairs of line averages having high edge strength; and

said computer readable code for causing the computer to identify a set of maximal pairs of line averages includes computer readable code for causing said computer to eliminate, from each of said clusters, line averages having adjacent pairs with a higher edge strength.

47. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to identify said set maximal pairs of line averages includes computer readable code for causing the computer suppress non-maximal pairs of said set of pairs of line averages having high edge strengths by eliminating pairs having any adjacent pairs with higher edge strength.

48. The computer usable medium according to claim 25 wherein said first and second images are part of a sequence of video images.

49. The computer usable medium according to claim 25 further comprising computer readable code for causing the computer to translate each of said line stacks of said second image in a direction corresponding to said computed distances.

50. The computer usable medium according to claim 49 wherein said computer readable code for causing the computer to translate each of said line stacks includes computer readable code for causing said computer to shift each of said line stacks in a direction orthogonal to lines of said line stack by a distance equal to respective computed distances to center each of said line stacks on respective areas of highest edge strength.

51. The computer usable medium according to claim 49 wherein said computer readable code for causing the computer to translate each line of said line stacks in said second image includes computer readable code for causing the computer to center said line stacks of said second image on respective areas of highest edge strength.

52. The computer usable medium according to claim 49 further comprising computer readable code for causing the computer to verify that all line averages fit to true object motion by compensating for edge movement internal to an object.

53. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to compute said plurality of line averages includes computer readable code for causing the computer to implement a Brandt-Dym method to compute said line averages.

54. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to compute a plurality of line averages for said first image includes computer readable code for causing the computer to compute line averages for sets of line averages, each set having line averages of different geometries.

55. The computer usable medium according to claim 54 wherein said different geometries include differences based on line length, width, angular orientation or relative position of lines of said pairs of line averages of said first image.

56. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to compute a plurality of line averages for said first image includes computer readable code for causing the computer to compute line averages across different geometries of lines selected from the group consisting of different line (i) lengths, (ii) widths, (iii) angular orientations, and (iv) positions.

57. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to compute a plurality of line averages for said first image includes computer readable code for causing the computer to compute an average color intensity value for a plurality of pixels defined by each of said line averages.

58. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to compute a plurality of line averages for said first image includes computer readable code for causing the computer to compute line averages each spanning a plurality of pixel elements arranged in a rectangular array.

59. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to identify said set of pairs of line averages having high edge strengths includes computer readable code for causing the computer to determine an intensity difference between line averages of each of said pairs of line averages.

60. The computer usable medium according to claim 59 wherein said computer readable code for causing the computer to determine an intensity difference includes computer readable code for causing the computer to determine an average pixel intensity of each line average of a pair of said line averages and subtract said average pixel intensities to produce an edge intensity corresponding to each of said pairs of said line averages.

61. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to identify said set of pairs of line averages having high edge strengths includes computer readable code for causing the computer to determine whether a difference in average pixel intensity of neighboring lines satisfies a threshold condition.

62. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to compute said distance between line stacks of said first and second images includes computer readable code for causing the computer to generate a set of motion vectors describing a movement of edges between said first and second images.

63. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to expand each of said maximal pairs of line averages into said line stacks to form said set of line stacks includes computer readable code for causing the computer to:

identify, for each of said maximal pairs, a set of 2ⁿ adjacent line averages wherein n is an integer value great than 1.

64. The computer usable medium according to claim 63 wherein each of said sets of 2ⁿ adjacent line averages include line averages taken over regions each having a major axis that is substantially parallel to that of the other regions of a set.

65. The computer usable medium according to claim 25 wherein said computer readable code for causing the computer to expand each of said maximal pairs of line averages into said line stacks to form said set of line stacks includes computer readable code for causing the computer to outwardly expand from a centralized one of said maximal pairs to include, within each of said line stacks, line averages of immediately adjacent lines.

66. A non-transitory computer usable medium having computer readable program code embodied therein for calculating motion vectors of an object included in a video, the computer readable program code including:

computer readable program code for causing the computer to identify, within a first image of said video, pairs of line averages having strong differences indicating high edge strengths;

computer readable program code for causing the computer to suppress non-maximal pairs of said pairs of line averages by eliminating ones of said pairs having adjacent pairs with higher edge strength leaving a plurality of remaining pairs of line averages;

computer readable program code for causing the computer to maximize differences of said remaining pairs of said line averages to obtain local maximum edginess by adjusting line parameters length, width, angular orientation and location of pairs;

computer readable program code for causing the computer to expand said remaining pairs of said line averages into line stacks of lines;

computer readable program code for causing the computer to apply said line stacks to a another image of said video;

computer readable program code for causing the computer to identify, for each line stack within said other image, a line pair having maximum differences indicating highest edge strength within line stack;

computer readable program code for causing the computer to translate said line stacks within said other image in direction orthogonal to said line stack lines to center line stacks on respective areas of highest edge strength; and

computer readable program code for causing the computer to calculate motion vectors between original and translated line stack positions.