利用多線程及改進(jìn)SSDA算法加快拼接速度

謝永勝，余正生

（杭州電子科技大學(xué)圖形圖像研究所，浙江杭州310018）

0 引 言

圖像配準(zhǔn)和圖像融合是圖像拼接［1］的兩個關(guān)鍵技術(shù)，圖像配準(zhǔn)是圖像融合的基礎(chǔ)，而且圖像配準(zhǔn)算法的計算量一般非常大，因此圖像拼接技術(shù)的發(fā)展很大程度上取決于圖像配準(zhǔn)技術(shù)的創(chuàng)新。圖像配準(zhǔn)在數(shù)字圖像領(lǐng)域已經(jīng)有很多研究成果。這一問題涉及到點(diǎn)對點(diǎn)的匹配，特征的提取等等方面。概述了圖像配準(zhǔn)技術(shù)的基本理論以及主要方法如文獻(xiàn)2，綜述了隨后10年的圖像配準(zhǔn)領(lǐng)域的相關(guān)方法如文獻(xiàn)3。配準(zhǔn)在圖像處理里應(yīng)該屬于一種比較基礎(chǔ)的技術(shù)，在某些特定的領(lǐng)域有著非常重要廣泛的應(yīng)用：比如計算機(jī)視覺處理［4］，醫(yī)學(xué)圖像處理［5］以及衛(wèi)星遙感領(lǐng)域［6］等等。正因?yàn)槿绱酥匾?，無論其配準(zhǔn)速度或配準(zhǔn)準(zhǔn)確率都在不斷地進(jìn)行著改進(jìn)?；诨叶鹊姆椒ū容^常用，但純粹基于灰度的拼接方法適應(yīng)性差，特別對于待配準(zhǔn)圖像的缺損方面要求很高。序列相似性檢測算法目前已有多種改進(jìn)，改進(jìn)后的算法大大提高了運(yùn)算速度，但由于速度的改進(jìn)往往會帶來準(zhǔn)確性的降低，而本文的改進(jìn)主要在于在淘汰非匹配點(diǎn)時對準(zhǔn)確性要求方面效果更佳，主要目的還是針對算法在保證高配準(zhǔn)精度條件下的對速度方面進(jìn)行改進(jìn)。

1 圖像配準(zhǔn)

基于圖像灰度相關(guān)的常用匹配方法為模板匹配，即一種對待匹配的象元以一定大小窗口的灰度陣列按某種或幾種相似性度量順次進(jìn)行搜索匹配的方法。見的相似性度量有以下幾種：

1.1 基于兩幅圖像灰度的平方差之和

計算模板和搜索子圖對應(yīng)灰度值之差的平方公式和：

該方法稱差和法，其中S，T分別代表圖像各個象素的灰度值，m，n代表各個象素的坐標(biāo)，其值最小者所對應(yīng)的位置（i，j）為最佳匹配位置，記錄其值。

1.2 序列相似度檢測

其基本思想是：如果窗口內(nèi)所有點(diǎn)被檢驗(yàn)完之前該誤差過早地達(dá)到預(yù)定的門限值，便認(rèn)為該窗位置不是匹配點(diǎn)，無須繼續(xù)檢驗(yàn)窗內(nèi)的剩余點(diǎn)，停止本次運(yùn)算，而轉(zhuǎn)向計算下一窗口位置，直到找到匹配點(diǎn)為止，記錄其值，從而省去大量的在非匹配位置處的無用運(yùn)算量。

1.3 互相關(guān)檢測

互相關(guān)檢測的思想是用到了概率和數(shù)理統(tǒng)計中相關(guān)系數(shù)的思想：

相關(guān)系數(shù)是0-1之間的一個數(shù)，其值越接近1說明量圖像越相似，所以，值最大者為最佳匹配點(diǎn)，同樣記錄其值（即等于 1），R（i，j）越大，模板與子圖 S（i，j）就越相似，（i，j）也就是要搜索的匹配點(diǎn)，同樣記錄其值。

2 圖像拼接

確定匹配點(diǎn)后，要確定整幅象素的值，如圖1所示。假設(shè)S點(diǎn)在矩形A中的坐標(biāo)為（Asx，AT），圖像左下角為坐標(biāo)原點(diǎn)。在矩形B中的坐標(biāo)為（Bsx，BT），AH、AWidth分別為矩形A的高度和寬度，BH、BWidth分別為矩形B的高度和寬度，則拼接后的圖像的高度和寬度為CH、Cwidth。部分流程如圖2所示。

圖1 拼接實(shí)例圖

圖2 拼接流程圖

3 算法改進(jìn)

基于圖像灰度方法雖然精確度較高，但是相應(yīng)的計算量也很大，實(shí)時性不高，并且受灰度圖像損傷程度影響較大，為了增加系統(tǒng)的實(shí)時性，適應(yīng)性，減少運(yùn)行時間，改進(jìn)的基本思想有：（1）修改算法，提高運(yùn)行速度；（2）多CPU線程并行編程技術(shù)；（3）引入仿射機(jī)制。

3.1 修改算法，提高程序運(yùn)行速度

