In this paper, we present a new approach to tackle simul- taneously linear and deformable registration between a pair of images. Our combined formulation avoids the bias created when linear registra- tion is performed independently before a deformable registration. Our registration problem is formulated as a discrete Markov Random Field employing a higher order objective function. To cope with both linear and deformable registration, we introduce two graphical models, one for each subproblem. The two graphical models consist of identical node sys- tems. The nodes of the first graph encode the local translations of the global linear registration component, while the nodes of the second graph encode the local translations of the deformable registration component. A higher-order edge system (third and fourth order interactions) that imposes the linearity of the transformation is introduced for the first graph, while a simple pairwise edge system that promotes the smooth- ness of the deformation field is employed for the second graph. The two graphs are coupled by additional edges that connect homologous nodes and encode the data term, while unary potentials are used only for the deformable part and penalize large deformations. The resulting formu- lation 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 per- formed efficiently through Alternating Direction Method of Multipliers. Promising results on medical 3D images demonstrate the potentials of our approach.