Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography, Vol. 31, No. 6-1, 483-491, 2013 http://dx.doi.org/10.7848/ksgpc.2013.31.6-1.483
이종의 도로망 데이터 셋에서 면 객체 매칭 기반 변화탐지
Automatic Change Detection Based on Areal Feature Matching
in Different Network Data-sets
김지영1) · 허용2) · 유기윤3) · 김정옥4) Kim, Jiyoung · Huh, Yong · Yu, Kiyun · Kim, Jung Ok
Abstract
By a development of car navigation systems and mobile or positioning technology, it increases interest in location based services, especially pedestrian navigation systems. Updating of digital maps is important because digital maps are mass data and required to short updating cycle. In this paper, we proposed change detection for different network data-sets based on areal feature matching. Prior to change detection, we defined type of updating between different network data-sets. Next, we transformed road lines into areal features(block) that are surrounded by them and calculated a shape similarity between blocks in different data-sets. Blocks that a shape similarity is more than 0.6 are selected candidate block pairs. Secondly, we detected changed-block pairs by bipartite graph clustering or properties of a concave polygon according to types of updating, and calculated Fréchet distance between segments within the block or forming it. At this time, road segments of KAIS map that Fréchet distance is more than 50 are extracted as updating road features. As a result of accuracy evaluation, a value of detection rate appears high at 0.965. We could thus identify that a proposed method is able to apply to change detection between different network data-sets.
Keywords : Updating, Road Network, Areal Feature Matching, Bipartite Graph Clustering, Fréchet Distance
초 록
차량용 내비게이션의 빠른 확산과 스마트폰 등 개인 단말기의 측위 기술 발달로 사용자 중심위치기반서비스, 특 히 보행자 내비게이션 서비스에 대한 관심이 증대되고 있다. 보행자 내비게이션 서비스를 위한 핵심정보인 수치지도 는 대용량이고 짧은 갱신주기를 요구하는 경우가 많아 수치지도의 효율적인 갱신이 중요한 이슈가 된다. 본 연구에 서는 구축시기가 상이한 이종의 도로망 데이터 셋에 형상유사도 기반 면 객체 매칭을 적용하여 변화 탐지하는 기법 을 제안하였다. 변화탐지에 앞서 이종의 도로망 데이터 셋의 면 객체 매칭에서 탐지될 수 있는 갱신 유형을 정의하 였다. 면 객체 매칭 기반 변화 탐지를 위하여 이종의 두 도로망 데이터 셋의 선형인 도로객체를 이들로 둘러싸인 면 인 블록으로 변환하였다. 변환된 블록을 중첩하여 중첩된 블록 간의 형상유사도를 계산하고, 이 값이 0.6 이상인 것을 후보 블록 쌍으로 추출하였다. 객체 유형별로 이분 그래프 군집화와 오목다각형 특성을 적용하여 정의된 갱신 유형별 블록 쌍을 탐지하고, 해당 블록 쌍을 구성하거나 내부에 있는 도로 세그먼트 간의 프레셰 거리를 계산하였 다. 이때, 프레셰 거리가 50 이상인 도로명주소기본도 도로구간의 도로객체가 갱신 도로객체로 추출된다. 그 결과 0.965의 높은 탐색율을 보여 제안된 기법이 이종의 도로망 데이터 셋의 선형 객체의 변화탐지에 적용될 수 있음을 확인할 수 있었다.
핵심어 : 갱신, 도로망, 면 객체 매칭, 이분 그래프 군집화, 프레셰 거리
483 1) Member · Dept. of Civil & Environmental Engineering, Seoul National University (E-mail: [email protected])
2) Member · Integrated Research Institute of Construction and Environmental Engineering, Seoul National University (E-mail: [email protected]) 3) Member · Dept. of Civil & Environmental Engineering, Seoul National University (E-mail: [email protected])
4) Corresponding Author · Member · Spatial Information Research Institute (E-mail: [email protected])
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://
creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography, Vol. 31, No. 6-1, 483-491, 2013
1. 서 론
차량용 내비게이션의 빠른 확산과 GPS가 탑재된 스마트폰 등 개인 단말기의 측위 기술발달로 사용자 중심 위치기반서비 스, 특히 보행자 내비게이션 서비스에 대한 관심이 증대되고 있다. 그러나 이들 보행자 내비게이션 서비스는 아직까지 보행 자가 이동할 수 있는 공간인 보행공간이 반영되지 않은 도로 망을 이용하거나 보행자 도로망을 이용하더라도 일부 지역만 을 대상으로 제한적으로 제공되고 있는 실적이다. 도화사와 같은 전문가가 현장조사 등으로 취득된 공간정보에서 디지타 이징하는 일반적인 수치지도(digital map) 구축 방법으로 보 행자 도로망을 구축한다면 정확한 공간정보를 생성할 수 있 으나 넓은 지역을 대상으로 할 경우 시간과 비용이 많이 소요 되는 노동집약적 사업이라는 한계가 있다. 이에 최근에는 그 활용성이 증대되는 보행자 도로망을 국가기본도나 항공사진 등의 기 구축된 공간정보를 이용하여 구축하는 연구가 꾸준 히 진행되고 있다(Elias, 2007; Karimi and Kasemsuppakorn, 2012; Kasemsuppakorn and Karimi, 2013; Kim et al., 2009;
Pun-Cheng et al., 2007). 그러나 보행자 도로망과 같은 수치 지도는 대용량인 경우가 대부분이며, 또한 짧은 갱신주기를 요구하는 경우가 많아 효율적인 갱신이 중요한 이슈가 된다.
대용량의 도로관련 수치지도의 효율적인 갱신을 위하여 최 신의 항공사진이나 위성영상에서 도로망을 추출하여 변화 를 탐지하거나 구축시기가 상이한 이종의 공간정보를 이용하 여 변화를 탐지하고 갱신하는 연구가 꾸준히 진행되고 있다 (Agouris et al., 2001a; Agouris et al., 2001b; Beyen et al., 2012; Eidenbenz et al., 2000; Fortier et al., 2001; Yang et al., 2000; Zhang and Baltsavias, 2002; Zhang and Couloigner, 2005). 특히 벡터 자료구조의 수치지도 간 변화탐지를 위한 연 구에서는 이종의 공간정보간의 매칭 기법을 기반으로 두 지도 간의 모든 객체를 비교하여 변화를 탐지하는 방법이 적용되 고 있다(Badard, 1999; Gabay and Doytsher, 1994; Goesseln and Sester, 2003; Uitermark et al., 1999; Saalfeld, 1988; Sui et al., 2004; Walter and Fritsch, 1999, Xiong and Sperling, 2004; Zhang et al., 2010). 그러나 도로망을 구성하는 세그먼 트, 즉 선형인 도로객체는 고속도로 주변의 복잡한 구조물이 나 차선 방향 표현 방식 등 두 공간정보 간의 세밀도(Level of details, LODs) 차이로 동일한 객체의 묘화나 위상(topology) 이 상이하여 두 도로 세그먼트 간의 유사도를 산출하여 매칭 하는데 어려움이 있다(Zhang et al., 2010).
따라서 본 연구에서는 구축시기가 상이한 도로관련 수치 지도를 갱신하기 위하여 이종의 도로망 데이터 셋에서 변화
를 탐지하는 기술을 제안하고자 한다. 이를 위하여 도형과 위 상정보가 상이한 선형 객체로 이루어진 도로망을 선인 도로 세그먼트로 둘러싸인 블록, 즉 면으로 변형하여 갱신 도로객 체를 탐지하는 기법을 개발한다. 최근에 그 필요성이 높아진 보행자 도로망과 매월 갱신되는 도로명주소기본도의 도로구 간을 대상으로 한다.
2. 이종의 도로망 데이터 셋에서의 갱신
본 연구에서는 Kim et al.(2009)이 제안한 기 구축된 공간 정보에서 보행자 도로망을 생성하는 방법을 적용하여 기 구축 된 공간정보로부터 보행자 도로망을 생성하였다. 이때, 생성된 보행자 도로망은 도로의 폭이 12m 이상이고 횡단보도나 육교 와 같은 도로횡단시설물이 존재하는 도로에서는 도로 양안의 보도에 링크가 생성되고, 그 외의 보행자가 이동할 수 있는 공 간은 그 중심에 링크가 구축된다. 이를 갱신하기 위하여 이용 될 도로명주소기본도는 도로를 기준으로 건물의 주소가 부여 되어 보행자가 이동할 수 있는 도로가 구축 · 관리되고, 매달 갱 신된 데이터가 국가공간정보유통시스템(www.nsic.go.kr)에서 무료로 배포되고 있어 취득이 용이하다는 장점이 있다.
보행자 도로망 링크와 도로명주소기본도 도로구간(TL_
SPRD_MANAGE)의 객체가 선으로 묘화되어 있으며, 이들 선 객체로 둘러싸인 면, 즉 블록을 생성하여 갱신 도로객체를 탐지하게 되므로 이종의 도로망 데이터 셋에서의 갱신을 정의 함에 있어 선 객체에서 변형된 블록을 기준으로 한다.
대상 도로망 데이터 셋에서 생성된 블록 객체를 중첩하면 각 블록별로 중첩되는 블록의 수가 상이하며, 이들 중첩되는 블록 간의 관계를 분석함으로써 변화가 발생한 블록을 탐지할 수 있 다. 따라서 이종의 도로망의 블록 간 매칭 관계를 바탕으로 이 종의 도로망에서 도로신설로 인한 갱신을 Table 1과 같이 정의 할 수 있다. 이때, 현장조사가 진행되지 않고 기 구축된 공간정 보만을 이용하여 도로망을 갱신하기 위해서는 보행자 도로망 과 도로명주소기본도 도로구간의 LODs 차이로 발생한 변화까 지 탐지하는데 한계가 있으므로 구축된 보행자 도로망 링크가 참이라고 가정한다. 보행자 도로망 링크에서 생성된 블록(링크 블록)과 도로명주소기본도 도로구간에서 생성된 블록(도로구 간 블록)을 서로 중첩하였을 때 각 블록간의 매칭 관계가 1:0이 나 M:1인 경우는 갱신이 아니라 LODs차이로 나타난다고 판단 할 수 있다. 다시 말하면 보행자 도로망 링크의 LODs가 도로명 주소 기본도 도로구간보다 높아 링크 블록은 있는데 도로구간 블록이 없거나 또는 링크 블록 여러 개가 하나의 도로구간 블 록과 중첩될 수 있다. 그 외 1:1, 1:N, 그리고 M:N 매칭 관계인
Automatic Change Detection Based on Areal Feature Matching in Different Network Data-sets
485 경우는 도로가 신설됨으로써 발생한 변화로 판단하고, 갱신 대
상으로 정의하였다. 1:1 매칭 관계는 링크 블록(A1, Fig. 1(a))과 매칭되는 도로구간 블록(B1) 내부에 신설 도로가 존재하는 경 우(Fig. 1(b))는 갱신(갱신Ⅰ)으로 정의될 수 있으나 도로가 신 설되지 않은 경우도 있을 수 있으므로 이를 구분할 필요가 있 다. 1:N과 M:N 매칭 관계는 도로구간 블록이 여러 개인 경우로 이는 신설된 도로로 여러 개의 도로구간 블록이 구성되는 경우 (갱신Ⅱ)이다. Fig. 1(c)와 같이 링크 블록(A1, Fig. 1(a))이 신설 도로로 구성된 도로구간 블록 B11과 B12에 매칭된다.
Table 1. Definition of update by cardinality of matching Cardinality of matching
Update Details
Link block in Pedestrian
network
Street block in KAIS
map
1 0 × Different LODs
between two data- sets
1 1 ○ Constructing new roads or not 1 N ○ Constructing new
roads
M 1 × Different LODs
between two data- sets
M N ○ Constructing new roads
따라서 본 연구에서는 도로가 신설되어 변화가 발생한 갱 신을 기존의 도로구간 블록 내부에 도로가 신설되는 경우(갱 신Ⅰ)와 도로가 신설되어 도로구간 블록이 여러 개로 분리된 경우(갱신Ⅱ)로 구분하고, 갱신Ⅰ은 링크 블록과 도로구간 블 록간의 매칭 관계가 1:1인 경우, 갱신Ⅱ는 1:N이나 M:N 매칭 관계로 정의할 수 있다. 정의된 갱신에 해당하는 도로구간 블 록이 판별되면 이후 탐지된 도로구간 블록에서 갱신 유형별로 신설된 도로를 탐지하게 된다.
3. 이종의 도로 데이터 셋에서 면 객체 기반 갱신 도로객체 탐지 기법
본 연구에서는 이종의 도로망 데이터 셋에서 면 객체기반 갱신 도로객체를 탐지하기 위한 연구 흐름은 Fig. 2와 같다. 먼 저 보행자 도로망 링크와 도로명주소기본도의 도로구간을 이 용하여 선 객체로 둘러싸인 면 객체인 블록을 생성하고, 생성 된 블록을 중첩하여 중첩되는 블록 간의 형상유사도를 측정 하여 후보 갱신블록 쌍을 추출한다. 이때, 후보 갱신블록 쌍 을 인접행렬 기반의 이분 그래프 군집화를 통하여 1:1 매칭 관 계인 블록 쌍은 갱신Ⅰ에 해당하는 경우로, 그 외에는 갱신Ⅱ 에 해당하는 경우로 본 연구에서 정의하는 갱신이 발생한 블 록 쌍으로 판별한다. 마지막으로 이들 블록 쌍과 원시 도로망 데이터와의 중첩을 통하여 추출된 도로객체를 대상으로 프 레셰 거리(Fréchet distance)를 산출하여 일정값 이상인 객체 를 갱신 도로객체로 최종 추출한다.
3.1 면 객체 기반 매칭을 통한 후보 갱신블록 쌍 판별 링크 블록과 도로구간 블록을 중첩하여 링크 블록과 중첩 되는 도로구간 블록에 대하여 Kim et al. (2011)이 제안한 형 상유사도를 이용한 면 객체 기반 매칭 알고리즘을 적용하여 형상유사도가 0.6 이상인 후보 갱신블록 쌍을 판별한다. 이 때, 본 연구에서는 동일한 방향성을 보이는 도로 선형으로 둘 러싸인 블록에서 매칭인 객체를 판별하므로 선행연구에서 사 용된 매칭 기준을 본 연구에서 생성된 블록(면) 간의 중첩이
Fig. 2. Work flow of this paper (a) Link block (b) Street block
(UpdateⅠ)
Fig. 1. Examples of update type in this paper (c) Street block
(UpdateⅡ)
