Dopasuj częściowe dane liniowe

Jaki jest solidny sposób na dopasowanie danych liniowych, ale hałaśliwych?

Mierzę sygnał, który składa się z kilku prawie liniowych segmentów. Chciałbym atomatycznie dopasować kilka linii do danych, aby wykryć przejścia.

Zestaw danych składa się z kilku tysięcy punktów, z 1-10 segmentami i znam liczbę segmentów.

To jest przykład tego, co chciałbym zrobić automatycznie.

Wypróbowałem dwa podejścia, naiwnie (używając tylko 3 segmentów). Z pewnością byłyby tam bardziej wyszukane metody.

RANSAC, ma być solidnym mechanizmem dopasowania. Po kilku segmentach łatwo jest zatrzymać algorytm. Wymuszanie ciągłości między segmentami może być jednak trudne - co wydaje się wymagane w Twojej aplikacji - przynajmniej za pomocą prostej implementacji. Jako dowód koncepcji, że utworzony obraz z punktami pomiarowymi, tak aby można używać silnik RANSAC dostępne w , funkcja wykrywania linii Mathematicą.$ImageLines$

Zamontuj częściowy model liniowy za pomocą minimalizatora ogólnego przeznaczenia. Egzekwowanie ciągłości segmentów jest łatwe. Co ciekawe, testowanie pozostałości i innych właściwości może dostarczyć informacji wystarczających do automatycznego określenia liczby segmentów - jednak tego nie próbowałem. Tak to wygląda w Mathematica:

Nie twierdzę, że poniższa metoda jest solidna, ale może działać dla Ciebie. Przy tysiącach punktów i być może około dziesięciu segmentach prostych postępuj w następujący sposób.$x[n]$

• Przetwórz punkty aby utworzyć tablicę bitów y [ n ] w następujący sposób. y [ n ] = { 1 , jeśli | ( x [ n + 1 ] - x [ n ] ) - ( x [ n ] - x [ n - 1 ] ) | < ϵ , 0 , w przeciwnym razie. Tutaj$x[n]$$y[n]$

  $$y[n] = \begin{cases}1, &\text{if} ~ |(x[n+1]-x[n]) - (x[n]-x[n-1])| < \epsilon,\\ 0, &\text{otherwise.}\end{cases}$$ jest małą liczbą wybraną, aby dopasować się do twojego pojęcia, jak blisko linii prostej chcesz punkty x [ n - 1 ] , x [ n ] , x [ n + 1 ] . Kryterium zostanie rozpoznane przez cognoscenti jako wymagające, aby linia prosta przez ( n - 1 , x [ n - 1 ] ) i ( n , x [ n ] $\epsilon$$x[n-1],x[n], x[n+1]$$(n-1, x[n-1])$$(n,x[n])$ma prawie takie samo nachylenie jak linia prosta przez i ( n + 1 , x [ n + 1 ] ) .$(n,x[n])$$(n+1,x[n+1])$

• Jeśli to tablica dziesięciu lub tak długich przebiegów 1 s oddzielonych biegami 0 s ze sporadycznymi zbłąkanymi 1 s tu i tam, aby niszczyć piękno, zrelaksować się, jesteś na dobrej drodze. W przeciwnym razie, jeśli jest zbyt mało przebiegów lub zbyt wiele przebiegów trwających 1 s, powtórz poprzedni krok z innym ϵ .$y[n]$$1$$0$$1$$1$$\epsilon$

• $y[n]$$x[3]$$x[88]$$x[94]$$x[120]$$x[129]$$\cdots$, i tak dalej. Rozciągnij A w prawo i B w lewo, aby dowiedzieć się, gdzie się przecinają; rozciągnij B w prawo, a C w lewo, aby dowiedzieć się, gdzie się przecinają itp. Gratulacje, masz teraz ciągły i częściowy model danych.

(Lata później) częściowo-liniowe funkcje to splajny stopnia 1, co można powiedzieć większości monterów splajnu. Na przykład scipy.interpolate.UnivariateSpline może być uruchamiany z k=1 parametrem wygładzania s, z którym będziesz musiał grać - patrz scipy-interpolacja-z-splajnami-zmiennymi .
W Matlab zobacz, jak wybrać węzły .

Dodano: znalezienie optymalnych węzłów nie jest łatwe, ponieważ może istnieć wiele lokalnych optymów. Zamiast tego podajesz UnivariateSpline cel s, sumę błędu ^ 2, i pozwalasz określić liczbę węzłów. Po dopasowaniu get_residual()otrzymasz rzeczywistą sumę błędu ^ 2 i get_knots()węzłów. Niewielka zmiana smoże bardzo zmienić węzły, szczególnie w dużym hałasie - ymmv.
Wykres pokazuje dopasowanie do losowej funkcji liniowo-częściowej + szum dla różnych s.

Aby dopasować stałe częściowe, zobacz Wykrywanie kroków . Czy można tego użyć do pw liniowego? Nie wiem; rozpoczęcie od różnicowania zaszumionych danych zwiększy hałas, źle.

Mile widziane są inne funkcje testowe i / lub linki do dokumentów lub kodu. Kilka linków:
kawałek-regresja-liniowa-z-węzłami-jako-parametry
$\qquad$Splajny liniowe są bardzo wrażliwe na to, gdzie są umieszczone węzły,
wybór węzłów-dla-regresji sześciennych
$\qquad$ Jest to trudny problem i większość ludzi wybiera węzły metodą prób i błędów.
$\qquad$ Jedną z metod, która zyskuje na popularności, jest stosowanie splajnów z regresją karną.

optimal k lines
    = optimal k - 1 lines up to some x
    + cost of the last line x to the end
over x  (all x in theory, nearby x in practice)

Programowanie dynamiczne jest bardzo sprytne, ale czy można pokonać brutalną siłę + heurystykę w tym zadaniu?
Zobacz doskonałe notatki kursu Erika Demaine'a pod MIT 6.006 Wprowadzenie do algorytmów, regresja liniowa segmentowana w
Google, także zespół Johna Henry'ego.

Weź pochodną i poszukaj obszarów o niemal stałej wartości. Będziesz musiał stworzyć algorytm, aby wyszukać te obszary o idealnie pewnym poziomie nachylenia +/-, a to da ci nachylenie linii dla tej sekcji. Przed dokonaniem klasyfikacji przekrojowej może być konieczne wykonanie wygładzenia, na przykład średniej ruchomej. Następnym krokiem byłoby uzyskanie przecięcia y, które w tym momencie powinno być trywialne.

Innym pomysłem jest użycie filtru trendu L1:

Papier

Przykład online