L62-合集-计算机科学进展-课件-川大

计算机视觉进展–立体视觉

基础部分I

计算机学院李征参考文献[1]DavidA.Forsyth,JeanPonce,ComputerVision;AModernApproach(1stEdition),NewJersey:PrenticeHall,August24,2002[2]GoshtasbyA.Ardeshir,2Dand3DImageRegistrationforMedical,RemoteSensing,andIndustrialApplications(1stEdition),JohnWiley&Sons,April,2005[3]RichardHartley,AndrewZisserman,MultipleViewGeometryinComputerVision(2ndEdition),CambridgeUniversityPress,March2004参考文献[4]OlivervanKaick,HaoZhang,GhassanHamarneh,DanielCohen-Or,ASurveyonShapeCorrespondence,ComputerGraphicsForum,Volume30,Issue6,pages1681-1707,September2011[5]HongshengLi,TianShen,XiaoleiHuang,ApproximatelyGlobalOptimizationforRobustAlignmentofGeneralizedShapes,IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,Vol.33,NO.6,June2011[6]TimorKadir,MichaelBrady,SaliencyScaleandImageDescription,InternationalJournalofComputerVision,Volume45,Issue2,November2001参考文献[7]ZhengLi,PohuangJiang,HongMa,JianYang,DongMingTang,AModelforDynamicObjectSegmentationwithKernelDensityEstimationBasedonGradientFeatures,ImageandVisionComputing,Volume27,Issue6,pages817-823,May2009[8]DavidG.Lowe,DistinctiveImageFeaturesfromScale-InvariantKeypoints,InternationalJournalofComputerVision,Volume60,No.2,pages91-110,2004[9]D.Marr,H.K.Nishihara,Representationandrecognitionofthespatialorganizationofthree-dimensionalshapes,Proc.R.Soc.Lond.B.200,pages269-294,1978参考文献[10]AliShokoufandeh,IvanMarsic,SvenJ.Dickinson,View-basedobjectrecognitionusingsaliencymaps,ImageandVisionComputing,Volume17,Issue5,pages445-460,April1999[11]JamesL.Crowley,AliceC.Parker,ARepresentationforShapeBasedonPeaksandRidgesintheDifferenceofLow-PassTransform,IEEETransactionsonPatternAnalysisandMachineIntelligence,Volume6,No.2,pages156-169,1984[12]KrystianMikolajczyk,CordeliaSchmid,ScaleandAffineInvariantInterestPointDetectors,InternationalJournalofComputerVision,Volume60,No.1,2004参考文献[13]A.Elgmmal,R.Duraiswami,D.Harwood,L.S.Davis,BackgroundandForegroundModelingusingnonparametrickerneldensityestimationforVisualSurveillance,in:ProceedingoftheIEEE,Vol.90,IEEEInstituteofElectricalandElectronics,USA,Issue7,pages1151-1163,July2002[14]A.Mittal,N.Paragios,Motion-BasedBackgroundSubtractionUsingAdaptiveKernelDensityEstimation,in:CVPR’04,Vol.2,IEEEComputerSociety,Washington,DC,USA,pagesII302-II309,July2004主要内容一.计算机视觉领域中的重要问题二.立体视觉的概念与基本原理三.射影几何中的基本概念四.基本的成像模型五.单视几何学的基本原理六.双视几何学的基本原理七.摄像机标定的基本原理一.计算机视觉领域中的重要问题1.计算机视觉的概念2.计算机视觉领域中的重要问题1.计算机视觉的概念什么是计算机视觉?模拟人眼接收客观世界中可见光信息，并由大脑解释可视信息的过程，使用算法对真实图像或视频中的内容给予有效的解释。入口数据：图像、视频（可视信息）出口数据：对可视内容的某种解释（非可视信息）1.计算机视觉的概念应用实例：文字识别（OCR）物体形状识别人脸识别车站视频中的人数统计医用图像中细胞数量统计医用视频中运动微粒测速军事目标定位、跟踪、行为分析基于视觉分析的人机交互1.计算机视觉的概念相关领域：计算机图形学数字图像处理计算机图形学使用图形生成流水线（一组有序执行的算法），由计算机内部的虚拟几何图形表述生成虚拟可视像素图形的过程。入口数据：虚拟二维或三维场景描述（几何图形，非可视数据）出口数据：经图形管道处理后得到的虚拟的、像素化图形（可视数据）数字图像处理使用算法对数字图像中的像素信息实施处理，使图像中内容的可视化质量得以提高的过程。入口数据：图像（可视）出口数据：图像（可视）脊椎动物的视觉过程脊椎动物的视觉过程两种感光细胞（PhotoreceptorCell）杆状细胞（rods）：仅对光能量有响应，但与光频率无关，很小的光能量即能触发生理刺激。弱光环境下主要依靠此类细胞接收光能量。锥状细胞（cones）：对光能量有响应，且与频率相关。能量低于一定阈值时此类细胞无响应（弱光环境下不工作）。两种感光细胞（PhotoreceptorCell）锥状细胞对不同频率光能量的吸收率两种感光细胞（PhotoreceptorCell）锥状细胞在视网膜中央区域的分布比周边区域更密集。脊椎动物的视觉过程接收场合并与多尺度描述接收场（receptivefield）：（三维）原像空间中能由输入光能量变化引起某神经细胞生理响应发生变化的空间区域。接收场合并（receptivefieldconvergence）：如果多个底层神经细胞与一个上层神经细胞有连接，并将视觉信号传递给它，那么该上层细胞的接收场是相关底层细胞接收场的并集。接收场合并与多尺度描述视觉系统中接收场的逐层合并：感光细胞——神经节细胞——视觉皮质细胞提炼的重要概念：多尺度描述对中央与边缘分别响应的两种神经节细胞提炼的概念：特征提取立体视觉的产生视觉皮层中的双视神经元具有左、右双眼视网膜的感光神经元合并产生的接收场，其完整的生理响应必须由双目视觉同时刺激。提炼的重要概念：立体视觉特征匹配在视觉中的必要性识别：神经元提取的多尺度视觉特征与记忆中的视觉特征相匹配，用于识别看见的物体；配准：左眼、右眼成像中，底层：哪些感光神经元接收的是同一原像的光能量刺激？上层：哪些神经细胞的接收场在哪些部分有重叠？图像匹配操作是必须的。二.立体视觉的概念与基本原理立体视觉的概念：模仿人眼的立体视觉过程，基于一帧或多帧具有共同拍摄场景的图像，由其中的二维形状信息恢复原始场景中三维形状信息的视觉过程。二.立体视觉的概念与基本原理1.单视几何原理2

