运动摄像环境下的背景建模算法研究 数字电子技术等专业毕业设计 毕业论文.pdf

中 国 科 学 技 术 大 学 本本 科科 毕毕 业业 论论 文文 题题 目目 运动摄像环境下的背景建模 算法研究 英英 文文 Background Modeling for Moving Cameras 院院 系系 少年班院 姓姓 名名 廖琦宇 学 号 PB08000674 导导 师师 俞能海 教授 日日 期期 2012 年 6 月 中国科学技术大学本科毕业论文 致谢 光阴似箭 四年本科求学之路即将走到尽头 回望四年科大生涯 老师 同 学和亲友们给了我很多无私的帮助和鼓励 带给我许多快乐 对此 我心中充满 了感激之情 借此机会向所有帮助和支持我的人 送上衷心的谢意和祝福 首先 也是最应该感谢的人就是我的导师 俞能海教授 自保研开始 就常 听说俞老师处最好云云 直到加入了 M Core 这个温暖的大家庭 亲身体会到了 俞老师如师如父的教导 才知道此言不虚 俞老师不仅教授与我生存技能 更宝 贵的是其在举手言行间传递的科学精神和对国家强烈的责任感和使命感 俞老师 常言自己热爱老师这个职位 不才看来他的确称得上 老师 这个无上光荣的职 业 我将永远以俞老师为榜样 此外还应该感谢教导我四年的中国科学技术大学和光荣的少年班学院 在这 里我感受到了最严谨的科研环境和最快乐的大学时光 陈旸院长 班主任黄松筠 在不才四年生活中给与了最无私的帮助 科大的老师们则在学习中传授给我们成 长最需要的科学知识 不管以后走到哪里 我将永远是少院人 是科大人 感谢我的同学 朋友 沈翀 张磊 滕硕 邹牧龙等 感谢他们陪我一同走 过四年难忘的大学时光 点点滴滴都要保存在脑海里 以后不管在哪里 还见不 见得到都要记得这一段互相扶持的青葱岁月 还有女友杨子柳同学 相识九年 往往是在我最无助的时候帮助和鼓励我 谢谢你们 我还要感谢 M Core 大家庭中的兄弟姐妹 周维师兄和刘羽师兄在不才的毕 业设计中提供了很多思路 给与了极大帮助 我今天能顺利完成毕业论文 与他 们的帮助密不可分 此外 感谢实验室中的师兄尹华罡 蒋锴 王鹏 孟垂实 王晶晶 张兆卓 王雨农等 你们让我感受到了 M Core 积极向上的科研风气和 温馨快乐的学习氛围 父亲青年时在南京求学 发愤苦读 总算走出大山 飞出一片更广阔的天地 26 岁时 父母相遇于湘畔 2 年之后 不才呱呱坠地 母教之以细心慈爱 礼仪 道德 父授之以科学文化 宽广胸襟 虽然期间家道经历数次剧变 但父母的爱 从未曾改变一分一毫 这里要特别感谢我的母亲 父亲出差开始断断续续经数年 形单影只育我于陌市 父母含辛茹苦 每思及此 常自觉愧对生我养我之恩 历时将近半年时间终于将这篇论文写完 这薄薄一纸本科毕业设计论文 却 中国科学技术大学本科毕业论文 是凝结了本人四年以来在科大学习生活的点点滴滴 苦辣酸甜尽在其中 在本人 6 月 6 日答辩完毕合上毕业论文扉页之时 人生书卷最美好的一页也随之永久封 存 正如这篇毕业设计论文本身 所交答卷虽远不能称之为圆满 但只要用心拼 过 也并无甚可后悔之处 本毕业设计是不才用心而为 然本人学术水平有限 文字章节期间必然有错 漏及不合理之处 还望老师同学多加指正 廖琦宇 2012 年 6 月 4 日 于中国科学技术大学 网络版声名 网络版声名 衷心衷心感谢网络上感谢网络上老师师兄同学老师师兄同学牛人们牛人们提供的帮助 提供的帮助 没有你们本人无法没有你们本人无法如此如此顺顺 利利地地完成完成本科本科毕业论文毕业论文 谢谢 谢谢 本毕业设计本毕业设计创新创新部分部分内容内容属于属于中国科学技术大学中国科学技术大学 M M CoreCore 若对于若对于本本毕业设计毕业设计 在在原理及代码方面有疑问 可以原理及代码方面有疑问 可以随时随时联系本人 如果在计算机视觉联系本人 如果在计算机视觉领域领域有任何有任何 新思路或者新思路或者建议建议 也欢迎 也欢迎指教指教 通讯录如下 通讯录如下 姓名 廖琦宇姓名 廖琦宇 永久永久邮箱 邮箱 qiyuliao qiyuliao 中国科学技术大学本科毕业论文 1 目录 中文内容摘要 3 英文内容摘要 4 第一章 绪论 5 1 1 研究背景与研究现状 5 1 1 1 研究背景和意义 5 1 1 2 研究历史和现状 7 1 2 本文的组织结构 9 第二章 国内外相关研究 10 2 1 Particle Video 算法提取和匹配特征点 10 2 1 1 传递 11 2 1 2 关系 12 2 1 3 优化 13 2 1 4 剔除 16 2 1 5 加入新粒子 16 2 2 单向性变换 16 2 2 1 Homography 概念 16 2 2 2 求解 Homography 矩阵 17 2 2 3 使用 RANSAC 算法进行鲁棒估计 18 2 2 4 多层 Homography 提取 19 2 3 运动轨迹分析 20 2 3 1 背景轨迹的低秩性 20 2 3 2 基于 RANSAC 的运动轨迹分析 21 2 4 本章小结 23 第三章 基于矩阵重建的运动轨迹分析算法 24 3 1 基于低秩矩阵恢复的轨迹分析算法 25 3 2 基于低秩矩阵填充的轨迹填充算法 26 3 3 图像的像素级标定 27 3 3 1 图像超像素分割 28 中国科学技术大学本科毕业论文 2 3 3 2 基于超像素的背景建模 28 3 4 本章小结 30 第四章 实验过程及结果分析 31 4 1 数据来源及描述 31 4 2 特征点标定 32 4 3 像素级标定 37 4 4 实验过程分析 38 4 4 1 特征点提取 38 4 4 2 随机一致性算法的实现 39 4 4 3 超像素分割的实现 40 4 5 实验结果分析 41 4 5 1 特征点标定 41 4 5 2 像素级标定 43 4 6 本章小结 43 第五章 工作总结与展望 45 5 1 工作总结 45 5 2 未来研究展望 46 参考文献 47 中国科学技术大学本科毕业论文 3 摘要 随着监控手段的多样化 出现了越来越多的可移动摄像头 如车载设备 机 器人 手持设备 PTZ 摄像机等 研究移动场景下的运动目标提取算法显得非常 必要 当场景运动时 固定场景下的背景建模方法不再有效 而移动场景下的背 景建模远比固定场景要困难 这方面的研究工作也相对较少 近年才逐渐成为学 术界的一个研究热点 本文的工作主要基于卡内基梅隆大学的舍赫教授在 2009 年提出移动摄像机 适用的背景相减算法 在此基础上引入矩阵重建方法 进而提出一种基于超像素 和轨迹分析的运动目标检测算法 本论文的主要创新点在于 1 采用低秩矩阵重建进行运动轨迹分析 该方法比传统的 RANSAC 方法对 动态背景或者噪声的干扰更加鲁棒 2 提出了一种基于稀疏表达的短轨迹分析算法 先基于稀疏表达算法将一 些较短的截断轨迹进行补全 并根据最小化的结果对短轨迹进行分类 这样便 可获得更密集的轨迹点 特别是能在一定程度上填补目标前后方的空白区域 有 利于背景和前景建模 3 提出了基于超像素 super pixels 的背 前景模型 该模型以图像分割的 超像素为建模的基本单元 即继承了基于区域的方法对干扰的鲁棒性又较好的保 护了运动目标的轮廓 关键词关键词 移动摄像机 背景建模 轨迹分析 矩阵重建 中国科学技术大学本科毕业论文 4 Abstract With the diversification of means of monitoring there has been a growing number of mobile camera such as automotive equipment robots handheld devices and PTZ cameras mobile scenarios moving target extraction algorithm is becoming more and more necessary When the camera moves background modeling method under the fixed camera is no longer valid Background modeling of mobile camera more difficult than a fixed one researches in this area is relatively less only in recent years has gradually become a hot research topic of the academic community This work is mainly based on work done by Professor Y Sheikh Carnegie Mellon University in 2009 using background subtraction algorithm We use matrix reconstruction method and then put forward a new super pixels analysis and moving targets detection algorithm The main innovation of this paper is 1 Low rank matrix reconstruction trajectory analysis This method is more robust than the traditional RANSAC algorithm under a dynamic background or noise interference 2 Short track analysis algorithms based on sparse expression Algorithms minimize the results of the classification of short track This allows more feature points available for analysis especially fit for situations that a certain blank areas appears on the target 3 back foreground modeling based on the super pixel super pixels This algorithms inherits a region based approach on interference robustness while protects of the outline of a moving target better Key words Mobile camera Background modeling Trajectory analyzing Matrix reconstruction 中国科学技术大学本科毕业论文 5 第一章 绪论 1 1 研究背景与研究现状 1 1 1 研究背景和意义 计算机视觉 作为近 20 年从出生到发展的一门新兴学科 在包括从军用到 民用的诸多领域都有着卓越的贡献和长足的发展潜力 它是一门研究如何使机器 看 的科学 更进一步的说 就是指用摄影机和电脑代替人眼对目标进行识别 跟踪和测量等行为 并进一步做图像处理 用电脑处理成为更适合人眼观察或传 送给仪器检测的图像 考虑到人类已经进入信息时代 计算机将越来越广泛地进 入几乎所有领域 一方面是更多未经计算机专业训练的人也需要应用计算机 而 另一方面是计算机的功能越来越强 使用方法越来越复杂 从另一个方面讲 它 同样可以被看作是生物视觉的一个补充 在生物视觉领域中 人类和各种动物的 视觉都得到了研究 从而建立了这些视觉系统感知信息过程中所使用的物理模型 另一方面 在计算机视觉中 靠软件和硬件实现的人工智能系统得到了研究与描 述 生物视觉与计算机视觉进行的学科间交流为彼此都带来了巨大价值 智能计算机的其中一项要求 就是能够使得计算机能够像人类一样 理解周 围的信息 包括视觉信息 声音信息 还有温度信息等 计算机视觉 脱胎于传 统图像处理 更着重于解决计算机如何学习人类的思考和理解模式 将视觉信息 瞬间的视觉图像 也可以是一系列的图像序列 转化为有意义的 较为简化的 数字信息 因为能够将人从繁重并且重复的工作中解脱出来而去从事更有创造 性的工作 计算机视觉于是有着它广阔的应用前景 视频监控和追踪从计算机视觉的应用诞生的年代起 就一直是热门的应用领 域 随着城市以及各种场所对安全等要求的逐渐提高 越来越多的人力和物力被 投入到视频监控项目的开发和运作当中 视频监控是安全防范系统的重要组成部 分 它是一种防范能力较强的综合系统 视频监控以其直观 准确 及时和信息 内容丰富而广泛应用于许多场合 近年来 随着计算机 网络以及图像处理 传 中国科学技术大学本科毕业论文 6 输技术的飞速发展 视频监控技术也有了长足的发展 我国的 天网 计划就是 一个明证 视频监控系统的发展大致经历了三个阶段 在90年代初以前 主要是以模拟 设备为主的闭路电视监控系统 称为第一代模拟监控系统 90年代中期 随着计 算机处理能力的提高和视频技术的发展 人们利用计算机的高速数据处理能力进 行视频的采集和处理 利用显示器的高分辨率实现图像的多画面显示 从而大大 提高了图像质量 这种基于PC机的多媒体主控台系统称为第二代数字化本地视频 监控系统 九十年代末 随着网络带宽 计算机处理能力和存储容量的快速提高 以及各种实用视频处理技术的出现 视频监控步入了全数字化的网络时代 称为 第三代远程视频监控系统 第三代视频监控系统以网络为依托 以数字视频的压 缩 传输 存储和播放为核心 以智能实用的图像分析为特色 引发了视频监控 行业的技术革命 然而 视频监控还是处于需要大量人力投入其中 究其原因 就是计算机对 于视频的理解还不能达到人类大脑的水平 物体的辨识 提取 人物的动作识别 等等问题 在当今的计算机视觉领域仍然是个热点 随着计算机视觉算法的不断 完善 视频监控所需要的人力将会大大减少 从而显著地降低成本 这也是民用 计算机视觉的市场价值所在 在视频监控应用当中 如何提取目标物体是很重要的研究方向 比如在路口 的交通监控当中 如何自动地提取车辆和行人 传统上 这样的算法都借助比对 相邻的两帧来实现 这样做的原因是传统上大多数摄像装置都是固定安装在一个 固定的位置上的 比如路口的电线杆上 楼层的墙角落里 或者 有些可以旋转 的摄像头 在短时间内可以看作是静止的 也就是说 摄像头所拍摄的场景相对 于摄像头本身是不运动的 这样一个假设所带来的效果是在短时间内如果不出现 我们感兴趣的物体 如运动着的车辆和行人 的话 摄像装置所拍摄的视频应该 是相同的 如果相邻两帧或几帧出现了较大的不同 那么很可能的原因就是出现 了运动着的物体 而这个物体很可能就是视频监控中感兴趣的前景物体 然而 随着全球技术和经济的不断发展 便捷随身的通讯设备逐渐进入了生 活的主流 手机的拍摄装置和不断便捷的摄像装置的发展也是一日千里 由移动 设备拍摄的视频信息的数量已经远远超过了不容忽视的程度 如何在移动设备所 拍摄的视频中应用已有的各种监控算法 也成为一个必须要解决的问题 所以本 中国科学技术大学本科毕业论文 7 论文将集中讨论如何在移动相机所拍摄的视频中进行前景物体的提取 移动相机所拍摄的视频与传统的视频最大的不同就是 在移动相机所拍摄的 视频当中 由于相机本身是运动的 那么背景相对于相机也是运动的 这样一来 通过比对相邻两帧的差别来辨别前景物体的方法将不再适用 本论文的目的就是 探讨一种能够在前景和背景都在变化的情况下能将两者较为完美的区分并且分 割出来的算法并且予以实现 1 1 2 研究历史和现状 移动视频当中的目标提取在目前的应用当中 很大一部分是依靠传感器的精 确性来实现的 光电传感器通过被安装在多种移动平台上用于执行安全及监察任 务 如安装用于执行警务的巡逻直升机上 监视边界及更为普遍的探测可能的动 态场景变化 在不同的监察和监视任务中使用无人驾驶和其他机上平台 成像传 感器同样被应用于多种地面运动车辆上 但是无论怎样 即使是固定平台也总不 是防震的 如支架摇摆等 在这些情况下 保证足够的精度及可靠性来探测场景的动态对人工的操作员 们是一项巨大的挑战 运动目标很快被漏掉 且已探测到的目标很容易丢失 更 具挑战性的由传感器运动 运动的传感器平台以及光学参数变化导致的动态性问 题也需待解决 因此 很有必要为操作人员提供必需的功能性支持 现有系统的 能力到目前为止都具有相当的局限性 其需要关于飞行及记录参数的高精度数据 待观测的背景信息等 否则就只能对相对运动做出粗略的评估 与硬件方法不同 视觉的算法虽然精度有所下降 但是更具有鲁棒性 理解场景中发生的事件是计算机视觉的一项基本目标 为了实现这个目标 首先需要获得前景物体的信息 其次才能去识别该前景物体以及理解与之相关的 事件 诸如识别人 车辆以及人的行为 在实现以上这些高层目标之前 必须面临 的问题是如何把前景物体从背景中分割出来 显然 如何建立一个稳定的背景模 型和如何判断图像中哪些区域是前景是一项非常基础的工作 传统的背景建模方法来自于对每个像素点建立一个混合高斯模型进行描述 如文献 1 3 建立起了较好的背景模型 但他们是建立在当前帧的背景像素点 能在下一帧中相同位置上找到对应 因此 在背景本身有一定扰动的情况下 该假 设显然不成立 如无法适用于波纹 微风 光照变化 阴影等情况 中国科学技术大学本科毕业论文 8 M ittal等人针对动态背景 建立了一个自适应核的密度估计模型来处理动态 背景差分问题 4 可以很好地处理复杂背景 但是其运算代价是十分庞大的 对 此 Tian 等人在处理动态背景的同时 采用了一些方法减少计算代价 5 使用对应 位置上像素点领域的梯度相似性来处理光照变化问题以及用光强的协方差来处 理阴影问题 以上这些方法都是建立在假设摄像机固定情况下的 在运动场景下 背景建 模问题远比固定场景中困难 其根本原因在于由于摄像头自由运动所导致的像素 点失配问题 以上列举的大多数算法都假设摄像头及场景是固定的 但是随着移 动监控的应用越来越多 这方面的研究也越来越多 不论算法的模型怎样 运动 场景下背景建模的首要任务是确定相邻帧之间部分或者全部像素点的对应关系 然后利用这些点的像素值或者运动轨迹进行建模 一些方法是基于运动补偿的 如 6 先寻找一些特征点的轨迹 然后利用仿射 相机模型 affine camera model 下通过几何约束找到背景点的轨迹构造全景图 Rao 等人利用 Homography 变换来建立相邻帧像素点见的映射关系 从而建立全 景图 7 进一步的 8 10 利用多层 Homography 变换来处理深度背景 文献 11 先建立背景和前景的外观模型 appearance model 利用置信度传播算法 Belief Propagation 来进行运动估计 根据估计的运动信息在相邻帧之间进行外观模型 转换 有些方法则是基于运动分析的 通过估计占支配地位的背景运动来将运动 不一致的前景趋于检测出来 9 将基于运动分析的方法和外观模型结合起来 先 通过运动分析确定一些点的类别 然后用这些点进行贝叶斯建模 还有的方法是 通过重建 3 维场景进行背景剪除 如 12 提出了一种利用多视角拍摄的视频来重 建 3D 场景 进而进行背景剪除的方法 针对繁多的背景建模方法 一些学者进行了总结和评价 如 13 14 15 16 17 等 总的来说 这些算法各有优劣 其中一些算法能较好的处理动态背景问题 实际应用场景复杂多样 目前仍没有一种能很好的解决2 1节中各种问题的方法 本论文所实现的算法 基本思想来自于舍赫教授在 2009 年发表的论文 9 不存在任何的类似于上述的假设 纯粹是根据图像中的跟踪点轨迹 通过仿射矩 阵的秩约束来对图像的像素进行粗分类 然后才是像素级别的细分类 这个方法 将完全使用于手持移动摄像装置的应用范畴 如果追踪点足够多而且足够准确的 话 本论文实现的方法的效果将会是极为精确的 中国科学技术大学本科毕业论文 9 1 2 本文的组织结构 本文前半部分主要分别介绍了背景建模的轨迹分析和单向性变换方法 以及 提取背景模型的一整套实现过程 后半部分主要关注已得到轨迹的处理方法 针 对原有 RANSAC 方法的弊端 本文结合矩阵重建相关知识 提出了一种新的轨 迹处理方法并实验验证其有效性 为以后后续的有关移动相机视频处理的应用和 讨论提供支持和话题 本文总共由五章组成 第一章对移动摄像机环境下背景建模的技术进行了大概介绍 同时也简单说 明了本文的研究背景 意义和课题的发展情况 第二章介绍了现有的相关技术和研究工作 分别分析说明特征点提取 单向 性变换及轨迹分析的已有算法和性能优劣 第三章中 作者针对现有技术的一些问题 结合矩阵重建等数学工具提出了 自己的解决方法 同时提出一种新的前景分割 第四章通过实验 分析本文中几种算法的性能优劣 验证本文提出算法在处 理特定场景下背景建模问题的有效性 第五章对本文进行全面的总结 对未来工作做出展望 中国科学技术大学本科毕业论文 10 第二章 国内外相关研究 在本章中 我们将主要介绍在移动环境下建立背景模型的各个环节的成 熟算法 包括特征点提取与匹配 变换算法和轨迹分析算法 图 2 1 背景建模与前景提取的流程 2 1 Particle Video 算法提取和匹配特征点 在运动视觉离散分析中 从相邻时刻的图像中抽取特征点并建立起对应是非 常重要的先期步骤 只有建立起正确的点特征匹配 才能由这些匹配有效地计算 出物体的结构和运动 特征点匹配问题描述为 分别提取连续N帧图像中具有不 变性质的特征点 构成N个点集 如何建立它们之间的匹配 对此问题存在不少成熟的算法 SIFT算法 18 是一种提取图像局部特征 用 于表达整幅图像的方法 其目的是在尺度空间寻找极值点 提取特征点位置 尺 度及旋转不变量 由Harris等人于1988年中提出的Harris角点检测算子方法 19 则是基于图像局部自矫正函数的 该自矫正函数衡量某个像素点在各个方向上微 小偏移所造成的局部范围内的像素变化 简单而言 Harris算子是寻找两个正交 方向上的剃度变化较大的点 经实验验证 这些方法是可行有效的 我们使用的算法为粒子视频算法 Particle Video 20 该算法通过向前 和向后移动整个视频帧窗口 使得难以探测的闭塞边缘成为便于解析的不闭塞边 缘 然后同时向两个方向扩展新的粒子 在本文中即特征点 对于每一帧 算法执行以下步骤 1 传播 根据正反向的流场 将粒子从相邻帧延展到当前帧 2 关系 更新粒子关系 特征点提取 与匹配 特征点运动 分析 像素级标定 和前景提取 中国科学技术大学本科毕业论文 11 3 优化 优化粒子在当前帧中的位置 4 剔除 剔除优化后和原粒子误差超过阈值的粒子 5 加入 在已有粒子空隙处添加新粒子 图 2 2 每个图都表示一对连续帧 算法根据流场将一帧中的粒子 黑色点 传递到下一帧 同时将流场闭塞范围内的粒子 蓝色点 排除 下一步 算法对 扩张后的粒子添加关系 据此优化所有粒子的位置并排除误差严重的粒子 最后 算法在已有粒子空隙处添加新的粒子 2 1 1 传递 根据帧间光流场 21 算法将所有在特定帧内已经定义过 但在相邻帧尚 未定义的粒子传递到对应帧 为了描述粒子 i 在第 t 1 帧到第 t 帧的传递过程 我们使用光流场u x y t 1 1 u 1 1 t 1 1 1 1 t 1 2 1 向后 从第 t 1 帧到第 t 帧 的传递与此类似 如果粒子的光流场闭塞 则不传递该粒子 中国科学技术大学本科毕业论文 12 2 1 2 关系 算法通过 Delaunay 三角剖分方法 21 建立粒子的关系 在任意给定帧中 如果相应三角形的边在此帧或相邻帧中存在 则算法创建关系 这样可以减少关 系变化的可能性 同时允许粒子创建和消失时关系随之创建和消失 视频帧 传播图 粒子传递 中国科学技术大学本科毕业论文 13 图 2 3 更新粒子关系 图 2 2 对每一帧的四步算法 算法首先根据流场生成一个决定粒子放置点的传 播图 然后给传播的粒子更新关系 左边是对特定帧的全局图 右边是细节图 同时 算法根据每个关系粒子的轨迹差异给对应关系赋权值 如果粒子拥有 相似的轨迹 则有较大可能出自同一视觉层次 关系应该较强 反之如果粒子被 闭塞边界分隔开 则权值应该为零或接近零 按此思想算法计算第T帧中粒子I 和 粒子 j 的运动均方误差 D i j 1 2 2 2 2 其中 t 1 t 1 权值定义 为 2 3 2 1 3 优化 粒子视频算法的核心步骤 就是将相邻帧中传递的粒子位置优化的过程 其目的是为了减少粒子在光流传播中的长程漂移 对象则是当前帧中所有非新生 成的粒子 1 粒子目标函数 算法根据一个最小化目标函数来重新定位粒子 这个目标函数包括两部 分 数据部分和畸变部分 这个目标函数与上个部分中描述的流场函数有一 些相似处 但它的目标仅局限于粒子本身 而不包括全局因素 我们定义第 t 帧中粒子 i 的能量为 中国科学技术大学本科毕业论文 14 E i t 2 4 其中 表示粒子的不同颜色通道分量 表示 t 帧中与粒子 I 关联 的一系列粒子 给定一系列粒子 P 和一系列帧 F 则完整的目标函数确定 为 E i 2 5 2 数据能量 数据部分的能量决定了粒子表征在空间上的匹配程度 我们允许粒子表 征随环境缓慢变化 对于 t 时刻的粒子 I 定义其第 k 个颜色通道的表征为 2 6 用高斯核 5 对这些表征值在时间轴上滤波 产生一个在时间轴 上缓慢变化的表征 对给定的一帧 数据能量由观察表征和滤波表征 之间的差异给出 2 2 7 其中 是一个鲁棒规范 此处虽然假定对象表征在短时间内是平滑的 但没有保证对运动也平滑 所以数据能量容许表征缓慢变化 但不要求粒子 拥有平滑的运动轨迹 3 畸变能量 数据部分本身并不能唯一确定粒子的位置 一个畸变部分的能量可以在 空间上传递数据方面的约束 从而共同地优化粒子的位置 如果两个关系粒 子向不同的方向移动 则它们倾向于拥有较大的畸变能量 反之移动方向趋 同的粒子倾向较小的畸变能量 畸变能量由一对关系粒子 I 和 j 进行定义 我们让 1 同时 1 考虑到运动差异越大畸变能量越 大 定义 2 2 2 8 明显畸变能量具有对称性 由于关系权 值 参与度量 算法可以排除关系穿过闭塞边界情况的影响 进而支持运动 中国科学技术大学本科毕业论文 15 的粒子群在当前帧继续按照原来的模式运动 与数据能量一样 粒子的畸变 能量不要求运动轨迹平滑 介于畸变能量表征粒子的相对运动 所以粒子群 的全局运动也不需要平滑 值得一提的是 畸变能量不能太强 因为这样可能会排除掉一些正确的 运动模式 比如说由视角变化或不规则形变导致的粒子运动 算法运行时 需要对因子 做一些必要的调整 4 建立一个稀疏的线性系统 有了目标函数E后 我们用d 代替 求偏微分后 我们 得到方程组 d 0 d 0 t F 2 9 解得的d 和d 加入原 值 就可以得到初步优化的位 置 5 派生数据 对图像做线性化 d d d 2 2 2 10 线性化只在优化循环内部进行 算法只对未线性化目标函数进行优化 6 派生畸变 对于畸变 我们用 代替 1 同时 代替 1 这样我们有了下面的偏导 d 2 t d d 2 11 定义 d d 2 d d 2 2 12 变量 在时间 t 和时间 t 1 中的粒子 j 的能量中也出现 而且这些 派生是相等的 所以我们可以在畸变派生中加入关系粒子对的因素 中国科学技术大学本科毕业论文 16 2 1 4 剔除 优化粒子位置之后 仍然存在具有高能量值的粒子 这些粒子或严重形变 或与原粒子产生了大的表征差异 需要予以剔除 我们已经定义能量E i t 表示粒子 I 在时刻 t 的目标函数值 为减小单独坏 帧造成的影响 我们用高斯函数 t 1 对每个粒子的能量值进行滤波 如果一 帧中滤波后的能量值大于阈值 5 则剔除对应粒子 2 1 5 加入新粒子 在优化和提出进行完毕后 算法需要在原有粒子间加入新的粒子 为了适应 复杂运动 我们希望在视觉复杂度高的区域加入更多的粒子 使得其密度增大 对视频运行该算法 对于提取出的粒子及其轨迹 我们期待对其进行进一步 处理 2 2 单向性变换 在本节中 我们将主要介绍清华大学金俣欣教授在 2008 年做的工作 8 该 论文将场景看作由多个平面所组成 使用 RANSAC 方法找到场景中不同的平面 即多层 Homography 每个像素点肯定在某个平面上 通过所属平面相应的 Homography 变换 就能使相邻两帧重叠视野中的像素点进行匹配 这样就能对 场景进行背景建模 2 2 1 Homography 概念 Homography 是一种空间中某平面在两个不同的视角下成像之间的投影变 换关系 图 2 4 给定空间 中某平 面上的一 组点 1 这里使用齐次坐标 空间的点被表示为 4 维向量 平面 上的点为 3 维向量 1 它们投影在第 1 视角的成像平面 1 上的镜像为 1 以及投影在第2视角的成像平面 2 上的镜像 2 之间通过某个 中国科学技术大学本科毕业论文 17 Homography矩阵 H 3 3 的矩阵 构成投影变换 1 2 因此 1 和 2 为 相等的齐次坐标 即两者的差积为 0 即 2 1 0 图 2 4 单向性变换示意图 2 2 2 求解 Homography 矩阵 计矩阵 H 的第 j 行的行向量为h 有 1 h1 1 h2 1 h 1 2 13 将上式展开 并由h 1 1 h 可得 2 1 2 1 h 2 1 h2 2 1 h1 2 1 h 2 1 h2 2 1 h1 0 2 14 改写为 0 2 1 2 1 2 1 0 2 1 2 1 2 1 0 1 2 0 中国科学技术大学本科毕业论文 18 1 2 H 1 2 4 5 6 7 8 9 2 15 这实际上是一个有 9 个未知数构成的线性方程组 而这 9 个未知数就是 H 的 元素 实际上 这里的方程组中需要注意 有一个方程是可由另外两个线性组合得 到的 所以 一组对应点只提供了两个方程组 记 0 2 1 2 1 2 1 0 2 1 1 2 0 2 16 其中 为一个 2 9 的系数矩阵 是由第i 组对应建立起来的方程 虽然 H 有 9 个参数 但因为在齐次坐标系下 尺度是可以任意的 实际上只有 8 个未知参 数需要求解 并限定 h 1 因此 为了求解 8 个未知参数的唯一解 至少需要 8 组线性无关的方程 这就意味着必须要存在4组精确的对应点 且每3个都不是共 线的 才能得到唯一解 但在实际情况中 找到的可能的对应点必定存在一些偏差 这种偏差可能来 自匹配算法的不精确 也可能来自像素本身的不精确 因为图像中像素坐标都是 离散的整数 而真实的坐标应该是连续的实数 所以需要更多的点来减少这种偏 差 当方程组数量超过未知数的数量时就成为了一个超定问题 并且很可能由于 偏差而导致方程组中出现矛盾方程 因此 就需要通过最小二乘法来求解超定方 程组 由n组对应点组成的系数矩阵 目标是最小化 h 最小值所对应的h就是 所求解 即求解特征方程 的最小特征根所对应的解向量 2 2 3 使用 RANSAC 算法进行鲁棒估计 前面已经介绍了在找到对应点的情况下求解该组对应点所在平面的 Homography变换 现在需要求解一个最能符合已匹配特征点的Hmography变换 最容易的做法就是直接使用这组特征点的坐标建立一个超定方程组 然后对其求 最小二乘解 但存在两个问题 一是对应的特征点未必在同一个平面上 这样显 然会得到一个非常不精确的最小二乘解 另一个是寻找对应点的方法不能保证找 到的对应点是真实的对应点 如果存在一些匹配错误的特征点 可能对求解方程 组造成毁灭性的影响 所以 我们需要更鲁棒的估计 而这种估计方法能够识别 中国科学技术大学本科毕业论文 19 出不符合所求解的对应点 可将这类点称为外点 相对的符合所求解的对应点称 为内点 的方法 22 可以解决这个问题 给定特征点及潜在的对应关系 后 使用 求解Homography变换的具体算法步骤如图 2 5 算法 2 1 基于 RANSAC 的 Homography 提取算法 1 使用 鲁棒估计 迭代 次 由人工指定 重复做 机采 4 组不退化的对应点作为样本 计算Hmography变换H 退化情况 为 4 组点中只要存在 3 组在同一直线上 每一组对应点计算距离 这里H 1为的H 逆变换 符合当前H 的对应点 它们的距离应该小于某个阈值d thr ho d 这样 即为内点 当前内点数量足够多的时候 退出循环进入步骤 2 否则返回步骤 1 2 对得到的内点做一次最小二乘法求解最终的H 图 2 5 2 2 4 多层 Homography 提取 实际上 多层的Homography算法是基于一个非常简单的思想 特征点大多 数都匹配正确 而这些匹配正确的点根据所处的层次都能服从各层次的 Homography变换 找到一个能令最多的对应点服从的Homography变换后 将 这些点从对应点中去除 并将它们的层标记为 1 随后在剩余的对应点中继续寻 找最优的Homography变换 将符合这个变换的点标记为 2 并去除 依此类推 算法描述如图 2 6 算法 2 2 基于 RANSAC 的多层 Homography 提取算法 1 初始化当前剩余的对应点集 1 2 1 2 1 2 计算当前最佳的Homography 迭代m次 1 使用 算法计算当前最佳的 中国科学技术大学本科毕业论文 20 2 找到当前的内点集 1 2 1 2 3 去处这些内点得到更新后的当前剩余对应点集 1 2 1 1 1 2 1 2 如果剩余对应点集中点数不足某个阈值p th r ho d 则中止算法 否则迭代 图 2 6 2 3 运动轨迹分析 本节主要将注意力集中在舍赫教授在 2009 年的工作上 文章 9 介绍了 一种基于 RANSAC 的轨迹分析算法 实验证明 这种分析方法是确实有效的 对 于很多干扰因素也保留着良好的鲁棒性 2 3 1 背景轨迹的低秩性 本小节介绍的内容基于这样一个经验认识 即背景点的运动轨迹趋于一致 而属于运动目标的点的运动轨迹会与背景点的轨迹差异明显 如图 3 1 所示 图像中的运动信息是由摄像机的运动 物体的自由运动以及场景的 3 维结构 共同决定的 对于背景建模问题 我们需要的是将由摄像机运动和物体的自由运 动导致的运动信息区分出来 用一个矩阵来描述一个时间窗 连续的 F 帧 内 P 个特征点的运动轨迹 2 1 2 1 1 1 1 1 1 1 1 2 17 矩阵中的每一列 1 2 1 1 表示一条运动 轨迹 而 表示特征点 在第 f 帧中的所处的位置 在理想情况下 场景中仅存在静态背景 背景物体无自由运动 且没有噪声 干扰时 所有点都拥有固定不变的三维空间坐标 按照正交投影原理 23 中国科学技术大学本科毕业论文 21 是点i在的3维坐标 通过正交投影矩阵 向成像面的投 影 即有 1 2 4 5 6 2 18 如此一来 2 可以分解为一个2F 的投影矩阵和一个 的空间坐 标矩阵 即 2 1 1 2 1 1 4 1 5 1 6 1 1 2 4 5 6 1 1 1 2 19 根据式 2 19 可知矩阵 2 的秩最大应为 3 即背景点的运动轨迹向量 可以由 3 个基向量线性组合而成 1 2 20 图 2 7 a 为基轨迹向量 b 为背景轨迹 可见较为一致 秩较低 c 为前景轨迹 秩很大 2 3 2 基于 RANSAC 的运动轨迹分析 在以上章节探讨过了 如果所有的追踪点轨迹构成的矩阵W符合秩约束为三 的限制和制约 那么这些追踪点理论上都是属于背景的 因为它们所有的运动都 是一致的 是由相机运动引入的 中国科学技术大学本科毕业论文 22 分辨两种不同的轨迹的关键在于是否能够挑选出三个足够有代表性的轨迹 基 使得所有的背景轨迹能够用这三个轨迹基线性表示 事实上 由于有移动的物体 所以不可能所有的追踪点轨迹都符合上述的约 束 一些位于移动的物体上的追踪点上的轨迹由于涵盖了上述两种的运动引入方 式 所以无法由三个在背景上的基轨迹来线性表示 是 Random Sample Consensus 随机抽样一致 的缩写 它可以 从一组包含 局外点 的观测数据集中 通过迭代方式估计数学模型的参数 它 是一种不确定的算法 它有一定的概率得出一个合理的结果 为了提高概率必 须提高迭代次数 该算法最早由Fi ch r 和Bo 于 1981 年提出 的基 本假设是 1 数据由 局内点 组成 例如 数据的分布可以用一些模型参数 来解释 2 局外点 是不能适应该模型的数据 3 除此之外的数据属于噪 声 局外点产生的原因有 噪声的极值 错误的测量方法 对数据的错误假设 也做了以下假设 给定一组 通常很小的 局内点 存在一个可以估计 模型参数的过程 而该模型能够解释或者适用于局内点 算法的输入是一组观测数据 一个可以解释或者适应于观测数据的 参数化模型 一些可信的参数 通过反复选择数据中的一组随机子集来 达成目标 被选取的子集被假设为局内点 并用下述方法进行验证 1 有一个模型适应于假设的局内点 即所有的未知参数都能从假设的局内 点计算得出 2 用 1 中得到的模型去测试所有的其它数据 如果某个点适用于估计的模 型 认为它也是局内点 3 如果有足够多的点被归类为假设的局内点 那么估计的模型就足够合理 4 然后 用所有假设的局内点去重新估计模型 因为它仅仅被初始的假设 局内点估计过 5 最后 通过估计局内点与模型的错误率来评估模型 这个过程被重复执行固定的次数 每次产生的模型要么因为局内点太少而被 舍弃 要么因为比现有的模型更好而被选用 错误函数如下 W W 1 f W 2 2 21 为投影矩阵 W 是由三个轨迹基组成的矩阵 如果符合W 空间的轨迹 中国科学技术大学本科毕业论文 23 左乘以 得到的还是 否则出入较大 通过这个错误函数计算法则 轨迹矩 阵能够被稳定地分成两类 2 4 本章小结 在本章中 我们分析了一种特征点提取和匹配算法 了解了两种移动环境下 的运动补偿算法 各自文献上的实验结果表明 方法是确实有效的 我们期望在下面实验中验证其有效性 同时提出一种新的轨迹分析算法 对 比几种算法的性能 分析优劣并对现有技术框架加以改进 中国科学技术大学本科毕业论文 24 第三章 基于矩阵重建的运动轨迹分析算法 由上一章关于运动轨迹分析的讨论可以知道 当场景中存在自主运动的物体 时 物体上的特征点的轨迹将与背景的轨迹模式存在较大区别 其轨迹将不能 由 3 个背景基向量线性表达 即残差 1 会比较大 此时运动 轨迹矩阵可以分解为 2 3 1 其中 B表示由摄像头运动导致的运动轨迹模式 其秩不超过 3 表示线性 表达误差 对于背景点来说 中元素的值都接近于 0 仅对于运动目标上的特征 点 其误差取值较大 图 3 1 特征点轨迹示例 其中背景点的轨迹基本一致 以上矩阵分解是在假设背景物体静止且无噪声的条件下得出的 但在现实场 景中 噪声不可避免 而且许多背景物体是动态变化的 如随风飘动的树枝和旗 帜 左右摆动的玩偶等 此时问题更加复杂 这可能使得一些背景轨迹的线性表 达误差也会比较大 我们可以认为运动轨迹矩阵是背景运动模式 前景运动模式 和噪声三部分组成 2 F 3 2 其中B是低秩的背景运动模式 F是前景运动模式与背景运动模式的残差 其特点为背景轨迹列向量接近 0 前景轨迹列向量值较大 E为噪声 其取值都 较小 如背景点的小幅运动 特征点的定位误差等 中国科学技术大学本科毕业论文 25 3 1 基于低秩矩阵恢复的轨迹分析算法 矩阵分解问题 3 2 可以转化为求解以下的凸优化问题 24 mi 1 2 ubj ct to B F E W 3 3 ra k B 其中 1和 2分别表示矩阵 X 的核范数 所有奇异值的和 一阶 范数 所有元素绝对值的和 和二阶范数 所有元素的平方和 该问题是典型 的带噪声的低秩矩阵恢复问题 学者们已经提出了很多的求解算法 而其中又以 微软亚洲研究院林宙辰等人提出的增广拉格朗日方法最为高效 25 不过我们的 情况稍有特殊 即 B 的秩不超过 3 因此需要对其中的算法作简单的修改 即在 进行 SVD 分解时仅选择前 3 个奇异值 通过以上矩阵分解 任意一条轨迹被分为 3 部分 根据前 文的分析过 是前景运动模式与背景模式的残差 如果该轨迹的属于背景区域 那么其特点为背景轨迹列向量接近 0 前景轨迹列向量值较大 因此可以根据残 差的大小来判断哪些轨迹属于背景 哪些轨迹属于前景 如果用 0 表示背景 用 1 表示前景 那么有 1 2 1 0 3 4 其中参数 T 为用户设定的残差阈值 轨迹分析的算法见图 3 2 算法 3 1 基于低秩矩阵恢复的轨迹分析算法 输入输入 轨迹矩阵W 2 参数 T 1 初始化 0 0 0 0 0 0 2 while not converge do 3 1 4 1 5 1 6 2 1 7 1 中国科学技术大学本科毕业论文 26 8 Update 1 9 end while 10 for each column of F do 11 label L by formula 3 3 12 end for 输出 输出 图 3 2 基于低秩矩阵恢复的轨迹分析算法 3 2 基于低秩矩阵填充的轨迹填充算法 以上的轨迹分析只能针对满长度轨迹 长度与时间窗相等的轨迹 或者说贯 穿全部F帧的轨迹 进行 而对于一些匹配轨迹长度小于F的特征点则无从分析 从而使得轨迹点比较稀疏 对下一步的背景建模不利 特别是在运动物体的前方 不断的有特征点被运动物体遮挡 以及新的背景特征点在运动物体的后方出现 这将导致轨迹分析在运动物体的前后方出现较大区域的空白 面对这些问题 一种直观的做法是减小轨迹的长度 但是这会带来两方面的 问题 1 减小轨迹长度会加强背景动态变化的影响 可能导致属于动态背景的 点被误判为前景点 2 一些前景特征点可能在一小段时间内与背景点呈现相似 的轨迹 导致算法对于前景的跟踪丢失率提高 另外一种思路是 我们可以通过插值方法对轨迹进行低秩填充 通过延伸轨 迹长度来利用短轨迹进行分析 但是现有的插值方法普遍存在一些问题 最严重 的就是无法预测特征点的运动模式 从而对矩阵整体的低秩性进行保证 我们提出基于稀疏表达的轨迹恢复算法对长度处于 F至F之间的轨迹进行填 充 假定待恢复的轨迹为y 且y中有一部分维度被抹平了 其可以表示为 y Wx 其中W为字典 e 为表达误差 如果我们采用那些满长度的轨迹矩 阵作为字典 那么当属于背景轨迹时 根据上一小节的分析的低秩约束原则 x 应当非常稀疏 且误差向量e 只在y被抹平的维度取值较大 这是一个典型的 1最 小化问题 可以将其描述为 mi 1 1