一種基于改進(jìn)FAST 角點(diǎn)檢測(cè)的LK 光流算法

朱代先，刁弘偉，劉樹林

（1.西安科技大學(xué) 通信與信息工程學(xué)院，陜西 西安 710054；2.西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054）

0 引 言

運(yùn)動(dòng)目標(biāo)檢測(cè)是目前機(jī)器視覺(jué)領(lǐng)域中的研究熱點(diǎn)，其廣泛應(yīng)用于航空航天、機(jī)器人自主避障、人臉識(shí)別等領(lǐng)域。當(dāng)前，常見的動(dòng)態(tài)目標(biāo)檢測(cè)算法有三類：

1）背景差分法，即以攝像頭固定為前提，運(yùn)用目標(biāo)幀圖像與背景圖像的差值來(lái)判斷是否存在移動(dòng)目標(biāo)。該方法準(zhǔn)確度高、運(yùn)行速度快，但對(duì)于動(dòng)態(tài)背景的改變，缺少有效的背景更新方法，并且對(duì)光照變化或外部環(huán)境改變較為敏感。文獻(xiàn)[2]提出了基于背景差分法的多運(yùn)動(dòng)目標(biāo)檢測(cè)與分割的方法，雖然成功地將多個(gè)移動(dòng)目標(biāo)進(jìn)行了標(biāo)記與分割，但該算法實(shí)時(shí)性不高。

2）幀間差分法，即用連續(xù)的兩幀或者三幀圖像的像素差分值來(lái)計(jì)算圖像中的動(dòng)態(tài)區(qū)域。當(dāng)差分值的絕對(duì)值小于閾值，即表示沒(méi)有移動(dòng)；反之，則有運(yùn)動(dòng)，所以該方法閾值的選取非常重要。

3）光流法，通過(guò)計(jì)算圖像灰度值在時(shí)間上的改變和圖像里目標(biāo)結(jié)構(gòu)及其運(yùn)動(dòng)關(guān)系來(lái)檢測(cè)移動(dòng)目標(biāo)，該算法不需要提前知道場(chǎng)景的任何信息，從而避免了背景模型的更新以及幀間時(shí)間間隔的選取問(wèn)題。但其無(wú)法有效地解決物體移動(dòng)形成的背景遮擋和孔徑小等問(wèn)題。文獻(xiàn)[7]將稠密光流法應(yīng)用于運(yùn)動(dòng)目標(biāo)檢測(cè)，將光流信息轉(zhuǎn)化到HSV 空間，并利用Sobel 算子進(jìn)行邊緣檢測(cè)提高了檢測(cè)的效果，避免了“重影”“空洞”及“拖尾”問(wèn)題，具有優(yōu)秀的識(shí)別精確性和抗干擾能力。文獻(xiàn)[8]使用Sift角點(diǎn)融合Harris 角點(diǎn)檢測(cè)函數(shù)值篩選特征點(diǎn)，可成功減少局部鄰域中無(wú)效的約束點(diǎn)，同時(shí)提升基本約束方程解的魯棒性。

但這些算法運(yùn)行速度慢，實(shí)時(shí)性仍有待提高。針對(duì)傳統(tǒng)LK 光流法無(wú)法有效跟蹤快速移動(dòng)的目標(biāo)，跟蹤時(shí)存在特征點(diǎn)選取實(shí)時(shí)性和準(zhǔn)確性不足的問(wèn)題，本文提出一種結(jié)合改進(jìn)FAST 特征點(diǎn)檢測(cè)的LK 光流法。該算法結(jié)合了FAST 角點(diǎn)檢測(cè)，并改進(jìn)篩選特征點(diǎn)方案，可以更快速地獲取初始目標(biāo)特征點(diǎn)；然后對(duì)每一幀圖像進(jìn)行金字塔圖像分層；最終使用LK 光流法對(duì)其進(jìn)行跟蹤，從而能夠?qū)崿F(xiàn)快速且穩(wěn)定的運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤。

1 特征提取

1.1 FAST 角點(diǎn)檢測(cè)原理

