\documentclass{beamer}

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{multirow}
\graphicspath{ {./images/} }

\usetheme{Madrid}

\title{Алгоритмы сжатия изображений}
\author[А.~Ю.~Гущин \and Р.~И.~Стаин]{Андрей~Гущин \and Роман~Стаин}
\institute[СГУ]{Саратовский Государственный Университет}
\date{11 ноября 2022 г.}

\begin{document}

\maketitle

\begin{frame}{Представление цифровых изображений}
  \begin{figure}[H]
    \includegraphics[width=0.9\textwidth]{compare}
  \end{figure}
\end{frame}

\begin{frame}{Алгоритмы сжатия без потерь}
  Основными и самыми популярными алгоритмами сжатия без потерь являются:
  \begin{itemize}
    \item
      \textbf{RLE} --- используется в форматах PCX --- в качестве основного метода
      и в форматах BMP, TGA, TIFF в качестве одного из доступных.
    \item \textbf{LZW} --- используется в формате GIF
    \item \textbf{Deflate} --- используется в формате PNG
  \end{itemize}
\end{frame}

\begin{frame}{Run-Length Encoding (RLE)}
  \begin{itemize}
    \item \texttt{WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW}
    \pause
    \item \texttt{9W3B24W1B14W}
  \end{itemize}
\end{frame}
\begin{frame}{Run-Length Encoding (RLE)}
  \begin{itemize}
    \item \texttt{ABCABCABCDDDFFFFFF}
    \pause
    \item \texttt{1A1B1C1A1B1C1A1B1C3D6F}
    \pause
    \item \texttt{-9ABCABCABC3D6F}
  \end{itemize}
\end{frame}
\begin{frame}{Run-Length Encoding (RLE)}
  \begin{itemize}
    \item
      \texttt{AAAAA{\dots}AAAAA}
    \pause
    \item \texttt{127A127A2A}
  \end{itemize}
\end{frame}

\begin{frame}{Lempel-Ziv-Welch (LZW) --- Кодирование}
  \begin{table}[H]
    \centering
    \scriptsize
    \begin{tabular}{|c|c|c|r|l|}
      \hline
      % Первая строка заголовка
      \multirow{2}{*}{Символ} &
      \multirow{2}{*}{Следующий} &
      \multicolumn{2}{|c|}{Вывод} &
      \multirow{2}{*}{Расширение словаря} \\ \cline{3-4}
      % Вторая строка заголовка
      && Код & \multicolumn{1}{|c|}{Биты} & \\ \hline
      % Символ & Следующий & Код & Биты             & Расширение словаря \\
      NULL     & T         &     &                  &                    \\ \hline
      T        & O         & 20  & \texttt{10100}   & 27: TO             \\ \hline
      O        & B         & 15  & \texttt{101111}  & 28: OB             \\ \hline
      B        & E         & 2   & \texttt{100010}  & 29: BE             \\ \hline
      E        & O         & 5   & \texttt{100101}  & 30: EO             \\ \hline
      O        & R         & 15  & \texttt{101111}  & 31: OR             \\ \hline
      R        & N         & 18  & \texttt{110010}  & 32: RN             \\ \hline
      N        & O         & 14  & \texttt{1001110} & 33: NO             \\ \hline
      O        & T         & 15  & \texttt{1001111} & 34: OT             \\ \hline
      T        & T         & 20  & \texttt{1010100} & 35: TT             \\ \hline
      TO       & B         & 27  & \texttt{1011011} & 36: TOB            \\ \hline
      BE       & O         & 29  & \texttt{1011101} & 37: BEO            \\ \hline
      OR       & T         & 31  & \texttt{1011111} & 38: ORT            \\ \hline
      TOB      & E         & 36  & \texttt{1100100} & 39: TOBE           \\ \hline
      EO       & R         & 30  & \texttt{1011110} & 40: EOR            \\ \hline
      RN       & O         & 32  & \texttt{1100000} & 41: RNO            \\ \hline
      OT       & \#        & 34  & \texttt{1100010} &                    \\ \hline
               &           & 0   & \texttt{000000}  &                    \\ \hline
    \end{tabular}
  \end{table}
