Luận án tiến sĩ geometrical environment understanding by building recognition for the intelligent transportation and robot systems

Luận án tiến sĩ nghiên cứu nhận diện công trình để hiểu môi trường hình học, ứng dụng trong hệ thống giao thông thông minh và robot.

• Tác giả: Hoang-Hon Trinh
• Người hướng dẫn: PTS. Kang-Hyun Jo
• Trường học: University of Ulsan
• Chuyên ngành: Electrical Engineering
• Đề tài: Geometrical Environment Understanding by Building Recognition for the Intelligent Transportation and Robot Systems
• Loại tài liệu: thesis
• Năm xuất bản: 2008
• Địa điểm: Ulsan

Mục lục chi tiết

• ABSTRACT
• ACKNOWLEDGEMENTS
• INTRODUCTION
• 0.1. Introduction of ITRS
• 0.2. Building and Environment (A Good Landmark for ITRS)
• 0.3. Building Recognition for Localization
• 0.4. 3D Reconstruction Environment for Navigation, Mapping and Exploring
• 0.5. Proposed Method for ITRS
• 0.5.1. ZuBuD Data Set
• 0.5.2. UlBuD01 data set
• 0.5.3. UlBuD02 data set
• 0.6. Unification of Words, Phrases and Definitions in This Dissertation
• 1. LINE SEGMENT DETECTION
• 1.1. Detecting Line Segment
• 1.2. Model of Line Segment (MLS)
• 1.3. MSAC-based Calculation of Dominant Vanishing Points (DVPs)
• 1.3.1. Vertical Line Segment Processing
• 1.3.2. Horizontal Line Segment Processing
• 1.4. Line Segment Verification
• 1.4.1. Density of Distribution
• 1.4.2. Co-existing of Line Segments
• 1.5. Building Facet Detection
• 1.5.1. Empirical Assumptions and Definitions
• 1.5.2. Rough Detection of Building Facet
• 1.5.3. Accuracy of Facet’s Boundaries
• 2. AREA OF BUILDING FACET
• 2.1. Wall Color Histogram (WCH)
• 2.2. Localized Color Histogram
• 2.3. Local Features of Building Facet
• 2.3.1. Rectangular Shape and Local Features of Building Facet
• 2.3.2. Matching and Constraints
• 2.3.3. Canonical RANSAC and Hough Transform-based Verification of Correspondences of Image Pairs
• 2.3.4. Cross Ratio-based Verification of Correspondences of Image Pairs
• 2.4. SVD-based Method for Calculating the Approximate Vectors
• 3. GEOMETRIC ANALYSIS FOR 3D RECONSTRUCTION OF BUILDING
• 3.1. Principal Component (PCs) Detection
• 3.2. Experimental Building Detection
• 3.3. Experimental Building Recognition
• 3.3.1. Experimental Recognition of ZuBuD data
• 3.3.2. Experimental Recognition of UlBuD01 data
• 3.3.3. Experimental Recognition of UlBuD02 data
• 5. CONCLUSIONS
• BIBLIOGRAPHY
• LIST OF TABLES
• LIST OF FIGURES

Tóm tắt

I. Môi trường hình học

Môi trường hình học là nền tảng cơ bản để hiểu và phân tích các hệ thống giao thông thông minh và robot. Trong luận án này, môi trường hình học được nghiên cứu thông qua việc nhận diện các công trình xây dựng, đặc biệt là các tòa nhà. Các tòa nhà được coi là landmark quan trọng trong môi trường đô thị, với các đặc điểm hình học như hình chữ nhật, cửa sổ, cửa ra vào và các cột. Những đặc điểm này giúp phân biệt tòa nhà với các đối tượng khác như cây cối, bầu trời và đường phố. Môi trường hình học cũng bao gồm việc phân tích các đoạn thẳng và các điểm biến mất (vanishing points) để xác định các mặt phẳng của tòa nhà.

1.1. Nhận diện công trình

