MeanshiftとCamshift

目次

• 目的
• Meanshift
  • OpenCV での Meanshift
• Camshift
  • OpenCV での Camshift
• 参考資料
• 演習

前のチュートリアル: 背景差分法の使い方
次のチュートリアル: オプティカルフロー

目的

本章では、

• 動画中の物体を追跡するためのMeanshiftおよびCamshiftアルゴリズムについて学ぶ。

Meanshift

Meanshiftの背後にある考え方は単純である。点の集合があるとする（ヒストグラムのバックプロジェクションのような、ピクセルの分布でもよい）。小さなウィンドウ（円でもよい）が与えられ、そのウィンドウをピクセル密度が最大（または点の数が最大）の領域へ移動させなければならない。これを下の単純な図で示す:

image

最初のウィンドウは「C1」という名前の青い円で示されている。その元の中心は「C1_o」という名前の青い四角で示されている。しかし、そのウィンドウ内の点の重心を求めると、「C1_r」という点（小さな青い円で示されている）が得られ、これがウィンドウの実際の重心である。当然ながら両者は一致しない。そこで、新しいウィンドウの円が直前の重心に一致するようにウィンドウを移動する。再び新しい重心を求める。ほとんどの場合、一致しない。そこで再び移動し、ウィンドウの中心とその重心が同じ位置に（または小さな所望の誤差の範囲内に）来るまで反復を続ける。こうして最終的に得られるのは、ピクセル分布が最大となるウィンドウである。これは「C2」という名前の緑の円で示されている。図でわかるように、点の数が最大になっている。この一連の処理を、下の静止画像上で示す:

image

そこで通常は、ヒストグラムをバックプロジェクションした画像と初期の対象位置を渡す。物体が動くと、当然その動きはヒストグラムをバックプロジェクションした画像に反映される。その結果、Meanshiftアルゴリズムはウィンドウを密度が最大となる新しい位置へ移動させる。

OpenCV での Meanshift

OpenCVでMeanshiftを使うには、まず対象を設定し、そのヒストグラムを求めて、各フレーム上で対象をバックプロジェクションしてMeanshiftの計算に使えるようにする必要がある。また、ウィンドウの初期位置も与える必要がある。ヒストグラムについては、ここでは色相 (Hue) のみを考慮する。さらに、低照度による誤った値を避けるため、低照度の値は cv.inRange() 関数を使って除外する。

C++

• ダウンロード可能なコード: こちらをクリック
• コードの概観:

  #include <iostream>
  #include <opencv2/imgcodecs.hpp>
  #include <opencv2/imgproc.hpp>
  #include <opencv2/videoio.hpp>
  #include <opencv2/highgui.hpp>
  #include <opencv2/video.hpp>
   
  using namespace cv;
  using namespace std;
   
  int main(int argc, char **argv)
  {
   const string about =
   "This sample demonstrates the meanshift algorithm.\n"
   "The example file can be downloaded from:\n"
   " https://www.bogotobogo.com/python/OpenCV_Python/images/mean_shift_tracking/slow_traffic_small.mp4";
   const string keys =
   "{ h help | | print this help message }"
   "{ @image |<none>| path to image file }";
   CommandLineParser parser(argc, argv, keys);
   parser.about(about);
   if (parser.has("help"))
   {
   parser.printMessage();
   return 0;
   }
   string filename = parser.get<string>("@image");
   if (!parser.check())
   {
   parser.printErrors();
   return 0;
   }
   
   VideoCapture capture(filename);
   if (!capture.isOpened()){
   //error in opening the video input
   cerr << "Unable to open file!" << endl;
   return 0;
   }
   
   Mat frame, roi, hsv_roi, mask;
   // take first frame of the video
   capture >> frame;
   
   // setup initial location of window
   Rect track_window(300, 200, 100, 50); // simply hardcoded the values
   
   // set up the ROI for tracking
   roi = frame(track_window);
   cvtColor(roi, hsv_roi, COLOR_BGR2HSV);
   inRange(hsv_roi, Scalar(0, 60, 32), Scalar(180, 255, 255), mask);
   
   float range_[] = {0, 180};
   const float* range[] = {range_};
   Mat roi_hist;
   int histSize[] = {180};
   int channels[] = {0};
   calcHist(&hsv_roi, 1, channels, mask, roi_hist, 1, histSize, range);
   normalize(roi_hist, roi_hist, 0, 255, NORM_MINMAX);
   
   // Setup the termination criteria, either 10 iteration or move by at least 1 pt
   TermCriteria term_crit(TermCriteria::EPS | TermCriteria::COUNT, 10, 1);
   
   while(true){
   Mat hsv, dst;
   capture >> frame;
   if (frame.empty())
   break;
   cvtColor(frame, hsv, COLOR_BGR2HSV);
   calcBackProject(&hsv, 1, channels, roi_hist, dst, range);
   
   // apply meanshift to get the new location
   meanShift(dst, track_window, term_crit);
   
   // Draw it on image
   rectangle(frame, track_window, 255, 2);
   imshow("img2", frame);
   
   int keyboard = waitKey(30);
   if (keyboard == 'q' || keyboard == 27)
   break;
   }
  }

