Data processing: measuring – calibrating – or testing – Measurement system – Dimensional determination
Reexamination Certificate
2001-11-13
2003-10-28
Shah, Kamini (Department: 2863)
Data processing: measuring, calibrating, or testing
Measurement system
Dimensional determination
C382S294000
Reexamination Certificate
active
06640201
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method for comparing two-dimensional sets of points.
BACKGROUND INFORMATION
A two-dimensional set of points may be understood to mean any type of arrangement of objects or features on a plane. Methods for comparing continuous two-dimensional sets of points such as images or sections of images are known. In these methods, for example cross-correlation methods (in the original range and the frequency range) are used to find matches between a plurality of sets. These methods require a great deal of processing power, as large quantities of data must be processed; moreover, as a general rule these methods can only recognize a limited range of types of similarity. Thus, for example, if conventional cross-correlation in Cartesian coordinates is applied to two image sections, it is possible to calculate a translation vector by which one of the two images must be shifted in order to superimpose it on the second with as great a similarity as possible; however, if Cartesian cross-correlation is used, it goes unnoticed that possibly greater similarity or even identity can be achieved by deforming, compressing or rotating an image. Vice versa, if cross-correlation in polar coordinates is used, it is possible to determine whether two images can be converted into one another via compressing and rotating, but if in addition a translation is required the similarity goes unnoticed.
SUMMARY OF THE INVENTION
The present invention constitutes a method for comparing two-dimensional sets of points that makes it possible to recognize many different types of similarity with very little processing power, and makes it possible, for example, to recognize that two sets of points are identical if one can be created from the other via a combination of rotation, translation and compression or stretching. It was unanticipated that to accomplish this it is simply necessary to assign exactly one point G
i
of the second set to each point P
i
of the first set and then to solve an equation system that can be obtained in the following way: first, a transformation equation P′
i
=T(P
i
) is generated for points P
i
of the first set, transformation function T having a plurality of variable parameters a
j
, and the values of parameters a
j
for which the sum over i of the squared distances between P′
i
and G
i
assumes a minimum are determined. The values of parameters a
j
obtained in this way are used as a measure of the similarity of the sets of points. Conventional methods of analysis can be used to determine the values of parameters a
j
that are to be found.
The method is particularly easy to use if each point P
i
, G
i
respectively is represented by a complex number.
A method for comparing two-dimensional sets of points in which transformation function T is in the form of a polynomial is a preferred special case of the method according to the present invention. In this case, the values of parameters a
i
for which the sum of the squared distances apart assumes a minimum are indicated via equation system 1.
(
∑
i
G
i
P
i
n
*
⋮
∑
i
G
i
P
i
*
∑
i
G
i
)
=
(
∑
i
P
i
n
P
i
n
*
⋯
∑
i
P
i
P
i
n
*
∑
i
P
i
n
*
⋮
⋮
⋮
∑
i
P
i
n
P
i
*
⋯
∑
i
P
i
P
i
*
∑
i
P
i
*
∑
i
P
i
n
⋯
∑
i
P
i
∑
i
1
)
(
a
n
⋮
a
1
a
0
)
(
1
)
Solving linear equation systems of this kind does not present any difficulties and can be accomplished with the help of an appropriately programmed computer or microprocessor via a fully automated process.
In order to use the method for comparing images that include a continuous set of points, it is sufficient to select a number of characteristic points from each of the two images to be compared and thus to generate sets of points { . . . , P
i
, . . . }, { . . . , G
i
, . . . } to which the method according to the present invention can be applied.
The selected points may involve, for example, the eyes, ears or other pronounced points on the image of a face which may be marked by the person performing operations, or they may also be determined via a fully automated process, so that the similarity between the person shown in the image and a second image or collection of images can be determined.
Another important application is, for example, joining together partially overlapping images, in particular maps. This problem arises in particular with maps displayed electronically in modern vehicle navigation systems. Navigation systems of this kind may have a set of maps of a region in which the driver of a motor vehicle may be moving, these maps partially overlapping but not transitioning continuously into one another. If maps of this kind have been obtained from different manufacturers, there may be differences in the type of projection, the scale and the orientation, which may make it difficult for the navigation system to switch from one map sheet to another. In such cases, with the help of the method according to the present invention it is possible to select a set of pronounced points, such as road intersections on one of the maps, to select a corresponding set in a second map, and to assign each point of one set to exactly one point of the other set, a hypothesis as to which selected intersections may correspond to one another being generated, and a comparison then being carried out using the method according to the present invention. If this comparison does not yield a sufficient level of matching, a new set of points is selected in one of the maps and a new comparison is carried out, it being of course possible for the newly selected set of points to contain elements of the previous set.
Further features and advantages of the present invention are given in the description of exemplary embodiments below, with reference to the figures.
REFERENCES:
patent: 10021535 (2000-05-01), None
Pickens D.R. et al., “Digital image motion correction by spatial wrap methods”, Med. Physics vol 14(1), pp. 56-61, Jan./Feb. 1987.*
Leon W. Couch II “Digital and Analog communication” Second edition, pp. 202-221 (chapter 4, sections 4.1-4.2), book publication date 1987.
Kenyon & Kenyon
Robert & Bosch GmbH
Shah Kamini
LandOfFree
Method for comparing points sets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for comparing points sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for comparing points sets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3170311