Intro
지난 포스트에서는 Lucas-Kanade Algorithm을 보완하기 위해 가중치를 통해 정확도를 올리는 방법과 Big Motion에 대응하기 위해 제안된 방법에 대해 이야기했다. 여태까지는 가장 대표적인 Handcrafted 방식인 Lucas-Kanade를 다뤘고, 이번 포스트에서는 필자가 개인적으로 생각하는 Handcrafted 기법의 정수인 EpicFlow를 다루겠다. 이것을 마지막으로 Handcrafted 기법은 더 이상 언급하지 않을 예정이다.(Horn-Schunck 등은 기회가 나면 다루겠다.) Epicflow를 마지막으로 다루는 이유는 앞으로 나올 Deep Learning을 이용한 기법들의 비교 대상으로 자주 언급되기 때문이다.
EpicFlow
EpicFlow는 CVPR2015에서 발표된 논문이다. Lucas-Kanade 등에서 사용된 Coarse-to-Fine 기법과 유사한 아이디어에 EpicFlow의 무언가를 추가해 성능을 좋게 만들었다. 그림을 보면 쉽게 그 아이디어를 이해할 수 있을 것이다.
EpicFlow는 크게 세 단계를 거쳐 Flow Map을 구한다. 먼저 매칭 알고리즘을 이용해 두 이미지 사이의 매칭 Sparse set을 구한다. 이때 사용되는 알고리즘은 가장 성능이 좋은 것(State of the art)을 선택한다. 그 후, Coarse-to-Fine에 대응되는 Sparse-to-Dense Interpolation을 통해 정밀한 Flow Map을 구하게 된다. 마지막으로 Energy Minimization으로 최종 Optical Flow를 구하게 된다.
위의 설명은 너무 고유 명사가 많다. 그림을 보는 것이 더 이해하기 편할 정도로 불친절한 설명이다. 따라서 하나씩 차근차근 풀어서 설명해 보겠다. 물론 이 포스트는 EpicFlow를 마스터하자!라는 취지의 글은 아니다. 오히려 앞으로 Handcrafted 기법의 정수로 Deep Learning 기법들의 대척점에 있는 EpicFlow가 어떤 알고리즘인지 콘셉트는 알고 가자! 의 취지에 가깝다. 따라서 너무 자세한 설명은 하지 않을 예정이니 양해 바란다.
Sparse set of matches
EpicFlow의 첫 번째 단계는 두 프레임 사이의 매칭쌍을 추출하는 것이다. State of the art Matching Algorithm이라고 표현한 만큼 어떠한 매칭 알고리즘도 사용될 수 있다. 실험에서는 Deep Matching과 Subset of an estimated nearest-neighbor field 방법을 사용했다.(Deep Matching 알고리즘은 단독적으로도 Optical Flow의 Large Displacement 약점을 보완하기 위해서 DeepFlow 네트워크에서 사용되기도 했다.) 매칭 쌍을 획득한다는 의미는 두 이미지에 대해서 Feature들을 Matching 하는 행위이다.
매칭 알고리즘 중 하나인 Feature Descriptor를 예시로 매칭한다는 의미를 이해해보겠다. Feature Descriptor는 시점이 다르거나 Affine Transform을 한 두 이미지에 대해서 특징점들을 매칭 하는 알고리즘이다. 쉽게 생각하면 서로 다른 두 이미지에서 같은 점을 찾는 알고리즘이며, 모든 픽셀에 대해서 찾는 것이 아니라 Edge와 같은 특징점들을 통해 Sparse 한 매칭 쌍을 추출한다. 이에 대한 자세한 정보는 Reference에 정리된 블로그 링크를 걸었으니 참조 바란다.
Interpolation Method
앞에서 구한 매칭쌍들을 Interpolate 과정을 거쳐 Dense 한 Flow Map을 추정해야 한다. EpicFlow는 두 가지 방법을 제안하고 있다.
- Nadaraya-Watson(NW) Estimation
- Locally-weighted Affine(LA) Estimation
여기에 추가적으로 Local Interpolation을 통해 사용하는 매칭 쌍 수를 제한한다. K-NN 알고리즘의 결과만을 Interpolation에 사용해 계산 속도를 향상했다.
Interpolation의 결과를 Energy Minimization 과정을 거쳐 Edge Point가 더 sharp 한 최종적인 Optical Flow를 획득한다. 에너지 최소화 방법은 이번 포스트에서는 자세히 다루지는 않겠다.(추후에 기회가 된다면 Horn-Schunk 알고리즘과 함께 다룰 예정이다.)
Edge-Preserving Distance
이제 EpicFlow Concept Figure의 대부분의 고유 명사가 해결되었다. 하나 남은 건 Contour후 결과로 얻은 Edge Map이다. EpicFlow에서는 Edge Map이 사용되는데 그 이유는 무엇일까? Large Displacement에 취약한 Lucas-Kanade Algorithm을 보완하기 위해 Coarse-to-Fine 기법이 사용된 건 앞선 포스트를 통해 알 수 있다. 그러나 이 방법 역시 Coarser 레벨에서 발생한 오차가 상위 레벨까지 전달되는 Error Propagation 문제가 있었다.
Sparse-to-Dense Interpolation은 이런 문제를 해결하기 위해 매칭 결과의 일부만을 활용했다. 이 과정에서 많은 정보를 상실하게 되고, 균일한 결과 혹은 기댓값을 위해서 Sparse 한 특징점들의 선정이 중요하다. 여기서 Edge Map이 제안되었으며, 그 이유는 새롭게 발생하는 모션의 경계는 이미지의 경계에서 나타난다는 특성 때문이다. 따라서 EpicFlow는 움직임의 경계, 즉 Edge Map을 보존해 Optical Flow 계산에 활용한다.
이때 보통 사용하는 Euclidean Distance는 Edge 부분에서 주변 배경과 차이가 많이 발생하는 Flow Map 특성상 배경의 영향을 많이 받아 Interpolation 시 결과물이 뭉개지는 문제가 있다. 따라서 Geodesic Distance(Edge-aware Distance)을 활용한다. Geodesic Distance는 계산량이 상당하기 때문에 시간이 오래 걸린다. 따라서 Approximation을 활용하는데 이에 대한 설명은 이번 포스트에서는 다루지 않겠다. 대신 Geodesic Distance와 Euclidean Distance의 차이에 대해 Concept Figure를 통해 알아보자.
Euclidean distance를 Coarse-to-Fine/Sparse-to-Dense Interpolation에서 사용하면 위 그림과 같이 배경의 영향을 많이 받는다. 따라서 Edge 부분의 Vector가 의도와 다른 값을 갖게 된다. 반대로 Geodesic distance를 사용하면 Interpolation 시 Optical Flow의 손상이 없거나 적다.
아래 그림은 Edge Map을 옆에서 바라본 그림이다. Euclidean distance의 경우 파란선과 같이 직선거리를 사용하기 때문에 Edge 밖과 안의 Vector들을 구분하지 않는다. 반면에 Geodesic distance는 Edge Map을 고려해 거리를 측정하기 때문에 Edge를 넘어가야 하는 경우 엄청 돌아가는 효과를 준다. 따라서 같은 Edge Map에 있는 Vector들끼리 비슷한 경향성을 유지하게 해 준다.
Reference
EpicFlow: Edge-Preserving Interpolation of Correspondences for Optical Flow
We propose a novel approach for optical flow estimation , targeted at large displacements with significant oc-clusions. It consists of two steps: i) dense matching by edge-preserving interpolation from a sparse set of matches; ii) variational energy minimi
arxiv.org
PR-214: FlowNet: Learning Optical Flow with Convolutional Networks
제 PR12 첫번째 발표 논문은 FlowNet이라는 논문입니다. Optical Flow는 비디오의 인접한 Frame에 대하여 각 Pixel이 첫 번째 Frame에서 두 번째 Frame으로 얼마나 이동했는지의 Vector를 모든 위치에 대하여 나
www.slideshare.net
[컴퓨터비젼] 6. Feature descriptors and matching
오늘은 Feature descriptor 와 matching 에 대해서 알아보도록 합시다. 저번 포스팅에서도 언급을 했듯이 Feature을 찾는 과정은 Detection, Description, Matching 으로 이루어져있습니다. 일단 Feature descript..
com24everyday.tistory.com
Next
다음 포스트에서는 Deep Learning 기반으로 Optical Flow를 측정하기 시작한 FlowNet에 대해 다룰 예정이다. EpicFlow와 같은 해에 공개되어 더 흥미로웠던 논문이며, 성능을 강화한 FlowNet 2.0의 경우 필자의 연구 주제에 사용하기도 했었다.
