下载文档原格式
随着多媒体信息的发展，视频成为人们获取信息的重要途径，面对海量的视频，如何从视频中提取关键部分，提高人们看视频的效率已经成为人们所关注的问题。
视频摘要技术正是解决这一问题的关键，在视频摘要技术中的核心部分就是关键帧的提取。
关键帧的提取可以分为以下六类：（1）基于抽样的关键帧提取基于抽样的方法是通过随机抽取或在规定的时间间隔内随机抽取视频帧。
这种方法实现起来最为简单，但存在一定的弊端，在大多数情况下，用随机抽取的方式得到的关键帧都不能准确地代表视频的主要信息，有时还会抽到相似的关键帧，存在极大的冗余和信息缺失现象，导致视频提取效果不佳[1]。
（2）基于颜色特征的关键帧提取基于颜色特征的方法是将视频的首帧作为关键帧，将后面的帧依次和前面的帧进行颜色特征比较，如果发生了较大的变化，则认为该帧为关键帧，以此得到后续的一系列关键帧。
该方法针对相邻帧进行比较，不相邻帧之间无法进行比较，对于视频整体关键帧的提取造成一定的冗余。
（3）基于运动分析的关键帧提取比较普遍的运动分析算法是将视频片段中的运动信息根据光流分析计算出来，并提取关键帧。
如果视频中某个动作出现停顿，即提取为关键帧，针对不同结构的镜头，可视情况决定提取关键帧的数量。
但它的缺点也十分突出，由于需要计算运动量选择局部极小点，这基于语义相关的视频关键帧提取算法王俊玲，卢新明山东科技大学计算机科学与工程学院，山东青岛266500摘要：视频关键帧提取是视频摘要的重要组成部分，关键帧提取的质量直接影响人们对视频的认识。
传统的关键帧提取算法大多都是基于视觉相关的提取算法，即单纯提取底层信息计算其相似度，忽略语义相关性，容易引起误差，同时也造成了一定的冗余。
对此提出了一种基于语义的视频关键帧提取算法。
该算法首先使用层次聚类算法对视频关键帧进行初步提取；然后结合语义相关算法对初步提取的关键帧进行直方图对比，去掉冗余帧，确定视频的关键帧；最后与其他算法比较，所提算法提取的关键帧冗余度相对较小。
聚类识别阈值-概述说明以及解释1.引言1.1 概述聚类是一种常用的数据分析方法，用于将数据集划分为具有相似特征的数据簇。
在聚类分析中，阈值是一个关键的参数，用于确定数据点之间的相似性和差异性。
通过设置合适的阈值，可以有效地识别出不同的数据簇，并提供有价值的信息用于决策和预测。
聚类算法的目标是通过最大化簇内的相似性和最小化簇间的相似性来使得聚类结果更加准确。
阈值在聚类识别中扮演着重要的角色，它可以用来区分簇内和簇间的相似性。
当相似性超过阈值时，数据点将被划分到同一个簇内；而当相似性低于阈值时，则被划分到不同的簇内。
选择合适的阈值对于聚类分析的准确性和稳定性至关重要。
如果阈值过小，可能会导致过多的簇被合并为一个簇，造成信息的丢失；反之，如果阈值过大，可能会导致簇内的差异性过大，无法准确地识别不同的数据簇。
因此，研究和确定合适的聚类识别阈值对于提高聚类分析的质量和效果具有重要意义。
通过深入研究聚类算法的原理和方法，结合实际应用场景，可以找到合适的阈值选择策略，从而在聚类识别中取得更好的结果。
本文将深入探讨聚类的概念和应用，聚类算法的原理和方法，以及阈值在聚类识别中的作用。
进一步地，本文将总结研究结果并强调阈值的重要性，同时对未来研究方向进行展望。
1.2文章结构1.2 文章结构本文主要分为引言、正文和结论三个部分。
下面详细介绍每个部分的内容。
引言部分主要包括概述、文章结构和目的三个方面。
概述部分旨在介绍聚类识别阈值的重要性和研究背景，强调其在实际应用中的价值。
文章结构部分（即本节内容）则是对本文内容进行概括性的介绍，指导读者了解全文结构和各部分的主要内容。
目的部分则明确了本文的研究目标和意义，以及对读者的启示。
接下来是正文部分，主要划分为三个小节。
2.1 聚类的概念和应用将简单介绍聚类方法以及其在数据挖掘领域中的应用。
2.2 聚类算法的原理和方法将详细介绍常见的聚类算法原理，包括K-means、层次聚类和密度聚类等，并给出其优缺点。
自动阈值算法是一种用于二值化图像的算法，它可以自动地确定图像中的像素值应该是1还是0。
这种算法通常被用于数字图像处理中的图像分割、目标识别和特征提取等任务。
自动阈值算法的基本思想是通过统计图像中像素的灰度值分布情况来确定阈值。
常用的自动阈值算法有以下几种：
1. Otsu算法：Otsu算法是最常用的自动阈值算法之一。
它通过计算图像中像素的灰度值分布直方图来确定阈值，使图像中两个类别（1和0）的类间方差最小。
Otsu算法的优点是快速且准确，但对于噪声较多的图像可能会出现误分类的情况。
2. 均值漂移算法：均值漂移算法是一种基于局部均值的图像分割算法。
它可以自动地确定阈值，将图像中的像素分成两个类别。
该算法的优点是可以处理噪声较多的图像，但对于复杂的图像可能会出现误分类的情况。
3. 基于支持向量机的算法：基于支持向量机的算法是一种基于机器学习的自动阈值算法。
它可以通过训练支持向量机模型来确定阈值，将图像中的像素分成两个类别。
该算法的优点是可以处理复杂的图像，但需要大量的计算资源和时间。
4. 基于神经网络的算法：基于神经网络的算法是一种基于人工神经网络的自动阈值算法。
它可以通过训练神经网络模型来确定阈值，将图像中的像素分成两个类别。
该算法的优点是可以处理复杂的图像，但需要大量的计算资源和时间。
总之，自动阈值算法可以帮助我们快速地对大量的二值化图像进行分类和处理，但需要根据具体的应用场景选择合适的算法。
关键帧筛选策略(一)关键帧筛选策略引言在计算机视觉和图像处理领域，关键帧是视频序列中具有代表性的帧。
在大数据时代，利用有效的关键帧筛选策略能够大大提高数据处理和分析的效率。
本文将介绍一些常见的关键帧筛选策略。
1. 基于时间间隔的策略•通过固定的时间间隔选择一定数量的关键帧，例如每隔1秒选择一帧。
这种策略简单直观，适用于不需要考虑内容变化的情况。
•根据关键帧之间的内容变化程度选择关键帧。
可以通过计算帧与前一帧之间的差异来度量内容变化程度，选择差异较大的帧作为关键帧。
2. 基于内容分析的策略•利用图像特征评估方法，如SIFT、SURF或HOG来提取帧的特征，然后通过特征相似度来选择关键帧。
可以使用聚类算法将相似的帧归为一类，选择每一类中代表性最强的帧作为关键帧。
•利用深度学习技术，通过预训练的视觉模型提取帧的特征表示，然后通过相似度或重要性得分来选择关键帧。
3. 基于目标检测的策略•对每一帧进行目标检测，将其中包含感兴趣目标的帧选为关键帧。
可以使用一些经典的目标检测算法，如SSD、Faster R-CNN或YOLO来实现目标检测。
•根据目标的变化情况，选择变化较大或关键目标出现的帧作为关键帧。
4. 基于视频质量评估的策略•使用视频质量评估算法，如PSNR、SSIM等，对视频帧进行质量评估，选择质量较高的帧作为关键帧。
•根据视频播放场景的需求，选择与场景匹配的关键帧，例如选择画面清晰、光线适中、没有抖动的帧作为关键帧。
结论关键帧筛选策略在计算机视觉和图像处理领域具有重要意义。
根据不同需求，可选择基于时间间隔、内容分析、目标检测或视频质量评估等不同的策略来进行关键帧的选择。
通过合理的策略选择，可以提高数据处理效率，加速图像或视频处理的步骤，为后续分析和应用提供可靠的数据基础。
基于GEP自动聚类算法的视频关键帧提取方法袁晖;元昌安;覃晓;彭昱忠【摘要】视频关键帧提取技术是视频数据处理研究领域的热点研究问题。
该文针对现有的镜头边界检测技术不能有效提取关键帧的不足，提出一种基于小波边缘检测算子的自适应分块视频镜头边界检测算法。
通过检测视频镜头变化，得到分割的镜头，然后对视频帧提取图像特征，并利用基因表达式编程（GEP）的自动聚类功能对视频帧进行聚类，提出并实现了基于GEP自动聚类的视频关键帧提取算法（KFC‐GEP）。
实验证明该方法能较好的提取视频序列的关键帧。
%The technology of key frame extraction is a research focus in video data processing do‐main .A video shot boundary detection algorithm with adaptive division based on wavelet edge detec‐tion is presented to overcome the drawbacks of the available algorithms for shot detection technology in this paper .First ,we obtain the video shot segmentation by detection of video shot change .Fur‐thermore ,we extract the image feature from video ,which cluster by autoclustering based on Gene Expression Programming ,propose and implement the video key frame extraction using an autocluster‐ing algorithm based on Gene Expression Programming (KFC‐GEP) .The proposed method is demon‐strated efficiently and effectively for extracting the key frame in video experimental results .【期刊名称】《广西师范学院学报（自然科学版）》【年(卷),期】2013(000)001【总页数】4页(P98-101)【关键词】镜头边界检测;小波边缘检测;视频关键帧;KFC-GEP【作者】袁晖;元昌安;覃晓;彭昱忠【作者单位】广西师范学院计算机与信息工程学院，广西南宁 530023;广西师范学院计算机与信息工程学院，广西南宁 530023;广西师范学院计算机与信息工程学院，广西南宁 530023;广西师范学院计算机与信息工程学院，广西南宁530023【正文语种】中文【中图分类】TP3910 引言近些年来，随着网络技术及信息采集技术的发展，视频数据呈指数级增长，与之对应的视频数据处理的需求也急剧增长。
自适应阈值法公式自适应阈值法，是一种信号处理中常用的方法，用于自动根据输入信号的特性调整阈值的大小，以实现更好的信号分割效果。
该方法可以应用于图像处理、音频处理、信号识别等领域。
自适应阈值法的基本思想是根据信号的统计特性来动态地确定阈值的大小。
传统的阈值处理方法通常使用固定的阈值进行信号分割，但这种方法对于不同类型的信号效果并不理想。
因为不同类型的信号具有不同的统计特性，传统的固定阈值方法无法适应这种变化。
而自适应阈值法通过分析信号的统计特性，根据实际情况动态地调整阈值的大小，从而能够更好地适应不同类型信号的分割需求。
自适应阈值法可以通过多种方式实现。
其中一种常用的方法是基于局部统计特性进行阈值调整。
具体而言，该方法将输入信号分割为若干个局部区域，然后针对每个局部区域计算出一个局部阈值，最后根据这些局部阈值进行整体的信号分割。
这种方法的优点是能够充分利用信号的局部特性，提高分割的准确性。
但同时也存在一些缺点，比如计算复杂度较高，对噪声敏感等。
另一种常用的自适应阈值法是基于全局统计特性进行阈值调整。
这种方法不再将信号分割为局部区域，而是直接对整个信号进行统计分析。
具体而言，该方法通过计算信号的均值、方差等统计量，然后根据这些统计量确定一个全局阈值，最后根据该阈值进行信号分割。
这种方法的优点是计算简单，对噪声的影响较小。
但同时也存在一些缺点，比如无法充分利用信号的局部特性，分割效果可能不够准确。
除了以上两种方法，还有一些其他的自适应阈值法。
比如基于图像梯度、基于灰度直方图等方法。
这些方法各有优劣，可以根据具体的应用场景选择合适的方法。
自适应阈值法是一种有效的信号处理方法，能够根据输入信号的特性动态地调整阈值的大小，以实现更好的信号分割效果。
这种方法在图像处理、音频处理、信号识别等领域有着广泛的应用前景。
通过不同的实现方式，可以适应不同类型信号的分割需求。
然而，不同的方法也存在各自的优缺点，需要根据具体的应用场景选择合适的方法。
《吸引子传播聚类算法的理论改进及其应用》一、引言随着大数据时代的到来，数据挖掘和机器学习技术得到了广泛的应用。
其中，聚类算法作为数据挖掘的重要手段之一，受到了越来越多的关注。
吸引子传播聚类算法（Affinity Propagation Algorithm）是一种新型的聚类方法，以其高效和良好的聚类效果得到了众多研究者的青睐。
本文将重点介绍吸引子传播聚类算法的理论改进及其应用。
二、吸引子传播聚类算法概述吸引子传播聚类算法是一种基于数据点之间相似性的无监督聚类方法。
该算法通过计算数据点之间的吸引度值和归属度值，实现数据的自动聚类。
该算法的优点在于不需要预先设定聚类的数量，且在处理大规模数据集时具有较高的效率。
然而，该算法在处理某些复杂数据集时仍存在一些不足，如对噪声和异常值的敏感性、参数设置的复杂性等。
三、理论改进针对吸引子传播聚类算法的不足，本文提出以下理论改进措施：1. 引入新的相似度度量方法：传统的吸引子传播聚类算法通常采用欧氏距离等简单的方法计算数据点之间的相似度。
本文提出采用更复杂的相似度度量方法，如核方法和深度学习特征等方法，提高数据点的相似性度量准确性。
2. 参数优化策略：吸引子传播聚类算法中的一些参数设置对聚类效果具有重要影响。
本文提出一种基于自适应阈值的参数优化策略，通过动态调整参数，使算法在处理不同类型的数据集时能够取得更好的效果。
3. 结合其他算法的优点：本文将吸引子传播聚类算法与其他聚类算法相结合，如K-means、谱聚类等，形成混合聚类算法。
通过结合不同算法的优点，提高聚类的准确性和鲁棒性。
四、应用改进后的吸引子传播聚类算法在多个领域得到了应用：1. 图像分割：在图像分割领域，吸引子传播聚类算法可以用于图像的自动分割和分类。
通过对图像的像素或特征点进行聚类，实现图像的语义分割和区域分割等任务。
2. 文本聚类：在文本处理领域，本文利用改进后的吸引子传播聚类算法进行文本的自动分类和聚类。
自适应阈值算法
自适应阈值算法是一种常用的图像处理算法，它可以根据图像的特征自动调整阈值，从而实现图像的二值化处理。
在实际应用中，自适应阈值算法被广泛应用于图像分割、目标检测、字符识别等领域。
自适应阈值算法的核心思想是根据图像的局部特征来确定阈值。
传统的阈值算法通常采用全局阈值，即将整幅图像分为前景和背景两部分，但是这种方法对于光照不均匀、背景复杂的图像效果不佳。
而自适应阈值算法则可以根据图像的局部特征来确定阈值，从而更加准确地分割图像。
自适应阈值算法的实现过程通常分为以下几个步骤：
1. 将图像分割为若干个小区域，每个小区域内的像素值相似。
2. 对每个小区域内的像素值进行统计分析，计算出该区域的平均值和标准差。
3. 根据每个小区域的平均值和标准差计算出该区域的阈值。
4. 将每个小区域内的像素值与该区域的阈值进行比较，将像素值大于阈值的像素标记为前景，将像素值小于阈值的像素标记为背景。
自适应阈值算法的优点在于它可以根据图像的局部特征自动调整阈值，从而更加准确地分割图像。
但是该算法也存在一些缺点，例如计算量较大、对噪声敏感等问题。
因此，在实际应用中需要根据具
体情况选择合适的算法。
自适应阈值算法是一种常用的图像处理算法，它可以根据图像的局部特征自动调整阈值，从而实现图像的二值化处理。
在实际应用中，该算法被广泛应用于图像分割、目标检测、字符识别等领域，具有重要的应用价值。
计算机研究与发展ISSN 100021239/CN 1121777/TPJournal of Computer Research and Development 42(10):1752～1757,2005 收稿日期:2005-06-14 基金项目:北京交通大学科技基金项目(2004sm013)基于自适应阈值的自动提取关键帧的聚类算法王方石 须 德 吴伟鑫(北京交通大学计算机与信息学院 北京 100044)(wfs @computer 1njtu 1edu 1cn )A Cluster Algorithm of Automatic K ey Frame ExtractionB ased on Adaptive ThresholdWang Fangshi ,Xu De ,and Wu Weixin(School of Com puter &Inf orm ation Technology ,Beijing Jiaotong U niversity ,Beijing 100044)Abstract It is a common method to extract key frames using the unsupervised cluster algorithm 1But the algorithm is sensitive to the initial number of the classes and the initial classification 1It is problematic to predefine the absolute number of key frames without knowing the video content 1An approach for two times clustering is presented 1In the first time ,the similarity distances of the consecutive frames in a shot are clustered into two classes so that the thresholds needed in the second time clustering process can be deter 2mined adaptively 1In the second time clustering ,all the frames in the shot are clustered using dynamic clus 2ter ISODA TA algorithm 1Then the frame nearest to the center of its class is automatically extracted as one key frame in the shot 1It is simple and effective with no need to predefine any threshold 1Experimental re 2sults of many videos with different traits demonstrate the good performance of the proposed algorithm 1K ey w ords key frame ;unsupervised cluster ;ISODA TA algorithm ;adaptive threshold摘 要 利用无监督聚类算法来提取关键帧是一种常用的方法,但该算法对类别数和初始类划分较敏感,在对视频内容一无所知的情况下,要求预先指定聚类数目是一个很困难的问题1提出一种二次聚类的方法;第1次以镜头内相邻两帧的相似度为数据样本进行聚类(分成两类),计算确定第2次聚类所需的阈值;第2次采用动态聚类的ISODA TA 算法,以视频序列的帧为数据样本进行聚类,得到最终聚类结果1最后在每类中自动提取距其类中心最近的帧为关键帧1该算法简单且行之有效,无需预定义任何阈值(如聚类数目)1对大量不同特点的视频进行了实验,该算法均取得了较好的实验结果1关键词 关键帧;无监督聚类;ISODA TA 算法;自适应阈值中图法分类号 TP3911 引 言为了有效地访问视频内容,首先需要将视频分解为一系列镜头,然后从每个镜头中提取最具代表性的、反映该镜头主要内容的若干帧,称之为关键帧1使用关键帧可简洁地表达镜头,为视频索引、浏览和检索提供合适的摘要,大大减少了视频操作的数据处理量1关键帧的提取主要涉及两个问题:①关键帧要具有代表性,能反映镜头内容;②关键帧的数量应根据镜头内容的变化程度而确定,内容变化大的镜头提取关键帧的数量要多1目前,已有多种关键帧提取技术1文献[1]计算当前帧与已存在的每个聚类中心之间的距离,同预先指定的阈值相比较,若当前帧与所有聚类中心间的距离均大于该阈值,则从该帧开始形成一个新类别,否则将其分配到离它最近的类中1取各类中离类中心距离最小的帧为关键帧1显然,关键帧数由类别数确定,而类别数又取决于指定的阈值1文献[2]提出结合关键帧和目标分割的算法,以Kullback Leibler(K L)距离作为度量,假设镜头中有N帧,先用文献[1]的聚类方法提取M(<N)个候选关键帧,用其为场景中的目标建立GMM模型,从所有候选关键帧中分割出目标,然后用SFFS(sequential forward floating selection)方法提取关键帧1由于该算法首先采用文献[1]的聚类方法提取候选关键帧,所以它也是依赖于阈值的1纵观上述算法,均需预先指定一些经验阈值,这些阈值对某些实验数据有效,对有些无效1尤其是在对视频内容一无所知的情况下,要求预先指定决定聚类数的经验阈值是一个很困难的问题1众所周知,无监督聚类算法对类别数和初始类划分较敏感,初值设置不当对实验结果影响很大1而视频中镜头长短不一,内容千差万别,不可能用统一的阈值对所有的实验数据均取得较好的效果1文献[3]提出自动确定类别数的方法,但却要指定两个阈值,最大关键帧数M和控制能否成为候选关键帧的参数r,该算法的最大难点就是选取r值1文献[4]采用聚类有效性分析,首先指定一个比实际类数大得多的类别最大数,取值为C=10+NΠ25,其中N为视频序列中帧的总数1然后将所有镜头的帧放在一起,进行C次标准的k均值聚类,每次聚类的类别数依次取[1,C]中的整数,计算其类分散度,使类分散度最小的类数即为最佳类别数1最后找离类中心最近的帧作为每类的关键帧1文中只给出了确定最佳类数的方法,并未说明如何划分初始类,而初始类的划分常常会影响最终结果1文献[5]在计算当前帧与其前一帧颜色直方图间相似度f col的同时,还要计算当前帧与其前K(文中取值20)帧颜色直方图均值之间的相似度f d,然后采用Otsu技术确定一个阈值T1若f col>T,则当前帧为关键帧,否则,若f d>T,则当前帧也为关键帧1另外还采用层次块匹配算法得到每帧的运动能量,取运动能量极小值处的帧为关键帧1只有两种方法都提出的帧才是真正的关键帧1其中K是人为给定的参数,且对实验结果有很大影响;层次块匹配算法本身也需设定一个参数———搜索范围,若像机进行快速变焦或摇移,而搜索范围过小,块匹配的结果就很不准确,若搜索范围过大,又会影响算法的时间效率12 提取关键帧的算法本文提出二次聚类的方法,可在已分割好的镜头中,根据其内容的变化程度,自适应地确定聚类所需的阈值,如关键帧的个数等,无需预定义任何阈值1然后采用动态的无监督聚类算法自动提取关键帧1该算法分4步:①读取镜头中的所有帧,提取各帧的特征向量并存入视频数据库;②进行第1次聚类,以相邻两帧间的相似度为样本,在一维数据空间中聚类,得到第2次聚类所需要的阈值;③第2次聚类采用ISODA TA算法,对镜头中的所有帧进行动态聚类;④在每类中提取离类中心最近的帧为关键帧1211 特征提取本算法采用HSV颜色累积直方图和MPEG27中推荐的边缘直方图描述符作为视觉特征1将H, S,V分别分为8,4,1个级别,得到一个32维的颜色特征向量,记为f c1再对每帧提取边缘直方图,得到一个80维的纹理特征向量,记为f t1为了消除各特征向量取值范围差异性的影响,对其进行高斯归一化1f c i,k表示第i帧的第k个颜色分量,f t i,k表示第i帧的第k个纹理分量,则计算两帧间相似度的公式为si m(F i,F j)=w1∑31k=0(f c i,k-f c j,k)2 + w2∑79k=0(f t i,k-f t j,k)2 ,(1)其中,w1和w2分别为颜色特征和纹理特征的权值,在本文中均取值0151为简化起见,下文中不分特征类型,用f i,k表示第i帧的第k个特征分量1 212 自适应确定聚类阈值并划分初始类所有基于帧差来判断两帧是否相似的方法都要指定一个阈值,本文提出一种自适应计算阈值的算法,即第1次聚类,其过程如下:(1)设一个镜头中有N帧{F1,F2,F3,…,F N},连续读入,利用式(1)求相邻两帧的相似度,得到数组Dif={D1,D2,…,D N-1};(2)以Dif中的元素作为一维数据空间的样3571王方石等:基于自适应阈值的自动提取关键帧的聚类算法本,进行聚类,分为两类1为提高算法效率,先对Dif 中的元素由大到小排序,假设排序后有:D1≥D2≥…≥D N-1,令T为T=arg minδ2W,(2)其中,δ2W=q Hδ2H+q Lδ2L,q H=T,q L=N-T-1,μH =1q H∑Ti=1D i,μL=1q L∑N-1i=T+1D i,δ2H =1q H∑Ti=1[D i-μH]2,δ2L=1q L∑N-1i=T+1[D i-μL]2,则D T就是所求阈值1(3)若相邻两帧帧差≥D T,则开始新的类;否则,若当前帧与当前类中心的距离≥D T,则开始新的类;(4)算法停止,得到初始类别数和初始类的划分1应用此算法对大量镜头进行了测试,限于篇幅,只给出视频序列Forest的曲线1如图1所示,曲线的横坐标是Dif中由大到小排序的元素D i所对应的第1帧的序号,纵坐标是以D i为分界点分成两类后计算所得的δ2W值1图中曲线最低点所对应的横坐标为60,这表示将Dif中已排序的元素在第60,其类内分散度最小,则D60即为所求阈值,比D60大的值有59个,因此初始划分的类数至少为60个1Fig11 Theδ2W curve of Forest sequence1图1 Forest序列的δ2W值曲线213 动态聚类并提取关键帧当镜头先对准A场景拍摄,接着对相机进行扫视(pan)、倾斜(tilt)、跟踪(track)或升降(boom)等操作,又对准B场景拍摄,然后转动镜头,再对A场景拍摄,假设A场景内容变化甚微,设为A′,则在提取关键帧时,文献[5]的方法会提出3个关键帧A,B,A′,而A和A′很相似,只用一个关键帧代表即可1文献[4]和本文所提算法采用动态聚类方法可解决此问题1在得到初始的类别数和初始类的划分后,本文采用ISODA TA算法[6]对镜头中的所有帧再进行动态聚类,即第2次聚类1该算法不仅能通过调整样本所属类别完成聚类分析,而且还能自动地进行类的合并和分裂,从而得到类数较为合理的各个聚类1ISODA TA算法需设置7个参数,以前的做法都是根据实验数据的先验知识,人为设定各参数值,显然不同数据对象的参数是不同的1本文采用自适应确定阈值的方法1K:期望得到的最大聚类数,取值为NΠ25,因为每秒视频包含25帧,1秒钟内最多提取一个关键帧,无需从太短的序列里提取关键帧;θN:一类中的最少样本数,取值为12(约015s);θS:标准偏差参数,取D T所对应那两帧(F i和F i+1)各特征分量之差的绝对值,即θS={|f i,0-f i+1,0|,|f i,1-f i+1,1|,…; |f i,d-1-f i+1,d-1|};θC:合并参数,取第212节第2步求得的D T;L:每次迭代允许合并的最大聚类对数,取值1;I:允许迭代的次数,本文中取值为41参数K,θN,L和I的值与视频内容无关,对所有镜头可以指定相同的值,与视频内容有关的阈值θS和θC是通过计算得到的1设由第212节得到的初始聚类数为c,初始的聚类为{Γi},各类中心为m i,i=1,2,…,c1该算法的主要思想为若某类的类内离散度大于各类离散度的均值 δ,且该类的最大标准偏差分量σj,max>θS,max(其中max表示最大标准偏差分量的序号),则将该类分裂成两个类1若某两类类中心之间的距离小于θc,则将这两类合并成一类1假设需要将类中心为m j的类Γj分裂成两个类中心分别为m+j和m-j的聚类,应把原来的m j取消,且令c增11原算法中m+j和m-j的计算如下:人为给定一个p(0<p≤1)值,令γj=pσj或γj=p [0,…,σj max,…,0]T(σj是该类的标准偏差向量),则m+j=m j+γj,m-j=m j-γj1可见p的取值至关重要,对不同的数据也不统一1本文给出一种新的计算m+j和m-j的方法,避免了手工设定阈值的随意性1考虑到新的两类的类中心之间应尽可能相距得远些,才能将样本分开,因此,首先求类Γj中相距最远的两帧,记为F i和F k,然后采用下式计算两个类中心:m+j=(m j+F i)Π2,m-j=(m j+F k)Π21(3)4571计算机研究与发展 2005,42(10) 计算类Γj 中每帧与两个新类中心的距离,将其归入较近的类中去1实验证明了该方法行之有效1在得到最终聚类后,从每一类中提取离类中心最近的帧作为关键帧1214 算法效率分析设N 为视频序列中的帧数,d 是视频特征的维数,C 为类别数,T 为迭代次数1本文算法中第1次聚类的时间复杂度是O (N d );第2次聚类的时间复杂度为O (N dC T );从理论上分析,本文提出的计算m +j 和m -j 的算法在最坏情况下时间复杂度为O (N 2d ),但实际上执行分裂步骤的概率很小,而且需要分裂的类中所包含的帧数比整个镜头中所含帧数少得多,故总的时间复杂度为O (N dC T +N 2d )1我们对文献[4]和文献[5]中算法的时间复杂度进行分析1文献[4]中,一次K 均值聚类的时间复杂度为O (N dC T ),共执行了N Π25+10次,总的时间复杂度为O (N 2dC T )1N dC T +N 2d N 2dC T=1N+1C T•1C T(因为N µC T )1 可见,与文献[4]中算法相比较,视频时间越长,本算法在时间效率上的优势越明显1文献[5]中采用颜色特征提取关键帧算法的时间复杂度为O (N d ),采用运动信息提取关键帧的时间复杂度为O (W HN S ),其中W,H 分别为图像的宽和高,S 为对每个像素点进行层次块匹配时搜索的范围,故总的时间复杂度为O (N d +W HN S )1以视频序列Hall monitor 为例,每帧大小为352×240,若层次块匹配算法中每点匹配次数S 不超过20次,特征向量的维数d 约120,迭代次数T 和类数C 一般不会超过10,可见本文算法并不比文献[5]效率低1文献[5]对Hall monitor 提取了4个关键帧,如图2所示:Fig 12 The key frames extracted in reference[5]1图2 文献[5]提取的关键帧3 实验结果及分析在AMD Athlon 2500+,256MB 内存,Windows XP 环境下,用VC ++编程实现了本算法1对不同特点的视频序列做了大量的测试,限于篇幅,仅以3个各具特点的镜头为例进行分析1图3显示对Hall monitor 视频序列最终提取的关键帧,该序列背景静止,前景目标做中速运动,共303帧,整个提取过程耗时1秒钟1初始类别为61个,因数量过多,图3中就不显示了1其原因是画面中背景所占比例较大,前景目标中速运动,相邻两帧差别不大,使类分散度最小的阈值在Dif 中的排序位置趋于中间,故初始类数过多1由于大多数类别中的帧数少于12帧,动态聚类中合并了这样的类,最终得到6类,所提取的关键帧数比文献[5]多了两帧,其结果符合人的主观判断,效果比较理想1Fig 13 The key frames of Hall monitor after dynamic clus 2tering 1图3 Hall monitor 视频序列动态聚类后的关键帧 图4显示对镜头Ball 提取的关键帧,该序列有摄像机的运动,也有前景目标的快速运动,共201帧,整个提取过程耗时1s 1图4(a )是从初始类中提取的所有关键帧,4(b )是动态聚类后提取的关键帧1可见,动态聚类后,将以0019和0030为关键帧的两类合并为一类,选0002为新的关键帧;将以0139和0151为关键帧的两类合并为一类,选0150为新的关键帧;将以0165,0174和0176为关键帧的3类合并为一类,以0172为新的关键帧;还将以0096为关键帧的类分裂为两类,分别以0067和0110为新的关键帧1本算法以离类中心最近的帧作为关键帧,所以初始类中的关键帧与动态聚类后提取的关键帧不同1从画面看,这样的处理符合人的视觉认知1图5显示对镜头Forest 提取的关键帧,该序列没有前景,只有摄相机的扫视、倾斜、缩小镜头(zoom out )操作,共301帧,整个提取过程耗时2秒钟1图5(a )是初始类中的部分关键帧,从图1可知初始类别至少是60个,在此只显示前5个和中间5个关键帧1注意到前5帧彼此间隔不超过12帧,且画面相似,却都被当成关键帧了,这是因为相机在扫视的过程中,强烈的阳光时而被茂密的树叶遮档,使画面变暗,时而透过树叶的缝隙直射镜头,使画面变5571王方石等:基于自适应阈值的自动提取关键帧的聚类算法亮,因此即使画面极相似,也会因明暗不同使帧间特征差很大1从图5(b )可以看出,经过动态聚类后,使分类变得较合理,这是因为算法将样本数少于12的类拆散,其元素被分配到离其最近的类中去1Fig 14 The key frames of Ball sequence 1(a )The key frames after initial clustering and (b )The key frames after dynamic clustering 1图4 Ball 视频序列的关键帧1(a )初始聚类后的关键帧;(b )动态聚类后的关键帧Fig 15 The key frames of Forest sequence 1(a )The par 2tial key frames after initial clustering and (b )The key frames after dynamic clustering 1图5 Forest 视频序列的关键帧1(a )初始聚类后的部分关键帧;(b )动态聚类后的关键帧4 结束语本文提出了一种二次聚类的方法,第1次是以相邻两帧间的相似度为样本,在一维数据空间中进行聚类,目的是要自适应地确定第2次聚类所需的阈值,避免人为指定聚类数对实验结果的影响1第2次采用动态聚类的ISODA TA 算法,以视频序列的帧为样本,在112维的数据空间中进行聚类,然后在每类中自动提取离其类中心最近的帧为关键帧1该算法可根据镜头中视频内容的变化程度,自动确定关键帧的个数,无需预定义任何阈值1从大量的实验结果来看,该算法取得了较理想的效果1参考文献1Y 1Zhuang ,Y 1Rui ,T 1S 1Huang ,et al 1Adaptive key 2frame extraction using unsupervised clustering 1IEEE Int ’l Conf 1Image Processing ,Chicago ,IL ,19982Xiaomu Song ,Guoliang Fan 1Joint key 2frame extraction and ob 2ject 2based video segmentation 1IEEE Computer Society Workshop on Motion and Video Computing (WACV ΠMO TION 2005),Breckenridge ,Colorado ,USA ,20053X 1Sun ,M 1S 1K ankanhalli ,Y 1Zhu ,et al 1Content 2based rep 2resentative frame extraction for digital video 1IEEE Multimedia Computing and Systems ,Austin ,Texas ,19984A 1Hanjalic ,H 1J 1Zhang 1An integrated scheme for automated video abstraction based on unsupervised cluster 2validity analysis 1IEEE Trans 1Circuits System Video Technol 1,1999,9(8):1280～12895G ao Qi ,C 1C ko ,Liyanage C de silva 1A universal scheme for content 2based video representation and indexing 1IEEE Asia 2Pacif 2ic Conference on Circuits and Systems (APCCAS 2000),Tianjin ,20006Bian Zhaoqi ,Zhang Xuegong 1Pattern Recognition 1Beijing :Ts 2inghua University Press,20001237～239(边肇祺,张学工1模式识别(第二版)1北京:清华大学出版社,20001237～239)W ang F angshi ,born in 19691Associate pro 2fessor 1Her research interests are content 2based video retrieval and pattern recognition 1王方石,1969年生,副教授,主要研究方向为基于内容的视频检索、模式识别1X u De ,born in 19441Professor and Ph 1D 1supervisor 1His main research interests are multimedia and content 2based videore 2trieval 1须 德,1944年生,教授,博士生导师,主要研究方向为多媒体、基于内容的视频检索16571计算机研究与发展 2005,42(10)Wu Weixin ,born in 19821Master candi 2date 1His main research interests include multimedia database 1吴伟鑫,1982年生,硕士研究生,主要研究方向为多媒体数据库1R esearch B ackgroundK ey frames are most suitable for content 2based video browsing ,where they can be used to guide a user to locate s pecific video segments of interest 1Furthermore ,key frames are also effective in representing visual content of a video sequence for retrieval purpos 2es :video indexes may be constructed based on visual features of key frames ,and queries may be directed at key frames using image re 2trieval techniques 1S o it is a basic and important work to extract a suitable number of key frames of a video sequence 1The number of key frames should vary along with the complexity of different videos 1The unsupervised clustering is a common method to extract key frames 1But it is hard to predefine the initial number of the classes frames without knowin g the video content 1In this paper ,we pre 2sent a method of two times clustering for automatically producing an adaptive number of key frames of an arbitrary video sequence 1In the first time ,the similarity distances of the consecutive frames in a shot are clustered into two classes so that the thresholds needed in the second time clustering process can be determined adaptively 1In the second time clustering ,all the frames in the shot are clustered using dynamic cluster ISODA TA algorithm 1Then the frame nearest to the center of its class is automatically extracted as one key frame in the shot 1This method is designed to work without any human supervision 1It is simple and effective with no need to prede 2fine any threshold 1欢迎订阅《计算机研究与发展》《计算机研究与发展》创刊于1958年,是我国第一个计算机刊物1现已成为我国计算机领域最有影响的学术期刊之一1多年来,本刊一直被评为我国计算技术类核心期刊;国务院学位办指定的评估学位与研究生教育的“中文重要期刊”;并成为美国《工程索引》(EI )、日本《科学技术文献速报》、俄罗斯《文摘杂志》、中国科技论文统计源期刊数据库、中国科学引文数据库等国内外重要机构的检索源期刊1《计算机研究与发展》多次荣获国家及省部级科技期刊奖及“百种中国学术期刊”奖1影响因子已达到01843;总被引频次为11631目前,本刊以漂亮的封面设计、特色鲜明的高质量内涵、活泼多样的栏目吸引着广大作者和读者1欢迎投稿,欢迎订阅1邮发代号:22654订价:48100元Π期,全年576元Π12期.到编辑部购买可享受八折优惠,即38.40元Π期,全年460元Π12期(含邮费)1通信地址:北京2704信箱《计算机研究与发展》编辑部邮政编码:100080电 话:(010)62620696;(010)6256553328609;联系人:王玉荣开户名称:中国科学院计算技术研究所开户银行:工行北京市分行海淀镇支行帐 号:020000450908812312357571王方石等:基于自适应阈值的自动提取关键帧的聚类算法。
