KR101740259B1 - 3차원 포인트 클라우드의 공간 분할 방법 - Google Patents

Abstract

본 발명은 3차원 포인트 클라우드의 공간을 다수 개의 그리드 셀로 균등 분할하는 단계, 3차원 포인트 클라우드의 공간상에서 바닥에 해당하는 베이스 면을 설정하는 단계, 베이스 면의 수직에 있는 모든 그리드 셀의 포인트를 누적하는 단계 및 포인트가 누적된 그리드 셀을 상기 누적된 포인트의 개수에 따라 물체와 바닥으로 분할하는 단계를 포함하는 것을 특징으로 한다.

Description

3차원 포인트 클라우드의 공간 분할 방법{AUTO SEGMENTATION METHOD OF 3D POINT CLOUDS}

본 발명은 3차원 포인트 클라우드의 공간 분할 방법에 관한 것으로서, 더욱 상세하게는 스캐너를 이용하여 획득한 대용량의 3차원 포인트 클라우드를 공간상에서 의미있는 그룹으로 분할하는 3차원 포인트 클라우드의 공간 분할 방법에 관한 것이다.

스캐너 장비는 정확한 3D 데이터를 신속하게 획득하기 위하여 다양한 분야에서 활용되고 있다.

스캐너 장비를 통해 획득한 데이터는 3차원 포인트 클라우드(3D Point Clouds;3차원 점 집합)라 하며, 이 엄청난 양의 포인트 클라우드들을 다루기 위한 다양한 기법들이 이슈가 되고 있다.

특히, 포인트들이 어느 물체에 속하는 포인트들인 지 혹은 하나의 물체를 표현하는 포인트들이 나타내는 것이 건물 혹은 나무 등인지를 구분하는 방법들이 이슈에 해당한다.

3차원 점 집합을 분할하는 문제는 가장 기본적이면서 어려운 문제이다. 스캐너 장비를 이용하여 획득한 실세계 데이터에는 노이즈가 많이 포함되어 있으며, 데이터가 너무 많기 때문이다. 데이터의 부정확한 획득으로 인해 물체와 배경 데이터 간에 정확하게 분할되지 않는다.

본 발명의 배경기술은 대한민국 특허공개번호 10-2010-0106126호(2010.10.01)에 개시되어 있다.

본 발명은 실세계에서 물체들이 바닥과 수직으로 형성되어 있는 특성을 이용하여 3차원 포인트 클라우드를 바닥과 그 외 물체로 실시간 분할하는 3차원 포인트 클라우드의 공간 분할 방법을 제공하는데 그 목적이 있다.

본 발명의 일 측면에 따른 3차원 포인트 클라우드의 공간 분할 방법은 3차원 포인트 클라우드의 공간을 다수 개의 그리드 셀로 균등 분할하는 단계; 상기 3차원 포인트 클라우드의 공간상에서 바닥에 해당하는 베이스 면을 설정하는 단계; 상기 베이스 면의 수직에 있는 모든 그리드 셀의 포인트를 상기 베이스면의 그리드 셀에 누적하는 단계; 및 상기 포인트가 누적된 그리드 셀을 상기 누적된 포인트의 개수에 따라 물체와 바닥으로 분할하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 상기 다수 개의 그리드 셀로 균등 분할하는 단계에서, 상기 그리드 셀은 상기 포인트의 개수에 따라 동일 크기로 분할되는 것을 특징으로 한다.

본 발명의 상기 베이스 면의 수직에 있는 모든 그리드 셀의 포인트를 누적하는 단계는 상기 누적된 포인트의 개수를 필터링하여 상기 베이스면의 그리드 셀의 선명도가 임계치 이상이면, 물체로 추정되는 물체 추정 그리드 셀로 결정하는 것을 특징으로 한다.

