Targeted marching

• US 8,352,174 B2
• Filed: 12/26/2004
• Issued: 01/08/2013
• Est. Priority Date: 01/15/2004
• Status: Active Grant

• Current Assignee: Philips Medical Systems Technologies Ltd. (Koninklijke Philips N.V.)
• Original Assignee: Algotec Systems Ltd. (Koninklijke Philips N.V.)
• Inventors: Akerman, Shmuel, Miller, Gad, Milstein, Ido
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Amin, Bhavesh V
• Application Number:
  US10/597,221
• Publication Number:
  US 20080091340A1
• Time in Patent Office: 2,935 Days
• Field of Search: None
• US Class Current: 701/400
• 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 a physical space, wherein a substantially infinite number of paths exist in the space between the start point and the target point, the method comprising:

(a) selecting a plurality of points in the physical space from among the points comprised in said substantially infinite number of possible paths;

(b) computing, using a programmed general purpose computer and a cost function, a path cost from the start point to one of said plurality of points;

said path cost representing an estimate of a minimal cost path from the start point to the one point which is acceptably accurate with respect to an optimization criterion;

(c) repeating (b) for a succession of others of said plurality of points to determine the path cost from the start point to each of said succession of other intermediate points;

d) computing estimated costs to target from the plurality of points for which path costs were determined in (b) and (c);

(e) selecting a group of points for further consideration according to those points determined in (b) and (c);

(f) repeating (b)-(e) to determine estimated total path costs to target for said selected group of points; and

(g) after computing said costs, determining, using said computer, 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 estimated total path costs and is an acceptably accurate estimate of the lowest cost path with respect to an optimization criterion.

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

3. A method according to claim 2, wherein the plurality of points and the selected group of points are on a regular grid.

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

5. A method according to claim 4, wherein selected group of points are neighbors of other points located at one or more adjacent grid points.

6. A method according to claim 5 wherein computing said 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)²+

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

7. A method according to claim 2, wherein the points are arranged as a graph.

8. A method according to claim 5, wherein said points are on a grid, and are located at a certain distance or at a certain radius from the point.

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

10. A method according to claim 9, wherein the minimal path determined includes line segments which connect two of said group of selected points.

11. A method according to claim 10, 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.

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

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

14. A method according to claim 13, wherein selecting said group of points for further consideration is done iteratively based on said computed path costs;

and (f) is repeated for said iteratively selected points.

15. A method according to claim 14, wherein selecting said plurality of points comprises generating a discrete model of said physical space.

16. A method according to claim 13, wherein said estimated-cost-to-target computation is adjusted by deceasing the computed value for use in determination of the minimal path or minimal path cost.

17. A method according to claim 13, wherein said estimated cost to target computation is adjusted by increasing the computed value for use in determination of the minimal path or minimal path cost.

18. A method according to claim 13 wherein said estimated cost to target is based on a Euclidian distance to said target.

19. A method according to claim 13, 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.

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

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

22. A method according claim 13, wherein costs of at least one point are updated after an initial calculation.

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

24. A method according to claim 13, wherein the estimated cost-to-target computation is applied to less than all the points for which the path cost has been computed.

25. A method according to claim 13, wherein the estimated cost-to-target computation is applied first for the points for which the path cost is lowest.

26. A method according to claim 25, wherein said estimated cost-to-target computation is applied to 40% or less of the points for which the path cost has been computed.

27. A method according to claim 13, wherein use of said estimated cost to target minimizes computation time for a path that is an acceptable estimate of a minimum path cost from said start point to said target point.

28. A method according to claim 13, wherein the locations of said points are not limited by a set of predetermined alternative routes.

29. A method according to claim 13, wherein said total path cost is the calculated cost from the start point to the points comprised in said selected group of points plus the estimated cost from said intermediate point to said end point.

30. A method according to claim 13, wherein said path is determined from medical image data and represents a path or a centerline along a blood vessel or other lumen in a body.

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

32. A method according to claim 1, wherein computing said path costs comprises solving an Eikonal equation.

33. A method according to claim 32 wherein solving comprises employing a finite-difference approximation to an Eikonal equation.

34. A method according to claim 32 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.

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

36. A method according to claim 1, wherein determining a path is carried out by a gradient descent method applied on said plurality of points and said selected group of points.

37. A method according to claim 36, wherein said gradient descent method is applied by:

(h) working backward from the target point to find a neighboring one of the selected group of points which has the lowest calculated cost;

(i) repeating (h) for points which are neighbors of the point determined in (h) to find the next lowest cost point;

(j) continuing iterations of (i) until a point is reached which has a total cost of zero; and

(k) stopping the iteration of (i) and recognizing the point having a total cost of as the start point.

38. A method according to claim 1, wherein selecting said group of points for further consideration is done iteratively based on said computed path costs;

and (f) is repeated for said iteratively selected points.

39. A method according to claim 12, wherein selecting said plurality of points comprises generating a discrete model of said physical space.

40. The method of claim 1, wherein the estimated total path costs to target is based on approximated total path cost for said selected group of points, where a total path cost is a function of the calculated costs from the start point to the points of said group of points and the estimated costs for said selected group of points to said target point.

41. The method of claim 40, wherein the path cost at the target point approximates a minimal path cost of a path from the start point to the target point in the physical space.