|
Kategorie: Diplomové, bakalářské práce |
Tento dokument chci!
Prvním cílem diplomové práce je prostudování základních principů komprimace obrazových signálů. Seznámení se s technikami používanými pro redukci zbytečnosti a nadbytečnosti v obrazovém signálu. Druhým cílem je, na základě těchto informací, realizovat jednotlivé komprimační nástroje v programovém prostředí Matlab a sestavit tak jednoduchý model video kodeku. Diplomová práce obsahuje popis realizace tří základních komprimačních bloků a sice - kódování uvnitř snímku, mezi snímkové kódování a kódování s proměnnou délkou slova - podle standardu MPEG-2.
12.2 N-krokové vyhledávání
N-krokové vyhledávání řadí mezi algoritmy rychlého vyhledávání.
Plné vyhledávání může probíhat rastrovém nebo spirálovém uspořádání, viz obr. Velikost kroku
S vyhledávacího okna jsou dány vztahy:
S 1-
2N
= (5)
)12(/ −−+ N
, (6)
kde počet kroků.
Vyhledávací okno pro tři kroky +/- pixelů. Obecně plné vyhledávání všech vyhledávacích algoritmů nejvíce
výpočetně náročné, ovšem výhodou je, vždy nalezne globální minimum prohledávané
oblasti (minimum SAE) [2].
Spirálové uspořádání jistou výpočetní výhodu při použití předčasného ukončení
vyhledávání, protože nejlepší shoda největší pravděpodobností blízkosti středu
vyhledávací oblasti.3.
1.
Nejrozšířenější variantou N-krokového vyhledávání tříkrokové, viz obr. Nevýhodou skutečnost, algoritmus prohledává
vyhledávací oblast zvoleném počtu kroků velikostí kroku, může tedy stát,
že algoritmus nenalezne globální minimum SAE, ale pouze lokální minimum. 13. 12. Vyhledávání rastrové (vlevo) spirálové (vpravo) [2].
Obr.3. Hlavní výhodou
takového vyhledávání redukce výpočetních operací oproti plnému vyhledávání tedy
i výrazné zrychlení celého algoritmu. Prvním krokem vyhledávání výpočet osmi
hodnot SAE vzdálenosti +/- pixely, viz rovnice okolo počátku (0, včetně něj.13
∑∑
−
=
−
=
−=
1
0
1
0
RCSAE
N
i
N
j
ijij (4)
kde hodnota vzorku aktuálního makrobloku,
R hodnota vzorku referenčním snímku a
N velikost makrobloku.
Z vypočtených devíti hodnot vybere hodnota nejmenším SAE její poloha nastaví
konec začátek počátku
začátek konec
