Matching pursuits over a basis of separable Gabor functions has been demons
trated to outperform DCT methods for displaced frame difference coding for
video compression, Unfortunately, apart from very low bit-rate applications
, the algorithm involves an extremely high computational load. This paper c
ontains original contribution to the issues of dictionary selection and fas
t implementation for matching pursuits video coding. First, it is shown tha
t the PSNR performance of existing matching pursuits codecs can be improved
and the implementation cost reduced by a better selection of dictionary fu
nctions. Secondly, dictionary factorization is put forward to further reduc
e implementation costs. A reduction of the computational load by a factor o
f 20 is achieved compared to implementations reported to date. For a majori
ty of test conditions, this reduction is supplemented by an improvement in
reconstruction quality. Finally, a pruned full-search algorithm is introduc
ed, which offers significant quality gains compared to the better-known heu
ristic fast-search algorithm, while keeping the computational cost low.