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

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

ВИНОКУРОВ Станислав Владимирович

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

Специальность — 05 13 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 2007

003159416

Работа выполнена в Московском государственном университете приборостроения и информатики

Научный руководитель

доктор технических наук, профессор Ульянов М В

Официальные оппоненты

доктор технических наук, профессор Мальцева С В

кандидат технических наук, доцент Остроух А В.

Ведущая организация

Московский государственный институт электроники и математики (технический университет)

Защита состоится 15 мая 2007 г. в 12 часов на заседании диссертационного Совета Д 212 119 02 в Московском государственном университете приборостроения и информатики (107996 Москва, Стромынка, 20)

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

Автореферат разослан 15 апреля 2007 г.

Ученый секретарь диссертационного совета Д212 119 02

У'"

к т н , доц '—■ Зеленко Г В

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

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

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

Состояние проблемы При разработке, исследовании и развитии методов фрактального сжатия изображений охватывается широкий круг проблем связанных с повышением временной эффективности методов фрактального сжатия изображений, их алгоритмического обеспечения, оценки качества алгоритмов сжатия и восстановления растровых изображений, в исследование и развитие которых внесли значительных вклад российские и зарубежные ученые Н А Ваганова, Д С Ватолин, Н Б Новинский, В В Нечепаев, М Barnsley, Т Bedford, J Bentley, А Bogdan, L Chen, F Dekkmg, Y Fisher, J R Fmkel, Friedman, M Gharavi-Alkhansan, R Hamzaoui, J Hutchinson, A Jacqum, W

Kinser, С Lee, S Leps0y, H Lm, В Mandelbrot, H Meadows, G 0ien, D Saupe, A Venetsanopoulos, L Wall, и др

Большинство современных публикаций по тематике исследования алгоритмов фрактального сжатия посвящены повышению временной эффективности фрактального кодирования Несмотря на интенсивные исследования в области классической теории алгоритмов фрактального сжатия растровых изображений некоторые вопросы остаются нерешенными В первую очередь это касается вопроса поиска эффективных методов построения систем итерируемых функций для заданного входного изображения Отметим в данном контексте работы Д С Ватолина (Московский государственный университет) по методам оптимизации алгоритмов фрактального сжатия статических растровых изображений и H А Вагановой (Институт вычислительной математики и математической геофизики) по методам фрактального сжатия динамических изображений Большой вклад в разработку методов обработки растровых изображений внесли работы, выполненные в институте систем обработки изображений РАН, в частности работы В В Сергеева и В А Сойфера

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

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

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

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

Достижение поставленной цели предполагает решение следующих основных задач

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

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

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

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

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

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

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

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

3 Разработан ресурсно-эффективный комбинированный алгоритм фрактального сжатия статических изображений

Практическая ценность результатов работы заключается в возможности решения

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

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

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

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

Реализация результатов работы Результаты работы использованы и внедрены в составе результатов научно-исследовательских работ, выполненных в ЗАО «СмартЛайн Инк» по следующим программным системам

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

в ЗАО «Смартлайн Инк», подтвержденное актом о внедрении — разработаны комбинированные временно-эффективные алгоритмические решения для фрактального сжатия статических изображений,

На основе результатов диссертационного исследования разработано программное обеспечение алгоритма фрактального сжатия растровых изображений с применением метода пространственно-чувствительного хеширования, зарегистрированное в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (№2006611251 от 18 06 06) Использование результатов диссертационной работы при разработке программных систем подтверждено актами о внедрении

Основные результаты, выносимые на защиту:

1 Применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение (х ,c)-NN задачи) в применении к фрактальному сжатию изображений

2 Способ построения семейства хеш-функций, адаптированных к фрактальному сжатия изображений

3 Асимптотические оценки временной эффективности разработанного алгоритма фрактального сжатия изображений

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

Апробация работы Основные положения и результаты диссертационной работы докладывались на всероссийских конференциях и семинарах I Всероссийский семинар аспирантов, 2006 г, Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2005 г , VIII Всероссийской научно-технической конференции «Новые информационные технологии», Москва, 2005 г, VIII Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2005 г,

