exam/Глава 2. Виды данных, их кодирование, команды.md at feat/tickets/09

CompArch2024/exam

Fork 0

Files

ElectronixTM a2dc72a3f4 useless: почему-то гит видит тут изменения

2024-11-10 00:50:57 +03:00

36 KiB

Raw Permalink Blame History

tags, source

2.5. Графические данные, их представление и кодирование

Классы изображений

Кодирование цвета

Способы и точность кодирования цвета для отображения

Форматы для хранения графических данных

Краткая характеристика наиболее распространенных растровых форматов

Всякие там алгоритмы сжатия

Алгоритмы сжатия без потерь

Неплохое видео: https://www.youtube.com/watch?v=CJFUN6BrkGE

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

Групповое кодирование RLE

Вместо того, чтобы писать последовательно много раз одинаковое значение, записывается сначала количество повторений байта, а затем сам байт

То есть если у нас есть последовательность 111112222222227, то мы как бы говорим: "запиши 5 раз 1, потом 9 раз 2, потом 1 раз 7". То есть запишется оно как: "[5]1[9]2[1]7" и если исходное сообщение занимало у нас 15 байт, то новое 6 байт.

Основная проблема данного алгоритма в том, что число повторений тоже надо хранить и остается хранить их только в сжатом тексте, так что если повторяющихся данных не так много, то алгоритм становится даже вреден. Например: 112431 превратится в [2]1[1]2[1]4[1]3[1]1, и того 10 байт против исходных 6. То есть размер даже увеличился

То есть алгоритм отлично себя показывает на изображениях, где много областей сплошной одноцветной заливки (как например схема самого алгоритм, приведенная выше)

Кодирование по Хаффману (Huffman, 1952)

Много поработав с естественным языком, мы довольно быстро заметим, что определенные буквы в нем встречаются чаще чем другие. Частотностью символа называется количество этого символа в тексте, к количеству символов в тексте. Проще говоря какой процент всех символов составляет например буква "а"

Эта особенность языка испокон веков использовалась для взлома простого шифра подстановки ¹, а потому частотность символов была многократно посчитана для почти всех языков, которые имеют письменность. Вот например частотность символов русского языка:

Видно, что буква "о" упоминается существенно чаще, чем буквы вроде "ф" или многострадальной "ё", (к которой у русских большая нелюбовь из-за неудобства ее печатного набора).

Эта особенность, которая несколько веков портила жизнь людям и не давала зашифровать сообщение, но ее можно обернуть и себе на пользу: при шифровании текста логично использовать для шифрования буквы "о" символ с наименьшей длинной, чуть длиннее сделать "е", еще чуть длиннее "а" и так далее вплоть до "ё", которую зашифруем уже как получится.

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

После этого мы алгоритмически реализуем подбор таких символов.

У этого метода есть одна проблема технического характера: частотности символов для языка в целом и для конкретного файла в частности могут весьма сильно различаться, а мы ведь этот алгоритм не только к текстам хотим применять (У нас-то в голове все с байтами работает). Построить таблицу частотностей для конкретного файла - пол беды, это займет O(n), что вполне допустима даже для гигабайтных данных. А вот как ее при разжимании получить? В классической реализации алгоритма Хаффмана она хранится в начале файла, но она, как вы можете догадаться, сама прибавляет размера нашим данным.

