Algorithms that measure parallelism and concurrency of lines in digital images

Peter Veelaert

doi:10.1117/12.364114

23 September 1999 Algorithms that measure parallelism and concurrency of lines in digital images

Peter Veelaert

Proceedings Volume 3811, Vision Geometry VIII; (1999) https://doi.org/10.1117/12.364114
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1999, Denver, CO, United States

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.

Citation Download Citation

Peter Veelaert "Algorithms that measure parallelism and concurrency of lines in digital images", Proc. SPIE 3811, Vision Geometry VIII, (23 September 1999); https://doi.org/10.1117/12.364114

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