Konvoluutiolaskentaa käytetään algoritmissa sisääntulevien kuvien suodatukseen.
Koska konvoluutio suoritetaan jokaiselle kuvalle, on se yksi tehokkuuden kannalta tärkeimmistä osuuksista.

\section{Konvoluution matemaattinen kuvaus}
\addmglos{$g(x, y)$}{Konvoluution tulos pikselille, joka on kohdassa $(x, y)$.}
\addmglos{$f(x, y)$}{Algoritmille syötetyn kuvan pikseliarvo kohdassa $(x, y)$.}
Kuvankäsittelyssä kaksiulotteinen konvoluutio tarkoittaa kuvan pikseliarvojen kertomista kerneliksi kutsutun matriisin mukaisilla painokertoimilla.
Matemaattisesti tuloskuvan pikselin määräävä funktio $g(x, y)$ riippuu lähtökuvan pikseleistä $f(x, y)$ ja kernelin arvoista $k(x', y')$ seuraavasti:
\begin{equation}
\label{eq_convolution}
g(x, y) = \sum_{x'} \sum_{y'} f(x + x', y + y') \cdot k(x',y')
\end{equation}

Määritelmän voi esittää myös matriisimuodossa, mutta käytetty esitystapa on kuvankäsittelyn näkökulmasta havainnollisin.
Käytettävien kuvan ja kernelin koot rajoittavat funktioiden määrittelyalueet ja summien välit äärellisiksi.
Tavallisesti kernelin koko on pienempi kuin kuvan, esimerkiksi $5\times5$ arvoa, jolloin summat ovat välillä $x', y' \in [-2,2]$. Laskentaa on havainnollistettu esimerkillä kuvassa \ref{fig_konvperiaate}.

\begin{figure}[tb]
\centering
\input{fig_konvperiaate.tex}
\caption{Konvoluution periaate.
Tuloskuvan oikean yläkulman pikseliarvon laskemiseksi jokainen kernelin arvo kerrotaan vastaavalla lähtökuvan pikselillä. Kertolaskujen tulokset lasketaan yhteen ja pyöristetään kokonaisluvuksi.
Reunimmaiset pikselit riippuvat käytetystä reuna-alueiden käsittelytavasta.}
\label{fig_konvperiaate}
\end{figure}

\addmglos{$w$}{Kuvan leveys.}
\addmglos{$h$}{Kuvan korkeus.}
\addmglos{$k$}{Konvoluutiokernelin koko, sama kumpaankin suuntaan.}
\addmglos{$c$}{Kuvan värikanavien määrä.}
Konvoluutio vaatii perusmuodossaan yhden kertolaskun jokaista pikseliä ja kernelin arvoa kohti.
Värikuvalle konvoluutiolaskenta suoritetaan erikseen kullekin värikanavalle.
Kokonaisuutena kertolaskujen määrä on siis $w \cdot h \cdot k^2 \cdot c$, jossa $w$ ja $h$ ovat kuvan leveys ja korkeus, $k$ kernelin koko kuhunkin suuntaan ja $c$ värikanavien määrä.
Yhteenlaskujen määrä on sama, koska jokainen kertolaskun tulos lisätään summamuuttujaan.

\subsection{Reuna-alueiden käsittely}
Kuvan reuna-alueilla lähtökuvassa ei ole kaikkia kernelin painokertoimia vastaavia pikseleitä. Näiden pikselien käsittelyyn on useita tapoja, jotka on esitetty myös kuvassa \ref{fig_blur}:
\begin{enumerate}[a)]
\item Kuvan ulkopuolisten pikseliarvojen olettaminen nollaksi eli täyttäminen mustalla.
Sumennuksessa tämä menetelmä aiheuttaa virheen reuna-alueille.

\item Kuvan reuna-alueiden laskematta jättäminen, jolloin syntyvä tuloskuva on lähtökuvaa pienempi.

\item Kuvan jatkaminen kopioimalla reunimmaiset pikseliarvot kuvan ulkopuolelle.

\item Kuvan toistaminen käyttämällä kuvan vastapäisellä reunalla olevia pikseliarvoja.
\end{enumerate}