.双视几何原理3.多视几何原理4.立体视觉的一般处理过程1.单视几何原理单视几何：针对平面物体的形状恢复2

.双视几何原理双视几何：基于标定摄像机的三维表面重建3.多视几何原理多视几何：基于未标定摄像机的三维表面重建4.立体视觉的一般处理过程plprPOlOrXlXrPlPrflfrZlYlZrYrR,T入口数据：单帧或多帧图像为了最终恢复三维信息，需要基于入口数据进一步获取哪些数据？4.立体视觉的一般处理过程问题：如何知道不同图像中的匹配信息？如何知道不同拍摄方位的相对放置（外部参数）？如何知道摄像机的内部参数？4.立体视觉的一般处理过程（1）图像配准（2）摄像机标定（确定内部参数）（3）确定摄像机相对放置（确定外部参数）（4）三维表面重建（1）图像配准1）基于像素的图像配准方法两帧图像中所有具有同一原像的像素对都应建立匹配关系。2）基于特征的图像配准方法仅针对两帧图像中的具有同一原像的点、线、区域特征对建立匹配关系。（1）图像配准两类方法具有一定的联系，并且，基于特征的图像配准效率更高，在其基础上可简化像素级配准。由于各类特征均可以转换为点特征，因此，基于特征点的配准方法成为研究的重点。例如，直线段特征可转换为直线段的两两交点，区域特征可转换为区域的重心。2）基于特征点的图像配准a）数字图像中的特征点提取示例：角点提取b）基于特征点空间分布的图像配准仿射图像配准、透视图像配准、基于外极几何约束的图像配准a）角点提取示例：基于独立性的角点提取方法两个像素窗口的关联系数：像素的独立性：123456789123456789x’与y’小于指定整数，且不同时为零a）角点提取独立性示例：亮度越强的像素位置独立性越强a）角点提取处理流程：1.从图像中提取边缘像素集2.将边缘像素按照独立性降序排序3.对于当前独立性最大的像素，若其独立性大于指定阈值，则将其输出到角点集，否则结束处理流程4.对于剩余的边缘像素集，将其独立性乘以H，转第2步a）角点提取其中，di为第i个剩余边缘像素与输出角点间的像素距离；D为相对距离定义，由它规定距离远、近的概念。b）基于特征点空间分布的图像配准图像配准的目的：在两帧图像间建立一个映射关系，该映射能够将其中一帧图像上的特征点坐标映射为另一帧图像中匹配特征点的坐标。b）基于特征点空间分布的图像配准问题：两帧图像中的特征点数量一定相等吗？是否所有特征点都存在对应的匹配特征点？两帧图象存在差异，内容不会完全一致，因此特征点数量也不一定相等两帧图象存在差异，某特征点可能在左图像中出现，但却可能在右图像中未出现b）基于特征点空间分布的图像配准特征点坐标间的映射可理解为坐标变换，可使用矩阵来表示。矩阵类型与图像间几何变换的关系：1.二维仿射矩阵与图像平面内的二维旋转、平移、放缩变换对应2.二维透视矩阵除包含二维变换外，还包含摄像机绕光心的旋转变换3.基础矩阵包含二维变换、摄像机旋转、摄像机平移等变换b）基于特征点空间分布的图像配准二维仿射变换：两帧图像间的变化可由二维图像平面上的二维旋转、放缩、平移来描述；r、l分别表示左右图像中特征点坐标，i、j表示特征点序号若已知左、右图像中的3个匹配特征点对，则能求解该变换b）基于特征点空间分布的图像配准二维透视变换：两帧图像间的变化包括二维图像平面上的二维旋转、放缩、平移、摄像机成像平面在三维空间中绕光心旋转；r、l分别表示左右图像中特征点坐标，i、j表示特征点序号若已知左、右图像中的4个匹配特征点对，则能求解该变换b）基于特征点空间分布的图像配准仿射配准的处理流程：1.假设左图像与右图像的特征点集分别为P、Q，从P、Q中选择一个未尝试的三点对，若已无三点对可以选择，则认为配准失败，并结束处理流程2.使用相似三角形约束判断三点对的合理性，若不合理，则转第一步b）基于特征点空间分布的图像配准相似三角形约束：p、q分别表示P、Q中的特征点，相同脚标表示具有匹配关系，ε为很小的值b）基于特征点空间分布的图像配准3.使用三点对解方程组，求解仿射变换的6个未知系数，确定变换矩阵4.使用得到的变换矩阵，求P中所有特征点在Q中满足容忍度D（误差，以像素为单位）的匹配特征点5.若特征点数量足够大，则认为配准成功，保存匹配点对信息，结束处理流程；否则，转第1步b）基于特征点空间分布的图像配准仿射配准示例：由于实际的几何变换包含摄像机绕光心旋转、平移等三维变换，因此导致部分点对失配特征提取与匹配的目的特征提取与匹配是三维表面重建（立体视觉）的必要基础；同时也是物体形状分类、识别、对齐等功能的必要基础。特征提取的总体原则1）在视觉中显著程度（Saliency）高，一般在图像中越稀少的内容显著度越高；例子：角点、边缘点、BLOB特征2）显著程度的其中一种评估标准：熵熵的评估：针对图像中的指定区域，一般以考察点为中心，其中的边缘信息越丰富，熵越高。视觉显著度示例使用直方图间接评估区域熵其它特征点提取与图像内容描述、配准方法c）熵特征提取d）BLOB特征提取e）特征点的局部描述符f）基于局部描述符的配准方法c）熵特征提取固定尺度熵特征的局限性：无法自动适应物体在图像中的尺寸c）熵特征提取固定尺度熵特征的局限性：边缘信息在全图像范围丰富时，无法体现“稀少”性质，特征的“显著性”减弱，“随机性”增强引入多尺度熵特征：左图：选择具有最大熵的尺度；右图：选择熵局部极值所在的尺度多尺度熵特征的优点能适应物体在图像中尺寸变化；各尺度特征的空间组合可用于描述物体形状结构；能在边缘总体丰富的情况下，保持特征提取的显著度；多尺度熵特征——加入K近邻聚类能适应图像中物体尺寸的变化多尺度熵特征——加入K近邻聚类边缘在全图像丰富时，仍能保持“高显著”多尺度熵特征——加入K近邻聚类多尺度特征的空间结构可用于特征匹配；间接提供一种物体形状或结构的描述方式多尺度熵特征对图像旋转的不变性多尺度熵特征对图像放缩的不变性多尺度熵特征对图像放缩的不变性多尺度熵特征对视角旋转有一定适应性，但不具有不变性多尺度熵特征对视角旋转有一定适应性，但不具有不变性d）BLOB特征提取BLOB特征是指图像中具有统一颜色或亮度的块状区域（同样具有尺度概念）Scale-spaceblobdetector:多尺度BLOB特征提取e）特征点的局部描述符提取特征点后，可使用其邻域内像素属性的空间分布描述其中的空间特征，即局部描述符，可用于匹配；如何使局部描述符具有旋转不变性若图像间存在旋转变换，则局部描述符间也存在旋转变换如何使局部描述符具有旋转不变性02p根据梯度方向直方图获得主方向，将图像区域的主方向旋转至标准方向即可如何使局部描述符具有仿射不变性若图像间存在仿射变形，则使用各向同性的描述符不能提取到相同的原像特征如何使局部描述符具有仿射不变性02p通过梯度方向直方图获得主方向，根据主方向调整区域形状，反复执行，直至区域形状稳定如何使局部描述符具有仿射不变性目前局部描述符的局限性对透视变形有一定适应能力，但不具备透视不变性；对其它复杂的非线性变换也不具备特征的不变性；f）基于局部描述符的配准方法可以不考虑特征点的空间分布，完全依赖图像间局部描述符的相似度进行匹配；也可将基于特征点空间分布的匹配方法引入其中。针对三维形状的图像描述基于视景（view-based）的描述：采用二维描述形式，将三维原像在不同拍摄方位的投影视为不同的形状，分别进行匹配；基于三维重建（reconstruction-based）的描述：采用三维描述形式，将二维投影结构还原为其三维原像结构，针对不变的三维原像进行匹配；三维描述举例特征匹配在时间域的拓展计算机视觉进展–立体视觉

