Meanshift and Camshift

Goal

In this chapter,

• We will learn about the Meanshift and Camshift algorithms to track objects in videos.

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:

image

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 the window. Surely they don't match. So move your window such that the circle of the new window matches with the previous centroid. Again find the new centroid. Most probably, it won't match. So move it again, and continue the iterations such that the center of window and its centroid falls on the same location (or within a small desired error). So finally what you obtain is a window with maximum pixel distribution. It is marked with a green circle, named "C2". As you can see in the image, it has maximum number of points. The whole process is demonstrated on a static image below:

image

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

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 an 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 cv.inRange() function.

C++

• Downloadable code: Click here
• Code at glance:

  #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 atleast 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

• Downloadable code: Click here
• Code at glance:

  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)
  
  # 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 atleast 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 meanshift to get the new location
          ret, track_window = cv.meanShift(dst, track_window, term_crit)
  
          # Draw it on image
          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

• Downloadable code: Click here
• Code at glance:

  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;
  
          // take the first frame of the video
          capture.read(frame);
  
          //setup initial location of window
          Rect track_window = new Rect(300, 200, 100, 50);
  
          // setup initial location of window
          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);
  
          // Setup the termination criteria, either 10 iteration or move by atleast 1 pt
          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);
  
              // apply meanshift to get the new location
              Video.meanShift(dst, track_window, term_crit);
  
              // Draw it on image
              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);
      }
  }

Three frames in a video I used is given below:

image

Camshift

Did you closely watch the last result? There is a problem. Our window always has the same size whether the car is very far or very close to the 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 1998 [27] .

It applies meanshift first. Once meanshift converges, it updates the size of the window as, \(s = 2 \times \sqrt{\frac{M_{00}}{256}}\). It also calculates the orientation of the best fitting ellipse to it. Again it applies the meanshift with new scaled search window and previous window location. The process continues until the required accuracy is met.

image

Camshift in OpenCV

It is similar to meanshift, but returns a rotated rectangle (that is our result) and box parameters (used to be passed as search window in next iteration). See the code below:

C++

• Downloadable code: Click here
• Code at glance:

  #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 atleast 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

• Downloadable code: Click here
• Code at glance:

  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 atleast 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

• Downloadable code: Click here
• Code at glance:

  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;
  
          // take the first frame of the video
          capture.read(frame);
  
          //setup initial location of window
          Rect track_window = new Rect(300, 200, 100, 50);
  
          // set up the ROI for tracking
          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);
  
          // Setup the termination criteria, either 10 iteration or move by atleast 1 pt
          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);
  
              // apply camshift to get the new location
              RotatedRect rot_rect = Video.CamShift(dst, track_window, term_crit);
  
              // Draw it on image
              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);
      }
  }

Three frames of the result is shown below:

image

Additional Resources

1. French Wikipedia page on Camshift. (The two animations are taken from there)
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

Exercises

1. OpenCV comes with a Python sample for an interactive demo of camshift. Use it, hack it, understand it.