\chyph \hoffset=-1cm \voffset=-1.2cm \hsize=18cm \ifx\pdfoutput\undefined \else \pdfpagewidth=21cm \pdfpageheight=15cm \fi \font\logocvut=lev scaled400 \ifx\zkratka\undefined\edef\zkratka{\jobname}\fi \def\cislo{13} \headline={\setfonts[/10]\rm \ifnum\pageno>1 \hfill {\setfonts[/7] BI-LIN, \zkratka, \cislo, P. Olšák \quad}\else \firstpage\hfill\fi [\the\pageno]} \footline={} \def\firstpage{\vbox to0pt{\kern13.7cm\hbox{% \setfonts[/8] a) \zkratka, \cislo, b) P. Olšák, FEL ČVUT, c) P. Olšák 2010, d) BI-LIN, e) L, f) 2009/2010, g) \lower1pt\hbox{\logocvut L}. Viz p. d. 4/2010 }\vss}} \input ofs [a35] %\def\fomenc{CM} %\showfonts \end %\displayfontmessages \setfonts[NewCentury/17] \setmath[17/12/8] \baselineskip=22pt \normalbaselineskip=\baselineskip \message{\fontname\tenit} \medskipamount=9pt \let\ms=\medskip \parskip=\medskipamount \def\n#1\par{\vfill\break} \def\g#1\par{{\null \vskip-31pt \baselineskip=30pt\setfonts[/23]\bf #1\par}\medskip} \def\gg#1\par{{\setfonts[/55]\bf #1}\medskip} \def\hb{\hfil\break} \def\emerge{{\emergencystretch=2em\par}} \parindent=0pt \catcode`\*=13 \def* {\par \hangindent=15pt \hangafter=1 \noindent \hbox to\hangindent {$\bullet$\hss}} \let\em=\it \def\C{{\bf C}} \def\R{{\bf R}} \def\Q{{\bf Q}} \def\a{{A}} \def\A{{\bf A}} \def\B{{\bf B}} \def\D{{\bf D}} \def\E{{\bf E}} \def\P{{\bf P}} \def\L{{\bf L}} \def\U{{\bf U}} \def\X{{\bf X}} \def\ker{\mathop{\rm Ker}} \def\st{\mathop{\rm St}} \def\hod{\mathop{\rm hod}} \def\vecc #1_#2{\vec#1_1, \vec#1_2, \ldots, \vec#1_{#2}} \def\lob<#1>{\langle #1\rangle} % =============================================================== \vglue .5cm \gg Afinní \gg transformace \bigskip\bigskip * je posunutí plus lineární transformace * má svou matici vzhledem k homogenním souřadnicím * využití například v počítačové grafice \n --------------------------------------------------------------- \g Idea afinního prostoru * Lineární prostor $V$ volných vektorů: dvě orientované úsečky reprezentují stejný volný vektor, pokud jsou rovnoběžné, stejně velké a stejně orientované. * Sčítání a násobení konstantou v lineárním prostoru $V$ provedeme pomocí vhodně zvolených reprezentatnů stejně jako v $U_O$. * Kromě vektorů z $V$ budeme v afinním prostoru pracovat s množinou bodů $\X$. Nové operace: * bod1 $+$ vektor = bod2. \ Na bod1 navážeme reprezentanta vektoru a koncový bod tohoto vektoru je výsledek operace. * bod1 $-$ bod2 = vektor. \ Výsledkem je vektor s reprezentantem, který má počáteční bod2 a koncový bod1. \n --------------------------------------------------------------- \g Definice afinního prostoru {\bf Definice}: Nechť $V$ je lineární prostor a $\X$ je libovolná množina. Dvojici množin $(\X,V)$ nazýváme {\em afinní prostor}, pokud kromě operací $+$ a $\cdot$ na $V$ je definována operace $+: \X\times V\to \X$ s vlastnostmi: $$ \eqalign{ (1)\ \ & P + \vec o = P \qquad \hbox{$\forall\ P\in\X$ \ ($\vec o\in V$ je nulový vektor)},\cr (2)\ \ & (P + \vec u) + \vec v = P + (\vec u+\vec v) \qquad \hbox{$\forall\ P\in\X$, $\vec u\in V$, $\vec v\in V$}, \cr (3)\ \ & \hbox{$\forall\ P\in\X$, $Q\in\X$ existuje jediný $\vec u\in V$ tak, že}\quad P = Q + \vec u } $$ Vektor $\vec u$ z vlastnosti (3) značíme $P-Q$ nebo $\vec{QP}$. Množina $\X$ a lineární prostor $V$ mohou být jakékoli takové, aby šlo definovat operaci $+$ s uvedenými vlastnostmi. Dobrá a postačující představa afinního prostoru je lineární prostor~$V$ volných vektorů a množina $\X$ bodů. \n ----------------------------------------------------------- \g Souřadnicový systém afinního prostoru Dimenze afinního prostoru je dimenze lineárního prostoru $V$. Nadále budeme předpokládat afinní prostory s konečnou dimenzí (zejména s dimenzí 3 nebo 2). Zvolme bázi $(B)$ prostoru $V$ a dále bod $O\in\X$. Dvojici $(O,B)$ nazýváme souřadnicovým systémem afinního prostoru. Vektor $\vec u\in V$ má souřadnice vzhledem k $(O,B)$ definovány jako jeho souřadnice vzhledem k bázi $(B)$. Bod $P\in\X$ má souřadnice vzhledem k $(O,B)$ definovány jako souřadnice vektoru $\vec{OP}$. Tomuto vektoru říkáme {\em radiusvektor bodu~$P$}. \n ------------------------------------------------------- \g Vlastnosti souřadnic v afinním prostoru Nechť $C$ je zobrazení souřadnic, $\vec u, \vec v\in V$, $P, Q\in \X$, $\alpha\in\R$. Pak $$ \def\c{C} \eqalign { (1)\ \ & \c(\vec u+\vec v) = \c(\vec u) + \c(\vec v) \cr (2)\ \ & \c(\alpha\cdot\vec u) = \alpha\cdot\c(\vec u) \cr (3)\ \ & \c(Q+\vec u) = \c(Q) + \c(\vec u) \cr (4)\ \ & \c(P-Q) = \c(P) - \c(Q) \cr } $$ Důkaz: (1) a (2): jsou to obvyklé souřadnice vektoru. (3), (4): stačí souřadnice bodů vyjádřit jako souřadnice jejich radiusvektorů. \n ---------------------------------------------------- \g Homogenní souřadnice Nechť má afinní prostor dimenzi $n$. {\em Homogenní souřadnice vektoru} v souřadnicovém systému $(O,B)$ je uspořádaná \hbox{$(n+1)$}-tice; prvních $n$ složek obsahuje souřadnice vektoru, poslední složka obsahuje nulu. {\em Homogenní souřadnice bodu} v souřadnicovému systému $(O,B)$ je uspořádaná \hbox{$(n+1)$}-tice; prvních $n$ složek obsahuje souřadnice bodu, poslední složka obsahuje jedničku. {\bf Pozorování:} Tvrzení z předchozí strany [5] o souřadnicích platí i v~případě, že $C$ značí homogenní souřadnice. \n ------------------------------------------------------- \g Matice v homogenních souřadnicích Zobrazení $\a:\X\to\X$, pro které existuje matice $\A\in\R^{n+1,n+1}$ s~vlastností: $$ \A\cdot\pmatrix{\hbox{homogenní}\cr\hbox{souřadnice}\cr\hbox{bodu }P\cr \hbox{vzhledem}\cr\hbox{k $(O,B)$}} = \pmatrix{\hbox{homogenní}\cr\hbox{souřadnice}\cr\hbox{bodu }\a(P)\cr \hbox{vzhledem}\cr\hbox{k $(O,B)$}} $$ se nazývá transformace s maticí $\A$ v homogenních souřadnicích. {\bf Pozorování:} Matice $\A$ musí být tvaru: $$ \A = \pmatrix {\A' & {\bf t}\cr {\bf o} & 1} $$ kde $\A'\in\R^{n,n}$, ${\bf t}\in\R^{n,1}$, ${\bf o}\in\R^{1,n}$ je nulový vektor. \n ---------------------------------------------------- \g Vlastnosti matice \vskip-.5\baselineskip \g v homogenních souřadnicích $$ \pmatrix {\A' & {\bf t}\cr {\bf o} & 1}\cdot \pmatrix{{\bf p}\cr 1} = \pmatrix{\A'\cdot {\bf p} + {\bf t}\cr 1} $$ tj. bod je transformován lineární transformací s maticí $\A'$ a následně posunut o ${\bf t}$. $$ \pmatrix {\A' & {\bf t}\cr {\bf o} & 1}\cdot \pmatrix{{\bf u}\cr 0} = \pmatrix{\A'\cdot {\bf u}\cr 0} $$ tj. vektor je pouze transformován lineární transformací s maticí~$\A'$. \n ----------------------------------------------------- \g Příklad 2D Obecná matice transformace v homogenních souřadnicích má tvar: $$ \pmatrix {a&b&c\cr d&e&f\cr 0&0&1}. $$ Je tedy určena šesti parametry. Bod se souřadnicemi $(x,y)$ přejde při transformaci s touto maticí na bod se souřadnicemi $(x',y')$: $$ \pmatrix {x'\cr y'\cr 1} = \pmatrix {a&b&c\cr d&e&f\cr 0&0&1} \cdot \pmatrix {x\cr y\cr 1} = \pmatrix {ax + by + c\cr dx + ey + f\cr 1}, $$ takže bod se transformuje lineárně a posune o vektor $(c,f)$. \n -------------------------------------------------- \g Příklad 3D Obecná matice transformace v homogenních souřadnicích má tvar: $$ \pmatrix {a&b&c&d\cr e&f&g&h\cr i&j&k&l\cr 0&0&0&1}. $$ Je určena dvanácti parametry. Transformace bodu probíhá podle následujícího vzorce: $$ \pmatrix {x'\cr y'\cr z'\cr1} = \pmatrix {a&b&c&d\cr e&f&g&h\cr i&j&k&l\cr 0&0&0&1} \cdot \pmatrix {x\cr y\cr z\cr1} = \pmatrix {ax+by+cz+d\cr ex+fy+gz+h\cr ix+jy+kz+l\cr 1} $$ \n ------------------------------------------------ \g Skládání transformací --- součin matic {\bf Věta}: Nechť $\A$ a $\B$ jsou matice transformací $A$ a $B$ v homogenních souřadnicích $$ \A = \pmatrix {\A' & {\bf t}\cr {\bf o} & 1}, \qquad \B = \pmatrix {\B' & {\bf s}\cr {\bf o} & 1} $$ Pak složená transformace $B\circ A$ má matici: $$ \B\cdot\A = \pmatrix {\B' & {\bf s}\cr {\bf o} & 1} \cdot \pmatrix {\A' & {\bf t}\cr {\bf o} & 1} = \pmatrix {\B'\cdot\A'& \B'\cdot{\bf t} + {\bf s}\cr {\bf o} & 1}. $$ {\bf Poznámka}: Je $(B\circ A)(x) = (B(A(x))$. Důkaz věty se provede analogicky, jako důkaz věty o složeném lineárním zobrazení. \n ------------------------------------------------ \g Inverzní transformace --- inverzní matice {\bf Věta:} Má-li transformace $A$ regulární matici $\A$ v homogenních souřadnicích, pak je prostá a na a $A^{-1}$ má matici $\A^{-1}$ v homogenních souřadnicích. {\bf Pozorování}: $$ \hbox{Je-li}\quad \A = \pmatrix {\A' & {\bf t}\cr {\bf o} & 1},\quad \hbox{pak}\quad \A^{-1} = \pmatrix {(\A')^{-1} & -\,(\A')^{-1}\,{\bf t}\cr {\bf o} & 1} $$ Inverzní matice k $\A$ existuje, právě když $\A'$ je regulární. \n ------------------------------------------------ \g Příklad: elementární transformace ve 2D {\bf Změna měřítka} má matici v homogenních souřadnicích: $$ \pmatrix {a& 0&0\cr 0&b&0\cr 0&0&1}. $$ {\bf Rotace} o úhel $\alpha$ má matici v homogenních souřadnicích: $$ \pmatrix {\cos\alpha& -\sin\alpha&0\cr \sin\alpha&\phantom+\cos\alpha&0\cr 0&0&1}, $$ {\bf Posunutí} o vektor se souřadnicemi $(t_x, t_y)$ má matici v homogenních souřadnicích: $$ \pmatrix {1&0& t_x\cr 0&1&t_y\cr 0&0&1} $$ Další transformace vznikají skládáním těchto transformací. \n ----------------------------------------------------- \g Příklad Najdeme matici (v homogenních souřadnicích) rotace o úhlel $\alpha$ kolem bodu $(2,3)$. Uvedená transformace je složením následujících transformací: * posunutí o vektor $(-2,3)$, * rotace o úhel $\alpha$, * posunutí o vektor $(2,3)$. Matice výsledné transformace je součinem matic: $$ \displaylines { \biggl( \hbox{posunutí o $(2,3)$} \biggr) \cdot \biggl( \hbox{rotace o úhel $\alpha$} \biggr) \cdot \biggl( \hbox{posunutí o $(-2,-3)$} \biggr) =\cr \noalign{\bigskip} = \pmatrix {1&0& 2\cr 0&1&3\cr 0&0&1} \cdot \pmatrix {\cos\alpha& -\sin\alpha&0\cr \sin\alpha&\phantom+\cos\alpha&0\cr 0&0&1} \cdot \pmatrix {1&0& \!-2\cr 0&1&\!-3\cr 0&0&1} = \ \cdots } $$ \n ------------------------------------------------------- \g Příklad, pokračování $$ \cdots \ = \pmatrix {\cos\alpha& -\sin\alpha\ & -2\cos\alpha+3\sin\alpha+2\cr \sin\alpha&\phantom+\cos\alpha\ &-2\sin\alpha-3\cos\alpha+3\cr 0&0&1}. $$ Takže bod o souřadnicích $(x,y)$ přechází po této transformaci na bod o souřadnicích $(x'y')$, pro který platí: $$ \displaylines { \pmatrix {x'\cr y'\cr 1} = \pmatrix {\cos\alpha& -\sin\alpha\ & -2\cos\alpha+3\sin\alpha+2\cr \sin\alpha&\phantom+\cos\alpha\ &-2\sin\alpha-3\cos\alpha+3\cr 0&0&1} \cdot \pmatrix {x\cr y\cr 1} = \cr \noalign{\bigskip} = \pmatrix {(\cos\alpha)\,x -(\sin\alpha)\,y -2\cos\alpha+3\sin\alpha+2\cr (\sin\alpha)\,x +(\cos\alpha)\,y -2\sin\alpha-3\cos\alpha+3\cr1} } $$ \n -------------------------------------------------------- \g Afinní transformace {\bf Definice}: Nechť $(\X,V)$ je afinní prostor. Transformace $\a:\X\to\X$ se nazývá {\em afinní}, pokud existuje lineární transformace $\a':V\to V$ tak, že $$ \a(P+\vec u) = \a(P) + \a'(\vec u) \qquad \forall\ P\in\X, \vec u\in V. $$ Zvolme bod $O\in\X$. Protože pro každý $P\in\X$ platí $P = O+\vec{OP}$, je $\a(P) = \a(O) + \a'(\vec{OP})$, takže každá afinní transformace je jednoznačně určena hodnotou $\a(O)$ a lineární transformací $\a': V\to V$. Protože každá lineární transformace $\a': V\to V$ je jednoznačně určena hodnotami na bázi $(B) = (\vecc b_n)$, je každá afinní transformace jednoznačně určena hodnotami v $n+1$ bodech: $$ O, \quad O+\vec b_1, \quad O+\vec b_2, \quad \ldots, \quad O+\vec b_n. $$ \n --------------------------------------------------------- \g Matice afinní transformace je její matice v homogenních souřadnicích. Je třeba ukázat: * Každá transformace, která má matici v homogenních souřadnicích, je afinní. * Každá afinní transformace má matici v homog. souřadnicích. Puntík první: Je dána matice $\A$ nějaké transformace v homogenních souřadnicích vzhledem k $(O,B)$. Matice hledaného zobrazení $\a'$ je také matice $\A$. Jsou-li ${\bf p}$ souřadnice bodu $P\in\X$ a ${\bf u}$ souřadnice vektoru $\vec u\in V$, pak $$ \A\cdot \pmatrix{{\bf p}+{\bf u}\cr 1} = \A\cdot \pmatrix{{\bf p}\cr 1} + \A\cdot \pmatrix{{\bf u}\cr 0}. $$ Puntík druhý: Hledaná matice obsahuje ve sloupcích homogenní souřadnice obrazů báze následované homogenními souřadicemi obrazu bodu $O$. Taková matice určuje hodnoty afinní transformace na bodech $O$, $O+\vec b_i$, takže určuje afinní transformaci jednoznačně. \n ---------------------------------------------------------- \g Vlastnosti afinní transformace * Skládání afinních transformací je afinní transformace * Afinní transformace je prostá právě když je na právě když má regulární matici v homogenních souřadnicích. * Je-li afiní transformace prostá, pak její inverze je také afiní transformace. * Prostá afinní transformace zobrazuje rovnoběžné přímky na rovnoběžné přímky. \n ------------------------------------------------------- \g Příklad Je dána afinní tansformace ve 2D prostoru taková, že posune počátek souřadnicového systému do bodu $(3,2)$ a transformuje první bázový vektor na vektor se souřadnicemi $(-1,2)$, druhý bázový vektor transformuje na vektor se souřadnicemi $(4,1)$. Najdeme matici v homogenních souřadnicích této transformace. Podle předchozího matice obsahuje homogenní souřadnice obrazů báze a v posledním sloupci homogenní souřadnice obrazu počátku. Tedy $$ \A = \pmatrix {-1 & 4& 3\cr \phantom+2& 1& 2\cr \phantom+0& 0& 1}. $$ Pronásobíme-li pixelové souřadnice každého pixelu touto maticí, dostáváme pixelové souřadnice obazu: maticovým násobením můžeme tansformovat dvourozměrný obrázek. \end