Prosenttipiste (engl. percentile) on mediaania muistuttava operaatio, jossa lukujoukko järjestetään suuruusjärjestykseen ja taulukosta valitaan tietyssä kohdassa oleva arvo.
Esimerkiksi 99~\% prosenttipiste on sellainen arvo, että 1~\% taulukon arvoista on sitä suurempia.
Periaate on esitetty myös kuvassa \ref{fig_percentile}.
Tämän algoritmin tapauksessa prosenttipistettä käytetään keskihajonnan tulosten suodatukseen, jolloin häiriöt yksittäisissä pikseleissä suodattuvat pois.

\begin{figure}[htb]
\begin{tikzpicture}
[node distance=0.8cm]
\node (input) {Keskihajonnan arvot};

\matrix [draw, matrix of nodes, right=of input, nodes={anchor=east}, inner sep=1mm] (unsorted) {
    143,5\\
    88,6\\
    230,8\\
    0,8\\
    0,0\\
    12,8\\
    8,9\\
    54,2\\
    4,2\\
    20,3\\
};

\matrix [draw, matrix of nodes, node distance=2cm, right=of unsorted, nodes={anchor=east}, inner sep=1mm] (sorted) {
    230,8\\
    |(ppiste)| 143,5\\
    88,6\\
    54,2\\
    20,3\\
    12,8\\
    8,9\\
    4,2\\
    0,8\\
    0,0\\
};

\node [right=of ppiste] (output) {90~\% prosenttipiste $= 143,5$};

\draw [thick, ->] (input) -- (unsorted);
\draw [thick, ->] (unsorted) -- (sorted) node [midway, above] {Lajittelu};
\draw [thick, ->] (ppiste) -- (output);
\end{tikzpicture}
\caption{Prosenttipisteen laskeminen. Keskihajonnan tulokset lajitellaan, ja lajitellusta taulukosta valitaan tietyssä kohdassa oleva arvo.}
\label{fig_percentile}
\end{figure}

\section{Prosenttipisteen matemaattinen kuvaus}
\addmglosb{$n2$}{$N$}{Prosenttipisteen laskennassa käsiteltävien lukujen lukumäärä, eli tämän algoritmin tapauksessa $w \cdot h$.}
Prosenttipisteelle on esitetty useita vaihtoehtoisia määritelmiä, jotka eroavat siinä, miten prosenttiluku pyöristetään taulukon indeksiksi. Tämän työn tapauksessa käytetään seuraavaa määritelmää. Prosenttipiste $P(p)$ on arvo, jonka kanssa yhtäsuuria tai pienempiä arvoja on $p \cdot N / 100$ kappaletta, missä kappalemäärä pyöristetään lähimpään kokonaislukuun. Käsiteltävien lukujen lukumäärä $N$ on tämän algoritmin tapauksessa pikselien lukumäärä eli $w \cdot h$. Kukin värikanava käsitellään siis erikseen.
\begin{align*}
&\text{Järjestetään luvut } v_0 \ldots v_{N-1} \text{ siten, että } v_0 \le v_1 \le \ldots \le v_{N-1}\\
&R = \mathrm{round}(\frac{p\cdot N}{100})\\
&P(p) = v_R
\end{align*}
Useimpien järjestysalgoritmien vaatima aika on $\mathcal{O}(N \log(N))$.
Prosenttipisteen laskemiseen ei kuitenkaan tarvita täyttä lajittelua.

\subsection{Nopeutus valinta-algoritmeilla}
\addmglosb{$o()$}{$\mathcal{O(\ldots)}$}{Algoritmien vertailussa käytetty merkintä, joka kuvaa ajan- tai muistinkulutuksen verrannollisuutta käsiteltävän tiedon määrään.}
Prosenttipisteen tehokkaasti laskevia algoritmeja kutsutaan yleisesti valinta-algoritmeiksi, ja ne ovat nopeimmillaan $\mathcal{O}(N)$ ajankäytöltään ja $\mathcal{O}(1)$ muistinkäytöltään \cite{blum}.
Tavallisin rakenne näissä algoritmeissa on valita taulukosta satunnainen luku kynnysarvoksi, ja jakaa taulukko sitten kahteen osaan sen mukaan ovatko luvut pienempiä vai suurempia kuin kynnysarvo.
Saatujen kahden taulukon pituuksista voidaan päätellä, kummassa taulukossa haluttu prosenttipiste on, ja tämän jälkeen jakamista jatketaan rekursiivisesti.
Algoritmin tehokkuus määräytyy lähinnä siitä, kuinka hyvin kynnysarvo valitaan.
Parhaassa tapauksessa kynnysarvoksi osuu taulukon mediaani, jolloin lajiteltavien lukujen määrä puolittuu jokaisella rekursiotasolla.

