본 글은 https://www.youtube.com/watch?app=desktop&v=Z_t0shK98pM
기반으로 작성되었습니다.
## Optical Flow란?
Optical Flow는 연속한 두 Frame 사이에서 각 Pixel의 Motion을 타나내는 Vector Map이다.
그림으로 설명하자면 다음과 같다.
이는 비디오의 인접한 두 프레임(t-1 frame, t frame)이 있을 때 t-1 frame의 픽셀을 빨간점이라고 하자
이 빨간점이 다음 프레임(t frame)에서의 빨간점으로 옮겨진 벡터(화살표 표시)가 나온다.
이 벡터를 t-1의 위치에 빨간점에 할당을 시킨다. 이를 한 점이 아닌 모든 픽셀에 대해서 계산을 하고 할당을 한 map을 Optical Flow라고 한다.
### Visualization Optical Flow
Optical Flow를 모든 픽셀에 대해서 위 그림과 같이 화살표로 나타낼 수 없다. 따라서 Optical Flow만의 Visualization 방식이 따로 존재한다.(일반적인 방법이지 절대적인 방법은 아니다.)
Optical Flow는 주로 Colormap으로 표현하는데 RGB 값이 아닌 HSV 값으로 표현한다.
여기서 HSV는 H는 색상, S가 채도, V가 명도이다.
Optical Flow에선 H(색상)을 가지고 Direction(방향)을 표현하고 S(채도)를 가지고 Magnitude(크기)를 나타낸다.
간단한 예시로 색상이 파란색이면 Direction이 왼쪽 윗 방향으로 움직인 것이고 빨간색이면 오른쪽 아래로 움직인 것이다.
채도는 진하면 Magnitude가 큰 것이고 하얀색에 가까우면 Magnitude가 작은 것이다.
## Optical Flow Constraint(OFC)
Optical Flow의 Constraint는 "Flow Vector로 이어진 두 Pixel 값은 동일하다." 이다.
이를 수식으로 표현하기 전 수식의 용어를 정리한다.
$$Image = I(x,y,t),Flow = (u,v)$$
여기서 \(x,y\)는 pixel의 좌표 \(t\)는 프레임 넘버(시간)이다. 그리고 Flow에서 \(u\)는 x 방향의 움직임, \(v\)는 y 방향의 움직임이다.
이제 Constraint를 수식으로 나타내면 다음과 같다.
$$I(x,y,t) = I(x+u,y+v,t+1)$$
t 프레임의 위치(x,y) 에서 x 방향으로 u 만큼 y 방향으로 v 만큼 움직인 값이 t 프레임에서의 기존의 값과 동일하다는 것이다.
이를 풀어쓰기 위해 간단한 수학적인 trick을 이용한다.
$$I(x,y,t) = I(x+u,y+v,t+1) = I(x,y,t+1) + \frac{\partial I}{\partial x}u + \frac{\partial I}{\partial y}v$$
$$I(x,y,t+1) - I(x,y,t) +\frac{\partial I}{\partial x}u + \frac{\partial I}{\partial y}v = 0$$
$$I_{t} + I_{x}u + I_{y}v = 0$$
이 식에 대해서 설명하겠다. 처음 식\(I(x+u,y+v,t+1) = I(x,y,t+1) + \frac{\partial I}{\partial x}u + \frac{\partial I}{\partial y}v\) 는 First-Order Taylor Approximation를 활용한 것이다. 일차 테일러전개는 곡선을 인접한 직선으로 만드는 방법이다. 이 방법을 활용함으로 인해 I에 대한 x를 편미분한 값애 u를 곱한 값과 같은 원리로 I를 y로 편미분한 값에 v를 곱한 값이 빠져나오게 된다.
그리고 이 전개식에서 \(I(x,y,t)\)를 이항시키면서 \(I(x,y,t+1) - I(x,y,t) +\frac{\partial I}{\partial x}u + \frac{\partial I}{\partial y}v = 0\) 식이 완성된다.
그리고 이 항은 \(I(x,y,t+1) - I(x,y,t)\) t에 대한 미분에 해당되기 때문에 \(I_{t}\)라고 나타내고 다른 편미분 값도 간단하게 나타낼 수 있게 된다.
따라서 \(I_{t} + I_{x}u + I_{y}v = 0\) 이 식을 Optical Flow Constraint라고 한다.
\(I_{t} + I_{x}u + I_{y}v = 0\) 이 식에서 u와 v를 구해야하는데 식은 하나도 구해야 할 변수는 u와 v 두개이다. 따라서 이는 부정방정식(Underdetermined)이 된다. 따라서 이를 해결하기 위해 하나의 제약조건을 더 추가를 해야한다. 그래서 Optical Flow의 문제를 해결하기 위해 많은 논문들은 새로운 제약조건을 제안하였다.
## Optical Flow Estimation by Optimization
### Lucas-Kanade Method
LK는 위 식을 최소화 하는 것에 목표를 둔다. 위 식을 좀 더 살펴보면 가운데 항은 Optical Flow의 Constraint 이고 이의 제곱을 최소화 하는 것이니 OFC = 0 이 되야한다는 것을 만족한다.
그러나 기존의 Optical Flow와 다른 점은 Neighborhood안에 있는 모든 x(\(N(x))\)에 대해서 OFC를 0을 만들고자 한다. 이러한 Neighbor는 다음과 같이 도출된다.
1. 이미지를 격자로 나눈다.
2. 같은 격자 안에 있는 벡터들은 같은 방향으로 움직인다고 가정한다.
여기서 한 그리드의 크기를 NxN 이라고 하면 그 그리드 안에 있는 픽셀의 개수는 \(N^{2}\) 이 된다. 그리고 이 \(N^{2}\)개의 픽셀은 모두 u와 v 의 방향으로 움직인다고 가정한다.
이렇게 되면 다음과 같이 \(N^{2}\)개의 식이 나온다.
여기서 u와 v는 공통이라고 가정했기 때문에 미지수는 2개고 식은 \(N^{2}\)개인 상황이 된다. 이는 아까와 다르게 overdetermined 상황이 되서 underdetermined 상황을 피할 수 있게 되었다.
u와 v가 1차로 나와있기 때문에 First-order 가 되고 이의 해결법은 pseudo inverse(의사역행렬)을 곱하는 방식으로 해결이 가능하다.
이러한 LK 알고리즘의 단점은 전체의 계산이 아니라 한 섹션에 대해서만 계산하기 때문에(실제 코드로는 Edge Point에서만 계산) sparse한 정보를 가질 수 밖에 없다. 따라서 정확도가 떨어질 수 밖에 없다.
### Variational Method
Variational Method는 첫번째 식을 Minimize하는 것을 목표로 둔다. \(\lambda\)가 곱해져 있는 절대값 안의 식은 OFC라는 것을 알 수 있다.
u와 v의 기울기벡터의 제곱을 더했는데 이 의미는 인접한 부분의 기울기 벡터의 변화가 크지 않아야한다는 것이고 이로 인해 급격한 기울기의 변화가 없게 된다. 왜냐하면 목적식 안에 있는 식을 최소화하는 것이 목적이기 때문에 두 기울기벡터의 합이 0에 가깝게 작아야하기 때문에 이와 같은 의미를 지닐 수 있다. 이를 Smoothness Constraint라고 하고 이를 Total Variation Loss라고 한다.
이 Loss는 위의 식은 L2 Loss Version이고 밑에 식은 L1 Loss Version이다.
이러한 Loss를 Gradient Descent를 이용하는 것이 아니라 수학적으로도 풀 수 있다. (Quadratic Relaxation)
앞에 정의한 L2 Loss는 1차식이 아니기 때문에 바로 풀 수가 없다. 따라서 이를 해결하기 위해 \(u-u', v-v' \)으로 나눈다. 이렇게 보조변수를 주고 \(u = u', v=v'\) 을 나타내기 위해 추가적인 constraint를 준다. 이게 \( \frac{1}{2\theta }(u-u')^{2} + \frac{1}{2\theta }(v-v')^{2} \) 이다.
이러한 상태에서 u와 v를 고정시킨다. 고정시킨 후에 기울기벡터 이후의 부분을 적분식에 넣는다. (빨간색 박스 1번 참고)
이 때 u와 v는 고정된 상태이고 u'과 v' 은 이차식의 형태를 띄고 있다. 따라서 이를 minimize하는 u'과 v'을 구할 수가 있게 된다.
이렇게 구한 u'과 v'을 고정하고 OFC를 제외한 식을 적분식에 넣는다. 이러면 u와 v는 quadratic의 형태를 띄고 있기 때문에 이 식에서도 u와 v를 구할 수 있게 된다.(빨간색 박스 2번 식)
그리고 1번과 2번 식을 N번 반복하여 u와 v를 update하는 방식으로 진행된다.
### Large Displacement
Large Displacement는 t-1 frame에서 t frame으로 움직일 때의 변화가 매우 큰 것을 의미한다. 이러한 Large Displacement는 앞서 언급한 LK 알고리즘과 Variational Method는 잘 반영하지 못한다.
이러한 이유는 OFC를 풀 때 First-Order Taylor approximation의 가정에 있다.
Taylor approximation은 Short Displacement가 전제되어 있다. 작은 변화가 전제되어 있기 때문에 큰 변화가 생기면 Taylor approximation의 에러는 커진다.
이러한 문제점을 해결하기 위해 제안된 Method는 Coarse-to-Fine Method 이다.
Coarse-to-Fine Method는 Large Displacement가 있는 이미지를 Downsampling으로 줄인다. 이러면 Large Displacement가 아닌 Small Displacement로 변한다. 그리고 Downsampling한 이미지를 다시 원본 이미지로 키워서 Upsampling 해서 복원시킨다.
하지만 Coarset level에서는 frame을 low resolution으로 downsampling해서 optical flow를 구하게 되는데 이 때 error가 많이 발생한다. 이를 다시 high resolution으로 복구할 때에도 에러가 남아있는 문제가 있다. 이러한 문제를 Error propogation 이라고 한다.
따라서 Coarse-to-Fine Method는 Error가 많아서 Large Displacement의 문제점을 제대로 해결하지 못했다.
두번째로 Large Displacement를 해결하기 위해 나온 방법은 TPAMI가 제안한 Large Displacement Optical Flow(2011)이다.
\(E_{color}\)에선 First-Order Taylor Approximation을 하지 않고, OFC를 있는 그대로 사용을 한다. 이를 이용하여 Gradient Descent 방법 등을 이용하여 접근한다.
\(E_{smooth}\)에선 앞서 설명한 Variational Method의 Loss를 그대로 사용을 한다.
\(E_{match}\)가 가장 핵심 loss인데 여기서 w(x)는 계산된 optical flow이고, \(w_{1}(x)\)는 feature descriptor를 이용한 mathcing 결과이다. \(\delta(x)\)는 해당 픽셀에 대해서 매칭 결과가 존재하면 1, 없으면 0이다.(feature descriptor가 sparse하기 때문에)
따라서 해당 픽셀이 Feature Descriptor가 존재할 때 계산하여 Optical Flow가 이 값을 따라갈 수 있게 만드는 loss이다.
- feature Descriptor란?
시점이 다르거나 Affine 변환을 한 두 이미지에 대해서 feature들을 matching 하는 알고리즘.
서로 다른 두 이미지에서 같은 점을 찾는 알고리즘. 이 때 모든 pixel에 대해서 dense하게 하는 것이 아니라 edge 같은 영역들을 통해서 sparse하게 matching을 이뤄냄
세번째로 EpciFlow(CVPR2015) 알고리즘이 있다.
EpicFlow 알고리즘은 첫번째 프레임에서 Edge map을 추출한다. 그리고 첫번째 두번째의 이미지와 비교해서 mathcing map을 사용하여 추출한다. 그리고 이 두 이미지를 이용하여 Dense Interpolation을 수행하고 이를 Energy Minimization을 이용하여 Edge point를 더 Sharp한 optical flow를 추출한다.
여기서 Edge map을 활용한 방법을 좀 더 자세히 알아보겠다.
위 그림에서 원을 하나의 이미지라고 생각하고 optical flow를 추출한다. (파란색 화살표) 이 때, EpicFlow도 Coarse-to-Fine 방식을 차용한다. Coarse-to-Fine 방식에서 Upsampling 할 때 여러 interpolation 방식 중 하날 사용하게 되는데 Euclidean Distance 방식을 사용하게 되면 물체와 배경의 다른 움직임을 가지는 flow의 영향을 받게 된다. 따라서 첫번쨰 그림에서 왼쪽 빨간색 화살표로 나와야 되는 것이 오른쪽 빨간색 화살표처럼 잘못 계산되게 된다.
따라서 이러한 interpolation 과정에서 optical flow의 손상이 없게 하도록 Geodesic distance 기반의 interpolation 기법을 사용한다.
밑 그림에서의 Edge map을 옆에서 바라본 그림이다. 기본 Euclidean distance를 사용하면 파란색 직선 거리를 사용하겠지만 Geodesic distance는 빨간색 선을 사용해서 Edge map을 따라서 이은 경로의 길이를 사용한다.
이러한 Geodesic distance를 활용할 때의 효과를 예를 들어 설명하겠다.
노란색이 유클리디안 거리라고 하고 빨간색 점을 기준으로 물체 안의 optical flow와 바깥의 optical flow의 유클리디안 거리가 같다고 가정하자.
그래서 유클리디안 거리를 사용했을 때는 두 길이가 같아서 빨간색 화살표(Optical flow)가 변형될 가능성이 있다. 그러나 Geodesic distance를 사용하면 물체 내의 optical flow와는 거리가 가깝지만 물체의 바깥에 있는 optical flow와는 edge map의 경로에서 한참을 돌아가야하기 때문에 멀다. 따라서 물체 내의 optical flow를 따를 수 있게 되는 것이다.
## FlowNet(ICCV 2015)
FlowNet은 딥러닝을 기반으로 Optical Flow를 추출하는 알고리즘이다. Optical Flow를 DeepLearning으로 하기에는 그 전엔 많은 한계가 있었다. 하드웨어와 딥러닝 기술의 부족이 있었고, Optical Flow의 Ground Truth 데이터셋의 부족이 가장 큰 문제였다.
따라서 이러한 문제를 해결하기 위해 Flying Chairs라는 데이터셋을 직접 만들었다.
Flicker DB에 3d Chairs 이미지를 합성하여 직접 데이터셋을 구축한 것이다.
## FlowNet 구조
FlowNet에선 두가지 구조를 제안한다.
FlowNetSimple은 이미지 2장을 한꺼번에 concat해서 네트워크에 넣어서 optical flow를 얻는 구조이다.
FlowNetCorr는 각 이미지에 대해서 feautre extraction을 진행한 다음에 두 feature를 corrleation layer라는 곳에 넣는다. 그리고 FlowNetSimple과 동일하게 네트워크에 넣어서 Optical Flow를 얻어내는 구조이다.
FlowNetCorr의 핵심인 corrleation layer는 위 그림으로 설명하겠다.
D x D의 영역을 먼저 정의를 한다. 그리고 영역 안에 K x K 의 patch가 존재한다.
하난 x1을 중심으로 한 patch이고 하난 x2를 중심으로 한 patch이다.
하나의 벡터로만 봤을 때 x1 위치의 벡터와 x2 위치의 벡터를 내적을 취한다. 그런데 이 x1과 x2가 각각 \(D^{2}\)개가 있기 떄문에 이러한 결과를 채널 축으로 쌓는다. 따라서 H x W x \(D^{2}\) 크기의 직육면체가 된다.
하지만 하나의 벡터로만 계산하는게 아니라 K x K 개의 patch 단위로 계산하게 된다.
즉, patch의 원소마다 내적을 하고 그 다음에 이를 summation 하여 H x W x \(D^{2}\) 에 저장하는 것이다.
이러한 과정을 식으로 나타내면 다음과 같다.
## Refinement Layer
Refinement Layer는 FlowNetCorr와 FlowNetSimple의 끝단에 있는 Layer이다.
이는 그림에서 볼 수 있듯이 upsampling과 convolution을 반복하는 형태이다. 또한 중간중간에 앞에서 계산된 layer를 skip connection 처럼 concat 하는 방식을 사용한다.
그리고 중간중간 계산된 결과에 대해서 각각의 flow를 뽑아서 gt image의 downsampling 버전과 비교를 하여 loss를 계산한다. 여기서 EPE loss(End Point Error)는 Estimated 와 GT 간의 L2 Loss이다.
## Results
EpicFlow보다 EPE가 더 높고 성능이 안좋음을 알 수 있다. 하지만 기존 CPU로만 계산하는 optical flow를 gpu로 올릴 수 있고, 계산이 빠르다는 contribution이 있다.
## FlowNet2.0(CVPR 2017)
FlowNet2.0은 기존의 FlowNet에서 성능을 향상 시키기 위해 만들어진 네트워크이다.
일단 FlowNet2.0은 Flying Chair dataset으로 pretraining을 한 다음에 Flying Things 3D dataset으로 추가적인 학습을 하였다.
### FlowNet2.0 Architecture
FlowNet2.0은 기존의 FlowNet network를 쌓아서 만들었다. 결과로는 FlowNet Corr + FlowNet Simple + FlowNet Simple이 가장 좋은 성능을 보였다.
여기에 추가로 FlowNet-SD라는 것도 합쳤다.
### FlowNet-SD Block
FlowNet-SD는 Small Displacement에 대한 성능을 강화하기 위한 Block이다. FlowNet은 Large-Displacement에 대해서 좋은 성능을 보이지만 Small Displacement에 대해선 좋은 성능을 보이지 못하였다. 따라서 이를 보강하기 위해 FlowNet-SD Block을 새롭게 만들었다. FlowNet-SD Block은 기존의 FlowNet-S 에서 Stride 등을 줄여서 조그마한 변화에 민감하게 학습할 수 있도록 만들었다.
또한, Small Displacement를 성능시키기 위해 ChairsSDHom이라는 새로운 Dataset을 만들고 이를 학습시켰다.
그리고 Large Displacement와 Small Displacement 를 합칠 수 있는 Fusion Layer를 통해서 결과 아웃풋 flow를 제공한다.
### Results
'논문 정리' 카테고리의 다른 글
| RAFT - Recurrent All-Pairs Field Transforms for Optical Flow (0) | 2021.07.23 |
|---|---|
| MaskFlowNet : Asymmetric Feature Matching with Learnable Occlusion Mask (0) | 2021.07.23 |
| Object Detection 정리(RCNN, FastRNN,FasterRCNN 중심으로) (0) | 2021.06.21 |
| TransGAN : Two Transformers Can Make One Strong GAN (0) | 2021.05.15 |
| A Style Based Generator Architecture for Generative Adversarial Networks(StyleGAN) (0) | 2021.05.09 |
댓글