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

• Горьков, Алексей Геннадьевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Горьков, Алексей Геннадьевич

ВВЕДЕНИЕ 5

ГЛАВА 1 ОБЗОР МЕТОДОВ СЖАТИЯ ИНФОРМАЦИИ 12

1.1 Методы сжатия информации без потерь 12

1.1.1 Поточные и словарные алгоритмы сжатия информации 13

1.1.2 Энтропийное кодирование 18

1.2 Сжатие изображений без потерь 22

1.2.1 Сжатие двоичных изображений 23

1.2.2 Сжатие монохромных изображений 26

1.3 Сжатие изображений с потерями 28

1.3.1 Критерии качества сжатого изображения 28

1.3.2 Сжатие посредством квантования и дискретизации 30

1.3.3 Кодирование с предсказанием и квантованием 32

1.3.4 Трансформационное кодирование 35

1.4 Выводы 41

ГЛАВА 2 МЕТОД ФРАГМЕНТАРНОГО СЖАТИЯ ВИДЕОПОТОКА 43

2.1 Основные понятия и определения 43

2.2 Основная идея метода фрагментарного сжатия видеопотока 45

2.3 Выбор способа получения коротких кодов 46

2.4 Схема передачи сжатого видеопотока 49

2.5 Алгоритм формированйя базы элементов 52

2.6 Оптимизация конфигурации окна сканирования 58

2.7 Кодирование цветных видеопотоков 63

2.8 Сравнение эффективности метода фрагментарного сжатия видеопотока с используемыми кодекам 68

2.9 Выводы 72

ГЛАВА 3 СПОСОБЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ СЖАТИЯ ФРАГМЕНТАРНОГО МЕТОДА 74

3.1 Повышение эффективности сжатия с сохранением качества исходного видеопотока 74

3.1.1 Метод фрагментарного сжатия битовых плоскостей видеопотока 74

3.1.2 Предварительное преобразование видеопотока в коды Грея 79

3.1.3 Перестройка кодового дерева для более эффективной передачи базы элементов 83

3.2 Повышение эффективности сжатия за счёт потерь 84

3.2.1 Удаление младших битовых плоскостей 84

3.2.2 Предварительная фильтрация исходного видеопотока 87

3.3 Выводы 91

ГЛАВА 4 АППАРАТНАЯ РЕАЛИЗАЦИЯ ДЕРЕВА СЕКУЩИХ ФУНКЦИЙ НА ЭЛЕМЕНТАХ

АССОЦИАТИВНОЙ ОСЦИЛЛЯТОРНОЙ СРЕДЫ 93

4.1 Выбор типа среды для реализации дерева секущих функций 93

4.2 Выбор типа ПЛИС для реализации базовых клеточных ансамблей ассоциативной осцилляторной среды 97

4.2.1 Функциональная ориентация 99

4.3 Базовые клеточные ансамбли и осцилляторы в ассоциативной осцилляторной среде 101

4.3.1 Проводник 102

4.3.2 Узел 102

4.3.3 Сумматор 103

4.3.4 Умножитель 104

4.3.5 Инвертор 105

4.3.6 Блок 105

4.3.7 Дифференциальный блок 106

4.3.8 Накапливающий осциллятор 107

4.3.9 Вычитающий осциллятор 108

4.3.10 Дифференциальный осциллятор 109

4.3.11 Дифференциал 110

4.4 Аппаратная реализация дерева секущих 111

4.4.1 Базовый клеточный ансамбль секущая 111

4.4.2 Реализация узла дерева секущих на элементах ассоциативной осцилляторной среды 113

4.4.3 Реализация дерева секущих функций 117

4.5 Выводы 122

ЗАКЛЮЧЕНИЕ

123

ЛИТЕРАТУРА 125

ПРИЛОЖЕНИЕ 131

Формирование базы элементов 131

Основные константы и определения (UGlobal) 131

Элементы и процедуры над ними (UElem) 132

Формирование баз (UProcess) 134

Вычисление характеристик базы (UStatList) 137

Введение диссертации (часть автореферата) на тему «Метод, алгоритмы и устройства фрагментарного сжатия видеопотока»

Введение

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

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

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

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

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

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

• CorePNG использует алгоритм deflate [1] для независимого сжатия каждого кадра. Теоретически кодек поддерживает дельта-кадры, но на практике эта возможность практически не используется;

• FFV1 использует метод кодирования с предсказанием и дальнейшим энтропийным кодированием ошибки предсказания;

• Huffyuv, как и алгоритм FFV1, использует кодирование с предсказанием, а ошибку предсказания эффективно кодирует с использованием алгоритма Хаффмана;

• MSU Lossless Video Codec много лет разрабатывается в лаборатории при МГУ им. Ломоносова.

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

Не менее важной проблемой является обеспечение высокого быстродействия методов сжатия. Закон Мура, предсказывающий удвоение производительности процессоров каждые 18 месяцев, базируется на идее о постоянном совершенствовании полупроводниковых технологий. Однако уже сейчас возможности по улучшению полупроводниковых технологий почти исчерпаны. Кроме того, доминирующая архитектура фон Неймана также ограничивает рост производительности современных компьютеров. В классической фон Неймановской архитектуре предполагается разделение устройств хранения и обработки информации. В соответствии с упомянутым законом Мура производительность процессора удваивается каждые 18 месяцев, но время доступа к памяти за этот же период сокращается менее чем на 10%. В итоге процессор (устройство обработки) вынужден ожидать поступления данных из памяти (устройства хранения), что крайне негативно сказывается на общей производительности системы [2-6].

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

совмещающие функции обработки и хранения информации. Современные разработчики сфокусированы на исследованиях клеточных автоматов [7] и однородных вычислительных сред. Одним из наиболее перспективных вариантов реализации архитектуры на основе клеточных автоматов является разработанная на кафедре ВТ под руководством д.т.н. проф. Огнева И.В. ассоциативная осцилляторная среда (АОС) [8-13].

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

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

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

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

• Разработка метода фрагментарного сжатия видеопотока;

• Разработка алгоритма формирования базы элементов для фрагментарного метода сжатия видеопотока;

• Выбор оптимальной конфигурации окна сканирования;

• Разработка способов повышения эффективности метода фрагментарного сжатия посредством:

о Разложения видеопотока на битовые плоскости; о Предварительного преобразования яркости пикселов видеопотока в коды Грея;

о Предварительной фильтрации исходного видеопотока;

о Исключения младших битовых плоскостей.

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

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

• Реализация и моделирование базовых клеточных ансамблей ассоциативной осцилляторной среды на ПЛИС;

• Разработка нового базового клеточного ансамбля ассоциативной осцилляторной среды - «секущая»;

• Построение дерева секущих на базовых клеточных ансамблях ассоциативной осцилляторной среды.

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

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

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

Научная новизна работы заключается в следующем:

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

• Разработаны способы повышения эффективности метода фрагментарного сжатия посредством:

о Разложения видеопотока на битовые плоскости;

о Предварительного преобразования яркости пикселов видеопотока в коды Грея;

о Предварительной фильтрации исходного видеопотока;

о Исключения младших битовых плоскостей.

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

• Реализованы базовые клеточные ансамбли ассоциативной осцилляторной среды на современных ПЛИС.

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

Практическая ценность полученных в диссертации результатов

заключается в следующем:

• Предложенный метод фрагментарного сжатия аппаратно реализован на основе базовых клеточных ансамблей ассоциативной осцилляторной среды;

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

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

о Формирование базы элементов;

о Построение дерева секущих функций для сформированной базы элементов;

о Автоматическое построение УНБЬ-описания дерева секущих на основе его программного описания;

о Кодирование видеопотока.

Достоверность положений, выводов и практических рекомендаций,

сформулированных в диссертации, подтверждена серией экспериментов,

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

Научные и практические результаты работы включены в курс лекций «Организация ЭВМ и систем» на кафедре вычислительной техники НИУ «МЭИ» и используются в дипломном проектировании студентов.

Апробация работы. Основные результаты докладывались на международных научно-технических конференциях «Информационные средства и технологии» в 2010, 2012, 2013 годах.

Публикации. Основные результаты диссертации опубликованы в семи печатных работах, в том числе в трёх изданиях, рекомендованных ВАК.

Структура и объём диссертационной работы. Диссертационная работа изложена на 139 страницах, из них 124 страницы основного текста, 56 рисунков, 38 таблиц. Состоит из введения, четырёх глав, заключения, списка литературы из 59 наименований и приложения на девяти страницах.

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

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

• Способы повышения эффективности метода фрагментарного сжатия посредством:

о Разложения видеопотока на битовые плоскости; о Предварительного преобразования яркости пикселов видеопотока в коды Грея;

о Предварительной фильтрации исходного видеопотока; о Исключения младших битовых плоскостей.

• Новый базовый клеточный ансамбль ассоциативной осцилляторной среды - «секущая», позволяющий с малыми аппаратными затратами строить многоуровневые деревья секущих.

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

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

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

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

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

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

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

1.1 Методы сжатия информации без потерь

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

1. Поточные и словарные алгоритмы. К этой группе относятся алгоритмы семейств RLE (поточные алгоритмы), LZ* [14,15] (словарные алгоритмы) и др. Особенностью всех алгоритмов этой группы является то, что при кодировании используется не информация о частотах символов в исходном сообщении, а информация о символах и последовательностях, встречавшихся ранее.

