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

МИНИСIЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

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

Погорелов Константин Владимирович

РАЗРАБОТКА БЫСТРОДЕЙСТВУЮЩИХ АЛГОРИТМОВ КОМПРЕССИИ ВИДЕОДАННЫХ С ИСПОЛЬЗОВАНИЕМ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ВТОРОГО ПОРЯДКА

Специальности: 05.13.17 - Теоретические основы информатики 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Таганрог 2005

Работа выполнена в Таганрогском Государственном Радиотехническом университете.

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

Кравченко Павел Павлович

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

Макаревич Олег Борисович

кандидат технических наук, доцент Байлов Владимир Васильевич

Ведущая организация: НИИ вычислительных,

информационных и управляющих систем - структурное подразделение ЮРГТУ (НПИ) (г. Новочеркасск)

Защита состоится "30" и. ЮН Я 2005 г. в -/ Ц часов на заседании диссертационного совета Д.212.259.02 Таганрогского Государственного Радиотехнического университета по адресу (347928, Таганрог, Ростовская область, ГСП-17А, пер. Некрасовский, 44).

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан мая _2005 г.

Ученый секретарь диссертационного совета Д 212.259.02

^ Бабенко Л.К.

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

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

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

В качестве решения отмеченных проблем в данной работе рассматривается применение оптимизированных алгоритмов дельта-преобразования второго порядка и алюритмов усеченного блочного кодирования. Алгоритмы оптимизированных дельта-преобразования второго порядка отличаются простотой реализации, широким динамическим диапазоном и высокой скоростью восстановления закодированного сигнала Вопросы построения алгоритмов дельта-преобразования второго порядка освещены в работах Р. Стила, А В Шилейко, Г.Г. Меньшикова, <3е Jeager Р. и многих других. Основной проблемой для применения известных алгоритмов дельта-преобразования второго порядка долгое время оставалась нестабильность (неустойчивость) преобразований, в связи с чем, эти алгоритмы практически оказывались непригодными.

Алгоритмы дельта-преобразований второго порядка,

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

их базе возможно построение более

•мммФтекА

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

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

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

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

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

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

Анализ существующих методов и алгоритмов компрессии видеоданных, выявление их достоинств и недостатков;

- Анализ методов оценки качества кодирования видеоданных;

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

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

Разработка алгоритма >правления скоростью выходного битовою поюка видеокодека;

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

- Проведение экспериментальных исследований программной модели видеокодека.

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

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

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

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

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

, и при кодировании видеоданных за счет применения разностных

алгоритмов с низкой вычислительной трудоемкостью и высоким качеством кодирования видеоинформации;

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

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

Практическая ценность.

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

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

3. Алгоритм быстрого выбора оптимальной шаблонной матрицы для алгоритма межкадрового видеокодирования;

4 Формат хранения выходного потока кодирующего устройства для хранения и передачи закодированных видеоданных;

5. Программный модуль для компрессии и декомпрессии видеоданных;

6. Динамическая библиотека, содержащая программные процедуры компрессии и декомпрессии видеоданных;

7. Оценки и рекомендации по выбору наилучших параметров для кодирования видеоданных;

8. Программная система многоточечной видеококференцсвязи "Дельта-конференция" с функцией видеоконференции на основе разработанных алгоритмов компрессии.

Результаты, полученные в работе, использовались в рамках х/д НИР. № г.р. 01 200.100690-«Разработка принципов и положений видеокодирования на основе оптимизированных дельта-преобразований второго порядка»; № гр 01.200.11468 - «Разработка алгоритмов и программной модели кодека внутрикадрового кодирования видеоданных на основе оптимизированных дельта-преобразований второго порядка. Проведение испытаний разработанного алгоритма компрессии», № г.р. 01 200 202147- «Разработка алгоритмов межкадрового кодирования и адаптивного управления скоростью выходного потока кодера видеопоследовательностей»; № г р. 01200216955 - «Программная реализация системы передачи видеоинформации с компрессией в режиме реального времени по 1Р-сети. Проведение экспериментальных исследований»; № г.р. 01200407218 - «Разработка программной системы конференцсвязи с поддержкой функций документ-конференции и аудиовидеоконферениии для локальных 1Р-сетей» совместно с ОАО ВНИИ ТР (г. Москва)

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

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на Международных, Всероссийских научно-технических конференциях. В том числе на- Ш Международной конференции "Телевидение: передача и обработка изображений", Санкт-Петербург, 2003; Международной научно-технической конференции "Интеллектуальные системы (IEEE AIS'03)"h "Интеллектуальные САПР (CAD-2003)", Москва, 2003; V Международной конференции "Digital Signal Processing and its Application", Москва, 2003; Международной научно-технической конференции "Informatics, Mathematical Modeling and Design, Владимир, 2004: Всероссийской конференции сгудентов, аспирантов и молодых ученых "Технологии Microsoft в теории и на практике", Москва, 2005.

Публикации

Результаты, полученные в работе, нашли отражение в 36 печатных работах, среди них 7 статей, 22 тезиса доклада и 2 свидетельства Всероссийского бюро по патентам и товарным знакам №2004610864 "Программа компрессии видеоинформации с использованием алгоритмов оптимизированных дельта-преобразований второго порядка" и № 2004610863 "Программа многосторонней видеоконференцсвязи для корпоративных локальных IP-сетей "Дельта-конференция".

Структура и объем работы.

Диссертация состоит из введения, пяти глав, заключения, списка литературы и семи приложений. Материал основной части диссертационной работы изложен на 196 страницах машинописного текста и содержит 20 таблиц, 61 рисунок, ПО библиографических источников и 18 страниц приложений.

Содержание работы.

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

В первой главе проведен обзор основных методов компрессии видеоинформации в рассматриваемой предметной области.

Анализ методов кодирования данных без потерь информации выявил серьезные недостатки (высокая трудоемкость, низкая степень компрессии) при их использовании для кодирования нескольких потоков видеоданных в

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

Однако, проведенный дополнительный анализ показал возможность построения высокоэффективных алгоритмов видеокодирования с использованием разностных алгоритмов В частности, в Таганрогском г осу дарственном радиотехническом университете (ТРТУ) разработаны алгоритмы оптимизированных дельта-преобразований второго порядка, отличи ¡ельными особенностями которых являются простота, высокое быстродействие, устойчивость. возможнос1ь обработки интенсивно изменяющегося сигнала, его сглаживания и эффективной компрессии Улучшенные качественные характеристики алгоритмов оптимизированных делма-преобразований второго порядка в сочетании с их высоким быстродействием позволили выбрать их в качестве базовых для разработки новых высокопроизводительных методов видеокомпрессии Также интерес представтяют методы адаптивного группового кодирования, основанные непосредственно на свойствах интеграционного восприятия изображений зрительным анализатором, и косвенно учитывающие статистику изображений, а именно - алгоритм усеченного блочного кодирования. Суть усеченного блочного кодирования заключается в том, что все изображение разбивается на непересекающиеся бпоки, параметры визуального представления которых подвергаются квантованию и подстраиваются не под некоторую усредненную характеристику изображения, а под локальные особенности каждого кодируемого блока. Данный подход позволяет сохранить мелкие детали изображений, не приводит к «размытию» границ и характеризуется сравнительно низкой трудоемкостью и является перспективным для построения на его базе новых высокоэффективных алгоритмов видеокодирования.

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

Вторая глава посвящена разработке алгоритмов

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

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

