In computer vision, video stitching is a very interesting problem. In this paper, we proposed an efficient and effective novel video stitching method based on fast structure deformation that is capable of simultaneously achieving quality stitching and computational efficiency. In our method, firstly, a two-stage seam searching algorithm is designed to search two distinct but structurally corresponding seams in the two original images. The seam location of the previous frame is further considered to preserve the inter-frame consistency. Real-time seam update is performed to reduce the deformation effect caused by moving objects. Secondly, along the double seams, 1-D feature detection and matching is performed to capture the structural relationship between the two adjacent views. Thirdly, after feature matching, we propose an efficient algorithm to linearly propagate the deformation vectors to eliminate structure misalignment. At last, image intensity misalignment is corrected by rapid gradient fusion based on the successive over slackening iteration (SOSI) solver. A principled solution to the initialization of the SOSI significantly reduced the number of iterations required. Compared to image stitching, video stitching faces several new challenges including temporal coherence, dominate foreground objects moving across views and camera jittering. Experimental results show that our method to perform the existing ones compared in terms of overall stitching quality and computational efficiency. A novel searching algorithm based on enhanced dynamic programing is presented, which can obtain satisfactory result and achieve better real-time performance.