2. Алгоритмы статистического (энтропийного) сжатия. Эта группа алгоритмов сжимает информацию, используя неравномерность частот, с которыми различные символы встречаются в исходном сообщении. К алгоритмам этой группы относятся различные алгоритмы префиксного (с использованием деревьев Шеннона-Фанно, Хаффмана и д.р. [16]) и арифметического кодирования.

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

1.1.1 Поточные и словарные алгоритмы сжатия информации

Кодирование длин серий или RLE (от англ. Run-Length Encoding) -это один из самых простых и распространённых алгоритмов сжатия данных. В этом алгоритме последовательность повторяющихся символов заменяется кодом символа и количеством его повторов.

Например, строка «ААААА», требующая для хранения 5 байт (при условии, что на хранение одного символа отводится байт), может быть заменена строкой «5А», требующей для хранения двух байт. Эффективность этого алгоритма тем выше, чем длиннее серия повторов.

Основным недостатком этого алгоритма является его крайне низкая эффективность на последовательностях неповторяющихся символов. Например, последовательность «АБАБАБ» (6 байт) после непосредственного применения алгоритма RLE будет преобразована в «1А1Б1А1Б1А1Б» (12 байт). Для более эффективного кодирования последовательностей неповторяющихся символов существуют различные методы.

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

1, то следующие 7 бит указывают количество повторов соответствующего символа, а если первый бит равен 0, то следующие 7 бит показывают количество символов, которые надо взять без повтора. Если закодировать «АБАБАБ» с использованием данной модификации, то получим «-6АБАБАБ» (7 байт). Очевидно, что предложенная методика позволяет значительно повысить эффективность RLE алгоритма на неповторяющихся последовательностях символов.

Вторым способом повышения эффективности алгоритма RLE является использование алгоритмов преобразования информации, которые непосредственно не сжимают данные, но приводят их к более удобному для сжатия виду. В качестве примера такого алгоритма можно привести BWT-перестановку, названную по фамилиям создателей Burrows-Wheeler transform [17]. Эта перестановка не изменяет ни сами символы, ни их количество, а изменяет только их порядок в кодируемой строке. При этом повторяющиеся подстроки после применения перестановки собираются в плотные группы, которые гораздо лучше сжимаются с помощью алгоритма RLE.

Прямое BWT преобразование сводится к следующей последовательности шагов:

1. Добавление к исходной строке специального символа конца строки, который нигде более не встречается;

2. Получение всех циклических перестановок исходной строки;

3. Сортировка полученных строк в лексикографическом порядке;

4. Возвращение последнего столбца полученной матрицы.

Проще всего пояснить это преобразование на конкретном примере. Возьмём строку «АНАНАС» и договоримся, что символом конца строки будет символ «|». После выполнения всех циклических перестановок и их лексикографической сортировки в последнем столбце матрицы будет получена строка «|ННАААС». Очевидно, что полученная в результате преобразования строка гораздо лучше, чем исходная, сжимается алгоритмом

14

RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв.

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

1. Создать пустую матрицу размером п * п, где п — количество символов в закодированном сообщении;

2. Заполнить самый правый пустой столбец закодированным сообщением;

3. Отсортировать строки таблицы в лексикографическом порядке;

4. Повторять шаги 2-3, пока есть пустые столбцы;

5. Вернуть ту строку, которая заканчивается символом конца строки.

Реализация обратного преобразования на первый взгляд не представляет сложности, но на практике его эффективность зависит от выбранного алгоритма сортировки. Тривиальные алгоритмы с квадратичной сложностью, очевидно, крайне негативно скажутся на быстродействии, поэтому рекомендуется использовать эффективные алгоритмы сортировки строк [18-20]. После сортировки таблицы, полученной на седьмом шаге, необходимо выбрать из таблицы строку, заканчивающуюся символом «|». Легко показать, что это строка единственная.

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

Группа словарных алгоритмов [14,15], в отличие от алгоритмов группы поточных алгоритмов, кодирует не количество повторов символов, а

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

Ниже описан простейший вариант словарного алгоритма:

1. Инициализировать словарь всеми символами, встречающимися во входной строке;

2. Найти в словаре самую длинную последовательность (5), совпадающую с началом кодируемого сообщения;

3. Выдать код найденной последовательности и удалить её из начала кодируемого сообщения;

4. Если не достигнут конец сообщения, считать очередной символ (с) и добавить 5с в словарь, перейти к шагу 2. Иначе, выход.

Например, только что инициализированный словарь для фразы «КУКУШКАКУКУШОНКУКУПИЛАКАПЮШОН» приведён в Табл. 1-1:

Табл. 1-1. Начальное состояние словаря

Символ Код символа

К 00001

У 00010

Ш 00011

А 00100

О 00101

Н 00110

