Multidimensional Rational Approximations with an Application to Image Compression

I present two methods for the calculation of simultaneous rational approximations with specific characteristics related to computation. The methods are intended for computationally efficient calculation of linear transforms for image compression; e.g., the Discrete Cosine Transform (DCT) or certain wavelet transforms. The rational approximations must have controlled precision (i.e., bits required for representation), and the numerators must use a minimum number of powers of two over the coefficient vector (i.e., the representation must have minimum "length"), to facilitate efficient multiplierless implementation. The first method uses successive approximation of the coefficients in a suboptimal algorithm with low computational complexity to achieve low-length representations. The convergence of this method is analyzed, along with the closeness of the approximations. The suitability of this method for computational implementation, along with the quality of its representations, are evaluated in the context of Jacobi-Perron and Furtwangler type algorithms, which are shown to have shortcomings for this application. While the method is shown to provide low-length representations, it is not guaranteed to produce the lowest-length representation. However, the method is shown to be suitable for real-time computation environments. The second method, which finds the lowest-length representation, requires significantly more computation, but is suitable for offline computation of representations. This method employs search tree pruning and, at each branch in the search tree, provides a lower bound for the representation length.