.. _meanshift:


Meanshift と Camshift
****************************


目的
========

このチュートリアルでは
    * 同画像中に写る物体を発見・追跡するためのMeanshift，Camshiftアルゴリズムについて学びます．
    
Meanshift
============

Meanshiftアルゴリズムのアイディアの直感的理解は単純です．点の集合(ヒストグラムの逆投影法のような画素の分布など)があるとします．あなたのタスクは，与えられた小さなウィンドウを移動し，画素の分布密度(もしくは画素数)が最大になる領域にウィンドウの位置を合わせることです．以下の図に示すような状況になります:

    .. image:: images/meanshift_basics.jpg
        :alt: Intuition behind meanshift
        :align: center

最初に与えられたウィンドウは "C1" と名付けられ青い円で描かれています． "C1" の中心 "C1_o" は青い四角形でマークされています．window内に位置する点群の重心を "C1_r" (小さい青い円でマークされている)とします．この二点("C1_o" と "C1_r")は確実に異なる点ですよね．なので，ウィンドウが重心 "C1_r" に重なるように移動させます．再びウィンドウ内に位置する点群の重心を計算します．おそらく今回もwindow内の重心と円の中心は重なりませんよね．この重心の計算と円の移動を二点が重なるまで(もしくは二点の距離が許容誤差範囲に収まるまで)繰り返します．最終的に画素の分布密度が最大となる位置にウィンドウが移動します．この時の円 "C2" を緑色で描いています．下の画像を見れば分かるように，緑色の円の中に最も点が密集しています．以下のアニメーションがmeanshiftアルゴリズムを使った物体追跡の全体的な流れを説明しています:

    .. image:: images/meanshift_face.gif
        :alt: Meanshift on static image
        :align: center

普通はヒストグラムを逆投影した画像と対象物体の初期位置を指定します．物体が動くと，その動きはヒストグラムを逆投影した画像中にはっきりと反映されます．結果として，meanshiftアルゴリズムはウィンドウを密度が最大となる場所へと移動させます．


OpenCVにおけるMeanshift
------------------------------

OpenCVでmeanshiftを使うためには，まず初めに追跡対象を設定し，対象のヒストグラムを計算する必要があります．そうすればmeanshiftの計算をする際に，追跡対象を各フレームに対して逆投影できます．また，ウィンドウの初期位置も設定する必要が有ります．ここで紹介する例ではHue成分のみを考慮します．暗い光源化での追跡失敗を防ぐために， **cv2.inRange()** 関数を使って暗い画素値を無視するようにしています．
::

    import numpy as np
    import cv2

    cap = cv2.VideoCapture('slow.flv')

    # take first frame of the video
    ret,frame = cap.read()

    # setup initial location of window
    r,h,c,w = 250,90,400,125  # simply hardcoded the values
    track_window = (c,r,w,h)

    # set up the ROI for tracking
    roi = frame[r:r+h, c:c+w]
    hsv_roi =  cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
    mask = cv2.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
    roi_hist = cv2.calcHist([hsv_roi],[0],mask,[180],[0,180])
    cv2.normalize(roi_hist,roi_hist,0,255,cv2.NORM_MINMAX)

    # Setup the termination criteria, either 10 iteration or move by atleast 1 pt
    term_crit = ( cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 1 )

    while(1):
        ret ,frame = cap.read()
        
        if ret == True:
            hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
            dst = cv2.calcBackProject([hsv],[0],roi_hist,[0,180],1)
            
            # apply meanshift to get the new location
            ret, track_window = cv2.meanShift(dst, track_window, term_crit)

            # Draw it on image
            x,y,w,h = track_window
            img2 = cv2.rectangle(frame, (x,y), (x+w,y+h), 255,2)   
            cv2.imshow('img2',img2)
            
            k = cv2.waitKey(60) & 0xff
            if k == 27:
                break
            else:
                cv2.imwrite(chr(k)+".jpg",img2)
            
        else:
            break    

    cv2.destroyAllWindows()
    cap.release()
    

