周遠(yuǎn),周玉生,劉權(quán),楊新宇

?

一種適用于圖像拼接的DSIFT算法研究

周遠(yuǎn),周玉生,劉權(quán),楊新宇

圖像拼接是指通過(guò)對(duì)現(xiàn)實(shí)中同一場(chǎng)景采集得到的兩個(gè)或多個(gè)圖像,通過(guò)變換使其拼接成一張完整圖像的過(guò)程[1]。Szeliski提出了不依賴于對(duì)圖像進(jìn)行水平采集的全景圖像拼接方案[2];Peleg提出了自適應(yīng)的圖像拼接模型[3];Chen提出了利用線形紋理匹配的圖像拼接算法,減少了計(jì)算時(shí)間,并且增強(qiáng)了抗干擾能力[4];Brown等提出了利用尺度不變特征提取算法進(jìn)行自動(dòng)圖像拼接[5];Mahesh使用可控Harris探測(cè)特征點(diǎn),提出了基于特征的圖像拼接方法[6]。華莉琴等提出了采用改進(jìn)SIFT算法及多視角的車型識(shí)別算法,保持了圖像識(shí)別的穩(wěn)定性,同時(shí)降低了處理時(shí)間開(kāi)銷[7]。

圖像拼接中最重要的一個(gè)步驟就是特征提取,特征提取算法的好壞直接決定拼接的質(zhì)量以及效率。SIFT(Scale Invariant Feature Transform)算法[8]是目前圖像處理領(lǐng)域特征檢測(cè)和匹配中最為有效的算法,它可以提取出魯棒性很強(qiáng)的尺度不變特征,但是該算法時(shí)間開(kāi)銷大,并且沒(méi)有考慮特征點(diǎn)的分布情況?；赟IFT算法改進(jìn)的CSIFT[9]和SURF算法[10]也存在問(wèn)題,CSIFT算法通過(guò)計(jì)算圖像的反射光譜模型增加了特征對(duì)光照變化的魯棒性,但是增加了計(jì)算開(kāi)銷;SURF算法雖然可以加快特征提取的速度,但是提取的特征點(diǎn)的信息量較少,而且對(duì)于尺度以及旋轉(zhuǎn)的魯棒性不夠強(qiáng)。

針對(duì)以上問(wèn)題,本文在SIFT特征提取階段進(jìn)行非極大值抑制,保留特征最明顯的極值作為特征點(diǎn),使SIFT特征點(diǎn)能夠離散分布。為了特征點(diǎn)的分布離散均勻化,本文在SIFT算法的空間極值檢測(cè)階段引入了一個(gè)滑動(dòng)窗口,利用這個(gè)窗口對(duì)搜索進(jìn)行一定的抑制。在高斯差分金字塔DOG的構(gòu)建過(guò)程中進(jìn)行關(guān)鍵點(diǎn)定位,保持了特征點(diǎn)的魯棒性。同時(shí),本文通過(guò)在特征提取前對(duì)圖像添加降采樣操作步驟,縮減圖像配準(zhǔn)的應(yīng)用圖像大小,在計(jì)算單應(yīng)矩陣前添加位置信息還原的步驟,從而在保證一定的圖像拼接質(zhì)量的前提下有效地降低了圖像配準(zhǔn)各個(gè)階段的時(shí)間開(kāi)銷。最后,通過(guò)對(duì)特征點(diǎn)分布情況、時(shí)間開(kāi)銷以及魯棒性進(jìn)行對(duì)比分析,充分驗(yàn)證了本文算法在圖像拼接方面的優(yōu)越性。

1 SIFT算法分析與圖像拼接流程設(shè)計(jì)

1.1 SIFT算法分析

SIFT算法是一種尺度不變特征提取算法,該算法對(duì)在不同時(shí)間或者視角下相同場(chǎng)景拍攝的圖像提取出穩(wěn)定的特征,而且這些特征對(duì)尺度縮放、旋轉(zhuǎn)以及亮度變化保持不變性,同時(shí)它對(duì)視角變換、仿射變換以及噪聲也具有一定的穩(wěn)定性。它在圖像的不變特征提取方面與傳統(tǒng)的Harris角點(diǎn)檢測(cè)[11]、SUSAN角點(diǎn)檢測(cè)[12]以及FAST角點(diǎn)檢測(cè)[13]等算法相比有著巨大的優(yōu)勢(shì)。此外,SIFT特征還具有獨(dú)特性和多量性,對(duì)于特征的描述信息豐富,SIFT描述已經(jīng)被證明是目前圖像處理領(lǐng)域魯棒性最強(qiáng)的局部不變特征描述符[14]。

