Быстрое нахождение неровных линий в наборах точек

12

В конкретном классе детекторов наши данные поступают в виде пар точек в двух измерениях, и мы хотим выстроить эти точки в линии.

Данные зашумлены и сгруппированы в одном направлении, но не в другом. Мы не можем гарантировать попадание в каждую ячейку, даже когда каждый элемент детектора работает, поэтому возможны пропуски.

Наша текущая цепочка анализа выглядит так

  1. Отрегулируйте попадания для калибровки отдельных элементов детектора
  2. Найти кластеры
  3. Грубые линии подгонки к кластерам
  4. Соедините кластеры в более длинные линейные структуры
  5. ...

Этот вопрос касается шага (3).

Для этого шага мы использовали преобразование Хафа, и оно работает хорошо, но, поскольку мы пытаемся перейти от испытательного стенда к моделированию полномасштабного проекта, оно становится неприемлемо медленным.

Я ищу более быстрый путь.

Для тех, кого интересует фактический вариант использования, здесь есть камера для проекции времени с жидким аргоном.

regression computer-vision pattern-recognition dmckee --- котенок экс-модератора
источник
1
Мы также выполнили рекурсивный метод преобразования Хафа для отслеживания пути через многопроволочные пропорциональные камеры в FermiLab. Старший тезис Эрика Кангаса содержит все детали. Я думаю, что это все еще лучший способ сделать это.
Мэтт Кнепли
1
Вы имели в виду «... пары на точке ...» или «... пары точек ...» в первом предложении?
Билл Барт

Ответы:

2

Существует вероятностная версия преобразования Хафа (PHT), которая работает быстрее. Как описано Bradski & Kaehler в их книге OpenCV:

Идея состоит в том, что пик все равно будет достаточно высоким, и тогда его попадание будет длиться лишь часть времени.

Библиотека OpenCV представляет реализацию для PHT.

Есть и другие альтернативы. Нетрудно создать распределенную версию преобразования Хафа. Просто разбейте свою точку на меньшие порции и используйте инфраструктуру MapReduce, чтобы суммировать все аккумуляторы. Другая идея состоит в том, чтобы выполнить грубую версию преобразования Хафа, используя пространство параметров с низким разрешением. Выберите своих лучших кандидатов и выполните более точную итерацию, используя пространство параметров с более высоким разрешением. Может быть, это идея FHT Гэндальфа.

TH.
источник
1
PHT был предложен в: Matas, J. and Galambos, C. and Kittler, JV, Робастное обнаружение линий с использованием прогрессивного вероятностного преобразования Хафа. CVIU 78 1, стр 119-137 (2000).
TH.
Конечно, процедура штрафа может быть обобщена на несколько этапов, что и делает Гэндальф.
dmckee --- котенок экс-модератора
Кстати, со времени, когда я задал этот вопрос, коллега добавил модуль, использующий прогрессивную вероятностную версию преобразования в нашем коде. Это привело к нескольким связанным изменениям, поэтому трудно точно определить, в чем они заключались, но это часть пакета, который значительно ускорил пару шагов анализа. Итак, я собираюсь принять это как «выигрышный» совет.
dmckee --- котенок экс-модератора
5

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

Реализация Gandalf интересна: они вычисляют пространство аккумулятора рекурсивным способом, как если бы они проходили через четырехугольник или окт-дерево. Регионы без особой плотности выбрасываются на ходу.

dmckee --- котенок экс-модератора
источник