基于二倍體顯性機(jī)制的透視變換矩陣參數(shù)優(yōu)化

方 樹(shù)，陳賢富

(中國(guó)科學(xué)技術(shù)大學(xué) 微電子學(xué)院，安徽 合肥 230027)

0 引言

隨著科學(xué)技術(shù)的飛速發(fā)展，人們對(duì)全景圖像在不同場(chǎng)合應(yīng)用涌現(xiàn)出新的要求：安防監(jiān)控、無(wú)人機(jī)技術(shù)、VR技術(shù)等，圖像拼接技術(shù)也得到越來(lái)越廣泛的運(yùn)用[1-2]。而圖像拼接技術(shù)的重中之重在于圖像的配準(zhǔn)。圖像配準(zhǔn)是對(duì)圖像的重疊區(qū)域進(jìn)行對(duì)齊的過(guò)程，首先是圖像特征點(diǎn)檢測(cè)，其次是完成特征點(diǎn)的匹配，再根據(jù)匹配點(diǎn)對(duì)的集合計(jì)算出透視變換矩陣的各個(gè)參數(shù)，最后通過(guò)透視變換矩陣完成圖像中的坐標(biāo)變換。其中變換矩陣參數(shù)的精度很大程度上影響了圖像配準(zhǔn)效果。

傳統(tǒng)的方法采用RANSAC(Random Sample Consensus)算法，該算法通過(guò)大量迭代的方式，能夠從包含大量局外點(diǎn)的數(shù)據(jù)集中估計(jì)出較高精度的參數(shù)。但圖像配準(zhǔn)中的匹配點(diǎn)對(duì)的集合經(jīng)過(guò)嚴(yán)格篩選，僅存在較少的局外點(diǎn)集，且如果設(shè)置迭代上限，則該算法迭代得到的結(jié)果可能不是最優(yōu)解，甚至為錯(cuò)誤解。

遺傳算法作為一種全局優(yōu)化搜索方法，使用簡(jiǎn)單，魯棒性強(qiáng)，易于并行化，因而應(yīng)用研究已經(jīng)從初期的組合優(yōu)化求解擴(kuò)展到許多高新工程化的應(yīng)用方面[3]。但傳統(tǒng)遺傳算法局部搜索能力差，容易陷入局部最優(yōu)解，本文針對(duì)這些不足，采用基于二倍體顯性機(jī)制的DNA遺傳算法來(lái)優(yōu)化透視變換矩陣中的參數(shù)。

1 圖像變換的基本模型

圖像配準(zhǔn)也稱(chēng)圖像對(duì)齊，該過(guò)程通過(guò)對(duì)待拼接圖像的特征點(diǎn)的提取和匹配，完成對(duì)圖像重疊區(qū)域的對(duì)齊[4]。在圖像配準(zhǔn)過(guò)程中，通常需要確定變換模型，而常見(jiàn)的模型有剛體變換、仿射變換、透視變換等。變換矩陣A的一般表達(dá)式為：

(1)

1.1 剛體變換

剛體變換主要是針對(duì)旋轉(zhuǎn)和平移進(jìn)行的一種變換。其特性是圖像中的兩點(diǎn)在變換后歐氏距離保持不變，且兩條直線的平行或垂直等這類(lèi)關(guān)系保持不變。在二維空間中，點(diǎn)(u，v)通過(guò)剛體變換至點(diǎn)(X，Y)的表達(dá)式為：

(2)

其中θ為旋轉(zhuǎn)角度，[tx,ty]為平移變量。

1.2 仿射變換

仿射變換主要針對(duì)平移、旋轉(zhuǎn)、縮放、剪切等進(jìn)行變換。仿射變換后直線與直線間的平行關(guān)系保持不變，但直線的長(zhǎng)度和角度都發(fā)生了改變。在二維空間中，點(diǎn)(u，v)通過(guò)仿射變換至點(diǎn)(X，Y)的表達(dá)式為：

(3)

其中[tx,ty]為平移變量，參數(shù)ai反映的是圖像旋轉(zhuǎn)、縮放等變化。

1.3 透視變換

透視變換是中心投影的射影變換，是將空間坐標(biāo)系下的三維物體或?qū)ο筠D(zhuǎn)變?yōu)槎S圖像的過(guò)程。在變換過(guò)程中，圖像中的直線映射到另一幅圖像中仍為直線，但平行關(guān)系基本不保持。二維圖像空間中，點(diǎn)(u，v)通過(guò)透視變換至點(diǎn)(X，Y)的表達(dá)式為：

(4)

令

(5)

其中變換參數(shù)ai(i=1,2,…,8)是依賴(lài)于場(chǎng)景和圖像的變換參數(shù)。變換后的圖像坐標(biāo)(x，y)分別為X/W和Y/W，即：

(6)

(7)

圖像拼接中，因變換矩陣H中8個(gè)參數(shù)都參與了變換，故圖像配準(zhǔn)多采用透視變換模型。如圖1、圖2所示：首先需要將待變換圖像通過(guò)透視變換矩陣變換至基準(zhǔn)圖像的平面，然后將兩幅位于同一平面的圖像進(jìn)行拼接。圖1為變換后的圖像，圖2為拼接后圖像。

圖1 透視變換后的圖像

圖2 拼接后的圖像

將圖2細(xì)節(jié)處放大后會(huì)發(fā)現(xiàn)，有很多拼接重合區(qū)域尚未對(duì)齊，如圖3、圖4所示(兩幅圖像顏色差異是因?yàn)榕臄z角度的變化導(dǎo)致光照色差的變化)。

圖3 尚未對(duì)齊處1

圖4 尚未對(duì)齊處2

基于上述拼接效果欠佳的現(xiàn)象，分析其直接原因?yàn)橥敢曌儞Q矩陣參數(shù)不夠精確，導(dǎo)致匹配圖中的各像素點(diǎn)沒(méi)有精確變換到基準(zhǔn)圖的相應(yīng)位置。

2 基于二倍體顯性機(jī)制的遺傳算法優(yōu)化

2.1 優(yōu)化模型

由1.3節(jié)可知，透視變換矩陣中參數(shù)精度上的誤差直接影響到拼接效果，因此如何尋找到最優(yōu)的矩陣H成為了圖像配準(zhǔn)的關(guān)鍵。

遺傳算法(Genetic Algorithm,GA)作為一種全局優(yōu)化搜索方法，起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究，最先是由Michgan大學(xué)的John Holland于1975年提出的[5]。遺傳算法的實(shí)現(xiàn)包括參數(shù)的編碼解碼、初始化種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作等。算法遵循“適者生存”的自然界法則，根據(jù)每一代適應(yīng)度值判別種群優(yōu)劣從而篩除劣勢(shì)種群，完成種群的進(jìn)化過(guò)程。

但是傳統(tǒng)遺傳算法的局部搜索能力較差，容易出現(xiàn)早熟收斂的現(xiàn)象[6]。參考文獻(xiàn)[7-8]中提出了一種基于二倍體顯性機(jī)制的DNA遺傳算法，該算法根據(jù)染色體的特有結(jié)構(gòu)，提出了最優(yōu)個(gè)體保存，重新優(yōu)化了種群之間的遺傳操作，在與傳統(tǒng)遺傳算法的對(duì)比中發(fā)現(xiàn)，基于二倍體顯性機(jī)制的遺傳算法能夠有效抑制早熟收斂現(xiàn)象，防止算法陷入局部最優(yōu)解。本文將基于此算法完成對(duì)透視變換矩陣參數(shù)的優(yōu)化。

2.2 基于二倍體顯性機(jī)制的遺傳算法

(1)交叉操作。參考文獻(xiàn)[7]中提出的基于二倍體顯性機(jī)制的遺傳算法，相較于傳統(tǒng)遺傳算法對(duì)交叉操作進(jìn)行了相應(yīng)的改進(jìn)。傳統(tǒng)遺傳算法中所有交叉方式的共同之處在于均繼承了兩父串的相同基因，而二倍體顯性遺傳算子在繼承父代同型等位基因的同時(shí)，對(duì)雜型等位基因按照“與”和“或”的方式進(jìn)行處理。例如，兩父串為：

F1：0100101101

F2：1101110100

則由“與”和“或”交叉操作后產(chǎn)生的兩子串分別為：

C1：0100100100

C2：1101111101

(2)變異操作。變異操作是對(duì)矩陣參數(shù)以變異概率p隨機(jī)指定的某一位或某幾位的值作變異運(yùn)算。

(3)挑選子代再變異。參考文獻(xiàn)[8]中為了提高局部隨機(jī)搜索能力，維持種群的多樣性，提出了挑選子代再變異操作。該操作將適應(yīng)度較高和較低的兩個(gè)子代作為遺傳對(duì)象來(lái)更新種群，有效抑制了適應(yīng)度低個(gè)體中優(yōu)秀基因的丟失，從而擴(kuò)大了局部搜索范圍，且維持了種群多樣性。

(4)適應(yīng)度函數(shù)設(shè)計(jì)。本文需預(yù)先獲取若干篩選后的匹配點(diǎn)對(duì)，利用所有匹配點(diǎn)對(duì)中數(shù)據(jù)測(cè)試透視變換模型，計(jì)算匹配點(diǎn)對(duì)中坐標(biāo)標(biāo)準(zhǔn)值與坐標(biāo)計(jì)算值的歐氏距離。適應(yīng)度Fitness表達(dá)式如下：

(8)

其中，(xi，yi)和(x′i，y′i)(i=1,2,…，n)為兩幅圖像特征點(diǎn)的匹配點(diǎn)對(duì)坐標(biāo)，a1,a2，…，a8為式(5)中透視變換矩陣參數(shù)。

根據(jù)以上步驟，制定的基于二倍體顯性機(jī)制的算法優(yōu)化流程圖如圖5所示。

圖5 基于二倍體顯性機(jī)制的遺傳算法流程圖

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

為了驗(yàn)證基于二倍體顯性機(jī)制的遺傳算法對(duì)透視變換矩陣參數(shù)的優(yōu)化方案，本文采用了0/1編碼方式對(duì)優(yōu)化問(wèn)題進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)環(huán)境為Windows 10 64位操作系統(tǒng)，使用Visio Studio 2013，采用C++語(yǔ)言編碼實(shí)現(xiàn)。實(shí)驗(yàn)中設(shè)置控制參數(shù)最大遺傳代數(shù)為400，選取交叉概率為0.8，變異概率為0.15，種群規(guī)模為100，染色體長(zhǎng)度為30，優(yōu)化目標(biāo)是獲取最優(yōu)透視變換矩陣參數(shù)，使得圖1和圖2能夠較好地完成拼接。進(jìn)化代數(shù)與適應(yīng)度函數(shù)的關(guān)系如圖6所示，其中橫坐標(biāo)表示為進(jìn)化代數(shù)；為使折線圖呈上升趨勢(shì)，縱坐標(biāo)表示為適應(yīng)度函數(shù)值的倒數(shù)，其中適應(yīng)度函數(shù)值為所有對(duì)應(yīng)像素坐標(biāo)之間的歐氏距離和。

圖6 適應(yīng)度圖

由圖6可知，本方案能以較快的速度達(dá)到局部最優(yōu)解，僅出現(xiàn)少量局部最優(yōu)的過(guò)渡，當(dāng)進(jìn)化至160代附近時(shí)尋求到透視變換矩陣參數(shù)的最優(yōu)解，得到透視矩陣為：

H=

(9)

基于優(yōu)化后的透視變換矩陣，重新對(duì)圖像進(jìn)行透視變換和圖像拼接，拼接后圖像如圖7所示，細(xì)節(jié)效果如圖8、圖9所示。

圖7 優(yōu)化后的矩陣拼接的圖像

圖8 優(yōu)化后的細(xì)節(jié)處1

圖9 優(yōu)化后的細(xì)節(jié)處2

從圖8、9可以看出，在基于二倍體顯性機(jī)制的透視變換矩陣參數(shù)優(yōu)化后，圖像的細(xì)節(jié)部分相較于優(yōu)化之前有明顯的改善，重合區(qū)域能夠較好銜接，整體拼接效果也趨于完善。

4 結(jié)束語(yǔ)

本文提出了基于二倍體顯性機(jī)制的透視變化矩陣參數(shù)優(yōu)化方案，在傳統(tǒng)的遺傳算法方案中引進(jìn)了“與”、“或”的交叉方式和子代再變異的遺傳操作，使得整個(gè)方案能夠較快、較準(zhǔn)確地獲得全局最優(yōu)解。經(jīng)試驗(yàn)表明，本方案完成了矩陣參數(shù)的優(yōu)化操作，進(jìn)而改善了圖像拼接效果。

但本方案的效果與完美拼接尚存在一定差距。分析其主要原因在于兩幅圖的匹配點(diǎn)對(duì)經(jīng)篩選后仍存在誤差，導(dǎo)致未能精確求解適應(yīng)度函數(shù)。后續(xù)將繼續(xù)研究匹配點(diǎn)對(duì)篩選的問(wèn)題，并將該改進(jìn)方案應(yīng)用到多路視頻拼接上。