Method and system for graph based interactive detection of curve structures in 2D fluoroscopy

1. A method for detecting a curve structure in an image, comprising:

detecting a plurality of curve segments in the image;

generating a graph based on the curve segments, wherein the graph comprises a plurality of nodes, including a respective node corresponding to each of the plurality of curve segments detected in the image, and a plurality of edges connecting the plurality of nodes, wherein each node of the plurality of nodes is connected by respective edges to multiple other nodes of the plurality of nodes and each edge represents a possible connection between the curve segments corresponding to the nodes connected by the edge; and

detecting a curve structure in the image by determining a path from a source node to a destination node in the graph.

2. The method of claim 1 , wherein the step of detecting a plurality of curve segments in the image comprises:

detecting piece-wise curve segments in the image using a trained piece-wise curve segment detector; and

detecting pair-wise probabilities of pairs of the piece-wise curve segments using a trained pair-wise curve segment detector, wherein the pair-wise probability of each pair of the piece-wise curve segments quantifies a probability of a connection between the pair of piece-wise curve segments.

3. The method of claim 2 , wherein the step of generating a graph based on the curve segments comprises:

associating an edge cost with each edge of the graph based on the pair-wise probability detected between the curve segments corresponding to the nodes connected by each edge.

4. The method of claim 1 , wherein the step of generating a graph based on the curve segments comprises:

generating the source node and the destination node of the graph based on user inputs.

5. The method of claim 3 , wherein the step of detecting a curve structure in the image comprises:

detecting a shortest path in the graph based on the edge costs associated with the edges in the graph.

6. The method of claim 1 , wherein the step of detecting a curve structure in the image comprises:

constructing a hyper-graph based on the graph, wherein the hyper-graph comprises a plurality of hyper-nodes, each corresponding to an edge in the graph, and a plurality of hyper-edges connecting hyper-nodes that correspond to edges that share a node in the graph; and

detecting a shortest path from a first hyper-node corresponding to an edge connected to the source node in the graph to a second hyper-node corresponding to an edge connected to the destination node in the graph, based on hyper-node costs and hyper-edge costs in the hyper-graph.

7. The method of claim 6 , wherein the step of constructing a hyper-graph based on the graph comprises:

associating each hyper-node in the hyper-graph with a hyper-node cost corresponding to an edge cost of the corresponding edge in the graph; and

associating each hyper-edge in the hyper-graph with a hyper-edge cost that imposes geometric constraints on a curve path represented by each hyper-edge.

8. The method of claim 7 , wherein the step of associating each hyper-edge in the hyper-graph with a hyper-edge cost that imposes geometric constraints on a curve path represented by each hyper-edge comprises:

associating each hyper-edge with a hyper-edge cost that imposes a smoothness constraint and a shortness constraint on the curve path represented by each hyper-edge.

9. The method of claim 6 , wherein the step of detecting a shortest path from a first hyper-node corresponding to an edge connected to the source node in the graph to a second hyper-node corresponding to an edge connected to the destination node in the graph, based on hyper-node costs and hyper-edge costs in the hyper-graph comprises:

detecting a plurality of shortest paths in the hyper-graph, each from a respective one of a plurality of hyper-nodes corresponding to a plurality of edges connected to the source node in the graph to one of a plurality of hyper-nodes corresponding to a plurality of edges connected to the destination node in the graph; and

selecting one of the plurality of shortest paths with the lowest cost.

10. The method of claim 6 , wherein the step of detecting a curve structure in the image further comprises:

mapping the detected shortest path in the hyper-graph to a path in the graph.

11. The method of claim 1 , wherein the step of detecting a curve structure in the image comprises:

detecting an initial curve structure in the image by detecting a shortest path in the graph based on edge costs of the edges in the graph;

removing nodes from the graph corresponding to curve segments greater than a certain distance from the initial curve structure in the image;

constructing a hyper-graph based on the remaining nodes in the graph, wherein the hyper-graph comprises a plurality of hyper-nodes, each corresponding to an edge in the graph, and a plurality of hyper-edges connecting hyper-nodes that correspond to edges that share a node in the graph; and

