Сжатие изображений с помощью фракталов и всплесков

Малыгин, Ярослав Владимирович

Сжатие изображений с помощью фракталов и всплесков тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Малыгин, Ярослав Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Екатеринбург МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Сжатие изображений с помощью фракталов и всплесков»

Автореферат диссертации на тему "Сжатие изображений с помощью фракталов и всплесков"

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

Малыгин Ярослав Владимирович

Сжатие изображений с помощью фракталов и всплесков

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург-2004

Работа выполнена в Институте математики и механики УрО РАН, в отделе теории и приближения функции

Научный руководитель: доктор физико-математических наук,

профессор, член-корреспондент РАН Бердышев В.И.

Официальные оппоненты: доктор физико-математических наук,

профессор Черных Н.И., кандидат физико-математических наук Ваганова Н.А

Ведущая организация: Уральский государственный

университет

Защита состоится июня 2004 г. в на заседании диссер-

тационного совета К.004.006.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ГСП-384, ул. С.Ковалевской 16.

С диссертацией можно ознакомиться в научной библиотеке ИММ УрО РАН.

Автореферат разослан мая 2004 г.

Ученый секретарь

диссертационного совета К.004.006.01 к.ф.-м.н., ст.н.с. /РлА

Скарин В.Д.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Современные информационные технологии предполагают передачу и хранение больших объемов данных. Значительную часть передаваемых данных составляют графические изображения и видеоинформация. В связи с этим важную роль играют методы сжатия (т.е. компактного описания) графических изображений. Под монохромным графическим изображением будем понимать матрицу целых чисел X = {z»j}"7iom~1>a;«i = 0| -ч 2Ь — 1. Каждый элемент матрицы X определяет интенсивность свечения графического элемента (пиксела). Нулевое значение элемента соответствует чёрному цвету, а значение (2Ь — 1) — белому. Параметр Ь называется глубиной цвета и определяет количество информации, необходимое для хранения значения одного элемента. Таким образом, для хранения всего изображения X необходимо т-п-Ь бит памяти.

Если b = 1, такое изображение называется бинарным, т.е. в нём могут быть графические элементы только чёрного и белого цвета. Бинарное изображение также можно представить как характеристическую функцию компактного множества из R2.

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

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

Различают два вида сжатия: сжатие без потерь и сжатие с потерями. Сжатие с потерями предполагает потерю части информации при сжатии и последующем восстановлении. Использование методов сжатия с потерями ограничивается объектами, где такие потери допустимы (обработка графической, звуковой информации и т.д.). Для оценки качества восстановления используют величину PSNR (peak signal-to-noise ratio, предельное отношение сигнал-шум), измеряемую в дБ:

n-l,m—1

KPSNr(X,Y) = -10 lg

.Sq (хц-Уч)2

n-rn- (2Ь — I)2 'дБ''

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

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

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

Цель работы

Целью представленной диссертационной работы является:

1. Оценить существующие алгоритмы сжатия графических изображений, в том числе, алгоритмы фрактального сжатия.

2. Разработать методы ускорения процедур фрактального сжатия монохромных изображений.

3. Улучшить аппроксимативные свойства алгоритма фрактального сжатия монохромных и бинарных изображений

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

Научная новизна работы

В данной работе впервые предложено использовать:

♦ - параметр нормализованной размерности для предварительной классификации фрагментов изображения; это позволяет ускорить процесс нахождения параметров фрактального сжатия.

♦ преобразование Мерсенна для ускорения процесса фрактального сжатия.

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

Апробация работы Основные результаты диссертации докладывались на:

Молодежной конференции "Проблемы теоретической и прикладной математики". Екатеринбург: УрО РАН, 1997. 1999, 2000,г.

Школе-конференции им. С.Б.Стечкина по теории приближения функции, Миасс, 1998, 1999, 2000, 2003г.

Сессиях молодых ученых ИММ УрО РАН

Расширенном семинаре "Параллельные вычисления" ИММ УрО РАН.

Структура и объем диссертации

Диссертация состоит из пяти глав основного текста и заключения, в котором перечислены основные полученные результаты. Объем диссертации составляет 73 страницы. Библиография включает 38 наименований. Диссертация содержит 23 рисунка и 3 таблицы.

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

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

Во второй главе изложены основные сведения о фрактальном методе сжатия изображений.

