Vectoren, matrices en beeld. Figuur: Lena. Albert-Jan Yzelman

Vectoren, matrices en beeld

Figuur: Lena

Albert-Jan Yzelman

Vectoren, matrices en beeld

Hoe coderen we foto’s zodat ze te gebruiken zijn op computers? Wat verwachten we van de bestandsgrootte? Hoe verkleinen we de benodigde opslagruimte?

Albert-Jan Yzelman

Vectoren, matrices en beeld > Vectoren

Outline

1

Vectoren

2

Matrices

3

Opslagruimte

Albert-Jan Yzelman


De reële getallen in −4

√ − 2∈

R,

R op een lijn: −3

0∈

R,

√ −2 − 2

1∈

R,

0

1

e∈

R,

2

e π

π∈

R,

4

et cetera.

Albert-Jan Yzelman


Het reële vlak

R2 = R × R:

π e 2

1 √

−2 − 2

0

1

2

e π

√ − 2 −2

Albert-Jan Yzelman


Coördinaten in het reële vlak (x, y ) ∈

R2:

√ (− 2, e) π e 2 (e, 1) 1 √ −2 − 2

0 √ − 2

1

2

e π √ (π, − 2)

−2

Albert-Jan Yzelman


R

Coördinaatparen in 2 noemen we ook wel vectoren. Er bestaan ook vectoren uit hogere dimensies: (x, y , z) ∈ 3 ,

R

Albert-Jan Yzelman


R

Coördinaatparen in 2 noemen we ook wel vectoren. Er bestaan ook vectoren uit hogere dimensies: (x, y , z) ∈ 3 , (x1 , x2 , x3 , x4 ) ∈ 4 , (x1 , x2 , x3 , x4 , x5 ) ∈ 5 , (x1 , x2 , . . . , xd ) ∈ d .

R

R R R

Albert-Jan Yzelman


~ ∈ Optellen van twee vectoren ~v , w

Figuur: ~v = (x1 , y1 )

R2.

~ = (x2 , y2 ) Figuur: w

Albert-Jan Yzelman


~ ∈ Optellen van twee vectoren ~v , w

Figuur: ~v = (x1 , y1 )

R2.

~ = (x2 , y2 ) Figuur: w

Figuur: ~v + w ~ = (x1 +x2 , y1 +y2 )

Albert-Jan Yzelman


R

In plaats van de reële getallen , kunnen we ook een ander startpunt nemen, zoals alle gehele getallen (ook wel integers):

Z

{· · · , −3, −2, −1, 0, 1, 2, 3, . . . }

−5

−4

−3

−2

−1

0

Figuur:

−4

−3

√ −2 − 2

2

3

1

2

e π

4

5

Z

0

Figuur:

1

4

R

Albert-Jan Yzelman


In het vlak:

0

Figuur:

Z2 = Z × Z Albert-Jan Yzelman


Ook hier hebben we vectoren:

(−4, 4)

(3, 2)

0

(−1, −2)

Figuur: Vectoren in

Z2 Albert-Jan Yzelman


Elke kleur is een principe een combinatie van een van de drie primaire kleuren: Rood Groen Blauw Elke pixel kan elk van deze drie kleuren apart aansturen. Elke kleur heeft een intensiteit in gehele stappen varierend van 0 (uit) tot 255 (aan): In totaal zijn er dus 256 ∗ 256 ∗ 256 = 16777216(= 224 ) verschillende kleuren mogelijk.

Albert-Jan Yzelman


Elke kleur is een vector k = (r , g , b): (0, 0, 0) (255, 0, 0) (0, 255, 0) (0, 0, 255) (255, 255, 255) (127, 127, 127) (255, 255, 0) (0, 255, 255)

zwart rood groen blauw wit grijs geel paars

Albert-Jan Yzelman


Digitaal geluid kunnen we ook zien als een vector. Trilling van een C−noot (~261 Hz) in 0.1 seconden

1

0.8

0.6

0.4

Amplitude

0.2

0

−0.2

−0.4

−0.6

−0.8

−1

0

0.01

0.02

0.03

0.04

0.05 Tijd (seconden)

0.06

0.07

0.08

0.09

0.1

Figuur: De C. Albert-Jan Yzelman


Om geluid te digitaliseren, bekijken we de amplitude op regelmatige tijdsintervallen: Trilling van een C−noot (~261 Hz) in 0.1 seconden, gesampled op 1024 Hz

