（控制科学与工程专业论文）基于计算机视觉的室内定位算法研究.pdf

渊燃必 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签 关于论文使用授权的说明 ：上o l o 一箩2o 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 摘要 摘要 随着计算机技术、数字信号处理理论和视觉传感技术的发展，人们开始了基 于视觉的定位技术的研究。为实现高精度、不依靠外部设备的室内定位，本文在 对现有的室内定位技术进行了分析的基础之上，提出了基于计算机视觉的室内定 位算法，主要开展了以下几个方面的研究： l 、从整体上对基于序列图像块匹配的室内定位算法进行了阐述。首先介绍 了块匹配算法，以及块匹配算法所涉及的关键因素，如块匹配原理、匹配准则、 搜索策略、搜索范围。对序列图像块匹配的整体过程进行了系统的说明，描述了 从获取图像至得到两帧图像位移变化量的具体步骤。 2 、为了使基于序列图像块匹配的室内定位算法具有更好的性能，能够适应 更复杂的条件，本文对算法提出了三点改进，并通过实验验证了改进效果： ( 1 ) 把搜索块的面积增大，并且将其改为网格式搜索块，将搜索范围由原 来的前一帧中的( m + u 。2 ) ( n + v x 2 ) 扩展为前一帧整幅图像，使得匹配算法的 速度和准确度的综合性能得到了提升。 ( 2 ) 对块匹配计算加入了阈值校验，并且在出现异常的情况下对这两帧图 像进行归一化相位相关法匹配，极大地提高了算法的准确性。 ( 3 ) 针对两帧图像完成匹配后进入下两帧图像匹配计算的过程中如果发生 图像旋转则会出现异常的情况，进行了基于h a r r i s 角点检测的图像旋转测量， 并且在检测出旋转的情况下，进行旋转回复，从而使匹配计算继续进行。使算法 能够适应旋转的情况。 3 、在上位机中实现了基本的定位算法和改进的定位算法，并进行了实验分 析。设计了基于v c + + 的上位机算法研究平台，并且该平台提供了扩展接口，如 果有什么新的算法或新的功能，不用重新设计应用程序，可以直接添加在该平台 之中，极大的提高了科研效率。 4 、搭建了基于t m s 3 2 0 d m 6 4 2 的定位系统研究平台。应用c c s 集成开发环境 进行了软件设计，在硬件上实现了基本的基于序列图像块匹配的室内定位算法， 并通过实验展示了定位系统研究平台的整体效果。 关键词：视觉定位、序列图像、块匹配、归一化相位相关、h a r r i s 角点检测 北京t 业大学工学硕十学位论文 _ i i l _ a b s t r a c t _ _ _ 一i i i 一 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , d i g i t a ls i g n a lp r o c e s s i n gt h e o r y a n dv i s u a ls e n s i n gt e c h n o l o g y , p e o p l eb e g a nt h er e s e a r c ho fl o c a t i o nb a s e do nv i s i o n t oa c h i e v eh i g ha c c u r a c yr e s u l to fi n d o o rl o c a t i o nw i t h o u tr e l y i n go ne x t e r n a ld e v i c e s ， i nt h i sp a p e r , t h ec u r r e n tl o c a t i o nt e c h n o l o g i e sa r ea n a l y z e d ，a n di n d o o rl o c a t i o n a l g o r i t h mb a s e do nc o m p u t e rv i s i o ni sp r o p o s e d m a i n l yc a r r i e do u tt h ef o l l o w i n g a r e a so fs t u d y ： i e l a b o r a t et h ei n d o o rl o c a t i o na l g o r i t h mo nb l o c km a t c ho fi m a g es e q u e n c e f i r s t ，i n t r o d u c e dt h eb l o c k - m a t c h i n ga l g o r i t h m ，a n dt h ek e yf a c t o r so fb l o c k - m a t c h i g a l g o r i t h m ，s u c ha sb l o c k m a t c h i n gp r i n c i p l e ，m a t c h i n gc r i t e r i o n ，s e a r c hs t r a t e g ya n d s e a r c ha r e a s e c o n d ，e x p l a i n st h eo v e r a l lp r o c e s s e so fi m a g es e q u e n c em a t c h i n g ， d e s c r i b e st h es p e c i f i cs t e p sf r o mg e t t i n gi m a g es e q u e n c et og e t t i n gt h et w oi m a g e d i s p l a c e m e n tv a r i a t i o n ，a n dv e r i f yt h ev a l i d i t yo f t h ea l g o r i t h mb ye x p e r i m e n t 2 i no r d e rt om a k et h ei n d o o rl o c a t i o na l g o r i t h mo nb l o c km a c t ho fi m a g e s e q u e n c eg e tb e t t e rp e r f o r m a n c e ，b ea b l et oa d a p tt om o r ec o m p l e xc o n d i t i o n s ， p r o p o s et h r e ei m p r o v e m e n ta l g o r i t h m s ，a n dv e r i f yt h er e s u l to fi m p r o v e m e n tb y e x p e r i m e n t ： ( 1 ) i n c r e a s et h es i z eo ft h es e a r c hb l o c k ，r e p l a c e di tb yg r i d - t y p es e a r c hb l o c k , c h a n g et h es e a r c ha r e af r o mt h e ( m + u 一2 ) ( n + v 。；x 2 )o fp r e v i o u sf r a m et ot h e w h o l ei m a g eo fp r e v i o u sf r a m e ，a n dt h i sp r o m o t et h es p e e da n da c c u r a c yo ft h e i n t e g r a t e dp e r f o r m a n c eo ft h em a t c h i n ga l g o d t h m ( 2 ) j o i nt h eb l o c k - m a t c h i n ga l g o r i t h mb yt h r e s h o l dt e s t ，m a k en o r m a l i z e dp h a s e c o r r e l a t i o ni nt h ec a s eo fa b n o r m a lp h e n o m e n ao ft w of r a m e s ，a n di m p r o v et h e a c c u r a c yo f t h ea l g o r i t h mg r e a t l y ( 3 ) a f t e rt w of r a m ec o m p l e t i n gt h em a t c h ，a n dg oi n t ot h ep r o c e s so fn e x tt w o f r a m e ，m a y b et h ei m a g ew i l lh a v ear o t a t i o n , i nv i e wo ft h i ss i t u a t i o n , m a k et h e m e a s u r e m e n to fi m a g er o t a t i o nb a s e do nh a r r i sc o m e rd e t e c t i o n ，a n di nt h ec a s eo f d e t e c t i n gr o t a t i o n ，r e s u m ei t ，s ot h i sw i l lm a k et h eb l o c km a t c h i n ga l g o r i t h mg oo n t h i si m p r o v e m e n tm a k et h ea l g o r i t h ma d a p tt ot h es i t u a t i o no fr o t a t i o n 3 a c h i e v et h eb a s i ca n di m p r o v e di n d o o rl o c a t i o na l g o r i t h mi n t h eh o s t c o m p u t e r d e s i g nt h eh o s tc o m p u t e rp l a t f o r mo fa l g o r i t h mr e s e a r c h , a n dt h ep l a t f o r m p r o v i d e se x t e n d e di n t e r f a c e s ，i fh a v i n ga n yn e wa l g o r i t h mo rn e wf u n c t i o n a l i t y , w i t h o u tr e d e s i g n i n gt h ea p p l i c a t i o n , c a nb ea d d e dd i r e c t l yi n t ot h ep l a t f o r m ，a n d g r e a t l yi m p r o v e st h ee f f i c i e n c yo fs c i e n t i f i cr e s e a r c h 4 s t r u c t u r e st h er e s e a r c hp l a t f o r mo fl o c a t i o ns y s t e mb a s e do nt m s 3 2 0 d m 6 4 2 ， d e s i g nt h es o f t w a r eb yc c si n t e g r a t e dd e v e l o p m e n te n v i r o n m e n t a c h i e v et h ei n d o o r l o c a t i o na l g o r i t h mo nb l o c km a t c ho fi m a g es e q u e n c ei nt h eh a r d w a r e d e m o n s t r a t e i i i 北京工业火学t 学硕士学位论文 - l _ _ _ _ _ i _ l _ _ _ _ _ _ _ _ _ l _ _ _ _ _ l _ _ l _ i _ _ _ _ l l _ _ i _ i _ _ i _ - _ l _ _ _ _ l l l l l _ _ i - l l i l i _ t h eo v e r a l le f f e c to ft h er e s e a r c hp l a t f o r mo fl o c a t i o ns y s t e mb ye x p e r i m e n t k e y w o r d s ：v i s u a ll o c a t i o n ；i m a g es e q u e n c e ；b l o c km a t c h ； n o r m a l i z e dp h a s ec o r r e l a t i o n ；h a r r i sc o m e rd e t e c t i o n i v 目录 目录 摘要i a b s t r a c t 。iii 第1 章绪论1 1 1 课题的研究背景1 1 2 国内外研究现状1 1 3 课题的研究意义3 1 4 论文研究思路与内容安排4 第2 章基于序列图像块匹配的室内定位算法7 2 1 引言7 2 2 块匹配算法7 2 2 1 块匹配原理7 2 2 2 匹配准则7 2 2 3 搜索策略8 2 2 4 搜索范围一1 0 2 3 定位算法的基本过程1 l 2 4 本章小结1 2 第3 章室内定位算法中关键技术的研究13 3 1 引言1 3 3 2 搜索块及搜索范围的调整1 3 3 2 1 扩大搜索块的面积1 3 3 2 2 网格式搜索块1 4 3 2 3 搜索区域的扩展1 5 3 2 4 实验结果及分析一1 6 3 。3 归一化相位相关匹配1 7 3 3 1 归一化互相关法1 8 3 3 2 基于相位差的运动估计方法18 3 3 3 归一化相位相关法2 1 3 3 4 实验结果及分析2 6 3 4 序列图像的旋转测量与处理2 7 3 4 1 图像旋转对定位效果的影响。2 8 3 4 2 基于h a r r i s 角点检测的图像旋转测量3 0 3 4 3 基于立方卷积插值算法的旋转处理3 9 3 4 3 实验结果及分析4 5 3 5 本章小结4 7 第4 章基于v c + + 的室内定位算法实现4 9 4 1 引言4 9 4 2 改进的定位算法过程4 9 4 3 开发环境的介绍5 4 4 4 基于v c + + 的上位机算法研究平台5 4 4 4 1 算法研究平台主界面5 4 北京下业大学t 学硕十学位论文 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ii _ _ _ _ _ _ _ _ 一 4 4 2 两幅图像匹配模块5 4 4 4 3 基本定位算法模块5 5 4 4 4 改进的定位算法模块5 5 4 5 实验结果及分析5 5 4 6 本章小结5 8 第5 章基于t m s 3 2 0 d m 6 4 2 的室内定位算法实现5 9 5 1 引言5 9 5 2t m s 3 2 0 d m 6 4 2 介绍5 9 5 3 基于t m s 3 2 0 d m 6 4 2 的匹配算法软件设计5 9 5 3 1 集成开发环境c c s 5 9 5 3 2 软件设计。6 0 5 4 实验结果及分析6 2 5 4 1 实验结果6 2 5 4 2 实验分析6 4 5 5 本章小节6 4 结论及展望6 5 结论6 5 展望6 5 参考文献6 7 攻读硕士学位期间所发表的学术论文7 1 致谢7 3 - 、，i 第1 章绪论 1 1 课题的研究背景 第1 章绪论 近年来，随着科技的发展和社会的进步，社区信息化和数字化水平日益提高， 数据业务和多媒体业务快速增加，人们对定位与导航的需求日益增大，室内定位 系统的开发与设计也引起了人们的关注。尤其在复杂的室内环境，如楼宇内、机 场大厅、展厅、仓库、超市、图书馆、地下停车场、矿井等环境中，常常需要确 定移动人员在室内的准确位置，实现对人员调度管理、与位置相关的信息服务、 人身安全和紧急救助等。 室内定位和室外定位有很大不同。首先，室内空间受限，拐角和障碍物较多； 其次，两种定位系统的坐标体系和测量精度要求不同。对于室内定位系统而言， 最重要的是如何识别区域边界，确定用户在哪一个区域内，应能精确到哪个楼层 的哪个房间或更高的要求，精度一般要达到1 米以内；再次，用户在室内环境中 是可以随意移动的，而大多数的室外定位系统，如交通运输定位系统，用户往往 被局限于道路、航线内。所以，室内定位变得非常困难，g p s 等室外应用较好的 定位系统在室内难以得到满意的定位效果，表现在定位精度差，定位时间长，甚 至不能使用。 室内人员定位系统的理想模式是：定位装置不受室内环境影响，通用性和可 扩展性强；能够实现自主定位，不需要增加辅助设备，不需要事先对室内环境进 行改造和布置；定位装置具有体积小、重量轻、人员配置方便，价格低廉、耗电 小等特点；定位系统实时性好、定位准确、鲁棒性强等。 1 2 国内外研究现状 从2 0 世纪8 0 年代末期起，许多高校和研究机构开始了室内定位技术的研究， 研究主要集中在利用卫星、无线通信网络或超声波、红外线、激光、视觉等传感 器，根据三边测量法、三角测量法、最大似然估计定位法、模型匹配算法等特定 的算法来确定定位终端在某一时间所处的位置。具有代表性的定位系统有： ( 1 ) 同时基于卫星和移动通信网络的混合定位系统( a g p s ，g p s o n e ) 。 a g p s 是在g p s 通过卫星接受定位信号的基础上，同时结合移动运营商所提供的 网络机站的定位信息来进行辅助定位。其一方面由具有g p s 的手机获取来自卫星 的定位信息，另一方面也要靠该手机透过g p r s 网络下载辅助的定位信息，两者 相结合来完成定位。a g p s 在冷启动时无须再接收卫星信息资料，通过g p r s 便很 快得到了当前的星历和方位俯仰角等信息。室内定位精度为5 0 3 0 0 米，定位时 北京t 业大学丁学硕十学位论文 间较长，定位精度低。 ( 2 ) 射频识别( r f i d ) 定位系统，该系统包括读卡器( r e a d e r ) 、电子标签 ( t a g ) 、主机( h o s t ) 及数据库。当系统要进行物体识别工作时，主机通过有线或 无线方式下达控制命令给r e a d e r ，r e a d e r 接收到控制命令后，其内部的控制器 会通过r f 收发器发送出某一频率的无线电波能量，当t a g 内的天线感应到无线 电波能量时，会传回含有自身种类识别码标志、制造商标志的识别资料给r e a d e r ， 最后传回主机进行识别与管理乜1 。该系统用活性参考标签t a g 替代离线数据采集， 其动态参考信息能够实时捕捉环境变化，提高定位精度和可信度。活性参考标签 t a g 的应用免去了每个测试点数百次的人工数据采集，且能更好的适应室内环境 的波动，提高定位精度。由于依据信号强度进行定位，室内多经衰落对定位的影 响很大，需要建立室内模型和算法，室内环境的变化对定位精度影响很大。 ( 3 ) 基于超声波技术的麻省里工学院的c r i c k e t 系统和a t & t 研究所设计 开发b a t 定位系统，系统定位精度较高。超声波定位系统由若干个应答器和一个 主测距器组成，主测距器放置在被测物体上，在微机指令信号的作用下向位置固 定的应答器发射同频率的无线电信号，应答器在收到无线电信号后同时向主测距 器发射超声波信号，得到主测距器与各个应答器之间的距离。当同时有三个或三 个以上不在同一直线上的应答器做出回应时，可以根据相关计算确定出被测物体 所在的二维坐标系下的位置。c r i c k e tl o c a t i o ns u p p o r ts y s t e m 啼1 是目前成功 使用该项技术的定位系统。缺点：超声波受多径效应和非视距传播影响很大，同 时需要大量的底层硬件设施投资，成本较高，无法大面积推广。 ( 4 ) 基于蓝牙的b i p s 室内定位系统h 1 ，该技术是一种短距离低功耗的无线 传输技术，支持点到点的话音和数据业务。在室内安装适当的蓝牙局域网接入点， 把网络配置成基于多用户的基础网络连接模式，就可以获得用户的位置信息，实 现移用蓝牙技术定位的目的。采用该技术作室内短距离定位，容易发现设备，且 信号传输不受视距的影响，但定位半径为l o m ，设备发现时间大于5 1 2s ，不能 用于跟踪用户；而且蓝牙器件和设备的价格比较高，而且对于复杂的空间环境， 蓝牙系统的稳定性稍差，受噪声信号干扰大。 ( 5 ) 基于地面基站的以色列的i t u r a n 定位测控系统畸1 ，系统的动态定位精度 为5 3 0 米( n ，如图3 2 所示 北京t 业大学t 学硕十学位论文 图3 - 2 搜索块的大小由m n 变为m i n f i g 3 - 2t h e s i z eo fs e a r c hb l o c kb e c o m e si n t om l n f r o mm n 这样，在计算最小绝对差值的时候，就可以在更大的范围内进行比较，从而 获得更大的准确性。但这样做的话，就不可避免地多出了m x n 一m n 的计算 量，也就是说，搜索块的面积扩大的越多，计算量就越大。而这种情况是我们不 愿看到的，因此，要对其进行调整。 3 2 2 网格式搜索块 将搜索块的面积扩大，能够带来准确性的提高，但同时也带来了更多的计算 量。原始的搜索块与前一帧图像的参考块进行最小绝对差值计算时要对搜索块与 参考块的所有像素进行计算，很明显，这是很大的计算量。然而，根据现实中的 经验，并不需要对其所有的像素进行运算，而只需计算其中的一部分像素，就完 全可以达到理想的效果。故而，为了在提高准确性的同时，能够只牺牲较小的速 度，本文提出了一种网格式的搜索块，即在进行匹配的过程中，并不计算搜索块 与参考块内的所有像素，而只是每隔一个像素计算一次，或是每隔几个像素计算 一次。这样下来，该搜索块就成了类似于网格似的模板，故而，本文命名其为网 格式搜索模块。其示意图如图3 3 所示。 图3 3 网格式搜索模块示意图 f i g 3 - 3s c h e m a t i cd i a g r a mo f t h eg r i d - t y p es e a r c hm o d u l e 图3 _ 4 ( a ) 和( b ) 所示为搜索块的两个模板示例，从模板可以直观地看到，采用网格 式搜索块，减少了所需计算的像素点。 第3 章室内定位算法中关键技术的研究 ( a ) 模板1 ( b ) 模板2 图3 - 4 网格式搜索模板 f i g 3 - 4t h et e m p l a t eo fg r i d t y p es e a r c h 通过这个改进，可以使大小为m x n 的搜索块减少很大的计算量。例如， 采用模板1 ，可以减少1 2 的计算量；采用模板2 ，可以减少2 3 的计算量。 3 2 3 搜索区域的扩展 块匹配算法的搜索区域由搜索块的大小和最大位移矢量的来决定，设搜索块 的大小为m x n ，搜索块的最大位移矢量为( u 。，v 。) ，则搜索区域的大小为 ( m + u 。2 ) x ( n + v 。2 ) 。然而，该搜索区域的确定需要事先定义最大位移矢量 ( u 。，v 。) ，这对于室内定位算法所处的工作条件是不适合的，因为算法并不能 预知下一阶段运动速度。如果该最大位移矢量定义的太小，显然无法满足要求， 但是如果该最大位移矢量定义的太大，则又失去了意义。故而，在前面扩大搜索 块面积和调整搜索块形式的基础上，本文提出了新的搜索区域的确定方法，即将 搜索区域改为整幅图像。如图3 - 5 所示。 f m “ 气 j- 搜索块l 坠、 hf n z v ，。 l前一帧搜索区域i v 。 w 苗 磅 ( 0 ，0 ) x 图3 5 搜索区域的扩展 f i g 3 - 5t h ee x p a n s i o no fs e a r c hr e g i o n 3 2 4 实验结果及分析 本实验中所用的序列图像为实验室地面的图像，首先用高像素的摄像机拍下 地面的图像，上传到上位机中，然后以y = 0 ( x ：1 5 0 c m ) 为轨迹截取图像，如 图3 - 6 所示。每一帧图像的大小w h = 1 2 8 1 2 8 ，搜索块的大小为3 2 3 2 ，搜 索范围是前一帧整幅图像。 ( a )( b )( c )( d ) 图3 - 6 部分实验室地面序列图像 f i g 3 - 6t h es e q u e n c ei m a g eo f p a r to f l a b o r a t o r yg r o u n d 图3 7 为序列图像的实际移动轨迹，图3 。8 为经过搜索块及搜索范围的调整 后改进的定位算法处理序列图像所得的轨迹与实际轨迹的合成图。 实际轨迹合成团 剐啄轨憝 l 算法所得皂t 迹 f i g 3 - 7a c t u a lt r a j e c t o r yf i g 3 8c o m p o s i t i o ng r a p h 表3 1 部分算法所得轨迹部分坐标值 t a b l e 3 - 1t h ec o o r d i n a t e so f t r a j e c t o r yd e r i v e df r o mt h ea l g o r i t h m a 1 ( 0 ，0 )a 2 ( 2 8 0 2 ，0 )a 3 ( 5 3 8 1 ，0 )a 4 ( 8 0 7 1 ，0 ) a 5 ( 1 0 6 5 ，o )a 6 ( 1 3 5 6 ，0 )a 7 ( 1 6 1 4 ，o )a 8 ( 1 8 7 2 ，0 ) a 9 ( 2 1 3 0 ，o )a 1 0 ( 2 4 1 0 ，0 )a l l ( 2 6 7 9 ，0 1 1 2 1 )a 1 2 ( 2 9 2 6 ，。0 1 1 2 1 ) a 1 3 ( 3 1 8 3 ，0 1 1 2 1 )a 1 4 ( 3 4 5 2 ，0 1 1 2 1 )a 1 5 ( 3 7 2 2 ，0 11 2 1 )a 1 6 ( 3 9 7 9 ，。0 1 1 2 1 ) a 1 7 ( 4 2 4 8 ，0 1 1 2 1 )a 1 8 ( 4 4 9 5 ，0 1 1 2 1 )a 1 9 ( 4 7 5 3 2 ，o )a 2 0 ( 5 0 4 4 ，0 1 1 2 1 ) 经过搜索块及搜索范围的调整，算法所需计算的像素数不仅得到了降低，从 图中可以看出，准确性也依然很好，算法所得轨迹可以表示实际轨迹。这个实验 也很好的体现了基于序列图像块匹配的室内定位算法高精度的特点。 苫 佰 竹 0 0 占 佃 侣 sv竖制定再聪 ， 蛇 口 们 们 山3v兽剐足毒誊 第3 章室内定位算法中关键技术的研究 3 3 归一化相位相关匹配 块匹配法的基本思想是将每一帧图像分割成一系列互不重叠的子块图像，计 算当前帧中每一子块与前一帧中的各子块的误差函数，把具有最小误差的前一帧 的对应子块作为当前块的匹配块，并把由匹配块与当前块的相对位置计算得出的 运动位移定义为当前块的运动矢量。但是完全块匹配法无法检验两幅图像是否具 有同一个图像模块，即两幅图像具有平移关系，且相对运动较小，即使两幅毫无 关系的图像，根据匹配准则的计算，也会有最小绝对差。这样的话，如果相邻两 帧图像间发生某些不确定因素，就很有可能得出错误的结果。 图3 - 9 ( a ) 和( b ) 是本文采集的两种不同地面的图像，图3 1 0 ( a ) 和( b ) 是图3 - 9 ( a ) 和( b ) 的匹配结果。 ( a ) 图像1( b ) 图像2 图3 - 9 原始图像 f i g 3 - 9o r i g i n a li m a g e ( a ) 图像l 匹配块( b ) 图像2 搜索块 图3 1 0 匹配结果 f i g 3 - 1 0t h er e s u l t so f m a t c h 从图中可以看到，图像1 和图像2 是从两种地面采集来的毫无关系的图像，但 通过块匹配法仍然可以计算得到匹配结果，故而，对完成块匹配计算的相邻两帧 图像进行校验是非常必要的。 那么针对这个问题，就要在块匹配算法完成处理后，对其所处理的两幅图像 进行阈值校验，如果搜索块与匹配块的最小绝对差值的均方差小于等于该阈值， 即认为块匹配算法的结果正常，则进行下两幅图像的处理；如果最小绝对差值的 北京t 业大学t 学硕十学位论文 均方差大于该阈值，即认为块匹配算法的结果异常，则需要用其他的方法重新进 行处理。如互相关法、基于相位差的运动估计法、归一化相位相关法等。 3 3 1 归一化互相关法 归一化互相关算法是一种经典的匹配算法，经常 n c ( i ，) = n c ( i ，) = mn t ( m ，z ) s 7 ( 所，刀) m = ln = l ( 3 1 ) ( 丁( 所，刀) 一歹( 聊，刀) ) ( s ( 历，刀) 一i l 7m ，疗) ) ：! ! ；! i ! ! ：；：；：；：一 ( 3 2 ) m n ( 丁( m ，玎) 一于( 掰， ) ) 2 兰兰m ，行) 一m ，刀) ) 2( 丁( m ，玎) 一于( 掰， ) ) 2 s 。 ，行) 一否l 7 ，刀) ) 式中： 歹( m ) 2 志蚤善t ( 伽) 硝所，z ) 2 志萎酽锄，疗) 上式们( f ，歹) 的值越大说明搜索图上( f ，) 位置与模板越相似，当n c ( i ，) 值 为1 时，说明该位置即为匹配位置。在实际应用中，通常找不到n c 值为l 的位 置，此时，只需要在搜索图中找到具有最大n c 值的位置，则认为该位置为最佳 匹配位割3 2 1 。 但从本质上讲，归一化互相关法也是属于模板匹配法，与块匹配算法的根本 性区别不是很大，故而，如果某种因素使得块匹配算法失效，通常也会使归一化 互相关法失效3 3 1 。因此，在这种情况下，不适合用归一化互相关法对图像进行匹 配。 3 3 2 基于相位差的运动估计方法 传统的相位相关算法是利用频域的相位谱来计算时域的平移运动矢量的 3 4 1 。 但由于这种方法计算量很大，很难满足实时性的要求。在实验中发现无噪声干扰 的两幅在时域存在平移关系的图像，在频域相角差矩阵是线性的，所以考虑能否 利用线性的相角差矩阵来估计图像间的平移值【3 引。 如果图像中仅存在一个运动物体，图像大小为m x n ，用l ( x ，y ) 表示前一帧 图像，用石( x ，y ) 表示当前帧图像。若物体做刚体的平移，可以将石( x ，y ) 看做是 l ( x ，y ) 经过平移( 缸，缈) 得到的，即 第3 章室内定位算法中关键技术的研究 l ( x ，y ) = f o ( x a x ，y 一缈) ( 3 3 ) 只要能求出( a x ，a y ) ，就能求出物体的运动矢量。 令f o ( x ，少) 和石( x ，力的傅里叶变换分别为： e ( ”，v ) = f f o ( x ，y ) ( 3 - 4 ) 巧( “，力= f f ( x ，y ) ( 3 5 ) 2 嬲= e x p 一j 2 n ( u x m + v y ) 】= e ) ( p ( 锄( 3 - 6 ) 对于仅存在物体的平移而没有旋转时，可以用下述方法来检测平移运动： 矽( 甜，1 ，) = l f , ( u ，v ) 一么磊( 扰，1 ，) = - 2 7 r ( u a x + r a y ) ( 3 7 ) 由变量的可分离性，l x ( x ) 和石x ( x ) 分别表示f o ( x ，y ) ，石( x ，y ) 在x 轴上的 投影，即 五x ( x ) = l ( x ，y ) y 石x ( x ) = 彳( x ，y ) j ， 则相位差在x 方向的投影为 ( 3 - 8 ) ( 3 9 ) a c x ( u ) = 么e ) 一么f o ( ”) = - 2 x u a x ( 3 - 1 0 ) 所以x 方向的运动偏移量为a x = 一o x ( u ) 2 x u 。同理，可得y 方向的运动偏 移量为a y = 一a b y ( u ) 2 x v 。图像的相位差矩阵大小为mx n ，其时域与频域在坐 标转换上存在的数值关系为 z ，= x m ( 3 1 1 ) 1 ，= y n ( 3 - 1 2 ) 由此，利用最小二乘法，分别对两个方向的相位差分量做线性拟合，就能准 确地估计出平移矢量( a x ，a y ) 。其中相位差( “，1 ，) 在【万，7 】之间，由于傅里叶 变换具有周期性，使相位谱在二维平面的某些地方存在间断点或相位跳变，而且 具有正和负两个极性的可能。为了解决这个问题，将折叠相位值平移2 万，这样 就能得到连续的相位图，便于做线性估计。算法步骤如下： s t e p l ：分别求出两帧图像的傅里叶变换 s t e p 2 计算相位角之差 s t e p 3 ：将折叠相位值平移2 万展成连续相位分量 s t e p 4 ：分别对水平方向和垂直方向的相位差分量做线性拟合，分别估计出 两个方向的相角差分量的斜率值，该斜率值就代表了平移矢量值的大小和方向。 北京t q k 大学t 学硕十学位论文 图3 - 11 相位差运动估计方法流程图 f i g 3 11f l o wc h a r to f t h em e t h o do f m o t i o ne s t i m a t i o nb a s e d o np h a s ed i f f e r e n c e 但是基于相位差的运动估计方法只适用于目标单一，背景简单的情况，而如 果待处理的图像是类似于图3 1 2 之类的无具体目标，背景比较复杂的序列图像， 图3 1 2 部分楼道地面的序列图像 f i g 3 12t h es e q u e n c ei m a g e o fp a r to fc o r r i d o rg r o u n d 图3 一1 3 所示为序y 0i 茎t 像的实际移动轨迹，图3 1 4 所示为基于相角差得运动 估计法所得的轨迹，图3 1 5 所示为实际移动轨迹与基于相角差的运动估计法所 得轨迹的合成图。 第3 章室内定位算法中关键技术的研究 实际轨迹 051 01 5加葛 瑚( c m ) 图3 1 3 实际轨迹 f i g 3 - 1 3a c t u a lt r a j e c t o r y 瑚( c m ) 图3 1 4 基于相位差的运动估计法所得轨迹 f i g 3 - 1 5t h et r a j e c t o r yo fm o t i o ne s t i m a t i o n b a s e do np h a s ed i f f e r e n c e 音成田 基量扭位堇洼显嘏吼迹 产 安际 | 厂 暂么i 一：鳖i - 个 k、 y j n 二= ；7 。 o5 1 0 瑚2 ) 卫葛扣 图3 1 5 合成图 f i g 3 15c o m p o s i t i o ng r a p h 可以看到，在无具体目标，背景复杂的情况下，基于相位差的运动估计法就 无法正确表达出实际的轨迹，故而，此方法不适用于此种情况。 3 3 3 归一化相位相关法 在传统的匹配方法中，主要研究的是图像的空域特性【3 6 1 ，随着处理器处理能 力的提高，对数据的实时傅里叶变换已经成为可能，对图像处理已经由空域转换 到频域或二者的结合，频域下的图像处理可能解决在空域下很难解决的问题。 在对图像进行二维离散傅里叶变换后，主要的特征为幅频与相频【3 7 1 ，相位信 息包含了大量的图像特征信息，如果能够找出空域下的图像位置移动与频域下的 相位变化的对应关系，那么就可以根据频域的相位变化关系，计算出图像间的相 对运动矢量，这是频域运动估计方法的基本思路和依据。 1 、一维傅里叶变换及其反变换啪1 设厂( f ) 是一个连续时间信号，若厂( f ) 属于厶空间，即 ii r ( t ) l a f t l k 大学工学硕士学位论文 ( a ) 图像1 ( b ) 图像2 图3 3 5 原始图像 f i g 3 3 5o r i g i n a li m a g e ( a ) 图像l( b ) 图像2 图3 3 5 角点检测结果 f i g 3 - 3 5r e s u l to f c o r n e rd e t e c t i o n 图3 3 6 角点匹配示意图 f i g 3 3 6s c h e m a t i cd i a g r a mo fc o m e rm a t c h i n g 图3 3 7 斜率判断示意图 f i g 3 - 3 7s c h e m a t i cd i a g r a mo fs l o p ed e t e r m i n a t i o n 可以看到，算法分别在各自的图像中检测出了特征点，并用十字标出，这就 3 8 - 第3 章室内定位算法中关键技术的研究 为后续的工作提供了基础。在检测出了特征点之后，图3 3 6 显示了两幅图像经 过特征点的匹配，而得到的对应关系，并把对应的特征点用直线连接了起来( 在 此处只标记两对特征点) 。那么最后，把图像3 3 6 ( a ) 中的两个角点a 、b 连线， 同时求出斜率k 1 ，并把图像3 3 6 ( b ) 中相对应的两个角点a ，、b 连线，同时求 出斜率l ( 2 ，如图3 3 7 ，这样，通过比较k l 和l ( 2 的大小，就可以判断出两幅图 像是否发生了旋转。 在这部分的内容中，本文对基于h a r r i s 角点检测的图像旋转测量进行