采用概率混合模型的圓周曲線識別方法

楊文彬，楊 明，林守金

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

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

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

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

1 圓周曲線檢測的概率模型

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

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

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

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

根據(jù)

(1)

(2)

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

(3)

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

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

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

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

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

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

步驟4 計算

求解關(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算法檢測多條圓周曲線

(4)

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

(5)

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

(6)

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

(7)

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

(8)

(9)

(10)

算法2 多條圓周曲線檢測的EM算法

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

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

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

3 BYY算法檢測多條圓周曲線

考慮到多數(shù)情況下待檢曲線條數(shù)未知，將提出的圓周曲線概率模型與貝葉斯陰陽和諧學(xué)習(xí)(BYY算法)相結(jié)合，以便在曲線條數(shù)未知的情況下完成識別。根據(jù)BYY算法的理論[12-13]，再結(jié)合動態(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λ(Θ)的過程就從BYY和諧學(xué)習(xí)轉(zhuǎn)到極大似然學(xué)習(xí)的過程，整個正則化學(xué)習(xí)過程就能在早期的BYY學(xué)習(xí)階段實現(xiàn)自適應(yīng)的模型選擇，然后在最終階段收斂到極大似然估計。

顯然，在參數(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)化問題。先固定Θ2，用拉格朗日乘子法解得：

(14)

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

(15)

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

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

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

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

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

步驟4 按照式(14)計算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 實驗

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

圖2 實驗1

圖3 實驗2

圖4 實驗3

圖5 實驗4

5 結(jié)束語

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

下一步將進(jìn)一步改進(jìn)算法，提高檢測和聚類的精度以及計算速度，并將該算法推廣到橢圓等更加復(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] 陳小艷，王強，李柏林.改進(jìn)的Hough變換檢測圓方法[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)識點圖形識別方法[J].自動化技術(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] 呂琪.不適定問題的迭代正則化方法研究[D].武漢：武漢理工大學(xué)，2012.