Echtzeitsteuerung und Online-Algorithmen

In diesem Kapitel wird die Umsetzung der zeitkritischen Prozesse beschrieben. Dies sind zum einen das unterliegende Betriebsystem RT-Linux, zum anderen die implementierten Online-Algorithmen wie die Linienerkennung und die Flächensegmentierung.

Real-Time Linux

Real-Time Linux ist ein Betriebssystem, bei dem ein kleiner Echtzeitkernel und der Linux Kernel nebeneinander existieren. Es soll erreicht werden, daß die hochentwickelten Aufgaben eines Standardbetriebssystems für Anwendungen zur Verfügung gestellt werden, ohne auf Echtzeitaufgaben mit definierten, kleinen Latenzen zu verzichten. Bisher waren Echtzeitbetriebssysteme kleine, einfache Programme, die nur wenige Bibliotheken dem Anwender zur Verfügung gestellt haben.

Mittlerweile ist es aber notwendig geworden, daß auch Echtzeitbetriebssysteme umfangreiche Netzwerk-Bibliotheken, Graphische Benutzeroberflächen, Datei- und Datenmanipulationsroutinen zur Verfügung stellen müssen. Eine Möglichkeit ist es, diese Features zu den existierenden Echtzeitbetriebssystemen hinzuzufügen. Dies wurde beispielsweise bei den Betriebssystemen VXworks und QNX gemacht. Eine andere Herangehensweise ist, einen bestehenden Betriebssystemkernel dahingehend zu modifizieren, daß dieser Echtzeitaufgaben bewältigt. Ein solcher Ansatz wird von den Entwicklern von RT-IX (Modcomp) verfolgt. RT-IX ist eine UNIX System V Implementation, die auch harte Echtzeitaufgaben bewältigen kann [Kuh98].

Real-Time Linux basiert auf einer dritten Herangehensweise. Ein kleiner Echtzeitkernel läßt ein Nicht-Echtzeitbetriebssystem als einen Prozeß mit niedrigster Priorität laufen. Dabei wird eine virtuelle Maschine für das eingebettete Betriebssystem benutzt.

Real-Time Linux behandelt alle Interrupts zuerst und gibt diese dann an den Linux Betriebssystem-Prozeß weiter, wenn diese Ereignisse nicht von Echtzeit-Prozessen behandelt werden. Durch einen solchen Aufbau sind minimale Änderungen am Linux Kernel nötig, da der Interrupt Handler auf den Echtzeitkernel abgestimmt werden muß. Der Real-Time Linux Kernel selbst ist ein ladbares Modul und kann bei Bedarf eingefügt und entfernt werden. Dieser Kernel stellt hauptsächlich die Schicht zwischen dem Linux Kernel und der Hardware-Interruptebene dar.

Real-Time Linux mutet anfänglich sehr spartanisch an, denn es liegt der Gedanke zugrunde, daß die Prinzipien von harten Real-Time Anwendungen in der Regel nicht vereinbar sind mit komplexer Synchronisation, dynamischer Resourcenverwaltung und allem anderen, was zeitliche Mehrkosten verursacht. Daher werden in der Standardkonfiguration nur sehr einfache Konstrukte zur Implementierung von Prozessen zur Verfügung gestellt, beispielsweise ein einfacher fixed priority scheduler, nur statisch allozierter Speicher und und kein Schutz des Adreßraums. Dennoch kann man mit den gegebenen Mitteln sehr effizient arbeiten, da alle Nicht-Echtzeitkomponenten unter Linux laufen und somit dortige Bibliotheken benutzen können.

Real-Time Programme bzw. Prozesse werden als ladbare Module eingebunden, was das Echtzeitbetriebssystem erweiterbar und einfach zu modifizieren macht. Die Programme werden mit den Standard-Linux-Werkzeugen erzeugt (GNU C compiler). Oftmals übernehmen andere, Nicht-Real-Time Programme die weitere Datenverarbeitung. Da Real-Time Linux keinerlei Mechanismen zum Schutz gegen Überladung der Hardware besitzt, ist es möglich, daß die Real-Time Prozesse die CPU blockieren. In diesem Fall bekommt der Linux Kernel nicht die Chance, eine Zeitscheibe zu bekommen, da er die niedrigste Priorität hat.

Da Real-Time Linux OPENSOURCE ist und da die Module von Real-Time Linux ladbar und damit jederzeit austauschbar, sind, fand eine breite Entwicklung von Zusatzmodulen statt. Als Zusatzmodule stehen zur Zeit alternative Scheduler (z.B. rate-monotonic scheduler), ein Semaphore Modul, IPCs (interprocess communication Mechanismen) und etliche Real-Time device driver zur Verfügung.

