Matching outlier structures with missing correspondences and/or local large deformations is very difficult in image registration. In this paper, we define structure matching as an iterative local adaptive kernel regression which locally reconstructs moving image’s dense deformation fields from the discrete displacement fields computed by multi-resolution block matching. First, a new joint saliency map (JSM) is proposed to match a structure-tensor-based local saliency distribution for each overlapping pixel pair and highlight the corresponding saliency structures (called joint saliency structures, JSSs) between the images. To explore the consistency of normal JSSs and their deformations around the outliers, we use JSM to guide the dense deformation reconstruction by emphasizing the JSSs’ discrete displacement vectors in kernel regression. The JSS adaptive kernel regression adapts anisotropic kernel’s shape and orientation to reference image’s structure and weights more contribution from JSS’s displacement vectors for the iterative regression, whereby moving image’s local deformations can be compliant with reference image’s corresponding normal structures. The experimental results demonstrate that the proposed method achieves almost the best performance in structure matching of all challenging image pairs with outlier structures compared with other state-of-the-art intensity-based nonrigid registration algorithms.