Francesco Leonetti
Compressione frattale
di immagini
scanner
Compressione delle immagini
compressione frattale di immagini
FRATTALI
Figure frastagliate
Curva di Koch
Triangolo di Sierpinski
Triangolo di Sierpinski
simulazioni di Demba Diallo Mady
b
G
G(b)
G(a)
a
X
X
allora
f=G(f)
G
f
X
G(f)
X
x(1)=d, x(2)=G(d),
x(3)=G(G(d)),
...
x(1)
x(2)
f
x(n)
x(3)
X
x(n) è vicino a f
X = insieme di tutte le figure =
G:X
eccetera
X
è definita così
Da qualunque figura si parta, applicando ripetutamente G, si
arriva alla figura f che non è cambiata da G:
f=G(f)
a
G(a) = V1(a)
G(a)
V2(a)
V3(a)
a
V1(a)
a
V2(a)
a
V3(a)
S 1/2 (x , y) = (x/2 , y/2)
T u , v (x , y) = (x+u , y+v)
V1 = T 0
, 0
V2 = T40 ,
0
°
S1/2
°
S1/2
V3 = T20 , ()20 ° S1/2
G(a) = V1(a)
V2(a)
V3(a)
G necessita di 9 parametri
f come figura 80 pixel x 80 pixel necessita di 6400 parametri
f come unica figura fissa di G
necessita dei soli parametri di G: 9 parametri
Compressione = 6400 / 9 = 711
f = G(f) = V1(f)
V2(f)
V3(f)
V3(f)
V1(f)
V2(f)
Data una immagine i trovare trasformazioni
W1 , W2 , … , Wk
i = W1 (i)
Posto
W2 (i)
H = W1
contrattive
…
W2
tali che
Wk (i)
…
Wk
risulta
a , H(a) , H(H(a)) , H(H(H(a))) , …. , approssima
qualunque altra immagine
i
immagine data
Esempio
Data l’immagine i
allora
i = W1(i)
W2(i)
W3(i)
W4(i)
W3(i) W4(i)
i
W1(i) W2(i)
i
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
R1
R2
R3
R4
i  D2
i  R1
i  R3
D2
R1
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D3
i  R1
i  R3
D3
R2
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D5
i  R1
i  R3
D5
R1
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D8
i  R1
i  R3
D8
R2
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D10
i  R1
i  R3
D10
R3
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D11
i  R1
i  R3
D11
R4
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D12
i  R1
i  R3
D12
R4
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
i  D14
i  R1
i  R3
D14
R3
i  R2
i  R4
S1/2 (i  R1)
S1/2 (i  R2)
S1/2 (i  R3)
S1/2 (i  R4)
D2
R1
2; 1
D3
R2
3; 2
D5
R1
5; 1
D8
R2
8; 2
D10
R3
10; 3
D11
R4
11; 4
D12
R4
12; 4
D14
R3
14; 3
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
Dj = Tu,v  S1/2 (Rk)
Wj = Tu,v  S1/2
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
R1
R2
R3
R4
a
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a)
L(a)
R1
R2
R3
R4
L(a)
D1
D2
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a)
R1
R2
R3
R4
L(a)
D1
D3
D4
D5
D6
D7
D8
D9
10
11
12
13
14
15
16
L(a)
R1
R2
R3
R4
L(a)
D1
D4
D
D15
D6
D7
D
D18
D9
D
10 1
D
11 1
12
D
13 1
14
15
16
L(a)
R1
R2
R3
R4
D1
D4
L(a)
D6
D7
D81
D
D9
D
10 1
D
11 1
12
D
13 1
14
15
16
L(a)
R1
R2
R3
R4
D1
D4
L(a)
D6
D7
D9
D
10 1
D
11 1
12
D
13 1
14
15
16
L(a)
R1
R2
R3
R4
D1
D4
L(a)
D6
D9
D
13 1
14
D7
D
11 1
12
15
16
L(a)
R1
R2
R3
R4
D1
D4
L(a)
D6
D7
D9
D
13 1
12
14
15
16
L(a)
R1
R2
R3
R4
D1
D4
L(a)
D6
D7
14
15
D9
D
13 1
16
L(a)
R1
R2
R3
R4
D1
D4
L(a)
D6
D7
L(L(a))
D9
D
13 1
15
16
L(L(a))
R1
R2
R3
R4
L(L(a))
D1
D2
D3
D4
D
D15
D6
D
D17
D
D18
D19
D
10 1
D
11 1
D
12 1
13
14
15
16
L(L(a))
R1
R2
R3
R4
L(L(a))
D1
D3
D4
D51
D6
D71
D81
D
D91
D
10 1
D
11 1
D
12 1
13
14
15
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D15
D6
D7
D18
D19
D
10 1
D
11 1
D
12 1
13
14
15
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D6
D7
D18
D9
D
10 1
D
11 1
D
12 1
13
14
15
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D6
D7
D9
D
10 1
D
11 1
12
13
14
15
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D6
D9
13
14
D7
D
11 1
12
15
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D6
D7
D9
13
12
14
15
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D6
D7
14
15
D9
13
16
L(L(a))
R1
R2
R3
R4
D1
D4
L(L(a))
D6
D7
L(L(L(a)))
D9
13
15
16
i
D2
R1
D3
R2
D5
R1
D8
R2
D10
R3
D11
R4
D12
R4
D14
R3
2;
1
3;
2
5;
1
8;
2
10 ;
3
11 ;
4
12 ; 4
14 ;
3
1;
0
2;
1
3;
2
4;
0
5;
1
6;
0
7;
0
8; 2
9;
0
10 ;
3
11 ;
4
12 ; 4
13 ;
0
14 ;
3
15 ;
0
16 ;
0
Compressione: 6400/16 = 400
Decompressione
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
Decompressione
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
Decompressione
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
L(a)
Decompressione
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
L(a)
L(L(a))
Decompressione
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
L(a)
L(L(a))
L(L(L(a)))
Decompressione
L(a) = W2 (a  R1)  W3 (a  R2)  W5 (a  R1)  W8 (a  R2)  W10 (a  R3)  W11 (a  R4)  W12 (a  R4)  W14 (a  R3)
a
L(a)
L(L(a))
i
L(L(L(a)))
Barnsley M - Hurd L, Fractal image compression, 1993
Fisher Y, Fractal image compression: theory and
application to digital images, 1995
http://www.inf.uni-konstanz.de/cgip/fractal/html/index.html
[email protected]
http://univaq.it/~leonetti