path: root/compression/report/report.tex

\documentclass[a4paper,14pt]{extarticle}

\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage[
  left=2.5cm, right=1.5cm,
  top=1.5cm, bottom=2cm,
]{geometry}
\usepackage{amsmath}
\usepackage{indentfirst}
\usepackage{underscore}
\usepackage{multirow}
\usepackage{float}
\usepackage{setspace}
\singlespacing
\usepackage{graphicx}
\graphicspath{{./images/}}

\setcounter{tocdepth}{3}

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

\begin{document}

\maketitle
\tableofcontents

\section{Представление цифровых изображений}

Для представления изображений в памяти компьютера используется два подхода:
\begin{itemize}
  \item растровое представление,
  \item векторное представление.
\end{itemize}

Ввиду того, что векторные изображения получаются путём математического описания
элементарных геометрических объектов, обычно называемых \emph{примитивами}
(линии, точки, геометрические фигуры), они занимают крайне малое количество
памяти компьютера и поэтому к ним обычно не применяют алгоритмы сжатия.

В отличие от них, растровые изображения хранятся в виде двумерного массива
чисел, где каждому значению соответствует цветовое значение пикселя. Для
уменьшения размера растрового изображения, помимо сжатия, также используют
уменьшение значения \emph{глубины цвета} (количества допустимых цветов), либо
уменьшения размера изображения в пикселях (масштабирование).

Но так как уменьшение размера изображения, или уменьшение глубины цвета могут
значительно изменить или ухудшить качество исходного изображения, обычно
применяются специализированные алгоритмы сжатия изображений: с потерями и без
потерь. Хотя сжатие с потерями также ухудшает качество изображения, зачастую
на практике изменения не настолько заметны, как в случае с изменением глубины
цвета.

\section{Алгоритмы сжатия изображений без потерь}

Сжатие без потерь часто предпочтительней для искусственно построенных
изображений, таких как графики, иконки программ, либо для специальных случаев,
например, если изображения предназначены для последующей обработки алгоритмами
распознавания изображений.

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

\subsection{Сжатие по стандарту RLE}

Рассмотрим изображение, содержащее текст чёрного цвета на сплошном белом фоне.
При построчном чтении пикселей такого изображения будут встречаться серии белых
(фон) и чёрных (буквы) пикселей. Буквой B обозначим чёрный пиксель, а буквой W
--- белый. Рассмотрим некую произвольную строку изображения длиной 51 символ:
\begin{center}
  \texttt{WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW}
\end{center}

Посчитаем количество символов:
\begin{enumerate}
  \item 4 символа <<B>>;
  \item 7 символов <<W>>.
\end{enumerate}

Итого найдено 5 серий. Заменим серии на число повторов и сам повторяющийся
символ:
\begin{center}
  \texttt{9W3B24W1B14W}
\end{center}

Получилась последовательность из 12 символов. Исходная последовательность
состояла из 51 символа. Данные были сжаты в $51 / 12 \approx 4.25$ раза.

Возьмём строку, состоящую из большого количества неповторяющихся символов:
\begin{center}
  \texttt{ABCABCABCDDDFFFFFF}
\end{center}

После сжатия методом RLE такая строка будет выглядеть так:
\begin{center}
  \texttt{1A1B1C1A1B1C1A1B1C3D6F}
\end{center}

Исходная строка состоит из 18 символов, а сжатая --- из 22. Размер данных
увеличился в $22 / 18 \approx 1.22$ раза.

Чтобы после сжатия размер данных не увеличивался, алфавит, в котором записаны
длины серий, делят на две части (обычно равные). Например, алфавит целых чисел
можно разделить на две части: положительные и отрицательные числа. Положительные
числа используют для записи количества повторов одного символа, а отрицательные
--- для записи количества неодинаковых символов, следующих друг за другом.

Посчитаем символы с учётом вышесказанного:
\begin{itemize}
  \item сначала друг за другом следуют 9 не одинаковых символов: <<ABCABCABC>>;
  \item затем записаны 3 символа <<D>>;
  \item наконец записаны 6 символов <<F>>.
\end{itemize}

Сжатая строка запишется в виде:
\begin{center}
  \texttt{-9ABCABCABC3D6F}
\end{center}

Исходная строка состоит из 18 символов, а сжатая --- из 15. Размер данных
уменьшился в $18 / 15 = 1.2$ раза.