detecting the curve structure by detecting a shortest path in the hyper-graph based on hyper-node costs and hyper-edge costs.

12. An apparatus for detecting a curve structure in an image, comprising:

a processor; and

a memory storing computer program instructions, which when executed by the processor cause the processor to perform operations comprising:

detecting a plurality of curve segments in the image;

generating a graph based on the curve segments, wherein the graph comprises a plurality of nodes, including a respective node corresponding to each of the plurality of curve segments detected in the image, and a plurality of edges connecting the plurality of nodes, wherein each node of the plurality of nodes is connected by respective edges to multiple other nodes of the plurality of nodes and each edge represents a possible connection between the curve segments corresponding to the nodes connected by the edge; and

detecting a curve structure in the image by determining a path from a source node to a destination node in the graph.

13. The apparatus of claim 12 , wherein detecting a plurality of curve segments in the image comprises:

detecting piece-wise curve segments in the image using a trained piece-wise curve segment detector; and

detecting pair-wise probabilities of pairs of the piece-wise curve segments using a trained pair-wise curve segment detector, wherein the pair-wise probability of each pair of the piece-wise curve segments quantifies a probability of a connection between the pair of piece-wise curve segments.

14. The apparatus of claim 13 , wherein generating a graph based on the curve segments comprises:

associating an edge cost with each edge of the graph based on the pair-wise probability detected between the curve segments corresponding to the nodes connected by each edge.

15. The apparatus of claim 12 , wherein generating a graph based on the curve segments comprises:

generating the source node and the destination node of the graph based on user inputs.

16. The apparatus of claim 14 , wherein detecting a curve structure in the image comprises:

detecting a shortest path in the graph based on the edge costs associated with the edges in the graph.

17. The apparatus of claim 12 , wherein detecting a curve structure in the image comprises:

constructing a hyper-graph based on the graph, wherein the hyper-graph comprises a plurality of hyper-nodes, each corresponding to an edge in the graph, and a plurality of hyper-edges connecting hyper-nodes that correspond to edges that share a node in the graph; and

detecting a shortest path from a first hyper-node corresponding to an edge connected to the source node in the graph to a second hyper-node corresponding to an edge connected to the destination node in the graph, based on hyper-node costs and hyper-edge costs in the hyper-graph.

18. The apparatus of claim 17 , wherein constructing a hyper-graph based on the graph comprises:

associating each hyper-node in the hyper-graph with a hyper-node cost corresponding to an edge cost of the corresponding edge in the graph; and

associating each hyper-edge in the hyper-graph with a hyper-edge cost that imposes geometric constraints on a curve path represented by each hyper-edge.

19. The apparatus of claim 17 , wherein detecting a shortest path from a first hyper-node corresponding to an edge connected to the source node in the graph to a second hyper-node corresponding to an edge connected to the destination node in the graph, based on hyper-node costs and hyper-edge costs in the hyper-graph comprises:

detecting a plurality of shortest paths in the hyper-graph, each from a respective one of a plurality of hyper-nodes corresponding to a plurality of edges connected to the source node in the graph to one of a plurality of hyper-nodes corresponding to a plurality of edges connected to the destination node in the graph; and

selecting one of the plurality of shortest paths with the lowest cost.

20. The apparatus of claim 12 , wherein detecting a curve structure in the image comprises:

detecting an initial curve structure in the image by detecting a shortest path in the graph based on edge costs of the edges in the graph;

removing nodes from the graph corresponding to curve segments greater than a certain distance from the initial curve structure in the image;

constructing a hyper-graph based on the remaining nodes in the graph, wherein the hyper-graph comprises a plurality of hyper-nodes, each corresponding to an edge in the graph, and a plurality of hyper-edges connecting hyper-nodes that correspond to edges that share a node in the graph; and

detecting the curve structure by detecting a shortest path in the hyper-graph based on hyper-node costs and hyper-edge costs.

21. A non-transitory computer readable medium encode with computer executable instructions for detecting a curve structure in an image, the computer executable instructions defining steps comprising:

detecting a plurality of curve segments in the image;