В разделе 2.1 приведены основные понятия и определения. В соответствии с теоремой Банаха о неподвижном элементе сжимающего оператора в полном метрическом пространстве, если для элемента г удастся найти сжимающий оператор Т такой, что Т(г) = г, то г может быть восстановлен с произвольной наперед заданной точностью. Восстановление осуществляется с помощью итерационной последовательности - произвольно выбранный начальный элемент. Используя неравенство Барнсли [1]

- коэффициент сжатия оператора Т,

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

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

Ег -- min p(z,T(z)).

В разделе 2.2 изложены основные принципы аппроксимации множеств. Пусть пространство Z = {М С Е2,Л/ — компакт}. Идея фрактальной аппроксимации множества М (Дж. Хатчинсон, [4]) заключается в использовании оператора Т, который действует на Z и задается соотношением:

T(M) = JjT,(M),

где Ti - аффинный сжимающий оператор, Z Z.

Обозначим Мт - инвариант для оператора Т, т.е. Мт — Т(Мт)-Набор {Т,}^! называют системой итерируемых функций (IFS) [1].

Задача аппроксимации инвариантом Мт бинарного изображения, заданного множеством JI/, состоит в нахождении оператора Т, т.е. параметров соответствующей IFS гарантирующего задан-

ную погрешность е: h(M,T(M)) < е, где h - расстояние по Хаус-дорфу.

В разделе 2.3 рассмотрено фрактальное представление монохромных изображений.

На основе понятия IFS A. Jacquin предложил метод фрактального сжатия монохромных изображений [5]. Под монохромным изображением в данном случае понимается ограниченная функция яркости /(х), которая задана на компактном множестве X С R2 с мерой

ц,Х -4 К, / G L2 = L2(X,{i).

Для построения оператора Т, действующего в Ьг (А", ц) требуются следующие составляющие:

1. Набор компактных множеств {Ä«}^,1,^ С X, такой, что:

«=о

2. Набор компактных множеств {Dj}^, Di С X, такой что для

UJti

любых Ri и Dj существует сжимающий оператор w^ : X —* X, имеющий обратное отображение причем wy(üj) = Ri.

3. Набор сжимающих операторов {у«}?^1»® ^ Обычно полагают, что <Pi(t) — cut + bi.

Множества Ri называются регионами (regions), а Dj —доменами (domains).

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

min iWH^iDj)) -Vi(/(A))||}, i = 0.....П - 1.

Произвольной функции / = f(x), (x G X) оператор T сопоставляет функцию Tf, задаваемую на каждом Ri, i = 0,...,n — 1 соотношением:

(Т/)(*) = ^/Ц^(*))),хеД<.

Номер t определяется по x, так как х е Ri, и для преобразования Т используются <fii и Ui с соответствующим индексом г.

Заранее выбранные наборы {ßi}"^1, {^j}j=o>а также вид операторов {v«}?^!)1 и определяют пространство поиска параметров фрактального сжатия.

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