Допустим, реализация метода RLE для записи длин серий (для подсчёта количества
символов) использует переменную целочисленного типа со знаком <<signed char>>.
В такую переменную можно записать числа от -128 до 127 включительно. Как
же быть, если длина серии равна 128 символам и более? В этом случае серию
разделяют на части так, чтобы длина части не превышала 127 символов. Например,
серия, состоящая из 256 символов <<A>>, будет закодирована следующей строкой
$(256=127+127+2)$:
\begin{center}
  \texttt{127A127A2A}
\end{center}

Запись на некотором языке программирования алгоритма RLE с учётом этих
ограничений нетривиальна.

Конечно, кодирование, которое используется для хранения изображений, оперирует с
двоичными данными, а не с символами ASCII, как в рассмотренных примерах, однако
принцип остаётся тем же.

\subsection{Сжатие по стандарту LZW}

Данный алгоритм при кодировании (сжатии) сообщения динамически создаёт словарь
фраз: определённым последовательностям символов (фразам) ставятся в соответствие
группы битов (коды) фиксированной длины. Словарь инициализируется всеми
1-символьными фразами (в случае 8-битных символов --- это 256 фраз). По мере
кодирования алгоритм просматривает текст символ за символом слева направо.
При чтении алгоритмом очередного символа в данной позиции находится строка W
максимальной длины, совпадающая с какой-то фразой из словаря. Затем код этой
фразы подаётся на выход, а строка WK, где K --- это символ, следующий за W во
входном сообщении, вносится в словарь в качестве новой фразы и ей присваивается
какой-то код (так как W выбрана жадно, WK ещё не содержится в словаре). Символ K
используется в качестве начала следующей фразы. Более формально данный алгоритм
можно описать следующей последовательностью шагов:
\begin{enumerate}
  \item
    Инициализация словаря всеми возможными односимвольными фразами.
    Инициализация входной фразы W первым символом сообщения.
  \item
    Если сообщение закончилось (символ \#), то выдать код для W и завершить
    алгоритм.
  \item Считать очередной символ K из кодируемого сообщения.
  \item
    Если фраза WK уже есть в словаре, то присвоить входной фразе W значение WK и
    перейти к Шагу 2.
  \item
    Иначе выдать код W, добавить WK в словарь, присвоить входной фразе W
    значение K и перейти к Шагу 2.
\end{enumerate}

Алгоритму декодирования на входе требуется только закодированный текст:
соответствующий словарь фраз легко воссоздаётся посредством имитации работы
алгоритма кодирования.

\subsubsection{Пример кодирования}

\begin{table}[H]
  \centering
  \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}

\subsubsection{Пример декодирования}

\begin{table}[H]
  \centering
  \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}


\section{Алгоритмы сжатия с потерями}
Алгоритмы сжатия с потерями могут применяться в тех случаях, когда необходимо
сжать естественное изображение (например, фотографию) в приложениях, где
незначительная потеря качества позволяет существенно увеличить скорость передачи изображения.

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

Некоторые из этих алгоритмов применяются в алгоритмах сжатия \textbf{JPEG},
JPEG2000.

\subsection{Сжатие по стандарту JPEG}

\subsubsection{Преобразование цветового пространства}
При сжатии изображение преобразуется из цветового пространства RGB в
\textbf{YCbCr}. Сжатие с потерями использует принцип отделения важной информации
от неважной. Для человеческого глаза изменение яркости заметно сильнее, чем
изменение цвета, поэтому и используется данное цветовое пространство.

Y' "--- компонента яркости, Cb и Cr являются синей и красной цветоразностными
компонентами.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.999\textwidth]{YCbCr.jpg}
    \caption{Цветное изображение и его компоненты Y, Cb и Cr}
\end{figure}

Хорошо видно, что на карте яркости намного больше деталей.

Сигналы Y'CbCr (до нормирования и смещения для перевода сигналов в цифровую
форму) формируются с применением гамма-коррекции из соответствующих RGB
источников следующим образом:
\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*}
где $K_B$ и $K_R$ коэффициенты, которые обычно выводятся из определения
соответствующего пространства RGB.

Здесь апостроф ' означает компоненты с гамма-коррекцией, поэтому $R'$, $G'$
и $B'$ располагаются в пределах от 0 до 1, где 0 соответствует минимальной
интенсивности (например, для отображения чёрного цвета) и 1 соответствует
максимуму (например, для отображения белого цвета). Результирующее значение
яркости (Y) будет иметь пределы от 0 до 1, а значения цветности (Cb и Cr) будут
расположены в пределах от -0.5 до +0.5.

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