Valinta-algoritmit ovat yleisessä tapauksessa tehokkain tapa prosenttipisteen laskemiseen, mutta tämän työn tapauksessa tulosten arvoalue on rajoitettu. Sen vuoksi laskeminen saadaan vielä nopeammaksi muodostamalla histogrammi tuloksista.

\subsection{Nopeutus histogrammilla}
Histogrammi muodostetaan laskemalla jokaisen arvon lukumäärä taulukossa.
Saadut lukumäärät käydään läpi pienimmästä arvosta alkaen ja summataan yhteen, kunnes summa on yhtäsuuri tai ylittää prosenttipisteen määritelmän mukaisen indeksin $R$.
Prosenttipiste on tällöin se arvo, johon summaaminen lopetettiin.
Periaate on esitetty myös kuvassa \ref{fig_histogram}.

\begin{figure}
\centering
\begin{tikzpicture}
[node distance=0.5cm]

\node [text width=5em, text centered] (input) {Keskihajonnan arvot};

\matrix [draw, matrix of nodes, right=of input, nodes={anchor=east}, inner sep=1mm] (unsorted) {
    143,5\\
    88,6\\
    230,8\\
    0,8\\
    0,0\\
    12,8\\
    8,9\\
    54,2\\
    4,2\\
    20,3\\
};

\node [coordinate, node distance=5cm, right of=unsorted] (histogrampos) {};

\begin{axis} [at=(histogrampos), anchor=west, name={histogram}, x=0.2mm, xmin=-5, ymin=0, ymax=3, xmax=256, grid=none, ytick={0,1,2}, xtick={0, 100, 143, 200}, y=1cm, clip=false]
\addplot[ycomb, mark=*, draw, black] plot coordinates
    {(0,2) (4,1) (8,1) (12,1) (20,1) (54,1) (88,1) (143,1) (230,1)};
\draw [decorate, decoration={brace,mirror,amplitude=2mm}, yshift=-6mm]
    (axis cs: 0,0) -- (axis cs: 143,0) node [coordinate, midway] (brace) {};
\node [below=of brace, text width=10em] (result) {Summa = 9~kpl, joten 90~\% prosenttipiste on 143.};
\draw [thick, ->] ($(brace)+(0,-2mm)$)--(result);
\end{axis}

\draw [thick, ->] (input) -- (unsorted);
\draw [thick, ->] (unsorted) -- +(5cm,0) node [midway, above, text width=10em, text centered] {Histogrammin muodostus};
\end{tikzpicture}
\caption{Histogrammin käyttö prosenttipisteen laskennassa. Kunkin keskihajonnan arvon esiintymismäärä taulukossa lasketaan, ja tulokset muodostavat histogrammin. Histogrammi käydään pienimmästä arvosta alkaen läpi ja summataan yhteen, kunnes summa ylittää prosenttipistettä vastaavan indeksin.}
\label{fig_histogram}
\end{figure}

Histogrammin muodostaminen on ajankäytöltään $\mathcal{O}(N)$, mutta muistinkäyttö riippuu käsiteltävästä arvoalueesta.
Koska varianssin tulokset ovat 16-bittisiä, riittää histogrammitaulukon kooksi 65~536 lukua.

Histogrammin laskeminen on ohjelmallisesti hyvin yksinkertaista: histogrammin muodostamiseen tarvitaan pelkkä taulukon indeksointi ja yksi yhteenlasku jokaista pikseliä varten. Prosenttipisteen laskeminen histogrammista puolestaan vaatii enimmillään 65~536:n luvun yhteenlaskun.
Vaikka valinta-algoritmit siis kuluttavat vähemmän muistia ja ovat ajankäytöltään samaa $\mathcal{O}$-luokkaa, vaatii niiden laskenta enemmän käskyjä kuin histogrammi.

\section{Toteutustapa}
Toteutus jakautuu kahteen osaan: histogrammin keräämiseen, ja prosenttipisteen laskentaan histogrammista.
Näistä edellinen suoritetaan jo keskihajonnan laskennan kanssa samassa silmukassa ja jälkimmäinen sen jälkeen.

Konvoluutiosta ja keskihajonnasta poiketen prosenttipisteen laskennassa ei käytetä SSE2-käskykantaa.
Eniten aikaa kuluu taulukon indeksointiin histogrammia kerättäessä.
Tässä on kyse epäsuorasta muistin osoituksesta, jonka nopeutuksessa SIMD-käskyistä ei ole apua.

