Signal processing

Use of correlation for pattern size extraction

by Nikolai V. Shokhirev

Up ABC Tutorials

Contents

Introduction

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)  

Preliminary study

We can employ the following approaches 

  1. Direct detection of the beginning and the end of signals. 
  2. Fourier transformation of the signal
  3. 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. 

Multi-pulse signal

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.

Two-width 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.

Smooth 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:

  1. Create
  2. DFT
  3. Corr
  4. Reset

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

 

Up ABC Tutorials
ABC Tutorials | Data Processing | Indirect Measurements | NMR Tutorials

Home | Resumé |  Shokhirev.com |  Computing |  Links |  Publications
[Mailbox]

Please e-mail me at nikolai@shokhirev.com

©Nikolai V. Shokhirev, 2001-2005