Real-Time und Linux-User Prozesse kommunizieren über lock-freie Queues (FIFOs) und shared memory. Anwendungsprogrammierern stellen sich die FIFOs als standard character devices dar, auf die mittels POSIX read/write/open/ioctl zugegriffen wird.

Es hat sich gezeigt, daß Real-Time Linux den Anforderungen eines Echtzeitbetriebssystems sehr nahekommt. Die Worst-Case interrupt latency auf einem 486/33MHz PC liegt unter 30$\mu$s ( $30\cdot 10^{-6}$s) und somit nahe dem Hardwarelimit [RTL98].

Installation von Real-Time Linux

Von Real-Time Linux gibt es verschiedene Versionen. Etliche kommerzielle Hersteller bieten ihre Versionen von dem Betriebssystem Real-Time Linux an. Wir beziehen uns im folgenden auf die frei erhältliche Version dieses Betriebssystems, siehe [ URLFsm].

Real-Time Linux gibt es bereits in der 3. Version. Mit der ersten Version wurde das Konzept implementiert und getestet. In Version 2 wurden etliche Features und die ganze API überarbeitet sowie mit dem Betriebssystem POSIX konform gemacht. Es wird Real-Time Linux Version 2.2a verwendet, die auf dem letzten stabil laufendem Linux Kernel basiert (Kernel Version 2.2.14) (Stand: Juni 2000). Die neue Version 3 basiert auf den noch nicht freigegebenen Kernel der 2.4er Serie.

Die Tabelle 3.1 zeigt die Real-Time Linux Versionen vs. den Linux Kernel Versionen.

Tabelle 3.1: Real-Time Linux Patchliste

Linux Kernel Nummer	Real-Time Patch Version
2.0.27	0.5
2.2.14	2.2
2.2.14	2.2a
2.4.pre-test0	3

Zur Installation benötigt man nur ein lauffähiges Linux. Man lädt sich einen frischen, d.h. ungepatchten Kernel und den Real-Time Linux Patch. Alternativ dazu kann man sich auch die vor-gepatchten Kernelquellen besorgen. Danach folge man den Anweisungen der Installations-Dateien.

Problematisch ist die Installation, wenn man andere Kernelversionen als die zu Real-Time Linux gehörenden verwenden möchte. Der Real-Time Patch läßt sich i.A. nur auf die Kernelversion anwenden, für die er geschrieben wurde. Für den Fall, daß andere Patches angewendet werden müssen, sollte man diese auf den Real-Time Quellcode anwenden. So ist es möglich, ein Real-Time fähiges Betriebssystem und Unterstützung mit USB (Universal Serial Bus) verbinden zu können.

API - die Grundfunktionen

Im folgenden sind die wichtigsten in der Scanner-Software verwendeten Real-Time Interfacefunktionen vorgestellt. Dabei wird die neue POSIX-konforme API V2 verwendet.

Real-Time Scheduler

Die Aufrufe zur Prozeß-Verwaltung sind in der ab Version 2 dem Standard pthread angeglichen wurden. Für einen Real-Time-Prozeß steht folgende Struktur zur Verfügung.

struct rtl_thread_struct {
        int *stack;     /* hardcoded */
        int uses_fp;
        enum rtl_task_states state;
        int *stack_bottom;
        rtl_sched_param sched_param;
        struct rtl_thread_struct *next;
        RTL_FPU_CONTEXT fpu_regs;
        int cpu;
        hrtime_t resume_time;
        hrtime_t period;
        void *retval;
        int pending_signals;
        struct tq_struct free_task;
        void *user[4];
        int errno_val;
        int pad [64];
}; 

typedef struct rtl_thread_struct RTL_THREAD_STRUCT;
typedef RTL_THREAD_STRUCT *pthread_t;

Es genügt daher, einen Thread wie folgt zu definieren.

pthread_t REALTIME_TASK;

Eine Funktion (Prozeß) kann nun diesem Thread zugeordnet und gestartet werden:

int pthread_create(pthread_t  *thread,
                   pthread_attr_t *attr,
                   void *(*start_routine)(void *),
                   (void *arg));

Nun muß der Prozeß periodisch gemacht werden. Dies geschieht mittels folgender nicht-posix konformer (erkennbar an dem Postfix ,, _np``) Funktion

int pthread_make_periodic_np(pthread_t  thread,  
                              hrtime_t start_time,
                              hrtime_t period);

Innerhalb des Prozesses lassen sich die Parameter des Threads (wie beispielsweise die Periode REALTIME_TASK->period) beeinflussen. Der Prozeß läßt sich bis zu dieser Periode mittels der Funktion

