KR20110097140A

KR20110097140A - 이동 로봇의 위치 추정 장치 및 방법

Info

Publication number: KR20110097140A
Application number: KR1020100016812A
Authority: KR
Inventors: 최기완; 박지영; 이형기
Original assignee: 삼성전자주식회사
Priority date: 2010-02-24
Filing date: 2010-02-24
Publication date: 2011-08-31
Also published as: US20110205338A1

Abstract

위치 추정에 소요되는 시간을 감소시킬 수 있는 위치 추정 장치 및 방법이 제공된다. 이동 로봇의 위치 추정 장치는, 3D 포인트 클라우드 데이터를 획득하는 거리 데이터 획득부와, 이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를 저장하는 저장부와, 획득된 3D 포인트 클라우드 데이터로부터 복수 개의 패치를 추적하여, 위치를 추정하는 위치 추정부를 포함한다.

Description

이동 로봇의 위치 추정 장치 및 방법{Apparatus for estimating location of moving robot and method thereof}

이동 로봇의 위치 추정 장치 및 방법에 관한 것으로, 더욱 상세하게는, 거리 센서를 이용하여 로봇의 자기 위치를 추정할 수 있는 위치 추정 장치 및 방법에 관한 것이다.

광학과 전자학에서의 새로운 기술 발전으로 저렴하면서도 더 정확한 레이저 스캐닝 시스템(laser scanning system)이 가능해지고 있다. 레이저 스캐닝 시스템은 물체로부터 깊이 정보를 직접적으로 얻을 수 있어 거리 이미지 분석(range image analysis)을 간단하게 할 수 있으며, 그 응용영역을 확대시키고 있다. 거리 이미지는 3차원의 구조적 데이터 점들의 집합으로 구성되며 여러 다른 관점에서 물체의 자유 형상 표면을 기술한다.

거리 이미지의 등록(registration)은 머신 비전과 관련되어 널리 알려진 중요한 문제이다. 산점도 행렬(scatter matrix), 기하학적 히스토그램(histogram), 반복 최근점(ICP, iterative closest point), 그래프 매칭(graph matching), 외부점(external point), 거리 기반의 탐색, 상호작용법(interactive method) 등과 같은 여러 가지 방법이 등록 문제를 해결하기 위해 제안되어 왔다. 등록 기법은 물체 인식, 운동 추정, 장면 이해(scene understanding), 로봇 자율 주행 등과 같은 여러 분야에서 다양하게 응용된다.

이러한 방법 중 반복 최근점 알고리즘(Iterative Closest Point) 방법은 제안된 이래 머신 비전 분야에서 많은 관심을 받았다. 반복 최근점 알고리즘(ICP)의 목적은 수학적으로 거리 데이터 좌표계 거리 데이터 세트와 모델 데이터 세트를 정렬할 변환 매트릭스를 찾는 것이다. 이러한 ICP 방법은 비교적 정확도가 높지만 3D 평면 매칭 등의 경우와 같이 비교할 입력 데이터의 양이 많은 경우에는 매칭 수행 시간이 데이터 양에 비례하여 길어지는 문제점이 있다.

위치 추정의 정확도를 유지하면서, 위치 추정에 필요한 데이터 계산량을 감소시켜서, 위치 추정에 소요되는 시간을 감소시킬 수 있는 위치 추정 장치 및 방법이 제공된다.

일 측면에 따른 이동 로봇의 위치 추정 장치로서, 3D 포인트 클라우드 데이터를 획득하는 거리 데이터 획득부와, 이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를 저장하는 저장부와, 획득된 3D 포인트 클라우드 데이터로부터 복수 개의 패치를 추적하여, 위치를 추정하는 위치 추정부를 포함한다.

위치 추정 장치는, 이전에 획득된 3D 포인트 클라우드 데이터로부터 적어도 하나의 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성하고, 생성된 패치를 저장부에 저장하는 패치 생성부를 더 포함할 수 있다.

