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

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

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

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

Обучение

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

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

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

Увеличьте чувствительность каждого центроида $s_{i}$ на небольшую сумму
Выберите точку отбора проб $P$ наугад
Для каждого центроида вектора квантования $c_{i}$ , позволять $d(P,c_{i})$ обозначаем расстояние $P$ и $c_{i}$
Найдите центроид $c_{i}$ для чего $d(P,c_{i})-s_{i}$ самый маленький
Двигаться $c_{i}$ к $P$ на небольшую долю расстояния
Набор $s_{i}$ до нуля
Повторить

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

Bink video ^[2]
Синепак
Daala основана на преобразовании, но использует пирамидальное векторное квантование преобразованных коэффициентов. ^[3]
Цифровое интерактивное видео : видео производственного уровня и видео в реальном времени
Индио
Майкрософт Видео 1
QuickTime : Apple Video (RPZA) и графический кодек (SMC)
Соренсон SVQ1 и SVQ3
Ужасное видео
Формат VQA , используемый во многих играх.

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

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

АМР-ВБ+
ВЫЗОВ
CELT (теперь часть Opus ) основан на преобразовании, но использует пирамидальное векторное квантование преобразованных коэффициентов.
Кодек 2
ДТС
G.729
iLBC
Огг Ворбис ^[4]
ТвинВК

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

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 для неконтролируемого перевода изображений в изображения.

См. также

Подтемы

Алгоритм Линде – Бьюзо – Грея (LBG)
Обучение векторному квантованию
Алгоритм Ллойда
Growing Neural Gas — нейросетевая система для векторного квантования.

Связанные темы

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

Ссылки

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

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

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

[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] «Спецификация Ворбиса 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 . ПМИД 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]