ÐẠI HỌC QUỐC GIA HÀ NỘI
TRUỜNG ÐẠI HỌC CÔNG NGHỆ
NGUYỄN NGỌC LAN NGHIÊN CỨU MÔ HÌNH ĐỘ CAO SỐ VÀ ỨNG DỤNG
TRONG HỆ THỐNG THÔNG TIN ĐỊA LÝ

LUẬN VĂN THẠC SĨ


Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ Hướng dẫn khoa học: TS. NGUYỄN HẢI CHÂU
Hà Nội - 2011
MỤC LỤC
MỞ ĐẦU 5
Chương 1. TỔNG QUAN VỀ MÔ HÌNH ĐỘ CAO SỐ 7
1.1. Dữ liệu độ cao số 7
1.1.1. Mặt thủy chuẩn 7
1.1.2. Hệ thống độ cao 7
1.1.3. Hệ toạ độ địa lý 8
1.2. Mô hình độ cao số là gì? 9
1.3. Mô hình dữ liệu trong DTM 10
1.3.1. Đường đồng mức 10
1.3.2. Lưới 12
1.3.3. Mạng tam giác không đều 14

2.4.3. Xây dựng mạng tam giác không đều từ dữ liệu phân phối không đều 37
2.4.4. Xây dựng mạng tam giác không đều từ dữ liệu phân phối đặc biệt 38
2.5. Xây dựng mạng lưới cho mô hình hoá bề mặt 38
2.5.1. Xây dựng mạng lưới tốt hơn lưới thô 39
2.5.2. Xây dựng mạng lưới từ dữ liệu phân phối ngẫu nhiên 41
2.5.3. Xây dựng mạng lưới từ dữ liệu đường đồng mức 42
Chương 3. XÂY DỰNG MẠNG TAM GIÁC KHÔNG ĐỀU 44
3.1. Một số khái niệm cơ bản 44
3.2. Cấu trúc mạng tam giác không đều 45
3.3. Nguyên tắc hình thành mạng tam giác không đều 46
3.4. Xây dựng mạng tam giác không đều dựa trên điều kiện Delaunay 51
3.4.1. Phương pháp kiểm tra tam giác thoả điều kiện Denaunay 51
3.4.2. Thuật toán Flip 52
3.4.3. Thuật toán Incremental 54
3.4.4. Thuật toán divide and conquer 55
3.4.5. Thuật toán Sweephull 60
3.4.6. Thuật toán Sweepline 62
3.5. Một số ứng dụng của mạng tam giác không đều 63
3.6. Cài đặt thử nghiệm 67
KẾT LUẬN 70
TÀI LIỆU THAM KHẢO 71

DSM
Digital Surface Model - Mô hình bề mặt số
DTM
Digital Terrain Model - Mô hình địa hình số
GIS
Geographic Information System - Hệ thống thông tin địa lý
GPS
Global Positioning System - Hệ thống định vị toàn cầu
INS
Inertial Navigation System - Hệ thống dẫn đường quán tính
LiDAR
Light Detecting And Ranging - Công nghệ LiDAR
LOP
Local Optimization Procedure - Quá trình tối ưu hóa cục bộ
TIN
Triangular Irregular Network - Mạng tam giác không đều
TRN
Triangular Regular Network - Mạng tam giác đều

