Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky. Diplomová práce. Stabilizace obrazu

Západočeská univerzita v Plzni Fakulta aplikovaných věd Katedra informatiky a výpočetní techniky

Diplomová práce Stabilizace obrazu

Plzeň, 2008

Petr Sládek

Abstract Video image stabilization is an important video enhancement technology for removing unwanted shaky motion from the video. However, most of the methods do not provide the video author the needed freedom to influence the image movement in the resulting video shot. Ordinary filtering methods provide some preset values for stabilization. Those values are fixed and cannot be changed. To influence the resulting video, we need some editable parameters. This diploma thesis deals with the digital video stabilization, while enabling the user of this system to freely choose the desired trajectory of the processed video. The methods used include feature based motion tracking using local motion vectors. Stabilization is reached by filtering and optionally by drawing Cubic Hermite splines.

1

Obsah 1 Úvod

6

1.1

Stabilizace obrazu . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2

Filmový průmysl . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3

Mechanická stabilizace . . . . . . . . . . . . . . . . . . . . . .

9

1.4

Optická stabilizace . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5

Elektronická stabilizace . . . . . . . . . . . . . . . . . . . . . . 12

1.6

Stabilizace digitálním filtrem . . . . . . . . . . . . . . . . . . . 14

2 Digitální stabilizace

16

2.1

Zpracování obrazu . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2

Rozdílové metody . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3

Detekce významných bodů . . . . . . . . . . . . . . . . . . . . 23

2.4

Shrnutí algoritmů . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Implementační rozhodnutí

26

3.1

Existující software . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2

Rozdělení aplikace . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3

Křivky trajektorií . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.4

Interpolační křivky Spline . . . . . . . . . . . . . . . . . . . . 31

3.5

Sledování trajektorie . . . . . . . . . . . . . . . . . . . . . . . 34

3.6

Super-resolution . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.7

Dva sledované body . . . . . . . . . . . . . . . . . . . . . . . . 38

3.8

Stabilizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.9

Spojování oblastí . . . . . . . . . . . . . . . . . . . . . . . . . 40 2

3.10 Editování křivek . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.11 Transformace času . . . . . . . . . . . . . . . . . . . . . . . . 43 3.12 Prokládané video . . . . . . . . . . . . . . . . . . . . . . . . . 44 4 Implementace

46

4.1

Antishake v C# . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2

Sledování trajektorie . . . . . . . . . . . . . . . . . . . . . . . 49

4.3

Slučování trajektorií . . . . . . . . . . . . . . . . . . . . . . . 50

4.4

Křivky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.5

Antishake pro VirtualDub . . . . . . . . . . . . . . . . . . . . 53

4.6

Implementace transformací . . . . . . . . . . . . . . . . . . . . 55

4.7

Stručný návod . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5 Závěr

67

5.1

Dosažené výsledky . . . . . . . . . . . . . . . . . . . . . . . . 67

5.2

Další práce

5.3

Zhodnocení . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Literatura

71

3

Prohlašuji, že jsem diplomovou práci vypracoval samostatně a výhradně s použitím citovaných pramenů.

V Plzni dne 22. dubna 2008

Seznam obrázků 3.1

Ukázka rozhraní programu Deshaker . . . . . . . . . . . . . . 27

3.2

Porovnání vlastností několika typů spline funkcí . . . . . . . . 33

3.3

Porovnání vzdálenosti řídících bodů Coonsovy křivky (vlevo) v porovnání s řídícími body Bézierovy křivky (vpravo) . . . . 34

3.4

Princip hledání motion vektoru . . . . . . . . . . . . . . . . . 35

3.5

Princip slučování oblastí v jeden celek . . . . . . . . . . . . . . 40

4.1

UML diagram TimeLineSegment . . . . . . . . . . . . . . . . 50

4.2

Význam prvků datové struktury pro Bézierovu křivku . . . . . 52

4.3

Princip algoritmu de Casteljau . . . . . . . . . . . . . . . . . . 52

4.4

Úvodní okno programu Antishake . . . . . . . . . . . . . . . . 60

4.5

Zadávání sledovaných bodů . . . . . . . . . . . . . . . . . . . 61

4.6

Stabilizace křivkami

4.7

Graph Preview . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.8

Okno programu VirtualDub . . . . . . . . . . . . . . . . . . . 65

. . . . . . . . . . . . . . . . . . . . . . . 62

5

Kapitola 1 Úvod Stabilizace obrazu je odvětví technologií, které se využívá pro rozmanité spektrum úkolů a výrobků. Tyto výrobky zahrnují dalekohledy s optickou stabilizací, fotografické a videografické přístroje a astronomické teleskopy. Cílem stabilizace je zlepšení kvality obrazu buď pro subjektivní pocit diváka anebo pro usnadnění dalšího technického zpracování obrazu. Při fotografování zhoršují ostrost obrazu otřesy a chvění, což zvyšuje nároky na techniku fotografa. Zvláště problematické jsou otřesy při nižší rychlosti závěrky nebo při použití delší ohniskové vzdálenosti objektivu. Při snímání videokamerou způsobuje třes rušivé chvění obrazu, které je obzvláště patrné při sledování záběru krokovaného snímek po snímku. Oborem této diplomové práce je stabilizace záznamu pořízeného videokamerou. Stabilizace obrazu videa je důležitá technologie, která zlepšuje výslednou kvalitu snímaného videoobrazu. Jejím úkolem je odstranit rušivý třes obrazu způsobený pohybem kamery v době snímání. Třes kamery může být způsoben nestabilitou podstavce kamery, nebo kamerou pohybující se po nerovném povrchu. V amatérských podmínkách bývá nejčastější příčinou natáčení videa z ruky, kde nestabilita pochází z chvění rukou, dechu a srdečního pulsu osoby, která ovládá kameru. Stabilizaci obrazu je možné v takovém případě do jisté míry použít i jako náhradu pevného stativu. V profesionální praxi se použití stabilizátorů nepreferuje, běžné profesio-

6

nální kamery stabilizátory neobsahují vůbec, pokud se pro záznam používá poloprofesionální kamera, pak často kameraman možnost stabilizace vypíná. Režiséři záznamu požadují, aby primární záznam měl co nejvyšší možnou kvalitu, proto se snaží, aby použití stabilizátorů vůbec nebylo zapotřebí. Pokud už se stabilizátory v profesionální praxi využívají, jedná se o speciální záběry, například z letadla, při seskoku padákem nebo jízdě autem. Pokud se při natáčení nevyužívají náročné mechanické stabilizátory, ale stabilizace v postprodukci (rozdělení bude vysvětleno později), klade se důraz na co možná nejnižší zásah do videozáznamu. Není tedy prakticky možné video soubor přesunout ze záznamové jednotky do počítače, zpracovat jej samostatným stabilizačním filtrem a poté jej teprve přesouvat do střižny. Fázi stabilizace videa by proto mělo být možné zařadit do řetězce pro zpracování videa. I na tento aspekt bylo při zpracování této diplomové práce brán zřetel. Stabilizace obrazu je podstatná nejen pro videozáznamy, které jsou určeny pro promítání divákům, ale také pro technické účely a automatické zpracování nebo rozpoznávání obrazu. Podle článku [11] mohou tyto technické účely zahrnovat například zpracování obrazu v reálném čase, navádění samočinných robotů, detekce nebo sledování pohybu a také chirurgické operace prováděné na dálku. Podle článku [8] je nejvíce patrný třes obrazu, pokud se kamera pohybuje v době snímání videa. Další faktor, který negativně ovlivňuje obraz a jeho subjektivní vnímání, je velká ohnisková vzdálenost. Další odstavce detailně rozebírají technickou stránku stabilizace obrazu.

1.1

Stabilizace obrazu

Tato kapitola popisuje mnoho různých druhů stabilizací, které se v současné době používají ať už pro pořizování fotografií, snímání videa anebo filmu. Hlavní důraz je kladen na technologie, které se používají pro video. Některé technické aspekty však tato kapitola neobsahuje, protože přímo nesouvisí s tématem diplomové práce. Jako příklad je možné uvést stabilizaci

7

obrazu astronomických teleskopů. Další příklad využití stabilizace z neobvyklé oblasti uvádí článek [14]: optická stabilizace je zařazena před modul řízení naváděné rakety. Stabilizátor s gyroskopem a elektromagnetickými horizontálními a vertikálními cívkami vyvažujícími optiku objektivu snímá cíl naváděné rakety, výstup tohoto stabilizátoru se předává modulu pro sledování cíle, který řídí let rakety.

1.2

Filmový průmysl

První pokusy se stabilizací obrazu se objevily v 70. letech 20. století pro účely natáčení celovečerních filmů. V těchto filmech bylo z dramaturgických důvodů nutné natáčet jízdu kamery náročnější technologií. Na rozdíl od snímání statické scény, při které stojí kamera na stativu, který ji pevně drží připoutanou k zemi, se pro scény v pohybu používal vozík na kolejnicích, který umožňoval plynulý pohyb. Tento vozík většinou tlačili zkušení kameramani, jak popisuje článek [18]. Tato metoda natáčení umožňuje plynulý pohyb při jízdě kamery bez znatelných otřesů, ale má také značné nevýhody. První nevýhodou je, že příprava kolejnic a dalšího zařízení je technicky i časově náročná. Další nevýhodou je, že režisér vždy musí scénu prostorově rozvrhnout tak, aby se v záběru neobjevily kolejnice nebo další zařízení. Dále není možné koleje postavit v rozmanitém terénu, nejde například snímat chůzi do schodů – kolejnice by se objevily v záběru a navíc lze vozíkem pohybovat pouze po vodorovném či jen mírně naklopeném terénu. Alternativní možností bylo použít záběr „z rukyÿ, to znamená, že kameraman nepoužívá kameru připevněnou na nějaký úchyt anebo podstavec, ale drží ji a ovládá jen svýma rukama, což mu poskytuje potřebnou rychlost a flexibilitu. Tento způsob práce sice umožňuje kameramanovi pořídit záběry, které by jinak nebylo možné nasnímat, ale ani nejzkušenější kameraman nedokáže zabránit třesení obrazu, pocházející z pohybů jeho těla. Z těchto důvodů se záběry „z rukyÿ pořizovaly většinou jen pro reportážní účely nebo jako

8

speciální efekt dramatických scén, vyvolávající v divácích pocit bezprostřední přítomnosti. V 70. letech se objevila první zařízení pro stabilizaci obrazu, která tento nechtěný vedlejší efekt eliminovala. Z hlediska technického provedení jsou možné tyto tři druhy stabilizace: • Mechanická stabilizace • Optická stabilizace • Elektronická stabilizace Nyní se na každý z těchto typů zaměříme podrobněji.

1.3

Mechanická stabilizace

První zařízení, které umožňovalo mechanickou stabilizaci obrazu vynalezl kameraman Garrett Brown. Svůj vynález nazval „Brown Stabilizerÿ [17]. Výhradní licenci na toto zařízení zakoupila firma Cinema Products Corporation a později jej uvedla na trh pod obchodním názvem Steadicam. V říjnu 2000 odkoupil obchodní známku výrobce The Tiffen Company LLC. První celovečerní film, který využíval technologii Steadicam, byl natočen v roce 1976 a jmenoval se Rocky. Zařízení funguje na mechanickém principu – kameraman si na tělo oblékne postroj, ke kterému je ramenem připevněna kamera. K ramenu je na opačné straně připevněno závaží, které tvoří protiváhu kamery. Přidáním závaží se zvyšuje i setrvačnost celé soustavy, což zabraňuje roztřesení kamery, přitom má ale kameraman stále volné ruce a tak může ovládat kameru. Jako protiváha se z praktických důvodů využívá monitor nebo baterie kamery. V současné době firma Tiffen vyrábí pod názvem Steadicam velkou škálu zařízení, od průmyslových jeřábů s elektromechanickým držákem na kameru, po malá zařízení ovládaná jedinou osobou [19]. Většinou jsou stabilizátory na mechanickém principu rozměrné a nákladné. Existují ale i levné amatérské montáže, například [20]. 9

1.4

Optická stabilizace

Kamery s dlouhou ohniskovou vzdáleností a špičkové dalekohledy používají optickou stabilizaci. Ta funguje na principu pohybu některého členu optiky objektivu nebo – v případě digitálního snímače – pohybu samotného snímacího čipu. V těchto zařízeních není optika pevně připojena k tělu kamery, ale je volně vázána závěsem, ve kterém se může mírně pohybovat. Optická stabilizace se snaží zajistit mechanickým posuvem, nakláněním či natáčením pohyblivého členu optiky nebo snímacího členu, aby paprsky, které vycházejí z jednoho bodu snímané scény, dopadaly během expozice stále na tentýž bod snímače. Zařízení s optickou stabilizací většinou používají gyroskop pro detekci pohybu kamery. Elektromagnetické cívky potom pohybují optikou objektivu proti směru pohybu kamery, čímž vyrovnávají nechtěný pohyb a výsledný obraz se tak přestává třást. Pro stabilizaci optikou se využívá buď optického měchu, plovoucí čočky nebo pohybu celého objektivu. Další odstavce podrobně popisují každou technologii zvlášť. V případě optického měchu je uvnitř objektivu umístěn optický člen, který se skládá ze dvou čoček propojených pružným měchem, který dovoluje natáčení jedné čočky vůči druhé. Měch je tvořen silikonem se stejným indexem lomu jako okraje čoček. Natáčením přední či zadní čočky a deformací měchu se pomocí připojené mechanické či elektronické vyrovnávací soustavy mění úhel lomu paprsků tak, aby paprsky dopadaly stále na stejné místo snímacího čipu. Výsledný obraz za objektivem se proto během expozice nechvěje a je ostrý [30]. Nejčastější metodou optické stabilizace je takzvaná plovoucí čočka. Jedná se o dodatečnou čočku v objektivu, která se může pohybovat a korigovat tak chvění fotoaparátu. Tyto korekce jsou řízeny na základě údajů z gyroskopických senzorů, které indikují nežádoucí změny polohy a patřičné informace předávají plovoucí čočce. Článek [22] uvádí značení objektivů různých firem: objektivy Canon EF SLR mají ke jménu připojena písmena IS (anglicky „Image Stabilizationÿ), objektivy Nikkor firmy Nikon mají k názvu připo10

jena písmena VR (anglicky „Vibration Reductionÿ). Dále tento článek uvádí, že při použití optické stabilizace je možné snímat až se čtyřikrát nižší rychlostí závěrky, než byla-li by optická stabilizace vypnutá. Firma Canon používá stabilizaci pomocí posuvu skupiny korekčních čoček v horizontálním a vertikálním směru, tento systém nazývá IS. Nabízí tři fotografické režimy: první režim koriguje pohyb plynule (po celou dobu zaostřování, navíc funguje i při snímání video sekvencí), druhý režim začíná působit až po zmáčknutí spouště, třetí režim funguje pouze ve směru kolmém na směr pohybu fotoaparátu. Třetí režim je vhodný zejména při sledování pohybujícího se objektu. Podle článku [28] se ve výrobcích firmy Canon používají gyroskopy pouze pro horizontální a vertikální pohyb, takže není možné korigovat rotaci kolem optické osy. Firma Nikon pro stabilizaci objektivů používá plovoucí čočky, se kterými se pohybuje prostřednictvím elektromotorků. Tato stabilizace však funguje pouze až při namáčknutí spouště a označuje se jako VR. Nikon nabízí i vylepšenou stabilizaci VRII, která pracuje ve dvou režimech: normální (pro slabší vibrace) a aktivní (pro silnější vibrace, např. při fotografování z jedoucího automobilu). O tomto systému podrobně informuje článek [29]. Technologie firmy Panasonic se nazývá O.I.S. (anglicky „Optical Image Stabilizerÿ). Uprostřed objektivu je umístěn posuvný optický člen, který se vyrovnává na základě informace z gyrosenzorů. Ten nabízí dva provozní režimy: v prvním režimu funguje stabilizace plynule již při komponování snímku, ve druhém režimu až při domáčknutí spouště a samotné expozici. První režim poskytuje fotografovi větší pohodlí, ale druhý způsob je o trochu účinnější. Optické stabilizátory s plovoucí čočkou využívá také Kodak EasyShare a Sony CyberShot. Výrobky Konica-Minolta využívají ke stabilizaci pohyb celého objektivu. Tento způsob je možný pouze u lehkých kapesních kompaktních fotoaparátů s periskopickými objektivy, které jsou celé uvnitř těla fotoaparátu a nevysouvají se ven.

