張曉慧

?

基于多目標優(yōu)化算法的圖像匹配

張曉慧

(阜陽職業(yè)技術(shù)學院，安徽 阜陽 236031)

作為計算機視覺和圖像處理領(lǐng)域的重要研究內(nèi)容，圖像匹配的主要目的是尋找圖形圖像之間的匹配關(guān)系。因為傳統(tǒng)的匹配方法主要是依靠點作為基本單元的一階匹配方法和依靠線作為基本單元的二階匹配方法，因此對采集特征點的選擇和匹配方法的優(yōu)化是很重要的。然而，基于局部圖像信息的這兩種方法的匹配效果不是很好，本文通過改進使用多目標優(yōu)化算法NSGA-II，設(shè)計實現(xiàn)一種新的高階圖匹配算法，通過設(shè)計相關(guān)的目標函數(shù)和遺傳算子，提取兩幅圖的特征，并在此基礎(chǔ)上確定特征點匹配關(guān)系。實踐表明，該方法在變形和噪聲存在的情況下，能夠正確匹配兩幅圖之間的特征點。

圖像匹配；特征；多目標；NSGA-II

1 引言

隨著計算機視覺的不斷發(fā)展，圖像匹配技術(shù)越來越受到人們的重視，其在很多科學技術(shù)領(lǐng)域中發(fā)揮著重要的作用，例如，目標追蹤、圖像分類或恢復(fù)、目標識別[1]、模型匹配[2]或?qū)捇€立體融合[3]。由于圖像在不同的時間、傳感器以及視角下所獲得的成像不同，對同一物體在圖像中所展示出來的幾何特性、光學特性、空間位置依然會有很大的不同，如果再考慮到噪聲、干擾等影響會讓圖像發(fā)生更大的差異，圖像匹配就是在這些不同之中尋找它們的相同點。NSGA-II算法是帶有精英策略的快速非支配排序算法，筆者從已經(jīng)提出的基于張量的高階圖匹配算法和現(xiàn)有的多目標優(yōu)化算法的結(jié)合出發(fā)，對圖像匹配算法進行探討和研究，改進出一種新的圖像匹配算法。

2 基于特征的圖像匹配方法

圖像匹配的過程一般可以分為圖像的輸入、預(yù)處理、特征提取、匹配、輸出等步驟，由于所采用的方法不盡相同，不同匹配方法的步驟會有很大不同，具體體現(xiàn)在圖像預(yù)處理的不同、圖像特征提取方法的不同以及匹配所用適應(yīng)度值計算方法的不同等，但它們的大致過程是一致的[4]。目前，國內(nèi)外對圖像匹配的研究重點在三個方面，即圖像匹配三要素：特征空間、相似性度量、搜索策略。

2.1 張量介紹

張量是一個矩陣的n維泛化。2維矩陣可以被表示為表格形式，而張量則可以被描述為n維超矩形表格形式，這樣一種張量的每一個元素都要被n個數(shù)索引：H={}。張量與向量可以通過不同的方式相乘，我們使用下面的公式表示：

式（2-2）

V是一個n維向量，A是一個n維張量，就好像一個矩陣和一個向量的乘積是一個向量一樣，一個n維張量與一個向量的乘積是n-1維的，同樣就像矩陣和向量的乘法有兩種方式一樣（向量分別在矩陣的左邊和右邊），張量和向量的乘法有n種不同的方式，標記符中的k表示我們按第k維相乘。

2.2 特征提取

本文重點研究的是基于圖像特征的匹配，點匹配算法是基于圖像特征的匹配算法中很重要的一部分，在各種特征中，特征點作為一種穩(wěn)定的、旋轉(zhuǎn)不變的、同時又能克服灰度反轉(zhuǎn)的特征參與到匹配過程中不僅可以減少計算量，同時又能夠不損失圖像的重要灰度信息，而且對于不相似的圖像還可以進行部分相似的匹配。

如果遇到了帶有尺度、旋轉(zhuǎn)、仿射變換的情況，傳統(tǒng)的以點或者點對為單元的匹配算法的準確率就會很低，針對這種問題，Olivier Duchenne和Francis Bach提出一種基于張量的高階匹配算法[5]，該算法使用了更高階的約束來建立兩套視覺特征之間的對應(yīng)關(guān)系，代替?zhèn)鹘y(tǒng)的點或點對的方法。

在本文中，我們使用3個點作為一個元組，即隨機從同一幅圖中取出3個點，然后利用這3個點做一個三角形，提取出這一個三角形的特征做為圖像特征。