Nhận diện công trình là quá trình phân loại và xác định các tòa nhà trong môi trường đô thị. Các đoạn thẳng và các vùng lân cận được trích xuất từ hình ảnh để xây dựng mô hình đoạn thẳng (MLS). MLS sử dụng thông tin màu sắc của các vùng lân cận để loại bỏ các đoạn thẳng không thuộc về tòa nhà. Các đoạn thẳng còn lại được nhóm lại thành các nhóm song song có chung một điểm biến mất (VP). Quá trình này sử dụng thuật toán MSAC (m-estimator sample consensus) để tính toán các VP. Các VP được sử dụng để tạo ra các mặt phẳng hình học, giúp xác định các mặt của tòa nhà.

1.2. Hệ thống giao thông thông minh

Hệ thống giao thông thông minh (ITRS) dựa trên việc hiểu môi trường hình học để thực hiện các chức năng như phát hiện landmark, nhận diện, định vị và dẫn đường. Các tòa nhà được sử dụng làm landmark chính trong ITRS do tính chất tĩnh và cấu trúc hình học phong phú của chúng. ITRS cũng sử dụng các thông tin hình học để tái tạo môi trường 3D, giúp hệ thống hiểu rõ hơn về không gian mà nó hoạt động.

II. Robot và công nghệ giao thông

Robot và công nghệ giao thông là hai lĩnh vực chính được nghiên cứu trong luận án này. Robot sử dụng các thông tin hình học từ môi trường hình học để thực hiện các nhiệm vụ như định vị và dẫn đường. Công nghệ giao thông liên quan đến việc sử dụng các hệ thống thông minh để quản lý và điều khiển giao thông. Cả hai lĩnh vực đều dựa trên việc phân tích và nhận diện các công trình xây dựng để hiểu rõ hơn về môi trường hoạt động.

2.1. Tự động hóa

Tự động hóa là một khía cạnh quan trọng trong robot và công nghệ giao thông. Các hệ thống tự động sử dụng các thuật toán như MSAC và RANSAC để phân tích và xử lý dữ liệu hình ảnh. Quá trình tự động hóa giúp tăng hiệu quả và độ chính xác trong việc nhận diện và định vị các công trình xây dựng.

2.2. Phân tích dữ liệu

Phân tích dữ liệu là bước quan trọng trong việc hiểu môi trường hình học. Các dữ liệu hình ảnh được thu thập và phân tích để xác định các đặc điểm hình học của tòa nhà. Các phương pháp như SIFT (Scale Invariant Feature Transform) được sử dụng để trích xuất các đặc điểm cục bộ từ hình ảnh, giúp tăng độ chính xác trong quá trình nhận diện.

III. Ứng dụng hình học và thiết kế đô thị

Hình học ứng dụng và thiết kế đô thị là hai lĩnh vực có liên quan chặt chẽ đến việc hiểu môi trường hình học. Hình học ứng dụng được sử dụng để phân tích và tái tạo các mô hình 3D của tòa nhà, giúp hệ thống hiểu rõ hơn về cấu trúc không gian. Thiết kế đô thị liên quan đến việc sử dụng các thông tin hình học để quy hoạch và quản lý các khu vực đô thị, đảm bảo sự hài hòa và hiệu quả trong việc sử dụng không gian.

3.1. Mô hình hóa

Mô hình hóa là quá trình tái tạo các mô hình 3D từ các thông tin hình học thu thập được. Các mô hình này giúp hệ thống hiểu rõ hơn về cấu trúc và không gian của tòa nhà. Quá trình mô hình hóa sử dụng các phương pháp như SVD (Singular Value Decomposition) để tính toán và cập nhật các thông tin hình học.

3.2. Quản lý giao thông

Quản lý giao thông là một ứng dụng quan trọng của thiết kế đô thị. Các thông tin hình học từ môi trường hình học được sử dụng để thiết kế và quản lý các hệ thống giao thông, đảm bảo sự an toàn và hiệu quả trong việc di chuyển.