Публикации По материалам диссертации опубликованы 8 печатных работ, из них 2 статьи в ведущих научных журналах, рекомендованных ВАК РФ (Автоматизация и современные технологии №12, 2005, Открытое образование, 4(57)'200б), 3 публикации в журналах и межвузовских сборниках научных трудов, 3 публикации в научных трудах международных и всероссийских конференций

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, приложения и библиографического списка Общий объем работы — 120 страниц текста, из них 110 страниц — основное содержание, включая 7 рисуноков и 3 таблицы, 3 страницы — приложение (акт о внедрении результатов работы в ЗАО «СмартЛайн Инк », свидетельство об официальной регистрации программы для ЭВМ), 9 страниц — библиографический список (125 наименований)

СОДЕРЖАНИЕ РАБОТЫ Во введении дана "краткая характеристика решаемой проблемы, обоснована актуальность темы, сформулированы цель исследования, научная новизна, практическая ценность работы, основные положения, выносимые на защиту, достоверность и обоснованность научных положений диссертации, апробация работы

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

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

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

В главе 2 «Фрактальное сжатие изображений при помощи поиска ближайшего соседнего элемента» кратко изложена идея Д Саупа о сведении задачи фрактального сжатия изображений к задаче поиска ближайшего соседнего элемента в многомерном пространстве, которая позволяет отойти от полного перебора всех комбинаций пар доменных и ранговых блоков и, путем относительно эффективной предобработки, свести эту задачу к задаче поиска ближайшего соседнего элемента в многомерном метрическом пространстве

Предположим, что растровое изображение разделено на не перекрывающиеся ранговые блоки размером N х N (обычно 4x4 или 8x8 пикселей), и доменные блоки вдвое большего размера При этом над каждым доменным блоком выполняются операции усреднения и фильтрации так, чтобы его результирующий размер был равен размеру рангового блока Л/"х N Будем рассматривать каждый ранговый блок с номером т как вектор Ят в линейном векторном пространстве

ЭТ", где п = Ых N, т = \, ,пг, пг — общее число ранговых блоков Преобразование растрового квадратного изображения со стороной квадрата длиной N в вектор длиной И2 можно выполнить, например, построчным сканированием Работа с векторами вместо двумерных массивов значительно упрощает запись, без потери общности рассмотрения

Обозначим через Ок вектор, представляющий доменный блок, где к — 1, ,п<1, а па — общее число доменных блоков Введем в рассмотрение множество В, состоящее из р независимых от изображения блоков, причем р<п Представим их векторами 5,,5,, ъВр ей", которые выбираются таким образом, чтобы они образовывали ортонормированный базис р -мерного подпространства

в 3?" Их называют фиксированными базисными блоками В процессе сжатия изображения для каждого рангового блока необходимо выполнить поиск по всем доменным блокам При этом задача кодирования рангового блока Ят формулируется как задача нахождения аффинных коэффициентов, минимизирующих ошибку

Е{А.ЛЯ)= пир к-(Я ^ + = тш ||Лт -(1)

где А - это пх(р +1) матрица, столбцы которой есть вектора Пк,В1,В2, ,Вр,а х = (а,Ь1УЬг, ,Ьр) е ЭТР+' —вектор коэффициентов Данная задача должна быть решена для всех доменных блоков О^., и блок, который дает наименьшее значение ошибки Е(Ок,Ят), выбирается при условии, что значение а для данного блока обеспечивает сходимость процесса декодирования (те |а| < 1)

1= «впип {Е(£>к, Л»)}, Н < 1

0„ 4=1 Щ

Введем в рассмотрение ортогональный оператор Р, который проецирует

)

9?" в подпространство 3 с базисом ВХ,В2, ,Вр Ранговый блок Ят имеет уникальное разложение Ят - ОЯт +Р/?И, где оператор О проецирует свой операнд на ортодополнение З1 Для 2 = (г,, ) е 9?" \ 3, определим оператор

= (2)

В данных обозначениях базовый результат, полученный Д Саупом имеет вид ОД,Лт)= {Ят,ф(Ят))^~{Ф{Ок),ф{'Кт))2 ,

где {,) — скалярное произведение двух векторов Таким образом, задача о минимизации ошибки E{Dk,Rm) для фиксированного Rm и всех доменных блоков Dk может рассматриваться с точки зрения углового критерия Минимум E(Dk,Rm) достигается тогда, когда скалярное произведение векторов (ф(Ок),ф{Ят))2 максимально, так как

(ф(Вк),ф(Ят))2 = cos2 ^ф(Ок)ЖК,У) Это означает необходимость минимизации угла А(ф(Ок),ф(Кт)), или, что эквивалентно, Z(ODk, ORm) Таким образом, задача фрактального сжатия изображения (в смысле поиска Dk для Rm) сводится к задаче о поиске ближайшего соседнего к данному ранговому блоку — вектору Rm доменного блока — вектора Dk в линейном пространстве 31" \ 3

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

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

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

Вначале кратко рассмотрена основная идея метода пространственно-чувствительного хеширования применительно к поиску ближайших доменных блоков Для множества точек S, содержащего проекции доменных блоков

= ф{йк) и ранговых блоков Я^ =ф(Ит) на 5?" \3, с Евклидовой мерой расстояния аЕ, семейство ЬБН функций определено в следующим образом

Множество хеш-функций Я = {/г 5 —» £/} называется (г1,г2,р],р2)-чувствительными для ¿Е, если для любой проекции рангового и доменного блока е 5 на 3?" \3 выполняется

если ¿^еД^.г,), то Ргя[Л(^) = Л(А±)]>/>„ если то Ргя[А(^) = А(£>4±)]<р2

где В(х,г) — гиперсфера радиусом г в смысле меры расстояния йЕ с центром в точке х, а Рг„ ) = )] — вероятность того, что хеш-функция образует коллизию для данных проекций рангового и доменного блока и £>4А

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

П <Г2

В специальной литературе принято обозначать задачу приближенного поиска соседнего элемента как (т ,е,)-ЬЛМ задачу, при этом гх = т и г2 = с г Покажем, как пространственно-чувствительные функции могут быть использованы для решения задачи при фрактальном сжатии, для данного семейства Н хэш-функций, обладающих параметрами (Г\,г2,р^р2), увеличим разрыв между «высокой» вероятностью р, и «низкой» вероятностью р2 путем соединения нескольких функций В частности, для параметра К, значение которого будет установлено ниже, определим семейство функций = ^ Л1 —> ¿7 *} так что g(D¡;) = (h\{D^), где А, е Н Для целого числа Ь выберем I функций из ЧР, независимо и равномерно, случайным образом Во время шага предварительных вычислений, сохраним каждую проекцию доменного блока Й4хб5 в наборе gJ(D^), для каждого 7 = 1, Так как общее число таких множеств может быть велико, оставим только непустые наборы путем

возврата к классическому хешированию Для того чтобы обработать ранговый блок Ят, производим поиск среди всех множеств ¿¡(Я^), -,,§¿(70 Так как возможно (хотя и маловероятно) что общее количество доменов, сохраненных в этих множествах велико, то поиск домена прерывается после нахождения 3£ элементов (включая дубликаты) Пусть О,1, ,£>/" —найденные элементы Для каждого домена Д , возвращаем ответ «ДА» (т е данный домен является потенциальным кандидатом построения преобразования в ранговый блок Ят), если £>, , еВ(Я^,г2), иначе возвращаем ответ «НЕТ» Параметры К и £ выбираются так, чтобы гарантировать, что следующие два свойства выполняются с заданной вероятностью

1 Если существует 0*к е В(Я^,г1), то gJ(D*k) = gJ(Я„) для некоторого у = 1 Ь

2 Общее количество коллизий Я^ с точками из 5 — ,г2) меньше чем ЗЬ (параметр определен эмпирическим путем) то есть

£|(5 - ВД\г2)) п < 31

