1 Introduction

Groupwise registration is key to population analysis of medical images. Unbiased groupwise registration is important for population analysis for discovering imaging biomarkers of neurological disorders, such as Alzheimer’s disease (AD) [1]. Unlike conventional pairwise registration, which aligns one image to another, groupwise registration aims to simultaneously align a set of images to their common space, i.e., the population center, thus facilitating the subsequent data analysis.

For over a decade, many groupwise registration methods have been proposed. The most straightforward way is to register each image to a selected template. To reduce the bias, Park et al. [2] chose the template image as the geometrical mean of the image set. Hamm et al. [3] built a spanning tree on a learned intrinsic geodesic image manifold, where the template image was selected as the median of the manifold. One major drawback of these methods is that the selected template image will inevitably introduce bias to the subsequent image analysis result, since the brain anatomies vary across individuals [4].

To avoid the bias introduced by selecting a specific subject as the template, unbiased groupwise registration methods were proposed [5,6,7], where the population center is estimated in a data-driven manner. Joshi et al. [5] proposed to calculate the initial tentative group mean by averaging the images after affine registration. Then, all images were aligned to this initial mean image by using diffeomorphic Demons [8]. These two steps were alternatively repeated until convergence, i.e., computing the group mean image from the warped images and aligning the warped images to the newly computed group mean image. However, one major drawback of this method is that the final registration accuracy could be limited by an initial blurry group mean image, especially for registering a group of images with large anatomical variations. To alleviate this limitation, data distribution was taken into consideration. Jia et al. [6] proposed a method called ABSORB to progressively move each image towards the group center by using the average deformation field calculated from its neighbor images in the image manifold. In a later study, Ying et al. [7] proposed a method called HUGS, which harnessed the image distribution in the image manifold using a graph. Then, the groupwise registration task was formulated as a dynamic graph shrinkage problem. Although these proposed groupwise registration methods can produce accurate group mean images, the computational cost is very expensive, which makes them less effective in real clinical application, especially when dealing with the large-scale dataset.

In this paper, we propose an efficient groupwise registration method for aligning MR brain images, which may potentially have large anatomical variations by using hierarchical graph set shrinkage. To handle images with large anatomical variation, we propose to use a hierarchical graph set to model the heterogeneous image distribution. The main idea is to divide the complex registration problem into multiple easy-to-solve registration problems. Thus, the whole registration process can be conducted accurately and efficiently. The main contributions can be summarized as follows.

  1. (1)

    We hierarchically divide the whole image set into multiple clusters. Then, we employ two types of graph shrinkage to register the heterogeneous distributed image set: (1) using intra-graph shrinkage to register the images within each cluster, and (2) using inter-graph shrinkage to register the cluster exemplar images from different clusters. Thus, the whole registration framework considers image distribution both locally and globally.

  2. (2)

    The registration can be performed efficiently by using the hierarchical graph set, where the deformation field of each image to the population center can be calculated by composing multiple small deformation fields of the neighboring images throughout the graph set.

We evaluated our method in registering 100 images with large anatomical variations from ADNI dataset and also compared it with two state-of-the-art groupwise registration methods, i.e., ABSORB [6] and HUGS [7].

2 Method

Our goal is to accurately register a set of brain images to their group center in an efficient manner. To achieve this goal, first, we divide the whole image set into multiple clusters hierarchically by using affinity propagation (AP) [9]. Then, we use two types of graphs, i.e., intra-graph and inter-graph, to hierarchically model the image distribution both within each cluster and across different clusters. Next, we formulate the groupwise registration into a series of simple graph shrinkage problems, where the entire image set can be registered to its population center both accurately and efficiently.

2.1 Hierarchical Image Clustering

