Method for comparing points sets

[0002] The present invention relates to a method for comparing two-dimensional sets of points.

[0003] 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.

[0004] 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_iof the second set to each point P_iof 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_iof the first set, transformation function T having a plurality of variable parameters a_j, and the values of parameters a_jfor which the sum over i of the squared distances between P′_iand G_iassumes a minimum are determined. The values of parameters a_jobtained 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_jthat are to be found.

[0005] The method is particularly easy to use if each point P_i, G_irespectively is represented by a complex number.

[0006] 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_ifor which the sum of the squared distances apart assumes a minimum are indicated via equation system 1. $\begin{array}{cc}\left(\begin{array}{c}\sum _i{G}_i{P}_i^{n*}\\ ⋮\\ \sum _i{G}_i{P}_i^{*}\\ \sum _i{G}_i\end{array}\right)=\left(\begin{array}{cccc}\sum _i{P}_i^n{P}_i^{n*}& \cdots & \sum _i{P}_i{P}_i^{n*}& \sum _i{P}_i^{n*}\\ ⋮& & ⋮& ⋮\\ \sum _i{P}_i^n{P}_i^{*}& \cdots & \sum _i{P}_i{P}_i^{*}& \sum _i{P}_i^{*}\\ \sum _i{P}_i^n& \cdots & \sum _i{P}_i& \sum _{i}1\end{array}\right)\left(\begin{array}{c}{a}_n\\ ⋮\\ a_1\\ a_0\end{array}\right)& \left(1\right)\end{array}$

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] Further features and advantages of the present invention are given in the description of exemplary embodiments below, with reference to the figures.

[0012] FIG. 1 shows two sets of points in a plane to which the method according to the present invention may be applied.

[0013] FIG. 2 is a first illustration of results from methods according to the present invention using polynomials of different orders.

[0014] FIG. 3 is a second illustration of results from methods according to the present invention using polynomials of different orders.

[0015] FIG. 4 is a third illustration of results from methods according to the present invention using polynomials of different orders.

[0016] FIG. 1 shows two sets of points P₁, . . . P₅and G₁, . . . G₅; to help show they are associated with one another, each set is joined by a line; the points are plotted in a coordinate grid. Each of these points is characterized by two coordinate values, which in this case are conceived as the real component and the imaginary component of a complex number. The real component and the imaginary component are plotted on the ordinate and the abscissa of the coordinate system.

[0017] The points may each constitute the coordinates of pronounced locations on two maps such as road intersection or the like, these two maps being stored in a navigation system of a motor vehicle; however, for example, points P₁and P₅could also constitute a series of positions of the motor vehicle determined with the help of a GPS system, and points G₁to G⁵could constitute the path of a road shown on a map in the navigation system.

[0018] In order to be able to decide whether both sets of points belong to the same object, i.e. in this case whether they represent the same road, it is necessary to assess their similarity. To accomplish this, transformation T is sought which converts the set of points P_iinto the set of points P′_ifor which the sum of the distance squares |P′_i-G_i|²is a minimum. This transformation T is in the form of a polynomial

[0019] P_i=T(P_i)=a_n·Pⁿ+ . . . a₂·P²+a₁·P+a₀  (2)

[0020] Just as with points P_i, coefficients a_nto a₀are conceived as complex numbers. Herein, a₀represents a straightforward shift transformation, and a₁represents a rotate/stretch transformation. In view of the standard terminology used in electronics for characteristic curve parameters, it is proposed that the quadratic coefficient a₂be designated a “curve”, and the cubic coefficient a₃be designated a “turn”.

[0021] The extremal requirement that the squares of the distance apart be a minimum can be written as $\begin{array}{cc}\sum _i\left(P_i^{\prime }-G_i\right)·{\left(P_i^{\prime }-G_i\right)}^{*}\Rightarrow \mathrm{Min}& \left(3\right)\end{array}$

[0022] Combining equations 2 and 3 results in the following equation: $\begin{array}{cc}\sum _i\left(a_n·P_i^n+\dots +a_2·P_i^2+a_1·P_i+a_0-G_i\right)·{\left(a_n·P_i^n+\dots +a_2·P_i^2+a_1·P_i+a_0-G_i\right)}^{*}\Rightarrow \mathrm{Min}& \left(4\right)\end{array}$

[0023] From this it is possible to obtain equation system (1) by generating partial derivatives $\frac{\partial }{\partial a_j^{*}},j=0,1\dots ,n.$

