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의 값을 가지는 상태 리스트와 함께 다음 지점들을 반환 한다. 다음 단계에서는 '다음 프레임'으로 전달했던 프레임을 '이전 프레임'으로 전달 하게 된다. 아래 코드를 살펴보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 |
import numpy as np
import cv2 as cv
cap = cv.VideoCapture('slow.flv')
# params for ShiTomasi corner detection
feature_params = dict(maxCorners = 100, qualityLevel = 0.3, minDistance = 7, blockSize = 7)
# Parameters for lucas kanade optical flow
lk_params = dict(winSize = (15,15), maxLevel = 2, criteria = (cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 0.03))
# Create some random colors
color = np.random.randint(0, 255, (100, 3)) # (low, high = None, size = None, dtype = 'l')
# Take first frame and find corners in it
ret, old_frame = cap.read()
old_gray = cv.cvtColor(old_frame, cv.COLOR_BGR2GRAY)
# Determines strong corners on an image(Input 8-bit or floating-point 32-bit, single-channel image).
p0 = cv.goodFeaturesToTrack(old_gray, mask = None, **feature_params)
# p0: array([[[435., 276.]], [[634., 111.]], [[175., 386.]], [[549., 73.]], [[554., 78.]], ...
# Create a mask image for drawing purposes
mask = np.zeros_like(old_frame)
while(1):
ret,frame = cap.read()
frame_gray = cv.cvtColor(frame, cv.COLOR_BGR2GRAY)
# Calculates an optical flow for a sparse feature set using the iterative Lucas-Kanade method with pyramids.
p1, st, err = cv.calcOpticalFlowPyrLK(old_gray, frame_gray, p0, None, **lk_params)
# p1: array([[[418.44635, 306.19986]], [[661.3394, 112.668175]], [[196.61299, 413.19797]], [[549.17065, 72.8348 ]], [[554.2681, 77.583626]], ...
# st: array([[1], [0], [1], [1], [1], ...
# Select good points
# st배열중 값이 1인 위치의 point만 선택되고 나머지(0) 위치의 point는 제외 된다.
good_new = p1[st==1]
# good_new: array([[418.44635, 306.19986], [196.61299, 413.19797], [549.17065, 72.8348], [554.2681, 77.583626], ...
good_old = p0[st==1]
# good_old: array([[435., 276.], [175., 386.], [549., 73.], [554., 78.], ...
# draw the tracks
for i,(new, old) in enumerate(zip(good_new,good_old)):
a,b = new.ravel() # Return a contiguous flattened array.
# a: 418.44635 b: 306.19986
c,d = old.ravel()
#c: 435. d: 276.
mask = cv.line(mask, (a, b), (c, d), color[i].tolist(), 2) # numpy.ndarray.tolist() - Return the array as a (possibly nested) list.
frame = cv.circle(frame, (a, b), 5, color[i].tolist(), -1)
# Calculates the per-element sum of two arrays or an array and a scalar.
img = cv.add(frame, mask)
cv.imshow('frame', img)
k = cv.waitKey(30) & 0xff
if k == 27:
break
# Now update the previous frame and previous points
old_gray = frame_gray.copy()
p0 = good_new.reshape(-1, 1, 2) # 42라인에서 변경한 shape을 원래 shape으로 변경.
cv.destroyAllWindows()
cap.release()
|
cs |
참고
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 |
import numpy as np
import cv2
arr1 = np.array([[1, 1],
[2, 3],
[3, 3],
[4, 4],
[5, 5]])
st = np.array([1, 0, 0, 1, 1])
result = arr1[st == 1]
print(result)
#[[1 1]
# [4 4]
# [5 5]]
arr2 = np.array([[1, 2],
[3, 4],
[5, 6]])
arr3 = np.array([[11, 12],
[13, 14],
[15, 16]])
for a, b in zip(arr2, arr3):
x, y = a.ravel(); print(x, y)
i, j = b.ravel(); print(i, j)
#1 2
#11 12
#3 4
#13 14
#5 6
#15 16
arr4 = cv2.add(arr2, arr3)
print(arr4)
#[[12 14]
# [16 18]
# [20 22]] |
cs |
(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)값에 대응 시킨다. 아래 코드를 살펴 보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | import cv2 as cv import numpy as np cap = cv.VideoCapture("vtest.avi") # cap.shape = (480, 640, 3)라고 가정. ret, frame1 = cap.read() prvs = cv.cvtColor(frame1,cv.COLOR_BGR2GRAY) hsv = np.zeros_like(frame1) hsv[...,1] = 255 # 2번 채널(y, x, 1)을 255로 초기화. #[[[ 0 255 0] # [ 0 255 0] # [ 0 255 0] ... while(1): ret, frame2 = cap.read() next = cv.cvtColor(frame2,cv.COLOR_BGR2GRAY) flow = cv.calcOpticalFlowFarneback(prvs,next, None, 0.5, 3, 15, 3, 5, 1.2, 0) # Computes a dense optical flow using the Gunnar Farneback's algorithm. # flow.shape = (480, 640, 2) mag, ang = cv.cartToPolar(flow[...,0], flow[...,1]) # Calculates the magnitude and angle of 2D vectors. # 마지막 옵션(angleInDegrees)이 True이면 degree로 계산 된다. (angleInDegrees=True) # mag.shape = (480, 640), ang.shape = (480, 640) hsv[...,0] = ang * 180 / np.pi / 2 # Radian을 Degree로 변환할 때, rad * 180 / PI 까지만 하면 된다. # 하지만 4.712 radian 만 되어도 약 270 degree가 되기 때문에 2를 나눠 주는거 같다. hsv[...,2] = cv.normalize(mag,None,0,255,cv.NORM_MINMAX) # Normalizes the norm or value range of an array. bgr = cv.cvtColor(hsv,cv.COLOR_HSV2BGR) cv.imshow('frame2',bgr) k = cv.waitKey(30) & 0xff if k == 27: break elif k == ord('s'): cv.imwrite('opticalfb.png',frame2) cv.imwrite('opticalhsv.png',bgr) prvs = next cap.release() cv.destroyAllWindows() #arr = np.arange(24).reshape(2, 3, 4) 2행 3열 4채널 #print(arr) ## 1행 ##[[[ 0 1 2 3] 1열, 각각의 원소들은 1~4채널 ## [ 4 5 6 7] 2열 ## [ 8 9 10 11]] 3열 ## 2행 ## [[12 13 14 15] 1열 ## [16 17 18 19] 2열 ## [20 21 22 23]]] 3열 #print(arr[1, ..., 2]) ## [14 18 22] # (1) #print(arr[1, :, 2]) ## [14 18 22] # (1)과 같은 결과 | cs |
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에서 찾을 수 있다.
