PTAM(Parallel Tracking and Mapping)과 PTAMM

영상처리 2014.03.30 22:38

PTAM(Parallel Tracking and Mapping)은 2007년 영국 옥스포드 대학의 Active Vision Group에서 발표한 기술로서 해당 논문이 ISMAR 2007 학회에 발표된 이후로 기존의 Visual SLAM 연구 흐름이 바뀔 정도로 지대한 관심을 받아온 기술입니다 (논문 피인용 건수만 1020회).


PTAM을 이용하면 손으로 들고 찍은 단일 카메라 영상으로부터 3D 공간이 실시간으로 구축되면서 카메라의 시점이 복원되고 매끄러운 증강현실(Augmented Reality)이 가능할 정도의 정밀한 카메라 위치추적이 가능해 집니다.


<PTAM 데모 동영상>


본 포스팅에서는 PTAM 기술의 핵심 개념과 관련 자료, 그리고 PTAM 기술의 확장판으로 볼 수 있는 PTAMM 기술에 대해 간략히 정리해 보고자 합니다.



1. 관련 자료


[PTAM] Parallel Tracking and Mapping


[PTAMM] Parallel Tracking and Multiple Mapping



2. PTAM (Parallel Tracking and Mapping)


PTAM을 한 마디로 설명하자면 키프레임(key frame)을 이용한 Visual SLAM(Simultaneous Localization and Mapping) 기술로 볼 수 있다.


☞ 키프레임이란 비디오를 압축할 때 전체 이미지가 저장되는 프레임을 의미한다. 비디오는 일련의 연속된 영상프레임으로 구성되는데, 모든 장면 장면을 전체 이미지로 저장하면 용량이 너무 커지기 때문에 변화가 큰 장면이나 일정 시간 간격으로만 전체 이미지를 저장하고 그 사이의 장면은 변화되는 정보만 저장하는 비디오 압축 기법이 사용된다. 이 때, 전체 이미지가 저장되는 영상프레임을 키프레임이라 부르는데 유투브 동영상의 경우에는 약 2초 간격으로 키프레임이 배치된다.


