改進(jìn)的Otsu算法及在運(yùn)動目標(biāo)檢測中的應(yīng)用研究

楊勝輝，李太君，肖 沙，周浩理，徐寧敏

(1. 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228；2. 海南省公安廳，海南 ?？?570311 )

改進(jìn)的Otsu算法及在運(yùn)動目標(biāo)檢測中的應(yīng)用研究

楊勝輝1，李太君1，肖 沙1，周浩理1，徐寧敏2

(1. 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228；2. 海南省公安廳，海南 ?？?570311 )

針對Otsu自適應(yīng)閾值分割算法中閾值搜索精準(zhǔn)度較低、效率不高的問題，結(jié)合視頻圖像序列的幀間相關(guān)性，利用遺傳算法的全局尋優(yōu)優(yōu)勢，及模擬退火算法較好的爬山性能，提出一種改進(jìn)的Otsu算法，并與三幀差分法相結(jié)合應(yīng)用于視頻運(yùn)動目標(biāo)檢測。實(shí)驗(yàn)證明，該算法相對Otsu算法和對比算法減少閾值分割中的尋優(yōu)嘗試次數(shù)，使最優(yōu)閾值的選取更精確，并提高了目標(biāo)檢測效果。

Otsu算法；遺傳算法；模擬退火算法；三幀差分；閾值分割

圖像分割是數(shù)字圖像處理、視頻分析的基礎(chǔ)，分割結(jié)果直接影響目標(biāo)檢測、識別及跟蹤的效果[1]。在各種圖像分割算法中， Otsu算法[2]以其簡單、有效等優(yōu)點(diǎn)在閾值分割中被廣泛使用。然而怎樣確定最優(yōu)閾值使分割效果最佳一直是閾值分割的研究熱點(diǎn)和難點(diǎn)。視頻序列由一幀幀連續(xù)圖像組成，序列中相鄰幀之間具有較強(qiáng)的相關(guān)性，其分割閾值十分相近。本文針對視頻序列中提取運(yùn)動目標(biāo)時Otsu算法效率低、難以適用廣泛自然圖像的不足，利用視頻序列的幀間相關(guān)性，并結(jié)合遺傳算法和模擬退火算法對Otsu算法進(jìn)行改進(jìn)，提升算法運(yùn)行效率，再與三幀差分法相結(jié)合，提高運(yùn)動目標(biāo)的檢測效果。

1 Otsu算法

Otsu算法是一種自適應(yīng)閾值分割算法，原理是將圖像按灰度級分成目標(biāo)和背景兩個部分，并通過方差的計算尋找一個合適的閾值進(jìn)行分割，計算方法如下：

σ2=ω0(μ0-μ)2+ω1(μ1-μ)2

(1)

其中，最佳閾值t*為方差的最大值[2-6]。

可以看出，最佳閾值的確定需要對圖像中所有的灰度值進(jìn)行遍歷[3]。當(dāng)圖像目標(biāo)與背景差異不明顯，灰度直方圖難以形成明顯的雙峰，或圖像中噪聲較多時，最優(yōu)閾值難以準(zhǔn)確判定。

許多研究人員針對該算法的缺陷利用不同思路提出了不同的改進(jìn)方法，例如文獻(xiàn)[3]針對目標(biāo)與背景間差異較小的特定圖像，對Otsu算法獲得的閾值賦予固定權(quán)重。文獻(xiàn)[4]針對目標(biāo)與背景差異較大的同類圖像，交換Otsu算法中類間均值求方差。該類改進(jìn)方法均提高特定圖像的分割效果，難以適用于廣泛的自然圖像。文獻(xiàn)[5]針對特定目標(biāo)的紅外圖像，運(yùn)用圖像平均灰度值做初始閾值，在較小灰度范圍逐步遞推Otsu的最佳閾值，但該方法只能檢測特定圖像中的特定目標(biāo)。文獻(xiàn)[6]運(yùn)用蟻群算法對Otsu算法進(jìn)行優(yōu)化，通過減少最優(yōu)閾值的嘗試次數(shù)來提升搜索速度，提高算法實(shí)時性。

2 基于遺傳模擬退火的Otsu算法改進(jìn)

2.1 遺傳算法

