Разработка и исследование методов повышения эффективности сжатия в современных видеокодеках тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Нгуен Ван Чыонг

• Нгуен Ван Чыонг
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Нгуен Ван Чыонг

Содержание

Список сокращений и условных обозначений

Введение

1 Анализ эффективности алгоритмов и методов кодирования в современном стандарте видеокодека H.265/HEVC

1.1 Описание принципа кодирования видеокодека H.265/HEVC

1.2 Особенности видеокодека H.265/HEVC

1.2.1 Особенности алгоритмов и методы кодирования видеокодека H.265/HEVC

1.2.2 Недостатки алгоритмов кодирования в современных видеокодеках и постановка задачи исследования

1.3 Выводы по разделу

2 Разработка и исследование алгоритмов блочного сопоставления для оценки движения при кодировании межкадровым предсказанием

2.1 Алгоритмы блочного сопоставления с фиксированным шаблоном

2.1.1 Определение алгоритмов блочного сопоставления

2.1.2 Субпиксельная точность

2.1.3 Анализ алгоритмов блочного сопоставления с фиксированным шаблоном

2.2 Алгоритмы блочного сопоставления с многосеточным шаблоном

2.2.1 Обзор алгоритмов блочного сопоставления с многосеточным шаблоном

2.2.2 Анализ алгоритмов блочного сопоставления с многосеточным шаблоном в H.265/HEVC

2.3 Выводы по разделу

3 Исследование и разработка алгоритмов устранения пространственной избыточности

3.1 Анализ алгоритмов внутрикадрового кодирования

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

3.3 Выводы по разделу

4 Разработка и исследование алгоритмов энтропийного кодирования

4.1 Исследование методов и алгоритмов энтропийного кодирования в современных стандартах видеокодеков

4.1.1 Метод CAVLC

4.1.2 Метод CABAC

4.2 Разработка алгоритма повышения эффективности энтропийного кодера видеокодека H.265/HEVC

4.3 Выводы по разделу

5 Модель видеокодека

5.1 Предложенная схема сжатия

5.1.1 Временная модель

5.1.2 Пространственная модель

5.1.3 Энтропийный кодер

5.2 Анализ полученных экспериментальных результатов

5.3 Выводы по разделу

Заключение

Список литературы

Приложение A Эксперимент на среде Матлаб

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

A.2 Программа для анализа алгоритмов интерполяции

A.3 Программа для анализа алгоритмов BMA с фиксированным шаблоном

основе блоков

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

A.6 Тестовые видеопоследовательности

Приложение B Эксперимент на среде разработки Visual C++

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

B.2 Тестовые видеопоследовательности '

Список сокращений и условных обозначений

Термины

AMVP

BD

BD-PSNR BD-rate

BMA CABAC

CAVLC

CB CDS

CSP

CTB

CTU

CU

DCT

DHaaT DHarT DS DST

В английском языке

Advanced Motion Vector Prediction

Bjontegaard Delta rate Bjontegaard Delta rate (PSNR) Bjontegaard Delta rate (bitrate)

Block Matching Algorithm Context-Adaptive Binary Arithmetic Coding Adaptive Variable-Length Coding

Coding Block Cross Diamond Search

Cross Search Pattern Coding Tree Block Coding Tree Unit Coding Unit

Discrete Cosine Transform

Discrete Haar Transform Discrete Hartley Transform Diamond Search Discrete Sine Transform

Русский перевод

Эффективное предсказание вектора движения

Метрика Бьёнтегарда Метрика Бьёнтегарда Метрика Бьёнтегарда (битрейт)

Алгоритм блочного сопоставления Контекстно-адаптивное двоичное арифметическое кодирование Контекстно-зависимое адаптивное кодирование с переменной длиной кодового слова Блок кодирования Поиск по перекрестно-ромбическому шаблону Перекрестный шаблон поиска Блок дерева кодирования Единица дерева кодирования Единица кодирования Дискретное косинусное преобразование

Дискретное преобразование Хаара Дискретное преобразование Хартли Поиск по ромбическому шаблону Дискретное синусное преобразование

DWT FS FSS FTZS

H.264/AVC

Discrete Wavelet Transform Full Search Four Step Search Fast Test Zone Search Advanced Video Coding

H.265/HEVC High Efficiency Video Coding

HARPS Hierarchical Adaptive Rood

Pattern Search HM HEVC Test Model

HS Hexagon-based Search

IP Integral Projection

LCU Largest Coding Unit

LDSP Large Diamond Search Pattern

LHSP Large Hexagon-based Search

Pattern

MAD Mean Absolute Difference

MBD Minimum Block Distortion

MC Motion Compensation

ME Motion Estimation

MP Mean Pyramid (Hierarchical Search)

MPM Most Possible Mode

MSD Mean Squared Differences

MV Motion vector

Дискретное вейвлет-преобразование Полный поиск Четырехэтапный поиск Быстрый поиск по тестовой зоне Расширенное кодирование видеоизображений Высокоэффективное кодирование видеоизображений Иерархический адаптивный поиск по шаблону

Эталонное программное

обеспечение НЕУС

Поиск по гексагональному шаблону

Интегральная проекция

Наибольший блок кодирования

Большой ромбический шаблон

поиска

Большой гексагональный шаблон поиска

Средняя абсолютная разность Наименьшая погрешность соответствия Компенсация движения Оценка движения Иерархический поиск

Режим наибольших вероятностей Средний квадрат разностей Вектор движения

NTSS New Three Step Search

PB Prediction Block

PDC Pel Difference Classification

PSNR Peak Signal to Noise Ratio

PU Prediction Unit

RD Rate-Distortion curve

RDOQ Rate-Distortion Optimized

Quantization

RQT Residual Quadtree Transform

RS Raster Search

SAD Sum of Absolute Differences

SDSP Small Diamond Search Pattern

SES Simple and Efficient Search

SHSP Small Hexagon-based Search Pattern

SS Square Search

SSD Sum of Squared Differences

SSIM Structure SIMilarity

TB Transform Block

TSS Three Step Search

TU Transform Unit

TZS Test Zone Search

WHT Walsh-Hadamard Transform

Новый трехэтапный поиск Блок предсказания Показатель разности пикселей Пиковое соотношение сигнал к шуму

Единица предсказания ЯС кривая

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

Просто-эффективный поиск Малый гексагональный шаблон поиска

Квадратичный поиск Сумма квадратов разностей Индекс структурного сходства Блок преобразования Трехэтапный поиск Единица преобразования Поиск по тестовой зоне Преобразование Уолша-Адамара

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

Введение

Актуальность проблемы. В настоящее время, разработчики могут использовать цифровое видео во многих мультимедийных приложениях. Цифровое кодирование данных играет большую роль в этом случае, поскольку оно обеспечивает необходимую степень сжатия данных, для передачи и хранения цифрового видео в доступных объемах памяти и сетях. Тем не менее, с появлением высокого и сверхвысокого разрешения видеопоследовательностей в технологии захвата и отображения видеоданных, стандарт кодирования видео H.264/AVC (англ. Advanced Video Coding) не обеспечивает требуемой степени сжатия, необходимой для их передачи и хранения существующими аппаратными средствами. Это привело к необходимости создания новых методов кодирования. В ответ на эти потребности, органы ITU-T VCEG и ISO/IEC MPEG начали новый проект по стандартизации видеокодирования под названием «Высокоэффективное кодирование видеоизображений H.265/HEVC» (англ. High Efficiency Video Coding).

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

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

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

1. Исследование эффективности алгоритмов сопоставления блоков для оценки движения при межкадровом кодировании видеоданных.

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

3. Исследование методов и алгоритмов интерполяции для субпиксельной оценки движения.

4. Разработка метода кодирования опорных видеокадров внутрикадровым предсказанием на основе трехэтапной схемы.

5. Исследование методов энтропийного кодирования бинарных последовательностей в современных видеостандартах.

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

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

диссертации составляет обобщение постановки задачи, ее формализация, конструирование методов ее решения, проведение и анализ результатов экспериментов. В работе используются методы теории информации (RD-теория, метрика Бьёнтегарда и сокращение избыточности данных), теории цифровой обработки сигналов и теории интерполяции, а также методы теории вероятностей и математической статистики. Тем не менее, в рамках практической части была проведена программная реализация предложенных методов и алгоритмов сжатия с их последующим сравнением с существующими. Экспериментальные методы основывались на моделировании и реализации алгоритмов в средах Matlab и Visual C++.

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

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

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

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

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

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

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

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

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

1. Для снижения временной избыточности предлагается использовать метод на основе быстрого алгоритма построения траектории движущихся объектов на основе поиска по тестовой зоне (FTZS - Fast Test Zone Search).

2. Для сокращения искажений и устранения блокинг-эффекта предлагается применить метод субпиксельной оценки движения на основе интерполяционного метода (метод суперразрешения).

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

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

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

- 2-й Международной мультидисциплинарной научно-практической конференции, Москва (2015 г.).

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

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

- V Научно-практическая конференция с международным участием «Наука настоящего и будущего» Университета ЛЭТИ (2017 г.).