☞ SLAM(Simultaneous Localization and Mapping) 기술은 주로 로보틱스 분야에서 오래동안 연구되어온 분야로서 미지의 공간에서 맵(map)을 생성하는 문제와 자신(로봇)의 위치를 파악하는 문제를 동시에 푸는 방법론을 연구하는 분야이다. 자신이 어떤 낯선 외국의 도심 한복판에 서 있는 경우를 생각해 보자. 이 때, 만일 눈앞의 건물중 하나라도 아는 건물이 있으면 자신의 위치를 쉽게 파악할 수 있을 것이다 (localization). 반대로, 자신의 위치를 알고 있다면 눈앞의 낯선 건물들이 어떤 건물인지 쉽게 알 수 있게 된다 (mapping). 또 하나의 예를 더 들어보면 자신이 어떤 낯선 미로같은 갱도(굴)에 던져졌다고 생각해 보자. 처음에는 자신이 어디에 있는지 갱도의 구조가 어떻게 되어 있는지 전혀 모르는 상태이다. 그러다 여기저기 탐색하면서 차츰 머리속에 갱도에 대한 맵이 형성될 것이고 맵이 완성되면 갱도를 탈출할 수 있게 될 것이다. 그런데, 눈앞의 길이 아까 왔던 곳인지 아니면 새로운 길인지 햇갈리게 되면 그 때부터 맵 생성 자체가 엉망이 될 것이고 길을 잃어버리게 될 것이다. 즉, 맵을 생성하는 문제와 맵 상에서 자신의 위치를 파악하는 문제는 서로 맞물려 있는 문제이기 때문에 이를 동시에 풀고자 하는 것이 SLAM(Simultaneous Localization and Mapping) 기술이다. SLAM은 다양한 센서를 이용하여 이루어질 수 있는데, 그 중 카메라 영상을 이용한 SLAM을 Visual SLAM이라 부르고 그중 특히 단일(single) 카메라를 이용한 경우를 mono SLAM이라 부른다 (mono SLAM은 영국 임페리얼 칼리지의 Andrew Davison이 대표적인 연구자이다. 홈페이지: http://www.doc.ic.ac.uk/~ajd/, 논문: "MonoSLAM: Real-Time Single Camera SLAM", PAMI 2007).


기존의 Visual SLAM에서는 영상에서의 특징점 매칭을 통해 카메라의 위치를 추적하고 이들 특징점들에 대한 3차원 맵을 생성한다. 그런데 기존의 Visual SLAM 방법들은 이러한 특징점 매칭 및 맵 갱신이 모든 영상 프레임에 대해서 이루어지기 때문에 처리속도가 느리고 또한 처리 속도가 느리기 때문에 정밀한 알고리즘을 사용하기 힘든 문제점이 있었다.


그런데, PTAM에서는 카메라의 위치를 추적하는 tracking 부분과 특징맵을 생성하는 mapping 부분을 서로 분리시켜서 별도의 쓰레드(thread)로 parallel하게 돌린다. 그래서 둘 사이의 종속성을 없애고 실시간성과 정확도를 동시에 만족시킬 수 있는 새로운(획기적인) 방법을 사용한다. 그 핵심 아이디어는 비교적 연산로드가 적은 카메라 tracking은 모든 영상프레임에 적용하여 실시간성을 추구하고, 맵 갱신은 주요 키프레임에만 적용하되 시간이 오래 걸리더라도 정밀한 알고리즘을 사용하여 정확도를 추구한 점에 있다.


PTAM의 tracking 모듈에서는 현재까지 구축된 특징맵 정보와 입력 영상을 매칭하여 카메라의 위치(3차원 위치 및 자세)를 실시간으로 추적하는 일을 수행한다. PTAM의 tracking 과정을 요약하면 다음과 같다. 먼저, 카메라로부터 새로운 입력 영상이 획득되면 입력영상의 특징점(FAST-10)과 맵 상의 특징점을 매칭한다. 매칭 유사도로는 8x8 이미지 패치 사이의 SSD(Sum of Squared Difference)를 이용한다. 그리고 매칭이 완료되면 찾아진 매칭쌍들에 대해 reprojection error를 최소화시키도록 카메라의 위치를 결정한다. Reprojection error란 매칭된 맵 특징점을 현재의 카메라 영상에 투영시킨 위치와 입력 영상에서 실제로 관측된 위치 사이의 에러를 의미한다.


PTAM의 매핑(mapping) 모듈에서는 tracking 모듈에서 제공하는 키프레임 이미지들을 맵에 추가하면서 3차원 특징맵을 생성해 나간다. 이러한 PTAM의 매핑 단계는 크게 초기맵 생성단계와 맵 확장/갱신 단계로 구분할 수 있다.


<PTAM 초기맵 생성>


초기맵 생성은 사용자의 직접적인 도움을 통해 이루어지는데, 처음에 카메라를 고정시킨 상태에서 시작 버튼을 누른 후 카메라를 평행하게 일정거리만큼 이동시키고 다시 종료 버튼을 누르면 시작 시점과 종료 시점의 두 이미지를 매칭하여 초기 맵을 생성한다. 좀더 구체적으로 보면 먼저 시작 시점의 이미지로부터 FAST-10 특징점을 추출한 후, 사용자가 카메라를 이동시키는 동안 이 특징점들을 계속해서 추적한다. 그래서 종료 시점에서 추적된 위치와 시작 시점의 위치에 대해 5-point 알고리즘을 적용하여 특징점들의 3D 좌표를 계산해 낸다. [영상 Geometry #7] Epipolar Geometry 글에서 설명한 바와 같이 이론적으로 서로 다른 두 시점에서 획득한 두 이미지에 대해 5개 이상의 매칭쌍이 있으면 두 카메라 시점 사이의 3차원 관계 및 매칭점들의 3D 위치를 복원할 수 있다. 단, 이렇게 구성한 공간의 스케일(scale)은 결정할 수 없는 문제가 있는데, PTAM에서는 스케일 문제를 해결하기 위해 사용자가 시작 시점과 종료 시점 사이에 이동시킨 거리를 10cm라 가정하고 이에 맞추어 공간의 스케일을 결정하는 방법을 사용한다.


PTAM의 맵은 위와 같이 초기에는 두 개의 키프레임 이미지로만 구성되지만 이후 카메라가 이동함에 따라 새로운 키프레임들이 추가됨으로써 맵이 확장 갱신된다. 이 때, 맵에 새로 추가되는 키프레임들은 다음의 3가지 조건을 모두 만족하는 경우에 한한다. i) 해당 프레임에서의 tracking 품질이 좋아야 한다 (tracking 모듈에서 매칭된 특징점의 비율이 특정 임계값 이상). ii) 가장 최근에 맵에 추가된 영상프레임과 최소 20프레임 이상 시간 차이가 나야 한다. iii) 카메라와 기존 맵과의 최단거리가 특정 임계값 이하여야 한다. 조건 iii)은 기존 맵과 너무 멀리 떨어진 시점에서 찍은 영상을 맵에 추가할 경우 기존 맵이 깨질 수 있기 때문에 이를 방지하기 위함이다.


