??? 摘? 要： 在研究三步搜索法工作原理的基礎(chǔ)上，根據(jù)運(yùn)動(dòng)矢量的特點(diǎn)，提出一種基于運(yùn)動(dòng)矢量方向預(yù)測的三步搜索法。結(jié)合圖像配準(zhǔn)融合，將此方法應(yīng)用于巖心掃描成像系統(tǒng)中。實(shí)驗(yàn)表明，改進(jìn)后的算法效率明顯提高，魯棒性增強(qiáng)。
??? 關(guān)鍵詞： 運(yùn)動(dòng)矢量檢測? 匹配準(zhǔn)則? 方向預(yù)測? 巖心掃描成像
?
??? 油氣勘探獲取的巖心樣本是石油地質(zhì)研究的寶貴歷史資料。為了資料的長久保存和資源共享，研制了巖心掃描儀，將巖心掃描成圖像后，存入圖文數(shù)據(jù)庫。由于巖心比較長，需要進(jìn)行分段掃描，然后將多段圖像拼接起來以進(jìn)行整幅圖像顯示及分析。拼接的關(guān)鍵是圖像配準(zhǔn)，而圖像配準(zhǔn)多采用匹配方法。
??? 在圖像匹配中，目前研究最多的是基于塊匹配(Block Matching，BM)的快速搜索法。塊匹配搜索法中精度最高的是全搜索(Full Search，F(xiàn)S)法。它對給定搜索區(qū)域的所有點(diǎn)進(jìn)行搜索，因此計(jì)算量相當(dāng)大。為減少計(jì)算量，提出了許多快速搜索算法。具有代表性的算法有二維對數(shù)搜索(2D-Logarithmic Search，LOGS)法、三步搜索(Three Step Search，TSS)法、對偶搜索(Conjugate Search，CS)法、鉆石搜索(Diamond Search，DS)法等。其中TSS算法是最為常用的算法之一，但它不足之處是計(jì)算量大，每一步都要搜索它的8個(gè)鄰域。為減少運(yùn)算量，提高運(yùn)算速度，本文提出一種運(yùn)動(dòng)矢量方向預(yù)測的三步搜索法。該方法是在每一步搜索后，預(yù)測下一步的搜索方向，下一步只在預(yù)測的方向附近搜索。實(shí)驗(yàn)表明，這種方法速度快，匹配精度高。下面分別介紹TSS算法的基本原理、本文提出的算法及該算法在巖心掃描成像中的應(yīng)用。
1? 三步搜索法的基本原理
??? 三步搜索法采用由粗到細(xì)的搜索模式，其基本原理圖如圖1所示，圖中1、2、3代表搜索步驟。(1)以圖像上的某點(diǎn)(如O點(diǎn))為中心，按步長為4取周圍的8個(gè)鄰域點(diǎn)，如圖中標(biāo)號(hào)為1的點(diǎn)(包括A點(diǎn))。樣本中心分別與9個(gè)點(diǎn)對齊，進(jìn)行圖像與樣本的匹配，搜索最優(yōu)匹配點(diǎn)。(2)以最優(yōu)匹配點(diǎn)(如A點(diǎn))為中心，按步長2取周圍的8個(gè)鄰域點(diǎn)，如圖中標(biāo)號(hào)為2的點(diǎn)（包括B點(diǎn)）。類似第1步，搜索8個(gè)點(diǎn)中的最優(yōu)匹配點(diǎn)。(3)又以最優(yōu)匹配點(diǎn)(如B點(diǎn))為中心，按步長為1取周圍的8個(gè)鄰域點(diǎn)，如圖中標(biāo)號(hào)為3點(diǎn)（包括C點(diǎn)）。類似第2步，搜索8個(gè)點(diǎn)中的最優(yōu)匹配點(diǎn)。最后的最優(yōu)匹配點(diǎn)，即C點(diǎn)就是搜索的結(jié)果。
?
??? 最佳匹配可以用均方誤差MSE(Mean-Square Err)最小作為匹配依據(jù)。
????
??? 其中m=n=t
??? 從上式可知，均方誤差的計(jì)算量比較大。為此，可采用平均絕對誤差MAD(Mean of the Absolute Difference)最小作為匹配依據(jù)。
??? 
??? 其中m=n=t，dx，dy分別是模板的移動(dòng)矢量在X和Y方向上的矢量，t值一般取16。
??? 由三步搜索算法原理和匹配準(zhǔn)則可以看出，該算法的運(yùn)算量較大。為此，提出一種運(yùn)動(dòng)矢量方向預(yù)測的三步搜索法。
2? 運(yùn)動(dòng)矢量方向預(yù)測三步搜索法
2.1 方向預(yù)測搜索思想
??? 在獲取巖心圖像的過程中，臺(tái)架上可放1m左右的巖心，而掃描儀的掃描長度為20cm，因此需將1m的巖心分成5次進(jìn)行掃描。第1段20cm的圖像掃描完后，通過精確控制步進(jìn)電機(jī)帶動(dòng)掃描頭回退2mm，再進(jìn)行第2段掃描。當(dāng)?shù)?段掃描完成時(shí)，就和第1段自動(dòng)拼接起來，同樣的道理，掃描第3段前先回退2mm，第3段掃描完成時(shí)就自動(dòng)和前面的圖像拼接起來。第4段、第5段依此類推。不難發(fā)現(xiàn)，要拼接的圖像的重疊區(qū)總是位于前一幅圖像的右邊。掃描儀掃描頭的運(yùn)動(dòng)示意圖如圖2所示。
?
2.2 運(yùn)動(dòng)矢量方向預(yù)測三步搜索法原理
??? 對柱狀巖心分成平動(dòng)掃描和滾動(dòng)掃描，對破碎巖心可以平動(dòng)掃描。無論哪一種掃描方式，其掃描頭的運(yùn)動(dòng)規(guī)律都相同，即相鄰2幅圖像都具有一定的重疊區(qū)域，而且后一幅圖像和前一幅圖像在時(shí)間上和空間上具有很強(qiáng)的相關(guān)性。在進(jìn)行圖像拼接時(shí)若按傳統(tǒng)的三步搜索法，每一步至少要對周圍的8個(gè)鄰域進(jìn)行搜索，而在實(shí)際情況中，拼接時(shí)的最佳位置只可能出現(xiàn)在右方。因此在搜索時(shí)可以不用考慮左邊的情況。由于圖像可能因?yàn)槟撤N原因在Y方向上有較大的偏移量，所以第1步搜索時(shí)應(yīng)該對第2幅圖像的重疊區(qū)進(jìn)行全面搜索。方向預(yù)測三步搜索法示意圖如圖3所示。該過程須對標(biāo)號(hào)為1的點(diǎn)進(jìn)行全面搜索；第2步和第3步則只需對主導(dǎo)方向附近的點(diǎn)進(jìn)行搜索，具體步驟如下：
?
??? (1)假設(shè)樣本模板對以某點(diǎn)為中心的重疊區(qū)搜索后找出的最佳匹配點(diǎn)為A1，然后對未搜索的相鄰區(qū)域進(jìn)行三步搜索，找出最佳匹配點(diǎn)B1，重復(fù)上面的步驟，對剩余重疊區(qū)進(jìn)行搜索，每次找出一個(gè)最佳匹配點(diǎn)，依次記為A1、B1、C1……直到重疊區(qū)域搜索完為止。然后比較A1、B1、C1……各點(diǎn)對應(yīng)的MAD值，找出最小的MAD，設(shè)其對應(yīng)點(diǎn)為P1，則該點(diǎn)為第1步所得最優(yōu)點(diǎn)，其矢量方向?yàn)橄虏剿阉鞯闹鲗?dǎo)方向。
??? (2)若P1點(diǎn)對應(yīng)矢量方向角為θ1，則以該點(diǎn)為中心，步長減半，并以θ1為主導(dǎo)方向，在其某一偏角△θ范圍內(nèi)進(jìn)行搜索，如圖3所示。第2步只需要搜索3點(diǎn)，即腳標(biāo)為2的3點(diǎn)，其中一點(diǎn)是主導(dǎo)方向上的點(diǎn)，另外2點(diǎn)是偏角為△θ范圍內(nèi)的2點(diǎn)。假設(shè)第2步搜索到的最佳匹配點(diǎn)為P2，且在主導(dǎo)方向以下，即在θ1-△θ內(nèi)，則P2為第2步所得最優(yōu)點(diǎn)，其矢量方向?yàn)榈?步搜索的主導(dǎo)方向。
??? (3)若P2點(diǎn)對應(yīng)矢量方向角為θ2，同第2步類似，以P2為中心，步長減半，同時(shí)以θ2為主導(dǎo)方向角，在步長范圍內(nèi)對同一△θ偏角內(nèi)的點(diǎn)進(jìn)行搜索。第3步只需要對腳標(biāo)為3的點(diǎn)搜索，根據(jù)MAD值最小找出最佳匹配位置點(diǎn)P3。這樣P3就是拼接時(shí)模板的最佳中心位置。至此，算法結(jié)束。
2.3 方向偏角的確定
??? 算法的關(guān)鍵是方向預(yù)測，通過第一次全面搜索，可以初步知道，最小MAD點(diǎn)對應(yīng)矢量的方向?yàn)橹鲗?dǎo)方向，即最佳匹配位置大致就在該方向上。具體位置則需要在初定位的基礎(chǔ)上進(jìn)一步精確定位。通過多次實(shí)踐驗(yàn)證，在該系統(tǒng)中最佳中心點(diǎn)總是出現(xiàn)在以主導(dǎo)方向?yàn)榛鶞?zhǔn)、△θ=±15°的范圍內(nèi)，因此搜索范圍就可以大大減少。若第1步進(jìn)行全搜索后得到的最優(yōu)點(diǎn)矢量方向即主導(dǎo)方向?yàn)?5°，則第2步就只需要搜索θ=45°±15°的范圍。在這一范圍內(nèi)第2步搜索到的最優(yōu)點(diǎn)矢量方向若為30°，則第3步就只需搜索θ=30°±15°的范圍。由于步長在不斷縮小，因此在有限的步長和角度范圍內(nèi)所搜索的點(diǎn)大大減少。需要注意的是：如果在主導(dǎo)方向的偏角范圍內(nèi)沒有目標(biāo)搜索點(diǎn)，則采用四舍五入的方式對其臨近點(diǎn)進(jìn)行搜索即可。
3? 巖心掃描成像中的圖像配準(zhǔn)及融合
3.1 樣本模板的選擇
??? 樣本模板包含的信息量越大，在搜索最佳匹配時(shí)效果越好。因此應(yīng)盡可能選擇包含信息量較大的特征區(qū)域，最常用的方法是濾波。由于“背景”信號(hào)大多為低通信號(hào)，而特征突出的信號(hào)多為高通信號(hào)，因此通過一個(gè)高通濾波器對第1幅圖像重疊區(qū)域進(jìn)行濾波，找出其特征區(qū)域，然后截取一塊作為模板，這樣便可以用高斯高通濾波器(GHPF)進(jìn)行濾波，根據(jù)局部熵最大的原則選取模板?？梢栽O(shè)定一個(gè)閥值，若熵大于閥值，模板取小一點(diǎn)；若小于閥值，模板適當(dāng)取大一點(diǎn)。
3.2 配準(zhǔn)及融合的基本算法
??? 經(jīng)過上述步驟找到最佳匹配點(diǎn)以后，將2幅圖像合成一幅圖像。由于拍攝時(shí)照度或曝光的不均勻，在重疊區(qū)域如果單純地取第1幅圖像或第2幅圖像的象素值，則可能導(dǎo)致拼接處產(chǎn)生明顯階梯，或者使重疊處圖像變得模糊。如何使拼接處平滑過渡，BURT曾提出了用Laplacian錐的辦法來解決，也有人用小波分解進(jìn)行邊界處理，但這些算法運(yùn)算量都較大。如果取2幅圖像象素平均值，則從算法上講比較簡單，但效果不理想。本文采用漸進(jìn)漸出的方法，即在重疊部分由第1幅圖像漸漸過渡到第2幅圖像。假設(shè)有一漸變因子d(0
??? 其中f1(x，y)代表第1幅圖像，f2(x，y)代表第2幅圖像，f(x，y)代表結(jié)果圖像，灰度圖像可以直接利用此公式計(jì)算。對于R、G、B 3種顏色的彩色圖像可以分別利用此公式計(jì)算。
4? 實(shí)驗(yàn)結(jié)果與討論
??? 掃描得到2幅相鄰的待拼接圖像如圖4所示。可以看出，2幅圖像有一定的重疊區(qū)域。應(yīng)用上述算法，拼接后圖像如圖5所示。
?
?
??? 文中算法是基于一種運(yùn)動(dòng)的思想，即對在時(shí)間和空間上相互關(guān)聯(lián)的圖像進(jìn)行預(yù)測搜索，找出其最佳匹配位置。在充分利用傳統(tǒng)的三步搜索法的基礎(chǔ)上，對其算法進(jìn)行改進(jìn)，并將其應(yīng)用到巖心掃描儀中進(jìn)行圖像拼接。在匹配準(zhǔn)則上選擇最小MAD對應(yīng)點(diǎn)為模板中心點(diǎn)的匹配點(diǎn)，盡量避免了乘除運(yùn)算，使計(jì)算量大為減少，因此拼接速度快、效率高、實(shí)用性強(qiáng)，而且經(jīng)過拼接融合后圖像基本上沒有明顯的裂痕。該算法的不足之處是算法的第1步仍然要進(jìn)行全面搜索，如何將第1步也進(jìn)行簡化，值得進(jìn)一步探討。
參考文獻(xiàn)
1?? 鐘力，胡曉峰.重疊圖像拼接算法.中國圖像圖形學(xué)報(bào)，1998；(5)
2?? 沈建國，戴勇剛.基于局部熵差的柵格地圖拼接方法.華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002；(12)
3?? Li R，Zeng B，Liou M.A New Three-step Search Algorithm for Block Motion Etimation.IEEE Trans CASVT，1994；4(8)
4?? Ghanbari M.The Cross_search Algorithm for Motion Estimation.IEEE Trans Commun，1990；38(7)
5?? Wang L F.Panorama Mosaix and Optimization.Application?Research of Computers，1999；(6)