Dopasowywanie profili w chmurze punktów

Chmura punktów jest generowany za pomocą równomiernego rozkładu funkcję (x,y,z). Jak pokazano na poniższym rysunku, badana jest płaska przecinająca się płaszczyzna ( profil ), która pasuje jako najlepszy (nawet jeśli nie dokładny) profil docelowy, tj. Podany w lewym dolnym rogu. Więc pytanie brzmi:

1- Jak znaleźć taki mecz podane target 2D point mapprzez point cloudrozważenie następujących Uwagi / warunki?
2- Jakie są zatem współrzędne / orientacje / stopień podobieństwa itp.?

Uwaga 1: Profil zainteresowania może być w dowolnym miejscu z dowolnym obrotem wzdłuż osi, a także może mieć inny kształt, np. Trójkąt, prostokąt, czworokąt itp., W zależności od jego położenia i orientacji. Na poniższej demonstracji pokazano tylko prosty prostokąt.

Uwaga 2: Wartość tolerancji można uznać za odległość punktów od profilu. Aby to wykazać na poniższym rysunku, załóżmy tolerancję 0.01razy najmniejszy wymiar (~1)tak tol=0.01. Jeśli więc usuniemy resztę i rzutujemy wszystkie pozostałe punkty na płaszczyznę badanego profilu, będziemy mogli sprawdzić jego podobieństwo do profilu docelowego.

Uwaga 3: Temat pokrewny można znaleźć w Rozpoznawaniu wzorców punktowych .

To zawsze będzie wymagało dużo obliczeń, szczególnie jeśli chcesz przetworzyć aż 2000 punktów. Jestem pewien, że istnieją już wysoce zoptymalizowane rozwiązania dla tego rodzaju dopasowywania wzorców, ale musisz dowiedzieć się, jak to się nazywa, aby je znaleźć.

Ponieważ mówisz o chmurze punktów (rzadkich danych) zamiast obrazu, moja metoda korelacji krzyżowej tak naprawdę nie ma zastosowania (i byłaby jeszcze gorsza obliczeniowo). Coś w rodzaju RANSAC prawdopodobnie szybko znajdzie dopasowanie, ale niewiele o nim wiem.

Moja próba rozwiązania:

Założenia:

• Chcesz znaleźć najlepsze dopasowanie, a nie tylko luźne lub „prawdopodobnie prawidłowe” dopasowanie
• W dopasowaniu wystąpi niewielki błąd związany z szumem w pomiarze lub obliczeniach
• Punkty źródłowe są współpłaszczyznowe
• Wszystkie punkty źródłowe muszą istnieć w celu (= każdy niedopasowany punkt jest niezgodnością dla całego profilu)

Powinieneś być w stanie wziąć wiele skrótów, dyskwalifikując rzeczy i skracając czas obliczeń. W skrócie:

1. wybierz trzy punkty ze źródła
2. przeszukuj punkty docelowe, znajdując zestawy 3 punktów o tym samym kształcie
3. po znalezieniu dopasowania 3 punktów sprawdź wszystkie pozostałe punkty w płaszczyźnie, które definiują, aby sprawdzić, czy pasują do siebie
4. jeśli znaleziono więcej niż jedno dopasowanie wszystkich punktów, wybierz ten z najmniejszą sumą błędu odległości 3D

Bardziej szczegółowe:

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

Która konfiguracja ma błąd najmniejszych kwadratów dla wszystkich innych punktów, najlepiej pasuje

Ponieważ pracujemy z 3 punktami testowymi najbliższego sąsiada, dopasowanie punktów docelowych można uprościć, sprawdzając, czy znajdują się w promieniu. Na przykład szukając promienia 1 z (0, 0), możemy zdyskwalifikować (2, 0) na podstawie x1 - x2, bez obliczania rzeczywistej odległości euklidesowej, aby ją nieco przyspieszyć. Zakłada się, że odejmowanie jest szybsze niż mnożenie. Istnieją również zoptymalizowane wyszukiwania oparte na bardziej dowolnym stałym promieniu .

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2+(z_1 - z_2)^2}$

$2000 \choose 2$

Właściwie, ponieważ i tak będziesz musiał obliczyć wszystkie, bez względu na to, czy znajdziesz dopasowania, czy nie, a ponieważ w tym kroku zależy ci tylko na najbliższych sąsiadach, jeśli masz pamięć, prawdopodobnie lepiej jest wstępnie obliczyć te wartości przy użyciu zoptymalizowanego algorytmu . Coś w rodzaju triangulacji Delaunaya lub Pittewaya , w której każdy punkt celu jest połączony z najbliższymi sąsiadami. Przechowuj je w tabeli, a następnie poszukaj ich dla każdego punktu, próbując dopasować trójkąt źródłowy do jednego z trójkątów docelowych.

W grę wchodzi wiele obliczeń, ale powinna być stosunkowo szybka, ponieważ działa tylko na danych, które są rzadkie, zamiast mnożenia wielu zerowych znaczeń zerowych, takich jak korelacja krzyżowa danych wolumetrycznych. Ten sam pomysł zadziałałby w przypadku 2D, gdybyś najpierw znalazł środki kropek i zapisał je jako zbiór współrzędnych.

Dodałbym opis @ mirror2image do alternatywnego rozwiązania obok RANSAC, możesz rozważyć algorytm ICP (iteracyjny najbliższy punkt), opis można znaleźć tutaj !

Myślę, że następnym wyzwaniem przy korzystaniu z tego ICP jest zdefiniowanie własnej funkcji kosztu i początkowej pozycji płaszczyzny docelowej w odniesieniu do danych punktu chmurowego 3D. Pewnym praktycznym podejściem jest wprowadzenie losowego szumu w danych podczas iteracji, aby uniknąć zbieżności z fałszywymi minimami. To heurystyczna część, którą chyba trzeba zaprojektować.

Aktualizacja:

Kroki w formie uproszczonej to:

1. Znajdź najbliższy punkt dla każdego punktu wejściowego.
2. Oblicz transformację od wejścia do celu, a następnie przesuń punkty wejściowe za pomocą transformacji.
3. Oblicz funkcję podobieństwa (np. Odległość dla każdego punktu wejściowego wrt do odpowiadającego mu punktu docelowego pary).
4. Sprawdź stan zatrzymania.

Powtórz krok 1-4.

Dostępna jest biblioteka, którą możesz rozważyć tutaj ! (Jeszcze tego nie próbowałem), w części dotyczącej rejestracji jest jedna sekcja (w tym inne metody).