Abstract: The computation complexity of the video coders based on matching pursuit is much higher,because of laboriously searching optimal atoms in a redundant dictionary.This paper proposes a video coding algorithm based on discreted Gabor dictionary,which incorporates an improved searching scheme using optimal timefrequency atoms,thus reduces the computation complexity of the original algorithm greatly.Experiment results show the algorithm can keep original coding efficiency and reduce the computation complexity efficiently.