Szybkie znajdowanie szorstkich linii w zestawach punktów

12

W konkretnej klasie detektorów nasze dane pojawiają się jako pary punktów w dwóch wymiarach, a my chcemy połączyć te punkty w linie.

Dane są zaszumione i są dzielone w jednym kierunku, ale nie w drugim. Nie możemy zagwarantować trafienia w każdym pojemniku, nawet gdy każdy element detektora działa, więc mogą wystąpić pomyłki.

Nasz obecny łańcuch analiz wygląda

  1. Dostosuj trafienia do kalibracji poszczególnych elementów detektora
  2. Znajdź klastry
  3. Surowe dopasowanie linii do klastrów
  4. Połącz klastry w dłuższe struktury podobne do linii
  5. ...

To pytanie dotyczy kroku (3).

Do tego kroku używamy transformacji Hougha i działa ona dobrze, ale gdy próbujemy przeskalować z poziomu stanowiska testowego do symulacji projektu na pełną skalę, staje się on niedopuszczalnie wolny.

Szukam szybszego sposobu.

Dla tych, którzy mogą obchodzić faktyczny przypadek użycia, jest komora do projekcji czasowej ciekłego argonu

regression computer-vision pattern-recognition dmckee --- były kot moderator
źródło
1
W FermiLab wykonaliśmy również rekurencyjną metodę transformacji Hougha do śledzenia ścieżki przez wieloprzewodowe komory proporcjonalne. Starsza praca Erika Kangasa zawiera wszystkie szczegóły. Myślę, że to wciąż najlepszy sposób, aby to zrobić.
Matt Knepley,
1
Miałeś na myśli „... pary w punkcie ...” lub „... pary punktów ...” w pierwszym zdaniu?
Bill Barth

Odpowiedzi:

2

Istnieje probabilistyczna wersja transformaty Hougha (PHT), która jest szybsza. Jak opisali Bradski i Kaehler w swojej książce OpenCV:

Chodzi o to, że szczyt i tak będzie wystarczająco wysoki, a uderzenie go wystarczy na ułamek czasu, aby go znaleźć.

Biblioteka OpenCV przedstawia implementację dla PHT.

Istnieją inne alternatywy. Stworzenie rozproszonej wersji transformacji Hougha nie jest trudne . Po prostu podziel zestaw punktów na mniejsze części i użyj struktury MapReduce, aby zsumować wszystkie akumulatory. Innym pomysłem jest wykonanie zgrubnej wersji transformaty Hougha przy użyciu przestrzeni parametrów o niskiej rozdzielczości. Wybierz najlepszych kandydatów i przeprowadź dokładniejszą iterację, używając przestrzeni parametrów o wyższej rozdzielczości. Może taki jest pomysł FHT Gandalfa.

TH
źródło
1
PHT zaproponowano w: Matas, J. i Galambos, C. i Kittler, JV, Solidne wykrywanie linii za pomocą progresywnej probabilistycznej transformacji Hougha. CVIU 78 1, s. 119–137 (2000).
TH.
Następnie precyzyjną procedurę można uogólnić na wiele kroków, co robi Gandalf.
dmckee --- były moderator kociak
BTW - Od czasu, kiedy zadałem to pytanie, kolega dodał moduł wykorzystujący progresywną probabilistyczną wersję transformacji do naszego kodu. Przyszło to z kilkoma powiązanymi zmianami, więc trudno jest dokładnie scharakteryzować dokonaną różnicę, ale jest to część pakietu, który znacznie przyspieszył kilka kroków analizy. Przyjmuję to jako „zwycięską” radę.
dmckee --- były moderator kociąt
5

Mój współpracownik znalazł szybką transformację Hougha w bibliotece Gandalfa , która wygląda bardzo obiecująco, ale jej integracja może wymagać dużo pracy, dlatego szukam innych podejść.

Implementacja Gandalfa jest interesująca: oceniają przestrzeń akumulatora w sposób rekurencyjny, tak jakby przemierzały drzewo czwórkowe lub ośmiordzeniowe. Regiony bez dużej gęstości są wyrzucane na bieżąco.

dmckee --- były kot moderator
źródło