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