Для определения необходимости изменения типа применяемой для аппроксимации видеосигнала функции используется анализ знаков вторых разностей кодируемых видеоданных (квантов модуляции). Разработанный комбинированный алюритм дельта-преобразования для видеокодирования использует анализируемые параметры процесса аппроксимации сигнала для выбора типа используемого алгоритма дельта-преобразования и может быть записан следующим образом: Кодирование: Zj - Y, -

4>'< = (у,+2-У№

если type,. ¡-ДМ] то AY,- О Az, — AY, - Ayi

F,=z, + 1. SAz, + (O.SAz,2/c - 0.125c)sign(AzJ; 4+/ = -sign(FJ;

condl -- (гуре,_г=ДМ2) & (type,.^M2) & (A, <> A,.,) cond2 = (type^MJ) & (1уре,.,=ДМ!) & (Al+, <> AJ & (AiH о A,.,) cond3 = (type, 2=ДМ1) & (1уре,_,=ДМ1) & (\s,\<3) & (A,+] = AJ & (A,H = A,.,) cond4 = (\Si\<3)

если (~cond3) & (condl vcond2 vcond4) mo typei =ДМ1 Yi+I = F, + A,+l с *

иначе

type, ~ ДМ2 AYl+l = AY; + A,+1c* Y,+l=Yi + AYM конец если если (A,+t = AJ mo s, = s, + 4+i иначе

s, = A„,

конец если

Декодирование:

если ¡уре-,.1=ДМ1 то AY, = О

condl = (1уре,^-ДМ2) & (¡уре,.,=ДМ2) & (А, о A, J

cond2 = (1уре12=ДМ1) & (type, ,=ДМ1) & (A,+l <> AJ & (А1+1 о A.J

condl = (¡уре^ДМ)) & (type-, ,=ДМ1) & ф,|<?) <fe (А,.А) & (A,+l = A,. J

cond4 = (\Si\<3)

если (~cond3) & (condl vcond2 vcond4) mo type,-ДМ1 Y,4 = F, + Al+I c*

иначе

typei —ДМ2 AY,+/ = AY, + A,+,c* У,+/ = Yi + AYi+l конец если если СД+/ = AJ то s, = Si + A,+1 иначе

= Ai+, конец если,

где type, - тип алгоритма делыа-преобразования на текущем шаге, condl - условие перехода на алгоритм дельта-преобразований первого порядка, cond2 - условие продолжения алгоритма дельта-преобразований первого порядка; cond3 - условие перехода на алгоритм дельта-преобразований второго порядка; s, - сумма квантов одного знака; cond4 -дополнительное условие продолжения дельта-преобразований первого порядка, AY', , - масштабированное значение первой разности декодированной функции для алгоритма дельта-преобразований второго порядка; & - операция "логическое И", v - операция "логическое ИЛИ"; - -операция "логическое НЕ".

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

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

F,=z, + 1.5Az, + (0.5Azi/с - 0.125c)\ign(AzJ;

Д+í = -sign(F¡);

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

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

Поэтому для повышения быстродействия алгоритма кодирования/декодирования с сохранением качественных характеристик преобразования на участках с ошибкой дельта-преобразования, превышающей пороговое значение, вводится отсчет дифференциальной импульсно-кодовой модуляции (ДИКМ). Значение отсчета выбирается из таблицы в соответствии с величиной z, в приведенном выше комбинированном алгоритме дельта-преобразования Общая структурная схема модифицированного алгоритма кодирования отсчетов строки изображения приведена на рис.1

Рисунок 1 - Общая структурная схема алгоритма кодирования отсчетов строки изображения.

Результаты работы разработанного алгоритма внутрикадрового витеокодирования на различных по характеру участках видеосигнала приведены на рис. 2.

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

разработанного алгоритма видеокодирования

На основании проведенного анализа разработанного комбинированного алгоритма видеокодирования рассчитаны нижние и верхние оценки трудоемкости реализации алгоритмов кодирования и декодирования (см. табл. 1).

Таблица 1 - Трудоемкость разработанного алгоритма внутрикадровой _видеокомпрессии

Гин обраба!ываемого участка сшнала Выполняемые операции Трудоемкость

Кодирование Декодирование

Гладкие участки изображения 1 Дельта-преобразование 9 операций/ пиксел 2 операции/ пиксел

Резкие изменения видеосигнала 1 Дель га-преобразование 2 Вставка корректирующих ДИКМ отсчетов 13 операций/ пиксел * операций' пиксел

Вычислительная трудоемкость разработанного алгоритма внутрикадрового кодирования (от 9 до 13 операций/пиксел) во много раз ниже фудоемкости реализации процедур внутрикадрового кодирования в современных стандартах видеокомпрессии (порядка 102 операций/пиксел) и их оптимизированных по быстродействию модификаций (порядка от 0.4*102 до 0.8*102 операций/пиксел).

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

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

- дополнительная обработка изображений перед компрессией, основанная на законах психовизуального восприятия (фильтрация) Позволяе г повысить коэффициент компрессии в 1.1-1.5 раз при незначительном снижении качества кодирования («размытие» и сглаживание границ).

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

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

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

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

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

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

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

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

Таким образом, блок межкадровой разности может быть закодирован с использованием не более пяти параметров (Р,, РР,, К2, К,). которые вычисляются по следующему алгоритму:

Р2 = тах

к<Е[\-,М)

К2=к(Р2);

Рт, = шах

" кф,М\

2М

1де N - размер квадратной матрицы блока (в данном кодере Л'=4); 5-матрица кодируемого блока, ТУ и Тк" ~ матрицы шаблонов аппроксимации лзя второго и третьего коэффициентов соответственно; М - количество шаблонныч матриц: Рь Р2, Р? - коэффициенты масштабирования блока, к(Р„) - функция, возврашаюшая номер шаблонной матрицы, при которой было получено значение параметра Р„\ К2, К3 - номера шаблонных матриц блока

Для передачи закодированного блока может использоваться либо одно значение (Л<), либо два значения (Р,, К2 и Р2). либо пять значений (Р), К2, Р2, К3. Я?) Для повышения степени компрессии значения Р/, Р2, Рз могут дополнительно кодироваться с использованием нелинейной шкалы квантования и методов статистического кодирования.

В ботыиинстве практических задач кодирования выполнение всех трех шагов уточнения не является необходимым Для оценки необходимости использования следующего цша кодирования вводятся параметры Е1 и Е2. Значение Е1 характеризует порог точности представления блока его средним значением Если все значения элементов матрицы Б' после выполнения шага |)е превышают по абсолютному значению величину Еь то считается, что блок аппроксимирован достаточно точно и нет необходимости в выполнение остальных шагов. Аналогичная процедура применяется после выполнения шага 2, но в этом случае используется параметр Е2

Формально, процесс декодирования состоит из трех шагов, причем два последних шага выполняются только при наличии признака их необходимости

/е [1;Лт],у е [1;АГ];

г г е[1;ЛП, / е [1;ЛГ];

= + Р2ТК} , / е [1; лау е [1;^],

где Я - матрица декодированного разностного блока.

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

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

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

Таблица 2 - Трудоемкость разработанного аш оритма межкадровой _видеокомпрессии

Тип обрабашваемою участка сигнала Выполняемые операции Трудоемкость

Кодирование Декодирование

Статичные участки видеосцены 1 Кодирование блока средним 3 операции/ пиксел 1 операция/ пиксел

Участки видеосцены с бочьи/ьм количеством движущихся объектов 1 Кодирование блока средним 2 Два шага аппроксимации шаблонными матрицами 10 операций/ пиксел 3 операции/ пиксел

Вычислительная трудоемкость разработанного метода межкадрового кодирования (от 3 до 10 операций/пиксел) во много раз ниже трудоемкости реализации процедур межкадрового кодирования в современных стандартах видеокомпрессии (порядка 103 операций/пиксел) и их оптимизированных по быстродействию модификаций (порядка от 4*102 до 5*102 операций/пиксел)

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

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

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

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

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

битовый поток

Рисунок 3 - Структурная схема программной модели кодера видеоданных

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

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

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

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

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

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

Таблица 3 - Влияния параметров алгоритмов на качественные и количественные характеристики процесса видеокодирования

Алгоритм Параметр Влияние на работу алгоритма

Внутрикадровое кодирование Вес кванта модуляции Не оказывает существенного влияния на изменение коэффициента компрессии

Порог овое значен не ошибки для введения от счета ДИКМ Оказывает большее влияние на соотношение коэффициента компрессии и степени верности кодирования

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

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

Ст абилизация выходной битовой скорости Требуемая выходная биювая скорость кодера Основной параметр управления качеством видеокодирования

Проведены экспериментальные оценки зависимости качественных характеристик кодирования от скорости выходного потока кодера Для оценки зависимости качественных характеристик кодирования от скорости выходного потока использовались объективные оценки (пиковое соотношение сигнал/шум) и субъективные (5-бальная шкала оценки качества изображения и 5-бальная шкала оценки ухудшения изображения) Для Экспериментов был выбран набор видеопоследовательностей с разрешением 320x176 пикселов, частотой 25 кадров/сек. и длительностью от 30 сек до 2 мин. Скорость каждого исходного (некомпрессированного) битового потока составляет 33 Мбит'с. Усредненные по набору видеопоследовательностей оценки приведены в табл.4. Процесс стабилизации выходной битовой скорости потока проилзюстрирован на рис. 4.

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

Таблица 4 - Результаты тестирования разработанного видеокодека на _различных битовых скоростях

11редельная скорость биювого потока, Кбит/с Требуемый коэффициент компрессии, раз Фактическая средняя скорость битового потока (Кбиг/с) Фактический средний коэффициент комирессии раз Пиковое соотношение сигнал/шум, дБ Оценка ПО шкале качества Оценка по шкапе ухудшений

2000 16,5 985 33,51 31 69 4,8 4,9

1800 18,3 983 33,58 31 68 4,8 4,9

1600 20,6 972 33,96 31 59 4 7 4.8

1400 23,6 941 35,05 31 38 4,6 4,8

1200 27,5 884 37,32 30 89 4,3 4,3

1000 33,0 818 40,36 30 27 3,9 .3,8

800 41,3 688 47,98 28 88 3,5 3,6

600 55,0 552 59,82 26 75 3,2 3,1

400 82,5 377 87,48 24 79 2,6 2,4

200 165,0 171 193,42 21 86 1,5 1 3

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

Размер кадра

. а .....^яи&х.. 1...... , г: " ^^ШТГЛ

Пропущенный кадр Качество кодирования кадра Опорный кадр Разностный кадр

(более темный цвет соответствует более высокому качеству кодирования)

Рисунок 4 - Процесс стабилизации выходной битовой скорости компрессированного видеопотока

Наиболее распространенными методами видеокомпрессии в настоящее время являются стандарты ряда MPEG. Схемы MPEG-2 и, особенно, MPEG-4 обеспечивают высокую эффективность кодирования, но вследствие высокой алгоритмической сложности, ориентированы на аппаратную реализацию. В то же время основным направлением проводимых исследований является разработка высокопроизводительных алгоритмов и программных систем видеокомпрессии. Поэтому оценки производительности разработанного в работе подхода по сравнению со стандартными схемами видеокомпрессии выполнены с использованием кодека MPEG-1 как наиболее производительного из программных кодеков стандарта MPEG, обеспечивающего сходные показатели по эффективности кодирования с

разработанным методом компрессии. В табл.5 приводятся сравнительные данные но степени компрессии и быстродействию алгоритмов кодирования и декодирования для разработанной программной модели и профессиональным программным пакетом MPEG-1 (XingMPEG) (эксперименты проводились на ПК с процессором типа Pentium IV с таковой частотой 1,2 ГГц, оперативной памятью 256 Мб, под операционной системой Windows ХР).

Таблица 5 - Сравнительные характеристики разработанного _видеокодека и видеокодека XingMPEG

Видео-пос пеяоеатель-лость Кодек MPFG 1 Разработанный кодек

Скорость кодирования кадров/сек Скорость ВЫХОДНОГО потока (коэф компрессии) Пи«гоная скорость декодирования с выводом на экран кадров/сек Скорость кодирования кадров/сек Средняя скорость выходного потока (коэф компрессии) Пиковая скорость декодирования с выводом на экран кацров/сек Пиковая скорость декодирования бео et >вода на экран кадров/сек

160x120 10 кадровик, 4 6 Мбит/с 99,0 120 Кбиг/с (38,3 раз) 203,6 197,0 127 4 Кбит/с (36,1 раз) 620,0 970,0

320x176 25 кадров>сек 33 8 Мбит с 27,2 1 Мбит/с (33,8 раз) 99,3 66,7 1 Мбит/с (33,8 раз) 240,0 391,0

320x240 30 кадров/сек 54 3 Мбит/с 22,Я 1 Мбит/с (55,3 раз) 80,8 54,7 1,3 Мби г/с (43,7 раз) 185,0 310,0

560x352 25 кадров/сек 1)83 Мбит/с 5,8 2,5 Мбит/с (47,3 раз) 32,2 13,6 2,66 Мбит/с (44,4 раз) 70,2 103 6

Оценки производительности кодирования с использованием разработанных алгоритмов в среднем в 2 раза, а декодирования - в среднем в 2,3 раза превосходят программный кодек МРЕО-1 при примерно одинаковых показателях эффективности кодирования (соотношения коэффициента сжатия и качества кодирования).

На рис 5 представлен график зависимости процента пропущенных декодером приемной стороны кадров от загруженности сетевого канала связи между приемным и передающим модулями. Как видно из рисунка, уже при свободной полосе пропускания сетевого канала (1,5-0,6) Мбит/с для различных форматов изображения (разрешение, частота кадров/сек) гарантируется достаточно качественная доставка видеопотока При дальнейшем повышении загруженности канала связи соответственно для каждого формата число пропущенных кадров резко возрастает, что объясняется увеличением числа потерянных фрагментов компрессированных данных кадров, и уменьшением числа правильно и полностью собранных кадров.

Число пропущенных кедров

100%

2000 1800 1о00 1400 1J00 1000 800

-320*24 0

ЗОкадр/сек

-- 320*176

25кад(/сек

180x120

Юкаярюек

•Доступная полоса

прогтугt ания канала

вязи Кбит/с

Рисунок 5 - Зависимость числа пропущенных кадров от загруженности сетевого канала связи.

Субъективная оценка качества принимаемого видеосигнала приведена на рис 6. Как показали экспериментальные исследования, человеческий зри'ельный аппарат достаточно чувствителен к пропаданию даже нескольких кадров видеопотока, что отразилось на результатах субъективных оценок качества работы программной системы передачи видео по сети

оценка качества видеосигнале

"Доступьи? ■¡••-¿y ¿

~4'vr¡ /ска^кя канала

.000 1800 1600 »00 1200 1000 800 600 <00 /00 0 семи Кв«[ с

Рисунок 6 - Зависимость субъективных оценок качества видеопогока от загруженности сетевого канала связи

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

Для оценки перспектив применения разработанной системы передачи видеопоследовательностей по 1Р-сети для проведения сеансов многоточечной конференцсвязи был проведен ряд экспериментов, направленных на

исследование качества доставки видеосигнала в режимах передачи "один-ко-мносим'' и "многие-к-одному".

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

Результаты тестирования системы в режиме приема одной рабочей станцией видеопотоков от нескольких передающих модулей приведены в табл. 7. Максимальное число подключенных передающих модулей достигало 10, дальнейший росг их количества ограничивался только вычислительными возможностями рабочей станции - приемника (Intel Celeron 1000 МГц). При этом загрузка сетевого канала составляла в среднем 30 Мбит при разрешении принимаемых изображений от 160x120 до 320x240.

Таблица 7 - Максимальная частота кадров, обеспечиваемая приемным _модулем

Видеопоследовате 1ыюсть Число одновременно принимаемых видеопогоков

1 2 3 4 5 6 7 8 9 10

160x120 65 63 60 55 53 50 48 44 40 35

320x176 52 48 43 38 30 27 23 17 14 11

320x240 45 40 З"7 32 27 22 17 12 8 4

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

*

Рисунок 7 - Пример экрана приемного терминала при воспроизведении 6 видеопотоков

Рисунок 8 - Снимок интерфейса программы Windows Media Player версии 9.0 в момент воспроизведения видеопотока, компрессированного разработанным видеокодеком

Для проверки степени совместимости разработанного модуля видеокодирования с операционной системой и программными продуктами сторонних разработчиков был проведен ряд экспериментальных исследований с участием нескольких различных по сложности и функциональному назначению программных продуктов, как стандартных для операционной системы Windows (входят в комплект поставки ОС), так и разработанных различными фирмами-производителями (рис 8), а именно. Virtual Dub v.l .5.8. Windows Media Player v 6 4, Windows Media Player v.9.0, Microsoft Office XP Word, Microsoft Office XP Excel. Проведенное тестирование выявило полную совместимость разработанного в виде драйвера на основе предлагаемых алгоритмов видеокодирования программного модуля видеокомпрессии с операционной системой Microsoft Windows и перечисленными программными продуктами сторонних разработчиков.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

Разработан основывающийся на разработанных алгоритмах видеокодирования совместимый с ОС Microsoft Windows программный модуль видеокомпрессии для системы видеоконференцсвязи «Дельта-конференция».

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

Проведены экспериментальные исследования возможности использования разработанного совместимого с ОС Microsoft Windows программного модуля видеокомпрессии в разработанной системе мультимедийного общения (система видеоконференцсвязи «Дельта-конференция») и программных системах работы с видеоматериалом сторонних производителей.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

1 Погорелов К.В Алгоритмы межкадровой и внутрикадровой компрессии видеоданных на основе оптимизированных дельта-преобразований второго порядка. - Известия ТРТУ Специальный выпуск. Материалы L научно-технической конференции профессорско-преподавательского состава, аспирантов и со грудников ТРТУ. - Таганрог: Изд-во ТРТУ, 2004. № 8 (43) С.68-69.

2. Погорелов К.В. Видеокодек на основе оптимизированных дельта-преобразований второго порядка в формате драйвера для ОС Microsoft Windows. - Технологии Microsoft в теории и практике программирования: Труды Всероссийской конференции студентов, аспирантов и молодых ученых. Центральный регион. Москва. 17-18 февраля 2005г. - М.. Изд-во МГТУ им. Н.Э.Баумана, 2005. С.70

3. Погорелов К.В. Разработка алгоритма сжатия изображений на основе оптимизированных дельта-преобразований второго порядка и усеченного блочного кодирования - Тез докл. V Всероссийской научной конференции студентов и аспирантов «Течническая кибернетика, радиоэлектроника и системы управления» - Таганрог Изд-во ТР1У, 2000. с.125-126.

4 Погорелов К.В. Алгоритм коррекции ошибок кодирования сигналов с использованием дельта-преобразований - VII Международная научно-техническая конференция студентов и аспирантов "Радиоэлектроника, электротехника и энергетика": 1ез. докл. в 3-х т - М.: Изд-во МЭИ, 2001, т. 1, с.276.

5. Погорелов К В., Кравченко П.П., Хусаинов Н.Ш., Хаджинов А А. Система организации многоточечной видеоконференции для локальных и корпорашвныч IP-сетей. - Труды Международных научно-технических конференций "Интеллектуальные системы (IEEE AIS'03)" и "Интеллектуальные САПР (CAD-2003)". Научное издание в 3-х юмах. - М.. Изд-во Физматлит. 2003, т.2.,с.264-270.

6 Погорелов К.В., Кравченко П.П., Хусаинов Н.Ш. Программа компрессии видеоинформации с использованием алгоритмов оптимизированных дельта-преобразований второго порядка. - М.. Реестр программ для ЭВМ Свид. № 2004610864 от 08.04.2004г.

Личный вклад автора в публикациях, написанных в соавторстве, состоит в следующем: [5, 6] - разработка алгоритмов видеокодирования и программная реализация модуля компрессии видеоинформации в виде драйвера.

Соискатель

Погорелов К.В.

I

Заказ № 206_ Тираж 100 экз.

Издательство Таганрогского государственного радиотехнического университета

ГСП 17 А, Таганрог, 28, Некрасовский, 44

Типография Таганрогского государственного радиотехнического университета

ГСП 17А, Таганрог, 28, Энгельса, 1

»1142?

РНБ Русский фонд

2006-4 7576

4

ВВЕДЕНИЕ.

4 1. АНАЛИТИЧЕСКИЙ ОБЗОР ИЗВЕСТНЫХ ПОДХОДОВ И МЕТОДОВ

ВИДЕОКОМПРЕССИИ.

1.1. Анализ особенностей цифрового представления видеоинформации.

1.2. Обзор основных подходов к цифровой видеокомпрессии.

1.2.1. Методы внутрикадровой цифровой видеокомпрессии.

1.2.2. Методы межкадровой цифровой видеокомпрессии.

1.3. Использование алгоритмов внутрикадрового и межкадрового кодирования в [4 современных международных стандартах видеокомпрессии.

1.3.1. Стандарты MPEG.

1.3.2. Рекомендации Н.26х.

1.4. Методы оценки качества кодирования.

1.4.1. Объективные оценки качества кодирования.

1.4.2. Субъективные оценки качества кодирования.

1.5. Выводы.

2. РАЗРАБОТКА АЛГОРИТМОВ ВЫСОКОПРОИЗВОДИТЕЛЬНОГО

ВНУТРИКАДРОВОГО ВИДЕОКОДИРОВАНИЯ НА ОСНОВЕ АЛГОРИТМОВ ОПТИМИЗИРОВАННЫХ ДЕЛЬТА-ПРЕОБРАЗОВАНИЙ ВТОРОГО ПОРЯДКА

2.1. Анализ требований к алгоритмам внутрикадрового кодирования на основе дельта-преобразований.

2.2. Основные достоинства и недостатки известных алгоритмов дельтапреобразований

2.3. Постановка задачи дельта-преобразования второго порядка.

2.4. Базовые алгоритмы двоичного дельта-преобразования.

2.4.1. Оптимизированные дельта-преобразования второго порядка на основе вторых разностей.

2.4.2. Модифицированный алгоритм двоичного дельта-преобразования со сглаживанием.

2.5. Комбинированный алгоритм дельта-преобразований для видеокодирования

2.6. Разработка алгоритма внутрикадрового видеокодирования.

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

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

2.8.1. Преобразования цветовых пространств.

2.8.2. Локальное прореживание изображений.

2.8.3. Предварительная обработка изображений.

2.8.4. Статистическое кодирование результатов работы алгоритма внутрикадровой компрессии.

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

2.10. Выводы.

3. РАЗРАБОТКА АЛГОРИТМОВ ВЫСОКОПРОИЗВОДИТЕЛЬНОГО

МЕЖКАДРОВОГО ВИДЕОКОДИРОВАНИЯ.

3.1. Анализ требований к алгоритмам межкадрового кодирования.

3.2. Анализ особенностей разностных кадров.

3.3. Базовый алгоритм межкадрового кодирования изображений.

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

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

3.6. Разработка алгоритма быстрого выбора оптимальной шаблонной матрицы.

3.7. Дополнительные методики повышения степени компрессии межкадрового кодера.

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

3.9. Алгоритм адаптивного управления скоростью выходного потока

• видеокодера.

ЗЛО. Выводы.

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ

КОМПРЕССИИ ВИДЕОДАННЫХ.

4.1. Основные требования к программной модели разработанных алгоритмов видеокодирования.

4.2. Структурная схема кодера видеоданных.

4.3. Формат хранения/передачи закодированных данных.

4.4 Разработка программной модели системы передачи видеоинформации с компрессией в режиме реального времени по IP-сети.

4.5. Разработка совместимого с ОС Microsoft Windows программного модуля видеокодека для системы видеоконференцсвязи.

4.6. Выводы.

5. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТАЛЬНЫХ ИССЛЕДОВАНИЙ РАЗРАБОТАННОЙ \f ПРОГРАММНОЙ МОДЕЛИ ВИДЕОКОДЕКА.

5.1. Методика проведения экспериментальных исследований.

5.2. Оценка зависимости качественных характеристик внутрикадрового кодирования и степени компрессии опорных кадров от параметров алгоритма внутрикадрового кодирования.

5.2.1. Оценка зависимости качественных характеристик кодирования и степени компрессии от изменения веса кванта модуляции.

5.2.2. Оценка зависимости качественных характеристик кодирования и степени компрессии от порогового значения ошибки для введения отсчета ДИКМ

5.2.3. Оценка зависимости качественных характеристик кодирования и степени компрессии от порогового значения ошибки для локальной поддискретизации.

5.3. Оценка зависимости качественных характеристик видеокодирования и степени компрессии видеопоследовательностей от параметров алгоритма межкадрового кодирования.

5.4. Экспериментальные оценки быстродействия разработанной программной модели кодека видеопоследовательностей.

5.4.1. Экспериментальная оценка зависимости качественных характеристик

• кодирования от скорости выходного потока кодера.

5.4.2. Экспериментальная оценка зависимости быстродействия разработанной программной модели видеокодека от параметров изображения.

5.4.3. Оценка производительности программной модели на основе алгоритмов внутрикадрового и межкадрового видеокодирования с оптимизацией на основе технологии ММХ.

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

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

5.4.6. Оценка максимального количества одновременно воспроизводимых видеопотоков.

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

5.6. Выводы.

Актуальность

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

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

Критерии качества преобразованного и передаваемого видеоматериала в современных системах обработки и передачи видеоинформации достаточно высоки, и требуемое качество видеосигнала должно быть не хуже, чем при обычном телевещании. Однако, как правило, эти требования вступают в противоречие с требованиями приемлемой производительности алгоритма компрессии и стоимости арендуемого канала связи. На сегодняшний день, по существу, для достижения высокого качества видеосигнала необходим канал, пропускная способность которого, с учетом наличия большого числа пользователей в данном канале, обеспечивала бы в пересчете на одного пользователя ту же эквивалентную скорость передачи информации, которая предоставляется при передаче телевизионной картинки (=270 Мбит/с). Практически это означает, что при реальном трафике, совместно используемом большим числом клиентов, требуемая пропускная способность канала должна составлять единицы и десятки Гбит/с [1].

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

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

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

В качестве решения подобной многокритериальной задачи в данной работе рассматривается применение оптимизированных алгоритмов дельта-преобразования второго порядка и алгоритмов усеченного блочного кодирования. Алгоритмы оптимизированных дельта-преобразований второго порядка отличаются простотой реализации, широким динамическим диапазоном и высокой скоростью восстановления данных [2, 3, 4, 5]. Вопросы построения алгоритмов дельта-преобразования второго порядка освещены в работах Р. Стала [6], А.В. Шилейко, Г.Г. Меньшикова, de Jeager F. и многих других. Важной проблемой для применения известных алгоритмов дельта-преобразования второго порядка долгое время оставалась нестабильность (неустойчивость) преобразований, в результате эти алгоритмы оказывались мало пригодны для практического использования.

Алгоритмы дельта-преобразований второго порядка, характеризующиеся стабильностью и оптимизацией по быстродействию и точности, впервые были освещены в работах П.П. Кравченко [7, 8, 9, 10].

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

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

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

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

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

Объект исследования

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

Цель и задачи работы

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

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

1) Анализ существующих методов и алгоритмов компрессии видеоданных, выявление их достоинств и недостатков;

2) Анализ методов оценки качества кодирования видеоданных;

3) Разработка быстродействующего алгоритма внутрикадровой компрессии видеоданных на основе единого алгоритмического подхода с использованием алгоритмов оптимизированных дельта-преобразований второго порядка со сглаживанием;

4) Разработка быстродействующего алгоритма межкадровой компрессии видеоданных на основе алгоритма усеченного блочного кодирования;

5) Разработка алгоритма управления скоростью выходного битового потока видеокодека;

6) Разработка формата хранения и передачи видеоданных;

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

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

9) Разработка программного модуля видеокодирования для системы мультимедийного общения (система видеоконференцсвязи «дельта-конференция»);

10) Проведение экспериментальных исследований программной модели видеокодека.

Основные научные результаты

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

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

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

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

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

1) Быстродействующий алгоритм и программная реализация внутрикадровой компрессии видеоданных с использованием алгоритмов оптимизированных дельта-преобразований второго порядка, дельта-преобразований первого порядка и дифференциальной импульсно-кодовой модуляции;

2) Быстродействующий алгоритм и программная реализация межкадровой компрессии видеоданных на основе алгоритма усеченного блочного кодирования с использованием шаблонных матриц;

