  The purpose of this paper is to introduce a very efficient algorithm for
signal extrapolation. It can widely be used in many applications in image and
video communication, e. g. for concealment of block errors caused by
transmission errors or for prediction in video coding. The signal extrapolation
is performed by extending a signal from a limited number of known samples into
areas beyond these samples. Therefore a finite set of orthogonal basis
functions is used and the known part of the signal is projected onto them.
Since the basis functions are not orthogonal regarding the area of the known
samples, the projection does not lead to the real portion a basis function has
of the signal. The proposed algorithm efficiently copes with this
non-orthogonality resulting in very good objective and visual extrapolation
results for edges, smooth areas, as well as structured areas. Compared to an
existent implementation, this algorithm has a significantly lower computational
complexity without any degradation in quality. The processing time can be
reduced by a factor larger than 100.
