立體匹配技術淺析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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