3) Алгоритм и программная реализация быстрого выбора оптимальной шаблонной матрицы для алгоритма межкадровой компрессии;

4) Алгоритм и программная реализация управления скоростью выходного битового потока видеокодера.

Практическая ценность

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

1) Быстродействующий комбинированный алгоритм внутрикадровой компрессии видеосигналов, объединяющий преимущества алгоритмов оптимизированных дельта-преобразований второго порядка со сглаживанием, алгоритмов дельта-преобразований первого порядка и алгоритмов дифференциального импульсно-кодового кодирования;

2) Быстродействующий алгоритм межкадровой компрессии ^ видеосигналов, построенный на принципах усеченного блочного кодирования с использованием шаблонных матриц;

3) Алгоритм быстрого выбора оптимальной шаблонной матрицы для алгоритма межкадрового видеокодирования;

4) Формат хранения выходного потока кодирующего устройства для хранения и передачи закодированных видеоданных;

V 5) Программный модуль для компрессии и декомпрессии видеоданных;

6) Динамическая библиотека, содержащая программные процедуры компрессии и декомпрессии видеоданных;

7) Оценки и рекомендации по выбору наилучших параметров для кодирования видеоданных;

8) Программная система мультимедиа общения — система многоточечной видеоконференцсвязи "Дельта-конференция" с функцией видеоконференции на основе разработанных алгоритмов компрессии.

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

