オプティカルフロー(Optical Flow)

目的

このチュートリアルでは
  • オプティカルフローの概念と,Lucas-Kanade法を使ったオプティカルフローの計算方法を学びます.
  • 同画像中の特徴点の追跡のために cv2.calcOpticalFlowPyrLK() 関数などを使います.

オプティカルフロー(Optical Flow)

オプティカルフローとは物体やカメラの移動によって生じる隣接フレーム間の物体の動きの見え方のパターンです.各ベクトルが1フレーム目から2フレーム目への変位ベクトルを表す2次元ベクトル場で表現されます.以下の画像(画像引用: Wikipedia article on Optical Flow) を見てください.

Optical Flow

この画像は連続する5フレーム中でのボールの動きを表す画像です.矢印は変位ベクトルを表します.オプティカルフローは以下のように様々なアプリケーションで使われます:

  • Structure from Motion(動きを基にした3次元復元)
  • 動画像の圧縮
  • 動画像の安定化(Stabilization)

オプティカルフローは幾つかの仮定をしています:

  1. 連続フレーム間で物体の画像上の明るさは変わらない.
  2. 隣接する画素は似たような動きをする.

1枚目の画像中の画素 I(x,y,t) を考えます(tは時間軸方向を表す次元です).時刻 dt 後に撮影された次の画像中で (dx,dy) の距離を移動したとします.この二つの画素は同じものを見ていて,かつ明るさは変わらないと仮定したので,以下の関係が成り立ちます.

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

定式の右辺をテイラー展開し,共通する項を取り除き dt で割ると以下の式を得ます:

f_x u + f_y v + f_t = 0 \;

ここで:

f_x = \frac{\partial f}{\partial x} \; ; \; f_y = \frac{\partial f}{\partial x}

u = \frac{dx}{dt} \; ; \; v = \frac{dy}{dt}

この式をOptical Flow equationと呼びます.画像の勾配である f_xf_y を計算できます.同様に時間軸方向の勾配 f_t も計算できます.しかし, (u,v) が未知です.二つの未知数があるのに式が一つしかないため,この問題を解けません.この問題を解くために色々な手法が提案されてきました.Lucas-Kanade法はそれらの一つです.

Lucas-Kanade法

先ほど全ての隣接画素は似たような動きをすると仮定しました.Lucas-Kanade法は,ある点に対してその点を含む周囲の3x3のパッチに含まれる9画素が同じ動きをしていると仮定し,この9画素の情報を基に (f_x, f_y, f_t) を計算します.これで二つの未知数に対して式が9本あるので,優決定系(over-determined)な線型方程式が得られます.よりよい解法は線型フィッティングによって得られます.二変数に対して式を二本持つ最終的な解法を以下に示します.

\begin{bmatrix} u \\ v \end{bmatrix} =
\begin{bmatrix}
    \sum_{i}{f_{x_i}}^2  &  \sum_{i}{f_{x_i} f_{y_i} } \\
    \sum_{i}{f_{x_i} f_{y_i}} & \sum_{i}{f_{y_i}}^2
\end{bmatrix}^{-1}
\begin{bmatrix}
    - \sum_{i}{f_{x_i} f_{t_i}} \\
    - \sum_{i}{f_{y_i} f_{t_i}}
\end{bmatrix}

(右辺の逆行列がHarrisのコーナー検出器に似ている点を確認してください.これはコーナーが物体追跡にとって適した点であることを意味します.)

使用者の観点で見るとアイディアは単純で,追跡のために点を幾つか指定し,これらの点のオプティカルフローを受け取ります.しかし,ここでも問題が発生します.これまでは小さい運動を扱っていましたが,大きな動きがあった場合でも問題なく追跡できるのでしょうか.ここで画像のピラミッドを使います.ピラミッドのスケールをアップすると,小さな動きが消され大きな動きが小さな動きとして観測されます.Lukas-Kanade法をこの解像度で適用することで,そのスケールでのオプティカルフローが得られます.

OpenCVにおけるLucas-Kanade法

OpenCVは上記の全ての処理を行う cv2.calcOpticalFlowPyrLK() という関数を用意しています.ここでは同画像中の複数の点を追跡するアプリケーションを作成します.追跡する点を決めるために cv2.goodFeaturesToTrack() 関数を使います.1枚目の画像を撮影し,Shi-Tomasiのコーナーを検出します.それ以降,Lucas-Kanade法を使ってこれらの点を繰り返し追跡します.関数 cv2.calcOpticalFlowPyrLK() を使う場合,前フレーム,前フレームでの店の位置,現フレームを入力します.返戻値は次のフレームでの点の位置と状態変数です.状態変数は次の画像中で点が見つかれば1,そうでなければ0になります.新しく検出した点を更に次のフレームでの入力に使用し,この処理を繰り返し行います.コードは以下のようになります:

import numpy as np
import cv2

cap = cv2.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 = (cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 0.03))

# Create some random colors
color = np.random.randint(0,255,(100,3))

# Take first frame and find corners in it
ret, old_frame = cap.read()
old_gray = cv2.cvtColor(old_frame, cv2.COLOR_BGR2GRAY)
p0 = cv2.goodFeaturesToTrack(old_gray, mask = None, **feature_params)

# Create a mask image for drawing purposes
mask = np.zeros_like(old_frame)

while(1):
    ret,frame = cap.read()
    frame_gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)

    # calculate optical flow
    p1, st, err = cv2.calcOpticalFlowPyrLK(old_gray, frame_gray, p0, None, **lk_params)

    # Select good points
    good_new = p1[st==1]
    good_old = p0[st==1]

    # draw the tracks
    for i,(new,old) in enumerate(zip(good_new,good_old)):
        a,b = new.ravel()
        c,d = old.ravel()
        mask = cv2.line(mask, (a,b),(c,d), color[i].tolist(), 2)
        frame = cv2.circle(frame,(a,b),5,color[i].tolist(),-1)
    img = cv2.add(frame,mask)

    cv2.imshow('frame',img)
    k = cv2.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)

cv2.destroyAllWindows()
cap.release()

(このコードでは次の特徴点の正確性は確認していません.つまり,画像中で特徴点が見えなくなったとしても,その点に似ている特徴点が次のフレームにあればオプティカルフローを計算してしまう可能性があるわけです.頑健な追跡を実現するためには,コーナー検出は特定の間隔で行われるべきです.OpenCVでは5フレーム毎に特徴点検出を行っています.また,オプティカルフローの逆方向への探索を行い安定した追跡結果だけを選択しています.サンプルファイル samples/python2/lk_track.py を確認してください).

See the results we got:

Lucas-Kanade method for optical flow

OpenCVでの密なオプティカルフロー

Lucas-Kanade法が出力するオプティカルフローは疎な特徴です(上記のコードではShi-Tomasiアルゴリズムによって検出したコーナーです).OpenCVは密なオプティカルフローを検出するためのアルゴリズムを別に用意しています.画像中の全画素に対してオプティカルフローを計算します.Gunner Farnebackが2003年に発表した “Two-Frame Motion Estimation Based on Polynomial Expansion” で提案されたアルゴリズムに基づいています.

以下のサンプルはこのアルゴリズムを使って密なオプティカルフローを計算します.出力として,オプティカルフローベクトル (u,v) を格納した2チャンネルの配列が返ってきます.オプティカルフローの強度と方向を計算し,カラーコード化した画像を下に示します.方向はHue成分,強度はValue成分によって表されています.以下のコードを見てください:

import cv2
import numpy as np
cap = cv2.VideoCapture("vtest.avi")

ret, frame1 = cap.read()
prvs = cv2.cvtColor(frame1,cv2.COLOR_BGR2GRAY)
hsv = np.zeros_like(frame1)
hsv[...,1] = 255

while(1):
    ret, frame2 = cap.read()
    next = cv2.cvtColor(frame2,cv2.COLOR_BGR2GRAY)

    flow = cv2.calcOpticalFlowFarneback(prvs,next, None, 0.5, 3, 15, 3, 5, 1.2, 0)

    mag, ang = cv2.cartToPolar(flow[...,0], flow[...,1])
    hsv[...,0] = ang*180/np.pi/2
    hsv[...,2] = cv2.normalize(mag,None,0,255,cv2.NORM_MINMAX)
    rgb = cv2.cvtColor(hsv,cv2.COLOR_HSV2BGR)

    cv2.imshow('frame2',rgb)
    k = cv2.waitKey(30) & 0xff
    if k == 27:
        break
    elif k == ord('s'):
        cv2.imwrite('opticalfb.png',frame2)
        cv2.imwrite('opticalhsv.png',rgb)
    prvs = next

cap.release()
cv2.destroyAllWindows()

See the result below:

Dense Optical Flow

OpenCVのサンプルの中には,更に発展的な内容もあるので, samples/python2/opt_flow.py を見てみてください.

補足資料

課題

  1. OpenCVのサンプルコードの samples/python2/lk_track.py の理解に調整してみてください.
  2. OpenCVのサンプルコードの samples/python2/opt_flow.py の理解に調整してみてください.