Разработка и исследование алгоритмов устранения визуальной избыточности на основе кодирующих преобразований тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Доан Бан Тиен

• Доан Бан Тиен
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Доан Бан Тиен

Реферат

Synopsis

Введение

1 Аналитический обзор современных алгоритмов и мотивация

1.1 Основные принципы стандартов сжатия видеопоследовательности

1.2 Современные стандарты сжатия видеопоследовательностей

1.3 Обзор стандарта H.265 / HEVC

1.4 Постановка задачи исследования

1.5 Выводы по главе

2 Методы снижения сложности за счет улучшения внутрикадрового предсказания

2.1 Внутрикадровое кодирование в HEVC

2.2 Разработка алгоритмов улучшения процесса внутрикадрового предсказания

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

2.2.2 Улучшение процесса предсказания путем раннего определения глубины CU

2.2.3 Адаптивный выбор режима предсказания на

основе текстурного разделения

2.3 Результаты эксперимента

2.4 Выводы по главе

3 Методы снижения сложности путем оптимизации межкадрового предсказания

3.1 Межкадровое кодирование в HEVC

3.2 Гибридный алгоритм для быстрой оценки движения в

ЫЕУС

3.3 Исследование и разработка быстрых алгоритмов оценки движения

3.4 Выводы по главе

4 Оптимизация кодирующего преобразования в ЫЕУС

4.1 Базовое преобразование в ЫЕУС

4.2 Анализ сложности базового преобразования в ЫЕУС

4.3 Уменьшение вычислительной сложности путем аппроксимации элементов базового преобразования

4.4 Гибридное преобразование для ЫЕУС

4.5 Выводы по главе

5 Экспертное визуальное сравнение результатов предложенных алгоритмов с оригинальным программным обеспечением ЫМ-16

5.1 Визуальные наблюдения некоторых тестовых последовательностей

5.2 Выводы по главе

Заключение

Список иллюстраций

Список таблиц

Литература

Краткие обозначения

Приложение 1 - Свойства платформы для эксперимента

Приложение 2 - Тестовые видеопоследовательности

Приложение 3 - Выходной файл журнала

Приложение 4 - Акты о внедрении

Приложение 5 - Тексты публикаций

Реферат

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

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

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

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

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

Интерес к проблеме сжатия видео возник примерно в 80-х годах 20 века. Было разработано и использовано много стандартов сжатия видео, таких как M-JPEG, MPEG-1, MPEG-2, MPEG-4, H.261, H.262, H.263, H.264 / AVC, H.265 / HEVC и другие. Среди них H.264 / AVC (Advanced Video Coding), который был разработан в мае 2003 года в результате сотрудничества между экспертной группой по кодированию видео (Video Coding Experts Group - VCEG) и экспертной группой по движущимся изображениям (Moving Picture Experts Group - MPEG), нацелен в основном на мобильную связь. Именно благодаря ему системы передачи мультимедиа контента, системы безопасности и персональные устройства добились впечатляющих успехов в развитии. Его можно считать наиболее успешным стандартом сжатия. Безусловно, H.264 является наиболее часто используемым форматом для записи, сжатия и распространения видео контента и по-прежнему занимает самую большую долю рынка.

Хотя H.264 довольно хорошо справляется со сжатием видео, он достиг своего предела в модернизации и развитии. Растущий спрос на высокое и сверхвысокое разрешение видео контента, в условиях ограничений по объемам памяти, пропускной способности канала, привел к срочной разработке нового стандарта сжатия видео с улучшенными характеристиками и поддержкой более высокого разрешения для замены H.264. В результате в 2013 году появился стандарт высокоэффективного кодирования видеоизображений HEVC (High Efficiency Video Coding). Этот стандарт также известен как H.265 или MPEG-H, часть 2.

За счет совершенствования существующих алгоритмов H.264 / AVC с добавлением новых технологий, HEVC обеспечивает примерно удвоенную степень сжатия при сохранении того же качества сжатого видео по сравнению с его предшественником. Этот новый стандарт сжатия всего через несколько лет он стал вторым по популярности форматом кодирования видео, и в его структуре есть возможности для дальнейшего развития. Однако эта эффективность достигается повышением

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

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

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

Степень разработанности темы. Наибольший вклад в развитие методов и теории сжатия видеоданных, в частности стандарта H.265 / HEVC внесли Дж. Ом, Г. Салливана, Ф. Боссен, Д. Флинн, В. Зи, М. Будагави, М. Вена, K.P. Рао, Я. Ричардсон, Р. Гонсалес, Д. Ватолин, Ш. Фахми и др.

Объектом исследования в данной диссертационной работе являются видеокодеки современных стандартов.

Предмет исследования. Методы и алгоритмы обработки видеоданных в современных стандартах компрессии.

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

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

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

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

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

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

5. Экспериментальное подтверждение эффективности предложенных методов и алгоритмов кодирования в предложенной модификации HEVC.

Методы исследования. Основные результаты были получены с помощью методов теории информации, теории цифровой обработки сигналов, теории вероятности, методов математического анализа. Для создания и отладки программы обеспечения исследования и разработок использованы эталонное программное обеспечение HEVC версии 16.20 (HEVC Test Model HM-16.20), MATLAB_R2017a, язык программирования C++, среда разработки Microsoft Visual Studio.

Научная новизна

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

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

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

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

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

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

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

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

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

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

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

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

Соответствие паспорту специальности. Диссертационная работа соответствует паспорту научной специальности ВАК РФ 05.13.11 -«Математическое обеспечение вычислительных машин, комплексов и компьютерных сетей» по п. 7 «Человеко-машинные интерфейсы; модели, методы, алгоритмы и программные средства машинной графики, визуализации, обработки изображений, систем виртуальной реальности, мультимедийного общения».

Апробация результатов работы. Основные результаты работы докладывались на различных конференциях, в числе которых:

- 14-я Международная конференция «Телевидение: Передача и обработка изображений» (2017 г., Университет ЛЭТИ).

- 7-я Международная конференция по анализу изображений, социальных сетей и текстов (АИСТ 2018) (2018 г., Москва).

- XI Международная научно-практическая конференция «Программная инженерия и компьютерная техника» (Майоровские чтения) (2019 г., Санкт-Петербург).

- 30-я Международная конференция по компьютерной графике и машинному зрению (Графикон-2020) (2020 г., Санкт-Петербург).

- VII Всероссийский Конгресс молодых ученых (КМУ) (2018 г., Университет ИТМО).

Публикации. Основные результаты диссертационной работы опубликованы в 7 статьях, из них 4 публикации в изданиях, рецензируемых Scopus, 3 публикации в журналах из перечня ВАК.

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

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

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

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

Структура и объем диссертации

Диссертация состоит из перечня используемых сокращений, введения, пяти глав, заключения, списка литературы и приложений. Объем диссертации составляет 234 страниц, включает в себя 34 рисунка, 24 таблицы. Библиографический список включает 81 наименование.

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

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

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

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

Несмотря на то, стандарт сжатия Н.264 / ЛУС был выпущен достаточно давно, он до сих пор по-прежнему наиболее широко используется благодаря эффективности, а также балансу между производительностью и вычислительной сложностью. Тем не менее, постоянно развивающееся развитие технологий предъявляет новые требования к кодированию видео. Стандарт сжатия Н.265 / ЫЕУС был создан с расчетом на повышение эффективности сжатия для видео высокой и ультравысокой четкости. ЫЕУС показал снижение битрейта для передачи видеоданных от 30 до 50 процентов без потери качества. Этот результат обусловлен изменениями в структуре блоков кодирования, улучшениями внутри-и межкадрового предсказания, фильтров деблокирования, энтропийного кодера и т. д. Однако вычислительная сложность этого стандарта сжатия увеличилась во много раз, что привело к увеличению времени кодирования / декодирования, а также возросшим требованиям к оборудованию, по сравнению с предыдущими стандартами сжатия. С самого

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

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

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

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

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

