IAPR Distinguished Speakers

Computational aspects of Digital Plane and Hyperplane Recognition

In discrete geometry, various definitions and properties of linear structures, such as straight lines, planes or hyperplanes, have been proposed, leading to analytical characterization of these objects. In many applications, we have to consider a reverse problem: given a set of pixels, voxels or hyper-voxels, decide if this set is a piece of discrete line, discrete plane or discrete hyperplane? In it is, a recognition algorithm is required.

In dimension 2, the arithmetical structure of discrete straight lines leads to efficient algorithms, as both their asymptotic computational cost and the efficiency of their implementations is studied.

In higher dimension, arithmetical structures still exist in discrete planes and hyperplanes. However, to solve the recognition problem, we usually adapt algorithms from linear programming (LP) or computational geometry (CG). In this case, there is a gap between the time complexity bounds obtained for LP or CG problems, and the efficiency of these algorithms when applied discrete objects. Indeed, we can observe that complexity bounds are not tight at all when we perform experimental analysis.

In this presentation, we will investigate computational and efficiency aspects of discrete plane and hyperplane recognition problems using results and tools from CG and Integer LP.

Polygonal Approximation of Point Sets

Our domain of interest is polygonal (and polyhedral) approximation of point sets. Neither the order of data points nor the number of needed line segments (surface patches) are known. In particular, point sets can be obtained by laser range scanner mounted on a moving robot or given as edge pixels/voxels in digital images. Polygonal approximation of edge pixels can also be interpreted as grouping of edge pixels to parts of object contours.

The presented approach is described in the statistical framework of Expectation Maximization (EM) and in cognitively motivated geometric framework. We use local support estimation motivated by human visual perception to evaluate support in data points of EM components after each EM step. Consequently, we are able to recognize a locally optimal solution, and modify the number of model components and their parameters. We will show that the proposed approach converges to a globally optimal solution independent of the initial number of model components and their initial parameters.