Xây dựng bản đồ giao thông sử dụng GPS Tracks: Luận văn Thạc sĩ

Hướng dẫn xây dựng bản đồ giao thông chi tiết từ GPS tracks. Từng bước tạo bản đồ số chính xác, hữu ích cho mọi người dùng. Tìm hiểu ngay!

• Tác giả: Đặng Văn Huy
• Người hướng dẫn: TS. Phạm Quang Dũng
• Trường học: Trường Đại học Bách khoa Hà Nội
• Chuyên ngành: Kỹ thuật Máy tính và Truyền thông
• Đề tài: Xây dựng bản đồ giao thông sử dụng GPS Tracks
• Loại tài liệu: Luận văn thạc sĩ kỹ thuật
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƢƠNG 1: TỔNG QUAN CÁC HƢỚNG TIẾP CẬN XÂY DỰNG BẢN ĐỒ GIAO THÔNG SỬ DỤNG GPS TRACKS
• 1.1. Sơ lƣợc về hệ thống định vị toàn cầu GPS
• 1.2. Các hƣớng tiếp cận xây dựng bản đồ giao thông sử dụng GPS tracks
• 1.2.1. Ứng dụng phân cụm
• 1.2.2. Thuật toán ƣớc lƣợng mật độ hạt nhân
• 1.2.3. Thuật toán xử lý đƣờng cong tại các nút giao nhau
• 1.2.4. Thuật toán phát hiện nút giao thông
• 1.3. Mục tiêu của luận văn
• 2. CHƢƠNG 2: ĐỀ XUẤT QUY TRÌNH XÂY DỰNG BẢN ĐỒ GIAO THÔNG SỬ DỤNG GPS TRACKS
• 2.1. Quy trình xây dựng một bản đồ giao thông hoàn thiện
• 2.2. Xây dựng ứng dụng thu thập dữ liệu GPS trên smartphone
• 3. KẾT QUẢ THỰC NGHIỆM ĐẠT ĐƢỢC
• 3.1. Kết quả đạt đƣợc
• DANH MỤC TÀI LIỆU THAM KHẢO
• Phụ lục 1: Cài đặt thuật toán xấp xỉ chuỗi các điểm GPS để rút gọn kích thƣớc dữ liệu
• Phụ lục 2: Cài đặt Tool GPSMapEdit
• Phụ lục 3: Cài đặt phần mềm thu thập dữ liệu GPS
• Phụ lục 4 : Định dạng file *
• Phụ lục 5: Định dạng OpenStreetMap

Tóm tắt

I. Khám phá tiềm năng Xây dựng Bản Đồ Giao Thông từ GPS Tracks Tổng quan ứng dụng

Trong bối cảnh đô thị hóa nhanh chóng và sự phát triển vượt bậc của công nghệ thông tin, vai trò của bản đồ số trong quản lý và quy hoạch giao thông ngày càng trở nên thiết yếu. Hệ thống định vị toàn cầu (GPS) đã mở ra một kỷ nguyên mới trong việc thu thập dữ liệu địa không gian chính xác, cho phép các nhà nghiên cứu và kỹ sư phát triển các phương pháp tiên tiến để xây dựng bản đồ giao thông từ GPS Tracks. Khác với các phương pháp truyền thống tốn kém, việc sử dụng dữ liệu GPS từ các phương tiện di chuyển hàng ngày mang lại khả năng cập nhật liên tục và độ chi tiết cao, phản ánh chân thực luồng giao thông và mật độ giao thông theo thời gian thực. Bài viết này sẽ đi sâu vào quy trình, thách thức, và các giải pháp đột phá trong lĩnh vực quan trọng này, đặc biệt dựa trên các sáng kiến kinh nghiệm và nghiên cứu chuyên sâu.

1.1. Vai trò thiết yếu của bản đồ số trong giao thông hiện đại và quản lý đô thị

Ngày nay, bản đồ số đã thay thế đáng kể bản đồ giấy truyền thống nhờ các tính năng ưu việt như khả năng lưu trữ gọn nhẹ, truy vấn thông tin đường đi, khoảng cách, và vị trí một cách dễ dàng, nhanh chóng. Các hệ thống thông tin địa lý (GIS) tích hợp bản đồ số cung cấp nền tảng vững chắc cho việc ra quyết định trong quy hoạch đô thị, quản lý vận tải, và phát triển hạ tầng. Khả năng hiển thị tuyến đường giao thông, điểm tắc nghẽn, và các thông tin liên quan giúp người tham gia giao thông tối ưu hóa lộ trình, tiết kiệm thời gian và chi phí. Theo nghiên cứu của Đặng Văn Huy (2014), bản đồ số chiếm một vị trí rất quan trọng trong lĩnh vực giao thông vận tải, là công cụ không thể thiếu để tối ưu hóa di chuyển.

1.2. Định vị vệ tinh GPS và nguyên lý thu thập dữ liệu GPS Tracks

Hệ thống định vị toàn cầu (GPS), ban đầu được phát triển cho mục đích quân sự, nay đã trở thành công cụ không thể thiếu trong nhiều lĩnh vực dân sự, đặc biệt là giao thông. Hệ thống này bao gồm ba phân đoạn chính: không gian (vệ tinh), điều khiển (trạm mặt đất), và người dùng (thiết bị thu GPS). Thiết bị thu GPS ghi lại nhật ký GPS (GPS Logs) dưới dạng các điểm tọa độ (kinh độ, vĩ độ, cao độ) theo thời gian. Các mã tín hiệu C/A và P từ vệ tinh được sử dụng để tính toán vị trí, với độ chính xác dao động từ vài mét đến hàng chục mét tùy thuộc vào loại thiết bị và điều kiện môi trường. Công nghệ Assisted-GPS (A-GPS) còn hỗ trợ tăng cường độ chính xác và tốc độ định vị bằng cách kết hợp tín hiệu vệ tinh với trạm trung gian mặt đất, giúp thu thập dữ liệu GPS ổn định hơn, giảm thiểu sai số trong quá trình xây dựng bản đồ giao thông.

II. Thách thức lớn khi xây dựng bản đồ giao thông từ GPS Tracks thô

Mặc dù dữ liệu GPS mang lại nhiều lợi ích, quá trình xây dựng bản đồ giao thông từ GPS Tracks không hề đơn giản. Dữ liệu thô thường chứa nhiều nhiễu và sai số do các yếu tố môi trường (tòa nhà cao tầng, cây cối, thời tiết) hoặc hạn chế của thiết bị thu. Điều này đặt ra những thách thức đáng kể trong việc tái tạo chính xác các tuyến đường giao thông và mạng lưới đường bộ. Ngoài ra, việc xử lý lượng lớn dữ liệu xe di chuyển cũng đòi hỏi các thuật toán và công cụ mạnh mẽ, hiệu quả. Việc đảm bảo độ chính xác và loại bỏ các đoạn đường ảo là yếu tố then chốt để tạo ra một bản đồ định tuyến đáng tin cậy, giúp giải quyết các bài toán về tắc nghẽn giao thông và luồng giao thông.

2.1. Vấn đề nhiễu và độ chính xác của dữ liệu GPS ban đầu

Một trong những thách thức hàng đầu khi xây dựng bản đồ giao thông từ GPS Tracks là xử lý dữ liệu GPS thô. Dữ liệu GPS thu được từ các phương tiện di chuyển thường xuyên bị ảnh hưởng bởi nhiễu tín hiệu, dẫn đến các điểm tọa độ không chính xác hoặc dịch chuyển so với vị trí thực tế trên bản đồ. Các yếu tố như sự che khuất của các tòa nhà cao tầng, hẻm núi đô thị ('urban canyons'), điều kiện thời tiết xấu, hoặc chất lượng thiết bị thu GPS kém có thể làm giảm độ chính xác của dữ liệu. Những lỗi này tạo ra các 'dấu vết' GPS không rõ ràng, chồng chéo, hoặc bị lệch, gây khó khăn cho việc nhận diện chính xác hình dạng và vị trí của tuyến đường giao thông. Việc làm mịn và chuẩn hóa dữ liệu GPS là bước tiền xử lý quan trọng để giảm thiểu sai số, đảm bảo cơ sở dữ liệu đầu vào có chất lượng cao cho quá trình xây dựng bản đồ sau này.

2.2. Phức tạp trong việc xử lý dữ liệu GPS và phát hiện tuyến đường giao thông

Việc xử lý dữ liệu GPS để phát hiện và tái tạo tuyến đường giao thông là một bài toán phức tạp, đặc biệt khi đối mặt với lượng dữ liệu GPS lớn và mật độ thấp. Khi nhật ký GPS quá thưa thớt, việc xác định các con đường rõ ràng trở nên khó khăn. Ngược lại, với mật độ quá cao, dữ liệu có thể bị chồng chéo, tạo ra các 'đường viền' hoặc 'đường ảo' không có thật trên thực tế. Hơn nữa, việc nhận diện các nút giao thông, đường cong, hay phân biệt các làn đường trên cùng một tuyến đường đòi hỏi các thuật toán xây dựng bản đồ tinh vi. Các thuật toán ước lượng mật độ hạt nhân và phương pháp phân tích không gian là cần thiết để biến hàng triệu điểm dữ liệu thành một mạng lưới giao thông có ý nghĩa. Điều này đòi hỏi sự kết hợp giữa kiến thức về GIS và khả năng lập trình để phát triển các giải pháp xử lý hiệu quả.

III. Phương pháp tiếp cận tối ưu để xây dựng bản đồ giao thông từ GPS Tracks

Để khắc phục những thách thức đã nêu, nhiều phương pháp và thuật toán xây dựng bản đồ tiên tiến đã được đề xuất để xây dựng bản đồ giao thông từ GPS Tracks một cách hiệu quả và chính xác. Các hướng tiếp cận này tập trung vào việc chuyển đổi dữ liệu GPS thô thành một mạng lưới đường bộ định tuyến, có khả năng phản ánh đúng cấu trúc hình học và kết nối của hạ tầng giao thông. Một trong những hướng nghiên cứu chính là ứng dụng các kỹ thuật phân tích không gian và học máy để làm mịn dữ liệu, loại bỏ nhiễu, và phát hiện các đặc điểm quan trọng của đường bộ. Mục tiêu cuối cùng là tạo ra một bản đồ định tuyến đáng tin cậy, có thể sử dụng cho các ứng dụng như tìm đường đi ngắn nhất, quản lý luồng giao thông, và phát hiện tắc nghẽn giao thông.

3.1. Phân cụm dữ liệu GPS và tạo mạng lưới tuyến đường giao thông hiệu quả

Một hướng tiếp cận nổi bật trong xây dựng bản đồ giao thông từ GPS Tracks là sử dụng phương pháp phân cụm. Theo Cao, Lili, và John Krumm (2009) [1], phương pháp này chuyển đổi dấu vết GPS thô thành mạng lưới đường bộ định tuyến bằng cách làm mịn và nhóm các dấu vết GPS cùng thuộc một con đường. Quy trình gồm hai bước chính: Đầu tiên, làm rõ các con đường bị lỗi do nhiễu bằng cách nhóm các dấu vết GPS lại với nhau. Sau đó, từ kết quả này, áp dụng thuật toán xây dựng bản đồ để tạo ra một đồ thị gồm các nút và các cạnh mô tả hướng đi trên mỗi con đường, từ đó hình thành mạng lưới đường bộ định tuyến. Kết quả thực nghiệm cho thấy phương pháp này giữ được các kết nối và đặc tính hình học quan trọng nhất của mạng lưới đường bộ, với hầu hết các tuyến đường giao thông trùng khớp với bản đồ số hiện có.

3.2. Ứng dụng thuật toán ước lượng mật độ hạt nhân để tăng độ chính xác bản đồ

Để khắc phục dữ liệu GPS có mật độ thấp và nhiễu, Xuemei Liu và cộng sự (2012) [2] đã đề xuất sử dụng thuật toán ước lượng mật độ hạt nhân (KDE). Thuật toán này giúp khôi phục dấu vết dữ liệu GPS có mật độ thấp, từ đó cập nhật và suy luận ra bản đồ đường bộ với độ chính xác cao. KDE hoạt động bằng cách đếm số đoạn đi qua mỗi điểm, sau đó tìm ra các đoạn đường đồng mức dựa trên ngưỡng mật độ nhất định (ví dụ, ngưỡng trên 80 được coi là đường giao thông). Tiếp theo, sơ đồ Voronoi được sử dụng để trích xuất đường trung tâm, loại bỏ các đường viền bên ngoài và các đoạn có ngưỡng thấp. Phương pháp này đảm bảo tính chính xác, loại bỏ các đường viền và đường ảo, tạo ra đường trung tâm phù hợp, đồng thời xử lý nhanh chóng các bộ dữ liệu GPS lớn.

IV. Quy trình đề xuất Xử lý dữ liệu GPS Tracks và tạo bản đồ chi tiết theo luận văn

Luận văn của Đặng Văn Huy (2014) đề xuất một quy trình toàn diện để xây dựng bản đồ giao thông từ GPS Tracks, không chỉ tập trung vào việc tạo ra mạng lưới đường bộ mà còn bổ sung các thuộc tính quan trọng như tên đường. Quy trình này bao gồm các bước từ thu thập dữ liệu GPS bằng smartphone, xử lý dữ liệu GPS bằng thuật toán xấp xỉ chuỗi dữ liệu GPS, đến tổng hợp dữ liệu và tích hợp các module phát hiện giao cắt, cũng như cài đặt thuật toán tìm đường đi ngắn nhất. Mục tiêu là tạo ra một bản đồ số hoàn chỉnh, có độ chính xác cao và cung cấp thông tin chi tiết, hỗ trợ người dùng trong việc định vị và tối ưu hóa lộ trình di chuyển, từ đó giảm thiểu tắc nghẽn giao thông và cải thiện luồng giao thông.

4.1. Thu thập dữ liệu GPS qua ứng dụng trên smartphone và tiền xử lý ban đầu

Bước đầu tiên trong quy trình đề xuất là thu thập dữ liệu GPS một cách hiệu quả. Luận văn đã xây dựng một ứng dụng chạy trên hệ điều hành Android, sử dụng công nghệ định vị GPS (có hỗ trợ A-GPS qua mạng 3G) để xác định tọa độ (kinh độ, vĩ độ) tại từng điểm trên đường đi. Ứng dụng này ghi lại một chuỗi các tọa độ theo thời gian, tạo thành nhật ký GPS (GPS Logs) của một tuyến đường giao thông. Việc sử dụng smartphone giúp quá trình thu thập dữ liệu trở nên tiện lợi và có thể triển khai rộng rãi. Sau khi thu thập, các dữ liệu GPS này sẽ trải qua giai đoạn tiền xử lý. Mặc dù A-GPS giúp giảm sai số, dữ liệu vẫn cần được kiểm tra và chuẩn hóa để loại bỏ những điểm bất thường, chuẩn bị cho các bước xử lý dữ liệu GPS tiếp theo, đảm bảo chất lượng đầu vào cho việc xây dựng bản đồ.

4.2. Thuật toán xấp xỉ chuỗi dữ liệu GPS để tối ưu kích thước bản đồ

Sau khi thu thập, kích thước của chuỗi dữ liệu GPS có thể rất lớn, ảnh hưởng đến hiệu suất của các thuật toán xây dựng bản đồ và thuật toán tìm đường đi ngắn nhất. Để giải quyết vấn đề này, luận văn đề xuất thuật toán xấp xỉ chuỗi dữ liệu GPS nhằm rút gọn kích thước dữ liệu mà vẫn giữ lại những điểm đặc trưng nhất của tuyến đường giao thông. Thuật toán hoạt động dựa trên nguyên lý loại bỏ các điểm có khoảng cách nhỏ hơn một ngưỡng 'esp' nhất định tới đoạn thẳng nối hai điểm đặc trưng liền kề. Ví dụ, nếu một tuyến phố gần như thẳng, chỉ cần giữ lại điểm đầu và điểm cuối. Quá trình này được lặp lại đệ quy cho đến khi chuỗi dữ liệu được tối ưu hóa. Việc áp dụng thuật toán này giúp giảm đáng kể lượng dữ liệu cần xử lý, cải thiện thời gian chạy của các thuật toán tiếp theo, và đồng thời duy trì độ chính xác hình học cần thiết cho bản đồ định tuyến.

4.3. Module tính điểm giao cắt và cài đặt thuật toán tìm đường đi ngắn nhất

Sau khi dữ liệu GPS được xấp xỉ và tổng hợp thành các đoạn đường, bước tiếp theo trong quy trình là xác định các nút giao thông. Luận văn đã xây dựng một module tính điểm giao cắt giữa các đường trên bản đồ, dựa trên tính chất hình học của đường thẳng. Module này nhận đầu vào là tập hợp các đoạn thẳng đã được xử lý và trả về các điểm giao nhau giữa chúng. Việc xác định chính xác các nút giao là cực kỳ quan trọng để xây dựng một mạng lưới đường bộ hoàn chỉnh, có khả năng định tuyến. Sau khi mạng lưới đường được xây dựng, thuật toán tìm đường đi ngắn nhất Dijkstra nổi tiếng được cài đặt để đánh giá độ chính xác của bản đồ xây dựng được so với các bản đồ số hiện có như Google Maps. Việc này không chỉ kiểm chứng chất lượng bản đồ mà còn cho thấy tiềm năng ứng dụng thực tế trong việc hỗ trợ người tham gia giao thông tìm kiếm lộ trình tối ưu, quản lý mật độ giao thông, và giảm thiểu tắc nghẽn giao thông.

V. Đánh giá và so sánh kết quả Bản đồ giao thông từ GPS Tracks hoạt động thế nào

Kết quả thực nghiệm là yếu tố then chốt để đánh giá hiệu quả của phương pháp xây dựng bản đồ giao thông từ GPS Tracks. Luận văn đã áp dụng quy trình đề xuất để xây dựng một phần bản đồ giao thông khu vực Hoàn Kiếm, Hà Nội, và tiến hành so sánh với các bản đồ số phổ biến như OpenStreetMap và Google Maps. Việc này không chỉ giúp kiểm định độ chính xác của bản đồ xây dựng được mà còn cung cấp cái nhìn định lượng về khả năng cạnh tranh và tiềm năng ứng dụng của nó. Kết quả đã chứng minh rằng các thuật toán xây dựng bản đồ được đề xuất có thể tạo ra một bản đồ định tuyến có độ chính xác cao, góp phần vào việc trực quan hóa dữ liệu bản đồ và hỗ trợ các ứng dụng giao thông thông minh.

5.1. Kiểm định độ chính xác của bản đồ xây dựng qua thuật toán tìm đường đi ngắn nhất

Để đánh giá độ chính xác của bản đồ giao thông từ GPS Tracks được xây dựng, luận văn đã sử dụng thuật toán tìm đường đi ngắn nhất Dijkstra và so sánh kết quả với Google Maps, một trong những phần mềm bản đồ tốt nhất hiện nay. Nghiên cứu đã chọn ngẫu nhiên 30 cặp điểm nguồn-đích trong khu vực Hoàn Kiếm, Hà Nội, và so sánh khoảng cách đường đi ngắn nhất trên bản đồ xây dựng được với kết quả từ Google Maps. Kết quả cho thấy, khoảng 63% các cặp điểm trên bản đồ xây dựng được cho kết quả tìm đường đi ngắn nhất nhỏ hơn hoặc bằng với Google Maps. Mặc dù có khoảng 37% chênh lệch do sai số hoặc tín hiệu GPS thấp, nhưng nhìn chung, kết quả này khẳng định khả năng của phương pháp trong việc tạo ra một bản đồ định tuyến đủ chính xác cho các ứng dụng thực tế, hỗ trợ việc quản lý luồng giao thông và giảm tắc nghẽn giao thông.

5.2. Tiềm năng phát triển bản đồ giao thông từ GPS Tracks trong tương lai

Kết quả đạt được từ việc xây dựng bản đồ giao thông từ GPS Tracks đã mở ra nhiều hướng phát triển tiềm năng. Bản đồ xây dựng được không chỉ cung cấp thông tin vị trí và tìm đường đi ngắn nhất mà còn cho phép người dùng tự cập nhật các con đường mới một cách dễ dàng. Trong tương lai, việc bổ sung các thuộc tính chi tiết hơn như tên đường, hướng đường, đường một chiều, hoặc các điểm địa lý quan trọng (nhà cửa, trường học, bệnh viện) sẽ làm tăng giá trị của bản đồ số. Hơn nữa, việc tích hợp sâu hơn với các hệ thống thông tin địa lý (GIS), phát triển các vùng trên bản đồ (sông, hồ, ranh giới hành chính), và bổ sung chức năng định vị cũng như tìm kiếm theo tên đường sẽ biến bản đồ giao thông này thành một công cụ mạnh mẽ cho các dự án Smart City, logistics, và quản lý vận tải công cộng, góp phần vào việc trực quan hóa dữ liệu bản đồ toàn diện.

VI. Kết luận và Hướng phát triển của Xây dựng bản đồ giao thông từ GPS Tracks

Tổng kết lại, nghiên cứu về xây dựng bản đồ giao thông từ GPS Tracks đã trình bày một quy trình toàn diện và hiệu quả để chuyển đổi dữ liệu GPS thu thập được từ thiết bị di động thành một bản đồ số có độ chính xác cao. Thông qua việc đề xuất và triển khai thuật toán xấp xỉ chuỗi dữ liệu GPS, cùng với việc tích hợp các module phát hiện giao cắt và cài đặt thuật toán tìm đường đi ngắn nhất, luận văn đã chứng minh tính khả thi và tiềm năng ứng dụng của phương pháp này. Kết quả thực nghiệm đã khẳng định khả năng tạo ra một bản đồ định tuyến đáng tin cậy, có thể hỗ trợ người dùng trong việc tối ưu hóa lộ trình và giảm thiểu tắc nghẽn giao thông. Các nghiên cứu tiếp theo sẽ tập trung vào việc mở rộng tính năng và nâng cao độ chính xác của bản đồ, nhằm đáp ứng các yêu cầu ngày càng cao của một hệ thống thông tin địa lý (GIS) hiện đại.

6.1. Tóm tắt quy trình và đóng góp chính của phương pháp xây dựng bản đồ

Quy trình xây dựng bản đồ giao thông được đề xuất bao gồm các bước cốt lõi: phát triển ứng dụng thu thập dữ liệu GPS trên điện thoại Android; đề xuất và triển khai thuật toán xấp xỉ chuỗi dữ liệu GPS để tối ưu hóa kích thước dữ liệu; tổng hợp dữ liệu GPS đã xử lý để tạo thành một bản đồ giao thông hoàn chỉnh; và xây dựng module phát hiện các nút giao nhau. Đóng góp chính của phương pháp này là cung cấp một quy trình linh hoạt và chi phí thấp để tạo ra và cập nhật bản đồ số dựa trên nhật ký GPS thực tế, đặc biệt phù hợp cho các khu vực có bản đồ số chưa được cập nhật thường xuyên. Việc tích hợp thuật toán tìm đường đi ngắn nhất cũng giúp minh chứng độ chính xác của bản đồ xây dựng, cung cấp một công cụ hữu ích cho người tham gia giao thông.

