黃 梅

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

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

黃 梅

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

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

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

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

1 RANSAC算法

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

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

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

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

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

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

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

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

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

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

2 M_RANSAC算法

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

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

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

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

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

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

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

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

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

M_RANSAC算法步驟如下:

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

圖1 風(fēng)景畫面

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

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

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

實(shí)驗(yàn)求出的模型為

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

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

圖2a和圖 2b這 2幅圖像,存在平移、旋轉(zhuǎn)、仿射的關(guān)系,提取特征點(diǎn)相對(duì)多,求出的模型也相對(duì)復(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ù)錯(cuò)誤率高(M變大),模型復(fù)雜時(shí)(一個(gè)數(shù)據(jù)檢驗(yàn)一個(gè)模型需要的平均時(shí)間為t3會(huì)變大),算法的時(shí)間差會(huì)變大,從而導(dǎo)致 RANSAC算法效率大幅度降低.圖 5為采用了M_RANSAC算法拼接的全景圖.

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

4 結(jié) 論

本文提出的一種高效的M_RANSAC算法,能快速地尋找模型參數(shù).當(dāng)原始數(shù)龐大、數(shù)據(jù)錯(cuò)誤率高、模型復(fù)雜時(shí),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]曹紅杏,柳稼航.基于角點(diǎn)變換矩陣的圖像拼接[J].計(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)鍵點(diǎn)檢測(cè)子的研究[J].浙江大學(xué)學(xué)報(bào):工學(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]仵建寧,郭寶龍,馮宗哲.一種基于興趣點(diǎn)匹配的圖像拼接方法[J].計(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級(jí)碩士研究生.