автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмическое и программное обеспечение системы сжатия видеопоследовательностей, созданной в рамках стандарта H.265/HEVC

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

Шарабайко Максим Павлович

Алгоритмическое и программное обеспечение системы сжатия видеопоследовательностей, созданной в рамках стандарта Н.265/НЕУС

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

АВТОРЕФЕРАТ

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

кандидата технических наук

4 ДЕК 2014

005556284

Томск - 2014

005556284

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

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

заслуженный деятель науки РФ, Марков Николай Григорьевич

Официальные оппоненты

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

Протасов Константин Тихонович, доктор технических наук, старший научный сотрудник, федеральное государственное бюджетное учреждение науки Институт оптики атмосферы им. В.Е. Зуева Сибирского отделения Российской академии наук, лаборатория распространения оптических сигналов, старший научный сотрудник.

Ведущая организация

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

Защита состоится 25 декабря 2014 г. в 12.30 на заседании диссертационного совета Д 212.267.08, созданного на базе федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корп. 2, ауд. 102).

С диссертацией можно ознакомиться в Научной библиотеке и на официальном сайте федерального государственного автономного образовательного учреждения высшего образования «Национальный исследовательский Томский государственный университет» www.tsu.ni.

Автореферат разослан ноября 2014 г.

Материалы по защите диссертации размещены на официальном сайте ТГУ: http://www.tsu.ru/content/news/announcement_of_tbe_dissertations_in_th0_tsu.php

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Скворцов Алексей Владимирович

Общая характеристика работы

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

Основы теории сжатия цифровых видеоданных заложены в работах таких ученых как Н.Ахмед, K.P.Pao, Т. Бергер, К. Карунен, М.Барнсли и др. Весьма полное изложение методов сжатия цифровых видеоданных представлено в работах Д. Ватолина, Д. Сэломона, Р. Гонсалеса.

Можно считать, что широкое применение методов и алгоритмов сжатия видеопоследовательностей началось в 1984 г. с момента принятия международного стандарта Н.120. Принимаемые в дальнейшем стандарты позволяли достигать более высоких степеней сжатия. В современных телекоммуникационных системах сжатие цифровых видеопоследовательностей осуществляется, в основном, в рамках стандартов видеокодирования MPEG-2 и H.264/AVC, принятых в 199G г. и 20U3 г. соответственно. Произошедшее за последние десять лет повышение требований к качеству визуального восприятия видеоданных, сопряженное с увеличением объемов видеоинформации, делает необходимым достижение более высокой степени сжатия цифровых видеоданных. С этой целью в 2013 г. приняты новые стандарты вндеокоди-рования H.2G5/HEVC и Google VP9. Находится в разработке стандарт Xipli Daala.

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

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

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

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

Для достижения поставленной цели необходимо решить задачи.

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

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

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

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

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

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

1. Сформулирована и экспериментально подтверждена гипотеза о высокой корреляционной связи битовой длины закодированного сообщения на выходе адаптивного арифметического кодера стандарта Н.205/НЕУС и энтропии поступающих на его вход символов, вычисляемой по контекстным группам арифметического кодера. Это позволило разработать оригинальный способ вычисления меры степени сжатия остаточного сигнала по энтропии символов для быстрого по сравнению с известными способами принятия решений в кодирующей системе на основе стандарта Н.265/НЕУС.

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

3. Предложен способ выбора режима пространственного предсказания при кодировании блока видеокадра, основанный на формировании короткого списка режимов-кандидатов. В список включаются режим с наименьшей ошибкой предсказания, а также три режима, однозначно определяемые режимами предсказания двух соседних блоков. Экспериментально показано, что использование этого способа со средней вероятностью 86,9% обеспечивает значительно более быстрый выбор того же режима предсказания, чем при методе полного перебора всех вариантов.

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

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

(H.265/AVC, VP8, VP9 и т.д.) и перспективных алгоритмов сжатия видеопоследовательностей, в которых применяется вычислительно сложное арифметическое кодирование. Кроме того, применение разработанного способа при выборе инструментов сжатия цифровых видеоданных позволяет строить и развивать модели и алгоритмы параллельной обработки нескольких блоков видеокадра.

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

