\[ \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*}} \]
(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:
[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}. fitlin.m
.
[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}. fitaff.m
.
Poznámky:
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:
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
). drawfitline.m
. plot
, hold on
, hold off
. Po vykreslení zavolejte příkaz axis equal
, aby měřítko obou os bylo stejné.
figure
ani close
).
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:
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.[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é. 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$. plottraj2.m
.
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. erraff.m
.