6.2. Triển vọng mở rộng ứng dụng bản đồ giao thông và tích hợp GIS

Hướng phát triển tiếp theo của nghiên cứu này rất rộng mở, hướng tới việc biến bản đồ giao thông từ GPS Tracks thành một hệ thống thông tin địa lý (GIS) toàn diện hơn. Kế hoạch bao gồm việc bổ sung mô tả cụ thể về các điểm nổi bật (nhà, trường học, bệnh viện), xây dựng các vùng địa lý (sông, hồ, ranh giới), và đặc biệt là tích hợp thêm chức năng định vị cũng như khả năng tìm đường theo tên đường. Những cải tiến này sẽ làm tăng đáng kể giá trị và tiện ích của bản đồ số, mở rộng ứng dụng bản đồ giao thông trong nhiều lĩnh vực như quy hoạch đô thị, quản lý tài nguyên, logistics, và phát triển các giải pháp Smart City. Việc liên tục cập nhật và nâng cấp dữ liệu GPS cũng như các thuật toán xây dựng bản đồ sẽ đảm bảo rằng bản đồ giao thông này luôn phản ánh chính xác thực trạng cơ sở hạ tầng, hỗ trợ hiệu quả cho người dùng và các nhà quản lý.

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

Đặt Vấn đề Ngày nay bản đồ số đóng vai trò quan trọng trong giao thông vận tải. Nó dần thay thế bản đồ trên giấy bởi các tính năng ưu việt như lưu chữ gọn nhẹ, truy vấn thông tin về đường đi, khoảng cách và vị trí một cách rễ dàng nhanh chóng thông qua GPS. Từ đó các phương pháp xây dựng bản đồ giao thông sử dụng GPS được nhiều nhóm tác giả đưa ra. Hướng tới xây dựng một bản đồ có dữ liệu và những tính toán chính xác giúp con người tham gia giao thông một cách hiệu quả nhất.

Sơ lƣợc về hệ thống định vị toàn cầu GPS Hệ thống GPS (Global Positioning System) được đưa vào sử dụng từ những năm 1960 bởi bộ quốc phòng Mỹ cho mục đích quân sự. Ngày nay, hệ thống này đã được mở rộng cho phép dùng vào các mục đích dân sự. Hệ thống GPS có thể chia làm ba phân đoạn: - Phân đoạn không gian: gồm 24 vệ tinh ( hiện tại sử dụng 21 vệ tinh và 3 vệ tinh dự phòng ) bay quanh quỹ đạo trái đất ở độ cao khoảng 20200km chu kỳ bay khoảng 12 giờ như hình dưới. 5 Luận Văn Thạc Sĩ HV: Đặng Văn Huy Hình 1: Ảnh 24 vệ tinh bay quanh quỹ đạo của trái đất - Phân đoạn điều khiển: bao gồm các thiết bị ở mặt đất cho phép giám sát và điều khiển các vệ tinh.

Hiện tại có 5 trạm điều khiển ở mặt đất. Trạm giám sát và điều khiển chính tọa lạc tại Colorado Springs (Mỹ). Bốn trạm khác phân bố tại Hawaii, Ascencio, Diego Garcia và Kwajalein trên khu vực xích đạo. Các trạm này có nhiệm vụ giám sát hoạt động của các vệ tinh và gửi tín hiệu điều khiển để hiệu chỉnh quỹ đạo các vệ tinh.

- Phân đoạn ngƣời dùng: bao gồm toàn bộ các thiết bị cho phép thu tín hiệu GPS để định vị tọa độ. Các thông tin có thể thu được từ thiết bị thu GPS phổ biến là: - Mã C/A (C/A code): đây là mã thô, độ chính xác thấp. - Mã P (P-code): đây là mã có độ chính xác cao. 6 Luận Văn Thạc Sĩ HV: Đặng Văn Huy Các mã C/A được trộn với thông báo hàng hải và truyền trong sóng mang L1.

Mã P được trộn với các thông báo hàng hải và truyền qua sóng mang L2. Các máy thu GPS có hai loại: - Một tần số (single frequency): chỉ thu được sóng L1. - Hai tần số (Dual frequency): thu được cả sóng L1 và L2. Độ chính xác của các thiết bị thu vào khoảng 1/100 bước sóng của mã.

