implementation.tex

\section{Umsetzung der einzelnen Module}
Der Kern unserer Idee ist die Richtungsbestimmung, die aus den Phasendifferenzen der verschiedenen Wellen bei verschiedenen Mikrofonen eine Richtung berechnet. Um diese Komponente überprüfen und das Verfahren anwenden zu können, haben wir die verschiedenen Module implementiert (siehe Abbildung~\ref{fig:flowchart}). Hierbei haben wir diese wie vorgesehen so universell umgesetzt, dass wir das Richtungsbestimmungsmodul sowohl mittels einer Simulation als auch mittels eines praktischen Aufbaus überprüfen können. Das nachfolgende Kapitel beschreibt eben diese Umsetzung in der Reihenfolge, mit der das Signal verarbeitet wird; von der Aufnahme der Schallquellen bis zur Ausgabe der Positionsdaten.
\begin{figure}[H]
	\includegraphics[width=\linewidth]{img/flowchart}
    \caption{Der modulare Aufbau unseres Konzeptes\label{fig:flowchart}}
\end{figure}

\subsection{Audiosimulation (Modul 1)}
\begin{wrapfigure}{r}{0.5\textwidth}
    \centering
    \includegraphics[width=0.5\textwidth]{img/bildsimulation}
    \caption{Screenshot der Simulation, die roten Punkte stellen die Mikrofone dar, die schwarzen die Schallquellen und die grünen die georteten Positionen, aus denen man die Richtung erkennen kann.}
\end{wrapfigure}
Um die Richtungsbestimmung unabhängig von Störfaktoren wie Rauschen und Reflexionen des Schalls an Wänden oder anderen Gegenständen zu überprüfen, haben wir zunächst eine Simulation entwickelt. Die Simulation kann beliebig viele Mikrofone an beliebigen Positionen simulieren. Leider konnten wir keine bestehenden Lösungen für die Simulation von dreidimensionalem Ton, wie \textit{OpenAL}~\cite{OpenAL}, welches eine Programmbibliothek für die Simulation von Schall ist, verwenden, da bei diesen die Anzahl der Mikrofone limitiert ist und die Phase des Audiosignals in der Simulation vernachlässigt wird. Da die Funktion unserer Richtungsbestimmung unabhängig von den Amplituden der Schallquellen bei den einzelnen Mikrofonen ist, haben wir eine Simulation geschrieben, die rein auf die Phase und die Laufzeit beschränkt ist. Um eine interaktive Benutzung und eine leichte Überprüfung der Richtungsbestimmung zu gewährleisten, besitzt die Simulation eine graphische Benutzeroberfläche, mit der man interaktiv Schallquellen hinzufügen und entfernen kann. Außerdem lässt sich mit dieser gezielt der Einfluss verschiedener Störfaktoren untersuchen. Zusätzlich kann die Simulation auch die bestimmten Richtungen darstellen und ermöglicht damit einen einfachen Vergleich der bestimmten und simulierten Richtungen.


\subsection{Hardware (Modul 1)}
Um das durch die Simulation evaluierbare Verfahren praktisch zu testen und zu nutzen, muss nur die Quelle der Daten, also das erste Modul, ausgetauscht werden. Die Aufgabe des ersten Moduls ist es nun nicht mehr, virtuelle Mikrofone  zu simulieren, die virtuelle Schallquellen aufnehmen. Stattdessen müssen die Signale echter Mikrofone, welche echte Schallquellen aufnehmen, eingelesen werden. Um die Signale der Mikrofone mit einem Computer zu verarbeiten, müssen sie digitalisiert werden. Zusätzlich benötigt man eine alternative Implementation des ersten Moduls, die die Daten von der Hardware annimmt und an das zweite Modul weiterleitet. Hierbei kommen wieder die Vorteile unserer modularen Vorgehensweise zum Tragen, da nur das erste Modul ersetzt werden muss und die gesamte restliche Software beibehalten werden kann. Dies sorgt auch dafür, dass die Simulation und die Realwelttests immer die gleichen Auswertungsalgorithmen verwenden und so sehr gut vergleichbar sind.
\subsubsection{Mikrofonarray}
\begin{figure}[H]
    \centering
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics[width=\textwidth]{img/v1.png}
        \caption{Prototyp 1\label{fig:prototyp1}}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics[width=\textwidth]{img/v2.png}
        \caption{Prototyp 2\label{fig:prototyp2}}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics[width=\textwidth]{img/v3.png}
        \caption{Prototyp 3\label{fig:prototyp3}}
    \end{subfigure}
    \caption{Unsere verschiedenen Prototypen\label{tet}}