int pthread_wait_np(void);

explizit schlafen legen, die Steuerung wird an andere Prozesse zurückgeben. Prozesse mit der Priorität 1 haben die höchste Priorität, der normale Linuxkernel wird mit der niedrigsten betrieben.

Zeit-Verwaltung

Für Zeiten in Real-Time Linux wird die Datenstruktur hrtime_t verwendet. Dies ist ein 64-Bit Integer. Die aktuelle Auflösung der Zeit (in Prozessorticks) durch diese Variable ist hardwareabhängig^3.1, es wird aber garantiert, daß die Auflösungsgenauigkeit unter 1$\mu$s (Mikrosekunde) liegt. Das Symbol HRTIME_INFINITY repräsentiert den maximalen Wert und wird niemals erreicht. Das Symbol HRTICKS_PER_SEC ist definiert als die Ticks pro Sekunde. Die Funktion

hrtime_t gethrtime(void);

liefert die aktuelle Zeit.

FIFO-Handling

Für Linux-Prozesse stehen die Real-Time FIFOs als character devices /dev/rtf0, /dev/rtf1 etc. zur Verfügung. Der Real-Time Prozeß muß die FIFOs explizit erzeugen und ihnen eine Größe geben. Dies geschieht mit der Funktion

int rtf_create(unsigned int fifo, int size);

Innerhalb der Real-Time Applikation kann mit den Funktionen

int rtf_put(unsigned int fifo, char *buf, int count);                   
int rtf_get(unsigned int fifo, char *buf, int count);

auf die FIFOs zugegriffen werden. Eine wichtige Funktion ist der Handler, der immer dann aufgerufen wird, wenn eine Linux-User Programm auf einen FIFO zugreift. Ein solcher Handler wird mit folgender Funktion mit dem FIFO verbunden:

int rtf_create_handler(unsigned  int  fifo,  
                       int  (* handler)(unsigned int fifo)
);

Servos ansteuern mit Real-Time Linux

Servomotoren werden üblicherweise im Modellbau eingesetzt. Handelsübliche Servos haben einen nominalen Winkelbereich von 90 Grad und erzeugen Drehmomente bis zu 150Ncm. Ein Servo verfügt über 3 Anschlußleitungen: Betriebsspannung, Masse und Steuersignal. Alle 20 Millisekunden erwartet der Servo als Steuersignal einen TTL-kompatiblen Impuls von 1 bis 2 Millisekunden Länge. Die Länge des Impulses bestimmt die Stellung des Servos, d.h. 1ms = links, 1.5ms = mitte, 2ms = rechts (vgl. Abbildung 3.1).

Abbildung: Steuersignale für den Servo

Tabelle: Die Auflösung des 3D-Scanners

Auflösung Laserscanner	Auflösung Servo in Grad
in Punkte pro Scanline	1/3	2/3	1
125	28350	18900	9450
250	56700	37800	18900
500	113400	75600	37800

Genauigkeit der Servoansteuerung: Um den Servo genau zu positionieren, muß die Länge des Signals exakt eingehalten werden. Eine Abweichung von 10$\mu$s entspricht ungefähr einer Abweichung von einem Grad. Messungen an unserer eingesetzten Testmaschine (PII, 333MHz) haben ergeben, daß man mit einer maximalen Latenz von 12$\mu s$ rechnen muß. Die durchschnittlichen Abweichung ist 5$\mu s$ und daher die Auflösung des Servos 0.5 Grad. Damit ergeben sich - unter variablen Punktauflösungen des Scanners - Auflösungen, die in Tabelle 3.2 dargestellt sind.

Folgende Skizze veranschaulicht den einfachen Anschluß eines Servomotors an die paralleler Schnittstelle.

Abbildung: Anschluß des Servos an die parallele Schnittstelle des Rechners

Das Verfahren zur Servoansteuerung läßt sich auf bis zu 12 Servos pro parallele Schnittstelle einfach erweitern.

Das Real-Time Modul steuert einen Servo an. Der periodische Prozeß in diesem Modul besteht im wesentlichen aus einer Schleife, die endlos durchlaufen wird. Als erstes wird die Zeit in Prozessorticks berechnet und überprüft, ob der Prozeß zu früh ausgeführt wird (early scheduling). Wenn die 20 ms erreicht sind, wird an der Leitung der parallelen Schnittstelle das TTL-Signal angelegt. Danach legt sich der Prozeß eine Zeit lang schlafen. Diese Zeit bestimmt die Stellung des Servos. Anschließend wird das Signal wieder gelöscht und die Kontrolle bis zum nächsten Durchgang an andere Prozesse abgegeben. Damit läßt sich bereits eine Stepper-Funktion realisieren.

