stringtranslate.com

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

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

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

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

Обучение

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

Набор дискретных уровней амплитуды квантуется совместно, а не каждый отсчет квантуется отдельно. Рассмотрим 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 для неконтролируемого перевода изображений в изображения.

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

Подтемы

похожие темы

Часть этой статьи изначально основана на материалах из Бесплатного онлайн-словаря по информатике и используется с разрешения GFDL.

Рекомендации

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

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