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 pr oposed from which the intuitive border of the set is extracted. The ap proach is based on a new definition called the s-shape, which can be g enerated 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. T he 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 bas ic steps: (i) choice of an appropriates (and corresponding r) from the given point set, (ii) generation of the r-shape, and (iii) cleaning o f inconsistent parts from the r-shape. The diagram composed of the con sistent edges of the r-shape is considered the perceived border of the dot pattern. A new structural basis called the dispersion matrix is e volved. Extension of the work to the digital case is discussed. The al gorithm for extracting the perceptual border is fast since it is mainl y composed of basic operations such as nonnegative integer addition an d logical operations. Moreover, it can be implemented on parallel mach ines since the operations are local in the point space. (C) 1997 Acade mic Press.