Image registration has been well studied problem in medical image analysis community, with rigid registration taking much of the spotlight. In addition to rigid registration, non-rigid registration is of great interest due to it's applications in inter-patient modality registration where deformations of organs are highly pronounced. However non-rigid registration is an ill-posed problem with numerous degrees of freedom, which makes finding the best transformation from source to final image very difficult. To counter this, some methods were proposed which constraint the non-rigid transformation $T$ to be within certain bounds, which is not always ideal. 

To this end, Tang et al. propose a novel framework which encapsulates the problem of non-rigid image registration into a graph-cut framework, which guarantees a global maxima (or minima) under certain conditions. The formulation requires that each pixel in source image has a displacement label (whcih is a vector) indicating its corresponding position in the floating image, according to an objective function. A smoothness constraint is also added to ensure that the values of the transformation function $T$ are meaningful and stay within natural limits (no large displacement should occur between absolute neighbouring pixels). The authors propose the following formulation as their objective function, which they then solve using graph-cuts methods:

$D^* = argmin_{D} \sum_{x\in X}||I(x) - J(x + D(x))|| + \lambda \sum_{(x,y)\in \mathcal{N}}||D(x) - D(y)||$

The equation above is not fully discretized, in the sense that $D$ is still unbounded and can vary from $[-\infty, \infty]$. To allow for optimization using graph-cuts, the transformation function $D$ is mapped to a finite set $\mathcal{W} = \{0, \pm s, \pm 2s...\pm ws\}^d$. Using this discretization, the equation above can be solved using graph-cuts via a sequence of alpha-expansion. $\alpha$-expansion is a two label problem where the cost of assigning a label $\alpha$ is calculated on the basis of the previous label of the pixel. Different costs are assigned to different scenarios where the previous label may keep it's original label, or change to new label $\alpha$. This is important since it is imperative that the cost conditions satisifes the inequality given by Kolmogorov \& Zabih which then guarantees a global optima. 

The method was tested on on MR data from BrainWeb dataset which were affinely pre-registered and intensity normalized to be within 0 and 255. The method demonstrated good qualitative results when compared two state-of-art methods DEMONS and FFD, where the average intensity differences for the proposed method was much lower than the competition, while the tissue overlap was higher.