е« = тшхшп^ДиГ.1^) - <^(/(Р;)||Ь » = 0,- 1.

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

В разделе 2.4 рассмотрен пример численного алгоритма фрактального сжатия монохромного изображения.

Для приложений, связанных с вычислительной техникой, удобно представлять графические изображения в виде матрицы.' * = KiKjir-1. х^-=0,...,2>-1.

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

Rk = {rfjJ^lo, rfj = xi+kivtj+kjv, где к = (kltk2),

V - размер регионов. Таким образом, данные регионы без пересечений покрывают все изображение X. На У строим набор домен, которые также являются квадратными фрагментами:

Фрактальное сжатие состоит в нахождении для каждого региона Ик наиболее подходящего домена Лг в смысле

Здесь 5 — контрастность, о — яркость. Оба эти параметра согласуют значения яркости различных фрагментов изображения. Вместо описания графического изображения как матрицы X надо запомнить для каждого региона номер наиболее подходящего для него домена / и параметры такой похожести (коэффициенты 5 и о). Методом наименьших квадратов для фиксированных I и к можно найти параметры ^ и о, при которых величина

достигает минимума.

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

В разделе 3.1 описан метод повышения быстродействия на основе предварительной классификации фрагментов изображения. Это позволяет для каждого региона проводить поиск, т.е. решать задачу оптимизации только среди домен, близких в смысле этой классификации к региону Я*. Удачно подобранный признак классификации позволяет значительно сократить объем требуемых вычислений, почти не увеличивая погрешность. Таким критерием может быть, например, пространственная близость региона и домена: поиск осуществляется лишь среди тех домен, которые расположены недалеко от данного региона.

Другой критерий, основанный на разделении всех фрагментов изображения на "гладкие", "шероховатые" и с "выраженной границей перепада значений", используется в работах Фишера, Якобса и Босса [2].

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

h — lim

log Ne

e->0 log 1/e'

где Ne — наименьшее число шаров радиуса Е, необходимых для покрытия поверхности. Чем больше h , тем "шероховатость" выше.

Для предварительной (т.е. до определения s и о) классификации фрагментов изображения предлагается использовать следующую нормализацию фрагментов функции:

G(4)^

def dlij-Dl

max с#,- — mind'-,-' D, 11 D,

где — средняя величина функции на фрагменте Д. При этом предполагается, что тах ф тш . Такая процедура нормализации гарантирует вьшолнение равенства

С(4) = С(з • + о) Чз,о.

В качестве признака классификации фрагментов выберем такую "нормализованную" размерность = б £>/, кото-

рая также не будет зависеть от коэффициентов в, о.

Таким образом, поиск пар регион-домен будет проводится в два этапа:

1. Нахождение и запоминание "нормализованных" размерностей д для всех рассматриваемых регионов {Я*} и домен {Д};

2. Для каждого региона Я* определяется множество домен Ю* С

на котором будет осуществляться поиск наилучшего

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

В таблице приведены результаты работы данного алгоритма на стандартном тестовом изображении Lenna.

Количество сматриваемых V распар Время счета (сек) Качество восстановления

1 млн. 17 26.07

2 млн. 25 26.43

4 млн. 40 26.59

В разделе 3.2 предложен метод повышения быстродействия с использованием преобразования Мерсенна. Попарное сравнение К регионов и X домен заключается в вычислении параметров в и о и погрешности £1к• При этом основная вычислительная сложность приходится на вычисление Ь • К выражений типа

Выражение вида

УМ,4- -

называется корреляцией (см. [10]). Для его быстрого вычисления можно использовать ^точечное дискретное преобразование Фурье. Однако преобразования Фурье для подобных вычислений оказывается неэффективным по следующим причинам:

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

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

Имеет смысл заменить преобразование Фурье неким другим преобразованием, которое было бы пригодно для аналогичного вычисления корреляций и, одновременно, лишено перечисленных недостатков, т.е. чтобы вычисления проводились в целых числах. Такими свойствами обладает, например, преобразование Мерсенна [10], особенностью которого является работа в модулярной арифметике. Одномерное р-точечное преобразование Мерсенна записывается в виде:

(р-1 I р~1

&}Рк=о = М ({х.ИГо1) = <| $>2"= mod (2" -1)1 , (1)

1»=о ) к=о

где р — простое число. Числа вида 2р '—1 ,{р~ простое),' называются числами Мерсенна.

Циклическая корреляция [10] представляется следующим образом

(£ »(*+!) (mod p)Xi] = М-1 (М-1 ({у,}) • М ({*<})) • р"1 ,

при условии, что значения получаемых отсчетов не превосходят величины

Для сравнения объема требуемых вычислений непосредственным счетом и с помощью преобразования Мерсенна автором настоящей работы были составлены соответствующие программы на ассемблере (TASM с опцией р486) и определено количество тактов процессора i486, требуемых для вычисления двумерной циклической корреляции обоими способами.

Метод с использованием преобразования Мерсенна требует ¿mersenn ^ 44р3 + 107р2 тактов для вычисления, а прямой счет 'direct ~ (40т2 + Ют) • р2 тактов, где т — линейный размер фрагмента изображения. Линейный размер т, длина преобразования р и глубина цвета Ь связаны между собой соотношением: Iogj m < р/2~Ь,

полученным из условия

52 (mod p)(fci+«s) (mod < 2P - 1,

Для типовых значений4 i» = 8, р = 23ит = 8 преобразование Мерсенна дает выигрыш примерно в 2.36 раза при получении точно таких же результатов, что и непосредственным вычислением.

В разделе 3.3 дается описание алгоритма вычисления параметров фрактального сжатия для многопроцессорной вычислительной техники. Многопроцессорный вычислительный комплекс представляет собой множество связанных между собой процессоров (устройств обработки информации). Схему аппаратной связи узлов друг с другом удобно представить в виде неориентированного графа, в котором вычислительные узлы Vi представляются в виде вершин, а связи между ними — в виде дуг. Если узлы не являются ближайшими соседями, то они все равно могут обмениваться сообщениями, передавая их "по цепочке" из непосредственно связанных между собой вычислительных узлов. Передача данных между узлами — относительно медленный процесс, по сравнению с самими вычислениями. Этот процесс протекает быстрее, если информацией обмениваются узлы, являющиеся непосредственными соседями.

Для оценки эффективности работы алгоритма на многопроцессорном комплексе используется коэффициент распараллеливания

где ti — время счёта задачи на одном узле (т.е. без распараллеливания), п — количество узлов, in — время счёта задачи на п узлах.

Распараллеливание считается идеальным, если iin(rt) и 1 при достаточно большом п.

Поиск наилучшего домена для каждого региона выполняется независимо, что упрощает распараллеливание алгоритма: один регион (или набор регионов) обрабатывется на отдельном узле вычислительного комплекса. Один из узлов назначим ведущим: он будет

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

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

Такой алгоритм требует большего количества обменов между узлами, что снижает производительность.

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

Через c¿J• обозначим расстояние между узлами ^ и V].

Назовем вершину Ук центром графа, если шахе*,- = тштахс;,-.

) « з