У этой проблемы есть решение - на практике мы можем не генерировать таблицу частотностей, а производить кодирование и построение дерева кодирования символов параллельно. Алгоритм Молодяковым не описан, просто знайте что он есть. Если кому интересно, он разбирался в этом видео (или если ютуб не грузит: https://vk.com/video-209186427_456239058 на 9:41). Этот алгоритм называется "адаптивный метод Хаффмана"

Алгоритм LZW (Lempel-Ziv-Welch - 1984)

Весьма сложный для понимания на слух. Алгоритм существует в двух вариантах LZW и LZW78

Идея: до этого мы кодировали текст уменьшая длинну символов, теперь мы кодируем текст при помощи частей этого самого текста. То есть в слове abracadabra есть 2 абсолютно идентичных набора символов. Хотелось бы это как-то учитывать при кодировании

Держим в уме, что текст тут только для примера и действительности мы всегда работаем с последовательностями байт

LZW исходный

[!note]+ Скользящее окно Некий кусок непрерывной памяти из двух частей - словаря, и буффера. Изначально кодируемый текст, насколько помещается, заносится в буффер (представьте буффер справа), а в процессе кодирования вся эта область памяти сдвигается влево (обычным сдвигом << 8)

Идея: кодируемый текст мы помещаем в буффер и в процессе обработки смещаем его в словарь, а внутри словаря потом в процессе кодирования ищем совпадения. Если совпадение нашлось, мы просто указываем в словаре где это совпадение можно отыскать

Реализация (в общих чертах): загоняем весь текст в буффер, после чего начинаем искать сопадение для первого символа в словаре (в самом начале кодирования совпадений не будет). Пока совпадений нет, сдвигаем всю цепочку на 1 влево, если есть еще символы, которых нет в буффере, попутно доставляем их туда (сдвинулись на 1 влево, в буффере освободилось место под один символ, дописываем в это место следующий в файле символ). Словарь и буффер - одна область памяти, называемая скользящим окном (см примечание выше), поэтому при сдвиге влево на один символ, самый левый символ из буффера появится в словаре, вытеснив самый старый символ уже словаря. Вытесненный символ нигде не хранится и просто исчезает из оперативной памяти. Как только есть совпадение на 1 символ, пытаемся найти совпадения на 2 символа, потом на 3 и так далее. То есть пытаемся найти как можно более длинное совпадение с содержимым словаря. Отмечу, что совпадения мы ищем даже тогда, когда словарь пуст. Если такое есть - даем на него ссылку в закодированном сообщении словаре (в классической реализации - смещение от конца влево и длину совпавшего куска)

Проблема: Если сначала мы ищем совпадение в один символ, потом в 2 символа, потом в 3 и так далее, то оценка сложности покажет сложность алгоритма по времени O(n!). Не очень хорошо. Чем больше будет размер скользящего окна, тем больше потенциальных длинных цепочек мы сможем найти и тем сильнее, соответственно, сжать данные, но тем дольше будет процесс кодирования

LZW78

Модифицированная версия, также и проще для понимания

У нас есть кодируемый текст и словарь. Поскольку примером данных будет текст, словарь у нас будет представлять обычный массив строк (только придется договориться, что нумерация в нем начинается с единицы а не с нуля).

Идея: мы кодируем текст и попутно составляем словарь. Мы ищем повторяющиеся последовательности символов длиной начиная от нуля и доскольки угодно. Если некоторой последовательности еще нет в словаре, мы ее туда заносим, если есть, мы в выходных данных даем номер совпавшей последовательности

[!note]+ Примечание Искать последовательности мы начинаем с длины 1, что означает, что при кодировании в словарь сначала добавится вхождение в 1 символ. Потом если с этим вхождением в 1 символ случится совпадение, в словарь будет добавлено совпадение уже из двух символов, а если будет совпадение с последовательностью из двух символов, будет добавлена новая последовательность из 3 символов.

Каждая новая добавленная последовательность создается из совпавшей последовательности + одна буква справа от нее. То есть если "abba" уже есть в словаре, а совпадение случилось в состоянии буфера "abbahelloworld", то следующей в словарь добавится последовательность "abbah", потому что слева стояла буква "h"

Реализация: теперь вместо символа или последовательности символов мы пишем номер, под которым соответствующая последовательность хранится в словаре (напоминаю, что нумеруем элементы массива в этом примере мы с единицы), после чего добавляем следующий за этой последовательностью символ. Если символ в словаре не найден, пишем в качестве числа 0. {'a', 'b', 'r'}), а вот потом встретится "a", которая есть в словаре, поэтому мы напишем ее порядковый номер, а затем следующий за совпавшей последовательностью символ: 1c (словарь: {'a', 'b', 'r', 'ac'}), потом в ход пойдет "ad", который закодируется соответственно в 1d и так далее после кодирования получим следующий результат: 0a0b0r1c1d1b3a (словарь: {'a', 'b', 'r', 'ac', 'ad', 'ab', 'ra'}) (заметим, что в данном случае мы ничего не сжали. Это нормально, потому что данные коротковаты, а алгоритмы сжатия дописывают довольно много информации. Порой сжатие не эффективно, тут ничего не поделать)