Das Modul ist auch in der Lage, den Motor kontinuierlich zu drehen und nach erfolgter Drehung dem Anwendungsprogramm dies mitzuteilen. Zur Kommunikation werden 2 Real-Time FIFOs benutzt.

Durch den ersten FIFO ( /dev/rtf0) teilt das Anwendungsprogramm über folgendes Telegramm die Anweisungen mit:

struct msg_struct{
    char option;
    hrtime_t data1;
    hrtime_t data2;
    hrtime_t time;
};

Ist das übermittelte Zeichen ein N, so wird der Servo angewiesen, die in data1 übermittelte Zeit (in Prozessorticks) als Highimpuls auszugeben.
Ist das übermittelte Zeichen T, so wird der Servo zwischen den Stellungen, die durch data1 und data2 spezifiziert sind, bewegt. Dabei wird jedesmal das auszugebende Signal um time Ticks erhöht bzw. erniedrigt. Dadurch konnte auf die Einbindung von floating-point Routinen verzichtet werden. Es ist prinzipiell möglich, floating-point Routinen statisch zu einem Real-Time Modul zu linken, da diese keine UNIX Systemaufrufe enthalten.

Der zweite FIFO ( /dev/rtf1) wird dazu benutzt, um dem Anwendungsprogramm das Ende einer Drehung mitzuteilen. Es wird nach Beenden der Drehung immer ein D in den FIFO geschrieben. Mittels non-blocking Fileoperationen kann das Anwendungsprogramm diesen Status kontinuierlich abfragen.

Meßdatenverarbeitung

Definition 1 (Scan-Punkt)   Ein Scan-Punkt $s_i = (\xi_i,\zeta_i,\phi_i)$ ist ein 3-Tupel, bestehend aus den 2D-Koordinaten $\xi_i, \zeta_i \in \mathbbm{N}$ sowie einem Winkel $\phi_i$ als der Winkel zwischen der aktuellen Scanebene und der $(X,Z)$-Ebene, der Grundfläche im Raum.

Definition 2 (Scan)   Ein Scan $S = (s_i)_{i=1,\dots, n}$ ist eine Folge von Scan-Punkten, welche alle in einer Ebene liegen ( $\phi_k = \phi_l \;\forall\, k,l \in \{1,\dots,n\}$).

Die bisherigen Definitionen beziehen sich auf einen zweidimensionalen Scan, wie er von dem Laserscanner direkt übermittelt wird. Im folgenden nun die Überleitung zum Dreidimensionalen.

Definition 3 (3D-Scan)   Ein 3D-Scan $S_{\text{3D}}= (S_j)_{j=1,\dots, m} = (s_{ij})$ besteht aus einer Folge von (ebenen) Scans. $s_{kl}$ bezeichnet somit den $k$-ten Punkt des $l$-ten Scans.

Definition 4 (Punkt)   Ein gescannter Punkt $p$ wird repräsentiert als ein Tripel $(x, y, z) \in \mathbbm{N}^3$.
Die Abbildung $(\text{\cm coord}_i)_{i \in \{1,2,3\}} \colon \mathbbm{N}^3 \to \mathbbm{N}$ sei definiert als

$$_i\bigl(p = (x, y, z)\bigr) := \begin{cases}x & \text{falls } i = 1 \\ y & \text{falls } i = 2 \\ z & \text{falls } i = 3\:. \end{cases}$$ (3.1)

Definition 5 (Linie)   Eine Linie $l = (p_1, p_2)$ besteht aus Anfangs- sowie Endpunkt, das bedeutet $l \in \mathbbm{N}^3 \times \mathbbm{N}^3$. Sei $l$ eine Linie, so liefert die Abbildung $\text{\cm head}(l)$ den Startpunkt der Linie, $\text{\cm head}\colon (\mathbbm{N}^3\times\mathbbm{N}^3) \to \mathbbm{N}^3$. Entsprechend liefert $\text{\cm tail}\colon (\mathbbm{N}^3\times\mathbbm{N}^3)\to \mathbbm{N}^3$ den Endpunkt von $l$.

Definition 6 (Fläche)   Eine Fläche $f = (l_1, l_2)$ ist definiert als die Fläche, die zwischen zwei Linien, einer Start- sowie einer Endlinie, eingeschlossen wird, $f \in \bigl((\mathbbm{N}^3 \times \mathbbm{N}^3) \times (\mathbbm{N}^3 \times \mathbbm{N}^3) \bigr)$.

