用于概括未知视频内容的方法

1.一种用于概括未知视频内容的方法，包括步骤：
选择视频的低水平特征；
根据低水平特征将视频划分成分段；
将分段分组成多个不相交的聚类，每个聚类包含相似的分段；
根据低水平特征标记多个聚类；
通过发现聚类的标记之间的关联，将多个聚类相关联，以推断出 高水平模式；和
根据高水平模式从视频中提取帧，以形成未知视频内容的内容自 适应摘要。
2.根据权利要求1的方法，其中，摘要是基于常见和不常见模 式的组合。
3.根据权利要求1的方法，其中，视频内容的制作风格是未知 的。
4.根据权利要求1的方法，其中，视频包括可视和音频数据。
5.根据权利要求1的方法，其中，从包括运动活性，颜色，文 本，音频，语义描述符及其组合的组中选择低水平特征。
6.根据权利要求1的方法，还包括步骤：
基于视频的选择的低水平特征由视频产生时间序列数据；和
对时间序列数据进行自相关以确定相似分段。
7.根据权利要求6的方法，还包括步骤：
平滑时间序列数据。
8.根据权利要求6的方法，还包括步骤：
对时间序列数据加权。
9.根据权利要求1的方法，其中，以多个时间分辨率发现所有 相似分段。
10.根据权利要求6的方法，还包括步骤：
对点跨距矩阵中的时间序列数据进行自相关，以测量表示分段相 似性的点跨距。
11.根据权利要求10的方法，其中，通过点跨距矩阵中基本上 对角的线来表示点跨距。
12.根据权利要求6的方法，还包括步骤：
对时间序列数据进行时间翘曲以发现相似分段。
13.根据权利要求12的方法，其中，通过动态规划执行时间翘 曲。
14.根据权利要求1的方法，还包括步骤：
在时间上对标记进行相关。
15.根据权利要求14的方法，其中，时间相关是同时的。
16.根据权利要求1的方法，还包括步骤：
生成标记出现的条件和结果，以发现高水平模式。
17.根据权利要求1的方法，其中，强关联与常见和不常见模式 相对应。
18.根据权利要求1的方法，其中，分组还包括步骤：
将重叠的分段进行划分，以使重叠分段具有相同的重叠或没有重 叠。
19.根据权利要求1的方法，还包括步骤：
为每个聚类分配参数，聚类参数包括聚类紧密度，聚类中分段的 数量，按帧测量的聚类中分段的总长度，和用于表示视频中分段的散 布的分段的最接近点之间的平均距离。
20.根据权利要求1的方法，还包括步骤：
估计成本函数，以确定所需的摘要长度。

