This paper proposes a keyframe-based video object editing scheme for automatic object shape deformation. Except for object segmentation, several technologies are developed in the proposed scheme to minimize user interactions as well as to facilitate users’ flexible and precise control on deformation. First, an automatic modeling technique is presented to establish the graph model for the segmented object, which can accurately represent 2D shape information. Second, when the user specifies the deformation of a video object in keyframes by dragging handles on it to new positions, an algorithm is proposed to automatically generate motion trajectories of the object handles along with frames. Finally, the 2D shape deformation is completed by our proposed non-linear energy minimization algorithm. Furthermore, in order to handle the abrupt change of positions, dimensionality reduction is applied together with the minimization algorithm. Experimental results fully demonstrate that the proposed scheme can generate natural video shape deformations with few user interactions.