Using the Voronoi tessellation for grouping words and multipart symbols in documents

Mark J. Burge; Gladys Monagan

doi:10.1117/12.216407

11 August 1995 Using the Voronoi tessellation for grouping words and multipart symbols in documents

Mark J. Burge, Gladys Monagan

Proceedings Volume 2573, Vision Geometry IV; (1995) https://doi.org/10.1117/12.216407
Event: SPIE's 1995 International Symposium on Optical Science, Engineering, and Instrumentation, 1995, San Diego, CA, United States

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.

Citation Download Citation

Mark J. Burge and Gladys Monagan "Using the Voronoi tessellation for grouping words and multipart symbols in documents", Proc. SPIE 2573, Vision Geometry IV, (11 August 1995); https://doi.org/10.1117/12.216407

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available