Если выполняются оба свойства, то алгоритм является корректным Отсюда следует, что если установить К = 1о§(1 / р2), и Ь-пр, где

1п(1 //>,)

1п(1 /р2У

то свойства (1) и (2) выполняются с постоянной вероятностью В области пространственно чувствительного хеширования описан результат обычно формулируемый в виде теоремы, определяющей зависимость эффективности решения (т, с^-ГчТч задачи при фрактальном сжатии изображений от параметров метода

Предположим, существует (г,с г,р^,рг)-чувствительное семейство функций хеширования Н для меры расстояния йЕ Тогда существует алгоритм для решения (г ,с)-ЫЫ задачи для меры йР, который использует О^п,/

памяти, с временем обработки одного запроса определяемым 0(п/) вычислений расстояния и 0(п/ 1о§(1 /р2) пг1) вычислений хеш-функций из Н, где р определен как (3)

Далее в главе рассмотрены вопросы адаптации пространственно-чувствительных хеш-функций к фрактальному сжатию изображений на основе р-устойчивых распределений Распределение ц над 3? называется р-устойчивым, если существует р> 0 такое, что для любых й действительных чисел V,, и переменных Хх, ,ХЛ с распределением ц, случайная переменная имеет такое же распределение, как и переменная р X, где X — случайная переменная с распределением ц

Известно, что устойчивые распределения существуют для любого р е (0,2] В частности гауссово (нормальное) распределение /иа, определенное как функция плотности вероятности

является 2-устойчивым

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

- относительно невелико), то они должны с большой вероятностью

вызывать коллизию (иметь одно и то же значение хеш-функции) и, если они расположены далеко друг от друга, то вероятность коллизии должна быть мала Пусть а — вектор размерности <1, элементы которого выбираются независимо из ¿»-устойчивого распределения Скалярное произведение проецирует

каждый вектор на множество действительных чисел Из ^-устойчивости следует, что для двух векторов Л^, расстояние между их проекциями

- распределено как - X, где X — это случайная пе-

ременная, выбранная из ^-устойчивого распределения Если «разделить» мно-

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

Формально, каждая хеш-функция й„6(у) 31—> N отображает вектор V

размерности й (проекция рангового или доменного блока) на множество целых чисел Каждая хеш-функция в семействе однозначно определяется выбором случайного вектора а, определенного выше, и действительного числа Ъ, выбранного случайным образом из диапазона [0, г] Для данных а,Ь определена хеш-функция

(а, у ) + Ь

Mv) =

г

Известно, что хэш-функция hlb является (г,,г2,рх,рг)-чувствительной для р, = р(1) и р2 = р(с) при г, !гх = с и доказано, что для фиксированного параметра г вероятность коллизии монотонно уменьшается с ростом с = -

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

(a,v ) + Ь

H = \hjy) =

ae5R ,èe9î,rs9l>

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

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

В главе 4 «Программная реализация эффективного алгоритма фрактального сжатия изображений, его применение и эксплуатация» предложена программная реализация алгоритма фрактального сжатия изображений с применением пространственно-чувствительных хэш-функций Алгоритм состоит из двух этапов: на этапе предварительных вычислений для всех векторов, представляющих доменные блоки вычисляется их ортонормированная проекция Пк = ф(Ок) на ортодополнение З1 Определение оператора ф{х) было дано выше Далее, для полученных точек е 9?" \ 3 вычисляются и сохраняются значения хеш-функций g¡(D^) по формуле (4)

Алгоритм; 1А (этап предварительных вычислений РгасЬБН)

ВХОД Доменный пул £>, , количество хеш-таблиц Ь ВЫХОД Хеш-таблицы Т,, г = 1, ,1 ДЛЯ КАЖДОГО 1 = 1,

Инициализировать хеш-таблицу Т, путем генерации случайной хеш-функции #,() ДЛЯ КАЖДОГО г = 1, ,Ь ДЛЯ КАЖДОГО 7 = 1,

Сохранить точку £И" в наборе gl(Df) хеш-таблицы Т( На этапе поиска доменно-ранговых соответствий для данного рангового блока вычисляется ортонормированная проекция Я^ = ф{Ят) на ортодополнение 3х Вычисляется значение хеш-функций g¡(R^)> и производится линейный поиск в таблицах хеш-функций доменных блоков, вычисленных ранее Алгоритм 1Б (поиск доменно-ранговых соотношений РгасЬБН)

ВХОД Ранговый блок ЯМ (максимальное число доменных блоков-кандидатов, которые должен возвратить алгоритм) ВЫХОД М (или меньше) доменных блоков - кандидатов

ДЛЯ КАЖДОГО 1 = 1, ,1

0.4— Ои{точки, найденные во множестве хэш-таблицы

Возвратить М ближайших соседних элементов из множества О (находятся линейным поиском среди всех кандидатов)_

Благодаря свойствам пространственно-чувствительных хеш-функций, при совпадении хеш-значений для рангового и доменного вектора, существует очень высокая вероятность того, что данные вектора лежат близко друг другу в заданном (в нашем случае в Евклидовом) метрическом пространстве Для М найденных доменных блоков кандидатов производится вычисление ошибки Е(0,,Ит), 1 = 1, ,М по формуле (1) и выбирается наиболее подходящий блок Таким образом, мы избегаем необходимости решать задачу для каждой пары до-менно-ранговых блоков, а отбираем лишь несколько кандидатов, которые с большой вероятностью дадут решение, близкое к оптимальному Этим и достигается существенное повышение временной эффективности предлагаемого алгоритма

Далее в главе приведена оценка временной эффективности алгоритма РгасЬЗН Показано, что при соответствующем выборе параметров алгоритма для одного запроса количество операций вычисления функции расстояния определяется как 0(п/), а количество операций вычисления хеш-функции, соответственно, как пг1), где па — общее количество доменных блоков, а остальные параметры были определены выше, р < 1 Таким образом, достигается сублинейное время обработки одного рангового блока, что является большим шагом вперед по сравнению с классическими алгоритмами фрактального сжатия

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

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

