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

Векторное квантование (VQ) - это классический метод квантования из обработки сигналов, который позволяет моделировать функции плотности вероятности с помощью распределения прототипы векторов. Первоначально он использовался для сжатия данных. Он работает путем разделения большого набора точек (векторов ) на группы, имеющие примерно одинаковое количество ближайших к ним точек. Каждая группа представлена ​​своей точкой центроида, как в k-средних и некоторых других алгоритмах кластеризации.

Свойство согласования плотности векторного квантования является мощным, особенно для определения плотности больших и многомерных данных. Поскольку точки данных представлены индексом их ближайшего центроида, часто встречающиеся данные имеют низкую ошибку, а редкие данные - высокую ошибку. Вот почему VQ подходит для сжатия данных с потерями. Его также можно использовать для коррекции данных с потерями и оценки плотности.

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

• 1 Обучение
• 2 Приложения
  • 2.1 Использование в сжатие данных
  • 2.2 Видеокодеки на основе векторного квантования
  • 2.3 Аудиокодеки на основе векторного квантования
  • 2.4 Использование в распознавании образов
  • 2.5 Использование в качестве алгоритма кластеризации
  • 2.6 Генеративные состязательные сети (GAN)
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Простейший алгоритм обучения для векторного квантования:

1. Выбор произвольной точки выборки
2. Перемещение ближайший центроид вектора квантования к этой точке выборки, на небольшую часть расстояния
3. Повторить

Более сложный алгоритм уменьшает смещение в оценке согласования плотности n, и обеспечивает использование всех точек, включая дополнительный параметр чувствительности:

1. Увеличьте чувствительность каждого центроида $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$на небольшую величину
2. Выберите точку выборки $P\; \{\backslash \; displaystyle\; P\}$случайным образом
3. Для каждого центроида вектора квантования $ci\; \{\backslash \; displaystyle\; c\_\; \{i\}\}$, пусть $d\; (P,\; ci)\; \{\backslash \; displaystyle\; d\; (P,\; c\_\; \{i\})\}$обозначает расстояние $P\; \{\backslash \; displaystyle\; P\}$и $ci\; \{\backslash \; displaystyle\; c\_\; \{i\}\}$
4. Найдите центроид $ci\; \{\backslash \; displaystyle\; c\_\; \{i\}\}$, для которого $d\; (P,\; ci)\; -\; si\; \{\backslash \; displaystyle\; d\; (P,\; c\_\; \{i\})\; -\; s\_\; \{i\}\}$- наименьшее
5. Move $ci\; \{\backslash \; displaystyle\; c\_\; \{i\}\}$в направлении $P\; \{\backslash \; displaystyle\; P\}$на небольшую часть расстояния
6. Установите $si\; \{\backslash \; displaystyle\; s\_\; \{i\}\}$до нуля
7. Повторить

Желательно использовать график охлаждения для достижения сходимости: см. Имитация отжига. Другой (более простой) метод - LBG, который основан на K-средних.

. Алгоритм можно итеративно обновлять «живыми» данными, а не путем выбора случайных точек из набора данных, но это внесет некоторую систематическую ошибку, если данные коррелируют во времени по множеству выборок.

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

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

Для оценки плотности площадь / объем, которые ближе к определенному центроиду, чем к любому другому, обратно пропорциональны плотности (из-за свойства согласования плотности алгоритма).

Использование при сжатии данных

Векторное квантование, также называемое «блочным квантованием» или «квантованием по шаблону», часто используется в сжатии данных с потерями. Он работает путем кодирования значений из многомерного векторного пространства в конечный набор значений из дискретного подпространства более низкой размерности. Вектор с меньшим пространством требует меньше места для хранения, поэтому данные сжимаются. Из-за свойства согласования плотности векторного квантования сжатые данные имеют ошибки, обратно пропорциональные плотности.

Преобразование обычно выполняется с помощью проекции или с помощью кодовой книги. В некоторых случаях кодовая книга может также использоваться для энтропийного кода дискретного значения на том же этапе путем генерации закодированного с префиксом значения с переменной длиной кода в качестве его вывода.

