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

Quách Đồng Thắng 

Trung tâm Ứng dụng GIS TP.HCM

TÓM TẮT

            Bài báo trình bày phương pháp xây dựng tim đường cho dữ liệu dạng vùng theo các cách tiếp cận khác nhau, phục vụ làm dữ liệu đầu vào cho các bài toán phân tích mạng và vấn đề gán nhãn cho đối tương dạng vùng phức tạp trong các ứng dụng GIS.

Từ khóa: tim đường, tìm xương, sơ đồ Voronoi, phân tích mạng, gán nhãn.

 1.  GIỚI THIỆU

            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ế. Ví dụ, xét 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.

            Nói  rộng ra, bài toán tìm centerline thuộc lớp bài toán tìm media axis/ skeleton cho đối tượng hình học, được ứng dụng rất nhiều trong thực tế như shape matching, animation, motion planning,... Vấn đề đặt ra là có thể tự động hóa công đoạn này hay không và cách tiếp cận giải quyết bài toán này như thế nào, đặc biệt trong các phần mềm, ứng dụng GIS. Đó cũng là mục tiêu nghiên cứu của bài báo.

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

            Trở lại bài toán tìm centerline cho polygon, có thể phân thành 02 nhóm phương pháp - tạm gọi là phương pháp vector và phương pháp raster. Phương pháp vector giới thiệu trong bài báo 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.1.  Phương pháp vector dựa trên sơ đồ Voronoi

            Trước tiên, bài báo trình bày 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 vectorxâ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

1.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.

 2.  Á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. Để sử dụng chức năng này phải chuyển lớp polygon sang line. 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.

            -   Sử dụng chức năng Create Centerlines của công cụ ET GeoWizards. Tuy nhiên đây là extension có bản quyền.

Hình 5: Chức năng Create Centerline trong ET GeoWizards

            Trên đây là các công cụ hỗ trợ người dùng cuối tạo centerline cho polygon trong phần mềm ArcGIS. Có thể thấy, hai phương pháp đầu là thủ công, phương pháp thứ ba sử dụng extension thương mại nên cũng khó tiếp cận nghiên cứu phương pháp, thuật toán thực sự được cài đặt bên dưới là gì.

            Trên cơ sở phân tích các phương pháp ở phần 1, bài báo sẽ tập trung hiện thực hóa ý tưởng, phương pháp xây dựng centerline cho polygon trong phần mềm ArcGIS, cũng như cho các phần mềm GIS khác.

2.1.  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. Bài báo thực hiện densify polygon với khoảng cách giữa các vertices là 1m.

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 của bài báo.

Hình 9: Toolbox Polygon to Centerline

            Ngoài ArcGIS, cách tiếp cận này cũng đã được sử dụng để tìm centerline cho đối tượng dạng vùng trên CSDL PostGIS bằng cách sử dụng các hàm xử lý dữ liệu không gian của PostGIS và hàm Voronoi của R thông qua ngôn ngữ PL/R. Cách tiếp cận này cũng được cài dặt trên thư viện geoscript chạy trên nền Jython.

            Bài báo trình bày cách xây dựng sơ đồ  Voronoi, làm cơ sở để tìm tim đường cho đối tượng dạng vùng trong PostGIS. Một số công cụ/ phần mềm được sử dụng:

            -   R: phần mềm mã nguồn mở hỗ trợ phân tích thống kê và hiển thị đồ họa mạnh mẽ.

            -   PL/R: một phần mở rộng của PostgreSQL cho phép viết các hàm PostgreSQL bằng ngôn ngữ R.

            -   Deldir package (Delaunay Triangulation and Dirichlet (Voronoi) Tessellation) của tác giả Rolf Turnerhỗ trợ xây dựng Voronoi diagram/ Delaunay Triangulation từ một tập điểm.

            Giải pháp đưa ra là sử dụng function được viết bằng PL/R trong PostgreSQL/PostGIS sử dụng gói deldir trong R để xây dựng sơ đồ Voronoi cho tập điểm là các vertices của polygon, kết hợp dùng các hàm xử lý dữ liệu không gian trong PostGIS để trích lọc tim đường cho polygon. Cụ thể:

            -   Sử dụng hàm ST_Boundary để trích xuất biên của polygon ở dạng line.  

            -   Sử dụng hàm ST_Line_Interpolate_Point để tạo tập điểm từ polygon boundary với mật độ tuỳ ý.

