In many vision tasks, one needs to define spatial properties which are based upon locations of certain entities in images called tokens. At the simplest level a neighbor relationshionship between image tokens need to be defined. Even more complex spatial properties can be defined such as local distribution of image tokens and density variations in a neighborhood.
For very simple tokens such as dots in an image (one can regard individual pixels as dots in some contexts) the most important property is their relative positions with each other. Traditionally, many approaches have been proposed for defining local neighborhood properties. Some look at fixed sized neighborhoods around an image token. Anything falling into such a neighborhood is then considered a neighbor. Other definitions exist which are based on graph theoretic constructions such as minimum spanning trees (MST).
One definition which we have used successfully is the Voronoi tessellation of a dot pattern. The Voronoi tessellation has some nice properties which match with our intuitive understanding of neighborhood.
Suppose that we are given a set S of three or more points in the Euclidean plane. Assume that these points are not all collinear, and that no four points are cocircular. Consider a point P in the set S. The Voronoi region assigned to the point P consists of all the points in the Euclidean plane that are closer to P than to any other point. For a set of dots, the Voronoi regions are polygons. Defining these Voronoi regions for all the points in the set S results in a tessellation of the plane which is called the Voronoi tessellation[1,2]. Two points are said to be Voronoi neighbors if the Voronoi polygons enclosing them share a common edge. The dual representation of the Voronoi tessellation is the Delaunay graph which is obtained by connecting all the pairs of points which are Voronoi neighbors as defined above.
The notion of the neighborhood of a dot allows access to the properties of a two-dimensional region around the dot in question such as area and shape properties. The Voronoi tessellation and the polygonal region assigned to each dot in this representation lead to a natural and intuitive definition of neighborhood of a dot. Because the Voronoi tessellation is adaptive to variations in dot distribution, such properties of the Voronoi polygons as the area, shape, etc. also vary with changes of scale, density variations, etc., thus reflecting the differences in spatial distributions of dots.
We consider as the neighborhood of a point P (the region enclosed by) the Voronoi polygon containing P. Considering the way a Voronoi polygon is constructed, this is an intuitively appealing approach. The local environment of a point in a given pattern is reflected in the geometrical characteristics of its Voronoi polygon. This presents a convenient way to compare the local environments of different points. An entire set of geometric properties of polygons can be computed based on their moments of area. Many intuitive properties such as the area and elongation can then be computed from these moments of area.
Translation in Czech provided by Andrey Fomin: http://www.pkwteile.de/wissen/vypocetni-geometrie
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, 1985.
N. Ahuja, ``Dot Pattern Processing Using Voronoi Neighborhoods,'' in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-4, no. 3, pp. 336-343, May, 1982.
N. Ahuja and M. Tuceryan, ``Extraction of Early Perceptual Structure in Dot Patterns: Integrating Region, Boundary, and Component Gestalt,'' Computer Vision, Graphics, and Image Processing, vol. 48, pp. 304-356, December 1989. (Abstract)
N. Ahuja and M. Tuceryan, ``Perceptual Organization of Dot Patterns,'' Encyclopedia of Artificial Intelligence, vol. 1, pp. 253-256, S. Shapiro (ed.), Wiley, 1985. (Book Chapter)
M. Tuceryan and T. Chorzempa, ``Relative Sensitivity of a Family of closest point graphs in computer vision applications,'' Pattern Recognition Journal, vol. 24, no. 5, pp. 361-373, 1991. (Abstract)