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

004615380

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

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

Окунев Вадим Вячеславович

МЕТОДЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ

Специальность 05.13.01 — Системный анализ, управление и обработка информации (в технических системах)

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

-2 ЛЕК 2010

Санкт-Петербург 2010

004615380

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

Научный доктор технических наук

руководитель: Потапов Алексей Сергеевич

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

оппоненты: Тропченко Александр Ювеиальевич (СПбГУ ИТМО)

кандидат технических наук

Федоренко Сергей Игоревич (ООО «Рекогнишн Фокус»)

Ведущая Санкт-Петербургский институт

организация: информатики и автоматизации РАН

Защита состоится 21 декабря 2010 года в 15 часов 00 минут на заседании диссертационного совета Д 212.227.03 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО. Автореферат размещён на сайте www. ifmo. ru

Автореферат разослан « » hOSiJnn__2010 г.

И. о. учёного секретаря д. т. н., проф.

диссертационного совета Д 212.227.03

Коняхин Игорь Алексеевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

К мультимедийной информации чаще всего применяется сжатие с потерями. Справедливость такого применения обусловлена тем фактом, что для ■мультимедийных объектов, как правило, можно отказаться от хранения каких-либо их особенностей (например, мелких детачей на изображении, либо не воспринимаемых человеческим ухом звуковых частот в аудиозаписи) в пользу увеличения степени компрессии. В действительности, существуют распространённые алгоритмы компрессии без потерь и для мультимедийных объектов, такие как FLAC для звуковых файлов или PNG для цифровых изображений. Однако такие форматы проектировались как универсальные для своего типа данных и, как следствие, оказались неспособными учитывать особенности конкретного сжимаемого файла, что в результате привело к существенному проигрышу в степени сжатия по сравнению с аналогичными алгоритмами компрессии с потерями.

Алгоритмы сжатия с потерями обычно в какой-то мере учитывают особенности типа сжимаемых данных, но этот учёт весьма ограниченный. В то же время, именно адекватная модель источника данных обеспечивает оптимальное сжатие. Такая модель почти никогда не вводится в явном виде в существующих методах компрессии, что заметно отличает данную область исследований от областей автоматического анализа изображений или звука. Вместо этого используется лишь какое-то одно свойство конкретного типа мультимедийных данных, выбранное из эвристических соображений. Можно сказать, что отсутствуют научные теории сжатия данных конкретных типов, в частности, сжатия изображений.

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

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

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

Проблемам и задачам фрактального описания цифровых изображений посвящено большое число исследований отечественных (Д. С. Ватолин, В.В.Сергеев, В. А. Сойфер, В. В. Александров, Н.Д.Горский) и зарубежных (М. Барнсли, А. Жакен, Ю. Фишер, Д. Заупе) учёных. В концептуальном плане следует отметить монографию В. В. Александрова, С. В. Кулешова и О. В. Цветкова «Цифровая технология инфокоммуникации. Передача, хранение и семантический анализ текста, звука, видео», в которой фрактальные представления рассмотрены в контексте алгоритмической теории информации. Однако до сих пор мало внимания уделялось многокритериальным методам оптимизации фрактального сжатия. Задача построения эффективных по времени алгоритмов фрактальной компрессии, которые были бы сопоставимы с исходными ресурсоёмкими алгоритмами по степени сжатия и качеству восстанавливаемого изображения, остаётся актуальной и на сегодняшний день.

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

Основные задачи исследования:

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

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

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

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

Научная новизна исследования:

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

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

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

4. Создана новая трёхуровневая схема сопоставления ранговых и доменных блоков.

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

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

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

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

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

Реализация результатов исследования. Результаты диссертационной работы были использованы в НИР «Разработка теории обучаемых систем анализа изображений и распознавания образов на основе принципа репрезента-ционной минимальной длины описания», проводимой на кафедре компьютерной фотоники и видеоинформатики СГ16ГУ ИТМО по гранту МД-2040.2010.9 Президента Российской Федерации для государственной поддержки молодых российских учёных, а также в производственном процессе общества с ограниченной ответственностью «ДНК» в части хранения архива графической информации на серверах компании.

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

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

Личный вклад автора. Все результаты диссертационной работы получены автором лично.

Апробация работы. Основные результаты диссертационной работы докладывались на следующих научных форумах: XXXV! И международная научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2007 г.), III всероссийская научная конференция «Проектирование научных и инженерных приложений в среде MATLAB» (Санкт-Петербург, 2007 г.), XL международная научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2009 г.), XXXIX научная и учебно-методическая конференция профессорско-преподавательского состава СПбГУ ИТМО (Санкт-Петербург, 2010 г.), XL1 международная научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2010 г.).

Публикации. По материалам диссертации опубликовано 7 научных работ, из которых одна опубликована в журнале, входящем в Перечень ведущих рецензируемых научных журналов и изданий, формируемый ВАК РФ. Список опубликованных работ приведён в конце автореферата.

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка цитируемой литературы. Она содержит 127 страниц машинописного текста, 15 рисунков и 10 таблиц. Список цитируемой литературы содержит 114 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Существующие форматы изображений разделены на две основные группы — использующие сжатие без потерь и с потерями. В качестве характерных представителей форматов сжатия без потерь выделены GIF и PNG. Проведён анализ основных достоинств и недостатков этих форматов, а также продемонстрирована достаточно низкая достигаемая степень сжатия при их использовании на некоторых классах изображений. Рассмотрен формат JPEG как наиболее широко распространённый представитель группы форматов сжатия с потерями. В качестве основных недостатков JPEG выделены неоптималыюе соотношение степени компрессии и качества восстановленных данных для некоторых типов изображений, а также отсутствие возможности масштабирования декодированных данных при допустимых потерях качества. Как лишённый вышеперечисленных недостатков, а также обеспечивающий весьма высокую теоретически достижимую степень сжатия, рассмотрен фрактальный подход к сжатию изображений, которому и посвящено дальнейшее исследование.

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

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

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

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

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

Для построения критерия эффективности фрактального сжатия использован подход, широко применяющийся, например, в задачах машинного обучения, а именно — принцип минимальной длины описания (МДО). Данный принцип сформулирован следующим образом: «Среди множества моделей следует выбрать ту, которая позволяет минимизировать сумму: 1) длины описания модели (в битах); 2) длины данных, описанных посредством этой модели (в битах)». В соответствии с принципом МДО оптимальное сжатие достигается при построении модели, критерием выбора которой и служит конечная длина описания. Под моделью понимается некоторая информационная структура, представляющая собой закодированное (сжатое) изображение, полученное в результате работы той или иной разновидности алгоритма компрессии, который в данном случае будет являться представлением изображений. В качестве длгшы описания модели рассматривается объём сжатого изображения в битах. Под длиной данных, описанных посредством модели, понимается длина той части данных, которая не вошла в саму модель, т. е. «объём потерь» — количество информации, содержащееся в отклонении восстановленного после сжатия изображения от исходного изображения, обозначаемое через ¿1055. Таким

образом, принцип МДО позволяет корректно оценить качество построенной модели в ачгоритмах сжатия с потерями.

Далее во второй главе произведены оценки объёма сжатого изображения 1\т% и объёма потерь Z,|0SS. Для оценки Lm установлено, какую информацию необходимо сохранить в сжатом файле, чтобы иметь возможность осуществить восстановление изображения. Если рассматривается один из NR вариантов разбиения изображения на ранговые блоки, то в среднем будет необходимо 1ог2Л'л бит для указания, какое именно разбиение было выбрано. Пусть для каждого такого разбиения детерминированным образом устанавливается множество доменных блоков, то есть отдельно описывать множество доменов не требуется. Помимо описания разбиения, сжатый файл будет содержать пг записей, где пг — число ранговых блоков. Каждая такая запись включает в себя информацию о наилучшем домене, соответствующем текущему ранговому блоку, а также о коэффициентах преобразования для этого домена. Если общее число доменных блоков для выбранного варианта разбиения равно nd, то для кодирования номера одного доменного блока потребуется log2и</ бит. Пусть число коэффициентов преобразования равно пр, при этом на каждый из них нужно выделить ВПо бит. Таким образом, размер сжатого изображения оценён как

