Image Enhancement by Multiplication of 2-D Cosine Transform Coefficients
© Copyright 1983, 1989 by Timothy D. Greer. Since this article has not been published elsewhere, I reserve rights to it that are not explicitly mentioned in the IBM copyright statement below.
Digital images which have been bandwidth compressed using two-dimensional cosine transform coding can be enhanced with a frequency-domain filter by modifying the decompressed cosine transform coefficients before the inverse cosine transformation. Compared to enhancement after the inverse transformation, by convolution for example, modifying the decoded transform coefficients requires much less computation and may also leave fewer artifacts.
Introduction
Degradation of an image by an optical system is corrected by digital processing with what is known as Modulation Transfer Function Correction (MTFC). The Modulation Transfer Function (MTF) of an imaging system indicates the relative energy passed by a system at various frequencies -- the function tells how much modulation is transferred. By multiplying the energy at all frequencies of the output image by the reciprocal of the MTF at corresponding frequencies, the original image is obtained. Noise and zeros in the MTF prevent perfect correction of degradation; nevertheless, enhancement is usually significant. Modification of the technique to over-correct at high frequencies is often used for further subjective improvement in image quality.
One way of applying MTFC to a digital image is to take the two-dimensional Fourier transform (FT) of the image, and then multiply the moduli of the FT coefficients by the correction factors before inverse Fourier transforming. Since a great deal of computation is required for an FT, usually MTFC enhancement is done using convolution. Convolution with the appropriate kernel approximates the effects of the FT -- multiplication -- inverse FT sequence [1], and for small kernels requires considerably less computation.
Much greater reduction in required computation is possible if the system contains certain transformations. In particular, a two-dimensional cosine transform is effectively a Fourier transform of an unfolded (reflected at edges) version of an image [2], so the coefficients can be manipulated to the same effects obtained through modification of FT moduli. An image may undergo two-dimensional cosine transform coding during Bandwidth Compression (BWC).
Ordinarily BWC and MTFC are kept separate; BWC degrades the image, and MTFC improves it. The literature on both subjects is vast. Readers needing an introduction to either area can find it in Pratt [2]. The contribution of this paper is to note that a savings in computation occurs if BWC and MTFC are mixed rather than done separately, and to discuss results of experiments using such a mix. The particular concern in the experiments was whether the MTFC would be as good as when applied separately from BWC.
Formulation and Discussion
A typical BWC scheme involving a two-dimensional cosine transform is the following:
Divide the image into N x N blocks of pixels. Obtain the Odd Symmetrical Cosine Transform G(u,v) of each input block F(j,k) by [3]
{
{ F(j,k)/4 j=k=0
_ {
F(j,k) = { F(j,k)/2 j=0, k<>0 or j<>0, k=0
{
{ F(j,k) elsewhere
{
N-1 N-1
----- -----
\ \
1 \ \ _
G(u,v) = - > > F(j,k) for u=v=0
N / /
/ /
----- -----
j=0 k=0
N-1 N-1
----- -----
\ \
2 \ \ _ 2pju 2pkv
G(u,v) = - > > F(j,k)cos(------)cos(------) otherwise.
N / / 2N-1 2N-1
/ /
----- -----
j=0 k=0
Note: For typographical reasons, I have used p for pi=3.14159... in the above formula, and will continue with that definition of p in all formulas throughout this article.
The coefficients G(u,v) are then grossly quantized, and coded representations of these quantized coefficients are transmitted to the receiver for decoding. The gross quantizing and encoding is often done using some form of a Max Quantizer [4].
The receiver decodes the signals from the sender to obtain an approximation of the cosine transform coefficients Gapp(u,v). To obtain the approximation Fapp(j,k) to the image as it was before BWC, an inverse transformation is performed:
N-1 N-1
----- -----
\ \
_ 1 \ \
Fapp(j,k) = - > > Gapp(u,v) for j=k=0
N / /
/ /
----- -----
u=0 v=0
N-1 N-1
----- -----
\ \
_ 2 \ \ 2pju 2pkv
Fapp(j,k) = - > > Gapp(u,v)cos(------)cos(------)
N / / 2N-1 2N-1
/ /
----- -----
u=0 v=0
otherwise.
{ _
{ 4Fapp(j,k) j=k=0
{ _
Fapp(j,k) = { 2Fapp(j,k) j=0, k<>0 or j<>0, k=0
{ _
{ Fapp(j,k) elsewhere
{
Typically at this point MTFC would be applied. Instead of doing such processing, one can apply MTFC by working directly on the approximation Gapp(u,v) of the cosine transform coefficients. Multiplication of the cosine transform coefficients is the same as multiplication of the Fourier transform moduli of an unfolded image, defined by reflection at the coordinate axes:
_
F(j,k) = F(|j|,|k|)
The original image F(j,k) is defined only for j,k > 0; the reflected image is also defined in the other quadrants. By multiplying the coefficients Gapp(u,v) by MTFC terms as if the coefficients Gapp(u,v) were the Fourier transform moduli, the output of the inverse cosine transform step will be the MTF-corrected (or enhanced) image instead of the approximation to the MTF-degraded image submitted to BWC.
Experimental results with such an enhancement technique confirm that this MTFC method works. The test image was divided into 16 x 16 blocks of pixels (N=16 in the above cosine transform formulas) for the experiments. Encoding of the cosine transform coefficients by a Max Quantizer reduced the bandwidth from 11 to 2 bits per pixel. The bits were allocated to encoding of the cosine transform coefficients in several different ways, and several MTFC weightings were tried to see the effects of various degrees of enhancement. In all cases that the bit allocation resulted in an acceptable approximation to the degraded-before-BWC image, adding the MTFC multiplication step before the inverse cosine transformation produced the same sort of improvement in quality that an equivalent convolution did.
Some bit allocations to the encoding of the cosine transform coefficients resulted in the objectionable effect known as tiling. The "tiles," the 16 by 16 blocks, become apparent if bit allocation is too heavily weighted to low frequencies at the expense of medium and high frequencies. When MTFC is applied, the tiling is exaggerated. The tiling appeared to be less severe when the MTFC was applied by multiplication of the coefficients before the inverse cosine transform. Application of MTFC by convolution using a 7 x 7 kernel resulted in more severe tiling. In both cases the tiling could be objectionable. However, this problem is almost eliminated if the bit allocation is properly adjusted to reflect the information capacity of the image [5]. For this experiment a satisfactory weighting resulted from setting the number of reconstruction levels of the Max Quantizer proportional to the variance of each coefficient multiplied by the radial distance from the DC term. The DC term was always coded with eight bits, while no other frequency was ever coded with more than five bits. Other satisfactory bit allocation weightings were also found, all based on setting the number of reconstruction levels proportional to the variance times a weighting to favor high frequencies.
Conclusions
Enhancement by multiplication of image data in the cosine transform domain is an alternative to convolution or Fourier transform domain multiplication. If the image is cosine transformed for bandwidth compression, most of the arithmetic processing involved in enhancement will thus be eliminated. The size of the two-dimensional cosine transform block employed will affect the output quality, just as the size of a Fourier transform block would. In general, a carefully designed BWC technique which gives acceptable results when MTFC is applied after uncompression will likely give acceptable results when MTFC is applied by coefficient multiplication before the final inverse transform.
References
- E. O. Brigham, The Fast Fourier Transform, Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
- W. K. Pratt, Digital Image Processing, J. Wiley & Sons, New York, 1978, pp. 242-247.
- W. K. Pratt, Digital Image Processing, J. Wiley & Sons, New York, 1978, p. 246.
- J. Max, Quantizing for Minimum Distortion, IRE Transactions on Information Theory, IT-6, March, 1960, pp. 7-12.
- J. C. Dainty and R. Shaw, Image Science, Academic Press, New York, 1974, p. 366.
The information provided, and views expressed on this site are my own and do not represent the IBM Corporation.