본 발명의 상기 물체와 바닥으로 분할하는 단계는 상기 물체 추정 그리드 셀을 상기 누적된 포인트의 개수가 많은 순서로 정렬하여 정렬된 순서로 상기 물체 추정 그리드 셀에 근접한 근접 그리드 셀을 찾아 그룹으로 설정하는 단계; 상기 그룹을 3차원으로 확장하여 상기 물체로 추정되는 물체 추정 바운딩 박스를 설정하는 단계; 상기 물체 추정 바운딩 박스에 포함되는 상기 물체 추정 그리드 셀과 상기 근접 그리드 셀 중에서, 상기 포인트를 포함하는 가장 작은 바운딩 박스에 대해 물체를 나타내는 물체 그룹 바운딩 박스로 결정하는 단계; 및 상기 물체 그룹 바운팅 박스에 포함되지 않는 상기 베이스면의 베이스 그리드 셀을 이용하여 바닥을 나타내는 바닥 셀을 결정하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 상기 근접한 그리드 셀은 상기 물체 추정 그리드 셀의 상,하,좌,우 및 대각선 방향에 근접한 그리드 셀인 것을 특징으로 한다.

본 발명의 상기 물체 추정 그리드 셀에 근접한 근접 그리드 셀을 찾아 그룹으로 설정하는 단계는 상기 물체 추정 그리드 셀과 상기 근접 그리드 셀을 같은 그룹에 포함시키는 것을 특징으로 한다.

본 발명의 상기 물체 추정 그리드 셀에 근접한 근접 그리드 셀을 찾아 그룹으로 설정하는 단계는 상기 물체 추정 그리드 셀이 상기 그룹에 이미 속해 있으면, 같은 그룹으로 포함시키는 것을 특징으로 한다.

본 발명의 상기 바닥을 나타내는 바닥 셀을 결정하는 단계는 상기 물체 그룹 바운딩 박스에 포함되지 않는 상기 베이스 그리드 셀 중에서 상기 포인트를 포함하고 있으면서 가장 낮은 곳에 위치한 그리드 셀을 상기 바닥 셀로 결정하는 것을 특징으로 한다.

본 발명은 3차원 포인트 클라우드를 물체와 바닥으로 실시간 자동 분할하여 각 분할된 물체의 포인트들로부터 건물, 나무, 자동차 등으로 쉽게 분할할 수 있도록 한다.

도 1 은 본 발명의 일 실시예에 따른 3차원 포인트 클라우드의 공간 분할 장치의 블럭 구성도이다.
도 2 는 본 발명의 일 실시예에 따른 3차원 포인트 클라우드의 공간 분할 방법의 순서도이다.
도 3 은 본 발명의 일 실시예에 따라 공간을 큐브 모양의 그리드 셀로 균등 분할된 예를 도시한 도면이다.
도 4 는 도 3 의 실세계의 바닥에 해당하는 베이스면을 설정한 예를 도시한 도면이다.
도 5 는 도 4 의 베이스면의 수직에 있는 그리드 셀을 누적한 포인트의 개수를 필터링하여 물체 추정 그리드 셀을 결정하는 과정을 도시한 도면이다.
도 6 은 도 5 에서 결정된 물체 추정 그리드 셀들을 그룹으로 설정한 예를 도시한 도면이다.
도 7 은 도 5 에서 결정된 물체 추정 그리드 셀들을 근접 그리드 셀들과 하나의 그룹으로 설정하는 예를 도시한 도면이다.
도 8 은 도 6 을 통해 설정된 그룹을 3차원으로 확장한 예를 도시한 도면이다.
도 9 는 도 8 을 통해 물체 추정 그리드 셀들을 이용하여 물체의 경계를 나타내는 바운딩 박스를 설정하고, 그 외 지역을 바닥으로 그룹화하는 예를 도시한 도면이다.

이하에서는 본 발명의 일 실시예에 따른 3차원 포인트 클라우드의 공간 분할 방법을 첨부된 도면들을 참조하여 상세하게 설명한다. 이러한 과정에서 도면에 도시된 선들의 두께나 구성요소의 크기 등은 설명의 명료성과 편의상 과장되게 도시되어 있을 수 있다. 또한 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로써, 이는 이용자, 운용자의 의도 또는 관례에 따라 달라질 수 있다. 그러므로 이러한 용어들에 대한 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야할 것이다.

