이 논문은 2D 사진 묶음에서 입체적인 3D 모형을 reconstruct하고, 그 사진들을 관리하기/둘러보기 쉽게 하는 방법을 소개한다. 논문은 저자들이 설계한 end to end system을 어떻게 만들었는지 설명하는데, section 5, 6, 7은 그 프로그램의 작동 방식이나 설계 구조를 설명하므로 이 리뷰에서는 보다 중요하다고 생각되는 section 4에서 다룬 3D reconstruction 방법을 다루겠다.
Summary
저자들은 대량의 여행지 사진을 통해 자동으로 3D 구조를 만들고 그 공간을 navigate할 수 있는 photo explorer을 만든다. 그럼으로써 그 프로그램이 아래의 네 가지 역할을 수행할 수 있도록 기대한다.
paper에서 만들고자하는 end-to-end 3D photo browsing system은 image-based modeling, image-based rendering, user-interface techniques 순으로 이루어진다. rendering이나 interface에서는 explorer 프로그램의 UI가 어떻게 생겼고, 화면 전환은 어떻게 이루어지고, 유저가 할 수 있는 작업은 무엇이고 등 design에 대한 이야기를 다루므로 그보다 근본적인(라고 내가 생각하는) modeling 단계에 대해서만 리뷰를 다루겠다.
modeling 작업의 목표는 이미지로부터 camera pose(위치, 방향, field of view)와 sparse 3D geometric scene information을 추출하는 것이다. 이는 1. 각 사진의 feature point를 detect하고 2. image pair들에서 feature point들을 matching하고 3. iterative, robust SfM procedure를 실행해서 camera parameter들을 구하고 4. (SfM은 각 카메라의 상대적인 위치만 추정하기 때문에) overhead map(=absolute coordinate)에 카메라들의 위치를 고정해주는 과정으로 이루어진다. 하나씩 자세히 살펴보겠다.
- Keypoint detection and matching
처음으로 SIFT를 이용해 이미지당 (약 수천개의) keypoint와 keypoint마다의 local descriptor를 추출한다. 다음으로 approximate nearest neighbors package of Arya(1998)를 이용해 image pair의 keypoint descriptor를 matching한다. 그리고 RANSAC을 이용해 image pair의 fundamental matrix를 추정한다.(fundamental matrix 참고 1, 2) 이때 각 RANSAC iteration마다 eight-point algorithm [Hartley and Zisserman 2004]을 이용해 fundamental matrix 후보를 계산하고 non-linear refinement를 해준다. 마지막으로 복원된 fundamental matrix에서 outlier인 match들을 제거해준다. 이때 남은 matching수가 20개보다 적으면 모든 match를 다 없앤다. 즉, image pair마다 matching되는 keypoint descriptor가 20개 이상일 때 그 이미지들은 서로 관련이 있다고(geometrically consistent) 보는 것이다.
이렇게 관련있는 image pair 집합을 찾은 후 match들을 tracks로 정리(organize)한다. 논문에서는 track이 'a connected set of matching keypoints across multiple images'라고 한다. 동일한 위치의 keypoint들을 여러개의 사진에서 찾아서 묶은 단위를 track이라고 이해했다. track이 한 사진에서 복수의 keypoint를 가진다면 이 track은 inconsistent한 것으로 간주된다.(아마 같은 위치라면 여러 keypoint가 나올 수 없을테니까) 적어도 2개의 keypoint를 가진 consistent track들을 다음의 reconstruction 단계에 사용하게 된다.
- Structure from motion
이제 트랙마다 camera parameters와 3D location을 알아내고자 한다. parameter들은 consistent해야하는데, 이는 reprojection error가 최소화된 상태라는 의미다. 이 minimization은 non-linear least squares problem이고 Levenberg-Marquardt [Nocedal and Wright 1999] 알고리즘으로 푼다. 그러나 이 알고리즘은 local minima에 빠지기 쉬우니 좋은 초기 parameter 수치를 추정하는 게 중요하다. 그리고 모든 카메라와 track의 parameter를 한 번에 계산하는 게 아니라 카메라를 하나씩 더해가는 incremental approach를 한다.
우선 single pair of cameras의 parameter들을 추정하는 것에서 시작한다. image pair들 중 가장 많은 matching이 존재하는 pair를 초기로 택한다. 다음으로 3D location이 이미 계산된 (카메라/이미지가 가진) track들의 숫자가 가장 많은 카메라를 택해서 추가한다. 그리고 RANSAC 과정 내에서 direct linear transform (DLT) technique [Hartley and Zisserman 2004]을 사용해 추가한 카메라의 extrinsic parameter를 initialize한다. DLT는 intrinsic parameter matrix K에 대한 값도 추정해 주는데, K와 EXIF tag에서 얻을 수 있는 focal length를 사용해 추가한 카메라의 focal length를 initialize한다. 마지막으로 추가한 카메라의 track을 optimization에 포함시킨다. track은 이 track이 적어도 하나의 다른 recovered camera에서 관찰되고 track을 triangulate했을 때 위치 정보를 잘 추정할 때 포함시킨다.
이렇게 카메라를 하나씩 추가하는 과정을 반복해서 남은 카메라가 더 reconstructed 3D point를 관찰하지 못할 때까지 계속한다. iteration마다 object function을 minimize하는 건 sparse bundle adjustment library of Lourakis and Argyros [2004]를 사용한다. 이렇게 scene을 reconstruct한 후 Schmid and Zisserman [1997]의 line segment reconstruction technique을 이용해 scene내의 3D line segments를 detect할 수 있는데, 이건 optional한 post-processing step이다.
논문에서는 속도와 robustness의 향상을 위해 위의 과정에 두 부분을 추가한다. 첫째로 optimization마다 높은 reprojection error를 가지는 keypoint를 적어도 하나 가진 outlier track를 찾아 optimization에서 제외한다. 그리고 outlier가 없어질 때까지 optimization을 하고 outlier을 제외하는 것을 반복한다. 두번째로 optimization에 카메라를 하나씩 추가하지 않고 여러 카메라를 한 번에 추가한다. 최대의 match 개수(M)를 가진 카메라를 추가하면서 0.75M개까지의 match를 가지는 카메라도 함께 추가하는 것이다.
- Geo-registration
앞선 SfM과정은 카메라 간의 상대적 위치만을 구해주기 때문에 이를 geo-referenced image나 map(e.g. satellite image, floor plan, digital elevation map)에 할당하는 과정이 필요하다. 계산된 카메라들의 (상대)좌표는 absolute location과 similarity transform(global translation, rotation, and uniform scale).의 관계에 있다. 이건 유저가 직접 상호작용하여 model을 map에 맞추는 것 같은데, 이를 돕기 위해 Szeliski [2005]의 방법을 이용해 gravity vector를 표시해준다고 한다. 그러면 유저는 model을 수평으로 회전시키기만 하면 된다.
가끔은 SfM과정에서 fully metric reconstruction을 실패하거나 low-frequency drift in the recovered point and camera locations 때문에 similarity transform으로 map에 scene을 정렬 못할 수 있다. 이런 경우에는 GPS tag등으로 정확한 위치를 알고 있는 ground control point들을 SfM optimization의 constraint로 추가하거나 유저가 수동으로 point/camera와 image/map의 관련성을 명시해줄 수도 있다.
Strenghts
- 카메라 위치, orientation, geometry 등 initialize에 필요한 데이터에 의존하지 않고 사진 자체에서 그 정보들을 추출해낸다는 점이 데이터를 수집하고 활용하기 쉬워 application이 좋은 기술인 것 같다.
- 1과 같은 맥락으로 기존의 기술과 달리 로봇이 찍거나 전문적으로 설계해서 만든 데이터가 아니라 일상적인 사진을 조합해서 reconstruct할수 있다는 것이 장점인 것 같다.
- object의 표면을 깔끔하고 매끄럽게 보여주는 게 아니라 Figure 1의 (b)처럼 point cloud를 보여주는데, 논문의 section 2에서 밝힌 것처럼 IBR과 달리 이 논문의 목표는 모든 view에서의 사진을 synthesize하는 게 아니라 사진 묶음으로 'sense of geometry'를 제공하는 거라 목표에 충실했다고 할 수 있다.
Weaknesses
- run time이 너무 길다. 사진 120장으로 몇시간이 걸리고 2635장으로 2주가 걸렸다고 하는데, 많은 사용자들이 사진을 추가하면 실시간으로 적용되긴 힘들 것 같다.
Thanks!