Video Analysis - Meanshift and CAMshift

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:

Meanshift의 원리는 간단하다. 우선 어떤 공간에 많은 점들이 있다고 가정해 보자 (Histogram backprojection으로 분포된 픽셀일 수도 있다). 그 공간에 속이 빈 작은 창(또는 원)을 놓고 점의 밀도가 가장 높은 곳으로 그 창을 움직여야 한다 (가능한 많은 점들을 포함 하도록). 간단히 그림으로 표현하면 아래와 같다.

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

파란창(원) C1의 처음 중심 위치는 파란 사각형의 "C1_o"이다. 하지만 이 원의 실제 무게중심(centroid)은 "C1_r"이다 (파란 원). 이 둘은 일치하지 않는다. 그럼 원의 중심이 무게 중심과 일치 하도록 원을 이동시켜 보자. 그리고 다시 원의 무게 중심을 찾는다. 아마 다시 일치 하지 않을 것이다. 다시 원을 이동시켜 원의 중심과 무게 중심이 일치하도록(혹은 무시할 만한 오차가 될 때 까지) 반복 한다. 결국 원 안 점들의 밀도가 최대가 되는 지점을 얻게 될 것이다. 이 지점은 녹색 원 "C2"로 표시 되었다. 그림에서 알 수 있듯이, 이 원에 가장 많은 점들이 들어가게 된다. 전체 과정은 아래 이미지에 표현 되어 있다.

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

일반적으로 histogram backprojected image와 초기 target의 위치를 알려 준다. 물체가 움직이면 histogram backprojected image에 움직임이 반영 되고 그 결과, meanshift 알고리즘이 밀도가 가장 높은 곳으로 원을 옮기게 된다.

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

