poster.tex

\documentclass[10pt, sans, mathserif]{beamer}
\usepackage{graphics}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[size=custom,width=100,height=100,scale=1.2,orientation=portrait]{beamerposter}
\usepackage[absolute,overlay]{textpos}
\usepackage{multirow}
\usepackage{titlecaps}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MATH
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}

\DeclarePairedDelimiter\abs{\lvert}{\rvert}%

\newcommand{\sumsum}{
    \sum_{m = 0}^{M_s-1}\sum_{n = 0}^{N_s-1}
}
\newcommand{\sad}{
    \sumsum{\abs*{B_{s,p}(m,n) - C_{s,p,x,y}(m,n)}}
}

\newcommand{\minsad}{
    \ensuremath{\text{minSAD}}
}

\newcommand{\lowersad}{
    \text{SAD}^\Omega
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GLOSSARIES
\usepackage[acronym]{glossaries}
\loadglsentries{acronyms}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TIKZ
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{tkz-euclide}


\usetikzlibrary{positioning}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{arrows.meta}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% REFERENCES
\usepackage{cleveref}

\crefname{figure}{Fig.}{Figures}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% BEAMER SETTINGS
\setbeamersize{text margin left=18cm,text margin right=2cm}
\setbeamerfont{normal text}{size=\normalsize}
\usepackage{sourcesanspro}
%\usefonttheme[onlymath]{mathpazo}
%\usepackage{kerkis} % Or palatino or mathpazo
%\usepackage{concmath}
%\usepackage{concrete}

%\usefonttheme{structurebold}
\setbeamertemplate{caption}[numbered]

%\def\baselinestretch{1.05}


\begin{document}

\usebackgroundtemplate{\includegraphics{icip.pdf}}

\begin{frame}[t]
    \centering

    %%%%%%%%%%%%%%%%%%%% HEADER %%%%%%%%%%%%%%%%%%%%%%%%%

    \huge{Sub-Partition Reuse For Fast Optimal Motion Estimation\\ In HEVC Successive Elimination Algorithms}

    \LARGE{Luc Trudeau, Stéphane Coulombe, Christian Desrosiers}

    \Large{Department of Software and IT Engineering, École de technologie supérieure, Montréal, Canada}

    %%%%%%%%%%%%%%%%%%%%%%%%% INTRO %%%%%%%%%%%%%%%%%%%%%%%%%
    \normalsize

 \begin{columns}[t, onlytextwidth]
    \begin{column}{0.5\textwidth}
        \begin{block}{\titlecap{1. Introduction}}
        %\begin{minipage}{0.55\textwidth}
            \begin{itemize}
            % Here is a problem
            \item Motion Estimation~(ME) is a crucial tool for video encoders.
            \item ME seeks the best candidate block~($C$) from a search area~($\mathcal{S}$) in a previously coded frame to predict the current block~($B$) (see \cref{fig:MotionEstimation}).
            % It's an interesting problem
            \item For HEVC, considering every candidate is prohibitively expensive, so modern search algorithms often find sub-optimal solutions.
            \item We want to reduce the number of candidates without sacrificing the optimal solution.
            % Here is my idea
            \item We propose an early termination scheme for square \glspl{pu} based on information reuse from rectangular ones.
            \end{itemize}
        %\end{minipage}\hfill
        % \begin{minipage}{0.45\textwidth}
            \begin{figure}[H]
                \vspace{-2em}
                \centering
                \include{motionestimation}
                \vspace{-1em}
                \caption{Motion estimation finds the best candidate to predict the current block.}
                \label{fig:MotionEstimation}
            \end{figure}
        %\end{minipage}

        \end{block}

        %%%%%%%%%%%%%%%%%%%%%%%%% SEA %%%%%%%%%%%%%%%%%%%%%%%%%
            \begin{block}{\titlecap{2. Successive Elimination Algorithm}}
            \begin{itemize}
            \item Let $s \in \{\mathbb{S}, \mathbb{V}, \mathbb{H}\}$ be the partitioning shape of a \gls{pu} and $p$ be the partition index
            \begin{figure}[htb]
                \centering
                \input{figPUShapes.tex}
                \caption{The first partition index is $0$ and if a second partition exists, its index is $1$.}
                \label{fig:CUShapes}
            \end{figure}
            \item The candidate at position $(x,y)$ is evaluated using
            \[
                \text{RCSAD}(s,p,x,y) = \sad + \lambda R(x,y) \:.
            \]

            \item Successive elimination uses a lower bound approximation of the RCSAD
            \[ \small
                \text{RCADS}(s,p,x,y) = \abs*{\sumsum{B}_{s,p}(m,n) - \sumsum{C_{s,p,x,y}(m,n)}} + \lambda R(x,y)\:.
                \label{eq:RCADS}
            \]

            \item Let $(\hat{x},\hat{y})$ be the position of the current best candidate. By transitivity:
            \begin{align*}
                \text{RCADS}(s,p,x,y) &\geqslant \text{RCSAD}(s,p,\hat{x},\hat{y}) \nonumber \\
                \implies \text{RCSAD}(s,p,x,y) &\geqslant \text{RCSAD}(s,p,\hat{x},\hat{y})\:.
                \label{eq:TransitiveElimination}
            \end{align*}
            \end{itemize}
        \end{block}


    %%%%%%%%%%%%%%%%%%%%%%%%% INFORMATION REUSE BETWEEN PU SHAPES %%%%%%%%%%%%%%%%%%%%%%%%%
        \begin{block}{\titlecap{3. Information reuse between PU shapes}}
           \begin{itemize}
           \item Traditionally, \glspl{pu} are evaluated  in the order \[\mathbb{S} \rightarrow \mathbb{V} \rightarrow \mathbb{H}\:.\]
           \item Consider the following orders \[\mathbb{V} \rightarrow \mathbb{H} \rightarrow \mathbb{S} \text{ and } \mathbb{H} \rightarrow \mathbb{V} \rightarrow \mathbb{S}\:,\] which allow for information reuse from $\mathbb{V}$ and/or $\mathbb{H}$ into $\mathbb{S}$. Such as
        \begin{equation}
            \lowersad =
            \max \begin{pmatrix}
                 \minsad(\mathbb{V},0) &+ \minsad(\mathbb{V},1), \nonumber \\
                 \minsad(\mathbb{H},0) &+ \minsad(\mathbb{H},1)
            \end{pmatrix}.
        \end{equation}
        \item It follows that
        \[
            \lowersad \leqslant \text{SAD}(\mathbb{S},0,x,y),~\forall~ (x,y) \in  \mathcal{S}_{\mathbb{S},0} \:.
        \]
                \item At worst, the min SAD of a partitioning is the min SAD of the block
        \begin{equation*} \text{SAD} \left(\: \tikz[scale=0.70,baseline=-0.25cm,very thick]{\draw (-2,-2) rectangle (2,2); \draw (0,-2) -- (0,2); \draw[->] (-1, 0) -- (-0.5, 0.5); \draw[->] (1, 0) -- (0.5, -0.5);
        }\:\right) \leqslant \text{SAD} \left(\: \tikz[scale=0.70,baseline=-0.25cm,very thick]{\draw (-2,-2) rectangle (2,2);  \draw[->] (0, 0) -- (0.5, -0.5); }\:\right)\:.
        \end{equation*}
        \end{itemize}
        \end{block}


                \begin{block}{\titlecap{4. Improved early termination for $\mathbb{S}$}}
            \begin{itemize}
                \item We evaluate candidates in increasing order of rate. When the rate is large the search can terminate (without evaluating the remainder of $\mathcal{S}$).
                \item Early termination rate proposed at ICIP 2014
                \[
                    R(x,y) \geqslant \frac{\text{SAD}(s,p,\hat{x},\hat{y})}{\lambda} + R(\hat{x},\hat{y}) \:.
                    \label{eq:Thres}
                \]
                \item Improved early termination rate for $\mathbb{S}$
                \[
                    R(x,y) \geqslant \frac{\text{SAD}(\mathbb{S},0,\hat{x},\hat{y}) - \lowersad}{\lambda} + R(\hat{x},\hat{y}) \:.
                    \label{eq:SThres}
                \]
            \end{itemize}
        \end{block}

    \end{column}
    \begin{column}{0.5\textwidth}

%%%%%%%%%%%%%%%%%%%%%%%%% EARLY TERMINATION %%%%%%%%%%%%%%%%%%%%%%%%%

        \begin{block}{}
        \begin{figure}
                \centering
                \vspace{-1em}
                \begin{tikzpicture}[scale=1.3]
                \tikzstyle{every node}=[font=\small]

                \draw[gray] (0,0) grid (20,16);
                \draw[line width=.5mm] (0,15) -- node[above] {$\lambda$} (15,0);

                \draw[decoration={markings,mark=at position 1 with
    {\arrow[scale=4,>=stealth]{>}}},postaction={decorate}, line width=.75mm] (0,0) -- (0,16) node[above] {Distortion};
                \draw[decoration={markings,mark=at position 1 with
    {\arrow[scale=4,>=stealth]{>}}},postaction={decorate}, line width=.75mm] (0,0) -- (20,0) node[right] {Rate};

                %\fill[yellow, fill opacity=0.4] (8,0) -- (8,7)  -- (15,0);
                \draw[loosely dashed, line width=1mm, blue, very thick] (8,7) -- (8,0);
                \draw[line width=1mm, red, very thick] (20,7) -- (0,7);

                \draw[loosely dashed, line width=1mm] (3,12) -- (0,12) node[left] {};
                \draw[loosely dashed, line width=1mm] (3,12) -- (3,0);
                \draw[|<->|, line width=1mm] (0,-0.75) -- node[fill=white] {$R(\hat{x},\hat{y})$} (3,-0.75);
                \draw[|<->|, line width=1mm] (0,-2) -- node[fill=white] {$\frac{\text{SAD}(\mathbb{S},0,\hat{x},\hat{y}) - \lowersad}{\lambda} + R(\hat{x},\hat{y})$} (8,-2);
                \draw[|<->|, line width=1mm] (0,-3) -- node[fill=white] {$\frac{\text{SAD}(\mathbb{S},0,\hat{x},\hat{y})}{\lambda} + R(\hat{x},\hat{y})$} (15,-3);

                \draw[|<->|, line width=1mm] (-1,0) -- node[fill=white, rotate=90] {$\lowersad$} (-1,7);
                \draw[|<->|, line width=1mm] (-2,0) -- node[fill=white, rotate=90] {$\text{SAD}(\mathbb{S},0,\hat{x},\hat{y})$} (-2,12);
                \draw[|<->|, line width=1mm] (-3,0) -- node[fill=white, rotate=90] {$\text{SAD}(\mathbb{S},0,\hat{x}, \hat{y}) + \lambda R(\hat{x}, \hat{y})$} (-3,15);

                \draw[->, line width=1mm, blue] (10, 11) node[above, align=center] {\textbf{Proposed Early Termination Threshold}} to[out=270,in=45] (8,7.1);
                \draw[->, line width=1mm, text width=6cm] (14, 4) node[above, align=center] {Previous Early Termination Threshold} to[out=270,in=45] (15,0.1);

                \draw[->, line width=1mm, text width=6cm] (19, 4) node[above] {Edge of the search area} to[out=270,in=90] (19,0.1);

                \draw[->, line width=1mm, text width=8cm, red] (14, 9) node[above, align=center] {\textbf{New: No candidates below this line}} to[out=270,in=90] (14,7.1);


                \fill[yellow, fill opacity=0.2] (0,16) -- (0,15) -- (8,7) -- (19,7) -- (19,16);
                \node[text width=15cm, orange] at (14, 15) {Candidates are only in this region};

                \end{tikzpicture}
                \vspace{-0.5em}
                \caption{Geometric representation of the early termination thresholds.}
                \label{fig:Triangle}
                \end{figure}
        \end{block}


                    %%%%%%%%%%%%%%%%%%%%%%%%% EXPERIMENTAL RESULTS %%%%%%%%%%%%%%%%%%%%%%%%%
        \begin{block}{\titlecap{5. Experimental Results}}
            \input{table.tex}
            \begin{figure}[htb]
                \centering
                \input{figBarChart-Poster.tex}
                \vspace{-0.5em}
                \caption{Results for main profile with 8-bit coding and Low Delay P settings (No AMP)}
                \label{fig:SADSavingBar}
            \end{figure}
        \end{block}

                %%%%%%%%%%%%%%%%%%%%%%%%% CONCLUSION %%%%%%%%%%%%%%%%%%%%%%%%%
        \begin{block}{\titlecap{6. Conclusion}}
        \begin{itemize}
            \item The proposed early termination scheme for square \glspl{pu}, based on information reuse from rectangular \glspl{pu}, results in a \textbf{6.13x} speedup and \textbf{94.9\%} SAD savings when compared to HM (Full Search).
            \item This work considerably decreases the number of candidates imposed by the HEVC standard in order to find the optimal solution.
        \end{itemize}
        \end{block}

    \end{column}
\end{columns}
\end{frame}
\end{document}