计算机视觉-计算理论与算法基础

武澳大阜

计算机视觉

--计算理论与算法基础

武汉大学遥感信息工程学院

摄影测量教研室

2008年9月

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

由第十章、基于三维特征对应的1

武澳大动5^4斤

基于二维特征对应的运动分析：噪声敏感

基于三维特征对应的运动分析：

信息量：三维数据»二维图像；

估计方法：大为简化；

结果：更稳健

应用：工业自动化和检验、运动机器人、机器

人装配、自姮辆、遥感、生物医学工程、物

体建模…补二

__________________________>

遥感信息工程学院2

SchoolofRemoteSensingandInformationEngineering

第十章、基于三维特征对应的

武澳大阜运动分析

10.1由三维点匹配估计运动

10.2不需显式匹配的方法

10.3从三维直线匹配估计运动

10.4从平面匹配估计运动

10.5二维-三维的物体定位

一5LiK

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.1由三维点匹配估计运动

武澳大阜

10.1.1问题

刚体运动（R,t）前后的三维欧氏空间点为:

J=1,2：n

数据噪声为玲，则m；=Rm,+t+n(10.1)

由尸(R,t)=£(o』m/-(Rmz+t)||=min(10.2)

I估计(R,t)。J

遥感信息工程学院4

SchoolofRemoteSensingandInformationEngineering

10.1由三维点匹配估计运动

武澳大阜

10.1.2直接利用旋转矩阵R

定义:

禹二（"'"2,…，43，小，2/3）

方程(10.1)变为m；=A,x+n

3x12

/TTT

m；0n0n100、

TT

m；0a010

TT

0nm；001,

OT是三城零向日

6

SchoolofRemoteSensingandInformationEngineering

10.1由三维点匹配估计运动

武澳大阜

10.1.2.1不考虑R的约束条件

。尸(R,t)zAT，Tx八

=21例(-Am+AAjA4.x)=0

nn

x=(APA)T(A，Pm')

至少需哭纥匹配点

未知数之间存在相关性：解不令人满意

遥感信息工程学院

7

SchoolofRemoteSensingandInformationEngineering

10.1由三维点匹配估计运动

武澳大阜

10.1.2.2考虑R的约束条件

(T\

令：约束条件：

R=r；

r；r，r,=l,d盯=0;=

k37

由拉格朗日因子法：

3

方'（R,t）=F（R,t）+YXj（r：r/_1）+2储1{r2+2及ifr3+2及r；r3

lf=°=t=m-Rm，/，/为m，,m的重心（1。3）J

遥感信息工程学院8

SchoolofRemoteSensingandInformationEngineering

武澳大阜________________________________________________________________________________________

如何估计R?2

重化,Pi-m;-m,p'i-mi-m

将t带入F'得F'，

n3

27

尸'=、3/p：—物』+g\（rG-1）+

2kSr?+2九+214

dFr,

l令菽=OnH=VUt（10-6）J

遥感信息工程学院9

SchoolofRemoteSensingandInformationEngineering

^^=一2^w,（pM-r^pf）p,424门十2人4口+2入5r3

武它配＞户/为向*pi

力巧门

2>^叫（户：,±Ha）Pi+212―2%+2%的第j个分*

ogr/r

2'皿・（£/一«^Pr）p.+2入门+2入m+2入6r2

«x7T7

Z叫pip/c+AM+3+L门=2现力.曲

令各导数为零，可得皿力R,2+~口+1口+入6门—£犯£,2弭

g卯必P；，$+人用+人卢2+入门=£WiP；,3Pf

B=（瓦b2b3）

M=2孙4m；

ARr+RTA=B两边从左乘以RRART+A=RB

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

RART+A=RB左边是对称的・RB=(RB)T或RBR=B「

武澳大阜

令B=UDVT为矩阵B的奇异值分解

其中U和V为规一化的正交矩阵,D为对角矩阵.

那么RUDVTR=VDUT

,/RUDVTR^VDU1：.R=VUT

rTr

RUDVR=VDUj_i__y_八丁小一丁八一~7

注：应为：RUDVR=VDU

10.1.2.3另一证明

对。0.、6）的另一证明＞另一解

遥感信息工程学院

11

SchoolofRemoteSensingandInformationEngineering

10.1.3元数解法

武澳大阜

⑴四元数q==（a=Zo,y=（九1外,九3）'）=（a,y）

四元数的乘：q/\q'=（aoi'-Y7',oc/'+a'y+Yxy'）（不可交换）

四元数的共甄：）=（a「丫）(6.5)

模：［q|=qAq=（£+y）,0=（q,0）=||同（6.6）

，单位四元数闻=1,

实纥X—（x,0）二巨维向量V—（0,v）

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.1.3四元数解法

若4=（儿），九i,刖,及），则

（、2、2）2）2

M+4~M2a刖-\)%3)2(XiA3+—2)

12A2A2A2

2（九儿+\）及）M—人1+^2-\)九1)(6.8)