도 1 은 본 발명의 일 실시예에 따른 3차원 포인트 클라우드의 공간 분할 장치의 블럭 구성도이다.

본 발명의 일 실시예에 따른 3차원 포인트 클라우드의 공간 분할 장치는 도 1 에 도시된 바와 같이, 데이터베이스부(10), 공간 분할부(20), 어큐뮬레이터(Accumulator)(30), 필터부(40) 및 그룹핑부(50)를 포함한다.

데이터베이스부(10)는 3차원 데이터를 획득하도록 하는 다양한 스캐너 장비(미도시)를 통해 획득한 3차원 포인트 클라우드를 저장한다.

공간 분할부(20)는 상기한 데이터베이스부(10)로부터 3차원 포인트 클라우드를 입력받아 3차원 포인트 클라우드를 공간(60)상에서 균등 분할하여 다수 개의 그리드 셀(51)을 획득한다.

여기서, 각 그리드 셀(51)은 큐브 모양으로 크기가 일정하며, 내부에 다수 개의 3차원 포인트 클라우드를 포함하며, 사용자가 임의로 결정하거나, 하나의 그리드 셀(51) 당 포함될 수 있는 최대 포인트의 개수를 설정하여 결정될 수 있다.

어큐뮬레이터(30)는 공간 분할부(20)에 의해 그리드 셀(51)로 균등 분할된 공간(60)에서 베이스면(Base plane)(52)을 설정하고, 설정된 베이스면(52)을 기준으로 수직에 있는 모든 그리드 셀(51)들에 포함된 모든 포인트의 개수를 바닥의 각 그리드 셀(51)에 누적한다. 이는 실세계에서는 모든 물체는 수직으로 향한다는 특성을 고려한 것이다.

아울러, 베이스면(52)은 스캐너 장비(미도시)에 의해 x-y-z 축이 달라질 수 있으므로, 사용자에 의해 다양하게 정의할 수 있다.

참고로, 본 명세서에서 바닥의 각 그리드 셀(51)을 베이스 그리드 셀(53)이라 한다.

필터부(40)는 베이스면(52)에 수직으로 누적된 포인트의 개수를 필터링하여 그 값이 큰 것은 더욱 크게 하는 반면 작은 것은 더욱 작게 하여 에러값들의 영향을 감소시키고 경계값들을 드라마틱하게 만들어준다.

이러한 필터부(40)는 고주파 강조 필터가 채용될 수 있으며, 특히, 상기한 바와 같이 선명도를 높인 후, 임계치를 초과하는 그리드 셀(51)을 물체로 추정되는 물체 추정 그리드 셀(55)로 간주한다.

그룹핑부(50)는 필터부(40)에서 필터링된 값들을 가장 큰 순으로 정렬하여 물체와 바닥으로 그룹하여 물체와 바닥으로 분할하여 저장한다.

이하, 본 발명의 일 실시예예에 따른 3차원 포인트 클라우드의 공간 분할 방법을 도 2 내지 도 9 를 참조하여 상세하게 설명한다.

도 2 는 본 발명의 일 실시예에 따른 3차원 포인트 클라우드의 공간 분할 방법의 순서도이고, 도 3 은 본 발명의 일 실시예에 따라 공간을 큐브 모양의 그리드 셀로 균등 분할된 예를 도시한 도면이며, 도 4 는 도 3 의 실세계의 바닥에 해당하는 베이스면을 설정한 예를 도시한 도면이며, 도 5 는 도 4 의 베이스면의 수직에 있는 그리드 셀을 누적한 포인트의 개수를 필터링하여 물체 추정 그리드 셀을 결정하는 과정을 도시한 도면이며, 도 6 은 도 5 에서 결정된 물체 추정 그리드 셀들을 그룹으로 설정한 예를 도시한 도면이며, 도 7 은 도 5 에서 결정된 물체 추정 그리드 셀들을 근접 그리드 셀들과 하나의 그룹으로 설정하는 예를 도시한 도면이며, 도 8 은 도 6 을 통해 설정된 그룹을 3차원으로 확장한 예를 도시한 도면이며, 도 9 는 도 8 을 통해 물체 추정 그리드 셀들을 이용하여 물체의 경계를 나타내는 바운딩 박스를 설정하고, 그 외 지역을 바닥으로 그룹화하는 예를 도시한 도면이다.

