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

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

2、的圖像立體匹配及其實現(xiàn)謝少榮 1, 王東紅 2, 羅 均 1, 龔振邦 1(1. 上海大學 機電工程與自動化學院 , 上海 200072;2. 廣西財經學院 , 廣西 南寧 530002摘要 :提出了一種基于生物信息學中雙 DNA 序列比對算法的圖像立體匹配新方法 DNA 序列比對的實質都是在匹配準則下搜索最佳匹配基元 , 。 首先介, 有限定值 , 進行了算法改進 , 極大地減少了計算量 , 最后采用 4組不同的圖像對進行了 實驗驗證 。 , 生成的視差圖效果表明雙序列比對算法為圖像立 關 鍵 詞 :序列 ; 雙序列比對 ; 對應點 中圖分類號 :Q2334; 文獻標識碼 :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 引 言 基于立體視覺恢復景物的深度信息 , 在機器 人避障導航 、 運動目標跟蹤 、 識別和生物醫(yī)學等領 域有著廣闊的應用前景 。顯然 , 由景物深度信息 z 與視差 (Disparity d 的關系 (d =B F/z , 式中 B 為基線距離 ; F 為相機焦距 不難看出 , 若兩個相 機的相對位置及焦距已知 , 由視差圖 (Disparity map 能很容易地計算出場景中景物的深度信息 , 其關鍵在于如何快速

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

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

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

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

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

14、現(xiàn)方向和通過行 i 的水平方向 , 空位罰分取 g 。再取 3個分值中的最大值作為該矩陣元素的得分 , 進行遞歸計算 , 實現(xiàn)動態(tài)規(guī)劃 。對于邊界初始分數(shù)取值為 :S (i , 0 =S (0, i =g 3i ,(2 依據(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)結 果 , 其路徑見表 (1 中箭頭所示 。若箭頭為對角 線 , 則在比對后的序列中兩個堿基相對應 ;

15、 若箭頭 為水平方向 , 則在 s 序列的相應位置插入一個空 格 2 ; 若箭頭為垂直方向 , 則在 t 序列的相應位 置插入一個空格 2 。 比對結果有兩種情況 :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 顯然 , 后一種結果不是最優(yōu)的 , 主要原因在于 有誤匹配 , 因此通過加大誤匹配時的罰分值能改 進上述比對 。誤匹配時 , 按分數(shù)減 2計算的得分 矩陣如表 2所示 。表 2中箭頭所示回溯路徑即為最優(yōu)比對結果。3 基

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

17、 分中的比對算法得到的最優(yōu)比對結果為 :圖 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個像素視差 。實際圖像易受噪聲 、 光照的影響 , 會造成左右 兩幅圖像中對應像素點的灰度值或 R G B 值有些 差異 ,

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

19、配中 , 攝像機的視場 、 兩個攝像機間的物理距離和 攝像機的焦距長度都是一定的 , 所以其最大視差 是一個有限的定值 , 因而也可利用上述改進算法 來大大減少搜索空間 , 縮小計算量 。圖 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 經以上設計 , 基于生物信息學中雙序列比對 算法的圖像立體匹配新方法在 VC6. 0中的實現(xiàn) 流程如圖 2所示 。5 實驗結果 為了便于和其他算法進行橫向比較 , 檢驗序 列比對算法的立體匹配效果 , 本文選用了立體匹 配實驗常用的一對下載自德國波恩大學計算機視 覺研究 小組 的 網(wǎng) 頁 http :/www 2dbv. informa 2tik. uni 2bonn. de corridor , 圖像大 小是 256×256, 如圖 , 在 P4/1. 6GHz/(亮度小 的點表示 ; 灰度值越大 (亮度大 的點 , 即深度越小 , 例如視差圖中的球 、

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

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

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

24、 速 度 為 10pixel/s , 完全能滿足機器人動態(tài)避障的應用要 求 。6 結 論 本文將生物信息學中已成功實現(xiàn)的雙序列比對算法引入圖像立體匹配 , 該方法具有較低的計 算復雜度和適宜于并行計算的特點 。 實驗證明該 算法給立體匹配提供了一個既具有低計算復雜度 又能生成致密視差圖的實用方法 , 匹配質量高 、 速 度快 。11 光學 精密工程 第 15卷 第1期 謝少榮 ,等 : 基于生物信息學中雙 DNA 序列比對算法的圖像立體匹配及其實現(xiàn) 111 參考文獻 : 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 . 光學 精密工程 ,2005 ,13 ( Supp . :2322235. 7 徐瑞鑫 ,劉偉寧 . 基于自適應模板的實時跟蹤算法 J . 光學 精密工程 ,2002 ,10 ( 4 :3652369. 369. (in Chinese 11 張敏 . 生物序列比對算法研究現(xiàn)狀與展望 J . 大連大學學報 , 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 結構光三維測量系統(tǒng)中的立體匹配 J . 光學 精密工程 ,2004 ,12 (1 :71275. 12 王宏漫 , 歐宗瑛 . 進化算法在 DNA 序列比對中的應用 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ù)學學報 , 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 - ,女 ,湖北天門人 ,博士 ,副教授 ,主要研究方向為計算機視覺和智能控制等 .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 . 光學 精密工程 ,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