GB1570070A - Arrangement for correlating pictures - Google Patents

Description

(54) IMPROVEMENTS IN OR RELATING TO ARRANGEMENT FOR CORRELATING PICTURES (71) We, E M I LIMITED, a British company of Blyth Road, Hayes, Middlesex, do hereby declare the invention, for which we pray that a patent may be granted to us, and the method by which it is to be performed, to be particularly described in and by the following statement: The present invention relates to arrangements for correlating pictures, each representing views of a continuous scene, to determine the value of relative displacement between the views.

For various purposes, such as the alignment of partially overlapping maps or following moving obiects, it may be desirable to compare successive pictures, representing a scene, to determine movement of a chosen object in the scene, or part of the scene, in the time elapsed between the two pictures. It is usual to achieve this effect by dividing the pictures into individual picture elements, such as is usually achieved in practice by the form of the picture information, to move the two scenes by several relative displacements and to correlate the data for corresponding picture elements of the two pictures to determine that displacement for which the correlation gives a maximum. A common correlation technique is the so-called cross correlation in which, in effect, a sum is obtained, over chosen region of the pictures, of the products of the amplitudes of the signals for corresponding elements.

It has been proposed (Kuglin and Hiner, Lockheed Report LMSC-D356260, Lockheed Missile and Space Company, (California USA)) to achieve the correlation by an alternative method known as "phasecorrelation". As in the cross-correlation technique, the input data represents overlapping images, g, and g2, of NxN picture elements. Act wording to the technique two-dimenzional Fourier transforms, G1 and G2, of the two images are determined and the magnitudes of each term of the transforms are set to unity. This leaves matrices of the phase contributions only C, for one matrix and 02 for the other.

From this a phase difference matrix D=ei 2) is constructed, D being defined as 1 2 IG1llG21 where the asterisk indicates the complex conjugate. This matrix is then subjected to inverse Fourier transformation to give a final matrix d=F-'[Dl. It should be noted that all of the parameters given hereinbefore are functions of spatial frequencyfin two dimensions. A peak value in 'd' is then indicative of a relative displacement of the two pictures.

It is, however, a potential defect in the procedure that the process can be strongly influenced by any noise present in regions in transform space for which the 'signal' to noise ratio is poor, the signals being those representing the magnitudes of each term of the Fourier transforms G1 and G2 It is an object of the invention to provide a method of reducing that disadvantage.

According to the invention, there is provided a correlation arrangement for correlating two pictures, representing overlapping scenes each comprising a matrix of individual picture elements, including a signal processing means which has an input arrangement for receiving signals representing the pictures, and which is arranged to determine the two dimensional Fourier transforms of the two pictures, to suppress those terms in each of the transforms for which the magnitudes of the terms are below respective threshold values, to determine a phase difference matrix indicative of the differences between the phases associated with corresponding unsuppressed terms of the transforms, to determine the inverse Fourier transform of the matrix, and to detect a peak in the inverse transform to provide an indication of the relative displacement of the two pictures.

In order that the invention may be clearly understood and readily carried into effect, an example thereof will now be described with reference to the accompanying drawing which shows in block diagrammatic form a circuit using the invention.

It has been mentioned hereinbefore that noise in the picture transform signals affects correlation in regions in which the signal amplitude (in G1 and/or G2) is small. In the arrangement of this invention, therefore, areas in G, and G2 containing signals below a certain level are identified and the corresponding signals suppressed. Different methods of achieving this may be used as desired.

In one example the values of the elements of the transform matrices G for each point of each spectrum are used to derive a histogram of the amplitude of each spectrum for this purpose a range of possible levels is divided into M sub-ranges and a 'l' is added to an accumulator for the sub range corresponding to each picture element amplitude. This gives N2 counts for each G.

Respective threshold amplitudes T1 and T2 are then determined for G1 and G2. T1 and T2 may correspond to (an amplitude value below which there is) a preset fraction of the total count in the histogram or any other suitable factor.

Using the values of Tr and T2 the transform d is processed from the matrices G1 and G2 (which have elements Guk and G2jk) in which any element havmg a magnitude less than the threshold associated with that matrix is suppressed: i.e. elements for which mod G1,k < T1 and mod G2jk < T2 are suppressed.

Alternatively a histogram of the products of the moduli of the corresponding elements of the matrices G1 and G2 may be formed to give a threshold T2 for similar suppression.

If the noise level may be estimated in advance of the correlation T1 and T2 (or T2) may be preset to a suitable factor above the noise level. This may be applied even if the noise is not uniformly distributed by storing profiles of T1 and T2 (or T2) for the spectra.

For applications in which the scene changes slowly the threshold pattern for suppressions of low 'signals' in transform space only changes slowly. The computation of parts to be suppressed need not, therefore, be carried out for each correlation but could be updated at suitable intervals.

A block diagrammatic circuit for one example of the invention is shown in the Figure. Data from a sensor 1 is applied to an analogue-digital converter (A-D) 2 and also to a control microprocessor 3. Control processor 3, receiving data concerning the status of the input, usually video, information, is able to control the operation of the other units to be described, via connections not shown. The digitised signals are then passed to a fast Fourier transform (FFT) unit 4, of known type, for the computation of a Fourier transform of each picture.

A reference picture transform is stored in a store 5 and each further incoming picture transform in a store 6. The reference picture transform may be updated in several ways.

For example it may be updated at predetermined intervals, when the finally determined displacement reaches a predetermined level or with each incoming picture transform after it has been used for comparison. The transforms 5 and 6 are applied to respective suppression circuits 13 and 12 and to respective histogram accumulator circuits 8 and 9. The histograms accumulated in each of 8 and 9 are the amplitudes of each of the terms of the Fourier transforms G1 and G2 and from these the threshold calculator circuits 10 and 11 evaluate the threshold T1 and T2 according to one of the methods mentioned hereinbefore. The values of T1 and T2 are applied to the suppression circuits 12 and 13 for suppression of those terms in the Fourier transforms whose amplitudes are below the thresholds for the respective transforms.

The 'thinned out' transforms are then applied to the phase matrix processor, 7, for calculation of the phase difference matrix, D, according to the method as described in the said report, the method of calculating D including setting the magnitudes of the unsuppressed terms of the transforms to unity.

The matrix D is applied to the inverse fourier transform circuit, 14, and the output from 14 is applied to the peak detector, 15, for detecting a peak or a highest peak which corresponds to the relative displacement of the two original pictures and is output therefrom.

It will be understood that other arrangements for achieving the effects described hereinbefore may be devised using processing method well known to those skilled in the art. Furthermore although only single connections have been shown in the processing channel it will be clear that the signals should be considered when appropriate to be of complex form having in-phase and quadrature or amplitude and phase components.

WHAT WE CLAIM IS: 1. A correlation arrangement for correlating two pictures, representing overlapping scenes each comprising a matrix of individual picture elements, including a signal processing means which has an input arrangement for receiving signals representing the pictures, and which

**WARNING** end of DESC field may overlap start of CLMS **.

Claims (5)