tam giác (b) 27
Hình 2.4. Mô hình hóa bề mặt lai 29
Hình 2.5. Sơ đồ Voronoi của một tập hợp điểm 31
Hình 2.6. Tính không liên tục trong đạo hàm cấp 1 của một bề mặt liên tục 31
Hình 2.7. Ví dụ về các bề mặt mịn 32
Hình 2.8. Xây dựng mạng tam giác đều từ một lưới đồng đều 33
Hình 2.9. Các kiểu có thể có của bề mặt xây dựng từ một lưới hình vuông 34
Hình 2.10. Bề mặt địa hình với tập dữ liệu phân phối đồng đều 34
Hình 2.11. Trạng thái địa hình và giá trị vi phân bậc hai của nó 35
Hình 2.12. Các tam giác Delaunay của dữ liệu hỗn hợp 38
Hình 2.13. Các tam giác phẳng xây dựng từ dữ liệu đường đồng mức 39
Hình 2.14. Lấy mẫu đơn giản cho hình thành lưới tốt hơn lưới thô 39
Hình 2.15. Xây dựng lưới tốt hơn lưới thô bằng cách lấy mẫu lại 40
Hình 2.16. Xây dựng mạng lưới từ dữ liệu phân phối ngẫu nhiên 41
Hình 2.17. Từ những dữ liệu ngẫu nhiên tới dữ liệu lưới thông qua tam giác 41
Hình 2.18. Nội suy đường đồng mức đặc trưng bằng cách sử dụng các trục xác
định trước 42
Hình 2.19. Lựa chọn hướng dốc và các điểm dữ liệu cho phép nội suy bậc 3 dọc
theo sườn dốc 43
Hình 3.1. Đường tròn ngoại tiếp tam giác 44 3
Hình 3.2. Ví dụ mô hình mạng TIN 45
Hình 3.3. Các cách tiếp cận xây dựng mạng tam giác không đều 47
Hình 3.4. Đường tròn ngoại tiếp tam giác Delaunay 48
Hình 3.5. Minh hoạ quá trình xử lý LOP theo nguyên tắc 2 49
Hình 3.6 . Xây dựng tam giác Delaunay từ sơ đồ Voronoi 50
Hình 3.7. Mối quan hệ kép giữa sơ đồ Voronoi và tam giác Delaunay 51
Hình 3.8. Mạng tam giác không chồng lấp của một tập hợp điểm 61

4
DANH MỤC CÁC BẢNG

Bảng 2.1. Hàm đa thức sử dụng cho xây dựng lại bề mặt 24
Bảng 3.1. Cấu trúc dữ liệu của một mạng TIN 46
5
MỞ ĐẦU
Ngày nay, với sự phát triển mạnh mẽ của Khoa học công nghệ, Hệ thống
thông tin địa lý (GIS), lĩnh vực Trắc địa - Bản đồ cũng chịu ảnh hưởng rất lớn về
công cụ, cách thức quản lý và sử dụng các sản phẩm dữ liệu địa hình. Việc can
vẽ biên tập trên giấy trước kia đã được chuyển sang dạng số và lưu trữ trên máy
vi tính. Cùng với đó là nhu cầu về sử dụng dữ liệu địa hình như là một công cụ
không thể thiếu trong các công đoạn thành lập bản đồ và ứng dụng cho khảo sát,
phân tích địa hình, thiết kế, quy hoạch Một dữ liệu quan trọng cần phải kể đến
đó là dữ liệu độ cao trên mặt đất.
Dựa trên dữ liệu về độ cao của bề mặt địa hình chúng ta có thể xây dựng
một mô hình ảo cho bề mặt trái đất. Trên thực tế, bề mặt trái đất là liên tục song
chúng ta chưa bao giờ đo được một bề mặt độ cao một cách liên tục như vậy.
Chúng ta chỉ có thể đo được độ cao tại một vị trí nào đó trên mặt đất. Kết quả
cuối cùng là một tập hợp các điểm đo rời rạc [16].
Mặc dù, công nghệ cao hiện nay có thể cho chúng ta tập điểm đo nhiều
hơn nhưng vẫn là các điểm đo rời rạc. Do vậy, cần phải tìm kiếm các phương
pháp mô hình hóa bề mặt địa hình biểu diễn chính xác nhất các thông tin bề mặt
dựa trên dữ liệu độ cao số đo được.

• Ứng dụng của mô hình DTM
Chương 2: Mô hình hóa bề mặt địa hình số
• Một số khái niệm cơ bản trong mô hình hóa bề mặt
• Phân loại phương pháp mô hình hóa bề mặt
• Xây dựng mạng tam giác cho mô hình hóa bề mặt
• Xây dựng mạng lưới cho mô hình hóa bề mặt
Chương 3: Xây dựng mạng tam giác không đều
• Một số khái niệm cơ bản
• Nguyên tắc xây dựng mạng tam giác không đều (TIN)
• Thuật toán xây dựng TIN dựa trên nguyên tắc Delaunay
• Cài đặt thử nghiệm
Kết luận:
Đánh giá kết quả đạt được và định hướng phát triển.
7
Chương 1. TỔNG QUAN VỀ MÔ HÌNH ĐỘ CAO SỐ