基础部分II

计算机学院李征主要内容一.计算机视觉领域中的重要问题二.立体视觉的概念与基本原理三.射影几何中的基本概念四.基本的成像模型五.单视几何学的基本原理六.双视几何学的基本原理七.摄像机标定的基本原理三.射影几何中的基本概念1.矩阵与向量间的关系2.几何变换与逆变换3.对偶与对偶变换4.欧氏几何、同射几何、仿射几何、射影几何的概念以及相互间的关系1.矩阵与向量间的关系向量的几何概念：具有长度、方向的几何元素向量表述的几何元素：点、线、面、乃至于N维空间中的线性几何元素向量的具体形式：一组坐标值向量坐标的本质向量坐标的本质：在N维空间中，在给定基向量集的基础上，任意向量在各基向量上的投影给定向量，求坐标：向各基向量投影给定坐标，求向量：以坐标为系数对基向量做线性组合向量坐标的本质oXY矩阵行、列均理解为基向量集矩阵的本质-以旋转为例Y'X'YXOVVXVYV’XV’Y思考：行、列向量组的含义是什么？逆变换θ矩阵的本质-以旋转为例YXY'X'O(x,y)矩阵的本质-以旋转为例YXY'X'O(x,y)矩阵的本质仅考虑N阶方阵，因为一般矩阵可通过添加零向量（行或列）扩展为方阵。任意N阶方阵的行、列向量组分别对应N维空间中两个不同的基向量集（同一基向量集中的不同基向量不一定线性无关），即N维空间中的两个坐标系。矩阵的本质方阵的行向量组为行坐标系基向量在列坐标系下的坐标；列向量组为列坐标系基向量在行坐标系下的坐标。矩阵的本质N阶方阵的本质是N维空间中两个坐标系间的坐标变换。若N阶方阵不是满秩矩阵，即行、列向量组中存在线性相关，则坐标变换中存在降维变换。N阶单位阵的行、列坐标系为同一坐标系，其中无坐标变换。向量变换与坐标系变换YXYY'XX'OOO等价变换向量变换与坐标系变换对任意一种向量变换，可以找到一种等价的坐标系变换与之对应；反之亦然。2.几何变换与逆变换（1）旋转变换与逆变换（2）放缩变换与逆变换（3）平移变换与逆变换（4）射影变换与逆变换（5）变换与逆变换基向量组间关系（1）旋转变换与逆变换旋转变换一一对应于单位正交阵，也称为旋转矩阵，其逆变换即为旋转矩阵的转置。解释：V由R的列坐标系变换到行坐标系，再由行坐标系变换到列坐标系；列坐标系自己向自己投影，即无坐标变换。（2）放缩变换与逆变换YXOYXOY'X'O等价变换沿坐标轴放缩沿坐标轴放缩对于沿坐标轴的放缩，变换矩阵为对角阵，对角线上各元素对应各坐标轴分别的放缩因子。行坐标系与列坐标系相互的坐标描述完全一致。思考：试从投影与线性组合两个角度来解释放缩变换。沿坐标轴放缩-逆变换（2）放缩变换与逆变换YXOαYXOαpp'XαpYOX’Y’ypxpxpyp等价变换沿任意方向放缩变换矩阵为对称阵放缩变换可能改变几何形状（夹角），但不会改变平行性β沿任意方向的放缩对于沿任意方向的放缩，其变换矩阵为对称阵，其含义是先将坐标系旋转到放缩方向，再实施向量放缩，最后再将坐标系旋转回原处。任意对称阵总可以拆分为RTKR的形式。行坐标系与列坐标系相互的坐标描述完全一致。思考：试从投影与线性组合两个角度来解释放缩变换沿任意方向的放缩-逆变换可见，逆变换的放缩方向并无变化，仅将放缩因子变为倒数线性变换N维向量空间中的旋转、放缩变换统称为线性变换。N维空间中的线性变换与N阶方阵一一对应。任一N阶矩阵对应的线性变换均可分解为旋转、放缩两种变换。N阶方阵的特征值分解（SVD）M为任意N阶矩阵，R’表示旋转，RTKR表示任意方向上的放缩（3）平移变换与逆变换在N维向量空间中，平移变换是通过向量加法来实现的，而非矩阵实现的线性变换。如果使用矩阵来实现平移，则必须引入齐次坐标系，将N维向量空间扩展为N+1维空间，称为N维射影空间。为了区分所讨论的向量空间，将N维常规空间称为IRN，将N维射影空间称为IPN。二维射影空间IP2YXOW(0,0,1)(x,y,w)(x/w,y/w,1)Plane:w=1在IP2中，对任意过原点的直线，其上所有点等价，每条过原点直线对应平面w=1上一个点。虽然是3维坐标，但自由度仍为2IR2在IP2中对应于平面w=1三维射影空间IP34维空间中每条过原点的直线等价于w=1这个3维超平面中的一个点虽然是4维坐标，但自由度仍为3三维射影空间IP3如果要针对IP3作图，则必须在4维空间作图，无法实现。但应理解，IR3中的每一点均为IP3中过原点直线在w=1的3维超频面上投影而成的。注：直线（1维）、平面（2维）、3维超平面、乃至N维超平面并没有本质区别，区别仅在于维度。XYW二维平移变换X’Y’W’X’Y’W’通过IP2中的线性变换实现了IR2中的平移变换IPN中平移变换的逆变换思考：试举一例说明IP2中平移变换与其逆变换的关系欧氏变换旋转与平移变换并称欧氏变换。显然，欧氏变换常用于描述刚体放置。注：平移变换在IRN中并非线性变换，它是通过IPN中的线性变换间接实现的。在欧氏变换中，几何形状、大小均不变化，仅坐标系中的方位变化。同射变换旋转、平移、各方向等比放缩并称为同射变换。在同射变换下，几何形状不变化（保持角度、长度比例），但长度、面积等测度，以及方位会变化。仿射变换旋转、平移、放缩并称为仿射变换。在仿射变换下，物体形状、测度、方位均可能变化，但原本平行的几何元素其平行性不变。为什么仿射变换不保持角度、长度比例？存在任意的放缩变换（4）射影变换与逆变换射影变换的含义：将IRN中的N维向量理解为IPN中N+1维向量在N维超平面w=1上的投影；对IPN中N+1维原向量实施变换，则IRN中的N维投影向量随之改变。二维射影变换XYWX’Y’W’X’Y’W’IP2中原像对应的过原点直线发生变化，引起IR2中的像点发生变化在IR2中，像点的变化规律为沿原射线方向变化（IR2原点为起点，变换前像点为终点确定的射线方向）三维射影变换XYZIR3IP3中原像对应的过原点直线发生变化，引起IR3中的像点发生变化在IR3中，像点的变化规律为沿原射线方向变化（IR3原点为起点，变换前像点为终点确定的射线方向）IP3无法作图，只能针对IR3作图观察N维射影变换N维向量的射影变换一定在IPN中才能完成。IPN中的射影变换：在N+1维向量坐标中，改变齐次项w，实质上修改了原像所在的过原点直线，从而引起IRN中N维投影向量的变化，但投影向量的方向总是不变，仅长度发生变化。N维射影变换N维射影变换的逆变换齐次坐标系的意义IRN中的平移变换通过IPN变换矩阵的第N+1列实现；IRN中的射影变换通过IPN变换矩阵的第N+1行实现齐次坐标系的引入，使得IRN中的平移、射影两种非线性变换能够用IRN+1（实质上是IPN）中的线性变换来表示。（5）变换与逆变换基向量组间关系A的行向量与A-1的列向量是同一坐标系下的表述；并且，除对应列外，A中任意一行与A-1中任意一列正交；同样，除对应行外，A-1中任意一列与A中任意一行正交对逆矩阵的一种理解：将A的行向量组投影到A-1的列向量组，由于两个向量组间的正交关系，最终将A中的行向量组变换为单位正交基。总结：A与A-1相乘，可理解为对A的行向量组或A-1的列向量组实施了一种几何变换，变换后它们成为标准正交基3.对偶与对偶变换XYWXYWIR2中的任意2D点可由IP2中3D向量确定;IR2中的任意直线可由IP2中过原点平面确定;IP2中给定一个3D向量，可以确定一个点，也可以确定一个过原点平面IP2IP2IP2中直线的描述YX(a,b)cIR2IP2中点与直线对偶若针对其中一个几何元素存在一个定理，则对其对偶几何元素一定存在一个相应的定理。示例：任意两个不同点确定一条直线任意两条不同直线交于一点（平行直线？）IP2中点与直线对偶XYWIP2PQR若P、Q为两点，则R为两点所确定的直线法向量；若P、Q为两直线法向量，则R为两直线的交点IP3中点与平面对偶在IP3中给定一个向量，可以确定一个IR3的点；也可以确定一个IR3的平面XYZ（a,b,c）IP3中点与平面对偶示例：三个不共线的点确定一个平面三个不共线的平面确定一个点IPN中的对偶关系对偶关系可以推广到N维空间IPN中的点与N-1维超平面对偶IPN中的对偶变换P为N-1维超平面上的点，π为超平面的法线向量若对P实施线性变换A，对π应实施何种变换，使它仍是该超平面的法线向量？对π而言：对偶变换的性质在IPN与IRN+1中是一致的IPN中的对偶变换对A作SVD分解：对P所作变换：对π所作变换：IPN中的对偶变换为什么对偶变换中的放缩变换必须互逆？换言之，为什么放缩互逆才能保角？YX以IR2为例IPN中的对偶变换在IPN中，若要在线性变换后保持两个向量间的角度，则需要对它们实施对偶变换。特别的，若要保证向量相对于某坐标系的坐标在线性变换前后保持不变，则考察向量与坐标系需要作互为对偶的变换。IPN中的对偶变换将A的列坐标系下任一点的列坐标P变换到行坐标系下，得到行坐标P’对P实施线性变换B，若期望经变换A后保持行坐标P’不变，必须对A中行坐标系基向量实施对偶变换4.欧氏、同射、仿射、射影几何（1）无穷远直线、平面（2）环点、绝对二次曲线（3）IPN中的欧氏几何（4）IPN中的同射几何（5）IPN中的仿射几何（6）IPN中的射影几何（1）无穷远直线、平面IP2中一个3D向量可确定IR2中的一条直线，若该向量与W坐标轴同向，直线在何处？（1）无穷远直线、平面对IP2中对无穷远直线的理解（1）无穷远直线、平面IP2中的普通直线IP2中的无穷远直线（1）无穷远直线、平面在IP2中，两条平行直线交于何处？无穷远直线上的某个无穷远点在IP2中，只要两条直线不同，无论是否平行，它们都具有交点。在IP2中，所有同方向的平行直线交于同一无穷远点。（1）无穷远直线、平面IP3中一个4D向量可确定IR3中的一个平面，若该向量与W坐标轴同向，平面在何处？无穷远处，即无穷远平面IP3中两条平行直线交于无穷远平面上一点；两个平行平面交于无穷远平面上一条直线（1）无穷远直线、平面IP3中的普通平面IP3中的无穷远平面（1）无穷远直线、平面同理，无穷远直线、平面的概念可以推广到N维空间IPN中存在N-1维无穷远超平面（2）环点、绝对二次曲线IP2中的二次曲线，包括圆、椭圆（2）环点、绝对二次曲线IP2中的二次曲线，包括圆、椭圆（2）环点、绝对二次曲线IP2中的二次曲线的简化表述如果二次曲线的参数a、b给定，则定下一种椭圆（或圆）所有这种形状的椭圆（或圆）交于如下两点：（2）环点、绝对二次曲线相同形状椭圆的交点也可写作：由于（2）环点、绝对二次曲线特别的，所有圆的交点为：对圆而言：此二点称为环点，环点是所有圆的共同交点，同时也是任意圆与无穷远直线的交点（2）环点、绝对二次曲线IP3中的二次曲面（2）环点、绝对二次曲线所有球面的交线称为绝对二次曲线，它也是任意球面与无穷远平面的交线仅存在一个实点，其余点均在复空间（2）环点、绝对二次曲线绝对二次曲线的概念可以推广到N维空间。在IPN中，存在绝对二次超曲线。（3）IPN中的欧氏几何欧氏变换仅包括旋转、平移变换。问题：以IP2为例，欧氏变换会改变无穷远直线或环点吗？以IP3为例，欧氏变换会改变无穷远平面或绝对二次曲线吗？IP2中平移对无穷远直线的影响对直线上的点实施平移，其法线向量则作对偶变换，实质上为射影变换：变换后法线向量未改变，可见平移不会改变无穷远直线的方位IP3中平移对无穷远平面的影响同理，平移不会改变IP3中无穷远平面的方位。此结论可以推广到IPN中，即平移不会改变IPN中的无穷远超平面。IP2中平移对环点的影响平移前后环点坐标未变，可见平移不改变环点的方位实际上，平移不影响任何无穷远点，由此可以推论，IP3中的平移不影响绝对二次曲线，IPN中的平移不影响绝对二次超曲线

