초록 ▼

가. 자연표식 인식 및 지도 작성
로봇이 위치인식을 하기위해 전역 지도를 필요로 한다. 여기서 전역 지도는 카메라를 통해 발견된 시각적 특징인 자연표식의 형태와 위치 정보이다. 영상 처리를 통해 시각적 특징을 구분할 수 있는 특징 기술자를 작성하고 자연표식 인식에 활용한다. 본 과제에서는 coner 형태의 영상 패턴을 검출하고 해당 영역에서 자연표식 특징을 추출하여 자연표식의 시각적 특징 기술자로 활용한다. 그리고 특징 기술자와 자연표식의 위치 정보를 포함하는 지도를 만들어 위치인식을 수행한다.
(1) 자연표식 특징 기술

가. 자연표식 인식 및 지도 작성
로봇이 위치인식을 하기위해 전역 지도를 필요로 한다. 여기서 전역 지도는 카메라를 통해 발견된 시각적 특징인 자연표식의 형태와 위치 정보이다. 영상 처리를 통해 시각적 특징을 구분할 수 있는 특징 기술자를 작성하고 자연표식 인식에 활용한다. 본 과제에서는 coner 형태의 영상 패턴을 검출하고 해당 영역에서 자연표식 특징을 추출하여 자연표식의 시각적 특징 기술자로 활용한다. 그리고 특징 기술자와 자연표식의 위치 정보를 포함하는 지도를 만들어 위치인식을 수행한다.
(1) 자연표식 특징 기술자
(가) 자연표식 특징점
입력 영상으로부터 자연표식 특징 포인트를 찾기 위해 coner 검출기를 사용한다. coner 검출기로 추출한 coner를 자연표식의 중심 포인트로 하고, 중심에서 일정 크기의 원형구간을 설정하여 이 영역을 자연표식 특징점으로 활용한다.
자연표식 특징점을 원형구간의 영상영역으로 설정하여 회전된 영상이 취득되어도 동일 구간이 표식으로 활용되도록 한다.
(나) 특징점 기술자
자연표식 특징점을 기술하기 위해 LBP(Local Binary Pattern) 코드를 사용한다. LBP는 기존에 사용되고 있는 SIFT와 같은 기법처럼 많은 연산량을 요구하지 않기 때문에 실시간으로 위치인식 알고리즘을 동작시키기에 유용하다. 그리고 영상의 각 화소 단위의 밝기 값을 사용하지 않고 주변 화소들과 밝기 차이 유무 정보를 이용하므로 조명변화가 큰 공간에서 적용하기에 유리하다. LBP 코드는 일정 구간의 영상내 화소 값들을 Binary Pattern으로 표현한 것이다. 그리고 Binary Pattern들의 발생 빈도수를 누적하여 히스토그램을 구성하고, 이를 특징 기술자로 사용한다.
본래 LBP는 회전된 영상에 대응할 수 없는 기법이기 때문에 위치인식과 같은 용도로 부적합하다. 본 과제에서 회전된 영상에도 적용할 수 있는 LBP 기법을 고안하여 적용한다. 지금부터 본 과제에 적용된 LBP 자연표식 특징 기술자에 대해 간단한 설명을 한다. 세부적인 기술 내용은 본론에서 다루는 것으로 한다.
그림 4 와 같이 원형의 자연표식 특징점을 두 개 이상의 동심 블록으로 나누고 각 동심 블록에 대한 LBP 히스토그램을 구한다. 모든 동심 블록에 대한 LBP 히스토그램을 연결시켜 하나의 자연표식 특징 기술자를 생성한다. 이 특징 기술자가 개개의 자연표식을 구분 짓는 특징으로 활용된다. 자연표식 영역을 다수의 동심 블록을 나누는 이유는 특징점에 대한 변별력을 크게 하기 위함이다. 다수의 히스토그램이 결합되면서 기술자의 차원이 동심 블록 개수만큼 커지고 그에 따라 특징점의 변별력이 높아진다. 변별력이 높아질수록 유사한 특징점들을 세밀하게 구분할 수 있다.
각 블록의 LBP 히스토그램은 블록 내 모든 화소의 LBP 코드 값들에 대한 분포로 구해진다. LBP 코드는 하나의 화소를 중심으로 이와 인접하는 모든 이웃화소의 밝기를 검출하여 중심 화소보다 어두운 이웃화소는 ‘0’으로 설정하고 그렇지 않은 나머지 이웃화소는 ‘1’로 설정한다. 이때 좌측상단을 기준으로 최하위 바이너리 비트를 할당하고 시계방향으로 단위가 증가하도록 바이너리 비트를 나열하여 LBP 패턴을 생성한다. 그림 5와 같이 LBP 패턴을 이진수로 하는 값이 LBP 코드 값이 된다.
LBP 히스토그램의 가로축은 각 LBP 코드 값을 의미하며 세로축은 각 LBP 코드가 발생한 개수(돗수)를 의미한다. 그림 4 와 같이 제 1 동심 블록, 제 2 동심 블록, 제 3동심 블록의 LBP 히스토그램을 결합하여 가로축의 크기가 세배로 늘어난 자연표식 특징점 기술자가 생성된다.
(2) 회전 불변 자연표식 특징 기술자
(가) LBP 패턴의 회전
로봇의 이동 방향 변화에 따라서 자연표식이 촬영되는 영상의 방향이 달라질 수 있다. 방향이 바뀌면 LBP 패턴의 바이너리 비트 배열이 회전하게 되어 LBP 코드 값이 변형 된다. 그 결과로 LBP 히스토그램 및 자연표식 특징점 기술자가 변화하므로 동일한 자연표식이 회전된 영상에서 다른 기술자로 표현된다. 따라서 로봇의 방향에 관계없이 일정한 값을 가지는 자연표식 특징점 기술자를 획득해야 한다.
그림 7과 같이 LBP 패턴 표현의 기준점을 영상의 회전에 맞추어 회전시키면 로봇의 방향 변화에 무관하게 동일 자연표식 동심 블록에 대한 동일한 LBP 코드를 구할 수 있다. LBP 패턴 표현의 기준점 기준은 해당 자연표식에 대한 고유의 값을 사용하도록 한다. 여기서 고유의 값으로는 자연표식의 방향을 적용한다.
자연표식의 방향은 자연표식 영상 구간의 이웃 화소 밝기차 분포 히스토그램을 이용하여 구할 수 있다. 히스토그램의 가로축은 이웃 화소의 방향 인덱스를 의미하고 세로축은 중심 화소와 이웃 화소의 밝기 차이 값을 누적한 값이다. 자연표식 영상 구간내의 모든 화소들에 대해 이웃 화소들과 밝기 차이를 계산하고 히스토그램의 각 이웃 방향에 대해 밝기 차이 값을 누적한다. 누적된 값이 가장 큰 방향 인덱스를 자연표식의 방향으로 결정한다.
자연표식 특징점 기술자를 구하는 과정에서 LBP 코드를 생성하기 위해 이웃화소와 밝기 차이를 계산하는 과정이 있으므로 자연표식 특징점 기술자 생성과 자연표식 방향 결정 두 가지 과정을 동시에 처리할 수 있다.
(나) 회전 불변 기술자
회전 불변 자연표식 기술자를 구하기 위해서는 LBP 패턴 표현의 기준점을 자연표식 방향을 기준으로 설정하고 새롭게 LBP 코드 및 히스토그램을 구해야 한다. 그러나 간단한 마스크 동작으로 기존에 구해진 자연표식 기술자를 회전 불변 자연표식 기술자로 변환 할 수 있다. 변환 마스크는 LBP 코드 패턴 회전의 일반화 수식을 통해서 구할 수 있다. 자세한 내용은 본문에서 다루기로 한다.
변환 마스크를 이용하여 히스토그램의 가로축을 재배열하면 LBP 패턴 기준점이 변경된 LBP 히스토그램을 구하게 된다. 각 블록에 대해 변환시킨 히스토그램을 결합하면 자연표식 방향을 기준점으로 작성된 회전 불변 자연표식 기술자가 완성된다.
(3) 자연표식 지도 작성
로봇이 이동하면서 연속된 카메라 영상을 취득하고 영상에서 검출된 자연표식 특징점을 저장한다.
자연표식의 특징점 기술자 외에도 자연표식의 절대위치를 기록하여 이 정보를 자연표식 지도로 사용한다. 로봇은 이 지도의 자연표식 특징점 위치와 로봇의 상대적인 위치 관계를 이용하여 위치 인식을 하게 된다.
(4) 자연표식 인식
로봇이 이동하면서 카메라로 영상을 취득하고 영상에서 취득된 자연표식은 회전 불변 특징 기술자의 형태로 자연표식 특징점 Database에 저장된다. 새로 영상이 취득될 때마다 발견된 자연표식 특징점은 Database의 특징 기술자와 비교하여 이전에 발견되었던 자연표식과 동일여부를 판단한다. 비교 대상인 두 특징 기술자의 유클리디안 거리가 일정 크기 이하인 경우 동일하다고 판단한다.
실제 환경에서 자연표식 특징은 매우 비슷한 형상을 가진다. 특히 천정을 향해 영상을 취득하는 경우, 매우 단조롭고 유사한 패턴이 반복되어 나타난다. 이런 경우에 특징 기술자는 동일한 형상을 기술하기 때문에 비슷한 값을 가지게 되는 경우가 많고 각 자연표식 특징점들의 매칭이 정상적으로 이루어지기 힘들다. 이런 상황에서 자연표식 특징점들의 correspondence를 확보하기 위해 POI(Point Of Interest) Matching 기법을 적용한다.
POI Matching은 기존에 발견되어 Database에 저장된 자연표식 특징점이 현재 영상에서 다시 발견될만한 위치를 미리 예측하여 해당 영역 내에서만 matching을 수행하는 방법이다.
로봇이 이동했을 때 로봇의 encoder 센서 정보로 미루어 대략적인 로봇의 위치를 추정한다. 추정된 로봇의 위치에서 영상을 새로 취득했을 때 영상프레임 내에서 발견될 가능성이 있는 자연표식 특징점을 Database에서 선별한다. 선별된 특징점이 나타날 가능성이 있는 영상프레임 내의 지점을 원형 구간으로 설정하고 이 구간을 POI 영역이라 한다. 영상의 POI영역 내에서 발견된 자연표식 특징점들을 POI에 해당하는 Database의 자연표식 특징점과 비교하여 동일 여부를 판단한다.
POI Matching을 적용함으로써 검출된 다수의 자연표식 특징점들에 대해 correspondence를 확보할 수 있고, 영상 전체 영역에 대한 matching 보다는 특정 구간에 대한 matching 작업을 수행하므로 matching 속도 개선을 가능하게 한다.
나. SLAM 알고리즘
(1) 위치인식 연구의 중요성
현재 실내 혹은 실외 환경에서 자율적으로 움직이는 서비스 로봇에 대한 연구가 점차 증가하고 있다. 이러한 서비스 로봇에 있어서 필수적인 기능으로는 자신의 위치가 어디인지 알아내는 것(localization)과 미지 환경을 알아내는 것(mapping)을 동시에 수행하는 SLAM 기술이다.
로봇이 아무런 사전 정보 없이 미지 환경에 놓였을 때 어떻게 자율적으로 움직일 것인가는 매우 중요한 부분이다. 즉 자율주행 로봇이 미지 환경은 임의의 위치에서부터 움직이게 된다면 어떻게 할 것인가? 이러한 경우 초기 위치부터 점진적으로 환경을 인식하여 환경 지도를 작성해야 할 것이다. 이와 동시에 계속적으로 작성되는 환경 지도를 이용하여 자신의 위치를 추정하여야 한다. 이러한 알고리듬을 Simultaneous Localization and Mapping (SLAM)이라 하며 이에 대한 연구가 활발히 이루어지고 있다. 대표적인 SLAM 알고리듬으로는 EKF-SLAM과 FastSLAM 등이 있다.
(2) SLAM 알고리즘
Simultaneous Localization and Mapping (SLAM)은 그림 13과 같이 Localization과 Mapping을 동시에 수행하는 것인데, 자율 이동로봇에게는 필수적인 기술이다.
지금까지 SLAM을 해결하기 위해 제안된 방법 중 가장 대표되는 것이 EKF-SLAM 이다. EKF-SLAM은 현재까지 많은 연구가 이루어져 있고, 실제 환경의 on-line상에서 원만한 동작을 하고 있다. 하지만, EKF-SLAM은 계산량이 landmark 개수에 대해서 2차 함수적으로 증가하기 때문에 계산량 부담이 크며, single data association 방식을 사용하므로 landmark의 data association이 잘못될 확률이 매우 높으며, 그 영향이 SLAM 결과에 치명적이다. 최근Particle filter가robotics 분야에서 핵심적인 위치를 차지하고 있으며, 많은 연구에 사용되고 있다. 특히, SLAM 분야에서는 기존의 EKF-SLAM의 단점을 극복하기 위해 particle filter가 사용된 FastSLAM 연구가 활발히 진행 중이다.
(3) FastSLAM 알고리즘
FastSLAM 알고리듬은 기존의 EKF-SLAM 알고리듬과는 다르게 particle filter를 이용한 방법으로 EKF-SLAM에 비해 많은 장점이 있다. 먼저 EKF-SLAM의 경우 landmark수가 증가함에 따라 computational complexity가 quadratic하게 증가하는 반면 FastSLAM은 conditional independency를 이용하여 map feature를 효율적으로 추정하므로 computational complexity가 logarithmic하게 증가한다. 각각의 개별적인 feature에 대해 추정을 하므로 dimension을 크게 낮출 수 있어서 curse of dimensionality 문제를 보완할 수 있다. 또한 EKF-SLAM은 single-hypothesis data association을 기반으로 하는 반면 FastSLAM의 경우 multiple-hypothesis data association을 기본으로 하므로 EKF-SLAM에 비해 외란 등에 강인하다.
FastSLAM 알고리듬이 사용하는 Particle filter는 연속적인 분포들을 불연속적인 particles 혹은 samples로 나타내는 것이다. 즉, Gaussian과 같이 분포의 평균과 분산의 parameter로 나타내는 것이 아니라 불연속적인 여러 개의 particle들로 나타내는 것이다.
Particle filter는 particle 개수가 증가함에 따라 계산 량이 지수 함수적으로 증가하기 때문에 on-line 성을 요구하는 SLAM에 직접 적용될 수는 없다. 따라서 SLAM의 특성을 이용하여 on-line에서도 SLAM을 할 수 있는 FastSLAM이 Montemerlo에 의해 개발되었다. FastSLAM의 핵심이 되는 SLAM 확률 분포의 분리화(factorization)는 다음 수식과 같다.
여기서 FastSLAM은 Rao-Blackwellized particle filter를 이용한 SLAM의 한 방법이다. 위 수식에서 SLAM 확률 분포가 로봇 경로와 환경 map확률 분포로 분리되는 것은 Rao-Blackwellized Particle Filter를 사용함으로써 가능하고, map 확률분포가 각각의 landmark의 확률분포의 곱으로 나타나는 것은 SLAM 문제를 그림 14와 같은 SLAM network으로 나타낼 수 있기 때문이다. 수식에서 로봇의 경로 혹은 위치의 확률 분포는 particle filter를 이용하여 추정하고, map 정보는 각각의 landmark별로 2by 2 EKF를 이용하여 추정한다.
그림 14에서 landmarks간에는 직접적인 관계가 없고, 오직 로봇 경로를 통해서만 관계 지어져 있다. 이것을 conditional independence라 하는데, 이를 이용하면 전체 map정보의 확률 분포는 각각의 landmark의 곱으로써 나타낼 수 있다.
본 과제에서는 영상처리를 통해 인식된 자연표식을 landmark로 이용하고, FastSLAM 알고리즘을 활용하여 로봇의 위치인식 기능을 구현한다.
다. 영상 보드
위치인식 기술을 독립적인 모듈로 개발하기 위해 영상 솔루션 전용의 특화된 보드를 제작한다. 로봇의 단가를 낮추어 로봇 보급 확산이 가능하도록 저가 센서를 이용한 단순한 하드웨어 구성을 갖추도록 한다. 또한 저 전력 설계기술 개발을 통해 이동 로봇의 전력 사용 효율을 높이도록 한다. 과제를 통해 제작한 영상보드는 저가의 CMOS 카메라를 사용하며 500mW 전력을 소비하는 수준으로 설계되었다. CPU로는 ARM11(532MHz)을 채택하였으며, 512MB RAM, 512MB FLASH 메모리, 1.3M CMOS Camera, USB 및 Serial 통신 모듈 등의 구성으로 설계 및 제작하였다. 영상 솔루션에 특화되도록 개발하였기 때문에 위치인식 소프트웨어 뿐 아니라 다양한 영상 관련 소프트웨어 솔루션에 활용 될 수 있다.

목차 Contents

• 표지 ...1
• 제출문 ...3
• 요약문 ...5
• 목차 ...25
• 제1장 서론 ...32
• 제1절 위치인식 기술의 배경 및 최근 연구동향 ...32
• 1. 기술의 개요 및 배경 ...32
• 가. 위치인식 개요 ...32
• 나. Vision based SLAM 개발 배경 ...32
• 2. 국내외 기술동향 및 전망 분석 ...33
• 가. 기술 동향 ...33
• (1)국내 기술동향 ...33
• (2)해외 기술동향 ...34
• 나. 위치인식 상용기술 ...35
• 다. 전망 ...38
• 제2절 기술개발 목적 및 중요성 ...40
• 1. 기술개발 목적 ...40
• 2. 기술개발의 중요성 ...40
• 가. 기술적 중요성 ...40
• 나. 경제적 중요성 ...41
• 제3절 위치인식 기술의 시장성 ...43
• 1. 시장동향 ...43
• 가. 국내시장 동향 ...43
• 나. 세계시장 동향 ...44
• 2. 시장전망 ...45
• 제2장 자연표식 인식 및 지도 작성 ...47
• 제1절 자연표식 특징 기술 ...48
• 1. Coner 검출기 ...48
• 2. 자연표식 영역설정 ...49
• 3. LBP 패턴 인식 ...50
• 가. LBP ...50
• (1) LBP Operator ...50
• (2) LBP 히스토그램 ...51
• 나. CS-LBP ...53
• (1) CS-LBP Operator ...53
• (2) CS-LBP 히스토그램 ...54
• 4. 자연표식 기술자 ...55
• 가. CS-LBP 자연표식 기술자 ...55
• 나. 회전 불변 히스토그램 블록 ...55
• 5. 자연표식 기울기 ...58
• 제2절 회전 불변 특징 기술자 ...60
• 1. 회전 불변 LBP ...60
• 가. LBP 패턴의 회전 ...60
• 나. 회전 불변 LBP...60
• 2. LBP 히스토그램 변환 ...61
• 가. 변환 마스크 ...61
• (1) LBP 패턴의 회전 변화 일반화 ...61
• (가) 반시계 방향 기준점 변경 ...61
• (나) 시계 방향 기준점 변환 ...62
• (2) 변환 마스크 ...63
• 나. 회전 불변 자연표식 기술자 ...64
• 제3절 자연표식 지도 작성 ...66
• 1. 국부지도 ...66
• 2. 전역지도 ...67
• 제4절 POI matching ...69
• 1. 자연표식 인식 ...69
• 2. POI matching ...70
• 제3장 확률기반 SLAM 알고리즘 ...72
• 제1절 Localization and Mapping ...72
• 1. Localization ...72
• 2. Mapping ...74
• 제2절 SLAM ...76
• 1. SLAM 개요 ...76
• 2. SLAM 알고리즘 ...76
• 3. FastSLAM ...77
• 가. Particle Filter ...77
• 나. FastSLAM 알고리즘 ...79
• (1) Particle Set 구조 ...79
• (2) FastSLAM의 4단계 ...79
• 제4장 영상보드 ...82
• 제1절 영상보드 Specification ...83
• 1. 하드웨어 구성 ...83
• 2. 보드 크기 ...84
• 3. 사용 전류 및 시간 ...84
• 4. 부속품 ...85
• 제2절 하드웨어 제작 ...86
• 1. 하드웨어 구성 부품 ...86
• 가. Main board ...86
• 나. Debug board ...88
• 2. 하드웨어 회로도 ...90
• 가. 카메라 모듈 ...90
• 나. GPIO 모듈 ...91
• 다. I2C Serial 모듈 ...92
• 라. Memory 모듈 ...95
• 마. Power 모듈 ...97
• 바. JTAG 모듈 ...99
• 사. USB OTG 모듈 ...100
• 제5장 소프트웨어 구현 ...101
• 제1절 자연표식 인식 소프트웨어 ...101
• 1. 소프트웨어 구조 ...101
• 가. 전체 구조 ...101
• (1) 비전 라이브러리 구조 ...101
• (가) Application Interface Layer ...102
• (나) Vision Core Layer ...102
• (2) 플로우 차트 ...103
• (가) 자연표식 검출, 인식, 등록 ...103
• (나) 자연표식 지도 갱신 ...104
• 나. 세부 모듈 ...105
• (1) DetectLM Class ...105
• (가) Vision Core 접근 API ...105
• (나) 자연표식 데이터 접근 API ...105
• (다) 환경 설정 API ...106
• (라) 내부 함수 ...106
• (2) Feature Detection ...107
• (3) Feature Description ...107
• (4) Feature Matching ...108
• (5) Feature Map Building ...109
• 2. 비전 라이브러리 구현 내용 및 매뉴얼 ...110
• 가. DetectLM 클래스 ...110
• (1) ObserveLandmark ...110
• (2) UpdateLandmark ...111
• (3) GetNumLandmarkNew ...112
• (4) GetNumLandmarkMatched ...112
• (5) GetNumLandmarkCurrentAll ...112
• (6) GetLandmarkNew ...113
• (7) GetLandmarkMatched ...113
• (8) SetCeilingHeight ...114
• (9) SetCandidRegionRadius ...114
• (10) SelectFeatures ...114
• 나. Feature Detection ...115
• (1) Corner_detect ...115
• 다. Feature Description ...116
• (1) feature_description ...116
• 라. Feature Matching ...116
• (1) Feature_matching_DataAssoc ...117
• (2) feature_matching_POI ...117
• (3) find_POI ...119
• (4) match_POI_curF_CR ...119
• (5) mapping_one_POI_to_one_curF ...120
• 마. Feature Map Building ...121
• (1) new_feat_global_mapping ...121
• (2) revise_new_feat_global_map ...122
• 제2절 SLAM 알고리즘 소프트웨어 구현 ...123
• 1. 소프트웨어 구조 ...123
• 가. 전체 제어구조 ...123
• (1) 블록 다이어그램 ...123
• (2) 플로우 차트 ...124
• 나. 세부 제어구조 ...125
• (1) FastSLAM 알고리즘 모듈 블록 다이어그램 ...125
• (2) FastSLAM 알고리즘 모듈 플로우 차트 ...126
• 2. FastSLAM 소프트웨어 구현 내용 및 매뉴얼 ...128
• 가. Robot Control 모듈 ...128
• (1) GetPose ...128
• (2) CorrectEncoder ...129
• (3) GetVel ...129
• 나. FastSLAM 알고리즘 모듈 ...130
• (1) ParticleFiltering ...131
• (2) GetGaussSample ...131
• (3) Choldc ...132
• (4) NormalRandom ...133
• (5) PredictPose ...133
• (6) GetNumP ...134
• (7) Predict ...134
• (8) AddMotionNoise ...135
• (9) pi_to_pi ...135
• (10) ComputeJacobians ...136
• (11) SetupSampling ...136
• (12) Sampling ...137
• (13) ComputeKDA ...137
• (14) ComputeWeight ...138
• (15) ComputeESS ...139
• (16) Resampling ...139
• (17) AddFeatures ...139
• (18) UpdateFeatures ...140
• (19) KF_update ...141
• 다. Definition 및 행렬 계산 모듈 ...141
• (1) Definition ...141
• (2) 행렬 계산 모듈 ...143
• 제6장 결론 ...145
• 제1절 개발결과 ...145
• 1. 자연표식 인식 성능 ...145
• 2. SLAM 모듈 ...148
• 3. 지적재산권 ...149
• 제2절 활용 및 기대효과 ...150
• 1. 활용방안 ...150
• 2. 기대효과 ...151
• 제3절 상용화 계획 ...153
• 1. 환경 및 시장 분석 ...153
• 가. 시장의 특징 ...153
• 나. 시장 수요 및 동향 분석 ...154
• 2. 관련 제품 분석 ...156
• 3. 비즈니스 전략 ...157
• 가. 목표시장 및 고객 ...157
• 나. 기존시장 확대 ...158
• 다. 신규시장 창출 ...158
• 라. 매출 예상 ...158
• 4. 경쟁우위 확보 전략 ...159
• 5. 사업화 애로사항 ...159
• 참고문헌 ...160