Master's Thesis

Modern methods of three quadrics in three dimensions (3Q3) and their utilisation in multilateration systems

Final Thesis 1.1 MB

Author of thesis: Bc. et Bc. David Kamenský

Acad. year: 2025/2026

Supervisor: Ing. Pavel Loučka, Ph.D.

Reviewer: Mgr. Jana Procházková, Ph.D.

Abstract:

This master's thesis, developed in collaboration with ERA a.s., addresses the challenge of precise target localisation in three-dimensional space using passive multilateration systems that rely on the Time Difference of Arrival (TDOA) of signals at multiple sensors. The core mathematical difficulty involves solving a system of non-linear equations, which this work approaches by transforming them into a system of three quadrics (3Q3).
The research evaluates several established algorithms, benchmarking them for accuracy, numerical stability, and computational efficiency. The Efficient 3Q3 (E3Q3) solver is identified as the most suitable baseline, as its non-iterative nature allows it to operate two to four orders of magnitude faster than competing methods while maintaining high accuracy. To overcome numerical instabilities caused by measurement errors, we propose the Modified E3Q3 (ME3Q3) algorithm. This method utilises the unscented transform to deterministically shift TDOA vectors via sigma points, significantly improving reliability.
Results indicate that while ME3Q3 offers a major stability leap in 3×TDOA scenarios, its improvement in 2×TDOA cases (utilising a substitute sphere) is more incremental. Additionally, the thesis explores various error estimation techniques to effectively select the best candidate from multiple potential intersection points.

Keywords:

Multilateration Systems, Time Difference of Arrival (TDOA), Quadrics, Homotopy continuation, Resultant, E3Q3 Solver, Numerical Stability, Unscented Transform, Hyperboloids

Date of defence

08.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Student prezentoval práci, školitel přečetl svůj posudek, byl přečten posudek oponenta. K otázkám oponentky: Která metoda byla použita k hledání polynomu osmého stupně vzniklého v solveru E3Q3 a proč? - NumPy metoda roots, protože je velmi dobře zavedená a otestovaná. Vysvětlit geometrické pozadí konstrukce trojúhelníku a odhad chyby - názorně vysvětleno. Může být metoda nasazena v praxi, když byla data k testování generována uměle? Ano a bude testována i na reálných datech. dr.Rozehnalová - Nově zkonstruované odhady v TDOA metodě jsou aproximace? prof.Lomtatidze - Jak je to se stabilitou? Vše zodpovězeno.

Language of thesis

English

Faculty

Department

Study programme

Mathematical Engineering (N-MAI-P)

Composition of Committee

doc. Mgr. Petr Vašík, Ph.D. (předseda)
doc. RNDr. Martin Kolář, Ph.D. (místopředseda)
prof. Aleksandre Lomtatidze, DrSc. (člen)
Ing. Ivan Eryganov, Ph.D. (člen)
Ing. Petra Rozehnalová, Ph.D. (člen)

Supervisor’s report
Ing. Pavel Loučka, Ph.D.

Diplomová práce Davida Kamenského se zabývá lokalizací cíle v trojrozměrném prostoru pomocí multilateračních systémů, a to ve spolupráci se společností ERA a.s. Problém matematicky vede na řešení soustavy tří nelineárních rovnic, kterou lze transformovat na soustavu představující tři kvadriky.

První kapitoly práce se zabývají představením problému a matematickým pozadím jeho řešení, včetně porovnání různých metod řešení. Pozornost je dále věnována modifikovanému algoritmu E3Q3 (zkráceně ME3Q3), který autor práce vyvinul. Poté se práce zabývá různými způsoby odhadu chyb a nakonec jsou shrnuty výsledky porovnání jednotlivých metod na zvolených datech.

Práce svým obsahem zasahuje do několika matematických disciplín, konkrétně je na pomezí algebry, geometrie, numerických metod a statistiky, autor tedy musel nastudovat netriviální objem teorie týkající se různých oblastí. Zásadní částí práce je také implementace příslušných metod v Pythonu a jejich následné otestování. Velice oceňuji autorovu samostatnost v řešení zadaného problému, zvláště s ohledem na množství různých variant algoritmů, které se mu podařilo vytvořit a ozkoušet. Detailní diskuze chybovosti metod činí z práce také skvělý podklad pro použití popsaných algoritmů na reálné problémy.

