王春艷，朱華平，胡鵬輝

武漢理工大學(xué) 理學(xué)院，武漢 430070

1 引言

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

本文重點(diǎn)研究了二維立體匹配模型及其數(shù)值解法?；跇?biāo)準(zhǔn)的笛卡爾理論，將二維立體匹配模型表示為四維空間上的變分問題。與一維模型不同的是，二維模型標(biāo)準(zhǔn)化后仍是非凸的，因此需要對(duì)非凸性變分問題的數(shù)據(jù)項(xiàng)進(jìn)行松弛。利用對(duì)偶理論中的雙共軛函數(shù)對(duì)其進(jìn)行對(duì)偶化，改寫為二維原始對(duì)偶立體匹配模型?；谠撃Ｐ团c鞍點(diǎn)結(jié)構(gòu)優(yōu)化模型的相似性，從而使用一階原始對(duì)偶算法[6]求解該模型。

2 模型的建立

2.1 一維立體匹配模型

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

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

式（1）的第一項(xiàng)表示正則項(xiàng)，用來平滑解u。第二項(xiàng)表示數(shù)據(jù)項(xiàng)，其值表示在點(diǎn)x處當(dāng)視差值為u時(shí)的匹配代價(jià)。

模型（1）對(duì)應(yīng)的離散形式為：

在文獻(xiàn)[4]中，利用未知函數(shù)的示性函數(shù)對(duì)模型進(jìn)行凸表示：

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

然后利用對(duì)偶公式，得到等價(jià)的鞍點(diǎn)問題：

上述對(duì)偶模型的離散形式為：

之后利用原始對(duì)偶近似點(diǎn)算法[7]進(jìn)行求解。

2.2 二維立體匹配模型

傳統(tǒng)的立體匹配模型通常是在一個(gè)維度上進(jìn)行搜索，對(duì)立體圖像對(duì)校準(zhǔn)精度要求很高，當(dāng)達(dá)不到這個(gè)要求時(shí)，得到的視差圖像精度不高。為能處理這個(gè)問題，在一維模型中加入另一維度的視差搜索函數(shù)，得到變分問題：

模型（2）對(duì)應(yīng)的離散形式為：

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

3 模型的凸表示

本文將對(duì)提出的二維模型進(jìn)行凸表示，使之成為鞍點(diǎn)問題。首先利用標(biāo)準(zhǔn)的笛卡爾理論改寫二維立體匹配模型（2）為高維空間中的變分問題。然后利用雙共軛函數(shù)，對(duì)正則項(xiàng)和數(shù)據(jù)項(xiàng)分別進(jìn)行對(duì)偶表示。

定義1二值函數(shù)定義為：

易知φ、φ的可行集為：

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

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

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

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

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

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

這里?x表示僅對(duì)3自變量函數(shù)進(jìn)行x的梯度運(yùn)算。

其次用 φ、φ 改寫問題（2）數(shù)據(jù)項(xiàng)，從式（3）、（4）可得。求解φ、φ在變量α、β的導(dǎo)數(shù)，則有：

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

與一維變分問題不同的是，這里變分問題（9）仍為非凸的，求解模型得不到最優(yōu)解。關(guān)于其非凸性有如下結(jié)論。

性質(zhì)變分問題（9）關(guān)于φ、φ是凸的，當(dāng)且僅當(dāng)對(duì)于任意點(diǎn) (φ,φ),(ξ,ψ)∈D ，有(φα-ξα)?(φβ-ψβ)≥0 。

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

由于梯度算子及1范數(shù)的凸性，上式等價(jià)于：

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

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

函數(shù) f(x)關(guān)于x的Legendre-Fenchel共軛函數(shù)為：

函數(shù) f(x)關(guān)于x的Legendre-Fenchel雙共軛函數(shù)為：

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

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

其中

其次，對(duì)于數(shù)據(jù)項(xiàng)進(jìn)行對(duì)偶化的處理。由性質(zhì)可知，數(shù)據(jù)項(xiàng)是非凸的，因此用雙共軛函數(shù)僅僅可以得到最小凸包。若數(shù)據(jù)項(xiàng)表示為：

則其共軛函數(shù)為：

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

數(shù)據(jù)項(xiàng)的雙共軛函數(shù)為：

為使上式成立且計(jì)算簡(jiǎn)便，使得下式成立：

上式成立的一個(gè)條件便是：

即對(duì)任意的 x、α、β，有：

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

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

上述對(duì)偶模型的離散形式為：

其為典型的鞍點(diǎn)問題，接下來將對(duì)該問題進(jìn)行求解。

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

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

不難看出，這里已經(jīng)建立鞍點(diǎn)問題（9）與模型（2）的對(duì)應(yīng)關(guān)系，即鞍點(diǎn)優(yōu)化模型與二維立體匹配模型的對(duì)應(yīng)關(guān)系。