= log2A'K + wr(log 2nd + npB„p).

Оценка £|0SS произведена следующим образом. Рассмотрена разность исходного и восстановленного изображений. Поскольку все закономерности данных должны быть вынесены в модель, полагается, что значения разности в каждом пикселе являются независимыми отсчётами некоторой случайной величины. Таким образом, количество информационных потерь в результате сжатия выражается через энтропию разностей:

L,os^S-H{f(x,y)-f(x,y)\, где S — площадь изображения в пикселях, f(x,y) — оригинальное изображение, f{x,y) —восстановленное изображение.

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

^ = Aoss + Amg •

Итак, оптимальная модель изображения выбирается как компромисс между величиной сжатия и качеством восстановленного изображения, что находит объективное выражение в критерии МДО. Помимо этого, использование величины L позволяет решить задачи автоматического выбора размера ранговых блоков и построения оптимального квадродерева.

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

Вначале рассмотрен классический алгоритм фрактального сжатия. При условии задания числа ранговых блоков п, и числа доменов получена оценка для суммарного количества операций /Уор, требуемых для компрессии изображения: М09=Ыцпгп,1Ь!Г11, где Ля — число возможных разбиений, а Л'Г(/ — количество операций, необходимых для сравнения одного рангового и одного доменного блока. Применение распространённого упрощения, а именно, разбиения изображения на ранговые блоки одинаковых размеров, а также покрытия изображения доменами, размер которых пропорционален размеру ранговых блоков, позволяет добиться полиномиального роста количества блоков с ростом размера изображения в отличие от присущего классическому алгоритму экспоненциального роста (когда на форму и размер блоков не накладывается ограничений), но при этом скорость роста остаётся достаточно большой даже при рассмотрении одного разбиения, а именно — 0(М*), поскольку скорость роста как так и пропорциональна Л'2 (здесь и далее N — среднее геометрическое линейных размеров изображения).

Дачее оценено влияние параметров N11 и Л^. Сперва рассмотрен компонент Лг„-, ответственный за сравнение одного рангового блока с одним доменом. В традиционном варианте это сравнение осуществляется «попиксельно», т. е. операции проводятся непосредственно с элементами матриц, соответствующих блокам. В работе исследована замена «попиксельного» сопоставления на сравнение векторов признаков, заранее вычисляемых для каждого блока, которая позволяет существенно сократить количество операций, необходимых для сравнения пары блоков, однако при этом не приводит к сильному снижению качества восстановленного изображения, если вектор признаков в достаточной мере отражает структуру блока. Помимо этого, рассмотрена проблема сравнения одного рангового блока с множеством доменов. Для минимизации суммарного количества операций при таком сравнении предложена классификационная схема оптимизации, сущность которой состоит в иерархическом разбиении всего множества блоков на классы и последующем поиске оптимальных доменов по дереву классов. Поскольку число уровней в дереве классов пропорционально логарифму от его размера, то число операций, затрачиваемых на поиск оптимального домена для одного рангового блока, пропорционально

Далее рассмотрен компонент Л'),, отвечающий за количество возможных разбиений изображения на ранговые блоки. В качестве первого шага выбора оптимального способа разбиения изображения предложен «беспереборный» выбор разбиения на ранговые блоки одинаковых размеров, где под оптимальным разбиением понимается разбиение, минимизирующее объём сжатого изображения и максимизирующее качество восстановленного изображения, а размер блока выбирается исходя из критерия среднего пространственного периода изображения, более подробно описанного в третьей главе. Второй шаг заключается в том, чтобы, начиная с полученного на первом шаге разбиения и модифицируя в нём константное число ранговых блоков, получать новые разбиения с найденными соответствиями ранговых блоков и доменов за время, не зависящее от размера изображения. Это даёт возможность рассмотрения нефиксированного числа разбиений, растущего с увеличением размера изображения.

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

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

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

Вначале описана схема алгоритма компрессии, включающего классификацию блоков и иерархический поиск по дереву классов, а также быстрое сравнение блоков по дескрипторам. Рассмотрено разбиение изображения на ранговые блоки равного размера г. В качестве доменных блоков выступают всевозможные блоки размера 2г, данное множество доменов названо основным. Далее формируется расширенное множество доменных блоков, полученное в результате объединения основного и дополнительного множеств доменов. Последнее множество формируется следующим образом: для каждого из «основных» доменов строится семь трансформаций, а именно: повороты блока на 90°, 180° и 270°, отражение блока относительно вертикальной оси симметрии и повороты полученного отражённого блока также на 90°, 180° и 270°. Для каждого рангового блока поиск проводится среди расширенного множества доменов, в целях осуществления которого каждому ранговому и доменному блоку присваивается индекс и дескриптор.

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

1. Рассматривается «верхний левый угол» матрицы В, соответствующей текущему блоку Ь (подматрица В = {В^}.

2. Поочерёдно оцениваются элементы этой подматрицы от 1-го до г-го (где / — выбранная размерность индекса, / е [1;8]) в порядке, показанном на рис. 1; если текущий элемент меньше нуля, то соответствующему разряду индекса в двоичном представлении, начиная слева, присваивается значение 0, если больше или равен нулю — значение I.

1 5

2 4 6

.4 7 8

Рис. 1. Порядок выбора элементов для вычисления индекса

При применении к блоку Ь поворотов или отражения правила изменения ДКП-матрицы В задаются следующими равенствами:

Р,] = (~1) }у =/дг-/,у> ¿V ~ (-1);+1/*//! /у=Л^-у»

ч р'-'ч где = 1,/7.

Отсюда следует, что ДКП-матрицы (а, следовательно, и индексы) «дополнительных» доменов могут быть найдены достаточно просто на основе ранее вычисленных ДКП-матриц «основных» доменов.

Для вычисления дескрипторов использовано двумерное дискретное вейвлет-преобразование Хаара. Предложен следующий алгоритм формирования дескриптора (для блока Ь размера рхр пикселей, где р = 2ц, еЮ.

I р р

1. Вычисляется коэффициент е, =— •

Р /-|у»|

2. Блок разделяется на четыре равных подблока А2, й,, />4 и Ь5.

I ч ч

3. Последовательно вычисляются коэффициенты е2=е{—^ХХ^'у,

4 1=1 м

1 9 Р | р ч \ р р

—И Ау-. е4=е1—г £ 2Л > —г Е И Vшот-

1 1=1 ./=<?+! Я /=?+1у=1 9 /=?+1 /=9+1

ветствующие подблокам 64 и ¿5.

4. Формируется вектор е = [е2 е3 е4 е5], который и будет являться искомым дескриптором.

Как и вычисление индекса, формирование дескриптора для «дополнительного» домена может быть упрощено, а именно, вместо расчёта по вышеприведённому алгоритму можно осуществить простую перестановку компонент дескриптора «основного» домена в соответствии с конкретной трансформацией блока.

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

1. Рассматривается первый ранговый блок г,.

2. Формируется подмножество расширенного множества О доменов

путём выборки всех доменов с полностью либо частично совпадающим значением индекса методом иерархического поиска (домены, принадлежащие О^, названы обладающими «первичным сходством» с рассматриваемым ранговым блоком, или просто «первичными»).

3. Дескриптор блока г, по очереди сравнивается с дескрипторами каждого из доменов, принадлежащих Д..

4. Формируется подмножество множества й^ путём выбора некоторого

количества доменов, дескрипторы которых обладают максимальной близостью к дескриптору рангового блока в смысле евклидова расстояния (домены, принадлежащие £>,, названы обладающими «вторичным сходством» с рассматриваемым ранговым блоком, или просто «вторичными»).

5. Среди найденных «вторичных» доменов ищется домен с}{, а также соответствующие паре —г/, коэффициенты яркости и контрастности .$■• и о,,

исходя из условия минимизации СКО: ^ =агзшт|кМ8Е(Г|,^|)|, где

¿1 = .Ц + оЕ, — сжатый до размера блока г, блок с1\, а Е — единичная матрица размера блока г\. Доменный блок, для которого будет выполняться приведённое условие минимизации СКО, назван оптимальным, или лучшим доменом.

6. Если найденный на предыдущем шаге домен с/, принадлежит «основному» множеству доменов, фиксируется его порядковый номер V,, если же «дополнительному» — фиксируется номер трансформации г,, путём которой он был получен из «исходного» домена, а также номер данного «исходного» домена .

7. Рассматривается второй ранговый блок гг, для которого повторяются шаги 2-6, затем третий ранговый блок г}, и так далее, пока не будет найден оптимальный домен г/у для последнего рангового блока , где

Мг — количество ранговых блоков.

Обоснован способ выбора числа вторичных доменов, заключающийся в том, чтобы количество операций на «попиксельное» сравнение не зависело от размера рангового блока. Это достигнуто путём уменьшения числа «вторичных» доменных блоков обратно пропорционально г1, где г — размер рангового блока. Пусть т — число «первичных» доменов данного класса, а к — число операций, затрачиваемых на сравнение дескрипторов двух блоков, тогда число «вторичных» блоков выбирается как тк/г2.

В пункте 5 вышеприведённого алгоритма в качестве окончательного критерия выбора лучшего домена используется минимизация СКО, которое является общепринятым показателем для определения сходства блоков во фрактальных алгоритмах компрессии. Этот критерий также используется в предла-

гаемом алгоритме, т. к. конечное сравнение исходного и восстановленного изображения для оценки качества сжатия осуществляется по критерию PSNR (англ. Peak Signal«to-Noise Ratio — пиковое отношение сигнал-шум), который строится на основе СКО разности сравниваемых изображений.

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

Пусть пространственный спектр изображения / размера М х N вычисляется через дискретное преобразование Фурье F:

Здесь и и V — частоты, а соответствующие им периоды равны М/и и N/v. Тогда величину некоторого характерного периода гармоник изображения можно оценить как

Величина названа средним пространственным периодом (СГ1П) изображения. Значение СПП используется в качестве априорной оценки влияния размера рангового блока на качество восстанавливаемого изображения. Детально способ применения СПП будет описан ниже — при изложении результатов экспериментальной проверки.

Для усовершенствования вышеописанного разбиения на ранговые блоки равного размера применён метод квадродерева, модифицированный с учётом требований критерия МДО следующим образом.

1. Строится разбиение изображения на ранговые блоки равного размера (при этом размер определяется в соответствии с критерием СПП).

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

х=0 у=О

I IfM

11=0 v-0

Проверка на улучшение качества производится с использованием критерия МДО, при этом слагаемое L\oss вычисляется через значение СКО. Однако осуществлять декомпрессию изображения на каждом шаге разделения блоков нецелесообразно, поэтому, в частности, не представляется возможным напрямую сравнивать значения СКО оригинального изображения от восстановленного; вместо этого используется оценочное значение СКО, которое вычисляется как среднее арифметическое от СКО, соответствующего всем ранговым блокам.

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

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

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

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

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

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

• время сжатия увеличивается как N4 для каждого фиксированного разбиения на ранговые блоки;

• качество восстановленного изображения увеличивается с уменьшением размера ранговых блоков;

• размер сжатого изображения увеличивается с уменьшением размера ранговых блоков;

• минимум критерия МДО как компромисса между информационными потерями и степенью сжатия достигается для некоторых промежуточных размеров ранговых блоков;

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

Далее в четвёртой главе представлены результаты тестирования оптимизированного фрактального алгоритма, включаюшего иерархический поиск по дереву индексов блоков и быстрое сравнение блоков с помощью дескрипторов. Пример изображения, восстановленного после сжатия с разными размерами ранговых блоков, приведён на рис. 2. Из анализа результатов тестирования оптимизированного алгоритма установлено, что скорость его работы не только выше по сравнению с классическим алгоритмом, но и имеет иную зависимость от размера изображения, вследствие чего на изображениях размера 60*60 пикселей имеется 8-кратный выигрыш, а на изображениях размера 240x240 пикселей — уже 70-75-кратный выигрыш. Время работы оптимизированного алгоритма растёт медленнее, чем N, что является приемлемым для практики. Сравнение результатов также показывает, что критерий качества МДО в результате использования оптимизированного алгоритма фрактального сжатия ухудшается в среднем на 4 %.

г - 10 г = 12 г - 16

Рис. 2. Примеры восстановленных изображений при разных размерах рангового блока

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

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

ИййЙ5«1«8^Э!а?К?М?гЙйЛ > «УаИИКИЖ

iSKSJiiirrtr-j-Sf?'..-

Рис. 3. Визуализация разбиеиия методом квадродерева

Принципиальным показателем эффективности построения квадродерева является уменьшение критерия длины описания. При сравнении результатов компрессии установлено, что значение МДО в случае квадродерева оказывается меньше, чем в случае ранговых блоков любых равных размеров. Уменьшение этого значения может быть как небольшим (менее I %), так и весьма высоким (более 15 %) по сравнению с классическим алгоритмом. Уменьшение значения МДО свидетельствует о том, что степень сжатия увеличивается при сохранении качества восстановленного изображения, либо же качество восстановленного изображения увеличивается при сохранении коэффициента сжатия.

В конце четвёртой главы приведена общая методика сравнения алгоритмов сжатия изображений с потерями, основанная на критерии МДО. а также результаты сравнения фрактального алгоритма и алгоритма JPEG посредством этой методики.

Для того, чтобы сравнить два или более алгоритма сжатия, необходимо выполнить следующие шаги:

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

• осуществить компрессию каждого изображения с разными установками степени сжатия, допустимыми в исследуемых алгоритмах;

• вычислить значение ¿¡ms для каждого из вариантов компрессии на основе размера сжатого файла, из которого вычтена длина метаданных, не имеющих отношения к кодированию содержания изображения;

• вычислить значение Lioss путём оценивания энтропии разности исходного и восстановленного после сжатия изображений, умноженной на площадь изображения в пикселях;

• найти установочные параметры, при которых достигается минимальное значение выражения ¿.¡mg+i-ioss;

• сравнить средние по выборкам изображений значения критерия МДО для сопоставляемых алгоритмов сжатия.

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

Тестирование алгоритмов фрактального сжатия и JPEG было проведено на шести ранее упомянутых выборках. Для каждого изображения каждой из выборок была найдена величина МДО для двух тестируемых алгоритмов сжатия. Эта величина, усреднённая по выборке, показывает для неё степень эффективности того или иного способа компрессии. Чтобы сделать эту величину независимой от размера изображения, она была поделена на L0 — объём несжатого файла. Величина L/L0 показывает коэффициент сжатия с учётом информационных потерь. В табл. 1 приведены результаты сравнения алгоритмов сжатия на каждой выборке.

Табл. 1. Результаты сравнения алгоритма JPEG и оптимизированного __алгоритма фрактального сжатия__

Выборка изображений L/La

Фрактальный алгоритм JPEG

Аэрокосмические 0,794±0,049 0,793±0,026

Облака 0,376±0,023 0,385±0,034

Наземные (дома) 0,706±0,024 0,722*0,033

Лица 0,559±0,016 0,622±0,018

Поверхность планет 0,645±0,061 0,644±0,072

Фрукты и ОВОЩИ 0,558±0,026 0,615±0,024

Как видно из таблицы, оптимизированный фрактальный алгоритм, использующий разбиение в форме квадродерева, в среднем оказывается не хуже алгоритма JPEG, однако его эффективность является разной на разных выборках. В частности, на аэрокосмических снимках поверхности Земли, а также других планет, фрактатьный атгоритм сопоставим (и, возможно, немного хуже) алгоритма JPEG. Это может быть связано с тем, что данные изображения содержат сцены с малыми перепадами дальности по сравнению с расстоянием до камеры. Вопреки ожиданиям, фрактальный алгоритм не оказывается существенно эффективнее на изображениях типично фрактальных объектов, таких как облака. Как и на изображениях трёхмерных наземных сцен (вне помещений), выигрыш здесь оказывается достоверным, но не слишком большим (отношение L/Ц уменьшается в 1,02 раза по сравнению с JPEG). Наибольший выигрыш достигается для изображений, содержащих плавные переходы яркости, которые, видимо, с помощью пространственного спектра представляются не слишком эффективно. Здесь отношение L/L0 в среднем уменьшается в 1,1 раза (а для некоторых подвыборок в 1,15 раза). С учётом оптимизации времени выполнения фрактального алгоритма сделан вывод о целесообразности его использования для указанных типов изображений.

ЗАКЛЮЧЕНИЕ

В диссертационном исследовании:

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

• проведён теоретический анализ способов минимизации временных затрат на фрактальную компрессию, включающий в себя покомпонентную оценку влияния параметров компрессии на суммарное количество вычислительных операций;

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

• создан новый оптимизированный алгоритм фрактальной компрессии с вычислительной сложностью, меньшей О(Л^), использующий иерархическую индексацию блоков по их ДКП-индексам и быстрое сравнение рангового и доменного блока по их вейвлет-дескрипторам;

• эмпирически определён высокий (более 0,9) коэффициент корреляции среднего пространственного периода изображения с оптимальным по МДО размером рангового блока, исходя из чего разработан новый метод априорного задания начального размера рангового блока для разбиения изображения в форме квадродерева;

« выполнено усовершенствование классического метода разбиения изображения в форме квадродерева путём его модификации с учётом требований критерия МДО, что позволило повысить качество сжатия по сравнению с использованием порогового значения СКО как критерия разделения рангового блока на подблоки;

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

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

ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

2. Разработанные алгоритмы фрактального сжатия, использующие иерархический поиск соответствий, обладают вычислительной сложностью ниже 0(Л,г3), где N — линейный размер изображения, при ухудшении качества изображения в среднем не более, чем на 5 % по сравнению с полным перебором соответствий ранговых и доменных блоков, имеющим вычислительную сложность 0(Л4) при покрытии изображения блоками равных размеров.

3. Средний пространственный период изображения обладает высоким (более 0,9) коэффициентом корреляции с оптимальным размером ранговых блоков при фрактальном сжатии.

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

5. Разработанная методика сравнения алгоритмов сжатия изображений на основе критерия минимальной длины описания обеспечивает оптимизацию параметров методов компрессии и принятие решения о выборе метода сжатия в зависимости от класса изображений.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендуемых ВАК РФ

1. ОкуневВ. В. Об одном методе оптимизации фрактального алгоритма сжатия изображений // Вестник Санкт-Петербургского университета. Сер. 10. —2010. — Вып. 2. — С. 114-121.

Свидетельства о государственной регистрации программ для ЭВМ

2. Потапов А. С., Окунев В. В. Программный модуль «Фрактальное представление изображений с индексацией по коэффициентам вейвлет-разложения» // Свидетельство о государственной регистрации программы для ЭВМ № 2010613461. — М.: Роспатент, 2010. — Дата поступления 06.04.2010, дата регистрации 26.05.2010.

Публикации в других изданиях

3. Окунев В. В. Оптимизация фрактального алгоритма сжатия изображений // Процессы управления и устойчивость: Труды 38-й международной научной конференции аспирантов и студентов / Под ред. А. В. Платонова, Н. В. Смирнова. — СПб.: Издательство Санкт-Петербургского университета, 2007. — С. 423-428.

4. Окунев В. В. Оптимизация фрактального алгоритма сжатия изображений // Труды Всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB». — СПб.: Издательство Санкт-Петербургского университета, 2007. — С. 1443-1449.

5. Окунев В. В. Адаптивное разбиение и классификация в алгоритме фрактального сжатия изображений II Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. — СПб.: Издательский Дом Санкт-Петербургского университета, 2009. — С. 491-496.

6. Окунев В. В., Потапов А. С. Применение метода иерархического поиска для оптимизации алгоритма фрактального сжатия изображений // Труды нау.чно-технического центра Фотоники и оптоинформатики / Под ред. И.П.Гурова и С.А.Козлова. — СПб.: СПбГУ ИТМО, 2009. — С. 373-381.

7. Окунев В. В., Потапов А. С. Априорная оценка влияния размера блоков на качество восстановленного изображения для фрактального алгоритма компрессии // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. — СПб.: Издательский Дом Санкт-Петербургского университета, 2010.— С. 466-471.

Тиражирование и брошюровка выполнены в учреждения «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 4669 объем 1 п.л. Тираж 100 экз.

Введение.

Глава 1. Обзор методов сжатия цифровых изображений.

1.1. Введение.

1.2. Обзор современных форматов цифровых изображений.

1.2.1. Компрессия без потерь.

1.2.1.1. Формат GIF.

1.2.1.2. Формат PNG.

1.2.2. Компрессия с потерями.

1.2.2.1. Формат JPEG.

1.2.2.2. Метод фрактального сжатия.

1.3. Классический алгоритм фрактального сжатия изображений.

1.3.1. Описание классического алгоритма.

1.3.2. Модификации алгоритма для разных типов графической информации.

1.4. Анализ подходов к оптимизации алгоритмов фрактального сжатия.

1.4.1. Выделение основных подходов.

1.4.2. Оптимизация на основе параллельных вычислений.

1.4.3. Оптимизация с помощью генетических алгоритмов.

1.4.4. Оптимизация с помощью предметно-зависимых эвристик.

1.5. Использование особенностей изображений при оптимизации алгоритмов фрактального сжатия.

1.5.1. Оптимизация разбиения изображения на ранговые блоки.

1.5.2. Оптимизация поиска соответствия ранговых и доменных блоков.

Выводы по первой главе.

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

2.1. Введение.

2.2. Оптимизация числа операций в алгоритмах фрактального сжатия.

2.2.1. Оценка числа операций в классическом фрактальном алгоритме.

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

2.2.3. Оптимизация процедуры поиска соответствий блоков.

2.2.4. Оценка допустимого числа вариантов разбиения изображения на ранговые блоки.

2.3. Оценка объёма сжатого изображения.

2.4. Оценка качества восстановленного изображения.

2.4.1. Классические критерии качества.

2.4.2. Принцип минимальной длины описания в оценке качества сжатия изображений.

2.5. Выбор оптимального разбиения на ранговые блоки.

2.5.1. Выбор размера рангового блока.

2.5.2. Оптимизация разбиения «жадным» алгоритмом.

Выводы по второй главе.

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

3.1. Введение.

3.2. Построение и описание доменных и ранговых блоков.

3.2.1. Разбиение изображения на ранговые блоки.

3.2.2. Покрытие изображения доменными блоками.

3.2.3. Преимущества выбранных способов.

3.2.4. Расширенное множество доменов.

3.2.5. Индексация блоков.

3.2.5.1. Основы ДКП-подхода.

3.2.5.2. Алгоритм вычисления индекса блока.

3.2.5.3. Упрощённое вычисление индексов «дополнительных» доменов.

3.2.5.3. Общая концепция использования индексов.

3.2.6. Применение дескрипторов для описания блоков.

3.3. Поиск оптимальных доменных блоков.

3.3.1. Иерархический поиск по индексам.

3.3.2. Поиск оптимальных доменов.

3.3.3. Оценка МДО сжатого изображения.

3.3.4. Оценка нижней границы допустимого размера рангового блока.

3.4. Выбор оптимального разбиения на ранговые блоки.

3.4.1. Выбор оптимального размера ранговых блоков.

3.4.2. Реализация метода квадродерева.

3.5. Формат сжатого файла.

3.5.1. Общая структура сжатого файла.

3.5.2. Заголовок сжатого файла.

3.5.3. Поле данных сжатого файла.

Выводы по третьей главе.

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

4.1. Введение.

4.2. Эмпирические характеристики классического алгоритма.

4.3. Тестирование метода оптимизированного поиска доменных блоков.

4.4. Связь среднего пространственного периода изображения с параметрами фрактального сжатия.

4.5. Повышение качества сжатия при оптимизации разбиения с помощью квадродерева.

4.6. Методика сравнения алгоритмов сжатия с потерями.

Выводы по четвёртой главе.:.

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

В настоящее время благодаря значительному распространению электронно-вычислительной техники хранение и обработка данных различного типа осуществляется преимущественно в цифровом виде. Всё большую значимость приобретают мультимедийные типы данных — видеофайлы, аудиозаписи, цифровые изображения. Помимо этого, в последнее время имеет место развитие вычислительных сетей, связывающих всевозможные типы устройств — компьютеры, принтеры, сотовые телефоны, а также различное телекоммуникационное оборудование, и даже искусственные спутники Земли. Это развитие обусловлено постоянно растущей необходимостью в обмене хранимой информацией. Такой обмен осуществляется посредством передачи данных по физическим телекоммуникационным каналам, построенным как на базе существующих сетей (например, телефонных линий), так и с применением различных инновационных технологий (таких как WiMAX, GPS, PON и других).

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

К мультимедийной информации чаще всего применяется сжатие с потерями. Справедливость такого применения обусловлена тем фактом, что 5 для мультимедийных объектов, как правило, можно отказаться от хранения* каких-либо их особенностей (например, мелких деталей на изображении, либо не воспринимаемых человеческим ухом звуковых частот в аудиозаписи) г в пользу уменьшения временных затрат и увеличения степени компрессии. В действительности, существуют распространённые алгоритмы компрессии без потерь и для мультимедийных объектов, такие как FLAC для звуковых файлов или PNG для цифровых изображений. Однако1 такие форматы проектировались как универсальные для своего типа данных^ и, как следствие, оказались неспособными учитывать особенности конкретного' сжимаемого файла, что в результате привело к существенному проигрышу в степени сжатия по сравнению с аналогичными алгоритмами компрессии с потерями.

Алгоритмы сжатия с потерями обычно в какой-то» мере учитывают особенности типа сжимаемых данных, но этот учёт весьма ограниченный. В,то же время; именно адекватная модель источника данных обеспечивает оптимальное сжатие. Такая модель почти никогда не вводится в явном, виде в существующих методах компрессии, что разительно отличает данную -область исследований от областей автоматического анализа изображений или звука. Вместо этого используется лишь какое-то одно свойство конкретного типа мультимедийных данных, выбранное из эвристических соображений. Можно сказать, что отсутствуют научные теории сжатия данных конкретных типов, в частности, сжатия изображений.

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

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

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

Проблемам и задачам фрактального описания цифровых изображений посвящено большое число исследований отечественных (Д. С. Ватолин, В. В. Сергеев, В. А. Сойфер, В. В: Александров, Н: Д. Горский) и зарубежных (М. Барнсли, А. Жакен, Ю. Фишер, Д. Заупе) учёных. В концептуальном плане следует отметить монографию В. В. Александрова, С. В. Кулешова и О. В. Цветкова [1], в которой фрактальные представления рассмотрены в контексте алгоритмической теории информации. Однако до сих пор мало внимания уделялось многокритериальным методам оптимизации фрактального сжатия. Задача построения эффективных по времени алгоритмов* фрактальной компрессии, которые были бы сопоставимы с исходными ресурсоёмкими алгоритмами по степени сжатия и качеству восстанавливаемого изображения, остаётся актуальной и на сегодняшний день.

Цель работы

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

Основные задачи

1. Теоретический анализ покомпонентной вычислительной сложности алгоритмов фрактального сжатия изображений.

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

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

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

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

Положения, выносимые на защиту:

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

2. Разработанные алгоритмы фрактального сжатия, использующие иерархический поиск соответствий, обладают вычислительной о сложностью ниже 0{Ы ), где N — линейный размер изображения, при ухудшении качества изображения в среднем не более, чем на 5 % по сравнению с полным перебором соответствий ранговых и доменных блоков, имеющим вычислительную сложность 0(Д/4) при покрытии изображения блоками равных размеров.

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

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

5. Средний пространственный период изображения обладает высоким (более 0,9) коэффициентом корреляции с оптимальным размером ранговых блоков при фрактальном сжатии.

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

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

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

3. Разработан новый алгоритм фрактального сжатия, имеющий 5 вычислительную сложность ниже О(ЛР) и обеспечивающий минимизацию критерия длины описания.

4. Создана новая трёхуровневая схема сопоставления ранговых и доменных блоков.

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

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

Практическая значимость

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

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

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

Реализация результатов работы

Результаты диссертационной работы были использованы в НИР «Разработка теории обучаемых систем анализа изображений и распознавания образов на основе принципа репрезентационной минимальной длины описания», проводимой на кафедре компьютерной фотоники и видеоинформатики СПбГУ ИТМО по гранту МД-2040.2010.9 Президента

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

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

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

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

Личный вклад автора

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

Апробация работы

Основные результаты работы докладывались на следующих научных форумах:

1. XXXVIII международная научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2007 г.).

2. III всероссийская научная конференция «Проектирование научных и инженерных приложений в среде МАТЬАВ» (Санкт-Петербург, 2007 г.).

3. ХЬ международная научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2009 г.).

4. XXXIX научная и учебно-методическая конференция профессорско-преподавательского состава СПбГУ ИТМО (Санкт-Петербург, 2010 г.).

5. ХЫ международная научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2010 г.).

Публикации

По материалам диссертации опубликовано 7 научных работ, из которых одна опубликована в журнале, входящем в Перечень ведущих рецензируемых научных журналов и изданий, формируемый ВАК РФ:

1. ОкуневВ. В. Оптимизация фрактального алгоритма сжатия изображений // Процессы управления и устойчивость: Труды 38-й международной научной конференции аспирантов и студентов / Под ред. А. В. Платонова, Н. В. Смирнова. — СПб.: Издательство Санкт-Петербургского университета, 2007. — С. 423-428.

2. Окунев В. В. Оптимизация фрактального алгоритма сжатия изображений // Труды Всероссийской научной конференции «Проектирование научных и инженерных приложений в среде МАТЬАВ». — СПб.: Издательство Санкт-Петербургского университета, 2007. — С. 1443-1449.

3. ОкуневВ. В. Адаптивное разбиение и классификация в алгоритме фрактального сжатия изображений // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. — СПб.: Издательский Дом Санкт-Петербургского университета, 2009. — С. 491-496.

4. Окунев В. В. Об одном методе оптимизации фрактального алгоритма сжатия изображений // Вестник Санкт-Петербургского университета. Сер. 10.—2010.—Вып. 2. —С. 114-121.

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

Под ред. И. П. Гурова и С. А. Козлова. — СПб.: СПбГУ ИТМО, 2009. — С. 373-381.

6. Окунев В. В., Потапов А. С. Априорная оценка влияния размера блоков на качество восстановленного изображения для фрактального алгоритма компрессии // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяиа. — СПб.: Издательский Дом Санкт-Петербургского университета, 2010. — С. 466-471.

7. Потапов А. С., Окунев В. В. Программный модуль «Фрактальное представление изображений с индексацией по коэффициентам вейвлет-разложения» // Свидетельство о государственной регистрации программы для ЭВМ № 2010613461. — М.: Роспатент, 2010. — Дата поступления 06.04.2010, дата регистрации 26.05.2010.

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

Диссертация состоит из введения, четырёх глав, заключения и списка цитируемой литературы. Она содержит 127 страниц машинописного текста, 15 рисунков и 10 таблиц. Список цитируемой литературы содержит 114 наименований.

Заключение

В диссертационном исследовании:

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

• проведён теоретический анализ способов минимизации временных затрат на фрактальную компрессию, включающий в себя покомпонентную оценку влияния параметров компрессии на суммарное количество вычислительных операций;

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

• создан новый оптимизированный алгоритм фрактальной компрессии с вычислительной сложностью, меньшей 0{Ы ), использующий иерархическую индексацию блоков по их ДКП-индексам и быстрое сравнение рангового и доменного блока по их вейвлет-дескрипторам;

• эмпирически определён высокий (более 0,9) коэффициент корреляции среднего пространственного периода изображения с оптимальным по МДО размером рангового блока, исходя из чего разработан новый метод априорного задания начального размера рангового блока для разбиения изображения в форме квадродерева;

• выполнено усовершенствование классического метода разбиения изображения в форме квадродерева путём его модификации с учётом требований критерия МДО, что позволило повысить качество сжатия по сравнению с использованием порогового значения СКО как критерия разделения рангового блока на подблоки;

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

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

1. Александров В. В., Кулешов С. В., Цветков О. В. Цифровая технология инфокоммуникации. Передача, хранение и семантический анализ текста, звука, видео. — СПб.: Наука, 2008. — 244 с.

2. Roelofs G. PNG: the definitive guide. — Sebastopol, CA: O'Reilly, 1999.xix, 321 p.

3. Miano J. Compressed image file formats: JPEG, PNG, GIF, XBM, BMP. — Reading, Mass.: Addison Wesley, 1999. — xi, 264 p.

4. Ватолин Д., Ратушняк А., Смирнов M., Юкин В. Методы сжатия данных. — М.: Диалог-МИФИ, 2003. — 381 с.

5. Fisher Y., Jacobs Е. W., Boss R. D. Fractal image compression using iterated transform // Naval Ocean Systems Center: NOSC Technical Report 1408. — 1991.

6. Jacquin A. Image coding based on a fractal theory of iterated contractive image transformations // IEEE Transactions on Image Processing. — 1992.1. No 1. —P. 18-30.

7. Ghosh S. K., Mukherjee J., Das P. P. Fractal image compression: a randomized approach // Pattern Recognition Letters. — 2004. — Vol. 25.1. P. 1013-1024.

8. Welstead S. Fractal and wavelet image compression techniques. — Bellingham (Wash.): SPIE Optical Engineering Press, 1999. —xv, 232 p.

9. Puate J., Jordan F. Using fractal compression scheme to embed a digital signature into an image // Proceedings of the SPIE Conference on Video Techniques and Software for Full-Service Networks. — 1997. — Vol. 2915.1. P. 108-118.

10. Schouten В. A. M., De Zeeuw P. M. Feature extraction using fractal codes // Proceedings of the Third International Conference on Visual Information and Information Systems. — 1999. — P. 483-492.

11. Polidori E., Dugelay J.-L. Zooming using iterated function systems // Fractals. — 1997. — Vol. 5. — P. 111-123.

12. Gharavi-Alkhansari M., DeNardoR., TendaY., Huang T. S. Resolution enhancement of images using fractal coding // Proceedings of the SPIE Conference on Visual Communications and Image Processing. — 1997. — Vol. 3024. —P. 1089-1100.

13. AliM., GennertM. A., ClarksonT. G. Analysis, generation and compression of pavement distress images using fractals // The Applications of Fractals and Chaos. — 1993. — P. 147-169.

14. Ali M., Xiaoping M., Clarkson T. G., Taylor J. G. Using fractal interpolation function encoded ultrasonic signals to train a neural network // IEEE Colloquium on Fractals in Signal and Image Processing. — 1993. — Vol. 5. —P. 1-3.

15. Ying Zhang, Lai-Man Po. Fractal color image compression using vector distortion measure // Proceedings of the IEEE International Conference on Image Processing. — 1995. — Vol. 3. — P. 276-279.

16. Hürtgen B., Mols P., Simon S. F. Fractal transform coding of color images // Proceedings of the SPIE Visual Communications and Image Processing. — 1994. —Vol. 2308. —P. 1683-1681.

17. GrebenikV. V. Fast hybrid fractal image compression algorithm for color images // Proceedings of the IEEE Fourth International Conference on Signal Processing. — 1998. — Vol. 1. — P. 804-806.

18. Al-Hilo E. A., George L. E. Speeding-up fractal colored image compression using moments features // Digital Image Computing: Techniques and Applications. — 2008. — P. 486-490.

19. Ying Zhang, Lai-Man Po, Ying-LinYu. Wavelet transform based variable tree size fractal video coding // Proceedings of the IEEE International Conference on Image Processing. — 1997. — Vol. 2. — P. 294-297.

20. Ali M., Clarkson T. G. Using linear fractal interpolation functions to compress video images // Fractals. — 1994. — Vol. 2, no. 3. — P. 417-421.

21. Ali M., Papadopoulos C., Clarkson T. G. The use of fractal theory in a video compression system // Proceedings of the IEEE Data Compression Conference. — 1992. — P. 259-268.

22. Dugelay J.-L., Majdandzic E. Moving picture fractal compression using I. F. S. — A Review (II) // EURECOM: Internal Research Report. — 1997.

23. Bogdan A. Multiscale (inter/intra-frame) fractal video coding // Proceedings of the IEEE International Conference on Image Processing. — 1994. — Vol. 1,—P. 760-764.

24. Gharavi-Alkhansari M., Huang T. S. Fractal video coding by matching pursuit // Proceedings of the IEEE International Conference on Image Processing. — 1996. —Vol. 1. — P. 157-160.

25. HurtgenB., Buttgen P. Fractal approach to low-rate video coding // Proceedings of the SPIE Visual Communications and Image Processing. — 1993. —Vol. 2094. —P. 120-131.

26. Sang Hyun Kim, Nam Chul Kim. Low bit rate video coding using wavelet-based fractal approximation // Proceedings of the IEEE International Conference on Image Processing. — 1997. — Vol. 2. — P. 787-790.

27. Kim Chang-Su, Lee Sang-Uk. Fractal coding of video sequence by circular prediction mapping // Fractals. — 1997. — Vol. 5. — P. 75-88.

28. Kim Chang-Su, Kim Rin-Chul, Lee Sang-Uk. Fractal coding of video sequence using circular prediction mapping and noncontractive interframe mapping // IEEE Transactions on Image Processing. — 1998. — Vol. 7, no. 4. —P. 601-605.

29. Xu Dong, Sudhakar R. Fractal compression of image sequences // Southcon Conference Record. — 1995. — P. 199-204.

30. Barthel K. U, Voye T. Three-dimensional fractal video coding // Proceedings of the IEEE International Conference on Image Processing. — 1995. — Vol. 3. — P. 260-263.

31. Barthel K. U, Ruhl G., Voye T. Combining wavelet and fractal coding for 3-D video coding // Proceedings of the IEEE International Conference on Image Processing. — 1996. — Vol. 1,—P. 181-184.

32. Barakat M., Dugelay J.-L. Image sequence coding using 3-D IFS // Proceedings of the IEEE International Conference on Image Processing. — 1996.—Vol. 1. —P. 141-144.

33. Chang-SuKim, Rin-Chul Kim, Sang-UkLee. Fractal coding of video sequence using circular prediction mapping and noncontractive interframe mapping // IEEE Transactions on Image Processing. — 1998. — Vol. 7, no. 4. —P. 601-605.

34. HamzaouiR. A new decoding algorithm for fractal image compression // Electronics Letters. — 1996. — Vol. 14. — P. 1273-1274.

35. Hamzaoui R. Fast decoding algorithms for fractal image compression // Albert-Ludwigs University at Freiburg: Technical Report 86. — 1997.

36. Hamzaoui R. Ordered decoding algorithm for fractal image compression // Proceedings of the International Picture Coding Symposium. — 1997. — P. 91-95.

37. Dedera L., Chmurny J. A parallel approach to image decoding in the fractal image block coding scheme // Neural Network World. — 1998. — Vol. 8, no. 4.— P. 365-374.

38. He C., Yang S. X., Huang X. Progressive decoding method for fractal image compression // IEE Proceedings — Vision, Image and Signal Processing. — 2004. —Vol. 151, no. 3. — P. 207-213.

39. Mukherjee J, Kumar P, Ghosh S. K. A graph-theoretic approach for studying the convergence of fractal encoding algorithm // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 3. — P. 366-377.

40. KominekJ. Convergence of fractal encoded images // Proceedings of the Conference on Data Compression. — 1995. — P. 242-251.

41. Hiirtgen В., Simon S. F. On the problem of convergence in fractal coding schemes // Proceedings of the IEEE International Conference on Image Processing. — 1994,—Vol. 3.—P. 103-106.

42. Hiirtgen В., Hain T. On the convergence of fractal transforms // Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. — 1994. — Vol. 5. — P. 561-564.

43. Mukherjee J, Kumar P, Ghosh S. K. A graph-theoretic approach for studying the convergence of fractal encoding algorithm // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 3. — P. 366-377.

44. Ruhl M., Hartenstein H. Optimal fractal coding is NP-hard // Proceedings of the Conference on Data Compression. — 1997. — P. 261—270.

45. Люгер Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. — 4-е издание. — Пер. с англ.: М., Изд. дом «Вильяме», 2003. —■ 865 с.

46. Cofer R. Н., Brown Н. К., Abdallah S. Impact of parallel computing on fractal image compression // Southcon Conference Record. — 1994. — P. 331-334.

47. Acken K. P., Kim H. N., Irwin M. J., Owens R. M. An architectural design for parallel fractal compression // Proceedings of the International Conference on Application Specific Systems, Architectures and Processors. — 1996. —P. 3-11.

48. Hufnagl C., Uhl A. Algorithms for fractal image compression on massively parallel SIMD arrays // Real-Time Imaging. — 2000. — Vol. 6, no. 4. — P. 267-281.

49. Jackson D. J., Ren H., Wu X.-W., Ricks K. G. A hardware architecture for real-time image compression using a searchless fractal image coding method // Real Time Image Processing. — 2007. — Vol. 1, no. 3. — P. 225-237.

50. Samavi S., Habibi M., Shirani S., Rowshanbin N. Real time fractal image coder based on characteristic vector matching // Image and Vision Computing, 2010. — Vol. 28, no. 11. —P. 1557-1568.

51. Erra U. Toward real time fractal image compression using graphics hardware // Proceedings of the International Symposium on Visual Computing. — 2005. — Vol. 3804. — P. 723-728.

52. FaraounK.M., BoukelifA. Speeding up fractal image compression by genetic algorithms // Multidimensional Systems and Signal Processing. — 2005. — Vol. 16, no. 2. — P. 217-236.

53. Vences L., Rudomín I. Genetic algorithms for fractal image and image sequence compression // Proceedings of the Computación Visual. — 1997.—P. 1-10.

54. Ming-Sheng Wu, We-Chih Teng, Jyh-Horng Jeng, Jer-Guang Hsieh. Spatial correlation genetic algorithm for fractal image compression // Chaos, Solitons & Fractals. — 2006. — Vol. 28, no. 2. — P. 497-510.

55. Mitra S. K., Murthy C. A., Kundu M. K. Technique for fractal image compression using genetic algorithm // IEEE Transactions on Image Processing. — 1998. — Vol. 7, no. 4. — P. 586-593.

56. Vences L., Rudomín I. Fractal compression of single images and image sequences using genetic algorithms // Institute of Technology, University of Monterrey: manuscript. — 1994.

57. Saupe D., Ruhl M. Evolutionary fractal image compression // Proceedings of the IEEE International Conference on Image Processing. — 1996. — Vol.1. —P. 129-132.

58. Berthe K., Jing Yun Hua, Yang Yang. Efficient image compression based on combination of fuzzy-fractal theory // Proceedings of the IEEE Region 10 Conference on Computers, Communications, Control and Power Engineering. — 2002. — Vol. 1. — P. 573-577.

59. Bogdan A., Meadows H. E. Kohonen neural network for image coding based on iteration transformation theory // Proceedings of the SPIE

60. Conference on Neural and Stochastic Methods in Image and Signal Processing. — 1992. — Vol. 1766. — P. 425^36.

61. Hamzaoui R. Codebook clustering by self-organizing maps for fractal image compression//Fractals. — 1995. — Vol. 5. — P. 27-38.

62. Welstead S. Self-organizing neural network domain classification for fractal image coding // Proceedings of the IASTED International Conference on Artificial Intelligence and Soft Computing. — 1997. — P. 248-251.

63. Tseng C.-C., Hsieh J.-G., Jeng J.-H. Fractal image compression using visual-based particle swarm optimization // Image and Vision Computing. — 2008. — Vol. 26, no. 8. — P. 1154-1162.

64. Ghim-Hwee Ong, Chorng-Meng Chew, Yi Cao. A simple partitioning approach to fractal image compression // Proceedings of the ACM Symposium on Applied Computing. — 2001. — P. 301-305.

65. Yigang Wang, Yiwen Jin, Qunsheng Peng. Merged quadtree fractal image compression // Optical Engineering. — 1998. — Vol. 37, no. 8. — P. 2284-2289.

66. Ruhl M., Hartenstein H., Saupe D. Adaptive partitionings for fractal image compression // Proceedings of the IEEE International Conference on Image Processing. — 1997. — Vol. 2. — P. 310-313.

67. Wohlberg B. E., De Jager G. Fast image domain fractal compression by DCT domain block matching // Electronics Letters. — 1995. — Vol. 31, no. 11,—P. 869-870.

68. PeregudaE. S. Acceleration of algorithm of fractal image compression // Proceedings of the SIBCON Conference on Control and Communications. — 2005. — P. 159-162.

69. Saupe D. Breaking the time complexity of fractal image compression // Albert-Ludwigs University at Freiburg: Technical Report 53. — 1994.

70. Belloulata K., Stasinski R., Konrad J. Region-based image compression using fractals and shape-adaptive DCT // Proceedings of the IEEE1.ternational Conference on Image Processing. — 1999. — Vol. 2. — P. 815-819.

71. Au О. C., Liou M. L., Ma L. K. Fast fractal encoding in frequency domain // Proceedings of the IEEE International Conference on Image Processing. — 1997. —Vol. 2. —P. 298-301.

72. Truong Т. K., Jeng J.-H., Reed I. S., Lee P. C., Li A. Q. A fast encoding algorithm for fractal image compression using the DCT inner product // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 4. — P. 529-535.

73. Wan C.-C., Hsieh C.-H. An efficient fractal image-coding method using interblock correlation search // IEEE Transactions on Circuits and Systems for Video Technology. — 2001. — Vol. 11, no. 2. — P. 257-261.

74. Hartenstein H., Saupe D. Lossless acceleration of fractal image encoding via the fast Fourier transform // Signal Processing: Image Communication. — 2000. — Vol. 16, no. 4. — P. 383-394.

75. Endo D., Hiyane Т., Atsduta K., Kondo S. Fractal image compression by the classification in the wavelet transform domain // Proceedings of the IEEE International Conference on Image Processing. — 1998. — Vol. 1. — P. 788-792.

76. Fisher Y. Fractal image compression: Theory and application. — New York: Springer-Verlag, 1995. — xviii, 341 p.

77. Yung-Gi Wu, Ming-Zhi Huang, Yu-Ling Wen. Fractal image compression with variance and mean // Proceedings of the IEEE International Conference on Multimedia and Expo. — 2003. — Vol. 1. — P. 353-356.

78. Zhou C.-G., Meng K., Qiu Z.-L. A fast fractal image compression algorithm based on average-variance function // The IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 2006. — Vol. E89-D, no. 3. — P. 1303-1308.

79. Amram E., Blanc-Talon J. Recursive histograms comparison for accelerating fractal image compression Электронный ресурс. //

80. Multimedia Signal Processing Group at the University of Konstanz: сайт. — 1997. — URL: http://www.inf.uni-konstanz.de/cgip/fractal2//pdf/AmB197.pdf (дата обращения: 18.10.2010).

81. Gotting D., Ibenthal A., Grigat R.-R. Fractal image coding and magnification using invariant features // Fractals. — 1997. — Vol. 5. — P. 65-74.

82. Curtis К. M., Neil G., Fotopoulos V. A hybrid fractal/DCT image compression method // Proceedings of the IEEE 14th International Conference on Digital Signal Processing. — 2002. — Vol. 2. — P. 1337-1340.

83. Melnikov G., Katsaggelos A. K. A jointly optimal fractal/DCT compression scheme // IEEE Transactions on Multimedia. — 2002. — Vol. 4, no. 4. — P. 413-422.

84. Melnikov G., Katsaggelos A. K. A non uniform segmentation optimal hybrid fractal/DCT image compression algorithm // Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. — 1998. — Vol. 5. — P. 2573-2576.

85. Thao N. T. A hybrid fractal-DCT coding scheme for image compression // Proceedings of the IEEE International Conference on Image Processing. — 1996. —Vol. 1. —P. 169-172.

86. Thao N. T. Local search fractal image compression for fast integrated implementation // Proceedings of 1997 IEEE International Symposium on Circuits and Systems. — 1997. — Vol. 2. — P. 1333-1336.

87. Zhao Y., Yuan B. Image compression using fractals and discrete cosine transform // Electronics Letters. — 1994. — Vol. 30, no. 6. — P. 474-475.

88. Zhao Y., Yuan B. A hybrid image compression scheme combining block-based fractal coding and DCT // Signal Processing: Image Communication. — 1996. — Vol. 8, no. 2. — P. 73-78.

89. Barthel K. U., Voye T. Adaptive fractal: image coding in the frequency domain // Proceedings of International Workshop on- Image Processing: Theory, Methodology, Systems and Applications. — 1994. — P. 33 38.

90. Simon B; Image coding using overlapping fractal transform in the wavelet domain- // Proceedings of the IEEE International' Conference on Image Processing. — 1996. — Vol. 1. - P. 177-180.

91. Krupnik H., Malah D., Karnin E. Fractal representation of images via the discrete wavelet transform // Eighteenth- Convention of Electrical and Electronics Engineers in Israel.—1995:;—P. 2.2.2.1-2.2.2.5.

92. Culik K., Dube S., Rajcani P. Efficient compression of wavelet coefficients for smooth and fractal-like1 data-II Proceedings of the Data Compression Conference. — 1993. — P!.234-243.

93. DonyR. D., Vrscay E. R. IFS coding- using an MPC network library // Proceedings of the IEEE Canadian Conference on Electrical and- Computer Engineering. — 1998: — Vol: 1. — P. 61-64.

94. Hamzaoui R:, Saupe D. Combining fractal image compression and vector quantization // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 2. —P. 197-208.

95. Wang Z., Zhang D., Yu Y. I-lybrid image coding based on partial fractal mapping // Signal Processing: Image Communication. — 2000: — Vol. 15, no. 9. —P. 767-779.

96. Tong C. S., Pi M.-H. Analysis of a hybrid fractal-predictive-coding compression scheme // Signal Processing: Image Communication. — 2003. —Vol: 18, no: 6. —P. 483-495.

97. Kovacs Т. A fast classification based method for fractal* image encoding // Image and Vision Computing. — 2008. — Vol. 26, no. 8. — P. 1129-1136.

98. Belloulata K. Fast fractal coding of subbands using a non-iterative block clustering // Proceedings of the SPIE Visual Communications and Image Processing. —2005. —Vol. 16, no. 1. —P. 55-67.

99. Chang H. Т., Kuo C. J. Iteration-free fractal image coding based on efficient domain pool design // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 3. —P. 329-339.

100. Gonzalez R. C., Woods R. E. Digital image processing. — 3rd ed. — Upper Saddle River, N. J.: Prentice Hall, 2008. — xxii, 954 p.

101. Pratt W. K. Digital image processing. — 2nd ed. — New York: Wiley, 1991.— xiv, 698 p.

102. Мирошников M. M., КушпильВ. И. Методологические вопросы исследования зрительного восприятия изображений в рамках иконики // Труды ГОИ им. С.И.Вавилова. — 1984. — Т. 57, вып. 191. — С. 4-10.

103. Rissanen J. Hypothesis selection and testing by the MDL principle // The Computer Journal. — 1999. — Vol. 42, no. 4. — P. 260-269.

104. Vitanyi P. M. В., Li M. Minimum description length induction, Bayesianism, and Kolmogorov complexity // IEEE Transactions on Information Theory. — 2000. — Vol. 46, no. 2. — P. 446-464.

105. Solomonoff R. J. The discovery of algorithmic probability // Journal of Computer and System Sciences. — 1997. — Vol. 55, no. 1. — P. 73-88.

106. HassaballahM., MakkyM. M., MahdyY. B. A fast fractal' image compression method based on entropy // Electronic Letters on Computer Vision and Image Analysis. — 2005. — Vol. 5, no. 1. — P. ЗО^Ю.

107. Jorgensen P. E. Т., Song M.S. Analysis of fractals, image compression, entropy encoding, Karhunen-Loeve transforms // Acta Applicandae Mathematicae, 2009. — Vol. 108, no; 3. — P. 489-508.110.111. 112.113.114.

108. Jutamulia S., Asakura Т., Balmguna R. D., De Guzman P. C. Autofocusing based on power-spectra analysis // Applied optics. — 1994. — Vol. 33, no. 26.—P. 6210-6212.

109. Knill D. C., Field D., Kersten D. Human discrimination of fractal images //• Journal of the Optical Society of America. — 1990. — Vol. A7. — P.1113-1123.