IP2中旋转对无穷远直线的影响直线上的点与法线向量作对偶变换，对旋转变换则是相同的旋转前后无穷远直线的法线向量未改变，说明旋转不改变无穷远直线的方位IP3中旋转对无穷远平面的影响同理，旋转不会改变IP3中无穷远平面的方位。此结论可以推广到IPN中，即旋转不会改变IPN中的无穷远超平面。IP2中旋转对环点的影响旋转前后环点坐标未变，可见旋转不改变环点的方位（复空间内，直线是螺旋形的）IP3中的旋转不影响绝对二次曲线（请自行给出说明），IPN中的旋转不影响绝对二次超曲线

（3）IPN中的欧氏几何在IPN中，欧氏变换不改变无穷远超平面、绝对二次超曲线。无穷远超平面的改变，意味着透视变形；绝对二次超曲线的改变，意味着仿射变形。在欧氏变换下，几何元素无任何变形，仅存在几何元素的方位改变。（4）IPN中的同射几何同射变换包含欧氏变换与各向等比放缩。在IPN中，同射变换不改变无穷远超平面、绝对二次超曲线。（自行说明）同射变换下，几何元素的方位、绝对测度可能改变，但相对形状不改变（5）IPN中的仿射几何仿射变换包括旋转、平移、各向等比或不等比放缩变换。在IPN中，仿射变换是否会影响无穷远超平面、绝对二次超曲线？IP2中不等比放缩对无穷远直线的影响对直线上的点实施放缩，其法线向量则作对偶变换，实质上为互逆的放缩：变换后法线向量未改变，可见不等比放缩不会改变无穷远直线的方位IP3中不等比放缩对无穷远平面的影响同理，不等比放缩不会改变IP3中无穷远平面的方位。此结论可以推广到IPN中，即不等比放缩不会改变IPN中的无穷远超平面。IP2中不等比放缩对环点的影响放缩前后环点坐标改变，可见不等比放缩会改变环点的方位同样的，IP3中的不等比放缩会影响绝对二次曲线，IPN中的不等比放缩会影响绝对二次超曲线