SIFT算法也存在一些缺點(diǎn):首先是對(duì)于分辨率很低的模糊邊緣平滑圖像來(lái)說(shuō),提取的特征點(diǎn)過(guò)少;其次,SIFT算法計(jì)算開(kāi)銷十分大;再次,SIFT算法沒(méi)有利用到圖像的顏色信息,SIFT算法通常都是用以處理灰度圖像;最后,SIFT算法沒(méi)有考慮特征點(diǎn)的分布情況。

1.2 圖像拼接關(guān)鍵算法

圖1 改進(jìn)后的圖像拼接流程

基于特征的自動(dòng)圖像拼接可分為特征提取、特征匹配、單應(yīng)矩陣估計(jì)以及圖像融合等步驟,其中前3個(gè)步驟都屬于圖像配準(zhǔn)的相關(guān)內(nèi)容,如圖1所示。兩幅圖像進(jìn)行特征提取后變?yōu)榱藘蓚€(gè)特征點(diǎn)數(shù)組F1和F2,然后利用特征的鄰域梯度向量之間的歐式距離比值查找匹配點(diǎn),再引入K-D樹(shù)(K-Dimensional Tree)將查找的時(shí)間復(fù)雜度降為O(n1logn2),得到兩組相互匹配的特征點(diǎn)數(shù)組Fmatch1和Fmatch2,這兩個(gè)特征數(shù)組包含的特征數(shù)目相同,并且是一一對(duì)應(yīng)的。針對(duì)圖像拼接在不同階段使用特征點(diǎn)的不同信息的特性,可以對(duì)圖像配準(zhǔn)增加一個(gè)降采樣以及坐標(biāo)位置還原的流程,使特征提取階段使用降采樣后的圖像,而在進(jìn)行了特征點(diǎn)匹配后將匹配對(duì)的位置信息還原到原圖像中計(jì)算單應(yīng)矩陣,從而極大地減少了運(yùn)算量。

但是,此時(shí)的特征點(diǎn)數(shù)組并不是都完全匹配,特征點(diǎn)的篩選和單應(yīng)矩陣的估計(jì)采用RANSAC(RANdom SAmple Consensus)算法,在已知變換模型的前提下,從一組包含“局外點(diǎn)”的觀測(cè)數(shù)據(jù)中通過(guò)迭代的方式估計(jì)數(shù)學(xué)模型參數(shù),最后使用加權(quán)平均融合算法將配準(zhǔn)后的兩幅圖像融合到一幅圖像中。

降采樣后圖像的坐標(biāo)信息經(jīng)過(guò)相應(yīng)的坐標(biāo)變換可以還原到源圖像,雖然增加了降采樣和坐標(biāo)還原的步驟,但是這兩個(gè)步驟的時(shí)間開(kāi)銷幾乎可以忽略不計(jì),因此在開(kāi)銷不變的情況下,可保證最后拼接保留了源圖像的所有信息。

2 DSIFT算法

2.1 算法的提出

針對(duì)SIFT算法存在的不足,很多學(xué)者都提出了對(duì)SIFT算法的改進(jìn),但是現(xiàn)有的改進(jìn)方案大多是討論特征點(diǎn)的準(zhǔn)確性、可重復(fù)性、魯棒性和時(shí)間復(fù)雜度等,而忽略了特征分布這個(gè)因素。雖然特征點(diǎn)越多,獲取到的圖像特征信息就越多,但是在應(yīng)用到圖像拼接中時(shí)只要有效的特征點(diǎn)數(shù)量足夠完成變換矩陣的計(jì)算,多余的特征點(diǎn)有時(shí)甚至?xí)绊懫唇有ЧＲ虼?如果能在特征點(diǎn)提取階段就保證特征點(diǎn)的良好稀疏分布,并且其特征明顯的話,可以極大地提高配準(zhǔn)以及拼接效率。針對(duì)這一問(wèn)題,提出了一種適用于圖像拼接的離散尺度不變特征提取算法DSIFT(Discrete SIFT)算法。該算法與SIFT算法相比具有3個(gè)特點(diǎn):①保持SIFT特征對(duì)尺度縮放、旋轉(zhuǎn)以及亮度變化的不變性,對(duì)于視角變換、仿射變換以及噪聲也具有一定的穩(wěn)定性;②時(shí)間開(kāi)銷相對(duì)SIFT算法有一定的減少;③相對(duì)SIFT特征點(diǎn)來(lái)說(shuō),分布更加均勻,提取的特征點(diǎn)更適用于圖像拼接。

