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

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

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

Q
Входной сигнал
Квантователь
Квантованный сигнал

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

АЦП сигналов (audio,video,etc.)
Квантование коэффициентов преобразования
(JPEG, JPEG2000)
Бинаризация и многоуровневая пороговая обработка
цифрового изображения

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

Квантование & округление
Любо действительное число x может быть округлено к
ближайшему целому значению q(x) = round(x):
If k 0.5 x <k +0.5 then q(x)=k
5
5.5
x=5.6
6
q(x)=6.0
6.5
x=6.4
7

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

{yi}
уровни репродукции (реконструкции)
{ai}
Уровни принятия решения (пороги)
Si =[ai-1, ai)
Ячейка (Cell)
ai -ai-1
Ширина ячейки
a0 =- ,
a6 =+ .

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

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

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

Входной сигнал x
Квантованный
сигнал
q(x)
Ошибка
квантования:
e(x) = x q(x)

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

Плотность распределения вероятности (РВ) x
определим как p(x)
Ошибка квантования: e(x) = x q (x)
Среднее значение ошибки квантования:
M
aj
E[ x q( x)] ( x yi ) p( x)dx
j 1 a j 1
Дисперсия 2 ошибки квантования :
M
2 E[( x q( x)) 2 ]
aj
2
(
x
y
)
p( x)dx
j
j 1 a j 1 j

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

E x2
SNR 10 lg
2
E
e
( x)
dB ( decibels )

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

Данные x -> 0-среднее значение, равномерное
распределение в диапазоне [-A/2,A/2].
Шаг равномерного распределения: =A/M.
M 1 2 ( i 1)
A
E e ( x)
2
i 0
2
x
A
2
i
2
A2 i
2
1
1
1
2
y
dy
M
A
M 12 12
i 0
M 1
2
2
1
dx
A

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

Данные x -> 0-среднее значение, равномерное
распределение в диапазоне [-A/2,A/2].
Число бит: R=log2M, M – число уровней или M=2R ячеек.
Шаг равномерного квантования : =A/M
E x2
SNR 10 log 2
2
E
e
( x)
C 20 log 2 M lg 2 C 6R
Цена 1 бита в квантователе 6 dB в отношении сигнал-шум
”6 dB per bit rule”

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

Задан сигнал x, с плотностью распределения
вероятности(ПРВ) (или гистограмма) p(x),
Требуется: найти квантователь q(x) сигнала x, который
минимизирует дисперсию ошибки квантования 2:
2
opt
min
M
aj
(x y )
{a j },{ y j } j 1 a
j 1
j
2
p( x)dx

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

2
opt
min
M
aj
2
(
x
y
)
p( x)dx
j
{a j },{ y j } j 1 a
j 1
Задача оптимизации: найти{aj} представление
уровней {yj}, минимизирующих дисперсию 2.

14.

Скалярный квантователь MaxLloyd

15. Max-Lloyd решение

2
opt
min
M
aj
2
(
x
y
)
p( x)dx
j
{a j },{ y j } j 1 a
j 1
2
0
y j
0
a j
2

16. Max-Lloyd решение

2
0
y j
2
2( x y j ) p ( x)dx 0 xp( x)dx y j p ( x)dx 0
y j
a j 1
a j 1
a j 1
2
0
a j
2
(a j y j 1 ) 2 p (a j ) (a j 1 y j ) 2 p (a j ) 0
a j
aj
aj
aj
xp( x)dx
yj
a j 1
aj
p( x)dx
a j 1
a j 1
aj
y j 1 y j
2

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

Решающие уровни ai среднее 2 точек:
aj
y j y j 1
2
aj
Представление уровней yi -центроиды:
xp( x)dx
yj
a j 1
aj
p( x)dx
a j 1
yj-1
aj-1
yj
aj
yj+1

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

• Если мы имеем некоторое множество уровней и
• уравнения Max-Lloyd, то мы можем контролировать
• удовлетворяют ли эти уровни критерию минимума
• дисперсии ошибки
•Но уравнения не говорят нам как найти
aj
• оптимальные уровни
aj
y j y j 1
2
?
xp( x)dx
yi
a j 1
aj
p( x)dx
a j 1

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

0. гипотетическое начальное множество
решающих уровней {aj}
aj
xp( x)dx
1. Вычисление представление уровней y j a
a
(центроидов) {yj}:
p( x)dx
j 1
j
a j 1
2. Вычисление решающих
уровней {aj}:
aj
y j y j 1
2
3. Повтор 1. и 2. до заданного снижения дисперсии 2

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

0. Начальное множество
решающих уровней {aj}
1. Вычисление представления
уровней (центроидов) {yj}:
p x
i
yj
i
a j 1 xi a j
p
i
a j 1 xi a j
2. Вычисление решающих
уровней {aj}:
aj
y j y j 1
2
3. Повтор 1. и 2. до заданного снижения дисперсии 2

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

• Итеративный алгоритм Ллойда не может
гарантировать глобального минимума ошибки
квантования

22. Lloyd Matlab

t = [0:.1:2*pi];
sig = sin(t);
partition = [-1:.2:1];
codebook = [-1.2:.2:1];
% Now optimize, using codebook as an initial guess.
[partition2,codebook2] = lloyds(sig,codebook);
[index,quants,distor] = quantiz(sig,partition,codebook);
[index2,quant2,distor2] = quantiz(sig,partition2,codebook2);
% Compare mean square distortions from initial and optimized
[distor, distor2] % parameters.
ans =
0.014798675568578 0.002223655629773

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

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