Definition 7 (3D-Scan (2))   Als Alternative zu Definition (3) läßt sich ein 3D-Scan auch betrachten als eine Folge von Punkten oder Linien aus dem 3D-Raum:

$$S_{\text{3D}}' = (S_j) = (p_{ij}) \qquad\text{bzw.}\qquad S_{\text{3D}}'' = (S_j) = (l_{ij}).$$ (3.2)

Linienerkenner

Der erste Schritt der Meßdatenverarbeitung ist die Linienerkennung. Sie dient in erster Linie zur Datenreduktion für die nachfolgenden Schritte der Segmentierung und Objekterkennung. Linenerkenner auf 2D Laserscannerdaten werden schon recht erfolgreich in herkömmlichen Anwendungen zur Navigation eingesetzt [Arr96]. Die dort eingesetzten Linienerkenner sind speziell für Laserscanner geeignet.

Wir haben zwei Linienerkenner implementiert. Der erste Algorithmus von Surmann und Liang [Pau98] ist ein einfacher Online-Algorithmus zum Detektieren von Linien mit der Zeitkomplexität $\O(n)$. Der zweite Linienerkenner ist die aus der Bildverarbeitung bekannte Houghtransformation [Hab91]. Die Houghtransformation ist recht gut für unsere Zwecke geeignet, da sie auf einem schwarz/weiß Bild arbeitet. Somit sind die Scan-Punkte die einzigen Bildpunkte. Dadurch ist die Houghtransformation immer noch recht schnell, mit der Zeitkomplexität $\O(c \cdot n), \quad c = \sqrt{(\Delta x)^2 + (\Delta y)^2}$, obwohl die Konstante wegen der großen Scanreichweite recht groß werden kann. Desweiteren liefert die Houghtransformation nicht nur die einzelnen Liniensegmente, sondern ebenfalls eine allgemeine Geradengleichung der Form $y=a \times x +b$. Diese Geradengleichung entspricht einer Ausgleichsgerade, die mehrere unterbrochene Liniensegmente verbindet. Derartige Liniensegmente treten beispielsweise an Wänden auf, die durch Nischen, Vorsprünge oder Türen unterbrochen sind.

Einfacher Linienerkenner

Der hier vorgestellte Linienerkenner wurde von Surmann und Liang speziell für 2D-Laserscanner entwickelt. Er kommt bei Robotern, die lediglich über 2D-Scanner zur Hindernisdedektierung verfügen, zum Einsatz. Der größte Vorteil dieses Verfahrens ist die Geschwindigkeit, denn dieser einfache Linienerkenner ist in der Praxis noch deutlich performanter als die ohnehin schon schnelle Houghtransformation.

Der Linienerkenner funktioniert in zwei Schritten,

1. Datenreduktion
2. Linienerkennung

welche sequentiell abgearbeitet werden.

Die Datenreduktion

In diesem Schritt werden die Meßwerte pro 2D-Scan (bis zu 500) reduziert. Dabei werden sukzessive Meßwerte genau dann zu einem Punkt zusammengefaßt, wenn ihr Abstand voneinander einen vorher festgelegten Wert nicht überschreitet. Dieser Wert wurde als stepDistance bezeichnet und stellt einen Parameter dar, mit dem die Güte der Datenreduktion beeinflußt werden kann.

Die Abbildung 3.3 zeigt einen 2D-Scan, Abbildung 3.4 die dazugehörigen reduzierte Datenmenge. Im Beispiel wurde mit einer stepDistance von 6 gearbeitet, d.h. alle Punkte in einem Radius von 6 cm werden zu einem einzelnen Punkt (ihrem Mittelpunkt) zusammengefaßt. Die 250 Meßwerte konnten damit auf 90 reduziert werden.

Abbildung 3.3: Beispielscan

Abbildung 3.4: Illustration der Punkte-Reduzierung

Der einfache Linienerkennungsalgorithmus

Der Linienerkenner geht sukzessive alle verbliebenen Punkte durch,um Punkte zu Linien zusammenzufassen. Seien $a_0, a_1,\ldots, a_n$ die Punkte. Weiterhin sei bereits bekannt, daß $a_i,\ldots, a_j$ auf einer Linien liegen. Nun betrachtet der Algorithmus den Punkt $a_{j+1}$. Es werden folgende Werte berechnet:

$$:= \left\lvert\left\lvert a_j,a_{j+1} \right\rvert\right\rvert$$ distance

$$:= \sum_{t=i}^{j} \left\lvert\left\lvert a_t, a_{t+1} \right\rvert\right\rvert$$ sum

$$\mbox{{\tt direct\_distance}} := \left\lvert\left\lvert a_i,a_{j+1} \right\rvert\right\rvert$$