Проблемы: пусть здесь мы и поправили скорость сжатия (теперь на поиск совпадений уходит O(n)), а также мы убрали ограничения на размер скользящего окна и теоретически можем искать совпадения большой длины, можно увидеть, что в этом варианте алгоритма мы не заметили, что "abra" встречается 2 раза без изменений. То есть чтобы алгоритм был эффективен, желательно данные иметь побольше. Также не трудно понять, что если длинных цепочек повторяющихся данных у нас нет, то сжатие пойдет во вред размеру файла и это надо учитывать, поэтому если в файле нечему повторяться, то этот алгоритм не только не эффективен, но подчас и вреден, как мы могли убедиться

Алгоритмы сжатия с потерями

Когда мы говорим о сжатии какого-нибудь текстового документа, потери данных оче ид о н прив дут ни к ч му хор шему, как можете видеть, читать такое не то чтобы очень приятно. Но вот если дело касается изображений - другой разговор. Наш глаз, вообще говоря, штука крайне не точная и вполне может не заметить каких-то деталей. Так что для фото и видео сжатия с потерями - отличный выход (потому что весят эти картиночки они будь здоров)

JPEG

JPEG - формат хранения изображения с потерями. Само по себе его обоснование довольно сложно и требует некоторых знаний в области математики. Тем не менее основывается он на некоторых вполне понятных идеях:

Если мы сжимаем фотографию или художественное полотно, то как правило 2 соседних пикселя будут близки по цвету
Человеческий глаз построен таким образом, что он гораздо восприимчивее к перепадам яркости, чем к изменению цвета (кому интересно, это связано с тем, что в нашей сетчатке глаза больше палочек чем колбочек). То есть человеческий глаз намного чувствительнее к изменению яркости нежели к изменению цвета

Процесс сжатия в этом формате довольно длинный. Подробно все шаги пояснять не буду, потому что это ну прям совсем хана

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

Тогда же были получены формулы перевода из RGB в другой формат - цветоразностное кодирование^[Далее в эфир 3 полученных числа кодировались по 3 раздельным каналам. ЧБ телевизоры воспринимали только один - Y, а цветные - все 3 канала] (яркость, коэф синего, коэф красного). Y - яркость: Y = 0.299R + 0587G + 0.144B. Cb - коэффициент синего: Cb= 0.1687R -0.3313G +0.500B. И Cr - коэффициент красного: Cr= 0.500R -0.4187G +0.0813B. Теперь именно при помощи этих чисел мы будем записывать все пиксели исходного изображения
На втором шаге мы уже сделаем сжатие - отбросим часть цветовых данных, но сохраним яркость. Глаз не очень чувствителен к такому изменению

Для этого изменим немного кодирование данных: возьмем квадрат 2х2 пикселя и будем считать, что он весь закрашен одним цветом, но при этом сохраним все значения яркостей. То есть вместо кодирования всех трех компонент для каждого отдельного пикселя, для каждого пикселя мы кодируем только яркость, а цвет кодируем для всего квадрата сразу. Таким образом из 12 значений (по 3 компоненты на каждый пиксель) мы получаем всего 6 (4 значения на яркости отдельных пикселей и 2 значения на цвет квадрата). Уже на этом этапе мы уменьшили размер изображения в 2 раза, а качество для нашего глаза еще не пострадало
Следующий шаг самый сложный как для реализации, так и для понимания. Упирается он в следующее размышление - у нас может быть разная детализация изображения. В какой-то области находится много мелких деталей, а в какой-то меньше. Это очень легко увидеть на картинах художников. Наша задача определить места, где мало деталей и закодировать их меньшим количеством информации. Наша задача понять, что же с технической точки зрения означает "количество деталей"

