Polygon finder and pruned tree geometric match method

• US 20020037105A1
• Filed: 07/11/2001
• Published: 03/28/2002
• Est. Priority Date: 08/07/2000
• Status: Active Grant

• Current Assignee: Electro Scientific Industries Incorporated (MKS Instruments Incorporated)
• Original Assignee: Electro Scientific Industries Incorporated (MKS Instruments Incorporated)
• Inventors: Michael, Nevine
• Granted Patent: US 6,735,343 B2
• Time in Patent Office: Days
• US Class Current: 382/203
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06T 7/75 involving models
• 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

A polygon finder and pruned tree search are provided. The polygon finder uses a geometric matcher to compare corner features from a polygon model against extracted corner features from an input image to locate an object in the image that matches the polygon. Any geometric match technique may be used to locate the polygons based on their corner features. The preferred geometric matcher is a pruned tree search which calculates pose and match fit errors during search tree construction. If the pose falls outside predefined pose bounds or the fit errors are larger than the maximum limit imposed by features uncertainty bounds, the search branch is truncated. The preferred geometric matcher may be used to locate any type of geometry.

Claims

1. A method for locating a polygon within an image comprising:

providing a polygon model defined by corner features;

capturing the image;

extracting corner features from the image;

using a geometric match to compare the corner features from the polygon model against the corner features extracted from the image to locate a polygon within the image that matches the polygon model.

2. A method for locating a polygon as in claim 1 wherein the corner features from the polygon model include polarity.

3. A method for locating a polygon as in claim 2 wherein the corner features from the polygon model includes a location.

4. A method for locating a polygon as in claim 3 wherein the corner features from the polygon model includes a direction.

5. A method for locating a polygon as in claim 1 wherein a local consistency measure is applied to the corner features extracted from the input image.

6. A method for locating a polygon as in claim 1 wherein multiple polygons are found within the image that match the polygon model.

7. A method for locating a polygon as in claim 1 further comprising:

extracting line edge segments from the input image;

determining whether the line edge segments define corners;

forming corners from the line edge segments where the line segments define corners.

8. A method for locating polygons as in claim 7 wherein a corner may be defined by edge segments which do not intersect.

9. A method for locating polygons as in claim 1 wherein the geometric matching is a search tree comprising:

comparing the corner features from the model against the plurality of corners features extracted from the image;

calculating a pose, fit errors and match score for each of the comparisons, and;

truncating the search tree if any of the pose, fit errors or match score fall outside predefined parameters.

10. A method for locating polygons as in claim 1 wherein the geometric matching is a tree search.

11. A method for locating polygons as in claim 10 further comprising:

calculating a pose, fit error and match score after three extracted features have been compared against three features from the polygon model, and;

truncating the search if any of the pose, fit error or match score is outside defined thresholds.

13. A method as in claim 12 comprising:

transforming the model features based on the calculated pose, and

calculating fit errors based on the difference between the pose-transformed model and the matched features location, and

not accepting the provisional match if the fit errors fall outside the maximum defined fit errors.

14. A method as in claim 13 where the geometric match is set to minimize fit error by constructing the search tree with a minimum number of matched features wherein the minimum number of matched features is less than the plurality of geometric features.

15. A method as in claim 14 where the search tree rotates through multiple permutations in which model features are assumed to be missing from the extracted geometric features.

16. A method as in claim 13 where the match is set to maximize the number of matched features by constructing the search tree such that a required number of matches is that all of the geometric features are matched against extracted geometric features.

17. A method as in claim 16 where the number of the number of matched features is decremented by one if the required number of matches cannot be found within the extracted features.

18. A method as in claim 16 where the matches are sorted and a success is reported.

19. A method as in claim 13 wherein the fit errors calculated are local

fit errors for each individual pose-transformed model feature and matched feature pair;

and

global fit errors are calculated as the root mean square error for the difference in locations of the pose-transformed model features and the corresponding extracted features.

20. A method as in claim 19 wherein:

the maximum allowable local fit errors are the user defined feature location uncertainty bounds, and

the maximum allowable global fit errors are calculated from the feature location uncertainty errors.

21. A method as in claim 12 further comprising:

comparing a fourth geometric model feature against the plurality of extracted geometric features and finding a provisional match between a fourth geometric model feature against a fourth extracted geometric feature if their comparison fall within predefined local consistency measures to thereby form a fourth branch of the search tree which depends from the third branch;

