DeepFlow: Large displacement optical flow with deep matching
[cite]10.1109/ICCV.2013.175[/cite]
1. Introduction
비디오 영상에서의 Optical flow 방법은 중요한 요소를 차지합니다. 이를테면 행동, 동작 인식, 감시 등의 분야에서 먼저 선행되어야 하는 방법으로 자리잡아 있습니다. 하지만 실제 영상에서는 Optical flow를 계산하기에는 불연속적인 움직임이나 가려짐, 조명변화, 그리고 갑작스럽게 멀리 이동해버린 요소들에 대한 문제를 고려해야만합니다.
Brox, Malik의 연구에서는 디스크립터를 매칭을 이용하여 큰 이동량을 다룰 수 있는 방법을 제안하였습니다. 그 아이디어는 디스크립터 매칭을 이용하여 곳곳의 대응하는 지점을 찾고, 이 정보를 기존의 전통적인 Optical flow 방법에 제공하는 것입니다.
하지만 현재 나온 디스크립터 매칭은 주로 사각의 Rigid 디스크립터로 모양이 거의 변하지 않는 모델을 사용하고 있으나, 이러한 부분은 Optical flow에 사용하기에는 잘 맞지 않기 때문에 여기서는 약간 변화를 주어 빠른 모션에 대해서도 대응할 수 있도록 하려고 합니다.
그리고 디스크립터 매칭 방법과 large displacement optical flow 알고리즘간의 갭을 잇는 새로운 방법인 deep matching이라는 새로운 디스크립터 매칭 알고리즘을 제안합니다. 이 방법은,
- Dence correspondences matching
- Self-smoothed matching
- Large displacement optical flow
의 특징을 가집니다.
2. Related work
Large displacement in optical flow estimation
큰 이동량에 대처하는 많은 방법들이 제안되어있지만, 주로 에너지 최소화(Energy minimization) 방법을 이용한 Brox의 방법을 확장한 방법들이 대부분입니다.
큰 이동량을 다루기 위해서 디스크립터 매칭 방법을 혼합한 방법이 제안[6]되었지만, 디스크립터가 특징이 존재하거나 rigid한 곳에서만 신뢰할 수 있다는 것이 단점으로 작용합니다. 또한 작은 이동량에서는 오히려 디스크립터를 만드는데 더 많은 연산이 소모되며, 잘못된 매칭이나 정밀함이 떨어지는 위험을 안고 있습니다.
이 논문에서는 효율적인 계산을 위해서 deep convolutional matching 과정을 소개합니다.
Descriptor matching
대부분의 이미지 매칭은 지역 디스크립터의 추출과 그 것들을 매칭하는 두 단계로 이루어집니다. 대부분의 경우 디스크립터는 rigid한 한 장면의 지역에서 추출되며, 디스크립터끼리는 nearest-neighbor 방법으로 매칭이 이루어집니다.
여기서는 non-rigid한 여러 장면에서 디스크립터를 추출할 것이며 이미지의 모든 영역으로부터 dense 매칭을 수행할 것입니다.
Non-rigid matching
여기서 제안하는 deep matching은 non-rigid 2D warping과 ddep convolutional networks에 많은 영감을 받은 것입니다.
3. Deep Matching
Deep matching은 6개의 층으로 이루어진 구조로 되어있습니다.
3.1 Insights on the approach
SIFT 디스크립터는 4 * 4 의 영역 셀로 이루어져 있고, 각 셀은 그래디언트의 히스토그램을 담고 있어 128 차원의 벡터 H 를 나타냅니다. SIFT의 영역을 4등분하여, 각 영역을 $ H^1, H^2, H^3, H^4 $라고 하여봅시다. SIFT에서는 이 4 * 4개의 셀들을 모두 고정시킨 상태에서 두 디스크립터 간의 매칭을 수행하였습니다. 하지만 만약 4등분한 조각들이 각각 대상 디스크립터에 가장 비슷한 부분으로 이동하는 위치를 찾는다면, 즉 각 4등분한 영역이 분리되는 것을 허용하여 서로 다른 곳에 위치하더라도 4개의 영역이 가장 비슷한 곳에 위치하는 부분을 찾는다면 모양이 변하는 물체에 대해서도 대응할 수 있을 것입니다. 즉 non-rigid 매칭을 할 수 있습니다. 이를 수식로 나타내면 다음과 같습니다.
$$\text{sim} (H, Q(p)) = \sum^4_{s=1} \max_{p_s} H_s^TQ(p_s)$$
여기서 $ Q(p) \in R^{32}$ 는 위치 p에서의 디스크립터의 한 4등분 조각의 디스크립터를 나타냅니다.
3.2 Deep matching as 2D warping
실제 구현은 2D 이미지에서 되어있지만, 이해를 돕기 위해 1D에서 설명을 하도록 하겠습니다.
먼저 길이 L을 갖는 2개의 1D 디스크립터를 각각 reference $ P = \{ P_i \}_{i=0}^{L-1} $, target $ P' = \{ P'_i \}_{i=0}^{L-1} $ 라고 합시다. 우리가 찾고자하는 것은, 두 디스크립터 사이의 유사도가 가장 큰 이동 관계 $ w^{*}(i) $를 찾는 것입니다. 즉,
$$S(w^*) = \max_{w \in W} S(w) = \max_{w \in W} \sum_i \text{sim}(P(i), P'(w(i)))$$
으로, $ w(i) $ 는 reference P의 i번째 성분이 target P’에서 어느 부분으로 이동했는지를 나타냅니다. 실제 구현에서는 위의 식을 계산하는데 그래디언트 성분을 이용하여 non-negative cosine similarity를 사용하였습니다.
최적의 w(i)를 효율적으로 찾고, 또한 적당한 모양 변화에도 대응하기 위하여 특별한 반복적인 방법을 사용하고자 합니다.
Efficient computation of response maps.
Deep matching의 아이디어는 디스크립터를 반으로 나누었을 때, 왼쪽과 오른쪽이 별개로 이동한다는 것에서 출발합니다. 반으로 나눠진 디스크립터를 다시 반으로 나누었을 때도 이는 마찬가지일 것입니다. 또한 계속적으로 나누었을 때, 나눠진 부분 디스크립터는 자기 자신의 길이만큼만 좌우로 이동이 가능합니다. 한편, 나누어진 두 부분 디스크립터의 상위 크기를 갖는 부분 디스크립터의 대응점은 하위 크기의 두 부분 디스크립터 대응점을 더한 값으로 결정하고자 합니다.
이러한 가정에서 출발하여 response map을 생성하도록 하겠습니다.
먼저 디스크립터를 계속적으로 반으로 쪼개어 한 조각의 길이 N이 4가 될 때까지 반복합니다. 쪼개진 디스크립터는 $P[ \delta , N]$으로 표헌합니다. i는 중심 위치이고, N은 조각의 길이입니다. $ N = 4 $ 인 조각이 생성되면, reference 디스크립터 조각 $ P[\dot \ , 4] $를 target 이미지에 convolution을 하여 response map을 생성합니다. 이렇게 계산된 값을 $ S(w^*_{N, \delta \rightarrow T}) $ 으로 표현합니다. 이는 reference에서의 크기 N, 중심 $ \delta $ 디스크립터 조각이 갖는 terget의 T위치에서의 response를 나타냅니다.
이제 이 response map을 앞에서 언급했던 가정에 따라 max-pooling 단계를 커쳐 N을 2배로 키운 response map을 생성합니다. 현재 계산된 N크기의 response map에서 가장 반응이 큰 위치 T를 얻습니다. 이 결과를 2의 크기로 subsampling 합니다. 실험에 따르면 높은 N일 수록 T에 대해서 천천히 변화하기 때문입니다.
이제 상위인 2N 크기의 디스크립터에 속하는 크기 N의 두개의 디스크립터의 대응점 T를 더하여 상위 디스크립터의 response map을 생성합니다.
Max-pooling with rectification.
이렇게 Max-pooling과 sub-sampling 과정이 끝난 직후에 power transform을 사용하여 좀더 response가 잘 전파되도록 합니다.
$$S'(w^*_{N,\delta \rightarrow T}) = S'(w^*_{N,\delta \rightarrow T})^\lambda$$
이를 계속적으로 반복하여 N을 키워나가며 response map을 계산하면 전체 이미지에 대한 4부터 원래 디스크립터 크기의 디스크립터에 대한 대응점을 구할 수 있습니다.
Merging dense correspondences.
이렇게 생성된 response maps들의 한 최대값으로는 픽셀 단위의 대응점을 구하기에 적당하지 않습니다. 여러 크기와 여러 지점의 response 정보를 이용하면 더 나은 정보를 계산할 수 있습니다. 먼저 가중치를 정의하도록 합니다. $ \text{weight} = \text{sim}(P_4, P'_4) \dot \ l \dot \ S(w^*) $ 가장 기본적인 4 * 4 패치의 simlarity와 피라미드 중 최대 값이 있는 레벨 l, 그리고 l레벨에서의 최대 값을 이용합니다. 이렇게 정의한 가중치는 높은 레벨의 global flow에 더 높은 점수를 주도록 되어있습니다.
마지막으로 4 * 4 블럭들에 해당하는 대응점 중 가중치에 따라 가장 좋은 것만을 남겨 최종 대응점 이미지로 사용합니다.
3.3 Analysis of deep matching
Multi-size patches and repetitive textures : 이 방법은 디스크립터의 텍스텨를 이용한 매치를 이용하므로, 여러 크기의 패치를 사용해 보았을 때 큰 패치를 사용하면 좀 더 성능이 좋고 패턴이 있는 곳에서도 잘 대응하였습니다.
Quasi-dense correspondences : 이 방법은 SIFT같은 매칭 방법과는 다르게 아주 dense한 단계에서까지 매칭을 대응점을 계산합니다.
Non-rigid deformations : 이미지의 non-rigid deformation에 대해서도 대응이 가능합니다. 이론상으로는 [1/2, 3/2]의 크기 변화와 [-30, +30]도의 회전에 대응할 수 있습니다.
4. DeepFlow
이제 앞에서 설명한 deep matching 방법을 에너지 최소화 프레임워크에 넣을 것입니다. 이것은 기존 Brox, Malik의 방법과 매우 유사한데, 3가지 추가적인 부분을 넣었습니다. 하나는 deep matching 방법을 사용한 것이고, data term을 normalization 하여 갑자기 이동량의 크기가 변해버리는 효과에 대한 충격을 줄이고, 각 레벨에 대하여 가중치를 다르게 사용하여 자세한 레벨에서 매칭되는 것을 줄였습니다.
두 이미지가 $ I_1, I_2 $라고 한다면, 그 이동량은 $ w = (u, v)^T $로 표현합니다. 이미지는 Gaussian filtering 되었다고 가정합니다. 에너지 최소화의 식은 아래와 같습니다.
$$E(w) = \int_{\Omega} E_D + \alpha E_S + \beta E_M dx$$
특별히 계산 도중 함수 robust penalizer $ \Psi(s^2) = \sqrt{s^2 + \epsilon^2} $ 을 사용할 것입니다.
Data term
Optical flow의 밝기가 일정하다는 가정에서 출발합니다.
$$E_D = \Psi(w^T J_0 w)$$
$ J_0 = (\nabla_3 I) (\nabla_3^T I) $로 정의되는 텐서입니다. 이렇게 정의되는 data term은 지역적 이미지 변화에 너무 많은 가중치를 주게 됩니다. 따라서 지역 변화량의 놈에 일정한 factor를 더하여 normalize를 해줍니다. Normalized 텐서 $ \bar{J_0} = \theta_0 J_0, \theta_0 = (||\nabla_2 I||^2 + \zeta^2)^{-1}, \zeta = 0.1$를 다음과 같이 계산합니다. 컬러 이미지의 경우엔 각 컬러값의 텐서를 모두 더한 다음 penalize를 해주도록 합니다.
그래디언트가 일정하다는 가정도 사용합니다. $ I_x, I_y $를 각각 이미지의 그래디언트라고 한다면, 비슷한 방법으로 채널 i에서의 그래디언트 텐서를 계산합니다.
$$\bar{J_{xy}^i} = (\nabla_3 I^i_x) (\nabla_3^T I^i_x) / ( || \nabla_2 I^i_x ||^2 + \zeta^2) + (\nabla_3 I^i_y) (\nabla_3^T I^i_y) / ( || \nabla_2 I^i_y ||^2 + \zeta^2$$
정리하면 Data term은 $ \delta $와 $\gamma$을 파라미터로 하는 다음 식으로 표현됩니다.
$$E_D = \delta \Psi(\sum_{i=1}^c w^T \bar{J_0^i} w) + \gamma \Psi( \sum_{i=1}^c w^T \bar{J^i_{xy}} w)$$
Smoothness term
이동량의 그래디언트를 사용합니다.
$$E_S = \Psi ( || \nabla u||^2 + || \nabla v || ^2)$$
Matching term
이 식의 역할은 우리가 미리 구해두었던 이동량 필드 $ w' $에 계산되는 optical flow가 $ w $가 비슷하게 되도록 하는 역할입니다. 따라서 이 둘간의 차이를 penalize하도록 식을 세우도록 하여봅시다.
기존의 매칭이 완전히 픽셀 단위로 이루어지지 않았으므로, 매칭 쌍이 있으면 1이고 아니면 0인 $ c(x) $함수를 사용하도록 합니다. 또한 매칭이 이상하다고 판단되거나 평평한 영역일 경우 낮은 가중치를 주도록 하는 함수 $ \phi(s) $도 사용합니다. 식을 먼저 제시해보자면 다음과 같습니다.
$$E_m = c \phi \Psi(||w - w'||)^2$$
$$phi(x) = \sqrt{\tilde{\lambda}(x)} / (\sigma_M \sqrt{2 \pi}) \exp(-\Delta(x) / 2 \sigma_m )$$
$$\Delta(x) = \sum_{i=1}^c | I_1^i(x) - I^i_2 (x - w'(x))| + | \nabla I_1^i(x) - \nabla I^i_2 (x - w'(x))|$$
$ \tilde{\lambda}(x) $ 는 autocorrelation matrix를 10으로 곱한 것의 가장 작은 eigenvalue입니다.
Minimization
Successive Over Relaxation (SOR) 방법을 이용하여 25번의 반복을 사용하였습니다.
5. Experiments
Middlebuery, MPI-Sintel, KITTI 데이터셋에 대하여 성능을 측정하였습니다.