"Развернем" данный граф в дерево, отбросив все дуги, кроме тех, которые образуют кратчайшие пути от центра графа до остальных вершин. Центр графа назначим ведущим узлом.

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

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

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

В соответствии с данным параллельным алгоритмом фрактального сжатия изображений была разработана программа для многопроцессорного вычислительного комплекса MVS-100.

В четвертой главе обсуждается применение всплесков в задаче фрактального сжатия. Теория всплесков родилась в середине 1980-х годов. Её возникновение и развитие связано с именем Ж.Морлета, Я.Мейера, С.Малла, И.Добеши и др. [9]. При дискретном всплеск-преобразовании функция представляется в виде

Это представление основано на понятии "кратномасштабная аппроксимация" ("multiresolution approximation").

В разделе 4.1 дается понятие кратномасштабной аппроксимации. Обычно коэффициенты всплеск-преобразования изображаются в виде бинарного дерева.

Коэффициенты группируются по блокам (поддеревьям) Bij. Т.е. можно определить блок коэффициентов

Определим расстояние между блоками всплеск-коэффициентов:

£ ауФ(<М - ft), cujj 6 R

P2(Bkrlj},Bk„h) = = 2~к/2 0 2-р/2 • £i=o (b*i+p,jV2»+i - bk2+p,jа-гя+j)2,

где к = max(fci,A;2).

В разделе 4.2 дается описание всплеск-фрактального преобразования.

Будем обозначать поэлементное умножение на А € Я всех коэффициентов блока Вк] как Л •

Зафиксируем некоторый уровень бинарного дерева к. Назовём блоки Вы, г = 0,2* — 1 регионами, а блоки Вк-и, i = 0,1 — 1 — доменами.

Каждому региону Вы некоторым образом сопоставим домен В к-г,/.- и множитель |А*|. На основе дерева коэффициентов исходного всплеск-преобразования построим новое следующим образом: верхние коэффициенты до уровня к оставим без изменения, а блоки Вы, I = 0,2'-1 заменим на \Bk-ij,-

Построенное таким образом новое дерево коэффициентов обозначим как На основе описанной процедуры из ^ построим р2, затем из Р2 и т.д. Таким образом, мы определили оператор

Т : ^ В [7] показано, что при | А* |< оператор Г будет

сжимающим.

Для минимизации величины р(Еа,Р*) где Р* = T(F*) будем минимизировать р{Р0,Т(Ро)). Для каждого региона Вы, г = 0,2* - 1 будем искать наилучший домен