П 00111

И 01000

Л 01001

Ю 01010

В процессе сжатия словарь будет дополняться встречающимися в сообщении последовательностями. Процесс пополнения словаря приведён в Табл. 1-2.

Табл. 1-2. Процесс заполнения словаря

Кодируемая последовательность 5 Код 5 Последовательность, добавляемая в словарь 5с Код 5с

К 00001 КУ 01011

У 00010 УК 01100

КУ 01011 КУШ 01101

ш 00011 ШК 01110

к 00001 КА 01111

А 00100 АК 10000

КУ 01011 КУК 10001

КУШ 01101 КУШО 10010

О 00101 ОН 10011

н 00110 НК 10100

КУК 10001 КУКУ 10101

У 00010 УП 10110

п 00111 ПИ 10111

и 01000 ил 11000

л 01001 ЛА 11001

АК 10000 АКА 11010

А 00100 АП 11011

П 00111 ПЮ 11100

Ю 01010 ЮШ 11101

Ш 00011 ШО 11110

ОН 10011

При описании алгоритма намеренно было опущено описание ситуации,

когда словарь заполняется полностью. В зависимости от варианта словарного алгоритма возможно различное поведение:

• Полная или частичная очистка словаря;

• Прекращение заполнение словаря;

• Расширение словаря с соответствующим увеличением разрядности кода.

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

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

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

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

1.1.2 Энтропийное кодирование Алгоритм Шеннона-Фано [21] — один из первых разработанных алгоритмов сжатия. В основе алгоритма лежит идея представления более частых символов с помощью более коротких кодов. При этом коды, полученные с помощью алгоритма Шеннона-Фано, обладают свойством префиксности: т.е. ни один код не является началом никакого другого кода. Алгоритм построения кодов Шеннона-Фано представлен ниже:

1. Разбить алфавит на две части, суммарные частоты символов в которых максимально близки друг к другу.

2. В префиксный код первой части символов добавить 0, в префиксный код второй части символов добавить 1.

3. Для каждой части (в которой не менее двух символов) рекурсивно выполнить шаги 1-3.

Несмотря на сравнительную простоту, алгоритм Шеннона-Фано не лишён недостатков, самым существенным из которых является

неоптимальность кодирования. Хоть разбиение на каждом шаге и является оптимальным, алгоритм, как и значительная часть «жадных» алгоритмов, не гарантирует оптимального результата в целом. Рассмотрим, например, следующую строку: «ААААБВГДЕЖ». Соответствующее дерево Шеннона-Фано и коды, полученные на его основе, представлены на Рис. 1-1:

Рис. 1-1. Пример дерева Шеннона-Фано

Без использования кодирования сообщение будет занимать 40 бит (при условии, что каждый символ кодируется 4 битами), а с использованием алгоритма Шеннона-Фано 4*2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 бит. Объём сообщения уменьшился на 32.5%, но далее будет показано, что этот результат можно значительно улучшить, используя кодирование по методу Хаффмана.

Алгоритм кодирования Хаффмана [22], разработанный через несколько лет после алгоритма Шеннона-Фано, также обладает свойством префиксности, а, кроме того, доказанной минимальной избыточностью (для префиксного кодирования), именно этим обусловлено его крайне широкое распространение. Для получения кодов Хаффмана используют следующий алгоритм:

1. Все символы алфавита представляются в виде свободных узлов, при этом вес узла пропорционален частоте символа в сообщении;

2. Из множества свободных узлов выбираются два узла с минимальным весом и создаётся новый (родительский) узел с весом, равным сумме весов выбранных узлов;

3. Выбранные узлы удаляются из списка свободных, а созданный на их основе родительский узел добавляется в этот список;

4. Шаги 2-3 повторяются до тех пор, пока в списке свободных больше одного узла;

5. На основе построенного дерева каждому символу алфавита присваивается . префиксный код.

Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-

Фано. Дерево Хаффмана и коды полученные для сообщения

«ААААБВГДЕЖ», представлены на Рис. 1-2:

Рис. 1-2. Пример дерева Хаффмана

Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано.

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

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

Арифметическое кодирование [23] - один из наиболее эффективных способов сжатия информации. В отличие от алгоритма Хаффмана, арифметическое кодирование позволяет кодировать сообщения с энтропией меньше 1 бита на символ. Так как большинство алгоритмов арифметического кодирования защищены патентами, далее будут описаны только основные идеи.

Предположим, что в используемом алфавите N символов а1,...,аы с частотами р±, соответственно. Шаги алгоритма арифметического

кодирования выглядят следующим образом:

1. В качестве рабочего полуинтервала выбирается [0; 1);

2. Рабочий полуинтервал разбивается на N непересекающихся полуинтервалов. При этом длина 1-го полуинтервала пропорциональна р^