деревьев для решения задачи поиска ближайшего соседнего элемента. Алгоритм FracANN создает промежуточную структуру данных — kd-дерево, размером O(rij) и глубиной Oflog(«j)}. Общее время конструирования такого дерева асимптотически составляет O(log(nd ) ■ nd).

На рис. 1 приведена диаграмма зависимости качества восстановленного изображения (PSNR, dB), определяемого общепринятым способом, от времени сжатия изображения предложенным алгоритмом и алгоритмом FracANN. Второй алгоритм является адаптацией известной библиотеки ANN, которая реализует поиск ближайшего соседнего элемента, используя один из вариантов реализации kd-дерева.

Рисунок 1. Сравнение алгоритмов РгасЬБН и РгасАМ^ Изображение разбивалось на ранговые блоки размером 4x4 пикселя. В обоих случаях испытания проходили на компьютере с процессором Реп?шт-4 2,4 вН? без поддержки технологии HyperThreadiпg. Изменение соотношения «время сжатия — качество» достигалось варьированием параметров К, Ь, М предложенного алгоритма и параметров М, £ алгоритма РгасАКК Как видно из рис. 1 при малом времени сжатия алгоритм РгасЬЗН опережает алгоритм ЯгасАЫЫ по качеству восстановленного изображения. При одинаковом качестве восстановленного изображения (PSNR~31dB) время работы предложенного алгоритма в 3 раза меньше времени работы алгоритма FracANN. При дальнейшем увеличении времени сжатия (рафики сливаются в одну линию, обеспечивая одинаковое соотношение для восстановленного изображения.

В Заключении по диссертации сформулированы основные результаты и перспективы развития исследований

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

2 Предложено использовать пространственно чувствительные хеш-функции в качестве метода, обеспечивающего решение задачи (х, çj-NN для задачи фрактального сжатия изображений с наилучшими временными оценками

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

4 На основе полученных результатов разработан эффективный алгоритм фрактального сжатия статических растровых изображений

5 Получена асимптотическая оценка временной эффективности разработанного алгоритма

6 Проведено сравнительное экспериментальное исследование разработанного алгоритма с одним из наиболее распространенных алгоритмов фрактального сжатия использующим kd-деревья Полученные результаты подтверждают эффективность разработанного алгоритма на значениях PNSR до 32,5

7 Внедрение результатов работы в систему подготовки мультимедия информации к тиражированию и распространению, применяемую в ЗАО «Смарт-лайн Инк», подтвержденное актом о внедрении, позволило уменьшить время подготовки одного мультимедиа носителя по сравнению с алгоритмическим решением на основе Frac ANN в среднем в 1,2 раза, и увеличить в среднем на 20% объем публикуемой информации по сравнению с решением на основе алгоритма JPEG

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Винокуров, C.B. Особенности фрактального сжатия изображений [Текст] / С В Винокуров // Автоматизация и современные технологии науч -тех журн — M Машиностроение - ISSN 0869-4931 -2005 -№12 - С 27-32

2 Винокуров C.B. Методы повышения временной эффективности алгоритмов фрактального сжатия изображений [Текст] / С В Винокуров // Информатика сборник, материалы конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» - МГАПИ - ISBN 5-8068-0328-7 - 2005 -С 53-59 -бОэкз

3 Винокуров C.B. Подход к фрактальному сжатию изображений с использованием пространственно-чувствительного хеширования [Текст] / С В Винокуров // Методы и модели автоматизации управления сборник научных трудов - МАДИ -УДК 625 08 -ГТУ -2006 - С 14-19 -ЮОэкз

4 Винокуров C.B. Построение пространственно-чувствительных хеш-функций, адаптированных к задаче фрактального сжатия изображений [Текст] / С В Винокуров // Методы автоматизации управления сборник научных трудов - МАДИ -УДК 625 08 - ГТУ, 2006, - С 19-25 - 100 экз

5 Винокуров C.B. Оценка временной эффективности алгоритма фрактального сжатия изображений с использованием пространственно-чувствительного хеширования [Текст] / С В Винокуров // Новые информационные технологии Сборник трудов IX Всероссийской научно-технической конференции - МГУПИ - ISBN 5-8068-0350-3 - 2006 - С 25-29 - 100 экз

6 Винокуров C.B. Эффективный алгоритм фрактального сжатия изображений с использованием пространственно-чувствительного хеширования [Текст] / С В Винокуров//Открытое образование науч-прак журн / учредители МЭСИ, МАОО -2006 - №4 (57) - С 62-70

7 Винокуров C.B. Комплексный критерий качества алгоритмов сжатия и восстановления растровых изображений на основе нормированных оценок [Текст] / С В Винокуров, M В Ульянов // Вестник МГУПИ Серия «Технические и естественные науки» - 2006 - №7 - С 43-52

8 Винокуров C.B. Обоснование использования пространственно-чувствительного хеширования при фрактальном сжатии изображений [Текст] / С В Винокуров // Задачи системного анализа, управления и обработки информации Межвузовский сборник научных трудов - Вып 1 -М МГУП - ISBN 5-8122-0721-6 -2006 - С 96-99 ил - 60 экз

ЛР № 020418 от 08 октяфя 1997 г

Подписано к печати 05 04 2007 г Формат 60x84 1/16 Объем 1,25 п л Тираж 100 экз Заказ № 56

Московский государственный университет приборостроения и информатики

107996, Москва, уп Стромынка, 20

ВВЕДЕНИЕ.

ГЛАВА 1. ФРАКТАЛЬНОЕ СЖАТИЕ ИЗОБРАЖЕНИЙ, ЕГО

ОСОБЕННОСТИ И ОБСЛАСТИ ПРИМЕНЕНИЯ.

Введение.

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

1.2. Фрактальное сжатие изображений в градациях серого.

1.3. Методы повышения временной эффективности фрактального алгоритма.

1.4. Фрактальное сжатие цветных изображений.

1.5. Особенности и области применения фрактального сжатия.

2.1. Математические основы фрактального сжатия с использованием ближайшего соседнего элемента.57

2.2. Современные методы поиска ближайшего соседнего элемента в многомерном метрическом пространстве.61

Заключение.71

ГЛАВА 3. АДАПТАЦИЯ ПРОСТРАНСТВЕННО-ЧУВСТВИТЕЛЬНОГО ХЕШИРОВАНИЯ ДЛЯ СОЗДАНИЯ ЭФФЕКТИВНЫХ МЕТОДОВ

ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ.72

Введение.72

3.1. Понятие пространственно-чувствительного хеширования.72

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

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

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

Заключение.83

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПРИМЕНЕНИЕ И ЭКСПЛУАТАЦИЯ ЭФФЕКТИВНОГО АЛГОРИТМА ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ.84

Введение.84

4.1. Описание алгоритма фрактального сжатия при помощи пространственно чувствительного хеширования (FracLSH). 84

4.2. Оценка временной эффективности алгоритма FracLSH. 91

4.3. Комплексный критерий качества алгоритмов сжатия и восстановления растровых изображений на основе нормированных оценок. 92

4.4. Сравнение FracLSH с другими современными алгоритмами сжатия изображений. 102

Заключение. 106

ЗАКЛЮЧЕНИЕ. 107

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.110

ПРИЛОЖЕНИЕ. 121

ВВЕДЕНИЕ

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

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

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

Состояние проблемы

При разработке, исследовании и развитии методов фрактального сжатия изображений охватывается широкий круг проблем связанных с повышением временной эффективности методов фрактального сжатия изображений, их алгоритмического обеспечения, оценки качества алгоритмов сжатия и восстановления растровых изображений, в исследование и развитие которых внесли значительных вклад российские и зарубежные ученые: Н. А. Ваганова, Д. С. Ватолин, Н.Б. Новинский, В.В. Нечепаев, М. Barnsley, Т. Bedford, J. Bentley, A. Bogdan, L. Chen, F. Dekking, Y. Fisher, J. R. Finkel, Friedman, M. Gharavi-Alkhansari, R. Hamzaoui, J. Hutchinson, A. Jacquin, W. Kinser, C. Lee, S. Lepsey, H. Lin, B. Mandelbrot, H. Meadows, G. 0ien, D. Saupe, A. Venetsanopoulos, L. Wall, и др.

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

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

Объект исследования

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

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

Научная новизна диссертации заключается в:

1. Обосновано применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение fr,cj-NN задачи) в применении к фрактальному сжатию изображений.

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

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

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

Основные результаты, выносимые на защиту:

1. Применение метода пространственно чувствительных хэш-функций для поиска множества ближайших соседних элементов (решение fr,cJ-NN задачи) в применении к фрактальному сжатию изображений.

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

3. Асимптотические оценки временной эффективности разработанного алгоритма фрактального сжатия изображений.

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

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

Основные положения и результаты диссертационной работы докладывались на всероссийских конференциях и семинарах: I Всероссийский семинар аспирантов, 2006 г.; Международном научно-техническом семинаре «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 2005 г.; VIII Всероссийской научно-технической конференции «Новые информационные технологии», Москва,

2005 г.; VIII Международной научно-практической конференции «Фундаментальные и прикладные проблемы приборостроения, информатики, экономики и права», Сочи, 2005 г.;

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ

Rm — ранговый блок с номером т, представленный как вектор, полученный путем построчного сканирования соответствующей области изображения в линейном векторном пространстве 91".

Dk — ранговый блок с номером к, представленный как вектор, полученный путем построчного сканирования соответствующей области изображения в линейном векторном пространстве 9Г. d(-,-) — функция, вычисляющая расстояние между своими операндами представляющими точки в полном метрическом пространстве. s — коэффициент масштабирования (scaling). о — смещение (offset). w(-) — сжимающее (как правило афинное) преобразование. fix, у) —изображение, рассматриваемое как вещественная функция. ЕЩ„,Ц) — функция, вычисляющая ошибку приближения (расстояние, между ранговым и доменным блоками.

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

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

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

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

Перспективы развития исследований

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

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

- Совмещение данного метода с другими метода повышения временной эффективности фрактального сжатия, или с векторным квантованием.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

1. Александров В.В., Горский Н.Д. Представление и обработка изображений: рекурсивный подход II Jl-д.: Наука 1985, 190 с. СойферОЗ] В. А. Сойфер. Методы компьютерной обработки изображений, ФИЗМАТЛИТ 2003, 784 с.

