改进的Otsu算法及在运动目标检测中的应用研究

杨胜辉，李太君，肖 沙，周浩理，徐宁敏

(1. 海南大学 信息科学技术学院，海南 海口 570228；2. 海南省公安厅，海南 海口 570311 )

改进的Otsu算法及在运动目标检测中的应用研究

杨胜辉1，李太君1，肖 沙1，周浩理1，徐宁敏2

(1. 海南大学 信息科学技术学院，海南 海口 570228；2. 海南省公安厅，海南 海口 570311 )

针对Otsu自适应阈值分割算法中阈值搜索精准度较低、效率不高的问题，结合视频图像序列的帧间相关性，利用遗传算法的全局寻优优势，及模拟退火算法较好的爬山性能，提出一种改进的Otsu算法，并与三帧差分法相结合应用于视频运动目标检测。实验证明，该算法相对Otsu算法和对比算法减少阈值分割中的寻优尝试次数，使最优阈值的选取更精确，并提高了目标检测效果。

Otsu算法；遗传算法；模拟退火算法；三帧差分；阈值分割

图像分割是数字图像处理、视频分析的基础，分割结果直接影响目标检测、识别及跟踪的效果[1]。在各种图像分割算法中， Otsu算法[2]以其简单、有效等优点在阈值分割中被广泛使用。然而怎样确定最优阈值使分割效果最佳一直是阈值分割的研究热点和难点。视频序列由一帧帧连续图像组成，序列中相邻帧之间具有较强的相关性，其分割阈值十分相近。本文针对视频序列中提取运动目标时Otsu算法效率低、难以适用广泛自然图像的不足，利用视频序列的帧间相关性，并结合遗传算法和模拟退火算法对Otsu算法进行改进，提升算法运行效率，再与三帧差分法相结合，提高运动目标的检测效果。

1 Otsu算法

Otsu算法是一种自适应阈值分割算法，原理是将图像按灰度级分成目标和背景两个部分，并通过方差的计算寻找一个合适的阈值进行分割，计算方法如下：

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

(1)

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

可以看出，最佳阈值的确定需要对图像中所有的灰度值进行遍历[3]。当图像目标与背景差异不明显，灰度直方图难以形成明显的双峰，或图像中噪声较多时，最优阈值难以准确判定。

许多研究人员针对该算法的缺陷利用不同思路提出了不同的改进方法，例如文献[3]针对目标与背景间差异较小的特定图像，对Otsu算法获得的阈值赋予固定权重。文献[4]针对目标与背景差异较大的同类图像，交换Otsu算法中类间均值求方差。该类改进方法均提高特定图像的分割效果，难以适用于广泛的自然图像。文献[5]针对特定目标的红外图像，运用图像平均灰度值做初始阈值，在较小灰度范围逐步递推Otsu的最佳阈值，但该方法只能检测特定图像中的特定目标。文献[6]运用蚁群算法对Otsu算法进行优化，通过减少最优阈值的尝试次数来提升搜索速度，提高算法实时性。

2 基于遗传模拟退火的Otsu算法改进

2.1 遗传算法

遗传算法[7]是模仿生物基因自然选择过程的搜索算法，在解决复杂问题时具有明显优越性。该方法对待解决问题的多种解用特定的染色体表示，其解的搜索空间可视为多个染色体在范围一定的空间中形成的特定种群，通过模仿自然界中生物进化的优胜劣汰、适者生存的法则，利用自适应度函数计算每个个体的适应度值，并通过适应度值的大小评价解的优劣。通过选择、交叉和变异等操作实现解的进化，在不断的进化与更新中，求得问题相对的最优解值，算法流程如下：

步骤1：种群初始化和编码。在搜索空间随机产生N个个体作为初始种群，并计算每个个体的适应度。因为图像的灰度值是在0～255之间，所以每个染色体编码为8位二进制，即可以表示成 00000000～11111111 中的任意一个值[6]。

步骤2：适应度函数。将式(1)作为适应度函数。

步骤3：选择。采用常用的轮盘赌选择(roulette wheel selection)[8], 并结合最优保留策略,保证算法收敛到全局最优解。在群体交叉之前,先按需保留最佳个体,直接遗传到子代群体中,其余个体采用轮盘赌选择法选择。

步骤4：交叉和变异。交叉和变异的概率Pc与Pm计算公式为

(2)

