Целью работы является проверка возможности использования разбиения Вороного, а точнее его частного случая, в задаче фрактального сжатия изображения.
Рассматривается вариант разбиения области посредством правильных шестиугольников. Такой подход достаточно просто реализуем и при точной настройке кода позволяет получить практически значимые результаты. Выполнение такой настройки, однако, выходит за рамки настоящей работы.
В традиционном алгоритме фрактального сжатия исходное изображение разбивается на прямоугольные или квадратные доменные и ранговые области (см. работу Фрактальное сжатие изображений).
В настоящей работе в качестве доменных и ранговых блоков берутся правильные шестиугольники (рис. 1 и рис. 2). Такое разбиение области сжимаемого изображения является частным случаем разбиения Вороного, с некоторыми аспектами которого можно познакомиться в работе Разбиение 3D-объекта на многогранники Вороного.
Рис. 1. Разбиение области правильными шестиугольниками
Рис. 2. Ранговые блоки
Задача фрактального сжатия заключается в выборе для каждого рангового блока такого доменного блока, при сжатии которого наблюдается наибольшее сходство этого блока с текущим ранговым блоком.
Поскольку часть области (эта часть выделена синим цветом) не покрывается шестиугольниками, то желательно, чтобы изображение находилось в пределах приведенного на рис. 1. красного прямоугольника. Для этого перед разбиением исходное изображение следует поместить в область большего размера, называемую далее рабочей областью. Пусть размеры такой области равны h2 и w2, тогда функция, обеспечивающая перенос исходного изображения в рабочую область, запишется следующим образом:
-- Переносит исходный образ в рабочую область
fn mvBtmp2 btmp h w h2 w2 = (
-- Создаем растровый образ размера w2 * h2
btmp2 = bitmap w2 h2 color: white
hS = (0.5 * (h2 - h)) as integer
wS = (0.5 * (w2 - w)) as integer
for k = 0 to w - 1 do setPixels btmp2 [wS, hS + k] (getPixels btmp [0, k] w)
close btmp
return btmp2
)
-- Проверка функции
-- Файл с исходным образом
fnBtmp = "d:/pawn.bmp"
btmp = openBitMap fnBtmp
btmp2 = mvBtmp2 btmp btmp.Height btmp.Width (1.2 * btmp.Height) (1.5 * btmp.Width)
-- Просмотр результата
display btmp2
Разбиение выполняет функция dvdBtm. Функция dfnDRSz определяет исходные (h и w) и рабочие (h2 и w2) размеры обрабатываемой области, а также число доменных блоков по высоте и ширине (nH и nW) рабочей области.
-- Вычисляет исходные и рабочие размеры сжимаемого образа
-- и число доменных блоков по высоте и ширине рабочей области
fn dfnDRSz btmp r r2 &h &w &h2 &w2 &nH &nW = (
h = btmp.Height as float
w = btmp.Width as float
-- Диаметр описанной окружности доменного блока
d = 2 * r
-- Целочисленный диаметр вписанной окружности доменного блока
d2 = 2 * r2
-- Число доменных блоков по высоте образа
nH = ceil ((h + d2) / d2) as integer
-- Уточняем рабочую высоту образа
h2 = d2 * nH
-- Рабочая ширина образа
w2 = w + 0.5 * d
-- Число доменных блоков по ширине образа
nW = ceil ((w2 - 0.25 * d) / (0.75 * d)) as integer
-- Уточняем рабочую ширину образа
w2 = 0.75 * nW * d + 0.25 * d
)
-- Выполняет вывод доменных (ранговых) блоков
fn dvdBtm r r2 nH nW h2 w2 tm m clr = (
local nH2
-- Диаметр описанной окружности блока
d = 2 * r
-- Целочисленный диаметр вписанной окружности блока
d2 = 2 * r2
x = -w2 / 2 + r
arrP = #()
for k = 1 to nW do (
z = -h2 / 2 + (if mod k 2 == 0 then 2 * r2 else r2)
nH2 = if mod k 2 == 0 then nH - 1 else nH
ps = [x, 0, z]
for k2 = 1 to nH2 do (
nGon radius:r nsides:6 scribe:1 pos:ps transform:tm wireColor:clr \
render_renderable:on render_displayRenderMesh:on render_thickness:1.0
ps += [0, 0, d2]
append arrP ps
)
x += (1.5 * r)
)
-- Файл с координатами центров доменных (ранговых) блоков
fnTpt = "d:/" + (if m == 2 then "rng" else "dmn") + ".txt"
fs = openFile fnTpt mode:"w"
-- Вывод координат центров блоков в текстовый файл
for ps in arrP do format "% % %\n" ps[1] ps[2] ps[3]to: fs
close fs
return arrP
)
-- Разбиение на доменные (ранговые) блоки
delete $*
-- Исходные размеры сжимаемого образа
h = w = 0
-- Рабочие размеры сжимаемого образа
h2 = w2 = 0
-- Число доменных блоков по высоте и ширине рабочей области образа
nH = nW = 0
-- Файл с исходным образом
fnBtmp = "d:/pawn.bmp"
btmp = openBitMap fnBtmp
-- Диаметр описанной окружности доменного блока
r = 20
-- Радиус вписанной окружности доменного блока
r2 = (0.5 * r * sqrt 3.0) as integer
-- Находит исходные и рабочие размеры сжимаемого образа,
-- а также число доменных блоков по высоте и ширине рабочей области
dfnDRSz btmp r r2 &h &w &h2 &w2 &nH &nW
tm = matrix3 [1,0,0] [0,0,1] [0,-1,0] [0,0,0]
-- Вывод габаритного прямоугольника рабочей области
rectangle length:h2 width:w2 transform:tm wireColor:black \
render_renderable:on render_displayRenderMesh:on render_thickness:2
-- Вывод габаритного прямоугольника исходной области
rectangle length:h width:w transform:tm wireColor:red \
render_renderable:on render_displayRenderMesh:on render_thickness:2
-- Вывод доменных блоков
dvdBtm r r2 nH nW h2 w2 tm 1 blue
-- Радиус описанной окружности рангового блока
rR = 0.5 * r
-- Радиус вписанной окружности рангового блока
rR2 = (0.5 * rR * sqrt 3.0) as integer
-- Число ранговых блоков по высоте и ширине образа
nHR= 2 * nH
nWR = 2 * nW
-- Вывод ранговых блоков
dvdBtm rR rR2 nHR nWR h2 w2 tm 2 orange
Варьируемыми параметром является радиус r описанной окружности доменного блока. Радиус задается в пикселях как четное число.
Радиус описанной окружности рангового блока равен r / 2. При позиционировании блоков по вертикали берется целая часть радиуса r2 вписанной окружности блока. Это обеспечивает в общем случае небольшое перекрытие блоков.
Результат работы программы для образа с размерами 162 * 200 пикселей при r = 20 показан на рис. 3.
Рис. 3. Разбиение образа на доменные и ранговые блоки
Красный прямоугольник – это очертание исходного образа.
Как видно из рис. 3, часть ранговых блоков находится за пределами исходного образа. Эти блоки при выполнении сжатия могут быть пропущены.
После восстановления изображения следует вернуться к размерам исходного образа.
Координаты центров блоков можно записать в текстовый файл: в случае доменных блоков – в файл dmn.txt, а в случае ранговых блоков – в файл rng.txt.
Заметим, что эта информация в алгоритме сжатия не используется: алгоритм оперирует габаритными прямоугольниками доменного и рангового блоков.
В результате рассмотренных подготовительных операций формируется часть параметров, передаваемых программе восстановления изображения – это r, h, w, h2, w2, nH и nW.
Построим алгоритм сжатия, который далее будем именовать базовым алгоритмом. Разработку выполним, опираясь на алгоритм, приведенный в работе Фрактальное сжатие изображений.
Отношение rt площадей доменного и ранговых блоков равно квадрату отношения радиусов описанных окружностей этих блоков:
rt = (rD / rR)2
В нашем примере rt = 4. Это означает, что при сжатии доменного блока его 4 пикселя соотносятся с одним пикселем рангового блока.
Зная размеры габаритных прямоугольников доменного и рангового блоков, нетрудно вычислить пиксельные координаты их центров. Таким образом, мы имеем все необходимое для локализации габаритных прямоугольников всех доменных и ранговых блоков. Эта информация обеспечит доступ к самим блокам.
Как и в базовом алгоритме, пиксели габаритного прямоугольника доменного блока перебираются с шагом 2, однако при этом пропускаются пиксели, находящиеся за пределами самого блока (рис. 4).
Рис. 4. Пропускаемые пиксели закрашены красным и синим цветами
Функция fndMssd заносит при движении в пределах габаритного прямоугольника сверху вниз в массив arrMssd число пикселей между левыми границами прямоугольника и доменного или рангового блока (красные пиксели). Для формирования массива функции передаются радиусы описанной и вписанной окружностей блока.
-- Формирует массив пропускаемых пикселей
-- Находит число пикселей в блоке
-- Пишет строку со значениями массива пропускаемых пикселей в результирующий файл
fn fndMssd rB rB2 fs &nPB= (
local arrMssd
-- Число пропускаемых пикселей на верхней границе блока
mssdTp = rB / 2 - 1
arrMssd = #(mssdTp)
-- Число перемещений по вертикали при неизменной x-координате
nDbl = rB2 - mssdTp
-- Шаг между такими перемещениями
stp = (rB2 / nDbl) as integer
crrntY = 0
for k = 2 to rB2 do (
crrntY += 1
if crrntY == stp then
crrntY = 0
else
mssdTp -= 1
append arrMssd mssdTp
)
if arrMssd[rB2] == 1 do arrMssd[rB2] = 0
for k = 1 to rB2 do append arrMssd arrMssd[rB2 - k + 1]
-- Всего при работе с блоком пропускается mssdTtl пикселей
mssdTtl = 0
strMssd = ""
for k = 1 to 2 * rB2 do (
mssdTtl += arrMssd[k]
strMssd += (arrMssd[k] as string) + " "
)
-- Сохраняем строку strMssd в результирующем файле
print (substring strMssd 1 (strMssd.Count - 1)) to: fs
mssdTtl *= 2
-- Число пикселей в блоке
nPB = 4 * rB * rB2 - mssdTtl
return arrMssd
)
-- Проверка функции
nP = 0
r = 20
r2 = (0.5 * r * sqrt 3.0) as integer
fnTpt = "d:/frctls.txt"
fs = openFile fnTpt mode:"w"
arrMssd = fndMssd r r2 fs &nP
close fs
Расстояние между доменным и ранговым блоками вычисляется 4 раза. Первые 2 раза обеспечиваются исходным доменным блоком и его поворотом на 180° (рис. 5). Следующие 2 – зеркальным отражением доменного блока и его поворотом на 180° (рис. 6).
Рис. 5. Ориентации 0 и 1
Рис. 6. Ориентации 2 и 3
Для изменения ориентации введем функцию rtArrDp. Для зеркального отражения введем массив, содержащий число элементов в каждой строке отражаемого массива.
-- Поворот доменного блока на 180 градусов (mkRt = true)
-- Зеркальное отражение доменного блока относительно оси Y (mkRt = false)
fn rtArrDp arrDP arrRW mkRt = (
local k, k2, nP2, nPLL2
if mkRt then (
-- Поворот на 180 градусов
nPLL = arrDP.Count
arrDPT = for k = 1 to nPLL collect arrDP[nPLL - k + 1]
)
else (
-- Зеркальное отражение
arrDPT = #()
nPLL2 = 0
nRW = arrRW.Count
for k = 1 to nRW do (
nP2 = arrRW[nRW - k + 1]
nPLL2 += nP2
for k2 = 1 to nP2 do append arrDPT arrDP[nPLL2 - k2 + 1]
)
)
return arrDPT
)
-- Формируем тестовый массив
nRW = 5
nPLL = 18
arrDP = for k = 1 to nPLL collect k
arrRW = #(2, 4, 6, 4, 2)
-- Поворот на 180 градусов
mkRt = true
-- Зеркальное отражение
-- mkRt = false
arrDP = rtArrDp arrDP arrRW mkRt
Сдвиг по яркости v берется равным
где n – число пикселей в ранговом блоке;
ri – значение пикселя рангового блока;
di – значение усредненного пикселя доменного блока;
u – коэффициент сжатия яркости (u = 0.75).
Расстояние между доменным и ранговым блоками вычисляется по следующей формуле:
После выбора рангового блока расстояние d(R, D) вычисляется поочередно для каждого доменного блока. В результате находится доменный блок, наиболее близкий в смысле расстояния d(R, D) к текущему ранговому блоку. В файл с результатом сжатия, как и в случае базового алгоритма, записываются следующие данные:
Число таких записей равно числу ранговых блоков.
Описанный алгоритм сжатия имеет ту же вычислительную сложность, что и базовый алгоритм. Однако число записей в результирующем файле будет больше, чем в файле-результате базового алгоритма (при равных размерах габаритного прямоугольника шестиугольного доменного блока и прямоугольного доменного блока базового алгоритма). Размер файла увеличится примерно в Sb / Sc = 4 / 3 раза, где Sc – это площадь правильного шестиугольника, а Sb – это площадь соответствующего габаритного прямоугольника.
Приводимый ниже алгоритм сжатия включает все выше описанные предварительные вычисления.
В приводимом коде повторяются ранее введенные вспомогательные функции. Это позволяет запустить программу сразу после ее копирования в редактор MAXScript и указания подготовленного для сжатия bmp-файла (переопределяется значение переменной fnBtmp). При необходимости можно изменить и значение переменной fnTpt, содержащей полное имя файла с результатами сжатия.
-- Находит исходные и рабочие размеры сжимаемого образа,
-- а также число доменных блоков по высоте и ширине рабочей области
fn dfnDRSz btmp r r2 &h &w &h2 &w2 &nH &nW = (
h = btmp.Height as float
w = btmp.Width as float
-- Диаметр описанной окружности блока
d = 2 * r
-- Целочисленный диаметр вписанной окружности блока
d2 = 2 * r2
-- Число доменных блоков по высоте образа
nH = ceil ((h + d2) / d2) as integer
-- Уточняем рабочую высоту образа
h2 = d2 * nH
-- Рабочая ширина образа
w2 = w + 0.5 * d
-- Число доменных блоков по ширине образа
nW = ceil ((w2 - 0.25 * d) / (0.75 * d)) as integer
-- Уточняем рабочую ширину образа
w2 = 0.75 * nW * d + 0.25 * d
)
-- Переносит исходный образ в рабочую область
fn mvBtmp2 btmp h w h2 w2 = (
-- Создаем растровый образ размера w2 * h2
btmp2 = bitmap w2 h2 color: white
hS = (0.5 * (h2 - h)) as integer
wS = (0.5 * (w2 - w)) as integer
for k = 0 to w - 1 do setPixels btmp2 [wS, hS + k] (getPixels btmp [0, k] w)
close btmp
return btmp2
)
-- Формирует массив пропускаемых пикселей
-- Находит число пикселей в блоке
-- Пишет строку со значениями массива пропускаемых пикселей в результирующий файл
fn fndMssd rB rB2 fs &nPB= (
local arrMssd
-- Число пропускаемых пикселей на верхней границе блока
mssdTp = rB / 2 - 1
arrMssd = #(mssdTp)
-- Число перемещений по вертикали при неизменной x-координате
nDbl = rB2 - mssdTp
-- Шаг между такими перемещениями
stp = (rB2 / nDbl) as integer
crrntY = 0
for k = 2 to rB2 do (
crrntY += 1
if crrntY == stp then
crrntY = 0
else
mssdTp -= 1
append arrMssd mssdTp
)
if arrMssd[rB2] == 1 do arrMssd[rB2] = 0
for k = 1 to rB2 do append arrMssd arrMssd[rB2 - k + 1]
-- Всего пропускается пикселей в при работе с блоком
mssdTtl = 0
strMssd = ""
for k = 1 to 2 * rB2 do (
mssdTtl += arrMssd[k]
strMssd += (arrMssd[k] as string) + " "
)
-- Сохраняем строку strMssd в результирующем файле
print (substring strMssd 1 (strMssd.Count - 1)) to: fs
mssdTtl *= 2
-- Число пикселей в блоке
nPB = 4 * rB * rB2 - mssdTtl
return arrMssd
)
-- Формирует массив усредненных яркостей доменных (ранговых) блоков
fn fndZ btmp nHB nWB h2 rB rB2 arrMssd nPB = (
local nH2
arrZ = #()
-- Х координата базовой точки первой вертикали
xB = rB
for k = 1 to nWB do (
-- Левая и правая границы габаритного прямоугольника блока
xS = xB - rB
xE = xB + rB - 1
-- Число блоков по горизонтали
nH2 = if mod k 2 == 0 then nHB - 1 else nHB
-- Y координата базовой точки очередного блока
yB = h2 - (if mod k 2 == 0 then 2 * rB2 else rB2)
for k2 = 1 to nH2 do (
-- Верхняя и нижняя границы габаритного прямоугольника блока
yS = yB - rB2
yE = yB + rB2 - 1
z = 0.0
k3 = 0
for y = yS to yE do (
k3 += 1
-- Корректировка параметров цикла на величину пропускаемых пикселей
xS3 = xS + arrMssd[k3]
xE3 = xE - arrMssd[k3]
for x = xS3 to xE3 do (
arrT = getPixels btmp [x, y] 1
z += arrT[1].Red
)
)
arrZ = append arrZ (z / nPB)
-- Y координата очередной горизонтали
yB -= (2 * rB2)
)
-- Х координата очередной вертикали
xB += (1.5 * rB)
)
return arrZ
)
-- Формирует массив значений яркости усредненных пикселей всех доменных блоков
-- Дополнительно формирует массив arrRW, содержащий число элементов в каждой
-- строке массива arrDP; данные этого массива переносятся в результирующий файл
fn fndDPLL btmp nHB nWB h2 rB rB2 arrMssd arrRW fs = (
local nH2
-- Массив arrDPLL состоит из массивов, отвечающих доменным блокам
arrDPLL = #()
-- Х координата базовой точки первой вертикали
xB = rB
for k = 1 to nWB do (
-- Левая и правая границы габаритного прямоугольника блока
xS = xB - rB
xE = xB + rB - 1
-- Число блоков по горизонтали
nH2 = if mod k 2 == 0 then nHB - 1 else nHB
-- Y координата базовой точки очередного блока
yB = h2 - (if mod k 2 == 0 then 2 * rB2 else rB2)
for k2 = 1 to nH2 do (
-- Верхняя и нижняя границы габаритного прямоугольника блока
yS = yB - rB2
yE = yB + rB2 - 1
k3 = 1
arrDP = #()
for y = yS to yE by 2 do (
-- Корректировка параметров цикла на величину пропускаемых пикселей
xS3 = xS + arrMssd[k3]
xE3 = xE - arrMssd[k3] - 1
k3 += 2
if k == 1 and k2 == 1 do nPRW = 0
for x = xS3 to xE3 by 2 do (
arrT = getPixels btmp [x, y] 2
arrT2 = getPixels btmp [x, y + 1] 2
clr = 0
-- Формируем усредненный пиксель доменного блока
for k4 = 1 to 2 do clr += arrT[k4].Red + arrT2[k4].Red
clr /= 4
-- Массив усредненных пикселей
arrDP = append arrDP clr
if k == 1 and k2 == 1 do nPRW += 1
)
if k == 1 and k2 == 1 do append arrRW nPRW
)
append arrDPLL arrDP
-- Y координата очередной горизонтали
yB -= (2 * rB2)
)
-- Х координата очередной вертикали
xB += (1.5 * rB)
)
strRW = ""
for k = 1 to arrRW.Count do strRW += (arrRW[k] as string) + " "
-- Сохраняем строку strRW в результирующем файле
print (substring strRW 1 (strRW.Count - 1)) to: fs
return arrDPLL
)
-- Поворот доменного блока на 180 градусов (mkRt = true)
-- Зеркальное отражение доменного блока относительно оси Y (mkRt = false)
fn rtArrDp arrDP arrRW mkRt = (
local k, k2, nP2, nPLL2
if mkRt then (
-- Поворот на 180 градусов
nPLL = arrDP.Count
arrDPT = for k = 1 to nPLL collect arrDP[nPLL - k + 1]
)
else (
-- Зеркальное отражение
arrDPT = #()
nPLL2 = 0
nRW = arrRW.Count
for k = 1 to nRW do (
nP2 = arrRW[nRW - k + 1]
nPLL2 += nP2
for k2 = 1 to nP2 do append arrDPT arrDP[nPLL2 - k2 + 1]
)
)
return arrDPT
)
-- Перебор пикселей рангового блока;
-- вычисление расстояния между текущими ранговым и доменным блоками;
-- поиск оптимальных параметров преобразования
fn trtRrDp btmp u v nP2 xSR xER ySR yER arrMssdR arrDP rntCrrnt kDFSCrrnt &kDFS &rnt &vFS &dMn = (
local d, kD, k3
d = 0
kD = 0
k3 = 0
cnt = arrDP.Count
for yR = ySR to yER do (
k3 += 1
-- Корректировка параметров цикла на величину пропускаемых пикселей
xSR3 = xSR + arrMssdR[k3]
xER3 = xER - arrMssdR[k3]
for xR = xSR3 to xER3 do (
kD += 1
if kD <= cnt do (
arrT = getPixels btmp [xR, yR] 1
rP = arrT[1].Red
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
)
)
strt = timeStamp()
clearListener()
-- Коэффициент сжатия яркости
u = 0.75
-- Коэффициент сжатия изображения
cmprssn = 2
-- Исходные размеры сжимаемого образа
h = w = 0
-- Рабочие размеры сжимаемого образа
h2 = w2 = 0
-- Число доменных блоков по высоте и ширине рабочей области образа
nH = nW = 0
-- Файл с исходным образом
fnBtmp = "d:/pawn.bmp"
btmp = openBitMap fnBtmp
-- Файл с результатами сжатия
fnTpt = "d:/frctls.txt"
-- Радиус описанной окружности доменного блока
r = 20
-- Радиус вписанной окружности доменного блока
r2 = (0.5 * r * sqrt 3.0) as integer
--
-- Исходные и рабочие размеры сжимаемого образа
-- Число доменных блоков по высоте и ширине рабочей области
dfnDRSz btmp r r2 &h &w &h2 &w2 &nH &nW
--
-- Вывод параметров сжатия в текстовый файл
fs = openFile fnTpt mode:"w"
format "% % % % % % %\n" r h w h2 w2 nH nW to: fs
--
-- Переносим исходный образ в рабочую область
btmp2 = mvBtmp2 btmp h w h2 w2
-- Радиус описанной окружности рангового блока
rR = r / cmprssn
-- Радиус вписанной окружности рангового блока
rR2 = (0.5 * rR * sqrt 3.0) as integer
-- Число ранговых блоков по высоте и ширине образа
nHR = 2 * nH
nWR = 2 * nW
--
-- Число пикселей в доменном и ранговом блоках
nPD = nPR = 0
-- Массив пропускаемых пикселей доменного блока
arrMssdD = fndMssd r r2 fs &nPD
--
-- Массив пропускаемых пикселей рангового блока
arrMssdR = fndMssd rR rR2 fs &nPR
--
-- Ищем усредненную яркость каждого доменного блока
-- Результат храним в массиве arrZD
arrZD = fndZ btmp2 nH nW h2 r r2 arrMssdD nPD
--
-- Ищем усредненную яркость каждого рангового блока
-- Результат храним в массиве arrZR
arrZR = fndZ btmp2 nHR nWR h2 rR rR2 arrMssdR nPR
--
-- Формируем массив значений яркости усредненных пикселей всех доменных блоков
-- Дополнительно формируем массив arrRW, содержащий число элементов
-- в каждой строке массива arrDP
arrRW = #()
arrDPLL = fndDPLL btmp2 nH nW h2 r r2 arrMssdD arrRW fs
--
-- Находим для каждого рангового блока ближайший доменный блок
-- Начальное расстояние между ранговым и доменным блоками
dMnS = 255 * 255 * r * r
-- Массив параметров преобразования
arrDFS = #()
-- Номер текущего рангового блока
kRCrrnt = 0
-- Берем поочередно все ранговые блоки
-- Х координата базовой точки первой вертикали
xR = rR
for kR = 1 to nWR do (
-- Левая и правая границы габаритного прямоугольника рангового блока
xSR = xR - rR
xER = xR + rR - 1
-- Число ранговых блоков по горизонтали
nHR2 = if mod kR 2 == 0 then nHR - 1 else nHR
-- Y координата базовой точки очередного рангового блока
yR = h2 - (if mod kR 2 == 0 then 2 * rR2 else rR2)
for kR2 = 1 to nHR2 do (
-- Верхняя и нижняя границы габаритного прямоугольника рангового блока
ySR = yR - rR2
yER = yR + rR2 - 1
kRCrrnt += 1
-- Усредненная яркость текущего рангового блока
zR = arrZR[kRCrrnt]
-- Номер текущего доменного блока
kDFSCrrnt = 0
-- Искомый номер доменного блока
kDFS = 0
-- Искомая ориентация доменного блока
rnt = 0
-- Искомый сдвиг по яркости
vFS = 0
-- Текущее расстояние между текущими ранговым и доменным блоками
dMn = dMnS
-- Берем поочередно все доменные блоки в 4-х ориентациях
for kD = 1 to nW do (
-- Число доменных блоков по горизонтали
nH2 = if mod kD 2 == 0 then nH - 1 else nH
for kD2 = 1 to nH2 do (
kDFSCrrnt += 1
-- Массив пикселей исходного доменного блока
arrDP = arrDPLL[kDFSCrrnt]
-- Массив пикселей зеркально отраженного доменного блока
arrDP2 = rtArrDp arrDP arrRW false
-- Усредненная яркость текущего доменного блока
zD = arrZD[kDFSCrrnt]
-- Текущий сдвиг по яркости между ранговым и доменным блоками
v = zR - u * zD
-- Исходная ориентация доменного блока
trtRrDp btmp2 u v r2 xSR xER ySR yER arrMssdR arrDP 0 kDFSCrrnt &kDFS &rnt &vFS &dMn
-- Поворот доменного блока на 180 градусов
arrDP = rtArrDp arrDP arrRW true
trtRrDp btmp2 u v r2 xSR xER ySR yER arrMssdR arrDP 1 kDFSCrrnt &kDFS &rnt &vFS &dMn
-- Зеркально отраженный доменный блок
trtRrDp btmp2 u v r2 xSR xER ySR yER arrMssdR arrDP2 2 kDFSCrrnt &kDFS &rnt &vFS &dMn
-- Поворот зеркально отраженного доменного блока на 180 градусов
arrDP2 = rtArrDp arrDP2 arrRW true
trtRrDp btmp2 u v r2 xSR xER ySR yER arrMssdR arrDP2 3 kDFSCrrnt &kDFS &rnt &vFS &dMn
)
)
arrDFS = append arrDFS [kDFS, rnt, vFS]
format "% %\n" kR kR2
-- Y координата очередной горизонтали
yR -= (2 * rR2)
)
-- Х координата очередной вертикали
xR += (1.5 * rR)
)
--
-- Вывод результата в текстовый файл
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
Декомпрессия производится следующим образом. Выбирают начальное, называемое инициатором, изображение. Инициатор разбивается на множество ранговых блоков; их число равно числу ранговых блоков в исходном изображении.
В качестве начального может быть взято любое изображение, например черное: соответствующий математический аппарат гарантирует сходимость последовательности изображений, получаемых в ходе употребления системы итерируемых функций, к неподвижному изображению. Обычно для этого достаточно не более 20 итераций.
Размеры восстанавливаемого и исходного изображений могут различаться: изображение восстанавливается в границах найденной при сжатии рабочей области, затем переносится в границы исходного образа и вслед может быть скопировано в образ с любыми подходящими размерами.
Восстановление изображения происходит по следующей схеме:
Эта схема используется для каждого рангового блока до стабилизации изображения: новые итерации практически не меняют текущего изображения.
Восстановление изображения обеспечивает следующий основанный на приведенной схеме MAXScript-код:
-- Поворот доменного блока на 180 градусов (mkRt = true)
-- Зеркальное отражение доменного блока относительно оси Y (mkRt = false)
fn rtArrDp arrDP arrRW mkRt = (
local k, k2, nP2, nPLL2
if mkRt then (
-- Поворот на 180 градусов
nPLL = arrDP.Count
arrDPT = for k = 1 to nPLL collect arrDP[nPLL - k + 1]
)
else (
-- Зеркальное отражение
arrDPT = #()
nPLL2 = 0
nRW = arrRW.Count
for k = 1 to nRW do (
nP2 = arrRW[nRW - k + 1]
nPLL2 += nP2
for k2 = 1 to nP2 do append arrDPT arrDP[nPLL2 - k2 + 1]
)
)
return arrDPT
)
-- Переносит образ из рабочей области в область с размерами исходного образа
fn mvBtmp btmp2 h2 w2 h w = (
-- Создаем растровый образ размера w * h
btmp = bitmap w h color: white
hS = (0.5 * (h2 - h)) as integer
wS = (0.5 * (w2 - w)) as integer
for k = 0 to w - 1 do setPixels btmp [0, k] (getPixels btmp2 [wS, hS + k] w)
return btmp
)
strt = timeStamp()
clearListener()
-- Файл с результатом (со сжатым изображением)
fnTpt = "d:/frctls.txt"
fs = openFile fnTpt mode:"r"
sRd = readLine fs
arrT = filterString sRd " "
-- Радиус описанной окружности доменного блока
r = arrT[1] as float
-- Радиус вписанной окружности доменного блока
r2 = (0.5 * r * sqrt 3.0) as integer
-- Радиус описанной окружности рангового блока
rR = 0.5 * r
-- Радиус вписанной окружности рангового блока
rR2 = (0.5 * rR * sqrt 3.0) as integer
-- Размеры исходного образа
h = arrT[2] as float
w = arrT[3] as float
-- Размеры рабочей области
h2 = arrT[4] as float
w2 = arrT[5] as float
-- Число доменных блоков по высоте и ширине рабочей области
nH = arrT[6] as integer
nW = arrT[7] as integer
-- Число ранговых блоков по высоте и ширине рабочей области
nHR = 2 * nH
nWR = 2 * nW
-- Массив пропускаемых пикселей доменного блока
sRd = readLine fs
arrMssdD = filterString (substring sRd 2 (sRd.Count - 2)) " "
for k = 1 to arrMssdD.Count do arrMssdD[k] = arrMssdD[k] as integer
-- Массив пропускаемых пикселей рангового блока
sRd = readLine fs
arrMssdR = filterString (substring sRd 2 (sRd.Count - 2)) " "
for k = 1 to arrMssdR.Count do arrMssdR[k] = arrMssdR[k] as integer
-- Массив, содержащий число элементов в каждой строке массива усредненных пиксе-лей
sRd = readLine fs
arrRW = filterString (substring sRd 2 (sRd.Count - 2)) " "
for k = 1 to arrRW.Count do arrRW[k] = arrRW[k] as integer
-- Заносим параметры преобразований в массив 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
-- Коэффициент сжатия яркости
u = 0.75
-- Создаем растровый образ размера w2 * h2 пикселей
-- Изначально образ залит серым цветом
btmp2 = bitmap w2 h2 color:gray
-- Выполняем 10 итераций восстановления образа
for kFS = 1 to 10 do (
print kFS
-- Номер текущего рангового блока
kRCrrnt = 0
-- Берем поочередно все ранговые блоки
-- Х координата базовой точки первой вертикали
xR = rR
for kR = 1 to nWR do (
-- Левая и правая границы габаритного прямоугольника рангового блока
xSR = xR - rR
xER = xR + rR - 1
-- Число ранговых блоков по горизонтали
nHR2 = if mod kR 2 == 0 then nHR - 1 else nHR
-- Y координата базовой точки очередного рангового блока
yR = h2 - (if mod kR 2 == 0 then 2 * rR2 else rR2)
for kR2 = 1 to nHR2 do (
-- Верхняя и нижняя границы габаритного прямоугольника рангового блока
ySR = yR - rR2
yER = yR + rR2 - 1
kRCrrnt += 1
-- Номер доменного блока, отвечающего текущему ранговому бло-ку
kDFS = arrDFS[kRCrrnt][1]
-- Ориентация дменного блока
rnt = arrDFS[kRCrrnt][2]
-- Сдвиг по яркости
vFS = arrDFS[kRCrrnt][3]
-- Находим доменный блок kDFS
-- Номер текущего доменного блока
kDFSCrrnt = 0
-- Берем поочередно все доменные блоки
-- Х координата базовой точки первой вертикали
xD = r
for kD = 1 to nW do (
-- Левая и правая границы габаритного прямоугольника до-менного блока
xSD = xD - r
xED = xD + r - 1
-- Число доменных блоков по горизонтали
nH2 = if mod kD 2 == 0 then nH - 1 else nH
-- Y координата базовой точки очередного блока
yD = h2 - (if mod kD 2 == 0 then 2 * r2 else r2)
for kD2 = 1 to nH2 do (
-- Верхняя и нижняя границы габаритного прямоугольника блока
ySD = yD - r2
yED = yD + r2 - 1
kDFSCrrnt += 1
-- Найден нужный доменный блок
if kDFSCrrnt == kDFS do (
-- Формируем массив arrDP усредненных пикселей доменного блока
arrDP = #()
k3 = 1
for y = ySD to yED by 2 do (
-- Корректировка параметров цикла на величину пропускаемых пикселей
xSD3 = xSD + arrMssdD[k3]
xED3 = xED - arrMssdD[k3] - 1
k3 += 2
for x = xSD3 to xED3 by 2 do (
arrT = getPixels btmp2 [x, y] 2
arrT2 = getPixels btmp2 [x, y + 1] 2
clr = 0
-- Формируем усредненный пиксель доменного блока
for k4 = 1 to 2 do clr += arrT[k4].Red + arrT2[k4].Red
clr /= 4
-- Массив усредненных пикселей доменного блока
arrDP = append arrDP clr
)
)
cnt = arrDP.Count
-- Выполняем при необходимости зеркальное отражение доменного блока
if rnt > 2 do (
arrDP = rtArrDp arrDP arrRW false
rnt -= 2
)
-- Выполняем при необходимости поворот до-менного блока
if rnt == 1 do arrDP = rtArrDp arrDP arrRW true
-- Восстанавливаем пиксели текущего рангового блока
kD = 0
k3 = 0
for y = ySR to yER do (
k3 += 1
-- Корректировка параметров цикла на величину пропускаемых пикселей
xSR3 = xSR + arrMssdR[k3]
xER3 = xER - arrMssdR[k3]
for x = xSR3 to xER3 do (
kD += 1
if kD <= cnt do (
clr = u * arrDP[kD] + vFS
setPixels btmp2 [x, y] #((color clr clr clr))
)
)
)
) -- Конец if Найден нужный доменный блок
-- Y координата очередной горизонтали доменных блоков
yD -= (2 * r2)
)
-- Х координата очередной вертикали доменных блоков
xD += (1.5 * r)
)
-- Y координата очередной горизонтали ранговых блоков
yR -= (2 * rR2)
)
-- Х координата очередной вертикали ранговых блоков
xR += (1.5 * rR)
)
)
-- Переносим пиксели в образ с исходными размерами
btmp = mvBtmp btmp2 h2 w2 h w
tm = (timeStamp() - strt) / 1000.0
-- Показываем результат
display btmp
Для проверки был взят bmp-файл с размерами 200 * 162 пикселя (рис. 7).
Рис. 7. Исходный образ (размеры 200 * 162 пикселя)
После сжатия с параметрами r = 20, nH = 6 и nW = 7 (соответственно радиус описанной окружности доменного блока и число доменных блоков по вертикали и горизонтали) и последующего восстановления результата получен приведенный на рис. 8 образ.
Рис. 8. Восстановленный образ при сжатии с параметрами r = 20, nH = 6 и nW = 7
Коэффициент сжатия около 300 (вычислен по rar-архиву результирующего файла). Время сжатия около 30 с., а время восстановления образа с 5-ю итерациями около 7 с.
Образ, восстановленный после сжатия с параметрами r = 10, nH = 12 и nW = 14, приведен на рис. 9.
Рис. 9. Восстановленный образ при сжатии с параметрами r = 10, nH = 12 и nW = 14
Коэффициент сжатия около 150 (также вычислен по rar-архиву результирующего файла). Время сжатия около 150 с., а время восстановления образа с 5-ю итерациями около 10 с.
Наблюдаемые потери качества обусловлены неточным сопоставлением пикселей доменного и рангового блоков, а также неполной обработкой их граничных пикселей. Можно предположить, что соответствующая нивелировка кода обеспечит приемлемый результат (в работе нет задачи получения практически значимого результата).
Иной способ повышения качества результата – это использование перекрывающихся блоков.
Кроме того, взамен разбиения Вороного можно употребить разбиение (триангуляцию) Делоне, которое несложно получить по известному разбиению Вороного (рис. 10).
Рис. 10. Разбиения Вороного и Делоне (красные треугольники)
Для получения рис. 10 можно употребить следующий код:
fn mkLn ps ps2 = (
spln = line pos:ps wireColor:red \
render_renderable:on render_displayRenderMesh:on render_thickness:1.0
addNewSpline spln
addKnot spln 1 #corner #line ps
addKnot spln 1 #corner #line ps2
updateShape spln
)
-- Выполняет вывод шестиугольных и треугольных блоков
fn dvdBtm r r2 nH nW h2 w2 tm clr = (
local nH2
-- Диаметр описанной окружности блока
d = 2 * r
-- Целочисленный диаметр вписанной окружности блока
d2 = 2 * r2
x = -w2 / 2 + r
arrPs = #()
for k = 1 to nW do (
z = -h2 / 2 + (if mod k 2 == 0 then 2 * r2 else r2)
nH2 = if mod k 2 == 0 then nH - 1 else nH
ps = [x, 0, z]
arrPs2 = #()
for k2 = 1 to nH2 do (
nGon radius:r nsides:6 pos:ps transform:tm wireColor:clr \
render_renderable:on render_displayRenderMesh:on \
render_thickness:1.0 scribe:1
append arrPs2 ps
ps += [0, 0, d2]
)
append arrPs arrPs2
x += (1.5 * r)
)
for k = 1 to nW do (
arrPs2 = arrPs[k]
for k2 = 1 to arrPs2.Count - 1 do (
mkLn arrPs2[k2] arrPs2[k2 + 1]
)
)
for k = 1 to nW - 1 do (
arrPs2 = arrPs[k]
arrPs3 = arrPs[k + 1]
cnt2 = arrPs2.Count
cnt3 = arrPs3.Count
for k2 = 1 to cnt2 do (
if k2 <= cnt3 do
mkLn arrPs2[k2] arrPs3[k2]
if cnt3 > cnt2 do
mkLn arrPs2[k2] arrPs3[k2 + 1]
if cnt3 < cnt2 and k2 < cnt2 do
mkLn arrPs2[k2 + 1] arrPs3[k2]
)
)
)
delete $*
h2 = 204
w2 = 220
-- Число блоков по высоте и ширине рабочей области образа
nH = 6
nW = 7
-- Диаметр описанной окружности блока
r = 20
-- Радиус вписанной окружности блока
r2 = (0.5 * r * sqrt 3.0) as integer
tm = matrix3 [1,0,0] [0,0,1] [0,-1,0] [0,0,0]
-- Вывод шестиугольных блоков
dvdBtm r r2 nH nW h2 w2 tm blue
Программа сжатия изображения содержит около 500 строк, а программа восстановления – около 150. Это позволяет говорить о технической простоте решаемой задачи. Прогнозируемые затраты на уточнение программы с целью повышения качества результата – 20-процентное увеличение кода.