논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

EpicFlow: Edge-Preserving Interpolation of Correspondences for Optical Flow

https://hal.inria.fr/hal-01097477

1. Introduction

비디오의 optical flow를 구하는 것은 아직까지 어려운 문제로 남았습니다. 이 문제를 어렵게 하는 것은 주로 가려짐이나, 모션의 불연속, 그리고 큰 이동량에 대한 부분들입니다. 이러한 문제를 해결하기 위하여 에너지 최소화 문제나, coarse-to-fine 알고리즘으로 구현하는 방법 등이 제안되었으나 여전히 잘 풀어내질 못하고 있습니다. Coarse-to-fine 알고리즘의 문제는 coarser 레벨에서의 오차가 상위 레벨까지 전파된다는 점입니다.

대신 여기서는 매칭 결과의 일부만을 가지고 interpolation하여 이를 optical flow의 초기값으로 사용하는 방법을 제안합니다. 그리고 한번의 에너지 최소화 계산을 통하여 최종 optical flow를 계산합니다. 이 과정에서 움직임의 경계를 보존해야 할 필요가 생깁니다. 새롭게 발견한 모션의 경계는 이미지의 경계 에서 나타난다.는 성질을 이용하고자 합니다. 또한 Euclidian distance 대신 더 좋은 edge-aware distance를 사용할 것입니다. 이렇게 얻어진 대응점들을 기반으로 EpicFlow 방법을 통해 optical flow를 계산합니다.

정리하자면,

  • Edge-aware distance에 기반한 sparse-to-dense interpolation 매칭 스키마인 EpicFlow를 제안합니다.
  • Edge-aware distance의 값을 빠르게 추정하는 방법을 제안합니다.
  • Coarse-to-fine 알고리즘들에 제안하는 방법이 더 정확하다는 것을 보입니다.

2. Related Works

기존의 방법들을 소개합니다. 생략하도록 하겠습니다.

3. Sparse-to-dense interpolation

EpicFlow는 크게 세 단계로 분류됩니다. 먼저 state-of-the-art 매칭 알고리즘을 이용하여 두 이미지 사이의 매칭 sparse set을 구한 다음, sparse-to-dense interpolation을 통하여 dense하게 만들어줍니다. 마지막으로 한번의 에너지 최소화 방법을 통하여 최종 optical flow를 계산합니다.

3.1 Sparse set of matches

