Splot 2

Na blogu pojawił się już kiedyś post o splocie. Odsyłam do niego, jeżeli chcecie przypomnieć sobie jak to działa. Poniżej przedstawię trochę bardziej zaawansowane techniki dokonywania splotu. Ich celem jest zwiększenie prędkości wykonania. Jest to ważne, gdyż taka operacja jest w niektórych sytuacjach wykorzystywana często, chociażby wyostrzając każdą klatkę obrazu z kamery. Każde zaoszczędzone cykle procesora w wizji się przydadzą :) 

FFT

FFT (Fast Fourier Transform, szybka transformacja Fouriera) jest operacją matematyczną pozwalającą przyspieszyć proces uzyskania sygnału w dziedzinie częstotliwościowej. Operację splotu można opisać następująco: wyznaczenie transformat Fouriera obrazu i maski, wymnożenie odpowiednich częstotliwości, wyznaczenie transformaty odwrotnej obrazu. Samo wyznaczenie sygnału w dziedzinie częstotliwościowej ma podobną złożoność obliczeniową co splot. Dzięki FFT można przyspieszyć ten uciążliwy proces. Dochodzi jednak mnożenie częstotliwości. Aby splot z FFT przyspieszył wykonywany kod, maska musi mieć odpowiednio duży rozmiar. Inną sprawą jest fakt, że do FFT najefektywniejsze są obrazy o rozmiarach będących potęgą dwójki. Niestety wykorzystanie FFT nie pozostaje bez wpływu na wyniki, które różnią się od tych uzyskanych stosując wprost wzór splotu. Są tutaj trochę inne problemy niż przy klasycznym splocie, zainteresowanych odsyłam do stosownej literatury. Kod można znaleźć w dokumentacji OpenCV.

Rozbicie operacji na mniejsze

Inną operacją pozwalającą zmniejszyć liczbę operacji jest robicie ich na mniejsze. Pewna grupa filtrów umożliwia rozbicie maski na dwa wektory. Przykładem jest filtr Sobela, którego maska wygląda następująco:

Macierz ta jest wynikiem mnożenia dwóch wektorów:

W takim przypadku można najpierw zastosować splot z jednym z wektorów a następnie na jego wyniku wykonać splot z drugim wektorem znacząco redukując przy tym liczbę mnożeń i dodawań. Do tego celu przeznaczona jest w OpenCV specjalna funkcja o nazwie sepFilter2D, bardzo podobna do filter2D z tym, że przyjmuje dwie maski, kolejno poziomą i pionową. Trzeba jednak wziąć po uwagę ewentualne pośrednie wyniki. Przy klasycznej masce Sobela mogą wystąpić wartości ujemne, natomiast w przypadku wektora [1,2,1] wykroczyć poza dopuszczalny zakres.

GPU

Inną metodą przyspieszenia splotu jest zaprzęgnięcie do obliczeń karty graficznej. OpenCV w wersji 2.2 wykorzystuje możliwości udostępnione przez firmę NVDIA w CUDA. Na marginesie sama NVIDIA zadeklarowała pomoc w rozwijaniu OpenCV. Aby dowiedzieć się więcej o programowaniu GPU polecam artykuł na wikipedii. W skrócie chodzi o fakt, że obliczenia te są mocno równoległe co znacznie przyspiesza pewien zakres operatorów matematycznych. Poza tym, odciąża ona CPU, który można wykorzystać do innych obliczeń. Samo programowanie GPU nie należy do łatwych, trzeba przestawić się na trochę inne myślenie, inaczej projektować algorytmy. Na szczęście OpenCV udostępnia uproszczone metody do działania na karcie graficznej. Znajdują się one w przestrzeni nazw gpu a zadeklarowane są w pliku nagłówkowym gpu.h. I tak mamy dwie metody dokonujące splotu:

void filter2D(const GpuMat& src,
GpuMat& dst,
int ddepth,
const Mat& kernel,
Point anchor=Point(-1,-1));

void sepFilter2D(const GpuMat& src,
GpuMat& dst,
int ddepth,
const Mat& kernelX,
const Mat& kernelY,
Point anchor = Point(-1,-1),
int rowBorderType = BORDER DEFAULT,
int columnBorderType = -1);

Najistotniejsza zmiana to wykorzystanie GpuMat zamiast Mat. Jest to spowodowane innym rodzajem pamięci dostępnej w GPU. Dla nas najważniejsze jest to, że można łatwo zamieniać jedną na drugą. Dostępny jest konstruktor GpuMat przyjmujący jako parametr referencję do Mat, oraz dwie metody pozwalające na przesyłanie danych i pobieranie ich:

void upload(const cv::Mat& m); // pobranie wartości z m
void download(cv::Mat& m) const; // zapisanie wartości do m

Same metody fiter2d oraz sepFilter2D działają tak samo jak ich "normalne" odpowiedniki. Trzeba tylko pamiętać, że na karcie graficznej dostępne są jedynie tablice floatów, więc przesłanie w GpuMat wartości typu uchar spowoduje błąd. Podobno autorzy mają usunąć to ograniczenie w przyszłości. Ponadto samo przesyłanie danych, ich odczyt a nawet samo zainicjowanie korzystania z GPU ma pewien narzut, więc przydaje się ono w często wykorzystywanych splotach, lub tych z wykorzystaniem wielki obrazów i masek. Na koniec małe porównanie czasu wykonania stu splotów z obrazem 800 na 600 pikseli  pomiędzy CPU a GPU (testowano na Intel C2D 2,4 GHz i GeForce 9600 GT)
CPU:

                filter2D   sepFilter2D
maska 3x3:       1,04s        0,40s
maska 15x15:     3,90s        2,99s  

GPU:

                filter2D   sepFilter2D
maska 3x3:       0,01s        0,28s
maska 15x15:     0,06s        0,69s