基于meanshift算法的文字分割及应用

杨富元，周晓东

（长春工业大学 机械工程学院，长春 130012）

0 引言

在工业生产一次性血袋时，把一种特殊纸带上的材料通过热转印技术，转印到血袋表面上，在血袋表面留下一串字符，纸带上材料因为热转印到血袋上形成镂空的字符串。该字符串的唯一性、正确性决定一次性血袋能否正常使用。因此，血袋上字符串成为不可缺少的检测信息。而对字符串的分割是字符串自动识别的重要组成部分。在文字识别的领域中，有很多的文字分割方法，如基于边缘的方法［1］，基于颜色聚类的方法［2］，基于纹理的方法［3］，基于直方图的方法［4］，对于不同场合应用，各有优缺点。从Fukunaga 等在1975 年提出mean shift 方法，到1995 年Yizong Cheng［5］对mean shift 定义了核函数及权重函数，拓宽了mean shift 的应用范围，到Comaniciu 等［6］把跟踪问题近似为Mean Shift 最优化问题，利用mean shift 可以进行跟踪。而针对视频流中连续字符的分割，mean shift 具有很好的鲁棒性及运算较快的特点。应用改进的mean shift 跟踪算法可对纸带上的字符串进行较高效、准确的文字分割。

1 Mean shift 基本原理

设在d 维空间Rd 中，存在n 个样本点xi，i=1，2，…，n，在x 点的Mean Shift 向量的基本形式定义为：

其中，Sh是满足以下关系的y 点的集合，h为该区域半径，k 代表Sh区域中的样本点xi的数量。

式（1）中的（xi－x），可以看成Sh区域中任意点xi到点x 的偏移向量，而向量Mh（x）就是对在Sh区域中的k 个样本点的到点x 的偏移向量求和后再平均。该向量就是指向Sh区域内的概率密度增加最大的方向，也就是说mean shift 向量指向概率密度梯度方向。

2 目标模型的描述

我们要对印有血袋编码的纸带利用mean shift 算法进行文字分割，首先要对血袋编码的视频流进行目标区域的选定，我们用灰度直方图或彩色直方图描述该目标，设定目标中心在x0处，则该物体可以表示为：

式中，C为qu的直方图归一化常数，n 是模板中像素的数量，x0是模板的中心位置，k 是核函数，可以对远离中心x0的像素分配较小的权值，较近的像素分配较大的权值，增加算法的鲁棒性。而xi为像素在模板中的位置，h为核函数带宽。

3 候选模型的描述

候选的位于y 的物体可以描述为：

式中，y 是候选目标模型的中心位置，xi是候选目标模板中的相对位置，其他与式（3）中相同。因此目标跟踪可以转换为寻找最优的y，使得pu（y）与qu最相似。

4 用Bhattacharrya 系数度量相似性

在得到目标模型和候选模型的概率密度函数后，用Bhattacharyya 系数评价pu（y）与qu的相似性，从而寻找到当前帧的目标位置。目标模型的概率分布qu（y0）与候选模型概率分布pu（y）的Bhattacharyya 系数为：

进行泰勒展开，得

由于目标连续运动的连续性，候选位置y0变化不大，可以省略高次项。

将式（5）带入式（7）中，得

式（7）中，第一项为定值与y 无关，因此第二子项是当前帧的位置y 处，利用wi加权的核函数k（x）估算密度概率函数。概率密度的极值能用mean shift 理论求得。将ρ（y）求偏导，并使其等于0。当ρ（y）取最大值时，

ρ（y）值越大时，模板与候选区域的相似度就越高。通过mean shift 算法的不断迭代与匹配，核函数中心向模板最相似的位置靠近，从而完成跟踪。

5 目标定位

假设前一帧目标的位置为y0，首先计算出当前帧中y0位置候选目标的Pu（y0），根据式（9）计算出ρ［pu（y0），q］，为了在当前帧中找到和目标模型最相似图像的位置，ρ［pu（y0），q］应当取最大，在跟踪过程中，核函数中心位置从前一帧目标位置y0不断向新一帧中心位置y1处移动：

