WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

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

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

МЕТОДЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

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

Специальность 05.13.01 — Системный анализ, управление

и обработка информации (в технических системах)

АВТОРЕФЕРАТ

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

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

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

Научный доктор технических наук руководитель: Потапов Алексей Сергеевич Официальные доктор технических наук, профессор оппоненты: Тропченко Александр Ювенальевич (СПбГУ ИТМО) кандидат технических наук Федоренко Сергей Игоревич (ООО «Рекогнишн Фокус») Ведущая Санкт-Петербургский институт организация: информатики и автоматизации РАН

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

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

Автореферат размещён на сайте www.ifmo.ru Автореферат разослан «_» 2010 г.

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

диссертационного совета Коняхин Д 212.227.03 Игорь Алексеевич

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

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




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

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

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

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

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

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





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

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

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

исследования:

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

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

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

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

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

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

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

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

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

Практическая значимость исследования:

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались на следующих научных форумах: XXXVIII международная научная конференция аспирантов и студентов «Процессы управления и устойчивость»

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

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

Список опубликованных работ приведён в конце автореферата.

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

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

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

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

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

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

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

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

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

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

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

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

Если общее число доменных блоков для выбранного варианта разбиения равно nd, то для кодирования номера одного доменного блока потребуется log2nd бит. Пусть число коэффициентов преобразования равно np, при этом на каждый из них нужно выделить Bn p бит. Таким образом, размер сжатого изображения оценён как Оценка Lloss произведена следующим образом. Рассмотрена разность исходного и восстановленного изображений. Поскольку все закономерности данных должны быть вынесены в модель, полагается, что значения разности в каждом пикселе являются независимыми отсчётами некоторой случайной величины. Таким образом, количество информационных потерь в результате сжатия выражается через энтропию разностей:

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

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

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

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

Вначале рассмотрен классический алгоритм фрактального сжатия. При условии задания числа ранговых блоков nr и числа доменов nd получена оценка для суммарного количества операций Nop, требуемых для компрессии изображения: Nop=NR nr nd Nrd, где NR — число возможных разбиений, а Nrd — количество операций, необходимых для сравнения одного рангового и одного доменного блока. Применение распространённого упрощения, а именно, разбиения изображения на ранговые блоки одинаковых размеров, а также покрытия изображения доменами, размер которых пропорционален размеру ранговых блоков, позволяет добиться полиномиального роста количества блоков с ростом размера изображения в отличие от присущего классическому алгоритму экспоненциального роста (когда на форму и размер блоков не накладывается ограничений), но при этом скорость роста остаётся достаточно большой даже при рассмотрении одного разбиения, а именно — O(N4), поскольку скорость роста как nr, так и nd, пропорциональна N2 (здесь и далее N — среднее геометрическое линейных размеров изображения).

Далее оценено влияние параметров NR и Nrd. Сперва рассмотрен компонент Nrd, ответственный за сравнение одного рангового блока с одним доменом.

В традиционном варианте это сравнение осуществляется «попиксельно», т. е.

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

Далее рассмотрен компонент N R, отвечающий за количество возможных разбиений изображения на ранговые блоки. В качестве первого шага выбора оптимального способа разбиения изображения предложен «беспереборный»

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

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

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

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

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

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

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

1. Рассматривается «верхний левый угол» матрицы B, соответствующей текущему блоку b (подматрица B = {Bij }i, j =1,3 ).

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

Рис. 1. Порядок выбора элементов для вычисления индекса При применении к блоку b поворотов или отражения правила изменения ДКП-матрицы B задаются следующими равенствами:

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

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

1. Вычисляется коэффициент e1 = 2 bij.

2. Блок разделяется на четыре равных подблока b2, b3, b4 и b5.

ветствующие подблокам b2, b3, b4 и b5.

4. Формируется вектор e = [ e2 e3 e4 e5 ], который и будет являться искомым дескриптором.

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

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

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

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

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

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

5. Среди найденных «вторичных» доменов ищется домен d1, а также соответствующие паре r1 — d1 коэффициенты яркости и контрастности s1 и o1, исходя из условия минимизации СКО: d1 = arg min RMSE(r1, d1 ), где d1 = sd1 + oE, d1 — сжатый до размера блока r1 блок d1, а E — единичная матрица размера блока r1. Доменный блок, для которого будет выполняться приведённое условие минимизации СКО, назван оптимальным, или лучшим доменом.

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

7. Рассматривается второй ранговый блок r2, для которого повторяются шаги 2–6, затем третий ранговый блок r3, и так далее, пока не будет найден оптимальный домен d N r для последнего рангового блока rN r, где N r — количество ранговых блоков.

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

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

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

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

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

Здесь u и v — частоты, а соответствующие им периоды равны M u и N v. Тогда величину некоторого характерного периода гармоник изображения можно оценить как Величина Tavg названа средним пространственным периодом (СПП) изображения. Значение СПП используется в качестве априорной оценки влияния размера рангового блока на качество восстанавливаемого изображения.

