Триколор 

Реализация в Matlab алгоритмов построения фрактальных объектов. Лекция - цветовые пространства. История фрактального сжатия

В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000 качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480.

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

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

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

Итак, в 1991 году такой алгоритм был найден. Кроме того, в дальнейших его статьях декларировался ряд уникальных возможностей новой технологии. Так, фрактальный архиватор позволяет, например, при распаковке произвольно менять разрешение (размеры) изображения без появления эффекта зернистости. Более того, он распаковывает гораздо быстрее, чем ближайший конкурент JPEG , и не только статическую графику, но и видео. В качестве примера приводилась программа, показывающая на машине с процессором i386/33 МГц цветной видеофильм с частотой 20 кадров в секунду без всякой аппаратной поддержки. В отличие от JPEG, в алгоритм изначально заложена возможность управлять степенью потерь на участках с максимальными потерями качества. Коэффициент сжатия изображений в целом примерно как у JPEG, но на некоторых реальных картинках достигалось сжатие в 10000 (!) раз.

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

История фрактального сжатия

Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто.

Четыре года спустя появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов.

Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии.

Если построение изображений с помощью фрактальной математики можно назвать прямой задачей, то построение по изображению IFS - это обратная задача. Довольно долго она считалась неразрешимой, однако Барнсли, используя Collage Theorem, построил соответствующий алгоритм. (В 1990 и 1991 годах эта идея была защищена патентами.) Если коэффициенты занимают меньше места, чем исходное изображение, то алгоритм является алгоритмом архивации.

Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека".

Отношение к новому методу изменилось в 1992 году, когда Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело.

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

В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии. Таким образом, многие важные события в области фрактальной компрессии произошли за последние три года: алгоритм только-только начинает развиваться.

Идея

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

Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость).

Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей.

Одна шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении.

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

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

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

Оценка потерь и способы их регулирования

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

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

Возможности масштабирования

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

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

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

Масштабирование - уникальная особенность, присущая фрактальной компрессии. Со временем ее, видимо, будут активно использовать как в специальных алгоритмах масштабирования, так и во многих приложениях. Действительно, этого требует концепция "приложение в окне". Было бы неплохо, если бы изображение, показываемое в окне 100х100, хорошо смотрелось при увеличении на полный экран - 1024х768.

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG . Сравним его с фрактальной компрессией.

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

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG . Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

N = 1500; %Количество точек (Точность)

x = zeros(N, 1); %Массив из N нулей, в будущем - наши F(n) - итерации

x(1) = 0.5; %Начальная точка

for r = 3.5: 0.001: 4 %Цикл от начала до конца диаграммы

x(c) = r * x(c-1) * (1-x(c-1)); %Итерация каждой функции

x(1: N-120) = ;

plot(t, x,"k.","MarkerSize", 3); %Поточечный вывод графика

xlabel("r"); ylabel("x"); %подпись осей

title("Bifurcation diagramm"); %подпись диаграммы

Задание

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

    1. Модель Рикера (Чётные номера вариантов)

      Модель Ферхюльста (Для нечётных вариантов)

c – положительный параметр, указывающий скорость увеличения популяции;

x – численность популяции.

c

r

c

r

[ 0.99, 2.95 ]

Для модели Риккера выбранную константу умножить на 6,2 (c’ = 6,2 * c).

Контрольные вопросы

    Почему последовательные бифуркации в системе влекут за собой хаотичное поведение?

    Какие существуют константы Фейгенбаума и чем они характирезуются (Их смысл)

    Почему точка периода 3 влечёт хаос?

Лабораторная работа № 4. Фрактальное броуновское движение

Цель работы

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

Методические указания

Броуновское движение

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

Когда в среду погружено крупное тело, то толчки, происходящие в огромном количестве, усредняются и формируют постоянное давление. Если крупное тело окружено средой со всех сторон, то давление практически уравновешивается, остаётся только подъёмнаясила Архимеда- такое тело плавно всплывает или тонет.

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

Приведем пример построения двумерного броуновского движения в среде MatLab. В MatLab элементы распределения получаются с помощью командыrandn.

N=10000; % количество шагов

T=70; % максимальное время

h=T/N; % интервал времени

t=(0:h:T); % вектор

sigma = 1.0; % сила шума

x=zeros(size(t)); % выделение массива для x

y=zeros(size(t)); % выделение массива для y

x(1)=0.0; % начальное положение x

y(1)=0.0; % начальное положение y

x(i+1)=x(i)+sigma*sqrt(h)*randn;

y(i+1)=y(i)+sigma*sqrt(h)*randn;

grid on % добавление сетки для осей

После запуска программы получим график вида:

Рис. 4 Броуновское движение частицы


Учебные вопросы:


1. Определение понятий "цветовая модель" и "цветовое пространство" (повторение).
2. Цветовое координатное пространство RGB.
3. Цветовое координатное пространство YCBCR и преобразование из RGB в YCBCR.
4. Примеры работы в пространстве YCBCR.
5. Гистограммы изображений

Основные цветовые пространства, которые используются при сжатии изображений – это RGB (классическое пространство) и YCrCb – так называемоецветоразностное пространство. Но прежде чем вести разговор о цветовых преобразованиях, необходимо определить, что такое цветовое пространство.

Цветовое пространство – область изменения и существования цвета в заданной цветовой системе (RGB , HSB ). Цветовой системой называется цветовое пространство с организованной системой цифровых цветовых координат для любого цвета. По-другому цветовое пространство представляет собойматематическое представление множества цветов. Существует три наиболее популярных цветовых пространства, используемых в машинной графике

RGB – red , green , blue (красная, синяя и зеленая составляющие), применяется в компьютерной графике (излучаемые цвета).

YCrCb (или YIQ , YUV ), используется в видеосистемах и в алгоритмах сжатия информации (например, JPEG ).

CMYK – используется при печати (отраженные цвета).

Кратко опишем цветовое пространство RGB , а затем перейдем к рассмотрению пространства YCrCb .

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

Рис.1. Цветовой куб RGB


Цвета RED , GREEN , BLUE являются компонентами пространства RGB (аддитивные цвета, нужный цвет получается смешением цветов), а, в свою очередь, цвета CAYN (голубой), MAGENTA (пурпурный), YELLOW (желтый) являются компонентами пространства CMYK (K – черный, BLAK – субтрактивные цвета, для образования цвета используется вычитание). Хотя цветовое пространство RGB идеально подходит для использования в компьютерной графике, но его использование не совсем эффективно при работе с реалистическими изображениями. Поэтому были разработаны другие цветовые пространства:

  • YUV , используется в системах PAL (Phase Alternation Line – линия с чередующейся фазой), NTSC (National Television System Committee – национальный комитет по телевизионной системе) и SECAM . Системы, транслирующие черно-белое видеоизображение используют только Y (светимость) и информацию о цвете (составляющие U и V ). Они сочетаются таким образом, что ресивер получает нормальную черно-белую картинку. Цветной ресивер декодирует дополнительную информацию о цветном изображении.
  • YIQ – цветовое пространство, опционально используемое в стандарте композитного NTSC . I обозначает фазу, Q – т.н. «квадратуру», которая является методом модуляции, использующегося для передачи цветной информации.
  • YCrCb – цветовое пространство, разработанное как часть рекомендации ITU - R BT .601, в процессе разработки глобального цифрового компонента стандарта видео.

Мы рассмотрим цветовое пространство YCrCb . Его составляющие определяют следующим образом:

  • Y - светимость (яркость).
  • Cb – цветность синего (хроматический синий)
  • Cr – цветность красного (хроматический красный).

Рассматриваемое цветовое пространство[ Ian E . G . richardson , H .264 and MPEG -4, 200] и его варианты (иногда именуется как YUV ) является одним из популярных методов эффективного представления цветных изображений. Y – светимость. Показатель может быть определен как среднее взвешенное компонентов R , G , B , запишется следующее соотношение:


гдекоэффициенты k – доли цветов, специальные коэффициенты. Они определены в рекомендации ITU - BT .601 следующим образом: k r = 0.299, k b = 0,114. Коэффициент k g не определяем, поскольку сумма трех коэффициентов равна 1.

Информация о цветах может быть представлена как цветовая разница (хроматические данные или насыщенность цвета). В этом случае каждая компонента представляет собой разницу между R , G , B и светимостью Y.


Полное описание цветного изображения дается с помощью компонента светимости (Y ) и трех цветоразностных компонентов Cb , Cr , Cg , представляющие собой разность между интенсивностью цвета и означают светимость каждого компонента изображения.

Заслуживает внимания то, что получили четыре компоненты вместо трех. Однако выражение Cb + Cr + Cg постоянно и необходимо запомнить только две из трех цветоразностных компонент, а третья может всегда может быть посчитана. В цветовом пространстве YCrCb для передачи записывается только компонента светимости (Y ), синяя (Cb ) и красная (Cr ) компоненты.Цветовое пространство YCrCb имеет важное преимущество перед пространством RGB , состоящее в том, что компоненты Cb и Cr могут быть представлены с более низким разрешением, чем компонента светимости, поскольку система человеческого зрения менее чувствительна к цвету, чем к светимости (яркости). Это снижает стоимость данных, необходимых для представления хроматических компонент, не оказывая существенного влияния на качество отображения. Для случайного наблюдателя нет очевидной разницы между RGB -изображением и YCrCb -изображением с пониженным разрешением хроматических компонент. Использование представления насыщенности цвета с более низким разрешением, чем светимость, является простой, но эффективной формой сжатия изображений.

