Transform image processing methods are methods that work in domains of image transforms, such as Discrete Fourier, Discrete Cosine, Wavelet, and alike. They proved to be very efficient in image compression, in image restoration, in image resampling, and in geometrical transformations and can be traced back to early 1970s. The paper reviews these methods, with emphasis on their comparison and relationships, from the very first steps of transform image compression methods to adaptive and local adaptive filters for image restoration and up to “compressive sensing” methods that gained popularity in last few years. References are made to both first publications of the corresponding results and more recent and more easily available ones. The review has a tutorial character and purpose. 1. Introduction: Why Transforms? Which Transforms? It will not be an exaggeration to assert that digital image processing came into being with introduction, in 1965 by Cooley and Tukey, of the Fast Fourier Transform algorithm (FFT, [1]) for computing the Discrete Fourier Transform (DFT). This publication immediately resulted in impetuous growth of activity in all branches of digital signal and image processing and their applications. The second wave in this process was inspired by the introduction into communication engineering and digital image processing, in the 1970s, of Walsh-Hadamard transform and Haar transform [2] and the development of a large family of fast transforms with FFT-type algorithms [3–5]. Whereas Walsh-Hadamard and Haar transforms have already been known in mathematics, other transforms, for instance, quite popular at the time Slant Transform [6], were being invented “from scratch.” This development was mainly driven by the needs of data compression, though the usefulness of transform domain processing for image restoration and enhancement was also recognized very soon [3]. This period ended up with the introduction of the Discrete Cosine Transform (DCT, [7, 8]), which was soon widely recognized as the best choice among all available at the time transforms and resulted in JPEG and MPEG standards for image, audio, and video compression. The third large wave of activities in transforms for signal and image processing was caused by the introduction, in the 1980s, of a family of transforms that was coined the name “wavelet transform” [9]. The main motivation was achieving a better local representation of signals and images in contrast to the “global” representation that is characteristic to Discrete Fourier, DCT, Walsh-Hadamard, and other fast transforms
References
[1]
J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Mathematics of Computation, vol. 19, no. 90, pp. 297–301, 1965.
[2]
H. F. Harmuth, Transmission of Information by Orthogonal Functions, Springer, Berlin, Germany, 1970.
[3]
H. C. Andrews, Computer Techniques in Image Processing, Academic Press, New York, NY, USA, 1970.
[4]
H. C. Andrews, “Two-dimensional Transforms,” in Picture Processing and Digital Filtering, T. S. Huang, Ed., Springer, New, York, NY, USA, 1975.
[5]
N. Ahmed and K. R. Rao, Orthogonal Transforms for Digital Signal Processing, Springer, Berlin, Germany, 1975.
[6]
W. K. Pratt, W.-H. Chen, and L. R. Welch, “Slant Transform Image Coding,” IEEE Transactions on Communications, vol. 22, no. 8, pp. 1075–1093, 1974.
[7]
N. Ahmed, N. Natarajan, and K. R. Rao, “Discrete cosine transform,” IEEE Transactions on Computers, vol. 23, no. 1, pp. 90–93, 1974.
[8]
K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms, Advantages, Applications, Academic Press, Boston, Mass, USA, 1990.
[9]
I. Daubechies, “Where do wavelets come from? A personal point of view,” Proceedings of the IEEE, vol. 84, no. 4, pp. 510–513, 1996.
[10]
S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, Boston, Mass, USA, 3rd edition, 2008.
[11]
H. Karhunen, über lineare Methoden in der Wahrscheinlichkeitsrechnung, Series A.I, Annales Academi？~Scientiarum Fennic？, 1947.
[12]
M. Loeve, “Fonctions aleatoires de seconde ordre,” in Processes Stochastiques et Movement Brownien, P. Levy, Ed., Hermann, Paris, France, 1948.
[13]
H. Hotelling, “Analysis of a complex of statistical variables into principal components,” Journal of Educational Psychology, vol. 24, no. 6, pp. 417–441, 1933.
[14]
T. P. Belokova, M. A. Kronrod, P. A. Chochia, and L. P. Yaroslavakii, “Digital processing of martian surface photographs from mars 4 and mars 5,” Space Research, vol. 13, no. 6, pp. 898–906, 1975.
[15]
L. P. Yaroslavsky, Digital Picture Processing: An Introduction, Springer, Berlin, Germany, 1985.
[16]
L. Yaroslavsky, Digital Signal Processing in Optics and Holography, Radio i Svyaz', Moscow, Russia, 1987 (Russian).
[17]
L. Yaroslavsky, Digital Holography and Digital Image Processing. Principles, Methods, Algorithms, Kluwer Academic Publishers, Boston, Mass, USA, 2004.
[18]
L. Yaroslavsky, Theoretical Foundations of Digital Imaging Using Matlab, Taylor & Francis, Boca Raton, Fla, USA, 2013.
[19]
L. Yaroslavsky, “Introduction to Digital Holography,” in Digital Signal Processing in Experimental Research, L. Yaroslavsky and J. Astola, Eds., vol. 1 of Bentham Series of e-books, Bentham, 2009, http://www.benthamscience.com/ebooks/9781608050796/index.htm.
[20]
L. P. Yaroslavskii and N. S. Merzlyakov, Methods of Digital Holography, Consultance Bureau, New York, NY, USA, 1980.
[21]
L. P. Jaroslavski, “Comments on FFT algorithm for both input and output pruning,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 29, no. 3, pp. 448–449, 1981.
[22]
J. Markel, “FFT pruning,” IEEE Trans Audio Electroacoust, vol. 19, no. 4, pp. 305–311, 1971.
[23]
H. V. Sorensen and C. S. Burrus, “Efficient computation of the DFT with only a subset of input or output points,” IEEE Transactions on Signal Processing, vol. 41, no. 3, pp. 1184–1200, 1993.
[24]
R. G. Alves, P. L. Osorio, and M. N. S. Swamy, “General FFT pruning algorithm,” in Proceedings of the 43rd IEEE Midwest Symposium on Circuits and Systems, vol. 3, pp. 1192–1195, August 2000.
[25]
L. Yaroslavsky, “Fast discrete sinc-interpolation: a gold standard for image resampling,” in Advances in Signal transforms: Theory and Applications, J. Astola and L. Yaroslavsky, Eds., vol. 7 of Eurasip Book Series on Signal Processing and Communications, pp. 337–405, 2007.
[26]
L. Yaroslavky, “Fast transforms in digital signal processing: theory, algorithms, applications,” in Digital Signal Processing in Experimental Research, L. Yaroslavsky and J. Astola, Eds., vol. 2 of Bentham E-book Series, 2011, http://www.benthamscience.com/ebooks/9781608052301/index.htm.
[27]
R. Yu. Vitkus and L. P. Yaroslavsky, “Recursive Algorithms for Local Adaptive Linear Filtration,” in Mathematical Research. Computer Analysis of Images and Patterns, L. P. Yaroslavsky, A. Rosenfeld, and W. Wilhelmi, Eds., pp. 34–39, Academie Verlag, Berlin, Germany, 1987, Band 40.
[28]
J. Xi and J. F. Chicharo, “Computing running DCT's and DST's based on their second-order shift properties,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 47, no. 5, pp. 779–783, 2000.
[29]
E. Candès, “Compressive sampling,” in Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006.
[30]
D. L. Donoho, “Compressed sensing,” IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006.
[31]
E. J. Candès, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Communications on Pure and Applied Mathematics, vol. 59, no. 8, pp. 1207–1223, 2006.
[32]
E. J. Candes and M. B. Wakin, “An introduction to compressive sampling: A sensing/sampling paradigm that goes against the common knowledge in data acquisition,” IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 21–30, 2008.
[33]
R. G. Baraniuk, “Compressive sensing,” IEEE Signal Processing Magazine, vol. 24, no. 4, pp. 118–124, 2007.
[34]
M. Elad, Spatse and Redundant Representations: From Theory to Applications in Signal and Image Processing, Springer, New York, NY, USA, 2010.
[35]
R. M. Willet, R. F. Mareia, and J. M. Nichols, “Compressed sensing for practical optical imaging systems: a tutorial,” Optical Engineering, vol. 50, no. 7, Article ID 072601, 2011.
[36]
“Compressive optical imaging: architectures and algorithms,” in Optical and Digital Image Processing. Fundamentals and Applications, G. Cristobal, P. Schelkens, and H. Thienpont, Eds., Wiley-VCH, New York, NY, USA, 2011.
[37]
J. M. Whittaker, Interpolatory Function Theory, Cambridge University Press, Cambridge, UK, 1935.
[38]
V. A. Kotelnikov, “on the carrying capacity of the ether and wire in telecommunications,” Material for the First All-Union Conference on Questions of Communication, Izd. Red. Upr. Svyazi RKKA, Moscow, Russia, 1933 (Russian).
[39]
C. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 623–656, 1948.
[40]
T. S. Huang and O. J. Tretiak, Picture Bandwidth Compression, Gordon and Breach, New York, NY, USA, 1972.
[41]
A. Habibi and P. Wintz, “Image coding by linear transformation and block quantization,” IEEE Transactions on Communications, vol. 19, no. 1, pp. 50–62, 1971.
[42]
T. A. Wintz, “Transform picture coding,” Proceedings of the IEEE, vol. 60, no. 7, pp. 809–823, 1972.
[43]
W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard, Springer, Berlin, Germany, 3rd edition, 1993.
[44]
I. E. G. Richardson, H.264 and MPEG-4 Video Compression, John Wiley & Sons, Chichester, UK, 2003.
[45]
T. Wiegand, G. J. Sullivan, G. Bj？ntegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560–576, 2003.
[46]
P. Schelkens, A. Skodras, and T. Ebrahimi, The JPEG, 2000 Suite, John Wiley & Sons, Chichester, UK, 2009.
[47]
I. Pitas, Digital Video and Television, Ioannis Pitas, 2013.
[48]
D. Vaisey and A. Gersho, “Variable block-size image coding, acoustics, speech, and signal processing,” in Proceedings of the IEEE International Conference on (ICASSP '87), vol. 12, pp. 1051–1054, 1987.
[49]
W. K. Pratt, “Generalized wiener filtering computation techniques,” IEEE Transactions on Computers, vol. 21, pp. 636–641, 1972.
[50]
H. C. Andrwes, “Digital computers and image processing,” Endeavour, vol. 31, no. 113, 1972.
[51]
N. Wiener, The Interpolation, Extrapolation and Smoothing of Stationary Time Series, Wiley, New York, NY, USA, 1949.
[52]
A. N. Kolmogorov, “Sur l'interpolation et extrapolation des suites stationnaires,” Comptes Rendus de l'Académie des Sciences, vol. 208, pp. 2043–2045, 1939.
[53]
D. L. Donoho and J. M. Johnstone, “Ideal spatial adaptation by wavelet shrinkage,” Biometrika, vol. 81, no. 3, pp. 425–455, 1994.
[54]
D. L. Donoho, “De-noising by soft-thresholding,” IEEE Transactions on Information Theory, vol. 41, no. 3, pp. 613–627, 1995.
[55]
L. Yaroslavsky, “Space variant and adaptive transform domain image and video restoration methods,” in Advances in Signal Transforms: Theory and Applications, J. Astola and L. Yaroslavsky, Eds., EURASIP Book Series on Signal Processing and Communications, 2007.
[56]
L. Yaroslavsky, “Local criteria: a unified approach to local adaptive linear and rank filterson,” in Signal Recovery and Synthesis III, Technical Digest Series 15, 1989.
[57]
M. D. Levine, Vision in Man and Machine, McGraw-Hill, New York, NY, USA, 1985.
[58]
H. S. Malvar and D. H. Staelin, “LOT: transform coding without blocking effects,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. v, pp. 553–559, 1992.
[59]
R. ？ktem, L. Yaroslavsky, K. Egiazarian, and J. Astola, “Transform domain approaches for image denoising,” Journal of Electronic Imaging, vol. 11, no. 2, pp. 149–156, 2002.
[60]
L. P. Yaroslavsky, B. Fishbain, A. Shteinman, and S. Gepshtein, “Processing and fusion of thermal and video sequences for terrestrial long range observation systems,” in Proceedings of the 7th International Conference on Information Fusion (FUSION '04), pp. 848–855, Stockholm, Sweden, July 2004.
[61]
A. Buades, B. Coll, and J. M. Morel, “A review of image denoising algorithms, with a new one,” Multiscale Modeling and Simulation, vol. 4, no. 2, pp. 490–530, 2005.
[62]
A. Buades, B. Coll, and J.-M. Morel, “A non-local algorithm for image denoising,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '05), pp. 60–65, June 2005.
[63]
J. M. Morel and A. Buades Capo, Non Local Image Processing, http://www.farman.ens-cachan.fr/6_JeanMichel_Morel.pdf.
[64]
S. E. Hecht and J. J. Vidal, “generation of ECG prototype waveforms by piecewise correlational averaging,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, no. 5, pp. 415–420, 1980.
[65]
K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, “Image denoising by sparse 3-D transform-domain collaborative filtering,” IEEE Transactions on Image Processing, vol. 16, no. 8, pp. 2080–2095, 2007.
[66]
L. Yaroslavsky and M. Eden, “Correlational accumulation as a method for signal restoration,” Signal Processing, vol. 39, no. 1-2, pp. 89–106, 1994.
[67]
V. Katkovnik, K. Egiazarian, and J. Astola, “Adaptive varying window methods in signal and image processing,” in Advances in Signal Transforms. Theory and Applications, J. Astola and L. Yaroslavsky, Eds., vol. 7 of Eurasip Book Series on Signal Processing and Communications, pp. 241–284, 2007.
[68]
D. Gabor, “Theory of Communication,” Journal of IEEE, vol. 93, pp. 429–457, 1946.
[69]
E. Wigner, “On the quantum correction for thermodynamic equilibrium,” Physical Review, vol. 40, no. 5, pp. 749–759, 1932.
[70]
R. K. Potter, G. Koppand, and H. C. Green, Visible Speech, Van Nostrand, New York, NY, USA, 1947.
[71]
D. L. Donoho, “Nonlinear wavelet methods for recovery of signals, densities, and spectra from indirect and noisy data,” Proceedings of Symposia in Applied Mathematics, American Mathematical Society, vol. 47, pp. 173–205, 1993.
[72]
R. R. Coifman and D. L. Donoho, “Translation- Invariant De-Noising,” in Wavelets and Statistics, A. Antoniadis, Ed., vol. 103 of Lecture Notes in Statistics, pp. 125–150, Springer, Berlin, Germany, 1995.
B. Z. Shaick, L. Ridel, and L. Yaroslavsky, “A hybrid transform method for image denoising,” in Proceedings of the 10th European Signal Processing Conference (EUSIPCO '00), M. Gabbouj and P. Kuosmanen, Eds., Tampere, Finland, September 2000.
[75]
M. Vetterli and J. Kovacevic, Wavelets and Sub-Band Coding, Prentice Hall, Englewood Cliffs, NJ, USA, 1995.
[76]
J. Backus, The Acoustical Foundations of Music, Norton and Co., New York, NY, USA, 1969.
[77]
M. Unser, A. Aldroubi, and M. Eden, “Polynomial spline signal approximations: Filter design and asymptotic equivalence with Shannon's sampling theorem,” IEEE Transactions on Information Theory, vol. 38, no. 1, pp. 95–103, 1992.
[78]
A. Gotchev, “Image interpolation by optimized spline-based kernels,” in Advances in Signal transforms: Theory and Applications, J. Astola and L. Yaroslavsky, Eds., vol. 7 of Eurasip Book Series on Signal Processing and Communications, pp. 285–335, 2007.
[79]
L. P. Yaroslavsky, “Efficient algorithm for discrete sine interpolation,” Applied Optics, vol. 36, no. 2, pp. 460–463, 1997.
[80]
L. P. Yaroslavsky, “Shifted discrete fourier transforms,” in Digital Signal Processing, V. Cappellini and A. G. Constantinides, Eds., pp. 69–74, Avademic Press, London, UK, 1980.
[81]
L. Yaroslavsky, “Boundary effect free and adaptive discrete signal sinc-interpolation algorithms for signal and image resampling,” Applied Optics, vol. 42, no. 20, pp. 4166–4175, 2003.
[82]
L. Bilevich and L. Yaroslavsky, “Fast DCT-based image convolution algorithms and application to image resampling and hologram reconstruction,” in Real-Time Image and Video Processing, Proceedings of SPIE, Brussels, Belgium, April 2010.
[83]
L. Bilevich and L. Yaroslavsky, “Fast DCT-based algorithm for signal and image accurate scaling,” in Image Processing: Algorithms and Systems XI, vol. 8655 of Proceedings of SPIE, February 2013.
[84]
L. P. Yaroslavsky, “Linking analog and digital image processing,” in Optical and Digital Image Processing. Fundamentals and Applications, G. Cristobal, P. Schelkens, and H. Thienpont, Eds., pp. 397–418, Wiley-VCH, New York, NY, USA, 2011.
[85]
M. Unser, P. Thevenaz, and L. Yaroslavsky, “Convolution-based interpolation for fast, high-quality rotation of images,” IEEE Transactions on Image Processing, vol. 4, no. 10, pp. 1371–1381, 1995.
[86]
P. Thévenaz, EPFL/STI/IOA/LIB, Bldg. +BM-Ecublens 4.137, Station 17, CH-1015 Lausanne VD, Switzerland, http://bigwww.epfl.ch/thevenaz/.
[87]
A. Gotchev, “Spline and wavelet based techniques for signal and image processing,” Tampere University of Technology, Publication 429, Tampere, Finland, TTY-Paino 2003.
L. Yaroslavsky, B. Fishbain, G. Shabat, and I. Ideses, “Superresolution in turbulent videos: making profit from damage,” Optics Letters, vol. 32, no. 21, pp. 3038–3040, 2007.
[90]
B. Fishbain, I. A. Ideses, G. Shabat, B. G. Salomon, and L. P. Yaroslavsky, “Superresolution in color videos acquired through turbulent media,” Optics Letters, vol. 34, no. 5, pp. 587–589, 2009.
[91]
B. Fishbain, L. P. Yaroslavsky, and I. A. Ideses, “Real-time stabilization of long range observation system turbulent video,” Journal of Real-Time Image Processing, vol. 2, no. 1, pp. 11–22, 2007.
[92]
W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes. the Art of Scientific Computing, Cambridge University Press, Cambridge, UK, 1987.
[93]
J. H. Mathew and K. D. Fink, Numerical Methods Using MATLAB, Prentice-Hall, Englewood Cliffs, NJ, USA, 1999.
[94]
L. P. Yaroslavsky, A. Moreno, and J. Campos, “Frequency responses and resolving power of numerical integration of sampled data,” Optics Express, vol. 13, no. 8, pp. 2892–2905, 2005.
[95]
C. F. Gauss, “Nachclass: theoria interpolationis methodo nova tractata,” IEEE ASSP Magazine, vol. 1, no. 4, pp. 14–81, 1984.
[96]
L. F. Yaroslavsky, G. Shabat, B. G. Salomon, I. A. Ideses, and B. Fishbain, “Nonuniform sampling, image recovery from sparse data and the discrete sampling theorem,” Journal of the Optical Society of America, vol. 26, no. 3, pp. 566–575, 2009.
[97]
L. P. Yaroslavsky, “Image recovery from sparse samples, discrete sampling theorem, and sharply bounded band-limited discrete signals,” in Advances in Imaging and Electron Physics, P. Hawkes, Ed., vol. 167, chapter 5, pp. 295–331, Academic Press, 2011.
[98]
R. W. Gerchberg and W. O. Saxton, “Practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik, vol. 35, no. 2, pp. 237–250, 1972.
[99]
A. Papoulis, “New algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans Circuits Syst, vol. 22, no. 9, pp. 735–742, 1975.
[100]
D. Gabor, “Theory of communication,” Journal of IEEE, vol. 93, pp. 429–457, 1946.
