Jak wdraża się rozmycie gaussowskie?

Czytałem, że rozmycie odbywa się w grafice w czasie rzeczywistym, robiąc to na jednej osi, a potem na drugiej.

W przeszłości przeprowadzałem trochę splotu w 1D, ale nie czuję się z tym zbyt dobrze, ani nie wiem, co dokładnie splotć w tym przypadku.

Czy ktoś może wyjaśnić w prosty sposób, w jaki sposób wykonuje się rozmycie Gaussa 2D obrazu?

Słyszałem również, że promień rozmycia może mieć wpływ na wydajność. Czy to z powodu konieczności większego splotu?

W trakcie splotu dwie funkcje matematyczne są łączone, aby uzyskać trzecią funkcję. W przetwarzaniu obrazu funkcje są zwykle nazywane jądrem. Jądro to nic innego jak (kwadratowa) matryca pikseli (mały obraz, że tak powiem). Zwykle wartości w jądrze sumują się do jednego. Ma to na celu upewnienie się, że po operacji energia nie zostanie dodana ani usunięta z obrazu.

W szczególności jądro Gaussa (używane do rozmycia Gaussa) to kwadratowa tablica pikseli, w której wartości pikseli odpowiadają wartościom krzywej Gaussa (w 2D).

Każdy piksel na obrazie jest mnożony przez jądro Gaussa. Odbywa się to poprzez umieszczenie środkowego piksela jądra na pikselu obrazu i pomnożenie wartości w oryginalnym obrazie przez piksele w jądrze, które się nakładają. Wartości wynikające z tych multiplikacji są sumowane i ten wynik jest wykorzystywany jako wartość piksela docelowego. Patrząc na obraz, pomnożysz wartość at (0,0) w tablicy wejściowej przez wartość at (i) w tablicy jądra, wartość at (1,0) w tablicy wejściowej przez wartość at (h ) w tablicy jądra i tak dalej. a następnie dodaj wszystkie te wartości, aby uzyskać wartość (1,1) na obrazie wyjściowym.

Aby odpowiedzieć na drugie pytanie w pierwszej kolejności, im większe jądro, tym droższa operacja. Im większy promień rozmycia, tym dłużej potrwa operacja.

Aby odpowiedzieć na pierwsze pytanie, jak wyjaśniono powyżej, splot można wykonać, mnożąc każdy piksel wejściowy przez całe jądro. Jeśli jednak jądro jest symetryczne (którym jest jądro Gaussa), można również pomnożyć każdą oś (x i y) niezależnie, co zmniejszy całkowitą liczbę mnożenia. W kategoriach matematycznych, jeżeli macierz można oddzielić, można ją rozłożyć na macierze (M × 1) i (1 × N). W przypadku jądra Gaussa powyżej oznacza to, że można również użyć następujących jąder:

$$\frac1{256}\cdot\begin{bmatrix} 1&4&6&4&1\\ 4&16&24&16&4\\ 6&24&36&24&6\\ 4&16&24&16&4\\ 1&4&6&4&1 \end{bmatrix} = \frac1{256}\cdot\begin{bmatrix} 1\\4\\6\\4\\1 \end{bmatrix}\cdot\begin{bmatrix} 1&4&6&4&1 \end{bmatrix}$$

Teraz pomnożysz każdy piksel na obrazie wejściowym przez oba jądra i dodasz wartości wynikowe, aby uzyskać wartość piksela wyjściowego.

Aby uzyskać więcej informacji o tym, jak sprawdzić, czy jądro można oddzielić, kliknij ten link .

Edycja: dwa pokazane powyżej jądra używają nieco innych wartości. Wynika to z faktu, że parametr (sigma) zastosowany dla krzywej Gaussa do utworzenia tych jąder był nieco inny w obu przypadkach. Aby wyjaśnić, które parametry wpływają na kształt krzywej Gaussa, a zatem wartości w jądrze podążają za tym linkiem

