System and method for camera tracking and pose estimation

• US 20060188131A1
• Filed: 02/22/2006
• Published: 08/24/2006
• Est. Priority Date: 02/24/2005
• Status: Active Grant

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Corp. (Siemens AG)
• Inventors: Ramesh, Visvanathan, Zhang, Xiang, Genc, Yakup, Tsin, Yanghai
• Granted Patent: US 7,616,807 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/74 involving reference images or patches

Abstract

A method of tracking a pose of a moving camera includes receiving a first image from a camera, receiving a sequence of digitized images from said camera, recording, for each of said sequence of digitized images, the pose and 2D correspondences of landmarks, reconstructing a location and appearance of a 2-dimensional texture patch from 2D correspondences of the landmarks by triangulation and optimization, computing back-projection errors by comparing said reconstructed texture patch with said first received image; and reconstructing said location and appearance of said 2-dimensional texture patch from the 2D correspondences of the landmarks of said sequence of digitized images by triangulation and optimization after eliminating those landmarks with large back-projection errors.

Claims

1. A method of tracking a pose of a moving camera, comprising the steps of:

receiving a first received digitized image from a camera, said image comprising a plurality of intensities corresponding to a domain of points on a 2-dimensional grid, and including one or more landmarks for tracking;

receiving a sequence of digitized images from said camera, each image comprising a plurality of intensities corresponding to a domain of points on a 2-dimensional grid;

recording, for each of said sequence of digitized images, the pose and 2D correspondences of each of said landmarks;

reconstructing a location and appearance of a 2-dimensional texture patch from the 2D correspondences of the landmarks of said sequence of digitized images by triangulation and optimization;

computing back-projection errors by comparing said reconstructed texture patch with said first received image; and

reconstructing said location and appearance of said 2-dimensional texture patch from the 2D correspondences of the landmarks of said sequence of digitized images by triangulation and optimization after eliminating those landmarks with large back-projection errors.

2. The method of claim 1, wherein said sequence of images comprises a plurality of intensities corresponding to a domain of points on a 3-dimensional (3D) grid.

3. The method of claim 1, wherein recording the pose and 2D correspondences of each of said landmarks comprises recording a texture patch about each said landmark, the camera pose from which said texture patch is obtained, and about each said landmark, a set of 3D coordinates of nearby neighbor features.

4. The method of claim 3, wherein said one or more landmarks are selected based on how well its 3D coordinates can be reconstructed, and wherein said landmarks are evenly distributed among the reconstructed landmarks.

5. The method of claim 4, wherein said one or more landmarks are selected based on a reliability measure r comprising the term b_max/(ε

_avg+ε

_std) wherein b_max is a maximum distance between camera centers, ε

_avg is an average back-projection error distance, and ε

_std is a standard deviation of back-projection errors.

6. The method of claim 4, wherein said landmarks are separated by at least a pre-defined threshold distance in the reconstructed image.

7. The method of claim 1, further comprising searching for a best match of each landmark correspondence in said reconstructed texture patch, wherein a search range is determined by a maximum back-projection error, wherein said best match is found by minimizing a sum of square differences.

$d^{}$

( I norm ) 2 = ∑

i = 0 , j = 0 i <

n p , j <

n p ⁢

( I c norm ⁡

( i c , j c ) - I 0 norm ⁡

( i , j ) ) 2 ,

wherein n_p is a size of said texture patch for each landmark, i_c and j_c are feature point coordinates, I_norm is the normalized intensity of a point defined by

$I_{\mathrm{norm}}=\frac{I-I_{\mathrm{avg}}}{I_{\max }-I_{\min }},$

wherein I is a intensity before normalization, and I_avg, I_max, and I_min are the average, maximum, and minimum intensity values of the texture patch, respectively.

8. The method of claim 7, further comprising deforming the landmark feature coordinates i_c and j_c using an approximate affine transformation

i_c=a₁₁(i₀−

n_p/2)+a₁₂(j₀−

n_p/2)+u_c,
j_c=a₂₁(i₀−

n_p/2)+a₂₂(j₀−

n_p/2)+v_c,

wherein u_c and v_c are landmark coordinates, and a₁₁, a₁₂, a₂₁, and a₂₂ are elements of a matrix that back-projects landmark coordinates u_c, v_c to the corresponding coordinates in the first image.

9. The method of claim 7, further comprising determining a likelihood score S_l,k for each feature point k of landmark l from

S_l,k=w_λ

(λ

(u_c,v_c)−

λ

₀)+w_l√

{square root over (d(I_norm)²)}/n_pix,

wherein n_pix is the number of pixels in the texture patch of landmark l, λ

(u_c, v_c)−

λ

₀ are the smallest eigenvalues of the current candidate pixel (u_c, v_c) and the original pixel respectively, and w_λ

and w_l are predetermined weighting factors.

10. The method of claim 8, further comprising using a RANSAC algorithm to eliminate those landmarks with large back-projection errors.

11. The method of claim 1, wherein said landmarks comprise corners and edges of an object depicted in said first image.

12. A method of tracking a pose of a moving camera, comprising the steps of:

providing a set of 3-dimensional model points that represent an edge in a digitized reference image;

receiving a digitized observed image from a camera, said image comprising a plurality of intensities corresponding to a domain of points on a 2-dimensional grid;

providing an initial pose estimation of a camera for a first image in a sequence of images;

detecting a set of data points in a next image of said sequence of images, said set of data points including an edge corresponding to the edge in said model point set;

defining a kernel density estimator for a probability density function that represents the probability that a point in said data set belongs to said edge;

