Video pose tracking system and method

• US 6,978,167 B2
• Filed: 07/01/2002
• Issued: 12/20/2005
• Est. Priority Date: 07/01/2002
• Status: Active Grant

• Current Assignee: Claronav Inc. (Kofax Incorporated)
• Original Assignee: Claron Technology Inc (Kofax Incorporated)
• Inventors: Dekel, Doron, Gatti, Claudio
• Primary Examiner(s): Casler, Brian L.
• Assistant Examiner(s): Roy, Baisakhi
• Application Number:
  US10/184,972
• Publication Number:
  US 20040002642A1
• Time in Patent Office: 1,268 Days
• Field of Search: 600/407, 600/426, 600/424, 600/410, 600/411, 600/437, 600/374, 600/512, 600/592, 600/417, 600/450, 600/558, 600/117, 600/454, 600/414, 600/441, 600/409, 600/508, 600/595, 382/103, 382/190, 382/195, 382/154, 382/206, 382/169, 382173- 4, 382/77, 382/203, 382205- 6, 382/131, 382/260, 382/299, 345/156, 606/130, 356/620
• US Class Current: 600/426
• CPC Class Codes: A61B 2034/2065 Tracking using image or pattern recognition
• CPC Class Codes: A61B 2090/363 Use of fiducial points
• CPC Class Codes: A61B 2090/364 Correlation of different images or relation of image positions in respect to the body
• CPC Class Codes: A61B 2090/3983 Reference marker arrangements for use with image guided surgery
• CPC Class Codes: A61B 34/10 Computer-aided planning, simulation or modelling of surgical operations
• CPC Class Codes: A61B 34/20 Surgical navigation systems; Devices for tracking or guiding surgical instruments, e.g. for frameless stereotaxis
• CPC Class Codes: G01B 11/002 for measuring two or more coordinates
• CPC Class Codes: G01B 11/26 for measuring angles or tapers; for testing the alignment of axes
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A measurement system and method for detecting and tracking the pose of an object displaceable in a coordinate reference frame. In the system and method a visible target pattern is provided on the object. The visible target pattern includes a series of contrast regions for providing at least two feature points. Each of these feature points is located at a juncture of an optically detectable plurality of edges. Each edge in the optically detectable plurality of edges separates different contrast regions. The method and system determine the location of the feature points by first locating the edges using the change in contrast between contrast regions, and then determining junctures of multiple edges. The method and system also involve a stereoscopic digital camera for generating a pair of digital images of the target pattern and a marker template comprising a set of reference characteristics including a relationship between the feature points.

Claims

1. A measurement system for tracking a pose of an object displaceable in a coordinate reference frame, the system comprising:

a) an optically visible target pattern secured to the object, the target pattern containing an arrangement of contrast regions for defining at least two feature points, each feature point being located at a juncture of an optically detectable plurality of edges, wherein each edge in the optically detectable plurality of edges separates different contrast regions;

b) an optical sensor assembly for generating a pair of digital images of the target pattern containing the feature points, the pair of images being generated from dissimilar viewing angles;

c) a marker template comprising a unique set of reference characteristics including a relationship between the feature points; and

,

d) a processor for testing the pixels of the digital images to determine the spatial location in the reference frame for each of the feature points of the target pattern, for comparing the determined spatial locations of the feature points to the set of reference characteristics to confirm the recognition of the target pattern, and for calculating the object pose from the spatial location of the feature points.

2. The system of claim 1 further comprising at least three feature points to define a pair of non-collinear target vectors.

3. The system of claim 2, wherein at least four feature points define the pair of non-collinear target vectors.

4. The system of claim 2, wherein a plurality of the feature points defines at least three non-collinear target vectors.

5. The system of claim 2 further comprising a plurality of target patterns with at least one of the feature points present on each one of the plurality of target patterns.

6. The system of claim 2, wherein the reference characteristics are selected from the group comprising a distance between the adjacent feature points, the number of feature points, a distance between adjacent target vectors, and an angle between adjacent target vectors.

7. The system of claim 1 wherein the contrast regions include a plurality of alternating dark and bright regions.

8. The system of claim 7 further comprising an intensity gradient between adjacent pixels in the digital images, one of the adjacent pixels being in one of the dark regions and the other of the adjacent pixels being in one of the bright regions.