3. Если не достигнут конец сообщения, в качестве нового рабочего интервала выбирается ¿-й полуинтервал и переход к шагу 2. В противном случае, вернуть любое число из рабочего полуинтервала. Запись этого

числа в двоичном коде и будет представлять собой закодированное сообщение.

На Рис. 1-3 представлен процесс кодирования сообщения «АБААВ»

О_|о,6 ¡0,8_|1

А |б И

0 0,36

А 6 8

0,432

А 'о |в

0,36 0,4032

' А & а

0,36 0,35592

А с в

| ргсультат т/щромит

Рис. 1-3. Пример арифметического кодирования

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

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

1.2 Сжатие изображений без потерь

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

1.2.1 Сжатие двоичных изображений

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

Список литературы диссертационного исследования кандидат наук Горьков, Алексей Геннадьевич, 2014 год

Список литературы

1. Стандарт RFC 1951 - алгоритм DEFLATE

2. Ревизия первооснов - конец застоя? Черняк Л. Открытые системы. - 2003 г. №5. с. 39-41.

3. Пенроуз Р, Новый ум короля. О компьютерах, мышлении и законах физики.: Изд. 2-е, испр. - М.: Едиториал УРСС, 2005. - 400 с.

4. Рассел С., Норвиг П. Искусственный интеллект. Современный подход. -М.: Вильяме, 200. -1408 с.

5. Кохонен Т. Ассоциативная память: Пер. с англ. -М.: Мир, 1980. -240 с.

6. Борисов В.В., Полячков A.B. Модель многоуровневого сетевого контроллера на основе ассоциативной среды, сборник научных трудов №6 ВУ ВПВО ВС РФ. - Смоленск: Издательство ВУ ВПО ВС РФ, 2001. -с. 41-44.

7. Дж. Нейман. Теория самовоспроизводящихся автоматов: Пер. с англ. —М.: Мир, 1971 г. -384 с.

8. Огнев И.В., Борисов В.В., Ассоциативные среды. -М.: Радио и связь, 2000. -312 с.

9. Комаров А.Н. Исследование и разработка ассоциативных сред и методов обработки информации. Диссертация на соискание учёной степени кандидата технических наук. -М.: МЭИ(ТУ), 2002. - 194 с.

Ю.Подолин П.Б. Исследование ассоциативных осцилляторных сред на примере задачи распознавания образов. Магистерская диссертация. -М.: МЭИ(ТУ), 2005, 117 с.

П.Огнев И.В., Борисов В.В. Интеллектуальные системы ассоциативной памяти. -М.: Радио и связь. 1996. - 176 с.

12.Комаров А.Н., Огнев И.В., Подолин П.Б. Базовые клеточные ансамбли ассоциативных осцилляторных сред и возможности их расширения / Вычислительные системы и технологии обработки информации: межвузовский сборник научных трудов. - вып. 5(30). - Пенза: Информационно-издательский центр ПТУ, 2006. - 200 с.

125

13.Огнев И.В., По долин П.Б. Распознавание символов в ассоциативной осцилляторной среде. -М.: Известия высших учебных заведений Поволжского региона. Технические науки №6/27, 2006. - с. 55-67.

14.Ziv, J.; Lempel, А. (1978). "Compression of individual sequences via variablerate coding". IEEE Transactions on Information Theory 24 (5).

15.Welch, Terry (1984). "A Technique for High-Performance Data Compression". Computer 17 (6): 8-4.

16.A. M. Яглом, И. M. Яглом. Вероятность и информация. — М.: Наука, 1973.

17.Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation.

18.Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ, 3-е издание. — М.: «Вильяме», 2013. — 1328 с.

19.Дональд Кнут Искусство программирования, том 3. Сортировка и поиск. — 2-е изд. — М.: «Вильяме», 2007. — 824 с.

20.Алгоритмы и структуры данных. Новая версия для Оберона + CD. —М.: ДМК Пресс, 2010.

21.Shannon, С.Е. (July 1948). "A Mathematical Theory of Communication". Bell System Technical Journal 27: 379-423.

22.Huffman, D. (1952). "A Method for the Construction of Minimum-Redundancy Codes". Proceedings of the IRE 40 (9): 1098-1101.

23.Witten, Ian H.; Neal, Radford M.; Cleary, John G. (June 1987). "Arithmetic Coding for Data Compression" (PDF). Communications of the ACM 30 (6): 520-540.

24.Ватолин Д., Ратушняк А., Смирнов M., Юкин В. "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". -М.: Диалог-МИФИ, 2003, 384 с.

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

26.Зорин В. А. Математический анализ. — М.: Физматлит, 1984. — с. 544.

