Extraction of Ground Points from LiDAR Data using Quadtree and Region Growing Method

Quadtree와 영역확장법에 의한 LiDAR 데이터의 지면점 추출

Extraction of Ground Points from LiDAR Data using Quadtree and

Region Growing Method

1)

배대섭*ㆍ김진남**ㆍ조기성***

Bae, Dae SeopㆍKim, Jin NamㆍCho, Gi Sung

要 旨

원시 LiDAR 데이터는 벡터 구조이기 때문에 직접 활용 시 처리과정이 복잡해지지만, LiDAR 데이터를 필터링을 통해 정규 가상 격자 형태로 변환하면 데이터 용량이 감소되고 처리 속도가 빠르기 때문에 저가의 장비에서도 처 리가 가능하다. 특히 Quadtree와 같은 영상 압축 처리 기법을 적용할 경우, 평활화를 통하여 비지면 요소인 자동차, 수목등이 제거되어 모델링에 유리하다는 장점이 있다. 따라서 본 연구에서는 대용량의 LiDAR 데이터로부터 Quadtree와 영역확장법을 활용하여 지면점을 자동 추출할 수 있는 알고리즘을 제시하였으며, 오차분류기법을 활용 하여 정확도를 분석하였다. 그 결과, 지면점 분류 정확도는 98%이상으로 나타나, 지면점 추출에 유리함을 알 수 있었다. 또한 Quadtree와 영역확장법을 활용시 자동차, 수목등의 비지면 요소들을 효과적으로 제거할 수 있었다.

핵심용어 : LiDAR, Quadtree, 영역확장법, Cross Matrix

Abstract

Processing of the raw LiDAR data requires the high-end processor, because data form is a vector. In contrast, if LiDAR data is converted into a regular grid pattern by filltering, that has advantage of being in a low-cost equipment, because of the simple structure and faster processing speed. Especially, by using grid data classification, such as Quadtree, some of trees and cars are removed, so it has advantage of modeling. Therefore, this study presents the algorithm for automatic extraction of ground points using Quadtree and refion growing method from LiDAR data. In addition, Error analysis was performed based on the 1:5000 digital map of sample area to analyze the classification of ground points. In a result, the ground classification accuracy is over 98%. So it has the advantage of extracting the ground points. In addition, non-ground points, such as cars and tree, are effectively removed as using Quadtree and region growing method.

Keywords : LiDAR, Quadtree, 영역확장법, Cross Matrix

1. 서 론

최근 GIS 분야에서는 도시지역의 수많은 정보와 속 성들을 평면적인 2차원의 형태에서 더욱더 현실세계와 근접한 3차원의 도시 모델로 나타내고자 많은 연구를 진행하고 있다. 또한 다양한 분야에서 최근 3차원 공간 정보의 활용분야 및 활용 사례가 증가하면서 3차원 공 간정보 구축 시 주로 사용되는 정밀한 3차원 지형 정보 의 필요성 및 중요성이 대두되고 있다. 3차원 지형 정 보는 국토계획 및 관리, 토목, 환경, 자원, 통신, 군사등

다양한 분야에서 활용되고 있다(최윤수 등, 2002). 이 러한 지형정보를 범정부 차원의 통합 데이터 베이스 구 축에 의해 통일성 있는 국가공간정보 인프라를 정비하 면, 예산 절감효과가 연 수천억원에 이를 것으로 전망 되며, 구축된 공간정보인프라를 각종 인터넷 및 통신 등과 결합하여 재개발, 신도시 건설 등에 활용함으로써 기존의 산업이 발전되고, u-city의 실현이 가능할 것으 로 예상된다(장영운과 조기성, 2010).

공간정보구축을 위한 3차원 지형정보는 지상측량, 항 공영상, 인공위성을 이용한 원격 탐사 및 GPS 측량 등

2011년 7월 4일 접수, 2011년 8월 1일 채택

