МЕТОДЫ СЖАТИЯ ИНФОРМАЦИИ. Методические указания Рекомендовано Научнометодическим советом университета для студентов, обучающихся по направлению Фундаментальная информатика и информационные технологии
 Скачать 0.87 Mb.
|
|
3. Сжатие изображений. Введение Определение. Цифровое изображение представляет собой прямоугольную таблицу (матрицу) точек, размер которой n × m, где n – число столбцов, m – число строк в изображении. Будем считать, что для каждой точки (x, y) определена положительная скалярная величина f(x, y) – отсчет, физический смысл которого определяется источником изображения. Принцип сжатия изображений Если случайно выбрать пиксель изображения, то с большой вероятностью ближайшие к нему пиксели будут иметь тот же или близкий цвет. Другими словами, мы можем ожидать, что ближайшие пиксели изображения коррелируют между собой. Студенты должны обратить внимание на то, что для корректной оценки степени сжатия изображения и целесообразности использования того или иного алгоритма сжатия к данному изображению следует учитывать класс изображения. Подклассом цифрового изображения понимается совокупность изображений, которая при применении к ней выбранного алгоритма сжатия дает качественно одинаковый результат. Традиционными классами изображений являются следующие Монохроматическое изображение. В этом случае все пик- селы могут иметь только два значения и значит каждый пиксел изображения представлен одним битом • Цветное изображение. Все цветные изображения можно подразделить на две группы с палитрой и без не. Для изображений с палитрой f (x, y) – это индекс в некотором одномерном векторе цветов, называемом палитрой. Палитры обычно бывают 8, 16 и 256 элементными. Изображения без палитры обычно бывают в определенной системе цветопредставления. Существует несколько методов задания цвета в цветовой модели, но обычно в описании участвуют три параметра. Как правило, цветной пик- сель состоит из трех байтов. Типичными цветовыми моделями являются RGB, CMY, HSV, YC r C b . Опишем указанные цветовые модели подробнее 30 – RGB (модель является основной при создании и обработке компьютерной графики, предназначенной для электронного воспроизведения Модель RGB является аддитивной, то есть любой цвет представляется сочетанием в различных пропорциях трех основных цветов – красного, зеленого, синего (рис. 5). Pис. 5. Модель RGB – CMY (модель используют при подготовке публикаций к печати. Модель описывается тремя компонентами голубым, пурпурным, желтым. Цвета CMY описывают отраженный от белой бумаги свет трех основных цветов RGB модели (рис. 6). Pис. 6. Модель Соотношения для перекодировки цвета из модели CMY в RGB: - = Y M C B G R 1 И обратно – из модели RGB в CMY: - = B G R Y M C 1 Здесь считается, что компоненты кодируются числами в диапазоне от 0 до 1. Для иного диапазона чисел можно записать соответствующие соотношения 31 – HSV (цвет описывается тремя компонентами цветовым тоном, насыщенностью, светлотой) Цветовой тон H измеряется в градусах от 0 до 60, цвета располагаются по кругу в таком порядке — красный, оранжевый, желтый, зеленый, голубой, синий и т. д. (рис. 7). Pис. 7. Модель Значения насыщенность S и светлота V находятся в диапазоне. Отметим, что насыщенность зависит от цветового охвата. Алгоритм преобразования цветового пространства HSV в Исходными данными алгоритма являются H цветовой тон (0–360 ̊ ) 0 ̊ – красный S насыщенность (0–1). › V светлота (Выходными данными алгоритма являются RGB – красный, зеленый, синий основные цвета(0–1) Алгоритм преобразования Пусть Floor – функция, выделяющая целую часть числа S = 0 then { If H = неопределенность then { R = V; G = V; B = V; } else если Н определено, то ошибка 32 else { If H = 360 then H = 0; else H = H / 60; I = Floor(H); F = H – I; M = V * (1 – S); N = V * (1 – S * F); K = V * (1 – S * (1 – F)); If I = 1 then (R, G, B) = (V, K, M) 9 If I = 2 then (R, G, B) = (N, V, M) If I = 3 then (R, G, B) = (M, V, K) If I = 4 then (R, G, B) = (M, N, V) If I = 5 then (R, G, B) = (K, M, V) If I = 6 then (R, G, B) = (V, M, Алгоритм окончен. Алгоритм преобразования цветового пространства RGB в Исходными данными алгоритма являются RGB – красный, зеленый, синий основные цвета(0–1) Выходными данными алгоритма являются H цветовой тон (0–360 ̊ ) 0 ̊ – красный S насыщенность (0–1). › V светлота (Алгоритм преобразования Пусть Max, Min – функции определения максимума и минимума) / V; If S = 0 then H = неопределенность (R, G, B) = (V, K, M) означает R = V, G = K, B = M. › 33 { C r = (V – R) / (V – Temp); C g = (V – G) / (V – Temp); C b = (V – B) / (V – Temp); If R = V then H = C b – C g ; If G = V then H = 2 + C r – C b ; If B = V then H = 4 + C g – C r ; H = 60 * H; If H < 0 then H = H + Алгоритм окончен модель описывается тремя компонентами Y – яркость хроматический красный, C b – хроматический синий. В отличие от RGB, где все компоненты равнозначны, цветовая модель концентрирует наиболее важную информацию водном из компонентов. Данная модель применима к сжатию за счет того, что человеческий глаз менее чувствителен к цвету, чем к яркости. Упрощенно перевод из цветового пространства RGB в цветовое пространство YC r C b можно представить с помощью матрицы перехода (опишем то, которое используется в формате jpeg [5]) : + - - - - = 128 128 0 * 5, 0 3313 ,0 1687 ,0 0813 ,0 4187 ,0 5, 0 114 ,0 587 ,0 Обратное преобразование - - - = 128 128 0 * 0 772 ,1 1 71414 , 0 34414 , 0 1 402 ,1 0 1 r b C C Y B G R • Полутоновое изображение. Каждый пиксель такого изображения может иметь значение из диапазона от 0 до 2 S – 1, обозначающее одну из 2 S градаций серого (или иного) цвета. Число обычно сравнимо с размером байта, то есть равно 4, 8, 12, 16 итак далее. Каждая градация серого цвета определяется яркостью. Серые цвета в модели RGB описываются одинаковыми значениями компонентов, то есть R = G = B. Для преобразования цветного изображения, представленного в системе RGB, в градации серого можно воспользоваться соотношением 587 , 0 где коэффициенты при R, G, B учитывают различную чувствительность зрения к соответствующим цветам. • Изображение с непрерывным тоном. Этот тип изображений может иметь много похожих цветов (или полутонов. Когда соседние пиксели отличаются всего на единицу, глазу практически невозможно различить их цвета. Можно выделить и специфические классы изображений, такие как рентгеновские снимки, томаграфические изображения, радиолокационные планы местности и т. д. Методы сжатия изображений обычно разрабатываются для конкретного класса изображений. Например, для монохроматического изображения можно эффективно использовать метод кодирования длин серий (RLE). Предполагаем, что отсчеты) непосредственных соседей пиксела (x, y) совпадают с f (x, y). Метод сжатия RLE упрощенно можно описать следующим образом изображение вытягивают в цепочку бит по строкам растра › находят числа, соответствующие длинам участков, на которых данные сохраняют неизменное значение › длины кодируют кодами переменной длины и записываются в сжатый файл. Дискретные преобразования Сжатие изображения достигается, если в процессе какого- либо преобразования получаются значения, которые имеют существенно меньшую корреляцию между собой, чем исходные отсчеты. Рассмотрим несколько известных дискретных преобразований, которые можно использовать для сжатия изображения Дискретное косинусное преобразование (Дискретным косинусным преобразованием вектора X = (x 0 , x 1 ,…, x n – 1 ) назовем вектор Y = (y 0 , y 1 ,…, y n – 1 ), компоненты которого определяются по формуле 1 2 cos 2 1 0 ∑ - = + ⋅ = n t t k k n k t x C n y π где , 0 , 1 0 , 2 1 > = = k k C k 0 ≤ k ≤ n – Тогда обратное дискретным косинусным преобразованием имеет вид ( ) , 2 1 2 cos 2 1 0 ∑ - = + = n k k k t n k t y C n x π где , 0 , 1 0 , 2 1 > = = k k C k 0 ≤ t ≤ n – Двумерное преобразование (DCT) оперирует блоками P размером, элементами которых служат сэмплы (обычно это отсчеты самого изображения или величины разностей между отсчетом и прогнозом изображения, и порождает блок n × n некоторых коэффициентов G. Действие DCT (а также обратного к нему преобразования IDCT) можно описать с помощью матрицы преобразования Прямое преобразование будет выглядеть как G = MPM T обратное Элементы матрицы M равны 1 2 cos π , где 0 , 1 i n i n C i , 0 ≤ i, j ≤ n – В случае если изображение разбивается на блоки пикселей p xy размера 8×8, уравнение, используемое для нахождения коэффициентов может быть записано следующим образом 1 0 0 1 (2 1) (2 1) cos cos 4 16 16 n n ij i j xy x y y j x i G C где , 0 2 1, 0 k k Ñ k = = > , 0 ≤i, j ≤ 7. C k Обратное преобразование DCT вычисляется по формуле 7 0 0 1 (2 1) (2 1) cos cos 4 16 16 xy i j ij i j y j x i p C C где , 0 2 1, 0 k k Ñ k = = > , 0 ≤i, j Пример. Найти матрицу дискретного косинусного преобразования, если n = 4. Решение Матрица преобразования M имеет вид 1 1 1 cos(0) cos(0) cos(0) cos(0) 2 2 2 2 1 1 3 1 5 1 7 cos cos cos cos 2 8 2 8 2 8 2 8 1 2 1 6 1 10 1 14 cos cos cos cos 2 8 2 8 2 8 2 8 1 3 1 9 1 15 1 21 cos cos cos cos 2 8 2 8 2 8 2 8 M π π π π π π π π π π π π Можно легко вычислить, что 0,5 0,5 0,5 0,653 0,271 0,271 0,653 0,5 0,5 0,5 0,5 0,271 0,653 0,653 Пример окончен. Дискретное псевдокосинусное преобразование Рассмотрим более простую в вычислении альтернативу DCT [8]. Алгоритм сжатия изображений на основе такого преобразования может быть востребован в устройствах с ограниченными аппаратными ресурсами Рассмотрим матрицы W 2 , W 3 , W 4 , которые будем называть элементарными матрицами дискретного псевдокосинусного преобразования (ДПКП) . - = - = 1 1 1 1 2 1 0 0 2 1 2 1 2 1 2 1 2 1 2 W - - = - - = 1 2 1 1 0 1 1 1 1 6 1 0 0 0 2 1 0 0 0 3 1 6 1 3 2 6 1 2 1 0 2 1 3 1 3 1 3 1 3 W 4 1 1 1 1 1 0 0 0 2 2 2 2 2 1 1 1 1 1 2 1 1 2 0 0 0 2 1 1 2 10 10 10 10 10 1 1 1 1 1 1 1 1 1 0 0 0 2 2 2 2 2 1 2 2 1 1 1 2 2 1 0 0 0 10 10 10 10 Заметим, что рассмотренные матрицы могут быть представимы в виде W n = где D n – диагональная матрица нормирующих множителей, C n – матрица, состоящая только из чисел {–2,–1,0,1,2}. Легко убедиться, что матрицы W 2 , W 3 , W 4 ортогональны, поэтому W i –1 = W i T , где (2 ≤ i ≤ 4). Определение. Кронекеровским произведением матриц A и называется матрица C, образуемая последующему правилу й элемент матрицы C представляет собой соответствующий элемент a ij матрицы A, умноженный на всю матрицу B, то есть c ij = a ij B. Для кронекеровского произведения матриц примем обозначение. Кронекеровское произведение матриц обладает следующими свойствами) ( ) ( )( ) ( ) ; 2 2 1 1 2 1 2 1 l l l l B A B A B A B B B A A A ⊗ ⊗ ⊗ = ⊗ ( )( ) ( ) ( ) ( ) 2 2 1 1 2 1 2 Матрицы дискретного псевдокосинусного преобразования размерности n > предлагается строить следующим образом = W 2 ⊗ W 3 , W 6 = W 2 ⊗ W 3 , W 6 = W 2 ⊗ W 3 , W 6 = W 2 ⊗ W 3 , W 6 = W 2 ⊗ W 3 Другими словами число n должно быть представимо в виде произведения чисел 2, 3, 4. Располагать матрицы W 2 , W 3 , W 4 следует в порядке увеличения нижнего индекса. Пусть W n = D n C n , где n = n 1 , n 2 ,…, n s , n i ∈ {2, 3, 4}, тогда D n = D n 1 ⊗ D n 2 ⊗ … ⊗ D n s , а C n = C n 1 ⊗ C n 2 ⊗ … ⊗ Дискретным псевдокосинусным преобразованием вектора X = (x 0 , x 1 ,…, x n – 1 ) назовем вектор Y = (y 0 , y 1 ,…, y n – 1 ), компоненты которого определяются по формуле = W n X = Тогда обратное преобразованием имеет вид X = W i –1 Y = Вычисление двухмерного ДПКП аналогично DCT, то есть сначала для строк блока применяем ДПКП, затем столбцы полученной матрицы подвергаются дискретному псевдокосинусному преобразованию. Пример. Приведите матрицу псевдокосинусного преобразования W 8 Решение Вспомним, что W 8 = W 2 ⊗ W 4 и W 8 = D 8 C 8 , где D 8 = D 2 ⊗ D 4 C 8 = C 2 ⊗ C 4 . Учитывая определение легко получить 8 2 4 1 0 0 0 2 1 1 0 0 0 0 10 2 1 1 0 0 0 0 2 2 1 0 0 0 10 D D D = ⊗ = ⊗ В результате получим диагональную матрицу = 5 2 1 , 2 2 1 , 5 2 1 , 2 2 1 , 5 2 1 , 2 2 1 , 5 2 1 , 2 2 1 8 D 39 8 2 4 1 1 1 1 1 1 1 1 2 1 1 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 2 2 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 2 2 1 1 2 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 C C C - - - - - - - - - - - - - - = ⊗ = ⊗ = - - - - - - - - - - - - - Пример окончен. |