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

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

Горьков Алексей Геннадьевич

МЕТОД, АЛГОРИТМЫ И УСТРОЙСТВА ФРАГМЕНТАРНОГО СЖАТИЯ ВИДЕОПОТОКА

Специальность 05.13.05 - Элементы и устройства вычислительной техники

и систем управления

АВТОРЕФЕРАТ

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

г 1 пай т

Москва-2014

005548566

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

Научный руководитель: доктор технических наук, профессор Огнев

Иван Васильевич

Официальные оппоненты: Комарцова Людмила Георгиевна, д.т.н.,

доцент, Калужский филиал МГТУ им. Баумана, профессор кафедры Компьютерные системы и сети. Плахов Александр Геннадьевич, к.т.н., ООО «Сандракс», генеральный директор.

Ведущая организация: ОАО «Концерн «Моринформсистема-Агат»

Защита состоится 27 июня 2014 года в 1Ц часов 00 минут на заседании диссертационного совета Д 212.157.16 при ФГБОУ ВПО «НИУ МЭИ» по адресу: 111250, г. Москва, ул. Красноказарменная, д. 17, ауд. Г-306.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБОУ ВПО «НИУ МЭИ», www.mpei.ru

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 111250, г.Москва, Красноказарменная ул., д. 14, Учёный совет МЭИ.

Автореферат разослан «3& » а.п/1<?/15С 2014 г,

Учёный секретарь диссертационного совета Д 212.157.16, к.т.н., доцент

Чернов С. А.

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

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

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

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

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

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

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

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

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

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

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

обработки и хранения информации. Современные разработчики сфокусированы на исследованиях клеточных автоматов и однородных вычислительных сред. Одним из наиболее перспективных вариантов реализации архитектуры на основе клеточных автоматов является разработанная на кафедре ВТ под руководством д.т.н. проф. Огнева И.В. ассоциативная осцилляторная среда (АОС). Помимо совмещения функций хранения и обработки информации АОС позволяет выполнять одновременный ассоциативный доступ ко всей хранящейся информации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

следующем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация результатов. Полученные результаты внедрены:

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

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

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

Результаты, полученные при выполнении диссертационной работы, опубликованы в 6 печатных работах: б статьях, включая 2 статьи в изданиях из перечня ВАК.

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

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

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

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

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

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

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

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

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

Первым рассмотренным методом сжатия является метод кодирования длин серий, заключающийся в замене повторяющихся последовательностей символов записью вида <число повторовХсимвол>. Несмотря на простоту метода, его практическое применение весьма ограничено ввиду малой эффективности. Далее рассмотрено несколько способов повышения эффективности рассмотренного метода: кодирование длин неповторяющихся последовательностей и сортирующие перестановки на примере В\УТ-преобразования.

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

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

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

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

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

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

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

числовых значений, каждое из которых соответствует определённому цветовому каналу.

