Search
\[ \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+)
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í. Zabalte soubory .pdf a .m do souboru .zip (bez podadresářů) a nahrajte do Brute. Podpůrné funkce a data nemusíte do zipu přidávat.
.m
.pdf
.zip
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 nějakém (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 je také neznámý, 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}$ (pozor: ve skriptech jsme je dávali do řádků). 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)
fitlin.m
[U,C,b0]=fitaff(A,k)
fitaff.m
Poznámky:
fitlin
fitaff
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.
ginput
drawfitline(A)
load line
drawfitline.m
plot
hold on
hold off
axis equal
figure
close
line.mat
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, což je nevýhoda. Naším úkolem bude snížit objem dat tak, abychom ztratili co nejméně informace.
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}.
A=load('soubor.txt')
playmotion(conn,A)
connected_points.txt
conn=load('connected_points.txt')
playmotion(conn,A,B)
plot3
walk1, makarena1, …
plottraj2(C)
plottraj2.m
d=erraff(A)
erraff
eig
svd
erraff.m