trouver des points de selle en 3D heightmap

Question

Étant donné un heightmap 3D (à partir d'un scanner laser), comment puis-je trouver le saddle points?

I.e. quelque chose de donné comme ceci:

Je cherche tous les points où la courbure est positive dans un sens et négatif dans l'autre.

(Ces directions ne doivent pas nécessairement être alignées avec les axes X et Y. Je sais comment vérifier si la courbure dans la direction X a le signe opposé comme la courbure dans la direction Y, mais cela ne couvre pas tous les cas . pire encore, la résolution X est différente de la résolution en Y)

Idéalement je suis à la recherche d'un algorithme qui peut tolérer une certaine quantité de bruit et seulement marquer des points de selle « importants ».

Answer 1

(A partir d'une estimation au mathématiques plutôt que de l'expérience pratique)

Monter un second degré à la surface dans une petite pièce autour de chaque point candidat, par exemple avec les moindres carrés. La taille du patch est une façon de contrôler le bruit, et vous pouvez gagner en pondérant des points en fonction de leur distance par rapport au point candidat. En notation matricielle, vous pouvez représenter le quadratique comme x'Ax + b'x + c, où A est symétrique.

Le quadratique aura un gradient nul à x = (A^-1) b/2. Si ce n'est pas dans le patch, jetez-le.

Si A a à la fois les valeurs propres + ve et -ve, vous avez un point de selle en x. Puisque A est seulement 2x2 et a donc au plus deux valeurs propres, vous pouvez ignorer le cas quand il vaut zéro valeur propre et donc vous ne pouviez pas l'inverser à l'étape précédente.

Answer 2

J'ai étudié un problème similaire pour une classe de topologie computationnelle et j'ai eu un certain succès avec la méthode décrite ci-dessous. D'abord vous aurez besoin d'une fonction de comparaison qui évaluera la hauteur à deux points d'entrée et renverra < ou> (non égal) pour n'importe quelle entrée. Une façon de faire est que si les points sont de hauteur égale, vous utilisez un index basé sur la position ou aléatoire pour trouver le plus grand point. Vous pouvez penser à cela en ajoutant une perturbation infinitésimale à la hauteur.

Maintenant, pour chaque point, vous allez comparer la hauteur de tous les voisins environnants (il y aura 8 voisins sur une grille rectangulaire 2D). Le lien inférieur pour un point sera l'ensemble de tous les voisins pour lesquels la hauteur est inférieure au point.

Si toutes les valeurs voisines sont dans le lien inférieur, vous êtes à un maximum local. Si aucun des points n'est dans le lien inférieur vous êtes à un minimum local. Sinon, si le lien inférieur est un seul ensemble connecté, vous êtes à un point régulier sur une pente. Mais si le lien inférieur est deux ensembles non connectés, vous êtes en selle.

En 2D, vous pouvez construire une liste des 8 points voisins dans un ordre cyclique autour du point que vous vérifiez. Vous attribuez une valeur de +/- 1 pour chaque voisin en fonction de votre fonction de comparaison. Vous pouvez ensuite parcourir cette liste (n'oubliez pas de comparer les deux extrémités) et compter le nombre de changements de signe pour déterminer le nombre de composants connectés dans le lien inférieur.

La détermination des selles qui sont «importantes» est une analyse plus difficile. Vous pouvez regarder ceci: http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Gyulassy08.pdf pour quelques conseils.

-Michael