Детально способ применения СПП будет описан ниже — при изложении результатов экспериментальной проверки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• найти установочные параметры, при которых достигается минимальное значение выражения Limg+Lloss;

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сер. 10. — 2010. — Вып. 2. — С. 114–121.

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

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

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

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

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

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

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

Н. В. Смирнова, Г. Ш. Тамасяна. — СПб.: Издательский Дом СанктПетербургского университета, 2010. — С. 466–471.



 
Похожие работы:

«САЛИХОВА ТАТЬЯНА ЮРЬЕВНА РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЗАЦИИ ЭСКИЗНОГО ПРОЕКТИРОВАНИЯ ИЗДЕЛИЙ ИЗ ПУШНО-МЕХОВЫХ И МЕХОВЫХ ПОЛУФАБРИКАТОВ 05.13.12 — Системы автоматизации проектирования (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Омск 2012 Работа выполнена на кафедре Конструирование швейных изделий Федерального государственного бюджетного образовательного учреждения высшего профессионального образования Омский государственный...»

«Лаздин Артур Вячеславович МЕТОДЫ ПОСТРОЕНИЯ ГРАФО-АНАЛИТИЧЕСКИХ МОДЕЛЕЙ ФУНКЦИОНАЛЬНЫХ ПРОГРАММ Специальность – 05.13.12 “Системы автоматизации проектирования” (приборостроение) АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Санкт-Петербург 2009 2 Работа выполнена в Санкт-Петербургском Государственном университете информационных технологий, механики и оптики. Научный руководитель доктор технических наук, профессор Немолочнов Олег Фомич...»

«ЧИКИН АЛЕКСЕЙ ЛЬВОВИЧ РАЗРАБОТКА И РЕАЛИЗАЦИЯ ДВУХСЛОЙНОЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ГИДРОФИЗИЧЕСКИХ ПРОЦЕССОВ В ВОДОЕМАХ С ОБШИРНЫМИ РАЙОНАМИ МЕЛКОВОДЬЯ НА ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ Специальность 05.13.18 –математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени доктора физико-математических наук Москва 2009 год Работа выполнена в Южно-Российском региональном центре информатизации ЮФУ и Южном...»

«ЧУКОВ ГЕОРГИЙ ВИКТОРОВИЧ НАУЧНО-МЕТОДИЧЕСКИЕ И АППАРАТНО-ПРОГРАММНЫЕ СРЕДСТВА КОНТРОЛЯ РАБОТОСПОСОБНОСТИ СОВРЕМЕННЫХ ИЗДЕЛИЙ ТВЕРДОТЕЛЬНОЙ СВЧ ЭЛЕКТРОНИКИ ПРИ ВОЗДЕЙСТВИИ ИОНИЗИРУЮЩИХ ИЗЛУЧЕНИЙ 05.13.05 – Элементы и устройства вычислительной техники и систем управления Автореферат диссертации на соискание ученой степени кандидата технических наук Автор: Москва – 2013 г. Работа выполнена в Национальном исследовательском ядерном университете МИФИ. Научный руководитель :...»

«Ключников Андрей Михайлович РАЗРАБОТКА МЕТОДОВ АНАЛИЗА ОСНОВНЫХ ПАРАМЕТРОВ ФУНКЦИОНАЛЬНЫХ УСТРОЙСТВ МИКРОПРОЦЕССОРОВ НА НАЧАЛЬНОЙ СТАДИИ ПРОЕКТИРОВАНИЯ Специальность 05.13.05 – Элементы и устройства вычислительной техники и систем управления АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2013 2 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Национальный...»

«Парамонов Илья Вячеславович МОДЕЛИРОВАНИЕ НЕЙРОННЫХ АССОЦИАЦИЙ. ОЦЕНКА ПАРАМЕТРОВ И ЯВЛЕНИЕ СИНХРОНИЗАЦИИ Специальность 05.13.18 — математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Ярославль – 2011 Работа выполнена на кафедре компьютерных сетей Ярославского государственного университета им. П. Г. Демидова доктор физико-математических наук, Научный профессор Глызин Сергей...»

«Кудрявцев Юрий Александрович Алгоритмы эффективной обработки MOLAP-кубов 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание учной степени е кандидата физико-математических наук Москва 2009 Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного...»

«АБРАМОВ Сергей Александрович ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ УПРАВЛЕНИЯ ВОДНЫМИ РЕСУРСАМИ НА ОСНОВЕ ТОПОЛОГИИ ПРОСТРАНСТВЕННЫХ ДАННЫХ Специальность 05.13.01 – Системный анализ, управление и обработка информации (в промышленности) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Уфа2009 Работа выполнена на кафедре геоинформационных систем Государственного образовательного учреждения высшего профессионального образования Уфимский государственный...»

«Лужков Юрий Валерьевич РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ СЖАТИЯ ИЗОБРАЖЕНИЙ С ПОТЕРЯМИ НА ОСНОВЕ АДАПТИВНОЙ СЕГМЕНТАЦИИ И КВАНТОВАНИЯ Специальность: 05.13.13 – Телекоммуникационные системы и компьютерные сети Автореферат диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2009 2 Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики. Научный руководитель : доктор технических наук,...»

«УДК 519.633 Расторгуев Иван Александрович Решение задач фильтрации устойчивыми явными методами 05.13.11- Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва - 2006 Работа выполнена в Российском научном центре Курчатовский институт доктор физико-математических наук, профессор Научный...»

«УДК 004.432.42 Идрисов Ренат Искандерович МЕЖПРОЦЕДУРНЫЙ АНАЛИЗ И РАСПАРАЛЛЕЛИВАНИЕ ПОТОКОВЫХ ПРОГРАММ НА БАЗЕ ГРАФА ИСПОЛНЕНИЙ ВЫЗОВОВ 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск 2010 Работа выполнена в Учреждении Российской...»

«КНЯЗЬКОВ Дмитрий Юрьевич МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ ПРОЦЕССА ФОРМИРОВАНИЯ ГОЛОГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЭФФЕКТИВНЫХ МЕТОДОВ РАСЧЕТА ЭЛЕКТРОМАГНИТНЫХ ПОЛЕЙ специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Москва — 2013 Работа выполнена в лаборатории механики управляемых систем Федерального государственного бюджетного учреждении науки...»

«КРАВЦОВА НАДЕЖДА АЛЕКСЕЕВНА АВТОМАТИЗАЦИЯ ПРОЦЕССОВ СБОРА И ХРАНЕНИЯ ДАННЫХ ПРИ ПРОВЕДЕНИИ АДМИНИСТРАТИВНОГО МОНИТОРИНГА Специальность 05.13.06 – Автоматизация и управление технологическими процессами и производствами (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Орел-2012 2 Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Государственный университет –...»

«БЕЛЫХ Александр Валерьевич ВИЗУАЛЬНЫЙ МЕТОД РАЗРАБОТКИ ОБЪЕКТНООРИЕНТИРОВАННЫХ БАЗ ДАННЫХ ДЛЯ СИСТЕМ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ Специальность 05.13.12 – Системы автоматизации проектирования (вычислительная техника и информатика) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Ростов-на-Дону 2010 Работа выполнена в государственном образовательном учреждении высшего профессионального образования Ростовский государственный университет путей...»

«Сатторов Фаррух Эътиборович МЕТОД И АЛГОРИТМЫ РАСПРЕДЕЛЕНИЯ ФУНКЦИОНАЛЬНЫХ ВОЗМОЖНОСТЕЙ ПОЛЬЗОВАТЕЛЕЙ В СИСТЕМАХ ОБРАБОТКИ ИНФОРМАЦИИ Специальность: 05.13.01 – Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург-2010 2 Работа выполнена в Санкт-Петербургском государственном электротехническом университете ЛЭТИ им. В.И. Ульянова (Ленина). Научный руководитель – доктор технических...»

«Мухин Сергей Иванович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ГЕМОДИНАМИКИ Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва - 2008 Диссертация выполнена на кафедре вычислительных методов Факультета ВМК МГУ имени М.В.Ломоносова Научный...»

«Симаков Сергей Сергеевич Численное моделирование сердечно-сосудистой и дыхательной систем организма человека с учетом их взаимодействия Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Москва — 2006 Работа выполнена на кафедре вычислительной математики Московского физикотехнического института (государственного университета). Научный руководитель...»

«АМАМРА РУШДИ АХМАД РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ТЕМАТИЧЕСКИ ОРИЕНТИРОВАННОГО РАСПРЕДЕЛЕННОГО ПОИСКА ИНФОРМАЦИИ В ГЛОБАЛЬНЫХ СЕТЯХ ТИПА ИНТЕРНЕТ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук САНКТ-ПЕТЕРБУРГ 2002 Работа выполнена в Санкт-Петербургском Государственном Техническом Университете. Научный руководитель : доктор...»

«Бодров Алексей Анатольевич ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ ССЫЛОЧНЫХ МАССИВОВ ДАННЫХ В ИНТЕГРИРОВАННЫХ СИСТЕМАХ ОБРАБОТКИ ИНФОРМАЦИИ Специальность: 05.13.01 – Системный анализ, управление и обработка информации (технические системы) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва 2009 Работа выполнена в Учреждении Российской академии наук Институте конструкторско-технологической информатики РАН (ИКТИ РАН). Научный руководитель : доктор...»

«УТКИН Павел Сергеевич ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ИНИЦИИРОВАНИЯ И РАСПРОСТРАНЕНИЯ ВОЛН ГАЗОВОЙ ДЕТОНАЦИИ В ПРОФИЛИРОВАННЫХ ТРУБАХ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук МОСКВА – 2010     Работа выполнена в отделе Вычислительных методов и турбулентности Учреждения Российской академии наук Институт автоматизации проектирования РАН Научный...»








 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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