Hierarchical matching using submap isomorphism

Abstract

This Ph.D. Thesis presents a novel part-based approach for automatic object detection in real scenes. For that purpose, the scene is represented using a novel perceptual segmentation approach, also presented in this thesis, that uses the combinatorial pyramid and that combines boundaries and region information. The target object is also represented by means of a combinatorial map. This representation provides two interesting properties for object detection: i) it does not deliver a single segmentation result, but a hierarchy of partitions that represent the image at different scales, and ii) topology can be used to drive the searching of the target object in the scene.

Then, in order to compare both representations (object and scene), a novel hierarchical algorithm for sub-combinatorial map isomorphism is performed. Submap isomorphism consists of checking if a given submap can be found into another map. This search procedure, however, should not expect the representation of the object, in any of the layers, to match exactly with the internal representation of that object. Shadows, occlusions and many other factors will avoid these exact matchings to occur. For that reason, this thesis presents a error-tolerant submap isomorphism algorithm that is able to identify the distortions that make one submap a distorted version of the other map.

The algorithm for submap isomorphism does not work with combinatorial maps, but with their associated symbol sequences. Thus, using this encoding, the submap isomorphism will be solved looking for a matching of symbol sequences. This search is done iteratively in each level of the combinatorial pyramid, starting from the apex.

The proposed method for object detection has been tested for traffic sign detection and also using a real use case in the framework of robot navigation showing good performance and robustness of the approach in the presence of partial occlusions, uneven illumination and 3-dimensional rotations. Moreover, the perceptual segmentation approach has been also evaluated using the Berkeley dataset BSD300. These experiments show that the proposed method yields better or similar results than other approaches while offering two insteresting features alreay mentioned: computation at multiple image resolutions and preservation of the image topology.