Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography Vol. 33, No. 1, 45-52, 2015
http://dx.doi.org/10.7848/ksgpc.2015.33.1.45
계층적 매칭 기법을 이용한 수치지도 건물 폴리곤 데이터의 자동 정합에 관한 연구
Automatic Matching of Building Polygon Dataset from Digital Maps Using Hierarchical Matching Algorithm
염준호1) · 김용일2) · 이재빈3) Yeom, Junho · Kim, Yongil · Lee, Jeabin
Abstract
The interoperability of multi-source data has become more important due to various digital maps, produced from public institutions and enterprises. In this study, the automatic matching algorithm of multi-source building data using hierarchical matching was proposed. At first, we divide digital maps into blocks and perform the primary geometric registration of buildings with the ICP algorithm. Then, corresponding building pairs were determined by evaluating the similarity of overlap area, and the matching threshold value of similarity was automatically derived by the Otsu binary thresholding. After the first matching, we extracted error matching candidates buildings which are similar with threshold value to conduct the secondary ICP matching and to make a matching decision using turning angle function analysis. For the evaluation, the proposed method was applied to representative public digital maps, road name address map and digital topographic map 2.0. As a result, the F measures of matching and non-matching buildings increased by 2% and 17%, respectively. Therefore, the proposed method is efficient for the matching of building polygons from multi-source digital maps.
Keywords : Hierarchical Matching, ICP Algorithm, Turning Angle Function, Automatic Building Matching, Road Name Address Map, Digital Topographic Map 2.0
초 록
공간정보 제작의 다원화로 인하여 다양한 수치지도들이 여러 공공기관 및 기업에서 제작됨에 따라 데이터의 상 호 운용성이 점점 중요해지고 있다. 이에 본 연구에서는 계층적 매칭 기법을 활용한 이종 수치지도의 건물 데이터
자동 정합기법을 제안하였다. 먼저 수치지도를 가구계 기반으로 분할한 후 ICP 알고리즘을 활용한 건물 기하보정
을 1차적으로 수행하였다. 대응 가능한 건물쌍의 중첩면적 유사도를 평가하여 대응 건물을 결정하고 Otsu 이진 임
계화를 수행하여 매칭·비매칭에 대한 임계값을 자동으로 설정하였다. 1차 매칭이 완료된 후 임계값과 비슷한 유사 도를 가지는 건물들을 오매칭 후보군으로 추출하여 개별 건물에 대한 ICP 알고리즘 기반의 기하보정을 다시 수행
하고 형태학적 인자인 회전각 함수분석을 추가 적용하여 정합여부를 재판단하였다. 실험평가를 위해 제안된 알고
리즘을 대표적인 공공분야 수치지도인 도로명주소지도와 수치지형도 2.0의 건물 데이터에 적용하고 활용성을 평 가하였다. 정확도 평가결과 매칭 건물 및 비매칭 건물에 대한 F 측정치가 각각 2%와 17% 향상되었으며 이를 통해
본 연구에서 제안한 알고리즘이 이종 수치지도 건물 정합에 효과적으로 적용될 수 있음을 확인하였다.
핵심어 : 계층적 매칭, ICP 알고리즘, 회전각 함수, 자동 건물 매칭, 도로명주소지도, 수치지형도 2.0
45 ISSN 1598-4850(Print) ISSN 2288-260X(Online) Original article
Received 2015. 01. 26, Revised 2015. 02. 26, Accepted 2015. 02. 28
1) Member, Department of Civil and Environmental Engineering, Seoul National University (E-mail: [email protected]) 2) Member, Department of Civil and Environmental Engineering, Seoul National University (E-mail: [email protected])
3) Corresponding Author, Member, Department of Civil Engineering, Institute of New & Renewable Energy Technology Research, Mokpo National University (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. 33, No. 1, 45-52, 2015
46
1. 서 론
측량기술의 발전과 공간정보의 다원화로 인하여 수치지도 들이 여러 공공기관 및 기업들에 의해 제작되어 공급되고 있 다. 통신 기업의 차량 항법(navigation) 지도, 검색 포털 기업 의 위치 기반 서비스 지도, 공공기관의 행정 지도 등 다양한 수치지도들이 각각의 목적과 사용자에 따라 운용되고 있다.
이 중 공공기관 수치지도 자료는 업무 공조와 예산의 중복 집 행을 줄이기 위하여 데이터의 높은 상호 운용성이 필요하다.
기 구축된 공간정보를 서로 통합하여 필요한 공간정보를 생 성하거나 갱신할 경우 데이터 취득과 관련된 비용 절감 효과 를 거둘 수 있다. 특히 수치지도의 건물 자료는 개체 수, 사용 자의 관심, 갱신 주기 등을 고려할 때 가장 핵심적인 자료라 할 수 있다. 이러한 이유로 이종 수치지도 간의 건물 정합을 위한 다양한 연구들이 진행되었다(Kang et al., 2006; Kim et al., 2008; Kim et al., 2010; Zhang et al., 2012).
이종 건물 폴리곤 자료의 정합에 관한 기존 연구들은 일반 적으로 객체의 중첩 면적을 중요 인자로 활용하여 매칭을 수 행하거나(Huh et al., 2013) 이를 개선하기 위하여 면적이나 형상에 관한 유사도를 계산하고 이에 대한 가중 조합을 통 해 매칭을 수행하였다(Huang et al., 2010; Kim et al., 2013;
Zhongliang and Jianhua, 2008). 기존 연구와 같이 객체의 중 첩 면적만을 유사도 기준으로 이용할 경우 중첩률이 높지만 형태학적으로 상이한 건물이 오매칭 될 가능성이 높다. 이를 보완하기 위하여 건물의 면적과 형상에 대한 가중 조합을 통 해 건물의 매칭 여부를 판단할 경우에는 매칭 후보가 되는 대응 가능한 모든 건물쌍에 대해 유사도 계산 및 조합 유사 도를 계산하여야 하므로 연산 효율성이 떨어지는 문제점이 있다. 또한 일반적으로 기존 연구들은 매칭된 건물에 대한 생산자 정확도(producer’s accuracy)와 사용자 정확도(user’s accuracy) 또는 이들의 조화 평균인 F 측정치(F measure)만 을 이용하여 정확도를 평가하였다(Kim et al., 2012; Zhang et al., 2012). 그러나 이러한 평가 기법은 비매칭 건물의 탐색 을 통한 데이터 갱신 측면에서 설명력이 부족하다는 문제점 이 있다. 따라서 신축이나 철거에 의한 변화 건물과 이종 수치 지도 간의 도화 작업 차이로 인한 건물과 같이 비매칭 건물에 대한 정확도 지표를 반영한 정확도 평가가 필요하다.
이에 본 연구에서는 이종 수치지도 건물 폴리곤에 계층적 매칭을 적용하여 매칭 정확도를 향상시켰다. 가구계(block) 기반 건물 폴리곤에 ICP(Iterative Closest Point) 알고리즘을 적용하여 기하보정을 수행하고 중첩 유사도 분석을 통해 1차 건물 매칭을 수행하였다. Otsu 임계화 기법을 이용하여 자동
으로 매칭 판별에 대한 임계값을 설정하고 임계값과 유사도 가 비슷한 건물들을 오매칭 후보군으로 선별하였다. 이 후 개 별 건물에 대한 ICP 기하보정과 회전각 함수 분석을 적용하 여 2차 매칭을 수행하였다. 제안된 기법의 효용성을 평가하기 위하여 데이터의 상호 운용성이 강조되는 대표적인 공공지도 인 도로명주소지도와 수치지형도 2.0을 이용하여 실험을 진 행하고 결과를 분석하였다. 최종적으로 매칭 건물 뿐만 아니 라 비매칭 건물에 대한 정확도 평가를 함께 수행하여 제안 기 법의 우수성을 확인하였다.
2. 연구방법
본 연구는 크게 전처리, 1차 매칭, 2차 매칭 및 정확도 평 가 세 부분으로 구성된다(Fig. 1). 전처리 과정은 대응 가구계 를 추출하는 과정으로서 도로명주소지도와 수치지형도 2.0 의 도로 레이어와 이를 포함하는 폴리곤을 이용하여 도로로 둘러싸인 가구계를 추출하고 매칭한다. 계층적 건물 폴리곤 매칭은 1차 매칭, 오매칭 후보군 추출, 2차 매칭으로 이루어 지며 1차 매칭에서는 대응 가구계 내에 존재하는 건물 군에 대해 ICP 알고리즘을 활용한 기하보정을 실시한 후 중첩 면 적 분석 및 매칭쌍 탐색을 수행한다. 중첩 면적 비율을 유사 도 기준으로 하여 매칭쌍과 비매칭쌍에 대한 Otsu 이진 분류 를 수행한다. 유사도가 임계값과 비슷한 건물들은 오매칭 확 률이 높으므로 정확도 개선을 위하여 재탐색 후보군으로 설 정하였다. 이 후 후보군에 대하여 가구계 건물 군이 아닌 개 별 건물들에 대해 ICP 알고리즘을 활용한 기하보정을 다시 수행하고 형태학적 인자인 회전각 함수분석을 적용하는 2차 매칭을 실시하였다. 최종적으로 판독을 통해 구축된 매칭 참
Fig. 1. Flow chart of the study
Automatic Matching of Building Polygon Dataset from Digital Maps Using Hierarchical Matching Algorithm
47 조 자료와 비교 분석하여 제안 기법의 정확도를 평가하였다.
2.1 가구계 추출 및 대응 가구계 결정
일반적으로 동일 지역의 소규모 건물군에 대한 매칭을 수 행할 경우 가구계 추출은 불필요하다. 그러나 광역 범위의 건 물군에 대한 매칭을 수행할 때 기하보정 기법에 의해 계산된 회전 및 이동량을 전체 데이터에 일괄적으로 적용할 경우 지 역적인 위치 오차가 크게 발생하게 된다. 따라서 본 연구에서 는 가구계를 우선적으로 추출하고 기하보정의 기본 단위로 사용하였다. 가구계란 도로로 둘러싸인 영역으로서 도시 계 획에 의해 구획된 블록을 의미하며 일반적으로 한 가구계에 는 수개에서 수십 개의 건물이 존재한다. 수치지형도와 도로 명주소지도 전체를 포함하는 폴리곤(O)을 생성하였을 때 도 로 폴리곤(
∩
∪
∩
×
AB BC FA
′
′ ′
)과의 차 연산을 통해 개별 가구계를 추출 할 수 있다(Eq. (1)). 또한 이종 데이터간에 대응 가능한 가구계쌍 의 중첩 면적비를 계산함으로써 면적유사도(Sa)가 가장 높은 대응쌍을 결정할 수 있다(Eq. (2)). 두 지도는 기준 타원체와 좌표계가 다르기 때문에 투영 변환 후에도 계통(systematic) 위치 오차가 존재하나 오차가 작고 중첩 면적비가 그에 비해 매우 크므로 별도의 기하학적 보정 방법 없이 투영 변환만을 적용하여 대응 가구계 탐색을 수행하였다.
∩
∪
∩
×
AB BC FA
′
′ ′
(1)
∩
∪
∩
×
AB BC FA
′
′ ′
(2)
where B : Block polygon set, O : Outer polygon,
∩
∪
∩
×
AB BC FA
′
′ ′
: Road polygon set, Sa : Area similarity, Br, Bd: block polygon of road name address map and digital topographic map.
2.2 계층적 건물 폴리곤 매칭
2.2.1 1차 건물 폴리곤 매칭 및 오매칭 후보군 추출 추출된 가구계 대응쌍 내에 존재하는 건물군에 대해 ICP 알고리즘을 적용하여 기하학적 위치 오차를 보정하였다. 본 연구에서는 최신성이 높은 도로명주소지도를 수치지형도에 맞추어 보정함으로써 신규 건물의 갱신이 가능하도록 하였 다. 가구계 기반으로 ICP 알고리즘을 적용할 경우 가구계별 로 고유한 회전 행렬(
∩
∪
∩
×
AB BC FA
′
′ ′
)과 이동 벡터(T)가 계산되기 때문에 지역적인 왜곡을 최소화 할 수 있으며 연산 부하를 줄일 수 있다.
ICP 알고리즘은 점으로 구성된 두 벡터 데이터의 기하학적 차이가 최소가 되도록 변환량을 반복적으로 추정하는 알고
리즘이다(Besl and Mckay, 1992; Chen and Medioni, 1992).
도로명주소지도를 수치지형도에 맞추어 등록(registration) 할 경우, 첫 번째 단계에서는 도로명주소지도 내 각각의 포인 트에 대하여 수치지형도 내 가장 가까운 인접 포인트를 탐색 한다. 이 후 Eq. (3)과 같이 두 데이터의 대응 포인트들에 대한 평균제곱근오차 비용함수(C)를 최소화 시키는 회전 행렬과 이동 벡터를 추정한다. 대응점을 탐색하고 회전 및 이동 요 소를 추정하는 전체 과정이 정해진 반복 횟수 또는 비용함수 가 수렴할 때까지 반복된다. 일반적으로 ICP 알고리즘을 적 용할 경우 빠른 속도로 비용함수가 수렴하며, 본 연구에서는 10번의 반복 횟수를 적용하였다.
∩
∪
∩
×
AB BC FA
′
′ ′
(3)
where C : Cost function, n : Number of point data,
∩
∪
∩
×
AB BC FA
′
′ ′
: Rotation matrix,
∩
∪
∩
×
AB BC FA
′
′
′
: Translation vector,
∩
∪
∩
×
AB BC FA
′
′ ′
,
∩
∪
∩
×
AB BC FA
′
′ ′
: Coordinate vector of i-th point in road name address map and digital topographic map.
가구계별로 계산된 회전 및 이동 변환량을 도로명주소지 도 건물에 적용한 후 수치지형도 건물과 중첩 면적 비율을 계 산하였다. 중첩 면적 비율은 Eq. (2)에서 설명한 것과 같이 두 폴리곤 데이터의 합집합 면적에 대한 교집합 면적으로서 유 사도 판별을 위한 가장 대표적인 기준이다. 대응 가능한 건물 쌍에 대하여 중첩 면적 비율을 계산하고 가장 유사도가 높 은 쌍을 매칭 건물로 결정하였다. 유사도는 0에서 1사이의 값 을 가지며 0은 중첩 되는 건물이 없는 것을 의미하고 1은 두 건물이 완벽히 중첩되는 것을 의미한다. 건물의 유사도가 높 을수록 동일 건물일 확률이 높으며 매칭 여부를 판별하기 위 해서는 0에서 1사이의 임계값 설정이 필요하다. 이종 건물 폴 리곤의 경우 매칭 건물은 두 데이터의 속성 융합에 활용되며 비매칭 건물은 신규 건물 갱신, 부정확한 도화 건물 수정에 활용이 가능하다. 매칭 건물과 비매칭 건물을 자동으로 분류 하기 위해 Otsu 임계화 기법을 이용하였다. Otsu 임계화 기법 은 클래스간 분산(
∩
∪
∩
×
AB BC FA
′
′ ′
)과 클래스내 분산(
∩
∪
∩
×
AB BC FA
′
′ ′
)을 이용하여 클 래스들의 분리도가 최대가 되도록 임계값을 탐색하는 알고 리즘이다(Otsu, 1975). Eq. (4)와 같이 전체 분산을 클래스간 분산과 클래스내 분산의 합으로 표현할 때, 클래스내 분산은 가중치가 고려된 매칭 건물과 비매칭 건물 분산의 합으로 표 현된다(Eq. (5)). 임계값에 따라 매칭 건물과 비매칭 건물의 분산이 달라지며 클래스 내의 분산이 최소, 클래스 간의 분
