基于meanshift算法的文字分割及應(yīng)用

楊富元，周曉東

（長春工業(yè)大學(xué) 機械工程學(xué)院，長春 130012）

0 引言

在工業(yè)生產(chǎn)一次性血袋時，把一種特殊紙帶上的材料通過熱轉(zhuǎn)印技術(shù)，轉(zhuǎn)印到血袋表面上，在血袋表面留下一串字符，紙帶上材料因為熱轉(zhuǎn)印到血袋上形成鏤空的字符串。該字符串的唯一性、正確性決定一次性血袋能否正常使用。因此，血袋上字符串成為不可缺少的檢測信息。而對字符串的分割是字符串自動識別的重要組成部分。在文字識別的領(lǐng)域中，有很多的文字分割方法，如基于邊緣的方法［1］，基于顏色聚類的方法［2］，基于紋理的方法［3］，基于直方圖的方法［4］，對于不同場合應(yīng)用，各有優(yōu)缺點。從Fukunaga 等在1975 年提出mean shift 方法，到1995 年Yizong Cheng［5］對mean shift 定義了核函數(shù)及權(quán)重函數(shù)，拓寬了mean shift 的應(yīng)用范圍，到Comaniciu 等［6］把跟蹤問題近似為Mean Shift 最優(yōu)化問題，利用mean shift 可以進行跟蹤。而針對視頻流中連續(xù)字符的分割，mean shift 具有很好的魯棒性及運算較快的特點。應(yīng)用改進的mean shift 跟蹤算法可對紙帶上的字符串進行較高效、準確的文字分割。

1 Mean shift 基本原理

設(shè)在d 維空間Rd 中，存在n 個樣本點xi，i=1，2，…，n，在x 點的Mean Shift 向量的基本形式定義為：

其中，Sh是滿足以下關(guān)系的y 點的集合，h為該區(qū)域半徑，k 代表Sh區(qū)域中的樣本點xi的數(shù)量。

式（1）中的（xi－x），可以看成Sh區(qū)域中任意點xi到點x 的偏移向量，而向量Mh（x）就是對在Sh區(qū)域中的k 個樣本點的到點x 的偏移向量求和后再平均。該向量就是指向Sh區(qū)域內(nèi)的概率密度增加最大的方向，也就是說mean shift 向量指向概率密度梯度方向。

2 目標模型的描述

我們要對印有血袋編碼的紙帶利用mean shift 算法進行文字分割，首先要對血袋編碼的視頻流進行目標區(qū)域的選定，我們用灰度直方圖或彩色直方圖描述該目標，設(shè)定目標中心在x0處，則該物體可以表示為：

式中，C為qu的直方圖歸一化常數(shù)，n 是模板中像素的數(shù)量，x0是模板的中心位置，k 是核函數(shù)，可以對遠離中心x0的像素分配較小的權(quán)值，較近的像素分配較大的權(quán)值，增加算法的魯棒性。而xi為像素在模板中的位置，h為核函數(shù)帶寬。

3 候選模型的描述

候選的位于y 的物體可以描述為：

式中，y 是候選目標模型的中心位置，xi是候選目標模板中的相對位置，其他與式（3）中相同。因此目標跟蹤可以轉(zhuǎn)換為尋找最優(yōu)的y，使得pu（y）與qu最相似。

4 用Bhattacharrya 系數(shù)度量相似性

在得到目標模型和候選模型的概率密度函數(shù)后，用Bhattacharyya 系數(shù)評價pu（y）與qu的相似性，從而尋找到當(dāng)前幀的目標位置。目標模型的概率分布qu（y0）與候選模型概率分布pu（y）的Bhattacharyya 系數(shù)為：

進行泰勒展開，得

由于目標連續(xù)運動的連續(xù)性，候選位置y0變化不大，可以省略高次項。

將式（5）帶入式（7）中，得

式（7）中，第一項為定值與y 無關(guān)，因此第二子項是當(dāng)前幀的位置y 處，利用wi加權(quán)的核函數(shù)k（x）估算密度概率函數(shù)。概率密度的極值能用mean shift 理論求得。將ρ（y）求偏導(dǎo)，并使其等于0。當(dāng)ρ（y）取最大值時，

ρ（y）值越大時，模板與候選區(qū)域的相似度就越高。通過mean shift 算法的不斷迭代與匹配，核函數(shù)中心向模板最相似的位置靠近，從而完成跟蹤。

5 目標定位

假設(shè)前一幀目標的位置為y0，首先計算出當(dāng)前幀中y0位置候選目標的Pu（y0），根據(jù)式（9）計算出ρ［pu（y0），q］，為了在當(dāng)前幀中找到和目標模型最相似圖像的位置，ρ［pu（y0），q］應(yīng)當(dāng)取最大，在跟蹤過程中，核函數(shù)中心位置從前一幀目標位置y0不斷向新一幀中心位置y1處移動：