패치 생성부는, 이전에 획득된 3D 포인트 클라우드 데이터 각각에 대한 법선 벡터를 계산하고, 각각의 법선 벡터를 구성하는 3차원 공간 좌표 (x, y, z)를 각각 RGB 값으로 설정하여, 각각의 법선 벡터를 RGB 영상으로 변환하고, 변환된 RGB 영상을 그레이 영상으로 변환하고, 그레이 영상에서 코너 추출 알고리즘을 이용하여 코너점을 추출하고, 추출된 코너점 중에서 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성할 수 있다.

패치 생성부는, 패치를 각각의 패치의 특징점의 위치 정보와 함께 저장할 수 있다. 패치 생성부는, 패치를 구성하는 포인트들이 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분하여 저장부에 저장할 수 있다.

위치 추정부는, 3D 포인트 클라우드 데이터의 각각의 포인트들에서 법선 벡터를 계산하고, 법선 벡터를 이용하여, 각각의 포인트들이 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분하고, 패치의 에지 포인트는 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 패치의 일반 포인트는 에지 포인트와 일반 포인트 구별 없이 3D 포인트 클라우드 데이터와 매칭시키는 에지 기반 ICP 기반 알고리즘을 이용하여 3D 포인트 클라우드 데이터로부터 패치를 추적할 수 있다.

위치 추정부는, 패치의 에지 포인트들은 가장 가까운 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 패치의 일반 포인트는 가장 가까운 3D 포인트 클라우드 데이터의 포인트와 매칭시킬 수 있다.

다른 측면에 따른 이동 로봇의 위치 추정 방법은, 3D 포인트 클라우드 데이터를 획득하는 단계와, 이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를, 획득된 3D 포인트 클라우드 데이터로부터, 추적하여 이동 로봇 위치를 추정하는 단계를 포함한다.

위치 추정의 정확도를 유지하면서, 위치 추정에 필요한 데이터 계산량을 감소시켜서, 위치 추정에 소요되는 시간을 감소시킬 수 있다.

도 1은 이동 로봇의 위치 추정 장치의 구성의 일 예를 나타내는 블록도이다.
도 2는 이동 로봇의 위치 추정 방법의 일 예를 나타내는 순서도이다.
도 3은 등록된 패치를 이용하여 위치를 추정하는 동작의 일 예를 나타내는 도면이다.
도 4는 패치 생성 방법의 일 예를 나타내는 도면이다.
도 5는 패치 추적에 의한 위치 추정 방법의 일 예를 나타내는 도면이다.
도 6a는 위치 추정 장치가 획득한 3D 포인트 클라우드 데이터 및 미리 등록된 패치의 일 예를 나타내는 도면이다.
도 6b는 일반 ICP를 이용한 패치 추적 과정의 일 예를 나타내는 도면이다.
도 6c는 일 실시예에 따른 에지 기반 ICP 알고리즘을 이용한 패치 추적 과정의 일 예를 나타내는 도면이다.

이하, 첨부된 도면을 참조하여 본 발명의 일 실시예를 상세하게 설명한다. 본 발명을 설명함에 있어 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략할 것이다. 또한, 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.

도 1은 이동 로봇의 위치 추정 장치의 구성의 일 예를 나타내는 블록도이다.

위치 추정 장치(100)는 주행부(110), 센서부(120), 거리 데이터 획득부(130), 제어부(140) 및 저장부(150)를 포함할 수 있다. 이하에서는, 위치 추정 장치(100)가 이동 로봇인 경우를 가정하고 설명한다.

주행부(110)는 이동 로봇(100)을 주행시키기 위하여 복수 개의 바퀴와 같은 주행 수단과, 주행 수단에 구동력을 제공하기 위한 구동원을 포함할 수 있다.

센서부(120)는 이동 로봇(100)에 장착되어 이동 로봇(100)의 이동량 및 회전량을 감지한다. 이를 위해, 센서부(120)는 엔코더(encoder) 또는 자이로 센서(gyrosensor)를 포함할 수 있다. 자이로 센서로 이동 로봇(100)의 실제 회전한 각도가 감지될 수 있으며, 엔코더로 이동 로봇(100)의 실제 움직인 경로가 인식될 수 있다. 상세하게는, 엔코더에 의해 움직인 거리 및 방향을 적분함으로써 현재 이동 로봇의 평면상의 2차원 좌표계상의 위치(position) 및 방향각 추정이 가능하다. 통상적으로, 엔코더는 짧은 구간에서는 비교적 정확하지만 적분을 계속 수행해 나감에 따라 오차가 누적된다. 한편, 센서부(120)는 장애물 지도를 작성하는데 이용되는 장애물 감지 정보를 감지하기 위하여 적외선, 레이저 또는 초음파 센서를 더 포함할 수 있다.

