黃 梅

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南?？?570228)

基于改進(jìn) RANSAC算法的圖像拼接技術(shù)

黃 梅

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南?？?570228)

針對傳統(tǒng) RANSAC算法在圖像拼接中效率低的問題,提出了一種解決該問題的新算法,即M_RANSAC算法.該方法首先通過 HARR IS算法提取 2幅圖像中的特征點,且在特征點匹配排序的基礎(chǔ)之上,根據(jù)數(shù)據(jù)錯誤率得出抽樣次數(shù),并采用雙閾值法進(jìn)行數(shù)據(jù)檢驗來提高算法效率.結(jié)果表明,M_RANSAC算法能有效地減少抽樣時間和數(shù)據(jù)檢驗時間,同時降低了誤矩陣的估算概率,提高了圖像拼接的效率.

RANSAC算法;圖像拼接;特征點匹配;抽樣次數(shù);數(shù)據(jù)檢驗

圖像拼接是將數(shù)張有部分重疊的圖像進(jìn)行無縫拼接,生成一張寬視角、高分辨的全景圖像.圖像拼接技術(shù)關(guān)鍵在于圖像配準(zhǔn)和算法效率,目前針對不同類型的圖像存在多種圖像配準(zhǔn)技術(shù),其中基于特征點的拼接技術(shù)是現(xiàn)在最常用的拼接方法之一.在基于特征的拼接技術(shù)中,尋求特征點對應(yīng)關(guān)系時需要計算變換矩陣,但實際上經(jīng)過提取、匹配和去偽得到的匹配點遠(yuǎn)遠(yuǎn)大于計算變換矩陣所需的匹配點對.利用RANSAC(random sampling consensus)算法,可估算出變換矩陣,但當(dāng)原始數(shù)據(jù)龐大、數(shù)據(jù)錯誤率高、估算模型復(fù)雜時,計算量會加大,效率會大幅度降低,針對這個問題,筆者提出了一種改進(jìn)的 RANSAC算法,M_RANSAC算法,可以有效地解決效率降低問題.

1 RANSAC算法

RANSAC算法[1]是一種參數(shù)估算方法,其基本思想是針對不同問題,設(shè)計不同目標(biāo)函數(shù),在原始數(shù)據(jù)集中隨機(jī)抽取M組抽樣,每一組抽樣的數(shù)據(jù)量根據(jù)目標(biāo)函數(shù)而定.用M組抽樣分別估算目標(biāo)函數(shù)參數(shù)初始值,再計算每一組的參數(shù)初始值所對應(yīng)的內(nèi)點 (滿足這一組參數(shù)初始值的數(shù)據(jù)點)和外點 (不滿足這一組參數(shù)初始值的數(shù)據(jù)點).統(tǒng)計每一組參數(shù)初始值的內(nèi)點數(shù),內(nèi)點數(shù)目越大,模型參數(shù)越好,最后根據(jù)一定的評選標(biāo)準(zhǔn),找出最優(yōu)目標(biāo)函數(shù)的參數(shù)初始值.下面給出估算變換矩陣的 RANSAC算法步驟:

Step 1 根據(jù) 2幅圖像存在的投影變換關(guān)系,確定一個變換函數(shù),本文采用的是射影變換[2-4],它符合平面目標(biāo)在不同視點、視角拍攝圖像之間的變換關(guān)系,2幅圖像對應(yīng)特征點滿足如下變換關(guān)系

Step 2 從特征點對集合 S中隨機(jī)反復(fù)的抽取一組數(shù)據(jù),每一組抽樣的樣本數(shù)為估算模型所需最小數(shù)據(jù)量,計算該組抽樣對應(yīng)的模型,本文采用的模型參數(shù)需要 4對匹配點;

Step 3 用集合 S所有的數(shù)據(jù)來檢驗?zāi)Ｐ?即進(jìn)行全數(shù)據(jù)檢驗,統(tǒng)計滿足該模型的內(nèi)點數(shù)量,以及內(nèi)點變換點和內(nèi)點匹配點的歐式距離之和,距離和公式如下

其中,num為滿足模型的內(nèi)點數(shù)量;

Step 4 根據(jù)內(nèi)點數(shù)量和歐式距離和來選擇模型參數(shù);

Step 5 重復(fù) Step2、3,直到選出滿足評選標(biāo)準(zhǔn)的模型,找出這個模型對應(yīng)的內(nèi)點,并用這些內(nèi)點計算出最終的模型參數(shù).

RANSAC算法中,為保證在一定的置信概率P下,在M次抽樣中至少有一組全是內(nèi)點,這就要求抽樣次數(shù)M足夠大,利用式(3),可得置信概率P、數(shù)據(jù)錯誤率ε(外點在原始數(shù)據(jù)中所占的比例)、抽樣數(shù)M和計算模型參數(shù)需要的最小數(shù)據(jù)量m之間的關(guān)系,即

