De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

La cuantificación vectorial ( VQ ) es una técnica de cuantificación clásica del procesamiento de señales que permite modelar funciones de densidad de probabilidad mediante la distribución de vectores prototipo. Originalmente se usó para la compresión de datos . Funciona dividiendo un gran conjunto de puntos ( vectores ) en grupos que tienen aproximadamente el mismo número de puntos más cercanos a ellos. Cada grupo está representado por su punto centroide , como en k-medias y algunos otros algoritmos de agrupamiento .

La propiedad de coincidencia de densidad de la cuantificación vectorial es poderosa, especialmente para identificar la densidad de datos grandes y de alta dimensión. Dado que los puntos de datos están representados por el índice de su centroide más cercano, los datos que ocurren comúnmente tienen un error bajo y un error alto en los datos raros. Es por eso que VQ es adecuado para la compresión de datos con pérdida . También se puede utilizar para la corrección de datos con pérdida y la estimación de densidad .

La cuantificación vectorial se basa en el paradigma de aprendizaje competitivo , por lo que está estrechamente relacionada con el modelo de mapa autoorganizado y con los modelos de codificación dispersa utilizados en algoritmos de aprendizaje profundo como el autoencoder .

Entrenamiento [ editar ]

El algoritmo de entrenamiento más simple para la cuantificación vectorial es: [1]

  1. Elija un punto de muestra al azar
  2. Mueva el centroide del vector de cuantificación más cercano hacia este punto de muestra, en una pequeña fracción de la distancia
  3. Repetir

Un algoritmo más sofisticado reduce el sesgo en la estimación de coincidencia de densidad y asegura que se usen todos los puntos, al incluir un parámetro de sensibilidad adicional [ cita requerida ] :

  1. Aumente la sensibilidad de cada centroide en una pequeña cantidad
  2. Elija un punto de muestra al azar
  3. Para cada centroide de vector de cuantificación , denotemos la distancia de y
  4. Encuentra el centroide para el que es el más pequeño
  5. Muévase hacia una pequeña fracción de la distancia
  6. Poner a cero
  7. Repetir

Es deseable utilizar un programa de enfriamiento para producir convergencia: consulte Recocido simulado . Otro método (más simple) es LBG que se basa en K-Means .

El algoritmo se puede actualizar iterativamente con datos "en vivo", en lugar de seleccionar puntos aleatorios de un conjunto de datos, pero esto introducirá algún sesgo si los datos están correlacionados temporalmente en muchas muestras.

Aplicaciones [ editar ]

La cuantificación vectorial se utiliza para la compresión de datos con pérdida, corrección de datos con pérdida, reconocimiento de patrones, estimación de densidad y agrupamiento.

La corrección o predicción de datos con pérdida se utiliza para recuperar los datos que faltan en algunas dimensiones. Se hace encontrando el grupo más cercano con las dimensiones de datos disponibles, luego prediciendo el resultado basado en los valores de las dimensiones faltantes, asumiendo que tendrán el mismo valor que el centroide del grupo.

Para la estimación de densidad , el área / volumen que está más cerca de un centroide particular que de cualquier otro es inversamente proporcional a la densidad (debido a la propiedad de coincidencia de densidad del algoritmo).

Usar en compresión de datos [ editar ]

La cuantificación vectorial, también denominada "cuantificación de bloques" o "cuantificación de coincidencia de patrones" se utiliza a menudo en la compresión de datos con pérdida . Funciona codificando valores de un espacio vectorial multidimensional en un conjunto finito de valores de un subespacio discreto de menor dimensión. Un vector de menor espacio requiere menos espacio de almacenamiento, por lo que los datos se comprimen. Debido a la propiedad de coincidencia de densidad de la cuantificación vectorial, los datos comprimidos tienen errores que son inversamente proporcionales a la densidad.

La transformación generalmente se realiza mediante proyección o utilizando un libro de códigos . En algunos casos, también se puede usar un libro de códigos para codificar entropía el valor discreto en el mismo paso, generando un valor codificado de longitud variable codificado con prefijo como su salida.