IPN中不等比放缩对绝对二次超曲线的影响不等比放缩会改变IP2中的环点、IP3中的绝对二次曲线、IPN中的绝对二次超曲线，这意味着圆会变形为椭圆、球面会变形为椭球面、超球面会变形为超椭球面。IPN中不等比放缩不改变平行性以IP2中的平行直线为例：假设法线向量已标准化，即（α,β）为单位向量，为IR2中该直线的法线向量与其平行的另一直线可设为：（方向相同，与原点距离不同）IPN中不等比放缩不改变平行性变换后，两平行直线的方向、相互距离都发生变化；但仍保持平行性IPN中不等比放缩不改变平行性此结论可以推广到IPN中，即IPN中不等比放缩变换不会改变N-1维平行超平面间的平行性。容易证明，旋转、平移不改变平行性，因此IPN中的仿射变换不改变平行性。（5）IPN中的仿射几何仿射变换可能改变几何元素的方位、形状，但不会改变几何元素间的平行性。若IPN中的绝对二次超曲线方位发生变化，而无穷远超平面未发生变化，则可以断定IPN中发生的变形为仿射变形。（6）IPN中的射影几何广义的射影变换包括旋转、平移、各向等比或不等比放缩、射影变换。在IPN中，射影变换是否会影响无穷远超平面、绝对二次超曲线？IP2中射影变换对无穷远直线的影响对直线上的点实施射影变换，其法线向量则作对偶变换，实质上为平移变换：变换后法线向量改变，可见射影变换会改变无穷远直线的方位IP2中射影变换对无穷远直线的影响射影变换会将IP2中的无穷远直线拉至与原点间具有有限距离的位置上。变换前，相互平行的直线交于一个无穷远点；变换后，它们交于一个与原点具有有限距离的点，它们还平行吗？不平行，射影变换不保持平行性。示例：目测的或照片中的两根平行铁轨IP2中射影变换对无穷远直线的影响示例：无穷远直线被拉至有限距离IP3中射影变换对无穷远平面的影响同理，射影变换会改变IP3中无穷远平面的方位。此结论可以推广到IPN中，即射影变换会改变IPN中的无穷远超平面。由于在IPN中，绝对二次超曲线在无穷远超平面内，因此绝对二次超曲线也会受到影响。（6）IPN中的射影几何射影变换会改变几何元素的方位、形状，并且不保持平行性。4.欧氏、同射、仿射、射影几何类型旋转平移等比例放缩不等比放缩透视扭曲欧氏几何vv同射几何vvv仿射几何vvvv射影几何vvvvv4.欧氏、同射、仿射、射影几何类型线性相交平行角度长度比例长度欧氏几何vvvvvv同射几何vvvvv仿射几何vvv射影几何vv计算机视觉进展–立体视觉

