立體匹配技術(shù)淺析

1、立體匹配技術(shù)淺析,計(jì)算機(jī)應(yīng)用技術(shù)2008級(jí)研究生姚剛,提綱,計(jì)算機(jī)視覺(jué)技術(shù)簡(jiǎn)介立體視覺(jué)的基本原理立體匹配算法簡(jiǎn)介立體匹配技術(shù)的發(fā)展趨勢(shì),計(jì)算機(jī)視覺(jué)技術(shù)簡(jiǎn)介,計(jì)算機(jī)視覺(jué),計(jì)算機(jī)視覺(jué)是研究用計(jì)算機(jī)和成像設(shè)備來(lái)模擬人和生物視覺(jué)系統(tǒng)功能的技術(shù)學(xué)科,其目標(biāo)是從圖像或圖像序列中獲取對(duì)外部世界的認(rèn)知和理解,即利用二維圖像恢復(fù)三維環(huán)境中物體的幾何信息,比如形狀、位置、姿態(tài)、運(yùn)動(dòng)等,并能描述、識(shí)別與理解。,計(jì)算機(jī)視覺(jué)技術(shù)簡(jiǎn)介,計(jì)算機(jī)視覺(jué)發(fā)展簡(jiǎn)史,

2、20世紀(jì)50年代歸入模式識(shí)別----主要集中在二維圖像分析和識(shí)別上，如光學(xué)字符識(shí)別，工件表面、顯微圖片和航空?qǐng)D片的分析和解釋等。 60年代，Roberts積木世界理論----開創(chuàng)了以理解三維場(chǎng)景為目的的三維計(jì)算機(jī)視覺(jué)的研究。70年代，Marr計(jì)算視覺(jué)理論----第一個(gè)較為完善的視覺(jué)系統(tǒng)框架，分三個(gè)層次進(jìn)行處理。 80年代以后，蓬勃發(fā)展----新概念、新方法、新理論不斷涌現(xiàn)，如基于感知特征群的物體識(shí)別理論框架，主動(dòng)視覺(jué)理論框架，視覺(jué)

3、集成理論框架等。,計(jì)算機(jī)視覺(jué)技術(shù)簡(jiǎn)介,視覺(jué)系統(tǒng)的三個(gè)層次,低層階段 ：基于圖像特征提取及分割 中層階段 ：基于物體的幾何模型與圖像特性表達(dá) 高層階段 ：基于景物知識(shí)的描述、識(shí)別與理解,計(jì)算機(jī)視覺(jué)技術(shù)簡(jiǎn)介,計(jì)算機(jī)視覺(jué)技術(shù)的應(yīng)用,(1)工業(yè)機(jī)器人、移動(dòng)機(jī)器人導(dǎo)航、安全監(jiān)測(cè)、監(jiān)測(cè)跟蹤、運(yùn)動(dòng)分析、工業(yè)產(chǎn)品農(nóng)作物食品檢測(cè)、智能交通系統(tǒng)、娛樂(lè)、指紋識(shí)別、人臉識(shí)別。 (2)基于內(nèi)容的圖像數(shù)據(jù)查詢、基于內(nèi)容的圖像自動(dòng)索引等成為很熱門的研究和應(yīng)

4、用課題,可應(yīng)用于數(shù)字圖書館、體育圖像自動(dòng)分析、運(yùn)動(dòng)物體自動(dòng)跟蹤等系統(tǒng),根據(jù)物體的二維圖像提取相應(yīng)的特征不變量進(jìn)行識(shí)別和分類也是一個(gè)十分重要的研究方向。同時(shí),三維物體識(shí)別也開始進(jìn)入了實(shí)用階段。,立體視覺(jué)的基本原理,立體視覺(jué)的研究?jī)?nèi)容與基本原理,獲取空間三維場(chǎng)景的距離信息是計(jì)算機(jī)視覺(jué)研究中最基礎(chǔ)的內(nèi)容。立體視覺(jué)的基本原理是從兩個(gè)(或多個(gè))視點(diǎn)觀察同一景物,以獲取在不同視角下的感知圖象,通過(guò)三角測(cè)量原理計(jì)算圖象象素間的位置偏差(即視差)來(lái)獲取

