Расстояние Хаусдорфа между точками двух сеток

Мне нужно реализовать расстояние Хаусдорфа для двух сеток. Сетки - это разные результаты сегментации человеческого органа, и мне нужно их сравнить, одна сетка - это золотой сегмент. а второй результат алгоритма сегментации.

Я буду использовать расстояние Хаусдорфа, но у меня есть некоторые проблемы с пониманием того, что именно я должен делать. Я понял, что я должен вычислить ближайшую точку для каждой точки в meshA в meshB и наоборот. Это мои относительные расстояния. Для 2 соответствующих точек в наборах я беру максимальное относительное расстояние => Хаусдорфа. (вот как далеко я)

Теперь моя проблема: у одного меша ~100 000 точек, у другого ~2000. Следовательно, это будут отношения n:1. Какие точки я беру для расчета Хаусдорфа, как мне с этим справиться? Был бы признателен за любую подсказку. Спасибо!


person toobee    schedule 01.06.2012    source источник


Ответы (1)


Если x and xявляется конечным или счетным объединением, то сумма

Если xи y являются метрическими пространствами, то размерность Хаусдорфа их произведения удовлетворяет сумма

upd: Алгоритм грубой силы:

1.  h = 0 
2.  for every point ai of A,
      2.1  shortest = Inf ;
      2.2  for every point bj of B
                    dij = d (ai , bj )
                    if dij < shortest then
                              shortest = dij
      2.3  if shortest > h then 
                    h = shortest 
person Dmitry Zagorulkin    schedule 01.06.2012
comment
Я думаю, что для этой задачи подойдет метод из python itertools product. docs.python.org/library/itertools.html#itertools.product - person Dmitry Zagorulkin; 01.06.2012
comment
Я все еще не уверен, правильно ли я понимаю его реализацию. Для каждой точки в meshA (PA) я рассматриваю все точки в meshB, которые имеют PA в качестве ближайшего соседа. Из этих точек я установил максимальное расстояние для ПА как хаусдорф. Теперь то же самое для meshB; Вот как я должен это сделать? - person toobee; 01.06.2012
comment
Вопрос о хаусдорфовом расстоянии, а ответ о хаусдорфовой размерности. Они очень разные... - person Alex Chamberlain; 08.06.2012
comment
ответ на ваш вопрос cgm.cs.mcgill .ca/~godfried/teaching/cg-projects/98/normand/ - person Dmitry Zagorulkin; 08.06.2012