Software Engineer English & Software Engineering Blog - Sean

Optical Flow

Optical flow is the pattern of apparent motion of image objects between two consecutive frames caused by the movement of object or camera. It is 2D vector field where each vector is a displacement vector showing the movement of points from first frame to second. Consider the image below (Image Courtesy: Wikipedia article on Optical Flow).

Optical flow는 연속되는 두 프레임에서 물체나 카메라의 이동으로 인해 발생하는 명확한 물체 이동 패턴이다. 이는 각각의 벡터가 첫 째 프레임에서 둘 째 프레임으로 포인트들의 이동을 보여주는 변위 벡터들인 2D 벡터장이다. 아래 그림을 살펴 보자. (이미지 제공: Wikipedia의  Optical Flow)

image

It shows a ball moving in 5 consecutive frames. The arrow shows its displacement vector. Optical flow has many applications in areas like :

연속된 5개 프레임에서 공의 움직임을 표현 하고 있다. 화살표는 변위 벡터이다. Optical flow는 아래와 같이 많은 분야에서 응용 가능하다.

Structure from Motion

Video Compression

Video Stabilization ...

움직임의 구조화

비디오 압축

비디오 안정화 ...

Optical flow works on several assumptions:

Optical flow는 몇 가지 가정을 하고 있다:

1. The pixel intensities of an object do not change between consecutive frames.

2. Neighbouring pixels have similar motion.

1. 연속되는 이미지들에서 물체의 픽셀 강도는 변하지 않는다.

2. 이웃하는 픽셀들은 비슷한 움직임을 갖는다.

Consider a pixel I(x,y,t) in first frame (Check a new dimension, time, is added here. Earlier we were working with images only, so no need of time). It moves by distance (dx,dy) in next frame taken after dt time. So since those pixels are the same and intensity does not change, we can say,

첫 번째 프레임의 I(x, y, t) 픽셀을 생각해 보자 (새로운 차원, 시간이 추가 되었다. 전에는 이미지만을 다루었기 때문에 시간이 필요 없었다). 이 픽셀은 다음 프레임에서 dt시간이 지나고 (dx, dy)만큼 움직인다. 이 픽셀들은 같은 픽셀들이고 강도가 같기 때문에 아래와 같이 말할 수 있다.

Then take taylor series approximation of right-hand side, remove common terms and divide by dt to get the following equation:

우변에 테일러 급수 근사를 적용하고 공통항을 제거 한다. 그리고 dt로 나눠주면 아래와 같은 방정식을 얻을 수 있다.

where:

Above equation is called Optical Flow equation. In it, we can find fx and fy, they are image gradients. Similarly ft is the gradient along time. But (u,v) is unknown. We cannot solve this one equation with two unknown variables. So several methods are provided to solve this problem and one of them is Lucas-Kanade.

위 방정식은 Optical Flow 방정식이라 부른다. 여기서 image gradient인 fx, fy를 구할 수 있다. 마찬가지로 ft는 시간에 따른 gradient이다. 하지만 한 개의 방정식으로 두 미지수 (u, v)를 알 수는 없다. 이 문제를 해결하기 위해 여러가지 방법이 있으며 그 중 하나가 Lucas-Kanade이다.

Lucas-Kanade method

We have seen an assumption before, that all the neighbouring pixels will have similar motion. Lucas-Kanade method takes a 3x3 patch around the point. So all the 9 points have the same motion. We can find (fx, fy, ft) for these 9 points. So now our problem becomes solving 9 equations with two unknown variables which is over-determined. A better solution is obtained with least square fit method. Below is the final solution which is two equation-two unknown problem and solve to get the solution.

위에서 이웃하는 모든 픽셀들은 비슷한 움직임을 갖는다고 가정 했었다. Lucas Kanade method는 한 point 주위 3X3 픽셀들을 취하기 때문에 총 9개의 point들이 같은 움직임을 갖는다. 이제 이 문제는 2개의 미지수와 9개의 방정식을 풀어야 하는 over-determined 상황이 되었고 이 9개 point들의 (fx, fy, ft)를 찾을 수 있다. 더 좋은 해결 방법은 최소제곱법이다. 아래는 두 방정식-두 미지수 문제를 해결한 최종 공식이다.

( Check similarity of inverse matrix with Harris corner detector. It denotes that corners are better points to be tracked.)

(역행렬과 Harris corner detector는 유사하다. 이는 코너가 추적하기 좋은 점이라는 것을 의미 한다.)

So from the user point of view, the idea is simple, we give some points to track, we receive the optical flow vectors of those points. But again there are some problems. Until now, we were dealing with small motions, so it fails when there is a large motion. To deal with this we use pyramids. When we go up in the pyramid, small motions are removed and large motions become small motions. So by applying Lucas-Kanade there, we get optical flow along with the scale.