Práce je vhodně členěná a čitelná, obsahuje velké množství ilustračního materiálu, použitá angličtina je na dobré úrovni.

Mohu říci, že cíle práce byly splněny. Celkově hodnotím práci jako vynikající a navrhuji známku „výborně/A“.
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod A
Vlastní přínos a originalita A
Schopnost interpretovat dosažené výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii A
Logické uspořádání práce a formální náležitosti A
Grafická, stylistická úprava a pravopis A
Práce s literaturou včetně citací A
Samostatnost studenta při zpracování tématu A

Grade proposed by supervisor: A

Reviewer’s report
Mgr. Jana Procházková, Ph.D.

Předložená diplomová práce se zabývá řešením průniku tří kvadrik v oblasti pasivních multilateračních systémů. Jedná se o odborně náročné a současně prakticky relevantní téma. Autor jej zpracoval na velmi dobré úrovni a vhodně propojuje matematické modelování, numerické metody, algoritmickou implementaci i experimentální vyhodnocení.

Velmi pozitivně hodnotím zejména to, že diplomant nezůstal pouze u rešerše existujících přístupů. Jednotlivé metody implementoval, systematicky porovnal a dále navrhl vlastní rozšíření solveru E3Q3 v podobě metody ME3Q3. Tento vlastní algoritmický přínos považuji za hlavní přínos práce. Navržená metoda zvyšuje robustnost a stabilitu řešení v numericky obtížných situacích. Součástí navrženého přístupu je také využití shiftingu TDOA vektoru pomocí sigma bodů pro zvýšení robustnosti řešení. Pozitivně hodnotím rovněž využití Mahalanobisovy vzdálenosti při hodnocení kandidátních řešení a odhadu jejich spolehlivosti.

Práce je logicky strukturovaná a jednotlivé kapitoly na sebe dobře navazují. Oceňuji také rozsah experimentální části a systematické vyhodnocení solverů z hlediska přesnosti, stability i praktické použitelnosti. Autor prokazuje velmi dobrou orientaci v problematice a schopnost propojit matematickou stránku problému s numerickou implementací.

Autor pracuje s relevantní odbornou literaturou odpovídající řešené problematice. Po formální stránce je práce na velmi dobré úrovni. Text je odborný, konzistentní a jazykově kvalitní. Některé části práce jsou vzhledem ke složitosti problematiky náročnější ke čtení. Zejména v části 6.2 bych uvítala více ilustračních schémat pro vysvětlení geometrických konstrukcí. Kapitola 6.5 navíc působí ve srovnání s ostatními částmi práce poměrně stručně a zasloužila by si podrobnější rozvedení. V úvodní rovnici (2.1) není definované (x_0, y_0, z_0).

Uvedené připomínky však nijak nesnižují celkově vysokou odbornou úroveň práce. Diplomová práce podle mého názoru splňuje požadavky kladené na tento typ závěrečné práce a v některých ohledech je překračuje.

Práci doporučuji k obhajobě.

Navržené hodnocení: A
Evaluation criteria Grade
Splnění požadavků a cílů zadání A
Postup a rozsah řešení, adekvátnost použitých metod A
Vlastní přínos a originalita A
Schopnost interpretovat dosaž. výsledky a vyvozovat z nich závěry A
Využitelnost výsledků v praxi nebo teorii A
Logické uspořádání práce a formální náležitosti A
Grafická, stylistická úprava a pravopis A
Práce s literaturou včetně citací A
Topics for thesis defence:
  1. Data k testování byla generována uměle. Odpovídají reálným situacím, kdy by metoda mohla být nasazena v praxi?
  2. U solveru E3Q3 vzniká ve výsledku polynom osmého stupně, jehož kořeny je třeba numericky určit. Můžete upřesnit, kterou z metod uvedených v části 3.1 jste ve finální implementaci použil a proč jste tuto volbu považoval za nejvhodnější?
  3. V části 6.2 Planar approach používáte geometrickou aproximaci založenou na trojúhelníku ABC a bodech A,B, A', B'. Mohl byste podrobněji vysvětlit geometrické pozadí této konstrukce a objasnit, jakým způsobem z ní plyne odhad chyby ve tvaru d*l/|h|?

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová