Gram-Schmidt: jak se z hrubých směrů udělá rámec
Kapitola 8 skončila u toho, že ortonormální báze je pohodlná: souřadnice v ní vypadnou z pouhého skalárního součinu a čísla nerostou do nesmyslných hodnot. Zbývá otázka, jak se k takové bázi dostat, když člověk má jenom pár hrubých směrů — což je v praxi vždycky.
Odpověď je jeden opakovaný pohyb, který už znáte z kapitoly 5: odečti průmět.
- a, b — ani kolmé, ani jednotkové
Vstup: dva směry, které někdo naměřil nebo odhadl. Chceme z nich udělat pravoúhlý rámec — a přitom co nejvíc respektovat, co bylo zadané.
- q₁ = a / |a|
První směr se jenom znormalizuje a jinak se nechá být. To je vlastnost, na které v praxi hodně záleží: když je a osa, kolem které se opravdu otáčí, nesmí se pohnout.
- proj = (b·q₁)q₁ → délka 1,286
Druhý vektor se rozloží podle kapitoly 5. Ta část, která míří podél q₁, je to, co b a a mají společné — a právě to musí pryč.
- w = b − proj
Zbytek. Celý Gram-Schmidt není nic jiného než tohle, jen opakovaně: vezmi další vektor, odečti z něj všechno, co už umí předchozí, a co zbude, je nový směr.
- w·q₁ = 0,000000
Nemusí se to věřit — vynásobí se to a vyjde nula. To není náhoda: odečetli jsme právě tolik, aby nezbylo nic ve směru q₁.
- q₂ = w / |w| — rámec je hotový
Zbývá zkrátit na jedničku. Ve třech rozměrech se stejný postup zopakuje s třetím vektorem, jen se odečítají dva průměty. A poslední směr se dá vzít i zkratkou: q₃ = q₁ × q₂.
Ve třech rozměrech se totéž zopakuje potřetí, jen se odečítají dva průměty. A poslední směr se dá vzít zkratkou: q₃ = q₁ × q₂ je z definice kolmý na oba a rovnou jednotkový.
První směr zůstává — a proto se to používá
Ta nesymetrie není vada, je to celý smysl. V robotice se tímhle staví rámec nástroje: osa z je směr, kterým chapadlo opravdu míří a se kterým se hýbat nesmí; x je jen hrubé přání („zhruba podél stolu“), které se srovná do kolmého směru.
Nápověda rovnoběžná s osou je ta výjimka, na kterou se musí
myslet. Když nápověda míří (skoro) stejně jako z, po odečtení průmětu nezbude
nic — a normalizovat něco, co je jen zaokrouhlovací chyba, znamená dostat naprosto náhodný směr
délky 1. Solver v takovém případě sáhne po náhradním kolmém směru, který si vyrobí sám
(anyPerpendicular), a testy ověřují, že vyjde kolmý i pro vstupy ležící přesně na
osách — což je zrovna to místo, kde naivní „vynásob to s x̂“ selže.
Vyhodit, ne znormalizovat
Když je vstupní vektor lineárně závislý na předchozích, zbytek po odečtení průmětů je nula (až na zaokrouhlení). Takový vektor se musí zahodit, ne znormalizovat. Znormalizovaný zbytek délky 10⁻¹⁷ je čistý šum, který se tváří jako plnohodnotný směr — a je to nejčastější způsob, jak tahle rutina tiše selže. Kalkulačka v téhle labce takový vektor vypíše jako vyhozený a řekne proč.
Kde se s tím ještě potkáte
- QR rozklad je Gram-Schmidt zapsaný v maticích: Q jsou ty vzniklé kolmé směry, R jsou odečtené průměty. Používá ho každý slušný řešič nejmenších čtverců — viz OptiLab.
- Ortogonalizace rotační matice: po tisících násobení se matice „rozjede“ a přestane být ortonormální. Gram-Schmidt ji srovná zpátky. Viz RotLab.
- Kalibrace kamery hledá rámec z naměřených, tedy nepřesných směrů — a musí skončit s pravoúhlým. Viz VisionLab.
Numerická poznámka. Klasický Gram-Schmidt počítá všechny průměty proti původním vektorům a při skoro rovnoběžných vstupech ztrácí kolmost. Modifikovaná verze odečítá postupně proti už hotovým směrům a je výrazně stabilnější. Solver v téhle labce dělá modifikovanou variantu a navíc druhý průchod (reortogonalizace), což je standardní recept, jak držet kolmost na úrovni strojové přesnosti.