簡宏偉,陳 震

摘 要:在基于直線光流場(chǎng)的三維重建研究中首先要對(duì)連續(xù)多幀單目圖像序列進(jìn)行處理,主要是二維圖像直線的提取、跟蹤及匹配。在此利用改進(jìn)的Hough變換對(duì)圖像進(jìn)行直線提取,利用Hough變換的點(diǎn)線對(duì)偶性,即可將對(duì)圖像序列中的特征直線的跟蹤與匹配問題轉(zhuǎn)化為在參數(shù)空間(ρ,θ)中對(duì)特征點(diǎn)運(yùn)動(dòng)軌跡的參數(shù)估計(jì),可以采用卡爾曼濾波器對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行初步跟蹤,預(yù)測(cè)其大致位置,再通過建立模板與圖像的匹配相關(guān)系數(shù)判定搜索到的特征點(diǎn)的精確坐標(biāo)。實(shí)驗(yàn)結(jié)果表明,該方法取得了較好的實(shí)驗(yàn)結(jié)果。

關(guān)鍵詞:邊界算子;Hough變換;卡爾曼濾波器;模板

中圖分類號(hào):TN919文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)20-066-03

Extraction and Tracking Match of 2-D Image Array Straight Line

JIAN Hongwei,CHEN Zhen

(College of Automation,Nanchang Hangkong University,Nanchang,330063,China)

Abstract:During the study of reconstructing 3D based on straight line optical flow,a sequence of monocular images should be processed first.Using improved Hough transform to extract lines,and a tracking characteristic lines method which is based on Hough transform is presented.Rather than tracking lines in image space directly,the method makes use of duality theory in Hough transform in order to transform line-tracking in image space into point-tracking in Hough space.The first step designing is adopting Kalman filter to preliminary track the motion target,then accurate characteristic point location is searched by using build-up modeling board and image matching correlation modulus.Experiment result using composed image array shows that the presented method provides a good estimation of the characteristic lines tracking.

Keywords:boundary operator;Hough transform;Kalman filter;modeling board

點(diǎn)和線是計(jì)算機(jī)視覺中最常用到的視覺特征,通常圖像特征抽象的層次越高,越有利于圖像的處理與分析,為了更好地進(jìn)行三維重建,非常有必要提高圖像特征的抽象層次,即將點(diǎn)級(jí)別提高到線級(jí)別。在計(jì)算機(jī)視覺和圖像處理領(lǐng)域,直線特征相比于點(diǎn)特征提供了更多場(chǎng)景結(jié)構(gòu)信息[1],并能夠很穩(wěn)健地檢測(cè)和跟蹤感興趣的直線特征。

1 Hough變換提取直線的改進(jìn)方法

1972年Duda和Hart提出利用Hough變換提取直線,Hough變換法提取直線是一種變換域提取直線的方法[2],利用線-點(diǎn)的對(duì)偶性,把直線上點(diǎn)的坐標(biāo)變換到通過該點(diǎn)的直線的系數(shù)域[3],利用了共線和直線相交的關(guān)系[4],使直線的提取問題轉(zhuǎn)化為計(jì)數(shù)問題[5]。Hough變換在直線提取方法中擁有眾多優(yōu)點(diǎn)的同時(shí)也存在著一些缺點(diǎn),如需要較大的存儲(chǔ)空間和較長的計(jì)算時(shí)間[6,7]。針對(duì)這一缺點(diǎn),這里采取一種Hough變換提取直線的改進(jìn)方法。

由幾何原理可知,平面上任意兩點(diǎn)可以確定一條直線的參數(shù)(ρ,θ),則可令直線上的兩點(diǎn)坐標(biāo)為(x1,y1)和(x2,y2),那么:

ρ=x2cos θ+y2sin θ

θ=-tan-1[(x2-x1)/(y2-y1)](1)

對(duì)于每一個(gè)非零點(diǎn),在其較小的鄰域中,計(jì)算其他非零點(diǎn)與該點(diǎn)所確定的直線參數(shù)并在相應(yīng)參數(shù)區(qū)間投票表決,統(tǒng)計(jì)出投票數(shù)最多的參數(shù)區(qū)間,以該參數(shù)作為直線參數(shù)[8],然后根據(jù)此參數(shù)在全圖范圍內(nèi)搜索直線上的其他點(diǎn),提高算法的魯棒性。

改進(jìn)算法的具體實(shí)現(xiàn)步驟如下:

(1) 在圖像中順序搜索,直到檢測(cè)到圖像中的一個(gè)非零點(diǎn)P,將該點(diǎn)作為一個(gè)參考點(diǎn);

