Скаларно и векторно квантуване
В тема 2 закръглихме всеки отчет поотделно – скаларно квантуване. При цвета това значи: червеното, зеленото и синьото се закръглят всяко за себе си. Но цветовете на папагала не са произволни: има много червено-оранжево, зелено от листата и почти никакво лилаво. Скаларното квантуване хаби нива за цветове, които ги няма.
Векторното квантуване (VQ) взима целия цвят (R, G, B) като един вектор и го заменя с най-близкия от предварително избран речник – кодова книга. Предава се само номерът. Ако книгата има L вектора, номерът е log₂L бита.
С 3 бита на пиксел скаларното квантуване дава PSNR = … dB, а палитра от 8 цвята – … dB.
При 3 бита скаларното дава 8 фиксирани мътни цвята, равномерно пръснати – повечето папагалът изобщо няма, и той става на сиво-червен плакат. Палитрата от 8 цвята е избрана от самата снимка – почти всичките отиват за червено-оранжевите нюанси. При 6 бита (64 цвята) VQ почти не се различава от оригинала. Така работи GIF.
Клетки на Вороной и LBG
Всеки кодов вектор „притежава“ точките, които са по-близо до него, отколкото до всеки друг – това е клетка на Вороной. Добрата книга има вектори там, където данните са гъсти.
Как се намира? С алгоритъма LBG (Linde–Buzo–Gray): започва с един вектор – средното на всички. Всеки вектор се разцепва на два и после се повтаря: (1) всяка точка отива при най-близкия вектор; (2) всеки вектор се мести в центроида (средното) на своите точки. Грешката пада при всяка стъпка.
корелация ρ = 0,9
Итерация 0 · 1,5 бит/отчет · DVQ = 0,129, Dскаларно ≈ 0,366
хоризонтално x₁, вертикално x₂ (−3,5…3,5, условни единици)
Точките са двойки съседни отчети; белите кръгчета – 8-те кодови вектора; цветните области – клетките. „▶ до сходимост“: векторите пълзят към центровете на групите си. Сравни с грешката на скаларното при същите битове. Намали ρ към 0 – облакът става кръгъл и предимството намалява.
Векторите от пиксели: блокове 2×2
VQ печели още повече, ако векторът е парче от снимката. Блок 2×2 пиксела е 12 числа (4 пиксела × 3 цвята). Книга от 6 бита = 64 блока значи 1,5 бита на пиксел вместо 24 – 16 пъти по-малко. PSNR = … dB.
С 64 блока (1,5 бита на пиксел, 16 пъти по-малко) папагалът се разпознава; ръбовете стават стъпаловидни, защото в книгата няма точно такъв блок. С 256 – почти незабележимо. Сметката отнема част от секундата – това е цената на VQ: кодирането (търсенето) е бавно, а декодирането е само четене от таблица.
Бързо търсене и сферично VQ
Пълното търсене сравнява всеки вектор с всичките L – бавно. Йерархичното подрежда книгата в дърво и търси само в един клон: при L = 256 и двоично дърво – 16 сравнения вместо 256 (понякога не намира абсолютно най-близкия).
Сферичното (shape/gain) VQ разделя вектора на сила g = ‖X‖ и форма S = X/g, с две малки книги. Един и същ ръб се среща с различна яркост – формата се пази веднъж. Пример: 16 нива на силата (4 бита) + 256 форми (8 бита) = 12 бита на блок; с обикновено VQ би трябвала книга от 4096 вектора.
Онлайн LBG (вектор по вектор): спечелилият вектор се мести с бягащо средно; близки вектори се сливат, празните класове се махат – от 25 начални остават например 8.
Самопроверка
1. Блок от 4 отчета, книга от 256 вектора. Колко бита на отчет?
log₂256 / 4 = 2 бита на отчет.
2. Защо VQ е по-добро от скаларното при еднакви битове?
Книгата следва данните (клетките се струпват където има точки), а скаларното хаби нива в празните ъгли – фигура 1: цветове, които папагалът няма.
3. Защо VQ кодирането е бавно, а декодирането – бързо?
Кодерът търси най-близкия от L вектора за всеки блок; декодерът само чете вектора по номера му.