11

Další, principielně odlišný přístup, který se také řadí k optické stabilizaci, popisují články [23], [32], [30]. Jedná se o pohyb samotného snímacího čipu CCD, který je za tímto účelem umístěný na speciálním gelovém podkladu. Hlavní výhoda tohoto způsobu stabilizace je nezávislost na použitém objektivu – funguje s různými výměnnými objektivy, které tak mohou být lehčí, menší a levnější. Technologii pohybu snímacího čipu využívají zejména digitální fotoaparáty. Nevýhodou však je, že v případě zrcadlovek s průhledovým hledáčkem není při komponování snímku vidět výsledek stabilizace. Tuto technologii uvedla na trh firma Konica Minolta. V produktové řadě této firmy se označuje AS (anglicky „anti-shakeÿ). Podle referencí tento systém stabilizace velmi dobře funguje. Například článek [23] uvádí, že zařízení DiMAGE A2 umožňuje pracovat až s osmkrát delší expoziční dobou, pokud je zapnutý systém „anti-shakeÿ. Tuto technologii proto převzaly i firmy Sony a také Pentax.

1.5

Elektronická stabilizace

Poslední možností stabilizace obrazu je elektronická stabilizace, což je operace nad výsledným nasnímaným obrazem videa, nikoli stabilizace samotné kamery nebo její optiky. Tato metoda se ve fotoaparátech používá výhradně pro natáčení video sekvencí, nelze ji využít při fotografování. Běžně se také používá v digitálních videokamerách. Výhoda elektronické stabilizace je, že nevyžaduje žádné další mechanické součásti a může být prováděna s videem pořízeným z jakéhokoli přístroje. Dále se nemusí na rozdíl od předchozích zmíněných metod uplatňovat v reálném čase (v době natáčení záběru), ale je možné ji spustit až v postprodukci nebo při sestřihu scény. Elektronická stabilizace pracuje na jednoduchém principu, při kterém se pro tvorbu obrazu nevyužívá celý snímací čip, ale pouze jeho část a při pohybu fotoaparátu nebo videokamery se tento obdélníkový výřez posouvá určitým směrem po snímači. Vhodným algoritmem lze sledovat zaznamenávaný

12

objekt a současně posouvat oblast čipu, ze které se bude číst záznam, jak uvádí články [30] a [32]. Nevýhodou této metody je, že na rozdíl od výše uvedené optické a mechanické stabilizace nejde uplatnit na fotoaparáty a fotografie, neboť neovlivňuje každý jednotlivý snímek doostřováním snímku, ale mění relativní prostorové umístění jednotlivých snímků v různých časech celého záběru. Stabilizační algoritmus zjišťuje směr a rychlost posuvu buď v reálném čase anebo až ve fázi postprodukce. Hlavní rozdíl mezi systémy reálného času a systémy fungujícími ve fázi postprodukce je, jak uvádí článek [28], že systémy fungujícími v reálném čase využívají jen část plochy snímacího čipu, zbytek plochy se využije tehdy, pokud je nutné posunout výřez snímání kvůli stabilizaci. Naproti tomu digitální stabilizační filtry, které se používají až ve fázi postprodukce, mají celou snímanou oblast předem pevně omezenou rozsahem obrazu vstupního videa. Při posouvání snímku videa by se teoreticky měla data číst mimo rozsah oblasti původního videa, což samozřejmě není možné, takže dochází k ořezávání výsledného obrazu, protože nelze nijak smysluplně doplnit chybějící data. Podle článku [8] se nejlepších výsledků s elektronickou stabilizací videa dosáhne ve fázi post-processingu, nikoli použitím real-time systémů v době pořizování záznamu. Patrně prvním komerčním produktem tohoto druhu, který prováděl elektronickou stabilizaci s uváděnou přesností na desetinu pixelu byl v roce 1998 přístroj PVT-200 Director firmy Sarnoff Corporation [5]. V té době bylo revoluční myšlenkou stabilizovat natočený obraz, nikoli samotnou kameru. Články [33] a [32] varují před marketingovým značením některých přístrojů, které nemají s optickou stabilizací obrazu vůbec nic společného. Rozmazání se v těchto přístrojích redukuje nastavením vyšší citlivosti snímače, minimální clonu a kratším časem expozice. Toto je sice běžná fotografická praxe, ale dochází při ní ke snižování kvality obrazu – zhoršuje se kresba a rozlišení detailů, jsou patrné chyby digitálních snímačů a zvyšuje se nežádoucí šum.

13

Obecné rady k používání stabilizátorů a rozdíl výsledků oproti snímání ze stativu rozebírá také článek [31], který se zaměřuje především na využití ve fotografii.

1.6

Stabilizace digitálním filtrem

V současné době se používají systémy pro nelineární střih videa, ve kterých bývají k dispozici také digitální stabilizační filtry. Většinou používají stejné metody, které se používaly již v elektronické stabilizaci, pouze převedené do digitální podoby. Na trhu existuje velké množství produktů pro filmový průmysl. Stránka [24] uvádí velké množství profesionálního softwaru pro zpracování videa. Jako příklady komerčních produktů, které umožňují stabilizaci, můžeme uvést Mokey [25] a SeadyMove [26]. Tyto produkty se prodávají ve velkém množství rozličných licencí s různými cenami. Většinou umožňují také několik jiných funkcí, například klíčování nebo čištění obrazu. Jako zástupce programu zdarma můžeme uvést Deshaker [16], což je plugin pro program VirtualDub [27], který je také zdarma. Přestože je Deshaker nabízen zdarma, nejsou k dispozici zdrojové kódy tohoto filtru. Deshaker je velmi kvalitní software, nezávislými testy (například [15]) je dokonce hodnocen lépe než komerční produkty. Nevýhodou všech stabilizátorů videa, které znám, ať už komerčních nebo volně dostupných, je, že nedovolují uživateli zvolit výsledný pohyb. Tyto stabilizátory určují trajektorii stabilizovaného videa zcela automaticky, nedovolují uživateli navolit jím zamýšlenou dráhu, kterou má video sledovat. Výsledkem této přednastavené automatiky, která za běžných okolností funguje dobře, jsou jisté nechtěné jevy. Jako příklad nežádoucích jevů, které nastávají při automatické stabilizaci, může sloužit „švenkÿ, což je horizontální otáčení kamerou do stran. Při švenku se stabilizátor snaží udržet obraz na jednom místě nepřiměřeně dlouho, a pak následuje jakési „cuknutíÿ obrazu, když se stabilizátor „utrhneÿ

14

od původního bodu, na který se fixoval. Tento efekt by se zajisté dal odstranit, pokud by tvůrce záběru měl možnost určit, který směr pohybu je ve videu žádoucí. Účelem této diplomové práce je vytvořit digitální filtr pro stabilizaci videa, který umožňuje uživateli volně si zvolit trajektorii výsledné stabilizace. Ve zbytku této publikace rozebíráme právě toto téma.

15

Kapitola 2 Digitální stabilizace Tato kapitola rozebírá různé přístupy ke zpracování videa, rozpoznání a sledování pohybu, výběr bodů pro stabilizaci a samotnou stabilizaci obrazu s ohledem na postupy využité v mé diplomové práci. Jedná se tedy o stabilizaci video obrazu digitálním filtrem. Alternativní postupy k tomuto tématu, například optická stabilizace objektivu kamer a fotoaparátů, byly již nastíněny v předchozí kapitole. Digitální video chápeme pro účely této práce jako sekvenci rastrových obrazů nasnímaných v čase. Všechny obrazy v jednom videu mají totožný rozměr a jsou nasnímány po stejně krátkých časových intervalech (jsou tedy uniformně vzorkované v čase). Intenzita jednoho bodu v obrazu se značí ft (i, j) kde i, j jsou souřadnice bodu v obrazu a t vyjadřuje čas počítaný jako celé číslo, které vyjadřuje pořadí snímku ve videu. Pro účely této diplomové práce tedy nebereme v potaz zvuk (přestože většinou bývá nedílnou součástí videa), protože na samotnou stabilizaci obrazu nemá žádný vliv. Dalším důležitým technickým aspektem, který je nutno brát v potaz, je tzv. prokládané video. Tato technologie zvyšuje snímkovou frekvenci videa za cenu snížení rozlišení snímků. Každý snímek videa (anglicky „frameÿ) je rozdělen na dva půlsnímky (anglicky „fieldsÿ), které nesou informaci o 16

celé ploše obrazu, ale jsou od sebe vzdálené v čase. Půlsnímky se do jednoho snímku kombinují tak, že se sloučí liché řádky z prvního půlsnímku se sudými řádkami druhého půlsnímku. Jeden snímek zastaveného videa proto může vypadat „proužkovaněÿ v horizontálním směru, protože se mezi sebou prolínají informace z různých časových vzorků. Stabilizace videa probíhá v několika oddělených krocích, které následují postupně jeden po druhém. Výstup jednoho kroku tvoří počáteční data pro následující krok. Článek [8] uvádí tři fáze elektronické digitální stabilizace: • Motion Estimation • Motion Compensation • Image Composition Ve fázi sledování trajektorie (anglicky „Motion Trackingÿ či „Motion Estimationÿ) se v jednotlivých snímcích videa, které následují v čase po sobě, zjišťuje pohyb v obrazu. Výsledkem sledování navzájem si odpovídajících bodů v jednotlivých snímcích je trajektorie bodu v čase. Změna polohy jednoho bodu mezi dvěma sousedními snímky videa se nazývá „lokální vektor pohybuÿ (anglicky „Local Motion Vectorÿ či „LMVÿ). Ve fázi stabilizace videa (anglicky „Stabilizationÿ či „Motion Compensationÿ) se odstraňuje rušivý třes obrazu. Nejjednodušší metody (např. [8], [10]) předpokládají, že výsledná scéna má být nehybná, proto se všechny snímky videa přizpůsobují pokud možno tak, aby polohou odpovídaly prvnímu snímku videa. Složitější metody používají pro stabilizaci videa například filtraci vysokých frekvencí trajektorie sledovaného bodu, které odpovídají chvění ruky. Tyto filtrace jsou založeny buď na Fourierově transformaci nebo waveletové transformaci. Ve fázi úpravy obrazu (anglicky „Image Compositionÿ) se provádí transformace každého jednotlivého obrazu videa tak, aby odpovídal poloze stabilizovaného obrazu. Některé citované metody používají jen posun obrazu (tzv. translaci), složitější metody berou v potaz i rotaci okolo optické osy (tedy okolo osy pohledu kamery). 17

Většina algoritmů předpokládá projektivní transformaci při snímání obrazu, takže se úpravy obrazu omezují na translaci, rotaci a případně i změnu měřítka, pokud algoritmus zvládá zoom. Při těchto operacích však dochází k výraznému posunutí obrazu, takže původní okraje obrazu již nejsou totožné s okraji obrazu po transformaci. Například pohne-li se kamera prudce doprava, začne obraz ujíždět vlevo. Stabilizátor vzniklou situaci koriguje tím, že obraz posouvá doprava, tam, kde bylo jeho původní místo. Tím vzniká na levé straně obrazu prostor, který nebyl v záběru, ale po korekci má být vidět v obrazu. Některé algoritmy se snaží doplňovat chybějící místa na krajích obrazu, která se dočasně dostala mimo zorné pole. Většinou doplňují data z předcházejících snímků, čímž mohou vzniknout systematické chyby. Jako příklad, který může způsobovat chyby tohoto systému, může sloužit kráčející osoba – pokud se její nohy dostanou na spodní hraně obrazu mimo záběr a stabilizátor se snaží tuto chybějící oblast doplnit obrazem nohou z předchozích snímků, jsou nohy již v jiné poloze a může se stát, že ve výsledném snímku se neobjeví vcelku. Článek [15] upozorňuje na další možnou chybu při stabilizaci obrazu: dokud se video chvěje, je každý jednotlivý snímek videa tímto pohybem mírně rozostřen. Takové rozostření pozorovatele subjektivně neruší, protože je rozostřen pohybující se objekt. Po stabilizaci videa je sledovaný objekt již v klidu, ale rozostření stále zůstává, takže je viditelné a pozorovatele může subjektivně více rušit. V tomto ohledu si zaslouží pozornost zvláště algoritmus [7], který doplňuje rozostřená místa videa a navíc řeší zakrývání okrajů obrazu velmi propracovaným způsobem. Podrobnější popis metody nazvané „image mosaicÿ je možné najít v kapitole 5.2 na stránce 68 této práce. Filter Deshaker [16], který jsem při hledání materiálů intenzivně studoval, řeší zakrývané okraje obrazu velmi jednoduchým způsobem – výsledný obraz mírně zvětší (jakoby šlo o zoom) tak, aby mizející okraje nezasahovaly do výsledného obrazu.

18

Nevýhodou všech metod a systémů, které znám, je, že neumožňují zvolit trajektorii přesně dle přání uživatele. Tato práce je zaměřena na možnost editování výsledné trajektorie sledovaného bodu podle navolené trajektorie. Hlavní náplní mé práce bylo vytvořit počítačový program, který by uživateli umožnil zadávat trajektorii pro stabilizaci obrazu videa. Operace se samotným obrazem byly podružné. Můj program tedy používá pro opravu obrazu pouze operace rotace a translace. Neřešil jsem rozostření obrazu při pohybu, ani chybějící místa na krajích obrazu. Odstranění chybějících okrajů je již na uživateli – může v nějakém dalším nástroji použít funkci zoom, čímž dosáhne stejného efektu jako u filtru Deshaker, anebo může velikost výsledného obrazu oříznout podle potřeby.

2.1

Zpracování obrazu

Jak již bylo uvedeno, zpracovávané video je možné chápat jako posloupnost obrazů, kde každý obraz je obdélníková matice bodů, které nesou barevnou informaci. Obor nazývaný zpracování obrazu, který se touto problematikou zabývá [4], řeší z praktického hlediska tři hlavní typy úloh, které se týkají analýzy pohybu v obrazu: • Detekce pohybu • Nalezení umístění a sledování trajektorie pohybujících se objektů • Určení prostorových vlastností objektů Smysl úlohy detekce pohybu odpovídá optickému hlídači, který upozorní na jakýkoli detekovaný pohyb. Příkladem praktického využití může být ostraha prodejen, skladišť a průmyslových objektů. Tato skupina úloh pracuje s neměnnou polohou snímací kamery. Cílem úlohy nalezení pohybujících se objektů je získání informací o pohybu v prostoru a čase. Získávání trojrozměrných údajů o objektech je nad rámec této práce, více informací je možné získat například z publikací [4] nebo [3]. 19