遺傳算法[7]是模仿生物基因自然選擇過程的搜索算法，在解決復(fù)雜問題時具有明顯優(yōu)越性。該方法對待解決問題的多種解用特定的染色體表示，其解的搜索空間可視為多個染色體在范圍一定的空間中形成的特定種群，通過模仿自然界中生物進(jìn)化的優(yōu)勝劣汰、適者生存的法則，利用自適應(yīng)度函數(shù)計算每個個體的適應(yīng)度值，并通過適應(yīng)度值的大小評價解的優(yōu)劣。通過選擇、交叉和變異等操作實(shí)現(xiàn)解的進(jìn)化，在不斷的進(jìn)化與更新中，求得問題相對的最優(yōu)解值，算法流程如下：

步驟1：種群初始化和編碼。在搜索空間隨機(jī)產(chǎn)生N個個體作為初始種群，并計算每個個體的適應(yīng)度。因?yàn)閳D像的灰度值是在0～255之間，所以每個染色體編碼為8位二進(jìn)制，即可以表示成 00000000～11111111 中的任意一個值[6]。

步驟2：適應(yīng)度函數(shù)。將式(1)作為適應(yīng)度函數(shù)。

步驟3：選擇。采用常用的輪盤賭選擇(roulette wheel selection)[8], 并結(jié)合最優(yōu)保留策略,保證算法收斂到全局最優(yōu)解。在群體交叉之前,先按需保留最佳個體,直接遺傳到子代群體中,其余個體采用輪盤賭選擇法選擇。

步驟4：交叉和變異。交叉和變異的概率Pc與Pm計算公式為

(2)

首先，從當(dāng)代種群中按輪盤賭選擇方法選擇兩個個體,然后根據(jù)染色體的適應(yīng)度函數(shù)值計算交叉概率，繼而進(jìn)行交叉(父代個體的相同閾值直接遺傳給后代,不同的閾值保留適應(yīng)度大的閾值)形成新的染色體。為了提高種群的進(jìn)化效率，對隨機(jī)選擇中具有較小函數(shù)值的個體進(jìn)行變異，即對染色體的一個或多個基因進(jìn)行位變異(依次計算待變異染色體上所有基因的閾值適應(yīng)度，然后從對應(yīng)的備選路徑集中隨機(jī)選擇另一個閾值替換適應(yīng)度最低的基因閾值)。

步驟5：終止條件。采用遺傳代數(shù)控制法和基于不改變規(guī)則的控制法。即當(dāng)最優(yōu)個體和群體的適應(yīng)度不再上升時，或者迭代次數(shù)達(dá)到預(yù)設(shè)值時算法終止(預(yù)設(shè)值一般設(shè)置為100～500)。

該算法通過群體搜索策略和遺傳算子實(shí)現(xiàn)在整個解空間中的探索，克服傳統(tǒng)的啟發(fā)式優(yōu)化算法的鄰域搜索限制，減少人工依賴，但存在搜索速度慢、尋找局部最優(yōu)解的能力不強(qiáng)和容易早熟收斂的缺陷。

2.2 模擬退火算法

模擬退火算法[10]是模仿物理中固體物質(zhì)的退火過程的選擇優(yōu)化算法，在尋找全局最優(yōu)解時具有較好的爬山性能。該方法從較高的初始溫度出發(fā)，隨著溫度參數(shù)的不斷下降中，在概率突跳特性作用下能克服并跳出當(dāng)前的局部最優(yōu)解，隨機(jī)在解空間中尋找目標(biāo)函數(shù)的最優(yōu)解，并最終趨于全局最優(yōu)解，算法流程如下：

步驟1：確定初溫。初始溫度t0=kδ應(yīng)充分大,使幾乎所有產(chǎn)生的候選解都能被接受,以此保證最終優(yōu)良的收斂性。其中,k為充分大的數(shù),δ=fmax-fmin,fmax為初始種群中的最大目標(biāo)函數(shù)值，fmin為種群的最小目標(biāo)函數(shù)值。

步驟2：溫度的衰減函數(shù)。設(shè)置合理的衰減函數(shù)仿物理中固體物質(zhì)的退火過程的選擇優(yōu)化過程，ε為無窮小正數(shù)

tk+1=tk/[1+tkln(1+ε)/3tk],k=0,1,2,…

(4)

步驟3：狀態(tài)躍遷。構(gòu)造鄰域解集,根據(jù)Metropolis判別準(zhǔn)則[11]形成新一代種群。盡管算法的最終目的是為了尋找全局最優(yōu), 但以概率exp(Δf/tk)出現(xiàn)的非最優(yōu)解還是被采用以避免陷入局部最優(yōu)。

Metropolis判別準(zhǔn)則：另Δf=fit(Ti)-fit(Tj),若Δf≤0||r

2.3 改進(jìn)的Otsu算法

視頻圖像序列的相鄰幀間目標(biāo)和背景的分割閾值相近。本文考慮視頻序列的幀間相關(guān)性，利用上一幀圖像的閾值及其鄰域解作為下一幀圖像的初始解，利用遺傳算法尋找最優(yōu)閾值，并使用模擬退火算法執(zhí)行交叉變異步驟，提高選取最優(yōu)閾值的準(zhǔn)確性。算法的詳細(xì)流程如下：

在搜索空間隨機(jī)產(chǎn)生N個個體作為初始種群，并將染色體編碼為8位二進(jìn)制數(shù)；

While(i<200)

{gen(0)=0;

while(適應(yīng)值不斷變化或gen

{gen++；

計算各個體的適應(yīng)值保留最優(yōu)個體；

按輪盤賭選擇某些剩余個體構(gòu)成新群體Pc；

隨機(jī)地組成交配對；

實(shí)施交叉和變異操作；

對每個當(dāng)前解：

構(gòu)造鄰域解集；

T=t0;

While (T)

{If未接受新解的次數(shù)n<=N

根據(jù)Metropolis判斷準(zhǔn)則形成新種群，保留最優(yōu)個體；

溫度衰減；}

} //end_while

保存最優(yōu)閾值;

在最優(yōu)閾值的鄰域內(nèi)產(chǎn)生N個個體作為下一代的初始種群，并將染色體編碼為8位二進(jìn)制數(shù)；}

3 結(jié)合三幀差分法的運(yùn)動目標(biāo)檢測

三幀差分法[8]是通過視頻圖像序列的三幀相鄰圖像進(jìn)行差分。三幀圖像中，第一幀與第二幀進(jìn)行差分，第二幀與第三幀進(jìn)行差分，然后將兩個差分圖進(jìn)行“與”運(yùn)算，檢測的運(yùn)動區(qū)域較精確，且可以解決相鄰幀的遮擋問題。

設(shè)在某視頻中，連續(xù)三幀視頻圖像序列分別為fk-1(x,y)，fk(x,y)，fk+1(x,y)，將前一幀圖像與中間一幀相減得到運(yùn)動變化圖像g1(x,y)，中間一幀圖像與后一幀相減得到運(yùn)動變化圖像g2(x,y)，然后將運(yùn)動變化圖像g1(x,y)和g2(x,y)進(jìn)行“與”運(yùn)算，就會得到中間幀圖像的運(yùn)動目標(biāo)區(qū)域。

相“與”運(yùn)算的定義是

(5)

在不同的視頻圖像序列中，利用三幀差分法檢測的視頻運(yùn)動目標(biāo)的分割閾值并不相同，且通常需要人工設(shè)定，實(shí)際操作中工作量大，結(jié)果不精確。為增強(qiáng)三幀差分法中閾值選取的自適應(yīng)能力，先通過三幀差分檢測出視頻運(yùn)動區(qū)域，再利用前文提出的改進(jìn)的Otsu算法對閾值搜索進(jìn)行優(yōu)化，提高運(yùn)動目標(biāo)的檢測效果。其具體流程如圖1所示。

圖1 視頻運(yùn)動目標(biāo)檢測流程圖

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

4.1 改進(jìn)的Otsu算法實(shí)驗(yàn)分析

首先為驗(yàn)證利用遺傳模擬退火改進(jìn)的Otsu算法的有效性，將改進(jìn)算法與原Otsu算法、文獻(xiàn)[12]中利用遺傳算法改進(jìn)的Otsu算法分別進(jìn)行分析對比(見圖2)。實(shí)驗(yàn)環(huán)境和算法運(yùn)行參數(shù)配置如下：在Windows 7系統(tǒng)下，4 Gbyte內(nèi)存，IDE采用Vs2010并結(jié)合Opencv2.4.3。測試圖像灰度級為256×256，種群的個體總數(shù)為10，編碼長度為8，交叉概率Pc=0.6，變異概率Pm=0.1，迭代代數(shù)為200，初始退火溫度為888。分別對兩種算法進(jìn)行50次運(yùn)算。

c 文獻(xiàn)[5]算法 d 本文算法圖2 圖像二值化分

從實(shí)驗(yàn)結(jié)果可以看出，3種算法的分割結(jié)果一定程度上受到圖像噪聲影響，但是改進(jìn)的Otsu算法的分割結(jié)果的噪聲點(diǎn)相對原Otsu算法較少，其分割的效果也較好，單一利用遺傳算法對Otsu算法進(jìn)行優(yōu)化后分割效果較Otsu算法有一定改善，但相較本文算法，背景的部分區(qū)域仍被視為前景，前景目標(biāo)輪廓存在明顯的背景干擾，難以準(zhǔn)確分割，說明選取的閾值不如本文算法準(zhǔn)確。

任選6段視頻圖像序列比較3種算法的分割性能，衡量閾值的獲取次數(shù)、尋優(yōu)時間和全局最優(yōu)閾值，分別運(yùn)行50次后取平均值，運(yùn)行結(jié)果如表1所示。

表1 6段視頻序列圖像的算法性能比較

視頻序列圖像編號Otsu算法文獻(xiàn)[12]算法本文算法計算次數(shù)計算時間/ms最優(yōu)閾值計算次數(shù)計算時間/ms最優(yōu)閾值計算次數(shù)計算時間/ms最優(yōu)閾值12567.4151544.7062414.395822568.23113383.84125413.9312932569.43130615.30146413.7214842568.6676514.5495414.4689525611.7897453.95110414.3710762567.23123524.60134413.92131

對比分析可知，原Otsu算法尋找最優(yōu)閾值時遍歷圖像全部灰度級，花費(fèi)代價較高。本文算法相對Otsu算法，在尋優(yōu)時間和取值精度上都有一定的提升；相對文獻(xiàn)[12]中算法，利用前幀圖像信息設(shè)置初始種群，節(jié)約閾值尋找時間，避免全局最優(yōu)閾值尋找過程的早熟收斂，提高全局最優(yōu)閾值精度，使圖像二值化分割結(jié)果更準(zhǔn)確。

4.2 結(jié)合三幀差分法的運(yùn)動目標(biāo)檢測實(shí)驗(yàn)分析

為驗(yàn)證檢測運(yùn)動目標(biāo)的有效性，將本文方法與三幀差分法進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境與上節(jié)相同。實(shí)驗(yàn)采用兩組視頻圖像序列sample video和highway進(jìn)行分析。

圖3和圖4是分別是單目標(biāo)人物行走視頻和交通車輛監(jiān)控視頻，可以發(fā)現(xiàn)：三幀差分法處理檢測的目標(biāo)對象腿部具有較明顯的空洞，背景噪聲較多，車輛目標(biāo)不完全，邊緣不清晰；而本文方法顯著降低背景噪聲，有效減少目標(biāo)空洞，使人物目標(biāo)表現(xiàn)更完整，車輛的邊緣更整齊，噪聲更少。

a 第49幀 b 第50幀 c 第51幀

d 三幀差分法 e 本文方法 圖3 sample video實(shí)驗(yàn)結(jié)果

5 結(jié)論

從視頻序列中有效檢測運(yùn)動目標(biāo)是視頻智能分析的關(guān)鍵，設(shè)定合理的分割閾值能提高圖像目標(biāo)提取的精度。最大類間差法作為一種重要的閾值分割方法難以獲得準(zhǔn)確的分割閾值，影響圖像目標(biāo)檢測效果。本文結(jié)合視頻圖像序列相鄰幀間具有較強(qiáng)相關(guān)性的特點(diǎn)，利用遺傳模擬退火算法對該算法進(jìn)行改進(jìn)，減少尋優(yōu)嘗試次數(shù)，提升算法運(yùn)行效率，提高閾

a 第126幀 b 第127幀 c 第128幀

d 三幀差分法 e 本文方法 圖4 highway實(shí)驗(yàn)結(jié)果

值選擇精度。在結(jié)合三幀差分檢測運(yùn)動目標(biāo)時，由于閾值選取的合理，檢測的運(yùn)動目標(biāo)更完整，檢測效果更好。該方法不僅在閾值分割的運(yùn)行效率和閾值搜索的精度上較Otsu算法有所提高，而且在整體的運(yùn)動目標(biāo)檢測效果上較三幀差分法也體現(xiàn)出了一定優(yōu)勢。但由于三幀差分法只利用相鄰三幀的像素信息，存在像素信息的統(tǒng)計損失，導(dǎo)致檢測的運(yùn)動目標(biāo)仍不甚理想，需要進(jìn)一步研究。

[1] 戴青云，余英林．?dāng)?shù)學(xué)形態(tài)學(xué)在圖象處理中的應(yīng)用進(jìn)展[J]．控制理論與應(yīng)用．2001，18(4)∶478-482.