技术领域\n本发明通常涉及计算机化视频处理，具体涉及用于概括视频内容 的方法和系统。\n背景技术\n数据挖掘是从大规模数据库和Internet中提取信息。数据挖掘已 经应用于市场、金融、传感器和生物数据的分析。数据挖掘不应当与 对数据进行搜索以得到已知模式的模式匹配混为一谈。\n基本上，数据挖掘是发现数据中“有兴趣的”和以前未知的模式。 有兴趣的模式通常是根据特定模式的重新出现频率来定义的。因为数 据挖掘并不假设任何预定的模式，所以它常常被描述为无监督的学习。\n数据挖掘从大量数据中推导出规则、趋势、规律和相关。数据挖 掘常常基于人工智能(AI)、基于记忆的推理(MBR)、关联规则生 成、决策树(DT)、神经元分析、统计分析、聚类和时间序列分析。\n聚类在数据中识别出相关信息的同类组。现有技术的聚类假定数 据中间的关系是已知的。聚类已经在统计学、模式识别和机器学习方 面进行了广泛的研究。聚类应用的例子包含市场分析中的顾客群划分、 传感数据中信号数据库的子类识别。\n聚类技术在广义上能够分成划分(positional)技术和分层 (hiearchical)技术。划分聚类将数据分成K个聚类，使得每个聚类中 的数据都比其它不同聚类中的数据彼此更相似。K的值能够由用户进 行赋值，或通过迭代确定以使聚类准则最小。\n分层聚类是划分的嵌套序列。凝聚(agglomerative)分层聚类将数 据置于原子聚类中，然后将这些原子聚类合并成越来越大的聚类，直 至所有数据均在单一大聚类中。分裂(divisive)分层聚类则颠倒这一过 程，其中从一个聚类中的所有数据开始，并将这个聚类细分成更小的 聚类，例如见Jain等人的“数据聚类算法”，Prentice Hall，1988， Piramuthu等人的“SOM神经网络与分层聚类方法之比较”，European Journal of Operational Research，93(2)：402-417，1996年9月， Michaud的“四种聚类技术”，FGCS Journal，Special Issue on Data Mining，1997，和Zait等人的“聚类方法的比较研究”，FGCS Journal， Special Issue on Data Mining，1997。\n大部分数据挖掘方法减少输入数据的维数。在高维数据空间中形 成的聚类不可能是有意义的聚类，因为在高维数据空间任意位置的预 期平均点密度较低。减少数据维数的已知技术包含主成分分析(PCA)、 因子分析、奇异值分解(SVD)和小波。主成分分析也被称为Karhunen -Loeve展开，其求解出能够说明数据特征方差的较低维表示，而因 子分析则求出数据特征中的相关性。Jain等人在“特征选择算法：评 估，技术报告”，计算机科学系，密执安州立大学，East Lansing，Mich.， 1996中描述了用于图像分析领域的技术。\n用于分析顾客购买模式的流行数据挖掘技术是对不明显关联或 关联规则的识别。明显关联的例子是购买婴儿代乳品的顾客也同时会 购买尿布。然而，1992年发现在傍晚时间人们会经常一起购买啤酒和 尿布。这样的关联是不明显关联的典型例子。正常情况下，人们不会 将尿布和啤酒联系为强相关的购买项目，因为啤酒通常不被认为是婴 儿代乳品。这样的方法也被称为购物篮分析法(market-basket analysis)。\n关联定义如下。如果有具有n个项I1，...，In的集合和选择这n 项中的一个子集的事务，例如数据库或操作，则在两项Ii和Ij之间的 关联被定义为规则R，用于被选入该子集的两项Ii和Ij中的任何事务。 规则R的条件被定义为Ii项的出现。规则R的结果被定义为Ij项的出 现。规则R的支持度被定义为具有项Ii和Ij的事务的百分比。规则R 的组合被定义为同一事务中Ii和Ij都出现。规则R的置信度被定义为 组合的支持度与条件支持度之比。最后，规则R的改进被定义为该规 则的支持度与条件Ii的支持度和结果Ij的支持度的乘积之比。\n当关联的支持度和置信度都很高时，关联就是强的。例如，对于 杂货店的交易，牛奶与每个其它售出的物品有很强的相关性，因此支 持度很高，因为大部分交易将牛奶作为其中一项。然而，对于例如像 贺卡这样的某些项，置信度很低，因为这些都不是被频繁购买的项目。\n最后，关联的改进也需要很强，因为小于1的改进表明条件没有 预测出比使用其本身组合的原始概率具有任何更好精度的组合。因此 即使该规则的支持度和置信度都很高，但如果相应的改进不大于1， 则该规则没有提供比纯随机更好的优势。下面，我们将描述视频特性 的“标签聚类”的关联的使用，而不是顾客的“购买项”。\n时间序列分析根据数据的时间间隔的函数将数据值关联。例如， 时间序列分析已经用于发现股票价格、销售量、气候数据和EKG分 析中的模式。通常假定存在产生时间序列的基础确定性过程，并且该 过程不是随机的。然而真实世界现象的时间序列数据经常与不确定性 数据，例如不可避免的随机噪声相互混杂。\n通常，使用例如欧几里得距离或其某种变型的相似度测量对时间 序列进行比较。然而，欧几里得距离测量往往不可靠。较健壮的相似 度测量是基于动态时间翘曲(DTW)技术，见Berndt等人的“发现时 间序列中的模式：动态规划方法”，知识发现和数据挖掘进展，AAA /MIT Press，Menlo Park，CA.pp.229-248，1966。DTW试图通 过有选择性地伸展和收缩时间轴来对准时间序列数据。\n直至现在，大多数数据挖掘技术已经把目光聚焦在文本数据、数 值数据和线性(一维)信号上。然而，现在海量的信息容易以具有空 间和时间维度的多维图像、电影和视频的形式获取。\n某些现有技术对视频进行初步的内容分析。最常见的方法是使用 一组标记样本训练专家系统，因此这些技术是基于监督学习的，而不 是基于无监督的数据挖掘，见Xu等人的“足球视频中的分割和结构分 析算法和系统”，IEEE国际多媒体会议及其博览会，东京，日本，2001 年8月22-25，Xu等人在2001年4月20日提交的美国专利申请09 /839,924，“域特定视频中的高级结构分析和事件检测的方法和系 统”，Naphade等人的“概率多媒体对象(multijects)：多媒体系统中的 索引和检索新方法”，1998年第五届IEEE图像处理国际会议论文集， 第三卷，pp.536-540。\n现有无监督视频分析技术大部分是内容中立的(content neutral)。 例如，已经通过从识别出的分段中选择关键帧对视频进行概括。该分 段通过检测场景或“快照”的变化，例如，音量的减弱或突然变化来确 定出来。场景所描述的是非实质性的。所选择的特定帧通常是按照某 种准则能够良好地代表快照中的其它帧。其它技术利用摄像机角度或 视场的变化，例如镜头的缩放。这样的内容中立技术已经取得了适度 的成功，并要求补充的内容特定的技术，以得到语义上满意的性能。\n然而，一般来说，与基于内容的视频挖掘相关的问题没有充分地 加以理解。\n例如，不清楚如果不进行相当大的修改，是否能够将著名的分类 和回归树(CART)应用于视频挖掘中。CART方法将独立的变量分 成小组的数据集，并将常值函数赋给该小数据集。在分类树中，常值 函数是一种取有限小值集合，例如是和否、或低、中和高的函数。在 回归树中，响应的平均值适于赋给连接较少(small connected)的数据 集。\n因此，希望提供一种用于挖掘从场景中探测的多维时间序列数 据，即通过摄像机获取的帧序列-视频的系统和方法。视频挖掘对于视 频中发现有兴趣的模式方面特别有用，其中例如编辑模型、新闻视频 特征或体育视频模式等等的域和内容的先验模型不容易获取。\n发明内容\n一个方法概括未知视频内容。首先，选择视频的低水平特征。然 后，根据低水平特征，将视频划分成分段。将分段分组成不相交 (disjoint)的聚类，其中，每个聚类包含有相似的分段。根据低水平 特征对聚类加标记，并分配表征聚类的参数。通过发现聚类的标记之 间的关联，将多个聚类相关联，以推断出高水平模式，并使用这些模 式从视频中提取帧，以形成未知视频内容的内容自适应摘要。\n附图说明\n图1是根据本发明的视频挖掘方法100的流程图；\n图2是高尔夫视频的时间序列图；\n图3是本发明使用的点跨距矩阵(point cross-distance matrix)；\n图4是具有重复模式的点跨距矩阵；\n图5是准对角最小成本路径的图表；\n图6是具有阈值角度的最小路径的图表。\n具体实施方式\n图1示出的是根据本发明的视频挖掘方法100的步骤。本发明对 于挖掘视频特别有用，其中内容中的模式不是先验已知的，例如监视 或家庭视频。发现的模式可以用于视频的“盲(blind)”概括。“盲”概括 的意思是指不必需要知道待概括的视频的内容或类型。我们的方法对 于例如广播新闻、体育报道、电影放映等等经过仔细准备的视频同样 有用。因此我们的方法允许对内容和产品风格存在不同差异的视频进 行盲概括(blind summarization)。\n我们从任意的、也许是未知内容和产品风格的视频101开始。该 视频包含可视和音频数据。首先我们选择110该内容的低级特征102， 例如特征组可以由运动活性(motion activity)、色彩、音频、文本等等 构成，例如MPEG-7描述符。可以用一个或多个选择的特征102进 行挖掘，每个挖掘轮次的结果可以组合以推断160输入视频101的更 高级理解。我们使用所选择的特征产生视频101的时间序列200。\n图2是基于运动活性的高尔夫比赛视频的时间序列200的例子。 图2画出的是高尔夫视频中运动活性的水平，它是时间的函数。根据 帧数在x轴201标明时间，沿y轴202标明运动活性，它是自前一帧 以来宏块中移动的像素的平均数。未加工(raw)的运动活性用曲线203 来表示。我们将运动活性数据划分为高211、中212和低213水平的 运动活性。\n我们观察后跟运动活性陡峭上升的低运动活性的长伸展，并且用 尖峰标记上升沿，如图所示。这样的尖峰对应于击球。直到击球时， 运动活性通常很低。在击球期间和紧接在击球之后，摄像机迅速地跟 随球的运动，因此产生了运动活性的“上升沿”。\n根据我们的发明，视频101的帧序列中的运动活性构成时间序列。 视频帧的色彩直方图是另一个多维时间序列。视频中的时间序列数据 也可以包含例如语义标记(例如，MPEG-7描述符)和音频信号的符号 值。\n我们的方法100基于视频的时间序列200测量130低水平特征的 相似表示，例如运动情形中的高、中或低，居主导的蓝、绿或褐色可 以是另一种表示。我们提供了“软”匹配，其中小的差异不会使匹配无 效。如上所述，我们通过数据平滑或限定低水平特征102的阈值来做 到这一点。如果使用了多个特征，该时间序列数据可以进行加权处理。 例如，在最终结果中，可以赋给色彩比运动活性更大的权重。在推断 160期间低水平特征之间的联系是松散的，因此，我们宁愿将我们的 数据挖掘技术分别应用到每个特征中，并通过融合160通过对所选择 的低水平特征102进行视频挖掘而分别得到的聚类数据151，推断出 更高水平的模式161。\n与只寻找具有指定分辨率的相似对的现有技术相反，我们的匹配 寻找140大时间序列(例如从视频获得的时间序列200)中所有时间分辨 率下的所有可能匹配对。\n为了在时间序列S(i)200中挖掘所有的时间模式103，我们需要 具有各种尺寸w的多分辨率窗口：\nw:S(1:w)，S(2:w+1)，...，S(N-w+1:N)。\n应当注意的是，我们不是显式地构建多分辨率窗口w。相反，我 们的窗口w是通过跨距矩阵300进行隐式定义的，我们所做的是求出 这些隐式定义的窗口。这使得我们能够在所有分辨率下求出所有的匹 配。下面将更详细地描述我们的隐式窗口发现技术。\n我们测量130时间序列数据200之间的所有点跨距(point cross-distance)300，以发现140最小距离400，并且因此将该视频101 聚类150。问题是如何求出相似度，其中多分辨率窗口具有不同尺寸。\n如图3所示，我们使用点距矩阵300解决这个问题。尺寸为w的 两个窗口之间的距离301测量如下：\n$D_w(x_i,x_j)=\underset{k=0}{\overset{w-1}{\Sigma }}{(x_{i+k}-x_{j+k})}^2.$\n于是，\nD1(xi，xj)＝(xi+k-xj+k)2，并且\n$D_w(x_i,x_j)=\underset{k=0}{\overset{w-1}{\Sigma }}{D}_1(x_{i+k},x_{j+k})---\left(1\right)$\n图3示出的是点距矩阵300的例子，其中一个窗口301是xi-xi+w， 另一个窗口302是xj-xj+w。线301表示方程(1)。曲线311和312分 别表示时间序列200。即，同一时间序列是沿x轴和y轴，换句话说， 测量是自相关的。\n点距矩阵300可以被搜索以得到点跨距较短的对角线。在图3的 表示中，按灰度级对距离进行着色(render)，其中较短的距离比较长 的距离更亮一些，因此，所有距离是0的主对角线是白的，因为测量 是自相关的。\n作为一个优点，矩阵300不限于任何给定的窗口尺寸w。因此， 可以求出具有短距离值的所有可能路径，其中短是针对某个阈值距离 值TD而言的。如果使用时间翘曲(time warping)，路径能够“接近”或 基本斜至图3的主对角线。\n如图4所示，我们通过使用适于我们的视频内容挖掘的多定标 (multi-scale)技术(例如小波)对时间序列进行子抽样来进行多分辨率分 析。这产生平滑矩阵400。我们的方法自动地在不同窗口尺寸w上进 行匹配，以揭示出时间序列中所有重复的时间模式401-402。\n动态时间翘曲(DTW)用于在一定的限度内“伸展”和“压缩”时 间，以允许具有不同时间长度的视频的相似分段之间具有良好对准。 就分段来说，我们的意思是指帧序列。动态规划可以用于求出提供最 佳匹配的分段的时间翘曲。DTW求出一定约束条件\n(i，j)，1≤I≤N，1≤j≤M\n下的栅格中的最佳路径，其中N和M是两个分段的长度，每个栅格 点(i，j)分别是两个分段的第i点和第j点之间的距离。\n我们使用动态规划求出点跨距矩阵中的点对之间的最小成本路 径。希望路径基本上对角，即基本上与主对角线310平行。此外，我 们希望路径通过矩阵中的低跨距值，其中低由某个阈值TD来定义。在 图3和4中，这些路径是白的，或准白的对角曲线分段。\n最小成本的可能定义是沿该路径的跨距值的平均值。我们也对允 许的路径提出某些约束，即路径500保持对角方向的取向，见图5。 一种可能的约束集合是沿着路径的每一步可以是下移一步、右移一步， 或对角移动一步，如图所示。\n此外，如图6所示，对角线与路径两个端点间的连线之间的阈值 角应当小于α°，其中0≤α≤45°。这样的路径成本准则和约束可以通过 动态规划来表达，以求出点跨距矩阵中两点之间的最小成本有效路径。\n即使不是精确对角的，那些获得的有效路径仍然指定时间序列中 两个相应子序列的动态时间翘曲。因此，我们使用动态规划求出两个 子序列之间的良好匹配的适当时间翘曲，并且求出跨距矩阵中两点之 间的最小成本路径。\n动态规划允许我们求出矩阵中两个给定点之间的最小成本路径。 我们感兴趣的是求出矩阵中所有可能点对之间的最小成本路径，并选 出成本低于给定阈值的路径。\n做到这一点的强力方式(brute force way)是针对每个可能的点对 执行动态规划过程。因为跨距矩阵是对称的，即时间序列的第i个样 本和第j个样本之间的距离等于第j个样本和第i个样本之间的距离， 我们只需要处理矩阵的上半部分，其中只有N2/2个点和N4/4个点 对。然而，处理步骤的数量可以减少以增加我们的方法的效率。\n首先，如图6所示，我们要求对角线与通过该路径两端点间的连 线之间的角度小于α°。因此，对于每个点，我们求出到这样的点的最 小成本路径，该点位于与对角线603成+α601度的线和与对角线603 成-α602度的线之间。而且，我们提出路径上所有点应当具有低于 阈值T的值的约束条件。在这种情形下，我们可以对整个矩阵限定阈 值，并且求出只在高于阈值的点集之间的最小成本路径。\n在已经求出所有这样的点之间的最小路径成本之后，我们将端点 彼此接近的较短路径合并成较长路径。我们也合并其中一个是另一个 的超集的路径。我们去掉两端点间的欧几里得距离短于一定长度的路 径。保留的路径集为我们提供多分辨率下视频的所有相似子序列对。\n在现有技术中，进行使用动态时间翘曲(例如，使用动态规划求 出跨距矩阵中的最小成本路径)相似以查询较大时间序列中的给定时 间序列模式，见Park等人“序列数据库中不同长度相似子序列的有效 搜索”，数据工程国际会议(ICDE)，pp.23-32，2000。\n我们的技术也可以用于在语音分析环境中求出两个序列之间的 良好对准，见Sakoe等人的“口语识别的动态规划算法优化”，IEEE Trans.Acoust.，Speech，Signal Process.，ASSP 26，pp.43-49，1978， 并且可用于基因和蛋白质序列分析，见Aach等人的“使用时间翘曲算 法对准基因表达时间序列”，Bioinformatics，17：495-508，2001。 然而，那些方法只求出给定的跨距矩阵中具有给定起始点的一条路径， 相反，我们求出所有的路径。\n在现有技术中，时间序列中子序列的自相似性通常通过使用固定 窗口大小w，并且算出原始序列上移动窗之间的跨距来进行计算，见 Agrawal等人“序列数据库中的有效相似性搜索”，第四届数据组织和 算法基础国际会议论文集，和“计算机科学的讲义注释”，730，Springer Verlag，p.，69-84。\n跨距矩阵的其它现有技术使用具有点图的形式，其中矩阵元素是 1或0，表明恰好匹配或没有匹配。它们已经被用于定量分析并作为可 视工具，见Church等人的“点图：探测数百万行文本和代码的自相似 性的程序”，计算和图形学统计期刊，2(2)：153-174，1993，或用 于沿对角线分割自相似区域，但不自动求出相似子序列对，见Jeffry， “求解主题边界的自动算法”，第32届计算语言学学会年会论文集， 1994。我们的方法可以用于任何这样的应用中。\n哈夫(Hough)变换可以用于将多个短路径合并成曲线。哈夫变 换将矩阵400中特定形状的特征分离出来。由于不能进行特征的简单 分析描述，我们可使用哈夫变换。作为一个优点，哈夫变换容忍特征 边界描述中的差距(gap)，并相对地不受数据中噪声的影响。此外，哈 夫变换对于发现特征的全局描述特别有用，其中解类别的数量不是先 验已知的，正如这里的情形那样。\n我们使用Hough变换的动机在于每个输入距离特征指示出它对 全局一致性模式的贡献。我们通过将特征空间量化为有限区间或累加 器单元来实现Hough变换，其中随着这条路径上的累加器单元的递 加，累加器单元显示出离散化的路径。累加器阵列的结果峰强有力地 表示出特征空间中存在相应路径的证据。我们使用Hough变换识别出 最佳拟合一组给定的边的路径。\n当然，应当理解的是，可以利用使用时间序列的自相关性寻找匹 配分段的其它技术。例如，可以使用点积(dot product)的技术。在这 种情形中，该积的大小表明相似程度。对于例如连续帧的色彩直方图 的多维时间序列，可以使用直方图交会法(histogram intersection)。\n使用DTW求出匹配窗口之后，我们将相似分段分组并标记150 成聚类151。对于分段，我们的意思是指视频中直接对应于具有相似 特征的窗口的帧序列。因此，使用时间序列数据对相似分段的识别基 本上允许我们将该视频进行划分并将相似的分段分组成聚类。\n我们同等使用术语“标记”和“项”，如上述针对关联所定义的那 样。当我们称之为聚类时，我们的意思是指聚类经过了标记，例如， 高运动活性的帧的聚类，或视频声道中噪声很大的聚类。通过使用利 用不同特征所获得的关联和标记152的融合，允许我们推断160聚类 151中的高水平模式。因此这些模式可以用于将视频101盲概括170 成摘要171。概括基本上按照高水平模式161提取视频中所选取的帧。\n在步骤160中，我们求出聚类的标记之间的关联。一种类型的关 联是寻找时间相关的“标记”。相关性可以是同时的，也可以是时间偏 移的，例如许多运动和大噪声表明在娱乐视频中的“动作”事件，或许 多之后接着鼓掌欢迎和欢呼的运动表明在体育视频中的“得分”事件。\n我们发现标记之间的关联如下。每个聚类的标记被认为等价于上 述的“项”。因此，我们产生含有标记Li的出现的条件和含有标记Lj 的出现的结果。在这种情形下，时间轴上的每个点具有相应的事务， 它含有与多于一个视频特征102相对应的标记。\n例如，我们能够拥有两组标记，第一组与高、中、低的运动活性 的描述相对应，第二组与音频语义类别有关，其中标记将表明例如观 众掌声、欢呼声、音乐等等的音频类别中的成员关系。于是，我们能 够发现在体育视频中高运动活性和观众掌声/欢呼声之间的关联。应 当注意的是，即使使用了更复杂的标记，仍然能够通过直接计算求出 这种关联。也可求出标记组合之间的复合关联。\n因此，强关联可以帮助我们发现视频101中相应的常见和非常见 模式，因为模式越常见，支持度就越高。\n因此，视频101的摘要171含有常见和非常见事件的组合，这取 决于用户的需要。在一个极端的例子中，摘要171含有具有强关联的 稀有事件。在另一个极端的例子中，摘要含有具有强关联的常见事件。\n因此，聚类150通过基于上述的距离度量将所有相似分段聚类来 开始。对部分重叠的分段进行划分，使得它们或者具有同样的重叠， 或者完全不重叠。聚类对可以使用凝聚过程进行合并以形成更大的聚 类。我们定义集合S含有至少一个相似聚类对中的所有分段。于是， 集合SC∪S是整个视频101，集合SC是集合S的补集。对聚类进行标 记，例如A，B，C，...，且A ∪B∪C...＝S。集合SC可以被认为是“废 弃”的聚类，即对于A、B和C等等不是“有意义的”。\n因此，聚类150产生各种长度和各种相互距离的非重叠分段的集 合S。每个聚类151具有下列相关参数：聚类的紧密性，即聚类中分 段的相似程度；聚类中分段的数目；聚类中分段的总长度(帧或时间)； 分段的最接近点之间的平均距离(表明整个视频中分段的散布)。\n聚类中每个分段具有下列参数：到其它聚类中心的平均距离，它 表明分段在包含其的聚类中的代表性；及其长度(帧或时间)。\n因此，概括成本函数C172可以在所需要的摘要长度，待包含在 摘要171中的所选分段的集合R的总长度，(即，)，S中每个 分段和R中最靠近分段之间的平均距离之间折衷一个绝对差。这表明 集合R(概括171)表示集合S的适合程度，当然集合S是整个视频 101。我们可以增加一个项以在时间上支持R的紧密性，或者相反。 因此摘要171是集合S的子集R，其使成本函数172最小化。\n于是摘要可以用于例如“智能”快进和倒退的视频控制的新特征， 以及在面临没有任何先验域知识时进行的即刻重新定位。\n应当明白，可以在本发明的宗旨和范围内对其进行各种其它的调 整和修正。因此，附加的权利要求的目的是涵盖本发明的真正宗旨和 范围内的所有这样的变化和修正。