基础部分III

计算机学院李征主要内容一.计算机视觉领域中的重要问题二.立体视觉的概念与基本原理三.射影几何中的基本概念四.基本的成像模型五.单视几何学的基本原理六.双视几何学的基本原理七.摄像机标定的基本原理四.基本的成像模型ZYX(0,0,-f)(0,0,f)OVirtualProjectionPlaneFactualProjectionPlane基本的小孔成像模型为简化模型，总是使用虚拟成像平面四.基本的成像模型从世界坐标系转换到左摄像坐标系世界坐标系下的原像坐标世界坐标系与左摄像坐标系间的平移图像坐标系原点与光心投影点间的平移图像坐标系内的倾斜因子焦距分别对应两个方向的放缩因子，将长度单位转换为像素左摄像机图像坐标系下的像坐标左摄像机外部参数左摄像机内部参数（1）倾斜因子的几何解释图像中倾斜产生的原因：传感器的原始排列图像中像素的排列原始成像平面数字图像（2）焦距对三维表面重建的影响ZYX(0,0,f)OVirtualProjectionPlane(0,0,1)摆放在正确焦距上的图像原像摆放在默认焦距上的图像四.基本的成像模型plprPOlOrXlXrPlPrflfrZlYlZrYrR,T四.基本的成像模型从世界坐标系转换到右摄像坐标系世界坐标系与右摄像坐标系间的平移右摄像机外部参数右摄像机内部参数五.单视几何学的基本原理单视几何学解决的问题：消除成像平面中平面像结构的仿射、透视变形，使之恢复为真实的原像结构；（针对平面结构的同射重建）五.单视几何学的基本原理单视几何学的应用：针对三维场景中某一平面结构实施同射重建，即生成成像平面与该原像平面平行时所成的图像单视几何学采用的变换模型由于单视几何学仅讨论三维场景中平面结构的成像问题，因此其中的几何变换不需要使用完整的成像模型。单视几何学中采用简化的变换模型。单视几何中的问题分类（1）场景中一个平面结构经透视投影，投影到成像平面，场景平面与成像平面间的变换是怎样的？单视几何中的问题分类（2）摄像机光心不动，成像平面绕光心旋转或调整焦距前后针对同一场景（不一定是平面）所成图像间的几何变换是怎样的？单视几何中的问题分类（3）摄像机自由运动前后，针对同一平面结构所成图像间的几何变换是怎样的？单视几何中的问题分类–归纳单视几何总是讨论两个平面结构之间的变换，此变换可视为IP2中的变换，因此不需要使用IP3中的摄像机模型来描述。单视几何中透视变形的消除给出图像中两对已知平行线（经透视投影，已变得不平行），求得两个交点后，确定无穷远直线，假设法向量为：单视几何中透视变形的消除假设从场景平面到成像平面间的线几何变换（与点几何变换对偶）如下：不影响无穷远直线仅考虑有影响的部分回忆IPN中的对偶变换P为N-1维超平面上的点，π为超平面的法线向量若对P实施线性变换A，对π应实施何种变换，使它仍是该超平面的法线向量？对π而言：考虑对应的点变换注：未体现平面内的旋转、放缩、平移变换，因为他们是仿射变换，不影响无穷远直线点变换为射影变换：对图像施以逆变换，即可消除透视变形：单视几何中透视变形的消除除使用2对已知平行线确定无穷远直线，从而消除透视变形外，还可以使用直线段间已知的长度比例来消除透视变形单视几何中仿射变形的消除假设场景平面与成像平面间的点仿射变换为：旋转与放缩平移这里不考虑射影变换相应的线变换为：单视几何中仿射变形的消除假设已知原像平面中两条直线正交：由于未知参数仅3个，提供3对正交直线可确定矩阵，分解、求逆后可得线变换矩阵（仅包含旋转、放缩），求对偶后可得点变换矩阵经仿射变换，两条像直线的内积已改变单视几何中仿射变形的消除（1）平移：尚有平移变换没有消除，但平移属于欧氏变换，不影响平面结构的形状。（2）方法扩展：给出图像中任意3对已知夹角的直线，即能消除图像中的仿射变换。单视几何中透视、仿射变形的消除使用已知长度比例的3对直线段消除透视变形；使用3对正交直线段消除仿射变形六.双视几何学的基本原理双视几何学解决的基本问题：1）已知摄像机内部参数；2）已通过配准方法获取左、右图像中8个以上的匹配点对；在此条件下，求解两台摄像机的相对放置，并在此基础上对匹配点对实施三维坐标重建。六.双视几何学的基本原理六.双视几何学的基本原理关键概念：1）外极面（EpipolarPlane）：IP3中由左、右摄像机光心与任意原像点构成的平面；2）基线（Base