2. Алимов Ш.А. Принцип сжатых отображений (Методы прикладного анализа). М.: Знание, 1983.64 с.

3. Балханов В.К. Введение в теорию фрактального исчисления. Улан-Удэ: Б ГУ, 2001.

4. Божокин С.В., Паршин Д.А. Фракталы и мулътифракталы. М., Ижевск: РХД, 2001.

5. Бондаренко В.А., Дольников В.Л. Фрактальное сжатие изображений по Барнсли-Слоану,! Автоматика и телемеханика. 1994. №5. С.12-20.

6. Ваганова Н. А., Фрактальное сжатие динамических изображений, Информационные технологии, Новосибирск 1999.

7. Васильев К.К., Наместников С.М. Анашз методов сжатия изображений при разных критериях оценки качества восстановленного изображения. Труды IX международной научно-технической конференции «Радиолокация, навигация, связь», Воронеж, 2003, с. 1060-1067.

8. Ватолин Д. С., Фрактальное сжатие изображений, Computerworld N06,1996.

9. Ватолин Д.С., Использование ДКП для ускорения фрактального сжатия изображений, Программирование, Номер 3, 1999, стр. 51-57.

10. Ватолин Д.С. Алгоритмы сжатия изображений И ISBN 5-89407-041-4 М.: Диалог-МГУ, 1999.

