Xây dựng tim đường từ dữ liệu vùng trong ARCGIS

Create centerlines from polygon features

            Trong quá trình số hóa, cập nhật dữ liệu, đôi khi chúng ta cần giải quyết bài toán rất cơ bản là xây dựng tim đường (centerline) cho dữ liệu dạng vùng (polygon) có cấu trúc mạng lưới (network) như hệ thống giao thông, sông suối, hệ thống cấp - thoát nước,... Công đoạn này có rất nhiều ứng dụng trong thực tế. Như bài toán tìm đường đi ngắn nhất với dữ liệu đầu vào chỉ có lớp giao thông dạng vùng. Công việc đầu tiên là phải tạo lớp tim đường, sau đó mới có thể xây dựng cấu trúc node - edge để build network cho bài toán tìm đường.

            Ngoài ra, đối với dữ liệu dạng vùng, vấn đề gán nhãn – labeling là bài toán khó trong việc hiển thị nhãn theo ngữ cảnh và theo dáng điệu của polygon, đặc biệt là đối với các polygon phức tạp. Vấn đề này có thể được giải quyết bằng cách gán nhãn dựa trên centerline/ media axis của đối tượng polygon.

Hình 1: Labeling dựa trên centerline

            Bài toán tìm centerline cho polygon, có thể phân thành 02 nhóm phương pháp - phương pháp vector và phương pháp raster. Phương pháp vector dựa trên sơ đồ Voronoi. Phương pháp raster chuyển dữ liệu vùng (dạng vector) về dạng raster rồi thực hiện các thuật toán thinning để xây dựng tim đường cho đối tượng.

1.  Phương pháp vector dựa trên sơ đồ Voronoi

            Một số khái niệm về sơ đồ Voronoi (còn được gọi là đa giác Thiessen) và khả năng ứng dụng trong bài toán tìm centerline cho polygon.

            Về cơ bản, sơ đồ Voronoi cho một tập hợp điểm được định nghĩa như sau:

            -   Cho P = {p₁,p₂,p₃,…,p_n} là tập n điểm trong không gian Euclidean.

            -   d(pi,pj): Khoảng cách Euclidean giữa p_i và p_j.

            -   Ô Voronoi của pi – kí hiệu V(p_i) được định nghĩa:

            V(p_i) = { q : d(p_i, q) < d(p_j, q), với ∀ j ≠ i }

            -   Sơ đồ Voronoi của tập điểm P, kí hiệu V(P) là hợp các ô Voronoi của tất cả các điểm thuộc P.

            Nói cách khác, sơ đồ Voronoi là một phân hoạch của P thành n vùng, mỗi vùng ứng với một và chỉ một điểm p_i thuộc P sao cho nếu  điểm q thuộc vùng ứng với p_i thì khoảng cách từ q đến p_i là nhỏ nhất so với các điểm khác thuộc P.

Hình 2: Sơ đồ Voronoi

            Dễ thấy các cạnh của sơ đồ Voronoi chính là đường trung trực của các cặp điểm kề nhau. Dựa vào tính chất này, nếu chúng ta xây dựng sơ đồ Voronoi cho các điểm biên của polygon thì có thể lọc được centerline của nó từ các cạnh của sơ đồ Voronoi. Đây cũng chính là ý tưởng cơ bản của phương pháp vector xây dựng centerline từ polygon dựa trên sơ đồ Voronoi.

Hình 3: Sơ đồ Voronoi các điểm biên của Polygon

2  Phương pháp raster

            Phương pháp raster chuyển dữ liệu vùng (dạng vector) về dạng raster rồi thực hiện các thuật toán thinning để xây dựng tim đường cho đối tượng.

 ÁP DỤNG

            Một số công cụ hỗ trợ xây dựng centerline ở mức người dùng cuối (trong phần mềm thương mại ArcGIS):

            -   Số hóa thủ công với sự trợ giúp của công cụ Midpoint. Nhược điểm là chậm và nhàm chán. Ưu điểm là người dùng có thể tinh chỉnh ngay trong giai đoạn số hóa tùy theo ngữ cảnh thực tế và tận dụng được kinh nghiệm của biên tập viên dữ liệu.

Hình 4: Số hóa centerline thủ công với công cụ Midpoint

            -   Collapse Dual Lines To Centerline: Đây là chức năng được tích hợp sẵn trong Cartography Tools/ Generalization.

·         Chuyển lớp dữ liệu dạng polygon sang dạng line bằng công cụ  Polygon to Line

·         Dùng công cụ EditFeatures để những đường kết thúc của lớp line vừa chuyển

·         Lưu thay đổi và kết thúc công việc edit, and stop the edit session

