基于小生境人工蜂群算法的字符邊緣圖像提取

張 爽, 王 華, 高金剛

(長春工程學(xué)院 機電工程學(xué)院, 長春 130012)

實際應(yīng)用中的許多物體都存在數(shù)字或字符標記在物體或?qū)ο笊嫌脕順擞浶畔⒌那樾? 如身份證號、 車牌號及銀行卡號等. 近年來, 二維碼及各種電子標簽的方式應(yīng)用廣泛, 但均為一種易于計算機軟件識別的方式獲取實體世界中的信息[1]. 而賦予機器設(shè)備能像人眼一樣讀懂字符和數(shù)字, 而不是以二維碼或條形碼方式獲取信息, 是人工智能發(fā)展的一個重要方向[2-3].

目前, 字符識別系統(tǒng)應(yīng)用廣泛, 如車牌字符自動識別[4]等. 實踐表明, 目前已有的這些算法具有良好的識別效果[5], 但其應(yīng)用范圍受環(huán)境影響, 如車輛行駛速度、 字符大小及格式、 光照條件等[6]. 隨著科學(xué)技術(shù)的發(fā)展, 各行業(yè)的管理發(fā)展趨勢都是逐步從人工管理轉(zhuǎn)變?yōu)樽詣踊芾韀7]. 對于機械制造業(yè)中生產(chǎn)的零部件, 通常都要求在零部件上標記字符, 以表示零件名、 零件編號、 生產(chǎn)日期和批次號等. 列車轉(zhuǎn)向架輪對端面刻有數(shù)字和英文字母的字符, 以表述生產(chǎn)日期和時間、 零件編號、 操作員編號等重要生產(chǎn)過程追溯信息. 生產(chǎn)過程追溯信息是產(chǎn)品質(zhì)量控制分析和內(nèi)外部物流跟蹤、 轉(zhuǎn)向架生產(chǎn)組織管理及售后質(zhì)量問題分析的重要參考信息. 列車轉(zhuǎn)向架輪對軸端刻印的字符如圖1所示. 本文以列車轉(zhuǎn)向架的關(guān)鍵部件輪對軸端刻印字符為研究對象, 提出一種在生產(chǎn)車間復(fù)雜的背景下, 適應(yīng)實際環(huán)境的字符識別方法, 自動識別這些零部件上的字符, 用以指導(dǎo)生產(chǎn)、 車間物流及生產(chǎn)信息記錄等.

圖1 列車轉(zhuǎn)向架輪對軸端字符Fig.1 Characters on train wheel set bogie

1 人工蜂群算法

人工蜂群算法[8]源于蜜蜂尋找蜜源及采蜜的行為方式, 包括蜂群的分工、 信息傳遞等群體行為, 完成對尋優(yōu)問題的求解[9]. 相比于蟻群算法、 遺傳算法和粒子群算法等其他群智能優(yōu)化算法, 其具有更顯著的尋優(yōu)能力, 廣泛應(yīng)用于各領(lǐng)域[10].

算法基本流程如下： 蜜源為整個搜索域內(nèi)相對有價值的解, 選取合理的函數(shù)使蜜源的價值與求解問題的函數(shù)建立聯(lián)系, 即收益度函數(shù)值能衡量蜜源價值. 初始時, 蜂群分為采蜜蜂和跟隨蜂兩類. 設(shè)蜜蜂總數(shù)為Ns, 跟隨蜂數(shù)量為Nu, 采蜜蜂數(shù)量為Ne, 對于蜂群分組通常將采蜜蜂的數(shù)量設(shè)為蜂群總數(shù)的一半, 另一半蜂群被設(shè)為跟隨蜂. 對于每個蜜蜂, 其搜索區(qū)域即為待優(yōu)化問題解的變量空間, 變量空間的維數(shù)設(shè)為D. 蜂群設(shè)為x={x1,x2,…,xNe},xi為任意一只采蜜蜂, 則

(1)

(2)

其中第xi個收益度函數(shù)值用f(xi)表示. 每次迭代后, 采蜜蜂招募跟隨蜂對已搜索到位置的鄰域進行搜索, 然后比較搜索到的新位置vi與原位置xi的收益度函數(shù)值大小, 并選擇其中收益度大的位置作為該蜜蜂下一次鄰域搜索的位置. 鄰域搜索位置公式為