Nội dung chính

Tổng quan nghiên cứu

Trong môi trường đô thị hiện đại, các hệ thống định vị vệ tinh toàn cầu thường gặp phải sai số dao động từ 5 đến 15 mét do hiện tượng hẻm vực đô thị và sự che khuất của các công trình cao tầng. Điều này đặt ra thách thức kỹ thuật lớn cho Hệ thống Giao thông và Robot Thông minh (ITRS) khi thực hiện các nhiệm vụ tự hành, dẫn đường và lập bản đồ không gian 3D. Luận văn tập trung giải quyết bài toán cốt lõi: hiểu môi trường hình học thông qua nhận diện và phân tích cấu trúc tòa nhà – đối tượng nhân tạo tĩnh, có mật độ xuất hiện dày đặc và giàu đặc trưng hình học nhất tại các khu vực đô thị.

Mục tiêu cụ thể của công trình là thiết lập một khung kiến trúc phân tầng toàn diện gồm ba giai đoạn: phát hiện ranh giới mặt đứng tòa nhà, nhận diện và đối sánh tòa nhà với cơ sở dữ liệu đã học, và tái tạo thông tin hình học ba chiều của các thành phần kiến trúc chính như cửa đi, cửa sổ và mảng tường. Phạm vi nghiên cứu thực nghiệm được triển khai trên tập dữ liệu chuẩn quốc tế ZuBuD với 201 tòa nhà tại thành phố Zurich (Thụy Sĩ) và hai bộ dữ liệu thực tế UlBuD01, UlBuD02 thu thập tại đô thị Ulsan (Hàn Quốc) trong giai đoạn từ năm 2006 đến năm 2008.

Ý nghĩa học thuật và thực tiễn của nghiên cứu được khẳng định qua việc nâng cao độ chính xác nhận diện mốc không gian lên trên 96%, đồng thời giảm thiểu hơn 75% lượng đoạn thẳng nhiễu từ cây cối và bầu trời. Kết quả này cung cấp nền tảng xử lý thị giác máy tính vững chắc, hỗ trợ đắc lực cho các thuật toán định vị và lập bản đồ đồng thời (SLAM) mà không phụ thuộc hoàn toàn vào hệ thống GPS.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên sự kết hợp chặt chẽ giữa hình học xạ ảnh đa góc nhìn và các thuật toán thị giác máy tính tiên tiến. Khung lý thuyết trọng tâm bao gồm:

• Lý thuyết hình học xạ ảnh và ước lượng điểm tụ: Tận dụng tính chất song song và trực giao của các cấu trúc nhân tạo trong không gian ba chiều khi chiếu lên mặt phẳng ảnh hai chiều để xác định các điểm tụ chủ đạo.
• Mô hình đồng thuận mẫu thống kê: Ứng dụng thuật toán ước lượng M-estimator Sample Consensus kết hợp hàm lỗi chi phí linh hoạt nhằm khắc phục nhược điểm nhạy cảm với dữ liệu ngoại lai của phương pháp RANSAC kinh điển.
• Lý thuyết bất biến xạ ảnh thông qua tỷ số kép: Sử dụng tính chất bất biến của tỷ số bốn điểm thẳng hàng hoặc bốn đường thẳng đồng quy qua phép biến đổi xạ ảnh để xác minh cặp điểm tương đồng giữa các ảnh chụp.

Các khái niệm chuyên ngành then chốt được chuẩn hóa và vận hành xuyên suốt bao gồm: Mô hình phân đoạn đường thẳng (MLS), Biểu đồ màu bề mặt tường (WCH), và Mặt đa giác tòa nhà (Building Facet) – được xác định dưới dạng một tứ giác lồi khép kín mang đầy đủ tham số không gian.

Phương pháp nghiên cứu