Given a set of linearly aligned images \( \varvec{I}\, = \,\{ I_{i} \,|i\, = \,1,\, \ldots \,N\} \), we aim to hierarchically divide the image set into multiple clusters, where images within each cluster have similar image appearance, while images falling into different image clusters exhibit anatomical variability. Specifically, we employ the affinity propagation (AP) to perform the image clustering. Compared to other clustering methods, the advantage of using AP clustering method is that no pre-defined number of clusters is required. The method clusters the image set by using an image similarity matrix S. The non-diagonal elements of the similarity matrix \( s\left( {i,j} \right)\left( {i,j\, \in \,\left[ {1,N} \right],i\, \ne \,j} \right) \) are calculated as the negative sum of squared distance (SSD) of the two images Ii and Ij, i.e., \( s\left( {i,j} \right)\, = \, - d_{i,\,j} \, = \, - \left\| {I_{i} - I_{j} } \right\|^{2} \). The diagonal element of matrix S is set to the preference value p. Since no prior knowledge is available for the input image set, all the diagonal elements of S are set to the same value, i.e., equal to the median of the input similarities, to generate a moderate number of clusters. Because the AP clustering method has no regulation on the number of images within each cluster, after the first round of AP clustering, some clusters may still contain a large number of images, as shown in Fig. 1. Thus, for the clusters with a large number of images, we iteratively perform the AP clustering method for these clusters until the number of images within each cluster is below a pre-defined number. Finally, we can divide the whole image set into hierarchical clusters.

Fig. 1.
figure 1

Illustration of a simple 2-round AP clustering on the image manifold.

Full size image

2.2 Construction of Hierarchical Graph Set

Upon obtaining the hierarchical image clusters, we build a series of graphs to model both the local and global image distribution using two types of graphs, i.e., intra-graph and inter-graph, as illustrated in Fig. 2. The intra-graph models the image distribution within each cluster, and the inter-graph models the image distribution across different clusters.

Fig. 2.
figure 2

Illustration of construction of hierarchical graph set.

Full size image

For the construction of intra-graph, we follow the graph construction method used in [7]. Specifically, by using a line-search based method, all images within the cluster are linked to a single graph, and the number of edges within the graph is minimized. The vertices of the graph represent all images within the same cluster, and the edge of the graph suggests that two connected images are similar. The topology of each constructed intra-graph is kept throughout the registration process to maintain the image distribution locally on the manifold within the image cluster. To move each image unbiasedly towards their group center within the cluster, each vertex of the graph is associated with a vertex label, which is defined by the degree of the graph vertex, i.e., the number of edges connected to the vertex. It will influence the speed of the image moving along the image manifold. Clearly, the larger the value of the vertex label, the more similar the current image is compared with other images, and the slower the image will move towards the group center. The advantage of assigning each vertex a label value is important for achieving unbiased registration.

For the construction of inter-graph, each vertex is the exemplar image of each cluster, where the exemplar image is chosen as one of the warped images in each cluster, which has the highest label vertex value. Each exemplar image is also associated with a vertex label value, which equals to the value of total vertex degree of the represented image cluster. As shown in Fig. 2, by constructing both intra-graph and inter-graph, the graph set can be constructed hierarchically from the clusters at the bottom level to the clusters at the top level.

2.3 Groupwise Image Registration via Hierarchical Graph Shrinkage

With the constructed hierarchical graph set, the groupwise registration for the entire dataset can be achieved by solving a series of dynamic simple graph shrinkage problems through the hierarchical graph set from the image clusters at the bottom level towards the image clusters at the top level. Specifically, for a certain image \( I_{i} \) located in an image cluster at the bottom level, we first obtain the deformation field \( \varphi_{i}^{1} \) using the intra-graph shrinkage, which warps the image \( I_{i} \) to the group center at the bottom level. Then, by using the inter-graph shrinkage at the next level, we can obtain the deformation field that warps the exemplar image to the group center at the next level. In this way, by performing the graph shrinkage hierarchically from the bottom level to the top level along the hierarchical graph set, a set of deformation fields \( \varvec{\varphi }_{i} = \{ \varphi_{i}^{p} |p = 1, \ldots ,P\left( i \right)\} \) can be obtained, where \( P\left( i \right) \) denotes the total number of deformation fields for image Ii warped from the bottom level to the whole-image-set group center IGC. Finally, the whole deformation pathway \( \psi_{i} \), which warps the image Ii to IGC, can be obtained by composing each part of the deformation fields in \( \varvec{\varphi }_{i} \):

$$ \psi_{i} = \varphi_{i}^{1} \circ \varphi_{i}^{2} \circ \cdots \circ \varphi_{i}^{P\left( i \right)} . $$
(1)

In this way, the final deformation field set \( {\varvec{\Psi}} = \{ \psi_{i} | i = 1, \ldots ,N\} \) can be obtained, which can be used to warp every respective image to the group center IGC.