Используя новую структуру кодирования с различными размерами единицы кодирования CU (Coding Unit) и единицы предсказания PU (Prediction Unit) в сочетании с 35 режимами предсказания, внутрикадровое кодирование в HEVC показывает более точные результаты по

сравнению с H.264 / AVC. Однако оптимальный режим выбирается для каждого PU путем расчета стоимости RD (Rate-Distortion) критерия для всех 35 режимов, и это является очень трудоемким процессом. Данная особенность затрудняет применение этого стандарта в приложениях реального масштаба времени. Для решения этой проблемы предлагается алгоритм, который объединяет метод оптимизации выбора кандидатов режима и решение о разделении CU, поэтому кодер может пропустить расчеты для ненужных размеров или режимов.

Рассматривая статистику выбора оптимальных режимов, было отмечено, что не все режимы играют одинаковую роль. Хотя для каждой видеопоследовательности есть индивидуальные различия, оптимальный выбор обычно фокусируется на режимах 0, 1, горизонтальном (режим 10), вертикальном (режим 26) и некоторых соседних как показано на рисунке P1. Вероятности выбора остальных режимов настолько малы, что ими можно пренебречь для упрощения расчетов и ускорения работы видеокодека.

20

15

0-Г 10

ашйй

» V '1'П <0 и и \\ О Ф Ф Ф Ф ^ Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф

Режимы предсказания О □ Traffic_2560x 1600_30 0 □ Cactus_1920x 1080_50 □ □ RaceHorses_832x480_30

Рисунок Р1 — Распределение вероятностей выбора режима предсказания в тестовых видеопоследовательностях

Основываясь на статистике выбора, был составлен список наиболее часто используемых режимов:

List! = {0,1, 2,6,10,14,18, 22, 26,30,34}.

(1)

5

0

В данный список вошли как наиболее популярные, так и некоторые угловые режимы на равном расстоянии. После расчета стоимости RD в процессе грубого решения режима RMD (Rough Mode Decision) будут проверены еще несколько режимов (рис. P2), чтобы более точно определить кандидатов для процесса оптимизации уровни искажений RDO (Rate-Distortion Optimized). Этот метод выбора помогает уменьшить общее количество режимов, которые необходимо проверять для каждого PU, до 68.75%. При этом потеря PSNR и средняя разница битрейта, измеряемые метриками Бьёнтегарда BD-PSNR (дБ) и BD-BR (%) соответственно, остаются на незначительном уровне, согласно таблице P1.

Рисунок Р2 — Внутрикадровое предсказание с адаптивным выбором режима. РМ и БМ - два лучших кандидата после первого процесса

ЯМБ

Таблица P1 — Сравнение метода выбора кандидатов режима с HM-16.20

Категория видео AT, % BD-BR, % BD-PSNR, дБ

A 13.50 0.89 -0.028

B 16.77 0.87 -0.017

C 16.74 1.06 -0.041

D 22.74 1.52 -0.048

E 12.58 2.25 -0.032

В среднем 16.46 1.32 -0.033

Чтобы найти подходящий размер для блока кодирования, кодер должен обрабатывать блоки различных размеров от наибольшего к наименьшему. Это одна из причин, которые дополнительно увеличивают вычислительную сложность. Для раннего определения продолжить или завершения разделения блока предлагается алгоритм, основанный на текстурных свойствах блока. Сложность L блока размером N х N определяется по 2, где Y(i,j) - значение яркости пикселя в точке (i, j), а Ya(i,j) представляет собой среднее значение яркости текущего блока.

i N-1 N-1

Ln xN = Е (Y (м) - Y»(>,j)f. (2)

i=0 j=0

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

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

Диапазон глубины единицы дерева кодирования CTU (Coding Tree Unit) можно предсказать заранее, используя CU внутри него. Dmin и Dmax обозначают минимальную и максимальную глубину текущего CTU. Их можно определить согласно 3 и 4.

0 если СИ64х64 однородный;

1 если есть СИ32х32 средне-сложный;

2 в иных случаях.

З-^'т.п.'г. — ^

(4)

0 если Сив4хб4 однородный;

1 если 4 Си32х32 однородные;

2 если 16 Си1бХ1б однородные;

3 если существует Си16х16 сложный.

V

С целью объединения метода выбора оптимальных режимов и текстурных свойств блоков Ри классифицируются на высоко-сложную (РИ4х4, РИвхв), средне-сложную (РИ16х16, РИз2х32) и низко-сложную (РИб4х64) группы. Поскольку выбор оптимального режима для каждого по сложности типа РИ в значительной степени зависят от его текстурных свойств, список режимов кандидатов Ыв^ может быть дополнительно сокращен, как показано на рисунке Р3 и в таблице Р2. В результате общее количество режимов, необходимых для расчета стоимости ИЛ при внут-рикадровом предсказании уменьшается на 88.57% (РИ64х64) и 77.14% (РИ16х16 и РИ32х32).

Другие

6% Угловой 26

5%

Угловой 10 7%

0 и 1

42%

Другие 10%

0 и 1

82%

Угловой 26 и соседние 20%

Угловой 10 и соседние 28%

Рисунок Р3 — Распределение выбора оптимальных режимов в однородной (слева) и средне-сложной (справа) областях

Таблица P2 — Режим-кандидаты для различных типов блоков

Тип блока Кандидаты

Однородный 0, 1, 10, 26

Средне-сложный 0, 1, 6, 10, 14, 22, 26, 30

Высоко-сложный 0, 1, 2, 6, 10, 14, 18, 22, 26, 30, 34

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

Шаг 1. Классифицировать CU по текстурам на однородный, средний и сложный.

Шаг 2. Выбрать оптимальный диапазон глубины [ Dmin,Dmax] на основе текстурных свойств CU.

Шаг 3. Выбрать список кандидатов List\ для PU в разных областях. Рассчитать RMD.

Шаг 4. Рассчитать RMD2 для дополнительных режимов в List2. Добавить наиболее вероятные режимы MPM (Most Probable Modes).

Шаг 5. Провести процесс RDO и по его результатам выбрать лучший режим.

Результаты работы общего алгоритма приведены в таблице P3, а RD-кривые для тестовой последовательности «FourPeople» из рекомендованного агентством ITU списка для тестирования видеокодеков показаны на рисунке P4. Потеря производительности и качества восстановленного видео незначительны.

Таблица P3 — Сравнение предложенного алгоритма с HM-16.20

Категория видео AT, % BD-BR, % BD-PSNR, дБ

A 36.26 1.85 -0.058

B 42.61 1.94 -0.038

C 36.91 2.22 -0.091

D 49.77 2.99 -0.109

E 55.61 3.85 -0.073

В среднем 44.23 2.57 -0.070

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

Конфигурация: AI-Main

Рисунок P4 — RD-кривые для яркостной (Y) компоненты последовательности «FourPeople»

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

Третья глава более подробно рассматривается межкадровое предсказание в HEVC и предлагаются некоторые меры по его улучшению. Процесс оценки движения ME (Motion Estimation) исследует временную избыточность из ранее закодированных кадров для кодирования текущего. В результате, кодировщику необходимо передавать и сохранять только различия между кадрами и вектором движения, что существенно сокращает объем данных. ME играет ключевую роль в кодировании видео и оказывает огромное влияние не только на эффективность сжатия, но и на сложность вычислений. По сравнению с H.264 / AVC, сложность ME в HEVC была значительно увеличена за счет различных разделов и направлений, а также большей точности. ME можно рассматривать как узкое место HEVC, поскольку именно на него приходится более половины времени работы видеокодека. Большую часть времени обработки ME составляют две его основные процедуры: оценка движения целочислен-

ных пикселей IME (Integer-pixel Motion Estimation) и оценка движения дробных пикселей FME (Fractional-pixel Motion Estimation).

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

В эталонном программном обеспечении принят алгоритм поиска по тестовой зоне TZS (Test Zone Search), который состоит из трех основных блоков: зональный поиск, растровый поиск и рафинирование. Хотя TZS приводит к значительному улучшению по сравнению с другими алгоритмами поиска, его сложность еще остается достаточно высокой. Для решения этой проблемы, в этой главе предлагается метод определения начальной точки поиска, и поискового диапазона. Для определения характеристики движения блока используются свойства движения и корреляция между векторами движения соседних блоков и текущего блока. Блок находится в однородной области если диапазоны поиска DPX и DPy меньше заданных порогов PX и Py. Координаты начальной точки поиска в этом случае задаются TPX, TPy. Схема предлагаемого алгоритма приведена на рисунке P5, где MV означает вектор движения; индексы L, R, AR представляют блоки слева, справа и сверху-справа соответственно от текущего.

DPx = MaxMVX - MinMVX;

X X

DPy = MaxMVy - MinMVyj;

MaxMVX + MinMVX

X X

X

■ (6) MaxMVX + MinMVyj У ;

TPy =-y-y-,

y 2 '

где MaxMVг = max(MVL, MVR, MVAR); MinMVj = min(MVL, MVR, MVAR); i,j = {L,R,AR}.

Ромбический или квадратичный поиск

Конец

Рисунок P5 — Блок-схема предлагаемого алгоритма определения

начальной точки

FME используется для уточнения предсказания вектора движения до | или | пикселя. Процесс интерполяции требует большего вычислительного ресурса, и в некоторых случаях он вызывает избыточность, поскольку FME может не понадобиться для статической области. Для уменьшения сложности предлагается алгоритм раннего решения пропуска FME, исходя из предположения, что, если PU размерности 2 N х 2 N выбирает целочисленный вектор движения в качестве окончательного наилучшего вектора движения для МЕ, это означает, что этот PU имеет простое содержимое или медленное движения, и другие разделения этого PU также будут кодироваться целочисленными векторами движения. Предлагаемый быстрый алгоритм может быть пошагово описан изложен следующим образом:

Список литературы диссертационного исследования кандидат наук Доан Бан Тиен, 2021 год

Литература

1. Cisco Annual Internet Report (2018-2023). — URL: https: //www.cisco.com/c/en/us/solutions/collateral/executive-perspectives/ annual-internet-report/white-paper-c11-741490.html (online; accessed: 2020-05-15).

2. ISO/IEC 14496-2:2004 - Information technology — Coding of audio-visual objects — Part 2: Visual. — URL: https://www.iso.org/standard/ 39259.html (online; accessed: 2020-05-16).

3. H.261 : Video codec for audiovisual services at p x 64 kbit/s.

URL: https://www.itu.int/rec/T-REC-H.261/en (online; accessed: 2020-05-16).

4. H.120 : Codecs for videoconferencing using primary digital group transmission. — URL: https://www.itu.int/rec/T-REC-H.120/ (online; accessed: 2020-05-16).

5. ISO/IEC 11172-2:1993 - Information technology — Coding of moving pictures and associated audio for digital storage media at up to about 1,5 Mbit/s — Part 2: Video (MPEG-1). — URL: https://www.iso.org/ standard/22411.html (online; accessed: 2020-05-16).

6. ISO/IEC 13818-2:2013 - Information technology — Generic coding of moving pictures and associated audio information — Part 2: Video (MPEG-2). — URL: https://www.iso.org/standard/61152.html (online; accessed: 2020-05-16).

7. H.262 : Information technology - Generic coding of moving pictures and associated audio information: Video. — URL: https://www.itu.int/rec/ T-REC-H.262 (online; accessed: 2020-05-16).

8. H.263 : Video coding for low bit rate communication. — URL: https: //www.itu.int/rec/T-REC-H.263/en (online; accessed: 2020-05-16).

9. H.264 : Advanced video coding for generic audiovisual services. — URL: https://www.itu.int/rec/T-REC-H.264 (online; accessed: 2020-05-16).

10. ISO/IEC 14496-10:2012 - Information technology — Coding of audio-visual objects — Part 10: Advanced Video Coding. — URL: https: //www.iso.org/standard/61490.html (online; accessed: 2020-05-16).

11. Bitmovin. Video Developer Report 2019. — URL: https://go.bitmovin. com/video-developer-report-2019 (online; accessed: 2020-05-16).

12. H.265 : High efficiency video coding. — URL: https://www.itu.int/rec/ T-REC-H.265/en (online; accessed: 2020-05-16).

13. ISO/IEC 23008-2:2013 - Information technology — High efficiency coding and media delivery in heterogeneous environments — Part 2: High efficiency video coding. — URL: https://www.iso.org/standard/35424.html (online; accessed: 2020-05-16).

14. Comparison of the coding efficiency of video coding standards—including high efficiency video coding (HEVC) / Jens-Rainer Ohm, Gary J Sullivan, Heiko Schwarz et al. // IEEE Transactions on circuits and systems for video technology. — 2012. — Vol. 22, no. 12. — Pp. 1669-1684.

15. Overview of the high efficiency video coding (HEVC) standard / Gary J Sullivan, Jens-Rainer Ohm, Woo-Jin Han, Thomas Wiegand // IEEE Transactions on circuits and systems for video technology. — 2012.

- Vol. 22, no. 12. — Pp. 1649-1668.

16. Bjontegaard Gisle. Calculation of average PSNR differences between RD-curves // VCEG-M33. — 2001.

17. Image quality assessment: from error measurement to structural similarity / Zhou Wang, Alan C Bovik, Hamid R Sheikh, Eero P Simoncelli // IEEE transactions on image processing. — 2004. — Vol. 13, no. 1.

18. Wang Zhou, Simoncelli Eero P, Bovik Alan C. Multiscale structural similarity for image quality assessment // The Thrity-Seventh Asilomar

Conference on Signals, Systems & Computers, 2003 / Ieee. — Vol. 2.

- 2003. — Pp. 1398-1402.

19. Intra coding of the HEVC standard / Jani Lainema, Frank Bossen, Woo-Jin Han et al. // IEEE transactions on circuits and systems for video technology. — 2012. — Vol. 22, no. 12. — Pp. 1792-1801.

20. Min Biao, Cheung Ray CC. A fast CU size decision algorithm for the HEVC intra encoder // IEEE Transactions on Circuits and Systems for Video Technology. — 2014. — Vol. 25, no. 5. — Pp. 892-896.

21. Chen Zong-Yi, Chang Pao-Chi. Rough mode cost-based fast intra coding for high-efficiency video coding // Journal of Visual Communication and Image Representation. — 2017. — Vol. 43. — Pp. 77-88.

22. A unified architecture for fast HEVC intra-prediction coding / Damian Ruiz, Gerardo Fernández-Escribano, Jose Luis Martínez, Pedro Cuenca // Journal of Real-Time Image Processing. — 2019. -Vol. 16, no. 5. — Pp. 1825-1844.

23. Fast CU size decision and PU mode decision algorithm in HEVC intra coding / Xiwu Shang, Guozhong Wang, Tao Fan, Yan Li // 2015 IEEE International Conference on Image Processing (ICIP) / IEEE. — 2015.

- Pp. 1593-1597.

24. Fast intra-mode and CU size decision for HEVC / Tao Zhang, Ming-Ting Sun, Debin Zhao, Wen Gao // IEEE Transactions on Circuits and Systems for Video Technology. — 2016. — Vol. 27, no. 8. — Pp. 1714-1726.

25. Oztekin Abdulkerim, Erçelebi Ergun. An early split and skip algorithm for fast intra CU selection in HEVC // Journal of Real-Time Image Processing. — 2016. — Vol. 12, no. 2. — Pp. 273-283.

26. Yang Mingyuan, Grecos Christos. Fast intra encoding decisions for high efficiency video coding standard // Journal of Real-Time Image Processing. — 2017. — Vol. 13, no. 4. — Pp. 797-806.

27. Fast CU size and prediction mode decision algorithm for HEVC based on direction variance / Xuebin Sun, Xiaodong Chen, Yong Xu et al. // Journal of Real-Time Image Processing. — 2019. — Vol. 16, no. 5. -Pp. 1731-1744.

28. Adaptive CU mode selection in HEVC intra prediction: a deep learning approach / Shiba Kuanar, KR Rao, Monalisa Bilas, Jonathan Bredow // Circuits, Systems, and Signal Processing. — 2019. — Vol. 38, no. 11. -Pp. 5081-5102.

29. An adaptive workload management scheme for HEVC encoding / Ma-teus Grellert, Muhammad Shafique, Muhammad Usman Karim Khan et al. // 2013 IEEE International Conference on Image Processing / IEEE. — 2013. — Pp. 1850-1854.

30. HEVC complexity and implementation analysis / Frank Bossen, Benjamin Bross, Karsten Suhring, David Flynn // IEEE Transactions on Circuits and Systems for Video Technology. — 2012. — Vol. 22, no. 12.

- Pp. 1685-1696.

31. High efficiency video coding (HEVC) test model 10 (HM10) encoder description / Il-Koo Kim, Ken McCann, Kazuo Sugimoto et al. // Document: JCTVC-01002, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 15th Meeting: Geneva. — 2013.

32. Choi Kiho, Park Sang-Hyo, Jang Euee S. Coding tree pruning based CU early termination // JCT-VC document, JCTVC-F092. — 2011.

33. Early SKIP detection for HEVC / J Yang, J Kim, K Won et al. // JCT-VC document, JCTVC-G543. — 2011.

34. Gweon RH, Lee YL, Lim J. Early termination of CU encoding to reduce HEVC complexity // JCT-VC document, JCTVC- F045. — 2011.

35. Choi Kiho, Jang Euee S. Fast coding unit decision method based on coding tree pruning for high efficiency video coding // Optical Engineering.

- 2012. — Vol. 51, no. 3. — P. 030502.

36. Yoo Hyang-Mi, Suh Jae-Won. Fast coding unit decision algorithm based on inter and intra prediction unit termination for HEVC // 2013 IEEE International Conference on Consumer Electronics (ICCE) / IEEE. —

2013. - Pp. 300-301.

37. Shen Liquan, Zhang Zhaoyang, Liu Zhi. Adaptive inter-mode decision for HEVC jointly utilizing inter-level and spatiotemporal correlations // IEEE Transactions on Circuits and Systems for Video Technology. -

2014. - Vol. 24, no. 10. - Pp. 1709-1722.

38. Ahn Sangsoo, Lee Bumshik, Kim Munchurl. A novel fast CU encoding scheme based on spatiotemporal encoding parameters for HEVC inter coding // IEEE Transactions on Circuits and Systems for Video Technology. - 2014. - Vol. 25, no. 3. - Pp. 422-435.

39. A fast CU size decision algorithm for HEVC / Jaeho Lee, Seongwan Kim, Kyungmin Lim, Sangyoun Lee // IEEE Transactions on Circuits and Systems for Video Technology. - 2014. - Vol. 25, no. 3. - Pp. 411-421.

40. Fast HEVC inter CU decision based on latent SAD estimation / Jian Xiong, Hongliang Li, Fanman Meng et al. // IEEE Transactions on Multimedia. - 2015. - Vol. 17, no. 12. - Pp. 2147-2159.

41. Shen Xiaolin, Yu Lu, Chen Jie. Fast coding unit size selection for HEVC based on Bayesian decision rule // 2012 picture coding symposium / IEEE. - 2012. - Pp. 453-456.

42. Kim Hyo-Song, Park Rae-Hong. Fast CU partitioning algorithm for HEVC using an online-learning-based Bayesian decision rule // IEEE transactions on circuits and systems for video technology. - 2015. -Vol. 26, no. 1. - Pp. 130-138.

43. MRF-based fast HEVC inter CU decision with the variance of absolute differences / Jian Xiong, Hongliang Li, Fanman Meng et al. // IEEE Transactions on Multimedia. - 2014. - Vol. 16, no. 8. - Pp. 2141-2153.

44. An effective CU size decision method for HEVC encoders / Liquan Shen, Zhi Liu, Xinpeng Zhang et al. // IEEE transactions on multimedia. -2012. — Vol. 15, no. 2. — Pp. 465-470.

45. An adaptive inter CU depth decision algorithm for HEVC / Jie Liu, Huizhu Jia, Guoqing Xiang et al. // 2015 Visual Communications and Image Processing (VCIP) / IEEE. — 2015. — Pp. 1-4.

46. Zhou Chengtao, Zhou Fan, Chen Yaowu. Spatio-temporal correlation-based fast coding unit depth decision for high efficiency video coding // Journal of Electronic Imaging. — 2013. — Vol. 22, no. 4.

- P. 043001.

47. Zhao Wenjun, Onoye Takao, Song Tian. Hierarchical structure-based fast mode decision for H. 265/HEVC // IEEE Transactions on Circuits and Systems for Video Technology. — 2015. — Vol. 25, no. 10.

- Pp. 1651-1664.

48. Liu Zhaoyi, Lin Ting-Lan, Chou Chi-Chan. Efficient prediction of CU depth and PU mode for fast HEVC encoding using statistical analysis // Journal of Visual Communication and Image Representation. — 2016.

- Vol. 38. — Pp. 474-486.

49. A fast inter coding algorithm for HEVC based on texture and motion quad-tree models / Fen Chen, Peng Li, Zongju Peng et al. // Signal Processing: Image Communication. — 2016. — Vol. 47. — Pp. 271-279.

50. Zhang Yongfei, Wang Haibo, Li Zhe. Fast coding unit depth decision algorithm for interframe coding in HEVC // 2013 Data Compression Conference / IEEE. — 2013. — Pp. 53-62.

51. An improved similarity-based fast coding unit depth decision algorithm for inter-frame coding in HEVC / Rui Fan, Yongfei Zhang, Zhe Li, Ning Wang // International Conference on Multimedia Modeling / Springer. — 2014. — Pp. 529-540.

52. Adaptive inter CU depth decision for HEVC using optimal selection model and encoding parameters / Yue Li, Gaobo Yang, Yapei Zhu et al. //

IEEE Transactions on Broadcasting. - 2017. - Vol. 63, no. 3. -Pp. 535-546.

53. Multidirectional parabolic prediction-based interpolation-free sub-pixel motion estimation / Rui Fan, Yongfei Zhang, Bo Li, Gang Wang // Signal Processing: Image Communication. - 2017. - Vol. 53. - Pp. 123-134.

54. Parmar Nidhi, Sunwoo Myung Hoon. Enhanced Test Zone search motion estimation algorithm for HEVC // 2014 International SoC Design Conference (ISOCC) / IEEE. - 2014. - Pp. 260-261.

55. Jeong Jae Heon, Parmar Nidhi, Sunwoo Myung Hoon. Enhanced test zone search algorithm with rotating pentagon search // 2015 International SoC Design Conference (ISOCC) / IEEE. - 2015. - Pp. 275-276.

56. Yang Shih-Hsuan, Jiang Jia-Ze, Yang Hsien-Jie. Fast motion estimation for HEVC with directional search // Electronics Letters. - 2014. -Vol. 50, no. 9. - Pp. 673-675.

57. Fan Rui, Zhang Yongfei, Li Bo. Motion classification-based fast motion estimation for high-efficiency video coding // IEEE Transactions on Multimedia. - 2016. - Vol. 19, no. 5. - Pp. 893-907.

58. Ko Yun-Ho, Kang Hyun-Soo, Lee Si-Woong. Adaptive search range motion estimation using neighboring motion vector differences // IEEE Transactions on Consumer Electronics. - 2011. - Vol. 57, no. 2. -Pp. 726-730.

59. Adaptive search range algorithm based on Cauchy distribution / Wei Dai, Oscar C Au, Sijin Li et al. // 2012 Visual Communications and Image Processing / IEEE. - 2012. - Pp. 1-5.

60. Adaptive low-complexity motion estimation algorithm for high efficiency video coding encoder / Ahmed Medhat, Ahmed Shalaby, Mohammed Sharaf Sayed et al. // IET Image Processing. - 2016. -Vol. 10, no. 6. - Pp. 438-447.

61. Li Wenhua, Salari Ezzatollah. Successive elimination algorithm for motion estimation // IEEE transactions on image processing. — 1995. -Vol. 4, no. 1. — Pp. 105-107.

62. Gao XQ, Duanmu CJ, Zou CR. A multilevel successive elimination algorithm for block matching motion estimation // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 3. — Pp. 501-504.

63. Nalluri Purnachand, Alves Luis Nero, Navarro Antonio. Complexity reduction methods for fast motion estimation in HEVC // Signal Processing: Image Communication. — 2015. — Vol. 39. — Pp. 280-292.

64. Fast motion estimation based on content property for low-complexity H. 265/HEVC encoder / Zhaoqing Pan, Jianjun Lei, Yun Zhang et al. // IEEE Transactions on Broadcasting. — 2016. — Vol. 62, no. 3. — Pp. 675-684.

65. Zhang Ying, Shen Tingzhi. Motion information based adaptive block classification for fast motion estimation // 2008 International Conference on Neural Networks and Signal Processing / IEEE. — 2008. — Pp. 686-691.

66. A novel fast two step sub-pixel motion estimation algorithm in HEVC / Wei Dai, Oscar C Au, Chao Pang et al. // 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) / IEEE.

- 2012. — Pp. 1197-1200.

67. A fast sub-pixel motion estimation algorithm for HEVC / Shan Jia, Wenpeng Ding, Yunhui Shi, Baocai Yin // 2016 IEEE International Symposium on Circuits and Systems (ISCAS) / IEEE. — 2016. — Pp. 566-569.

68. Zhang Qi, Dai Yunyang, Kuo C-C Jay. Direct techniques for optimal sub-pixel motion accuracy estimation and position prediction // IEEE transactions on circuits and systems for video technology. — 2010. — Vol. 20, no. 12. — Pp. 1735-1744.

69. A robust interpolation-free approach for sub-pixel accuracy motion estimation / Wei Dai, Oscar C Au, Wenjing Zhu et al. // 2013 IEEE

International Conference on Image Processing / IEEE. — 2013. -Pp. 1767-1771.

70. Zuo Xuguang, Yu Lu. A novel interpolation-free scheme for fractional pixel motion estimation // 2015 Picture Coding Symposium (PCS) / IEEE. — 2015. — Pp. 80-84.

71. Core transform design in the high efficiency video coding (HEVC) standard / Madhukar Budagavi, Arild Fuldseth, Gisle Bj0ntegaard et al. // IEEE Journal of Selected Topics in Signal Processing. — 2013. — Vol. 7, no. 6. — Pp. 1029-1041.

72. Ahmed Nasir, Natarajan T_, Rao Kamisetty R. Discrete cosine transform // IEEE transactions on Computers. — 1974. — Vol. 100, no. 1. — Pp. 90-93.

73. Budagavi Madhukar, Sze Vivienne. Unified forward+ inverse transform architecture for HEVC // 2012 19th IEEE International Conference on Image Processing / IEEE. — 2012. — Pp. 209-212.

74. 2-D large inverse transform (16 x 16, 32 x 32) for HEVC (high efficiency video coding) / Jong-Sik Park, Woo-Jin Nam, Seung-Mok Han, Seong-Soo Lee // JSTS: Journal of Semiconductor Technology and Science. -2012. — Vol. 12, no. 2. — Pp. 203-211.

75. Ahmed Ashfaq, Shahid Muhammad Usman et al. N Point DCT VLSI Architecture for Emerging HEVC Standard // VLSI Design. — 2012. — Vol. 2012.

76. A fast algorithm-based cost-effective and hardware-efficient unified architecture design of 4 x 4, 8 x 8, 16 x 16, and 32 x 32 inverse core transforms for HEVC / Chia-Wei Chang, Hao-Fan Hsu, Chih-Peng Fan et al. // Journal of Signal Processing Systems. — 2016. — Vol. 82, no. 1.

- Pp. 69-89.

77. Multiplierless 16-point DCT approximation for low-complexity image and video coding / Thiago LT da Silveira, Raiza S Oliveira, Fabio M Bayer et al. // Signal, Image and Video Processing. — 2017. — Vol. 11, no. 2.

- Pp. 227-233.

78. Chatterjee Subiman, Sarawadekar Kishor. Approximated Core Transform Architectures for HEVC Using WHT-Based Decomposition Method // IEEE Transactions on Circuits and Systems I: Regular Papers. — 2019. — Vol. 66, no. 11. — Pp. 4296-4308.

79. Jridi Maher, Alfalou Ayman, Meher Pramod K. Efficient approximate core transform and its reconfigurable architectures for HEVC // Journal of Real-Time Image Processing. — 2018. — Pp. 1-11.

80. Arai Yukihiro, Agui Takeshi, Nakajima Masayuki. A fast DCT-SQ scheme for images // IEICE TRANSACTIONS (1976-1990). — 1988. — Vol. 71, no. 11. — Pp. 1095-1097.

81. Winograd Shmuel. On computing the discrete Fourier transform // Mathematics of computation. — 1978. — Vol. 32, no. 141. — Pp. 175-199.

Краткие обозначения

Обозначение На английском На русском

1-D One-Dimensional Одномерный

2-D Two-Dimensional Двумерный

AI All Intra Все внутри

AVC Advanced Video Coding Расширенное кодирование видео

BD-BR Bj0ntegaard-Delta Bitrate Метрика Бьёнтегарда (битрейт)

BD-PSNR Bj0ntegaard-Delta PSNR Метрика Бьёнтегарда (РЯЖ)

BMA Block Matching Algorithm Алгоритм блочного сопоставления

CABAC Context Adaptive Binary Arithmetic Coding Контекстно-адаптивное двоичное арифметическое кодирование

CB Coding Block Блок кодирования

CTB Coding Tree Block Блок дерева кодирования

CTU Coding Tree Unit Единица дерева кодирования

CU Coding Unit Блок кодирования

dB Decibel Децибел (дБ)

DCT Discrete Cosine Дискретное косинусное

Transform преобразование

DFT Discrete Fourier Transform Дискретное преобразование Фурье

DST Discrete Sine Дискретное синусоидальное

Transform преобразование

ECU Early CU termination Ранее прекращения Си

ESD Early Skip Detection Ранее обнаружение пропуски

FME Fractional-pixel Оценка движения

Motion Estimation дробных пикселей

HEVC High Efficiency Video Высокоэффективное

Coding кодирование видео

HM HEVC Test Model Эталонное программное обеспечение ЫЕУС

IME Integer-pixel Motion Оценка движения

Estimation целочисленных пикселей

ISO International Organization Международная организация

for Standardization стандартизации

ITU International Международный союз

Telecommunication Union электросвязи

International Сектор стандартизации

ITU-T Telecommunication Union - Telecommunication электросвязи Международного

Standardization Sector союза электросвязи

LB Low Delay Низкая задержка

with B-pictures с В-изображениями

LCU Largest Coding Unit Наибольший блок кодирования

LD Low Delay Низкая задержка

LP Low Delay Низкая задержка

with P-pictures с Р-изображениями

MAD Mean of Absolute Среднее значение

Differences абсолютных разностей

MC Motion Compensation Компенсация движения

MB Macro Block Макроблок

MCM Multiple-Constant Multiplication Многократное умножение

ME Motion Estimation Оценка движения

MPEG Moving Picture Экспертная группа по

Experts Group движущимся изображениям

MPM Most Probable Mode Наиболее вероятное режим

MSE Mean Squared Error Средняя квадратическая ошибка

MS-SSIM Multiple-Scale SSIM Мультимасштабный ЯБШ

MV Motion Vector Вектор движения

PB Prediction Block Блок предсказания

PMV Predictive Motion Вектор предсказательного

Vector движения

POC Picture Order Count Счетчик порядка изображения

PSNR Peak Signal to Noise Пиковое отношение

Ratio сигнал-шум

PU Prediction Unit Единица предсказания

QP Quantization Parameter Параметр квантования

RA Random Access Произвольный доступ

RAP Random Точка произвольного

Access Point доступа

RD Rate-Distortion Скорость-Искажение

RDOQ Rate-Distortion Optimized Quantization Оптимизирование квантование скорости-искажения

RMD Rough Mode Грубой выбор

Decision режима

RQT Residual Quad Tree Четырехугольное дерево остатка

SCU Smallest Coding Unit Наименьшая единица кодирования

SOP Structure of Pictures Структура изображений

SSIM Structural Similarity Индекс структурного

Index сходства

TB Transform Block Блок преобразования

TU Transform Unit Единица преобразования

TZS Test Zone Search Поиск по тестовой зоне

^ ^ Video Coding Экспертная группа по VCEG

Experts Group кодированию видео

Y Luminance Яркость

Приложение 1 - Конфигурация системы для эксперимента

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

- Операционная система: macOS Mojave, версия 10.14.x;

- Процессор: Intel© Core™ i5-5257U @ 2.7 ГГц;

- Оперативная память: 8 ГБ.

Приложение 2 - Тестовые видеопоследовательности

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

Таблица А1 — Тестовые видеопоследовательности_

Категория Разрешение Последовательность Частота кадров

А 2560 х 1600 ТМс 30 Hz

Реор1еОп81гее1 30 Ыz

Юшопо 24 Ыz

РагкБсепе 24 Ыz

В 1920 х 1080 Са^иэ 50 Hz

Вазке^аШпуе 50 Ыz

BQTeггace 60 Ыz

Вазке^аЮгШ 50 Ыz

С 832 х 480 BQMa11 60 Ыz

Раг1уБсепе 50 Hz

КасеЫогэез 30 Ыz

ВазкеЛаПРазэ 50 Ыz

э 416 х 240 BQSquaгe 60 Ыz

В1ошт§ВиЬЬ1е8 50 Ыz

КасеЫогэез 30 Hz

ЕоигРеор1е 60 Ыz

Е 1280 х 720 ЛоЬппу 60 Ыz

KгistenAndSaгa 60 Ыz

Приложение 3 - Выходной файл журнала

HM software: Encoder Version [16.20] (including RExt) [Mac OS X] [GCC 4 . 2.1][6 4 bit]

Input File

Bitstream File

Reconstruction File Real Format I n t e r n a l Format Sequence PSNR output Sequence MSE output Frame MSE output MS-SSIM output xPSNR c a l c u l a t i o n Cabac-zero —word-padding Frame /Field Frame index Profile

CU size / depth / total —depth RQT trans. size (min / max) Max RQT depth inter Max RQT depth intra Min PCM size Motion search range Intra period Decoding refresh type

QP

Max dQP signaling depth Cb QP Offset Cr QP Offset QP a d a p t a t i o n GOP size Input bit depth MSB—extended bit depth Internal bit depth PCM sample bit depth Intra reference smoothing diff_cu_chroma_qp_ offset _ depth extended_precision_processing_flag implicit _rdpcm_enabled_flag explicit_rdpcm_enabled_flag transform_skip_rotation_enabled_flag transform_skip_context_enabled_flag cross_component_prediction_enabled_flag high_precision_offsets_enabled_flag

FourPeople_1280x720_60 . yuv

FourPeople . bin

FourPeople . yuv

1280x720 60Hz

1280x720 60Hz

Linear average only

Enabled

Enabled

Enabled

Disabled

Enabled

Frame based coding

0 — 19 (20 frames) main

64 / 4 / 4

4/32

3

3

8

64

1 1 22 0 0 0

0 (range=0)

1

(Y 8 , C 8)

(Y 8 , C 8)

(Y 8 , C 8)

(Y 8 , C 8)

Enabled —1

Disabled Disabled Disabled Disabled Disabled Disabled Disabled

persistent_rice_adaptation_enabled_flag

cabac_bypass_alignment_enabled_flag

log2_sao_offset_scale_luma

log2_sao_offset_scale_chroma

Cost function :

RateControl

WPMethod

Max Num Merge Candidates

Disabled Disabled

Lossy coding (default)

TOOL CFG: IBD : 0 HAD: 1 RDQ: 1 RDQTS: 1 RDpenalty:0 LQP:0 SQP:0 ASR:0 MinSearchWindow : 8 RestrictMESampling : 0 FEN: 1 ECU:0 FDM: 1 CFM: 0 ESD:0 RQT: 1 TransformSkip : 1 TransformSkipFast : 1 TransformSkipLog2MaxSize : 2 Slice: M=0 SliceSegment : M=0 CIP: 0 SAO:1 PCM:0 TransQuantBypassEnabled : 0 WPP: 0 WPB: 0 PME: 2 WaveFrontSynchro : 0 WaveFrontSubstreams : 1 ScalingList :0 TMVPMode: 1 AQpS:0 SignBitHidingFlag : 1 RecalQP:0

Non environment variable controlled macros set as follows :

RExt__DECODER_DEBUG_BIT_STATISTICS = 0

RExt__HIGH_BIT_DEPTH_SUPPORT = 0

RExt__HIGH_PRECISION_FORWARD_TRANSFORM = 0

O0043_BEST_EFFORT_DECODING = 0

ME_ENABLE_ROUNDING_OF_MVS = 1

Input ChromaFormatIDC = 4:2:0 Output ( internal ) ChromaFormatIDC = 4: 2: 0

POC 0 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 503168 bits [Y 43.8511 dB

U 46.8547 dB V 47.9694 dB] [MS-SSIM Y 0.996374 U 0.995453 V

0.996240] [Y MSE 2.6790 U MSE 1.3415 V MSE 1.0379] [ET 4 ] [L0 ] [L1 ]

POC 1 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 500776 bits [Y 43.8376 dB

U 46.8537 dB V 47.9597 dB] [MS-SSIM Y 0.996386 U 0.995397 V

0.996244] [Y MSE 2.6873 U MSE 1.3419 V MSE 1.0402] [ET 4 ] [L0 ] [L1 ]

POC 2 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 502624 bits [Y 43.8464 dB

U 46.8604 dB V 47.9999 dB] [MS-SSIM Y 0.996399 U 0.995423 V

0.996291] [Y MSE 2.6819 U MSE 1.3398 V MSE 1.0306] [ET 4 ] [L0 ] [L1 ]

POC 3 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 502112 bits [Y 43.8278 dB

U 46.9083 dB V 47.9618 dB] [MS-SSIM Y 0.996386 U 0.995458 V

0.996231] [Y MSE 2.6934 U MSE 1.3251 V MSE 1.0397] [ET 4 ] [L0 ] [L1 ]

POC 4 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 502872 bits [Y 43.8439 dB

U 46.8355 dB V 48.0113 dB] [MS-SSIM Y 0.996393 U 0.995454 V

0.996275] [Y MSE 2.6834 U MSE 1.3475 V MSE 1.0279] [ET 4 ] [L0 ] [L1 ]

POC 5 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 500784 bits [Y 43.8406 dB

U 46.8316 dB V 47.9981 dB] [MS-SSIM Y 0.996377 U 0.995377 V

0.996280] [Y MSE 2.6854 U MSE 1.3487 V MSE 1.0310] [ET 4 ] [L0 ] [L1 ]

POC 6 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 503160 bits [Y 43.8426 dB

U 46.9101 dB V 47.9823 dB] [MS—SSIM Y 0.996397 U 0.995525 V

0.996272] [Y MSE 2.6842 U MSE 1.3246 V MSE 1.0348] [ET 4 ] [L0 ] [L1 ]

POC 7 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 501104 bits [Y 43.8410 dB

U 46.8398 dB V 47.9546 dB] [MS—SSIM Y 0.996406 U 0.995412 V

0.996245] [Y MSE 2.6852 U MSE 1.3462 V MSE 1.0414] [ET 4 ] [L0 ] [L1 ]

POC 8 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 503944 bits [Y 43.8496 dB

U 46.8670 dB V 47.9691 dB] [MS—SSIM Y 0.996400 U 0.995387 V

0.996227] [Y MSE 2.6799 U MSE 1.3378 V MSE 1.0379] [ET 4 ] [L0 ] [L1 ]

POC 9 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 503704 bits [Y 43.8315 dB

U 46.8364 dB V 47.9641 dB] [MS—SSIM Y 0.996393 U 0.995430 V

0.996228] [Y MSE 2.6911 U MSE 1.3472 V MSE 1.0391] [ET 4 ] [L0 ] [L1 ]

POC 10 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502696 bits [Y 43.8070 dB

U 46.8884 dB V 47.9792 dB] [MS—SSIM Y 0.996362 U 0.995477 V

0.996282] [Y MSE 2.7063 U MSE 1.3312 V MSE 1.0355] [ET 4 ] [L0 ] [L1 ]

POC 11 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502768 bits [Y 43.8423 dB

U 46.8798 dB V 47.9582 dB] [MS—SSIM Y 0.996412 U 0.995449 V

0.996247] [Y MSE 2.6844 U MSE 1.3338 V MSE 1.0405] [ET 4 ] [L0 ] [L1 ]

POC 12 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 504376 bits [Y 43.8180 dB

U 46.8564 dB V 47.9244 dB] [MS—SSIM Y 0.996381 U 0.995437 V

0.996232] [Y MSE 2.6995 U MSE 1.3410 V MSE 1.0487] [ET 4 ] [L0 ] [L1 ]

POC 13 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502848 bits [Y 43.8194 dB

U 46.8723 dB V 47.9838 dB] [MS—SSIM Y 0.996401 U 0.995451 V

0.996267] [Y MSE 2.6986 U MSE 1.3361 V MSE 1.0344] [ET 4 ] [L0 ] [L1 ]

POC 14 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502784 bits [Y 43.8241 dB

U 46.8771 dB V 47.9838 dB] [MS—SSIM Y 0.996394 U 0.995502 V

0.996236] [Y MSE 2.6957 U MSE 1.3347 V MSE 1.0344] [ET 4 ] [L0 ] [L1 ]

POC 15 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502040 bits [Y 43.8296 dB

U 46.8796 dB V 47.9379 dB] [MS—SSIM Y 0.996368 U 0.995452 V

0.996204] [Y MSE 2.6923 U MSE 1.3339 V MSE 1.0454] [ET 4 ] [L0 ] [L1 ]

POC 16 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502648 bits [Y 43.8111 dB

U 46.8439 dB V 47.9710 dB] [MS—SSIM Y 0.996390 U 0.995426 V

0.996229] [Y MSE 2.7038 U MSE 1.3449 V MSE 1.0375] [ET 4 ] [L0 ] [L1 ]

POC 17 TId: 0 ( I —SLICE, nQP 22 QP 22 ) 502144 bits [Y 43.8285 dB

U 46.8609 dB V 47.9862 dB] [MS—SSIM Y 0.996377 U 0.995429 V

0.996228] [Y MSE 2.6929 U MSE 1.3396 V MSE 1.0338] [ET 4 ] [L0 ] [L1 ]

POC 18 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 503144 bits [Y 43.8285 dB

U 46.8707 dB V 47.9899 dB] [MS-SSIM Y 0.996381 U 0.995420 V

0.996266] [Y MSE 2.6929 U MSE 1.3366 V MSE 1.0330] [ET 4 ] [L0 ] [L1 ]

POC 19 TId: 0 ( I -SLICE, nQP 22 QP 22 ) 500880 bits [Y 43.8233 dB

U 46.8735 dB V 47.9706 dB] [MS-SSIM Y 0.996356 U 0.995438 V

0.996251] [Y MSE 2.6962 U MSE 1.3358 V MSE 1.0376] [ET 4 ] [L0 ] [L1 ]

SUMMARY-

Total Frames | Bitrate Y-PSNR U-PSNR V-PSNR YUV-PSNR Y-MS-SSIM U-MS-SSIM V-MS-SSIM Y-MSE U-MSE V-MSE YUV-MSE

20 a 30151.7280 43.8322 0.996387 0.995440 0.996249 2.1897

I Slices-

Total Frames | Bitrate Y-PSNR U-PSNR V-PSNR YUV-PSNR Y-MS-SSIM U-MS-SSIM V-MS-SSIM Y-MSE U-MSE V-MSE YUV-MSE

20 i 30151.7280 43.8322 0.996387 0.995440 0.996249 2.1897

P Slices-

Total Frames | Bitrate Y-PSNR U-PSNR V-PSNR YUV-PSNR Y-MS-SSIM U-MS-SSIM V-MS-SSIM Y-MSE U-MSE V-MSE YUV-MSE

0 p nan nan nan nan nan

nan nan nan nan nan nan

nan

B Slices-

Total Frames | Bitrate Y-PSNR U-PSNR V-PSNR YUV-PSNR Y-MS-SSIM U-MS-SSIM V-MS-SSIM Y-MSE U-MSE V-MSE YUV-MSE

0 b nan nan nan nan nan

nan nan nan nan nan nan

nan RVM: 0.000

Bytes written to file: 1256322 (30151.728 kbps) Total Time: 87.091 sec .

46.8650 47.9728 44.7270 2.6907 1.3384 1.0371

46.8650 47.9728 44.7270 2.6907 1.3384 1.0371

Приложение 4 - Акты о внедрении

^ ОБЩЕСТВО С ОГРАНИЧЕННОЙ

ОТВЕТСТВЕННОСТЬЮ "ЛМТ"

№ Q3/21 от 04.02.2021 г. На № от

"УТВЕРЖДАЮ" Генеральный директор ООО «ЛМТ» г.Е. Шатунов

¿>2- 2021 г.

АКТ ИСПОЛЬЗОВАНИЯ

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

Комиссия в составе председателя комиссии ведущего специалиста к.т.н. Пинкевича В.Ю. и члена комиссии инженера Ключева В.А. составили настоящий акт о том, что в ООО «ЛМТ» использованы результаты диссертации Доан Бан Тиена на тему «Разработка и исследование алгоритмов устранения визуальной избыточности на основе кодирующих преобразований», а именно: методы устранения внутри- и межкадровой избыточности при сжатии видеоданных, позволяющие сократить время компрессии по сравнению со стандартом сжатия H.265/HEVC.

Эффект от использования указанных результатов в разрабатываемом проекте платформы «Умное здание» заключается в снижении требований к производительности контроллерных блоков распределенной вычислительной системы объектов автоматизации при организации видеоконференций и передаче видеоданных.

Экономический эффект от использования не определялся.

Председатель комиссии wLLiMv^ ' В.Ю.Пинкевич

Член комиссии у* В.А.Ключев

Юр. адрес: 194044, город Санкт-Петербург, переулок Зеленков, дом 7А, литер 3, пом.5-н, офис 120. Факт, адрес: 199034, г. Санкт-Петербург, Биржевая линия, д. 16. ОГРН 1027801562172 ИНН 7802097381 КПП 780201001 тел./факс: [phone] http://lmt.spb.ru, email: [e-mail]

Приложение 5 - Тексты публикаций

I. Doan, B. Fast Intra Mode Decision for HEVC / Doan, B. and Tropchenko, A. // CEUR Workshop Proceedings. 2020. Vol. 2590, pp. 1-10.

II. Доан, Б. Т. Быстрый алгоритм оценки движения в видеокодеке стандарта HEVC / Б. Т. Доан, А. А. Тропченко // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 6(130). С. 802-806. doi: 10.17586/2226-1494-2020-20-6-802-806

III. Doan, B. Fast Intra Mode Decision Algorithm for HEVC Based on Block Textural Properties / Doan, B. and Tropchenko, A. // CEUR Workshop Proceedings. 2020. Vol. 2744, pp. 1-8. doi: 10.51130/graphicon-2020-2-4-57

IV. Доан, Б. Т. Применение гибридного преобразования в видеокодеке стандарта HEVC / Б. Т. Доан, А. А. Тропченко // Известия Тульского государственного университета. Технические науки. 2020. № 10. С. 263-269.

V. Ban, D. T. Improving the Efficiency of Entropy Coding Method in Video Encoder H.265/HEVC / Tropchenko, A., Ban, D. T. and VanTruong, N. // CEUR Workshop Proceedings - 2018, Vol. 2268, pp. 95-103.

VI. Доан, Б. Т. Гибридный алгоритм для быстрой оценки движения в стандарте H.265/HEVC / Доан Б. Т., Тропченко А. А. // Известия высших учебных заведений. Приборостроение. 2020. Т. 63. № 1. С. 18-25. doi: 10.17586/0021-3454-2020-63-1-18-25

VII. Доан, Б. Т. Повышение эффективности метода кодирования внут-рикадровым предсказанием в стандарте H.265/HEVC / Нгуен В., Тропченко А. А., Доан Б. Т. // Научно-технический вестник информационных технологий, механики и оптики. 2018. Т. 18. № 2(114). С. 255-261. doi: 10.17586/2226-1494-2018-18-2-255-261

Fast Intra Mode Decision for HEVC

Ban Doanl0000-0003-0900-6284! and Audrey Tropchenko!000-0001-9812-7947]

ITMO University, Saint Petersburg, 197101, Russian Federation bandoanOitmo.ru, aatropchenkoSitmo.ru

Abstract. For the higher coding performance than the previous video coding standards, High-Efficiency Video Coding (HEVC) adopts an intra prediction method with 35 modes, which requires heavy computational complexity. Intending to reduce this complexity, we analyzed the role of modes and proposed a scheme that contains two rough mode decision (RMD) processes with a customized set of modes to be tested in the first stage. The second stage of the RMD is calculated for a maximum of 4 modes. As compared to the default encoding scheme in HEVC test model HM-16.20, experimental results show that the proposed method reduces encoding time up to 22.74% with negligible loss of coding efficiency.

Keywords: HEVC/H.265 • Video compression • Intra prediction • Mode decision • Rate-distortion optimization.

o

(M

M

0) a

a

o

CT. LO

1 Introduction

^ In recent years, there has been a growing interest in services related to the

transmission and storage of high and ultrahigh definition videos. The video coding standard H.264/Advanced Video Coding (AVC) [1] published in 2003 has been unable to meet those requirements and the introduction of the HEVC [2] video coding standard as one of the solutions to the problem. ^ Mainly due to the new coding tools and the flexible data structures, HEVC

provides a significant improvement in compression efficiency compared to its predecessors H.264, especially when operating on high-resolution video content [4, ^ 3]. Similar to older video compression technologies, HEVC is based on a hy-

