基于MeanShift算法的目標(biāo)跟蹤

1、基于meanshift算法的目標(biāo)跟蹤1算法描述1.1 meanshift算法背景meanshift這個概念是由fukunage在1975 年提111的，fukunage等人在一篇尖丁概 率密度梯度函數(shù)的佔計中捉出這一概念。其敁初的含義:如其名：偏移的均值向s;但隨著 理論的發(fā)展，meanshift的含義己經(jīng)發(fā)生了很多變化。如今，我們說的meanshift算法，一般 是指一個迭代的步驟，即先算出當(dāng)前點的偏移均值，然后以此為新的起始點，繼續(xù)移動，直 到滿足一定的結(jié)束條件。在很長一段時i川內(nèi)，meanshift算法都沒杏得到足夠的重視，直到1995年另一篇重要論 文的發(fā)表。該論文的作者yizong

2、cheng定義了一族核函數(shù)，使得隨卷樣本與被偏移點的距 離不同，其偏移暈對均值偏移m暈的貢獻(xiàn)也不同。其次，他還設(shè)定了一個權(quán)重系數(shù)，使得不 同樣木點的重要性不一樣，這人人擴(kuò)展了 meanshift的疢用范喇。此外，還有研究人員將非 剛體的跟蹤問題近似為一個iwanshift的敁優(yōu)化問題，使得跟蹤可以實時進(jìn)行。目前，利用 meanshift進(jìn)行跟蹤己經(jīng)相當(dāng)成熟。1.2 meanshift算法原理meanshift可以應(yīng)用在很多領(lǐng)域，比如聚類，閣像平滑，圖像分割，還在目標(biāo)跟蹤領(lǐng)域 有重要的應(yīng)川。meanshift跟蹤算沾足通過計算候選0標(biāo)與0標(biāo)模板之間相似度的概率密度 分布，然后利用概率密度梯度下降

3、的方向來獲収匹配搜索的最佳路徑，加速運動r標(biāo)的定位 和降低搜索的時間，因此其在fi標(biāo)實時跟蹤領(lǐng)域有著很高的應(yīng)用價值。該算法由于采川了統(tǒng)計特征，因此對噪聲具奮很好的魯棒性；由于是一個缶參數(shù)算法, 容易作為一個模塊和其他算法集成：采用核函數(shù)直方閣建模，對邊緣肌擋、目標(biāo)的旋轉(zhuǎn)、變 形以及背景運動都不敏感；同時該算法構(gòu)造丫一個可以用meanshift算法進(jìn)行尋優(yōu)的相似度 函數(shù)。meanshift本質(zhì)上是最陡下降法，因此其求解過程收斂速度快，使得該算法其有很好 的實用性。meanshift算法的思想足利川概率密度的梯度爬升來尋找局部最優(yōu)。它要做的就是輸入 一個在閣像的范m,然p直朝著重心迭代,h到滿足你

4、的要求成者達(dá)到迭代最人次數(shù)結(jié)來。 在openev中，進(jìn)行meanshift jt實很簡單，輸入一張圖像（imgprob），再輸入一個7t始迭 代的力*框（windowln）和一個迭代條件（criteria），輸出的是迭代完成的位置（comp ）。 這是闌數(shù)原型：int cvmeanshift（ const void* imgprob, cvrect windowln，cvtermcriteria criteria, cvconnectedcomp* comp ）參數(shù)介紹：imgprob： m標(biāo)直方圖的反向投影windowln:初試的搜索框criteria：確定搜索窗口的終止條件comp：生成的

5、結(jié)構(gòu)，包含收斂的搜索窗u坐稱（comp->rect宇段）與窗u內(nèi)部所存像素的 和（comp->arca 字段）1.3 meanshift算法跟蹤目標(biāo)實現(xiàn)步驟| .首先從攝像頭或者本地文件讀入視頻2. 選擇耍跟蹤的物體，程序讀取一幀視頻3. 計算視頻幀的色調(diào)直方圖4. 計算視頻幀的反4投影圖5. 輸入反向投影圖和跟蹤矩形框，調(diào)用meanshift算法迭代，尋找局部最優(yōu)解。根據(jù)重心的 移動，調(diào)整跟蹤矩形框6. 讀取k一幀視頻，川當(dāng)前矩形桐作為輸入，重復(fù)執(zhí)行步驟2-51.4 meanshift算法實現(xiàn)過程1在顏色概率分布圖屮選取搜索窗w2計算零階距：x y汁算一階距：x yx y計算搜索

