## Use of correlation for pattern size extraction

by Nikolai V. Shokhirev

ABC Tutorials |

## Contents

IntroductionPreliminary studyMulti-pulse signalTwo-width multi-pulse signalSmooth signalDownloads

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

- Direct detection of the beginning and the end of signals.
- Fourier transformation of the signal
- Autocorrelation of the signal

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.

*One-pulse 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).

(1a) | |

(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: W_{1} = 20 and W_{2} = 10.The pulses can
overlap.

Fig.9. Random two-width (W_{1} = 20 and W_{2} = 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 .

**
Downloads**

The program **Correlation.zip** .

Mini-Manual:

- Create
- DFT
- Corr
- Reset

Complete project Delphi7 source code: **correlations.zip**.
The code requires my **PasMatLib**
library. It should work down to Delphi3.

ABC Tutorials |

Please e-mail me at nikolai@shokhirev.com |

©Nikolai V. Shokhirev, 2001-2005