MeanShift：
如果僅僅使用特征檢測來跟蹤物體會丟失對應(yīng)物體的信息稳吮。為了解決對應(yīng)性問題殉摔，我們可以使用之前學(xué)過的特征匹配和光流法凄贩，或者淑玫，可以使用meanshift track方法崎岂。
meanshift track是一個追蹤任意物體的簡單但是有效的方法捆毫。meanshift的思想就是考慮在一個小的我們感興趣的區(qū)間（ROI）里的從潛在的概率密度函數(shù)采樣的像素來表示一個目標。
其中冲甘，灰色的點代表從某個概率分布里采樣的點绩卤。點的距離越近他們就越相似。直覺上江醇，meanshif就是在圖里找到密度最大的區(qū)域然后畫一個圈濒憋。這個算法會從不稠密的區(qū)域畫圈，然后移動圓圈到稠密的地方然后固定在哪里陶夜。如果這個場景不是點凛驮，而是對應(yīng)彩色直方圖，可以用Meanshift找到最接近目標直方圖的對象条辟。
meanshift非常適合做目標跟蹤黔夭。在opencv中使用cv2.meanShift來調(diào)用，但是需要一個預(yù)過程捂贿。大致過程如下：
- 固定一個包圍數(shù)據(jù)點的窗口：可以是一個ROI(range of interest)的bounding box
- 計算窗口內(nèi)數(shù)據(jù)的平均值纠修，一般用像素值的直方圖，通常會轉(zhuǎn)化為HSV的色彩空間
- 反復(fù)移動窗口到平均值直到收斂厂僧。這個使用cv2.meanShift完成的扣草。我們可以控制迭代的長度和精度。
CamShift
Meanshift有個不好的地方時颜屠，它框出的區(qū)域不會隨著目標的擴大（或縮谐矫睢）而擴大（或縮小）甫窟，CamShift則不會有這樣的缺點密浑。
Saliency map
在介紹實例之前，我們介紹一下特征圖粗井。使用傅里葉分析可以得到我們對自然圖片數(shù)據(jù)的一般性理解赊时，幫助我們建立一般圖片背景的模型。通過比較背景模型與指定圖片幀的不同闻丑，我們可以得到去掉背景的子區(qū)域，這樣我們的注意力就會在這些子區(qū)域上餐济。這個技術(shù)叫做Visual saliency（視覺顯著性）。
傳統(tǒng)模型試圖通過特征匹配或視覺變換來檢測目標胆剧，這需要手動的標記與訓(xùn)練絮姆，可是，如果特征和對象數(shù)量都是未知的情況呢秩霍？
這里的方法是應(yīng)用視覺顯著性的方法篙悯，立即定位到抓住我們注意力的區(qū)域（那些脫離常規(guī)的數(shù)據(jù)），這樣這個算法就可以跟蹤任意數(shù)量的物體铃绒。
就像我們的大腦會被某些圖片上的區(qū)域抓住注意力一樣鸽照，視覺顯著性試圖去描述對象們的視覺質(zhì)量，越高則越能夠引起重視匿垄，同時忽視掉較低的不重要的部分移宅。這在信息豐富的環(huán)境中無疑是一個創(chuàng)造性的策略。就像下面兩張圖中的兩根小棍椿疗，瞬間就引起你的注意：
但是如果把這些小棍雜糅在一起那么紅色的近乎垂直的小棍就很難找到：
所以，要想找到唯一的脫穎而出的目標是比較困難的糠悼，那么届榄，應(yīng)該怎么做呢，就是要讓計算機知道自己要把注意力放在什么樣的目標上倔喂。
- 傅里葉譜圖
要想找到視覺顯著的區(qū)域铝条，我們需要查看它的頻率光譜圖。一般我們都在空間域查看圖片席噩，分析像素或者圖片在各個子通道的強度班缰。然而，圖片也可以在頻率域（frequency domain）中進行表示：通過分析像素的頻率或者學(xué)習(xí)像素出現(xiàn)在圖片的周期性悼枢。
我們可以通過傅里葉變換將圖片從空間域轉(zhuǎn)換到頻率域埠忘。在頻率域中，我們不在考慮圖片的坐標馒索，而是將焦點放在圖片的譜圖上莹妒。傅里葉的根本思想就是這個問題：是否能將信號或者圖片轉(zhuǎn)化為一系列圓弧路徑（或者說：諧波），就像將太陽光里不同的光譜展示出來绰上。對比彩虹中的頻率：電磁頻率旨怠，圖片中的是空間頻率——像素值的空間周期性。比如一所監(jiān)獄的圖片蜈块，空間頻率就好比兩間鄰接監(jiān)獄的距離鉴腻。
傅里葉譜圖有兩個部分迷扇，一個是量級（magnitude），一個是相位（phase）爽哎。量級描述的是一張圖片里不同頻率的數(shù)量谋梭，相位說的是這些頻率的空間位置。
右圖是左圖的傅里葉譜圖倦青，右圖告訴我們在左圖的灰度版本中哪個頻率組件是最突出的（最亮）瓮床。譜圖是調(diào)整過的，所以圖片的中心對應(yīng)于x和y的頻率0产镐。所以隘庄，越往外，頻率越高癣亚。這張圖告訴我們左圖里有很多低頻率的組件（因為亮度都集中在中間）丑掺。
在Opencv中，這個轉(zhuǎn)換可以通過Discrete Fourier Transform(DFT)述雾，包含在Saliency類的plot_magnitude方法中街州。具體過程如下：
- 轉(zhuǎn)換圖片成灰度圖：
def plot_magnitude(self):
if len(self.frame_orig.shape)>2:
frame = cv2.cvtColor(self.frame_orig,cv2.COLOR_BGR2GRAY)
else:
frame = self.frame_orig
- 擴展圖片到一個最佳的大小：圖片大小是2的倍數(shù)時DFT的轉(zhuǎn)換速度是最快的玻孟，因此一般都用0來填充圖片唆缴。
rows, cols = self.frame_orig.shape[:2]
nrows = cv2.getOptimalDFTSize(rows)
ncols = cv2.getOptimalDFTSize(cols)
frame = cv2.copyMakeBorder(frame, 0, ncols-cols, 0, nrowsrows, cv2.BORDER_CONSTANT, value = 0)
- 應(yīng)用DFT：使用Numpy中的fft2函數(shù)，返回一個2維復(fù)數(shù)矩陣黍翎。
img_dft = np.fft.fft2(frame) - 將實數(shù)值和復(fù)數(shù)值轉(zhuǎn)換為量級：對復(fù)數(shù)取絕對值面徽，就是取模。
magn = np.abs(img_dft) - 轉(zhuǎn)換到對數(shù)量度（logarithmic scale）：傅里葉系數(shù)通常都大到無法在屏幕上顯示匣掸。一些小的和大的改變值無法觀察到趟紊。因此，高的值會成為白點碰酝，小的值為黑點霎匈。為了實現(xiàn)灰度值的可視化，將線性量度轉(zhuǎn)換為對數(shù)量度：
log_magn = np.log10(magn) - 平移：將譜圖放在中間送爸，方便觀察铛嘱。
spectrum = np.fft.fftshift(log_magn) - 返回結(jié)果：
return spectrum/np.max(spectrum)*255
- 自然統(tǒng)計規(guī)則
自然世界有很多統(tǒng)計規(guī)則，最普遍知道的大概是1/f規(guī)則碱璃。它陳述了自然圖片的集成的振幅遵從1/f 分布弄痹，也被成為尺度不變形（scale invariance維基百科）。
一張2維圖片的一維功率譜圖可以用Saliency類里的plot_power_spectrum函數(shù)來視覺化查看嵌器。我們可以用與之前量級譜圖相似的方式肛真，但我們要保證正確的將2維譜圖降到單軸上。
- 轉(zhuǎn)換圖片成灰度圖：
def plot_power_spectrum(self):
if len(self.frame_orig.shape)>2:
frame = cv2.cvtColor(self.frame_orig,cv2.COLOR_BGR2GRAY)
else:
frame = self.frame_orig
- 擴大圖片到最優(yōu)大兴健：
rows, cols = self.frame_orig.shape[:2]
nrows = cv2.getOptimalDFTSize(rows)
ncols = cv2.getOptimalDFTSize(cols)
frame = cv2.copyMakeBorder(frame, 0, ncols-cols, 0, nrowsrows, cv2.BORDER_CONSTANT, value = 0)
- 應(yīng)用DFT得到對數(shù)譜圖：這里可以選擇numpy的傅里葉方法或者opencv的傅里葉方法蚓让。
if self.use_numpy_fft:
img_dft = np.fft.fft2(frame)
spectrum = np.log10(np.real(np.abs(img_dft))**2)
else:
img_dft = cv2.dft(np.float32(frame), flags=cv2.DFT_COMPLEX_OUTPUT)
spectrum = np.log10(img_dft[:, :, 0] ** 2 + img_dft[:, :, 1] ** 2)
- 徑向平均（radial averaging）：簡單的將二維spectrum在x或y方向上取平均數(shù)是錯誤的乾忱。這被稱為徑向平均功率譜圖（radially averaged power spectrum ）。
L = max(frame.shape)
freqs = np.fft.fftfreq(L)[:L/2]
dists = np.sqrt(np.fft.fftfreq(frame.shape[0])[:,np.newaxis]**2 + np.fft.fftfreq(frame.shape[1])**2)
dcount = np.histogram(dists.ravel(), bins=freqs)[0]histo, bins = np.histogram(dists.ravel(), bins=freqs, weights=spectrum.ravel())
- 畫出結(jié)果：記得用bin的值規(guī)范化上一步累加的值
centers = (bins[:-1] + bins[1:]) / 2
plt.plot(centers, histo, dcount)
plt.xlabel('frequency')
plt.ylabel('log-spectrum')
plt.show()
結(jié)果和頻率成反比例的历极。如果要確認1/f特性窄瘟，你可以將x的值進行np.log10操作來查看曲線是否是大致上線性遞減的。這里僅僅是對y的值取對數(shù)操作趟卸，結(jié)果如下：
這個特性告訴我們?nèi)绻覀儗⑺凶匀粓D片的所有譜圖平均化蹄葱，也會得到上圖的圖片。那么锄列，如何利用這個特性來告訴我們的算法把焦點放在Limmat river圖的水上的船只而不是旁邊的樹木呢图云？
- 利用光譜殘留（spectral residual）生成特征圖
知道1/f 規(guī)則后，我們可以想到邻邮，圖片上的什么內(nèi)容會引起我們的注意呢竣况，那就是那些不遵從1/f 規(guī)則的內(nèi)容，那些異常的數(shù)據(jù)筒严，被叫做光譜殘留丹泉，對應(yīng)的就是潛在的引起我們興趣的對象。將這些異常數(shù)據(jù)以白點的形式顯示的圖片就被稱為特征圖（saliency map）鸭蛙。
光譜殘留的方法是在這里提出的：Xiaodi Hou and Liqing Zhang (2007). Saliency
Detection: A Spectral Residual Approach. IEEE Transactions on Computer
Vision and Pattern Recognition (CVPR), p.1-8. doi:
10.1109/CVPR.2007.383267.
生成特征圖需要單獨處理圖片的每個通道摹恨。
圖片的每個通道可以通過私有方法Saliency.getchannel_sal_magn來生成特征圖：
def getchannel_sal_magn(self, channel):
# 計算圖片傅里葉譜圖的量級和相位
if self.use_numpy_fft:
img_dft = np.fft.fft2(channel)
magnitude, angle = cv2.cartToPolar(np.real(img_dft), np.imag(img_dft))
else:
img_dft = cv2.dft(np.float32(channel), flags=cv2.DFT_COMPLEX_OUTPUT)
magnitude, angle = cv2.cartToPolar(img_dft[:, :, 0], img_dft[:, :, 1])
# 計算傅里葉譜圖的振幅的log值，量級的下邊界限制在1e-9规惰，防止計算log值時除數(shù)為0
log_ampl = np.log10(magnitude.clip(min=1e-9))
# 近似計算典型自然圖片的平均譜圖
log_ampl_blur = cv2.blur(log_amlp, (3, 3))
# 計算光譜殘留睬塌，大體上包括了場景里不平凡的部分。
magn = np.exp(log_amlp – log_ampl_blur)
# 通過反向的傅里葉變換計算特征圖
if self.use_numpy_fft:
real_part, imag_part = cv2.polarToCart( magn, angle)
img_combined = np.fft.ifft2(real_part + 1j*imag_part)
magnitude, = cv2.cartToPolar(np.real(imgcombined), np.imag(img_combined))
else:
img_dft[:, :, 0], img_dft[:, :, 1] = cv2.polarToCart(residual, angle)
img_combined = cv2.idft(img_dft)
magnitude, = cv2.cartToPolar(imgcombined[:, :, 0], img_combined[:, :, 1])
return magnitude
得到的單通道特征圖然后返回給Saliency.get_saliency_map函數(shù)歇万，輸入圖片的每個通道都要經(jīng)過這樣的過程，如果是灰度圖就比較簡單勋陪，只處理一個通道：
def get_saliency_map(self):
if self.need_saliency_map:
# 這一幀的特征圖還沒有計算
num_channels = 1
if len(self.frame_orig.shape)==2:
# 單個通道
sal = self.getchannel_sal_magn(self.frame_small)
else:
# 考慮每一個通道
sal = np.zeros_like(self.frame_small).astype(np.float32)
for c in xrange(self.frame_small.shape[2]):
sal[:, :, c] = self.getchannel_sal_magn(self.frame_small[:, :, c])
# 多個通道取平均
sal = np.mean(sal, 2)
# 可選的后處理，例如使結(jié)果更平滑
if self.gauss_kernel is not None:
sal = cv2.GaussianBlur(sal, self.gauss_kernel,sigmaX=8, sigmaY=0)
# 將sal的值平方诅愚，這樣可以突出高特征的區(qū)域寒锚，并將它還原到原始的分辨率并且歸一化
sal = sal**2
sal = np.float32(sal)/np.max(sal)
sal = cv2.resize(sal, self.frame_orig.shape[1::-1])
# 為了避免下一次進行這么密集的計算，將當(dāng)前結(jié)果保存违孝，并更改flag
self.saliency_map = sal
self.need_saliency_map = False
return self.saliency_map
下面是得出的特征圖：
- 檢測對象原型
在一定程度上刹前，saliency map 已經(jīng)擁有了對象原型的信息，我們要做的就是通過設(shè)置閾值獲取對象原型雌桑。
這里的代碼可以讓用戶選擇3倍于平均特征的閾值喇喉，或者使用Otsu閾值：
def get_proto_objects_map(self, use_otsu=True):
saliency = self.get_saliency_map()
if use_otsu:
# saliency的范圍是0到1所以要乘以255，并且轉(zhuǎn)為uint8型
_, img_objects = cv2.threshold(np.uint8(saliency*255), 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
else:
thresh = np.mean(saliency)*255
_, img_objects = cv2.threshold(np.uint8(saliency*255), thresh, 255, cv2.THRESH_BINARY)
return img_objects
結(jié)果如下圖：
實例：自動跟蹤足球場上所有的選手
將特征檢測得到的結(jié)果校坑，即特征圖作為meanshift的目標輸入拣技，視頻來自Alfheim數(shù)據(jù)庫千诬，可以從http://home.ifi.uio.no/paalh/dataset/alfheim/下載。
實例主要包括兩個過程：
- 將某一幀中的所有原型的bounding boxes標出膏斤。特征檢測器會在當(dāng)前幀圖片中進行操作徐绑，同時，meanshift tracker會在當(dāng)前幀中尋找上一幀里存在的原型目標莫辨。
- 只保留兩個算法檢測到的目標bounding boxes的交集傲茄，就是指兩個算法都認為這些bounding boxes框出的是正確的目標。
難點就是多目標的跟蹤沮榜，這里介紹一下它的實現(xiàn)盘榨，具體實現(xiàn)在MultiObjectTracker 類中：
新的一幀獲取后調(diào)用advance_frame函數(shù)，它有一個frame幀參數(shù)敞映，另外接受一個目標圖proto_objects_map作為參數(shù)较曼，然后對frame進行一個深拷貝：
def advance_frame(self, frame, proto_objects_map):
self.tracker = copy.deepcopy(frame)
然后該方法會建立多個bounding boxes作為候選，這些候選框中包括特征圖里的也包括從上一幀圖片到這一幀的meanshift tracking的結(jié)果：
box_all = []
# 添加從當(dāng)前目標原型圖里獲得的bouding boxes
box_all = self.appendboxes_from_saliency(proto_objects_map, box_all)
# 找到meanshift tracking在上一幀中的所有bounding boxes
box_all = self.appendboxes_from_meanshift(frame, box_all)
然后要將所有的bounding boxes合并在一起振愿，并且去掉重復(fù)的項捷犹。通過cv2.groupRectangles方法來完成，如果有group_thresh+1個或者更多的bounding boxes重復(fù)了冕末，該方法會返回一個唯一的bounding box萍歉，這樣一來，如果僅有單獨的一個bounding boxes档桃，它就會排除枪孩，即只保留交集：
if len(self.object_roi) == 0:
group_thresh = 0 # 沒有前一幀，全部bounding boxes來自于特征圖
else:
group_thresh = 1 #前一幀加上特征圖
box_grouped, _ = cv2.groupRectangles(box_all, group_thresh, 0.1)
要想使meanshift正常工作藻肄，需要記錄存留的boxes：
# 更新留存的boxes記錄
self.updatemean_shift_bookkeeping(frame, box_grouped)
然后將這些沒有重復(fù)的boxes畫出來蔑舞，并將圖片返回：
for (x, y, w, h) in box_grouped:
cv2.rectangle(self.tracker, (x, y), (x+w, y+h), (0, 255, 0), 2)
return self.tracker
-
獲取原型目標的bounding boxes
將一個原型目標圖以及一個bounding boxes的列表作為輸入，首先檢測原型目標圖的輪廓：
def appendboxes_from_saliency(self, proto_objects_map, box_all):
box_all = []
cnt_sal, = cv2.findContours(proto_objects_map, 1, 2)
去掉比閾值小的塊：
for cnt in cnt_sal:
if cv2.contourArea(cnt) < self.min_cnt_area:
continue
將結(jié)果存入box_all:
box = cv2.boundingRect(cnt)
box_all.append(box)
return box_all
-
為meanshift tracking建立必須的記錄
這個方法需要兩個參數(shù)嘹屯，分別是輸入的圖片和一系列的bounding boxes：
def updatemean_shift_bookkeeping(self, frame, box_grouped):
Bookkeeping主要保存了每個bounding box的HSV彩色值攻询，因此需要將輸入圖片轉(zhuǎn)換為HSV顏色空間：
hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
我們要保存bounding box的位置和大小，也包括HSV彩色值得彩色直方圖：
self.object_roi = [] # 彩色直方圖
self.object_box = [] # bounding box位置和大小
從box列表里抽取出box的大小和位置州弟，從HSV圖片里獲取ROI：
for box in box_grouped:
(x, y, w, h) = box
hsv_roi = hsv[y : y+h, x : x+w]
然后計算ROI中H值的直方圖钧栖，設(shè)置一個mask濾掉昏暗的區(qū)域，并規(guī)范化直方圖：
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)
然后存儲這個信息到對應(yīng)的私有變量中婆翔，在循環(huán)的下一幀可以被使用拯杠，同時在下一幀中會使用meanshift算法來找到ROI的區(qū)域：
self.object_roi.append(roi_hist)
self.object_box.append(box)
-
使用meanshift算法進行目標跟蹤
最后，通過記錄的前一幀的bookkeeping信息來跟蹤原型目標啃奴。與appendboxes_from_meanshift類似潭陪，建立一個bounding boxes的列表，它有兩個參數(shù)纺腊，分別是輸入的圖片和用來存儲bounding boxes的列表：
def appendboxes_from_meanshift(self, frame, box_all):
hsv = cv2.cvtColor(frame, cv2.COLOR_BGR2HSV)
然后這個方法解析之前存儲的原型目標：
for i in xrange(len(self.object_roi)):
roi_hist = copy.deepcopy(self.object_roi[i])
box_old = copy.deepcopy(self.object_box[i])
為了獲取新的ROI的位置畔咧，我們將ROI的反向投影作為meanshift算法的參數(shù)茎芭。終止條件（self.term_crit）保證足夠的迭代次數(shù)（100）并且均值平移至少一個像素：
dst = cv2.calcBackProject([hsv], [0], roi_hist, [0, 180], 1)
ret, box_new = cv2.meanShift(dst, tuple(box_old),self.term_crit)
在添加新的檢測到的平移的bounding box到列表之前，我們希望確認一下誓沸，是否是正確的目標梅桩。那些不動的目標通常是錯誤的正例，例如線標或者其他的與任務(wù)無關(guān)的特征塊拜隧。
為了丟棄掉無關(guān)的跟蹤結(jié)果宿百，我們比較了新舊box的所在位置：
(xo, yo, wo, ho) = box_old
(xn, yn, wn, hn) = box_new
如果它們的中心沒有移動至少sqrt(self.min_shift2)像素，我們就將他們排除：
co = [xo + wo/2, yo + ho/2]
cn = [xn + wn/2, yn + hn/2]
if (co[0] - cn[0])**2 + (co[1] - cn[1])**2 >= self.min_shift2:
box_all.append(box_new)
然后將結(jié)果返回：
return box_all
-
將上面所說的組合在一起
這個實例的關(guān)鍵點就在于洪添，通過特征圖和meanshift跟蹤的相結(jié)合垦页，排除掉了那些不動的錯誤正例。