^ brid scheme of coding image blocks, which uses intra- and inter-frame prediction

> coding together with transform coding of residual data.

HEVC contains several elements improving the efficiency of intra prediction over earlier solutions. HEVC design supports a total of 35 intra prediction ^ modes, including Planar, DC and 33 angular modes, as presented in Figure f,

which contribute to representing different texture and object edge direction more precisely [5]. Due to the significantly increased number of intra modes, more techniques are required to efficiently encode the mode, one of which is to divide the frame into segments called coding units (CU), prediction units (PU), and transformation units (TU). The encoder needs to try all the combinations of

Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

CU, PU, and TU in the rate-distortion optimization (RDO) process to find the best mode with the lowest rate-distortion (RD) cost [5]. Such a process is very time-consuming.

Fig. 1. Intra prediction modes in HEVC

While an increase in the number of intra prediction modes can provide substantial performance gains, it also makes the RDO process more complex. To reduce the computational load of intra prediction, the official HM software [6] uses a fast encoding algorithm [5, 7,10] with two phases through a combination of RMD and RDO process. First, all 35 modes are evaluated with respect to a cost function. N modes with minimum cost Jsatd are then selected as the most promising candidate modes.

JSATD = SATD + Xpred X Rpred (1)

where SATD represents the absolute sum of Hadamard transformed residual signal for a PU. Xpred is a Lagrange multiplier, and Rpred represents the number of bits for the prediction mode. The number N is varied depending on the PU

