A fast algorithm for the generation of orthogonal base functions on an arbitrarily shaped region

In region-oriented transform coding, an image is divided into several nonrectangular regions. The image intensity in each of these regions is represented as a weighted sum of orthogonal base functions. These base functions depend on the shape of the image region and are obtained by orthogonalizing a nonorthogonal starting base. This can be done by using the Gramm-Schmidt procedure. In that case, if base functions of degree up to N are required, a number of O(N⁴) multiplications and additions must be computed for each pixel in the image region. This paper presents a new orthogonalization algorithm, in which the complexity is reduced from O(N⁴) to O(N³). The algorithm applies in the important cases, where the starting base consists of polynomials or sinewaves