11. Ватолин Д.С. Тенденции развития алгоритмов архивации графики // Открытые системы. Номер 4, 1995.

12. Вишик М.И. Фрактальная размерность множеств. II Соросовский образовательный журнал, № 1, 1998.

13. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах научных исследований. М.: Наука, 1982. - 213 с.

14. Горбачев А.А. Колданов А.П., Потапов А.А., Чигин Е.П., Нелинейная радиолокация. Серия "Фракталы. Хаос. Вероятность", М.: Радиотехника, 2005.

15. Гонсалес Р., Вудс Р., Цифровая обработка изображений — М.: Техносфера, 2005. — 1072 с.

16. Добеши И .Десять лекций по вейвлетам И Пер. с анг. Е.В. Мищенко, под ред. А.П.Петухова. М.: Ижевск 2001,464 стр.

17. Дьяконов В. П., Вейвлеты. От теории к практике. Изд. 2-е, перераб. И доп. М.: СОЛОН-Пресс, 2004. - 400 с.

18. Забарянский С.Ф. Фрактальное сжатие изображений. // Компьютеры + программы, № 6(39), 1993.

19. Зельдович Я.Б., Соколов Д.Д. Фракталы, подобие, промежуточная асимптотика. IIУФН, Т. 14, Вып. 3, 1985.

20. Иванов С.С. Оценка фрактальной размерности самоаффинных множеств: метод встречного масштабирования дисперсий. II ДАН, 1993, N 1, Т.332.

21. Карпов П.М. Быстрый фрактачьный алгоритм сжатия изображений, Научная сессия МИФИ, 2006. Том 15.

22. Колмогоров А.Н. К логическим основам теории информации и теории вероятностей. //Проблемы передачи информации, 1969, том V, вып. 3, сс. 3-7.

23. Морозов А.Д., Введение в теорию фракталов. Москва-Ижевск: Институт компьютерных исследований, 2004, 160 стр.

24. Павлидис Т. Алгоритмы машинной графики и обработка изображений И М.: Радио и связь 1986, 400 с.

25. Потапов А.А., Фракталы в радиофизике и радиолокации: Топология выборки. II Университетская книга, 2005.

26. Претт У. Цифровая обработка изображений в двух томах // М.: Мир 1982,790 с.

27. Розеншельд А. Распознавание и обработка изображений II М.: Мир 1972,232 с.

28. Смирнов Б.М. Физика фрактальных кластеров. М.: Наука, 1991.

29. Сойфер В.А., Сергеев В. В., Попов С. Б., Мясников В. В., Теоретические основы цифровой обработки изображений.; М-во образования Рос. Федерации и др. -Самара : СГАУ, 2000. 255 с.

30. Сойфер В.А., Компьютерная обработка изображений, Часть 1. Математические модели. Соросовский образовательный журнал N2, 1996.

31. Сойфер В. А., Компьютерная обработка изображений, Часть 2. Методы и алгоритмы. Соросовский образовательный журнал N2, 1996.

32. Странные аттракторы. // Под редакцией Синая Я.Г. и Шильникова Л.И. -М.: Мир, 1981.

33. Транковский С. Красота хаоса // Наука и жизнь, № 4, 1994.

34. Шабаршин А. А. Фрактальное сжатие и восстановление видеоинформа-ijuu в реальном масштабе времени, Научные школы УПИ-УГТУ 1997.

35. Шабаршин А.А. Метод фрактального сжатия изображений, Научные школы УПИ-УГТУ 1997. №1. С.70-82.

36. Шредер М. Фракталы, хаос, степенные законы. М., Ижевск: РХД 2001.

37. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособ.- М.: Изд. Триумф, 2003 320 с. Эфрос82] Эфрос A.JT. Физика и геометрия беспорядка. - М.: Наука, 1982.

38. Федер Е. Фракталы. М.: Мир, 1991.

39. Фоменко А.Т. Наглядная геометрия и топология. М.: МГУ-ЧеРо, 1998.

40. Фракталы. И Компьютерная газета, N 36 (226), 1999.

41. Яншин В.В. Анализ и обработка изображений (принципы и алгоритмы) II М.: Машиностроение, 1995.

42. ANN: Approximate Nearest Neighbors, http://www.cs.umd.edu/~mount/ANN.

43. Arya S., Mount D.M., Netanyahu N. S., Silvernam R., Wu A., An optimal algorithm for approximate nearest neighbour searching, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994) 573-582.

44. Bani-Eqbal В., Speeding up fractal image compression, in: Proceedings from IS&T/SPIE 1995 Symposium on Electronic Imaging: Science & Technology, Vol. 2418: Still-Image Compression 1995.

45. Barnsley M. F., Fractals Everywhere, New York: Academic, 1988.

46. Barthel K. U., Schiittemeyer J., Voye Т., Noll P., A new image coding technique unifying fractal and transform coding, in: Proc. ICIP-94 IEEE International Conference on Image Processing, Austin, Texas, Nov. 1994.

47. Bedford Т., Dekking F.M., Keane M. S., Fractal image coding techniques and contraction operators, Nieuw Arch. Wisk. (4) 10,3 (1992) 185-218.