\end{frame}
\begin{frame}{Lempel-Ziv-Welch (LZW) --- Декодирование}
  \begin{table}[H]
    \centering
    \scriptsize
    \begin{tabular}{|r|c|c|l|l|}
      \hline
      % Первая строка заголовка
      \multicolumn{2}{|c|}{Ввод} &
      \multirow{2}{*}{Вывод} &
      \multicolumn{2}{|c|}{Новая запись} \\ \cline{1-2} \cline{4-5}
      % Вторая строка заголовка
      \multicolumn{1}{|c|}{Биты} &
      Код & &
      \multicolumn{1}{|c|}{Полная} &
      \multicolumn{1}{|c|}{Частичная} \\ \hline
      % Биты          & Код & Вывод & Полная   & Частичная \\
      \texttt{10100}  & 20  & T     &          & 27: T?    \\ \hline
      \texttt{01111}  & 15  & O     & 27: TO   & 28: O?    \\ \hline
      \texttt{00010}  & 2   & B     & 28: OB   & 29: B?    \\ \hline
      \texttt{00101}  & 5   & E     & 29: BE   & 30: E?    \\ \hline
      \texttt{01111}  & 15  & O     & 30: EO   & 31: O?    \\ \hline
      \texttt{10010}  & 18  & R     & 31: OR   & 32: R?    \\ \hline
      \texttt{001110} & 14  & N     & 32: RN   & 33: N?    \\ \hline
      \texttt{001111} & 15  & O     & 33: NO   & 34: O?    \\ \hline
      \texttt{010100} & 20  & T     & 34: OT   & 35: T?    \\ \hline
      \texttt{011011} & 27  & TO    & 35: TT   & 36: TO?   \\ \hline
      \texttt{011101} & 29  & BE    & 36: TOB  & 37: BE?   \\ \hline
      \texttt{011111} & 31  & OR    & 37: BEO  & 38: OR?   \\ \hline
      \texttt{100100} & 36  & TOB   & 38: ORT  & 39: TOB?  \\ \hline
      \texttt{011110} & 30  & EO    & 39: TOBE & 40: EO?   \\ \hline
      \texttt{100000} & 32  & RN    & 40: EOR  & 41: RN?   \\ \hline
      \texttt{100010} & 34  & OT    & 41: RNO  & 42: OT?   \\ \hline
      \texttt{000000} & 0   & \#    &          &           \\ \hline
    \end{tabular}
  \end{table}
\end{frame}

\begin{frame}{Алгоритмы сжатия с потерями}
  Наиболее часто применяемые алгоритмы сжатия с потерями:
  \begin{itemize}
    \item
      Дискретное косинусное преобразование "--- кодирование, основанное на
      преобразованиях Фурье.
    \item Вейвлет сжатие "--- сжатие за счёт отбрасывания низких амплитуд.
    \item Квантование цветов "--- процесс уменьшения количества различных цветов.
    \item
      Прореживание (субдискретизация) компонентов цветности "--- усреднение или
      уменьшение части информации о цветности изображения.
    \item
      Фрактальное сжатие "--- алгоритм сжатия изображений с потерями, основанный
      на применении систем итерируемых функций к изображениям
  \end{itemize}
\end{frame}

\begin{frame}{Преобразование цветового пространства}
  \begin{figure}[H]
    \includegraphics[width=0.9\textwidth]{YCbCr}
  \end{figure}
  \begin{align*}
    Y'  &= K_R \cdot R' + (1 - K_R - K_B) \cdot G' + K_B \cdot B' \\
    C_B &= \frac{1}{2} \cdot \frac{B' - Y'}{1 - K_B} \\
    C_R &= \frac{1}{2} \cdot \frac{R' - Y'}{1 - K_R} \\
  \end{align*}
\end{frame}

\begin{frame}{Прореживание (субдискретизация) компонентов цветности}
  Есть несколько схем прореживания, которые применяются в зависимости от
  требований к качеству изображения после его восстановления. Структура
  дискретизации сигнала обозначается как соотношение между тремя частями X:a:b
  (например, 4:2:2).

  \begin{figure}[H]
    \includegraphics[width=0.9\textwidth]{subd}
  \end{figure}
\end{frame}

\begin{frame}{Дискретное косинусное преобразование}
  \begin{minipage}[t]{0.48\linewidth}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{dct64}
    \end{figure}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \begin{align*}
      RES &= DCT \cdot IMG \cdot DCT^T \\
      DCT &=
        \sqrt{\frac{2}{N}} \cdot
        \cos{\frac{(2j + 1) \cdot i \cdot \pi}{2 \cdot N}} \\
      N &= 8, 0 \leq i, j \leq 7
    \end{align*}
  \end{minipage}
\end{frame}

\begin{frame}{Дискретное косинусное преобразование}
  До преобразования ДКП:
  \begin{equation*}
    \begin{pmatrix}
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\
      100 & 100 & 100 & 100 & 100 & 100 & 100 & 100
    \end{pmatrix}
  \end{equation*}
\end{frame}

\begin{frame}{Дискретное косинусное преобразование}
  После преобразования ДКП:
  \begin{equation*}
    \begin{pmatrix}
      800 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
        0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
    \end{pmatrix}
  \end{equation*}
\end{frame}

\begin{frame}{Квантование и кодирование}
  \begin{minipage}[t]{0.48\linewidth}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{q1}
    \end{figure}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{q2}
    \end{figure}
  \end{minipage}
\end{frame}

\begin{frame}{Фрактальное сжатие изображений}
  \begin{figure}[H]
    \includegraphics[width=\textwidth]{fractal}
  \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Внимание!}

  \begin{center}
    {\Huge Спасибо за внимание!} \\
    {\footnotesize Сжимайте осторожнее.}
  \end{center}
\end{frame}

\end{document}