1

0.8

0.6

0.4

Amplitude

0.2

0

−0.2

−0.4

−0.6

−0.8

−1

0

0.01

0.02

0.03

0.04

0.05 Tijd (seconden)

0.06

0.07

0.08

0.09

0.1

Figuur: C 1024 keer per seconde gesampled. Albert-Jan Yzelman


Deze waardes uitgelezen levert één grote vector op (102 elementen):

0,0.9994,-0.068987,-0.99464,0.13764,0.98514,-0.20565,-0.9709 Nemen we aan dat elk element uit de vector kan worden opgeslagen in 2 bytes, en dat we 44100 keer per seconde in stereo samplen, dan kost 60 seconden geluid ons 44100 · 2 · 60 · 2 = 10584000 bytes, ofwel ongeveer 10 Megabyte.

Albert-Jan Yzelman


Fourier-transformatie van tijdsdomein naar frequentiedomein: Amplitude spectrum of signal

800 700 600

Amplitude

500 400 300 200 100 0

0

500

1000

1500

2000 2500 Frequency (Hz)

3000

3500

4000

4500

Figuur: Frequentieplaatje van C gesampled op 8192 Hz. Albert-Jan Yzelman


Een echte geluidssample: Handel’s Hallelujah

0.8

0.6

0.4

Amplitude

0.2

0

−0.2

−0.4

−0.6

−0.8

0

1

2

3

4

Tijd (seconden)

5

6

7

8

9

Figuur: 9 seconden van Hadel’s Hallelujah. Albert-Jan Yzelman


Een echte geluidssample, in frequentiedomein: Amplitude spectrum of signal

1800

1600

1400

1200

Amplitude

1000

800

600

400

200

0

0

500

1000

1500

2000 2500 Frequency (Hz)

3000

3500

4000

4500

Figuur: 9 seconden van Hadel’s Hallelujah, de frequenties. Albert-Jan Yzelman


Compressie Idee: We gooien frequenties met lage amplitudes weg; ofwel, degenen met een amplitude onder t procent van het maximum. Alternatief: niet-hoorbare frequenties verwijderen. Alternatief: de hoogste van dichtbij elkaar liggende frequenties kiezen. Maar, muziek is niet opgebouwd uit continu dezelfde tonen (frequenties); deel het hele muziekstuk op in n stukjes.

Albert-Jan Yzelman


Wat hoort bij elkaar? n = 1, t = 0 n = 1, t = 1 n = 1, t = 5 n = 1, t = 50 n = 100, t = 5 n = 1000, t = 5 n = 1000, t = 10

% % % % % % %

Goede kwaliteit met redelijke compressie Op zich goede kwaliteit, maar stotterend Geen kwaliteitsverlies; perfect geluid Schel geluid boven de (goed klinkende) muziek uit Goede kwaliteit met redelijke compressie Muziek gereduceerd tot één accoord ’Gedempt’ geluid; veel detail verloren

Albert-Jan Yzelman

Vectoren, matrices en beeld > Matrices

Outline

1

Vectoren

2

Matrices

3

Opslagruimte

Albert-Jan Yzelman


π e 2

1 √ −2 − 2

0

1

2

e π

√ − 2 −2

Figuur: Een foto in het vlak

R2 Albert-Jan Yzelman


0

Figuur: Een foto over

Z2. Albert-Jan Yzelman


Voor elk gridblok kiezen we één kleur:

0

Figuur: Een foto over

Z2.

Natuurlijk leidt dit niet tot een mooi resultaat... Albert-Jan Yzelman


Figuur: Lena in 10 × 10 resolutie, uitvergroot.

We moeten de foto spreiden over een zo’n groot mogelijk grid, om een goed resultaat op het scherm te krijgen. Stel dat een foto m pixels in de verticale richting beslaat, en n pixels in de horizontale, dan projecteren we de foto over [0, m] × [0, n]. Albert-Jan Yzelman


De foto verspreid over een fijner grid:

Figuur: Lena over [0, 256]2 .

Albert-Jan Yzelman


We gaan nu tijdelijk over naar alleen grijswaarden; dit versimpelt kleurcoderingen: k is nu een geheel getal tussen 0 en 255, in plaats van een vector.

Figuur: Lena in grijswaarden Albert-Jan Yzelman