、2)2f\2A

、2（九仇3—熊沏）2(刖九3+一九i)M―人］~M+人3

Rv-q/\v/\q

RzRv=q?△(%△以△")△夕2=(如八qj2八g八q、)

描述三维刚体运动

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.1由三维点匹配估计运动

10.1.3四元数解法

武澳大擘_—一

我们现在用单位四元数q（lql=l）来表达旋转（见第6.2.3节）.由四元数的性质知,

矩阵和向量的相乘Rp和两个四元数的相乘（记为A）是一致的：

Rp=qApAq

假设点的坐标已经作了相对于重心的平移

改"（R）=WJwJIPi-Rp，II2（R是一旋转矩阵）

=X%(E-qAP.Aq|•|q|)

=2皿1叭Aq-qAp.l2

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.1.3四元数解法

武澳大阜

由四元数乘积的定义,有下列关于q的线性关系:

Pz.Aq—qAP,=A,q(10.9)

A,是一4X4反对称矩阵:-0(Pr-Pf)T'

Aj=,

—一(PLP；)LPi+P；lx-

问题就成为对下式在约束条件llqll=1下的最小化:

T

£w,qTATA,q三qAq其中A=是对称矩阵

i-1

利用拉格朗日因子法，上述问题的解由下式给出:

士(q'Aq+Ml-q'q))=0

>Aq=XqJ

遥感信息工程学院

15

SchoolofRemoteSensingandInformationEngineering

10.1.3四元数解法

武澳大擘Aq=八Xqy

出比人建电粹A的一个卅＜±ta，q是阳怛的为世［可

但这有四个可能解.假设矩阵的四个特征值为

入12人2＞入32入4

如果入=%（这里i未定），那么得到

q'Aq+AQ—qTq）=qr（Aq—Aq）+A=4

既然我们所要求的是这个函数的最小值，那么

相们所M触解朝息A的对■山干―小陆征值

__________________7

遥感信息工程学院16

SchoolofRemoteSensingandInformationEngineering

10.1.4利用欧拉角

武澳大阜

1）二维旋转：求。

当点共面时，点可由平面上的二维坐标决定•

令m,=（z,y）T和ml=（x；，乂）T.

ml=Rm,

0<6V2兀为了求e,我们要求解以下函数的最小值:

交（夕）=2WiIIm；—Rm"|

2（①㈤+y乂）cos。—2（二乂-yH）sin6）

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

令其一阶导数为零，于是得到解析解:

n

—yix'）

tan'=-----------------------

、犯（工壮十%”）

y

遥感信息工程学院

18

SchoolofRemoteSensingandInformationEngineering

武澳大阜10.1.4利用欧拉角

2）三维旋转:

三维旋转可由三个欧拉角来表达（a，3＞）：

R=R2(a)Ry(P)&(Y)

一加）一旦（a）鸟的&（丫）（小一叫）|

生一个解析解来解决这个问题

10.1,5旋转向量法

X,y,z三方向不等权

武澳大阜

到目前为止，噪声V在式（10・2）中仅用一

标量皿描述.如果三维点m,和m；由高斯

随机向量描述，其协方差矩阵为八一和A一,那

么我们不应该用式（10・2）,而应该对一加权

的平方和求最小化（加权最小二乘法）：

史(R,t)=WXA"

(10.10)

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.1.5旋转向量法

武澳大阜

用卡尔曼滤波器来解决这个问题

状态向量就是要求的运动参数

旋转的参数表达法用旋转向量「

若旋转轴为□(IIUII=1)而旋转角为6那么r=仇1

所以6=Hr||

I•和R的关系由Rodrigues公式(6.3)给出：

R3=I+半

是一个六维向量

我们观测到的是三维点,观测向量定义为1

遥感信息工程学院

21

SchoolofRemoteSensingandInformationEngineering

10.1.5旋转向量法

武澳大阜

如果设观测点m,和血独立，那么观测向量的协方差矩阵为

这里0是3X3的零矩阵

得到观测方程:f(s,x,)=Rm,+t—m!—0

在当前观测值（4,京）附近按泰勒级数展开:

f(s,x,)=f(s,x,)4-)(Xi-£,)4-置与*2(s-s)

忽略高阶项，即得到一线性方程：y1=Mr-s4-n,

遥感信息工程学院

22

SchoolofRemoteSensingandInformationEngineering

y,=MjS+iij

人A

线性化的观测向量y尸—f(s,x,)H-----z--s

OS

af(s,xr)

线性化的观测矩阵M尸—S—

af(SW).

向量y,的噪声

E[nJ=O,而协方差矩阵为

36,五)

加

现在，卡尔曼滤波器可以应用在这个线性化的系统上了

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

波打U：整起见，还需要两个导数，它们分别为

武澳大阜,

f(s,x,)=Rm,-Ft—m!=0

而

誓=哼@[曰加产+*皿叶m产

—/S)[m【x+g(e死一[Wxm]x+(rTm)I—mrr]

A

8)=(1—cos。)/凭