먼저, 공간 분할부(20)는 데이터베이스부(10)에 저장된 3차원 포인트 클라우드를 공간(60)상에서 다수 개의 그리드 셀(51)로 균등 분할한다(S10).

여기서, 그리드 셀(51)의 크기는 사용자가 결정을 할 수도 있고, 하나의 그리드 셀(51) 당 최대 포함하는 포인트의 개수를 설정하여 결정할 수도 있다.

공간 분할부(20)에서 다수 개의 그리드 셀(51)로 분할되면, 어큐뮬레이터(30)가 도 3 과 도 4 에 도시된 바와 같이, 베이스면(52)을 설정하고, 베이스면(52)을 기준으로 수직에 있는 모든 포인트들을 누적한다(S20,S30).

즉, 공간 분할부(20)는 균등 분할된 공간(60)에서 베이스면(52)을 설정하기 위해 도 3 과 도 4 에 도시된 바와 같이, 실세계에서 모든 물체는 수직으로 향한다는 특성을 고려하여 xz 평면을 바닥면으로 설정한다.

상술한 바와 같이, 공간(60)에서 모든 물체는 수직으로 향하고 있기 때문에 베이스면(52)을 기준으로 수직에 있는 모든 그리드 셀(51)에 속한 모든 포인트의 개수를 바닥의 각 그리드 셀(51), 즉 베이스 그리드 셀(53)에 누적한다.

이 경우, 모든 포인트들이 각 베이스 그리드 셀(53)에 누적이 된 결과는 수직으로 높이 올라갈수록 베이스 그리드 셀(53)이 포함하는 포인트의 개수가 높을 것이며, 높이가 낮을수록 베이스 그리드 셀(53)이 포함하는 포인트의 개수가 낮을 것이다. 이는 베이스 그리드 셀(53)이 포함하는 포인트가 많을수록 물체일 확률이 높은 것을 뜻하게 된다.

여기서, 베이스면(52)에 누적된 포인트의 개수을 살펴보면, 스캐너 장비의 스캔 에러로 인해 포인트가 비정확하게 얻어질 수 있다. 따라서, 포인트에 위치 에러가 존재하게 된다. 이러한 위치 에러는 포인트를 베이스 그리드 셀(53)에 누적할 때 정확한 위치에 누적되지 않기 때문에 에러가 존재할 수 있게 된다.

이와 같이, 공간 분할부(20)에서 베이스면(52)을 기준으로 수직의 포인트들이 누적되면, 필터부(40)는 고주파 강조 필터링과 같은 필터링을 사용함으로써 선명도를 더욱 높인 후, 임계치를 넘는 베이스 그리드 셀(53)에 대하여 물체로 추정되는 물체 추정 그리드 셀(55)로 결정한다.

즉, 도 5 를 참조하면, (a)와 같이, 베이스면(52)에 누적된 포인트의 개수를 기반으로 하여 베이스 그리드 셀(53)을 결정한다. 여기서, 짙은 색일 경우 포인트의 개수가 많은 베이스 그리드 셀(53)이다.

이 후, (b)와 같이, 누적된 포인트의 개수를 강조한다. 여기서, 짙은 색은 더욱 짙게하고 옅은 색은 더욱 옅게 되는 것을 확인할 수 있다.

최종적으로, (c)와 같이 임계치를 넘는 다수 개의 물체 추정 그리드 셀(55)이 남게 된다.

