二維立體匹配模型及其數值解法

王春艷，朱華平，胡鵬輝

武漢理工大學 理學院，武漢 430070

1 引言

立體匹配是計算機視覺領域的重要研究課題之一，其主要目的是獲取立體圖像對的空間相同點坐標，進而從二維圖像獲取空間場景的深度信息并進行三維重建。目前，該領域的研究熱點和難點之一是，提出適用于左右匹配點不全在同一條極線上，即極線校準不精確問題的通用模型[1]，以及如何克服該模型對應能量泛函中數據項的非凸性，避免陷入局部最優，進而得到全局最優解的方法。云挺等[2]利用極線考慮立體圖像對匹配點在不同相對位置下的數據項，適用于幾乎所有的圖像對，對提出的能量泛函應用梯度下降法求解。但是該模型需要計算極線方程，且使用的算法容易陷入局部最優，在迭代過程中還需要對圖像對進行插值計算。因此這種模型難以廣泛應用，特別是在設備參數未知的情況下。Rudin等[3]提出連續全變分正則化模型，為克服該模型數據項的非凸性，Pock等[4-5]引入未知函數的示性函數，將原變分問題改寫為高一維空間中的凸問題，然后利用對偶公式表示為鞍點問題，最后利用原始對偶近似點的方法求全局最優解，避免了用歐拉法求解全變分出現分母為零的情況。然而該模型僅能計算一維視差的情況，意味著僅考慮了左右匹配點極線在水平線上的情況。

本文重點研究了二維立體匹配模型及其數值解法。基于標準的笛卡爾理論，將二維立體匹配模型表示為四維空間上的變分問題。與一維模型不同的是，二維模型標準化后仍是非凸的，因此需要對非凸性變分問題的數據項進行松弛。利用對偶理論中的雙共軛函數對其進行對偶化，改寫為二維原始對偶立體匹配模型。基于該模型與鞍點結構優化模型的相似性，從而使用一階原始對偶算法[6]求解該模型。

2 模型的建立

2.1 一維立體匹配模型

一維立體匹配模型[3]可以表述為下面的變分問題：

其中u:Ω→A是未知函數；Ω?R2表示圖像區域；是函數u的取值范圍；x=(x,y)T表示圖像坐標。假定函數u滿足第二邊界條件。

式（1）的第一項表示正則項，用來平滑解u。第二項表示數據項，其值表示在點x處當視差值為u時的匹配代價。

模型（1）對應的離散形式為：

在文獻[4]中，利用未知函數的示性函數對模型進行凸表示：

得到與一維模型（1）等價的高維問題：

然后利用對偶公式，得到等價的鞍點問題：

上述對偶模型的離散形式為：

之后利用原始對偶近似點算法[7]進行求解。

2.2 二維立體匹配模型

傳統的立體匹配模型通常是在一個維度上進行搜索，對立體圖像對校準精度要求很高，當達不到這個要求時，得到的視差圖像精度不高。為能處理這個問題，在一維模型中加入另一維度的視差搜索函數，得到變分問題：

模型（2）對應的離散形式為：

不難看出，一維模型的視差僅由x方向視差決定，二維模型的視差由x、y兩個方向的視差決定，考慮了極線校準不精確情況，可以處理匹配點在任意相對位置的情況。

3 模型的凸表示

本文將對提出的二維模型進行凸表示，使之成為鞍點問題。首先利用標準的笛卡爾理論改寫二維立體匹配模型（2）為高維空間中的變分問題。然后利用雙共軛函數，對正則項和數據項分別進行對偶表示。

定義1二值函數定義為：

易知φ、φ的可行集為：

上面定義了如何由u、v得到φ、φ。反過來，若已知 φ、φ，可由式（7）、（8）得到 u、v：

上面是關于u、v和φ、φ的關系。接下來將用φ、φ來表示變分問題（2），目的是把變分問題改寫為凸的變分問題。

首先使得變分問題在凸集范圍內求解，也就是要把φ、φ可行集（5）、（6）凸松弛，得到：

定理1變分問題（2）等價于高維的變分問題：

變分問題（9）最優解可以通過式（7）、（8）表示為變分問題（2）的最優解。

證明首先問題（2）正則項可以分別由φ、φ表示，利用推廣的Co-area公式，得到：

這里?x表示僅對3自變量函數進行x的梯度運算。

其次用 φ、φ 改寫問題（2）數據項，從式（3）、（4）可得。求解φ、φ在變量α、β的導數，則有：

將式（10）、（11）、（14）代入變分問題（2）便可得到定理1。證畢。

與一維變分問題不同的是，這里變分問題（9）仍為非凸的，求解模型得不到最優解。關于其非凸性有如下結論。

性質變分問題（9）關于φ、φ是凸的，當且僅當對于任意點 (φ,φ),(ξ,ψ)∈D ，有(φα-ξα)?(φβ-ψβ)≥0 。

證明能量泛函（9）是凸的，也就是對任意的θ∈[0,1]，有下式成立：

由于梯度算子及1范數的凸性，上式等價于：

也就是對任意點 (x,α,β)∈Ω×A×B 滿足 (φα-ξα)?(φβ-ψβ)≥0。上述為等價條件。證畢。

易知，關于變分問題凸的充要條件不是自然成立的。因此將對數據項進行凸松弛[8-9]，用其雙共軛函數來近似。首先對雙共軛函數[10-13]進行說明。

