\[ \def\_#1{\mathbf{#1}} \def\x{\times} \def\R{\mathbb{R}} \def\mat#1{\begin{bmatrix}#1\end{bmatrix}} \def\matr#1{\begin{bmatrix*}[r]#1\end{bmatrix*}} \] ===== PCA: Motion Capture ===== (T.Werner, V.Franc 2014+, V.Voráček) Tato domácí úloha má tři podúlohy. Zadání se může zdát dlouhé, ale každou požadovanou funkci lze napsat na pár řádků. /* Výstupem domácí úlohy budou ''.m'' soubory a zpráva (společná pro všechny podúlohy) v PDF. Ve zprávě nemusí být nic víc, než co je požadováno v zadání. */ Úlohu vypracujte v Matlabu nabo Pythonu. Můžete využít templaty pro {{./matlab_template_mocap.zip|Matlab}} a {{./python_template_mocap.zip|Python}}. ==== 1. Proložení bodů podprostorem ==== Jsou dány body $\_a_1,\ldots,\_a_n\in\R^m$ a přirozené číslo $k\le m$. Najděte body $\_b_1,\ldots,\_b_n\in\R^m$ takové, aby ležely v (lineárním) podprostoru dimenze $k$ prostoru $\R^m$ a byly co nejblíže bodům $\_a_1,\ldots,\_a_n$ ve smyslu nejmenších čtverců, tj. minimalizovaly výraz \begin{equation} \sum_{i=1}^n\|\_a_i-\_b_i\|^2. \label{eq:obj} \end{equation} Zdůrazněme, že zmíněný podprostor předem neznáme, máme ho najít zároveň s body $\_b_1,\ldots,\_b_n$. Tento podprostor budeme reprezentovat jeho ortonormální bází $\_u_1,\ldots,\_u_k\in\R^m$. Dále máme najít souřadnice $c_{11},\ldots,c_{kn}$ nalezených bodů $\_b_1,\ldots,\_b_n$ v této bázi, tedy \begin{equation} \_b_j = \sum_{i=1}^k c_{ij}\_u_i = \_U\_c_j \qquad\forall j=1,\dots,n \label{eq:coords} \end{equation} kde $\_U\in\R^{m\x k}$ je matice se sloupečky $\_u_1,\ldots,\_u_k$ (splňující $\_U^T\_U=\_I$) a $\_c_j\in\R^k$ je vektor s prvky $c_{1j},\dots,c_{kj}$. Někdy řešíme pozměněnou úlohu: k daným bodům $\_a_1,\ldots,\_a_n\in\R^m$ hledáme body $\_b_1,\ldots,\_b_n\in\R^m$, které leží v //afinním// podprostoru dimenze $k$ a minimalizují chybu \eqref{eq:obj} Pak místo \eqref{eq:coords} máme \begin{equation} \_b_j = \_b_0 + \_U\_c_j \qquad\forall j=1,\dots,n , \label{eq:coords-aff} \end{equation} kde $\_b_0\in\R^m$ je (neznámé) posunutí afinního podprostoru vůči počátku. Nahrazení sekvence $\_a_1,\ldots,\_a_n$ sekvencí $\_c_1,\dots,\_c_n$ lze vnímat jako kompresi dat: druhá sekvence obsahuje typicky daleko méně čísel než první (velikost báze $\_U$ je zanedbatelná). Je výhodné uspořádat vektory $\_a_1,\ldots,\_a_n\in\R^m$, $\_b_1,\ldots,\_b_n\in\R^m$, $\_c_1,\ldots,\_c_n\in\R^k$ do sloupců matic $\_A\in\R^{m\x n}$, $\_B\in\R^{m\x n}$, $\_C\in\R^{k\x n}$. Pak účelovou funkci \eqref{eq:obj} můžeme napsat jako $\|\_A-\_B\|^2$ (kde $\|\cdot\|$ je zde Frobeniova norma) a rovnici \eqref{eq:coords} příp. \eqref{eq:coords-aff} jako $\_B = \_U\_C$ příp. $\_B=\_b_0\_1^T+\_U\_C$. **Úkoly:** /* - Nastudujte příslušnou látku z přednášek. Navrhněte řešení popsaných úloh (včetně vzorce pro matici $\_C$). \\ **Výstup úkolu** (do zprávy): popis algoritmu a jeho odůvodnění */ - Implementujte matlabskou funkci ''[U,C]=fitlin(A,k)'', jejímž vstupem je matice $\_A$ a číslo $k$ a výstupem jsou matice $\_U$ a $\_C$, které minimalizují \eqref{eq:obj} za podmínky \eqref{eq:coords}. \\ **Výstup úkolu**: soubor ''fitlin.m''. - Implementujte funkci ''[U,C,b0]=fitaff(A,k)'', jejímž vstupem je matice $\_A$ a číslo $k$ a výstupem jsou matice $\_U,\_C$ a vektor $\_b_0$, které minimalizují \eqref{eq:obj} za podmínky \eqref{eq:coords-aff}. \\ **Výstup úkolu**: soubor ''fitaff.m''. Poznámky: * Předpokládejte, že nejen $k\le m$ ale i $k\le n$. * Neměli byste nikde vytvořit matici rozměru $n\x n$, protože počet bodů $n$ může být veliký. * Implementované funkce nemají nic vypisovat ani vykreslovat, mají jen vrátit požadovaný výstup. * Smíte používat jen základní funkce Matlabu (tedy žádné toolboxy), viz stránka cvičení. * Funkci ''fitlin'' lze napsat na 4 řádky, funkci ''fitaff'' na 3 řádky. ==== 2. Proložení bodů přímkou ==== Nyní použijete výsledek výše na prokládání množiny bodů v rovině přímkou ($m=2$ a $k=1$), která nemusí procházet počátkem. Představte si např., že někdo body naklikal myší v grafickém rozhraní (to můžete udělat v Matlabu sami příkazem ''ginput'') a vaším úkolem je proložit jimi nejlepší přímku. **Úkoly:** - Implementujte funkci ''drawfitline(A)'', která má na vstupu matici $\_A\in\R^{2\x n}$ se zadanými body a nakreslí optimální přímku zeleně, body $\_a_1,\dots,\_a_n$ jako červené křížky, a $n$ červených úseček kde $i$tá úsečka spojuje bod $\_a_i$ s bodem $\_b_i$. Funkci si můžete vyzkoušet na matici $\_A$ v souboru {{./line.mat}} (nahrajete ho příkazem ''load line''). \\ **Výstup úkolu**: soubor ''drawfitline.m''. \\ Poznámky: * Uvědomte si, že místo přímky musíte vlastně nakreslit úsečku (protože přímka je nekonečná a na obrazovku se nevejde) a tedy musíte nějak rozumně zvolit koncové body této úsečky. * Pro vykreslení použijte příkazy ''plot'', ''hold on'', ''hold off''. Po vykreslení zavolejte příkaz ''axis equal'', aby měřítko obou os bylo stejné. * Uvnitř funkce neotvírejte ani nezavírejte matlabský obrázek (tj. nevolejte funkce ''figure'' ani ''close''). * Funkci lze napsat do 15 řádků. /* - Nalezněte požadovanou přímku pro body ze souboru ''line.mat'' ve dvou různých reprezentacích: \begin{equation}\{\, \_b_0+\_uc \mid c\in \R \,\} = \{\,\_b\in\R^2\mid \_x^T\_b = y \,\}. \end{equation} Vektory zvolte tak, aby $\|\_x\|=\|\_u\|=1$ a aby norma $\|\_b_0\|$ byla nejmenší možná (tj. aby $\|\_b_0\|$ byla vzdálenost přímky od počátku $\_0$). \\ **Výstup úkolu** (do zprávy): teoretický postup, vektory $\_b_0,\_u,\_x\in\R^2$ a skalár $y\in\R$. */ ==== 3. Komprese a analýza sekvence z motion capture ==== Při tvorbě počítačových her nebo filmů se používá technologie //motion capture//. Na živého herce se připevní terčíky odrážející infračervené světlo. Terčíky se připevňují na významné body na těle, jako klouby apod. Speciální soustava kamer snímají polohy terčíků a z těch se počítá poloha každého terčíku v třírozměrném prostoru pro každý snímek. Polohy terčíků v prostoru se pak použijí např. pro animaci postav syntetizovaných počítačovou grafikou. Viz např. [[http://en.wikipedia.org/wiki/Motion_capture|wikipedie]]. Pro získání plynulého pohybu je třeba snímat s vysokou frekvencí. Například data použitá v naší úloze byla snímána s vzorkovací frekvencí 120 Hz. Ve výsledku je pak třeba pracovat s velkými objemy dat. Naším úkolem bude snížit objem dat tak, abychom sejmuté body poškodili co nejméně. Prostorová poloha jednoho terčíku v jednom snímku je dána trojicí souřadnic. V našem případě máme $\ell=41$ terčíků. Poloha všech terčíků v jednom snímku je dána vektorem $\_a\in\R^m$ kde $m=3\ell$. Ten si lze představit jako bod v $m$-rozměrném prostoru. Celkově máme $n$ snímků, tedy vektory $\_a_1,\ldots,\_a_n\in\R^m$. Hledáme body, které co nejlépe aproximují původní body a zároveň se dají reprezentovat menším objemem dat. Přesněji, hledáme body $\_b_1,\ldots,\_b_n$, které leží v afinním podprostoru dané dimenze $k