【導(dǎo)讀】南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文）。計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院。論文題目基于模板匹配的目標(biāo)跟蹤技術(shù)研究與實(shí)現(xiàn)。指導(dǎo)教師職稱(chēng)講師。專(zhuān)業(yè)網(wǎng)絡(luò)工程班級(jí)

　　

【正文】 。采用 模板匹配來(lái)跟蹤目標(biāo)，就是 把 要跟蹤的目標(biāo) （模板 ）保存好，然后在每一幀來(lái)臨的時(shí)候，在整個(gè)圖像 （搜索 圖像）中尋找與這個(gè)目標(biāo)最相似的 位置， 其基本跟蹤過(guò)程如圖 所示 。 首先 ， 第一幀時(shí) 初始化要跟蹤的目標(biāo)，一 個(gè) 完整的跟蹤 系統(tǒng) 應(yīng)該采用自動(dòng)化的方法 進(jìn)行目標(biāo)的初始化，我們?cè)诖酥豢紤]跟蹤算法 ， 所以采用 手動(dòng)化 的方法進(jìn)行初始化，即第一幀時(shí)用戶(hù)手動(dòng)用鼠標(biāo)在圖像中框出 要 跟蹤的目標(biāo)。 第一幀中初始化模板目標(biāo)初始化在當(dāng)前幀中匹配模板目標(biāo)跟蹤目標(biāo)更新N = 1N = 2 , 3 , 4 , 5 , …用匹配到的信息更新目標(biāo)模板 ， 同時(shí)將它作為下一幀匹配要用的模板N = 2 , 3 , 4 , 5 , … 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 21 圖 模板 匹配目標(biāo)跟蹤基 本過(guò)程 其次， 對(duì)于后面的每幀圖像，首先采用模板匹配算法 找到 目標(biāo)在當(dāng)前幀的位置（ 搜索 圖像中 相似度 最大的位置） ， 然后利用匹配到的信息更新目標(biāo)模板 。進(jìn)行目標(biāo)模板更新的目的主要是考慮到目標(biāo) 所處 的環(huán)境的變化 （背景 變化，光照變化等）。 如果在 整個(gè)過(guò)程中目標(biāo)模板都 保持跟蹤 時(shí)很容易丟失。 用 8 位圖像 作 為例 子 ，模板 T 疊放在被搜索圖 I 向 上平移， 其中 T 為 m n 個(gè)像素 、 I 為 W H 個(gè)像素 。 模板 T 覆蓋 于 被搜索圖 I 的那塊區(qū)域叫 做 子圖 ,ijS 。 ,ij是 子圖 的 左上角在被搜索圖上的 所在的 坐標(biāo)。 那么 搜索范圍 就 是： 1 i W M? ? ? 1j H N?? 對(duì)比 模板和子圖的相似性 來(lái) 完成模板匹配。衡量 它們 的匹配程度 ,可 以使用 第三章我們介紹的幾種測(cè)量，也可以使用 下面 這種測(cè)度： ,11( i , ) S ( , ) ( , )MN ijmnD j m n T m n?????? 以上方法稱(chēng)為 SAD，是最簡(jiǎn)單快速的方法，但這種方法的 魯邦性 不好 ，為了 提高該算法在這個(gè)方面的性能 ， 也考慮到 實(shí)時(shí)性， 就有了 相關(guān)系數(shù)法 。 相關(guān)系數(shù) 作為 一種數(shù)學(xué)距離可以衡量?jī)蓚€(gè)向量 之間 的相似程度。 相關(guān)系數(shù) 源于余弦定理：c o s ( ) ( 2 2 2 ) / 2A a c b b c? ? ?.若 兩個(gè)向量 之間 的夾角為 0（對(duì)應(yīng) r 也就是相關(guān)系數(shù)為1）， 這就意味著 它們 是 完全相似 的 ， 若 夾角 是 90 度， 那么相關(guān)系數(shù) r 為 0，就意味著 它們完全不相似， 若 夾角 是 180 度 ,那么相關(guān)系數(shù)為 1，就意味著 它們完全相反。 將 余弦定理 用 向量的形式 表達(dá)即為 ： c o s ( ) , /( )A b c b c?? ? ? 即： 2 2 2 2 2 21 1 2 2 1 2 1 2c o s A = ( b + b + . . . . . . b ) / [ (b b . . . . b ) ( c c . . . c ) ]n n n nc c c s q r t ? ? ? ? ?（ ） 上式中 分子 是 兩向量的內(nèi)積，分母 是 兩向量的模相乘。 而 實(shí)際應(yīng)用中， 比較 常用的 是 去均值相關(guān)系數(shù) 法 ，在 余弦的向量表達(dá) 的基礎(chǔ)上在 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 22 分子分母 上 減去 了 各個(gè)向量的均值： 22( ) ( )( ) ( y )iiiix x y yrx x x???????? 其中 ,xy分別是 , , 1, 2, ,iix y i n? 的 均值 ， 即 11,iix x y yn m n m??????,mn分別 是模板的寬和高。 另一方面決定模板大小與否往往與經(jīng)驗(yàn)密切相關(guān)， 緊帖 著 目標(biāo)輪廓的模板 和 包含了 太多 的 背景的模板 所得到的效果往往不是很好 ，前者 是因?yàn)?模板 過(guò) 小，對(duì) 于 目標(biāo)的變化 會(huì) 太 過(guò)于 敏感， 從而 會(huì) 導(dǎo)致 很容易丟失目標(biāo)。后者 模板太大 ，目標(biāo)變化 已經(jīng)開(kāi)始發(fā)生變化了但是 算法卻 還 沒(méi)有 什么 反應(yīng)。 通常情況下， 目標(biāo)占模板比例 為 30%到 50%是最好的 。 評(píng)判算法的標(biāo)準(zhǔn) 為滿(mǎn)足實(shí)時(shí)模板匹配的需要，匹配方法的好壞需從以下的四個(gè)方面來(lái)進(jìn)行衡量：可靠性、穩(wěn)定性、匹配耗時(shí)和匹配精度。 （ 1） 可靠性是 指被搜索圖像的目標(biāo)區(qū)域被遮擋，或目標(biāo)出現(xiàn)部分缺失的情況下，算法能否找到所要尋找目標(biāo)的相應(yīng)能力。 （ 2） 穩(wěn)定性指的是噪聲、光照等外界環(huán)境的變化對(duì)檢測(cè)的結(jié)果的影響。 （ 3） 匹配精度是算法應(yīng)該要著重考慮到的一個(gè)方面。多數(shù)情況下，匹配精度比以上所提到的兩個(gè)方面在算法運(yùn)用時(shí)更受關(guān)注，例如在導(dǎo)彈定位中，假如最后的匹配誤差相對(duì)來(lái)說(shuō)較大，可能就會(huì)造成相當(dāng)嚴(yán)重的后果。很多的實(shí)際運(yùn)用中，在算法性能無(wú)法再有提升的時(shí)候，管理者們都是通過(guò)提升機(jī)器的硬件來(lái)提高匹配精度的。 （ 4） 最后是匹配耗時(shí)，也就是本文敘述的關(guān)鍵問(wèn)題所在。當(dāng)外界條件固定時(shí)，比較算法 實(shí)時(shí)性的優(yōu)劣。雖然隨著時(shí)代的進(jìn)步，計(jì)算機(jī)的性能和運(yùn)算速度都在不斷的提高，但是隨著使用的范圍越來(lái)越大，數(shù)據(jù)也就越來(lái)越多，也就越來(lái)越難得達(dá)到良好的實(shí)時(shí)性。很多時(shí)候還是需要通過(guò)對(duì)算法進(jìn)行優(yōu)化，從而提高實(shí)時(shí)性。例如，工廠(chǎng)的原件檢測(cè)時(shí)，原件用很快的速度在移動(dòng)，所以算法就必須以毫秒級(jí)速度完成原件檢測(cè)，這樣才能夠達(dá)到要求。 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 23 模板匹配跟蹤算法缺陷 當(dāng)識(shí)別的設(shè)計(jì)靜態(tài)的物體的時(shí)候模板匹配會(huì)具有比較高的匹配精度。匹配值是由相似度量函數(shù)直接決定的，所以相似度量函數(shù)也就直接決定最優(yōu)匹配的位置，進(jìn)而對(duì)跟蹤結(jié)果也有直接的影響。傳 統(tǒng)模板匹配算法主要運(yùn)用三種函數(shù)：相關(guān)匹配度量、平方差度量和相關(guān)系數(shù)度量。這三種相似度量函數(shù)中相關(guān)系數(shù)度量的匹配準(zhǔn)確度比較高，但是它的計(jì)算量大。而平方差度量的計(jì)算量相對(duì)來(lái)說(shuō)小，但是匹配的準(zhǔn)確度低了一些。三種度量方法具有的共同優(yōu)點(diǎn)是通用性強(qiáng)，是因?yàn)樗鼈兌贾焕媚０搴湍繕?biāo)圖像兩者的像素信息，但是這三種函數(shù)的運(yùn)用都未考慮目標(biāo)跟蹤的特點(diǎn)，因而在目標(biāo)跟蹤技術(shù)的應(yīng)用中，效果都不理想。 上面 的分析表面：采用相關(guān)系 數(shù) 來(lái)度量相似度進(jìn)行模板匹配的精度最高，但是它的計(jì)算量相對(duì)于其他兩種度量方法也相應(yīng)的更大 。 那么 我們 能不能 夠 采用相關(guān) 系數(shù)度量來(lái)保證匹配精度，但想方設(shè)法降低 它 的復(fù)雜度，從而在精度和復(fù)雜度之間達(dá)到一個(gè)折中呢？這個(gè) 是 我們 在 下一小節(jié)中將要闡述的，也是本文的一個(gè)重點(diǎn)之一。 圖 描述 目標(biāo)常用的兩種方式 圖 目標(biāo) 角度旋轉(zhuǎn)示例 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 24 另一方面 ，在目標(biāo)跟蹤算法中，我們一般用 矩形 或者橢圓來(lái)描述目標(biāo) ， 如圖 所示 。 并且 匹配的時(shí)候只是 對(duì)于 目標(biāo)位置進(jìn)行匹配，沒(méi)有考慮目標(biāo)的旋轉(zhuǎn)。也就是說(shuō) 當(dāng)目標(biāo)旋轉(zhuǎn)的時(shí)候，我們?nèi)匀皇褂镁匦慰?來(lái)描述目標(biāo)，這樣會(huì)帶來(lái)很大的誤差 ，甚至導(dǎo)致目標(biāo)跟蹤失敗。 這一點(diǎn) 我們不難從圖 得到 很好的解釋。 假設(shè) 圖中黃色的小方塊是待跟蹤的目標(biāo)初始 狀態(tài) ，我們 紅色 的小矩形 描述 它 。經(jīng)過(guò)若干幀 之后，黃色的目標(biāo)發(fā)生了一定程度的 旋轉(zhuǎn)， 如果此時(shí)我們?nèi)匀皇褂貌粠D(zhuǎn)角度的小矩形 去描述 它將會(huì)產(chǎn)生很多錯(cuò)誤的信息：一部分不見(jiàn)包含進(jìn)來(lái)了，同時(shí)一部分目標(biāo)信息 處于 小矩形框的外面了。 在這種 情況下匹配的時(shí)候?qū)a(chǎn)生很大的誤差，甚至有可能導(dǎo)致目標(biāo)跟蹤失敗。 本 小節(jié)我們主要針對(duì)上面提到的兩個(gè)缺陷進(jìn)行 改進(jìn) 。 算法加速 關(guān)于 提速我們從兩個(gè)方面進(jìn)行。 一方面我們 將一次匹配 的 過(guò)程改 成了 兩次匹配 。即 一次粗略匹配，一次精確匹配。 第一次 是 粗略匹配。取模板隔行隔列 的 數(shù)據(jù)， 也就是 1/4 模板數(shù)據(jù)， 然后 在被搜索 圖像 上 開(kāi)始 隔行隔列 的 匹配， 也就是 在原圖 1/4 的 范圍內(nèi) 進(jìn)行 匹配。由于數(shù)據(jù)量 的大幅 度 減少，匹配速度 就會(huì)得到 顯著提高。 于此 同時(shí) 也 需要設(shè)計(jì)合理的誤差閥值 0E 00 ( m 1 ) / 2 ( n 1 ) / 2Ee? ? ? ? ? 上 式中： 0e 是 各 個(gè) 點(diǎn)平 均最大誤差，一般 來(lái)說(shuō) 取 40~50 就可以了 ； ,mn是 模板的長(zhǎng)和 寬 。 第二次是精確匹配。在第一次誤差最小點(diǎn) min min( , )ij的鄰域內(nèi)，即在對(duì)角點(diǎn)為m in m in m in m in( 1 , 1 ) , ( 1 , 1 )i j i j? ? ? ?的矩形內(nèi)，進(jìn)行搜索匹配，得到最后結(jié)果。 另一 方面，我們從匹配時(shí)采用的相關(guān)系數(shù)計(jì)算公式入手。 如果我們 嚴(yán)格 按照 相關(guān) 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 25 系數(shù)公式來(lái)進(jìn)行匹配， 在一幀 600*800 的圖像中尋找一個(gè) 30*30 的目標(biāo)大概需要幾秒的時(shí)間，還遠(yuǎn)遠(yuǎn)達(dá)不到實(shí)時(shí)性的要求。為 了 加速，我們將相關(guān)系數(shù)公式 變形， 即 ? ? ? ?? ? ? ?222 2 2 22 2 2 22222( ) ( )( ) ( y )()( 2 ) ( 2 )()( 2 ) ( 2 )iiiii i i ii i i ii i i ii i i ii i i ii i i ix x y yrx x xx y x y x y x yx x x x y y y yx y x y x y x yx x x x y y y yn x y x yn x x n y y?????? ? ??? ? ? ?? ? ??? ? ? ??????????????? ? ?? ? ? ? 其中 ix? ， 2ix? 都是一個(gè)常數(shù)，不必每次都算。分母的右邊可以通過(guò)積分 直方圖來(lái)加速 。通過(guò)這些 方法，可以在一定程度上提高算法的執(zhí)行效率。 角度匹配 通過(guò)構(gòu)造由不同的旋轉(zhuǎn)角度的模板構(gòu)成一個(gè)集合，再將集合中的成員分別與目標(biāo)圖象進(jìn)行匹配，總有一種情況符合實(shí)時(shí)情況，從這些匹配數(shù)據(jù)中選擇匹配程度的最好位置作為匹配結(jié)果。然后找 出實(shí)時(shí)圖像和參考圖像之間的關(guān)系，也就是用平移大小和旋轉(zhuǎn)的角度表示。 11( , )xy 為原始坐標(biāo)， 22( , )xy 為旋轉(zhuǎn)之后的坐標(biāo)， 1m 和 2n 是原始模板的長(zhǎng)和寬，對(duì)應(yīng)的 2m 和 2n 則為旋轉(zhuǎn)之后的圖的長(zhǎng)和寬，參考圖旋轉(zhuǎn)后與原來(lái)的參考圖像的坐標(biāo)存在以下關(guān)系：（逆時(shí)針旋轉(zhuǎn)為例） （ 1）當(dāng) 0 90 , 90? ? ?? ? ? ? 111 2 21 2 2c o s sinc o s c o ssin c o sc o s sinxnynx x x yy y x y????????? ? ??????? ? ? ? ??? ? ? ? ?? （ 2）當(dāng) 90 180 , 180? ? ?? ? ? ? 南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院畢業(yè)設(shè)計(jì)（論文） 26 1111 2 21 2 2c o s c o sc o s sinc o s sinsin c o sxmy n mx x x yy y x y????????????? ? ??? ? ? ? ??? ? ? ? ?? （ 3）當(dāng) 180 270 , 270? ? ?? ? ? ? 1111 2 21 2 2sin c o ssin sinsin c o sc o s sinx m nynx x x yy y x y????????? ? ??????? ? ? ? ??? ? ? ? ?? （ 4）當(dāng) 270 360 , 360? ? ?? ? ? ? 111 2 21 2 2sin sinsin c o sc o s sinsin c o sxmymx x x yy y x y????????? ? ???? ? ??? ? ? ? ??? ? ? ? ?? 如果參考圖與實(shí)時(shí)圖之間只存在旋轉(zhuǎn)和平移，參考圖坐標(biāo)與實(shí)時(shí)圖坐標(biāo)就有如下的關(guān)系： c os si n si n c osst xydXXs dYY??? ? ? ? ???????? ? ? ? ????? ? ? ??? ??? ? ? ? 上式中β是旋轉(zhuǎn)角度， xd 和 yd 是橫向位移和縱向位移， s 則是縮放因子。 位置 角度匹配算法 對(duì)于 整個(gè)匹配 算法 ，我們分 三 步走： 第一步： 位置的 匹配： 首先在目標(biāo)上 位置 周?chē)捎?粗 略匹配得到目標(biāo) 的一個(gè) 初始位置 ；然后采用精確匹配得到目標(biāo)最終的 位