* 정회원ㆍ전북대학교 공과대학 토목공학과 석사([email protected])

** 전북대학교 공과대학 토목공학과 박사과정([email protected])

*** 교신저자ㆍ정회원ㆍ전북대학교 공과대학 토목공학과 교수([email protected]) 연구논문

에 의해서 취득되어진다. 그러나 지상 측량 및 GPS 측 량은 직접적으로 현장에 나가 측량을 실시해야하므로 높은 인건비와 시간이 오래 걸린다는 단점이 있으며, 항공사진 및 위성영상을 이용하여 3차원 정보를 취득 했을 경우 기복변위로 인해 입체 영상의 영상정합시 잘 못된 정합이 발생될 수 도 있고, 태양 고도에 따른 그림 자 지역이나 촬영 각도 및 광각 촬영에 의한 폐색 지역 때문에 지면 추출에 문제가 발생할 수도 있다. 또한 이 러한 영상 취득 방법들은 처리과정 및 방법이 복잡하면 서도 필요로 하는 소요 정확도를 만족시키지 못하고 있 다. 따라서, 보다 정교하고 동적인 지형 데이터를 취득 하기 위해서 LiDAR(Light Detection And Range)가 활발히 이용되고 있다(최연웅 등, 2006).

그러나, 이와 같이 취득된 LiDAR 데이터는 별도의 전처리 과정을 거치지 않으면 벡터 형태로 저장된다. 벡터 데이터 자체를 활용하여 지면을 추출 할 경우 데 이터의 손실을 줄일 수 있어 보다 정밀한 결과를 얻을 수 있다(최연웅 등, 2005). 하지만 데이터를 검색하기 용이하지 않기 때문에 처리과정이 복잡해져 작업시간 또한 늘어나게 된다. 이에 비해 LiDAR 데이터를 정규 가상 격자 형태로 변환하면 변환 과정에서 손실은 발생 할 수 있지만 벡터 구조에 비해 간단한 구조와 빠른 처 리 속도로 인하여 저가의 장비에서도 처리가 가능하다 는 장점이 있다. 특히 Quadtree 기법을 활용할 경우 수 치해석기법의 적용이 용이하고, 도심지역과 같이 넓고 경사가 완만한 지역을 빠르게 검색할 수 있다.

따라서, 본 연구에서는 대용량의 LiDAR 데이터로부 터 지면점을 추출하기 위해 필터링 기법을 활용하여 LiDAR 데이터를 가상 격자화시켰다. 또한 가상 격자

그림 1. 전반적인 연구 흐름도

화된 LiDAR 데이터를 Quadtree와 영역확장법을 활용 하여 지면점을 자동 추출할 수 있는 알고리즘을 제시하 였다. 지면점/비지면점의 분류 정확도를 분석하기 위하 여 대상지역의 수치지도 1: 5000을 기준으로 오차분석 기법인 Cross-Matrix를 적용하여 정확도 분석을 수행하 였다. 그림 1은 전반적인 연구 흐름도를 보여주고 있다.

2. 알고리즘 개요

2.1 Quadtree 기법

GIS 분야에서 도시 환경의 기반이 되는 지형의 표현 은 매우 중요하다. 하지만 대부분의 지형 데이터들은 일반적으로 데이터양이 방대하여 하드웨어의 속도가 빨라져도 데이터 그대로 처리하기는 쉽지가 않다. 따라 서 기존의 방대한 지형 데이터를 처리하기 위해 다양한 형태의 데이터 구조와 간략화 기법들이 고안되었다 (Linstrom et al., 1996).

지형 데이터를 빠르게 검색하기 위한 대표적인 구조 로써 Quadtree 기법이 있다. 이 구조는 계층적인 처리 에 적합한 영상 데이터의 처리의 방법으며 영상을 각각 의 노드가 최대 4개의 자식을 가진 트리에 의하여 표현 하는 방법이다(고성식 등, 2005). 따라서, 가변크기의 가상 격자(variable sized grid cell)를 사용하는 방식으 로 한 지역을 일정한 크기의 격자로 나누기 보다는 세 밀한 지역은 격자로 세분화 한다. 그림 2는 Quadtree 표현 방식을 나타낸 것이다.

