Vektorkvantálás

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Legyen [math]\underline{X}[/math] egy [math]d[/math] elemű forrásvektor [math]f(\underline{x})[/math] sűrűségfüggvénnyel. A [math]d[/math]-dimenziós vektorkvantáló a [math]Q(\underline{x})[/math] függvény, [math]\underline{x} \in \mathbb{R}^d[/math] bemenetet az [math]\underline{x_1}, \underline{x_2}, \ldots, \underline{x_N} \in \mathbb{R}^d[/math] vektorok egyikébe képzi le. A [math]\mathbb{B}_1, \ldots, \mathbb{B}_N[/math] tartományok diszjunktak és lefedik [math]\mathbb{R}^d[/math]-t.

Négyzetes torzítás

[math] D(Q)=\frac{1}{d}E\left\|\underline{X}-Q(\underline{X})\right\|^2=\frac{1}{d}\sum_{i=1}^{N}{\int_{x \in \mathbb{B}_i}\limits{\left\|\underline{x}-\underline{x}_i\right\|^2f(\underline{x})d\underline{x}}} [/math]

Optimális a kör/gömb/hipergömb lenne, ezzel viszont nem lehet hézagmentesen lefedni a teret.

Voronoi tartományok

A voronoi tartományok egy tetszőleges dimenziós metrikus (ahol a pontok távolsága értelmezve van) tér partícionálását adják a tér egy W diszkrét részhalmaza alapján. A részhalmaz minden w pontjához egy tartományt rendelünk úgy, hogy ebbe a tartományba a tér azon pontjai tartozzanak, amelyekhez W egyik másik pontja sincs közelebb, mint w.

Voronoi diagram

Optimális vektorkvantáló

Optimális vektorkvantáló kielégíti a következő feltételeket:

• [math]\mathbb{R}^d[/math] partíciója Dirichlet partíció, azaz tartományai Voronoi-tartományok:
  • [math] \mathbb{B}_i=\left\{\underline{x}: \left\|\underline{x}-\underline{x_i}\right\|\leq\left\|\underline{x}-\underline{x_j}\right\|, \forall j\neq i\right\} [/math]

• A kimeneti vektorok a tartományok súlypontjai:

[math] \underline{x_i} = argmin_{\underline{y}}{\int_{\mathbb{B}_i}{\left\|\underline{x}-\underline{y}\right\|^2f(\underline{x})d\underline{x}}} [/math]

A Linde-Buzo-Gray algoritmus:

Megjegyzés: a következő algotimus a LLoyd-Max algoritmushoz nagyon hasonló, annak sokdimenziós kiterjesztése.

• Vegyünk fel közelítést a kvantálási vektorokra.
  
• Optimalizáljuk a kvantálót a kvantálási vektorok szerint: határozzuk meg a tartományokat a Voronoi-tartományokra vonatkozó feltételnek megfelelően.
  
• Számítsuk ki a torzítást, ha az egy küszöbértéknél jobb, készen vagyunk.
  
• Optimalizáljuk a kvantálót az így kapott tartományokhoz, a súlypont feltétel szerint, és ugorjunk a 2. pontra.
  

Fa struktúrájú vektorkvantáló

[math]L=K^d[/math] kimeneti vektor körül a közel optimálisat egy [math]d[/math] mélységű [math]K[/math]-adfokú fával határozzuk meg. Így [math]K^d[/math] helyett [math]d\left\lceil \log{K} \right\rceil[/math] összehasonlítás szükséges.

Megjegyzés by zslevi:

Gyakorlatilag kiválasztunk egy dimenziót, amelyikhez egy kvantálót csinálunk, majd a kapott kvantálási intervallumokhoz külön-külön kvantálókat csinálunk a következő dimenzió szerint, és így tovább, amíg el nem fogynak a dimenziók. (A könyv ábráját érdemes megnézni, abból talán megvilágosodsz: 87. oldal)

Osztott vektorkvantálás

A forrásvektorokat független osztályokba soroljuk, és ezekhez külön vektorkvantálót tervezünk. (pl. képtömörítésnél az éleket tartalmazó ill. nem tartlamzó képpontok külön osztályt alkotnak.)

Többszintű vektorkvantálás

Több menet. Először egy durva közelítést állítunk elő, majd mindig az eredeti és az aktuális közti különbséget (a kvantálási hibát) kvantáljuk.