Share Email Print

Proceedings Paper

Using the Voronoi tessellation for grouping words and multipart symbols in documents
Author(s): Mark J. Burge; Gladys Monagan
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

We examine the importance of the definition of neighbors and neighborhoods for grouping in document understanding and list some previous definitions. We present a number of benefits to using the Voronoi neighborhood definition; however, we argue that definitions based upon the point Voronoi diagrams are insufficient in the general case (e.g. for grouping image elements in line drawings). We give the definition of a generalized (Euclidean distance measure, 2D Cartesian space, and an area based generator set) Voronoi tessellation and then present our algorithm for approximating this generalized tessellation. The algorithm is constructed from a normal point Voronoi tessellation algorithm. A parameterized Voronoi neighborhood graph (VNG) which can be derived from the tessellation is defined. A graph algorithm for grouping based on the VNG, its image elements, and Voronoi cell descriptors can then be easily derived. We show some results of how this algorithm was used in a map understanding system.

Paper Details

Date Published: 11 August 1995
PDF: 9 pages
Proc. SPIE 2573, Vision Geometry IV, (11 August 1995); doi: 10.1117/12.216407
Show Author Affiliations
Mark J. Burge, Swiss Federal Institute of Technology (Switzerland)
Gladys Monagan, Swiss Federal Institute of Technology (Switzerland)

Published in SPIE Proceedings Vol. 2573:
Vision Geometry IV
Robert A. Melter; Angela Y. Wu; Fred L. Bookstein; William D. K. Green, Editor(s)

© SPIE. Terms of Use
Back to Top