This paper presents a new method for lossy compression of temporal data of both naturally recorded and synthetically created videos by Catmull-Rom spline and quadratic Bezier curve fitting. The proposed method approximates the luminance or color variations in a sequence of frames by spline fitting in Euclidean space. Precise control of accuracy at pixel level is achieved by specified tolerance of error. A break and fit criterion is employed to minimize the number of curve segments required to fit the data. Experimental results show that the described method yields very good results, both in terms of objective and subjective quality measurement, i.e., bit-rate/PSNR and human visual acceptance, without causing any blocking artifacts.