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 thes-shape, which can be generated by a data-driven procedure. Thes-shape generates a staircase-like border. To obtain a polygonal border, anr-shape is defined for which the parameterris found froms, the parameter of thes-shape. The main advantage of this approach is that it can be computed inO(n) time for a dot pattern containingnpoints. The approach has three basic steps: (i) choice of an appropriates(and correspondingr) from the given point set, (ii) generation of ther-shape, and (iii) cleaning of inconsistent parts from ther-shape. The diagram composed of the consistent edges of ther-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.