Оптимальное квантования

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

Входной сигнал

Квантованный сигнал

Q

Квантователь

Квантование : область применения

АЦП сигналов (audio,video,etc.)

Бинаризация и многоуровневая пороговая обработка
цифрового изображения

Квантование

Квантование & округление

Любо действительное число x может быть округлено к ближайшему

Квантование как линейное разбиение

{yi} − уровни репродукции (реконструкции)
{ai} − Уровни

Неравномерный квантователь: M = 8 уровней

Переходная (вход-выход) характеристика
неравномерного квантователя

R=log2M

Ошибка квантования

Ошибка квантования:
e(x) = x−q(x)

Входной сигнал x

Квантованный сигнал
q(x)

Измерение искажения: СКО, дисперсия

Плотность распределения вероятности (РВ) x определим как

Отношение сигнал –шум

Источник с равномерным распределением : СКО

Данные x -> 0-среднее значение,

Источник с равномерным распределением : отношение сигнал-шум

Данные x -> 0-среднее

Задача оптимального квантования

Задан сигнал x, с плотностью распределения вероятности(ПРВ) (или гистограмма)

Задача квантования :формулирвка

Задача оптимизации: найти{aj} представление уровней {yj}, минимизирующих дисперсию σ2.

Скалярный квантователь Max-Lloyd

Max-Lloyd решение

Max-Lloyd решение

Max-Lloyd: условие оптимального квантования

Представление уровней yi -центроиды:

Решающие уровни ai среднее 2

Как конструировать оптимальный квантователь?

Если мы имеем некоторое множество уровней и

Max-Lloyd: итеративный алгоритм

0. гипотетическое начальное множество
решающих уровней {aj}
Вычисление представление

Итеративный алгоритм: дискретный вариант

0. Начальное множество
решающих уровней {aj}
Вычисление представления
уровней (центроидов)

Как построить оптимальный скалярный квантователь?

Итеративный алгоритм Ллойда не может гарантировать

Lloyd Matlab

t = [0:.1:2*pi];
sig = sin(t);
partition = [-1:.2:1];
codebook = [-1.2:.2:1];
% Now

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

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

Данные X: -∞ < x < ∞ ; p(x)

Центроидная плотность (ЦП)

ЦП: gC=1/Δj, один центроид для одной ячейки.
В

Оптимальное высокоскоростное квантование

Найти такую ЦП gC(x) которая минимизирует
общее искажение D

Метод множителей Лагранжа

Преобразуем задачу в задачу оптимизации
без ограничений с

Поиск минимума D*

Центроидная плотность:

Используем ограничение

Для вычисления коэффициента λ.

Высокоскоростной квантователь

Центроидная плотность:

Искажения :

Оптимальный скалярный квантователь

Формулировка задачи

Пусть X={x1, x2, …, xN} – конечное упорядоченное множество

Задача разбиения последовательности

Ошибка квантования для одной ячейки:

Центроид ячейки

Задача оптимизации

Для заданных данных X, вероятностей P и числа ячеек

Функция стоимости DM(0,N]

Положим, мы введем в рассмотрение функцию стоимости Dm(0,n]

Подход динамического программирования (ДП)

Окончательно:

Перепишем функцию стоимости в виде:

Рекуррентное уравнение

Инициализация :

Рекурсия :

Оптимальное скалярное квантование

Оптимальный скалярный квантователь определяет наикратчайший путь во взвешенном

Matlab

Пример: M=3

Input image

Uniform

Optimal

Пример: M=3

Uniform

Optimal

Пример: M=12

Центроидная плотность высока, если высока
и плотность распределения вероятностей

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

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

VQ: определение

∙

∙

∙

∙

∙

∙

∙

∙

∙

∙

X={x1,x2,…,xN } есть множество входных векторов в d-D пространстве

Пример : VQ цвета в 3-D пространстве

Входные данные

Кодовые векторы

N=65000

M=1000

VQ

voronoi(rand(100,1), rand(100,1))
set(gca, 'visible', 'off')

GUI Matlab