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

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

改進的Otsu算法及在運動目標檢測中的應用研究

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

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

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

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

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

1 Otsu算法

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

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

(1)

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

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

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

2 基于遺傳模擬退火的Otsu算法改進

2.1 遺傳算法

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

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

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

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

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

(2)

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

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

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

2.2 模擬退火算法

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

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

步驟2：溫度的衰減函數(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判別準則[11]形成新一代種群。盡管算法的最終目的是為了尋找全局最優(yōu), 但以概率exp(Δf/tk)出現(xiàn)的非最優(yōu)解還是被采用以避免陷入局部最優(yōu)。

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

2.3 改進的Otsu算法

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

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

While(i<200)

{gen(0)=0;

while(適應值不斷變化或gen

{gen++；

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

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

隨機地組成交配對；

實施交叉和變異操作；

對每個當前解：

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

T=t0;

While (T)

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

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

溫度衰減；}

} //end_while

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

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

3 結(jié)合三幀差分法的運動目標檢測

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

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

相“與”運算的定義是

(5)

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

圖1 視頻運動目標檢測流程圖

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

4.1 改進的Otsu算法實驗分析

首先為驗證利用遺傳模擬退火改進的Otsu算法的有效性，將改進算法與原Otsu算法、文獻[12]中利用遺傳算法改進的Otsu算法分別進行分析對比(見圖2)。實驗環(huá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。分別對兩種算法進行50次運算。

c 文獻[5]算法 d 本文算法圖2 圖像二值化分

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

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

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

視頻序列圖像編號Otsu算法文獻[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)閾值時遍歷圖像全部灰度級，花費代價較高。本文算法相對Otsu算法，在尋優(yōu)時間和取值精度上都有一定的提升；相對文獻[12]中算法，利用前幀圖像信息設置初始種群，節(jié)約閾值尋找時間，避免全局最優(yōu)閾值尋找過程的早熟收斂，提高全局最優(yōu)閾值精度，使圖像二值化分割結(jié)果更準確。

4.2 結(jié)合三幀差分法的運動目標檢測實驗分析

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

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

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

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

5 結(jié)論

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

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

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

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

[1] 戴青云，余英林．數(shù)學形態(tài)學在圖象處理中的應用進展[J]．控制理論與應用．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] 鐘雪君．一種改進的Otsu雙閾值二值化圖像分割方法[J].電子世界，2013(4)：104.

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

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

[6] 陶輝，陳閩杰，賀石中,等．在線鐵譜圖像分析中基于蟻群算法改進Otsu的設計與應用[J]．電子設計工程，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]．電子學報，2010，38(2A)∶76-82.

[9] 胡敏，李梅，汪榮貴．改進的Otsu算法在圖像分割中的應用[J]．電子測量與儀器學報，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判別準則的遺傳算法[J]．控制與決策，1998，13(2)∶181-184.

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

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

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

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

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

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

責任編輯：哈宏疆

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ā)展科技專項(SF201455)

TP393

A

10.16280/j.videoe.2015.24.024

2015-05-29

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