1.1. Dữ liệu độ cao số
Để nghiên cứu trái đất và biểu diễn nó trên mặt phẳng, con người phải tiến
hành đo đạc mặt đất. Công tác trắc địa này thực chất là xác định vị trí các điểm
đặc trưng của bề mặt đất trong hệ quy chiếu tọa độ nào đó hay có thể hiểu đó là
định vị điểm. Vị trí các điểm trên mặt đất được xác định bởi thành phần tọa độ
mặt bằng và độ cao.
Độ cao là thành phần quan trọng để xác định vị trí không gian của các
điểm trên mặt đất, để có độ cao các điểm ta phải xác định các mặt chuẩn quy
chiếu độ cao [6].
Độ cao được biểu diễn dưới dạng số được gọi là dữ liệu độ cao số.
1.1.1. Mặt thủy chuẩn

khoảng cách theo phương đường dây dọi từ điểm đó tới mặt thủy chuẩn quy ước
[1]. Trong hình 1.1, nếu chọn mặt thủy chuẩn đi qua điểm B là mặt thủy chuẩn
quy ước thì độ cao quy ước của điểm A là đoạn h
AB
.
Các công trình quy mô nhỏ, xây dựng ở nơi hẻo lánh xa hệ thống độ cao
nhà nước thì có thể dùng độ cao quy ước. Trong xây dựng công trình công
nghiệp và dân dụng người ta thường chọn mặt thủy chuẩn quy ước là mặt phẳng
nền nhà tầng một.
1.1.3. Hệ toạ độ địa lý
Hệ tọa độ địa lý nhận trái đất là hình cầu với gốc tọa độ là tâm trái đất,
mặt phẳng kinh tuyến gốc qua đài thiên văn Greenwich ở nước Anh và mặt
phẳng vĩ tuyến gốc là mặt phẳng xích đạo (hình 1.2). Một điểm trên mặt đất
trong hệ tọa độ địa lý được xác định bởi hai thành phần tọa độ là vĩ độ ϕ và
kinh độ λ . [1]

Hình 1.2. Hệ tọa độ địa lý
Vĩ độ của điểm M là góc hợp bởi phương đường dây dọi đi qua điểm đó
với mặt phẳng xích đạo. Vĩ độ nhận giá trị 0
0
ở xích đạo và 90
0
ở hai cực. Các
điểm trên mặt đất có vĩ độ bắc hay nam tùy thuộc chúng nằm ở bắc hay nam bán
cầu.
Kinh độ của một điểm là góc nhị diện hợp bởi mặt phẳng kinh tuyến gốc
và mặt phẳng kinh tuyến đi qua điểm đó. Kinh độ nhận giá trị từ 0
0
đến 180
0

điểm trong mô hình. DEM là một thuật ngữ được sử dụng rộng rãi tại Hoa
Kỳ và thường đề cập đến việc tạo ra một mảng liên tục của độ cao, thông
thường là hình vuông hoặc một mẫu hình lục giác trên địa hình.
 DSM (Digital Surface Model): Mô hình bề mặt số (DSM) là một mô
hình số độ cao miêu tả bề mặt trái đất và bao gồm cả các đối tượng vật thể
trên đó như nhà cửa, cây, đường giao thông
 DTM (Digital Terrain Model): Một khái niệm phức tạp hơn không chỉ