以下に，テストに使用した動画像中の3フレームを示します:

    .. image:: images/meanshift_result.jpg
        :alt: Meanshift result
        :align: center
        

Camshift
============

上記の結果をよく観察しましたか？実は問題がありました．追跡対象である車が近づいてきているのに対して，追跡に使用したウィンドウは常に同じサイズです．これはよくありません．追跡対象の見え方によってウィンドウのサイズを調節する必要があります．Gary Bradskが1988年に発表した "Computer Vision Face Tracking for Use in a Perceptual User Interface" で提案されたCAMshift (Continuously Adaptive Meanshift) を使えばこの問題を解決できます．

まず初めにmeanshiftアルゴリズムを適用します．meanshiftアルゴリズムの計算が収束したら :math:`s = 2 \times \sqrt{\frac{M_{00}}{256}}` という風にウィンドウサイズを変更します．同時に対象物体に最もフィットする楕円の回転角を計算します．再びmeanshiftアルゴリズムを適用しますが，サイズを変更したウィンドウと前回の収束場所から計算を始めます．このように，meanshiftアルゴリズムとウィンドウサイズの更新を収束条件が満たされるまで繰り返すのがCAMshiftアルゴリズムです．

    .. image:: images/camshift_face.gif
        :alt: Meanshift on static image
        :align: center


OpenCVでのCamshift
---------------------

meanshiftアルゴリズムとほとんど同じですが，返戻値が回転した矩形とそのパラメータという点が異なります．コードは以下のようになります:
::

    import numpy as np
    import cv2

    cap = cv2.VideoCapture('slow.flv')

    # take first frame of the video
    ret,frame = cap.read()

    # setup initial location of window
    r,h,c,w = 250,90,400,125  # simply hardcoded the values
    track_window = (c,r,w,h)

    # set up the ROI for tracking
    roi = frame[r:r+h, c:c+w]
    hsv_roi =  cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
    mask = cv2.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
    roi_hist = cv2.calcHist([hsv_roi],[0],mask,[180],[0,180])
    cv2.normalize(roi_hist,roi_hist,0,255,cv2.NORM_MINMAX)

    # Setup the termination criteria, either 10 iteration or move by atleast 1 pt
    term_crit = ( cv2.TERM_CRITERIA_EPS | cv2.TERM_CRITERIA_COUNT, 10, 1 )

    while(1):
        ret ,frame = cap.read()
        
        if ret == True:
            hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
            dst = cv2.calcBackProject([hsv],[0],roi_hist,[0,180],1)
            
            # apply meanshift to get the new location
            ret, track_window = cv2.CamShift(dst, track_window, term_crit)

            # Draw it on image
            pts = cv2.boxPoints(ret)
            pts = np.int0(pts)        
            img2 = cv2.polylines(frame,[pts],True, 255,2)   
            cv2.imshow('img2',img2)
          
            k = cv2.waitKey(60) & 0xff
            if k == 27:
                break
            else:
                cv2.imwrite(chr(k)+".jpg",img2)
            
        else:
            break    

    cv2.destroyAllWindows()
    cap.release()
    
Three frames of the result is shown below:

    .. image:: images/camshift_result.jpg
        :alt: Camshift result
        :align: center
        

補足資料
=============================

#. Wikipedia(フランス語　の `Camshift <http://fr.wikipedia.org/wiki/Camshift>`_ のページ(このチュートリアルで使用したアニメーションの出典元です)

#. Bradski, G.R., "Real time face and object tracking as a component of a perceptual user interface," Applications of Computer Vision, 1998. WACV '98. Proceedings., Fourth IEEE Workshop on , vol., no., pp.214,219, 19-21 Oct 1998


課題
===============

#. OpenCVのサンプルにcamshiftのデモがあります．色々と遊んでみてください．