0

Figuur: Lena over

Z2.

Bij elke pixel (i, j), hoort een grijswaarde Aij . Albert-Jan Yzelman


Alle A bij elkaar genomen krijgen we een blok getallen, wat we een matrix noemen. In ons geval hebben we 512 ∗ 512 = 262144 getallen in een 512 × 512 blok: 133 133 134 129 126 128 128 128 126 126 128 128 126 125 128 128

132 131 129 129 129 129 127 127 127 127 126 126 124 127 127 129

129 129 130 129 127 127 127 127 127 128 126 122 124 127 128 128

131 132 130 127 127 119 127 127 124 126 125 128 127 126 128 128

134 134 132 130 129 128 128 128 127 127 129 128 129 128 128 130

130 130 128 129 128 128 128 128 126 126 127 127 128 129 128 128

130 129 127 125 128 127 125 127 127 128 129 128 128 129 130 131

128 128 127 122 125 127 127 125 126 130 128 128 128 128 128 131

127 128 128 126 125 127 127 125 124 131 128 130 131 129 128 131

134 134 130 125 128 125 127 127 126 130 128 128 125 130 130 130

126 127 125 125 127 128 129 125 127 125 122 128 128 126 128 131

128 128 124 122 124 125 125 125 126 127 126 127 128 128 129 135

127 124 126 128 124 126 128 125 125 126 124 120 126 123 123 122 126 126 125 124 125 124 125 124 122 123 125 125 127 128 124 127 129 124 125 128 127 129 133 128 133 137 131Albert-Jan 137 Yzelman 140 136 139 139


Onderstaande is ook een voorbeeld van een matrix: √   2 0 30 0.364 A= π 0 −9 0  0 −1.9 0 e

Albert-Jan Yzelman


Onderstaande is ook een voorbeeld van een matrix: √   2 0 30 0.364 A= π 0 −9 0  0 −1.9 0 e Matrices kunnen van elke grootte zijn. In dit geval zien we dat we 3 rijen hebben, en 4 kolommen; we spreken dan van een m bij n matrix.

Albert-Jan Yzelman


Sommatie van twee  a11  a21   a31 a41 

n × m matrices A + B.   a12 a13 b11  b21 a22 a23  + a32 a33   b31 a42 a43 b41

a11 + b11  a21 + b21   a31 + b31 a41 + b41

a12 + b12 a22 + b22 a32 + b32 a42 + b42

b12 b22 b32 b42

 b13 b23  = b33  b43

 a13 + b13 a23 + b23   a33 + b33  a43 + b43

Albert-Jan Yzelman


Vermenigvuldiging 1 × n en n × 1 matrices: A · B.   b11  b21   a11 a12 a13 a14 ·   b31  = b41 a11 ∗ b11 + a12 ∗ b21 + a13 ∗ b31 + a14 ∗ b41 = n X

a1k ∗ bk1

k=1

Albert-Jan Yzelman


Vermenigvuldiging m × 1  a11  a21   a31 a41 

en 1 × n matrices.   · 

a11 ∗ b11  a21 ∗ b11   a31 ∗ b11 a41 ∗ b11

b11

b12

a11 ∗ b12 a21 ∗ b12 a31 ∗ b12 a41 ∗ b12

b13

=

 a11 ∗ b13 a21 ∗ b13   a31 ∗ b13  a41 ∗ b13

Albert-Jan Yzelman


Vermenigvuldiging m × n en n × m matrices. 

a11 ...

a12 ...

a13 ...

b11

 ·  b21 b31

.. . .. . .. .

  = 

c11 .. .

... .. .

!

 b11 ·  b21  b31 

waar c11 =

a11

a12

a13

Albert-Jan Yzelman


Vermenigvuldiging m × n en n × m matrices.

a11 ...

a12 ...

a13 ...

 . ..  . . ·  . .. .

b12



b22

 = 

... . ..

c12 .. .

!

b32  b12 ·  b22  b32 

waar c12 =

a11

a12

a13

Albert-Jan Yzelman


Vermenigvuldiging m × n en n × m matrices.   b11 b12 a11 a12 a13 c11   b21 b22 · = a21 a22 a23 c21 b31 b32

c12 c22



c11 =

a11

a12

a13

c12 =

a11

a12