본 연구에서 활용된 Quadrtee 기법은 격자기반의 데 이터에서 수행하기 수월하기 때문에 원시 LiDAR 데이 터를 최소값 필터를 활용하여 가상 격자화시켰다. 그 후, 전체 지역의 격자 표고값에 대한 평균과 표준편차 를 계산하고 최대 크기의 가상 격자 내부의 표준편차가

그림 2. Quadtree 표현방식

임계값 이상일 경우 4등분을 하고, 그 가상 격자에 평 균값을 저장하게 된다. 이러한 과정은 격자를 4등분 했 을 때 크기가 최소인 격자가 생성될 때까지 반복 수행 하게 되며 모든 격자의 분할이 완료되면 각 격자에서는 포함된 LiDAR 데이터의 표고값의 평균을 저장하게 된 다. 이러한 Quadtree 방식은 인접한 격자의 사용을 필 요로 하는 분석에 있어서 대단히 빠르고 편리한 데이터 의 추출을 가능하게 하며 전반적인 시스템의 성능을 향 상시키고, 특히 특정 폴리곤 내에 해당되는 격자나 포 인트를 찾을 때 유용하다. 각각의 압축 알고리즘은 대 상에 따라서 다양한 압축률을 나타내므로 가장 좋은 압 축 기법을 선정할 수는 없지만 대체적으로 넓은 지역에 서 적은 속성값으로 나누어진 경우, Quadtree 기법이 활용되고 있다.

그림 3은 본 연구에서 제시된 Quadtree 알고리즘의 수행 순서를 보여준다. Quadtree 알고리즘을 활용하여 속성값을 분류하기 위한 표준편차는 1m로 설정하여 수 행하였다. 또한 최대가상격자 한 변 크기는 최대 Quadtree의 깊이를 n이라 했을 때, 2ⁿ 식에 의해 미리 연산되고 대상지역 세로길이에 근접한 값으로 결정된다.

그림 3. Quadtree 수행 순서도

(a) Start of Growing a Region

(b) Growing Process After a Few Iterations 그림 4. 영역확장법의 개요

2.2 영역확장법의 적용

일반적으로 영상 및 DEM 또는 DSM 등의 동일한 객체의 영역에 소속된 화소들은 서로 유사한 통계적 특 성을 갖는다. 즉 LiDAR의 경우 표고정보 혹은 반사강 도 정보들은 서로 유사한 특성을 가지고 있으며 이를 공간적 동질성(spatial homogeneity)이라 한다.

영역확장법(region growing)은 seed point를 중심으 로 분할 여부를 결정하는 변수를 통해 색감, 질감, 명암 등이 유사하다고 판단되는 화소들을 분할한다(윤아영, 2004). 이러한 특성을 이용하여 미리 정의된 기준에 따 라 화소들을 더 큰 영역으로 군집화하는 과정으로써 그 림 4에서와 같이 초기 시작점을 시작으로 유사한 영역 을 확장시키는 방법이다.

하지만 Quadtree가 수행된 가상 격자 데이터는 위의 그림과 달리 사각형의 크기가 다른 가변형 격자이다.

따라서 Quadtree 알고리즘이 수행된 가상 격자 데이터 로부터 영역확장법을 활용하여 지면점을 추출하기 위 해서는 시작격자 설정이 매우 중요하다. 그 이유는 시 작격자를 맨홀과 같이 지표면보다 비정상적으로 낮은 점을 시작격자로 설정하게 되면 연산 과정에서 오류가 발생할 수 도 있고 부정적인 결과를 초래할 수 있기 때 문이다. 따라서 처음 시작 격자는 최소 크기의 격자보 다 한 단계 큰 격자를 시작격자로 설정해야한다. 또한 인접 버퍼의 크기는 격자와 격자 사이에 버퍼가 겹치는 것을 방지하기 위해 시작격자 크기에 최소격자 크기의 1/2를 더하여 버퍼를 수행하였다. 그림 5는 시작격자 선정과 버퍼의 크기를 설명해주고 있다.