9. The system of claim 8, wherein a distribution of intensity gradients corresponding to the alternating dark and bright regions defines an arrangement of alternating intensity peaks and valleys.

10. The system of claim 9, wherein each of the feature points is an intensity saddle located in the center of the arrangement of alternating peaks and valleys.

11. The system of claim 10, wherein the type of the feature points is determined by the number of peaks and valleys associated with each of the feature points.

12. The system of claim 11, wherein the feature point type is included in the reference characteristics.

13. The system of claim 1 further comprising a plurality of target patterns, each of the target patterns having at least one feature point.

14. The system of claim 13, wherein each of the target patterns contain a respective set of at least two of the feature points.

15. The system of claim 14, wherein the respective set of feature points defines a corresponding target vector.

16. The system of claim 15, wherein each of the target vectors is oriented in a unique direction.

17. The system of claim 16, wherein the plurality of target patterns are located on a planar surface.

18. The system of claim 16, wherein at least one of the target patterns is located on a three dimensional surface.

19. The system of claim 16, wherein at least one of the target patterns is positioned on a corresponding one of a plurality of planes, and each of the planes is oriented in a different direction.

34. The system according to claim 1 further comprising a second target pattern secured to the object, the second target pattern being movable within a predefined path in relation to the target pattern.

35. The system according to claim 34, wherein the relative position of the second target pattern along the path is determined in relation to the pose of the object.

36. The system according to claim 1, wherein the testing and comparing by the processor includes the relative orientation of the feature points with respect to one another.

20. A measurement method for tracking a pose of an object displaceable in a coordinate reference frame, the method comprising the steps of:

a) providing a visible target pattern on the object, the visible target pattern having an arrangement of contrast regions for defining at least two feature points, each feature point being located at a juncture of an optically detectable plurality of edges, wherein each edge in the optically detectable plurality of edges separates different contrast regions;

b) generating a pair of digital images of the target pattern containing the feature points, the pair of images being generated from dissimilar viewing angles;

c) testing the pixels of the digital images to determine the spatial location in the reference frame for at least two of the feature points of the target pattern by determining the juncture of the optically detectable plurality of edges for each feature point;

d) comparing the determined spatial locations of the feature points to a unique set of reference characteristics for recognizing the target pattern in the coordinate frame; and

e) calculating the object pose from the determined spatial locations of the feature points.

21. The method of claim 20, wherein the step of testing the pixels includes a first point test for rejecting a majority of the pixels not containing candidate feature points.

22. The method of claim 21 further comprising the step of applying a second test for identifying the feature points from the remaining pixels containing the candidate feature points.

23. The method of claim 21, wherein the first test for the image pixels is selected from the group comprising multi-resolution processing, change detection, edge orientation template, edge orientation histogram, and fast tracking slow detection.

24. The method of claim 22, wherein the second test for the image pixels is selected from the group comprising multi-resolution processing, change detection, edge orientation template, edge orientation histogram, and fast tracking slow detection.

25. The method of claim 20, wherein step c) comprises locating a pair of edge lines in the plurality of edges, wherein the pair of edge lines intersect at a feature point candidate.

26. The method of claim 25 further comprising the step of selecting a sequence of pixels in a direction different to the direction of one of said pair of edge lines according to intensity gradients between adjacent contrast regions.

27. The method of claim 26, wherein said sequence is selected at least two pixel units away from the feature point candidate.

28. The method of claim 27 further comprising the step of selecting a plurality of intensity values on each of said pair of edge lines contained in said sequence.

29. The method of claim 28 further comprising the step of fitting a curve equation to the intensity values for determining the location of each of said pair of edge lines to sub pixel accuracy.

30. The method of claim 29 further comprising the step of performing a linear regression on the intensity values of sub pixel accuracy for each said pair of edge lines.

31. The method of claim 30 further comprising the step of calculating the intersections of the edge lines resulting from the regression for determining the sub pixel location of the feature point candidate at an intensity saddle point.

32. The method of claim 29, wherein the curve fit is second order or higher.

33. A computer readable medium storing an algorithm for performing the method steps of claim 20.

37. The method according to claim 20, wherein the steps of testing and comparing includes the relative orientation of the feature points with respect to one another.