[cite]10.1109/TPAMI.2010.143[/cite]

1. Introduction

Optical flow는 bottom-up 방식의 비전 시스템에서의 중요한 요소를 차지하고 있습니다. Grouping이나 visual learning, perception of structure, self-localization에서 특히 중요한 역할을 하지요.

컴퓨터 비전 연구에서 이미지에서의 dense optical flow를 계산하는 일은 주로 Horn, Schunk의 연구에서 파생된 방법론을 사용하고 있습니다. 픽셀 값의 지역적이고, 그래디언트 기잔의 매칭 방법에 기반하고 여기에 global smoothness 성질을 가정하여 문제를 설정합니다. 이로부터 여러 연구들이 제안되고 온 뒤, 마침내 큰 이동량(large displacement)에 대한 경우도 대응할 수 있는 알고리즘이 나오게 되었습니다. 이러한 방법은 주로 coarse-to-fine warping 방법을 사용합니다.

계산해야 하는 정답이 정해져있는 optical flow 문제이지만, 이렇게 구해진 방법이 꼭 정답이라는 보장이 없습니다. 계산 결과는 여러 contraints 안에서의 local minimum인 것입니다. 따라서 결과는 계산의 초기값에 대하여 편향될 수 밖에 없습니다.

Coarse-to-fine warping 방법은 이러한 문제를 해결하기 위하여, coarse한 해상도에서 계산된 값을 초기값을 사용합니다. 큰 구조에서 사용된 움직임을 순차적으로 세세한 해상도로 내려가면서 정교하게 값을 갱신합니다. 하지만 이러한 방법은 작은 크기의 구조가 큰 스케일의 전체 움직임에 현저하게 다르게 움직일 경우 잘못된 계산을 하게 됩니다. 또한 사람의 팔과 같이 물체 끼리 연결된 축에 대하여 상대적으로 회전운동을 하는 articulated motion의 경우에도 좋지 않을 결과를 나타냅니다.

이 연구에서는 디스크립터 매칭 방법을 활용하여 이러한 문제를 해결하고자 합니다. SIFT, HOG 등과 같은 디스크립터들은 이미지 전체에 대한 global 매칭에서도 좋은 결과를 나타내기 때문입니다.

Optical flow 문제에서의 디스크립터 사용은 다음과 같은 문제를 가지고 있습니다.

1. 가려짐으로 인한 올바른 디스크립터 쌍을 기대할 수 없는 경우
2. 픽셀 단위 정확도의 디스크립터로 인한 낮은 정확도
3. 히스토그램 기반의 디스크립터의 사용으로 인한 부정확성

여기서는 큰 이동량에 대해서 정확하게 쌍을 찾을 수 있는 디스크립터의 장점과 기존 optical flow로부터 파생되어 나온 방법들의 정확성만을 혼합하고자 합니다.

2. Related work

디스크립터를 이용한 optical flow 연구는 Weber, Mlik으로부터 시작되어 SIFT flow까지 이어옵니다. SIFT flow는 이미지 전체에 대하여 SIFT 디스크립터를 계산한 뒤, belief propagation을 통하여 문제를 풀게 됩니다. 이 연구와 SIFT flow와의 차이는 3가지 입니다.

1. 히스토그램 기반의 피처에 완전히 의지 하지 않고, 픽셀 값을 또한 매칭에 사용합니다.
2. 최적화 값을 찾는 전략이 다릅니다. 모든 매칭 쌍을 찾는 것이 아니라 좋은 매칭 쌍만을 사용하고자 합니다.
3. 연속적인 모델을 사용하여 서브픽셀수준의 정확도를 제공합니다.

3. Variational model

Optical flow를 계산할 두 장의 이미지를 $ I_1, I_2 $라고 하고, 이미지의 2차원 좌표의 도메인을 $ \Omega \in R^2 $, 그리고 각 좌표의 픽셀 값을 $ R^d $라고 하여봅시다. d는 그레이 영상의 경우 1, 컬러 영상은 3이 될 것입니다. 이미지 도메인의 한 지점은 $ \mathbf{x} = (x, y)^T $로, $ \mathbf{w} = (u, v)^T $는 그 지점의 optical flow를 나타냅니다.

기본적으로 optical flow는 이동한 각 점들은 픽셀 값이 변하지 않는다는 가정에서 출발합니다.

$$E_{\text{color}} (\mathbf{w}) = \int_{\Omega} \Psi (|I_2(\mathbf{x + w(x)}) - I_1(\mathbf{x})|^2) d\mathbf{x}$$

Horn, Schunck의 연구에서 사용된 linearization 성질이 여기에서는 포함되지 않기 때문에 큰 움직임에 대해서도 계산이 가능한 식입니다. 함수 $ \Psi(s^2) = \sqrt{s^2 + \epsilon^2 }, \epsilon = 0.001 $를 사용하는 것은 가려짐과 가우시안 모양이 아닌 매칭 결과 기준에 대응하기 위한 것입니다.