$$\mbox{{\tt two\_distance}} := \left\lvert\left\lvert a_{j-1},a_j \right\rvert\right\rvert + \left\lvert\left\lvert a_j,a_{j+1} \right\rvert\right\rvert$$

$$\mbox{{\tt two\_d\_distance}} := \left\lvert\left\lvert a_{j-1},a_{j+1} \right\rvert\right\rvert$$

$$\mbox{{\tt ratio}} := \frac{\mbox{{\tt direct\_distance}}}{\mbox{{\tt sum\_distance}}}$$

$$\mbox{{\tt ratio2}} := \frac{\mbox{{\tt two\_d\_distance}}}{\mbox{{\tt two\_distance}}}$$

Abbildung 3.5: Die Wirkungsweise des einfachen Linienerkenners

Die Linie $a_i,...a_j$ wird nun um den Punkt $a_{j+1}$ erweitert, wenn alle der folgenden Bedingungen erfüllt sind:

1. ratio$~~~~~\, > ~ \displaystyle 1 - \frac{0.3}{\bigl(1+1.5\cdot(j+1)\bigr)}$
2. ratio2$~~~~ > ~ 0.8$
3. distance$~ < ~ 3 \cdot \texttt{stepDistance}$.

Wie man leicht sieht, wird mit ratio und ratio2 die Linienerkennung kontrolliert. Die 3. Ungleichung drückt aus, inwieweit Linien ohne vorliegende Meßpunkte extrapoliert werden. Die in den Ungleichungen auftretenden Konstanten wurden von uns empirisch bestimmt.

Abbildung 3.5 zeigt das Resultat des Linienerkenners auf den Meßpunkten aus Abbildung 3.4 (eingezeichnet in die Originaldaten). Ein Vergleich der beiden Abbildungen zeigt, daß alle Punkte, die nach dem Reduzieren übrig geblieben sind, auch Linien zugeordnet werden konnten.

Houghtransformation

Die Houghtransformation dient zum Erkennen von geometrischen zweidimensionalen Objekten [McL98, URLHou]. Dazu wird eine $(\varrho ,\theta)$-Parametrisierung des Linienraums benutzt, wobei $\theta$ der Winkel des Normals zu der Linie ist und $\varrho$ die Länge des Normals, also der Abstand des Punktes zum Ursprung des Bildes.

Abbildung: Der Kreis für die Berechnung der Houghtransformation

Alle Punkte einer Linie erfüllen durch diese Parametrisierung die Gleichung

$$\varrho = x \cdot \cos(\theta) + y \cdot \sin(\theta).$$ (3.3)

Ein Beispiel soll das Verfahren demonstrieren: Gegeben seien vier Punkte (vgl. Abbildung 3.7): $(50,200)$, $(75,200)$, $(100,200)$ und $(125,100)$. Wie man leicht sieht, liegen drei der vier Punkte auf einer Geraden. Diese drei Punkte überlagern sich im $(\varrho ,\theta$)-Raums konstruktiv und bilden im Histogramm dann ein Maximum.

Diese Transformation wird für alle Punkte des Scans berechnet und das Ergebnis in einem Histogramm aufsummiert. Dabei wird sowohl der Winkel $\theta(j)$ als auch $\varrho (k)$ diskretisiert [ URLHou].

for (i=0; i < nr_pts; i++) {
   for (j=0; j < resolution; j++) {
      // theta in [-PI/2,PI/2)
      
      // Die Winkel theta sind in einem Array hinterlegt
      rho = cos_theta[j] * (double) x[i] + sin_theta[j] * 
            (double) y[i];
      k   = (int) ((resolution) * (rho / (2.0 * max_rho_d) + 
            0.5));
 
      histogram[j][k]++;
   }
}

Danach wird im Histogramm das globalen Maximum bestimmt. Damit errechnet man eine Geradengleichung und markiert alle zu dieser Geraden gehörigen Punkte. Gleichzeitig werden alle Linien, d.h. Geradensegmente als Ausgabe für die Houghtransformation, bestimmt. Viele Parameter bestimmen die Güte der aus den Geraden extrahierten Linien und wurden dahingehend angepaßt, daß möglichst korrekt im nahen Sensorbereich erkannt wird. Anschließend werden die Punkte, die zu einer Gerade gehören, von dem Histogramm abgezogen. Dabei wird nicht nur das Maximum des Histogramms entfernt, sondern auch alle Punkte, die zu der geraden beigetragen haben. Damit senkt sich das Gesamtniveau des Histogramms also ab.

