GEOMETRICAL ENVIRONMENT UNDERSTANDING BY BUILDING RECOGNITION FOR THE INTELLIGENT TRANSPORTATION AND ROBOT SYSTEMS By Hoang-Hon Trinh SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY AT UNIVERSITY OF ULSAN ULSAN, KOREA DECEMBER 2008 c Copyright by Hoang-Hon Trinh, 2008 ° UNIVERSITY OF ULSAN DEPARTMENT OF GRADUATE SCHOOL OF ELECTRICAL ENGINEERING The undersigned hereby certify that they have read and recommend to the Faculty of Graduate Studies for acceptance a thesis entitled “Geometrical Environment Understanding by Building Recognition for the Intelligent Transportation and Robot Systems ” by Hoang-Hon Trinh in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Dated: December 2008 ii Committee Vice-chair Dr.: Research Supervisor: Kang-Huyn Jo Committee Member Dr.: iii UNIVERSITY OF ULSAN Date: December 2008 Author: Hoang-Hon Trinh Title: Geometrical Environment Understanding by Building Recognition for the Intelligent Transportation and Robot Systems Department: Graduate School of Electrical Engineering Degree: Ph. Convocation: December Year: 2008 Permission is herewith granted to University of Ulsan to circulate and to have copied for non-commercial purposes, at its discretion, the above title upon the request of individuals or institutions. Signature of Author THE AUTHOR RESERVES OTHER PUBLICATION RIGHTS, AND NEITHER THE THESIS NOR EXTENSIVE EXTRACTS FROM IT MAY BE PRINTED OR OTHERWISE REPRODUCED WITHOUT THE AUTHOR’S WRITTEN PERMISSION.
THE AUTHOR ATTESTS THAT PERMISSION HAS BEEN OBTAINED FOR THE USE OF ANY COPYRIGHTED MATERIAL APPEARING IN THIS THESIS (OTHER THAN BRIEF EXCERPTS REQUIRING ONLY PROPER ACKNOWLEDGEMENT IN SCHOLARLY WRITING) AND THAT ALL SUCH USE IS CLEARLY ACKNOWLEDGED. iii Table of Contents Table of Contents v List of Tables viii List of Figures ix Abstract xiv Acknowledgements xvi Introduction 1 0.1 Introduction of ITRS .2 Building and Environment (A Good Landmark for ITRS) .3 Building Recognition for Localization .4 3D Reconstruction Environment for Navigation, Mapping and Exploring 6 0.5 Proposed Method for ITRS .1 ZuBuD Data Set .2 UlBuD01 data set .3 UlBuD02 data set .7 Unification of Words, Phrases and Definitions in This Dissertation .2 Line Segment Detection .1 Detecting Line Segment .2 Model of Line Segment (MLS) .3 MSAC-based Calculation of Dominant Vanishing Points (DVPs) .2 Vertical Line Segment Processing .3 Horizontal Line Segment Processing .4 Line Segment Verification .1 Density of Distribution .2 Co-existing of Line Segments .5 Building Facet Detection .1 Empirical Assumptions and Definitions .2 Rough Detection of Building Facet .3 Accuracy of Facet’s Boundaries .2 Area of Building Facet .1 Wall Color Histogram (WCH) .2 Localized Color Histogram [81] .3 Local Features of Building Facet .2 Rectangular Shape and Local Features of Building Facet .1 Matching and Constraints .2 Canonical RANSAC and Hough Transform-based Verification of Correspondences of Image Pairs .3 Cross Ratio-based Verification of Correspondences of Image Pairs 64 2.5 SVD-based Method for Calculating the Approximate Vectors. 74 3 Geometric Analysis for 3D Reconstruction of Building 77 3.2 Principal Component (PCs) Detection .1 Experimental Building Detection .2 Experimental Building Recognition .1 Experimental Recognition of ZuBuD data .2 Experimental Recognition of UlBuD01 data .3 Experimental Recognition of UlBuD02 data. 93 vi 5 Conclusions 96 Bibliography 98 vii List of Tables 1.1 Results of DVP’s detection .2 The values of threshold N1 and N2 .3 The condition of horizontal boundaries.4 The conditions for rejecting the ambiguous partial face.1 The distances of histograms (di , i = 1, 2, ., 5) between the test and the stored images from left to right, respectively.2 Corresponding parameters for estimating DVP and homography matrix.3 Explanation for Fig.4 Selected γ for updating wall color histogram and local features.1 Estimated size of buildings in Fig.1 Test conditions for detecting building’s facets.2 Summary of building detection.3 Explanation for each sub-image in Fig.4 Results of building recognition.5 Comparing the size of database for each building.
95 viii List of Figures 1 Examples of challenges of building and environment analysis. 3 2 Building detection and feature extraction. 7 3 Scheme for training database and recognition.1 Illustration of line segment detection.2 An example of line segment detection: (a) Original image in ZuBuD data set; (b) 554 detected line segments, the red lines overwrite on the original image; for easy vision, in (c), the black lines are overwritten on the blurred image with linear transformation [min, max] (values of pixels) → [125, 255]; .3 MLS: Example image is taken from ZuBuD data set; (a) Neighbored regions; (b) line segment detection; (c) building and non-building seg- ments are selected by handling.4 Distribution of 4I, σm 200 first sampled segments and selected thresh- olds.5 Using MLS to reduce the noise from natural object regions or images.6 The angle between the segment and the line where lies through the segment’s middle point and vanishing point.7 Retrieval of broken edges: (a) the vertical segments which create an acute angle 200 in maximum with y-axis; (b) the right edge split into four segments replacing by the blue one.8 Vertical Line Segment Processing: (a) inliers of MSAC process. The region in the marked rectangle is extracted and zoomed in as (b, c and d); (b) many lines are not converging to the DVP; (c) the replaced lines which lie through the vanishing point and middle of vertical segments; (d, e) are the results after reducing coincident lines; (d) shows us the extracted region inside the rectangular mark; (e) presents the results of whole image.9 Results of DVP’s detection: The cyan semgents are vertical group; the red, green, blue and yellow segments are horizontal groups from high to low priority.10 The single line: (a) around region of line segment; (b) relation between length of line segment and diameter of semicircles; (b-f) survived seg- ments.11 Co-existences and extended line segments.12 Candidate line: (a) vertical lines and horizontal segments (ZuBud data image); (b,c) the intersections and estimated height at each vertical line; (d,e) candidate lines of horizontal groups, H1 and H2 respectively; magenta lines are the candidate for both of horizontal groups.13 Other examples for roughly detecting of building facets in step by step: (a-h) come from one building; (i) comes from another one; Blue group in (h) is rejected because it is not passed the thresholds N and h0 .14 Facet detection: (a) four roughly detected facets; (b) three facets sur- vive after rejecting the ambiguities; (c) result of facet detection.15 Accuracy of Facet’s Boundaries: the first row are the results of rough detection of facets; the second row is final results of facet detection.1 Convex quadrangle as the boundary of detected facet.2 Illustration for detecting wall region; (g) final wall color histogram.3 Extracted wall region of corresponding facets of one building in ZuBuD data set.4 Detected wall region and its hue color histogram.5 Robustness of wall color histogram: first column is original images with boundaries of detected facets; the middle is extracted wall regions; the last one is corresponding wall color histogram.6 A test image and five stored images are listed from left to right with differences of scale, viewpoints and day times.7 The illustration of comparison between the wall color histogram and the localized color histogram.8 Selected keypoints and features: A circle center represents location of a keypoint and its approximate region is represented by the size of circle.9 Selected keypoints and features: (d) is zoomed in regions of yellow rectangles of (c).10 (a) two detected and corresponding transformed facets; detected key- points (red marks); (b,c) correct matches with the original and trans- formed images, respectively.11 Repeated features of building: the green circles are correct match and five repeated features; their distances are approximate together; the images are in ZuBuD data set.12 d0 threshold selection by statistics.13 Illustration of a drawback of canonical RANSAC for verification: (a) 104 matches of building facets; (b) the best sample given by using homography matrix; (c) the correct sample.14 Examples of object recognition by using Hough transform-based method; in each image, the small one is training image and the big one is test image.15 Illustration for drawback of Hough Transform-based verification: (a) 63 matches given by using the nearest neighbor constraint; (b) 21 matches given by the bin with the largest number matches of 4D space (Hough transform entry); (b) 451 matches given by using Eq.16 The illustration of cross ratio-based method: (a) concurrent lines; (b) artificial object; (c, d) left and right poses.17 Step by step illustration for searching the corresponding local features of image pairs.18 Relation between factor α and maximum area of detected facets, A.19 Automatically reducing the noise by SVD-based update of features.20 The observing distances are reduced following the updated times with different γ.21 Building images, facet detection, wall regions, wall histogram and com- mon models.1 Step-by-step illustration of PC detection process.2 Typical results of detection of principal component.1 Examples of facet detection in general test conditions: two first rows are illustrated results of ZuBuD data ; two last rows are the test images of our data.2 The detection by movement of ITRS: (a) and (b) are undetected and detected building, respectively.3 Examples of non-building images.4 Confused detection of building images.5 Examples of detection of non-planar buildings.6 Several worst results of building detection.7 Several examples of building recognition of ZuBuD data set; in each sub-image, the above building is the test and the below is the correct matches.8 Non-planar and smooth surfaces; reflection of glass faces of building images .9 The correct recognitions of multiple buildings in images with scale, rotation, seasons and illumination changes.10 Example for robust recognition: the above images are two tests of the same building; the bottom images are the first five matches with descending rank from left to right.11 Two cases of incorrect results: the left are the test images and right are their correspondent images with five models of views; the shown facets includes the ambiguous detections.12 From left to right, The results of without, 10 and 20 times of update, respectively.13 Without Transforming into rectangular shape, from left to right, The results of without, 10 and 20 times of update, respectively.
95 xiii Abstract This dissertation describes a method for understanding the geometrical environment of the intelligent transportation and robot systems (ITRS) by building recognition. To understand the environment, the ITRS can perform several functions such as land- mark detection, recognition, localization, navigation, environment reconstruction and so on. Buildings are considered as the best landmark with dense appearance in the city. The outer surface of building comprises of some special properties of man- made objects such as rectangular shape, doors, windows, wall and columns.
These characters support the information for classifying the buildings with other objects and identifying to each other. The dissertation comprises of three major parts as a hierarchical system for understanding of intelligent transportation and robot systems. The first part of this thesis is for detecting landmark. The buildings are classified with other objects like sky, trees, bushes and roads.
Firstly, line segments and two neighborhood regions are extracted. A model of line segment (MLS) is constructed by color information of neighborhood regions. MLS is used to reduce the line segments of non-building patterns. Secondly, the rest of line segments are clustered such parallel lines which have a common vanishing point (VP) by MSAC (m-estimator sample consensus) algorithm.
The maximum numbers of VPs calculated for vertical and horizontal directions are one and five, respectively. The vertical and one of horizontal clusters create a mesh of convex quadrangles (skew parallelograms) as a candidate face of building. The geometrical properties like distributed density of line segments and number of intersections are analyzed and considered as criteria to refine the building face. Finally, the building facets are detected and represented by a boundary xiv xv quadrangle with its area and vertical and horizontal VPs.
The second part is for identifying the building to each other by a test image. The test image is taken when the robot is working. Then it is matched against the stored images in a database. To do so, wall region of facet is extracted.
Then a wall color histogram and a list of SIFT (scale invariant feature transform) features are calculated for each facet. The matching process contains two steps.