圖1 特征三角形

如圖1所示，我們可以從三角形中提取到很多的特征作為圖像匹配的特征，例如通過提取三角形的三個內(nèi)角值，可以找到兩幅圖中的相似三角形，當圖像發(fā)生尺度和旋轉(zhuǎn)變換時，可以通過特征三角形的內(nèi)角值特征進行圖像匹配，為了簡化計算，我們可以使用內(nèi)角的正弦值代替角度值；通過提取三角形三條邊的比值作為特征，可以應(yīng)對圖像的仿射變換。在我們的實驗中，就是用三角形的內(nèi)角值和邊長比作為特征。

根據(jù)張量的計算公式，在這里我們可以定義一個新的目標函數(shù)：

在這個函數(shù)中，只有當點元組｛i,j,k｝和｛i,j,k｝匹配的時候，的值為1，此時，將添加到目標函數(shù)中，其它情況下，目標函數(shù)值都為0。

H代表一種相似測量方法，當點元組｛i,j,k｝和｛i,j,k｝相似的話，H的值就會很高，同樣，對于同一幅圖中的每一組點，每一個特征向量f,我們要重新定義H：

2.3 改進的稀疏張量計算方法

如果對于從圖中提取的每一個特征三角形，我們都需要計算與之對應(yīng)的特征三角形之間的張量值，這將會大大增加計算量和算法的復(fù)雜度。我們在這里使用一種改進的稀疏張量計算方法，通過省略掉不必要的張量計算，大大提高算法的效率。在我們的實驗中，我們使用一個高斯核函數(shù)：

所以，對我們選取的每一個點元組，找到σ范圍內(nèi)的近鄰點元組，實驗中我們使用ANN（近似最近鄰算法）尋找點元組的近似最近鄰，這種ANN算法是基于kd-trees搜尋近似最近鄰的。

然而，如果對全部點元組都使用ANN算法的話，這將是一個非常耗時的工作，所以，我們只取一部分點元組進行計算，這樣就可以減少計算，但是要注意不可取太少的點元組數(shù)目，因為當元組數(shù)目過少將會影響匹配效果。

然后，計算每一個特征三角形的標識符，并把它們存儲在kd-tree中，為了更高效的查找，對選中的三角形，我們這樣計算張量：

如果triangle(i,j,k)triangle(i,j,k)屬于triangle(i,j,k)的k個近似最近鄰的話，否則H為0。

基于ANN算法的高效計算張量方法：

input：圖像I1，I2和點集P1，P2；output：張量HH←空張量for each t∈P2產(chǎn)生的所有特征三角形 do f←computetupleFeature（t,I2）;endT ←computeANNtree(F);S ←選擇一些三角形在I1；for each s∈S do N←搜尋k個最近鄰（T , s）; for each n∈N do H(index(s),index(n))←相似度(特征值(s),特征值(n)); endend

3 圖像匹配的多目標設(shè)計方法

3.1 NSGA-II算法與圖像匹配問題的對應(yīng)關(guān)系

NSGA-II算法是以遺傳學為基礎(chǔ)的問題求解模型，下面給出生物遺傳概念在圖像匹配中的對應(yīng)關(guān)系，如下：

生物遺傳概念圖像匹配問題中的作用 個體可行解的編碼 適應(yīng)性目標函數(shù)值的大小 適者生存目標函數(shù)值越大的編碼被保留的機會越大 交配根據(jù)適應(yīng)度值選定的一組分配方案，通過交叉操作產(chǎn)生一組新個體的過程 變異編碼的某一分量發(fā)生變化的過程

3.2 圖像匹配的編碼解碼設(shè)計

NSGA-II算法中能夠操作的數(shù)據(jù)是經(jīng)過編碼后的基因，而不能是實際問題中的數(shù)據(jù)，所以我們必須先完成編碼工作，實現(xiàn)由問題空間（可能解空間）向遺傳空間（經(jīng)過編碼的個體組成的空間）的映射。編碼方式的不同對NSGA-II算法的操作有著很大的影響，好的編碼不僅能夠加速NSGA-II算法的收斂速度，而且能夠提高準確率。一般來說，使用最多的編碼方式是二進制編碼，但是在圖像匹配時選點數(shù)量比較多的時候，使用二進制編碼，基因串的位數(shù)會很長，進而影響到求解效率，因此本文采用十進制編碼。

1 2 3 ……… N

為了方便起見，這里我們假設(shè)分別從待匹配的兩幅圖中取n個特征點，并把這n個點進行排序，然后我們建立一個n維向量，這個n維向量里存儲的是從1到n這n個數(shù)字的一個排列組合，例如：

……

這里表示第i,j,k……n個特征點分別與第1,2,3……n個特征點分別是對應(yīng)匹配的。

3.3 適應(yīng)度值的計算

適應(yīng)度值是NSGA-II算法中的一個重要指標，我們就是通過這個指標進行下面的非支配排序以及選擇操作的，通常適應(yīng)度的計算就是我們的目標函數(shù)的計算，必須要求我們所需要的個體的適應(yīng)度值高，即越靠近最優(yōu)解的一些個體的適應(yīng)度值越高，而越偏離最優(yōu)解的個體的適應(yīng)度值越低。我們使用式（2-3）作為目標函數(shù)。

3.4 快速非支配排序

NSGA-II采用了快速非支配排序方法，對于每個個體i都設(shè)有以下兩個參數(shù)ni和si，ni為在種群中支配個體i的解個體的數(shù)量，s為被個體i所支配的解個體的集合。

①首先判斷所有個體的n值，并保存n=0的個體。

②對于每一個n=0的個體，就可以將它所支配的解集合s中的每一個個體k的n值減1，即去除掉能支配個體k的個體i。

③將n=0作為第一級非支配個體，這些個體是最優(yōu)面上的解，賦予這些個體一個相同的非支配序，它們只支配其它個體，但不被其他任何個體所支配，然后去除掉這些個體，對其它個體繼續(xù)進行非支配排序，然后分別給它們相應(yīng)的非支配序，直到所有的個體都被分級。

3.5 交叉操作

交叉操作的方法有很多種，比如單點交叉、多點交叉、洗牌交叉、均勻交叉等。本文采用的是兩點交叉，隨機找到染色體上的兩點位置，然后父母雙方這兩點位置之間的基因互換，這樣就會產(chǎn)生兩個新的子代個體。

但是，本文中，單純地使用這種交叉方式是有問題的，因為本文使用的編碼結(jié)構(gòu)，同一個基因在不同的位置處代表的意義是不同的，因而通過改變基因的位置可以生成新的染色體，然而本文使用的編碼結(jié)構(gòu)是有一定的約束條件的，那就是每一個基因位上的數(shù)字都互不相同。

如果只是簡單地使用兩點交叉，必然會導(dǎo)致某些新基因而有些基因位上的數(shù)字是相同的，為了解決這個問題，我們使用下面的方法：

13467952108 35796821410

我們假設(shè)將第4位到第8位之間的基因相互交換，即

13496821108 35767952410

然后我們遍歷這兩個新個體的第1位到第3位以及第9位到第10位的每一段基因，例如，第一個新個體的第1位基因與第8位基因相同，那么我們把第二位新個體的第8位的基因2賦給第一位新個體的第1位基因，即變?yōu)椋?/p>

23496821108

這時我們發(fā)現(xiàn)該個體的第1位基因與第7位基因相同，所以我們把第二位新個體的第7位基因賦值給第一位新個體的第1位基因，這時就變?yōu)椋?/p>

53496821108

這時我們發(fā)現(xiàn)第一位基因已經(jīng)是獨一無二的了，然后我們接著遍歷下一位基因。如此重復(fù)下去直到遍歷完所有的基因，我們就可以得到兩個滿足約束條件的新個體：

53496821107 31867952410

3.6 變異操作

變異的目的是充分挖掘出種群的多樣性，解決可能陷入局部最優(yōu)的問題。本文采用隨機變異策略，對每一個參與變異操作的個體，隨機地選取兩個基因位，然后把這兩個基因位的基因相互交換位置。

12345678910

假設(shè)第1位與第2位基因發(fā)生交換，即產(chǎn)生新個體：

21345678910

使用這種變異方式主要出于兩點考慮：一是因為本文的十進制編碼結(jié)構(gòu)，同一數(shù)值在不同的基因位所代表的意義不同，因此通過互換基因位的數(shù)值可以生成新的染色體；二是因為如果使用一般的變異算子，必然會引入新的不滿足約束條件的基因，就需要通過上述的遍歷來使每一個染色體都滿足約束條件，影響到算法的速度。

3.7 算法步驟

我們已經(jīng)分別介紹了計算張量和NSGA-II的步驟，那么只需要簡單的結(jié)合就可以作為我們的圖匹配的NSGA-II算法步驟，步驟如下：

