2D Convolution w Przetwarzaniu Obrazów

Ten artykuł zapewnia wgląd w dwuwymiarowej konwolucji i zero-padding w odniesieniu do cyfrowego przetwarzania obrazu.

W moim poprzednim artykule „Lepszy wgląd w DSP: Nauka o konwolucji”, omówiłem konwolucji i jej dwóch ważnych zastosowań w dziedzinie przetwarzania sygnałów. Tam, sygnały były przypuszczalnie uważane za jednowymiarowe w domenie przestrzennej. Jednak proces konwolucji może być również przeprowadzony na sygnałach wielowymiarowych.

W tym artykule postaramy się lepiej zrozumieć proces i konsekwencje dwuwymiarowej konwolucji, szeroko stosowanej w dziedzinie przetwarzania obrazów.

Definicja konwolucji 2D

Konwolucja obejmująca sygnały jednowymiarowe jest określana jako konwolucja 1D lub po prostu konwolucja. W przeciwnym razie, jeśli konwolucja jest wykonywana między dwoma sygnałami rozpiętymi wzdłuż dwóch wzajemnie prostopadłych wymiarów (tj. jeśli sygnały są dwuwymiarowe w naturze), wtedy będzie to określane jako konwolucja 2D. Koncepcja ta może być rozszerzona o sygnały wielowymiarowe, dzięki czemu możemy mieć wielowymiarowe convolution.

W domenie cyfrowej, konwolucja jest wykonywana przez mnożenie i akumulowanie wartości chwilowych nakładających się próbek odpowiadających dwóch sygnałów wejściowych, z których jeden jest odwrócony. Ta definicja konwolucji 1D ma zastosowanie nawet do konwolucji 2D, z wyjątkiem tego, że w tym ostatnim przypadku jedno z wejść jest odwrócone dwukrotnie.

Ten rodzaj operacji jest szeroko stosowany w dziedzinie cyfrowego przetwarzania obrazu, gdzie matryca 2D reprezentująca obraz będzie konwertowana z porównywalnie mniejszą matrycą zwaną jądrem 2D.

Przykład konwolucji 2D

Spróbujmy obliczyć wartość piksela obrazu wyjściowego wynikającego ze splotu macierzy obrazu x o rozmiarze 5×5 z jądrem h o rozmiarze 3×3, pokazanym poniżej na rysunku 1.

Rysunek 1: Macierze wejściowe, gdzie x reprezentuje oryginalny obraz, a h reprezentuje jądro. Obraz stworzony przez Sneha H.L.

Aby to osiągnąć, poniżej przedstawiono procedurę krok po kroku, którą należy wykonać.

Krok 1: Odwrócenie macierzy

Krok ten obejmuje odwrócenie jądra wzdłuż, powiedzmy, wierszy, po którym następuje odwrócenie wzdłuż jego kolumn, jak pokazano na rysunku 2.

Rysunek 2: Obrazowe przedstawienie inwersji macierzy. Obraz stworzony przez Sneha H.L.

W wyniku tego każdy (i,j)th element oryginalnego jądra staje się (j,i)th elementem nowej macierzy.

Krok 2: Przesuń jądro nad obrazem i wykonaj operację MAC w każdym momencie

Nakładaj odwrócone jądro na obraz, posuwając się piksel po pikselu.

Dla każdego przypadku oblicz iloczyn wzajemnie nakładających się pikseli i oblicz ich sumę. Wynik będzie wartością piksela wyjściowego w tym konkretnym miejscu. W tym przykładzie przyjmiemy, że nienakładające się piksele będą miały wartość „0”. Omówimy to bardziej szczegółowo w następnej sekcji „Zero Padding”.

W niniejszym przykładzie zaczniemy przesuwać jądro najpierw w kierunku kolumny, a następnie wzdłuż wierszy.

Piksele Wiersz po wierszu

Najpierw obejmijmy całkowicie pierwszy rząd, a następnie przejdźmy do drugiego, i tak dalej, i tak dalej.