Кадр - набор всех видимых пикселей в конкретный момент времени. Количество строк пикселей в кадре называется высотой кадра и обозначается в дальнейшем Л^. Аналогично количество столбцов пикселей в кадре называется шириной кадра и обозначается Ы2. Таким образом кадр может быть представлен в виде матрицы чисел [Л^хЛу.

Видеопоток (фильм) - упорядоченная по времени последовательность кадров. Длиной видеопотока будем называть количество кадров в нём и обозначать М — общее число кадров в фильме.

Окно сканирования - прямоугольная область кадра высотой щ и шириной п2 пикселей.

Фрагмент - цифровое представление окна сканирования. Для хранения фрагмента проще всего использовать битовую строку длиной к = п1*п2* Ьрр бит.

Логическая разность фрагментов - результат побитового применения операции исключающего ИЛИ к двум фрагментам, полученным в соответствующих окнах соседних кадров. Логическая разность фрагментов, как и сам фрагмент, представляется в виде двоичной строки длиной к = п1*п2* Ьрр бит.

Арифметическая разность фрагментов — результат попиксельного вычитания яркостей в соответствующих окнах соседних кадров, представленный в виде битовой строки. Арифметическая разность фрагментов, в отличие от фрагментов и их логических разностей, представляется в виде двоичной строки длиной к = п1*п2* Ьрр + п1*п2 бит.

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

Объём фильма — общее количество элементов в кодируемом фильме. Объём фильма обозначается Щ и вычисляется по следующей формуле: Л^ = лг

П!»П2

Частота элемента — отношение количества появлений конкретного элемента в кодируемом фильме к объёму фильма (ЛГф).

База элементов - набор всех присутствующих в видеопотоке элементов и их частот. Мощность базы элементов обозначается Ыб, информационная энтропия базы элементов обозначается Нб.

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

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

энтропией. Свойство минимальной избыточности позволяет добиться высокой эффективности сжатия. • Префиксность - то есть ни один код не является началом никакого другого кода. Любому префиксному коду можно поставить в соответствие двоичное дерево, называемое кодовым. Короткий двоичный код, который ставится в соответствие элементу, можно получать как код траектории от корня до листа (соответствующего элементу) в кодовом дереве.

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

Слово - последовательность из ш бит (число ш называют разрядностью слова).

Литерал секущей - пара вида разряд-значение разряда. Например, литерал (4,1) означает, что четвёртый бит слова сравнивается с 1. Если условие литерала выполняется, то литерал считается истинным, в противном случае -ложным.

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

Процесс построения дерева заключается в поиске секущей, позволяющей разделить информационный массив на две максимально близкие по весу части. В каждом узле сначала выполняется поиск одноразрядной секущей, дающей наилучшее разделение, а затем происходит итеративный процесс добавления разрядов. Таким образом с методологической точки зрения метод секущих функций является вариантом метода Шеннона-Фано. Отличие состоит в том, что деление исходного массива секущими функциями не позволяет получить разделение на две любые наперёд заданные комбинации строк с их весами. На Рис. 1 показан пример дерева секущих:

г (4;0)

г (2;0) -

1000 (111)

1100(110)

L (2;0)

rjOOOl (101)

1101(100)

L (2;0)

(1;о)

0011(011)

0111(00)

1011(010)

Рис. 1. Пример дерева секущих функций

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

• Поиск необходимого элемента среди листьев дерева;

• Восстановление траектории от корня к найденному листу.

Поиск необходимого листа можно выполнить, совершив обход всех листьев дерева. Сложность этой процедуры составляет 0(М), где N -количество листьев. Восстановление траектории до листа потребует ещё 0(1одЩ операций. В большинстве случаев эта сложность приемлема, но в методе фрагментарного сжатия количество листьев в соответствующем дереве очень велико. Кроме того, процедура поиска и восстановления траектории должна выполняться для каждого элемента из сжимаемого видеопотока. Таким образом общая сложность кодирования видеопотока методом Хаффмана составляет 0(Мф * (Л^ + /о(?/Уб)) ~ * Очевидно, что мощность базы элементов (Л^) не позволяет использовать кодирование Хаффмана напрямую.

Далее во второй главе рассматривается вопрос оптимизации окна сканирования и сравнение эффективности сжатия с другими распространёнными методами.

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

виде:

* Ы2 * М * Ьрр (п! *п2* Ьрр+ 2)* М* ^ * Я6

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

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

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

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

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

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

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

Зависимость коэффициента сжатш от конфигурации окна (студийные съёмки)

Рис. 2. Коэффициент сжатия (естественные съёмки)

Зависимость коэффициента сжатия от конфигурация окна (мультфильмы)

2

Рис. 3. Коэффициент сжатия (мультфильмы)

Из графиков видно, что наилучшее сжатие достигается при использовании четырёхпиксельного окна, при этом коэффициент сжатия составляет примерно 3,4 (для студийных съёмок) и 5,2 для мультфильмов.

В Graphics & Media Lab Video Group при МГУ им. Ломоносова было выполнено обширное сравнение алгоритмов сжатия видео без потерь по множеству параметров (скорости компрессии, расходу ресурсов, эффективности сжатия и т.д.). Наиболее важной характеристикой является эффективность сжатия. По этому критерию были проанализированы следующие кодеки: Alpary; ArithYuv; AVIzlib;

CamStudio GZIP; CorePNG; FastCodec; FFV1; Huffyuv; Lagarith; LOCO; LZO; MSULab; PICVideo; Snow; x264; YULS

Сравнение выполнялось на стандартных тестовых последовательностях, приведённых в Табл. 1:

Тестовая последовательность Количество кадров Разрешение

Foreman 300 352x288

Susi 374 704x576

Tennis 373 704x576

ВВС 374 704x576

Battle 1599 704288

News 32 720x480

Da 262 720x352

Mi 261 640x272

Bankomat 376 704x352

независимо. Полученные результаты приведены на Рис. 4:

13

Сотрге£5к>п гаНа (¡№324)

(ОПИТИГ) б я! ЬЬс Ьо*в Ьайэ ващлпе* пет ¿а т Ьаг*

-»-«рау^и!) -*-А1ршу(Мп) -*-АуИй(Раг!) -*-СогеРМ2<Ов(в1Й) СогаРР*5(Рм1) -А- РП/Т(1Лц) НиЯЧ\л?>Аи) СогвРНС(Мк} -*- Саш5и*6о<Ра?1) -•♦--иОССНОеЛиИ)

-к-Ь&ХОеЬпЩ

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

Сравнение эффективности сжатия

1 И

... _ 1 1 Е

Мпед сжатия

Рис. 5. Средние коэффициенты сжатия исследуемых методов Прямое применение метода фрагментарного сжатия на этих тестовых видеопоследовательностях оказывается малоэффективным. Это объясняется тем, что длительность тестовых видеопотоков очень мала и существенную часть в сжатом методом фрагментарного сжатия фильме составляет база элементов (см. Рис. 6).

Рис. 6. Зависимость характеристик базы элементов от времени При достаточной длительности видеопотока (от 5000 кадров) средний коэффициент сжатия метода фрагментарного сжатия составляет 3,38, что превышает коэффициенты сжатия лучших из рассмотренных методов.

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