liên quan đến chiều cao và độ cao mà còn thể hiện thông tin địa lý khác
như các con sông hay các dãy núi… Hơn nữa, DTM cũng có thể bao gồm
các dữ liệu thu được về địa hình như độ dốc, hình dáng và tầm
nhìn. Trong nghĩa hẹp, DTM đại diện cho một mô hình nổi. Theo nghĩa
rộng, một DTM được hầu hết mọi người biết đến bao gồm cả mặt bằng và
dữ liệu địa hình nổi. Hiểu một cách đơn giản thì: Mô hình địa hình số 10
(DTM) là mô hình số miêu tả bề mặt trái đất nhưng không bao gồm các
đối tượng vật thể trên đó [13].
1.3. Mô hình dữ liệu trong DTM
Trong quá trình xử lý dữ liệu địa hình, tập hợp các thành phần dữ liệu liên
quan được thu thập. Để xây dựng một DTM toàn diện và có thể sử dụng thì việc
xây dựng các mối quan hệ topo giữa các thành phần dữ liệu cũng như một mô
hình nội suy biểu diễn bề mặt là rất cần thiết.
Một bề mặt liên tục, chẳng hạn như Trái đất, có một số lượng vô hạn
điểm có thể được đo. Rõ ràng, chúng ta không thể ghi lại mọi điểm, do vậy một
phương pháp lấy mẫu phải được sử dụng để tách ra các điểm đặc trưng. Những
điểm đặc trưng sau đó có thể được sử dụng để xây dựng một mô hình bề mặt
gần giống với bề mặt thực tế. Một mô hình bề mặt phải đảm bảo:
1. Đại diện chính xác cho các bề mặt.
2. Thích hợp cho việc kết nối dữ liệu hiệu quả.

dụng cho hầu hết các nơi trên thế giới.
Độ chính xác của đường đồng mức phụ thuộc vào việc các đường này đã
được tạo ra từ dữ liệu chính hay có nguồn gốc từ dữ liệu được tách ra. Nếu các
đường đồng mức được tạo ra từ tập dữ liệu điểm, khi đó vị trí của những đường
đồng mức được nội suy giữa các giá trị đã biết. Nếu đường đồng mức bắt được
từ các bức ảnh trên không như dữ liệu chính sử dụng một máy phân tích lập thể,
đường đồng mức là chính xác cao.
Khi trình bày bản đồ cứng, mỗi đường đồng mức được vẽ như là một
đường liên tục kế tiếp trên bề mặt. Mỗi đường chứa một số vô hạn điểm mẫu
tiềm năng. Khi số hóa một bản đồ, hệ thống sẽ tự động hóa các đường đồng mức
của nó từ bản cứng sang định dạng số. Các đường phải được lấy mẫu lại bởi vì
việc lưu trữ tất cả các điểm dọc theo một đường thẳng là không thực tế. Kỹ thuật
phổ biến nhất là số hóa hoặc lựa chọn các điểm cong quan trọng dọc theo đường
đồng mức sao cho các đường được số hóa không có những sai chệch quan trọng
so với các đường đồng mức thực tế. Điều này tạo nên một nhược điểm lớn của
đường đồng mức là chúng chỉ cho thấy giá trị bề mặt dọc theo đường này,
những điểm dị thường của bề mặt ở giữa các đường đồng mức không được mô
tả. Tuy nhiên, khi bề mặt đã được biểu diễn như là đường đồng mức thì nội suy
có thể được sử dụng để lấy độ cao cho các vùng giữa đường đồng mức [13]. 12
1.3.2. Lưới
Lưới là một cấu trúc ma trận ghi lại mối quan hệ topo giữa các điểm dữ
liệu. Kể từ khi cấu trúc dữ liệu này là tương tự như cấu trúc lưu trữ mảng của
máy tính kỹ thuật số thì việc xử lý ma trận độ cao là hoàn toàn đơn giản và do
đó, các thuật toán mô hình địa hình lưới cơ bản có xu hướng được đơn giản hoá.
Mặt khác, mật độ điểm trong lưới chuẩn không bị ảnh hưởng bởi sự phức
tạp địa hình, do đó một số lượng lớn các điểm dữ liệu được yêu cầu để mô tả địa
hình sẽ thể hiện mức độ chính xác cao.

thường cho kết quả biểu diễn bề mặt chính xác hơn.
3. Giảm khoảng cách giữa các điểm mẫu có thể làm tăng dữ liệu dư thừa.
Điều này đặc biệt đúng với các khu vực bề mặt không có sự thay đổi đáng
kể, khi đó không cần thiết quá nhiều các điểm lưới để mô tả chúng chính
xác. Ảnh vệ tinh
Ảnh 3-D
Lấy mẫu dưới
Lấy mẫu trên
Hình 1.6. Tác động của kích cỡ lưới lên biểu diễn bề mặt
14
Cấu trúc dữ liệu Lưới
 Ưu điểm:
- Đã có lưới DTM không cần xử lý thêm nữa.
- Dễ dàng lưu trữ và thao tác.
- Thích hợp cho nhiều loại bề mặt.
- Dễ dàng tích hợp với các cơ sở dữ liệu dạng raster.
- Đã xuất hiện phổ biến với các tính năng địa hình nguồn.
 Nhược điểm:
- Lấy mẫu không hiệu quả, sẽ luôn có những điểm không cần thiết mặc
dù tiến độ lấy mẫu trên lưới với địa hình phức tạp là có thể ngày càng
chính xác hơn.
- Các điểm cao nhất hoặc thấp nhất trên cảnh quan hiếm khi được lấy
mẫu, vì chúng có thể không rơi vào lưới mẫu.
- Không có khả năng sử dụng các kích thước lưới khác nhau để phản

biễu diễn tốt bởi các tam giác phẳng như: hình ảnh đóng băng. Tam giác làm
việc tốt nhất trong khu vực độ dốc, nơi cạnh TIN có thể được liên kết với các
đoạn cắt ngang như: đoạn dọc theo các rặng núi hoặc con kênh.
Cấu trúc dữ liệu TIN
 Ưu điểm:
- Có khả năng mô tả bề mặt ở các mức khác nhau của độ phân giải.
- Hiệu quả trong lưu trữ dữ liệu.
- TIN có thể bao gồm các điểm cao nhất/thấp nhất trên vùng.
- Có thể tăng lấy mẫu tại các khu địa hình cao.
- Thích hợp cho nhiều loại bề mặt.
 Nhược điểm:
Trong các trường hợp yêu cầu kiểm tra hình ảnh và điều khiển thủ
công của mạng.
1.4. Thu thập dữ liệu cho DTM
Thông tin không gian mặt đất là đầu vào rất quan trọng trong các lĩnh vực
thành lập bản đồ số, phân tích không gian, mô hình hóa bề mặt trái đất. Sau đây
là một số phương pháp được sử dụng để thu thập dữ liệu xây dựng mô hình
DTM: 16
1.4.1. Khảo sát mặt đất
Đây là phương pháp cơ bản mang tính thủ công. Dữ liệu được thu thập
thông qua quá trình khảo sát, đo đạc trực tiếp của con người trên cơ sở sử dụng
các thiết bị đo đạc hiện có.

Hình 1.8. Thiết bị khảo sát mặt đất
Phương pháp này thường mang lại tập dữ liệu với độ chính xác cao. Tuy
nhiên, tiến hành thu thập dữ liệu theo phương pháp này tốn khá nhiều thời gian
và công sức, chỉ phù hợp với khu vực địa hình nhỏ. Vì vậy khảo sát mặt đất

công nghệ xử lý ảnh số hay giải đoán bằng mắt thường, những thông tin này sẽ
chuyển đến cho người dùng.
1.4.3. Sử dụng dữ liệu bản đồ
DTM có thể được tạo ra từ các dữ liệu bản đồ, chẳng hạn như bản đồ
đường đồng mức và bản đồ trạng thái. Những dữ liệu tương tự này có thể được
số hóa thông qua số hóa thủ công hoặc bằng các phương tiện tự động quét raster
và vector.
: Tiến hành số hóa các đường đồng mức theo phương
pháp thủ công vẫn được coi là phương pháp tiêu chuẩn để xây dựng một
DTM. Mỗi đường đồng mức được số hóa riêng lẻ và được gán mã thể
hiện độ cao tương .
(scanning):
.
Do chi phí của các phương pháp thu thập dữ liệu địa hình trực tiếp (khảo
sát và chụp ảnh lập thể) tương đối cao, và hiện có một khối lượng lớn các bản đồ
giấy thì phương pháp gián tiếp là chiếm ưu thế hơn trong các dự án thu thập dữ
liệu lớn. Điều này đặc biệt phù hợp đối với các cơ quan lập bản đồ quốc gia
Hình 1.9. Hệ thống viễn thám
18
hoặc quân đội. Hình 1.10 cho thấy một mẫu của các đường đồng mức quét số
hóa tạo ra một mô hình loại này.

Hình 1.10. Mẫu quét số hóa và các đường đồng mức dạng vector từ Bản đồ
quốc gia của Thụy Sĩ với tỉ lệ 1:25000 [13]