Dieser Prozeß wird iteriert, d.h. die Houghtransformation wird erneut gestartet mit den verbliebenen Punkten. Es wird solange iteriert, bis entweder alle Punkte in Geraden aufgegangen sind (hierbei werden einzelne Punkte als Ein-Punkt-Geraden erkannt), oder nach der 100sten Iteration abgebrochen wird.

Abbildung 3.7: Houghtransformation mit 4 Punkten

Abbildung 3.8 stellt das zweidimensionale Histogramm dar und veranschaulicht die Entfernung von Geraden.

Abbildung 3.8: Histogramme zur Houghtransformation

Bemerkung: Die Houghtransformation liefert Geradengleichungen. Die hier vorgestellte Arbeit benutzt zur Zeit nur die Linien-, d.h. Strecken-Information. Die Houghtransformation jedoch liefert insbesondere Geradengleichungen, welche die Möglichkeit bieten, aufgrund von Hintergrundwissen über die eingescannte Szene verdeckte Linien zu propagieren. Wände lassen sich somit extrapolieren, was für Anwendungen in der Robotik sehr sinnvoll ist.

Zum Abschluß geben wir zwei Beispiele. Abbildung 3.9 zeigt die mittels der Hough-Transformation erkannten Linien zu den in den Abbildungen 3.8 dargestellten Histogrammen. Abbildung 3.10 zeigt den gleichen 2D-Scan wie Abbildung 3.3 und ist hier als direkter Vergleich zu dem einfachen Linienerkenner angegeben.

Abbildung 3.9: Erkannte Linien mit Houghtransformation

Abbildung 3.10: Erkannte Linien mit Houghtransformation - analog zu Abbildung 3.5

Meßwertumrechnung

Die beim Einscannen gelieferten Daten - die Punkte eines Scans - müssen nun noch in das kartesische Koordinatensystem $\mathbbm{R}^3$ eines 3D-Scans umgerechnet werden. Die Scan-Punkte eines Scans sind gegeben durch $\xi,\zeta$ Koordinaten und den aktuellen Neigungswinkel des Scanners, $\phi$.

Die $(x,y,z)$-Koordinaten werden aus den Meßwerten ($\xi,\zeta$) berechnet (vgl. Abbildung 3.11) durch

$$x = \xi$$ (3.4)

$$y = \zeta \cdot \sin(\phi),$$ (3.5)

$$z = \zeta \cdot \cos(\phi).$$ (3.6)

Abbildung 3.11: Umrechnung der Koordinaten

Berechnung der Texturen

Der 3D Scanner ist zusätzlich mit einer Kamera ausgestattet, um Bilder für Texturen aufzunehmen, die dann auf die Objekte abgebildet werden können.

Bei der Texturberechnung wird jedem Punkt eindeutig ein Punkt auf dem Foto, beziehungweise auf dem aus mehreren Fotos zusammengesetzten Bild, zugeordnet. Als Textur-Koordinaten werden im folgenden die zu einem Scan-Punkt gehörigen Koordinaten auf dem Bild bezeichnet.

Um die Textur-Koordinaten eines Meßpunktes zu berechnen, soll jeder Meßpunkt $P$ auf eine virtuelle Ebene $E$ projiziert werden (siehe Abbildung 3.12). Dies geschieht online, also während des Scanvorgangs.

Um dies zu erreichen, werden zuerst die Winkel $\varphi_1$ (Winkel zwischen $(P_z,P_x)$ und der $x$-Achse) und $\varphi_2$ (Winkel zwischen $(P_y,P_z)$ und der $y$-Achse und der $z$-Achse, verschoben um die Kameraposition) berechnet.

$$\varphi_1 = \frac{\pi}{2} - \arctan\left(\frac{P_z}{P_x}\right)$$ (3.7)

$$\varphi_2 = \arctan\left(\frac{P_y - h(\mbox{Scanner})}{P_z}\right)$$ (3.8)

Abbildung: Projektion eines Meßpunktes auf eine virtuelle Ebene

Mit diesen Winkeln wird dann der Punkt auf eine 2 Meter entfernte Ebene projiziert. Die Projektion $V \to P \to P'$ wird in zwei Projektionen zerlegt, nämlich eine, die in der $(y,z)$ Ebene abläuft, und eine, die in der $(x,y)$ Ebene abläuft. Das Ergebnis der beiden Projektionen ergibt sich durch Zusammensetzung der Projektionen.

$$x = x + \tan\left(\varphi_1\right) \cdot \bigl( ( ) - P_z\bigr)$$ (3.9)

$$y = y + \tan\left(\varphi_2\right) \cdot \bigl(\text{\cm dist}(\mbox{Plane}) - P_z\bigr)$$ (3.10)

