Dot Pattern Processing Using Voronoi Neighborhoods
- 1 May 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. PAMI-4 (3) , 336-343
- https://doi.org/10.1109/tpami.1982.4767255
Abstract
A sound notion of the neighborhood of a point is essential for analyzing dot patterns. The past work in this direction has concentrated on identifying pairs of points that are neighbors. Examples of such methods include those based on a fixed radius, k-nearest neighbors, minimal spanning tree, relative neighborhood graph, and the Gabriel graph. This correspondence considers the use of the region enclosed by a point's Voronoi polygon as its neighborhood. It is argued that the Voronoi polygons possess intuitively appealing characteristics, as would be expected from the neighborhood of a point. Geometrical characteristics of the Voronoi neighborhood are used as features in dot pattern processing. Procedures for segmentation, matching, and perceptual border extraction using the Voronoi neighborhood are outlined. Extensions of the Voronoi definition to other domains are discussed.Keywords
This publication has 28 references indexed in Scilit:
- Recognition of spatial point patternsPattern Recognition, 1983
- Toward a low-level description of dot clusters: Labeling edge, interior, and noise pointsComputer Graphics and Image Processing, 1979
- Region growing: Childhood and adolescenceComputer Graphics and Image Processing, 1976
- Computing the perceptual boundaries of dot patternsComputer Graphics and Image Processing, 1974
- A parameter-free clustering modelPattern Recognition, 1972
- A method of comparing two patterns independent of possible transformations and small distortionsPattern Recognition, 1972
- Minimum Spanning Trees and Single Linkage Cluster AnalysisJournal of the Royal Statistical Society Series C: Applied Statistics, 1969
- Hierarchical clustering schemesPsychometrika, 1967
- A Method for Curve Seeking from Scattered PointsThe Computer Journal, 1966
- Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.Journal für die reine und angewandte Mathematik (Crelles Journal), 1908