primoz_godec_colorization.tex

%================================================================
% SLO
%----------------------------------------------------------------
% datoteka: 	thesis_template.tex
%
% opis: 		predloga za pisanje diplomskega dela v formatu LaTeX na
% 				Univerza v Ljubljani, Fakulteti za računalništvo in informatiko
%
% pripravili: 	Matej Kristan, Zoran Bosnić, Andrej Čopar,
%			  	po začetni predlogi Gašperja Fijavža
%
% popravil: 	Domen Rački, Jaka Cikač, Matej Kristan
%
% verzija: 		30. september 2016 (dodan razširjeni povzetek)
%================================================================


%================================================================
% SLO: definiraj strukturo dokumenta
% ENG: define file structure
%================================================================
\documentclass[a4paper, 12pt]{book}

\usepackage{longtable}
\usepackage{multirow}
\usepackage{afterpage}
\usepackage{adjustbox}
\usepackage{graphicx} % http://ctan.org/pkg/graphicx
\usepackage{booktabs} % http://ctan.org/pkg/booktabs
\usepackage{xparse}   % http://ctan.org/pkg/xparse
\usepackage{emptypage}
\usepackage{listings}
\usepackage{setspace}
%\usepackage{color}
\usepackage{minted}
\usepackage{fontspec}

% set font for source code and urls
\setmonofont{Ubuntu Mono}

% minted settings
\usemintedstyle{tango}
\setminted[python]{xleftmargin=0.5cm, fontsize=\footnotesize}