Pro téma této diplomové práce je z uvedených možností samozřejmě nejdůležitější sledování trajektorie vybraného objektu. I pro toto zadání existuje několik odlišných přístupů. Většinou se používají postupy srovnávání obrazových dat – po nalezení významných bodů pohybujících se objektů se hledají jejich vzájemné korespondence s objekty v dalších snímcích videa. Tyto metody se používají například při vzdáleném pozorování Země pro sledování pohybu a vývoje oblačnosti z posloupnosti družicových meteorologických snímků, pro analýzu dopravních situací v městském provozu i mnoho vojenských aplikací. Protože se tato metoda zaměřuje na detaily obrazu, nazývá se anglicky „feature-basedÿ. Implementačně složitější alternativní metoda je založena na grafové reprezentaci objektů v každém obraze a na postupech srovnávání grafů. Dalším, principiálně odlišným přístupem je analýza pohybu na základě výpočtu optického toku, jehož výsledkem je určení směru a rychlosti pohybu v každém místě obrazu. Na základě výpočtu optického toku lze určovat další parametry pohybu. Tato metoda zpracovává obraz jako celek, proto se anglicky nazývá „area-basedÿ a je také výpočetně mnohem náročnější. Kompromisem mezi metodami srovnávání a výpočtem optického toku je určení rychlostního pole, což je obdoba optického toku pro posloupnosti obrazů. Nejznámější metodou je „Block Matching Algorithmÿ („BMAÿ), při které je obraz rozdělen na obdélníky. V každém z nich se hledá korespondence v následujícím obrazu videa. Významné je také hledisko, zda je prováděná analýza pohybu závislá anebo nezávislá na poloze pohybujících se objektů. Příkladem nezávislé analýzy je využívání optického toku, příkladem objektově závislé analýzy je tvorba rychlostního pole, nebo rozdílové metody. Při závislé analýze se většinou nejprve hledají významná místa obrazu, jako například hrany [14], další zpracování obvykle hledá souhlas mezi takto nalezenými oblastmi či body obrazu.

20

2.2

Rozdílové metody

Jednoduchou detekci pohybu umožňuje zjišťování rozdílů mezi obrazy snímanými v různých časových okamžicích stacionární kamerou v konstantním osvětlení. Kniha [4] zavádí pojem „rozdílový obrazÿ pro takový binární obraz, kde nulové hodnoty představují sobě odpovídající místa obrazů f1 a f2 , v nichž nedošlo k významné změně jasových úrovní mezi okamžiky snímání obou obrazů:   0 pro |f (i, j) − f (i, j)| < e 1 2 d1,2 (i, j) =  1 jinak

kde e je předem určené kladné číslo. Je zřejmé, že pohyb objektu jasově odlišného od nepohybujícího se pozadí bude tímto postupem detekován. Prvek rozdílového obrazu d1,2 (i, j) na pozici (i, j) statické kamery nabývá hodnoty 1 pro jednu z následujících příčin: • jeden bod byl elementem pohybujícího se objektu, druhý elementem pozadí • oba body f1 (i, j) i f2 (i, j) byly elementy různých pohybujících se objektů • oba obrazové elementy byly elementy téhož pohybujícího se objektu v místech různého jasu • vlivem přítomnosti šumu a různých nepřesností snímání kamerou se objeví nesprávně detekovaný bod Metoda rozdílového obrazu vlastně stanovuje kritéria, kdy ve kterém místě obrazu dochází k pohybu. Úkolem metody stabilizace obrazu je potlačit míru takto detekovaného pohybu. Ovšem je třeba vzít v potaz, že ne každý pohyb v obraze je nežádoucí. Tento fakt musí být brán v potaz zejména při analýze pohybu a rozhodnutí, které body obrazu je nutné stabilizovat a 21

které se mohou pohybovat. Většina metod stabilizace zachází s těmito body zcela automaticky, což se může v některých případech ukázat jako nevýhoda, pokud má uživatel jiné představy o výsledném videu. Tato práce předchází problémům tím, že umožňuje uživateli rozhodnout o vhodných místech pro sledování obrazu i o konečné opravě obrazu. Z rozdílového obrazu je pohyb úspěšně detekován, nelze však rozhodnout o směru pohybu objektů. Tento nedostatek odstraňuje užívání akumulativního rozdílového obrazu. Obraz f1 se určí jako referenční. dakum (i, j) =

n X

ak |f1 (i, j) − fk (i, j)|

k=1

kde ak značí váhové koeficienty označující významnost jednotlivých obrazů v čase a n je počet obrazů posloupnosti. Směr monotónního nárůstu hodnot v akumulativním rozdílovém obrazu vypovídá o směru pohybu. Principielně odlišný přístup navrhuje publikace [11], kde je navrženo korelování obrazů po Fourierově transformaci. Výhodou tohoto zlepšení je, že ihned po korelaci je zřejmý směr pohybu objektů ve scéně. Vychází totiž z vlastnosti Fourierovy transformace, při které se posun v souřadném systému obrazů projeví lineární změnou fáze ve Fourierově obrazu. Uvedenou metodu ovšem nebylo možné využít pro účely této diplomové práce, protože sice velmi efektivně určí směr pohybu, avšak není možné podle ní určit polohu objektu v obraze. Při realizaci diplomové práce byla použita mírně modifikovaná varianta rozdílové metody – jedná se o hledání motion vektorů. Tato technologie však nebyla primárně vyvinuta za účelem sledování pohybu ve videu, ale pro kompresi videa. Tento „Local Motion Vectorÿ určuje pouze které místo snímku se podobá nějakému místu předchozího snímku. Proto je při použití této technologie velmi důležité zvolit správný výchozí bod, aby motion vektor odpovídal pohybu v obrazu. Propojením technologie motion vektorů s vhodným výběrem sledovaného bodu, se z ní stává mocný nástroj pro sledování pohybu a stabilizaci obrazu.

22

2.3

Detekce významných bodů

Většina metod založená na srovnávání korespondence významných bodů mezi po sobě následujícími obrazy určuje tuto korespondenci za účelem vytvoření obrazu rychlostního pole. Nejprve je však nutné určit ony významné body. Většina metod preferuje nalezení hran a rohů autokorelační funkcí. Kniha [4] navrhuje jako nejjednodušší metodu Moravcův operátor: f (i, j) =

j+1 i+1 X 1 X |g(k, e) − g(i, j)| 8 k=i−1 e=j−1

Tyto automaticky vybrané body jsou sice optimální z technického hlediska, nemusí však vždy být nejlepší volbou z pohledu uživatele. Pokud má uživatel možnost editovat trajektorii videa, měl by mít také možnost výběru, kterými body bude pohybovat. Tyto body velmi záleží na druhu scény, kterou si uživatel přeje stabilizovat. Pokud scéna obsahuje některé statické prvky a některé pohybující se prvky, u nichž ale na pohybu nezáleží, může si uživatel vybrat ty body, na které klade důraz. Jako příklad můžeme uvést exteriér, ve kterém je zachycena statická skála, podle níž bude uživatel pravděpodobně určovat stabilizaci, a v pozdí se objevují stromy pohybované větrem, na jejichž pohybu uživateli nezáleží. Software, který je předmětem této diplomové práce, tedy neurčuje výchozí body pro sledování trajektorie ani průběh výsledné stabilizace – jejich volba záleží na vůli uživatele. Pokud použijeme příklad se skálou a pohybujícími se stromy, pak výběrem skály jako bodu pro sledování trajektorie pohybu určí uživatel, na kterém bodu bude probíhat stabilizace, ostatní body se budou při sledování trajektorie ignorovat, při stabilizaci se s nimi bude provádět shodná transformace jako se stabilizovanými body skály. Existují však jistá doporučení, která by měl uživatel při volbě bodu pro sledování trajektorie brát na zřetel, aby výpočet pracoval správně. Jejich přehledné shrnutí je v následující kapitole. 23

2.4

Shrnutí algoritmů

Metody založené na sledování detailů (anglicky „feature basedÿ) mají oproti celoobrazovým metodám (anglicky „area basedÿ) několik výhod: jsou rychlejší a především rozpoznají větší množství obrazových transformací. Nevýhodou je, že se ztrácí na obrazu bez jasné struktury a bez detailů. Pro implementaci diplomové práce jsem vybral metodu sledování detailů s lokálními motion vektory, protože věřím, že uživatel dokáže vhodně zvolit jasně strukturovaný bod, který je možné ve videu sledovat, čímž se zmíněné problémy odstraní. Publikace [6] uvádí na straně 7 riziková kritéria obrazu, na kterých tato implementovaná metoda selhává: periodické struktury s nepravidelným pohybem v obrazu. Jako příklad nevhodně zvoleného bodu pro stabilizaci můžeme uvést hrací pole šachovnice, protože se velmi podobá ostatním hracím polím na šachovnici. Článek [14] podrobně shrnuje slabá místa, na kterých selhává zvolená metoda: • Existují pohybující se objekty • Vyskytují se opakující se vzory • Existuje velmi málo hran • Nízký odstup signál-šum • Mění se jas nebo intenzita (např. blesk fotoaparátu) • Skutečný rozsah pohybu je větší než předpokládaný • Obraz hran je rozostřen pohybem • Pohyby se neskládají jen z posunů, ale i rotací • Rovina kamery není kolmá na snímanou plochu • Pracuje se s optickým zoomem 24

Může se zdát, že slabých míst je poměrně dost, přesto pro většinu běžných úloh bude fungovat spolehlivě. Uživatel má totiž možnost zvolit v různých časových okamžicích různé body pro sledování, čímž může eliminovat chybu ve sledování bodu, pokud již dříve vybraný bod není vhodným kandidátem pro sledování. Navíc chybně vysledované body je možné ručně opravit editací stabilizační křivky.

25

Kapitola 3 Implementační rozhodnutí Podstatnou součástí této diplomové práce je implementace digitálního filtru pro stabilizaci obrazu videa. Tato kapitola probírá implementační rozhodnutí a různé technické aspekty vytvořeného filtru. Pro splnění úkolu naimplementovat filtr pro stabilizaci videa bylo nutné využít znalosti z různorodých oblastí: geometrie (pro výpočet hodnot a průběhu spline křivek), zpracování obrazu (pro hledání trajektorie sledovaného bodu ve videu), zpracování signálu (pro filtraci roztřesené trajektorie), počítačové grafiky (pro transformace obrazu) a samozřejmě také softwarového inženýrství. Implementaci předcházelo studium dostupných pramenů a zdrojů a také zkoumání již existujících metod.

3.1

Existující software

Za největší zdroj inspirace pro stabilizaci videa posloužil software Deshaker [16], který můžeme považovat za referenční implementaci stabilizačního filtru, neboť je pravděpodobně jeden z nejlepších ve svém oboru, viz například článek [15]. Navíc je Deshaker k dispozici zdarma, ale velkou nevýhodou je, že se nedodává společně se zdrojovými kódy. Začneme popisem Deshakeru jako odrazového můstku, od kterého přejdeme k rozhodnutím uplatněným v implementaci vlastního softwaru. Filtr

26

Obrázek 3.1: Ukázka rozhraní programu Deshaker

Deshaker je plugin pro program VirtualDub se vším, co k tomu patří – je tedy velmi efektivní, spolehlivý, ale jeho ovládání není příliš intuitivní. Celé jeho uživatelské rozhraní zahrnuje jedno komplexní dialogové okno pro oba průchody. Filtr pracuje dvouprůchodově. V prvním průchodu videem sleduje Deshaker pohyb v celém obrazu metodou „Block Matching Algorithmÿ, která byla zevrubně popsána již dříve. Znamená to tedy, že se nesleduje jeden určitý objekt, ale scéna jako celek. K možným nastavením patří velikost makrobloku, velikost zkoumané oblasti a další technická nastavení. Ve druhém průchodu dochází již ke korekci videa. Uživatel má možnost zvolit parametry, které ovlivní výpočet upravovaného snímku, například může nastavit metodu pro převzorkování obrazu, maximální hodnoty korekčních transformací, jako je například translace a zoomu a dalších parametrů. V průběhu přípravy této diplomové práce byly zkoumány i jiné digitální stabilizační filtry, jako například Mokey [25] a Steadymove [26], ale jejich vysoká pořizovací cena nedovolila jejich přímé ozkoušení. Bylo tedy zapotřebí

27

spokojit se jen s dostupnými ukázkami jejich výstupů, které byly k dispozici na webových stránkách jako reklamní upoutávky. Další dostupné filtry [24] však neposkytovaly srovnatelně uspokojivé výsledky, takže nebyly zahrnuty do porovnání s dříve uvedenými filtry. Na CD přiloženém k této diplomové práci jsou pro srovnání uloženy ukázky výstupů některých filtrů. Žádný z nalezených filtrů však nedisponoval možností přímo editovat stabilizaci videa. Deshaker, stejně jako ostatní stabilizační filtry, neumožňuje přímo ovlivnit trajektorii výsledného obrazu videa, nepotřebuje tedy dodatečné grafické rozhraní pro interakci s uživatelem. Na rozdíl od tohoto přístupu se implementovaná aplikace přímo zaměřuje na editaci křivek trajektorie výsledného stabilizovaného obrazu. Tato změna v konceptu vedla k zásadnímu implementačnímu rozhodnutí, které je popsané v následující kapitole.

3.2

Rozdělení aplikace

Filtr Antishake, který jsem implementoval, jsem koncipoval dvouprůchodově podobně jako filtr Deshaker, avšak rozhodl jsem se každý z průchodů umístit do samostatné aplikace. Původním záměrem bylo celý filtr implementovat jako plugin pro Virtualdub, ovšem technická omezení, která stála v cestě, vedla k rozhodnutí rozdělit aplikaci do dvou samostatných částí a ve Virtualdubu implementovat pouze export videa. Ostatní operace, jako načítání videa, stabilizační filtraci a manipulaci křivkami uživatelem jsem zpracoval v samostatném programu. V následujícím textu diskutujeme rozhodnutí rozdělit implementovaný software do dvou aplikací. V prvním průchodu, kdy uživatel vybírá body pro sledování a upravuje trajektorii pro stabilizaci, je velmi důležité pohodlí uživatele, přehlednost aplikace a možnost volného pohybu po časové ose videa. Proto jsem se rozhodl vytvořit tuto část ve formě samostatné aplikace. Z technického hlediska je zapotřebí zvládnout zejména import videa, grafické zobrazení a reakci na zadání uživatele. Druhý průchod je principielně zaměřen na dávkové zpracování, protože

28