사용자 관점에서 아이디어는 간단하다. 특정 지점들을 추적하고 그 지점들의 optical flow vector를 얻는다. 하지만 문제가 있다. 지금까지는 작은 움직임만 다루었기 때문에 큰 움직임이 있다면 추적을 실패하게 되는 것이다. 큰 움직임은 pyramids를 사용한다. pyramis에서 상위 단계로 갈 수록 작은 움직임은 제거 되고 큰 움직임은 작은 움직임이 된다. 그러므로 Lucas-Kanade를 적용 함으로써 스케일에 따른 optical flow를 얻게 된다.

Lucas-Kanade Optical Flow in OpenCV

OpenCV provides all these in a single function, cv.calcOpticalFlowPyrLK(). Here, we create a simple application which tracks some points in a video. To decide the points, we use cv.goodFeaturesToTrack(). We take the first frame, detect some Shi-Tomasi corner points in it, then we iteratively track those points using Lucas-Kanade optical flow. For the function cv.calcOpticalFlowPyrLK() we pass the previous frame, previous points and next frame. It returns next points along with some status numbers which has a value of 1 if next point is found, else zero. We iteratively pass these next points as previous points in next step. See the code below:

OpenCV는 이 모든것을 cv.calcOpticalFlowPyrLK()로 제공한다. 영상에서 특정 포인트들을 추적하는 프로그램을 만들어 보자. 추적 포인트는 cv.goodFeaturesToTrack()로 결정 한다. 첫 번째 프레임에서 Shi-Tomasi corner를 감지하고 Lucas-Kanade optical flow를 사용해 이 점들을 반복 추적 한다. cv.calcOpticalFlowPyrLK()에는 이전 프레임, 이전 포인트 그리고 다음 프레임을 전달 한다. 그러면 다음 지점이 발견된 경우 1, 발견 되지 않은 경우 0의 값을 가지는 상태 리스트와 함께 다음 지점들을 반환 한다. 다음 단계에서는 '다음 프레임'으로 전달했던 프레임을 '이전 프레임'으로 전달 하게 된다. 아래 코드를 살펴보자.

참고

(This code doesn't check how correct are the next keypoints. So even if any feature point disappears in image, there is a chance that optical flow finds the next point which may look close to it. So actually for a robust tracking, corner points should be detected in particular intervals. OpenCV samples comes up with such a sample which finds the feature points at every 5 frames. It also run a backward-check of the optical flow points got to select only good ones. Check samples/python/lk_track.py).

위 코드는 다음 키포인트들이 정확한지 확인하지 않는다. 그러므로 optical flow는 이미지에서 특징점이 사라져도 그와 비슷한 점을 찾아갈 가능성이 있다. 그러므로 확실한 추적을 위해서는 추적점들을 특정 간격으로 확인해야 한다. OpenCV 예제 중 5 프레임마다 특징점을 확인하는 샘플이 있다. 이 샘플은 정확한 점들을 선택하기 위해 optical flow 지점들의 backward-check도 실행한다. samples/python/lk_track.py에서 확인할 수 있다)

See the results we got:

아래는 실행 결과이다:

image

Dense Optical Flow in OpenCV

Lucas-Kanade method computes optical flow for a sparse feature set (in our example, corners detected using Shi-Tomasi algorithm). OpenCV provides another algorithm to find the dense optical flow. It computes the optical flow for all the points in the frame. It is based on Gunner Farneback's algorithm which is explained in "Two-Frame Motion Estimation Based on Polynomial Expansion" by Gunner Farneback in 2003.

Lucas-Kanade는 밀도가 높지 않은 특성들에 대한 optical flow를 계산한다(이 글의 예제에선 Shi-Tomasi 알고리즘을 사용해 점들을 감지했다). OpenCV는 밀도가 높은 optical flow를 찾기위한 알고리즘도 제공 한다. 이 알고리즘은 프레임의 모든 점들에 대한 optical flow를 계산하며 "Two-Frame Motion Estimation Based on Polynomial Expansion" by Gunner Farneback in 2003에 소개되어 있는 Gunner Farneback's algorithm을 이용한다.

Below sample shows how to find the dense optical flow using above algorithm. We get a 2-channel array with optical flow vectors, (u,v). We find their magnitude and direction. We color code the result for better visualization. Direction corresponds to Hue value of the image. Magnitude corresponds to Value plane. See the code below:

아래 샘플은 위 알고리즘을 이용해 dense optical flow를 찾는 방법을 보여준다. optical flow 벡터 (u, v)의 2채널 배열과 그것들의 크기, 방향을 얻는다. 좀 더 분명한 시각화를 위해 색깔 변화를 준다. 방향은 이미지의 Hue 값에 대응시키고 크기는 Value(Brightness)값에 대응 시킨다. 아래 코드를 살펴 보자.

image

OpenCV comes with a more advanced sample on dense optical flow, please see samples/python/opt_flow.py.

OpenCV dense optical flow에 관련된 심화된 샘플은 samples/python/opt_flow.py에서 찾을 수 있다.

Meanshift