[2] OTSU N. A threshold selection method from gray level histograms[J]. IEEE Trans. Systems Man and Cybern，1979，9(1):62-66.

[3] 鐘雪君．一種改進(jìn)的Otsu雙閾值二值化圖像分割方法[J].電子世界，2013(4)：104.

[4] 付燃，白艷萍．一種新改進(jìn)的otsu算法[J].科技信息，2012(8):117.

[5] 陳崢，石勇鵬，吉書鵬．一種改進(jìn)的Otsu圖像閾值分割方法[J].激光與紅外，2012，42(5)：584-588.

[6] 陶輝，陳閩杰，賀石中,等．在線鐵譜圖像分析中基于蟻群算法改進(jìn)Otsu的設(shè)計與應(yīng)用[J]．電子設(shè)計工程，2014，10(22)：60-63.

[7] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence [M]. 2nd ed. Cambridge: MIT Press，1992.

[8] 許新征，丁世飛，史忠植，等．圖像分割的新理論和新方法[J]．電子學(xué)報，2010，38(2A)∶76-82.

[9] 胡敏，李梅，汪榮貴．改進(jìn)的Otsu算法在圖像分割中的應(yīng)用[J]．電子測量與儀器學(xué)報，2010，24(5)∶443-449.

[10] METROPOLIS N，ROSENBLUTH A，ROSEBLUTH M. Equation of state calculation by fast computing machines[J]. The Journal of Chemical Physics，1953(21):1087-1092.