☞ PTAM의 맵을 확장하기 위한 조건 i),ii),iii)를 좀더 직관적으로 생각해 보면 다음과 같다. 먼저, 현재 카메라 영상이 키프레임으로서 맵에 추가되었다고 하자. 그런데, 현재 위치에서 카메라를 움직이지 않고 가만히 있다면 굳이 똑같은 영상들을 맵에 추가할 필요는 없다. 그러다가 카메라가 움직이기 시작하면 즉, 시점에 변화가 생기면 일정값 이상의 시점 변화가 생길때마다 이미지들을 키프레임 영상으로 맵에 추가한다. 위 조건 i)~iii)은 이러한 목표를 달성하기 위한 하나의 방법일 뿐이다. 그리고, PTAM에서 말하는 키프레임 영상이란 동영상 압축에서 말하는 키프레임의 의미라기 보다는 시점이 서로 구분되는 이미지들을 의미한다.


위와 같이 새로운 키프레임이 추가되면 PTAM의 매핑 모듈에서는 bundle adjustment라는 과정을 통해 맵을 갱신하고 최적화한다. 사실 PTAM 맵은 현재까지 추가된 키프레임 이미지들과 각 키프레임 이미지에 대한 카메라 시점(위치) 정보, 그리고 이 키프레임 이미지들 사이의 서로 매칭된 특징점들에 대한 3차원 좌표로 구성되어 있다. 이 때, Bundle adjustment는 맵 상의 3차원 포인트들을 키프레임 이미지들에 투영(projection)시킨 위치와 해당 영상 프레임에서 실제 관측된 위치의 차이 즉, reprojection error를 최소화시키도록 3차원 포인트의 위치 및 카메라의 위치를 최적화하는 과정을 지칭하는 용어이다. 여기서 'bundle'이라는 용어는 우리말로 번역하면 '묶음'이라는 의미인데, 한 포인트에 대한 reprojection error가 아니라 여러 포인트들의 (그리고 여러 카메라 시점에 대한) reprojection error를 (묶음으로) 동시에 최소화시킴을 나타낸다.


논문에도 나와 있지만 PTAM은 사무실 책상 위 등과 같이 비교적 소규모의 제한된(bounded), 그리고 고정된(not deformable) 공간에 적합한 방법이다. 따라서 카메라가 복도를 따라서 이동하는 경우나 공간의 규모가 너무 큰 경우에는 적용하기 힘든 문제점을 갖는다. 여기서 공간의 크기라 함은 실제 물리적인 공간의 크기라기 보다는 카메라의 시점이 움직일 수 있는 범위를 지칭한다고 하는 것이 보다 정확한 표현이다. 아무리 넓은 공간이라 하더라도 카메라가 공간의 한쪽 면만을 바라본다면 카메라의 시점 변화가 제한적이기에 PTAM을 적용하기 좋은 문제가 된다. 반면에 좁은 방 안이라 할지라도 방 중앙에 서서 방 전체를 상하좌우로 둘러보는 경우라면 카메라의 시점 변화의 폭이 커지기 때문에 PTAM을 적용하기 힘들수 있다.



