魯春，楊會成，楊文斌，朱文博

(安徽工程大學(xué)電氣工程學(xué)院, 安徽蕪湖241000)

結(jié)合光流法與最近鄰算法的運動目標檢測

魯春，楊會成，楊文斌，朱文博

(安徽工程大學(xué)電氣工程學(xué)院, 安徽蕪湖241000)

運動目標檢測具有廣泛的理論和現(xiàn)實意義，光流法是檢測運動目標的重要方法之一。但是用于運動目標檢測的光流算法卻有著計算量大、處理復(fù)雜的問題。一種聚類分析算法和改進的LK光流法相結(jié)合檢測方案可以很好地解決此類問題。對基于改進的LK光流法的運動目標檢測算法進行了分析和仿真，再加以聚類分析使得檢測出的運動目標更加準確。首先對圖像序列進行采樣與預(yù)處理，并利用LK光流法計算得出相鄰幀圖像的光流場，然后再利用最近鄰聚類算法對得到的光流場進行處理，進而檢測出圖像中的運動目標，最后使用Matlab軟件進行算法程序驗證。通過實驗可知，基于金字塔LK光流法與最近鄰算法的運動目標檢測方案可以更加有效地檢測出運動物體。

運動目標檢測；LK光流法；金字塔；最近鄰聚類算法

引言

計算機視覺的最終目的就是使用計算機等智能設(shè)備來代替人去對周圍環(huán)境進行感知、解釋及應(yīng)答。近年來，對動態(tài)目標進行識別與跟蹤是圖像處理與計算機視覺領(lǐng)域中一個不可或缺的分支，對這方面的研究引起許多國內(nèi)外學(xué)者的重視，并且已經(jīng)有許多研究所開始了有關(guān)的基礎(chǔ)與開發(fā)研究。

運動目標檢測就是在找尋運動的區(qū)域，目的就是把靜止的像素點跟運動的像素點分開。一般地，視頻圖像會被分為兩類：一類如監(jiān)控視頻般，背景靜止；一類如車載視頻般，背景不靜止。其實，在現(xiàn)實生活中不會存在完全靜止的背景，天氣、光照等環(huán)境的變化都可能使得背景變化。主要的檢測算法有光流法、幀間差分法和背景差分法三種[1]。背景差分法，就是固定攝像頭，利用背景與運動目標之間的差別來檢測運動目標。這種方法有著精準、速度快的優(yōu)勢，但是易受外部環(huán)境變化的影響。結(jié)合幀間差分法可以有效地克服局部運動以及噪聲等外部環(huán)境的影響[2-3]。幀間差分法，就是取相鄰兩幀或者三幀圖像之間的像素差來提取運動目標。光流法[4-5]就是將幀圖像中灰度的變化與二維速度場聯(lián)系起來，用光流場反映像素點運動的方向和速度，并根據(jù)光流場的分布特征來提取運動目標。用光流法結(jié)合幀間差分法[6]、光流的改進算法等算法間的相互結(jié)合[7-10]，有效地解決了光流法計算量大，處理復(fù)雜的問題。

聚類算法作為數(shù)據(jù)分析中廣泛使用的主要方法之一，已經(jīng)廣泛應(yīng)用于模式識別、機器學(xué)習(xí)、圖像處理和數(shù)據(jù)挖掘等方面[11-14]。簡單來說，聚類分析就是根據(jù)數(shù)據(jù)的特征將數(shù)據(jù)進行分類，使得屬于同一類別的數(shù)據(jù)間有盡可能多的相同特征，而屬于不同類別數(shù)據(jù)間的特征則盡可能不同。目前，常用聚類分析算法可以分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法[15]。

本文提出了基于金字塔(Lucas-Kanade，LK)光流法和聚類分析算法相結(jié)合的運動目標檢測方案，并以前方行駛車輛作為檢測的運動目標[16-17]，使用金字塔LK光流算法，克服了傳統(tǒng)光流法計算量大，處理復(fù)雜等問題。結(jié)合最近鄰聚類分析算法，大大提高了運動目標檢測的準確性。

1 運動目標檢測流程

在運動目標檢測過程中，第一步是對攝像機采集到的圖像序列進行重采樣和預(yù)處理；第二步是利用金字塔改進光流法計算出各點的光流值，得出各點的光流場；第三步是利用最近鄰規(guī)則聚類算法對光流場進行分割，得到運動目標區(qū)域。

1.1光流場算法

光流法的前提假設(shè)：

(1) 假設(shè)相鄰視頻幀之間的亮度恒定。

(2) 假設(shè)相鄰視頻幀之間的取幀時間連續(xù)，或者相鄰視頻幀之間物體的運動變化量比較微小。

(3) 保持空間的一致性，即同一子圖像的像素點具有相同的運動。

光流場的目的是找到視頻幀圖像中每個像素點的速度向量[6-8]。設(shè)在t時刻像素點(x,y)處的灰度值為I(x,y,t)；在t+dt時刻，該像素點更新到位置(x+dx,y+dy)，灰度值為I(x+dx,y+dy,t+dt)。根據(jù)上面的光流法前提假設(shè)可知，在給定的鄰域內(nèi)的速度向量場的變化是緩慢的。

I(x,y,t)=I(x+dx,y+dy,t+dt)

(1)

用泰勒公式將上式展開：

I(x+dx,y+dy,t+dt)=

(2)

忽略無窮小項ε，

(3)

Ixu+Iyu+It=0

(4)

(5)

方程(4)～(5)為光流的約束方程，包含 、兩個未知變量，本文選擇用Lucas-Kanade光流法解決這個問題。

1.2 LK光流法

可以利用LK光流法算法對以上的問題進行求解。若該像素點與鄰域內(nèi)的點運動情況相似，為了求解該像素點的運動信息，則可利用以下條件求解光流，在該點鄰域空間內(nèi)建立約束方程，并聯(lián)立方程以求解光流矢量。

假設(shè)在(u,v)的一個小的局部鄰域內(nèi)亮度恒定，那么：

(6)

即：

(7)

其中：

經(jīng)計算可得：

(8)

(9)

由于LK光流法有一定的缺陷，需要在設(shè)置鄰域窗口后計算光流。窗口較大，光流量的計算更加魯棒；而窗口較小時，光流量的計算更準確。但由于運動的每個部分的圖像不一致，如果窗口開得太大，很容易違反第三個前提。如果窗口很小，則包含更少的像素，更精確些，但當(dāng)運動相對較為劇烈的時候，無法實現(xiàn)光流的基本假設(shè)。

1.3光流法的改進

對于LK光流法，速度小、亮度恒定、區(qū)域一致性強，對于這些假設(shè)都不容易滿足。例如，當(dāng)物體移動的速度變得更快時，則假設(shè)不滿足，隨后的假設(shè)將具有較大的偏差，這使得考慮車輛行駛速度較大時光學(xué)流量值會具有較大的誤差，這使得算法可能出現(xiàn)較大的誤差。于是寄希望降低圖像中物體的運動速度，就是縮小圖像的像素。假設(shè)，初始圖像的像素為400×400，物體的運動速度為[16，16]，將圖像的像素縮小至200×200，那么物體的運動速度將變?yōu)閇8，8]，將圖像的像素縮小至100×100，那么物體的運動速度將變?yōu)閇4，4]。所以對源圖像進行了大量的縮放后，原算法變得適用。所以光流可以由原始圖像生成的金字塔圖像[6-7]逐層求解，不斷精確地尋找。

首先，引入兩個光流量：剩余光流量和猜測光流量。對于第層光流，通過從層的精確光流量輸出的猜測光流量gL和在修整后基于該層獲得的剩余光流量dL獲得。獲得的L層的光流量：

kL=gL+dL

(10)

根據(jù)層的精確光流量，可得層的猜測光流量，兩者關(guān)系：

gL=2×kL-1=2×(gL-1+dL-1)

(11)

