二維圖像序列直線的提取及跟蹤匹配研究

簡宏偉,陳 震

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

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

中圖分類號:TN919文獻標識碼:A

文章編號: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

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

1 Hough變換提取直線的改進方法

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

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

ρ=x2cos θ+y2sin θ

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

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

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

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

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

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

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

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

(6) 將搜索范圍擴展至全圖,對檢測到的每個非零點,令=,若-<Δρ,則認為屬于該直線,將其投票數進行累加,并將該點的灰度置為0;

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

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

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

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

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

在此針對Hough空間特征點的跟蹤估計,可設一個特征點的運動軌跡由三次多項式來描述,定義狀態(tài)向量為下列一個六維向量X=[p,,],其中點P在Hough空間位置坐標為P=(ρ,θ)T,狀態(tài)方程為:

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

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

F=I2I2T12I2T

02I2I2T

0202I2

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

而在Hough空間中僅能觀測到特征點的坐標位置,所以,觀測方程可以表達為:

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

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

因為狀態(tài)方程和觀測方程都是線性的,可以直接應用標準的Kalman濾波器來實現(xiàn)對Hough空間特征點的跟蹤。

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

(1) 利用系統(tǒng)的狀態(tài)模型預測下一狀態(tài)的系統(tǒng)。在Hough空間中預測運動目標特征點的狀態(tài)向量。

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

(2) 特征點狀態(tài)向量協(xié)方差矩陣P(k)的預測和Kalman增益矩陣Kg(k)的計算。

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)對應的協(xié)方差,P(k-1|k-1)是X(k-1|k-1)對應的協(xié)方差;式(2),式(3)是對系統(tǒng)的預測。

(3) 由Hough空間特征點的觀測值(ρ,θ)和預測值來更新運動目標特征點的狀態(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) 由上面三個步驟已經得到最優(yōu)的估算值X(k|k),但是為了要令Kalman濾波器不斷地運行下去,直到系統(tǒng)過程結束,就要更新X(k|k)的協(xié)方差P(k|k)。

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

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

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

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

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

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

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

3 實驗與結果

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

圖1 合成立方體及其直線檢測圖像

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

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

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

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 結 語

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

實驗結果表明該方法取得了較好的直線提取和匹配效果,可應用于基于直線運動的三維物體運動和結構重建的研究中。

參考文獻

[1]馬頌德,張正友.計算機視覺計算理論與算法基礎[M].北京:科學出版社,1998.

[2]陳海峰.數字圖像中基本幾何形狀檢測算法的研究與應用[D].杭州:浙江大學,2007.

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

[4]康文丁,丁雪梅,崔繼文,等.基于改進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].電腦與信息技術,2006,14(5):29-31.

[7]楊順遼.弗里曼鏈碼法在圖像處理中的應用[J].中國水運:理論版,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].計算機應用,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)代電子技術,2008,31(18):149-150,156.