48. Breazu M., Toderean G., Region-based fractal image compression using deterministic search, IEEE ICIP 98, Chicago, Oct. 1998.

49. Bogdan A., Meadows H., E., Kohonen neural network for image coding based on iteration transformation theory, in: Proceedings from SPIE Neural and Stochastic Methods in Image and Signal Processing, Vol. 1766, pp. 425-436, 1992.

50. Boss R. D., Jacobs E. W., Archetype classification in an iterated transformation image compression algorithm, in: Fractal Image Compression Theory and Applications, Y. Fisher (ed.), Springer-Verlag, New York, 1994.

51. Burkhard W. A., Keller R. M. Some approaches to best-match file searching. Commun. ACM, 16:230-236, 1973.

52. Caso G., Obrador P., Kuo C.-C. J., Fast methods for fractal image encoding, in: Proceedings from IS&T/SPIE 1995 Symposium on Electronic Imaging: Science & Technology, Vol. 2501, pp. 583-594, 1995.

53. Chambers J.M., Mallows C.L., and Stuck B. W. A method for simulating stable random variables. J. Amer. Statist. Assoc., 71:340-344, 1976.

54. Chavez E., Navarro G., Baeza-Yates R., and Marroquin J. L. Searching in metric spaces. ACM Computing Surveys, 33(3): 273-321, 2001.

55. Ciscar G., On entropy coding Fisher's fractal quadtree code, June 1996.

56. Darrell Т., Indyk P., Shakhnarovich G. (eds.), Locality-sensitive hashing using stable distributions, Nearest Neighbor Methods in Learning and Vision: Theory and Practice, MIT Press, 2006.

57. Dekking F.M., An inequality for pairs of martingales and its applications to fractal image coding, Technical Report 95-10, Faculty of Technical Mathematics and Informatics, Delft University of Technology, 1995.

58. Dekking F.M., Fractal image coding: some mathematical remarks on its limits and its prospects, Technical Report 95-95, Faculty of Technical Mathematics and Informatics, Delft University of Technology, 1995.

59. Devroye L., Gyorfi L., Lugosi G. A Probabilistic Theory of Pattern Recognition. Springer-Verlag, New York, 1996.61 . Dony R., Vrscay E., IFS coding using an MPC network library, 1998 Canadian Conf. Eleclr. and Сотр. Engineering, ON, May 1998.

60. Fibush D.K. Practical application of objective picture quality measurements, Broadcasting Convention, 1997. International Volume , Issue , 12-16 Sep 1997. pp. 504 -513.

61. Fisher Y., Fractal image compression, SIGGRAPH'92 Course Notes. 1992. Vol.12. P.7.1-7.19, 21 p.

62. Fisher Y., Fractal Image Compression: Theory and Application. New York: Spriger-Verlag, 1995.

63. Fix E., Hodges J. L. Jr., Discriminatory analysis, non-parametric discrimination. Technical Report 4, USAF School of Aviation Medicine, 1951. Project 21-49-004.

64. Friedman J. H., Bentley J. L., Finkel R. A., An algorithm for finding best matches in logarithmic expected time, ACM Trans. Math. Software 3,3 (1977) 209-226.

65. Frigaard C., Gade J., Hemmingsen Т., Sand Т., Image compression based on fractal theory, Institute for Electronic Systems, Aalborg University, Denmark, 1994.

66. Forte В., Vrscay E. R., Solving the inverse problem for function/image approximations using iteratedfunction systems, I. Theoretical basis, Fractals 2,3 (1994) 325-334.

67. Gharavi-Alkhansari M., Fractal-based image and video coding using matching pursuit, PhD Thesis, University of Illinois, 1997.

68. Gray R.M., Neuhoff D. L. Quantization. IEEE Trans. Inform. Theory, 44:23252383,1993.

69. Hamzaoui, Codebook clustering by self-organizing maps for fractal image compression, in: NATO ASI Conf. Fractal Image Encoding and Analysis, Trondheim, July 1995, to appear in a special issue of Fractals.

70. Hjaltason G.R., Samet H. Index-driven similarity search in metric spaces. ACM Trans. Database Syst. 28(4):517-580, 2003.

71. Hurtgen В., Stiller C., Fast hierarchical codebook search for fractal coding of still images, in: EOS/SPIE Visual Communications and PACS for Medical Applications'93, Berlin, 1993.

72. Hurtgen В., Performance bounds for fractal coding, Proceedings oflCASSP-1995 IEEE International Conference on Acoustics, Speech and Signal Processing, Vol. 4, Detroit, 1995.

73. Hutchinson J., Fractals and self-similarity, Indiana Univ. J. Math. 30, 713-7471981).

74. Indyk P., Motwani R. Approximate nearest neighbor: towards removing the curse of dimensionality. Proceedings of the Symposium on Theory of Computing, 1998.

75. Indyk P. Stable distributions, pseudorandom generators, embeddings and data stream computation. Proceedings of the Symposium on Foundations of Computer Science, 2000.

76. Jacquin, A.E., A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding, PhD Thesis, Georgia Institute of Technology, 1989.

77. Jacobs E. W., Fisher Y., Boss R. D., Image compression: A study of the iterated transform method, Signal Processing 29 (1992) 251-263.

78. Kominek J., Algorithm for fast fractal image compression, Proceedings of SP1E, Volume 2419, 1995.

79. Knuth Donald Ervin. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Boston, 1998.

80. Lee C.-H., Chen L. H., Fast closest codeword search algorithm for vector quantization, IEE Proc.-Vis. Image Signal Process. 141, 3 (1994) 143-148.

81. Lepsoy S., Attractor Image Compression: Fast Algorithms and Comparisons to Related Techniques, PhD Thesis, The Norwegian Institute of Technology, Trondheim, Norway, June 1993.