거리 데이터 획득부(130)는 3차원 환경을 스캐닝하여 획득된 스캔 데이터를 처리하여 스캐닝한 3차원 환경에 대한 거리 데이터(range data)를 측정한다. 거리 데이터 획득부(130)는 거리 데이터를 감지 및 측정하기 위하여 3차원 환경을 인식할 수 있도록 레이저 구조광(structured light)을 이용한 센서 시스템을 포함하여 구성될 수 있다.

거리 데이터 획득부(130)는 3D 거리 센서(도시되지 않음)를 포함하여 3D 거리 정보인 R[r, θ, ψ]를 획득한다. 거리 데이터 획득부(130)는 3D 거리 정보인 R[r, θ, ψ]를 P[x, y, z]로 표현되는 3D 포인트 클라우드(point cloud)로 변환할 수 있다. x는 r*cosψ*cosθ로, y는 r*cosψ*sinθ로, z는 r*sinψ의 값을 가진다.

제어부(140)는 주행 경로 계획 장치(100)의 동작 전반을 제어하도록 구성될 수 있다. 제어부(140)는 패치 생성부(142), 위치 추정부(144) 및 경로 생성부(146)을 포함할 수 있다.

패치 생성부(142)는 3D 포인트 클라우드 데이터로부터 적어도 하나의 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성하고, 생성된 패치를 저장부(150)에 저장한다. 통상적으로, 영상 센서로부터 얻은 영상으로부터 SIFT(Scale-Invariant Feature Transform), MSER(Maximally Stable Extremal Region) 기법, 또는 해리스 코너 검출(Harris Corner Detector) 방법 등과 같은 특징점 추출 알고리즘을 이용하여 특징점 및 특징점 기술자가 생성되어, 위치 추정에 이용된다. 일 실시예에서는, 특징점 주변의 포인트들을 포함하는 패치가 위치 추정에 이용된다. 패치의 형태는 다양한 3차원 형태를 가질 수 있다. 패치는 예를 들어, 3D 클라우드 데이터에서 특징점을 중심으로 하는 정육면체에 포함되는 포인트들로 구성될 수 있다.

패치 생성부(142)는, 3D 포인트 클라우드 데이터 각각에 대한 법선 벡터(normal vector)를 계산한다. 패치 생성부(142)는 각각의 법선 벡터를 구성하는 3차원 공간 좌표 (x, y, z)를 각각 RGB 값으로 설정하여, 각각의 법선 벡터를 RGB 영상으로 변환한다. 그런 다음, 패치 생성부(142)는 변환된 RGB 영상을 그레이 영상으로 변환하고, 그레이 영상에서 코너 추출 알고리즘을 이용하여 코너점을 추출하고, 추출된 코너점 중에서 특징점을 추출할 수 있다. 여기에서 특징점은 사물의 모서리 또는 코너와 같이 형상을 특정시킬 수 있는 점을 의미한다.

패치 생성부(142)는 특징점 주변의 3차원 공간상에 위치하는 포인트들을 패치로서 생성할 수 있다. 따라서, 특징점은 생성된 패치의 중간에 위치하는 점일 수 있다.

패치 생성부(142)는, 패치를 각각의 패치의 특징점의 위치 정보와 함께 저장할 수 있다. 또한, 패치 생성부(142)는, 패치를 구성하는 포인트들이 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구별하여 저장부(150)에 저장할 수 있다.

위치 추정부(144)는 이동 로봇(100)이 출발하는 위치 및 출발시 방향각을 기준값으로 위치를 추정할 수 있다. 이동 로봇의 위치를 추정한다는 것은 이동 로봇의 2차원 평면상에서의 위치 및 방향각을 추정함을 의미한다. 이동 로봇(100)의 위치에 대한 기준은 지도(map) 상에 존재하는 특징점(Feature)을 포함하는 패치가 될 수 있다. 따라서, 이동 로봇(100)의 위치 정보는 이동 로봇(100)이 인식한 특징점을 기준으로 한 이동 로봇(100)의 위치 및 방향각을 포함할 수 있다.