Edycja: na drugim obrazku powyżej jądro mówi, że używane jądro jest odwrócone. To oczywiście robi różnicę tylko wtedy, gdy używane jądro nie jest symetryczne. Powód, dla którego musisz przerzucić jądro, wynika z matematycznych właściwości operacji splotu ( więcej informacji na ten temat znajdziesz w linku ). Mówiąc wprost: jeśli nie przerzucisz jądra, wynik operacji splotu zostanie odwrócony. Odwracając jądro, otrzymujesz poprawny wynik.

Oto najlepszy artykuł, jaki przeczytałem na ten temat: Efektywne rozmycie gaussowskie z liniowym próbkowaniem . Odpowiada na wszystkie pytania i jest naprawdę dostępny.

Dla laika bardzo krótkie wyjaśnienie: gaussowska jest funkcją o przyjemnej właściwości rozdzielności, co oznacza, że ​​2D funkcja Gaussa może być obliczona przez połączenie dwóch funkcji Gaussa 1D.

Tak więc dla rozmiaru ( ) wystarczy oszacować wartości ( ), co jest znacznie mniejsze. Jeśli twoja operacja polega na odczytaniu elementu tekstury (powszechnie nazywanego „stukaniem” ), to dobra wiadomość: mniej stuknięć jest tańsze, ponieważ pobieranie tekstury ma swój koszt.$n \times n$$O(n^2)$$2 \times n$$O(n)$

Właśnie dlatego algorytmy rozmycia wykorzystują tę właściwość, wykonując dwa przejścia, jeden do rozmycia w poziomie poprzez zebranie poziomych pikseli, a drugi do rozmycia w pionie poprzez zebranie pionowych pikseli. Wynikiem jest końcowy rozmazany kolor piksela.$n$$n$

Ogólnie rzecz biorąc, splot odbywa się poprzez pobranie całki iloczynu dwóch funkcji w przesuwanym oknie, ale jeśli nie jesteś z matematyki, nie jest to bardzo pomocne wyjaśnienie, a na pewno nie da ci użytecznej intuicji dla tego. Bardziej intuicyjnie, splot pozwala wielu punktom w sygnale wejściowym wpływać na pojedynczy punkt na sygnale wyjściowym.

Ponieważ nie czujesz się komfortowo ze zwojami, najpierw przeanalizujmy, co oznacza zwoje w takim dyskretnym kontekście, a następnie przejdźmy do prostszego rozmycia.

W naszym dyskretnym kontekście możemy pomnożyć nasze dwa sygnały, po prostu mnożąc każdą odpowiednią próbkę. Całka jest również łatwa do wykonania dyskretnie, po prostu dodajemy każdą próbkę w przedziale, który integrujemy. Jednym prostym dyskretnym splotem jest obliczanie średniej ruchomej. Jeśli chcesz wziąć średnią ruchomą 10 próbek, można to potraktować jako splot sygnału przez rozkład 10 próbek o długości i 0,1 wysokości, każda próbka w oknie jest najpierw mnożona przez 0,1, a następnie wszystkie 10 są dodawane razem, aby uzyskać Średnia. Ujawnia to również interesujące i ważne rozróżnienie, gdy rozmycie następuje w wyniku splotu, rozkład, którego używasz, powinien sumować się do 1,0 na wszystkich jego próbkach, w przeciwnym razie zwiększy lub zmniejszy ogólną jasność obrazu po jego zastosowaniu.

Teraz, gdy spojrzeliśmy na zwoje, możemy przejść do rozmycia. Rozmycie gaussowskie jest realizowane przez zwoje obrazu według rozkładu Gaussa. Inne rozmycia są generalnie realizowane przez zwoje obrazu przez inne dystrybucje. Najprostszym rozmyciem jest rozmycie pudełka i wykorzystuje ono ten sam rozkład, który opisaliśmy powyżej, pudełko z polem jednostkowym. Jeśli chcemy rozmazać obszar 10x10, mnożymy każdą próbkę w polu przez 0,01, a następnie sumujemy je wszystkie razem, aby uzyskać środkowy piksel. Nadal musimy upewnić się, że całkowita suma wszystkich próbek w naszym rozkładzie rozmycia wynosi 1,0, aby upewnić się, że obraz nie będzie jaśniejszy ani ciemniejszy.

