Implementation of A 2D Real-Time Correlator Based on a DSP

Texas Instruments Audio and Video/Imaging Series

Image correlation plays an important roll in vision systems and it can be used for autonomous navigation, tracking systems, detection of environment changes, and automatic pattern recognition. The correlation between images must usually be calculated in a very short period of time to be integrated in real-world applications. In this project, the operation of a 2D correlator is tested by implementing a pattern recognition system based on the real-time location of a vehicle model moving along a square-shaped area. This system uses some traditional filter designs for correlation-based pattern recognition.

Correlation evaluation begins when an input image is presented. Eventually it could need some preprocessing, which usually includes operations such as size adjustment, color space transformations, or image compression [1]. After preprocessing, we must calculate a 2D Fourier Transform of the image. In the case of an image consisting of M rows by N columns (M+N) we need a 1D Fourier Transform. A 1D Fast Fourier Transform (FFT) for N samples needs about Nlog₂N complex products, thus a 2D FFT for an M*N image involves about N*M*log₂MN complex multiplications [3],[5],[10]. We can achieve additional speed up considering that the input image is a real signal and hence its Fourier Transform is an Hermitic function (F(s) = F*(-s)) [3].

Then, the 2D Fourier Transform of the input image is multiplied by the conjugation of the filter's frequency response. We obtain the classical matched-filter (MF) when the Fourier Transform of the target is taken as a filter [7]. When all the magnitudes of the frequency response are set to 1 the filter is called a Phase-only Filter (POF). Also, we can use a circular harmonic component of the target's spectrum as a filter which leads to the Circular Harmonic Filter (CHF) [7]. These are only a sample of some of the filter designs available. The product between the spectrum of the image and the conjugation of the filter is used as input for a 2D Inverse Fourier Transform and the result is the desired correlation. The correlator implemented in this work follows Equation 1 for its calculations.

   (1)

Where the terms represent:

We can analyze the correlation result in several ways to make a decision about possible locations of the target in the input scene. The filter H(u,v) is previously calculated and stored in memory. We can calculate FFTs faster for real data if the values are arranged in a special way, because the length of the vector is reduced in half [6].

IFFT operations are performed without additional optimization while quadrants swap (ƒs) and matrix transpose (T) are accomplished using channels for Direct Memory Access (DMA) available in the IDK. Table 1 demonstrates results on the time invested in each process for the evaluation of Equation 1 using the DSP TMS320C6711.

Figure 1:  Stages involved in a basic pattern recognition system

After binarizing the magnitude of the correlation matrix, a labeling is done in which an integer number is assigned to the pixels of each non-zero region of the matrix. Then, centers of mass are calculated for each of the labeled regions and those values are stored in memory. Finally, the display process consists of showing a mark (for example, a small cross) at each of the coordinates at the centers of mass stored in memory. All these operations must be done in real-time. We haveimplemented them with the DSP TMS320C6711 and tested in real-time conditions; mean values for processing time results for a single frame are demonstrated in Table 2.

As Table 2 illustrates, additional processing for the pattern recognition system leads to an increase of 13.12 milliseconds which is about 13.4% of computational load. Most of the additional load is concentrated in the process of labeling and calculation of center of mass which takes 9.4% of the whole processing time.

Figure 2:  Car models used as target pattern

This proposed application requires rotation invariant response of the filter because target location must be given independently of the orientation of the vehicle given that car models move in random directions. Circular Harmonic Filters (CHFs) exhibit this feature an were appropriated for this requirement.

   (2)

we can calculate the order m radial component, ƒ_m(r) according to

   (3)

From Equation 2, when the target is rotated by α degrees, all its CHCs will include a phase term of the form e^imα. Using Equation 3, we can conclude that only radial components are affected when the target is scaled. Particularly, the first feature is used by CHFs to obtain rotation invariance, which guarantees a constant correlation peak value even when the target is rotated in the input scene. Order m^th classical CHFs have the following impulse and frequency response:

   (4)

   (5)

There are many filter designs based on CH decomposition. Some of the most important versions include the following designs:

Phase-Only CHF:	(6)
Optimum Trade-Off CHF:	(7)
Phase-Derived CHF:	(8)

Where K is a tunable constant while m is the order of the filter.

We tested and evaluated the recognition performance of Classical, Phase-Only, Optimum Trade-Off, and Phase-Derived CHFs on the implemented system. Second order filters (m=2) lead in all cases to the best results.

Figure 3:  (a) Input scene and (b) magnitude of the correlation matrix between the scene and target in Figure 2a

We tested the performance of the four filter designs in real-time conditions with the pattern recognition system. The target was perfectly located almost all of the time independently of its orientation (Figure 3). This figure shows the intensity distribution of the correlation between the phase-derived CHF of target (Figure 2a) and the scene (Figure 3a). Sometimes the system lost the target, usually when the car model was located at the borders of the track, while a non-target vehicle was located at the central region. This situation is caused by a change in perspective.

In order to compare the general performance of the different filter designs, an 18 minute video clip of the cars moving randomly along the track was recorded and used as input for the recognition system. The video was processed with the recognition system, changing the filter design and the target, so a total of 12 specific situations were tested. The output of the pattern recognition system was recorded and the probabilities of success in target location were estimated by randomly sampling a representative number of output frames. These probabilities are shown in Figure 4.

Figure 4:  Probabilities of success for target location with different filter designs

From Figure 4, we concluded that Phase-Derived CHF shows the best performance. Also, when the car model in Figure 2c was used as target, the probability of success for all the filters was very high, close to 100%. This is because target in Figure 2c exhibits the highest mean intensity value among all three targets. Targets 2a and 2b showed a probability of detection close to 80% when detected with Phase-derived CHF. In the remaining 20% of the cases, when the target was missed, a false detection was generated due to the presence of the car model corresponding to Figure 2c, which is brighter than all the other images.

We idetified some limitations on the use of DSPs for digital image processing. DSPs are very well suited for basic image processing operations, such as binarization or spatial filtering, and they take advantage of software and hardware resources. However, the architecture of the DSP used in this implementation does not allow a peak performance when operations such as 2D filtering in frequency domain or 2D correlation are performed.

The implementation of the pattern recognition system allowed us to compare four filter designs that guarantee rotation-invariant results for correlation. Particularly, phase-derived CHFs achieved the best results when we measured probability of detection. Future work will be focused on including invariance to small perspective variations generated when the target is far away from the vertical axis of the camera. Also, a superior resistance to noise presence and changes in illumination will improve the performance of the system.

References