外點不敏感的快速圖像配準算法

摘 要：提出一種圖像配準算法，用于視頻監控中將預存的背景幀與當前視頻幀配準檢測出運動對象。由于外點的存在，運動參數方程求解只適于使用穩健回歸算法，但穩健回歸需要較長的計算時間，因此提出一種稱為屏蔽外點的圖像配準算法，綜合利用線性回歸和穩健回歸，求解運動參數方程。實驗表明，該方法在計算速度和穩健性兩方面均有較好的綜合性能。

關鍵詞：穩健回歸；線性回歸；圖像配準；外點

中圖法分類號：TN919.81； TP391.4文獻標識碼：A

文章編號：1001—3695(2007)02—0178—03

1 引言

圖像配準在醫療圖像處理、三維重建、虛擬現實、視頻監控等領域均有重要應用。現有算法大致可以劃分為基于特征的算法[1—3]、耗盡性搜索算法[4] 、頻率域算法[5]和基于模型的算法[6， 7]四類。基于特征的算法依賴于精確的圖像特征檢測，根據特征的位移計算攝像機的運動參數，但當缺少圖像特征時算法容易失敗；耗盡性搜索算法通過窮盡運動參數所有可能取值尋找最佳匹配，顯然當運動參數較多時這一算法計算代價太大；頻率域算法對計算位移和旋轉運動參數很有效，其不足是對噪聲較敏感；基于模型的算法假定背景幀與當前幀的差異是由攝像機的運動產生的，通過建立攝像機的運動模型求解背景幀與當前幀之間的最佳匹配，該方法的優點是圖像配準精度高。由于現有基于模型的算法主要考慮的是配準精度，而對算法的實時性考慮較少，在通用PC上不能實時運行，因此對視頻監控等大多采用PC和強調實時性的應用仍需進一步的研究。

基于模型的配準算法的時間主要取決于采用的運動參數模型和求解參數的算法。常用的圖像配準參數模型主要是透視模型[8]和仿射模型[9]。透視模型用于配準精度要求較高而實時性要求不強的應用，如圖像拼接（Mosaic）、3D重建等，其要求估計八個運動參數，不利于算法快速實現；仿射模型只有六個運動參數，有利于算法優化，可用于配準精度不太高但實時性要求較強的應用。本文研究視頻監控中的圖像配準算法，由于在精度和實時性兩方面更注重于實時性，因此選擇六參數仿射模型。

2 視頻幀之間的運動參數求解

圖像配準就是求解兩幅圖像之間的運動參數。當兩幅圖像之間的運動參數較大時，可以利用連續圖像運動的原理來求解。若t時刻圖像運動參數矢量用ρ(t)表示，則連續圖像運動參數的變化表示為

3 快速圖像配準算法

第2節內容僅用于兩幅圖像運動參數變化較小時的情況。實際兩幅需要配準的圖像之間的運動可能較大，直接求解方程，不僅需要很長的計算時間，而且有可能只得到方程的局部最優解。要解決這一問題，一般采用多分辨率分層圖像配準。多分辨率分層圖像的生成可以使用小波分解，也可以使用高斯金字塔分解[11]，考慮算法的速度和實現復雜性，本文采用高斯金字塔分解。配準操作從最低分辨率開始，低分辨率得到的運動參數作為下一較高分辨率級的初始參數，求解新的更精確的運動參數，直到最高分辨率層。

實際上在同一分辨率級，一次配準操作往往難以得到最優解，一般需要多次配準循環操作才能得到最優解。相鄰兩次配準也符合連續圖像的運動問題，可使用與分層配準相同的運動參數模型。本文對同一分辨率層的多次配準操作使用圖像矯正(Warp)技術，即利用當前運動參數將當前幀變換到背景幀坐標系下得到新的當前幀，在下一次循環中將新的當前幀與背景幀配準，更新運動參數，如此下去，直到運動參數不再發生有意義的變化。

式（1）可以使用線性回歸和穩健線性回歸[12]。線性回歸得到的是最小平方解，算法速度較快，但當圖像中存在外點（Outliers）時（外點主要由運動對象引起），由于外點一般產生的平方差都很大，使得平方解偏向于外點的運動參數，這不是圖像配準所希望的。穩健回歸通過限制平方差值較大的像素點的權值，減少外點對解的影響，得到的解更符合圖像配準應用的需要。穩健回歸的缺點是算法需要的計算時間較長。