從二維模型（2）的定義以及其等價(jià)的鞍點(diǎn)形式可知，當(dāng)其中y方向視差v=0，二維模型就變?yōu)橐痪S模型，與二維模型等價(jià)的鞍點(diǎn)問題也變?yōu)榕c一維模型等價(jià)的鞍點(diǎn)問題。由此可以得出，二維模型是一維模型的推廣。

4 模型的原始對(duì)偶算法

文獻(xiàn)[6]提出了一階原始對(duì)偶算法，用來解決鞍點(diǎn)結(jié)構(gòu)的優(yōu)化問題。因此可以直接得到關(guān)于凸松弛后變分問題（15）的算法，如下所示。

算法1

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

（2）迭代：

（3）計(jì)算能量泛函（2）的值，當(dāng)?shù)哪芰坎钚∮诮o定的閾值停止迭代；否則，令n=n+1，轉(zhuǎn)（2）。

算法1中P表示投影算子，PD是向集合D投影，PG是向集合G投影。原始變量集投影算子PD用簡(jiǎn)單的截?cái)嗪瘮?shù)實(shí)現(xiàn)。對(duì)偶變量集PG用下式進(jìn)行投影運(yùn)算，關(guān)于x有：

關(guān)于 pα、qβ的投影就是求下述最優(yōu)問題，對(duì)于每點(diǎn)x,α,β∈Ω×A×B有：

本文中梯度算子用向前差分進(jìn)行近似，散度算子用向后差分進(jìn)行近似。因此關(guān)于初始化迭代步長(zhǎng)關(guān)系式中，梯度算子的范數(shù)為‖‖?=12。

5 實(shí)驗(yàn)結(jié)果與分析

為測(cè)試并評(píng)價(jià)本文算法，在Matlab 2017a平臺(tái)上，對(duì)文獻(xiàn)[14]提供的Middlebury立體視覺2014版數(shù)據(jù)庫(kù)中15種場(chǎng)景的1/4像素雙目圖像進(jìn)行實(shí)驗(yàn)，并對(duì)實(shí)際獲取的真實(shí)場(chǎng)景圖像進(jìn)行了求取視差的實(shí)驗(yàn)與結(jié)果分析，采用一維模型[2]和本文的二維模型進(jìn)行比較。

5.1 標(biāo)準(zhǔn)庫(kù)實(shí)驗(yàn)結(jié)果

用全部標(biāo)準(zhǔn)庫(kù)中的立體圖像對(duì)進(jìn)行測(cè)試。表1給出本文結(jié)果與一維立體匹配在Middlebury網(wǎng)站的測(cè)評(píng)結(jié)果。本文給出兩種誤差，分別為非遮擋誤匹配率（nocc，%）和所有區(qū)域誤匹配率（all，%），誤差閾值為1，并且給出了算法運(yùn)行時(shí)間的對(duì)比。實(shí)驗(yàn)數(shù)據(jù)中存在關(guān)于亮度變化的立體圖像對(duì)，對(duì)于有光照影響的圖像對(duì)采用文獻(xiàn)[15]中的關(guān)于梯度的匹配代價(jià)作為數(shù)據(jù)項(xiàng)。

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

圖1 部分標(biāo)準(zhǔn)庫(kù)圖像實(shí)驗(yàn)結(jié)果對(duì)比圖

圖2 真實(shí)場(chǎng)景

其中精度由錯(cuò)誤率衡量，收斂速度由迭代時(shí)間進(jìn)行度量，由數(shù)據(jù)可以得到二維模型比一維模型相比，nocc精度降低4.69%，all精度降低4.11。這是因?yàn)樵诙S模型中存在凸松弛，盡管是最小凸包，但是與真實(shí)最優(yōu)解存在誤差。關(guān)于迭代速度，一維模型、二維模型有快有慢。

圖1給出部分標(biāo)準(zhǔn)庫(kù)圖像實(shí)驗(yàn)對(duì)比圖，可以看到二維模型視差圖像視覺效果和一維模型相當(dāng)。

二維模型可以處理標(biāo)準(zhǔn)庫(kù)經(jīng)校準(zhǔn)的圖像，且效果與一維模型相差無幾。

5.2 實(shí)拍場(chǎng)景圖像的實(shí)驗(yàn)

為了驗(yàn)證算法的實(shí)用性，實(shí)驗(yàn)?zāi)M了室內(nèi)環(huán)境，用普通移動(dòng)拍照設(shè)備得到4組場(chǎng)景圖，并進(jìn)行了縮放處理，得到實(shí)驗(yàn)所用立體圖像對(duì)。然后用本文模型和一維模型得到的視差圖像進(jìn)行對(duì)比，如圖2。

每組立體圖像對(duì)均有明顯的極線偏差。對(duì)本文模型與一維模型得到的視差圖進(jìn)行對(duì)比，可以發(fā)現(xiàn)本文模型可以處理極線校準(zhǔn)不精確的圖像，在細(xì)節(jié)部分更加清晰，得到的視差圖像效果更好。一維模型處理真實(shí)場(chǎng)景圖像變得很困難。

6 結(jié)束語

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