Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00050
NGHIÊN CỨU KẾT HỢP THUẬT TOÁN MCC VÀ K-MEANS TRONG PHÂN LOẠI
ĐÁM MÂY ĐIỂM LIDAR
Nguyễn Thị Hữu Phương1, Đặng Văn Đức2, Nguyễn Trường Xuân1, Trần Mạnh Trường2
1
Khoa Công nghệ thông tin, Trường Đại học Mỏ - Địa chất
2
Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
nguyenphuong85.nb@gmail.com, dvduc@ioit.ac.vn, nguyentruongxuan@humg.edu.vn, tmtruong@ioit.ac.vn
TÓM TẮT: Năm 2007, nhóm tác giả Jeffrey S.Evans và Andrew T.Hudak đã đề xuất thuật toán MCC (Multiscale Curvature
Classification) để phân loại tự động đám mây điểm thành hai lớp mặt đất và không mặt đất. Trong quá trình phân loại, nhóm tác
giả chỉ ghi nhận những điểm thuộc lớp mặt đất để tiến hành tạo DEM cho khu vực khảo sát, nhóm điểm không mặt đất bị loại bỏ,
trong khi đây là nhóm điểm có chứa nhiều thông tin có ích về bề mặt không gian của khu vực khảo sát. Với mong muốn có thể thu
thập và ghi nhận những thông tin có ích trong nhóm điểm trên, bài báo tập trung vào nghiên cứu cách kết hợp thuật toán MCC và
K-means nhằm tối ưu hơn trong bài toán phân loại đám mây điểm LiDAR để từ đó có thể sử dụng điểm sau phân loại vào bài toán
khảo sát bề mặt của khu vực đo.
Từ khóa: MCC, K-Means, LiDAR, đám mây điểm.
ĐẶT VẤN ĐỀ
Công nghệ LiDAR là một công nghệ tiên tiến hàng đầu trong hệ thống các công nghệ thu thập dữ liệu không
gian trên thế giới. Với khả năng trực tiếp thu nhận đám mây điểm 3D với hộ chính xác cao, LiDAR được áp dụng rộng
rãi trong việc thành lập mô hình số độ cao (Digital Elevation Model - DEM) của bề mặt địa hình, dựa vào đó có thể
theo dõi được dòng chảy của nước hay giám sát di chuyển khối, thành lập bản đồ và viễn thám. 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. Hơn thế nữa, xung laser có thể xuyên qua các địa hình, địa vật như lá, mặt đất dưới tán
cây. LiDAR là kỹ thuật viễn thám quang học chủ động, thu nhận thông tin về đối tượng bằng cách truyền chùm tia
laser đến đối tượng cần khảo theo các tuyến khảo sát cụ thể. Sự phản xạ của chùm tia laser từ đối tượng được phát hiện
và phân tích bởi bộ thu nhận trong bộ cảm biến LiDAR. Những bộ thu nhận này sẽ ghi lại chính xác thời gian từ khi
xung laser được phát ra đến khi trở về để tính khoảng cách giữa cảm biến và mục tiêu. Kết hợp với thông tin về vị trí từ
thiết bị GPS, những phép đo khoảng cách này sẽ được chuyển thành các phép đo ba chiều thực tế của mục tiêu phản xạ
trong không gian đối tượng (ESRI, 2018). Công nghệ LiDAR có thể tạo ra được đám mây điểm lớn chứa nhiều thông
tin có giá trị về khu vực đo vẽ, khảo sát.
Đám mây điểm là tập hợp các điểm đại diện cho hình dạng và đặc trưng 3D. Mỗi điểm có bộ toạ độ (X, Y, Z) và
trong một số trường hợp có các đặc trưng bổ sung thêm. Đám mây điểm có nguồn gốc từ dữ liệu thô được quét từ các
đối tượng vật lý trên bề mặt Trái đất như toà nhà, cây cối, nhà máy, đường dây điện, …. Một đám mây điểm thường rất
lớn từ hàng chục nghìn đến hàng chục triệu điểm. Do đó, để có thể sử dụng đám mây điểm vào các mục đích như thành
lập DEM/DTM phải tiến hành phân loại đám mây điểm thành các lớp chuyên biệt như lớp mặt đất, không mặt đất, lớp
nhà cao tầng, …. (Knowlegde Center, 2015)
Với bài toán phân phân loại đám mây điểm LiDAR, đã có nhiều nhà khoa học trên thế giới nghiên cứu và đã có
những thành công nhất định. Như trong nghiên cứu của nhóm tác giả (Borja Rodriguez - Cuenca, nnk, 2015) đã sử
dụng thuật toán phát hiện điểm để phát hiện và phân loại các đối tượng đô thị và cây cối từ dữ liệu 3D MLS (Mobile
Laser Scanning) và TLS. Phương pháp bao gồm cả việc phân đoạn tự động để loại bỏ đi những phần không liên quan
đến quá trình phân đoạn dọc đối tượng. Những đối tượng này được phân đoạn bằng thuật toán RX và sau đó được phân
cụm để chia lớp đối tượng thành các lớp như cây cối, hồ nhân tạo,…. Hay trong nghiên cứu (A.Brzank, C.Heipke,
2005), đã đưa ra phương pháp mới để phân loại dữ liệu LiDAR thành các điểm mặt nước và mặt đất. Những điểm đo sẽ
được phân loại theo đường quét và trong nghiên cứu này các tác giả cũng áp dụng logic mờ trong việc xác định những
giá trị thành viên cho mỗi điểm thuộc về lớp mặt nước. Sau đó, phép phân loại sẽ phát hiện và làm chính xác bằng cách
so sánh độ cao khác nhau giữa những điểm gần mặt nước và không phải mặt nước. Trong khi đó, các nghiên cứu
(Suresh K. Lodha và nnk., 2003), (Yu chuan chang và nnk., 2008, (Zhuqiang Li và nnk., 2016) cũng đã đưa ra những
phương pháp và thuật toán để phân loại đám mây điểm LiDAR nhằm trích xuất ra thông tin phục vụ cho quá trình
nghiên cứu.
Năm 2007, hai tác giả J. Evans và T. Hudak đã đề xuất thuật toán phân loại đám mây điểm LiDAR dựa trên
miền cong đa tỉ lệ MCC (Multiscale Curvature Classification), sau phân loại đám mây điểm sẽ được phân thành hai lớp
điểm mặt đất (ground) và không mặt đất (non-ground). Nhóm tác giả sử dụng nhóm điểm mặt đất để thành lập DEM
của khu vực khảo sát, trong khi đó, nhóm điểm không mặt đất bị loại bỏ, nhưng đây lại là nhóm điểm chứa nhiều thông
tin có ích về khu vực khảo sát. Với mong muốn thu nhận và phân loại nhóm điểm không mặt đất bị loại bỏ trong thuật
toán MCC, nhóm tác giả đã áp dụng thuật toán K-means cho nhóm điểm này. Thuật toán K-means là thuật toán phân
- 380 NGHIÊN CỨU KẾT HỢP THUẬT TOÁN MCC VÀ K-MEANS TRONG PHÂN LOẠI ĐÁM MÂY ĐIỂM LIDAR
cụm phổ biến, trong nghiên cứu của (Kun Zhang và nnk., 2015) nhóm tác đã sử dụng tham số mật độ của đám mây
điểm như là điều kiện để lựa chọn số lượng cụm để tiến hành phân loại và là điều kiện để hội tụ. Hay trong nghiên cứu
của (C. Torresan và nnk., 2016) phương pháp được các tác giả sử dụng để có thể phân loại rừng là thuật toán phân cụm
K-means và thuật toán phân loại theo thứ bậc kết hợp với phương pháp máy học. Để đánh giá được độ chính xác của
phương pháp các tác giả đã sử dụng cây phân loại, tuy nhiên kết quả phân loại có sai số tương đối lớn 45.9% với dữ
liệu được chọn, còn đối với rừng tỉ lệ lỗi là 33.3%.
II. NGHIÊN CỨU KẾT HỢP THUẬT TOÁN MCC VÀ K-MEANS TRONG PHÂN LOẠI
ĐÁM MÂY ĐIỂM LIDAR
2.1. Thuật toán MCC
Thuật toán MCC là thuật toán được sử dụng để phân loại đám mây điểm LiDAR 3D được phát triển bởi
Moscow Forestry Sciences Laboratory, sử dụng chủ yếu để phân loại các tia phản xạ LiDAR trong môi trường rừng.
Thuật toán này được sử dụng để phân loại các điểm thành hai lớp là mặt đất và không mặt đất (Jeffrey S.Evans,
Andrew T.Hudak, 2007). MCC là thuật toán phân loại tín hiệu phản xạ LiDAR vượt quá ngưỡng độ cong của bề mặt,
cách tiếp cận đa tỉ lệ sẽ xác định độ lệch của các điểm cần phân loại với bề mặt trung bình và loại bỏ dần những điểm
này ra khỏi nhóm mặt đất. Thuật toán sẽ tính toán bề mặt trung bình từ những điểm mặt đất đặc trưng bằng phép lặp
TPS (Thin Plate Spline), sau đó sẽ hiệu chỉnh nó thông qua một lõi lọc (Jeffrey S. Evans, Andrew T. Hudak, 2007).
Thuật toán MCC có hai tham số là s (scale - biểu thị cho tỉ lệ) và t là ngưỡng độ cong (curvature threshold),
trong đó tham số tỉ lệ là hàm của tỉ lệ các đối tượng trên mặt đất và khoảng lấy mẫu (khoảng cách sau) của dữ liệu
LiDAR (Jeffrey S. Evans, Andrew T. Hudak, 2007). Triển khai thuật toán MCC các tác giả định nghĩa một vevtor Z(s)
chứa giá trị tọa độ của tất cả các điểm LiDAR. Vector này sẽ được sử dụng trong phép lặp bề mặt raster sử dụng phép
lặp TPS với độ phân giải theo tỉ lệ . Một lõi lọc có kích thước 3x3 duyệt qua tất cả các phép lọc để tìm một vector mới
x(s). Miền tỉ lệ l là mô hình lặp được thiết lập với tham số của mô hình chạy đến khi hội tụ. và t sẽ được định nghĩa
bởi người dùng (Jeffrey S. Evans, Andrew T. Hudak, 2007). Dung sai độ cong t sẽ được thêm vào x(s) và các điểm sẽ
được phân lớp vào lớp không mặt đất bằng việc sử dụng điều kiện “If Z(s) > c then phân lớp không mặt đất”. Trong đó
c là độ cong của miền tỉ lệ l (Jeffrey S. Evans, Andrew T. Hudak, 2007).
Thuật toán MCC được mô tả như sau (Jeffrey S. Evans, Andrew T. Hudak, 2007):
1) Một bề mặt phẳng được lặp bằng cách sử dụng Z(s) và TPS. Hai tham số của mô hình cho miền tỉ lệ l được
áp dụng là tham số tỉ lệ và ngưỡng độ cong t (khởi tạo và t do người dùng định nghĩa)
2) Một lõi lọc 3x3 sẽ duyệt qua toàn bộ bề mặt, một vector mới x(s) được định nghĩa có độ trùng khớp với Z(s)
3) Độ cong trong miền tỉ lệ l sẽ được tình theo công thức: c = x(s) + t; với x(s) là vector độ cao trung bình trùng
khớp với Z(s) trong miền tỉ lệ l và t là tham số ngưỡng độ cong trong miền tỉ lệ l
4) Điểm LiDAR sẽ được phân lớp vào lớp không mặt đất và bị loại bỏ nếu:
If Z(s) > c then phân lớp không mặt đất.
Với c là độ cong trong miền tỉ lệ l
5) Ngưỡng hội tụ j sẽ được đánh giá, sau đó mô hình lặp lại hoặc sẽ bắt đầu với một miền tỉ lệ mới
Hình 1. Mô tả thuật toán phân loại đám mây điểm LiDAR với MCC
- Nguyễn Thị Hữu Phương, Đặng Văn Đức, Nguyễn Trường Xuân, Trần Mạnh Trường 381
2.2. Áp dụng K-means trong phân loại nhóm điểm không mặt đất với thuật toán MCC
K-means là thuật toán phân cụm dành cho dữ liệu nhiều chiều, là thuật toán dễ hiểu, dễ triển khai tuy nhiên
điểm yếu của thuật toán là chỉ làm việc được với một giới hạn số lượng dữ liệu. Với dữ liệu đám mây điểm, thuật toán
K-means hoạt động với 3 chiều dữ liệu X, Y, Z trong tính toán trắc địa. Khoảng cách Euclide sẽ được sử dụng để tính
toán khoảng cách giữa các điểm(Kun Zhang và nnk., 2015).
Trong bài báo này, chúng tôi áp dụng thuật toán K-means để phân lớp các điểm bị loại bỏ khi được gán vào lớp
không mặt đất sau khi được phân loại với thuật toán MCC.
Những điểm sau phân loại với MCC sẽ được gán nhãn 2 nhóm điểm không mặt đất, nhãn 1 nhóm điểm mặt đất
và được lưu trong file có định dạng .las. Định dạng LAS là định dạng nhị phân được chuẩn hóa để lưu trữ dữ liệu đám
mây điểm 3 chiều và các thuộc tính điểm cùng với thông tin tiêu đề và các bản ghi độ dài biến đổi cụ thể cho dữ liệu.
Hàng triệu điểm dữ liệu được lưu trữ dưới dạng đám mây dữ liệu 3 chiều dưới dạng một loạt các điểm x (kinh độ), y
(vĩ độ) và z (độ cao). Ngoài thông tin về toạ độ (x, y, z) của điểm dữ liệu LiDAR có thể lữu trữ những thông tin khác
như cường độ của tín hiệu phản xạ, số tín hiệu phản xạ, thời gian đi và về, và nguồn (đường bay) của mỗi điểm
(NOAA, 2012). Trong đám mây điểm sau phân loại này, thu nhận những điểm có nhãn là 2 để tiến hành phân loại với
K-means. Kết quả này sẽ được sử dụng cho thành lập mô hình 3D của khu vực đo vẽ.
Thuật toán được triển khai như sau:
Input: đám mây điểm LiDAR
Output: điểm sau phân loại
For l = 1 to 3
Repeat
Lặp tìm S = TPS(U, , f); Lặp tìm S’ = 3x3
Untill điểm không thuộc U < 10% tổng số điểm của nó
Phân lớp các điểm còn lại của U vào lớp mặt đất
If Pj thuộc nhóm lớp không mặt đất
{Chọn số cụm cần phân loại, tính toán tâm của cụm khởi tạo
Repeat{ Gán điểm vào cụm có tâm gần nhất
Tính toán lại trọng tâm của cụm
∑
∑
} Untill hội tụ
Return tâm cụm, số điểm mỗi cụm}
End
Hình 2. Kết hợp thuật toán MCC và K-means trong phân loại đám mây điểm LiDAR
- 382 NGHIÊN CỨU KẾT HỢP THUẬT TOÁN MCC VÀ K-MEANS TRONG PHÂN LOẠI ĐÁM MÂY ĐIỂM LIDAR
III. THỬ NGHIỆM
3.1. Dữ liệu thử nghiệm
Bộ dữ liệu được sử dụng để thử nghiệm trong bài báo là dữ liệu đám mây điểm LiDAR được download từ trang
web www.opentopo.sdsc.edu, khu vực khảo sát là rừng quốc gia Tahoe. Với số lượng điểm là 780.405 điểm; Xmin,
Ymin = (717068.453734, 4366529.995007); Xmax, Ymax = (717471.08773, 4366736.144926). Đây là dữ liệu thu
được từ thiết bị quét được gắn trên không (Airborne LiDAR), mật độ điểm là 8,93 điểm /m 2, quét trên khu vực có diện
tích 89,7 km2. Với hệ thống toạ độ Horizontal: NAD83 (2011) UTM Zone 10N meters [EPSG: 26910], Vertical:
NAVD88 (Geoid 12a), phép chiếu UTM, đơn vị đo mét.
Hệ thống quét có các tham số:
ảng 1. Tham số của dữ liệu
Tham số Chỉ tiêu
Góc quét (Scan FOV) 0 – 500
Tần số quét 0 – 70Hz
Bước sóng tia laser 1064 nm
Thời gian lấy mẫu 1ns
Độ dài thời gian T0 = 40ns, Treturn = 440ns
Cường độ (Min, max) (1, 8160)
Hình 3. Hình ảnh về khu vực đo vẽ
3.2. Thử nghiệm và đánh giá
Lựa chọn tham số s = 3, t = 0,3 cho thuật toán phân loại với MCC.
Hình 4. Lựa chọn tham số cho thuật toán MCC
Với 3 miền tỉ lệ SD1, SD2, SD3, kết quả phân loại có 344.021 điểm được phân loại vào lớp mặt đất, còn
436.384 điểm thuộc lớp không mặt đất.
Hình 5. Kết quả sau phân loại
- Nguyễn Thị Hữu Phương, Đặng Văn Đức, Nguyễn Trường Xuân, Trần Mạnh Trường 383
Hình 6. Các điểm sau phân loại với MCC
Sau quá trình phân loại với MCC có 436.384 điểm được gán vào nhóm mặt đất, tham số s và t được lựa chọn
lần lượt là 3 và 0,3. Với 3 miền tỉ lệ SD1 = 1,5 (0,5s) với 4 lần lặp, SD2 = 3 (s) với 3 lần lặp, SD3 = 4,5 (1,5s) với 4 lần
lặp. Điều kiện hội tụ của thuật toán MCC là 0,0026% (9 điểm được gán vào lớp không mặt đất của miền tỉ lệ 3 với lần
lặp thứ 4). Với tỉ lệ điểm không mặt đất trong mỗi miền tỉ lệ như sau:
Hình 7. Tỉ lệ phân loại trong mỗi miền
Hình 8. DEM của khu vực khảo sát
Với 436.384 điểm sau phân loại thuộc lớp không mặt đất, tiếp tục phân loại với thuật toán K-means. Lựa chọn
thuộc tính độ cao (Z) của điểm làm thuộc tính phân cụm, điều kiện hội tụ đặt cho thuật toán là 0, số lần lặp lớn nhất là
10. Lựa chọn k = 3 tương ứng với số lớp được mô hình trong mô hình 3D của khu vực khảo sát.
Khi lựa chọn k = 3, tâm cụm khi khởi tạo và số lần lặp của thuật toán thay đổi như sau:
ảng 2. Khởi tạo tâm cụm và số lần lặp với k = 3
(a) Tâm cụm khi khởi tạo (b) Số lần lặp của thuật toán
Tâm cụm trong lần lặp cuối và số điểm được gán vào mỗi cụm:
- 384 NGHIÊN CỨU KẾT HỢP THUẬT TOÁN MCC VÀ K-MEANS TRONG PHÂN LOẠI ĐÁM MÂY ĐIỂM LIDAR
ảng 3. Số điểm sau phân loại được gán vào mỗi cụm
Hình 9. Kết quả sau phân loại với k = 3
Với k = 2 và k = 3, số điểm lỗi của thuật toán là 0 (số điểm không thuộc về cụm nào), điều kiện hội tụ của thuật
toán đều là 0, khoảng cách nhỏ nhất giữa tâm cụm khởi tạo với k = 2 là 118 trong khi đó với k = 3 là 59.
Có thể thấy, với số điểm tương đối lớn trên 400 nghìn điểm, thuật toán K-means vẫn cho ra số điểm lỗi là 0, số
lần lặp của thuật toán đều nhỏ hơn 10 – số lần lặp có thể chấp nhận. Sau quá trình phân loại, những điểm thuộc nhóm
không mặt đất được thu nhận và phân loại chi tiết hơn tuỳ theo mục đích sử dụng. Các điểm sau phân loại được gán
nhãn, và phân loại theo độ cao. Từ đó, có thể thành lập được các mô hình về khu vực khảo sát.
Hình 10. Mô hình đám mây điểm 3D
(a) Zmin (b) Zmax
Hình 11. Mô hình TIN với độ cao lớn nhất và nhỏ nhất
So sánh mô hình được thành lập với hình ảnh vệ tinh của khu vực khảo sát trong hình 3 có thể thấy mô hình 3D
được thành lập sau phân loại với MCC và K-means đáp ứng được yêu cầu.
IV. KẾT LUẬN
Dữ liệu đám mây điểm LiDAR là dữ liệu chứa nhiều thông tin có ích, do có khả năng thu nhận thông tin trên
một khu vực đo vẽ rộng lớn nên số lượng điểm của đám mây điểm thường rất lớn. Do đó, để lựa chọn được một thuật
toán phù hợp để phân loại là hoàn toàn cần thiết. Qua thử nghiệm cho thấy, thuật toán MCC là thuật toán phân loại đám
- Nguyễn Thị Hữu Phương, Đặng Văn Đức, Nguyễn Trường Xuân, Trần Mạnh Trường 385
mây điểm tự động, phân chia điểm thành hai lớp mặt đất và không mặt đất. Trong khi đó thuật toán K-means được sử
dụng để phân loại lớp điểm không mặt đất, có tỉ lệ điểm lỗi là 0, điều kiện hội tụ là 0. Có thể thấy, K-means có khả
năng sử dụng để phân loại đám mây điểm LiDAR, dữ liệu sau phân loại có thể áp dụng cho những bài toán cụ thể hơn.
V. LỜI CẢM ƠN
Các tác giả biết ơn sự ủng hộ bài báo này từ dự án IoIT (VAST) đề tài cơ sở có mã số CS18.10.
VI. TÀI LIỆU THAM KHẢO
[1] A. Brzank, C. Heipke. (2005). Classification of LiDAR data into water and land points in coastal areas. ISPRS.
[2] Beril Sirmacek, Roderik Lindenbergh. (2015). Automatic classification of trees from laser scanning point clouds.
ISPRS, 137-144.
[3] Borja Rodriguez - Cuenca, nnk. (2015). Automatic detection and classification of pole-like objects in urban point
cloud data using an anomaly detection algorithm. Remote Sensing, 7, 12680-12703.
[4] C. Torresan, nnk. (2016). Using classification trees to predict forest structure types from LiDAR data. Annals of
forest research, 59.
[5] ESRI. (2018, 06 09). What is LiDAR data? Retrieved from http://desktop.arcgis.com/en/arcmap/10.3/manage-
data/las-dataset/what-is-lidar-data-.htm.
[6] Jeffrey S. Evans, Andrew T. Hudak. (2007). A multiscale curvature algorithm for classifying discrete return
LiDAR in forest environments. IEEE transactions on geoscience and remote sensing , 1029-1038.
[7] Knowlegde Center. (2015, 5 28). What is point cloud data? Retrieved from
https://knowledge.safe.com/articles/257/what-is-a-point-cloud-what-is-lidar.html.
[8] Kun Zhang, nnk. (2015). A new kmeans clustering algorithm for point cloud. International Journal of Hybrid
Information Technology, 8(9), 157-170.
[9] N. Yastikli, Z. Cetin. (2014). Classification of LiDAR data with point based classification methods. ISPRS.
[10] Suresh K. Lodha, nnk. (2003). Aerial LiDAR data classification using AdaBoost.
[11] Yu chuan chang, nnk. (2008). Automatic classification of LiDAR data in to ground and non-ground points.
Remote sensing and Spatial information Sciences, 457-462.
[12] Zhuqiang Li, nnk. (2016). A three step approach for TLS point cloud classification. IEEE.
THE STUDY COMBINES MCC AND KMEANS ALGORITHMS IN LIDAR POINT CLOUD
CLASSIFICATION
Nguyen Thi Huu Phuong, Dang Van Duc, Nguyen Truong Xuan, Tran Manh Truong
ABSTRACT: In 2007, the authors Jeffrey S. Evans and Andrew T.Hudak proposed the MCC (Multiscale Curvature Classification)
algorithm to automatically classify the point cloud into ground and non-ground classess. In the classification process, the authors
only recorded the points in the ground class to conduct the DEM creation for the surveyed area, the non-ground point group was
eliminated, while this is the point group containing much information there. Desiring to collect and record useful information in this
point group, the paper focuses on the study of how to combine the MCC and K-means algorithms to optimize the LiDAR point cloud
classification problem.
nguon tai.lieu . vn
