Tracing retinal vessel trees by transductive inference

Abstract

Background: Structural study of retinal blood vessels provides an early indication of diseases such as diabetic retinopathy, glaucoma, and hypertensive retinopathy. These studies require accurate tracing of retinal vessel tree structure from fundus images in an automated manner. However, the existing work encounters great difficulties when dealing with the crossover issue commonly-seen in vessel networks.

Results: In this paper, we consider a novel graph-based approach to address this tracing with crossover problem: After initial steps of segmentation and skeleton extraction, its graph representation can be established, where each segment in the skeleton map becomes a node, and a direct contact between two adjacent segments is translated to an undirected edge of the two corresponding nodes. The segments in the skeleton map touching the optical disk area are considered as root nodes. This determines the number of trees to-be-found in the vessel network, which is always equal to the number of root nodes. Based on this undirected graph representation, the tracing problem is further connected to the well-studied transductive inference in machine learning, where the goal becomes that of properly propagating the tree labels from those known root nodes to the rest of the graph, such that the graph is partitioned into disjoint sub-graphs, or equivalently, each of the trees is traced and separated from the rest of the vessel network. This connection enables us to address the tracing problem by exploiting established development in transductive inference. Empirical experiments on public available fundus image datasets demonstrate the applicability of our approach.

Conclusions: We provide a novel and systematic approach to trace retinal vessel trees with the present of crossovers by solving a transductive learning problem on induced undirected graphs.

Figure 1

Flowchart of our approach. Overview of the proposed tracing pipeline (Best view in color).

Figure 2

Visual comparison of the segmentation result on an exemplar fundus image.(A) Original image (DRIVE-Test-Image-19), and its ground-truth segmentation in (B). (C) Segmentation result of [10]. (D) Segmentation result of [6](E) Segmentation result of [7]. (F) Segmentation result of our method. (G) Original image (DRIVE-Test-Image-01). (H) Segmentation result of [5]. (I) Segmentation result of our method. If we pay close attention to the boxed regions, we can see that our segmentation step does a much better job at retaining the connectivity of the skeleton.

Figure 3

Notation on the skeleton pixels. Skeleton pixels are classified into the following three types: Body points – Pixels having 2 neighbors; Branching points – Pixels having 3 or more neighbors; Terminal points – Pixels having 1 neighbor, being either root or end pixels. A segment is thus defined as a continuous subset of skeleton pixels starts with a terminal/branching point, and ends with a branching/terminal point.

Figure 4

Shreve’s ordering. The vessel segments are ordered hierarchically. The ordering starts from the leaf segments which are assigned an order of 1. When two segments of order μ₁ and μ₂ meets then the resulting segments are given an order of μ₁+μ₂.

Figure 5

Modified Shreve’s ordering. Shreve’s ordering is modified to handle crossovers like A, B and C. For 4-cliques like A and B, when two segments with order μ₁ and μ₂ meets then the resulting segments are ordered as μ₁+μ₂. Similarly for 5-clique like C, when three segments with order μ₁, μ₂ and μ₃ meets then the resulting segments are ordered as μ₁+μ₂+μ₃.

Figure 6

Another modification in Shreve’s ordering. Shreve’s ordering is modified further to handle erroneous 3-cliques like C₂ in sub-figure (A) and (B). The C₂ in sub-figure (A) is caused by one segment terminating on another segment whereas the C₂ is sub-figure (B) is caused by wrong skeletonization of a 4-clique. In both the situations, segments cannot be ordered further as for a 3-clique at least two segments should be already ordered to assign an order to the third segment. This deadlock is overcome by measuring the angles between other segments for all those 3-cliques where only one segment is already ordered (let’s assume the order is μ). Among all these cliques we assign an order of μ+1 (for two unordered segments) to the clique which has smallest angle. The resulting orders are shown in sub-figure (C) and (D).

Figure 7

A graph simplification example.(A) A skeleton. The digits in black denotes segment orders whereas the digits in blue denotes segment indexes. (B) An unsimplified graph. (C) A simplified graph. The highlighted segments are particular examples of graph simplification.

Figure 8

Influence ofθ on the values of functionsf₁,f₂,f₃ and their correspondingW.(A) Variation of f₁(θ) with θ. (B) Variation of f₂(θ) and f₃(θ) with θ. (C)W corresponding to sub-figure (A). (D)W corresponding to sub-figure (B).

Figure 9

3-cliques.(A) A simple 3-clique. (B) A 3-clique created by the termination of one segment (red one) on another segment (blue one). (C) Two 3-cliques created by the wrong skeletonization of a 4-clique

Figure 10