Методы исследования

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

Апробация работы

Результаты работы докладывались и обсуждались на Международных, Всероссийских научно-технических конференциях, в том числе на:

- III Международной конференции "Телевидение: передача и обработка изображений", Санкт-Петербург, 2003;

- Международной научно-технической конференции "Интеллектуальные системы (IEEE AIS'03)"h "Интеллектуальные САПР (CAD-2003)", Москва, 2003;

- V Международной конференции "Digital Signal Processing and its Application", Москва, 2003;

- Международной научно-технической конференции "Informatics, Mathematical Modeling and Design, Владимир, 2004;

- Всероссийской конференции студентов, аспирантов и молодых ученых "Технологии Microsoft в теории и на практике", Москва, 2005.

Работа выполнялась в рамках х/д НИР:

- № г.р. 01.200.100690 - «Разработка принципов и положений видеокодирования на основе оптимизированных дельта-преобразований второго порядка»;

- № г.р. 01.200.11468 - «Разработка алгоритмов и программной модели кодека внутрикадрового кодирования видеоданных на основе оптимизированных дельта-преобразований второго порядка. Проведение испытаний разработанного алгоритма компрессии»;

- № г.р. 01.200.202147 - «Разработка алгоритмов межкадрового кодирования и адаптивного управления скоростью выходного потока кодера видеопоследовательностей»;

