Nghiên cứu một số thuật toán phân cụm dữ liệu Lidar

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG XUÂN THƯƠNG

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN

PHÂN CỤM DỮ LIỆU LIDAR

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN – 2021

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG XUÂN THƯƠNG

NGHIÊN CỨU MỘT SỐ THUẬT TOÁN

PHÂN CỤM DỮ LIỆU LIDAR

Chuyên ngành: Khoa học máy tính

Mã số: 8 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Giáo viên hướng dẫn: PGS.TS. Đặng Văn Đức

THÁI NGUYÊN - 2021

i

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá nhân tôi,

kết quả của luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên

cứu dưới sự hướng dẫn của giáo viên hướng dẫn PGS.TS. Đặng Văn Đức.

Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu

khoa học của luận văn này.

Cẩm Phả, ngày … tháng … năm 2021

Học viên

Hoàng Xuân Thương

ii

LỜI CẢM ƠN

Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến PGS .TS Đặng Văn Đức

– Viện Công nghệ thông tin Hà Nội người đã tận tình hướng dẫn, chỉ bảo,

giúp đỡ em trong suốt quá trình làm luận văn.

Em cũng xin gửi lời cảm ơn đến cô TS Nguyễn Thị Hữu Phương – Đại

học mỏ địa chất Hà Nội, các thầy cô giáo trường Đại học Công nghệ thông

tin và truyền thông - Đại học Thái Nguyên đã truyền đạt những kiến thức và

giúp đỡ em trong suốt quá trình học của mình.

Và học viên cũng xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và

bạn bè những người đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để học

viên có được kết quả như ngày hôm nay.

iii

MỤC LỤC

LỜI CAM ĐOAN ..............................................................................................i

LỜI CẢM ƠN ...................................................................................................ii

MỤC LỤC........................................................................................................iii

DANH MỤC BẢNG BIỂU .............................................................................vi

DANH MỤC HÌNH ẢNH ..............................................................................vii

MỞ ĐẦU .......................................................................................................... 1

1. Đặt vấn đề...................................................................................................... 1

2. Những nội dung nghiên cứu chính................................................................ 4

CHƯƠNG 1: TỔNG QUAN VỀ CÔNG NGHỆ LIDAR VÀ BÀI TOÁN

PHÂN CỤM..................................................................................................... 5

1.1 Tổng quan về công nghệ LiDAR................................................................ 5

1.1.1 Cấu trúc hệ thống LiDAR......................................................................... 5

1.1.2 Đặc điểm cơ bản của công nghệ LiDAR.................................................. 7

1.2. Thu nhận dữ liệu LiDAR ........................................................................... 9

1.3. Xử lý dữ liệu LiDAR ............................................................................... 12

1.3.1. Quy trình xử lý dữ liệu LiDAR.............................................................. 12

1.3.2. Thuộc tính dữ liệu LiDAR ..................................................................... 12

1.3.3. Phương pháp xử lý dữ liệu LiDAR........................................................ 14

1.4. Khả năng ứng dụng của LiDAR............................................................... 16

1.5. Bài toán phân cụm dữ liệu LiDAR .......................................................... 18

1.5.1 Khái niệm phân cụm dữ liệu ................................................................. 18

1.5.2 Các kiểu dữ liệu và độ đo tương tự........................................................ 19

1.5.3 Các kỹ thuật tiếp cận trong phân cụm dữ liệu ....................................... 24

1.5.4 Các ứng dụng phân cụm dữ liệu ............................................................ 27

1.5.5 Phân cụm dữ liệu LiDAR ....................................................................... 28

1.6. Kết chương............................................................................................... 29

iv

CHƯƠNG 2: MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU LIDAR

......................................................................................................................... 30

2.1 Thuật toán MCC........................................................................................ 30

2.2 Thuật toán EM........................................................................................... 34

2.3 Thuật toán K-Means.................................................................................. 39

2.4 Thuật toán H - Kmeans............................................................................. 43

2.5 Đánh giá các thuật toán và lựa chọn thuật toán để thực nghiệm .............. 49

2.6 Đánh giá kết quả phân cụm dữ liệu LiDAR của MCC và K-Means........ 50

2.6.1 Thuật toán MCC..................................................................................... 50

2.6.2 Thuật toán K-Means............................................................................... 52

2.7. Kết chương............................................................................................... 55

CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH PHÂN CỤM DỮ LIỆU

LIDAR............................................................................................................ 56

3.1 Giới thiệu bài toán thử nghiệm ................................................................. 56

3.2 Lựa chọn thuật toán phân cụm và dữ liệu thử nghiệm.............................. 56

3.3 Môi trường và các công cụ sử dụng để xây dựng chương trình ............... 58

3.3.1 Ngôn ngữ C# .......................................................................................... 58

3.3.2 LASTool.................................................................................................. 59

3.4 Phát triển chương trình.............................................................................. 60

3.4.1 Các bước thực hiện ................................................................................ 60

3.4.2 Giao diện và các chức năng của chương trình...................................... 61

3.5 Đánh giá kết quả thu được ........................................................................ 63

3.5.1 Phân loại với MCC ................................................................................ 63

3.5.2 Phân loại đám mây điểm với K-means .................................................. 64

3.5.3 Đánh giá................................................................................................. 65

KẾT LUẬN.................................................................................................... 68

TÀI LIỆU THAM KHẢO ............................................................................ 69

v

DANH MỤC CHỮ VIẾT TẮT

LiDAR: Light Detection And Ranging

Laser: Light amplification by stimulated emission of radiation

GNSS: Global Navigation Sattelite System

INS: Inertial Navigation System

IMU: Inertial measurement unit

DEM: Digital Elevation Model

DSM: Digital Surface Model

DTM: Digital terrain model

MCC: Multiscale Curvature Classification

EM: Expectation Maximization

CURE: Clustering Using Representatives

BIRCH: Balanced Interative Reducing and Clustering Hierarchies

ALS: Aerial Scanning Laser

PCDL Phân cụm dữ liệu

H-Kmeans Hierarchical – Kmeans (Kmeans phân cấp)

vi

DANH MỤC BẢNG BIỂU

Bảng 1.1: Thuộc tính dữ liệu LiDAR ............................................................. 14

Bảng 3.1 Thông số của file las...................................................................... 57

Bảng 3.2: Thống kê sự thay đổi tỉ lệ % phân loại ứng với mỗi miền tỉ lệ ...... 64

Bảng 3.3: Số lượng điểm của mỗi cụm........................................................... 65

Bảng 3.4: So sánh với kết quả phân cụm với trang Opentopo........................ 65

Bảng 3.5: So sánh với kết quả phân loại của trang Opentopo với K-Means.. 65