Обычное изображение после захвата может быть преобразовано в YCrCb -изображение с целью уменьшения затрат памяти, необходимой для хранения изображения и/или для передачи по каналу связи. Перед отображением на экране монитора необходимо выполнить обратное преобразование: перевод в RGB -изображение. Приведем соотношения, необходимые для преобразования цветовых пространств .


Y = 16 + 65.481 * R + 128.553 * G + 24.966 * B ;

Cb = 128 - 37.797 * R - 74.203 * G + 112 * B;

Cr = 128 + 112 * R - 93.786 * G -18.214 * B;

Эти формулы были определены в рекомендации CCIR 601-2. Цветовое пространство YCrCb разработано как основа для стандарта цифрового видео. Компонента светимости Y имеет значения от 16 до 235, хроматические компоненты Cr и Cb изменяются в диапазоне 16 – 240, причем 128 соответствует нулевым значениям. Также описаны в рекомендации несколько форматов YCrCb , которые используются для дальнейшей обработки сигналов: 4:4:4, 4:2:2, 4:1:1. Мы о них поговорим в следующих лекциях, когда будем изучать алгоритм сжатия JPEG , а также выясним, почему были получены именно такие соотношения.

В цветовой модели RGB используется три основных цвета, с помощью которых можно получить любой оттенок видимого спектра. Максимальное количество различных цветовых оттенков определяется глубиной цвета, которая, в свою очередь, определяется количеством битов, используемых для кодирования цвета. В популярной модели RGB 24 с глубиной цвета 24 бита для каждого цвета отводится по 8 битов. С помощью 8 битов можно задать 256 различных цветовых оттенков соответственно красного, зеленого и синего цветов. Каждому оттенку присваивается значение от 0 до 255. К примеру, красный цвет может принимать 256 градаций: от чисто красного (255) до черного (0). Максимальное значение кода соответствует чистому цвету, а код каждого цвета принято располагать в следующем порядке: красный, зеленый и синий. Например, код чистого красного цвета записывается в виде (255, 0, 0), код зеленого цвета - (0, 255, 0), а код синего цвета - (0, 0, 255). Желтый цвет можно получить смешением красного и зеленого, и его код записывается в виде (255, 255, 0) .

Основное достоинство модели YUV (YCrCb) заключается в том, что этот метод кодирования хотя и более сложен, чем RGB, однако требует меньшей полосы пропускания. Дело в том, что чувствительность человеческого глаза к яркостному Y-компоненту и цветоразностным компонентам неодинакова, поэтому вполне допустимым представляется выполнение этого преобразования с прореживанием (интерливингом) цветоразностных компонентов, когда для группы из четырех соседних пикселов (2×2) вычисляются Y-компоненты, а цветоразностные компоненты используются общие (так называемая схема 4:1:1).

Рис.2. Слева - изображение в пространстве RGB, справа - в пространстве YCBCR.

Y – это набор яркостей, который основывается по большей части на зелёном цвете, лучше всего воспринимаемом человеческим глазом. Наборы Cr и Cb хранят ключи для восстановления красного и синего цвета из Y. Использование разложения YCrCb позволяет сильнее сжимать изображение при меньших потерях качества, так как главная информация для человека в картинке – это именно информация о яркости отдельных точек. Составляющие Cr и Cb хорошо сжимаются, не внося сильных ухудшений в качество картинки, сами по себе они менее чёткие, чем Y. С помощью команд пакета MATLAB можно выделить составляющие изображения и сравнить их с составляющими обычного RGB -изображения.

Рис.3. Слева - канал Y, по центру и справа - каналы Cb и Cr

Если посмотрим на R , G , B -каналы изображения, то увидим отличия:

Рис.4. Каналы: Red(слева), Green(по центру), Blue (справа)

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

В современных алгоритмах сжатия кодирование компонент происходит независимо друг от друга, при сжатии не учитывается взаимная связь между сигналами. При анализе уравнений преобразования цветовых пространств можно заметить следующий факт: существуют две точки: набор для черного (0,0,0) и набор для белого (255, 255, 255) цвета, для которых можно однозначно вывести значения в YCrCb пространстве. Для пространства YCrCb эти значения будут следующими: черный YCrCb = (0,0,0) и белый YCrCb = (255,128,128). Цветовой куб пространства выглядит следующим образом:

Рис.5. Цветовой куб YCBCR