- № г.р. 01200216955 - «Программная реализация системы передачи видеоинформации с компрессией в режиме реального времени по IP-сети. Проведение экспериментальных исследований»;

- № г.р. 01200407218 - «Разработка программной системы конференцсвязи с поддержкой функций документ-конференции и аудиовидеоконференции для локальных IP-сетей».

Вышеперечисленные НИР выполнялись совместно с ОАО ВНИИ TP (г. Москва)

Результаты работы используются в учебном процессе в дисциплинах:

- «Цифровое управление, сжатие и параллельная обработка информации на основе алгоритмов оптимизированных дельта-преобразований»;

- «Теория кодирования информации».

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

Публикации

Результаты, полученные в работе, нашли отражение в 36 печатных работах, среди них 7 статей и 2 свидетельства Всероссийского бюро по патентам и товарным знакам:

- №2004610864 «Программа компрессии видеоинформации с использованием алгоритмов оптимизированных дельта-преобразований второго порядка»;

- №2004610863 «Программа многосторонней видеоконференцсвязи для корпоративных локальных IP-сетей «Дельта-конференция».

Структура работы

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

5.6. Выводы

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

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

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

4) Проведены экспериментальные исследования скоростных характеристик разработанной программной модели видеокодека и оценки влияния параметров кодируемых видеопоследовательностей на эффективность и скорость видеокодирования, подтвердившие высокие показатели быстродействия и минимальное время кодирования видеоданных различных типов, пространственных и временных разрешений;

