| Home | Organisation | Educational |
In discrete geometry various definitions and properties of linear structures -- such as straight lines, planes, or hyperplanes -- have been proposed. On this basis, computational efficient analytic characterizations of these objects have been obtained. In many applications one considers a reverse problem: given a set of pixels or (hyper)voxels, decide if it is a portion of a discrete line or (hyper)plane. For this, a recognition algorithm is needed.
In dimension two, the arithmetic structure of discrete straight lines (DSL) has been exploited to design efficient algorithms, as both their asymptotic computational cost and practical efficiency have been studied. In higher dimension, similar arithmetic structures still exist in digital planes and hyperplanes. However, to solve a recognition problem, one usually adapts algorithms from linear programming (LP) or computational geometry (CG). As a rule, there is a gap between the theoretical time complexity bounds obtained for linear programming or computational geometry problems and the practical efficiency of these algorithms when applied to discrete objects. Indeed, one can observe that the existing time complexity bounds are not tight when experimental analysis is performed.
The objective of the challenge is to provide both DPS generators and frameworks to compare the existing recognition algorithms.
We have created a subversion repository to track the source files. To download the code (read-only access, send an email to David Coeurjolly to obtain a write-access if you wish):
svn checkout https://svn.liris.cnrs.fr/dcoeurjo/DigitalPlaneRecognition/trunk/
Implemented generators:
Two main recognition softwares: