Алгоритм сжатия изображения FELICS

Размещено на http://www.allbest.ru/

FELICS

(Fast and Efficient Lossless Image Compression System)

FELICS

Рисунок 1 - Блок-схема алгоритма на микроуровне

1 шаг: инициализация начальных параметров алгоритма

Исходное изображение:

где - яркость пикселя с координатами ;

- размеры изображения.

Порядок считывания пикселей - строками (начиная с верхней). Каждый пиксель обрабатывается по отдельности.

Выбор соседних пикселей для сжимаемого пикселя:

P - яркость сжимаемого пикселя, N1 и N2 - яркости пикселей окрестности

Рисунок 2 - Расположение пикселей, используемых при сжатии каждого нового пикселя

2 шаг: выполнение условия сохранения значений пикселей исходного изображения

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

3 шаг: вычисление разности максимального и минимального значений пикселей окрестности

,

где - минимальное значение яркости пикселей из окрестности;

- максимальное значение яркости пикселей из окрестности.

4 шаг: определение местоположения значения сжимаемого пикселя по отношению к промежутку

- переход к шагу 5.1;

- переход к шагу 5.2;

- переход к шагу 5.3.

5 шаг: кодирование сжимаемого пикселя

5.1 Кодирование пикселя в случае, когда :

-целые значения, которые необходимо закодировать.

Бинарный код - код, кодовые слова которого - числа, представленные в двоичной форме.

Префиксный код - код, любое кодовое слово которого не является началом какого-либо другого кодового слова.

-

длина кодовых слов бинарного кода, если .

Длина кодовых слов префиксного кода, если :

-

для чисел в центре интервала ;

-

для крайних значений интервала .

Кодовое слово сжатого пикселя: первый бит - 1(0) - означает нахождение внутри интервала ; остальные биты - кодовое слово построенного кода, соответствующее значению, равному .

Переход к шагу 3.

5.2 Кодирование пикселя в случае, когда :

-

значения (целые), которые необходимо закодировать.

Коды Голомба (Райс-коды как частный случай):

кодовое слово состоит из двух частей:

- левая часть - унарный код длиной ,

где - кодируемое целое число,

- параметр кода ( );

- правая часть - 1) для (Райс-коды):

бинарный код значений длиной ;

2) для :

если - код длиной бит;

если - код длиной бит,

где .

Унарный код - кодовое слово содержит единиц и ноль, следующий после единиц.

Рисунок 2 - Коды Голомба для некоторых значений n и m

Подбор параметра кода для кодирования каждого нового пикселя:

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

Кодовое слово сжатого пикселя: первый бит - 0(1) - означает то, что ; второй бит - 0(1) - означает то, что ; остальные биты - кодовое слово построенного кода, соответствующее значению, равному .

Переход к шагу 3.

5.3 Кодирование пикселя в случае, когда :

-

значения (целые), которые необходимо закодировать.

Кодовое слово сжатого пикселя: первый бит - 0(1) - означает то, что ; второй бит - 1(0) - означает то, что ; остальные биты - кодовое слово построенного кода, соответствующее значению, равному .

Переход к шагу 3.

Рисунок 3 - Кодирование пикселя в зависимости от местоположения значения его яркости по отношению к промежутку

6 шаг: конечный результат работы алгоритма

,

где - значения яркости первых двух пикселей (в двоичной форме);

- кодовое слово сжатого пикселя.

Прогрессивный FELICS

Использует иерархический способ обработки пикселей:

Рисунок 4 - Иерархический способ обработки пикселей

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

Для кодирования каждого нового пикселя используется окрестность из четырех пикселей, из которых выбираются два со средними значениями. На основании этих двух пикселей производится обработка нового пикселя такая же, как и в FELICSе.

Помимо используемых ранее кодов используются также новые коды - субэкспоненциальные:

-

число единиц унарного кода левой части кодового слова,

где k - параметр Райс-кода,

- число бит бинарного кода правой части.

Длина кодовых слов данного кода, в отличие от кодов Голомба, растет логарифмически.

Рисунок 5 - Субэкспоненциальные коды для некоторых значений n и k

Экспериментальные результаты работы алгоритмов

В таблицах 1 - 4 используются усредненные значения параметров для всех используемых в эксперименте изображений.

Таблица 1 - Результаты работы прогрессивного FELICS при использовании различных префиксных кодов

где

- коэффициент сжатия;

- среднее число бит на пиксель в сжатом изображении;

- неэффективность, %;

- производительность, тыс. пикселей/с.

Таблица 2 - Результаты работы прогрессивного FELICS при использовании различных масштабирующих коэффициентов s

где s (scaling factor) - число, на которое в конце уровня делятся все произведенные вычисления.

Таблица 3 - Результаты работы прогрессивного FELICS при использовании различных значений f (freezing level)

где f (freezing level) - значение длины кодового слова.

сжатие изображение потеря алгоритм пиксель

Таблица 4 - Сравнительные результаты работы различных алгоритмов

где high compression mode - использует коды Голомба без freezing;

fast mode - использует Райс-коды с f=1024;

MLP - метод сжатия, использующий иерархический способ обработки пикселей.

Таблица 5 - Коэффициенты сжатия при работе различных алгоритмов

Рисунок 5 - Изображения, используемые в эксперименте

Выводы: FELICS, по сравнению со стандартным методом сжатия изображений - JPEG, позволяет чуть больше сжать изображение и при этом работает в пять раз быстрее. Прогрессивный FELICS сжимает изображения примерно на 1% лучше, чем FELICS, но работает только в два раза быстрее, чем JPEG.

Размещено на Allbest.ru