Construction of isothetic covers of a digital object: A combinatorial approach

An isothetic cover of a digital object not only specifies a simple representation of the object but also provides an approximate information about its structural content and geometric characteristics. When the cover “tightly” encloses the object, it is said to be an outer isothetic cover; and when the cover tightly inscribes the object, it is an inner isothetic cover. If a set of horizontal and vertical grid lines is imposed on the object plane, then the outer (inner) isothetic cover is defined by a set of isothetic polygons, having their edges lying on the grid lines, such that the effective area corresponding to the object is minimized (maximized). Increasing or decreasing the grid size, therefore, decreases or increases the complexity or the accuracy of the isothetic cover corresponding to a given object, which, in turn, extracts the object information at different resolutions. In this paper, a combinatorial algorithm is presented for varying grid sizes, which is free of any backtracking and can produce the isothetic cover of a connected component in a time linear in the length of the perimeter of the cover. The algorithm has also been extended for finding the isothetic covers of real-world digital objects having multiple components with or without holes. Experimental results that demonstrate applications of an isothetic cover to diverse problems of pattern analysis and computer vision, are reported for various data sets.