- I Всероссийской научной конференции «Информационные технологии в моделировании и управлении: подходы, методы, решения» Тольяттинского государственного университета (2017 г.).

- IV, V, VI, VII Всероссийских конгрессах молодых ученых (2015-2018

г.).

- XLIV и XLVII Научной и учебно-методической конференции НИУ

ИТМО (2015 г. и 2018 г.).

Публикации. Основные результаты диссертационного исследования опубликованы в 23-х научных публикациях: в том числе 6 статьей в изданиях из перечня ВАК [16-18, 20, 21, 24], в т.ч. 1 из перечня Scopus [20]; 2 - в изданиях из перечня Web of Science или Scopus [77, 100]; 1 охранный документ на результат интеллектуальной деятельности № 2018617191 от 20.06.2018 (Программа для ЭВМ); 11 - в материалах конференций и сборниках тезисов докладов [5-15] и 3 в других изданиях [23, 75, 76].

Личный вклад. Основные результаты, представленные в диссертации, получены лично автором. В статьях [16-18, 20, 21, 24, 77] постановка задач, редактирование текстов, постановка экспериментов делались совместно с научным руководителем, а эксперименты, их обработка и интерпретация выполнены автором. В статье [100] соавтор Тропченко А.Ю. обеспечивал проведение экспертных оценок точности и полноты извлечения терминов.

Структура и объем работы. Диссертация состоит из списка сокращений и условных обозначений, введения, пяти разделов, заключения, списка литературы и двух приложений. Основной объем диссертации составляет 123 страницы с 50 рисунками и 20 таблицами. Объем двух приложений - 37 страниц. Список литературы содержит 115 библиографических наименований.

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

В первом разделе исследуется состояние проблемы и работы в данной области, делается обзор эффективности методов и алгоритмов стандарта H.265, проводится сравнительный анализ между стандар^м H.265 его предшественником H.264. После анализа оформляется постановка задачи диссертационного исследования.

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

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

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

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

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

В приложениях содержится информация платформы, на которой проведены эксперименты; а также представлены программы для демонстрации предложенных методов сжатия.

1 Анализ эффективности алгоритмов и методов кодирования в современном стандарте видеокодека

H.265/HEVC

В данном разделе исследованы алгоритмы и методы кодирования, применяемые в современном стандарте H.265/HEVC [97], а также проводится сравнение с стандартом-предшественником H.264/AVC [104] с целью выявления недостатков и возможностей усовершенствования методов и алгоритмов стандарта H.265/HEVC.

1.1 Описание принципа кодирования видеокодека H.265/HEVC

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

HEVC выигрывает над предшественниками за счет применения единиц дерева кодирования (англ. Coding Tree Unit - CTU) больших размеров. Это было показано в экспериментах по PSNR (англ. Peak Signal to Noise Ratio) с помощью эталонного программного обеспечения HEVC HM-8.0 (англ. HEVC Test Model. Экспериментальные результаты на всех тестовых последовательностях показали, что при сравнении с размером 64x64 CTU скорость передачи данных HEVC увеличилась на 2.2% по сравнению с CTU размером 32x32 и на 11.0% по

сравнению с CTU размерности 16*16. В тестовых последовательностях класса A, где разрешение видео составляло 2560*1600, по сравнению с размером 64*64 CTU было показано, что скорость передачи данных HEVC увеличилась на 5.7% по сравнению с 32*32 CTU, и на 28.2% по сравнению с 16*16 CTU. Эксперименты доказали, что при больших размерах CTU эффективность кодирования повышается, а также вычислительные затраты снижаются, следовательно время кодирования уменьшается [80].

Основной профиль HEVC сравнивался по эффективности кодирования с профилем H.264 / MPEG-4 AVC High, расширенным простым профилем MPEG-4, высокочастотным профилем H.263 (HLP) и H.262 / Основной профиль MPEG-2. Видеокодирование было выполнено с помощью Эталонного программного обеспечения HM-8.0 HEVC для развлекательных приложений и двенадцати различных битрейтов на девяти тестовых видеопоследовательностях. Из девяти тестовых видеопоследовательностей пять в разрешении HD, а четыре - в разрешении WVGA (800 * 480). Снижение скорости передачи бит для HEVC на 35,4% по сравнению с H.264 / MPEG-4 AVC HP, 63,7% по сравнению с MPEG-4 ASP, 65,1% по сравнению с H.263 HLP , и 70,8% по сравнению с H.262 / MPEG-2 MP [80].

Блок основного управления кодированием

Рисунок 1.1 - Схема типового кодера НБУС

Как и предыдущие стандарты (начиная со стандарта Н.261), Н.265/НЕУС тоже применяет гибридный подход видеокодирования. Т.е. внутрикадровое и межкадровое кодирование потока видеоданных используются вместе для сжатия [13]. Основная задача остается прежней - устранить временную, пространственную, статистическую и перцептивную избыточности видеопоследовательности (рисунок 1.1). Временная модель стремится к устранению временной избыточности, а пространственная использует схожесть или подобие соседних сэмплов кадра при этом устраняет пространственную избыточность. Статистическая и перцептивная избыточность сокращаются соответственно энтропийным кодером и квантованием.

Для оценки качества стандарта видеокодеков разработаны многие метрики. Среди метрик оценки подобия блоков кадров выделяют [16, 82]:

1. Сумма абсолютных разностей SAD (Sum of Absolute Differences) или средняя абсолютная разность MAD (Mean Absolute Difference)

(1.1)

SAD = XZI I (i, j) - K (i, j)

i=1 j=1

1 n m

MAD = — XEII (i, j ) - K (i, j )

nm i=1 j=1

(1.2)

где I(i, j) и K(i, j) - яркости входного и восстановленного (выходного) видеокадра в точке (i, j), a n и m - размеры блока.

2. Сумма квадратов разностей SSD (Sum of Squared Differences) или средний квадрат разностей MSD (Mean Square Difference)

2 (1.3)

SSD = XZI I (i, j) - K (i, j )|2, i=1 j=1

1 " ™ (1.4)

MSD = — XZ I(i,j)-K(i, j)2,

nm i=1 j=1

3. Показатель разности пикселей PDC (Pel Difference Classification) [39], сравнивает каждый пиксель целевого блока с его копией в блоке-кандидате и классифицирует каждую пару пикселей как совпадающие или не совпадающие.

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

" ^ г /, , 4-, (1.5)

PDC = (|I(i, j) - K(i, j)| < t)] ,

i =1 j=1

где, ord(f) оценивается в 1, если f истинно, а 0 - в противном случае.

4. Интегральная проекция IP (Integral Projection) [63, 92], вычисляются путем суммирования значений пикселей из каждого столбца и каждой строки блока.

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

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

=1

j=i

SI ( j )-S к ( i, j )

i=1

i=1

n

+S

i=1

SI ( j )-S к ( i, j )

j =1 j =1

(1.6)

5. Пиковое соотношение сигнал к шуму PSNR максимизируется.

PSNR = 10log

10

MAX,2 MSD

(1.7)

где MAXj - это максимальное значение, принимаемое пикселем изображения. 6. Функция кросс - корреляции максимизируется [79].

R-1C-1

Ko 11=SS 'о (1, j X

i=0 j=0

' R

i + r--, j + c--

2

2

(1.8)

где r и c — параметры вектора движения, а R и C — параметры размеров

некоторой окрестности сущности прогноза.

7. Индекс структурного сходства SSIM (Structure SIMilarity) [102, 111]:

(2MxMy + c!)(2axv + C2) (1.9)

SS1M ( x, y ) =

<X 2 + My2 + C1)(ax 2 + ay 2 + C2)7

где ßx и цу - среднее x и y; ctx и <гу - дисперсия x и y; ^ - ковариация x и y; а c1 = (k1L )2и c2 =(k2 l)2- L: динамический диапазон пикселей (2(bits per pixel) -1), а k = 0.01 и k2 = 0.03.

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

В качестве критерия оценки степени сжатия видеопотоков служит зависимость количества искажений от степени сжатия видеопотоков (RD кривая

от англ. Rate-Distortion curve). В теории кодирования сигналов с потерями функция зависимости размера данных от искажений сигнала определяется следующим образом [108]:

R (D) = min Y (I; K), (1.10)

P(k|i ):Z (k|i) P(i) P(k|i) d (k|i)< D

где R(D) - искомая RD функция, I - исходный сигнал, K - декодированный сигнал, Y - полная информация, p - плотность вероятности сигнала, d -расстояние между исходным и декодированным сигналом в некоторой метрике.

В данной диссертационной работе под RD зависимостью понимается зависимость PSNR от битрейта. Битрейт является величиной необходимой для передачи (хранения) одной секунды воспроизведения видеопотока.

Кроме того, в работе была применена метрика Бьёнтегарда BD (англ. Bjontegaard Delta rate) [37]. Величина BD является оценкой средней относительной разницы битрейтов BD-rate (количество бит в секунду) или значений PSNR BD-PSNR, получаемых при кодировании видеоданных с использованием двух сравниваемых алгоритмов. Положительное значение BD-rate означает рост битовой скорости и, как следствие, снижение на ту же величину степени сжатия видеоданных. А положительное значение BD-PSNR означает рост PSNR и, как следствие, повышение на ту же величину степени сжатия видеоданных.

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

1.2 Особенности видеокодека H.265/HEVC

В данном разделе будут рассмотрены основные алгоритмы и методы, используемые современным видеокодеком H.265/HEVC. При этом выявлены его преимущества и недостатки для постановки задачи диссертационного исследования.

1.2.1 Особенности алгоритмов и методы кодирования видеокодека

H.265/HEVC

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

[97].

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

Алгоритм кодирования совместимый с HEVC, обычно выполняется следующим образом. Каждый кадр разделяется на блочные области, причем точное разделение блоков передается в декодер. Первый кадр видеопоследовательности (и первого кадра в каждой выбранной точке с произвольным доступом в видеопоследовательности) будет кодироваться только внутрикадровым предсказанием (это использует пространственно некоторое предсказание данных от области к области в пределах одного и того же кадра, но не имеет связи с другими кадрами). Для всех оставшихся кадров видеопоследовательности межкадровое предсказание обычно используется для большинства блоков. Процесс кодирования для межкадрового предсказания заключается в сборе информации о движении, содержащей выбранный опорный кадр, и вектор движения (англ. Motion Vector - MV), который будет применен для прогнозирования сэмплов каждого блока. Кодер и декодер генерируют идентичные сигналы прогнозирования интерпретации путем использования компенсации движения (англ. Motion Compensation - MC) с использованием данных разрешения MV и режима, которые передаются в виде побочной информации.

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

методов энтропийного кодирования и передаются вместе с информацией предсказания.

Декодер выполняет цикл, обратный по отношению к кодеру (Рисунок 1.1), при этом он генерирует предсказания идентичные тем, что были выполнены кодером для последующих данных. Поэтому коэффициенты квантованного преобразования строятся путем обратного масштабирования и затем преобразуются обратно для получения декодированного приближения остаточного сигнала. Затем к предсказанию добавляется остаток, и результат подается в один или два фильтра с обратной связью для сглаживания артефактов, вызванных блочной обработкой и квантованием. Окончательно восстанавливаемое изображение сохраняется в буфере декодированного изображения, который будет использоваться для предсказания последующих изображений. В общем, порядок кодирования или декодирования обработки изображений часто отличается от порядка, в котором они поступают от источника; что требует разграничения между порядком кодирования (то есть порядком битового потока) и порядком вывода (то есть порядком отображения) для декодера [2, 97].

В дальнейшем различные функции, связанные с гибридным кодированием видео с использованием НЕУС, выделяются следующим образом:

Рисунок 1.2 - Блок дерева кодирования и соответствующая ему древовидная

структура

Единица дерева кодирования CTU (англ. Coding Tree Unit) (Рисунок 1.2): Единицей кодирования в предыдущих стандартах был макроблок, содержащий 16 х 16 блоков образцов яркости и, в обычном случае выборки цвета 4: 2: 0, два соответствующих 8x8 блока образцов цветности; тогда как аналогичная структура в HEVC представляет собой блок дерева кодирования CTU, который имеет размер, выбранный кодером, и может быть больше, чем традиционный макроблок. CTU состоит из блоков дерева кодирования CTB (англ. Coding Tree Block) яркости и соответствующих CTB цветности и синтаксических элементов. Размер L х L яркостного CTB можно выбрать как L = 16, 32 или 64 образца, причем более крупные размеры обычно обеспечивают лучшее сжатие. Затем HEVC поддерживает разбиение CTB на более мелкие блоки с использованием древовидной структуры и сигнальной сигнализации, подобной квадранту [91].

Единица кодирования CU (англ. Coding Unit) и блок кодирования CB (англ. Coding Block): синтаксис квадранта CTU определяет размер и положение его CB яркости и CB цветности. Корень квадродерева связан с CTU. Следовательно, размер CTB яркости является самым большим поддерживаемым размером для CB яркости. Разделение CTU на СВ яркости и цветности сигнализируется совместно. Один CB яркости и обычно два CB цветности вместе с соответствующим синтаксисом образуют единицу кодирования CU. CTB может содержать только один CU или может быть разделен на несколько CU, и каждый CU имеет связанное разбиение на единицы предсказания (англ. Prediction Unit - PU) и единицы преобразования (англ. Transform Unit - TU).

M

M/2 x M

M X M

2

M2 x M4

M4 X M (лев) M4 X M (прав) M x ^ (вер) M x ^ (ниж) Рисунок 1.3 - Способы деления блоков предсказания

Единица предсказания и блок предсказания PB (англ. Prediction Block) (Рисунок 1.3): решение о том, следует ли кодировать область изображения с использованием межкадрового или внутрикадрового предсказаний, производится на уровне CU. Структура разделения PU имеет свой корень на уровне CU. В зависимости от решения основного типа предсказания, яркостные и цветные СВ могут затем быть дополнительно разделены по размеру и предсказаны из PB яркости и цветности. Стандарт HEVC поддерживает размеры PB от 64 х 64 до 4 х 4 семплов.

Единица преобразования и блок преобразования TB (англ. Transform Block): остаток предсказания кодируется с использованием блочных преобразований. Структура дерева TU имеет свой корень на уровне CU. Остаточность CB яркости может быть идентична TB яркости или может быть дополнительно разделена на более мелкие TB. То же самое относится к TB яркости. Для квадратного размера TB 4 х 4, 8 х 8, 16 х 16 и 32 х 32 определены целочисленные базовые функции, аналогичные функциям дискретного косинусного преобразования DCT (англ. Discrete Cosine Transform). Альтернативно, для преобразования 4 х 4 остатков предсказания при включении яркости, одно целое преобразование, полученное из

формы дискретного синусного преобразования DST (англ. Discrete Sine Transform).

Определение векторов движения MV (англ. Motion Vector): используется расширенное предсказание вектора движения AMVP (англ. Advanced Motion Vector Prediction), которое определяет кандидаты наибольших вероятностей в наборе данных из соседних блоков PU и опорных кадров. При выполнении может использоваться режим слияния ММ (англ. Merge Mode) для кодирования, позволяющий наследование MV из временных или пространственных соседних PB, а режим пропуска MS (англ. Mode Skip) используется в случае, когда нет необходимости кодировать остаток (режим MS позволяет достигнуть наибольшей степени сжатия блока CU)

Компенсация движения MC: для MV используется 1/4-пиксельная точность, а для интерполяции дробных позиций используются 1/7-пиксельные или 1/8-пиксельные фильтры (по сравнению с 1/6-пиксельными фильтрами, за которыми следует линейная интерполяция с 1/4-пиксельной точностью в H.264/AVC). Подобно H.264/AVC, используются эталонные кадры. Для каждого PB может быть передан один или два вектора движения, приводящий либо к однонаправленному, либо к двунаправленному кодированию, соответственно.

Внутрикадровое предсказание: декодированные сэмплы границ соседних блоков используются в качестве эталонных данных для внутрикадрового предсказания. Внутрикадровое предсказание включает в себя 35 режимов: 33 угловых режима, режим Planar и режим DC (Рисунок 1.4). Сначала режимы внутрикадрового предсказания выбираются, которые затем кодируются путем получения режимов наибольших вероятностей (англ. Most Probable Modes) [60] на основе ранее декодированных соседних PB.

Список литературы диссертационного исследования кандидат наук Нгуен Ван Чыонг, 2018 год

Список литературы

1. Архипцев С. В., Лукьянов Д. П. Сравнительный анализ методов видеокодирования стандартов ITU_T H.264_AVC/ MPEG_4 Part_10 и H.265 HEVC // T-COMM - Телекоммуникации и Транспорт. — 2014. — Т. 8. — № 1. — C. 15-19.

2. Дворкович В.П., Дворкович А.В., Грызов Г.Ю. Новые возможности стандарта видеокодирования HEVC // Цифровая Обработка Сигналов. — 2013. — № 3. — С. 2-8.

3. Красильников Н. Н. Цифровая обработка 2D- И 3D-изображений. — СПб.: БХВ-Петербург, 2011. — 608 с.

4. Крылов A.C. Математические методы решения биометрических задач. Лекция 1. Повышение разрешения изображений // Лаборатория математических методов обработки изображений. [Электронный ресурс]. URL: http://esyr.Org/wiki/images/a/a6/Imaging_Lecture_1.pdf (дата обращения: 24.04.2018).

5. Нгуен В.Ч. Анализ методов и алгоритмов кодирования в современном гибридном видеокодеке H.265/HEVC [Электронный ресурс]. URL: http://openbooks.ifmo.ru/ru/file/5424/5424.pdf (дата обращения: 15.05.2018).

6. Нгуен В. Ч. Адаптивный цело-пиксельный метод оценки движения с мультисеточным шаблоном [Электронный ресурс]. URL: http://openbooks.ifmo.ru/ru/file/4771/4771.pdf (дата обращения: 15.05.2018).

7. Нгуен В.Ч. Исследование алгоритмов сопоставления блоков для оценки движения в современных видеокодерах [Электронный ресурс]. URL: http://openbooks.ifmo.ru/ru/file/3006/3006.pdf (дата обращения: 15.05.2018).

8. Нгуен В.Ч. Современные алгоритмы сокращения временной избыточности видеоданных [Электронный ресурс]. URL: http://openbooks.ifmo.ru/ru/file/853/853.pdf (дата обращения: 15.05.2018).

9. Нгуен В.Ч. Исследование алгоритмов сопоставления блоков для оценки движения в современных видеокодерах // Сборник трудов V Всероссийского конгресса молодых ученых (Санкт-Петербург, 12-15 апреля 2016 г.). — 2016. — C. 55-59.

10. Нгуен В.Ч. Анализ метода кодирования опорных видеокадров внутрикадровым предсказанием в стандарте H.265/HEVC // Информационные технологии в моделировании и управлении: подходы, методы, решения: материалы I Всероссийской научной конференции (Тольятти, 12-14 декабря 2017г.). — 2017. — C. 187-191.

11. Нгуен В.Ч. Адаптивный цело-пиксельный метод оценки движения с мультисеточным шаблоном // Сборник трудов VI Всероссийского конгресса молодых ученых (Санкт-Петербург, 2017 г.). — 2017. — C. 154-156.

12. Нгуен В.Ч. Адаптивный алгоритм оценки движения в задачах сжатия видеоданных // Сборник материалов V научно-практической конференции с международным участием «Наука настоящего и будущего» для студентов, аспирантов и молодых ученых. — 2017. — C. 97-99.

13. Нгуен В.Ч. Анализ методов и алгоритмов кодирования в современном гибридном видеокодеке H.265/HEVC // Сборник трудов VI Всероссийского конгресса молодых ученых (Санкт-Петербург, 2017 г.). — 2017. — C. 151153.

14. Нгуен В.Ч., Доан Т.Б. Исследование блочных алгоритмов кодирования преобразованием в стандартах сжатия мультимедийных данных // Материалы 14-ой международной конференции «Телевидение: передача и обработка изображений». — 2017. — C. 194-197.

15. Нгуен В.Ч., Тропченко А.А. Методы и алгоритмы сокращения временной избыточности видеоданных // Сборник статьей II-ой Международной мультидисциплинарной научно-практической конференции «Актуальные проблемы науки ХХ1 века». — 2015. — Ч. 2. — C. 36-41.

16. Нгуен В.Ч., Тропченко А.А. Иерархический адаптивный алгоритм шаблонного поиска для оценки движения при анализе видеопоследовательности // Научно-технический вестник информационных технологий, механики и оптики. — 2016. — № 3 (16). — C. 474-481.

17. Нгуен В.Ч., Тропченко А.А. Быстрый алгоритм поиска по тестовой зоне для межкадрового кодирования // Научно-технический вестник информационных технологий, механики и оптики. — 2017. — № 3 (17). — C. 483-489.

18. Нгуен В.Ч., Тропченко А.А. Анализ методов интерполяции в задачах реконструкции изображений // Наука и Образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2017. — № 3. — C. 170-181.

19. Нгуен В.Ч., Тропченко А.А. Быстрый алгоритм поиска по тестовой зоне для межкадрового кодирования // Научно-технический вестник информационных технологий, механики и оптики. — 2017. — № 3 (17). — C. 483-489.

20. Нгуен В.Ч., Тропченко А.А. Повышение эффективности метода энтропийного кодирования в современных стандартах видеосжатия // Труды СПИИРАН. — 2018. — № 3 (58). — С. 111-127.

21. Нгуен В.Ч., Тропченко А.А., Бан Д.Т. Повышение эффективности метода

кодирования внутрикадровым предсказанием в стандарте H.265/HEVC // Научно-технический вестник информационных технологий, механики и оптики. — 2018. — № 2 (18). — C. 255-261.

22. Нгуен В.Ч., Тропченко А.А. Иерархический адаптивный алгоритм шаблонного поиска для оценки движения при анализе видеопоследовательности // Научно-технический вестник информационных технологий, механики и оптики. — 2016. — № 3 (16). — C. 474-481.

23. Нгуен В.Ч. Анализ и разработка методов и алгоритмов энтропийного кодирования. — Saarbrucken - Berlin - Leipzig, Deutchland: LAP LAMBERT Academic Publishing, 2017. — 52 c.

24. Нгуен В.Ч., Тропченко А.А. Повышение эффективности сжатия данных с помощью иерархического перечислительного кодирования // Известия высших учебных заведений. Приборостроение. — 2016. — № 12 (59). — C. 991-996.

25. Ричардсон Я. Видеокодирование. H.264 и MPEG-4 - стандарты нового поколения. — М.: Техносфера, 2005. — 368 с.

26. Akansu A. N., Haddad R. A. Multiresolution signal decomposition: transforms, subbands, and wavelets. — Academic Press, 2001. — 499 p.

27. Amirpour H., Mousavinia A., Shamsi N. Predictive Three Step Search (PTSS) algorithm for motion estimation IEEE. — 2013. — P. 48-52.

28. An-Chao Tsai [and etc.]. Intensity Gradient Technique for Efficient Intra-Prediction in H.264/AVC // IEEE Transactions on Circuits and Systems for Video Technology. — 2008. — Vol. 18, no. 5. — P. 694-698.

29. An-Chao Tsai [и др.]. Effective Subblock-Based and Pixel-Based Fast Direction Detections for H.264 Intra Prediction // IEEE Transactions on Circuits and Systems for Video Technology. — 2008. — Vol. 18, no. 7. — P. 975-982.

30. Artigas X. [and etc.]. The DISCOVER codec: architecture, techniques and evaluation // Picture Coding. — 2007. — Vol. 17, no. 9. — P. 1103-1120.

31. Auli-Llinas F. Context-Adaptive Binary Arithmetic Coding with Fixed-Length Codewords // IEEE Transactions on Multimedia. — 2015. — Vol. 17, no. 8. — P. 1385-1390.

32. Barry K. IP Video CCTV and H.264 [Электронный ресурс]. URL: http://www. securityworldmag. com/tech/tech_view. asp?idx=853 &part_code=010 060194&page=1 (дата обращения: 23.04.2018).

33. Belyaev E. [and etc.]. An Efficient Adaptive Binary Range Coder and Its VLSI Architecture // IEEE Transactions on Circuits and Systems for Video Technology. — 2015. — Vol. 25, no. 8. — P. 1435-1446.

34. Belyaev E., Turlikov A., Egiazarian K. An Efficient Adaptive Binary Arithmetic Coder With Low Memory Requirement // IEEE Journal of Selected Topics in Signal Processing. Special Issue on Video Coding: HEVC and beyond, 2013. — 2013. — Vol. 7, no. 6. — P. 1053-1061.

35. Bharanitharan K. [and etc.]. A Low Complexity Detection of Discrete Cross Differences for Fast H.264/AVC Intra Prediction // IEEE Transactions on Multimedia. — 2008. — Vol. 10, no. 7. — P. 1250-1260.

36. Biswas B., Mukherjee R., Chakrabarti I. An efficient VLSI architecture for motion estimation using new three step search algorithm // TENCON 2014 - 2014 IEEE Region 10 Conference. — 2014. — P. 1-5.

37. Bj0ntegaard G. Calculation of average PSNR differences between RD-curves // Technical Report VCEG-M33 - ITU-T SG16/Q6 - Austin, TX, USA [Электронный ресурс]. URL: http://wftp3.itu.int/av-arch/video-site/0104_Aus/VCEG-M3 3.doc/ (дата обращения: 11.05.2018).

38. Burger W., Burge M. Digital image processing: an algorithmic introduction using Java. — Springer, 2008. — 564 p.

39. Chan E. [and etc.]. Experiments on block-matching techniques for video coding // Multimedia Systems. — 1994. — № 5 (2). — P. 228-241.

40. Chan M. H., Yu Y. B., Constantinides A.G. Variable size block matching motion compensation with applications to video coding // IEE Proceedings I Communications, Speech and Vision. — 1990. — Vol. 137, no. 4. — P. 205-212.

41. Cheung C. -H., Po L. -M. Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation // IEEE Transactions on Multimedia. — 2005. — Vol. 7, no. 1. — C. 16-22.

42. Cheung C. K. Fast Motion Estimation Techniques for Video Compression // Master Thesis — 1998.

43. Ching-Yeh C. [and etc.]. Analysis and architecture design of variable block-size motion estimation for H.264/AVC // IEEE Transactions on Circuits and Systems I: Regular Papers. — 2006. — Vol. 53, no. 3. — P. 578-593.

44. Davisson L. D. Comments on «Sequence Time Coding for Data Compression» // Proceedings of the IEEE. — 1966. — Vol. 55, no. 12. — P. 2010-2011.

45. Dufaux F., Moscheni F. Motion estimation techniques for digital TV: a review and a new contribution // Proceedings of the IEEE. — 1995. — Vol. 83, no. 6. — P. 858-876.

46. Elyousfi A., Tamtaoui A., Bouyakhf E. H. Fast Mode Decision Algorithm for Intra prediction in H.264/AVC Video Coding // IJCSNS International Journal of Computer Science and Network Security. — 2007. — Vol. 7, no. 1. — P. 356-

47. Guifen T., Goto S. Content adaptive prediction unit size decision algorithm for HEVC intra coding // IEEE Picture Coding Symposium (PCS). — 2012. — P. 405-408.

48. Hao Z., Zhan M. Early termination schemes for fast intra mode decision in High Efficiency Video Coding // Circuits and Systems (ISCAS), 2013 IEEE International Symposium on. — 2013. — P. 45-48.

49. Hao Z., Zhan M. Fast Intra Mode Decision for High Efficiency Video Coding (HEVC) // IEEE Transactions on Circuits and Systems for Video Technology. — 2014. — Vol. 24, no. 4. — P. 660-668.

50. Hartley R. V. L. A More Symmetrical Fourier Analysis Applied to Transmission Problems // Proceedings of the IRE. — 1942. — Vol. 30, no. 3. — P. 144-150.

51. Helle P. [and etc.]. Block Merging for Quadtree-Based Partitioning in HEVC // IEEE Transactions on Circuits and Systems for Video Technology. — 2012. — Vol. 22, no. 12. — P. 1720-1731.

52. Heo J., Ho Y. -S. VLC table prediction for CAVLC in H.264/AVC using correlation, statistics, and structural characteristics of mode information // Telecommunication Systems. — 2013. — Vol. 52, no. 3. — P. 1633-1641.

53. Heo J., Oh K. -J., Ho Y. -S. An Efficient Table Prediction Scheme for CAVLC in H.264 [Электронный ресурс]. URL: https://pdfs.semanticscholar.org/a383/2912d3fbb463b4dde1d286c7f138226171ed .pdf (дата обращения: 15.03.2017).

54. Hsieh H., Andrews H. Cubic splines for image interpolation and digital filtering // IEEE Transactions on Acoustics, Speech, and Signal Processing. — 1978. — Vol. 26, no. 6. — P. 508-517.

55. Huanqiang Zeng, Kai-Kuang Ma, Canhui Cai. Hierarchical Intra Mode Decision for H.264/AVC // IEEE Transactions on Circuits and Systems for Video Technology. — 2010. — Vol. 20, no. 6. — P. 907-912.

56. Huffman D. A. A method for the construction of minimum-redundancy codes // Proc. IRE. — 1952. — Vol. 40, no. 9. — P. 1098-1101.

57. Iain R. H.264/AVC Context Adaptive Variable Length Coding [Электронный ресурс]. URL: https://www.vcodex. com/h264avc-context-adaptive-variable-length-coding/ (дата обращения: 15.03.2017).

58. Iain R. H.264 / MPEG-4 Part 10 White Paper. Context-Based Adaptive Arithmetic Coding.

59. ITU-T. Recommendation H.264 Series H: audiovisual and multimedia systems.

— 2003.

60. ITU-T. Recommendation H.265 High Efficiency Video Coding — 2015. — 609 P-

61. Jagiwala D. D., Shah P. S. N. Analysis of Block Matching Algorithms for Motion Estimation in H.264 Video CODEC // International Journal of Engineering Research and Applications (IJERA). — 2012. — Vol. 2, no. 6. — P. 1396-1401.

62. Keys R. G. Cubic Convolution Interpolation for Digital Image Processing // IEEE Transactions on Acoustics, Speech, and Signal Processing. — 1981. — Vol. 29, no. 6. — P. 1153-1160.

63. Kim J. -S., Park R. -H. A fast feature-based block matching algorithm using integral projections // IEEE Journal on Selected Areas in Communications. — 1992. — Vol. 10, no. 5. — P. 968-971.

64. Konrad J., Dubois E. Bayesian estimation of motion vector fields // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1992. — Vol. 14, no. 9. — P. 910-927.

65. Lai Y. -T., Tseng C. -F. Fast coding unit decision and mode selection for intraframe coding in high-efficiency video coding // IET Image Processing. — 2016.

— Vol. 10, no. 3. — P. 215-221.

66. Lainema J. [and etc.]. Intra Coding of the HEVC Standard // IEEE Transactions on Circuits and Systems for Video Technology. — 2012. — Vol. 22, no. 12. — P. 1792-1801.

67. Lap-Pui Chau, Xuan Jing. Efficient three-step search algorithm for block motion estimation in video coding // Acoustics, Speech, and Signal Processing, 2003. Proceedings. (ICASSP '03). 2003 IEEE International Conference on. — 2003. — P. 421-424.

68. Li X. [and etc.]. Fast motion estimation methods for HEVC // Broadband Multimedia Systems and Broadcasting (BMSB), 2014 IEEE International Symposium on. — 2014. — P. 1-4.

69. Li X. [and etc.]. Context-adaptive fast motion estimation of HEVC // Circuits and Systems (ISCAS), 2015 IEEE International Symposium on. — 2015. — P. 27842787.

70. Lu J., Liou M. L. A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation // IEEE Transactions on Circuits and Systems for Video Technology. — 997. — Vol. 7, no. 2. — P. 429-433.

71. Lu X. [and etc.]. Fast Intra Coding Implementation for High Efficiency Video Coding (HEVC) // Data Compression Conference (DCC), 2017. — 2017. — P. 201-210.

72. Lynch T. J. Sequence time coding for data compression // Proceedings of the IEEE. — 1966. — Vol. 54, no. 10. — P. 1490-1491.

73. Mallat S. G., Stéphane G., Peyré G. A wavelet tour of signal processing: the sparse way. — Academic Press, 2009. — 805 p.

74. Marpe D., Schwarz H., Wiegand T. Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard // IEEE Transactions on Circuits and Systems for Video Technology. — 2003. — Vol. 13, no. 7. — P. 620-636.

75. Nguyen V. T. Development of block matching algorithms for motion estimation. Part 2. — Saarbrucken - Berlin - Leipzig, Deutchland: LAP LAMBERT Academic Publishing, 2018. — 52 p.

76. Nguyen V. T. Development of block matching algorithms for motion estimation. Part 1. — Saarbrucken - Berlin - Leipzig, Deutchland: LAP LAMBERT Academic Publishing, 2018. — 56 p.

77. Nguyen V. T., Tropchenko A. A. Fast Multigrid Pattern Search for Motion Estimation in Hybrid Compression Systems // CEUR Workshop Proceedings. — 2017. — Vol. 1975. — P. 242-253.

78. Nie Y., Ma K. -K. Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation // IEEE Transactions on Image Processing. — 2002. — Vol. 11, no. 12. — P. 1442-1449.

79. Nosratinia A. Post-Processing of JPEG-2000 Images to Remove Compression Artifacts // IEEE Signal Processing Letters. — 2003. — Vol. 10, no. 10. — P. 296-299.

80. Ohm J. R. [and etc.]. Comparison of the coding efficiency of video coding standards-including high efficiency video coding (HEVC) // IEEE Transactions on Circuits and Systems for Video Technology. — 2012. — Vol. 22, no. 12. — P. 1669-1684.

81. Olivier R., Hanqiang C. Nearest Neighbor Value Interpolation // IJACSA) International Journal of Advanced Computer Science and Applications. — 2012. — Vol. 3, no. 4. — P. 1-6

82. Pan J. N., Shi Y. Q., Shu C. Q. Correlation-feedback technique in optical flow determination // IEEE Transactions on Image Processing. — 1998. — Vol. 7, no. 7. — P. 1061-1067.

83. Park S. C., Park M. K., Kang M. G. Super-Resolution Image Reconstruction: A Technical Overview // IEEE Signal Processing Magazine. — 2003. — Vol. 20, no. 3. — P. 21-36.

84. Piao Y., Min J., Chen J. Encoder improvement of unified intra prediction //

presented at the JCTVC-C042, Guangzhou, October 2010.

85. Po L. -M., Ma W. -C. A Novel Four-Step Search Algorithm for Fast Block Motion Estimation // IEEE Trans. Circuits Syst. Video Technol. — 1996. — Vol. 6, no. 3. — P. 313-317.

86. Purnachand N., Alves L. N., Navarro A. Fast Motion Estimation Algorithm for HEVC // Consumer Electronics - Berlin (ICCE-Berlin), 2012 IEEE International Conference on. — 2012. — P. 34-37.

87. Reoxiang Li, Bing Zeng, Liou M. L. A new three-step search algorithm for block motion estimation // IEEE Transactions on Circuits and Systems for Video Technology. — 1994. — Vol. 4, no. 4. — P. 438-442.

88. Ria, Yadav S. C. Mapping Three Step Search algorithm onto a systolic array processor in H.264 // Recent Advances in Information Technology (RAIT), 2016 3rd International Conference on. — 2016. — P. 561-563.

89. Rissanen J., Langdon G. G. Arithmetic Coding // IBM Journal of Research and Development. — 1979. — Vol. 23, no. 2. — P. 149-162.

90. Rissanen J. Generalized Kraft Inequality and Arithmetic Coding // IBM Journal of Research and Development. — 1976. — Vol. 20, no. 3. — P. 198-203.

91. Samet H. The Quadtree and Related Hierarchical Data Structures // ACM Computing Surveys. — 1984. — Vol. 16, no. 2. — P. 187-260.

92. Sauer K., Schwartz B. Efficient block motion estimation using integral projections // IEEE Transactions on Circuits and Systems for Video Technology. — 1996. — Vol. 6, no. 5. — P. 513-518.

93. Selesnick I. W., Baraniuk R. G., Kingsbury N.C. The dual-tree complex wavelet transform // IEEE Signal Processing Magazine. — 2005. — Vol. 22, no. 6. — P. 123-151.

94. Seth K. [and etc.]. A parallel architectural implementation of the New Three-Step Search algorithm for block motion estimation // VLSI Design, 2004. Proceedings. 17th International Conference on. — 2004. — P. 1071-1076.

95. Shen L. [and etc.]. An Effective CU Size Decision Method for HEVC Encoders // IEEE Transactions on Multimedia. — 2013. — Vol. 15, no. 2. — P. 465-470.

96. Siast J., Stankowski J., Domanski M. Hierarchical Fast Selection of Intraframe Prediction Mode in HEVC // INTL Journal of Electronics and Telecommunications. — 2016. — Vol. 62, no. 2. — P. 1-5.

97. Sullivan G. J. [and etc.]. Overview of the high efficiency video coding (HEVC) standard // IEEE Transactions on Circuits and Systems for Video Technology. — 2012. — Vol. 22, no. 12. — P. 1649-1668.

98. T. Koga [and etc.]. Motion compensated interframe coding for video conferencing // National Telecommunication. Conference. — 1981. — P. 5.3.15.3.5.

99. Tan Y. H. [and etc.]. On residual quad-tree coding in HEVC // Multimedia Signal Processing (MMSP), 2011 IEEE 13th International Workshop on. — 2011. — P. 1-4.

100. Tropchenko A. U., Tropchenko A. A., Nguyen V. T. Research of Block-Based Motion Estimation Methods for Video Compression // Tem Journal-Technology, Education, Management, Informatics. — 2016. — Vol. 5, no. 3. — P. 277-283.

101. Unser M. Spline: a perfect fit for signal and image processing // IEEE Signal Processing Magazine. — 1999. — Vol. 16, no. 6. — P. 22-38.

102. Wang Z. [and etc.]. Image Quality Assessment: From Error Visibility to Structural Similarity // IEEE Transactions on Image Processing. — 2004. — Vol. 13, no. 4. — P. 600-612.

103. Welch T. A. A Technique for High-Performance Data Compression // IEEE Computer Society. — 1984. — Vol. 17, no. 6. — P. 8-19.

104. Wiegand T. Overview of the H.264/AVC video coding standard // IEEE Transactions on Circuits and Systems for Video Technology. — 2003. — Vol. 13, no. 7. — P. 560-576.

105. Yap S. Y., McCanny J. V. A VLSI Architecture for Variable Block Size Video Motion Estimation // IEEE Transactions on Circuits and Systems II: Express Briefs. — 2004. — Vol. 51, no. 7. — P. 384-389.

106. Yarlagadda R. K. R., Hershey J. E. Hadamard Matrix Analysis and Synthesis. — Boston, MA: Springer US. — 1997.

107. Yi-Hsin Huang, Tao-Sheng Ou, Chen H. H. Fast Decision of Block Size, Prediction Mode, and Intra Block for H.264 Intra Prediction // IEEE Transactions on Circuits and Systems for Video Technology. — 2010. — Vol. 20, no. 8. — P. 1122-1132.

108. Yoo H. Closed-form least-squares technique for adaptive linear image interpolation // Electronics Letters. — 2007. — Vol. 43, no. 4. — P. 210-212

109. Zhongli He [and etc.]. An efficient VLSI architecture for new three-step search algorithm // Circuits and Systems, 1995., Proceedings., Proceedings of the 38th Midwest Symposium on. — 1995. — P. 1228-1231.

110. Zhou D., Shen X., Dong W. Image zooming using directional cubic convolution interpolation // IET Image Processing. — 2012. — Vol. 6, no. 6. — P. 627-634.

111. Zhou Wang, Bovik A. C. A universal image quality index // IEEE Signal

Processing Letters. — 2002. — Vol. 9, no. 3. — P. 81-84.

112. Zhu C. [and etc.]. A Novel Hexagon-based Search Algorithm for Fast Block Motion Estimation // Acoustics, Speech, and Signal Processing, 2001. Proceedings. (ICASSP '01). 2001 IEEE International Conference on. — 2001. — P. 1593-1596.

113. Zhu S., Ma K. -K. A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation // IEEE Transactions on Image Processing. — 2000. — Vol. 9, no. 2. — P. 287-290.

114. Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory. — 1977. — Vol. 23, no. 3. — P. 337-343.

115. ITU/ISO/IEC. HEVC software [Электронный ресурс]. URL: http s : //hevc. hhi. fraunho fer. de/svn/svn_HEVC S o ftware/tags/HM-16.0/ (дата обращения: 11.05.2018).

Приложение A Эксперимент на среде Матлаб

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

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

- Операционная система: Windows 10 Home Edition;

- Процессор: Intel (R) Core (TM) i5-4210U CPU @ 1,70 ГГц 2,40 ГГц;

- Оперативная память: 6,00 ГБ;

- Тип системы: 64-разрядная операционная система, процессор на базе процессоров

x64.

A.2 Программа для анализа алгоритмов интерполяции Главная программа (Файл main.m) % Этот файл программы для выполнения алгоритма Super-Resolution clc

clear variables close all dbstop if error

%% Подготовка изображения

file = '.\images\cameraman.bmp'; im = imread(file); im = rgb2gray(im); im = imresize(im, [ 256 256 ]); im = im2double(im);

%% Simulate the low-resolution images numlmages = 4; blurSigma = 1;

[ images offsets croppedOriginal ] = SynthDataset(im, numlmages, blurSigma);

%% Вычислить изображение с высоким разрешением

tic

[ lhs rhs ] = SREquations(images, offsets, blurSigma); K = sparse(1 : size(lhs, 2), 1 : size(lhs, 2), sum(lhs, 1));

initialGuess = K \ lhs' * rhs; % This is an 'average' image produced from the LR images.

HR = GradientDescent(lhs, rhs, initialGuess);

HR = reshape(HR, sqrt(numel(HR)), sqrt(numel(HR)));

toc

%% Визуализация результатов

ShowLRImages(images); figure;

subplot(2, 4, 1); tic

imco1 = imresize(croppedOriginal, 0.5); imc1 = imresize(imco1, 2, 'nearest'); toc

imshow(imc1); title('Nearest Neighbor');

subplot(2, 4, 2); tic

imco2 = imresize(croppedOriginal, 0.5); imc2 = imresize(imco2, 2, 'bilinear'); toc

imshow(imc2); title('Bilinear');

subplot(2, 4, 3); tic

imco3 = imresize(croppedOriginal, 0.5); imc3 = imresize(imco3, 2, 'bspline'); toc

imshow(imc3); title('Bspline');

subplot(2, 4, 4); tic

imco4 = imresize(croppedOriginal, 0.5); imc4 = imresize(imco4, 2, 'cubic'); toc

imshow(imc4); title('Bicubic');

subplot(2, 4, 5); tic

imco5 = imresize(croppedOriginal, 0.5); imc5 = imresize(imco5, 2, 'lanczos2'); toc

imshow(imc5); title('Lanczos2');

subplot(2, 4, 6); tic

imco6 = imresize(croppedOriginal, 0.5); imc6 = imresize(imco6, 2, 'lanczos3'); toc

imshow(imc6); title('Lanczos3');

subplot(2, 4, 7);

imshow(HR);

title('Super-Resolution');

subplot(2, 4, 8);

imshow(croppedOriginal);

title('Reference');

%% Вычисление значений PSNR

psnrl = imgPSNR(croppedOriginal,imc1,3); disp(psnrl);

psnr2 = imgPSNR(croppedOriginal,imc2,3); disp(psnr2);

psnr3 = imgPSNR(croppedOriginal,imc3,3); disp(psnr3);

psnr4 = imgPSNR(croppedOriginal,imc4,3); disp(psnr4);

psnr5 = imgPSNR(croppedOriginal,imc5,3); disp(psnr5);

psnr6 = imgPSNR(croppedOriginal,imc6,3); disp(psnr6);

psnr7 = imgPSNR(croppedOriginal,HR,3); disp(psnr7);

%% Вычислить среднеквадратичную ошибку реконструкции

mse = sum((HR(:) - croppedOriginal(:)) .* (HR(:) - croppedOriginal(:))) / numel(HR); fprintf(1, 'Reconstruction Mean-square error: %f\n', mse);

Файл функции создания уравнения с высоким разрешением (Файл SREquations.m)

% Создает линейные уравнения с высоким разрешением для данных. % Модель изображения, реализованная здесь, представляет собой % пространственный перевод -> размытие -> прореживание. % Граничные условия являются круглыми.

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

function [ lhs rhs ] = SREquations(images, offsets, blurSigma) lhs = D; rhs = [];

superSize = 2 * size(images{1}) + [ 1 1 ]; for i = 1 : numel(images) transMat = TransMat(superSize, offsets(i, :)); blurMat = BlurMat(superSize, blurSigma); decMat = DecMat(superSize);

