Wednesday, June 27, 2012

Sử dụng PAL trong các phần mềm GIS mã nguồn mở

Quách Đồng Thắng  - Trung tâm Ứng dụng GIS TP.HCM

Tóm tắt
Gán nhãn tự động (Automatic Label Placement) là một trong những vấn đề khá quan trọng trong các ứng dụng GIS. Đối với các phần mềm thương mại, việc gán nhãn được giải quyết khá tốt (chưa kể việc sử dụng các công cụ hỗ trợ mạnh mẽ như Maplex cho ArcGIS, SmartLabel/EverName cho MapInfo). Trong khi đó, chức năng gán nhãn trong các phần mềm GIS mã nguồn mở còn nhiều hạn chế như bị trùng lắp, dễ gây nhầm lẫn, gây khó khăn cho người sử dụng. PAL (Automatic Label Placement) là một thư viện mã nguồn mở được phát triển bởi University of Applied Sciences, Western Switzerland (HES-SO). PAL được thiết kế cho việc gán nhãn động, đa lớp với thời gian chấp nhận được và chất lượng gán nhãn cao. Bài viết trình bày khả năng áp dụng gói thư viện PAL để nâng cao hiệu quả và chất lượng gán nhãn trong các phần mềm GIS mã nguồn mở thông dụng là gvSIG, Quantum GIS và MapWindow.
Từ khoá: gán nhãn tự động, PAL, JPAL,POPMUSIC, phần mềm GIS mã nguồn mở.

Abstract
Automatic Label Placement is an important problem in GIS applications. For commercial GIS software, this problem has been solved fairly well (Maplex for ArcGIS, SmartLabel/EverName for MapInfo). Meanwhile, Automatic Label Placement in open source GIS softwares is still a considerable problem. PAL is an open source library package developed by University of Applied Sciences, Western Switzerland (HES-SO). PAL is designed for dynamic, multi-layers labeling with acceptable execution time and high quality. This paper presents the ability of  using PAL to enhance the effect and quality of automatic labeling placement in some popular open source GIS softwares such as gvSIG, QuantumGIS and MapWindow.

Key words: Automatic Label Placement, PAL, JPAL POPMUSIC, open source GIS

1. GIỚI THIỆU
Gán nhãn là một trong những vấn đề khá quan trọng trong ngành bản đồ học. Trước khi có bản đồ số, các quy tắc gán nhãn trên bản đồ nói chung đã được nhiều nhà nghiên cứu đề xuất nhằm đảm bảo tính dễ đọc, dễ nhận biết, ít gây nhầm lẫn và tính thẩm mỹ trong công tác thành lập và xuất bản bản đồ. Đối với bản đồ số, việc gán nhãn là một quá trình động và phức tạp vì nó phụ thuộc vào nhiều yếu tố như khung nhìn bản đồ, số lớp/ số đối tượng cần hiển thị nhãn, độ lớn trường dữ liệu mà nhãn thể hiện,…
Eduard Imhof (1895-1986), nhà bản đồ học nổi tiếng người Thuỵ Sĩ, trong quyển “Positioning Names on Maps” (1962/1975) đã nêu ra một số quy tắc căn bản trong việc gán nhãn cho bản đồ:
-         Dễ đọc: các nhãn phải được đặt sao cho dễ đọc, dễ nhận biết và dễ phân biệt.
-         Không nhập nhằng: dễ dàng nhận biết chính xác đối tượng mà nhãn thể hiện.
-         Tránh chồng lắp: so với các nhãn khác và với các đối tượng đồ hoạ khác.
Ông đã nêu ra một số khuyến cáo khi gán nhãn cho các đối tượng dạng điểm, đường và vùng trong bản đồ:
Đối tượng dạng điểm
-         Vị trí nhãn ở về phía trên bên phải thì ưa nhìn hơn so với phía dưới và bên trái.
-         Vị trí nhãn càng gần điểm mà nó thể hiện càng tốt.
-         Nhãn được bố trí nằm ngang.


Đối tượng dạng đường
-         Nhãn càng gần đường mà nó thể hiện càng tốt.
-         Nhãn phải bố trí theo hình dạng của đường.
-         Nhãn càng có ít vị trí cong càng tốt.
-         Đối với các đường dài, nhãn phải được lặp lại.
-         Đối với các đường thẳng đứng: Nếu nhãn nằm về phía bên trái thì đọc từ dưới lên, ngược lại bên phải thì đọc từ trên xuống


