A novel approach to computation of the shape of a dot pattern and extraction of its perceptual border

A novel approach to defining the external shape of a dot pattern is proposed from which the intuitive border of the set is extracted. The approach is based on a new definition called the s-shape, which can be generated by a data-driven procedure. The s-shape generates a staircase-like border. To obtain a polygonal border, an r-shape is defined for which the parameter r is found from s, the parameter of the s-shape. The main advantage of this approach is that it can be computed in O(n) time for a dot pattern containing n points. The approach has three basic steps: (i) choice of an appropriates (and corresponding r) from the given point set, (ii) generation of the r-shape, and (iii) cleaning of inconsistent parts from the r-shape. The diagram composed of the consistent edges of the r-shape is considered the perceived border of the dot pattern. A new structural basis called the dispersion matrix is evolved. Extension of the work to the digital case is discussed. The algorithm for extracting the perceptual border is fast since it is mainly composed of basic operations such as nonnegative integer addition and logical operations. Moreover, it can be implemented on parallel machines since the operations are local in the point space. (C) 1997 Academic Press.