그림 5. 시작격자 선정과 버퍼

시작격자 주변으로 버퍼를 수행을 하면 버퍼에 포함 되는 여러 격자들과 시작 격자와의 경사도를 분석하게 된다. 가상 격자 중심간 거리와 표고값의 차이의 비로 경사도가 계산된다. 경사도는 도로의 구조ㆍ시설에 관 한 규칙(2009.02.19 국토해양부령 101호)과 같이 법적 으로 최대 종단경사를 규정하고 있다. 국지도로는 기능 적 체계로 구분할 때의 맨 하위 체계, 주택지ㆍ상업지 따위에서 직접 통행이 이루어지는 도로로 정의되어 있 다. 따라서 본 연구에서는 도심지의 지형 경사도 임계 값은 국지도로의 경사도를 기준으로 지면점 추출을 수

그림 6. 영역확장법 수행 순서도

행하였다. 하지만 도심지의 아파트 단지 지역일 경우 경사가 급한 지하 주차장이 있기 때문에 영역확장법을 수행 시 적용할 경사도 임계값을 안전율을 고려하여 경 험적으로 가장 적당하다고 판단되는 25%로 설정하였다.

경사도 분석 후 경사도가 임계값 이하인 격자일 경우 지면점으로 분류가 되며, 경사도가 임계값 이상인 격자 일 경우 비지면점으로 분류가 된다. 경사도 분석이 가 상 격자 주변 모두 완료가 되면 경사도 연산이 수행된 가상 격자 중 지면점이 존재하는 가상 격자를 다음 시 작격자로 설정하여 경사도 연산을 계속 수행하게 된다.

이러한 과정은 더 이상 분류할 가상 격자가 존재 하지 않을 때까지 영역확장법을 수행하여 지면점과 비지면 점을 분류하게 된다. 그림 6은 Quadtree 개념을 활용하 여 영역확장법을 적용한 지면점과 비지면점 분류 수행 순서를 나타낸 것이다.

3. 적용 및 고찰

3.1 대상 지역 선정

본 연구에서 사용된 LiDAR 데이터는 그림 7, 그림 8과 같이 주거 및 상가 지역을 포함한 건물과 지면의 구분이 뚜렷하고 높은 건물과 낮은 건물이 분포되어있 는 두 곳을 대상으로 하였다. 또한 대상지역영상은 LiDAR 데이터 취득시 보조 장비로 활용된 CCD 카메 라로부터 취득되었다.

그림 7. 대상지역(Ⅰ)의 항공영상과 원시 LiDAR

그림 8. 대상지역(Ⅱ)의 항공영상과 원시 LiDAR

그림 9. 최소값 필터의 원리

3.2 데이터 구축

본 연구에서는 벡터 형태의 대용량 LiDAR 데이터 처리를 수월하게 하기 위해서 필터링 기법 중 경험적으 로 가장 지면점 추출에 유리하다고 판단되는 최소값 필 터링을 활용하여 가상 격자화시켰다. 그림 9와 같이 원 시 LiDAR 데이터에 최소값 필터를 적용하면, LiDAR 데이터 가상 격자 안에 지면 포인트 없이 건물, 인공 구 조물등과 같은 비지면 포인트가 존재하더라도 그 중 가 장 낮은 표고값을 대표 표고값으로 설정하기 때문에 지 면 분류시 인접 가상 격자와의 경사도가 임계값 이하가 되어 지면점으로 분류되기 때문이다(배대섭 등, 2011).