\begin{figure}[tb]
\centering
\subfigure[][Täyttö mustalla]{\label{fig_blur_none}\includegraphics[width=3cm]{bluredges_none.png}}
\subfigure[][Leikkaaminen]{\label{fig_blur_crop}\includegraphics[width=3cm]{bluredges_crop.png}}
\subfigure[][Jatkaminen]{\label{fig_blur_padding}\includegraphics[width=3cm]{bluredges_padding.png}}
\subfigure[][Toistaminen]{\label{fig_blur_wrap}\includegraphics[width=3cm]{bluredges_wrap.png}}
\caption{Vertailu konvoluution reuna-alueiden käsittelytavoista sumennuksen yhteydessä. Ylempi kuva on lähtökuva kullakin täydennystavalla käsiteltynä, ja alempi kuva on tulos.}
\label{fig_blur}
\end{figure}

Näistä toteutukseen valittiin tuettavaksi reuna-alueiden jatkaminen ja reunojen leikkaaminen.
Reuna-alueiden jatkaminen tuottaa luonnollisen tuloksen sumennusta käytettäessä, ja on ollut algoritmissa jo aiemmin käytössä.
Leikkaamisen toteutus puolestaan on yksinkertainen ja on hyödyllinen käsiteltäessä pienempää aluetta suuresta kuvasta.

\subsection{Separoituvat kernelit}
\newcommand{\X}{\mathbf{X}}
\newcommand{\Y}{\mathbf{Y}}
\newcommand{\U}{\mathbf{U}}
\newcommand{\V}{\mathbf{V}}
Useat käytännön kannalta olennaiset kernelit, kuten Gaussian-sumennus ja keskiarvosuodatus, voidaan jakaa pystyvektorin $\Y$ ja vaakavektorin $\X$ tuloksi seuraavasti:
\[
k(x', y') = \X_{x'} \cdot \Y_{y'}
\]