\end{figure}
\paragraph{Anforderungen}
Die erste Komponente, die bei einem realen Aufbau der Messapparatur eine wichtige Rolle spielt, ist die der Schallwandlung. Dies wird durch Mikrofone realisiert. An diese gibt es einige Anforderungen. Die wichtigste Anforderung ist, dass sie eine möglichst kugelförmige Charakteristik haben.
Außerdem erzeugen kleine Mikrofone weniger Schallschatten und Reflexionen. Des Weiteren sollte das Signal-Rausch-Verhältnis möglichst groß sein, da Rauschen die Messungen unpräziser macht~\cite{Rausch}.

\paragraph{Erster Prototyp}
Wir haben drei Prototypen unseres Mikrofonarrays konstruiert und diese dabei optimiert. Der erste Prototyp (siehe Abbildung~\ref{fig:prototyp1}) unseres Mikrofonarrays bestand aus 4 Mikrofonen, die in einem Tetraeder angeordnet waren, da dies das absolute Minimum für eine dreidimensionale Richtungsbestimmung ist. Für diesen haben wir Elektretmikrofonkapseln verwendet, da diese klein sind, verhältnismäßig gute Signalqualität bieten und teilweise eine Kugelcharakteristik besitzen.
Die Charakteristik der Mikrofone sollte möglichst gleichmäßig sein, da nur so aus allen Richtungen Töne mit gleicher Qualität aufgenommen werden können. Wenn zum Beispiel alle Mikrofone eine Nierencharakteristik aufweisen und sie in einem gleichseitigen Dreieck angeordnet sind, liefert mindestens ein Mikrofon ein deutlich schwächeres Signal als die anderen, was dazu führt, dass die Phasenlagen der einzelnen Wellen ungenauer bestimmt werden, und hierdurch auch die Richtungsbestimmung ungenauer wird.

\paragraph{Vermessen von Mikrofoncharakteristika}
\begin{wrapfigure}{R}{0.5\textwidth}
	\centering
	\includegraphics[width=0.5\textwidth]{img/chara_mess}
	\caption{Unsere Apparatur zur Messung der Charakteristik eines Mikrofons.}
\end{wrapfigure}
Um unter diesem Aspekt geeignete Elektretmikrofonkapseln zu finden, haben wir die Charakteristiken verschiedener Mikrofone mittels einer selbst entwickelten Messapparatur und einer selbst entwickelten Messsoftware überprüft. Unsere hierfür entwickelte Messapparatur sendet mittels eines Lautsprechers eine Sinus-Schwingung aus und misst, wie stark diese vom Mikrofon aufgenommen wurde. Danach dreht sie das Mikrofon um einen festgelegten Winkel weiter und führt erneut eine Messung durch. Dieser Vorgang wird solange wiederholt, bis das Mikrofon einmal um \ang{360} gedreht wurde.
Die so ermittelten Daten können nun mittels des freien Plottingprogramms \textit{gnuplot}~\cite{Gnuplot} visualisiert werden, um die Richtcharakteristik darzustellen.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.45\linewidth]{img/badMic}
    \includegraphics[width=0.45\linewidth]{img/goodMic}
    \caption{Vergleich der Richtcharakteristik zwei verschiedener Mikrofone.\label{fig:caracter}}
