【正文】 □ 良 □ 中 □ 及格 □ 不及格 （在所選等級(jí)前的□內(nèi) 畫(huà)“√”） 教研室主任（或答辯小組組長(zhǎng)）： （簽名） 年 月 日 教學(xué)系意見(jiàn)： 系主任： （簽名） 年 月 日 第 3 頁(yè) 共 29 頁(yè) 南京大學(xué)金陵學(xué)院本科生畢業(yè)論文（設(shè)計(jì)）中文摘要 畢業(yè)論文題目： 基于動(dòng)態(tài)規(guī)劃理論的立體匹配算法研究 信工 院系 電子信息科學(xué)與技術(shù) 專業(yè) 08 級(jí)本科生姓名： 張洋洋 指導(dǎo)教師（姓名）： 李揚(yáng) 隨著計(jì)算機(jī)視覺(jué)的發(fā)展，雙目立體視覺(jué)已經(jīng)成為近期研究的重 點(diǎn)，它主要是通過(guò)模擬人眼立體成像的機(jī)制，利用兩臺(tái)攝像機(jī)通過(guò)不同位置成像，然后通過(guò)后續(xù)的處理，主要包括攝像機(jī)標(biāo)定，立體匹配，以即最后 3D 重建最終產(chǎn)生三維的圖像。 對(duì)于立體匹配，現(xiàn)如今已經(jīng)有許多不同的研究成果，包括分為不同流派的研究思路，主要有針對(duì)區(qū)域的匹配算法和全局的匹配算法的研究并且都取得了很大的進(jìn)展，其中針對(duì)全局路徑的立體匹配要優(yōu)于塊匹配，最著名的是基于動(dòng)態(tài)規(guī)劃的匹配算法，這種傳統(tǒng)的匹配算法，僅僅引入單調(diào)順序約束，缺乏全局對(duì)于掃 描線約束的限制，使得匹配后的視差圖像存在大量帶狀誤匹配的情況，針對(duì)此現(xiàn)象，本文提出了基于動(dòng)態(tài)規(guī)劃理論的立體匹配思想，通過(guò)加入行掃描線之間的約束條件和列掃描，能夠較好的完成圖像的匹配與視差的還原。 雙目立體視覺(jué)概述 ......................................................................................錯(cuò)誤 !未定義書(shū)簽。 第 2章 常用的一些立體匹配的算法 ....................................................................3 視差理論 .....................................................................................................4 第 5 頁(yè) 共 29 頁(yè) 立體匹配常用算法綜述 .............................................................................4 第 3章 分層正交動(dòng)態(tài)劃匹配算法 ........................................................................4 匹配代價(jià)與視差空間 .................................................................................5 匹配代價(jià)計(jì)算 ....................................................................................6 固定窗口塊匹配過(guò)程 ........................................................................7 滑動(dòng)窗口匹配 ....................................................................................9 動(dòng)態(tài)規(guī)劃立體匹配 ....................................................................................10 分層正交動(dòng)態(tài)規(guī)劃立體匹配算法 ............................................................12 水平方向最優(yōu)路徑 ...........................................................................12 水平雙向能量函數(shù) ...........................................................................13 垂直方向最優(yōu)路徑 ...........................................................................13 第 4 章 總結(jié)與展望 第一章 緒論 計(jì)算機(jī)視覺(jué)的發(fā)展概況 “計(jì)算機(jī)視覺(jué)領(lǐng)域的最突出特點(diǎn)是其多樣性和不完善性。然而這些發(fā)展往往起源于其他不同領(lǐng)域的需要，因而何謂 “計(jì)算機(jī)視覺(jué)問(wèn)題 ”始終沒(méi)有得到正式定義，很自然地， “計(jì)算機(jī)視覺(jué)問(wèn)題 ”應(yīng)當(dāng)被如何解決也沒(méi)有成型的公式 ” ]1[ 。 第 6 頁(yè) 共 29 頁(yè) 除了上 面提到的領(lǐng)域，很多研究課題同樣可被當(dāng)作純粹的數(shù)學(xué)問(wèn)題。如何使既有方法通過(guò)各種軟硬件實(shí)現(xiàn)，或說(shuō)如何對(duì)這些方法加以修改，而使之獲得合理的執(zhí)行速度而又不損失足夠精度，是現(xiàn)今電腦視覺(jué)領(lǐng)域的主要課題。 如今對(duì)于計(jì)算機(jī)雙目立體視覺(jué)的研究比較熱，也取得了很多進(jìn)展，本文著重對(duì)雙 目立體視覺(jué)中的算法進(jìn)行高論分析。它通過(guò)仿生學(xué)的原理模擬人類雙眼成像的機(jī)制原理，利用兩個(gè)攝像機(jī)在不同角度拍的攝同一景物或者物體，通過(guò)一個(gè)參考空間來(lái)計(jì)算兩幅拍攝圖像中的視差，進(jìn)而獲得對(duì)應(yīng)點(diǎn)的三維坐標(biāo)值信息。 整個(gè)雙目立體視覺(jué)流程如圖 所示： 第 7 頁(yè) 共 29 頁(yè) 左 圖 像 右 圖 像預(yù) 處 理相 機(jī) 標(biāo) 定立 體 匹 配三 維 重 建 圖 雙目立體視覺(jué)的處理流程 由于本文主要研究立體匹配的相關(guān)算法，因此不過(guò)多對(duì)：圖像的預(yù)處理、相機(jī)標(biāo)定以及三維重建等細(xì)節(jié)進(jìn)行相關(guān)的研究討論。因?yàn)楝F(xiàn)實(shí)中的大多圖像信息都是三維的，然而攝像機(jī)只能將三維的圖像信息投射到二維的空間，這就使得三維空間中復(fù)雜的信息都只能以單一的像素表現(xiàn)在二維圖像中。所以就目前立體匹配研究的方向來(lái)看，無(wú)論哪一種立體匹配的算法，其步驟和內(nèi)容都主要分為三個(gè)方面，首先是選取恰當(dāng)?shù)钠ヅ涮胤N方法，這一點(diǎn)尤為重要?，F(xiàn)如今我們看到的主流的算法都是介于這三個(gè)不走展開(kāi) 的，基于這種方法世界各地也提出了很多各具特色的算法匹配，但是由于立體匹配本身復(fù)雜多樣性，同時(shí)涉及的問(wèn)題復(fù)雜繁多，所以至今未有一整套成熟通用的算法去解決問(wèn)題。全文安排如下：第一章，主要介紹現(xiàn)代計(jì)算機(jī)視覺(jué)發(fā)展的概況以及雙目立體 第 8 頁(yè) 共 29 頁(yè) 視覺(jué)匹配的一些概念。第三章，重點(diǎn)分析傳統(tǒng)動(dòng)態(tài)規(guī)劃匹配算法的不足，并根 據(jù)不足提出改進(jìn)的匹配算法即基于動(dòng)態(tài)規(guī)劃正交立體匹配算法。 第二章 立體匹配的常用算法 Scharstein 等提出立體匹配算法可以大致分為四個(gè)步驟 [2] ：第一步是初始代價(jià)匹配計(jì)算；第二步是對(duì)初始匹配代價(jià)的能量聚合值計(jì)算；第三步是視差的計(jì)算與優(yōu)化；最后則是圖像校正。而自適應(yīng)窗口塊匹配算法則將前兩部相結(jié)合，后續(xù)步驟相同。 全局算法在匹配代價(jià)函數(shù)的基礎(chǔ)上，結(jié)合根據(jù)特定的約束條件建立新的代價(jià)函數(shù)，從而構(gòu)成全局能量函數(shù)，然后通過(guò)選用的特有的不同方法尋查找使得全局能量最小匹配聚合值。 相對(duì)而言，動(dòng)態(tài)規(guī)劃算法具有計(jì)算效率高、匹配效果較好的特點(diǎn)，因此成為實(shí)時(shí)處理中最常用的算法之一。人 第 9 頁(yè) 共 29 頁(yè) 的左眼和右眼在觀察同一個(gè)物體的時(shí)候，由于雙眼之間總有一定的距離，在觀察同一個(gè)物體的時(shí)候，左眼與右眼總有一定的距離偏移（視差），但在雙眼的聚焦點(diǎn)處偏移為零，比較直觀的體會(huì)是在觀察同一個(gè)物體的時(shí)候，通過(guò)分別單獨(dú)遮擋住一只眼睛，可以發(fā)現(xiàn)所觀察的事物有一定的視差。因此人可以區(qū)分不同景深的物體。 立體匹配常用算法綜述 由于采用平行攝像機(jī)（同一個(gè)攝像機(jī)），外極線是水平的，與圖像掃描線重合，在進(jìn)行匹配點(diǎn)搜索時(shí)可以大大簡(jiǎn)化搜索步驟。 鑒于非平 行性下的攝像機(jī)配置為題的復(fù)雜性，國(guó)內(nèi)外主要針對(duì)平行攝像機(jī)下的立體匹配做了重點(diǎn)研究，立體匹配的主要的思路就是試圖找到左右圖像在同一幅圖像上對(duì)應(yīng)點(diǎn)。表 列出了各類匹配 方法的典型算法。在固定的塊區(qū)域進(jìn)行算法匹配。 特征匹配 由于像素可靠性相對(duì)較低，特征匹配利用圖像的如邊緣特征進(jìn)行算法 第 10 頁(yè) 共 29 頁(yè) 匹配。 全局匹配 選取最小全局能量函數(shù)，獲取視差空間。 Graph Cuts 運(yùn)用圖形中的最大流的最小切割原理來(lái)估算視差值。 表 立體匹配典型算法 第三章 分層正交動(dòng)態(tài)規(guī)劃立體匹配算法 匹配代價(jià)與視差空間 我們假設(shè)：左圖像、右圖像分別用 LI 和 RI 表示，那么左視差 Ld 就表示左圖像上的點(diǎn) ( , )LI xy 和右圖像上點(diǎn) ( , )RLI x d y? 為同一副圖像在兩幅圖像上的映射即兩點(diǎn)映射到圖像上的同一個(gè)位置，可以通俗的講，這中對(duì)應(yīng)關(guān)系中零點(diǎn)的灰度值是相等的