(2) 選取以P點(diǎn)為起始點(diǎn)的一個(gè)M×M區(qū)域Ap。在Ap中搜索其他的非零點(diǎn),并根據(jù)式(1)計(jì)算每個(gè)非零點(diǎn)pi與P點(diǎn)所屬直線的參數(shù)對(duì)(ρi,θi);

(3) 令ρ的偏差范圍為Δρ,θ的偏差范圍為Δθ。在Ap內(nèi)進(jìn)行投票表決,統(tǒng)計(jì)落入每個(gè)(ρ+Δρ,θ+Δθ)參數(shù)區(qū)間的參數(shù)對(duì)的個(gè)數(shù)ni;

(4) 找出Ap中最多的得票數(shù)的參數(shù)區(qū)間nmax,并對(duì)所有落入該區(qū)間的(ρi,θi)取均值,以減少量化誤差的影響,得到(,),以此作為在Ap內(nèi)通過P點(diǎn)的直線的參數(shù);

(5) 令T1為Ap內(nèi)直線長度閾值,若nmax>T1,則轉(zhuǎn)到步驟(6),搜索屬于該直線的其他點(diǎn);否則認(rèn)為過P點(diǎn)的直線不存在,將P點(diǎn)灰度清為零,轉(zhuǎn)到步驟(1),重新開始搜索;

(6) 將搜索范圍擴(kuò)展至全圖,對(duì)檢測(cè)到的每個(gè)非零點(diǎn),令=,若-<Δρ,則認(rèn)為屬于該直線,將其投票數(shù)進(jìn)行累加,并將該點(diǎn)的灰度置為0;

(7) 全圖搜索完畢,若直線的投票數(shù)大于設(shè)定閾值T2,則認(rèn)為直線存在,否則認(rèn)為直線不存在;

(8) 將P點(diǎn)灰度清零,返回步驟(1),重新搜索,直到圖像中不再有非零點(diǎn)時(shí)結(jié)束。

2 二維圖像序列直線的跟蹤及匹配

由Hough變換提取直線的過程可以看到,圖像平面中的直線和Hough空間中對(duì)應(yīng)的點(diǎn)具備點(diǎn)線對(duì)偶性。這樣就可以利用Hough變換的點(diǎn)線對(duì)偶性原理,將對(duì)圖像平面中特征直線的跟蹤問題轉(zhuǎn)化為對(duì)Hough空間中特征點(diǎn)的跟蹤問題[9]。

1960年,Kalman提出了離散系統(tǒng)Kalman濾波[10],后來他把這一濾波方法推廣到連續(xù)時(shí)間系統(tǒng)中去?？柭鼮V波器是常用預(yù)測(cè)、跟蹤工具。卡爾曼濾波算法為最優(yōu)化的自回歸數(shù)據(jù)處理,它可以根據(jù)過去時(shí)刻積累的信息,預(yù)測(cè)當(dāng)前時(shí)刻目標(biāo)的粗略位置,為精確定位目標(biāo)提供依據(jù)。

在此針對(duì)Hough空間特征點(diǎn)的跟蹤估計(jì),可設(shè)一個(gè)特征點(diǎn)的運(yùn)動(dòng)軌跡由三次多項(xiàng)式來描述,定義狀態(tài)向量為下列一個(gè)六維向量X=[p,,],其中點(diǎn)P在Hough空間位置坐標(biāo)為P=(ρ,θ)T,狀態(tài)方程為:

X(k|k-1)=FX(k-1|k-1)+W(k|k-1)

式中:X(k|k-1)是利用上一狀態(tài)預(yù)測(cè)的結(jié)果:

F=I2I2T12I2T

02I2I2T

0202I2

式中:I2為2×2單位矩陣;02為2×2零矩陣;T為相鄰兩幀的時(shí)間間隔;X(k-1|k-1)是上一狀態(tài)最優(yōu)的結(jié)果,因?yàn)闆]有狀態(tài)的控制量,所以U(k|k-1)為0。

而在Hough空間中僅能觀測(cè)到特征點(diǎn)的坐標(biāo)位置,所以,觀測(cè)方程可以表達(dá)為:

Z(k)=HX(k)+V(k)

式中,H=[I2,02,02]是一個(gè)2×6維的矩陣。

因?yàn)闋顟B(tài)方程和觀測(cè)方程都是線性的,可以直接應(yīng)用標(biāo)準(zhǔn)的Kalman濾波器來實(shí)現(xiàn)對(duì)Hough空間特征點(diǎn)的跟蹤。

Kalman濾波器跟蹤Hough空間特征點(diǎn)的實(shí)現(xiàn)步驟:

(1) 利用系統(tǒng)的狀態(tài)模型預(yù)測(cè)下一狀態(tài)的系統(tǒng)。在Hough空間中預(yù)測(cè)運(yùn)動(dòng)目標(biāo)特征點(diǎn)的狀態(tài)向量。

X(k|k-1)=FX(k-1|k-1)(2)

(2) 特征點(diǎn)狀態(tài)向量協(xié)方差矩陣P(k)的預(yù)測(cè)和Kalman增益矩陣Kg(k)的計(jì)算。

P(k|k-1)=FP(k-1|k-1)FT+Q(3)

Kg(k)=P(k|k-1)HT/[HP(k|k-1)HT+R](4)

式(3)中:P(k|k-1)是X(k|k-1)對(duì)應(yīng)的協(xié)方差,P(k-1|k-1)是X(k-1|k-1)對(duì)應(yīng)的協(xié)方差;式(2),式(3)是對(duì)系統(tǒng)的預(yù)測(cè)。

(3) 由Hough空間特征點(diǎn)的觀測(cè)值(ρ,θ)和預(yù)測(cè)值來更新運(yùn)動(dòng)目標(biāo)特征點(diǎn)的狀態(tài)向量方程,從而可以得到現(xiàn)在狀態(tài)的最優(yōu)化估算值X(k|k)。

X(k|k)=X(k|k-1)+Kg(k)[Z(k)-

HX(k|k-1)]

(4) 由上面三個(gè)步驟已經(jīng)得到最優(yōu)的估算值X(k|k),但是為了要令Kalman濾波器不斷地運(yùn)行下去,直到系統(tǒng)過程結(jié)束,就要更新X(k|k)的協(xié)方差P(k|k)。

P(k|k)=[I-Kg(k)H]P(k|k-1)

式中:I為單位矩陣。當(dāng)系統(tǒng)進(jìn)入(k+1)狀態(tài)時(shí),P(k|k)就是式(3)中的P(k-1|k-1)。

依據(jù)上述四個(gè)步驟,當(dāng)測(cè)量誤差協(xié)方差陣和狀態(tài)噪聲協(xié)方差陣不夠準(zhǔn)確時(shí),濾波結(jié)果存在較大誤差,甚至有時(shí)濾波器會(huì)發(fā)散或振蕩,所以由Kalman濾波器跟蹤預(yù)測(cè)到運(yùn)動(dòng)特征點(diǎn)的位置為粗略位置,為了得到點(diǎn)的精確坐標(biāo),可以以該點(diǎn)位置為中心,采取匹配相關(guān)算法搜索跟蹤結(jié)果。

匹配相關(guān)算法是以設(shè)某一匹配模板為模板圖像中以特征點(diǎn)為中心的一個(gè)M×N的小區(qū)域M(i,j),定義模板與當(dāng)前圖像幀在點(diǎn)(m,n)處的歸一化相關(guān)系數(shù)為:

R(m,n)=C(m,n)C1(m,n)×C2(m,n)(5)

式(5)中:C(m,n)為模板與圖像相關(guān)系數(shù);C1(m,n)為模板M(i,j)的自相關(guān)系數(shù);C2(m,n)為當(dāng)前圖像幀在以像素點(diǎn)(m,n)處為中心的M×N范圍內(nèi)的自相關(guān)系數(shù)。

其中R(m,n)的取值范圍為[0,1],最優(yōu)搜索匹配位置就是使歸一化相關(guān)系數(shù)R(m,n)最大的那個(gè)位置,即是當(dāng)前圖像幀中該特征點(diǎn)的最優(yōu)跟蹤測(cè)量位置點(diǎn)。

3 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)對(duì)象為合成立方實(shí)體運(yùn)動(dòng)圖像序列。利用計(jì)算機(jī)輔助設(shè)計(jì)軟件Swift 3D生成立方實(shí)體模型。將該模型以給定的、很小的旋轉(zhuǎn)和平移量在3D空間運(yùn)動(dòng),獲取其連續(xù)圖像序列,如圖1所示。分別為連續(xù)運(yùn)動(dòng)圖像序列的第一幀及其直線檢測(cè)圖像,利用該文的方法檢測(cè)連續(xù)圖像中的特征直線及其匹配。

圖1 合成立方體及其直線檢測(cè)圖像

對(duì)圖像序列的連續(xù)三幀圖像進(jìn)行濾波,并采用Canny算子進(jìn)行邊緣檢測(cè),采用Hough變換提取直線的改進(jìn)方法對(duì)圖像進(jìn)行直線提取,將直線的方程表示成法線式,得到各條直線的Hough空間坐標(biāo)ρ和θ,將各條直線連續(xù)三幀的Hough空間坐標(biāo)映射到Hough空間上。將獲取的Hough空間圖像采用卡爾曼濾波算法,估計(jì)Hough空間中特征點(diǎn)運(yùn)動(dòng)的軌跡參數(shù),得到預(yù)測(cè)點(diǎn)的粗略位置,存儲(chǔ)各位置坐標(biāo),利用匹配模板在以預(yù)測(cè)點(diǎn)為中心的小區(qū)域搜索,按式(5)計(jì)算出各個(gè)位置的歸一化相關(guān)系數(shù)R(m,n),記錄R(m,n)為最大值的點(diǎn),即為這兩幀中匹配的特征點(diǎn),也就是相應(yīng)連續(xù)圖像平面中匹配的直線。該次實(shí)驗(yàn)中共匹配到如表1所示的1~11條直線參數(shù)坐標(biāo)。

表1 合成立文體的直線提取及跟蹤匹配結(jié)果

直線編號(hào)第一幀(ρ,θ)第二幀(ρ,θ)第三幀(ρ,θ)

1-100.355 9-1.57-100.355 9-1.57-100.355 9-1.57

2-138.491 1-1.134 5-137.487 5-1.134 5-136.484 0-1.134 5

341.145 9-1.134 544.156 6-1.11747.167 3-1.099 6

4189.672 60.017 5187.665 50.017 5183.651 20

5169.601 40.261 8173.615 70.209 4176.626 30.157 1

675.266 90.261 888.313 20.331 698.348 80.366 5

7222.791.134 5223.793 61.117224.797 21.117

823.081 9-0.261 823.081 9-0.331 625.089 0-0.384

944.156 61.11744.156 61.134 546.163 71.117

10-58.206 4-0.541 1-72.256 2-0.645 8-81.288 3-0.715 6

11115.409 3-0.279 3129.459 1-0.226 9145.516 0-0.157 1

4 結(jié) 語

在此利用Hough變換提取直線的改進(jìn)方法,提高了Hough變換提取直線的精度,并且利用Hough變換的點(diǎn)線對(duì)偶性,將對(duì)圖像序列中的特征直線的匹配轉(zhuǎn)化為在參數(shù)空間(ρ,θ)中對(duì)特征點(diǎn)運(yùn)動(dòng)軌跡的參數(shù)估計(jì),設(shè)計(jì)采用卡爾曼濾波器對(duì)運(yùn)動(dòng)目標(biāo)進(jìn)行初步預(yù)測(cè)估計(jì),通過建立模板與圖像的匹配相關(guān)系數(shù),便可搜索判定參數(shù)空間特征點(diǎn)的精確坐標(biāo),即圖像空間中匹配的直線。

實(shí)驗(yàn)結(jié)果表明該方法取得了較好的直線提取和匹配效果,可應(yīng)用于基于直線運(yùn)動(dòng)的三維物體運(yùn)動(dòng)和結(jié)構(gòu)重建的研究中。

參考文獻(xiàn)

[1]馬頌德,張正友.計(jì)算機(jī)視覺計(jì)算理論與算法基礎(chǔ)[M].北京:科學(xué)出版社,1998.

[2]陳海峰.數(shù)字圖像中基本幾何形狀檢測(cè)算法的研究與應(yīng)用[D].杭州:浙江大學(xué),2007.

[3]許強(qiáng),陳震.圖像序列直線提取和匹配時(shí)Hough變換的應(yīng)用研究[J].南昌航空工業(yè)學(xué)院學(xué)報(bào):自然科學(xué)版,2007,21(1):43-47.

[4]康文丁,丁雪梅,崔繼文,等.基于改進(jìn)Hough變換的直線圖像快速提取算法[J].光電工程,2007,34(3):150-108.

[5]Mieghem J A V,Avi-Itzhak H I,Melen R D.Straight Line Extraction Using Iterative Total Least Squares Methods[J].Journal of Visual Communication and Image Representation,1995,6(1):59-68.

[6]楊順遼.基于Hough變換提取直線的改進(jìn)方法研究[J].電腦與信息技術(shù),2006,14(5):29-31.

[7]楊順遼.弗里曼鏈碼法在圖像處理中的應(yīng)用[J].中國水運(yùn):理論版,2006,4(1):23-25.

[8]JeongHun Jang,KiSang Hong.Fast Line Segment Grouping Method for Finding Globally more Favorable Line Segments[J].Pattern Recognition,2002,35:2 235-2 247.

[9]陳震,高滿屯,楊聲云.基于Hough變換的直線跟蹤方法[J].計(jì)算機(jī)應(yīng)用,2003,23(10):30-32.

[10]Kalman R E.A New Approach to Linear filtering and Prediction Theory[J].Transactions of the ASME-Journal of Basic Engineering,1960(82):35-45.

[11]董梁.基于哈夫變換的圖像邊緣連接[J].現(xiàn)代電子技術(shù),2008,31(18):149-150,156.