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

楊富元，周曉東

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

0 引言

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

1 Mean shift 基本原理

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

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

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

2 目標(biāo)模型的描述

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

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

3 候選模型的描述

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

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

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

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

進(jìn)行泰勒展開(kāi)，得

由于目標(biāo)連續(xù)運(yùn)動(dòng)的連續(xù)性，候選位置y0變化不大，可以省略高次項(xiàng)。

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

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

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

5 目標(biāo)定位

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

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

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

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

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

7 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

8 結(jié)論

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

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

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

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

［4］凌彤輝，黃山，王新增，等.車(chē)牌字符分割算法的研究［J］.中國(guó)測(cè)試技術(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 的灰度目標(biāo)跟蹤新算法［J］.光學(xué)技術(shù)，2007，33（2）：226-229.

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

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

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

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