角点检测技术在镜头自动切割中的研究与应用

本科毕业设计(论文)( 2012届 )论文题目 角点检测技术在镜头自动切割中的 研究与应用 Research and Application of SIFT for Automatic Shot Segmentation 学 生 姓 名： 贾 淇 学 号： 080701111 二级学院名称： 电子信息学院 专 业： 广播电视工程 指 导 教 师： 李金龙 职 称： 讲 师 合作/企业教师： 职 称： 郑 重 声 明我谨在此郑重声明：本人所写的毕业论文角点检测技术在镜头自动切割中的研究与应用均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。 承诺人（签名）： 年 月 日浙江传媒学院本科毕业论文 角点检测技术在镜头自动切割中的研究与应用角点检测技术在镜头自动切割中的研究与应用摘要: 镜头自动切割技术的应用有效地提高了海量视频数据的管理及检索效率。本论文以视频镜头结构作为切入点，以视频的图像序列作为镜头分割的基础，利用图像特征匹配算法检测出镜头边界，从而实现镜头自动分割。众多图像匹配算法中，SIFT 角点检测算法具有良好的尺度、光照和空间旋转的不变性。针对视频基本结构、图像序列特点及SIFT算法进行简单阐述，合理高效地进行图像序列匹配，并根据算法特点设计镜头自动分割应用方案。首先读取视频数据获得图像序列矩阵，将图像数据转换为灰度图像便于SIFT算法进行处理，对视频图像序列进行SIFT角点检测，采用欧氏距离为匹配度量函数应用于图像匹配，返回匹配数值，并将匹配结果作为镜头边界度量标准，设置合理阈值，从而实现镜头自动分割。最后，就提高SIFT算法效率及适用性进行讨论，同时根据设计方案进行了大量的实验仿真，实验结果证明了算法的有效性。关键词：镜头分割；SIFT；角点；图像特征RESEARCH AND APPLICATION OF SIFT FOR AUTOMATIC SHOT SEGMENTATIONAbstract: Automatic Shot Segmentation technology effectively improve the management and retrieval of mass video data. Considering the video structure，this paper describes the implement of automatic shot segmentation which is based on the video image sequence theory，withtheimagefeature matchingalgorithm to detecttheshot boundary. Among many matching algorithm，SIFT（Scale Invariant Feature Transform）is not variable in the scale and rotation in the image changes，but also has a strong adaptability in illumination. Introducing the basic structure of the video、 image sequence characteristics and the SIFT algorithm，matching the image sequence, and then designing applications of automatic shot segmentation based on algorithm characteristics. First read the video data to obtain the image sequence matrix，converting the image data into grayscale images to facilitate the processing of SIFT algorithm. Making SIFT detection for video sequences. Euclidean distance was adopted as the measuring function into matching. Return the matchingvalue and compare the value with the pre-configured threshold. Then Automatic Shot Segmentation can be achieved.At last, discussed ways to enhance the efficiency and applicability of the SIFT algorithm, based on the theoretical analysis, lots of numeric experiments are performed, and the experimental results verify the improvements of the proposed algorithm.Key words：shot segmentation ; SIFT; keypoint ; image feature目 录1绪论11.1选题背景11.2国内外现状21.3研究目的及意义42图像特征匹配概要研究52.1视频结构分析52.2图像匹配概述62.3图像匹配算法比较73角点检测技术在镜头自动切割中的应用方案设计73.1应用方案流程图设计73.2视频图像序列的获取93.3帧图像的SIFT角点检测93.3.1建立尺度空间并选取候选点93.3.2精确确定关键点113.3.3确定关键点方向133.3.4提取特征描述符143.4特征点匹配153.5视频序列的合成与输出164基于角点检测算法的视频镜头分割实验与测试184.1实验环境184.1.1实验平台184.1.2运行环境194.2角点检测应用于图像匹配194.2.1单幅图片角点检测结果194.2.2图像序列特征匹配结果204.3图像序列匹配阈值统计224.4镜头层图像序列的自动合成输出235总结和展望245.1总结245.2展望25致谢26参考文献27浙江传媒学院本科毕业论文 角点检测技术在镜头自动切割中的研究与应用 1 绪论1.1 选题背景随着科技生活的进步和互联网的蓬勃发展，每天都有大量的图像和视频信息不断产生，如何有效地在这种视频大仓库的环境中组织和检索视频信息已成为数据库领域以及信息检索领域中研究的关键问题。由于视频的来源和内容非常广泛，因此为了更好的组织视频信息，视频镜头分割技术便成了解决该问题的关键技术。镜头分割也是计算机视觉和图像处理领域的热点，在多媒体通信、视频检索与交互处理、智能监控系统中得到了广泛的应用。因此，视频分割往往不是独立应用的，它通常是为了方便视频的进一步分析处理而做的前期准备。镜头分割技术中，我们可以通过着重研究如何定位视频中的转场帧（镜头）继而对视频进行场景分割。转场帧是指与前一帧差异较大的帧，常用方法是通过帧差法、统计法、模式匹配分类法等，此类方法一般是基于RGB、HSI、LAB、CMYK等计算两帧的差异性，再通过阈值判断是否为转场帧，这忽略了图像内部对象形状和纹理的相似性。本课题主要研究使用角点检测技术进行镜头分割，应用较好的主流角点检测算法有：SIFT角点检测技术、Harris算法、广义Hough变换等。相对于原图像而言，使用角点进行匹配能够大大减少计算量，因此角点在图像匹配中有良好的应用价值，通过该技术检测不同帧的角点方向和个数，以此为特征比较不同帧的差异性，从而实现转场帧的自动判断和分割。计算机视觉处理中的一项基本任务就是图像的角点检测，同时角点检测也是图像处理的一项基本任务。在各种影像特征中角点特征具有其特有优势，即角点具有旋转、尺度及光照不变性的优点。利用角点特征在一些应用中进行图像处理，不仅可减少计算数据量且完整保存图像灰度信息。此外角点在图像匹配的研究中具有很重要的意义，图像匹配是计算机视觉的一个重要方面，在众多的视觉应用中是个关键技术，广泛的应用于地理信息系统、物体识别领域，利用角点特征进行匹配可以大大提高匹配的速度。尤其在实时处理中有很高的应用价值。因此角点检测已成为很多研究课题的重要环节。采用特征点即角点进行图像匹配可以追溯到1981 年，Moravec 采用角点检测做立体匹配。1988 年，Harris 和Stephens 改进了Moravec 的检测器，使检测到的特征更加稳定。1992 年，Harris 介绍了他的角点检测器在运动跟踪和3 维重构方面的优势，从此之后，角点检测方法被广泛的使用。角点检测最初的应用多在于运动跟踪和立体匹配方面，后来Zhang 等人在1995 年实现了图像角点的匹配。他们使用了角点邻域的关联窗来寻找可能的匹配。1997年Schmid 和Mohr做出了开创性的工作，他们采用图像的局部特征进行图像匹配，使得一个特征可以和一个大的图像库中的图像做匹配。他们同样采用Harris 角点，但不同的是，他们开创性的使用了旋转不变的、图像局部区域的描述子。Harris 角点检测对尺度变化十分敏感，Lowe 在1999 年实现了局部特征的尺度无关性，并且他提出了新的局部描述子，这种描述子更具独特性和鲁棒性，较好的解决了物体遮挡、旋转缩放、视角变换引起的图像变形等问题。从此SIFT角点检测技术在多次使用及研究的过程中一直在不断优化不断完善。SIFT角点检测算法由D.G.Lowe 1999年提出，2004年完善总结。随后Y.Ke用PCA代替直方图将SIFT算法中的特征描述子进行改进。SIFT 角点检测算法的主要思想即是从图像中提取局部特征，在尺度空间寻找极值点，确定其位置，尺度，保证特征点具有旋转性。该特征具有良好的旋转、尺度及亮度不变性，同时对视角变化、仿射变换、噪声也保持一定程度的稳定性。应用在海量特征数据库中进行快速、准确的匹配。近年来，在图像处理领域，类似SIFT特征的局部不变特征描述子在特征识别以及图像特征匹配方面均有显著发展。SIFT算法采用提取图像的SIFT特征，实用于在海量数据库中进行快速实时的匹配。另外，SIFT算法提取的少数特征点具有大量的SIFT特征，可以对图像的特征点进行准确的匹配。因此对于视频帧图像的特征匹配中，使用SIFT算法有很多便利之处。因而使用角点检测技术能够实现镜头的分割，以便于应用到如多媒体通信、视频检索与交互处理、智能监控系统等各个场合中。1.2 国内外现状特征提取在图像处理、重建3D场景、运动趋势估计、目标跟踪识别、图像匹配等计算机视觉领域中起着非常重要的作用。而图像的一个重要特征角点，对图像图形的分析和理解有很重要的作用，长期以来备受研究者关注，也取得了很多研究成果。角点是二维图像亮度变化剧烈的点或图像边缘曲线上曲率极大值的点，能很好地被区分出来，这些点保留了图像的重要特征，同时利用信息量用于处理计算，切实实现高效快速的计算速度。经过三十多年的发展，产生了大量的角点检测算法，取得了很大的突破和进展，但此领域的研究一直受到相关研究人员的重视，对于角点检测的方法如何优化使之更高效是十分值得关注的研究方向。 国内外关于角点检测按检测目的大致分为三类，第一类是基于灰度图像进行特征点检测，通过该方法检测角点首先应计算图像中曲率和梯度值，基于灰度图像的角点检测技术又分为基于梯度的方法和基于模板的方法，通过计算边缘曲率获得角点是基于梯度的方法，边缘强度与边缘方向的变化率都会影响到角点的计算。图像亮度的变化则是基于模板的方法主要考虑的问题，该方法定义角点为在邻域点中对比度足够大的点。其中基于梯度的方法要比基于模板的角点检测方法对噪声更为敏感。第二类是基于轮廓曲线的角点提取，根据图像的边缘特征，用轮廓点来计算对称性、边缘曲率或夹角来判定角点。这类方法定义角点为曲率函数最大值点，这样很容易通过阈值方法将其检查出来。第三类是基于二值图像的角点检测，研究人员提出一种新的基于形态骨架的角点检测方法，该方法把原始图像比成一个多边形，角点即为骨架中最大圆盘半径为零的点，并由它的补图来获得凹点的角点，通过由原图及补图获得的角点进行异或操作，则得到全部角点并去掉离散化后产生网格角点。因为在二值图像阶段处理，计算量并不是很大，所以保证了计算的实时性。应该指出的是，虽然将二值图像作为一个单独的检测目标列出来，但是基于灰度图像的各种处理方法对此仍然有效。二值图像处于灰度和边缘轮廓图像的中间步骤，所以专门针对此类图像的角点检测方法并不多见1。通常在计算机视觉中，图像匹配是一个非常重要的基础步骤，也是国内外研究的热点。由于角点在图像匹配中占有重要地位，因此，图像匹配技术目前的主要方法有基于灰度的方法和基于图像特征的算法。到目前为止，计算机视觉领域中，还没有在数学方面给出很好的角点定义。对于不同的角点检测方法具有多种不同的数学描述，因此对于角点也有多种定义。因为对于定义的理解不同，所以在检测方法及评判标准难以统一。考虑到实际应用的需求，从快速性、准确性、鲁棒性等角点检测技术需提高的问题及要求出发,可以看出各种角点检测算法各有利弊。直接基于图像的角点检测基本上是全局搜索；基于边缘轮廓的角点检测数据量较少，可以采用多分辨分析并行处理，从灰度图像得到边缘轮廓曲线要经过两次以上的全局搜索,速度并不是很快，但对角点的误检和漏检要比直接基于图像的方法好得多。如果在得到轮廓曲线的过程中应用一些其他的变换方法，就计算的速度而言下降不少1。SIFT算法采用提取图像的SIFT特征，使其具有很多优点：SIFT特征是图像的局部特征，它对图像的光线亮度变化、尺度缩放以及旋转都能保持不变，对视角变化和噪声也保持一定程度的稳定性。实用于在海量数据库中进行快速实时的匹配。另外，SIFT算法提取的少数特征点具有大量的SIFT特征，可以对图像的特征点进行准确的匹配。虽然SIFT算法有诸如上述的很多优点，但是在相似的环境或对称的环境下匹配正确性很低。因此现在一些国内外相关研究人员也着手对SIFT算法提出了改进。因为没有角点确切的定义，所以方法的优劣难以通过定量评价标准来评判，导致在进行图像匹配时选择角点检测方法时没有很好的依据，且在研究过程中没有很好的改进方法。对于角点检测算法稳定性及精确性的衡量，同样不存在恰当的定义。一些现有的评判准则对于研究图像噪声等参数的变化对检测结果的影响也无法定论。这些参数包括高斯尺度、阈值、信噪比和在原始图像的灰度级转换宽度。在角点检测技术中，阈值通常需要通过大量实验验证进行手动设定，自动化程度不高，对于不同的视频信息，阈值的设定标准也有所不同，未来在研究角点检测方法的同时，我们仍需要关注阈值的选取标准。1.3 研究目的及意义多媒体压缩等众多编码技术的发展、计算机性能大幅提高及Internet应用的快速增长导致了数字视频的海量增长。数字图书馆、视频点播、交互式电视、远程学习、多媒体信息系统等应用都产生和使用了大量的视频数据。这一切都需要一些能够有效地索引、浏览和检索相关视频资料的工具，这些工具首先需要将视频数据重组为层次化的结构数据。这种结构数据可以按照自顶向下的结构定义为节目、场景、镜头和帧，把一个视频流准确地重组并构造成这样的层次需要较为复杂的技术支撑，有时候甚至是件十分困难的事情。从视频流中检测出其基本单位即每个独立的镜头只是其中关键的一步，是随后的高层内容分析、分类、索引和查询的基础。镜头边界检测，即镜头分割，是进行自动数字视频序列检索的第一步2。综上所述，研究镜头自动分割技术具有十分重要的实践及理论意义。该技术的研究不仅可以直接作用于人们的日常生活和工作，从海量视频信息中提取目标镜头，还可以推动基于内容的视频检索技术以及视频结构化理论研究的发展，使数字图像处理技术得到更广泛的应用。本论文在内容安排上主要分为以下几个部分：第一章 简要介绍视频镜头分割以及图像特征匹配的研究背景和国内外现状以及本课题的主要研究目的和意义。第二章 概括介绍视频结构理论及图像匹配技术，详细介绍了图像匹配常用技术帧差法和图像特征匹配中角点检测算法等两种技术，并对其进行了概要的比较和总结。第三章 具体阐述了基于SIFT角点检测技术的视频镜头自动切割技术的研究与应用方案，包括视频帧描述及图像序列的合成、帧图像的SIFT角点检测技术、特征点匹配、特征匹配数目阈值的选取及设定等一系列方案的总体设计思路。第四章 根据实验方案进行实验测试，并分析数据。第五章 总结全文，阐述自己在本次研究设计中所做的工作和本论文需进一步改进和优化的地方。2 图像特征匹配概要研究2.1 视频结构分析视频结构的划分依次为节目层、场景层、镜头层、帧层。从节目层到帧层语义信息逐渐减少。帧即是一副静态图像，因此帧是视频组成中的最小逻辑单元。镜头是摄像机连续拍摄的一段视频，由若干帧组成，描绘一个事件或一个场面的一部分，如“飞机起飞”这组镜头，它的画面色彩和纹理等图像特征基本保持不变。镜头是对视频流进行处理的最小物理单元，它包含了少许语义内容，强调构成帧的视觉内容相似性，由于在同一组镜头中，属于同一组镜头的帧图像之间的特征保持稳定，在镜头内部的图像变化，其原因一般是摄像头的运动和对象的运动、以及光源的亮度变化等3。如果相邻图像帧之间的特征发生了明显变化，则认为发生了镜头变化。在一组视频镜头中，可以选取一幅能够代表镜头内容的图像作为关键帧。语义上相关并且时间上相邻的若干组镜头组成了场景，如新闻场景中连续相关的多个镜头表现一则新闻故事等。场景是视频所蕴含的高层抽象概念和语义的表达。场景可以是相同对象的不同角度、不同技法拍摄，也可以是具有相同主题和时间的镜头组合，强调语义的相关性。视频层包含一个完整的时间或故事，作为最高层的视频内容结构，它包括视频的组成关系以及对视频的摘要、语义和一般性描述等4。在视频流数据中，其最小的语义数据单元是“镜头”，视频分割就是将视频中的连续图像帧在特征突变地方（镜头边界）分割开来，镜头边界是指相邻的镜头与镜头之间的帧，这个边界是上一个镜头的结束帧或下一个镜头的开始帧。因此，视频分割不是将视频数据流还原成图像帧，而是将连续帧分割成长短不一的视频镜头，由于镜头是视频检索的基本单元，为了对视频进行结构化处理，需要将视频还原多个单独的镜头，这个过程即成为镜头分割。镜头分割的主要任务是找出镜头边界的定位，确定边界帧的位置或时间点，即可据此对视频进行分割。所以，镜头分割一般又称为镜头边界检测。镜头用来表示视频内对象在时空上连续的一组运动。基于这个假设，可以推论出镜头与镜头之间的帧间差异大于镜头内的帧间差异。由此，镜头分割的主要思路是通过判断连续帧之间的差异来识别镜头的边界，根据镜头边界把视频分割为单独的镜头3。检测帧间差异本质上即是进行图像特征匹配。2.2 图像匹配概述图像匹配就是在两幅或多幅采集于同一场景并具有一定重叠区域的图像中，利用恰当的配准方式和有效的相关运算，建立正确的映射变换关系的图像处理技术。图像配准方法一般有三类，分别为基于灰度的匹配方法，基于频率域的匹配方法，基于图像特征的匹配方法。其中基于灰度的匹配方法是直接利用灰度信息找出能使原始图像间相似度达到极值的变换模型参数值，要求原始图像灰度差异不能太大，计算量很大。基于频率域的匹配方法是将原始图像由空间域变换到频率域，再根据已知的变换原理来实现图像间的配准。基于图像特征的匹配方法，通过提取原始图像的明显特征，建立图像间特征的匹配关系从而确定整幅图像的对应关系，处理对象为图像特征而非像素点，因此处理信息量小，不受灰度差异和变形方式的限制5。图像匹配较常用方法有帧差法，本文采用基于图像特征的匹配方法，常用方法有角点检测技术。帧差法较为简单，利用帧差法进行图像匹配的主要途径就是判断相邻图像帧之间特征的绝对差。该方法是通过采集视频获取图像序列计算帧间差异实现的。按照时域顺序每副图像分别作为后一帧图像模板进行比较，记录连续帧之间的差值，并以此做判断其是否在同一镜头层中。具体实现是通过计算相邻两个图像帧中所有像素的色彩亮度之和，两帧的差别就定义为各自对应像素的亮度和之差。在图像的各种特征中，角点是图像的轮廓线上局部曲率变化最大的点，是一类能够反映图像特征的重要局部特征，具有平移、旋转不变性质。角点包含的信息数据量较小，即非常小的数据信息保存了图像的灰度变化的特征信息，同时外界影响因素对角点特征提取算法的影响也较小，因此角点检测对于图像处理的研究意义重大。角点检测技术是目前计算机视觉领域中高效的图像匹配技术之一，处理图像时利用角点作为入手点，在保证了图像信息的同时，又减少了数据量，对于图像内容特征匹配具有很高的研究价值，且匹配效率和效果都优于其他技术。2.3 图像匹配算法比较根据两种图像匹配方法的实现过程，我们可以分析一般图像匹配法与图像特征匹配方法二者差异，具体为角点检测技术与帧差法差异比较，确保实现完善高效的匹配结果，从而确定本文实验方案中图像特征匹配方法的选取。（1） 帧差法实现简单，程序设计复杂度低，角点检测方法研究图像内部结构，如计算像素点梯度的差异等，与帧差法比较，由于计算较为复杂，所以计算效率有所下降。（2） 由于帧差法的计算复杂程度低，这使得利用该方法进行图像匹配时实时性较强，可实现实时监视，由此可广泛应用于视频对象运动速度较慢时或者背景简单的场合，例如电话会议、电视播音等。而角点检测技术则多应用于视频或图像已完整呈现后的后期处理与分析上，实时性效果不够理想。（3） 在大多数视频中，帧差法存在运动区域及图像特征区域的背景遮挡现象，且该方法主要考虑图像整体的数据差异性，与角点检测技术比较缺少了对画面内部结构的分析，匹配成功率较低。在这方面，角点检测技术则强调分析画面内部形状和纹理，更为智能化。综上所述，结合基于图像匹配进行视频分割的可实现性与准确性考虑，我们选取SIFT角点检测技术进行图像特征匹配。3 角点检测技术在镜头自动切割中的应用方案设计3.1 应用方案流程图设计本论文在研究基于SIFT角点检测技术的镜头自动切割应用的理论基础上，同时进行实验方案设计，进行大量有效实验。角点检测技术在镜头自动切割中的应用方案设计如下： 图3- 1 应用方案流程图读取视频信息并获取待测帧图像数据利用二维高斯函数与图像卷积生成尺度空间建立图像高斯金字塔利用高斯差分核建立DOG金字塔便于SIFT算法进行图像处理分别在尺度空间与二维空间比较各点，确定候选关键点去除低对比度点及边缘响应点，精确确定关键点位置计算关键点梯度方向，确保其具有旋转不变性根据关键点周围44个种子点得到一个128维特征向量。返回特征点数 检测下一幅图，利用PCA主成分分析法进行特征匹配，返回匹配点数目NNT合成输出镜头片段文件，并以镜头边界帧号命名整个视频图像序列是否修复完毕将所有处理完成视频帧进行合成否是是否该方案设计首先读取视频，获得其图像序列矩阵数据，进而进入该方案的第一个核心即对每幅画面进行SIFT角点检测，并逐帧进行图像特征匹配，返回匹配特征点数目N，与阈值T进行比较，若NT则在该帧处存在镜头边界，在此处进行视频镜头分割，合成输出镜头片段。以下介绍实验方案各步骤详细设计。3.2 视频图像序列的获取常见的视频格式有：AVI、MPEG、MOV、WMV、REAL VIDEO、n AVI、3GP、QuickTime、MKV、ASF、FLV等，而在Matlab中有效的读入视频帧则需要适当的视频编码方式，并非所有的视频文件格式都满足。故需对视频格式进行转换，以便视频帧在Matlab环境中能够被正常读入。在Matlab函数库中，可以直接调用aviread()函数来实现对于实验视频帧的读取。因此对视频运用Matlab软件进行处理之前，应先对其格式进行转换，使之成为恰当的avi格式以便读取，从而实现将视频文件转换为图片序列，读取图像数据得到其结构体，以便接下来进行的图像角点检测及特征匹配。3.3 帧图像的SIFT角点检测为了进行有效的图像特征匹配，需对各帧图像序列进行角点检测，提取每幅图像角点，并进行标识。在本文中我们采取SIFT算法进行角点检测，在进行检测之前首先将已得到的视频图像序列转换为灰度图像，便于使用SIFT方法处理。SIFT方法是一种局部不变特征点的提取方法，通过该方法提取的SIFT特征即是图像的局部特征，对旋转、尺度缩放和亮度具有不变性，对噪声及仿射变换也具有一定的稳定性。SIFT角点检测算法流程图：图3- 2 SIFT角点检测算法流程图去除低对比度及边缘响应点，精确确定关键点位置建立尺度空间，由高斯金字塔及高斯差分核建立DOG金字塔，从尺度空间及二维空间初步确定候选关键点确定关键点方向并利用关键点周围44个种子点生成128维特征描述符3.3.1 建立尺度空间并选取候选点尺度空间理论最早出现于计算机视觉领域，目的是为了模拟图像数据的多尺度特征。其基本思想是：在视觉信息的处理过程中引入一个尺度参数，通过连续变化的尺度参数获得不同尺度下的视觉处理信息，然后综合这些信息以便深入挖掘图像的本质特征6 。由于Koendetink 证明了高斯核是实现尺度变换的唯一变换核，所以即可利用二维高斯核对原始图像进行空间滤波，获得图像在多尺度下的尺度空间表示序列，而后对这些序列进行尺度空间特征提取，从而达到尺度不变性7。SIFT算法中，首先利用二维高斯滤波函数对图像进行高斯滤波，二维高斯滤波函数为： （3.1）其中为高斯分布函数的方差，即为尺度空间因子。一副二维图像在不同尺度下的尺度空间定义为该图像与高斯核的卷积： ，其中（x,y）表示图像上的点 （3.2）值越小则意味着图像被平滑的程度越大，小尺度对应图像的细节特征，图像的概貌特征由大尺度呈现，因此选择合适的尺度因子平滑是建立尺度空间的关键。（1）建立高斯金字塔为了得到在不同尺度空间下的稳定特征点，图像应与不同尺度因子下的高斯核进行卷积，构成高斯金字塔8，高斯金字塔共有O组S层，第一组第一层为原始图像，对原始图像进行一次尺度因子为的高斯卷积得到第二层图像，第三层图像尺度空间因子则为k,即相邻层之间的尺度因子比例为k，不同组对应相同层之间的尺度因子相同。同时每一组图像均由上一组图像降二采样得到，图像大小即为前一组图像的1/2。（2）建立DOG金字塔为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。DOG金字塔是相邻两尺度空间函数之差，用表示，它是利用不同尺度因子的高斯差分核（由对应相邻尺度空间相减得到）与图像卷积生成： （3.3）如图3- 3所示，左侧部分为高斯金字塔中相邻两组，右侧为对应高斯差分核与图像卷积后生成的DOG金字塔9。图3- 3高斯金字塔和DOG金字塔（3）检测空间极值点为了寻找尺度空间中的极值点，每一个采样点要和它所有的相邻点比较，如图3- 4 所示，检测点与和它同尺度的8个相邻点及上下相邻尺度对应的92个点共26个点进行比较，以确保在尺度空间和二维图像空间都检测到极值点，所得的最大或最小值点即为局部极值点，这些极值点构成了一个SIFT候选关键点的集合10。本实验中所提取的图像角点特征即在该集合中选取。图3- 4 DOG尺度空间局部极值检测3.3.2 精确确定关键点通过将尺度空间图像看成一个曲面，根据特征点周围像素点的梯度分布情况，拟合三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度）。由于DOG算子对噪声和边缘较敏感，故需要去除不稳定的边缘响应点。此外，还需要过滤低对比度特征点，以增强匹配稳定性、提高抗噪声能力11。（1）去除低对比度点尺度空间函数的二次泰勒展开式为： （3.4）其中x为候选关键点之一，为包含特征点位置和尺度信息的向量，当x趋于0时对上式求导，得到关键点精确位置： （3.5）针对该精确位置的点的尺度空间函数的计算，将3.5式代入3.4式可得： （3.6）对于数值，若该数值小于0.03，则认为该点属于低对比度点并进行抛弃12。由于DOG金字塔在图像边缘部分具有很大的边缘响应，此处的点对噪声也极为敏感，因此仍需去除边缘响应点。（2）去除边缘响应点SIFT算法中主要利用海森边缘检测方法进行边缘响应点的去除，一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率13。的主曲率通过一个22 的Hessian矩阵H求出： （3.7）的主曲率和H的特征值成正比，令为最大特征值，为最小的特征值，则 （3.8）令，则： （3.9）其中(r + 1)2/r的值在两个特征值相等的时候最小，且随着r的增大而增大，因此，为了检测主曲率是否在某域值r下，只需检测 （3.10）选取合适的主曲率阈值，可以去除不稳定的边缘响应点，从而获得精确定位的极值点作为关键点14。在Lowe的SIFT算法介绍的文章中，取r10。3.3.3 确定关键点方向为了使检测出的特征点具备旋转不变性，可以利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数。梯度方向及模的计算公式如下： （3.11）其中(x,y) 是关键点的邻域像素，L所用的尺度为每个关键点各自所在的尺度。 在实际计算时，我们在以关键点为中心的邻域窗口内采样，建议采用大小为1616的邻域范围，并用直方图统计邻域像素的梯度方向。梯度直方图的横轴表示邻域像素的梯度方向，范围是0360度，其中每10度一个柱，总共36个柱，纵轴代表了邻域像素梯度值的大小。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。图3- 5是采用7个柱时使用梯度直方图为关键点确定主方向的示例。 图3- 5由梯度方向直方图确定主梯度方向在梯度方向直方图中，当存在一个相当于主峰值80%能量的峰值时，则将这个方向定为该关键点的辅方向。一个关键点可能会被指定具有多个方向（一个主方向，一个以上辅方向），这可以增强匹配的鲁棒性，减少图像旋转对特征关键点的影响15。 至此，图像的关键点已检测完毕，每个关键点有三个信息：位置、所处尺度、方向，由此可以确定一个SIFT特征区域6。3.3.4 提取特征描述符确定关键点方向后，接着用特征向量对关键点进行描述，使其数值化。首先将平面坐标系的坐标轴旋转至关键点的主方向，以确保其具有旋转不变性。 图3- 6由关键点邻域梯度信息生成特征向量接下来以关键点为中心取88的窗口。图3- 6（1）所示中央黑点即为当前关键点，每个小格代表关键点邻域所在尺度空间的一个像素，小格中箭头为该像素点梯度信息，其中箭头方向代表该像素的梯度方向，箭头长度代表其梯度模值，图中圆圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每44的小区域上计算8个方向（即每45度一个区间）的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图3- 6（2）所示。此时一个关键点由22共4个种子点组成，每个种子点由一个八维向量表示。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性16。 为了增强匹配的稳健性，SIFT算法中对每个关键点使用44共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响11。 通过利用SIFT角点检测技术，我们获得待分割视频图像序列SIFT参数，分别为：图像矩阵数据、描述子、对应特征点位置信息。返回的这三个参数将利用到接下来的图像特征点匹配中。3.4 特征点匹配SIFT特征向量匹配是根据相似性度量来进行的。由于PCA-SIFT描述符与标准SIFT描述符具有相同的亚像素位置、尺度和主方向，但在特征描述符生成时有所不同，PCA-SIFT用主成分分析法（PCA）将传统SIFT的128维特征向量进行降维，以达到更精确的表示方式17。因此，在本实验中我们将采用改进SIFT匹配方式对图像进行特征匹配。当两幅待匹配图像通过PCA-SIFT特征提取算法提取出各自的SIFT特征向量并进行精确定位后，生成相对应的描述符，采用关键点特征向量的欧几里得距离来作为两幅图像中关键点相似性的判定度量。两个特征向量之间的欧氏距离越小，即表示这两个点越相似匹配程也就越高。首先找出其中一幅图像的某个关键点，利用遍历方法计算出该点与另外一幅图像所有点的欧氏距离。为了避免过滤掉本身具有较大差异的正确匹配关键点，采用邻近搜索方法进行比较。获取SIFT特征向量后，采用优先k-d树进行优先搜索来查找每个特征点的近似最邻近特征点。具体为取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，如果最近的距离除以次近的距离小于某个比例阈值t，则接受这一对匹配点，t一般取值范围在0.60.75之间，本文取0.6，t的取值越小，关键点匹配对数越少但会更加稳定。本实验中，由于余弦角距离比欧氏距离对于离群点具有更好的鲁棒性，所以用余弦角距离代替欧氏距离进行度量18。特征点匹配流程如图3- 7所示：图3- 7 特征点匹配流程读取相邻两幅图像所有角点SIFT参数，主要提取其描述子矩阵特征向量组1中一个向量与特征向量组2所有向量相乘，得两向量余弦角，替代欧式距离进行数值比较对所得余弦角距离进行排序得到最近距离与最小距离将两幅图像并排放置在同一副图中，按照特征向量组顺序开始计算匹配索引值大于零继续处理下一帧最近点在特征向量中的位置赋值给匹配索引值最近距离与次近距离之比小于0.6第一幅图像中的关键点按照匹配索引值找到第二幅图中相应匹配点，并用线段连接是否是否在该步骤中，对输入的实验视频分解的帧序列进行逐一匹配，并返回其匹配特征点数目，作为镜头层差异的判断依据。3.5 视频序列的合成与输出在对视频图像序列进行角点检测并实现特征匹配后，方案实施最后阶段即需判定镜头边界并输出镜头视频序列。为了判定各帧图像之间的匹配数目是否满足镜头边界，在此需设定一个阈值。该阈值的选取为本节的难点，固定阈值的方法无法满足视频内容的复杂变化，检测准确率势必降低。一般说来，一个可接受的镜头边界分割算法应满足：合理的计算复杂程度且易于实施，对实际问题具有较强的适应性。在每帧图像进行图像角点检测后，调用MATLAB中的imshow(image)以及M（m）=getframe，其中m为索引标志，初始值设为1，即从第一帧开始将图片信息按照时域顺序储存在M结构体中，M中包含图像数据信息及调色板。设定第i帧与第i+1帧的角点匹配数目为N，镜头边界图像匹配阈值为T，每得到一个N值，均使之与T值进行比较，若NT，则说明第i帧与第i+1帧之间特征匹配数目小于应匹配数目最小值，即在此视频画面出现了不连续性表现，可判定此处为镜头边界，输出该镜头视频，反之则边界不存在，为同一镜头内画面，继续进行图像角点检测，相邻图像特征匹配及匹配数目阈值比较，并设定m=m+1，将索引值自动加1。若第i帧处判定为镜头边界，通过调用来movie2avi(M,filename)进行视频输出，即根据M结构体中图像数据生成相应的avi视频文件，从而实现已分割镜头的自动输出。在此为便于区分，在输出视频文件名中加入该镜头最后一帧帧号，通过调用语句filename=sprintf(out%d.avi,j)实现，其中j为对应帧号。该步骤详细流程图如图3- 8所示：图3- 8 图像序列合成及镜头视频文件输出流程读取图片数据并显示按照时域顺序存储图片数据于结构体中比较两相邻图像匹配关键点数目N与初始设定阈值T将结构体中图像数据按时域排列输出avi格式视频以镜头边界帧号（最后一段为last）命名输出文件继续处理下一帧判定i帧处为镜头边界NT是否由以上流程图分析可知，在逐帧进行图像特征点匹配后，新建一个存储图像数据结构体用于新的图像序列即镜头的输出，在每幅画面进行匹配后均将其图像数据放入该结构体中，直到检测到匹配点数目NT，则封装结构体中图像数列生成视频文件，同时清空该结构体进入之后的匹配比较，如此直至视频图像序列最后一帧为止。4 基于角点检测算法的视频镜头分割实验与测试4.1 实验环境4.1.1 实验平台本实验采用MATLAB7.0实现，MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化等诸多强大功能集成在一个易于使用的视窗环境中，代表了当今国际科学计算软件的先进水平。MATLAB拥有强大的图形功能以及世界一流水平的数值计算函数库，它的数字图像可以以矩阵形式表示，这意味着MATLAB强大的矩阵运算能力对于图像处理非常有利，矩阵运算的语法对MATLAB中的数字图像同样适用。因此本次实验选MATLAB实现基于角点检测技术的镜头自动切割。4.1.2 运行环境（1）操作系统：Windows 7（2）CPU：AMD Athlon（tm）P320 2.10G（3）内存：2.00G（4）显卡：ATI Mobility Radeon HD 5145（5）硬盘：320G4.2 角点检测应用于图像匹配本次实验首先选取一段avi格式视频作为实验视频，在Matlab中通过调用aviread（）读取视频信息，返回该视频信息相应的Matlab结构变量，通过提取该结构体中cdata获得对应图像序列数据，调用rgb2gray（）使各图像数据转换成相应灰度图像数据，至此，视频即分解为帧图像序列且转换为所需灰度图像，按照时码顺序逐一对图像序列进行角点检测返回所需图像特征参数，实验结果如下：4.2.1 单幅图片角点检测结果以图4- 1中图像为例，对该图像进行角点检测，生成特征描述向量并获得其角点数目。对图像中检测出的角点及对应特征向量进行显示，在其原有图像基础上生成一幅新的图片，并在其中标识出所有关键点特征向量，为方便实验观察，将所有关键点特征向量模值放大六倍。角点检测结果如图4- 2所示。图4- 1原始待检测图像图4- 2标识角点图像在这幅图像中，共检测出795个角点。从已标识出角点的图像中可以看出，角点多集中在树木边缘及亮色花朵周边，这也验证了角点的定义，即角点是二维图像亮度变化剧烈的点或图像中物体边缘曲线上曲率极大值的点。4.2.2 图像序列特征匹配结果按照时域顺序读取视频图像序列后，逐一进行角点检测，并读取各幅图像的角点数目，并依次进行图像特征匹配，返回匹配关键点数值。采用以下相近的两幅图像为角点检测特征匹配对象，原始图像如图4-3- 1原始图像1、图4-3- 2原始图像2。图4-3- 1原始图像1图4-3- 2原始图像2分别对这两幅图像进行角点检测，令特征向量模值放大六倍，并将两幅图像检测结果置于同一张图片中以便观察比较，其中第一幅图像检测结果为Error! Reference source not found.左图所示，共检测出795个角点，第二幅图像检测结果为图4-3- 3右图，共检测出837个角点。图4-3- 3标识角点图像针对已检测出的两幅图像进行特征匹配，即利用由主成分分析法改进的SIFT特征匹配方法对两幅图像中关键点进行最小距离计算，得出匹配关键点显示其匹配角点数目，并用线段将对应匹配点连接，使匹配结果更为直观，如图4-4 所示。图4-4 特征匹配图像该图显示匹配像素点有183个，从图中我们可以观察到，匹配像素点多对应于图像中同一物体的同一特征部位，而与其在图像中的位置无关，由此体现出SIFT角点检测方法具有位置尺度不变性的良好性能。4.3 图像序列匹配阈值统计图像序列按照时域顺序逐帧进行图像匹配并返回匹配关键点数目后，按照设计实验方案应与设定初始阈值进行判断并输出视频，本节将针对阈值的选取设定进行实验，以达到最佳效果。首先选取具有多个镜头的avi格式视频作为实验素材，读取视频并获取图像序列信息，对该图像序列进行逐帧图像匹配，并返回图像特征匹配数目。预览视频初步判断镜头边界处时间，计算对应帧号范围。统计匹配数目并显示数据列表，与帧号范围比较，反复试验确定适合该视频阈值。取一个具有三个镜头的视频片段，逐帧检测其图像特征匹配点，描点如图4- 5 所示：图4- 5 实验视频图像序列特征匹配统计该视频为无损avi格式，时长为00:00:15:04,帧率为29帧每秒，通过先验统计，约在6S、9S处视频有镜头切换。该统计图表横坐标为帧号，纵坐标为匹配点数目，从图中清晰可见，在X=183及X=262处特征匹配数目有明