Rozmycie gaussowskie odbywa się zgodnie z tą samą szeroką procedurą, co rozmycie pudełkowe, ale używa bardziej złożonej formuły do ​​określania wag. Rozkład można obliczyć na podstawie odległości od centrum r, oceniając Suma wszystkich próbek w Gaussa ostatecznie będzie wynosić około 1,0, jeśli próbkujesz każdy pojedynczy piksel, ale fakt, że Gaussian ma nieskończoną obsługę (ma wartości wszędzie) oznacza, że ​​musisz użyć nieco zmodyfikowanej wersji, która sumuje się do 1,0 przy użyciu tylko kilku wartości.

$$\frac{e^{-x^2/2}}{\sqrt{2\pi}}$$

Oczywiście oba te procesy mogą być bardzo kosztowne, jeśli wykonasz je w bardzo dużym promieniu, ponieważ musisz próbkować wiele pikseli, aby obliczyć rozmycie. Tu pojawia się ostatnia sztuczka: zarówno rozmycie gaussowskie, jak i rozmycie pudełkowe są tak zwane rozmycie „możliwe do oddzielenia”. Oznacza to, że jeśli wykonasz rozmycie wzdłuż jednej osi, a następnie wykonasz je wzdłuż drugiej osi, uzyskasz dokładnie taki sam wynik, jak gdybyś wykonał to wzdłuż obu osi jednocześnie. Może to być niezwykle ważne. Jeśli twoje rozmycie ma szerokość 10 pikseli, wymaga 100 próbek w naiwnej formie, ale tylko 20 po oddzieleniu. Różnica tylko się powiększa, ponieważ połączone rozmycie to , podczas gdy oddzieloną formą jest .$O(n^2)$$O(n)$

Najważniejszą rzeczą do rozważenia przy wdrażaniu rozmycia Gaussa jest, jak zauważyli inni, rozdzielenie filtra splotu 2D na dwa sploty 1D, ponieważ zmniejsza złożoność z do .$O(n^2)$$O(n)$

Istnieją jednak jeszcze dwie sztuczki, które warto rozważyć w rzeczywistej implementacji:

Filtr ma określony promień i dlatego na samym brzegu należy obliczyć za pomocą pikseli, które wypadają poza obrazem. W takim przypadku możesz wypróbować jedną z następujących czynności: w przypadku pikseli zewnętrznych po prostu bierzesz ostatnią możliwą wartość (tj. Piksel na samej granicy, jak w max(x, 0). Lub możesz „odbić” obraz na zewnątrz (jak w x < 0 ? -x : x). Lub możesz po prostu zatrzymać się na granicy, ale wtedy musisz dostosować mianownik w filtrze splotowym, aby sumował się do 1. Na przykład:

$$\operatorname{sum} \frac{1}{256} \begin{bmatrix} 1 & 4 & 6 & 4 & 1 \\ 4 & 16 & 24 & 16 & 4 \\ 6 & 24 & 36 & 24 & 6 \\ 4 & 16 & 24 & 16 & 4 \\ 1 & 4 & 6 & 4 & 1 \\ \end{bmatrix} = \operatorname{sum} \frac{1}{225} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 16 & 24 & 16 & 0 \\ 0 & 24 & 36 & 16 & 0 \\ 0 & 16 & 24 & 16 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} = 1.$$ Kolejna sztuczka dotyczy sposobu obliczania faktycznych współczynników jądra. Oczywiście można spróbować zaimplementować funkcję Gaussa, ale znacznie szybszym sposobem jest zaobserwowanie, że jądro 1D przypomina trójkąt Pascala . Na przykład:

     1
    1 1
   1 2 1
  1 3 3 1
[1 4 6 4 1]