從式(3)[5]可以得出,m,M,P和ε成指數(shù)關(guān)系,P不變時,M隨ε,m的變大而變大,當(dāng)抽樣數(shù)M變大,就有更多模型進(jìn)行全數(shù)據(jù)檢驗,所以當(dāng)原始數(shù)據(jù)量龐大、模型復(fù)雜、數(shù)據(jù)錯誤率高時,直接造成 RANSAC算法效率下降.

以上分析可知,提高 RANSAC算法效率,可從減少抽樣次數(shù)和減少模型數(shù)據(jù)檢驗時間方面來考慮.

2 M_RANSAC算法

2.1 抽樣次數(shù)在 RANSAC算法中,從原始數(shù)據(jù)集隨機(jī)反復(fù)抽取M組抽樣,直到滿足評選條件的模型被選出來,將原始數(shù)據(jù)集進(jìn)行排序,從質(zhì)量高的數(shù)據(jù)開始抽取,能更快地找到滿足評選標(biāo)準(zhǔn)的模型,從而大大減少抽樣次數(shù).

對原始數(shù)據(jù)集中的數(shù)據(jù)排序,要回到特征點匹配,在匹配過程中,不可避免地存在一些錯誤匹配的特征點對,這不僅造成了原始數(shù)據(jù)集會存在一定錯誤率,而且也造成了模型估算不準(zhǔn)確或抽樣次數(shù)增加.在特征點匹配過程中,將匹配點對按一定順序排序,使可信度高的匹配點對排在前面,即對原始數(shù)據(jù)集進(jìn)行了排序,再從質(zhì)量高的數(shù)據(jù)開始抽取,減少抽樣次數(shù).

式(4)為第i對特征點對的行標(biāo)的距離對值,等于第j對特征點對的行標(biāo)的距離對值;式(5)為第i對特征點對的列標(biāo)的距離對值,等于第j對特征點對的列標(biāo)的距離對值.即對于任意兩隊正確的匹配特征點對來說,對應(yīng)的坐標(biāo)都應(yīng)滿足式(4)和(5),因此可認(rèn)為,經(jīng)過特征點匹配和去除偽特征點后,正確的特征點對在集合中是占大多數(shù)的.那么,根據(jù)特征點對的距離對值來對特征點進(jìn)行排序.特征點對集合排序劃分步驟如下

Step 1 求出所有特征點對的距離對值,行標(biāo)的距離對值存在 distance_x矩陣中,列標(biāo)的距離對值存在 distance_y矩陣中;

Step 2 統(tǒng)計所有特征點對的距離對值的種類,并統(tǒng)計每一種類的數(shù)量,記錄屬于這一種類的特征點對,例如(distace_xi,distace_yi)為第i對特征點對的距離對值,如果這個距離對值在已出現(xiàn)的距離對值種類中,沒有與distace_xi,和distace_yi都相等的距離對值,則(distace_xi,distace_yi)為一種新的距離對值種類,如果在已出現(xiàn)的距離對值種類中,存在與distace_xi,和distace_yi都相等的距離對值,則在原有距離對值種類中數(shù)量加 1,并將記錄第i對特征點屬于這個種類的距離對值.

Step 3 按照種類數(shù)量多少進(jìn)行排序,假設(shè)得到的距離對值種類為n,那么就對特征點對集合S劃分為n個集合S1,S2,S3,…,Sn,第 1個集為數(shù)量最多的距離對值種類所對應(yīng)的特征點對集合S1,第 2個集合為數(shù)量第二多的種類所對應(yīng)的特征點對集合S2,以此類推.

排序后,將S1,S2,S3,…,Sn這n個集合重新劃分為m個新集合{S1},{S1,S2},{S1,S2,S3},…,{S1,S2,S3,…,Sn},并對這m個新劃分的集合設(shè)定m個遞增的數(shù)據(jù)錯誤率,{S1}的數(shù)據(jù)錯誤率最低,以此類推.根據(jù)式(3),可計算出不同錯誤率下的最大抽樣次數(shù).假設(shè){S1}的抽樣次數(shù)為M1,如果在M1次抽樣次數(shù)中沒有得到滿足評選條件的模型參數(shù),則將抽取范圍擴(kuò)到集合{S1,S2},抽樣次數(shù)為M2,以此類推,直到出現(xiàn)滿足評選條件的模型參數(shù).

