In this paper, we present a new approach to tackle simultaneously linear and deformable registration between two images. Our combined formulation avoids the bias created when linear registration is performed independently before a deformable registration. Our registration problem is formulated as a discrete Markov Random Field and a higher order objective function. Usually, a grid is superimposed on the image domain where the latent variables correspond to the local image displacement vectors. Here, we decouple the linear part and the deformable part of the displacement vectors into two conjugate nodes of the grid. We enforce the smoothness of the deformable displacements vectors with binary potentials while the linearity is imposed through third and fourth order potentials. The resulting formulation is modular with respect to the image metric used to evaluate the correctness of mapping as well as with respect to the nature of the linear transformation (rigid, similarity, affine). Inference on this graph is performed efficiently through Alternating Direction Method of Multipliers. Promising results on medical 3D images demonstrate the potentials of our approach.