·         Tạo centerlines bằng công cụ  the Collapse Dual Lines To Centerline tool.

Hình 5: Số hóa centerline với công cụ Collapse Dual Lines To Centerline

Tuy nhiên công cụ này có hiệu quả thấp, chỉ phù hợp với mạng giao thông (polygon tương đối thẳng và không qua phức tạp), và rất khó sử dụng vì phải nhập thông số Maximum width thích hợp mới cho kết quả chấp nhận được.

 Hiện thực phương pháp vector dựa trên sơ đồ Voronoi

            Ý tưởng thuật toán trên được áp dụng trong ArcGIS bằng cách sử dụng các công cụ sẵn có theo các bước sau:

            -   Đầu tiên chuyển các vertices của polygon thành lớp điểm riêng bằng công cụ Feature Vertices to Points trong Data Management Tools/ Features. Để nâng cao chất lượng khi tạo centerline, có thể tăng mật độ các vertice của polygon (sử dụng chức năng Editing Tools/ Densify). Lưu ý nếu tạo mật độ điểm càng dày, độ chính xác càng cao nhưng thời gian tính toán càng tăng.

Hình 6: Tăng mật độ điểm biên bằng Densify

            -   Tiếp theo, tạo Thiessen trong Analysis Tools/ Proximity/ Create Thiessen polygon.

Hình 7: Tạo Thiessen polygon cho lớp điểm

            -   Sau đó chuyển Thiessen Polygon vừa tạo thành lớp line, dùng Select By Location để lọc những đường nằm trong polygon. Đến đây centerline đã dần lộ diện.

Hình 8: Lọc centerline từ các cạnh Voronoi

            -   Để tinh chỉnh kết quả thành centerline như mong muốn, có thể xóa thủ công các nhánh không cần thiết hoặc tiếp tục sử dụng các kĩ thuật lọc khác. Công đoạn cuối cùng là merge tất cả các line lại thành một centerline duy nhất.

            Chúng ta có thể sử dụng ModuleBuilder trong ArcGIS để thiết kế và chạy tự động các bước trên, hoặc có thể sử dụng công cụ Polygon to Centerline được publish trên Arcgis Resource Center dưới dạng một toolbox. Công cụ có 02 chức năng là tạo centerline và hiệu chỉnh centerline, áp dụng phương pháp vector dựa trên sơ đồ Voronoi như đã phân tích trong phần 1

Hình 9: Toolbox Polygon to Centerline

Hiện thực phương pháp raster

            Cách tiếp cận thứ hai là chuyển dữ liệu sang raster. Cách tiếp cận này được sử dụng nhiều trong lĩnh vực xử lý ảnh và thị giác máy tính.

            Trong ArcGIS, chúng ta có thể hiện thực bằng các bước sau:

            -   Chuyển polygon sang raster : Conversion Tools      / To Raster/ Polygon to Raster

·         Input Features: Lớp vùng cần chuyển

·         Value field : Trường giá trị

·         Output Raster Dataset: Lớp kết quả

·         Cell assigment type :Phương pháp gán

·         Priority field : Trường ưu tiên

·         Cellsize : kích thước pixel

Hình 10: Công cụ Polygon to Raster

            -   Dùng công cụ Thin (Spatial Analysis Tools/Generalization/Thin) để tạo centerline dạng Raster:

·         Input Raster: Lớp vùng dạng Raster

·         Output Raster: Lớp kết quả

·         Background value:giá trị nền

·         Shape for corners: hình dạng góc

·         Maxximum thickness: Độ dày tim đường

            -  Sau đó  chuyển lớp tim đường raster sang lớp tim đường dạng vector (Conversion Tools/ Form Raster/ Raster to Polyline):

·         Input raster:Lớp tim đường dạng raster

·         Field: Trường thuộc tính

·         Output Poline Features: Lớp kết quả

·         Background value: Giá trị nền

·         Minimum dangle length:Chiều dài tối thiểu được giữ lại

Hình 11: Kết quả tạo tim đường dạng raster

            - Lớp dữ liệu tim đường vừa được tạo chưa có giá trị thuộc tính ta có thể dùng công cụ Spatial Join (Arctoolbox/Analysis Tools/Overlay/Spatial Join)để lấy thuộc tính của lớp dự liệu giao thông ban đầu:

·         Target Feature: lớp tim đường

·         Join Feature: Lớp vùng

·         Output Feature Class: Lớp kết quả

·         Join Operation:Mối quan hệ thuộc tính

·         Field Map of Join Features: Các trường của lớp vùng

·         Match Option: Mối quan hệ không gian

Hoàng Đức Thông

Tổng hợp