函數 f(x)關于x的Legendre-Fenchel共軛函數為：

函數 f(x)關于x的Legendre-Fenchel雙共軛函數為：

若 f(x)關于 x 是凸的，則 f??(x)=f(x)；否則，f??(x)是 f(x)的最小凸包（凸包絡）。

定理2變分問題（9）的最小凸包為：

其中

其次，對于數據項進行對偶化的處理。由性質可知，數據項是非凸的，因此用雙共軛函數僅僅可以得到最小凸包。若數據項表示為：

則其共軛函數為：

由Dirac Delta函數的性質可知，若u(x)=a,v(x)=b,則有：

數據項的雙共軛函數為：

為使上式成立且計算簡便，使得下式成立：

上式成立的一個條件便是：

即對任意的 x、α、β，有：

若滿足上述條件（16），則有：

把對偶變量 p、q滿足的條件整合，則有定理集合G成立，把正則項和數據項代入變分問題（9）則有定理成立。證畢。

上述對偶模型的離散形式為：

其為典型的鞍點問題，接下來將對該問題進行求解。

本文的最終目的還是解決二維變分問題（2），下面說明怎樣由凸松弛后變分問題得到的最優解得到變分問題（2）的最優解。假設松弛后變分問題的最優解為φ?、φ?，通過下式得到：

要注意的是，這里u、v并非變分問題（2）的最優解，僅僅是在一定范圍的次最優解。

不難看出，這里已經建立鞍點問題（9）與模型（2）的對應關系，即鞍點優化模型與二維立體匹配模型的對應關系。

從二維模型（2）的定義以及其等價的鞍點形式可知，當其中y方向視差v=0，二維模型就變為一維模型，與二維模型等價的鞍點問題也變為與一維模型等價的鞍點問題。由此可以得出，二維模型是一維模型的推廣。

4 模型的原始對偶算法

文獻[6]提出了一階原始對偶算法，用來解決鞍點結構的優化問題。因此可以直接得到關于凸松弛后變分問題（15）的算法，如下所示。

算法1

（1）初始化：選取可行集 D×G 中變量 (φ,φ)×(p,q)，且令，迭代步長為 τ,σ＞0 且滿足

（2）迭代：

（3）計算能量泛函（2）的值，當迭代的能量差小于給定的閾值停止迭代；否則，令n=n+1，轉（2）。

算法1中P表示投影算子，PD是向集合D投影，PG是向集合G投影。原始變量集投影算子PD用簡單的截斷函數實現。對偶變量集PG用下式進行投影運算，關于x有：

關于 pα、qβ的投影就是求下述最優問題，對于每點x,α,β∈Ω×A×B有：

本文中梯度算子用向前差分進行近似，散度算子用向后差分進行近似。因此關于初始化迭代步長關系式中，梯度算子的范數為‖‖?=12。

5 實驗結果與分析

為測試并評價本文算法，在Matlab 2017a平臺上，對文獻[14]提供的Middlebury立體視覺2014版數據庫中15種場景的1/4像素雙目圖像進行實驗，并對實際獲取的真實場景圖像進行了求取視差的實驗與結果分析，采用一維模型[2]和本文的二維模型進行比較。

5.1 標準庫實驗結果

用全部標準庫中的立體圖像對進行測試。表1給出本文結果與一維立體匹配在Middlebury網站的測評結果。本文給出兩種誤差，分別為非遮擋誤匹配率（nocc，%）和所有區域誤匹配率（all，%），誤差閾值為1，并且給出了算法運行時間的對比。實驗數據中存在關于亮度變化的立體圖像對，對于有光照影響的圖像對采用文獻[15]中的關于梯度的匹配代價作為數據項。

表1 圖像精度及收斂速度比較

圖1 部分標準庫圖像實驗結果對比圖

圖2 真實場景

其中精度由錯誤率衡量，收斂速度由迭代時間進行度量，由數據可以得到二維模型比一維模型相比，nocc精度降低4.69%，all精度降低4.11。這是因為在二維模型中存在凸松弛，盡管是最小凸包，但是與真實最優解存在誤差。關于迭代速度，一維模型、二維模型有快有慢。

圖1給出部分標準庫圖像實驗對比圖，可以看到二維模型視差圖像視覺效果和一維模型相當。

二維模型可以處理標準庫經校準的圖像，且效果與一維模型相差無幾。

5.2 實拍場景圖像的實驗

為了驗證算法的實用性，實驗模擬了室內環境，用普通移動拍照設備得到4組場景圖，并進行了縮放處理，得到實驗所用立體圖像對。然后用本文模型和一維模型得到的視差圖像進行對比，如圖2。

每組立體圖像對均有明顯的極線偏差。對本文模型與一維模型得到的視差圖進行對比，可以發現本文模型可以處理極線校準不精確的圖像，在細節部分更加清晰，得到的視差圖像效果更好。一維模型處理真實場景圖像變得很困難。

6 結束語

本文針對一維立體匹配模型極線校準不精確的問題，提出了二維立體匹配模型及其原始對偶算法。通過實驗證明，二維模型可以處理標準庫中圖像。相比一維模型，雖然由于其中數據項的松弛，二維模型的精度平均會降低4%～5%，但是對于現實場景的圖像對進行實驗，二維模型可以處理真實場景圖像，與一維模型相比，得到的視差圖更加精確。其中松弛方法導致的標準圖像庫中實驗精度下降問題，是下一步研究的課題。