이때, 임계치는 높이와 관련이 있으며 이는 사용자가 값을 설정하도록 한다. 또한 이때 필터링 방법은 다양한 방법들이 사용 가능하다.

이와 같이, 필터링 과정을 거쳐 물체 추정 그리드 셀(55)이 설정되면, 그룹핑부(50)는 이들 물체 추정 그리드 셀(55)과 근접 그리드 셀(54)을 이용하여 그룹(61)을 설정한다(S40).

이 경우, 임계치를 넘는 물체 추정 그리드 셀(55)을 포인트의 개수가 많은 순으로 정렬하고, 정렬된 순서로 각 물체 추정 그리드 셀(55) 마다 근접 그리드 셀(54)을 찾아 하나의 그룹으로 설정한다.

이때, 근접 그리드 셀(54)은 베이스면(52)상에서 도 7 에 도시된 바와 같이, 물체 추정 그리드 셀(55)의 상, 하, 좌, 우, 대각선 방향으로 인접해 있는 그리드 셀(51)로써, 물체 추정 그리드 셀(55)과 묶어 하나의 그룹(61)에 포함시키도록 한다.

만약, 물체 추정 그리드 셀(55)이 이미 그룹(61)에 속한 상황이라면 근접 그리드 셀(54)을 찾은 후 같은 그룹으로 포함시킨다.

아울러, 그룹(61)으로 묶인 물체 추정 그리드 셀(55)과 근접 그리드 셀(54)은 베이스면(52)상에서의 그룹(61)이므로 이를 3차원으로 확장을 하면 도 8 과 같이 표현 가능하다. 여기서, 도 8 은 측면도이다.

물체 추정 그리드 셀(55)과 근접 그리드 셀(54)을 3차원으로 확장하여, 실세계 바운딩 박스의 높이를 나타내는 경계 바운딩 박스(Bounding box)(63)를 결정한다(S50).

이 경우, 경계 바운딩 박스(63) 내에 속한 그리드 셀(54,55) 중에서 포인트를 포함하고 있는 그리드 셀(54,55)을 포함하는 가장 작은 바운딩 박스에 대해 물체를 나타내는 물체 그룹 바운딩 박스(64)로 결정한다(S60).

이와 같이, 물체 그룹핑이 완료되면, 도 9 에 도시된 바와 같이, 물체 그룹 바운딩 박스(64)에 포함되지 않는 베이스 그리드 셀(53)들을 바닥으로 추정되는 바닥 추정 그리드 셀(67)로 결정한다.

이때 바닥 추정 그리드 셀(67) 중에서 포인트를 포함하고 있으면서 y축으로 가장 낮은 곳에 위치한 그리드 셀(51)을 바닥 셀(67)로 결정한다(S70).

이러한 바닥 셀(67)을 바닥 그룹으로 설정하고, 나머지에 대해서는 물체를 나타내는 물체 셀(68)을 묶어 물체 그룹으로 설정한다.

이와 같이, 본 발명은 3차원 포인트 클라우드를 입력으로 하여 실세계에서의 물체는 수직으로 향한다는 특성을 사용하여 물체와 바닥을 자동 분할할 수 있다.

본 발명은 도면에 도시된 실시예를 참고로 하여 설명되었으나, 이는 예시적인 것에 불과하며 당해 기술이 속하는 기술분야에서 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호범위는 아래의 특허청구범위에 의하여 정해져야할 것이다.

10: 데이터베이스부 20: 공간 분할부
30: 어큐뮬레이터 40: 필터부
50: 그룹핑부 51: 그리드 셀
52: 베이스면 53: 베이스 그리드 셀
54: 근접 그리드 셀 55: 물체 추정 그리드 셀
61, 62: 그룹 63: 경계 바운딩 박스
64: 물체 추정 바운딩 박스 67: 바닥 셀
68: 물체 셀

Claims (8)

