Abstract
In this paper, we introduce a nonrigid registration method using a Markov Random Field (MRF) energy model with second-order smoothness priors. The registration determines an optimal labeling of the MRF energy model where the label corresponds to a 3D displacement vector. In the MRF energy model, spatial relationships are constructed between nodes using second-order smoothness priors. This model improves limitations of first-order spatial priors which cannot fully incorporate the natural smoothness of deformations. Specifically, the second-order smoothness priors can generate desired smoother displacement vector fields and do not suffer from fronto-parallel effects commonly occurred in first-order priors. The usage of second-order priors in the energy model enables this method to produce more accurate registration results. In the experiments, we will show comparative results using uni-and multi-modal Brain MRI volumes.
INTRODUCTION
Recently, nonrigid registration methods based on a Markov Random Field (MRF) energy model incorporating the discrete energy optimization [1, 2] showed the promising experimental results [3, 4, 5] . These methods model the deformation pattern as a discrete label set where labels correspond to displacements of control points (nodes) placed on a cubic mesh grid. The energy is constructed via the standard pairwise MRF model 
INTRODUCTION
where V is a set of nodes placed on a cubic grid, E is a set of edges incorporating neighborhood information of nodes, and x s is the label of s ∈ V. In this model, the data cost θ s is computed using similarity measures between reference and input images and the smoothness cost θ st is computed using displacement differences between s and t. For θ st , the following first-order smoothness prior (truncated linear potential) is conventionally used
θst(xs, xt) λst min ( d(xs) − d(xt) 1, Tst)
where λ st is the regularization constant, d(x s ) represents the 3D displacement vector corresponding to the label x s , and T st is a threshold for truncation. However, the energy models based on (2) have limitations. The pairwise potentials penalize the global transformations of the mesh, such as rotation and scaling movements. Mesh nodes are needed to be remained at initial position or translated all together to get low energy. These problems correspond to fronto-parallel effects in stereo matching. In nonrigid registrations, irregular spacing between neighboring nodes in recovered vector fields is commonly appeared by these limitations.
θst(xs, xt) λst min ( d(xs) − d(xt) 1, Tst)
To overcome these limitations, Kwon et al. [6] proposed a registration method using higher-order MRF energy model. This method incorporates second-order spatial interactions to represent natural smoothness of displacement fields. The energy model is formulated using factor graph notations and factor to pairwise graph conversion is used for applying belief propagation (BP) variant optimization methods. In experiments, they showed promising results using 2D images.
θst(xs, xt) λst min ( d(xs) − d(xt) 1, Tst)
Here, we introduce a nonrigid volume registration method using a MRF based energy model. The proposed method extends the second-order MRF model proposed in [6] to work on 3D volumes. As displacements are 3D vectors, graph models in [6] are modified to involve ternary potentials for interlayer interactions in the decomposed scheme. Also, we apply a coarse-to-fine registration scheme for efficient computations and sub-pixel accuracy. In next sections, the proposed MRF energy model for registration is described, and optimization strategies are introduced. In experiments, the proposed method is compared with a first-order MRF registration method [3] using uni-and multi-modal brain MRI data.
MRF ENERGY MODEL FOR REGISTRATION
For an input volume, we construct a set V which consists of nodes placed on each voxel. Then we generate a factor graph [7] G F = (V, F H ) where F H is a set of factors for second-order potentials. For each s ∈ V, let x s be a label taking values in some discrete set L. A function d : L → R 3 maps a label to a corresponding 3D displacement where each label x s corresponds to a displacement vector d(
MRF ENERGY MODEL FOR REGISTRATION
is defined for each node s ∈ V and a second-order potential θ stu (x s , x t , x u ) is defined for each factor (s, t, u) ∈ F H . 1 
Second-Order Smoothness Prior
In [8] , deformation energy of the mesh is usually defined as a sum of squared second derivatives of its nodes. This deformation energy describes the natural representation of inherent deformedness of the mesh which depends only on the relative locations of mesh nodes. Following the analysis on [6] , we incorporate second-order smoothness priors into the energy model. To apply second-order smoothness priors, the ternary potential θ stu (x s , x t , x u ) is constructed on every collinear three nodes s, t and u as follows
Second-Order Smoothness Prior
By applying second-order smoothness priors, the final MRF energy model is
Second-Order Smoothness Prior
where F H is defined on a set of collinear three nodes 2 on a cubic grid.
Data Cost Computation
The unary term θ s (x s ) of (4) which measures the cost when a node s has a label x s is defined as θs(xs) f (sx, sy, sz, sx + dx(xs), sy + dy(xs), sz + dz(zs)) .
Data Cost Computation
This cost is calculated by the dissimilarity measure f using two volume patches centered on (s x , s y , s z ) in a source volume and (s x +d x (x s ), s y +d y (x s ), s z +d z (z s )) in a target volume, respectively. As this representation is flexible, we can incorporate various dissimilarity measures to f . In this paper, we use the normalized cross correlation (NCC) for uni-modal registrations and the normalized mutual information (NMI) for multi-modal registrations. For computing NCC, we used cubic B-spline weighting scheme used in [3] with patch width 4. For NMI, we compute local NMI [9] for each nodes with patch width 8.
OPTIMIZATION STRATEGY
Optimizing the proposed energy model (4) directly is timeconsuming when a large search space L should be applied to cover large displacements. To reduce computational burden, we apply a decomposed scheme with a coarse-to-fine scheme.
OPTIMIZATION STRATEGY
1 When a factor a connects nodes s, t and u, we use (s, t, u) ∈ F H to represent a ∈ F H when we do not need to use factor representations explicitly. 2 For example, collinear nodes in x axis are placed on (x − 1, y, z), (x, y, z), and (x + 1, y, z).
Decomposed Scheme
Based on the scheme introduced in [ 
Decomposed Scheme
where i ∈ {x, y, z}. In the graph G Then, the MRF energy on G D is defined as follows
Decomposed Scheme
where
The unary term (5) is changed to ternary term (7) and its set is included in F D
H . The energy model applying decomposed scheme consists of ternary potentials only.
Coarse-to-Fine Scheme
To cover large displacements efficiently, we compute multilevel displacement in a coarse-to-fine manner [9] . For a pyramidal dense descriptor representation, input volumes of finer level are smoothed and down-sampled for generating volumes of the coarser level. The displacements are computed on each level with propagated displacement offset which is scaled from the coarser levels. To achieve sub-pixel accuracy, we perform the sub-pixel refinement on the finest level.
Discrete Optimization Method
To optimize the proposed energy model (4) or (8), tree reweighted message passing (TRW) [11, 1] is applied. The TRW message passing provides the lower bound guaranteed not to decrease. A recent comparative study shows the TRW gives the state-of-the-art performances among the various discrete optimization methods [12] . As the TRW theory is built on the pairwise MRF, we need to convert factor graphs representations to pairwise interactions. The detailed conversion procedure is referred to [6] . As the proposed energy model uses higher-order smoothness priors, converting to the hierarchical gradient node graph [13] is possible. Although optimization strategy we introduced decrease computational burden significantly, running TRW or BP on 3D volumes still require high computational power. However, as BP variant optimization algorithms have highly parallel structures, we implement TRW message passing algorithms for 3D registrations on GPU using NVIDIA CUDA. Using GPU, the time required for 1 cycle of whole message passing in a volume takes few seconds. The total time for registration of the proposed method takes about 20 ∼ 40 minutes in the experiments.
EXPERIMENTS
In this section, we show registration results using uni-and multi-modal brain MRI data. The results are compared to those of a method using the first-order MRF energy model [3] . In experiments, λ st = 6, T st = 20, λ stu = 6 and T stu = 20 are used. For label widths, we use
EXPERIMENTS
th level (n = 1 for the finest level) and d i ∈ {−1.0, −0.75, . . . , 0.75, 1.0} for the sub-pixel refinement where i ∈ {x, y, z}. We use 4 levels for coarse-to-fine schemes and 2mm voxel spacing for finest level. All parameters are empirically chosen.
Registration Using Synthetically Deformed Data
We generate synthetically deformed data sets from 10 aligned T1 and T2 weighted brain MRI pairs. The deformed volume is generated by TPS [8] warping with control points (placed on grid with 30mm spacing) perturbed with random variation [−6mm, 6mm] in each axis. More detailed procedure for generating synthetic images are described in [14] . The registration is performed between T1 and warped T1 volumes (uni-modal) and T1 and warped T2 volumes (multi-modal), respectively. As intensity characteristics between T1 and T2 images are not consistent, registrations between T1 and T2 are more challenging problem. In Table 1 , we show averaged root mean square (RMSE), mean (MEAN) and standard deviation (STD) for the magnitude of differences (mm) between the ground truth and the recovered displacement fields. One can see the performances of the proposed method are better than the first order model. In Fig. 1 , we show registration results for a selected case. In the figure, the proposed method produces smoother displacements with higher accuracy than the other method. The recovered displacements using First-Order [3] and Proposed shown in (g) and (h), respectively. In (f-h), left and right figure correspond to ρ-θ and ρ-φ parts of the displacements.
Registration Using Inter-Subject Data
For inter-subject registrations, we use IBSR V2.0 data set [15] which consists 18 T1 weighted brain MRI volumes with manual segmentations. The volumes are scaled to have 1mm voxel spacing in each axis. We select first data as a template and remaining data sets are registered to the template. The recovered displacement fields are used to deform the corresponding segmentations, and then deformed segmentations are compared to the manual ones. We show DICE score (DICE), the sensitivity (SENS) and the specificity (SPEC) for gray matters, white matters and ventricle in Table 2 . For limited spaces, only two selected cases are shown. One can see the proposed method have better scores in terms of DICE, SENS and SPEC measures. In Fig. 2 , we show Case 2 results. In the figure, the proposed method produces smoother displacements and better overlapping regions than the other method. The proposed method especially works better in central regions on brain than the other method.
CONCLUSION
In this paper, we proposed a nonrigid registration method using the MRF model with second-order smoothness priors. The second-order prior enables us to generate smoother displacement fields with better accuracy. In experiments, we showed the proposed method outperformed a MRF energy model with first-order smoothness priors on uni-and multimodal brain MRI registrations using synthetically deformed data and inter-subject brain MRI data.

{'paper_id': '13425187', 'title': 'Nonrigid volume registration using second-order MRF model', 's2_url': 'https://api.semanticscholar.org/CorpusID:13425187', 'source': 'S2ORC'}