\subsection{Lukualueet}
Histogrammitaulukon alkiot tarkoittavat pikselien lukumääriä, joten niiden arvoalue riippuu kuvan koosta.
Esimerkiksi $640\times480$ pikselin kuvassa on 307~200 pikseliä.
Jos kuvassa ei ole yhtään muutoksia, on kaikkien pikselien varianssi 0, ja siten histogrammin ensimmäinen arvo on 307~200 ja muut arvot 0.

Sopiva bittileveys histogrammitaulukolle on siten 32 bittiä.
Tämä riittää enintään $2^{32}$ pikselin kokoisille kuville, eli esimerkiksi $65~536\times65~536$ pikselin kokoon asti.

\subsection{Histogrammitaulukon kerääminen}
Histogrammitaulukko alustetaan nollaksi ennen varianssilaskennan silmukkaa.
Varianssilaskennassa tulokset saadaan neljän luvun lohkoissa, joka sitten käydään luku kerrallaan läpi.
Jokainen luku vastaa yhden pikselin varianssia, ja on arvoalueeltaan 16-bittinen.
Histogrammitaulukkoa indeksoidaan tällä luvulla ja kasvatetaan taulukon arvoa, eli \code{histogrammi[varianssi]++;}.

Laskennan nopeuden kannalta suurin merkitys on muistioperaation nopeudella.
Koska taulukon koko on $65536\cdot4=262144 \text{ tavua}=256 \text{ kilotavua}$, mahtuu se nykyaikaisten prosessorien toisen tason välimuistiin kokonaan.
Lisäksi jos kuvassa on vain vähän muutoksia, eniten käytetään histogrammin ensimmäisiä alkioita jotka vastaavat pieniä varianssin arvoja.
Tällöin ne mahtuvat ensimmäisen tason välimuistiin, ja niiden käsittely on hyvin nopeaa.

\subsection{Rinnakkaistus}
Varianssi lasketaan rinnakkaisesti, joten samassa silmukassa suoritettava histogrammitaulukon päivitys suoritetaan myös rinnakkain.
Jotta eri säikeissä tapahtuvat laskennat eivät rikkoisi toistensa tuloksia, jokaiselle säikeelle varataan oma taulukko.

Säikeiden määrä määräytyy sen mukaan, montako prosessoriydintä laitteistossa on.
Tarvittavien taulukoiden määrää ei siksi tiedetä käännösvaiheessa.
Taulukot varataan siksi dynaamisesti \code{calloc()}-kutsulla aina ennen laskentaa.
Muistivaraus vie jonkin verran aikaa, ja sen voisi periaatteessa siirtää algoritmin alustukseen.
Käytännössä ajankäyttö on testatuilla alustoilla kuitenkin merkityksettömän pieni, enemmän aikaa kuluu histogrammitaulukon nollaamiseen, mikä täytyy tehdä joka tapauksessa aina ennen laskentaa.

\subsection{Prosenttipisteen hakeminen histogrammista}
Prosenttipisteen laskemiseksi histogrammin alkioita summataan järjestyksessä yhteen, kunnes summa ylittää halutusta prosenttipisteestä määräytyvän arvon.
C-kielellä esitettynä laskenta tapahtuu näin:

\begin{verbatim}
int pp_indeksi = (int)roundf(leveys * korkeus * prosenttipiste);
int varianssi;
int summa = 0;
for (varianssi = 0; varianssi < HISTOGRAMMI_KOKO; varianssi++)
{
    for (int saie = 0; saie < saikeiden_maara; saie++)
    {
        summa += histogrammit[saie][varianssi];
    }
    
    if (summa >= pp_indeksi)
        break;
}

float keskihajonnan_prosenttipiste = sqrtf((float)varianssi / 4);
\end{verbatim}

Taulukon läpikäyntiä voisi ajatella nopeutettavan SSE2-käskyillä, siten että kerralla summattaisiin yhteen kokonainen 16 tavun lohko.
Testien perusteella pullonkaula on kuitenkin muistihauissa, sillä lohkoissa tehtävä summaus ei nopeuttanut laskentaa lainkaan.

\subsection{Rajoitukset}
Merkittävin rajoitus prosenttipisteen laskennassa on se, että histogrammitaulukon koko rajoittaa prosenttipisteen tarkkuutta.
Tarkkuus riittää hyvin 8-bittisille luvuille, mutta 16-bittisellä värisyvyydellä taulukon kokoa jouduttaisiin kasvattamaan tai pienentämään tuloksen tarkkuutta.