위치 추정부(144)는 주행부(110) 및 센서부(120)로부터 획득되는 오도메트리 정보, 각속도, 가속도 등의 정보를 종합적으로 이용하여 위치를 추정 및 인식할 수 있다. 또한, 위치 추정부(144)는 추정된 위치를 입력으로 하여 슬램을 수행하여 지도 작성과 함께 위치 인식을 수행할 수 있다. 슬램은 어떤 위치에서 주변 환경의 지도를 구성하고 구성된 지도를 바탕으로 다시 이동한 로봇의 위치를 알아내는 과정을 반복하여 로봇의 위치와 주변 환경의 지도를 동시에 추정할 수 있는 알고리즘이다.

일 예로, 위치 추정부(144)는 엔코더 및 자이로 정보와 통합하여 새로운 거리 정보를 추출할 수 있도록 칼만 필터(Kalman Filter)를 이용할 수 있다. 칼만 필터는 기본적으로 모델에 의해 위치를 추정하는 예측 과정과, 센서 값을 통하여 추정된 값을 보정하는 업데이트 과정으로 구성된다.

위치 추정부(144)는 예측 과정에서는, 이전 과정의 예측치에 미리 설정된 모델을 사용하여 주어진 입력에 대하여 예산되는 출력을 추정한다.

위치 추정부(144)는 예측 과정에서는, 과거의 위치 정보와 센서부(120)에서 새롭게 획득한 정보를 가지고 현재의 위치를 예측한다. 위치 추정부(144)는 업데이트 과정에서는 예측된 위치를 기준으로 새롭게 획득된 3D 포인트 클라우드 데이터로부터 복수 개의 패치를 추적하고, 추적된 정보를 가지고 더욱 정확한 위치를 추정하게 된다. 미리 저장된 패치들은 각각 독립된 좌표계를 가지고 있으며, 독립된 좌표계와 절대 좌표계 사이의 변환 정보를 가지고 있다. 따라서, 저장된 패치의 위치는 변환 정보와 예측 과정에서 예측된 로봇의 위치 정보를 가지고 로봇의 좌표계 기준의 상대 위치로 변환되고, 추적된 패치의 위치와의 차이를 계산하여 로봇의 위치를 추정하게 된다.

또한, 위치 추정부(144)는 추적된 패치 중에서 잘못 추정된 추정 결과를 제거할 수 있다. 이를 위해서, 위치 추정부(144)는 RANSAC(RANdom SAmple Consensus) 또는 JCBB(Joint Compatibility Branch and Bound) 방법 등을 이용할 수 있다. 이 밖에도, 위치 추정부(144)는 위치 인식과 지도 구성을 수행하는 한 다양한 구조를 가질 수 있다.

위치 추정부(144)는, 다음과 같은 방법으로, 패치를 추적할 수 있다. 여기에서, 패치는 이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함한다. 우선, 위치 추정부(144)는 3D 포인트 클라우드 데이터의 각각의 포인트에서 법선 벡터를 계산하고, 법선 벡터를 이용하여 3D 포인트 클라우드 데이터의 각각의 포인트들이 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분한다. 위치 추정부(144)는 패치의 에지 포인트는 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 패치의 일반 포인트는 에지 포인트와 일반 포인트 구별 없이 3D 포인트 클라우드 데이터와 매칭시키는 에지 기반 ICP(edge combination ICP) 알고리즘을 이용하여 3D 포인트 클라우드 데이터로부터 패치를 추적할 수 있다. 여기에서, 위치 추정부(144)는, 패치의 에지 포인트는 가장 가까운 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 패치의 일반 포인트는 가까운 3D 클라우드 데이터 포인트와 매칭시킬 수 있다.

경로 생성부(146)는 위치 추정부(144)에서 인식된 이동 로봇(100)의 위치 정보를 이용하여 경로를 생성할 수 있다.