OpenCV에서 meanshift를 이용하기 위해서는 우선 target을 지정하고 target의 histogram을 계산해야 한다. 이 histogram으로 각 frame에서 target을 backproject하여 meanshift를 계산한다. 잘못된 값이 나오는걸 막기 위해 너무 낮은 light 값은 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(roi, 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()

Three frames in a video I used is given below:

아래 사진들은 위 코드에 사용된 video에서 추출한 프레임들이다.

Camshift

Did you closely watch the last result? There is a problem. Our window always has the same size when car is farther away and it is very close to 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 1988.

위 코드의 결과를 확인하면 문제점을 찾을 수 있다. 자동차가 멀리 있거나 가까이 있는거에 상관 없이 창은 항상 일정한 크기이다. 바람직한 현상은 아니다. Target의 크기와 회전 상태에 따라 창의 크기도 변경되어야 한다. 이에 "OpenCV Labs"의 Gary Bradsky가 1988년 발표한 논문 "Computer Vision Face Tracking for Use in a Perceptual User Interface에서 CAMshift (Continuously Adaptive Meanshift)라는 해결책을 제시 하였다.

It applies meanshift first. Once meanshift converges, it updates the size of the window as, . It also calculates the orientation of best fitting ellipse to it. Again it applies the meanshift with new scaled search window and previous window location. The process is continued until required accuracy is met.

CAMshift는 우선 meanshift를 적용 한다. Meanshift가 한 점으로 수렴하면 창의 사이즈를 로 변경하고 target에 꼭 맞는 타원의 방향을 계산한다. 그리고 다시 크기가 변경된 search window와 이전 창의 위치를 이용해 meanshift를 적용한다. 이 과정은 충분히 정확한 결과를 얻을 때 까지 계속 된다.

Camshift in OpenCV

It is almost same as meanshift, but it 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:

Meanshift와 거의 비슷하지만 회전된 사각형과 box parameter(다음 iteration을 위해 search window 값으로 넘겨진다)를 반환 한다는 점이 다르다. 아래 코드를 보자.

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(roi, 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:

아래 사진들은 위 코드에 사용된 video에서 추출한 프레임들이다.

import cv2
import numpy as np
 
roi = None
drag_start = None
mouse_status = 0
tracking_start = False
 
def onMouse(event, x, y, flags, param = None):
    global roi
    global drag_start
    global mouse_status
    global tracking_start
    
    if event == cv2.EVENT_LBUTTONDOWN:
        drag_start = (x, y)
        roi = (0, 0, 0, 0) # ROI를 재설정하는 경우를 위한 초기화
        tracking_start = False
    elif event == cv2.EVENT_MOUSEMOVE:
        if flags == cv2.EVENT_FLAG_LBUTTON:
            xmin = min(x, drag_start[0])
            ymin = min(y, drag_start[1])
            xmax = max(x, drag_start[0])
            ymax = max(y, drag_start[1])
            roi = (xmin, ymin, xmax, ymax)
            mouse_status = 1
    elif event == cv2.EVENT_LBUTTONUP:
        mouse_status = 2
 
cv2.namedWindow('meanShift tracking')
cv2.setMouseCallback('meanShift tracking', onMouse)
 
cap = cv2.VideoCapture(0)
if(not cap.isOpened()):
    print('Error opening video')
height, width = (int(cap.get(cv2.CAP_PROP_FRAME_HEIGHT)), int(cap.get(cv2.CAP_PROP_FRAME_WIDTH)))
roi_mask = np.zeros((height, width), dtype = np.uint8)
term_crit = (cv2.TERM_CRITERIA_MAX_ITER + cv2.TERM_CRITERIA_EPS, 10, 1)
 
while True:
    ret, meanframe = cap.read()
    if not ret:
        break
    
    camframe = meanframe.copy()
    hsv = cv2.cvtColor(meanframe, cv2.COLOR_BGR2HSV)
    mask = cv2.inRange(hsv, (0., 60., 32.), (180., 255., 255.))
    # Checks if array elements lie between the elements of two other arrays.
 
    if mouse_status == 1:
        x1, y1, x2, y2 = roi
        cv2.rectangle(meanframe, (x1, y1), (x2, y2), (255, 0, 0), 2)
 
    if mouse_status == 2:
        print('Initializing...', end = ' ')
        mouse_status = 0
        x1, y1, x2, y2 = roi
        if (np.abs(x1 - x2) < 10) or (np.abs(y1 - y2) < 10):
            print('failed. Too small ROI. (Width: %d, Height: %d)' %(np.abs(x1 - x2), np.abs(y1 - y2)))
            continue
 
        mask_roi = mask[y1:y2, x1:x2]
        hsv_roi = hsv[y1:y2, x1:x2]
 
        hist_roi = cv2.calcHist([hsv_roi], [0], mask_roi, [16], [0, 180])
        cv2.normalize(hist_roi, hist_roi, 0, 255, cv2.NORM_MINMAX)
        track_window1 = (x1, y1, x2 - x1, y2 - y1)
        track_window2 = (x1, y1, x2 - x1, y2 - y1)
        tracking_start = True
        print('Done.')
 
    if tracking_start:
        backP = cv2.calcBackProject([hsv], [0], hist_roi, [0, 180], 1)
        # Calculates the back projection of a histogram.
        backP &= mask
        cv2.imshow('backP', backP)
 
        ret, track_window1 = cv2.meanShift(backP, track_window1, term_crit)
        # Finds an object on a back projection image.
        x, y, w, h = track_window1
        cv2.rectangle(meanframe, (x, y), (x + w, y + h), (0, 0, 255), 2)
 
        track_box, track_window2 = cv2.CamShift(backP, track_window2, term_crit)
        # Finds an object center, size, and orientation.
        x, y, w, h = track_window2
        cv2.rectangle(camframe, (x, y), (x + w, y + h), (0, 255, 0), 2)
        cv2.ellipse(camframe, track_box, (0, 255, 255), 2)
        pts = cv2.boxPoints(track_box) # Finds the four vertices of a rotated rect.
        pts = np.int0(pts)
        dst = cv2.polylines(camframe, [pts], True, (0, 0, 255), 2)
 
    cv2.imshow('meanShift tracking', meanframe)
    cv2.imshow('CamShift tracking', camframe)
    key = cv2.waitKey(25)
    if key == 27:
        break
 
if cap.isOpened():
    cap.release()
cv2.destroyAllWindows()