Automatic path planning system and method

• US 7,167,180 B1
• Filed: 02/23/1998
• Issued: 01/23/2007
• Est. Priority Date: 02/23/1998
• Status: Expired due to Fees

• Current Assignee: Algotec Systems Ltd. (Koninklijke Philips N.V.)
• Original Assignee: Algotec Systems Ltd. (Koninklijke Philips N.V.)
• Inventors: Shibolet, Omer
• Primary Examiner(s): Nguyen; Phu K.
• Application Number:
  US09/622,731
• Time in Patent Office: 3,256 Days
• Field of Search: 345/418, 345/419, 345/473, 345/474
• US Class Current: 345/474
• CPC Class Codes: A61B 6/466 adapted to display 3D data
• CPC Class Codes: A61B 6/506 for diagnosis of nerves
• CPC Class Codes: A61B 6/5205 involving processing of raw data to produce diagnostic data
• CPC Class Codes: G06T 2207/30101 Blood vessel; Artery; Vein; Vascular
• CPC Class Codes: G06T 2207/30172 Centreline of tubular or elongated structure
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/155 involving morphological operators

Abstract

A method of path planning, comprising providing a dataset representing a cavity and a boundary; providing a plurality of points in said dataset, including at least a starting point and an ending point; and automatically determining a path between the starting point and the ending point, responsive to a penalty associated with passing through points in the cavity. Preferably, the penalty value associated with a point depends on a distance between the point and the boundary.

Claims

1. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point;

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity; and

selecting a data granularity level for said path determination.

2. A method according to claim 1, wherein automatically determining a path comprises evaluating a penalty function for the points.

3. A method according to claim 2, wherein said penalty function is dependent on the distance of the point from a boundary of the cavity.

4. A method according to claim 3, wherein said penalty function is lower for points which are further from the boundary.

5. A method according to claim 1, wherein said granularity is determined responsive to a morphology of said cavity.

6. A method according to claim 5, wherein a local granularity is determined and wherein said morphology comprises a local morphology.

7. A method according to claim 6, wherein said local morphology comprises a local width.

8. A method according to claim 1, wherein a local granularity is determined and wherein said granularity is determined responsive to a distance of a locality from a cavity boundary.

9. A method according to claim 1, wherein a first granularity is determined for a first path planning and comprising repeating said path planning using a second granularity and using said first path as a starting point for said repeated path planning.

10. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein said determining a path comprises determining a relatively short path.

11. A method according to claim 10, wherein said penalty function is responsive to a morphology of the cavity.

12. A method according to claim 11, wherein said morphology comprises a width.

13. A method according to claim 11, wherein said morphology is a local morphology.

14. A method according to claim 10, wherein said penalty function is responsive to the path.

15. A method according to claim 14, wherein said penalty function is responsive to an amount of local bending of the path.

16. A method according to claim 10, wherein automatically determining a path comprises automatically determining a trajectory of an origin of a viewport.

17. A method according to claim 10, wherein providing a plurality of points comprises providing a trajectory.

18. A method according to claim 10, wherein automatically determining a path comprises automatically determining a trajectory of an aiming point.

19. A method according to claim 10, wherein a relatively short path comprises a shortest path which takes into consideration the penalty value associated with the various locations.

20. A method according to claim 10, wherein automatically determining a path comprises generating a graph representing at least a portion of the cavity.

21. A method according to claim 20, wherein said path is determined by applying a path finding method to the graph and wherein said portions of said graph are generated only when needed by said method.

22. A method according to claim 20, wherein automatically determining a path comprises determining a path using Dijkstra'"'"'s shortest path finding method on said graph.

23. A method according to claim 20, wherein said graph includes only a subset of voxels in said cavity.

24. A method according to claim 23, wherein said graph comprises substantially only a skeleton of said cavity.

25. A method according to claim 24, wherein said skeleton is found utilizing data from erosion of the cavity, which erosion is utilized to determine a distance of interior points from said boundary.

26. A method according to claim 10, wherein said dataset is represented by voxels.

27. A method according to claim 10, wherein said boundary is represented by polygons.

28. A method according to claim 10, wherein said dataset comprises a CT dataset.

