基于生物信息學(xué)中雙DNA序列比對算法的圖像立體匹配及其實(shí)現(xiàn)

1、第 15卷 第 1期2007年 1月 光學(xué) 精密工程 Optics and Precision Engineering Vol. 15 No. 1 Jan. 2007 收稿日期 :2006204210; 修訂日期 :2006206206. 基金項(xiàng)目 :國家自然科學(xué)基金資助項(xiàng)目 (No. 50405046和 No. 60605028 ; 上海市科委資助項(xiàng)目 (No. 045107031 ; 上海市優(yōu)秀青年教師培養(yǎng)計(jì)劃資助項(xiàng)目 (No. 04Y0HB094 ; 上海大學(xué)優(yōu)秀青年教師后備人選科研項(xiàng)目文章編號 10042924X (2007 0120106206基于生物信息學(xué)中雙 DNA 序列比對算法

2、的圖像立體匹配及其實(shí)現(xiàn)謝少榮 1, 王東紅 2, 羅 均 1, 龔振邦 1(1. 上海大學(xué) 機(jī)電工程與自動化學(xué)院 , 上海 200072;2. 廣西財(cái)經(jīng)學(xué)院 , 廣西 南寧 530002摘要 :提出了一種基于生物信息學(xué)中雙 DNA 序列比對算法的圖像立體匹配新方法 DNA 序列比對的實(shí)質(zhì)都是在匹配準(zhǔn)則下搜索最佳匹配基元 , 。 首先介, 有限定值 , 進(jìn)行了算法改進(jìn) , 極大地減少了計(jì)算量 , 最后采用 4組不同的圖像對進(jìn)行了 實(shí)驗(yàn)驗(yàn)證 。 , 生成的視差圖效果表明雙序列比對算法為圖像立 關(guān) 鍵 詞 :序列 ; 雙序列比對 ; 對應(yīng)點(diǎn) 中圖分類號 :Q2334; 文獻(xiàn)標(biāo)識碼 :ANovel s

3、tereo m atching algorithm based on pair 2wise D NAalignment algorithm in bioinform atics and its implementationXIE Shao 2ro ng 1,WAN G Dong 2hong 2,L UO J un 1, GON G Zhen 2bang 1(1. School of Mechatronics Engineering and A utomation , S hanghai University , S hanghai 200072, China;2. Guan g x i U n

4、i versit y of Fi nance and Economics , N anni ng 530002, Chi na Abstract :A novel stereo matching algorit hm based on pair 2wise DNA alignment algorit hm is presen 2ted. The essential of bot h stereo matching and pair 2wise DNA alignment in bioinformatics is t hat t he correspondence point s are sea

5、rched by matching criteria , so t he pair 2wise DNA alignment algorit hm is int roduced to design a new stereo matching algorit hm. Firstly , t he principle of t he dynamic program 2ming and implementation of t he propo sed algorit hm are p resented. Then , t his algorit hm is significant 2ly improv

6、ed to reduce t he calculation drastically , because t here is a maximum possible disparity who se value can be derived f rom t he field of view of t he cameras , t he p hysical distance between t he two cam 2eras , and t he focal lengt h of t he cameras. The flow of t he algorit hm is designed in de

7、tail wit h VC6. 0. Finally , t he disparity map s of several different test images by means of t his algorit hm are shown ,t he advantages are low comp uter complexity and parallel processing. The result s show t hat t he proposed algorit hm is usef ul andeffective. K ey w ords :stereo matching ; st

8、ereo vision ; DNA sequence ;pair 2wise alignment algorit hm ; correspon 2 dence point s1 引 言 基于立體視覺恢復(fù)景物的深度信息 , 在機(jī)器 人避障導(dǎo)航 、 運(yùn)動目標(biāo)跟蹤 、 識別和生物醫(yī)學(xué)等領(lǐng) 域有著廣闊的應(yīng)用前景 。顯然 , 由景物深度信息 z 與視差 (Disparity d 的關(guān)系 (d =B F/z , 式中 B 為基線距離 ; F 為相機(jī)焦距 不難看出 , 若兩個相 機(jī)的相對位置及焦距已知 , 由視差圖 (Disparity map 能很容易地計(jì)算出場景中景物的深度信息 , 其關(guān)鍵在于如何快速

9、、 準(zhǔn)確尋找同一場景在相機(jī) 拍攝的左右兩幅圖像上的對應(yīng)點(diǎn) 122,問題 。 因此 ,一個熱點(diǎn)研究問題 ,出了很多匹配算法 ,域 324、 基于特征 527和基于相位 82103類方法 , 其 實(shí)質(zhì)都是在匹配準(zhǔn)則下搜索最佳匹配基元 。 這些 方法都各有其優(yōu)缺點(diǎn) :基于特征的匹配是對圖像 對的特征區(qū)域進(jìn)行匹配 , 其優(yōu)點(diǎn)是速度快 、 能得 到比較精確的匹配 , 但只能得到稀疏的視差圖 , 無 法處理特征不明顯的場景圖像 ; 基于區(qū)域的匹配 可以直接產(chǎn)生致密的視差圖 , 但其主要缺點(diǎn)是計(jì) 算復(fù)雜度大 ; 基于相位的匹配 , 是利用具有局域頻 率特征的相位信號作為匹配基元進(jìn)行匹配 , 具有 從粗到精的

10、多分辨率特性 , 也可以進(jìn)行每個像素 的匹配 , 但一般只能得到景物的粗糙結(jié)構(gòu) , 有時還 需進(jìn)行特殊處理 。無獨(dú)有偶 , 在現(xiàn)代生物信息學(xué)中 , 通過序列比 較 , 在已知結(jié)構(gòu)和功能的序列數(shù)據(jù)庫中找出與新 測定序列具有相似性的同源序列 , 從而以足夠的 可信度確定新序列的結(jié)構(gòu)和功能信息 , 因而尋求 更快更靈敏的生物序列相似性比對算法也一直是 生物信息學(xué)的研究熱點(diǎn) 。 經(jīng)過 40多年的發(fā)展 , 雙 序列比對算法已基本實(shí)現(xiàn) , 序列比對的未來發(fā)展 方向是基因組比較 , 雙序列比對是其重要基礎(chǔ) 。 該比對方法具有較低的計(jì)算復(fù)雜度和適宜于并行 計(jì)算的特點(diǎn) 11215。圖像立體匹配和序列比對的實(shí)質(zhì)相

11、同 , 都是 在匹配準(zhǔn)則下搜索最佳匹配基元 。因此 , 本文新 穎地將生物信息學(xué)中雙 DNA 序列比對算法引入圖像立體匹配 , 該方法具有較低的計(jì)算復(fù)雜度和 適宜于并行計(jì)算的特點(diǎn) 。2 生物信息學(xué)中雙 DNA 序列比對 算法一 。 在生物學(xué)研究中 , , 根據(jù)同時進(jìn)行比對的序 。經(jīng)過 40 , 雙序列比對問題已基本解決 。本文 正是擬將雙序列比對算法引入圖像立體匹配 。 DNA 序列由 A 、 T 、 C 、 G 四種堿基組成 , 從而 一個 DNA 序列就可視為由這 4個字母組成的字 符串 。 雙序列比對算法 , 就是根據(jù)給定的計(jì)分函 數(shù)計(jì)算在待比對的兩個字符串中插入空格 2 的 適當(dāng)位置和

12、數(shù)量 , 從而得到兩個序列之間的最大 相似性排列 , 也就是實(shí)現(xiàn)了最優(yōu)比對 。插入空格 2 的數(shù)量可視為左右兩幅圖像中對應(yīng)點(diǎn)間的視 差 。 例如兩條 DNA 序列 T GC GT 和 A T GGT , 希望通過對每條字符序列插入空格 , 得到使兩條 序列的匹配字符數(shù)最大的最佳比對 , 具體算法過 程如下 :用 s 表示待比較的前一序列 , t 表示后一序 列 , S (i , j 表示得分矩陣中 s 的第 i 個字符和 t 的 第 j 個字符的最佳隊(duì)列的分?jǐn)?shù) , g 表示一個間隔 分?jǐn)?shù) , 表示 s 中第 i 個字符與 t 中第 j 個字符匹配 的分?jǐn)?shù) 。 在生物信息學(xué)中 , 當(dāng)正確匹配時

13、, 分?jǐn)?shù)加 2; 誤匹配時 , 分?jǐn)?shù)減 1, 間隔罰分 g 取 -1。 給定計(jì)分函數(shù) :S (i , j =S (i -1, j +gS (i , j -1 +gS (i -1, j -1 +P (i , j , (1 由式 (1 可以看出 , 從三個方向可以到達(dá)矩陣 元素 (i , j :對角線方向元素 、 同一行或同一列 的元素 。 在得分矩陣中 , 到達(dá)位置為 (i , j 的某 一個元素有三種可能的路徑 :通過位置 (i -1, j -1 的對角方向 , 沒有空位罰分 ; 通過列 j 的垂直 701第 1期 謝少榮 , 等 :基于生物信息學(xué)中雙 DNA 序列比對算法的圖像立體匹配及其實(shí)

14、現(xiàn)方向和通過行 i 的水平方向 , 空位罰分取 g 。再取 3個分值中的最大值作為該矩陣元素的得分 , 進(jìn)行遞歸計(jì)算 , 實(shí)現(xiàn)動態(tài)規(guī)劃 。對于邊界初始分?jǐn)?shù)取值為 :S (i , 0 =S (0, i =g 3i ,(2 依據(jù)上述計(jì)分函數(shù)所得得分矩陣如表 1所示 :表 1 雙 DNA 序列比對得分矩陣T ab. 1 Score matrix of pair -wise DNA alignment algorithm (i =m , j =n 開 始 , 通過動態(tài)規(guī)劃回溯法 , 追溯序列比對的最優(yōu)結(jié) 果 , 其路徑見表 (1 中箭頭所示 。若箭頭為對角 線 , 則在比對后的序列中兩個堿基相對應(yīng) ;

15、 若箭頭 為水平方向 , 則在 s 序列的相應(yīng)位置插入一個空 格 2 ; 若箭頭為垂直方向 , 則在 t 序列的相應(yīng)位 置插入一個空格 2 。 比對結(jié)果有兩種情況 :s 2T G C G T 和 2 T G C G T t A T G -G TA T G G -T表 2 改變誤匹配罰分值后的得分矩陣Tab. 2 Score matrix when mismatch is - 2 顯然 , 后一種結(jié)果不是最優(yōu)的 , 主要原因在于 有誤匹配 , 因此通過加大誤匹配時的罰分值能改 進(jìn)上述比對 。誤匹配時 , 按分?jǐn)?shù)減 2計(jì)算的得分 矩陣如表 2所示 。表 2中箭頭所示回溯路徑即為最優(yōu)比對結(jié)果。3 基

16、于雙序列比對算法的立體匹配方法 假設(shè)左右兩幅圖像是由兩個完全相同的攝像機(jī)同時拍攝同一場景所得 , 且兩個圖像平面位于 同一個平面上 , 兩攝像機(jī)坐標(biāo)系的 x 軸平行 , 光 軸相互平行 , 這樣場景中的同一特征點(diǎn)在兩個攝 像機(jī)圖像平面上的成像位置只具有水平視差 , 而 且外極線與圖像行平行 。因此 , 可以將兩幅圖像 , 其特征 B , 將雙序列比對算 , 插入 。如圖 1所示 , 場 。 左圖像中的一極 線上的像素灰度值為 (0,0,0,0,0,255,255,255, 0,0 , 同時在右圖像中相應(yīng)極線上的像素灰度值 為 (0,0,0,255,255,255,0,0,0,0 。應(yīng)用第 2部

17、 分中的比對算法得到的最優(yōu)比對結(jié)果為 :圖 1 圖像的字符串表示Fig. 1 Intensity (brightness values of a grayscaleimage (or R G B values of a color image can be interpreted as the characters of the strings0000025525525522 00000222552552550000顯然 , 從左圖像中的第 4個像素開始 , 增加了 2個像素視差 。實(shí)際圖像易受噪聲 、 光照的影響 , 會造成左右 兩幅圖像中對應(yīng)像素點(diǎn)的灰度值或 R G B 值有些 差異 ,

18、為了保證該匹配算法的穩(wěn)定性 、 容錯性 , 可 視實(shí)際情況設(shè)定匹配 /誤匹配的灰度值或 R G B 值 的差異閾值 。801 光學(xué) 精密工程 第 15卷 4 算法改進(jìn) 從序列比對的實(shí)際意義出發(fā) , 如果兩個序列 較為相似 , 那么最優(yōu)比對只需沿得分矩陣的對角 線 (左上至右下 , 在其上下一定范圍內(nèi)進(jìn)行規(guī)劃 就可以得到 。對于表 1和表 2, 假定最大視差值 為 1, 則不需要計(jì)算全部的動態(tài)規(guī)劃表 , 如表 3所 示 , 只計(jì)算對角線及其上 /下移一個位置的元素 。 因此 , 可將計(jì)算復(fù)雜度從 O (m n 縮減至 O (dm 或 O (dn , 取 m 、 n 中較大者 。在實(shí)際圖像立體匹

19、配中 , 攝像機(jī)的視場 、 兩個攝像機(jī)間的物理距離和 攝像機(jī)的焦距長度都是一定的 , 所以其最大視差 是一個有限的定值 , 因而也可利用上述改進(jìn)算法 來大大減少搜索空間 , 縮小計(jì)算量 。圖 2 基于雙序列比對算法的立體匹配流程圖Fig. 2 Flow of a novel stereo matching based on pair 2wise alignment algorithm表 3 限定了動態(tài)規(guī)劃范圍的得分矩陣T ab. 3 Score matrix limited by dynamic programming rangej 0 1 23450 0-1T1-1-1 1G 2-2 03C

20、 3-122G 4143 經(jīng)以上設(shè)計(jì) , 基于生物信息學(xué)中雙序列比對 算法的圖像立體匹配新方法在 VC6. 0中的實(shí)現(xiàn) 流程如圖 2所示 。5 實(shí)驗(yàn)結(jié)果 為了便于和其他算法進(jìn)行橫向比較 , 檢驗(yàn)序 列比對算法的立體匹配效果 , 本文選用了立體匹 配實(shí)驗(yàn)常用的一對下載自德國波恩大學(xué)計(jì)算機(jī)視 覺研究 小組 的 網(wǎng) 頁 http :/www 2dbv. informa 2tik. uni 2bonn. de corridor , 圖像大 小是 256×256, 如圖 , 在 P4/1. 6GHz/(亮度小 的點(diǎn)表示 ; 灰度值越大 (亮度大 的點(diǎn) , 即深度越小 , 例如視差圖中的球 、

21、圓錐和走廊盡頭的墻壁 , 其灰度是由淺到深 , 深度 信息相當(dāng)明顯 。圖中上部分的文本框是輸入信 息 , 包括左右原圖像 、 視差范圍 、 匹配分?jǐn)?shù) 、 補(bǔ)償間 隔等 。圖 3 corridor 原始像對 Fig. 3 Original images圖 4 用本文算法得到的視差圖Fig. 4 Our disparity map與采用基于遺傳算法和基于 Hopfield 網(wǎng)絡(luò) 的實(shí)驗(yàn)結(jié)果 (如圖 5所示 相比較 , 本文算法生成901第 1期謝少榮 , 等 :基于生物信息學(xué)中雙 DNA 序列比對算法的圖像立體匹配及其實(shí)現(xiàn)的視差圖效果明顯優(yōu)于這兩者 , 非常清楚地把圖 像對中的各個景物按深度信息分

22、開了層次 。 在硬 件條件相當(dāng)?shù)那闆r下 , 基于 Hopfield 網(wǎng)絡(luò)的匹配 時間是 39. 7s , 而本文算法的運(yùn)行時間是 1. 56s , 比基于區(qū)域的灰度相關(guān)算法的運(yùn)行時間減少了 3050倍 。 對實(shí)際圖像 (如圖 6(a 和 (b 所示 匹 配的效果如圖 6(c 所示 , 計(jì)算產(chǎn)生的視差圖密度 大 , 定位精度高 。 綜上所述 , 本文算法是一種匹配 質(zhì)量高 、 速度快的圖像立體匹配算法 。(a 遺傳算法 (a G enetic (b Hopfield network圖 5 其他算法所得 corridor 的視差圖Fig. 5 Other disparity maps(a (b (

23、c 圖 6 實(shí)際圖像對及其視差圖Fig. 6 True images and disparity map本文提出的基于序列比對的立體匹配算法已實(shí)際應(yīng)用于遠(yuǎn)距離場景中動態(tài)目標(biāo)深度信息的實(shí)時獲取 。 圖 7和圖 8分別是目標(biāo)距離為 54m 和57m 處的獲取情況 。像對中白框所標(biāo)示的動態(tài) 目標(biāo)正在向左側(cè)路邊靠近 , 圖像對上方的文本框 中是實(shí)時獲取的深度信息顯示 。圖 7 目標(biāo)距離 54mFig. 7 Object of 54 m圖 8 目標(biāo)距離 57mFig. 8 Object of 57m根據(jù)實(shí)際應(yīng)用情況 , 每對像對只取動態(tài)目標(biāo)周圍 50×50的 區(qū) 域 進(jìn) 行 匹 配 , 處 理

24、 速 度 為 10pixel/s , 完全能滿足機(jī)器人動態(tài)避障的應(yīng)用要 求 。6 結(jié) 論 本文將生物信息學(xué)中已成功實(shí)現(xiàn)的雙序列比對算法引入圖像立體匹配 , 該方法具有較低的計(jì) 算復(fù)雜度和適宜于并行計(jì)算的特點(diǎn) 。 實(shí)驗(yàn)證明該 算法給立體匹配提供了一個既具有低計(jì)算復(fù)雜度 又能生成致密視差圖的實(shí)用方法 , 匹配質(zhì)量高 、 速 度快 。11 光學(xué) 精密工程 第 15卷 第1期 謝少榮 ,等 : 基于生物信息學(xué)中雙 DNA 序列比對算法的圖像立體匹配及其實(shí)現(xiàn) 111 參考文獻(xiàn) : 1 GDAN G. Point matching under large image defo rmations and i

25、lluminatin changes J . I E E E Com p ut . S oc. , BO 2 朱明 ,魯劍鋒 ,胡碩 . 采用 DSP 的電視測量跟蹤器的研制 J . 光學(xué) 精密工程 ,2005 ,13 ( Supp . :2322235. 7 徐瑞鑫 ,劉偉寧 . 基于自適應(yīng)模板的實(shí)時跟蹤算法 J . 光學(xué) 精密工程 ,2002 ,10 ( 4 :3652369. 369. (in Chinese 11 張敏 . 生物序列比對算法研究現(xiàn)狀與展望 J . 大連大學(xué)學(xué)報(bào) , 2004 , 25 ( 4 : 75279. 79 . (in Chinese 1975 , 18 ( 6

26、 :341 2343 . 263. net 1999 , 70 :129 2139 . ( 4 : 463 2466 . (in Chinese ( 2 :207 2212 . (in Chinese Con f erence on Pattern Recog nition , 1996 , 451 2455 . 3 KANAD E T , O KU TOMI M. A stereo matching algorit hm wit h an adaptive window : t heo ry and experiment J . 4 SUN C H. A fast stereo matchi

27、ng met hod C . Di git al I m a ge Com p uti n g an d A p p lications , 1997 : 95 2100 . 10 葉海加 ,陳罡 ,邢淵 . 雙目 CCD 結(jié)構(gòu)光三維測量系統(tǒng)中的立體匹配 J . 光學(xué) 精密工程 ,2004 ,12 (1 :71275. 12 王宏漫 , 歐宗瑛 . 進(jìn)化算法在 DNA 序列比對中的應(yīng)用 J . 數(shù)據(jù)采集與處理 , 2002 , 17 ( 4 : 4632466. WAN G H M , OU Z Y. Evolution algorit hm for sequence alignment J

28、. J . D at a A cquis . 15 唐玉榮 , 汪懋華 . 基于動態(tài)規(guī)劃的快速比對算法 J . 生物數(shù)學(xué)學(xué)報(bào) , 2005 , 20 ( 2 :2072212. O pt. P recision En g . , 2004 ,12 (1 :71275. (in Chinese ces. , 1997 , 6 ( 10 : 1460 21464 . I E E E T rans . Pattern A nal . M ach. I ntel. , 1994 , 16 ( 9 : 920 2932 . P recision En g . , 2004 ,12 ( 3 :311231

29、5. (in Chinese 作者簡介 : 謝少榮 ( 1972 - ,女 ,湖北天門人 ,博士 ,副教授 ,主要研究方向?yàn)橛?jì)算機(jī)視覺和智能控制等 .E2mail : srxie 5 CANDOCIA F , ADJ OUADI M A. Similarity measure fo r stereo feat ure matching J . I E E E T rans . I m a g. Pro2 6 姜凱 ,陳海霞 ,劉立峰 ,湯建華 . 基于模板抽樣的快速圖像匹配算法 J . 光學(xué) 精密工程 ,2004 ,12 ( 3 :3112315. J . M ach. V ision A p p l . , 1998 , 11 ( 2 : 83 295 . J IAN G K ,C H EN H X ,L IU L F , TAN G J H. Fast image matching algorit hm based o n template samplingJ . O pt. 8 FRO HL IN GHAU S T , BU HMANN J M. Regularizing p hase2based stereo C . P rocee di n gs of t he I nternational YE H J ,C