El conjunto de niveles de amplitud discretos se cuantifica conjuntamente en lugar de cuantificar cada muestra por separado. Considere un vector k- dimensional de niveles de amplitud. Se comprime eligiendo el vector coincidente más cercano de un conjunto de vectores n- dimensionales , con n < k .

Todas las combinaciones posibles del vector n- dimensional forman el espacio vectorial al que pertenecen todos los vectores cuantificados.

Solo se envía el índice de la palabra de código en el libro de códigos en lugar de los valores cuantificados. Esto ahorra espacio y logra más compresión.

La cuantificación de vectores gemelos (VQF) es parte del estándar MPEG-4 que se ocupa de la cuantificación de vectores intercalados ponderados en el dominio del tiempo.

Códecs de video basados ​​en cuantificación vectorial [ editar ]

  • Bink video [2]
  • Cinepak
  • Daala se basa en transformadas pero utiliza la cuantificación vectorial piramidal en coeficientes transformados [3]
  • Video digital interactivo : video de nivel de producción y video en tiempo real
  • Indeo
  • Vídeo de Microsoft 1
  • QuickTime : Apple Video (RPZA) y códec de gráficos (SMC)
  • Sorenson SVQ1 y SVQ3
  • Video de Smacker
  • Formato VQA , utilizado en muchos juegos

El uso de códecs de video basados ​​en la cuantificación vectorial ha disminuido significativamente a favor de los basados ​​en la predicción compensada por movimiento combinada con la codificación de transformación , por ejemplo, los definidos en los estándares MPEG , ya que la baja complejidad de decodificación de la cuantificación vectorial se ha vuelto menos relevante.

Códecs de audio basados ​​en cuantificación vectorial [ editar ]

  • AMR-WB +
  • CELP
  • Códec 2
  • DTS
  • G.729
  • iLBC
  • Ogg Vorbis [4]
  • Opus está basado en transformaciones pero usa cuantificación vectorial piramidal en coeficientes transformados
  • TwinVQ

Usar en el reconocimiento de patrones [ editar ]

VQ también se utilizó en los años ochenta para el reconocimiento del habla [5] y del hablante . [6] Recientemente también se ha utilizado para la búsqueda eficiente del vecino más cercano [7] y el reconocimiento de firmas en línea. [8] En las aplicaciones de reconocimiento de patrones , se construye un libro de códigos para cada clase (cada clase es un usuario en aplicaciones biométricas) utilizando vectores acústicos de este usuario. En la fase de prueba, la distorsión de cuantificación de una señal de prueba se resuelve con todo el conjunto de libros de códigos obtenidos en la fase de entrenamiento. El libro de códigos que proporciona la distorsión de cuantificación vectorial más pequeña indica el usuario identificado.

La principal ventaja de VQ en el reconocimiento de patrones es su baja carga computacional en comparación con otras técnicas como la deformación de tiempo dinámica (DTW) y el modelo de Markov oculto (HMM). El principal inconveniente en comparación con DTW y HMM es que no tiene en cuenta la evolución temporal de las señales (voz, firma, etc.) porque todos los vectores están mezclados. Para superar este problema, se ha propuesto un enfoque de libro de códigos de múltiples secciones. [9] El enfoque de múltiples secciones consiste en modelar la señal con varias secciones (por ejemplo, un libro de códigos para la parte inicial, otro para el centro y un último libro de códigos para la parte final).

Usar como algoritmo de agrupamiento [ editar ]

Como VQ busca centroides como puntos de densidad de muestras cercanas, también se puede usar directamente como un método de agrupamiento basado en prototipos: cada centroide se asocia luego con un prototipo. Con el objetivo de minimizar el error de cuantificación al cuadrado esperado [10] e introducir una ganancia de aprendizaje decreciente que cumpla con las condiciones de Robbins-Monro, múltiples iteraciones sobre todo el conjunto de datos con un número concreto pero fijo de prototipos convergen a la solución del algoritmo de agrupamiento de k-medias de manera incremental.