pro transformaci videa a export do AVI není nutný žádný zásah uživatele. Samotný export videa je však implementačně velmi náročný, především výběr výstupního kodeku a nastavení jeho parametrů. Proto jsem se rozhodl tuto část implementovat ve formě pluginu pro program VirtualDub. V tomto programu je export videa již vyřešen, plugin má za úkol pouze zpracovávat snímky videa, které poskytuje VirtualDub. Toto rozhodnutí výrazně zjednodušilo implementaci poslední fáze celého procesu. Princip fungování běžného filtru na základě pluginu v hostitelské aplikaci funguje následujícím způsobem. Program Virtualdub se stará o veškeré načítání videa, jeho zpracování i pohyb po časové ose. Pokud se do procesu zpracování videa ve Virtualdubu zapojí nějaký filtr, získává pouze informace o každém zpracovávaném snímku videa. Filtr nemá k dispozici prvky uživatelského rozhraní, nemůže si vyžádat libovolný snímek videa, pokud jej potřebuje, a pokud požaduje vstupy od uživatele, je možné je získat jen z konfiguračního dialogu filtru, který si uživatel může zobrazit. Možnosti manipulace s filtrem ve Virtualdubu jsou tedy z uživatelského hlediska velmi úzké. Filtry pro Virtualdub se proto většinou omezují na manipulaci s obrazem, jako je například změna velikosti obrazu, úprava jasu a barevnosti, čištění obrazu, různé grafické efekty a další. Takové prostředí tedy není vhodné k účelu, který byl popsán dříve, tedy pro bohaté uživatelské rozhraní se širokými možnostmi manipulovat videem. Proto padlo rozhodnutí naimplementovat uživatelské rozhraní jako samostatnou aplikaci v prostředí .Net v jazyku C#. Důvody, které vedly k rozhodnutí rozdělit manipulaci s videem do dvou programů, byly jednak uživatelský komfort v samostatné aplikaci, jednak implementační nároky na přístup k nízkoúrovňovému API pro zpracování při exportu videa videa. V dalších kapitolách je popsána implementace obou těchto součástí. Rozdělení aplikace na dvě samostatné části sebou přináší ještě také jednu důležitou výhodu. Jak již bylo zmíněno na straně 7, není vhodné videoklip zpracovávat samostatně, bez návaznosti na ostatní zpracování videa. Autor

29

videa proto může požadovat, aby ke stabilizaci došlo v jím zvolené aplikaci pro zpracování videa, například v softwaru pro nelineární střih Avid. Za tímto účelem je možné pro daný program vytvořit nový plugin, který bude mít na starosti stabilizaci obrazu v rámci daného programu. Kdyby k rozdělení aplikace na dvě části nedošlo, bylo by velmi obtížné, téměř nemožné portovat celou aplikaci jako plugin do jiného softwaru, čehož jsme byli svědky již v případě Virtualdubu. Naproti tomu, implementovat jako plugin pouhou transformaci obrazu je řádově snazší zadání.

3.3

Křivky trajektorií

Implementovaný program využívá pro manipulaci se stabilizovaným obrazem křivky trajektorií. Tato část textu vysvětluje, jakým způsobem se tvoří a jak se s nimi poté manipuluje. Jistá část obrazu by měla být bez pohybu, tedy celá statická – jedná se o pozadí natáčené scény, nepohyblivé okolí pohybujícího se předmětu. Pokud byla kamera při natáčení v pohybu, například sledovala-li pohybující se předmět, pak je v pohybu i ono původně statické pozadí. Zakreslíme-li pozice sledovaného statického pozadí do grafu s kartézskými souřadnicemi, výsledkem bude křivka představující trajektorii pohybu kamery. Tato křivka má obecný tvar, většinou se však blíží úsečce, oblouku nebo jinému podobnému geometrickému objektu. Vlivem chvění je křivka nerovná, toto chvění se projevuje jako drobná kostrbatost křivky. Tvůrce filmu, který si přeje chvění odstranit, tak chce vlastně převést jeden tvar křivky trajektorie na jiný tvar křivky, ve kterém se již chvění neprojevuje. Rozdíl mezi vstupní křivkou a křivkou bez chvění tedy bude představovat jen zbylý šum způsobený třesem ruky anebo klepáním podstavce kamery. V implementovaném programu tedy uživatel vidí dvě křivky. První křivka představuje hodnoty naměřené algoritmem pro sledování pohybu a je roztřesená. Druhá křivka je hladká a uživatel může upravovat její tvar podle

30

svých vlastních představ. Převedením obrazových dat ze souřadnic ležících na roztřesené křivce do polohy určené hladkou křivkou dochází vlastně ke stabilizaci. Existující programy odstraňují šum automatickými metodami filtrování vstupního signálu, například použitím filtrů s konečnou odezvou zapojených jako nízkopásmová propusť. Běžné programy tedy křivku trajektorie nepovažují za objekt, který je dále možné ručně editovat podle přání autora videa. Pokud by se křivka dala editovat a tvarovat, jako je to možné ve vektorových programech, například ve 3D Studiu, umožnila by se úprava křivky trajektorie tak, jak požaduje autor videa, čímž by se zabránilo nechtěným efektům a umožnilo by to vznik zcela novým efektům. Jako křivky pro editování trajektorie se přímo nabízejí kubické interpolační křivky, které jsou běžné ve vektorových editačních programech. Rozhodnutí, popisující výběr konkrétního typu křivky a manipulaci s ním následují v pozdější kapitole.

3.4

Interpolační křivky Spline

Účelem implementovaného digitálního filtru je poskytnout uživateli možnost editování výsledné stabilizační křivky, proto nejprve prozkoumáme existující metody pro editaci křivek. Neboť neexistují jiné obdobné programy pro stabilizaci obrazu videa, které by využívaly křivky editovatelné uživatelem, je nutné porozhlédnout se v jiné příbuzné oblasti počítačové grafiky a to jak v plošné vektorové grafice (softwarové nástroje například InDesign, Inkscape a mnoho dalších), tak ve 3D animaci (například programy 3D Studio, Maya, Blender a další). Tyto grafické programy využívají pro reprezentaci křivek různé geometrické nástroje, nejčastěji založené na polynomiálních křivkách, jako jsou různé varianty křivek spline, například Bézierovy křivky, B-spline, TCB-spline, NURBS a další. Trajektorie výsledného stabilizovaného videa musí být spojitá a hladká křivka. Pro taková zadání jsou nejvhodnější některé z geometrických křivek

31

spline, stejně jako to dělají jiné grafické programy. Další důležitým kritériem pro výběr ze široké třídy splinů je možnost snadné manipulace s křivkou. Například B-spline nebo přirozený spline sice poskytuje velmi dobré tvary, uživatel však nemá možnost přímo ovlivnit tečné vektory ve zvolených bodech. Dalším kritériem je rozhodnutí, zda používat aproximační křivky (to jsou takové křivky, které neprocházejí zvolenými body, jen se svým tvarem těmto bodům přibližují) anebo interpolační křivky (to jsou křivky, jež přímo prokládají zadané body). Toto rozhodnutí není možné učinit pouze ze zadání a požadavků kladených na výsledek, neboť obě třídy křivek jsou svými geometrickými vlastnostmi stejně vhodné pro určenou úlohu. Rozhodujícím faktorem pro výběr konkrétního typu křivek tedy byla možnost a snadnost ruční manipulace uživatelem. Shrneme implementační požadavky na vlastnosti křivky, kterou požadujeme do implementované aplikace: • Geometricky hladká křivka (alespoň C1 ) • Lokální změna řídících bodů má lokální efekt • Nízká výpočetní náročnost • Intuitivní ovládání uživatelem Další požadavek kladený na interpolační křivku je Cm spojitost, přičemž m je stupeň derivace, do kterého je spojitost zachována. Například C2 spojitost zachovává spojitou nultou, první a druhou derivaci v každém bodu interpolační křivky. Volba interpolační funkce může silně ovlivnit výslednou křivku. Problém interpolace je možné formulovat následujícím způsobem: Je dáno N + 1 bodů Pi , kde i = 0..N . Najděte křivku Q(t) procházející těmito body. Toto zadání je možné matematicky řešit polynomiální cestou – najít polynom Q(t) stupně N , který prochází všemi body Pi – avšak takové řešení, 32

Křivka

Lokální Spojitost

Typ

Hermitova

Ano

C1

Interpolační

Bézierova

Ano

C1

Interpolační

Catmull-Rom

Ano

C1

Interpolační

Přirozený spline

Ne

C2

Interpolační

Coonsova

Ano

C1

Aproximační

Obrázek 3.2: Porovnání vlastností několika typů spline funkcí

přestože je matematicky správné, neposkytuje uspokojivé výsledky z hlediska geometrických požadavků na křivku v implementované aplikaci (viz výše). Křivka je sice hladká a má nízké nároky na výpočet, ale pro vyšší stupně N křivka osciluje, změna kteréhokoli bodu má globální efekt a proto není její ovládání intuitivní. Existuje ještě další množina interpolačních křivek, které splňují jak základní požadavky na interpolaci a blíží se svou hladkostí k polynomiální interpolaci, tak je i ovládání snadno pochopitelné pro uživatele. Tyto interpolační křivky, zachovávající spojitost do určitého řádu, se začaly ve větší míře používat v počítačové grafice pro návrhy designu karoserií automobilů. Obecně se tyto křivky nazývají spline a lze je určit několika způsoby. Nejznámější jsou takzvané Beziérovy křivky, Hermitova křivka, přirozený spline a další. Původním záměrem bylo použít Coonsovy aproximační křivky pro zadávání editovatelné trajektorie videa. Protože tyto křivky samy o sobě aproximují trajektorii namísto pouhé interpolace, čímž by se také dosáhlo dodatečného „vyhlazeníÿ a stabilizace křivky. Praktické pokusy s tímto typem křivek ovšem ukázaly tuto volbu jako nevyhovující hned ze dvou důvodů. Prvním důvodem byla snadnost ovládání – editace křivky totiž není příliš intuitivní. Není totiž na pohled příliš zřejmé, který bod a jakým způsobem ovládat pro dosažení určitého požadovaného výsledku. Další důvodem bylo technické omezení – je totiž nutné používat mnohem větší grafické plátno pro

33

Obrázek 3.3: Porovnání vzdálenosti řídících bodů Coonsovy křivky (vlevo) v porovnání s řídícími body Bézierovy křivky (vpravo)

uživatelský vstup, než je zobrazované video. Poměr mezi rozsahem zadávaných bodů a skutečnou velikostí křivky znázorňuje obrázek 3.3. Bylo proto nutné vybrat jinou křivku, která by byla vhodná pro editování. Z kubických spline funkcí je patrně nejvhodnější Bézierova křivka, populární z vektorových grafických editorů jako je například Adobe InDesign. Poskytuje dobré ovládací možnosti pro úpravu tvaru křivek, které jsou navíc srozumitelné i naprostému začátečníkovi. Bézierova kubická křivka je podobná Hermitově křivce, ale definice jejích tečných vektorů je mnohem intuitivnější. Jedná se o interpolační křivku s řídícími body, které mění výsledný tvar jen lokálně. Má čtyři řídící body, z nichž dva jsou uzly ležící na křivce. V dalším textu je podrobně rozebrána problematika interpolace.

3.5

Sledování trajektorie

Pro sledování trajektorie metodou hledání motion vektorů byla zvolena metoda z knihy [3], která poskytuje relativně snadno ověřitelné výsledky. Na obrázku 3.4 je znázorněn princip hledání motion vektoru ve dvou po sobě jdoucích snímcích. Kolem zvoleného bodu v prvním snímku je vytvořen makroblok o určité velikosti – v implementaci se jedná o bitmapu, která je vzorkem ze zkoumaného snímku. Ve druhém snímku se prohledává oblast

34

Obrázek 3.4: Princip hledání motion vektoru

35

z určitého okolí původního makrobloku a nejlepší nalezená podobnost je pak prohlášena za shodu. Rozdíl souřadnic staré a nové polohy makrobloku je pak tzv. „motion vektorÿ. Několik po sobě následujících motion vektorů tvoří trajektorii sledovaného objektu. Nyní bude algoritmus hledání motion vektoru popsán podrobněji. Porovnávání dvou makrobloků, ze kterých může vzniknout motion vektor, se provádí sumací rozdílů, což je chyba v jejich shodě. Chyba shody makrobloku na pozici (x, y) v prvním snímku It s makroblokem na pozici (x + u, y + v) v druhém snímku It+1 se nazývá „sum of square differenceÿ („SSDÿ) a vypočítává se následujícím předpisem: SSDt,(x,y) (u, v) =

M X

M X

(It (x + i, y + j) − It+1 (x + u + i, y + v + j))2

j=−M i=−M

kde (x, y) jsou původní souřadnice zdrojového bodu a (u, v) jsou souřadnice právě zkoumaného posunutí (jedná se o kandidáty na motion vektor). M je polovina velikosti makrobloku – jedná se vlastně o čtvercové okolí bodu, který pro stabilizaci vybral uživatel. Jako výběr nejlepší aproximace motion vektoru se vybírá souřadnice, která dosáhla minima rozdílu z prohledávání metodou SSD všech možných kandidátských bodů: s~t = arg min SSDt,(x,y) (u, v) (u,v)∈S

kde S je prohledávané okolí v určitém rozsahu původního makrobloku o velikosti −p ≤ u, v ≤ p (kde M je přirozené číslo) a zároveň každý takový bod je platným prvkem obrazu (tedy jeho prohledávané okolí neleží mimo hranice obrazu). Algoritmus, který vyhledává motion vector hrubou silou, přímou implementací výše popsaných vzorečků, se nazývá „Full-Search Block Matching Algorithmÿ, protože prohledává všechny možné body, které jsou kandidáty na motion vector. Takové algoritmy jsou výpočetně velmi náročné. Kategorie algoritmů optimalizovaných na rychlost výpočtu se nazývá „Fast Block Matching Algorithmÿ, existuje jich celá řada a většinou jsou zaměřené na 36

kompresi videa MPEG nebo jinou podobnou technologii, ovšem je možné některé z těchto metod využívat i pro motion tracking. Optimalizační algoritmy je možné podle dokumentu [36] rozdělit na tři kategorie podle toho, na kterou oblast se zaměřují s optimalizací. Techniky v první kategorii šetří výpočetní cykly redukováním počtu prohledávaných pozic (v tomto dokumentu prohledávanou množinu označujeme S). Naproti tomu se techniky v druhé kategorii snaží šetřit náklady na výpočetní složitost jednodušším postupem pro výpočet chyby ve shodě každých dvou obrazců. Tyto dvě kategorie je možné kombinovat, takže vznikne třída hybridních algoritmů, které se zaměřují na obě problematické oblasti. Porovnání mnoha algoritmů pro Fast Block Matching Algorithm je možné nalézt například v dokumentu [36]. V této práci nebyly z důvodu vysoké implementační náročnosti použity sofistikované algoritmy, původně určené pro kompresi videa. Urychlení algoritmu pro vyhledávání trajektorie objektů se dosahuje dvouprůchodovým algoritmem, metoda se řadí do první kategorie optimalizačních algoritmů, čili zaměřuje se na redukování počtu prohledávaných pozic a porovnává se jen několik málo bodů z celkové množiny S. Následuje popis principu použitého algoritmu pro Fast Block Matching Algorithm. Při prvním průchodu obrazem se vynechává konstantní počet prohledávaných pozic v horizontálním i vertikálním směru, čímž se shoda nalezne pouze přibližně. Nalezený bod tedy tvoří kandidáta na další prozkoumání. Při druhém průchodu se pak porovnává každá pozice pixelu, ale pouze v malém okolí kandidátského bodu, který byl nalezen při prvním průchodu, takže dojde ke zpřesnění prohledávání z prvního průchodu. V implementaci je tedy cyklus v cyklu, který prohledává daný čtverec kandidátských bodů tím, že se vybírají diskrétní body uspořádané do čtverce. Pro přeskakování prohledávaných pozic byla zvolena konstanta 7 v neprokládaném videu a konstanta 8 v prokládaném videu (aby byla zachována pozice ve zvoleném půlsnímku prohledávaného snímku). Tato hodnota je dostatečná pro srovnání detailů v běžném videu při prvním průchodu prohledáváním a