27.Афонский А. А., Дьяконов В. П. Цифровые анализаторы спектра, сигналов и логики / Под ред. проф. В. П. Дьяконова. — М.: COJIOH-Пресс, 2009. — с. 248.

28.Сергиенко А. Б. Цифровая обработка сигналов. — 2-е изд. — СПб.: Питер, 2006. —с. 751.

29.Чуи К. Введение в вэйвлеты. — М.: Мир, 2001. — 412 с.

30.Добеши И. Десять лекций по вейвлетам. — Ижевск: РХД, 2001. — 464 с.

31.Haar, Alfred (1910), "Zur Theorie der orthogonalen Funktionensysteme", Mathematische Annalen 69 (3): 331-371.

32.Д. Сэломон. Сжатие данных, изображений и звука. -М.: Техносфера, 2004. -с. 368.

33.Огнев И.В., Огнев А.И., Горьков А.Г. Алгоритм формирования базы данных для фрагментарного метода сжатия видеопотока без потерь / Труды XX международной научно-технической конференции «Информационные средства и технологии». - Том 1. - М: Издательский дом МЭИ, 2012. - с. 67-77.

34.Огнев И.В., Огнев А.И., Горьков А.Г. Оптимизация конфигурации окна сканирования в фрагментарном методе сжатия видеопотока без потерь / Труды XX международной научно-технической конференции «Информационные средства и технологии». - Том 1. — М: Издательский дом МЭИ, 2012. - с. 78-85.

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

«Информационные средства и технологии». - Том 1. - М: Издательский дом МЭИ, 2013.-с. 47-52.

Зб.Закревский Д.А. Логика распознавания. - Минск: Наука и техника, 1988. -119с.

37.Бруснецов Н.П., Владимирова Ю.С. Конструктивная компьютеризация силлогистики / математические методы распознавания образов // 13-я Всероссийская конференция: Сб. докл. -М.: МАКС Пресс, 2007, -10-13 с.

38.Неделько В.М. Об эффективности эмпирических функционалов качества решающей функции / Математические методы распознавания образов // 13-я Всероссийская конференция. Сб. докл. - М.: МАКС Пресс, 2007. -4749 с.

39.Огнев И.В., Огнев А. И., Горьков А. Г. Алгоритм фрагментарного сжатия цветового видеопотока. Информационные технологии в проектировании и производстве: Науч.-техн. журн./ ФГУП "ВИМИ", 2014. № 1 с. 62 - 68.

40.И. В. Огнев, А. И. Огнев, А. Г. Горьков. Метод фрагментарного сжатия битовых плоскостей, преобразованных в коды Грея / Известия высших учебных заведений. Поволжский регион. Технические науки. - 2013. - № 4 (28).-С. 76-87.

41.Огнев И.В., Огнев А.И., Горьков А.Г. Методы фрагментарного сжатия битовых плоскостей видеопотока. Вестник московского энергетического института (№2), - М: Издательский дом МЭИ, 2014 г.

42.И.В. Огнев, H.A. Сидорова Обработка изображений методами математической морфологии в ассоциативной осцилляторной среде / Известия высших учебных заведений. Поволжский регион. - 2007. - Вып. 4. - с. 87-97. - (Технические науки)

43.Огнев И.В., Сидорова H.A. Реализация древовидных структур в ассоциативной осцилляторной среде. Труды 8-ой международной научно-технической конференции «Информационные технологии и системы». Часть 1. -2008 г. - издательство Пензенского гос. Университета. С. 165171.

44.Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений: Учебное пособие для студентов вузов. — М.: высшая школа, 1983 г. -295 с.

45.Чжао Цзюньцай, Шарапов А.П. Исследование и разработка алгоритмов заполнения пустот для построения трехмерного изображения по сечениям. - Вычислительные сети: теория и практика №1. — 2007.

46.Robert Dueck. Digital Design with CPLD Applications and VHDL. Delmar Cengage Learning. 2007. 896 с.

47.Тарасов И.Е. Разработка цифровых устройств на основе ПЛИС XILINX с применением языка VHDL. - М.: Горячая линия - Телеком, 2005, -252 с.

48.Угрюмов Е.П., Грушвицкий Р.И.. Мурсаев А.Х. Проектирования систем на микросхемах с программируемой структурой. -2-е издание. СПб.: БХВ-Петербург, 2006. - 736 с.

49.Глушков В.М. Синтез цифровых автоматов. - М.: Физматгиз, 1962. -476 с.

50.Потёмкин И.С. Функциональные узлы цифровой автоматики. — М.: Энергоатомиздат, 1988. -320 с.

51.Белов A.B. Создаём устройства на микроконтроллерах. - СПб.: Наука и техника, 2007.-307 с.

52.Стешенко В.Б. ПЛИС фирмы Altera: проектирование устройств обработки сигналов. - М.: ДОДЭКА ,2000. -128 с.

