• Startseite
• Recherche
• Veröffentlichen
• Hilfe

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 grouping

Fehlerfortpflanzung und Gruppierung in der projektiven Geometrie

Kurzfassung in Englisch

This thesis describes the approach used for, and the improvements
possible 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 Deutsch

In dieser Arbeit beschreibe ich meinen Ansatz zur Kombination von
Methoden 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.