5、景物的三維信息,這一過(guò)程與人類視覺(jué)的立體感知過(guò)程是類似的。,立體視覺(jué)的基本原理,立體視覺(jué)系統(tǒng)的組成,(1)圖象獲取 圖象獲取的方式主要取決于應(yīng)用的場(chǎng)合和目的 。獲取立體圖象時(shí)不但要滿足應(yīng)用要求,而且要考慮視點(diǎn)差異、光照條件、攝象機(jī)性能以及景物特點(diǎn)等因素的影響,以有利于立視計(jì)算。(2)攝象機(jī)標(biāo)定 確定攝象機(jī)的位置、屬性參數(shù)和建立成象模型,以便確定空間坐標(biāo)系中物體點(diǎn)同它在圖象平面上象點(diǎn)之間的對(duì)應(yīng)關(guān)系。建立一個(gè)有效的攝象機(jī)模型,除了能夠

6、精確地恢復(fù)出空間景物的三維信息外,還有利于解決立體匹配問(wèn)題。,立體視覺(jué)的基本原理,立體視覺(jué)系統(tǒng)的組成,(3)特征提取 為了得到匹配賴以進(jìn)行圖象特征的提取，目前尚沒(méi)有一種普遍適用的理論可運(yùn)用于圖象特征的提取,從而導(dǎo)致了立體視覺(jué)研究中匹配特征的多樣性。 (4)立體匹配立體視覺(jué)中最重要也是最困難的問(wèn)題，其基本原理是從兩個(gè)視點(diǎn)觀察同一景物以獲取立體像對(duì),匹配出相應(yīng)像點(diǎn),從而計(jì)算出視差并獲得三維信息。20 世紀(jì)80 年代,美國(guó)麻省理工學(xué)院的

7、Marr 提出了一種視覺(jué)計(jì)算理論奠定了立體視覺(jué)發(fā)展的理論基礎(chǔ)。,立體視覺(jué)的基本原理,立體視覺(jué)系統(tǒng)的組成,(5)深度確定 根據(jù)立體匹配的結(jié)果，計(jì)算出圖像對(duì)應(yīng)點(diǎn)的視差值，然后根據(jù)視差值得到圖像的深度信息。 (6)三維重建立體視覺(jué)的最終目的是為了恢復(fù)景物可視表面的完整信息 ，即三維重建。,立體匹配算法簡(jiǎn)介,立體匹配,立體匹配一直是三維場(chǎng)景結(jié)構(gòu)信息獲取的研究熱點(diǎn)之一,其基本原理是從兩個(gè)視點(diǎn)觀察同一景物以獲取立體像對(duì),匹配出相應(yīng)像點(diǎn),從而計(jì)

8、算出視差并獲得三維信息. 20 世紀(jì)80 年代,美國(guó)麻省理工學(xué)院的Marr 提出了一種視覺(jué)計(jì)算理論并應(yīng)用在雙目匹配上,使兩張有視差的平面圖產(chǎn)生具有深度的立體圖形,從而奠定了立體視覺(jué)發(fā)展的理論基礎(chǔ)。,立體匹配算法簡(jiǎn)介,立體匹配算法,(1)立體匹配算法從本質(zhì)上看，就是以最小的代價(jià)在兩幅圖像上精確的尋找相同的像素點(diǎn)，找到一條最優(yōu)的線路。因此設(shè)計(jì)立體匹配算法就是構(gòu)建一種優(yōu)化模型，求解最優(yōu)解的過(guò)程。(2)從各具特色的雙目立體匹配算法框架來(lái)看,算

