Dijkstra's algorithm and extraction of medical imaging of the celebral vasculature

This report will try to show how Dijkstra’s algorithm can be applied in medicine, in particular how Verscheure et al show in their paper ‘Dijkstra's algorithm applied to 3D skeletonization of the brain vascular tree: Evaluation and application to symbolic description’ how the problem of extracting a 3D skeleton from a human brain’s blood vessel network - a vascular tree - can be solved, even out of considerable amounts of imaging data. Since the vascular network is a tree-like graph it does make sense to explore the imaging data with the help of an algorithm such as by Dijkstra that optimises exploration time through a vast network of interconnected nodes and paths.

Dijkstra

It is another of the distinct features of Dijkstra’s algorithm to find the shortest path from any node to any other connected node of a graph. As it expands to a node it updates the shortest distances found to that node in a queue, to be precise a priority queue. The algorithm stops when all points in the queue are processed and all shortest paths from the starting node to all other nodes are found.

Skeletonization

In order to represent the brain vasculature Verscheure et al have chosen to construct a tree-like three-dimensional shape by systematically exploring the data provided by the imaging methods. The authors make use of Dijkstra’s algorithm in order to measure the paths and nodes of the celebral vasculature in the imaging data. The scientists start with the branch that has the maximum depth by using Depth First Search, calling this branch the ‘centerline’ and then letting Dijkstra’s algorithm run over that centerline and recursively on each connected branch. This way even the most distal vasculature will be extracted from the imaging data. The resulting graph is three dimensional, the data can be stored as an object oriented model and it is weighted, meaning that the shortest distance to each vasculature junction will be known.

skeleton1

The authors tested their approach with phantoms, artificial vascular models, and successfully verfied their data with the original. The authors state that there exist numerous vessels extraction methods, but for the added difficulty of constructing a 3D model, Dijkstra’s algorithm was the most appropriate giving additional benefits. Such as that the data gathered by Dijkstra’s algorithm allows simulating blood flow inside the vascular network and most notably the data can be used to reduce risks during brain surgery by “discerning possible collisions between electrodes and cerebral vascular network” (Verscheure, 2010).

A*

There are however alternatives to Dijkstra’s algorithm, which are indeed faster. A*, pronounced ‘A-Star’, by Hart, Nilsson and Raphael of Stanford Research Institute is an extension of Dijkstra’s algorithm. A* calculates an evaluation function f(n) to determine the optimal path through a node n.

$$ \hat f(n) = \hat g(n) + \hat h(n) $$

f(n) is comprised of the optimal path g(n) from the starting node s to the current node n found so far by A* and an approximation of the optimal path h(n) to a goal node of n (Hart et al, 1968). The evaluation function f(n) is used to sort a priority queue we know from Dijkstra’s algorithm already. In most practical cases A* is more efficient than Dijkstra’s solution, to be precise if h is perfectly estimated the number of nodes processed is minimised and time efficiency is maximised, which means A* will be faster than Dijkstra’s algorithm. (please note: due to formatting issues, think of a 'hat' symbol on top of f,g and h)

Conclusion

While it is conceivable that A* might have improved the performance of Verscheure et al’s 3D skeletonizsation it seems that Verscheure et al’s focus wasn’t only time efficiency but to construct an accurately weighted graph.

References

Verscheure, L., Peyrodie, L., Makni, N., Betrouni, N., Maouche, S., Vermandel, M. (2010) ‘Dijkstra's algorithm applied to 3D skeletonization of the brain vascular tree: Evaluation and application to symbolic description’, Engineering in Medicine and Biology Society (EMBC), 2010 Annual International Conference of the IEEE, vol. 3081-4.

Hart, P.E., Nilsson, N.J., Raphael, B. (1968) ‘A Formal Basis for the Heuristic Determination of Minimum Cost Paths’, IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107.