\end{figure}
Auf den beiden Grafiken ist die gemessene Amplitude des Mikrofons über den Winkel aufgetragen. Bei der linken Grafik kann an feststellen, dass das vermessene Mikrofon eine sehr ungleichmäßige Charakteristik aufweist, diese Mikrofone haben wir zu Anfang verwendet. Auf der rechten Seite ist die Charakteristik der Mikrofone zu sehen, die endgültig für den ersten Prototypen benutzt haben.\\
Um die Elekretmikrofonkapseln an das Audiointerface anzuschließen, benötigt man zusätzlich eine Schaltung, welche das unsymmetrische Signal der Elektretmikrofonkapsel in ein symmetrisches Signal für das Audiointerface umwandelt. Außerdem muss die Schaltung die Phantomspeisung, die das Audiointerface bereitstellt und eine Spannung von \SI{48}{\volt} hat, in eine Tonaderspeisung für das Mikrofon konvertieren. Hierfür kommt die Schaltung von~\cite{Powering_microphones} zum Einsatz.
Die Mikrofone unseres ersten Prototyps haben wir an den Ecken eines gleichseitigen Tetraeders angebracht, da dies zur gleichmäßigsten Ortungsgenauigkeit führt. Um die Charakteristik der Mikrofone möglichst wenig zu verändern, haben wir die Mikrofone nur an ihrem Kabel mit dem Tetraeder verbunden. Dadurch ist der Schallschatten durch den Tetraeder relativ gering. Das Mittelstück des Tetraeders haben wir mithilfe eines 3D-Druckers hergestellt (siehe Abbildung~\ref{fig:prototyp1}).\\

\paragraph{Zweiter und dritter Prototyp}
Der zweite Optimierungsschritt des Mikrofonarrays (siehe Abbildung~\ref{fig:prototyp2}) beinhaltete eine Erhöhung der Mikrofonanzahl von \num{4} auf \num{8} und einen Umstieg auf eine würfelförmige Anordnung. Hierdurch stehen mehr Informationen für den Richtungsbestimmungsalgorithmus zur Verfügung und das Gleichungssystem wird überbestimmt. Auch sind wir von Elektretmikrofonkapseln auf professionelle Messmikrofone umgestiegen, da diese eine definierte Charakteristik haben und ein besseres Signal-Rausch-Verhältnis aufweisen.

Da beim zweiten Prototyp des Mikrofonarrays der Abstand zwischen den Mikrofonen sehr groß war und dadurch das nutzbare Frequenzspektrum nach oben hin sehr stark eingeschränkt wurde, war das Ziel des dritten Prototyps (siehe Abbildung~\ref{fig:prototyp3}) diese wieder näher aneinander zu rücken. Dieses Ziel erreichten wir durch eine Umkehrung der Mikrofonrichtung, so dass diese nun nicht mehr von innen nach außen, sondern von außen nach innen zeigen.
\subsubsection{Audiointerface}
Auch für das Audiointerface, also die Verbindung zwischen Mikrofonen und Computer, gibt es bestimmte Voraussetzungen. So benötigt unser Verfahren mindestens \num{4} Mikrofone, jedoch lässt es sich einfach auf mehr Kanäle erweitern, was der Genauigkeit zugute kommt. Daher haben wir ein Audiointerface mit möglichst vielen Kanälen gesucht. Eine weitere wichtige Anforderung an das Audiointerface ist eine hohe Auflösung, da hierdurch die Signalqualität verbessert wird und eine digitale Verstärkung bei ausreichender Audioqualität möglich ist.
\subsubsection{Software}
Um die reale Mikrofone für die Richtungsbestimmung zu verwenden, muss noch eine Verbindung zwischen dem Audiointerface und dem nächsten Modul geschaffen werden. Durch unseren modularen Aufbau lässt sich dies leicht implementieren. Wir haben dazu ein Programm in Java entwickelt, das fähig ist, mehrkanalige Audiosignale in Echtzeit aufzunehmen und über TCP/IP an die Fourier-Transformation weiterzuleiten. Zur Umsetzung haben wir die Programmbibliothek \textit{portaudio}~\cite{portaudio} verwendet. Diese Programmbibliothek hat den Vorteil, dass mehrere Audiokanäle zeitsynchronisiert eingelesen werden können. Dies ist sehr wichtig, damit unser Verfahren zur Richtungsbestimmung, welches auf der relativen Phasenlage basiert, funktioniert. \textit{Portaudio} haben wir in Java über das Java Native Interface (JNI) benutzt.

