楊文彬，楊 明，林守金

(1.中北大學(xué) 理學(xué)院， 太原 030051； 2.信息探測(cè)與處理山西省重點(diǎn)實(shí)驗(yàn)室， 太原 030051；3.中山邁雷特?cái)?shù)控技術(shù)有限公司， 廣東 中山 528437)

曲線識(shí)別是圖像識(shí)別和機(jī)器視覺(jué)的重要研究課題之一。當(dāng)前常用的方法主要有Hough變換及其各種改進(jìn)算法、基于目標(biāo)優(yōu)化的方法、基于邊界跟蹤的方法、基于模糊聚類的方法等[1-8]。這些方法各具特色，但也有不同的缺點(diǎn)。基于Hough變換的方法往往計(jì)算量較大。基于目標(biāo)優(yōu)化的方法往往因?yàn)閮?yōu)化方法自身的缺陷導(dǎo)致產(chǎn)生錯(cuò)誤的分類結(jié)果。邊界跟蹤方法易受噪聲影響。基于模糊聚類的方法往往需要事先給出類別數(shù)(曲線條數(shù))。

近些年，國(guó)內(nèi)外學(xué)者將概率混合模型用于曲線識(shí)別，取得了不錯(cuò)的效果。Fang等[9]利用數(shù)據(jù)點(diǎn)到待檢直線的距離信息構(gòu)造混合模型，采用EM算法進(jìn)行參數(shù)估計(jì)。Long等[10]利用圖像中直線段之間的轉(zhuǎn)換關(guān)系以及直線段之間的距離構(gòu)建混合模型，實(shí)現(xiàn)對(duì)應(yīng)直線的匹配，從而完成圖像的配準(zhǔn)。Arellano等[11]采用橢圓上任意兩點(diǎn)所在直線的方向和法向等信息建立混合模型，實(shí)現(xiàn)了對(duì)多個(gè)橢圓的識(shí)別。

本文依據(jù)圓周曲線的幾何特征建立相應(yīng)的混合模型，推導(dǎo)出參數(shù)估計(jì)方法，并分別用EM算法和貝葉斯陰陽(yáng)和諧學(xué)習(xí)算法實(shí)現(xiàn)圓周曲線混合模型的模型選擇和參數(shù)估計(jì)，以完成曲線識(shí)別。

1 圓周曲線檢測(cè)的概率模型

圖1 分布在圓周曲線及其附近的隨機(jī)點(diǎn)

從兩個(gè)方面分析點(diǎn)集S的分布特點(diǎn)：首先，在圓周方向上表現(xiàn)為均勻分布，這一特點(diǎn)可以由點(diǎn)x與圓心c的連線同x軸正向的夾角θ的均勻性刻畫，即假設(shè)θ～U(0,2π)(對(duì)于圓弧曲線，可假設(shè)θ～U(α,β))。其次，點(diǎn)x到圓心c的距離r圍繞圓周曲線的半徑R波動(dòng)，可以用正態(tài)分布刻畫，即假設(shè)r～N(R,σ2)。此外，假設(shè)θ和r相互獨(dú)立，這樣就可以用隨機(jī)向量(θ,r)來(lái)刻畫點(diǎn)集S中每一個(gè)點(diǎn)與圓心的關(guān)系。

隨機(jī)向量(θ,r)的聯(lián)合概率密度函數(shù)為

點(diǎn)x的坐標(biāo)(x,y)與(θ,r)之間的關(guān)系為

根據(jù)

(1)

(2)

對(duì)式(2)關(guān)于各參數(shù)求偏導(dǎo)并令其等于0，得到方程組：

(3)

求解方程組(3)即可得到各參數(shù)的極大似然估計(jì)。其中前2個(gè)方程可以直接解得R和σ的表達(dá)式，而第3個(gè)方程沒(méi)有解析解，需要用牛頓法等數(shù)值方法求解。以下給出參數(shù)估計(jì)的算法。

算法1 圓周曲線參數(shù)的估計(jì)方法

輸入：數(shù)據(jù)點(diǎn)xj(j=1,2,…,n)，最大迭代次數(shù)K，控制誤差ε；

輸出：迭代次數(shù)k，參數(shù)c、R、σ。

步驟1 在允許的范圍內(nèi)隨機(jī)初始化圓心c(0)，或者隨機(jī)選取3個(gè)數(shù)據(jù)點(diǎn)，以這3點(diǎn)確定一個(gè)圓，該圓的圓心為c(0)，令k←1。

步驟2 若k>K，停止迭代，輸出失敗信息，否則進(jìn)行下一步。

步驟4 計(jì)算

求解關(guān)于Δc的線性方程組HcΔc=F，令c(k)=c(k-1)+Δc。

步驟5 若max{||R(k)-R(k-1)||, ||σ(k)-σ(k-1)||, ||c(k)-c(k-1)||}<ε，則停止迭代，輸出參數(shù)，否則令k←k+1，轉(zhuǎn)步驟2。

2 EM算法檢測(cè)多條圓周曲線

(4)

則分布在多條圓周曲線附近的隨機(jī)點(diǎn)服從混合概率分布，其概率密度函數(shù)為

(5)

其中αi是位于第i條圓周曲線附近的數(shù)據(jù)點(diǎn)在整個(gè)點(diǎn)集中所占的比例，稱之為“混合比”系數(shù)。參數(shù)集為Θ={ci,Ri,σi,αi,i=1,2,…,k}。

(6)

在EM算法的第p+1次迭代的E(expectation)步中，計(jì)算lnLC(Θ)的條件概率EΘ(p)(lnLC(Θ)|X)，也就是計(jì)算計(jì)算zij的后驗(yàn)概率：

(7)

從而得到M(maximization)步的目標(biāo)函數(shù)：

(8)

(9)

(10)

算法2 多條圓周曲線檢測(cè)的EM算法

輸出：迭代次數(shù)p，混合比αi，圓周曲線參數(shù)ci,Ri,σi，i=1,2,…,k。

步驟7 若||Θ(p)-Θ(p-1)||<ε，則停止計(jì)算，輸出參數(shù)；否則轉(zhuǎn)下一步；

步驟8p←p+1，若p>P，則停止計(jì)算，輸出“經(jīng)P次迭代算法不收斂”的失敗信息；否則轉(zhuǎn)步驟2。

3 BYY算法檢測(cè)多條圓周曲線

考慮到多數(shù)情況下待檢曲線條數(shù)未知，將提出的圓周曲線概率模型與貝葉斯陰陽(yáng)和諧學(xué)習(xí)(BYY算法)相結(jié)合，以便在曲線條數(shù)未知的情況下完成識(shí)別。根據(jù)BYY算法的理論[12-13]，再結(jié)合動(dòng)態(tài)正則化學(xué)習(xí)[14-15]，構(gòu)造如下目標(biāo)函數(shù)：

Lλ(Θ)=J(Θ)+λON(p(y|x))

(11)

其中：λ是正則化尺度參數(shù)；J(Θ)為圓周曲線混合模型的和諧函數(shù)，

(12)

(13)

在式(11)中，如果能夠控制λ以一定的策略從0增加到1，最大化Lλ(Θ)的過(guò)程就從BYY和諧學(xué)習(xí)轉(zhuǎn)到極大似然學(xué)習(xí)的過(guò)程，整個(gè)正則化學(xué)習(xí)過(guò)程就能在早期的BYY學(xué)習(xí)階段實(shí)現(xiàn)自適應(yīng)的模型選擇，然后在最終階段收斂到極大似然估計(jì)。

顯然，在參數(shù)集Θ={ci,Ri,σi,αi,p(i|xj)}上極大化目標(biāo)函數(shù)Lλ(Θ)是很困難的。將參數(shù)分為兩組：Θ1={p(i|xj)}和Θ2={ci,Ri,σi,αi}，然后用交替迭代尋優(yōu)的方法求解該優(yōu)化問(wèn)題。先固定Θ2，用拉格朗日乘子法解得：

(14)

再固定Θ1，同樣用拉格朗日乘子法可以得到：

(15)

求解方程組(15)即可得到各參數(shù)估計(jì)值。下面給出完整的交替迭代的算法。

算法3 圓周曲線混合模型的BYY正則化算法

輸出：迭代次數(shù)q、最優(yōu)分支數(shù)k、參數(shù)集Θ。

步驟2 按照下面式子更新正則化尺度參數(shù)λ：

若|λ(M)-1|<ε1，則停止計(jì)算；否則記q←0，進(jìn)行下一步；

步驟4 按照式(14)計(jì)算p(q)(i|xj)；

步驟7 若Θ(q+1)-Θ(q)<ε2，Θ(0)←Θ(q+1)，M←M+1，進(jìn)行下一步；否則轉(zhuǎn)步驟9；

步驟9q←q+1，若q>Q，Θ(0)←Θ(q+1)，M←M+1，返回步驟2；否則返回步驟3。

4 實(shí)驗(yàn)

采用3個(gè)數(shù)值實(shí)驗(yàn)和1個(gè)真實(shí)圖像實(shí)驗(yàn)來(lái)檢驗(yàn)算法的性能，實(shí)驗(yàn)結(jié)果見(jiàn)圖2～ 5。圖2～ 4是3個(gè)數(shù)值實(shí)驗(yàn)的結(jié)果，其中：(a)為實(shí)驗(yàn)數(shù)據(jù)點(diǎn)；(b)為曲線檢測(cè)結(jié)果；(c)為數(shù)據(jù)點(diǎn)聚類結(jié)果。3個(gè)實(shí)驗(yàn)分別展示了圓之間的3種位置關(guān)系：相離，相交和相切。3個(gè)實(shí)驗(yàn)都取得了不錯(cuò)的檢測(cè)結(jié)果，其中實(shí)驗(yàn)1中3個(gè)同心圓的檢測(cè)結(jié)果最好；實(shí)驗(yàn)1和實(shí)驗(yàn)2的聚類結(jié)果較好，實(shí)驗(yàn)3在2個(gè)小圓與大圓相切處的數(shù)據(jù)點(diǎn)的聚類結(jié)果略有偏差。顯然，無(wú)論對(duì)于曲線檢測(cè)還是數(shù)據(jù)點(diǎn)聚類，相離是最簡(jiǎn)單的，而相切是最難的。圖5展示了真實(shí)圖像實(shí)驗(yàn)的結(jié)果，其中：(a)為原始圖像；(b)為經(jīng)過(guò)預(yù)處理后去掉背景的灰度圖像；(c)為曲線識(shí)別結(jié)果；(d)為數(shù)據(jù)點(diǎn)聚類結(jié)果。可以看到：對(duì)預(yù)處理之后的圖像，無(wú)論是曲線檢測(cè)還是數(shù)據(jù)點(diǎn)聚類，算法都取得了理想的結(jié)果。

圖2 實(shí)驗(yàn)1

圖3 實(shí)驗(yàn)2

圖4 實(shí)驗(yàn)3

圖5 實(shí)驗(yàn)4

5 結(jié)束語(yǔ)

本文根據(jù)圓周曲線的幾何特征，建立了圓周曲線的有限混合模型，解決了多條圓周曲線的檢測(cè)問(wèn)題以及數(shù)據(jù)點(diǎn)的聚類問(wèn)題。由于EM算法無(wú)法估計(jì)曲線條數(shù)，故結(jié)合貝葉斯陰陽(yáng)和諧學(xué)習(xí)算法，在曲線條數(shù)未知的情況下實(shí)現(xiàn)了圓周曲線識(shí)別。實(shí)驗(yàn)結(jié)果表明：在圓之間相離、相切和相交的情況下，算法都有令人滿意的效果，尤其是對(duì)于類間有交叉的數(shù)據(jù)集，一般的模糊聚類算法(如FCM算法、PCM算法)和密度聚類算法(如DBSCAN算法)都無(wú)法完成正確的聚類，而本文算法并不受這種情況的影響。另外，該算法完全適用于真實(shí)圖像中圓周曲線的檢測(cè)。需要注意的是，應(yīng)先對(duì)目標(biāo)圖像進(jìn)行圖像分割等預(yù)處理，提取出待檢測(cè)的部分，還需要對(duì)圖像進(jìn)行適當(dāng)?shù)目s放。

下一步將進(jìn)一步改進(jìn)算法，提高檢測(cè)和聚類的精度以及計(jì)算速度，并將該算法推廣到橢圓等更加復(fù)雜的圖形中。

[1] XU Z，SHIN B S，KLETTE R.Accurate and robust line segment extraction using minimum entropy with hough transform[J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society，2015，24(3):813-822.

[2] NG C S.Intelligent hough transform for object detection and tracking[J].Innovative Food Science & Emerging Technologies，2015，5(3):307-316.

[3] MUKHOPADHYAY P，CHAUDHURI B B.A survey of hough transform[J].Pattern Recognition，2015，48(3):993-1010.

[4] 陳小艷，王強(qiáng)，李柏林.改進(jìn)的Hough變換檢測(cè)圓方法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015，24(8):197-201.

[5] XU G，YANG Y Q，LIU B B，et al.An efficient hybrid multi-objective particle swarm optimization with a multi-objective dichotomy line search[J].Journal of Computational & Applied Mathematics，2015，280(C):310-326.

[6] LI Jin-long，MA Hong-feng，ZHANG W Z，et al.Research on edge detection of track fastener based on machine vision[J].Journal of Northwest Normal University，2017(7):96-101.

[7] SOMKANTHA K，THEERAUMPON N，AUEPHANWIRIYAKUL S.Boundary detection in medical images using edge following algorithm based on intensity gradient and texture gradient features.[J].IEEE transactions on bio-medical engineering，2011，58(3):567.

[8] 石磊，孫凱明，王剛,等.基于模糊聚類的標(biāo)識(shí)點(diǎn)圖形識(shí)別方法[J].自動(dòng)化技術(shù)與應(yīng)用，2015，34(12):90-92.

[9] FANG C，MA J.A Fixed-point EM algorithm for straight line detection[M].Berlin:Springer Berlin Heidelberg，2011:136-143.

[10] LONG T，JIAO W，HE G，et al.Automatic line segment registration using gaussian mixture model and expectation-maximization algorithm[J].IEEE Journal of Selected Topics in Applied Earth Observations & Remote Sensing，2014，7(5):1688-1699.

[11] ARELLANO C，DAHYOT R.Robust ellipse detection with Gaussian mixture models[J].Pattern Recognition，2016，58(C):12-26.

[12] XU L.Best harmony，unified RPCL and automated model selection for unsupervised and supervised learning on Gaussian mixtures，three-layer nets and ME-RBF-SVM models.[J].International Journal of Neural Systems，2001，11(1):43-69.

[13] MA J，WANG T，XU L.A gradient BYY harmony learning rule on Gaussian mixture with automated model selection[J].Neurocomputing，2004，56:481-487.

[14] JIA Y，YANG Z，SONG Q.Experimental study of random dynamic loads identification based on weighted regularization method[J].Journal of Sound & Vibration，2015，342:113-123.

[15] 呂琪.不適定問(wèn)題的迭代正則化方法研究[D].武漢：武漢理工大學(xué)，2012.