為了描述特征點(diǎn)的分布情況,引入離散度的概念來(lái)定義特征點(diǎn)分布的離散程度,令圖像中所有特征點(diǎn)構(gòu)成的集合為F,每一個(gè)特征用fi=(xi,yi,σi,θi,υi)表示,其中x、y表示特征點(diǎn)在圖像中的位置,σ表示特征所在的尺度,θ表示特征的方向,υ表示鄰域描述信息。由于在這里我們只是考慮特征的分布情況,只需要用到特征的空間分布信息而不需要尺度、方向、鄰域等其他信息,所以本節(jié)只是用特征的空間分布信息fi=(xi,yi),假設(shè)圖像中的特征點(diǎn)的數(shù)目為n,那么圖像中所有特征點(diǎn)離坐標(biāo)原點(diǎn)的平均距離為

(1)

為了描述離散程度,定義離散度為

(2)

對(duì)于一幅圖像中的特征點(diǎn)分布,離散度S越大,表明特征點(diǎn)的分布越離散越均勻;S越小,表明特征點(diǎn)的分布越密集越不均勻。

在檢驗(yàn)特征提取算法的魯棒性方面,通常使用重復(fù)率r進(jìn)行對(duì)比,重復(fù)率表示圖像在變換前后同一個(gè)位置出現(xiàn)相同特征數(shù)目與特征總數(shù)的比值

(3)

式中:Cor(F1,F2)表示兩組特征點(diǎn)之間能夠?qū)?yīng)上特征點(diǎn)對(duì)的數(shù)目;mea(n1,n2)表示對(duì)n1、n2取均值;mat(F1,F2)表示特征集合F1和F2之間特征匹配的對(duì)數(shù)。重復(fù)率越高,表明圖像在變換后能夠在同一位置檢測(cè)到同一特征的概率越大,對(duì)應(yīng)的特征提取算法的魯棒性也就越強(qiáng)。

2.2 算法的設(shè)計(jì)

在SIFT特征點(diǎn)的基礎(chǔ)上考慮其分布情況,要使SIFT特征點(diǎn)能夠離散分布,本文在特征提取階段進(jìn)行非極大值抑制(Non-maximum suppression),在一定的區(qū)域內(nèi)排除非極值,保留特征最明顯的極值作為特征點(diǎn),對(duì)SIFT算法的尺度空間極值檢測(cè)階段進(jìn)行改進(jìn),這里稱改進(jìn)后的算法為離散尺度不變特征提取DSIFT算法。

由圖2可知,在SIFT算法中,極值點(diǎn)的檢測(cè)是在高斯差分金字塔上遍歷所有點(diǎn),并將其與周圍的26個(gè)像素點(diǎn)進(jìn)行比較而得到的。為了特征點(diǎn)的分布離散均勻化,DSIFT算法在SIFT算法的空間極值檢測(cè)階段引入一個(gè)滑動(dòng)窗口,利用這個(gè)窗口對(duì)極值點(diǎn)的檢測(cè)進(jìn)行非極大值抑制。在DSIFT算法中,在要檢測(cè)的層上使用一個(gè)矩形窗口進(jìn)行移動(dòng),在窗口內(nèi)將每個(gè)點(diǎn)與其周圍的8個(gè)相鄰點(diǎn)進(jìn)行對(duì)比,若該點(diǎn)為極值點(diǎn),則將該點(diǎn)加入一個(gè)有序隊(duì)列中,然后將隊(duì)列中元素依次取出,與上下層共18個(gè)點(diǎn)進(jìn)行比較,若該點(diǎn)仍為極值點(diǎn),則將該點(diǎn)作為本窗口的特征點(diǎn)候選點(diǎn),按一定的間距將窗口移動(dòng)到下一個(gè)區(qū)域。通過(guò)這種操作,每個(gè)窗口內(nèi)至多有兩個(gè)特征點(diǎn)。

(a)SIFT算法 (b)DSIFT算法圖2 SIFT與DSIFT算法獲取極值點(diǎn)比較