\subsection{Fourier-Transformation (Modul 2)}
Dieses Modul teilt die Audio-Signale in einzelne Sinuswellen auf und bestimmt deren Phase und Amplitude. Dies lässt sich mit einer diskreten Fourier-Transformation bewerkstelligen. Die diskrete Fourier-Transformation bestimmt aus einem zeitdiskreten Signal die einzelnen Sinusschwingungen mit ihrer zugehörigen Phase und Amplitude, die zusammen das Signal bilden. Ein schneller Algorithmus, um die diskrete Fourier-Transformation eines Signals zu berechnen, ist die Fast Fourier-Transformation (FFT). Dieser ist schnell genug, um eine Echtzeitverarbeitung des Signals zu ermöglichen. Als Implementation der FFT haben wir \textit{FFTW}~\cite{FFTW} verwendet, da \textit{FFTW} kostenlos, opensource und vergleichsweise schnell ist.
Das Fourier-Transformations-Modul wurde aus Performancegründen in \textit{C++} implementiert.\\
Durch eine diskrete Fourier-Transformation von $n$ reellen Zahlen erhält man eine Liste aus $n$ komplexen Zahlen. Eine komplexe Zahl $z$ an der Stelle $j$ enthält die Amplituden- und Phaseninformation für die Frequenz~$f$:
\begin{equation}
f = j\frac{r}{n}
\end{equation}
Dabei ist $r$ die Abtastrate des Signals. Die Amplitude $A$ des Sinus lässt sich mit dem Betrag der komplexen Zahl berechnen und die Phase $\phi$ mit dem Arcus-Tangens. Dies entspricht der Koordinatentransformation von einem kartesischen in ein polares Koordinatensystem:\\
\begin{minipage}{0.49\textwidth}
   \begin{align}
    A &= \sqrt[]{{\Re(z)}^2 + {\Im(z)}^2}\\
    \phi &= \operatorname{atan2}(\Im(z), \Re(z))\\
    \operatorname{atan2}(y,x) &:= \begin{cases} \arctan\frac{y}{x} & \mathrm{für}\ x > 0\\ \arctan\frac{y}{x} + \pi & \mathrm{für}\ x < 0,\ y \geq 0\\ \arctan\frac{y}{x} - \pi & \mathrm{für}\ x < 0,\ y < 0\\ +\pi/2 & \mathrm{für}\ x = 0,\ y > 0\\ -\pi/2 & \mathrm{für}\ x = 0,\ y < 0\\ 0 & \mathrm{für}\ x = 0,\ y = 0 \end{cases}
    \end{align}
\end{minipage}
\begin{minipage}{0.49\textwidth}
    \begin{figure}[H]
        \centering
        \hspace*{-2cm}\input{img/polarconvert.tex}
        \caption{Transformation vom kartesischen zu polaren Koordinatensystem\label{fig:polarconvert}.}
    \end{figure}
\vspace{10pt}
\end{minipage}
\\
Die Verwendung der oben definierten Funktion $\operatorname{atan2}(y,x)$ anstelle von $\arctan\frac{y}{x}$ sorgt dafür, dass der richtige Winkel berechnet wird. $\arctan\frac{y}{x}$ liefert nur Winkel von \ang{-90} bis \ang{90}, deswegen muss anhand des Vorzeichens von $x$ und $y$ bestimmt werden, in welchem Quadranten der Punkt liegt und der von $\arctan\frac{y}{x}$ gelieferte Winkel dementsprechend interpretiert werden.

Das in Frequenz, Phase und Amplitude konvertierte Ergebnis der Fourier-Transformation wird dann gefiltert. Alle Frequenzen mit einer Amplitude, die unterhalb einer bestimmten Grenze liegen, werden verworfen. Die verbleibenden Frequenzen werden an das Richtungsmodul übermittelt.