3.3 Quadtree 알고리즘 적용 결과

Quadtree 알고리즘은 Microsoft 사의 Visual Basic 6.0을 사용하였으며, ASCII 형식의 LiDAR 원시 데이 터를 Shape 파일 형식으로 변환하거나 데이터 확인 및 결과 분석 시각화를 위한 프로그램으로 ESRI 사의 ArcGIS 9.2와 ArcView 3.3 등을 활용하였다.

그림 10과 그림 11은 대상지역 LiDAR 데이터로부

그림 10. 대상지역(Ⅰ) Quadtree 알고리즘 수행결과

그림 11. 대상지역(Ⅱ) Quadtree 알고리즘 수행결과

터 Quadtree 알고리즘을 수행한 결과이다.

위의 Quadtree 수행 결과에서 볼 수 있듯이 가상 격 자 데이터 표고값의 표준편차의 임계값 이하인 아파트 주변 도로나 아파트 건물 사이에 존재하는 주차장등 평 지 대부분 큰 가상 격자를 나타내고 있다. 또한 아파트 주변의 수목지역 그리고 차량이 주차되어있는 지역은 가상 격자가 세분화되었다. 또한 대상지역 영상과 Quadtree 수행결과를 비교해보면 표고값이 낮은 차량 이나 지물등은 큰 지면 가상 격자로 대부분 분류되었음 을 볼 수 있다(그림 12).

그림 12. 대상지역영상과 Quadtree 결과 비교

그림 13. (I)지역 지면/비지면 분류 결과

그림 14. (II)지역 지면/비지면 분류 결과

3.4 영역확장법 적용 결과

본 연구에서는 LiDAR 데이터로부터 지면점과 비지 면점을 분류하기 위해 Quadtree 기법과 영역확장법을 적용한 알고리즘을 제시하였다.

그림 13과 14는 대상지역 (I)과 (II)는 최소값 필터 에 활용해 가상 격자화된 LiDAR 데이터를 제안된 알 고리즘에 의해 지면과 비지면으로 분류한 결과를 나타 낸 것이다. 지면은 노란색점 그리고 비지면점은 갈색점 으로 설정하였으며 분류 정확도를 시각적으로 볼 수 있 도록 1: 5000 수치지도와 비교하였다. 이때 수치지도는 모든 속성 데이터를 포함하고 있기 때문에 수치지도에서 건물 레이어만 추출하여 LiDAR 데이터에 중첩하였다.

3.5 정확도 분석

위의 결과들을 수치지도 1/5,000과 비교해서 분석한

그림 15. LiDAR 데이터의 오분류 유형

대상 지역

종류

참조 지 면 비지면 합 계 오차(%) (Ⅰ)

지역

지 면 30,049 357 30,406 1.17%

비지면 117 8,665 8,782 1.33%

합 계 30,166 9,022 39,188 1.2%

(Ⅱ) 지역

지 면 121,626 1,457 123,083 1.18%

비지면 337 26,650 26,987 1.24%

합 계 121,963 28,107 150,070 1.19%

표 1. 제안된 알고리즘 적용 시 오차분석

결과 지면과 비지면을 양호하게 분류되었음을 알 수 있 었다. 그러나 분류된 LiDAR 데이터는 그림 15와 같은 오분류가 존재하기 때문에 그 분류 정확도를 분석하기 위해 Cross-Matrix를 이용하였다(Sithole, 2001).

지면에서 비지면으로 오분류된 점의 개수와 비지면 에서 지면으로 오분류된 점의 개수를 파악하여 지면점 분류오차, 비지면점 분류오차 및 총 오차를 분석하였다.

표 1은 제안된 알고리즘을 활용해 지면과 비지면 분류 결과를 Cross-Matrix를 활용해 분석한 결과이다.

