General pose refinement and tracking tool

• US 8,437,502 B1
• Filed: 09/25/2004
• Issued: 05/07/2013
• Est. Priority Date: 09/25/2004
• Status: Active Grant

• Current Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Original Assignee: Cognex Technology & Investment Corporation (Cognex Corporation)
• Inventors: Davis, Jason, Siddiqui, Matheen
• Primary Examiner(s): Chu, Randolph I
• Assistant Examiner(s): BLOOM, NATHAN J
• Application Number:
  US10/949,530
• Time in Patent Office: 3,146 Days
• Field of Search: 382/106, 382/159, 382/209, 382215-216, 382/284, 382293-296
• US Class Current: 382/103
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

Per one embodiment, a method is provided for refining a pose estimate of a model. The model is coarsely aligned with a run-time image, and it represents a 2D pattern. The pose estimate includes at least one pose estimate parameter. The model has a plurality of model features, and the run-time image has a plurality of run-time features. A given distance value is determined representing a given distance between a given one of the plurality of the model features mapped by a given pose estimate and a corresponding given run-time feature. A two-dimensional model description of the two-dimensional model pattern is provided. The two-dimensional model pattern is mapped using the given pose estimate to create a transformed version of the two-dimensional model pattern. The transformed version represents a non-linear movement of at least portions of the two-dimensional model pattern in a direction orthogonal to a plane of the two-dimensional model description.

Claims

1. A method for refining a pose estimate of a model coarsely aligned with a run-time image, the pose estimate having at least one parameter, the model having a plurality of model edgelets, the run-time image having a plurality of run-time edgelets, each edgelet having a position and an orientation, the method comprising:

mapping the position and orientation of each model edgelet onto the run-time image using the pose estimate to provide a plurality of mapped edgelets;

for each mapped edgelet, finding all run-time features having a position within a distance capture range of the mapped edgelet, and having an orientation within an angular capture range of the mapped edgelet, and having an orientation within an angular capture range of the mapped edgelet, so as to provide a correspondence list of run-time features of the mapped edgelet, thereby providing a plurality of correspondence lists;

for each mapped edgelet, finding a closest run-time edgelet within the correspondence list of the mapped edgelet;

for each mapped edgelet, finding a distance between the mapped edgelet and the closest run-time edgelet within the correspondence list of the mapped edgelet; and

modifying the at least one parameter of the pose estimate so as to minimize an average over the plurality of mapped edgelets of the distance between each mapped edgelet and the closest run-time edgelet within the correspondence list of the mapped edgelet.

2. The method of claim 1, wherein the distance is the point-to-line distance between the mapped edgelet and the closest run-time edgelet within the correspondence list of the mapped edgelet.

3. The method of claim 1, wherein modifying the at least one parameter of the pose estimate so as to minimize an average over the plurality of mapped edgelets of the distance proceeds as an iterative loop.

4. The method of claim 3, wherein the iterative loop is terminated when a number of iterations of the iterative loop reach a maximum number of iterations.

5. The method of claim 3, wherein the iterative loop is terminated when the average over the plurality of mapped edgelets of the distance is less than an average distance threshold.

6. The method of claim 3, wherein the iterative loop is terminated when a change in the at least one parameter per iteration is less than a change threshold.

7. The method of claim 1, further comprising:

performing data-reduction on the model prior to mapping the position and orientation of each model edgelet.

8. The method of claim 7, wherein performing data-reduction includes chaining model edgelets, and discarding edgelets not included in a chain of edgelets.

9. The method of claim 7, wherein performing data-reduction includes discarding every n^th edgelet, where n is an integer selected so as to reduce computation overhead while preserving sufficient accuracy for an application to which the method is applied.

10. The method of claim 1, wherein the plurality of model edgelets are obtained by first sub-sampling a model image to provide a sub-sampled model image, and then edge detecting the sub-sampled model image to provide a model having a plurality of edgelets.

11. The method of claim 1, wherein modifying the at least one parameter of the pose estimate includes:

computing a search direction in pose parameter space; and

incrementing the pose parameter in the search direction in pose parameter space.

