Параметрическое семейство фрактальных текстур

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

Одним из методов сжатия изображений является метод фрактального сжатия. Ключевое свойство, которым обладают фракталы, - это самоподобие. Поэтому основой метода фрактального сжатия является обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. А. Жакен представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков, блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером и рядом других исследователей.

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

В этой связи была поставлена цель работы:

- попробовать использовать при фрактальном кодировании изображений в качестве системы итерируемых функций систему квадратичных кривых Безье.

Во фрактальном сжатии изображений используются IFS специального вида, а именно системы итерируемых кусочно-определённых функций. PIFS состоит из полного метрического пространства X , набора подобластей ^i ^ X ¹ - n и набора сжимающих отображений w * D i ° X ^, i = ^1,‘"’ ⁿ .

~

В качестве wi возьмём систему отображений с использованием квадратичных кривых Безье, задаваемых формулой:

w ( X , y )

u ( x ) = a ₀ (1 - x )² + 2 a_xx (1 - x ) + a₂x ², 1

. v ⁽ y ) = b o ^{(1 -} y ) ^{+ 2 Ь} 1 У ⁽¹ - y ) ⁺ b 2 y ,

При отображении с использованием квадратичных кривых Безье прямолинейная область переходит в прямолинейную, криволинейная область - в криволинейную.

При фрактальном кодировании изображений мы пытаемся найти множество сжимающих преобразований, которые отображают доменные блоки (которые могут перекрываться) в множество ранговых блоков, которые покрывают изображение.

Попробуем теперь осуществить фрактальное кодирование изображения с использованием квадратичных кривых Безье. Исследование осуществим в программе SciLab.

Разобьём изображение f на неперекрывающиеся ранговые блоки {Ri}. Используем метод квадродерева. Устанавливаем максимальную глубину квадродерева равной шести и допустимую погрешность 0,04.

Теперь покрываем изображение размерности 128х128 (после применения к нему выборки) последовательностью доменных блоков – прямоугольников. Количество строк и столбцов устанавливаем равными 16. Горизонтальное и вертикальное перекрывания выбираем половинными. Таким образом, общее количество доменов равно 16*16+15*16+16*15+15*15=961.

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

Коэффициенты a0, a1, a2, b0, b1, b2 определим при переводе координат доменного блока в координаты соответствующего рангового блока.

W x, y )

После этого отображаем каждую точку

⁽ x , y )

доменного блока в

Посредством интерполяции определяем значения пикселов в

доменном блоке после отображения. Размер доменного блока для соответствия ранговой области в этой точке сжимается. Далее вычисляем контрастность и яркость.

Безье  aaabbb, значения яркости o и контрастности s. После этого переходим к следующему ранговому блоку (если остались ещё непокрытыми ранговые блоки).

Если же достаточно точного соответствия не получилось, то разбиваем ранговые блоки на меньшие ранговые блоки и продолжаем процесс до тех пор, пока или не добьёмся приемлемого соответствия, или не будет достигнута максимальная глубина квадродерева.

Таким образом, в файле для каждого рангового блока записываются 9 чисел. В результате кодирования было покрыто 2659 ранговых блоков, таким образом в файле «kod.dat» содержится 2659*9=23931 число. Само изображение имеет размерность 256*256=65536. Тогда отношение размерности закодированного изображения к размерности исходного равно 23931

≈ 0,3

65536 . Таким образом, отображение W является сжимающим.

Для реализации итерационной схемы декодирования определим два массива изображений: domen и im. В качестве массива domen можно взять любое произвольное изображение. Содержимое каждого рангового блока вычисляется применением преобразования к соответствующему ранговому блоку. Результирующие значения пикселов рангового блока хранятся в массиве im. Одна итерация завершается, когда обработаны все ранговые блоки. Перед началом новой итерации необходимо заменить массив domen массивом im, массив im очистить.

В качестве начального изображения можно взять однородное серое.

Другое исходное изображение

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

Средняя пиксельная ошибка после предварительного сжатия обоих изображений до размеров 64х64 равна 0,026.

Стандартная количественная оценка искажений для сжатого изображения 25,4Дб.