Ar. Chaudhuri et al., A NOVEL-APPROACH TO COMPUTATION OF THE SHAPE OF A DOT PATTERN AND EXTRACTION OF ITS PERCEPTUAL BORDER, Computer vision and image understanding, 68(3), 1997, pp. 257-275
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.