6、窗的質(zhì)心：= af10 / a/oo ;)c = a/則 / a/。3調(diào)整搜索窗大小寬度為s = yj aoo / 2 5 6長度為1.2s4移動搜索窗的中心到質(zhì)心，如來移動距離大于預(yù)設(shè)的同定閾值，則熏復(fù)2)3)4)，直到搜索 窗的中心與質(zhì)心間的移動距離小于預(yù)設(shè)的岡定閾值，或者循環(huán)運p:的次數(shù)達(dá)到某一敁人值, 停止計算。1.5 meanshift算法跟蹤效果使用攝像頭跟蹤人的膚色效果如圖1.5.1所示。圖 1.5.1對應(yīng)于圖1.5.1的反向投影圖如下圖1.5.2所示。圖 1.5.2點選區(qū)域的像索點直方圖如圖1.5.3所示。圖 1.5.3從以上效果圖可以發(fā)現(xiàn)，meanshift算法處理的是hsv

7、屮的色調(diào)分朵。換化話說，就是 通過追蹤相同的顏色，而達(dá)到追蹤物體的功能。程序首先計算點選框里的冇效像索點，通過 統(tǒng)計獲得像素點分布直方圖；然后計算岀視頻的反向投影圖，即是像素點的概率分布圖。如 上圖1.5.2所示，越亮的點就是與原物體越匹配的點，大量的亮點的聚集處就極有可能是需 耍跟蹤的物體；最后用矩形框框住當(dāng)前幀中帶跟蹤的物體，如上閣1.5.1所示的結(jié)果。當(dāng)被跟蹤的物體的色調(diào)與背景相似吋，跟蹤就會失效，如圖1.5.4所示。圖 1.5.4品然，當(dāng)背景與被跟蹤物體顏色難以區(qū)分吋跟蹤會失敗。原因很簡單，meanshift兌法 實現(xiàn)跟蹤的原理就是通過計算色調(diào)的概率分布達(dá)到跟蹤的效果，所以待跟蹤的物體

8、一定耍與 背景在色調(diào)上柯區(qū)分度。類似的，本程序也可以通過設(shè)s:調(diào)試-命令參數(shù)，使川本地的視頻文件來實現(xiàn)視頻屮 特定物體的跟蹤，具體方法如圖1.5.5所示。由于實驗的效果與使用攝像頭跟蹤物體差不多， 所以就不一一截圖顯示了。圖 1.5.52程序源碼與數(shù)據(jù)結(jié)構(gòu)#includc<stdlih.h>#include "stdafx.h"#ifdef_ch_#pragma package <opencv>#endif#ifndef jeic #inclucle <stdio.h> #include "cv.h" #include

9、 "highgui.li" #includc <ctypc.h> #endifipllmage * image = 0, *hsv = 0, *hue = 0, *mask = 0, *backproject = 0, *histimg = 0 /用hsv屮的hue分量進(jìn)行跟蹤 cvhistogram *hist = 0;/直方圖類int backproject_mode = 0;int selectobject = 0;int trackobject = 0;int showhist = 1;cvpoint origin;cvrect selection;cv

10、rect track一window;cvbox2d track_box;/meanshift跟蹤算法返回的box類/typedef struct cvbox2d（/cvpoint2d32fcenter; /* 盒子的中心*/cvsize2d32f size; /* 盒子的長和寬*/float angle; /*水平軸與染一個邊的夾角，川弧度表示*/cvbox2d;cvconnectedcomp trackcomp;/連接部件/typedef struct cvconnectedcomp/double area; /* 選通域的 ifti積/float value; z*分割域的灰度湘放值*/c

11、vrect rect; /* 分割域的 roi */ cvconnectedcomp;int hdims = 32;/劃分直方圖bins的個數(shù)，越多越精確float hranges一arr = 0,180）;/像素值的范凼float* hranges = hranges_arr;/川于初始化cvhistogram類int vmin = 10, vmax = 256, smin = 30;/用于設(shè)置滑動條int cvmeanshift(const void *imgprob,cvrect windowln, cvtermcriteria criteria, cvconnectedcomp* co

12、mp) / 'i:現(xiàn) meanshift 算法 icvmomcnts moments;/cvmomcnts川來計算矩形的重心，肉積等形狀特征int i=0，eps;cvmat stub, *mat=(cvmat*)imgprob;cvmat curwin;cvrect cur_rect=windowln;/當(dāng)前組形框cv_funcname("cvmeanshift"); if(comp)/初始化跟蹤姐形comp->rect=windowln;moments.m00=moments.m01 =moments.mlo =0; /將階矩和階矩背_beg1n_;cv_

