A fast stereo video coding algorithm based on fractal video coding was presented in this paper. Firstly, the conventional Circular Prediction Mapping/Non-contractive Interframe Mapping(CPM/NCIM) method was improved,in which frame I of the video sequences was coded based on Discrete Cosine Transform(DCT) and the others were partitioned into subblocks by a tree structured partition method . In the stereo video encoding, the left channel was a base layer and the right channel was a enhanced layer. The left channel was encoded by using the Motion Compensation Prediction(MCP) method,and the right channel was encoded by using both MCP and Disparity Compensation Prediction(DCP) methods. In the encoding of DCP, the polarization property and the epipolar line property in the parallel stereo encoding structure was used of to simplify the DCP search method. Therefore, a fast DCP encoding method was presented. The experiment results indicate that the computational complexity by the proposed method has reduced to 0.028-0.029 times comparing to that of the full search method while the reconstructed image quality is as good as that in the full search,which makes the stereo video encoding method more useful.