FAST 是一種重要的角點(diǎn)檢測(cè)方法，常用于檢測(cè)局部灰度改變明顯的像素點(diǎn)。FAST 角點(diǎn)檢測(cè)的原理是：當(dāng)一個(gè)像素點(diǎn)與其鄰域中的像素點(diǎn)差別過(guò)大（太亮或太暗），即判定該點(diǎn)是一個(gè)角點(diǎn)。步驟如下：

1）從圖片里選取一個(gè)像素點(diǎn)，設(shè)的亮度值為I。

2）設(shè)定一個(gè)合適的閾值（例如，20%的I）。

3）以為圓心，半徑為3 像素作離散化圓，該圓的圓周上存在16 個(gè)像素點(diǎn)，如圖1 所示。

圖1 FAST 角點(diǎn)選取原理圖

4）如果該圓周上有個(gè)連續(xù)的像素點(diǎn)，其像素值都比I+大，或者都比I-小，那么判定像素點(diǎn)就是一個(gè)角點(diǎn)，如圖1 中的白色虛線所示。值可以設(shè)置為12 或9，實(shí)驗(yàn)表明設(shè)為9 計(jì)算效果更好。

1.2 改進(jìn)FAST 角點(diǎn)檢測(cè)

傳統(tǒng)FAST 角點(diǎn)檢測(cè)必須將圖像里所有的點(diǎn)都要遍歷它鄰域圓周上的16 個(gè)點(diǎn)的像素，計(jì)算速率過(guò)低。為了更進(jìn)一步提升角點(diǎn)檢測(cè)的速度，本文使用了更高效的檢測(cè)方法來(lái)快速排除大部分非特征點(diǎn)的像素。改進(jìn)后的方法只用計(jì)算點(diǎn)離散圓周上1，5，9 和13 四點(diǎn)方位的像素，首先計(jì)算方位1，9 的亮度值，當(dāng)其亮度值都比閾值亮或比閾值暗，再檢測(cè)方位5，13 的亮度值。如果以上4 個(gè)像素點(diǎn)里最少有3 個(gè)亮度都大于I+或者小于I-，那么判定點(diǎn)是一個(gè)候選角點(diǎn)。對(duì)所有像素點(diǎn)做上面這一部分的初步檢測(cè)后，再對(duì)所有候選的角點(diǎn)做完整的FAST 角點(diǎn)檢測(cè)，此時(shí)得到的角點(diǎn)即為所需要的目標(biāo)特征點(diǎn)。改進(jìn)的FAST 角點(diǎn)檢測(cè)算法流程圖如圖2 所示。

圖2 改進(jìn)的FAST 角點(diǎn)檢測(cè)算法流程圖

2 目標(biāo)跟蹤

2.1 LK 光流法基本原理

LK 光流法（Lucas-Kanada 稀疏光流法）是一種基于兩幀圖像差分的光流運(yùn)動(dòng)估計(jì)算法。一個(gè)圖像序列()可以用一個(gè)三維的列向量=(,,)表示，式中：和分別是方位和方位的空間分量；是時(shí)間分量。

假設(shè)獲取上一幀和下一幀圖像的時(shí)間分別為和+d，則根據(jù)灰度不變假設(shè)有：

式中：d和d表示像素在d時(shí)間內(nèi)沿，方向的位移增量。

根據(jù)小運(yùn)動(dòng)模型假設(shè)，將式（1）泰勒展開：

由灰度不變假設(shè)可得：

把圖像灰度對(duì)時(shí)間的改變量寫為I，寫成矩陣形式為：

式（4）有兩個(gè)未知數(shù)，根據(jù)空間的一致性假設(shè)，設(shè)某一區(qū)域中的像素具有統(tǒng)一的運(yùn)動(dòng)，區(qū)域大小為×，像素個(gè)數(shù)為，則：

可得：

式（6）為關(guān)于，的超定線性方程。

將式（7）使用最小二乘法求解可得光流的計(jì)算公式為：

2.2 金字塔LK 光流法