calculating a second pose, fit error and match score based on the comparison of the first through fourth features and not accepting the provisional match if any of them fall outside predefined bounds.

22. A method as in claim 21 wherein the fit errors calculated are local

fit errors for each individual pose-transformed model feature and matched feature pair;

and

global fit errors are calculated as the root mean square error for the difference in locations of the pose-transformed model features and the corresponding extracted features.

23. A method as in claim 12 wherein the geometric model is characteristic of a circle having a contour and the geometric model features represent locations on the circle contour.

24. A method as in claim 12 wherein the model feature includes at least a characteristic location.

25. A method as in claim 12 wherein the pose is calculated using a least squares minimization technique.

27. A method as in claim 26 wherein the corner features include a location, polarity and direction.

28. A method as in claim 27 wherein the pose includes shifts in direction, scale changes and angles of rotation.

29. A method as in claim 28 wherein the scale changes are calculated in a X and a Y direction.

30. A method as in claim 29 wherein the scale changes in the X and Y directions are calculated independently of one another.

31. A method as in claim 29 wherein an aspect ratio is imposed on changes in scale in the X and Y direction.

38. An article of manufacture as in claim 1 further comprising:

means for extracting line edge segments from the input image;

means for determining whether the line edge segments define corner, and;

means for forming corners from the line edge segments where the line segments define corners.

12. A method for performing a geometric match to locate an object within an image using a search tree comprising:

providing a model of the object including a plurality of geometric model features;

providing an input image;

extracting a plurality of geometric features from the input image of the same quality of the geometric model features;

comparing a first geometric model feature against the plurality of extracted geometric features and matching the first geometric model feature against a first extracted geometric feature if their comparison falls within predefined local consistency measures to thereby form a first branch within the search tree;

comparing a second geometric model feature against the plurality of extracted geometric features and matching the second geometric model feature against a second extracted feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch;

comparing a third geometric model feature against the plurality of extracted geometric features and finding a provisional match between the third geometric model feature and a third extracted geometric feature;

calculating a pose based on the comparison of the first through third model features and extracted features, and not accepting the provisional match if the pose falls outside a predefined pose bound.

26. A method of locating a polygon in an image comprising:

providing a polygon model including a plurality of model features, each model feature characteristic of a corner from the polygon;

providing an input image;

extracting a plurality of corner features from the input image;

comparing a first model feature against the plurality of extracted corner features and matching the first model feature against a first extracted corner feature if their comparison falls within predefined local consistency measures to thereby form a first branch within a search tree;

comparing a second model feature against the plurality of extracted corner features and matching the second model feature against a second extracted corner feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch;

comparing a third geometric model feature against the plurality of extracted corner features and finding a provisional match between the third geometric model feature and a third extracted corner feature;

calculating a pose, fit error and match score based on the comparison of the first through third model features and extracted corner features, and not accepting the provisional match if the any of them fall outside predefined bounds.

32. An article of manufacture, comprising:

a computer readable medium bearing computer program code embodied therein for performing a task and including;

means for defining a polygon model defined by corner features;

means for activating a camera to capture an image of an object wherein the image includes a polygon

means for extracting corner features from the image;

means for geometrically matching the corner features from the polygon model against the corner features extracted from the image to locate a polygon within the image that matches the polygon model.

33. An article of manufacture as in claim 32 wherein the corner features from the polygon model include polarity.

34. An article of manufacture as in claim 33 wherein the corner features from the polygon model includes a location.

35. An article of manufacture as in claim 34 wherein the corner features from the polygon model includes a direction.

36. An article of manufacture as in claim 32 wherein the means for extracting corner features from an images includes means for applying a local consistency measure.

37. An article of manufacture as in claim 32 wherein the means for geometrically matching finds multiple polygons within the image that match the polygon model.

39. An article of manufacture as in claim 38 wherein a corner may be defined by edge segments which do not intersect.

40. An article of manufacture as in claim 32 wherein the means for geometrically matching includes a search tree comprising:

means for comparing the corner features from the model against the plurality of corners features extracted from the image;

means for calculating a pose, fit errors and match score for each of the comparisons, and;

means for truncating the search tree if any of the pose score, fit errors and match score fall outside predefined parameters.

41. An article of manufacture as in claim 32 wherein the means for geometrically matching comprises a tree search.

42. An article of manufacture as in claim 41 further comprising:

means for calculating a pose, fit error and match score after three extracted features have been compared against three features from the polygon model, and;

