지도일반화를 위한 거주지 선택 기법 (A Settlement Selection Scheme for Map Generalization)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 소프트웨어 및 응용 / 40권 / 12호 / 848 ~ 858페이지
· 저자명 : 응웬녹융, 나현숙

초록

지도일반화는 큰 스케일의 지도에서 작은 스케일의 지도를 추출해내는 모든 과정들을 일컫는다. GIS 응용 프로그램 및 지도 기반 웹서비스에서는 미리 준비된 다중스케일 지도데이터와 이들에 대한 잦은 업데이트를 필요로 하기 때문에 지도일반화가 중요한 문제이다. 여기서 추구되는 가장 바람직한 상황은 시스템이 하나의 지도데이터(모든 세부정보를 가진 큰 스케일의 지도)만을 자주 업데이트하고 다른 스케일의 지도들은 이 지도 및 지도일반화기술을 이용해 필요할 때마다 자동으로 계산하도록 하는 것이다. 본 논문은 지도일반화에서의 거주지 분류 및 선택 문제를 다룬다. 여기서 거주지란 빌딩, 도시, 국가들을 의미한다. 이전의 거주지 분류 및 선택 기법들은 주로 거주지들간의 의미론적 특성(상대적 중요도)과 거리적 특성(상대적 거리)을 유지하는 것에 중점을 두었으며, 거주지 그룹의 모양이나 거주지들간의 또는 이들 그룹과 강, 길, 호수 등 다른 지도객체들과의 위상적 관계를 유지하는 것에 대해서는 거의 관심을 두지 않았다. 최근 Zheng과 Hu는 델로네 삼각분할(Delaunay Triangulation)과 개미알고리즘(ACO, Ant Colony Optimization)을 이용하여 거주지들간의 네 가지 특성 모두를 고려하는 알고리즘을 제시했다. 여기서는 Zheng과 Hu의 ACO-기반 선택 기법 대신, RDP 선분 단순화(Ramer-Douglas-Peucker line simplification) 기법을 응용한 새로운 알고리즘을 제시한다. 개선된 알고리즘이 시간복잡도에 있어서 Zheng과 Hu의 알고리즘보다 더 효율적임을 이론적 측면과 실험적 측면에서 증명하고, 거주지 그룹의 기하적 모양을 유지하는 측면에서도 더 성공적이라는 실험적 증거도 제시한다. 그룹화에 있어서는 Zheng과 Hu의 방법론과 동일하므로, 전체적인 차원에서의 위상적 관계 및 거리적 특성 또한 잘 유지된다.

영어초록

Map generalization refers to all processes of deriving a smaller-scale map from a larger-scale map. It has been a critical issue in GIS applications and map-based webservices since the system needs to handle pre-computed multi-scale data and frequently to update the dataset. Desirable situation here is that the system frequently updates only one detailed (largest-scale) database and maps at the other scales are updated on-demand using that database through automated digital map generalization techniques. In this note, we study settlement classification and selection in map generalization. Settlements represent buildings, cities, or countries. Previous classification and selection schemes mainly focused on keeping the semantic and proximity characteristics of settlements, such as the relative importance and distance of settlements. Little attention has been paid to the shape of settlement groups and to the topological relationship between settlements and between their groups and other map objects, e.g., rivers, roads, lakes, etc. Recently, Zheng and Hu proposed an algorithm taking all these characteristics into account, by using constrained Delaunay triangulation and Ant Colony Optimization (ACO) technique. We improve Zheng and Hu’s algorithm by replacing their ACO-based selection scheme with our modification of Ramer-Douglas-Peucker line simplification algorithm. We prove theoretically and empirically that our algorithm is more efficient in the aspect of time complexity than that of Zheng and Hu. Moreover, we provide empirical evidence indicating that our selection scheme preserves better the geometric shape information of each group of settlements. Our classification scheme is the same as Zheng and Hu’s, thus keeps well the global topology and proximity of settlements.

참고자료

· 없음