37

přitom dojde k vysokému urychlení výpočtu (přibližně padesátinásobnému). Druhý průchod již prohledává okolí nalezeného bodu pixel po pixelu ve čtvercovém okolí metodou cyklus v cyklu.

3.6

Super-resolution

Pro zvýšení přesnosti vyhledávání bodu je použita metoda super-resolution, což je metoda pracující s přesností jemnější než je jeden pixel. Konkrétně byla v této implementaci použita metoda mikroposuvů pixelů s bilineárním převzorkováním. Stejná metoda byla v této práci použita pro transformaci stabilizovaného obrazu translací a rotací. Tato metoda je podrobněji popsána v algoritmické části v kapitole 4.6 na straně 55. Měření bodu s jemnější přesností se provádí až po dvou průchodech vyhledání nejlepšího kandidátského bodu. Poté je vyšší přesnosti dosaženo posouváním porovnávaného vzoru obrazu po krocích o hodnotě čtvrtiny pixelu jak v horizontálním tak vertikálním směru. Ke srovnávání dochází prohledáváním metodou SSD popsanou výše. Nejlepší shoda porovnání je prohlášena za mikro-souřadnici nalezeného bodu, čímž je nalezena souřadnice kandidátského bodu s přesností na čtvrtinu pixelu.

3.7

Dva sledované body

V předchozích kapitolách byl popsán motion tracking jednoho bodu. Implementovaný filtr používá pro sledování polohy a rotace metodu sledování dvou bodů. Aplikace umožňuje uživateli stabilizovat polohu i rotaci obrazu, čehož není možné dosáhnout trackingem jednoho bodu. Pro motion tracking je tedy v aplikaci nutné zadat dva body pro sledování, aby bylo možné stabilizovat oba parametry současně. Jeden bod je sledován pouze s ohledem na jeho polohu, druhý bod je považován za vektor vedoucí z prvního bodu a je sledován úhel tohoto vektoru v kartézském souřadnicovém systému. S parametry polohy i rotace se zachází 38

naprosto shodně, provádí se s nimi shodná operace stabilizace a jsou později převedeny na křivky, což je popsáno v následující kapitole.

3.8

Stabilizace

Digitální filtry je možné dělit podle způsobu práce na konvoluční (nazývané také jako „filtry s konečnou impulzní odezvouÿ, FIR) a na rekurzivní (nazývané také jako „filtry s nekonečnou impulzní odezvouÿ, IIR). Filtry FIR jsou vždy stabilní. Při implementaci bylo učiněno několik praktických experimentů s filtry optimálními podle různých kritérií z knihy [1], ale nakonec se jako postačující ukázal čtyřiceti tapový filtr FIR s konstantní hodnotou všech tapů. Přenos kauzálního filtru je dán vztahem: H(z) = b0 + b1 z −1 + · · · + bN z n−N =

N X

bn z −n

n=0

Příslušná diferenční rovnice má tvar: y[n] = b0 x[n] + b1 x[n − 1] + · · · + bN x[n − N ] =

N X

bi x[n − i]

i=0

Kde x[n] je vstupní signál, y[n] je výstupní signál, bi jsou koeficienty filtru a N je řád filtru (udává počat tapů filtru). Pokud je

PN

i=0 bi

= 1, pak

je zachována hladina energie signálu. Z těchto předpokladů byl vybrán FIR se čtyřiceti koeficienty o shodných hodnotách bi =

1 . 40

Protože je výstupní signál kratší než vstupní, bylo nutné

doplnit některé hodnoty, takže byl vstupní signál uměle prodloužen nakopírováním hodnot prvního a posledního vzorku signálu. Tím vznikla první fáze stabilizace. Ke druhé fázi stabilizace dochází převedením filtrovaných hodnot na křivky Catmull-Rom spline, což je varianta Bézierových křivek, ve kterých jsou uzlové body dány, a ostatní řídící body se dopočítají z uzlových bodů.

39

Obrázek 3.5: Princip slučování oblastí v jeden celek

3.9

Spojování oblastí

Ve videu jsou tedy ve fázi stabilizace dvě trajektorie: jedna křivka, která vznikla sledováním zadaného bodu v obrazu, a jeden hladký spline, který si navolil uživatel. Určitému bodu na stabilizované křivce odpovídá poloha určitého bodu na křivce, ve které je obsaženo chvění. Mohlo by se tedy zdát, že stabilizace vychází jen z těchto dvou křivek, avšak je nutné vzít v potaz ještě jeden faktor. Sledovaný bod se může dostat mimo obraz (např. pokud kamera švenkuje na jiný objekt) nebo může dojít k zakrytí sledovaného bodu jiným objektem. V takovém případě dojde k přerušení sledované trajektorie a je nutné zadat další bod pro sledování. Takto je možné zadat libovolné množství bodů v různých časech. Při stabilizaci je ovšem dobré vnímat celou časovou osu jako jeden celek. Bylo by nepraktické zadávat novou stabilizační křivku pro každý započatý úsek stabilizace. Proto je vhodné všechny takové úseky ve videu nějakým

40

způsobem sloučit v jeden celek. Uživatel tak získá možnost ovládat stabilizaci nezávisle na poloze bodů, které určil pro sledování. Nejdříve je nutné sloučit jednotlivé oblasti v jeden celek. Princip slučování takových oblastí znázorňuje obrázek 3.5. Na něm je zobrazen příklad diagramu sledování trajektorie polohy bodu v závislosti na čase, který ubíhal stále jedním směrem. Poté, co se bod ve videu dostal mimo obraz, uživatel zvolil nový bod pro sledování. Například původní bod mohl z obrazu zmizet směrem nahoru a uživatel vybral nový bod uprostřed obrazovky, ale nová trajektorie kamery je pokračováním té původní. Nový objekt pro sledování je tedy napojen na předchozí sledovanou trajektorii. To je na obrázku znázorněno křivkou. Proto je tedy možné celou trajektorii vnímat jako jeden souvislý celek, přestože vznikla spojením více kratších segmentů. Stabilizace se tedy dosahuje porovnáváním dvou křivek a je tak možné, aby uživatel zadal jako stabilizační křivku jen počáteční a koncový bod, přestože pro sledování zadával bodů více.

3.10

Editování křivek

Křivky pro stabilizaci jsou Bézierovy křivky, jejichž použití je známé z běžných grafických vektorových editorů. Jedna kubická Bézierova křivka je zadána čtyřmi body, dva z nich jsou koncové uzlové body, další dva představují koncové body vektorů vedoucí z uzlových bodů, tyto vektory jsou tečné na křivku v jejích koncových bodech. Jednu takovou křivku znázorňuje obrázek 4.2 na stránce 52. Pro vytváření složitějších tvarů je možné na sebe Bézierovy napojovat v koncových bodech, čímž vznikne jedna dlouhá křivka a z původních uzlových koncových bodů se stanou kotevní body, z nichž každý má k sobě připojeny dva body uřčující tečné směry. Pokud jsou jednotlivé kotevní body uloženy v různých časech a jsou na křivce seřazeny v rostoucí posloupnosti v pořadí podle času, pak tvoří křivka mezi těmito body trajektorii. Stejným způsobem je křivky využito i v této

41

práci. Spline křivka je určena body, které jsou rovnoměrně rozloženy od začátku sledování až do konečného bodu v čase. Pokud si uživatel přeje změnit tvar křivky, stačí přesunout příslušný řídící bod, ať už se jedná o kotevní bod anebo bod určující tečnu. Může ovšem nastat případ, kdy pouhé přesunování bodů nestačí k vystihnutí tvaru křivky požadovaného uživatelem. V takovém případě je možné do křivky zařadit nový kotevní bod mezi body již existující. Uživatel umístí jezdec pro výběr času na patřičné místo, kam si přeje umístit nový bod, stiskne tlačítko pro vytvoření bodu a systém přidá řídící body tak, aby kotevní bod ležel na původní křivce a kotevní body z ní vycházely. Poté je možné body přesunovat k dosažení kýženého tvaru. Zajímavý je princip algoritmu pro výpočet sady nových řídících bodů, které určují tvar křivky. Pro rozdělení Bézierovy křivky na dvě části je možné s výhodou použít algoritmus de Casteljau, jehož princip je naznačen na obrázku 4.3 na stránce 52. Uzlový bod leží na původní křivce, výpočet jeho polohy je tímto algorigmem přímočarý, stačí jen zadat patřičný parametr. O něco málo náročnější je výpočet bodů určujících tečné vektory. Při výpočtu algoritmu de Casteljau se vychází z orientovaného polygonu o čtyřech vrcholech. Po každém kroku algorimtu vznikne nový polygon, který má o jeden vrchol víc, než předcházející. První krok algoritmu tak vypočítá polygon s pěti vrcholy, druhý krok vypočítá polygon s šesti vrcholy. A právě vrcholy z druhého kroku výpočtu jsou řídící body nového polygonu. Toto bylo naznačení výpočtu nových řídících bodů při přidávání bodu do křivky. Pokud si uživatel naopak přeje bod z křivky odstranit, například křivka obsahuje příliš mnoho bodů pro potřeby uživatele, je situace poněkud odlišná od předchozí situace. Křivka totiž v obecném případě reprezentuje tvar, který není možné po odebrání bodu vystihnout. Pokud například původní tvar křivky reprezentoval vlnovku do tvaru písmene „Wÿ se třemi vrcholy, dva v každém rohu písmene a jeden uprostřed, pak po odebrání prostředního vrcholu není možné napodobit původní tvar křivky. Neexistuje tedy exaktní řešení takového zadání. Proto jsem se pro jednoduchost rozhodl ubírání vr-

42

cholu z křivky implementovat jako prosté smazání bodu s tím, že původní nesmazané body zůstanou beze změny. Toto je nejjednodušší řešení daného úkolu.

3.11

Transformace času

Jako inspirace alternativní možnosti k editování křivek může sloužit přístup z některých modelovacích nástrojů pro 3D. V nich je možné nezávisle editovat průběh trajektorie a nezávisle na trajektorii editovat průběh času. Jako příklad využití této metody bývá uváděn planetární model sluneční soustavy. Pokud by uživatel chtěl vytvořit planetární model metodou kreslení klíčových bodů, byla by taková práce velmi náročná na čas i schopnosti uživatele, navíc by obsahovala nepřiměřeně mnoho klíčových bodů na křivkách jednotlivých trajketorií planet. Proto bývá jako alternativa nabízena možnost vytvořit křivku trajektorie nezávisle na časovém průběhu pohybu bodu po této křivce. Křivky planet bývají reprezentovány kružnicí nebo elipsou, časový průběh pohybu po takových křivkách je možné editovat zvlášť, stejně snadno jako kdyby se jednalo o pohyb po lineární trajketorii. Při implementaci programu pro stabilizaci jsem se snažil tento přístup zakomponovat do návrhu programu a přidat možnost editovat časový průběh na nezávislé ose grafu. Příklad využití takové možnosti může být záběr na řadu stojících fotbalistů, které zabírá kamera jedoucí rovnoběžně s jejich řadou. Pokud by se například tvůrce záběru rozhodl ve fázi postprodukce změnit časování a záběr na malou chvíli pozdržet na některém fotbalistovi uprostřed řady, byla by trajektorie obrazu stále lineární. Kdyby existovala možnost měnit průběh času nezávisle na trajektorii, stačilo by editovat tento průběh tak, aby se uprostřed poněkud zpomalil a záběr se na kratší dobu pohyboval pomaleji v okolí zvoleného bodu. Při použití této možnosti ve spojení s křivkami spline se vlastně jedná o složenou funkci, neboť křivky trajektorií nejsou v takovém případě závislé

43

na čase, ale na vnitřní proměnné, která je naopak funkcí času. Praktické pokusy s touto možností však značně komplikovaly běžné editování, protože průběhy trajektorií se přestávaly chovat intuitivně. V okně Graph Preview přestaly být vektory tečné na průběh křivek, neboť změna časování křivky značně změnila její tvar. Rozhodl jsem se proto takové chování do programu neimplementovat. Jedná se však o velmi zajímavou alternativu, bylo-li by zadávání trajektorie řešeno jinou geometrickou technikou.

3.12

Prokládané video

Technika prokládaného videa vznikla z důvodu přenosové kapacity médií ve třicátých letech dvacátého století. Bylo nutné zvýšit snímkovou frekvenci vysílaného obrazu, ale nebylo možné přenášet plné rozlišení obrazu ve vyšších snímkových frekvencích. Bylo proto rozhodnuto každý snímek rozdělit na dva půlsnímky a řádkové vzorkování obrazu rozdělit na liché a sudé. Tím se dosáhlo dvojnásobné snímkové frekvence, která je příjemnější lidskému zraku, při zachování nízké přenosové kapacity. Tato technika je sice velmi vhodná pro efektivní přenos signálu, je ale velmi složitá pro návrh algoritmů na zpracování obrazu. V současné době se v praxi používá i video s obrazem neprokládaným a je otázka, kterou cestou se bude televizní technika do budoucna ubírat. Algoritmus sledování trajektorie Block Matching Algorithm je zaměřen na použití na progresivním videu. Použití prokládaného videa v tomto altoritmu způsobuje několik probémů, které je nutné brát v potaz. Jednotlivé půlsnímky jsou posunuty v čase, navíc jsou ale sudé a liché půlsnímky navzájem posunuty prostorově, protože jsou vzorkované na jiných řádcích obrazu. Tím vzniká otázka, jak sledovat pohyb v prokládaném videu. Pokud by se proklad videa ignoroval, bylo by mnohdy nemožné najít korespondující bod v nějakém snímku videa, protože rozdíl v obrazech způsobený pohybem v prokládaném videu by způsobil rozpadnutí obrazu na liché a sudé snímky, které by nebyly podobné vzororvému obrazu s jinou rychlostí pohybu.

44

Pokud by se prokládané video řešilo zcela speciálně a každý snímek by byl rozdělen na dva nezávislé půlsnímky, vzniká otázka, jak zacházet s každým z nich zvlášť, protože vzorky z těchto půlsnímků se nacházejí na jiném místě i v jiném čase. V této diplomové práci je prokládané video řešeno technikou, která je kompromisem mezi oběma uvedenými principy. Pokud uživatel zadá, že video je prokládané, sleduje se pohyb jen v prvním půlsnímku, ale posun stabilizace se vypočítává shodný pro oba půlsnímky. Ve fázi korekce obrazu se oba půlsnímky berou jako dva nezávislé snímky. Vznikají tím potíže v obrazu, pokud byl pohyb příliš veliký, projeví se to ve snímku obrazem rozpadlým na dvě poloviny a ve stabilizovaném videu je viditelný artefakt podobný cuknutí. S prokládáným videem se v této práci tedy zachází správně ve smyslu obrazových transformací (to znamená že obsah prvního půlsnímku zůstane v prvním půlsnímku a naopak), ale nezachází se správným způsobem se sledováním pohybu, protože obsah druhého snímku se v této fázi zcela ignoruje. Podpora prokládaného videa je v této práci tedy pouze experimentální a primárně se zaměřuje na progresivní video.

45

