Method and apparatus for registration of virtual endoscopic images

• US 20050048456A1
• Filed: 08/09/2004
• Published: 03/03/2005
• Est. Priority Date: 08/14/2003
• Status: Active Grant

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Geiger, Bernhard, Chefd'hotel, Christophe
• Granted Patent: US 7,300,398 B2
• Time in Patent Office: Days
• US Class Current: 434/267
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/10088 Magnetic resonance imaging [MRI]
• CPC Class Codes: G06T 2207/30028 Colon; Small intestine
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/38 Registration of image sequences

Abstract

A method for registration of virtual endoscopy images in first and second patient positions comprises performing colon segmentation and feature extraction, including centerline and colon surface data for each of the images; resampling the centerline and colon surface data; computing respective local descriptors; pairing point correspondences on the centerlines between the first and second images by minimal cost matching; extrapolating the centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between the first and second images. The method also includes selecting a position for a virtual endoscope in one of the images; associating an orthogonal reference frame with the virtual endoscope; and applying the 3D/3D transformation to the orthogonal reference frame so as to derive a corresponding transformed reference frame for the virtual endoscope in the other of the images.

Claims

1. A method for registration of virtual endoscopic images, said method comprising:

deriving first and second volumetric images by an endoscopic protocol and representing said images by respective first and second volumetric image data sets;

deriving respective centerline representations by connected line components;

resampling said connected components to provide respective first and second sample sets;

computing a descriptor for each sample;

computing a similarity matrix using distances between said descriptors; and

determining an optimal set of point correspondences between said first and second sample sets by application of a minimization algorithm to said similarity matrix.

2. A method as recited in claim 1, wherein said step of deriving first and second volumetric images comprises a step of deriving said first and second volumetric images by a colonoscopy protocol.

3. A method as recited in claim 1, wherein said step of deriving respective centerline representations comprises:

a step of deriving said respective centerline representations by connected polygonal line components;

identifying a colon surface in each of said volumetric images; and

deriving respective colon radius information by determining the distance from each point of said centerline representation to a respectively closest point on said colon surface.

4. A method as recited in claim 1, comprising the steps of:

extrapolating said centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second volumetric images; and

applying said 3D/3D transformation to transform a virtual endoscope position between said first and second volumetric images.

5. A method for prone-supine registration of first and second volumetric images obtained by virtual colonoscopy and including respective centerline representations by connected polygonal line components and including respective colon radius information, said method comprising:

resampling of said connected components to provide respective first and second centerline sample sets;

computing a descriptor for each sample;

computing a similarity matrix using distances between said descriptors;

determining an optimal set of centerline point correspondences between said first and second sample sets by application of a minimization algorithm to said similarity matrix;

extrapolating said centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second volumetric images; and

applying said 3D/3D transformation to transform a virtual endoscope position between said first and second volumetric images.

6. A method for prone-supine registration of first and second volumetric images obtained by virtual colonoscopy represent by respective first and second volumetric datasets, including respective centerline representations by connected polygonal lines and including colon radius information, said method comprising:

resampling of said connected polygonal lines to provide respective first and second sample sets;

computing a descriptor for each sample;

computing a similarity matrix using distances between said descriptors; and

determining an optimal set of point correspondences between said first and second sample sets by application of a minimization algorithm to said similarity matrix.

7. A method as recited in claim 6, comprising the step of:

extrapolating said optimal set of centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second volumetric images.

8. A method as recited in claim 7, comprising the step of:

applying said 3D/3D transformation to transform a virtual endoscope position between said first and second volumetric images.

9. A method for registration of virtual endoscopy images in first and second patient positions, said method comprising:

performing colon segmentation and feature extraction, including centerline and colon surface data for each of said images;

resampling said centerline and colon surface data;

computing respective local descriptors;

pairing point correspondences on said centerlines between said first and second images by minimal cost matching; and

extrapolating said centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second images.

10. A method as recited in claim 9, comprising:

selecting a position for a virtual endoscope in one of said images;

associating an orthogonal reference frame with said virtual endoscope; and

applying said 3D/3D transformation to said orthogonal reference frame so as to derive a corresponding transformed reference frame for said virtual endoscope in the other of said images.

11. A method as recited in claim 10, wherein said step of performing colon segmentation comprises deriving respective centerline representations by connected polygonal line components.

12. A method as recited in claim 11, wherein said step of resampling comprises:

selecting a fixed number N of sampling points on said respective connected polygonal line components;

computing the total sum length of said connected polygonal line components;

dividing said total sum length by (N−

1) to derive a computed value; and

resampling each of said connected polygonal line components at respective new sampling points such that an arc length between said new sampling points corresponds to said value, said new sampling points having positions determined by linear interpolation.

13. A method as recited in claim 12, wherein said step of computing respective local descriptors comprises:

computing said respective descriptors as a vector of scalar geometric features and an estimated distance to a colon surface, utilizing said colon radius data at each of said new sampling points.

14. A method as recited in claim 13, wherein said step of computing respective local descriptors comprises:

computing said geometric features to include curvature, torsion, and distance to a centroid at each of said new sampling points.

15. A method as recited in claim 13, wherein said step of computing local descriptors comprises:

computing a list of vectors containing Euclidean distances and orientations from each of said new sampling points to all other ones of said new sampling points of the same one of said datasets.

16. A method as recited in claim 15, wherein said step of computing a list of vectors comprises computing said orientations relative to a local, Frenet type, coordinate frame.

17. A method as recited in claim 15, wherein said step of computing a list of vectors comprises computing said orientations relative to a global coordinate system.

18. A method as recited in claim 9, wherein said step of pairing point correspondences on said centerlines comprises computing a similarity matrix by constructing an N×

N similarity matrix giving for each sample of said first sample set a distance measure between the descriptor for said each sample and descriptors of all samples of said second sample set.

19. A method as recited in claim 18, wherein said distance measure between any two of said descriptors is computed as one of (a) the mean and (b) the median of a normalized distance between corresponding attributes of said any two of said descriptors.

20. A method as recited in claim 19, wherein said distance measure between any two of said descriptors is computed as

(A) in the case of scalar attributes, half of the squared difference between said scalar attributes, and

(B) in the case of vectors of Euclidean distances and orientations, a distance evaluated using a statistical similarity measure.

21. A method as recited in claim 20, wherein step (B) comprises one of the following:

(c) rank ordering said vectors and computing Spearman'"'"'s rank correlation,

(d) computing histograms of elements of said vectors and comparing said elements using one of (C) Kullback-Leibler divergence and (D) Chi-square measure, and

(e) computing a joint histogram of two respective sets of elements of two vectors and computing their similarity by the Mutual Information of said two respective sets.

22. A method as recited in claim 9, wherein said step of pairing point correspondences on said centerlines between said first and second images by minimal cost matching comprises:

determining an optimal assignment that minimizes the sum of distances between all corresponding points by applying a bipartite matching algorithm.

23. A method as recited in claim 22, wherein said step of applying a minimization procedure comprises applying a fast Augmenting Path technique to said similarity matrix.

24. A method as recited in claim 23, wherein said step of extrapolating said centerline point correspondences to a first 3D/3D transformation between said first and second volumetric images and a second 3D/3D transformation between said second and said first volumetric images, reciprocal to said first 3D/3D transformation by utilizing a regularized radial basis function approximation.

25. A method as recited in claim 24, comprising empirically choosing a regularization parameter for said regularized radial basis function approximation.

26. A method as recited in claim 24, wherein said step of associating an orthogonal reference frame with said virtual endoscope comprises associating with said virtual endoscope an infinitesimal orthogonal frame with a point of origin and three respective points, one for the extremity of each of three basis vectors;

and

applying said 3D/3D transformation to each of said points so as to derive said corresponding transformed reference frame for said virtual endoscope.

27. A method for prone-supine registration of first and second volumetric images, obtained by virtual colonoscopy and represented by first and second volumetric image data sets, including respective centerline representations by connected polygonal line components, and including respective colon radius data, said method comprising:

resampling of said connected line components to provide respective first and second sample sets;

computing, for each sample, a descriptor comprising a vector of geometric features and an estimated value of said colon radius data;

computing a similarity matrix using distances between said descriptors;

applying a minimization procedure to said similarity matrix to determine an optimal set of correspondences between points of said first and second sample sets by applying an algorithm to said similarity matrix for minimizing the sum of distances between all corresponding points;

extrapolating said centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second volumetric images;

selecting a position for a virtual endoscope in one of said volumetric images;

associating an orthogonal reference frame with said virtual endoscope; and

applying said 3D/3D transformation to said orthogonal reference frame so as to derive a corresponding transformed reference frame for said virtual endoscope in the other of said volumetric images.

28. A method as recited in claim 27 wherein said step of resampling comprises:

selecting a fixed number N of sampling points on said respective connected polygonal line components;

computing the total sum length of said connected polygonal line components;

dividing said total sum length by (N−

1) to derive a computed value; and

resampling each of said connected polygonal line components at respective new sampling points such that an arc length between said new sampling points corresponds to said value, said new sampling points having positions determined by linear interpolation.

29. A method as recited in claim 27, wherein said step of computing respective descriptors comprises:

computing said respective descriptors as a vector of scalar geometric features and an estimated distance to a colon surface, utilizing said colon radius data at each of said new sampling points.

30. A method as recited in claim 29, wherein said step of computing respective descriptors comprises:

computing said geometric features to include curvature, torsion, and distance to a centroid at each of said new sampling points.

31. A method as recited in claim 27, wherein said step of computing respective descriptors comprises:

computing a list of vectors containing Euclidean distances and orientations from each of said new sampling points to all other ones of said new sampling points of the same one of said datasets.

32. A method as recited in claim 31, wherein said step of computing a list of vectors comprises computing said orientations relative to a local, Frenet type, coordinate frame.

33. A method as recited in claim 31, wherein said step of computing a list of vectors comprises computing said orientations relative to a global coordinate system.

34. A method as recited in claim 27, wherein said step of computing a similarity matrix comprises:

constructing an N×

N similarity matrix giving for each sample of said first sample set a distance measure between the descriptor for said each sample and descriptors of all samples of said second sample set.

35. A method as recited in claim 34, wherein said distance measure between any two of said descriptors is computed as one of (a) the mean and (b) the median of a normalized distance between corresponding attributes of said any two of said descriptors.

36. A method as recited in claim 35, wherein said distance measure between any two of said descriptors is computed as

(A) in the case of scalar attributes, the absolute value of the difference between said scalar attributes, and

(B) in the case of vectors of Euclidean distances and orientations, a distance evaluated using a statistical similarity measure.

37. A method as recited in claim 36, wherein step (B) comprises one of the following:

(c) rank ordering said vectors and computing Spearman'"'"'s rank correlation,

(d) computing histograms of elements of said vectors and comparing said elements using one of (C) Kullback-Leibler divergence and (D) Chi-square measure, and

(e) computing a joint histogram of two respective sets of elements of two vectors and computing their similarity by the Mutual Information of said two respective sets.

38. A method as recited in claim 27, wherein said step of applying a minimization procedure comprises:

determining an optimal assignment that minimizes the sum of distances between all corresponding points by applying a bipartite matching algorithm.

39. A method as recited in claim 38, wherein said step of applying a minimization procedure comprises applying a fast Augmenting Path technique to said similarity matrix.

40. A method as recited in claim 39, wherein said step of extrapolating said centerline point correspondences to a first 3D/3D transformation between said first and second volumetric images and a second 3D/3D transformation between said second and said first volumetric images, reciprocal to said first 3D/3D transformation by utilizing a regularized radial basis function approximation.

41. A method as recited in claim 40, comprising empirically choosing a regularization parameter for said regularized radial basis function approximation.

42. A method as recited in claim 40, wherein said step of associating an orthogonal reference frame with said virtual endoscope comprises associating with said virtual endoscope an infinitesimal orthogonal frame with a point of origin and three respective points, one for the extremity of each of three basis vectors;

and

applying said 3D/3D transformation to each of said points so as to derive said corresponding transformed reference frame for said virtual endoscope.

43. A method for registration of virtual endoscopic images, said method comprising:

deriving first and second volumetric images by a colonoscopy protocol and representing said images by respective first and second volumetric image data sets;

deriving respective centerline representations by connected polygonal line components;

identifying a colon surface in each of said volumetric images;

deriving respective colon radius information by determining the distance from each point of said centerline representation to a respectively closest point on said colon surface;

resampling said connected components to provide respective first and second sample sets;

computing a descriptor for each sample;

computing a similarity matrix using distances between said descriptors; and

determining an optimal set of point correspondences between said first and second sample sets by application of a minimization algorithm to said similarity matrix.

44. A method as recited in claim 43, comprising:

extrapolating said centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second volumetric images.

45. A method as recited in claim 43, comprising:

applying said 3D/3D transformation to transform a virtual endoscope position between said first and second volumetric images.

46. Apparatus for prone-supine registration of first and second volumetric images obtained by virtual colonoscopy and including respective centerline representations by connected polygonal line components and including respective colon radius information, said apparatus comprising:

means for resampling of said connected components to provide respective first and second centerline sample sets;

means for computing a descriptor for each sample;

means for computing a similarity matrix using distances between said descriptors;

means for determining an optimal set of centerline point correspondences between said first and second sample sets by application of a minimization algorithm to said similarity matrix;

means for extrapolating said centerline point correspondences to a 3-dimensional/3-dimensional (3D/3D) transformation between said first and second volumetric images; and

means for applying said 3D/3D transformation to transform a virtual endoscope position between said first and second volumetric images.

47. Apparatus for registration of virtual endoscopic images, said apparatus comprising:

means for deriving first and second volumetric images by an endoscopic protocol and representing said images by respective first and second volumetric image data sets;

means for deriving respective centerline representations by connected line components;

means for resampling said connected components to provide respective first and second sample sets;

means for computing a descriptor for each sample;

means for computing a similarity matrix using distances between said descriptors; and

means for determining an optimal set of point correspondences between said first and second sample sets by application of a minimization algorithm to said similarity matrix.