Hình 10: Tạo Voronoi Diagram trong PostGIS bằng hàm PL/R

2.2.  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:

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

            -   Dùng công cụ Thin trong Spatial Analysis Tools/Generalization để tạo centerline, sau đó  dùng công cụ Raster to Polyline để có được lớp tim đường dạng vector.

Hình 12: Kết quả tạo tim đường giao thông

3.  KẾT LUẬN

            Bài báo đã giới thiệu cách tiếp cận xây dựng centerline cho polygon và hiện thực hóa trong phần mềm ArcGIS cũng như giới thiệu một số cài đặt trên các môi trường khác như PostGIS hoặc geoscript. Việc lựa chọn công cụ nào tùy thuộc vào nhu cầu sử dụng thực tế của người dùng. Các cách tiếp cận được đề cập trong bài báo mang tính giới thiệu để các nhà nghiên cứu có quan tâm tiếp tục nâng cao chất lượng tạo tim đường cho đối tượng dạng vùng hoặc đề xuất các hướng tiếp cận khác để giải quyết vấn đề này.

TÀI LIỆU THAM KHẢO

1.    Boissonnat, J.-D. (January 2010). Convex Hulls, Voronoi Diagrams and Delaunay Triangulations. ENS-Lyon.
2.    Francis Chin, Jack Snoeyinky, Cao An Wangz. Finding the Medial Axis of a Simple Polygon.
3.    Franz Aurenhamme, Rolf Klein. Voronoi Diagrams.
4.    Goswami, P. P. Introduction to Computational Geometry.
5.    Inkulu, R. Voronoi diagrams: Higher order.
6.    Kreveld, M. v. Computational Geometry: its objectives and relation to GIS.
7.    LLeo Hsu and Regina Obe. (n.d.). bostongis. Retrieved from PL/R and PostGIS:

       http://www.bostongis.com/?content_name=postgresql_plr_tut02#98

8.    Mark de Berge, Otfried Cheong, Marc vn Kreveld, Mark Overmars. (2008). Computational Geometry -  

       Algorithms and applications. Springer.           
9.    Nandy, S. C. Voronoi Diagram.
10.   Nehab, D. Medial Axis.
11.   Edwards, R. (2010). Determining the Skeleton of a Simple Polygon in (Almost) Linear Time. Oak Ridge,

        Tennessee. 
12.   Joachim Giesen, B. M. The Scale Axis Transform.
13.   M.Ilg, R. O. (1992). Voronoi Skeletons: Theory and Applications. CVPR'92, (pp. 63-69). Illinois.
14.   Michael McAllister, J. S. media axis generalisation of hydrology. Vancouver, BC, Canada, V6T 1Z4:      

        Department of Computer Science, University of British Columbia.

15.   A Geospatial World. (n.d.). Retrieved 08 2013, from Voronoi diagram of the polygon skeletonization:    

        http://ageoguy.blogspot.com/search?q=voronoi 

16.   ArcGIS Resource Center. (n.d.). Retrieved 07 2013, from Polygon to Centerline:

        http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=EF0C96FF-1422-2418-7F9F-               B0A8839FC796       

17.    ArcGIS tools add-ons and extensions from ET SpatialTechnique. (n.d.). Retrieved 08 2013, from

        http://www.ian-ko.com/                  
18.   Smathermather's Weblog. (n.d.). Retrieved 6 2013, from What is the center line of a complex polygon?:

        http://smathermather.wordpress.com/2011/09/16/what-is-the-center-line-of-a-polygon-or-how-to