53.Бородин В.Б. Калинин A.B. Системы на микроконтроллерах и БИС программируемой логики. -М.: Издательство ЭКОМ, 2002. - 400 с.

54.Комолов Д.А., Мяльк P.A., Зобенко A.A., Филлипов A.C. Системы автоматизированного проектирования фирмы Altera: MAX+plus II и Quartus II/ -М.: ИП Радиософт, 2002. -352 с.

55.Бутаев М.М., Вашкевич Н.П., Гурин Е.И., Коннов H.H. Проектирование цифровых устройств на программируемых логических интегральных схема. - Пенза: Изд-во пенз. Гос. Техн. университета, 1996. -65 с.

56.Угрюмов. Цифровая схемотехника. — Спб.: БХВ-Петербург, 2010. — 798 с.

57.0гнев И.В., Сидорова H.A. Реализация деревьев с использованием ресурсов памяти ПЛИС / радиоэлектроника, электротехника И ЭНЕРГЕТИКА: 16 международная научн.-техн. конф. студентов и

аспирантов: Тезисы докладов. -М.: Издательский дом МЭИ, 2010. —с. 394395.

58.Огнев И.В., Огнев А.И., Горьков А.Г. Аппаратная реализация дерева секущих на ПЛИС / Труды XVIII международной научно-технической конференции «Информационные средства и технологии». - Том 1. — М: Издательский дом МЭИ, 2010. - с. 36-43.

59.Огнев И.В., Сидорова H.A. Реалзация системы обработки и распознавания образов в ассоциативной осцилляторной среде / Известия высших учебных заведений. Поволжский регион. - 2008. Спец. Вып. 2. -с. 98-104. (Технические науки).

Приложение Формирование базы элементов

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

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

UGlobal - модуль, содержащий основные константы и типы данных;

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

UProcess - модуль, в котором происходят основные вычисления (формирование псевдокадра, формирование базы кадра, частичной и полной баз);

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

Основные константы и определения (UGlobal)

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

Листинг 1 Интерфейсная часть модуля UGlobal

type

TBaseType = (btFrag, btLDiff, btMDiff); // Тип базы (фрагменты, логические разности, арифметические разности)

TBaseColor = (RGB_R, RGB_G, RGB_B, YIQ_Y, YIQ_I, YIQ_Q); // Цветовое канал

TFilterType = (ftNone, ftAVG, ftMedian, ftThresold); // Используемый фильтр_

const

ElemH =2; // Высота окна ElemW =5; // Ширина окна ElemSize = ElemH * ElemW; // Размер окна

PicH = 384; // Высота кадра PicW = 510; // Ширина кадра

FrameBaseSize = PicH * PicW div ElemSize; // Количество окон в кадре

var

BaseType: TBaseType; BaseColor: TBaseColor; GrayCode: boolean; BitNum, bpp: byte; FilterType: TFilterType; FilterParam: byte;

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

Элементы и процедуры над ними (UElem) Модуль U Elem содержит программное описание элементов, а также процедуры для сравнения элементов между собой. Полный код модуля UElem приведён в Листинг 2

Листинг 2 Модуль UElem

unit UElem;

interface

uses

UGlobal;

type

TElem = array [1 .. UGlobal.ElemSize] of integer; TPRElem = ATRElem;

TRElem = record

elem: TElem;

count: int64;

end;

function CompareElem(fl, f2: TElem): byte;

implementation

function CompareElem(fl, f2: TElem): byte;

var

i: byte;

r: byte;

begin

r : = 1 ;

i := 1;

while (fl[i] = f2[i]) and (i < UGlobal.ElemSize) do

i : = i + 1 ;

if fl [i] < f2[i] then

r 0;

if fl [i] = f2[i] then

r := 1;

if fl[i] > f2[i] then

r := 2;

result := r;

end;

end.

Элементы представляются в виде массива целочисленных переменных.

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

Функция сравнения элементов function CompareElem возвращает целочисленное значение:

• О-в случае, если первый элемент меньше второго;

• 1 - в случае равенства элементов;

• 2 - в случае, если первый элемент больше второго.

При этом сравнение выполняется поэлементно слева направо. Крайне важно, чтобы во время формирования базы элементов обход окна выполнялся в одном порядке.

Формирование баз (UProcess) UProcess - самый объёмный модуль. В нём содержится код, позволяющий формировать базы элементов. Для повышения быстродействия в модуле определены глобальные переменные, доступные любой процедуре модуля. Описание глобальных переменных приведено в Листинг 3.

Листинг 3 Глобальные переменные модуля UProcess

uses

UGlobal, UElem, SysUtils, Windows, UFMain, USettings, Classes, UStatList;

const

MAX_BUFFER_SIZE = 15000000; type