There are two reasons that why the whole groupwise registration process can be efficiently performed. First, for intra-graph shrinkage, the registration process can be converged with only a few iterations, since all image appearances within the image cluster are similar. Second, for inter-graph shrinkage, the total number of the graph vertices (exemplar image) is small, since only one exemplar image is used for each cluster. Thus, the computational cost is not expensive. Therefore, our method can significantly reduce the computational time.

3 Experiments and Results

To verify the effectiveness of our method, we evaluated the method for registering one hundred brain images, which were randomly selected from ADNI dataset. For the selected images, we randomly selected 50 subjects from the normal control (NC) group and the other 50 images from the AD group. Before performing groupwise registration, all images were pre-processed by the following steps. First, all images were resampled and cropped to an image size of 196 × 164 × 176 with a voxel size of 1 × 1 × 1 mm3. Then, we used N3 algorithm [10] to correct the intensity inhomogeneity. After that, we employed Brain Extraction Tool (BET) [11] for skull stripping. Then, we selected one image sitting in the median of the geodesic image manifold as the template image, and all the remaining images were linearly aligned to this template by using FLIRT [12]. Next, we segmented each image into three brain tissues of gray matter (GM), white matter (WM) and cerebrospinal fluid (CSF) by using FAST [13]. These tissue segmentations were then manually corrected by visual inspection and were used as the ground truth for evaluating the registration performance. Figure 3 illustrates typical intensity images and their corresponding segmented images from the NC group (left three columns) and the AD group (right three columns).

Fig. 3.
figure 3

Typical MR brain images and the corresponding tissue labels from ADNI dataset. The darker yellow, light yellow and blue represent brain tissue types of GM, WM, and CSF, respectively. (Color figure online)

Full size image

To quantitatively evaluate our method, we employed Dice ratio to measure the tissue overlap after groupwise registration. The Dice ratio is defined as \( DR = 2 \times \left| {A \cap B} \right|/(\left| A \right| + \left| B \right| \)), where A and B are the two corresponding tissue regions in the two aligned brain images. Since no label image was available in the common space of the group center, we used a majority voting method on all registered images to compute a label image in the common space. The Dice ratio of different brain tissue type for each image can be then calculated with respect to the created label image in the common space.

To illustrate the registration performance of our method compared with the state-of-the-art groupwise registration methods, Fig. 4(a) shows the progression curve of the overall Dice ratio at each iteration when performing groupwise registration. It can be observed that our method achieved the best registration accuracy with only a few iterations, compared with the other methods. By regarding the maximum performance as the one with the slope of progression curve smaller than 0.001, the ABSORB method reached its maximum performance at 11th iteration with Dice ratio of 83.6%. HUGS attained its maximum performance at 15th iteration with Dice ratio of 89.3%. Our proposed method (HML) obtained its maximum Dice ratio at 6th iteration with overall Dice ratio of 90.3%. By using a t-test, our method significantly outperformed state-of-the-art registration methods. In addition, our method can also significantly reduce the computational time compared with the best counterpart method (HUGS). Figure 4(b) illustrates the computational time of each method for reaching their maximum performance. It shows that our method saves about six times the computational cost compared with the HUGS method. Figure 5 shows the group mean images of all registered 100 brain images by the three groupwise registration methods in achieving their maximum registration performance. As can be seen, the group mean image of our method has more anatomical details compared to the other two methods.

Fig. 4.
figure 4

(a) Progression curve of the overall Dice ratio of the three brain tissue types, i.e., GM, WM, and CSF, during the groupwise registration by the three methods on the ADNI dataset. (b) Time cost comparison between our method and the other two methods in registering 100 images from ADNI dataset for achieving the maximum registration performance at the n-th iteration.

Full size image
Fig. 5.
figure 5

Group mean images of the three groupwise registration methods (left: ABSORB; middle: HUGS; right: HML) at their maximum performance.

Full size image

4 Conclusion

In this paper, we proposed an accurate and efficient groupwise registration method for registering MR brain images that may pose large anatomical variations. After hierarchically dividing the whole image set into multiple image clusters, we employed two types of graphs, i.e., intra-graph and inter-graph, to model the local and the global image distributions hierarchically. Then, the whole image registration can be achieved by solving a series of simple graph shrinkage problems, where each simple graph shrinkage can be calculated both accurately and efficiently. Our method was successfully applied to registering 100 brain images with large anatomical variations. Experimental results showed that our method could an provide more accurate registration result while significantly reducing the computational cost, compared to state-of-the-art groupwise registration methods.