The aim of this paper is to achieve seamless image stitching for eliminating obvious visual artifact caused by severe intensity discrepancy, image distortion and structure mis-alignment, given that the input images are globally registered. Our approach is based on structure deformation and propagation while maintaining the overall appearance affinity of the result to the input images. This new approach is proven to be effective in solving the above problems, and has found applications in mosaic deghosting, image blending and intensity correction. Our new method consists of the following main processes. First, salient features or structures are robustly detected and aligned along the optimal partitioning boundary between the input images. From these features, we derive sparse deformation vectors to uniformly encode the underlying structure and intensity misalignment. These sparse deformation cues will then be propagated robustly and smoothly into the interior of the target image by solving the associated Laplace equations in the image gradient domain. We present convincing results to show that our method can handle significant structure and intensity misalignment in image stitching.