Other Integral Transforms: The Discrete Cosine Transform and The Hartley Transform (Biomedical Image Analysis)

Other integral transforms exist that have properties similar to those of the Fourier transform but are real-valued. Most notably, these are the discrete cosine transform26 and the discrete Hartley transform.4,16 For both of them, a fast recursive formulation similar to the FFT exists.5 Like the Fourier transform, both transforms decompose the image into its frequency components. The discrete cosine transform finds widespread use in lossy image compression (see Section 12.3), and the discrete Hartley transform is sometimes used as a real-valued substitute for the Fourier transform in frequency-domain filter operations. In fact, some image processing programs, such as NIH Image and ImageJ, really compute the discrete Hartley transform, although the menu indicates the Fourier transform. The advantage of the Hartley transform is that it does not require dealing with complex numbers. However, both the discrete cosine transform and the discrete Hartley transform have fundamentally different periodicity and symmetry properties than those of the Fourier transform. Consequently, some theorems, including the convolution theorem, are different from, and notably more complex than, the equivalent theorems of the Fourier transform. In addition, patent restrictions that were held up until 1995 may have hampered a more widespread adoption of the fast Hartley transform.

The two-dimensional discrete cosine transform and its inverse transform are given, respectively, by*


tmp2F-135_thumb

where the scaling factor s(k) assumes the values s(0) = V2 and s(k) = 2 for all other k. Whereas the Fourier transform assumes 2^-periodicity of the input signal, the discrete cosine transform assumes the input data to be only one-half of the 2^ period. The other half is mirrored. Consider the one-dimensional input sequence to be x0, x1, … , xN-1; then the sequence is assumed to continue with x-1 = x0, x-2 = x1,… to the left, and xN = xN-1, xN+1 = xN-2,… to the right. This behavior is identical to a discrete Fourier transform when the input data are real-valued with even symmetry and all even-indexed elements are zero. Furthermore, the discrete cosine transform does not yield negative frequency components as the Fourier transform does. For this reason, the origin with zero frequency cannot be shifted into the center as shown in Figure 3.3. Rather, the M x N data points of the discrete cosine transform represent the positive part of the spectrum only. To achieve a spectrum similar to the one obtained from the Fourier transform, the M x N point spectrum needs to be mirrored along the u-axis, then the new spectrum mirrored again along the v-axis, leading to a 2M x 2N spectrum. This mirroring process generates four zero-frequency points and is therefore rarely performed. However, even the one-quadrant spectrum of positive frequencies provides the ability to design filters based on the discrete cosine transform.

The discrete Hartley transform is more closely related to the Fourier transform than the discrete cosine transform. In fact, Hartley envisioned his integral transform as a real-valued replacement of the Fourier transform for real-valued data.3 Whereas the Fourier transform uses the harmonic complex oscillation as its basis function, the Hartley transform uses the cas function. The term cas is an acronym for cosine and sine, and the cas function is defined as

The one-dimensional discrete Hartley transform is given by

tmp2F-136_thumbtmp2F-137_thumb

The discrete Hartley transform is its own inverse; in other words, the inverse Hartley transform is identical to the forward Hartley transform. In Equation (3.38) the inverse transform is obtained by exchanging I(x,y) and H(u, v) and performing the summation over u and v. The Fourier and Hartley transforms are closely related. The Hartley transform can be computed from the real and imaginary components of the Fourier transform through the equation3

tmp2F-138_thumb

and the Fourier transform can be obtained by splitting the Hartley transform into its even and odd components, which then constitute the real and imaginary parts of the Fourier transform4:

tmp2F-139_thumb

Similar to the Fourier transform, the signal is assumed to be periodic, and its Hartley transform is also periodic in the sense of H(k) = H(k + mN), where N is the length of the data set and m is an integer number. The discrete Hartley transform yields the transform components for negative frequencies in the upper half of the transformed data. For this reason, the shift H(-k) = H(N — k) is usually performed to move the zero-frequency point into the center of the data stream or, in the two-dimensional case, into the center of the image. The magnitude of the Hartley transform IH(u,v)I and the magnitude of the Fourier transform IF(u,v)l are very similar in appearance. Frequency-domain filtering is possible with the Hartley transform, but the convolution theorem differs from that of the Fourier transform. If two signals g1 and g2 are convolved into a signal g, the convolution theorem for the discrete Hartley transform requires that we split one of the transforms into its even and odd components such thattmp2F-140_thumb is the Hartley transform of g1, G1e is the even part of G1 withtmp2F-141_thumb tmp2F-142_thumb, and G1o is the odd part of G1 withtmp2F-143_thumbin analogy to Equation (3.35). With these definitions, the Hartley transform G = H{g} of the convolved signal can be computed through4

tmp2F-144_thumb

When one of the functions (e.g., a Gaussian filter kernel) is even, G2o(w) = 0 follows, and the second summation term in the convolution theorem [Equation (3.36)] can be dropped.

In two dimensions, additional considerations arise, as there are two possible extensions of the one-dimensional discrete Hartley transform34 with mutually exclusive properties. The following equation describes a two-dimensional Hartley transform that maintains the relationship between the Fourier and Hartley transform in Equations (3.34) and (3.35):

tmp2F-145_thumb

The normalization factor M-1N-1 can either be applied in the forward Hartley transform as proposed by Bracewell,4 in the inverse Hartley transform as proposed by Watson and Poirson,34 or in both the forward and inverse transform, as in Equation (3.37) with the advantage that the Hartley transform is still its inverse under this definition. The following equation defines a separable discrete Hartley transform34 that is separable in analogy to the Fourier transform [Equation (3.8)]:

tmp2F-146_thumb

The separable Hartley transform in Equation (3.38) was proposed by Bracewell as the two-dimensional extension of the one-dimensional discrete Hartley transform.3 However, the separable discrete Hartley transform no longer obeys the relationship to the Fourier transform in Equations (3.34) and (3.35). This implies that the convolution theorem, Equation (3.36), is not valid in two dimensions under Equation (3.38). Instead, Watson and Poirson derived the modified convolution theorem34

tmp2F-147_thumb

where the indices e and o indicate the even (cosine) part and the odd (sine) part of the discrete Hartley transform, respectively.

To view and examine a frequency spectrum, the discrete Hartley transform is an attractive alternative to the Fourier transform, since the transform is real-valued and no imaginary component or phase component needs to be considered. For the same reasons, the memory requirement is lower, and the actual transform is faster, since the cas function can be computed with a single trigonometric operation, where two such operations are needed for the complex exponential of the Fourier transform. However, when the Hartley transform is used for image filtering, the complexity of the convolution theorem offsets some of that advantage.

Next post:

Previous post: