基于改進遺傳算法的攝像機自標定方法

(西南科技大學 計算機科學與技術學院，四川 綿陽 621010)

0 引言

攝像機標定是計算機視覺領域的關鍵技術，它是從二維圖像恢復到三維圖像的必不可少的步驟，被廣泛應用到三維測量、三維物體重建、物體識別、工業檢測、虛擬現實等領域。目前攝像機標定技術有很多種分類方法，應用最為普遍的是將其分為傳統攝像機標定方法、自標定方法和基于主動視覺的標定方法[1]。傳統攝像機標定方法需要利用幾何參數精確且已知的標定塊，其優點是標定精度比較高但是標定過程復雜，計算量大，且需要精密加工的標定參照物。基于主動視覺的標定方法是指在已知的運動軌跡信息下進行攝像機標定，其優點是可以線性求解攝像機的模型，因而算法簡單和魯棒性比較高，但限制了攝像機的運動。以上兩種方法均有一些限制條件，對于場景任意，攝像機運動未知的情況則不能實現。自標定技術則無需要求標定板和已知攝像機運動軌跡信息，僅通過圖像與圖像之間的對應點間的關系直接求解攝像機模型,即求解攝像機的內參數矩陣K，K包含4個未知參數(攝像機的焦距和主點的坐標)。

攝像機自標定方法可以分為以下4種方法：Faugeras[2]提出的直接求解Kruppa方程的方法，利用絕對二次曲線和極線變換推導出Kruppa方程；分層逐步標定方法[3]，首先對圖像序列做射影重建再通過絕對二次曲線加以約束，最后求得仿射參數和攝像機內參數；Triggs[4]提出的絕對二次曲面的自標定方法，該方法和基于Kruppa方程的方法都是利用絕對二次曲線在歐式變換下的不變性，但基于絕對二次曲面的方法更有利于多幅圖像的標定；可變內參數的攝像機標定方法，Heyden[5]等人證明了內參數可變的情況下可以實現攝像機的自標定。

直接求解Kruppa方程的方法是一個非線性問題。可以利用一些優化算法對Kruppa方程所提供的代價函數進行優化。傳統的基于遺傳算法的攝像機自標定方法參數優化過程中，易出現過早收斂、停滯現象和解易陷入局部最優的問題。因此，針對傳統方法中出現的上述問題，本文提出了一種改進的基于遺傳算法的攝像機自標定方法。

1 算法原理

1.1 投影模型

在攝像機模型為針孔模型下，假設三維空間點為X=(x,y,z,1)T對應到二維圖像的點為m=(u,υ,1)T。它們的成像關系可以表示為：

m?K[R|t]X#

(1)

1.2 基礎矩陣和Kruppa方程

從兩不同的視點獲得的同一場景的兩幅圖像，它們之間存在著一定的約束關系，這就是對極幾何關系。基礎矩陣F是對極幾何關系的代數表達。根據攝像機與圖像之間的關系，Faugeras、Luong和Maybank等人提出可用Kruppa方程表示為(具體推導方法可參閱文獻[6])：

(2)

在Kruppa方程中，我們只需要已知極點e′和基礎矩陣F就可以知道矩陣C即攝像機內參數K。但是極點非常的不穩定，不易確定。因此Hartley提出了一種不需要極點的新的Kruppa方程形式[7]。令基礎矩陣F的SVD分解為F=UDVT。其中矩陣U和V的列向量分別為F的左奇異向量和右奇異向量。D是一個對角矩陣，對角線上的元素就是F的奇異值。直接由基礎矩陣推導得到Kruppa方程的簡化形式：

(3)

其中:Vi和Ui分別表示的是矩陣V和U的第i列向量，r和s是F的奇異值。

(4)

(5)

(6)

設目標函數為:

f(fu,fv,u0,v0)=

(f1-f2)2+(f1-f3)2+(f3-f2)2#

(7)

目標函數f的值最小或趨近為0時，C即為所求的值。

2 基于改進的遺傳算法的攝像機自標定

遺傳算法是受達爾文進化論的啟發，通過模擬自然界和生物進化過程而被提出的用來解決優化問題的有效方法，是一種啟發式的搜索方法，也稱進化算法[8]。傳統的遺傳算法操作盲目無方向，所需要的收斂時間長且最優值容易早熟陷入局部最優。

文獻[9]證明遺傳算法雜交過程的成熟化效應是引起遺傳算法過早收斂的主因。過早收斂現象表現出來的特征是種群序列多樣性減少。為了使最優值結果避免過早陷入最優解，主要是要使種群序列多樣性高。

本文對遺傳算法做出了以下改進：結合精英保留策略和隨機聯賽選擇算法作為初始化種群的方法；采用實數編碼；改進輪盤賭選擇方法；采用自適應雜交概率和變異概率方法。

2.1 編碼

本文采用實數編碼方式。傳統的遺傳算法一般采用二進制編碼方式，二進制編碼使用字符集(0，1)組成，雖然簡單易用，但是存在Hamming懸崖問題，在求解最優化問題時缺陷較大。實數編碼方式更接近問題空間，在基因型空間和表現型空間中是一致的。

2.2 改進的種群初始化

傳統的遺傳算法初始化是隨機生成個體。這種初始化的種群對于多峰病態復雜函數來說，如后續遺傳算子操作不當很容易使算法出現早熟現象。為了使搜索過程中更大概率找到真正最優值的波峰，初始化時結合了隨機聯賽選擇算法和精英保留策略。初始化步驟：

1)按照搜索空間采用線性隨機生成方法生成N個個體。

2)計算N個個體的適應度，對N個適應度進行從大到小到排序。

3)選取適應度最大的那個個體作為初始種群的成員。

4)重復上面1)～3)的步驟直到初始種群滿員。

這樣初始種群本身就會具有較高的適應度，而且種群內個體處在最優解所處波峰附近的概率就會大大地提高。

2.3 改進的輪盤賭選擇算法

輪盤賭選擇算法選擇的依據是目標函數的適應度大小。在進化初期通常會產生一些適應度超常大的個體，這些異常大的個體被選擇的概率很大，它們會很大程度地控制選擇過程，造成種群的多樣性降低。因此，本文算法將每次被選擇的個體從總選擇序列中拿出，不在參與下一次選擇。

改進的輪盤賭選擇步驟：

1)將種群全部個體的適應度進行從大到小排序，求得全部個體的適應度總和S。

2)產生一個0～S之間的隨機數M。

3)從種群中編號為1的個體開始，將其適應度值與后面個體的適應度值相加，直到累加的和大于M則停止。最后加進去的個體即為被選擇出的父代。

4)將被選擇的個體從種群中拿出，重復2)、3)步驟直到選擇出足夠多的父代。

這樣避免了哪些異常大的值會被多次選中，豐富了種群的多樣性。并且適應度值異常大的值也不會被破壞，從而避免了進化初期適應度異常高個體處于局部最優情況導致的算法收斂于局部最優的情況。

2.4 自適應的雜交和變異概率

雜交是模仿生物自然進化過程中，兩個個體間相互配對的染色體按一定方式以雜交概率交換其部分基因，生成兩個新個體[10]。雜交概率主要控制種群新群體產生的速度，因為雜交操作進行的是基因重組，生成相對父代波動較大的基因。變異是遺傳算法中保持生物多樣性的一個重要途徑，也是對雜交過程可能丟失的某種遺傳基因進行修復和補充，可防止遺傳算法盡快收斂到局部最優解[10]。變異概率主要控制基因擾動，在實數編碼時更為明顯。

為了豐富種群的多樣性和加快搜索時間，在遺傳算法初期希望種群基因波動范圍較大和種群基因型豐富，能夠在搜索的種群里面快速的找到包含最優解的波形峰。而在遺傳算法后期，大多數的搜索點已經在包含最優解的波形峰的附近，但是沒有找到最優解，在這時希望種群能夠在波形峰小范圍內波動來搜索到最優解。即在遺傳算法初期雜交概率大變異概率小，后期雜交概率小變異概率大。概率Pc和Pm表達式為：

(8)

(9)

Pc1和Pm1是雜交概率和變異概率的初始值，i是當前進化次數，n是最高進化次數，count是累積最優解不改變的次數。當count為0的時候，Pc為Pc1，Pm為Pm1/2，雜交概率Pc大變異概率Pm小。當count變大時，雜交概率Pc變小變異概率Pm變大。

本文的目的是求攝像機的內參數，即目標函數f(fu,fv,u0,v0)，適應度為1/f(fu,fv,u0,v0)，種群大小為N，進化代數為n。

改進遺傳算法的具體步驟：

1)初始化相關變量，如Pc1、Pm1、N、n等。

2)初始化種群。用上面改進了的初始化方法生成N個個體。

3)采用改進了的輪盤賭選擇算法，選擇出N/2個個體作為父代。

4)采用實數編碼的方式對種群進行編碼，按照公式(8)計算自適應的雜交概率Pc，在Pc的控制下進行雜交，將兩個父代進行雜交操作生成兩個新的基因。進行完整個雜交操作將參數N/2個新基因。

5)進行變異操作。按照公式(9)計算自適應變異概率Pm，在Pm的控制下選擇新產生的基因進行變異操作，最后產生N/2個新基因。

6)計算目前種群個體的適應度，按照適應度從大到小排序。目前種群個體一共有3N/2個個體，包含步驟3)中未被選中的N/2個個體、步驟4)中雜交產生的N/2個新個體、步驟5)中變異產生的N/2個新個體。按照適應度排序選擇前N個個體作為新一代種群。

7)選出新一代種群里面最優的個體和上一代最優個體進行比較，較優者替換新一代最差的個體。

8)計算新一代種群的總適應度、平均適應度。保存本代最優個體，判斷本代最優個體是否和上一代相同，若相同count=count+1，若不同count不變。

9)終止條件判斷。當前運行代數i>n迭代終止；若i

3 實驗與分析

為了驗證本文說提出的攝像機自標定方法的魯棒性和實用性，進行了仿真實驗和真實圖像的實驗。

3.1 仿真實驗

在仿真實驗中，用Matlab合成攝像機仿真圖像并加入高斯噪聲。攝像機的內參數設置為fu=500,fv=500,u0=250,v0=250。讓仿真攝像機生成一個10*20的點陣并改變其外參數，從而得到不同的圖像。為了和真實圖像相似，所以在仿真實驗中向圖像點加上了高斯噪聲。設置了6種不同的噪聲等級，在每種噪聲等級下進行了20次實驗。其中設定初始時種群規模N=50,進化代數n=200,雜交概率pc1=0.01，變異概率Pm1=0.01。對實驗結果進行了分析，實驗統計結果如圖1所示。

圖1 fv的平均誤差

圖2 fu的平均誤差

圖3 u0的平均誤差

圖4 v0的平均誤差

通過圖1～圖4可以看出。本文改進的遺傳算法求得的攝像機內參數比傳統的遺傳算法平均誤差要小。另外隨著噪聲級的不斷增高，本文算法求得的攝像機各內參數平均誤差變化率逐漸變小。證明基于改進遺傳算法求得的攝像機內參數準確度更高，魯棒性更好。

3.2 真實實驗

除了仿真實驗外，還進行了真實圖像實驗。用攝像機拍攝實驗標定塊的一組圖片，對圖5兩張不同角度的圖像進行了標定。

圖5 標定塊圖像序列

其中設定初始時種群規模N=50,進化代數n=200,雜交概率pc1=0.6，變異概率pm1=0.01。自標定結果如表1所示。

表1 對圖5的標定結果

由表1可以看出，本文的標定算法和Matlab標定工具箱的標定結果更相近，這證明了本算法的準確性。

從網站http://www.robots.ox.ac.uk/～vgg/data/data-mview.html下載文獻[11]和[12]使用的Valbonne church圖像用于本實驗。其中設定初始時種群規模N=50,進化代數n=300,雜交概率Pc1=0.6，變異概率Pm1=0.01。自標定結果如表2所示。

圖6 Valbome church圖像

fufvu0v0文獻[11]682.84682.84255.99383.92文獻[12]670.46667.21245.23355.54本文算法675.81678.15249.31369.21

與文獻[11]和[12]的實驗結果相比，本文的實驗結果與其十分接近，可以證明本算法具有較高的魯棒性。

4 結論

本文提出的基于改進遺傳算法的攝像機自標定方法，能夠較好地避免傳統遺傳算法出現的過早收斂和陷入局部最優解的現象。本文的方法和基于傳統遺傳算法的攝像機自標定方法進行實驗對比，其準確性較好，魯棒性較高，是一種簡單易用的自標定方法。