[11] 王宏剛，曾建潮．基于Metropolis判別準(zhǔn)則的遺傳算法[J]．控制與決策，1998，13(2)∶181-184.

[12] 羅麗霞．基于遺傳算法的Otsu圖像分割方法[J].河北北方學(xué)院學(xué)報：自然科學(xué)版，2014，30(6)：29-33.

楊勝輝(1990— )，碩士生，主研圖像處理、視頻分析；

李太君(1964— )，教授，碩士生導(dǎo)師，主研數(shù)字圖像處理、網(wǎng)絡(luò)與多媒體通信，為本文通信作者；

肖 沙(1988— )，碩士生，主研圖像處理、視頻分析；

周浩理(1988— )，碩士生，主研數(shù)字圖像處理、視頻分析；

徐寧敏(1965— )，高級工程師，主研網(wǎng)絡(luò)安全、多媒體通信。

責(zé)任編輯：哈宏疆

Research on Improved Otsu Algorithm and Its Application in Moving Objection Detection

YANG Shenghui1，LI Taijun1，XIAO Sha1，ZHOU Haoli1，XU Ningmin2

(1.CollegeofInformationScience&Technology,HainanUniversity,Haikou570228,China;2.DepartmentofPublicSecurityofHainanProvince,Haikou570311,China)

Considering the problem of the Otsu adaptive threshold segmentation algorithm which the accuracy of the threshold search is lower and the efficiency is not high in threshold search precision, in this paper, combined with the correlation between frames of video sequences, genetic algorithm is used with the advantage of global searching, and annealing algorithm is simulated with the better performance of mountain climbing, to improve Otsu algorithm. Then three frame difference method are contacted to detect moving objection in video sequences. Experimental results show that, the method reduced segmentation threshold optimization attempts, selected more accurate threshold compared with the traditional Otsu algorithm and comparison algorithm, and improved the target detection effects.

Otsu algorithm; genetic algorithm; simulated annealing algorithm; three frame difference method; threshold segmentation

海南省社會發(fā)展科技專項(xiàng)(SF201455)

TP393

A

10.16280/j.videoe.2015.24.024

2015-05-29

【本文獻(xiàn)信息】楊勝輝，李太君，肖沙，等.改進(jìn)的Otsu算法及在運(yùn)動目標(biāo)檢測中的應(yīng)用研究[J].電視技術(shù),2015，39(24).