Share Email Print

Proceedings Paper

Algorithms that measure parallelism and concurrency of lines in digital images
Author(s): Peter Veelaert
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Several geometric concepts from affine geometry have their counterparts in digital geometry. We define and discuss the digitization of three of important concepts: parallelism, colinearity, and concurrency of digital straight lines. Their main characteristic is that in the digital plane these properties become Helly-type theorems, which means that they express a geometric relation holding for an entire collection of geometric objects in terms of simpler geometric relations that must hold for subcollections. For example, in the digital plane we can show that a collection of digital lines is parallel if and only if each of its 2-membered subcollections consists of two digital lines that are parallel. Thus parallelism in the digital plane is more complicated than it is in ordinary affine geometry. Appropriate definitions for digital parallelism and concurrency have many applications in digital image processing. For example, they provide an appropriate setting for verifying whether lines detected in a digital image satisfy the constraints imposed by a perspective projection. Furthermore, the existence of Helly-type properties has important implications from a computational viewpoint. In fact, these theorems ensure that in the digital plane parallelism, colinearity, and concurrency can be detected in polynomial time by standard algorithms developed within the field of computational geometry. We illustrate this with several algorithms, where each algorithm solves a particular geometric problem.

Paper Details

Date Published: 23 September 1999
PDF: 11 pages
Proc. SPIE 3811, Vision Geometry VIII, (23 September 1999); doi: 10.1117/12.364114
Show Author Affiliations
Peter Veelaert, Hogeschool Gent (Belgium)

Published in SPIE Proceedings Vol. 3811:
Vision Geometry VIII
Longin Jan Latecki; Robert A. Melter; David M. Mount; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top