Практически значимыми являются разработанные быстрые алгоритмы сжатия видеопоследовательностей, а также созданное программное обеспечение системы сжатия, реализующее разработанные и базовые алгоритмы видеообработки стандарта H.265/HEVC. Значимой является программная реализация алгоритмов видеокодирования, использующая для ускорения вычислений SIMD команды процессора. Практически значимыми также являются результаты проведенных в работе сравнительных исследований характеристик алгоритмов видеообработки, положенных в основу стандартов видеокодирования H.265/HEVC, Google VP9 и Xiph Daala. Эти результаты могут быть использованы как при проектировании систем сжатия видеопоследовательностей на основе этих стандартов, так и при развитии алгоритмов видеообработки в следующем поколении стандартов видеокодирования.

Результаты работы внедрены в ЗАО «Элекард Девайсез» (г. Томск) и используются в составе коммерческих программных средств Elecard HEVC Codec SDK, Elecard Converter Studio и Elecard CodecWorks Encoder этой компании. Программные продукты Elecard HEVC Encoder и Elecard HEVC Decoder, включающие программные модули созданной системы сжатия, зарегистрированы в Федеральной службе по индивидуальной собственности (Роспатент).

Результаты диссертационной работы также были использованы в лаборатории обработки и трансляции мультимедийных данных института инно-ватики Томского государственного университета систем управления и радиоэлектроники при выполнении НИОКР от 19.11.12 № 97/12 по созданию системы потокового телевещания с высокой степенью сжатия.

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

1. Энтропия последовательности двоичных символов, получаемых в результате бинаризации квантованных спектральных отсчетов остаточного сигнала, оцениваемая с учетом принадлежности этих символов к определенной синтаксической группе, имеет высокую корреляционную связь с битовой длиной сообщения, представляющего остаточный сигнал в закодированном видеоиотоке и, как следствие, может использоваться в качестве меры степени сжатия остаточного сигнала в кодирующей системе на основе стандарта H.265/HEVC.

2. Новый алгоритм оценки эффективности использования различных инструментов кодирования блока видеоизображения, основанный на вычислении меры степени сжатия остаточного сигнала по энтропии символов и на оригинальной эмпирической оценке битового размера вспомогательной информации о пространственном предсказании кодируемого блока, позволяет исключить из процедуры выбора варианта кодирования этап сложного в вычислительном отношении арифметического кодирования, что приводит к сокращению вычислительных затрат при сжатии в среднем на 20% по отношению к базовой реализации алгоритма сжатия в рамках стандарта H.265/HEVC и обеспечивает возможность распараллеливания вычислений.

3. Разработанный алгоритм выбора варианта пространственного предсказания кодируемого блока видеокадра на основе метода спуска при поиске экстремума и предложенного способа формирования короткого списка режимов-кандидатов в рамках стандарта H.265/HEVC обеспечивает ускорение быстродействия базовой реализации алгоритма сжатия на 40% при среднем снижении степени сжатия на 1,9%.

4. Алгоритмическое и программное обеспечение созданной системы сжатия видеопоследовательностей с параллельной обработкой, энтропийной оценкой битового размера и выбором варианта кодирования блоков в видеокадре, обеспечивает в 3 раза более высокое быстродействие в сравнении с аналогичными системами в рамках стандарта H.265/HEVC, а также обеспечивает на 12,8% большую степень сжатия в сравнении с текущими промышленными системами сжатия на основе стандарта H.264/AVC.

Апробация результатов работы. Основные результаты диссертационной работы были представлены на следующих конференциях: VIII и IX International Forum on Strategic Technology IFOST (Томск, 2012, Читтагонг (Бангладеш), 2014): X .Международной IEEE конференция по управлению и связи SIBCON-2013 (Красноярск, 2013); X, XI и XII Международной научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск. 2012, 2013, 2014); XIX и XX Международная научно-практическая конференция студентов, аспирантов и молодых ученых «Современные техника и технологии» (Томск, 2013, 2014); X Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (Томск, 2013).