13、call(mat=cvgetmat(mat,&stub);if( cv_mat_cn( mat->typc )> 1 )/通道數(shù)選擇 fli 錯icv_error( cv_badnuinchannels，cvunsupportedhormat);)if( windowln.height <= 0 | windowln.width <= 0)/點選的窗 口無效fcvjerror( cv一stsbadarg，minput window has non-positive sizes)；1if( windowln.x < 0 | windowln.x + wind

14、owln.width > mat->cols |windowln.y < 0 | windowln.y + windowln.height > mat-rovs )cvjerror( cvstsbadarg，minitial window is not inside the image roim);cv_call( criteria = cvchecktermcriteria( criteria，1.，100 );/選代的標(biāo)準(zhǔn)，精度=1.0,選代次數(shù)eps = cvround( criteria.epsilon * criteria.epsilon );/精度 eps=

15、lfor( i = 0; i < criteria.max一iter; i+ )int dx，dy，nx，ny: double inv_m00;/選取搜索區(qū)域，對該矩形區(qū)域計箅它的，1階矩cv_call( cvgctsubrcct( mat，&cur_win, currect);cvcall( cvmonicnts( &cui一win，&momcnts );/* calculating center of mass */if( fabs(moments.moo) < dblepsilon)break;)/搜索岡域的質(zhì)雖inooinv_m00 = mornen

16、ts.inv_sqrt_moo*moments.inv_sqrt_nioo;/搜索區(qū)域的水平重心偏移dxdx = cvround( moments.mlo * invmoo windowln.width*0.5 );/搜索區(qū)域的乖貞重心偏移dydy = cvround( moments.mol * invmoo - windowln.height*0.5 ); /搜索區(qū)域的重心坐標(biāo)(nx，ny) nx = cur_rect.x + dx; ny = currect.y + dy;/跟蹤b標(biāo)處于圖像邊緣吋進(jìn)行一些對應(yīng)的處現(xiàn)if( nx < 0 )nx = 0;)else if( nx +

17、currect.widthmat->cols )nx = mat-cols - cur_rect.width;if( ny < 0 )ny = 0;else if( ny + currect.heightmat->rows ) ny = mat-rows - cur_rect.height;dx = nx - cur ject.x;dy = ny - cui一rect.y;cur_rect.x = nx;cur一rect.y = ny;/* check for coverage centers mass & window */ /精度達(dá)到耍求吋就可以退出循環(huán)if( d

18、x*dx + dy*dy < eps )(break;)1end ;if(comp)comp->rect=cur_rect;comp-area=(float)moments.moo;/國像面識return i;) void on_mouse( int event，int x，int y，int flags，void* param )/鼠標(biāo)調(diào)函數(shù)，該蚋數(shù)用鼠標(biāo)進(jìn)行跟蹤0標(biāo)的選擇iif( !image) return;if( image->origin)y = image->height - y;/如澩閣像原點嘩標(biāo)在左下，則將其改為左上if( selectobject)/s

19、clcct_objcct為，表示在川鼠標(biāo)進(jìn)行s標(biāo)選擇/此吋對矩形類selection用當(dāng)前的鼠標(biāo)位置進(jìn)行沒置 (selections = min(x,origin.x); selection.y = min(y,origin.y);selection.width = selection.x + cv_iabs(x - origin.x); selection.height = selection.y + cviabs(y - origin.y);selections = max( selections, 0 );selection.y = max( selection.y, 0 );selec

20、tion.width = min( selection.width, imagc->width );selection.height = min( selection.height, image->height);selection.width -= selection.x;selection.height -= selection.y;switch( event)1case cv_event_lbuttondown:/鼠標(biāo)按_卜'，開始點擊選擇跟蹤物體origin = cvpoint(x,y); selection = cvrect(x，y，0,0); selectobj

21、ect = 1; break;case cv_event_lbuttonup:/鼠標(biāo)松開，充成選擇跟蹤物體select_object = 0;if( selection.width > 0 && selection.height > 0) /如果選抒物體打效，則打開跟蹤功能 trackobject = -1;break;)cvscalar hsv2rgb( float hue )/川于將hue fi轉(zhuǎn)換成rgbsiint rgb3，p，sector;static const int sector_data3=(0,2,1), 1,2,0j 1,0,2, 2,0，d，