저장부(150)는 위치 추정 장치(100)의 동작에 필요한 운영체제, 애플리케이션 및 데이터가 저장될 수 있다. 또한, 저장부(150)는 이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를 저장하는 패치 저장부(152)를 포함할 수 있다.

도 2는 이동 로봇의 위치 추정 방법의 일 예를 나타내는 순서도이다.

위치 추정 장치(100)는 3D 포인트 클라우드 데이터를 획득한다(210).

위치 추정 장치(100)는 이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를, 획득된 3D 포인트 클라우드 데이터로부터, 추적하여 이동 로봇 위치를 추정한다(220).

위치 추정 장치(100)는 등록된 패치의 개수가 미리 설정된 개수 이하이거나, 추적된 패치의 개수가 미리 설정된 개수 이하인 경우와 같이, 추가적으로 패치가 필요하다고 판단하는 경우(230), 획득된 3D 포인트 데이터로부터 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성하여, 저장부(150)에 저장함으로써 패치를 추가적으로 등록할 수 있다(240).

도 3은 등록된 패치를 이용하여 위치를 추정하는 동작의 일 예를 나타내는 도면이다.

도 3에서, 프레임 N1(310)은 이전에 획득된 3D 포인트 클라우드 데이터를 나타내고, 프레임 N2(320)는 현재 획득된 3D 클라우드 포인터 데이터를 나타낸다.

위치 추정 장치(100)는, 프레임 N1(310)의 영역(311)에서 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치(333)를 패치 저장부(152)에 저장해둘 수 있다. 패치 저장부(152)에는 패치(333)를 포함하는 복수 개의 패치(331, 332, 333)가 등록되어 저장될 수 있다.

위치 추정 장치(100)가 프레임 N2(320)를 획득하면, 프레임 N2(320)에서 미리 등록된 복수 개의 패치(331, 332, 333)를 추적할 수 있다. 예를 들어, 패치(333)가 프레임 N2(320)에서 영역(321)으로부터 추적되면, 프레임 N2(320)에서의 패치(333)의 상대적인 위치를 알 수 있다. 따라서, 위치 추정 장치(100)는 패치(333)의 프레임 N2(320)에서 파악된 상대적인 위치 정보를 이용하여 위치 추정 장치(100)의 절대 위치를 추정할 수 있다.

도 4는 패치 생성 방법의 일 예를 나타내는 도면이다.

도 1의 패치 생성부(142)는, 이전에 획득된 3D 포인트 클라우드 데이터 각각의 포인트에 대한 법선 벡터를 계산한다(142).

패치 생성부(142)는 각각의 법선 벡터를 구성하는 3차원 공간 좌표 (x, y, z)를 각각 RGB 값으로 설정하여, 각각의 법선 벡터를 RGB 영상으로 변환한다(420). 따라서, 생성된 RGB영상에서 R(Red), G(green) 및 B(Blue)는 각각 각 포인트에서의 법선 벡터의 방향을 나타낸다.

패치 생성부(142)는 변환된 RGB 영상을 그레이 영상으로 변환한다(430).

패치 생성부(142)는 그레이 영상에서 코너 추출 알고리즘을 이용하여 코너점을 추출한다(440). 해리스 코너 검출 등 알려진 다양한 방법으로 그레이 영상에서 코너점들이 추출될 수 있다. 노이즈 등으로 인하여 실제 코너가 아님에도 코너점으로 추출될 수 있으므로, 패치 생성부(142)는 추출된 코너점 중에서 특징점으로 적합한지 판단하고, 적합하다고 판단된 코너점을 특징점으로 추출한다(450). 예를 들어, 패치 생성부(142)는 추출된 코너점 주변의 포인트들의 법선 벡터의 변화도(gradient)가 일정 크기 이하이면, 특징점으로 적합하지 않은 것으로 결정할 수 있다.

추출된 특징점 주변의 포인트들은 패치로 결정되어 저장부(150)에 저장될 수 있다. 이때, 패치는 각각의 패치의 특징점의 위치 정보와 함께 저장될 수 있다. 또한, 패치를 저장할 때, 패치를 구성하는 포인트들 각각이 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분하여 저장할 수 있다. 패치에서 에지 포인트들 및 일반 포인트들을 구별하여 저장하면, 패치 추적 과정에서 이용되는 에지 기반 ICP 실행시 계산 시간이 단축될 수 있다.

