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

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

Основные понятия

Кодовая книга

Кодовая книга (или кодовая таблица) — это множество K эталонных векторов (кодовых слов) фиксированной размерности d. Каждый эталонный вектор представляет собой типичный представитель некоторого кластера данных. Размер кодовой книги (количество кодовых слов) определяет степень сжатия: чем меньше слов, тем выше сжатие, но больше потенциальные искажения.

Квантование

Процесс квантования заключается в том, что для каждого входного вектора x (размерности d) находится ближайший эталонный вектор y из кодовой книги по некоторой метрике (обычно евклидово расстояние). Входной вектор заменяется индексом этого эталонного вектора в кодовой книге. Таким образом, передаётся или хранится не сам вектор, а его индекс, что требует значительно меньшего объёма данных.

Искажение

Мера искажения (или ошибки квантования) — это среднее расстояние между входными векторами и их квантованными представлениями. Наиболее распространённая метрика — среднеквадратичная ошибка (MSE). Цель векторного квантования — минимизировать искажение при заданном размере кодовой книги.

История

Идея векторного квантования восходит к работам по теории информации середины XX века. В 1948 году Клод Шеннон в своей работе «Математическая теория связи» заложил основы теории квантования. Однако практическое развитие векторного квантования началось в 1970-х годах с развитием вычислительной техники. В 1980 году Дж. Линде, А. Бузо и Р. Грей предложили алгоритм LBG (Linde-Buzo-Gray), который стал стандартным методом построения кодовой книги. Этот алгоритм является модификацией K-средних (K-means) для задачи векторного квантования. С конца 1980-х годов векторное квантование активно применялось в сжатии изображений (например, в стандарте JPEG) и аудио (например, в кодеках MPEG).

Алгоритмы построения кодовой книги

Алгоритм LBG

Алгоритм LBG (Linde-Buzo-Gray) — итеративный метод, основанный на принципе «разделяй и властвуй». Он включает следующие шаги:

1. Инициализация: выбирается начальная кодовая книга (например, случайные векторы из обучающей выборки).
2. Кластеризация: каждый вектор обучающей выборки относится к ближайшему кодовому слову.
3. Обновление: каждое кодовое слово заменяется центроидом (средним арифметическим) всех векторов, отнесённых к нему.
4. Проверка сходимости: если изменение искажения меньше заданного порога, алгоритм останавливается; иначе повторяются шаги 2–3.

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

Другие методы

• Алгоритм K-средних (K-means): аналогичен LBG, но часто используется в задачах кластеризации, а не квантования.
• Алгоритм «жадного» разделения (Greedy splitting): начинается с одного кодового слова, которое затем последовательно разделяется на два, и процесс повторяется до достижения нужного размера кодовой книги.
• Нейросетевые подходы: самоорганизующиеся карты Кохонена (SOM) и нейронные сети с конкурирующим обучением могут использоваться для построения кодовой книги.

Применение

Сжатие изображений

Векторное квантование используется в сжатии изображений, особенно в системах с низкой пропускной способностью. Изображение разбивается на блоки (например, 4×4 пикселя), каждый блок квантуется как вектор. Кодовая книга создаётся на основе обучающей выборки типичных изображений. Метод лёг в основу стандарта JPEG (в части квантования коэффициентов дискретного косинусного преобразования) и используется в некоторых форматах сжатия без потерь (например, в PNG — для квантования палитры).

Сжатие аудио

В аудиокодеках (например, MP3, AAC) векторное квантование применяется для квантования спектральных коэффициентов. В частности, в стандарте MPEG-1 Layer III (MP3) используется адаптивное векторное квантование в сочетании с психоакустической моделью.

Сжатие видео

В видеокодеках (например, H.264, H.265) векторное квантование применяется для квантования коэффициентов трансформации (дискретного косинусного преобразования) после этапа предсказания. Это позволяет эффективно сжимать остаточные сигналы.

Распознавание образов

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

Машинное обучение

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

Достоинства и недостатки

Достоинства

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

Недостатки

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

Интересные факты

• Векторное квантование является частным случаем более общего метода — квантования с кодовой книгой, который также включает скалярное квантование как случай размерности вектора, равной 1.
• Алгоритм LBG был предложен в 1980 году и до сих пор остаётся одним из наиболее распространённых методов построения кодовой книги, несмотря на появление более современных подходов (например, на основе нейронных сетей).
• Векторное квантование используется в некоторых системах сжатия изображений для космических аппаратов, где важна высокая степень сжатия при ограниченной пропускной способности канала связи.

Источники

• Линде, А., Бузо, А., Грей, Р. (1980). «Алгоритм построения кодовой книги для векторного квантования». IEEE Transactions on Communications.
• Шеннон, К. (1948). «Математическая теория связи». Bell System Technical Journal.
• Грей, Р. (1984). «Векторное квантование». IEEE ASSP Magazine.
• Рабин, Л., Шефер, Р. (1993). «Цифровая обработка речевых сигналов». Москва: Радио и связь.