A video compression framework based on parametric object and background compression is proposed. At the encoder, an embodiment detects objects and segments frames into regions corresponding to the foreground object and the background. The object and the background are individually encoded using separate parametric coding techniques. While the object is encoded using the projection of coefficients to the orthonormal basis of the learnt subspace (used for appearance based object tracking), the background is characterized using an auto-regressive (AR) process model. An advantage of the proposed schemes is that the decoder structure allows for simultaneous reconstruction of object and background, thus making it amenable to the new multi-thread/multi-processor architectures.