23 September 1999 Algorithms that measure parallelism and concurrency of lines in digital images
Author Affiliations +
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.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Peter Veelaert, Peter Veelaert, } "Algorithms that measure parallelism and concurrency of lines in digital images", Proc. SPIE 3811, Vision Geometry VIII, (23 September 1999); doi: 10.1117/12.364114; https://doi.org/10.1117/12.364114
PROCEEDINGS
11 PAGES


SHARE
RELATED CONTENT

An algorithm for a lossless compression of raw radar data
Proceedings of SPIE (December 16 2014)
Computing stair-case visibility polygon
Proceedings of SPIE (December 01 1993)
The Fast Hartley Transform
Proceedings of SPIE (December 19 1985)

Back to Top