Đối tượng dạng vùng
-         Nhãn nên nằm bên trong và trải ra đủ lớn trên diện tích của vùng.
-         Các đối tượng vùng nhỏ, các quy tắc gán nhãn tương tự quy tắc gán nhãn cho điểm.
Eduard Imhof đã liệt kê ra các trường hợp tốt/ xấu khi gán nhãn một cách trực quan cho các đối tượng điểm, đường và vùng. Các quy tắc gán nhãn của ông mặc dù thiên về kỹ thuật xuất bản cho bản đồ giấy nhưng đồng thời là một tham khảo rất có giá trị trong việc gán nhãn tự động cho bản đồ số. Bằng chứng là các quy tắc căn bản và các khuyến cáo của ông vẫn được tuân thủ khá tốt trong các công cụ gán nhãn tự động và được xem như các quy tắc tham khảo cho việc đánh giá chất lượng và tính thẩm mỹ của gán nhãn tự động trên bản đồ số.
2. GÓI THƯ VIỆN PAL
2.1 Giới thiệu chung
Đối với việc xây dựng một công cụ gán nhãn cho bản đồ số, có 3 vấn đề cần quan tâm:
-         Tuân thủ các quy tắc căn bản trong việc gán nhãn bản đồ nói chung, đồng thời đáp ứng khả năng gán nhãn động trong bản đồ số.
-         Nghiên cứu lựa chọn giải thuật gán nhãn sao cho thời gian thực thi ở mức chấp nhận được.
-         Khả năng tuỳ biến của người dùng: trong việc lựa chọn vị trí hiển thị, xác định độ ưu tiên của lớp dữ liệu,…
PAL được phát triển bởi University of Applied Sciences, Western Switzerland (HES-SO), với sự hợp tác của 3 nhóm MIS-TIC, IICT-SYSIN và G2C:
-         MIS-TIC: giải thuật tối ưu.
-         IICT-SYSIN:  hiện thực giải thuật thành gói thư viện PAL.
-         G2C: chịu trách nhiệm về các quy tắc gán nhãn (dễ nhìn, không gây nhầm lẫn, tính thẩm mỹ,...).

2.2 Đặc điểm và chức năng
PAL được thiết kế cho gán nhãn đa lớp đồng thời, hỗ trợ các lớp dữ liệu như điểm, đường và vùng. Các yếu tố ảnh hưởng đến việc gán nhãn có thể tuỳ biến trong PAL:
-         Giới hạn tỉ lệ hiển thị nhãn.
-         Độ ưu tiên của lớp dữ liệu gán nhãn.
-         Đối tượng được hiển thị nhãn có được xem là chướng ngại vật khi tính toán vị trí hiển thị nhãn hay không?
-         Lớp dữ liệu có đang được hiển thị hay không?
-         Lớp dữ liệu có được hiển thị nhãn hay không?
-         Phương hướng hiển thị ưa thích (tự do, nằm ngang, nằm trên đường, ...).

2.3 Cách hoạt động của PAL
Quá trình gán nhãn gồm 2 giai đoạn chính: Xác định vị trí ứng viên và tối ưu hoá.
2.3.1 Xác định ứng viên
Xác định vị trí ứng viên trả về một tập các vị trí ứng viên cho mỗi đối tượng cần gán nhãn và một đồ thị thể hiện sự xung đột vị trí (conflict graph) giữa các ứng viên.