TPRListElem = ATRListElem;

TRListElem = record elem: UElem.TRElem; prev, next: TPRListElem; end;

TFrame = array [1 .. UGlobal.PicH, 1 .. UGlobal.PicW] of byte;

var

FrameOld, FrameNew: TFrame; //Предыдущий и текущий кадры видеопотока

FrameData: array [1 .. UGlobal.PicH, 1 .. UGlobal.PicW] of integer; // Сформированный псевдокадр

FrameBase: array [1 .. UGlobal.FrameBaseSize] of UElem.TRElem; // База элементов кадра BASE_COUNT: LongWord;

elemBuffer: array [1 .. MAX_BUFFER_SIZE] of TPRElem; // Частичная база

DLF, DLL: TPRListElem; // База, представленная в виде списка

Основная процедура в модуле UProcess - обработка одного кадра (см. Листинг 4)

Листинг 4 Обработка одного кадра

procedure ProcessFrame; begin

FrameOld := FrameNew; LoadFrameFromBitMap; case FilterType of ftNone:;

ftAVG: AVG_Filter(FilterParam, FilterParam); ftMedian: Median_Filter(FilterParam, FilterParam); ftThresold: Thresold_Filter(FilterParam); end;

CreateFrameData; ShowResuitFrame; CreateFrameBase; AddToBase;

FrameNum := FrameNum + 1;

end;_

В процессе обработки одного кадра решаются следующие задачи:

• Фильтрация (в случае необходимости);

• Формирование псевдокадра;

• Формирование базы элементов кадра;

• Добавление сформированной базы в частичную базу.

В зависимости от типа базы процедура формирования псевдокадра значительно отличается (см. Листинг 5):

Листинг 5 Процедура формирования псевдокадра

procedure CreateFrameData; var

row, col: word; val: integer; begin

for row := 1 to UGlobal.PicH do for col := 1 to UGlobal.PicW do begin

if BaseType = btMDiff then _val := FrameNew[row, col] - FrameOld[row, col];

if BaseType = btLDiff then

val := FrameNew[row, col] xor FrameOld[row,

col] t

if BaseType = btFrag then

val := FrameNew[row, col];

if BitNum = 9 then

begin

if val > 0 then

val := 255

else

val : = -255;

end;

if BitNum in [1 . . 8] then

begin

val := val and (1 shl (BitNum - 1));

if val > 0 then

val := 255

else

val := -255;

end;

FrameData [row, col] := val;

end;

end;

Но после формирования псевдокадра база элементов может быть

вычислена с использованием довольно тривиального алгоритма (см. Листинг

Листинг 6 Формирование базы элементов кадра

procedure CreateFrameBase;

var

row, col, i, j, p: word;

k: LongWord;

begin

row := 1;

col := 1;

k := 1;

while row <= UGlobal.PicH - (UGlobal.ElemH - 1) do

begin

while col <= UGlobal.PicW - (UGlobal.ElemW - 1) do

begin

p : = 1;

for i := row to row + (UGlobal.ElemH - 1) do

for j := col to col + (UGlobal.ElemW - 1) do

begin

FrameBase[к].elem[p] := FrameData[i, j]; p := p + 1; end;

FrameBase[k].count := 1; к := к + 1;

col := col + UGlobal.ElemW; end;

row := row + UGlobal.ElemH; col := 1; end;

SealFrameBase;

end;_

Вычисление характеристик базы (UStatList)

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

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

Для хранения вспомогательной базы определена специальная структура (см. Листинг 7)

Листинг 7 Структура хранения вспомогательной базы

type

TPStatElem = ^TRStatElem;

TRStatElem = record ID, count: int64; next, prev: TPStatElem; end;

TRList = record

DLF, DLL: TPStatElem; end;

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

Листинг 8 Функции вычисления характеристик базы

function GetNFilm(): int64; var

NFilm: int64; elem: TPStatElem; begin

NFilm := 0;

elem := L.DLFA.next;

while elem <> L.DLL do

begin

NFilm := NFilm + elemA.ID * elemA.count; elem := elemA.next; end;

GetNFilm := NFilm; end;

function GetNBase(): int64; var

NBase: int64; elem: TPStatElem; t begin

NBase := 0;

elem := L.DLFA.next;

while elem <> L.DLL do

begin

NBase := NBase + elemA.count; elem := elemA.next; end;

GetNBase := NBase; end;

function GetEntropy(): double; var

elem: TPStatElem; P_i, Ent: double; NFilm: int64; begin

elem := L.DLFA.next;

Ent := 0;

NFilm := GetNFilmO; while elem <> L.DLL do begin

P_i := elemA.ID / NFilm;

Ent := Ent - P_i * log2(P_i) * elemA.count; elem := elemA.next; end;

GetEntropy := Ent; end;