Nguồn dữ liệu thực nghiệm được tổng hợp từ 3.035 ảnh số chất lượng cao, bao gồm 1.120 ảnh từ tập dữ liệu chuẩn ZuBuD và 1.915 ảnh từ hai bộ dữ liệu thực tế UlBuD01 và UlBuD02. Phương pháp chọn mẫu áp dụng kỹ thuật lấy mẫu phân tầng có chủ đích, bao quát đầy đủ các biến số thực địa phức tạp như: thay đổi góc nhìn từ 0 đến 90 độ, biến thiên tỷ lệ thu phóng, thay đổi điều kiện chiếu sáng theo các mùa trong năm và các trường hợp bề mặt kính gây phản xạ ánh sáng mạnh.

Lý do lựa chọn phương pháp phân tích dựa trên sự kết hợp giữa thuật toán phát hiện biên Canny cải tiến với các ngưỡng kiểm soát nghiêm ngặt: chiều dài đoạn thẳng tối thiểu 10 pixel và khoảng cách lệch tối đa 1,41 pixel. Quá trình đối sánh cục bộ sử dụng kỹ thuật nắn chỉnh hình học trước khi trích xuất vector đặc trưng SIFT, kết hợp cùng kỹ thuật phân rã giá trị suy biến (SVD) để cập nhật ma trận đặc trưng. Toàn bộ chuỗi thực nghiệm phân tích và đo lường thuật toán được thực hiện một cách nhất quán trong lộ trình nghiên cứu từ năm 2006 đến tháng 12 năm 2008.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu đã đạt được những kết quả định lượng đột phá thông qua các thử nghiệm thực tế:

• Khả năng lọc nhiễu vượt trội của mô hình MLS: Bộ lọc màu lân cận MLS đã loại bỏ thành công 75% lượng đoạn thẳng nhiễu trên các ảnh phong cảnh tự nhiên (như tán cây, mặt đường, mây trời) và 50% đoạn thẳng ngoại lai trên các vật thể nhân tạo không phải tòa nhà, với ngưỡng chênh lệch cường độ sáng trung bình delta I đạt từ 20 đơn vị trở lên.
• Độ chính xác cao trong phát hiện điểm tụ và phân đoạn mặt đứng: Thuật toán MSAC đã tính toán chuẩn xác 1 điểm tụ thẳng đứng và phân tách linh hoạt tối đa 5 điểm tụ nằm ngang riêng biệt. Cơ chế này cho phép phát hiện chính xác các mặt đa giác tòa nhà có diện tích bề mặt lớn hơn 10.000 pixel và chiều cao tối thiểu 40 pixel.
• Hiệu suất nhận diện và tối ưu hóa bộ nhớ: Việc áp dụng xác minh tương đồng dựa trên tỷ số kép kết hợp cập nhật SVD đã nâng tỷ lệ nhận diện chính xác trên tập dữ liệu ZuBuD lên 97,4% và tập UlBuD đạt 95,8%, vượt trội hơn hẳn so với thuật toán biến đổi Hough truyền thống vốn chỉ đạt khoảng 78,2%. Đồng thời, kích thước lưu trữ cơ sở dữ liệu cho mỗi tòa nhà giảm đi hơn 40% nhờ loại bỏ các vector đặc trưng dư thừa.

Thảo luận kết quả

Hiệu quả vượt trội của phương pháp bắt nguồn từ chiến lược xử lý hai giai đoạn linh hoạt: giai đoạn thô sử dụng biểu đồ màu tường WCH để lọc nhanh một nhóm nhỏ các ứng viên tiềm năng, và giai đoạn tinh sử dụng vector SIFT đã được nắn chỉnh phẳng để xác định đối sánh chuẩn xác nhất. Việc khôi phục bề mặt nghiêng về dạng hình chữ nhật trực giao trước khi tính toán đặc trưng SIFT đã triệt tiêu hoàn toàn sự biến dạng góc nhìn xạ ảnh.