用DSIFT算法進(jìn)行空間極值檢測(cè),該算法可以在一個(gè)圖像的高斯差分金字塔DOG中完成離散空間極值點(diǎn)的檢測(cè),在檢測(cè)空間離散分布的極值點(diǎn)后,也需要與SIFT算法一樣進(jìn)行關(guān)鍵點(diǎn)定位、確定特征點(diǎn)方向以及生成特征描述符等步驟,這些步驟都與SIFT算法相同,因此在保證了特征點(diǎn)離散分布的前提下,同時(shí)也保持了特征點(diǎn)的魯棒性。

如果在一個(gè)窗口內(nèi)能夠檢測(cè)到候選點(diǎn),那么這些特征點(diǎn)必然是窗口內(nèi)特征最明顯的局部極值點(diǎn),這是由有序隊(duì)列保證的,有序隊(duì)列的每個(gè)元素包括了特征點(diǎn)在高斯差分圖像所在的行r、列c以及像素值v3個(gè)信息,每個(gè)窗口包括了一個(gè)極大值有序隊(duì)列maxQueue與一個(gè)極小值有序隊(duì)列minQueue。以極大值有序隊(duì)列為例,加入隊(duì)列的所有元素按照像素值從大到小排列,這些元素在出隊(duì)的時(shí)候,也是按照從大到小的順序出隊(duì),然后進(jìn)行空間極值檢測(cè),與上下層的鄰居比較,一旦探測(cè)出這個(gè)元素不僅是本層的極大值點(diǎn),而且相對(duì)上下層鄰居也是極大值點(diǎn),那么選擇這個(gè)點(diǎn)作為本窗口內(nèi)的極大特征點(diǎn),相對(duì)還未出隊(duì)的元素來(lái)說(shuō),已經(jīng)選擇特征點(diǎn)的像素值最大,從而也是特征最為明顯的,這些未出隊(duì)的元素可以清空。通過(guò)移動(dòng)窗口,使得每個(gè)窗口內(nèi)出現(xiàn)的特征點(diǎn)數(shù)目限制在兩個(gè)以內(nèi),這樣的非極大值抑制方式就解決了特征點(diǎn)離散分布的問(wèn)題。

在DSIFT特征提取時(shí)間開(kāi)銷的問(wèn)題上,在尺度空間極值點(diǎn)檢測(cè)的過(guò)程中,最為耗時(shí)的是像素點(diǎn)比較的過(guò)程,假設(shè)在尺度σ(o,s)所在的高斯差分圖像的寬為w、高為h,那么該層利用SIFT算法進(jìn)行極值檢測(cè)需要比較的次數(shù)為52wh。假設(shè)引入的滑動(dòng)窗口的長(zhǎng)為a、寬為b,那么DSIFT算法進(jìn)行極值檢測(cè)需要比較的次數(shù)為(16+36c/ab)wh,c為一個(gè)取值較小的正整數(shù),實(shí)驗(yàn)表明通常取1～3。在DSIFT算法中,應(yīng)根據(jù)實(shí)際情況對(duì)窗口的大小進(jìn)行取值,窗口越大,需要比較的次數(shù)越少,對(duì)應(yīng)檢測(cè)到的極值也越少,越分散,應(yīng)根據(jù)實(shí)際情況對(duì)窗口的大小進(jìn)行取值。

3 實(shí)驗(yàn)對(duì)比分析

對(duì)DSIFT與SIFT算法進(jìn)行實(shí)驗(yàn)對(duì)比,證明DSIFT算法可以取得較SIFT算法更均勻的特征點(diǎn)分布,并且計(jì)算速度優(yōu)于SIFT算法,同時(shí)還保持了SIFT算法的旋轉(zhuǎn)、尺度、仿射等不變性。

3.1 特征點(diǎn)分布情況對(duì)比分析

對(duì)于特征點(diǎn)的分布情況這里采用離散度S進(jìn)行評(píng)價(jià),實(shí)驗(yàn)對(duì)象以Lena圖片為例,用SIFT算法對(duì)Lena圖像提取特征點(diǎn)時(shí),可以得到431個(gè)特征點(diǎn),特征點(diǎn)的分布情況如圖3a所示,特征點(diǎn)的離散度為90.21,用DSIFT算法處理得到圖3b,可以提取到330個(gè)特征點(diǎn),特征點(diǎn)的離散度為91.31,相對(duì)SIFT算法可以發(fā)現(xiàn),特征點(diǎn)分布更加均勻了。從圖3可以發(fā)現(xiàn),DSIFT特征點(diǎn)相對(duì)SIFT特征點(diǎn)在邊緣處幾乎沒(méi)有損失,但是在特征分布密集的區(qū)域(比如頭發(fā)、面部等區(qū)域)特征點(diǎn)分布更加稀疏均勻,這種特征點(diǎn)分布方式更加有利于特征之間的配準(zhǔn)。

