Cuantizare vectorială - Vector quantization

Cuantizarea vectorială ( VQ ) este o tehnică de cuantificare clasică din procesarea semnalului care permite modelarea funcțiilor densității probabilității prin distribuția vectorilor prototip. A fost inițial folosit pentru compresia datelor . Funcționează împărțind un set mare de puncte ( vectori ) în grupuri având aproximativ același număr de puncte cel mai apropiat de ele. Fiecare grup este reprezentat de punctul său de centroid , la fel ca în mijloacele k și alți algoritmi de grupare .

Proprietatea de potrivire a densității cuantificării vectoriale este puternică, în special pentru identificarea densității datelor mari și înalte. Deoarece punctele de date sunt reprezentate de indicele celui mai apropiat centroid al acestora, datele frecvente au erori reduse și date rare de eroare ridicată. Acesta este motivul pentru care VQ este potrivit pentru compresia de date cu pierderi . Poate fi folosit și pentru corectarea datelor cu pierderi și estimarea densității .

Cuantificarea vectorială se bazează pe paradigma de învățare competitivă , deci este strâns legată de modelul de auto-organizare a hărții și de modelele de codare rare utilizate în algoritmi de învățare profundă , cum ar fi autoencoder .

Instruire

Cel mai simplu algoritm de antrenament pentru cuantificarea vectorială este:

  1. Alegeți un punct de eșantionare la întâmplare
  2. Deplasați cel mai apropiat centru de vector de cuantificare către acest punct de eșantionare, cu o mică parte din distanță
  3. Repeta

Un algoritm mai sofisticat reduce distorsiunea în estimarea potrivirii densității și asigură utilizarea tuturor punctelor, incluzând un parametru de sensibilitate suplimentar:

  1. Creșteți sensibilitatea fiecărui centroid cu o cantitate mică
  2. Alegeți un punct de eșantionare la întâmplare
  3. Pentru fiecare centru de vector de cuantificare , să denotăm distanța lui și
  4. Găsiți centroidul pentru care este cel mai mic
  5. Deplasați-vă spre o mică parte din distanță
  6. Setați la zero
  7. Repeta

Este de dorit să se utilizeze un program de răcire pentru a produce convergență: a se vedea recoacere simulată . O altă metodă (mai simplă) este LBG care se bazează pe K-Means .

Algoritmul poate fi actualizat iterativ cu date „live”, mai degrabă decât prin alegerea punctelor aleatorii dintr-un set de date, dar acest lucru va introduce unele părtiniri dacă datele sunt corelate temporar pe mai multe eșantioane.

Aplicații

Cuantificarea vectorială este utilizată pentru comprimarea datelor cu pierderi, corectarea datelor cu pierderi, recunoașterea modelelor, estimarea densității și gruparea.

Corecția pierderilor de date sau predicția este utilizată pentru a recupera datele care lipsesc din anumite dimensiuni. Se face găsind cel mai apropiat grup cu dimensiunile de date disponibile, apoi prezicând rezultatul pe baza valorilor pentru dimensiunile lipsă, presupunând că acestea vor avea aceeași valoare ca centroul grupului.

Pentru estimarea densității , aria / volumul care este mai aproape de un anumit centroid decât de oricare altul este invers proporțională cu densitatea (datorită proprietății de potrivire a densității algoritmului).

Utilizare în compresia datelor

Cuantizarea vectorială, numită și „cuantificare bloc” sau „cuantificare potrivire model” este adesea utilizată în compresia de date cu pierderi . Funcționează prin codificarea valorilor dintr-un spațiu vectorial multidimensional într-un set finit de valori dintr-un subspațiu discret de dimensiune inferioară. Un vector cu spațiu mai mic necesită mai puțin spațiu de stocare, astfel încât datele sunt comprimate. Datorită proprietății de potrivire a densității cuantificării vectoriale, datele comprimate au erori care sunt invers proporționale cu densitatea.

Transformarea se face de obicei prin proiecție sau folosind un codbook . În unele cazuri, un codbook poate fi folosit și pentru a entropia codul valorii discrete în același pas, prin generarea unei valori codificate cu lungime variabilă codificată ca prefix ca ieșire.

Setul de niveluri de amplitudine discrete este cuantificat împreună, mai degrabă decât fiecare probă fiind cuantificată separat. Luați în considerare un vector k- dimensional al nivelurilor de amplitudine. Se comprimă alegând cel mai apropiat vector de potrivire dintr-un set de n- vectori dimensionali , cu n < k .

Toate combinațiile posibile ale vectorului n- dimensional formează spațiul vectorial de care aparțin toți vectorii cuantizați.

Numai indexul cuvântului de cod din codbook este trimis în locul valorilor cuantificate. Acest lucru conservă spațiul și obține o compresie mai mare.

Cuantificarea vectorilor gemeni (VQF) face parte din standardul MPEG-4 care se ocupă de cuantificarea vectorilor intercalate ponderate în domeniul timpului.

Codecuri video bazate pe cuantificarea vectorială

Utilizarea codecurilor video bazate pe cuantizarea vectorială a scăzut semnificativ în favoarea celor bazate pe predicția compensată de mișcare combinată cu codificarea transformării , de exemplu cele definite în standardele MPEG , deoarece complexitatea redusă a decodificării cuantizării vectoriale a devenit mai puțin relevantă.

Codecuri audio bazate pe cuantizarea vectorială

Se utilizează în recunoașterea modelelor