means for truncating the search if any of the pose, fit errors or match score is outside defined thresholds.

43. A computer readable storage medium containing software executable by a computer to perform process steps for performing a geometric match to locate an object within a captured image utilizing a model of the object, wherein the model includes a plurality geometric features, the process steps comprising:

extracting a plurality of geometric features from the input image of the same quality of the geometric model features;

comparing a first geometric model feature against the plurality of extracted geometric features and matching the first geometric model feature against a first extracted geometric feature if their comparison falls within predefined local consistency measures to thereby form a first branch within the search tree;

comparing a second geometric model feature against the plurality of extracted geometric features and matching the second geometric model feature against a second extracted feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch;

comparing a third geometric model feature against the plurality of extracted geometric features and finding a provisional match between the third geometric model feature and a third extracted geometric feature;

calculating a pose based on the comparison of the first through third model features and extracted features, and not accepting the provisional match if the pose falls outside a predefined pose bound.

44. A computer readable storage medium as in claim 43 wherein the process steps further comprise:

transforming the model features based on the calculated pose, and

calculating fit errors based on the difference between the pose-transformed model and the matched features location, and

not accepting the provisional match if the fit errors fall outside the maximum defined fit errors.

45. A computer readable storage medium as in claim 44 where the geometric match is set to minimize fit error by constructing the search tree with a minimum number of matched features wherein the minimum number of matched features is less than the plurality of geometric features.

46. A computer readable storage medium as in claim 45 where the search tree rotates through multiple permutations in which model features are assumed to be missing from the extracted geometric features.

47. A computer readable storage medium as in claim 44 where the match is set to maximize the number of matched features by constructing the search tree such that a required number of matches is that all of the geometric features are matched against extracted geometric features.

48. A computer readable storage medium as in claim 47 where the number of the number of matched features is decremented by one if the required number of matches is cannot be found within the extracted features.

49. A computer readable storage medium as in claim 47 where the matches are sorted and a success is reported.

50. A computer readable storage medium as in claim 44 wherein the fit errors calculated are local fit errors for each individual pose-transformed model feature and matched feature pair;

and

global fit errors are calculated as the root mean square error for the difference in locations of the pose-transformed model features and the corresponding extracted features.

51. A computer readable storage medium as in claim 50 wherein:

the maximum allowable local fit errors are the user defined feature location uncertainty bounds, and

the maximum allowable global fit errors are calculated from the feature location uncertainty errors.

52. A computer readable storage medium as in claim 43 wherein the process steps further comprise:

comparing a fourth geometric model feature against the plurality of extracted geometric features and finding a provisional match between a fourth geometric model feature against a fourth extracted geometric feature if their comparison fall within predefined local consistency measures to thereby form a fourth branch of the search tree which depends from the third branch;

calculating a second pose, fit error and match score based on the comparison of the first through fourth features and not accepting the provisional match if any of them fall outside predefined bounds.

53. A computer readable storage medium as in claim 52 wherein the fit errors calculated are local fit errors for each individual pose-transformed model feature and matched feature pair;

and global fit errors are calculated as the root mean square error for the difference in locations of the pose-transformed model features and the corresponding extracted features.

54. A computer readable storage medium as in claim 43 wherein the geometric model is characteristic of a circle having a contour and the geometric model features represent locations on the circle contour.

56. A computer readable storage medium as in claim 43 wherein the pose is calculated using a least squares minimization technique.

55. A computer readable storage medium as 43 wherein the model feature includes at least a characteristic location.

57. A computer readable storage medium containing software executable by a computer to perform process steps for performing a geometric match to locate a polygon within a captured image utilizing a model of the polygon, wherein the model includes a plurality geometric features, the process steps comprising:

providing a polygon model including a plurality of model features, each model feature characteristic of a corner from the polygon;

providing an input image;

extracting a plurality of corner features from the input image;

comparing a first model feature against the plurality of extracted corner features and matching the first model feature against a first extracted corner feature if their comparison falls within predefined local consistency measures to thereby form a first branch within a search tree;

comparing a second model feature against the plurality of extracted corner features and matching the second model feature against a second extracted corner feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch;

comparing a third geometric model feature against the plurality of extracted corner features and finding a provisional match between the third geometric model feature and a third extracted corner feature;

calculating a pose, fit error and match score based on the comparison of the first through third model features and extracted corner features, and not accepting the provisional match if any of them fall outside predefined bounds.