Read an Excerpt

Deconvolution of Images and Spectra

Dover Publications, Inc.

Convolution and Related Concepts

Peter A. Jansson

College of Optical Sciences, University of Arizona, Tucson

I. Introduction
II. Definition of Convolution
A. Discrete Case
B. Continuous Case
III. Properties
A. Integration and Differentiation
B. Central-Limit Theorem
C. Voigt Function
IV. Fourier Transforms
A. Special Symbols and Useful Functions
B. Some Properties and Relationships
C. Sampling and the Discrete Fourier Transform
D. Hartley Transform
V. The Problem of Deconvolution
A. Defining the Problem
B. Difficulties
C. Alternatives to Deconvolution
References

List of Symbols

a, b, g functions a(x), b(x), g(x), with no explicit dependences shown

a',b',g' first derivatives of functions a, b, g

an,bn,gn, sampled values of a(x), b(x), g(x)

a(x), b(x), g(x) functions used to illustrate properties of convolution

A,B,G functions A(ω), B(ω), C(ω), with no explicit dependences shown

A(ω), B(ω), G(ω) Fourier transforms of a(x), b(x), g(x)

c Constant

C Constant

cas(x) Cos(x)+Sin(x)

f(x),F(ω) function and Fourier transform, respectively

F'(ω), F"(ω) first and second derivatives of F(ω), respectively

G(ζ) Fourier transform of g(x) give n by alternative convention

H(X) 1 when x>0, 0 when x ≤ 0

i(x),i "image" data that incorporate smearing by s(x); sometimes include noise

ip(x) ideal noise-free image data

îM(ν,x) model representing idealized image data

j imaginary operator such that j2 = -1

n(x) additive noise

Na,Nb,Ng number of samples available for function a,b,g

o(x),o "object" or function sought by deconvolution, usually the true spectrum, but also the instrument function when this is sought by deconvolution

ô(x) estimate of o(x)

ôM(ν,x) model of true spectrum or true object

q independent variable given in scaled units of Gaussian half widths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

rect(x) rectangle function having haif-width ½

sgn(x) 1 when x>0, -1 when x≤0

sinc(x) (sin πx)/πx

Si(x) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

s(x),s spread function, usually the instrument function, but also spreading due to other causes

