Buchvorstellung
Buchcover

Das einzige Mittel, den Irrtum zu vermeiden, ist die Unwissenheit.
Jean-Jacques Rousseau

Bestimmung von Regelgeometrien mit der FormFittingToolbox (FFT)

Zu der Veredlung von Punktwolken gehört zweifelsohne auch das Ableiten von Regelgeometrien, da hierdurch die aufgenommenen Objekte erst in eine mathematisch beschreibbare Darstellung überführt werden. Die Formanalyse ermöglicht es bspw. erst, die Qualität eines Werkstücks objektiv zu bewerten, indem abgeleitete Formmaße mit den zu erzielenden SOLL-Maßen verglichen werden. Neben einer anwenderfreundlichen und intuitiv zu bedienenden Oberfläche muss eine Software, die Regressionsparameter von Formen schätzt, den Anwender auf eventuell konterminierte Daten hinweisen. Routinen zur Bestimmung von geeigneten Startwerten ggf. in Kombination mit resistenten Algorithmen, die auch bei schlechten Startwerten noch gute Konvergenzeigenschaften aufweisen, sollten heute nicht fehlen.


Parameterschätzung mit der FormFittingToolbox

Die FormFittingToolbox ist eine OpenSource-Entwicklung in JAVA zur Parameterbestimmung von verschiedenen Regelgeometrien in der Ebene und im Raum, welche seit kurzem in der Version v2.0 verfügbar ist und hier im Service-Bereich zusammen mit JAG3D bezogen werden kann. Bestimmt werden können Geraden (2D, 3D), Kreise (2D, 3D), Ellipsen (2D, 3D), Quadriken (2D, 3D), Polynome mit unterschiedlichen Polynomgrad, Ebenen, Kugeln, Kreiszylinder, Rotationsparaboloide, Rotationsellipsoide, Tori und Kreiskegel. Das Programm bestimmt die gewählte Regressionsform durch eine Ausgleichungsrechnung im strengen Gauß-Helmert-Modell. Dies bedeutet, dass neben den Unbekannten auch die Beobachtungen sukzessiv in jeder Iteration Zuschläge erhalten. Eine Beschreibung zum gewählten Modell kann u.a. Lenzmann & Lennzmann (2001) oder Lösler & Nitschke (2010) entnommen werden. Weiterhin unterstützt die FormFittingToolbox vollbesetzte (reguläre) Varianz-Kovarianz-Matrizen für die eingelesenen Punkte. Da hierdurch bei einer großen Anzahl von Punkten entsprechender Speicherplatz bereitgestellt werden muss, limitiert es indirekt die Anzahl der Formpunkte, mit der das Programm arbeiten kann. Dieser Grenzwert hängt stets vom verfügbaren bzw. bereitgestellten Heap-Space des Rechners ab und ist nicht durch das Programm selbst limitiert!

Die FormFittingToolbox versucht, Näherungswerte für die gewählte Form selbstständig aus der Punktwolke zu extrahieren. Da die Qualität dieser ersten Näherung von der Anzahl und der Verteilung der Punktwolke abhängt, muss das Gleichungssystem durch die so bestimmten Startwerte nicht konvergieren. Um die Erfolgsrate auch bei schlecht gewählten Näherungswerten zu verbessern, ist eine einfache Form des Levenberg-Marquardt-Algorithmus (Levenberg, 1944; Marquardt, 1963) zusammen mit dem Gauß-Helmert-Modell implementiert (Lösler, 2009). Gegenüber dem klassischen Ausgleichungsalgorithmus besitzt dieser deutlich robustere Eigenschaften bei schlecht gewählten Startwerten. Diese robusten Eigenschaften des Levenberg-Marquardt-Algorithmus werden jedoch durch schlechtere Konvergenzgeschwindigkeiten erkauft, sodass sein Einsatz mit Bedacht gewählt werden sollte. Bei linearen Ausgleichungsproblemen sollte daher zugunsten der Berechnungszeit auf den Einsatz verzichtet und Null für den Dämpfungsparameter gewählt werden.


Verifizierung der implementierten Algorithmen

