Détection de cercles (ellipses) dans un nuage de points 2D

14

Étant donné un ensemble de points (2D) soit, nuage de points (PC), la question est d'un robust, accurateet computing-friendlyméthode pour trouver des cercles (ou ellipses en version avancée).

L'idée intuitive est d'utiliser Brute-Force Search sur tous les points possibles (comme centre) {infini!} Et les rayons (encore infini!). C'est ultra-extrêmement lent et inefficace.

Comme démontré ci-dessous, chaque cercle ajusté serait classé en fonction du nombre de points ( nn) positionnés sur la circonférence du cercle à une distance inférieure à un seuil ( t). Il faut derrdonc présenter une distance moyenne.

Sous une forme avancée, les ellipses sont intéressantes à ajuster.

Des idées, des remue-méninges, des expériences, des commentaires? entrez la description de l'image ici

edge-detection local-features point-cloud hough-transform Développeur
la source
Bonne question. Quel programme avez-vous utilisé pour générer ce diagramme?
Jason R
@JasonR Comme toujours, Python + MatPlotLib .
Développeur

Réponses:

14

La meilleure idée qui tente exactement de résoudre ce problème est Hough Transform .

Fondamentalement, le signal dans l'espace hough sera r, x, ydes coordonnées. Ici r représente le rayon et le x,ycentre. Chaque point peut appartenir à un ou plusieurs cercles. Ainsi , dans le plan Hough passer par tous les milieux possibles où ce point pourrait appartenir et faire juste un +1. Ce n'est pas une recherche, juste une collection.

Maintenant, si un vrai cercle existe, tant de points s'ajouteront et le score d'un tel r, x, ysera beaucoup plus élevé que tous les autres. La sélection d'un tel point vous permettra de choisir les bons cercles.

Voici un chemin classique du papier en 1971 (avant ma naissance!) Qui a inventé ce concept.

  1. UTILISATION DE LA TRASFORMATION FORTE POUR DÉTECTER DES LIGNES ET DES COURBES DANS DES IMAGES Par: Richard O. Duda, Peter E. Hart Tech report Artificial Intelligence Cente April 1971.

Pour le tutoriel, je suggère des références ci-dessous:

  1. HIPR2 -Link
  2. Amos storkey
  3. Référence IDL

Spécifiquement pour la détection de cercle, vous pouvez vous référer à ceci ci-dessous:

  1. AI Shack
  2. Rapport technique de Chicago Univ.
  3. Notes de cours du Rochester Institute

Ces méthodes sont très efficaces et très faciles à utiliser.

Dipan Mehta
la source
1
Je peux me porter garant des articles AI Shack, ils aident vraiment à comprendre les mathématiques plus rigoureuses que vous lirez ailleurs.
Ivo Flipse
1
Bonne réponse. Je connais déjà Hough Transform (HT). Celui que j'ai utilisé était pour la détection de lignes. Il y avait un peu de difficulté à déterminer les segments de ligne. Il a donc été recommandé d'utiliser la transformation probabiliste de Hough (PHT). Je n'ai pas eu d'idée claire sur l'extension. Je pensais que cela pouvait être si complexe pour les cercles ou apparaître d'autres difficultés. Concernant mes expériences HT est bon mais pas parfait. Je souhaite également étendre HT à la 3D. Je vais essayer de revoir vos liens fournis. Votre réponse est assez bonne pour être candidate comme réponse.
Développeur
AI Shack et le rapport technique de Chicaco sont morts
Mehdi