06-11-2012, 03:35 PM
Image Transforms
1Image Transforms.pdf (Size: 322.09 KB / Downloads: 80)
Separability gives rise to processing
advantages in the computer. The transform
may be performed as a single dimensional
computation on the rows and columns.
• The Fourier matrix can be factored into the
product of 2 log N sparse and diagonal
log2 matrices (observed by Good in 1958). This is
the basis for the Fast Fourier Transform.
Fast Fourier Transform
To approximate a function by samples, and to
approximate the Fourier integral by the discrete Fourier
transform, requires applying a matrix whose order is the
number sample points n.
Since multiplying an n x n matrix by a vector costs on the
order of n2 arithmetic operations, the problem gets quickly
worse as the number of sample points increases.
However, if the samples are uniformly spaced, then the
Fourier matrix can be factored into a product of just a few
sparse matrices, and the resulting factors can be applied
to a vector in a total of order n log n arithmetic operations.
This is the so-called fast Fourier transform or FFT.
• The Walsh transform uses square‐waves as
it's basis functions, and these vary from ‐1
to +1.
• We talk of sequency instead of frequency
when discussing the Walsh.
• The advantage of the Walsh transform is
that it does not require floating‐point math
or transcendental functions.
• The inverse Walsh kernel is identical to the
forward kernel.