首先，从当代种群中按轮盘赌选择方法选择两个个体,然后根据染色体的适应度函数值计算交叉概率，继而进行交叉(父代个体的相同阈值直接遗传给后代,不同的阈值保留适应度大的阈值)形成新的染色体。为了提高种群的进化效率，对随机选择中具有较小函数值的个体进行变异，即对染色体的一个或多个基因进行位变异(依次计算待变异染色体上所有基因的阈值适应度，然后从对应的备选路径集中随机选择另一个阈值替换适应度最低的基因阈值)。

步骤5：终止条件。采用遗传代数控制法和基于不改变规则的控制法。即当最优个体和群体的适应度不再上升时，或者迭代次数达到预设值时算法终止(预设值一般设置为100～500)。

该算法通过群体搜索策略和遗传算子实现在整个解空间中的探索，克服传统的启发式优化算法的邻域搜索限制，减少人工依赖，但存在搜索速度慢、寻找局部最优解的能力不强和容易早熟收敛的缺陷。

2.2 模拟退火算法

模拟退火算法[10]是模仿物理中固体物质的退火过程的选择优化算法，在寻找全局最优解时具有较好的爬山性能。该方法从较高的初始温度出发，随着温度参数的不断下降中，在概率突跳特性作用下能克服并跳出当前的局部最优解，随机在解空间中寻找目标函数的最优解，并最终趋于全局最优解，算法流程如下：

步骤1：确定初温。初始温度t0=kδ应充分大,使几乎所有产生的候选解都能被接受,以此保证最终优良的收敛性。其中,k为充分大的数,δ=fmax-fmin,fmax为初始种群中的最大目标函数值，fmin为种群的最小目标函数值。

步骤2：温度的衰减函数。设置合理的衰减函数仿物理中固体物质的退火过程的选择优化过程，ε为无穷小正数

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

(4)

步骤3：状态跃迁。构造邻域解集,根据Metropolis判别准则[11]形成新一代种群。尽管算法的最终目的是为了寻找全局最优, 但以概率exp(Δf/tk)出现的非最优解还是被采用以避免陷入局部最优。

Metropolis判别准则：另Δf=fit(Ti)-fit(Tj),若Δf≤0||r

2.3 改进的Otsu算法

视频图像序列的相邻帧间目标和背景的分割阈值相近。本文考虑视频序列的帧间相关性，利用上一帧图像的阈值及其邻域解作为下一帧图像的初始解，利用遗传算法寻找最优阈值，并使用模拟退火算法执行交叉变异步骤，提高选取最优阈值的准确性。算法的详细流程如下：

在搜索空间随机产生N个个体作为初始种群，并将染色体编码为8位二进制数；

While(i<200)