Размышления над этим привели к страшной математике: дискретному косинусному преобразованию. Про его устройство Молодяков не пишет и надеюсь не спрашивает.

Изображение разбивается на блоки 8х8^[Сейчас размеры блока яркости удваиваются и яркость кодируется блоками по 16 на 16]. Внутри этих блоков мы берем отдельно 3 компоненты (те самые яркость и 2 цвета) и отдельно над каждой проводим одни и те же манипуляции: берем их значения и из интервала 0-255 переводим в -128 -127. Было доказано, что любые значения в получившейся матрице можно получить сложением 64-х отдельных элементарных (и не очень) матриц. Все они получены были косинусным преобразованием и выглядят так:

!

Дальше идет не очень понятный мне этап преобразования исходной матрицы 8 на 8 к матрице по примерно следующей формуле:
```
G_{ij} = \frac{1}{4} C_{i}C_{j}\sum_{x=0}^{7} \sum_{x=1}^{7} p_{xy}\cos\left( \frac{(2y+1)j\pi}{16} \right)\cos\left( \frac{(2x+1)i\pi}{16} \right)
```
Тут боюсь я и сам не в курсе, откуда она взялась.

В общем на выходе получается примерно следующая матрица

!

Для нас самое важное сейчас то, что чем ближе к правому нижнему углу, тем числа ниже. При этом эта матрица кодирует "значимость элементов для нашего глаза"^[Не спрашивайте как до этого додумались. Разработка формата по некоторым источникам велась 6 лет. Я не смогу ужать 6 лет страданий ученых в 3 абзаца] %%Может быть дополню когда-нибудь маленькой заметкой откуда взялось уравнение и в чем его основная идея. По крайней мере полезно будет для моего ящика для заметок%%.
Далее из-за пазухи достаем уже заранее за нас составленную матрицу квантования и делим попарно элементы матрицы после преобразования на матрицу квантования^[Замечу, что для яркости одна матрица кватнования, а для цвета другая. Все матрицы квантования подбирались опытным путем (и существенное время). Отрегулировать степень сжатия можно умножением этих матриц на константу] и округляем значения

!

После этого процесса получилось очень много ноликов - этого мы и добивались - выжили только существенные детали, а остальные съело делением. Вот эту-то матрицу мы и будем хранить.

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

Поэтому решили записывать числа зигзагом по этому направлению:

!
После того, как мы писали этот ужас мы сжимаем его страшной помесью Хаффмана и RLE. Описывать я это дело пожалуй не буду, просто скажу, что таблицы для алгоритма Хаффмана построены заранее.

В целом этот алгоритм позволяет сжимать изображения в десятки раз. (вплоть до 50-кратного уменьшения размера)

Повторим еще раз идейно наши шаги:

graph TD;
	convert(Перекодировать цвета, чтобы появился явный параметр яркости)-->resize(Выкинуть часть информации о цвете, которую глаз не заметит);
	resize-->split(разбить изображения по каналам, а содержимое каналов поделить на группы по 8х8 для цветов и по 16х16 для яркости);
	split-->DCT(Выявить какие узоры из числа заранее известных 64-х в каких пропорциях присутствуют в группах);
	DCT-->clean(выкинуть все несущественные узоры);
	clean-->compress(Оставшиеся коэффициенты матрицы компактно упаковать);
	compress-->Готово!;

MPEG

Сжимаем видео

Фактически базируется на JPEG и разделяет с ним идеи. Помимо них добавляется еще одна: ^fe65ee

Между двумя отдельными кадрами видео изменения как правило малы

Краеугольным камнем всего формата являются кадры двух типов: I - кадры, сжатые полноценно и независимо, и P - кадры, которые построены с ссылкой на предыдущий)

В целом уже довольно сильное сжатие можно было бы достичь и этим, но мы пошли чуть дальше и ввели категорию B - кадры, которые ссылаются на следующий и предыдущий кадры. В реализациях классического MPEG алгоритма они вообще просто генерируются на основании двух ближайших кадров категорий I и P. Обычно являются неким "средним арифметическим" между этими двумя кадрами. на эту категорию ничего не ссылается

Примерное кодирование выглядит так: нeзависимо кодируется кадр видео целиком. Обычно кодируются каждый пол секунды видео. Затем если мы говорим про частоту кадров в 24 кадра/секунду, то на равных промежутках вставляется еще 3 кадра категории P. Они кодируются, как и было сказано, со ссылкой на предыдущий кадр. А дальше добивается это дело B-кадрами. Судя по описанию методички их по факту даже нет в исходном видеоряде. Они просто строятся на основе двух соседних кадров^[Чем-то напоминает dlss если вы понимаете о чем я]. Обычно кодирование ведется группами по N кадров. Такие группы могут декодироваться независимо от других групп. Обычно размеры группы естественным образом определяются расстоянием между кадрами типа I. ^9aa8aa

Говоря о самих изображениях, они состоят из макроблоков (размером 16х16 пикселей %%ничего не напоминает?)%%). Такие блоки имеют привычку смещаться и немного изменяться со временем. Вот их смещения обычно отслеживают и сжимают. Сжатие происходит очень сходно с JPEG

Основные пути повышения степени сжатия

Улучшение сжатия I-кадров
Улучшение подбора векторов смещения блоков (исходно - среднеквадратичное смещение%%Я тоже не в курсе, что за смещения векоторов. Такое чувство, что Молодяков тут не объясняет а напоминает%%)
Если у вас еще остались тяжелые наркотики можете посравнивать коэффициентики в соседних блоках 8х8. Там адовы преобразования можно усреднить значения соседних блоков и добавить степени сжатия
Если сжать кадры слишком сильно, то будут видны края блоков, но в целом можно алгоритмами убирать их на пост обработке и продолжать увеличивать сжатие
Можно предварительно обработать видео, чтобы оно лучше подходило для сжатия (вырезать многие детали, которые все равно не заметны), вырезать разные шумы и "высокие частоты"^[Молодяков их так назвал. Что это в контексте изображения - ума не приложу]

Motion-JPEG

Если видео короткое, или вам в целом все равно, что один видосик будет занимать у вас пол диска, то можно обойтись и Motion-JPEG (M-JPEG). Он заключается в основном в том, что все кадры будут независимо сжаты при помощи JPEG.

Это помогает при монтаже видео и в целом JPEG обладает аппаратным ускорением^[То есть в процессоры вмонтированы устройства подобные тем, что мы на схемаче собираем, которые гоняют только операции над JPEG и ничем другим не занимаются. За счет того, что такие сопроцессоры не программируются а один раз собраны, скорость обработки получается очень быстрой]

Шифр простой подстановки - шифр, где каждому символу исходного алфавита (например русского), ставится в соответствии символ другого алфавита. Классический пример - замена одних букв на другие: а -> в, г -> а и т.д. И тогда сообщение "Бегите, глупцы" станет "Гжакфж, анхсшэ" (тут поменяны и другие буквы, можете попытаться прикинуть, какой алфавит тут использовался). Символом другого алфавита может быть и просто другой символ. Ярким примером может стать например шифр Стенфорда Пайнса из Гравити Фолз (кстати рекомендую попробовать его расшифровать, мне это доставило некоторое удовольствие) ↩︎

36 KiB Raw Permalink Blame History Unescape Escape