LK 光流法的第二條假設(shè)針對(duì)的是小位移運(yùn)動(dòng)，當(dāng)運(yùn)動(dòng)目標(biāo)速度過(guò)快時(shí)，該算法會(huì)出現(xiàn)不小的偏差，而使用金字塔圖像分層的LK 光流法可以有效解決該問(wèn)題。設(shè)有兩幀灰度圖像和，(,)和(,)分別為圖像和上(,)位置處的灰度值。設(shè)圖像的像素點(diǎn)= [u,u]匹配到圖像上的像素點(diǎn)=+=[u+d,u+d]，使(u,u)和(u+d,u+d)誤差最小。位移= [d,d]被稱為和光流。通常在以點(diǎn)為中心的圖像區(qū)域[2w+1,2w+1]內(nèi)，通過(guò)最小灰度匹配誤差的平方和來(lái)求解。此損失函數(shù)為：

對(duì)圖像進(jìn)行金字塔分層，原始圖像位于金字塔最底層，上一層圖像的長(zhǎng)和寬每次縮小為下層圖像的一半，最終分辨率最低的圖像位于金字塔的最頂層；然后從最頂層開始，向下遞歸求解直到原始圖像為止。

設(shè)第層的損失函數(shù)為：

重新定義：

對(duì)(+v,+v)進(jìn)行泰勒展開：

同時(shí)，令：

得：

得：

2.3 改進(jìn)的光流跟蹤算法

本文算法的核心部分主要由改進(jìn)的FAST 角點(diǎn)檢測(cè)、金字塔圖像分層、LK 光流法等部分組成。FAST 角點(diǎn)檢測(cè)是計(jì)算機(jī)視覺(jué)領(lǐng)域的一類經(jīng)典算法，相比其他角點(diǎn)檢測(cè)算法，F(xiàn)AST 在運(yùn)行效率和計(jì)算速度等方面都有一定的優(yōu)勢(shì)，因此在圖像處理問(wèn)題上得到了廣泛的應(yīng)用。算法的跟蹤過(guò)程分為兩部分：角點(diǎn)檢測(cè)和光流估計(jì)。對(duì)于角點(diǎn)檢測(cè)，改進(jìn)的FAST 用于快速提取第一幀中最強(qiáng)的灰度變化角點(diǎn)，通過(guò)設(shè)定閾值篩選目標(biāo)特征點(diǎn)。對(duì)于光流估計(jì)，根據(jù)首幀檢測(cè)到的特征點(diǎn)，通過(guò)LK金字塔估計(jì)第二幀與首幀的匹配點(diǎn)位置，然后將獲得的位置用作第三幀的初始預(yù)估位置。操作一直進(jìn)行到獲得最后一幀的匹配點(diǎn)位置為止。最終算法成功跟蹤運(yùn)動(dòng)目標(biāo)，改進(jìn)的跟蹤算法流程圖如圖3 所示。

圖3 改進(jìn)的跟蹤算法流程圖

改進(jìn)的FAST 角點(diǎn)檢測(cè)算法相比傳統(tǒng)FAST 方法擁有兩次特征點(diǎn)篩選。第一次篩選候選角點(diǎn)時(shí)能夠快速剔除圖像上非角點(diǎn)的像素點(diǎn)，極大提高了算法的運(yùn)行速度。第二次目標(biāo)特征點(diǎn)的提取在第一次篩選的候選角點(diǎn)基礎(chǔ)上進(jìn)行小閾值篩選，減少了特征點(diǎn)的數(shù)量并且提高了特征點(diǎn)提取的準(zhǔn)確性。傳統(tǒng)光流法跟蹤運(yùn)動(dòng)速度過(guò)快的目標(biāo)時(shí)會(huì)導(dǎo)致跟蹤失敗，因此引入圖像分層模塊。金字塔圖像分層主要解決了運(yùn)動(dòng)目標(biāo)幀間變化較大的問(wèn)題，將原本較大位移運(yùn)動(dòng)通過(guò)降低圖像像素變成小位移運(yùn)動(dòng)，使泰勒展開式仍能夠進(jìn)行計(jì)算，從而提升光流算法的有效性。

