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

• Окунев, Вадим Вячеславович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Окунев, Вадим Вячеславович

Введение.

Глава 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 на некоторых классах изображений.

Список литературы диссертационного исследования кандидат технических наук Окунев, Вадим Вячеславович, 2010 год

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.