Принципы сжатия видеоинформации

Август 2, 2022

Главная
Информатика
Принципы сжатия видеоинформации

Содержание

2. Конвейер операций, используемый в алгоритме JPEG
3. Шаги преобразования 1 шаг. Преобразования цветового пространства в сигнал яркости Y и два цветоразностных сигнала U
4. 1 шаг. Преобразования цветового пространства в сигнал яркости Y и два цветоразностных сигнала U и V.
5. 2 шаг. Прореживание U и V данных цветности Прореживание U и V данных цветности. При прореживании
6. 3 шаг. Преобразование блоков изображения при помощи двухмерного ДКП Преобразование небольших блоков изображения при помощи двухмерного
7. 4 шаг. Операция квантования Матрица проходит операцию квантования, которая позволяет сократить разрядность коэффициентов. Это математически соответствует
8. 5 шаг. Матрица вытягивается в строку данных. Матрица после квантования вытягивается в строку данных так, что
9. 6 Шаг. Статистическое кодирование по методу Хаффмана Статистическое кодирование по методу Хаффмана, считается, что этот метод
10. Положительными сторонами алгоритма является то, что: Задается степень сжатия. Выходное цветное изображение может иметь 24 бита
12. Алгоритм Хаффмана Классический алгоритм Хаффмана. Алгоритм использует только частоту появления одинаковых байт в изображении. Сопоставляет символам
13. Определения Определение 1 Пусть задан алфавит ψ = {a1, ……ar}, состоящий из конечного числа букв. Конечную
14. Определение 2. Рассмотрим соответствие между буквами алфавита Y и некоторыми словами алфавита Ω: а1 -- В
15. Определение 3. Пусть слово В имеет вид В = В’B” (1.7) Тогда слово В’ называется началом
16. Схема S обладает свойством префикса, если для любых i и j (1 ≤ i, j ≤
17. Определение 5. Коды, определяемые схемой с lср = l*, называются кодами с минимальной избыточностью или кодами
18. Алгоритм построения схемы Шаг 1. Упорядочиваем все буквы входного алфавита в порядке убывания вероятности. Считаем все
19. Пример: Пусть у нас есть 4 буквы в алфавите Ψ = {а1, a r} (r =4),
20. Производя действия, соответствующие 2-му шагу, мы получаем псевдосимвол с вероятностью 0.26 (и приписываем 0 и 1
21. Характеристики классического алгоритма Хаффмана: Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты). Класс изображений: Практически
22. Векторное квантование Считается перспективным и используется в JPEG векторное квантование. Векторное квантование эффективно, когда требуемое число
24. Скачать презентацию

Слайд 2

Конвейер операций, используемый в алгоритме JPEG

Слайд 3

Шаги преобразования
1 шаг. Преобразования цветового пространства в сигнал яркости Y и

два цветоразностных сигнала U и V
Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить так:
Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу

Слайд 4

1 шаг. Преобразования цветового пространства в сигнал яркости Y и два

цветоразностных сигнала U и V.

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

Слайд 5

2 шаг. Прореживание U и V данных цветности
Прореживание U и V

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

Слайд 6

3 шаг. Преобразование блоков изображения при помощи двухмерного ДКП
Преобразование небольших

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

где

Слайд 7

4 шаг. Операция квантования
Матрица проходит операцию квантования, которая позволяет сократить разрядность

коэффициентов.
Это математически соответствует делению матрицы коэффициентов дискретного косинусного преобразования размерностью 8 х 8 на матрицу квантования также размерностью 8 х 8 .
матрица квантования q[u,v] (далее МК).
После квантования значения чисел в левом верхнем углу становятся значительно меньше , а ближе к правому нижнему углу становятся равными нулю. Именно в этой операции происходит основная и необратимая потеря информации.
Яркостная компонента квантуется обычно с большим числом разрядов, чем цветоразностные

Слайд 8

5 шаг. Матрица вытягивается в строку данных.
Матрица после квантования вытягивается

в строку данных так, что все последовательности нулей правого нижнего угла оказываются в конце строки.
В некоторых версиях информация о яркости и цвете кодируется так, что сохраняются только отличия между соседними блоками.
Переводим матрицу 8x8 в 64-элементный вектор при помощи “зигзаг”-сканирования, т.е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...
Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце — высоким.

Слайд 9

6 Шаг. Статистическое кодирование по методу Хаффмана
Статистическое кодирование по методу Хаффмана,

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

Слайд 10

Положительными сторонами алгоритма является то, что:
Задается степень сжатия.
Выходное цветное

изображение может иметь 24 бита на точку.
Отрицательными сторонами алгоритма является то, что:
При повышении степени сжатия изображение распадается на отдельные квадраты (8x8).
Проявляется эффект Гиббса.
Характеристики алгоритма JPEG:
Коэффициенты компрессии: 2-200 (Задается пользователем).
Класс изображений: Полноцветные 24 битные изображения, или изображения в градациях серого без резких переходов цветов (фотографии).
Симметричность: 1

Слайд 11

Слайд 12

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

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

Слайд 13

Определения
Определение 1
Пусть задан алфавит ψ = {a1, ……ar}, состоящий из

конечного числа букв. Конечную последовательность символов из ψ
А = а i1, ai2,…..ain (1.4)
Будем называть словом в алфавите ψ, а число n - длина слова А, длина слова обозначается как l (А).
Пусть задан алфавит Ώ, Ώ = {b1,….bq}. Через В обозначим слово в алфавите Ώ и через S(.Ώ) –множество непустых слов в алфавите Ώ.
Пусть S = S (ψ) множество всех непустых слов в алфавите ψ, S’ – некоторое подмножество множества S. Пусть задано отображение F, которое каждому слову А, А s(ψ) ставит в соответствие слово
В = F(A), B S(Ω) (1.5)
Слово В будем называть кодом сообщения А, а переход слова А к его коду- кодированием.

Слайд 14

Определение 2.
Рассмотрим соответствие между буквами алфавита Y и некоторыми словами алфавита

Ω:
а1 -- В 1;
а2 -- В 2;
_______ (1.6)
аr -- В r;
Это соответствие называют схемой и обозначают ∑ . Оно определяет кодирование следующим образом:
- каждому слову А = аi1, аi2,…, аin из S’(ψ) = s(ψ) ставится в соответствие слово В = Bi1, Bi2,…, Bin, называемым кодом слова А.
Слова B1,… Br называются элементарными кодами. Такой вид кодирования называется алфавитным кодированием.

Слайд 15

Определение 3.
Пусть слово В имеет вид
В = В’B” (1.7)
Тогда слово

В’ называется началом или префиксом слова В, а слово B” – концом слова B. При этом пустое слово L и само слово В считается началом и концом слова В.

Слайд 16

Схема S обладает свойством префикса,
если для любых i и j

(1 ≤ i, j ≤ r , i≠j) слово Вi не является префиксом слова Вj.
Теорема 1. Если схема ∑ обладает свойством префикса то алфавитное кодирование будет взаимно однозначным.
Предположим, что задан алфавит ψ ={a1,…,ar} (r > 1) и набор вероятностей p1,…,pr ( =1) появления символов a1,…,ar . Пусть далее, задан алфавит W, W = {b1,…,bq} где (q > 1).
Тогда можно построить целый ряд схем алфавитного кодирования.
a1 - B1
… (1.8)
ar - Br
обладающих свойством взаимной однозначности.
Для каждой схемы можно ввести среднюю длину l ср, определяемую как мат. ожидание длины элементарного кода:
lср = , = l (Bi) – длины слов (1.9)
Длина lср, показывает, во сколько раз увеличивается средняя длина при кодировании со схемой Σ
Можно показать, что lср достигает величины своего минимума l* на некоторой схеме Σ
и определена как
l* =

Определение 4.

Слайд 17

Определение 5.
Коды, определяемые схемой с lср = l*, называются кодами с

минимальной избыточностью или кодами Хаффмана. Коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании.
В нашем случае алфавит = {a1,…,ar} задает символы входного потока, а алфавит {0,1}, т.е. состоит всего из нуля и единицы.

Слайд 18

Алгоритм построения схемы
Шаг 1.
Упорядочиваем все буквы входного алфавита в порядке

убывания вероятности. Считаем все соответствующие слова Вi , из алфавита Ω = {0,1} пустыми.
Шаг 2.
Объедением два символа аir-1 и a ir с наименьшими вероятностями рir-1 и р ir в псевдосимвол а’ {аir-1, a ir} с вероятностью рir-1 + р ir. Дописываем 0 в начало слова Вir-1 (Вir-1 = 0, Вir-1) и 1 в начало слова Вir (Вir = 1, Вir).
Шаг 3.
Удаляем из списка упорядоченных символов аir-1 и a ir и заносим туда псевдосимвол а’ {аir-1, a ir}. Проводим шаг 2, добавляя при необходимости 1 или 0 до тех пор, пока в списке не останется один псевдосимвол.

Слайд 19

Пример:
Пусть у нас есть 4 буквы в алфавите Ψ =

{а1, a r} (r =4),
p1= 0.5; p2 = 0,24; p3 = 0,15; p4 = 0,11 ( ).

Процесс построения схемы можно представить так:

Слайд 20

Производя действия, соответствующие 2-му шагу, мы получаем псевдосимвол с вероятностью 0.26

(и приписываем 0 и 1 соответствующим словам). Повторяя же эти действия для измененного списка, мы получаем псевдосимвол с вероятностью 0.5. И, наконец, на последнем этапе мы получаем суммарную вероятность 1.
Для того, чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью p4, получим B4=101, для p3 получим B3=100, для p2 получим B2=11, для p1 получим B1=0. Что означает схему:
a1 — 0,
a2 — 11
a3 — 100
a4 — 101
Эта схема представляет собой префиксный код, являющийся кодом Хаффмана. Самый часто встречающийся в потоке символ a1 мы будем кодировать самым коротким словом 0, а самый редко встречающийся a4 длинным словом 101.
Для последовательности из 100 символов, в которой символ a1 встретится 50 раз, символ a2 — 24 раза, символ a3 — 15 раз, а символ a4 — 11 раз, данный код позволит получить последовательность из 176 бит (). Т.е. в среднем мы потратим 1.76 бита на символ потока.

Слайд 21

Характеристики классического алгоритма Хаффмана:
Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший

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

Слайд 22

Векторное квантование
Считается перспективным и используется в JPEG векторное квантование.
Векторное квантование эффективно,

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

Принципы сжатия видеоинформации

Содержание

Конвейер операций, используемый в алгоритме JPEG

Шаги преобразования1 шаг. Преобразования цветового пространства в сигнал яркости Y и

1 шаг. Преобразования цветового пространства в сигнал яркости Y и два

2 шаг. Прореживание U и V данных цветности Прореживание U и V

3 шаг. Преобразование блоков изображения при помощи двухмерного ДКП Преобразование небольших

4 шаг. Операция квантованияМатрица проходит операцию квантования, которая позволяет сократить разрядность

5 шаг. Матрица вытягивается в строку данных. Матрица после квантования вытягивается

6 Шаг. Статистическое кодирование по методу ХаффманаСтатистическое кодирование по методу Хаффмана,

Положительными сторонами алгоритма является то, что: Задается степень сжатия. Выходное цветное

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

ОпределенияОпределение 1 Пусть задан алфавит ψ = {a1, ……ar}, состоящий из

Определение 2.Рассмотрим соответствие между буквами алфавита Y и некоторыми словами алфавита

Определение 3. Пусть слово В имеет вид В = В’B” (1.7) Тогда слово

Схема S обладает свойством префикса, если для любых i и j

Определение 5.Коды, определяемые схемой с lср = l*, называются кодами с

Алгоритм построения схемыШаг 1. Упорядочиваем все буквы входного алфавита в порядке

Пример: Пусть у нас есть 4 буквы в алфавите Ψ =