Podczas tego procesu pierwsze nakładanie się pikseli jądra i obrazu nastąpi, gdy piksel w prawym dolnym rogu jądra spadnie na wartość pierwszego piksela w lewym górnym rogu matrycy obrazu. Obie te wartości pikseli są wyróżnione i pokazane ciemnoczerwonym kolorem na Rysunku 3a. Tak więc pierwsza wartość piksela obrazu wyjściowego będzie wynosić 25 × 1 = 25.

Następnie przesuńmy jądro wzdłuż tego samego rzędu o jeden piksel. Na tym etapie dwie wartości macierzy jądra (0, 1 – zaznaczone ciemnoczerwoną czcionką) pokrywają się z dwoma pikselami obrazu (25 i 100 zaznaczone ciemnoczerwoną czcionką), jak pokazano na rysunku 3b. Zatem wynikowa wartość piksela wyjściowego będzie wynosić 25 × 0 + 100 × 1 = 100.

Rysunek 3a, 3b. Wyniki konwolucji uzyskane dla pikseli wyjściowych w lokalizacji (1,1) i (1,2). Obraz stworzony przez Sneha H.L.

Rysunek 3c, 3d: Wyniki konwolucji uzyskane dla pikseli wyjściowych w lokalizacji (1,4) i (1,7). Image created by Sneha H.L.

Postępując analogicznie, można obliczyć wszystkie wartości pikseli pierwszego rzędu w obrazie wyjściowym. Dwa takie przykłady odpowiadające czwartemu i siódmemu pikselowi macierzy wyjściowej są pokazane odpowiednio na rysunkach 3c i 3d.

Jeśli dalej przesuwamy jądro wzdłuż tego samego rzędu, żaden z pikseli w jądrze nie pokrywa się z pikselami w obrazie. Oznacza to, że zakończyliśmy przesuwanie wzdłuż bieżącego rzędu.

Przesuwanie w dół w pionie, przesuwanie w poziomie

Kolejnym krokiem byłoby przesuwanie w pionie w dół o jeden piksel przed ponownym rozpoczęciem przesuwania w poziomie. Pierwsze nakładanie się, które wtedy wystąpi jest jak pokazano na Rysunku 4a i wykonując operację MAC nad nimi; otrzymamy wynik jako 25 × 0 + 50 × 1 = 50.

Następnie możemy przesuwać jądro w kierunku poziomym, aż nie będzie więcej wartości, które nakładają się pomiędzy jądrem a matrycami obrazu. Jeden z takich przypadków odpowiadający szóstej wartości piksela macierzy wyjściowej (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) pokazany jest na rysunku 4b.

Rysunek 4a, 4b. Wyniki konwolucji uzyskane dla pikseli wyjściowych w lokalizacji (2,1) i (2,6). Image created by Sneha H.L.

Ten proces przesuwania o jeden krok w dół, a następnie skanowania poziomego musi być kontynuowany aż do ostatniego wiersza macierzy obrazu. Trzy losowe przykłady dotyczące pikseli wyjściowych w lokalizacjach (4,3), (6,5) i (8,6) przedstawiono na rysunkach 5a-c.

Rysunek 5a. Wyniki konwolucji uzyskane dla pikseli wyjściowych w punkcie (4,3). Obraz utworzony przez Sneha H.L.

Rysunek 5b. Wyniki konwolucji uzyskane dla pikseli wyjściowych w punkcie (6,5). Obraz utworzony przez Sneha H.L.

Rysunek 5c. Wyniki konwolucji uzyskane dla pikseli wyjściowych w punkcie (8,6). Obraz utworzony przez Sneha H.L.

Krok

Więc wynikową macierzą wyjściową będzie:

Rysunek 6. Wynikowa macierz wyjściowa dla naszego przykładu. Image created by Sneha H.L.

Zero Padding

Matematyczna formuła konwolucji 2-D jest dana przez