Redes generativas antagónicas (GAN) [ editar ]

VQ se ha utilizado para cuantificar una capa de representación de características en el discriminador de GAN. La técnica de cuantificación de características (FQ) realiza una coincidencia de características implícita. [11] Mejora el entrenamiento GAN y produce un rendimiento mejorado en una variedad de modelos GAN populares: BigGAN para generación de imágenes, StyleGAN para síntesis facial y U-GAT-IT para traducción de imagen a imagen sin supervisión.

Ver también [ editar ]

  • Codificación de voz
  • Ogg Vorbis
  • Diagrama de Voronoi
  • Función de distorsión de velocidad
  • Agrupación de datos
  • Aprendizaje de la cuantificación de vectores
  • Teselado centroidal de Voronoi
  • Growing Neural Gas , un sistema similar a una red neuronal para la cuantificación de vectores
  • Segmentación de imagen
  • Algoritmo de Lloyd
  • Linde, Buzo, algoritmo de Gray (LBG)
  • Agrupación de K-medias
  • Autoencoder
  • Aprendizaje profundo

Parte de este artículo se basó originalmente en material del Free On-line Dictionary of Computing y se utiliza con permiso de la GFDL.

Referencias [ editar ]

  1. ^ Dana H. Ballard (2000). Introducción a la computación natural . MIT Press. pag. 189. ISBN 978-0-262-02420-4.
  2. ^ "Bink video" . Libro de la Sabiduría . 2009-12-27 . Consultado el 16 de marzo de 2013 .
  3. ^ Valin, JM. (Octubre 2012). Cuantización vectorial piramidal para codificación de video . IETF . Proyecto de identificación-valin-videocodec-pvq-00 . Consultado el 17 de diciembre de 2013 .
  4. ^ "Especificación de Vorbis I" . Xiph.org. 2007-03-09 . Consultado el 9 de marzo de 2007 .
  5. ^ Burton, DK; Shore, JE; Buck, JT (1983). "Una generalización del reconocimiento de palabras aisladas mediante cuantificación vectorial". IEEE International Conference on Acustics Speech and Signal Processing ICASSP . 8 : 1021-1024. doi : 10.1109 / ICASSP.1983.1171915 .
  6. ^ Soong, F .; A. Rosenberg; L. Rabiner; B. Juang (1985). "Un enfoque de cuantificación vectorial para el reconocimiento de hablantes" . IEEE Proceedings International Conference on Acustics, Speech and Signal Processing ICASSP . 1 : 387–390. doi : 10.1109 / ICASSP.1985.1168412 . S2CID 8970593 . 
  7. ^ H. Jegou; M. Douze; C. Schmid (2011). "Cuantización de productos para la búsqueda de vecinos más cercanos" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 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). "Reconocimiento de firmas offline y online basado en VQ-DTW". Reconocimiento de patrones . 40 (3): 981–992. doi : 10.1016 / j.patcog.2006.06.007 .
  9. Faundez-Zanuy, Marcos; Juan Manuel Pascual-Gaspar (2011). "Reconocimiento de firmas en línea eficiente basado en VQ de múltiples secciones" . Análisis de patrones y aplicaciones . 14 (1): 37–45. doi : 10.1007 / s10044-010-0176-8 . S2CID 24868914 . 
  10. ^ Gray, RM (1984). "Cuantización vectorial". Revista IEEE ASSP . 1 (2): 4–29. doi : 10.1109 / massp.1984.1162229 .
  11. ^ La cuantificación de funciones mejora el entrenamiento de GAN https://arxiv.org/abs/2004.02088

Enlaces externos [ editar ]

  • http://www.data-compression.com/vq.html
  • QccPack: biblioteca de cuantificación, compresión y codificación (código abierto)
  • Compresión de índices VQ y ocultación de información mediante codificación de índices híbrida sin pérdida , Wen-Jan Chen y Wen-Tsung Huang