3. PTAMM (Parallel Tracking and Multiple Mapping)


PTAMM은 PTAM이 나온지 1년 후인 2008년도에 같은 연구그룹에서 발표된 기술로서, 그 이름에서 알 수 있듯이 PTAM을 멀티 맵에서 동작할 수 있도록 확장한 버전이다. 개인적으로는 논문을 읽기 전까지만 해도 PTAMM을 PTAM의 단순한 확장판 정도로만 생각했다. 하지만 논문을 읽고 난 후, PTAMM에는 기존의 PTAM을 어떻게 하면 실제 응용들에 좀더 써먹을 수 있는 기술로 만들 수 있을까 하는 고민과 노력들이 고스란히 녹아들어 있음을 알 수 있었다.


<PTAMM 데모 동영상>


PTAMM은 기존의 PTAM의 가장 큰 단점인 그 적용이 소규모의 공간에 제한된다는 문제에 대한 하나의 해결책으로 볼 수 있다. PTAMM에서 이 문제를 푼 방식은 다음과 같다.


PTAM에서는 자신의 책상 앞 또는 실내 공간의 한쪽 면 등과 같이 제한된 공간에 대한 하나의(single) 맵을 생성하고 그 공간 내에서 카메라의 움직임(위치)을 추적할 수 있는 방법을 제공한다. 그런데, 공간의 크기가 커지고 맵이 커지면 컴퓨팅 파워의 한계로 인해 맵을 유지하기 힘든 한계를 갖는다. PTAMM에서는 이러한 문제를 근본적으로 해결하기 위한 방법으로 하나의(single) 맵이 아닌 여러(multiple) 개의 맵을 독립적으로 생성하여 적용하는 방법을 사용한다. 즉, 자신의 책상 앞 공간에 대한 맵, 동료 A의 책상에 대한 맵, 동료 B의 책상에 대한 맵, 사무실 내부 공간에 대한 맵, 휴게실에 대한 맵, ... 등과 같이 각각의 소규모 공간들을 별도의 맵으로 생성하고 각각을 파일로 저장한다. 이렇게 맵을 모두 생성한 후 나중에 카메라를 들고 사무실 내부를 지나가다가 동료 A의 책상앞에 다다르면 동료 A의 책상 공간에 대한 맵이 활성화(로드)되고 동료 B의 책상앞에 다다르면 동료 B의 책상 공간에 대한 맵이 활성화된다.


이를 좀더 기술적으로 들어가 보면, 처음에 자신의 책상 앞에서 카메라를 들고 있을 때에는 이 공간 내에서 카메라의 위치가 정확하게 추적되면서 필요한 AR(증강현실) 작업들이 동작한다. 그러다가 자리를 벗어나서 다른 곳으로 이동하면 카메라 위치 추적이 실패하면서 카메라의 위치를 복원하고자 하는 노력을 계속한다. 하지만 현재 카메라 시야에 들어오는 공간은 미리 매핑된 공간이 아니기에 카메라의 위치추적은 계속해서 실패한다. 그러다 미리 매핑된 동료 A의 책상앞에 다다르면 매칭이 성공하면서 이 공간 내에서의 카메라의 위치가 복원되고 다시 정상적인 위치추적이 이루어진다.