도 5는 패치 추적에 의한 위치 추정 방법의 일 예를 나타내는 도면이다.

도 1의 위치 추정부(144)는 3D 포인트 클라우드 데이터의 각각의 포인트에서 법선 벡터를 계산한다(510).

위치 추정부(144)는 법선 벡터를 이용하여 3D 포인트 클라우드 데이터의 각각의 포인트가 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분한다(520). 예를 들어, 3D 포인트 클라우드 데이터의 포인트들의 법선 벡터의 변화가 일정 크기 이상 큰 위치에 존재하는 포인트들이 에지 포인트로 결정될 수 있다.

위치 추정부(144)는 에지 기반 ICP를 이용하여, 3D 포인트 클라우드 데이터에서 패치를 추적한다(530). 에지 기반 ICP 알고리즘은 패치의 에지 포인트는 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 패치의 일반 포인트는 에지 포인트와 일반 포인트 구별 없이 3D 포인트 클라우드 데이터와 매칭시킨다.

따라서, 위치 추정부(144)는 추적되는 패치들에 대하여, 패치를 구성하는 포인트들이 에지 포인트이지 일반 포인트인지를 구분한 다음, 3D 포인트 클라우드 데이터와 매칭을 수행할 수 있다. 패치를 구성하는 포인트들이 에지 포인트인지 일반 포인트인지를 구분하는 방법은, 3D 포인트 클라우드 데이터의 각각의 포인트들이 에지 포인트인지 일반 포인트인지를 구분하는 방법과 동일하다. 또한, 도 4와 관련된 설명에서와 같이, 패치를 저장할 때, 해당 패치를 구성하는 포인트들이 에지 포인트인지 일반 포인트인지 구별하여 저장하면, 위치 추정 과정에서, 패치를 구성하는 포인트들인지 에지 포인트인지를 구분하는 단계가 생략되므로, 처리 시간을 단축할 수 있다.

도 6a는 위치 추정 장치가 획득한 3D 포인트 클라우드 데이터 및 미리 등록된 패치의 일 예를 나타내는 도면이다.

도 6a에서, 도면 부호 610은 3D 포인트 클라우드 데이터를 2차원 형식으로 간략하게 나타낸 것이고, 도면 부호 620은 미리 등록된 패치를 마찬가지로 간략화하여 나타낸 것이다. 3D 포인트 클라우드 데이터(610)에서 포인트들(611, 612, 613)은 에지 포인트를 나타내고, 나머지 포인트들은 일반 포인트를 나타낸다. 패치(620)에서 포인트(621)는 에지 포인트를 나타내고, 나머지 포인트들은 일반 포인트를 나타낸다.

도 6b는 일반 ICP를 이용한 패치 추적 과정의 일 예를 나타내는 도면이다.

일반 ICP에서는 일반 포인트와 에지 포인트의 구별 없이 획득된 3D 포인트 클라우드 데이터와 미리 등록된 3D 포인트 클라우드 데이터의 매칭이 이루어진다. 따라서, 일반 ICP를 일 실시예에 따른 3D 포인트 클라우드 데이터와 패치간에 적용하게 되면, 도 6b에서 단계 1에서와 같이, 획득된 3D 포인트 클라우드 데이터와 미리 등록된 3D 포인트 클라우드 데이터 간에, 포인트들의 거리가 가장 가깝게 되는 위치로 매칭이 이루어진다. 따라서, 단계 2에서와 같은 잘못된 매칭 결과가 생성될 수 있다. 이와 같은, 잘못된 매칭 결과는 카메라의 방향에 따라서, 3D 포인트 클라우드 데이터가 일부 가려짐(occulusion)이 발생될 수 있기 때문이다.

도 6c는 일 실시예에 따른 에지 기반 ICP를 이용한 패치 추적 과정의 일 예를 나타내는 도면이다.

