Conformal geometric algebra voting scheme

This project proposes a novel algorithm based on classical voting schemes like Hough Transform and Tensor Voting. In particular, it combines the use of perceptual saliency functions and geometric flags with a clustering technique, all within the mathematical framework of the conformal model of Geometric algebra. So that, the voting scheme can represent complex configurations of visual data we want to detect; in addition, this algorithm can be use as building blocks to design hierarchical architectures. Experimental results show its ability to extract pair of points, lines, circles, and symmetry axes from synthetic and real images.

Computational problem.

Goal: To detect features associated to geometric properties in images.

Input: A 2D digital image.

Output: A set of descriptors asociated to geometric properties of the objects contained in the image.


The voting scheme can be summarized in the following steps:

  1. To construct candidate solutions from the image (geometric structures).

  2. To assign a scalar value to each candidate solution using a function (perceptual saliency of the structure).

  3. To group similar structures into clusters using DBSCAN algorithm.

  4. To select clusters with maximum perceptual saliency (winners of the voting process)

Steps 1 and 2 consist in representing the information conatined in the image. For this purpose, geometric algebra is used to construct geometric representations from image data. In addition, a function is defined to assign a perceptual value to the geometric structure. We can define different functions and geometric structures depending on the information we want to detect (geometric primmitives, simmetries, continuity, parallelism, etc.)

Steps 3 and 4 are the voting process: we group similar solutions, compute a perceptual saliency for each cluster of solutions and select the cluster with maximum saliency or select those whose saliency surpases a threshold value.

After the voting scheme, we can apply join and meet operations or geometric transformations over the resulting geometric structures. In addition, we can aply the voting scheme in a hierarchical way, by defining more complicated geometric structures or perceptual funcions.

Application to detection of circles and lines in 2D images.

The voting scheme with 2 hierarchical stages was applied for detection of circles and lines. The first stage detects geometric primitives in a local neighbourhood, while the second stage groups information from all over the image. The perceptual saliency function was defined to favor continuity properties of pixels.

Some interesting results found were:

  • The voting scheme describe non-linear countours with a set of lines and circles. This can be used to construct local descriptors of shape. I addition, the normal of the countour at each position can be found using the circles and lines computed by the voting scheme.

  • In contrast to the Hough transform algorithm, the voting scheme can detect local and global geometric primitives.

  • In contrast to the Tensor voting algorithm, the voting scheme can detect multiple geometric primitives in local neighbourhoods.

  • Implementations in C++ for CPU and FPGA were tested, achiving an spead-up of 2 for images with 700 entities in a local neighbourhood.

Application to detection of bilateral symmetry in 2D images.

The voting scheme was applied as building blocks to construct a 3-stage hierarchical architecture, with 2 independent process; the left part detect circles and lines and use this information to compute symmetry axis, while the right part compute symmetry axis directly from the image data.

The algorithm has a similar performance (precision and recall), in the detection of bilateral simmetry over synthetic and real images, than state of the art algorithms.


[1] Gerardo Altamirano-Gómez and Eduardo Bayro-Corrochano. “Conformal Geometric Method for Voting”. In: Journal of Intelligent Data Analysis 20 (2016), S69-S82.

[2] Gerardo Altamirano-Gómez and Eduardo Bayro-Corrochano. “Conformal Geometric Algebra Method for Detection of Geometric Primitives”. In: 23nd International Conference on Pattern Recognition (ICPR). 2016.

[3] Gerardo Soria-Garcı́a et. al. “Conformal Geometric Algebra Voting Scheme implemented in reconfigurable devices for geometric entities extraction”. In: IEEE Transactions on Industrial Electronics (2017).