2.2 數(shù)據(jù)檢驗時間在 RANSAC算法中,每一次迭代計算的變換矩陣模型都進(jìn)行了全數(shù)據(jù)檢驗,即數(shù)據(jù)集中的所有點都參與了模型檢驗.如果減少參與全數(shù)據(jù)檢驗的模型便可減少數(shù)據(jù)檢驗時間.根據(jù)上文將征點對集合S的劃分,可以在每次產(chǎn)生新的模型參數(shù)時,首先在進(jìn)行本次抽樣的質(zhì)量高的數(shù)據(jù)集合中進(jìn)行檢驗,假設(shè)為{S1,S2},如果這個模型的內(nèi)點比例超過了預(yù)先設(shè)置一個集合內(nèi)點比例B1(內(nèi)點數(shù)與取樣集合例如{S1,S2}中數(shù)據(jù)點數(shù)的比值)和集合歐式距離閾值T1,則這個模型可以參與全數(shù)據(jù)檢驗,否則丟棄這個模型,進(jìn)入下次抽樣.在原始數(shù)據(jù)龐大的情況下,可大大減少模型數(shù)據(jù)檢驗時間.

2.3 M_RANSAC算法的實現(xiàn)本文采取 HARR IS算法[6]提取不同尺度下的特征點[7-9],雙向歸一化方法[10-11]匹配特征點,循環(huán)閾值和比較特征點距離對值的方法[11]去除偽匹配點,得到特征點對集合S.

M_RANSAC算法步驟如下:

Step 1 將特征點對集合S按照距離對值種類的多少對特征點進(jìn)行排序劃分,劃分為n個集合S1,S2,S3,…,Sn.

Step 2 將S1,S2,S3,…,Sn這n個集合重新劃分為m個新集合{S1},{S1,S2},{S1,S2,S3},…,{S1,S2,S3,…,Sn},設(shè)定m個遞增的數(shù)據(jù)錯誤率,根據(jù)式(3)計算出不同錯誤率下每個集合的最大抽樣次數(shù)Mmax_i.

Step 3 從第i個集合中隨機(jī)抽取(i從 1開始,即從{S1}開始抽樣)4對匹配點,根據(jù)每組的抽樣數(shù)據(jù),計算模型參數(shù),集合抽樣數(shù)記為Mi,集合每迭代一次Mi加 1,當(dāng)集合抽樣數(shù)Mi大于第i個集合的最大抽樣次數(shù)Mmax_i時,i=i+1轉(zhuǎn)下個集合中開始抽樣,如果Mi≤Mmax_i則轉(zhuǎn)到 Step 4.

Step 4 計算模型參數(shù)在第i個集合中的內(nèi)點比例和內(nèi)點的歐式距離和,設(shè)定集合的內(nèi)點比例閾值為B1,集合的歐式距離和閾值為T1,如果內(nèi)點比例大于B1,并且內(nèi)點的歐式距離和小于T1,則轉(zhuǎn)到 Step 5,否則回到 Step 3,重新開始抽樣.

Step 5 對模型參數(shù)進(jìn)行全數(shù)據(jù)檢驗,設(shè)定全數(shù)據(jù)的內(nèi)點比例閾值為B2,全數(shù)據(jù)的歐式距離和閾值為T2,如果模型內(nèi)點比例大于B2,并且歐式距離和小于T2,則轉(zhuǎn)到 Step 6,如果不滿足,回到 Step 3,重新開始抽樣.

Step 6 利用選出的模型參數(shù),計算模型所有內(nèi)點,從而計算出最終的模型.

M_RANSAC算法在特征點排序劃分的基礎(chǔ)上,計算出不同錯誤率下最小抽樣次數(shù)減少了抽樣時間,并采用了預(yù)檢測法將參與全數(shù)據(jù)檢驗的模型減少,節(jié)省了大量數(shù)據(jù)檢驗時間.

3 實驗結(jié)果

驗證改進(jìn)后的算法效果,用 4幅圖像進(jìn)行 2組實驗,圖像如圖 1a,圖 1b,圖 2a,圖 2b.實驗條件:CPU Intel core i3 2.27 GHz、內(nèi)存 2 G、操作系統(tǒng)W indows 7、Matlab7.1.實驗數(shù)據(jù)來源:圖 1a和圖 1b來源于網(wǎng)絡(luò),分辨率為 525×350,圖 2a和圖 2b來源于云臺拍攝,分辨率為 533×400.

圖1 風(fēng)景畫面

圖2 海南大學(xué)教學(xué)樓

從圖 1a和 b可知,2幅圖關(guān)系簡單,求出模型也為簡單的平移模型.在模型相對簡單,原始數(shù)據(jù)較少時,從表 1可知算法效率上沒有太大區(qū)別

表1 風(fēng)景畫算法結(jié)果分析表

實驗求出的模型為

將圖 1a和圖 1b拼接成為圖 3.

圖3 風(fēng)景畫拼接結(jié)果圖

