EP0039263A1 - Two-dimensional correlator device - Google Patents

Abstract

Device for two-dimensional correlation of an image obtained by scanning electromagnetic or acoustic waves with a reference image.

The scanned image is written in memories (40) and (41) and the reference image in memories (42) and (43). A couple of memories stores the real part and the imaginary part of the signal of the corresponding images. After digital-analog conversion, the signals are put on carrier and correlated line to line in the elastic wave convolver (50). The correlation signal after analog-digital conversion and complex demodulation is applied to an adder and the correlation image is stored with its real and imaginary parts in the memories (57) and (58).

Application to registration of the vehicle position on maps.

Description

The present invention relates to the two-dimensional correlation in real time of an image obtained line by line and of an image in memory. The device provides the image correlation signals for a certain number of lines with the image in memory, in time corresponding to a line scan.

The device according to the invention applies in particular to systems on board a vehicle and which provide images such that the lines are renewed by advancing the vehicle. More particularly, the device is applicable to radar, sonar or optical imagery which must necessarily operate in real time and for which the rate of renewal of the image lines is high and also to systems for which the volume and the consumption of means used must be reduced to the maximum. Among these systems, there may be mentioned the on-board systems for guiding, locating and resetting maps.

For example, in the field of underwater acoustic imaging, high definition sonar systems are used to visualize the seabed.

Also in the field of aerial mapping, airborne radar systems or active or passive infrared systems are used.

These systems consist of a transmitting antenna which sends signals in the form of waves, ultrasonic, electromagnetic, or infrared, in all or part of the surrounding space. The signals received by the same antenna are processed to separate the energies coming from different directions. The separation distance obtained depends on the angular resolution of the antenna, which is a function of the ratio between the wavelength λ of the signals transmitted and the length L of the antenna, ie λ / L.

For example, in order to obtain a high separating power, it is known to use a lateral vision radar antenna (called "side-looking" in Anglo-American literature) operating as a synthetic antenna, ₁ that is to say say using the displacement of the carrier vehicle to synthesize longer antenna length.

In airborne systems intended for aerial mapping by radar with synthetic lateral antenna, the signals received are recorded on photographic film and then processed to restore the true image, the processing consisting in correlating the signals with the reference signal as a function of displacement. of the vehicle and the distance to the object. The data collected is therefore important and the correlation treatments long. They are carried out optically by reading the film as described for example in an article by L.J. Cutrona et al (Proceedings IEEE, Vol. 54 no. 8, 1966, p. 1026).

In other applications for processing radar signals, where the correlation and also convolution functions play an important role, the processing operations are performed digitally because they are more precise and flexible, these processing operations being mainly focused on measurements of time of arrival, sorting and identification of signals.

Given the calculation speed, digital devices take up too much space and consume electricity for on-board, airborne or submarine systems.

• 1) P. Anthouard et T. Beauvais AGARD Conférence Proceeding N° 230, et
• 2) E.C.S. Paiges, Proc. Int. Seminar on Component Performances and System Application of SAW devices (Avemore Scotland) p. 167-180, 1973, TEE Publication.

To remedy these drawbacks, the device according to the invention uses, for the correlation, elastic wave components which are particularly well suited to the rapid processing of analog signals. An application to radar signal processing can be found in the following articles:

• 1) P. Anthouard and T. Beauvais AGARD Conférence Proceeding N ° 230, and
• 2) ECS Paiges, Proc. Int. Seminar on Component Performances and System Application of SAW devices (Avemore Scotland) p. 167-180, 1973, TEE Publication.

Briefly, it is a two-dimensional correlation device, between a reference image of an Oxy plane and having lines oriented in the direction Ox and an image obtained by scanning in the Oxy plane, the scanned lines being parallel to Ox, characterized by the fact that the device comprises, on the one hand a correlator receiving simultaneously on these two inputs the two electrical signals of a line of the reference image and of a line of the scanned image providing a one-dimensional correlation line formed of points corresponds to the offsets of the two input signals and that it also comprises a summing device summing the signals for the points corresponding to the same offset, for all of the one-dimensional correlation lines of the two images, the summation signal providing a two-dimensional correlation line, and that the device provides a new two-dimensional correlation line, after each new scanned line of the image obtained by scanning .

• - la figure 1, le schéma de balayage d'un plan Oxy obtenu par avancement d'un véhicule muni d'une antenne émettrice et réceptrice ;
• - figure 2, le schéma du principe de la corrélation bidimensionnelle de deux images ;
• - figure 3, un convoluteur à ondes élastiques ;
• - figure 4, un organigramme simplifié du corrélateur bidimensionnel ;
• - figure 5, le schéma d'un corrélateur bidimensionnel pour des images mises en mémoire avec corrélation par un convoluteur à ondes élastiques ;
• - figure 6, le schéma des circuits par une mise sur porteuse d'un signal complexe ;
• - figure 7, quelques signaux temporels ;
• - figure 8, le schéma des circuits pour l'obtention des composantes complexes du signal de corrélation ;
• - figure 9, le schéma montrant le calage d'une image balayé à partir des signaux de corrélation.

Other characteristics and advantages will emerge from the description which follows, illustrated by the figures which represent:

• - Figure 1, the scanning diagram of an Oxy plane obtained by advancing a vehicle provided with a transmitting and receiving antenna;
• - Figure 2, the diagram of the principle of the two-dimensional correlation of two images;
• - Figure 3, an elastic wave convolver;
• - Figure 4, a simplified flowchart of the two-dimensional correlator;
• - Figure 5, the diagram of a two-dimensional correlator for images stored in memory with correlation by an elastic wave convolver;
• - Figure 6, the circuit diagram by putting a carrier on a complex signal;
• - Figure 7, some time signals;
• - Figure 8, the circuit diagram for obtaining the complex components of the correlation signal;
• - Figure 9, the diagram showing the timing of a scanned image from the correlation signals.

Figure 1 shows an example of lateral vision imagery. Mounted on the vehicle 1 moving in a direction yy ', the antenna transmits and receives along the beam F which intercepts the object plane along a line J parallel to the axis xx'.

The image points forming this line J correspond to a distance between L ₁ and 1.2. The resolution along yy 'corresponds to the angular width at half power of the beam F while the resolution along xx' is inversely proportional to the frequency band of the signals transmitted.

By advancing vehicle 1, a succession of lines' is obtained, forming a so-called B-mode image.

In other systems, several beams F can be formed simultaneously on reception, making it possible to obtain several lines forming an image.

The image lines thus obtained are stored and used to be correlated with an image already in memory.

où X est la dimension de l'espace pour lequel est calculé la fonction correspondant à un décalage ℓ suivant Ox.The one-dimensional correlation function of two signals s ₁ and s ₂ depending on the dimension x is:

where X is the dimension of the space for which the function corresponding to an offset ℓ along Ox is calculated.

où X et Y sont les dimensions de l'espace pour lequel est calculée la fonction correspondant à un décalage A suivant Ox et un décalage m suivant Oy.The two-dimensional correlation function of two signals s ₁ and s ₂ depending on the two dimensions x and y is written:

where X and Y are the dimensions of the space for which the function corresponding to an offset A according to Ox and an offset m according to Oy is calculated.

It is possible to obtain in a simple manner the two-dimensional correlation function of two images, in the case where one of the two images is obtained by a system such as that of FIG. 1, the other image being fixed. Indeed in this case the shift along the direction of propagation of the vehicle, for example Oy, is effected automatically by the advancement of the vehicle.

The principle of correlation between a fixed image and an image obtained by scanning is shown in FIG. 2.

The still image 10 has K lines of M points and the scanned image 11 has L line, such as J, of N points. The scanning is done parallel to the direction Ox. In fig 2 we took the case of K less than L and M greater than N.

• On corrèle suivant la dimension x et ligne à ligne les K premières lignes de l'image balayée 11, avec les K lignes de l'image fixe 10 pour obtenir K lignes de (M-N) points de la fonction de corrélation monodimensionnelle C(ℓ) suivant la direction Ox (1), chaque point correspondant à un décalage ℓ.

The operating principle of the device according to the invention is as follows:

• The first K lines of the scanned image 11 are correlated along the dimension x and line to line, with the K lines of the fixed image 10 to obtain K lines of (MN) points of the single-dimensional correlation function. tional C (ℓ) in the direction Ox (1), each point corresponding to an offset ℓ.

The K points corresponding to the same offset t are summed over all of the K lines to obtain MN two-dimensional correlation points C (ℓ, m) for an offset m along Oy (2), these MN points forming a correlation line such as 13.

The same process is repeated with lines 2 to K + 1 of image 11 providing a second two-dimensional correlation line and so on until LK correlation lines of MN points forming the two-dimensional correlation 12 of the two images 10 and 11.

This principle applied to the imaging systems recalled above naturally leads to obtaining the line by line offset of the image 11 by advancing the vehicle along Oy and the system can therefore provide an image 11 formed only of K lines.

A correlation line 13 is obtained each time a line of the image 11 is renewed. The proposed device makes it possible, thanks to the use of acoustic convolvers, to obtain a two-dimensional correlation line in a time interval which is generally less than the period of renewal of the lines of images obtained by imaging systems using a vehicle, as will be shown later in the applications.