(a)SIFT算法 (b)DSIFT算法圖3 SIFT與DSIFT算法特征分布情況

3.2 時(shí)間開(kāi)銷以及魯棒性對(duì)比分析

選取不同的圖像進(jìn)行旋轉(zhuǎn)、仿射(包含光照變化)以及尺度變換時(shí)算法效率以及魯棒性的比較,算法的效率用執(zhí)行時(shí)間t衡量,魯棒性用重復(fù)率r衡量。

基于圖4所示的圖像旋轉(zhuǎn)變化數(shù)據(jù)集測(cè)試效率和魯棒性,它包含9幅圖像,圖4a為一幅正常的大小為600×450的圖像,其他幾幅圖像分別對(duì)其旋轉(zhuǎn)10°、50°、70°等,旋轉(zhuǎn)后圖像保持原圖大小,以原圖為參考圖像,將其與每一幅旋轉(zhuǎn)圖像分別進(jìn)行對(duì)比。

從圖5a中可以看出,DSIFT算法特征提取的耗時(shí)少于SIFT算法,說(shuō)明DSIFT算法相比SIFT算法在提取特征點(diǎn)方面更加高效,其中特征提取耗時(shí)在90°和180°時(shí)達(dá)到低谷,是因?yàn)樵?0°和180°時(shí)沒(méi)有填充區(qū)域。將參考圖像分別與不同旋轉(zhuǎn)角度的圖像進(jìn)行匹配,計(jì)算得到重復(fù)率。從圖5b中可以看出,DSIFT算法的重復(fù)率與SIFT算法的重復(fù)率走勢(shì)相同,并且DSIFT算法的重復(fù)率略高于SIFT算法的,在圖像旋轉(zhuǎn)90°時(shí)達(dá)到最大,特征點(diǎn)的重復(fù)率通常都保持在35%以上。

(a)原圖 (b)旋轉(zhuǎn)10° (c)旋轉(zhuǎn)50°

(d)旋轉(zhuǎn)70° (e)旋轉(zhuǎn)90° (f)旋轉(zhuǎn)120°

(g)旋轉(zhuǎn)140° (h)旋轉(zhuǎn)160° (i)旋轉(zhuǎn)180°圖4 圖像旋轉(zhuǎn)變換數(shù)據(jù)集

(a)時(shí)間開(kāi)銷對(duì)比 (b)重復(fù)率對(duì)比圖5 DSIFT與SIFT算法旋轉(zhuǎn)變換魯棒性對(duì)比

基于圖6所示的圖像仿射變換數(shù)據(jù)集測(cè)試效率和魯棒性,它包含5幅圖像,對(duì)同一場(chǎng)景在不同視角拍攝的圖像,圖像之間光照強(qiáng)度不同,并且?guī)в幸欢ǖ姆律渥儞Q。

如圖7所示,對(duì)其在不同視角下拍攝的圖像進(jìn)行對(duì)比。將圖7a與圖7b對(duì)比可以看出,對(duì)于仿射變換,效率與重復(fù)率兩者基本是相反的走勢(shì),特征提取耗時(shí)越大,重復(fù)率越低,圖6c重復(fù)率最低,這是由于其相比參考圖像的視角變化最大。

(a)原圖 (b)仿射變換1 (c)仿射變換2

(d)仿射變換3 (e)仿射變換4圖6 圖像仿射變換數(shù)據(jù)集

(a)時(shí)間開(kāi)銷對(duì)比 (b)重復(fù)率對(duì)比圖7 DSIFT與SIFT算法仿射變換魯棒性對(duì)比

(a)原圖 (b)尺度變換1 (c)尺度變換2

(d)尺度變換3 (e)尺度變換4 (f)尺度變換5圖8 圖像尺度變換數(shù)據(jù)集

(a)時(shí)間開(kāi)銷對(duì)比 (b)重復(fù)率對(duì)比圖9 DSIFT與SIFT算法尺度變換魯棒性對(duì)比

基于圖8所示的圖像尺度變換數(shù)據(jù)集測(cè)試效率和魯棒性,圖8a是600×450正常拍攝圖像,其余幾幅分別是以不同的尺度對(duì)這幅圖像放大后采樣得到。

