Это сообщение лишь кратко описывает суть метода фрактального сжатия без объяснения принципов, на которых основывается данный метод.
Определение: Отображение w называется сжимающим, если для любых двух точек P1 и P2 расстояние
d(w(P1),w(P2)) < s * d(P1,P2), для некоторого s < 1. (1)
Наиболее часто, если две точки плоскости имеют координаты P1 = (x1,y1) и P2 = (x2,y2), то расстояние между ними определяется по формуле:
d(P1,P2) = sqrt( (x2-x1)^2 + (y2-y1)^2 )
Примером сжимающего преобразования на плоскости является
- - - - - -
w| x | = | 0.5 0 | | x |
| y | | 0 0.5| | y |
- - - - - -
которое уменьшает расстояние между любыми точками наполовину.
Кроме (1) на сжимающие преобразования не накладывается больше никаких условий, однако, для сжатия изображений наиболее часто используют аффинные преобразования, которые позволяют сдвигать, уменьшать или увеличивать, сжимать или растягивать изображение. В частности, аффинные преобразования всегда отображают квадрат в параллелограмм.
Легко можно заметить, что если сжимающее преобразование преобразование многократно применять к одному изображению, мы всегда получим изображение, которое в дальнейшем не будет изменяться при новых итерациях и это изображение будет состоять из одной точки, называемой неподвижной точкой данного сжимающего изображения.
Если же мы теперь выберем конечную фиксированную совокупность W некоторых сжимающих преобразований Wi, каждое из которых будем их применять к части изображения Di ( Wi(Di) = Ri), то через некоторое время мы опять получим изображение, которое не будет меняться при дальнейших операциях. Для однозначности можно потребовать чтобы множества Ri не пересекались. Неподвижная точка обозначается |W|.
Теорема: Всякое сжимающее отображение, определенное в полном метрическом пространстве, имеет одну и только одну неподвижную точку.
Метод фрактального сжатия конкретного изображения заключается в отыскании такой совокупности сжимающих преобразований, неподвижная точка которой является этим изображением, либо достаточно мало от него отличается.
Любое изображение можно представить в виде функции z=f(x,y). Значение этой функции зависит от цвета точки с координатами (x,y), например, может совпадать с номером ее цвета. Для простоты, будем считать, что значения (x,y) принадлежат единичному квадрату I^2 = [0,1]x[0,1], а значения функции f - единичному интервалу I = [0,1].
В дальнейшем, нам надо будет определять отличие одного изображения от другого, для этого в пространстве функций изображений введем метрику
q(f,g) = sup | f(x,y) - g(x,y) |
(x,y) из I^2
Метрика по-другому называется расстояние. Возможно задание и других метрик
пространства функций изображений.
Как уже было сказано, фрактальное сжатие изображения f заключается в отыскании совокупности W сжимающих преобразований Wi такой, что |W| = f. Т.е. чтобы изображение было неподвижной точкой этой совокупности преобразований: f = W(f) = объединение Wi(f). В общем случае, найти такую совокупность почти невозможно, однако, мы можем найти другое изображение f' такое, что f' = |W| и значение q(f,f') значительно мало. Для нахождения такого изображения необходимо минимизировать значения:
q(f пересечение Ri, Wi(f)) (2)
При этом мы найдем преобразования Wi и фрагменты Di изображения f, которые
полностью определят фрактальную модель изображения. Отыскание Di и Wi - это
наиболее очень трудная задача (NP-трудная задача).
Для черно-белых изображений преобразования Wi можно искать в виде:
- - - - - - - -
| x | | Ai Bi 0 | | x | | Ei|
| y | = | Ci Di 0 | | y | + | Fi|
| z | | 0 0 Si| | z | | Oi|
- - - - - - - -
где Si отвечает за контрастность, а Oi - за яркость изображения.
Пусть дано изображение 256x256 точек из 256 цветов (или градаций серого). Пусть R1, R2, ..., R1024 - 8x8 битовые непересекающиеся квадратные фрагменты изображения, а D - множество всех (пересекающихся) квадратных 16х16 фрагментов изображения. Это множество содержит 214'241 = 58081 элемент. Для каждого Ri во множестве D находим элемент, минимизирующий (2). Имеется 8 способов (поворот на 4 стороны или зеркальное отражение и поворот на 4 стороны) аффинного преобразования квадрата в квадрат. Это требует сравнения 8'58081=464648 квадратов с каждым из 1024 квадратов Ri. Заметим, что квадраты Di в 4 раза больше квадратов Ri, т.е. при сравнении в 2х2 подквадратах Di мы должны либо выбирать одну некоторую точку, либо заменять его средним значением всех 4 точек.
Минимизировать (2) можно по двум составляющим одновременно: найти наилучший
фрагмент Di и наилучшие значения контрастности Si и яркости Oi. Для каждого Di
значения Si и Oi можно легко найти используя метод наименьших квадратов для
линейной регрессии:
Пусть даны две последовательности из n значений цветов пикселов: a1, ..., an
(из Di) и b1, ..., bn (из Ri). Мы можем найти s и o минимизируя
n
R = SUM ( s'ai + o -bi)^2
i=1
Это выражение достигает своего минимума когда
( n n n ) ( n n )
s = | n^2'SUM ai'bi - (SUM ai )'(SUM bi)|/| n^2'SUM ai^2 - (SUM ai)^2|
( i=1 i=1 i=1 ) ( i=1 i=1 )
( n n )
o = | SUM bi - s'SUM ai| / n^2
( i=1 i=1 )
В этом случае значение минимума будет равно
( n n n n
R = | SUM bi + s(s'SUM ai^2 - 2(SUM ai'bi) + 2o'SUM ai) +
( i=1 i=1 i=1 i=1
n )
+ o(o'n^2 - 2'SUM bi)| / n^2
i=1 )
n n n
Если же n^2'SUM ai^2 - (SUM ai)^2 = 0, то s = 0 и o = SUM bi / n^2.
i=1 i=1 i=1
Выбрав соответствующие Di и Oi с Si мы полностью определим отображение Wi.
Когда мы имеем всю совокупность отображений W1, ..., W1024, исходное изображение можно легко восстановить из любого начально приближения, например, из черного квадрата. Причем размер восстановленного изображения никак не зависит от размера первоначального изображения, т.е. легко можно получить уменьшенную или увеличенную копию исходного изображения.
Вернемся к нашему примеру. Оригинальное изображение занимает 65536 байт. А преобразования для хранения требуют 3968 байт ( 8 бит для определения позиции Di по горизонтали и вертикали, 7 бит для Oi, 5 бит для Si, 3 бита для определения поворота и отражения при преобразовании Di в Ri). Таким образом достигается коэффициент сжатия 16.5:1.
Как можно было заметить из приведенного выше примера, основным недостатком данного метода сжатия является очень большой объем вычислений для кодирования изображения. Для программ, реализующих данный метод, применяются как обычные методы увеличения скорости программ: целочисленная арифметика, ассемблерная реализация и др., так и специфические эвристические приемы: использование аффинных преобразований только одного типа, различные варианты деления изображения на области Ri и Di и т.п.
Ниже приводятся схемы двух алгоритмов, которые для некоторых классов изображений могут значительно уменьшить объем вычислений. Параметрами для этого алгоритма служат уровень значимости для погрешности кодирования изображения и минимальный размер областей Ri. Этот алгоритм обеспечивает одинаковую точность кодирования всего изображения.
1. Выберем уровень значимости e для (2).
2. R1 = I^2 и пометим его как необработанный фрагмент.
3. Пока есть необработанный фрагмент Ri делать
3.1 Найти Di и Wi, которые наилучшим образом приближают Ri (на которых
достигается минимум (2)).
3.2 Если q(fпересечениеRi,Wi(f)) < e или size(Ri) < min
то пометить Ri как обработанное.
Иначе: Разбить Ri на более мелкие фрагменты и пометить их
как необработанные.
Параметром второго алгоритма является количество областей Ri, используемых для
кодирования изображения, что прямо влияет на объем, а следовательно и скорость
вычислений. Данный алгоритм в некоторых случаях не обеспечивает достаточной
точности кодирования отдельных фрагментов изображения.
1. Выберем максимальное число N фрагментов Ri.
2. Добавим фрагмент R1 = I^2 в список преобразований и пометим его
как необработанный.
3. Пока есть необработанные фрагменты в списке делать
3.1 Для каждого необработанного фрагмента найти соответствующие Di и Wi.
3.2 Найти в списке фрагмент Rj наибольшего размера и наибольшей метрикой
q(fпересечениеRj,Wj(f)).
3.3 Если число фрагментов в списке меньше N, тогда разбить фрагмент Rj на
более мелкие и занести их в список как необработанные; вычеркнуть из
списка фрагмент Rj.
| Изменена 29.11.2012 16:10 MSK |
|
|