9、法有效性主要依賴3 個(gè)因素,即選擇準(zhǔn)確的匹配基元（決策變量）、尋找相應(yīng)的匹配準(zhǔn)則（目標(biāo)函數(shù)和約束條件）和構(gòu)建能夠準(zhǔn)確匹配所選基元的穩(wěn)定算法（求解過(guò)程）。(3)構(gòu)建一個(gè)完整的立體匹配算法應(yīng)從4 個(gè)方面著手:1) 廣義匹配基元與特征參數(shù)選擇;2) 匹配方法及策略;3) 匹配代價(jià)優(yōu)化標(biāo)準(zhǔn);4) 視差提煉方式。,立體匹配算法簡(jiǎn)介,立體匹配中的約束分類——幾何約束,基于圖像幾何的約束的依據(jù)主要是圖像獲取過(guò)程中的幾何學(xué)和光度測(cè)定學(xué)原理。1) 極

10、線約束2) 唯一性約束3) 幾何相似性約束4) 光度測(cè)定學(xué)相容性約束,立體匹配算法簡(jiǎn)介,立體匹配中的約束分類——場(chǎng)景約束,基于場(chǎng)景的約束的依據(jù)主要是利用典型場(chǎng)景中物體的某些共同性質(zhì) 。1) 視差光滑性約束 2) 輪廓視差約束 3) 特征相容性約束 4) 順序約束 5) 互對(duì)應(yīng)約束 6) 相位約束 7) 視差范圍約束8) 視差梯度范圍約束,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于局部約束算法,基于局部約束算法利用興

11、趣點(diǎn)周圍的局部信息進(jìn)行計(jì)算,涉及信息量較少,相應(yīng)的計(jì)算復(fù)雜度較低, 但其對(duì)噪聲較敏感,對(duì)無(wú)紋理區(qū)域、視差不連續(xù)區(qū)域和遮擋區(qū)域匹配效果不理想。,1）區(qū)域匹配算法：本質(zhì)上,基于光度測(cè)量學(xué)不變性原理的區(qū)域匹配算法,常以鄰域窗的灰度為匹配基元,以相關(guān)程度作為判別依據(jù),可以得到較稠密的視差圖?；叶认嚓P(guān)性算法的研究主要集中在匹配代價(jià)聚合的窗口構(gòu)建上,區(qū)域匹配算法的一個(gè)突出缺點(diǎn)是,對(duì)無(wú)紋理區(qū)域常常由于相關(guān)函數(shù)變化的銳度不夠以及難于保留深度不連續(xù)特性,

12、不能取得精確的匹配結(jié)果 。,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于局部約束算法,基于局部約束算法利用興趣點(diǎn)周圍的局部信息進(jìn)行計(jì)算,涉及信息量較少,相應(yīng)的計(jì)算復(fù)雜度較低, 但其對(duì)噪聲較敏感,對(duì)無(wú)紋理區(qū)域、視差不連續(xù)區(qū)域和遮擋區(qū)域匹配效果不理想。,2) 特征匹配算法：本質(zhì)上,基于幾何不變性原理的特征匹配算法克服了區(qū)域匹配算法對(duì)深度不連續(xù)和無(wú)紋理區(qū)域敏感的缺點(diǎn),特別是由于特征基元的統(tǒng)計(jì)特性和數(shù)據(jù)結(jié)構(gòu)的規(guī)則性,使其適合于硬件設(shè)計(jì)。按匹配基元

13、的特征可分為全局特征和局部特征兩大類.全局特征包括多邊形和圖像結(jié)構(gòu)等,多與下文中的全局算法混合使用;局部特征算法常用點(diǎn)、邊緣、線段、小區(qū)域或局部能量等圖像信息作為匹配基元,對(duì)噪聲不敏感,可以得到較精確的匹配 。特征匹配主要存在兩點(diǎn)不足及其改進(jìn)措施:其一,圖像特征的稀疏性決定特征匹配只能得到稀疏視差圖,要得到稠密視差需附加較為復(fù)雜的插值過(guò)程。其二,特征匹配結(jié)果的性能緊密依賴于特征提取的精度。,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于局部