Line）：IP3中由左、右摄像机光心确定的直线；外极面由基线与原像点确定。六.双视几何学的基本原理3）外极线（Epipolar

Line）：外极面与左、右摄像机成像平面的交线；在左（右）成像平面上给定一个像点，其原像位于由它与左（右）摄像机光心确定的直线上，该直线在右（左）成像平面上的像直线即为其对应的外极线。左（右）成像平面给定像点的匹配像点一定位于右（左）成像平面对应的外极线上。六.双视几何学的基本原理4）外极点（EpipolarPoint）：基线与成像平面的交点因为所有外极面包含基线，所以成像平面内的外极线均过外极点六.双视几何学的基本原理六.双视几何学的基本原理六.双视几何学的基本原理外极几何原理外极线eMmm'l'e'lOO'm'

TFm=0基线外极点外极平面外极线3*3基础矩阵或本征矩阵摄像机模型回顾-左摄像机使用相同的单位，一般为mm原像点投影到单位焦距的像点实际的像点，以像素为单位摄像机模型回顾–右摄像机本征矩阵解析将右像点转换到左摄像坐标系将左像点转换到右摄像坐标系在左摄像坐标系与t作外积在右摄像坐标系与t作外积外极几何的本质：如果左右两个像点对应同一原像，则它们与两个光心共面，即位于同一外极面基础矩阵解析基础矩阵，虽同为3*3矩阵，但其中蕴含了未知的摄像机内部参数本征矩阵与基础矩阵的求解两种矩阵均为3*3矩阵，所描述的外极几何关系是同射性质的，因此矩阵的自由度为8。如果摄像机是标定的，则给出8对像点的mm单位坐标，得到由8个方程构成的方程组，从而求解本征矩阵。如果摄像机是未标定的，则给出8对像点的像素单位坐标，从而求解基础矩阵。本征矩阵分解t求与t的外积本征矩阵分解–求解相对放置内部参数未标定的情况若摄像机未标定，则每种内部参数假定对应一种不同的摄像机相对放置，从而衍生一种不同的重建结果2023/10/26AdvancedTopicsinDatabaseTechnologies217AdvancedTopicsinComputerSciencePresenter:ChuanLiDepartmentofComputerScienceSichuanUniversity/~lichuan2023/10/26AdvancedTopicsinDatabaseTechnologies2182023/10/26AdvancedTopicsinDatabaseTechnologies219Chapter3:DataWarehousingandOLAPTechnology:AnOverviewWhatisadatawarehouse?

Amulti-dimensionaldatamodelDatawarehousearchitectureDatawarehouseimplementationFromdatawarehousingtodatamining2023/10/26AdvancedTopicsinDatabaseTechnologies220DataWarehousingandOLAPTechnology:AnOverviewWhatisadatawarehouse?

Amulti-dimensionaldatamodelDatawarehousearchitectureDatawarehouseimplementationFromdatawarehousingtodatamining2023/10/26AdvancedTopicsinDatabaseTechnologies221WhatisDataWarehouse?Definedinmanydifferentways,butnotrigorously.Adecisionsupportdatabasethatismaintainedseparatelyfromtheorganization’soperationaldatabaseSupportinformationprocessingbyprovidingasolidplatformofconsolidated,historicaldataforanalysis.“Adatawarehouseisa

subject-oriented,integrated,time-variant,andnonvolatile

