Object correlation based on relation density.

Stamin, Dragos ; Stamin, Cristina ; Marinescu, Mirel 等

Abstract: This paper proposes a method to correlate two nadiral ungeoreferenced images based on the analysis of relation density of correspondence relations between objects independently determined on two images. This paper presents a brief illustration of the proposed method and analyses the validity of the method. It also applies the method to two different images of a same real scene.

Key words: image correlation, relation density

1. INTRODUCTION

This paper proposes a method to correlate two nadiral ungeoreferenced images for the purpose of making a relative registration of images that differ from each other with respect to origin, scale and/or orientation. The existent automate solution involves computing classical correlation parameters based on the radiometric similarity between small windows on images (Richards & Jia, 2006). The automatic solution has a small tolerance for large differences in scale and orientation. The proposed method is based on established correspondence relations between objects determined on both images. The implementation of the proposed method still needs optimizations, in order to be applied to large images.

2. METHOD PRESENTATION

Consider two nadiral images (images A and B) located on the same terrain scene, both of them already geometrically and radiometrically processed (Liu & Mason, 2009). Images A and B have a different origin, a different orientation and a different scale. To correlate the two images, we have to find a biunique correspondence between the elements composing each of the images (Stamin et al., 2008b). Assume the composing elements are areal objects, that are determined, for example, by segmentation techniques (***, 2011). The fundamental steps for determining the set of correspondences are: 1) detecting spatially distinct areal objects on each of the images and allocating a set of characteristics to each of them; 2) determining the set of correspondence relations; and 3) eliminating the false correspondences by checking the correspondences via another method.

Depending upon the level of analysis desired, one may also want to find the transformation parameters between images A and B.

For purposes of determining the set of correspondence relations, we analyze three techniques: one based on dimensionless parameters associated to each of the objects in images; another technique that builds a ratio for each pair of distances between two objects on each image; and a technique that uses pairs of three objects on each image to build an angle (Stamin et al., 2008a).

As part of our discussion regarding the three techniques listed above, we generally use the word ,,entity" for any of the following: dimensionless parameters and distances between two objects or angle made by three objects. Also, for distance and angle computations, we reduce an object to a point, defined as the centroid of the convex envelope of the object.

For each of the enumerated techniques the same mathematics apply. Each image has a number of spatially distinct areal objects, {[a.sub.1],..., [a.sub.n]} [member of] A and {[b.sub.1,...,[b.sub.m]} [member of] B, respectively. Therefore, for each of the images we have one set of entities. With these entities we build a correlation matrix. Subject to certain exceptions, this matrix indicates the correlation parameter as the prevalent element of the correlation matrix.

Suppose the following two entity sets: [o.sub.n], ... [o.sub.n] [member of ]A and [o'.sub.1], ..., [o'.sub.m] [member of] B. First, we rearrange the elements of each set in increasing (or decreasing) order. After elimination of all the repeating values, we then obtain two strict increasing (or decreasing) sequences [{[o.sub.i]}.sub.i=1..p] [member of] A and [{[o'.sub.j]}.sub.j=1..q] [member of]B. The elements of the correlation matrix are the ratios between one element of sequence {[0.sub.i]} and another element of sequence {[o'.sub.j]}. Denoting [o.sub.i]/[o'.sub.j] = [m.sub.ij] we will get the matrix M=([m.sub.ij]).

a) Let us analyze the case p=q. If the correspondence relation is biunique, the matrix M will be a square one and all the diagonal elements will be equal.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

The most unfavorable case is when the consecutive elements from each sequence generate the same ratio. Even in this case, the number of equal elements on the matrix's diagonal is one larger than the number of the equal elements neighboring the diagonal (Table 1). Unfavorable cases seldomly arise and can be surpassed, for example, by choosing different characteristics.

If there is not a biunique correspondence, matrix M may or may not be a square matrix. It is certain, however, that not all the elements on the diagonal will be equal. In this case, if we compute the distribution of the values within matrix M and make the same analysis as above, we find that the preponderant value indicates the correspondence relation between the entities of the two images.

b) If p [not equal to] q we can go further in more ways. One easy way (however, time consuming) involves consideration of square matrices built from the initial nonsquare matrix through elimination of one or more rows or columns, followed by application of the reasoning presented in a). Another method is to calculate the distribution of the values of the matrix, and then consider all the peaks of the distribution as correlation ratios. To establish which one of these peaks is the right one, one has to check the correctness of the correlation parameter by another method. For example, if we obtain a set of peaks for correlation parameters using dimensionless characteristics of objects, we can verify the appropriate peak by applying the method whereby one locates the correlation parameter by using ratios between distances or ratios between angles.