其中g(shù)（x）=-k′（x），且設(shè)k′（x）的區(qū)間x∈［0，∞］除有限點外都存在。

6 預(yù)測定位及文字分割

傳統(tǒng)的Mean Shift 跟蹤算法是以第一幀的目標中心位置為起始點開始搜索的，在搜索過程中目標模型與候選模型不斷匹配，因為模型之間重疊區(qū)域較少，需要經(jīng)過多次迭代計算，找到目標的實際位置，使得該算法花費大量時間進行計算，而這對實現(xiàn)實時跟蹤是相矛盾的。因此，為了實現(xiàn)實時跟蹤，我們可以提前預(yù)測目標中心位置，讓預(yù)測的目標的中心位置在實際的中心位置附近，以達到目標模型與候選模型區(qū)域重疊的最大化，減少迭代步驟的目的。血袋字符是直線運動的，我們可以根據(jù)字符運動的速度進行預(yù)測，完成跟蹤。進行跟蹤的血袋紙帶上面的字符串上的間隔是基本相等的，我們可以利用第一次追蹤的結(jié)果加上兩個字符串中心的間距r，預(yù)測出下一幀字符串的中心位置，然后從預(yù)測位置開始搜索迭代，這樣就大大減少了算法的迭代次數(shù)，提高了追蹤效率。

實驗中記錄血袋條碼的視頻流為每秒a 幀，每秒中記錄完整進入屏幕到走出的b 個字符串，當(dāng)?shù)谝恍凶址?jīng)過a/b 幀之后，利用mean shift 算法計算的目標中心為y1，完成一次分割。然后目標模型中心更換為y1+r，繼續(xù)對下一目標跟蹤，完成連續(xù)分割。

7 實驗結(jié)果

本實驗采用的時頻流為每秒30 幀，圖像大小為720×576，目標模板為420×100。下面列舉了部分跟蹤分割圖像，如圖1 所示。

圖1（a）為初始幀，當(dāng)給定初始點后，不需要輸入任何參數(shù)，將自動連續(xù)的進行文字分割，如圖1（b）、（c）所示。

圖1（b）為匹配模板跟蹤分割的字符串1P759089，圖1（c）為更換目標模板為1P789088，圖1（d）為新匹配模板跟蹤分割的字符串1P759088。

在相同條件下，以不同方法對該視頻流進行字符分割，結(jié)果如表1 所示。

從表1 可以看出，在相同條件下mean shift 算法比其進行文字分割。他幾種方法速度快。

圖1 血袋編碼跟蹤分割圖像

表1 不同算法分割一條字符所需時間 ms

8 結(jié)論

利用mean shift 算法，使用直方圖描述目標的紋理及邊緣特征，能快速有效地對連續(xù)字符的時頻流進行文字分割，并且運用預(yù)測的方法減少了mean shift 算法中的迭代步驟，使搜索過程快速收斂，減少了運行時間。但直方圖信息的單一性，也使得分割區(qū)域的中心與實際中心有一定偏差，本文以放大分割區(qū)域來實現(xiàn)準確的分割。實驗結(jié)果證明，利用mean shift 算法能快速有效地對連續(xù)字符

［1］許劍峰.數(shù)字視頻中的文本分割的研究［D］.廣州：華南理工大學(xué)，2005.

［2］陳黎，黃心漢，王敏，等.基于聚類分析的車牌字符分割方法［J］.計算機工程與應(yīng)用，2002，38（6）：221-222，256.

［3］楊大鵬，高向東，劉紅.基于紋理特征的道路行人識別研究［J］.機械設(shè)計與制造，2012（1）：182-184.

［4］凌彤輝，黃山，王新增，等.車牌字符分割算法的研究［J］.中國測試技術(shù)，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］.光學(xué)技術(shù)，2007，33（2）：226-229.

［8］康一梅，謝晚冬，胡江，等.目標尺寸自適應(yīng)的Mean-Shift 跟蹤算法［J］.兵工學(xué)報，2011，32（2）：210-216.

［9］胡文廣.運動人體檢測及遮擋處理［D］.哈爾濱：哈爾濱工程大學(xué)，2009.

［10］烏恩.智能視頻監(jiān)控中運動目標檢測與跟蹤算法研究［D］.長沙：國防科學(xué)技術(shù)大學(xué)，2010.

［11］張昊，黃戰(zhàn)華，郁道銀，等.基于差分圖像的運動目標跟蹤與分割方法的應(yīng)用研究［J］.光學(xué)技術(shù)，2005，31（4）：565－567.