Векторное квантование - Vector quantization

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

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

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

Подготовка

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

Бинк видео^[2]
Cinepak
Даала основан на преобразовании, но использует векторное квантование преобразованных коэффициентов^[3]
Цифровое видео интерактивное: Видео производственного уровня и видео в реальном времени
Indeo
Microsoft видео 1
QuickTime: Apple видео (РПЗА) и Графический кодек (SMC)
Соренсон SVQ1 и SVQ3
Smacker видео
VQA формат, используемый во многих играх

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

^ Дана Х. Баллард (2000). Введение в естественные вычисления. MIT Press. п. 189. ISBN 978-0-262-02420-4.
^ "Бинк видео". Книга мудрости. 2009-12-27. Получено 2013-03-16.
^ Валин, Дж. (Октябрь 2012 г.). Пирамидальное векторное квантование для видеокодирования. IETF. I-D черновик-валин-видеокодек-pvq-00. Получено 2013-12-17.
^ «Спецификация Vorbis I». Xiph.org. 2007-03-09. Получено 2007-03-09.
^ Бертон, Д. К .; Shore, J. E .; Бак, Дж. Т. (1983). «Обобщение распознавания отдельных слов с использованием векторного квантования». Международная конференция IEEE по акустике обработки речи и сигналов ICASSP. 8: 1021–1024. Дои:10.1109 / ICASSP.1983.1171915.
^ Сунг, Ф .; А. Розенберг; Л. Рабинер; Б. Хуанг (1985). «Подход векторного квантования к распознаванию говорящего». Международная конференция IEEE Proceedings по акустике, обработке речи и сигналов ICASSP. 1: 387–390. Дои:10.1109 / ICASSP.1985.1168412. S2CID 8970593.
^ Х. Джегоу; М. Дуз; К. Шмид (2011). «Квантование продукта для поиска ближайшего соседа» (PDF). IEEE Transactions по анализу шаблонов и машинному анализу. 33 (1): 117–128. CiteSeerX 10.1.1.470.8573. Дои:10.1109 / TPAMI.2010.57. PMID 21088323. S2CID 5850884.
^ Фаундез-Зануй, Маркос (2007). «Распознавание подписи офлайн и онлайн на основе VQ-DTW». Распознавание образов. 40 (3): 981–992. Дои:10.1016 / j.patcog.2006.06.007.
^ Фаундез-Зануй, Маркос; Хуан Мануэль Паскуаль-Гаспар (2011). «Эффективное онлайн-распознавание подписи на основе Multi-section 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

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

[1] Дана Х. Баллард (2000). Введение в естественные вычисления. MIT Press. п. 189. ISBN 978-0-262-02420-4.

[2] "Бинк видео". Книга мудрости. 2009-12-27. Получено 2013-03-16.

[3] Валин, Дж. (Октябрь 2012 г.). Пирамидальное векторное квантование для видеокодирования. IETF. I-D черновик-валин-видеокодек-pvq-00. Получено 2013-12-17.

[4] «Спецификация Vorbis I». Xiph.org. 2007-03-09. Получено 2007-03-09.

[5] Бертон, Д. К .; Shore, J. E .; Бак, Дж. Т. (1983). «Обобщение распознавания отдельных слов с использованием векторного квантования». Международная конференция IEEE по акустике обработки речи и сигналов ICASSP. 8: 1021–1024. Дои:10.1109 / ICASSP.1983.1171915.

[6] Сунг, Ф .; А. Розенберг; Л. Рабинер; Б. Хуанг (1985). «Подход векторного квантования к распознаванию говорящего». Международная конференция IEEE Proceedings по акустике, обработке речи и сигналов ICASSP. 1: 387–390. Дои:10.1109 / ICASSP.1985.1168412. S2CID 8970593.

[7] Х. Джегоу; М. Дуз; К. Шмид (2011). «Квантование продукта для поиска ближайшего соседа» (PDF). IEEE Transactions по анализу шаблонов и машинному анализу. 33 (1): 117–128. CiteSeerX 10.1.1.470.8573. Дои:10.1109 / TPAMI.2010.57. PMID 21088323. S2CID 5850884.

[8] Фаундез-Зануй, Маркос (2007). «Распознавание подписи офлайн и онлайн на основе VQ-DTW». Распознавание образов. 40 (3): 981–992. Дои:10.1016 / j.patcog.2006.06.007.

[9] Фаундез-Зануй, Маркос; Хуан Мануэль Паскуаль-Гаспар (2011). «Эффективное онлайн-распознавание подписи на основе Multi-section 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]