5) Проведены экспериментальные исследования возможности применения разработанных алгоритмов и программных моделей видеокодека в системах с передачей видеоинформации в рамках локальных IP-сетей, подтвердившие высокие показатели эффективности и скорости видеокодирования и декодирования, минимальное время задержки обработки видеопотока, и высокие показатели надежности передачи видеоинформации в рамках локальных IP-сетей;

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

7) Проведенные экспериментальные исследования подтвердили возможность использования разработанного совместимого с ОС Microsoft Windows программного модуля видеокомпрессии в программной системе мультимедийного общения (система видеоконференцсвязи «Дельта-конференция») и в программных системах работы с видеоматериалом сторонних производителей.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Материалы диссертационной работы использованы при выполнении х/д НИР № г.р. 01.200.100690 - «Разработка принципов и положений видеокодирования на основе оптимизированных дельта-преобразований второго порядка», № г.р. 01.200.11468 - «Разработка алгоритмов и программной модели кодека внутрикадрового кодирования видеоданных на основе оптимизированных дельта-преобразований второго порядка. Проведение испытаний разработанного алгоритма компрессии», № г.р. 01.200.202147 - «Разработка алгоритмов межкадрового кодирования и адаптивного управления скоростью выходного потока кодера видеопоследовательностей», № г.р. 01200216955 - «Программная реализация системы передачи видеоинформации с компрессией в режиме реального времени по IP-сети. Проведение экспериментальных исследований», № г.р. 01200407218 - «Разработка программной системы конференцсвязи с поддержкой функций документ-конференции и аудиовидеоконференции для локальных IP-сетей» совместно с ОАО ВНИИ TP (г. Москва). Результаты работы используются в учебном процессе в дисциплинах «Цифровое управление, сжатие и параллельная обработка информации на основе алгоритмов оптимизированных дельта-преобразований» и «Теория ^ кодирования информации». Получены 2 свидетельства Всероссийского бюро по патентам и товарным знакам №2004610864 «Программа компрессии видеоинформации с использованием алгоритмов оптимизированных дельта-преобразований второго порядка» и №2004610863 «Программа многосторонней видеоконференцсвязи для корпоративных локальных IP-сетей «Дельта-конференция». $ Достоверность полученных в диссертации результатов подтверждается разработкой действующей программной библиотеки для компрессии и восстановления видеоданных, проведенными экспериментальными исследованиями, а так же действующей программной системой ВКС "Дельта-конференция".

1. Синепол B.C., Цикин И. А. "Системы компьютерной видеоконференцсвязи". Серия изданий "Связь и бизнес", М. 0 0 0 "Мобильные коммуникации", 1

2. Стил Р. Принципы дельта-модуляции: Пер. с англ. Под ред. В.В.Маркова. М.: Связь, 1

3. Дельта-модуляция. Кравченко П.П. Теория Основы и применение М.Д.Венедиктов, дельтаЮ.П.Женевский, В.В.Марков, Г.С.Эйдус. М Связь, 1976. теории оптимизированных преобразований второго порядка. Цифровое управление, сжатие и параллельная обработка информации. Таганрог: Изд-во ТРТУ, 1997.

4. Кравченко П.П. Высокопроизводительные алгоритмы дельтамодуляции, оптимизированной Электросвязь. 1989. 9.

5. Агиевич C.H., Батенков А.А. Глушанков Е.И. и др. Новые методы эффективного кодирования изображений для передачи по системам связи //Электросвязь. 1995. 8.

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

7. Кравченко П.П. Дельта-модуляция на основе высших разностей и глубокого прогноза// Электронное моделирование. 1984.

8. Кравченко П.П. О дельта-модуляции на основе вторых разностей и оптимизированного А.с. 1112552 СССР. переходного МКИ НОЗК процесса 13/

9. Электронное Дельта-модулятор моделирование. 1986. 2. /П.П.Кравченко. Опубл. 1984. Бюл.№ 33. по быстродействию и точности 186

10. Бутаков Е.А. и др. Обработка изображений на ЭВМ /Е.А.Бутаков, В.И.Островский, И.Л.Фадеев. М Радио и связь, 1

