攝像機旋轉運動下的快速目標檢測算法

蔣建國 ， 吳 暉， 齊美彬， 張 莉

（1. 合肥工業大學計算機與信息學院，安徽 合肥 230009；2. 安全關鍵工業測控技術教育部工程研究中心，安徽 合肥 230009）

在智能監控系統中，有時需要攝像機旋轉（主要是俯仰運動和平掃運動）以增加監控的范圍，或者隨著目標的移動進行主動跟蹤，因此研究攝像機旋轉情況下的運動目標檢測具有重要意義。通常，人們將攝像機運動導致圖像全局運動的序列稱為動態場景圖像序列，動態場景圖像序列的目標檢測問題近年來已成為學者研究的熱點[1-5]。動態場景下運動目標檢測一般分為兩個步驟[6]：第1步是運動補償。其目的在于將攝像機運動導致的背景運動去除。首先計算全局運動參數，再使用計算出的全局運動參數，計算出當前幀每個像素的移動速度，預測該像素在下一幀的位置，得到補償圖像；第2步是目標檢測。將補償圖像與下一幀或重建的背景圖像做幀差，得到運動目標。其中運動補償最為關鍵，常用的算法有3種：第1種是分塊運動補償(BMC for block motion compensation)[6-7]，它將每幀分成若干像素塊，并且假設塊內像素運動矢量相同。對當前幀的某個塊進行預測下一幀中的位置，預測的過程只有平移，其中背景塊的運動矢量即為全局運動矢量。該方法的缺陷是不適合旋轉、縮放或者仿射變換等圖像非平移運動的情況。第2種是光流法。該方法對每個像素都計算運動矢量，從而得到整幅圖像的運動場，再對運動場進行聚類分割，直接得到前景和背景[8-10]。光流法適應的范圍比較廣，但是它的缺點是運算量太大。第3種是特征點匹配的方法，該方法在相鄰幀中分別提取特征點，并匹配特征點，再利用匹配的特征點對求解全局運動參數。

由于特征點匹配的方法不需假設塊內像素運動一致的條件，擺脫了塊匹配方法只適合平移的限制；也不需要像光流法一樣對每個像素求運動矢量，只需要對某些有特征的，穩定的點計算，大大提高了算法速度。基于上述兩點考慮，本文便采用這種方法。

SIFT特征點是Lowe在1999年提出[11]，2004年完善的特征算子[12]，該算子不但具有尺度、仿射、視角、光照不變性，對目標的運動、遮擋、噪聲等因素也有很好的魯棒性。該算子一個重要的特點是匹配點多而且穩定，已被廣泛采用在機器人定位，三維場景建模等方面。SIFT特征點匹配按照最小歐式距離原則，使用 BBF(Best-Bin-First)方法匹配特征點。這個過程首先需要建立樹，其次在樹中查找最優匹配點。當特征點數目比較多的時候，這種方式比較耗時，難以滿足實時性的要求。因此，本文針對SIFT匹配算法速度上的缺陷，提出了基于運動預測的特征點匹配算法，在保持SIFT良好性能的前提下，提高匹配效率，快速檢測出運動目標。

1 快速目標檢測算法

運動補償的關鍵在于求解全局運動參數，1.1節對全局運動建立旋轉參數模型，并介紹了特征點匹配的方法求解運動參數的原理；針對SIFT算法檢測效率低的缺陷；1.2節提出基于運動預測的特征點匹配算法；1.3節介紹特征點更新策略；1.4節為算法整體描述。算法整體流程如圖1所示。

圖1 算法流程圖

1.1 求解全局運動參數

全局運動模型[13]常用的有：二參數、四參數、六參數仿射模型等。這些模型都屬于線性模型，即像素的運動矢量大小與像素坐標呈線性關系。當攝像機旋轉角度比較小時，這些模型一般能夠很好的描述背景運動，但是當攝像機旋轉的角度比較大時，像素運動矢量與坐標之間是非線性的二次型變換的關系，上述模型不能準確的描述全局運動，因此作者引入旋轉參數模型[14]。

