Targeted Marching

• US 20080091340A1
• Filed: 12/26/2004
• Published: 04/17/2008
• Est. Priority Date: 01/15/2004
• Status: Active Grant

• Current Assignee: Philips Medical Systems Technologies Ltd. (Koninklijke Philips N.V.)
• Original Assignee: Alogtec Systems Limited
• Inventors: Milstein, Ido, Miller, Gad, Akerman, Shmuel
• Granted Patent: US 8,352,174 B2
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: A61B 6/506 for diagnosis of nerves
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/20044 Skeletonization; Medial axis transform
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/30101 Blood vessel; Artery; Vein; Vascular
• CPC Class Codes: G06T 2210/41 Medical
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking
• CPC Class Codes: G06T 7/64 of convexity or concavity

Abstract

A method of finding a path from a start point to a target point, in multi-dimensional space, including: (a) determining a plurality of points in a physical space, including a start point and an target point; (b) computing, using a cost function, for said points an accumulated path cost from the start point to a point; representing a minimal cost path from the start point to the point with respect to an optimization criteria; (c) computing for at least some of said points an estimated-cost-to-target from a point to the target point; and (d) after computing said costs, determining at least one of a minimal path or a minimal path cost of a path from the start point to the target point in the physical space, wherein the determination is based on said accumulated path costs, and is minimal with respect to the optimization criteria.

Claims

1. A method of finding a path from a start point to a target point, in multi-dimensional space, comprising:

(a) determining a plurality of points in a physical space, including a start point and an target point;

(b) computing, using a cost function, for said points an accumulated path cost from the start point to a point;

representing a minimal cost path from the start point to the point with respect to an optimization criteria;

(c) computing for at least some of said points an estimated-cost-to-target from a point to the target point; and

(d) after computing said costs, determining at least one of a minimal path or a minimal path cost of a path from the start point to the target point in the physical space, wherein the determination is based on said accumulated path costs, and is substantially minimal with respect to the optimization criteria.

2. A method according to claim 1, wherein determining a plurality of points comprises generating a discrete model of said physical space.

3. A method according to claim 1, wherein the accumulated path cost at the target point approximates a minimal accumulated path cost of a path from the start point to the target point in the physical space.

4. A method according to claim 1, wherein the minimal path determined is made of line segments and each line segment connects two of said points.

5. A method according to claim 4, wherein the minimal path cost has a lower or equal cost than any zigzag path from the start point to the target point, wherein the zigzag path connects a plurality of said points, only by straight line segments.

6. A method according to claim 1, wherein the minimal path determined is a continuous smooth line.

7. A method according to claim 1, comprising repeatedly updating the accumulated path costs until a stopping criteria is satisfied.

8. A method according to claim 1, comprising selecting additional points based on said computed costs.

9. A method according to claim 1, wherein the accumulated path cost of a point is a function of a local cost of the point and an accumulated path cost of at least one neighbor point of the point.

10. A method according to claim 1, wherein computing said accumulated path cost comprises solving an Eikonal equation.

11. A method according to claim 10, wherein solving comprises employing a finite-difference approximation to an Eikonal equation.

12. A method according to claim 10 wherein computing said accumulated path cost at a point p is carried out by solving an Eikonal equation ∥

gradient(U(p))∥

=L(p), where U(p) is an accumulated path cost function, L(p) is a local cost function, ∥

∥

is a norm, and where the condition L(p)>

0 holds.

13. A method according to claim 11 wherein computing said accumulated path cost (u) at a point P, in a three dimensional grid, is carried out by solving the equation:

L²=max(u−

U<sub>x−

1,y,z</sub>,u−

U_x+1,y,z,0)²+

max(u−

U<sub>x,y−

1,z</sub>,u−

U_x,y+1,z,0)²+

max(u−

U<sub>x,y,z−

1</sub>,u−

U_x,y,z+1,0)²+

where L is the local cost and the U'"'"'s are accumulated path costs for neighbors of P.

14. A method according to claim 1, wherein computing said accumulated path cost is carried out using cost calculations suitable for a fast marching method.

15. A method according to claim 1, wherein the points are on a regular grid.

16. A method according to claim 1, wherein the points are on an irregular grid.

17. A method according to claim 1, wherein said computing using a cost function comprises computing the cost function for grid points in a particular order.

18. A method according to claim 15, wherein neighbors of a point are one or more adjacent grid points to the point.

19. A method according to claim 1, wherein the points are selected ad-hoc and not according to an a priori grid.

20. A method according to claim 1, wherein the points are arranged as a graph.

21. A method according to claim 1, wherein neighbors of a point are one or more grid points at a certain distance or at a certain radius from the point.

22. A method according to claim 1, wherein determining a path is carried out by a gradient descent method applied on said points with calculated costs.

23. A method according to claim 1, wherein said estimated-cost-to-target is intentionally underestimated.

24. A method according to claim 1, wherein said estimated cost to target is intentionally overestimated.

25. A method according to claim 1, wherein said estimated cost to target is based on a Euclidian distance to said target.

26. A method according to claim 1, wherein a collection data structure is used for obtaining a point with the smallest cost, wherein adding or removing a value from the collection, and reordering the collection has a computational cost of order O(log M) or better, where M is the number of points in the collection.

27. A method according to claim 26, wherein a heap-type data structure is used for obtaining a point with the smallest cost.

28. A method according to claim 1, wherein points are categorized and points of different categories are processed differently.

29. A method according to claim 1, wherein costs of at least one point are updated after an initial calculation.

30. A method according to claim 1, wherein costs of no points are updated after an initial calculation.

31. A method according to claim 1, wherein (c) is applied less often than (b).

32. A method according to claim 1, wherein (c) causes delayed evaluation of less promising points.

33. A method according to claim 32, wherein said delayed evaluation causes a lack of evaluation of at least 40% of points on a grid including said plurality of points.