Anschließend wird das zweidimensionale Abbild des Scans noch so skaliert, daß Punkte, von denen Texturinformationen vorliegen, $x$ Werte zwischen 0 und 506/1024 und $y$ Werte zwischen 0 und 997/2048 besitzen. Dabei ist 506 $\times$ 997 die Auflösung des aus mehereren Fotos bestehenden Bildes und 1024 $\times$ 2048 die Auflösung der Textur innerhalb des OpenGL Programms (vgl. Abschnitt 6.5.2)

Bei dem verwendeten Aufbau exisistiert nicht von allen Punkten eine Texturinformation, da der Öffnungswinkel der Kamera wesentlich kleiner als 180 Grad ist.

Abbildung 3.13: Darstellung der zu berechnenden Winkel

Flächen-Segmentierung

Die Flächensegmentierung beruht auf der Annahme, daß eine eingescannte Fläche (z.B. eine Wand) in mehreren -- in etwa aufeinander folgenden -- Scans durch hinreichend nahe übereinander liegende Linien approximiert wird.

Gegeben sei ein Objekt, welches im Sichtbarkeitsbereich des Scanners liegt. Die erste (unterste) Linie, die zu diesem Objekt gehört, sei zuerst im $k$-ten Scan $S_k$ sichtbar und werde mit $l_{ik}$ bezeichnet. Wenn in dem darauffolgenden Scan $S_{k+1}$ die Prädiktion einer potentiellen Fläche validiert wird, d.h. eine Linie $l_{j,k+1}$ existiert, so daß die Endpunkte beider Linien hinreichend genau übereinstimmen, wird die Anfangslinie aus Scan $k$ zu einer Fläche expandiert.

Dieser Vergleich der Endpunkt ist in Abbildung 3.14 zu sehen. Jedoch beschränkt sich der Test nicht nur auf die reine euklidische Distanz der Endpunkte, sondern schließt auch die Überprüfung des Winkels $\measuredangle(l_{i,k},l_{j,k+1})$ zwischen beiden Linien mit ein, der eine Schranke $\varepsilon _2$ nicht überschreiten darf. Ansonsten besteht insbesondere bei kürzeren Linien die Möglichkeit, daß sie selbst dann gematcht werden, wenn ihre Orientierungen stark voneinander differieren.

Abbildung: Expansion einer Fläche durch eine weitere gematchte Linien

Die eigentliche Segmentierung erfolgt in drei Schritten: Gegeben sei ein Scan $S_j = (l_{ij})_{i=1,\dots,n}$, bestimmt durch die darin erkannten Linien. Jede dieser neuen Linien wird nun wie folgt unterschieden:

1. Stellt $l_{ij}$ eine Expansion einer bereits gefundenen Fläche dar?
   Dazu wird die Datenstruktur surface_queue^3.2 durchlaufen auf der Suche nach einer Fläche, deren obere Linie mit $l_{ij}$ gematcht werden kann (d.h. diese beiden Linien müssen oben beschriebene Kriterien erfüllen). Wenn eine solche Fläche existiert, wird diese um $l_{ij}$ erweitert.
2. Andernfalls wird in der Struktur lines_queue - die alle (zumindest bis zu diesem Zeitunkt noch) singulären Linien verwaltet - nach einer Linie gesucht, welche mit $l_{ij}$ gematcht werden kann und höchstens 3 Scans zuvor aufgenommen worden ist. Auf diese Weise ist das Verfahren hinreichend fehlertolerant bei Scans, in denen die Linien (lokal) nur unzureichend erkannt werden konnten.
   Diese beiden Linien bilden nun eine neue Fläche ($\leadsto$ Verschiebung in surface_queue), die mit hoher Wahrscheinlichkeit innerhalb der nächsten Scans weiter expandiert werden wird.
3. Im dritten Fall wird $l_{ij}$ als singuläre Linie in lines_queue aufgenommen, um bei der Bearbeitung eines späteren Scans möglicherweise in Schritt (2) als Grundlinie einer Fläche erkannt zu werden.

Am Ende des Algorithmus sind nun jene Linien, die hinreichend gut eine Fläche in der eingescannten Szene approximieren, nun auch intern zu einer Fläche zusammengefügt. Die in der Szene erkannten Flächen dienen nicht nur der Visualisierung (z.B. durch Einfärbung mittels einer aus dem Kamerabild extrahierten Textur) und der Objektsegmentierung. Sie stellen auch eine ,,Verbindung`` zwischen verschiedenen Scans dar: Marken, die es ermöglichen, mehrere sukzessive aufgenommenen Scans zu einer großen Aufnahme zu vereinen.