curLhs = decMat * blurMat * transMat; curRhs = images{i}; lhs = [ lhs ; curLhs ]; rhs = [ rhs ; curRhs(:) ];

end

end

% Создать оператор перевода

function transMat = TransMat(superSize, offsets) transposeMat = TransposeMat(superSize); transMat = ... transposeMat * TransMatY(superSize, offsets(1)) ...

* transposeMat * TransMatY(superSize, offsets(2));

end

% Создать оператор перевода для оси Y изображения

function transMatX = TransMatY(superSize, offset) row1 = zeros(1, prod(superSize)); nzInd = floor(1 - offset) : ceil(1 - offset); filterValues = LinearKernel(1 - offset - nzInd); nzInd(nzInd < 1) = prod(superSize) - nzInd(nzInd < 1); row1(nzInd) = filterValues; col1 = zeros(1, prod(superSize)); col1(1) = row1(1); col1 (2) = row1(end); transMatX = sptoeplitz(col1, row1);

end

% Создать матрицу оператора перевода

function transposeMat = TransposeMat(superSize) [ row col ] = meshgrid(1 : superSize(1), 1 : superSize(2)); inputPixInd = sub2ind(superSize, row, col); outputPixInd = sub2ind(superSize, col, row);

transposeMat = sparse(outputPixInd, inputPixInd, ones(size(outputPixInd)));

end

% Создать оператор размытия

function blurMat = BlurMat(superSize, blurSigma) transposeMat = TransposeMat(superSize); blurMat = ...

transposeMat * BlurMatY(superSize, blurSigma) ...

* transposeMat * BlurMatY(superSize, blurSigma);

end

% Создать оператор размытия для оси Y изображения

function blurMatY = BlurMatY(superSize, blurSigma) blurKernel = GaussianKernel(-1 : 1, blurSigma); blurKernel = blurKernel ./ sum(blurKernel(:)); row1 = zeros(1, prod(superSize)); row1([ end 1 2 ] ) = blurKernel; col1 = zeros(1, prod(superSize));

col1(1) = row1(1); col1(2) = row1 (2); blurMatY = sptoeplitz(col1, row1); end

% Создать оператор прореживания

function decMat = DecMat(superSize) sampledSize = 0.5 * (superSize - 1);

[ outputRow outputCol ] = meshgrid(1 : sampledSize(1), 1 : sampledSize(2)); inputRow = 2 * outputRow; inputCol = 2 * outputCol;

inputInd = sub2ind(superSize, inputRow, inputCol); outputInd = sub2ind(sampledSize, outputRow, outputCol);

decMat = sparse(outputInd, inputInd, ones(numel(outputInd), 1), prod(sampledSize), prod(superSize)); end

Файл функции создания синтетического набора данных (Файл SynthDataset.m)

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

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

function [ images offsets croppedOriginal ] = SynthDataset(im, numlmages, blurSigma) padRatio = 0.2;

workingRowSub = round(0.5 * padRatio * size(im, 1)) : round((1 - 0.5 * padRatio) * size(im, 1)); workingColSub = round(0.5 * padRatio * size(im, 2)) : round((1 - 0.5 * padRatio) * size(im, 2));

croppedOriginal = im(workingRowSub, workingColSub);

offsets(1, :) = [ 0 0 ];

images{1} = im(workingRowSub, workingColSub);

for i = 2 : numlmages offsets(i, :) = 2 * rand - 1; offsetRowSub = workingRowSub - offsets(i, 2); offsetColSub = workingColSub - offsets(i, 1); [ x y ] = meshgrid(1 : size(im, 2), 1 : size(im, 1)); [ x2 y2 ] = meshgrid(offsetColSub, offsetRowSub); images{i} = interp2(x, y, im, x2, y2); end

blurKernel = fspecial('gaussian', 3, blurSigma);

for i = 1 : numlmages images{i} = conv2(images{i}, blurKernel, 'same');

curIm = images{i};

images{i} = curIm(2 : 2 : end - 1, 2 : 2 : end - 1); end end

Файл функции создания редкой матрицы Теплица (Файл sptoeplitz.m)

function T = sptoeplitz(col,row)

if nargin < 2 % symmetric case col(1) = conj(col(1)); row = col; col = conj(col); else

if col(1)~=row(1)

warning('MATLAB:sptoeplitz:DiagonalConflict',['First element of ' ... 'input column does not match first element of input row. ' ... '\n Column wins diagonal conflict.']) end end

% Размер результата

m = length(col(:)); n = length(row(:));

% Locate the nonzero diagonals

[ic,jc,sc] = find(col(:)); row(1) = 0; % not used [ir,jr,sr] = find(row(:));

% Использовать spdiags для конструкции d = [ ir-1; 1-ic ];

B = repmat( [ sr; sc ].', min(m,n),1 ); T = spdiags( B,d,m,n );

Файл функции отображения набора изображений с низким разрешением

(Файл ShowLRImages.m)

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

function ShowLRImages(images) numCols = ceil(sqrt(numel(images))); numRows = numCols;

for i = 1 : numRows for j = 1 : numCols imageInd = (i - 1) * numCols + j; subplot(numCols, numRows, imageInd); imshow(images{imageInd}); hold on;

title(sprintf('Low-Res Image No.%d', imageInd));

end end end

Файл функции ядра линейной интерполяции (Файл LinearKernel.m)

function y = LinearKernel(x) aboveThresh = abs(x) >= 1; y(aboveThresh) = 0;

y(~aboveThresh) = 1 - abs(x(~aboveThresh)); end

Файл функции реализации оптимизации градиентного спуска

(Файл GradientDescent.m)

% Реализация оптимизации градиентного спуска

function x = GradientDescent(lhs, rhs, initialGuess) maxIter = 100; iter = 0; eps = 0.01;

x = initialGuess; res = lhs' * (rhs - Ihs * x); mse = res' * res; mse0 = mse;

while (iter < maxIter && mse > epsA2 * mse0) res = lhs' * (rhs - lhs * x); x = x + res; mse = res' * res;

fprintf(1, 'Gradient Descent Iteration %d mean-square error %3.3f\n', iter, mse); iter = iter + 1; end

end

Файл функции ядра градиентного спуска (Файл GaussianKernel.m)

function y = GaussianKernel(x, sigma)

y = exp(-(xA2) ./ (2 * sigmaA2)); end

Файл функции вычисления PSNR (Файл imgPSNR.m) % Вычисляет PSNR изображения с компенсацией движения function psnr = imgPSNR(imgP, imgComp, n) [row col k] = size(imgP); err = 0;

for i = 1:row for j = 1:col

err = err + (imgP(i,j) - imgComp(i,j)^2; end end

mse = err / (row*col); psnr = 10*log10(n*n/mse);

A.3 Программа для анализа алгоритмов BMA с фиксированным шаблоном

Файл главной программы (Файл motionEstAnalysis.m)

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

clc

close all clear all

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

imageName = 'Tennis'; mbSize = 16; p = 7;

v = VideoReader(sprintf('%s.avi',imageName));

for i = 0:(v.NumberOfFrames - 3)

imgINumber = i; imgPNumber = i+2;

if imgINumber < 9

imgIFile = sprintf('./%s/00%djpg',imageName, imgINumber+1); elseif imgINumber < 100

imgIFile = sprintf('./%s/0%d.jpg',imageName, imgINumber+1); end

if imgPNumber < 9

imgPFile = sprintf('./%s/00%d.jpg',imageName, imgPNumber+1); elseif imgPNumber < 100

imgPFile = sprintf('./%s/0%dJpg',imageName, imgPNumber+1); end

imgI = double(imread(imgIFile)); imgP = double(imread(imgPFile)); imgI = imgI(:, :); imgP = imgP(:, :);

% Exhaustive Search

[motionVect, computations] = motionEstES(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); ESpsnr(i+1) = imgPSNR(imgP, imgComp, 255); EScomputations(i+1) = computations;

% Three Step Search

[motionVect,computations ] = motionEstTSS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize);

TSSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); TSScomputations(i+1) = computations;

% New Three Step Search

[motionVect,computations ] = motionEstNTSS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); NTSSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); NTSScomputations(i+1) = computations;

% Simple and Efficient Three Step Search [motionVect, computations] = motionEstSESTSS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); SESTSSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); SESTSScomputations(i+1) = computations;

% Four Step Search

[motionVect, computations] = motionEst4SS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); SS4psnr(i+1) = imgPSNR(imgP, imgComp, 255); SS4computations(i+1) = computations;

% Diamond Search

[motionVect, computations] = motionEstDS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); DSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); DScomputations(i+1) = computations;

%Cross Diamond Search

[motionVect,computations ] = motionEstCDS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); CDSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); CDScomputations(i+1) = computations;

% Hexagon Search

[motionVect, computations] = motionEstHS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); HSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); HScomputations(i+1) = computations;

% Adaptive Rood Patern Search

[motionVect, computations] = motionEstARPS(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); ARPSpsnr(i+1) = imgPSNR(imgP, imgComp, 255); ARPScomputations(i+1) = computations;