Зг = а^ тт. ттр(Вн,А •

;=0,2к_1-1 А

Величина тт/>(В]к,А - находится при помощи метода.

наименьших квадратов. Для такого всплеск-фрактального представления достаточно запомнить "верхние этажи" пирамиды до уровня к — 1 и 2к пар коэффициентов А{). При восстановлении дерево коэффициентов Р* будет достраиваться сверху вниз, начиная с уровня к.

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

1. Для всех регионов найти наилучшие домены и величины ошибок е{.

2. Найти регион с самой большой ошибкой £,» = шахе,.

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

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

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

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

В пятой главе предлагается метод нахождения параметров IFS. Данный метод состоит из двух этапов: предварительного и уточняющего. На предварительном этапе необходимо найти "не самые плохие" начальные коэффициенты IFS, которые можно было бы уточнить на следующем этапе. Основной целью предварительного этапа является выделение на исходном множестве M областей, за аппроксимацию которых будет "отвечать" соответствующий оператор Ti.

Для этого предлагается следующий алгоритм:

1. На M построим последовательность итерационно наиболее удаленных друг от друга точек (ИУТ) {г,}"=1 следующим образом:

XI,х2 G M : р(х 1,х2) = max р{х,у) х,у ем

xt = ar</maxmin^(x,,a;),i = 3,...,n,

iÇAf j<«

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

2. Произведем разбиение множества M на подмножества Р, С М,г = 1 т.е. Р, = fx € M : p[xt,x) < min p(z,,i)}. Эти

1=1, ..,N

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

3. Для того, чтобы аффинное преобразование Tî соответствовало конкретному подмножеству Pi, определим коэффициенты этого преобразования так, чтобы расстояние Хаусдорфа между множествами Ti(M) и Pi было не очень большим. С этой целью для каждого Pi находим три итерационно удаленные точки Коэффициенты выбираем так, чтобы {у}}3=1 являлись образами первых трех ИУТ

всего множества М. Из возможных 6 вариантов наложения одной тройки точек на другую выбираем тот, при котором ошибка h(Ti(M),Pi)) наименьшая.

4. Из найденного набора IFS выберем преобразование Tj. с самой большой ошибкой и построим новое подмножество

