то
в этом случае если x¯(n)ЄCi, то ей ставят в соответствие yi¯*
и в этом случае среднее искажение для i ячейки
определяются по следующей формуле:
где Mi-число векторов x(n) попавший в область Ci.
Для критерия СКО можно показать что Di минимизируется при условии если:
Как разбить всю кодовою книгу на ячейки Ci оптимальным образом?
Одним из наиболее эффективных методов построения кодовой книги является итерационный кластерный алгоритм. Алгоритм разделяет набор обучающих векторов x¯(n), i от 1 до M на L кластеров Ci, i от 1 до L таким образом чтобы удовлетворялись два необходимых условия оптимальности указанных выше.
Кластерный алгоритм построения кодовой книги включает следующие шаги:
1.Задание на начальных условий произвольным образом выбираются значения yi(0), i от 1 до L yi(0) начальное значение центройда
2.Классификация, классифицируют набор обучающих векторов x(n) по кластерам Ci с помощью правила ближайшего соседа.
т.е.: x¯Є Ci(m) тогда и только тогда, когда d(x¯,yi¯)=<d(x¯,yj¯) j≠i. m-номер итерации.
3.Коррекция кодовых векторов (центройдов), производится путем вычисления новых значений центройдов обучающих векторов для каждого кластера.
4.Рассчитывается суммарное среднее искажение, по следующей формуле:
5.Проверка на окончание процедуры. Если уменьшение велечены общего среднего искажения D(m), на итерации m относительно искажения D(m-1) меньше некоторого порога, процедура заканчивается, в противном случае переход на шаг 2.
3.14Кодирование изображений: кодеки JPEG.
Основные алгоритмы сжатия изображений.
Возможности сокращения описания изображения обусловлено 2 факторами:
1) Ограничение зрительного восприятия - изображение можно аппроксимировать более простой моделью.
2) Избыточность цифрового изображения даже после первичного сжатия. Дополнительное сжатие можно обеспечить методами неравномерного статистического кодирования.
Первый класс методов сжатия основан на свойствах самого изображения и динамике его изменения от кадра к кадру. Данные методы ведут к потере части информации об изображении. Реализованы как в виде внутрикадрового, так межкадрового кодирования. К первому классу можно отнести:
1) Кодирование предсказанием АДИКМ.
2) Линейное кодирование с предсказанием.
3) Мужкадровое кодирование (большая часть изображения незначительно изменяется друг относительно друг от кадра к кадру).
4) Прореживание отсчетов с последующей интерполяцией.
5) Гибридное межкадровое и внутрикадровое кодирование.
Статическое кодирование обеспечивает сжатие за счет статистических свойств сигнала изображения и в принципе не ведет к потерям изображения. Ко второму классу можно отнести:
1) Использование статистических кодов, арифметических кодов.
2) Векторное кодирование.
3) Фрактальные методы – медленная архивация, но быстрая распаковка.
Алгоритм JPEG.
Разработан группой экспертов для сжатия 24 битных полноцветных изображений (алгоритм ДКП участков изображения 8*8, равномерное квантование, кодирование Хаффмана). На участке 8*8 яркость и цвет меняются сравнительно плавно. При разложении матрицы такой области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты. Цветовое восприятие слабо распознает некоторые частоты, то есть более грубая аппроксимация некоторых компонент будет происходить без потери качества.
Характеристики JPEG:
1) Коэффициент компрессии от 2 до 200.
2) Полноцветные 24 битные изображения.
Недостатки:
1) Создается ореол вокруг резких горизонтальных и вертикальных границ изображения (эффект Гиббса).
2) При высокой степени сжатия изображение распадается на блоки 8*8 пикселей.
Последовательность операций JPEG.
Y - яркостная компонента.
U,V - цветовые компоненты.
V - хроматический синий
U - хроматический красный.
RLE - алгоритм группового кодирования.
Шаг 1.
Переводим изображение из цветового пространства RGB в цветовое пространство YUV, что делается для последующего обеспечения более грубого квантования цветовых компонент U,V при более точном квантовании яркостной компоненты Y. Упрощенно перевод можно представить в виде:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.