collectionofdatainsupportofmanagement’sdecision-makingprocess.”—W.H.InmonDatawarehousing:Theprocessofconstructingandusingdatawarehouses2023/10/26AdvancedTopicsinDatabaseTechnologies222DataWarehouse—Subject-OrientedOrganizedaroundmajorsubjects,suchascustomer,product,sales.Focusingonthemodelingandanalysisofdatafordecisionmakers,notondailyoperationsortransactionprocessing.Provideasimpleandconciseviewaroundparticularsubjectissuesbyexcludingdatathatarenotusefulinthedecisionsupportprocess.2023/10/26AdvancedTopicsinDatabaseTechnologies223DataWarehouse—IntegratedConstructedbyintegratingmultiple,heterogeneousdatasourcesrelationaldatabases,flatfiles,on-linetransactionrecordsDatacleaninganddataintegrationtechniquesareapplied.Ensureconsistencyinnamingconventions,encodingstructures,attributemeasures,etc.amongdifferentdatasourcesE.g.,Hotelprice:currency,tax,breakfastcovered,etc.Whendataismovedtothewarehouse,itisconverted.2023/10/26AdvancedTopicsinDatabaseTechnologies224DataWarehouse—TimeVariantThetimehorizonforthedatawarehouseissignificantlylongerthanthatofoperationalsystems.Operationaldatabase:currentvaluedata.Datawarehousedata:provideinformationfromahistoricalperspective(e.g.,past5-10years)EverykeystructureinthedatawarehouseContainsanelementoftime,explicitlyorimplicitlyButthekeyofoperationaldatamayormaynotcontain“timeelement”.2023/10/26AdvancedTopicsinDatabaseTechnologies225DataWarehouse—Non-VolatileAphysicallyseparatestoreofdatatransformedfromtheoperationalenvironment.Operationalupdateofdatadoesnotoccurinthedatawarehouseenvironment.Doesnotrequiretransactionprocessing,recovery,andconcurrencycontrolmechanismsRequiresonlytwooperationsindataaccessing:initialloadingofdataandaccessofdata.2023/10/26AdvancedTopicsinDatabaseTechnologies226DataWarehousevs.HeterogeneousDBMSTraditionalheterogeneousDBintegration:Buildwrappers/mediatorsontopofheterogeneousdatabasesQuerydrivenapproachWhenaqueryisposedtoaclientsite,ameta-dictionaryisusedtotranslatethequeryintoqueriesappropriateforindividualheterogeneoussitesinvolved,andtheresultsareintegratedintoaglobalanswersetComplexinformationfiltering,competeforresourcesDatawarehouse:update-driven,highperformanceInformationfromheterogeneoussourcesisintegratedinadvanceandstoredinwarehousesfordirectqueryandanalysis2023/10/26AdvancedTopicsinDatabaseTechnologies227DataWarehousevs.OperationalDBMSOLTP(on-linetransactionprocessing)MajortaskoftraditionalrelationalDBMSDay-to-dayoperations:purchasing,inventory,banking,manufacturing,payroll,registration,accounting,etc.OLAP(on-lineanalyticalprocessing)MajortaskofdatawarehousesystemDataanalysisanddecisionmakingDistinctfeatures(OLTPvs.OLAP):Userandsystemorientation:customervs.marketDatacontents:current,detailedvs.historical,consolidatedDatabasedesign:ER+applicationvs.star+subjectView:current,localvs.evolutionary,integratedAccesspatterns:updatevs.read-onlybutcomplexqueries2023/10/26AdvancedTopicsinDatabaseTechnologies228OLTPvs.OLAP2023/10/26AdvancedTopicsinDatabaseTechnologies229WhySeparateDataWarehouse?HighperformanceforbothsystemsDBMS—tunedforOLTP:accessmethods,indexing,concurrencycontrol,recoveryWarehouse—tunedforOLAP:complexOLAPqueries,multidimensionalview,consolidationDifferentfunctionsanddifferentdata:missingdata:DecisionsupportrequireshistoricaldatawhichoperationalDBsdonottypicallymaintaindataconsolidation:DSrequiresconsolidation(aggregation,summarization)ofdatafromheterogeneoussourcesdataquality:differentsourcestypicallyuseinconsistentdatarepresentations,codesandformatswhichhavetobereconciledNote:TherearemoreandmoresystemswhichperformOLAPanalysisdirectlyonrelationaldatabases2023/10/26AdvancedTopicsinDatabaseTechnologies230DataWarehousingandOLAPTechnology:AnOverviewWhatisadatawarehouse?Amulti-dimensionaldatamodelDatawarehousearchitectureDatawarehouseimplementationFromdatawarehousingtodatamining2023/10/26AdvancedTopicsinDatabaseTechnologies231FromTablesandSpreadsheetstoDataCubesAdatawarehouseisbasedonamultidimensionaldatamodelwhichviewsdataintheformofadatacubeAdatacube,suchassales,allowsdatatobemodeledandviewedinmultipledimensionsDimensiontables,suchasitem(item_name,brand,type),ortime(day,week,month,quarter,year)Facttablecontainsmeasures(suchasdollars_sold)andkeystoeachoftherelateddimensiontablesIndatawarehousingliterature,ann-Dbasecubeiscalledabasecuboid.Thetopmost0-Dcuboid,whichholdsthehighest-levelofsummarization,iscalledtheapexcuboid.Thelatticeofcuboidsformsadatacube.2023/10/26AdvancedTopicsinDatabaseTechnologies232Cube:ALatticeofCuboidstime,itemtime,item,locationtime,item,location,supplieralltimeitemlocationsuppliertime,locationtime,supplieritem,locationitem,supplierlocation,suppliertime,item,suppliertime,location,supplieritem,location,supplier0-D(apex)cuboid1-Dcuboids2-Dcuboids3-Dcuboids4-D(base)cuboid2023/10/26AdvancedTopicsinDatabaseTechnologies233ConceptualModelingofDataWarehousesModelingdatawarehouses:dimensions&measuresStarschema:AfacttableinthemiddleconnectedtoasetofdimensiontablesSnowflakeschema:Arefinementofstarschemawheresomedimensionalhierarchyisnormalizedintoasetofsmallerdimensiontables,formingashapesimilartosnowflakeFactconstellations:Multiplefacttablessharedimensiontables,viewedasacollectionofstars,thereforecalledgalaxyschemaorfactconstellation

2023/10/26AdvancedTopicsinDatabaseTechnologies234ExampleofStarSchema

time_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcitystate_or_provincecountrylocationSalesFactTable

time_key

item_key

branch_key

location_key

units_sold

dollars_sold

avg_salesMeasuresitem_keyitem_namebrandtypesupplier_typeitembranch_keybranch_namebranch_typebranch2023/10/26AdvancedTopicsinDatabaseTechnologies235ExampleofSnowflakeSchematime_keydayday_of_the_weekmonthquarteryeartimelocation_keystreetcity_keylocationSalesFactTable

time_key

item_key

branch_key

location_key

units_sold

dollars_sold

avg_salesMeasuresitem_keyitem_namebrandtypesupplier_