Algorithme pour suivre le chemin des arêtes sur une image 3D

Question

J'essaie de trouver un algorithme (ou des idées d'algorithme) pour suivre une crête sur une image 3D, dérivée d'un modèle d'élévation numérique (DEM). J'ai réussi à obtenir un programme très basique fonctionnant juste à travers chaque ligne de l'image marquant une ligne de crête où il trouve un grand changement d'aspect (par exemple de < 180 degrés à> 180 degrés). Cependant, les lignes que cela produit ne sont pas brillantes, il y a souvent des lacunes et divers artefacts étranges. J'espère essayer d'étendre cela en utilisant une sorte d'algorithme pour suivre les lignes de crête, produisant ainsi des lignes complètes (c'est-à-dire sans lacunes) et plus précises.

Un certain nombre de personnes ont mentionné des algorithmes de serpent, mais ils ne semblent pas être tout à fait ce que je cherche. J'ai aussi fait beaucoup de recherches sur les algorithmes de recherche de chemin, mais encore une fois, ils ne semblent pas être la bonne chose à faire.

Est-ce que quelqu'un a des suggestions pour les types ou les algorithmes ou les algorithmes spécifiques que je devrais regarder?

Mise à jour: On m'a demandé d'ajouter plus de détails sur la zone exacte à laquelle je vais appliquer cela. Il travaille avec des données d'altitude quadrillées de dunes de sable. J'essaie d'extraire les crêtes si ces dunes ressemblent aux limites entre les bassins versants, mais peuvent être beaucoup plus complexes (par exemple, il peut y avoir plusieurs dunes de sable très proches les unes des autres avec des crêtes qui se confondent graduellement)

Answer 1

Je ne sais pas à quoi ressemblent vos données ni de quelle automatisation vous avez besoin. Cela ne fonctionnera pas si des pics se compose sans arêtes claires (mais alors vous ne serait probablement pas poser la question.)

startPoint = highest point in DEM (or on ridge) 
curPoint = startPoint; 
line += curPoint; 
Loop 
    curPoint = highest point adjacent to curPoint not in line; // (Don't backtrack) 
    line += point; 
Repeat 

Curieux ce que la vraie solution se révèle être.

Edité pour ajouter: en fonction de la grossièreté de votre ensemble de données, 'point' peut être un point unique ou une moyenne lissée d'une région locale de points.

Answer 2

http://en.wikipedia.org/wiki/Ridge_detection

Answer 3

Vous pouvez traiter l'élévation comme vous une couleur en niveaux de gris, utilisez un filtre de reconnaissance de bord 2D. Il y a beaucoup de méthodes de reconnaissance de bord disponibles. Le meilleur dépend de vos besoins spécifiques.

Answer 4

Vous pouvez obtenir une bonne estimation des arêtes en utilisant les changements de signe de la courbure. Notez que la courbure sera proche de l'infini dans les régions plates. Par conséquent possible pseudo-code d'un algorithme de détection de crête pourrait être:

for each face in the mesh 
    compute 1/curvature 
    if abs(1/curvature) != zeroTolerance 
    flag face as ridge 
    else 
    continue 

(ZeroTolerance est un nombre proche mais non égale à zéro par exemple, 0,003, etc.)

également Meshlab fournit un module d'estimation normale & de courbure sur la plupart des formats. Vous pouvez tester l'idée en l'utilisant avant de la coder.