對序列相似性檢測作進(jìn)一步的改進(jìn)，這本身是一種快速圖像匹配算法，但由于其閥值的單一性，所以可針對其閥值進(jìn)行算法修改。首先是定義誤差，閥值增值為Add，閥值的取值空間設(shè)定為Value［Min-Num…MaxNum］，設(shè)置訪問變量B［（M-N+1）（M-N+1）］為True，算法從W=Value［MinNum］開始循環(huán)，在子圖中隨即選取象素點(diǎn)，計算它同T中對應(yīng)點(diǎn)的誤差Error，然后把這點(diǎn)的差值同其他點(diǎn)對的差值累加起來，當(dāng)累加P次直到誤差超過Value［MinNum］則停止累加，并記下累加次數(shù)P。記下各累加次數(shù)點(diǎn)，找出W=Value［MinNum］這輪循環(huán)中累加次數(shù)最大點(diǎn)的值Max。淘汰W=Value［MinNum］這輪循環(huán)中累加次數(shù)點(diǎn)小于T的點(diǎn)，即將其B［］值設(shè)為False。通過對T的不同取值，分別進(jìn)行50次配準(zhǔn)（選取的兩幅圖像大小分別為256×56，35×44經(jīng)過選取多幅圖像進(jìn)行測試也有類似的結(jié)論），來查看正確的配準(zhǔn)次數(shù)，如表1所示：

表1 配準(zhǔn)正確率比較

3.2 利用多CPU線程并行編程技術(shù)

提出了把多線程技術(shù)應(yīng)用于圖像配準(zhǔn)，并且已經(jīng)在平臺下用VC++6.0加以實(shí)現(xiàn)，而硬件條件是采用英特爾酷睿2雙核處理器，在一定程度上提高計算機(jī)資源的利用率，降低系統(tǒng)運(yùn)行時間。在模板匹配的過程中，模板在待匹配圖像上一個象素一個象素的進(jìn)行遍歷匹配，可以認(rèn)為各象素間的匹配是沒有任何關(guān)系的，基于此，提出將待匹配圖像分為上下兩個部分，創(chuàng)建兩個線程，分別將兩個部分在不同的線程中進(jìn)行遍歷匹配。主線程必須等待輔助線程都完成后，然后將各個輔助線程得出的誤差進(jìn)行相加，這樣可以得這趟循環(huán)總的誤差，然后用前述算法進(jìn)行處理。最后綜合兩個線程的遍歷結(jié)果，再通過主線程找出最佳匹配點(diǎn)。

3.3 引入仿射機(jī)制，用最小二乘法進(jìn)行擬合

一旦將共同區(qū)域確定下來之后，那就需要通過仿射變換公式將映射參數(shù)計算出來。2D空間中，變換公式為：

引入最小二乘法，用多個配準(zhǔn)點(diǎn)找出最優(yōu)參數(shù)解。假設(shè)W為A，B兩圖中特征點(diǎn)組成的矩陣，X′，Y′分別為B圖中特征點(diǎn)的X，Y坐標(biāo)組成的矩陣。所以有：

那么就是所求的最優(yōu)仿射參數(shù)解。由于式4中有逆矩陣的存在，這樣計算結(jié)果會出現(xiàn)小數(shù)，所以對于結(jié)果圖像的處理上的象素可能不在整數(shù)點(diǎn)上，就需要通過插值法進(jìn)行彌補(bǔ)，而采用三次卷積法比較理想。

4 實(shí)驗(yàn)分析

因?yàn)楸疚闹袌D像的拼接所耗費(fèi)的時間主要花費(fèi)在配準(zhǔn)上面，用上述提出的改進(jìn)算法，首先對大量圖像進(jìn)行配準(zhǔn)實(shí)驗(yàn)，主要是針對已有的幾種配準(zhǔn)算法進(jìn)行時間上的比較。拼接前的兩幅圖像如圖3所示，拼接后的兩幅圖像如圖4所示。各種算法拼接速度的比較如表2所示。

圖3 拼接前的兩幅圖像

圖4 拼接后的結(jié)果圖像

表2 各種算法實(shí)現(xiàn)時間的比較

5 結(jié)束語

文中討論的拼接算法具有實(shí)時響應(yīng)速度快，特別是引入多CPU的線程同步技術(shù)，大大加快了拼接速度。但是由于要考慮到準(zhǔn)確性方面，每次淘汰非匹配點(diǎn)的時候還是會有很多點(diǎn)需要在以后的循環(huán)當(dāng)中進(jìn)行重復(fù)的匹配，實(shí)驗(yàn)算法速度改進(jìn)的空間還是很大的。

［1］ 王俊杰，劉家茂.圖像拼接技術(shù)［J］.計算機(jī)科學(xué)，2003，30（6）：141-144.

［2］ Brown LG.A survey of image registration techniques［J］.ACM Computing Surveys，1992，24（4）：325-367.

［3］ Zitoa B，F(xiàn)lusser.I Image resist ration methods a Survey［J］.Image and Vision Computing，2003，21（11）：977-1 000.

［4］ Huang X，Paragios N，Metaxas D.Shape registration in implicit spaces using information theory and free form deformations［J］.IEEE Trans Pattern Anal Mach Intell，2006，28（8）：1 303-1 318.

［5］ 陳靈娜，盛利元，陳俊熹.CT圖像配準(zhǔn)算法的研究與實(shí)現(xiàn)［J］.醫(yī)療設(shè)備信息，2004，19（8）：4-5.

［6］ Bentoutou Y，Table N，kpalma K，et al.An automatic image registration for applications in remote sensing［J］.IEEE Trans Geosci Remote Sens，2005，43（9）：2 127-2 137.