This paper focuses on the design of fast algorithms for rotating images and preserving high quality. The basis for the approach is a decomposition of a rotation into a sequence of one-dimensional translations. As the accuracy of these operations is critical, we introduce a general theoretical framework that addresses their design and performance. We also investigate the issue of optimality and present an improved least-square formulation of the problem. This approach leads to a separable three-pass implementation of a rotation using one-dimensional convolutions only. We provide explicit filter formulas for several continuous signal models including spline and bandlimited representations. Finally, we present rotation experiments and compare the currently standard techniques with the various versions of our algorithm. Our results indicate that the present algorithm in its higher-order versions outperforms all standard high-accuracy methods of which we are aware, both in terms of speed and quality. Its computational complexity increases linearly with the order of accuracy. The best-quality results are obtained with the sine-based algorithm, which can be implemented using simple one-dimensional FFTs.

A class of criteria of image processing quality, the local criteria, is introduced. The criteria are based on a generalized notion of pixel's neighborhood and separate averaging the criteria loss function over the neighborhood and random factors associated with image formation and intended utilization of the image. This offers a new and unified approach to treatment and design of local adaptive linear and non-linear rank filters for image restoration and enhancement. The corresponding examples are briefly outlined.>

We demonstrate the use of informational redundancy of signals and transforms for reducing the computational costs of signal processing. Four concrete examples of accelerated signal processing algorithms are presented to support the idea of purposive use of signal and transform redundancy for saving the computational costs. These are: an accelerated algorithm for Fourier spectral analysis, an accelerated algorithm for computing the signal local histograms, the quantized discrete Fourier transforms, and recursive implementation of arbitrary digital filters. The former two reduce computation time by exploiting signal redundancy. The latter two save processing time at the expense of the accuracy of representation of the corresponding signal transforms.