Kapitola 4 Implementace Tato kapitola nastiňuje některé implementační detaily programu pro zpracování videa. Tyto detaily mohou být užitečné, pokud by se čtenář buď setkal s potížemi při práci v podobné oblasti anebo měl zájem rozšiřovat stávající funkčnost filtru pro stabilizaci videa. Zdrojové kódy obou programů jsou podrobně komentovány v anglickém jazyce, takže je při pohledu do programu zřejmé, co ta která část programu dělá. V této kapitole jsou tedy popsány datové struktury vyšší úrovně, složitější algoritmy a také nečekané technické potíže a omezení, se kterými jsem se při implementaci setkal.

4.1

Antishake v C#

Program Antishake jsem se rozhodl implementovat v programovacím jazyku C#, pro jeho silné propojení s rozhraním Windows, které poskytuje jak přístup ke standardním grafickým komponentám uživatelského rozhraní, tak nízkoúrovňovým službám pro práci s videem pomocí knihovny DirectShow. Úkolem tohoto programu je načíst zadané video a zobrazit jej uživateli ve formě pracovní plochy, na které může provádět různé operace. V první fázi jde o výběr bodů, které jsou určené pro tracking, ve druhé fázi jde o editaci křivek určených pro stabilizaci.

46

Důležité bylo získat přístup přímo k datům, které video obsahuje, aby s nimi mohl uživatel pracovat. Podle článku [34] není možné přistupovat k obrazovým datům přímo z platformy .NET a jazyka C#. Pro zprovoznění této možnosti je nutné využít modulu nižší úrovně, v této práci bylo využito knihovny DirectShowNet [35]. I přes využití externích knihoven však není možné využívat všech možností, které poskytuje knihovna nižší úrovně DirectShow. Následuje výčet nejzávažnějších technických nedostatků přístupu k videu na nižší úrovni a nástin řešení, která jsem použil, abych se vyhnul potížím. Nejdůležitější funkčností bylo získávání dat z obrazu videa. Běžně program nemá přístup k datům videa, pokud otevřel video soubor pomocí rozhraní knihovny DirectShow. Tento nedostatek bylo nutné obejít při použití knihovny DirectShowNet. Využil jsem informací v článku [34], autor radí přidat do grafu pro zpracování videa filtr SampleGrabber, který je zařazen mezi dekódování dat videa a mezi zobrazení na obrazovku. Při každém výpočtu jednotlivého snímku videa se zavolá metoda z rozhraní ISampleGrabber, která poskytuje datový ukazatel na obsah videa. Této možnosti jsem tedy v implementaci využil. Při každém spuštění call-back metody z filtru SampleGrabber se data nakopírují do připraveného bufferu, ze kterého se mohou buď vykreslovat na obrazovku nebo slouží pro tracking bodu. Pokud tedy program požaduje zachytit data určitého snímku videa, nastaví časovou pozici ve videau a uspí své výkonné vlákno. Filtr pro zpracování videa poté spustí call-back metodu, ve které se zkopírují data do připraveného bufferu a probudí se vlákno výkonného programu. Dalším technickým nedostatkem je zjišťování snímkové frekvence videa. Antishake potřebuje tuto informaci pro přístup k jednotlivým snímkům videa, aby si mohl vyžádat kopii jejich dat. Většinou jsou tyto informace dostupné pro video pořízené videokamerou. Potíže mohou nastat u některých kodeků, některé například nepracují s konstantní snímkovou frekvencí, takže je zjištění tohoto údaje nemožné. Tento nedostatek jsem vyřešil tím, že se v uživatelské aplikaci po otevření video souboru uživateli zobrazí dialogové

47

okno pro zadání snímkové frekvence. Pokud snímková frekvence nemohla být zjištěna z informací poskytovaných kodekem, zobrazí se dialog s předvyplněnou hodnotou „1ÿ a zadání smysluplné hodnoty je na uživateli. Poloha v čase se určuje pomocí reálného čísla vyjadřující počet sekund od začátku videa. Zadávání daného údaje takovýmto způsobem přináší ještě další problém a to zjištění čísla aktuálního snímku podle časové značky. Běžným problémem je například to, že na dotaz na celkovou délku videa vrátí kodek nějakou hodnotu, ale když video dohraje, má hodnota snímku odlišnou hodnotu. Může to způsobit například to, že jezdec pro výběr časové polohy ve videu se v grafickém uživatelském rozhraní nedostane až na svůj konec, přestože bylo dosaženo posledního snímku videa, přičemž kodek negeneruje žádnou novou událost, na kterou by mohl program reagovat. Nelze také zastavit přehrávání videa, přestože už dosáhlo svého konce. Pokud tedy uživatel stiskne ikonu pro přehrávání videa, je video stále v módu pro přehrávání a když uživatel pohne jezdcem pro výběr časové pozice ve videu, začne se video samo přehrávat. Podstatným nedostatkem je nemožnost získávat vstup od uživatele, který provádí v okně videa. Není například možné zachytit kliknutí myši do oblasti, ve které se přehrává video knihovnou DirectShow. Tento technický nedostatek jsem musel obejít rozdělením aplikace na dva módy: přehrávač (reprezentovaný záložkou Player) a editor (reprezentovaný záložkami Tracking a Stabilize). V módu přehrávače nemá uživatel možnost provádět zásahy do videa, pokud se však přepne do editoru, je okno přehrávače zakryto a nahradí ho bitmapa vytvořená z obrazových dat videa, která je ovšem schopná události myši přijímat. Tato operace je pro uživatele zcela transparentní. Uživatel si proto vůbec nevšimne, kdy dojde k přepnutí, ani nemá možnost rozlišit, kdy je zobrazen přehrávač videa nebo kdy je viditelná bitmapa s daty videa. Zcela správně funguje vykreslování i při změně měřítka nebo velikosti okna. Přehrávání videa je možné pouze v módu přehrávače, zatímco data z obrazu videa je možné získat jen v módu editoru. Tím vzniká problém, že není

48

možné zobrazit náhled na stabilizované video, který by se přehrával stejnou rychlostí jako původní video, protože není možné transformovat obraz v reálném čase. Tento nedostatek se nedal odstranit technickými prostředky, proto jsem se v implementaci rozhodl obejít tento problém jinou cestou. Namísto vykreslování okna náhledu, které by zobrazilo podobu obrazu videa tak, jak by vypadalo po transformaci, což by bylo bezúčelné, neboť by se jednalo o statický obraz, nikoli o přehrávání náhledu v reálném čase, přidal jsem do programu zobrazení křivek trajektorií v grafu. Uživatel tak může porovnat křivky trajektorie pohybu v jednotlivých osách v závislosti na čase. V každé z os vedle sebe vidí křivku před stabilizací a po stabilizaci. Jejich vzájemným porovnáním může zvolit nejvhodnější možnou stabilizaci. Okno, které jsem v aplikaci nazval „Graph Previewÿ, je popsané v kapitole o ovládání programu. Další otázkou je také stabilita použité knihovny, neboť práce s videem opakovaně zhroutila program bez jediné hlášené chyby nebo vyhozené výjimky. Doporučení pro bezpečnější práci s videem jsou uvedena ve stručném návodu programu. Přes uvedené nevýhody je knihovna DirectShowNet patrně nejlepší volbou pro přístup k datům videa, jak uvádí článek [34], použitá knihovna patrně dosahuje nejzasší hranice, které je možné na moderní platformě .NET v oblasti videa dosáhnout.

4.2

Sledování trajektorie

Princip algoritmu pro sledování bodu Block Matching Algorithm byl popsán již dříve v této publikaci. V této části popíšeme datové struktury, se kterými pracuje. Algoritmus ke své práci potřebuje souřadnice bodu v obrazu v daném čase a výřez obrazu kolem tohoto bodu, podle kterého vyhledává korespondující body v následujících snímcích videa. Jeho výstupem je pak souvislá řada nalezených bodů. Zadání souřadnic pro sledování i výstup algoritmu jsou uloženy ve společné datové struktuře, která se skládá z datových typů TimeLine, TimeLineSegment a TimeSpot, jejich UML diagram zachycuje pro

49

Obrázek 4.1: UML diagram TimeLineSegment

lepší pochopení obrázek 4.1.

4.3

Slučování trajektorií

Poměrně složitým se ukázal z implementačního hlediska úkol slučování sledovaných oblastí, jak to znázorňuje obrázek 3.5 v sekci 3.9 na straně 40. Při zpracování těchto dat a při stabilizaci bylo nutné brát na zřetel to, že křivka sledování byla původně rozdělena na jednotlivé segmenty podle bodů zadaných pro sledování a nyní je složena z několika částí, které spolu původně nesouvisely. Ty je nutné v určitém bodě sloučit. Po zadání bodu pro sledování jsou v následujících snímcích videa nalezeny odpovídající body, které tvoří sledovanou trajektorii. Toto prohledávání není možné ukončit ihned, jakmile algoritmus ve videu nalezne další bod pro sledování. První trajektorie musím končit ve stejném snímku, ve kterém začíná druhá trajektorie. Tyto dva body ve stejném snímku videa je nutné uložit pro pozdější zpracování, aby z nich pak mohl být spočítán rozdíl mezi první a druhou křivkou.

50

tracking = false; for (i = 0; i < len; i++) { GoToFrame(i); if (tracking) { trackPoint(sampBmp, out pX, out pY, frameBmp); nts = new TimeSpot(pX, pY); segment.Add(nts); } nSeg = timeLine.findTimeLineSegment(i); if (nSeg != null) { segment = nSeg; sampBmp = segment.sampleBMP; pX = segment.getTrackingTimeSpot().watchTimeSpot.x; pY = segment.getTrackingTimeSpot().watchTimeSpot.y; tracking = true; } }

Algoritmus pro slučování oblastí byl pro jednoduchost spojen s algoritmem pro sledování bodu. Princip tohoto spojeného komplexního algoritmu ukazuje program zapsaný v pseudokódu na této stránce.

4.4

Křivky

Datová struktura pro ukládání řídících bodů Bézierových křivek je velmi jednoduchá – jedná se o jednorozměrné pole bodů KeyFrame, každý z nich obsahuje časovou informaci frameNumber, souřadnice uzlového bodu point a souřadnice fromPoint a toPoint. Pro ilustraci významu jednotlivých složek je přiložen obrázek 4.2. Bézierova křivka se vykresluje známým algoritmem de Casteljau. Základem jeho principu pro výpočet jednoho bodu na křivce je rekurzivní dělení 51

Obrázek 4.2: Význam prvků datové struktury pro Bézierovu křivku

Obrázek 4.3: Princip algoritmu de Casteljau

52

úseček řídícího polygonu v daném poměru, čímž se počet úseček snižuje, až se dojde k jedinému bodu. Princip je zobrazen na obrázku 4.3.

4.5

Antishake pro VirtualDub

Software pro export je plugin pro program VirtualDub [27]. Výhodou programu VirtualDub je to, že je k dispozici zdarma i se zdrojovými kódy. Jedná se o nástroj pro zpracování a kompresi digitálního videa. Poskytuje několik efektů, jako je korekce jasu, změna rozlišení, doostření a jiné. Další efekty je možné do programu dodat ve formě pluginů. Funguje tedy i jako plugin-host pro filtry třetích stran. Výhodou této metody je, že každý filtr přistupuje k videu pomocí standardizovaného rozhraní, aniž by se musel starat o interakci s jinými filtry, import videa ze souboru AVI, práci s kodeky nebo ošetřování většiny akcí uživatele. Pro pluginy je připraveno jednoduché rozhraní (anglicky „application programming interfaceÿ či „APIÿ). Při spuštění zpracování videa se zavolá funkce startProc(), jejím úkolem je připravit datové struktury filtru. Poté se při zpracovávání videa spustí pro každý jednotlivý snímek funkce runProc(), která má přístup k datům snímku a také může libovolně měnit

jeho obsah. Pokud si uživatel přeje konfigurovat filtr, vyvolá se funkce configProc(), která může otevřít konfigurační dialogové okno. Rozhraní obsahuje samozřejmě ještě několik dalších funkcí, ty jsou ovšem z hlediska pochopení funkčnosti filtru nevýznamné. Pro detailní pochopení všech funkcí je velmi vhodný tutorial, který je standardní součástí SDK pro VirtualDub. Externí filtry VirtualDubu mají oproti interním filtrům několik omezení: • Není možné přistupovat k datům z jiných framů videa • Není možné měnit počet snímků • Nemohou přistupovat k interním strukturám VirtualDubu 53

Nemožnost přistupovat k interním strukturám VirtualDubu velmi omezuje komfort uživatele. Filtr totiž například nemůže přímo získávat informace o akcích uživatele. Bylo by například vhodné, aby uživatel klikl na obrázek videa do místa, které vybral jako klíčové. Protože je ale tento filtr externí, informace o kliknutí myši nemůže získat. Tato vlastnost rozhraní pluginu velmi omezuje možnosti, kterými plugin komunikuje s uživatelem. Z pohledu externích filtrů se tedy opravdu jedná o nástroj pro dávkové zpracování videa, spíše než o interaktivní program, který zprostředkuje rozhraní mezi uživatelem a filtrem. Filtr pro VirtualDub, který je součástí vypracování této diplomové práce, byl zpracován účelovým a přímočarým způsobem. Režim jeho práce je následující. Po zavedení filtru do VirtualDubu se zobrazí dialogové okno, které uživatele vybízí, aby zadal soubor, ve kterém jsou uloženy informace o stabilizaci videa. Uživatel vybere soubor a data o stabilizaci se okamžitě uloží v paměti počítače. Dále je popsán formát souboru s informacemi o stabilizaci. Soubor je textový, řádkově orientovaný. První řádek obsahuje přirozené číslo s informací o celkovém počtu snímků ve videu. Druhý řádek obsahuje buď text „interlacedÿ nebo „noninterlacedÿ podle toho, zda je video prokládané nebo neprokládané. Následuje stejný počet řádek, jako je snímků ve videu, na každém z těchto řádek je pět reálných čísel, navzájem oddělených mezerami. První dvě čísla určují vektor posunutí ve vodorovném a svislém směru, druhá dvě čísla určují souřadnice středu rotace v pixelech obrazu a poslední číslo udává úhel rotace v radiánech, rotace je orientována v kladném smyslu (tzn. proti směru běhu hodinových ručiček). Přikládat zde příklad výpisu souboru pravděpodobně nemá význam z prostorových důvodů, navíc je formát velmi jednoduchý a uživatel aplikace si takový příklad může snadno vygenerovat sám. Při další práci s videem ve VirtualDubu se obraz transformuje podle informací získaných z transformačního souboru. Před zobrazením každého snímku videa se spustí funkce filtru runProc(), která provede rotaci a posunutí obrazu. Hodnoty těchto transformací čte z paměti počítače, indexované jsou

54

podle čísla snímku ve videu. Filtr funguje samočinně bez dalších zadání uživatele, není tedy zapotřebí pracovat s grafickými prvky uživatelského rozhraní. Filtr provádí pouze obrazové transformace v době, kdy získá obrazová data od hostitelské aplikace, která zavolá pro zpracování metodu runProc(). Následuje pseudokód této medoty. int runProc() { fr = lCurrentSourceFrame; if (fr je ve sledovaném rozsahu) { vyplnit dst černou barvou; tmp = rotate(src, rotAngle, interlaced, rx, ry); dst = shift(tmp, tx, ty); } else { zkopírovat data aktuálního snímku na výstup filtru } return 0; }