14、約束算法,基于局部約束算法利用興趣點(diǎn)周圍的局部信息進(jìn)行計(jì)算,涉及信息量較少,相應(yīng)的計(jì)算復(fù)雜度較低, 但其對(duì)噪聲較敏感,對(duì)無(wú)紋理區(qū)域、視差不連續(xù)區(qū)域和遮擋區(qū)域匹配效果不理想。,3) 相位匹配算法：基于傅立葉平移定理的相位匹配算法的本質(zhì)，是對(duì)帶通濾波后的時(shí)/ 空2頻域定位性的基元信號(hào)相位信息進(jìn)行處理而得到像對(duì)間的視差。究其本質(zhì),相位匹配就是尋找局部相位相等的對(duì)應(yīng)點(diǎn)。,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于全局約束算法,基于全局約束算法利

15、用對(duì)應(yīng)掃描線或整個(gè)圖像數(shù)據(jù)信息進(jìn)行計(jì)算,著重解決圖像中不確定區(qū)域的匹配問(wèn)題,能到達(dá)全局最優(yōu)解. 全局最優(yōu)算法的本質(zhì)是將對(duì)應(yīng)點(diǎn)的匹配問(wèn)題轉(zhuǎn)化為尋找某一能量函數(shù)的全局最優(yōu)問(wèn)題,通常跳過(guò)代價(jià)聚合步驟,直接計(jì)算視差值. 這類算法的核心環(huán)節(jié)包括:1) 能量函數(shù)構(gòu)造方法;2) 能量函數(shù)優(yōu)化求解策略.,1) 動(dòng)態(tài)規(guī)劃算法：本質(zhì)是在左右圖像對(duì)應(yīng)掃描線上尋找最小匹配代價(jià)路徑的過(guò)程. 常在視差空間圖中應(yīng)用連續(xù)性約束和順序約束,由全局代價(jià)函數(shù)決定匹配代價(jià),規(guī)

16、劃出的路徑由趨于具有最小代價(jià)的匹配點(diǎn)集合構(gòu)成. 動(dòng)態(tài)規(guī)劃算法能有效降低計(jì)算復(fù)雜度. 動(dòng)態(tài)規(guī)劃算法為局部無(wú)紋理區(qū)域提供了全局支持,從而提高了匹配精確度. 動(dòng)態(tài)規(guī)劃算法的最大局限是不能有效融合水平和垂直方向連續(xù)性約束.,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于全局約束算法,基于全局約束算法利用對(duì)應(yīng)掃描線或整個(gè)圖像數(shù)據(jù)信息進(jìn)行計(jì)算,著重解決圖像中不確定區(qū)域的匹配問(wèn)題,能到達(dá)全局最優(yōu)解. 全局最優(yōu)算法的本質(zhì)是將對(duì)應(yīng)點(diǎn)的匹配問(wèn)題轉(zhuǎn)化為尋找某一能

17、量函數(shù)的全局最優(yōu)問(wèn)題,通常跳過(guò)代價(jià)聚合步驟,直接計(jì)算視差值. 這類算法的核心環(huán)節(jié)包括:1) 能量函數(shù)構(gòu)造方法;2) 能量函數(shù)優(yōu)化求解策略.,2) 圖割算法：為解決動(dòng)態(tài)規(guī)劃算法不能充分融合水平和垂直方向連續(xù)性約束問(wèn)題,將匹配問(wèn)題看成是利用這些約束在圖中尋求最小割問(wèn)題. 圖割算法的其本思想是將立體匹配問(wèn)題轉(zhuǎn)化為一種能量函數(shù)的形式,根據(jù)能量函數(shù)構(gòu)造合適的圖,求其最小割(最大流) . 圖割算法的特性表現(xiàn)在:其一,構(gòu)造能量函數(shù)用于圖割求解時(shí),其本