本文提出一種綜合利用線性回歸和穩健回歸屏蔽外點影響的運動參數求解算法，即MO(Mask Outliers)算法。MO算法的主要思想是，在圖像最低分辨率層使用穩健回歸得到初始的運動參數，根據這一運動參數將該層的當前幀變換到背景坐標系下使用背景減確定出該層的外點，并以此估計出下一高分辨率層的外點位置，在下一高分辨率層配準之前先將外點清除，然后使用線性回歸求解運動參數，如此估計和清除更高分辨率層的外點，使用線性回歸估計運動參數直到最高分辨率層。因本文算法只在最低分辨率層使用穩健估計，所以算法的時間接近線性回歸求解，并且由于算法在計算過程中消除了外點的影響，因此算法有較好的穩健性。

根據低分辨率層的外點估計較高分辨率層中的外點是基于這樣的觀察：不同分辨率層圖像像素之間的關系可以看作是樹型結構，低分辨率層中的一個節點（像素）在更高分辨率層對應四個子節點（像素），如圖1所示，當父節點為外點時其下層的四個子節點也是外點。實驗表明這一觀察基本正確，這一外點消除方法是可行的。圖2是一個配準實例在當前幀各分辨率層估計出的外點（線段連接的區域），得到的外點基本上是運動目標所處的像素。

4 算法速度與穩健性實驗

實驗計算機配置PⅢ 800Hz/256MB，Windows 2000操作系統，圖像幀大小320×240，算法采用MATLAB 6實現。為了測試本文算法的速度和穩健性，實驗選取兩幅基本上沒有外點的視頻幀，一幅作為背景幀(圖3)；另一幅作為當前幀(圖4)。為了便于與其他算法對比，外點是通過人工加入亮度較大的矩形圖塊產生的，這樣可以清楚知道兩幅圖像中實際存在的外點數和不同算法實際發現的外點數，從而比較出不同算法性能。兩個對比算法是美國斯坦福大學的教授Heeger用MATLAB語言實現的基于仿射模型的線性回歸和穩健回歸圖像配準算法。實驗引入的外點數量從0—2 500，共進行了26組實驗，所有算法均采用相同的結束條件：連續兩次配準循環運動參數不再發生有意義的變化，即|| δρ||< ε（ε為常數）。圖5、圖6分別是三種算法隨著引入外點數目的增加，檢測出的外點數目和執行時間變化的曲線。

（1）算法穩健性比較：圖5中的三角符號曲線為本文算法檢測出的外點數目隨引入外點數目變化的關系圖，本文算法檢測出的外點數目基本上等同于實際圖像中存在的外點數目，因此曲線基本近似為一條直線；圖5中菱形符號曲線代表線性回歸算法，當外點數目超過400點時，檢測出的外點數目已遠遠超過實際的外點數目，當外點繼續增加時，檢測出的外點迅速增加，表明配準算法失敗，這說明線性回歸算法穩健性較差；相對于線性回歸算法，穩健回歸有較好的穩健性，在外點數目增加到1 700個之前，穩健回歸基本上與本文算法檢測出的外點數曲線重合，但當外點增加超過1 700時，穩健回歸算法檢測出的外點數目劇增，表明配準算法失敗。實驗結果表明本文算法具有更好的穩定性。

（2）算法的執行時間比較：從圖6可以看出，本文算法在外點數為2 000以下時耗時0.8s，當外點超過2 000點時算法執行時間迅速增加，當外點超過2 500時需要耗時2s左右；線性回歸算法所需要的時間基本上不受引入外點的影響，大約需要3s左右；穩健回歸在外點數目沒有超過1 700點以前基本固定，大約需要4s，但外點超過1 700點時由于配準算法失敗，可能產生各種解，因此算法需要的時間出現波動。從算法的執行時間來看，本文算法是最快的，當外點數目不太多時算法可在1s內完成，即使外點較多時本文算法的執行時間也不超過線性回歸算法。

5 結束語

由于外點的存在，運動參數方程求解只適于使用穩健回歸算法，但穩健回歸需要較長的計算時間。本文利用高斯金字塔多分辨率參數估計，在最低圖像分辨率級使用穩健回歸，并以此估計出較高分辨率級中圖像的外點，在消除這些外點之后利用一般線性回歸算法求解運動參數方程，這樣有效地減少了運動參數的計算時間。

由于圖像配準操作過程涉及大量的圖像變換（Warp）和插值等耗時的運算，使用軟件方法在目前的PC機上還不能做到實時檢測。但圖像變換和插值計算都是并行性很強的運算，特別適于使用數字處理芯片（如FPGA，DSP等）進行處理，因此將來可以考慮用硬件實現圖像配準以解決實時檢測問題。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。