\subsection{Richtungsmodul (Modul 3)}
Die von der Fourier-Transformation bestimmten Tripel aus Frequenz, Phase und Amplitude werden vom Richtungsmodul weiterverarbeitet. In das Richtungsmodul können verschiedene Methoden der Richtungsbestimmung eingesetzt werden. Die ermittelten Richtungen werden an das Ausgabemodul weitergesendet.
Das Richtungsmodul haben wir in C++ geschrieben und dabei \textit{LAPACK}~\cite{Anderson:1990:LPL:110382.110385} verwendet.
\subsection{Ausgabemodul (Modul 4)}
\begin{wrapfigure}{r}{0.4\textwidth}
	\centering
    \includegraphics[width=0.4\textwidth]{img/output}
    \caption{Screenshot unseres Beispiel-Ausgabemoduls\label{fig:output}}
\end{wrapfigure}
Wir haben ein Beispiel-Ausgabemodul in Javascript implementiert. Mit diesem ist es möglich, die Positionsdaten zu visualisieren, was das unmittelbare Überprüfen unseres Verfahrens stark vereinfacht. Die Programmiersprache Javascript haben wir gewählt, damit dieses Ausgabemodul auf jedem Endgerät mit modernem Webbrowser, wie z.B. Smartphones oder Laptops, ausgeführt werden kann.\\
Die Simulation enthält eine weitere Implementation eines Ausgabemoduls. Auch dieses visualisiert die bestimmten Richtungen, erlaubt es aber, diese auf der gleichen Benutzeroberfläche wie die Sollrichtung anzuzeigen. Dies gibt ein sehr direktes Feedback beim Entwickeln des Algorithmus zur Richtungsbestimmung. Dieses letzte Modul könnte allerdings, dank unseres modularen Konzeptes, bei Bedarf auch anders, z.B. als Plugin für eine \textit{Digital Audio Workstation} (\textit{DAW}), implementiert werden.

\subsection{Zentrale Steuerung}
Um die Konfiguration der einzelnen Module zu vereinfachen und schneller an neue Situationen anpassen zu können, haben wir ein Programm entwickelt, dass alle Module mit der gewünschten Konfiguration startet und mit dem man alle Module konfigurieren kann. Außerdem überwacht das Programm die Ausführung aller Module, gibt etwaige Fehlermeldungen aus und startet die einzelnen Module nach kritischen Fehlern neu.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.475\textwidth]{img/GUI}
    \hfill
    \includegraphics[width=0.475\textwidth]{img/GUI2}
    \caption{Screenshots der Steuerungsoberfläche\label{fig:gui_screenshot}}
\end{figure}
\pagebreak
\subsection{Testen der einzelnen Module}
\begin{wrapfigure}{r}{0.5\textwidth}
    \centering
    \includegraphics[width=0.5\textwidth]{img/glplot}
    \caption{Screenshot unseres Plottingprogramms\label{fig:glplot}}
\end{wrapfigure}
Ein weiterer Vorteil der Modularität ist, dass jedes Modul unabhängig von den anderen Modulen funktionsfähig ist. Dadurch kann die korrekte Funktionsweise für jedes Modul einzeln überprüft werden und man kann Fehler besser lokalisieren.
Die Audiosimulation haben wir mithilfe eines selbstgeschriebenen Plottingprogramms überprüft. Dieses stellt die von der Audiosimulation versendeten Samples in Abhängigkeit zur Zeit dar. Damit kann manuell die Phasendifferenz von dem Graphen abgelesen und mit dem erwarteten Wert verglichen werden.
Die Fourier-Transformation konnten wir mit der vorher überprüften Audiosimulation testen. Dazu haben wir die von der Fourier-Transformation bestimmten Tripel aus Frequenz, Phase und Amplitude mit den tatsächlich in der Simulation eingestellten Werten verglichen.
Durch das Testen der einzelnen Module konnten wir effizient die vorhandenen Fehler, wie die falsche Berechnung der Phase und einen Fehler in der Distanzberechnung der Audiosimulation, finden und beheben.