위의 결과를 분석해 보면, 제안된 알고리즘을 활용하 여 지면점과 비지면점을 분류한 결과를 보면 대상지역 (I)의 분류 오차는 1.2%이며, 대상지역(II)의 분류 오차 는 1.19%로 지면 분류 정확도가 상당히 양호함을 알 수 있다.

그 요인으로는 Quadtree 수행 시 가상 격자 내부의 표고값들이 설정된 임계값의 표준편차 1m 이하면 대부 분 동일한 격자로 분류되었기 때문이다. 또한 LiDAR 가상 격자의 최소 표고값을 대푯값으로 설정하므로 영 역확장법을 활용한 지면 분류시 대부분의 자동차, 수목 그리고 지물등은 경사도 임계값 25%이하로 설정되어 지면점으로 분류되었기 때문이라 판단된다.

4. 결 론

본 연구는 LiDAR 데이터로부터 Quadtree와 영역확 장법을 활용하여 지면점 추출을 위한 연구로써 다음과 같은 결론을 얻을 수 있었다.

첫째, 대용량의 도심 LiDAR 데이터로부터 Quadtree 와 영역확장법을 활용하여 지면점을 자동 추출할 수 있 는 알고리즘을 제시하였다.

둘째, 제안된 알고리즘을 활용한 지면추출 결과의 총 오차를 분석한 결과, 지면점 분류 정확도는 98% 이상 으로 나타나, 지면점 추출에 양호하다고 판단된다.

셋째, Quadtree와 영역확장법을 활용하여 지면점과 비지면점을 분류한 결과, 수목, 자동차 그리고 인공지 물 등과 같은 비지면적 요소를 효과적으로 제거할 수 있었다.

참고문헌

1. 고성식, 구대성, 최현용, 김정화, 2005, 충격성 잡음에 효과적인 사분위편차 기반 쿼드트리 영역분할, 대한전 자공학회 논문지

,

2. 배대섭, 고제웅, 조기성, 2011, 도심 LiDAR 자료로부터 지면점 추출을 위한 Quadtree와 영역확장 적용 분석, 한국지형공간정보학회 춘계학술대회, 한국지형공간 정보학회, pp.237-238.

3. 윤아영, 2004, 고해상도 위성영상의 그림자 효과 보정 에 관한 연구, 서울대학교 석사 학위논문.

4. 장영운, 조기성, 2010, 3차원 점군자료의 효율적 저장 을 위한 자료구조 연구, 한국지형공간정보학회지_, 제18권, 제2호, pp.113-118.

5. 최연웅, 조기성, 2005, 도시지역 LiDAR DSM으로부터 DEM추출 기법연구, 한국지형공간정보학회지, 제13 권, 제1호, pp.19-25.

6. 최연웅, 최내인, 이준환, 조기성, 2006, LiDAR 자료의 지면정보 추출기법의 정확도 평가, 한국지형공간정 보학회지, 제14권, 제4호, pp.12-26.

7. 최윤수, 한상득, 위광재, 2002, 도화원도를 이용한 LiDAR DEM의 정확도 평가, 한국측량학회지, 제2권 제20호, pp.23-32.

8. Barrow, H. G, 1981, Scene Modeling: A Structural Basis for Image Description,

Computer Graphics and Image Processing

9. Haala, N., Brenner, C, 1999, Extraction of building and trees in urban environments,

ISPRS Journal of Photogrammetry & Remote Sensing

130-137.

10. Kilian, J., N.Haala, and M.Englich, 1996, Capture and evaluation of airborn laser scanner data,

international Archives of Photogrammetry and Remote Sensing

11. P. Linstrom, D. Koller, W. Wibarsky, Larry F, Hodge, N. Faust and G. A. turner, 1996, Real-time, Continuous Levels of detail for hight field.

SIGGRAPH

12. Sithole G, 2001, Filtering of laser altimetry data using a slope adaptive filter.

IAPRS

13. Vosselman G, 2000, Slope based filtering of laser altimetry data.

IAPRS