Z predchádzajúcich kapitol je zrejmé, že dynamický obraz pozostáva zo série po sebe nasledujúcich statických obrazov. Za predpokladu dostatočnej obnovovacej frekvencie je ľudským zrakom táto séria snímok vnímaná ako kontinuálny pohyb. Z uvedeného vyplýva, že snímky sú vzájomne vysoko korelované (za predpokladu že nedochádza k rýchlej zmene scény). Túto vzájomnú korelovanosť je možné využiť pri návrhu predikčného systému. Obrazový prvok je teda možné predikovať nielen na základe predchádzajúcich prvkov danej snímky ale aj pomocou op predchádzajúcej snímky. Obrazové prvky v predchádzajúcej snímke môžu mať rovnaké súradnice ako predikovaný obrazový prvok ale tiež sa môžu líšiť. Rovnako ako pre vnútrosnímkovú predikciu, aj pre medzisnímkovú predikciu existujú optimálne algoritmy vychádzajúce z autokorelačnéj funkcie. V prípade, že táto nie je známa je možné použiť suboptimálne algoritmy. Pri návrhu predikcie je vždy potrebné vychádzať z požiadaviek danej aplikácie. Predikcia je vykonaná na základe trojrozmerného okolia predikovaného op. V takom prípade hovoríme o nemennej predikcii. Na obr. 10 je pre ilustráciu zobrazená nemenná medzisnímková predikcia 7 rádu.
Obr. 9 Medzisnímková predikcia 7. radu
Estimácia pohybu
Je zrejmé, že ak hovoríme o dynamickom obraze, logicky dochádza k posunutiu objektov zachytených v obraze. Teda vykonávať predikciu iba na základe okolia predikovaného op nemusí byť efektívne. Z tohto dôvodu boli vyvinuté algoritmy predikcie s pohybovou kompenzáciou. Princíp týchto algoritmov spočíva v aktualizácii polohy op predošlej snímky. Táto aktualizácia sa vykoná na základe vektoru pohybu, ktorý popisuje zmenu polohy op.
Obr. 10 Princíp medzisnímkovej predikcie obrazu
Ako sme už ukázali, pre Pre vykonanie medzisnímkovej predikcie je nutné poznať vektor posunutia . Je zrejmé, že tento nie je možné (resp. bolo by to veľmi nepraktické) vypočítavať pre každý jeden prvok. V princípe, bez ohľadu na použitý algoritmus estimácie pohybového vektoru, je tento vždy vyhľadávaný pre určitú oblasť obrazových prvkov – blok. Tieto bloky môžu mať tvar pravouhlého okna alebo ich tvar môže zodpovedať tvarom nasnímaných objektov. Pre jednoduchosť ďalej budeme uvažovať pravouhlé bloky s rozmerom MxN op. Princíp estimácie pohybového vektora spočíva v rozdelení obrazu na menšie bloky. Pre každý blok aktuálnej snímky sa vyhľadáva korešpondujúci blok v predchádzajúcej snímke. Toto vyhľadávanie sa vykonáva len v určitej definovanej oblasti. Táto je daná maximálnou možnou hodnotou posunutia bloku za dobu, ktorá uplynie medzi dvoma snímkami. Pokiaľ sa taký blok nájde, rozdiel súradníc medzi jeho pôvodnou a novou polohou bude predstavovať vektor pohybu. Princíp vyhľadávania bloku je zobrazený na nasledujúcom obr. 11.
Obr. 11 Princíp medzisnímkovej predikcie obrazu s blokovým vyhľadávaním
Samotné vyhľadávanie sa uskutočňuje pomocou vyhodnocovania dvojrozmernej normovanej korelačnej funkcie r(V). Poloha posunutého bloku je daná súradnicami (i‘, j‘) pohybového vektora v mieste, kde táto funkcia nadobudne maximálnu hodnotu.
Túto normovanú korelačnú funkciu je možné prepísať do tvaru:
Presnosť predikcie s pohybovou kompenzáciou závisí hlavne na veľkosti bloku a rýchlosti pohybu. Je potrebné nájsť kompromisný rozmer bloku. Ak je blok príliš malý, bude vo zvýšenej miere dochádzať k nesprávnej detekcii (menej prvkov --> vyššia pravdepodobnosť vysokej korelácie s nesprávnym blokom). Ak je blok príliš veľký, nezachytí pohyb rôznych častí obrazu. Výpočet korelácie je výpočtovo náročný a pre zvýšenie efektivity vyhľadávania je možné použiť aj inú vyhodnocovaciu funkciu. Uvedieme napríklad funkciu skreslenia s využitím strednej kvadratickej chyby. V tomto prípade budeme na rozdiel od korelačnej metódy hľadať minimálnu hodnotu tejto funkcie.
Vyššie popisovaná metóda sa nazýva aj metóda úplného prehľadávania, pretože hodnota korelačnej, resp. chybovej funkcie sa vyšetruje v celej stanovenej oblasti. Takéto vyhľadávanie je pomalé a z praktického hľadiska je vhodnejšie vyhľadávanie vykonať niektorým z rýchlych algoritmov.
Rýchle algoritmy
Rýchly algoritmus pracuje tak, že sa hodnota funkcie skreslenia vypočíta najprv vo všetkých 8 smeroch od stredu bloku. Hodnota skreslenia sa vypočíta vo vzdialenosti, ktorá vychádza z maximálneho posunutia. Na obr.11 12 uvažujeme blok s veľkosťou 3x3 op, maximálne posunutie budeme uvažovať 6 op. Vzdialenosť medzi stredmi blokov v aktuálnej a nasledujúcej snímke pre prvú iteráciu budeme uvažovať 3 op. Potom, ako sa nájde vektor posunutia definovaný prostredným prvkom nájdeného bloku, nasleduje ďalšia iterácia. V tejto iterácii sa v 8 smeroch prehľadáva okolie prostredného prvku, ale vzdialenosť je teraz len 2 op. Potom, ako sa znova nájde prostredný prvok, pri ktorom je hodnota skreslenia najmenšia, prechádza sa do poslednej iterácie. V tretej iterácii sa prehľadáva okolie so vzdialenosťou jedného op. Tento proces je zobrazený na obr. 12.
Obr. 12 Princíp vyhľadávania bloku pomocou rýchleho algoritmu
Adaptívne algoritmy
Dynamický obraz zachytáva pohyb rôznych častí vizuálnej scény, ktorý sa vo všeobecnosti pre tieto líši. Častí obrazu sa môžu pohybovať rôznym smerom a rôznou rýchlosťou. Môžu byť väčšie i menšie. Je preto výhodné, aby veľkosť bloku bola aspoň čiastočne ovplyvnená týmito parametrami. Toto zabezpečujú adaptívne algoritmy. Princíp spočíva v rozdelení obrazu na bloky vo viacerých rovinách. V prvom kroku sa obraz rozdelí na rovnaké bloky tak ako to bolo popísané vyššie. Následne sa v zvolenom počte krokov vyhľadajú korešpondujúce bloky. Bloky, pre ktoré funkcia skreslenia prevýši zvolený prah, sa ďalej rozdelia na menšie bloky (napr. na štvrtiny). V týchto blokoch sa znova vykoná vyhľadávanie a proces delenia bloku sa opakuje. Vektor pohybu navyše nie je potrebné odhadovať vo všetkých smeroch, ako to bolo popísané vyššie. Na vyššej úrovní je výhodné Vektor vektor pohybu inicializovať vektorom pohybu z predchádzajúcej úrovne. Tiež je možné použiť niektorú z techník interpolácie. Takto sa navyšuje počet úrovní, až dokiaľ funkcia skreslenia pre všetky bloky nemá podprahovú úroveň alebo sa nedosiahne stanovená maximálna úroveň. Tento postup pre tri úrovne je zobrazený na obr. 13.
Obr. 13 Trojúrovňová adaptívna estimácia pohybu s delením bloku na podbloky
Na obr. 14 je zobrazená jedna snímka videosekvencie rozdelená na bloky a podbloky pomocou adaptívneho algoritmu. Z obr. 14 je možné usúdiť, že tie časti scény, ktoré vykazujú vysokú dynamiku (hráči, lopta) sú rozdelené na menšie bloky 2. a 3. úrovne a časti, ktoré sa tak výrazne nepohybujú (trávnik) budú spracovávané v blokoch 1. úrovne.
Obr. 14 Trojúrovňová adaptívna estimácia pohybu aplikovaná na jednu snímku videosekvencie [https://www.canon.co.nz/cameras/xf705]