warping and resampling the set of model points to correspond to the set of data points according to the initial pose estimation; and

maximizing a kernel-density correlation function of the warped and resampled model point set, wherein said maximized function provides an estimate of the camera pose of said next image in said sequence of images.

13. The method of claim 12, wherein said kernel density estimator for said data point set in said observed image comprises

$P_D^{\prime }$

⁡

( x ) = 1 

D 

⁢

∑

d ∈

D ⁢

K G ⁡

( x - d , 2 ⁢

h ) ,

wherein D represents said data point set, |D| represents the sized of said data point set, d is a point in set D, and K_G is a Gaussian kernel function with bandwidth h.

14. The method of claim 12, wherein maximizing said kernel-density correlation function of the warped and resampled model point set comprises maximizing a sum of the data point set kernel density estimators over said warped and resampled model point set divided by the size of the model point set and an L₂ norm of the kernel density estimators.

15. The method of claim 12, wherein the steps of warping and resampling the set of model points and of maximizing the kernel-density correlation function are repeated until said pose estimation has converged.

16. The method of claim 12, wherein the step of warping and resampling the set of model points includes projecting a first point of said edge to the data point set, wherein a subsequent point of said model point set edge are projected to said data point set is accepted as a resampled point only if its distance to a previously resampled point is greater than a predefined distance.

17. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for tracking a pose of a moving camera, said method comprising the steps of:

receiving a first received digitized image from a camera, said image comprising a plurality of intensities corresponding to a domain of points on a 2-dimensional grid, and including one or more landmarks for tracking;

receiving a sequence of digitized images from said camera, each image comprising a plurality of intensities corresponding to a domain of points on a 2-dimensional grid;

recording, for each of said sequence of digitized images, the pose and 2D correspondences of each of said landmarks;

reconstructing a location and appearance of a 2-dimensional texture patch from the 2D correspondences of the landmarks of said sequence of digitized images by triangulation and optimization;

computing back-projection errors by comparing said reconstructed texture patch with said first received image; and

reconstructing said location and appearance of said 2-dimensional texture patch from the 2D correspondences of the landmarks of said sequence of digitized images by triangulation and optimization after eliminating those landmarks with large back-projection errors.

18. The computer readable program storage device of claim 17, wherein said sequence of images comprises a plurality of intensities corresponding to a domain of points on a 3-dimensional (3D) grid.

19. The computer readable program storage device of claim 17, wherein recording the pose and 2D correspondences of each of said landmarks comprises recording a texture patch about each said landmark, the camera pose from which said texture patch is obtained, and about each said landmark, a set of 3D coordinates of nearby neighbor features.

20. The computer readable program storage device of claim 19, wherein said one or more landmarks are selected based on how well its 3D coordinates can be reconstructed, and wherein said landmarks are evenly distributed among the reconstructed landmarks.

21. The computer readable program storage device of claim 20, wherein said one or more landmarks are selected based on a reliability measure r comprising the term b_max/(ε

_avg+ε

_std), wherein b_max is a maximum distance between camera centers, ε

_avg is an average back-projection error distance, and ε

_std is a standard deviation of back-projection errors.

22. The computer readable program storage device of claim 20, wherein said landmarks are separated by at least a pre-defined threshold distance in the reconstructed image.

23. The computer readable program storage device of claim 17, the method further comprising searching for a best match of each landmark correspondence in said reconstructed texture patch, wherein a search range is determined by a maximum back-projection error, wherein said best match is found by minimizing a sum of square differences.

$d^{}$

( I norm ) 2 = ∑

i = 0 , j = 0 i <

n p , j <

n p ⁢

( I c norm ⁡

( i c , j c ) - I 0 norm ⁡

( i , j ) ) 2 ,

wherein n_p is a size of said texture patch for each landmark, i_c and j_c are feature point coordinates, I_norm is the normalized intensity of a point defined by

$I_{\mathrm{norm}}=\frac{I-I_{\mathrm{avg}}}{I_{\max }-I_{\min }},$

wherein I is a intensity before normalization, and I_avg, I_max, and I_min are the average, maximum, and minimum intensity values of the texture patch, respectively.

24. The computer readable program storage device of claim 23, the method further comprising deforming the landmark feature coordinates i_c and j_c using an approximate affine transformation

i_c=a₁₁(i₀−

n_p/2)+a₁₂(j₀−

n_p/2)+u_c,
j_c=a₂₁(i₀−

n_p/2)+a₂₂(j₀−

n_p/2)+v_c,

wherein u_c and v_c are landmark coordinates, and a₁₁, a₁₂, a₂₁, and a₂₂ are elements of a matrix that back-projects landmark coordinates u_c, v_c to the corresponding coordinates in the first image.

25. The computer readable program storage device of claim 23, the method further comprising determining a likelihood score S_l,k for each feature point k of landmark l from

S_l,k=w_λ

(λ

(u_c,v_c)−

λ

₀)+w_l√

{square root over (d(I_norm)²)}/n_pix,

wherein n_pix is the number of pixels in the texture patch of landmark l, λ

(u_c, v_c)−

λ

₀ are the smallest eigenvalues of the current candidate pixel (u_c, v_c) and the original pixel respectively, and w_λ

and w_l are predetermined weighting factors.

26. The computer readable program storage device of claim 24, further comprising using a RANSAC algorithm to eliminate those landmarks with large back-projection errors.

27. The computer readable program storage device of claim 17, wherein said landmarks comprise corners and edges of an object depicted in said first image.