generating a graph based on the curve segments, wherein the graph comprises a plurality of nodes, including a respective node corresponding to each of the plurality of curve segments detected in the image, and a plurality of edges connecting the plurality of nodes, wherein each node of the plurality of nodes is connected by respective edges to multiple other nodes of the plurality of nodes and each edge represents a possible connection between the curve segments corresponding to the nodes connected by the edge; and

detecting a curve structure in the image by determining a path from a source node to a destination node in the graph.

22. The computer readable medium of claim 21 , wherein the computer executable instructions defining the step of detecting a plurality of curve segments in the image comprise computer executable instructions defining the steps of:

detecting piece-wise curve segments in the image using a trained piece-wise curve segment detector; and

detecting pair-wise probabilities of pairs of the piece-wise curve segments using a trained pair-wise curve segment detector, wherein the pair-wise probability of each pair of the piece-wise curve segments quantifies a probability of a connection between the pair of piece-wise curve segments.

23. The computer readable medium of claim 22 , wherein the computer executable instructions defining the step of generating a graph based on the curve segments comprise computer executable instructions defining the step of:

associating an edge cost with each edge of the graph based on the pair-wise probability detected between the curve segments corresponding to the nodes connected by each edge.

24. The computer readable medium of claim 21 , wherein the computer executable instructions defining the step of generating a graph based on the curve segments comprise computer executable instructions defining the step of:

generating the source node and the destination node of the graph based on user inputs.

25. The computer readable medium of claim 23 , wherein the computer executable instructions defining the step of detecting a curve structure in the image comprise computer executable instructions defining the step of:

detecting a shortest path in the graph based on the edge costs associated with the edges in the graph.

26. The computer readable medium of claim 21 , wherein the computer executable instructions defining the step of detecting a curve structure in the image comprise computer executable instructions defining the steps of:

constructing a hyper-graph based on the graph, wherein the hyper-graph comprises a plurality of hyper-nodes, each corresponding to an edge in the graph, and a plurality of hyper-edges connecting hyper-nodes that correspond to edges that share a node in the graph; and

detecting a shortest path from a first hyper-node corresponding to an edge connected to the source node in the graph to a second hyper-node corresponding to an edge connected to the destination node in the graph, based on hyper-node costs and hyper-edge costs in the hyper-graph.

27. The computer readable medium of claim 26 , wherein the computer executable instructions defining the step of constructing a hyper-graph based on the graph comprise computer executable instructions defining the steps of:

associating each hyper-node in the hyper-graph with a hyper-node cost corresponding to an edge cost of the corresponding edge in the graph; and

associating each hyper-edge in the hyper-graph with a hyper-edge cost that imposes geometric constraints on a curve path represented by each hyper-edge.

28. The computer readable medium of claim 26 , wherein the computer executable instructions defining the step of detecting a shortest path from a first hyper-node corresponding to an edge connected to the source node in the graph to a second hyper-node corresponding to an edge connected to the destination node in the graph, based on hyper-node costs and hyper-edge costs in the hyper-graph comprise computer executable instructions defining the steps of:

detecting a plurality of shortest paths in the hyper-graph, each from a respective one of a plurality of hyper-nodes corresponding to a plurality of edges connected to the source node in the graph to one of a plurality of hyper-nodes corresponding to a plurality of edges connected to the destination node in the graph; and

selecting one of the plurality of shortest paths with the lowest cost.

29. The computer readable medium of claim 21 , wherein the computer executable instructions defining the step of detecting a curve structure in the image comprise computer executable instructions defining the steps of:

detecting an initial curve structure in the image by detecting a shortest path in the graph based on edge costs of the edges in the graph;

removing nodes from the graph corresponding to curve segments greater than a certain distance from the initial curve structure in the image;

constructing a hyper-graph based on the remaining nodes in the graph, wherein the hyper-graph comprises a plurality of hyper-nodes, each corresponding to an edge in the graph, and a plurality of hyper-edges connecting hyper-nodes that correspond to edges that share a node in the graph; and

detecting the curve structure by detecting a shortest path in the hyper-graph based on hyper-node costs and hyper-edge costs.