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

HỒNG XN THƯƠNG

NGHIÊN CỨU MỘT SỐ THUẬT TỐ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

HỒNG XN THƯƠNG

NGHIÊN CỨU MỘT SỐ THUẬT TỐ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 hồn tồn chịu trách nhiệm về tính pháp lý q 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 TỐ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


vii
DANH MỤC HÌNH ẢNH
Hình 1.1: Hệ thống LiDAR ........................................................................ 5
Hình 1.2: Tổng quan và nguyên lý hoạt động của hệ thống LiDAR............ 6
Hình 1.3: Cách phát và thu nhận tín hiệu phản hồi ..................................... 9
Hình 1.4: Tia laser phản xạ khi đi qua mục tiêu ....................................... 10
Hình 1.5: Quy trình tổng quát xử lý dữ liệu LiDar ................................... 12
Hình 1.6: Ví dụ về đám mây điểm LiDAR được hiển thị dưới dạng 3D ... 15
Hình 1.7: Quy trình phân loại đám mây điểm LiDAR .............................. 15
Hình 1.8: Ứng dụng trong khảo sát địa hình và lập bản đồ ....................... 16
Hình 1.9: Ứng dụng trong lâm nghiệp ...................................................... 16
Hình 1.10: Ứng dụng trong lập bản đồ ngập úng ...................................... 16
Hình 1.11: Ứng dụng cho đới duyên hải ................................................... 17
Hình 1.12:Ứng dụng trong lập bản đồ địa hình ven biển .......................... 17
Hình 1.13: Ứng dụng trong quan trắc dự báo trượt lở ............................... 17
Hình 1.14: Ứng dụng trong lập bản đồ tuyến truyền tải ............................ 17
Hình 1.15: Ứng dụng trong lập bản đồ tuyến truyền tải ............................ 18
Hình 1.16: Ứng dụng trong quy hoạch và quản lý mạng điện thoại di động
................................................................................................ 18
Hình 1.17: Ứng dụng trong lập mơ hình và mơ phỏng đơ thị .................... 18
Hình 1.18: Tác vụ của Khai phá dữ liệu ................................................... 19

Hình 1.19 : Một số hình dạng cụm dữ liệu khám phá được bởi kỹ thuật
PCDL dựa trên mật độ ............................................................ 26
Hình 1.20: Mơ hình cấu trúc dữ liệu lưới ................................................. 27
Hình 2.1: Tiến trình phân cụm sử dụng MCC ........................................... 32
Hình 2.2: Mơ tả thuật toán EM trong phân loại đám mây điểm LiDAR .... 35
Hình 2.3: Phân cụm các đối tượng trên bề mặt đo vẽ ............................... 35
Hình 2.4: Tiến trình của thuật tốn EM .................................................... 37
Hình 2.5: Mơ tả thuật tốn K-Means ........................................................ 40


viii
Hình 2.6: Ví dụ phân loại với K-Means .................................................... 41
Hình 2.7: Pseudo code của thuật tốn K-means ........................................ 43
Hình 2.8: Seeded-Kmeans khởi tạo 3 cụm ban đầu .................................. 47
Hình 2.9: Dùng 2-KMeans để chia các cụm cha thành hai cụm con ......... 47
Hình 2.10: Áp dụng tiêu chuẩn BIC ......................................................... 47
Hình 2.11: Kết quả có 4 cụm .................................................................... 47
Hình 2.12: Khu vực thực nghiệm trong nghiên cứu .................................. 50
Hình 2.13: Tỉ lệ các điểm thuộc hai lớp sau phân loại .............................. 51
Hình 2.14: Kết quả phân loại với K=5 ...................................................... 52
Hình 2.15: Kết quả phân loại với K=7 ...................................................... 53
Hình 3.1: Thông tin file .las sau khi xử lý bằng lasinfo của LASTools ..... 57
Hình 3.2: Đám mây điểm khu vực khảo sát .............................................. 58
Hình 3.3: Ảnh vệ tinh của khu vực đo vẽ ................................................. 58
Hình 3.4: Giao diện GUI của LasTool ...................................................... 60
Hình 3.5: Giao diện chương trình ............................................................. 61
Hình 3.6: Cửa sổ Setting thiết lập thơng số cho MCC và K-Means .......... 61
Hình 3.7: Dữ liệu file *.txt chứa toạ độ (x, y, x) của các điểm ................. 62
Hình 3.8: Phân loại với MCC ................................................................... 62
Hình 3.9: Phân loại với K-Means (K = 2) ................................................. 63