A 4-clique. Here we know the (x,y) coordinates of points A,B,C,D in the image plane, so we can find the equation of straight lines $\overline{\mathit{\text{AC}}},\overline{\mathit{\text{BD}}},\overline{\mathit{\text{AB}}},\overline{\mathit{\text{BC}}},\overline{\mathit{\text{CD}}},\overline{\mathit{\text{AD}}}$. We take the pair of straight line equations $(\overline{\mathit{\text{AC}}},\overline{\mathit{\text{BD}}}),(\overline{\mathit{\text{AB}}},\overline{\mathit{\text{CD}}})$ and $(\overline{\mathit{\text{AD}}},\overline{\mathit{\text{BC}}})$ and find the intersecting points between the pairs. Only one pair $(\overline{\mathit{\text{AC}}},\overline{\mathit{\text{BD}}})$ intersect within the convex hull of points (A,B,C,D) while others pairs are either parallel or will intersect outside the convex hull. By using this we understand that A pairs with C and B pairs with D. Accordingly we assign (X,Z) (The segments containing points A and C) and (W,Y) (The segments containing points B and D) pair with weight from Equation 7 (Blue curve in Figure 8-D) and for other pairs we assign from Equation 8 (Red curve in Figure 8-D).

Figure 11

5- and 6-cliques.(A) A 5-clique. (B) A 6-clique. In both the scenarios weights are assigned using the same function as 3-cliques.

Figure 12

The introduction of small spurious segments. An illustrative example of the introduction of a small spurious segment when converting a binary segmentation into its skeleton map.

Figure 13

Tracing results: visual examples. Visualizing exemplar results for the tracing step. (A) Synthetic Image (B) Tracing without graph simplification for synthetic data. (C) Tracing with graph simplification for synthetic data. (D) Image from DRIVE dataset. (E) Tracing without graph simplification for DRIVE image. (F) Tracing with graph simplification for DRIVE image. (G) Image from STARE dataset. (H) Tracing without graph simplification for STARE image. (I) Tracing with graph simplification for STARE image.

Figure 14

Illustration on generating synthetic images.(A) An exemplar tree with low complexity. (B) An exemplar tree with medium complexity. (C) Illustration on how the synthetic image is generated.

Figure 15

Tracing: Synthetic dataset 1. Synthetic Dataset 1: Synthetic images with fixed number of trees and spread angle (angular distance between two adjacent trees), but with varying tree complexity. (A) Less complex image. (B) Complex image.

Figure 16

Tracing: Synthetic dataset 2. Synthetic Dataset 2: Synthetic images with fixed tree complexity and spread angle, but with varying tree numbers. (A), (B) are two synthetic images composed with different number of trees.

Figure 17

Tracing: Synthetic dataset 3. Synthetic Dataset 3: Synthetic images with fixed tree complexity and tree numbers, but with varying spread angle. (A), (B) are two synthetic images composed with different spread angles.

Figure 18

Preparation prior to computing the DIADEM score. Preparing the computation of the DIADEM score: Address the self-intersection issues of the tracing results as illustrated in (A), (B), and (C).

Figure 19

Tracing results: synthetic experiments. Performance on synthetic dataset. (A) Performance of algorithm with graph simplification with varying k for Dataset 1 (B) Performance of algorithm with graph simplification with varying k for Dataset 2. (C) Performance of algorithm with graph simplification with varying k for Dataset 3. (D) Comparing the performance of algorithm with graph simplification (in red) and without graph simplification (in blue) for Datset 1. (E) Comparing the performance of algorithm with graph simplification (in red) and without graph simplification (in blue) for Datset 2. (F) Comparing the performance of algorithm with graph simplification (in red) and without graph simplification (in blue) for Datset 3.

Figure 20

Tracing results: effect of internal parameters. The effect on performance by varying internal parameters of the proposed method. The top row denotes the performance for DRIVE dataset and the bottom row denotes the performance for STARE dataset.

Figure 21

Our segmenter: Based on existing methods.(A) Original color fundus image. (B) Supervised segmentation result with the highest F1 score. (C) Supervised segmentation result with the highest recall. (D) Unsupervised segmentation method. (E) Two branches are wrongly segmented into one, small branches are disconnected. (F) Small branches are often connected back here. (G) Two branches are often kept separated from each other.

Figure 22

Our segmenter: Combining the segmentation results.(A) The partial result so ar, by combining the best elements from Figure 7B-D. (B) Final segmentation result. (C)-(D) Zoom-in views that reveals small branches are still disconnected. (E)-(F) After the re-connection procedure described in Section ‘Experimental results’, Small branches are now connected.