Matching 3-D prone and supine CT colonography scans using graphs

Abstract

In this paper, we propose a new registration method for prone and supine computed tomographic colonography scans using graph matching. We formulate 3-D colon registration as a graph matching problem and propose a new graph matching algorithm based on mean field theory. In the proposed algorithm, we solve the matching problem in an iterative way. In each step, we use mean field theory to find the matched pair of nodes with highest probability. During iterative optimization, one-to-one matching constraints are added to the system in a step-by-step approach. Prominent matching pairs found in previous iterations are used to guide subsequent mean field calculations. The proposed method was found to have the best performance with smallest standard deviation compared with two other baseline algorithms called the normalized distance along the colon centerline (NDACC) ( p = 0.17) with manual colon centerline correction and spectral matching ( p < 1e-5). A major advantage of the proposed method is that it is fully automatic and does not require defining a colon centerline for registration. For the latter NDACC method, user interaction is almost always needed for identifying the colon centerlines.

Fig. 1

Prone and supine three-dimensional CTC surface reconstructions of the colon of a 65 year old man. Colon centerlines shown in green.

Fig. 2

A 3D graph constructed from a CTC scan. Colored lines represent links between key points identified by the n-SIFT algorithm. For each link, its color in RGB color space is determined by its XYZ coordinates, respectively. Blue square shows location of a colonic polyp.

Fig. 3

The proposed graph matching algorithm based on mean field theory.

Fig. 4

System diagram of the proposed non-centerline based prone/supine registration method.

Fig. 5

Matching results of (a) n-SIFT and (b) our proposed algorithms. We show 3D renderings of the segmented colon from prone (left) and supine (right) CTC scans. Pink lines between the scans indicate matched key points on prone and supine colons.

Fig. 6

Four landmarks matched by our algorithm (shown by green line between scans). The constructed graphs are shown in blue lines overlapped on the 3D renderings of scans. The ranks of the four matched vertices are 1, 3, 6 and 7 from (a) to (d), respectively. There are 50 ranked vertices for each scan. The rank of a matching link is defined as the order it is identified or fixed during the iterative optimization process.

Fig. 7

Registration errors for the three colon registration methods on the test set. For NDACC, we show results with and without manual correction of the colon centerline. The proposed method, NDACC with manual centerline correction, and spectral matching had lowest registration errors on 11, 7 and 2 polyps, respectively.