矩陣A為常數矩陣，由攝像機內部參數和t時刻攝像機的旋轉角速度所決定，與像素坐標無關。若已知t時刻的旋轉參數矩陣A，那么由式(1)，就可以求得圖像的全局運動，從而進行運動補償。實際應用時，攝像機的瞬時旋轉速度是未知的，而且攝像機通常都是未被標定過的，所以必須通過別的途徑估計矩陣A。值得一提的是：如果將矩陣中二次項對應的參數設為零，就可以變換成其他的參數模型。因此，使用該模型的好處是：不僅能夠準確的描述攝像機旋轉情況下的圖像全局運動，對于攝像機平移、縮放的情況同樣適用。

使用特征點匹配方法求解全局運動參數的思想就是：在相鄰兩幀中分別搜索特征點，再對特征點進行匹配，得表示匹配點對的集合，其中 fn=(Xt-1,n, Xt,n)為第n對匹配特征點。由式(1)可以建立方程組，每對特征點可以建立兩個方程，因此N對特征點可以建立2×N個方程，而矩陣A只有8個參數，這是一個超約束方程組，可以采用最小二乘法求最優解。

由于噪聲影響，特征點會出現少量誤匹配的情況，誤匹配的點也稱為外點。即使外點的數目很少，也有可能會導致計算結果與真實值有較大的偏差。因此，采用RANSAC方法[15]來去除外點。該方法通過重復迭代過程，在集合中尋找到不含外點的最大子集（也稱為最大一致集）。去除外點之后采用最小二乘法求得的參數矩陣就比較接近真實值。

1.2 基于運動預測的特征點匹配算法

考慮到監控視頻相鄰幀的時間間隔是很短的，在幀率為25時，兩幀間只有40ms的間隔，在這樣非常短暫的時間內，攝像機的旋轉不會帶來場景的大幅度變化，相鄰幀間通常只是幾個像素的移動量。(t-1)幀的特征點集實際上包含了大量t幀對應特征點位置的信息，因此，可以充分利用這一信息，進行基于運動預測的匹配，快速匹配特征點。其思路是：使用上一幀圖像特征點集對當前幀特征點的位置進行預測，在預測位置的一個小范圍內搜索特征點，從而得到當前幀的特征點集。

匹配過程如下：

該算法的優點在于：

（1）減少外點的影響。使用Lowe的樹查找方式時，并沒有考慮到匹配點之間的位置相關性，兩個位置相差很大的點可能因為其特征描述子的相似性而發生誤匹配的情況；而基于預測的匹配算法實際上是給匹配點對加上了一個位置的約束，這樣就避免了某些誤匹配的發生，保證參數矩陣的準確求解；

（2）由于對特征點可能存在的位置進行了預測，減少了搜索范圍；

（3）搜索到的點與它在上一幀中的對應形成匹配的特征點對，無需為上一幀的特征點集建立樹，以及在樹中查找最優匹配點，節約了匹配時間。

需要注意的是 N的選取與算法的計算量直接相關。N太大的話，搜索范圍增大，計算量增大，對實驗結果并無明顯改善；通過對多組動態場景下拍攝的視頻進行實驗（包括平移、緩慢旋轉和快速旋轉），確定N =3時效果最佳。

1.3 基于殘差圖像的特征點更新

由于攝像機的旋轉，視場中的場景也在發生變化，圖像的特征也逐漸改變，如果不及時更新特征點，那么匹配特征點對的數目不可避免的將減少，影響運動參數的求解。因此，當某時刻的匹配特征點數目減少到Tf時，就更新特征點集，保證下一幀有足夠的匹配點對進行參數求解。Tf的選取非常重要，如果太小，平均匹配點數下降，最小二乘解不夠準確；Tf太大則造成不必要的冗余數據，降低算法效率。

為了驗證 Tf對算法性能的影響，用TPR(True Positive Rate)來衡量。TPR為最終檢測出的前景中，屬于真實目標的比率，取值在0到1之間；TPR越接近1，說明檢測的準確度越好。

圖2反映了Tf對算法性能的影響：圖 2(a)說明隨著Tf的增大，算法速度近似線性的下降。圖2(b)反映了Tf對TPR的影響。Tf＜ 1 5時，Tf增大，TPR隨之增大；Tf＞ 1 5時， TPR接近100%，增幅也不明顯。綜合考慮算法速度和準確性，選擇 Tf= 1 5。

更新特征點最簡單的方式是全圖搜索新的特征點，但這樣做會有很大的缺陷：運動目標即前景往往是特征豐富的，當全圖搜索進行更新時，將會有很大一部分更新的特征點是目標上的點。但是在計算全局運動參數的時候，真正起作用的是背景點。因此，更新范圍要盡可能排除目標所在的區域。

圖2 Tf對算法性能的影響

基于殘差圖像可以快速標記出前景所在的區域，標記過程如圖3所示。由于直接對殘差圖像處理數據量較大，必須先對其下采樣到原圖的1/16，再將下采樣的圖分為4× 4的小塊。當某個塊的前景點數大于零時，標記該塊為前景塊，否則為背景塊。更新過程只在背景塊中進行，并且要避免特征點集中在一個小的區域。實驗證明當特征點在圖像中分布均勻時，運動補償效果最佳。

圖3 標記前景塊示意圖

1.4 算法整體步驟

已知Pt-1為t-1幀的特征點集，At-1為t-1幀的旋轉參數矩陣。第t幀運動目標檢測算法詳細步驟如下：

步驟 2 由Pt-1和tP建立匹配點對tF。

步驟 3 應用 RANSAC算法去除tF中的外點，再使用最小二乘法求t幀的旋轉參數矩陣At。

步驟 4 使用式(1)對t-1幀圖像It-1進行運動補償，得到補償圖像。

步驟 5 將第t幀圖像It和補償圖像做幀差處理，得到殘差圖像Iobj。

步驟 6 判斷tP中特征點數目是否小于Tf，若小于，則更新特征點。

步驟 7 保存Iobj,At和tP。t←t+1，結束。

2 實驗結果

為了驗證該算法的性能，作者將SIFT算法、塊匹配算法[7]和該算法分別應用于三組實驗視頻，并對結果進行對比和分析。實驗平臺在Core 2 Duo、內存1G的PC機上使用VC6.0進行調試。為了提高檢測效率，我們采用隔幀檢測的方法。

圖4是對一實拍外景序列的實驗結果，圖像分辨率為 320×240。圖 4(a)為原序列的第 50和100幀；圖4(b)為塊匹配的方法得到的檢測結果，可以看到背景中的樹木沒有被完全去除，而且目標比較模糊，不能清楚分辨；圖4(c)和圖4(d)中分別為SIFT算法和該算法的結果，可以看到二者效果基本相同，都可以很好的完整正確的檢測到目標，背景干擾完全去除，這說明該算法很好的繼承了SIFT算法本身的優越性能。

圖4 序列1的實驗結果

圖5是對圖4中的同一場景增大攝像機旋轉速度的實驗結果，其目的是考察算法在快速旋轉情況下的性能。經測定，該攝像機旋轉角速度約為0.5rad/s。圖5(a)為原序列的第25和50幀；圖5(b)中塊匹配的方法不能夠準確的運動補償，因此背景的干擾非常嚴重；圖5(c)和圖5(d)中SIFT算法和本文算法依然能夠很好的檢測出前景目標。此組實驗說明在旋轉速度比較大，塊匹配方法失效的情況下，本文算法仍能夠穩定地檢測出目標。

圖5 序列2的實驗結果

圖6是對MPEG-4標準測試序列coastguard的實驗結果，圖像分辨率為352×288。該序列的背景運動屬于攝像機平移導致的全局運動，從實驗結果可以看到，3種算法的性能相當，都可以較好的去除全局運動的影響。此組實驗說明本文算法不僅能夠處理復雜的旋轉情況，而且對于攝像機平移的情況同樣適用。

圖6 序列3的實驗結果

表1是3種算法的處理速度比較。從表中可以看出，本文算法的速度是塊匹配方法的 2倍，是SIFT算法的5倍，在隔幀處理時，滿足實時性的要求。而且，本文算法檢測準確度高，能夠準確進行運動參數估計，去除全局運動的影響。因此，本文提出的特征點匹配與更新算法對于攝像機旋轉運動下的目標檢測比傳統的算法更具有實用性。

表1 3種算法執行時間比較

3 結 論

本文提出了一種基于運動預測的特征點匹配算法以解決運動攝像機下的目標檢測問題。首先為圖像的全局運動建立旋轉參數模型，其次通過特征點匹配算法在相鄰幀建立特征點對，并通過最小二乘求解旋轉參數，最后基于殘差圖像的特征點更新策略保證了參數的穩定求解。實驗結果證明本文算法可以實時、準確地檢測出復雜場景中的運動目標。

[1]Irani M, Anandan P. A unified approach to moving object detection in 2D and 3D scenes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 6(6): 577-589.

[2]Kang J, Cohen I, Medioni G, et al. Detection and tracking of moving objects from a moving platform in presence of strong parallax [C]//Proceedings of the IEEE International Conference on Computer Vision,Beijing, 2005: 10-17.

[3]Kundu A, Krishna K M, SIVASWAMY J. Moving object detection by multi-view geometric techniques from a single camera mounted robot [C]//IEEE International Conference on Intelligent Robots and Systems, 2009: 4306-4312.

[4]Sorwar G, Murshed M, DOOLEY L. Fast global motion estimation using iterative least-square estimation technique [C]//Proceedings of the 2003 Joint Conference of the Fourth International Conference on Information, Communications and Signal Processing, Singapore, 2003: 282-286.

[5]Rath G B, Makur A. Iterative least squares and compression based estimations for a four-parameter linear global motion model and global motion compensation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1999, 9(7):1075-1099.

[6]Dufaux F, Konrad J. Efficient, robust and fast global motion estimation for video coding [J]. IEEE Transactions on Image Processing, 2000, 9(3):497-500.

[7]Tao T F, Han C Z, Wu Yanqi. Motion estimation based on an improved block matching technique [J].Chinese Optics Letters, 2006, 14(4): 208-210.

[8]Wang J, Adelson E H. Representing moving images with layers [J]. IEEE Transactions on Image Processing Special Issue: Image Sequence Compression, 1994, 3(5): 625-638.

[9]Forsyth D A, Ponce J. Computer vision: a modern approach [M]. New Jersey: Prentice Hall, 2002:359-368.

[10]Turetken E, Alatan A. Temporally consistent depth ordering via pixel voting for pseudo 3D representation [C]// 3DTV Conference: The True Vision Capture, Transmission and Display of 3D Video, 2009: 1-4.

[11]Lowe D G. Object recognition from local scale invariant features [C]//International Conference on Computer Vision, Corfu, Greece, 1999: 1150-1157.

[12]Lowe D G. Distinctive image features from scale invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[13]Mech R, Wollborn M. A noise robust method for 2D shape estimation of moving objects in video sequences considering a moving camera [J]. Signal Processing, 1998, 66(2): 203-217.

[14]Hartley R, Zisserman A. Multiple view geometry in computer vision [M]. Cambridge: Cambridge University Press, 2003: 153-176.

[15]吳福朝. 計算機視覺中的數學方法[M]. 北京: 科學出版社, 2008: 338-343.