s(x,x') general integral equation kernel; shift-variant spread function

ν(x) function used to illustrate Fourier transform

V(ω) Fourier transform of ν(x) given by third system

x,x' generalized independent variables and arguments of various functions

<x>, <x2> first and second moments of a distribution of x

z(x)z1(x),z2(x) functions used to illustrate the Hartley transform

z(ω)z1(ω),z2(ω) Hartley transforms of z(x), z1(x), and z2(x), respectively

z2e(ω)z20(ω) even and odd parts of Z2(ω)

® fractional increase in instrument response-function breadth due to convolution with narrow spectral line

β parameter specifying influence of sharpness or smoothness criteria

[cross product] convolution operation

δ(x),δ Dirac δ function or impulse

δ'(x),δ' first derivative of δ(x)

Δ(x) half-width at half maximum (HWHM)

ΔxG,ΔxC Gaussian and Cauchy half-widths at half maximum

ΔxN Nyquist interval

ζ conjugate of x in alternative Fourier transform system; Fourier frequency in cycles per units of x; variable of integration

θ(x), Θ(ω) spurious part of solution ô(x) and its Fourier transform Ô(ω)

{LAMBDA](x) triangle function of unit height and half-width ½

μ scaled ratio of Cauchy to Gaussian half-widths,

σ standard deviation

σ2 variance

σ2a, σ2b, σ2g variances of a, b,g

σ2A, σ2B, σ2G variances of A,B,G

τ(ω),τ τ(ω), Fourier transform of s(x)

υ vector having components υl

υ1 parameters of a model comprising multiple peaks

Φ(υ) objective function to be minimized

ω conjugate of x; Fourier frequency in radians per units of x

Ω cutoff frequency such that τ(ω) = 0 for |ω| > Ω

II(x) positive-impulse pair 1/2δ(x + 1/2) + 1/2δ(x - 1/2)

II(x) impulse pair with positive and negative components, 1/2δ(x + 1/2) - 1/2δ(-1/2)

III(x) Dirac "comb" [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

I. Introduction

Our daily experience abounds with phenomena that can be described mathematically by convolution. Spreading, blurring, and mixing are qualitative terms frequently used to describe these phenomena. Sometimes the spreading is caused by physical occurrences unrelated to our mechanisms of perception; sometimes our sensory inputs are directly involved. The blurred visual image is an example that comes to mind. The blur may exist in the image that the eye views, or it may result from a physiological defect. Biological sensory perception has parallels in the technology of instrumentation. Like the human eye, most instruments cannot discern the finest detail. Instruments are frequently designed to determine some observable quantity while an independent parameter is varied. An otherwise isolated measurement is often corrupted by undesired contributions that should rightfully have been confined to neighboring measurements. When such contributions add up linearly in a certain way, the distortion may be described by the mathematics of convolution.

Spectroscopy is profoundly affected by these spreading and blurring phenomena. The recovery of a spectrum as it would be observed by a hypothetical, perfectly resolving instrument is an exciting goal. Recent advances have stimulated development of restoring methods that receive increasingly wider application. Imaging systems too suffer from blur, be they telescopes trained on large and distant objects, or microscopes examining small ones that are near. Whether we concern ourselves with science that requires imaging, spectroscopy, or other experimental approaches, our state of knowledge is often defined by the resolving limit of our instruments. Through modern restoring methods, the scientist has access to information that would otherwise remain unavailable. The advent of the new methods has even changed the way we regard experimental apparatus. These methods cannot fail to have a marked influence on the progress of science.

Before we can confront the problem of undoing the damage inflicted by spreading phenomena, we need to develop background material on the mathematics of convolution (the function of this chapter) and on the nature of spreading in a typical instrument, the optical spectrometer (see Chapter 2). In this chapter we introduce the fundamental concepts of convolution and review the properties of Fourier transforms, with emphasis on elements that should help the reader to develop an understanding of deconvolution basics. We go on to state the problem of deconvolution and its difficulties.

The most important symbols introduced in this chapter are used throughout the volume; that we occasionally deviate from this notation is testimony to the diversity of applications and to the limited number of clear and convenient notational possibilities. We have avoided mathematical rigor in favor of developing an intuitive grasp of the fundamentals. The reader is referred to the outstanding and readable text by Bracewell (1986a) for added depth.

This volume deals primarily with spectra and images, which may be taken generally to represent data acquired as a functions of one and two independent variables, respectively. Data from fields as diverse as radio astronomy, statistics, separation science, and communications are suitable candidates for treatment by the methods described here. Confusion arises when we discuss Fourier transforms of these quantities, which may also be called spectra. To avoid this confusion, we adopt the convention of referring to the latter spectra as Fourier spectra. When this term is used without the qualifier, the data space (nontransformed regime) is intended.

Also, application of these methods is not limited to one- and twodimensional problems. Most of the concepts herein may readily be extended to solve higher dimensional problems. Of particular interest are the closely related tomographic techniques of reconstruction from projections that have reached widespread application in medical imaging and industry. Works by Barrett and Swindell (1981) and by Herman (1980) serve as excellent guides to these methods and applications.

II. Definition of Convolution

A. DISCRETE CASE

Convolution, in its simplest form, is usually considered to be a blurring or smoothing operation. A "rough" or "bumpy" function is convolved with a smoothing function to yield a smoother output. Typically, each output value is identified with a corresponding input value. It is obtained, however, by processing that value and some of its neighbors. One simple way of smoothing the fluctuations in a sequence of numbers is to perform a moving average. Below, in row a, we see a smoothed sequence partially computed for the noisy values in row g:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this particular case, we chose to average five adjacent g numbers to produce each value in row a. We wrote each element in row a opposite the center of the averaging interval. Giving each element of rows a and g indices n and m, respectively, we write the moving average

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

It could suit our purpose to apply a weight to each of the g elements before summing:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this example the sum of the b weights is 1. Therefore, we may say that b is normalized. We see that each element of row a is a linear combination of a corresponding subset of the g elements. Sequential values of a are computed by sliding the set of b factors along row g. It is usually convenient to write each a value opposite the largest weighting coefficient in row b:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

We generalize this procedure in the following equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

For the present case, b vanishes everywhere except over the interval -2 to + 2. We also can define b as an infinite sequence of numbers. In this case we may write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

This is sometimes called the discrete convolution or serial product. The values of b and g, however, may just be samples of continuous functions.

Note here that because each value of an requires values of gn_2 through gn+2, N values of a can never be computed from N values of g. If Na is the number of a values desired, and Ng the number of g values available, we must always have Ng > Na, except in the trivial case where b has only one non-zero value. The representation of real-world situations usually involves some accommodation of this effect, possibly by padding the ends of arrays with zeros or by treating data values as if they were cyclic and "wrapped around," as is the case in a circulant matrix (Chapter 3, Section III.A). Often, sections of spectra can be chosen so that they begin and end in regions having base-line values of zero. Alternatively, one may choose the range of interest far from the ends of the data so that end effects can be ignored.

B. CONTINUOUS CASE

We may choose the sample interval to be as fine as we please, thus extending the concept of summation into the continuous regime. With a, b, and g now written as functions of the continuous variables x and x', we may write the convolution integral

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Each value of a is a weighted integral of the g function, the function b supplying the required weight and being slid along g according to the displacement specified by x'.

If the area under b(x) is unity,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

we may say that b(x) is normalized. Equation (5) then represents a moving weighted average. In the study of instrumental resolution, we often think of the convolution integral in this way.

We may denote convolution by the symbol [cross product], and rewrite Eq. (5):

a = b [cross product] g. (7)

The presence of the minus sign in the argument of b in Eq. (5) gives the convolution integral the highly useful property of commutativity, that is,

b [cross product] g = g [cross product] b. (8)

This is easily shown by redefining the variable of integration. Convolution also obeys associativity,

(d [cross product] b) [cross product] g = d [cross product] (b [cross product] g), (9)

and is distributive with respect to addition,

d [cross product] (b + g) = (d [cross product] b) + (d [cross product] g). (10)

These properties carry back to the discrete formulation. We shall use both discrete and continuous formulations in this volume, changing back and forth as needs require. The continuous regime allows us to avoid consideration of sampling effects when such consideration is not of immediate concern. Deconvolution algorithms, on the other hand, are numerically implemented on sampled data, and we find the discrete representation indispensable in such cases.

III. Properties

In addition to the relations just presented, we shall state without proof some other properties of convolutions. Most of these are quite easily proved.

A. INTEGRATION AND DIFFERENTIATION

If b and g are peaked functions (such as in a spectral line), the area under their convolution product is the product of their individual areas. Thus, if b represents instrumental spreading, the area under the spectral line is preserved through the convolution operation. In spectroscopy, we know this phenomenon as the invariance of the equivalent width of a spectral line when it is subjected to instrumental distortion. This property is again referred to in Section II.F of Chapter 2 and used in our discussion of a method to determine the instrument response function (Chapter 2, Section II.G).

---

Excerpted from Deconvolution of Images and Spectra by Peter A. Jansson. Copyright © 1997 Peter A. Jansson. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---