12. the method of claim 11, wherein the search direction is in the direction of one of gradient and robust gradient.

13. The method of claim 1, wherein the distance capture range of the mapped edgelet is sized so as to capture some run-time image edgelets in portions of a run-time image having an edge, and so as not to capture any run-time image edgelets in portions of the run-time image not having an edge.

14. The method of claim 1, wherein the average is an arithmetic average.

15. The method of claim 1, wherein the average is a root mean squared average.

16. The method of claim 1, wherein the pose estimate is a non-linear pose estimate.

17. the method of claim 16, wherein the non-linear pose estimate is a non-linear transformation selected from the group including:

perspective, cylinder, cone, polynomial, and thin-plate spline.

18. The method of claim 1, wherein modifying the at least one parameter of the pose estimate so as to minimize an average over the plurality of mapped edgelets of the distance proceeds as an iterative loop,

the iterative loop using only run-time image edgelets that are located within a consider range of each mapped edgelet that was mapped by the pose estimate prior to the iterative loop.

19. The method of claim 18, wherein each iteration of the iterative loop uses only run-time edgelets that are within a capture range of each mapped edgelet that was mapped by a current estimate of the pose, and

the capture range is sized smaller than the consider range so as to effectively reduce the influence of outliers and spurious run-time image edgelets.

20. A method for refining a pose estimate of a model coarsely aligned with a run-time image, the pose estimate including at least one parameter, the method comprising:

providing a pose estimate to be refined, the pose estimate being characterized by at least one parameter;

extracting edgelets from a model image so as to provide a model having a plurality of model edgelets, each model edgelet having a position and an orientation;

extracting edgelets from the run-time image so as to provide a plurality of run-time edgelets, each run-time edgelet having a position and an orientation;

mapping the position and orientation of each model edgelet onto the run-time image using the pose estimate to provide a plurality of mapped edgelets;

pairing each mapped edgelet with a run-time edgelet to provide a plurality of edgelet pairs;

for each edgelet pair, finding a distance between the mapped edgelet and the run-time edgelet paired with the mapped edgelet; and

modifying at least one parameter of the pose estimate so as to minimize an average over the plurality of edgelet pairs of the distance between the mapped edgelet and the run-time edgelet paired with the mapped edgelet.

21. The method of claim 20, wherein the run-time edgelet of an edgelet pair is selected from a plurality of run-time edgelets.

22. The method of claim 20, wherein pairing each mapped edgelet with a run-time edgelet includes:

finding all run-time features having a position within a distance capture range of the mapped edgelet, and having an orientation within an angular capture range of the mapped edgelet, so as to provide a correspondence list of run-time features of the mapped edgelet, thereby providing a plurality of correspondence lists; and

finding a closet run-time edgelet within the correspondence list of the mapped edgelet.

23. The method of claim 20, wherein extracting features from the model image includes:

sub-sampling the model image to provide a sub-sampled model image; and

detecting edges in the sub-sampled model image to provide a model having a plurality of edgelets.

24. A method for refining a non-linear pose estimate of a model coarsely aligned with a run-time image, the non-linear pose estimate having at least one parameter, the model having a plurality of model edgelets, the run-time image having a plurality of run-time edgelets, each edgelet having a position and an orientation, the method comprising:

modifying the at least one parameter of the pose estimate so as to minimize an average distance taken over a plurality of model edgelets mapped by the pose estimate, the distance being the distance between each model edgelet mapped by the pose estimate and a corresponding run-time edgelet;

wherein the corresponding run-time edgelet is the run-time edgelet that is closest to the model edgelet mapped by the pose estimate;

wherein the corresponding run-time edgelet is the run-time edgelet that is closest to the model edgelet mapped by the pose estimate, and also falls within a capture range; and

wherein the capture range includes both a distance capture range, and an angle capture range.

25. The method of claim 24, wherein each corresponding edgelet is included in a correspondence list.

26. The method of claim 25, wherein the correspondence list is a list of lists.

27. The method of claim 24, wherein modifying the at least one parameter of the pose estimate is performed iteratively.

28. A method for tracking the motion of a pattern in an image undergoing a non-linear deformation over a sequence of images, the method comprising:

providing a current pose of a model aligned with a first image of the sequence, the current pose being a non-linear transformation having at least one parameter;

providing a second image of the sequence of images, the second image having a plurality of second image edgelets, each second image edgelet having a position and an orientation;

mapping the position and orientation of each model edgelet onto the second image using the current pose of the model in the first image to provide a plurality of mapped edgelets;

for each mapped edgelet, finding all second image features having a position within a distance capture range of the mapped edgelet, and having an orientation within an angular capture range of the mapped edgelet, so as to provide a correspondence list of run-time features of the mapped edgelet, thereby providing a plurality of correspondence lists;

for each mapped edgelet, finding a closest run-time edgelet within the correspondence list of the mapped edgelet;

for each mapped edgelet, finding a distance between the mapped edgelet and the closest second image edgelet within the correspondence list of the mapped edgelet; and

modifying the at least one parameter of the current pose so as to minimize an average over the plurality of mapped edgelets of the distance between each mapped edgelet and the closest second image edgelet within the correspondence list of the mapped edgelet, thereby providing an updated pose.

29. The method of claim 28, wherein the distance is the point-to-line distance between the mapped edgelet and the closest second image edgelet within the correspondence list of the mapped edgelet.

30. The method of claim 28, wherein modifying the at least one parameter proceeds as an iterative loop.

31. The method of claim 30, wherein the iterative loop is terminated when a number of iterations of the iterative loop reaches a maximum number of iterations.

32. The method of claim 30, wherein the iterative loop is terminated when the average over the plurality of mapped edgelets of the distance is less than an average distance threshold.

33. The method of claim 30, wherein the iterative loop is terminated when a change in the at least one parameter per iteration is less than a change threshold.

34. The method of claim 28, further comprising:

performing data-reduction on the model prior to mapping the position and orientation of each model edgelet.

35. The method of claim 34, wherein performing data-reduction includes chaining model edgelets, and discarding edgelets not included in a chain of edgelets.

36. The method of claim 34, wherein performing data-reduction includes discarding every n^th edgelet, where n is an integer selected so as to reduce computation overhead while preserving sufficient accuracy for an application to which the method is applied.

37. The method of claim 28, wherein the plurality of model edgelets are obtained by first sub-sampling a model image to provide a sub-sampled model image, and then edge detecting the sub-sampled model image to provide a model having a plurality of edgelets.

38. The method of claim 28, wherein modifying the at least one parameter of the pose estimate includes:

computing a search direction in pose parameter space; and

incrementing the pose parameter in the search direction in pose parameter space.

39. the method of claim 38, wherein the search direction is in the direction of one of:

gradient and robust gradient.

40. The method of claim 28, wherein the distance capture range of the mapped edgelet is sized so as to capture some run-time image edgelets in portions of a run-time image having an edge, and so as not to capture any run-time image edgelets in portions of the run-time image not having an edge.

41. The method of claim 28, wherein the average is an arithmetic average.

42. The method of claim 28, wherein the average is a root mean squared average.

43. The method of claim 28, wherein the pose estimate is a non-linear pose estimate.

44. The method of claim 43, wherein the non-linear pose estimate is a non-linear transformation selected from the group including:

perspective, cylinder, cone, polynomial, and thin-plate spline.

45. A method for refining a pose estimate of a model coarsely aligned with a run-time image, the model representing a two-dimensional pattern, the pose estimate including at least one pose estimate parameter, the model having a plurality of model features, the run-time image having a plurality of run-time features, the method comprising:

determining a given distance value representing a given distance between at (east a given one of the plurality of the model features mapped by a given pose estimate and a corresponding given run-time feature;

providing a two-dimensional model description of the two-dimensional model pattern; and

mapping the two-dimensional model pattern using the given pose estimate to create a transformed version of the two-dimensional model pattern, the transformed version representing a non-linear movement of at least portions of the two-dimensional model pattern in a direction orthogonal to a plane of the two-dimensional model description.

46. The method according to claim 45, wherein the model includes a geometric model.

47. The method according to claim 45, wherein the model features include model edgelets and wherein the run-time features include run-time edgelets.

48. The method according to claim 45, wherein plural distance values are determined respectively representing distances between individual ones of a plurality of the model features mapped using the given pose estimate and corresponding run-time features.

49. The method according to claim 45, further comprising modifying the at least one pose estimate parameter in order to reduce the given distance as represented by the given distance value.

50. The method according to claim 49, wherein the mapping includes a cylindrical mapping.

51. The method according to claim 49, wherein the mapping includes a perspective mapping.

52. A method comprising:

representing relative movement over time of a three dimensional target object with a sequence of image frames;

producing a model from a training image of an object, the model including model features of a portion of the target object, the model representing a two-dimensional model pattern;

tracking iteratively the target object from a given image frame of the image frames, while, for each iteration of the tracking, incrementing the given image frame to be a next image frame;

a given iteration of the tracking including, for a given run-time image within the given frame;

producing a current pose estimate configured to attempt to align the model features with the given run-time image;

mapping the model features using the current pose estimate;

refining the current pose estimate to produce a refined pose estimate, the refining including modifying at least one parameter of the current pose estimate to reduce a given distance between at least a given mapped model feature mapped using the current pose estimate and a corresponding run-time feature;

repeating both the mapping and the refining, while each time treating the most recently refined pose estimate as the current pose estimate; and

wherein the current pose estimate is used to map the model features to create a transformed version of the two-dimensional model pattern, the transformed version representing a perspective or deformed non-linear movement of at least portions of the two- dimensional model pattern in a direction orthogonal to a plane of the two-dimensional model pattern.

53. The method according to claim 52, wherein the sequence of image frames includes image frames taken by a camera.

54. The method according to claim 52, wherein the sequence of image frames includes image frames taken from different camera views.

55. The method according to claim 52, wherein the sequence of image frames includes image frames taken from a common camera view.

56. The method according to claim 52, further comprising obtaining a training image that is a flat feature of a three-dimensional training object and determining the two-dimensional model pattern from the training image.

57. The method according to claim 52, wherein the model features are obtained from a two-dimensional template requiring a non-linear transformation to map from the template to the given run-time image.

58. The method according to claim 52, further comprising producing the model features with a training process including imaging orthogonally to a 2D pattern.

59. The method according to claim 58, wherein the training process includes training with a real training image.

60. The method according to claim 58, wherein the training process includes training with a synthetic training image.

61. The method according to claim 52, further comprising extracting the model features from a two-dimensional training image.

62. The method according to claim 52, wherein one of the current pose estimates includes a coarsely aligned pose estimate.

63. The method according to claim 52, wherein a given run-time feature is deemed to be the corresponding run-time feature corresponding to the given mapped model feature when it is a member of a set of considered run-time features to be considered as possibly corresponding to the given mapped model feature.

64. The method according to claim 52, wherein the repeating of both the mapping and the refining includes repeating both the mapping and the refining up to a maximum number of iterations.

65. The method according to claim 52, wherein the repeating of both the mapping and the refining includes repeating both the mapping and the refining up to a number iterations determined as a function of the given distance.

66. The method according to claim 52, wherein the repeating of both the mapping and the refining includes repeating both the mapping and the refining up to a number of iterations coinciding with when the average, over a plural set of the mapped features, of the given distance is less than an average distance threshold.

67. The method according to claim 52, wherein the model features and the run-time features include edge-based features.

68. The method according to claim 52, wherein the model features and the run-time features include edgelets.

69. The method according to claim 52, wherein the model features and the run-time features include chains of edgelets.

70. The method according to claim 52, wherein the model features and the run-time features include features involving detection and sub-pixel location of edges.

71. A method comprising:

representing relative movement over time of a three-dimensional object with a sequence of image frames;

producing a model from a training image of an object, the model representing a two-dimensional model pattern;

for a given image frame, producing a coarsely aligned pose estimate of the model pattern coarsely aligned with a given run-time image within the given image frame by performing a non-linear transformation on the model;

for the same given image frame, refining the coarsely aligned pose estimate to produce a refined pose estimate by determining distance values representing distances between model features and corresponding run-time features; and

wherein the refined pose estimate is used to map the model features to create a transformed version of the two-dimensional model pattern, the transformed version representing a perspective or deformed non-linear movement of at least portions of the two-dimensional model pattern in a direction orthogonal to a plane of the two-dimensional model pattern.

72. The method according to claim 71, wherein the sequence of image frames are taken by a camera.

73. The method according to claim 72, wherein the sequence of image frames includes image frames taken from different camera views.

74. The method according to claim 73, wherein the sequence of image frames includes image frames taken from a common camera view.

75. The method according to claim 71, wherein the producing the model includes producing model features with a training process includes imaging orthogonally to a 2D pattern.

76. The method according to claim 71, wherein the model features of the two-dimensional pattern include model features extracted from a two-dimensional training image.

77. The method according to claim 71, comprising using a refined pose for a previous image frame as a coarsely aligned pose estimate for a next image frame.

78. Apparatus comprising:

computer-readable media;

a processor;

computer-readable media encoded representations of movement over time of a three-dimensional target object, the representations including a sequence of image frames;

computer-readable media encoded representations of a model from a training image of an object, the model including model features of a portion of the target object, the model representing a two-dimensional model pattern;

a tracker configured to track iteratively the target object for a given image frame of the image frames, while, for each iteration of the tracking, incrementing the given image frame to be a next image frame;

wherein the tracker is configured so that a given iteration of the tracking includes, for a given run-time image within the given frame;

producing a current pose estimate configured to attempt to align the model features with the given run-time image;

mapping the model features using the current pose estimate;

refining the current pose estimate to produce a refined posed estimate, the refining including modifying at least one parameter of the current pose estimate to reduce a given distance between a least a given mapped model feature mapped using the current pose estimate and a corresponding run-time feature;

repeating both the mapping and the refining, while each time treating the most recently refined pose estimate as the current pose estimate; and

wherein the current pose estimate is used to map the model features to create a transformed version of the two-dimensional model pattern, the transformed version representing a perspective or deformed non-linear movement of a least portions of the two-dimensional model pattern in a direction orthogonal to a plane of the two-dimensional model description.

79. The apparatus according to claim 78, wherein the model features and the run-time features include edge-based features.

80. The apparatus according to claim 78, wherein the model features and run-time features include edgelets.

81. The apparatus according to claim 78, wherein the model features and the run-time features include chains of edgelets.

82. The apparatus according to claim 78, wherein the model features and the run-time features include features involving detection and a sub-pixel location of edges.

83. Non-transitory computer-readable media including data, the data being encoded, when interoperably read by a computer, to cause:

representing relative movement over time of a three-dimensional target object with a sequence of image frames;

producing a model from a training image of an object, the model including model features of a portion of the target object, the model representing a two-dimensional model pattern;

tracking iteratively the target object from a given image frame of the image frames, while, for each iteration of the tracking, incrementing the given image frame to be a next image frame;

a given iteration of the tracking including, for a given run-time image within the given frame;

producing a current pose estimate configured to attempt to align the model features with the given run-time image;

mapping the model features using the current pose estimate;

refining the current pose estimate to produce a refined pose estimate, the refining including modifying at least one parameter of the current pose estimate to reduce a given distance between at least a given mapped model feature mapped using the current pose estimate and a corresponding run-time feature;

repeating both the mapping and the refining, while each time treating the most recently refined pose estimate as the current pose estimate; and

wherein the current pose estimate is used to map the model features to create a transformed version of the two-dimensional model pattern, the transformed version representing a perspective or deformed non-linear movement of at least portions of the two-dimensional model pattern in a direction orthogonal to a plane of the two-dimensional model description.

84. The non-transitory computer-readable media according to claim 83, wherein the model features and the run-time features include edge-based features.

85. The non-transitory computer-readable media according to claim 83, wherein the model features and run-time features include edgelets.

86. The non-transitory computer-readable media according to claim 83, wherein the model features and the run-time features include chains of edgelets.

87. The non-transitory computer-readable media according to claim 83, wherein the model features and the run-time features include features involving a detection and a sub-pixel location of edges.