基于改進(jìn)遺傳算法的攝像機(jī)自標(biāo)定方法

(西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽(yáng) 621010)

0 引言

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

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

直接求解Kruppa方程的方法是一個(gè)非線性問(wèn)題。可以利用一些優(yōu)化算法對(duì)Kruppa方程所提供的代價(jià)函數(shù)進(jìn)行優(yōu)化。傳統(tǒng)的基于遺傳算法的攝像機(jī)自標(biāo)定方法參數(shù)優(yōu)化過(guò)程中，易出現(xiàn)過(guò)早收斂、停滯現(xiàn)象和解易陷入局部最優(yōu)的問(wèn)題。因此，針對(duì)傳統(tǒng)方法中出現(xiàn)的上述問(wèn)題，本文提出了一種改進(jìn)的基于遺傳算法的攝像機(jī)自標(biāo)定方法。

1 算法原理

1.1 投影模型

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

m?K[R|t]X#

(1)

1.2 基礎(chǔ)矩陣和Kruppa方程

從兩不同的視點(diǎn)獲得的同一場(chǎng)景的兩幅圖像，它們之間存在著一定的約束關(guān)系，這就是對(duì)極幾何關(guān)系?；A(chǔ)矩陣F是對(duì)極幾何關(guān)系的代數(shù)表達(dá)。根據(jù)攝像機(jī)與圖像之間的關(guān)系，F(xiàn)augeras、Luong和Maybank等人提出可用Kruppa方程表示為(具體推導(dǎo)方法可參閱文獻(xiàn)[6])：

(2)

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

(3)

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

(4)

(5)

(6)

設(shè)目標(biāo)函數(shù)為:

f(fu,fv,u0,v0)=

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

(7)

目標(biāo)函數(shù)f的值最小或趨近為0時(shí)，C即為所求的值。

2 基于改進(jìn)的遺傳算法的攝像機(jī)自標(biāo)定

遺傳算法是受達(dá)爾文進(jìn)化論的啟發(fā)，通過(guò)模擬自然界和生物進(jìn)化過(guò)程而被提出的用來(lái)解決優(yōu)化問(wèn)題的有效方法，是一種啟發(fā)式的搜索方法，也稱(chēng)進(jìn)化算法[8]。傳統(tǒng)的遺傳算法操作盲目無(wú)方向，所需要的收斂時(shí)間長(zhǎng)且最優(yōu)值容易早熟陷入局部最優(yōu)。

文獻(xiàn)[9]證明遺傳算法雜交過(guò)程的成熟化效應(yīng)是引起遺傳算法過(guò)早收斂的主因。過(guò)早收斂現(xiàn)象表現(xiàn)出來(lái)的特征是種群序列多樣性減少。為了使最優(yōu)值結(jié)果避免過(guò)早陷入最優(yōu)解，主要是要使種群序列多樣性高。

本文對(duì)遺傳算法做出了以下改進(jìn)：結(jié)合精英保留策略和隨機(jī)聯(lián)賽選擇算法作為初始化種群的方法；采用實(shí)數(shù)編碼；改進(jìn)輪盤(pán)賭選擇方法；采用自適應(yīng)雜交概率和變異概率方法。

2.1 編碼

本文采用實(shí)數(shù)編碼方式。傳統(tǒng)的遺傳算法一般采用二進(jìn)制編碼方式，二進(jìn)制編碼使用字符集(0，1)組成，雖然簡(jiǎn)單易用，但是存在Hamming懸崖問(wèn)題，在求解最優(yōu)化問(wèn)題時(shí)缺陷較大。實(shí)數(shù)編碼方式更接近問(wèn)題空間，在基因型空間和表現(xiàn)型空間中是一致的。

2.2 改進(jìn)的種群初始化

傳統(tǒng)的遺傳算法初始化是隨機(jī)生成個(gè)體。這種初始化的種群對(duì)于多峰病態(tài)復(fù)雜函數(shù)來(lái)說(shuō)，如后續(xù)遺傳算子操作不當(dāng)很容易使算法出現(xiàn)早熟現(xiàn)象。為了使搜索過(guò)程中更大概率找到真正最優(yōu)值的波峰，初始化時(shí)結(jié)合了隨機(jī)聯(lián)賽選擇算法和精英保留策略。初始化步驟：

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

2)計(jì)算N個(gè)個(gè)體的適應(yīng)度，對(duì)N個(gè)適應(yīng)度進(jìn)行從大到小到排序。

3)選取適應(yīng)度最大的那個(gè)個(gè)體作為初始種群的成員。

4)重復(fù)上面1)～3)的步驟直到初始種群滿(mǎn)員。

這樣初始種群本身就會(huì)具有較高的適應(yīng)度，而且種群內(nèi)個(gè)體處在最優(yōu)解所處波峰附近的概率就會(huì)大大地提高。

2.3 改進(jìn)的輪盤(pán)賭選擇算法

輪盤(pán)賭選擇算法選擇的依據(jù)是目標(biāo)函數(shù)的適應(yīng)度大小。在進(jìn)化初期通常會(huì)產(chǎn)生一些適應(yīng)度超常大的個(gè)體，這些異常大的個(gè)體被選擇的概率很大，它們會(huì)很大程度地控制選擇過(guò)程，造成種群的多樣性降低。因此，本文算法將每次被選擇的個(gè)體從總選擇序列中拿出，不在參與下一次選擇。

改進(jìn)的輪盤(pán)賭選擇步驟：

1)將種群全部個(gè)體的適應(yīng)度進(jìn)行從大到小排序，求得全部個(gè)體的適應(yīng)度總和S。

2)產(chǎn)生一個(gè)0～S之間的隨機(jī)數(shù)M。

3)從種群中編號(hào)為1的個(gè)體開(kāi)始，將其適應(yīng)度值與后面?zhèn)€體的適應(yīng)度值相加，直到累加的和大于M則停止。最后加進(jìn)去的個(gè)體即為被選擇出的父代。

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

這樣避免了哪些異常大的值會(huì)被多次選中，豐富了種群的多樣性。并且適應(yīng)度值異常大的值也不會(huì)被破壞，從而避免了進(jìn)化初期適應(yīng)度異常高個(gè)體處于局部最優(yōu)情況導(dǎo)致的算法收斂于局部最優(yōu)的情況。

2.4 自適應(yīng)的雜交和變異概率

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

為了豐富種群的多樣性和加快搜索時(shí)間，在遺傳算法初期希望種群基因波動(dòng)范圍較大和種群基因型豐富，能夠在搜索的種群里面快速的找到包含最優(yōu)解的波形峰。而在遺傳算法后期，大多數(shù)的搜索點(diǎn)已經(jīng)在包含最優(yōu)解的波形峰的附近，但是沒(méi)有找到最優(yōu)解，在這時(shí)希望種群能夠在波形峰小范圍內(nèi)波動(dòng)來(lái)搜索到最優(yōu)解。即在遺傳算法初期雜交概率大變異概率小，后期雜交概率小變異概率大。概率Pc和Pm表達(dá)式為：

(8)

(9)

Pc1和Pm1是雜交概率和變異概率的初始值，i是當(dāng)前進(jìn)化次數(shù)，n是最高進(jìn)化次數(shù)，count是累積最優(yōu)解不改變的次數(shù)。當(dāng)count為0的時(shí)候，Pc為Pc1，Pm為Pm1/2，雜交概率Pc大變異概率Pm小。當(dāng)count變大時(shí)，雜交概率Pc變小變異概率Pm變大。

本文的目的是求攝像機(jī)的內(nèi)參數(shù)，即目標(biāo)函數(shù)f(fu,fv,u0,v0)，適應(yīng)度為1/f(fu,fv,u0,v0)，種群大小為N，進(jìn)化代數(shù)為n。

改進(jìn)遺傳算法的具體步驟：

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

2)初始化種群。用上面改進(jìn)了的初始化方法生成N個(gè)個(gè)體。

3)采用改進(jìn)了的輪盤(pán)賭選擇算法，選擇出N/2個(gè)個(gè)體作為父代。

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

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

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

7)選出新一代種群里面最優(yōu)的個(gè)體和上一代最優(yōu)個(gè)體進(jìn)行比較，較優(yōu)者替換新一代最差的個(gè)體。

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

9)終止條件判斷。當(dāng)前運(yùn)行代數(shù)i>n迭代終止；若i

3 實(shí)驗(yàn)與分析

為了驗(yàn)證本文說(shuō)提出的攝像機(jī)自標(biāo)定方法的魯棒性和實(shí)用性，進(jìn)行了仿真實(shí)驗(yàn)和真實(shí)圖像的實(shí)驗(yàn)。

3.1 仿真實(shí)驗(yàn)

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

圖1 fv的平均誤差

圖2 fu的平均誤差

圖3 u0的平均誤差

圖4 v0的平均誤差

通過(guò)圖1～圖4可以看出。本文改進(jìn)的遺傳算法求得的攝像機(jī)內(nèi)參數(shù)比傳統(tǒng)的遺傳算法平均誤差要小。另外隨著噪聲級(jí)的不斷增高，本文算法求得的攝像機(jī)各內(nèi)參數(shù)平均誤差變化率逐漸變小。證明基于改進(jìn)遺傳算法求得的攝像機(jī)內(nèi)參數(shù)準(zhǔn)確度更高，魯棒性更好。

3.2 真實(shí)實(shí)驗(yàn)

除了仿真實(shí)驗(yàn)外，還進(jìn)行了真實(shí)圖像實(shí)驗(yàn)。用攝像機(jī)拍攝實(shí)驗(yàn)標(biāo)定塊的一組圖片，對(duì)圖5兩張不同角度的圖像進(jìn)行了標(biāo)定。

圖5 標(biāo)定塊圖像序列

其中設(shè)定初始時(shí)種群規(guī)模N=50,進(jìn)化代數(shù)n=200,雜交概率pc1=0.6，變異概率pm1=0.01。自標(biāo)定結(jié)果如表1所示。

表1 對(duì)圖5的標(biāo)定結(jié)果

由表1可以看出，本文的標(biāo)定算法和Matlab標(biāo)定工具箱的標(biāo)定結(jié)果更相近，這證明了本算法的準(zhǔn)確性。

從網(wǎng)站http://www.robots.ox.ac.uk/～vgg/data/data-mview.html下載文獻(xiàn)[11]和[12]使用的Valbonne church圖像用于本實(shí)驗(yàn)。其中設(shè)定初始時(shí)種群規(guī)模N=50,進(jìn)化代數(shù)n=300,雜交概率Pc1=0.6，變異概率Pm1=0.01。自標(biāo)定結(jié)果如表2所示。

圖6 Valbome church圖像

fufvu0v0文獻(xiàn)[11]682.84682.84255.99383.92文獻(xiàn)[12]670.46667.21245.23355.54本文算法675.81678.15249.31369.21

與文獻(xiàn)[11]和[12]的實(shí)驗(yàn)結(jié)果相比，本文的實(shí)驗(yàn)結(jié)果與其十分接近，可以證明本算法具有較高的魯棒性。

4 結(jié)論

本文提出的基于改進(jìn)遺傳算法的攝像機(jī)自標(biāo)定方法，能夠較好地避免傳統(tǒng)遺傳算法出現(xiàn)的過(guò)早收斂和陷入局部最優(yōu)解的現(xiàn)象。本文的方法和基于傳統(tǒng)遺傳算法的攝像機(jī)自標(biāo)定方法進(jìn)行實(shí)驗(yàn)對(duì)比，其準(zhǔn)確性較好，魯棒性較高，是一種簡(jiǎn)單易用的自標(biāo)定方法。