Method and apparatus for automatic local path planning for virtual colonoscopy

• US 20040209234A1
• Filed: 01/08/2004
• Published: 10/21/2004
• Est. Priority Date: 01/30/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
• Granted Patent: US 7,081,088 B2
• Time in Patent Office: Days
• US Class Current: 434/262
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/30028 Colon; Small intestine
• CPC Class Codes: G06T 2210/41 Medical
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: G06V 2201/03 Recognition of patterns in medical or anatomical images
• CPC Class Codes: G16H 50/50 for simulation or modelling of medical disorders
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass

Abstract

A method for automatic local path planning for a virtual endoscope comprises the steps of defining a sub volume around a current endoscope position in a lumen; performing a region growing inside the lumen, starting from the current endoscope position; calculating and clustering the intersection of the region with the faces of a cube circumscribing the sub volume; calculating approximated centerline paths from the current endoscope position to the center of each cluster formed in the preceding step; comparing each of the centerline paths with a current path exhibited by the endoscope; and selecting an optimal centerline path based on the comparison.

Claims

1. A method for automatic local path planning for a virtual endoscope, comprising the steps of:

deriving a colon dataset obtained by a colonoscopy protocol for utilization in subsequent steps;

defining a sub volume around a current endoscope position in a lumen;

performing a region growing inside said lumen, starting from said current endoscope position;

calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step;

comparing each of said centerline paths with a current path exhibited by said endoscope;

assigning a score based on said comparing, to each of said centerline paths; and

selecting a centerline path based on said score.

2. A method in accordance with claim 1, wherein said step of deriving a colon dataset obtained by a colonoscopy protocol comprises deriving said data set by computerized tomography (CT).

3. A method in accordance with claim 1, wherein said step of deriving a colon dataset obtained by a colonoscopy protocol comprises deriving said data set by magnetic resonance (MR).

4. A method in accordance with claim 1, including a step of defining said cube to be of a given number of voxels centered around said current endoscope.

5. A method in accordance with claim 1, including the steps of:

region growing inside “

air”

within said lumen; and

labeling all voxels in said air within said lumen.

6. A method in accordance with claim 1, including steps of:

forming a cluster at each location wherein said air within said lumen intersects a corresponding face of said cube;

including in each said cluster voxels that share a face corresponding to said cluster.

7. A method in accordance with claim 6, including step of:

calculating the center of each cluster by averaging voxel coordinates of voxels of each of said clusters.

8. A method in accordance with claim 7, including step of:

calculating respective centerline paths from said center of each cluster to said current endoscope position.

9. A method in accordance with claim 1, wherein said step of assigning a score based on said comparing, to each of said centerline paths comprises:

starting from said current endoscope position, forming the sum of the absolute values of the difference of points on a respective centerline path to a corresponding point on said current path exhibited by said endoscope;

dividing said sum by length of said respective centerline path to form a quotient score; and

selecting a path having the highest quotient score.

10. A method in accordance with claim 9, including step of detecting when only one centerline path exists and indicating such a result as a dead end.

11. A method in accordance with claim 1, wherein said step of calculating approximated centerline paths comprises:

calculating an initial path; and

centering and smoothing said initial path.

12. A method in accordance with claim 11 wherein said step of calculating an initial path comprises:

from said endpoint, successively storing voxels with decreasing label numbers until reaching said start point.

13. A method in accordance with claim 11 wherein said step of centering and smoothing said initial path comprises using Gaussian smoothing.

14. A method in accordance with claim 13, wherein said step of centering and smoothing said initial path comprises:

setting a sphere at a vertex location;

increasing the size of said sphere size until it comes into collision with a wall of said lumen;

calculating a translation force from said collision;

applying said translation force until said sphere is no longer in collision;

increasing the size of said sphere and it again comes into further collision with said wall;

calculating a further translation force;

applying said further translation force until said sphere is no longer in collision;

repeating the foregoing three steps until said sphere reaches a final position where it cannot grow any more without collision;

indicating said final position as a final vertex position.

15. A method for automatic local path planning for a virtual endoscope, comprising the steps of:

deriving a colon dataset obtained by a colonoscopy protocol for utilization in subsequent steps;

defining a sub volume around a current endoscope position in a lumen;

performing a region growing inside said lumen, starting from said current endoscope position;

calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step by;

calculating an initial path;

centering and smoothing said initial path;

comparing each of said centerline paths with a current path exhibited by said endoscope;

assigning a score based on said comparing, to each of said centerline paths; and

selecting a centerline path based on said score.

16. A method in accordance with claim 15, wherein said step of deriving a colon dataset obtained by a colonoscopy protocol comprises deriving said data set by computerized tomography (CT).

17. A method in accordance with claim 15, wherein said step of deriving a colon dataset obtained by a colonoscopy protocol comprises deriving said data set by magnetic resonance (MR).

18. A method for automatic local path planning for a virtual endoscope, comprising the steps of:

defining a sub volume around a current endoscope position in a lumen;

