Приводятся MAXScript-программы фрактального сжатия изображения и его последующего восстановления.
При фрактальном сжатии изображения для области меньшего размера подыскивается похожая на нее область большего размера того же изображения (рис. 1).
Рис. 1. Доменный и ранговый блоки
Область большого размера называется доменным блоком, а меньшего – ранговым блоком.
Перевод доменного блока в ранговый осуществляется посредством аффинных преобразований, которые в случае изображения в оттенках серого цвета можно представить следующей системой уравнений:
где x, y, z – соответственно координаты и яркость пикселя доменного блока;
x*, y*, z* – соответственно координаты и яркость пикселя рангового блока;
a, b, c, d, e, f – коэффициенты преобразований координат на плоскости;
u – коэффициент сжатия яркости;
v – сдвиг по яркости.
В рассматриваемых алгоритмах фрактального сжатия и восстановления изображения введенные упрощения позволяют заменить матричные преобразования операциями изменения ориентации доменного блока и операциями расчета яркости пикселей. Изменения ориентации доменного блока осуществляется за счет его поворота на угол кратный 90° и зеркального отражения и поворота зеркального отражения.
Из всех возможных доменных блоков выбирается блок, ближайший (в выбранной метрике) к рассматриваемому ранговому блоку.
Когда доменный блок найден, то запоминаются его номер и параметры преобразования в текущий ранговый блок, из которых и состоит решение задачи фрактального сжатия.
Использованный алгоритм фрактального сжатия относится к разряду тестовых. Он содержит следующие ограничения:
Результатами поиска доменного блока являются:
Совокупность параметров, найденная для всех ранговых блоков, образует систему итерируемых функций. Для восстановления изображения берется произвольная начальная картинка: ее каждый ранговый блок восстанавливается по соответствующему, найденному в процессе сжатия доменному блоку.
Геометрия и размеры блоков влияют на качество результата и время его получения.
Среди всех возможных доменных блоков в качестве решения берется блок, наиболее близкий к рассматриваемому ранговому блоку. Используется следующая метрика. Сдвиг по яркости берется равным
где n – число пикселей в строке (столбце) рангового блока;
rij – значение пикселя рангового блока;
dij – значение усредненного пикселя доменного блока;
u – коэффициент сжатия яркости (u = 0.75).
Расстояние между доменным и ранговым блоками вычисляется по следующей формуле:
-- Перебор пикселей рангового блока;
-- вычисление расстояния между текущими ранговым и доменным блоками;
-- поиск оптимальных параметров преобразования
fn trtRrDp btmp u v nP2 xSR xER ySR yER arrDP rntCrrnt kDFSCrrnt &kDFS &rnt &vFS &dMn = (
local d, kD
d = 0
kD = 0
for yR = ySR to yER do (
for xR = xSR to xER do (
kD += 1
arrT = getPixels btmp [xR, yR] 1
rP = arrT[1].r
d0 = u * arrDP[kD] + v - rP
d += d0 * d0
)
if d >= dMn do exit
)
if d < dMn do (
-- Номер искомого доменного блока
kDFS = kDFSCrrnt
-- Ориентация искомого доменного блока
rnt = rntCrrnt
-- Сдвиг по яркости между ранговым и искомым доменным блоками
vFS = v
-- Текущее минимальное расстояние между ранговым и доменными блоками
dMn = d
)
)
-- Поворот доменного блока на 90° (mkRt = true)
-- Зеркальное отражение доменного блока относительно оси Y (mkRt = false)
fn rtArrDp nP2 nP22 arrDP mkRt = (
local k, k2
arrDPT = #()
if mkRt then
for k = nP2 to 1 by -1 do
for k2 = k to nP22 by nP2 do (
arrDPT = append arrDPT arrDP[k2]
)
else
for k = 1 to nP2 do
for k2 = nP2 to 1 by -1 do
arrDPT = append arrDPT arrDP[k2 + (k - 1) * nP2]
return arrDPT
)
strt = timeStamp()
clearListener()
-- Файл с исходным образом
fnBtmp = "d:/chstC.bmp"
-- Файл с результатом
fnTpt = "d:/chstFsC.txt"
btmp = openBitMap fnBtmp
h = btmp.height
w = btmp.width
-- Коэффициент сжатия яркости
u = 0.75
-- Коэффициент сжатия изображения
cmprssn = 2
-- Число пикселей в стороне доменного блока
nP = 20
-- Число пикселей в стороне рангового блока
nP2 = nP / cmprssn
nP22 = nP2 * nP2
-- Число доменных блоков по осям X и Y
nDX = w / nP
nDY = h / nP
-- Число ранговых блоков по осям X и Y
nDX2 = nDX + nDX
nDY2 = nDY + nDY
-- Начальное расстояние между ранговым и доменным блоками
dMnS = 255 * 255 * nP22
-- Ищем усредненную яркость каждого рангового блока
-- Результат храним в массиве arrZR
arrZR = #()
for kR = 1 to nDY2 do (
ySR = (kR - 1) * nP2
yER = ySR + nP2 - 1
for kR2 = 1 to nDX2 do (
xSR = (kR2 - 1) * nP2
xER = xSR + nP2 - 1
zR = 0
for yR = ySR to yER do
for xR = xSR to xER do (
arrT = getPixels btmp [xR, yR] 1
zR += arrT[1].r
)
arrZR = append arrZR (zR / nP22)
)
)
-- Ищем усредненную яркость каждого доменного блока
-- Результат храним в массиве arrZD
arrZD = #()
-- Формируем массив значений яркости пикселей всех доменных блоков
-- Массив arrDPLL состоит из массивов, отвечающих доменным блокам
arrDPLL = #()
for k = 1 to nDY do (
yS = (k - 1) * nP
yE = yS + nP - 2
for k2 = 1 to nDX do (
xS = (k2 - 1) * nP
xE = xS + nP - 2
zD = 0
arrDP = #()
for y = yS to yE by 2 do
for x = xS to xE by 2 do (
arrT = getPixels btmp [x, y] 2
arrT2 = getPixels btmp [x, y + 1] 2
clr = 0
-- Формируем усредненный пиксель доменного блока
for k3 = 1 to 2 do
clr += arrT[k3].r + arrT2[k3].r
clr /= 4
zD += clr
-- Массив усреденных пикселей
arrDP = append arrDP clr
)
arrZD = append arrZD (zD / nP22)
arrDPLL = append arrDPLL arrDP
)
)
-- Массив параметров преобразования
arrDFS = #()
-- Номер текущего рангового блока
kRCrrnt = 0
-- Берем поочередно все ранговые блоки
for kR = 1 to nDY2 do (
ySR = (kR - 1) * nP2
yER = ySR + nP2 - 1
for kR2 = 1 to nDX2 do (
kRCrrnt += 1
zR = arrZR[kRCrrnt]
xSR = (kR2 - 1) * nP2
xER = xSR + nP2 - 1
kDFSCrrnt = 0
-- Искомый номер доменного блока
kDFS = 0
-- Искомая ориентация доменного блока
rnt = 0
-- Искомый сдвиг по яркости
vFS = 0
-- Текущее расстояние между ранговым и доменным блоками
dMn = dMnS
-- Берем поочередно все доменные блоки в 8-и ориентациях
for k = 1 to nDY do
for k2 = 1 to nDX do (
kDFSCrrnt += 1
-- Массив пикселей исходного доменного блока
arrDP = arrDPLL[kDFSCrrnt]
-- Массив пикселей зеркально отраженного доменного блока
arrDP4 = rtArrDp nP2 nP22 arrDP false
zD = arrZD[kDFSCrrnt]
-- Текущий сдвиг по яркости между ранговым и доменным блоками
v = zR - u * zD
for rntCrrnt = 0 to 7 do
if rntCrrnt < 4 then (
trtRrDp btmp u v nP2 xSR xER ySR yER arrDP rntCrrnt kDFSCrrnt &kDFS &rnt &vFS &dMn
-- Поворот доменного блока на 90°
if rntCrrnt < 3 do arrDP = rtArrDp nP2 nP22 arrDP true
)
else (
trtRrDp btmp u v nP2 xSR xER ySR yER arrDP4 rntCrrnt kDFSCrrnt &kDFS &rnt &vFS &dMn
-- Поворот зеркально отраженного доменного блока на 90°
if rntCrrnt < 7 do arrDP4 = rtArrDp nP2 nP22 arrDP4 true
)
)
arrDFS = append arrDFS [kDFS, rnt, vFS]
format "% %\n" kR kR2
)
)
close btmp
fs = openFile fnTpt mode:"w"
-- Вывод результата в текстовый файл
for fsD in arrDFS do
format "% % %\n" (fsD[1] as integer) (fsD[2] as integer) (fsD[3] as integer) to: fs
tm = (timeStamp() - strt) / 1000.0
close fs
За изменение ориентации доменного блока отвечает функция rtArrDp. Результаты ее тестирования на матрице 5×5 приведены на рис. 2 (показаны исходный блок и его повороты на 90, 180 и 270°) и на рис. 3 (показаны зеркальное отражение исходного блока и повороты зеркального отражения на 90, 180 и 270°).
Рис. 2. Ориентации 0, 1, 2 и 3
Рис. 3. Ориентации 4, 5, 6 и 7
Декомпрессия производится следующим образом. Выбирают начальное изображение. Инициатор разбивается на множество ранговых блоков; их число равно числу ранговых блоков в исходном изображении.
В качестве начального может быть взято любое изображение, например черное: соответствующий математический аппарат гарантирует сходимость последовательности изображений, получаемых в ходе употребления системы итерируемых функций, к неподвижному изображению. Обычно для этого достаточно не более 20 итераций.
Размеры восстанавливаемого и исходного изображений могут различаться.
Восстановление изображения происходит по следующей схеме:
Эта схема используется для каждого рангового блока до стабилизации изображения: новые итерации практически не меняют текущего изображения.
Восстановление изображения обеспечивает следующий, основанный на приведенной схеме MAXScript-код:
-- Поворот доменного блока на 90° (mkRt = true)
-- Зеркальное отражение доменного блока относительно оси Y (mkRt = false)
fn rtArrDp nP2 nP22 arrDP mkRt = (
local k, k2
arrDPT = #()
if mkRt then
for k = nP2 to 1 by -1 do
for k2 = k to nP22 by nP2 do (
arrDPT = append arrDPT arrDP[k2]
)
else
for k = 1 to nP2 do
for k2 = nP2 to 1 by -1 do
arrDPT = append arrDPT arrDP[k2 + (k - 1) * nP2]
return arrDPT
)
strt = timeStamp()
clearListener()
-- Файл с результатом (со сжатым изображением)
fnTpt = "d:/chstFsC.txt"
-- При тестировании берем изображение того же размера, что и исходное
fnBtmp = "d:/chst.bmp"
btmp = openBitMap fnBtmp
h = btmp.height
w = btmp.width
close btmp
u = 0.75
nP = 20
nP2 = nP / 2
nDX = w / nP
nDY = h / nP
nDX2 = nDX + nDX
nDY2 = nDY + nDY
fs = openFile fnTpt mode:"r"
-- Заносим параметры преобразований в массив arrDFS
arrDFS = #()
while not eof fs do (
sRd = readLine fs
arrT = filterString sRd " "
arrDFS = append arrDFS (point3 (arrT[1] as integer) (arrT[2] as integer) (arrT[3] as integer))
)
close fs
-- Создаем растровый образ размера w * h пикселей
-- Изначально образ залит серым цветом
btmp = bitmap w h color:gray
-- Выполняем 10 итераций по восстановлению образа
for kFS = 1 to 10 do (
print kFS
kRCrrnt = 0
-- Берем поочередно все ранговые блоки
for kR = 1 to nDY2 do (
ySR = (kR - 1) * nP2
yER = ySR + nP2 - 1
for kR2 = 1 to nDX2 do (
xSR = (kR2 - 1) * nP2
xER = xSR + nP2 - 1
kRCrrnt += 1
kDFS = arrDFS[kRCrrnt][1]
rnt = arrDFS[kRCrrnt][2]
vFS = arrDFS[kRCrrnt][3]
-- Вычисляем координаты k и k2 найденного при сжатии доменного блока
k = ((kDFS - 1) / nDX) as integer
k2 = (kDFS - k * nDX) as integer
yS = k * nP
yE = yS + nP - 2
xS = (k2 - 1) * nP
xE = xS + nP - 2
arrDP = #()
-- Формируем массив arrDP усредненных пикселей доменного блока
for y = yS to yE by 2 do
for x = xS to xE by 2 do (
arrT = getPixels btmp [x, y] 2
arrT2 = getPixels btmp [x, y + 1] 2
clr = 0
for k3 = 1 to 2 do
clr += arrT[k3].r + arrT2[k3].r
clr /= 4
arrDP = append arrDP clr
)
-- Выполняем при необходимости зеркальное отражение доменного блока
if rnt > 4 do (
arrDP = rtArrDp nP2 nP22 arrDP false
rnt -= 4
)
-- Выполняем при необходимости повороты доменного блока
for k = 1 to rnt do arrDP = rtArrDp nP2 nP22 arrDP true
-- Восстанавливаем пиксели рангового блока
kD = 0
for yR = ySR to yER do
for xR = xSR to xER do (
kD += 1
clr = u * arrDP[kD] + vFS
setPixels btmp [xR, yR] #((color clr clr clr))
)
)
)
)
tm = (timeStamp() - strt) / 1000.0
-- Показываем результат
display btmp
Проверка программ выполнена на простых, подобных приведенному на рис. 4 изображениях.
Рис. 4. Тестовое изображение
Размер образа 240×200 пикселей.
Первый тест выполнен при размере стороны доменного блока nP = 20 пикселей, второй – при размере стороны доменного блока nP = 10 пикселей. В обоих случаях выполнено 10 итераций (цикл с параметром kFS).
Результаты показаны на рис. 5 и 6.
Рис. 5. Восстановленное изображение (nP = 20, 10 итераций)
Рис. 6. Восстановленное изображение (nP =10, 10 итераций)
Низкое качество сжатия не присуще рассматриваемому методу, а обусловлено принятыми упрощениями.
Время сжатия при nP = 20 равно около 50 с, а при nP = 10 время сжатия составляет около 300 с. Ввиду простоты исходного изображения повороты доменного блока и его зеркальное отражение не выполнялись.
В данной реализации временные характеристики не являются показательными, поскольку известно, что MAXScript – это не самый быстрый язык программирования.
Для упрощения выходные данные записывались в виде целых чисел. На самом деле для представления набора параметров достаточно 27 бит: 16 бит для задания номера доменного блока, 3 бита для указания ориентации и последние 8 бит для сдвига по яркости.
Несмотря не нетривиальность алгоритма фрактального сжатия изображения программа его реализующая достаточно проста, она содержит чуть более 150 строк кода. Еще проще программа декомпрессии (около 100 строк кода).