[cite]10.1111/j.1467-8659.2012.03013.x[/cite]

1. Introduction

Optical flow는 비디오에서 모션을 설명하는데 필수적인 알고리즘이지만, 제대로 동작하기 위해서는 몇가지 넘어야 할 산이 있습니다. 하나는 가려짐에 대한 대처이고, 나머지 하나는 Aperture 문제입니다. Aperture 문제란 이미지에서의 영역이 일정한 값을 가지고 있으면 움직임이 있더라도 별다른 정보를 얻을 수 없는 문제를 뜻합니다. 전통적인 optical flow 방법들은 주로 현재 프레임과 다음 프레임에서 컬러 값이 같은 픽셀을 찾는 문제로 해결해 나가고 있으나, 같은 컬러를 갖는 픽셀들이 꼭 한가지만 존재하지는 않기 때문에 제대로 결과를 내지 못하는 경우가 많습니다. 이를 해결하기 위해 픽셀이 아닌 블럭을 단위로 한 연구가 있으나 블럭의 크기를 어떻게 결정할지는 여전히 문제로 남아있습니다.

이러한 접근법에서 Optical flow를 계산하는 것은 Markov Random Field (MRF) 문제로 바꾸어 푸는 것으로 구현되곤 합니다. MRF 문제는 NP-Hard 문제이기 때문에 이를 추정하는 연구들이 나와있으나 그 계산량은 여전히 적지 않아 픽셀 수에 대하여 superlinear 합니다. 또한 최근 제안된 연구들은 GPU를 이용하여 계산 시간을 줄이기도 하였으나, 반복적인 방법을 사용하였기 때문에 여전히 계산 시간은 픽셀 수에 민감합니다.

이 Simple flow는 이러한 단점을 개선하기 위하여 반복적인 방법을 사용하지 않고(iteration-free), uniform motion에서는 일부분의 샘플만을 계산하는 방법을 사용할 것입니다. 여기에 멀티스케일 방법을 사용하고, 각 픽셀들은 독립적으로 계산되록 하여 병렬처리에 아주 적합한 방법을 제안합니다. 각 픽셀은 움직임의 확률론적인 표현으로 나타내어지며, 이것은 픽셀 값의 차이로부터 유도될 것입니다.

알고리즘은 자체적으로 잘 동작하지만, 다른 최적화 알고리즘의 초기값으로도 사용될 수 있습니다.

2. A Single-scale Algorithm

설명을 위해서 멀티스케일은 고려하지 않고, 두 연속적인 이미지에서의 알고리즘을 이야기해보겠습니다.

먼저 사용되는 기호를 먼저 정의하도록 하겠습니다. 연속적인 각 프레임은 $ F_t, F_{t+1} $로 나타냅니다. $ (x, y) $픽셀의 이동 벡터는 $ (u, v) $로 표시합니다. 각 프레임에서의 x, y위치의 픽셀 값은 $ F_t(x, y) $으로 나타냅니다.

A Simple likelihood model

이동전과 후의 두 픽셀은 컬러가 같다는 전제에 따라 모델을 정의하도록 합니다. 두 픽셀에 대한 에너지를 정의해보자면,

$$e(x,y,u,v) = || F_t(x,y) - F_{t-1}(x+u, y+v) ||^2$$

로 정의할 수 있고, 이것의 likelihood는 $ p \propto \exp(-e) $ 로 생각할 수 있습니다. 이것은 계산하기는 쉽지만, 기존의 연구에서 보였듯 에지 부분에서는 ambiguity가 발생합니다. 또한 p가 주변에 대해 일정하다면 역시 그 신뢰도가 떨어질 것입니다. 다시 말하자면, 이것은 픽셀 하나하나에 대한 계산이기 때문에 노이즈에 영향을 많이 받고 모호한 정보를 갖게 되는 것입니다.

Local validity as smoothness prior

따라서 한가지 가정을 더 추가하여, 좁은 영역에서의 움직임은 갑자기 변하지 않고 smooth한 성질을 갖는다고 생각합니다. 하지만 이전의 연구에서처럼 $ || (u_1, v_1) - (u_2, v_2) ||^2 $와 같은 것은 사용하지 않을 것입니다. 이것은 한 픽셀에 대한 계산이 주변 영역과 연결지어지기 때문에 문제를 풀기 어렵게 만들기 때문입니다. 그 대신 여기서는 조금 반대로 생각하여, 픽셀 $ (x_0, y_0) $에서의 움직임 $(u_0, v_0)$은 그 픽셀의 움직임 뿐만 아니라 그 주변 영역 $N_0 $의 픽셀들의 움직임또한 나타낸다고 생각해 봅시다. 다시 수식으로 표현하자면 다음과 같습니다.

$$(u_0, v_0) = \arg \max_{(u, v) \in \Omega} \prod_{(x,y) \in N_0} p(x, y, u, v)$$

여기서 $ \Omega $는 가능한 $(u,v)$의 집합을 나타냅니다. 이렇게 주변 영역 $N_0$의 픽셀의 정보까지 활용하면 더욱 부드럽고 깔끔한 이동량의 추정값을 계산할 수 있습니다. 계산을 쉽게 하기 위하여 log-likelihood 형식으로 식을 변경하여 줍니다.

$$(u_0, v_0) = \arg \min_{(u, v) \in \Omega} \sum_{(x,y) \in N_0} e(x, y, u, v)$$

다시 말하지만 이렇게 정의한 모델은 주변 픽셀과의 pairwise한 수식을 추가지 않아 다른 미지수와 상호작용하는 부분이 없기에 계산이 매우 간단해 집니다.

여기에 픽셀 간 서로 얼마나 관련이 있는지를 나타내는 가중치를 추가합니다. 가중치는 두가지로 두 픽셀간 거리가 얼마나 떨어져있는지를 나타내는 $ w_d $와 컬러 값이 얼마나 차이가 나는지를 나타내는 $ w_c $입니다.

$$w_d = \exp(-||(x_0, y_0) - (x, y)||^2 / 2 \sigma_d )$$

$$w_c = \exp(-||F_t(x_0, y_0) - F_t(x, y)||^2 / 2 \sigma_d )$$

이를 모두 반영하면 식은 다음과 같습니다.

$$E(x_0, y_0, u, v) = \sum_{(x,y) \in N_0} w_d w_c e(x, y, u, v)$$

Detecting occlusions

이제 가려짐을 찾아낼 차례입니다. 간단하게 t 프레임에서 t+1 프레임으로의 이동량 $ (u_f, v_f) $과 t+1 프레임에서 t 프레임으로의 이동량 $ (u_b, v_b) $을 비교해봅니다. 이론상으로는 둘은 부호만 다른 값을 가져야 할 것입니다. 두가지 방법을 생각할 수 있는데, 둘간의 차이에 따라 binary 값을 사용하거나, 차이 값 $ || (u_f, v_f) - (-u_b, -v_b)|| $ 를 그대로 사용할 수 있습니다. 만약 차이가 크면 그 픽셀은 가려졌다고 판단해야할 것입니다.

Practiacal implementation

실제 구현 과정을 살펴봅시다. $ F_t$의 각 픽셀 위치 $(x_0, y_0) $에 대하여, $ F_{t+1}$에서의 그 픽셀을 중심으로 하는 n * n 영역에 대한 $ e $를 계산합니다. 그 결과로 $n^2$크기의 벡터 $ \mathbf{e}$ 가 생성됩니다. 이제 $\mathbf{e}$에 $F_t$로부터 계산된 $w_c$를 이용하여 bilateral filer를 적용하면 E를 계산할 수 있습니다.