Набор дискретных уровней амплитуды квантуется совместно, а не каждый отсчет квантуется отдельно. Рассмотрим k-мерный вектор $[x\; 1,\; x\; 2,...,\; x\; k]\; \{\backslash \; displaystyle\; [x\_\; \{1\},\; x\_\; \{2\},...,\; x\_\; \{k\}]\}$уровней амплитуды. Он сжимается путем выбора ближайшего совпадающего вектора из набора n-мерных векторов $[y\; 1,\; y\; 2,...,\; yn]\; \{\backslash \; displaystyle\; [y\_\; \{1\},\; y\_\; \{2\},...,\; y\_\; \{n\}]\}$, с n < k.

Все возможные комбинации n-мерного вектор $[y\; 1,\; y\; 2,...,\; yn]\; \{\backslash \; displaystyle\; [y\_\; \{1\},\; y\_\; \{2\},...,\; y\_\; \{n\}]\}$образуют векторное пространство, которому принадлежат все квантованные векторы.

Только индекс кодового слова в кодовой книге отправляется вместо квантованных значений. Это экономит место и обеспечивает большее сжатие.

Двойное векторное квантование (VQF) является частью стандарта MPEG-4, имеющего дело с взвешенным векторным квантованием с перемежением во временной области.

Видеокодеки на основе векторного квантования

• Видео Bink
• Cinepak
• Daala основано на преобразовании, но использует векторное квантование на преобразованных коэффициентах
• Digital Video Interactive : Производство - Видео уровня и видео в реальном времени
• Indeo
• Microsoft Video 1
• QuickTime : Apple Video (RPZA) и Графический кодек (SMC)
• Соренсон SVQ1 и SVQ3
• Формат Smacker video
• VQA, используемый во многих играх

Использование видеокодеков, основанных на векторном квантовании, значительно снизилось в пользу кодеков, основанных на прогнозирование с компенсацией движения в сочетании с кодированием с преобразованием, например те, которые определены в стандартах MPEG, поскольку низкая сложность декодирования векторного квантования стала менее актуальной.

Аудиокодеки на основе векторного квантования

• AMR-WB +
• CELP
• Codec 2
• DTS
• G.729
• iLBC
• Ogg Vorbis
• Opus основан на преобразовании, но использует векторное квантование преобразованных коэффициентов.
• TwinVQ

Использование в распознавании образов

VQ также использовался в восьмидесятые годы для распознавания речи и говорящего. В последнее время он также используется для эффективного поиска ближайшего соседа и распознавания подписи в режиме онлайн. В приложениях распознавания образов создается одна кодовая книга для каждого класса (каждый класс является пользователем в биометрических приложениях) с использованием акустических векторов этого пользователя. На этапе тестирования искажение квантования тестового сигнала обрабатывается со всем набором кодовых книг, полученных на этапе обучения. Кодовая книга, которая обеспечивает наименьшее искажение векторного квантования, указывает идентифицированного пользователя.

Основным преимуществом VQ в распознавании образов является его низкая вычислительная нагрузка по сравнению с другими методами, такими как динамическое преобразование времени (DTW) и скрытый марковский модель (HMM). Главный недостаток по сравнению с DTW и HMM заключается в том, что он не принимает во внимание временную эволюцию сигналов (речь, подпись и т. Д.), Потому что все векторы смешаны. Чтобы преодолеть эту проблему, был предложен подход с использованием многосекционной кодовой книги. Многосекционный подход состоит в моделировании сигнала с помощью нескольких секций (например, одна кодовая книга для начальной части, другая для центра и последняя кодовая книга для конечной части).

Использование в качестве алгоритма кластеризации

Поскольку VQ ищет центроиды в качестве точек плотности близлежащих лежащих образцов, его также можно напрямую использовать в качестве метода кластеризации на основе прототипа: каждый центроид затем связывается с один прототип. Стремясь минимизировать ожидаемую квадратичную ошибку квантования и вводя убывающий выигрыш в обучении, удовлетворяющий условиям Роббинса-Монро, несколько итераций по всему набору данных с конкретным, но фиксированным количеством прототипов сходятся к решению k-средних алгоритм кластеризации инкрементным способом.