Python

• ダウンロード可能なコード: こちらをクリック
• コードの全体像:

  import numpy as np
  import cv2 as cv
  import argparse
   
  parser = argparse.ArgumentParser(description='This sample demonstrates the meanshift algorithm. \
   The example file can be downloaded from: \
   https://www.bogotobogo.com/python/OpenCV_Python/images/mean_shift_tracking/slow_traffic_small.mp4')
  parser.add_argument('image', type=str, help='path to image file')
  args = parser.parse_args()
   
  cap = cv.VideoCapture(args.image)
   
  # 動画の最初のフレームを取得
  ret,frame = cap.read()
   
  # ウィンドウの初期位置を設定
  x, y, w, h = 300, 200, 100, 50 # 値を単純にハードコード
  track_window = (x, y, w, h)
   
  # 追跡用のROIを設定
  roi = frame[y:y+h, x:x+w]
  hsv_roi = cv.cvtColor(roi, cv.COLOR_BGR2HSV)
  mask = cv.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
  roi_hist = cv.calcHist([hsv_roi],[0],mask,[180],[0,180])
  cv.normalize(roi_hist,roi_hist,0,255,cv.NORM_MINMAX)
   
  # 終了条件を設定（10回の反復、または少なくとも1ポイント移動）
  term_crit = ( cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 1 )
   
  while(1):
   ret, frame = cap.read()
   
   if ret == True:
   hsv = cv.cvtColor(frame, cv.COLOR_BGR2HSV)
   dst = cv.calcBackProject([hsv],[0],roi_hist,[0,180],1)
   
   # meanshiftを適用して新しい位置を取得
   ret, track_window = cv.meanShift(dst, track_window, term_crit)
   
   # 画像上に描画
   x,y,w,h = track_window
   img2 = cv.rectangle(frame, (x,y), (x+w,y+h), 255,2)
   cv.imshow('img2',img2)
   
   k = cv.waitKey(30) & 0xff
   if k == 27:
   break
   else:
   break

Java

