optical flow with opencv python 연습

기본적인 전제는 동영상이 한 프레임에서 다음 프레임으로 넘어갈 때 pixel intensity 가 빠르게 변하지 않는다는 것이다. 그렇기에 물론 지나치게 빠르게 이동하는 물체는 잡아내기 힘들다. 사실 지나칠 것까지도 없고 슝- 하는 정도기만 해도 못잡지만...

그러므로 기본 등식을 다음과 같이 쓸 수 있다.

I(x, y, t) = I(x + dx, y + dy, t + dt)

 시간에 따라 x, y 좌표가 살짝씩 움직여도 intensity 즉 명도에는 차이가 없다는 뜻이다.

우변을 테일러 전개로 풀어주면 다음과 같이 된다.

I(x + dx, y + dy, t + dt)

= I(x) + dx* dI/dx +I(y) + dy * dI/dy + I(z) + dt* dI/dt

그러면 좌변에서 소거해 줄 수 있고, 남는 식은 이것 뿐이다.

dx* dI/dx + dy* dI/dy + dt* dI/dt = 0

좌변을 dt로 나누고 Intensity function I 의 dI/dx, dI/dy, dI/dt를 알아보기 쉽게 f_x, f_y, f_t로 바꿔주자(진작부터 f로 할걸...)

dx/dt *f_x + dy/dt * f_y + f_t = 0

마지막으로 dx/dt, dy/dt를 u, v로 치환해주면 optical flow equation 완성!

u*f_x + v*f_y + f_t = 0

 여기서 f_x와 f_y는 한 프레임 내에서 이미지의 명도가 어떻게 변하는지 확인하면 구할 수 있는 변수이고, f_t 역시 프레임이 다음 프레임으로 넘어갈 때 명도가 어떻게 변하는지 확인하면 구할 수 있다. 그러므로 총 미지수는 u, v 로 두 개이다. u와 v는 x,y가 시간에 따라 어떻게 변하는지에 대한 변수이므로, '속도'라고 보면 되겠지?

 어쨌든 변수는 두 개, 방정식은 하나이므로 식을 하나 더 만들어야 한다. 그건 Lucas Kanade Method를 사용해서 세워줄 수 있다. 3x3 행렬을 사용하여 픽셀의 gradient 들을 계산해주는 방법이다. 총 9개의 픽셀이 같은 u, v를 가진다고 등식을 세워주는 것이다. 픽셀을 p1 부터 p9 까지 정하기로 하자.

1번 식 : u*f_x(p1) + v*f_y(p1) = -f_t(p1)
2번 식 : u*f_x(p2) + v*f_y(p2) = -f_t(p2)
....
9번 식 : u*f_x(p9) + v*f_y(p9) = -f_t(p9)

두 개의 미지수를 위해 9개의 방정식이 나온 것은 너무하니까 최소자승법을 활용해서 가장 적합한 해를 찾아줄 수 있다. 행렬 A는 [f_x(p1)  f_y(p1); f_x(p2)  f_y(p2); ... ; f_x(p9)  f_y(p9)] 으로 9x2 행렬이고,  행렬 v 는 [u; v]로 2x1 행렬, 행렬 b 는 [-f_t(p1); -f_t(p2); ...; -f_t(p9)]로 9x1 행렬이다.

A * v = b

v를 구하는 것이므로 A를 정사각행렬로 만들어서 역행렬을 곱해주면 v만 남는다. A의 전치행렬 A'를 앞에 곱해주면 다음과 같이 정리할 수 있다.

A'A * v = A' * b

A'A는 A가 영행렬만 아니라면 반드시 역행렬을 가진다. 다음과 같은 이유 때문이다.

Consider the following:

ATAx=0

Here, Ax, an element in the range of A, is in the null space of AT. However, the null space of AT and the range of A are orthogonal complements, so Ax=0. If A has linearly independent columns, then Ax=0⟹x=0, so the null space of ATA={0}. Since ATA is a square matrix, this means ATA is invertible. 출처

 결국 v는 다음과 같이 약간 지저분하지만 깔끔하게 정리할 수 있다.

 이렇게 v를 구하면, 이전 좌표에서 이동한 좌표로 값을 바꿔줄 수 있다.
과정 설명과 결과는 다음과 같다.