**WARNING** start of CLMS field may overlap end of DESC **. understood and readily carried into effect, an example thereof will now be described with reference to the accompanying drawing which shows in block diagrammatic form a circuit using the invention. It has been mentioned hereinbefore that noise in the picture transform signals affects correlation in regions in which the signal amplitude (in G1 and/or G2) is small. In the arrangement of this invention, therefore, areas in G, and G2 containing signals below a certain level are identified and the corresponding signals suppressed. Different methods of achieving this may be used as desired. In one example the values of the elements of the transform matrices G for each point of each spectrum are used to derive a histogram of the amplitude of each spectrum for this purpose a range of possible levels is divided into M sub-ranges and a 'l' is added to an accumulator for the sub range corresponding to each picture element amplitude. This gives N2 counts for each G. Respective threshold amplitudes T1 and T2 are then determined for G1 and G2. T1 and T2 may correspond to (an amplitude value below which there is) a preset fraction of the total count in the histogram or any other suitable factor. Using the values of Tr and T2 the transform d is processed from the matrices G1 and G2 (which have elements Guk and G2jk) in which any element havmg a magnitude less than the threshold associated with that matrix is suppressed: i.e. elements for which mod G1,k < T1 and mod G2jk < T2 are suppressed. Alternatively a histogram of the products of the moduli of the corresponding elements of the matrices G1 and G2 may be formed to give a threshold T2 for similar suppression. If the noise level may be estimated in advance of the correlation T1 and T2 (or T2) may be preset to a suitable factor above the noise level. This may be applied even if the noise is not uniformly distributed by storing profiles of T1 and T2 (or T2) for the spectra. For applications in which the scene changes slowly the threshold pattern for suppressions of low 'signals' in transform space only changes slowly. The computation of parts to be suppressed need not, therefore, be carried out for each correlation but could be updated at suitable intervals. A block diagrammatic circuit for one example of the invention is shown in the Figure. Data from a sensor 1 is applied to an analogue-digital converter (A-D) 2 and also to a control microprocessor 3. Control processor 3, receiving data concerning the status of the input, usually video, information, is able to control the operation of the other units to be described, via connections not shown. The digitised signals are then passed to a fast Fourier transform (FFT) unit 4, of known type, for the computation of a Fourier transform of each picture. A reference picture transform is stored in a store 5 and each further incoming picture transform in a store 6. The reference picture transform may be updated in several ways. For example it may be updated at predetermined intervals, when the finally determined displacement reaches a predetermined level or with each incoming picture transform after it has been used for comparison. The transforms 5 and 6 are applied to respective suppression circuits 13 and 12 and to respective histogram accumulator circuits 8 and 9. The histograms accumulated in each of 8 and 9 are the amplitudes of each of the terms of the Fourier transforms G1 and G2 and from these the threshold calculator circuits 10 and 11 evaluate the threshold T1 and T2 according to one of the methods mentioned hereinbefore. The values of T1 and T2 are applied to the suppression circuits 12 and 13 for suppression of those terms in the Fourier transforms whose amplitudes are below the thresholds for the respective transforms. The 'thinned out' transforms are then applied to the phase matrix processor, 7, for calculation of the phase difference matrix, D, according to the method as described in the said report, the method of calculating D including setting the magnitudes of the unsuppressed terms of the transforms to unity. The matrix D is applied to the inverse fourier transform circuit, 14, and the output from 14 is applied to the peak detector, 15, for detecting a peak or a highest peak which corresponds to the relative displacement of the two original pictures and is output therefrom. It will be understood that other arrangements for achieving the effects described hereinbefore may be devised using processing method well known to those skilled in the art. Furthermore although only single connections have been shown in the processing channel it will be clear that the signals should be considered when appropriate to be of complex form having in-phase and quadrature or amplitude and phase components. WHAT WE CLAIM IS:

1. A correlation arrangement for correlating two pictures, representing overlapping scenes each comprising a matrix of individual picture elements, including a signal processing means which has an input arrangement for receiving signals representing the pictures, and which

is arranged to determine the two dimensional Fourier transforms of the two pictures, to suppress those terms in each of the transfoms for which the magnitudes of the terms are below respective threshold values, to determine a phase difference matrix indicative of the differences between the phases associated with corresponding unsuppressed terms of the transforms, to determine the inverse Fourier transform of the matrix, and to detect a peak in the inverse transform to provide an indication of the relative displacement of the two pictures.

2. An arrangement according to Claim 1, wherein the signal processor means is arranged to determine the threshold values from the magnitudes of the terms of the Fourier transforms.

3. An arrangement according to Claim 1, wherein the signal processing means comprises a Fourier transform for determining the transforms of the two pictures, means for storing the terms of the transforms of the two pictures, means for suppressing those terms in each of the stored transforms for which the magnitudes are below respective threshold values, means for forming a phase difference matrix indicative of the differences between the phases associated with corresponding unsuppressed terms of the transforms, means for determining the inverse Fourier transform of the matrix, and means for detecting a peak in the inverse transform to provide an indication of the relative displacement of the two pictures.

4. An arrangement according to Claim 3, wherein the signal processing means comprises means for determining from the magnitudes of the terms of the stored transforms the respective threshold values.

5. A correlation arrangement substantially as hereinbefore described with reference to the accompanying drawing.