Motion estimation is a coding technique to eliminate the temporal redundancy of video. However, state-of-the-art translational motion model is not able to efficiently represent objects' local non-rigid complex motion. To address the issue, an elastic motion estimation algorithm is developed in this paper based on modified Gauss-Newton method. The effect of initial iteration point is first analyzed on the result of the Gauss-Newton method, and a two bit-depth pixel based uniform search is used to predict the initial iteration point. Subsequently, it is found that different step size has obvious influence on the performance of the elastic motion estimation by both theoretical and experimental analyses. The ratio of low-frequency energy of discrete cosine transform is employed to estimate the upper bound of the step size which is then refined by the golden ratio method. Experimental results show that the proposed algorithm is able to obtain stable performance for video sequences with various scene characteristics. It gains 1.73dB and 1.42dB higher average motion-compensated peak signal-to-noise ratio (PSNR) than those of the full search algorithm based on block-wise translational model and conventional elastic motion estimation, respectively. Furthermore, the proposed algorithm has faster convergence speed. Only 1~3 iterations are needed before the proposed algorithm achieves higher PSNR than conventional elastic motion estimation and block-wise translational full search method.