Содержание к диссертации
Введение
ГЛАВА 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 Проводник
4.3.2 Узел
4.3.3 Сумматор
4.3.4 Умножитель
4.3.5 Инвертор
4.3.6 Блок
4.3.7 Дифференциальный блок
4.3.8 Накапливающий осциллятор
4.3.9 Вычитающий осциллятор
4.3.10 Дифференциальный осциллятор
4.3.11 Дифференциал
4.4 Аппаратная реализация дерева секущих 111
4.4.1 Базовый клеточный ансамбль секущая 111
4.4.2 Реализация узла дерева секущих на элементах ассоциативной осцилляторной среды 113
4.4.3 Реализация дерева секущих функций 117
4.5 Выводы 122
Заключение 123
Литература 125
- Поточные и словарные алгоритмы сжатия информации
- Алгоритм формирования базы элементов
- Предварительное преобразование видеопотока в коды Грея
- Базовые клеточные ансамбли и осцилляторы в ассоциативной осцилляторной среде
Введение к работе
Актуальность исследования. Разработка методов, алгоритмов и аппаратных сред сжатия видеопотоков является одним из важнейших направлений современных информационных технологий. Методы сжатия видеопотока позволяют уменьшить объём данных, необходимый для его передачи или хранения. С ростом качества изображений и видеоданных всё острее встаёт вопрос об их сжатии без потерь.
На сегодняшний день разработаны эффективные методы для сжатия видео с потерями. Во многих задачах возникающие при сжатии с потерями искажения и артефакты (блочность, замыливание и т.д.) незначительны, но существует широкий круг задач, в которых потери недопустимы. К таким задачам, в частности, относятся охранные системы, научные и медицинские видеоданные, дипломатические и разведывательные записи большой ценности. На текущий момент разработаны различные методы и алгоритмы сжатия видеопотока без потерь. Они используются в следующих распространённых кодеках:
CorePNG использует алгоритм deflate для независимого сжатия каждого кадра. Теоретически кодек поддерживает дельта-кадры, но на практике эта возможность практически не используется;
FFV1 использует метод кодирования с предсказанием и дальнейшим энтропийным кодированием ошибки предсказания;
Huffyuv, как и алгоритм FFV1, использует кодирование с предсказанием, а ошибку предсказания эффективно кодирует с использованием алгоритма Хаффмана;
MSU Lossless Video Codec много лет разрабатывается в лаборатории при МГУ им. Ломоносова.
Однако ряд практических задач требует более эффективного сжатия, поэтому остро стоит вопрос о разработке новых более эффективных методов, позволяющих выполнять сжатие видеопотоков без потерь.
Не менее важной проблемой является обеспечение высокого быстродействия методов сжатия. Закон Мура, предсказывающий удвоение производительности процессоров каждые 18 месяцев, базируется на идее о постоянном совершенствовании полупроводниковых технологий. Однако уже сейчас возможности по улучшению полупроводниковых технологий почти исчерпаны. Кроме того, доминирующая архитектура фон Неймана также ограничивает рост производительности современных компьютеров. В классической фон Неймановской архитектуре предполагается разделение устройств хранения и обработки информации. В соответствии с упомянутым законом Мура производительность процессора удваивается каждые 18 месяцев, но время доступа к памяти за этот же период сокращается менее чем на 10%. В итоге процессор (устройство обработки) вынужден ожидать поступления данных из памяти (устройства хранения), что крайне негативно сказывается на общей производительности системы.
Перечисленные проблемы вынуждают разрабатывать новые архитектуры. Наиболее перспективными являются архитектуры, совмещающие функции
обработки и хранения информации. Современные разработчики сфокусированы на исследованиях клеточных автоматов и однородных вычислительных сред. Одним из наиболее перспективных вариантов реализации архитектуры на основе клеточных автоматов является разработанная на кафедре ВТ под руководством д.т.н. проф. Огнева И.В. ассоциативная осцилляторная среда (АОС). Помимо совмещения функций хранения и обработки информации АОС позволяет выполнять одновременный ассоциативный доступ ко всей хранящейся информации.
Перечисленные достоинства послужили основой для выбора АОС в качестве основы для аппаратной реализации предложенного метода сжатия видеопотока.
Таким образом, актуальной является проблема разработки новых методов, алгоритмов и устройств сжатия видеопотока.
Объектом исследования являются методы сжатия видеопотока, различные их модификации, а также реализация предложенных методов в ассоциативной осцилляторной среде.
Цель работы состоит в исследовании существующих и разработке новых методов, алгоритмов и устройств сжатия видеопотока. Для разработанного метода предлагается аппаратная реализация на основе ассоциативных осцилляторных сред.
Для достижения поставленных целей в диссертации решаются следующие задачи:
Разработка метода фрагментарного сжатия видеопотока;
Разработка алгоритма формирования базы элементов для фрагментарного метода сжатия видеопотока;
Выбор оптимальной конфигурации окна сканирования;
Разработка способов повышения эффективности метода фрагментарного сжатия посредством:
о Разложения видеопотока на битовые плоскости;
о Предварительного преобразования яркости пикселов видеопотока в коды Грея;
о Предварительной фильтрации исходного видеопотока;
о Исключения младших битовых плоскостей.
Методы исследования базируются на теории арифметических и логических основ вычислительной техники, теории информации, математическом и функциональном анализе, теории вероятности и теории сложности алгоритмов. Экспериментальные исследования, подтверждающие полученные в диссертации результаты, проводились путём моделирования на ЭВМ.
Научная новизна работы состоит в следующем:
Разработан новый эффективный метод сжатия видеопотока без потерь,
заключающийся в представлении видеопотока в виде хорошо сжимаемой
цепочки элементов из собранной на основе сжимаемого видеопотока базы
данных;
Разработаны способы повышения эффективности метода фрагментарного
сжатия посредством:
о Разложения видеопотока на битовые плоскости;
о Предварительного преобразования яркости пикселов видеопотока в
коды Грея; о Предварительной фильтрации исходного видеопотока; о Исключения младших битовых плоскостей.
Разработан новый базовый клеточный ансамбль ассоциативной осцилляторной среды - «секущая», позволяющий с малыми аппаратными затратами строить многоуровневые деревья секущих.
Реализованы базовые клеточные ансамбли ассоциативной осцилляторной среды на современных ПЛИС.
На основе разработанного нового базового клеточного ансамбля («секущей») реализовано дерево секущих функций, позволяющее быстро получать префиксные коды.
Практическая значимость полученных результатов заключается в следующем:
Предложенный метод фрагментарного сжатия аппаратно реализован на основе базовых клеточных ансамблей ассоциативной осцилляторной среды;
Предложенный метод и его аппаратная реализация позволяет быстро и с высокой эффективностью сжимать видеопотоки;
Разработан программный комплекс, реализующий метод фрагментарного сжатия, состоящий из следующих блоков:
о Формирование базы элементов;
о Построение дерева секущих функций для сформированной базы
элементов; о Автоматическое построение VHDL-описания дерева секущих на
основе его программного описания; о Кодирование видеопотока. Положения, выносимые на защиту:
Метод фрагментарного сжатия видеопотока, заключающийся в представлении видеопотока в виде хорошо сжимаемой цепочки элементов из собранной на основе сжимаемого видеопотока базы данных;
Способы повышения эффективности метода фрагментарного сжатия посредством:
о Разложения видеопотока на битовые плоскости;
о Предварительного преобразования яркости пикселов видеопотока в
коды Грея; о Предварительной фильтрации исходного видеопотока; о Исключения младших битовых плоскостей.
Новый базовый клеточный ансамбль ассоциативной осцилляторной среды -
«секущая», позволяющий с малыми аппаратными затратами строить
многоуровневые деревья секущих.
Разработанное на основе нового базового клеточного ансамбля («секущей»)
дерево секущих функций, позволяющее быстро получать префиксные коды.
Достоверность научных результатов подтверждена серией экспериментов, выполненных в процессе моделирования предложенных методов на ЭВМ, апробацией работы на международных и региональных конференциях.
Реализация результатов. Полученные результаты внедрены:
в учебный процесс подготовки специалистов с высшим образованием по направлению «Информатика и вычислительная техника» специальности 230104.65 «Системы автоматизированного проектирования» по дисциплине «Организация ЭВМ и систем».
в офтальмологической клинике LegeArtis при создании базы операций и послеоперационных снимков. Сжатие необходимо для уменьшения объёма хранящихся данных, в то же время область применения (медицинская диагностика) не допускает потерь качества изображения.
Апробация работы и публикации. Основные результаты работы докладывались и обсуждались на научных семинарах кафедры вычислительной техники и на трёх международных конференциях «Информационные средства и технологии» в 2010, 2012, 2013 годах.
Результаты, полученные при выполнении диссертационной работы, опубликованы в 6 печатных работах: 6 статьях, включая 2 статьи в изданиях из перечня ВАК.
Структура и объём работы. Диссертационная работа изложена на 139 страницах, из них 124 страницы основного текста, 56 рисунков, 38 таблиц. Состоит из введения, четырёх глав, заключения, списка литературы из 59 наименований и приложения на девяти страницах.
Поточные и словарные алгоритмы сжатия информации
Подавляющее большинство алгоритмов сжатия без потерь может быть отнесено к одной из двух групп:
1. Поточные и словарные алгоритмы. К этой группе относятся алгоритмы семейств RLE (поточные алгоритмы), LZ [14,15] (словарные алгоритмы) и др. Особенностью всех алгоритмов этой группы является то, что при кодировании используется не информация о частотах символов в исходном сообщении, а информация о символах и последовательностях, встречавшихся ранее.
2. Алгоритмы статистического (энтропийного) сжатия. Эта группа алгоритмов сжимает информацию, используя неравномерность частот, с которыми различные символы встречаются в исходном сообщении. К алгоритмам этой группы относятся различные алгоритмы префиксного (с использованием деревьев Шеннона-Фанно, Хаффмана и д.р. [16]) и арифметического кодирования.
В отдельную группу иногда выделяют алгоритмы преобразования информации. Их применение не приводит к непосредственному сжатию информации, но значительно упрощает дальнейшее сжатие с использованием поточных, словарных и энтропийных алгоритмов.
Поточные и словарные алгоритмы сжатия информации Кодирование длин серий или 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. Возвращение последнего столбца полученной матрицы.
Проще всего пояснить это преобразование на конкретном примере. Возьмём строку «АНАНАС» и договоримся, что символом конца строки будет символ «». После выполнения всех циклических перестановок и их лексикографической сортировки в последнем столбце матрицы будет получена строка «ННАААС». Очевидно, что полученная в результате преобразования строка гораздо лучше, чем исходная, сжимается алгоритмом RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв. Обратное BWT-преобразование, позволяющее восстановить исходное сообщение, вычислительно существенно сложнее прямого. Для восстановления исходной строки необходимо выполнить следующие действия: 1. Создать пустую матрицу размером , где – количество символов в закодированном сообщении; 2. Заполнить самый правый пустой столбец закодированным сообщением; 3. Отсортировать строки таблицы в лексикографическом порядке; 4. Повторять шаги 2-3, пока есть пустые столбцы; 5. Вернуть ту строку, которая заканчивается символом конца строки. Реализация обратного преобразования на первый взгляд не представляет сложности, но на практике его эффективность зависит от выбранного алгоритма сортировки. Тривиальные алгоритмы с квадратичной сложностью, очевидно, крайне негативно скажутся на быстродействии, поэтому рекомендуется использовать эффективные алгоритмы сортировки строк [18-20]. После сортировки таблицы, полученной на седьмом шаге, необходимо выбрать из таблицы строку, заканчивающуюся символом «». Легко показать, что это строка единственная.
Основными плюсами группы алгоритмов поточного кодирования являются простота и скорость работы (в том числе и скорость декодирования), а главным минусом является низкая эффективность на неповторяющихся наборах символов. Использование специальных перестановок повышает эффективность алгоритма, но также сильно увеличивает время работы.
Алгоритм формирования базы элементов
Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов реализации кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес узлов при построении дерева постоянно растёт, рано или поздно возникает переполнение. Таким образом, несмотря на концептуальную простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно при кодировании большого количества элементов.
Арифметическое кодирование [23] - один из наиболее эффективных способов сжатия информации. В отличие от алгоритма Хаффмана, арифметическое кодирование позволяет кодировать сообщения с энтропией меньше 1 бита на символ. Так как большинство алгоритмов арифметического кодирования защищены патентами, далее будут описаны только основные идеи.
Предположим, что в используемом алфавите символов с частотами соответственно. Шаги алгоритма арифметического кодирования выглядят следующим образом: 1. В качестве рабочего полуинтервала выбирается [0; 1); 2. Рабочий полуинтервал разбивается на непересекающихся полуинтервалов. При этом длина -го полуинтервала пропорциональна . 3. Если не достигнут конец сообщения, в качестве нового рабочего интервала выбирается -й полуинтервал и переход к шагу 2. В противном случае, вернуть любое число из рабочего полуинтервала. Запись этого числа в двоичном коде и будет представлять собой закодированное сообщение. представлен процесс кодирования сообщения «АБААВ» Рис. 1-3. Пример арифметического кодирования При декодировании необходимо выполнить аналогичную последовательность действий, только на каждом шаге необходимо дополнительно определять, какой именно символ был закодирован.
Очевидным достоинством арифметического кодирования является его эффективность, а самым существенным (за исключением патентных ограничений) недостатком – необходимость высокоточной вещественной арифметики.
Рассмотренные выше алгоритмы могут использоваться для кодирования любой информации, но их использование для сжатия изображений сопряжено с рядом особенностей, рассмотрению которых посвящён текущий раздел. 1.2.1 Сжатие двоичных изображений Проще всего начать рассмотрение алгоритмов сжатия изображений с бинарных изображений (как наиболее удобных для сжатия), а затем расширить описанные идеи на полутоновые и цветные изображения.
Метод кодирования длин серий, разработанный в 1950-х годах, является наиболее простым для понимания методом сжатия двоичных изображений. Основная идея метода заключается в представлении каждой строки бинарного изображения в виде последовательности длин непрерывных групп чёрных и белых пикселей (частный случай рассмотренного ранее поточного алгоритма RLE). Например, вторая строка изображения, приведённого на Рис. 1-4, закодированная методом кодирования длин серий, будет выглядеть следующим образом: 2,3,2. Но в процессе декодирования возникнет неоднозначность, т.к. непонятно, какую серию: чёрную или белую кодирует первое число. Для решения этой проблемы существует два очевидных метода: либо для каждой строки предварительно указывать значение первого пиксела, либо договориться, что для каждой строки сначала указывается длина последовательности белых пикселов (при этом она может быть равна нулю).
Тестовое изображение Метод кодирования длин серий весьма эффективен, особенно для изображений с простой структурой, но этот метод может быть значительно улучшен, если дополнительно сжимать полученные последовательности каким-нибудь энтропийным алгоритмом, например, методом Хаффмана.
Кроме того, энтропийный алгоритм может независимо применяться отдельно для чёрных и белых последовательностей. Например, для печатного текста длинные непрерывные серии чёрных пикселов встречаются значительно реже, чем длинные непрерывные серии белых пикселов. Раздельное энтропийное кодирование позволяет учитывать этот факт, что ещё сильнее увеличивает степень сжатия.
Дальнейшим развитием идеи кодирования длин серий является метод сжатия с отслеживания контуров. Этот метод основан на использовании высокоуровневых свойств сжимаемого изображения. Т.е. изображение воспринимается не просто как набор пикселов, а как объекты переднего плана и фон. Сжатие выполняется за счёт высокоуровневого описания объектов. Тестовое изображение, на примере которого будет показан алгоритм сжатия с отслеживанием контуров, приведено на Рис. 1-5.
Прежде всего надо отметить, что описание каждого объекта должно быть заключено в специальные сообщения (теги) начала и конца объекта. Первый и самый простой способ – указывать координаты начальной и конечной точки контура на каждой строке. Изображение на Рис. 1-5 будет закодировано следующим образом:
Предварительное преобразование видеопотока в коды Грея
Изучив полученные изображения, можно заметить, что на сжатых изображениях возникают отчётливые ложные контуры, которые значительно ухудшают визуальное восприятие. Этот недостаток сильно ограничивает прямое применение квантования для сжатия изображений.
Большинство современных методов удаления визуально избыточной информации используют сведения об особенностях человеческого зрения. Одной из таких особенностей является различная чувствительность человеческого глаза к информации о цветности и яркости изображения. В Табл. 1-7 показано изображение в цветовом пространстве YIQ, закодированное с разной глубиной квантования цветоразностных сигналов IQ: Табл. 1-7. Пример кодирования изображения с разной глубиной квантования цветоразностных компонент 256 уровней 128 уровней 64 уровня Как видно из Табл. 1-7, глубина квантования цветоразностных сигналов может быть понижена с 256 до 32 уровней с минимальными визуальными искажениями. Несмотря на простоту описанных методов, в чистом виде они применяются редко, чаще всего они служат одним из шагов более эффективных алгоритмов.
1.3.3 Кодирование с предсказанием и квантованием Ранее кодирование с предсказанием уже было рассмотрено как весьма эффективный метод сжатия информации без потерь. Если совместить кодирование с предсказанием и сжатие посредством квантования, получится весьма простой и эффективный алгоритм сжатия изображения с потерями.
В описываемом методе квантуется ошибка предсказания. Именно точность её квантования определяет как степень сжатия, так и искажения, вносимые в сжатое изображение.
Выбор оптимальных алгоритмов для предсказания и для квантования -довольно сложная задача. На практике широко используют следующие универсальные (обеспечивающие приемлемое качество на большинстве изображений) предсказатели:
Рассмотрим самый простой и в то же время весьма популярный способ кодирования с потерями - т.н. дельта-модуляцию. Этот алгоритм использует предсказание на основе одного предыдущего пиксела, т.е. Pu = ai Pk-i. Полученная после этапа предсказания ошибка ек = рк — р квантуется следующим образом:
На первый взгляд это очень грубый способ квантования, но у него есть одно неоспоримое преимущество: результат предсказания может быть закодирован одним единственным битом. В Табл. 1-8 показаны изображения, закодированные с помощью дельта-модуляции (обход по строкам) с различными значениями f.
Наиболее заметны два вида искажений - размытие контуров и зернистость изображения. Эти наиболее типичные искажения, возникающие при кодировании с использованием дельта-модуляции, называют перегрузкой по крутизне и шумом гранулярности.
Шум гранулярности возникает в основном на однотонных областях, когда значение f слишком велико для корректного отображения малых колебаний яркости (или их отсутствия). На Рис. 1-6 жёлтой линией отмечена исходная яркость, а синие столбцы показывают возникающий при квантовании ошибки предсказания шум.
Перегрузка по крутизне Ситуация перегрузки по крутизне принципиально отличается от ситуации с шумом гранулярности. В этом случае величина слишком мала для передачи резкого перепада яркости. Из-за того, что яркость закодированного изображения не может расти так же быстро, как яркость исходного изображения, возникает заметная размытость контуров. Ситуация с перегрузкой по крутизне поясняется на Рис. 1-7
Легко заметить, что шум гранулярности уменьшается вместе с уменьшением , но вместе с этим растут искажения из-за перегрузки по крутизне и наоборот. Это приводит к определённым сложостям при выборе величины . Для большинства изображений рекомендуется выбирать [5; 7].
1.3.4 Трансформационное кодирование
Все рассмотренные ранее методы сжатия изображений обрабатывали непосредственно значения яркостей пикселей исходного изображения. Такой подход называют пространственным кодированием. В текущем разделе будет рассмотрен принципиально иной подход, называемый трансформационным кодированием.
Основная идея похожа на рассмотренный ранее способ сжатия с использованием квантования, но квантоваться будут не значения яркостей пикселов, а специальным образом рассчитанные на их основе коэффициенты преобразования (трансформации). Схемы трансформационного сжатия и восстановления изображений приведены на Рис. 1-8, Рис. 1-9.
Сжатое изображение Ф Декодирование коэффициентов Ф Обратное преобразование J - J Рис. 1-9. Схема трансформационного восстановления
Непосредственно сжатие происходит не в момент кодирования, а в момент квантования коэффициентов, т.к. для большинства реальных изображений большая часть коэффициентов может быть грубо квантована. Для получения коэффициентов используют обратимые линейные преобразования: например, преобразование Фурье, дискретное косинусное преобразование или преобразование Уолша-Адамара [26-28]. Выбор конкретного преобразования зависит от допустимого уровня искажения и имеющихся ресурсов.
В общем случае изображение размерами пикселов рассматривается как дискретная функция от двух аргументов (,), тогда прямое преобразование можно выразить в следующем виде:
Набор (,);, = 0,1,2, …,-1 как раз и является искомым набором коэффициентов. На основе этого набора можно восстановить исходное изображение, воспользовавшись обратным преобразованием:
Функции называют ядрами преобразования, при этом функция - ядро прямого преобразования, а функция - ядро обратного преобразования. Выбор ядра преобразования определяет как эффективность сжатия, так и вычислительные ресурсы, требуемые для выполнения преобразования.
Перед кодированием изображение разбивается на квадратные блоки, а затем каждый блок независимо подвергается преобразованию. От выбора размера блока зависит как вычислительная сложность, так и итоговая эффективность сжатия. При увеличении размера блока растёт и эффективность сжатия, и вычислительная сложность, поэтому на практике чаще всего используются блоки размером 88 или 1616 пикселей. После вычисления коэффициентов преобразования они (коэффициенты) подвергаются квантованию и кодированию. Наиболее распространёнными подходами являются зональное и пороговое кодирование.
При зональном кодировании предполагается, что наиболее информативные коэффициенты будут находиться вблизи нулевых индексов полученного массива. Это значит, что соответствующие коэффициенты должны быть наиболее точно квантованы. Другие коэффициенты можно квантовать значительно грубее или просто отбросить. Проще всего понять идею зонального кодирования можно, посмотрев на соответствующую маску (Рис. 1-10):
Примерная маска, используемая при зональном кодировании Число в ячейке показывает количество бит, отводимых для кодирования соответствующего коэффициента.
В отличие от зонального кодирования, где для любого блока используется одна и та же маска, пороговое кодирование подразумевает использование уникальной маски для каждого блока. Пороговая маска для блока строится, исходя из следующих соображений: наиболее важными для восстановления исходного изображения являются коэффициенты с максимальным значением, поэтому, сохранив эти коэффициенты и обнулив все остальные, можно обеспечить как высокую степень сжатия, так и приемлемое качество восстановленного изображения. В Рис. 1-11 показан примерный вид маски для конкретного блока.
Базовые клеточные ансамбли и осцилляторы в ассоциативной осцилляторной среде
При увеличении площади окна и фиксированной глубине цвета отношение — растёт так быстро, что доля кодового дерева в передаче становится доминирующей и ведёт к ухудшению степени сжатия независимо от средней длины получаемых кодов. Обойти эту проблему можно двумя способами:
1. Исследования показали, что при фиксированном размере окна увеличение продолжительности фильма (М) приводит, во-первых, к уменьшению отношения — (за счёт того, что iVfi растёт гораздо медленнее AL), во Доф О ф вторых, к уменьшению Нб ( что априори совсем не очевидно, так как сама база растёт). Отсюда следует, что гораздо выгоднее собирать базу элементов и кодировать её сразу для видеопотоков большой длительности, например, вместо кодирования записей видеонаблюдения по дням гораздо эффективнее закодировать запись за всю неделю или месяц. Кроме того, не исключена возможность создания некой универсальной базы элементов, общей для всех существующих фильмов с фиксированной глубиной цвета . Эта теоретическая база может иметь размеры, позволяющие работать с ней на обычных персональных ЭВМ (особенно при небольших значениях ), а соответствующее ей кодовое дерево может быть заранее известно всем пользователям, что позволит ограничится только передачей последовательности коротких кодов элементов. 2. Второй способ связан с разбиением исходного видеопотока на двоичных видеопотоков (битовых плоскостей). Метод разложения на битовые плоскости заключается в разделении одного изображения с 2 уровнями яркости на бинарных изображений. При этом -ое изображение формируется путём выделения -ых битов из каждого пикселя исходного изображения. Если применить такое разложение ко всем кадрам видеопотока, то будет сформировано бинарных видеопотоков с глубиной яркости в один бит на пиксель, то есть каждый пиксель которых имеет всего два возможных значения яркости.
Метод фрагментарного сжатия битовых плоскостей видеопотока состоит в том, что каждый из сформированных бинарных видеопотоков сжимается по отдельности. При этом для каждого бинарного видеопотока могут быть выбраны свои оптимальные параметры метода. Также при этом легко вычисляется степень сжатия исходного видеопотока как среднее арифметическое степеней сжатия всех видеопотоков, так как объёмы бинарных видеопотоков одинаковы.
Большим преимуществом этого метода является то, что достаточно вычислить базы элементов для каждого бинарного видеопотока, и нет необходимости вычислять общую базу элементов исходного фильма. Это позволяет резко увеличить размеры окна и исследовать степени сжатия видеопотока при ранее недостижимых размерах окон.
Была проведена серия экспериментов [40], в которых видеопотоки, полученные путём выделения битовых плоскостей, кодировались фрагментарным методом сжатия. Результаты экспериментов показывают, что фрагментарное сжатие битовых потоков позволяет переходить к окнам большого размера. Ниже приведена Табл. 3-1, показывающая степень сжатия без потерь для каждой из восьми битовых плоскостей для различных окон (в качестве элемента выступают фрагменты). Для каждого окна также подсчитана средняя степень сжатия, то есть степень сжатия исходного видеопотока.
Очевидно, что в случае битовых плоскостей степень сжатия растёт вместе с увеличением окна. Также видно, что старшие битовые плоскости сжимаются существенно лучше младших. Это объясняется тем, что видеопотоки, получаемые в старших битовых плоскостях, практически полностью состоят из нулевых элементов, в то время как элементы, получаемые в младших битовых плоскостях, сильно зашумлены. Табл. 3-2 наглядно иллюстрирует это: Табл. 3-2. Разности получаемые в различных битовых плоскостях Исходное изображение 8 битовая плоскость 1 битовая плоскость
Отсюда можно сделать вывод, что различные битовые плоскости должны сжиматься разными методами, это позволит резко улучшить степень сжатия. Например, для каждой из битовых плоскостей можно выбирать свою оптимальную конфигурацию окна сканирования. Из Табл. 3-1 получаем , что оптимальной конфигурацией окна для каждой битовой плоскости является окно 4x5, но в общем случае оптимальным для старших битовых плоскостей является окно с большей площадью, чем для младших.
Улучшение коэффициента сжатия (CV = —) при разбиении на битовые плоскости по сравнению со сжатием без разбиения на битовые плоскости показано на Рис. 3-2: 2,5 Зависимость коэффициента сжатия от площади окна 7" S 1.5І J 0,5 : 1 3 4 5 6 S 9 10 12 15 20Площадь окна С разбиениемна битовые плоскости Безразбиения на битовые плоскости Рис. 3-2. Улучшение коэффициента при разбиении на битовые плоскости Показанные в работе степени сжатия для общих баз данных и для битовых плоскостей вовсе не являются предельными. Они могут быть значительно улучшены применением к однобитовым видеопотокам индивидуальных дополнительных методов сжатия.
Предварительное преобразование видеопотока в коды Грея
Ранее уже было показано, что младшие битовые плоскости сильно зашумлены. Шум является случайным плохо сжимаемым сигналом. Это приводит к плохой сжимаемости всего видеопотока в младших плоскостях. Бороться с этим можно, пытаясь выделить из видеопотоков осмысленный сигнал. Одним из способов добиться этого является преобразование яркости пикселей в коды Грея [41].
Довольно очевидным недостатком алгоритма кодирования битовых плоскостей является эффект многократного переноса разрядов при незначительном изменении яркости. Например, при изменении яркости со 127 на 128 произойдёт изменение значений всех двоичных разрядов (0111111 - 10000000), что вызовет изменение во всех битовых плоскостях.
Чтобы снизить негативные последствия от многократных переносов, необходимо использовать специальные коды, например коды Грея, в которых два соседних элемента различаются только в одном разряде. Для перевода 72-битного числа в код Грея необходимо выполнить операцию побитового исключающего ИЛИ с этим же числом, сдвинутым на один бит вправо. Обратное преобразование из кода Грея можно осуществить, выполняя побитовую операцию исключающего ИЛИ для всех сдвигов исходного числа, не равных нулю.