• Данные X: - < x < ; p(x) - ПРВ
• Положим, что p(x) имеет вид плоской функции над
ячейкой Cj
• Квантование в M ячейках: M 1.
• Искажение для ячейки Cj с учетом выдвинутых
предположений:
Dj
aj
aj
a j 1
a j 1
2
2
(
x
y
)
p
(
x
)
dx
p
(
y
)
(
x
y
)
j
j
j dx
p( y j ) (a j a j 1 )3 12 [ p( y j ) j ] 2j 12
• Искажение для равномерного квантователя: D= 2/12

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

• ЦП: gC=1/ j, один центроид для одной ячейки.
• В пределе M и j 0, ЦП gC(x) есть функция x и
j 1/gC.
• В этом случае искажение в одной ячейки оценивается
как
D j p( y j ) j ( 12)
2
j
• Общее искажение D:
D
D
xi C j
j
xi C j
2j
p( y j ) j
12 g 2j ( y j )
1
2
p( yi )
j
p( y) g C ( y )dy
12
12

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

• Найти такую ЦП gC(x) которая минимизирует
•общее искажение D :
1
2
D min p( x) g C ( x)dx
g C ( x ) 12
ограничение:
g
C
( x)dx N

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

• Преобразуем задачу в задачу оптимизации
•без ограничений с стоимостной функцией Лагранжа D*:
D * D g C ( x)dx
• Найдем минимум стоимостной функции Лагранжа:
1
*
2
D min p( x) g C ( x)dx g C ( x)dx
g C ( x ) 12

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

D* ( g C )
0
g C
D*
( 2 p ( x) g C 3 ( x) / 12 )dx 0
g C
Центроидная плотность:
g C ( x)
p( x)
6
1
3
Используем ограничение
g
C
( x)dx M
Для вычисления коэффициента .

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

Центроидная плотность: g C ( x) M
p1 / 3 ( x )
Искажения :
1
D
12 N 2
p
1/ 3
p1/ 3 ( x)dx
( x)dx
3

30.

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

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

p1
x1
p2
x2
xN
• Пусть X={x1, x2, …, xN} – конечное упорядоченное
множество действительных чисел (значения
интенсивности).
• Пусть P={p1, p2, …, pN}- соответствующее множество
вероятностей для значений X (гистограмма).
• Пусть {r0,r1,r2, …,rM+1} – упорядоченное множество
целых чисел, которое определяет разбиение множества
X на M частей:
r0= 0 < r1 < ... < rj < rj+1 <... < rM = N.

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

• Индексы разбиения: r0= 0 < r1 <... < rj < ... < rM =N.
(r0= 0 для x0= .)
M
• Общая ошибка квантования:
e (rj 1 , rj ]
2
2
j 1
• Ошибка квантования для одной ячейки:
e (rj 1 , rj ]
2
• Центроид ячейки yj:
p
r j 1 k r j
yj
k
( xk y j )
p
r j 1 k r j
k
xk
p
r j 1 k r j
k
2

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

• Для заданных данных X, вероятностей P и числа ячеек M
найти такое разбиение {ro,r1, r2, …, rM} которое приводит
к минимуму общую ошибку квантования :
M 2
min e (rj 1 , rj ]
{r j } j 1
2
где
и
e 2 (rj 1 , rj ]
p
yj
r j 1 k r j
2
p
(
x
y
)
k k j
r j 1 k r j
k
xk
p
r j 1 k r j
k

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

Положим, мы введем в рассмотрение функцию
стоимости Dm(0,n] которая минимизирует ошибку
квантования данных подмножества
Xn={x1, x2, …, xn} из m ячеек:
1
2
Dm (0, n ] min e ( rj 1 , rj ] , где rj n.
{ r } j 1
m
j
Тогда DM(0,N] дает решение задачи .

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

• Перепишем функцию стоимости в виде:
m 2
Dm (0, n] min e (rj 1 , rj ]
r1 , r2 ,..., rm 1
j 1
m 1 2
2
min min e (rj 1 , rj ] e (rm 1 , n] .
rm 1
r1 ,r2 ,..., rm 2 j 1
• Окончательно:
Dm (0, n] min
D
m 1 rm 1 n
2
(
0
,
r
]
e
(rm 1 , n]
m 1
m 1

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

Инициализация :
D1 (0, n] e (0, n]
2
Рекурсия :
1
Dm (0, n] min Dm 1 (0, j ] e ( j, n]
m 1 j n
2

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

• Оптимальный скалярный квантователь определяет
наикратчайший путь во взвешенном графе .
• ДП алгоритм [1963]: временная сложностьs O(MN2)
• Wu [1991] уменьшил временную сложность
оптимального ДП алгоритма до O(MN)
• X,Y,Z [2003] ”Fast algorithm for multilevel thresholding”:
O(NM) O(NM-1)

38. Matlab

39. Пример: M=3

Uniform
Input image
Optimal

40. Пример: M=3

Uniform
Optimal

41. Пример: M=12

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

42.

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

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

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

X={x1,x2,…,xN } есть множество входных векторов в d-D
пространстве
c={c1,c2,…,cM} множество кодовых векторов в
пространстве
P разбиение пространства на M кодовых ячеек
(кластеров)
C={C1,C2,…,CM}
VQ имеет NP-сложность!

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

Входные данные
N=65000
Кодовые векторы
M=1000

46. VQ

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

47. GUI Matlab

48. Вопросы

Спасибо за внимание