圖2a和圖 2b這 2幅圖像,存在平移、旋轉(zhuǎn)、仿射的關(guān)系,提取特征點相對多,求出的模型也相對復(fù)雜,從表 2中可知,在這種情況下,改進(jìn)后的算法比傳統(tǒng)算法效率高.

表2 海南大學(xué)教學(xué)樓算法結(jié)果分析表

求出的模型為

將圖 2a和 b拼接成為圖 4.

圖4 海南大學(xué)教學(xué)樓拼接結(jié)果圖

從(11)式知,當(dāng)情況變復(fù)雜,即原始數(shù)據(jù)龐大(SN變大),數(shù)據(jù)錯誤率高(M變大),模型復(fù)雜時(一個數(shù)據(jù)檢驗一個模型需要的平均時間為t3會變大),算法的時間差會變大,從而導(dǎo)致 RANSAC算法效率大幅度降低.圖 5為采用了M_RANSAC算法拼接的全景圖.

圖5 海南大學(xué)教學(xué)樓全景圖

4 結(jié) 論

本文提出的一種高效的M_RANSAC算法,能快速地尋找模型參數(shù).當(dāng)原始數(shù)龐大、數(shù)據(jù)錯誤率高、模型復(fù)雜時,M_RANSAC算法比傳統(tǒng) RANSAC算法穩(wěn)定,且能快速估算出模型參數(shù),其效率更高、更有效地提高了全景圖的拼接效率.

[1]MART IN A I,ROBERT C B.Random Samlpe Concesus:proceeding ofA Paradigm forModel Fittingwith Applications to Image Analysis and Automated Cartography[J].Communications of the ACM,1981,24(6):381-395.

[2]R I CHARD Z,HEUNG-YEUNG S.Creating FullView Panoramic ImageMosaics and EnvironmentMaps:the 24th annual conference on Computer graphics and interactive techniques,LosAngeles,August,3-8,1997[C].New York:ACM press/Addision-wesley publishing co,1997.

[3]曹紅杏,柳稼航.基于角點變換矩陣的圖像拼接[J].計算機(jī)應(yīng)用,2008,8(16):4536-4529.

[4]YAO Li,MA L I-zhuang.A Fast and Robust Image Stitching Algorithm:proceeding of the 6th World Congress on Intelligent Control and Automation,Dalian,Jun,21-23,2006[C].Dalian:[s.n.],2006.

[5]WEILi-fang,HUANGLin-lin,PAN Lin,et al.The Retinal ImageMosaicBased on Invariant Feature and Hierachical TransformationModels:proceeding of the 2nd International Congress on Image and Signal Processing,Tianjin,October 17-19,2009[C].Tianjin:[s.n.],2009.

[6]HARR IS C,STEPHENSM.A combined corner and edge detector:proceeding of the 4th Alvey vision conference,Manchester,August,31-Septemter,2,1988[C].Manchester:[s.n.],1998.

[7]程邦勝,唐孝威.Harris尺度不變性關(guān)鍵點檢測子的研究[J].浙江大學(xué)學(xué)報:工學(xué)版,2009,43(5):855-859.

[8]LOWED G.Disctinctive Image Features For m Scale-Invariant Keypoints[J].InternationalJournalof ComputerVison,2004,60(2):91-110.

[9]M IKOLAJCZYK K,SCHM ID C.Scale&Affine Invariant Interest PointDetectors[J].International Journal of ComputerVistion,2004,60(1):63-86

[10]ZITOVA B,FLUSSER J. Image registration methods:a survey[J]. Image and Vision Computing,2003,21(11):977-1000.

[11]仵建寧,郭寶龍,馮宗哲.一種基于興趣點匹配的圖像拼接方法[J].計算機(jī)應(yīng)用,2006,26(3):610-612.

I mageMosaicMethod Based on I mproved RANSAC

HUANGMei

(College of Infor mation Science and Technology,Hainan University,Haikou 570228,China)

Because of the disadvantages of the low efficiency of traditional RANSAC algorithm in image mosaic,a new algorithm,M_RANSAC algorithm,was proposed.Firstly,the feature points were extracted by HARR IS algorithm,then based on the sorting of thematching pairof feature points,the timesof random selectionwere obtained by the error rate of data and the data testingwere implemented by themethod of double threshold.The results indicated that this new algorithm,M_RANSAC algorithm,can efficiently decrease the time of the random selection and the date testing,reduce the likelihood of false matrix assessing at the same time,which can be applied in image mosaic successfully.

RANSAC algorithm;image mosaic;feature pointsmatching;sampling frequency;data testing

TP 391.41 < class="emphasis_bold">文獻(xiàn)標(biāo)志碼:A

A

1004-1729(2011)02-0172-06

2011-02-21

黃梅 (1987-),女,江西贛州人,海南大學(xué)信息科學(xué)技術(shù)學(xué)院 2008級碩士研究生.