Method and apparatus for automatic local path planning for virtual colonoscopy

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.