18、身必須滿足一定的約束條件；其二,不同的能量函數(shù)有著不同的構(gòu)圖方式.,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于全局約束算法,基于全局約束算法利用對(duì)應(yīng)掃描線或整個(gè)圖像數(shù)據(jù)信息進(jìn)行計(jì)算,著重解決圖像中不確定區(qū)域的匹配問(wèn)題,能到達(dá)全局最優(yōu)解. 全局最優(yōu)算法的本質(zhì)是將對(duì)應(yīng)點(diǎn)的匹配問(wèn)題轉(zhuǎn)化為尋找某一能量函數(shù)的全局最優(yōu)問(wèn)題,通常跳過(guò)代價(jià)聚合步驟,直接計(jì)算視差值. 這類算法的核心環(huán)節(jié)包括:1) 能量函數(shù)構(gòu)造方法;2) 能量函數(shù)優(yōu)化求解策略.,3) 人

19、工智能算法：Marr 提出的重要理論之一是立體視覺(jué)的不確定性,而且立體匹配問(wèn)題可以看作是代價(jià)函數(shù)的優(yōu)化問(wèn)題. 智能算法的基本思想是在約束條件下, 首先建立以基元匹配的相似性條件和相容性條件為基礎(chǔ)的最優(yōu)準(zhǔn)則;然后進(jìn)行點(diǎn)集的最優(yōu)匹配搜索, 使各基元的相似性和相容性達(dá)到總體最優(yōu).,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于全局約束算法,基于全局約束算法利用對(duì)應(yīng)掃描線或整個(gè)圖像數(shù)據(jù)信息進(jìn)行計(jì)算,著重解決圖像中不確定區(qū)域的匹配問(wèn)題,能到達(dá)全局最優(yōu)

20、解. 全局最優(yōu)算法的本質(zhì)是將對(duì)應(yīng)點(diǎn)的匹配問(wèn)題轉(zhuǎn)化為尋找某一能量函數(shù)的全局最優(yōu)問(wèn)題,通常跳過(guò)代價(jià)聚合步驟,直接計(jì)算視差值. 這類算法的核心環(huán)節(jié)包括:1) 能量函數(shù)構(gòu)造方法;2) 能量函數(shù)優(yōu)化求解策略.,A：基于神經(jīng)網(wǎng)絡(luò)的匹配算法，該算法的本質(zhì)是根據(jù)所構(gòu)建網(wǎng)絡(luò)的形式,通過(guò)迭代學(xué)習(xí)算法將匹配代價(jià)函數(shù)及其匹配固有約束轉(zhuǎn)化成能量最小化尋優(yōu)過(guò)程,網(wǎng)絡(luò)的動(dòng)態(tài)變化過(guò)程是多個(gè)約束的極小化實(shí)現(xiàn)過(guò)程.B：基于遺傳算法的匹配算法，該算法的本質(zhì)是根據(jù)采用的匹配基

21、元和基因構(gòu)建策略,將問(wèn)題的解編碼到染色體中,考慮匹配約束構(gòu)造適當(dāng)?shù)倪m應(yīng)度函數(shù),利用進(jìn)化機(jī)制獲得匹配最優(yōu)解,是一種利用自然選擇和進(jìn)化思想在高維空間中尋優(yōu)的方法. 此類算法性能差異主要體現(xiàn)在4 個(gè)方面:1) 基因構(gòu)建策略;2) 染色體編碼方式;3) 匹配約束下適應(yīng)度函數(shù)的構(gòu)建;4) 進(jìn)化機(jī)制的實(shí)施.,立體匹配算法簡(jiǎn)介,立體匹配算法分類——基于全局約束算法,基于全局約束算法利用對(duì)應(yīng)掃描線或整個(gè)圖像數(shù)據(jù)信息進(jìn)行計(jì)算,著重解決圖像中不確定區(qū)域的匹

