第四章 立体视觉 立体视觉是仿照人类利用双目线索感知距离的方法实现对三维信息的感知， 在实现上采用基于三角测量的方法运用两个或多个摄象机对同一景物从不同位置 成象，并进而从视差中恢复距离。 立体视觉中一般需要解决三方面的问题： b f d C A l l aP A B C P l l a l b r r Pr 图 4.1视差测距原理图 V 图象面上的视差计算 V 由视差恢复某些点的三维坐标 V 由稀疏的三维数据恢复表面。 4.1一般性原理 最简单的情况如图 4.1所示 C Cl r, 分别为左、右二个相机的光心 Cl 与 Cr 之间的距离为 b，相机焦距为 f。 物体上的点 P在左、右相机图象面上 的投影点分别为 P Pl r, ， 令 A P ll l a= ， A P lr r b= ， P B ar = ，则由 相似三角形有： d f d a a lb ? = + (4.1) d f d b l l a b l a a b b ? = ? + + + + (4.2) 由 (4.1)、 (4.2)有 b ba a l ll bla ? ?= (4.3) bab b ll bf l lafd ?= += (4.4) 由上式可以看出，距离 d与 b、 f 和 l la b? 有关。 l la b? 称为点 P 在左、右两个 图象面上形成的视差，它表示了 P 点在左、右两幅图象中成像点的位置差异。 由于 b、 f 是已知的，因此，要实现双目立体视差测距，最关键的就是要求得视 差 l la b? ，即要实现空间中同一点 P 在左、右两幅图象上的投影点之间的对应。 两幅图象间对应点的寻求称为两幅图象的配准。 P1 P2 P C1 C2 E1 E2 I1 I2 DE1 DE2 图 4.2 内极点与内极线 4.2 内极点、内极线与内极平面 4.2.1 一般情况 光心线与视平面 1P 的交点 1E 称为视平 面 1P 的 内极点 (Epipolar)，光心线与视平面 2P 的交点 2E 称为视平面 2P 的 内极点 。 设空间中有一点 P ，在 1P 上的投影为 I1 ，则将由点 1I 和光心线所确定的平 面称为内极平面 (Epipolar plane)，内极平面与视平面 P1 的交线称为点 I1 的内极线 (Epipolar)，记为 1ED 。对称地，由点 I2 和光心线所确定的平面与视平面 2P 的交线 称为点 2I 的内极线，记为 2ED 。 性质： 视平面 1P 上任何内极线 1ED 必然通过内极点 1E ，视平面 2P 上任何内极线 2E D 必然通过内极点 2E 。内极线 2E D 的解释是，给定 1I ，它在 2P 上可能的对应点 一定在内极线 2ED 上；反之亦然。 作用： 降低搜索空间 P1 P2 P C1 C 2 E1 E2 I1 I2DE 1 DE 2 Y' X' Y X Z O Y" X" Z" O"O' Z' h1 h 2 1 图 4.3 世界坐标系与摄象机坐标系 内极点和内极线的计算。 考虑一般情况，摄象机 C1 的坐标系 ZYXO ′′′′ 是从世界坐标系 OXYZ 原点经旋 转 ( ))1(1 ijrR = ( , , , )i j = 1 2 3 和平移 ( )tCCC ZYXh 1111 = 形成的，摄象机 C2 的 坐标系 ′′ ′′ ′′ ′′O X Y Z 是从世界坐标系 OXYZ 原点经旋转 ( ))2(2 ijrR = )3,2,1,( =ji 和平移( ) t CCC ZYXh 2222 = 形成的，如图 4.3所 示。 设 H h h= ?2 1， 则 C E1 1在 OXYZ 坐标下的 N矢量为 ( )HNmC =1 ， C E2 2在 OXYZ 坐标下的 N矢量为 21 CC mm ?= 于是在视平面 P1上，内极点 E1 的 N矢量为 11 1 C t C mRm =′ (4.5) 类似地，在视平面 P2 上，内极点 E2的 N矢量为 22 2 C t C mRm =′ (4.6) 设点 P在视平面 P1上象点的 N矢量为 ′mI1 ，在 OXYZ 坐标下的 N矢量为 11 1 II mRm ′= (4.7) 内极平面在 OXYZ 坐标下的 N矢量为 [ ] ( ) 2121 1 CICI mmkmmNn ×=×= (4.8) 视平面 P2 在 OXYZ 坐标下的 N矢量为 ? ? ? ? ? ? ? ? ? ? = )2( 33 )2( 23 )2( 13 2 r r r nP (4.9) 内极线 DE2 在 OXYZ 坐标下的方向矢量为 [ ] ( ) ( ) 22122122 12 PCIPCIPDE nmmRknmmknnkm ××′=××=×= (4.10) 其中， kkk ,, 21 为归一化常数。 内极线 DE2 在 ′′ ′′ ′′ ′′O X Y Z 坐标下的方向矢量为 ( ) 2212 12 PCI t DE nmmRkRm ××′=′′ (4.11) 结论 :当立体视觉系统的内部参数已知时，对任意给定的视平面 1P 上的一点 1I ，可根 据其在 1P 上的 N 矢量 1Im′ ，利用 (4.11)式求得其在视平面 2P 上对应点 2I 所在内极线 2ED 的方向矢量 2DEm ′′ 。 实际上，多数的立体视系统其摄象机之 间保持平行的关系，即满足 R R1 2= (4.12) 满足 (4.12)式的立体视觉系统称为平行立 体视系统。 4.2.2 平行立体视中的内极线约束 为讨论方便，通常取 P1 的坐标系为世界坐标 系，即 ( )th 0001 = ， IRR == 21 设 tbbbbh ),,( 3212 == ，则称表示摄象机平移的矢量 tbbbb ),,( 321= 为平移基矢量。平移基 矢量 b与摄象机坐标系的关系如图 4.4所示。 在不考虑 N矢量方向的情况下，有 定理 4.1 平移基矢量为 b 的平行立体视在视平面上的内极点的 N 矢量为 ][bNu = ，所 有的内极线均过内极点。 进一步，有， 命题 4.1 在基矢量为 b 的平行立体视中，过 N 矢量为 m 的点的内极线的 N 矢量 n(m) 由下式给定 , [ ]bmNmn ×=)( (4.13) O X Y O' X' Y' o o' x y x' y' Z Z' P p p' b 图 4.4 平行立体视与平移基矢量 b 在立体视中实际可测的是视差，而视觉系统要求的却是距离，因此视差与距离 的关系是立体视系统研究的重要内容之一。 设空间点 P 在两个视平面上的 N 矢量分别为 m 和 m'， m 与 m'之间的夹角为 θ( 20 pq ≤≤ )，称为点 P 的视差。 视差 θ 的大小，实质上反映了点 P 与两个视平面位置关系，由此可以计算获得 点 P 的三维信息。 称函数 ) ,(cos)( 1 mmm ?=q 在二维平面上所形成的二维图为视差图。 除了视差以外，视点 O 到空间点 P 的距离 r(m)也反映 P 的空间位置，称函数 r(m)所形成的二维图为距离图。 命题 4.2 平移基矢量为 b 的平行立体视的距离图与视差图的关系如下 , )(ctg||)(,,||),()( mmnmbmbmr q+= (4.14) 其中， n(m)为内极线矢量， q 为视差。 证明：如图 4.4，用下列表示记矢量 → OP 和 →′ PO , 'mrPO rmOP =′ = → → (4.15) 其中 r, r'为正实数。从而有 'mrrmb ?= (4.16) 现在考虑矢量 b， m， n的矢量混合积，并注意到 qsin' ±=× mm 0),( =× nmm 于是有， qsin' )',('),'('),( ),''(),(|,,| r mmnrnmmrnmmr nmmrrmnmbnmb ±= ×?=×?×= ×?=×= (4.17) 另一方面，对 (4.16)式两边作 m的标量积有，并考虑 qcos)',( =mm ，于是有 qcos'),'('),(),'(),( rrmmrmmrmrmrmmb ?=?=?= (4.18) 将 (4.17)式代入 (4.18)式并整理，即得 (4.14)式结果。 定理 4.2 基矢量为 b的平行立体视的距离图与视差图满足 )(ctg||||),()( mmbmbmr q×+= (4.19) 证明：由于 [ ] bmbm bmbmbm bmmbbmNmbmnmb ×=× ××=××=×= ),(,,,,)(,, (4.20) 将其代入 (4.14)式即得。 [证毕 ] 上述定理说明，距离图 r(m)可以由视差图 θ 和基矢量 b唯一的确定。 命题 4.2和定理 4.2说明了，对于平行立体视，只要已知基矢量 b和视差 )(mq ，距离 图 r(m)就可以计算出来。 由定理 4.1知，基矢量为 b的平行立体视的 内 极点为 ][bNu = ，即应有 0, ≥= kkub ， 从而有， 推论 4.1 设内极点的 N矢量为 u，则距离图可由下式计算。 )](ctg||||),[()( mmumukmr q×+= (4.21) 4.3 立体视中的配准 根据配准所采用的基元以及成象几何的不同，配准策略在很大程度上也是不同 的，其中根据配准方法的不同可分为基于面积的配准和基于特征的配准，根据成象 几何的不同可分为平行光轴配准和非平行光轴配准。 4.3.1 双目配准 在配准中可以有基于面积、特征等的不同方法，在计算的实现上可以直接计算 或采用层次方法实现。 4.3.1.1 基于面积的配准 基本思想： 把一幅图象中某一象点的灰度邻域作为模板，在另一幅图象中搜索具有相同 (或 相似 )灰度值分布的对应点邻域，从而实现两幅图象的配准。在搜索过程中，通常是 以互相关函数作为两个搜索邻域间的相似性测度。 设 ),( yxfL 和 ),( yxfR 分别为双目立体视觉中的左、右两幅图象， ),( LL yx 是),( yxf L 中的一点。取以 ),( LL yx 为中心的某一邻域作为模板 T，其大小为 nm × 。现在 ),( yxfR 中平移模板 T，并假设 T在水平方向平移 x? ，在垂直方向平移 y? 后，它所覆 盖下的 ),( yxfR 的第 k个子图为 kS 。若 T与 kS 相同，则它们的差为零，否则不为零。由 此定义 T与 kS 之间差别的测度为 ∑∑ ∑∑ ∑∑+??∑∑ ?= = = = = = == = m i n j m i n j m i n jkk m i n j kk jiTjiTjiSjiSjiTjiSSTD 1 1 1 1 1 1 22 1 1 2 )],([),(),(2)],([=)],(),([),( (4.22) 当 D T Sk( , )最小时， T与 Sk 达到最佳匹配。 使 D T Sk( , )达到最小等价使 ∑ ∑ ? = = m i n j k jiTjiS 1 1 )],(),([ 达到最大，归一化 ∑ ∑ ∑ ∑? ∑ ∑ ? =?? = = = = = = m i n j m i n jk m i n j k jiTjiS jiTjiS yxC 1 1 1 1 2/122/12 1 1 })],([{})],([{ )],(),([ ),( (4.23) 为一克服噪声的影响，还可将互相关函数定义为： Tk m i n j Tkk jiTjiS yxC ss mm ? ∑ ∑ ??? =?? = =1 1 ]),([]),([ ),( (4.24) 其中 Tm 、 2Ts 、 km 和 2ks 分别是模板和窗口的均值与方差 问题——基于面积的图象配准过程的运算量过大。 为此，提出了一些改进基于面积的图象配准的方法。 Levine给出了一种对平行立体视在内极线约束下的互相关检测过程，使得对匹配邻 域的搜索由二维减小到一维。其互相关测度定义为 ),(),( )],(),(),(),([)12)(12( 1 )( pjiji pjijipffvu p RL ui ui vj vj RLRL + ∑ ∑ +?+++ = + ?= + ?= ss mmhxhx j x h (4.25) 其中 f x yL ( , ) 和 f x yR ( , ) 分别为左、右两幅图象，相关匹配邻域是以 ( , )i j 为中心，以 ( ) ( )2 1 2 1u v+ × + 为大小的窗口， μ L i j( , ) 、 μ R i j p( , )+ 、 σ L i j 2 ( , ) 和 σ R i j p 2 ( , )+ 分别是左右窗 口的均值和方差。最终由 { ( ) max}d d? = 确定视差 d 。 Moravec给出了一种由粗到细的基于面积的配准搜索策略，可以较好地提高基于面 积的图象配准的运算速度。 另外， Genney和 Hannah等也给出了一些改进基于面积的图象配准的方法。 基于面积的图象配准的问题： (1)由于基于面积的图象配准是直接利用图象中的象素灰度值进行匹配，因此，它对 于图象的旋转以及光强和对比度的变化等非常敏感。 (2)当左、右两幅图象中存在重复结构的纹理特征或相关象素邻域内存在遮挡现象 时，常常会引起匹配的混淆，给出错误的配准结果。 (3)虽然采用内极线假设以及由粗到细的层次化结构等约束条件可以在一定程度上减 少基于面积的图象配准的计算量，但由于互相关匹配的大运算量特点，这种方法 的时空复杂性仍然是很大的。 4.3.1.2 基于特征的配准 1. 特征是通过灰度导出的，因此，它对于对比度和明显的光照变化等相对稳定 2. 基于特征的配准可通过对特征属性的简单比较实现，因此，比基于面积的配准要 快得多。 1.基于边缘点配准的 Barnard方法 (1)特征属性值的计算 设 f x yL ( , )和 f x yR ( , )分别为左、右两幅图象。以左图象为例，定义其特征点图象为 F x yL ( , )，则有 },,,min{),( RLVHjiFL = (4.26) 其中 22 )]1,(),([)]1,(),([ +?+??= jifjifjifjifH LLLL 22 )],1(),([)],1(),([ jifjifjifjifV LLLL +?+??= 22 )]1,1(),([)]1,1(),([ ++?+???= jifjifjifjifL LLLL 22 )]1,1(),([)]1,1(),([ ?+?++??= jifjifjifjifR LLLL 将它们各自划分成大小为 nm × (如取 55 ×=× nm )的互不重叠的区域 Wp q, ，对每一互不 重叠的 m n× 区域，求坐标 ),( ** ji ，使之满足 { }),(max),( ,),( ** jiFjiF LWjiL qp∈ = (4.27) 为消除噪声影响，对所有特征点图象取阈值， ?? ? >= otherwise0 ),( if),(),( ****** ThjiFjiFjiF LL L (4.28) 理想的情况是对左图象中的每一特征点，在右图象中有唯一的特征点与之对应， 但由于遮挡、阴影及噪声等的影响，对左图象中的某些特征点，在右图象中可能没有 对应点。 为了使两幅图象的特征点之间能够实现正确的对应，对左图象中的每一特征点进 行如下处理：假设左图象中的一个特征点 F x yL i i( , )在右图象中的最大移动距离为 r ( r 为沿 yx, 移动距离中的较大者），则将右图象中该移动距离范围内的所有特征点作为 左图象中该特征点的所有可能匹配点集，记为 { ( , )}F x yR i j j ，从而对左图象中的特征 点，可以得到一标号集 Li ，其中的标号 l 或者是该特征点与其可能匹配点之间的视差 l l lx y= ( , )，其中 lx 和 ly 分别表示特征点与可能匹配点在水平和垂直两个方向上的位置差 别，或者是一个未定义的标号 l l= *，其中 l* 代表左图象中的特征点在右图象中无特征 点与之对应，因此称为未定义的标号。对于每一可能匹配点样 ai ，按下述方法为其定 义一个初始匹配概率： 设 Wi是左图象中以 ( , )x yi i 为中心的一个 nm × 区域， ),( yx lll = 为可能的视差，则对于 所有的 *ll ≠ ，定义 ∑ ++?= ∈ iWyx yxRLi lylxfyxflS ),( 2)],(),([)( (4.29) 当 S li ( ) 较小时，初始配概率 p li0 ( ) 应较大，反之亦然。为此 * , )(1 1)( ll lSclW ii ≠?+= (4.30) 其中 c 为常数。 W li ( )代表了 ),( iiL yxF 的标号 l 所具有的权重 定义未定义视差 l* 的初始概率为： )}({max1)( * * lWlp ill o i ≠?= (4.31) 则由贝叶斯准则， F x yL i i( , ) 具有标号 l l l( )*≠ 的初始匹配概率为 **00 )),(1)(()( lllpilplp iii ≠?= (4.32) 其中 p l ii ( ) 是在 ),( iiL yxF 可匹配条件下，具有标号 l 的条件概率， )(1 *0 lpi? 是F x y L i i( , )可匹配的概率。 )( ilp i 可表示为 ( ) ∑ ′= ≠′ * )( )( ll i i i lW lWilp (4.33) (2)松驰迭代过程 对于由可能匹配点的邻域的相似性程度所得到的初始匹配概率，可利用视差一致 性约束来对其进行迭代。 所谓视差一致性性质是指对 p li ( ) 的第 k + 1次迭代，当 F x yL i i( , ) 附近具有较多点近似 地具有视差 l 时，增大 )(1 lpki + ，否则减小 )(1 lpki + 。即 q≤′? ll (4.34) 其中 θ为一阈值， Ryyxx jiji ≤?? ),max( (4.35) 其中 R 为半径。 令 * ),( )()( , lllplq lilj k j k i ≠∑ ′= ?∈′ (4.36) 其中 { }|- and ,|)||,max(|,, q≤′≤??′=? llRyyxxlj jijili 则迭代更新概率为 )()(? ))(()()(? **1 *1 lplp lllqBAlplp k i k i k i k i k i = ≠?+?= + + (4.37) 其中 A、 B 分别为衰减和增益参数，它们影响着迭代收敛的进程。规格化 $p 有 p l p lp lik i k i k l Li + + + ′∈ = ′∑1 1 1( ) $ ( ) $ ( ) (4.38) 经过若干次迭代后，达到相对稳定。 2.基于边缘点配准的 Kim方法 (1)匹配基元的提取。 通过对每幅图象利用 LoG算子 进行卷积运算得到零交叉点，根据 零交叉点连通性得到 16种零交叉模 式，如图 4.5所示。 在确定零交叉模式后，与 Barnard方法类似，在特征点的最 大移动距离范围内对左图象中的每 一零交叉模式，在右图象中寻找可 能匹配点。由于采用水平内极线假 设，因此可能匹配点的寻找仅需在 水平方向进行。 图 4.5 零交叉模式 将左图象中的所有非水平零交叉模式构成一点集 { }ia ，其中每一点 ia 赋予一个标号 集 }{ ji lL = 和一个概率 )( ji lp ，其中 jl 表示 ia 与可能匹配点所具有的视差， )( ji lp 表示 ia 具有视差 jl 的概率。类似于 Barnard方法中的计算过程，根据零交叉模式的相似性和 灰度梯度的差值计算权函数 Wj ),(),(1 1 1 1 jjRiiLij j yxGyxGbDPaW ?+?++?= (4.39) 其中， DPij 是左图象 f x yL ( , ) 中 ( , )x yi i 点处的零交叉模式与右图象 ),( yxfR 中 ),( jj yx 点 处零交叉模式的方向差， ba, 为正的常数且满足 1=+ ba 2 ),1(),1(),( 2 ),1(),1(),( jjRjjR jjR iiLiiL iiL yxfyxfyxG yxfyxfyxG ??+= ??+= (4.40) 从而 ∑+ = = m k k j ji WW Wlp 1 * 0 )( (4.41) mjWW j j ,,2,1),(max1* L=?= (4.42) 其中 m 是标号集 }{ ji lL = 中的基数。 (2)松驰迭代过程 设 ( , )x yi i 是点 ai 所代表的零交叉模式的中心点， ),( pp yx 和 ),( ss yx 分别是与 ( , )x yi i 相邻 的两个零交叉点，则迭代更新概率为 )()())(()()(? 1 psjkiksjkijkijki pIlpdplpFclplP ?????+=+ (4.42) 其中， ? ? ? <≤?? ≤≤= 1)(5.0))(1()( 5.0)(0)]([))(( 2 j k ij k ij k i j k ij k i j k i lplplp lplplpF )}1(,),1(max{ +?= jksksjksks lpplpp ? ? ? =+ ≠+= 01 00)( k s k p k s k p ps pp ppPI )}1(,),1(max{ +?= jkpkpjkpkp lpplpp c d, 为正常数。 上述公式考虑了三个约束条件：视差的连续性；视差的连通性，连通零交叉点匹配 的确定性。 当与零交叉点 ),( ii yx 相邻的零交叉点 ),( pp yx 和 ),( ss yx 与 ),( ii yx 具有相似的视差时， )(? 1 jki lp + 增大，否则 )(? 1 jki lp + 减小。通过规格化处理有 ∑ ′= ∈′ + + + iLl k i j k i j k i lp lplp )(? )(?)( 1 1 1 (4.43) 在每次更新迭代过程中，去除具 有较小 （如小于 0.05）的可能匹配 点。当迭代概率值大于某一阈值 （如小于 0.7）时，则确定此时的可 能匹配点为最终匹配点，从而实现 图象的配准。 4.3.1.3 配准的层次化方法 在图象配准过程中，仅在原图象 之间直接进行匹配往往计算量很 大。为此，人们提出了层次化的配 准方法，即将图象分成不同分辨率 的层次，图象的配准可先从低分辨 率的层次开始，逐渐扩展到高分辨 率的层次，以提高配准的速度。 0 第 层 1 第 层 2 第 层 图 4.6 层次化 4.3.2 三目配准 二目图象配准由于对应点搜索空间比 较大，因而往往比较复杂。为此，可采 用三目配准的方法，增加配准的约束条 件，简化配准问题。 有三个摄象机，其光心分别为 )3,2,1( =iCi ，对应的视平面为 )3,2,1(P =ii 。对于一个给定的空间点 A 在视平面上的投影点为分别 1a 、 2a 和 3a ， 称为同调图象点。 同调图象点的搜索仅需在其共轭内极 线上进行。 现在考虑三个摄象机的情况。设有摄象机 1,2,3，对于任意的同调点三元组 ( , , )a a a1 2 3 ，a 1同时位于内极线 L12 和 L13 上，其中 L12 和 L13 分别由另二个图象面上的点 a2 和 a3 所定义， 如图 4.7所示。 结论 给定摄象机的空间位置参数后，即可通过内极线的计算来实现图象配准。 A C1 C3 C2 P a L L 1 1 12 13 P a L L 3 3 32 31 P a L L 2 2 23 21 图 4.7 三目成象几何 P Q I H Q I PB B B H PH P P L H H HB 1 m Q IV V PV LV H1 P P LVB V V 1 m LV 2 LV m 图 4.8 基于边缘点的三目配准 基于边缘点的三目配准 如图 4.8所示，对于视平面 BI 上的 任意一点 BP ， 1.计算它在视平面 HI 上的内极线 HBL ，从而得到沿内极线 HBL 的候选匹 配点 },,,{ 21 mHHH PPP L 。 2.计算 PHi 在视平面 VQ 上的内极线 HViL ，从而在 VQ 上得到一个内极线集 },,{ 21 HVHVHV m LLL L 。 3. 计算 BP 在图象面 VQ 上的内极线 VBL ，对于任一 L L L LV H V H V H V Hi m∈{ , , }1 2 L ， HVVBV ii LLP ∩= 。 4.对所有的边缘点 PHi 和 iVP ，检测 iHB PP , 和 PVi 的局部特征属性 (如边缘点的强度、 边缘的连续性等 )的相似性，若满足相似性条件，则将它们作为匹配点保留下来。 5.检测每一匹配点所产生的视差的一致性。去除掉那些与邻域匹配点所产生的视 差不一致的匹配点后，即可得到最终的匹配点，完成图象的配准。 基于边缘线段的三目配准 预处理过程 输入 :原始图象 输出 :线段邻接图 1.线段边缘的提取 2.定义线段邻接图，图中的结点为线段边缘， 其中赋予线段的局部几何特性，包括线段的中点 位置、线段的方向和长度以及强度函数的均值等。 若二个线段相邻接，则在图中代表这两个线段的 结点间以一条弧相连接。 配准过程 输入 :的线段邻接图 G G G1 2 3, , ， 1. 对 G1中的每一线段 S1，计算其中点 1a 在图象 2中的内极线 21L ，则 1a 在图象 2中的同 调图象点 2a 在 21L 上。 (2)考虑 2G 中与 21L 相交的线段 2S ，并设其交点为 2a 。对于每一个 2S ，比较它与 1S 的 局部几何特征中的长度和方向，若它们是可匹配的。则把 S2 作为 S1 的可能匹配线段。 (3)对每一个可能匹配线段 S2 ，计算它在图象 3中的内极线 L32 ，并设它与 a1 在图象 3中 的内极线 31L 的交点为 a3 。若有一条线段 S3 在 a3 附近，则将其长度和方向与由 S1 和 S2 所获得的长度和方向相比较，如果它们是可匹配的，则 S1 、 S2 和 S3 组成匹配线段。 最后，由所有匹配线段实现图象的配准。 S L a 2图 象 a S 1图 象 1 1 2 2 21 S a L L 3图 象 3 3 32 31 图 4.9基于边缘线段的配准 4.4 三维表面重建 作用 ：由稀疏视差 ( 距离 ) 图得到一个完整的三维表面的距离或方向信息 问题 : 从理论上讲通过已知分散点的表面可以有无穷多个，因此，要重建的是一个与图象 信息相一致的最佳拟合表面。 这样的一个最佳拟合表面是存在的，并且这个表面使得二次变分函数 ∫ +∫ += 2/1222 ])2([)( dxdySSSS yyxyxxq (4.44) 达到最小，其中 S 是一个表面， 22222 /,/,/ ySSyxSSxSS yyxyxx ??????? === 。因此， 最佳表面的拟合问题实质上是一个优化问题。 求解 : Grimson指出，考虑到视觉表面重建问题中的局部性、平行性和一致性特点，以及对 分散输入数据的处理能力，最好的优化方法是采用数学规划法。 数学规划法的简单描述如下：首先，将表面划分成 mm × 的网格，我们所要计算的是 每一网格点上的表面信息，因此，可以将每一个表面看成是一个 2m 维向量空间中的一个 点，其每一维代表网格上每一点的值。将这个 m 2 维的向量扩展到 12 +m 维，使得最后一维 是二次变分函数 )(Sq 的值，这样，可以在 m 2 1+ 维空间中建立一个 “超面” （称为目标 面）。目标面的最低点所代表的表面即为使二次变分函数 )(Sq 最小的表面。数学规划法 通过迭代过程来寻求目标面上的最低点 (1) 选择目标面上的一个点作为起始点； (2) 在目标面上检测该点的一个局部区域，选取这一区域中的最低点； (3) 以最低点作为新的起始点，重复上述过程直至满足要求为止。 上面给出的二次变分函数是连续的。为了将数学规划法应用于求解 θ( )S 的最小化 问题，需要考虑它的离散情况。首先，由于在 θ( )S 中涉及到一个平方根运算，则使 θ( )S 最小等价于使平方根中的项最小，从而不失一般性，可设 ∫ +∫ += dxdySSSS yyxyxx )2()( 222q (4.45) 对于 m m× 的网格，令每一网格点的坐标位置为 ( , )i j ，它代表第 i 行，第 j 列的网 格点，网格上每一点的表面值用 S i j( , ) 来表示。按行或列的次序排列 S i j( , ) ，可得一个 m2维向量 S S S S m m= ? ?{ ( , ), ( , ), , ( , )}0 0 0 1 1 1L ，从而在离散形式下，近似地有： ? ? 2 2 2 21 1 2 1S i j x h S i j S i j S i j O h ( , ) [ ( , ) ( , ) ( , )] ( )= + ? + ? + (4.46) ? ? 2 2 2 21 1 2 1S i j y h S i j S i j S i j O h ( , ) [ ( , ) ( , ) ( , )] ( )= + ? + ? + (4.47) ? ? ? 2 2 21 4 1 1 1 1 1 1 1 1 S i j x y h S i j S i j S i j S i j O h ( , ) [ ( , ) ( , ) ( , ) ( , )] ( )= + + ? + ? ? ? + + ? ? + (4.48) 其中 h 为网格间距。 在进行上述离散化处理后，还需将双重积分转化为等价的离散形式，即在离散 网格上对确定差分算子进行双重求和运算。需要指出的是，交叉项 dxdySxy∫ ∫ 2 需在二 倍于网格的空间分辨率上实现离散化处理。由此，我们得到了一个离散的目标函 数： ∑ ∑ ++++?+? +∑ ∑ ++??+∑ ∑ ++?? ? = ? = ? = 2-m 0=i 2 0 2 1-m 0=i 2 1 22-m 1=i 1 0 2 )]1,1()1,(),1(),([2 )]1,(),(2)1,([)],1(),(2),1([ m j m j m j jiSjiSjiSjiS jiSjiSjiSjiSjiSjiS (4.49) 表面重建问题等价于使这一目标函数达到最小。 现在考虑这一问题的约束条件。令： |),{( ji=Φ 网格点 ),( ji 上的深度已知的点集 }, 则约束条件为对 Φ∈),( jiV ，有 0),(),( =? jiCjiS (4.50) 其中 C i j( , )是反映立体数据的一组约束，即深度的测量值。 另外，考虑到目标函数是二次的，具有 "凸 "的形式，所以在目标面上得到的局 部最小点即为全局最小点，不存在局部极小化问题。 梯度投影法求解 由数学规划法的迭代过程可知，为了使目标函数最小化，对每一当前点，需在目标 面上选择其局部区域的最低点，并将这一最低点作为新的当前点。为此，可计算当前 点在目标面上的梯度向量，然后沿着其负值方向将当前点移动到最低点。梯度向量的 分量计算可以化为模板进行卷积运算。 在得到当前点的移动方向后，为了确定当前点沿该方向的移动距离，还有必要确定 该方向目标函数的最小值，即要确定一个 α的值，使得 [ ]{ } [ ]{ } { [ ]}2 2- 0= 2 0 1- 0= 2 1 2 2- 1= 1 0 2 )1,1()1,(),1(),( )1,1()1,(),1(),(2 )1,(),(2)1,()1,(),(2)1,( ),1(),(2),1(),1(),(2),1( ++++?+?+ ∑ ∑ ++++?+? +∑ ∑ ++??+++?? +∑ ∑ ++??+++?? ? = ? = ? = jidjidjidjid jiSjiSjiSjiS jidjidjidjiSjiSjiS jidjidjidjiSjiSjiS m i m j m i m j m i m j a a a (4.51) 达到最小，通过对上式的微分计算可得 α的值由 21 /aaa = 确定，其中 ∑ ∑ ++++?+?++++?+? +∑ ∑ ++??++?? +∑ ∑ ++??++??= ? = ? = ? = 2- 0= 2 0 1- 0= 2 1 2- 1= 1 01 )]1,1()1,(),1(),()][1,1()1,(),1(),([2 )]1,(),(2)1,()][1,(),(2)1,([ )],1(),(2),1()][,1(),(2),1([ m i m j m i m j m i m j jidjidjidjidjiSjiSjiSjiS jidjidjidjiSjiSjiS jidjidjidjiSjiSjiSa (4.52) ∑ ∑ ++++?+? +∑ ∑ ++??+∑ ∑ ++??= ? = ? = ? = 2- 0= 2 0 2 1- 0= 2 1 22- 1= 1 0 2 2 )]1,1()1,(),1(),([2 )]1,(),(2)1,([)],1(),(2),1([ m i m j m i m j m i m j jidjidjidjid jidjidjidjidjidjida (4.53) 其中 ),( jid 为梯度分量。 综上所述，梯度投影方法的具体实现步骤为： (1)给出任意一个初始近似表面，使得 Φ∈? ),( ji ，该表面在 ),( ji 点处的值为立体深度 值 ),( jiC 。 (2)根据上述模板对当前近似表面的网格形式的卷积运算得到目标函数的梯度，并由 其负值得到方向向量。将方向向量中对应于已知深度的点的分量置为零。 (3)由上述公式计算标量 α，从而得到由目标函数定义的目标面上沿方向向量的移动 距离。 (4)根据长度因子为 α的方向向量和当前近似表面，得到一个新的近似表面。 (5)重复上述步骤，直至方向向量的所有分量值都小于某一常数 ε为止，此时得到的近 似表面即为重建表面。