李園芳　項　安

(同濟大學(xué)電子與信息工程學(xué)院　上海 201804)

0　引　言

物料分選既是根據(jù)相應(yīng)的要求或固定的標(biāo)準(zhǔn)將待分選物料分類成不同的產(chǎn)品或者剔除物料中的不合格品和異物，來提高其使用價值來滿足消費和生產(chǎn)的需要[1]。在農(nóng)業(yè)、農(nóng)產(chǎn)品加工業(yè)、環(huán)境資源業(yè)、化工能源業(yè)等涉及天然性固體物料分級分類的各種領(lǐng)域中，物料分選得到了普遍應(yīng)用[1]。在分選過程中，根據(jù)產(chǎn)品的外觀特征參數(shù)(顏色特征和形狀特征)要求作為分選依據(jù)。通常待分選物料中的不合格品以及異物的顏色特征與合格品沒有明顯的區(qū)分界限，因此形狀分選在物料分選中起了重要的作用[2]。對于類似工業(yè)制品等完全按照嚴(yán)格的質(zhì)量標(biāo)準(zhǔn)進行生產(chǎn)的物料，模板匹配算法就能達(dá)到較好的精度要求。但對于受自然因素、社會因素、生長規(guī)律等制約，具有某種程度的天然屬性的物料(如農(nóng)產(chǎn)品)，無與之匹配的固定模板。在色選和X射線異物檢測等物料分選應(yīng)用背景下，僅根據(jù)面積和周長等形狀特征進行分選，往往漏檢率較高[3]。因此，研究能夠準(zhǔn)確分選物料形狀的特征是目前物料分選領(lǐng)域的熱點。

骨架作為一種重要的圖像目標(biāo)形狀特征，有效地反映出了物體形狀的拓?fù)浣Y(jié)構(gòu)或連通性，是圖像處理過程中許多特征提取的前提。骨架信息已經(jīng)被廣泛地應(yīng)用在各個圖像識別領(lǐng)域，在農(nóng)業(yè)上，黃成龍等[4]應(yīng)用玉米葉片骨架信息獲取了葉片角度、長度和彎曲度性狀，并且對葉片骨架基于位置的信息進行配準(zhǔn)得到了單片葉性狀的動態(tài)變化過程；刁智華等[5]提出了一種快速剔除偽分支的作物行骨架提取算法，基本滿足了農(nóng)業(yè)精準(zhǔn)施藥的要求；宗澤等[6]提出了基于骨架提取算法的作物表型參數(shù)提取方法，有效獲得了玉米植株的平滑骨架圖像；張?zhí)彀驳萚7]提出了一種基Dijkstra距離分段的骨架提取方法，對樹木主枝干進行了三維重建；羅艷等[8]提出了一種能夠有效去除多余分支并且不影響主骨架線長度，完整地提取對蝦主骨架線的算法。綜上可見，骨架算法已被廣泛運用于農(nóng)業(yè)中葉片性狀的測量、精準(zhǔn)施藥、樹木三維重建等領(lǐng)域，但在物料形狀分選中，骨架算法的應(yīng)用研究較少。

本文對物料的二值化圖像，利用骨架細(xì)化算法獲得物料的骨架信息，通過對骨架信息的約束進行分選。為了進一步提高分選精度，對骨架信息進行了擴展應(yīng)用，得到了物料的期望骨架長度，并且提出了新的基于骨架信息的圓形度和對稱性算法。對所選的物料進行上述各項特征參數(shù)的判斷，大大地提高了物料分選的精度。

1　骨架算法的原理及實現(xiàn)

1.1　骨架定義

骨架是可以反映物體形狀的一組曲線，且其與原始形狀拓?fù)浣Y(jié)構(gòu)分布和連通性具有一致性。骨架有兩種經(jīng)典定義：一種是草原之火模型，將一個圖像區(qū)域想象為由干草組成的平坦大草原，且假設(shè)沿草原邊界點火。火的前線以相同的速度向區(qū)域中心推進，中軸骨架就是同一時間多個火線到達(dá)點的集合[9]。

第二種經(jīng)典的定義，即是最大圓盤定義，骨架就是最大圓盤圓心點的全數(shù)集合，最大圓盤就是指完全包含在物體內(nèi)部，并且與物體的邊界有兩點或兩點以上相切點的圓，每一個骨架點都是物體邊界的一個最大內(nèi)切圓的圓心點[9]。

另外，骨架的定義還有很多種，如形態(tài)學(xué)骨架、脊點投影骨架等。不論何種定義，骨架算法的基本原理即從物體的內(nèi)部找到一組最大圓盤圓心點和相應(yīng)的半徑，利用這組數(shù)據(jù)來表示物體的形狀輪廓，也可以通過這組數(shù)據(jù)實現(xiàn)物體形狀輪廓的重建[10]。

骨架有許多性質(zhì)[11]，如中心性、拓?fù)湟恢滦?、?xì)性、等距變換不變性、可重建性、魯棒性、光滑性等。

1.2　基于邊緣點刪除的骨架算法

目前主要有3類離散域骨架算法：一是拓?fù)浼?xì)化的方法[12]，此方法可以保證得到骨架的連通性，但冗余的分支較多，對邊界噪聲非常敏感，且骨架點的位置并非準(zhǔn)確地靠近物體的中心。二是基于距離變換的方法[13-15]，骨架是圖像的距離梯度脊線，此類方法得到的骨架優(yōu)點是位置精確，但連通性難以保證。三是基于Voronoi圖的方法[16]。Voronoi圖是中軸的包集，需要對生成的骨架進行修剪[17]，具有很高的復(fù)雜度。

上述幾種骨架算法生成的骨架有各自不同的優(yōu)缺點，但都需要大量的計算才能實現(xiàn)。為了改善計算效率，本文采用基于邊緣點刪除的骨架算法，該算法是迭代刪除圖像的邊界點的細(xì)化算法，刪除這些點時要服從如下約束條件：1) 不能刪除端點；2) 不能破壞連接性；3) 不能導(dǎo)致區(qū)域的過度腐蝕[9]。

完整的骨架細(xì)化算法要經(jīng)過多次相同步驟的迭代，其中每次的迭代都是由如下步驟組成：1) 標(biāo)記將被刪除的邊界點；2) 刪除做了標(biāo)記的點；3) 在剩余的邊界點中標(biāo)記將被刪除的邊界點；4) 刪除標(biāo)記過的點。反復(fù)如上4個步驟，直到?jīng)]有點被刪除，此時算法終止，就得到了該圖形的骨架[9]。上述4個步驟中，步驟1和步驟3的具體內(nèi)容如下：

步驟1：首先假設(shè)區(qū)域點的值為1，背景點的值為0，參考圖1的8鄰域表示，定義邊界點是值為1且至少有一個相鄰像素的值為0的像素點。邊界點p1如果滿足如下條件，則將該邊界點p1標(biāo)為要刪除的點[9]：

a) 2≤N(p1)≤6

b)T(p1)=1

c)p2·p4·p6=0

d)p4·p6·p8=0

其中，N(p1)是p1的非零相鄰像素數(shù)量，即：

N(p1)=p2+p3+…+p8+p9

(1)

T(p1)是排序序列p2,p3,…,p8,p9,p2從0到1轉(zhuǎn)換的次數(shù)。若p1點的8鄰域中，p3,p5,p7,p8為1，其余為0，則N(p1)=4,T(p1)=3。

圖1　鄰域像素排列

步驟3：在判斷某點是否被標(biāo)記為被刪除的點時，條件a)和b)與步驟1中的條件a)和b)相同，但條件c)和d)變?yōu)椋?/p>

c′)p2·p4·p8=0,d′)p2·p6·p8=0。

2　骨架算法的應(yīng)用

2.1　圖像采集

本文以南瓜子為研究對象，采用X射線異物檢測機獲取南瓜子樣本圖像和常見異物樣本圖像，圖片輸出為16位灰度圖像，如圖2所示。用于圖像處理的計算機配置為Pentium(R) Dual-Core, 2.60 GHz, 3.25 GB內(nèi)存，并在Matlab R2012a軟件中進行研究和開發(fā)。

圖2　X光機中得到的圖像

2.2　圖像預(yù)處理

通過對原始X光圖像設(shè)定閾值，將物料和背景分開，得到二值化物料圖像。由于X射線初始圖像的背景中含有一些與物料顏色相近的像素塊，閾值分割后的二值化圖像存在噪聲。通過形態(tài)學(xué)的腐蝕處理去除背景噪聲，再通過膨脹處理得到邊緣較為平滑的預(yù)處理結(jié)果圖像。

2.3　期望骨架長度

采用本文所述基于邊緣點刪除的骨架算法對預(yù)處理結(jié)果圖像進行骨架的提取，如圖3所示。

圖3　初始骨架圖像

合格的南瓜子產(chǎn)品外觀形狀多近似橢圓，因此合格產(chǎn)品的骨架多數(shù)為一條曲線。但由于南瓜子產(chǎn)品的大小不一(由采集的大量樣本統(tǒng)計面積大小為250到800個像素點)，且由基于邊緣刪除的骨架算法的刪除條件可知，對于越接近圓的圖像提取的骨架越短(骨架端點距離初始邊緣越遠(yuǎn)，見圖4)，并不能直接根據(jù)該算法得到的初始骨架將合格南瓜子精確分選出來?；诖藨?yīng)用背景，本文對于基于邊緣點刪除的骨架算法得到的初始骨架進行改進與創(chuàng)新：

a) 簡化骨架：去除初始骨架上的冗余點。

b) 沿簡化后的骨架端點做切線交于原始邊界，得到圖像的期望骨架。

c) 計算期望骨架長度。

圖4　骨架對比

步驟二根據(jù)簡化骨架的端點及其8鄰域中的骨架點，以x=0,y=0的像素點為原點，得出切線的方程y=kx+b。此時切線與原始邊界有兩點相交，應(yīng)當(dāng)選擇與此骨架端點距離最近的交點，初始骨架加上骨架端點與最近交點的連線就是本文所求的期望骨架。本文所選物料的骨架有兩個端點，骨架端點與最近交點的連線也應(yīng)有兩條，如圖5所示。

圖5　期望骨架

步驟三計算期望骨架長度。計算排序后的相鄰骨架點之間的距離，并將其相加。

2.4　圓形度

由于物料的期望骨架長度范圍較大，僅根據(jù)長度進行形選精度仍不夠高。本文提出圓形度來對物料進行分選，傳統(tǒng)的圓形度計算等于4π乘以物料的面積與周長的平方之比[18]，亦或是通過計算物料的內(nèi)、外切圓半徑比值得到圓形度[2]。以上算法均需另求物料的周長參數(shù)或內(nèi)、外切圓半徑參數(shù)，本文則直接通過骨架長度來定義圓形度：

D=area/L

(2)

式中：area表示物料二值圖像的面積，L表示期望的骨架長度。圓形度越高，表示物料越接近圓形，反之，物料形狀越窄。

2.5　對稱性

為了進一步提高形選的精度，本文引入對稱性判斷。南瓜子物料形狀多近似為橢圓，幾何意義上，橢圓中任何穿過中心點的直線相交于邊緣的兩點時，兩個交點與橢圓中心點的距離相同。由于南瓜子圖像并非處處對稱并且為了提高算法的快速性，本文通過計算圖像中四條穿過中心點的直線的對稱性來判斷物料是否為橢圓。對稱性計算的重點是找到物料圖像(即橢圓)的長軸，其余三條直線均可通過旋轉(zhuǎn)長軸并且使旋轉(zhuǎn)直線與邊緣相交得到。傳統(tǒng)的長軸計算方法均使用了最小外接矩形法，無論其如何優(yōu)化，均需通過不斷旋轉(zhuǎn)圖像，反復(fù)嘗試才能得到圖像的長軸和短軸[19-21]。此種方法運算量大，算法耗時，不符合物料形選時的實時性要求。本文利用骨架來快速判斷圖像中四條穿過中心點的直線的對稱性。首先旋轉(zhuǎn)物料圖像使骨架處于水平0度方向并定義其為0度軸，逆時針方向旋轉(zhuǎn)依次為45度軸、90度軸、135度軸，通過判斷四條軸的邊緣點與質(zhì)心的距離之差，來判斷對稱性，具體步驟如下(其中各點標(biāo)記情況見圖6，假設(shè)圖中橢圓為南瓜子物料的邊緣)：

判斷0度軸是否對稱：

假設(shè)圖7的直線AB是本文算法求得的骨架，計算得到骨架AB與Y軸的夾角θ，順時針旋轉(zhuǎn)θ度，求得旋轉(zhuǎn)后圖像中Y軸坐標(biāo)與質(zhì)心O點Y軸坐標(biāo)y(o)相同的A點和B點的X軸坐標(biāo)x(A)、x(B)，OA和OB的長度L(OA)、L(OB)分別為|x(A)-x(O)|、|x(B)-x(O)|。

圖6　對稱性判斷

圖7　旋轉(zhuǎn)圖形

若L(OA)與L(OB)長度之差小于4(實際南瓜子圖形不一定為完全對稱橢圓)，則本文認(rèn)為O度軸對稱，反之則不對稱。45度軸、90度軸、135度軸判斷方法與上述相同。當(dāng)四個方向都軸對稱時，則認(rèn)為圖形為對稱。本文將物料的骨架信息直接運用到對稱性計算方法中，不需要另外計算物料的長軸，算法簡單快捷，滿足了實時性要求。

3　實驗結(jié)果分析

本文在X射線異物檢測機上采集有代表性的36個南瓜子樣本X射線圖像和74個常見有機物異物樣本X射線圖像，如圖8所示。樣本圖像中物料圖像的不合格率為100%，使用MATLAB2012a作為圖像處理工具。

圖8　樣本圖像

3.1　面積約束

先對樣本圖像進行二值化處理，提取圖像中的物料區(qū)域。再對二值化物料圖像進行形態(tài)學(xué)的腐蝕膨脹操作，得到預(yù)處理后的圖像。統(tǒng)計南瓜子樣本圖像面積特征值，閾值范圍為250～800。利用面積約束信息判斷有機物異物樣本，檢測樣本的不合格率為77%，與真實的不合格率100%有較大差距。

3.2　期望骨架約束

統(tǒng)計南瓜子樣本圖像期望骨架長度特征值，閾值范圍為15～50。在面積約束的基礎(chǔ)上，利用期望骨架長度約束信息判斷有機物異物樣本，檢測樣本的不合格率為84%，相比僅有面積約束條件時的檢測精度得到了提高。

3.3　圓形度約束

選取一種傳統(tǒng)的圓形度算法與本文所提基于骨架信息的圓形度進行對比，比較計算耗時以及其對檢測精度的影響，見表1。

表1　圓形度算法比較

傳統(tǒng)圓形度算法公式(物料周長用p表示)如下：

D=4π×area/p2

(3)

在實驗條件下，增加兩種圓形度約束，都提高了檢測精度。其中，增加傳統(tǒng)圓形度約束，檢測精度比增加本文圓形度約束情況下高4%。但本文算法比傳統(tǒng)算法耗時更少，出于在實際產(chǎn)品分揀過程中實時性的要求，本文選用了基于骨架信息的圓形度算法。

3.4　對稱性約束

將基于骨架信息的對稱性算法與基于最小外接矩形的對稱性算法進行對比，比較計算耗時以及其對檢測精度的影響，見表2。其中，基于最小外接矩形的對稱性算法具體步驟如下：

1) 計算物料圖像的質(zhì)心，以及物體的邊界。

2) 以質(zhì)心為原點，將物體的邊界以每次3°左右的增量在90°范圍內(nèi)旋轉(zhuǎn)。每旋轉(zhuǎn)一次都記錄其坐標(biāo)系方向上的外接矩形邊界點的最大和最小x、y值以及外接矩形的面積。取面積最小的外接矩形的參數(shù)為長軸和短軸。

3) 將長軸逆時針旋轉(zhuǎn)45度和135度求得物料圖像的45度軸和135度軸，短軸作為90度軸。

4) 將求得的四根軸線與物料的實際邊緣相交，判斷物料圖像是否在四根軸線上對稱。

表2　對稱性算法比較

在實驗條件下，增加兩種對稱性約束，都提高了檢測精度。但由于基于最小外接矩形的算法需要對圖像進行30次旋轉(zhuǎn)才能找到長軸，計算耗時較長?；诠羌苄畔⒌乃惴ū葌鹘y(tǒng)算法耗時更少，檢測精度較高，本文選用了基于骨架信息的對稱性算法。

3.5　實驗結(jié)果分析

增加了期望骨架長度、圓形度和對稱性等三個骨架衍生的特征約束后，檢測樣本的不合格率為95%。相比僅做面積特征判斷時，樣本檢測的精度有了很大的提高。并且基于骨架信息的圓形度特征算法和對稱性算法與傳統(tǒng)算法相比，不僅檢測精度能滿足要求并且實時性效果更好。

4　結(jié)　語

在物料的形狀分選中，本文利用基于邊緣點刪除的骨架細(xì)化算法，獲得物料的骨架信息。為了進一步提高分選精度，通過對骨架信息的擴展應(yīng)用，得到了物料的期望骨架長度，并且提出了新的基于骨架信息的圓形度和對稱性算法。在算法驗證實驗中，通過增加對物料的骨架信息以及衍生條件的約束判斷，分選精度從77%提高到了95%。

本文提出了一種在無固定模板的物料的形狀分選中，反映物料形狀的連通性或拓?fù)浣Y(jié)構(gòu)并且有效提高分選精度的分選算法。該算法簡單靈活，易于實現(xiàn)，能適用于多種類似的物料分選過程，滿足了實時生產(chǎn)檢測準(zhǔn)確性要求，具有廣泛的應(yīng)用前景，但運算速度仍需進一步提高。

[1] 許萬婷.物料分選的優(yōu)化策略研究[D].大連理工大學(xué),2013:1-2.

[2] 高達(dá)睿.基于顏色和形狀特征的茶葉分選研究[D].中國科學(xué)技術(shù)大學(xué),2016:1-3.

[3] 劉瓔瑛.基于機器視覺的稻米品質(zhì)評判方法研究[D].南京農(nóng)業(yè)大學(xué),2010:1-15.

[4] 黃成龍,張雪海,吳迪,等.基于時間序列的玉米葉片性狀動態(tài)提取方法研究[J].農(nóng)業(yè)機械學(xué)報,2017,48(5):174-178.

[5] 刁智華,吳貝貝,魏玉泉,等.一種快速剔除偽分枝的作物行骨架提取算法[J].農(nóng)機化研究,2016(9):17-22.

[6] 宗澤,張雪,郭彩玲,等.基于骨架提取算法的作物表型參數(shù)提取方法[J].農(nóng)業(yè)工程學(xué)報,2015(S2):180-185.

[7] 張?zhí)彀?云挺,薛聯(lián)鳳,等.基于骨架提取的樹木主枝干三維重建算法[J].南京師范大學(xué)學(xué)報(工程技術(shù)版),2014(4):51-57.

[8] 羅艷,張安紅,成芳.基于機器視覺技術(shù)的對蝦主骨架線提取[J].食品工業(yè)科技,2013,34(8):68-73.

[9] 阮秋琦.數(shù)字圖像處理學(xué)[M].電子工業(yè)出版社,2013:525-527.

[10] 張靜.骨架提取算法研究與應(yīng)用[D].遼寧師范大學(xué),2012:5-10.

[11] 黃文偉.基于拉普拉斯算子的點云骨架提取[D].大連理工大學(xué),2009:9-13.

[12] Ogniewicz R L,Kübler O.Hierarchic Voronoi skeletons[J].Pattern Recognition,1995,28(3):343-359.

[13] August J,Zucker S W,Siddiqi K.Ligature Instabilities in the Perceptual Organization of Shape[C]//Computer Vision and Pattern Recognition,1999.IEEE Computer Society Conference on.IEEE,1999:2042-2048.

[14] Malandain G,Fernández-Vidal S.Euclidean skeletons[J].Image & Vision Computing,1998,16(5):317-327.

[15] Xie W,Thompson R P,Perucchio R.A topology-preserving parallel 3D thinning algorithm for extracting the curve skeleton[J].Pattern Recognition,2003,36(7):1529-1544.

[16] 丁頤,劉文予,鄭宇化.基于距離變換的多尺度連通骨架算法[J].紅外與毫米波學(xué)報,2005,24(4):281-285.

[17] 江萍,徐曉冰,方敏.基于形態(tài)學(xué)骨架提取算法的研究及其實現(xiàn)[J].計算機應(yīng)用,2003,23(S1):136-137.

[18] 魏康麗,王振杰,孫柯,等.基于計算機視覺對蘋果脆片外觀品質(zhì)分級[J].南京農(nóng)業(yè)大學(xué)學(xué)報,2017,40(3):547-555.

[19] 向元平,何燕平,危郁林,等.一種快速提取植物葉片最小外接矩形算法[J].計算機與現(xiàn)代化,2016(2):58-61.

[20] 張法全,王國富,曾慶寧,等.利用重心原理的圖像目標(biāo)最小外接矩形快速算法[J].紅外與激光工程,2013,42(5):1382-1387.

[21] 盧蓉,范勇,陳念年,等.一種提取目標(biāo)圖像最小外接矩形的快速算法[J].計算機工程,2010,36(21):178-180.