Hình 3.10: Tham số được lựa chọn trong giải thuật MCC ........................ 63
Hình 3.11: Các điểm được gán nhãn sau phân loại với MCC ................... 64
Hình 3.12: Kết quả phân loại với K-means ............................................... 64
Hình 3.13: Mơ hình số địa hình khu vực thử nghiệm................................ 66
Hình 3.14: Mơ hình số bề mặt khu vực thử nghiệm .................................. 67
Hình 3.15: Mơ hình địa hình kỹ thuật số khu vực thử nghiệm .................. 67


1
MỞ ĐẦU
1. Đặt vấn đề
Cuộc cách mạng công nghiệp lần thứ 3 đã chấm dứt khi cuộc khủng
hoảng tài chính Châu Á nổ ra vào năm 1997 và làn sóng thứ 4 đã diễn ra từ
đầu thế kỷ 21 với các cuộc cách mạng số, những công nghệ mới như trí tuệ
nhân tạo (AI), hệ thống tự động kết nối cao (Internet of Thing), công nghệ
nano, sinh học, vật liệu mới, năng lượng mới...
Công nghệ viễn thám thu thập dữ liệu dưới dạng ảnh chụp (ảnh hàng
không) hoặc dưới dạng ảnh quét (ảnh vệ tinh) dựa trên việc ghi nhận năng lượng
bức xạ (đối với ảnh hàng không và ảnh vệ tinh) hoặc ghi nhận sóng phản hồi
phát ra từ vật thể khi khảo sát (đối với ảnh radar). Để thu nhận thông tin của các
đối tượng, hiện tượng trên bề mặt trái đất qua ảnh viễn thám, cần sử dụng các kỹ
thuật xử lý, phân tích hình ảnh để có thể chiết xuất được càng nhiều thơng tin
càng tốt. Hiện nay, ảnh viễn thám quang học là loại ảnh dữ liệu dễ tiếp cận, dễ
tìm kiếm, các kỹ thuật phân tích cũng đã đa dạng, dễ thực hiện, giảm thiểu thời
gian xử lý và ngày càng chính xác hơn.
Từ những năm đầu của thập niên 60 của thế kỷ XX, sự ra đời của bộ
khuếch đại ánh sáng bằng phát xạ kích thích – laser đã mở ra rất nhiều ứng
dụng mới, trong đó phải kể đến kỹ thuật khảo sát từ xa sử dụng nguồn kích
thích bằng tia laser gọi là LiDAR. Trong công tác thu nhận dữ liệu không gian
địa lý công nghệ LiDAR là một trong hai phương pháp mang lại hiệu quả rất

cao [3].
LiDAR là công nghệ viễn thám mới, chủ động của ngành Trắc địa –
Bản đồ, kể từ khi được áp dụng rộng rãi vào những năm 90 của thế kỉ trước,
LiDAR đang ngày càng chứng tỏ được ưu thế của mình trong việc thu thập
thông tin về những đối tượng trên bề mặt địa hình. Với khả năng trực tiếp
thu nhận đám mây điểm 3D với độ chính xác cao, LiDAR được áp dụng
rộng rãi cho mục đích thành lập mơ hình số độ cao (DEM), mơ hình số địa


