应用于双视图三维复原的降维八点算法＋
姜桂祥任蕾杨忠根
（上海海运学院电子工程系上海２００１３５）
Ｅ－ｍａｉｈｙｍａｇｚｇ＠ｓｈｍｔｕ．ｅｄｕ∞
摘要传统的应用于双视图三维复原的八点算法使用标准特征值分析（ＥＶＤ）算法。通过误差分析可知，
该技术存在估计偏差大、均方误差大的缺点。其产生原因是数据噪声的有色性和自相关函数矩阵的条件数
过大，因此白化数据噪声和正则化变换是提高性能的有效措施。这从理论上有力地支持了Ｈａｒｔｌｅｙ提出的正
则化八点算法。然后，我们通过理论分析和计算机仿真实验，表明了我们给出的降维技术固有地同时具备
噪声预自化功能和数据正则化功能，因此它能给出均方误差相当小的无偏估计。由于它无须进行预白化变
换或正则化变换，并把最优化过程的维数从９降为４，所以它还具有计算快速，实现简单方便的优点。计
算机仿真实验例证了我们的分析。
关键词计算机视觉，双视图三维复原，特征值分解，正则镟降维特征值分解。
分类号ＴＮ９４１１
Ｄｉｍｅｎｓｉｏｎ－ＲｅｄｕｃｅｄＥＶＤＴｅｃｈｎｉｑｕｅＡｐｐｎｅｄｔｏＴｗｏ—ｖｉｅｗ３１）Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ
环境污染英语作文
ＪＩＡＮＧＧｕｉ—ＸｉａｎｇＲＥＮＬｅｉＹＡＮＧＺｈｏｎｇ－Ｏｅｎ
（Ｄｅｐｔ．矿ＥｌｅｃｔｒｏｎｉｃＥｎｇ，ＳｈａｎｇｈａｉＭａｒｉｔｉｍｅＵｎｌｖ，Ｓｈａｎｇｋｉ－２００１３５）
Ｅ－ｍａｌｈｙａｎｇｚｇ＠ｓｈｍｍ．ｅｄｕｃｎ
ＡｂｓｔｒａｅｔＴｈｅｔｒａｄｉｔｉｏｎａｌｅｉｇｈｔ—ｐｏｉｎｔａｌｇｏｒｉｔｈｍＯｆｔｗｏ－ｖｉｅｗ３ＤｒｅｃｏｎｓｔｒｕｃｔｉｏｎｕｔｉｌｉｚｅｓｔｈｅｓｔａｎｄａｒｄＥｉｇｅｎＶａｌｕｅ
Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＥＶＤ）ａｌｇｏｒｉｔｈｍ．Ｂｙｍｅａｎｓｏｆｔｈｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ｗｅｋｎｏｗｔｌｌ如ｉｔｈａｓｔｈｅｄｉｓａｄｖａｎｔａｇｅｓｏｆ
ｖｅｒｙｂｉｇｅｓｔｉｍａｔｉｏｎｂｉａｓａｎｄｒｕｓｅ．Ｔｈｅｒｅａｓｏｎｉｓｔｈａｔｔｈｅｄａｔａｎｏｉｓｅｉｓｎｏｔｗｈｉｔｅａｎｄｔｈｅｃｏｎｄｉｔｉｏｎｎｕｍｂｅｒｏｆｔｈｅ
ＡＣＦｍａｔｒｉｘｏｆｔｈｅｄａｔａｏｂｓｅｒｖａｔｉｏｎｉｓｅｘｔｒｅｍｅｌｙｂｉｇＴｈｕｓ，ｔｈｅｅｆｆｅｃｔｉｖｅｍｅ∞ｕｍｔｏｉｍｐｒｏｖｅｔｈｅｉｓｗｈｉｔｅｎｉｎｇｔｈｅ
ｄａｔａｎｏｉｓｅａｎｄｒｅｇｕｌａｔｉｏｎｔｒａｎｓｆｏｒｍａｔｉｏｎ．田正ｓｔｈｅｏｒｅｔｉｃａｎａｌｙｓｉｓｈａｓｓｔｒｏｎ羽ｙｓｕｐｐｏｒｔｔｈｅｒｅｇｕｌａｒｉｚｅｄａｌｇｏｒｉｔｈｍ
ｄｅｖｅｌｏｐｅｄｂｙＨａｒｔｌｅｙ．Ｔｈｅｎ．ｗｎｄｅｖｅｌｏｐａｄｉｍｅｎｓｉｏｎ・ｒｅｄｕｃｅｄａｌｇｏｒｉｔｈｍ．ｎｅｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｉｓａｎｄｃｏｍｐｕｔｅｒ
ｓｉｍｕｌａｔｉｏｎｓｈａｖｅｄｅｍｏｎｓｔｒａｔｅｄｔｈａｔｔｈｅｔｅｃｈｎｉｑｕｅｈａｓｔｈｅａｄｖａｎｔａｇｅｓｏｆｉｎｔｒｉｎｓｉｃａｌｌｙａｂｉｌｉｔｙｔｏｗｈｉｔｅｎｔｈｅｄａｔａｎｏｉｓｅ
钢琴符号ａｎｄｔｏｒｅｇｕｌａｒｉｚｅｔｈｅｃｏｎｄｉｔｉｏｎｎｕｍｂｅｒｏｆｔｈｅＡＣＦｍａｔｒｉｘｏｆｔｈｅｄａｔａｏｂｓｅｒｖａｔｉｏｎＳＯｔｈａｔｉｔｃａｎ
ｇｉｖｅａｕｎｂｉａｓｅｄｅｓｔｉｍａｔｉｏｎｏｆｐａｒａｍｅｔｅｒｍａｔｒｉｘｗｉｔｈｖｅｒｙｓｍａｌｌｍｓｅＦｕｒｔｈｅｒｍｏｒｅ，ｎｅｉｔｈｅｒｗｈｉｔｅｎｉｎｇｔｒａｎｓｆｏｒｍａｔｉｏｎｎｏｒｒｅｇｕｌａｔｉｏｎ
ｔｒａｎｓｆｏｒｍａｔｉｏｎｉＳｎｅｅｄｅｄａｎｄｔｈｅｄｉｍｅｎｓｉｏｎｎｕｍｂｅｒｏｆｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｃｅｄｕｒｅｉＳｒｅｄｕｃｅｄｆｒｏｍ９ｔｏ４Ｔｈｅｒｅｆｏｒｅ
ｔｈｅｃｏｍｐｕｔａｔｉｏｎｃｏｍｐｌｅｘｉｓｌａｒｇｅｌｙｓｉｍｐｌｉｆｉｅｄ．
ＫｅｙｗｏｒｄｓＣｏｍｐｕｔｅｒｖｉｓｉｏｎ，Ｔｗｏ—ｖｉｅｗｓｔ／ｌｌｃｔｕｍｆｒｏｍｍｏｔｉｏｎ，ＥＶＤ，ｒｅｇｕｌａｒｉｚａｔｉｏｎ，ｄｉｍｅｎｓｉｏｎ—ｒｅｄｕｃｅｄＥＶＤ
１引言
在计算机视觉中，从运动复原形状（ＳＦＭ）由于充分利用了图象序列中的大量冗余信息来检测、定位和跟踪视场中的动目标而成为复原动目标三维视觉信息的有力技术，多年来一直受到学术界普遍
受上海市高等学校科学技术发展基金项目“计算机视觉技术在港１２１集装箱装卸自动化中的应用”的资助。
应用于双视图三维复原的降维八点算法３６７
重视和广泛研究”１２ｎ４ｓｓ１‘Ｊ。其中，最简单最常用的是从双视图特征点对集合复原目标三维视觉信息的两帧法，它也是以扩展卡尔曼滤波为框架的称之为动态运动视觉的多帧法的基础。双视图三维复原的核心是本质矩阵参数的最优估计，在未标定情况下，是基础矩阵参数的最优估计。它通常使用标准八点算法。实践表明，标准八点算法的实际性能很差，尤其是应用于基础矩阵参数估计时，存在估计偏差大、拟合均方误差大和噪声灵敏度极大的缺点。Ｈａｒｔｌｅｙｌ８Ｉ指出其产生原因
是数据自相关阵的条件数过大，根据此分析，他提出了正则化八点算法。实践证明了正则化八点算法的良好性能。我们通过误差分析，从理论上证明了标准八点算法的低性能来自数据噪声的有色性和数据自相关阵条件数的过大，指出了改善性能的两个根本措施是白化数据噪声和正则化数据自相关阵。Ｈａｔｔｌｅｙ推荐的正则化变换具有强的正则化功能，并能在一定程度上白化数据矢量，因此它具有良好的性能。我们的分析使Ｈａｒｔｌｅｙ算法有了坚实的理论支持。与此同时，我们指出了经过Ｈａｒｔｌｅｙ的正则化变换，数据噪声仍是有色的，因而只能给出参数的有偏估计。然后，我们证明了降维八点算法在不进行任何变换的前提下固有地同时具有数据噪声白化功能和数据正则化功能，并能把最优化问题的维数从９降到４，这样它在大大降低计算复杂性的条件下能给出与Ｈａｎｌｅｙ算法相同的性能。实验证实了我们的分析。
２双视图复原问题的八点算法及其存在问题
２．１八点算法
众所周知，双视图问题的核心是利用外极线约束方程
ｍ，Ｅｎｄ＝０
从对应点对集合最优地估计本质矩阵参数，或者在未标定情况下估计基础矩阵参数，其中，（ｍｍ：）
是点对（Ｉ，ｔ）的齐次坐标。。由于矩阵Ｅ的ＤｏＦ不可能大于８，因此，我们由八个点对就可从
Ｘ；’＝０，ｉ＝１，２，…，Ｎ（２）上式中定义了数据矢量ｘｔ。ｆ圣ｉ囊］，其中％２Ｉ”ｍｙｉＬ“＊ＸｉＪｌ和参数矢量ｅ＝［圣］，其中上式中定义了数据矢量置。ｌ：：：Ｊ’其中％２和参数矢量ｅ２ｌ；；ｊ’其中
Ｅ＝ｋ，巳巳】・即，线性八点算法叙说，最优解矢量为数据阵ｘ＝应，Ｘ。…Ｘ。】ｒ的最小奇异值所对应的右奇异矢量（这是奇异值分解法，即ＳＶＤ法）或数据自相关阵如２言ｘ７ｘ２专善ｘ。ｘｔ７的最小本征值所对应的本征矢量‘这是本征分解法，即ＥⅦ法）。与会者
假设观测数据矢量Ｘ。＝ｘ！‘’＋Ⅳｉ，其中，本文用上标（ｔ）表示真值，Ｎｉ为观测噪声。由于ｅ‘‘’１尺；’ａ（‘）＝０，因此，当且仅当观测噪声与观测数据不相关并且为方差阵等于盯！，的零均值白声时，有Ｊ＝ｅ１ＲｘＯ＝ｅ’Ｒ：氇＋ｐｌ２盯：，使得噪化自相关阵Ｒｘ＝尺：’＋仃：，与真自相关阵Ｒ？’有相
！塑！垫些堡堡：蔓查兰堡旦
同的最小本征矢量，即最优解矢量为解矢量的真值相等。这表明，线性算法给出无偏估计的条件是：观测噪声矢量与观测数据矢量的真值不相关并且为方差阵等于盯：Ｊ的零均值白声。
对于八点算法，观测噪声矢量是个与观测数据矢量相关并且为方差阵不等于盯：，的非零均值有色噪声。不失一般性，假设特征点‘＝Ｊ～｛＝‘‘‘’＋月。，其中噪声”。为与‘无关的方差阵等于晓的零均
Ｌｙｉｊ
值白声；并且‘１＝‘’‘‘’＋ｎ：，其中噪声ｎ：为与‘＋无关的方差阵等于嘎的零均值白声。可以证明，数据自相关阵Ｒ。＝Ｒ。＋晚，，其中，Ｒ。为其真值，相应的噪化数据观测矢量可表示为Ｘ。＝Ｘ。。十ｎⅪ。
其中的观测噪声矢量”Ⅻ的均值不等于零，并且其方差阵不是个对角阵，其值等于晓，＝晓＠Ｒｊ７’＋吃．ｏＲ：。＋瓯。晓，算符。表示矩阵直积运算。。因此，八点算法只能给出解矢量的有偏估计，并且，消除有偏性的根本措施是预白化数据观测中的噪声分量。
２．３八点算法的病态性
根据矩阵摄动理论，有：０＝Ｒ０。＝嘏。一积。冷一国）＝（Ｒ。一积。）一尺。＆
使得：＆ｚＲｘ＋＠。一积。》
琨韵碟黔刘恻｛）＿魄ｆ，＋钳卜。）∽
其中，数据自相关阵Ｒ。的条件数Ｋ（Ｒ；）是误差灵敏度系数，它定义为
银行大堂经理职责
氓）书＋㈣啡Ａ—Ｑｘ＋ｋ呶）＝铡㈤
Ａ。，（Ｒ；）和Ａ。（Ｒ。）分别为Ｒ。的最大本征值和最小非零本征值，并且Ｋ（Ｒ。）有数量级
Ｋ（Ｒ。）＝ｏＱ（Ｒ。）【ｒ（Ｒ，＋））（５）对于八点算法，如果假设２Ｄ点的散布半径为ｈ，则仃（Ｒ。）＝Ｄ（ｈ４）和ｔｒ乜。＋）＝００），使得Ｋ＠。）＝ｏ（ｈ４ｏ在未标定双视图复原情况，ｈ可高达数百，这样条件数会惊人地大，从而使参数矢量严重偏离真值。因此・消除八点算法病态性的根本措施是大幅度降低数据自相关阵Ｒｘ的条件数Ｋ僻，）。
３Ｈａｒｔｌｅｙ删，１］化八点算法
大量实践表明，标准八点算法性能较差。Ｈａｒｔｌｅｙ在分析其产生原因时，注意到二维点的齐次坐标在分布上的极大差异会导致数据矢量自相关阵条件数惊人地大，从而使估计偏差和估计不确定性都不可接受地大。他提出，采用对两个二维点集的分别预白化处理，可有效地把该条件数减小到一个相当小的量级。这是一个简单而又行之有效的正则化技术。Ｈａｒｔｌｅｙ的正则化八点算法如下所示。
步Ｉ：分别计算屯＝Ｉｘ。ＹｉＪｒｆｉ＝，，２，…，Ｎ｝和ｔ’，＝【Ｘ。ｊｙ’，ｒｌｉ＝Ｊ，２，…，Ｎｊ的均值矢量Ｆ和Ｆ’及方差阵６，和０，把它们分别进行Ｃｈｏｌｅｓｋｅｙ分解，即６，＝ＫＫ７和６＝Ｋ’Ｋ“，取两个正则化变
应用于双视图三维复原的降维八点算法３６９换阵分别为Ｌ＝Ｋ。和￡＝Ⅳ’～；
步２：对二二维点集皂＝Ｉｘ．Ｙｉｒｌｉ＝Ｊ，２，…，Ｎ）和ｔ’。：［ｘ’．ｙ’。］ｒｌｉ＝Ｊ，２，…，Ｎｊ分别进行线性正则化变换ｉ＝Ｌ“一ｉ）和Ｆ１。＝，１５（ｒ’，一ｉ’）：
腊排骨炖土豆
步３：并把变换后的二维点对集合转换成数据矢量集合，计算其自相关阵Ｒｉ；
步４：计算数据自相关阵Ｒ｝的最小特征值ｋ所对应的单位特征矢量ｆ，并计算相应的参数矢量的最优估计为萝＝ＬｘｌＦ，其中，相应于（Ｌ，￡）有对数据矢量而言的正则化变换Ｌ。，即文＝ＬｘＸ。此时，ｊｋ给出拟合误差。
正则化变换后的数据矢量有ｈ＝００），使得条件数Ｋ（Ｒ。）＝ｏＯ），因此它能消除八点算法的病态陛。
实际上，该技术给出的参数矢量最优估计根本就不是数据自相关阵Ｒ，的特征矢量，因为
Ｒ。占＝Ｌｘ－７ＲｉＬ。１ＴＪｋ１Ｆ１－ｋ。ｋ一笞＝Ａ。ＬＸ－１Ｌｘ－ＴＳ≠艇、。这解释了正则化八点算法能取＼／
得完全不同于标准八点算法效果的原因。
应当指出，于Ｈａｒｔｌｅｙ技术白化的是两个二维点集，而不是数据矢量中的噪声分量，使得该噪声分量仍是有色的，因此它只能给出参数矢量的有偏估计，当然，Ｈａｒｔｌｅｙ技术仍能相当程度地白化数据噪声矢量，因此偏差往往较小。另外．其计算略嫌麻烦。
４降维八点算法
节２论证了实现无偏估计的根本出路是白化数据矢量中的噪声分量，这需要先验已知或在线估计该噪声的均值和方差，这在实践中很难做到。
为克服此困难，我们首先中心化数据矢量，即把式（２）中心化，使得
ｅ。＝一（置＿，＋豆。’。）（６）
和量１ａ＝［量，７量。７］匿：］＝。ｃ，，这儿ｘｏ，：『Ｇ’）（ｘｙ’）醢’）６。：１Ｔ和ｘｏ：：ｒｘ，ｏ：’纠１，ａ，：［ｅ，，。。。。，。。】ｒＬＪ。Ｊ
和ａ２＝［ｅ＂ｅ∞ｅｊ，ｅ３２】ｒ，其中，上“ｏ’’号表示中心化运算，上横杠符号表示取平均运算。根据式（７），有对中心化数据而言的均方误差
￡一三Ｎ学ｉ：ｌｆｌ立。７ａ］２＝ａ，７量户，＋乃，１蜀夕。＋ａ：’如夕：，（ｓ）其中铲告善Ｎ掰。
（９）为消除方程齐次性影响，使用对参数矢量的约束，例如ａ：’：＝Ｊ，这样有最小化准则函数
！！！旦垫些垄笙：垫查兰堕旦———————————————————一
Ｊ：ａ，１Ｒ，户，十五，。尺，２ｅ
２＋ｐ２１尺２夕２一兄６。１ａ。一，）
（１０）易知，最优估计满足』Ｒ箩：＝Ａ。。（Ｒ；。芦。其中，Ｒ乏：Ｒ。ｔＲ，一’Ｒ，。…）【ａＪ＝一“ｎ¨－１ｎＪ，？２
Ｒ
２２－ＲＡ一（Ｒ；。）是非负定阵尺；：的最小特征值，占：是相应的特征矢量。这就是我们所推荐的降维八点大麦茶的功效与禁忌
算法步ｌ：把二维点对集合转换成数据矢量集合，并把数据矢量中心化；
步２：用式（９）计算民ｖｉｉ＝１１，１２，２２
步３：用式（１１）计算Ｒ；：，并计算其最小特征值ｋ所对应的单位特征矢量占：，再计算占
步４：用式（６）计算ｅｊｊ。
５降维八点算法的性能分析
首先需要指出的是，式（１１）是式（１０）的算法实现。容易证明，中心化数据矢量的噪声分量有零均值并且其方差阵是块对角阵，即
／、。
哆。０］Ｅｈ尸和◇；２ｌＪ７晓。ｌＬ０２Ｊ（１２）
其中，盯。２，是二维点集乜）的噪声ｎ。和二维点集ｔ’；】的噪声ｎ’。的方差阵。因此，我们可使用对曼，的噪声分量和ｘｏ：的噪声分量的分别预白化变换就可完成对中心化数据矢量的‘‘观测噪声”的预白化和正则化。即令｛ｘ，。７ｌ芒。，使得变换前后的各相关阵有如下映射关系：ＩＸ，＝职Ｘ２角的初步认识教学反思
毛＝ｗｉＲ日ｗｊ７Ｖｉｊ∈０ｊ，１２，２２｝（１３）
…獬一觥…揪叫擎：簪警谢，艺删舸。考虑到占，：ＷＩＴｏ－，和占：＝职１￡后，易知，对应的变换前的最优解一定由式（１１）给出。这意味着，无须进行噪声白化变换和参数后映射运算，就可直接由降维算法得到与基于噪声预白化处理的降维技术完全相同的最优解。
组建团队并且，容易看出，ｔｒ（Ｒ乏）＝ｏ（ｈ２）和ｔｒｋ：：＋户ｏ（ｈ＿２），使得Ｋ（Ｒ。）＝ｏＱ），Ｅ１１Ｒ；ｅ的条件数有量级ｏ（ｊ），因此它已自然地具有数据正则化作用。
总之，我们推荐的降维技术固有地同时具备噪声预白化功能和数据正则化功能，因此它同时具有噪声预白化处理和正则化处理所具有的优点：能给出误差方差相当小的无偏参数估计。由于它无须进