由于第層到第層為采樣一半，那么光流量相應(yīng)地也該減半，因此粗略估計不準確。為了精確地計算出第層的光流量，還需要使用基本流量方程去計算得出第層中剩余光流量。基本光流方程為：

(12)

其中，IL(x,y)為原圖，JL(x,y)為參考圖，(dx,dy)為在(ux,uy)處的光流向量，(wx,wy)為(ux,uy)的搜索半徑。

由于先前的光流層提供的先驗信息，允許光的流動跳出(wx,wy)的約束并進一步移動，從而解決了前文提到的有關(guān)窗口大小的問題。

1.4基于金字塔光流法光流場求解

光流法可以動態(tài)地分析圖像，檢測圖像中的運動物體。如果圖像中沒有運動物體，則在整個圖像區(qū)域中光流矢量的變化是連續(xù)的。當(dāng)圖像中存在運動物體時，目標與圖像背景之間存在相對運動，運動目標形成的速度矢量與鄰域背景速度矢量不同，以檢測運動目標及其位置。光流法檢測運動物體的問題主要是由于光流法運算量大、缺乏實時性和實用性。對于那些運動速度太快的對象，它們將違反路光流法假設(shè)(2)與假設(shè)(3)。本文提出了改進的金字塔光流算法[10]，首先對圖像進行預(yù)處理，然后進行金字塔光流運算。這樣不僅可以檢測出速度較快的運動目標，而且可以減少計算量，提高系統(tǒng)的實時性。

具體步驟如下：

(1) 視頻序列中圖像預(yù)處理、去噪。

(2) 取連續(xù)兩張圖像I、J，在點處的灰度值為和，并且已知圖像I中此點的速度為，圖像J中此點速度為。

(3) 將建立金字塔模型，。初始化金字塔光流估計值，層圖像上點的速度為。

(4) 初始化剩余光流量，并根據(jù)基本光流方程計算層的光流值。

(5) 計算層的光流，以此類推得到最后的光流值。圖像J中對應(yīng)點為。

1.5最近鄰聚類算法

聚類分析是根據(jù)收集的某些或某些因素將多個類別進行分組的過程。在這個過程中，集合中的每個組件都盡可能地具有相同的特征。對于其他組件，特性盡可能不同。最近鄰聚類算法是一種基本的聚類分析算法。在前車檢測中，同一物體在兩個連續(xù)的視頻幀流中具有連續(xù)的特點。連續(xù)性是最近鄰聚類算法的基礎(chǔ)。位于同一運動物體上的點必然是距離相對較近的點。如果在兩個相鄰的數(shù)據(jù)點發(fā)生了巨大的變化，那么這兩點可以認為是屬于兩個不同的對象。相反，如果兩個數(shù)據(jù)點之間的距離很小，那么這兩點可以認為是兩個數(shù)據(jù)點屬于同一個對象。

首先計算同一視頻幀中相連兩點的光流量差值，之后將計算得到與設(shè)定的閾值進行比較，若，則可以確定這兩點屬于同一類，反之則確定這兩點屬于不同的類。在整個算法中，聚類閾值的選取是非常關(guān)鍵的一步，對聚類結(jié)果有很大的影響。如果閾值選擇的過小，可能會將同一個目標分割成多個部分，同時對算法實時性也有影響。而閾值選擇過大，則會將兩個或多個目標混為一個目標，影響算法的準確性。

1.6結(jié)合LK光流法與最近鄰算法的檢測方法

相對于傳統(tǒng)光流法，本文提出一種結(jié)合改進LK光流法與最近鄰算法的檢測方法，該算法使用基于金字塔的LK 光流算法，將可能存在運動目標的區(qū)域提取出來，通過最近鄰算法在該區(qū)域內(nèi)外選取各自不同的閾值來進行提取目標，這樣便將閾值分割與區(qū)域分割結(jié)合起來，完成運動目標的檢測提取。具體步驟為：

(1) 計算同一視頻幀中相連兩點的光流量差值。

(2) 將計算得到與設(shè)定的閾值進行比較，若，則可以確定這兩點屬于同一類，反之則確定這兩點屬于不同的類。

