There is a growing interest on adapted signal expansions for efficient sparse approximations. For this purpose, signal expansions on over-complete bases are of high interest. Several strategies exist in order to get sparse approximations of a signal as a superposition of functions from a redundant dictionary. One of these strategies is the well known Matching Pursuit (MP). MP is an algorithm where complexity depends on the accuracy of the desired approximation. This is due to its greedy iterative nature. For very large dictionaries, however, complexity depends in great manner on the size of this, i.e. at each iteration the whole dictionary has to be browsed. Sometimes, heuristic procedures need to be adopted due to the overwhelming complexity that this may represent. However, these reduce the search space and, consequently, a poorer signal approximation is retrieved. In this work, we propose a feasible approach for Full Search Matching Pursuit (FSMP) for the particular case of natural image approximations with an-isotropically refined oriented atoms (which have the purpose of exploiting image geometry). Thanks to the structure of the dictionary and its spatio-temporal localisation, several enhancements are possible to speed-up the calculation of the most critical step: the scalar product of the signal with all the functions from the dictionary.