V´ ypoˇ cet transformaˇ cn´ıch koeficinet˚ u vybran´ ych 2D transformac´ı Jan Jeˇzek ˇcerven 2008
Obsah 1 Odvozen´ı transformaˇ cn´ıho kl´ıˇ ce vybran´ ych 2D transformac´ı 1.1 Metody vyrovn´ an´ı . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Obecn´e vyj´ adˇren´ı line´ arn´ıch 2D transformac´ı . . . . . . . . . . 1.3 Podobnostn´ı transformace . . . . . . . . . . . . . . . . . . . . . 1.4 Afinn´ı transformace . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Afinn´ı transformace s podm´ınkami . . . . . . . . . . . . . . . . 1.6 Projektivn´ı transformace . . . . . . . . . . . . . . . . . . . . . . 1.7 Speci´ aln´ı pˇr´ıpady afinn´ı transformace . . . . . . . . . . . . . . . Literatura
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
2 2 4 4 5 6 8 8 10
1
1
Odvozen´ı transformaˇ cn´ıho kl´ıˇ ce vybran´ ych 2D transformac´ı
C´ılem t´eto ˇc´ asti je podrobnˇe popsat vˇsechny implementovan´e postupy v´ ypoˇctu transformaˇcn´ıch koeficient˚ u. Pops´ an bude jak obecn´ y postup vyrovn´an´ı, tak konkr´etn´ı tvary matic pro jednotliv´e transformaˇcn´ı metody.
1.1
Metody vyrovn´ an´ı
Pro jednoznaˇcn´e urˇcen´ı transformaˇcn´ıho kl´ıˇce z nadbyteˇcn´eho poˇctu identick´ ych bod˚ u byla pouˇzita metoda nejmenˇs´ıch ˇctverc˚ u. Tato metoda byla aplikovan´a na vzd´alenost (v rovinnˇe) mezi c´ılov´ ymi a pˇretransformovan´ ymi v´ ychoz´ımi body. V n´ asleduj´ıc´ım textu budou pops´ any vzorce, kter´e byly pouˇzit´e pro jednotliv´a vyrovn´an´ı metodou zprostˇredkuj´ıc´ıch pozorovan´ı. D´ ale bude tak´e zm´ınˇen sloˇzitˇejˇs´ı pˇr´ıpad vyrovnan´ı metodu zprostˇredkuj´ıc´ıch s podm´ınkami. Pro dalˇs´ı rovnice pouˇzijeme toto oznaˇcen´ı: x x0 dx Fi (x)
= = =
li vi f¯i i
(x1 . . . xk )T (x10 . . . xk0 )T (dx1 . . . dxk )T
vektor hledan´ ych veliˇcin vektor pˇribliˇzn´ ych hodnot nezn´am´ ych vektor pˇr´ır˚ ustk˚ u pˇribliˇzn´ ych hodnot funkˇcn´ı vztah mezi hledan´ ymi x a mˇeˇren´ ymi veliˇcinami (v naˇsem pˇr´ıpadˇe transformaˇcn´ı rovnice) namˇeˇren´a zprostˇredkuj´ıc´ı veliˇcina oprava namˇeˇren´e zprostˇredkuj´ıc´ı veliˇcina vyrovn´a hodnota zprostˇredkuj´ıc´ı veliˇciny index i-t´e zprostˇredkuj´ıc´ı rovnice
Pak plat´ı: Fi (x) = f¯i Fi (x1 . . . xk ) = li + vi Fi (x10 + dx1 . . . xk0 + dxk ) = li + vi Levou stranu rozvedeme do Taylerova rozvoje 1 : Fi Fi dx1 + . . . + dxk = li + vi Fi (x0 ) + dx1 dxk Po u ´pravˇe dost´ av´ ame: ai1 dx1 + ai2 dx2 + . . . + aik dxk + Fi (x0 ) − li = vi ,
(1)
kde i = 1, . . . , n a n je poˇcet linearizovan´ ych zprostˇredkuj´ıc´ıch rovnic oprav a k je poˇcet hledan´ ych nezn´ am´ ych. V´ yraz Fi (x0 ) − li = Li je tzv. absolutn´ı ˇclen.
1 Pro pˇ r´ıpad, kdy zavedeme vhodnou substituci a napˇr. jako transformaˇ cn´ı koeficienty nevol´ıme pˇr´ımo geometrick´ e parametry, nen´ı pouˇ zit´ı Taylerova rozvoje nutn´ e. V pˇr´ıpadˇ e, kdy potˇrebujeme, ale zav´ est podm´ınky pˇr´ımo pro geometrick´ e koeficienty (napˇr, stoˇ cen´ı rovno nule, nebo shodn´ a zmˇ ena mˇ eˇr´ıtek pro obˇ e osy apod..) Tylerovo rozvoj mus´ıme pouˇ z´ı.
2
V´ yraz (1) m˚ uˇzeme zapsat maticovˇe takto: Adx + L = v, kde A=
a11 a21 .. .
a21 a22 .. .
... ... .. .
a1k a2k .. .
ank
an2
...
ank
L=
,
dx =
dx1 dx2 .. .
,
(2)
dxk
F1 (x0 ) − l1 F2 (x0 ) − l2 .. .
.
(3)
Fn (x0 ) − ln Po aplikace metody nejmenˇs´ıch ˇctverc˚ u (odvozen´ı viz [1]) z´ısk´av´ame pro vyrovnan´e nezn´am´e vztah: dx = −(AT A)−1 (AT L)
(4)
Tento zp˚ usob byl implementov´ an pro v´ ypoˇcet podobnost´ı, afinn´ı a projektivn´ı transformace, pˇriˇcemˇz konkr´etn´ı matice jsou uvedeny v n´asleduj´ıc´ıch kapitol´ach. Pro pˇr´ıpad, kdy chceme zav´est podm´ınky pro nezn´ am0 je v´ ypoˇcet n´ asleduj´ıc´ı: Podm´ınky pro opravy nezn´ am´ ych definujeme pomoc´ı obecn´eho vyj´adˇren´ı:
b11 v1 + . . .
+b1n vn + U1 = 0 .. .
br1 v1 + . . .
+brn vn + Ur = 0
(5)
kde Ui jsou hodnoty uz´ avˇer˚ u - tzn. rozd´ıl mezi hodnotou vypoˇc´ıtanou z pˇribliˇzn´ ych hodnot a hodnotou poˇzadovanou, kter´ a je stanovena podm´ınkou. Koeficienty oznaˇcen´e jako bii tvoˇr´ı pak matici B. M˚ uˇzeme tedy ps´ at:
Bv + U = 0
(6)
Pro spoleˇcn´e vyrovn´ an´ı zprostˇredkuj´ıc´ıch mˇeˇren´ı s podm´ınkami pak dost´av´ame (odvozen´ı viz [1]):
dx k
=
AT A B
BT 0
3
−1
AT L U
(7)
1.2
Obecn´ e vyj´ adˇ ren´ı line´ arn´ıch 2D transformac´ı
V t´eto ˇc´ asti se budeme zab´ yvat implementovanou skupinou line´arn´ıch 2D transformac´ı a pˇredevˇs´ım zp˚ usobem v´ ypoˇctu transformaˇcn´ıho kl´ıˇce z nadbyteˇcn´eho poˇctu identick´ ych bod˚ u. Pops´any budou: • Podobnostn´ı transformace • Afinn´ı transformace • Projektivn´ı transformace • Afinn´ı transformace s podm´ınkami • Speci´ aln´ı pˇr´ıpad afinn´ı transformace Obecn´ y v´ yraz pro vˇsechny tyto metody lze napsat pomoc´ı obecn´eho maticov´eho vyj´adˇren´ı x0 = Px, kde qx0 p00 p10 p20 x x0 = qy 0 P = p01 p11 p12 , x = y , q p02 p12 1 1 pˇriˇcemˇz x0 , y 0 jsou souˇradnice v c´ılov´e soustavˇe, x, y ve v´ ychoz´ı, pnn jsou transformaˇcn´ı koeficienty a q je pomocn´ y parametr. V n´ asleduj´ıc´ıch odstavc´ıch budou uvedeny vztahy pro v´ ypoˇcet transformaˇcn´ıch koeficient˚ u na ˇ Aˇckoliv je toto odvozen´ı pomˇernˇe jednoduch´e, z´ akladˇe zn´ am´ ych identick´ ych bod˚ u pomoc´ı MNC. uv´ ad´ıme jej zde pˇredevˇs´ım z d˚ uvodu dokumentace implementovan´ ych algoritm˚ u. C´ılem je tak´e vytvoˇrit jednotn´ y soupis vˇsech vztah˚ u pro tyto metody. Pro koneˇcn´ y v´ ypoˇcet koeficient˚ u lze pouˇz´ıt algoritmus vyrovn´an´ı zprostˇredkuj´ıc´ıch mˇeˇren´ı (viz ˇc´ ast 1.1). C´ılem n´ asleduj´ıc´ıch sekc´ı je tedy pˇredevˇs´ım popsat tvar matic A, dx a L. Pro koneˇcn´ y transformaˇcn´ıch parametr˚ u pak staˇc´ı pouˇz´ıt vzorec (4).
1.3
Podobnostn´ı transformace
Podobnostn´ı transformaci lze vyj´ adˇrit pomoc´ı vztahu: 0 x a −b c x y0 = b a d y 0 0 1 1 1 Jelikoˇz se jedn´ a o line´ arn´ı vztah, lze jako pˇribliˇzn´e hodnoty nezn´am´ ych zvolit x0 = (0, 0, 0, 0)T a tedy plat´ı i 0 + dxi = xi → xi = dxi Nezn´am´ ymi jsou transformaˇcn´ı koeficienty. Necht’ tedy matice dx m´ a tvar: a b dx = c d Potom matice A m´ a tvar:
x1
xn A= y1 yn
−y1 .. .
1
−yn x1 .. .
1 0
xn
0
4
0
0 1 1
(8)
Vzhledem k volbˇe nulov´ ych pˇribliˇzn´ ych hodnot m˚ uˇzeme ps´at Fi (x0 ) = 0 a tedy (dle 3) matice L m´ atvar: 1 x01 .. . 0 xn L = − y10 . ..
(9)
yn0
Pouˇzit´ım vztahu (4) dost´ av´ ame tak pˇr´ımo vyrovnan´e nezn´am´e bez nutnosti dalˇs´ı iterace. D˚ uvodem je line´ arn´ı vztah mezi nezn´ am´ ymi a mˇeˇren´ ymi veliˇcinami.
1.4
Afinn´ı transformace
Afinn´ı transformaci lze vyj´ adˇrit pomoc´ı vztahu: 0 x a b c x y0 = d e f y 1 0 0 1 1 Na z´ akladˇe obdobn´e volby nezn´ am´ ych jako v 1.3 m˚ uˇzeme ps´at tvar matice dx: a b c dx = d e f Potom matice A m´ a tvar:
x1
xn A= 0 0
y1
1 .. .
0
0
yn 0
1 0 .. .
0 x1
0 x1
0
0 xn
xn
0
0 1 1
(10)
Matice L je pak shodn´ a jako u podobnost´ı transformace viz vztah 9. Pouˇzit´ım vztahu 4 dost´av´ame tak pˇr´ımo vyrovnan´e nezn´ am´e. Pro optimalizaci v´ ypoˇctu lze matici A zjednoduˇsit a poˇc´ıtat nezn´ame a, b, c a d, e, f oddˇelenˇe. Matice A m´ a pak tvar: x1 y1 1 .. A= . xn
yn
1
pˇriˇcemˇz d´ılˇc´ı matice nezn´ am´ ych jsou:
a d dx1 = b , dx2 = e c f 1V
implementaci tohoto zp˚ usobu bylo znam´ enko matice L vytknuta a uplatnˇ eno aˇ z ve vztahu 4.
5
a d´ ale matice L lze rozdˇelit takto: x01 L1 = − ... , L2 = − x0n
1.5
y10 .. . yn0
(11)
Afinn´ı transformace s podm´ınkami
Jednou z ˇcasto pouˇz´ıvan´ ych forem afinn´ı transformace je varianta, kdy parametr zkosen´ı je roven nule. Tento zp˚ usob se ˇcasto vyuˇz´ıv´ a pr´ avˇe pˇri referencov´an´ı satelitn´ıch sn´ımk˚ u apod. Obecnˇe lze tuto u ´lohu ˇreˇsit bud’ pˇr´ım´ ym vylouˇcen´ım tohoto parametru, nebo pouˇzit´ım vyrovn´an´ı zprostˇredkuj´ıc´ıch mˇeˇren´ı s podm´ınkami. V n´ asleduj´ıc´ıch odstavc´ıch bude pops´ano odvozen´ı vyrovn´an´ı vˇcetnˇe podm´ınek, tak jak bylo implementov´ ano. V´ yhodou je obecn´ y pˇr´ıstup k ˇreˇsen´ı dan´eho probl´emu. V´ ysledek pak umoˇzn ˇuje definovat jak´ekoliv jin´e podm´ınky bez z´asahu do k´odu. Pro urˇcen´ı transformaˇcn´ıch koeficient˚ u je pouˇcit obecn´ y algoritmus vyrovn´an´ı zprostˇredkuj´ıc´ıch mˇeˇren´ı s podm´ınkami dle [1]. Jelikoˇz je nutn´e pracovat pˇr´ımo s geometrickou formou transformaˇcn´ıch parametr˚ u je v´ ychoz´ı vztah afinn´ı transformace tento: x0 y0
= Sx cos αx = Sx sin αx
− +
Sy sin αy Sy cos αy
+ Tx + Ty
(12)
kde x0 , y 0 jsou c´ılov´e souˇradnice, x, x jsou v´ ychoz´ı souˇradnice. Dalˇs´ı oznaˇcen´ı je: Sx Sy αx αy Tx Ty
mˇeˇr´ıtko ve smˇeru osy X, mˇeˇr´ıtko ve smˇeru osy Y, u ´hel rotace pro osu x, u ´hel rotace pro osu y, posun ve smˇeru osy X, posun ve smˇeru osy Y.
Parametr q vyjadˇruj´ıc´ı zkosen´ı je potom q = αx − αy Pro dalˇs´ı postup vyrovn´ an´ı byla matice dx nezn´am´ ych zvolena takto: dx =
dSx dSy αx αy dTx dTy
(13)
Na z´ akladˇe t´eto volby byla odvozena matice A. Jednotliv´e derivace potom jsou (i = 1, . . . , n je poˇcet identick´ ych bod˚ u):
dx Sx dx
i
Sy i dx αx
dx αy
dx Tx
dx Ty
i i i
=
cos αx xi
= − sin αy yi = −Sx sin αx xi = −Sy cos αy yi =
1
=
0
i
6
(14)
dy Sx
dy Sy
dy
i i
αx i dy αy
dy Tx dy Ty
i i
=
sin αx xi
=
cos αy yi
=
Sx cos αx xi
=
−Sy sin αy yi
=
0
=
1
(15)
i
Matice A m´ a tedy tvar:
dx Sx
1 dx Sx n A= dy Sx 1 dy Sx
n
dx Sy
.. . dx Sy
dy Sy
1
n
.. . dy Sy
1
n
dx αx
dx αx dy αx
dy αx
1
n
1
n
dx αy
dx αy dy αy
dy αy
1
dx Tx
1
.. .
n
Tx n
dx
1
n
dy Tx
.. . dy Tx
1
dx Ty
1
dx Ty n dy Ty 1
n
dy Ty
(16)
n
Zb´ yv´ a jeˇstˇe naplnit matici L. Dle vztah˚ u (3) a (12) m˚ uˇzeme ps´at: f x(x0 ) − x01 .. . f x(x0 ) − x0n L= 0 , f y(x0 ) − y1 .. .
(17)
f y(x0 ) − yn0
kde x0 je vektor pˇribliˇzn´ ych hodnot nezn´am´ ych. Pro zaˇrazen´ı podm´ınek do vyrovn´ an´ı je jeˇstˇe nutn´e urˇcit tvar matice B a U. Chceme-li napˇr. definovat podm´ınku, ˇze parametr zkosen´ı q m´a b´ yt roven (tzn. mus´ı platit αx −αy = 0) bude rovnice (6) m´ıt tento tvar: vα x + (−q0 ) = 0 Matice B bude m´ıt pak tvar (vzhledem ke vztahu (13)): B = (0, 0, −1, 1, 0, 0) Chceme-li aby parametr zkosen´ı q mˇel po vyrovn´an´ı hodnotu q = 0 bude matice U m´ıt tvar: U = (αx0 − αy0 ) , kde q0 je pˇribliˇzn´ a hodnota parametru q. V´ ysledn´e opravy pak dostaneme pomoc´ı vzorce (7). M´ ame-li k dispozici odpov´ıdaj´ıc´ı pˇribliˇzn´e hodnoty m˚ uˇzeme opravy poˇc´ıtat iterativnˇe. Pˇribliˇzn´e hodnoty lze z´ıskat napˇr. v´ ypoˇctem afinn´ı transformace bez podm´ınek jak je pops´ano v ˇc´asti 1.4.
7
1.6
Projektivn´ı transformace
Projektivn´ı transformaci lze vyj´ adˇrit pomoc´ı vztahu: mx0 a b c x my 0 = d e f y m g h 1 1 Vzhledem k line´ arn´ı formˇe vztah˚ u m˚ uˇzeme opˇet zvolit: a b c d dx = e f g h Potom matice A m´ a tvar:
x1
xn A= 0 0
y1
1
0 .. .
0
−x0 x −x0 y
0
yn 0
1 0
0 x1 .. .
0 y1
0 1
0
0 xn
yn
1
0 0 −x x −x y −x0 x −x0 y −x0 x −x0 y
(18)
Matice L je pak shodn´ a jako u podobnost´ı transformace viz vztah (9). Pouˇzit´ım vztahu (4) dost´ av´ ame tak opˇet pˇr´ımo vyrovnan´e nezn´am´e.
1.7
Speci´ aln´ı pˇ r´ıpady afinn´ı transformace
V t´eto ˇc´ asti bude pops´ ano odvozen´ı transformace pˇr´ı kter´e doch´az´ı ke zmˇenˇe mˇeˇr´ıtek v obou smˇerech a k posunu. Na rozd´ıl od afinn´ı transformace tedy nen´ı uplatnˇeni zkosen´ı a rotace. Pouˇzijeme-li ve vztahu (12) nulov´e koeficienty pro stoˇcen´ı z´ısk´ame transformaˇcn´ı rovnici ve tvaru: 0 a 0 b x x y0 = 0 c d y 1 0 0 1 1 Necht’ tedy matice nezn´ am´ ych dx m´ a tvar:
a b dx = c d Potom matice A m´ a tvar:
x1
xn A= 0 0
1 .. .
0
1 0 .. .
0 y1
0 yn 8
0
0 1 1
(19)
V´ ysledn´ y postup v´ ypoˇctu nezn´ am´ ych je shodn´ y s v´ ypoˇctem afinn´ı transformace. Pouˇzit´ım vztahu (4) dost´ av´ ame opˇet pˇr´ımo vyrovnan´e nezn´am´e. Pro optimalizaci v´ ypoˇctu je moˇzn´e matici A opˇet rozdˇelit a poˇc´ıtat koeficienty oddˇelenˇe. Na rozd´ıl od afinn´ı transformace vˇsak nedostaneme pro obˇe skupiny koeficient˚ u stejnou matici A.
9
Reference [1] Kabel´ aˇc, J.: Geodetick´e metody vyrovn´ an´ı metoda nejmenˇs´ıch ˇctverc˚ u. Skriptum Fakulty Aplikovan´ ych Vˇed Plzeˇ n, Z´ apadoˇcesk´ a univerzita v Plzni 2003, ISBN 80-7043-260-8.
10