The intuition behind the meanshift is simple. Consider you have a set of points. (It can be a pixel distribution like histogram backprojection). You are given a small window (may be a circle) and you have to move that window to the area of maximum pixel density (or maximum number of points). It is illustrated in the simple image given below:

Meanshift의 원리는 간단하다. 우선 어떤 공간에 많은 점들이 있다고 가정해 보자 (Histogram backprojection으로 분포된 픽셀일 수도 있다). 그 공간에 속이 빈 작은 창(또는 원)을 놓고 점의 밀도가 가장 높은 곳으로 그 창을 움직여야 한다 (가능한 많은 점들을 포함 하도록). 간단히 그림으로 표현하면 아래와 같다.

The initial window is shown in blue circle with the name “C1”. Its original center is marked in blue rectangle, named “C1_o”. But if you find the centroid of the points inside that window, you will get the point “C1_r” (marked in small blue circle) which is the real centroid of window. Surely they don’t match. So move your window such that circle of the new window matches with previous centroid. Again find the new centroid. Most probably, it won’t match. So move it again, and continue the iterations such that center of window and its centroid falls on the same location (or with a small desired error). So finally what you obtain is a window with maximum pixel distribution. It is marked with green circle, named “C2”. As you can see in image, it has maximum number of points. The whole process is demonstrated on a static image below:

파란창(원) C1의 처음 중심 위치는 파란 사각형의 "C1_o"이다. 하지만 이 원의 실제 무게중심(centroid)은 "C1_r"이다 (파란 원). 이 둘은 일치하지 않는다. 그럼 원의 중심이 무게 중심과 일치 하도록 원을 이동시켜 보자. 그리고 다시 원의 무게 중심을 찾는다. 아마 다시 일치 하지 않을 것이다. 다시 원을 이동시켜 원의 중심과 무게 중심이 일치하도록(혹은 무시할 만한 오차가 될 때 까지) 반복 한다. 결국 원 안 점들의 밀도가 최대가 되는 지점을 얻게 될 것이다. 이 지점은 녹색 원 "C2"로 표시 되었다. 그림에서 알 수 있듯이, 이 원에 가장 많은 점들이 들어가게 된다. 전체 과정은 아래 이미지에 표현 되어 있다.

So we normally pass the histogram backprojected image and initial target location. When the object moves, obviously the movement is reflected in histogram backprojected image. As a result, meanshift algorithm moves our window to the new location with maximum density.

일반적으로 histogram backprojected image와 초기 target의 위치를 알려 준다. 물체가 움직이면 histogram backprojected image에 움직임이 반영 되고 그 결과, meanshift 알고리즘이 밀도가 가장 높은 곳으로 원을 옮기게 된다.

Meanshift in OpenCV

To use meanshift in OpenCV, first we need to setup the target, find its histogram so that we can backproject the target on each frame for calculation of meanshift. We also need to provide initial location of window. For histogram, only Hue is considered here. Also, to avoid false values due to low light, low light values are discarded using cv2.inRange() function.

OpenCV에서 meanshift를 이용하기 위해서는 우선 target을 지정하고 target의 histogram을 계산해야 한다. 이 histogram으로 각 frame에서 target을 backproject하여 meanshift를 계산한다. 잘못된 값이 나오는걸 막기 위해 너무 낮은 light 값은 cv2.inRange()를 이용해 제거한다.

Three frames in a video I used is given below:

아래 사진들은 위 코드에 사용된 video에서 추출한 프레임들이다.

Camshift

Did you closely watch the last result? There is a problem. Our window always has the same size when car is farther away and it is very close to camera. That is not good. We need to adapt the window size with size and rotation of the target. Once again, the solution came from “OpenCV Labs” and it is called CAMshift (Continuously Adaptive Meanshift) published by Gary Bradsky in his paper “Computer Vision Face Tracking for Use in a Perceptual User Interface” in 1988.

위 코드의 결과를 확인하면 문제점을 찾을 수 있다. 자동차가 멀리 있거나 가까이 있는거에 상관 없이 창은 항상 일정한 크기이다. 바람직한 현상은 아니다. Target의 크기와 회전 상태에 따라 창의 크기도 변경되어야 한다. 이에 "OpenCV Labs"의 Gary Bradsky가 1988년 발표한 논문 "Computer Vision Face Tracking for Use in a Perceptual User Interface에서 CAMshift (Continuously Adaptive Meanshift)라는 해결책을 제시 하였다.

It applies meanshift first. Once meanshift converges, it updates the size of the window as, . It also calculates the orientation of best fitting ellipse to it. Again it applies the meanshift with new scaled search window and previous window location. The process is continued until required accuracy is met.

CAMshift는 우선 meanshift를 적용 한다. Meanshift가 한 점으로 수렴하면 창의 사이즈를 로 변경하고 target에 꼭 맞는 타원의 방향을 계산한다. 그리고 다시 크기가 변경된 search window와 이전 창의 위치를 이용해 meanshift를 적용한다. 이 과정은 충분히 정확한 결과를 얻을 때 까지 계속 된다.