Публикации. Материалы диссертации опубликованы в 13 печатных работах, в том числе 5 статей в журналах, входящих в перечень ВАК РФ. Кроме того, получено 2 свидетельства о регистрации программ для ЭВМ.

Личный вклад. Основные теоретические и практические результаты получены лично автором. Постановка задач диссертационного исследования выполнена автором совместно с научным руководителем, д.т.н., профессором Н.Г. Марковым. Анализ результатов сравнительных исследований алгоритмов видеообработки стандартов H.265/HEVC и Google VP9 проведен совместно с Пономаревым О.Г. и Поздняковым A.A.

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и 120 библиографических источников. Основной текст занимает 144 с.

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

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

Проведенный анализ показал, что в настоящее время одним из путей повышения визуального качества видеопоследовательностей является переход от систем высокой четкости к системам ультравысокой четкости. Осуществление такого перехода в рамках имеющихся средств хранения и каналов передачи данных и при использовании существующих систем сжатия на основе стандартов MPEG-2 и AVC не представляется возможным. Необходима более высокая степень сжатия видеопоследовательностей. С целью повышения степени видеокомпрессии в 2013 г. приняты новые стандарты видеокодирования H.265/HEVC и Google VP9, а также находится в разработке стандарт Xiph Daala. Они имеют увеличенный набор программных инструментов видеокодирования, тем самым повышая вычислительную сложность алгоритмов сжатия видеопоследовательностей настолько, что сегодня невозможно

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

Во второй главе разрабатывается концепция построения современной системы сжатия видеопоследовательностей. Её основными положениями являются необходимость создания системы в рамках одного из международных стандартов видеокодирования и необходимость удовлетворения ряда требований к системе. Одним из таких требований выступает обеспечение более высокой степени сжатия в сравнении с существующими системами. Таким образом, первостепенной является задача выбора стандарта видеокодирования из числа перспективных стандартов нового поколения (H.265/HEVC, Google VP9 или Xiph Daala), который позволил бы обеспечить более высокую степень сжатия видеоданных в сравнении с существующими системами.

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

Для автоматизации процесса сравнения результатов исследования эффективности различных алгоритмов сжатия применяется метрика DD-Rate (англ. Bjontegaard delta Rate - изменение битовой скорости по Бъёнтегарду). Величина BD-Rate измеряется в процентах и характеризует среднее изменение битовой скорости (количества бит в секунду) па выходе кодирующей системы, получаемое при использовании тех или иных алгоритмов видеообработки, при сохранении уровня искажений, оцениваемых метрикой PSNR. Положительные значения BD-Rate означают рост битовой скорости и эквивалентны относительному снижению на ту же величину степени сжатия видеоданных. Кроме того, метрика BD-Rate позволяет соотносить получаемые результаты с результатами сторонних исследований. Для этих целей эксперименты по сжатию проводились с использованием тестового набора видеопоследовательностей международного комитета JCT-VC, применяемого в большинстве работ подобной тематики. Тестовый набор включает 24 цветные видеопоследовательности различной четкости, битовой глубины и содержания,

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

Результаты проведенных исследований показали, что алгоритмы видеокомпрессии стандарта Н.265/НЕУС позволяют на 40% снизить битовый размер кодируемых видеопоследовательностей в сравнении с получаемым размером сжатия при использовании алгоритмов индустриального стандарта Н.264/АУС. В то же время, стандарт УР9 позволяет лишь на 20% сократить битовый размер сжатия видеопоследовательности, а при использовании алгоритмов видеообработки стандарта Оаа1а не удается достичь степени сжатия, достигаемой при использовании инструментов стандарта Н.264/АУС.