첫번째 단계로 매칭쌍을 추출하는 단계입니다. 어떠한 매칭 알고리즘도 이 단계에서 사용할 수 있으나 실험에서는 Deep Matching과 subset of an esimated nearest-neighbor field 방법을 사용하였습니다. 이 대응 쌍을 $ M = \{ (p_m, p_m') \} $으로 표현하고 $ p_m, p'_m$은 각각 첫번째, 두번째 이미지의 픽셀입니다.

3.2 Interpolation method

두번째로 앞에서 구한 대응 관계들을 interpolate하여 dense한 대응 field를 추정해 낼 것입니다. 여기에서는 두가지 방법 중 하나를 사용할 수 있습니다.

Nadaraya-Watson (NW) estimation

Nayaraya-Watson estimator를 이용하여 계산되는 대응 field $ F_{NW}(p) $는 주변 매칭값의 합으로 결정됩니다.

$$F_{NW}(p) = \frac{\sum_{(p_m, p'_m) \in M} k_D (p_m, p) p'm} {\sum_{(p_m, p'_m) \in M}k_D(p_m, p)}$$

여기서 $k_D(p_m, p) = \exp(-a D(p_m, p)) $는 픽셀간 거리에 가우시안 커널을 씌운 것입니다.

Locally-weighted affine (LA) estimation

이 방법은 $ F_{LA} (p) = A_p p + t_p^T $로 계산됩니다. $ A_p$$t_p$는 affine transform을 하기 위한 파라미터로 least-square 을 이용하여 $ k_D (p_m, p) (A_p p_m + t_p^T - p'_m) = 0 $을 풀어 구할 수 있습니다.

Local interpolation

Interpolation에 사용하는 매칭 쌍을 제한하고자 합니다. 지점 p에서의 거리 D를 기준으로 K nearest neighbors 방법의 결과만을 interpolation에 사용하니다. 이들 점은 $ N_K(p) $로 나타냅니다.

3.3 Edge-preserving distance

Euclidian distance를 사용하여 위의 계산을 할 수도 있지만, 그렇게 하면 모션의 경계 부분은 반영이 되지 않습니다. 모션의 경계를 알고 있다고 가정한다면, 우리는 모션 경계를 기반으로 geodesic distance $ D_G $ 를 사용할 수 있습니다. 일반적으로 geodesic distance는 cost map에서 다음과 같이 정의됩니다.

$$D_G(p, q) = \inf_{\Gamma \in P_{p, q}} \int_{\Gamma} C(p_s)dp_s$$

우리의 문제에서는 C가 모션 경계라고 생각할 수 있습니다. 따라서 같은 모션에 속하는 레이어의 픽셀들은 거리가 까갑다고 평가될 것이고, 그렇지 않으면 먼 거리에 있다고 판단될 것입니다.

하지만 실제 모션 경계를 계산하는 것은 불가능하기 때문에 모션 경계는 이미지 에지의 부분 집합이라고 가정하고자 합니다. Cost map C를 생성하기 위해서 edge detector인 structued edge detector (SED) 방법을 사용하였습니다.

3.4 Fast approximation

Geodesic distance를 계산하는 시간은 상당합니다. 따라서 이를 추정 $ \tilde{D}_G $하는 방법을 사용하여야 합니다.

Geodesic Voronoi diagram

먼저 p로부터 가장 geodesic distance가 가까운 매칭을 나타내는 $ L(p) $를 정의하여야 합니다 이는 곧 어떠한 클러스터링 문제로도 생각할 수 있습니다.

Approximated geodesic distance

이제 픽셀 $p$와 다른 아무 $p_m$사이의 거리를 가장 가까운 매치인 $ L(p)$와의 거리에 매치간의 거리를 더하여 나타내고자 합니다.

$$\tilde{D}_G(p, p_m ) = D_G(p, L(p)) + D_G^G(L(p), p_m)$$

$D^G_G$는 두 매치 간의 geodesic distance를 그래프 기반의 방법으로 추정할 것입니다. 그래프는 매칭 쌍 $ p_m, p_m' $을 노드로 하고 L에서 인접하고 있다면 서로 에지로 연결시켜놓은 그래프입니다. 에지의 가중치는 두 노드간의 geodesic distance를 계산하여 할당합니다. 이렇게 생성된 그래프는 Voronoi 문제와 일치하게 되며, Dijkstra 방법을 통하여 두 지점간 거리를 구할 수 있게 됩니다.

Peicewise field

이제 픽셀과 매치 포인트간의 거리를 추정할 차례입니다. 픽셀 p에서 가장 가까운 매치를 $ L(p) = p_m $이라고 하여봅시다. p와 어느 한 $ p_n$과의 거리는 $p_m$$p_n$과의 거리에 $p_n$에는 무관한 상수를 더한 값입니다. 또한 $N_K(p) = N_K(p_m)$ 이므로, $k_{\hat{D}_G} (p, p_n) = k_{D_G}(p, p_m) \times k_{D^G_G}(p_m, p_n) $입니다. 결국 $ D^G_G $를 이용하여 생성한 거리 F(p)는 $ F(p_m) $과 같습니다.

4. Optical Flow Estimation

Coarse-to-fine vs. EpicFlow

EpicFlow의 sparse-t-desnse interpolation 처럼 coarse-to-fine 알고리즘도 dense한 대응점 필드를 생성하지만, 정확한 값으로 수렴하는 것을 보장하지는 않습니다. 이것이 그 알고리즘들이 초기화에 민감한 이유입니다. 여기서는 그것의 대안으로 다른 방법을 사용합니다. Full-sacle의 에너지 최솨화 방법 전에 보다 정확한 초기 값을 주는 것입니다.

Variational Energy Minimization

마찬가지로 data term과 smoothness term으로 정의된 에너지 함수를 최소화할 것입니다. Data term은 픽셀의 값과 그래디언트가 일정하다는 가정에 따른 [40]의 연구와 완전히 같으며, smoothness term은 이동량의 그래디언트를 놈을 이용합니다.

$$\alpha(x) = \exp(- k||\nabla_2 I(x)||), k = 5$$

최소화를 수행하기 전에 이전 단계에서 구한 sparse-to-dense interpolation 값들을 초기 값으로 넣어준 뒤 최소화 작업을 시작합니다.

5. Experiments

MPi-Sintel, Kitti, Middlebury 데이터셋에 대하여 실험하였습니다.


Add a Comment Trackback