Xác định vị trí ứng viên gồm 2 bước chính: tạo ứng viên và lọc ứng viên. Tạo ứng viên tính toán danh sánh các đối tượng cần gán nhãn, danh sách các chướng ngại vật, tỉ lệ và độ lớn khung nhìn bản đồ và tính toán tương ứng với từng đối tượng gán nhãn là một số các vị trí ứng viên được tạo ra kèm với nó là một trọng số. Giai đoạn lọc ứng viên sẽ lọc ra một số các vị trí có trọng số thấp và ít trùng lắp với các đối tượng khác.
Đối với các đối tượng điểm: Có p vị trí ứng viên được tạo ra (p là tham số có thể = 4, hoặc 8, hoặc nhiều hơn tuỳ vào mô hình ứng viên). Vị trí tốt nhất là phía trên bên phải, vị trí tệ nhất là phía trái-bên dưới.  
Đối tượng đường:
-         Chọn các điểm a và b trên đường, ứng với mỗi đoạnxác định được độ dài của nhãn.
-         P_line: ứng viên được đặt ngay trên 
-         P_line_around: đặt 2 ứng viên cách một khoảng distlabel so với 
-         Tính toán tỉ lệ   xác định chất lượng ứng viên.
Đối tượng vùng: 4 cách chọn vị trí ứng viên
-         P_POINT: Gán nhãn theo tâm của vùng.
-         P_LINE: Gán nhãn theo vành đai của vùng.
-         P_FREE:  đặt nhãn nằm trong vùng, cho phép quay nhãn
-         P_HORIZ: đặt nhãn nằm trong vùng, theo phương nằm ngang
Đầu tiên sẽ kiếm tra tính lồi của vùng. Đối với các đối tượng vùng lõm, vùng sẽ được chia thành các đa giác lồi, sau đó xác định các vị trí ứng viên cho các hình chữ nhật bao nhỏ nhất của từng đa giác lồi này. 


2.3.2 Tối ưu hoá
Quá trình tối ưu hoá nhằm xác định vị trí cần hiển thị trong số các ứng viên (trên cơ sở tính toán chất lượng vị trí, độ ưu tiên của lớp dữ liệu, đồ thị xung đột vị trí,…) dựa trên các giải thuật sau: 
-         Giải thuật FALP (Fast Point-Feature Label Placement Algorithm).
-         POPMUSIC (Partial Optimization Metaheuristic Under Special Intensification Conditions):
thuật toán meta-heuristic tối ưa hoá từng phần.
-         4 phương pháp tìm kiếm:
  • Pt: POPMUSIC + Tabu Search.
  • Ptc: POPMUSIC + Tabu Search + Chain Transformation.
  • Pc: POPMUSIC + tìm kiếm đệ quy + Chain Transformation.
  • c:  tìm kiếm đệ quy + Chain Transformation.

3. SỬ DỤNG PAL TRONG MỘT SỐ PHẦN MỀM GIS MÃ NGUỒN MỞ
Đối với các phần mềm GIS mã nguồn mở như Quantum GIS, MapWindow và gvSIG, chức năng gán nhãn tự động còn một số hạn chế như sau:
-         Hiện tượng “đám mây” khi zoom bản đồ ở tỉ lệ nhỏ.
-         Hướng hiển thị của nhãn không được tính toán theo dáng điệu của đối tượng đường.
-         Đối với các đối tượng dạng vùng là đa giác lõm, nhãn có thể nằm ngoài đa giác (do vị trí gán nhãn được chọn là tâm của đa giác), dễ gây nhầm lẫn cho người sử dụng.
-         Khi di chuyển khung nhìn bản đồ dọc theo các đối tượng đường có kích thước dài hoặc các đối tượng vùng có kích thước lớn, các nhãn không được tính toán và vẽ lại vị trí trong khung nhìn hiện tại, gây khó khăn cho việc nhận biết nhãn.
-         Trùng lắp vị trí khi có nhiều lớp dữ liệu được gán nhãn đồng thời trên bản đồ.