☞ PTAMM에서는 매핑된 공간들 사이의 어떤 기하학적 관계도 가정하지 않는다. 즉, 자유롭게 자신이 원하는 장소마다 맵을 생성하면 그뿐, 생성된 맵들 사이의 기하학적 관계를 맞출 필요가 전혀 없다는 의미이다. 사실 기존에도 맵을 소규모의 맵으로 분할하여 처리하고자 하는 시도들을 꾸준히 있어왔다. 하지만 기존에는 소규모의 맵으로 분할할 때, 어떻게 하면 이들 사이의 기하학적 관계를 정확히 알아낼 것인가에 연구의 초점이 모아졌고 이러한 제약으로 인해 그 활용성 또한 제한이 되었다. 하지만 PTAMM에서는 맵 간의 기하학적인 관계를 아에 무시해 버린다. 그렇게 함으로써 어디든지 사용자가 원하는 대로 자유롭게 맵을 만들수 있도록 한다. 또한 맵 간의 상호 의존성이 없기 때문에 맵을 새로 추가하거나 삭제, 수정하는 것이 무척 자유롭다. 이러한 PTAMM의 특성은 아이러니하게도 그 응용을 제한하기 보다는 오히려 보다 폭넓은 응용을 가능케 한다. 한 예로, 박물관 내부의 각 코너마다 맵을 생성하고 카메라를 들이대면 해당 코너에 맞는 증강현실(AR)이 구현되는 응용을 생각할 수 있다. 공룡의 뼈가 전시된 코너에 카메라를 대면 공룡의 외형이 복원된 영상이 보여지고 카메라의 시점에 따라 다양한 각도에서 공룡의 모습을 살펴볼 수 있는 상황을 상상해 보자.


이러한 멀티 맵을 이용한 모든 응용이 가능하기 위한 전제조건은 카메라가 각각의 맵 영역에 들어섰을 때 카메라의 시점이 안정적으로 복원되야 한다는 것이다. 즉, 현재 카메라가 미리 매핑되어 있는 공간 내에 있는지 아니면 전혀 낯선 공간에 있는지, 만일 사전에 매핑된 공간에 있다면 어떤 맵 공간에 있는지, 그리고 그 공간 내에서 현재 카메라의 위치가 어디인지를 정확히 알수 있어야 한다는 얘기이다. PTAMM에서는 이 문제를 1/8 크기의 저해상도로 축소된 이미지 사이의 SSD(Sum of Squared Difference) 매칭을 통해 해결한다. 즉, 현재의 카메라 영상을 1/8로 축소한 영상과 맵에 저장되어 있는 키프레임 영상들을 1/8로 축소한 영상을 비교하여 가장 유사도가 높은 키프레임을 찾는다. 그리고 찾아진 키프레임이 포함된 맵을 현재의 맵으로 인식하고 카메라의 위치는 찾아진 키프레임의 위치로 초기화된다. 이렇게 카메라의 위치가 복원되면 이후에는 정상적인 tracking 과정이 진행된다. 만일 맵 및 키프레임이 제대로 매칭되었다면 이후의 tracking은 정상적으로 잘 진행될 것이고 만일 매칭이 잘못되었다면 tracking이 곧바로 실패할 것이다. 만일 tracking이 실패하면 맵을 잃어버린 것으로 간주하고 다시 시점이 복원될 때까지 탐색 작업을 반복한다.


☞ 저해상도 이미지 매칭을 통한 시점 복원 과정을 이해하기 위해서는 PTAM과 PTAMM에서 사용하는 맵에 대한 이해가 필요하다. PTAM과 PTAMM에서 하나의 맵은 일련의 키프레임 이미지들과 이 키프레임 이미지들로부터 추출된 3차원 특징점들로 구성된다. 그런데 여기서 키프레임이라 함은 앞서 말한 바와 같이 동영상 압축에서 말하는 키프레임이라기 보다는 시점이 서로 구분되는 이미지들을 의미한다. 따라서, 다양한 시점에 대하여 키프레임 이미지들이 맵에 촘촘히 추가되어 있다면 단순한 저해상도 SSD 이미지 매칭만으로도 현재 카메라 영상과 매칭되는 키프레임 영상을 안정적으로 찾을 수 있게 된다.



