Optimal scheduling of tracing computations for real-time vascular landmark extraction from retinal fundus images

Recently, this group published fast algorithms for automatic tracing (vectorization) of the vasculature in live retinal angiograms, and for the extraction of visual landmarks formed by vascular bifurcations and crossings. These landmarks are used for feature-based image matching for controlling a computer-assisted laser retinal surgery instrument currently under development. This paper describes methods to schedule the vascular tracing computations to maximize the rate of growth of quality of the partial tracing results within a frame cycle. There are two main advantages. First, progressive image matching from partially extracted landmark sets can be faster, and provide an earlier indication of matching failure. Second, the likelihood of successful image matching is greatly improved since the extracted landmarks are of the highest quality for the given computational budget. The scheduling method is based on quantitative measures for the computational work and the quality of landmarks. A coarse grid-based analysis of the image is used to generate seed points for the tracing computations, along with estimates of local edge strengths, orientations, and vessel thickness. These estimates are used to define criteria for real-time preemptive scheduling of the tracing computations. It is shown that the optimal schedule can only be achieved in perfect hindsight, and is thus unrealizable. This leads to scheduling heuristics that approximate the behavior of the optimal algorithm. One such approximation produced approximately 400% improvement in the quality of the partial results at a defined milestone, as compared to random scheduling. The resulting algorithm can be readily implemented on conventional and multiple-processor systems, and is being applied to computer-assisted laser retinal surgery.