The proposed device applied to imaging systems therefore provides the two-dimensional correlation function of two images in real time.

The diagram in FIG. 3 shows the organization of the device for correlating the two images 30 and 31. Only two consecutive lines r _l , r ¹ ₁ of the image 30 and r ₂ , r ¹ ₂ of l have been represented. image 31. The two images 30 and 31 are correlated line to line, r ₁ with r ₂ then r ¹ ₁ with r ¹ ₂ , etc. in a correlating device 32. Each time two lines, for example r ₁ and r ₂₁ are correlated the correlating device provides a one-dimensional correlation line composed of points each corresponding to a certain offset ℓ. In circuit 33 the points of all the correlation lines are added by offset ℓ and when all the image lines 30 and 31 have been processed, circuit 33 provides a line of the two-dimensional correlation corresponding to an offset m in the direction of movement line by line of one of the two images.

The correlating device 32 can for example consist of a computer which can also include the circuit 33. Preferably, it will consist of an analog device formed by an acoustic convolver.

FIG. 4 shows the known principle of the elastic wave convolution device. It comprises a rod made of piezoelectric material 20, comprising at these ends two interdigitated transducers Ti and T ₂ between which a pair of planar electrodes 21 and 22 is disposed.

The two signals from which we want to obtain the convolution F (t) and G (t) are modulated by a pulsation carrier w capable of generating acoustic waves in the bar 20.

• _F(t-_z/v) e^j(ωt - kz) et _G (t + _z/v) e^j(ωt + kz) où z est la coordonnée pour les ondes à la vitesse v et k le nombre d'onde w/v. Du fait des propriétés non linéaires du substrat, on obtient entre les bornes des deux électrodes 21 et 22 un signal H (t) = K_c e^2jωt F (τ) - G (2t -τ) d_T (2), où K_c est lié au rendement énergétique.

These signals are applied to the transducers T and T ₂ and the two contradictory acoustic waves thus emitted are of the form:

• _F (t- _{z / v} ) e ^j (ωt - kz) and _G (t + _{z / v} ) e ^j (ωt + kz) where z is the coordinate for waves at speed v and k the wave number w / v. Due to the non-linear properties of the substrate, we obtain between the terminals of the two electrodes 21 and 22 a signal H (t) = K _c e ^2jωt F (τ) - G (2t -τ) d _T (2), where K _it is related to energy efficiency.

The signal H (t) represents the convolution function of F and G compressed in time in a ratio 2, and in a time interval corresponding to the time during which the two signals interact over the entire length S of the electrodes 21 and 22 , along the axis of propagation. So if the two signals had the same duration only one point of the correlation function would be valid. On the other hand, if the two signals have a different duration, a number of valid correlation points is obtained equal to the difference in the number of points between the two signals.

Generally, to increase the efficiency of these devices, acoustic beam compressors or a plate of semiconductor material placed between the electrodes 21 and 22 and the bar 20 are used.

Operation in correlator requires the reversal in time of one of the signals. This operation is easily implemented when the signals are stored in memory, since it then suffices to carry out the reading in the opposite direction to writing.

An exemplary embodiment according to the invention is shown by the diagram of FIG. 5, for the processing of signals corresponding to the two images to be correlated. To keep information of both amplitude and phase, each signal has two components called complex components. The two signals are stored in the form of complex digital samples in random access memories of RAM type. To simplify, only the reading circuits of these memories have been shown. Thus the real and imaginary parts of the signal representative of the image scrolling line by line are stored line by line in the memories 40 and 41 while the real and imaginary parts of the reference signal are also stored line by line in the memories 42 and 43.

The digital samples of the stored signals are quickly read line by line at the rate of a clock signal H _M supplied by the generator 46. The clock signal H _M is applied to the addressing devices 61 and 62 which supply the addresses of RAM memories 40, 41, 42 and 43.

The clock signal also controls the rate of analog-digital conversion of the samples read in the converters 44.1, 44.2, 44.3 and 44.4 so as to synchronize the sending of the two signals on two modulator circuits 45.1 and 45.2. A modulator circuit for setting on a carrier frequency is represented in FIG. 6. It is of conventional type, namely composed of two multipliers 65 and 66 in cos (2πf _o t) and sin (27rf t), where the frequency f is supplied by a local oscillator 47. The real part P of each of the input signals is multiplied by the term in cosine while the imaginary part P ₁ is multiplied by the term in sine. The two signals obtained are then added in a circuit 63 and the resulting signal is filtered in a bandpass filter 64 centered on f ₀ of band B _{0 as a} function of the frequency of the clock signal H _M.