4. PTAM/PTAMM 소스코드 컴파일하기


PTAM/PTAMM에 대한  공개 소스코드를 컴파일하는 방법에 대해서는 PTAM/PTAMM 컴파일하기 글을 참고하기 바랍니다.



5. 맺음말


개인적으로 PTAM, PTAMM은 정말  좋은 기술이라고 생각합니다. 그 가장 큰 이유는 그들이 기존의 이론의 틀에 머무르지 않고 현실 세계와 접목된, 실제 써먹을 수 있는 기술이 되기위한 해법을 추구하고 또 제시했기 때문입니다.


by 다크 프로그래머


  • 밥버러지 2014.03.31 16:05 신고 ADDR 수정/삭제 답글

    와... 국내에 PTAM, PTAMM에 대해 이정도의 깊은 이해를 가지고 계신 분이 몇이나 있을까요... 잘 보고 갑니다. 감사합니다.

  • 2014.06.02 10:58 ADDR 수정/삭제 답글

    비밀댓글입니다

    • BlogIcon 다크pgmr 2014.06.04 08:51 신고 수정/삭제

      안녕하세요. 답글이 조금 늦었습니다.
      저도 slam에 대해 잘 아는게 아니라 사실 답변드리기가 어렵습니다만 생각하신 흐름이 제가 아는 것과 크게 다르지 않은것 같습니다. 다만 2.~3. 과정이 과정이 조금 이상한 것 같긴 한데요, 보통은 로봇의 위치를 예측할 때 휠 엔코더를 이용한 오도메트리를 이용하는 것으로 알고 있습니다. 그리고 이렇게 예측된 위치에서 맵에 존재하는 특징점들이 영상에 나타내야될 위치와 실제 관측된 위치와의 오차를 이용하여 위치를 보정하는 것이 일반적입니다.
      그런데, 카메라만을 사용하는 경우는 constant velocity motion model 등을 이용해서 카메라 위치를 예측한 후에 앞서와 같이 역투영된 특징점 위치와 관측된 특징점 위치의 차이를 보정할 수도 있고, 아니면 visual odometry (영상 프레임간의 위치변화를 특징점 매칭으로 계산) 개념으로 위치를 추정한 후 기존 맵에 있던 특징점이 현재 영상에서 관측되면 관측오차를 이용하여 맵과 위치를 보정하는 방식이 아닐까 생각합니다.

  • 2015.09.07 16:39 ADDR 수정/삭제 답글

    비밀댓글입니다

    • BlogIcon 다크pgmr 2015.09.08 00:11 신고 수정/삭제

      네, 카메라 한대로 하는 것입니다. 단순 질문글은 공개로 부탁드립니다.

  • 초심자 2017.04.12 22:23 신고 ADDR 수정/삭제 답글

    정말 쉽고 자세한 설명 진심으로 감사드립니다.
    꾸준히 들어오게 만드는 중독성 있는 블로그인 것 같아요.
    궁금한 것이 하나 있는데, 맵 확장 갱신에서 매 키프레임(세 가지 조건을 만족하는 프레임)들을 추가하고 bundle adjustment를 통해 맵 갱신 및 최적화를 진행한다고 하셨는데
    키프레임이 10장 추가되면 10장에 대한 메모리를 모두 갖고 있어야 하는 것인가요?
    계속 영상이 저장되어야 한다면 속도는 빠를지 몰라도 필요한 메모리가 계속 증가되는 문제가 발생하지 않을까하여 질문드립니다.

    • BlogIcon 다크pgmr 2017.04.12 22:57 신고 수정/삭제

      솔직히 말씀드리면 구체적인 구현은 잘 기억은 나지 않습니다. 벌써 3년 전에 쓴 글이네요.. 키 프레임이 늘어나는게 기존의 것들과 중복되지 않는 것들만 추가되기 때문에 늘어나더라도 어느 정도 한계는 있을 것입니다. 원래 PTAM이 소규모 공간에서 동작하는 기술이라서...