4.6

Implementace transformací

Transformace v metodě runProc() se skládají z posunutí a rotace. Tyto transformace je zapotřebí rozebrat poněkud podrobněji, neboť nejsou zcela triviální. Obě transformace navíc používají metodu nazývanou super-resolution, takže pracují se sub-pixelovou přesností. Obě transformace využívají pomocné statické funkce pro posun jednoho sloupce pixelů nebo jedné řádky pixelů v obrazu. Parametr pro hodnotu posunutí je reálné číslo, posunutí se tedy neprovádí prostým kopírováním hodnot pixelů. Transformace se děje lineární kombinací dvou po sobě následujících pixelů v řádku nebo sloupci pixelů. Pro názornost následuje pseudokód metody pro posun řádky pixelů.

55

shiftBitmapLine() { if (shift < 0) { intShift = -(int)(1 - shift); alpha = intShift + 1 - shift; src = src - intShift * 4; copyWidth = width + intShift; } else { intShift = (int)shift; alpha = intShift + 1 - shift; dst = dst + intShift * 4; copyWidth = width - intShift; } rR = 0, rG = 0, rB = 0; for (int x = 0; x < copyWidth; x++) { // sub-pixel moving for Red color orig = *src; tmp = orig * alpha; *dst = rR + tmp; rR = orig - tmp; src++; dst++; // následuje totožný postup // pro barvy Green a Blue, // v proměnných rG a rB... // z důvodu stručnosti vypuštěno } }

56

Transformace posunutí je z obou transformací ta jednodušší. K transformaci dochází separovaným bilineárním algoritmem. Nejprve se voláním pomocné funkce posunou o zadanou hodnotu všechny řádky pixelů, poté se posunou všechny sloupce pixelů. Složitost algoritmu je tedy O(n2 ), kde n je rozměr bitmapy v jednom směru. Následuje pseudokód metody pro posun bitmapy se sbupixelovou přesností. shiftBitmap(src, dst, x, y, width, height, stride) { for (line = 0; line < width; line++) { shiftBitmapLine(src, dst, width, x); } if (interlaced) { for (int col = 0; col < width; col++) { shiftBitmapColumn(src, stride * 2, dst, stride * 2, (height + 1) / 2, y / 2); shiftBitmapColumn(src + stride, stride * 2, dst, stride * 2, height / 2, y / 2); } } else { for (int col = 0; col < width; col++) { shiftBitmapColumn(src, stride, dst, stride, height, y); } } }

Je důležité podmínku na prokládané video vyzvednout mimo cyklus, protože podmínka v cyklu je z hlediska efektivity velmi drahá operace. Podmínka je proto vně cyklu a cyklus je ve zdrojovém kódu naprogramován dvakrát. Transformace rotace je v grafice velmi choulostivá operace. Pokud by se bitmapou otáčelo bod po bodu za použití goniometrických funkcí, byla by transformace nejenom velmi pomalá, ale také by docházelo k mnoha chybám při interpolaci bodů. Transformace rotace je pro dosažení vyšší efektivity algoritmu rozdělena na tři transformace zkosení, které jsou ekvivalentní rotaci. Tento agloritmus je v počítačové grafice velmi dobře známý. 57

Před začátkem vlastního zpracování obrazu jsou nejprve vypočteny konstanty pro jednotlivé transformace. Pokud je α úhel rotace, pak sH =

cos(α)−1 sinα

je hodnota pro zkosení v horizontálním směru a sV = sinα je hodnota zkosení ve vertikálním směru. Poté se postupuje v následujícím pořadí: horizontální zkosení, vertikální zkosení a nakonec horizontální zkosení. Transformace zkosení je dosaženo posunem řádků obrazu v cyklu pro horizontální zkosení, posunem sloupců v cyklu pro vertikální zkosení. Výpočetní složitost algoritmu je tedy také O(n2 ), kde n je rozměr bitmapy v jednom směru. Následuje pseudokód metody pro rotaci bitmapy se sbupixelovou přesností. void rotate(src, dst, angle, interlaced, line, column) { absrot = abs(angle); if (absrot > eps) s1 = (cos(angle) - 1) / sin(angle); else s1 = 0; s2 = sin(angle); shearHoriz(src, stride, tmp1, w, h, line, s1); if (interlaced) { shearVert(tmp1, stride * 2, tmp2, stride * 2, w, h / 2, column, s2 / 2); shearVert(tmp1 + stride, stride * 2, tmp2 + stride, stride * 2, w, h / 2, column, s2 / 2); } else { shearVert(tmp1, stride, tmp2, stride, w, h, column, s2); } shearHoriz(tmp2, stride, dst, stride, w, h, line, s1); }

Následuje ještě příklad algoritmu pro vertikální zkosení. To probíhá posunutím každého sloupce bitmapy. Narozdíl od posouvání celé bitmapy jako 58

celku se vypočítává koeficient posunutí pro každý sloupec jiný. void shearVert(srcP, srcStride, dstP, dstStride, width, height, column, shear) { for (int x = 0; x < width; x++) { h = column - x; shift = h * shear; shiftBitmapColumn(srcP, srcStride, dstP, dstStride, height, shift); dstP += 4; srcP += 4; } }

Při transformaci rotace i posunutí je nutné dbát zvýšené opatrnosti při práci s prokládaným obrazem videa. S každým půlsnímkem je nutné nakládat, jako by se jednalo o samostatný nezávislý obraz, přitom hodnoty pro svislé posunutí i svislé zkosení se musí vypočítávat poloviční oproti neprokládanému obrazu. Tyto hodnoty je nutné propagovat i do podřízených funkcí, které tento fakt musí brát v potaz.

4.7

Stručný návod

Toto je návod na použití samostatné aplikace Antishake i pluginu pro program VritualDub. Návod je psán takovým postupem a v takovém pořadí, aby podle něj bolo možno pracovat s oběma programi a stabilizovat video. Každý soubor videa ovšem není vhodný ke stabilizaci. Například filmové soubory s kodekem DivX jsou pro zpracování výslovně nevhodné kvuli použití kodeku zaměřeného primárně na kompresi dat. Knihovna DirectShowLib má s takovým typem dat potíže a při převíjení videa občas způsobí dokonce zhroucení celého programu. Nejvhodnějším typem souboru jsou AVI ve formátu DV, který pořizují digitální kamery. S tímto typem souboru bylo při praktických pokusech nejméně 59

Obrázek 4.4: Úvodní okno programu Antishake

problémů. Jako příklad je několik takových souborů nahráno na přiloženém DVD. Samostatnou aplikaci není nutné nijak instalovat, nicméně k jejímu spuštění je zapotřebí knihovna DirectShowLib, která je přiložena na CD. Po spuštění obsahuje program oblast pro obraz videa, posuvník pro pohyb v čase a oblast pro ovládání. Úvodní okno programu je na obrázku 4.4. Program pracuje ve třech režimech, mezi kterými je možné přepínat záložkami v oblasti pro ovládání v levém dolním rohu. První režim Player funguje jako přehrávač videa, ovládací prvky jsou jen pro spuštění a zastavení přehrávání. Po otevření souboru s videem položkou menu File > Open se zobrazí první snímek videa a program se zeptá na vlastnosti videa – snímkovou frekvenci a prokládaný obraz – poté a jsou přístupné ovládací položky. Ikona pro spuštění přehrávání videa. Ikona pro zastavení přehrávání.

60

Obrázek 4.5: Zadávání sledovaných bodů

Druhý režim programu (znázorněn na obrázku 4.5) je určen pro zadávání sledovaných bodů. Do tohoto režimu je možné dostat se klepnutím na záložku Tracking v ovládací oblasti. V tomto režimu je možné kliknout myší do obrazu videa, čímž se zadá nový bod pro sledování. Kliknutím pravým tlačítkem myši do obrazu videa se k bodu pro sledování trajektorie přidá druhý bod, který je určen pro sledování rotace obrazu. Je možné se pohybovat v časové ose a zadávat další body pro sledování, pokud původní bod například zmizel z obrazu. Pokud zadání bodu nebylo správné, může uživatel kliknout do obrazu znovu, čímž zadá nový bod pro sledování na aktuální časové pozici. Pokud chce uživatel úplně zrušit jeden konkrétní zadaný bod, stačí jej vymazat klepnutím na ikonu. Červeným křížkem je možné vymazat bod na aktuální časové pozici. Ikona pro smazání bodu pro sledování na aktuální pozici. Nyní bude popsán význam barevných bodů na obrazovce. Po stisknutí myši do oblasti videa se objeví modré kolečko s červeným okrajem, které značí počáteční bod pro sledování nějakého předmětu ve videu. Body, které byly nalezeny metodou motion tracking, jsou zobrazeny modrým kolečkem 61

Obrázek 4.6: Stabilizace křivkami

bez červeného okraje. Po stisknutí pravého tlačítka myši dojde k přidání bodu pro sledování rotace. Body pro sledování rotace představuje malé červené kolečko, které je spojeno rovnou čarou s bodem pro sledování pohybu. Toto je význam všech grafických prvků v obraze. Nyní může uživatel spustit sledování bodů. Po stisknutí tlačítka Start Tracking začne program sledovat trajektorie ve videu. Pokud není uživatel spokojen s výsledkem vyhledaných trajektorií, je možné vrátit se zpět na proces přidávání bodů pro sledování a tam zadat nové vhodnější body. Pokud je uživatel spokojen a byla zpracována celá oblast videa, je možné přepnout se do třetího režimu. Do třetího režimu je možné dostat se klepnutím na záložku Stabilize v ovládací oblasti. Tento režim slouží na úpravu trajektorie bodu, který byl sledován v přecházejícím kroku. Jde o editaci kubických spline křivek, po kterých bude probíhat nově zvolená trajektorie. Snímek tohoto režimu je na obrázku 4.6. V tomto režimu je v obrazu znázorněn sledovaný bod, který ukazuje místo

62

nalezené na trajektorii v určitém čase. Tento sledovaný bod je znázorněn modrým kroužkem, stejně jako v kroku vyhledávání trajektorie. Dále je v obrazu znázorněna Bézierova křivka stabilizované trajektorie, po které bude nový bod probíhat. Křivky jsou v obrazu znázorněny žlutou barvou. Důležité pro ovládání křivky jsou řídící body. Uzlové body jsou znázorněny zeleným kolečkem, body vektorů jsou reprezentované modrými úsečkami s kolečkem na konci. Pokud chce uživatel pohnout některým z bodů pro ovládání křivek, stačí na příslušném bodu stisknout tlačítko myši a bod tažením přesunout na jiné místo. Na křivce je zobrazen červený bod, který značí, na které nové místo se přesune původně sledovaný bod. Tento bod je určen podle parametru času. Při pohybu jezdcem pro ovládání času se červený bod pohybuje po žluté křivce spline. Pokdu si uživatel přeje dále změnit tvar křivky a nabízené ovládací body k tomuto již nestačí, je možné přidat nový kotevní bod. Nejprve je nutné zvolit v kterém čase kotevní bod přidat a tuto hodnotu zvolit na jezdci pro výběr času v oblasti pro ovládání. Ikonami je možné přidávat a ubírat uzlové body v aktuálním čase tak, jak je to běžné ve vektorových grafických editorech. V tomto režimu je k dispozici několik ovládacích ikon. Ikona pro vyhledání času předcházejícího kotevního bodu křivky. Ikona pro přidání nového kotevního bodu na aktuální pozici. Ikona pro smazání kotevního bodu na aktuální pozici. Ikona pro vyhledání času následujícího kotevního bodu křivky. Pokud chce uživatel zadat jinou polohu sledovaného bodu, má možnost vrátit se do předchozího režimu a vybrat nový bod pro sledování. Pro přesnější zadání bodů do obrazu je možné využít funkci zoom v nabídce okna nebo prostým tažením rámu okna. Vhodné je také využít funkci Video > Graph Preview, známý jako Graph Editor z programů Maya, 3D Studio nebo Blender (kde se ovšem nazývá IPO Curves Editor). Okno Graph Preview je znázorněno na obrázku 4.7.

63

Tento dialog částečně nahrazuje funkci preview. V okně jsou pod sebou přehledně zobrazeny tři panely, každý znázorňující jeden graf, představují závislost polohy nebo rotace na čase. V pořadí shora dolů představují vodorovnou osu polohy, svislou osu polohy a rotaci. V každém z panelů Graph Preview se zobrazují dvě křivky: křivka sledovaného bodu a křivka s editovanou trajektorií. Křivka sledovaného bodu je zobrazena červenou barvou, křivka s editovanou trajektorií je zobrazena zelenou barvou. Svislá červená čára představuje aktuální pozici v čase. Kotevní body editované křivky mají stejnou barvu, jako v okně videa. Uzlové body jsou znázorněny zeleným kolečkem, body vektorů jsou reprezentované modrými úsečkami s kolečkem na konci. Při pohybu v čase se v Graph Preview pohybuje červená linka znázorňující aktuální čas. Průsečík této časové značky s červenou a zelenou křivkou znázorňuje polohu určitého bodu v čase. Ze vzdáleností těchto dvou průsečíků lze vyčíst, o jak velkou hodnotu bude stabilizovaný obraz posunut nebo zrotován. Pokud se editovaná křivka skládá z více kubických křivek, je to v okně Graph Preview znázorněno dalšími kotevními body, které leží na křivce. V okně videa se zobrazuje vždy jen jedna kubická křivka, která je v právě zvoleném čase aktivní. Pokud je uživatel s výsledkem spokojen a byla zadána celá trajektorie, je možné informace o trajektorii vyexportovat do textového souboru pomocí položky v menu File > Export. Vyexportovaný textový soubor je možné zpracovávat pluginem, který již není součástí této samostatné aplikace. Tím je dokončena práce se samostatnou aplikací Antishake. Plugin je možné použít pouze ve spojení s programem VirtualDub (na obrázku 4.8). Instalace programu VirtualDub je velmi snadná a vlastně se ani o instalaci nejedná – program se pouze „rozbalíÿ z archivu do cílového adresáře. Stejně tak není nutná instalace pluginů. Požadovaný plugin stačí nakopírovat do adresáře plugins, kde jej VirtualDub při spuštění najde. Po spuštění

64

Obrázek 4.7: Graph Preview

Obrázek 4.8: Okno programu VirtualDub

65

programu VirtualDub se otevře okno, v jehož dolní části se nacházejí ovládací ikonky. V menu File > Open video file... je možné otevřít video soubor AVI. Položkou menu Video > Filters... je možné vložit do řetězce zpracování nový filtr, po stisku tlačítka Add... vybrat filtr „Antishakeÿ, který při své inicializaci požádá o jméno vstupního souboru. Nakonec přichází na řadu zpracování videa. Zpracování se spouští tlačítkem ve tvaru >|, které je umístěné dole, třetí zleva, nebo je možné uložit výsledný soubor pomocí položky menu File > Save as AVI... Tím je celé zpracování videa dokončeno. Jelikož filtr neopravuje chybějící okraje, je tato činnost ponechána na dalším zpracování uživatelem. Je možné okraje buď zcela oříznout nebo použít zvětšení obrazu, čímž se okraje dostanou mimo viditelné pole.

66

Kapitola 5 Závěr Tato kapitola uzavírá celou diplomovou práci, diskutuje dosažené výsledky a shrnuje možnosti pro další rozšiřování. Podstatnou součástí této diplomové práce je software přiložený na DVD.

5.1

Dosažené výsledky

Byl prezentován filtr pro digitální stabilizaci videa, který na rozdíl od ostatních dostupných filtrů umožňuje uživateli zvolit libovolnou křivku trajektorie pro stabilizované video. Pro porovnávání výstupu stabilizačních filtrů obecně neexistuje objektivní měřítko. Je sice možné měřit zpoždění filtru, rozsah stabilizovaných frekvencí a další parametry, ale vždy záleží především na tom, zda bylo dosaženo záměru autora. Proto věřím, že v tom je právě přednost této zpracovávané metody – autor videa může do nejmenších detailů ovlivnit konečný výsledek editováním trajektorie stabilizovaného videa, což neumožňuje žádný jiný existující nástroj. Implementovaný filtr podává srovnatelně kvalitní výsledky stabilizace v porovnání s filtrem Deshaker a dalšími zkoumanými filtry, navíc ovšem nabízí možnost libovolně upravovat trajektorii pohybu kamery, což nenabízí žádný další existující filtr.

67

Editování trajektorie stabilizace je možné pomocí Bézierových křivek. V průběhu vývoje existovala i varianta použití Coonsových aproximačních křivek, ale pro zajištění pohodlné editace pro uživatele, bylo nutné od této metody opustit. Rozhodnutí použít Bézierovy spliny vysvětluje kapitola 3.4 na straně 31. V průběhu implementace došlo k dalšímu zásadnímu rozhodnutí a to rozdělit aplikaci na dvě samostatné části – na část provádějící motion tracking, motion compensation a editaci křivek a na část zajišťující image composition, implementovanou ve formě pluginu pro program Virtualdub. Rozhodnutí rozdělit aplikaci na dvě části vysvětluje kapitola 3.2 na straně 28. Implementovaný stabilizační filtr je schopen zpracovávat jak progresivní, tak i prokládaný obraz videa. Pro porovnání časové efektivity byl jako referenční brán filtr Deshaker [16], který je považován za kvalitativně nejlepší filtr v oboru. Rychlost implementovaného filtru je při prvním i druhém průchodu videem dokonce rychlejší než filtr Deshaker, jedná se tedy o velmi rychlý filtr. Kvalita obrazu je ve většině případů srovnatelná s filtrem Deshaker. Na přiloženém DVD jsou pro porovnání kvality uloženy ukázky snímků stabilizované implementovaným filterm a filterm Deshaker. Tento filtr klade větší nároky na ovládání uživatele. Ostatní filtry fungují samočinně, proto nevyžadují žádné zásahy. Například filtr Deshaker vyžaduje zadat množství číselných údajů, podle kterých se pak bude bez dalšího zásahu uživatele zpracovávat video. Nesnadné ovládání je také dáno tím, že žádná podobná aplikace dosud neexistuje, takže není možné převzít myšlenku nebo metaforu jiného uživatelského rozhraní. Svou roli v omezení uživatelského rozhraní sehrála i rozličná technická omezení.

5.2

Další práce

Tato část kapitoly rozebírá možnosti pro případné další rozšiřování implementovaného filtru.

68

Článek [13] uvádí další možnou optimalizaci rychlosti algoritmu pro sledování trajektorie: na vstupní obraz se nejprve aplikuje hranový filtr, jehož výstupem je binárním obraz hran, protože důležité jsou při porovnávání především hrany. Toto vylepšení sice umožňuje rychlejší zpracování, ale přesnost takového porovnání je omezena na jeden pixel, což zabraňuje použití metody super-resolution. Přidání této optimalizace by tedy bylo možné pouze v určité mezifázi algoritmu. Po hrubém nalezení polohy sledovaného bodu by přišel na řadu implementovaný algoritmus pro sub-pixelové posuny. Pro další experimenty s vyhledáváním trajektorie je možné vyzkoušet fázovou korelaci tak, jak ji navrhuje článek [11]. Článek [10] uvádí metodu pro nalezení odpovídajících bodů metodou dualizmu „bod-přímkaÿ pomocí lineárního programování. Článek [7] uvádí vylepšení obrazu zvané „motion inpaintingÿ, které přidává nejen informaci o barvě pixelu, ale také informaci o pohybu obrazu v čase, ze které později doplňuje informaci o chybějících bodech na kraji obrazu. Dále je v tomto článku uváděna metoda pro odstranění rozostření v pohybujících se částech obrazu (anglicky „motion blurÿ) zvaná „image deblurringÿ. Dokud se obraz chvěje, je obraz zároveň tímto pohybem také mírně rozostřen. Toto rozostření diváka neruší, neboť je zároveň součástí pohybu, takže ho lidské oko nevnímá s takovou přesností jako okolní scénu, která je statická. Pokud je obraz stabilizován, rozostření již není součástí pohybu, čímž vytváří viditelné rušivé artefakty. Odstraněním tohoto rozostření ve stabilizovaném videu by došlo ke zlepšení kvality obrazu. Teoreticky by bylo možné algoritmus pro odstranění pohybových artefaktů uváděné v [7] založit na metodě „Point Spread Functionÿ (zkráceně PSF ), ale z praktického hlediska toto není možné, neboť je často obtížné získat přesnou hodnotu PSF pro volně se pohybující kameru. Proto pro odstranění tohoto rozostření není vhodná dekonvoluce. Namísto toho využívá citovaná metoda způsob založený na interpolaci. Základem je využití odpovídajících pixelů z ostatních snímků, které jsou ostřejší. Nejprve se vypočítává tzv. „relativní rozostřeníÿ obrazu v porovnání se sousedními framy. Toto číslo

69

udává, jak moc je obraz vhodným kandidátem pro náhradu neostrých pixelů v sousedních framech. Poté jsou neostré oblasti nahrazeny ostrými oblastmi z ostrých framů. Další podstatné vylepšení by byla možnost sledovat více trajektorií najednou, což by přineslo zpřesnění výpočtů a možnost rozpoznání video-efektů jako je zoom.

5.3

Zhodnocení

V této diplomové práci byl představen implementovaný systém pro stabilizaci digitálního videa. Při práci na tomto filtru jsem překonával víc technických obtíží, než jsem původně očekával. Práce na tomto projektu byla pro mě velmi zajímavá, protože se jednalo o využití zcela nové metody. Doufám, že se jedná o vykročení správným směrem, a že nakonec přinese nové možnosti editování videa nejen v laboratorních podmínkách, ale i běžným uživatelům.

70

Literatura [1] POYNTON, Charles. Digital video and HDTV algorithms and interfaces San Francisco: Morgan Kaufmann Publishers, 2003. 692 s. ISBN 1-55860-792-7. [2] SMITH, Julius O. Digital Audio Resampling Home Page Center for Computer Research in Music and Acoustics (CCRMA), Stanford University, 2006 [cit. 2006-05-13]. Dostupný z WWW: http://ccrma.stanford.edu/~jos/resample/resample.pdf

[3] SHAPIRO, Linda; STOCKMAN, George. Computer vision. Upper Saddle River: Prentice Hall, 2001. xx, 580 s. ISBN 0-13-030796-3. [4] ŠONKA, Milan; HLAVÁČ, Václav. Počítačové vidění Praha: Grada, 1992. 252 s. ISBN 80-85424-67-3. (Broľ.) [5] HighBeam Research. New System Electronically Stabilizes Camera Movement In Video Images at the Studio, in Real Time [online]. Business Wire, 1998 [cit. 2006-08-22]. Dostupný z WWW: http://www.highbeam.com/library/ docFree.asp?docid=1G1:20459160

[6] WATKINSON, John. The Engineers Guide to Motion Compensation [online]. Snell & Wilcox, 1994 [cit. 2006-03-18] Dostupný z WWW: http://www.snellwilcox.com/community/knowledge_center/ engineering_guides/emotion.pdf

71

[7] MATSUSHITA, Y.; OFEK, E.; TANG, X.; SHUM, H.-Y. Full-frame Video Stabilization [online]. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR05), 2005 [cit. 2006-05-13]. Dostupný z WWW: http://research.microsoft.com/users/yasumat/ publications/fullframe_cvpr05.html

[8] PIVA, S.; ZARA, M.; GERA, G.; REGAZZONI, C. S. Color-Based Video Stabilization for Real-Time On-Board Object Detection on High-Speed Trains [online]. IEEE Conference on Advanced Video and Signal Based Surveillance (AVSS’03), 2003 [cit. 2006-05-13]. Dostupný z WWW: http://doi.ieeecomputersociety.org/ 10.1109/AVSS.2003.1217935

[9] McREYNOLDS, D.; SHENG, Y.; GAGNON, L.; SEVIGNY, L. Stabilization of Infrared Image Sequence with Rotation, Scaling and View Angle Changes [online]. International Conference on Applications of Photonic Technology, Ottawa, 1998 [cit. 2006-05-13]. Dostupný z WWW: http://citeseer.ist.psu.edu/29686.html

[10] BEN-EZRA, Moshe; PELEG, Shmuel, WERMAN, Michael. A Real-Time Video Stabilizer with Linear-Programming [online]. IEEE Computer Society Conference on Computer Vision, 1999 [cit. 2006-05-14]. Dostupný z WWW: http://vast.uccs.edu/~tboult/FRAME/Ben_Ezra/frame.pdf

[11] BIKRAMADITYA B.; KWON, O.; SAI, S. K. T. V.; RYU, B.; PAIK, J. Reconfigurable VLSI architecture design for real time image stabilization [online].

72

Electronic Journal Technical Acoustics, 2006 [cit. 2006-05-14]. Dostupný z WWW: http://ejta.org/en/bibhuti1

[12] KWON, Ohyun; SHIN, Jeongho; PAIK, Joonki. Video Stabilization Using Kalman Filter and Phase Correlation Matching [online]. International Conference on Image Analysis and Recognition, 2005 [cit. 2006-05-11]. Dostupný z WWW: http://springerlink.metapress.com/content/ 5kgbm422g91u/?sortorder=asc&p_o=10

[13] PAIK, Joon Ki; PARK, Yong Chul. An edge detection approach to digital image stabilization based on tri-state adaptive linear neurons [online]. IEEE International Conference on Consumer Electronics, 1991 [cit. 2006-08-20]. Dostupný z WWW: http://ipis.cau.ac.kr/publications/journal.htm

[14] PAIK, Joon Ki; PARK, Yong Chul; KIM, Dong Wook. An adaptive motion decision system for digital image stabilizer based on edge pattern matching [online]. IEEE International Conference on Consumer Electronics, 1992 [cit. 2006-05-11] Dostupný z WWW: http://ipis.cau.ac.kr/publications/journal.htm

[15] MEYER, John. A guide to using deshaker [online]. 2004 [cit. 2006-08-20]. Dostupný z WWW: http://www.sundancemediagroup.com/ articles/deshaker_guide.htm

[16] THALIN, Gunar. Deshaker – video stabilizer [online]. 2006 [cit. 2006-03-18]. Dostupný z WWW: http://www.guthspot.se/video/deshaker.htm

73

[17] Wikipedia contributors. Steadicam [online]. Wikipedia, The Free Encyclopedia, 2006 [cit. 2006-08-23]. Dostupný z WWW: http://en.wikipedia.org/wiki/Steadycam

[18] Wikipedia contributors. Camera dolly [online]. Wikipedia, The Free Encyclopedia, 2006 [cit. 2006-08-23]. Dostupný z WWW: http://en.wikipedia.org/wiki/Camera_dolly

[19] Steadicam [online]. The Tiffen Company LLC., 2005 [cit. 2006-08-23]. Dostupný z WWW: http://www.steadicam.com/handheldSteadicamJR.html

[20] LEE, Johnny Chung. $14 Steadycam – The Poor Mans Steadicam [online]. 2006 [cit. 2006-08-22]. Dostupný z WWW: http://www.cs.cmu.edu/~johnny/steadycam/

[21] Build your own steadycam [online]. wilbosoft-systems, 2001 [cit 2006-08-22]. Dostupný z WWW: http://www.bohlen.com.au/steadycam.htm

[22] BOCKAERT, Vincent. Image Stabilization [online]. Digital Photography Review, 2006 [cit. 2006-08-22]. Dostupný z WWW: http://www.dpreview.com/learn/?/key=image+stabilization

[23] BOCKAERT, Vincent. Anti-shake [online]. Digital Photography Review, 2006 [cit. 2006-08-22]. Dostupný z WWW: http://www.dpreview.com/learn/?/key=anti-shake

74

[24] ROWE, Robin. The Linux Motion Picture Pipeline [online]. Linux Movies Group, poslední aktualizace 9. října 2005 [cit. 2006-08-23]. Dostupný z WWW: http://linuxmovies.org/software.html

[25] Mokey [online]. Imagineer Systems Limited, 2006 [cit. 2006-08-23]. Dostupný z WWW: http://www.mokey.com/products/mokey/

[26] 2d3 – SteadyMove [online]. 2D3 LIMITED, 2006 [cit. 2006-08-23]. Dostupný z WWW: http://www.2d3.com/html/products/steadymove_overview.html

[27] VirtualDub [online]. Avery Lee, 2006 [cit. 2006-08-23]. Dostupný z WWW: http://www.virtualdub.org/

[28] Wikipedia contributors. Image stabilization [online]. Wikipedia, The Free Encyclopedia, 2007 [cit. 2007-05-01]. Dostupný z WWW: http://en.wikipedia.org/wiki/Image_stabilization

[29] Wikipedia contributors. Vibration Reduction [online]. Wikipedia, The Free Encyclopedia, 2007 [cit. 2007-05-01]. Dostupný z WWW: http://en.wikipedia.org/wiki/Vibration_Reduction

[30] Stabilizace obrazu [online]. AZ FOTO, 2007 [cit. 2007-05-01]. Dostupný z WWW: http://www.azfoto.cz/_web/_informace/ digital_pod_lupou_stabilizace.php

75

[31] Lék na rozmazané fotky: Stabilizátor obrazu, nebo je lepší stativ? [online]. PĚNKAVA, Jan; HERWIG, Bohumil, 2006 [cit. 2007-05-01]. Dostupný z WWW: http://technet.idnes.cz/ tec_foto.asp?r=tec_foto&c=A051220_164919_tec_foto_psp

[32] Vyplatí se koupit fotoaparát se stabilizátorem? [online]. LIBICH, Jan, 2007 [cit. 2007-05-01]. Dostupný z WWW: http://technet.idnes.cz/ tec_foto.asp?c=A070403_202217_tec_foto_vse

[33] Stabilizátor obrazu – marketingový klam nebo užitečné zařízení? [online]. DOLEJŠÍ, Tomáš, 22. září 2006 [cit. 2007-05-01]. Dostupný z WWW: http://www.fotoradce.cz/stabilizator-obrazu.php

[34] DirectShow and C#: The final frontier [online]. Informikon, 2006 [cit. 2007-05-01]. Dostupný z WWW: http://www.informikon.com/directshow-tutorials/ directshow-and-c-the-final-frontier--.html

[35] DirectShowNet Library [online]. Kolektiv autorů, 2005 [cit. 2007-05-01]. Dostupný z WWW: http://directshownet.sourceforge.net/

[36] Fast Block Matching Algorithm Based on the Winner-Update Strategy [online]. Kolektiv autorů, 2005 [cit. 2008-05-03]. Dostupný z WWW: http://www.cs.nctu.edu.tw/~yschen/papers/TIP01-winup.pdf

76