1. 3차원 포인트 클라우드의 공간을 다수 개의 그리드 셀로 균등 분할하는 단계;
   상기 3차원 포인트 클라우드의 공간상에서 바닥에 해당하는 베이스 면을 설정하는 단계;
   상기 베이스 면의 수직에 있는 모든 그리드 셀의 포인트를 상기 베이스 면의 그리드 셀에 누적하고, 상기 누적된 포인트의 개수를 필터링하여 상기 베이스 면의 그리드 셀의 선명도가 임계치 이상이면, 물체로 추정되는 물체 추정 그리드 셀로 결정하는 단계; 및
   상기 물체 추정 그리드 셀의 누적된 포인트의 개수에 기초하여 물체를 추정하는 물체 추정 바운딩 박스를 설정하고, 상기 물체 추정 바운딩 박스를 기반으로 상기 물체와 바닥으로 분할하는 단계를 포함하는 3차원 포인트 클라우드의 공간 분할 방법.
2. 제 1 항에 있어서, 상기 다수 개의 그리드 셀로 균등 분할하는 단계에서,
   상기 그리드 셀은 상기 포인트의 개수에 따라 동일 크기로 분할되는 것을 특징으로 하는 3차원 포인트 클라우드의 공간 분할 방법.
3. 삭제
4. 제 1 항에 있어서, 상기 물체와 바닥으로 분할하는 단계는
   상기 물체 추정 그리드 셀을 상기 누적된 포인트의 개수가 많은 순서로 정렬하여 정렬된 순서로 상기 물체 추정 그리드 셀에 근접한 근접 그리드 셀을 찾아 그룹으로 설정하는 단계;
   상기 그룹을 3차원으로 확장하여 상기 물체로 추정되는 물체 추정 바운딩 박스를 설정하는 단계;
   상기 물체 추정 바운딩 박스에 포함되는 상기 물체 추정 그리드 셀과 상기 근접 그리드 셀 중에서, 상기 포인트를 포함하는 가장 작은 바운딩 박스에 대해 물체를 나타내는 물체 그룹 바운딩 박스로 결정하는 단계; 및
   상기 물체 그룹 바운딩 박스에 포함되지 않는 상기 베이스 면의 베이스 그리드 셀을 이용하여 바닥을 나타내는 바닥 셀을 결정하는 단계를 포함하는 것을 특징으로 하는 3차원 포인트 클라우드의 공간 분할 방법.
5. 제 4 항에 있어서, 상기 근접한 근접 그리드 셀은
   상기 물체 추정 그리드 셀의 상,하,좌,우 및 대각선 방향에 근접한 그리드 셀인 것을 특징으로 하는 3차원 포인트 클라우드의 공간 분할 방법.
6. 제 4 항에 있어서, 상기 물체 추정 그리드 셀에 근접한 근접 그리드 셀을 찾아 그룹으로 설정하는 단계는
   상기 물체 추정 그리드 셀과 상기 근접 그리드 셀을 같은 그룹에 포함시키는 것을 특징으로 하는 3차원 포인트 클라우드의 공간 분할 방법.
7. 제 6 항에 있어서, 상기 물체 추정 그리드 셀에 근접한 근접 그리드 셀을 찾아 그룹으로 설정하는 단계는
   상기 물체 추정 그리드 셀이 상기 그룹에 이미 속해 있으면, 상기 근접 그리드 셀을 상기 물체 추정 그리드 셀이 속한 그룹과 같은 그룹으로 포함시키는 것을 특징으로 3차원 포인트 클라우드의 공간 분할 방법.
8. 제 4 항에 있어서, 상기 바닥을 나타내는 바닥 셀을 결정하는 단계는
   상기 물체 그룹 바운딩 박스에 포함되지 않는 상기 베이스 그리드 셀 중에서 상기 포인트를 포함하고 있으면서 가장 낮은 곳에 위치한 그리드 셀을 상기 바닥 셀로 결정하는 것을 특징으로 하는 3차원 포인트 클라우드의 공간 분할 방법.

Images