하지만 실제로는 조명의 영향 탓으로 대응하는 점들은 색깔이 같지 않습니다. 따라서 하나의 제약을 더하게 됩니다. 바로 그래디언트가 일정하다는 가정입니다.

$$E_{\text{grad}} (\mathbf{w}) = \int_{\Omega} \Psi (|\nabla I_2(\mathbf{x + w(x)}) - \nabla I_1(\mathbf{x})|^2) d\mathbf{x}$$

이 두가지로도 부족하여 한가지를 더 추가합니다. 이동량의 변화에 대한 제한입니다.

$$E_{\text{smooth}} (\mathbf{w}) = \int_{\Omega} \Psi (| \nabla u(\mathbf{x})|^2 + |\nabla v(\mathbf{x})|^2) d \mathbf{x}$$

이 세가지를 모두 넣어 모델을 표현하면 다음과 같습니다.

$$E(\mathbf{w}) = E_{\text{color}} + \gamma E_{\text{gradient}} + \alpha E_{\text{smooth}}$$

이러한 모델을 사용하면 거의 모든 optical flow를 설명할 수 있게 되지만, 알고리즘의 실패는 w를 계산하는 과정에서 사용되는 approximative optimization 방법에 의한 것입니다. 다양한 optical flow 방법들은 coarse-to-fine 방법을 이용한 것으로, 입력 영상에서 초기 값으로 사용되는 값은, 자잘한 변화 요소보다는 이미지 전체의 커다란 변화 요소가 사용됩니다.

이 논문에서는 이 global regularity를 사용하지 않고 디스크립터를 이용하여 이미지 전체에 대한 매칭 정보를 사용할 것입니다.

디스크립터를 사용하는 단점으로는,

1. 서브픽셀수준의 정확도를 제공하지 않고,
2. 고정된 크기를 사용하는 디스크립터가 가져오는 효과.

를 들수가 있습니다.

이러한 이유로 여기서는 coarse-to-fine 최적화 과정에 디스크립터를 사용하는 것으로 해결하고자 합니다. 이제 새로운 제한을 추가할 것입니다.

$$E_{\text{match}}(\mathbf{w}) = \int \delta(\mathbf{x}) \rho(\mathbf{x}) \Psi(|\mathbf{w}(\mathbf{x}) - \mathbf{w}_1(\mathbf{x})|^2) d \mathbf{x}$$

여기서 $ \mathbf{w}_1(\mathbf{x}) $는 지점 $ \mathbf{x} $는 디스크립터 매칭을 통해 구한 이동에 대한 벡터입니다. $ \delta_i(\mathbf{x}) $는 대응하는 매칭 쌍이 있을 경우 1, 없으면 0입니다. 각 대응하는 지점은 매칭 점수 $ \rho_i(\mathbf{x}) $로 정의되는 가중치입니다. 이 식은 이미 매칭이 모두 이루어지고 난 뒤를 가정합니다.

매칭 과정에 대한 에너지 또한 추가합니다.

$$E_{\text{desc}}(\mathbf{w}_1) = \int \delta(\mathbf{x}) | \mathbf{f}_2(\mathbf{x + w}_1(\mathbf{x})) - \mathbf{f}_1(\mathbf{x})|^2 d \mathbf{x}$$

$ \mathbf{f}_1, \mathbf{f}_2 $는 각 프레임 1, 2에 대한 피쳐를 나타냅니다.

모든 수식을 통합하면 다음과 같이 됩니다.

$$E(\mathbf{w}) = E_{\text{color}} + \gamma E_{\text{gradient}} + \alpha E_{\text{smooth}} + \beta E_{\text{match}}(\mathbf{w}, \mathbf{w}_1) + E_{\text{desc}}(\mathbf{w}_1)$$

$ \alpha, \beta, \gamma $는 파라미터로 이미지 특성에 따라 수동으로 결정하여야 합니다.

여기서 optical flow와는 별도로 $ \mathbf{w}_1$ 을 사용한 이유는, 픽셀 단위의 디스크립터 매칭을 보조하고자 만든 것입니다.

4. Minimization

이제 이 식을 최소화하는 w를 구할 차례입니다. 이 수식은 매우 non-convex 하므로 approximation 방법을 이용하여야 할 것입니다. 좋은 초기값을 구하기 위하여 디스크립터 매칭을 이용한 뒤 그 결과를 continuation method에 적용하여 초기값을 구할 것입니다.

4.1 Descriptor matching

이 단계에서는 다른 에너지들은 무시하고 $ E_{\text{desc}}(\mathbf{w}_1) $ 만들 최소화하는 w를 찾는 것이 목적입니다. 이 수식만 따로 본다면, global 최적해를 찾을 수 있는 문제입니다.

$$E_{\text{desc}}(\mathbf{w}_1) = \int \delta(\mathbf{x}) | \mathbf{f}_2(\mathbf{x + w}_1(\mathbf{x})) - \mathbf{f}_1(\mathbf{x})|^2 d \mathbf{x} \\
= \sum_{i, \delta (\mathbf{x}_i) = 1} | \mathbf{f}_2 (\mathbf{x}_i + \mathbf{w}_1(\mathbf{x}_i)) - \mathbf{f}_1(\mathbf{x}_i)|^2$$

