A new image matching technique is described. It is implemented as an object-independent hierarchical structural
juxtaposition algorithm based on an alphabet of simple object-independent contour structural elements. The structural
matching applied implements an optimized method of walking through a truncated tree of all possible juxtapositions of
two sets of structural elements. The algorithm was initially developed for dealing with 2D images such as the aerospace
photographs, and it turned out to be sufficiently robust and reliable for matching successfully the pictures of natural
landscapes taken in differing seasons from differing aspect angles by differing sensors (the visible optical, IR, and SAR
pictures, as well as the depth maps and geographical vector-type maps). At present (in the reported version), the
algorithm is enhanced based on additional use of information on third spatial coordinates of observed points of object
surfaces. Thus, it is now capable of matching the images of 3D scenes in the tasks of automatic navigation of extremely
low flying unmanned vehicles or autonomous terrestrial robots. The basic principles of 3D structural description and
matching of images are described, and the examples of image matching are presented.
The automatic analysis of images of terrain is urgent for several decades. On the one hand, such analysis is a base of automatic navigation of unmanned vehicles. On the other hand, the amount of information transferred to the Earth by modern video-sensors increases, thus a preliminary classification of such data by onboard computer becomes urgent. We developed an object-independent approach to structural analysis of images. While creating the methods of image structural description, we did our best to abstract away from the partial peculiarities of scenes. Only the most general limitations were taken into account, that were derived from the laws of organization of observable environment and from the properties of image formation systems. The practical application of this theoretic approach enables reliable matching the aerospace photographs acquired from differing aspect angles, in different day-time and seasons by sensors of differing types. The aerospace photographs can be matched even with the geographic maps. The developed approach enabled solving the tasks of automatic navigation of unmanned vehicles. The signs of changes and catastrophes can be detected by means of matching and comparison of aerospace photographs acquired at different time. We present the theoretical proofs of chosen strategy of structural description and matching of images. Several examples of matching of acquired images with template pictures and maps of terrain are shown within the frameworks of navigation of unmanned vehicles or detection of signs of disasters.
The investigation presented in this article continues our long-term efforts directed towards the automatic structural matching of aerospace photographs. An efficient target independent hierarchical structural matching tool was described in our previous paper, which, however, was aimed mostly for the analysis of 2D scenes. It applied the same geometric transformation model to the whole area of image, thus it was nice for the space photographs taken from rather high orbits, but it often failed in the cases when the sensors were positioned near the 3D scenes being observed. Different transformation models should be applied to different parts of images in the last case, and finding a correct separation of image into the areas of homogeneous geometric transformations was the main problem.
Now we succeeded in separating the images of scenes into the surfaces of different objects on the base of their textural and spectral features, thus we have got a possibility of separate matching the sub-images corresponding to such objects applying different transformation model to each such sub-image. Some additional limitations were used in the course of such separation and matching. In particular, the a priory assumptions were applied in different cases about the possible geometry of scenes, rules of illumination and shadowing, thus the aerospace photographs, indoor scenes, or images of aircrafts were analyzed in slightly differing ways. However the additional limitations applied could be considered as very general and are worth to be used in a wide sphere of practical tasks. The automatic image analysis was successful in all considered practical cases.
The surface textures of natural objects often have the visible fractal-like properties. A similar pattern of texture could be found looking at the forests in the aerial photographs or at the trees in the outdoor scenes when the image spatial resolution was changed. Or the texture patterns are different at different spatial resolution levels in the aerial photographs of villages. It creates the difficulties in image segmentation and object recognition because the levels of spatial resolution necessary to get the homogeneously and correctly labeled texture regions differ for different types of landscape. E.g. if the spatial resolution was sufficient for distinguishing between the textures of agricultural fields, water, and asphalt, the texture labeled areas of forest or suburbs are hardly fragmented, because the texture peculiarities corresponding to two stable levels of texture spatial resolution will be visible in this case. A hierarchical texture analysis could solve this problem, and we did it in two different ways: we performed the texture segmentation simultaneously for several levels of image spatial resolution, or we subjected the texture labeled image of highest spatial resolution to a recurring texture segmentation using the texture cells of larger sizes. The both approaches turned out to be rather fruitful for the aerial photographs as well as for the outdoor images. They generalize and support the hierarchical image analysis technique presented in another our paper. Some of the methods applied were borrowed from the living vision systems.
We present an information-theoretic approach to the image interpretation problems. In the context of this approach such tasks as contour extracting, constructing the most informative image features and image matching are described as a single unified problem. Our approach is based primarily on the interpretation of the image (or image set) representation problem as a Minimum Description Length (MDL) problem. The image matching turns out to be a generally adopted method of images alignment by maximization of their mutual information. However, instead of using the pixels intensities themselves a more condensed data representation form can be used to reduce the dimensionality of input data and to extract the invariant information: hierarchical image structural description. Though we developed and successfully applied the information-theoretic approach for the images matching, it can be extended to the other problems, e.g. the changes detection.
The aim of investigation was developing the image registration algorithms dealing with the aerial and cosmic pictures taken in different seasons from differing view points, or formed by differing kinds of sensors (visible, IR, SAR). The task could not be solved using the traditional correlation based approaches, thus we chose the structural juxtaposition of the stable specific details of pictures as the general image matching technique. Structural matching was usually applied in the expert systems where the rather reliable results were based on the target specific algorithms, but our algorithms deal with the aerospace photographs of arbitrary contents for which the application specific approaches could not be used. The chosen form of structural descriptions should provide distinguishing between the similar simple elements in the huge multitudes of image contours, thus the descriptions were made hierarchical: we grouped the contour elements belonging to the separate compact image regions. The structural matching was carried out in two levels: matching the simple elements of every group in the first image with the ones of every group in the second image; matching the groups as the wholes. The top-down links were used to enhance the lower level matching using the higher level matching results.
The aim of investigation was developing the registration algorithms for the aerial and cosmic pictures taken in different seasons from differing viewpoints, formed by differing kinds of sensors (visible, IR, SAR). Structural matching was chosen as the only approach that could manage with the mentioned image differences. In the contrast to the target dependent structural analysis applied in the expert systems we dealt with the images of arbitrary content, thus the rigidity and opacity of landscape objects and the rules of shadowing were the only limitations applied. The simple contour elements corresponding to the objects borders were judged to be a most stable source of structural descriptions in this uncertain situation. However a large amount of similar simple elements produced a high dimensional structural matching task. It decreased the reliability of matching and exponentially increased the computational expenditures. We solved this problem building the hierarchical structural descriptions. We separated the structural elements to the rather small local groups and structurally matched them using the special tree walking algorithms. Two grouping approaches were applied: uniting the elements belonging to a continuous contour line, or uniting the ones situated in a separate compact region. The matching results were reliable both for the multiple season and multiple sensor images. The first approach demonstrates a slightly better precision, while the second one is slightly more robust and flexible, thus it can deal also with the structural elements of other nature: the compact regions formed in result of texture segmentation were also successfully structurally matched.
The aim of investigation was developing the data fusion algorithms dealing with the aerial and cosmic pictures taken in different seasons from the differing view points, or formed by differing kinds of sensors (visible, IR, SAR). This task couldn't be solved using the traditional correlation based approaches, thus we chose the structural juxtaposition of the stable characteristic details of pictures as the general technique for images matching and fusion. The structural matching usually was applied in the expert systems where the rather reliable results were based on the target specific algorithms. In the contrast to such classifiers our algorithm deals with the aerial and cosmic photographs of arbitrary contents for which the application specific algorithms couldn't be used. To deal with the arbitrary images we chose a structural description alphabet based on the simple contour components: arcs, angles, segments of straight lines, line branching. This alphabet is applicable to the arbitrary images, and its elements due to their simplicity are stable under different image transformations and distortions. To distinguish between the similar simple elements in the huge multitudes of image contours we applied the hierarchical contour descriptions: we grouped the contour elements belonging to the uninterrupted lines or to the separate image regions. Different types of structural matching were applied: the ones based on the simulated annealing and on the restricted examination of all hypotheses. The matching results reached were reliable both for the multiple season and multiple sensor images.