Алгоритм следования траектории гребней на трехмерном изображении

Question

Я пытаюсь найти алгоритм (или идеи алгоритма) для отслеживания гребня на трехмерном изображении, полученном из цифровой модели рельефа (ЦМР).Мне удалось заставить работать очень простую программу, которая просто перебирает каждую строку изображения, отмечая линию гребня, где бы она ни находилась с большим изменением в аспекте (то есть от <180 градусов до> 180 градусов).

Однако, линии, которые это производит, не блестящие, часто есть промежутки и различные странные артефакты.Я надеюсь попробовать и расширить это, используя какой-то алгоритм следования линиям гребня, таким образом создавая линии, которые являются полными (то есть без пропусков) и более точными.

Несколько человек упомянулиалгоритмы змеи для меня, но они, кажется, не совсем то, что я ищу.Я также много занимался поиском алгоритмов поиска путей, но, опять же, они не совсем правильные.

У кого-нибудь есть предложения по типам, алгоритмам или конкретным алгоритмам, которые мне следуетпосмотрите?

Обновление: Меня попросили добавить более подробную информацию о точной области, к которой я буду применять это.Он работает с привязанными к рельефу данными о высоте песчаных дюн.Я пытаюсь извлечь гребни, если эти песчаные дюны похожи на границы между водосборными бассейнами, но могут быть намного более сложными (например, может быть несколько песчаных дюн очень близко друг к другу с постепенно сливающимися гребнями)

Answer 1

Вы можете получить хорошую оценку гребней, используя изменения знака кривизны. Обратите внимание, что кривизна будет близка к бесконечности в плоских областях. Следовательно, возможный псевдокод для алгоритма обнаружения гребня может быть:

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

(zeroTolerance - число, близкое к нулю, но не равное, например, 0,003 и т. Д.)

Также Meshlab предоставляет модуль для оценки нормальной и кривизны в большинстве форматов. Вы можете проверить идею, используя ее, прежде чем кодировать ее.

Answer 2

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

Answer 3

Вы можете обрабатывать высоту как цвет в оттенках серого, а затем использовать 2D-фильтр распознавания краев.Существует множество методов распознавания краев.Лучшее зависит от ваших конкретных потребностей.

Answer 4

Я не знаю, каковы ваши данные или сколько вам нужно автоматизации. Это не сработает, если состоит из пиков без четких ребер (но тогда вы, вероятно, не задавали бы вопрос.)

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

Любопытно, что реальное решение оказывается.

Отредактировано, чтобы добавить: в зависимости от грубости вашего набора данных, 'точка' может быть одной точкой или сглаженным средним по локальной области точек.