(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ů. Úlohu vypracujte v Matlabu nabo Pythonu. Můžete využít templaty pro Matlab a Python.

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:

1. 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.
2. 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.

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:

1. 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ů.

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ř. 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<m$ a minimalizují chybu \eqref{eq:obj}.

Úkoly:

1. Stáhněte si data (tanec Macarena nastudujte zde). Každý soubor obsahuje jednu matici $\_A$, nahrajete ji příkazem A=load('soubor.txt')' (pozor na transpozici). Pro vizualizaci sekvencí použijte příkaz playmotion(conn,A) (vyžaduje funkci playmotion.m a soubor connected_points.txt, který nahrajete příkazem conn=load('connected_points.txt')). Toto, i ekvivalent v pythonu je implementováno v templatech.
   Výstup úkolu: nic.
2. Aproximujte sekvenci příkazem [U,C,b0]=fitaff(A,k) pro různě zvolená $k\in\{1,\dots,m\}$, aproximovaná sekvence je pak dána vzorcem \eqref{eq:coords-aff}. Obě sekvence zároveň si přehrajte příkazem playmotion(conn,A,B). Pokud máte vše správně, sekvence si budou podobné. Zkoušejte, jak se mění kvalita aproximace pro různá $k$ a různé sekvence. Dumejte, proč se některé sekvence lépe komprimují (stačí menší $k$) než jiné.
   Výstup úkolu: nic.
3. Nahrazení sekvence $\_a_1,\dots,\_a_n$ sekvencí $\_c_1,\dots,\_c_k$ může mít i jiné výhody než kompresi: protože druhá sekvence 'žije' v prostoru nižší dimenze, dá se např. snadněji zobrazit (vizualizace dat) či rozpoznat z ní typ pohybu herce (pattern recognition). Zkuste si to: pro $k\in\{2,3\}$ si zobrazte trajektorii bodu $\_c_i$ v rovině jako funkci času $i$, kde po sobě jdoucí body spojíte úsečkami (použijte příkaz plot příp. plot3; pro $k=3$ si na matlabském okně s obrázkem zvolte rotaci a točte si 3-D grafem v prostoru). Všimněte si, jak se trajektorie liší pro různé vstupní sekvence (walk1, makarena1, …). Implementujte funkci plottraj2(C) se vstupem $\_C\in\R^{2\x n}$, která zobrazí tuto trajektorii pro $k=2$.
   Výstup úkolu: soubor plottraj2.m.
4. Chceme spočítat optimální chybu aproximace \eqref{eq:obj} pro všechny dimenze $k=1,\dots,m$ afinního podprostoru. Dostaneme tedy čísla $d_1,\dots,d_m$, kde $d_k$ je chyba aproximace pro dimenzi $k$. Implementujte funkci d=erraff(A), která pro sekvenci $\_A\in\R^{m\x n}$ spočítá tato čísla a uloží je do vektoru $\_d\in\R^m$ (funkce nemá nic vypisovat ani vykreslovat). Ve funkci erraff smíte zavolat matlabskou funkci eig příp. svd jen jednou. V BRUTE je jeden test na matici asi $1000 \times 1000$, funkce musí být dost rychlá, aby to stihla.
   Výstup úkolu: soubor erraff.m.