Das National Institute of Standards and Technology (NIST) stellt für verschiedene geometrische Formen Beispieldatensätze mit zugehörigen Lösungen bereit, mit denen eine Software auf Herz und Nieren untersucht werden kann. Die frei verfügbaren Datensätze vom NIST beinhalten jeweils 30 Datensätze für folgende Formen: 2D-Gerade, 2D-Kreis, Ebene, Kugel, 3D-Kreis, Zylinder und Kegel. All diese Formen wurden mit der FormFittingToolbox ausgeglichen, um die implementierten Algorithmen zu verifizieren. Da Untersuchungen der Vorgängerversion der FormFittingToolbox am Beispiel der Regressionseben an der FH Mainz bereits sehr gute Resultate aufgezeigt hatten (Mordwinzew, 2010), lag das Hauptaugenmerk beim Prozessieren der NIST-Datensätze auf den bestimmten Näherungswerten bzw. den damit verbundenen Konvergenzeigenschaften. Tabelle 1 fasst die erzielten Ergebnisse kurz zusammen. Die zugehörigen HTML-Reporte können am Ende des Artikels heruntergeladen werden.

Tabelle 1: Konvergenz und Divergenz bei NIST-Formen
Form Datensätze Konvergiert Divergiert
2D-Gerade 30 30 0
2D-Kreis 30 30 0
3D-Gerade 30 30 0
Ebene 30 30 0
Kugel 30 30 0
3D-Kreis 30 30 0
Zylinder 30 29 1
Kegel 30 27 3

Lediglich bei 4 von 240 Formen konnte keine Lösung mit der FormFittingToolbox erzielt werden, da die automatisch bestimmten Näherungswerte so ungünstig waren, dass selbst durch den Einsatz des Levenberg-Marquardt-Algorithmus kein Minimum gefunden werden konnte.


Berücksichtigung vollständiger Varianz-Kovarianz-Informationen bei der Formanalyse

Wie eingangs bereits beschrieben, können vollbesetzte Varianz-Kovarianz-Matrizen im stochastischen Modell berücksichtig werden. Ein Datensatz, der aus tachymetrischen Daten bei der Referenzpunktbestimmung am Radioteleskop Wettzell stammt, soll hierbei als Beispiel dienen. Es handelt sich um einen räumlichen Viertelkreis, der aus 10 Punkten besteht. Aus der Netzausgleichung, die mit JAG3D durchgeführt wurde, liegt die Varianz-Kovarianz-Matrix vor.


Eingelesene Punkte und Varianz-Kovarianz-Matrix in der FormFittingToolbox
Eingelesene Punkte und Varianz-Kovarianz-Matrix in der FormFittingToolbox

Sowohl die Punktdatei als auch die Varianz-Kovarianz-Matrix ist zunächst über den Datei-Dialog auszuwählen. Ferner ist als Formtyp der Kreis 3D zu markieren. Da für den räumlichen Kreis i.d.R. sehr gute Näherungswerte bestimmbar sind (vgl. Tabelle 1), kann auf den Einsatz des Levenberg-Marquardt-Algorithmus verzichtet werden und die Parameterbestimmung gestartet werden. Nach erfolgreicher Berechnung springt das Programm automatisch zum Ausgleichungsergebnis.


Formparameter mit zugehöriger Varianz-Kovarianz in der FormFittingToolbox
Formparameter mit zugehöriger Varianz-Kovarianz in der FormFittingToolbox

Neben den Formparametern und der zugehörigen Standardabweichung des 3D-Kreises wird auch die vollbesetzte Varianz-Kovarianz-Matrix der Parameter ausgegeben. Wurde auf dem Einstellungsblatt am Anfang die Option: Nur Formparameter bestimmen nicht aktiviert, so können auf der letzten Dialogseite die ausgeglichenen Punkte nebst zugehörigen stochastischen Parametern abschließend analysiert werden.

Nicht immer liegt aus der Netzausgleichung eine vollbesetzte Matrix vor. So kann aus SpatialAnalyzer lediglich eine Bandmatrix der ausgeglichenen Punkte exportiert werden. Andere Programme ermöglichen überhaupt keinen Export der Kovarianzmatrix, sodass hier lediglich Standardabweichungen der einzelnen Punkte vorliegen. Im einfachsten Fall sind überhaupt keine stochastischen Informationen vorhanden, sodass mit einem gleichgewichteten Modell gerechnet werden muss. Tabelle 2 zeigt die Lösungen der unterschiedlichen Methoden für den o.g. räumlichen Kreis.