3. EXAMPLES

In the following three ways two images of the same terrain scene can differ: different origin, different scale and different orientation. Since difference in origin does not impose any complications in finding the correlation parameter, we focus on the last two cases. We also consider the following additional factors: the precision of the calculus and the number of combinations taken (q). These factors can influence the correctness of the results.

The results presented here are based on computing the elements of the correlation matrix as ratios of distances between pairs of points. The algorithm is a repetitive one in that it tries to locate object A on image A that corresponds to object B on image B.

Case 1: Two images with different scales (see fig. 1). Having two different scales results in a different number of identifiable areal objects on each image. It also results in diminished geometric details of areal objects with scale reduction. Therefore, we get a 15% difference in areal object content between the two images. There are 29 areal objects associated with the left image and 36 areal objects associated with the right image (see fig. 2).

Table 2 summarizes the results for the two images depicted in fig. 1. An algorithm was applied for 4 cases of combinations (10, 15, 20, 25), using three different precision levels (0.1, 0.01, 0.001). The values reflected in Table 2 represent the number of correspondences determined by the algorithm. One can observe that the number of determined correspondences increases with the number of combinations taken. However, increasing the precision level does not always lead to a higher number of correspondences.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

Case 2: Two images with different scales and different orientations (see fig. 3). In the left image we have 29 areal objects and in the right image 31 areal objects. The two images share in common only 26 areal objects (see fig. 4).

Table 3 summarizes the results for the two images depicted in fig. 3. One can observe that the number of determined correspondences increases with the number of combinations taken and there is only one precision that leads to favorable results.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

4. CONCLUSIONS

The proposed method described in this paper determines the correlation parameter in all the above cases. The number of the correlated objects depends upon the number of combinations considered and the precision level. While increasing the number of combinations leads to a larger number of correspondence relations established by the algorithm, increasing the precision level does not always produce the same result. The scale difference is the main factor that influences the convergence of the algorithm.

To determine the transformation parameters between the two images it is sufficient to establish the minimum number of correspondences between a real objects of the two images.

5. REFERENCES

Liu, J.G. & Mason, J.P. (2009). Essential Image Processing and SIG for Remote Sensing, John Wiley and Sons, Inc., ISBN: 9780470510322, New York

Richards, J.A. & Jia, X., (2006). Remote Sensing Digital Image Analysis: An Introduction, Fourth Edition, ISBN: 10 3-540-25128-6, Springer-Verlag, Heildelberg

Stamin, D., Stamin, C. & Amza, R., (2008a). Methods for correlating image objects, Tehnica military, nr 1/2008, pp. 47-59, ISSN: 1582-7321, Bucharest, Romania

Stamin, D., Stamin, C. & Buciu, C., (2008b). Image correlation based on relation density, Proceedings of the 38th International Scientific Symposium of Military Equipment and Technologies Research Agency, May 2009, CD-ISBN: 978-973-0-056846, Bucharest, Romania

*** (2011). Image Segmentation, Pei-Gee Ho (Ed.), InTech, ISBN 978-953-307-228-9, Rijeka, Croatia

Tab. 1. The unfavorable case of correlation matrix

 1 2 4 8 16

1 1 2 4 8 16
2 1/2 1 2 4 8
4 1/4 1/2 1 2 4
8 1/8 1/4 1/2 1 2
16 1/16 1/8 1/4 1/2 1

Tab. 2. Results for two images with different scales

 Precision Level

 0.1 0.01 0.001

Q 10 10 15 3
 15 12 20 6
 20 14 18 5
 25 13 22 7

Tab. 3. Results of method application for two images with
different scales and different orientations

 Precision Level

 0.1 0.01

q 10 5 8
 15 3 13
 20 6 17
 25 6 23
 26 7 26