29. A method according to claim 10, wherein said dataset comprises an MRI dataset.

30. A method according to claim 10, wherein said dataset comprises a NM dataset.

31. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein automatically determining a path comprises evaluating a penalty function for the points, said penalty function being dependent on the distance of the point from a boundary of the cavity, and said penalty function being lower for points which are further from the boundary, wherein said penalty function has a substantial rate of increase when approaching said boundary.

32. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein automatically determining a path comprises evaluating a penalty function for the points, said penalty function being dependent on the distance of the point from a boundary of the cavity, and said penalty function being lower for points which are further from the boundary, wherein said penalty function has a low rate of change away from said boundary.

33. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point;

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein automatically determining a path comprises evaluating a penalty function for the points, said penalty function being dependent on the distance of the point from a boundary of the cavity; and

determining said distance by erosion of the dataset.

34. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point;

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein automatically determining a path comprises evaluating a penalty function for the points, said penalty function being dependent on the distance of the point from a boundary of the cavity; and

determining said distance by wave propagation from the boundaries of said cavity.

35. A method of path planning, comprising:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein said boundary has small holes therein and wherein said path does not pass through holes narrower than a predetermined width.

36. A method according to claim 35, wherein said predetermined width is dependent on a morphology of the cavity.

37. A method of path planning, comprising the steps of:

providing a medical dataset representing a cavity having a plurality of bends and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, wherein said path does not remain substantially in a medical axis of the cavity and does not approach closer than a predetermined distance to said boundary, in at least two of said bends;

wherein said dataset is represented using voxels and wherein said path does not approach closer than three voxels to said boundary.

38. A method of path planning, comprising the steps of:

providing a medical dataset representing a cavity having a plurality of bends and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, wherein said path does not remain substantially in a medical axis of the cavity and does not approach closer than a predetermined distance to said boundary, in at least two of said bends;

wherein said dataset is represented using voxels and wherein said path does not approach closer than one tenth the local width of said cavity, to said boundary.

39. A method of path planning, comprising the steps of:

providing a medical dataset representing a cavity having a plurality of bends and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, wherein said path does not remain substantially in a medical axis of the cavity and does not approach closer than a predetermined distance to said boundary, in at least two of said bends;

wherein said dataset is represented using voxels and wherein said path does pass through holes in said boundary which are narrower than a predetermined width.

40. A method of simultaneously distance determining and skeletonizing a dataset including a cavity and a boundary thereof, comprising:

eroding said cavity, using a series balls of increasing radius R_i;

determining a distance of points interior to the cavity, from the boundary, utilizing said erosion;

opening said eroded cavity, for each radius R_i, using a ball of radius 1; and

accumulating the points which are removed from said eroded cavity by said opening, to form a skeleton.

41. A method according to claim 40, wherein erosion by a ball R comprises eroding the result of eroding with a ball of radius R−

1, with a ball of radius 1.

42. A method of path planning, comprising the steps of:

providing a dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein automatically determining a path comprises evaluating a penalty function for the points, wherein said penalty function is dependent on the distance of the point from a boundary of the cavity, and wherein said penalty function is lower for points which are further from the boundary.

43. A method of path planning, comprising the steps of:

providing a dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein said determining a path comprises determining a relatively short path.

44. A method according to claim 43, wherein a relatively short path comprises a shortest path which takes into consideration the penalty value associated with the various points.

45. A method according to claim 43, wherein automatically determining a path comprises generating a graph representing at least a portion of the cavity and wherein said path is determined by applying a path finding method to the graph and wherein said portions of said graph are generated only when needed by said method.

46. A method of path planning, comprising the steps of:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein said penalty function is responsive to an Euclidean distance of said various points from said boundary.

47. A method of path planning, comprising the steps of:

providing a medical imaging dataset representing a cavity and a boundary;

providing a plurality of points in said dataset, including at least a starting point and an ending point; and

automatically determining a path between the starting point and the ending point, responsive to a penalty function defined by penalty values associated with passing through various points in the cavity, wherein said path planning allows a path to pass through two diagonally-adjacent voxels.