3 實(shí) 驗(yàn)

3.1 實(shí)施方案

為了充分說(shuō)明改進(jìn)方法的有效性和優(yōu)越性，設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)方案，具體方法如下：

1）對(duì)運(yùn)動(dòng)目標(biāo)分別提取Sift 特征點(diǎn)、Harris 特征點(diǎn)、FAST 角點(diǎn)和改進(jìn)后的FAST 特征點(diǎn)，然后分別使用金字塔LK 光流法對(duì)其運(yùn)動(dòng)目標(biāo)進(jìn)行跟蹤，驗(yàn)證不同特征點(diǎn)對(duì)算法的影響。

2）考慮到FAST 特征點(diǎn)本身具有的優(yōu)點(diǎn)，為驗(yàn)證改進(jìn)后的FAST 特征點(diǎn)作為L(zhǎng)K 光流法跟蹤時(shí)的目標(biāo)特征點(diǎn)能否繼續(xù)保留FAST 角點(diǎn)原本的性能。通過(guò)一段小球鉛擺運(yùn)動(dòng)的實(shí)時(shí)視頻，來(lái)對(duì)比驗(yàn)證FAST 光流算法與改進(jìn)后的FAST 光流算法跟蹤運(yùn)動(dòng)目標(biāo)的實(shí)時(shí)性與準(zhǔn)確性。

3.2 算法跟蹤性能的分析

為了體現(xiàn)算法的有效性，實(shí)驗(yàn)采取以下數(shù)據(jù)衡量算法性能：實(shí)驗(yàn)1 中使用初始動(dòng)態(tài)目標(biāo)檢測(cè)耗時(shí)、初始時(shí)識(shí)別的特征點(diǎn)個(gè)數(shù)NUM、每秒處理的圖像幀數(shù)FPS（反映算法的實(shí)時(shí)性）等指標(biāo)；實(shí)驗(yàn)2 中使用跟蹤路線和實(shí)際路線在軸方向上的誤差、跟蹤路線和實(shí)際路線在軸方向上的誤差（反映算法的準(zhǔn)確性）作為指標(biāo)。若改進(jìn)FAST 光流算法相比未改進(jìn)的FAST 光流算法在運(yùn)行速度上有一定程度的提高，并且能夠使跟蹤誤差基本保持不變，則說(shuō)明改進(jìn)后的算法擁有更好的性能。

3.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)硬件平臺(tái)為個(gè)人PC，具體參數(shù)如下：

處理器：AMD Ryzen 5 3550H with Radeon Vega Moblie Gfx 2.10 GHz ，RAM 16.0 GB，Windows 10，Visual Studio 2017，Matlab 2018。

實(shí)驗(yàn)1 依次使用Sift 特征點(diǎn)、Harris 特征點(diǎn)、FAST 角點(diǎn)和改進(jìn)FAST 特征點(diǎn)融合LK 光流法對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行跟蹤，類比數(shù)據(jù)指標(biāo)分析算法的性能，具體指標(biāo)統(tǒng)計(jì)見表1。其中，為初始運(yùn)動(dòng)目標(biāo)檢測(cè)耗時(shí)；NUM 為初始識(shí)別的特征點(diǎn)個(gè)數(shù)；FPS 為每秒處理的圖像幀數(shù)。

表1 四種跟蹤效果的指標(biāo)統(tǒng)計(jì)

從表1 可以看出，運(yùn)動(dòng)目標(biāo)跟蹤算法運(yùn)行速度分別是改進(jìn)FAST 光流法＞FAST 光 流法＞Harris 光 流法＞Sift光流法。改進(jìn)FAST 特征點(diǎn)結(jié)合LK 光流法相比未改進(jìn)FAST 特征點(diǎn)結(jié)合LK 光流法初始運(yùn)動(dòng)目標(biāo)檢測(cè)耗時(shí)降低了8 ms，且特征點(diǎn)數(shù)量基本保持不變，但每秒處理的圖像幀數(shù)提高了22.4%。可以得到結(jié)論：采用改進(jìn)后的FAST 角點(diǎn)檢測(cè)作為L(zhǎng)K 光流法的目標(biāo)特征點(diǎn)，可以使跟蹤算法的運(yùn)行速率得到更進(jìn)一步的提升。