% Adaptive Rood Patern Search based MP imgl = imresize(imgI, 0.5); imgP = imresize(imgP, 0.5);

[motionVect, computations] = motionEstARPSMP(imgP,imgI,mbSize,p); imgComp = motionComp(imgI, motionVect, mbSize); ARPSMPpsnr(i+1) = imgPSNR(imgP, imgComp, 255);

ARPSMPcomputations(i+1) = computations;

disp(sum(ESpsnr)/(v.NumberOfFrames-2));

disp(sum(TSSpsnr)/(v.NumberOfFrames-2));

disp(sum(NTSSpsnr)/(v.NumberOfFrames-2));

disp(sum(SESTSSpsnr)/(v.NumberOfFrames-2));

disp(sum(sS4psnr)/(v.NumberOfFrames-2));

disp(sum(DSpsnr)/(v.NumberOfFrames-2));

disp(sum(CDSpsnr)/(v.NumberOfFrames-2));

disp(sum(HSpsnr)/(v.NumberOfFrames-2));

disp(sum(ARPSpsnr)/(v.NumberOfFrames-2));

disp(sum(ARPSMPpsnr)/(v.NumberOfFrames-2));

x = 1:(v.NumberOfFrames-2);

x,EScomputations, ...

figure(1);plot(x,TSScomputations, ...

x,NTSScomputations, ... x,SESTSScomputations, ... x,SS4computations, ... x,DScomputations, ... x,CDScomputations, ... x,HScomputations, ... x,ARPScomputations, ... x,ARPSMPcomputations);

figure(2);plot(x,ESpsnr, ... x,TSSpsnr, ...

x,NTSSpsnr, ... x,SESTSSpsnr, ...

x,SS4psnr, ... x,DSpsnr,... x,CDSpsnr, ... x,HSpsnr, ... x,ARPSpsnr,... x,ARPSMPpsnr);

save dsplots2 ESpsnr EScomputations TSSpsnr TSScomputations ... NTSSpsnr NTSScomputations SESTSSpsnr SESTSScomputations ... SS4psnr SS4computations DSpsnr DScomputations ... CDSpsnr CDScomputations HSpsnr HScomputations ... ARPSpsnr ARPScomputations ARPSMPpsnr ARPSMPcomputations

A.4 Программа для анализа алгоритмов кодирования преобразованием на

основе блоков

Файл главной программы (Файл main.m)

clc;

clear all;

set(0, 'RecursionLimit', 100000);

% открытие изоброжения

file = '.\images\lenna.bmp'; I = imread(file); I = im2double(I); [N M l] = size(I); figure(1); imshow(I);

R = I(:,:,1); G = I(:,:,2); B = I(:,:,3);

% RGB->YUV

Y = 0.299 * R + 0.587 * G + 0.114 * B;

U = -0.14713 * R - 0.28886 * G + 0.436 * B + 128;

V = 0.615 * R - 0.51499 * G - 0.10001 * B + 128;

% Выбор метода преобразования

i = 4; switch i

case 1 % Дискретное косинусное преобразование DCT T = sqrt(8)*dctmtx(8);

case 2 % Дискретное преобразование Хартли DHarT

T = [1 1 1 1 1 1 1 1;

1 sqrt(2) 1 0 -1 -sqrt(2) -1 0;

1 1 -1 -1 1 1 -1 -1;

1 0 -1 sqrt(2) -1 0 1 -sqrt(2);

1 -1 1 -1 1 -1 1 -1;

1 -sqrt(2) 1 0 -1 sqrt(2) -1 0;

1 -1 -1 1 1 -1 -1 1;

1 0 -1 -sqrt(2) -1 0 1 sqrt(2)];

case 3 % Дискретное преобразование Хаара DHaаT T = [ 1 1 1 1 1 1 1 1; 1 1 1 1 -1 -1 -1 -1; sqrt(2) sqrt(2) -sqrt(2) -sqrt(2) 0 0 0 0; 0 0 0 0 sqrt(2) sqrt(2) -sqrt(2) -sqrt(2); 2 -2 0 0 0 0 0 0; 0 0 2 -2 0 0 0 0;

0 0 0 0 2 -2 0 0; 0 0 0 0 0 0 2 -2];

case 4 % Преобразование Уолша-Адамара WHT T = [ 1 1 1 1 1 1 1 1; 1 -1 1 -1 1 -1 1 -1; 1 1 -1 -1 1 1 -1 -1; 1 -1 -1 1 1 -1 -1 1; 1 1 1 1 -1 -1 -1 -1; 1 -1 1 -1 -1 1 -1 1; 1 1 -1 -1 -1 -1 1 1; 1 -1 -1 1 -1 1 1 -1;];

end

dct = @(block_struct) (T * block_struct.data * T')/8; Y1 = blockproc(Y,[8 8],dct); U1 = blockproc(U,[8 8],dct); V1 = blockproc(V,[8 8],dct);

% Квантование

QP = 255/12;

Y2 = blockproc(Y1,[8 8],@(block_struct) round(QP .* block_struct.data)); U2 = blockproc(U1,[8 8],@(block_struct) round(QP .* block_struct.data)); V2 = blockproc(V1,[8 8],@(block_struct) round(QP .* block_struct.data));

% Переупорядочение: Zigzag

Y3 = blockproc(Y2,[8 8],@(block_struct) zigzag(block_struct.data)); U3 = blockproc(U2,[8 8],@(block_struct) zigzag(block_struct.data)); V3 = blockproc(V2,[8 8],@(block_struct) zigzag(block_struct.data));

% Матрица в последовательность

for i=1:(M*8) for j=1:(N/8) Y30((i-1)*(N/8)+j) = Y3(j,i); U30((i-1)*(N/8)+j) = U3(j,i); V30((i-1)*(N/8)+j) = V3(j,i); end end

% RLE

Y4 = rle(Y30); U4 = rle(U30); V4 = rle(V30);

% Энтропийное кодирование методом Хаффмана

[dicty codey] = huffman(Y4); [dictu codeu] = huffman(U4); [dictv codev] = huffman(V4);

% Энтропийное декодирование методом Хаффмана

Y4I = huffmandeco(codey, dicty); U4I = huffmandeco(codeu, dictu); V4I = huffmandeco(codev, dictv);

% Обратный RLE

Y30I = irle(Y4I); U30I = irle(U4I); V30I = irle(V4I);

% Последовательность в матрицу

for i=1:(M*8) for j=1:(N/8) Y3I (j,i) = Y30I((i-1)*(N/8)+j); U3I(j,i) = U30I((i-1)*(N/8)+j); V3I(j,i) = V30I((i-1)*(N/8)+j); end end

% Обратный zigzag

Y2I = blockproc(Y3I,[1 64],@(block_struct) izigzag(block_struct.data,8,8)); U2I = blockproc(u3I,[1 64],@(block_struct) izigzag(block_struct.data,8,8)); V2I = blockproc(V3I,[1 64],@(block_struct) izigzag(block_struct.data,8,8));

% Обратное квантование

Y1I = blockproc(Y2I,[8 8],@(block_struct) block_struct.data ./ QP); U1I = blockproc(U2I,[8 8],@(block_struct) block_struct.data ./ QP); V1I = blockproc(V2I,[8 8],@(block_struct) block_struct.data ./ QP);

% Обратный метод преобразования

invdct = @(block_struct) (T' * block_struct.data * T)/8; YI = blockproc(Y1I,[8 8],invdct); UI = blockproc(U1I,[8 8],invdct); VI = blockproc(V1I,[8 8],invdct);

% YUV->RGB

RI = YI + 1.13983 * (VI - 128);

GI = YI - 0.39465 * (UI - 128) - 0.58060 * (VI - 128);

BI = YI + 2.03211 * (UI - 128);

Ip(:,:,1) = RI; Ip(:,:,2) = GI; Ip(:,:,3) = BI; figure(2); imshow(Ip);

% Вычисление значения PSNR

msel = sum((I - Ip).*(I - Ip));

mse = sum(msel);

psnr = 10*log10(255*255/mse);

disp((6*psnr(1)+psnr(2)+psnr(3))/8);

Файл функции кодирования методом RLE (Файл RLE.m)

function Output=rle(Input) L=length(Input); j=1; k=1; i=1;

while i<2*L comp=1; for j=j:L if j==L

break end;

if Input(j)==Input(j+1)

comp=comp+1; else

break end; end;

Output(k+1)=comp;

Output(k)=Input(j);

if j==L && Input(j-1)==Input(j)

break end; i=i+1; k=k+2; j=j+1; if j==L if mod(L,2)==0 Output(k+1)=1; Output(k)=Input(j); else

Output(k+1)=1; Output(k)=Input(j); end;

break end; end;

Файл функции декодирования методом RLE (Файл IRLE.m)

function Output=irle(Input)

L=length(Input);

s=1;

k=1; i=1;

while i<=L while s<=Input(i+1) Output(k)=Input(i); s=s+1; k=k+1; end; i=i+2; s=1; end;

Файл функции zigzag (Файл zigzag.m)

function new = zigzag(im) t=0;

l=size(im);