第 25 卷第 6 期 齐 齐 哈 尔 大 学 学 报 Vol.25,No.6 2009 年 11 月 Journal of Qiqihar University Nov.,2009 模拟退火算法在视频序列图像 二值化阈值选取中的应用 郭锋1，陈燕1，杨晨晖2 (1. 郑州轻工业学院 计算机与通信工程系，郑州 450002 ；2 厦门大学 信息科学与技术学院 ，浙江 厦门 361005) 摘要：阈值的选取问题是图像二值化的过程中的一个关键问题，现有的方法主要是利用 Otsu 算法对分割阈 值从 0～255 的所有灰度值依次遍历，没有考虑视频两帧图像间的相关性。本文利用帧间相关性给出了一个 阈值选取算法，该算法在保存上一帧阈值的基础上，运用模拟退火算法对本帧阈值进行一种智能搜索，优化 了搜索策略，提高了运行效率。实验表明，该算法提高了阈值选取的效率。 关键词：模拟退火算法；Otsu算法；二值化 中图分类号：TP391 文献标识码：A 文章编号：1007-984X(2009)06-0020-03 图像二值化的过程中，阈值的选取极其关键，图像的灰度变化范围很大，在其中选择一个最合适的值 作为阈值，是一个典型的优化选择问题。根据所选取的阈值，将图像分成目标和背景两大类。在目标的识 别和跟踪系统[1]中，阈值选取是其中非常重要的环节，直接影响目标的定位、识别和后期跟踪环节的精度， 同时也决定了整个系统的性能；在实时性系统中，如果在不影响阈值精度的前提下，能适当地减少运行时 间。因此，图像二值化阈值选取具有重要的理论和应用价值。已有的方法主要是利用 Otsu 算法，该算法的 思想是：对分割阈值从 0～255 的所有灰度值依次遍历求得阈值，代价很高。视频序列前后两帧有很大的 相关性，前后两帧图像二值化所选的阈值很相近。已有的研究中基本没有利用这种相关性，因此本文利用 帧间相关性给出了一个阈值选取算法，该算法在保存上一帧阈值的基础上，运用模拟退火算法对本帧阈值 进行一种智能搜索，优化了搜索策略，提高了运行效率。最后通过实验验证了该算法缩短了阈值选取的运 行时间，取得了较好的效果。 1 基础知识 （1）OTSU算法。最大类间方差法[2](Otsu法)是1979年N.Otsu提出的动态阈值方法,基本思想是在最小二 乘法原理的基础上利用图像的灰度直方图，以目标和背景的方差最大来动态地确定图像的分割阈值，通过 基本原理可以得到Otsu方法求出图像最佳阈值的公式为 * t = Arg Max t L 0 1 ≤ ≤ − ⎢ ⎣ P w w a 0 − ( a 2 ) + P w w b 0 − ( b 2 ) ⎥ ⎦ （1） 具体的数学推导和理论部分以及各个变量所代表的物理意义参见文献[2]。 （2）模拟退火算法。模拟退火算法[1]的基本思想就是用物质系统的退火过程来模拟优化问题的寻优过 程，当物质系统达到最小能量状态时，优化问题的目标函数也相应地达到全局最优值[2,3]。 模拟退火算法用 Metropolis 算法[4]产生优化问题解的序列，并由与 Metropolis 准则相应的概率转移。确 定是否进行从当前解 i 到新解 j 的转移。 iPi ( =⇒ ) j 1 j )( − ( f ⎧ ⎪ ⎨ exp( ⎪⎩ f ( i )) ) kt f f i )( i )( < > f f j )( j )( （2） 收稿日期：2009-09-04 基金项目：郑州轻工业学院博士基金资助项目（2008BSJJ012） 作者简介：郭锋（1981－），男，硕士，助教，主要研究领域为智能交通系统理论及应用。 

第 6 期 模拟退火算法在视频序列图像二值化阈值选取中的应用 ·21· 由上式可知，系统温度 t 决定着随机移动的转移（接受）概率。温度越高，则算法接受使目标函数上 升移动的能力越强，具有较强的“爬山”能力，温度很低则使目标函数值上升移动的接受概率很低。 2 基于模拟退火算法的阈值选取 视频跟踪系统中，视频图像序列具有很大的信息冗余，具有极大的帧间相关性，所以前后两帧选取的 阈值很相近，根据这种特性，基于模拟退火算法思想，对 Otsu 算法进行了改进，提出了基于模拟退火算法 的阈值选取算法。最佳阈值的确定过程，就是在整个灰度级范围内搜索函数极值的过程，实际应用中由于 帧间的相关性，相邻帧的阈值非常接近，故保存上一帧处理得到的分割阈值作为该帧模拟退火算法的初值 迭代解，对本帧图片阈值进行智能搜索，并保存整个模拟退火过程中的最优解。主要步骤如下： （1）编码：在模拟退火算法中，解空间是一个二进制字符串，所有的解都具有相同的长度。编码的 任务是将变量 x 的所有可能取值都用解空间表示，因此需要首先确定解长度。因为总共为 256 个灰度级， 所以可以用 8 位二进制表示，即可以表示成 00000000～11111111 中的任意一个解值，这样每一个 8 位二 进制数，代表一个可能的灰度值。 （2）目标函数：此时的目标函数即为方差 f(t)=ω0(µ0(t)-µ)2+ω1(µ1(t)-µ)2=ω0ω1(µ0(t)-µ1(t))2 （3） µ0(t)和µ1(t)可以分别代表背景和目标的中心灰度，要使目标和背景得到最好的分割，当然希望两者的 差值尽量大，及(µ0(t)-µ1(t))2 或 | µ0(t)-µ1(t) |尽量大，从而类间方差 f(t)的值越大，f(t)越大，表明运动目标越 可以更好的被分割出来。因此，类间方差 f(t)作为衡量不同阈值导出的类别分离性能的测量准则，极大化 f(t)的过程就是自动确定阈值的过程。 （3）新解的产生:对于 8 位的二进制数据，对其中随机任意一位进行取反操作，以得到新解，从一个 灰度阈值变为另一个可能的灰度阈值。例如若有解 01001101，若随机假定第七位取反，即为 01001111； 对应的灰度值即从 77 变为 79。 （4）代价函数差:代价函数差反映了新解是否是更优的解，即满足要求的解，本实例中，可以看成一 个依据 OTSU 算法，是否更有利于把目标分割出来的图像分割阈值。可设新解为 f(j)，上一代解为 f(i)，新 解和上一代解的代价函数差为△= f(j)- f(i)。△>0 表示新阈值更有利于把目标分割出来。 （5）接受准则:若新解的 f(j)大于上一代解为 f(i)，表明新解是更优的解，即更有利于目标被分割出来 的 阈 值 ， 则 直 接 接 受 ； 如 果 新 解 的 f(j) 小 于 上 一 代 解 为 f(i) ， 表 明 新 解 不 如 上 一 代 解 优 ， 但 若 ( f j )( − f ( i )) exp( kt ) > x （k 为一系数，x 为一随机数且 0

·22· 齐 齐 哈 尔 大 学 学 报 2009 年 (a) (b) (c) 图 1 基于模拟退火实验效果图 4 结束语 本文在深入分析视频运动车辆检测的过程后，根据其相邻帧的相关性，运用智能优化算法，提出了一 种运用模拟退火算法对视频图像阈值进行一种智能优化搜索的方法，并通过实验对该方法进行了验证，实 验表明，应用该方法能够取得较好的结果。 参考文献 [1] McKeown D M，Harvey W A，McDermot t J．Rule - Based Interpretation of Aerial Imagery [J]. IEEE Trans. on PatternAnal And Machine Intel，1985（7）: 570-585. [2] Parist R．Car plate recognition by neural networks and image processing[J]. IEEE International Symposium on Circuits and Systems, USA, 2000, 5（10）：98-106. [3] Lucidi S，Piccialli V．New calsses of globally convexized filled functions for global optimization[J]. Journal of global optimization, 2002（24）： 67-76. [4 ] Qi L，Zhong Wan，Yuefei,Yang．Global minimization of normal quartic polynomials based on the descent directions[J]. SIAM on Optimization,2005, 15（1）：275-302. Simulated annealing algorithm application in binary image of video sequence GUO Feng1，CHEN Yan1，YANG Chen-hui 2 (1.Zhengzhou Light Industry College, Zhengzhou 450002, China; 2.Xiamen University, Zhejiang Xiamen 361005, China) Abstract: Because the video sequence has great relevance, and threshold of adjacent frames is very close, the traditional OTSU method ergodic all gray value and obtain threshold, it is clumsy. In this paper, according to simulated annealing theory, we save a threshold of the previous frame and let it be initial value of simulated annealing algorithm, then intelligent search of the current frame. Finally, we can obtain a satisfied threshold. The experiments show that our algorithms shorten the running time and obtain a good result. Key words：simulated annealing algorithm；otsu algorithm；binary processing