四種特征點(diǎn)檢測(cè)效果如圖4 所示。

圖4 四種特征點(diǎn)檢測(cè)效果

實(shí)驗(yàn)2 因?yàn)镕AST 特征點(diǎn)自身?yè)碛锌焖贆z測(cè)的特點(diǎn)，為判斷改進(jìn)后的FAST 光流算法能否繼續(xù)保持良好的穩(wěn)定性，設(shè)計(jì)追蹤小球鉛擺運(yùn)動(dòng)的實(shí)驗(yàn)，判斷小球?qū)嶋H運(yùn)動(dòng)軌跡與算法跟蹤軌跡在軸方向和軸方向的偏差是否滿足精度要求。

圖5 分別展示了改進(jìn)算法在跟蹤移動(dòng)小球的第5，25，50，75 幀時(shí)的跟蹤情況。圖6、圖7 顯示了傳統(tǒng)FAST角點(diǎn)結(jié)合LK 光流法與改進(jìn)FAST 角點(diǎn)結(jié)合LK 光流法分別跟蹤動(dòng)態(tài)目標(biāo)的軌跡與動(dòng)態(tài)目標(biāo)實(shí)際移動(dòng)軌跡的方位與方位的跟蹤誤差。傳統(tǒng)算法軸方向與軸方向的平均跟蹤誤差為0.778 8 像素和0.705 0 像素，改進(jìn)后的算法軸方位與軸方位的平均跟蹤誤差為0.741 3 像素和0.720 4 像素，可以看出算法改進(jìn)后的跟蹤誤差略有減小。將改進(jìn)后的算法取75 幀作為測(cè)試樣本，原始圖像的分辨率為720×480 像素，金字塔的數(shù)量層為4 層，迭代閾值為0.5 像素，即迭代次數(shù)為20 次。改進(jìn)跟蹤算法平均4 次迭代就可以滿足收斂，而未改進(jìn)的方法平均需要5 次迭代才能滿足收斂。綜合而言，可以證明改進(jìn)后的FAST 角點(diǎn)檢測(cè)結(jié)合光流法相比傳統(tǒng)算法在精度變化不大的情況下運(yùn)行速度得到了明顯提高，能夠準(zhǔn)確而實(shí)時(shí)地跟蹤移動(dòng)目標(biāo)。

圖5 改進(jìn)后的跟蹤算法不同時(shí)間的跟蹤結(jié)果

圖6 x 軸方向的跟蹤誤差

圖7 y 軸方向的跟蹤誤差

4 結(jié) 論

針對(duì)傳統(tǒng)LK 光流法無(wú)法跟蹤快速移動(dòng)的物體，跟蹤過(guò)程中存在特征點(diǎn)選取實(shí)時(shí)性和準(zhǔn)確性不足的問(wèn)題，本文提出了結(jié)合改進(jìn)FAST 算法進(jìn)行特征選取和融合金字塔LK 光流法進(jìn)行特征追蹤的綜合算法。實(shí)驗(yàn)證明改進(jìn)后的算法可以更快速地提取較優(yōu)的特征點(diǎn)，使算法運(yùn)行速度提高的同時(shí)也能保持較低的跟蹤誤差，能夠滿足實(shí)時(shí)且穩(wěn)定的跟蹤效果。如今計(jì)算機(jī)視覺(jué)有良好的發(fā)展前景，該算法還有進(jìn)一步發(fā)展的空間，怎樣突破光流法灰度不變假設(shè)的局限；當(dāng)環(huán)境整體明暗改變時(shí)如何避免可能會(huì)出現(xiàn)光流法跟蹤失效的情況，這些都是今后研究的重點(diǎn)方向。