11. Новик Д.А. Эффективное кодирование. М. Л.: Энергия, 1965. Ziv J., Lempel А. Compression of Individual Sequences via Variable-Rate Coding //IEEE Trans. 1978. No.

12. Witten 1.Н., Neal R.M., Cleary J.G. Arithmetic Coding for Data Compression //Communications of the ACM. 1987. Vol.30, No.

13. Мастрюков Д. Алгоритмы сжатия информации //Монитор. 1993. №7-8, 1994.№1,№

14. Теория информации и ее приложения: Сборник переводов /Под ред. А.А.Харкевича.-М.: ГИФМЛ, 1

15. Величкин А.И. Теория дискретной передачи непрерывных сообщений. М., Советское радио, 1

16. Цифровое кодирование телевизионных изображений /И.И.Цуккерман, Б.М.Кац, Д.С.Лебедев и др.; под ред. И.И.Цуккермана. М.; Радио и связь, 1981.

17. Каляев А.А. Теория цифровых интегрирующих машин и структур. М.: Советское радио, 1970. 20. 21. 22. 23. ч

18. Харатишвили Н.Г. Дифференциальная импульсно-кодовая модуляция в системах связи. М.: Радио и связь, 1

19. Борзенко А.И. Методы сжатия данных //КомпьютерПресс. 1995. №

20. Харкевич А.А. Очерки общей теории связи. М.: ГИТТЛ, 1

21. Крутько П.Д. Синтез нелинейных законов управления дискретных систем /Под ред. В.М.Пономарева //Нелинейная оптимизация систем автоматического управления. М.: Машиностроение, 1

22. Карташев В.Г. Основы теории дискретных сигналов и цифровых фильтров: Учеб.пособие для вузов. М Высш.школа, 1982. 187

23. Меньшиков Г.Г. Двоичная аппроксимация: основы теории, применение к вопросам передачи сообщений. Л.: ЛИЭС, 1968, Мешковский К.А., Кириллов Н.Е. Кодирование в технике связи. М.: Связь, 1

24. Хусаинов Н.Ш. Метод сжатия графических изображений на основе алгоритмов дельта-преобразований Всероссийская научная второго порядка: Тез. докл. студентов и аспирантов конференция «Радиоэлектроника, микроэлектроника, системы связи и управления». Таганрог.: Изд-во ТРТУ, 1997. 28. 29.

25. Уинтц П. Кодирование изображения посредством преобразований //ТИИЭР.-1972.-№

26. Обработка изображения и цифровая фильтрация. Под ред. Т.Хуанга. М Мир, 1

27. Эндрюс Г. Применение вычислительных машин для обработки изображений. Пер. с англ. /Под ред. Б.Ф.Курьянова. М.: Энергия, 1977.

28. Nasiopoulos, Yeldin, Ward А High Performance Fixed-Length Compression Method Using the Karhunen-Loeve Transform //IEEE Trans, on Consumer Electronics. 1995. Vol.41, No.4. 32. 33.

29. Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука, 1989 Daubechies I. Orthonormal Basis of Compactly Supported Wavelets //Comm. Pure Applied Mathematics. 1998. Vol.

30. Mallat S. A Theory of Multiresolution Signal Decomposition: The Wavelet Representation //IEEE Trans. Pattern Analysis and machine Intelligence. 1989.-Vol.11.

31. Харатишвили Н.Г., Чхеидзе И.М., Степерман В.Г., Абзиандзе Н.Э. Эффективность пирамидального кодирования в условиях действия случайных ошибок //Электросвязь. 1997. 4.

32. Chan Y.T. Wavelet Basics. Kluwer Academic Publishers, Norwell, MA, 1

33. Roese J.A. Interframe Coding of Digital Images Using Transform and Hybrid Transform/Predictive Coding Techniquie. USCIPI Rep.700, SC, Los Angeles. 38. 39.

34. Яншин В.В. Анализ и обработка изображений: принципы и алгоритмы.-М.: Машиностроение, 1

35. Quweider М.К., Salari В. Gradient-Based Block Truncation Coding //Electronics Letters. 1995. Vol.31, No.

36. Kamel M., Sun СТ., Guan L. Image Compression by Variable Block Truncation Coding with Optimal Threshold //IEEE Trans, on Signal Processing. 1991. -Vol.39, No.4 41. 42. 43. 44.

37. Delp E.J., Michell O.R. The Use of Block Truncation Coding in DPCM Image Coding //IEEE Trans, on Signal Processing. 1991. Vol.39, No.4. Kuo C.-H., Chen C.-F. Progressive DPCM system with block truncation coding //Electronics letters. 1995. Vol.31, No.

38. Schufer R., Sikora T. Digital Video Coding Standards and Their Role in Video Communications Proceedings of the IEEE. 1995. Vol.83, No.

39. Синепол B.C., Цикин И.А. Системы компьютерной видеоконференцсвязи М.: Связь и бизнес, 1

40. Martins М., Moura F. Video Representation with Three-Dimensional Entities //IEEE Journal on Selected Areas in Comm. 1998, Vol. 16, No.l. 46. 47.

41. Пилипчук Прэтт Н.И., Яковлев "Методы В.П. Адаптивная импульсно-кодовая Сокращение модуляция.-М.:Радио и связь, 1986. У.К. передачи изображений. избыточности" М.: "Радио и связь", 1

42. Яншин В.В., Калинин Г.А. Обработка изображений на языке Си для IBM PC: Алгоритмы и программы. М.: Мир, 1994. 189

43. Dufaux F., Moscheni F. Motion estimation techniques for digital TV: Review and a new contribution //Proceedings of the IEEE. 1995, Vol. 83, No. 6.

44. Horn P., Schunck B. Determining optical flow //Artifical Intelligence. 1981.-Vol. 17.

45. Nagel H, Displacement vectors derived from second-order intensity variations in image sequences //Computer Graphics and Image Process. 1983.-Vol. 21.

46. Netravali A., Robbins J. Motion compensated television coding //Bell System Technologies Journal. 1979. Vol. 58, No.3

47. Koga T. Motion compensated interframe coding of video conferencing //Proceeding of National Telecommunications Conference. New Orleans, LA, 1981.

48. Musmann H., Pirsch P., Grallert H., Advances in picture coding //Proc. IEEE. 1985. Vol. 73.

49. Jain R. Jain A., Displacement measurement and its application in interframe image coding //IEEE Trans. Commun. 1981. Vol. 29. 57. OKoHHop П. Преобразование стандартов с компенсацией движения //Техника кино и телевидения. 1995. №4.

50. Зубарев Ю.Б., Дворкович В.П., Нечепаев В.В., Соколов А.Ю. Методы анализа и компенсации движения в динамических изображениях //Электросвязь. 1998. 11.

51. Pogorelov K.V., Krovchenko P.P., Khussainov N. Sh., Khadjinov A.A. Development of High-Performance Intraframe and Interframe Video Compression Techniques. Proceedings of 5-th International Conference 190

52. Погорелов K.B., Кравченко П.П., Хусаинов Н.Ш. Сборник 61. 62. трудов Научно-практической Разработка конференции алгоритмов внутрикадровой и межкадровой видеокомпрессии. "Информационная безопасность". Таганрог, ТРТУ, 2002г., с. 160-

53. Dufaux F. Multigrid block matching motion estimation for generic video coding. Institute of Tech., Lausannes, Switzerland, 1

54. Anandan P., A unified perspective on computational techniques for the measurement of visual motion //IEEE Proc. Int. Conf Computer Vision, London, UK.-1987.

