3

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

Актуальность исследования. Разработка методов, алгоритмов и

аппаратных сред сжатия видеопотоков является одним из важнейших

направлений современных информационных технологий. Методы сжатия

видеопотока позволяют уменьшить объём данных, необходимый для его

передачи или хранения. С ростом качества изображений и видеоданных всё

острее встаёт вопрос об их сжатии без потерь.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

o Построение дерева секущих функций для сформированной базы o Автоматическое построение VHDL-описания дерева секущих на основе его программного описания;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кадр – набор всех видимых пикселей в конкретный момент времени.

Количество строк пикселей в кадре называется высотой кадра и обозначается в дальнейшем 1. Аналогично количество столбцов пикселей в кадре называется шириной кадра и обозначается 2. Таким образом кадр может быть представлен в виде матрицы чисел [1 2 ].

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

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

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

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

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

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

Объём фильма – общее количество элементов в кодируемом фильме.

Объём фильма обозначается ф и вычисляется по следующей формуле: ф = Частота элемента – отношение количества появлений конкретного элемента в кодируемом фильме к объёму фильма (ф ).

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

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

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

Вторая часть главы посвящена выбору способа получения кодов элементов. К этому двоичному коду предъявляются следующие требования:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Влияние характеристик окна сканирования на коэффициент сжатия () практически невозможно выразить аналитически.

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

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

Искусственные видеопотоки. Отличительной особенностью видеопотоков, отнесённых ко второй группе, является неестественность их происхождения.

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

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

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

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

Alpary;

ArithYuv;

AVIzlib;

CamStudio GZIP;

CorePNG;

FastCodec;

FFV1;

Huffyuv;

Lagarith;

LOCO;

LZO;

MSU Lab;

PICVideo;

Snow;

x264;

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

Табл. 1. Используемые при сравнении видеопоследовательности последовательность Каждая видеопоследовательность была сжата каждым кодеком независимо. Полученные результаты приведены на Рис. 4:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Табл. 3. Таблица истинности одноразрядной секущей функции

DIGIT DIGIT_VALUE SECANT

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

А на основе СДНФ – аппаратную реализацию, используя базовые клеточные ансамбли (см. Рис. 7):

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

приведены в Табл. 4:

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

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

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

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

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

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

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

1. Предложен новый метод сжатия видеопотока – фрагментарный метод.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Издательский дом МЭИ, 2010. – с. 36-43.

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

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