Первым рассмотрен способ разбиения видеопотока на битовые плоскости. Метод разложения на битовые плоскости заключается в разделении одного изображения с 2Ьрр уровнями яркости на Ьрр бинарных изображений. При этом £-е изображение формируется путём выделения i-x битов из каждого пикселя исходного изображения. Если применить такое разложение ко всем кадрам видеопотока, то будет сформировано Ьрр бинарных видеопотоков с глубиной яркости в один бит на пиксель, то есть каждый пиксель которых имеет всего два возможных значения яркости. Большим преимуществом этого метода является то, что достаточно вычислить базы элементов для каждого бинарного видеопотока и нет необходимости вычислять общую базу элементов исходного фильма. Это позволяет резко увеличить размеры окна и исследовать степени сжатия видеопотока при ранее недостижимых размерах окон. Была проведена серия экспериментов, в которых видеопотоки, полученные путём выделения битовых плоскостей, кодировались фрагментарным методом сжатия. Результаты экспериментов показывают, что фрагментарное сжатие битовых потоков позволяет переходить к окнам большого размера тем самым повышая эффективность сжатия.

Вторым способом повышения эффективности предложенного метода является преобразование яркостей пикселов в коды Грея. Довольно очевидным недостатком алгоритма кодирования битовых плоскостей является эффект многократного переноса разрядов при незначительном изменении яркости. Например, при изменении яркости со 127 на 128 произойдёт изменение значений всех двоичных разрядов (0111111—>-10000000), что вызовет изменение во всех битовых плоскостях. Чтобы снизить негативные последствия от многократных переносов, необходимо использовать специальные коды, например, коды Грея, в которых два соседних элемента различаются только в

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

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

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

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

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

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

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

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

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

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

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

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

Предложена реализация базовых клеточных ансамблей ассоциативной осцилляторной среды на современных ПЛИС. Например, в Табл. 2 показана реализация базового клеточного ансамбля «БЛОК» _Табл. 2. Базовый клеточный ансамбль «блок»

Графическое обозначение

Таблица истинности

га

EHÉhsí

Основной вход

о

О

1

Блокирующий _ вход

1

Выход

О

Аппаратная реализация

i blocking basic

inverter

4zn ou'

Jltipller

1Н1

1нг оит

1НЗ

glffUff"

— btackíng

Временная диаграмма работы

100.От 200.0т 300.От <00. Рп» 500.0пв . 600.0м 700.0пв 000.0л* 900.0м 1£:

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

DIGIT DIGIT VALUE SECANT

0 0 1

0 1 0

1 0 0

1 1 1

При этом DIGIT — значение анализируемого разряда распознаваемого образа, DIGITJVALUE - значение соответствующего разряда секущей, а SECANT - результат вычисления секущей функции. По Табл. 3 можно построить СДНФ:

SECANT = WGIT&DIGIT VALUE WDIGIT&DIGIT VALUE А на основе СДНФ - аппаратную реализацию, используя базовые клеточные ансамбли (см. Рис. 7):

Рис. 7. Реализация одноразрядной секущей функции узла на основе БКА АОС Полученная функция выполняет важную логическую операцию эквиваленции. Для упрощения дальнейшего практического использования ассоциативных осцилляторных сред было принято решение включить эту функцию (секущую) в список базовых клеточных ансамблей. Графическое обозначение и аппаратная реализация нового клеточного ансамбля «секущая» приведены в Табл. 4:

_Табл. 4. Базовый клеточный ансамбль «секущая»_

Графическое обозначение

/

D V

Аппаратная реализация

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

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

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

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

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

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

2. Метод фрагментарного сжатия видеопотока обобщён для сжатия цветных видеопотоков, экспериментально показана большая эффективность сжатия при кодировании в цветовом пространстве YIQ по сравнению с цветовым пространством RGB.

3. Проведено сравнение предложенного метода с другими известными методами сжатия видеопотоков без потерь. Показано, что разработанный метод обеспечивает более высокий коэффициент сжатия (3,38 раз), чем рассмотренные методы, обеспечивающие сжатие в диапазоне от 1,5 и до 3,25 раз.

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

5. Предложены способы повышения эффективности метода фрагментарного сжатия. Исследована возможность разделения видеопотока на битовые плоскости и применения метода фрагментарного сжатия к каждой плоскости по отдельности. За счёт сравнительно малого размера базы элементов удаётся добиться высокой эффективности общего сжатия.

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в периодических изданиях, рекомендованных ВАК:

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

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

Публикации в других изданиях:

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

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

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

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

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

Подписано в печать

Зак. т Тир. т П.Л.

Полиграфический центр МЭИ Москва, ул. Красноказарменная, д. 13

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ»

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

04201458271

ГОРЬКОВ АЛЕКСЕЙ ГЕННАДЬЕВИЧ

МЕТОД, АЛГОРИТМЫ И УСТРОЙСТВА ФРАГМЕНТАРНОГО

СЖАТИЯ ВИДЕОПОТОКА

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 алгоритма на неповторяющихся последовательностях символов.

Вто