遥感信息工程学院

24

SchoolofRemoteSensingandInformationEngineering

武澳大阜

10.1.6三个点匹配时的特殊方法

（不稳定，噪声敏感）

10.1.7鲁棒法：同第九章

y

遥感信息工程学院

25

SchoolofRemoteSensingandInformationEngineering

10.2不需显式匹配的方法

武澳大阜

｛叫I，=L：势与｛屈11=1,：n｝是刚体上同一组点,

但巴里关至未知。nn

犯

Xw,mtXml

m=-：・1---，7_i—l

,/m=Rm+1.n

Sw«,

i=*l

t=m-Rm

西何估计旋转？曰

若u.ve{mJU不平行V,对应向量u,ve^m-

八uxv〜,/xM

6〜W=-----J—bW=---------

’14XvUxv'

u'-Ru.vr-Hv,w'=RwnR7

遥感信息工程学院

26

SchoolofRemoteSensingandInformationEngineering

10.2不需显式匹配的方法

武澳大阜

如何找到这两个向量

10.2.1共面点

u=平面法向量,

10.2.2一般点群

武m大＞

令（重心化）

Pi-mz=-m,p,=m-=mz-m-

点集的分散矩Q=2PiP：,Q=£P；P；T

则。'=ZP；P「=£RPi=RQRT=

R是正交矩阵,Q和Q'的特征值相同.

,，T

力Q=UAV'

成的对角矩阵

遥感信息工程学院

28

SchoolofRemoteSensingandInformationEngineering

10.2.2一般点群

武澳大阜

Q,Q'分解:

T

Q=U九2U

<九3/

U和U'是由特征向量组成的规一化的正交矩阵

既然,Q'=RQRT,于是有U'AU'7=RUAUTRr

[71||△0'=[土百，土出土ii0

则R=uUT!

其中「是矩阵Q'的第i个特征向量8个解

r

V,»*detR=d(u'u}=+1，4个角军

V/遥感信息工程学院29

SchoolofRemoteSensingandInformationEngineering

10.2.2一般点群

对第一点集的每一个点力,针对每一个旋转的解段计算H

把第二个点集中高点p\最近的点作为自的匹配，并记为P\

由此可计算出每个解的误

2=min之——角翠

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

£

10.3从三维直线匹配估计运动

武澳大阜

10.3.1三维直线的变换

空间直线L：方向单位向量u,原点到

直线向量d,直线上一点M

L作刚体运动(R,t)后的参数为(u则:

u—■(10.16)(10.18)

Q

(10.17)■

d'=Rd+/x/(10.19)7

y

遥感信息工程学院

31

SchoolofRemoteSensingandInformationEngineering

10.3从三维直线匹配估计运动

10.3.2解析解

10.3.2.1旋转的估计

由叫『估计R(四元数法)(10.20)

10.3.2.2平移的估计

由(10.19),minVd[-R&-u；xt(10.21)

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.3.2.1旋转的估计

(XHh[u；孤)t=ZLu；X(d；-Rd,)

ir=]

若矩阵（满秩（即可逆）

平移的解析解为

nn

t=(HK门SWJ5d_Rd.))(10.22)

r*li=l

l乙G=iLUi」xL四」火）的伏

遥感信息工程学院

SchoolofRemoteSensingandInformationEngineering

10.3.2.2平移的估计

武大

另一种方法

如果用任意线上一点M来表达直线位置

对于任一匹配直线，总存在一个数4使得

给定〃个匹配，我们有3+〃未知数

3兀个关于t和a&=l,…，麓）的线性方程,

<3〃>3+〃，这个系统超定.

小二乘法可用来估计平移

遥感信息工程学院

35

SchoolofRemoteSensingandInformationEngineering

10.3从三维直线匹配估计运动

武澳大阜

10.3.3

数值方法

uxRu——0

我们不能期望点M和点M对应空间同一点

定在直线上

一^行，即

W-r)=0

遥感信息工程学院

36

SchoolofRemoteSensingandInformationEngineering

10.3从三维直线匹配估计运动

武澳大阜

10.3.3数值方法

MxR”=0u'x(M'-RM-1)=0

[u]R”

x=0

10.3.3.1苴展的卡尔曼滤波

10:3.金2数值最小化技术

J

遥感信息工程学院

37

SchoolofRemoteSensingandInformationEngineering

10.4从平面匹配估计运动

武澳大阜

10.4.1问题的描述

由两组（n个）匹配的平面一刚体运动（R，t）

平面：法向量n,点m

a=（a，。）'：x+ay+0z+c=0（1。.35）

遥感信息工程学院

38

SchoolofRemoteSensingandInformationEngineering

10.4从平面匹配估计运动

武澳大阜

10.4.2解析解

n--Rrii=0（10.36）

-Q=0（10.37）

min^k-^.||2估计R（四元数表示法）

'-2

・L"，A,线性LS,

mm>（%量-R