$$ y^suma_{m=-linfty}^^suma_{n=-linfty}^^^^fty h $$

gdzie, x reprezentuje macierz obrazu wejściowego, która ma być połączona z macierzą jądra h w celu uzyskania nowej macierzy y, reprezentującej obraz wyjściowy. Tutaj indeksy i oraz j dotyczą macierzy obrazu, natomiast indeksy m oraz n dotyczą macierzy jądra. Jeżeli rozmiar jądra biorącego udział w konwolucji wynosi 3 × 3, wówczas indeksy m i n zawierają się w przedziale od -1 do 1. Dla tego przypadku, rozwinięcie przedstawionego wzoru daje w wyniku

$$ y = suma_{m=- \$$

Wskazuje to, że aby uzyskać każdy piksel wyjściowy, należy wykonać 9 mnożeń, których czynnikami są nakładające się na siebie elementy pikseli obrazu i jądra. Tymczasem, gdy obliczaliśmy wartość dla naszego pierwszego piksela wyjściowego, wykonaliśmy tylko jedno mnożenie (Rysunek 3a powielony jako Rysunek 7a). Co to oznacza? Czy sugeruje to niezgodność z formą równania konwolucji dwuwymiarowej? Nie, nie bardzo. Ponieważ, wynik otrzymany przez sumowanie dziewięciu członów iloczynu może być równy iloczynowi jednego członu, jeżeli efekt zbiorczy pozostałych ośmiu członów iloczynu zrównuje się z zerem. Jednym z takich sposobów jest przypadek, w którym każdy z iloczynów pozostałych ośmiu terminów ocenia się na zero. W kontekście naszego przykładu oznacza to, że wszystkie terminy iloczynu odpowiadające nienakładającym się (między obrazem a jądrem) pikselom muszą stać się równe zero, aby wyniki obliczeń formułowych były równe wynikom obliczeń graficznych.

Z naszej elementarnej wiedzy matematycznej wiemy, że jeśli przynajmniej jeden z czynników biorących udział w mnożeniu jest równy zero, to wynikowy produkt jest również równy zero. Przez tę analogię, możemy stwierdzić, że w naszym przykładzie, musimy mieć zero-wartościowy obraz-piksel odpowiadający każdemu nienakładającemu się pikselowi macierzy jądra. Obrazowo można to przedstawić tak, jak na rysunku 7b. Jedną ważną rzeczą, którą należy tutaj zauważyć jest to, że takie dodanie zer do obrazu nie zmienia obrazu w żadnym sensie poza jego rozmiarem.

Rysunek 7: Zero-padding pokazany dla pierwszego piksela obrazu (narysowany przeze mnie)

Ten proces dodawania dodatkowych zer jest znany jako zero padding i jest wymagany do wykonania w każdym przypadku, gdy nie ma pikseli obrazu, które zachodzą na piksele jądra. Dla naszego przykładu, zero padding wymaga przeprowadzenia dla każdego piksela, który leży wzdłuż pierwszych dwóch wierszy i kolumn, jak również tych, które pojawiają się wzdłuż ostatnich dwóch wierszy i kolumn (te piksele są pokazane niebieską czcionką na Rysunku 8). Ogólnie rzecz biorąc, liczba wierszy lub kolumn do zerowego paddingu po każdej stronie obrazu wejściowego jest dana przez (liczba wierszy lub kolumn w jądrze – 1).

Rysunek 8

Jedną z ważnych rzeczy, o których należy wspomnieć, jest fakt, że zerowy padding nie jest jedynym sposobem radzenia sobie z efektami krawędziowymi wywołanymi przez konwolucję. Inne techniki paddingu obejmują replikację paddingu, rozszerzenie okresowe, mirroring, itp. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Podsumowanie

Ten artykuł ma na celu wyjaśnienie graficznej metody 2-D convolution i koncepcji zerowego paddingu w odniesieniu do cyfrowego przetwarzania obrazów.

.