points d'angle Recherche d'un Quadrilatère de jeu de points

Question

je tente d'obtenir les points d'angle d'un quadrilatère de jeu de points.

• L'ensemble des points sont ordonnés et décrire les grandes lignes
• Parfois, le contour a un peu de bruit (voir 2ème photo)
• La recherché des points d'angle ne doivent pas être des points sur l'ensemble donné de des points (voir en bas 3ème photo à gauche)
• Les points d'angle recherché décrivent un quadrilatère convexe, pas nécessairement un rectangle

La deuxième image est un peu extrême, mais la "qualité" de mon ensemble de points se situe entre la première et la deuxième image.

D'abord, je pensais de faire un Histogramme de plus de 1-360 ° et la longueur, deux points suivants décrivent. Les quatre plus hauts sommets décriraient la longueur de chaque ligne. Mais avec ça, je perds les points de commande, je connais juste le degré et la longueur ou une ligne et je ne sais pas à quelle position appartient une ligne.

Alors je pensais à la fusion de deux lignes suivantes si elles ont plus ou moins le même degré, mais je ne sais pas comment gérer le bruit ici ou prédire un coin.

Est-ce que quelqu'un sait d'un algorithme qui gère ce problème ou quelque chose de similaire?

Answer 1

Vous pouvez traiter cela comme un problème de regroupement, où les clusters « centres » sont en fait des lignes droites. Pour calculer la classification, vous pouvez utiliser un algorithme k-means:

1. Choisissez 4 paires de points aléatoires. Ajuster une ligne à chacun, de sorte que vous avez 4 lignes traversant le nuage de points.
2. Répéter jusqu'à ce que la solution semble avoir convergé:
   1. Pour chacun des points, calculez la distance à chacune des 4 lignes.
   2. Affectez le point à un compartiment correspondant à la ligne à laquelle il se trouve le plus proche.
   3. Fit 4 nouvelles lignes aux points chacun des 4 seaux (vous pouvez utiliser la régression linéaire ou SVD)

Pour améliorer la première étape, vous pouvez prendre votre idée de prendre un histogramme sur la angles, et affecter chaque point initialement à un seau qui correspond au pic le plus proche. Ajustez ensuite les lignes aux quatre compartiments et recommencez l'itération.

Vous pouvez également traiter cela comme un problème d'optimisation: prendre 4 points afin que la zone de la différence (zone blanche à l'intérieur et à l'extérieur de la zone noire de la quadrilatérale) est le plus petit possible. Les algorithmes d'optimisation génériques fonctionnent probablement, mais pour le rendre rapide, vous avez besoin d'un algorithme raisonnable pour calculer les zones.