[0024] If it is assumed that sets of points P_iand G_imust be converted into one another via translation and rotation/stretching, i.e. via rotation and modification of the scale, it is sufficient to consider equation (1) for the case n=1. In this case the following equation is obtained after equation (4) has been simplified: $\begin{array}{cc}\sum _i\left(a_n·P_i^n+a_0-G_i\right)·{\left(a_1·P_i+a_0-G_i\right)}^{*}\Rightarrow \mathrm{Min}.& \left(5\right)\end{array}$

[0025] After partial derivatives $\frac{\partial }{\partial a_0^{*}}$

[0026] and $\frac{\partial }{\partial a_1^{*}}$

[0027] have been generated and equating to zero has been carried out, the following equation system is obtained: $\begin{array}{cc}\left(\begin{array}{c}\sum _i{G}_i·P_i^{*}\\ \sum _i{G}_i\end{array}\right)=\left(\begin{array}{cc}\sum _i{P}_i·P_i^{*}& \sum _i{P}^{*}\\ \sum _i{P}_i& \sum _{i}1\end{array}\right)\left(\begin{array}{c}{a}_1\\ a_0\end{array}\right)& \left(6\right)\end{array}$

[0028] Methods for solving this equation system are known and do not need to be described in detail. As a solution the coefficients a₁, a₀are obtained which yield the transformation equation of the form

[0029] P=a₁·P+a₀

[0030] having the minimum error square.

[0031] Linear complex coefficient a₁contains the angle of rotation (phase and argument) and the stretching and change of scale (amount) relative to G. Scalar coefficient a₀indicates the translation. For the points shown in FIG. 1, calculation of the coefficients yielded the following results:

[0032] Thus the transformation that produces the greatest similarity between sets of points P_iand G_iincludes a 0.9-fold compression of set P_i, rotation of −1.3° and a shift of 2.4 in the direction 28°. The result is shown in FIG. 2, the coordinate grid of FIG. 1 in which points P₁to P₅are embedded having also been transformed so as to make the transformation clearer.

[0033] Calculating the value of the error square from equation (3) yields a measure of the similarity of the two sets of points.

[0034] If this error square exceeds a predefined boundary value, this suggests the two sets of points do not correspond to one another, and a different set of points from the map can be selected and the method applied once again thereto, until a modification is achieved that has an error square which is so small that it is fair to assume there is a match between the sets of points that have been selected.

[0035] Transformation parameters which take into account curves and turns can be found in an analogous manner to that described above. Thus, for example, using a transformation involving a quadratic polynomial T(P_i)=a₂P_i²+a₁P_i+a₀results in the following equation system: $\begin{array}{cc}\left(\begin{array}{c}\sum _i{G}_i·P_i^2\\ \sum _i{G}_i·P_i^{*}\\ \sum _i{G}_i\end{array}\right)=\left(\begin{array}{ccc}\sum _i{P}_i^2·P_i^{2*}& \sum _i{P}_i·P_i^{2*}& \sum _i{P}^{2*}\\ \sum _i{P}_i^2·P_i^{*}& \sum _i{P}_i·P_i^{*}& \sum _i{P}^{*}\\ \sum _i{P}_i^2& \sum _i{P}_i& \sum _{i}1\end{array}\right)\left(\begin{array}{c}{a}_2\\ a_1\\ a_0\end{array}\right)& \left(12\right)\end{array}$

[0036] Solving this equation system yields the following results for the points P₁to P₅and G₁to G₅shown:

[0037] A statement regarding the similarity may now be obtained, for example, via the ratio of the amount of quadratic coefficient a₂to the amount of linear coefficient a₁, i.e. via the non-linear part of the transformation: $\frac{\left(a_2\right)}{\left(a_1\right)}=0.035$

[0038] The result of the transformation is shown in FIG. 3, the transformation also having been carried out on the coordinate grid of points P₁to P₅, the result of which is deformed grid 2.

[0039] FIG. 4 shows the result of a transformation using cubic polynomial T having coefficients a₃, a₂, a₁, a₀that have been optimized according to the method described above. The coefficients are indicated in the table below:

[0040] Herein, it is important to note that when the error amount square method is used, for each higher order of modification, new values of the individual coefficients are produced, and the sum of the error squares becomes smaller and smaller the more optimizable coefficients are used. Therefore the change in a coefficient associated with the transition to the next higher modification level may also be used as a measure of the similarity.