\NewDocumentCommand{\rot}{O{45} O{1em} m}{\makebox[#2][l]{\rotatebox{#1}{#3}}}%



% foot note
\makeatletter
\newcommand\footnoteref[1]{\protected@xdef\@thefnmark{\ref{#1}}\@footnotemark}
\makeatother

%mod 
\newcommand{\Mod}[1]{\ \mathrm{mod}\ #1}



%================================================================
% SLO: Odkomentiraj "\SLOtrue " za izbiro slovenskega jezika
% ENG: Uncomment "\SLOfalse" to chose English languagge
%================================================================
\newif\ifSLO
% switch language

\SLOtrue % Enables Slovenian language
%\SLOfalse  % Enables English language

%================================================================
% SLO: vključi oblikovanje in pakete
% ENG: include design and packages
%================================================================
\input{style/thesis_style}

% url break
\makeatletter
\g@addto@macro{\UrlBreaks}{\UrlOrds}
\makeatother

%----------------------------------------------------------------
% |||||||||||||||||||||| USTREZNO POPRAVI |||||||||||||||||||||||
% |||||||||||||||||||||| EDIT ACCORDINGLY |||||||||||||||||||||||
%----------------------------------------------------------------
\newcommand{\ttitle}{Barvanje črnobelih slik z globokimi modeli}
\newcommand{\ttitleEn}{Deep models for image coloring}
\newcommand{\tsubject}{\ttitle}
\newcommand{\tsubjectEn}{\ttitleEn}
\newcommand{\tauthor}{Primož Godec}
\newcommand{\temail}{p.godec9@gmail.com}
\newcommand{\myyear}{2017}
\newcommand{\tkeywords}{umetna inteligenca, strojno učenje, globoke nevronske mreže, barvanje črno-belih slik}
\newcommand{\tkeywordsEn}{artificial inteligence, machine learning, deep neural networks, image colorization}
\newcommand{\mysupervisor}{prof.~dr.~Blaž Zupan}
\newcommand{\mycosupervisor}{}

% include formatted front pages
\input{style/thesis_front_pages}

%================================================================
% ENG: main pages of the thesis
%================================================================

%----------------------------------------------------------------
% Poglavje (Chapter) 1: Uvod
%----------------------------------------------------------------
\chapter{Uvod}
\label{ch:uvod}

Čeprav so prvo barvno fotografijo naredili že leta 1886\footnote{\url{https://petapixel.com/2015/10/11/a-brief-history-of-color-photography-from-dream-to-reality/}}, se je ta tehnika v vsakdanji uporabi uveljavila šele mnogo let pozneje. Tako imajo naši stari starši še vedno veliko črno-belih fotografij. Ker te prikazujejo realnost drugače, kot smo navajeni danes, nas zanimajo računski in algoritmični postopki, ki bi znali avtomatsko obarvati črno-bele slike.

Barvanja črno-belih fotografij so se lotevali že v devetnajstem stoletju, ko so to počeli še ročno. V sedemdesetih letih prejšnjega stoletja so se pojavili prvi pristopi z računalnikom\footnote{\url{http://articles.chicagotribune.com/1986-08-29/entertainment/8603050091_1_wilson-markle-constance-bennett-laurel-and-hardy-movie}}, ki so še vedno zahtevali nekaj uporabnikovega sodelovanja. Kasneje so se pristopi izboljševali in postajali vse bolj avtomatski\footnote{\url{http://www.museum.tv/eotv/colorization.htm}} \cite{levin2004colorization, huang2005adaptive, Koleini2010, shirley2001color, tai2005local}.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=12cm]{imcompare}
\end{center}
\caption{Pristop barvanja črno-belih slik za vhod vzame sivinsko sliko (levo) in na izhodu vrne obarvano sliko (desno).}
\label{im:compare}
\end{figure}
 
Algoritmi za barvanje črno-belih slik dobijo kot vhod črno-belo sliko, ki ji dodajo barvo, kot je prikazano na sliki \ref{im:compare}. Pristopi za barvanje črno-belih slik se uporabljajo na več področjih: barvanje starih slik, barvanje črno-belih filmov in v umetnosti. V preteklosti so bili pristopi za barvanje slik pol-avtomatski \cite{levin2004colorization, huang2005adaptive, Koleini2010, shirley2001color, tai2005local}, danes pa jih zamenjujejo pristopi, ki obarvajo sliko popolnoma samostojno \cite{Cheng2015, Deshpande2015, Zhang2016, larsson2016learning, Iizuka2016}. Zadnje raziskujemo v tem magistrskem delu.

\begin{figure}[hbt]
\begin{center}
\includegraphics[width=13cm]{black-colored-comparison}
\end{center}
\caption{Primeri barvanja črno-belih slik. Barvali smo s pristopi predlaganimi v tej nalogi. Za vsako sliko je prikazana črno-bela slika (levo), ki je vhod v algoritem in obarvana slika - izhod algoritma (desno). }
\label{im:pari-cb-b}
\end{figure}

Za človeka je barvanje črno-belih slik, ki so prikazane na sliki \ref{im:pari-cb-b}, enostavna naloga. Z vsakdanjim opazovanjem sveta se je človek naučil, da je nebo modro z belimi oblaki, drevesa so zelena in cesta je siva. Za objekte, ki nimajo enolično določene barve, ljudje lahko uganemo, kakšne barve naj bi bili. Pri tem opravilu je potrebno sliko razumeti oziroma prepoznati objekte na sliki, saj iz sivinskih slik ni možno neposredno razbrati barv. Pri nastanku sivinskih slik se dve od treh dimenzij izgubita, saj je barvna slika zapisana z tremi barvnimi kanali v praktično kateremkoli barvnem prostoru, črno-bela pa le z enim barvnim kanalom, ki predstavlja sivino.

Problem barvanja postane bolj kompleksen, ko ga želimo rešiti na avtomatski način z računalnikom. Pri tem so nam v pomoč teksture in njihove lastne barve \cite{Zhang2016}. Pri objektih, ki nimajo enolično določenih barv --- na primer avtomobili, stavbe in knjige --- je izziv mnogo težji. Pomaga nam dejstvo, da je naš cilj ohranjanje naravnega izgleda slike in ne reprodukcija originalnih barv. Nihče ne bo vedel, da je bil avtomobil, ki smo ga pobarvali modro, v resnici rdeče barve. 

Za barvanje slik smo v sklopu pričujoče naloge implementirali pristope, ki uporabljajo nevronske mreže. Te delujejo podobno kot človeški možgani. Na začetku jih naučimo tako, da jim podamo čim več parov sivinske in ustrezne barvne slike, nevronska mreža pa naučeno znanje oziroma funkcijo, ki sivinsko pretvori v barvno sliko, uporabi za barvanje slik.  
Za učenje modela potrebujemo veliko črno-belih slik z referenčno barvno sliko. Vzamemo lahko katerokoli barvno sliko in jo pretvorimo v sivinsko.

V nalogi rešujemo problem barvanja črno-belih slik z implementacijo različnih pristopov, ki temeljijo na globokih nevronskih mrežah. Rezultate smo ovrednotili s primerjavo med obarvanimi in originalnimi barvnimi slikami. Rezultate lastnih v nalogi razvitih pristopov smo primerjali s tremi pristopi iz nedavno objavljenih sorodnih del. Ker v naravi obstaja veliko objektov, ki nimajo enolične barve in je naš namen naravnost rezultatov, smo kvaliteto barvanja slik dodatno ocenjevali s spletno anketo.

V nadaljevanju najprej pogledamo sorodna dela, nekaj ozadja o podatkih in globokih nevronskih mrežah. V tretjem poglavju so podrobno opisane arhitekture nevronskih mrež in predlagani različni pristopi za barvanje. V četrtem poglavju je opisano učenje nevronskih mrež, podatki, na katerih smo te učili in način evalvacije. V petem poglavju smo primerjali naše pristope s tistimi iz sorodnih del in si pogledali, kateri pristopi in slike pri barvanju najbolj izstopajo. Preizkusili smo, kateri pristop deluje najbolje na slikah večjih velikosti in ustreznost barvanja preverili s spletno anketo.

%----------------------------------------------------------------
% Poglavje (Chapter) 2: Pregled področja
%----------------------------------------------------------------
\chapter{Pregled področja}
\label{ch:pregled}

Za barvanje črno-belih slik so bili razviti konceptualno različni pristopi. Nedavno predlagane tehnike uporabljajo globoke nevronske mreže. Pri vseh pristopih barvanja je pomembna tudi predstavitev slikovnih podatkov.

\section[Predstavitev slikovnih podatkov in barvni prostori]{Predstavitev slikovnih podatkov in \\ barvni prostori}
\label{se:podatki}

Barvne slike, ki smo jih v disertaciji uporabili pri učenju, so shranjene v barvnem prostoru RGB \cite{Pm2013}. Kot je pokazano v \cite{Iizuka2016}, se izkaže, da barvanje na osnovi prostora RGB daje slabše rezultate, saj prostor iz dveh razlogov ni primeren za učenje barvanja:

\begin{itemize}

\item \textbf{Sistem RGB se slabo ujema s človeško percepcijo barv}, saj so številčne razdalje med enako sorodnimi barvami za človeka v prostoru RGB različne \cite{Prangnell}. Primer parov dveh barv je predstavljen na sliki \ref{im:color_dist}. Različnost med barvami v prvi vrstici je za človekov vizualni sistem enaka različnosti med barvami v drugi vrstici. Razdalja med barvami prvega para v barvnem prostoru RGB je $160$, pri drugem paru pa $211$.

\item \textbf{Sistem RGB nima ločenega kanala za svetlost} \cite{Pm2013}, kar je razvidno iz slike \ref{im:color_dist}. Sprememba svetlosti pri barvah v paru povzroči spremembo vseh komponent v barvnem prostoru RGB. Glede na to, da modeli za barvanje napovedujejo le barvne elemente v sliki, svetlost pa privzamejo iz originalne slike, je najbolj priročno, če uporabljamo barvni prostor, ki ima ločen kanal za svetlost, saj je izhod metode združena komponenta za svetlost z barvnimi komponentami. 

\end{itemize}

\begin{figure}[hbt]
\begin{center}
\includegraphics[width=12cm]{color_distances}
\end{center}
\caption{Slika prikazuje dva para za ljudi enako oddaljenih barv. Barve so zapisane v barvnih prostorih RGB in CIE L*a*b*. L*a*b* je barvni prostor, kjer enaka številčna razdalja med dvema odtenkoma (na sliki je v obeh primerih razdalja 40) pomeni tudi enako razliko za človekov vizualni sistem \cite{Prangnell}.}
\label{im:color_dist}
\end{figure}

\subsection{Izbira primernega barvnega prostora}
\label{ch:barvni-prostor}

Na podlagi predpostavk o primernosti barvnega prostora je izbira prostorov omejena na Lab \cite{Bansal}, YUV \cite{Jack2005} in HSL \cite{Pm2013}. Vsi našteti prostori vsebujejo ločen kanal za svetlost. Med njimi je Lab edini, kjer bližina barv v prostoru ustreza tudi percepcijski bližini.

Obstaja več implementacij barvnega prostora Lab, ki dobro aproksimirajo človeški zaznavni sistem. Enaka barva je v različnih implementacijah prostora Lab opisana z nekoliko drugačnimi vrednostmi, saj se je prostor razvijal skozi čas in postajal vedno bolj natančen. Trenutno se največ uporablja CIE L*a*b*, ki naj bi bil najboljša aproksimacija človeškega vizualnega sistema \cite{Prangnell}. Ta prostor je tudi neodvisen od naprave, ki je sliko zajela. 

Prostor CIE L*a*b* predstavi vse barve, ki jih je možno zaznati s tremi barvnimi kanali. Vrednost $L*$ predstavlja svetlost, $a*$ se razširja od zelene proti rdeči in $b*$ od modre proti rumeni barvi (slika \ref{im:lab}). Zaloga vrednosti $L*$ je od $0$, ki predstavlja črno barvo, do $100$, ki predstavlja belo barvo \cite{Weatherall1992}. Vrednosti komponent $a*$ in $b*$ načeloma niso omejene, vendar sta v implementacijah omejeni na vrednosti v intervalu $[-128, 127]$, kar je možno predstaviti z osem bitnim celim številom\footnote{\url{https://www.freiefarbe.de/en/grenzen-des-cielab-farbraums/}}. Ker zaradi pretvorbe iz barvnega prostora RGB redko dosežemo vrednosti komponent $a*$ in $b*$, ki so višje od $100$ ali nižje $-100$, smo opazili, da nekatere implementacije omejijo zalogo vrednosti barvnih komponent na interval $[-100, 100]$. Za pomoč pri implementaciji nevronske mreže smo sami preizkusili, kakšen je dejanski interval barv pretvorjenih iz barvnega prostora RGB (tabela \ref{tab:rgbcie}).

\begin{figure}[hbt]
\begin{center}
\includegraphics[width=6cm]{cielab}
\end{center}
\caption{Kanali barvnega prostora CIE L*a*b*. $L*$ predstavlja svetlost, $a*$ se razteza od zelene barve v najbolj negativni točki proti rdeči barvi, $b*$ pa se razteza od modre proti rumeni. Nasprotujoče barve na kanalih $a*$ in $b*$ se nikoli ne kombinirajo v odtenek. Vir slike: Adobe, Technical Guid, CIELAB\protect\footnotemark{}.}
\label{im:lab}
\end{figure}

\footnotetext{\url{http://dba.med.sc.edu/price/irf/Adobe_tg/models/cielab.html}}

\begin{table}[htb]
\caption{Največje in najmanjše vrednosti posamezne komponente barvnega prostora CIE L*a*b* pri pretvorbi  barv iz barvnega prostora RGB. Pretvorba je bila narejena z uporabo osvetlitve $D65$, ki določa temperaturo bele točke. Izkaže se, da je večina vrednosti komponent $a*b*$ znotraj intervala $[-100, 100]$. }
\begin{center}
    \begin{tabular}{lccc}
    	\hline
        Kanal & Najmanjša vrednost & Največja vrednost \\
        \hline
        L* & 0 & 100 \\
        a* & -86,185 & 98,254 \\
        b* & -107,863 & 94,482 \\
        \hline
    \end{tabular}
\end{center}
\label{tab:rgbcie}
\end{table}

\subsection{Pretvarjanje med barvnima prostoroma RGB in CIE L*a*b*}

Za pretvorbo med prostoroma ni enostavne enačbe, saj je barvni prostor RGB odvisen od naprave, ki sliko zajame, CIE L*a*b* pa je neodvisen. V našem primeru imamo slike že zapisane v standardnem RGB ali sRGB barvnem prostru, ki je neodvisen od naprave. V ta prostor je bila slika pretvorjena že ob zajemu. Pretvorba v L*a*b* se zato zgodi v dveh korakih \cite{Connolly1997}: 

\begin{enumerate}

\item \textbf{Pretvorba v barvni prostor CIE 1931} \cite{Ohta2005} ali drugače imenovan barvni prostor CIE XYZ. Ta pretvorba se izvede s pomočjo linearne pretvorbe - množenje z matriko. Matrika je odvisna od izbire referenčne bele barve \cite{Ohta2005}. Običajno se izbere referenčno temperaturo bele točke \textit{D65}, ki je tudi standardizirana\footnotemark{}.

\footnotetext{Zapis na uradni strani komisije International Commision on Illumination (krajše CIE), ki je postavila standard, pravi, da se kot standardno uporablja referenčno temperaturo bele točke D65: \url{http://cie.co.at/index.php?i_ca_id=484}}

\item \textbf{Pretvorba iz CIE XYZ v L*a*b*} se izvede z uporabo transformacijskih enačb opisanih v članku XYZ to LAB\footnote{\url{http://www.brucelindbloom.com/index.html?Eqn\_XYZ\_to\_Lab.html}}.  

\end{enumerate}

Pretvorbo med barvnima prostoroma sRGB in CIE L*a*b* demonstrira sledeča implementacija v Pythonu. 

\inputminted{python}{rgb2lab.py}

\section{Globoke nevronske mreže}
\label{se:globoke}

Nevronska mreža je funkcija $f(\vec{x})$, ki preslika vhod $\vec{x}$ v izhod $\hat{y}$. Med postopkom učenja je ta funkcija optimizirana tako, da najbolje aproksimra dejanske vrednosti $\vec{y}$, ki so za učne podatke znani\footnote{\label{note1}\url{https://deeplearning4j.org/neuralnet-overview}}. Nevronska mreža je sestavljena iz več nivojev. Nivoje si lahko predstavljamo kot vrsto vozlišč, ki se odzovejo v primeru dovolj visokih signalov na vhodu. Primer strukture vozlišča in nivojev je predstavljena na sliki \ref{im:nn-structure}. Vozlišče pomnoži vhodne vrednosti s trenutnimi vrednostmi uteži, doda še pristranskost (ang. {\em bias}), vrednosti sešteje in moč aktivacije izračuna s pomočjo tako imenovane aktivacijske funkcije, ki tvori izhod vozlišča. Aktivacijski funkcija vnese nelinearnost, saj poskrbi za to, da nevronska mreža ni le linearna funkcija. Tipični primeri aktivacijskih funkcij so sigmoidna funkcija, tanh, ReLU, leaky ReLU in maxout\footnote{A. Karpathy, ``Neural Networks Part 1: Setting up the Architecture,'' Zapiski predavanj, CS231n Convolutional Neural Networks for Visual Recognition, Stanford University, 2016.}. Uteži se skozi postopek učenja spreminjajo in s tem določajo aktivacijo vozlišča.

\begin{figure}[htb]
\begin{center}
\centering
\includegraphics[width=7cm]{node_structure}
\includegraphics[width=4cm]{nn_structure}
\end{center}
\caption{Leva slika prikazuje zgradbo enega vozlišča nevronske mreže. Vhod je lahko izhod prejšnjega nivoja ali predstavlja vhodne podatke, ki se potem pomnožijo z utežmi in seštejejo. Desna slika prikazuje zgradbo večnivojske nevronske mreže. V našem primeru ima ta en vhodni nivo, en skriti nivo in izhodni nivo. Vir slike: Introduction to Deep Neural Networks\protect\footnoteref{note1} in Neural Networks\protect\footnotemark{}.}
\label{im:nn-structure}
\end{figure}


\footnotetext{\url{http://docs.opencv.org/2.4/modules/ml/doc/neural\_networks.html}}


Nivojem v nevronskih mrežah, ki se nahajajo med vhodnim in izhodnim nivojem, pravimo skriti nivoji (ang. {\em hidden layers}) \footnote{A. Karpathy, ``Neural Networks Part 1: Setting up the Architecture,'' Zapiski predavanj, CS231n Convolutional Neural Networks for Visual Recognition, Stanford University, 2016.}. Tradicionalni algoritmi na področju strojnega učenja so sestavljeni iz vhodnega, izhodnega nivoja in enega skritega nivoja, globoka nevronska mreža (ang. {\em deep neural network}) pa ima vsaj dva skrita nivoja \cite{collobert2008unified}, pri večini praktičnih implementacij pa jih je mnogo več. Vsak nivo globoke nevronske mreže prepozna določene lastnosti vhodnih podatkov. Nivoji, ki se nahajajo globje, lahko prepoznajo bolj kompleksne lastnosti podatkov, saj na vhodu dobijo značilke, ki še dodatno opisujejo vhodne podatke. 

Da nevronska mreža daje zadovoljive rezultate, je potrebno utežem do\-lo\-či\-ti ustrezne vrednosti. To naredimo z učenjem. Vsaka nevronska mreža ima cenilno funkcijo (ang. {\em loss function}), ki pove, kako dobre rezultate daje nevronska mreža na testnih podatkih. V postopku učenja je cilj zmanjšati vrednost cenilne funkcije z enim od algoritmov optimizacije. Tipične cenilne funkcije so cenilna funkcija večrazredne metode podpornih vektorjev (ang. {\em Multiclass Support Vector Machine Loss}), križna entropija, norma L2 (povprečna kvadratna napaka) in norma L1\footnote{A. Karpathy, ``Setting up the data and the model,'' Zapiski predavanj, CS231n Convolutional Neural Networks for Visual Recognition, Stanford University, 2016.}. 

\subsection{Konvolucijske nevronske mreže}

Ker bi bilo na primeru slik pri uporabi klasičnih nevronskih mrež hitro preveč parametrov, kar bi poleg podaljšanja časa učenja povzročilo tudi prekomerno prilagajanje (ang. {\em overfitting}) in pomanjkanje pomnilnika, uporabljamo konvolucijske nevronske mreže. Te so tako kot običajne nevronske mreže sestavljene iz nevronov, ki imajo svoje uteži in pristranskost. Ti parametri so učljivi. Operacije znotraj nevrona so podobne tistim pri običajnih nevronskih mrežah, le da so prilagojene slikam. Vhod v vsak nivo nevronske mreže je tenzor $X$ z obliko $vi\check{s}ina \times \check{s}irina \times globina$, kjer globina pomeni število barvnih kanalov slike\footnote{\label{ref:karpatUnder}A. Karpathy, ``Understanding and Visualizing Convolutional Neural Networks,'' Zapiski predavanj, CS231n Convolutional Neural Networks for Visual Recognition, Stanford University, 2016.}. Konvolucijske nevronske mreže so v osnovi sestavljene iz treh vrst nivojev:

\begin{itemize}

\item \textbf{Konvolucijski nivo} je glavni gradnik konvolucijske nevronske mreže. Parametri tega nivoja so sestavljeni iz majhnih konvolucijskih jeder, ki pokrivajo majhno polje slike. Več takih jeder pa pokriva celotni nivo v globino, tako si lahko eno jedro predstavljamo kot utež pri skritih nivojih v običajni nevronski mreži, ki zraven izvaja še konvolucijo. Med prehodom po nevronski mreži izvedemo konvolucijo po višini in širini vhodnega tenzorja, po globini pa se izhode teh konvolucij sešteje enako kot pri običajni nevronski mreži. Izhod konvolucije z enim setom jeder je dvodimenzionalna matrika \cite{lecun1995convolutional}. Na sliki \ref{im:convolution_ex} je shema, ki prikazuje rezultat konvolucije.

\begin{figure}[hbt]
\begin{center}
\includegraphics[width=8cm]{depthcol}
\end{center}


\caption{Primer, ki prikazuje potek konvolucije. Vhodni tenzor je po celotni višini in širini konvuliran z množico konvolucijskih jeder. Izhod ene operacije je enodimenzionalni tenzor, v tem primeru ima ta pet elementov in vpliva le na del izhodnega tenzorja. Skupek vseh konvolucij tvori celoten izhodni tenzor. Vir slike: Karpathy\protect\footnoteref{ref:karpatUnder}.}
\label{im:convolution_ex}
\end{figure}


\item \textbf{Nivo združevanja (ang. {\em pooling layer})} je namenjen podvzorčenju (ang. {\em downsampling}) tenzorja. To izvede tako, da združi več izhodov iz nevronov nekega nivoja v posamezen nevron v naslednjem nivoju. Za združevanje obstaja več strategij. Najbolj pogosto je maksimalno združevanje (ang. {\em max pooling}), poznamo pa še povprečno združevanje (ang. {\em average pooling}). Z združevanjem zmanjšamo prostorsko dimenzijo tenzorja in s tem število parametrov, kar vpliva na zmanjšanje računske zahtevnosti in prekomernega prilagajanja. Deluje na principu, da je točna lokacija značilke manj pomembna kot približna lokacija glede na ostale značilke. \cite{Krizhevsky2012}. 

\item \textbf{Polnopovezni nivo} je nivo enak skritim nivojem pri klasični nevronski mreži. Večinoma se uporabi za zadnjih nekaj nivojev pri konvolucijski nevronski mreži.

\end{itemize}

\subsection{Primer konvolucijske nevronske mreže}
\label{ch:cov_nev_net}

Za primer konvolucijske nevronske mreže bomo predstavili poenostavljeno mrežo za prepoznavanje objektov v sliki. Ta naloga je namreč postala šolski primer uporabe konvolucijskih nevronskih mrež \cite{ILSVRC15}.

Odločili smo se implementirati mrežo, ki na vhodu prejme sliko velikosti $h \times w$ slikovnih točk in ima tri barvne kanale prostora RGB. Mreža na izhodu vsako sliko klasificira v enega od razredov. Za demonstracijo smo se odločili, da bomo slike klasificirali v enega od desetih razredov, čeprav večina ostalih implementacij slike razvršča v mnogo več razredov. Primeri razredov so na primer živali, drevesa, zgradbe, morje in ljudje in so odvisni od podatkovne zbirke, s katero učimo mrežo.

Mreža, ki jo uporabljamo za to nalogo, je shematsko prikazana na sliki \ref{im:vgg-like}. Na začetku ima dva konvolucijska nivoja, nato sledi nivo maksimalnega združevanja, ki zmanjša prostorsko dimenzijo tenzorja. Sledita še dve konvoluciji in še eno maksimalno združevanje. Takoj za tem se tenzor splošči v enodimenzionalni tenzor in gre preko dveh polnopovezanih nivojev. Prvi velikost enodimenzionalnega tenzorja zmanjša na velikost $256$, drugi pa na velikost $10$. Vsaka vrednost v zadnjem tenzorju predstavlja verjetnost za pripadnost objekta na sliki določenemu razredu. Razred z največjo verjetnostjo predstavlja objekt na sliki. 

\begin{figure}[htb]
\begin{center}
\centering
\includegraphics[width=7cm]{vgg_like_arh}
\end{center}
\caption{Shematski prikaz poenostavljene nevronske mreže za prepoznavanje objektov na sliki. Na levi strani je prikazano spreminjanje velikosti tenzorjev ob prehodu skozi nevronsko mrežo, na desni pa so označeni nivoji mreže.}
\label{im:vgg-like}
\end{figure}

Vsak nivo ima tudi svojo aktivacijsko funkcijo. Pri vseh nivojih uporabljamo funkcijo ReLU, razen pri zadnjem, polnopovezanem, kjer je aktivacijska funkcija softmax. Glede na to, da je problem klasifikacijski, za cenilno funkcijo uporabljamo križno entropijo. Primer implementacije te nevronske mreže v vmesniku Keras je predstavljen v nadaljevanju.


\subsection{Konvolucijske nevronske mreže v Kerasu}
\label{ch:keras}

Keras\footnote{\url{https://github.com/fchollet/keras}} je visokonivojski programski vmesnik za nevronske mreže. Vmesnik lahko teče na zaledju Tensorflow \cite{tensorflow2015-whitepaper}, Theano \cite{2016arXiv160502688short} ali CNTK \cite{Seide:2016:CMO:2939672.2945397}. V našem primeru smo izbrali Tensorflow.
Razlog za izbiro vmesnika Keras je, da je visokonivojski in zaradi tega uporabniku prijazen, narejen je v programskem jeziku Python\footnote{\url{https://www.python.org/}}, ki nam je najbolje poznan in je zelo modularen, nevronska mreža je predstavljena kot sekvenca ali graf, ki jo je enostavno dopolniti ali spremeniti.

V spodnji kodi smo implementirali konvolucijsko nevronsko mrežo iz poglavja \ref{ch:cov_nev_net}.

\inputminted{python}{vvg_like.py}

% podatki
Kot je razvidno iz prvega dela implementacije, so podatki, ki smo jih pripravili, generirani naključno. Ti podatki nam sicer ne zagotavljajo smiselnega učenja, iz njih pa lepo vidimo strukturo podatkov. 
Pri podatkih predpona \texttt{x} označuje, da gre za vhodne podatke v mrežo, \texttt{y} označuje prave vrednosti oziroma pričakovane izhode iz mreže. Običajno razlikujemo med tremi vrstami podatkov. Učni podatki (\texttt{x\_training}, \texttt{y\_training}) so tisti, ki jih uporabimo zgolj za učenje mreže, validacijski podatki (\texttt{x\_validation}, \texttt{y\_validation}) so tisti, ki imajo tako kot učni podatki zraven prisotne prave vrednosti in služijo preverjanju natančnosti mreže. Testni podatki (\texttt{x\_test}) so tisti, ki jih na koncu uporabimo za prikaz rezultatov mreže. Velikokrat testni podatki nimajo prisotnih pravih vrednosti. Na primer pri raznih tekmovanjih na področju strojnega učenja tekmovalec dobi le vhodne podatke, napovedi pa odda za kasnejše vrednotenje, pri čemer ne vidi pravilnih napovedi.

% nekaj o zgradbi
Mreža ima sekvenčno zgradbo, konvolucijski nivoji uporabljajo jedro velikosti $3 \times 3$, pri maksimalnem združevanju (\texttt{MaxPooling}) uporabljamo velikost združevanja $2 \times 2$, kar pomeni, da se velikost tenzorja po višini in širini zmanjša za faktor polovico. V implementaciji se uporabljajo tudi nivoji za opustitev nevronov (\texttt{Dropout}), ki v vsakem koraku učenja izločijo določen delež vozlišč. Ta vozlišča s tem ne vplivajo na rezultat napovedi in se v tistem koraku tudi ne učijo. S tem zmanjšajo prekomerno prilagajanje (ang. {\em overfitting}).

% učenje
Pri učenju smo uporabljali optimizator \texttt{Adam} \cite{DBLP:journals/corr/KingmaB14}. Optimizator je algoritem, ki določa strategijo spreminjanja uteži in s tem zmanjšuje vrednost cenilne funkcije. Najbolj enostavni optimizator je gradientni sestop, ki spreminja uteži v smeri najhitrejšega zmanjševanja napake, vendar to ni vedno dovolj učinkovito, zato so bili razviti novi algoritmi. V praksi se sicer največ uporabljajo optimizacijski pristopi: SGD, Adagrad, RMSprop in Adam\footnote{A. Karpathy, ``Learning,'' Zapiski predavanj, CS231n Convolutional Neural Networks for Visual Recognition, Stanford University, 2016.}. 

Kot lahko opazimo ob pogledu na funkcijo \texttt{fit}, je parameter \texttt{epochs} nastavljen na fiksno število korakov. V tem primeru mrežo učimo z desetimi prehodi skozi vse podatke. Običajno se trajanje učenja določi s spremljanjem obnašanja validacijske napake. Z učenjem končamo, ko se validacijska napaka neha zmanjševati. Takrat pravimo, da je algoritem skonvergiral k najmanjši napaki. Če bi z učenjem nadaljevali, se začne mreža prekomerno prilagajati učnim podatkom, kar v večini primerov pomeni, da se slabše odreže na validacijskih in kasneje testnih podatkih.

\subsection{Cenilne funkcije}
\label{ch:cenilne}

Pri pristopih, ki smo jih opisali v nalogi, uporabljamo tri cenilne funkcije. Pri regresijskih pristopih se je za dobro izkazala povprečna kvadratna napaka (ang. {\em mean squared error}), ki jo označimo z MSE:
\begin{equation}
\textrm{MSE}(\hat{Y}, Y) = \frac{1}{hwc} \sum_{i=0}^{h} \sum_{j=0}^{w} \sum_{k=0}^{c} (Y_{i,j,k} -  \hat{Y}_{i,j,k})^2.
\label{eq:mse}
\end{equation}
Spremenljivka $Y$ predstavlja originalno sliko, $\hat{Y}$ pa obarvano sliko s strani mreže. Spremenljivka $h$ je višina slike, $w$ je širina slike in $c$ je število kanalov. MSE smo računali le na komponentah $a*$ in $b*$, tako da je $c=2$.  

Pri enem od klasifikacijskih pristopov smo za cenilno funkcijo uporabili divergenco Kull\-back-Leibler \cite{joyce2011kullback}, ki jo označujemo z $\text{D}_{\text{KL}}$. V našem primeru smo izvedli divergenco Kullback-Leibler na posamezni slikovni točki in jo povprečili preko celotne slike: 
\begin{equation}
\textrm{D}_{\text{KL}}(Z || \hat{Z}) = \frac{1}{hw} \sum_{i=0}^{h} \sum_{j=0}^{w} \sum_{k=0}^{c} Z_{i, j, k} \log \frac{Z_{i, j, k}}{\hat{Z}_{i, j, k}}.
\label{eq:kld}
\end{equation}
V enačbi $Z$ predstavlja originalno sliko, $\hat{Z}$ pa obarvano sliko s strani mreže, obe sta pretvorjeni v vektorje s $400$ razredi, ki predstavljajo barve. Spremenljivka $h$ je višina slike, $w$ je širina slike, oznaka $c$ v tem primeru predstavlja število razredov, v katere mreža klasificira barve, zato je $c = 400$. 



Kot zadnjo cenilno funkcijo smo uporabili tudi križno entropijo (ang. {\em cross entropy}) \cite{Mannor2005}. Križna entropija se računa na razredih napovedanih s strani mreže:

\begin{equation}
\textrm{H}(\hat{Z}, Z) = \sum_{i=0}^{h} \sum_{j=0}^{w} \sum_{k=0}^{c} Z_{i, j, k} \log \hat{Z}_{i, j, k}.
\label{eq:ce}
\end{equation}

Druga različica križne entropije uporablja uteži, ki predstavljajo povprečno pogostost pojavitve posamezne barve v slikah. Pogostost je bila izračunana na množici $100.000$ naključnih slik izbranih iz zbirke ImageNet. Uteži v cenilni funkciji dajejo večji pomen tistim točkam, kjer se v originalni sliki pojavijo močnejše barve. S tem želimo vzpodbuditi mrežo, da bo večkrat obarvala z močnejšimi barvami. Pri ostalih pristopih je namreč problem, da barve velikokrat niso tako kontrastne, kot bi lahko bile. Križno entropijo z utežmi označimo s Hw, kjer $v(\cdot)$ predstavlja utež za barvo v slikovni točki na koordinatah $(h, w)$:

\begin{equation}
\textrm{Hw}(\hat{Z}, Z) = \sum_{i=0}^{h} \sum_{j=0}^{w} v(Z_{i, j}) \sum_{k=0}^{c} Z_{i, j, k} \log \hat{Z}_{i, j, k}.
\label{eq:cew}
\end{equation}

\section[Metode za barvanje črno-belih slik]{Metode za barvanje črno-belih slik}

Pristope za barvanje črno-belih slik lahko delimo v dve večji skupini. Prva zahteva interakcijo uporabnika med postopkom barvanja, ki se je več uporabljala v preteklosti, pri drugi pa barvanje poteka popolnoma avtomatsko.

\subsection{Pristopi z interakcijo uporabnika}

To skupino pristopov delimo na tehnike, ki temeljijo na uporabnikovem barvanju manjših delov slik (ang. {\em scribble based}) \cite{levin2004colorization, huang2005adaptive} in tiste, ki temeljijo na primerih podobno obarvanih slik (ang. {\em example based}) \cite{Koleini2010, shirley2001color, tai2005local}. 
Pri prvih uporabnik določi barvo nekaj točkam na sliki, te pa algoritem avtomatsko razširi preko cele slike. Kvaliteta barvanja je odvisna od zahtevnosti slike in števila točk, ki jih je uporabnik označil.
Pri barvanju na primerih uporabnik izbere referenčno sliko podobno tisti, ki jo želimo obarvati, algoritem pa lastnosti izbrane slike razširi na drugo sliko ali množico slik. Kvaliteta barvanja je odvisna od podobnosti referenčne slike s sliko, ki jo barvamo. 

Prednost tehnike barvanja, ki temelji na barvanju manjših delov je, da je barvanje lahko zelo natančno in naravno, vendar mora uporabnik za dovolj veliko natančnost označiti veliko točk na sliki. V nasprotnem primeru je lahko barvanje tudi zelo nenatančno. 
Prednost tehnike barvanja s primeri pa je njena hitrost in avtomatičnost po tem, ko imamo izbrano referenčno sliko, vendar je velikokrat problem najti dobro referenčno sliko.
Zaradi teh lastnosti se tehnika barvanja s primeri uporablja za barvanje videa, saj je v tem primeru potrebno ročno pobarvati na primer vsako stoto sliko, na ostale pa algoritem sam razširi lastnosti ročno barvane slike. 
Ta tehnika je večinoma zelo natančna, saj se slike, ki so v videu blizu, običajno zelo malo razlikujejo.

\subsection{Popolnoma avtomatski pristopi}

V magistrskem delu se osredotočamo na avtomatske pristope barvanja. Ti pristopi samostojno brez uporabnikovega posredovanja obarvajo celotno sliko. Prva dva pristopa, ki sta bila predlagana na tem področju, temeljita na značilkah slik, ki opisujejo intenziteto posamezne barve in robove. Prvi pristop uporablja za barvanje nevronsko mrežo \cite{Cheng2015}, ki vsebuje zgolj polnopovezane nivoje, druga pa za barvanje uporabi metodo naključnih gozdov \cite{Deshpande2015}. 

Novejši pristopi barvanja uporabljajo konvolucijske nevronske mreže, ki v vsakem nivoju same odkrijejo značilke, ki so pomembne za čimbolj kvalitetno barvanje. Prva tovrstna rešitev\footnote{\url{http://tinyclouds.org/colorize/}} gradi mrežo na podlagi značilk že zgrajene šestnajst-nivojske mreže VGG-16, ki so jo razvili na univerzi v Oxfordu \cite{Simonyan2014} in je namenjena prepoznavanju objektov na sliki. Rešitev uporablja evklidsko cenilno funkcijo in barvni prostor YUV \cite{Jack2005}. Njena slabost je slabša barvna nasičenost in poudarjenost rjavih odtenkov. 

Problem nenasičenosti je moč odpraviti z uporabo softmax funkcije v zadnjem nivoju nevronske mreže. Problem barvanja na ta način spremeni v klasifikacijskega.  
Zhang in sod. \cite{Zhang2016} uporabijo konvolucijsko nevronsko mrežo z več nivoji in aktivacijskimi funkcijami ReLU. Uporabljajo barvni prostor L*a*b*. Arhitektura je predstavljena na sliki \ref{im:zgang-arh}. Posebnost te mreže je cenilna funkcija. Uporablja križno entropijo (enačba \ref{eq:cross_ent_weights}), ki je v tem primeru izvedena na primerjavi barv vsake slikovne točke glede na barvni prostor, ki je kvantiziran:
\begin{equation}
H(\hat{Z}, Z) = - \sum_{i=0}^{h} \sum_{j=0}^{w} v(Z_{i, j}) \sum_{k=0}^c Z_{i, j, k} \log (\hat{Z}_{i, j, k}).
\label{eq:cross_ent_weights}
\end{equation}
Spremenljivka $Z$ predstavlja barve originalne slike, ki so zapisane kot $c$ razsežni vektorji, kjer $c$ predstavlja število barv. $\hat{Z}$ je ocenjena barva.  Napake so pomnožene z utežmi, ki odražajo pogostost barv. Redkeje uporabljene barve so utežene tako, da prispevajo večji delež k cenilni funkciji. S tem so avtorji izboljšali rezultate tako, da se bolj pogosto pojavljajo tudi močnejši odtenki, torej tisti z višjimi vrednostmi v barvnem prostoru \textit{a*b*}, ki so bili prej redkeje zastopani zaradi bolj pogostega pojavljanja nežnejših barv v slikah. To so barve bližje vrednostim $(0, 0)$ v prostoru \textit{a*b*}. V enačbi \ref{eq:cross_ent_weights} za obteževanje vrednosti poskrbi funkcija $v(\cdot)$.
Pogostost je bila izračunana z analizo vseh slik v podatkovni zbirki Imagenet \cite{ILSVRC15}. 

\begin{figure}[htb]
\begin{center}
\includegraphics[width=12cm]{zhang_arh}
\end{center}
\caption{Arhitektura mreže Zhang in sod. \cite{Zhang2016}. Na vhodu je črno-belo slika, nato sledi več konvolucijskih blokov. Vsak od blokov vsebuje dve ali tri konvolucije. Vsaki konvoluciji sledi normalizacija serije in aktivacijska funkcija ReLU. Modri blok predstavlja napovedi barve v obliki verjetnosti za vsak razred, ki predstavlja množico odtenkov. Te vrednosti se na koncu pretvorijo v barvne vrednosti $a*b*$ in združijo s črno-belo sliko, da dobimo obarvano sliko. Vir slike: Zhang in sod. \cite{Zhang2016}. }
\label{im:zgang-arh}
\end{figure}
 
Larsson in sod. \cite{larsson2016learning} za osnovo uporabijo mrežo VGG-16, iz katere vzamejo tenzorje vsakega nivoja, ki jim povečajo prostorsko dimenzijo tako, da se ujemajo in združijo v enotno matriko. Sledi še en polno-povezan nivo. Rezultat klasifikacije je histogram z verjetnostmi posameznega odtenka za vsako točko na sliki. Arhitektura mreže je predstavljena na sliki \ref{im:larsson-arh}. Uporabljajo barvni prostor HSV, ki ga prilagodijo zaradi nestabilnosti v delu prostora v komponente: odtenek označen z $H$, barvna nasičenost označena z $C$ in svetlost $L$. Cenilna funkcija, ki jo uporabljajo, je divergenca Kullback-Leibler, ki primerja izhodni histogram z originalno sliko pretvorjeno v histogram po zgoraj opisanih komponentah:
\begin{equation}
\begin{gathered}
L(\hat{Z}, Z) = \sum_{i=0}^{h} \sum_{j=0}^{w} \left(\text{D}_\text{KL}(Z_{i, j, C} ||  \hat{Z}_{i, j, C}) + \lambda \text{D}_\text{KL}(Z_{i, j, H} || \hat{Z}_{i, j, H})\right) \\ 
\text{D}_\text{KL}(z ||  \hat{z}) = \sum_{i=0}^{c} z_{i} \log \frac{z_{i}}{\hat{z}_{i}}.
\end{gathered}
\label{eq:kl_div}
\end{equation}
V enačbi \ref{eq:kl_div}  $Z$ predstavlja originalno sliko spremenjeno v histogram vrednosti za vsako od komponent $H$ in $C$, $\hat{Z}$ predstavlja ocenjeno barvo. Utež $\lambda$ določa, koliko k napaki prispeva vsaka od komponent $C$ in $H$ in so jo avtorji nastavili na vrednost $\lambda = 5$.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=11cm]{larson_arh}
\end{center}
\caption{Slika prikazuje arhitekturo mreže Larsson in sod. \cite{larsson2016learning}. Mreži VGG-16 je podana črno-belo slika, nato se iz omenjene mreže vzame izhode vseh konvolucij in polnopovezanih nivojev, jih nadvzorči na velikost osnovne slike ter združi v skupni tenzor, kot je prikazano na sliki. Sledi še en polnopovezani nivo in dobimo ocene v obliki histogramov verjetnosti, ki se jih potem pretvori v barvni prostor HSV in združi v sliko skupaj z originalno sliko. Vir slike: Larsson in sod. \cite{larsson2016learning}.}
\label{im:larsson-arh}
\end{figure}
 
\newpage 
 
Iizuka in sod. \cite{Iizuka2016} uporabijo nevronsko mrežo sestavljeno iz dveh delov (slika \ref{im:iizuka-arh}). Del za klasifikacijo poskrbi za napovedovanje vsebine slike, ki se potem združi z glavnim delom in izboljša natančnost barvanja.  Uporabljajo barvni prostor L*a*b. Za cenilno funkcijo so uporabili povprečno kvadratno napako v kombinaciji s križno entropijo:
\begin{equation}
\begin{split}
L_(\hat{Y}^{color}, Y^{color}, \hat{Y}^{class}, l^{class}) = \sum_{i=0}^{h} \sum_{j=0}^{w}  \left(
 \left\Vert Y_{i, j}^{color} - \hat{Y}_{i, j}^{color} \right\Vert_{FRO}^2 \right. \\ 
 \left.
 - \lambda \left(\hat{Y}^{class}_{l^{class}} - 
\log \left(\sum_{i=0}^N \exp(\hat{Y}^{class}_i \right)\right)
\right).
\end{split}
\label{eq:iizuka_loss}
\end{equation}
Prva je namenjena ocenjevanju kvalitete barvanja, druga pa ocenjuje natančnost klasifikacije objektov na sliki. S tem je poskrbljeno, da se skupaj z učenjem glavne mreže uči še mreža za klasifikacijo. Oznaka $y^{color}$ predstavlja barvo slikovne točke na originalni sliki, $\hat{y}^{color}$ ocenjeno barvo, $\hat{y}^{class}$ ocenjen razred, ki določa vsebino slike in $l^{class}$ indeks objekta, ki se v resnici nahaja na sliki. Z $\left\Vert \cdot \right\Vert_{FRO}$ označimo Frobeniusovo normo in z $\lambda$ utež, ki določa razmerje med vplivom mreže za klasifikacijo in glavne mreže za učenje. 
Za razliko od prejšnjih dveh pristopov pristop Iizuka in sod. napoveduje direktno $a*$ in $b*$ vrednosti ter za to uporabi regresijo.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=13cm]{iizuka_arh}
\end{center}
\caption{Arhitektura mreže Iizuka in sod. \cite{Iizuka2016}. Mreža dobi na vhodu črno belo sliko. Ta se poda tako mreži za klasifikacijo (spodaj), kot mreži za barvanje (zgoraj). Izhod mreže je slika z barvnimi komponentami $a*b*$, ki se nato združi s črno-belo sliko. Vir slike: Iizuka in sod. \cite{Iizuka2016}. }
\label{im:iizuka-arh}
\end{figure}


%----------------------------------------------------------------
% Poglavje (Chapter) 3: Pregled področja
%----------------------------------------------------------------

\chapter{Barvanje črno-belih slik z globokimi nevronskimi mrežami}
\label{ch:barvanje}

V nalogi smo razvili nekaj različnih arhitektur globokih nevronskih mrež. Razvili smo tako pristope z regresijo kot klasifikacijo. Razvili smo tudi pristop, ki zna učinkovito barvati slike večje od teh iz učne množice. Pri arhitekturah mrež smo se zgledovali po sorodnih, že obstoječih pristopih, a v eksperimentih skušali razumeti, kateri elementi teh pristopov najbolj vplivajo na kvaliteto barvanja.

\section{Arhitekture nevronskih mrež}
\label{ch:arhitekture}

Implementirali smo štiri arhitekture nevronskih mrež in jih kombinirali z različnimi cenilnimi funkcijami, pristopi (regresijski ali klasifikacijski) in na\-či\-ni napovedovanja (lokalni in globalni).

\subsection{Arhitektura S+G}
\label{ch:plitva}

Arhitektura S+G (ang. {\em Shallow with Global}) je sestavljena iz dveh delov, ki se kasneje združita v enotno mrežo. Glavni del predstavlja zaporedje konvolucijskih nivojev, ki na vhodu sprejmejo črno-belo sliko z enim kanalom, izhod pa je obarvana slika z dvema kanaloma za barvni komponenti $a*$ in $b*$. Po prvih osmih kovolucijskih nivojih se mreža združi s tako imenovano globalno mrežo, ki prepoznava objekte na sliki. Za globalno mrežo smo po vzoru \cite{Iizuka2016} vzeli že naučeno šestnajstnivojsko mrežo VGG-16 \cite{Simonyan2014}, ki smo ji odvzeli zadnji polnopovezani nivo in ji dodali nov polnopovezani nivo z izhodnim tenzorjem dolžine 256. Ker je arhitektura VGG-16 namenjena sprejemu barvnih slik s tremi vhodnimi kanali, smo vhod prilagodili tako, da sprejme sivinsko sliko na vsakem od vhodnih kanalov. Arhitektura nevronske mreže je predstavljena na sliki \ref{im:arh1} in z implementacijo v prilogi \ref{ch:app_sg}.

\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=13cm]{arh1}
\end{center}
\caption{Velikosti tenzorjev skozi arhitekturo S+G. Oznaki $h$ in $w$ predstavljata višino in širino vhodne slike. Podrobnosti nivoja združitev so predstavljene na sliki \ref{im:fusion}, nivo izhodne slike ni natančneje označen, saj se razlikuje v različnih implementacijah, ki so podrobneje opisane v poglavjih \ref{ch:regression-methods} in \ref{ch:classification-methods}. }
\label{im:arh1}
\end{figure}

Vhod v element za združevanje glavne in globalne mreže sta tenzorja velikosti $\frac{h}{8} \times \frac{w}{8} \times 256$ iz glavne mreže in enodimenzionalni tenzor velikosti $256$ iz globalne mreže. Pri tem $h$ in $w$ predstavljata višino in širino vhodne slike v mrežo. Pri združevanju vsakemu elementu širine in višine prvega tenzorja pridružimo tenzor globalne mreže (slika \ref{im:fusion}). Tako na izhodu dobimo tenzor velikosti $\frac{h}{8} \times \frac{w}{8} \times 512$. 
 
\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=8cm]{fusion1}
\end{center}
\caption{Delovanje nivoja združevanja glavne nevronske mreže z globalno nevronsko mrežo. K izhodu glavne nevronske mreže (modri tenzor) dodamo tenzor iz globalne mreže (rdeči tenzor), tako da ga priključimo k vsem prostorskim lokacijam glavnega tenzorja kot dodatnih 256 kanalov. Izhodni tenzor ima tako velikost $\frac{h}{8} \times \frac{w}{8} \times 512$.}
\label{im:fusion}
\end{figure}

% l2 regularizacija citation \cite{mackay1992practical}

\subsection{Arhitektura D+G}
\label{ch:globjaz}

Arhitektura D+G (ang. {\em Deep with Global}) ima v osnovi enako zasnovo kot S+G, a uporabi 14 konvolucijskih nivojev pred združitvijo in 7 po združitvi (slika \ref{im:arh2} in priloga \ref{ch:app_dg}). 
Za zmanjševanje prostorskih dimenzij uporablja maksimalno združevanje \cite{Krizhevsky2012} in za povečevanje le-teh v zadnjih nivojih transponirano konvolucijo (ang. {\em transpose convolution}) \cite{Dumoulin2016}, imenovano tudi dekonvolucija. Transponirana konvolucija je transformacija, ki deluje v nasprotni smeri kot običajna konvolucija. Na vhodu vzame tenzor dimenzije, ki je izhod konvolucije z enakimi parametri, izhod transponirane konvolucije pa je tenzor dimenzije enake tistemu na vhodu običajne konvolucije. Transponirana konvolucija za svoje delovanje še vedno uporablja princip konvolucije. Združevanja glavne in globalne mreže se izvede, kot je opisano v poglavju \ref{ch:plitva}.

Arhitektura D+G prinaša še eno spremembo. To so tako imenovane rezidualne povezave, ki so bile prvič uporabljene v nevronski mreži ResNet, zasnovani s strani Microsoft Research Asia \cite{Wu2017}, ki je leta 2015 zmagala na tekmovanju ImageNet \cite{ILSVRC15}. Te povezave so na sliki \ref{im:arh2} označene s puščicami nad nevronsko mrežo in predstavljajo povezavo, ki na mestu, kamor kaže puščica, združi trenutni tenzor s tenzorjem izračunanim pred dvema nivojema. Operacija združevanja pomeni seštevanje isto ležečih elementov v tenzorju. Za rezidualne povezave smo se odločili, saj naj bi te prisilile nivoje, da se naučijo nekaj novega in ne le nadgradijo izhod prejšnjega nivoja. S tem smo računali na izboljšavo v natančnosti barvanja.

\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=13cm]{arh2}
\end{center}
\caption{Tenzorji v arhitekturi D+G. Oznaki $h$ in $w$ predstavljata višino in širino vhodne slike. Podrobnosti nivoja združitev so predstavljene na sliki \ref{im:fusion}, nivo izhodne slike pa ni natančneje označen, saj je odvisen od implementacije, ki so podrobneje opisane v poglavjih \ref{ch:regression-methods} in \ref{ch:classification-methods}. }
\label{im:arh2}
\end{figure}

\subsection{Arhitektura D}

Ta arhitektura je v glavnem delu enaka arhitekturi D+G, a ne uporablja globalne mreže. Mreža za vhod vzame črno-belo sliko z enim kanalom in izračuna barvno sliko na izhodu samo preko konvolucijskih nivojev. Arhitekturo D smo uporabili z namenom preverjanja vpliva globalne mreže na rezultate barvanja.

\subsection{Arhitektura X-VGG}

Arhitektura X-VGG je zgrajena tako, da za nižje nivoje uporabimo mrežo VGG-16 \cite{Simonyan2014}, kateri smo odstranili vse zadnje polnopovezane nivoje. Na vhodu sprejme črno-belo sliko, ki se nato prilagodi za vhod nevronske mreže VGG-16, tako da ima tri vhodne kanale. Te pridobimo tako, da vzamemo sivinsko sliko za vsak vhodni kanal. Tenzor, ki ga vrne zadnji konvolucijski nivo mreže VGG-16, podamo na vhod prvega nivoja nove mreže (slika \ref{im:arh4} in priloga \ref{ch:app_xvgg}). Nova mreža ima dodatnih osem konvolucijskih nivojev in štiri nivoje nadvzorčenja, ki poskrbijo za povečanje dimenzije prostorskih komponent. Po zadnjem nivoju izvedemo še povečanje slike za faktor dve, saj se nadvzorčenje izkaže kot slabše.

\begin{figure}[htb]
\begin{center}
\centering
\includegraphics[width=12cm]{arh4}
\end{center}
\caption{Velikosti tenzorjev skozi arhitekturo X-VGG. Oznaki $h$ in $w$ predstavljata višino in širino vhodne slike. Nivo izhodne slike ni natančneje označen, saj je odvisen od implementacije (poglavji \ref{ch:regression-methods} in \ref{ch:classification-methods}). Prvi večji blok predstavlja mrežo VGG-16 \cite{Simonyan2014}}
\label{im:arh4}
\end{figure}

\section{Pristopi z regresijo}
\label{ch:regression-methods}

Regresijski pristopi direktno napovejo vrednosti barvnih komponent $a*$ in $b*$ v prostoru CIE L*a*b*. Tu mreža predstavlja regresijsko funkcijo $\vec{y} = f(x)$ za vsako točko slike, ki na vhod dobi točko sivinske slike $x$, izhod pa sta zvezni vrednosti $a*$ in $b*$ (slika \ref{im:reg-scheme}).
Mreži podamo sivinsko sliko, ta oceni barvni komponenti $a*$ in $b*$, nato izhod mreže združimo s sivinsko sliko, ki je obenem komponenta $L*$.

\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=13cm]{regresija-shema1}
\end{center}
\caption{Regresijski pristopi na vhod prejmejo črno-belo sliko in s pomočjo nevronske mreže izračunajo barvni komponenti $a*$ in $b*$ barvnega prostora \textit{CIE L*a*b*}. }
\label{im:reg-scheme}
\end{figure}

\subsection{Lokalni pristop}
\label{ch:parts-im}

Barvanje pri tem pristopu izvedemo ločeno na majhnih delih slik, kot človek, ki bi na primer ločeno obarval vodo, nato gozd in kasneje še nebo. 

Sliko razdelilmo na koščke velikosti $32 \times 32$ slikovnih točk. Pri tem se sosednja koščka prekrivata za $16$ slikovnih točk, kot je prikazano na sliki \ref{im:overlapping}. 
V arhitekturah, kjer je prisotna ločena globalna mreža, ta še vedno na vhodu prejme celotno sliko. Dele slik po barvanju sestavimo z metodo prekrivanja, tako da imajo vrednosti točk pri robu manjši vpliv kot tiste pri sredini. Vpliv barvne točke se izračuna po enačbi 
\begin{equation}
Y'_{h, w} = \frac{d}{16} Y_{h, w},
\label{eq:1}
\end{equation}
kjer $Y_{h, w}$ predstavlja vrednost slikovne točke, $d$ pa predstavlja oddaljenost od središča v številu slikovnih točk. Enačba se ločeno uporablja v vertikalni in horizontalni smeri. Da dobimo končno vrednost v določeni točki, seštejemo vse prispevke za tisto točko.

\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=6cm]{overlapping1}
\end{center}
\caption{Razdelitev slike velikosti $128 \times 128$ slikovnih točk, na $7 \times 7$ enakih delov velikosti $32$ slikovnih točk, ki se med seboj v vseh smereh prekrivajo za $16$ slikovnih točk. Rdeč in zelen kvadrat prikazujeta prvi dve podsliki.}
\label{im:overlapping}
\end{figure}

S predlaganim pristopom pričakujemo pohitritev učenja, saj menimo, da je že del slike dovolj, da se mreža nauči celotne teksture objekta. Na primer, da se naučimo barvati vodo, ne potrebujemo celotnega območja vode na sliki, ki včasih lahko zavzema tudi pol ali več slike, ampak le ujemajoči del.

V tabeli \ref{tab:learning-speed} so prikazani časi potrebni za učenje pri dveh regresijskih pristopih na $2.854.912$ slikah, ki se razlikujeta le v tem, da en uči po delih, drugi pa na celih slikah. Oba pristopa sta bila učena ob istem času na isti napravi in ločenih GPU enotah. Iz tabele je razvidno, da lokalni pristop potrebuje krajši čas, da se nauči barvanja. To pripišemo predvsem  krajšemu času potrebnemu za en korak učenja, število korakov do naučenega pristopa pa je podobno.

\begin{table}[hbt]
\caption{Povprečen čas enega koraka (prehod preko 50.000 slik) pri učenju pristopov, število prehodov potrebnih za učenje in skupni čas potreben za učenje. Rezultati so prikazani za dva regresijska pristopa z enakimi arhitekturami, oba imata arhitekturo D+G in drugačnim načinom učenja. Iz rezultatov je razvidno, da lokalni pristopi za konvergenco potrebujejo manj časa.}
\begin{center}
    \begin{tabular}{lccc}
    \hline
	Pristop & Čas za korak [s] & Št. korakov & Skupni čas učenja [s]\\
	\hline
	Lokalni pristop & 619,8 & 90  & 55.782\\
	Globalni pristop  & 1815,0 & 89 & 161.535\\
	\hline
    \end{tabular}
\end{center}
\label{tab:learning-speed}
\end{table}

V tabeli \ref{tab:methods-whole} so predstavljene podrobnosti vsakega od lokalnih pristopov. Vsem pristopom je skupno, da uporabljajo cenilno funkcijo povprečna kvadratna napaka (MSE).


\subsection{Globalni pristopi}

Za primerjavo točnosti lokalnih pristopov s tistimi na celih slikah - globalnimi, smo dva pristopa, opisana v poglavju \ref{ch:parts-im}, pretvorili v globalni pristop. Uporabili smo  arhitekturi D+G in D, ki smo jih prilagodili tako, da na vhodu sprejmeta celotno sivinsko sliko in vrneta celotno obarvano sliko. Tej smo dodali še globalni regresijski pristop z mrežo VGG, saj ta zaradi večkratnega pomanjšanja prostorskih dimenzij znotraj arhitekture ne more biti realiziran kot lokalni pristop. V tabeli \ref{tab:methods-whole} so predstavljeni vsi regresijski pristopi in njihove arhitekture. Pri vseh je cenilna funkcija povprečna kvadratna napaka (MSE). 

\begin{table}[hbt]
\caption{Regresijski pristopi in njihove arhitekture, ki so podrobneje opisane v poglavju \ref{ch:arhitekture}.}
\begin{center}
\begin{tabular}{lc}
\hline
Pristop & Arhitektura \\
\hline
	Reg. lokalni & D+G \\
	\hspace{0.5em} - brez softmax & D+G\\
	\hspace{0.5em} - brez globalne mreže & D \\
\hline
Reg. globalni & D+G.\\
\hspace{0.5em} - brez globalne mreže & D \\
Reg. globalni VGG & X-VGG \\
\hline
\end{tabular}
\end{center}
\label{tab:methods-whole}
\end{table}

\section{Pristopi s klasifikacijo}
\label{ch:classification-methods}

Razvili smo štiri pristope, ki namesto regresije uporabljajo klasifikacijo. Pri teh pristopih barvo ocenimo z izbiro najbolj primernega razreda, ki predstavlja nekaj sosednjih odtenkov. Posamezen razred opiše barve, ki so blizu skupaj v dvodimenzionalnem prostoru a*b*.
Klasifikacija se izvede z uporabo \textit{softmax} funkcije v zadnjem nivoju mreže. 

Kot je prikazano na sliki \ref{im:class-scheme}, je vhod v metodo črno-bela slika, ki se posreduje nevronski mreži. Ta oceni obarvanje kot vektor verjetnosti za vsakega od razredov vsake slikovne točke. Te vrednosti se potem pretvorijo v komponenti $a*$ in $b*$ barvnega prostora CIE L*a*b*. Enako kot pri regresiji je rezultat združitev sivinske slike z ocenjenimi barvnimi komponentami. 

\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=13cm]{classification-scheme1}
\end{center}
\caption{Shematski prikaz delovanja klasifikacijskih  pristopov, ki na vhodu prejmejo črno-belo sliko, s pomočjo nevronske mreže izračunajo verjetnosti za posamezen razred barv (histogram), te potem pretvorijo v barvni komponenti $a*$ in $b*$ barvnega prostora CIE L*a*b*, te pa nato združijo s sivinsko sliko $L*$, da dobijo obarvano sliko.}
\label{im:class-scheme}
\end{figure}

Razrede smo dobili tako, da  komponenti $a*$ in $b*$ barvnega prostora CIE L*a*b* razdelimo v $400$ razredov, kar se je izkazalo za najbolje, saj s $400$ razredi lahko barve zapišemo tako, da izgub zaradi nenatančnega kodiranja uporabnik ne bo opazil, večje število razredov pa bi preveč upočasnilo učenje in napovedovanje. Vsako od komponent smo razdelili v $20$ razredov med vrednostima $-100$ in $100$, kar pomeni, da vsak razred zajema interval širine $10$. Vse kombinacije obeh komponent prinesejo $400$ razredov.

Pretvorba iz zapisa $a*b*$ v histogram se uporabi pri učenju, kjer originalno sliko pretovorimo v histogram, da lahko izračunamo napako. To izvedemo z enačbo 
\begin{equation}
l = 20 \left\lfloor\frac{a + 100}{10} \right\rfloor + \left\lfloor\frac{b + 100}{10} \right\rfloor,
\label{eq:ab2hist}
\end{equation}
kjer $a$ in $b$ predstavljata vrednost $a*$ in $b*$ slikovne točke, $l$ pa indeks razreda v histogramu, ki zavzema cela števila v intervalu $[0, 399]$. 

Pretvorba iz histograma v $a*$ in $b*$ se uporabi pri pretvorbi ocenjenih barvnih vrednosti s strani mreže in se izvede skladno z enačbo
\begin{equation}
\begin{gathered}
a = 10 \left\lfloor \frac{l}{20} \right\rfloor - 100 + 5 \\
b = 10 (l \Mod{20})  - 100 + 5.
\end{gathered}
\label{eq:hist2ab}
\end{equation}
Pri tem $a$ in $b$ predstavljata $a*$ in $b*$ barvne vrednosti slikovne točke, $l$ pa predstavlja indeks razreda v histogramu, ki je bil napovedan z največjo verjetnostjo. Vsem komponentam dodamo še vrednost $5$, tako da dobimo barvne vrednosti iz sredine vsakega razreda.

V tabeli \ref{tab:methods-class} so prikazani pristopi s klasifikacijo, njihova arhitektura in cenilna funkcija. Vsi pristopi s klasifikacijo uporabljajo lokalni pristop.

\begin{table}[hbt]
\caption{Lokalni klasifikacijski pristopi, njihove arhitekture, ki so podrobneje opisane v poglavju \ref{ch:arhitekture} in cenilne funkcije uporabljene za učenje. Cenilne funkcije so podrobneje opisane v poglavju \ref{ch:cenilne}}
\begin{center}
    \begin{tabular}{lcc}
  	\hline
	Pristop & Arhitektura & Cenilna funkcija \\
	\hline
	Klas. brez uteži - S+G. & S+G &  Divergenca KL \\
	Klas. brez uteži - D+G & D+G & Križna entropija \\
	Klas. z utežmi - S+G & S+G & Križna entropija z utežmi \\
	Klas. z utežmi - D+G & D+G & Križna entropija z utežmi \\
	\hline
    \end{tabular}
\end{center}
\label{tab:methods-class}
\end{table}

%----------------------------------------------------------------
% Poglavje (Chapter) 4: Vrednotenje
%----------------------------------------------------------------

\chapter{Vrednotenje}

V nalogi smo pristope naučili na različno velikih učnih množicah, jih preizkusili na testni množici in rezultate vrednotili s primerjanjem z originalno sliko, za kar smo uporabili dve metriki. Ker ta primerjava v vseh primerih ne zadošča, smo pristope vrednotili še z anketo.

\section{Postopek učenja}
\label{ch:postopekucenja}

V tem poglavju bomo predstavili podrobnosti učenja na manjši množici, na večji učni množici in si za konec pogledali, kakšne značilke prepozna posamezen nivo nevronske mreže. 

Za posodabljanje uteži mreže smo uporabili optimizator Adam, ki je trenutno najbolj v uporabi na nivoju nevronskih mrež. Pri tem so se za dobre izkazali parametri, ki so prikazani v tabeli \ref{tab:adam-param}. Prikazani parametri so bili izbrani z opazovanjem konvergence napake mreže, kjer so se izkazali za najboljšo izbiro. Pri vseh pristopih smo uporabili velikost serije (ang. {\em batch size}) $32$, razen pri učenju metode Zhang in sod., kjer smo morali zaradi večjih dimenzij tenzorjev in posledično pomanjkanja pomnilnika, uporabiti velikost serije $8$.

\begin{table}[hbt]
\caption{Parametri, s katerim smo Adam optimizatior nastavili. }
\begin{center}
\begin{tabular}{lcc}
\hline
Parameter & Vrednost parametra \\
\hline
stopnja učenja (ang. {\em learning rate}) & $10^{-4}$ \\ 
beta 1 & $0,9$ \\
beta 2 & $0,99$ \\ 
epsilon & $10^{-8}$ \\
\hline
\end{tabular}
\end{center}
\label{tab:adam-param}
\end{table}

Za učenje na manjši učni množici smo izbrali vse pristope, za učenje na večji učni množici smo izbrali sedem pristopov, pet lastnih in dva iz sorodnih del. Manjša in večja učna množica sta podrobno opisani v poglavju \ref{ch:podatki}. Odločili smo se za tri regresijske pristope: lokalna regresija z globalno mrežo, globalna regresija z globalno mrežo in globalna regresija z mrežo VGG-16. Izpustili smo oba pristopa brez globalne mreže, saj imata očitno slabše rezultate barvanja. 
Izbrali smo dva klasifikacijska pristopa --- klasifikacija brez uteži - S+G in klasifikacija z utežmi - S+G, ker se je izkazalo, da  arhitektura D+G poslabša rezultate, zato smo se odločili, da izvedemo le primerjavo dveh pristopov z arhitekturo S+G. 

%----------------------------------------------------------------
% Section: Podatki
%----------------------------------------------------------------

\section{Barvanje večjih slik}
\label{ch:vecjih}

Večina pristopov v sorodnih delih je naučenih za barvanje slik velikosti $224 \times 224$ in ima to omejitev, da omogoča le barvanje slik te velikosti. Iizuak in sod. \cite{Iizuka2016} omogočajo barvanje večjih slik, tako da večjo sliko podajo enaki mreži na vhod, ki nima omejitve za velikosti vhodne slike, saj je sestavljena le iz konvolucijskih nivojev. Pri tem avtorji komentirajo, da mreža deluje najbolje na slikah velikosti $224 \times 224$.

Z lokalnimi pristopi, ki smo jih implementirali v okviru tega dela, ta problem rešujemo drugače. Slike katerekoli velikosti večjih od $32 \times 32$ razdelimo na dele velikosti $32 \times 32$ s prekrivanjem, jo obarvamo po delih in potem spet sestavimo po principu opisanem v poglavju \ref{ch:parts-im}.

Primerjavo kakovosti barvanja večjih slik smo izvedli tako, da smo pristopa Iizuka in sod. ter lokalno regresijo z globalno mrežo preizkusili na istih slikah pomanjšanih na velikost $224 \times 224$ slikovnih točk, kjer naj bi bilo barvanje optimalno in velikost $896 \times 896$. Primerjava je izvedena na mrežah naučenih na manjši učni množici s $100.000$ slikami. 

\section{Podatki}
\label{ch:podatki}

Podatke, ki smo jih uporabili za učenje in validacijo pristopov, smo pridobili iz podatkovne zbirke ImageNet \cite{ILSVRC15}, ki vsebuje približno $14$ milijonov slik. Iz zbirke smo naključno izbrali množico podatkov in jih za namen učenja pretvorili v barvni prostor CIE L*a*b*. Pri preizkusu na manjši množici smo za učenje naključno izbrali $100.000$ slik, za validacijo pa $10.000$ slik iz nabora. Validacijska množica je bila obenem tudi testna množica. Zaradi praktično neomejene količine podatkov smo se odločili za fiksno testno množico namesto prečnega preverjanja. Za učenje na večji množici smo naključno izbrali $2.854.912$ slik.

Za vrednotenje barvanja večjih slik, opisanega v poglavju \ref{ch:vecjih}, podatki iz podatkovne zbirke ImageNet niso bili zadovoljivi, saj so slike večinoma velikosti manjših od $500 \times 500$ slikovnih točk. Odločili smo se, da testiranje izvedemo na slikah iz zbirke avtorja te naloge, ki so večje od velikosti $896 \times 896$, kar pomeni, da slik ni potrebno povečevati in s tem povzročati dodatnih napak v barvanju zaradi slabe kvalitete slik. Vzeli smo $584$ slik, za katere je aplikacija Google Photos\footnotemark{} ocenila, da gre za slike pohodništva. Za te slike smo se odločili, ker gre večinoma za slike narave, kjer je barvanje ponavadi najboljše in lahko razliko opazujemo na slikah, ki se večinoma barvajo dobro. 

\footnotetext{\url{http://photos.google.com}}

Za preizkus na starih črno-belih slikah smo izbrali raznovrstne slike iz dveh člankov iz spleta in zbirke starih črno-belih slik:
40 Must-See Photos From The Past\footnote{\url{http://www.boredpanda.com/must-see-historic-moments/}}, 
37 Wonderfully Weird Old Photos That Show Just How Much We’ve Changed\footnote{\url{http://www.lifebuzz.com/old-photos/}} in Old Photo Archive\footnote{\url{http://oldphotoarchive.com/}}.


%----------------------------------------------------------------
% Section: Racunanje napake
%----------------------------------------------------------------

\section{Računanje napake}
\label{ch:napake}

Za primerjavo pristopov smo napake računali na testni množici. Pri tem smo uporabili dve metriki: koren povprečne kvadratne napake (ang. {\em root mean squeared error}) ter razmerje med signalom in šumom (ang. {\em peak signal-to-noise ratio}).  

Koren povprečne kvadratne napake (RMSE) za vsako sliko smo izračunali s pomočjo enačbe 
\begin{equation}
\textrm{RMSE} = \sqrt{\sum^{h}_{i=1} \sum^{w}_{j=1} \sum^{c}_{k=1} (Y_{i, j, k} - \hat{Y}_{i, j, k})},
\label{eq:rmse}
\end{equation} 
kjer $h$ in $w$ prestavljata višino in širino slike ter $c$ predstavlja število kanalov slike. Oznaka $Y$ predstavlja originalno sliko (ang. {\em ground truth}) in $\hat{Y}$ obarvano sliko s strani pristopa za barvanje. Napaka je bila izračunana za vsako sliko posebej in kasneje povprečena preko vseh slik. Napaka RMSE je bila izračunana na slikah v barvnem prostoru CIE L*a*b* le za barvna kanala $a*$ in $b*$, saj za barvni kanal $L*$ izračun napake ni smiseln, ker so to vrednosti iz sivinske slike. 

Razmerje med signalom in šumom (PSNR) je metrika, ki kaže razmerje med največjo možno močjo signala in močjo šuma, ki signal pokvari. Primerna je za primerjave rekonstruiranih podatkov, kot so v našem primeru validacijske slike, ki jih poskušamo rekonstruirati s pomočjo pristopov, ki bazirajo na nevronskih mrežah. Vrednosti razmerja med signalom in šumom se merijo v enoti decibel ($dB$) \cite{Saupe2006}. Zadovoljive vrednosti rekonstrukcije slike $8$ bitnih podatkov, kamor sodijo tudi naši podatki, saj smo primerjali slike v barvnem prostoru \textit{RGB}, so med $30$ in $50$ dB \cite{welstead1999fractal}. 

Napako PSNR smo izračunali z enačbo
\begin{equation}
\textrm{PSNR} = 20 \log_{10}\left(\frac{MAX_I}{\textrm{RMSE}}\right),
\label{eq:psnr}
\end{equation}
v kateri ima $MAX_I$ največjo možno vrednost slikovne točke, kar je v barvnem prostoru RGB $255$, $\textrm{RMSE}$ pa je napaka izračunana z enačbo \ref{eq:rmse}. Napako smo povprečili preko vseh slik v testni množici. Za izračun napake smo izbrali barvni prostor RGB, saj računanje PSNR v prostoru L*a*b* ni možno, ker ne poznamo največje možne vrednosti signala za komponenti $a*$ in $b*$.

\section[Primerjava pristopov glede na realističnost barvanja]{Primerjava pristopov glede na \\ realističnost barvanja}

Izkaže se, da številčna napaka, izračunana s primerjavo z originalno sliko, ni vedno dobra metrika za kvaliteto barvanja, saj nas bolj kot natančna obarvanost zanima realističnost in naravnost slike. Številčna napaka ni najboljša metrika predvsem v naslednjih primerih:

\begin{itemize}

\item Nekateri objekti na sliki imajo lahko različne barve, zato v primeru, ko algoritem pobarva z drugačno, a še vedno smiselno barvo, primerjava z originalno sliko ne da pravilne ocene napake.

\item Odtenki na originalni sliki so lahko različno močni, medtem ko barvanje lahko izgleda enako naravno pri različno močnih barvah. Na primer travnik je lahko obarvan z bolj nežnimi sepia barvami ali bolj močno zeleno barvo. Oboje izgleda naravno, medtem ko številčna napaka preferira eno od teh rešitev.

\end{itemize}

Zaradi omenjenih problemov s številčno napako smo se odločili, da pristope primerjamo tudi s pomočjo spletne ankete. 
Anketirancem smo na zaslonu pokazali eno sliko obarvano z dvema različnima pristopoma, ti pa so morali oceniti, katera slika je bolje, oziroma bolj realistično obarvana. Slika \ref{im:evalvation-screen} prikazuje aplikacijo za ocenjevanje. Vsak anketiranec je ocenil $23$ parov slik, od katerih sta bili dve testni in nista upoštevani v evalvaciji. 
Ostalih $21$ je izbranih tako, da je vsak od anketirancev vsako od kombinacij pristopov ocenil enkrat. Anketiranec je vedno dobil drugo sliko, s čimer smo zmanjšali vpliv že videne slike na oceno. Slike smo izbirali po principu naključne zasnove poizkusa (ang. {\em randomized experimental design}) \cite{wu2006sampling}. Za tako zasnovo smo se odločili, da izničimo vse vplive, ki bi jih lahko povzročil določen vrstni red slik. 

\begin{figure}[htb]
\begin{center}
\centering
\includegraphics[width=13cm]{evaluation-1}
\end{center}
\caption{Aplikacija za vrednotenje kakovosti barvanja slik s pomočjo anketirancev. Anketiranec je v posameznem koraku dobil na zaslon sliko obarvano z dvema pristopoma. S klikom na sliko je ocenil, katera je bolj naravno obarvana. }
\label{im:evalvation-screen}
\end{figure}

Evalvacijo smo izvajali na skupno $100$ slikah, ki so bile izbrane naključno iz množice $10.000$ testnih slik. V evalvacijo je bilo vključenih sedem pristopov naučenih na večji učni množici, ki so našteti v poglavju \ref{ch:postopekucenja}.

Spletno anketo za ocenjevanje smo implementirali v ogrodju Django\footnote{\url{https://djangoproject.com}} in je vsebovala štiri prikaze. Prvi je bil zaslon s kratkimi navodili za uporabnika. Sledil je zaslon, ki je bil namenjen kratkemu opisu poteka evalvacije, s čimer smo poskrbeli, da uporabnik na prvem zaslonu ni dobil preveč informacij. Sledilo je $23$ ponovitev tretjega zaslona, na katerem je potekala evalvacija in je prikazan na sliki \ref{im:evalvation-screen}. Na koncu je sledil zaslon z zahvalo in povabilom na ponovno evalvacijo. V primeru, da se je uporabnik odločil za ponovno evalvacijo, smo poskrbeli, da je vedno dobil nove slike, ki jih prej še ni videl. V primeru, da je ocenil že vse slike, mu je bila nadaljnja evalvacija onemogočena. Izvorna koda aplikacije je objavljena na GitHubu PrimozGodec/EvaluationApp\footnote{\url{https://github.com/PrimozGodec/EvaluationApp}}.

Anketiranje je potekalo v dneh od $25.$ do vključno $27.$ julija $2017$. Anketirance smo pridobili z objavo na socialnih omrežjih Facebook in LinkedIn. V anketi smo zbrali odzive $1010$ anketirancev. Anketiranci so v povprečju ocenili $21,49$ slik, če iz statistke izključimo dve testni sliki, ki sta bili namenjeni privajanju na način evalvacije. Večina anketirancev, $838$, je izpolnila anketo samo enkrat, $90$ anketirancev se je odločilo za vsaj eno ponovno evalvacijo, $82$ anketirancev pa je anketo zapustilo predčasno in so ovrednotili manj kot $21$ slik. Zbrani podatki v obliki datoteke \textit{json} so objavljeni na GitHubu PrimozGodec/EvaluationApp\footnote{\url{https://github.com/PrimozGodec/EvaluationApp}}.


%----------------------------------------------------------------
% Poglavje (Chapter) 5: Rezulatati in diskusija
%----------------------------------------------------------------

\chapter{Rezultati in diskusija}
\label{ch:rezultati}

V tem poglavju predstavljamo natančnosti pristopov naučenih na manjši množici in jih med seboj primerjamo. Pogledali si bomo primerjavo pristopov naučenih na večji učni množici in primerjali pristope pri barvanju večjih slik od tistih, na katerih so bili pristopi naučeni.

\section[Primerjava pristopov na manjši učni množici]{Primerjava pristopov na manjši\\ učni množici}
\label{ch:prim-manjsa}

Tabela \ref{tab:napake-100} prikazuje natančnost pristopov na testni množici slik. Izkaže se, da se na manjši množici najbolje obnese pristop Iizuka in sod., ki je glede na napako RMSE za $0,066$ boljši od našega pristopa z globalno regresijo. Ostali pristopi, razviti s strani drugih avtorjev, se na tej množici obnesejo slabše od večine naših pristopov. 

Izkazalo se je tudi, da se na tej množici, glede na napako, regresijski pristopi obnesejo bolje kot pristopi s klasifikacijo. Pristop lokalna regresija se s klasifikacijo brez uteži z arhitekturo D+G glede na RMSE razlikuje skoraj za $2$. Omenjena pristopa imata enako arhitekturo mreže. Med pristopi z regresijo je opaziti boljše rezultate pri tistih, ki barvajo celotno sliko naenkrat. Opazimo lahko tudi, da globalna mreža prinese izboljšave glede na RMSE nekje od  $0,3$ do $0,4$. Pri klasifikacijskih pristopih se je izkazalo, da arhitektura S+G deluje bolje pri tej učni množici. Izkaže se tudi, da uteži v cenilni funkciji ne prinesejo izboljšave v natančnosti.

\begin{table}[hbt]
\caption{Tabela prikazuje napake izračunane na testni množici podatkov. Za vsakega od pristopov smo izračunali napaki opisani v poglavju \ref{ch:napake}. V zgornjem delu tabele so prikazane napake na pristopih iz sorodnih del, v vmesnem napake na pristopih z regresijo in v spodnjem delu tabele napake na pristopih s klasifikacijo.}
\begin{center}
    \begin{tabular}{lccc}
    	\hline
        Pristop & RMSE & PSNR \\
        \hline
        Zhang in sod. & 15,004 & 22,252 \\
        Iizuka in sod. & 12,941 & 23,439 \\
        Dahl & 13,936 & 22,551 \\
        \hline
        Reg. lokalna & 13,216 & 23,199 \\
        \hspace{0.5em} - brez softmax & 13,206 & 23,183 \\
        \hspace{0.5em} - brez globalne mreže & 13,767 & 22,840 \\
        Reg. globalna & 13,007 & 23,434 \\
        \hspace{0.5em} - brez globalne mreže & 13,334 & 23,068 \\
        Reg. globalna VGG & 13,387 & 23,131 \\
        \hline
        Klas. brez uteži - S+G & 14,336 & 22,738 \\
        Klas. brez uteži - D+G & 15,086 & 22,380 \\
        Klas. z utežmi - S+G & 14,573 & 22,610 \\         
        Klas. z utežmi - D+G & 15,137 & 22,395 \\ 
       	\hline
    \end{tabular}
\end{center}
\label{tab:napake-100}
\end{table}

Za vsak pristop smo napake za slike iz testne zbirke spremenili v range glede na napako RMSE na določeni sliki, ki se raztezajo od najboljše z rangom $0$, do najslabše z rangom $9.999$. Izkaže se, da rangi med pristopi močno korelirajo (slika \ref{im:ranks-between-methods}). To pomeni, da je natančnost barvanja slike v veliki meri odvisna od motiva na sliki, kar je bilo pričakovati.

Korelacija je v veliki meri prisotna pri vseh pristopih, je pa nekoliko različna glede na sorodnost pristopov (tabela \ref{tab:spearman} v prilogi). Pristopa klasifikacija brez uteži - D+G in klasifikacija z utežmi - D+G (slika \ref{im:ranks-between-methods}, desno), ki sta si bolj podobna glede na arhitekturo in način barvanja, imata tako zelo veliko korelacijo. Pristopa klasifikacija brez uteži - D+G in Dahl (slika \ref{im:ranks-between-methods}, levo), ki sta si na način napovedovanja bolj različna, prvi je regresijski in drugi klasifikacijski, imata manjšo korelacijo. Še vedno so točke razporejene okoli premice, ki razpolavlja kvadrant grafa, vendar je odstopanj več. Podobne slike dobimo tudi pri primerjavi ostalih pristopov. 

\begin{figure}[htb]
\begin{center}
\centering
\includegraphics[width=6cm]{ranks_dahl_arh2-2}
\includegraphics[width=6cm]{rank_arh2_arh2-2}
\end{center}
\caption{Primerjava rangiranja slik glede na napako RMSE pri dveh različnih pristopih barvanja. Os $X$ predstavlja rang pri prvem pristopu, $Y$ pa rang pri drugem pristopu. Prva slika prikazuje primerjave rangov Dahlovega pristopa in klasifikacijskega pristopa z arhitekturo D+G. Druga slika prikazuje range pri dveh klasifikacijskih pristopih z enakimi arhitekturami.}
\label{im:ranks-between-methods}
\end{figure}

Ker smo želeli podobnost pristopov med seboj primerjati v prostoru, smo izračunali Spearmanovo korelacijo rangov \cite{hauke2011comparison} za vsak par pristopov. Korelacije so številčno prikazane v tabeli \ref{tab:spearman} v prilogi. Za izris podobnosti (slika \ref{im:methods-mds}) smo uporabili metodo večdimenzionalno skaliranje (ang. {\em multidimensional scaling} - MDS) \cite{Wickelmaier2003} na Spearmanovih korelacijah. Uporabili smo implementacijo v programu Orange \cite{demvsar2013orange}. 

Pristopi s klasifikacijo so skupaj (levo na sliki) in so bolj oddaljeni od tistih z regresijo (desno na sliki). Pri pristopih s klasifikacijo opazimo, da na različnost bolj vpliva vrsta arhitekture kot uporaba uteži za pogostost barve. Izkaže se, da je pristop Zhang in sod. bližje tistim z arhitekturo D+G. Glede na to, da so lastnosti teh arhitektur popolnoma drugačne, se izkaže, da na podobnost glede na napake vpliva predvsem globina arhitekture. 

Pri regresijskih pristopih lahko opazimo, da je največja razlika glede na uporabo globalne mreže. Pristopi, ki ne uporabljajo globalne mreže, so na vrhu prikaza, ostali so spodaj. Globalna regresija VGG je bližja pristopom z globalno mrežo. To gre verjetno pripisati dejstvu, da ta pristop uporablja mrežo VGG-16, ki je del globalne mreže pri ostalih pristopih, vendar ta pristop to mrežo izkorišča kot glavno. 

Čeprav je Dahlov pristop glede na arhitekturo popolnoma različen od naših, se glede na napake izkaže podoben pristopom brez globalne mreže, kar še dodatno potrdi deljenje pristopov glede na prisotnost globalne mreže. Pristop Iizuka in sod. je v gruči s pristopi, ki uporabljajo globalno mrežo, saj tudi sam uporablja podoben pristop. Pri pristopih z regresijo lahko opazimo še, da sta pristopa Iizuka in sod. ter globalni regresijski pristop bolj skupaj, saj oba delujeta na celotni sliki. 

\begin{figure}[htb]
\begin{center}
\centering
\fbox{\includegraphics[width=12.5cm]{methods_mds-3}}
\end{center}
\caption{Primerjava pristopov v prostoru MDS kaže na sorodnosti med pristopi glede na vrsto pristopa (klasifikacija - označeno z rdečo in regresija - označena z modro), arhitekturo mreže in načinom napovedovanja (lokalni - označeno s krogom ali globalni - označeno s kvadratom).}
\label{im:methods-mds}
\end{figure}

Zanimalo nas je tudi, katere so tiste slike, kjer je eden od pristopov boljši, ostali pa slabši. Na sliki \ref{im:ranks-between-methods} so taki primeri točke, ki ležijo stran od diagonale. Te slike smo našli z metodo za iskanje osamelcev (ang. {\em outliers}) \cite{Ramaswamy}, ki poišče slike, ki so najbolj oddaljene od diagonale v večdimenzionalnem prostoru vseh pristopov. 

Slike, ki najbolj izstopajo glede na napako na različnih pristopih, so prikazane kot točke v prostoru MDS, konstruiranem glede na range slik (slika \ref{im:images-mds}). Ob pregledu slik se izkaže, da gre tukaj večinoma za slike, kjer je težje zaznati teksturo. Ob tem predvidevamo, da so se določeni pristopi bolje naučili ravno te teksture kot drugi pristopi. 

Napaka je močno povezana z motivom na sliki. V prostoru MDS so bližje skupaj slike s podobnim motivom in barvami. Na levi strani so prikazane tri slike, ki so blizu skupaj in jim je skupno to, da je na sliki morje ali nebo, ki sta oba modre barve in imata prisoten določen objekt (v našem primeru žival). Na desni strani sta dve sliki, ki se tudi ujemata glede na odtenke v sliki, čeprav je motiv popolnoma drugačen. 

\begin{figure}[htb]
\begin{center}
\centering
\fbox{\includegraphics[width=13cm]{images_mds}}
\end{center}
\caption{Razporeditev slik v prostoru MDS, ki zajema $100$ slik, ki najbolj izstopajo glede na različnost rangov pri pristopih. Prostor je konstruiran glede na kosinusno razdaljo med vektorji rangov slik. Opazimo lahko, da so v prostoru podobne slike bližje skupaj. Dve podobni skupini slik sta prikazani ob robu.   }
\label{im:images-mds}
\end{figure}

Primerjave barvanja slik po pristopih so prikazane na sliki \ref{im:images-100-compare-reg} za regresijo in na sliki \ref{im:images-100-compare-klas} za klasifikacijo. Slike smo izbrali tako, da prva dva stolpca prikazujeta dve sliki iz množice dvajset najbolje obarvanih s strani vseh pristopov, tretji in četrti stolpec prikazujeta slike, ki so bile različno dobro obarvane s strani različnih pristopov. Ti sliki sta izbrani izmed točk v prostoru na sliki \ref{im:images-mds}. Zadnja dva stolpca prikazujeta slike, ki so bile v množici dvajset najslabše obarvanih s strani vseh algoritmov. 

Opazimo lahko, da sliki v prvih dveh stolpcih spadata v skupino najbolje obarvanih slik zato, ker imajo že originalne slike prisotne zelo nenasičene (blede) odtenke barv. Pristopi, posebej regresijski, ki običajno obarvajo z bolj nenasičenimi barvami, so se zato zelo približali originalni sliki, čeprav barvanje v več primerih ni ravno najboljše. Pri drugem in tretjem stolpcu so se nekateri pristopi dobro približali pravi barvi, drugi pa so slike obarvali napačno. Sliki iz zadnjih dveh stolpcev sta bili glede na napako v množici najslabše obarvanih slik zato, ker imajo originalne slike zelo močne odtenke, katerim se pristopi niso približali. Kljub temu so nekatera barvanja dovolj naravna v primeru, da jih ne primerjamo z originalno sliko.

V primerjavi s pristopi iz sorodnih del tudi tu opazimo, da najboljše barva pristop Iizuka in sod., ki je imel tudi najmanjšo napako. Zhang in sod. se na določenih delih obnese dobro, vendar so slike zelo lisaste in nepopolno obarvane, medtem ko so pri pristopu Dahl odtenki zelo rjavi, čeprav vmes lahko opazimo nekaj pravih barv.

Pri primerjavi regresijskih pristopov lahko opazimo, da je po pričakovanjih najboljše barvanje s strani globalne regresije z globalno mrežo, čeprav lokalna regresija ne zaostaja dosti. Opazimo lahko tudi pomen in izboljšavo z uporabo globalne mreže. Enaki pristopi brez globalne mreže so obarvali bolj nenatančno, nenaravno, prisotnih je tudi več rjavih odtenkov. 

Pri klasifikacijskih pristopih opazimo, da pristopi z arhitekturo S+G dajejo boljše rezultate kot tisti z D+G, kjer barvanja skorajda ni. Pri pregledu slik in primerjavi klasifikacije z utežmi in brez na slikah opazimo, da pristop z utežmi barva z močnejšimi odtenki kot tisti brez, kar je bilo za pričakovati, saj je namen uteži zmanjšati izbor šibkejših odtenkov, ki imajo $a*$ in $b*$ vrednost bližje nič. Kljub barvanju z močnejši odtenki barv in s tem približevanju realni barvi, je na pogled barvanje brez uteži bolj naravno, saj je opaziti manj napak v barvanju. Za primer lahko vzamemo sliko s ptico, kjer sta les in ptica pobarvana bolj realno in letalo nima sivega pasu okoli sebe.

Iz primerjave barvanja na slikah \ref{im:images-100-compare-reg} in \ref{im:images-100-compare-klas} lahko opazimo, da pristopi z regresijo obarvajo bolje in bolj naravno kot pristopi s klasifikacijo, čeprav je nekaj izjem pri barvanju neba in praproti. Izkaže se tudi, da barvanje z regresijo večkrat obarva z bolj rjavimi odtenki, kar pri klasifikacijskih pristopih ni zaznati. Tam je bolj pogosto, da slika ni obarvana. 

% \afterpage{\clearpage}
\begin{figure}[htbp]
\begin{center}
\centering
\includegraphics[width=10.5cm]{images-methods-comparison-100-reg-2}
\end{center}
\caption{Slike iz testne množice, ki so bile obarvane z regresijskimi pristopi opisanimi v tem delu in pristopi iz sorodnih del. Vsaka vrstica prikazuje drug pristop, prva vrstica prikazuje originalno sliko. Sliki v prvih dveh stolpcih sta bili izbrani iz množice $20$ najbolje obarvanih slik glede na rang, srednji dve iz množice $100$ slik, ki najbolj izstopajo glede na različnost rangov pri pristopih in zadnji dve iz množice $20$ najslabše obarvanih slik. }
\label{im:images-100-compare-reg}
\end{figure}

% \afterpage{\clearpage}
\begin{figure}[htbp]
\begin{center}
\centering
\includegraphics[width=11.3cm]{images-methods-comparison-100-klas-2}
\end{center}
\caption{Slike iz testne množice, ki so bile obarvane s klasifikacijskimi pristopi opisanimi v tem delu in pristopi iz sorodnih del. Vsaka vrstica prikazuje drug pristop, prva vrstica prikazuje originalno sliko. Sliki v prvih dveh stolpcih sta bili izbrani iz množice $20$ najbolje obarvanih slik glede na rang, srednji dve iz množice $100$ slik, ki najbolj izstopajo glede na različnost rangov pri pristopih in zadnji dve iz množice $20$ najslabše obarvanih slik.}
\label{im:images-100-compare-klas}
\end{figure}

% here
\section[Primerjava pristopov na večji učni množici]{Primerjava pristopov na večji \\ učni množici}
\label{ch:rez-vecji}

V tabeli \ref{tab:napake-full} so prikazane napake pristopov, ki so naučeni na večji učni množici. Opazimo, da je razmerje med pristopi ostalo nespremenjeno glede na rezultate v poglavju \ref{ch:prim-manjsa}. Prav pri vseh pristopih se  je po pričakovanjih izboljšala natančnost barvanja. Kot lahko opazimo, če rezultate primerjamo s tistimi v tabeli \ref{tab:napake-100}, smo največjo izboljšavo pridobili pri pristopu Iizuka in sod. in pristopu klasifikacija z utežmi z arhitekturo S+G. 

\begin{table}[hbt]
\caption{Napake izbranih pristopov izračunane na testni množici podatkov. Za vsakega od pristopov smo izračunali dve napaki opisani v poglavju \ref{ch:napake}. V zgornjem delu tabele so prikazane napake na pristopih iz sorodnih del, v vmesnem napake na pristopih z regresijo in v spodnjem delu tabele napake na pristopih s klasifikacijo.}
\begin{center}
    \begin{tabular}{lccc}
    	\hline
        Pristop & RMSE & PSNR \\
        \hline
        Iizuka in sod. & 12,252 & 23,831 \\
        Dahl & 13,745 & 22,827 \\
        \hline
        Reg. lokalna & 12,960 & 23,363 \\
        Reg. globalna & 12,368 & 23,829 \\
        Reg. globalna VGG & 12,976 & 23,398 \\
        \hline
        Klas. brez uteži - S+G & 14,015 & 22,909 \\
        Klas. z utežmi - S+G & 14,326 & 22,717 \\         
       	\hline
    \end{tabular}
\end{center}
\label{tab:napake-full}
\end{table}

Slika \ref{im:full-learning} prikazuje izboljšanje barvanja po prvih desetih korakih učenja. Korak predstavlja učenje na sklopu $50.000$ slik. Deset korakov smo izbrali, ker je tu viden največji napredek. Izkaže se, da je pri vseh pristopih največja razlika narejena že v prvem koraku, v nadaljnjih pa se dogajajo spremembe, ki večinoma barvanje naredijo bolj realno. 

\begin{figure}[htbp]
\begin{center}
\centering
\includegraphics[width=10.6cm]{n00443692_1173-learning-3}
\end{center}
\caption{Napredovanje barvanja po prvih desetih korakih učenja pri različnih prestopih. Stolpec predstavlja pristop, vsaka vrstica pa posamezen korak. }
\label{im:full-learning}
\end{figure}

Za konec predstavitve smo izbrali še nekaj slik, ki so bile dobro obarvane pri skoraj vseh pristopih in nekaj slik, katerih barvanje je bilo slabo ali delno slabo v vseh primerih.

Dobro obarvane slike so prikazane na sliki \ref{im:images-full-compare-1}. Te slike so v večini slike narave in tiste z zelo pogostimi motivi, ki imajo enako barvo v vseh primerih. Na primer rdeč opečnat zid na zadnji sliki je zelo dobro obarvan, saj je vedno enake barve, prav tako rdeč paradižnik. Opazimo lahko, da pristopi Iizuka in sod ter lokalna regresija in globalna regresija v večji meri barvajo bolj natančno. Izkaže se, da pristopa Iizuka in sod. in globalna regresija nimata bistvenih razlik v kakovosti barvanja pri slikah, ki sodijo v množico dobro obarvanih slik. 
Sklepamo, da se globalni regresijski pristop izkaže za slabšega od pristopa Iizuka in sod. na slikah, ki sodijo v množico slabše obarvanih slik. Lokalna regresija nekoliko zaostaja, vendar je barvanje še vedno realno. Klasifikacijska pristopa se izkažeta za manj natančna, vidi pa se, da pristop z utežmi poskuša barvati z močnejšimi odtenki. To se najbolje opazi pri paradižniku, ki je še najbolje obarvan prav s tem pristopom. Izkaže se, da so največje razlike pri barvanju pri podvodnih slikah, mogoče bi to lahko pripisali manj očitnim teksturam v sliki. Presenečeni smo nad kvaliteto barvanja košarkarske žoge.

%\afterpage{\clearpage}
\begin{figure}[htbp]
\begin{center}
\centering
\includegraphics[width=11.5cm]{images-methods-comparison-full-7}
\end{center}
\caption{Slike iz testne množice, katerih barvanje se je izkazalo za dobro. Vsak stolpec predstavlja enega od pristopov opisanih v delu. }
\label{im:images-full-compare-1}
\end{figure}

Slika \ref{im:images-full-compare-2} prikazuje slike, ki so obarvane slabše. Slike so obarvane slabo iz več razlogov. Pri večini gre za problem pri predmetih z neenoličnimi barvami. V tem primeru nekateri pristopi obarvajo naravno, vendar drugače kot je v originalu, s čimer ni nič narobe, nekateri pa obarvajo popolnoma narobe. Seveda je vse odvisno od motiva. Šopek rož je na primer praktično pri vseh regresijskih pristopih obarvan naravno. Tudi jakna na sliki je v nekaterih primerih obarvana naravno, medtem ko notranjost prostorov in zunanjost hiš ni prepričljivo obarvana. 
V nekaterih primerih pride do napake, ko določen predmet ali žival dobi barvo okolice. To se večkrat zgodi pri lokalnih pristopih vendar ni zelo običajno. Sklepamo lahko, da se ti pristopi občasno preveč opirajo na globalno mrežo. Veliko slik je obarvanih s premalo nasičenimi barvami. To se zgodi pri predmetih, ki nimajo enolične barve. Na primer rdeč avto kaže zametke rdečih odtenkov, ki pa niso ravno prepričljivi. Pri sliki v drugi vrsti so skalne stene zelo močno rdečih odtenkov. Ker mreža večkrat vidi primer sivih skal, je tudi tukaj barvanje bolj sivo kot rdeče. 

Kot smo ugotovili že v poglavju \ref{ch:prim-manjsa}, lahko tudi na primerih slik zaključimo, da je kvaliteta barvanja v veliki meri odvisna od motiva na sliki. Večino dobro obarvanih slik je pri vseh pristopih obarvano pristopu primerno, medtem kot tiste slabo obarvane, večinoma slabo obarvane pri vseh pristopih. Barvanje se redko približa kvaliteti originalne slike, vendar v večini primerov uporabi prave barve, odtenki pa niso vedno najbolj prepričljivi.

\begin{figure}[htbp]
\begin{center}
\centering
\includegraphics[width=11.7cm]{images-methods-comparison-full-8}
\end{center}
\caption{Slike iz testne množice, katerih barvanje se je izkazalo za slabše. Vsak stolpec predstavlja enega od pristopov opisanih v delu. }
\label{im:images-full-compare-2}
\end{figure}


\section[Primerjava pristopov glede na realističnost barvanja]{Primerjava pristopov glede na \\ realističnost barvanja}

Za primerjavo pristopov smo zgradili model Bradley–Terry  \cite{hunter2004mm}. Parametre smo ocenili z metodo največjega verjetja (ang. {\em  maximum likelihood}). Model je zgrajen tako, da nam je v pomoč pri rangiranju podatkov pridobljenih v medsebojni primerjavi parov. Pri katerem ni nujno, da so primerjave popolne in enako pogoste za pare.

Model je bil zgrajen na podlagi primerjav prikazanih v tabeli \ref{tab:rez-survey} v prilogi. Izračunana sta bila parametra $\gamma_i$ in $\beta_i$, ki sta si v razmerju $\gamma_i = e^{\beta_i}$, kjer je $i$ zaporedna številka pristopa. Večja vrednost parametra pomeni pristop, ki se je bolje izkazal glede na evalvacijo. Parametri so prikazani v tabeli \ref{tab:rang-survey}.

\begin{table}[hbt]
\caption{Vrednosti parametrov modela Bradley-Terry za pristope, ki jih primerjamo. Večja vrednost pomeni, da se je pristop bolje izkazal pri ocenjevanju.}
\begin{center}
    \begin{tabular}{lccc}
    	\hline
        Pristop & $\gamma_i$ & $\beta_i$ \\
        \hline
        Iizuka in sod. & 0,277 & -1,28 \\
        Dahl & 0,125 & -2,08 \\
        \hline
        Reg. lokalna & 0,106 & -2,25 \\
        Reg. globalna & 0,189 & -1,67 \\
        Reg. globalna VGG & 0,130 & -2,04 \\
        \hline
        Klas. brez uteži - S+G & 0,098 & -2,32 \\
        Klas. z utežmi - S+G & 0,076 & -2,58 \\         
       	\hline
    \end{tabular}
\end{center}
\label{tab:rang-survey}
\end{table}
 
Če rezultate primerjamo s tistimi v poglavju \ref{ch:rez-vecji}, kjer smo pristope primerjali glede na izračunano napako, vidimo določene podobnosti in tudi razlike. Najbolje se je enako kot pri napaki s primerjavo z originalno sliko izkazal pristop Iizuka in sod. Zaostaja naš globalni regresijski pristop, do spremembe pa je prišlo pri globalnem regresijskem pristopu z mrežo VGG, ki se je glede na oceno anketirancev izkazal za boljšega od lokalne regresije. Enako kot prej je pristop, ki ga je razvil Dalh, boljši od klasifikacijskih, ki se tudi v primeru evalvacije s pomočjo anketirancev izkažeta za slabša. 


\section{Barvanje večjih slik}

Tabela \ref{tab:vecjih} prikazuje napake pri dveh velikostih slik na dveh pristopih. Ena velikost je velikost na kateri je bila mreža naučena, druga pa je štirikratna velikost slik v višino in širino. Izkaže se, da ima pristop lokalna regresija z globalno mrežo zelo majhno razliko v napaki, pri barvanju slik večjih velikosti glede na napako na osnovni velikosti, medtem ko je ta razlika pri pristopu Iizuka in sod. merjena v RMSE kar $6,18$. 

\begin{table}[htb]
\caption{Primerjava napak pristopov Iizuka in sod. ter lokalna regresija z globalno mrežo pri barvanju dveh velikosti slik. $224 \times 224$ je velikost na kateri je bila mreža naučena, druga velikost je uporabljena za testiranje razlike v barvanju večjih slik. Za računanje napake so uporabljene metrike opisane v poglavju \ref{ch:napake}.}
\begin{center}
\begin{tabular}{lccc}
\hline
Pristop & Velikost slik & RMSE & PSNR \\
\hline
\multirow{2}{*}{Iizuka in sod.} & 224 & 10,018 & 24,750 \\
 								& 896 & 16,136 & 20,906 \\
\hline
\multirow{2}{*}{Reg. lokalna} & 224 & 9,892 & 24,700 \\
 								& 896 & 10,096 & 24,523 \\
\hline
\end{tabular}
\end{center}
\label{tab:vecjih}
\end{table}


\section{Barvanje starih slik}

Glavna motivacija magistrskega dela je bila razviti pristop za barvanje črno-belih slik z namenom, da obarvamo stare črno-bele slike. 
Zato smo pristop uporabili na množici zgodovinskih slik. Za barvanje zgodovinskih slik smo uporabili pristop, ki se je najbolje obnesel, to je globalna regresija. 

Rezultati barvanja zgodovinskih slik so prikazani na sliki \ref{im:history}. Iz rezultatov lahko opazimo dobro barvanje objektov z enolično določeno barvo. Nekaj več napak zaradi pomanjkljive kvalitete slik lahko opazimo na nekaterih delih. Tam, kjer je barva neenolična, je prisotnih več rjavih odtenkov, česar smo že vajeni iz prejšnjih primerov. Slike niso enake tistim, ki bi bile zajete z barvnim fotoaparatom, če bi obstajal, ampak so bolj nežnih in nenasičenih odtenkov. V večini primerov so barve smiselne in doprinesejo k živahnosti fotografije. 

\begin{figure}[htbp]
\begin{center}
\centering
\includegraphics[width=11cm]{old-2}
\end{center}
\caption{Pari črno-belih zgodovinskih slik in obarvanih slik. Slike so pridobljene iz spletnih podatkovnih zbirk navedenih v poglavju \ref{ch:podatki}.}
\label{im:history}
\end{figure}

\section{Konvergenca nevronske mreže}

Pri učenju smo beležili vrednosti cenilne funkcije po vsakem končanem prehodu čez vse podatke (ang. {\em epoch}) na učni množici in validacijskih množici. S tem smo opazovali, kdaj je določen pristop optimalno naučen. To se v našem primeru zgodi v trenutku, ko vrednosti cenilne funkcije na validacijski množici prenehajo padati ali začnejo naraščati. V tem trenutku je naša mreža optimalno naučena, zato smo te uteži uporabili za testiranje. Grafi padanja cenilnih funkcij za vse pristope naučene na manjši učni množici so prikazani na sliki \ref{im:histograms-100}. 

%\afterpage{
\begin{figure}[p]
\begin{center}
\centering
\includegraphics[width=12cm]{histograms-100-3}
\end{center}
\caption{Prikaz padanja napake modela pri učenju na manjši množici. Za vsak prehod preko vseh podatkov (ang. {\em epoch}) je prikazana vrednost cenilne funkcije na učni in validacijski množici. }
\label{im:histograms-100}
\end{figure}
%}

Enako kot v primeru na manjši učni množici smo si tudi pri večji izrisovali vrednosti cenilne funkcije na učni množici in validacijski množici. Spreminjanje teh vrednosti je prikazano na sliki \ref{im:histograms-full}. 

\begin{figure}[hbt]
\begin{center}
\centering
\includegraphics[width=12cm]{histograms-full-2}
\end{center}
\caption{Prikaz padanja napake modela pri učenju na večji množici. Za vsak prehod preko $50.000$ slik je prikazana vrednost cenilne funkcije na učni množici in validacijski množici. }
\label{im:histograms-full}
\end{figure}

\section{Pomen nivojev mreže}

Konvolucijsko nevronsko mrežo si lahko predstavljamo kot nivoje, ki poskrbijo za zajem značilk iz slike. V preteklosti so to počeli z različnimi pristopi, kot so SIFT \cite{ke2004pca}, HOG \cite{ke2004pca}, SURF \cite{bay2006surf} in ostalimi. Nevronska mreža za to poskrbi sama in izlušči tiste značilke, ki so za določeno nalogo relevantne. Uporabljene značilke lahko v grobem vidimo z vizualizacijo izhodov konvolucijskih nivojev. 
 
V tem poglavju bomo pogledali, katere značilke zaznajo nivoji. V ta namen smo izrisali izhode prvih šestih konvolucijskih nivojev nevronske mreže, ki so prikazani na sliki \ref{im:layers-vis}. Vsak nivo predstavlja več slik, ki so izhodi posameznih filtrov, število slik pa je odvisno od števila filtrov. Čeprav ima mreža več nivojev, smo se odločili, da prikažemo le prvih šest, saj so ti najbolj razumljivi. Za vizualizacijo smo si izbrali globalni regresijski pristop z globalno mrežo, saj je ta najbolj zgovorna za vizualizacijo.

Slike prikažejo na katere elemente se filtri v posameznem nivoju odzivajo, oziroma kaj zaznavajo. V prvem nivoju lahko opazimo, da se v večji meri osredotočajo na robove v sliki. Opazimo lahko, da se nekateri odzovejo tudi na večji del slike, kar vidimo kot nekoliko okrnjeno vhodno sliko. V drugem nivoju  opazimo že bolj osredotočene odzive. Nekateri še vedno zaznajo robove, drugi pa se že osredotočijo samo na določene dele slike, na primer vodoravne ali navpične robove. Nekateri zaznajo tudi že dele, ki se enako obarvajo, na primer nebo v ozadju. 

V tretjem in četrtem nivoju filtri še v večji meri zaznavajo določene dele ali motive. Nekatere značilke je že težje razumeti in opisati. Še vedno je veliko filtrov, ki zaznavajo robove in površine, ki bodo kasneje enako obarvani. To se še vedno nadaljuje tudi v petem in šestem nivoju, kjer je še več značilk, ki imajo pomen za nevronsko mrežo, težje pa so razložljive nam ljudem. Opazimo lahko tudi, da se v kasnejših nivojih pojavlja tudi več izhodov z zelo malo ali praktično nič aktivacijami. Za te predvidevamo, da služijo drugačnim značilkam, ki jih v dani sliki ni bilo mogoče zaznati.

\begin{figure}[!htbp]
\begin{center}
\centering
\includegraphics[width=11cm]{layers-vis-2}
\end{center}
\caption{Vizualizacija izhodov prvih 6 konvolucijskih nivojev nevronske mreže na primeru slike Atenske akropole. Slika prikazuje, kaj v sliki zaznajo posamezni nivoji in posamezni filtri.    }
\label{im:layers-vis}
\end{figure}

%----------------------------------------------------------------
% Poglavje (Chapter) 6: Zaključek
%----------------------------------------------------------------

\chapter{Zaključek}

% kaj naredil
V okviru magistrskega dela smo podrobno raziskali področje barvanja črno-belih slik in videov. Ugotovili smo, da so regresijski pristopi bolj natančni, vendar barve niso tako nasičene in so dostikrat bolj sprane. Pristopi s klasifikacijo v osnovi barvajo z močnejšimi in bolj nasičenimi barvami, vendar je barvanje večinoma manj natančno. V primerjavi z obstoječimi pristopi, se je izkazalo, da je naš globalni pristop z regresijo skoraj tako natančen kot pristop Iizuka in sod., ki se je sicer izkazal za najboljšega. Implementacija naših pristopov se nahaja v GitHubu  PrimozGodec/ImageColorization\footnote{\url{https://github.com/PrimozGodec/ImageColorization}}.

Pri kakovosti barvanja z ra\-zli\-čni\-mi pristopi je prisotna velika korelacija, kar pomeni, da je kakovost barvanja zelo odvisna od motiva na sliki. Za primer lahko vzamemo slike z motivom narave, ki se barvajo mnogo bolje kot tiste z manj običajnimi motivi. Slike, ki od te korelacije najbolj odstopajo, so slike, kjer je težje prepoznati teksturo, vendar jo nekateri pristopi še vedno dobro prepoznavajo. Primer take teksture je nebo brez oblakov. Pri testiranju na večji učni množici smo ugotovili, da ta ne spremeni dosti razmerja v kakovosti barvanja med pristopi, je pa pri vseh pristopih opazno izboljšanje kvalitete barvanja tako pri opazovanju napake kot tudi na slikah. 

% kaj je novo
V okviru magistrske naloge smo implementirali več lokalnih pristopov, ki imajo drugačno strategijo barvanja od že obstoječih. Ti pristopi barvajo slike po delih. Kljub temu, da je natančnost teh pristopov v primerjavi s primerljivimi pristopi iz sorodnih del nekoliko slabša, ta pristop omogoča boljše barvanje slik velikosti, ki so različne od tistih, na katerih so bile naučene. Lokalni pristopi so zaradi manjše zahtevnosti povprečno tudi trikrat hitreje naučeni, saj uporabljamo manjše tenzorje, deli slik pa prispevajo dovolj informacij. 

% prihodnje delo
V prihodnosti bi se radi posvetili izboljšanju pristopov barvanja videa. Barvanja videa so se lotili že avtorji pristopov za barvanje slik\footnote{Primeri barvanja videov so dostopni na \url{http://hi.cs.waseda.ac.jp/~iizuka/projects/colorization/en/} in \url{http://richzhang.github.io/colorization/}.}, vendar se pri teh opazijo hitri preskoki med različnimi odtenki, ki so posledica barvanja posamezne slike v videu. Problem bi poskusili rešiti z upoštevanjem sosednjih slik. Izdelali bi tudi spletno aplikacijo, ki omogoča barvanje poljubnih slik uporabnikov.


%----------------------------------------------------------------
% SLO: bibliografija
% ENG: bibliography
%----------------------------------------------------------------
%\bibliographystyle{elsarticle-num}
\bibliographystyle{myieeetr}

%----------------------------------------------------------------
% SLO: odkomentiraj za uporabo zunanje datoteke .bib (ne pozabi je potem prevesti!)
% ENG: uncomment to use .bib file (don't forget to compile it!)
%----------------------------------------------------------------
\bibliography{bibliography,bibliography_web}

%----------------------------------------------------------------
% Poglavje: Priloge
%----------------------------------------------------------------

\appendix
%\addcontentsline{toc}{chapter}{Razširjeni povzetek}
\chapter{Spearmanova korelacija rangov med pristopi}

\begin{table}
\caption{Tabela prikazuje vrednosti Spearmanove korelacije rangov med pristopi opisanimi v tem delu. Podrobnosti so opisane v poglavju \ref{ch:prim-manjsa}. }
\tiny
\begin{center}
\begin{tabular}{p{1.9cm}ccccccccccccc}
	\hline
          & \rot[90]{Zhang in sod.} & \rot[90]{Iizuka in sod.} & \rot[90]{Dahl}      & \rot[90]{Reg. lokalna} & \rot[90]{Reg. lokalna - brez softmax } & \rot[90]{Reg. lokalna - brez globalne} & \rot[90]{Reg. globalna} & \rot[90]{Reg. globalna - brez globalne} & \rot[90]{Reg. globalna VGG} & \rot[90]{Klas. brez uteži - S+G} & \rot[90]{Klas. brez uteži - D+G} & \rot[90]{Klas. z utežmi D+G} & \rot[90]{Klas. z utežmi - S+G} \\
\hline
Zhang  & 1,00    &0,86    &0,86    &0,86    &0,84    &0,88    &0,87    &0,88    &0,89    &0,90    &0,94    &0,92    &0,90  \\
Iizuka &0,86    &1,00    &0,89    &0,94    &0,94    &0,90    &0,94    &0,92    &0,93    &0,90    &0,85    &0,85    &0,88     \\
Dahl      &0,86   &0,89   &1,00  &0,90   &0,90   &0,98    &0,88    &0,95    &0,91    &0,86    &0,88    &0,87    &0,84     \\
R. lok.&0,86    &0,94    &0,90    &1,00    &0,94    &0,90    &0,93    &0,91    &0,93    &0,90    &0,86    &0,85    &0,88     \\
R. lok. brez sm.&0,84   &0,94   &0,90    &0,94    &1,00    &0,91    &0,93    &0,91    &0,92    &0,87    &0,84    &0,83    &0,86    \\
R. lok. brez gl.&0,88  &0,90  &0,98    &0,90  &0,91    &1,00    &0,90    &0,96    &0,92    &0,87    &0,89    &0,88    &0,85    \\
R. glob.&0,87  &0,94  &0,88    &0,93  &0,93    &0,90    &1,00    &0,91    &0,93    &0,90    &0,86    &0,86    &0,89    \\
R. glob. brez gl.&0,88  &0,92  &0,95    &0,91  &0,91    &0,96    &0,91    &1,00    &0,93    &0,87    &0,86    &0,85    &0,85    \\
R. glob. VGG&0,89  &0,93    &0,91    &0,93    &0,92    &0,92    &0,93    &0,93    &1,00    &0,90    &0,88    &0,88    &0,89    \\
K. brez ut. S+D &0,90  &0,90    &0,86    &0,90    &0,87    &0,87    &0,90    &0,87    &0,90    &1,00    &0,92    &0,92    &0,94    \\
K. brez ut. G+D&0,94  &0,85    &0,88    &0,86    &0,84    &0,89    &0,86    &0,86    &0,88    &0,92    &1,00    &0,98    &0,91    \\
K. ut. G+D&0,92  &0,85    &0,87    &0,85    &0,83    &0,88    &0,86    &0,85    &0,88    &0,92    &0,98    &1,00    &0,92    \\
K. ut. S+D&0,90  &0,88    &0,84    &0,88    &0,86    &0,85    &0,89    &0,85    &0,89    &0,94    &0,91    &0,92    &1,00    \\
\hline
\end{tabular}
\end{center}
\label{tab:spearman}
\end{table}

\chapter{Implementacije globokih mrež}

\section{Arhitektura S+G}
\label{ch:app_sg}

Arhitektura S+G predstavljena z implementacijo v vmesniku Keras:

\inputminted{python}{SG_arh.py}

\section{Arhitektura D+G}
\label{ch:app_dg}

Arhitektura D+G predstavljena z implementacijo v vmesniku Keras:

\inputminted{python}{DG_arh.py}

\section{Arhitektura X-VGG}
\label{ch:app_xvgg}

Arhitektura X-VGG predstavljena z implementacijo v vmesniku Keras:

\inputminted{python}{X_VGG_arh.py}



\chapter{Primerjava pristopov s spletno anketo}

\begin{table}[htb]
\caption{Razporeditev rezultatov evalvacije s spletno anketo. Števila prikazujejo kolikokrat so anketiranci izbrali pristop v vrstici za boljšega od tistega v stolpcu.}

\begin{center}
\begin{tabular}{lccccccc}
	\hline
          & \rot[90]{Iizuka in sod.} & \rot[90]{Dahl}      & \rot[90]{Reg. lokalna} & \rot[90]{Reg. globalna} &\rot[90]{Reg. globalna VGG} & \rot[90]{Klas. brez uteži - S+G} & \rot[90]{Klas. z utežmi - S+G} \\
\hline
Iizuka & &  700 & 765 & 642 & 716 & 743 & 796 \\
Dahl & 339 & & 551 & 395 & 488 & 601 & 647 \\
Regresija lokalna & 271 & 487 & & 346 & 501 & 518 & 622\\
Regresija globalna & 387 & 635 & 688 & & 635 & 656 & 719\\
Regresija globalna VGG & 314 & 543 & 543 & 394 & & 599 & 687\\
Klasifikacija brez uteži S+G & 298 & 431 & 518 & 370 & 428 &  & 561\\
Klasifikacija z utežmi S+G & 241 & 385 & 417 & 312 & 343 & 476 & \\
\hline
\end{tabular}
\end{center}
\label{tab:rez-survey}
\end{table}


%----------------------------------------------------------------
% SLO: zakomentiraj spodnji del, če uporabljaš zunanjo .bib datoteko
% ENG: comment the part below if using the .bib file
%----------------------------------------------------------------



\end{document}