159 Pages
English

Hierarchical real-time recognition of compound objects in images [Elektronische Ressource] / Markus Ulrich

-

Gain access to the library to view online
Learn more

Informations

Published by
Published 01 January 2003
Reads 21
Language English
Document size 7 MB

Institut fur¨ Photogrammetrie und Kartographie
der Technischen Universitat¨ Munc¨ hen
Lehrstuhl fur¨ Photogrammetrie und Fernerkundung
Hierarchical Real Time Recognition of
Compound Objects in Images
Dissertation
Markus UlrichInstitut fur¨ Photogrammetrie und Kartographie
der Technischen Universitat¨ Munc¨ hen
Lehrstuhl fur¨ Photogrammetrie und Fernerkundung
Hierarchical Real Time Recognition of
Compound Objects in Images
Markus Ulrich
Vollstandiger¨ Abdruck der von der Fakultat¨ fur¨ Bauingenieur und Vermessungswesen
der Technischen Universitat¨ Munc¨ hen zur Erlangung des akademischen Grades eines
Doktor Ingenieurs (Dr.-Ing.)
genehmigten Dissertation.
Vorsitzender: Univ. Prof. Dr.rer.nat. E. Rank
Pruf¨ er der Dissertation:
1. Univ.-Prof. Dr. Ing. H. Ebner
2. Univ.-Prof. Dr. Ing. habil. Th. Wunderlich
Die Dissertation wurde am 30.4.2003 bei der Technischen Universitat¨ Munc¨ hen
eingereicht und durch die Fakultat¨ fur¨ Bauingenieur und Vermessungswesen am
10.6.2003 angenommen.Abstract
This dissertation proposes a novel approach for the recognition of compound 2D objects in images under
real time conditions. A compound object consists of a number of rigid object parts that show arbitrary relative
movements. The underlying principle of the approach is based on minimizing the overall search effort, and
hence the computation time. This is achieved by restricting the search according to the relative movements of
the object parts. Minimizing the search effort leads to the use of a hierarchical model: only a selected root
object part, which stands at the top of the hierarchy, is searched within the entire search space. In contrast, the
remaining parts are searched recursively with respect to each other within very restricted search spaces. By
using the hierarchical model, prior knowledge about the spatial relations, i.e., relative movements, between
the object parts is exploited already in an early stage of the recognition. Thus, the computation time can be
reduced considerably. Another important advantage of the hierarchical model is that it provides an inherent
determination of correspondence, i.e., because of the restricted search spaces, ambiguous matches are avoided.
Consequently, a complicated and computationally expensive solution of the correspondence problem is not
necessary. The approach shows additional remarkable features: it is general with regard to the type of object, it
shows a very high robustness, and the compound object is localized with high accuracy. Furthermore, several
instances of the object in the image can be found simultaneously.
One substantial concern of this dissertation is to achieve a high degree of automation. Therefore, a method
that automatically trains and creates the hierarchical model is proposed. For this, several example images that
show the relative movements of the object parts are analyzed. The analysis automatically determines the rigid
object parts as well as the spatial relations between the parts. This is very comfortable for the user because a
complicated manual description of the compound object is avoided. The obtained hierarchical model is used
to recognize the compound object in real time.
The proposed strategy for recognizing compound objects requires an appropriate approach for recognizing
rigid objects. Therefore, the performance of the generalized Hough transform, which is a voting scheme to
recognize rigid objects, is further improved by applying several novel modifications. The performance of the
new approach is evaluated thoroughly by comparing it to several other rigid object recognition methods. The
evaluation shows that the proposed modified generalized Hough transform fulfills even stringent industrial
demands.
As a by product, a novel method for rectifying images in real time is developed. The rectification is based on
the result of a preceding camera calibration. Thus, a very fast elimination of projective distortions and radial
lens distortions from images becomes possible. This is exploited to extend the object recognition approach in
order to be able to recognize objects in real time even in projectively distorted images.
IIIZusammenfassung
In der vorliegenden Arbeit wird ein neues Verfahren vorgestellt, mit dem zusammengesetzte 2D Objekte in
Bildern unter Echtzeit Anforderungen erkannt werden konnen.¨ Ein zusammengesetztes Objekt besteht aus
mehreren starren Einzelteilen, die sich relativ zueinander in beliebiger Art bewegen konnen.¨ Das dem Ver-
fahren zugrunde liegende Prinzip basiert auf der bestmoglichen¨ Verringerung des Suchaufwandes und dient
somit dem Ziel, die Berechnungszeit wahrend¨ der Erkennungsphase zu minimieren. Die Umsetzung dieses
Zieles wird durch die Einschrankung¨ der Suche entsprechend der relativen Bewegungen der Objektteile er
reicht. Dies fuhrt¨ zu der Verwendung eines hierarchischen Modells: Lediglich das Objektteil, das an der
Spitze der Hierarchie steht, wird innerhalb des gesamten Suchraumes gesucht. Die verbleibenden Objektteile
werden hingegen innerhalb eingeschrankter¨ Suchraum¨ e relativ zueinander unter Verwendung eines rekur-
siven Verfahrens gesucht. Durch den Einsatz des hierarchischen Modells kann Vorwissen uber¨ die raum¨ lichen
Beziehungen, d.h. die relativen Bewegungen, zwischen den Objektteilen bereits in einer sehr fruhen¨ Phase
der Erkennung genutzt werden. Dadurch wird die Rechenzeit entscheidend reduziert. Ein weiterer großer
Vorteil des hierarchischen Modells ist die inharente¨ Bestimmung der Zuordnung: Durch die eingeschrank ¨
ten Suchraum¨ e werden Probleme, die durch auftretende Mehrdeutigkeiten hervorgerufen werden wurden,¨
vermieden. Eine komplizierte und rechenintensive Losung¨ des Zuordnungs Problems wahrend¨ der Erken
nungsphase erubrigt¨ sich somit. Das vorgestellte Verfahren besitzt weitere bemerkenswerte Eigenschaften: Es
ist nicht auf eine bestimmte Objektart beschrankt,¨ sondern ist nahezu auf beliebige Objekte anwendbar. Das
Verfahren zeichnet sich außerdem durch eine hohe Robustheit aus und ermoglicht¨ es, das zusammengesetzte
Objekt mit hoher Genauigkeit im Bild zu lokalisieren. Daruber¨ hinaus konnen¨ auch mehrere Instanzen eines
Objektes im Bild simultan gefunden werden.
Ein wesentliches Anliegen dieser Arbeit ist es, einen hohen Automatisierungsgrad zu erzielen. Aus diesem
Grund wird eine Methode entwickelt, die es erlaubt, das hierarchische Modell automatisch zu trainieren und
aufzubauen. Hierfur¨ werden einige Beispielbilder, in denen die relativen Bewegungen der Objektteile zu sehen
sind, analysiert. Durch die Analyse konnen¨ sowohl die starren Objektteile als auch die Relationen zwischen
den Teilen automatisch ermittelt werden. Dieses Vorgehen ist außerst¨ komfortabel, da sich eine komplizierte
manuelle Beschreibung des zusammengesetzten Objektes durch den Benutzer erubrigt.¨ Das somit abgeleitete
hierarchische Modell kann schließlich fur¨ die Erkennung in Echtzeit genutzt werden.
Die in dieser Arbeit vorgeschlagene Strategie zur Erkennung zusammengesetzter Objekte setzt die Nutzung
eines Verfahrens zur Erkennung starrer Objekte voraus. Deshalb werden einige neue Modifikationen der gene
ralisierten Hough Transformation, einem Voting Mechanismus zur Erkennung starrer Objekte, vorgestellt, die
die Leistungsfahigk¨ eit der generalisierten Hough Transformation verbessern. Die erzielte Leistungsfahigk¨ eit
wird durch einen Vergleich mit weiteren Erkennungsverfahren fur¨ starre Objekte eingehend evaluiert. Es zeigt
sich, dass die modifizierte generalisierte Hough Transformation strengen industriellen Anforderungen genugt.¨
Gleichsam als ein Nebenprodukt der vorliegenden Arbeit wird eine neue Methode zur Rektifizierung von
Bildern in Echtzeit vorgestellt. Die Rektifizierung basiert auf dem Ergebnis einer zuvor durchgefuhrten¨
Kamerakalibrierung. Dadurch ist es moglich,¨ sowohl projektive Verzerrungen als auch radiale Verzeich
nungen des Kameraobjektives in Bildern sehr effizient zu eliminieren. Die Rektifizierung kann dann genutzt
werden, um das Objekterkennungsverfahren dahingehend zu erweitern, Objekte auch in projektiv verzerrten
Bildern in Echtzeit zu erkennen.
IIIIVContents
1 Introduction 1
2Scope 3
2.1 ExampleApplicationsandMotivation .... ..... ...... ..... ...... .... 3
2.2 Requirements ...... ..... ...... .... 9
2.3 Concept ... ..... ...... ..... ...... .... 12
2.4 Background . ...... ..... ...... .... 14
2.5 Overview . . ..... ...... ..... ...... .... 15
3 Camera Calibration and Rectification 17
3.1 ShortReviewofCameraCalibrationTechniques.... ...... ..... ...... .... 17
3.2 CameraModelandParameters .. ...... ..... .... 19
3.3 CameraCalibration ... ..... ...... ..... ...... .... 21
3.4 Rectification. ...... ...... ..... .... 22
3.4.1 ComputationoftheRectificationMap ...... ..... ...... .... 22
3.4.2 Rectification Process . . . ...... ..... ...... ..... ...... .... 25
3.5 Example ... ...... ..... .... 25
4 Recognition of Rigid Objects 29
4.1 PreviousWork...... ..... ...... ..... ...... ..... ...... .... 29
4.1.1 Classification of Object Recognition Approaches ..... .... 29
4.1.1.1 ApproachesUsingIntensityInformation .... ..... ...... .... 31
4.1.1.2 ApproachesUsingLowLevelFeatures ..... .... 33
4.1.1.3 ApproachesUsingHighLevelFeatures ..... ...... .... 40
4.1.2 Methods for Pose Refinement .... ..... ...... .... 41
4.1.3 General Methods for Speed Up . . . ..... ...... .... 42
4.1.4 Conclusions... ..... ...... ..... ...... .... 43
4.2 Modified Generalized Hough Transform (MGHT) . . . ...... ..... ...... .... 44
4.2.1 G Hough Tr .... ..... .... 44
4.2.1.1 Principle .... ...... ...... ..... ...... .... 44
4.2.1.2 Advantages . . ..... .... 47
4.2.1.3 Drawbacks ... ...... ...... ..... ...... .... 48
4.2.2 Computation of the R-tables ..... ..... .... 50
4.2.3 Increasing the Efficiency . ...... ...... ..... ...... .... 51
4.2.3.1 Multi Resolution Model . ...... .... 51
4.2.3.2 Domain Restriction .... ...... ..... ...... .... 54
4.2.3.3 Tiling the Model ...... ..... .... 57
4.2.4 PoseRefinement ..... ...... ..... ...... .... 58
4.2.5 QuantizationEffects ... ...... ..... .... 59
V4.2.5.1 Rotation .... ...... ..... ...... ..... ...... .... 59
4.2.5.2 Translation ... .... 61
4.2.5.3 GradientDirection ..... ..... ...... ..... ...... .... 61
4.2.5.4 TileStructure . ...... .... 66
4.2.6 ImplementationDetails.. ..... ...... ..... ...... .... 67
4.2.7 Conclusions... ..... ...... .... 69
4.3 Shape Based Matching (SBM) . . ..... ...... ..... ...... .... 70
4.3.1 Similarity Measure .... ...... ...... ..... ...... .... 70
4.3.2 ImplementationDetails.. ..... .... 71
4.3.3 Least-SquaresPoseRefinement ... ...... ..... ...... .... 72
4.4 PerformanceEvaluationoftheMGHTandtheSBM. . .... 73
4.4.1 Additionally Evaluated Object Recognition Methods . . . ..... ...... .... 73
4.4.1.1 SumofAbsoluteDifferences .... ...... .... 73
4.4.1.2 NormalizedCrossCorrelation .... ...... ..... ...... .... 74
4.4.1.3 HausdorffDistance .... ..... .... 74
4.4.1.4 Geometric Model Finder . ...... ..... ...... .... 74
4.4.1.5 PatMaxandPatQuick ... ..... .... 75
4.4.2 Robustness ... ..... ...... ...... ..... ...... .... 75
4.4.3 Accuracy .... ..... .... 82
4.4.4 ComputationTime .... ...... ...... ..... ...... .... 85
4.4.5 Conclusions... ..... ..... .... 87
5 Recognition of Compound Objects 89
5.1 PreviousWork...... ..... ...... ..... ...... ..... ...... .... 89
5.2 Strategy ... .... 91
5.3 TrainingtheHierarchicalModel . ...... ..... ...... ..... ...... .... 97
5.3.1 Initial Decomposition . . .... 97
5.3.2 Rigid Models for the Components . . ..... ...... ..... ...... .... 99
5.3.3 Pose Determination of the Components .... .... 101
5.3.3.1 RatingofMatches ..... ..... ...... ..... ...... .... 103
5.3.3.2 IdentificationofPhysicalInstances . .... 105
5.3.3.3 Building the Bipartite Graph .... ...... ..... ...... .... 106
5.3.3.4 Bipartite Graph Matching using Linear Programming . . .... 107
5.3.4 ExtractionofObjectParts ...... ..... ...... ..... ...... .... 110
5.3.5 AnalysisofRelationsbetweenObjectParts .. .... 114
5.4 CreatingtheHierarchicalModel . ...... ..... ...... ..... ...... .... 115
5.4.1 RigidModelsfortheObjectParts .. .... 115
5.4.2 OptimumSearchTrees .. ...... ..... ...... ..... ...... .... 116
5.4.3 RootPartRanking .... .... 119
5.5 Object Recognition . . . ..... ...... ..... ...... ..... ...... .... 120
5.5.1 Principle of Hierarchical Object Recognition . .... 120
5.5.2 PracticalExtensions ... ...... ..... ...... ..... ...... .... 122
5.5.2.1 Missed Object Parts .... .... 122
5.5.2.2 Multiple Matches ..... ..... ...... ..... ...... .... 123
5.5.2.3 EliminationofOverlappingMatches .... 124
5.5.2.4 Missed Root Part ..... ..... ...... ..... ...... .... 125
5.6 Examples . . ...... ..... ...... .... 127
6 Conclusions 133
VI