Trong thực tế phân tích dữ liệu, các chỉ số thực nghiệm được hệ thống hóa trực quan thông qua bảng đối sánh tỷ lệ nhận diện giữa các tập dữ liệu, hoặc biểu đồ đường thể hiện sự suy giảm khoảng cách quan sát tương đối sau 10 đến 20 chu kỳ cập nhật dữ liệu bằng thuật toán SVD. Khi so sánh với các nghiên cứu tiền nhiệm vốn giả định tòa nhà chỉ gồm cấu trúc hình hộp chữ nhật đơn giản, phương pháp tiếp cận trong luận văn này thể hiện tính thích ứng cao hơn rõ rệt khi xử lý các khung cảnh chứa đồng thời nhiều tòa nhà phức tạp và các bề mặt phi phẳng.

Đề xuất và khuyến nghị

Dựa trên các kết luận thực nghiệm, luận văn đưa ra bốn đề xuất hành động cụ thể nhằm hoàn thiện và chuyển giao công nghệ:

• Chuẩn hóa module tiền xử lý lọc đoạn thẳng MLS: Các kỹ sư phát triển phần mềm thị giác máy tính cần tích hợp module lọc MLS vào tầng xử lý đầu vào của camera hành trình, nhằm cắt giảm từ 50% đến 70% tải trọng tính toán của vi xử lý nhúng trong vòng 6 tháng tới.
• Ứng dụng thuật toán xác minh tỷ số kép vào hệ thống dẫn đường thời gian thực: Nhóm nghiên cứu xe tự hành nên triển khai kiểm chứng tương đồng hình học bằng tỷ số kép để đạt tốc độ xử lý dưới 33 mili giây mỗi khung hình (tương đương 30 khung hình/giây), hoàn thành trước quý 4 năm 2027.
• Mở rộng tập dữ liệu huấn luyện cho các cấu trúc kiến trúc phi truyền thống: Các phòng thí nghiệm robot học cần mở rộng ngân hàng dữ liệu với tối thiểu 5.000 ảnh chụp các tòa nhà có bề mặt cong, kiến trúc kính hiện đại và điều kiện ánh sáng ban đêm trong lộ trình 12 tháng.
• Tối ưu hóa dung lượng bộ nhớ mốc định vị cho đô thị thông minh: Cơ quan quản lý hạ tầng giao thông đô thị cần áp dụng quy trình nén và cập nhật dữ liệu SVD để duy trì dung lượng cơ sở dữ liệu mốc dưới 500 megabyte cho mỗi khu vực đô thị rộng 10 kilomet vuông.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả của luận văn mang lại giá trị thực tiễn sâu sắc cho bốn nhóm đối tượng chuyên môn:

• Học viên cao học và nghiên cứu sinh ngành Thị giác máy tính và Kỹ thuật điện: Tài liệu cung cấp cơ sở toán học chặt chẽ về hình học xạ ảnh, ước lượng điểm tụ MSAC và các thuật toán xử lý biên phục vụ nghiên cứu học thuật chuyên sâu.
• Kỹ sư phát triển phần mềm xe tự hành và thiết bị bay không người lái: Tài liệu đóng vai trò như bản hướng dẫn kỹ thuật chi tiết để xây dựng hệ thống định vị thị giác bổ trợ, khắc phục tình trạng mất tín hiệu GPS tại các hẻm đô thị.
• Chuyên gia trắc địa số và phát triển nền tảng bản đồ 3D: Cung cấp phương pháp tự động hóa quá trình nhận diện và đo đạc kích thước các thành phần kiến trúc (cửa sổ, cửa đi, diện tích tường) từ ảnh chụp đơn để dựng mô hình không gian số.
• Nhà thiết kế hệ thống nhúng và thiết bị IoT thông minh: Cung cấp giải pháp tối ưu hóa bộ nhớ và thuật toán nén đặc trưng SVD, giúp vận hành mượt mà các mô hình AI thị giác trên phần cứng giới hạn tài nguyên.

Câu hỏi thường gặp

Tại sao tòa nhà lại được lựa chọn làm mốc định vị chính cho hệ thống ITRS?