a13

 n b 11 X ·  b21  = a1k ∗ bk1 k=1 b31   n b 12 X ·  b22  = a1k ∗ bk2 k=1 b32

Albert-Jan Yzelman


Vermenigvuldiging m × n en n × m matrices.   b11 b12 a11 a12 a13 c11   b21 b22 · = a21 a22 a23 c21 b31 b32

c12 c22



c11 =

a11

a12

a13

c12 =

a11

a12

a13

cij =

 n b 11 X ·  b21  = a1k ∗ bk1 k=1 b31   n b 12 X ·  b22  = a1k ∗ bk2 k=1 b32 n X

aik ∗ bkj

k=1

Albert-Jan Yzelman


Vermenigvuldiging m × n  a11 a12 a13  a21 a22 a23   a31 a32 a33 a41 a42 a43

en n × p matrices.     c11 b11 b12   c21  ·  b21 b22  =    c31 b31 b32 c41 cij =

n X

 c12 c22   c32  c42

aik ∗ bkj

k=1

Albert-Jan Yzelman


Veelgebruikt is matrix-vector vermenigvuldiging; ofwel vermenigvuldigingen tussen m × n en n × 1 matrices.      c11 a11 a12 a13 b11  c21  a21 a22 a23    b21  =    c31  a31 a32 a33  · b31 c41 a41 a42 a43

   

Albert-Jan Yzelman


Een voorbeeld is spiegeling; bedenk wat de volgende matrix doet met vectoren uit 2 : −1 0 0 1

R

Albert-Jan Yzelman

Vectoren, matrices en beeld > Opslagruimte

Outline

1

Vectoren

2

Matrices

3

Opslagruimte

Albert-Jan Yzelman


´ en bit is een 0 of een 1. Met 1 bit kunnen we dus twee waardes E´ onderscheiden. Met twee bits worden dit er 2 ∗ 2 = 4. En met k bits kunnen we 2 ∗ 2 ∗ · · · ∗ 2 = 2k waardes onderscheiden. In [0, 255] zitten 256 = 28 waarden, dus om één grijswaarde te onthouden hebben we 8 bits nodig. Om een RGB-vector te onthouden hebben we er 3 · 8 = 24 nodig. We hebben echter ook 8 bits nodig om de doorzichtigheid van het plaatje op te slaan; we komen dus op een totaal van 32 = 25 bits.

Albert-Jan Yzelman


´ en bit is een 0 of een 1. Met 1 bit kunnen we dus twee waardes E´ onderscheiden. Met twee bits worden dit er 2 ∗ 2 = 4. En met k bits kunnen we 2 ∗ 2 ∗ · · · ∗ 2 = 2k waardes onderscheiden. In [0, 255] zitten 256 = 28 waarden, dus om één grijswaarde te onthouden hebben we 8 bits nodig. Om een RGB-vector te onthouden hebben we er 3 · 8 = 24 nodig. We hebben echter ook 8 bits nodig om de doorzichtigheid van het plaatje op te slaan; we komen dus op een totaal van 32 = 25 bits. Als we een foto hebben van 512 bij 512 moeten we dus 5122 = (29 )2 = 218 kleuren onthouden, en dus hebben we 218 · 25 = 223 bits nodig. Een byte staat gelijk aan 8 = 23 bits, dus het opslaan van Lena kost ons 223 = 220 23

bytes.

Albert-Jan Yzelman


Herinnering: we hebben 220 bytes nodig voor Lena. Omdat we continu in machten van 2 werken, defeniëren we een kilobyte als 1024 = 210 bytes, in plaats van 1000 bytes; dit deelt makkelijker. Zo hebben we namelijk dat, om een foto op te slaan, we de volgende hoeveelheid kilobytes nodig hebben: 220 = 210 = 1024. 210 we hebben dus 1 Megabyte nodig om zo’n klein plaatje op te slaan. Digitale fototoestellen maken plaatjes van minstens 1024 bij 768 pixels, dit komt dan neer op: 32 · 1024 · 768 = 3145728 b, 23

3145728 = 3072 kb, 210

3072 = 3 Mb; 1024

De meeste plaatjes van die afmetingen zijn echter in de orde van 500 tot 600 kilobyte groot. Dit is bijna een zesde van de originele grootte! Albert-Jan Yzelman

Vectoren, matrices en beeld. Figuur: Lena. Albert-Jan Yzelman

Recommend Documents