通過上述流程，就可以確定出視頻幀中最可能存在運動目標的大致區(qū)域。

2 實驗結(jié)果與分析

本文選用一段視頻中的1260幀圖像作為實驗數(shù)據(jù)庫，將圖像中前方行駛車輛作為檢測目標對本文方案進行檢測，并進行傳統(tǒng)方法與結(jié)合聚類分析的檢測方案相比較。使用Matlab軟件對于金字塔LK光流法的汽車前方車輛檢測方法進行了分析和仿真，通過計算得出相鄰幀圖像的光流，然后用最近鄰聚類算法對圖像的光流進行檢測。

為了更好地檢測到運動目標，本文將在視頻序列中隨機選取相鄰兩幀圖像，圖像大小為175×120，如圖1所示的前兩張前車圖像，根據(jù)本文算法計算得出其光流場，并與相鄰兩幀圖像中的后者疊加，以判斷是否檢測出前方行駛車輛的大致位置。判定金字塔LK光流法是否可以確定視頻幀中移動目標的大致區(qū)域。

圖1 金字塔LK光流法

圖1運用金字塔LK光流算法對視頻中相鄰兩幀圖像進行初步的光流處理，并根據(jù)得出的光流差值圖大致判斷出前方是否有行駛車輛，給出了大致位置。由表1可知，改進的金字塔光流算法的運算速度可達到0.153秒/次，相比較于傳統(tǒng)的光流算法提高了0.564秒，大大地減小了運算量，達到減小運算時間的目的，提高了檢測效率。

表1 兩種算法的平均計算時間

本文通過實驗確定閾值。首先設(shè)定最近鄰聚類個數(shù)k, 初始化k=1開始，使用檢驗集估計分類的錯誤率。每次k增加1，當(dāng)產(chǎn)生最小錯誤率最小時，選擇其中最大光流差值設(shè)為閾值，本文的設(shè)定閾值mth=0.24。

圖2在金字塔LK光流算法的初步處理所得到的光流值的基礎(chǔ)上，根據(jù)最近鄰聚類算法并由實驗得出光流閾值。利用值對光流場進行分類處理，以更加具體的框出前方行駛車輛，并與傳統(tǒng)的運動物體檢測方法比較。

圖2 兩種方法的比較

相比較傳統(tǒng)方法與結(jié)合最近鄰聚類分析算法的運動目標檢測方法，后者可以更加具體、準確地檢測出前方行駛車輛。本文采用 CVPR 2013 Benchmark 提出的評價標準[18]，根據(jù)空間魯棒性對檢測的精確性進行評估，給出在中心位置誤差閾值為40個像素點時的結(jié)果，其評估結(jié)果如圖3所示。

圖3 SRE精確度圖

根據(jù)圖3可知，本文方案的精確度可達到0.8409。與傳統(tǒng)方案的精確度相比較提升了0.0454。在對前方車輛檢測與跟蹤中，使用此方法檢測出前方行駛車輛，對其進行訓(xùn)練生成檢測器，進而可以更加有效地進行檢測與跟蹤。

3 結(jié)束語

本文提出了基于金字塔LK光流法檢測前方行駛車輛，結(jié)合最近鄰聚類算法，可以更加有效地檢測出前方行駛車輛。本文使用Matlab軟件對提出的組合算法進行了分析和仿真。通過實驗，組合金字塔LK光流法與最近鄰聚類算法可以更準確地檢測前車。

[1] 程愛靈,黃昶,李小雨.運動目標檢測算法研究綜述[J].信息通信,2017(1):12-14.

[2] 劉仲民,何勝皎,胡文瑾,等.基于背景減除法的視頻序列運動目標檢測[J].計算機應(yīng)用,2017,37(6):1777-1781.

[3] 孫挺,齊迎春,耿國華.基于幀間差分和背景差分的運動目標檢測算法[J].吉林大學(xué)學(xué)報:工學(xué)版,2016,46(4):1325-1329.