• ダウンロード可能なコード: こちらをクリック
• コードの全体像:

  import java.util.Arrays;
  import org.opencv.core.*;
  import org.opencv.highgui.HighGui;
  import org.opencv.imgproc.Imgproc;
  import org.opencv.video.Video;
  import org.opencv.videoio.VideoCapture;
   
   
  class Meanshift {
   public void run(String[] args) {
   String filename = args[0];
   VideoCapture capture = new VideoCapture(filename);
   if (!capture.isOpened()) {
   System.out.println("Unable to open file!");
   System.exit(-1);
   }
   Mat frame = new Mat(), hsv_roi = new Mat(), mask = new Mat(), roi;
   
   // 動画の最初のフレームを取得
   capture.read(frame);
   
   // ウィンドウの初期位置を設定
   Rect track_window = new Rect(300, 200, 100, 50);
   
   // ウィンドウの初期位置を設定
   roi = new Mat(frame, track_window);
   Imgproc.cvtColor(roi, hsv_roi, Imgproc.COLOR_BGR2HSV);
   Core.inRange(hsv_roi, new Scalar(0, 60, 32), new Scalar(180, 255, 255), mask);
   
   MatOfFloat range = new MatOfFloat(0, 256);
   Mat roi_hist = new Mat();
   MatOfInt histSize = new MatOfInt(180);
   MatOfInt channels = new MatOfInt(0);
   Imgproc.calcHist(Arrays.asList(hsv_roi), channels, mask, roi_hist, histSize, range);
   Core.normalize(roi_hist, roi_hist, 0, 255, Core.NORM_MINMAX);
   
   // 終了条件を設定（10回の反復、または少なくとも1ポイント移動）
   TermCriteria term_crit = new TermCriteria(TermCriteria.EPS | TermCriteria.COUNT, 10, 1);
   
   while (true) {
   Mat hsv = new Mat() , dst = new Mat();
   capture.read(frame);
   if (frame.empty()) {
   break;
   }
   Imgproc.cvtColor(frame, hsv, Imgproc.COLOR_BGR2HSV);
   Imgproc.calcBackProject(Arrays.asList(hsv), channels, roi_hist, dst, range, 1);
   
   // meanshiftを適用して新しい位置を取得
   Video.meanShift(dst, track_window, term_crit);
   
   // 画像上に描画
   Imgproc.rectangle(frame, track_window, new Scalar(255, 0, 0), 2);
   HighGui.imshow("img2", frame);
   
   int keyboard = HighGui.waitKey(30);
   if (keyboard == 'q' || keyboard == 27) {
   break;
   }
   }
   System.exit(0);
   }
  }
   
  public class MeanshiftDemo {
   public static void main(String[] args) {
   System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
   new Meanshift().run(args);
   }
  }

使用した動画の3フレームを以下に示す:

image

Camshift

直前の結果をよく見ただろうか。一つ問題がある。車がカメラから非常に遠くにあっても非常に近くにあっても、ウィンドウのサイズは常に同じである。これはよくない。対象のサイズや回転に応じてウィンドウのサイズを適応させる必要がある。ここでも解決策は「OpenCV Labs」から生まれ、CAMshift (Continuously Adaptive Meanshift) と呼ばれる。これはGary Bradskyが1998年の論文「Computer Vision Face Tracking for Use in a Perceptual User Interface」で発表したものである [41] 。

まずMeanshiftを適用する。Meanshiftが収束したら、ウィンドウのサイズを \(s = 2 \times \sqrt{\frac{M_{00}}{256}}\) として更新する。また、それに最もよく当てはまる楕円の向きも計算する。再び、新しくスケールされた探索ウィンドウと前回のウィンドウ位置でMeanshiftを適用する。必要な精度が満たされるまでこの処理を続ける。

image

OpenCV での Camshift

Meanshiftに似ているが、回転矩形（これが結果である）とボックスのパラメータ（次の反復で探索ウィンドウとして渡される）を返す。以下のコードを参照:

C++