{gen(0)=0;

while(适应值不断变化或gen

{gen++；

计算各个体的适应值保留最优个体；

按轮盘赌选择某些剩余个体构成新群体Pc；

随机地组成交配对；

实施交叉和变异操作；

对每个当前解：

构造邻域解集；

T=t0;

While (T)

{If未接受新解的次数n<=N

根据Metropolis判断准则形成新种群，保留最优个体；

温度衰减；}

} //end_while

保存最优阈值;

在最优阈值的邻域内产生N个个体作为下一代的初始种群，并将染色体编码为8位二进制数；}

3 结合三帧差分法的运动目标检测

三帧差分法[8]是通过视频图像序列的三帧相邻图像进行差分。三帧图像中，第一帧与第二帧进行差分，第二帧与第三帧进行差分，然后将两个差分图进行“与”运算，检测的运动区域较精确，且可以解决相邻帧的遮挡问题。

设在某视频中，连续三帧视频图像序列分别为fk-1(x,y)，fk(x,y)，fk+1(x,y)，将前一帧图像与中间一帧相减得到运动变化图像g1(x,y)，中间一帧图像与后一帧相减得到运动变化图像g2(x,y)，然后将运动变化图像g1(x,y)和g2(x,y)进行“与”运算，就会得到中间帧图像的运动目标区域。

相“与”运算的定义是

(5)

在不同的视频图像序列中，利用三帧差分法检测的视频运动目标的分割阈值并不相同，且通常需要人工设定，实际操作中工作量大，结果不精确。为增强三帧差分法中阈值选取的自适应能力，先通过三帧差分检测出视频运动区域，再利用前文提出的改进的Otsu算法对阈值搜索进行优化，提高运动目标的检测效果。其具体流程如图1所示。

图1 视频运动目标检测流程图

4 实验结果与分析

4.1 改进的Otsu算法实验分析

首先为验证利用遗传模拟退火改进的Otsu算法的有效性，将改进算法与原Otsu算法、文献[12]中利用遗传算法改进的Otsu算法分别进行分析对比(见图2)。实验环境和算法运行参数配置如下：在Windows 7系统下，4 Gbyte内存，IDE采用Vs2010并结合Opencv2.4.3。测试图像灰度级为256×256，种群的个体总数为10，编码长度为8，交叉概率Pc=0.6，变异概率Pm=0.1，迭代代数为200，初始退火温度为888。分别对两种算法进行50次运算。

c 文献[5]算法 d 本文算法图2 图像二值化分

从实验结果可以看出，3种算法的分割结果一定程度上受到图像噪声影响，但是改进的Otsu算法的分割结果的噪声点相对原Otsu算法较少，其分割的效果也较好，单一利用遗传算法对Otsu算法进行优化后分割效果较Otsu算法有一定改善，但相较本文算法，背景的部分区域仍被视为前景，前景目标轮廓存在明显的背景干扰，难以准确分割，说明选取的阈值不如本文算法准确。

任选6段视频图像序列比较3种算法的分割性能，衡量阈值的获取次数、寻优时间和全局最优阈值，分别运行50次后取平均值，运行结果如表1所示。

表1 6段视频序列图像的算法性能比较

视频序列图像编号Otsu算法文献[12]算法本文算法计算次数计算时间/ms最优阈值计算次数计算时间/ms最优阈值计算次数计算时间/ms最优阈值12567.4151544.7062414.395822568.23113383.84125413.9312932569.43130615.30146413.7214842568.6676514.5495414.4689525611.7897453.95110414.3710762567.23123524.60134413.92131

对比分析可知，原Otsu算法寻找最优阈值时遍历图像全部灰度级，花费代价较高。本文算法相对Otsu算法，在寻优时间和取值精度上都有一定的提升；相对文献[12]中算法，利用前帧图像信息设置初始种群，节约阈值寻找时间，避免全局最优阈值寻找过程的早熟收敛，提高全局最优阈值精度，使图像二值化分割结果更准确。

4.2 结合三帧差分法的运动目标检测实验分析

为验证检测运动目标的有效性，将本文方法与三帧差分法进行对比实验，实验环境与上节相同。实验采用两组视频图像序列sample video和highway进行分析。

图3和图4是分别是单目标人物行走视频和交通车辆监控视频，可以发现：三帧差分法处理检测的目标对象腿部具有较明显的空洞，背景噪声较多，车辆目标不完全，边缘不清晰；而本文方法显著降低背景噪声，有效减少目标空洞，使人物目标表现更完整，车辆的边缘更整齐，噪声更少。

a 第49帧 b 第50帧 c 第51帧

d 三帧差分法 e 本文方法 图3 sample video实验结果

5 结论

从视频序列中有效检测运动目标是视频智能分析的关键，设定合理的分割阈值能提高图像目标提取的精度。最大类间差法作为一种重要的阈值分割方法难以获得准确的分割阈值，影响图像目标检测效果。本文结合视频图像序列相邻帧间具有较强相关性的特点，利用遗传模拟退火算法对该算法进行改进，减少寻优尝试次数，提升算法运行效率，提高阈

a 第126帧 b 第127帧 c 第128帧

d 三帧差分法 e 本文方法 图4 highway实验结果

值选择精度。在结合三帧差分检测运动目标时，由于阈值选取的合理，检测的运动目标更完整，检测效果更好。该方法不仅在阈值分割的运行效率和阈值搜索的精度上较Otsu算法有所提高，而且在整体的运动目标检测效果上较三帧差分法也体现出了一定优势。但由于三帧差分法只利用相邻三帧的像素信息，存在像素信息的统计损失，导致检测的运动目标仍不甚理想，需要进一步研究。

[1] 戴青云，余英林．数学形态学在图象处理中的应用进展[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— )，教授，硕士生导师，主研数字图像处理、网络与多媒体通信，为本文通信作者；

肖 沙(1988— )，硕士生，主研图像处理、视频分析；

周浩理(1988— )，硕士生，主研数字图像处理、视频分析；

徐宁敏(1965— )，高级工程师，主研网络安全、多媒体通信。

责任编辑：哈宏疆

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

海南省社会发展科技专项(SF201455)

TP393

A

10.16280/j.videoe.2015.24.024

2015-05-29

【本文献信息】杨胜辉，李太君，肖沙，等.改进的Otsu算法及在运动目标检测中的应用研究[J].电视技术,2015，39(24).