55. Bierling M., Displacement estimation by hierarchical block matching //SPIE Proc. Visual Commun. and Image Process. 88, Cambridg, MA. 1988.-Vol. 1001.

56. Sullivan G. Baker R. Motion compensation for video compression using control grid interpolation //IEEE Proc. ICASSP91, Toronto, Canada. 1991.-Vol. 4. 65. 66. 67. 68. 69.

57. Netravali A., Lippman A. Digital Television: A Perspective //Proceedings of the IEEE. 1995. Vol.83, No.6. ISO/IEC 13

58. Information Technology Generic Coding of Moving Pictures and Associated Audio Information /Ed.l, JTC 1/SC 29, 1

59. Ярославский Л.П. Введение

60. Локшин Б.А. Цифровое вещание: от студии к телезрителю. М.: Компания Сайрус Системе, 2

61. Самойлов Ф.В. Методы сжатия цифровых видеосигналов Техника кино и телевидения. 1995. 6 Волкова Ю. Сущности MPEG //Сети. 2000. 9, Попов А. А. MPEG2 в телевидении //Новости техники и технологии, ТКТ. -1999. 7. 191

62. Ряхин А. Видеостандарт MPEG //625. 1996. №

63. Дворкович А., Дворкович В., Марков Д., Новинский Н., Соколов А. Испытательные f 75. таблицы для измерения качества цифрового и аналогового телевизионного вещания //625. 1999. №8. ISO/IEC 11

64. Information Technology Coding of Moving Pictures and Associated Audio for Digital Storage Media up to about 1,5 Mbit/s /Ed.l, JTC 1/SC29, 1993. 76.

65. Полунин A. Уплотнение видеосигнала //Сети. 2000.

66. Прэтт У. Цифровая обработка изображений в 2-х кн. М.: Радио и связь, 1987.

67. Попов А.А. Объективная оценка качества последовательности скомпрессированных изображений. Эвристически оптимизированная модель //Техника кино и телевидения 1999. 6.

68. Гласман К.Ф., Логунов А.Н., Перегудов А.Ф., Лячаков В.Н. Объективная оценка артефактов видеокомпрессии //Техника кино и телевидения 2000.- 2. 80.

69. Кривошеев М.И. Основы телевизионных измерений. М.: Связь, 1

70. Видеопотоки MPEG: предобработка и контроль качества Snell Wilcox //Broadcasting. 2001. 3.

71. Lubin J., Brill M., Crane R. Vision Model-Based Assessment of Distorion Magnitudes in Digital Video. NJ: David Sarnoff Research Center, 2000.

72. Wallace, Gregory K. The JPEG Still-Picture Compression Standard //Communications of the ACM. 1991. 34 (4). 192

73. Хусаинов Н.Ш. Использование алгоритмов дельта-преобразований второго порядка для кодирования графических изображений со сжатием: Тез. докл. IV Всероссийской научно-технической конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления». Таганрог, 1998.

74. Погорелов К.В., Кравченко П.П,, Хусаинов Н.Ш., Хаджинов А.А. Система децентрализованной многоточечной видеоконференцсвязи в 1Р-сетяхю "Новые информационные технологии. Разработка и аспекты применения". Труды VI Всероссийской научной конференции с международным участием. Научное издание. Таганрог. ООО "Антон", 2003. 48-53.

75. Кравченко П.П., Хусаинов Н.Ш. Сжатие графических изображений на основе алгоритмов оптимизированных дельта-преобразований второго порядка //Известия ТРТУ. 1998. 3.

76. Кравченко П.П., Хусаинов Н.Ш. Сжатие растровых изображений с потерями на основе алгоритма оптимизированных дельта- 193

77. Новаковский СВ. Цвет на экране телевизора. Основы телевизионной колориметрии М.:Радио и связь, 2

78. Климов А.Г. Форматы графических файлов. М.: Диалог, 1

79. Истомин Б.К., Коёкин А.И., Михайлов Б.А. Сжатие данных в цифровом телевидении //Электросвязь. 1995.

80. Птачек М. Цифровое телевидение. Теория и техника /Пер. с чешек, под ред. Л.С.Виленчика. М.: Радио и связь, 1

81. Стандарт MPEG-2: комментируют специалисты //Техника кино и телевидения, 1999.

82. Дворкович В.П. Нечепаев В.В. Оценка качества компенсации движения при использовании точных значений векторов движения. В сб. "Доклады 1-й Международной конференции DSPA-98". М.: МЦНТИ, 1998. 194

83. Архитектура, программирование, интерфейс. М.:Горячая линияТелеком, 2000.

84. Дворкович В.П., Нечепаев В.В. Компенсация движения использованием преобразования Фурье. В 102. 103. сб. "Доклады 1-й Международной конференции DSPA-98". М МЦНТИ, 1

85. Kunt М., Ikonomopoulos А., Kocher М. Second Generation Image Coding Techniques //Proc. of the IEEE. 1985. Vol. PROC-

86. Погорелов K.B., Хусаинов Н.Ш., Кульбацкий А.Ю. Цифровая компрессия аудиовизуальной информации на основе алгоритмов оптимизированных дельта-преобразований второго порядка. Известия ТРТУ. Спец. выпуск "Материалы XLVI научно-технической конференции". Таганрог: Изд-во ТРТУ, 2001. 1 (19), с. 63, 104.

87. Покровский Б. Расчет и измерение разборчивости речи. М.:Связь, 1

88. Погорелов К.В., Кравченко П.П., Хусаинов Н.Ш., Хаджинов А.А. Система организации многоточечной видеоконференции для локальных сетей с негарантированным качеством обслуживания. "Известия высших учебных заведений. Северо-Кавказский регион. Технические 2003г., с.18-21.

89. Погорелов К.В. Многоточечная видеоконференцсвязь в локальных сетях. "Новые информационные технологии. Разработка и аспекты применения". Труды VII Всероссийской научной конференции с международным участием. Научное издание Таганрог: "ПБОЮЛ В.А.Кравцов", 2004г. 36-38.

90. Погорелов К.В. Алгоритмы межкадровой и внутрикадровой компрессии видеоданных на основе оптимизированных дельтанауки". Специальный выпуск "Математическое моделирование и компьютерные технологии в науке и производстве". 195

91. Материалы L научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников ТРТУ. Таганрог: Изд-во ТРТУ, 2004. 8 (43). 68-

92. Погорелов К.В. Видеокодек на основе оптимизированных дельтапреобразований второго порядка в формате драйвера для ОС Microsoft Windows. Технологии Microsoft в теории и практике программирования: Труды Всероссийской конференции студентов, аспирантов и молодых ученых. Центральный регион. Москва. 17-18 fi 109. феврапя 2005г. М.: Изд-во МГТУ им. Н.Э.Баумана, 2005.

93. Погорелов К.В. Разработка алгоритма сжатия изображений на основе оптимизированных научной дельта-преобразований студентов и второго порядка и усеченного блочного кодирования. Тез. докл. V Всероссийской конференции аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» Таганрог: Изд-во ТРТУ, 2000. с. 125-126.

94. Погорелов К.В. Алгоритм коррекции ошибок кодирования сигналов с использованием дельта-преобразований. VII Международная научнотехническая конференция студентов и аспирантов "Радиоэлектроника, электротехника и энергетика": Тез. докл. в 3-х т. М.: Изд-во МЭИ, 2001,т.1,с.276. 196