\begin{enumerate}
    \item
      Тип 4:4:4 (отсутствие субдискретизации) "--- каждому пикселю в каждой
      строке соответствует собственное уникальное значение компонентов Y, Cb и
      Cr.
    \item
      Тип 4:2:2 "--- объединение по компонентам цветности происходит по
      горизонтали в группах по два пикселя.
    \item
      Тип 4:2:0 "--- изображение разбивается на квадраты $2 \times 2$ пикселей и
      в каждом из них все пиксели получают одинаковые значения Cb и Cr.
    \item
      Тип 4:1:1 "--- объединение по компонентам цветности происходит по
      горизонтали в группах по 4 пикселя.
\end{enumerate}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.999\textwidth]{subd.png}
    \caption{Примеры субдискретизации}
\end{figure}


\subsubsection{Дискретное косинусное преобразование}
Далее яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr разбиваются
на блоки $8 \times 8$ пикселей. Каждый такой блок подвергается дискретному
косинусному преобразованию (ДКП, DCT). Его суть заключается в разложении по
спектру пространственных волн. Или другими словами, есть 64 изображения,
совмещая которые можно получить любое другое изображение.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{dct64.png}
    \caption{}
\end{figure}

Обозначим такие блоки через $IMG$. Тогда ДКП осуществляется по формуле:
\[ RES = DCT \cdot IMG \cdot DCT^T, \]
где $DCT = \displaystyle \sqrt{\frac{2}{N}} \cdot \cos{\frac{(2j + 1) \cdot i \cdot \pi}{2 \cdot N}}$,
$N = 8, 0 \leq i, j \leq 7$.

Например, если взять матрицу, состоящую из одинаковых значений, то можно
увидеть, что в левом верхнем углу получившейся матрицы сохраняется большое
значение.

До преобразования ДКП:
\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*}

После преобразования ДКП:
\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*}

\subsubsection{Квантование и кодирование}
Далее матрица коэффициентов делится на матрицу квантования, которая зависит от
настроек сжатия. Например, если требуется сохранить 100\% качество, то каждый
коэффициент делится на 1 (то есть остается таким же). Если сохранение проходит
с меньшим качеством, то каждый коэффициент делится на определенное число (в
зависимости от выбранного качества).

Затем производится округление поделённых коэффициентов до целого значения. И при
сильном сжатии многие из них округляются до нуля.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.45\textwidth]{q1.png}
    \caption{Примеры матрицы полученной после квантования}
\end{figure}

Затем матрица коэффициентов выписывается <<зиг-загом>>:

\begin{figure}[H]
    \centering
    \includegraphics[width=0.45\textwidth]{q2.png}
    \caption{}
\end{figure}

Получается последовательность чисел, в конце которой зачастую одни нули: 239,
32, 34, -70, -3, 27, -12, -19, 2, 5, -17, 0, 8, 6, 3, -5, 3, 23, -6, -3, 0, -3,
4, 6, 11, 9, 0, 3, 0, 0, 6, 0, 6, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.

Затем эта последовательность пакуется так, что указывается число нулей, идущих
подряд (алгоритм кодирования длины серии): 239, 32, 34, -70, -3, 27, -12, -19,
2, 5, -17, (0, 1), 8, 6, 3, -5, 3, 23, -6, -3, (0, 1), -3, 4, 6, 11, 9, (0, 1),
3, (0, 2) 6, (0, 1), 6, (0, 6), 3, (0, 24).

Затем коэффициенты кодируются с помощью алгоритма кодирования Хаффмана, чтобы
получить окончательное изображение.


\subsection{Фрактальное сжатие изображений}

Библиотека под названием Fiasco была создана Ульрихом Хафнером. В 2001 году
о ней написали в Linux Journal. Согласно руководству 2000-04, Fiasco можно
использовать для сжатия видео. Также библиотека Netpbm включает в себя Фиаско.

Электронная энциклопедия Microsoft Encarta использует разновидность фрактального
сжатия. Эта энциклопедия выпускалась на компакт-дисках объёмом 650МБ. На диск
записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых
карт, а также 7000 качественных фотографий.

\end{document}