| | | | | | | | | | | К | р | а | т | к | о | е | | о | п | и | с | а | н | и | е | | м | е | т | о | д | а | | ф | р | а | к | т | а | л | ь | н | о | г | о | | с | ж | а | т | и | я | | и | з | о | б | р | а | ж | е | н | и | й | | | | | | | | | | | | |
Захаров Максим |
31.03.93, 21.04.93 |
| FIDO 2:5065/1.12, 2.2 | |
|
Это сообщение лишь кратко описывает суть метода фрактального сжатия без |
объяснения принципов, на которых основывается данный метод. |
|
Сжимающие отображения |
Определение | : Отображение 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. |
----------------------------------- |
P.S. Комментарии приветствуются. | |