Tabelle 2: Gegenüberstellung der Ergebnisse der Kreisausgleichung mit unterschiedlichen stochastischen Modellen
Parameter Vollbesetzt Bandmatrix Diagonalmatrix Einheitsmatrix
Mx 187.619912549 187.619906052 187.619886533 187.619885326
My 272.314024430 272.314019190 272.314000605 272.313998655
Mz 622.464288496 622.464280359 622.464256788 622.464255524
R 1.390912548 1.390903302 1.390876101 1.390874557
Nx -0.026283027 -0.026280400 -0.026270869 -0.026269884
Ny 0.999654510 0.999654579 0.999654826 0.999654852
Nz 0.000250023 0.000253220 0.000264484 0.000265704
D 267.444354170 267.446850237 267.455699510 267.456648551

Am deutlichsten Fallen die Unterschiede beim Abstand D der Kreisebene zum Koordinatenursprung auf. Hier differieren die Werte um einige Millimeter. Ansonsten sind kaum Unterschiede zu verzeichnen, sodass die Verwendung der vollbesetzten Kovarianzmatrix hier eher akademischen Wert hat. Die Punkte sind alle von einem Standpunkt aus einmal beobachtet worden, sodass sie nur schwach korreliert sind. Mit deutlicheren Unterschieden ist somit erst zur rechnen, wenn die Korrelationen zwischen den Punkten größer als dies im vorliegenden Fall ist. Sind die Punkte in allen drei Raumrichtungen in etwa gleichgenau, so bringt es keinen nennenswerten Vorteil, dies über eine diagonale Varianzmatrix anstatt der Einheitsmatrix zu berücksichtigen.


Abschlußbemerkung

Die FormFittingToolbox v2.0 wurde in diesem Beitrag kurz vorgestellt und Möglichkeiten zur Parameterschätzung von Regelgeometrien am Beispiel der Kreisausgleichung aufgezeigt. Durch die Verarbeitung vollständiger Varianz-Kovarianz-Informationen ist die FormFittingToolbox für große Punktewolken eher ungeeignet. Für diese Aufgaben bieten sich die am Markt existierenden Standardtools an. Werden jedoch diskrete Punkte bspw. durch antastendes Messen mittels Koordinatenmessmaschine, Lasertracker oder Tachymeter bestimmt und liegt aus einer Netzausgleichung die zugehörige Kovarianzmatrix vor, so stellt die FormFittingToolbox ein einfach zu bedienendes Tool zur Formschätzung dar – kostenlos, wohlgemerkt.

Eingangsdaten und Ergebnisse aller erwähnten Beispiele können hier runtergeladen werden.

Eingangsdaten und erzielte Ergebnisse


Quellen

Verwendete Literatur, die nicht der Bibliothek entnommen ist:

  • Lenzmann, E., Lennzmann, L. (2001), Zur Bestimmung eindeutiger Transformationsparameter. Zeitschrift für Geodäsie, Geoinformation und Landmanagement (zfv).
  • Levenberg, K. (1944), A Method for the Solution of Certain Problems in Least Squares. Quarterly of Applied Mathematics.
  • Lösler, M., Nitschke, M. (2010), Bestimmung der Parameter einer Regressionsellipse in allgemeiner Raumlage. Allgemeine Vermessungs-Nachrichten (AVN).
  • Lösler, M. (2009), New Mathematical Model for Reference Point Determination of an Azimuth-Elevation Type Radio Telescope. Journal of Surveying Engineering.
  • Marquardt, D.W. (1963), An Algorithm for Least-Squares Estimation of Nonlinear Parameters. Society for Industrial and Applied Mathematics.
  • Mordwinzew, W. (2010), Untersuchungen zur strengen Lösung der bedingten Ausgleichung mit Unbekannten (Gauss-Helmert Modell) am Beispiel der Bestimmung ausgleichender Ebenen. Bachelorarbeit, FH-Mainz (unveröffentlicht).

16.01.2011 von Michael Lösler