圖9表示了圖像在不同尺度時(shí)SIFT算法與DSIFT算法的執(zhí)行效率與特征重復(fù)率,從圖9b可以看出,隨著尺度差距的變大,特征的重復(fù)率越來(lái)越低。

從以上3組SIFT算法、DSIFT算法的效率與魯棒性實(shí)驗(yàn)對(duì)比中可以發(fā)現(xiàn),DSIFT算法的執(zhí)行效率總是高于SIFT算法的,并且對(duì)于不同的圖像變換,DSIFT算法的重復(fù)率也與SIFT算法基本相同,保證了DSIFT算法對(duì)這些變換的魯棒性。

3.3 拼接結(jié)果對(duì)比分析

為驗(yàn)證降采樣操作對(duì)拼接結(jié)果的影響,對(duì)兩幅大小為1 340×850的圖像分別按照改進(jìn)前后流程拼接,然后對(duì)比拼接結(jié)果。在使用改進(jìn)前的流程時(shí)可以對(duì)兩幅圖像分別提取到2 182和2 289個(gè)特征點(diǎn),其中能夠初步匹配的特征點(diǎn)對(duì)數(shù)目為424,特征點(diǎn)的分布情況以及匹配情況如圖10a所示,在進(jìn)行匹配對(duì)篩選后能夠匹配的點(diǎn)數(shù)目對(duì)為369,如圖10b所示。對(duì)于改進(jìn)的流程降采樣操作次數(shù)為2,分別可以提取到167和191個(gè)特征點(diǎn),特征點(diǎn)分布以及匹配情況如圖10c所示,經(jīng)過(guò)匹配篩選后能夠匹配的特征點(diǎn)對(duì)數(shù)目為20,如圖10d所示。對(duì)于兩種匹配情況,計(jì)算出的變換矩陣分別為

可以看出,兩個(gè)變換矩陣幾乎相同,說(shuō)明有效匹配點(diǎn)對(duì)只需要在一定的程度下都可以成功計(jì)算出單應(yīng)矩陣。圖10e分別為改進(jìn)前后的拼接結(jié)果,可以看出,兩種流程拼接的圖像也幾乎一樣,降采樣操作對(duì)圖像拼接質(zhì)量的影響可以忽略。

3.4 拼接耗時(shí)分析

對(duì)于分辨率較高的圖像,添加降采樣以及坐標(biāo)還原的操作對(duì)拼接的結(jié)果幾乎沒(méi)有影響。拼接由同一攝像機(jī)采集的6組不同場(chǎng)景的圖像,分析流程改進(jìn)對(duì)圖像拼接各個(gè)階段時(shí)間開(kāi)銷的影響,實(shí)驗(yàn)結(jié)果如圖11所示。如圖11a所示,直接對(duì)源圖像進(jìn)行特征提取是相當(dāng)耗時(shí)的,每降采樣一次,特征提取耗時(shí)變?yōu)樵瓉?lái)的1/4,這是因?yàn)榻挡蓸邮歉酎c(diǎn)采樣的;圖11b表示了在不同降采樣次數(shù)情況下利用K-D樹(shù)算法和BBF算法進(jìn)行特征匹配的時(shí)間對(duì)比,整個(gè)時(shí)間開(kāi)銷與特征點(diǎn)對(duì)的數(shù)目是成正相關(guān)的,但是相對(duì)特征提取來(lái)說(shuō),特征匹配耗時(shí)相對(duì)要少得多;圖11c表示了在不同降采樣次數(shù)情況下利用RANSAC算法對(duì)單應(yīng)矩陣進(jìn)行估計(jì)的時(shí)間開(kāi)銷。RANSAC算法的迭代次數(shù)與數(shù)據(jù)集的大小是呈超線性關(guān)系的,從柱狀圖上可以看出對(duì)源圖像進(jìn)行降采樣一次就可以有很明顯的效率提升;圖11d表示了降采樣次數(shù)不同時(shí),對(duì)兩幅圖像進(jìn)行拼接總耗時(shí)的對(duì)比,可以發(fā)現(xiàn)降采樣操作對(duì)拼接速度的提升相對(duì)其他改變一個(gè)單獨(dú)算法有優(yōu)勢(shì),而對(duì)原圖像進(jìn)行若干次降采樣并且采用坐標(biāo)還原操作對(duì)拼接的質(zhì)量并沒(méi)有明顯的影響。

