Разработка и исследование алгоритмов сжатия бинарных изображений в мультисервисных сетях связи

• Автор: Гузеев, Алексей Валерьевич
• Шифр специальности: 05.12.13
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 177 с. : ил.

Содержание
Введение
Актуальность темы
Цели и задачи исследования
Объект исследования и предмет исследования
Методологическая и теоретическая основа исследования
Информационная база исследования
Научная новизна исследования
Практическая значимость работы
Использование результатов работы
Апробация результатов исследования
Основные положения, выносимые на защиту
Объем работы
Глава 1: Классификация современных алгоритмов сжатия и стандарты кодирования в мулътисервисных сетях
1.1 Постановка задачи
1.2 Анализ стандартов сжатия информации в мулътисервисных сетях связи
1.2.1 Основные методы повышения эффективности передачи информации МСС
1.2.2 Акселерация трафика данных (решения JUNIPER Networks)
1.3 Сжатие изображений и виды избыточности, свойственные изображениям
1.3.1 Понятие класса изображения
1.3.2 Понятие избыточности данных
1.3.3 Кодовая избыточность
1.3.4 Межэлементная избыточность
1.3.5 Психовизуальная избыточность
1.3.6 Понятие документальной информации
1.3.7 Понятие глубины цветопередачи изображения
1.3.8 Понятия алгоритма сжатия и формата файла изображения
1.4 Анализ основных алгоритмов эффективного кодирования
1.4.1 Классический алгоритм Хаффмана
1.4.2 Факсимильное сжатие
1.4.3 Кодирование длин серий
1.4.4 Словарное кодирование (LZW)
1.4.5 Арифметическое кодирование
1.4.6 Фрактальное кодирование
1.4.7 Вейвлет кодирование
1.5 Анализ стандартов кодирования изображений
1.5.1 Анализ технологии JPEG
1.5.2 JBIG: стандарт для сжатия двухградационных изображений
1.6 Классификация алгоритмов сжатия
1.7 Выводы
Глава 2: Разработка алгоритмов сжатия и внесения потерь для двухградационных изображений
2.1 Постановка задачи
2.2 Алгоритм предобработки
2.2.1 Внесение потерь на базе блочного представления изображений
2.2.2 Разрешающая способность человеческого глаза
2.2.3 Разработка алгоритма внесения потерь
2.2.4 Метрики ошибок
2.3 Алгоритмы сжатия бинарных изображений

2.3.1 Модифицированный алгоритм Хаффмана
2.3.2 Алгоритм префиксного блочного кодирования
2.3.3 Процедура выделения областей интереса
2.4 Алгоритм формирования распределения вероятностей появления блоков в
изображении
2.5 Форматы файлов
2.6 Выводы
Глава 3: Выбор оптимальных параметров разработанных алгоритмов сжатия
3.1 Постановка задачи
3.2 Математическая модель двухградационного изображения
3.3 Вычисление вероятности появления блока на основе цепи Маркова
3.4 Проверка адекватности математической модели
3.5 Определение оптимальных размеров блока алгоритма ПБК
3.5.1 Преобразование битового потока
3.5.2 Вычисление коэффициента сжатия
3.6 Доказательство оптимальности алгоритма построения шаблона замены
3.7 Выводы
Глава 4: Анализ степени сжатия разработанных алгоритмов на основе компьютерного моделирования
4.1 Постановка задачи
4.2 Подготовка компьютерного моделирования
4.3 Компьютерное моделирование разработанных алгоритмов
4.3.1 Результаты моделирования для варианта
4.3.2 Результаты моделирования для варианта
4.3.3 Результаты моделирования для варианта
4.3.4 Результаты моделирования для варианта
4.3.5 Результаты моделирования для варианта
4.4 Сравнительный анализ предложенных вариантов
4.5 Анализ влияния потерь на степень сжатия алгоритмов, использующих
формирование распределения вероятностей появления блоков в изображении
4.6 Разработка рекомендаций по использованию предложенных алгоритмов
4.7 Выводы
Заключение
Список литературы
Приложение 1: Набор тестовых изображений
Приложение 2: Таблицы расчета критерия Фишера для тестовых изображений
Прилоэ/сение
Приложение 4: Форматы файлов разработанных алгоритмов
Приложение 5: Метрики ошибок для тестового набора изображений
Приложение 6: Пример построения списка длин кодов и списка счетчиков длин
Прилоэ/сение 7: Классический алгоритм Хаффмана
Пршюжение 8: Пример работы алгоритмов LZ77 и LZ
Пршожение 9: Технология JPEG
Приложение 10: Основные особенности стандарта JBIG

