Image structure map data structure for spatially indexing an imgage

Abstract

A data structure representation of an original image called an image structure map (ISM) accurately, compactly and explicitly represents the geometry, topology and signal properties of regions in an original image. In mathematical terms, the ISM is a partition of the original image induced by a set of image region boundaries. The ISM data structure includes, for each region in the original image, a region data item that indicates the region boundary data items that form the region and a signal property descriptor indicating the value of signals computed for or assigned to the region. Region boundary data items represent image region boundaries that are determined to occur in the original image as a result of analyzing signal properties of original image locations. Vertices (endpoints and intersections) of region boundary data items are represented in the ISM in machine representable values that result from modifying infinite precision vertex values using a rounding operation that mathematically ensures topological and geometric consistency with the original image. The image structure map includes a spatial image indexing data structure in the form of hierarchy of partitions of the original image of varying levels of detail that allows for efficient point location. An illustrated implementation of the data structure has the form of a vertical cell decomposition. The ISM may be implemented to permit dynamic modifications so that changes to regions resulting from the insertion or deletion of new or changed region boundaries may be made without recomputing the entire ISM.