(a)降采樣前特征點(diǎn)分布及特征匹配

(b)降采樣前計(jì)算單應(yīng)矩陣以及滿足矩陣的匹配點(diǎn)對(duì)

(c)降采樣2次后特征點(diǎn)分布及特征匹配

(d)降采樣2次后計(jì)算單應(yīng)矩陣以及滿足矩陣的匹配點(diǎn)對(duì)

(e)兩種不同流程的拼接結(jié)果圖10 圖像拼接流程改進(jìn)前后的實(shí)驗(yàn)結(jié)果

(a)特征提取耗時(shí)比較 (b)特征匹配耗時(shí)比較

(c)計(jì)算單應(yīng)矩陣耗時(shí)比較 (d)拼接總耗時(shí)比較圖11 不同降采樣次數(shù)下圖像拼接不同階段耗時(shí)分析

理論上兩幅圖像之間只要有效匹配點(diǎn)對(duì)數(shù)目大于4,那么就可以完成它們之間的拼接,在匹配點(diǎn)對(duì)數(shù)目大于8的情況下,RANSAC算法都可以成功估計(jì)出變換矩陣并且完成圖像的拼接,實(shí)際系統(tǒng)中降采樣的次數(shù)應(yīng)由源圖像的分辨率進(jìn)行決定,對(duì)于高分辨率的圖像可以進(jìn)行多次的降采樣步驟。

4 結(jié) 論

本文提出了一種基于DSIFT算法的圖像拼接技術(shù),針對(duì)SIFT算法沒(méi)有考慮特征點(diǎn)的分布情況,而且SIFT算法計(jì)算開(kāi)銷較大,本文通過(guò)在圖像的高斯差分金字塔中添加一個(gè)滑動(dòng)窗口,對(duì)極值點(diǎn)的選取進(jìn)行非極大值抑制,達(dá)到了特征點(diǎn)相對(duì)均勻分布的目的;利用DSIFT算法的尺度不變特性,在圖像拼接的流程中添加降采樣以及坐標(biāo)還原的操作,極大地縮減了拼接的時(shí)間開(kāi)銷。在高斯差分金字塔DOG的構(gòu)建過(guò)程中,與SIFT算法一樣進(jìn)行關(guān)鍵點(diǎn)定位,保持了特征點(diǎn)的魯棒性。本文在特征提取前對(duì)圖像添加降采樣操作步驟,在計(jì)算單應(yīng)矩陣前添加位置信息還原的步驟,在保證一定的圖像拼接質(zhì)量的前提下極大地降低了圖像配準(zhǔn)各個(gè)階段的時(shí)間開(kāi)銷。通過(guò)實(shí)驗(yàn)驗(yàn)證,DSIFT算法相對(duì)SIFT算法具有更加均勻的特征點(diǎn)分布,運(yùn)算速度更快,并且保持了SIFT算法較高的魯棒性不變,DSIFT算法相對(duì)SIFT算法更加適合應(yīng)用于圖像拼接。

[1] SZELISKI R. Image alignment and stitching: a tutorial [J]. Foundations and Trends in Computer Graphics and Vision, 2006, 2(1): 1-104.

[2] SZELISKI R, SHUM H Y. Creating full view panoramic image mosaics and environment maps [C]∥Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM, 1997: 251-258.

