Pattern recognition process

• US 4,843,631 A
• Filed: 08/13/1987
• Issued: 06/27/1989
• Est. Priority Date: 12/20/1985
• Status: Expired due to Fees

• Current Assignee: Dietmar Steinpichler, Gerhard W. Sterreicher
• Original Assignee: Dietmar Steinpichler, Gerhard W. Sterreicher
• Inventors: sterreicher, Gerhard W., Steinpichler, Dietmar
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/098,621
• Time in Patent Office: 684 Days
• Field of Search: 364/576, 364/726, 364/827, 382/1, 382/10, 382/17, 382/31, 382/34, 382/39, 382/41-43, 382/48, 381/41-43
• US Class Current: 382/280
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A process for analyzing a two-dimensional image, wherein the structural identity of stored reference patterns with image contents or portions is determined, irrespective of the position of said image content or portion in the image to be analyzed. The image is subjected to a two-dimensional Fourier transformation operation and the separated amplitude distribution or power distribution is compared to amplitude or power distributions in respect of the reference patterns in the Fourier range, while determining the respective probability of identity, the twist angle and the enlargement factor as between the reference pattern and the image content or portion. Storage and processing of the image and the reference patterns or the Fourier transforms thereof are effected in digital form. In order to locate an image content or portion in the original image, which is identical with a reference pattern, the respective reference pattern or the Fourier transform thereof is assimilated to said image content or portion, in respect of size and orientation, by inverse rotary extension, with the ascertained twist angle and enlargement factor, and finally the position or positions at which the reference pattern when converted in that way has maximum identity with a section of the image is established.

Claims

1. A method for analyzing a two dimensional image in an original image plane, for the purpose of determining a probability of identity, a twist angle, and an enlargement factor, between known reference patterns and contents or portions of the image, irrespective of at what position or positions of the image to be analyzed the contents or portions of the image are located, comprising;

storing and processing the image to be analyzed in digital form;

subjecting the stored image to a two-dimensional Fourier transformation operation to generate a Fourier transform of the image;

determining a separated-off amplitude distribution or another amplitude distribution which can be ascertained from said separated-off amplitude distribution of said Fourier transform of the image;

comparing, in a Fourier range, said separated-off amplitude distribution, or said other amplitude distribution, to separated-off amplitude distributions or other amplitude distributions which can be determined therefrom of the reference patterns which are stored digitally;

ascertaining the respective probability of identity, the twist angle and the enlargement factor as between the reference pattern and the image content or portion;

locating an image content or portion in the image which is identical with a stored reference pattern with the ascertained degree of probability of identity by assimilating the reference pattern, or the Fourier transform of the reference pattern, to the image content or portion in respect of size and orientation by inverse rotary extension with said ascertained twist angle and enlargement factor and by then establishing the position or positions at which the reference pattern, when converted by inverse rotary extension, has maximum identity with a section of the image being analyzed.

2. The method according to claim 1 wherein the amplitude distribution of the image, which has been acertained from the Fourier transform of the image, or a distribution which can be ascertained therefrom, is determined in the form of a real two-dimensional image matrix in polar co-ordinates, and then a two dimensional polar rotary extension correlation in respect of said real two-dimensional image matrix which is stored in polar coordinates, with real reference matrices which are also stored in polar co-ordinates, said real reference matrices representing amplitudes distribution or distribution which can be ascertained therefrom, in respect of the reference patterns, is carried out, as a result of which matrix values are obtained for probabilities of identity in respect of the correlated real image and reference matrices with associated twist angles and enlargement factors of the image matrix in relation to the reference matrices said matrix values being stored to form a correlation matrix having at least one maximum, each of said at least one maximum having a relative degree of steepness.

3. The method according to claim 1 further comprising the steps of:

forming a real power matrix in semi-logarithmic polar co-ordinates from a complex matrix having real and imaginary components which is present after the two-dimensional Fourier transformation operation, by formation of an absolute square, wherein to form the real power matrix in preferably semi-logarithmic polar co-ordinates, firstly the real portion and the imaginary portion of the complex matrix undergo co-ordinate conversion in themselves by constantly associated interpolation to preferably semi-logarithmic polar co-ordinates, whereupon the power matrix is ascertained by squaring of the real and imaginary portions and then addition; and

comparing said real power matrix to similarly formed and stored real power matrices of the reference patterns.

4. The method according to claim 2 further comprising the steps of:

detecting said at least one maximum of the correlation matrix obtained as a result of the correlation operation; and

storing values associated with said at least one maximum, for twist angle and enlargement factor associated with the inverse rotary extension operation or operations which are applied to the respective reference pattern in order to achieve a relative identity of the image with the respective reference patterns.

5. The method according to claim 3 wherein a Fourier transform of the two-dimensional image matrix is ascertained in a logarithmic polar co-ordinate system with a logarithmic radius scale and Fourier transforms of reference matrices of the reference patterns, are stored in a logarithmic polar co-ordinate system with a logarithmic radius scale whereby the rotary extension becomes a rotary shift, whereupon a polar rotary shift correlation operation is carried out.

6. The method of claim 5 wherein the co-ordinates of the logarithmic polar co-ordinate system are translated on to a right angled axis system whereupon a discrete two-dimensional right-angled correlation operation is carried out in respect of the Fourier transforms of the real two-dimensional image matrix with the Fourier transform of the reference matrices, with the rotary extension or rotary shift being resolved into two shifts along the axes of the axes system.

7. The method according to claim 6 wherein, in a learning operation, the method further comprises the step of:

storing the Fourier transforms of the two-dimensional image matrix and of the reference matrices which have been generated from the two-dimensional Fourier transformation operation in the form of complex matrices or separate amplitude and phase matrices by inputting or reading in known reference images, preferably by way of an input intermediate storage means, in preferably abstractly hierarchical order.

8. The method according to claim 7 wherein, in a learning operation, the method further comprises the step of:

storing amplitude matrices which have been generated from the two-dimensional Fourier transformation operation, or image matrices which can be ascertained therefrom, preferably in polar co-ordinates by inputting or reading in known reference images, preferably by way of an input intermediate storage means, in the form of real reference matrices, in reference storage means, in preferably abstractly hierarchical order.

9. The method according to claim 8 further comprising the step of:

correlating the amplitude distribution which is stored in the form of an image matrix, or a distribution which can be ascertained therefrom, in respect of the image, and the amplitude distribution which is stored in the form of a reference matrix, or a distribution which can be ascertained therefrom, in respect of the reference pattern, in the Fourier range by the real image matrix and the real reference matrix each being subjected to a respective further two-dimensional Fourier transformation operation to generate a complex reference matrix and a complex image matrix, and the resulting complex matrices being multiplied together in an element-wise conjugated complex mode, and the product matrix thereupon being subjected to reverse Fourier transformation.

10. The method according to claim 9 wherein to establish the position or positions of an image content or portion, in the original image plane, which content or portion is detected in the Fourier plane with a given degree of probability of identity with a rotary-extended reference pattern, the reference pattern, which is subjected to inverse rotary extension with the ascertained values in respect of twist angle and enlargement factor, in said image plane with the image to be analyzed the identity maximum or maxima is or are detected.

11. The method according to claim 9 wherein to establish the position or positions of an image content or portion, in the original image plane, which content or portion is ascertained in the Fourier plane with a given degree of probability of identity with a rotary-extended reference pattern, the complex reference matrix which is subjected to inverse rotary extension with the ascertained values in respect of twist angle and enlargement factor is multiplied in conjugated complex and element-wise mode with the complex image matris in the Fourier range to generate a complex product matrix whereupon the complex product matrix is subjected to a two-dimensional Fourier reverse transformation operation and that finally said at least one maximum of the correlation matrix as a result of that correlation operation are detected and co-ordinate values which are associated with said at least one maximum are ascertained for the position or positions of the located image content or portion in the original image.

12. The method according to claim 11 wherein, when using semi-logarithmic polar co-ordinates, the inverse rotary extension of the complex matrix is performed by inverse integral displacement with respect to the logarithmic polar co-ordinates being used whereupon the resulting matrix is subjected to co-ordinate conversion by constantly associated reverse interpolation to Cartesian co-ordination.

13. The method according to claim 10 further comprising the step of:

carrying out a further inverse rotary extension or rotary shift (in relation to logarithmic polar co-ordinates) with the ascertained value, which is altered through 180°

, in respect of the twist angle, and the acertained value in respect of the enlargement factor, whereupon after the correlation operation has been carried out any maxima in respect of probability of identity that may be present can be detected.

14. The method according to claim 11 further comprising the step of:

Passing, by way of respective contour-accentuating O-phase filters, both the real reference matrix which is subjected to inverse rotary extension with the ascertained value in respect of the twist angle or with the ascertained value with respect to twist angle changed through 180° and

also the real image matrix of the image to be analyzed, before they are multiplied in conjugated complex and element-wise mode, together with the associated phase matrices.

15. The method according to claim 11 further comprising the step of:

multiplying in the Fourier Range the complex reference matrix which has been subjected to inverse rotary extension and the complex image matrix, before their conjugatedly complex multiplication, in an element-wise manner respectively with a contour-accentuating real O-phase filter matrix with an underlying Fourier co-ordinate system having an origin, said filter matrix having elements which increase in value as their distance from the origin of the underlying Fourier co-ordinate system increases.

16. The method according to claim 15 wherein for the purposes of classification of pattern similarity, the relative degrees of steepness of said at least one maximum of said correlation matrix are used.

17. The method according to claim 16 further comprising the step of:

ascertaining the relative degrees of steepness of the correlation maxima of the correlation matrix, by converting the correlation matrix to a logarithmic equivalent and subjecting the logarithmic equivalent to two-dimensional Fourier transformation to generate a two dimensional spectrum whereupon the two-dimensional spectrum is multiplied preferably by an O-phase filter in an element-wise manner by the distance of the respective pair of Fourier elements from the origin of the underlying Fourier co-ordinate system, and then said two-dimensional spectrum is subjected to a Fourier reverse transformation operation to generate a new spectrum matrix having amplitude maxima, the amplitude maxima of the new spectrum matrix obtained in that manner being a direct measurement in respect of the relative steepness of the correlation maxima of the correlation matrix.

18. The method according to claim 17 further comprising the step of:

setting elements of the real reference matrices which are below a given value to zero for better separability with a high foreign structure component in the image to be analyzed.

19. The method according to claim 18, when using a polar co-ordinate system in the Fourier range made up of radial and angular co-ordinates, to produce a quasi-periodicity in the direction of the radial co-ordinates for subsequent correlation in a window between two radial co-ordinates, further comprising the step of:

setting to zero values which are above a given radial co-ordinate, in respect of the real reference matrix, while in the real image matrix in the Fourier range, still real values are entrained at greater radial co-ordinates which values correspond to higher spatial frequencies or said values are also set to zero.

20. The method according to claim 19, for equal evaluation of different spatial frequency components, further comprising the step of:

accentuating linearly the elements of the amplitude matrices of the image to be analyzed and the reference patterns with the spatial frequency or accentuating quadratically the elements of the corresponding power matrices with the spatial frequency, preferably by an O-phase filter, before they are correlated with each other.