size. The N is set to {8, 8, 3, 3, 3} for 4 X 4, 8 X 8, 16 X 16, 32 X 32, and 64 X 64 PU, respectively.

In the second step, three most probable modes (MPM), which are derived from the intra modes of the left and top neighboring PUs [5], are added to the list of candidates [8, 9]. The full RD costs with the reconstructed residual signal used for the actual encoding process are compared among those (N + 3) modes, and the prediction mode with the minimum RD cost is selected as the final prediction mode. The RD cost (Jrdo) for each intra mode is computed by:

JrDO — SSE + Xpred X Rtotal (2)

where SSE represents the sum of the squared errors between the original CU and the reconstructed CU. Rtotai is the total number of bits used for encoding with this mode.

In this way, the RDO process has to check only a maximum of 11 modes instead of all 35, and so the computational load can be reduced. However, the complexity is still high, since, in the RMD step all the 35 modes need to perform the cost calculation, the number of modes for RDO is still large. In this paper, a fast intra mode decision is proposed to further reduce the complexity of HEVC intra coding while maintaining the RD performance.

2 Analysis mode selection probability

Theoretically, 35 intra modes play the same role and their probability of choice is equal. However, the results of analyzing some videos of various categories have given a different perspective. To perform the statistical analyses of frequently chosen modes, HEVC reference software HM-16.20 was used to encode a set of video sequences of different classes and resolutions. Statistical results for test sequences in class B and the sequence "PeopleOnStreet" are shown in tables 1 and 2 with the four most frequent modes are represented in bold.

Table 1. Average distribution of intra prediction modes for B-class test sequences.

Mode Frequency, % Mode Frequency, % Mode Frequency, %

Planar 23.31 12 1.95 24 2.02

DC 13.31 13 1.65 25 2.75

2 1.01 14 1.54 26 8.45

3 0.89 15 1.35 27 2.32