US7167180B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic path planning system and method
Assignee: Algotec Systems Ltd
•
Filing: 1998-02-23
•
Granted: 2007-01-23
•
Expires: 2018-02-23
Abstract
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.
Inventors
- 👤 Omer Shibolet
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:57
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/155; G06T7/13; A; A61; A61B; A61B6/00; A61B6/46; A61B6/461; A61B6/466; A61B6/50; A61B6/506; A61B6/52; A61B6/5205; G06T2207/00; G06T2207/30; G06T2207/30004; G06T2207/30101; G06T2207/30172
Claims Analysis
Total Claims: 62
Claim 1
Independent Claim
75 words
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.
Claim 2
Independent Claim
75 words
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.
Claim 3
Dependent Claim
20 words
A method according to claim 1 , wherein automatically determining a path comprises evaluating a penalty function for the points.
Claim 4
Dependent Claim
25 words
A method according to claim 2 , wherein said penalty function is dependent on the distance of the point from a boundary of the cavity.
Claim 5
Dependent Claim
21 words
A method according to claim 3 , wherein said penalty function is lower for points which are further from the boundary.
Claim 6
Dependent Claim
19 words
A method according to claim 1 , wherein said granularity is determined responsive to a morphology of said cavity.
Claim 7
Dependent Claim
21 words
A method according to claim 5 , wherein a local granularity is determined and wherein said morphology comprises a local morphology.
Claim 8
Dependent Claim
15 words
A method according to claim 6 , wherein said local morphology comprises a local width.
Claim 9
Dependent Claim
30 words
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.
Claim 10
Dependent Claim
42 words
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.
Claim 11
Independent Claim
77 words
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.
Claim 12
Independent Claim
77 words
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.
Claim 13
Dependent Claim
19 words
A method according to claim 10 , wherein said penalty function is responsive to a morphology of the cavity.
Claim 14
Dependent Claim
13 words
A method according to claim 11 , wherein said morphology comprises a width.
Claim 15
Dependent Claim
14 words
A method according to claim 11 , wherein said morphology is a local morphology.
Claim 16
Dependent Claim
16 words
A method according to claim 10 , wherein said penalty function is responsive to the path.
Claim 17
Dependent Claim
22 words
A method according to claim 14 , wherein said penalty function is responsive to an amount of local bending of the path.
Claim 18
Dependent Claim
23 words
A method according to claim 10 , wherein automatically determining a path comprises automatically determining a trajectory of an origin of a viewport.
Claim 19
Dependent Claim
17 words
A method according to claim 10 , wherein providing a plurality of points comprises providing a trajectory.
Claim 20
Dependent Claim
21 words
A method according to claim 10 , wherein automatically determining a path comprises automatically determining a trajectory of an aiming point.
Claim 21
Dependent Claim
28 words
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.
Claim 22
Dependent Claim
24 words
A method according to claim 10 , wherein automatically determining a path comprises generating a graph representing at least a portion of the cavity.
Claim 23
Dependent Claim
36 words
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.
Claim 24
Dependent Claim
25 words
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.
Claim 25
Dependent Claim
19 words
A method according to claim 20 , wherein said graph includes only a subset of voxels in said cavity.
Claim 26
Dependent Claim
18 words
A method according to claim 23 , wherein said graph comprises substantially only a skeleton of said cavity.
Claim 27
Dependent Claim
33 words
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.
Claim 28
Dependent Claim
14 words
A method according to claim 10 , wherein said dataset is represented by voxels.
Claim 29
Dependent Claim
14 words
A method according to claim 10 , wherein said boundary is represented by polygons.
Claim 30
Dependent Claim
14 words
A method according to claim 10 , wherein said dataset comprises a CT dataset.
Claim 31
Dependent Claim
14 words
A method according to claim 10 , wherein said dataset comprises an MRI dataset.
Claim 32
Dependent Claim
14 words
A method according to claim 10 , wherein said dataset comprises a NM dataset.
Claim 33
Independent Claim
124 words
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.
Claim 34
Independent Claim
124 words
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.
Claim 35
Independent Claim
124 words
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.
Claim 36
Independent Claim
124 words
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.
Claim 37
Independent Claim
104 words
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.
Claim 38
Independent Claim
104 words
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.
Claim 39
Independent Claim
108 words
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.
Claim 40
Independent Claim
108 words
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.
Claim 41
Independent Claim
87 words
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.
Claim 42
Independent Claim
87 words
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.
Claim 43
Dependent Claim
19 words
A method according to claim 35 , wherein said predetermined width is dependent on a morphology of the cavity.
Claim 44
Independent Claim
109 words
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.
Claim 45
Independent Claim
109 words
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.
Claim 46
Independent Claim
115 words
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.
Claim 47
Independent Claim
115 words
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.
Claim 48
Independent Claim
113 words
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.
Claim 49
Independent Claim
113 words
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.
Claim 50
Independent Claim
80 words
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.
Claim 51
Independent Claim
80 words
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.
Claim 52
Dependent Claim
31 words
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.
Claim 53
Independent Claim
113 words
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.
Claim 54
Independent Claim
113 words
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.
Claim 55
Independent Claim
78 words
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.
Claim 56
Independent Claim
78 words
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.
Claim 57
Dependent Claim
28 words
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.
Claim 58
Dependent Claim
54 words
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.
Claim 59
Independent Claim
86 words
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.
Claim 60
Independent Claim
86 words
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.
Claim 61
Independent Claim
82 words
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.
Claim 62
Independent Claim
82 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2010-01-22 | 2010-07-24 | 2011-01-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2014-01-22 | 2014-07-24 | 2015-01-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2018-01-22 | 2018-07-24 | 2019-01-23 | $7700.00 | Window Closed / Lapsed |