Today's video codecs employ motion compensated prediction in combination with block matching techniques. These techniques, although achieving some level of adaptivity in their latest versions, continue to rely on the decomposition of frames on a set of artificial primitives: blocks. This paper presents a new approach to video coding. A geometrically adaptive image decomposition scheme using an over-complete basis is used to represent the scene. Using Matching Pursuit (MP), we are able to express local features such as position, anisotropic scale and orientation in terms of a set of spatio-frequential primitives. In order to perform frame prediction, only the changes in the parameters that determine these functions from frame to frame will have to be coded. Such an approach, in addition to being able to catch displacements in images deals as well in a natural way with local scale deformations and local rotations.