input：張量H;output: 最優(yōu)解集；初始化種群；for 進化代數(shù)=1：max計算種群個體的目標函數(shù)值；對種群個體進行非支配排序；依照排序結(jié)果進行選擇、交叉、變異產(chǎn)生新一代種群；end

4 實驗結(jié)果及對比

為驗證算法的可行性和有效性，利用Matlab編程工具實現(xiàn)，仿真實驗在Intel(R) Core(TM) i5 2.67GHz、6GB內(nèi)存的計算機上進行，首先隨機產(chǎn)生一個點集（），對該點集進行平移、旋轉(zhuǎn)、尺度變換，并添加高斯噪聲產(chǎn)生第二個點集，然后對這兩個點集進行匹配。

圖2 冪迭代算法、遺傳算法、NSGA-II算法的比較

從圖2可以看出，隨著特征點的增加，冪迭代和遺傳算法的準確率都在降低，而與之相反的是，NSGA-II算法得到的結(jié)果依然很好。同時我們在利用真實照片來驗證算法的可行性，在圖像的匹配的過程中，特征點的選取是一個很關(guān)鍵的步驟，我們這里通過手工選點的方法，手動地從圖像中選取一些交點、角點等作為特征點。

圖3 仿射變換的房子圖片匹配

圖4 大小變換的吉他圖片匹配

我們可以看到實驗結(jié)果是很不錯的，這些特征點總是可以被正確地匹配。圖3所示的待匹配圖片僅包含仿射變換，從圖中可以看出，仿射變換破壞了單個特征點的屬性，并且破壞了特征點與特征點之間的相對位置屬性，利用特征三角形的幾何不變性，就能夠較好地識別出兩幅圖中對應(yīng)的特征點。圖4所示的待匹配圖片僅包含大小變換，從實驗結(jié)果可以看出，利用特征三角形可以非常好地識別出兩幅圖片中對應(yīng)特征點。圖5是從不同的取景角度獲得同一棟建筑的照片，其中包含了仿射變換、大小變換、平移變換等多種變換方式，從實驗結(jié)果來看，本文提出的算法依然能夠較好地應(yīng)用于多種變換交織的待匹配圖像。

5 結(jié)束語

將多目標遺傳算法NSGA-II引入到圖像匹配中，實現(xiàn)了基于多目標優(yōu)化算法的高階圖匹配，保證了經(jīng)過復(fù)雜變化的兩幅圖片之間高效、正確的匹配。

[1] A. Berg, T. Berg, and J. Malik,“Shape Matching and Object Recognition Using Low Distortion Correspondence,”Proc. IEEE Conf. Computer Vision Pattern Recognition,2005.

[2] M. Leordeanu and M. Hebert,“A Spectral Technique for Correspondence Problems Using Pairwise Constraints,”Proc.IEEE Int’l Conf. Computer Vision,2005.

[3] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories,”Proc. IEEE Conf. Computer Vision and Pattern Recognition,2006.

[4]公茂果,焦李成.進化多目標優(yōu)化算法研究[J].軟件學報，2009(2).

[5]崔海波.基于NSGA-Ⅱ的炮兵群火力分配問題研究[D].國防科技大學，2010.

[6] 阮宏博.基于遺傳算法的工程多目標優(yōu)化研究[D].大連理工大學,2007.

On the Image Matching Based on Multi-objective Optimization Algorithm

ZHANG Xiao-hui

(Fuyang Institute of Technology, Fuyang, Anhui 236031, China)

As an important part in the field of computer vision and image processing, the key objective of image matching is to find out the match relationship between graphics and images. Since the traditional matching method mainly depends on the point as one-order matching method of basic unit, and depends on line as two-order matching method of basic unit, it is important to optimize matching method and choose capturing feature points.

However, the matching of the two methods doesn’t work so well based on the local image information. The paper aims to design a new matching method of high-order image through using Multi-objective optimization algorithm NSGA-II, and to extract the features of images through design related objective function and the genetic operator, and to conform the matching relation of the feature points on this basis. The results show that the method correctly matches the feature points of the twographics in the presence of noise and transformation.

Image matching; Feature; Multi-objective;NSGA-II

TP

A

1672-4437(2017)03-0047-06

2017-03-07

安徽省高等學校省級質(zhì)量工程項目（2015tszy051）;安徽省高校自然科學研究重點項目 (KJ2016A563)。

張曉慧（1978-），女，安徽阜陽人，阜陽職業(yè)技術(shù)學院副教授，碩士，主要研究方向：圖像處理、多媒體技術(shù)。