МЕТОДЫ СЖАТИЯ ИНФОРМАЦИИ. Методические указания Рекомендовано Научнометодическим советом университета для студентов, обучающихся по направлению Фундаментальная информатика и информационные технологии
 Скачать 0.87 Mb.
|
|
Преобразование Уолша (Студенты могут легко убедиться, что намного проще и быстрее считаются преобразования, основанные на импульсоподоб- ных сигналах, которые принимают значения только ±1. Кроме того, они больше подходят для описания сигналов с нарушением непрерывности. Преобразование Уолша – это преобразование, основанное на наборе гармонических прямоугольных импульсов, которые называются функциями Уолша (рис. 8 ирис. Pис. 8. Первые восемь функций Уолша с упорядочением по Уолшу wal(n, θ) (для матрицы преобразования Пусть n = 2 m и m – натуральное число, тогда дискретным преобразованием Уолша вектора X = (x 0 , x 1 ,…, x n – 1 ) назовем вектор Y = (y 0 , y 1 ,…, y n – 1 ), компоненты которого определяются по формуле или X M n Y h 1 = , где M w – матрица преобразования Уолша с упорядочением по Уолшу размерности n × n; 40 M h – матрица преобразования Уолша Адамара размерности n × Обратное преобразование Уолша будем рассматривать, соответственно как X = M w Y или X = Двухмерное преобразование Уолша оперирует с блоками P размером n × n и выглядит следующим образом [6]: T M P M n G * * 1 2 = , где n = 2 m , m = 1, 2, 3, …; G – матрица коэффициентов преобразования – матрица преобразования, все матрицы имеют размерность Обратное преобразование Уолша описывается при помощи следующего выражения Преобразование Уолша с упорядочением по Уолшу (Для рассматриваемого преобразования используется следующая матрица M 10 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 M - - = - - - - 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Матрица M преобразования Уолша с упорядочением по Уолшу для n = Матрица M преобразования Уолша с упорядочением по Уолшу для n = 8 10 Строки матрицы M упорядочены по количеству переходов через нуль за единицу времени Пример Найти преобразование Уолша для последовательности данных X = (1, 2, 0, Решение Подставляя в явном виде матрицу M в формулу получаем 1 2 3 1 1 1 1 1 1,75 1 1 1 1 2 0,25 1 1 1 1 1 0 0,75 4 1 1 1 1 4 1,25 y y y y - - - = = - - - - - Легко убедиться, что обратное преобразование возвращает вектор X. 0 1 2 3 1 1 1 1 1,75 1 1 1 1 1 0,25 2 1 1 1 1 1 0,75 0 4 1 1 1 1 1,25 4 x x x x - - - = = - - - - - Пример окончен. Преобразование Уолша – Адамара (Можно сказать, что это тоже преобразование Уолша, нос другим порядком функций Уолша и, следовательно, строк матрицы преобразования. Будем считать, что нам даны матрицы Адамара второго порядка 2 H и – 2 H. 2 1 1 1 1 H = - 2 1 1 1 1 H - - - = Любую матрицу Адамара порядка 2n можно рекурсивно получить из 2 H как - 42 Pис. 9. Первые восемь функций Уолша с упорядочением по Адамару had(n, θ) (для матрицы преобразования 8×8) = - = = H H H H H M 2 2 2 2 4 - - - - - - = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - = - = = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 4 4 Матрица M преобразования Уолша–Адамара для n = Матрица M преобразования Уолша–Адамара для n = От функций Уолша, упорядоченных по Адамару, можно перейти к функциям Уолша, упорядоченным по Уолшу [6]. Алгоритм перехода состоит из четырех шагов) номер функции Уолша–Адамара представляется в двоичном коде) полученные на шаге 1 векторы преобразуются – биты переставляются в обратном порядке) записанные таким образом номера рассматриваются так, как если бы они были закодированы кодом Грея Иногда требуются коды, у которых следующие друг за другом кодовые слова различаются только одной цифрой водном из разрядов. Преобразование двоичного кода в код Грея Пусть s = g n–1 g n–2 … g 0 – кодовое слово в разрядном двоичном коде Грея, а соответствующая 43 4) полученный на шаге 3 код Грея преобразуется в двоичный код. Номерами функций Уолша упорядоченных по Уолшу являются числа полученные после преобразования двоичного вектора в число. Пример. Постройте код Грея для чисел от 0 до 7. Решение Число Двоичный код Код Грея Число Двоичный код Код Грея 0 (000) (000) 4 (100) (110) 1 (001) (001) 5 (101) (111) 2 (010) (011) 6 (110) (101) 3 (011) (010) 7 (111) (100) Пример окончен. Пример. Постройте преобразование из функций Уолша–Ада- мара в функции Уолша, упорядоченные по Уолшу для первых восьми функций Уолша–Адамара. двоичная запись числа s = b n – 1 b n – 2 … b 0 . Тогда g i может быть получена как g i = b i ⊕ b i + 1 , 0 ≤ i ≤ n – 2, g n – 1 = b n – 1 , символ ⊕ означает сложение по модулю 2. Например, s = 2, тов двоичная запись числа равна 10 и значит b 1 = 1; b 0 = 0. Следовательно, g 1 = b 1 = 1, g 0 = b 0 ⊕ b 1 = 1. Таким образом, число s = 2 в разрядном коде Грея кодируется, как 11. 12 Преобразование кода Грея в двоичный код Пусть g n–1 g n–2 … g 0 – кодовое слово в разрядном двоичном коде Грея, соответствующее двоичному числу b n – 1 b n – 2 … b 0 . Начинаем с цифры самого левого разряда и двигаемся направо, принимая b i = g i , если число единиц, предшествующих g i , четно, и b i = g i (черта обозначает дополнение, если число единиц, предшествующих g i , нечетно. При этом нулевое число единиц считается четным. Например, двоичное число, соответствующее коду Грея 1001011, имеет вид 1110010 и может быть получено следующим образом 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 0 0 1 1 1 1 1 0 1 0 0 1 b b b b b b b g g g g g g g ↓ ↓ ↓ ↓ ↓ ↓ ↓ 44 Решение Номер функции Уолша– Адамара Номер в двоичном коде Двоично- инвертированная запись. Рассматриваем ее как код Грея Преобразование кода Грея в двоичный код Номер функции Уолша, упорядоченной по Уолшу 0 (000) (000) (000) 0 1 (001) (100) (111) 7 2 (010) (010) (011) 3 3 (011) (110) (100) 4 4 (100) (001) (001) 1 5 (101) (101) (110) 6 6 (110) (011) (010) 2 Пример окончен. Алгоритмы сжатия изображений без потерь. Алгоритм При рассмотрении графических файлов студенты сталкиваются с двумя понятиями формат файла и алгоритм сжатия. Заметим, что между форматом графического файла и алгоритмом сжатия нет однозначного соответствия. Например, модификации алгоритма LZW реализованы в огромном количестве фор- LZW реализованы в огромном количестве фор- реализованы в огромном количестве форматов. В тоже время многие современные форматы поддерживают запись с использованием нескольких алгоритмов архивации. Рассмотрим модификацию алгоритма LZW, которая использу- LZW, которая использу- , которая используется в формате Gif. Описание алгоритма проведем по работе Напомним, что формат Gif разрабатывался для изображений, содержащих от 2 до 256 цветов, а файл формата Gif состоит из следующих разделов: a) метка файла) локальная карта цвета; b) описатель экрана) изображение; c) глобальная карта цвета) завершитель файла. d) описатель изображения Следует отметить, что разделы d) –f) могут повторяться в фай- d) –f) могут повторяться в фай) –f) могут повторяться в фай- f) могут повторяться в фай) могут повторяться в файле один и более раз. Изображение хранится как последовательность значений индексов цвета. Пиксели хранятся как строки изображения слева направо. По умолчанию каждая строка изображения записана последовательно, сверху вниз (если строки хранятся в другом порядке, то это не скажется на работе алгоритма Рассмотрим отличия алгоритма сжатия в формате Gif по срав- if по срав- по сравнению со стандартным алгоритмом LZW. › Введен код очистки, который переводит все параметры компрессии или декомпрессии и таблицы в исходное состояние. Значение этого кода равно t 13 › Код конца информации, который явно отмечает конец потока данных изображения. В этом случае алгоритм LZW завершает свою работу. Этот код должен быть последним кодом, который выводится кодировщиком в последовательность кодов. Значение кода конца равно код очистки + 1. › Первый доступный код сжатия равен код очистки + 2. › Выводимые коды имеют переменную длину, начиная с величины размер кода +1 битов на код и до 12 битов на код. Таким образом, максимальное значение кода есть Напомним, что алгоритм LZW работает стремя объектами и при сжатии, и при разжимании поток символов, поток кодов и таблица строк (словарь. Первое, что делается при сжатии, – это инициализация словаря. Дальше используется стандартный алгоритм Поскольку применяемое в формате Gif сжатие выдает последовательность кодов переменной длины (от трех до двенадцати битов каждый, то эти коды должны быть переформатированы в последовательность восьмибитовых байтов. Это дает возможность для дополнительного сжатия изображения. Процесс декомпрессии аналогичен стандартному алгоритму размер кода. Размер кода – сколько битов необходимо для представления множества реальных значений пикселей, обычно это будет тоже значение, что и число битов цвета. У алгоритма существуют ограничения, черно-белые изображения (с одним битом на цвет) должны считаться как имеющие размер кода, равного двум Символ – это индекс, описывающий цвет данного пикселя. 46 3.4. Алгоритмы сжатия изображений с потерями К преимуществам алгоритмов с потерями можно отнести возможность выбора необходимого коэффициента сжатия. Это часто бывает необходимо для адаптации к пропускной способности канала, емкости накопителя и т. д. Разумеется, с ростом коэффициента сжатия качество восстановленного изображения ухудшается. В основе наиболее распространенных современных методов сжатия цифровых изображений с потерями лежат ортогональные декоррелирующие преобразования, осуществляющие разделение элементов данных на составляющие, содержащие основную информацию об изображении и определяющие малозначимые детали. Сжатие происходит за счет удаления составляющих второго типа из преобразованных элементов данных с последующим энтропийным кодированием оставшихся элементов. Если изображение сжимается с применением блочного преобразования, то оно обычно разбивается на блоки размером 8×8 или 16×16 пикселей для ускорения вычислений, поскольку тогда каждый блок преобразуется и обрабатывается отдельно. Понятно, что здесь не учитывается корреляция между блоками изображения, хотя эта корреляция может оказаться серьезным источником информационной избыточности итогового сжатия. подобная схема компрессии Самым распространенным в настоящее время методом сжатия изображений с потерями является JPEG, который основан на квантовании и статистическом кодировании коэффициентов дискретного косинусного преобразования (DCT). Однако данный метод сжатия может быть модифицирован. Рассмотрим подобную схему компрессии статического полутонового изображения. Алгоритм включает следующие этапы › разбивка изображения на блоки 8×8 пикселей; › выполнение одного из рассмотренных дискретных преобразований на полученном блоке элементов изображения для де- корреляции источника 47 › квантование коэффициентов преобразования для снижения визуальной избыточности › энтропийное кодирование проквантованных значений для снижения кодовой избыточности (в качестве примера можно привести одну из модификаций кода Хаффмана). При восстановлении, соответственно, последовательно выполняются статистическое декодирование, деквантование и обратное дискретное преобразование. В работе [10] в качестве подобной рассматривается следующая схема. Рис. 10. подобная схема компрессии В работе [12] в качестве подобной рассматривается схема, где вместо ДПКП используются преобразование Уолша, упорядоченное по Уолшу, и преобразование Уолша–Адамара. Перед тем как мы завершим обсуждение подобной схемы компрессии, необходимо рассмотреть, как изменится ее работа при сжатии цветного изображения. Предположим, что сжимаем битовое изображение, тогда в рассмотренной схеме добавится дополнительный этап цветное изображение из пространства RGB преобразуется в цветовое пространство YCrCb. Выполняем разделение изображения натри полутоновых и сжимаем их независимо друг от друга. Переход к YCrCb обусловлен тем фактом, что глаз чувствителен к малым изменениям яркости пикселей, ноне цветности, поэтому из компоненты цветности можно удалить значительную долю информации для достижения высокого сжатия без заметного визуального ухудшения качества образа. Указанное свойство можно использовать при компрессии для увеличения скорости работы или увеличения качества компрессии (например, при сжатии › › 48 пикселей яркости использовать преобразование DCT, а при сжатии компонентов цветности использовать преобразование ДПКП или преобразования WHT). 3.4.2. Метод усеченного блочного кодирования (УБК) Классическая реализация УБК (другое название метод BTC – Block Truncation Coding), предполагает разбиение изображения на небольшие непересекающиеся прямоугольные куски одинакового размера m × n пикселов называемые блоками [9]. Каждый такой блок обрабатывается независимо от других, поэтому рассмотрим алгоритм обработки одного блока. Алгоритм состоит из нескольких шагов пусть k = m × n, а b 1 , … , b k – яркость соответствующего пиксела в блоке. Вычисляем среднее значение яркости пикселов C и средний квадрат E, где ∑ = = k i i b k C 1 1 и ∑ = = k i i b k E 1 2 1 ; › для каждого блока вычисляем σ 2 = E – C 2 ; › вычисляем пороговое значение яркости b thr , где b thr = C; › определяем уровни квантования и q q k C a - + = + σ , где q – число пикселей яркость которых больше или равна пороговому значению для каждого блока выполняем процесс квантования последующему правилу b b s aåñëè b b + - ≥ = где s i – яркость пиксела i после квантования после квантования получим блок S из k элементов, элементами являются a – или a + . Для дальнейшего сжатия найдем блок заменив в S элементы a – на ноль, а a + соответственно на единицу. В сжатый файл можно отдельно записать числа a – , a + и двоичный вектор ͞S в виде числа, который строится по Алгоритм закончен, если b i ≥ b thr a – , если b i < b thr Таким образом, классический алгоритм BTC делит изображение на маленькие блоки пикселей, а затем сокращает количество уровней яркости в пределах каждого блока. Сокращение обычно выполняется с сохранения у декодируемого и исходного изображения каких-либо характеристик (например среднюю яркость, среднеквадратичное отклонение) или с минимизацией некоторой функции. Студенты должны обратить внимание на то, что классическая схема УБК работает с полутоновыми изображениями, а степень сжатия и качество восстановленного изображения сильно зависят от размеров блока. Отметим, что наиболее удовлетворительные результаты были получены при применении блоков размером 4×4. Пример. Выполнить метод усеченного блочного кодирования для изображения представленного матрицей H, где h ij – яркость соответствующего пикселя. 121 110 56 45 20 200 247 253 16 10 0 150 40 2 5 200 H = Решение Легко заметить, что C ≈ 92,19, σ ≈ 88,68, k = 16, q = 7. Таким образом можно найти 7 92,19 88,68 13,98 9 q a C k q σ - = - = - = - и 9 92,19 88,68 192,74 7 k q a C q σ + - = +После квантования получим матрицу S, битовую матрицу и вектор ͞S: 193 193 14 14 14 193 193 193 14 14 14 193 14 14 14 193 S = , матрица * 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 S = Таким образом в выходной сжатый файл можно записать вектор ͞S = (1,1,0,0,0,1,1,1,0,0,0,1,0,0,0,1) и два значения 193 и Пример окончен. Рассмотренный способ определения порога и уровней квантования не является единственным. Приведем несколько модификаций классического алгоритма ВТС. – Первая модификация (AMBTC) › пороговое значение яркости b thr = C; › уровни квантования * 2 k a C k q α - = - - и * 2 k a C q α + = +где b i – яркость соответствующего пиксела в блоке, k – количество пикселов в блоке , C – среднее значение яркости пикселов, 1 1 k i i b C k α = = - ∑ , q – число пикселей, яркость которых больше или равна пороговому значению. Процесс кодирования и декодирования аналогичен классической реализации BTC. – Вторая модификация › пороговое значение яркости min max 2 thr b b b + = ; › уровни квантования 1 i i b C a b k q - < = - ∑ и 1 i i b C a b q + ≥ = ∑ , где b i – яркость соответствующего пиксела в блоке, b max и b min – максимальная и минимальная яркость в блоке, C – среднее значение яркости пикселов, k – количество пикселей в блоке, q – число пикселей, яркость которых больше или равна пороговому значению. Процесс кодирования и декодирования аналогичен классической реализации Использование УБК для сжатия изображений приводит к целому ряду специфических искажений, основным недостатком которых является то, что теряется информация об изображении, основанная на интенсивности пикселей в каждом блоке (малое число градаций яркости в пределах блока. Следовательно, изображение после УБК может иметь блочный характер Задачи. Используя статистический и динамический метод Хафф- мана, закодируйте слова дерево, переселение, дискуссия. Используя алгоритм LZW, закодируйте слова дискуссия, ассамблея, воевода, после покажите процесс декодирования. Закодируйте числа {10,65,89,110} унарным кодом, кодом Левенштейна, кодом Элайеса и покажите процесс декодировки. 4. Пусть T = 11. Закодируйте числа {10,65,89,110} кодом Го- ломба. 5. Пусть T = 16. Закодируйте числа {10,65,89,110} кодом Го- ломба. 6. Предположим, что нам известны блоки размера 8×8 полутонового черно-белого изображения 130 127 130 131 129 130 131 129 130 129 139 132 135 133 135 133 134 135 136 137 138 139 140 129 129 129 129 129 129 129 129 132 133 134 135 136 137 138 139 129 129 129 129 141 141 141 141 128 132 133 128 132 140 128 125 140 141 142 143 140 141 142 143 231 224 224 217 217 203 189 196 210 217 203 189 203 224 217 224 196 217 210 224 203 203 196 189 210 203 196 203 182 203 182 189 203 224 203 217 196 175 154 140 182 189 168 161 154 126 119 112 175 154 126 105 140 105 119 84 154 98 105 98 105 63 112 Выполните для них LZW кодирование. Предположим, что нам известны блоки размера 8×8 полутонового изображения 224 224 217 217 203 189 196 210 217 203 189 203 224 217 224 196 217 210 224 203 203 196 189 210 203 196 203 182 203 182 189 203 224 203 217 196 175 154 140 182 189 168 161 154 126 119 112 175 154 126 105 140 105 119 84 154 98 105 98 105 63 112 84 150 155 160 165 170 175 180 185 145 150 155 160 165 170 175 180 140 141 142 143 144 145 146 147 145 146 147 148 149 150 151 152 145 147 149 151 153 155 157 159 182 189 168 161 154 126 119 112 175 154 126 105 140 105 119 84 154 98 105 98 105 63 112 Выполните для них дискретное косинусное и псевдокоси- нусное преобразование для n = 8 и n = 4. 52 8. Предположим, что нам известны блоки размера 8×8 полутонового изображения 130 127 130 131 129 130 131 129 130 129 139 132 135 133 135 133 134 135 136 137 138 139 140 129 129 129 129 129 129 129 129 132 133 134 135 136 137 138 139 129 129 129 129 141 141 141 141 128 132 133 128 132 140 128 125 140 141 142 143 140 141 142 143 150 155 160 165 170 175 180 185 145 150 155 160 165 170 175 180 140 141 142 143 144 145 146 147 145 146 147 148 149 150 151 152 145 147 149 151 153 155 157 159 182 189 168 161 154 126 119 112 175 154 126 105 140 105 119 84 154 98 105 98 105 63 112 Выполните для них преобразование Уолша, упорядоченное по Уолшу, и преобразование Уолша–Адамара для n = 8 и n = 4. 9. Закодируйте числа {15,64,89,110,125} кодом Грея. Предположим, что нам известны блоки размера 8×8 полутонового изображения 130 127 130 131 129 130 131 129 130 129 139 132 135 133 135 133 134 135 136 137 138 139 140 129 129 129 129 129 129 129 129 132 133 134 135 136 137 138 139 129 129 129 129 141 141 141 141 128 132 133 128 132 140 128 125 140 141 142 143 140 141 142 143 150 155 160 165 170 175 180 185 145 150 155 160 165 170 175 180 140 141 142 143 144 145 146 147 145 146 147 148 149 150 151 152 145 147 149 151 153 155 157 159 182 189 168 161 154 126 119 112 175 154 126 105 140 105 119 84 154 98 105 98 105 63 112 Выполните для них метод усеченного блочного кодирования (УБК) и модификации УБК. Литература. Сэломон, Д. Сжатие данных, изображений и звука / Д. Сэ- ломон. – М. : Техносфера, 2004. – 367 с. Кудряшов, Б. Д. Теория информации / Б. Д. Кудряшов – СПб. : Питер, 2009. – 320 с. Чернега, В. С. Сжатие информации в компьютерных сетях / В. С. Чернега. – Севастополь : СевГТУ, 1997. – 212 с. Роджерс, Д. Алгоритмические основы машинной графики / Д. Роджерс. – М. : Мир, 1989. – 512 с. Методы сжатия данных : Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. – М. : ДИАЛОГ-МИФИ, 2002. – 384 с. 6. Ахмед, Н. Ортогональные преобразования при обработке цифровых сигналов / Н. Ахмед, КР. Рао. – М. : Связь, 1980. – 248 с. Айфичер, Э, Цифровая обработка сигналов : Практический подход / Э. Айфичер, Б. Джервис. – М. : Вильямс, 2004. – 992 с. Умняшкин, СВ. О модификации дискретного косинусно- го преобразования / СВ. Умняшкин // Известия Тул. гос. унта. Серия : Математика. Механика. Информатика. Вып. 1. – Тула : ТулГУ, 1998. – Т. 4. – С. 143–147. 9. Salomon, D. Data Compression, Springer-Verlag / D. Salo- mon. – L. : London Limited, 2007. – 1093 с. Умняшкин, СВ, Алгоритм сжатия изображений на основе дискретного псевдокосинусного преобразования / СВ. Ум- няшкин, В. В. Курина // Цифровая обработка сигналов. – 2009. – № 3. – С. 2–7. 11. Романов, В. Ю. Популярные форматы файлов для хранения графических изображений на IBM PC / В. Ю. Романов. – М. : Унисех, 1992. – 156 с. Карагодин, МА. Алгоритм сжатия изображений на основе функций Уолша / МА. Карагодин, АН. Осокин // Информационные системы и технологии : материалы межд. конф. ИСТ. – Новосибирск, 2003. – Т. 2. – С. 126–130. Оглавление. Введение 2. Универсальное сжатие 2.1. Неравномерное кодирование дискретных источников 2.1.1. Код Хаффмана 7 2.1.2. Код Шеннона 16 2.1.3. Код Гилберта–Мура 17 2.2. Словарные методы 2.2.1. Алгоритм LZW 18 2.3. Монотонные кода 2.3.1. Унарный код 2.3.2. Код Голомба 24 2.3.3. Код Левенштейна 26 2.3.4. Код Элайеса 28 3. Сжатие изображений 3.1. Введение 3.2. Дискретные преобразования 3.3. Алгоритмы сжатия изображений без потерь 3.3.1. Алгоритм LZW 44 3.4. Алгоритмы сжатия изображений с потерями 3.4.1. подобная схема компрессии 3.4.2. Метод усеченного блочного кодирования (УБК) 48 Задачи 51 Литература 53 Учебное издание Методы сжатия информации текст и изображение Методические указания Составитель Краснов Михаил Владимирович Редактор, корректор М. Э. Левакова Верстка Е. Б. Половковой Подписано в печать 09.10.14. Формат 60×84 Усл. печ. л. 2,56. Уч.-изд. л. Тираж 20 экз. Заказ Оригинал-макет подготовлен в редакционно-издательском отделе ЯрГУ. Ярославский государственный университет им. П. Г. Демидова. 150000, Ярославль, ул. Советская, 14. 56 |