stringtranslate.com

Векторная квантизация

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

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

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

Обучение

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

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

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

  1. Увеличьте чувствительность каждого центроида на небольшую величину
  2. Выбрать точку выборки случайным образом
  3. Для каждого центра вектора квантования обозначим расстояние и
  4. Найдите центроид, для которого это наименьшее
  5. Двигайтесь в сторону на небольшую часть расстояния
  6. Установить на ноль
  7. Повторить

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

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

Приложения

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

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

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

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

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

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

Набор дискретных уровней амплитуды квантуется совместно, а не каждый образец квантуется отдельно. Рассмотрим k -мерный вектор уровней амплитуды. Он сжимается путем выбора ближайшего совпадающего вектора из набора n -мерных векторов , где n < k .

Все возможные комбинации n -мерного вектора образуют векторное пространство , которому принадлежат все квантованные векторы.

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Подтемы

Похожие темы

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

Ссылки

  1. ^ Дэна Х. Баллард (2000). Введение в естественные вычисления . MIT Press. стр. 189. ISBN 978-0-262-02420-4.
  2. ^ "Bink video". Книга Мудрости . 2009-12-27 . Получено 2013-03-16 .
  3. ^ Valin, JM. (Октябрь 2012). Пирамидально-векторное квантование для видеокодирования. IETF . Идентификатор draft-valin-videocodec-pvq-00 . Получено 17.12.2013 .См. также arXiv:1602.05209
  4. ^ "Спецификация Vorbis I". Xiph.org. 2007-03-09 . Получено 2007-03-09 .
  5. ^ Бертон, Д.К.; Шор, Дж.Э.; Бак, Дж.Т. (1983). «Обобщение распознавания изолированных слов с использованием векторного квантования». ICASSP '83. Международная конференция IEEE по акустике, речи и обработке сигналов . Том 8. С. 1021–1024. doi :10.1109/ICASSP.1983.1171915.
  6. ^ Soong, F.; A. Rosenberg; L. Rabiner; B. Juang (1985). «Векторный квантовый подход к распознаванию говорящего». ICASSP '85. Международная конференция IEEE по акустике, речи и обработке сигналов . Том 1. стр. 387–390. doi :10.1109/ICASSP.1985.1168412. S2CID  8970593.
  7. ^ H. Jegou; M. Douze; C. Schmid (2011). "Product Quantization for Nearest Neighbor Search" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 33 (1): 117–128. CiteSeerX 10.1.1.470.8573 . doi :10.1109/TPAMI.2010.57. PMID  21088323. S2CID  5850884. Архивировано (PDF) из оригинала 2011-12-17. 
  8. ^ Faundez-Zanuy, Marcos (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

Внешние ссылки