• ダウンロード可能なコード: こちらをクリック
• コードの概観:

  #include <iostream>
  #include <opencv2/imgcodecs.hpp>
  #include <opencv2/imgproc.hpp>
  #include <opencv2/videoio.hpp>
  #include <opencv2/highgui.hpp>
  #include <opencv2/video.hpp>
   
  using namespace cv;
  using namespace std;
   
  int main(int argc, char **argv)
  {
   const string about =
   "This sample demonstrates the camshift algorithm.\n"
   "The example file can be downloaded from:\n"
   " https://www.bogotobogo.com/python/OpenCV_Python/images/mean_shift_tracking/slow_traffic_small.mp4";
   const string keys =
   "{ h help | | print this help message }"
   "{ @image |<none>| path to image file }";
   CommandLineParser parser(argc, argv, keys);
   parser.about(about);
   if (parser.has("help"))
   {
   parser.printMessage();
   return 0;
   }
   string filename = parser.get<string>("@image");
   if (!parser.check())
   {
   parser.printErrors();
   return 0;
   }
   
   VideoCapture capture(filename);
   if (!capture.isOpened()){
   //error in opening the video input
   cerr << "Unable to open file!" << endl;
   return 0;
   }
   
   Mat frame, roi, hsv_roi, mask;
   // take first frame of the video
   capture >> frame;
   
   // setup initial location of window
   Rect track_window(300, 200, 100, 50); // simply hardcoded the values
   
   // set up the ROI for tracking
   roi = frame(track_window);
   cvtColor(roi, hsv_roi, COLOR_BGR2HSV);
   inRange(hsv_roi, Scalar(0, 60, 32), Scalar(180, 255, 255), mask);
   
   float range_[] = {0, 180};
   const float* range[] = {range_};
   Mat roi_hist;
   int histSize[] = {180};
   int channels[] = {0};
   calcHist(&hsv_roi, 1, channels, mask, roi_hist, 1, histSize, range);
   normalize(roi_hist, roi_hist, 0, 255, NORM_MINMAX);
   
   // Setup the termination criteria, either 10 iteration or move by at least 1 pt
   TermCriteria term_crit(TermCriteria::EPS | TermCriteria::COUNT, 10, 1);
   
   while(true){
   Mat hsv, dst;
   capture >> frame;
   if (frame.empty())
   break;
   cvtColor(frame, hsv, COLOR_BGR2HSV);
   calcBackProject(&hsv, 1, channels, roi_hist, dst, range);
   
   // apply camshift to get the new location
   RotatedRect rot_rect = CamShift(dst, track_window, term_crit);
   
   // Draw it on image
   Point2f points[4];
   rot_rect.points(points);
   for (int i = 0; i < 4; i++)
   line(frame, points[i], points[(i+1)%4], 255, 2);
   imshow("img2", frame);
   
   int keyboard = waitKey(30);
   if (keyboard == 'q' || keyboard == 27)
   break;
   }
  }

Python

• ダウンロード可能なコード: こちらをクリック
• コードの概観:

  import numpy as np
  import cv2 as cv
  import argparse
   
  parser = argparse.ArgumentParser(description='This sample demonstrates the camshift algorithm. \
   The example file can be downloaded from: \
   https://www.bogotobogo.com/python/OpenCV_Python/images/mean_shift_tracking/slow_traffic_small.mp4')
  parser.add_argument('image', type=str, help='path to image file')
  args = parser.parse_args()
   
  cap = cv.VideoCapture(args.image)
   
  # take first frame of the video
  ret,frame = cap.read()
   
  # setup initial location of window
  x, y, w, h = 300, 200, 100, 50 # simply hardcoded the values
  track_window = (x, y, w, h)
   
  # set up the ROI for tracking
  roi = frame[y:y+h, x:x+w]
  hsv_roi = cv.cvtColor(roi, cv.COLOR_BGR2HSV)
  mask = cv.inRange(hsv_roi, np.array((0., 60.,32.)), np.array((180.,255.,255.)))
  roi_hist = cv.calcHist([hsv_roi],[0],mask,[180],[0,180])
  cv.normalize(roi_hist,roi_hist,0,255,cv.NORM_MINMAX)
   
  # Setup the termination criteria, either 10 iteration or move by at least 1 pt
  term_crit = ( cv.TERM_CRITERIA_EPS | cv.TERM_CRITERIA_COUNT, 10, 1 )
   
  while(1):
   ret, frame = cap.read()
   
   if ret == True:
   hsv = cv.cvtColor(frame, cv.COLOR_BGR2HSV)
   dst = cv.calcBackProject([hsv],[0],roi_hist,[0,180],1)
   
   # apply camshift to get the new location
   ret, track_window = cv.CamShift(dst, track_window, term_crit)
   
   # Draw it on image
   pts = cv.boxPoints(ret)
   pts = np.int0(pts)
   img2 = cv.polylines(frame,[pts],True, 255,2)
   cv.imshow('img2',img2)
   
   k = cv.waitKey(30) & 0xff
   if k == 27:
   break
   else:
   break

