Optical Flow 루카스-카나데(LK) 알고리즘

Optical Flow중 가장 많이 사용하는 루카스-카나데 알고리즘에 대해 정리합니다.

루카스 카나데 알고리즘은 3가지 가정을 기초로 구성되어 있습니다.

1. 밝기 항상성 : 어떤 객체 상의 픽셀은 프레임이 바뀌어도 그 값이 변하지 않는다.

2. 시간 지속성 : 영상 내에서의 움직임은 빠르지 않다. 즉, 영상에서의 객체 움직임에 비하여 시간 변화가

                  더 빨리 진행된다.(연속된 프레임 상에서 보면 이동량이 크지 않다는 것을 의미)

3. 공간 일관성 : 공간적으로 인접한 객체는 동일 객체일 확률이 높다.

 한가지씩 살펴보면, 첫번째로 밝기 항상성은 추적되고 있는 영역 안의 픽셀들은 시간이 지나도 그 값이 일정함을 

나타내며, 이를 다음과 같은 수식으로 나타낼 수 있습니다.

밝기 값은 시간이 지나도 변하지 않는것을 의미합니다.

 두 번째, 시간 지속성은 프레임 사이의 움직임이 작다는 것을 의미합니다. 변화는 시간에 비한 밝기값의 미분이라고 

볼 수 있는데 연속적인 프레임 상에서의 변화는 매우 작다고 가정하는 것입니다.

1차원 공간에서의 경우를 생각해 보면

 위 그림에서 1차원의 경우 움직임 속도는 시간축 미분(시간의 변화량) It와 x축에 대한 미분(공간의 변화량) Ix를 갖고

으로 구할 수 있습니다.

 위 그림은 옵티컬 플로우 수식에 대한 또 다른 관점을 볼 수 있습니다. 앞에서 제시한 가정이 상항 맞는것은 아닙니다.

만약 객체의 움직임에 비해 카메라 촬영 시간이 느릴 경우도 있으므로 반복으로 정확한 해를 구할 수 있습니다. 위 그림

의 경우 추정된 속도를 시작점으로 하여 반복 연산을 수행하여 정확한 해를 구합니다. 밝기 항상성 가정으로 인해 x축 

방향으로의 공간 미분값은 첫 번째 프레임에서 계산된 값이 그대로 유지됩니다.(재 계산을 줄여 속도 향상)

시간축으로의 미분값은 매 프레임에서 매번 다시 계산해야 합니다. 그러나 만약 충분히 비슷한 값에서 시작 할  경우 

대략 5번 정도의 반복이라면 정확한 해를 구할 수 있습니다. 이 방법을 뉴턴방법(Newton's method)라고 부릅니다. 만약

첫 번째 측정이 충분히 유사하지 않으면, 뉴턴 방법은 발산합니다.

 위의 경우 1차원의 문제에 대한 해석이미만, 2차원 영상에서의 문제로 확장해 보면 단순히 y축을 추가하는것 만으로 

해결할 수 있습니다. 

표기법을 변형시켜 y축 방향으로의 속도 성분을 v라 하고, x축 방향으로의 속도 성분을 u라고 한다면

아래와 같은 수식으로 정리 할 수 있습니다.

 하나의 픽셀에 대해서 구성되는 이 방정식은 두 개의 미지수를 가지고 있습니다. 따라서 하나의 픽셀에서 구한

측정 값으로 2차원 움직임에 대한 유일해를 구할 수 없지만, 선형 방정식에 의해 기술되는 직선에 대해 수직 또는 

법선 방향의 움직임 성분을 구할 수 있습니다.