The two signals s (t) and r (t) obtained at the output of the two modulators 45.1 and 45.2 are sent after amplification on the transducers of a piezoelectric convolver device 50, whose central frequency is equal to f and the band equal to B .

If TH is the period of the signal of the control clock H _M , N and M respectively the number of samples per line in the image memories 40, 41 and in the reference memories 42, 43, the signal durations s (t) and r (t) which correspond to each line read are respectively equal to NT _H and MT _H.

et il est décalé par rapport aux signaux d'entrée d'un temps égal à

; en outre il est à la fréquence f₁ = 2 f comme le montre la formule (2).The time diagram of the input and output signals of the convolver 50 is indicated in FIG. 7 when M = 2N. At time t the two signals r (t) and s (t) shown respectively on lines a and b are sent to the two transducers 51 and 52 (FIG. 5) distant by a length S _o = MT _H .v , if v is the speed of the elastic waves in the piezoelectric bar. Given the time compression of a factor of 2, the signal obtained u (t) represented on line _c , has a duration equal to

and it is offset from the input signals by a time equal to

; furthermore it is at the frequency f ₁ = 2 f as shown in formula (2).

The signal u (t) is sent to a demodulator circuit 49 shown in FIG. 8, in which the signal is multiplied in circuits 82 and 83 by sin (2πf ₁ t) and cos (Zπf ₁ t), the frequency f _I being supplied. by a local oscillator 48 the two signals obtained then being filtered in two low-pass filters 84 and 85 whose cut-off frequency is close to B _o / 2.

At the output of the demodulator 49 the two signals are sent in two sampler-coder circuits 55.1 and 55.2 controlled by a clock signal H _T with a period 2 times smaller than H _M and restoring the signals in the form of digital samples.

At the output of each of the circuits 55: 1 and 55.2, we therefore obtain for a processed line and at the rate MT _H , MN samples coded on a number of bits n chosen for example equal to the number of original bits in the memories and occupying a duration (M - N) T _H / 2.

These MN samples corresponding for example to the line i + 1 are added with the MN samples coming from the sum of the samples of the i preceding lines in a circuit 56 composed of a buffer memory, of an accumulator, formed of MN boxes of n bits and one or more adders. So the samples from each of these two registers are. added box by box sequentially or in parallel in a time interval at most equal to t2 = MT _H. When all of L lines have been processed the M - N samples obtained are stored in a line of memories 57 and 58, at the rate of a clock H _S of the same period as H _m forming a two-dimensional correlation line.

The process thus described begins again each time a line is renewed in the process image. When a number L of lines have been renewed the memories 57 and 58 are filled and correspond to the two-dimensional correlation of the reference image, with the image which has passed line by line over L lines. The number of correlation lines at output can be arbitrary; however, from a number L of lines formed, the two original images which correspond to line i and to line i + L are entirely distinct.

The output signals of circuit 56 can be processed to obtain either the module or the phase, a single output memory then being used.

Of course, it is possible to reverse the size of the memories, the copy then being smaller than the image read.

The device according to the invention applies to guiding a machine by resetting cards. Referring to FIG. 9, a machine follows a trajectory 72 and at each instant it acquires the image of a portion of terrain 70. It has in memory a reference map 71 composed of lines identified according to an axis system rectangular Oxy and whose ordinate is known there. The navigation systems on board the device make it possible to provide an image at all times, the lines of which remain parallel to the axis Oy of the reference map. At the instant when the ordinate of the read image is equal to y, the two-dimensional correlation line corresponding to this instant has a maximum whose position will make it possible to measure the abscissa x and to readjust the machine.

The device is applicable for aerial systems with radar and infrared and also for underwater systems with sonar. In addition, if the machine is able to follow the same trajectory several times with great precision in a relatively long period of time, the device can be applied to the detection of changes in terrain or seabed; in particular it can be applied to satellites taking into account the reduced dimensions for this type of machine.

The device described also applies to the recognition of shapes: the copy representing the shape to be recognized is then smaller than the image read.

• - nombre de ligne L = 100
• - nombre de points par ligne N = 100 et M = 400
• - échantillons numériques sur 8 bits.

In an exemplary embodiment, the dimensions of the image and reference memories are for example:

• - number of lines L = 100
• - number of points per line N = 100 and M = 400
• - 8-bit digital samples.

These memories are chosen using dynamic MOS technology. By cutting the memory into planes whose cycles partially overlap, the reading of a memory point can be done in 100 ns and the clock period T _H is equal to this value, ie a clock frequency of 10 MHz.