Таким образом, анализ полученных результатов исследований позволяет считать, что в качестве базовых следует выбрать алгоритмы видеокомпрессии стандарта Н.265/НЕУС. При этом базовая реализация его кодера НМ обладает крайне низким быстродействием, поскольку использует полный набор инструментов кодирования стандарта Н.265/НЕУС, а выбор инструментов сжатия осуществляет на основе почти полного перебора всех вариантов кодирования. Одним из способов повышения быстродействия можно считать отказ от некоторых инструментов видеокомпрессии. Однако проведенные в работе исследования показали, что отказ от ряда инструментов видеообработки в стандарте существенно (на 12-20%) снижает эффективность алгоритма сжатия, поэтому такой способ увеличения быстродействия не представляет практического интереса.

Все это еще раз указывает на актуальность задачи разработки эффективных алгоритмов сжатия видеопоследовательностей с учетом специфики инструментария стандарта Н.265/НЕУС. Поскольку межкадровое предсказание в стандарте Н.265/НЕУС не претерпело принципиальных изменений, к нему применимы алгоритмы поиска и компенсации движения, разработанные для блочных гибридных кодеров, в том числе в рамках стандарта Н.264/АУС. Напротив, сжатие с использованием пространственного предсказания существенно усложнилось за счет увеличения числа режимов предсказания с 10 до 35 и за счет увеличения максимального размера блока, и числа возможных подблоков в его разбиении. Таким образом, дальнейшие исследования решено сосредоточить на решении задачи эффективного сжатия с использованием пространственного предсказания. В работе сформулированы подходы к решению этой задачи и намечен ряд подзадач, подлежащих дальнейшему исследованию.

В третьей главе описываются исследования, посвященные созданию быстродействующего алгоритма оценки эффективности различных инструментов кодирования блока в видеокадре в рамках стандарта Н.265/НЕУС. Быстродействие создаваемого алгоритма также определяется принципиальной возможностью параллельной обработки нескольких блоков видеокадра. Оценка эффективности вариантов кодирования блока видеокадра в

и

подобного рода алгоритмах осуществляется путем нахождения минимума ЛО-функции Лагранжа:

Jrd = D + А Я, (1)

где Л = const - множитель Лагранжа, R - битовый размер кодируемой информации о блоке, D - степень внесенных при сжатии искажений в представление блока видеокадра. Эффективность применения /Ш-функции в качестве критерия выбора варианта кодирования блока видеокадра обоснована в ряде фундаментальных работ Клода Шеннона и Тоби Бергера.

Рис. 1. Схема вычисления значения R£>-функции Лагранжа

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

В стандарте Н.265/НЕУС используется адаптивный арифметический кодер БВАС, разделяющий поступающие па вход символы по синтаксическим группам. Значение и вероятность появления определенного символа при кодировании отдельной синтаксической группы определяется состоянием соответствующей этой группе контекстной модели. При этом каждый кодируемый символ изменяет состояние определенной контекстной модели и вероятностный интервал кодирования. Таким образом, для вычисления значения Д при оценке /Ш-стоимости варианта кодирования (п + 1)-го блока необходим арифметический кодер с состоянием, сформированным в результате кодирования всех п предыдущих блоков, что делает невозможной параллельную обработку нескольких блоков видеокадра.

Из теории информации известно, что среднее число бит, получаемое в результате арифметического кодирования, достаточно близко к энтропии Н(Х)

исходного сообщения:

г=0

где p(xi) - вероятность появления значения Xi = г случайной величины X в сообщении. Однако в работе показано, что энтропия символов на входе арифметического кодера SBAC не соответствует получаемому коэффициенту сжатия этих символов. По результатам проведенного анализа предлагается способ вычисления оценки R реального числа бит R, получаемого в результате арифметического кодирования остаточного сигнала блока видеокадра, основанный на вычислении энтропии символов кодируемого сообщения для каждой из 7 выделяемых при кодировании синтаксических групп в отдельности. Исследования показали, что такая оценка R имеет высокую корреляцию с реальным значением R (коэффициент корреляции Пирсона равен 0,999). Высокая степень корреляции значений оценки R(B) с истинными значениями R(B) позволяет с высокой точностью аппроксимировать диаграмму рассеяния линейной зависимостью R = а - R + b (рис. 2). Параметры а и b аппроксимирующей прямой при этом определяют величину смещения оценки. Обработка тестовых последовательностей из набора JCT-VC показала, что в среднем значение параметра b « 1,157, а величина а ~ 1,071. Отличие а от 1 приводит к смещению оценки R(B), что эквивалентно изменению значения параметра Л в (1). Для того, чтобы скомпенсировать смещение, нами был введен корректирующий фактор к = 1/а « 0,93.