2
hình (DTM) hay mơ hình số bề mặt (DSM) [2]. Công nghệ LiDAR là sự
phát triển và ứng dụng các thiết bị laser, định vị vệ tinh và đo quán tính để
thu thập dữ liệu địa lý trên bề mặt trái đất. So sánh với các phương pháp thu
nhận và xử lý trắc địa ảnh truyền thống, xử lý dữ liệu LiDAR dễ dàng hơn,
thành lập chính xác mơ hình DEM. Để thành lập ra được DEM từ dữ liệu
đám mây điểm LiDAR, phải tiến hành phân loại dữ liệu thành hai lớp phản
xạ đầu tiên (hay điểm không mặt đất – Non - Ground) và phản xạ cuối cùng
(điểm mặt đất - Ground), quá trình này gọi là phân loại dữ liệu LiDAR [4].
Việc phân loại dữ liệu tự động của đám mây điểm được thực hiện bằng phép
giải các bài toán lọc điểm, trên cơ sở kết hợp sử dụng ảnh cường độ, kết quả
đo vẽ các bãi kiểm định chuẩn trên thực địa và ảnh số chụp được (nếu có
trong cơng nghệ có lắp thêm hệ thống máy chụp ảnh kỹ thuật số).
Bề mặt Trái đất có hình dạng gồ ghề, phức tạp, gồm các đại dương, lục
địa và hải đảo. Địa hình của Trái đất tại mỗi lục địa và vị trí là khác nhau. Địa
hình trên bề mặt Trái đất ln thay đổi do có sự tác động của nội lực và ngoại
lực, hai quá trình này ảnh hưởng đến nhau một cách nhất định, trong đó, nội
lực đóng vai trị chủ yếu trong hình thành các yếu tố địa hình lớn, cịn ngoại
lực đóng vai trị trong hình thành các yếu tố địa hình nhỏ. Các đối tượng trên
bề mặt trái đất gồm: Địa vật, thủy hệ, điểm dân cư, mạng lưới giao thông và
đường dây liên lạc, dáng đất, lớp phủ thực vật và đất, ranh giới hành

chính….[4]
LiDAR là cơng nghệ viễn thám có khả năng thu nhận dữ liệu về một
vùng rộng lớn, không bị hạn chế về thời tiết, đo được vào ban đêm, có khả
năng đi xuyên qua nước và mặt đất, dữ liệu thu được từ hệ thống LiDAR là
vơ cùng lớn và có giá trị trong nghiên cứu bề mặt trái đất [4]. Phân cụm bề
mặt Trái đất là quá trình chia bề mặt Trái đất thành các lớp phủ mặt đất. Lớp
phủ mặt đất là lớp phủ quan sát được khi nhìn từ mặt đất hoặc thơng qua một
số phương pháp đo đạc như viễn thám, quang học như thực vật (tự nhiên hoặc


3
nhân tạo), các cơng trình xây dựng trên đất (nhà, cơng trình giao thơng,…),
mặt nước,…. Trên thực tế, mỗi khu vực trên Trái đất đều có loại hình lớp phủ
mặt đất đặc trưng và mỗi đối tượng chịu sự tác động của tự nhiên, con người
là khác nhau, chính sự tác động này làm cho lớp phủ mặt đất luôn biến đối.
Để nghiên cứu và tìm hiểu về khu vực đo vẽ, tìm hiểu được loại lớp phủ và
đặc trưng của nó giúp cho cơng việc thuận lợi hơn. Để thu thập được thông tin
về lớp phủ mặt đất tại khu vực đo vẽ phương pháp sử dụng tư liệu viễn thám
là phương pháp hiện đại, giúp trích xuất thơng tin về lớp phủ nhanh chóng,
hiệu quả và cơng nghệ LiDAR là công nghệ viễn thám được sử dụng để phân
loại lớp phủ mặt đất [4]. Những khu vực có kết cấu phức tạp như đô thị,
thường phân loại lớp phủ mặt đất khá phức tạp do có nhiều đối tượng, nhiều
thuộc tính lựa chọn, gây khó khăn cho các nhà nghiên cứu trong q trình
chọn lựa và trích xuất đối tượng.
Hiện nay, có nhiều thuật tốn để phân cụm dữ liệu LiDAR như: EM
(Expectation Maximization), MCC (Multiscale Curvature Classification), KMeans, K-Medoids, K-Means phân cấp, CURE (Clustering Using
REpresentatives), BIRCH (Balanced Interative Reducing and Clustering
Hierarchies)…, với mỗi thuật tốn đều có ưu hay nhược điểm riêng, việc hiểu
biết sâu sắc và ứng dụng hiệu quả các thuật tốn này có vai trò quan trọng.
Học viên lựa chọn nội dung: “Nghiên cứu một số thuật toán phân cụm dữ liệu

