Отправляет email-рассылки с помощью сервиса Sendsay

Фрактальное сжатие изображений

Рассылка закрыта

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Июнь 2010   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
smkibermax@inbox.ru

Статистика

3 подписчиков
0 за неделю
←   Все выпуски   →

Фрактальное сжатие изображений. Революционный алгоритм LenPEG


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

С ресурса фрактального сжатия изображений fic.bos.ru: статья.

Автор: David Morgan, 08 февраля 2006 г.
Добавлено: 17 июня 2010.
Редактор : Максим Лович
Оригинальная статья
Использованы материалы блога Александра Назаровского

Введение

LenPEG является новейшим алгоритмом сжатия изображений, оставляющим далеко позади все существующие и даже еще не изобретенные алгоритмы сжатия изображений.

Цели алгоритма

  • Достижение максимального коэффициента сжатия без потерь для тестовых изображений.
  • Сохранение поддержки предыдущих и будущих версий реализации алгоритмов сжатия изображений.

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

image001Алгоритмы сжатия изображений традиционно апробируются и сравниваются на основе известного тестового изображения. Как известно, общепринятым стандартом в области цифровой обработки изображений является изображение «Lenna»

Классическое изображение Лены имеет размер 512x512 пикселей с тремя цветовыми каналами, каждый из которых содержит 8 бит данных на пиксель. Таким образом, изображение занимает  512*512*3*8 = 6’291’456 бит.

 

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

Магическое число

Файлы LenPEG идентифицируются особой «магической» последовательностью битов в начале, что является стандартным для файлов с изображениями сжатыми при помощи различных алгоритмов. В данном случае возможны такие варианты числовой последовательности:

  • 0
    Данный файл является файлом LenPEG, при условии, что это единственный бит в файловом потоке.
  • 1 <последовательность, идентифицирующая иной алгоритм сжатия>
    Данный файл является файлом, сжатым алгоритмом LenPEG , далее идет поток данных, кодирующий изображение другим способом.

Алгоритм компрессии

С целью достижения максимального коэффициента сжатия для изображений, LenPEG может использовать различные вспомогательные алгоритмы. Рассмотрим работу алгоритма LenPEG более подробно, используя блок схему.

 image002


Алгоритм декомпрессии

Для декомпрессии изображения, сжатого при помощи LenPEG, используется следующий алгоритм.

image003 

Анализ алгоритма

При использовании стандартного теста эффективности алгоритмов сжатия изображений (тестовое изображение Lenna)  метод LenPEGпоказывает наивысшую степень сжатия среди существующих алгоритмов, поскольку результирующий файл имеет размер в 1 бит. Следовательно, коэффициент сжатия равен 6’291’456 к одному. Заметим также, что сжатие тестового изображения происходит без потерь.

На иных изображениях, как ясно видно из блок-схем, результат сжатия при помощи LenPEG будет всего на один бит больше, чем для самого лучшего из известных алгоритмов сжатия. Эта ничтожная разница в один бит, при современных размерах графических файлов в несколько мегабайт, не заслуживает никакого внимания.

Выводы

Итак, выводы очевидны. Алгоритм LenPEG является наиболее эффективным алгоритмом сжатия изображений и результат не может быть превзойден никакими иными методами. Характеристики алгоритма позволяют судить о его полном превосходстве над всеми прочими существующими и даже еще не придуманными алгоритмами сжатия изображений.

LenPEG v2

Трудно поверить, но Туомас Хиено усовершенствовал алгоритм LenPEG. Вот модифицированный алгоритм, предоставим слово автору.

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

Алгоритм сжатия изображений LenPEG 2 включает в себя следующие шаги:

1. Проверка, является ли это изображение тестовым изображением Lenna? Если да – записать пустой файл и выйти. Если нет – переход к следующему шагу.

2. Запросить у пользователя, каким методом сжимать изображение (GIF, JPEG, PNG) и т.д.

3. Использовать указанный алгоритм и сжать искомое изображение при помощи него.

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

(grep "`./smr`" < input || cat lenna) | xv -

Другими словами, если магическая последовательность не найдена – то это изображение Lenna. Если нет – определяем магическую последовательность, затем алгоритм компрессии и используем соответствующий декомпрессор.

Легко видеть, что для стандартного тестового изображения новый алгоритм LenPEG 2 обладает бесконечно большей степенью сжатия, а конкретно 6’291’456 к нулю,вместо 6’291’456 к одному в предыдущей версии. К тому же получаемые сжатые изображения будут на один бит короче, чем в предыдущей версии.

LenPEG v3

Автор первоначального алгоритма разработал Версию 3, которая предоставляет еще большую степень сжатия, отрицательную. Это воистину непобедимый алгоритм.

При получении на входе изображения, алгоритм LenPEG 3 выполняет следующие шаги

1. Это тестовое изображение Lenna? Если да, то удаляем все данные на компьютере. Если нет – переходим к следующему шагу.

2. Запросить у пользователя, каким методом сжимать изображение (GIF, JPEG, PNG) и т.д.

3. Использовать указанный алгоритм и сжать искомое изображение при помощи него. Затем удалить остальную информацию с компьютера.

Чтобы показать изображение декомпрессор использует следующие шаги

1. Если на компьютере нет никаких данных – показываем изображение Lenna.

2. Если на компьютере есть файл с магической последовательностью, применяем к нему соответствующий декодер и показываем результат.

Для стандартного тестового изображения LenPEG 3 сжимает его настолько эффективно, что место на носителе даже освобождается. Точную степень сжатия невозможно посчитать, ибо она зависит от аппаратных характеристик машины, на которой выполняется LenPEG 3. Но, естественно она всегда будет превосходить LenPEG 2, поскольку освобождается место занимаемое и операционной системой, и самой реализацией алгоритма LenPEG 3.

Ссылки

  1. IEEE Professional Communication Society Newsletter Volume 45 №3, May/June 2001//ISSN 0143-433X   http://www.ieeepcs.org
  2. Playboy Magazine. November 1972
  3. www.lenna.org
В избранное