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

楊文彬，楊 明，林守金

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

曲線識別是圖像識別和機器視覺的重要研究課題之一。當前常用的方法主要有Hough變換及其各種改進算法、基于目標優化的方法、基于邊界跟蹤的方法、基于模糊聚類的方法等[1-8]。這些方法各具特色，但也有不同的缺點。基于Hough變換的方法往往計算量較大。基于目標優化的方法往往因為優化方法自身的缺陷導致產生錯誤的分類結果。邊界跟蹤方法易受噪聲影響。基于模糊聚類的方法往往需要事先給出類別數(曲線條數)。

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

本文依據圓周曲線的幾何特征建立相應的混合模型，推導出參數估計方法，并分別用EM算法和貝葉斯陰陽和諧學習算法實現圓周曲線混合模型的模型選擇和參數估計，以完成曲線識別。

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

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

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

隨機向量(θ,r)的聯合概率密度函數為

點x的坐標(x,y)與(θ,r)之間的關系為

根據

(1)

(2)

對式(2)關于各參數求偏導并令其等于0，得到方程組：

(3)

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

算法1 圓周曲線參數的估計方法

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

輸出：迭代次數k，參數c、R、σ。

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

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

步驟4 計算

求解關于Δ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)||}<ε，則停止迭代，輸出參數，否則令k←k+1，轉步驟2。

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

(4)

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

(5)

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

(6)

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

(7)

從而得到M(maximization)步的目標函數：

(8)

(9)

(10)

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

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

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

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

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

考慮到多數情況下待檢曲線條數未知，將提出的圓周曲線概率模型與貝葉斯陰陽和諧學習(BYY算法)相結合，以便在曲線條數未知的情況下完成識別。根據BYY算法的理論[12-13]，再結合動態正則化學習[14-15]，構造如下目標函數：

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

(11)

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

(12)

(13)

在式(11)中，如果能夠控制λ以一定的策略從0增加到1，最大化Lλ(Θ)的過程就從BYY和諧學習轉到極大似然學習的過程，整個正則化學習過程就能在早期的BYY學習階段實現自適應的模型選擇，然后在最終階段收斂到極大似然估計。

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

(14)

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

(15)

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

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

輸出：迭代次數q、最優分支數k、參數集Θ。

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

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

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

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

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

4 實驗

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

圖2 實驗1

圖3 實驗2

圖4 實驗3

圖5 實驗4

5 結束語

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

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

[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] 陳小艷，王強，李柏林.改進的Hough變換檢測圓方法[J].計算機系統應用，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] 石磊，孫凱明，王剛,等.基于模糊聚類的標識點圖形識別方法[J].自動化技術與應用，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].武漢：武漢理工大學，2012.