Далее следует рассмотреть этапы кодирования по алгоритму JPEG - дискретное косинусное преобразование, квантование и энтропийное кодирование. Также посмотрим, как определяется степень потерь при сжатии (если изучается среда MATLAB, то далее целесообразно провести лабораторную работу по гистограммам изображений (смотри файл).


Лекция - цветовые пространства

1. Панов Е.А. Познание цвета: Равнозначность цвета в цифровых системах. М.: Книжный дом «ЛИБРОКОМ», 2009ю – 240 с. ISBN 978-5-397-00192-2.

2. Гонсалес Р., Вудс.Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. Москва: Техносфера, 2006. – 616 с. ISBN 5-94836-092-X.

3. Сэломон Д. Сжатие данных, изображений и звука, 2006

4. http://courses.graphicon.ru/main/mdc - курсы лаборатории компьютерной графики ВМиК МГУ

Цветовое пространство YCBCR

Система CMYK . Данная система используется для формирования цветов окрашенных несветящихся объектов, которые поглощают часть спектра освещающего белого света и отражают остальное излучение. Система CMYK является основной для цветной печати. Она основана на субтрактивной модели CMY (Cyan - голубой, Magenta - пурпурный, Yellow - желтый) - модели вычитания цветов. Основных цветов здесь по-прежнему три: голубой - это белый минус красный, пурпурный – белый минус зеленый, желтый - белый минус синий. Для улучшения качества полиграфического изображения в систему добавлен черный цвет, который является ключевым (Key – отсюда буква K в названии системы) для цветной печати.

Система HSB . Эта система основана на использовании тона или оттенка (Hue), насыщенности (Saturation) и освещенности (Lightness). Тон характеризует конкретный оттенок цвета, насыщенность – его относительную интенсивность, яркость цвета - величину черного оттенка для получения более темного изображения. Система HSB лучше соответствует модели восприятия цвета человеком. Разновидностью этой системы является система HSL, в которой буква I соответствует интенсивности цвета.

Глубина цвета определяет количество цветов при отображении одного пиксела (элемента) изображения. Если она равна 8 битам, то количество возможных цветов равно 256. Режим с глубиной цвета 24 бита называют истинным цветом (True Color). Количество возможных цветов при этом составляет . 32-битная глубина использует 24 бита для запоминания цветовой информации, а еще 8 бит применяют для запоминания насыщенности (прозрачности). Это так называемый альфа - канал. При этом значительно увеличивается скорость обработки графической информации процессором.

2. Форматы изображений


В настоящее время используется большое количество различных форматов графических файлов. Наиболее широко распространенными из них являются форматы TIFF, GIF, JPEG и BMP.

Формат TIFF (Tagged Image File Format) является одним из наиболее надежных и универсальных форматов для хранения сканированных цветных изображений с высоким качеством. В нем может быть использовано сжатие по алгоритму LZW, т.е. он относится к форматам хранения изображений без потерь.

Формат GIF (Graphics Interchange Format) имеет цветовую палитру в 256 цветов и использует для сжатия алгоритм без потерь LZW. Если исходное количество цветов больше 256, то часть цветовой информации будет утрачена.

Формат JPEG (Joint Photographers Expert Group) основан на одноименном алгоритме для сжатия изображений. Он относится к алгоритмам сжатия с потерями и предназначен для хранения полноцветных изображений с высоким коэффициентом сжатия. При использовании формата возможно управление параметром качества от 0 (максимальное сжатие) до 100 (максимальное качество). Коэффициент сжатия в зависимости от качества от 10 до 1000. Этот формат чаще других применяют для хранения полноцветных фотографических изображений, которые не предназначены для дальнейшей обработки.

Формат BMP (Windows Device Independent Bitmap) относится к собственным растровым (bitmap) форматам операционной системы Windows. Он пригоден для хранения изображений как в индексированном виде с палитрой до 256 цветов, так и в виде полноцветных RGB – изображений с глубиной цвета 24 бита. Возможно применение алгоритма сжатия RLE (Run Length Encoding).

Кроме вышеупомянутых MATLAB поддерживает форматы PNG (Portable Network Graphics) и XWD (X Window Dump).

4. Типы изображений Matlab

Пакет Image Processing Toolbox Matlab работает с четырьмя типами изображений:

· Бинарное (Binary ) – логический массив, содержащий только единицы и нули, при этом единицы соответствуют черному цвету, нули – белому.

· Индексное (Indexed ) –изображение состоит из массива и палитры. Палитра – это матрица с размерами m x 3. Каждая строка палитры описывает красную, зеленую и синюю составляющие цвета пиксела. Элемент матрицы изображения является индексом для строки матрицы палитры.

· Полутоновое (Grayscale ) – двумерный массив, значения элементов которого соответствуют значениям интенсивностей изображения.

· Полноцветное (Truecolor ), другое название RGB – изображение представляется массивом с размерами m x n x 3 в формате uint8, uint16, single или double . В этом массиве хранятся компоненты цвета (красная, зеленая и синяя составляющая) для каждого пикселя изображения.
В Matlab существуют возможности (функции) преобразования одного типа изображения в другой. Например, функция rgb2ind() преобразует полноцветное изображение в индексное.

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