에지 기반 ICP를 적용하면, 획득된 3D 포인트 클라우드 데이터의 포인트들 및 패치를 구성하는 포인트들의 각각의 위치에서 법선 벡터가 계산되고, 법선 벡터를 이용하여 획득된 3D 포인트 클라우드 데이터 및 패치를 구성하는 포인트들 각각이 에지를 형성하는 에지 포인트들 및 에지를 형성하지 않는 일반 포인트들로 구분된다. 위치 추정부(144)는 패치의 에지 포인트는 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 패치의 일반 포인트는 에지 포인트와 일반 포인트 구별 없이 3D 포인트 클라우드 데이터와 매칭시킨다.

따라서, 도 6c의 단계 1에서와 같이, 우선 에지 포인트들이 가장 가깝게 되도록 매칭시키고, 단계 2에서와 같이, 일반 포인트들이 가장 가깝게 되도록 매칭시킨다. 그 결과로, 단계 3에서와 같이, 에지 포인트가 일치되는 매칭 결과가 생성될 수 있다. 이와 같이, 에지 기반 ICP 알고리즘을 적용하면, 일반적인 ICP 알고리즘에 비하여, 포인트 매칭시 더욱 정확한 매칭 결과를 얻을 수 있다. 따라서, 위치 추정의 정확도를 유지하면서, 위치 추정에 필요한 데이터 계산량을 감소시켜서, 위치 추정에 소요되는 시간을 감소시킬 수 있다.

본 발명의 일 양상은 컴퓨터로 읽을 수 있는 기록 매체에 컴퓨터가 읽을 수 있는 코드로서 구현될 수 있다. 상기의 프로그램을 구현하는 코드들 및 코드 세그먼트들은 당해 분야의 컴퓨터 프로그래머에 의하여 용이하게 추론될 수 있다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록 장치를 포함한다. 컴퓨터가 읽을 수 있는 기록 매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피 디스크, 광 디스크 등을 포함한다. 또한, 컴퓨터가 읽을 수 있는 기록 매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산 방식으로 컴퓨터가 읽을 수 있는 코드로 저장되고 실행될 수 있다.

이상의 설명은 본 발명의 일 실시예에 불과할 뿐, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 본 발명의 본질적 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현할 수 있을 것이다. 따라서, 본 발명의 범위는 전술한 실시예에 한정되지 않고 특허 청구범위에 기재된 내용과 동등한 범위 내에 있는 다양한 실시 형태가 포함되도록 해석되어야 할 것이다.

Claims