а б

Рис. 2. Диаграммы рассеяния для оценки Я и реального значения Я: а - для видеопоследовательности BasketballDrill; б - для видеопоследовательности PeopleOnStreet.

Для исключения этапа арифметического кодирования из процесса вычисления оценки R необходимо также оценивать размер данных о выполняемом пространственном предсказании блока. Исследования показали, что для этого необходимо классифицировать режим пространственного предсказания по тому, входит он 13 число наиболее вероятных МРМ (сокр. от англ. Most

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

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

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

Размер блока 4x4 8x8 16x16 32x32

Режим из числа МРМ 2 3 2 2

Режим не из числа МРМ 7 7 6 6

НАЧАЛО Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4. Шаг 5.

Шаг 6. Шаг 7. Шаг 8. КОНЕЦ.

Применение оценки Ё. битового размера R при выборе варианта кодирования блока видеокадра па основе /Ш-функции Лагранжа в базовой программной реализации кодера в рамках стандарта Н.265/НЕУС позволяет исключить этап арифметического кодирования, что приводит к увеличению быстродействия алгоритма сжатия в целом на 15-25%, а. алгоритма выбора варианта

ВВЕСТИ: трт - индикатор режима предсказания,

size - размер блока предсказания,

В - кодируемые данные

Задать начальное значение оценки R = S,

где S определяется по Таблице 1.

Разделить данные В на семь контекстных групп

Вп, п = [0; 7]. Положить г = 0.

Определить число нулей а и число единиц Ь в сообщении В*. Определить энтропию сообщения контекстной группы:

ВД) = • 1°Э2(йь1-• (¿5). Обновить оценку R = R + 0,93 • (а + Ъ) - Н(В{). Увеличить г = i + 1. Если г ^ 7, перейти на шаг 4. ВЫВЕСТИ: Значение R.

кодирования блока - на 20-40%. Кроме того, становится возможной параллельная обработка блоков, позволяющая в разы повысить быстродействие алгоритма сжатия. Вносимая такой оценкой ошибка выбора варианта кодирования блока приводит к увеличению на 2-5% размера кодируемых видеопоследовательностей, при этом общая степень сжатия все еще выше, чем при использовании инструментов стандарта Н.264/АУС.

Четвертая глава посвящена исследованию возможности дальнейшего ускорения алгоритма сжатия за счет снижения числа оцениваемых вариантов пространственного предсказания при кодирования блока видеокадра. В базовой реализации в рамках стандарта Н.265/НЕУС алгоритм выбора варианта пространственного предсказания блока разделяется на два этапа. На первом этапе вычисляется ошибка Е(т) предсказания всех 35 доступных режимов т и формируется сокращенный список режимов с наименьшими значениями ошибки. В список также включаются режимы предсказания двух соседних блоков. На втором этапе из числа режимов-кандидатов выбирается режим с наименьшей /Ш-стоимостью, используемый для последующего сжатия блока видеокадра. Несмотря на существенное сокращение вычислений /Ш-стоимости вариантов кодирования блока в сравнении с методом полного перебора, быстродействие такого алгоритма выбора режима пространственного предсказания все еще недостаточно высокое.

В работе исследуется влияние большего сокращения списка режимов-кандидатов на эффективность базового алгоритма сжатия видеопоследовательностей стандарта Н.265/НЕУС. В результате предлагается способ формирования списка режимов-кандидатов из одного режима с наименьшей ошибкой предсказания и трех режимов, однозначно определяемых режимами предсказания соседних блоков, что приводит к увеличению битового размера кодируемых тестовых видеопоследовательностей в среднем на 1,65% в сравнении с базовым способом. Предлагаемый способ также позволяет ограничить задачу первого этапа, алгоритма выбора режима пространственного предсказания нахождением одного режима с наименьшей ошибкой предсказания.

Анализ алгоритмов пространственного предсказания блока в стандарте Н.265/НЕУС показывает наличие корреляции значений ошибок предсказания соседних угловых режимов. При этом удаление от углового режима с минимальной ошибкой предсказания Е(т) ведет к возрастанию значения этой ошибки. Как следствие, поиск минимума функции Е(т) нами предложено осуществлять на основе метода спуска с учетом особенностей режимов пространственного предсказания стандарта Н.2С5/НЕУС.

На основе проведенных исследований и предложенного способа формирования списка режимов-кандидатов создан алгоритм выбора варианта пространственного предсказания блока видеокадра в рамках стандарта Н.265/НЕУС. Алгоритм позволяет в 2,3 раза сократить число вычислений функции Е(т). Общее ускорение базовой программной реализации кодера в

рамках стандарта H.265/HEVC составляет 20-40%, при этом на тестовом наборе видеопоследовательностей комитета JCT-VC среднее снижение степени сжатия относительно исходного алгоритма составляет всего 1,9%.

НАЧАЛО.

Шаг 1. ВВЕСТИ: Е(т) - функция оценки ошибки режима

предсказания т € М, М = {тп\т G N, 2 ^ т ^ 34}; А С М - режимы предсказания из числа МРМ;

Шаг 2. Найти среди режимов

Mi = {mi|mi = 4 -п + 2, п € Z, п = [0;8]> такой режим т\, что т\ : Е(т\) = min Е{т{).

miZMi

Шаг 3. Найти среди режимов

М2 = {т2\т2 = ml+2-n, п 6 Z, п = [-1; 1], 2 ^ т2 ^ 34} такой режим т2, что т2 : Е(т2) = min Е(т2).

Шаг 4. Найти среди режимов

М3 = {m3|m3 = т2 + п, п G Z, п = [-1; 1], 2 ^ т3 < 34} такой режим т3, что ГП3 : E(ml) = min Е(т3).

т3€М3

Шаг 5. Найти среди режимов М4 = {0, 1, ТО3} такой режим ml, что ml : Е{тц) = min Е(т4).

Шаг 6 . Сформировать множество S = ml U А режимов предсказания s G S.

Шаг 7. Найти т* : ^ди(ш') = minJ/j£>(m).

meS

Шаг 8. ВЫВЕСТИ: Значение т* и Jrd("J*)-

КОНЕЦ.

В пятой главе описывается программное обеспечение (ПО) системы сжатия сжатия видеопоследовательностей, разработанной в рамках стандарта H.265/HEVC. Приводятся результаты исследования эффективности созданной системы. Схема структуры ПО созданной системы сжатия видеопоследовательностей приведена, на рис. 3.

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

1G

в сравнении с базовой программной реализацией кодера, а также в 3 раза более высоким быстродействием в сравнении с аналогичными системами в рамках стандарта Н.265/НЕУС. Созданная система сжатия обеспечивает на 12,9% меньший размер пространственного сжатия видеопоследовательностей в сравнении с системами сжатия на основе стандарта Н.264/АУС.

I

Рис. 3. Схема структуры ПО системы сжатия видеопоследовательностей

а б

Рис. 4. Сравнение эффективности сжатия с использованием пространственного предсказания базовых программных реализаций алгоритмов сжатия в рамках стандартов вндеоко-дирования H.2G5/HEVC (кодер НМ) и H.2G4/AVC (кодер JM): а - для последовательности BasketballDrill; б — для последовательности Traffic

Характерные показатели степени видеокомпрессии разработанной системы и базовых кодеров стандартов H.265/HEVC и H.264/AVC приведены на рис. 4. Разработанная система применялась при решении задач автономного кодирования видеопоследовательностей (рис. 4, «Авторский 1»), для которых приоритет уделяется достигаемой степени сжатия. В этом режиме созданная система обладает большей степенью сжатия в сравнении с системами в рамках стандарта H.264/AVC. Для решения задач потокового кодирования требуется обработка кадров кодируемой видеопоследовательности в режиме реального времени. Требуемая производительность достигается созданной системой сжатия в скоростном режиме работы (рис. 4, «Авторский 2»). В этом

режиме степень сжатия созданной системой ниже, чем у базового кодера ЛМ в рамках стандарта Н.264/АУС.

Основные научные и практические результаты работы

1. Проведен анализ тенденций развития систем сжатия видеопоследовательностей, рассмотрены основные алгоритмические средства сжатия, показавший направленность развития систем хранения и передачи видеоданных в сторону систем ультравысокого разрешения. Для эффективного сжатия видеопоследовательностей такого разрешения необходимо применение новых алгоритмов сжатия, созданных в рамках современных стандартов видеокодирования Н.265/НЕУС, УР9 и Баа!а.

2. Проведено исследование предельной степени сжатия, достигаемой применением средств видеообработки, заложенных в стандартах видеокодирования Н.265/НЕУС, УР9 и Баа1а, показавшее преимущества алгоритмов стандарта Н.265/НЕУС, позволяющих достичь наиболее эффективного сжатия видеопоследовательностей.

3. Разработаны концептуальные основы построения системы сжатия видеопоследовательностей, основанной на стандарте Н.265/НЕУС.

4. Предложен способ оценки битового размера кодируемых данных при выборе варианта кодирования блока видеокадра для стандарта Н.265/НЕУС на основе оценки энтропии символов, поступающих на вход синтаксического арифметического кодера Б В АС стандарта Н.265/НЕУС, отличающийся от известных устранением необходимости восстановления состояния БВАС; разработан алгоритм оценки битового размера данных о кодировании блока видеокадра при использовании пространственного предсказания в рамках стандарта Н.265/НЕУС, отличающийся от известных исключением вычислительно сложного этапа арифметического кодирования из процесса оценки;

5. Предложен способ перебора режимов пространственного предсказания блока видеокадра в рамках стандарта Н.205/НЕУС, отличающийся от известных использованием корреляции значений ошибок предсказания соседних угловых режимов; разработан алгоритм выбора режима пространственного предсказания при кодировании блока видеокадра в рамках стандарта Н.265/НЕУС, отличающийся от известных алгоритмов необходимостью оценки только одного режима с наименьшей ошибкой предсказания и трех наиболее вероятных режимов.

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

Список публикаций по теме диссертации

Публикации в изданиях, включенных в базу данных Scopus:

1. Sharabayko М.Р. Intra Compression Efficiency in VP9 and HEVC / Sharabayko M.P., Ponomarev O.G., Chernyak R.I. // Applied Mathematical Sciences. - 2013. - Vol. 7, no. 137. - P. 6803-6824. -0,64/0,20 п.л.

2. Sharabayko M.P. Iterative intra prediction search for H.265/HEVC / Sharabayko M.P., Markov N.G. // in Proc. of the XXth IEEE International Siberian Conference on Control and Communications (SIBCON). -Krasnoyarsk, Russia, 12-13 Sept. 2013. - P. 1-4. - 0,48/0,24 п.л.

3. Sharabayko M.P. Fractal Compression of Grayscale and Color Images: Tools and Results / Sharabayko M.P., Markov N.G. // in Proc. of the 7th IEEE International Forum on Strategic Technology (IFOST). - Tomsk, Russia, 17-21 Sept. 2012. - Vol. 1. - P. 571-575. - 0,42/0,21 п.л.

Статьи в журналах, включенных в Перечень рецензируемых научных изданий, рекомендованных Высшей аттестационной комиссией при Министерстве образования и науки Российской Федерации для опубликования основных научных результатов диссертаций:

4. Шарабайко М.П. Эффективность режимов внутреннего предсказания блоков в современных стандартах сжатия видео / Шарабайко М.П., Марков Н.Г. /7 Известия ТПУ. - 2013. - Т. 322, № 5. - С. 175-181. -0,32/0,20 п.л.

5. Шарабайко М.П. Обзор нового стандарта сжатия цифрового видео H.265/HEVC / Черняк Р.И., Шарабайко М.П., Поздняков А.А. // Открытое и дистанционное образование. - 2013. - № 2. - С. 5-9. -0,54/0,11 п.л.

6. Шарабайко М.П. Анализ эффективности методов и алгоритмов видеокомпрессии стандарта H.265/HEVC / Пономарев О.Г., Шарабайко М.П., Поздняков А.А. // Электросвязь. - 2013. - № 3. - С. 29-33. -0,57/0,19 п.л.

7. Шарабайко М.П. Эффективность адаптивной нелинейной постфильтрации в системе кодирования цифровых видеоданных стандарта HEVC / Пономарев О.Г., Шарабайко М.П. // Доклады ТУСУРа. 2013.-№ 3.

- С. 93-99. - 0,45/0,23 п.л.

8. Шарабайко М.П. Сжатие цветных изображений с помощью фракталов / Шарабайко М.П.. Марков Н.Г. // Информационные технологии.

- 2013. - № 1. - С. 37-40. - 0.33/0,16 п.л.

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

9. Sharabayko М.Р. Research on H.2G5/HEVC Intra Prediction Modes Selection Frequences // «Современные техника и технологии»: Сборник трудов XX Международной научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ, 14-18 апреля 2014. - Т. 2. - С. 315-316. - 0,14 п.л.

10. Sharabayko М.Р. Next Generation Video Codecs: HEVC, VP9 and Daala // «Молодежь и современные информационные технологии»: Сборник трудов XI Международной научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ. - 2013. -С. 35-37. - 0,17 п.л.

11. Шарабайко М.П. Ускорение одномерной интерполяции пикселей при временном предсказании в стандарте H.265/HEVC // Технологии Microsoft в теории и практике программирования»: Сборник трудов X Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных. - Томск: Изд-во ТПУ, 19-20 марта 2013. — С. 51-53. - 0,14 п.л.

12. Шарабайко М.П. Исследование эффективности устранения временной избыточности при однонаправленном предсказании в стандарте H.265/HEVC // «Современные техника и технологии»: Сборник трудов XIX Международной научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ, 15-19 апреля 2013. - Т. 2. - С. 397-398. - 0,21 п.л.

13. Шарабайко М.П. Сжатие опорных видео кадров в стандарте H.265/HEVC // «Молодежь и современные информационные технологии»: Сборник трудов X Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ, 13-16 ноября 2012. - С. 40-41. - 0,16 п.л.

Свидетельства о регистрации программ для ЭВМ:

14. Шарабайко М.П. Программа для ЭВМ «Elecard HEVC Video Encoder» / Поздняков A.A., Пономарев О.Г., Шарабайко М.П. ; заявитель и правообладатель ЗАО «Элскард наноДевайсез» (RU), ЗАО «Элс-кард Девайссз» (RU). // РОСПАТЕНТ. Свидетельство №2014613489 от 27.03.2014.

15. Шарабайко М.П. Программа для ЭВМ «Elecard HEVC Video Decoder» / Поздняков A.A., Шарабайко М.П., Мезенцев A.A., Черняк Р.И.; заявитель и правообладатель ЗАО «Элекард наноДсвайссз» (RU), ЗАО «Элскард Девайссз» (RU). ,7 РОСПАТЕНТ. Свидетельство №2014618195 от 12.08.2014.

Научное издание

Шарабайко Максим Павлович

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук на тему: Алгоритмическое и программное обеспечение системы сжатия видеопоследовательностей, созданной в рамках стандарта Н.265/НЕУС

Подписано в печать 23.10.2014 г. Формат А4/2 Тираж 100 экз. Заказ №14699.

ООО «Издательство «Иван Федоров» 034020, г. Томск, ул. Р. Люксембург, 115, стр. 1