Như vậy thiết bị một tần số (mã C/A) có độ chính xác sai lệch khoảng 3m và của thiết bị hai tần số (mã P) vào khoảng 0,3m. Tuy nhiên, độ chính xác của thiết bị thu còn phụ thuộc vào thời tiết và địa hình (núi, nhà cao tầng,…). Hệ thống GPS cung cấp tọa độ không gian ba chiều: vĩ độ, kinh độ và cao độ. - Cơ chế hoạt động: Vị trí của 1 điểm trên mặt đất, sẽ là tham chiếu so với vị trí của các vệ tinh và trung tâm tín hiệu trung gian mặt đất.

Vị trí của một điểm sẽ được tính toán dựa trên khoảng cách từ điểm đó đến các vệ tinh, và đến các trung tâm mặt đất. Khoảng cách này được đo bằng phương pháp rất đơn giản, đó là Quãng đường bằng Vận Tốc nhân với Thời Gian (s = v×t). Ở đây, vận tốc là vận tốc truyền tín hiệu (sóng), thời gian đo bằng đồng hồ nguyên tử có độ chính xác rất cao. Vì thế, khi nhận được tín hiệu từ vệ tinh, thiết bị sẽ tự tính toán ra khoảng cách giữa thiết bị và vệ tinh thông qua phương pháp trên.

Theo lý thuyết, chỉ cần có 3 vệ tinh là có thể tính toán được vị trí (tính ra tọa độ x,y,z trong không gian), tuy nhiên do có sai số nhất định nên hệ thống cần thêm 1 tham chiếu nữa, tức là thêm 1 vệ tinh nữa là 4 vệ tinh để có thể tính toán được chính xác. Nếu có nhiều hơn 4 vệ tinh thì nó cũng sẽ nhận và xử lý hết tín hiệu. Có thêm nhiều vệ tinh thì có thể bắt chính xác hơn. 7 Luận Văn Thạc Sĩ HV: Đặng Văn Huy Hình 2: Xác định vị trí một điểm trên mặt đất Cuối cùng, GPS tính toán vị trí rất chính xác nhưng vẫn luôn luôn có sai số.

Sai số này có thể là vài mét, hoặc vài trăm mét. Sai số hiển thị trên màn hình thiết bị chỉ là sai số có thể có, dựa trên phân tích tín hiệu thu nhận được. Bởi các vệ tinh, trái đất, và cả chúng ta đều di chuyển liên tục đồng thời trong thời gian thực. - Công nghệ Assisted-GPS (A-GPS).

Assisted-GPS: công nghệ hỗ trợ cho hệ thống GPS qua việc sử dụng các trạm trung gian trên mặt đất. Các trạm trung gian này chính là các cột phát sóng của nhà mạng trong khu vực. Và hệ thống A-GPS có 1 máy chủ để tính toán các tín hiệu và thông số mà nó nhận được. Thiết bị sử dụng A-GPS sẽ phải kết nối với máy chủ để nhận tín hiệu này (qua kết nối internet 3G, GPRS, wifi).

Như hình vẽ chúng ta có thể thấy A- GPS nhận tín hiệu từ 3 vệ tinh và 1 trạm mặt đất. Nhờ đó mà tín hiệu sẽ nhanh chóng và ổn định hơn. Vì trạm mặt đất ở gần hơn. Sóng khỏe hơn và trạm này cố định.

Nhờ 8 Luận Văn Thạc Sĩ HV: Đặng Văn Huy đó A-GPS hoạt động nhanh hơn và ổn định hơn. A-GPS không hoàn toàn thay thế GPS, nó chỉ có tác dụng hỗ trợ. Nếu ko có sóng di động, ko có liên lạc với máy chủ hay trạm BTS, thì thiết bị vẫn có thể định vị nhờ GPS như bình thường. Hình 3: Trạm trung gian hỗ trợ hệ thống GPS Trong luận văn này tôi có sử dụng công nghệ A-GPS hỗ chợ xác định tọa độ trong quá trình thu thập dữ liệu.

Công nghệ A-GPS sẽ giúp tính toán tọa độ nhanh và chính xác hơn vì vậy sai số sẽ nhỏ hơn. Các hƣớng tiếp cận xây dựng bản đồ giao thông sử dụng GPS tracks 1. Ứng dụng phân cụm Năm 2009 Cao, Lili, và John Krumm đề xuất hướng tiếp cận phân cụm để xây dựng bản đồ giao thông [1]. Nhóm tác giả trình bày về phương pháp chuyển đổi dấu vết GPS thô thu được vào một mạng lưới đường bộ định tuyến.