82. Leps0y S., 0ien G. E., Fast attractor image encoding by adaptive codebook clustering, in: Fractal Image Compression Theory and Application, Y. Fisher (ed.), Springer-Verlag, New York, 1994.

83. Lin H., Venetsanopoulos, A.N., Fractal-based image coding by nonlinear contractive functions, in: Proceedings of the 17th Biennial Symposium on Communications, Kingston, Ontario, pp. 295-298, May-June 1994.

84. Linde Y., Buzo A., Gray R. M. An algorithm for vector quantizer design. IEEE Transactions on Communications, 28:84-95, 1980.

85. Lu N. Fractal Imaging, San Diego: Academinc Press, 1997.

86. Mandelbrot B.B., The Fractal Geometry of Nature. New York: W. H. Freeman and Company, 1982.

87. Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. Symposium on Computational Geometry 2004: 253-262.

88. Mico M. L., Oncina J., Vidal E. A new version of the nearest-neighbour approxi-maning and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recognition Letters, 15(1):9-17, 1994.

89. Monro D.M., Dudbridge F., Fractal approximation of image blocks, in: Proceedings of ICASSP-1992 IEEE International Conference on Acoustics, Speech and Signal Processing,Vol. 3, pp. 485-488, 1992.

90. Motwani R., Naor A., Panigrahy R., lower bounds on Locality Sensitive Hashing. Proceedings of the Symposium on Foundations of Computer Science, 2005.

91. Nolan J.P. An introduction to stable distributions. http://academic2.american.edu/~jpnolan/stable/chap 1 .pdf.

92. Novak M., Attractor coding of images, Licentiate Dissertation, Dept. of Electrical Engineering, Linkoping University, May 1993.

93. Omohundro S. Five balltree construction algorithms. Technical report, International Computer Science Institute, 1989.

94. Saupe D., Hamzaoui R., Hartenstein H., Fractal image compression An introductory overview, in: Fractal Models for Image Synthesis, Compression, and Analysis, ACM-SIGGRAPH'96 Course Notes, 66 p.

95. Sarnoff Corporation, JND: A human vision system model for objective picture quality measurements, Sarnoff Technical Report from www.jndmetrix.com, (2001).

96. Saupe D., Lean domain pools for fractal image compression, in: Proceedings from IS&T/SPIE 1996 Symposium on Electronic Imaging: Science & Technology Still Image Compression II, Vol. 2669, to appear Jan. 1996.

97. Saupe D., Hartenstein H., Lossless acceleration of fractal image compression by fast convolution, in: Proc. ICIP-96 IEEE International Conference on Image Processing, Lausanne, Sept. 1996.

98. Saupe D., Accelerating fractal image compression by multi-dimensional nearest neighbor search, in: Proceedings DCC'95 Data Compression Conference, J. A. Storer and M. Cohn (eds.), IEEE Сотр. Soc. Press, March 1995.

99. Saupe D., Breaking the time complexity of fractal image compression, Technical Report 53, Institut fur Informatik, Universitat Freiburg, 1994.

100. Saupe D., From classification to multi-dimensional keys, in: Fractal Image Compression Theory and Application, Y. Fisher (ed.), Springer-Verlag, New York, 1994.

101. Saupe D., Fractal Image compression via nearest neighbour search, in: Conf. Proc. NATO ASI Fractal Image Encoding and Analysis, Trondheim, July 1995, Y. Fisher (ed.), to appear in Springer-Verlag, New York, 1995.

102. Saupe D., Hamzaoui R., A guided tour of the fractal image compression literature, in: New Directions for Fractal Modelling in Computer Graphics, J. Hart (ed.), ACM SIGGRAPH'94 Cource Notes 13, 1994.

103. Shasha D., Wang T.-L. New techniques for best-match retrieval. ACM Trans. Inf.Syst., 8(2): 140-158, 1990.

104. Uhlmann J. K., Satisfying general proximity/similarity queries with metric trees. Inform. Proc. Letters, 40:175-179, 1991.

105. Vidal E. An algorithm for finding nearest neighbours in (approximately) constant average time. Pattern Recognition Letters, 4:145-157, 1986.

106. Wall L., Kinser W., A fractal block coding technique employing frequency sensitive competitive learning, in: Proc. Of IEEE Communications, Computers and Power, pp. 320-329, 1993.

107. Wohlberg В., Jager G, A Review of the Fractal Image Coding Literature, IEEE Trans. On Image Processing, Vol. 8, No.12, pp. 1716-1729, 1999.

108. Zolotarev V.M. One-Dimensional Stable Distributions. Vol. 65 of Translations of Mathematical Monographs, American Mathematical Society, 1986.

109. Винокуров С.В. Особенности фрактального сжатия изображений. II Автоматизация и современные технологии №12, М.: Машиностроение, 2005, с. 2732.

110. Винокуров С.В. Методы повышения временной эффективности алгоритмов фрактального сжатия изображений. II Материалы конференции «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики», сборник Информатика, МГАПИ, 2005, с. 53-59.

111. Винокуров С.В. Подход к фрактальному сжатию изображений с использованием пространственно-чувствительного хеширования II Методы автоматизации управления: Сборник научных трудов МАДИ ГТУ, 2006, с. 14-19.

112. Винокуров С.В. Построение пространственно-чувствительных хеш-функций, адаптированных к задаче фрактального сжатия изображений // Методы автоматизации управления: Сборник научных трудов МАДИ ГТУ, 2006, с. 19-25.

113. Винокуров С.В. Эффективный алгоритм фрактального сжатия изображений с использованием пространственно-чувствительного хеширования // Открытое образование, 4(57)'2006, с. 62-70.

114. Винокуров С.В., Ульянов М.В. Комплексный критерий качества алгоритмов сжатия и восстановления растровых изображений на основе нормированных оценок II Вестник МГУПИ Серия: Технические и естественные науки 7, 2006, С. 43-52.