SSP

Введение

Целью данной курсовой работы по дисциплине «Информатика» является разработать алгоритм сжатия изображений без потерь и реализовать его. В процессе работы были изучены теоретические основы алгоритма SSP, проанализированы результаты, даваемые этим алгоритмом, а также был разработан свой алгоритм сжатия изображений на основе алгоритма SSP, который был реализован на объектно–ориентированном языке высокого уровня Java. По окончании работы было произведено тестирование разработанного алгоритма, позволившее оценить его эффективность.

Описание алгоритмов

Компрессия изображения

Компрессия изображения содержит следующие этапы:

1. изображение декодируется в RGB массив;
2. производится фильтрация изображения фильтром Paeth;
3. выполняется прямое преобразование BWT;
4. производится сжатие полученных данных с помощью алгоритма LZW.

Декомпрессия изображения

Декомпрессия изображения содержит следующие этапы:

1. производится декомпрессия данных с помощью алгоритма LZW;
2. выполняется обратное преобразование BWT;
3. производится дефильтрация данных фильтром Paeth;
4. полученные данные кодируются в массив пикселей.

Фильтр Paeth[1]

В системе этот фильтр применяется отдельно для каждого канала цвета. Это преобразование выполняется для всех пикселей, кроме пикселей первой строки и первого столбца. Обозначим пиксели исходного изображения: x - текущий пиксель, a - пиксель, находящийся западнее текущего, b - пиксель, находящийся севернее текущего, c - пиксель, находящийся северо-западнее текущего. Следующая таблица иллюстрирует расположение четырёх соседних пикселей:

c	b
a	x

При фильтрации получим новую матрицу пикселей. Обозначим пиксели фильтрованного изображения: x₁, a₁, b₁, c₁.

c1	b1
a1	x1

Фильтрация

Для каждого фильтруемого пикселя необходимо посчитать три значения:
p_a = |b-c|
p_b = |a-c|
p_c = |a+b-2∗c|
Значение пикселя x₁ определяется из трёх условий:
Если p_a ≤ p_b и p_a ≤ p_c, то x₁ = x-a
Если p_b ≤ p_c, то x₁ = x-b
Если p_b ≥ p_c, то x₁ = x-c

Дефильтрация

Для каждого дефильтруемого пикселя необходимо посчитать три значения:
p_a = |b-c|
p_b = |a-c|
p_c = |a+b-2∗c|
Значение пикселя x определяется из трёх условий:
Если p_a ≤ p_b и p_a ≤ p_c, то x = x₁+a
Если p_b ≤ p_c, то x = x₁+b
Если p_b ≥ p_c, то x = x₁+c

Преобразование BWT (Преобразование Барроуза — Уилера)[2]

Преобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных.

Прямое преобразование

Преобразование выполняется в три этапа. На первом этапе составляется таблица всех циклических сдвигов входной строки. На втором этапе производится лексикографическая сортировка строк таблицы. На третьем этапе в качестве выходной строки выбирается последний столбец таблицы преобразования. Следующий пример иллюстрирует описанный алгоритм: Пусть нам дана исходная строка s=«ABACABA».
http://habrastorage.org/storage1/7ce4ce91/292b10ed/55483ae4/49f57c59.png
Результат вкратце запишем так: BWT(s)=(«BCABAAA», 3), где 3 — это номер исходной строки в отсортированной матрице, так как он может понадобиться для обратного преобразования.

Обратное преобразование

Пусть нам дано: BWT(s)=(«BCABAAA», 3). Тогда выпишем в столбик нашу преобразованную последовательность символов «BCABAAA». Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем «BCABAAA». Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. Алгоритм обратного преобразования описан в таблице ниже:
http://habrastorage.org/storage1/c0b2f7fe/f90b0af8/9ccead14/70a91cc7.png

Алгоритм LZW (Алгоритм Лемпеля — Зива — Велча)[3]

Алгоритм Лемпеля — Зива — Велча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь.

Кодирование

Процесс сжатия выглядит следующим образом. Последовательно считываются символы входного потока и происходит проверка, существует ли в созданном словаре строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в словарь, а поиск начинается снова.
Например, если сжимают байтовые данные, то при инициализации словаря в нём окажется 256 строк (от «0» до «255»). Новые строки формируют словарь последовательно. Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового. Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер.

Декодирование

Декодер начинает с заполнения словаря первыми символами алфавита (в нашем случае их 256). Затем он читает входной файл, который состоит из номеров строк в словаре, использует каждый номер для того, чтобы восстановить несжатые символы из словаря и записать их в выходной файл. Кроме того, он строит словарь тем же методом, что и кодер.
Особенность LZW заключается в том, что для декодирования не нужно сохранять словарь строк в файл для распаковки. Алгоритм построен таким образом, что восстановить словарь строк возможно используя только поток кодов.

Описание разработанной системы

Разработанная система представляет собой консольное приложение, написанное на объектно–ориентированном языке высокого уровня Java. Это приложение позволяет сжимать изображения формата PNG с глубиной цвета равной 24 бита.

Результаты тестирования

Для тестирования использовался набор тестовых изображений[4]:

http://www.researchandtechnology.net/pcif/images/thumbnails/frymire.jpg	http://r0k.us/graphics/kodak/thumbs/kodim05t.jpg	http://r0k.us/graphics/kodak/thumbs/kodim20t.jpg	http://www.researchandtechnology.net/pcif/images/thumbnails/monarch.jpg	http://www.researchandtechnology.net/pcif/images/thumbnails/peppers.jpg	http://www.researchandtechnology.net/pcif/images/thumbnails/sail.jpg	http://www.researchandtechnology.net/pcif/images/thumbnails/tulips.jpg
frymire.png	kodim05.png	kodim20.png	monarch.png	peppers.png	sail.png	tulips.png

Все изображения имеют глубину цвета равную 24 бита. Каждый файл сжимался три раза, время выполнения сжатия вычислялось как среднее арифметическое между полученными значениями. Средний коэффициент сжатия составил 1,32. Полученные результаты представлены в таблице:

Название файла	Размер оригинального файла, пиксели	Объём оригинального файла, КБ	Объём сжатого файла, КБ	Коэффициент сжатия	Время выполнения сжатия, с
frymire.png	1118∗1105	361	524	-	40,44
kodim05.png	768∗512	767	641	1,20	8,09
kodim20.png	768∗512	480	330	1,45	8,37
monarch.png	768∗512	621	479	1,30	7,67
peppers.png	512∗512	441	331	1,33	4,73
sail.png	768∗512	777	629	1,24	7,76
tulips.png	768∗512	691	497	1,39	7,15

Все изображения, за исключением изображения flymire.png, были сжаты. Такой результат можно объяснить тем, что эффективность сжатия, конечно же, зависит от сжимаемых данных. Изображение flymire.png “составлено” из других изображений и не имеет повторяющихся фрагментов. Такой случай является наихудшим для используемых алгоритмов. Именно этим можно объяснить увеличение объёма сжатого файла по сравнению с исходным.