22、(2,1,0, 0,1,2); hue *= 0.033333333333333333333333333333333f; sector = cvfloor(hue);p 二 cvround(255*(huc - sector); p a= sector & 1 ? 255 : 0;rgbsector_data| sector) 0| = 255; rgbsector一 datasector 1 = 0; rgbsector一 datasector2 = p;return cvscalar(rgb2, rgbl, rgb0，0);)int main( int arge，char* arg

23、v )icvcapture* capture = 0;if( arge = 1 | (arge = 2 && strlen(argvl) = i && isdigit(argv i ()/打開攝像頭capture = cvcapturefromcam( arge = 2 ? argvl0 - 0 ： 0 );else if( argc = 2 )/打開avicapture = cvcapturcfroniavi( argvl);if( !capture )/打開視頻流失敗(fprintf(stderr/could not initialize capturing

24、”an”); return -1;printf( nhot keys: nn”tesc - quit the programnh”tc - stop the trackingnhntb - switch to/from backprojection viewnn"th show/hide object histogramnh”to initialize tracking, select the object with m()usen”)；/打印程序功能列表cvnamedwindow( histogram"，1 );/用于兄示直方圖cvnamedwindow( "m

25、eanshiftdemo"，1 );/用于姑示視頻cvsetmousecallback( ,meanshiftdemom, onmouse, 0 );/設(shè)置鼠標(biāo)m調(diào)函數(shù)cvcreatetrackbar( vmin”，"meanshiftdemo' &vmin，256,0); cvcreatetrackbar( nvmax”，"meanshiftdemo"，&vmax, 256,(); cvcrcatctrackbar( smin"，',mcanshiftdcmo, &smin，256, 0 );/設(shè)置滑動

26、條lor(;)/進(jìn)入視頻幀處理主循環(huán)1ipllmage* frame = 0; int i, bin一w，c;frame = cvqueryframe( capture );/選取一中貞聞像if( ! frame)break;if( !image)/image為，表明剛斤始還未對image揀作過，先述立一a緩沖區(qū)image = cvcreateimage( cvgetsize(frame)，8, 3 );image->origin = frame->origin;hsv 二 cvcrcatcimagc( cvgetsize(frame)，8, 3 );hue = cvcrcatci

27、magc( cvgctsizc(framcx 8, 1 );mask = cvcreateimage( cvgetsize(frame)，8, 1 );/分配掩膜閣像空間backproject = cvcreateimage( cvgetsize(frame), 8, 1 );/分配反向投影圖空間，大小一樣，華通道hist = cvcrcatchist( 1, &hdims, cv_hist_array, &hrangcs, 1 );/分配直方圖空間histimg = cvcreateimage( cvsize(320,200), 8, 3 );/分配用于直方圖顯示的空叫cvz

28、ero( histimg);/背背景為黑色)cvcopy( frame，image，0 );cvcvtcolor( image，hsv，cv一bgr2hsv );/把閣像從rgb表色系轉(zhuǎn)為hsv表色系if( track一object)/track_object非零，衣示省盂要跟蹤的物體int vmin 二 vmin，vmax = vmax;cvinranges( hsv, cvscalar(o，smin，min(一vmin，vmax)，0)，cvscalar(180,256，max(vmin，vmax)，o)，mask);/制作掩膜板，只處理像素值為h: *180, s： smin256，v:

29、 vminvmax之間的部分 cvsplit( hsv, hue，0,0,0);/分離h分量if( trackobject < 0 )/如果盂要跟蹤的物體還沒yf進(jìn)行屬性提収，則進(jìn)行選収框類的閿像屬性提収1float max_val = o.f; cvsetimageroi( hue，selection );/設(shè)置原選擇框為roi cvsetimageroi( mask，selection );/設(shè)置掩膠板選抒框為roi cvcalchist( &hue，hist，0, mask );/得到選擇框內(nèi)且滿足掩膜板內(nèi)的直;/閣cvgetminmaxhistvalue( hist，0,

30、 &max_val，0, 0 );cvconvertscale( hist-bins，hist-bins，max_val ? 255. / max_val : ().，0 );/對直方閣的數(shù)値轉(zhuǎn)為255 cvresetimageroi( hue);/去除roicvrcsctimagcroi( mask );/去除roitrack_window = selection; trackobject = 1;/w. lrack_object為，衣明屈性提収記成 cvzero( histimg); binw = histimg->width / hdims; for( i = 0; i &

31、lt; hdims; i+ )/岡直方閣到閣像空叫(int val = cvround( cvgetreal 1 d(hist->bins,i)*histimg->height/255 );cvscalar color = hsv2rgb(i*l 8o.f/hdinis); cvrectangle( histimg，cvpoint(i*binv，histimg->height)，cvpoint(i+1 )*bin_w,histimg->height - val), color, -i, 8, 0 );cvcalcbackproject( &hue，backpro

32、ject，hist);/計算hue的反向投影圖cvand( backproject, mask, backproject，()；/得到掩膜iaj的反向投影/cvcamshift( backproject，tracks window,/cvtermcriteria( cv一termcriteps | cvtermcritjter，10, 1 )，/&track_comp, &track_box);cvmeanshift( backproject，track_window,cvtcrmcritcria( cv_termcrit_eps | cv_termcrit_iter, 10,

33、 1 )，&track一comp );/使用meanshift 法對backproject屮的內(nèi)容進(jìn)彳y搜索，返回跟辟結(jié)災(zāi)track_window = trackcomp.rect;/將到跟蹤結(jié)果的矩形框if( backproject一mode )cvcvtcolor( backproject, image, cv一gray2bgr );if( image->origin)track_box.angle = -track_box.angle;/cvellipsebox( image, trackbox，cvrgb(255,0,0)，3, cvaa，0 );/岡出跟蹤結(jié)澩的位置cvrectangle(image，cv