Фрактальное сжатие изображений. Лекция - цветовые пространства. Сравнение с JPEG
В декабре 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 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.
|
|
Учебные вопросы:
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
Современные компьютеры весьма интенсивно применяют графику. Операционные системы с интерфейсом оконного типа используют картинки, например, для отображения директорий или папок. Некоторые совершаемые системой действия, например загрузку и пересылку файлов, также отображаются графически. Многие программы и приложения предлагают пользователю графический интерфейс (GUI), который значительно упрощает работу пользователя и позволяет легко интерпретировать полученные результаты. Компьютерная графика используется во многих областях повседневной деятельности при переводе сложных массивов данных в графическое представление. Итак, графические изображения крайне важны, но они требуют так много места! Поскольку современные дисплеи передают множество цветов, каждый пиксел принято интерпретировать в виде 24-битового числа, в котором компоненты красного, зеленого и голубого цветов занимают по 8 бит каждый. Такой 24-битовый пиксел может отображать миллионов цветов. Тогда изображение с разрешением 512х512 пикселов будет занимать 786432 байта. А изображению размером 1024х1024 пиксела потребуется 3145728 байт для его хранения. Мультфильмы и анимация, которые также весьма популярны в компьютерных приложениях, потребуют еще большего объема. Все это объясняет важность сжатия изображений. К счастью, изображения допускают частичную потерю информации при сжатии. В конце концов, изображения призваны для того, чтобы люди на них смотрели, поэтому та часть изображения, которая не воспринимается глазом, может быть опущена. Эта основная идея вот уже три десятилетия движет разработчиками методов сжатия, допускающих некоторую потерю данных.
В общем случае, информацию можно сжать, если в ней присутствует избыточность. В этой книге часто повторялось утверждение, что компрессия информации делается путем удаления или сокращения избыточности данных. При сжатии с потерями мы имеем дело с новой концепцией, с новой парадигмой, которая предполагает сжатие путем удаления несущественной, нерелевантной информации. Изображение можно сжать с потерей, удалив несущественную информацию, даже если в нем нет избыточности.
Отметим, что изображение без избыточности не обязательно является случайным. На стр. 18 обсуждались два типа избыточности, присущей графическим образам. Самой важной из них является корреляция (зависимость) пикселов. В редких случаях корреляция пикселов может быть слабой или вовсе отсутствовать, но изображение все еще не будет случайным и даже осмысленным.
Идея о допустимости потери графической информации станет более приятной, после того, как мы рассмотрим процесс образования цифровых изображений. Вот три примера: (1) реальное изображение может быть сосканировано с фотографии или рисунка и оцифровано (переведено в матрицу пикселов), (2) образ может быть записан видеокамерой, которая сама порождает пикселы и сохраняет их в памяти, (3) картинка может быть нарисована на экране компьютера с помощью специальной компьютерной программы. Во всех трех случаях некоторая информация теряется при переводе в цифровую форму. Зритель готов позволить некоторую потерю информации при условии, что это будет терпимая и малозаметная потеря.
(Оцифровывание изображений состоит из двух этапов: выборки образцов и квантования. Выборка образцов, дискретизация, состоит в разбиении двумерного изображения на маленькие области, пикселы, а под квантованием подразумевается процесс присвоения каждому пикселу некоторого числа, обозначающего его цвет. Заметим, что оцифровывание звука состоит из тех же этапов, но только звуковой поток является одномерным.)
Приведем простой тест на качественное определение потери информации при сжатии изображения. Пусть данный образ A (1) сжат в В, (2) разжат в С, и (3) их разница обозначена D=С-А. Если А был сжат без потери информации и разжат подобающим образом, то С должен быть идентичен А, и образ D должен быть равномерно белым. Чем больше информации потеряно, тем дальше будет D от равномерно белого образа.
Так как же все-таки следует сжимать изображения? До этого момента мы рассматривали три подхода к задаче компрессии: это RLE, статистический метод и словарный метод. Неявно предполагалось, что эти методы применимы к данным любой природы, но из практических наблюдений мы заметили, что лучше всего эти методы работают при сжатии текстов. Поэтому новые методы сжатия должны учитывать три основных различия между текстами и графическими изображениями:
1. Текст одномерен, а изображение имеет размерность 2. Весь текст можно рассматривать как одну длинную строку символов. Каждая буква текста имеет двух соседей, слева и справа. Все соседи весьма слабо коррелированы между собой. Например, в этом абзаце букве «и» предшествуют буквы «н», «р», «л», «с», «п», а за ней следуют буквы «е», «в», «н», «м», «р». В других абзацах та же буква «и» может иметь других соседей. В изображении пиксел имеет четырех непосредственных соседей и восемь ближайших (за исключением пикселов, лежащих на границе, см. рис. 3.1, где восемь ближайших соседей пиксела «*» показаны черным цветом), и между ними существует сильная корреляция.
Рис. 3.1. Четыре ближайших и восемь соседних пикселов.
2. Текст состоит из относительно небольшого числа символов алфавита. Обычно, это 128 кодов ASCII или 256 байтов длины по 8 бит каждый. Наоборот, каждый пиксел изображения представим 24 битами, поэтому может быть до миллионов различных пикселов. Значит, число элементарных «символов» в изображении может быть огромным.
3. Не известен алгоритм, который определял бы, какая часть текста является неважной или малозначимой, и ее можно удалить без ущерба для всего текста, но существуют методы, которые автоматически удаляют неважную информацию из графического образа. Этим достигается значительна степень компрессии.
Таким образом, методы сжатия текстовой информации становятся малоэффективными и неудовлетворительными при работе с изображениями. Поэтому в этой главе будут обсуждаться совершенно другие подходы к решению этой задачи. Они различны, но все они удаляют избыточность с использованием следующего принципа.
Принцип сжатия изображений . Если случайно выбрать пиксел изображения, то с большой вероятностью ближайшие к нему пикселы будут иметь тот же или близкий цвет.
Итак, сжатие изображений основывается на сильной корреляции соседних пикселов. Эта корреляция также называется пространственной избыточностью.
Вот простой пример того, что можно сделать с коррелированными пикселами. Следующая последовательность чисел отражает интенсивность 24 смежных пикселов в одной строке некоторого непрерывно тонового изображения:
12, 17, 14, 19, 21, 26, 23, 29, 41, 38, 31, 44, 46, 57, 53, 50, 60, 58, 55, 54, 52, 51, 56, 60.
Здесь только два пиксела совпадают. Их среднее значение равно 40.3. Вычитание каждого предыдущего символа даст последовательность
12, 5, -3, 5, 2, 5, -3, 6, 12, -3, -7, 13, 2, 11, -4, -3, 10, -2, -3, -1, -2, -1, 5, 4.
Эти последовательности пикселов проиллюстрированы графически на рис. 3.2, который показывает потенциал сжатия: (1) разность пикселов существенно меньше их абсолютных величин. Их среднее равно 2.58. (2) Они повторяются. Имеется только 15 различных значений. В принципе, каждый из них можно закодировать 4 битами. Они декоррелированы, то есть, разности соседних значений, в среднем, не уменьшаются. Это видно из последовательности вторых разностей:
12, -7, -8, 8, -3, 3, -8, 9, 6, -15, -4, 20, -11, 9, -15, -1, 13, -12, -1, 2, -1, -1, 6, 1.
Эти разности уже больше исходных величин.
Рис. 3.2. Величины и разности 24 соседних пикселов.
Рис. 3.3 предлагает другую иллюстрацию «коррелированных величин». Матрица А размером 32x32 заполнена случайными числами, и ее значения на рисунке (а) изображены квадратиками различных серых оттенков. Случайная природа этих элементов очевидна. Затем эту матрицу обратили и результат - матрицу В - изобразили на рисунке (b). На этот раз этот массив квадратиков 32х32 выглядит на глаз более структурированным. Прямое вычисление корреляции с помощью коэффициента Пирсона по формуле (3.1) показывает, что перекрестная корреляция верхних двух строк матрицы А является относительно малым числом 0.0412, в то время, как соответствующая величины, вычисленная для верхних строк матрицы В равна относительно большому числу -0.9831. Дело в том, что каждый элемент матрицы В зависит от всех элементов матрицы А
. (3.1)
Рис. 3.3. Случайная матрица (а) и ее обратная матрица (b).
n=32; a=rand(n); imagesc(a); colormap(gray)
b=inv(a); imagesc(b)
Программа на Matlab для рис. 3.3.
Пример : Воспользуемся специальной программой для иллюстрации ковариационной матрицы для (1) матрицы с коррелированными элементами и (2) матрицы с декоррелированными элементами. На рис. 3.4 показаны две 32х32 матрицы. Первая из них а является случайной (то есть, декоррелированной), а вторая матрица b является обратной для матрицы а (значит, она коррелирована). Их ковариационные матрицы также показаны. Очевидно, что матрица cov(a) близка к диагональной (недиагональные элементы равны нулю или близки к нулю), а матрица cov(b) далека от диагональной. Далее приведена программа для системы Matlab, которая рисует эти картинки.
Рис. 3.4. Ковариация коррелированной и декоррелированной матриц.
Если понятие коррелированных величин стало более ясным, то можно легко ответить на вопрос: «Как проверить стали ли пикселы изображения после некоторого преобразования декоррелированными или нет?» Ответ будет таким: «Если матрица содержит декоррелированные значения, то ковариация любой ее строки с любым столбцом равна нулю». В результате ковариационная матрица М будет диагональной. Статистическое понятия дисперсии, ковариации и корреляции обсуждаются в любом учебнике по статистике.
Принцип сжатия изображений имеет и другую сторону. Нам хорошо известно но опыту, что яркость близких пикселов тоже коррелирована. Два смежных пиксела могут иметь разные цвета. Один может быть близок к красному, а второй к зеленому, однако, если первый был ярким, то его сосед, обычно, тоже будет ярким. Это свойство можно использовать для перевода представления пикселов RGB (red, green, blue) в виде трех других компонентов: яркости и двух хроматических компонентов, определяющих цвет. Одним таким форматом (или пространством цветов) служит YCbCr, где Y (компонента «светимости») отвечает за яркость пиксела, а Сb и Сr определяют его цвет. Этот формат будет обсуждаться в § 3.7.1, но его преимущество уже легко понять. Наш глаз чувствителен к маленьким изменениям яркости, но не цвета. Поэтому потеря информации в компонентах Сb и Сr сжимает образ, внося искажения, которые глаз не замечает. А искажение информации о компоненте Y, наоборот, является более приметной.
a=rand(32); b=inv(a);
figure(l); imagesc(a); colormap(gray); axis square
figure(2); imagesc(b); colormap(gray); axis square
figure(3); imagesc(cov(a)); colormap(gray); axis square
figure(4); imagesc(cov(b)); colormap(gray); axis square
Программа на Matlab для рис. 3.4.
Задание
Тема курсового проекта: Реализация в MATLAB алгоритмов построения фрактальных объектов.
Исходные данные: Журнал Exponenta Pro. Математика в приложениях. №3, 2003 г.
Основные вопросы, подлежащие исследованию:
.Применение рекурсивного алгоритма.
.Применение L-системы и терл - графики.
.Применение системы итерированных функций.
К защите представить: ·пояснительную записку объемом не менее 40 листов:
·теоретическое обоснование;
·листинг программы;
·результаты расчетов.
·электронную версию всех материалов курсового проекта;
·слайды плакатов в Ms Off PowerPoint 2003:
·тема и цель курсового проекта;
·алгоритм решения задачи;
·результаты решения задачи в виде графиков и таблиц;
·экранный вид интерфейса задачи.
Введение 1.1 Ковёр Серпинского 1.1.1 Код программы "Serpinsky.m" 1.1.2 Изображения ковра Серпинского 1.2 Квадратный ковёр Серпинского 1.2.1 Код программы "Serpinsky2.m" 2.2 Изображения ковра Серпинского 3 Кривая Коха 3.1 Код программы "Koch.m" 3.2 Изображения кривой Коха L - системы и терл - графика 1 Снежинка Коха 1.1 Код программы "RuleKoch.m" (возвращает функцию) 1.2 Код программы "Snowflake.m" (вывод изображения) 1.3 Изображение снежинки Коха 2 Дракон Хартера-Хайтвея 2.1 Код программы "Dracon.m" 2.2 Изображение дракона Хартера-Хайтвея 2.3 Изображение кривой Гильберта 2.4 Изображение кривой Госпера 2.5 Изображение кривой Серпинского 3 Ветвление 3.1 Код программы "Flower.m" 3.2 Изображение цветка 3.3 Изображение куста 3.4 Изображение Снежинки Системы итерированных функций 1 Построение ковра Серпинского с помощью ДСИФ 3.1.1 Код программы "SerpDSIF.m" 1.2 Изображение ковра Серпинского построенного при помощи ДСИФ 2 Кристалл построенный по алгоритму РСИФ 2.1 Код программы "Cristal.m" 2.2 Изображение кристалла 2.3 Код программы "Maple.m" 2.4 Изображение Листа 2.5 Код программы "Paporotnic.m" 2.6 Изображение папоротника Заключение Список использованных источников
Введение
Фракталы - математические объекты дробной размерности, название которых было введено в математику Б. Мандельбротом, являются в настоящее время, как предметом самостоятельных математических исследований, так и инструментарием, используемым в целом ряде прикладных задач нелинейной динамики, теории хаоса, обработки сигналов. Однако только относительно недавно появилось первое полноценное учебное пособие по новой быстро развивающейся математической дисциплине, основой которого стал учебный курс, преподававшийся автором книги в течение ряда лет в университете Миссури Колумбия. Так как при изучении фракталов и хаоса большую роль играет компьютерное моделирование, в курсе предусмотрено параллельное изучение теоретических вопросов и проведение компьютерных экспериментов. Это отличает его структуру от традиционной структуры большинства математических курсов: теорема-доказательство-пример-задача. В обобщенном виде подробно описаны известные алгоритмы построения фрактальных объектов (L-системы и терл-графика, аффинные преобразования, системы итерированных функций, случайные системы итерированных функций). Однако соответствующих программ, созданных на каком-либо языке программирования или в математическом пакете, не приводится. В то же время опыт практической реализации алгоритмов построения фрактальных объектов, описанных в каком-либо из современных математических пакетов (MATLAB, Mathcad, Maple, Matematica и т. д.), широко используемых в настоящее время в преподавании целого ряда физико-математических дисциплин, показывает, что существует необходимость внесения в них определенных корректировок, учитывающих особенности выбранного пакета (в первую очередь графические). В курсовой работе отражены алгоритмы построения классических фракталов и их программные реализации в пакете MATLAB. 1. Рекурсивный алгоритм
1 Ковёр Серпинского
Рассматривается алгоритм, основанный на использовании рекурсивной функции. Приведён пример построения простого самоподобного фрактала - ковра Серпинского. В рассматриваемом в данном разделе алгоритме используется способ построения, основанный на последовательном удалении из начальной области внутренних подобластей в соответствии с заданными правилами. Выберем в качестве начального множества S0 равносторонний треугольник вместе с областью, которую он замыкает. Удалим внутренность центральной треугольной области и назовем оставшееся множество S1. Затем повторим описанный процесс для каждого из трех оставшихся треугольников и получим приближение S2. Продолжая, таким образом, получим последовательность вложенных множеств, Sn пересечение которых и образует ковер Серпинского S (рис. 1). Из построения видно, что ковер является объединением N=3 непересекающихся уменьшенных в два раза копий (коэффициенты подобия по горизонтали и вертикали в данном случае оказываются одинаковыми, r = 1/2). Фрактальная размерность ковра Серпинского d равна:
Для построения рассматриваемого фрактала, очевидно, можно использовать следующий алгоритм. Задать порядок ковра N. Задать координаты вершин исходного треугольника ABC: (XA, YA), (XB, YB), (XC, YC).
Построить равносторонний треугольник ABC и залить его синим цветом. 5. Построить треугольник A′B′C′ и залить его красным цветом. Повторить N раз действия, описанные в пп. 4, 5, для треугольников AA′C′, A′BB′, C′B′C, соответственно. Наиболее просто описанный выше алгоритм можно реализовать при использовании рекурсивной процедуры, выполняющей последовательность действий, описанных в пп. 4, 5. Для реализации алгоритма в пакете MATLAB создана специальная функция, возвращающая изображение ковра Серпинского. Для этого использовался встроенный текстовый редактор MATLAB. Код программы приведён ниже. Изображение ковра Серпинского на рисунках 1 - 6.
1.1 Код программы "Serpinsky.m"
% Листинг файла Serpinsky.mz = Serpinsky(Lmax) % функциЯ, возвращающая изображение ковра Серпинского % Lmax - порядок ковра % задание координат вершин равнобедренного треугольника x1=0; y1=0; x2=1; y2=0; x3=0.5; y3=sin(pi/3); h=figure(1); % инициализациЯ графического окнаon; % включение режима рисования фигур в одном графическом окне fill(,,"b"); % прорисовка равностороннего треугольника(gca,"xtick",,"ytick",); % отключение режима оцифровки осей(gca,"XColor","w","YColor","w"); % установка цвета рисования осей Simplex(x1,y1,x2,y2,x3,y3,0,Lmax); % обращение к функции, прорисовывающей равносторонние треугольники % белого цветаoff % отключение режима рисования фигур в одном графическом окне function z=Simplex(x1,y1,x2,y2,x3,y3,n,Lmax) % рекурсивная функция, прорисовывающая равносторонние треугольники % белого цветаn % задание координат вершин текущего равностороннего треугольника dx=(x2-x1)/2; dy=(y3-y1)/2; x1n=x1+dx; y1n=y1; x2n=x1+dx+dx/2;n=y1+dy;x3n=x1+dx/2; y3n=y1+dy;(,,"r");=n+1; % рекурсия(x1,y1,x1n,y1n,x3n,y3n,n,Lmax); Simplex(x1n,y1n,x2,y2,x2n,y2n,n,Lmax);(x3n,y3n,x2n,y2n,x3,y3,n,Lmax); end
1.1.2 Изображения ковра Серпинского
Рисунок 1 - Ковёр Серпинского 0 порядка
Рисунок 2 - Ковёр Серпинского 1 порядка
Рисунок 3 - Ковёр Серпинского 2 порядка
Рисунок 4 - Ковёр Серпинского 3 порядка
Рисунок 5 - Ковёр Серпинского 4 порядка
Рисунок 6 - Ковёр Серпинского 5 порядка
2 Квадратный ковёр Серпинского
Алгоритм визуализации фрактального объекта, основные этапы построения которого представлены на рисунках 7 - 12, реализуется следующей последовательностью действий. .Задать порядок ковра N.
.Задать координаты вершин исходного квадрата ABCD: (XA,YA), (XB, YB) (XC, YC),(XD, YD).
3.Построить квадрат ABCD и залить его синим цветом.
.Вычислить координаты точек, делящих стороны квадрата ABCD на три равные части: dx=(XB-XA)/3, dy=(YB-YA)/3, XA=XA+dx, YA=YA+dy, XB=XA+dx+dx, YB=YA+dy, XC=XA+dx+dx, YC=YA+dy+dy, XD=XA+dx, YD=YA+dy+dy.
.Построить квадрат A′B′C′D′ и залить его белым цветом.
.Повторить N раз действия, описанные в пп. 4, 5, для квадратов с вершинами, имеющими следующие координаты:
(XA,YA), (XA,YA), (XA,YA), (XA,YA),
(XA,YA), (XB,YA), (XB,YB), (XA,YB),
(XB,YA), (XB,YB), (XB,YB), (XB,YB),
(XB,YB), (XB,YB), (XB,YC), (XC,YC),
(XC,YC), (XB,YC), (XC,YC), (XC,YC),
(XD,YD), (XC,YC), (XC,YC), (XD,YC),
(XA,YD), (XD,YD), (XD,YC), (XD,YD),
(XA,YA), (XA,YD), (XD,Y