Введение
Актуальность темы
Компактное представление информации в целом и компактное представление изображений в частности является неотъемлемой частью любой современной сети связи. Эффективное кодирование применяется для решения задач двух типов: для сокращения объема занимаемого данными при хранении информации и для уменьшения времени передачи информации. Однако, подход к проблеме, когда рассматривается только одна из указанных задач, достаточно узок. Например, возможна ситуация, когда за счет сокращения объема передаваемой информации уменьшается не только время передачи, но и ее стоимость. С другой стороны, если некоторая информация была передана в сжатом виде и не утратила свою ценность после передачи, то целесообразно в такой форме и осуществлять ее последующее хранение.
Современные алгоритмы и стандарты сжатия, созданные для цветных или полутоновых изображений либо не учитывают специфику, либо вовсе не предназначены для двухградационных изображений. А алгоритмы, предназначенные для сжатия бинарных изображений, не дают необходимой степени сжатия, либо просто не используются т.к. содержат алгоритмы не совместимые с другими этапами обработки и хранения изображений. Характерным примером является использование в стандарте DICOM метода сжатия JPEG по умолчанию, в то время как использование эффективного кодирования предназначенного для бинарных изображений дает не только большее сжатие самих бинарных изображений, но и открывает новые подходы к сжатию полутоновых и цветных изображений. В очень многих случаях роль черно-белых изображений преуменьшается, а иногда их вообще путают с полутоновыми, хотя обработка и хранение именно бинарных изображений широко используется в таких областях, как телемедицина, картография, системы видеонаблюдения и системы документооборота.
Существует две основные проблемы, связанные с компактным представлением изображений.
Во-первых, последовательное применение алгоритмов сжатия, работающих по схожим физическим принципам, дает меньшую эффективность работы второго алгоритма, чем его отдельное применение.
Второй проблемой является отсутствие связи между характером внесения потерь в кодируемое изображение и особенностями восприятия результата этой операции человеком (в том случае, если изображение предназначено для человека, а не для некоторой автоматизированной системы). Природа восприятия человеком окружающего
неподвижному изображению (близкому к исходному). Обычно для этого достаточно 16 итераций.
Фрактальное кодирование предназначено для сжатия полутоновых и цветных изображений, несложно в реализации, но требует больших вычислительных затрат. Удаляет межэлементную избыточность, но эта избыточность возникает не за счет высокой корреляции близких областей, а за счет корреляции каких угодно областей с любой ориентацией в пространстве.
1.4.7 Вейвлет кодирование
Рекурсивный (волновой) алгоритм происходит от английского названия рекурсивного сжатия - wavelet. На русский язык оно переводится как волновое сжатие, и как сжатие с использованием всплесков. Этот вид архивации известен довольно давно и напрямую исходит из идеи использования когерентности областей. Ориентирован алгоритм на цветные и полутоновые изображения с плавными переходами. Идеален для картинок типа рентгеновских снимков. Коэффициент сжатия задастся и варьируется в пределах 5-100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется лестничный эффект - ступеньки разной яркости размером в несколько пикселей.
Идея алгоритма заключается в том[26], что в файл сохраняется разница - число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.
Например, для изображения 512x512 пикселей после первого wavelet-преобразования получается 4 матрицы размером 256x256 элементов:
В первой хранится уменьшенная копия изображения, во второй - усредненные разности пар значений пикселей по горизонтали, в третьей - усредненные разности пар значений пикселей по вертикали, в четвертой - усредненные разности значений пикселей по диагонали.
К достоинствам этого алгоритма можно отнести то, что он очень легко позволяет реализовать возможность постепенного проявления изображения при передаче изображения по сети. Кроме того, поскольку в начале изображения фактически хранится его уменьшенная копия, упрощается показ огрубленного изображения по заголовку.
Как и большинство других алгоритмов сжатия, основанных на математических преобразованиях, вейвлет кодирование усредняет значения по некоторой области изображения, следовательно, не предназначено для сжатия черно-белых изображений. Устраняет межэлементную избыточность.