Effiziente Synthese konsistenter Graphen und ihre Anwendungen in der digitalen Signalverarbeitung
Final Report Abstract
In den unterschiedlichen Ingenieursanwendungen wie der Lokalisierung von akustischen Quellen mittels Mikrofongruppen oder der Abstands- und Geschwindigkeitsmessung in Fahrerassistenzsystemen im Automobil kommt es bei den aktuellen Verfahren zu Mehrdeutigkeiten in den Messzuordnungen. So können z.B. die Laufzeitdifferenzen von unterschiedlichen akustischen Quellen nicht eindeutig einem Ziel zugeordnet werden. Dies führt zu vielen Falschdetektionen oder muss mit aufwendigen Verfahren wie der Independent Component Analysis (ICA) aufgelöst werden. Hier setzt dieses DFG-Projekt an und leist mit graphentheoretischen Werkzeugen dieses Kombinationsproblem in einer effizienten Art und Weise. Dabei nutzen wir den Umstand aus, dass die Summe der betrachteten Messgrößen entlang einer Masche von Sensoren i, j,..., l Null ergibt. Das ergibt sich aus der Definition der Messgrößen als Differenzmessungen wij = pi -pj, wobei wij die Laufzeitdifferenzen, Geschwindigkeitsdifferenzen oder Positionsdifferenzen (Abstand) darstellen. Die gewünschten Messgrößen pi, wie Laufzeit, Geschwindigkeit oder Position, können oft nicht direkt gemessen werden. In dem vorliegenden Projekt haben wir die unterschiedlichen Problemstellungen aus der Signalverarbeitung auf ein graphentheoretisches Problem abgebildet und konnten so das Problem als Suche nach Teilgraphen mit einer Nullsumme entlang aller Maschen beschreiben. Dieser Algorithmus wird als Synthese konsistenter Graphen (engl. synthesis of consistent graphs, SONG) bezeichnet. Dafür haben wir zum einen vorhandene Verfahren aus der Graphentheorie wie die Suche nach zusammenhängenden Teilgraphen und die Suche nach fundamentalen Maschen untersucht und ihre Vor- und Nachteile für dieses Projekt genau analysiert. Zum anderen haben wir für die Synthese konsistenter Graphen neben dem Verfahren des Backtracking aus der Informatik einen neuen Algorithmus CCGsearch entwickelt, der eine flexible Synthese von Teilgraphen ermöglicht. Dieser Algorithmus beruht auf einem neuen Graphentyp, namlich dem Kompatibilitäts-Konflikt Graph (engl. compatibility-conflict graph, CC-Graph), der den finalen Schritt des Zusammenfügens der konsistenten Maschen bestmöglich widerspiegelt. CCGsearch wurde in diesem Projekt als kombinatorisches Optimierungsverfahren entwickelt, analysiert und die Komplexität abgeschätzt. Um die Effizienz des SONG-Algorithmus auch unter realen Bedingungen zu prüfen, wurde er in Laufzeitdifferenz (engl. time difference of arrival TDOA) basierte akustische Lokalisierung eingebunden und konnte so in einem Echtzeitsystem angewendet werden. Der fachübergreifende Ansatz der Synthese konsistenter Graphen führte zu einer Best-Paper Auszeichnung.
Publications
- 2010, “A graph theoretical framework for consistent time differences of arrival”, ITG Fachtagung Speech Communication
M. Kreißig and B. Yang
- “Efficient synthesis of consistent graphs”, 2010, European Signal Processing Conference
M. Kreißig und B. Yang
- “An introduction to consistent graphs and their signal processing applications”, 2011, IEEE Int. Conf. on Acoustics, Speech and Signal Processing
B. Yang und M. Kreißig
- “An efficient algorithm for the synthesis of fully consistent graphs”, 2012, IEEE Int. Conf. on Acoustics, Speech and Signal Processing
M. Kreißig und B. Yang
- “A Graph-Based Approach to Assist TDOA Based Localization”, 2013, Int. Workshop on Multidimensional Systems
B. Yang und M. Kreißig
- “Fast and reliable TDOA assignment in multi-source reverberant environments”, 2013, IEEE Int. Conf. on Acoustics, Speech and Signal Processing
M. Kreißig und B. Yang
- “Joint consistent graph synthesis and speed of sound estimation for acoustic localization in multi-source reverberant environments”, 2013, Int. Workshop on Multidimensional Systems
P. Annibale, R. Rabenstein, M. Kreißig and B. Yang
