Кодирование символов

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

Рейтинг:   / 1

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

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

Серия повторяющихся величин заменяется двумя: значением и количеством. Цепочка из n одинаковых байтов (при байт/пиксел) будет заменена двумя байтами. Хорошо кодируются изображения с большими областями постоянной закраски (из-под "рисовалок" типа PaintBrush).

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

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

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

Используется в архиваторах. Подобно алгоритму Хаффмана, заменяет длинные последовательности более короткими, но не требует предварительно собирать статистику. Он формирует все более эффективную таблицу кодирования по мере продвижения по шифруемому массиву. Более "шумные" изображения кодируются хуже. Поэтому иногда рекомендуется подавить низкочастотной фильтрацией высокие пространственные частоты на изображении Типичные коэффициенты сжатия между 1:1 и 1:3, хотя иногда м.б. и 1:10. Этот алгоритм используется в графических форматах GIF и TIFF.

Арифметическое сжатие (1979...1989)

Подобно алгоритму Хаффмана, использует более длинные кодовые последовательности для более редких входых последовательностей.

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

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

Алгоритм JPEG Joinnt Photographic Experts Group - комитет ISO

Метод сжатия включает следующие шаги:

  1. Представление RGB преобразуется в представление YCbCr (формулы были даны ранее в этом тексте)
  2. Выполняется дискретное косинусное преобразование для квадратных фрагментов изображения (обычно 8х8) отдельно для яркости и отдельно (с меньшей пространственной дискретностью) - для цветовых компонент.
  3. Полученные коэффициенты округляются. Это позволяет представить их меньшим количеством битов (на этом этапе - основные потери. Коэффициенты при высоких частотах при этом могут оказаться нулевыми, тогда их можно отбросить.
  4. Последовательность коэффициентов кодируется по Хаффману или алгоритмом арифметического кодирования.
  5. При декодировании этапы выполняются в обратном порядке. Достижимые коэффициенты сжатия - 1:10...1:50 при ухудшающемся качестве.
Я(0,0) Я(0,1) Я(0,2) ...
Я(1,0)  Я(1,1) Я(1,2)  ...
Я(2,0)  Я(2,1)  ... ...
... ...
 
         
 

--------------------->

--------------------->

F(0,0)     F(0,1)                           
F(1,0) F(1,1)
 

 
F(2,0) F(2,1)
 

 

 

 

 

 

MPEG - международный комитет Motion Pictures Expert ISO в 1993г

MPEG разработан международным комитетом Motion Pictures Expert и принят в окончательной редакции ISO только в 1993г. Хотя MPEG-стандарт определяет правила кодирования и декодирования цифровых потоков как изображений, так и связанного с ними звука, в этом материале мы остановимся только на изображении. Стандарт JPEG отличается от MPEG тем, что проводит независимое сжатие каждого кадра изображения.

Компрессия использует следующие основные идеи:

  • Устранение временной избыточности видео, учитывающее тот факт, что в пределах коротких интервалов времени большинство фрагментов сцены оказываются неподвижными или незначительно смещаются по полю. На рисунке (см. рисунок ниже) показаны два соседних кадра из фильма Терминатор-2 и разностный кадр (кодируем разностный кадр).
  • Устранение пространственной избыточности изображений подавлением мелких деталей сцены, несущественных для ее визуального восприятия человеком (цвет большинства точек неба одинаков - кодируем их одинаково).
  • Использование более низкого цветового разрешения при YUV-представлении изображений (Y -яркость, U и V - цветоразностные сигналы). Установлено, что глаз менее чувствителен к пространственным изменениям оттенков цвета по сравнению с изменениями яркости. Повышение информационной плотности результирующего цифрового потока путем выбора оптимального математического кода для его описания (например, использование более коротких кодовых слов для наиболее часто повторяемых значений).

На первой ступени поток видео разделяется на кадры изображения:

  • I (Intra) - независимо сжатые, опорные при восстановлении остальных изображений по их разностям;
  • Р (predicted) - сжатые с использованием ссылки на одно изображение, содержащие разность текущего изображения с предыдущим I или Р с учетом смещений отдельных фрагментов;
  • В (bidirertlonally predicted) - сжатые с использованием ссылки на два изображения, содержащие разность текущего изображения с предыдущим и последующим изображениями типов I или Р с учетом смещений отдельных фрагментов.

Изображения объединяются в группы (GОР Group Of Pictures), представляющие собой минимальный повторяемый набор последовательных изображений, которые могут быть декодированы независимо от других изображений в последовательности. 

Типичной является группа вида (I0 В1 B2 РЗ В4 В5 Р6 В7 В8 Р9 B10 В11) (I12 В13 В14 Р15 В16 В17 Р18...), в которой I-тип повторяется каждые пол-секунды. Обратим внимание, что в изображении РЗ основная часть фрагментов сцены предсказывается на основании соответствующих смещенных фрагментов изображения I0. Собственно кодированию подвергаются только разности этих пар фрагментов.

Аналогично Р6 строится на базе РЗ, Р9 - на базе Р6 и т.д. В то же время большинство фрагментов В4 и В2 предсказываются как полусумма смещенных фрагментов из I0 и РЗ, В4 и В5 - из РЗ и Р6, В7 и В8 - из Р6 и Р9 и т.д. В то же время В-изображения не используются для предсказания никаких других изображений.

Ясно, что точность кодирования должна быть максимальной для I, ниже - для Р, минимальной - для В. Установлено, что для типичных сцен хорошие результаты достигаются при отведении числа бит для I в 3 раза больше, чем для Р, и для Р в 2-5 раз больше, чем для В. Эти отношения уменьшаются для динамичных сцен и увеличиваются для статичных.

Отдельные изображения состоят из макроблоков. Макроблок - это основная структурная единица фрагментации изображения. Он соответствует участку изображения размером 16х16 пикселей. Именно для них определяются вектора смещения относительно I- или Р- изображений. В свою очередь каждый макроблок состоит из шести блоков, четыре из которых несут информацию о яркости Y, а по одному - определяют цветовые U- и V- компоненты. Каждый блок представляет собой матрицу 8х8 элементов. Блоки являются базовыми структурными единицами, над которыми осуществляются основные операции кодирования, в том числе, выполняется дискретное косинусное преобразование (DCT discrete cosine transform) и квантование полученных коэффициентов. Кодирование блоков похоже на кодирование в алгоритме JPEG.

Упрощенно процесса MPEG-кодирования сводится к следующему:

  • На этапе предварительной обработки входной видеосигнал оцифровывается и форматируется согласно заданному размеру и цветовой выборке 2:1 (на каждые 2 Y-отсчета по горизонтали и вертикали приходится по одному U- и V-отсчету).
  • После этого кодер осуществляет выбор структуры группы (она может меняться в процессе кодирования в зависимости от содержания видео и разрешенного объема передаваемой информации), задает типы всех изображений и, по необходимости, меняет их последовательность.
  • Далее для I-изображений он осуществляет DCT каждого макроблока. Для Р- и В-изображений он сначала оценивает вектора смещения: по одному на макроблок для Р (для предсказания вперед) и по 2 - для В (вперед и назад).
  • Затем, сравнивая число бит, необходимое для кодирования макроблока как в случае предсказания его значений на основе соответствующих макро- блоков из предыдущего (для Р) и последующего (для В) изображений, так и без оного предсказания, -кодер по каждому макроблоку принимает отдельное решение и осуществляет DCT либо собственных значений макро-блока, либо его разностных (относительно предсказанных) значений.
  • После этого полученные коэффициенты DCT подвергаются квантованию с переменным шагом более высоким частотам задается больший шаг. В результате большинство высокочастотных коэффициентов принимают нулевые значения, что позволяет математически эффективно их кодировать. Изменяя масштаб квантования, кодер реализует компромисс между качеством кодированных изображений (тем хуже, чем больше масштаб) и объемом передаваемой информации (тем меньше, чем больше масштаб). Это особенно важно для систем с фиксированной пропускной способностью.
    Поскольку в видео информационная насыщенность изображений меняется со временем, то кодер должен постоянно отслеживать реальный объем передаваемых данных и оперативно менять масштаб квантования и, конечно, значения других параметров.
    Безусловно, этот процесс не может быть абсолютно точным, поэтому кодер (как и декодер) обладает буфером памяти, в который предварительно записывается переменный поток данных, и из которого этот поток передается с заданной скоростью.
    Чем больше размер этого буфера, тем большие изменения объема данных на изображение относительно среднего уровня допускаются. В стандарте буфер установлен как 327 680 бит (40 Кб), что при скорости 200 Кб/с соответствует 0,2 с.
    Таким образом, кодер должен следить за реальным состоянием буфера, не допуская его переполнения (часть данных 6удет потеряна) или недополнения (качество передаваемых изображений будет неоправданно низким).
    В результирующем потоке кодер должен передавать как собственно математически закодированные значения коэффициентов DCT, так и выбранные значения всех параметров кодировки (вид матрицы квантования и ее масштаб, тип предсказания макроблока и значения векторов смещения, структуру группы и т.д.).
  • Декодеру остается сравнительно простая работа - принять в буфер и расшифровать (шифр задан стандартом) полученную информацию, осуществить обратные преобразования и отобразить полученное видео на мониторе.

Вышеизложенное объясняет, почему при наличии множества недорогих MPEG-проигрывателей MPEG-кодеры до сих пор остаются дорогими и элитарными устройствами.

Команды работы с изображением

Перечислим операции по обработке изображений, которые находят свое отражение в системах команд процессоров:

  • побитовая обработка - команды побитовой обработки, часто называемые логическими командами, есть во всех процессорах;
  • перенос блоков (двумерных фрагментов, обычно прямоугольных) - Transputer, графические сопроцессоры;
  • аппаратное рисование примитивов: линии, прямоугольники, трапеции - графические сопроцессоры;
  • поддержка shading и удаления невидимых - операции линейной интерполяции (i80860, MMX).

 

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

Рейтинг:   / 0
  1. Формат PCX ( PCExchange) разработан PCPaintBrush, является одним из самых известных и старых. Практически любое приложение легко импортирует его. Он не позволяет хранить цветоделенные CMYK-изображения и цветовые профили, что делает невозможным его применение при создании цветных публикаций. Является устаревшим, вытеснен усовершенствованными форматами GIF и TIFF.
  2. Формат BMP (Bitmap) предназначен для Windows и поддерживается всеми приложениями, работающими в этой среде. Позволяет хранить полноцветные изображения в цветовой модели RGB и индексированные изображения. Не применяется в издательской деятельности, но широко используется в оформлении прикладных программ.
  3. Формат JPEG (JointPhotographicExpertsGroup) предназначен для сохранения растровых файлов со сжатием. Сжатие по этому методу уменьшает размер файла от десятых долей процента до ста раз (практический диапазон - от 5 до 15), но при этом происходит потеря качества (в большинстве случаев эти потери находятся в пределах допустимых). Распаковка JPEG-файла происходит автоматически во время его открытия. Формат поддерживает только полутоновые и полноцветные изображения в моделях RGB и CMYK. Допускается сохранение контуров обтравки и цветовых профилей. Формат не позволяет использовать анимацию и прозрачность. Обычно формат JPEG применяется для хранения высококачественных фотографий. Формат JPEG позволяет использовать до 16 миллионов цветов.
  4. Формат GIF (GraphicsInterchangeFormat) в издательских целях не применяется,однако очень широко распространен на Web. Допускает хранение в одном файле нескольких изображений. Чаще всего такая возможность используется на страницах Web. Web-браузер демонстрирует изображения, находящиеся в файле GIF последовательно. Если каждое изображение представляет собой фазу мультипликации, то вы увидите маленький мультфильм. Формат способен хранить только индексированные изображения. Стандартный фильтр экспорта в. формат GIF поддерживает единственную особенность формата- чересстрочную развертку. Чересстрочная развертка используется браузерами: по мере загрузки в изображении появляется все больше деталей. Это дает возможность пользователю еще в процессе загрузки изображений решить, стоит ли дожидаться ее завершения или перейти к следующей странице.
  5. Формат PNG (PortableNetworkGraphics) предназначен для передачи изображений в сетях. Поддерживает полноцветные изображения RGB и индексированные изображения. Возможно использование единственного дополнительного канала для хранения маски прозрачности. Имеет эффективный алгоритм сжатия без потери информации. Этот формат тоже применяется на Web
  6. Формат PCD (Photo CD). Изображения запоминаются всегда в альбомной ориентации. Дает при импорте определять разрешение изображения.
  7. Формат PSD (Adobe Photoshop Document) является внутренним форматаом программы AdobePhoroshop. Удобен для общения с другими продуктами фирмы Adobe. Поддерживает все сведения о документе, но пока недостаточно распространен. 
  8. Формат TIFF (Tagged Image File Format) создан как универсальный формат для сканированных изображений. Переносим на разные платформы. Импортируется парктически во все издательские системы. Поддерживает алгоритмы сжатия без потерь.
  9. Формат EPS (Encapsulated PostScript) описывает изображение на универсальном языке PostScript. Описывает не только растровые, но и векторные изображения, а также текст. Предпочтителен для полиграфических целей. Имеет большой размер файла.
  10. Формат DCS позволяет вставлять изображения, разделенные на плашечные цвета. Является вариантом формата EPS.
  11. Формат PDF (Portable Document Format) предложен фирмой Adobe как независимый от платформы формат, в котором могут быть сохранены иллюстрации (векторные и растровые) и текст, причем с множеством шрифтов и гипертекстовых ссылок. Для достижения продекларированной в названии переносимости (portable), размер PDF-файла должен быть малым. Для этого используется компрессия - к каждому виду объектов применяется свой способ. Для работы с этим форматом компания Adobe выпустила пакет Acrobat. Acrobat Distiller переводит в PDF PostScript-файлы, Acrobat Exchange позволяет их редактировать: устанавливать внутренние ссылки, ссылки на внешние звуковые и видеофайлы, Web-ссылки. Ряд программ также позволяют создавать PDF'ы. Первоначальная задача PDF - передача по сети в сжатом виде проиллюстрированных и отформатированных документов - сегодня значительно расширена. Кроме того, в PDF можно быстро передавать клиенту полноценные эскизы. PDF позволяет не заботиться о наличии необходимых шрифтов у получателя - все подгружается прямо в файл.

Общие вопросы представления графических данных для хранения, передачи и отображения

Рейтинг:   / 0

Общая схема операций с изображением включает следующие этапы:

  1. Ввод изображения (Подсистема COMPUTER VISION). Используется входное описание изображения, м.б. преобразование в формат обработки или в формат хранения.
  2. Обработка в компьютере (IMAGE PROCESSING). После обработки изображение может быть преобразовано в формат отображения или в формат хранения/передачи.
  3. Вывод изображения (Подсистема COMPUTER GRAPHICS). 

Подсистемы 1 и 3 характеризуются каждая рядом величин:

  • пространственной разрешающей способностью (количество пикселов);
  • разрешающей способностью по уровню (количество градаций яркости);
  • неквадратностью пиксела;
  • линейностью характеристики преобразования света;
  • размерами поля.

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

Система IMAGE PROCESSING обычно содержит память, в которой хранится обрабатываемое изображение. Его представление в памяти должно быть наиболее удобным для обработки. В частности, хорошо, когда элементами данных являются числа, прямо несущие информацию об интенсивностях цветовых компонент. Размер как памяти, так и хранимого в ней изображения, - может никак быть не привязан ни к параметрам устройства, с помощью которого может быть получено изображение (сканер, телекамера, …), ни к параметрам подсистемы вывода изображения (видеоконтроллер + дисплей, плоттер,…).

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

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

Рейтинг:   / 0

Свойства изображений, которые хочется отобразить в графическом файле: 

  • чтобы система работала с разными устройствами ввода и с разными устройствами вывода и была инвариантна к различию их свойств;
  • чтобы объем данных при хранении или передаче был минимальным, поэтому для хранения наиболее объемной части (собственно изображения) используют разнообразные алгоритмы сжатия (компрессии) данных (на компрессию / декомпрессию будет уходить дополнительное время.);
  • чтобы формат представления собственно изображения требовал минимума действий для преобразования из входного формата в формат обработки, а затем в формат отображения;
  • чтобы описывалось более одного изображения в одном файле, тогда необходимо сохранять индивидуальные характеристики для каждого изображения, такие как таблица цветов, позиционирование и т.п.;
  • кроме того, размещение изображения на "листе" (привязка к координатам вывода), interlacing (чередование строк0 и др.

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

Графические форматы

Группа способов кодирования, в которых разделена информация о яркости (интенсивности) и цвете

Рейтинг:   / 9

(Y,Cb,Cr): Y - luminosity яркость, Cb и Cr - доли синего и красного. Такие представления позволяют с разной точностью кодировать яркость (более точно, т.е. большим количеством битов на пиксел) и менее точно - цвет. Это разумно, так как глаз менее чувствителен к относительному изменению интенсивностей отдельных цветов и более чувствителен к суммарной интенсивности.

Y= 0.299R +0.587G +0.114B
Cb= 0.1687R -0.3313G +0.500B
Cr= 0.500R -0.4187G +0.0813B

Есть и другие способы кодирования, относящиеся к этой группе.

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

Способы и точность кодирования цвета имеет две взаимосвязанных стороны:

  1. Количество представляемых цветов.
  2. Как эти цвета выбраны во всем множестве цветов (в RGB- пространстве). Используются два способа:
  • непосредственное представление цветовых компонент;
  • представление с использованием таблицы цветов Color Look-Up Table (CLUT).

При непосредственном представлении цветов каждый пиксел изображения представлен элементом данных, включающим три битовых поля R, G, B. Каждое поле содержит число, характеризующее интенсивность одной цветовой компоненты. Код этой интенсивности непосредственно используется для управления яркостью луча при отображении на дисплее. Размеры полей nr, ng, nb определяют общее количество представимых цветов N=2n, где n=nr+ng+nb - количество битов на один пиксел.

При длине элемента данных, описывающего пиксел, равной одному байту (8 битов), длины цветовых полей R, G, B обычно составляют соответственно 3, 3 и 2 бита. При этом общее количество представимых цветов равно 28=256. Меньшее количество битов для интенсивности синего в данном и в следующем представлениях объясняется меньшей чувствительностью глаза к изменениям синего.

При длине элемента данных пиксела в два байта (16 или 15 битов) цветовые компоненты обычно имеют длины 6(R), 6(G) и 4(B) бита, или 5(R), 6(G) и 5(B), или 5(R), 5(G) и 5(B), или 4(R), 4(G) 4(B и 4(Атрибут), а общее количество представимых цветов равно 216=65536 либо 215=32768. Это представление называют HiColor.

При большей длине пиксела используют для каждой цветовой компоненты поле длиной в байт, при этом количество градаций по каждому цвету составляет 28=256, а общее количество представимых цветов равно 224=16777216 (около 16 миллионов). Это представление носит название True Color. Длина элемента данных, описывающего пиксел может составлять три, либо четыре байта, в последнем случае "лишний" байт используется для какой-либо дополнительной информации о пикселе.

При непосредственном представлении цветов точность представления цвета, набор и количество представимых цветов однозначно связаны. Это означает, например, что в формате "два байта на пиксел" 6(R), 6(G), 4(B) количество градаций красного mr и зеленого mg равно по 26=64, количество градаций синего mb равно 24=16, а общее количество представимых на одном изображении цветов равно mr*mg*mb=26*26*24=216=65536.

При использовании представления с таблицей цветов код пиксела не содержит информации об интенсивности цветовых компонент, а лишь указывает строку в таблице цветов (см. рисунок ниже).

Таблица цветов представляет собой память небольшого объема: m строк (называемых обычно регистрами), в каждой строке (регистре) nr + ng + nb битов. Обычно делают nr = ng = nb = n. В памяти (на диске, в массиве изображения в ОЗУ, в видеопамяти и т.п.) одному пикселу соответствует элемент данных длиной m битов (чаще всего один байт). При этом на изображении возможно одновременно отображать не более 2m цветов. Информация о цветовых компонентах этих цветов хранится в строках таблицы цветов. При этом "точность" задания цвета определяется длинами nr, ng, nb полей. Регистры таблицы цветов программно доступны, таким образом набор отображаемых цветов (палитру) можно в любой момент переопределить программно. Всего возможно задать 23n разных оттенков, однако в каждый данный момент отображаются только 2m из них.

Наиболее известная реализация системы с таблицей цветов - видеоадаптеры типа VGA. В них использована таблица размером 256 регистров х 3 * 6 бит/цвет. Одномоментно доступны 256 цветов из набора в 262144 цвета.

 

Яндекс.Метрика