Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
24
Добавлен:
22.05.2015
Размер:
178.69 Кб
Скачать

Тема 6. Квантование изображений: квантование скалярной величины и векторной величины. Оптимальное положение уровня квантования и пороговых уровней, выражение Пантера-Дайтта. Оптимальное размещение пороговых уровней в зависимости от числа уровней квантования, таблица Макса. Лекция 9

КВАНТОВАНИЕ ИЗОБРАЖЕНИЙ: КВАНТОВАНИЕ СКАЛЯРНОЙ ВЕЛИЧИНЫ И ВЕКТОРНОЙ ВЕЛИЧИНЫ.

Оптимальное положение уровня квантования и пороговых уровней, выражение Пантера-Дайтта.

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

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

Процесс преобразования отсчетов, имеющих непрерывное множество значений (вещественные), в отсчеты с дискретными значениями (целочисленными), называется квантованием.

Объясним принцип квантования на примере квантования скалярной величины.

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

Пример.

Пусть f – случайная величина, с плотностью вероятности р(f). Кроме того, предполагается, что f не выходит за пределы некоторого интервала: aL f ≤ aU.

При решении задачи о квантовании необходимо выбрать такой набор пороговых уровней dj и уровней квантования rj, что если dj f dj+1, то исходный отсчет заменяется на число, равное уровню квантования rj.

На рис.1 приведен пример размещения пороговых уровней и уровней квантования на отрезке числовой оси, содержащем J пороговых уровней.

Рис. 1.

Другой распространенной формой представления характеристики квантования является ступенчатая кривая.

Уровни квантования и пороговые уровни выбирают так, чтобы уменьшить до минимума некоторую заданную величину, характеризующую ошибку квантования, т.е. степень различия между f и (f и – значения отсчета действительного скалярного сигнала до и после квантования).

В качестве меры ошибки квантования обычно выбирают среднеквадратическую ошибку. Если J – число уровней квантования, то среднеквадратическая ошибка квантования равна:

(1)

**Если J велико, т.е. J>>1, то плотность вероятности значений квантуемого сигнала на каждом из интервалов (dj, dj+1) можно считать постоянной и равной p(rj).

(2)

или

. ( 2*)

Оптимальное положение уровня квантования rj в (dj, dj+1) можно найти, решая задачу о минимуме ошибки как функции rj.

. (3)

dj – пороговые уровни, rj – уровни квантования.

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

Пороговые уровни: d0 d1 d2 d3 … dj-1 dj dj+1… dJ-1 dJ

Уровни квантования: aL r0 r1 r2 rj-1 rj rJ-1 aU

Подставим в (2*) и получим:

(4)

Оптимальное положение пороговых уровней можно определить, находя минимум ошибки  методом множителей Лагранжа.

Пантер и Дайт показали, что положения пороговых уровней довольно точно определяются по формуле: ,

где , j=0, 1, …, J.

Выводы:

Если плотность вероятности значений отсчетов равномерна, то пороговые уровни будут расставлены равномерно.

При неравномерных плотностях пороговые уровни чаще, где плотность вероятности велика, и реже там, где она мала.

Если число уровней квантования J невелико, то приближение, с помощью которого получено равенство (2), становится неоправданным и следует использовать точное выражение для ошибки (1).

Дифференцируя его по переменным dj и rj и приравнивая производные к нулю, получаем:

(а)

(б)

После преобразований приходим к системе:

(5)

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

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

Таблица Макса

Квантование векторных величин

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

Пусть сигнал f представляет собой вектор f размерности N. Будем считать, что вектор является реализацией случайного вектора с N-мерной плотностью вероятности: p(f)=p{f1, f2, …, fN}.

При квантовании вектора f N-мерное векторное пространство разделяется на J ячеек квантования Dj, каждой из которых соответствует один из J квантованных векторов. Векторный сигнал f заменяется на квантованный вектор rj, если f попадает в ячейку Dj.

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

Рис.2. Ячейки квантования в векторном пространстве.

Среднеквадратическую ошибку векторного квантования можно представить в виде суммы:

, (6)

tr – Евклидова норма матрицы.

(7)

оптимальное положение квантованных векторов rj при фиксированных границах.

(8)

условное математическое ожидание вектора f, когда он попадает в ячейку Dj.

(8*)

В этом случае минимальная среднеквадратическая ошибка квантования равна:

(9)

Rf – корреляционная матрица вектора f.

Оптимальные положения квантованных векторов rj при фиксированных ячейках квантования Dj невозможно определить, не зная совместной плотности вероятности p(f). Часто такая информация отсутствует. Еще одна существенная трудность связана с вычислением интегралов в формуле (8). Поэтому часто приходится упрощать процедуру векторного квантования.

  • Если компоненты вектора f некоррелированны, то вектор квантования сводится к последовательному квантованию скалярных величин.

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

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

Найдем набор ячеек квантования Dj, при котором минимизируется среднеквадратическая ошибка квантования.

Брюс разработал метод решения этой задачи на основе динамического программирования.

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

Ошибка квантования i – го сжатия равна

. (10)

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

Несколько специалистов разработали алгоритмы распределения числа разрядов b(i) при фиксированном В, позволяющем минимизировать среднеквадратическую ошибку квантования.

Алгоритм Реди и Уинца

(для квантования независимых гауссовых величин по методу Макса)

  1. Вычислить распределение числа разрядов по формуле , где - дисперсия i- го отчета.

  2. Округлить b(i) до ближайшего целого.

  3. Изменить полученное распределение, пока не будет выполнено условие .

Более надежные результаты можно получить, используя метод минимальной ошибки Прэтта.

Соседние файлы в папке Лекц_Доска (Семичевская)