Duální kvaterniony a jejich aplikace Jitka Prošková∗ Abstrakt: Příspěvek je zaměřen na kvaterniony, duální kvaterniony a jejich schopnost popsat přímé shodnosti. Výhodou je jednoduchost reprezentace rotace a translace v jedné prostorové operaci tj. jejich složení. Využívají se například tam, kde klasický maticový přístup naráží na své specifické problémy. Dále budou zmíněny některé vhodné aplikace duálních kvaternionů (robotika, počítačová grafika, kybernetika).
1
Úvod
Práce je zaměřena na vyjádření rotace a posunutí duálními kvaterniony. Zavedený jednotkový kvaternion je využíván k popisu rotace. Dále jsou popsána duální čísla, která vznikla rozšířením reálných čísel duální jednotkou. Kvaterniony a duální čísla jsou využívány k zavedení duálních kvaternionů. Analogicky zavedený jednotkový duální kvaternion se používá k popisu přímé shodnosti ve speciální euklidovské grupě. Další část práce je věnovaná použití duálních kvaternionů v praxi.
2
Kvaterniony
Kvaterniony jsou zobecněním komplexních čísel v trojrozměrném prostoru. U zrodu kvaternionů stál Sir William Rowan Hamilton (1805–1865). Nalezl vztah pro násobení čtyř základních jednotek, pro něž platí i2 = j2 = k2 = i j k = −1. Přišel na to, že je zapotřebí zavést jednu reálnou a tři imaginární složky, aby byla správně vytvořena algebra kvaternionů. Nyní zavedeme některé důležité pojmy. Definice 2.1 Nechť i2 = k2 = j2 = ijk = −1, ij = k a ji = −k. Kvaternion q můžeme napsat jako: q = [a, v ], a ∈ R, v ∈ R3 = [a, (b, c, d)], a, b, c, d ∈ R = a + i b + j c + k d, a, b, c, d ∈ R. Definice 2.2 Množinu všech kvaternionů budeme značit H. ∗
Katedra matematiky, ZČU v Plzni, Univerzitní 22, 306 14 Plzeň,
[email protected]
Definice 2.3 Nechť q ∈ H. Pak q = [a, v ] = [a, −v ] nazýváme konjugovaným kvaternionem s kvaternionem q. Definice 2.4 Nechť q ∈ H, q = [a, v ] = [a, (b, c, d)]. Norma k q k kvaternionu q je dána vztahem √ p kqk= a2 + b2 + c2 + d2 = qq. (1) Jednotkové kvaterniony kq k= 1 jsou významné pro počítačovou grafiku, tento kvaternion ˆ sin θ], kde kˆ se dá zapsat jako q = [cos θ, v vk= 1. Množinu všech jednotkových kvaternionů budeme označovat H1 . Kvaternion popisuje rotaci v trojrozměrném prostoru, a to rotaci ˆ o úhel 2θ (viz [2]). kolem jednotkového vektoru v Věta 2.1 Nechť q ∈ H1 , q = [cos θ, sin θˆ v]. Nechť r = (x, y, z) ∈ R3 a p = [0, r] ∈ H. Pak (2)
pˆ = qp¯ q
ˆ, viz Obr. 1. je obrazem p v rotaci o úhel 2θ kolem osy, která je daná směrovým vektorem v Důkaz: Viz [6].
2 o Pˆ
P 2θ
ˆ v
0
ˆ. Obrázek 1: Otočení bodu P o úhel 2θ kolem osy o, která je daná směrovým vektorem v Reprezentace rotace pomocí kvaternionů je výhodnější než pomocí matic, protože kvaterniony obsahují pouze čtyři složky, zatímco matice typu 3×3 mají složek devět. Pro rotaci dostáváme vztah pˆ = qp¯ q , kde q je jednotkový kvaternion. Tento vztah je důležitý, protože jej budeme aplikovat i na rotace spojené s duálními kvaterniony, více např. v [6].
3
Duální čísla
Duální kvaterniony vznikly složením kvaternionů a duálních čísel. Duální čísla poprvé v pravém významu uvedl William Kingdon Clifford (1845–1879). Tento anglický matematik se také podílel na vzniku duálních kvaternionů1 . Duální čísla se podobají komplexním číslům – v podstatě si je můžeme i podobně představit. Základní odlišností je duální jednotka ε, pro kterou platí vztah ε2 = 0. Algebra duálních čísel tvoří komutativní, asociativní okruh s jednotkovým prvkem. Pomocí duálních čísel můžeme zavést duální vektor případně duální úhel, který je používán v souvislosti s duálními kvaterniony. V této algebře neexistují inverzní prvky k ryzím duálním číslům čímž se odlišují od komplexních čísel. Množinu všech duálních čísel budeme značit D. Definice 3.1 Nechť a ∈ R, aε ∈ R a ε 6= 0, ε2 = 0. Duální číslo z můžeme napsat jako z = a + εaε .
4
(3)
Duální kvaterniony
Nyní již můžeme říci, že duální kvaternion je kombinace duálního čísla a duálního vektoru. Můžeme si jej také představit jako součet dvou kvaternionů, kdy jeden z nich je násoben duální jednotkou. Tato algebra má podobné vlastnosti jako algebra kvaternionů, netvoří těleso, ale asociativní okruh s jednotkovým prvkem. Definice 4.1 Nechť ad , bd , cd , dd ∈ D. Duální kvaternion qd definujeme vztahem qd = ad + bd i + cd j + dd k,
(4)
kde ad je skalár (duální číslo), (bd , cd , dd ) je vektor (duální vektor) a 1, i, j, k jsou čtyři základní kvaternionové jednotky z Definice 2.1. Poznámka 4.1 1. Duální jednotka ε je komutativní s kvaternionovými jednotkami, např. i ε = εi. 2. Duální kvaternion můžeme zapsat následujícím způsobem qd = a + bi + cj + dk + εaε + εbε i+εcε j+εdε k nebo jako součet dvou kvaternionů qd = q +εqε , kde q = a+bi+cj+dk a qε = aε + bε i + cε j + dε k. Definice 4.2 Množinu všech duálních kvaternionů budeme značit Hd . Definice 4.3 Nechť qd ∈ Hd , pak duální kvaternion q∗d nazýváme duálně konjugovaným duálním kvaternionem s duálním kvaternionem qd , jestliže platí q∗d = q − εqε .
(5)
V literatuře bývají duální kvaterniony rovněž označovány jako bi-kvaterniony nebo komplexní kvaterniony. 1
Definice 4.4 Nechť qd ∈ Hd , qd = q + εqε = a + bi + cj + dk + εaε + εbε i + εcε j + εdε k. Norma kqdk duálního kvaternionu qd je dána vztahem p p kqdk= (a + εaε )2 + (b + εbε )2 + (c + εcε )2 + (d + εdε )2 = qd qd . (6) Pro jednotkový duální kvaternion opět platí kqd k= 1. Množinu všech jednotkových duálních kvaternionů budeme značit Hd1 . Hlavní výhodou duálních kvaternionů je fakt, že dokáží jednoduše reprezentovat rotaci a translaci v jedné prostorové operaci. Právě duální kvaterniony se využívají v grafice, kde nepomáhají maticové reprezentace. Takovými technikami, kde je lze využít, je například skinnig2 (viz [5]). Věta 4.1 Nechť je dán polohový vektor p = (p1 , p2 , p3 ) ∈ R3 bodu P , vektor posunutí t = (t1 , t2 , t3 ) ∈ R3 a jednotkový kvaternion q ∈ H1 . Pak posunutí a otočení bodu P do bodu Pˆ můžeme vyjádřit jako ˆ d = qd pd q∗d , (7) p kde pd je jednotkový duální kvaternion odpovídající vektoru p, který je ve tvaru pd = 1 + ε(p1 i + p2 j + p3 k),
(8)
a qd je jednotkový duální kvaternion, pro který platí qd = q + εqε = q + ε
tq , 2
t = t1 i + t2 j + t3 k ∈ H.
(9)
Důkaz: Viz [7].
5
Aplikace duálních kvaternionů
Duální kvaterniony se využívají v mnoha odvětvích. Najdeme je také například v kinematice, fyzice nebo geometrickém modelování. Zde jsou uvedené vybrané aplikace, další např. viz [7].
5.1
Hand–eye kalibrace
Další uplatnění duálních kvaternionů nalezneme v robotice. V dnešní době se můžeme s roboty setkat také v lékařství [4]. Tomuto odvětví se říká robotická chirurgie. Výhodou je šetrný přístup k lidské tkáni, kdy se operuje jen přesně ohraničené místo a snižují se následné komplikace (např. infekce). Robotický systém se skládá z ramen, kdy je jedno rameno vybaveno speciální kamerou s trojrozměrným obrazem. Chirurg může vnímat mimo obrazu i hloubku a určit tak přesně pohyb chirurgických nástrojů, jenž jsou pevně připevněné k ramenům robota. Hand–eye systém bychom mohli přeložit do češtiny jako systém ruka–oko. Oko představuje kamera, která je pevně připevněná na pohyblivém úchopu a snímá okolí. Hand–eye kalibrace je vypočtení vzájemné pozice a nastavení mezi úchopem robota a kamerou pevně připevněnou k 2
Metoda v počítačové grafice, která se používá k animaci deformace složitějších objektů.
úchopu. Zahrnuje tedy počítání přímých shodností mezi nimi, respektive mezi pozicí v obraze a polohou úchopu. Problém se týká všech senzorů, které jsou připevněné na mechanických spojích. Jedná se například o kameru namontovanou na binokulární hlavě s mechanickými stupni volnosti nebo kameru připevněnou na nějakém přístroji. S pomocí kamery, kterou připevníme na úchop, můžeme odhadnou pozici uchopení nebo získat pozici kamery. Řídící pokyny robota jsou zadány v souřadnicovém systému úchopu. Dokonce, když změníme souřadnice kamery, měli bychom poznat, jak se změní obraz snímaný kamerou robota. Pomocí kamery umístěné na úchopu také můžeme provést stereoskopickou rekonstrukci tak, že kameru nastavíme do několika poloh sdílejících stejný pohled. K rekonstrukci trojrozměrné pozice musíme znát vzájemnou korelaci z kamerového souřadnicového systému. Ovšem známe pouze jednu transformaci a ta je v souřadnicích robota. Podobný postup bychom použili i pro připojení kamery na binokulární hlavě. Pokud je kamera ručně připevněná, tak je nutná tato kalibrace, protože může dojít k naklonění kamerového systému. Obvykle můžeme popsat hand–eye kalibraci pomocí několika homogenních transformačních matic. Označme X jako matici transformace z kamery do úchopu, Ai jako transformační matici z kamery do bázového systému souřadnic a Bi jako transformační matici ze základny robota do úchopu v i-té pozici. Platí AX = XB, kde A, B, X jsou matice typu 4 × 4 , které mají tento tvar: RA t A RB tB RX tX A= , B= , X= , 0 1 0 1 0 1
(10)
(11)
kde RA , RB , RC ∈ SO(3)3 a tA , tB , tX ∈ R3 jsou vektory popisující posunutí. Nechť A1 a A2 jsou transformační matice z kamery do bázového systému souřadnic ve dvou pozicích, dostáváme: (12) A = A2 A−1 1 . Matici B popisuje pohyb úchopu z jedné pozice do druhé, a opět pokud jsou B1 a B2 transformační matice ze základny robota do úchopu, dostáváme: B = B2−1 B1 .
(13)
Ze vztahu (10) vyplývá základní rovnice pro popis vztahu mezi kamerou a úchopem: RA RX = RX RB (RA − I)tX = RX tB − tA .
(14) (15)
Obvykle se postupuje tak, že se vyřeší RX ze vztahu (14) a poté tX ze vztahu (15). K vyřešení neznámých se využívá nelineární optimalizace. Nyní se pokusíme úlohu formulovat pomocí duálních kvaternionů, které využijeme pro interpretaci rotace a translace. Nechť pd označuje šroubový pohyb kamery a rd označuje šroubový pohyb úchopu. Kamera a úchop jsou pevně spojené. Přímá shodnost mezi nimi není známá a budeme ji označovat jednotkovým duálním kvaternionem qd . Složením tedy dostáváme: pd = qd rd qd . 3
Speciální ortogonální grupa, tj. podgrupa ortogonálních matice, jejichž determinant je roven 1.
(16)
Skalární části duálních kvaternionů ℜ(pd ) a ℜ(rd ) se rovnají, proto se vztah (16) zjednoduší. Šroubový pohyb tedy popíšeme následujícím vztahem: vdp sin
θdp θd = qd (vdr sin r )qd . 2 2
(17)
Vztah (17), který jsme získali použitím duálních kvaternionů, a vztah (14) jsou ekvivalentní. K dokončení výpočtu můžeme použít např. lineární metodu SVD rozkladu viz [3]. Výhoda duálních kvaternionů je hlavně v tom, že dokáží popsat přímou shodnost.
5.2
Segmentace objektů z ultrazvukového obrazu
Ultrasonografie je diagnostická zobrazovací technika, která využívá ultrazvukové vlny. Používá se například pro zobrazování svalů nebo vnitřních orgánů. Následně se zkoumá jejich velikost, struktura nebo poškození. V kybernetice se můžeme setkat s tzv. segmentací objektů z ultrazvukového obrazu vytvořeného ultrasonografií. Segmentace, viz [1], je využívána právě ke zpracování a analýze obrazových dat, při které se dělí obraz na určité oblasti. Vlastnosti těchto oblastí jsou v nějakém ohledu stejnorodé. Obvykle se pokoušíme odlišit určité objekty od pozadí. Segmentace je složitý problém. Při snímání se do obrazu může přidat šum nebo může dojít k tvarovým deformacím, a proto je těžké rozpoznat hledané objekty. Důležité je mít nějaké informace o problému, např. tvar objektu nebo pozice ve scéně. Jednou z nejčastějších metod segmentace je prahování. Jedná se o transformaci obrazu na obraz binární. Tato metoda dobře funguje pro objekty, které se výrazně liší od pozadí. V ultrazvukových snímcích jsou si velmi podobné textury objektu a pozadí. Je složité hledaný objekt oddělit a prahování zde nelze použít. Hledá se tedy metoda, která dokáže přesně ohraničit objekty ze snímků, jenž jsou špatně rozeznatelné. Soustřeďme se nyní na rozpoznávání tvaru ledvin v ultrazvukovém snímku. Nejprve se popíší textury, které jsou v hledané oblasti, tedy v ledvinách. Poté se zjišťuje podobnost mezi texturou ledvin a texturou snímku. Chceme tak určit tvar ledviny. To ovšem není snadné. Potřebujeme ještě získat obecný tvarový model ledviny. Vezmeme tedy co nejvíce různých tvarů ledvin a z nich získáme model průměrného tvaru ledviny a vektory deformací. Vektor deformací uvádí, jak a kde se ledviny mohou deformovat. Sestaví se kritérium, které obsahuje tyto míry deformací. Poté se tvarový model ledviny otáčením a posouváním aplikuje na snímek, kde se dle kritéria vypočítávají míry deformací. Postupnou aplikací bychom měli získat přesný tvar ledviny na ultrazvukovém snímku. O problém segmentace objektů z ultrazvukového obrazu se začala zajímat katedra kybernetiky na ZČU. Díky nedostatku lékařských dat se tento problém snaží řešit pro segmentaci javorových listů. Na část celé úlohy můžeme aplikovat duální kvaterniony. Jedná se tedy o otočení, posunutí a zvětšení resp. zmenšení daného objektu. Předně se zpracuje snímek javorového listu v programu Matlab. Převede se na jednotlivé body, chybějící body se dopočítají a javorový list se vykreslí. Dostáváme potřebné body objektu, s kterými budeme dále pracovat. List musíme posunout do požadované polohy a dále s ním otáčíme. Celý proces otáčení a posouvání slouží k pozdější aplikaci porovnávání,
kdy daný obecný list porovnáváme s tím, který chceme rozpoznat, zjišťujeme jeho vektory deformace a hledáme optimální kritérium. K řešení použijeme funkci pro otočení a posunutí bodu duálními kvaterniony v prostoru, podrobněji viz podkapitola 5.3. Zadaná data jsou pouze dvojrozměrná, a proto se celý algoritmus zjednoduší.
5.3
Výpočet otočení a posunutí ploch, křivek a bodů v trojrozměrném prostoru
Vytvoříme funkci pro výpočet otočení plochy, resp. křivky okolo zadané osy o úhel ϕ a posunutí o vektor t v programu matlab (dále jen otočení a posunutí plochy). Uvedeme pouze algoritmus, dle kterého program pracuje. Využijeme získaných poznatků o duálních kvaternionech. Použijeme vztah pro otočení a posunutí bodu duálním kvaternionem (7). Algoritmus 1 Vstup: Zadávány jsou tyto parametry: bod, který chceme transformovat: P = [px , py , pz ]; body určující osu otočení: A = [ax , ay , az ], B = [bx , by , bz ]; vektor posunutí: t = (tx , ty , tz ), úhel otočení ϕ. Výpočet: • Nejprve posuneme bod P o vektor a = (−ax , −ay , −az ) tak, aby osa otočení procházela počátkem. Souřadnice posunutého bodu jsou: pˆx p x − ax , (18) Pˆ = P + a = py − ay = pˆy . pˆz p z − az ˆ d dostáváme: Po přepsání bodu Pˆ do jednotkového duálního kvaternionu p ˆ d = [1, 0, 0, 0, 0, pˆx , pˆy , pˆz ] = [a2 , 0, 0, 0, 0, f2 , g2 , h2 ]. p • Určíme směrový vektor osy otočení, tj. s = B − A. Po normování směrového vektoru dostáváme jednotkový vektor n = (nx , ny , nz ). • Rotační část q duálního kvaternionu qd = [a1 , b1 , c1 , d1 , e1 , f1 , g1 , h1 ], získáme jako: q = [cos θ, (nx sin θ, ny sin θ, nz sin θ)] = [a1 , b1 , c1 , d1 ],
kde θ = ϕ/2.
• Translační část qε duálního kvaternionu qd , získáme ze vztahu qε = tq2 . Přičemž bod posuneme o vektor t a vektor −a. Dostáváme t = [0, tx +ax , ty +ay , tz +az ] = [t1 , t2 , t3 , t4 ] a translační část, s použitím násobení, můžeme vyjádřit jako: e1 (−t2 b1 − c1 t3 − d1 t4 )/2 (t2 a1 + d1 t3 − c1 t4 )/2 f1 qε = (19) (−t2 d1 + a1 t3 + b1 t4 )/2 = g1 . (t2 c1 − b1 t3 + a1 t4 )/2 h1
Duálně konjugovaný kvaternion q∗d k duálnímu kvaternionu qd má následující tvar: q∗d = [a1 , −b1 , −c1 , −d1 , −e1 , f1 , g1 , h1 ] = [a4 , b4 , c4 , d4 , e4 , f4 , g4 , h4 ]. • Postupujeme podle rovnosti (7) s použitím násobení. Nejprve vypočítáme vztah ˆ d , tj.: ad = qd p a1 a2 a3 b3 a2 b 1 c3 a c 2 1 d3 a d 2 1 ad = (20) −b1 f2 − c1 g2 − d1 h2 + e1 a2 = e3 . a1 f2 + c1 h2 − g2 d1 + a2 f1 f3 a1 g2 − b1 h2 + f2 d1 + a2 g1 g3 a1 h2 + b1 g2 − f2 c1 + a2 h1 h3 • Nyní vynásobíme duální kvaternion ad zprava duálním kvaternionem q∗d . Dostaneme ˜ d = [1, 0, 0, 0, 0, p˜x , p˜y , p˜z ], pro jehož souřadnice platí jednotkový duální kvaternion p tento vztah: p˜x a3 f4 + e4 b3 + c3 h4 − g4 d3 + e3 b4 + a4 f3 + g3 d4 − c4 h3 p˜y = a3 g4 − b3 h4 + e4 c3 + f4 d3 + e3 c4 − f3 d4 + a4 g3 + b4 h3 . (21) p˜z a3 h4 + b3 g4 − f4 c3 + e4 d3 + e3 d4 + f3 c4 − b4 g3 + a4 h3 Výsledný bod P˜ po otočení a posunutí má souřadnice P˜ = [˜ px , p˜y , p˜z ]. Získali jsme tak algoritmus pro otočení bodu P o nějaký úhel ϕ okolo libovolné osy otočení a posunutí o nějaký vektor t. Chceme-li otočit a posunout plochu, resp. křivku, budeme postupovat obdobně. Pro transformaci objektu vypočteme jednotlivé body, které následně otočíme a posuneme. Celý kód s příklady je k nahlédnutí v [7]. Výstup algoritmu může být následující: Příklad 5.1 Vykreslení otočené a posunuté plochy hyperbolického paraboloidu viz Obr. 2. Parametrické zadání: P (T 1, T 2) = (T 1, T 2, T 12 − T 22 ). Body osy otočení: A = [0, 10, 0], B = [1, 2, 3]. Úhel otočení: ϕ = π3 . Vektor posunutí: t = [12, 2, 0]. Uvedený algoritmus pro otočení a posunutí se výrazně zjednoduší, pokud ho upravíme pro rovinu. V rovině otáčíme objekt pouze kolem bodu. Rotační část duálního kvaternionu qd přejde do tvaru: q = [cos θ, 0, 0, sin θ] a zjednoduší se i tvar pro translační část duálního ˆd, kvaternionu qε , tj.: qε = [0, (a1 t2 + t3 d1 )/2, (−d1 t2 + t3 a1 )/2, 0]. Duální kvaternion ad = qd p viz vztah (20), upravíme: a1 a2 0 0 a d 2 1 . (22) ad = 0 a1 f2 − g2 d1 + a2 f1 a1 g2 + f2 d1 + a2 g1 0
10 5 0 −5 −10
8 6 4 2 0 −2 −10
−5
0
15
10
5
20
Obrázek 2: Hyperbolický paraboloid v základní poloze (vlevo) a po transformaci (vpravo).
1200
1000
800
600
400
200
0
−200 −200
−100
0
100
200
300
400
500
Obrázek 3: Původní javorový list (zelený) a po otočení o úhel zvětšený s = 1, 6 (modrý).
600
π 8
700
800
okolo bodu A = [500, 500] a
Souřadnice výsledného bodu P˜ jsou tvaru: P˜ = [a3 f4 − g4 d3 + a4 f3 + g3 d4 , a3 g4 + f4 d3 − f3 d4 + a4 g3 ].
(23)
Zvětšení bodu získáme tím, že přenásobíme příslušné souřadnice bodu konstantou s. Algoritmus pro otočení, posunutí a zvětšení bodu najdeme v [7]. Výstup kódu můžeme nalézt na Obr. 3. Funkce také dokáže vypočítat hodnotu zpětné transformace.
6
Závěr
V práci byla zpracována základní teorie týkající se kvaternionů, duálních čísel a duálních kvaternionů. Duální kvaterniony dokáží popsat přímé shodnosti. Výhodou je, že mohou jednoduše reprezentovat rotaci a translaci v jedné prostorové operaci. Využívají se například tam, kde není možné využít reprezentaci rotace a posunutí pomocí matic. V dnešní době mají široké využití. Můžeme je využít v robotice. Dokáží řešit například problém hand–eye kalibrace. Duální kvaterniony popisují pozici mezi úchopem robota a kamerou, která je k úchopu připevněna. Robotický systém se skládá z několika ramen, přičemž je jedno rameno vybaveno speciální kamerou. Lékař tak může přesně určit pohyb chirurgických nástrojů. V práci je nastíněná aplikace duálních kvaternionů pro aktuální problém. Katedra kybernetiky na ZČU se v této době zabývá segmentací z ultrazvukových snímků. Technika, která z ultrazvukových snímků dokáže přesně oddělit požadovaný objekt od pozadí, má velký potenciál pro aplikaci v lékařství.
Reference [1] ANDRET, L. Automatická volumetrie patologických ložisek parenchymatosních orgánů v USG obraze. Bakalářská práce. Plzeň, 2008. [2] CONWAY, J. H., SMITH, D. A. On quaternions and octonions: theory, arithmetic and symetry. 1. vyd, USA : Springer, 2003. [3] DANIILIDIS, K. Hand–Eye Calibration using dual quaternions.The International Journal of Robotics Research. 1999, 3 číslo, s. 286–298. [4] Hospimed -Robotický systém. [online]. [cit. 2009-04-19]. Dostupný na WWW:
. [5] KAVAN, L., COLLINS, S., ŽÁRA, J., O´SULLIVAN, C. Skinning with Dual Quaternions. ACM Transaction on Graphics., 2008, 27(4). [6] PROŠKOVÁ, J. Kvaterniony a jejich užití v geometrii. Bakalářská práce. Plzeň, 2006. [7] PROŠKOVÁ, J. Kvaterniony, duální kvaterniony a jejich aplikace. Diplomová práce. Plzeň, 2009.