3.1 Sử dụng PAL trong Quantum GIS
Gói thư viện PAL được tích hợp vào QuantumGIS (http://www.qgis.org/) từ  phiên bản 1.4, phục vụ cho việc gán nhãn tự động và cả việc thể hiện biểu đồ trên các đối tượng không gian. Hiện tại người dùng có thể sử dụng chức năng gán nhãn chuẩn của Quantum GIS hoặc sử dụng công cụ PAL. Hình sau thể hiện ưu điểm khi sử dụng PAL để gán nhãn trong Quantum GIS

Người dùng có thể tuỳ biến các tuỳ chọn gán nhãn như vị trí hiển thị ưa nhìn, độ ưu tiên của lớp đối tượng, khoảng tỉ lệ hiển thị nhãn, lựa chọn sử dụng phương pháp tìm kiếm,...

3.2 Sử dụng PAL trong MapWindow
Hiện tại chức năng gán nhãn trong MapWindow (http://www.mapwindow.org/) vẫn còn nhiểu hạn chế hạn chế như đã trình bày. Tuy nhiên, PAL đang được nhóm phát triển MapWindow xem xét lựa chọn sử dụng để nâng cao chất lượng gán nhãn trong các phiên bản sau của MapWindow (http://www.mapwindow.org/phorum/read.php?5,12798).

3.3 Sử dụng PAL gvSIG
gvSIG (http://www.gvsig.org/web/) được phát triển trên nền java, trong khi PAL là gói thư viện được viết bằng C++. Đối với các ứng dụng GIS nền java nói chung và gvSIG nói riêng, JNI (Java Native Interface) được dùng để gọi các dll của gói thư viện PAL. Do đó PAL trong các ứng dụng GIS nền java thường được gọi là JPAL (JPAL = JNI + PAL).

PAL được tích hợp trong gvSIG thông qua plugin extJPAL. Phần sau trình bày cách cài đặt, cấu hình extJPAL trong gvSIG

3.3.1 Cài đặt, cấu hình gvSIG chạy trong JRE 1.6.
extJPAL sử dụng một số các đối tượng đồ hoạ được hỗ trợ từ java 1.6. Do đó, để sử dụng extJPAL, gvSIG phải được cấu hình chạy trong môi trường JRE 1.6.
Đối với trường hợp cài dặt mới gvSIG, trình cài đặt mặc định dùng JRE 1.5. Do đó, trước khi cài đặt gvSIG chạy trên JRE 1.6, cần cài đặt theo trình tự như sau:
-           JRE 1.6.x
-           JAI 1.1.x for JRE
-           JAI Image I/O 1.x for JRE
-           gvSIG 1.1.x
Lưu ý:
-         Khi cài đặt gvSIG, chọn “No” checking application requirement, sau đó chọn đường dẫn đến JRE vừa cài đặt.
-         Trình cài đặt gvSIG sẽ copy một số DLL vào thư mục Java, trong đó có msvcr71.dll bị lỗi khi chép đè. Do đó cần đổi tên hoặc xoá msvcr71.dll trước khi cài đặt gvSIG.
Đối với trường hợp nâng cấp gvSIG:  Nếu đã có phiên bản gvSIG chạy trên Java 1.5, chỉnh sửa jre_home  trong file gvSIG.ini  thành:
jre_home = C:\Program Files\Java\jre6
3.3.2 Cài đặt extJPAL trong gvSIG
-         Download  extJPAL-Window, giải nén trong thư mục cài đặt gvSIG, ví dụ: C:\Program Files\gvSIG_1.1_PAL.
-         Chạy file deploy.bat, chọn “D”. Deploy.bat thực hiện các công việc sau:
  • copy jpal.dll vào gvSIG_1.1\lib.
  • copy libgeos-3-0-0.dll vào gvSIG_1.1\lib
  • copy thư mục ch.heigvd.jpal vào  thư mục extensions của gvSIG.
-         Sửa tên gvSIG_1.1_PAL\bin\gvSIG\extensiones\com.iver.cit.gvsig\lib\fmap.jar thành gvSIG_1.1_PAL\bin\gvSIG\extensiones\com.iver.cit.gvsig\lib\fmap.jar.old
-         Copy ch.heigvd.jpal\lib\fmap.jar vào  gvSIG_1.1_PAL \bin\gvSIG\extensiones\com.iver.cit.gvsig\lib\fmap.jar
-         Copy gvSIG.bat trong gvSIG_1.1_PAL\ deployWindow vào  gvSIG_1.1_PAL\bin\
-         Sử dung gvSIG.bat để khởi động gvSIG (thay vì gvSIG.exe)

3. KẾT LUẬN
PAL là gói thư viện mã nguồn mở cho việc nâng cao hiệu quả và chất lượng gán nhãn tự động trong các ứng dụng GIS. Việc sử dụng PAL trong Quantum GIS và extJPAL trong gvSIG cho thấy khả năng tích hợp rất tốt của PAL vào các phần mềm GIS mã nguồn mở. Mặc dù tốc độ thực thi và khả năng tuỳ biến không thể so sánh với Maplex của ArcGIS, song PAL là một lựa chọn rất tốt cho cộng đồng GIS mã nguồn mở.

4. TÀI LIỆU THAM KHẢO
[1]. Olivier Ertz, Maxence Laurent, Daniel Rappo, Abson Sae-Tang1, Eric Taillard, 2008. PAL - A cartographic labelling library, Foos4G2008.
[2]. Eduard Imhof, 1975. Positioning Names on Maps. The American Cartographer, Vol.2, No.2, pp. 128 -144.
[3]. Steven Woudenberg, 2007. Label Placement.