Генеративные состязательные сети (GAN)

VQ использовался для квантования слоя представления признаков в дискриминаторе GAN. Метод квантования признаков (FQ) выполняет неявное сопоставление признаков. Он улучшает обучение GAN и обеспечивает повышенную производительность на различных популярных моделях GAN: BigGAN для генерации изображений, StyleGAN для синтеза лиц и U-GAT-IT для неконтролируемого преобразования изображения в изображение.

• Кодирование речи
• Ogg Vorbis
• Диаграмма Вороного
• Функция скорости-искажения
• Кластеризация данных
• Обучающее векторное квантование
• Центроидная мозаика Вороного
• Growing Neural Gas, похожая на нейронная сеть система для векторного квантования
• Сегментация изображения
• Алгоритм Ллойда
• Линде, Бузо, алгоритм Грея (LBG)
• Кластеризация K-средних
• Автоэнкодер
• Глубокое обучение

Часть этой статьи изначально была основана на материалах из Free On-line Dictionary of Computing и используется с разрешением в рамках GFDL.

1. ^Дана Х. Баллард (2000). Введение в естественные вычисления. MIT Press. п. 189. ISBN 978-0-262-02420-4.
2. ^"Бинк видео". Книга мудрости. 2009-12-27. Проверено 16 марта 2013 г.
3. ^Валин, Дж. М.. (Октябрь 2012 г.). Пирамидальное векторное квантование для кодирования видео. IETF. И-Д проект-валин-видеокодек-ПВК-00. Проверено 17 декабря 2013 г.
4. ^«Спецификация Vorbis I». Xiph.org. 2007-03-09. Проверено 9 марта 2007 г.
5. ^Burton, D.K.; Shore, J. E.; Бак, Дж. Т. (1983). «Обобщение распознавания отдельных слов с использованием векторного квантования». Международная конференция IEEE по акустике обработки речи и сигналов ICASSP. 8 : 1021–1024. doi : 10.1109 / ICASSP.1983.1171915.
6. ^Сунг, Ф.; А. Розенберг; Л. Рабинер; Б. Хуанг (1985). «Подход векторного квантования к распознаванию говорящего». Международная конференция IEEE Proceedings по акустике, обработке речи и сигналов ICASSP. 1 : 387–390. DOI : 10.1109 / ICASSP.1985.1168412. S2CID 8970593.
7. ^H. Джегоу; М. Дуз; К. Шмид (2011). «Квантование продукта для поиска ближайшего соседа» (PDF). IEEE Transactions по анализу шаблонов и машинному анализу. 33 (1): 117–128. CiteSeerX 10.1.1.470.8573. DOI : 10.1109 / TPAMI.2010.57. PMID 21088323. S2CID 5850884.
8. ^Фаундез-Зануй, Маркос (2007). «Распознавание подписи офлайн и онлайн на основе VQ-DTW». Распознавание образов. 40 (3): 981–992. doi : 10.1016 / j.patcog.2006.06.007.
9. ^Фаундез-Зануй, Маркос; Хуан Мануэль Паскуаль-Гаспар (2011). «Эффективное распознавание подписи в режиме онлайн на основе многосекционного VQ». Анализ шаблонов и приложения. 14 (1): 37–45. DOI : 10.1007 / s10044-010-0176-8. S2CID 24868914.
10. ^Грей, Р.М. (1984). «Векторное квантование». Журнал IEEE ASSP. 1 (2): 4–29. doi : 10.1109 / massp.1984.1162229.
11. ^Квантование функций улучшает обучение GAN https://arxiv.org/abs/2004.02088

• http: // www.data-compression.com/vq.html
• QccPack - Библиотека квантования, сжатия и кодирования (с открытым исходным кодом)
• Сжатие индексов VQ и скрытие информации с использованием гибридного индексного кодирования без потерь, Вен-Ян Чен и Вэнь-Цун Хуан