Эффект сжатия

Главнов Владимир

Спецвыпуск: Хакер, номер #054, стр. 054-008-4

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

Продолжением каскадного поиска является многомасштабная компенсация движения (подробности - в книжке 2).

Квантователь

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

На сегодняшний день самыми популярными являются три вида квантователей:

1. однородный скалярный квантователь с мертвой зоной;

2. векторный квантователь со словарем;

3. сеточный квантователь.

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

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

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

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

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