Similarity assessment for cardinal directions between extended spatial objects

Cardinal directions are frequently used as selection criteria in spatial queries or for assessing similarities of spatial scenes. Current models for cardinal directions use crude approximations in the form of the objects' minimum bounding rectangles or their generalizations to points. To overcome the limitations of these models so that improved reasoning can be performed, the coarse direction-relation matrix is introduced. It partitions space around a reference object and records into which direction tiles an extended target object falls. The detailed direction-relation matrix captures more details by recording the ratio of the target object in each direction tile or the number of separations per tile. This multi-resolution model provides a better approximation for direction relations of complexly structured spatial objects than the approach with minimum bounding rectangles.; In order to record directions between arbitrary pairs of point, line, and region objects, the model based on the coarse direction-relation matrix is extended to the deep direction-relation matrix. It additionally records information about the intersection of the target object with the boundaries of direction tiles, if necessary. This thesis demonstrates that directions recorded at smaller scales using this model are compatible with the directions recorded at larger scales. The compatibility makes this model useful for direction-based queries in spatial databases over multiple scales.; To apply direction-relation matrices for the assessment of similarity between spatial scenes, this thesis develops a method to compute similarity between direction-relation matrices. The similarity between two direction-relation matrices depends on the distances between cardinal directions along a conceptual neighborhood graph, which has a node for each direction tile and edges connecting nodes corresponding to neighboring tiles. There are two types of graphs: the 4-neighborhood graph and the 8-neighborhood graph. The comparative study of the mappings from directions changes to similarity values provided by the graphs reveals that the 4-neighbohood graph provides a sounder mapping than the 8-neighborhood graph. The similarity assessment method gives cognitively plausible rankings of spatial scenes based on the cardinal direction between objects, and it is useful in retrieving spatially similar scenes in image databases, video databases, multimedia databases, and web databases.