Tällöin konvoluutio voidaan suorittaa kahdessa osassa, eli erikseen vaaka- ja pystysuunnassa.
Myöhemmin havaitaan, että toteutuksen kannalta pystysuunnan konvoluutio on hyödyllistä suorittaa ensin. 
Tulos on yhtenevä aikaisemman konvoluution määritelmän kanssa:
\begin{align*}
g_1(x, y) &= \sum_{y'} f(x, y + y') \cdot \Y_{y'} \\
g(x, y) &= \sum_{x'} g_1(x + x', y) \cdot \X_{x'} \\
       &= \sum_{x'} \left( \sum_{y'} f(x + x', y + y') \cdot \Y_{y'} \right) \cdot \X_{x'} \\
       &= \sum_{x'} \sum_{y'} f(x + x', y + y') \cdot
            \underbrace{\Y_{y'} \cdot \X_{x'}}_{=\,k(x', y')}
\end{align*}

Kummassakin osiossa tarvitaan nyt jokaista pikseliarvoa kohti $k$ kertolaskua, eli yhteensä vain $2k$ aiemman $k^2$ sijaan.
Ero laskutoimitusten määrässä on esimerkiksi $5\times5$ kernelillä 2,5-kertainen ja $15\times15$ kernelillä 7,5-kertainen. Separoituvan kernelin käyttö on esitetty myös kuvassa \ref{fig_sep}.

\begin{figure}[h]
\centering
\begin{tikzpicture}
\node (start) {\includegraphics[width=3cm]{sep_start.png}};
\node (convolve1) [right=0.5cm, draw, shape=circle] at (start.east) {\Large $\ast$};
\node (yconv) [right=0.5cm] at (convolve1.east) {\includegraphics[width=3cm]{sep_yconv.png}};
\node (convolve2) [right=0.5cm, draw, shape=circle] at (yconv.east) {\Large $\ast$};
\node (result) [right=0.5cm] at (convolve2.east) {\includegraphics[width=3cm]{sep_result.png}};

\node [above] at (start.north) {Lähtökuva};
\node [above, text width=10em, text centered] at (yconv.north) {Pystysuunnassa\\ tehty konvoluutio};
\node [above] at (result.north) {Tuloskuva};

\node (kernel1) [below=1cm] at (convolve1.south) {
\small$\begin{bmatrix}
    0.2 \\ 0.2 \\ 0.2 \\ 0.2 \\ 0.2 \\
\end{bmatrix}$
};

\node (kernel2) [below=1cm] at (convolve2.south) {
\small$\begin{bmatrix}
    0.2 & 0.2 & 0.2 & 0.2 & 0.2 \\
\end{bmatrix}$
};

\draw [->,thick] (start)--(convolve1);
\draw [->,thick] (kernel1)--(convolve1);
\draw [->,thick] (convolve1)--(yconv);
\draw [->,thick] (yconv)--(convolve2);
\draw [->,thick] (kernel2)--(convolve2);
\draw [->,thick] (convolve2)--(result);

\node (label) [text width=10em, text centered] at (kernel2.south |- kernel1.east)
{Kernelin separointi};

\node (orig) [below=0.5cm] at (label.south) {
\small$\begin{bmatrix}
    0.04 & 0.04 & 0.04 & 0.04 & 0.04 \\
    0.04 & 0.04 & 0.04 & 0.04 & 0.04 \\
    0.04 & 0.04 & 0.04 & 0.04 & 0.04 \\
    0.04 & 0.04 & 0.04 & 0.04 & 0.04 \\
    0.04 & 0.04 & 0.04 & 0.04 & 0.04 \\
\end{bmatrix}$
};

\node (origlabel) [below=0.1cm, inner sep=0] at (orig.south) {Alkuperäinen kerneli};

\draw [->,dashed] (orig)--(label);
\draw [->,dashed] (label)--(kernel1);
\draw [->,dashed] (label)--(kernel2);
\end{tikzpicture}
\caption{Separoidun kernelin käyttäminen. Kun konvoluutio suoritetaan kahdessa osassa, kertolaskuja tarvitaan vähemmän. Kuvassa konvoluutiota on merkitty asteriskilla $\ast$.}
\label{fig_sep}
\end{figure}

\subsubsection{Separoidun kernelin laskeminen}
Separoituvuuden hyödyntämiseksi ohjelman täytyy pystyä testaamaan, voidaanko annettu kerneli jakaa pysty- ja vaakavektoreiksi, sekä laskemaan nämä vektorit.
Tämä voidaan toteuttaa esimerkiksi pääakselihajotelman (engl. Singular Value Decomposition) avulla \cite{mathworks_separable}.
Pääakselihajotelman toteuttaminen ilman ulkoista lineaarialgebrakirjastoa olisi kuitenkin hyvin työlästä, joten alla esitetty yksinkertainen rivin ja sarakkeen valintaan perustuva menetelmä on parempi. Menetelmää ei ole kuitenkaan kuvattu kirjallisuuslähteissä, joten sen todistus on esitetty alla.

Valitaan $x_0$ ja $y_0$ siten, että $k(x_0, y_0) \neq 0$. Tällaiset indeksit ovat olemassa ellei kerneli sisällä pelkkää nollaa.
Separoidut vaaka- ja pystyvektorit ovat tällöin
\begin{align}
\X_{x'} &= \frac{1}{k(x_0, y_0)}\;k(x', y_0) \label{eq_sepx} \\
\Y_{y'} &= k(x_0, y') \label{eq_sepy}\text{ .}
\end{align}
Separoituvuus voidaan testata yksinkertaisesti kertomalla vektorit $\X$ ja $\Y$ ja vertaamalla tulosta alkuperäiseen kerneliin.

\begin{proof}
Oletetaan, että annettu kerneli on separoituva eli on olemassa vektorit $\U$ ja $\V$ siten, että kernelin arvo $k(x', y') = \U_{x'} \cdot \V_{y'}$ kaikilla indekseillä $x'$ ja $y'$.
Tällöin todistettavina olevien kaavojen \ref{eq_sepx} ja \ref{eq_sepy} tulokset ovat
\begin{align*}
X_{x'} &= \frac{1}{k(x_0, y_0)}\;k(x', y_0)
    = \frac{1}{\U_{x_0} \cdot \V_{y_0}}\;\U_{x'}\cdot\V_{y_0} \\
Y_{y'} &= \ldots = \U_{x_0}\cdot\V_{y'}
\end{align*}
Tällä kernelillä suoritetun konvoluution tulos on
\begin{align*}
g(x, y) &= \sum_{x'} \sum_{y'} f(x + x', y + y') \cdot \X_{x'} \cdot \Y_{y'} \\
&= \sum_{x'} \sum_{y'} f(x + x', y + y') \cdot \frac{1}{\U_{x_0} \cdot \V_{y_0}} \cdot \U_{x'}\cdot\V_{y_0} \cdot \U_{x_0}\cdot\V_{y'} \\
&= \sum_{x'} \sum_{y'} f(x + x', y + y') \cdot \U_{x'} \cdot \V_{y'}
\end{align*}
eli sama kuin alkuperäisellä kernelillä saatu. \qedhere
\end{proof}

\section{Toteutustapa}
Konvoluution toteutuksessa pääpaino on ollut laskennan nopeuttamisessa kokonaislukujen ja SSE2-käskykannan käytöllä. Laskenta suoritetaan 8- ja 16-bittisillä kokonaisluvuilla 16 tavun lohkoissa, mikä suoraan nostaa nopeuden moninkertaiseksi verrattuna jokaisen pikselin laskemiseen erikseen. Lisäksi kuva jaetaan pystysuunnassa osiin eri prosessoreilla käsiteltäväksi.

Tietyillä kerneleillä laskentaa voidaan nopeuttaa. Separoituvat kernelit tunnistetaan automaattisesti, ja tällöin käytetään niille optimoitua toteutusta. Separoituvuudesta saatava etu riippuu kernelin koosta, ja mittausten perusteella esimerkiksi $5\times5$ kernelillä nopeus puolitoistakertaistuu. Myös yksikkökerneli, jolla tehty konvoluutio ei muuta kuvaa, tunnistetaan ja tällöin konvoluutio ohitetaan.
Tämänkin nopeusetu on melko pieni, sillä pullonkaulaksi muodostuu kuvan summaaminen varianssipuskuriin.

Ohjelmakoodia on nopeutettu myös hyödyntämällä kääntäjän automaattisia optimointeja.
Esikääntäjämakrojen avulla algoritmista käännetään erillinen versio jokaiselle pikseliformaatille, jolloin ajonaikaiset vertailut vähenevät. Lisäksi reuna-alueiden tarkistuksia ei tehdä kuvan keskiosassa, vaan ainoaan reunimmaisissa lohkoissa.

\subsection{Kokonaislukulaskenta}
Algoritmin käsittelemät pikseliarvot ovat valmiiksi 8-bittisiä kokonaislukuja.
Laskentaa varten myös liukulukuina annetut kernelin arvot on skaalattava jollain vakiolla, ja pyöristettävä lähimpään kokonaislukuun.

Kernelin arvot ovat tavallisesti välillä $[0, 1]$, mutta esimerkiksi reunantunnistuksessa arvot voivat vaihdella laajemmalla alueella ja myös negatiivisiksi. Parhaan tarkkuuden saamiseksi skaalauskerroin kannattaa siis sovittaa käytettävään kerneliin.

\subsubsection{Ehdot skaalauskertoimelle}
Konvoluutiota laskettaessa pikseliarvojen summa kerätään etumerkilliseen 16-bittiseen muuttujaan saturoivan yhteenlaskukäskyn avulla. Laskutavasta johtuen kernelin arvoille on tiettyjä rajoituksia joilla vältetään laskutoimitusten ennenaikainen saturoituminen.

Konvoluution 16-bittisen summan maksimiarvo on \code{0x7FFF}. 
Jotta tämä vastaisi suurinta pikseliarvoa 255, voi skaalauskerroin olla enintään
127. Summan saturoitumista käytetään hyödyksi siten, että kernelin arvojen
summa voi olla yli 127, jolloin liian suuret tulokset leikkaantuvat suurimpaan
mahdolliseen arvoon.

Saturoituva yhteenlasku suoritetaan vasta kertolaskun jälkeen, joten kertolaskun
ylivuodon välttämiseksi itseisarvoltaan suurin kernelin arvo saa olla skaalattuna
enintään $\pm127$. Tällöin 8-bittisen pikseliarvon kanssa tehtävän kertolaskun
tulos mahtuu 16 bittiin.

Saturoitumista ei voida kuitenkaan käyttää jos kernelissä on negatiivisia arvoja.
Tällöin summa voisi saturoitua kesken laskutoimituksen ja myöhempi vähennyslasku
tuottaisi väärän tuloksen. Siksi negatiivisia arvoja sisältävien kernelien
kanssa täytyy tarkistaa, että skaalattujen positiivisten arvojen summa on
enintään 127, ja vastaavasti skaalattujen negatiivisten arvojen summa enintään -127.

\begin{figure}[tb]
\centering
\begin{tikzpicture}[ampersand replacement=\&]
\matrix (floatkernel) [matrix of nodes, nodes={draw, font=\scriptsize, minimum size=7mm}]
{
    1/9 \& 1/9 \& 1/9 \\
    1/9 \& 1/9 \& 1/9 \\
    1/9 \& 1/9 \& 1/9 \\
};
\node (errors) [below=1cm] at (floatkernel.south)
{
\small
\begin{tabular}{r|r}
$s$ & $\sum e^2$ \\
\hline
127 & 0,11 \\
126 & 0,00 \\
125 & 7,11 \\
124 & 5,44 \\
\end{tabular}
};

\node (multiply) [right=1cm, draw, shape=circle] at (floatkernel.east) {$\times$};

\matrix (intkernel) [right=1cm, matrix of nodes, nodes={draw, font=\scriptsize, minimum size=7mm}]
at (multiply.east)
{
    14 \& 14 \& 14 \\
    14 \& 14 \& 14 \\
    14 \& 14 \& 14 \\
};

\node [above, text width=10em, text centered] at (floatkernel.north) {Kerneli\\ liukulukuina};
\node (terrors) [above, text width=10em, text centered] at (errors.north) {Pyöristysvirheet};
\node [above, text width=10em, text centered] at (intkernel.north) {Kerneli\\ kokonaislukuina};

\draw [->,thick] (floatkernel) -- (terrors);
\draw [->,thick] (errors.east) -| (multiply)
    node [pos=0.2,above=0mm,font=\scriptsize] {$s = 126$};
\draw [->,thick] (floatkernel) -- (multiply);
\draw [->,thick] (multiply) -- (intkernel);

\node (convolve) [right=3cm, draw, shape=circle] at (intkernel.east) {\Large $\ast$};
% \node [right] at (convolve.east) {\scriptsize Konvoluutio};
\node (input) [above=1cm] at (convolve.north) {Lähtökuva};
\node (divide) [below=1cm, draw, shape=circle] at (convolve.south) {$\div$};
\node (result) [below=1cm] at (divide.south) {Tuloskuva};

\draw [dashed] (-1.5cm,2.5cm) rectangle (7.5cm,-5cm);
\node [above] at (3cm,2.5cm) {Alustusfunktiossa};

\draw [dashed] (8cm,2.5cm) rectangle (12cm,-5cm);
\node [above] at (10cm,2.5cm) {Jokaiselle kuvalle};

\draw [->,thick] (errors.east) -- +(7cm,0) -- (divide);
\draw [->,thick] (intkernel) -- (convolve);
\draw [->,thick] (input) -- (convolve);
\draw [->,thick] (convolve) -- (divide);
\draw [->,thick] (divide) -- (result);
\end{tikzpicture}

\caption{Skaalauskertoimen $s$ käyttö konvoluutiossa. Kuvassa on esitetty skaalauskertoimen valinta pyöristysvirheiden perusteella, kernelin pyöristys sekä tuloksen jakaminen. Pyöristysvirhe $\sum e^2$ on tässä tapauksessa 0, sillä 126 on jaollinen 9:llä.}
\label{fig_convscale}
\end{figure}

\subsubsection{Skaalauskertoimen valinta}
Skaalauskertoimen valinnalla pyritään minimoimaan pyöristysvirheet kernelin arvoissa.
Kerneli on laskennan ajan kiinteä, eikä alustukseen kuluvalla ajalla ole suurta merkitystä.
Lisäksi mahdollisia skaalauskertoimen arvoja on enimmillään 127 yllä esitetyistä ehdoista johtuen.

Skaalauskertoimen yläraja $\hat{s}$ saadaan määritettyä suoraan ehtojen perusteella.
Alustuksessa käydään läpi kaikki skaalauskertoimen kokonaislukuarvot $s \in [2, \hat{s}]$ ja lasketaan pyöristysvirheistä johtuvan virheen neliösumma. Skaalauskertoimeksi valitaan se arvo, joka tuottaa pienimmän virheen.

Koko ketju skaalauskertoimen valinnasta sen käyttöön on esitetty kuvassa \ref{fig_convscale}.

\subsection{Keskialueen laskenta}
Kuvan keskialueella konvoluution laskenta on yksinkertaisin, koska reuna-alueita
ei ole huomioitavana. Tuloskuva muodostuu 16 tavun lohkoista, joista kukin lasketaan seuraavasti:
\begin{enumerate}
\item Alustetaan muuttujat \code{sum\_low} ja \code{sum\_high} nollaksi.
\item \label{conv_kerniter} Käydään jokainen kernelin indeksi läpi. Jos indeksiä vastaava kernelin arvo ei ole nolla:
\begin{enumerate}
\item \label{conv_load} Ladataan kernelin indeksiä vastaavasta kohdasta 16 tavun lohko lähtökuvaa muistiin.
\item Pikseliarvoille ja kernelin kokonaislukuarvolle suoritetaan 16-bittinen etumerkillinen kertolasku.
\item \label{conv_addtosum} Kertolaskun tulos lisätään summamuuttujiin 16-bittisellä saturoituvalla yhteenlaskulla.
\end{enumerate}
\item Summa jaetaan skaalauskertoimella $s$ kertolaskun avulla:
\begin{enumerate}
\item \label{conv_round} Summaan lisätään puolet skaalauskertoimesta.
\item \label{conv_mult} Summa kerrotaan skaalauskertoimen käänteisluvulla $(256\cdot256)/s$ ja
tuloksesta jätetään pois 16 alinta bittiä.
\end{enumerate}
\item Summat palautetaan etumerkittömiksi 8-bittisiksi luvuiksi siten, että ylimenevät arvot
saturoituvat.
\item Tulos tallennetaan tuloskuvan seuraaviin 16 tavuun, ja paikkalaskuria
kasvatetaan 16:lla.
\end{enumerate}

Jokaista tuloskuvan tavua varten kerätään 16-bittinen etumerkillinen summa konvoluution määritelmän \ref{eq_convolution} mukaisesti.
Koska lohkon koko on 16 tavua, tarvitaan summien tallentamiseen kaksi 128-bittistä SSE2-muuttujaa.
Kaikki värikanavat käsitellään samalla tavalla, joten tässä kohtaa ei tarvitse huomioida käytettävää pikseliformaattia.

Kohdassa \ref{conv_kerniter} ohitetaan suoraan kaikki kernelin sisältämät nollakertoimet, sillä ne eivät vaikuttaisi tulokseen.
Näin laskenta on tehokasta, vaikka ajon aikana käytettäisiin pienempää kerneliä kuin käännösvaiheessa asetettu maksimikoko on.

Lähtökuvan lohkon paikka määritetään kohdassa \ref{conv_load} kernelin indeksin ja tuloskuvan lohkon perusteella.
Esimerkiksi kernelin arvon $k(-1, -1)$ kohdalla vähennetään tuloskuvan kohdasta yksi rivi ja yksi sarake, ja ladataan lähtökuvan lohko tästä kohdasta. Sarakekoordinaatissa huomioidaan pikseliformaatin koko, eli esimerkiksi RGB24-kuvilla tavuosoitteesta vähennetään 3.

Kertolaskua varten 8-bittiset pikseliarvot on laajennettava 16-bittisiksi. Tämä laajennus tehdään etumerkittömästi, eli lisäämällä nollia eniten merkitseviksi biteiksi, koska pikseliarvot ovat positiivisia.
Itse kertolasku suoritetaan kuitenkin etumerkillisenä negatiivisten kernelin arvojen huomioimiseksi.

Kohdassa \ref{conv_addtosum} käytetään saturoituvaa yhteenlaskua, jolloin laskutoimituksen tulos jää maksimi- tai minimiarvoon ylivuodon sijaan. 
Saturoituvuutta on käytetty hyväksi kernelin skaalauskertoimen valinnassa, jolloin skaalauskerroin voi olla suurempi ja saavutetaan parempi tarkkuus pyöristysvirheiden suhteen.
Lisäksi SSE2-käskykannassa on valmis käsky saturoituvalle yhteenlaskulle, joten sen käyttö ei vaikuta nopeuteen.

Oikean lopputuloksen saamiseksi summa pitää jakaa käytetyllä skaalauskertoimella.
Hitaan jakolaskun välttämiseksi se tehdään kertomalla summa skaalauskertoimen käänteisluvulla.
Käänteisluku voidaan laskea silmukan ulkopuolella, jolloin se ei vaikuta laskennan nopeuteen.

Pyöristystä varten summaan lisätään kohdassa \ref{conv_round} puolet skaalauskertoimesta, jolloin aikaansaadaan pyöristys positiivisille luvuille.
Periaatteena on yhteys $x/s+\frac{1}{2} = (x+\frac{s}{2})/s$.
Negatiiviset luvut saturoituvat joka tapauksessa tuloksessa nollaksi, joten niiden pyöristyksellä ei ole merkitystä.

SSE2-käskykannassa on kohtaan \ref{conv_mult} sopiva erityinen käsky, joka suorittaa $16\times16$-bittisen kertolaskun ja palauttaa tuloksen 16 ylintä bittiä.
Kertolaskun tulos muunnetaan 8-bittiseksi saturoivasti, jolloin negatiiviset arvot pyöristyvät nollaan ja yli menevät arvot 255:een.

\subsection{Reuna-alueiden käsittely}
Pikseliarvojen jatkaminen kuvan reuna-alueilla tehdään ylläolevan listan kohdassa \ref{conv_load}.
Jos reunaan osutaan pystysuunnassa, eli $y + y'$ on negatiivinen tai ylittää kuvan alalaidan, koko ladattavan lohkon kohtaa siirretään pystysuunnassa kuvan lähimpään reunaan. Vaakasuunnan käsittely on monimutkaisempi, koska yhtäaikaisesti käsitellään 16 vierekkäistä tavua.

Ennen lohkon lataamista testataan, onko joko $x + x'$ negatiivinen tai $x + x' + 15$ yli kuvan oikean laidan. Jos näin on, ladattavan lohkon kohtaa siirretään vaakasuunnassa siten, ettei lataus mene rivin ulkopuolelle. Muutoin kuvan alussa tai lopussa voisi tapahtua lukeminen varaamattomalta muistialueelta, ja sen seurauksena ohjelman kaatuminen. Lataamisen jälkeen lohkoa siirretään vaakasuunnassa siirto-operaatiolla ja täydennetään kopioimalla reunan pikseliarvoja.

Reuna-alueiden tarkistukset tehdään vain tarvittavissa kohdissa, eli kuvan ja rivien alussa ja lopussa. Yksittäisten lohkojen laskenta on eriytetty toiseen funktioon, jolla on \code{inline}-määre ja parametri, joka ohjaa ehtojen käsittelyä. Tällöin kääntäjä luo automaattisesti keskialuetta varten koodin, jossa ei ole turhia ehtolauseita hidastamassa.

\subsection{Separoituvuuden hyödyntäminen}
Kernelin separoituvuus testataan alustuksen yhteydessä. Separoinnin tulosvektorit tallennetaan kahteen taulukkoon, joille haetaan kummallekin erikseen skaalauskerroin. Jos kerneli on todettu separoituvaksi, käytetään konvoluutiossa erillistä laskentarutiinia.

Tämä laskentarutiini käyttää osaksi samaa koodia kuin yllä käsitelty. Separoituva konvoluutio lasketaan aluksi pystysuunnassa, sitten tulos tallennetaan, ja sen jälkeen tehdään vastaava vaakasuunnassa tulosriville.
Pystysuunnan laskenta tehdään ensiksi jotta sen tulos mahtuu käytettävissä olevalle yhdelle tulosriville. Kummankin suunnan konvoluutio on aiemmin käsiteltyä yksinkertaisempi, koska reuna-alueet ja kernelin läpikäynti täytyy tehdä vain yhdessä ulottuvuudessa.

% Välimuistin hyödyntämiseksi pysty- ja vaakasuunnan konvoluutiot suoritetaan lohkoille limittäin, sen sijaan että koko rivi käsiteltäisiin ensin pystysuunnassa ja sitten vaakasuunnassa. Jotta vaakasuunnassa saadaan oikeat tulokset, on käsiteltävän lohkon sekä sen oikealla ja vasemmalla puolella olevien lohkojen sisällettävä pystysuunnan konvoluution tulos. Siksi pystysuunnan konvoluution $x$-koordinaatti on vaakasuunnan konvoluutiota edellä, ja toisaalta vaakasuunnan konvoluution tulos tallennetaan yhden lohkon viiveellä.

Separoituvuutta ei kuitenkaan voida käyttää kerneleille, joissa on negatiivisia arvoja. Koska välitulos tallennetaan 8-bittisenä ilman etumerkkiä, negatiiviset välitulokset leikkautuisivat. Ongelman voisi kiertää käyttämällä erillistä puskuria, johon välitulokset tallennettaisiin 16-bittisinä. Algoritmin käyttötarkoituksessa positiiviset kernelit ovat kuitenkin yleisempiä, ja koska separoituvuudesta saatava nopeusetu on muutenkin rajallinen, ei tämän toteutukseen käytetty aikaa.

\subsection{Rinnakkaistus}
Laskenta suoritetaan tuloskuvan rivi kerrallaan. Pystysuunnan silmukka on jaettu eri prosessoreille OpenMP-käskyjen avulla. Koska jokaiseen tuloskuvan kohtaan kirjoitetaan vain yhdessä säikeessä, ei eri säikeiden välille synny riippuvuusongelmia. Jotta prosessorikohtaisen välimuistin käyttö olisi tehokasta, peräkkäiset rivit käsitellään aina samassa säikeessä. Kuva siis jaetaan esimerkiksi kahden prosessorin tapauksessa ylä- ja alaosaan, sen sijaan että rivit käsiteltäisiin vuorotellen eri prosessoreilla.

\subsection{Kääntäjäoptimoinnit}
Kääntäjä pystyy suorittamaan konvoluutioalgoritmille joitain hyödyllisiä optimointeja.
Kernelin koko on käännösaikainen vakio, joten kääntäjä avaa (engl. loop unrolling) kernelin läpikäynnissä käytetyt silmukat.

Jotta käännetty kirjasto olisi joustava, pikseliformaattia ei voitu määritellä vakioksi. Sen sijaan kullekin tuetulle pikseliformaatille käännetään erillinen versio konvoluutioalgoritmista, ja suorituksen aikana valitaan mitä näistä kutsutaan. Käytännössä tämä on toteutettu määrittelemällä kääntäjän komentoriviltä esikääntäjämakro \code{PIXEL\_SIZE}, jonka perusteella muodostetaan myös funktion nimi. Eri parametreilla käännetyt funktiot linkitetään yhteen, ja pääfunktiossa, nopeuskriittisen silmukan ulkopuolella, on ehtorakenne valitsemassa oikean version.

\subsection{Rajoitukset}
Suurin tuettu kernelin koko on $33\times33$, jolloin indeksi $x'$ on välillä $[-16, 16]$. Rajoitus muodostuu siitä, että reuna-alueiden tarkastelussa huomioidaan vain reunimmaiset lohkot. Jos indeksi $x'$ olisi yli 16, täytyisi tarkastelu laajentaa myös muihin lohkoihin.

Kernelin symmetrisyydellä on separoituvuuden tavoin mahdollista nopeuttaa laskentaa, mutta tätä ei ole toteutettu.
Tällaiselle kernelille $k(x', y') = k(\pm x', \pm y')$, jolloin kaikki neljä lähtöpikseliä
$f(x \pm x', y \pm y')$ voitaisiin laskea yhteen ennen kertolaskua. Mittausten
perusteella kertolaskuihin kuluva aika muodostaa kuitenkin vain yhden neljäsosan
konvoluution laskenta-ajasta, joten symmetrisyydestä saatava hyöty olisi rajallinen.
