document.tex

\documentclass[a4paper,12pt]{article}

\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{hyperref}
\usepackage{enumitem}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{dirtytalk}
\usepackage{siunitx}

%\usepackage{titlesec}
%\newcommand{\sectionbreak}{\clearpage}
%\setlist{nosep}

\newcommand{\image}[4]{\begin{figure}[h!] \centering \includegraphics[width=#1\linewidth]{figures/#2} \caption{#4} \label{#3} \end{figure}}
\newcommand{\bThreed}{B$^3$D }

\pgfplotsset{
	compat=1.5, 
	width=7cm,
	/pgfplots/ybar legend/.style={
    /pgfplots/legend image code/.code={%
       \draw[##1,/tikz/.cd,yshift=-0.25em]
        (0cm,0cm) rectangle (3pt,0.8em);},
   }
}
\pgfplotsset{%
    axis line origin/.style args={#1,#2}{
        x filter/.append code={ % Check for empty or filtered out numbers
            \ifx\pgfmathresult\empty\else\pgfmathparse{\pgfmathresult-#1}\fi
        },
        y filter/.append code={
            \ifx\pgfmathresult\empty\else\pgfmathparse{\pgfmathresult-#2}\fi
        },
        xticklabel=\pgfmathparse{\tick+#1}\pgfmathprintnumber{\pgfmathresult},
        yticklabel=\pgfmathparse{\tick+#2}\pgfmathprintnumber{\pgfmathresult}
    }
}

\author{Moravec Vojtěch}
\title{Metody komprese bioinformatických dat pro přenos na HPC infrastrukturu}
\date{2018/2019}

\begin{document}
\maketitle
\newpage

\section{Úvod}
\textit{TODO}
\newpage

\section{ZISRAW (CZI) formát}

Vše co bude v této sekci uvedeno vychází z oficiální specifikace formátu CZI \cite{czi_spec}, společnosti Carl Zeiss ZEN software. 

Formát CZI je určen pro ukládání obrazů a metadat, které popisují jak samotný obraz tak i způsob získání obrazů, například v jakých podmínkách byl snímek získán. 
CZI vychází z obecnějšího formátu ZISRAW, jehož hlavním cílem je umožnit streamování velkých dat a metadat v binární podobě. Metadata jsou ukládány ve formátu XML
s kódováním UTF-8. Metadata v souberech CZI vycházejí ze specifikace OME (Open Microscopy Environment) \cite{omeweb}.

Struktůra ZISRAW/CZI formátu byla navržena tak, aby dovolovala streamování velkého množství dat, proto se ZISRAW/CZI soubory skládají ze segmentů.
Každý segment je identifikován svou hlavičkou, která obsahuje informace o jaký segment se jedná a jaká je jeho velikost. Za hlavičkou následuje část s daty. 
V souboru nalezneme speciální segmenty, které fungují jako adresáře pro segmenty s obrazy a přílohami. 
Tyto adresáře odkazují na pozice v souboru, kde se nachází požadované segmenty, což umožňuje načítání pouze těch částí, které jsou potřeba.

Obrazy se nacházejí v segmentech, označené jako \mbox{ZISRAWSUBBLOCK}. Kromě samotných pixelů zde najdeme i metadata, specifické pro daný obraz.
Specifickými metadaty mohou být např. minimální a maximální hodnoty pixelů, počet bitů na pixel a seznam dvojic klíč/hodnota, udávající libovolnou informaci o obrazu (datum pořízení, pozice mikroskopu v \SI{}{\micro\metre}).


Formát CZI dovoluje různé typy pixelu, jak pro barevné tak i černobílé obrazy, seznam všech podporovaných typů najdeme v Tabulce \ref{tab:pixelTypes}.

\begin{figure}[h!]
    \centering
    \begin{tabular}{| l | c | l |}
        \hline
        Typ                 & Byte/Pixel    &  Poznámka \\\hline
        Gray8               &     1         &  8 bit unsigned            \\\hline
        Gray16              &     2         &  16 bit unsigned   \\\hline
        Gray32Float         &     4         &  32 bit IEEE float   \\\hline
        Bgr24               &     3         &  3 $\times$ 8 bit unsigned   \\\hline
        Bgr48               &     6         &  3 $\times$ 16 bit unsigned   \\\hline
        Bgr96Float          &     12        &  3 $\times$ IEEE float   \\\hline
        Bgra32              &     4         &  4 $\times$ 8 bit unsigned   \\\hline
        Gray64ComplexFloat  &     8         &  2 $\times$ IEEE float   \\\hline
        Bgr192ComplexFloat  &     24        &  8 $\times$ IEEE float   \\\hline
        Gray32              &     4         &  32 bit signed \textit{planovaný} \\\hline
        Gray64              &     8         &  64 bit float \textit{planovaný} \\\hline
    \end{tabular}
    \caption{Tabulka podporovaných typů pixelu v CZI}
    \label{tab:pixelTypes}
\end{figure}

Informaci o typu pixelu nalezneme v metadatech, které jsou společné pro všechny obrazy nacházející se v CZI souboru. 
Mimo typ pixelu, nalezneme v těchto společných vlastnostech další zajímavé informace, některé jsou uvedeny v Tabulce \ref{tab:imageMetadata}, 
nutno podotknout, že soubor nemusí tyto informace obsahovat.

\begin{figure}[h!]
    \centering
    \begin{tabular}{| l | l |}
        \hline
        Klíč                & Význam \\\hline
        SizeX               & Šířka obrázku \\\hline
        SizeY               & Výška obrázku \\\hline
        SizeC               & Počet kanálů \\\hline
        SizeZ               & Počet řezů ve směru Z \\\hline
        SizeT               & Počet časových bodů \\\hline
        SizeH               & Počet fází \\\hline
        SizeR               & Počet různých úhlu, ze kterých byl obraz získán \\\hline
        SizeS               & Počet různých scén \\\hline
        SizeI               & Počet různých nasvícení \\\hline
        SizeM               & Počet dílů mozaiky \\\hline
        SizeB               & Počet snímání jednoho obrazu \\\hline
        SizeV               & Počet různých pohledů \\\hline
        PixelType           & Typ pixelu \\\hline
        Dimensions          & Dodatečné informace k dimenzím \\\hline
    \end{tabular}
    \caption{Základní informace o obrazech v souboru CZI}
    \label{tab:imageMetadata}
\end{figure}

Šířka, výška obrázku, počet kanálů, řezů, fází atd. to vše jsou \say{dimenze} obrázku, pro které mohou být uvedeny dodatečné informace. Taktéž, kanály se mohou lišit
typem pixelu, počtem bitů na komponentu, metodou získaní atd., proto i pro ně najdeme specifická metadata.

Data pixelu mohou být v CZI souborech jak komprimovaná tak nekomprimovaná. Specifikací jsou povolené komprese
LZW, JPEG a JPEG-XR. Všechny tyto komprese jsou specifikací omezeny na 2D obrazy. LZW je bezztrátová komprese a momentálně se nepoužívá pro
širokopásmovou mikroskopii. JPEG je ztrátová komprese a JPEG-XR je modernější variantou JPEG, která nabízí lepší kompresní poměry a také bezztrátovou kompresi.

\newpage
\section{Kompresní metody}
V této sekci si popíšeme kompresní metody, které jsme vyzkoušeli na bioinformatických datech. 
Nejprve uvedeme 3 metody, které se používají pro bezztrátovou kompresi dat všech druhů a se staly \emph{de facto} standardem. 
Následně popíšeme kompresi \bThreed, která se přímo zaměřuje na kompresi obrazů, získaných z mikroskopů. 
Také zde prozkoumáme techniku přeuspořádání dat, která by mohla vést k lepším výsledkům komprese.

Komprese budou hodnoceny pomocí kompresního poměru, který je vypočten následovně:
\begin{equation*}
    \text{kompresní poměr} = \frac{\text{velikost dat}}{\text{velikost komprimovaných dat}}
\end{equation*}
\noindent žádoucí jsou tedy hodnoty větší než $1.0$.

\subsection{Standartní metody}

Standartní metody, které zde uvedeme, jsou hojně využívány v nejrozšířeněšjších programech zabývající se bezztrátovou kompresí. Tyto metody jsou navrženy tak,
aby byly nezávislé na typy procesoru, operačním systému nebo souborovém systému. Tato nezávislost dovoluje přenesitelnost mezi různými stroji. 

Soubory jsou komprimací převáděny do jiných formátů, zaobalující komprimovaná data. Příkladem může být jeden z jednodušších formátů a to \emph{gzip} \cite{gzip},
používá se například i pro HTTP kompresi. Tento formát využívá zřejmě nejrozšířeněšjší 
metodu komprese DEFLATE \cite{deflate_spec}. DEFLATE kombinuje algoritmus LZ77 \cite{LZ77} and Huffmanovo kódování. 
DEFLATE je nejpouživanějším typem komprese v \emph{zip} souborech.

LZMA algoritmus kombinuje více druhů algoritmů, LZ77 \cite{LZ77}, aritmetické kódování a využívá Markuv model predikce. Tento algoritmus se využívá v programu
\emph{7-Zip}.

Třetí algoritmem je bzip2, stejně jako LZMA využívá více metod, Run-Length kódování, Huffmanovo kódování a Block-Sorting kompresi \cite{block_sorting}.

V následujících grafech porovnáme uvedené 3 metody. Všechny 3 algoritmy dovolují nastavit určitou úroveň komprese, obecně platí, že vetší úroveň znamená
vyšší kompresní poměr, ale také větší paměťové a časové nároky. Né vždy je tedy nejlepším řešením použít maximální úroveň, obvykle 9. 
Následující testy byly provedeny nad CZI souborem, který obsahoval 39 řezů žabronožky, řez je uložen v obrazu $1388 \times 1040$ pixelů, kde typ pixelu je Gray16,
tedy 2 byty pro každý pixel, rozmezí hodnot $0 - 65535$.

\begin{figure}[h!]
    \centering
    % \pgfplotsset{scaled x ticks=false}
        \begin{tikzpicture}
        \begin{axis}[
            width=0.8\linewidth,
            xlabel = {Úroveň komprese},
            ylabel = {Kompresní poměr},
            domain=1:9,
            legend entries = {gzip, lzma, bzip2},
            legend pos = outer north east,
            ymin=2, ymax=4,
            ]
            \addplot[red, thick] table{data/artemia_gzip_level.dat};
            \addplot[blue, thick] table{data/artemia_lzma_level.dat};
            \addplot[green, thick] table{data/artemia_bzip2_level.dat};
        \end{axis}
        \end{tikzpicture}
    \caption{Průměrný kompresní poměr pro jednotlivé úrovně}
    \label{fig:comp_level_comp}
\end{figure}

Na Obrázku \ref{fig:comp_level_comp} vidíme, že pro metody gzip a bzip2 nehraje kompresní úroveň velkou roli a naopak lzma algoritmus vydává lepší
výsledky od úrovně 5. Také vidíme, že pro kompresi daných snímků žabronožky je nejlepší metoda gzip. Uvedené kompresní poměry jsou průměrem přes
všechn 39 řezů. Na následujícím Obrázku \ref{fig:more_files_comp} si porovnáme algoritmy na více souborech, uvedené kompresní poměry jsou průměrem přes 
všechny snímky v souboru a kompresní úroveň 6.

\begin{figure}[h!]
    \centering
    \begin{tikzpicture}
        \begin{axis}[
        width=0.8\linewidth,
		height=0.55\linewidth,
        xbar,
        enlargelimits=0.25,
        ytick = data,
        xlabel={Kompresní poměr},
        legend pos = outer north east,
        symbolic y coords={{Artemia},{Artemia Flash}, {LLC Emerald}, {16 Bit Z Stack}},
        nodes near coords,
        ]
        % gzip
        \addplot coordinates {
        (2.67797,{Artemia})
        (1.84856,{Artemia Flash})
        (1.40943,{LLC Emerald})
        (1.47818,{16 Bit Z Stack})
        };
        % lzma
        \addplot coordinates {
            (3.46118,{Artemia})
            (2.3531,{Artemia Flash})
            (1.64554,{LLC Emerald})
            (1.80586,{16 Bit Z Stack})
        };
        % bzip2
        \addplot coordinates {
            (3.62971,{Artemia})
            (2.47042,{Artemia Flash})
            (1.72,{LLC Emerald})
            (1.90709,{16 Bit Z Stack})
        };
        \legend{gzip,lzma,bzip2}
        \end{axis}
    \end{tikzpicture}
    \caption{Srovnání kompresí mezi více soubory, úroveň komprese 6}
    \label{fig:more_files_comp}
\end{figure}

Pokud se podíváme na kompresi jednotlivých snímků v grafu na Obrázku \ref{fig:frame_compression}, vídíme, že hodnota poměru je různá pro každý
snímek a obě metody dosahují horších výsledků pro stejné snímky, cca. snímky 25 až 75. Toto je pravda i pro metodu lzma, ale pro přehlednost, 
jsme jí v grafu vynechali.

\begin{figure}[h!]
    \centering
        \begin{tikzpicture}
        \begin{axis}[
            width=0.8\linewidth,
            xlabel = {Snímek},
            ylabel = {Kompresní poměr},
            legend entries = {gzip, bzip2}, %lzma
            legend pos = outer north east
            ]
            \addplot[red, thick ]   table{data/llc_gzip_by_frame.dat};
            %\addplot[blue, thick] table{data/llc_lzma_by_frame.dat};
            \addplot[green, thick ]      table{data/llc_bzip_by_frame.dat};
        \end{axis}
        \end{tikzpicture}
    \caption{Komprese jednotlivých snímků}
    \label{fig:frame_compression}
\end{figure}

V Tabulce \ref{tab:compressionTable} uvadíme ještě shrnutí kompresí jednotlivých souborů, pro úroveň komprese 6.
Uvádíme zde bity na pixel, což je průměrný počet bitů potřebný k zakódování informace o jednom pixelu. Jak jsme již uvedli,
všechny tyto soubory obsahují pixely typu Gray16, takže původně bylo potřeba $16$ bitů pro uložení jednoho pixelu. Dalé zde uvádíme
rychlost, nebo také propustnost kompresní metody, tento údaj ja měřen bez jakékoliv paralelizace komprese. Z tabulky vychází jako
nejlepší metoda bzip2, která nabízí nejlepší kompresní poměry a narozdíl od metody lzma není tak pomalá.

\begin{figure}[h!]
    \centering
    \begin{tabular}{ l  l | r r  r }
        Metoda  & Soubor            & Kompresní poměr   & Bity na pixel & Rychlost [MB/s]  \\\hline\hline
        gzip    & Artemia           & 2.678             & 5.998       & 8.064       \\
                & Artemia Flash     & 1.849             & 8.657       & 8.630       \\
                & LLC Emerald       & 1.409             & 11.417      & 7.085       \\
                & 16 Bit Z Stack    & 1.478             & 10.853      & 14.170      \\\hline
        lzma    & Artemia           & 3.461             & 4.634       & 1.683       \\
                & Artemia Flash     & 2.353             & 6.802       & 0.704       \\
                & LLC Emerald       & 1.646             & 9.814       & 1.846       \\
                & 16 Bit Z Stack    & 1.806             & 8.884       & 2.149       \\\hline
        bzip2   & Artemia           & 3.630             & 4.412       & 13.491      \\
                & Artemia Flash     & 2.470             & 6.477       & 7.789       \\
                & LLC Emerald       & 1.720             & 9.383       & 12.788      \\
                & 16 Bit Z Stack    & 1.907             & 8.401       & 13.107      \\
    \end{tabular}
    \caption{Statistiky komprese}
    \label{tab:compressionTable}
\end{figure}


\subsection{Komprese obrazů z mikroskopu, knihovna \bThreed}
Tato sekce vychází z \cite{Balazs164624}, taktéž grafy jsou přebrány z této práce.
\bThreed  je Open Source knihovna, řešící problém komprese obrazů z mikroskopu. Je napsána v jazyce C++ a využívá CUDA architekturu. 
Slibovaná rychlost komprese je více než 1 GB/s. Tato knihovna nabízí jak ztrátovou tak i bezztrátovou kompresi, kde ztrátová zohledňuje fakt,
že se jedná o obrazy z mikroskopu a uživatel si může zvolit maximální chybu, kterou bude tolerovat.
Autoři knihovny definuji tzv. WNL (\emph{within noise level}) mód ztrátové komprese, kde kvantizační krok je roven šumu v obraze. 
V tomto módu je chyba, vzniklá ztrátovou kompresí, mnohem menší než šum nacházející se v obraze.
Kompresní poměry bezztrátové a WNL komprese můžeme vídět na Obrázku \ref{img:compressionComp}.

\image{0.65}{compressionComparsionBars.pdf}{img:compressionComp}{Porovnání kompresních poměrů různých vzorků}

Vliv ztrátové komprese na obraz byl testován na datasetu embrya octomilky obecné, metodou segmentačního překrývání. Byl testován komprimovaný obraz s originálním
obrazem, a hodnota 1 znamená, že se obrazy dokonale překrývají. V grafu na Obrázku \ref{img:segoverlap}, můžeme vidět, že překryv klesá až při velkých 
kompresních poměrech. Překryv pro WNL mód je téměř dokonalý 0,996.

\image{0.65}{noise_overlap.pdf}{img:segoverlap}{Vliv ztrátové komprese na kvalitu obrazu}

Použitý bezztrátový algoritmus se skládá ze dvou částí. V první části se provede predikce hodnoty pixelu vzhledem k hodnotám jeho sousedních pixelů a v 
druhé části jsou chyby predikce zakódovány pomocí RLE a Huffmana. 

Bezztrátová komprese dosáhla kompresního poměru 2,7 kdežto ztrátová WNL komprese dosahuje kompresního poměru 5. Chyba lokalizace jediné molekuly v obrazu vstoupla pouze o 4\%. (Bylo testováno na datasetu získaném pomocí Single-Molecule Localization Microscopy, rozlišení 2-25 nm).

\newpage
\subsection{Mortonovo kódování}
Mortonovo kódování, je způsob mapování multidimenzionálních dat na jednodimenzionální. Jedná se o přeuspořádání dat podle \emph{Z křivky}, která jimi
prochází. \emph{Z křivka} spadá do skupiny tzv. prostor vyplňujících křívek, které obecně prochází každým bodem prostoru v $n$-dimenzionální hyperkrychli.
Na Obrázků \ref{fig:zCurve} můžeme vidět jak probíhá mapování 2D prostoru na 1D prostor, pro každý bod roviny je vypočtena $Z$ souřadnice, 
pomocí které následně seřadíme jednotlivé body. $Z$ souřadnice je vypočtena prolnutím bitů $X$-ové a $Y$-ové souřadnice. 
V našem případě pomocí $Z$ souřadnice přeuspořádáme data obrazů.

\image{0.5}{ZCurve.pdf}{fig:zCurve}{Mortonovo kódování}

V grafu na Obrázku \ref{fig:z_order_comp}, můžeme vidět procentuální změnu kompresního poměru, vzhledem k výsledkům v grafu \ref{fig:more_files_comp}.
Naměřené výsledky jsou znovu průměrem přes všechny snímky s úrovní komprese 6.
Mortonovo kódování se nejvíce vyplatilo pro metody GZIP a LZMA, kde pozorujeme až $9\%$ nárost v kompresním poměru. Naopak pro metodu bzip2 nemělo
přeuspořádání dat smysl, neboť naměřené kompresní poměry jsou o něco horší než původní.

\begin{figure}
    \begin{tikzpicture}
        \begin{axis}[
            ybar,
            %xlabel = {},
            ylabel = {Procentuální změna kompresního poměru},
            axis line origin={0,100},
            width=0.8\linewidth,
            symbolic x coords={{Artemia},{Artemia Flash}, {LLC Emerald}, {16 Bit Z Stack}},
            legend pos = outer north east,
            x tick label style={
                rotate=90,
                anchor=east,
            },
            xtick=data,
            % nodes near coords,
            % every node near coord/.append style={rotate=90},
            ]
            % gzip
            \addplot coordinates {
            ({Artemia},105.95400)
            ({Artemia Flash},109.29308)
            ({LLC Emerald},101.46799)
            ({16 Bit Z Stack},101.15722)
            };
            % lzma
            \addplot coordinates {
                ({Artemia},103.4885)   
                ({Artemia Flash},104.98964)
                ({LLC Emerald},102.23146)
                ({16 Bit Z Stack},101.92729)
            };
            % bzip2
            \addplot coordinates {
                ({Artemia},99.84425)
                ({Artemia Flash},100.77455)
                ({LLC Emerald},99.89707)
                ({16 Bit Z Stack},98.90801)
            };
            \legend{gzip,lzma,bzip2}
        \end{axis}
    \end{tikzpicture}
    \caption{Komprese dat, přeuzpořadaných podle \emph{Z křivky}}
    \label{fig:z_order_comp}
\end{figure}

    

\bibliography{citations}
\bibliographystyle{ieeetr}

\end{document}