이동 로봇의 위치 추정 장치로서,
3D 포인트 클라우드 데이터를 획득하는 거리 데이터 획득부;
이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를 저장하는 저장부; 및
상기 획득된 3D 포인트 클라우드 데이터로부터 상기 복수 개의 패치를 추적하여, 상기 이동 로봇의 위치를 추정하는 위치 추정부를 포함하는 위치 추정 장치.
제1항에 있어서,
이전에 획득된 3D 포인트 클라우드 데이터로부터 적어도 하나의 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성하고, 생성된 패치를 상기 저장부에 저장하는 패치 생성부를 더 포함하는 위치 추정 장치.
제2항에 있어서,
상기 패치 생성부는, 상기 이전에 획득된 3D 포인트 클라우드 데이터 각각에 대한 법선 벡터를 계산하고, 상기 각각의 법선 벡터를 구성하는 3차원 공간 좌표 (x, y, z)를 각각 RGB 값으로 설정하여, 상기 각각의 법선 벡터를 RGB 영상으로 변환하고, 상기 변환된 RGB 영상을 그레이 영상으로 변환하고, 상기 그레이 영상에서 코너 추출 알고리즘을 이용하여 코너점을 추출하고, 상기 추출된 코너점 중에서 특징점을 추출하고, 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성하는 위치 추정 장치.
제2항에 있어서,
상기 패치 생성부는, 상기 패치를 각각의 패치의 특징점의 위치 정보와 함께 저장하는 위치 추정 장치.
제2항에 있어서,
상기 패치 생성부는, 상기 패치를 구성하는 포인트들이 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분하여 상기 저장부에 저장하는 위치 추정 장치.
제5항에 있어서,
상기 위치 추정부는,
상기 3D 포인트 클라우드 데이터의 각각의 포인트들에서 법선 벡터를 계산하고, 상기 법선 벡터를 이용하여, 상기 각각의 포인트들이 각각 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지를 구분하고, 상기 패치의 에지 포인트는 상기 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 상기 패치의 일반 포인트는 에지 포인트와 일반 포인트 구별 없이 상기 3D 포인트 클라우드 데이터와 매칭시키는 에지 기반 ICP 기반 알고리즘을 이용하여 상기 3D 포인트 클라우드 데이터로부터 상기 패치를 추적하는 위치 추정 장치.
제6항에 있어서,
상기 위치 추정부는,
상기 패치의 에지 포인트들은 가장 가까운 상기 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 상기 패치의 일반 포인트는 가장 가까운 상기 3D 포인트 클라우드 데이터의 포인트와 매칭시키는 위치 추정 장치.
이동 로봇의 위치 추정 방법으로서,
3D 포인트 클라우드 데이터를 획득하는 단계; 및
이전에 획득된 3D 포인트 클라우드 데이터로부터 추출된 특징점 주변의 포인트들을 포함하는 복수 개의 패치를, 상기 획득된 3D 포인트 클라우드 데이터로부터 추적하여 이동 로봇 위치를 추정하는 단계를 포함하는 위치 추정 방법.
제8항에 있어서,
상기 복수 개의 3D 클라우드 패치를 생성하는 단계를 더 포함하고,
상기 생성하는 단계는,
이전에 획득된 3D 포인트 클라우드 데이터로부터 적어도 하나의 특징점을 추출하는 단계;
상기 추출된 특징점 주변의 포인트들을 포함하는 패치를 생성하는 단계; 및
상기 생성된 패치를 저장하는 단계를 포함하는 위치 추정 방법.
제9항에 있어서,
상기 복수 개의 3D 클라우드 패치를 생성하는 단계는,
상기 이전에 획득된 3D 포인트 클라우드 데이터에 대한 법선 벡터를 각각 계산하는 단계;
상기 법선 벡터를 구성하는 3차원 공간 좌표 (x, y, z)를 각각 RGB 값으로 설정하여, 상기 각각의 법선 벡터를 RGB 영상으로 변환하는 단계;
상기 변환된 RGB 영상을 그레이 영상으로 변환하는 단계;
상기 그레이 영상에서 코너 추출 알고리즘을 이용하여 코너점을 추출하는 단계; 및
상기 추출된 코너점 중에서 특징점을 추출하는 단계를 포함하는 위치 추정 방법.
제9항에 있어서,
상기 생성된 패치를 저장하는 단계는, 상기 패치를 각각의 패치의 특징점의 위치 정보와 함께 저장하는 위치 추정 방법.
제9항에 있어서,
상기 생성된 패치를 저장하는 단계는, 상기 패치로부터 에지를 형성하는 에지 포인트들 및 에지를 형성하지 않는 일반 포인트들을 구별하여 저장하는 단계를 포함하는 위치 추정 방법.
제12항에 있어서,
상기 위치를 추정하는 단계는,
상기 3D 포인트 클라우드 데이터의 각각의 포인트에서 법선 벡터를 계산하는 단계;
상기 법선 벡터를 이용하여 상기 3D 포인트 클라우드 데이터의 각각의 포인트들이 에지를 형성하는 에지 포인트인지 에지를 형성하지 않는 일반 포인트인지 구분하는 단계; 및
상기 패치의 에지 포인트는 상기 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키고, 상기 패치의 일반 포인트는 에지 포인트와 일반 포인트 구별 없이 상기 3D 포인트 클라우드 데이터와 매칭시키는 에지 기반 ICP 기반 알고리즘을 이용하여 상기 3D 포인트 클라우드 데이터로부터 상기 패치를 추적하는 단계를 포함하는 위치 추정 방법.
제13항에 있어서,
상기 패치를 추적하는 단계는,
상기 패치의 에지 포인트를 가장 가까운 상기 3D 포인트 클라우드 데이터의 에지 포인트와 매칭시키는 단계; 및
상기 패치의 일반 포인트를 가장 가까운 상기 3D 포인트 클라우드 데이터의 포인트와 매칭시키는 단계를 포함하는 위치 추정 방법.