Use of correlation for pattern size extraction
by Nikolai V. Shokhirev
- Preliminary study
- Multi-pulse signal
- Two-width multi-pulse signal
- Smooth signal
The knowledge of characteristic sizes of image/signal patterns is very important in image processing, pattern recognition, signal compression, multi-resolution analysis and modeling. This information allows the creation of more efficient algorithms (for example, the use of reduced number of basis functions).
Let us consider the following model problem. Several rectangular pulses are randomly distributed on the interval of length L. The pulses can overlap. In the examples below the length L = 640, the number of pulses N = 15, the width of each pulse W = 20. It is necessary to determine the width W.
Fig.1. Random (overlapping) rectangular pulses (top) and their derivatives (bottom)
We can employ the following approaches
The first method is inefficient, inaccurate, unstable, and does not work well in the case of overlapping pulses. The next two approaches have the strong advantage that they do not depend on the position of a signal.
Fourier spectrum. In the case of one pulse the Fourier transform has the following spectrum
Fig.2. Spectrum intensity (absolute value) for the one-pulse signal.
The first minimum is at n = L/W = 640/20 = 32. This is also the period of spectrum pulsation.
Note that in general the real and imaginary parts of the one-pulse spectrum display no specific pattern and their shape depends on the pulse position:
Fig.3. Discrete Fourier transform of the rectangular one-pulse signal function
Autocorrelation function. The correlation of two functions f and g is defined in Eq. (1a). It can be also expressed via their Fourier transforms F and G (1b).
The correlation function for f = g is called the autocorrelation function.
In the case of a one-pulse signal the autocorrelation function has the following shape:
Fig.4. autocorrelation function for the one-pulse signal.
It reaches zero at n = W = 20.
Fourier spectrum. In the case of N = 15 the spectrum has the following shape
Fig.5. Spectrum intensity for the multi-pulse signal.
The spectrum has less distinctive features in comparison with the one-pulse signal (Fig. 2.). The spectrum is noisy because of the random pulse positions.
Autocorrelation function. The autocorrelation function now has the minimum at n = 20, instead of zero in the one-pulse case (Fig.4.). The additional extrema again are due to the noise.
Fig.6. Autocorrelation function for the multi-pulse signal.
This additional structure makes impossible processing the signals containing the pulses with different widths.
Use of derivative
Fourier spectrum. The Fourier transform of the derivative of multi-pulse signal is very broad and shows no specific features.
Fig.7. Discrete Fourier transform of the derivative of multi-pulse signal
Autocorrelation function. In contrast to the Fourier transform, the autocorrelation function has a strong peak at the width of the pulse.
Fig.8. Autocorrelation function of the derivative of multi-pulse signal.
The signal comprises of an equal number of randomly distributed rectangular pulses with two different widths: W1 = 20 and W2 = 10.The pulses can overlap.
Fig.9. Random two-width (W1 = 20 and W2 = 10) rectangular pulses (top) and their derivatives (bottom)
The derivative approach allows extracting of the width of both pulses. The accuracy and resolution are pretty high.
Fig.10. autocorrelation function for the multi-pulse signal.
As an example consider the signal consisting of the Gaussian pulses
The width W is defined as a distance between the points of the steepest slope
Fig.11. Gaussian-pulse signal (top) and its "sharpening" (bottom)
The use of both the original signal and the derivative in this case does not produce any reasonable result. However the "sharpening" of the signal allows the determination of the pulse width. The smooth signal is replaced with the sequence of rectangular pulses with vertical boundaries at the points of steepest slopes.
Fig.6. Autocorrelation function for the sharpened signal.
The values of the autocorrelation function are distributed around n = 21. The width parameter W = 20 is within the spread of values .
The program Correlation.zip .
Complete project Delphi7 source code: correlations.zip. The code requires my PasMatLib library. It should work down to Delphi3.
Please e-mail me at firstname.lastname@example.org
©Nikolai V. Shokhirev, 2001-2005