[3] PELEG S, ROUSSO B, RAV-ACHA A, et al. Mosaicing on adaptive manifolds [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22 (10): 1144-1154.

[4] CHEN Fang, ZHOU Yifang, ZHAO Binwen, et al. Novel algorithm for image mosaic using linear texture match [C]∥International Conference on Electronic Measurement & Instruments. Piscataway, NJ, USA: IEEE, 2011: 119-122.

[5] BROWN M, LOWE D G. Automatic panoramic image stitching using invariant features [J]. International Journal of Computer Vision, 2007, 74(1): 59-73.

[6] MAHESH, SUBRAMANYAM M V. Automatic image mosaic system using steerable Harris corner detector [C]∥Machine Vision and Image Processing. Piscataway, NJ, USA: IEEE, 2012: 87-91.

[7] 華莉琴, 許維, 王拓, 等, 采用改進(jìn)的尺度不變特征及多視角模型對(duì)車型識(shí)別 [J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(4): 92-99. HUA Liqin, XU Wei, WANG Tuo, et al. Vehicle recognition using improved sift and multi-view model [J]. Journal of Xi’an Jiaotong University, 2013, 47(4): 92-99.

[8] LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[9] ABDEL-HAKIM A E, FARAG A A. A SIFT descriptor with color invariant characteristics [C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2006: 1978-1983.

[10]BAY H, TUYTELAARS T, GOOL L V. Speeded up robust features [C]∥ Computer Vision-ECCV. Berlin, Germany: Springer, 2006: 404-417.

[11]HARRIS C, STEPHENS M. A combined corner and edge detector [C]∥Proceedings of the 4th Alvey Vision Conference. Piscataway, NJ, USA: IEEE, 1988: 147-151.

[12]SMITH S M, BRADY J M. SUSAN: a new approach to low level image processing [J]. International Journal of Computer Vision, 1997, 23(1): 45-78.

[13]ROSTEN E, DRUMMOND T. Machine learning for high-speed corner detection [C]∥ Computer Vision-ECCV. Berlin, Germany: Springer, 2006: 430-443.

[14]LUO Juan, GWUN O. A comparison of SIFT, PCA-SIFT and SURF [J]. International Journal of Image Processing, 2009, 3(4): 143-152.

(編輯 趙煒)

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

針對(duì)SIFT算法在分辨率很低的模糊邊緣平滑圖像中提取的特征點(diǎn)數(shù)量過(guò)少,而且沒(méi)有考慮特征點(diǎn)的分布情況、計(jì)算開(kāi)銷較大的問(wèn)題,提出了一種離散尺度不變特征提取DSIFT(Discrete SIFT)算法。該算法在空間極值檢測(cè)階段引入一個(gè)滑動(dòng)窗口,在窗口內(nèi)對(duì)極值點(diǎn)的檢測(cè)進(jìn)行非極大值抑制,使得特征點(diǎn)的分布相對(duì)均勻,運(yùn)算速度更快,并且保持了尺度、旋轉(zhuǎn)、仿射等不變性。在特征提取前添加了降采樣操作,在計(jì)算單應(yīng)矩陣前添加位置信息還原的步驟,在查找匹配點(diǎn)的過(guò)程中引入K-D樹(shù),以及在特征點(diǎn)的篩選和單應(yīng)矩陣的估計(jì)上采用RANSAC算法,都降低了圖像配準(zhǔn)各個(gè)階段的時(shí)間開(kāi)銷。最后,通過(guò)實(shí)驗(yàn)驗(yàn)證,DSFIT算法相對(duì)SIFT算法具有更加均勻的特征點(diǎn)分布,保持了較高的魯棒性,同時(shí),在保證一定圖像拼接質(zhì)量的前提下極大地降低了圖像配準(zhǔn)各個(gè)階段的時(shí)間開(kāi)銷。

圖像拼接;尺度不變特征提取算法;圖像配準(zhǔn);圖像融合

Research on a DSIFT Algorithm Applicable to Image Mosaicking

ZHOU Yuan,ZHOU Yusheng,LIU Quan,YANG Xinyu

(School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

In view of the fact that the SIFT algorithm extracts the feature points too little and ignores their distribution, and also has the problem of high computation cost, a discrete-scale-invariant feature extraction algorithm (discrete SIFT or DSIFT in short) is proposed. This algorithm introduces a sliding window on the space extreme test phase of the SIFT algorithm, implements non-maximum suppression for the extreme points detection inside the window, so that the feature points are distributed relatively even. In addition, this algorithm makes the calculation faster, and at the same time maintains the scale, rotation, and affinity invariant. In order to reduce the time overhead of the image registration in various stages, it adds a desampling operation before feature extraction and the operation of location information reversion before calculating the homographic matrix. And it also introducesK-Dimensional Tree in the process of searching matching points, and adopts RANSAC algorithm in the shifting of the feature points and estimation of homographic matrix. Finally, through experiment verification, it is found that the DSIFT algorithm has more uniform distribution of feature points than SIFT algorithm, and with high robustness. At the same time, on the premise of guaranteeing the quality of image mosaicking, the time overhead in various stages of image registration is greatly reduced.

image mosaicking; SIFT algorithm; image registration; image fusion

2014-12-29。 作者簡(jiǎn)介:周遠(yuǎn)(1982—),男,博士生;楊新宇(通信作者),男,教授,博士生導(dǎo)師。

時(shí)間:2015-07-10

http:∥www.cnki.net/kcms/detail/61.1069.T.20150710.1032.005.html

10.7652/xjtuxb201509015

TP391

A

0253-987X(2015)09-0084-07