The central frequency f _o and the band B _o of the convolver are chosen to be 50 MHz and 10 MHz respectively.

The duration MT _H of the signal r (t) is equal to 40 us and the length S is close to 12 cm providing a reduced bulk.

The circuit 56 of FIG. 6 comprises an 8-bit x 300 buffer memory and a 16-bit x 300 accumulator. An addition operation being carried out in a time of 50 ns, period of the clock H _T , the time to add 300 samples remains below MT _H, ie 40 us using a single adder.

A two-dimensional correlation line is therefore obtained in 40 µs x 100, or 4 ms, using a single convolver. Of course, higher operating speeds can be achieved by using several convolvers in parallel to process several lines in parallel.

For comparison, the fastest digital circuits allow the calculation of a point of the correlation function in the same order of magnitude of time where the whole function is reconstituted by the convolver device, that is to say a speed ratio of around 100.

In the example shown, a line of the two-dimensional correlation between a line of 100 x 100 and an image of 400 x 100 is obtained in 4 ms using a single convoluting device.

For real-time processing, this duration corresponds to the maximum duration that must be respected between two two-dimensional correlations images for two shifts depending on the progress of the vehicle. This duration corresponds to a distance traveled of the order of 1 meter at a speed of Mach 1 and this resolution is of the order of magnitude of that sought, in general, for soil exploration systems.

In the field of underwater acoustic imaging, the resolution obtained at a hundred meters is of the order of 15 centimeters. For a boat going at 20 knots, the renewal period of an image line is equal to 15 ms and only the use of the proposed device makes it possible to obtain the two-dimensional correlation function in real time.

According to a variant of the invention, the digital memories 41, 42, 43 and 44 are replaced by charge transfer devices or C.C.D. These devices can have 512 stages and be controlled at a frequency of 10 MHz making their use possible. Also a charge transfer device can be used in place of an acoustic convolver.

For the correlation of images obtained by optical methods, this correlation is done on the intensities and not on the amplitudes. In the case, the reference image and the scanned image are stored respectively in a single memory such as 40 and 42 in FIG. 5.

Claims (8)

1. Two-dimensional correlation device between a reference image of an Oxy plane and having lines oriented in the direction Ox and an image obtained by scanning in the Oxy plane, the scanned lines being parallel to Ox, characterized in that the device comprises, on the one hand a correlator receiving simultaneously on its two inputs the two electrical signals of a line of the reference image and of a line of the scanned image providing a one-dimensional correlation line formed of points corresponding to the offsets of two input signals and that it also comprises a summing device summing the signals for the points corresponding to the same offset, for all the one-dimensional correlation lines of the two images, the summing signal providing a two-dimensional correlation line, and that the device provides a new two-dimensional correlation line, after each new scanned line of the image obtained by scanning. 2. Two-dimensional correlation device according to claim 1, characterized in that the lines of the reference image are oriented in opposite direction relative to the image obtained by scanning and that the correlation signal is supplied by a device of the surface wave convolver type and the correlator is an analog convolver. 3. Two-dimensional correlation device according to claim 2, characterized in that the analog convolver is of the surface wave convolver type. 4. Correlation device according to claim 2, characterized in that the analog convolver is of the charge transfer convolutor type. 5. Two-dimensional correlation device according to claims 2 or 3, characterized in that the reference image (10) consists of K lines of M points and that the scanned image (11) consists of L lines of N points, where L> K and N <M, that the K lines of the reference image are correlated line by line with all the sets of K lines such that i to i + K - 1 of the scanned image (11) where 1≤ i ≤ L - K, thus providing after summation for the same shift i along Ox, (LK) correlation lines (13) of (MN) points. 6. Correlation device according to claim 5, characterized in that the signals corresponding to the reference image and to the scanned image are stored in at least two random access memories (40, 41, 42, 43 ), these memories being read under the control of an H _MI clock, the two line signals being read, one along Ox and the other in opposite directions, and applied to digital-analog conversion circuits (44.1, 44.2, 44.3, 44.4) and the analog signals obtained being applied to putting circuits on a carrier of frequency f (45.1, 45.2) and correlated in the analog convolver (50), that the correlation signal is applied to a demodulation circuit at the frequency f (49), that the demodulated signals are applied to analog-digital converters (55.1, 55.2), followed by a summing circuit (56) composed of a storage memory and an accumulator. 7. Correlation device according to claim 6, characterized in that the signals of the reference image and of the scanned image are stored in memory with their complex components respectively in two pairs of memories (40, 41 and 42, 43). 8. Correlation device according to claim 6 or 7, characterized in that the memories for storing the two images and the correlation lines are produced by charge transfer devices.

Images