Java

• ダウンロード可能なコード: こちらをクリック
• コードの全体像:

  import java.util.Arrays;
  import org.opencv.core.*;
  import org.opencv.highgui.HighGui;
  import org.opencv.imgproc.Imgproc;
  import org.opencv.video.Video;
  import org.opencv.videoio.VideoCapture;
   
   
  class Camshift {
   public void run(String[] args) {
   String filename = args[0];
   VideoCapture capture = new VideoCapture(filename);
   if (!capture.isOpened()) {
   System.out.println("Unable to open file!");
   System.exit(-1);
   }
   
   Mat frame = new Mat(), hsv_roi = new Mat(), mask = new Mat(), roi;
   
   // 動画の最初のフレームを取得
   capture.read(frame);
   
   // ウィンドウの初期位置を設定
   Rect track_window = new Rect(300, 200, 100, 50);
   
   // 追跡用のROIを設定
   roi = new Mat(frame, track_window);
   Imgproc.cvtColor(roi, hsv_roi, Imgproc.COLOR_BGR2HSV);
   Core.inRange(hsv_roi, new Scalar(0, 60, 32), new Scalar(180, 255, 255), mask);
   
   MatOfFloat range = new MatOfFloat(0, 256);
   Mat roi_hist = new Mat();
   MatOfInt histSize = new MatOfInt(180);
   MatOfInt channels = new MatOfInt(0);
   Imgproc.calcHist(Arrays.asList(hsv_roi), channels, mask, roi_hist, histSize, range);
   Core.normalize(roi_hist, roi_hist, 0, 255, Core.NORM_MINMAX);
   
   // 終了条件を設定（10回の反復、または少なくとも1ポイント移動）
   TermCriteria term_crit = new TermCriteria(TermCriteria.EPS | TermCriteria.COUNT, 10, 1);
   
   while (true) {
   Mat hsv = new Mat() , dst = new Mat();
   capture.read(frame);
   if (frame.empty()) {
   break;
   }
   Imgproc.cvtColor(frame, hsv, Imgproc.COLOR_BGR2HSV);
   Imgproc.calcBackProject(Arrays.asList(hsv), channels, roi_hist, dst, range, 1);
   
   // camshiftを適用して新しい位置を取得
   RotatedRect rot_rect = Video.CamShift(dst, track_window, term_crit);
   
   // 画像上に描画
   Point[] points = new Point[4];
   rot_rect.points(points);
   for (int i = 0; i < 4 ;i++) {
   Imgproc.line(frame, points[i], points[(i+1)%4], new Scalar(255, 0, 0),2);
   }
   
   HighGui.imshow("img2", frame);
   int keyboard = HighGui.waitKey(30);
   if (keyboard == 'q'|| keyboard == 27) {
   break;
   }
   }
   System.exit(0);
   }
  }
   
  public class CamshiftDemo {
   public static void main(String[] args) {
   System.loadLibrary(Core.NATIVE_LIBRARY_NAME);
   new Camshift().run(args);
   }
  }

結果の3フレームを以下に示す:

image

参考資料

1. Camshiftに関するフランス語版Wikipediaのページ Camshift。（2つのアニメーションはそこから引用している）
2. 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

演習

1. OpenCV には camshift の対話的なデモを行う Python の サンプル が付属している。実際に使い、いじり、理解してほしい。