22、配問(wèn)題,能到達(dá)全局最優(yōu)解. 全局最優(yōu)算法的本質(zhì)是將對(duì)應(yīng)點(diǎn)的匹配問(wèn)題轉(zhuǎn)化為尋找某一能量函數(shù)的全局最優(yōu)問(wèn)題,通常跳過(guò)代價(jià)聚合步驟,直接計(jì)算視差值. 這類算法的核心環(huán)節(jié)包括:1) 能量函數(shù)構(gòu)造方法;2) 能量函數(shù)優(yōu)化求解策略.,4) 其他全局算法：A協(xié)作算法的靈感源于人類視覺(jué)計(jì)算模型,其所用的非線性迭代操作在整體行為上類似于全局算法.B非線性擴(kuò)散算法的研究熱點(diǎn)集中在提高遮擋問(wèn)題的處理性能上.C置信度傳播算法，此算法能得到全局算法的精度和局部算

23、法的效率.,立體匹配技術(shù)的發(fā)展趨勢(shì),立體匹配研究重點(diǎn),雙目立體匹配問(wèn)題是一個(gè)“病態(tài)”問(wèn)題. 雙目立體匹配實(shí)施要考慮諸多因素,并以計(jì)算復(fù)雜度和穩(wěn)定性等總體性能指標(biāo)來(lái)衡量方案實(shí)施的可行性和有效性。1) 多種立體匹配算法有效融合。2) 研究新穎的特定匹配約束以及合理變通利用匹配約束。①如何有效地保護(hù)視差表面的不連續(xù)信息; ②如何避免出現(xiàn)局部最優(yōu)的問(wèn)題; ③如何檢測(cè)匹配不可見(jiàn)的遮擋區(qū)域。3) 能量函數(shù)構(gòu)造及其最優(yōu)求解策略是全局算法的核心問(wèn)

24、題。4) 紋理缺乏、特征缺失、遮擋和不連續(xù)的圖像區(qū)域,是立體匹配研究中的一個(gè)難點(diǎn)和重點(diǎn)。①降低算法對(duì)遮擋的敏感性,從而減輕遮擋的不良影響 ; ②對(duì)遮擋進(jìn)行檢測(cè)并標(biāo)示出遮擋的存在,雖然并不對(duì)其進(jìn)行解決,但可以避免由其引起的錯(cuò)誤; ③為遮擋問(wèn)題建立專門的幾何模型,對(duì)于遮擋問(wèn)題進(jìn)行特別處理。5) 對(duì)匹配算法評(píng)價(jià)方法的研究。精度，復(fù)雜度，可靠性，通用性。,立體匹配技術(shù)的發(fā)展趨勢(shì),立體匹配發(fā)展趨勢(shì),1) 完善雙目立體匹配總體理論框架. 特別是

25、在復(fù)雜場(chǎng)景中,如何提高算法的去歧義匹配和抗干擾能力,如何降低計(jì)算復(fù)雜度和運(yùn)算量,仍需要進(jìn)行更加深入的探索和研究。2) 立體匹配與重建相結(jié)合.匹配結(jié)果約束著內(nèi)插的重建;反過(guò)來(lái),重建結(jié)果又引導(dǎo)著正確的匹配.3) 充分挖掘人工智能算法的發(fā)展空間,建立基于知識(shí)、規(guī)則、模型的智能化匹配算法. 4) 建立實(shí)時(shí)、精確以及穩(wěn)定的實(shí)用立體匹配算法. 5) 立體匹配與認(rèn)知科學(xué)緊密結(jié)合. 認(rèn)知科學(xué)中的圖形組織規(guī)則對(duì)立體匹配中的圖像分割問(wèn)題有著重要的指