performing a region growing inside said lumen, starting from said current endoscope position;

calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step;

comparing each of said centerline paths with a current path exhibited by said endoscope; and

selecting an optimal centerline path based on said comparing.

19. A system for automatic local path planning for a virtual endoscope, comprising:

means for defining a sub volume around a current endoscope position in a lumen;

means for performing a region growing inside said lumen, starting from said current endoscope position;

means for calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

means for calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step;

means for comparing each of said centerline paths with a current path exhibited by said endoscope; and

means for selecting an optimal centerline path based on said comparing.

20. A system for automatic local path planning for a virtual endoscope, comprising:

means for deriving a colon dataset obtained by a colonoscopy protocol for utilization in subsequent steps;

means for defining a sub volume around a current endoscope position in a lumen;

means for performing a region growing inside said lumen, starting from said current endoscope position;

means for calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

means for calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step;

means for comparing each of said centerline paths with a current path exhibited by said endoscope;

means for assigning a score based on said comparing, to each of said centerline paths; and

means for selecting a centerline path based on said score.

21. A system in accordance with claim 20, wherein said means for deriving a colon dataset obtained by a colonoscopy protocol comprises means for deriving said data set by computerized tomography (CT).

22. A system in accordance with claim 20, wherein said means for deriving a colon dataset obtained by a colonoscopy protocol comprises means for deriving said data set by magnetic resonance (MR).

23. A system in accordance with claim 20, including means for defining said cube to be of a given number of voxels centered around said current endoscope.

24. A system in accordance with claim 20, including means for:

region growing inside “

air”

within said lumen; and

labeling all voxels in said air within said lumen.

25. A system in accordance with claim 20, including means for:

forming a cluster at each location wherein said air within said lumen intersects a corresponding face of said cube;

including in each said cluster voxels that share a face corresponding to said cluster.

26. A system in accordance with claim 25, including means for:

calculating the center of each cluster by averaging voxel coordinates of voxels of each of said clusters.

27. A system in accordance with claim 26, including means for:

calculating respective centerline paths from said center of each cluster to said current endoscope position.

28. A system in accordance with claim 20, wherein said means for assigning a score based on said comparing, to each of said centerline paths comprises means for:

starting from said current endoscope position, forming the sum of the absolute values of the difference of points on a respective centerline path to a corresponding point on said current path exhibited by said endoscope;

dividing said sum by length of said respective centerline path to form a quotient score; and

selecting a path having the highest quotient score.

29. A system in accordance with claim 28, including means for detecting when only one centerline path exists and indicating such a result as a dead end.

30. A system in accordance with claim 20, wherein said means for calculating approximated centerline paths comprises means for:

calculating an initial path; and

centering and smoothing said initial path.

31. A system in accordance with claim 30 wherein said means for calculating an initial path comprises means for:

from said endpoint, successively storing voxels with decreasing label numbers until reaching said start point.

32. A system in accordance with claim 30 wherein said means for centering and smoothing said initial path comprises means for using Gaussian smoothing.

33. A system in accordance with claim 30, wherein said means for centering and smoothing said initial path comprises means for:

setting a sphere at a vertex location;

increasing the size of said sphere size until it comes into collision with a wall of said lumen;

calculating a translation force from said collision;

applying said translation force until said sphere is no longer in collision;

increasing the size of said sphere and it again comes into further collision with said wall;

calculating a further translation force;

applying said further translation force until said sphere is no longer in collision;

repeating the foregoing three steps until said sphere reaches a final position where it cannot grow any more without collision;

indicating said final position as a final vertex position.

34. A system for automatic local path planning for a virtual endoscope, comprising means for:

deriving a colon dataset obtained by a colonoscopy protocol for utilization in subsequent steps;

defining a sub volume around a current endoscope position in a lumen;

performing a region growing inside said lumen, starting from said current endoscope position;

calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step by;

calculating an initial path;

centering and smoothing said initial path;

comparing each of said centerline paths with a current path exhibited by said endoscope;

assigning a score based on said comparing, to each of said centerline paths; and

selecting a centerline path based on said score.

35. A system for automatic local path planning for a virtual endoscope, comprising:

means for defining a sub volume around a current endoscope position in a lumen;

means for performing a region growing inside said lumen, starting from said current endoscope position;

means for calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

means for calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step;

means for comparing each of said centerline paths with a current path exhibited by said endoscope; and

means for selecting an optimal centerline path based on said comparing.

36. A system for automatic local path planning for a virtual endoscope, comprising:

means for defining a sub volume around a current endoscope position in a lumen;

means for performing a region growing inside said lumen, starting from said current endoscope position;

means for calculating and clustering the intersection of said region with the faces of a cube circumscribing said sub volume;

means for calculating approximated centerline paths from said current endoscope position to the center of each cluster formed in the preceding step;

means for comparing each of said centerline paths with a current path exhibited by said endoscope; and

means for selecting an optimal centerline path based on said comparing.