|
Eingang zum Volltext |
|
Lizenz
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende URN: urn:nbn:de:bsz:25-opus-29323 URL: http://www.freidok.uni-freiburg.de/volltexte/2932/ Utcke, Sven
Error propagation in geometry-based groupingFehlerfortpflanzung und Gruppierung in der projektiven Geometrie
Kurzfassung in EnglischThis thesis describes the approach used for, and the improvementspossible by, the use of error propagation in conjunction with several algorithms for the grouping of structures based on geometric entities. But rather than rigidly favouring the exact solution each and every time I have put particular weight on practicability, demonstrating the relative gain for many approaches and giving shortcuts where the results are not marred by their use; but also demonstrating how common shortcuts used by many authors can lead to disaster if the underlying assumptions are violated. My main focus in writing this thesis has been to demonstrate that many problems are much easier solved using error propagation, or indeed only solvable using error propagation - I believe that the application grouping pedestrian crossings is such an example - but all the time with a firm eye on computational complexity as well as the necessity for error propagation (or, as it sometimes happens, the lack of it). It is to this end that I not only describe the combination of error propagation with projective geometry, which for the unwary keeps a number of stumbling blocks at hand, but also demonstrate 3 very different application domains. My first example is the application of error-propagation principles to the grouping and recognition of zebra crossings and other repeated structure. This application is a nice example of an implementation which I believe would have been impossible without the use of error propagation due to the high variations of a zebra-crossing's size and quality even within a single image; of particular interest here is how only a few confidence-tests can replace a host of manually chosen parameters, resulting in a uniquely stable algorithm. In the next application I outline an algorithm for the grouping of houses (or, indeed, any structure consisting of orthogonal and parallel elements). Over the years we have seen a few algorithms for the reconstruction of buildings from monocular images, however, in contrast to multi-view approaches these nearly always require manual segmentation of image regions. The algorithm outlined in this chapter could be seen as an attempt to remedy this situation. It is, however, included in this thesis for a different reason: buildings show a number of diverse features at different scales, and I will in particular have a closer look at collinear line segments of only a few pixels to several hundreds of pixels in length and distance as well as vanishing points, the image of intersection of parallel lines at infinity, which can be anywhere from literally in the image to literally at infinity. What is more, these features come with differing accuracies, and even one and the same feature can have different accuracies attached to it depending on context. This application is therefore well suited as a showcase for several different ideas and approaches such as a new algorithm for the iterative improvement of vanishing-point position and one for the automatic grouping of vanishing points; a new objective function for the (partial) calibration of a camera from vanishing-points which takes the different uncertainties in the positions of the vanishing points into account and extends the usual Legoland assumption to more general setups; an extension on previous work which takes the vanishing-point information into account when merging line-segments; and finally a comparison of the performance of several different error-measures, both new ones first introduced in this thesis as well as established ones from the literature, for the identification of collinear line segments. In the last example I finally describes part of the grouping algorithm underlying some of my older publications on the recognition of surfaces of revolution. An important feature for both recognition as well as reconstruction of SORs is the object's axis. The axis can be calculated, e.g., based on the intersections of bitangents, which can vary considerably in their accuracy; it is therefore an excellent example to compare the performance of a number of established algorithms on a number of different features and to demonstrate how even a well-known and often-used algorithm like total least squares will fail if the underlying assumptions (iiid-data) are violated; much better alternatives are introduced and an extensive comparison and discussion shows the merit of error propagation for a problem which, in similar form, one can see tackled with unsuitable tools at nearly any computer-vision conference, even today. The comparisons are done on real contour-data derived from real images which previously appeared in publications about the grouping and recognition of SORs.
Kurzfassung in DeutschIn dieser Arbeit beschreibe ich meinen Ansatz zur Kombination vonMethoden der Fehlerfortpflanzung mit mehreren Algorithmen, die das Geometrie-basierte grouping von Strukturen erlauben. Von der bekannten Literatur unterscheidet sich meine Arbeit vor allem durch die Schwerpunktsetzung auf Anwendbarkeit: die tatsächliche praktische Anwendung zeigt deutlich, welche zusätzlichen Möglichkeiten man durch Fehlerfortpflanzung gewinnt; andererseits habe ich, statt starr an der exakten Lösung festzuhalten (die, wo möglich, natürlich gegeben wird) auch untersucht, welche Auswirkungen die Verwendung von Näherungslösungen haben kann - und in welchen, in der Literatur teilweise recht häufig anzutreffenden, Fällen solche Näherungslösungen verheerende Auswirkungen auf die Korrektheit (oder sogar Existenz) des Ergebnisses haben können. Einer der Gründe für die geringe Verbreitung der Fehlerfortpflanzung unter Bildverarbeitern liegt meiner Meinung nach in der vorhandenen Literatur, deren Interesse stets der korrekten Lösung gilt, ohne Blick auf die praktische Anwendbarkeit. Im Gegensatz hierzu ist die vorliegende Arbeit aus der Praxis für die Praxis entstanden: ich zeige anhand von Beispielen, dass sich viele Probleme tatsächlich einfacher lösen lassen, wenn man Grundlagen der Fehlerfortpflanzung berücksichtigt - oder sogar nur dann; ich denke die Anwendung auf Zebrastreifen ist so ein Beispiel. Dabei behalte ich jedoch stets die algebraische und algorithmische Komplexität der verwendeten Verfahren sowie die Notwendigkeit zu ihrer Verwendung (oder, auch das kann passieren, die mangelnde Notwendigkeit) im Auge. Aus diesem Grund beschreibe ich nicht nur die Kombination von Fehlerfortpflanzung und projektiver Geometrie (die für den uneingeweihten einige Schwierigkeiten bereithält) sondern demonstriere die Anwendung dieser Prinzipien anhand von 3 sehr verschiedenen Beispielen. Die erste Anwendung ist die Erkennung von Zebrastreifen (und anderer periodischer Strukturen). Es handelt sich hier um eine Anwendung von der ich glaube, dass sie so ohne Fehlerfortpflanzung nicht möglich gewesen wäre; besonders interessant an dieser Anwendung ist, wie einige wenige Konfidenz-Tests eine Vielzahl manuell zu wählender Parameter ersetzen können, wodurch ein extrem stabiles System entstanden ist. In meiner nächsten Anwendung beschäftige ich mich mit der Segmentierung von Häuserfronten (orthogonalen und parallelen Strukturen) in Einzelbildern. Es wird kein fertiger Algorithmus präsentiert, stattdessen wird dieses Szenario genutzt, um eine Anzahl unterschiedlicher und auf unterschiedlichen Skalen operierender Techniken zu vergleichen. Der Schwerpunkt liegt auf der Bestimmung kollinearer Liniensegmente und von Fluchtpunkten. Das letzte Anwendungskapitel beschreibt schließlich Teile der Segmentierungsroutinen, die meinen ältesten Publikationen über die Erkennung rotationssymmetrischer Objekte zugrundeliegen. Ein wesentliches Merkmal ist dabei das Bild der Rotationsachse. Dieses lässt sich theoretisch als eine Linie durch die Schnittpunkte von Bitangenten berechnen. Da diese jedoch erheblich in ihrer Genauigkeit variieren können, haben wir hier ein exzellentes Beispiel, um verschiedene Algorithmen zu vergleichen; ich zeige, wie selbst ein bekannter und häufig genutzter Algorithmus wie die kleinste Summe der Fehlerquadrate zu unbrauchbaren Ergebnissen führen kann, wenn die zugrundeliegende Annahme unabhängiger, isotroper und gleichverteilter Fehler nicht zutrifft, und stelle bessere Alternativen vor.
Ein kostenloser Dienst Ihrer Universitätsbibliothek Freiburg. |