vi,j=xi,j+fi,j(xi,j-xk,j),

(3)

其中:j∈{1,2,…,D},k∈{1,2,…,Ne},k,j為搜索范圍內(nèi)隨機自然數(shù)， 且k≠j;fi,j為[-1,1]內(nèi)的隨機系數(shù), 其作用是保持鄰域搜索時的隨機性. 將蜂群按收益度大小排序, 跟隨蜂優(yōu)先選擇收益度高的采蜜蜂, 跟隨其在鄰域內(nèi)搜索. 若在鄰域新位置找到的蜜源收益度更高, 則令新位置替代采蜜蜂的原位置.

若采蜜蜂的鄰域搜索次數(shù)超過設(shè)定的規(guī)則, 但仍未找到收益度更高的蜜源, 則其身份轉(zhuǎn)變?yōu)閭刹榉? 并繼續(xù)在全局內(nèi)隨機產(chǎn)生新位置作為下一輪迭代的搜索位置. 當(dāng)滿足預(yù)先設(shè)定的停止條件時, 如總迭代次數(shù)或未滿足收益值提高的閾值等, 則算法停止并輸出結(jié)果; 若未滿足算法停止條件, 則蜂群將進行下一輪迭代過程. 人工蜂群算法流程如圖2所示.

圖2 人工蜂群算法流程Fig.2 Flowchart of artificial bee colony algorithm

人工蜂群算法通過模擬蜂群信息溝通, 控制蜂群在相對收益大的位置進行鄰域搜索, 放棄適應(yīng)度值低的位置, 并對在全局內(nèi)隨機產(chǎn)生的新位置進行搜索, 即可實現(xiàn)在每次迭代中逐步優(yōu)化搜索值的目的, 并最終搜索到問題的最優(yōu)解. 對采蜜蜂、 跟隨蜂和偵查蜂進行不同分工及將其身份互相轉(zhuǎn)化, 實現(xiàn)算法在全局搜索的優(yōu)異性能及鄰域求解的更高精度.

2 小生境技術(shù)及小生境人工蜂群算法

小生境是指在生物學(xué)的特定環(huán)境中由一種生物群體組成的群體組織. 在自然界中, 常見一些習(xí)性或特征等相似的物種聚集并生活在一起組成群體, 并逐漸形成一種物種及其特定的生存空間. 小生境技術(shù)通常被應(yīng)用于處理多模函數(shù)優(yōu)化問題中. 多模優(yōu)化問題是搜索問題的全局最優(yōu)解及局部最優(yōu)解[11]. 小生境技術(shù)能控制群體優(yōu)化方向, 并形成多個物種, 即使算法最終收斂到多個不同的解空間, 從而避免了算法過早收斂于局部最優(yōu)空間, 可增強算法的局部搜索性能.

人工蜂群算法可用于尋找全局最優(yōu)解， 具有收斂速度快、 求解精度高、 參數(shù)設(shè)置少等特點. 為優(yōu)化人工蜂群算法局部最優(yōu)解的搜索能力, 在算法中引進小生境技術(shù), 在各局部搜索空間形成所需物種, 從而在兼顧全局最優(yōu)解能力的基礎(chǔ)上, 增強算法局部搜索能力. 小生境識別、 跟隨蜂選擇策略是將小生境技術(shù)應(yīng)用到人工蜂群算法中的關(guān)鍵. 本文選擇限制競爭策略作為小生境保持策略, 即設(shè)定每個子種群各自的獨立搜索空間, 從而限制子種群之間在搜索域內(nèi)的競爭, 避免了算法在局部搜索域內(nèi)過早收斂于某個特定的位置.

在人工蜂群算法中, 蜜源效益度高的采蜜蜂群體具有引導(dǎo)跟隨蜂的職能, 控制這些采蜜蜂的搜索方向, 可實現(xiàn)在迭代運算過程中引導(dǎo)整個蜂群的搜索范圍. 采用設(shè)定小生境半徑的方法限定每個子種群的搜索范圍, 對于進入其他小生境搜索范圍的采蜜蜂, 賦予其新的位置, 通過限制與引導(dǎo)的策略控制多次迭代中算法能按預(yù)定的方式搜索.

小生境人工蜂群算法步驟如下：

1) 設(shè)置基本參數(shù), 包括限制次數(shù)limit、 最大迭代次數(shù)maxCycle、 子種群的數(shù)目N、 子種群規(guī)模Bee total、 小生境半徑R-niche等;

2) 在規(guī)定的搜索范圍內(nèi), 隨機產(chǎn)生子種群的搜索位置, 結(jié)束搜索后計算每個子種群內(nèi)蜜蜂的適應(yīng)度函數(shù)值, 將數(shù)值按大小排序, 并存儲相對優(yōu)異的位置及函數(shù)值;

3) 子種群內(nèi)的采蜜蜂按設(shè)定的方法搜索新蜜源, 并與上次迭代中存儲的蜜源收益比較, 當(dāng)新蜜源效益度值高于存儲的蜜源效益度時, 令新蜜源替換之前的蜜源, 即存儲本次新搜索到的蜜源效益度值及位置；

4) 根據(jù)蜜源效益度值的大小排序, 效益度高的采蜜蜂獲得大概率招募跟隨蜂, 并引領(lǐng)跟隨蜂在上次迭代位置的鄰域附近搜索新的潛在蜜源位置;

5) 若在鄰域內(nèi)搜索效益度更高的蜜源次數(shù)達到設(shè)定閾值, 但仍未找到更優(yōu)的蜜源位置, 則將這只采蜜蜂身份轉(zhuǎn)化為偵查蜂, 并在下次迭代中執(zhí)行隨機全局搜索;

6) 計算每個子種群內(nèi)每個蜜蜂的效益度值, 排序并保存更新后的各子種群內(nèi)最優(yōu)解的效益度值及位置;

7) 判斷蜜蜂是否進入其他子種群搜索范圍內(nèi), 如果存在則重新設(shè)定該蜜蜂的搜索位置;

8) 檢查算法是否已達到設(shè)定的迭代次數(shù)上限值, 如果達到則算法結(jié)束, 輸出結(jié)果； 如果次數(shù)未達到, 則算法返回步驟3).

3 字符邊緣提取

考慮字符圖像的邊緣特性, 并合理設(shè)置小生境人工蜂群算法參數(shù), 包括子種群數(shù)量、 算法結(jié)束條件、 小生境半徑、 群體規(guī)模、 解的保存方式和效益度函數(shù). 算法結(jié)束條件的設(shè)置常用限定循環(huán)次數(shù)或效益度函數(shù)值大于設(shè)定的閾值. 小生境半徑合理的設(shè)定可合理分配蜂群的搜索能力, 以獲得包含多個局部最優(yōu)解的結(jié)果. 在蜂群上次搜索的最優(yōu)解對應(yīng)的八鄰域內(nèi)繼續(xù)搜索與效益度函數(shù)值最接近中心的點, 將搜索到的新位置替代原位置, 并作為下一次搜索的中心位置. 算法循環(huán)執(zhí)行直至算法滿足結(jié)束條件并停止. 提取出每次循環(huán)搜索到的位置, 即得到了對應(yīng)圖像的邊緣圖像.

蜂群的數(shù)量是決定算法搜索能力的重要參數(shù). 若蜂群數(shù)量設(shè)定過多, 則會導(dǎo)致運算能力的浪費, 且結(jié)果中會包含劣勢解. 若蜂群數(shù)量設(shè)定過少, 則會導(dǎo)致搜索能力不足[12]. 合理的蜂群數(shù)量應(yīng)該是根據(jù)圖像邊緣信息及圖像的尺寸確定. 本文采用將圖像中所有像素點之和的平方根作為蜂群數(shù)量, 計算公式為

(4)

其中:N表示圖像的像素行數(shù);M表示圖像的像素列數(shù);Ns表示蜂群的總數(shù)量. 跟隨蜂Ne的數(shù)量為

Ne=Ns/2.

(5)

子種群數(shù)量N由圖像內(nèi)容及布局設(shè)定, 對于字符圖像, 可設(shè)定為字符的數(shù)量, 即每個子種群對應(yīng)一個字符, 即可保證子種群的搜索能力覆蓋到每個字符. 對于本文中待識別的字符, 每個字符像素點相對接近, 對于子種群規(guī)模Bee total設(shè)定時, 將蜂群總體平均分配到每個子種群中以簡化算法. 為避免種群搜索空間交叉的現(xiàn)象, 小生境半徑可設(shè)為字符中心之間的距離.

選擇與圖像邊緣點強相關(guān)的函數(shù)作為小生境人工蜂群算法的效益度函數(shù)表達式[13-14]. 本文算法的效益度函數(shù)采用像素點八鄰域的灰度突變值函數(shù), 效益度函數(shù)為

f(Ii,j)=|Ii-1,j-1-Ii+1,j+1|+|Ii-1,j-Ii+1,j|+|Ii-1,j+1-Ii+1,j-1|+|Ii,j-1-Ii,j+1|,

(6)

其中: (i,j)表示圖像中任意一個像素點的位置；Ii,j表示位置(i,j)的灰度值.f(Ii,j)的八鄰域如圖3所示.

圖3 八鄰域示意圖Fig.3 Schematic diagram of 8 neighbor area

圖4 圖像邊緣及灰度值Fig.4 Edge image and gray value

若某像素點八鄰域灰度梯度值大于或等于設(shè)定的判定閾值, 則設(shè)定該像素點為邊緣點, 并將該點的灰度值標記為1, 如圖4所示. 圖像灰度梯度值的閾值為

T=fix(std2(image))×1.5.

(7)

4 實驗結(jié)果分析

以如圖5所示的實際生產(chǎn)線上零部件采集到的單個字符為例說明本文算法的有效性. 圖5中圖像大小為193×103, 則蜂群數(shù)量

圖5 初始圖像Fig.5 Initial image

待搜索的字母為4個, 子種群規(guī)模

Beetotal=140÷4=35;

閾值

T=fix(std2(image))×1.5=93;

總迭代次數(shù)iter為10次, 鄰域搜索次數(shù)設(shè)定為5次. 由圖5可見, 圖像寬度為193個像素, 其中每個字母在整個圖像中寬度的分布列于表1. 在小生境算法中, 設(shè)定規(guī)則保證每個子種群的搜索范圍固定在對應(yīng)字母的整體圖像寬度分布內(nèi), 從而保證每個字母得到均衡的搜索能力.

表1 字母寬度分布Table 1 Distribution of alphabet width

圖6為未應(yīng)用小生境半徑算法得到的字符邊緣圖像, 圖7為應(yīng)用小生境算法得到的字符邊緣圖像. 對比圖6與圖7可見, 圖6的邊緣點明顯分布不均, 以致于第一個字母V下部明顯缺失.

圖6 未應(yīng)用小生境算法的邊緣圖像Fig.6 Edge image without niche algorithm

圖7 應(yīng)用小生境算法的邊緣圖像Fig.7 Edge image obtained by niche algorithm

分別統(tǒng)計圖6和圖7中每個字母的邊緣點數(shù)量, 結(jié)果列于表2. 由表2可見, 應(yīng)用小生境算法得到的對應(yīng)每個字母的邊緣點數(shù)量一致, 均為249個, 而未應(yīng)用小生境算法得到的圖像邊緣點在4個字母上分布不均勻, 字母B上的數(shù)量為393個, 是字母T邊緣點150個的2.62倍, 而應(yīng)用了小生境算法得到的字母T的邊緣點數(shù)量為249個, 是未應(yīng)用小生境算法得到字母T邊緣點的1.66倍. 實例測試結(jié)果表明, 應(yīng)用小生境技術(shù)的人工蜂群算法采集到的邊緣圖像邊緣點分布均勻, 更利于下一步的字符識別.

表2 邊緣點數(shù)量對比Table 2 Quantity comparison of edge points

綜上所述, 本文將小生境人工蜂群優(yōu)化算法與圖像邊緣檢測原理相結(jié)合, 提出了一種針對字符圖像的邊緣檢測新方法. 利用小生境技術(shù)合理布置搜索能力, 通過控制子種群規(guī)模和搜索位置, 提高了局部搜索精度, 加強了算法的總體搜索能力. 對圖像進行小生境人工蜂群算法的字符邊緣檢測, 可按需求控制搜索的位置和能力, 極大地方便了后續(xù)處理過程. 實驗結(jié)果表明, 該方法不僅能快速地識別出字符, 且對較模糊或亮度不均勻的圖像也能準確識別, 適用于生產(chǎn)車間的復(fù)雜環(huán)境, 可滿足圖像檢測的實時性需求.