Informační systémy ve zdravotnictví d i í ZS 2008/2009 Zoltán Szabó Tel : (+420) 312 608 207 Tel.: E-mail:
[email protected] č.dv.: 504, 5.p
Dnešní přednáška
Kódování, komprese
2
1
Komprese dat Cíl komprese: redukovat objem dat za účelem přenosu dat archivace dat Kvalita komprese: rychlost komprese symetrie/asymetrie kompresního algoritmu Symetrické algoritmy – stejný čas potřebný pro kompresy i dekompresi Asymetrické algoritmy – čas potřebný pro kompresi a dekompresi se liší
3
Míra komprese Komprimované Nekomprimované
Kompresní poměr = př: ř 40/160 = 1/4 = 0 0,25 25
Ratio = 1 - kompresní poměr (úspora, udává kolik % ušetřilo) př: 1 - 0,25 = 0,75 = 75%
Bit per pixel = velikost obrazu [bit] / počet pixelů v obraze př: 65536 / (256x256) = 1 bpp 4
2
Komprese dat
bezztrátová - po kódování a dekódování je výsledek 100% shodný,
nižší kompresní poměr požívají s výhradně pro kompresi textů a v případech, kdy nelze připustit ztrátu informace
ztrátová - po kódování a dekódování dochází ke ztrátě
obvykle vyšší kompresní poměr než bezztrátové lze p použít p pouze v p případech p kdy y ztráta jje akceptovatelná p (komprese obrazů, zvuku
5
Metody komprese
jednoduché – založené na kódování opakujících se posloupností znaků (RLE) statistické – založené na četnosti výskytu znaků v komprimovaném souboru (Huffmanovo kódování, Aritmetické kódování) slovníkové – založené na kodování všech vyskytujících se posloupností (LZW) transformační – založené na ortogonálních popř popř. jiných transformacích (JPEG, waveletová komprese, fraktálová komprese)
6
3
RLE - kódování délkou běhu RLE (Run Length Encoding) Princip: opakující se symboly se kódují dvojicí Počet opakování Symbol Př. Vstup: Vý t Výstup:
AAAABBCDDDDABD 4A2B1C4D1A1B1D
Nevýhoda: pokud se znaky neopakují často nedochází ke kompresi, ale naopak k prodloužení kódovaného souboru 7
RLE - kódování délkou běhu
pomocí escape sekvencí – kódují se pouze opakující se sekvence delší než 3 znaky, kratší sekvence se zapisují přímo do výstupního souboru b Př. Vstup: AAAABBCDDDDABD Výstup: #4ABBC#4DABD
Výhoda: neprodlužuje soubor, kde není co komprimovat to zůstane v původní podobě Pozn.:
escape - z množiny znaků je nutné vyčlenit symbol, který se nevyskytuje v komprimovaném souboru. Dále může nastat problém pokud je opakující se sekvence delší než 255 znaků (pokud kódujeme délku běhu na 8 bitech). Řešení závisí na konkrétní aplikaci
Použití RLE: např. obrazový formát BMP 8
4
LZW (Lempel-Ziv-Welch) metoda Princip: vyhledávání hl dá á í opakujících k jí í h se posloupností l tí znaků, ků ukládání kládá í tě těchto ht posloupností do slovníku pro další použití a přiřazení jednoznakového kódu těmto posloupnostem. jednoprůchodová metoda (nevyžaduje předběžnou analýzu souboru) Při průchodu komprimovaným souborem se vytváří slovník (kde první položky jsou znaky původní abecedy a zbývající položky tvoří posloupnosti znaků obsažené v komprimovaném souboru.
9
LZW (Lempel-Ziv-Welch) metoda Algoritmus komprese a vytvoření slovníku
Výsledný výstupní řetězec: 65 66 67 256 258 257 68 259
10
5
Huffmanovo kódování
algoritmus navržen v Davidem Huffmanem v roce 1952 kódové symboly mají proměnnou délku
Princip: Metoda je založená na stanovení četnosti výskytů jednotlivých znaků v kódovaném souboru a kódování znaků s největší četností slovem s nejkratší délkou. Algoritmus kódování: Zjištění četnosti jednotlivých znaků v kódovaném souboru 2. Vytvoření binárního stromu (Huffmanova kódu jednotlivých znaků) 3 3. Uložení stromu 4. Nahrazení symbolů jednotlivými kódy (posloupností bitů) 1.
11
Příklad: ABRAKADABRA
(11)
10010110001100001001011
0
(6)
Algoritmus vytvoření stromu
0 A R B K D
1 01 001 0001 0000
1
(4)
1
0 1
(2) 0 1
D (1)
K (1)
B (2)
R (2)
A (5) 12
6
Dekomprese 1. Načtení a obnovení stromu, algoritmus je popsán při kompresi X 2 Vlastní dekomprese: Nahrazení kódů původními znaky. 2. znaky Příklad: 10010110001100001001011
A R B K D
1 01 001 0001 0000
ABRAKADABRA
13
Zpracování biosignálu
Digitální zpracování – A/D převod EKG – Diagnosticky podstatné od 0,5 do 150 Hz Vzorkování EKG – 250 až 1000 vzorků/s. (pro klinické účely doporučeno 500 vzorků/s)
Filtrace Šum způsobený napěťovými interferencemi, kolísáním isoelektrické linie, svalové artefakty, apod. Doporučena hranice 0,05 Hz (aby nedošlo ke zkreslení T vlny a ST úseku)) • Speciální problém – odstranění síťové frekvence 50 Hz Detekce pozdních potenciálů (ve srovnání s EKG mají velmi malou amplitudu a vysoký frekvence – min. 1000 Hz až 8000 Hz) → kumulační metody odstranění šumu.
7
Zpracování biosignálu
Komprese dat
Vzorkování vs. Množství dat
Bezeztrátová vs. ztrátová komprese
R Rozpoznání á í začátku čátk a konců k ů jjednotlivých d tli ý h vln l a kmitů Např.: • Prahování • Korelace
R
T
P QS
Počítačové systémy pro analýzu EKG Základními parametry jsou úseky a intervaly, z těchto jsou pak odvozeny další parametry (různé poměry jednotlivých kmytů komplexu QRS), gradienty, integrály a úhly. Běžně dnes – více než 300 ukazatelů.
Zpracování obrazu RTG, CT, NMR, PET, SPECT, UZ, termovize Pořízení obrazu
Zpracování
Uchování
Obecný systém pro zp pracování obrazu
Zobrazení
8
Zpracování obrazu
Základní pojmy
CCD (Charge Coupled Devices – nábojově vázané struktury) obsahuje světlocitlivé prvky, p y které g generujíj množstvý ý elektrického náboje úměrné počtu dopadajících fotonů Rozlišovací schopnost, DPI (Dots Per Inch) Bitová hloubka obrazu (28, u CT 210=1024 úrovní) Šedotónový, černobílý, barevný, pseudobarevný obraz
Zpracování obrazu
Komprese - JPEG
JPEG (Joint Photographic Experts Group)
9
Zpracování obrazu
Komprese - JPEG Originál 243 054 bajtů j
Komprimovaný ~30:1 7 977 bajtů j
X=imread('Kobzanova.bmp','bmp'); imwrite(X,'q50.jpg','jpg','Quality',50);
Zpracování obrazu
Komprese - JPEG Originál 243 054 bajtů j
Komprimovaný ~70:1 3 400 bajtů j
X=imread('Kobzanova.bmp','bmp'); imwrite(X,'q10.jpg','jpg','Quality',10);
10
Zpracování obrazu
Komprese - JPEG Originál 243 054 bajtů j
Komprimovaný ~100:1 2 415 bajtů j
X=imread('Kobzanova.bmp','bmp'); imwrite(X,'q4.jpg','jpg','Quality',4);
Zpracování obrazu
Komprese - JPEG
•
Čtyři modifikace: • bezeztrátový mód kódování • sekvenční kódování • progresivní kódování • hierarchické kódování
r = Predikce - x
vstup
Prediktor
C B A x
Predikce A B C A+B-C A+(B-C)/2 B+(A-C)/2 (A+B)/2
VLC
výstup
Kódovací tabulka
11
Zpracování obrazu
Komprese - JPEG
•
Čtyři modifikace: • bezeztrátový mód kódování • sekvenční kódování • progresivní kódování • hierarchické kódování
Sqv,u
8x8 blok
DCT
Sx,y
Kvantizátor
VLC
Kvantizaèní tabulka
Kódovací tabulka
výstup
Sv,u vu
⎡ 7 7 (2 x + 1)uπ cos (2 y + 1)vπ ⎤ 1 S vu = Cu Cv ⎢ S yx cos ⎥ 4 16 16 ⎣⎢ x = 0 y = 0 ⎦⎥
∑∑
kde Cu , Cv =
1 1
q S vu = round
S vu Qvu
2 pro u , v = 0 jinak
Zpracování obrazu
Komprese - JPEG
•
Čtyři modifikace: • bezeztrátový mód kódování • sekvenční kódování • progresivní kódování • hierarchické kódování
12
Zpracování obrazu
Komprese - JPEG 4↓
•
Čtyři modifikace: • bezeztrátový mód kódování • sekvenční kódování • progresivní kódování • hierarchické kódování
Encode 2↑
Decode
2↓
+ + 2↑
+ +
+ +
Encode Decode
Encode
13
