W tym wpisie szczegółowo wyjaśniam działanie funkcji splotu, matematycznej operacji która znakomicie przydaje się w przetwarzaniu obrazów. Ponadto jest jednym z głównych bloków w sieciach konwolucyjnych.

Convolutional Neural Networks (#ConvNets) stanowią jeden z fundamentów wśród metod klasyfikacji i rozpoznawania obrazów, swoją siłę zawdzięczają właśnie wykorzystaniu warstw dokonujących operacji splotu pomiędzy obrazem (lub warstwami dolnymi) a macierzą wag w danej warstwie. Lecz zanim zaczniemy analizować architekturę sieci konwolucyjnych warto nabrać intuicji czym ta operacja jest oraz jaką rolę pełni w przetwarzaniu obrazów.

W niniejszym wpisie przeczytasz o:

• Konwolucja czyli połączenie dwóch funkcji – wyjaśniam czym jest operacja splotu? Przedstawiam formalną matematyczna definicje oraz związane z nią intuicje.
• Operacja splotu w analizie obrazów – obraz jako dyskretny sygnał dwuwymiarowy wraz z przykładem
• Implementacja splotu w Python i Numpy – napiszemy skrypt w Python i Scipy, dokonujący operacji konwolucji z kilkoma popularnymi filtrami

Konwolucja (splot) czyli połączenie dwóch funkcji

Operacja splotu po raz pierwszy do sieci neuronowych została wprowadzona w pracy LeCunn at al  [bibcite key=LeCun1989], lecz jest to operacja matematyczna, której pierwsze wzmianki przypisuje się D’Alebert’owi w 1754. Formalnie zdefiniowana jest w dość zawiły sposób z wykorzystaniem całek, lecz spróbujmy rozłożyć to na czynniki pierwsze.

Po pierwsze jest to operacja wykonywana na dwóch funkcjach np. \(f(t), g(t)\), w wyniku której otrzymamy nową funkcję  \(h(t)\). Hej, hej, stop. Jak to otrzymujemy nową funkcję? To na funkcjach można wykonywać działania? A no można, już pewnie wcześniej takie operacje wykonywałeś np. dodawanie funkcji lub mnożenie, np. niech \(f(t)=t^2,  g(t)=\sin(t)\), możemy określić działania:

\begin{align}
h(t)=&(f+g)(t)=f(t)+g(t)=t^2+\sin(t) \\\
h(t)=&(f \cdot g)(t)=f(t) \cdot g(t)=t^2\cdot\sin(t)
\end{align}

Analogicznie możemy określić działanie splotu funkcji wykorzystując szereg złożonych operacji: mnożenie funkcji, odbicie funkcji, translację oraz operacje całkowania:

$$h(t)=(f*g)(t)=\int\limits_{0}^t f(x)g(t-x) dx$$

Co to za poczwarka, skąd nagle wzięły się dwie literki \(t, x\) i jak mam rozumieć tę całkę?

1. Po pierwsze, zauważ że główną zmienną jest cały czas u nas \(t\), zmienna \(x\) służy tylko jako zmienna do całkowania, ostatecznie zniknie ona w wyniku obliczenia całki. Wyobraź sobie ze chcemy policzyć \(h(5)\), czyli wszędzie w wzorach za t podstawiamy wartość 5.
2. Pod całką obliczamy zwykły iloczyn dwóch funkcji \(f, g\) z tym, że funkcja \(g\) jest odbita względem osi OY, \(g(-x)\) oraz przesunięta o t \(g(t-x)\).
3. Na funkcję \(g(t)\) można patrzeć jak na funkcję określającą wagi dla funkcji \(f(t)\) (jak przy średniej ważonej).
4. Całkowanie można rozumieć jako zsumowanie wartości poszczególnych iloczynów z pewnej okolicy (przedzału).

Ja osobiście tłumaczę to sobie następująco, wybieram wartość \(t=t_1\), następnie wiem, że będę dokonywał sumowania wartości dla z pewnej okolicy \(t_1\), w naszym przykładzie \(x \in [0,t_1]\), dla każdej wartości z przedziału obliczam iloczyn pomiędzy \(f(x)\cdot g(t_1-x)\) oraz sumuje je. Sumowanie w tym przypadku jest określone przy pomocy całki, gdyż zmienna \(x\) jest ciągła.

Zobaczcie jak można policzyć konkretny przykład:

Bardzo pomocnym w zrozumieniu tej operacji jest przypadek dyskretny, w którym zmienne przyjmują wartości naturalne.

Splot funkcji z wartościami dyskretnymi

W tym przypadku nasze funkcje są ciągami o wyrazach \(f=\{ f[0],f[1],f[2], \dots \}\) oraz \( g=\{ g[0],g[1], g[2],\dots \}\), operację konwolucji dyskretnej możemy zdefiniować następująco:

$$(f*g)[n] =\sum _{{m }}^{{n }}f[m]\,g[n-m]$$

Tak na dobrą sprawę wzór jest taki sam, z tym że znak całki został zamieniony na znak sumy. Zakres zmiennej indeksującej \(m\) kolejno zmienia się w zależności od długości ciągu \(g\) oraz na której pozycji dla której chcemy obliczyć splot. Zobaczmy to na przykładzie, zwróćcie uwagę na różną długość ciągów oraz zmienną \(m\)

Policzmy przykład. Mamy dwa ciągi skończone \(f=\{1,0,1,1,1,0\}, g=\{1,1,0\}\), w których wyrazy numerujemy od zera, obliczmy kolejno \(h[0],h[1],…\)

\begin{align}
n=0, m&=0 \\\
h[0] &= f[0] \cdot g[0]=1 \cdot 1=1 \\\
n=1, m&=0,1 \\\
h[1]&= f[0] \cdot g[1-0]+f[1] \cdot g[1-1]=1 \cdot 1+0 \cdot 1=1 \\\
n=2, m&=0,1,2 \\\
h[2]&= f[0] \cdot g[2-0]+f[1] \cdot g[2-1]+f[2] \cdot g[2-2] \\\
&= 1 \cdot 0+0 \cdot 1+1 \cdot1=1 \\\
\end{align}

A teraz uwaga, jak policzyć \(h[3]\)? Zwróćmy uwagę, że jeden z ciągów jest krótszy, więc możemy do obliczeń wziąć tylko 3 elementy ciągu.

\begin{align}
n=3, m &=1,2,3 \\\
h[3]&=f[1]\cdot g[3-1]+f[2]\cdot g[3-2]+f[3]\cdot g[3-3]\\\
&=0\cdot 0+1\cdot 1+1\cdot 1=2
\end{align}

Pomocną techniką jest zapisanie dwóch dyskretnych sygnałów jeden nad drugim, z tym że jeden odbijamy lustrzanie, elementy nakładające się mnożymy i dodajemy do sąsiednich iloczynów.

h[0]=1
---------------
    1,0,1,1,1,0
0,1,1

h[1]=1
---------------
    1,0,1,1,1,0
  0,1,1

h[2]=1
---------------
    1,0,1,1,1,0
    0,1,1

h[3]=2
---------------
    1,0,1,1,1,0
      0,1,1
...

Powyższe przykłady, zarówno ciągły jak i dyskretny były jednowymiarowe, tzn. funkcje \(f, g\) były funkcjami jednej zmiennej. Zobaczmy jak to wygląda dla sygnału dwuwymiarowego, którego dobrym przykładem jest właśnie obraz.

Operacja splotu w analizie obrazów

Cała idea konwolucji, w głównej mierze polega na przesuwaniu okna z wartościami z \(g\) (nazwijmy tę funkcję filtrem) wzdłuż sygnału \(f\), przemnażaniu odpowiadających wartości oraz dodawaniu tych iloczynów do siebie. W przypadku dwuwymiarowym, przesuwanie to będzie odbywało się z lewej do prawej, a następnie z góry na dół, formalnie prezentuje się to następująco:

$$h[m,n]=(f*g)[m,n]=\sum _{j}\sum _{k}{f[j,k]g[m-j,n-k]} $$

W kontekście przetwarzania obrazów funkcja \(f\) jest dwuwymiarową macierzą zawierającą wartości pikseli obrazu, zazwyczaj ma ona duże wymiary np. 600x400px, natomiast funkcja \(g\), nasz filtr, jest zdecydowanie mniejszą macierzą np. 3x3px, 5x5px itp. W wyniku konwolucji obrazu z filtrem, otrzymamy nowy obraz, w którym każdy piksel \(h[m,n]\) został utworzony na podstawie jego sąsiedztwa. W zależności do wyboru filtra możemy otrzymać obraz rozmyty, wyostrzony lub z uwypuklonymi krawędziami.

Implementacja operacji splotu w Python’ie

Operacja konwolucji jest na tyle standardową operacją, że nie musimy jej sami implementować. Dwie popularne biblioteki numeryczne Numpy i Scipy mają tą operację zaimplementowaną. My na nasze potrzeby zastosujemy funkcję scipy.signal.convolve.

Wszystkie przykłady znajdują się w repo na githubie:

• https://github.com/ksopyla/image_convolution_example

Rozmycie obrazu kolorowego

Rozmycie obrazu możemy zrealizować uśredniając wartości z sąsiedztwa, stąd filtr wygląda następująco:

$$
g = \frac{1}{9}\left[\begin{array}{ccc}
1 & 1 & 1 \\\
1 & 1 & 1 \\\
1 & 1 & 1
\end{array}
\right]
$$

Wartości w macierzy zostały podzielone przez 9, tak aby sumowały się do 1. A oto skrypt realizujący tę operację:

import scipy.signal
import numpy as np
import matplotlib.pyplot as plt
from scipy import ndimage

#read image
im = plt.imread('img/building.jpg').astype(float)
im =im/255.   # normalise to 0-1, it's easier to work in float space
plt.imshow(im)

#smooth kernel  - small smooth
kernel_size=3 #try values 5,7,9
kernel = np.ones((kernel_size,kernel_size)) 
kernel/=1.0*kernel_size*kernel_size 

# convolve 2d the kernel with each channel
r = scipy.signal.convolve2d(im[:,:,0], kernel, mode='same')
g = scipy.signal.convolve2d(im[:,:,1], kernel, mode='same')
b = scipy.signal.convolve2d(im[:,:,2], kernel, mode='same')

# stack the channels back into a 8-bit colour depth image and plot it
im_out = np.dstack([r, g, b])
im_out = (im_out * 255).astype(np.uint8) 

plt.subplot(1,2,1)
plt.imshow(im, interpolation='none', cmap=plt.cm.gray)
plt.subplot(1,2,2)
plt.imshow(im_out, interpolation='none', cmap=plt.cm.gray)
plt.show()

W liniach 1-4 importujemy niezbędne biblioteki, następnie odczytujemy obraz i dzieląc przez 255 normalizujemy wartości pikseli do przedziału [0,1]. W liniach 12-14 definiujemy filtr o wymiarach 3×3, na początku definiujemy macierz składającą się z samych jedynek o później dzielimy przez ilość elementów w macierzy.
Operację konwolucji stosujemy do każdego kanału RGB oddzielnie (linie 17-19) podając do funkcji convolve2d kolejno: obraz, filtr (kernel) oraz sposób w jaki mają być obsłużone wartości na krawędziach. Następnie (linie 22-23) składamy z powrotem poszczególne kanały wyniku w obraz,  denormalizujemy wartości z [0,1] na [0,255] i rzutujemy na int.
Ostatnie linie służą wyświetleniu wyniku:

Wydobycie głębi w obrazie w odcieniach szarości

Używając odpowiednio wybranych macierzy, jesteśmy w stanie otrzymać wiele ciekawych efektów na naszym obrazie. Chcąc wyostrzyć głębię oraz krawędzie na obrazie możemy zastosować operację Emboss (wybaczcie, nie wiem jak to przetłumaczyć), wystarczy użyć następującego filtra:

$$
g = \left[\begin{array}{ccc}
-2 & -1 & 0 \\\
-1 & 1 & 1 \\\
0 & 1 & 2
\end{array}\right]
$$

Poniżej kod, który wykorzystuje powyższy filtr.

import scipy.signal
import numpy as np
import matplotlib.pyplot as plt
from scipy import ndimage

def rgb2gray(rgb):
    '''convert rgb image to gray scale, it uses formula
    gray_img = 0.299 R + 0.587 G + 0.114 B
    '''
    return np.dot(rgb[...,:3], [0.299, 0.587, 0.114])

#read image
im = plt.imread('img/wikipedia_steam.png').astype(float)
gray = rgb2gray(im)
gray /= 255
plt.imshow(gray, interpolation='none', cmap=plt.cm.gray)

#emmboss filter
kernel = np.array([[-2, -1, 0], [-1, 1, 1], [0, 1, 2]])

em_img = scipy.signal.convolve2d(gray, kernel)
em_img*=255

plt.subplot(1,3,1)
plt.imshow(im, interpolation='none', cmap=plt.cm.gray)
plt.subplot(1,3,2)
plt.imshow(gray, interpolation='none', cmap=plt.cm.gray)
plt.subplot(1,3,3)
plt.imshow(em_img, interpolation='none', cmap=plt.cm.gray)
plt.show()

Cały kod wygląda podobnie do poprzedniego przykładu, z tym że tutaj operujemy na obrazie w odcieniach szarości, kolorowy obraz (linia 16) konwertujemy na obraz w odcieniach szarości (linia 17) przy pomocy prostej zdefiniowanej przez nas funkcji (linie 6-12). W lini 23 zdefiniowane jest nasze jądro, które następnie użyte w operacji konwolucji (linia 25). Na koniec wyświetlamy trzy obrazy obok siebie, kolorowy, szary oraz wynikowy.

Podsumowanie

Wpis ten, ma na celu zapoznanie was z pojęciem konwolucji oraz praktycznym jej wykorzystaniem w przetwarzaniu obrazów. Zachęcam do zabawy z tworzeniem własnych filtrów oraz odsyłam do kilku wartościowych  materiałów w sieci, w których znajdziecie inne standardowe filtry

• http://setosa.io/ev/image-kernels/ – w ciekawy interaktywny sposób można pobawić się filtrami
• http://www.pyimagesearch.com/2016/07/25/convolutions-with-opencv-and-python/ – operacja konwolucji z wykorzystniem OpenCV
• https://docs.gimp.org/en/plug-in-convmatrix.html – kilka standardowych filtrów

Idee oraz intuicje przedstawione w tym poście mają stanowić fundament do zrozumienia konwolucyjnych sieci neuronowych, w których poszczególne filtry są wyuczane w trakcie treningu.