Bằng cách làm mịn, dõ con 9 Luận Văn Thạc Sĩ HV: Đặng Văn Huy đường được tạo bởi các dữ liệu GPS thô ban đầu. Nhóm tác giả đã sử dụng thuật toán phân cụm để tạo ra một đồ thị gồm các nút và các cạnh mô tả cho hướng đi trên mỗi con đường, tạo ra mạng lưới đường bộ định tuyến. Xuất phát từ những thách thức phải làm dõ những đường được tạo ra, do dữ liệu GPS thu được từ các xe bị lỗi hoặc do nhiễu tín hiệu GPS làm ảnh hưởng đến độ chính xác của những con đường đó. Do vậy nhóm tác giả đã đề xuất cách tiếp cận theo 2 bước.

Bước 1: làm rõ các con đường được tạo bởi dấu vết GPS lỗi bằng cách nhóm những dấu vết GPS và các điểm thuộc cùng một con đường lại với nhau. Bước 2: Căn cứ vào kết quả Bước 1, nhóm tác giả sử dụng thuật toán sinh ra một biểu đồ chỉ dẫn mô tả kết nối hình học của mạng lưới đường bộ. Qua kết quả thực nghiệm tạo ra đồ thị giữ được kết nối quan trọng và đặc tính hình học quan trọng nhất của mạng lưới đường bộ trong khu vực thử nghiệm. So sánh kết quả thu được với bản đồ Microsoft Bing hầu hết các tuyến đường là trùng khớp trong các trường hợp.

Nhưng có một số tuyến đường tạo ra không trùng khớp với bản đồ Microsoft Bing do hai nguyên nhân. - Con đường đó mới được xây dựng xong nhưng trong bản đồ Microsoft Bing chưa cập nhật hoặc những con đường đã bị phá bỏ để xây dựng, nhưng vẫn tồn tại trong bản đồ Microsoft Bing - Do dữ liệu thu được trên các đoạn đường cao tốc bị hạn chế tạo ra các phân đoạn không đáng tin cậy nên bị loại bỏ do vậy không có trong đồ thị. Nhóm tác giả đã đưa gia một phương pháp mới tạo ra bản đồ đường định tuyến từ dấu vết GPS thu thập được trên các xe tham gia giao thông. Đây là một phương pháp thay thế cho quá trình tốn kém về tiền bạc công sức, để tạo ra một bản đồ sử dụng các thiết bị GPS trên xe chuyên dụng.

10 Luận Văn Thạc Sĩ HV: Đặng Văn Huy 1. Thuật toán ƣớc lƣợng mật độ hạt nhân Năm 2012 Xuemei Liu , James Biagioni, Yin Wang và Yanmin Zhu đề xuất sử dụng thuật toán ước lượng mật độ hạt nhân để xây dựng ra bản đồ suy luận có độ chính xác cao[2]. Liu và các cộng sự của mình đã sử dụng thuật toán ước lượng mật độ hạt nhân (KDE) để sử lý, khôi phục lại dấu vết dữ liệu GPS có mật độ thấp từ đó cập nhật và suy luận ra bản đồ đường bộ có độ chính xác cao. Bài toán cần giải quyết của Liu là sử dụng thuật toán KDE để khắc phục dữ liệu GPS có mật độ thấp và nhiễu.

Thuật toán KDE được mô tả qua các bước: B1: bắt đầu bằng cách đếm xem có bao nhiêu đoạn đi qua mỗi điểm. B2: sau đó tìm ra những đoạn đường đồng mức dựa trên ngưỡng mật độ của các điểm nhất định (ngưỡng trên 80 được coi là đường giao thông). B3: dựa vào sơ đồ Voronoi trích xuất đường trung tâm B4: loại bỏ những đường viền bên ngoài của đường trung tâm và những đoạn có ngưỡng thấp. B5: so sánh và cập nhật với bản đồ thật mặt đất Bằng thử nghiệm thực tế kết quả thử nghiệm thuật toán với dữ liệu có mật độ thấp thu thập được tại chicago và dữ liệu taxi tại thượng hải đã tìm ra ngưỡng khoảng cách phù hợp giữa đường viền là 20m.

Thuật toán KDE đảm bảo tính chính xác cao loại bỏ được những đường viền và những đoạn đường ảo,tạo ra đường trung tâm phù hợp, loại bỏ được nhiễu từ dữ liệu GPS. Qua thử nghiệm bằng thực tế nhóm tác giả thấy thuật toán KDE thời gian xử lý nhanh và phù hợp trong xử lý bộ dữ liệu lớn. Thuật toán xử lý đƣờng cong tại các nút giao nhau Năm 2010 Chen, Daniel và cộng sự đã đưa ra những đề xuất giải pháp tái tạo lại mạng lưới đường bộ từ một tập hợp các dấu vết GPS của những con đường đảm bảo độ chính 11 Luận Văn Thạc Sĩ HV: Đặng Văn Huy xác trong xây dựng bản đồ theo các giả định hợp lý [3].