항공 라이다 데이터로부터 확장 카이 알고리즘을 이용한 건물경계선 추출
Extracting Building Boundary from Aerial LiDAR Points Data Using Extended χ Algorithm
조홍범1)·이광일2)·최현석3)·조우석4)·조영원5)
Cho, Hong-BeomㆍLee, Kwang-IlㆍChoi, Hyun-SeokㆍCho, Woo-sugㆍCho, Young-won
Abstract
It is essential and fundamental to extract boundary information of target object via massive three- dimensional point data acquired from laser scanner. Especially extracting boundary information of man- made features such as buildings is quite important because building is one of the major components consisting complex contemporary urban area, and has artificially defined shape. In this research, extended χ-algorithm using geometry information of point data was proposed to extract boundary information of building from three-dimensional point data consisting building. The proposed algorithm begins with composing Delaunay triangulation process for given points and removes edges satisfying specific conditions process. Additionally, to make whole boundary extraction process efficient, we used Sweep-hull algorithm for constructing Delaunay triangulation. To verify the performance of the proposed extended χ-algorithm, we compared the proposed algorithm with Encasing Polygon Generating Algorithm and α-Shape Algorithm, which had been researched in the area of feature extraction. Further, the extracted boundary information from the proposed algorithm was analysed against manually digitized building boundary in order to test accuracy of the result of extracting boundary. The experimental results showed that extended χ-algorithm proposed in this research proved to improve the speed of extracting boundary information compared to the existing algorithm with a higher accuracy for detecting boundary information.
Keywords : Chi Algorithm, Alpha Shape, Laser Scanning Data, Extracting Building Boundary Geometry
초 록
항공 라이다로부터 획득한 대용량의 3차원 점 데이터로부터 대상 물체의 윤곽정보를 추출하는 것은 데이터 처
리 과정에서 필수적이며 기반적인 기술 중의 하나이다. 특히 인공 구조물인 건물은 복잡한 현대 도시를 구성하는 주요 구조물이며 그 형태가 명확하기에 윤곽 정보의 추출 과정이 더욱 중요하다 할 수 있다. 본 연구에서는 항공 라
이다를 이용하여 얻어진 건물을 구성하는 3차원 점 데이터로부터 건물의 윤곽정보를 추출하기 위하여 점 데이터의
기하정보만을 이용한 확장 카이(χ-Chi) 알고리즘을 제안한다. 제안된 알고리즘은 임의의 점군을 델로니(Delaunay) 삼각망으로 구성하고 특정 조건을 만족하는 변(edge)를 제거하는 과정을 통하여 구현된다. 덧붙여, 전체적인 추출
과정의 효율화를 위해서 델로니 삼각망의 구성을 스윕헐 알고리즘을 적용하여 수행하였다. 본 연구에서 제안하는
확장 카이 알고리즘의 성능을 확인하기 위하여 본 연구와 같은 목적으로 개발된 인케이싱 폴리곤 제작 알고리즘
과 알파 쉐이프 알고리즘을 비교하였고 기 제작된 건물의 도화정보를 이용하여 윤곽정보 추출의 정확도를 비교하 였다. 실험결과, 본 연구에서 제안한 알고리즘은 기존의 알고리즘들보다 윤곽정보 추출 속도 및 정확도가 향상됨을 확인하였다 .
핵심어 : 카이 알고리즘, 알파 쉐이프, 항공 라이다 데이터, 건물 윤곽정보 추출
1) (주)일도엔지니어링 · 대리(E-mail:[email protected]) 2) 인하대학교 토목공학과 · 대학원생(E-mail:[email protected]) 3) 인하대학교 토목공학과 · 대학원생(E-mail:[email protected]) 4) 교신저자 · 정회원 · 인하대학교 토목공학과 교수(E-mail:[email protected]) 5) (주)일도엔지니어링 · 대표이사(E-mail:[email protected])
111
112
1. 서 론
항공 라이다(LiDAR)로부터 획득되는 데이터는 대량의 3 차원 점(point)의 형태로 표현된다. 이러한 3차원 점 형태의 라 이다 데이터로부터 각 점들이 대표하는 대상 물체를 인식하기 위해서는 대상 물체의 기하 및 정성적 정보를 추출하는 과정 이 필요하다. 특히, 대상 물체를 구성하는 임의의 점군에서 윤 곽6) 기하정보를 추출하는 단계는 위의 과정에서 가장 기본적 이며 필수적인 단계이다. 본 연구에서 언급하는 윤곽이란 점 군의 내·외부 경계7)를 의미하며 외곽8)이란 점군의 외부 경계 정보를 의미한다. 현대 도시를 구성하는 대표적인 지물인 건 물의 경우는 인공적으로 구성되었기 때문에 명확한 윤곽을 보유한다. 이러한 특성은 정밀한 윤곽정보의 필요성을 증가시 키며 특정한 알고리즘으로부터 추출되어진 윤곽정보의 정확 도 분석의 용이함을 제공한다.
본 연구에서 활용하는 라이다 점 데이터로부터 점군의 윤 곽 기하정보를 추출하는 연구는 다양한 방식으로 수행되어 져 왔다. 라이다 점 데이터를 활용한 기존의 연구들은 라이 다 데이터의 특성이 점으로 구성된다는 특성을 반영하여 Zabuawala 등(2009)과 같이 항공영상 등의 이종 센서의 데 이터를 융합하여 건물의 윤곽정보를 추출하였다. 그러나 라 이다 데이터만이 활용 가능한 데이터일 경우에는 적용이 불 가능하다. 조우석 등(2003)은 라이다 점 데이터를 격자 형태 로 정규화하여 외곽 기하정보를 추출하는 방식을 제안하였 다. 라이다 점 데이터를 격자화 하는 방식의 경우에는 라이다 점 데이터가 가지고 있는 기하정보의 손실이 발생하게 된다.
이영진(2003)은 인케이싱 폴리곤(Encasing Polygon)이라 는 개념을 통하여 윤곽 기하정보를 추출하였다. 인케이싱 폴 리곤이란 건물의 윤곽 점으로 구성되는 도형으로 임의의 점 군에서 세 점이 반 시계 방향으로 이루는 각도가 최소인 점을 찾는 과정을 통하여 제작된다. 조홍범(2008)은 기존의 인케이 싱 폴리곤 알고리즘의 한계거리를 탄력적으로 적용하여 알고 리즘의 적용 범위를 확장하였다. 인케이싱 폴리곤 알고리즘은 탐색 범위에 따라 탐색 경로가 내부로 진행되거나 전체 알고 리즘이 교착 상태에 빠지는 경우가 발생한다.
Shen(2008)은 Edelsbrunner 등(1983)이 제안한 알파 쉐이프 알고리즘을 통하여 건물을 구성하는 윤곽 점들을 추출하였 다. 알파 쉐이프 알고리즘은 두 점을 지나는 지름이 알파(α)인
원안에 다른 점이 포함되지 않을 때 두 점은 윤곽 기하정보를 이루는 점으로 규정하는 개념이다. 이후, 추출된 윤곽 점들을 대상으로 개선된 파이프 알고리즘(Improved Pipe Algorithm) 을 적용하여 최종적인 윤곽 기하정보를 정리하였다.
Duckham 등(2008)은 알파 쉐이프 알고리즘에서 발생하는 윤곽 기하정보의 손실을 방지하는 카이(χ) 알고리즘을 제안 하였다. 카이 알고리즘은 점군의 위상관계를 델로니 삼각망으 로 구성하였고 일정 알파 값을 초과하는 변을 제거하는 과정 의 연속으로 윤곽 기하정보의 탐색을 수행하였다. 또한 각 델 로니 삼각형을 이루는 정점의 정규성(Regularity)를 검사하여 기하정보의 보존을 보장하였다.
이정호와 김영일(2012)은 적응적 컨벡스헐 알고리즘을 제 안하여 윤곽 기하정보를 추출하였다. 적응적 컨벡스헐 알고리 즘은 인케이싱 폴리곤 알고리즘과 비슷하게 탐색거리의 제한 을 통하여 점군의 윤곽 기하정보를 탐색한다. 탐색거리는 촬 영 라이다 시스템의 스캔라인 특성을 이용하여 설정하고 탐 색이 실패하는 경우 점진적으로 탐색 거리를 증가시킨다. 적 응적 컨벡스헐 알고리즘의 초기 탐색 점 설정 및 탐색범위 설 정을 위해서는 평균 점 간격의 설정과 촬영 라이다 시스템의 특성이 필요하다.
앞에서 분석한 알고리즘의 한계점을 보완하기 위해서 본 연 구에서는 라이다 점 데이터의 기하학적 특성을 분석 · 비교하 여 건물 윤곽 기하정보의 안정적인 탐지를 보장하는 기존의 Duckham 등(2008)이 제안한 카이 알고리즘의 한계점을 보완 하여 확장 카이 알고리즘을 구현하였다. 카이 알고리즘은 알 파 쉐이프 알고리즘에 발생하는 기하정보 손실을 방지하여 단순 윤곽 기하정보를 추출한다. 본 연구의 확장 카이 알고리 즘은 외곽 기하정보만을 탐지하는 기존의 카이 알고리즘의 한계를 보완하기 위해서 알고리즘의 적용 절차와 범위를 선별 적으로 하였다. 또한 카이 알고리즘에서 활용하는 기준(α) 값 을 결정하는 과정을 점군의 밀도에 유연하고 라이다 데이터 특성을 반영하는 방식으로 수행하였다. 추가적으로, 전체적 인 윤곽 탐지과정의 효율화를 위하여 기존의 방식보다 개선 된 델로니 삼각망 구성을 도입하였다.
2. 윤곽 기하정보의 추출
2.1 델로니 삼각망 구성
본 연구에서 제안하는 확장 카이 알고리즘은 델로니 삼각 망을 기반으로 수행되기 때문에 델로니 삼각망 구성이 선행 되어야 한다. 또한 Naus 등(2008)이 제안한 불연속적으로 존 재하는 라이다 점 데이터의 평균 점 분포간격(Average point
6) 윤곽 : 대상 형체의 외부(Exterior) 및 내부(Interior) 경계의 기하정보
7) 경계 : 대상 형체를 다른 형체와 구별하는 대표 기하정보
8) 외곽 : 대상 형체의 외부(Exterior) 경계의 기하정보
항공 라이다 데이터로부터 확장 카이 알고리즘을 이용한 건물경계선 추출
113
spacing) 특성을 확인하기 위해서도 델로니 삼각망 구성 과정이 필요하다. 델로니 삼각망 구성 과정을 간략하게 정리하면, 모든 점군을 포함하는 최초 삼각형(Super Triangle)을 구성하 고 최초 삼각형 안에서 각 점을 대상으로 세 점을 포함하는 원 안에 다른 점 이 존재하지 않으면 그 삼각형을 델로니 삼각형 으로 추가하는 과정이다. 최초 삼각형은 모든 델로니 삼각망 구성 과정이 수행되면 삭제된다. 이러한 델로니 삼각망 구성 과정은 모든 점을 교차로 비교하기 때문에 최악의 경우 O(n log(n))의 시간 복잡도를 지니게 되며 점의 양이 증가하면 삼 각망 구성 시간이 크게 증가한다.
본 연구에서는 델로니 삼각망 구성의 최적화 및 효율화를 위하여 Sinclair(2010)가 제안한 스윕헐(Sweep-hull) 알고리 즘을 적용하였다. 스윕헐 알고리즘은 최초 점을 설정하고 이 를 바탕으로 거리에 따라 점들을 정렬하고 겹치지 않는 삼각 형들을 구성하는 것을 시작으로 한다. 이후 구성된 삼각형들 의 변을 비교하여 인접관계 및 포함관계 비교를 통하여 위상 관계를 정립하는 플립핑(Flipping) 과정을 거쳐 델로니 삼각 망 구성 과정을 수행한다. 다음 그림 1은 내부에 공백이 존재 하는 O자 형태의 점군과 내부에 공백이 존재하는 L자 형태 의 점군에 스윕헐 알고리즘을 적용한 델로니 삼각화 과정의 결과를 나타낸다.
스윕헐 알고리즘의 구현 과정은 다음과 같다.
스윕헐 알고리즘 (Sinclair, 2010) 1. 전체의 점군
≥
∈
,
∥
or
∥
log
log
에서 최초
≥
∈
,
∥
or
∥
log
log
점를 선택 2. 최초 점과의 거리에 따라 정렬
≥
∈
,
∥
or
∥
log
log
3. 최초 점
≥
∈
,
∥
or
∥
과 최근접한 위치의 점
≥
∈
,
∥
or
∥
log
log
탐색 4. 최초 점
≥
∈
,
∥
or
∥
, 최초 점과 최근접한 위치의 점
≥
∈
,
∥
or
∥
log
, 이들 점 과 함께 삼각형을 구성하여 이 삼각형의 외접원(C)이 최 소 반지름을 보유하게 하는 점
≥
∈
,
∥
or
∥
탐색 5. 오른손 좌표계 방향으로
≥
∈
,
∥
or
∥
정렬 6. 남은 점
≥
∈
,
∥
or
∥
들을
≥
∈
,
∥
or
∥
log
크기 순서대로 정렬
7. 정렬된 남은 점
≥
∈
,
∥
or
∥
log
log
들을 처음 선택된 세 점
≥
∈
,
∥
or
∥
log
log
으 로 구성된 삼각형과 비교하여 연속적으로 삼각형 및 볼 록 다각형을 구성
8. 서로 중복되지 않는 삼각형들이 구성
9. 중복되지 않는 삼각형들 중 인접한 삼각형들의 위상관 계를 비교하여 삼각형의 정점의 순서를 뒤집는 과정을 수행(Flipping)
2.2 확장 카이 알고리즘
2.2.1 기존 카이 알고리즘 (χ-Algorithm)
Duckham 등(2008)이 제안한 카이 알고리즘은 임의의 점 군에서 외곽 정보를 추출하는데 있어서 직관적이고 시스템적 으로 최적화된 접근을 시도하였다. 델로니 삼각망 구성 과정 을 통해 얻어진 삼각망에서 대상 삼각형의 최장변이 일정 기 준 값을 초과하였을 경우 그 변을 제거해 나가는 과정으로 요약할 수 있다. 다음은 카이 알고리즘의 구현 과정은 다음 과 같다.
χ-Algorithm (Duckham 등, 2008) 입력 데이터: 점군(P)
결과 데이터: 도형(Polygon)
1. 주어진 점군(P)에서 델로니 삼각망 구성
2. 외곽 삼각형들 중 다른 삼각형과 인접하지 않는 변(외곽 변) 리스트(B)의 구성
3. 리스트 B를 변의 크기에 따라 내림차순 정렬
4. 리스트 B의 구성 변 e을 순차적으로 탐색하면서 e가 다 음의 기준을 만족하면 리스트 B에서 제거
4.1 구성 변 e의 길이가 기준 값(a)를 초과 4.2 구성 변 e가 포함된 삼각형(T)의 정점(
≥
∈
,
∥
or
∥
log
log
)는 필히 2 개의 외곽 변(boundary edge)을 보유 (Regularity Check)
5. 구성 변 e가 포함되는 외곽 삼각형에서 나머지 두 변을 리스트 B에 추가
6. 리스트 B의 어떤 구성 변 e도 기준 값을 초과하지 않을 때 까지 3~5의 과정을 반복 수행
7. 최종적으로 리스트 B에 존재하는 변을 조합하여 외곽 도형을 구성
2.2.2 제약조건의 설정 및 알고리즘 적용
기존의 카이 알고리즘은 외곽 삼각형으로 판명된 델로니 삼각형을 대상으로 수행하기 때문에 내부의 윤곽정보의 탐 지를 배제하고 있다. 본 연구에서는 기존의 카이 알고리즘을
Figure 1. Delaunay triangulation using
Sweep-Hull Algorithm
114
확장하고 점군의 내·외곽 기하정보(윤곽)를 탐지하기 위하여 알고리즘의 구현방식을 차등하여 적용하였다. 카이 알고리즘 의 정규성 검사 제약조건을 보다 구체화하여, 확장 카이 알고 리즘은 순차적으로 델로니 삼각형의 최장변을 제거해 나가는 과정에서 최장변이 포함된 델로니 삼각형이 이미 2개의 변이 제거 대상이라면 그 삼각형의 나머지 변은 일정 알파 값을 초 과하더라도 제거하지 않는 첫 번째 제약조건을 설정한다. 또 한 추가적으로 두 번째 제약조건으로 대상 최장변이 제거된 후에 형성되는 윤곽선을 이루는 정점(Vertices)들 중에 하나 라도 이미 2개의 윤곽정보를 포함하고 있다면 대상 최장변을 보전하도록 한다. 다음 그림 2와 표 1은 확장 카이 알고리즘의 제약조건을 나타낸다.
델로니 삼각망 구성 과정을 통하여 구성되는 삼각망은 외 부 삼각형 군과 내부 삼각형군의 변의 크기의 차이가 뚜렷하 게 발생하게 된다. 점군이 이루는 내부 및 외부의 윤곽정보를 탐색하기 위해서는 외곽 · 내부 삼각형군 변의 크기 차이를 고 려한 탐색기법의 적용이 필요하다. 본 연구에서는 외곽·내부 삼각형 군에 차등화한 기준 값을 적용하여 확장 카이 알고리 즘을 적용한다. 먼저, 다른 삼각형과 인접하지 않은 변을 보유 한 외곽 삼각형 군을 대상으로 확장 카이 알고리즘을 통한 탐 지를 수행하여 기준 값을 초과하고 위에 제안한 2개의 제약조
건을 만족하는 변을 제거한다. 순차적으로, 제거가 완료된 내 부의 삼각형 군으로 분류되는 삼각망에 기준 값을 초과하고 위에 제안한 제약조건 (2)을 만족하는 변을 제거한다. 내부의 공백은 외곽 기하정보를 보존하지 않아도 공백만으로 완전한 폴리곤의 기하를 이루기에 외곽 기하정보의 보존 제약조건인 제약조건 (1)을 배제한다. 다음의 그림 3은 본 연구에서 확장 카이 알고리즘을 적용하는 단계를 표현하였다.
1. 외부 기하정보 : 델로니 삼각망 구성 과정에서 다른 삼각 형과 접하지 않는 최외곽 삼각형을 대상으로 기준 값을 결정하고 확장 카이 알고리즘(제약조건 1,2 만족)을 적용 하여 순차적으로 윤곽 기하정보를 추가한다.
2. 내부 기하정보 : 외곽 기하정보를 형성한 후 내부의 삼각 형 군을 대상으로 기준 값을 결정하고 이 기준 값을 바탕 으로 내부의 삼각형 중에 윤곽 기하정보로 포함할 수 있 는 공백을 탐색한다. 공백탐사를 할 경우에 확장 카이 알 고리즘(제약조건 2 만족)을 적용한다.
2.2.3 기준 값(α)의 결정
카이 알고리즘과 알파 쉐이프 알고리즘의 가장 중요한 변 수는 기준 값(α)의 결정이다. 위의 두 알고리즘은 기본적으로 기준 값의 비교를 통하여 기준을 만족하는 기하정보를 윤곽 기하정보로 인식하기 때문에 기준 값을 결정하는 과정이 중 요하다.
본 연구에서는 점군의 밀도에 유연한 기준 값 설정을 위하
Table 1. Constraint condition of extended Chi algorithm
제약조건 1
input : Destination Triangle(T) and edges (e) operation :
≥
∈
,
∥
or
∥
log
log
return : false
제약조건 2
input : Vertex(
≥
∈
,
∥
or
∥
log
log
) and triangles containing destination vertex
operation :
≥
∈
,
∥
or
∥
log
log
return : false
Figure 2. Constraint condition of extended Chi algorithm for preserving boundary geometry
Left : Constraint of triangle containing two boundary edges Right : Constraint of vertex meeting boundary edges
Figure 3. Implementation of extended Chi algorithm
항공 라이다 데이터로부터 확장 카이 알고리즘을 이용한 건물경계선 추출
115
여 K 평균 클러스터링(K-means clustering) 알고리즘을 활용한다. 일반적인 K 평균 클러스터링은 N차원 상에 분포된 점군을 초기 설정한 K 개의 점 위치와 비교를 통하여 거리 가 가까운 쪽으로 군집하고 각 군집의 평균 X, Y 좌표를 다 시 비교 점으로 설정하여 최종적인 K 개의 군집화를 수행하 는 알고리즘이다. 본 연구에서는 제거 대상을 판별하는 기 준 값을 획득하기 위하여 K 평균 클러스터링을 활용하기 때 문에 델로니 삼각형의 최장 변을 대상으로 1차원 적으로 군 집화를 수행한다. 그림 4와 같이 델로니 삼각형 선분의 길이 를 y 축으로 하여 큰 변화가 일어나는 부분의 값을 기준 값 으로 결정한다.
본 연구에서는 각 군집을 나누는 세밀한 기준 값의 획득이 중요하다. 세밀한 기준 값을 획득하기 위하여 각 군집을 구 분하는 값들이 최대 차이가 나타나게 되어 더 이상 각 군집 의 평균이 변화하지 않는 시점까지 반복을 수행한다. 반복적 인 군집화를 수행하는 알고리즘의 특성으로 인하여 초기 군 집이 알고리즘의 효율성을 결정하게 된다. 본 연구에서는 라 이다 데이터의 특성을 반영하여 Naus 등(2008)이 제안한 평 균 점 분포간격(Average point spacing)을 기반으로 초기 군 집을 수행한다. 평균 점 분포간격은 비정규적으로 분포하는 라이다 점 데이터의 특성을 반영하여 라이다 점 데이터 기 반의 델로니 삼각망을 구성하고 구성된 델로니 삼각망의 평 균 점 거리를 평균 점 분포간격으로 정의한다. 다음은 본 연 구에서 구현한 K 평균 클러스터링 알고리즘의 구현 과정을 나타낸다.
K 평균 클러스터링의 구현과정
1. 주어진 데이터에서 평균 점 분포간격을 기준으로 상·하로 두 개의 군집을 구성한다.
2. 두 군집의 평균값을 계산하여 초기 값(
≥
∈
,
∥
or
∥
log
log
)으로 선택 한다.
3. 각 관측 값
≥
∈
,
∥
or
∥
log
log
에 대해 초기 값(
≥
∈
,
∥
or
∥
log
log
)까지의 차이 (Difference)를 계산한다.
≥
∈
,
∥
or
∥
log
log
4. 각
≥
∈
,
∥
or
∥
log
log
를 단계 2에서 계산된 k개의
≥
∈
,
∥
or
∥
log
log
중 가장 작은
≥
∈
,
∥
or
∥
log
log
를 주는 초기 값 쪽의 군집으로 할당한다.
5. 군집의 중심을 다시 계산한다.
6. 3~5의 단계를 반복 후 중심의 변화가 더 이상 발생하지 않으면 단계를 중지한다.
3. 실험결과
본 연구에서 제안한 알고리즘은 MS Visual Studio.NET 2010 을 사용하여 구현하였으며 ArcGIS 9.3을 사용하여 비 교, 분석을 하였다. 또한 알고리즘의 성능을 평가하기 위해, 다 음의 표2와 같이 3가지 대하여 비교 분석을 하였다.
3.1 실험 데이터
3.1.1 라이다 데이터 제원
실험데이터는 캐나다 Optech사의 ALTM 30/70 항공 라이 다 장비를 사용하여 1256.92m의 고도에서 촬영한 것을 사용 하였다. 실험데이터의 이론적인 촬영 제원 상의 점밀도는 3~5
≥
∈
,
∥
or
∥
log
log
이나 다중 반송파의 동일 좌표 중복을 제거한 경우 에는 1~2
≥
∈
,
∥
or
∥
log
log
이다. 촬영은 (주)한진정보통신에서 대전시 지역을 대상으로 총38개의 스트립을 3일에 걸쳐서 촬영하였 으며 그림 5와 표 3은 대상지역의 라이다 데이터의 3차원 가시 화와 라이다 데이터의 제원을 보여준다.
Table 2. Evaluation standards for result analysis Standard 1
Performance comparison between classicaland sweep-hull Delaunay triangulation
Standard 2
Qualitative assessment of result geometryStandard 3
Quantitative assessment of result geometry(edge length, area)
Figure 4. Determination of threshold value using K means
clustering algorithm (Clustering for finding threshold value)
Table 3. Specification of LiDAR data
Item Specification
System Optech ALTM 30/70
Date 2005.2
Area Daejeon city area Altitude 1219.2m
Range 414.77m
Point Density 1~2
≥
∈