위의 수식에서처럼 두 이미지의 피쳐에 대하여 그 차이가 적은 쌍을 찾으면 되는데, efficient nearest neighbor 방법을 이용하여 계산 시간을 줄일 수 있습니다.

여기서 피쳐는 3가지 종류를 사용할 수 있습니다. 바로 region matching, HOG 디스크립터, geometric blur (GB) 방법입니다.

4.1.1 Region matching

Region matching 방법은 Arbelaez의 방법을 이용합니다. 이 방법을 사용하면 이미지가 계층적인 구조로 over-segmentation되는데, 계층의 각 영역마다 SIFT와 컬러에 기반한 디스크립터를 계산하고 이를 매칭하도록 합니다. 매칭 점수는 $ \rho(\mathbf{x}_i) = \frac{d_2 - d_1}{d_1} $을 이용합니다. d는 각각 가장 좋은 매치와 두번째로 좋은 매치와의 거리입니다. 거리는 sum of squared difference를 이용합니다.

4.1.2 Histogram of oriented gradients

또 다른 방법으로는 모든 영역에 대하여 histogram of oriented gradients (HOG) 를 계산하는 것입니다. 각 그래디언트 히스토그램은 7 * 7 영역 내에서의 다른 방향에 대하여 계산됩니다. 단 그래디언트의 방향에 대해서는 고려하지 않습니다. 인테그랄 이미지를 이용하면 계산이 매우 빠르며 quantization effect를 줄이기 위하여 Gaussian filter를 사용하였습니다. 최종적으로 디스크립터는 영역 중앙 픽셀과 4픽셀 간격으로 떨어진 총 9개 지점을 기준으로 계산되므로 15 * 9 = 135 의 항목을 가집니다. 길이는 역시 sum of squared diffrences 를 사용하고 $ \rho $ 또한 region matching과 같은 방법을 사용합니다.

이 방법은 첫번째 이미지에서 4 픽셀 단위마다 디스크립터를 계산하도록 하여 16배 빠르게 계산할 수 있으나, 영역이 7픽셀을 차지하므로 놓치는 영역은 없을 것입니다. 두번째 이미지에서는 모든 픽셀에 대하여 계산하는 것을 통해 픽셀 수준의 정확도를 유지할 수 있습니다.

부가적으로 영역내의 $ \nabla I \nabla I^T $의 eigenvalue $ \lambda $를 계산하여 전체 이미지 평균의 1/8 보다 작은 경우 그 지점의 디스크립터는 무시하도록 합니다.

HOG 디스크립터는 SIFT와 비슷하지만 크기 변화와 회전에 불변한 성질은 가지고 있지 않습니다.

4.1.3 Geometric blur

HOG와 비슷한 방법으로 7 * 7 크기의 $ \sigma_0 = 0, \sigma_1 = 1, \sigma_2 = 2 $ 3개 레벨의 Gaussian blurring을 적용하여 히스토그램을 생성합니다. 레벨 0에서 1개, 레벨 1에서의 4개, 레벨 2에서의 8개 항목을 조합하여 디스크립터를 생성합니다. 히스토그램을 생성하는 위치는 그림 3에 잘 나와있습니다. 나머지 방법은 HOG와 동일합니다.

4.2 Continuation method

앞에서 $ E_{\text{desc}}(\mathbf{w}_1) $ 를 해결하였으니 나머지 식들을 최적화할 차례입니다. Continuation 방법의 아이디어는 입력 이미지를 여러 단계로 smoothing하여 부분 문제로 나누어 처리하는 것입니다. Smoothing은 아주 세세한 단계의 피라미드를 생성하거나 아니면 이미지 크기는 그대로 둔 채로 smoothing 하는 방법도 사용할 수 있습니다.

각 피라미드에서의 최적 값 w는 Euler-Lagrange 방법을 이용하여 구할 수 있으며, 자세한 수식 전개는 논문에 나와있습니다. Coarsest 레벨에서 $ \mathbf{w}^0 = (0, 0)$으로부터 시작하여 최적값을 계산하고 다음 레벨에서는 $ \mathbf{w}^{k+1} = \mathbf{w}^k + \mathbf{dw}^k $ 으로 초기화를 수행합니다. $ \mathbf{dw} $ 의 계산법 또한 논문을 참고하기 바랍니다.

이러한 방법은 Expectation-maximization과 마찬가지로 전역이 아닌 어느 한 지역 최적값으로 수렴하는 것을 보장하지만, 초기값을 주는 것으로 잘못된 결과를 도출하는 것을 피해가고 있습니다.

5. Experiments

Middlebury benchmark 데이터를 이용한 실험을 수행하였고, 다른 방법들, 특히 SIFT flow와의 성능 비교를 보여주고 있습니다.

---