Описывается фрактальный алгоритм сжатия изображений с потерями, имеющий значительно меньшие, чем аналоги, временные затраты

Вид материала

Документы

Подобный материал:

• Тезисы к докладу «Вейвлетное (wavelet) сжатие. Jpeg2000», 11.1kb.
• 1. Адаптивный алгоритм сжатия телемеханических данных, 21.8kb.
• Обработка и передача изображений, 164.04kb.
• Программа дисциплины Комбинаторные методы сжатия данных Семестр, 8.35kb.
• Цифровая обработка многомерных сигналов, 307.08kb.
• Алгоритмы архивации с потерями, 96.34kb.
• Безотметочное обучение осуществляется не только в 1-х, но и во 2-х классах, 338.5kb.
• На 23/29 заседании Комиссий рсс по эмс рэс и рв 20. 09. 2007, 96.09kb.
• Новый способ архивирования данных передаем фильм с помощью sms, 198.04kb.
• «Проектирование микропроцессорных систем», 183.64kb.

П.М. КАРПОВ

Московский инженерно-физический институт (государственный университет)


БЫСТРЫЙ ФРАКТАЛЬНЫЙ АЛГОРИТМ СЖАТИЯ

ИЗОБРАЖЕНИЙ


Описывается фрактальный алгоритм сжатия изображений с потерями, имеющий значительно меньшие, чем аналоги, временные затраты.


Наибольшее распространение среди фрактальных методов сжатия получил метод Итерируемых Систем Функций (Iterated Functions System – IFS). Суть его заключается в следующем: ищется сжимающее отображение, переводящее изображение в себя же. Так как отображение сжимающее, то после многократного применения его к любому начальному изображению в результате будет получено изображение, близкое к исходному.

Таким образом, для восстановления изображения достаточно сохранить лишь отображение. Так как количество возможных отображений огромно, на практике поступают следующим образом: разбивают всё изображение на (возможно, перекрывающиеся) доменные блоки Di и неперекрывающиеся ранговые блоки Ri, заполняющие всё изображение. Затем для каждого рангового блока производится поиск доменного блока и преобразования, наилучшим образом переводящего Di в Ri. Класс преобразований обычно ограничен аффинными преобразованиями – масштабирование, отражение, вращение, яркость/контраст. Для разбиения на доменные блоки часто используется метод квадродерева, состоящий в рекурсивном разбиении одного доменного блока на несколько (обычно 4) при превышении ошибки в этом блоке некоторого значения.

Несмотря на высокую степень сжатия, фрактальные методы не получили широкого распространения главным образом из-за большого времени кодирования: компрессия одного изображения на ПК может занимать несколько часов. Число блоков обоих типов растёт пропорционально размеру изображения и таким образом временные затраты пропорциональны квадрату размера изображения (в байтах).

Предлагаемый метод в отличие от других методов ускорения фрактального сжатия (см. [1]) использует специфику изображений, в частности – свойство локальности: значение пиксела заметно коррелирует лишь со значениями близких ему пикселов. Рассмотрение показывает, что в случае края или градиента, поиск доменных блоков имеет смысл производить лишь вблизи рассматриваемого рангового блока. Таким образом, разбиение на доменные блоки не является фиксированным. Временные затраты в этом случае пропорциональны первой степени размера изображения. Сжатие типичного изображения занимает от нескольких секунд до нескольких минут.

Оценочно, по качеству сжатия алгоритм находится на уровне JPEG, но в отличии от него и вэйвлет - методов, предлагает дополнительные возможности такие, как качественная интерполяция и очистка от шума.


Список литературы

1. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Триумф, 2003.
   
2. Методы сжатия данных / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. М.: Диалог–МИФИ, 2002.