其中g（x）=-k′（x），且设k′（x）的区间x∈［0，∞］除有限点外都存在。

6 预测定位及文字分割

传统的Mean Shift 跟踪算法是以第一帧的目标中心位置为起始点开始搜索的，在搜索过程中目标模型与候选模型不断匹配，因为模型之间重叠区域较少，需要经过多次迭代计算，找到目标的实际位置，使得该算法花费大量时间进行计算，而这对实现实时跟踪是相矛盾的。因此，为了实现实时跟踪，我们可以提前预测目标中心位置，让预测的目标的中心位置在实际的中心位置附近，以达到目标模型与候选模型区域重叠的最大化，减少迭代步骤的目的。血袋字符是直线运动的，我们可以根据字符运动的速度进行预测，完成跟踪。进行跟踪的血袋纸带上面的字符串上的间隔是基本相等的，我们可以利用第一次追踪的结果加上两个字符串中心的间距r，预测出下一帧字符串的中心位置，然后从预测位置开始搜索迭代，这样就大大减少了算法的迭代次数，提高了追踪效率。

实验中记录血袋条码的视频流为每秒a 帧，每秒中记录完整进入屏幕到走出的b 个字符串，当第一行字符串经过a/b 帧之后，利用mean shift 算法计算的目标中心为y1，完成一次分割。然后目标模型中心更换为y1+r，继续对下一目标跟踪，完成连续分割。

7 实验结果

本实验采用的时频流为每秒30 帧，图像大小为720×576，目标模板为420×100。下面列举了部分跟踪分割图像，如图1 所示。

图1（a）为初始帧，当给定初始点后，不需要输入任何参数，将自动连续的进行文字分割，如图1（b）、（c）所示。

图1（b）为匹配模板跟踪分割的字符串1P759089，图1（c）为更换目标模板为1P789088，图1（d）为新匹配模板跟踪分割的字符串1P759088。

在相同条件下，以不同方法对该视频流进行字符分割，结果如表1 所示。

从表1 可以看出，在相同条件下mean shift 算法比其进行文字分割。他几种方法速度快。

图1 血袋编码跟踪分割图像

表1 不同算法分割一条字符所需时间 ms

8 结论

利用mean shift 算法，使用直方图描述目标的纹理及边缘特征，能快速有效地对连续字符的时频流进行文字分割，并且运用预测的方法减少了mean shift 算法中的迭代步骤，使搜索过程快速收敛，减少了运行时间。但直方图信息的单一性，也使得分割区域的中心与实际中心有一定偏差，本文以放大分割区域来实现准确的分割。实验结果证明，利用mean shift 算法能快速有效地对连续字符

［1］许剑峰.数字视频中的文本分割的研究［D］.广州：华南理工大学，2005.

［2］陈黎，黄心汉，王敏，等.基于聚类分析的车牌字符分割方法［J］.计算机工程与应用，2002，38（6）：221-222，256.

［3］杨大鹏，高向东，刘红.基于纹理特征的道路行人识别研究［J］.机械设计与制造，2012（1）：182-184.

［4］凌彤辉，黄山，王新增，等.车牌字符分割算法的研究［J］.中国测试技术，2005，31（1）：41-43.

［5］CHENG Yizong.Mean shift，mode seeking，and clustering［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1995，17（8）：790-799.

［6］COMANICIU，D，RAMESH V，MEER P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）：564-577.

［7］张旭光，赵恩良，王延杰.基于Mean_shift 的灰度目标跟踪新算法［J］.光学技术，2007，33（2）：226-229.

［8］康一梅，谢晚冬，胡江，等.目标尺寸自适应的Mean-Shift 跟踪算法［J］.兵工学报，2011，32（2）：210-216.

［9］胡文广.运动人体检测及遮挡处理［D］.哈尔滨：哈尔滨工程大学，2009.

［10］乌恩.智能视频监控中运动目标检测与跟踪算法研究［D］.长沙：国防科学技术大学，2010.

［11］张昊，黄战华，郁道银，等.基于差分图像的运动目标跟踪与分割方法的应用研究［J］.光学技术，2005，31（4）：565－567.