 |
Claims  |
|
|
We claim:
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.degree., 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.degree.
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. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
The invention relates to a process for analysing 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 analysed, by the image being
subjected to a two-dimensional Fourier transformation operation and the
separated-off amplitude distribution or a distribution which can be
ascertained therefrom being compared to amplitude distributions or
distributions which can be ascertained therefrom, in respect of the
reference patterns, in the Fourier range, while determining the respective
probability of identity, the twist angle and the magnification factor as
between the reference pattern and the image content or portion.
Many areas of use call upon the function of being able to recognise or
identify two-dimensional images, for example by means of a television
camera, and being able clearly to establish the position thereof with
respect to a zero point or an axis system. Mention may be made in this
connection solely by way of example of the operation of precisely
positioning a gripping arm of an industrial robot relative to a given
article to be gripped. In accordance with the present invention, the term
two-dimensional images means two-dimensional optical images or pictures
but also two-dimensional patterns which are formed by values in
two-dimensional association, but not necessarily of optical origin, for
example two-dimensional signals in speech analysis.
The use of one-dimensional Fourier analysis for image analysis operations
is known from medical diagnostics, in particular for outline
classification of organs on X-ray pictures (outline line detection).
Besides the known methods which in the image space are based on outline
recognition processes (that is to say corner and edge recognition),
optical processes are also known in which two-dimensional Fourier
transformation operations are carried out by means of lens assemblies.
Such transformation operations provide that an image content or portion
can be determined, irrespective of its position in the image to be
analysed.
However the known optical processes suffer from major disadvantages which
hitherto prevented use thereof in a practical situation for image
analysis. Firstly, the optical system is extremely complex and costly
while nonetheless being fairly inflexible in regard to the parameters when
once set, such as for example the size of the image to be analysed.
Identification of an image content or portion irrespective of the twist
and size thereof in the image and determining the extent of the twist and
increase in size (or reduction in size) relative to a reference pattern is
in principle possible in real time, when using such optical arrangements.
In practice there is also an interest in the location (or locations) at
which the identified image portion occurs in the image. Establishing those
locations is not possible by means of optical processes in real time as a
photographic plate would be necessary in that respect, for intermediate
storage purposes. In addition, at the present time there is still no
possibility of rotating and reducing images by deliberate interference.
The object of the present invention is to provide a process of the general
kind set forth in the opening part of this specification, with which the
position of already identified image contents or portions in the image to
be analysed can be determined in real time. The invention further seeks to
provide that two-dimensional images (patterns) which are not of optical
origin can also be analysed by means of the system.
SUMMARY OF THE INVENTION
In a process of the general kind set forth in the opening part of this
specification, that is achieved in that storage and processing of the
image and the reference patterns or the Fourier transforms thereof are
effected in digital form and that to locate an image content or portion in
the original image, which is identical with a reference pattern with the
ascertained degree of probability of identity, 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 magnification 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.
By means of digital processing of the signals it is possible for the first
time for the position of the detected image contents or portions in the
image to be analysed to be ascertained in real time. The process according
to the invention makes it possible to carry out any image analysis
operations when suitable reference patterns are provided.
With the process according to the invention, any image content or portion
which is contained entirely in the plane of the image can be identified
irrespective of its position, twist, magnification, partial masking or
obstruction, while at the same time providing an independent evaluation of
the quality of identification (that is to say probability values in
respect of object identification=probability of identity). Such quality
evaluation is not adequately possible in the case of the processes which
operate only in the image plane. In addition the process according to the
invention gives the values in respect of twist and magnification relative
to a reference pattern, and the position of the identified image content
or portion in the image. A major difference in the process according to
the invention, in comparison with the known processes which are based on
corner and edge recognition, is the full functional effectiveness in
relation to partially masked edges, corner or uneven surface illumination
in respect of the images, articles or patterns to be recognised.
Disturbances and interference in outline are therefore tolerated, more
particularly to a parametrisable extent in that in the Fourier range
structural details of the image are either emphasised or faded out by
filtering.
It is possible by means of the process according to the invention to
identify and locate a plurality of reference patterns in the image. That
is also possible if a reference pattern frequently occurs in different
states of twist and magnification. Even if a reference pattern (image
content or portion) in the image occurs in the same state of magnification
and orientation (twist), the system can identify same and specifically
indicate where the individual reference patterns lie in the image.
In accordance with a further embodiment of the process according to the
invention, it is particularly desirable if the amplitude distribution of
the image, which occurs in the Fourier range, or a distribution which can
be ascertained therefrom, are ascertained in the form of a real
two-dimensional image matrix in polar coordinates, and then a
two-dimensional polar rotary extension correlation in respect of said
image matrix which is present in polar coordinates, with real reference
matrices which are also prevent in polar coordinates (amplitude
distribution or distribution in respect of the reference patterns, which
can be ascertain therefrom), in respect of stored reference patterns, is
produced 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 magnification factors of the image matrix
in relation to the reference matrices.
It is also possible however to provide for conversion of the real amplitude
matrix or a real image matrix which can be ascertained therefrom, in the
Fourier range, into a polar coordinate system with logarithmic radius
scale wherein the amplitude matrices of the reference objects or real
reference matrices which can be formed are stored in a polar coordinate
system with logarithmic radius scale whereby the rotary extension becomes
a rotary displacement or shift, whereupon a polar rotary shift correlation
operation is carried out. In that connection the term rotary displacement
or shift denotes an operation in which the rotary extension is caused to
degenerate or change insofar as the length of a radial section remains
constant, irrespective of the increase in size in the original
non-logarithmic polar coordinate system, but the section is displaced or
shifted radially, in dependence on that increase in size. A particularly
advantageous way of carrying out the first correlation operation provides
that the coordinates of the logarithmic polar coordinate system are
translated onto a right-angled axis system whereupon a discrete
two-dimensional right-angled correlation in respect of the real image
matrix with the reference matrices in the Fourier range is produced, with
the rotary extension or rotary shift being resolved into two shifts along
the axes of the axis system.
The reference patterns may already be contained in the reference storage
means form the outset but it is more advantageous if, in a learning
operation, the matrices which are present directly after the
two-dimensional Fourier transformation operation in the Fourier range are
stored, 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 the form of real or complex
reference matrices, in reference storage means, in preferably abstractly
hierarchical order.
In that connection, the term abstractly hierarchical order means the
capacity on the part of the present process, after elimination of the
parameters in respect of position, twist and magnification, independently
to form generic terms from a plurality of similar image contents in a
learning process and to store same or the Fourier transforms thereof as
reference matrices. For example it is possible for what is known as a
"standard face" which includes the features of a large number of faces to
be stored at the top in a hierarchical structure. That gives the advantage
that with the process according to the invention it is possible
immediately to decide whether the image to be analysed is a face,
whereupon further searching is performed only in low hierarchical order.
There is also the advantage that even a face which is unknown to the
system, although it cannot be identified thereby, can be at least
recognised as such.
It is in principle possible that, in order to ascertain the position or
positions of an image content or portion in the original image plane,
which is recognised in the Fourier plane with a certain degree of
probability of identity with a rotary-extension reference pattern, the
reference pattern which has been subjected to inverse rotary extension
with the ascertained values in respect of twist angle and magnification
factor, in said image plane, is compared to the image to be analysed and
the maximum or maxima in respect of identity is or are detected.
As the complex matrices of the actual image and the reference pattern
already occur in the Fourier plane, in accordance with a further
development of the process according to the invention it is particularly
advantageous, in determining the coordinate values for the position of the
actual image content or portion in the image, to make use of the
correlation theorem (convolution theorem) thereby considerably reducing
the number of computing steps. That is effected in that, in order to
ascertain the position or positions of an image content or portion in the
original image plane, which is recognised in the Fourier plane with a
certain degree of probability of identity with a rotary-extension
reference pattern, the complex reference matrix which is subjected to
inverse rotary extension with the ascertained values in respect of twist
angle and magnification factor is multiplied in a conjugated complex and
element-wise manner by the complex image matrix in the Fourier range
whereupon the complex product matrix is subjected to a two-dimensional
Fourier back-transformation operation, and finally the maximum (or maxima)
of the identity probability matrix obtained as a result of that
correlation operation is or are detected and the coordinate value
associated with said maximum (or maxima) are ascertained for the position
or positions of the recognised image content or portion in the original
image.
It is even more advantageous, also when using the convolution theorem, if,
when employing semi-logarithmic polar coordinates the inverse rotary
extension of the complex reference matrix is performed by inverse integral
dispacement with respect to the logarithmic polar coordinates, whereupon
the resulting matrix is subjected to coordinate conversion, by constantly
associated reverse interpolation, to Cartesian coordination. In that
alternative embodiment, care is taken in particular to avoid
non-constantly associated interpolation effects. More specifically, for
rotary extension of a matrix (in the present case, inverse rotary
extension), by way of a Cartesian grid, it is necessary to have an
interpolation effect which is dependent on the extent of the respective
rotary extension as the elements obtained after the rotary extension step
do not generally lie over grid points on the Cartesian grid.
By virtue of the above-mentioned embodiment, rotary extension can be
performed, in logarithmic polar coordinates, in the form of a shift or
displacement, more particularly without substantial limitation to integral
grid spacings in the logarithmic polar coordinates (that is to say without
interpolation). Reverse interpolation of the matrix which is subjected to
extension in that way, to Cartesian coordinates is admittedly still
necessary but, as the Cartesian and polar grids are constantly fixed
relative to each other, it can be taken from a schedule, which
considerably reduces the computing expenditure.
The only ambiguity which is still to be found, in twist of the article
through 180.degree. (the amplitude distribution or a distribution which
can be ascertained therefrom has a periodicity of 180.degree. in the
Fourier plane) can be eliminated by a further inverse rotary extension
operation being performed, with the ascertained value changed through
180.degree. for the twist angle and the ascertained value in respect of
the magnification factor, whereupon after the correlation operation has
been carried out, any maxima in respect of probability of identity that
may be present are detected.
In order reliably to avoid incorrect correlation results in the event of
missing surface structuring of the images, in a further embodiment of the
invention it can be provided that both the real reference matrix which is
subjected to inverse rotary extension with the ascertained value in
respect of the twist angle or that value which has been changed through
180.degree. and also the real image matrix of the actual image, which is
present after the two-dimensional Fourier transformation operation, are
passed by way of respective contour-accentuating O-phase filters before
they are subjected to the conjugated complex multiplication operation,
together with the associated phase matrices. Such a contour-accentuating
O-phase filter accentuates for example the elements of the amplitude
matrix linearly with frequency, whereby higher frequencies (which in fact
originate from edges and corners) are valued more highly.
The invention will now be described in greater detail by means of an
embodiment with reference to the accompanying drawings in which:
BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 shows a block circuit diagram of an embodiment of a system for
carrying out the process according to the invention,
FIGS. 2A through 6H show picture screen representations of the image
distributions in the image plane and in the Fourier range, which occur in
various stages of the process according to the invention,
FIG. 7 shows a block circuit diagram of a further embodiment of a system
for carrying out a process according to the invention, and
FIG. 8 is a one-dimensional section in the radial direction through spatial
frequency spectra, represented in logarithmic polar coordinates, in the
Fourier range.
As shown in FIG. 1, the process according to the invention may be carried
into effect by the successive interconnection of signal and
matrix-processing stages. In general terms, in FIG. 1 the
signal-processing stages have the top right corner cut off while all other
stages represent storage means (that is to say matrix storage means) or
intermediate storage means.
Firstly the television image signal from a television camera 1 or another
two-dimensional pattern formed by values in two-dimensional association is
stored in an input intermediate storage means 2 and then subjected in
stage 3 to a two-dimensional Fourier transformation operation. Instead of
the camera 1 it is also possible to use a synthetic image or pattern
generator or for example a matrix of crossed wires with certain electrical
or magnetic potentials at the points of intersection.
In the case of a television image or picture the amplitude corresponds to
brightness in the respective points of the television picture or image. An
axis system: x/y is associated with the image in that image plane. The
amplitude values can then be written in the form of a matrix A (M,N)
wherein M/N corresponds to the number of grid points in the respective
x/y-directions. It is also possible to use the form of expression M (x,y)
selected in FIG. 1, for the matrix in the x,y plane: for the specific
article detection process the position of the sensitivity window of a
camera which possibly represents an image on the spectral frequency axis
is immaterial (infra-red image, night-vision image, . . . ).
However besides television images it is also possible to use all other
two-dimensional amplitude value images or patterns which have image
contents or portions, for example a given article or object such as a
triangle or a letter. As an example in that respect, mention may also be
made of a time-frequency band representation (vocoder) of a speech signal
where amplitude values are plotted in an orthogonal frequency-time axis
system.
In the case of a television image, it is necessary for it to be filed in an
intermediate storage means 2 (individual image freezing).
The representation of the two-dimensional Fourier transformation operation
reads as follows, in the continuous case:
##EQU1##
while in the discrete case it is as follows:
##EQU2##
F (u,v) represents the complex spectrum and comprises the two real matrices
A (u,v) . . . , real amplitude spectrum and .phi. (u,v) . . . real phase
spectrum. Besides that breakdown into amplitude spectrum and phase
spectrum, if necessary it is also possible to provide for breakdown of the
complex spectrum into real and imaginary sub-matrices.
The result of that two-dimensional Fourier transformation operation is
stored in the intermediate storage means 4 for the amplitude matrix of the
actual image or article or pattern and 5 for the phase matrix of said
image or article or pattern.
The following consideration can be applied to fix the section in the
Fourier plane (u/v-plane):
The greatest spatial frequency occurring corresponds to a O/1-succession of
grid amplitude to adjacent grid amplitude:
##EQU3##
The lowest frequency obtained is of a wavelength of
##EQU4##
wherein w.sub.min =1, that is to say one oscillation per N and M
respectively.
On the basis of the condition F(-u,-v)=F*(u,v) the matrix height of both
matrices can be halved without loss of information (except the zero line).
The characteristics of that discrete two-dimensional Fourier transformation
operation are:
The amplitude matrix is image content-position invariant, that is to say
one and the same picture content can be displaced as desired (in the
x/y-plane) without the amplitude spectrum or the amplitude matrix changing
(in the u/v-plane) (see FIGS. 2A-2D).
An increase in size in the image plane (x/y-plane) corresponds to a
proportional reduction in size of the amplitude pattern or amplitude
matrix in the Fourier plane (u/v-plane; see FIGS. 2A-2D and FIGS. 3A-3D).
(It will be appreciated that the phase matrix is also proportionally
reduced in size).
A twist or rotation in the image plane (x/y-plane) corresponds to a twist
or rotation to the same extent and in the same direction in the Fourier
plane (u/v-plane; see FIGS. 3A-3D and FIGS. 4A-4D).
That information is illustrated by FIGS. 2A-4D reproducing expressed screen
image representations (amplitude represented as blackening). Thus FIG. 2A
and FIG. 2B show two position-displaced image contents M (x,y) in the
original image plane (x/y-plane). FIGS. 2C and 2D show the respectively
associated amplitude matrices A (u, v) after carrying out the
two-dimensional Fourier transformation operation, as are represented in
the intermediate storage means 4 in the u/v-plane. It will be seen that
the representations in FIGS. 2C and 2D are identical, that is to say the
positional shift in the x/y-plane has no influence on the amplitude matrix
in the u/v-plane (positional invariance).
FIGS. 3A and 3B show the same rectangle M (x,y) in the x/y-plane as FIG.
2A, but increased in size by the factor 2, while in addition in FIG. 3B
the rectangle is turned or twisted relative to the rectangle in FIG. 3A,
in the x/y-plane. FIGS. 3C and 3D show the amplitude matrices A (u,v)
associated with the image contents (rectangles) of FIGS. 3A and 3B,
wherein a comparison between FIGS. 2A and 3A on the one hand and FIGS. 2C
and 3C on the other hand shows the inversely proportional increase in size
(that is to say reduction) in the image in the u/v-plane relative to the
image in the x/y-plane; from a comparison between FIGS. 3A and 3B on the
one hand and FIGS. 3C and 3D on the other hand, there directly follows the
equivalent twist or rotation of the amplitude matrix in the u/v-plane upon
image rotation in the x/y-plane, more particularly by the same angle of
rotation in each of the two planes.
FIGS. 4A-4D show a realistic representation of the straight and the twisted
or turned rectangular bar shown in FIGS. 3A and 3B together with
transformation into the u/v-plane, that representation corresponding to
the image produced by a video camera (edge smoothing). The amplitude
matrices A (u,v) shown in FIGS. 4C and 4D, which are derived from the
images in FIGS. 4A and 4B, particularly in the twisted or turned situation
(FIG. 4D), no longer suffer from the edge disturbances which occur in FIG.
3D (due to successively sharp edge rastering in FIG. 3B). As in the
continuous case, the following addition and linearity theorem also applies
in the case of discrete Fourier transformation, in the complex mode:
F(A.sub.1 +A.sub.2)=F(A.sub.1)+F(A.sub.2),
F(c.multidot.A.sub.1)=c.multidot.F(A.sub.1)
In the pattern of the amplitude matrix of the u/v-plane the two search
dimensions "position in the x-direction" and "position in the y-direction"
are separated off (they are contained exclusively in the .phi.-matrix)
while article identification, determination of size (which can optionally
be interpreted directly as distance or range) and determination of twist
or rotation can be hereafter ascertained without reduction in quality even
in regard to a plurality of article patterns which are displaced in any
fashion.
Of the five search dimensions article identity (identity of an image
content or portion), magnification (possibly corresponding to distance),
twist, position in the x-direction and position in the y-direction, the
first three parameters can now be completely separated from the last two
and determined in a decoupled manner.
The Fourier transformation operation also provides that local disturbances
in the image plane produce effects solely in the amplitude values at
higher frequencies. For example the amplitude matrices of two equally
proportional, equally turned and equally large rectangles of which one has
rounded corners differ only at the higher frequencies.
When illustrated in the x/y-plane, corresponding to discrete Fourier
transformation is the breakdown of a pattern which is in the x/y-plane,
into transverse sources which pass over the image with different
amplitudes, frequencies and directions of movement, and produce the image
by the summing thereof. The directions of movement all occur in a grid of
point-to-point connections which can be drawn in. All combinations of the
fundamental wave and harmonics which are perpendicular to each other occur
at frequencies. Now, the amplitude spectrum or matrix which is being
analysed, possibly containing a plurality of any articles which suffer
disturbance (for example in the case of a workpiece, those with partially
masked or damaged edges), is to be compared by means of rotary extension
with the amplitude spectra or matrices of the reference objects,
previously stored in the reference storage means 6, 7 and 10 respectively.
In order to be able to carry out that comparison operation, advantageously
a transformation operation for transforming the orthogonal amplitude
matrix into a polar matrix is firstly carried out, a logarithmic scale
being selected for the radius. As a result increase/reduction in size of
an article degenerate in the image space into a shift or displacement
(computing cursor effect). That transformation operation is carried out in
the conversion stage 8 in accordance with the following formulae:
##EQU5##
Then a discrete two-dimensional right-angled correlation is effected in
respect of the amplitude matrix contained in the intermediate storage
means 9 in logarithmic polar coordinates, with the reference amplitude
matrices which can be selected from the reference storage means 10,
wherein the identity probability matrix or correlation matrix
K(x,y)=A.sub.1 .circle. A.sub.2
(x,y)=.SIGMA..sub.x',.SIGMA..sub.y',A.sub.1 (x'-x,y'-).multidot.A.sub.2
(x',y') is ascertained.
That correlation step is carried out in the correlation stage 11 whose
inputs receive the amplitude matrix A (r.sub.1,.alpha.), represented in
logarithmic polar coordinates r.sub.1, .alpha., of the actual image
detected by the camera 1, from the intermediate storage means 9, and a
selectable amplitude matrix A.sub.Ref.spsp.1 (r.sub.1,.alpha.),
A.sub.Ref.sbsb.2 (r.sub.1,.alpha.) . . . which is also represented in
logarithmic polar coordinates r.sub.1, .alpha., from the reference storage
means 10.
As already stated, comparison in respect of magnification becomes a
comparison in respect of displacement or shift, as a result of the
logarithmic radius scale, wherein the twist angle .alpha. of the article,
in the original x/y-plane, is not influenced.
If the logarithmic polar coordinates are plotted on a right-angled
coordinate system (see for example FIGS. 6E-6G which will be described in
greater detail hereinafter), the rotary extension or rotary shift of the
reference amplitude matrix, which is to be performed in the correlation
operation, degenerates into two linear shifts or displacements along the
r.sub.1 - and .alpha.-axes. Therefore each twist-magnification comparison
(rotary extension) becomes a shift comparison (computing cursor effect).
Instead of the amplitude matrices A(r.sub.1,.alpha.) and A.sub.Ref.sbsb.1
(r.sub.1 .alph | | |