р,. = {х е M : p(x,Ti.(M)) < ад Ар(х, (J ТДМ)) > 52(е),

iïï

где е = h(M,T(M)). Величина ¿i(e) определяет насколько сильно будет отклоняться новое Pi- от старого Ti-(M), а <Ь(е) регулирует вхождение в новое Р,тех точек, которые будут аппроксимироваться за счет остальных Tj. Эти величины выбираются экспериментально.

Этап уточнения подробно описан в [8]. Обозначим F(T) = h(M,T(M)). Будем говорить, что AT задает направление спуска, если при всех достаточно малых Л > 0 выполняется неравенство F(T + ДАТ) < F(T). Можно указать условия, когда AT в точке Т задает направление спуска. Задача нахождения этого направления спуска сводится к задаче выпуклого программирования.

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

Основные результаты

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

2. Предложено использование быстрого вычисления корреляции с помощью преобразования Мерсенна для повышения быстродействия фрактального сжатия изображений.

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

4. Предложена модификация всплеск-фрактального метода сжатия изображений. Модификация заключается в разбиении дерева коэффициентов всплеск-преобразования на регионы в зависимости от конкретного изображения.

5. Предложен метод предварительного нахождения параметров IFS для описания бинарных изображений.

Список работ по теме диссертации

1. V.I. Berdyshev, S.V. Berdyshev, V.P. Kondrat'ev, V.B. Kostousov, Ya V. Malygin. On compression and modelling of images // Russian Journal of Numerical Analysis and Mathematical Modelling. Vol. 11, № 4, 1996, p. 275-285.

2. Ya. V. Malygin. Two Methods for Fast Fractal Compression of Images // Pattern recognition and Image Analysis. Vol. 9, JV 3, 1999, p. 448-452.

3. Малыгин Я.В. Всплеск-фрактальное сжатие с адаптивными размерами регионов // Проблемы теоретической и прикладной математики: Труды 32-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2001, С. 37-39.

4. Малыгин Я.В. Поиск параметров IFS для бинарного изображения // Проблемы теоретической и прикладной математики: Труды 33-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2002, С. 71-73.

5. Малыгин Я.В. Параллельный алгоритм фрактального сжатия графических изображений большого размера // Проблемы теоретической и прикладной математики: Труды 34-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 276-278.

Результаты автора по этой теме также были использованы в монографии Бердышев В.И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 297 с.

Список литературы

[1] M.Barnsley. Fractals Everywhere. Boston: Academic Press, 1988.

[2] Y.Fisher, B.Jacobs, R.Boss. Iterated Transform Image Compression // NOSC Technical Report 1408. San Diego: Naval Ocean Systems Center (CA), April 1991, p. 1-27.

[3] Y.Fisher. A discussion of fractal image compression // Chaos and Fractals: New Frontiers of Science /H.-O.Peitgen, H.Jurgens, and D.Saupe, eds. New York: Springer-Verlag, 1992. p. 903-919.

[4] J. Hutchinson. Fractals and Self-Similarity // Indiana University Mathematics Journal. Vol. 30, № 5,, 1981, p. 713-747.

[5] A. Jacquin, Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations // IEEE Transactions on Image Processing. Vol. 1, № 1 January 1992, p. 18-30.

[6] B.Mandelbrot. The fractal Geometry of Nature. W.H. Freemam & Co, second edition, 1983.

[7] E.Vrscay. A Generalized Class of Fractal-Wavelet Transforms for Image Representation and Compression // Canadian Journal of Electrical and Computer Engineering, January 1998.

[8] Бердышев В.И., Петрак Л.В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 297 с.

[9] Добеши И. Десять лекций по вейвелетам. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001. 464 с.

[10] Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985. 248 с.

Малыгин Ярослав Владимирович

Сжатие изображений с помощью фракталов и всплесков

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 07.06.2004 г. Формат бумаги 60 х 84 1/г« Объем 1,2 уч.-изд. л. Тираж 100 экз.

Отпечатано в Государственном целевом фонде высшей школы Свердловской области, г. Екатеринбург пр. Космонавтов 18 ь.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Малыгин, Ярослав Владимирович

1 Введение

2 Фракталы

2.1 Основные понятия и определения.

2.2 Аппроксимация множеств.

2.3 Фрактальное представление монохромных изображений.

2.4 Численный алгоритм фрактального сжатия монохромного изображения.

3 Методы повышения быстродействия фрактального сжатия

3.1 Предварительная классификация фрагментов изображения.

3.2 Использование преобразования Мерсенна.

3.3 Использование многопроцессорной вычислительной техники.

4 Применение всплесков в задаче фрактального сжатия

4.1 Кратномасштабный анализ

4.2 Всплеск-фрактальное преобразование.

4.3 Модифицированный метод всплескфрактального сжатия.

5 Поиск параметров IFS для бинарных изображений

Введение диссертация по математике, на тему "Сжатие изображений с помощью фракталов и всплесков"

Актуальность темы

Современные информационные технологии предполагают передачу и хранение больших объемов данных. Значительную часть передаваемых данных составляют графические изображения и видеоинформация. В связи с этим важную роль играют методы сжатия (т.е. компактного описания) графических изображений. Под монохромным графическим изображением будем понимать матрицу целых чисел X = о"-1, Xij = 0,2Ь — 1. Каждый элемент матрицы X определяет интенсивность свечения графического элемента (пиксела). Нулевое значение элемента соответствует чёрному цвету, а значение (2Ь — 1) — белому. Параметр 6 называется глубиной цвета и определяет количество информации, необходимое для хранения значения одного элемента. Таким образом, для хранения всего изображения X необходимо т • п • Ь бит памяти.

Если 6 = 1, такое изображение называется бинарным, т.е. в нём могут быть графические элементы только чёрного и белого цвета. Бинарное изображение также можно представить как характеристическую функцию компактного множества из R2.

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

Как видно из названия, сжатие с потерями предполагает потерю части информации при сжатии и последующем восстановлении. Использование методов сжатия с потерями ограничивается объектами, где такие потери допустимы (обработка графической, звуковой информации и т.д.). Для оценки качества восстановления используют величину PSNR (peak signal-to-noise ratio, предельное отношение сигнал-шум), измеряемую в дБ: п—1,171 — 1

Е (хч - va)2 kpsnr(x,y) = -ioig [ДВ], (i.i) где X и Y - соответственно исходное и восстановленное изображения. Качество восстановления, как правило, находится в обратной зависимости от коэффициента сжатия. Т.е. коэффициент сжатия ограничен требуемым качеством восстановления, и его значение может достигать сотни и более. В данной работе рассматриваются лишь методы сжатия с потерями.

В настоящее время для сжатия численной информации используют методы аппроксимации функций полиномами [37], рациональными дробями [5], экспонентами [32], сплайнами [26], всплесками. Одним из самых распространенных алгоритмов сжатия с потерями фотогорафических изображений является JPEG (Joint Photographie Expert Group - объединенная группа экспертов по фотографии). Этот алгоритм [31] основан на разбиении исходного изображения на фрагменты размером 8x8 пикселов. Для каждого фрагмента выполняется двумерное дискретное косинус-преобразование (ДКП) [1]. Далее происходит квантование по уровню спектра ДКП, что и определяет потери при сжатии. Коэффициенты квантования определяют, какое количество данных теряется и, следовательно, коэффициент сжатия и качество восстановленного изображения. Для получения окончательного результата выходные данные квантования без потерь упаковываются с использованием какого-либо статистического метода кодирования. Таким методом может быть арифметическое кодирования, либо кодирования по методу Хаффмана [8], [20].

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

Самое общее понятие фрактала можно дать следующим образом: это такой объект, который при сколь угодно большом увеличении (рассмотрении все меньших фрагментов) сохраняет неизменной степень своей детализации (визуальной сложности). Классический пример фрактала — береговая линия. Если выбрать некоторый участок берегового контура, например, на карте с мелким масштабом, а затем увеличивать этот участок (использовать карты со все более крупным масштабом), то можно увидеть, как появляются все новые и новые детали. При больших увеличениях географических карт будет недостаточно, и придется воспользоваться фотографиями. Камни и песок, составляющие береговую линию, издали кажутся гладкими, но пр дальнейшем увеличении и они будут состоять из различных "шероховатостей". Ни при каком увеличении не будет наблюдаться тенденции к сглаживанию береговой линии. Фрактальные методы сжатия основаны на предположении Б. Мандельброта о глобальной "самопохожести" (масштабной инвариантности) многих естественных объектов [17]. Это означает, что различные части объекта оказываются похожими друг на друга или на весь объект в целом.

Цель работы

Целью представленной диссертационной работы является:

2. Разработать методы ускорения процедур фрактального сжатия монохромных изображений.

3. Улучшить аппроксимативные свойства алгоритма фрактального сжатия монохромных и бинарных изображений

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

Научная новизна работы

В данной работе впервые предложено использовать:

• параметр нормализованной размерности для предварительной классификации фрагментов изображения; это позволяет ускорить процесс нахождения параметров фрактального сжатия.

• преобразование Мерсенна для ускорения процесса фрактального сжатия.

Апробация работы Основные результаты диссертации докладывались на:

Молодежной конференции "Проблемы теоретической и прикладной математики". Екатеринбург: УрО РАН, 1997, 1999, 2000г.

Школе-конференции им. С.Б.Стечкина по теории приближения функции, Миасс, 1998, 1999, 2000, 2003г.

Сессиях молодых ученых ИММ УрО РАН.

Расширенном семинаре "Параллельные вычисления"ИММ УрО

Исследования, проведенные по теме диссертации, поддержаны грантами РФФИ №96-01-00121, №99-01-00460 и №02-01-00782, а также грантом "Ведущие научные школы РФФИ" №00-15-96035.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав основного текста и заключения, в котором перечислены основные полученные результаты. Объем диссертации составляет 73 страницы. Библиография включает 38 наименований. Диссертация содержит 23 рисунка и 3 таблицы.

Заключение диссертации по теме "Вычислительная математика"

6 Заключение

В процессе работы над темой диссертации были получены следующие результаты:

5. Предложен метод предварительного нахождения параметров IFS для описания бинарных изображений.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Малыгин, Ярослав Владимирович, Екатеринбург

1. Ahmed N., Natarajan T., Rao K. Discrete Cosine Transform // IEEE, Trans. Computers. 1974. Vol. C-23. P.90-93.

2. Barnsley M. Fractals Everywhere. Boston: Acad. Press, 1988. 396p.

3. Beaumont J.M. Advanced in Block Based Fractal Coding of still Pictures // Proc. of IEEE Colloquium: The Application of Fractal Techniques in Image Processing, 1990 , P. 3.1-3.6.

4. On compression and modelling of images /V.I. Berdyshev, S.V. Berdyshev, V.P. Rondrat'ev, V.B. Kostousov, Ya.V. Malygin// Russ. J. Numer. Anal, and Math. Modelling. 1996. Vol. 11, N 4, P. 275-285.

5. Cheney E.W. Introduction to approximation theory. New York: McGraw-Hill, 1966. 259p.

6. Fisher Y., Jacobs B., Boss R. Iterated Transform Image Compression// NOSC Techn. Report 1408. San Diego: Naval Ocean Systems Center (CA). April 1991. P. 1-27.

7. Fisher Y. A discussion of fractal image compression // Chaos and Fractals: New Frontiers of Science /H.-O. Peitgen, H. Jurgens, and D. Saupe, eds. New York: Springer-Verlag, 1992, P. 903-919.

8. Gersho A., Gray R. Vector Quantization and Signal Compression. Boston, MA.: Kluwer, 1992.

9. Hutchinson J. Fractals and Self-Similarity // Indiana Univ. Math. J. 1981. Vol. 30, N 5. P. 713-747.

10. Jacobs B., Boss R., Fisher Y. Image Compression: A Study of the Iterated Transform Method// Signal Processing. 1992. Vol. 29. p. 251263.

11. Jacquin A. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations // IEEE Trans. Image Processing. 1992. Vol. 1, N 1. P. 18-30.

12. Kominek J. Convergence of fractal encoded images. Proc. DCC'95 Data Compression Conf.// IEEE Computer Society Press, March 1995.

13. Krupnik H., Malah D., Karnin E. Fractal representation of image via the discrete wavelet transform // IEEE 18-th Convention of Electrical Engineering in Israel, Tel-Aviv, March 1995.

14. Mallat S.G. A Theory for Multiresolution Signal Decomposition: The Wavelet Representation // IEEE Trans. PAMI. 1989. Vol. 5. P. 565-568.

15. Mallat S.G. Multifrequency channel decompositions of images and wavelet models // IEEE Trns. Acoust., Speech, Signal Processing. 1989. Vol. 33, Dec. P. 2099-2110,

16. Malygin Ya.V. Two Methods for Fast Fractal Compression of Images // Pattern Recognition and Image Anal. 1999. Vol. 9, N. 3, P. 448452.

17. Mandelbrot B. The Fractal Geometry of Nature. San Francisco (Calif.) :W.H. Freemam and Co, 1982. 460p.

18. Saupe D., Hamzaoui R. Complexity reduction methods for fractal image compression // Conf. Proc. on Image Processing: Math. Methods and Appl. Sept. 1994. Oxford: Oxford Univ. Press, 1994,

19. Stein M. Fractal image models and objects detection // SPIE Vol. 845. VCIP II. 1987, P. 293-300.

20. Nelson M., Gailly J. The Data Compression Book. New York: MAT Books, 1995.

21. Sweldens W. The Lifting Scheme: a Custom-design Construction of Biorthogonal Wavelets // Appl. Comput. Harmon. Anal. 1996. Vol. 3 N 2. p. 186-200.

22. Tricot C. Curves and Fractal Dimension. New York: SpringerVerlag, 1995.

23. Sweldens W. Bilding your own wavelts at home: Techn. Report 1995:5: Industrial Math. Initiative / Dep. of Math., Univ. South California, 1995.

24. Vrscay E. A Generalized Class of Fractal-Wavelet Transforms for Image Representation and Compression // Canadian J. Electrical and Computer Eng. 1998.

25. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 297с.

26. Бердышев В.И., Субботин Ю.Н. Численные методы приближения функций. Свердловск: Ср.-Урал. кн. изд-во, 1979. 120с.

27. Бродин В.Б., Шагурин И.И. Микропроцессор i486. Архитектура, программирование, интерфейс. М.: Диалог-МИФИ, 1993. 240с.

28. Васильев Ф.П. Численные методы решения экстремальных заг дач: Учеб. пособие для вузов. М.: Наука, 1988. 549с.

29. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608с.

30. Добеши И. Десять лекций по вейвелетам. Ижевск: НИЦ "Регу-ляр. и хаотич. динамика", 2001. 164с.

31. Климов A.C. Форматы графических файлов: Киев: НИПФ "ДиаСофт Лтд." 1995. 480с.

32. Ланцош К. Практические методы прикладного анализа. М.: Физматгиз, 1961. 524с.

33. Малыгин Я.В. Поиск параметров IFS для бинарного изображения // Проблемы теорет. и прикл. математики: Тр. 33-й Регион, молодеж. конф. Екатеринбург: УрО РАН, 2002. С. 71-73.

34. Малыгин Я.В. Параллельный алгоритм фрактального сжатия графических изображений большого размера // Проблемы теорет. и прикл. математики: Тр. 34-й Регион, молодеж. конф. Екатеринбург: УрО РАН, 2003. С. 276-278.

35. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985. 248с.

36. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. 478с.

37. Ремез. Е.Я. Основы численных методов чебышевского приближения. Киев: Наук, думка, 1969. 624с.

38. Чуй К. Введение в вэйвлеты: Пер. с англ. М.: Мир, 2001. 413с.