\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 символа <>; \item 7 символов <>. \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 не одинаковых символов: <>; \item затем записаны 3 символа <>; \item наконец записаны 6 символов <>. \end{itemize} Сжатая строка запишется в виде: \begin{center} \texttt{-9ABCABCABC3D6F} \end{center} Исходная строка состоит из 18 символов, а сжатая --- из 15. Размер данных уменьшился в $18 / 15 = 1.2$ раза. Допустим, реализация метода RLE для записи длин серий (для подсчёта количества символов) использует переменную целочисленного типа со знаком <>. В такую переменную можно записать числа от -128 до 127 включительно. Как же быть, если длина серии равна 128 символам и более? В этом случае серию разделяют на части так, чтобы длина части не превышала 127 символов. Например, серия, состоящая из 256 символов <>, будет закодирована следующей строкой $(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}