From 7ac882e3a313d59b4a5478e1e0f0583f8ca473bd Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sat, 24 Dec 2022 23:20:10 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=20=D0=BB=D0=B5=D0=BA=D1=86=D0=B8=D1=8F=20=D0=BF=D0=BE=20=D1=81?=
 =?UTF-8?q?=D0=B6=D0=B0=D1=82=D0=B8=D1=8E?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 compression/report/report.tex | 443 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 443 insertions(+)
 create mode 100644 compression/report/report.tex

(limited to 'compression/report/report.tex')

diff --git a/compression/report/report.tex b/compression/report/report.tex
new file mode 100644
index 0000000..a780d15
--- /dev/null
+++ b/compression/report/report.tex
@@ -0,0 +1,443 @@
+\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}
-- 
cgit v1.2.3