LiDAR” làm đề tài thực hiện khóa luận thạc sĩ của mình với mục đích ứng
dụng các kỹ thuật phân cụm, cụ thể trong phạm vi đề tài: học viên tập trung
nghiên cứu các thuật toán EM, MCC, K-Means và K-Means phân cấp, lựa
chọn 02 trong số 04 thuật toán trên để nghiên cứu kĩ về thuật toán (đánh giá
về thuật toán, kết quả phân cụm dữ liệu LiDAR), từ đó có định hướng vận
dụng giải quyết bài toán thực nghiệm đặt ra.


4
2. Những nội dung nghiên cứu chính
Ngồi phần mở đầu trình bày lý do chọn đề tài và phần kết luận trình bày
các kết quả đạt được của luận văn này, nội dung nghiên cứu chính được trình
bày trong ba chương như sau:
Chương 1: Trình bày khái qt về cơng nghệ LiDAR và các ứng dụng,
bài toán phân cụm dữ liệu LiDAR.
Chương 2: Trình bày phương pháp phân cụm dữ liệu LiDAR với 4 thuật
toán MCC, EM, K-Means và K-Means phân cấp.
Chương 3: Xây dựng chương trình thử nghiệm phân loại dữ liệu LiDAR
bao gồm: Giới thiệu bài toán thử nghiệm, lựa chọn thuật toán phân loại và dữ
liệu thử nghiệm, môi trường và các công cụ sử dụng để xây dựng chương
trình, phát triển chương trình và đánh giá kết quả thu được.


5
CHƯƠNG 1:
TỔNG QUAN VỀ CƠNG NGHỆ LIDAR VÀ BÀI TỐN PHÂN CỤM
1.1 Tổng quan về công nghệ LiDAR
1.1.1 Cấu trúc hệ thống LiDAR
LiDAR là một thuật ngữ để chỉ một công nghệ viễn thám mới, chủ động,
sử dụng các loại tia laser để khảo sát đối tượng từ xa. Dữ liệu thu được của hệ

thống là tập hợp đám mây điểm phản xạ 3 chiều của tia laser từ đối tượng
được khảo sát. Đây là công nghệ mới được áp dụng tại Việt Nam, cho phép
đo đạc độ cao chi tiết địa hình một cách nhanh chóng và chính xác.
Hệ thống LiDAR bao gồm bộ đầu quyết (bộ cảm biến), hệ thống đo quán
tính IMU, hệ thống GPS, hệ thống quản lý bay, hệ thống camera số và hệ
thống các thiết bị lưu trữ dữ liệu.

Hình 1.1: Hệ thống LiDAR

Bộ máy quét Laser (bộ cảm biến): Gồm hai bộ phận được gắn vào bên
dưới máy bay; một bộ phận có vai trò phát xung laser hẹp đến bề mặt trái đất
trong khi máy bay di chuyển với tốc độ nhất định; một máy thu gắn trên máy
bay sẽ thu nhận phản hồi của những xung này khi chúng đập vào bề mặt trái
đất và quay trở lại thiết bị thu trên máy bay. Hầu hết các hệ thống LiDAR đều
sử dụng gương quét để tạo ra một dải xung. Sóng Laser nằm trong dải sóng
cận hồng ngoại để phục vụ cơng tác đo đạc địa hình, bề mặt trái đất, còn với