cách giữa các điểm đo phụ thuộc vào góc quét của máy quét và độ cao máy bay.
Dùng máy bay nhẹ loại hai hay một động cơ, với thông số làm việc chính là: vận
tốc bay 200 đến 250km/giờ (55 đến 70m/giây), độ bay cao chụp 300 đến 1000m,
góc quét chính ± 30, đến ± 20 độ, laser loại 2000 đến 5000 xung/giây [16].

Các thông số được chọn để thu được các điểm với mật độ vài mét, cung
cấp đủ số liệu để tạo mô hình địa hình số DTM đáp ứng hầu hết mọi yêu cầu
ứng dụng về lập bản đồ các loại.
Yếu tố đầu tiên trong độ chính xác của mô hình DTM là số liệu GPS. Sai
số vị trí và định hướng của máy bay, góc phóng tia, khúc xạ khí quyển và vài
nguồn sai số khác làm giảm cấp toạ độ của điểm mặt 5 đến 10 cm. Qua nghiên
cứu đánh giá độ chính xác LiDAR đạt được về độ cao là 10 - 20cm, về mặt bằng
là khoảng 1m.
LiDAR rất đắc dụng trong việc thu thập số liệu độ cao trong trường hợp
rừng dày đặc, nơi mà ảnh không bộc lộ sự kém độ chính xác thông tin địa hình
vì tán cây dày che phủ. Không giới hạn bởi điều kiện môi trường hạn chế của
Hình 1.11. Nguyên lý hoạt động của hệ thống LiDAR 20
ảnh hàng không. LiDAR hàng không nổi lên như một thay thế hấp dẫn đối với

hình hóa và phân tích thông tin địa hình không gian.
Các lĩnh vực ứng dụng của DTM bao gồm:
1.5.1. Ứng dụng trong Xây dựng
Phạm vi ứng dụng DTM trong các dự án xây dựng các con đường, đường
sắt, đập, hồ chứa, kênh, rạch, đất khai hoang, và khai thác mỏ… gần như vô tận.
Cụ thể, DTM hỗ trợ khảo sát và thiết kế về cơ sở vật chất trong các mô hình địa 21
hình của các dự án nêu trên. Các kỹ sư xây dựng có thể sử dụng mô hình DTM
để thực hiện các thao tác cắt-và-điền vào các vấn đề liên quan đến thiết kế đường
bộ trong quy hoạch, thiết lập các thông tin, cảnh quan mô hình 3-D, trực quan
cho nhiệm vụ xây dựng dân dụng: t ông,
vị trí và quy hoạch tuyến đường,
, tính toán thể tích trong việc xây dựng đập, hồ chứa …
1.5.2. Ứng dụng trong ngành Khoa học Trái đất
Thông tin chính xác về bề mặt của Trái đất có ý nghĩa là nền móng cho tất
cả các ứng dụng khoa học địa lý. Ví dụ, trong mô hình dự báo thời tiết và khí
hậu, mô hình chuyển đổi giữa mặt đất và bầu khí quyển cũng như của các biến
động trong các tầng lớp khí quyển thấp hơn cũng dựa vào địa hình và DTM toàn
cầu. Nhiều trung tâm ứng dụng khoa học địa lý và trái đất còn ứng dụng chủ yếu
vào việc phân tích và mô tả trên các dạng địa hình đặc biệt.
Đây có thể bao gồm nghiên cứu tác động khí hậu, mô hình địa chất, thuỷ
văn, địa mạo và phân tích cảnh quan, phân tích mô hình sinh lý, nghiên cứu địa
chất, bản đồ nguy cơ tạo ra các mối nguy hiểm địa chấn, nguy hiểm sạt lở đất,
núi lửa, xói mòn… Tạo độ dốc, bản đồ bề mặt, và mặt nghiêng độ dốc để tạo ra
các bản đồ nổi là các nhiệm vụ phổ biến được thực hiện trong khoa học trái đất
sử dụng DTM.
1.5.3. Ứng dụng trong Quy hoạch và Quản lý tài nguyên
Đây là một nhóm tổng hợp của các lĩnh vực khác nhau bao gồm viễn