마지막으로 이제 $ \Omega $의 영역에 대하여 E를 최소화하여 $(u_0, v_0)$를 계산합니다. 이 과정에서 이렇게 계산된 이동량은 정수 값을 가지지만 $(u_0, v_0)$ 의 주변 3 * 3 의 이동량을 고려하여 parabola fit을 한 뒤 최소 값을 사용 서브픽셀 수준의 이동량을 계산할 수 있습니다. 이 과정에서

앞에서 언급한 것처럼 가려짐에 대한 검사를 하여 가려진 픽셀들은 제거한 뒤, $ w_d, w_c$ 와 추가적으로 이동량에 대한 신뢰도를 나타내는 $w_r$를 정의하여 사용합니다.

$$w_r(x, y) = \text{mean}_{(u, v) \in \Omega} e(x,y,u,v) - \min_{(u,v) \in \Omega}e(x,y,u,v)$$

Discussion

이 방법은 최대 n의 크기만큼의 이동량에 대해서만 계산할 수 있기에 n이 커질수록 비효율적이게 됩니다. 다음 장에서 멀티스케일을 활용하는 방법을 알아볼 것입니다.

3. A Multiscale Sublinear Algorithm

3.1. Multiscale Flow Estimation

각 이미지를 해상도를 1/2로 줄여가면서 이미지 피라미드를 생성합니다. 그 후, 가장 마지막 레벨의 이미지에서 섹션 2의 방법을 적용합니다. 이제 이 결과를 토대로 상위 레벨에서의 올라가면서 이동을 계산할 차례입니다.

이미 계산된 하위 레벨의 이동량 $ (\bar{u}_{l+1}, \bar{v}_{l+1}) $ 으로부터 upsampling된 이동량의 초기값을 $ (\bar{u}_l, \bar{v}_l) $ 이라고 합시다. Umsapling 방법은 joint-bilateral upsampling 방법을 사용합니다. 이제 섹션 2의 방법을 적용하되, $N $ 대신 $(x_0 + \bar{u}, y_0 + \bar{v})$ 를 중심으로 하는 $\bar{N}$을 사용하여 계산하도록 합니다.

3.2 An Efficient Scheme

피라미드를 사용하는 방법은 픽셀 값에 대하여 선형적으로 증가하는 계산량을 가지고 있습니다. 이를 조금 더 개선하여봅시다. 아이디어는, 이동량이 천천히 변화하는 곳의 계산을 직접 하지 않고 간단한 계산으로 대체하는 것입니다.

레이어의 각 픽셀 $ (x_0, y_0) $에 대하여, 다음 수식을 사용하여 irregularity map을 생성합니다.

$$\max_{(x,y) \in N_0} || ((u(x,y), v(x,y)) - (u(x_0, y_0), v(x_0, y_0))||$$

Upscaling 과정에서, 이 값이 임계치 $\tau$보다 작으면 본래 계산을 하지 않고, 영역의 4 모서리 부분의 계산만을 한 뒤, bilinear interpolation을 이용하여 계산을 대체합니다. 더 높은 정확도가 필요한 경우 높은 차수로 interpolation을 하여도 괜찮습니다.

4. Results

Middlebury optical flow 벤치마크 데이터셋을 포함하여 다양한 이미지에 대하여 실험하였고, 정확도와 속도면에서 비교하였습니다. 사용한 파라미터는 $ \sigma_c = 0.08, \sigma_d = 5.5, \tau = 0.25, N = 11 \times 11, \Omega = 20 \times 20 $ 을 사용하였습니다.

Limitations

대체로 알고리즘이 잘 작동햇으나, 반복되는 패턴, 그리고 빠른 모션에 대해서는 대응하기가 힘들었습니다.

5. Discussion and Conclusion

Optical flow를 구하기 위하여 global optimizatio을 사용하지 않고 지역적인 확률 평균을 이용하여 이미지 크기에 대해 sublinear한 복잡도 증가로 계산을 할 수 있었습니다.

---