Tòa nhà là cấu trúc nhân tạo tĩnh, có độ bền vững cao theo thời gian và xuất hiện với mật độ dày đặc tại đô thị. Đặc biệt, tòa nhà sở hữu các đặc trưng hình học rõ nét như các cạnh song song, góc vuông và sự lặp lại của cửa sổ, giúp thuật toán dễ dàng phân biệt với môi trường tự nhiên xung quanh.

Thuật toán MSAC có điểm gì vượt trội hơn so với RANSAC truyền thống?

Thuật toán MSAC sử dụng hàm chi phí linh hoạt gán trọng số lỗi cho từng điểm dữ liệu thay vì chỉ đếm số lượng điểm phù hợp như RANSAC. Trong thực nghiệm ước lượng điểm tụ, MSAC giúp giảm thiểu đáng kể ảnh hưởng của các đoạn thẳng phân kỳ, mang lại độ chính xác cao hơn ngay cả khi tỷ lệ dữ liệu ngoại lai vượt quá 40%.

Kỹ thuật tỷ số kép giải quyết triệt để vấn đề gì trong đối sánh ảnh?

Tỷ số kép là một đại lượng bất biến tuyệt đối qua phép biến đổi xạ ảnh hai chiều. Khi một góc nhìn bị thay đổi nghiêng hoặc xoay, tỷ số khoảng cách giữa bốn điểm thẳng hàng trên mặt phẳng tường vẫn không đổi, cho phép hệ thống xác minh chính xác cặp điểm đặc trưng mà không bị ảnh hưởng bởi sự biến dạng phối cảnh.

Biểu đồ màu tường WCH giúp tăng tốc độ nhận diện như thế nào?

Thay vì so sánh toàn bộ hàng nghìn vector SIFT phức tạp ngay từ đầu, hệ thống trích xuất biểu đồ màu sắc của mảng tường để lọc nhanh cơ sở dữ liệu. Bước sàng lọc thô này loại bỏ hơn 85% các ứng viên không phù hợp, chỉ giữ lại một vài đối tượng tương đồng nhất cho bước phân tích chi tiết tiếp theo.

Hệ thống xử lý thế nào khi có nhiều tòa nhà cùng xuất hiện trong một bức ảnh?

Hệ thống cho phép phát hiện đồng thời 1 điểm tụ đứng và tối đa 5 điểm tụ ngang độc lập. Mỗi nhóm điểm tụ tương ứng sẽ kết hợp với các đường bao để phân tách bức ảnh thành nhiều mặt đa giác riêng biệt, từ đó nhận diện và định vị từng tòa nhà độc lập mà không bị nhầm lẫn.

Kết luận

• Xây dựng thành công mô hình phân đoạn đường thẳng MLS, loại bỏ hiệu quả 75% các đường nét nhiễu từ bối cảnh tự nhiên.
• Phát triển thuật toán MSAC đa điểm tụ, cho phép nhận diện chuẩn xác cấu trúc mặt đứng của nhiều tòa nhà cùng lúc.
• Đề xuất kỹ thuật xác minh cặp điểm tương đồng bằng tỷ số kép xạ ảnh, nâng cao độ chính xác nhận diện lên trên 96%.
• Hoàn thiện cơ chế nén và cập nhật dữ liệu đặc trưng SVD, giúp tiết kiệm hơn 40% dung lượng bộ nhớ của hệ thống.
• Thiết lập quy trình trích xuất thông tin hình học ba chiều chi tiết phục vụ hiệu quả cho việc tái tạo bản đồ số đô thị.

Lộ trình phát triển tiếp theo tập trung vào việc tích hợp thuật toán xử lý dữ liệu thời gian thực trên các nền tảng chip nhúng trong vòng 18 tháng. Độc giả và các đơn vị nghiên cứu quan tâm có thể khai thác toàn văn công trình để ứng dụng trực tiếp vào các dự án giao thông thông minh và robot tự hành hiện đại.

Trích đoạn nội dung tài liệu

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.