VQ a fost, de asemenea, utilizat în anii optzeci pentru recunoașterea vorbirii și a vorbitorilor . Recent, a fost folosit și pentru căutarea eficientă a vecinilor și pentru recunoașterea on-line a semnăturilor. În aplicațiile de recunoaștere a modelelor , este construit un codbook pentru fiecare clasă (fiecare clasă fiind un utilizator în aplicații biometrice) folosind vectori acustici ai acestui utilizator. În faza de testare, distorsiunea de cuantificare a unui semnal de testare este elaborată cu întregul set de manuale de coduri obținute în faza de antrenament. Codbook-ul care oferă cea mai mică distorsiune de cuantificare vectorială indică utilizatorul identificat.

Principalul avantaj al VQ în recunoașterea tiparelor este sarcina sa de calcul redusă în comparație cu alte tehnici, cum ar fi deformarea dinamică a timpului (DTW) și modelul ascuns Markov (HMM). Principalul dezavantaj în comparație cu DTW și HMM este că nu ține cont de evoluția temporală a semnalelor (vorbire, semnătură etc.) deoarece toți vectorii sunt amestecați. Pentru a depăși această problemă, a fost propusă o abordare cu coduri de mai multe secțiuni. Abordarea cu mai multe secțiuni constă în modelarea semnalului cu mai multe secțiuni (de exemplu, un codbook pentru partea inițială, altul pentru centru și un ultim codbook pentru partea finală).

Folosiți ca algoritm de grupare

Întrucât VQ caută centroizi ca puncte de densitate a probelor situate în apropiere, poate fi de asemenea utilizat direct ca metodă de grupare bazată pe prototip: fiecare centroid este apoi asociat cu un prototip. Prin obiectivul de a minimiza eroarea de cuantificare pătrată așteptată și introducerea unui câștig de învățare în scădere care îndeplinește condițiile Robbins-Monro, iterații multiple pe întregul set de date cu un număr concret, dar fix de prototipuri converge la soluția algoritmului de grupare a mijloacelor k într-un mod incremental. manieră.

Rețele contradictorii generative (GAN)

VQ a fost folosit pentru a cuantifica un strat de reprezentare a caracteristicilor în discriminatorul GAN-urilor. Tehnica cuantificării caracteristicilor (FQ) realizează potrivirea implicită a caracteristicilor. Îmbunătățește antrenamentul GAN ​​și oferă o performanță îmbunătățită pe o varietate de modele populare GAN: BigGAN pentru generarea de imagini, StyleGAN pentru sinteza feței și U-GAT-IT pentru traducerea nesupravegheată de la imagine la imagine.

Vezi si

O parte a acestui articol a fost inițial bazată pe material din Dicționarul gratuit de calcul online și este utilizată cu permisiunea conform GFDL.

Referințe

  1. ^ Dana H. Ballard (2000). O introducere în calculul natural . Apăsați MIT. p. 189. ISBN 978-0-262-02420-4.
  2. ^ „Bink video” . Cartea Înțelepciunii . 27.12.2009 . Adus 16-03-2013 .
  3. ^ Valin, JM. (Octombrie 2012). Cuantificare vectorială piramidă pentru codare video . IETF . ID draft-valin-videocodec-pvq-00 . Adus 17-12-2013 .
  4. ^ "Specificația Vorbis I" . Xiph.org. 09.03.2007 . Adus 09-03-2007 .
  5. ^ Burton, DK; Shore, JE; Buck, JT (1983). „O generalizare a recunoașterii cuvintelor izolate folosind cuantificarea vectorială”. Conferința internațională IEEE privind procesarea acustică a vorbirii și semnalului ICASSP . 8 : 1021-1024. doi : 10.1109 / ICASSP.1983.1171915 .
  6. ^ Soong, F .; A. Rosenberg; L. Rabiner; B. Juang (1985). „O abordare de cuantizare vectorială a recunoașterii difuzoarelor” . IEEE Proceedings International Conference on Acoustics, Speech and Signal Processing ICASSP . 1 : 387-390. doi : 10.1109 / ICASSP.1985.1168412 . S2CID  8970593 .
  7. ^ H. Jegou; M. Douze; C. Schmid (2011). „Cuantificarea produsului pentru cea mai apropiată căutare a vecinilor” (PDF) . Tranzacții IEEE privind analiza modelelor și inteligența mașinilor . 33 (1): 117-128. CiteSeerX  10.1.1.470.8573 . doi : 10.1109 / TPAMI.2010.57 . PMID  21088323 . S2CID  5850884 .
  8. ^ Faundez-Zanuy, Marcos (2007). „Recunoașterea semnăturii offline și on-line bazată pe VQ-DTW”. Recunoașterea tiparului . 40 (3): 981–992. doi : 10.1016 / j.patcog.2006.06.007 .
  9. ^ Faundez-Zanuy, Marcos; Juan Manuel Pascual-Gaspar (2011). „Recunoaștere eficientă a semnăturilor on-line bazată pe VQ cu mai multe secțiuni” . Analiza modelului și aplicații . 14 (1): 37-45. doi : 10.1007 / s10044-010-0176-8 . S2CID  24868914 .
  10. ^ Gray, RM (1984). „Cuantizare vectorială”. Revista IEEE ASSP . 1 (2): 4-29. doi : 10.1109 / massp.1984.1162229 .
  11. ^ Cuantificarea caracteristicilor îmbunătățește instruirea GAN https://arxiv.org/abs/2004.02088

linkuri externe