OpenCV  4.1.2
Open Source Computer Vision
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.

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 [Bradski98] .

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:

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.
cv::meanShift
int meanShift(InputArray probImage, Rect &window, TermCriteria criteria)
Finds an object on a back projection image.
cv::Point_< float >
cv::rectangle
void rectangle(InputOutputArray img, Rect rec, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
cv::TermCriteria
The class defining termination criteria for iterative algorithms.
Definition: types.hpp:852
cv::NORM_MINMAX
flag
Definition: base.hpp:207
cv::calcBackProject
void calcBackProject(const Mat *images, int nimages, const int *channels, InputArray hist, OutputArray backProject, const float **ranges, double scale=1, bool uniform=true)
Calculates the back projection of a histogram.
cv::cvtColor
void cvtColor(InputArray src, OutputArray dst, int code, int dstCn=0)
Converts an image from one color space to another.
cv::COLOR_BGR2HSV
convert RGB/BGR to HSV (hue saturation value), color conversions
Definition: imgproc.hpp:583
cv::calcBackProject
void calcBackProject(InputArrayOfArrays images, const std::vector< int > &channels, InputArray hist, OutputArray dst, const std::vector< float > &ranges, double scale)
cv::inRange
void inRange(InputArray src, InputArray lowerb, InputArray upperb, OutputArray dst)
Checks if array elements lie between the elements of two other arrays.
cv::normalize
void normalize(const SparseMat &src, SparseMat &dst, double alpha, int normType)
cv::VideoCapture
Class for video capturing from video files, image sequences or cameras.
Definition: videoio.hpp:603
cv::waitKey
int waitKey(int delay=0)
Waits for a pressed key.
cv::TermCriteria::COUNT
the maximum number of iterations or elements to compute
Definition: types.hpp:860
cv::TermCriteria::EPS
the desired accuracy or change in parameters at which the iterative algorithm stops
Definition: types.hpp:862
cv::boxPoints
void boxPoints(RotatedRect box, OutputArray points)
Finds the four vertices of a rotated rect. Useful to draw the rotated rectangle.
highgui.hpp
cv::line
void line(InputOutputArray img, Point pt1, Point pt2, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
Draws a line segment connecting two points.
cv::rectangle
void rectangle(InputOutputArray img, Point pt1, Point pt2, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
Draws a simple, thick, or filled up-right rectangle.
imgcodecs.hpp
video.hpp
cv::RotatedRect
The class represents rotated (i.e. not up-right) rectangles on a plane.
Definition: types.hpp:503
cv::polylines
void polylines(InputOutputArray img, InputArrayOfArrays pts, bool isClosed, const Scalar &color, int thickness=1, int lineType=LINE_8, int shift=0)
Draws several polygonal curves.
cv::Rect_
Template class for 2D rectangles.
Definition: types.hpp:420
cv::imshow
void imshow(const String &winname, InputArray mat)
Displays an image in the specified window.
cv::calcHist
void calcHist(InputArrayOfArrays images, const std::vector< int > &channels, InputArray mask, OutputArray hist, const std::vector< int > &histSize, const std::vector< float > &ranges, bool accumulate=false)
cv::RotatedRect::points
void points(Point2f pts[]) const
cv::CamShift
RotatedRect CamShift(InputArray probImage, Rect &window, TermCriteria criteria)
Finds an object center, size, and orientation.
cv::Scalar
Scalar_< double > Scalar
Definition: types.hpp:669
cv::calcHist
void calcHist(const Mat *images, int nimages, const int *channels, InputArray mask, OutputArray hist, int dims, const int *histSize, const float **ranges, bool uniform=true, bool accumulate=false)
Calculates a histogram of a set of arrays.
cv::Mat
n-dimensional dense array class
Definition: mat.hpp:791
cv::imshow
void imshow(const String &winname, const ogl::Texture2D &tex)
Displays OpenGL 2D texture in the specified window.
cv::CommandLineParser
Designed for command line parsing.
Definition: utility.hpp:831
cv
"black box" representation of the file storage associated with a file on disk.
Definition: affine.hpp:51
imgproc.hpp
cv::gapi::mask
GMat mask(const GMat &src, const GMat &mask)
Applies a mask to a matrix.
cv::normalize
static Vec< _Tp, cn > normalize(const Vec< _Tp, cn > &v)
videoio.hpp