利用仿射变换的快速空间关系验证
第22卷第4期2010年4月
计算机辅助设计与图形学学报
Jo ur nal of Co mputer A ided Design &Computer G raphics V ol.22N o.4Apr.2010
收稿日期:2009-04-02;修回日期:2009-07-17.基金项目:国家 九七三 重点基础研究发展计划项目(2007CB311100);国家 八六三 高技术研究发展计划(2007AA01Z416);国家自然科学基金(60873165,60802028);北京市科技新星计划项目(2007B071);北京市教育委员会共建项目.汪文英(1982 ),男,博士研究生,主要研究方向为多媒体内容分析和检索;张冬明(1977 ),男,博士,副研究员,硕士生导师,CCF 会员,主要研究方向为视频编解码、视频分析和检索;张勇东(1973 ),男,博士,副研究员,博士生导师,CCF 高级会员,主要研究方向为视频编解码、视频分析和检索;李锦涛(1962 ),男,博士,研究员,博士生导师,CCF 高级会员,主要研究方向为数字媒体处理、虚拟现实、普适计算等.
利用仿射变换的快速空间关系验证
汪文英
1,2)
,张冬明1),张勇东1),李锦涛
1)
1)(中国科学院计算技术研究所前瞻研究实验室 北京 100190)2)
(中国科学院研究生院 北京 100049)(wangw en ying@https://www.wendangku.net/doc/8410427334.html,)
摘要:为了合理利用视觉关键词之间的空间关系,以提高基于视觉关键词的对象检索方法的准确度,提出一种利
用仿射变换进行空间关系验证的算法.首先通过视觉关键词仿射协变的空间邻近特征集进行初步空间关系一致性匹配;然后计算对应仿射协变区块的多组可能的仿射变换矩阵,并选择满足区块匹配最多的变换矩阵作为对象与图像之间最终仿射变换矩阵,其中,仅利用一对协变区块来计算自由度为6的仿射变换的算法有效地提高了计算速度和鲁棒性;最后通过计算出的仿射变换矩阵来精确验证对象与图像之间的空间位置关系是否一致.实验结果表明,与现有方法相比,文中算法更鲁棒,能以较低的计算开销显著地提高基于对象的实时图像检索的准确度.关键词:对象检索;仿射变换;视觉关键词;空间关系验证中图法分类号:T P391.3
Fast Spatial Verification with Affine Transformations
Wang Weny ing
1,2)
,Zhang Dongm ing 1),Zhang Yo ng dong 1),and Li Jintao
1)
1)(Cente r f or A d v anced C omp uting Resear ch ,I nstitute o f Comp uting Te chnology ,Chinese A cad emy of S ciences ,B eij ing 100190)2)
(Grad uate Univ er sity of Chinese Ac ade my o f S cience s,Beij ing 100049)
Abstract :A fast spatial verification scheme using affine transform ations is pro posed to improve the retr ieval pr ecision by ex ploiting proper spatial constraints amo ng visual key w o rds.Fir stly,affine cov ar iant neig hborhoo ds of v isual w ords are used to verify the spatial consistency.Secondly,a set of affine transformation m atrices betw een the cor respo nding covariant regions is calculated,and the matrix w ith the mo st inlier s is chosen as the best matching affine transform ation matrix (BM ATM ).In this step,only a single pair of co rresponding affine cov ariant reg io ns is used to calculate the 6degree of freedom (DOF)affine transfor matio n for acceleratio n.In the last step,the spatial consistency is verified by the BM ATM.Ex perimental r esults show that this schem e is mor e r obust,more accur ate and faster in co mpare w ith the state of the art approaches.
Key words :object based image retrieval;affine transfo rmatio ns;v isual w ords;spatial ver ification 随着数字图像数量的爆炸式增长和大容量存储器的广泛使用,基于对象的图像检索技术成为计算机视觉领域的研究热点之一.其主要目标是设计出一种快速且准确的方法,以从大规模的图像数据库
中挑选出包含指定对象的图像集.
由于基于视觉关键词的对象检索方法对光照变化、旋转缩放以及部分遮挡等都有很强的鲁棒性,它已成为近年来对象检索中的最受欢迎的检索方法.
该方法首先提取仿射协变的特征区块[1 2],通过特征区块描述子得到特征区块特征向量,并将特征向量通过K m eans 等方法进行聚类量化成为视觉关键词;然后通过将图像和对象表示成视觉关键词集合的方式进行检索[3].该方法不依赖于图像分割技术,且对各种条件变化都有很强的鲁棒性,但由于抛弃了视觉关键词之间的空间位置信息,往往区分度不够高.
利用特征之间的空间位置信息提高图像检索的效率和准确度以适应大规模数据库检索的需求成为研究热点[4 6]
,其中通过图像之间的仿射变换的计算来精确验证对象之间的特征匹配是一种有效方法[5,7]
.仿射变换的计算通常采用RANSAC 算法,用不共线的3组对应特征点联立线性方程组来计算仿射变换[7].为了提高仿射变换计算的速度,Philbin 等[5]通过LO RANSAC 算法计算仿射变换,首先假设图像视角不会发生较大变化等限制条件,利用每一组对应仿射协变区块来计算图像之间的自由度受限的仿射变换;然后利用前一步的结果计算不带强假设的仿射变换.然而该算法使用了较强的假设条件,限制了其在对象检索中的应用.
本文提出了一种新的利用仿射变换进行空间关系验证的快速算法.首先,提出了基于仿射协变的邻近特征集的特征匹配算法,以提高特征初步匹配的准确度;然后,提出了一种利用每一组对应仿射协变区块形状特征计算仿射变换的快速算法,并最终选择满足特征点最多的仿射变换,有效地提高图像检索的速度和准确度.
图1 基于快速空间关系验证的对象检索方法框架图
1 基于仿射变换验证的图像检索方法
本文提出的基于空间关系验证的对象检索方法总体框架如图1所示.在预处理阶段进行特征区块检测,提取视觉关键词,并建立基于视觉关键词的索引文件.在检索阶段,首先采用视觉关键词词频的方
法进行初始检索,得到少量图像组成的候选图像集;然后通过仿射协变邻近特征集和仿射变换的估计进行空间关系验证,将所选图像进行重新排序,得到最终检索结果.这种分层检索方法有利于在满足实时性的要求下提高检索准确度.
在基于视觉关键词词频的图像检索方法中,完全丢弃了图像特征之间的空间相对位置关系,为了提高检索的准确度,通常采用验证空间关系的方法来验证特征之间的匹配关系[3,5]
.本文首先通过仿射协变的邻近特征集计算每一对匹配的支持度;然后通过仿射变换的估计来进行空间关系验证;使用满足该仿射变换的特征数来衡量对象与图像之间匹配的程度,从而对检索的初始结果进行重新排序,得到最终的检索结果.1.1 视觉关键词的提取
本文通过MSER 算法[2]
检测局部区块,并使用SIFT 特征[8 9]作为区块描述子.通过对对象和图像上的局部区块描述子的量化,得到对象和图像数据库中的视觉关键词集合.视觉关键词可以使用一个三元组来表示f i =(w i ,X i , i );其中,w i 表示局部区块描述子经过量化后得到的单词标识,X i =(x i ,y i )T 为视觉关键词f i 在图像上的坐标, i 描述了局部区块的形状.描述局部区块的形状的椭圆方程为(X -X i )T
-1
i (X -X i )=1.
假定待检索对象为视觉关键词的集合O ={f o 1,f o 2, ,f on o },n o 为对象中视觉关键词的个数.同样,数据库中的某一待匹配的检索图像也可以表示成为视觉关键词的集合T ={f t 1,f t 2, ,f tn t },其中n t 为图像中包含视觉关键词的个数.这样,局部区块的局部描述子经过量化就形成了一个基础的匹配集
match init (O,T )={ f oi ,f ti |f oi O
f ti T w oi =w ti }.1.2 基于空间一致性的区块匹配
由于视觉关键词由区块特征向量集通过聚类并量化的方式产生,所以它不能够精确地将各种相似特征区分开,通常可通过特征区块之间的空间一致性提高匹配的准确度.文献[3]中使用KNN 算法分别求出对应特征点的最近K 个邻近特征,并通过K 个邻近特征的交集来衡量空间一致性.基于空间上下文
[10]
的匹配方法,通过仿射协变性的空间邻域得
到自适应的多层空间上下文描述,然后使用Fuzzy EM D 距离度量方法计算空间上下文相似性.前一种
方法虽然计算简单,但是未考虑到仿射协变区块的
626
计算机辅助设计与图形学学报 第22卷
仿射协变性,且所有邻近特征都具有相同的权重;后一种基于空间上下文的方法匹配更加准确,但计算复杂度有所增加.
本文采用仿射协变的邻近特征集的方法提高match init 的准确度.对于视觉关键词f k ,同一图像中的其他局部区块与它的距离可以采用仿射协变的Mahalanobis 距离,即
Aff ineDist(f i ,f k )=[(X i -X k )T
-1
k (X i -X k )]1
2. 通过仿射协变的距离计算方法可以得到f k 最近的K 个特征作为仿射协变邻近特征集,从而得到视觉关键词f k 的仿射协变邻近特征集
N (f k )={f i |Af f ineDist (f i ,f k ) d K th f k I f i I i k}.其中,I 表示对象O 或者检索图像T ;d K th 为一个距离阈值,为了得到最近的K 个特征区块,将它动态地设为第K 个最近的距离值.对于match init (O,T )中的每一个初始匹配 w oi ,w ti ,都可以得到一个仿射协变的支持集
S upp ort( f oi ,f ti )={ f ok ,f tk |f ok N(f oi ) f tk N (f ti ) f ok ,f tk match init }.仿射协变区块之间可以通过对应邻近特征集的支持集S upp ort( f oi ,f ti )来度量特征之间的空间一致性,从而得到一个空间一致性匹配集
match spatial (O,T)={ f oi ,f ti | f oi ,f ti match init (O,T) |Sup p or t( f oi ,f ti )| th };其中|S upp or t ( f oi ,f ti )|表示支持集的大小,称为支持度,th 为设置的一个阈值.
1.3 仿射变换计算算法
通过计算图像之间的仿射变换来精确验证对象之间的特征匹配是一种验证空间位置一致性的有效方法[5,7]
.本文分析了现有算法中存在的问题,并提出了一种新的快速仿射变换计算算法.1.3.1 LO RANSAC 算法
现有方法通过RA NSA C 进行随机采样的方法来计算仿射变换,通过多次迭代挑选出满足特征点最多的仿射变换来进行估算.
为了提高空间关系验证中仿射变换计算的速度,达到实时要求,Philbin 等[5]提出一种基于LO RANSAC 算法的快速仿射变换算法.该算法通过2步来进行仿射变换计算:首先,通过假设互联网中大部分图像不会发生较大视角变化等限制条件,在限制仿射变换的自由度(deg ree of freedom,DOF)的条件下,利用每一组对应仿射协变区域估计图像之间
的受限仿射变换,得到初始的仿射变换和初始的特
征匹配;然后根据前一步骤得到的匹配,通过局部优化步骤计算出不带假设的6DOF 的仿射变换,其中5DOF 的仿射变换是通过2个仿射协变区块的归一化求得垂直切变的仿射变换.在归一化变换中,将(0,1)T
作为归一化变换的特征向量,仿射协变区块与归一化的单位圆形区块保持相同的正立姿势,如图2a 所示.
图2 仿射变换示意图
Philbin 等[5]的LO RANSAC 算法能够通过每一组对应仿射协变区块计算自由度受限的仿射变换.然而由于自由度受限的仿射变换只能描述平移和垂直方向的切变,在实际图像数据库中,图像由于视角的变化往往会发生旋转和各向切变,甚至发生翻转.在这些发生较大角度变化的情况下,该算法就不能得到近似正确的初始仿射变换,这种较强的假设严重限制了其在图像检索中的应用.1.3.2 快速仿射变换计算算法
本文设计了一种利用一组对应仿射协变区块形状快速计算不带假设的(6DOF)仿射变换的方法.对于match spatial (O,T )中的每一组匹配 f oi ,f ti 都可以计算出一种仿射变换A ii ,并将A ii 满足的视觉关键词的个数作为衡量该仿射变换的标准,即inlier (A ii )={ f ok ,f tk | A ii X ~
ok ,X ~
tk d th f ok ,f tk match in it }.
其中, 表示欧氏方程,X ~
表示齐次坐标.本文选择满足视觉关键词最多的仿射变换A obest,tbest 为最终对象到图像的仿射变换,并用|inlier(A obest,tb est )|来度量对象与图像之间视觉关键词空间关系匹配的程度.
对于仿射协变区块f oi 和f
ti
,通过
X T -1t X =X T (C t C T t )-1
X = X T (C t R t R T t C T t )-1X =1,t =oi ,ti
(1)
对仿射协变区块的形状特征进行分解.其中,C t 表示对椭圆区域的归一化,R t 表示一定角度的旋转.可以看出,归一化之后得到的单位圆区域发生任何
627
第4期汪文英,等:利用仿射变换的快速空间关系验证
的旋转都不会改变其原本形状特征 t (t =oi,ti ).从而,对应仿射协变区块之间的仿射变换
A ( f oi ,f ti )=C ti R ti R -1oi C -1
oi .
由此将仿射变换分解为归一化变换H 1(对应
C -1oi )、旋转变换H r (对应R ti R -1oi )和还原变换H -12
(对应C ti )3个变换步骤,如图2b 所示.
在如图2b 所示的仿射变换算法中,准确计算经过仿射区块归一化变换之后的单位圆形区块O 1与O 2之间的旋转角度 尤为重要.由式(1)可以看出,归一化变换之后单位圆区域发生任何的旋转变换都不会改变其原本形状特征 t (t =oi,ti ),所以要精确计算出图像之间的仿射变换,必须借助其他信息来确定仿射协变区块之间的旋转角度.通常的方法是使用特征区块描述子中区块的方向来计算旋转角度.如在SIFT 描述子中,将梯度方向直方图的主能量值作为该区块的方向[11].使用这种方法存在2个不足:1)方向已经被量化到数量有限的离散值,使得方向不够准确;2)存在多个方向且无法确定对应关系时会得出多个可能的旋转角度,从而增加计算的复杂度.
本文提出了一种参考仿射协变邻近特征集来精确计算仿射协变区块之间旋转角度的方法.在第1.2节中介绍的基于空间一致性的区块匹配方案中,经过空间关系验证得到的匹配集m atch spatial (O,T )中,每一组空间一致性的匹配 f oi ,f ti 都有一组支持其匹配的支持集S upp or t( f oi ,f ti ).如图3所示,对于一组匹配的仿射协变区块 f oi ,f ti ,存在着n(K n th )组邻近特征{ N i 1,N i 1 , N i 2,N i 2 , , N in ,N i n }的支持
.
图3 参考邻近特征集的旋转变换计算方法
仿射协变区块的归一化变换有2个步骤,首先将区块的中心平移到x ,y 坐标的原点,然后将椭圆
区域转换成单位圆形区块.经过仿射协变区块的i 和i 的归一化变换之后,f oi ,f ti 将会重叠在单位圆
上,得到一个旋转夹角 k = N ik O ii N i k ,其中O ii 表示仿射协变区块f oi 和f ti 经过归一化之后重叠的单位圆区块.对于有n(n th)组邻近特征支持的仿射协变区块的匹配,将会得到n 种旋转夹角{ 1,
2, ,
n },从而实现了从位置空间向旋转角度参数空间的转换.通过哈夫变换得到最佳的旋转夹角
ii ,进而得到该组匹配 f oi ,f ti 对应的仿射变换为A ii =H -1
2H r H 1,其中,
H r =cos ii -sin ii
sin ii cos ii
.
与文献[5]中基于LO RANSAC 算法的仿射变换算法相比,本文算法有3个优点:1)LO RANSAC 算法通过一组对应仿射协变区块计算出的受限制的仿射变换,需要进一步通过优化步骤计算6DOF 的仿射变换;而在本文算法中,match spatial (O,T )中的每一组对应的仿射协变区块都能计算出6DOF 仿射变换,最终选择满足特征最多的仿射变换作为结果,所以其计算量更小.2)文献[5]中也使用到了归一化变换,但其中归一化变换中将(0,1)T 设为归一化变换的特征向量,以保证仿射协变区块与归一化的单位圆形区块保持相同的正立姿势;而在本文算法中归一化变换由仿射协变区块定义,没有使用较强的假设条件.3)本文增加了旋转变换,这是由于本文算法没有限制归一化变换保持正立姿势,准许图像之间发生较大的视角变化,所以本文算法更加鲁棒.
2 实验及结果分析
本文通过识别基准的数据库[4 5]来测试比较对象检索算法.该图像数据库包含10200幅图像,其中每4幅一组,为同一个场景不同视角、不同光照条件下的图像.选择这样的图像集是因为其中包含了大量物体,贴近实际的图像检索的应用.实验平台为P43.2GH z CPU ,1.5GB 内存的计算机.在实验中,随机圈出150个矩形区域作为检索对象,检索效果通过同一组的4幅图像上的对象被检索并排在前4名的比率来衡量.
我们将本文方法与VideoGoog le [3]中KNN 算
法和快速仿射变换验证检索算法
[5]
进行比较.为了
比较的公平性,在所有的检索方法中使用相同的M SER 特征、相同的SIFT 128维描述子和相同的
628
计算机辅助设计与图形学学报 第22卷
视觉词典.在前处理过程中,通过MSER 提取最大稳定连通区域的方式提取约107个仿射协变局部区块以及相应的SIFT 描述子,然后通过随机选取105个局部描述子进行K m eans 聚类,形成大小为103
的视觉关键词词典,其中特征提取大约花费2d 的
时间.
在本文算法和文献[5]算法的比较中,通过分别提取基于视觉关键词的检索方法中的前200,400,600和800个图像进行验证并重新排序,其中仿射协变空间邻近特征的选择中K 取为10,th 取为3,d th 取为4.文献[5]算法中首先通过5DOF 的仿射估计出最佳的仿射变换,然后通过LO RANSAC 算法计算出6DOF 的完全仿射变换来进行验证.通过图4可以看出,本文算法比文献[5]算法有显著的改善,由于文献[5]算法对仿射变换进行了较强的假设,而本文测试数据库中图像多来自不同视角,发生如图4所示的较大角度的旋转甚至翻转,所以其对检索的准确度的提高很有限.采用本文算法进行检索的计算时间随对象包含的视觉关键词的数目变化,由图5可以看出,当分别从前200,400,600和800个图像中进行估计仿射变换时,检索时间基本上与匹配的图像数保持线性关系,且平均检索时间保持在1s 以内,能够满足实时性的要求
.
图4
平均检索准确度
图5 平均检索时间
从图6a 中可以看出,若不通过空间一致性检验,视觉关键词之间存在大量的误匹配;图6b~6c 所示为通过提取10个近邻并限制支持集大于3的方式进行空间一致性匹配,再进行仿射变换计算的结果.图6b 所示为本文算法得到的仿射变换图,可以看出,虽然图像发生了较大强度的旋转和切变,但每一组对应的仿射协变区块可以基本准确地确定仿射变换,且每组对应特征确定的仿射变换有较好的一致性.图6c 中由于图像有较大的视角变化,导致文献[5]中5DOF 的方法不能计算出近似正确的仿射变换,从而导致漏检.图7第一行给出了该对象通过本文算法的检索结果,可以看出,当图像发生较大角度的视角变化时,仍能够准确检索.而在LO RA NSA C 算法的检索结果中,靠右边的2幅图像被漏检
.
图6 空间关系示意图
图7所示为部分检索结果实例,可以看出,虽然部分图像由于视角的变化发生了较大角度的旋转和切变,但本文算法也能够比较准确地计算出它们之
间的仿射变换,从而进一步验证了对象的匹配.
629
第4期汪文英,等:利用仿射变换的快速空间关系验证
图7 部分检索结果
3 结 论
为了提高对象检索的准确度和速度,本文提出了一种新的利用仿射变换进行空间关系验证的快速算法.首先通过仿射协变的空间邻近特征集进行初步匹配,然后通过仿射变换来进行空间关系验证.
与现有方法相比,本文算法有三大优点:1)仿射协变的空间邻近特征集有效地减少了初始误匹配,从而减少了空间一致性验证的无用计算;2)与现有的利用3组对应的特征来计算仿射变换的方法相比,本文提出了利用每一组对应的仿射协变区块计算仿射变换的方法,并选择满足特征点最多的仿射变换作为对象与检索图像之间的仿射变换,从而显著地提高了计算效率;3)与LO RANSAC算法相比,本文算法不仅效率更高,而且对旋转和各向切变都有更强的鲁棒性.
实验结果表明,本文算法在保证实时性的条件下,有效地提高了基于对象的图像检索的效率和准确度.
参考文献(References):
[1]M atas J,Ch um O,U rban M,e t al.Robus t w ide baseline
stereo from max imally s table extrem al region s[J].Image and Vision Computing,2004,22(10):761 767
[2]M ikolajczyk K,T uytelaars T,S chm id C,et al.A com paris on
of affine region detectors[J].International J ou rnal of Computer Vis ion,2006,65(1):43 72
[3]Sivic J,Zis serman A.VideoGoogle:a text retrieval approach
to object matchin g in videos[C] Proceedings of the9th IEEE Intern ational Conference on Computer Vis ion,
Wash ington D C,2003:1470 1477
630计算机辅助设计与图形学学报 第22卷
[4]Nist r D,Stew ni us H.Scalable recogni tion w ith a vocabulary
tree[C] Proceeding s of the IEEE Computer S ociety
C onference on Computer Vision and Pattern Recognition,
N ew York,2006:2161 2168
[5]Philbin j,C hum O,Isard M,e t al.Object retrieval w ith large
vocabularies and fast spatial m atch ing[C] Proceedin gs of the IEEE Conference on Computer Visi on and Pattern Recogni tion, M inneapolis,2007:1 8
[6]Zheng Q F,W ang W Q,Gao W.Effective and efficient
ob ject based im age r etrieval usin g visu al ph ras es[C] Proceedin gs of the14th ACM In ternation al Conference on M ultimedia,Santa Barb ara,2006:77 80
[7]L ow e D G.Distinctive im age featu res from s cale invariant
k eypoints[J].In ternation al Journal of Computer Vision, 2004,60(2):91 110
[8]M ikolajczyk K,Schmid C.Scale&affin e invariant interest
point detectors[J].International J ou rnal of Computer Vision,2004,60(1):63 86
[9]Low e D G.Ob ject recognition from local scale in variant
featu res[C] Proceedings of International Con feren ce on Computer Vis ion,Kerkyra,1999:1150 1157
[10]Gao Ke,Lin S houxun,Zh ang Yon gd on g,et al.Object based
image retrieval usin g spatial con text[J].J ou rnal of Computer Aided Design&Computer Graphics,2008,20
(11):1452 1458(in Ch ines e)
(高 科,林守勋,张勇东,等.基于空间上下文的目标图像检索[J].计算机辅助设计与图形学学报,2008,20(11): 1452 1458)
[11]Carneir o G,Jepson A D.Flexible s patial configuration of
local image features[J].IE EE Transactions on Pattern Analysis and M achine Intelligen ce,2007,29(12):2089 2104
(上接第624页)
[15]Kass M,Witkin A,Terzopoulos D.Snakes:active contour
m od els[J].International J ou rnal of Computer Vision,1988,
1(4):321 331
[16]M on tagnat J,Deling ette H,Ayache N.A review of
deform able s urfaces:topology,geometry and d eformation
[J].Image and Vis ion Computing,2001,19(14):1023
1040
[17]Borgefors G.Distance transformation s in digital imag es[J].
C om puter Vision,Graphics,an d Im age Proces sing,1986,34
(3):344 371
[18]Grevera G J.Th e dead reckonin g sign ed distan ce
transform[J].Computer Vision and Image U nders tanding,
2004,95(3):317 333
[19]Rem y E,T hiel https://www.wendangku.net/doc/8410427334.html,pu tin g3D m edial axis for chamfer
dis tances[M] Lectu re Notes in Computer S cien ce.
H eidelb erg:Springer,2000,1953:418 430
[20]H oppe H,DeRose T,Du champ T,e t al.M esh optim ization
[C] Proceedings of the20th International Conference on
C om puter Grap hics and In teractive Techniques,Anah eim,
1993:19 26
[21]S ong P,W u X J,Wang M Y.A robu st an d accurate meth od
for visual hu ll com putation[C] Proceedings of th e IEEE
International Con feren ce on Information and Automation,
M acau,2009:784 789
631
第4期汪文英,等:利用仿射变换的快速空间关系验证
利用空间向量求空间角教案设计
利用空间向量求空间角 一、高考考纲要求： 能用向量方法解决异面直线的夹角、线面角、面面角问题．体会向量法在立体几何中的应用． 二、命题趋势： 在高考中，本部分知识是考查的重点内容之一，主要考查异面直线所成角、线面角、面面角的计算，属中档题，综合性较强，与平行垂直联系较多. 三、教学目标 知识与技能：能用向量法熟练解决异面直线的夹角、线面角、面面角的计算问题，了解向量法在研究立体几何问题中的应用； 过程与方法：通过向量这个载体，实现“几何问题代数化”的思想，进一步发展学生的空间想象能力和几何直观能力； 情感态度价值观：通过数形结合的思想和方法的应用，进一步让学生感受和体会空间直角坐标系，方向向量，法向量的魅力. 四、教学重难点 重点：用向量法求空间角——线线角、线面角、二面角； 难点：将立体几何问题转化为向量问题. 五、教学过程 （一）空间角公式 1、异面直线所成角公式：如图，设异面直线l ，m 的方向向量分别为a r ,b r ,异面直线l ，m
2、线面角公式：设直线l 为平面α的斜线，a r 为l 的方向向量，n r 为平面α的法向量，θ为 l 与α所成的角，则sin cos ,a n θ==r r a n a n ?r r r r . 3、面面角公式：设1n r ，2n r 分别为平面α、β的法向量，二面角为θ，则12,n n θ=r r 或 12,n n θπ=-r r （需要根据具体情况判断相等或互补） ，其中121212 cos ,n n n n n n ?=r r r r r r . α θ O n r a
（二）典例分析 如图，已知：在直角梯形OABC 中，//OA BC ，90AOC ∠=o ，SO ⊥面OABC ，且 1,2OS OC BC OA ====.求： （1）异面直线SA 和OB 所成的角的余弦值； （2）OS 与面SAB 所成角α的正弦值； （3）二面角B AS O --的余弦值. 解：如图建立空间直角坐标系，则(0,0,0)O ， (2,0,0)A ，(1,1,0)B ，(0,1,0)C ，(0,0,1)S ， 于是我们有(2,0,1)SA =-u u r ，(1,1,0)AB =-u u u r ，(1,1,0)OB =u u u r ，(0,0,1)OS =u u u r ， （1）cos ,5SA OB SA OB SA OB ?== =u u r u u u r u u r u u u r u u r u u u r ， 所以异面直线SA 和OB 所成的角的余弦值为5 . （2）设平面SAB 的法向量(,,)n x y z =r ， 则0,0, n AB n SA ??=???=??r u u u r r u u r ，即0,20.x y x z -+=??-=? 取1x =，则1y =，2z =，所以(1,1,2)n =r ， sin cos ,3OS n OS n OS n α?∴=== =u u u r r u u u r r u u u r r . （3）由（2）知平面SAB 的法向量1(1,1,2)n =u r ， 又OC ⊥Q 平面AOS ，OC ∴u u u r 是平面AOS 的法向量， 令2(0,1,0)n OC ==u u r u u u r ，则有121212 cos ,n n n n n n ?== =u r u u r u r u u r u r u u r . ∴二面角B AS O --O A B C S
第十五章组织力量的整合
第十五章组织力量的整 合 集团标准化工作小组 [Q8QX9QT-X8QQB8Q8-NQ8QJ8-M8QMN]
第十五章组织力量的整合 ? 一、教学要点 1、正式组织与非正式组织的区别。 2、非正式组织对正式组织的积极作用和不利影响。 3、如何发挥非正式组织的作用 4、直线和参谋的内涵。 5、直线和参谋的矛盾表现。 6、如何正确发挥参谋的作用 7、运用委员会的理由。 8、委员会的局限性。 9、如何提高委员会的工作效率 10、关键名词：正式组织、非正式组织、直线关系、参谋关系、委员会 ? 二、习题 (一)填充题 1.正式组织以成本和效率为主要标准，维系正式组织的主要是_________的原则，而维系非正式组织的主要是____________上的因素。 2.组织文化是指被组织成员共同接受的________、________、__________等群体意识的总称。 3.组织中的管理人员是以___________和__________两类不同的身份来从事管理工作的。 4.直线关系是一种______和_______的关系，授予直线人员的是________和 ________权力。 5.参谋关系是一种______和_______的关系，授予参谋的是思考、筹划和建议的权力。 6.委员会的工作方式所具有的局限性是___________, _____________, _____________。 7.向参谋授予必要权力之后，要防止出现________________的危险。 8.谨慎地使用职能权力，包括两层含义，首先要认真分析授予职能权力的 _________，其次要明确职能权力的_____________。 9.委员会的规模主要受到两个因素的影响：____________和_____________。 10.在确定委员会的规模时，要努力在追求___________和__________这两者之间取得适当的平衡。 11.组织设计的结果形成____________组织，而___________组织是伴随着它的运转而形成的。 12.非正式组织要求成员___________的压力，往往也会束缚成员的个人发展。? (二)选择题 1．下列关于非正式组织不正确的说法是________________。 A.非正式组织主要以感情和融洽为主要的标准； B.正式组织与非正式组织是交叉混合的； C.非正式组织的危害要大于积极作用； D.非正式组织会发展组织的惰性。 2.下列关于委员会的说法中不正确的是_________________-。
计算机图形学报告_仿射变换最小二乘法
计算机图形学报告仿射变换最小二乘法 姓名： 班级： 学号：
仿射变换的定义 仿射变换（Affine Transformation或 Affine Map），是指在几何中，一个向量空间进行一次线性变换并接上一个平移，变换为另一个向量空间。 一个对向量平移一般可用如下公式表示： 等价于： 仿射变换可以由以下基本变换复合而成：平移（Translation）、缩放（Scale）、翻转（Flip）、旋转（Rotation）和错切（Shear），这些基本的变换如下图1表示： 图1 下图2中变换矩阵将原坐标(x, y)变换为新坐标(x', y') 图2
最小二乘法 最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。 这是一个示例：某次实验得到了四个数据点：、、、 （图3红色的点）。我们希望找出一条和这四个点最匹配的直线 ，即找出在某种“最佳情况”下能够大致符合如下超定线性方程组 的和： 图3 最小二乘法采用的手段是尽量使得等号两边的方差最小，也就是找出这个函数的最小值： 最小值可以通过对分别求和的偏导数，然后使它们等于零得 到。 如此就得到了一个只有两个未知数的方程组，很容易就可以解出： 也就是说直线是最佳的。
仿射变换最小二乘法 景物在成像过程中产生的扭曲，会使图像的比例失调，可用仿射变换来校正各种畸变。而仿射变换的参数可以用最小二乘法进行估算。 设原图像为f(x,y)，畸变后的图像为F(X',Y')，要将F(X',Y')恢复为f(x,y)，就是要找到(X',Y')坐标与(x,y)坐标的转换关系，这个转换关系称为坐标变换，表示为(x,y)=T(X',Y')。 景物在成像过程中产生的扭曲，会使图像的比例失调，可用仿射变换来校正各种畸变。先计算出坐标变换的系数，仿射变换的表达式为:R(x)=Px+Q, x=(x,y)是像素的平面位置，P是2*2的旋转矩阵，Q是2*1的平移向量，P、Q即为仿射变换参数，即： x= AX' + BY' + C y= DX' + EY' + F 因此，几何畸变的校正归根结底为坐标转换系数A,B,C,D,E,F的求解。 为了防止出现空像素，一般采用反向映射，由最小二乘法得(matlab)： vec1 = inv([X Y I]'*[X Y I])*[X Y I]'*U; vec2 = inv([X Y I]'*[X Y I])*[X Y I]'*V; 其中vec1＝[A B C]'; vec2 =[D E F]'; X Y U V I分别是x，y，X', Y', 1构成的向量。 最小二乘法估计就是估计原始坐标点与经过变换后的坐标点之间的关系，从通过这种关系进行矫正图像，大体步骤如下：
利用空间向量求空间角考点与题型归纳
利用空间向量求空间角考点与题型归纳 一、基础知识 1．异面直线所成角 设异面直线a ，b 所成的角为θ，则cos θ＝|a ·b | |a ||b | ? ， 其中a ，b 分别是直线a ，b 的方向 向量． 2．直线与平面所成角 如图所示，设l 为平面α的斜线，l ∩α＝A ，a 为l 的方向向量，n 为平面α的法向量， φ为l 与α所成的角，则sin φ＝|cos 〈a ，n 〉|＝|a ·n | |a ||n | ? . 3．二面角 (1)若AB ，CD 分别是二面角α-l -β的两个平面内与棱l 垂直的异面直线，则二面角(或其补角)的大小就是向量AB ―→与CD ―→ 的夹角，如图(1)． (2)平面α与β相交于直线l ，平面α的法向量为n 1，平面β的法向量为n 2，〈n 1，n 2〉＝θ，则二面角α -l -β为θ或π－θ.设二面角大小为φ，则|cos φ|＝|cos θ|＝ |n 1·n 2| |n 1||n 2| ? ，如图(2)(3)． 两异面直线所成的角为锐角或直角，而不共线的向量的夹角为(0，π)，所以公式中要加绝对值． 直线与平面所成角的范围为????0，π 2，而向量之间的夹角的范围为[0，π]，所以公式中要加绝对值． 利用公式与二面角的平面角时，要注意〈n 1，n 2〉与二面角大小的关系，是相等还是互
补，需要结合图形进行判断． 二、常用结论 解空间角最值问题时往往会用到最小角定理 cos θ＝cos θ1cos θ2. 如图，若OA 为平面α的一条斜线，O 为斜足，OB 为OA 在平面α内的射影，OC 为平面α内的一条直线，其中θ为OA 与OC 所成的角，θ1为OA 与OB 所成的角，即线面角，θ2为OB 与OC 所成的角，那么cos θ＝cos θ1cos θ2. 考点一 异面直线所成的角 [典例精析] 如图，在三棱锥P -ABC 中，P A ⊥底面ABC ，∠BAC ＝90°.点D ，E ，N 分别为棱P A ，PC ，BC 的中点，M 是线段AD 的中点，P A ＝AC ＝4，AB ＝2. (1)求证：MN ∥平面BDE ； (2)已知点H 在棱P A 上，且直线NH 与直线BE 所成角的余弦值为7 21 ，求线段AH 的长． [解] 由题意知，AB ，AC ，AP 两两垂直，故以A 为原点，分别以AB ―→，AC ―→，AP ―→ 方向为x 轴、y 轴、z 轴正方向建立如图所示的空间直角坐标系．依题意可得A (0，0,0)，B (2，0,0)，C (0,4,0)，P (0，0,4)，D (0,0,2)，E (0,2,2)，M (0，0,1)，N (1,2,0)． (1)证明：DE ―→＝(0,2,0)，DB ―→ ＝(2,0，－2)． 设n ＝(x ，y ，z )为平面BDE 的法向量， 则????? n ·DE ―→＝0，n ·DB ―→＝0， 即????? 2y ＝0，2x －2z ＝0. 不妨取z ＝1，可得n ＝(1,0,1)．
仿射变换
仿射变换
————————————————————————————————作者：————————————————————————————————日期:
第四章保距变换和仿射变换 本章教学目的：通过本章的学习,使学生掌握保距变换和仿射变换这两类重要的几何变换,从而深化几何学的研究，并掌握解决几何问题的一个有效方法。 本章教学重点：(1）保距变换和仿射变换的定义和性质; (2）仿射变换的基本定理； (３）保距变换和仿射变换的变换公式; (４)图形的仿射分类与仿射性质。 本章教学难点：仿射变换的性质和基本定理;仿射变换的变换公式的求法。 本章教学内容： §1 平面的仿射变换与保距变换 1.1――对应与可逆变换 集合X到集合Y的一个映射f:X→Ｙ是把X中的点对应到Y中的点的一个法则,即?ｘ∈X,都决定Y中的一个元素f(ｘ)，称为点ｘ在ｆ下的像。对X的一个子集A,记 f(Ａ)={ｆ（a)|ａ∈A}， 它是Y的一个子集，称为A在f下的像。对Y的一个子集Ｂ,记 f-1(B）={x∈Ｘ|f(ｘ)∈Ｂ｝， 称为B在F下的完全原像,它是X的子集。 如果f是X到Y的映射,ｇ上Y到Z的映射,则它们的复合上X到Z的映射,记作 gｆ: Ｘ→Ｚ，规定为 g f(x)=g(f(ｘ）),?ｘ∈Ｘ. 对A?X， gｆ(A)＝ｇ(f(A)); 对C?Z， （g f)-1(C）＝f－１（g－1(C)). 映射的复合无交换律，但有结合律。 映射f: X→X称为X上的一个变换，iｄX: X→X,?x∈X，ｉd X（x）＝x,称为X的恒同变换。 对映射f: X→Y，如果有映射g：Y→X,使得 g f＝ idＸ：X→X,fｇ=ｉdＹ:Y→Y, 则说ｆ是可逆映射，称ｇ是f的逆映射。 如果在映射f： X→Y下X的不同点的像一定不同,则称ｆ是单射。如果f(Ｘ）=Ｙ，则称f是满射。 如果映射f: X→Ｙ既是单射,又是是满射，则称f为——对应。此时?f－1f=ｉd X,, ｆf-1= ｉdＹ,于是f是可逆映射,并且ｆ的逆映射是f-1。 一个集合X到自身的可逆映射称为X上的可逆变换。 1．2平面上的变换群 平移取定平行于平面的一个向量u,规定π的变换P u：π→π为:?Ａ∈π，令P u AP（A）=u的点。称P u为π上的一个平移，称向量u是P u的平移量。（Ａ）是使得 u
第六章 组织与组织变革习题
精心整理 2019年－9月 第六章 组织与组织变革 一、单项选择题 1.管理者为实现组织目标而建立和协调组织结构的一系列工作过程叫做（ ）。 A 结构设计 B 组织 C 组织变革 D 人员配备 2.（ ）把权力划分为法理权.奖赏权.A 韦伯 B 巴纳德 C 弗兰奇&雷文 D 法约尔 3.关于部门化，现代的观点更加强调（ A 区域部门化 B 产品部门化 C 顾客部门化 D 过程部门化 4.A B C D 5.（ A B C 委员会D 6.（ ）一般为临时结构，多为达成特定复杂任务而设立。 A 多维矩阵 B 任务小组 C 股东委员会 D 虚拟企业 7.在管理学上，人们基于相互联系的需要而自发地建立的社会关系的网络叫做（ ）。 A 非正式组织 B 群体 C 非正式网络
精心整理 2019年－9月 D 小集团 8.着名的“解冻——变革——冻结——解冻……”的三阶段理论是（ ）提出的。 A 罗宾斯 B 孔茨 C 卢因 D 库兹 9.（ ）与有机结构是两种不同的典型组织形式。 A 直线职能结构 B 机械机构 C 无机机构 D 直线结构 10.设立和变革组织结构的工作叫做（ A 组织设计 B 组织变革 C 结构设计 D 结构调整 11.A 复杂化 B 正规化 C 集权化 D 分化度12.A 绝对 B 无关 C D 相对 13. ）通过《战略与结构》的写作做出了较A 孔茨 B 法约尔 C 钱德勒 D 韦伯 14.（ ）不属于有机式组织设计选择。 A 简单结构 B 矩阵型结构 C 企业集团 D 事业部型结构 15.（ ）不属于机械式组织设计选择。 A 直线型结构
.. B直线职能型结构 C委员会结构 D职能型结构 16.当员工人数较少，或者组织是新建的.环境简单的时候，（）结构效果较好。A直线职能型 B直线型 C任务小组 D矩阵 17.以下关于组织变革带给员工压力的说法中，错误的是（）。 A压力本质上并不是不好的东西，有压力也未必就是件坏事。 B压力的根源在于与组织有关的因素及员工自己生活中衍生的因素。 C最好的管理者能够通过自身努力根除变革给下属带来的压力。 D降低压力水平的努力需要始于员工的甄选。 18.以下关于结构与战略的说法中，错误的是（）。 A组织结构必须服从组织所选择的战略的需要 B战略选择的不同，会直接影响到组织结构的选择 C结构紧跟战略，在20世纪70年代是西方成功企业的一般做法 D不同的战略对业务活动提出不同的要求，但一般不会影响到管理结构的设计 19.（）结构更可能造成多头指挥，从而降低组织效率。 A直线型 B事业部型 C任务小组 D职能型 20.直线型结构最大的优点是（）。 A结构简单.命令统一 B在命令统一基础上可充分发挥专家的作用 C强调结果，会提高效率 D对于环境的适应性高 21.状师能够帮人写状子.打官司，主要是基于他的（）。 A职权 B专家权 C个人影响权（模范权） D强制权 22.权力的分散主要是通过（）和授权两个途径来实现。 A制度分权 B部门再细分 C一人多职 D权力简化 23.以下机构中，更多行使参谋职能的是（）。 ..
第十五章 组织力量的整合
第十五章组织力量的整合 一、教学要点 1、正式组织与非正式组织的区别。 2、非正式组织对正式组织的积极作用和不利影响。 3、如何发挥非正式组织的作用？ 4、直线和参谋的内涵。 5、直线和参谋的矛盾表现。 6、如何正确发挥参谋的作用？ 7、运用委员会的理由。 8、委员会的局限性。 9、如何提高委员会的工作效率？ 10、关键名词：正式组织、非正式组织、直线关系、参谋关系、委员会 二、习题 (一)填充题 1.正式组织以成本和效率为主要标准，维系正式组织的主要是_________的原则，而维系非正式组织的主要是____________上的因素。 2.组织文化是指被组织成员共同接受的________、________、__________等群体意识的总称。 3.组织中的管理人员是以___________和__________两类不同的身份来从事管理工作的。 4.直线关系是一种______和_______的关系，授予直线人员的是________和________权力。 5.参谋关系是一种______和_______的关系，授予参谋的是思考、筹划和建议的权力。 6.委员会的工作方式所具有的局限性是___________,_____________,_____________。 7.向参谋授予必要权力之后，要防止出现________________的危险。 8.谨慎地使用职能权力，包括两层含义，首先要认真分析授予职能权力的_________，其次要明确职能权力的_____________。 9.委员会的规模主要受到两个因素的影响：____________和_____________。 10.在确定委员会的规模时，要努力在追求___________和__________这两者之间取得适当的平衡。 11.组织设计的结果形成____________组织，而___________组织是伴随着它的运转而形成的。 12.非正式组织要求成员___________的压力，往往也会束缚成员的个人发展。 (二)选择题 1．下列关于非正式组织不正确的说法是________________。 A.非正式组织主要以感情和融洽为主要的标准； B.正式组织与非正式组织是交叉混合的； C.非正式组织的危害要大于积极作用； D.非正式组织会发展组织的惰性。 2.下列关于委员会的说法中不正确的是_________________-。 A.委员会能够综合各种意见，提高决策的正确性； B.委员会一般只活跃于组织的中间层和较低管理层； C.委员会容易导致时间上的延误； D.日常事务管理不宜采用委员会的管理方式。 3.下列哪一种情况最不应该采取群体决策方式____________________。 A.确定长期投资于哪一种股票 B.决定一个重要副手的工作安排 C.选择某种新产品的上市时间 D.签署一项产品销售合同 4.如果你是一家公司的经理，当你发现公司中存在许多小团体时，你的态度是________。 A.立即宣布这些小团体为非法，予以取缔 B.深入调查，找出小团体的领导人，向他们发出警告，不要再搞小团体 C.只要小团体的存在不影响企业的正常运行，可以对其不闻不问，听之任之