Векторное квантование

Цель скалярного квантования - преобразование потока Л-битовм ментов, такое, чтобы в формируемом выходном потоке оставалось н-чем (заданное число) N значений.

Иллюстрация скалярного квантования, N=5, - навис. 1.4.

<_*__|_*__|_*__h_*_L^*_>

-4 -3-2-1 0 1 2 3 4

Рис. 1.4

Аналогично цель векторного квантования (Vector Quantization преобразование потока групп элементов (векторов), такое, чтобы в выходной поток записывался один из N векторов.

Иллюстрация векторного квантования для двумерного лучя - рис. 1.5.

Рис. 1.5. Иллюстрация векторного квантования для двух измеюенш 52

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

Основная идея состоит в том, чтобы каждый входной вектор X = {X_!iU Хм,---,Хц) заменять адресом (в код-книге) того код-вектора С = (Cjj, Cj^,... ..■,Cj,k), отклонение которого от входного, определяемое как D = (Х^-

- Cj,d²+(Xi3-Cj.2)²+- -HXijrCjjf . минимально.

Размер данных в результате применения VQ уменьшается, если данные соответствуют модели, либо если сжимаем с потерями.

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

Из краткого описания общей идеи видно, что

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

2. Задача метода может формулироваться двояко:

а) задан размер код-книги и требуется заполнять ее так, чтобы сум­
марное отклонение было минимальным;

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

3. Размеры элементов внутри Л-мерного вектора X могут быть разными.

4. В еще более сложном случае размеры N векторов разные: k_t, k₂,..., Аз, но одинаковы размеры элементов внутри этих N векторов переменной длины. И задача состоит в оптимальном разбиении входного потока на векторы.

Прямое преобразование

В простейшем случае - просто деление компонент вектора на заданные числа Я,-. Если компонента одна, а В,, = В = 4:

S[i]=S[i]/4;

Следующий по сложности вариант - поиск код-вектора (одномерного) в код-книге (массиве CodeBook размером CBSize, в котором код-векторы сортированы по возрастанию значений):

// найдем минимальный код-вектор

// со значением, большим S[i] for (cvector=0, step=CB_Size/2; step>0; step/=2) if (S[i]<CodeBook[cvector+step]) cvector+=step;

// определим, к нему или к

// предыдущему ближе кодируемый S[i] if ( (S[i]-CodeBook[cvector-l])<(CodeBook[cvector]-S[i]) ) cvector—;

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

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

Из Л₀-битовых элементов, применяя VQ, создаем Лгбитовые, являю­щиеся указателями на вектора-цвета (в таблице-палитре), причем

1) так, чтобы расхождение между исходным множеством S₀ и восста­новленным по палитре множеством Sj было минимально возможным;

2) Л,<Д₀.

В данном случае код-книга содержит палитру, а код-векторы есть индек­сы цветов в этой палитре. Степень сжатия будет равна Ro/R\. Например, ес­ли Л₀=24, /?i=8, то получаем сжатие в 3 раза.

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

Увеличение скорости сжатия

Если памяти достаточно, а размер входного блока существенно больше множества возможных значений векторов входного блока Х_ь имеет смысл заранее, при инициализации, создать таблицу, ставя в соответствие всевоз­можным X/ оптимальные для них (по критерию D) код-векторы.