Fractal encoding technique possesses some particular properties which make it as an attractive approach to video sequences compression. In this paper, we propose a novel fractal-based encoding method for video signals, which, based on Self-Transformation Systems( STS), is combined with Motion Compensation as well as nonlinear transformation. Experiment of results of realtime image sequences show that the proposed method can achieve a very fast encoding speed and acceptable tradeoff between compression ration and decoding quality.