[4] 關(guān)興來,謝曉竹.基于光流的運動目標檢測跟蹤快速算法[J].微計算機信息,2012,28(10):421-423.

[5] 張利平,趙俊梅.基于光流的運動車輛檢測和跟蹤技術(shù)的研究[J].車輛與動力技術(shù),2014(2):61-64.

[6] 袁國武,陳志強,龔健,等.一種結(jié)合光流法與三幀差分法的運動目標檢測算法[J].小型微型計算機系統(tǒng),2013,34(3):668-671.

[7] 張忠義.基于改進LK光流的目標跟蹤算法研究[J].信息技術(shù),2015(10):127-130.

[8] 朱俊杰,李勝,侯保林,等.基于金字塔LK算法的運動目標的檢測[J].工業(yè)控制計算機,2015,28(9):13-15.

[9] 郝慧琴,王耀力.基于幀間差分和金字塔光流法的運動目標檢測[J].電視技術(shù),2016,40(7):134-138.

[10] 陳添丁,胡鑒,吳滌,等.稀疏光流快速計算的動態(tài)目標檢測與跟蹤[J].中國圖象圖形學(xué)報,2013,18(12):1593-1600.

[11] 馮柳偉,常冬霞,鄧勇,等.最近最遠得分的聚類性能評價指標[J].智能系統(tǒng)學(xué)報,2017,12(1):67-74.

[12] 秦亞輝,何利力.基于分塊后重疊K-means聚類的KNN分類算法[J].工業(yè)控制計算機,2017,30(2):103-104.

[13] 孫水輝.聚類分析在學(xué)生成績分析中的應(yīng)用[J].中國管理信息化,2016(6): 229-230.

[14] 許進文.數(shù)據(jù)挖掘中聚類分析算法及應(yīng)用研究[J].計算機光盤軟件與應(yīng)用,2013(6):176-177.

[15] 張靜.數(shù)據(jù)挖掘中聚類分析綜述[J].價值工程,2014,33(15):226-227.

[16] SHUKLA D,PATEL E.Speed determination of moving vehicles using Lucas-Kanade algorithm[J].International Journal of Computer Applications Technology & Research,2013,2(1):32-36.

[17] INDU S,GUPTA M,BHATTACHARYYA A.Vehicle tracking and speed estimation using optical flow method[J].International Journal of Engineering Science and Technology,2011,3(1):429-434.

[18] WU Y,LIM J,YANG M H.Online object tracking:a benchmark[C]//Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition,Portland,OR,USA,June 23-28,2013:2411-2418.

MovingObjectDetectionMethodCombinedOpticalFlowandK-NearestNeighborAlgorithm

LUChun,YANGHuicheng,YANGWenbin,ZHUWenbo

(College of Electrical Engineering, Anhui Polytechnic University, Wuhu 241000,China)

Moving object detection has great significance in theory and practice, and optical flow is one of the important moving object detection methods. A method to detect moving objects combined K-Nearest neighbor algorithm and pyramid LK optical flow is proposed to solve such problems，as the optical flow algorithm for moving target detection has a large computational complexity and a complex problem. Analysis and simulation of moving target detection based on the improved Lucas-Kanade optical flow algorithm are given, and then the clustering analysis is made to make the moving object more accurate．Firstly, the image sequences of moving target are sampled and processed. Then Lucas-Kanade optical flow method is used to calculated the adjacent frames of light flow to get the optical flow field. Lastly, the K-Nearest neighbor algorithm is used to detect the moving object. The experiments prove that the object detection algorithm combined Lucas-Kanade algorithm and K-Nearest neighbor algorithm is an efficient moving target detection method.

moving object detection; Lucas-Kanade optical flow; pyramid; K-Nearest neighbor algorithm

TP391

A

2017-08-20

安徽省高校自然科學(xué)研究重大項目(KJ2014ZD04)

魯 春(1993-),女,安徽滁州人,碩士生,主要從事圖像處理方面的研究,(E-mail)1114510762@qq.com

1673-1549(2017)05-0063-06

10.11863/j.suse.2017.05.11