一种新闻视频故事单元关联方法

摘要

本发明公开了一种新闻视频故事单元关联方法，目的是提供一种关联故事单元的方法，提高基于局部关键点的相似关键帧识别速度和准确性。技术方案是先对采集的待处理新闻视频进行预处理，按照时间选择策略构建子数据库，去除播音员镜头，并进行关键帧的场景分类；然后利用高斯差分DOG局部关键点探测方法和SIFT特征描述方法探测和描述局部关键点，得到局部关键点集；再采用层次过滤方法进行相似关键帧识别，得到相似关键帧；最后对故事单元之间的关联关系进行判断，得到子数据库中和不同子数据库之间的故事单元之间的关联关系。采用本发明能够提高识别的准确性和速度，满足用户对新闻视频数据的跟踪、组织和检索的需求。

说明书

技术领域

本发明涉及多媒体信息处理技术领域关于新闻视频故事单元的关联方法，其实质是一种故事单元之间的相似关键帧识别与关联的方法，是一种能够适应多种不同来源、不同语种的新闻视频处理方法。

背景技术

随着信息技术和网络技术的快速发展，新闻视频的来源日益广泛，数量日益庞大，获取更加便捷。每时每刻都有大量来自不同国家、不同语种、不同电视台以及不同新闻网站的大量新闻视频。为方便用户随时访问自己需要的新闻信息，有必要对新闻视频进行处理、组织和标注，目前这些处理都完全依靠人工，是一项非常耗时的工作。同时，作为一种公开的情报信息来源，各国都把新闻视频的采集、处理作为获得政治、经济、军事、外交等各方面信息的一种重要手段。因此，针对新闻视频开展相关研究对于多媒体信息的组织、检索以及情报工作都具有非常重要的意义。

新闻是已经发生和正在发生的有价值事件的及时报道，新闻为用户提供的各种信息与其报道的事件内容密切相关，因此如何根据新闻事件对新闻视频数据进行有效的组织成为一个亟待研究的问题。目前按照新闻事件组织信息的方法绝大部分基于文本数据。与纯文本新闻报导相比，新闻视频除解说词外，还包括视频和音频轨迹，能够提供非常广泛的信息。当前研究通常把新闻视频结构层次化为帧-镜头-故事，其中帧与镜头主要表示事件的局部内容，单独的帧和镜头只能提供有限的语义信息；与之相比，故事单元是一个事件的完整报道，能够提供关于事件的各种语义信息，因此围绕故事单元开展新闻视频研究不仅可在语义事件的层次上实现对新闻视频的组织和管理，也可获取故事单元及其所包含的帧和镜头的各种信息，更加贴近实际应用中用户的各种需求。相关研究包括两个方面：一是故事单元的分割，二是故事单元按照新闻报道事件的关联组织。其中第一个方面目前开展的研究较多，技术也相对比较成熟。

对于第二个方面的研究，一部分研究对新闻视频进行自动语音识别，从纯文本的角度实现相似度分析。然而，对多语种视频进行语音识别、机器翻译等处理时面临一些实际问题，得到的文本语义信息可能模糊不清，甚至很难得到有价值的文本信息，因此这种方法存在很大的局限性。故事在视觉上可以看作是一组关键帧序列。在新闻视频的编辑过程中，对相同事件进行报道的故事通常包含重复或者近似的场景和对象。因此视觉特征的相似度计算成为解决问题的一种可行方法。早期部分视频检索研究使用镜头的视觉相似性来进行相似度衡量。然而基于全局特征(如：HSV颜色特征)的相似度分析方法对于分析不同来源、不同语种、不同时间的镜头相似性易于受到光照、编辑方式等各种因素的干扰。研究基于相似关键帧识别方法的故事关联研究成为当前国际研究的一个新的热点问题。故事单元关联的核心问题是相似关键帧的识别和匹配问题。其中最为相关的是香港城市大学和新加坡国立大学开展的研究，这些研究直接利用了尺度不变特征转换(Scale Invariant Feature Transform，SIFT)局部特征描述和匹配的算法，在一个静态数据库中，通过时间分割、特征聚类等操作和索引方法实现匹配速度的提高。在相似关键帧的匹配和识别过程中，首先提出了基于关键点对称性的一一对称关键点匹配方法来过滤错误匹配的关键点，这种方法虽然可以消除部分错误的匹配点，在一定程度提高分析准确率，但是在相似关键帧的识别时需要对两幅关键帧中所有关键点依次进行对称的两次遍历和匹配，增加了识别的时间；为提高相似关键帧识别的效率，在进行匹配时需要将两幅关键帧在水平和垂直方向分别进行比较，并将匹配信息进行融合分析，增加了匹配的时间，虽然可以提高识别效率，但是明显增加了处理时间。

因此这一系列研究面临图像匹配中的一些典型限制：分析速度仍然较慢，尤其是对于大容量的视频数据库来说速度限制更加明显。影响速度的原因主要有两个：(1)视频库的关键帧数量巨大，要在整个库中进行相似关键帧探测是一项费时的任务；(2)关键帧的局部关键点数量庞大，在关键帧之间进行局部关键点的一一匹配需要耗费大量时间。此外，当前国际上开展的相关研究大多直接利用了图像匹配的方法，针对新闻视频故事单元关联的特殊性开展相应研究。故事单元关联研究的特定要求有：

(1)对于故事单元关联分析而言，NDK探测的准确率是一个非常重要的问题。如果准确率不能满足要求，关联分析的结果将非常混乱。这与当前部分新闻视频检索研究中的NDK检索方法有本质的区别。

(2)索引等加速方法对于静态数据库非常有效，但是面对实际应用中动态变化的新闻视频数据库，反复建立索引是一项复杂费时的工作。虽然目前研究中采用的索引等方法可以加快数据读取的速度，但是没有在本质上解决图像匹配分析的速度问题。

(3)新闻视频中相同节目和电视台的播音员镜头中存在大量的相似关键帧，而它们对分析新闻故事的相似性没有明显的帮助。

(4)研究中被广泛应用的相似关键帧的传递性原则并不总是成立。同样，相关联的新闻视频故事单元之间可能并没有出现相似关键帧，需要有更加严格的方法来辅助。

目前国内相关研究尚处于起步探索阶段。

现有的新闻视频故事单元关联研究还不能有效满足辅助用户跟踪、组织和检索新闻事件的需要，研究一种快速有效的新闻视频故事单元关联方法尤为重要。

发明内容

本发明要解决的技术问题是提供一种在动态采集的新闻视频数据中快速、有效关联故事单元的方法，实现对视频中的新闻故事单元按照报道的新闻事件进行自动分组，提高基于局部关键点的相似关键帧识别速度和准确性，满足用户对新闻视频数据的跟踪、组织和检索的需求。

本发明的具体技术方案是：

第一步，对采集的待处理新闻视频进行预处理，即利用现有新闻视频结构分析方法提取新闻视频的镜头结构、故事单元结构和关键帧特征，并将相关信息存储到已有的视频数据库中。

第二步，按照时间选择策略在视频数据库中确定需要的视频数据，将这些视频数据与经过第一步预处理的视频数据一起构建成一个进行相似关键帧识别的子数据库，去除子数据库中播音员镜头，并进行关键帧的场景分类以进一步对数据进行分组，从而减少每次处理的关键帧数量，实现对处理速度的提高。

具体方法是：

2.1、按照时间选择策略构建子数据库。

时间选择策略为：若待处理视频与数据库中数据相比，时间是最新，则选择该时间点(日期)之前T天，T为自然数(实验证明T＝7具有最佳效果，如果全部数据的时间覆盖范围小于7天，则选择全部数据)的数据构建子数据库；若待处理视频与数据库中数据相比，时间不是最新的，则以该时间点为中心，按照实际情况，选择前后延续T天(例如：前3天后3天，前4天后2天等)的视频数据构建子数据库。

2.2、在子数据库中去除播音员镜头。方法是：

首先利用OpenCV算法探测视频关键帧中的人脸，记录人脸的位置和大小信息，然后基于这些特征对出现人脸的视频关键帧进行聚类处理。具体方法如下：

2.2.1设一段视频中探测到人脸的镜头代表帧集合为S＝{k₀，k₁，...，k_n-1}，k_i为镜头关键帧，n表示代表帧数量，是一个大于1的自然数，定义关键帧k_i和关键帧k_j的人脸属性之间的距离为d_ij，

d_ij＝D(k_i，k_j)＝1-Sim(k_i，k_j)    (1)

其中，0≤i，j≤n-1，Sim(k_i，k_j)表示关键帧k_i和关键帧k_j人脸位置和大小属性之间的相似程度，计算如下：

$\mathrm{Sim}(k_i,k_j)=\left(\begin{array}{ccc}\psi & \mathrm{if}& \psi <=1\\ 1/\psi & \mathrm{if}& \psi >1\end{array}\right)---\left(2\right)$

ψ＝[size(fk_i)/size(fk_j)+px(fk_i)/px(fk_j)+py(fk_i)/py(fk_j)]/3    (3)

上式中，size(fk_i)表示关键帧k_i中人脸区域的大小，size(fk_j)表示关键帧k_j中人脸区域的大小，px(fk_i)表示关键帧k_i中人脸区域水平方向坐标，px(fk_j)表示关键帧k_j中人脸区域水平方向坐标，py(fk_i)表示关键帧k_i中人脸区域垂直方向坐标，py(fk_j)表示关键帧k_j中人脸区域垂直方向坐标。

利用公式(1)计算所有探测到人脸的关键帧之间人脸属性的距离，得到距离矩阵Δ＝[d_ij|0≤i，j＜n]。该距离矩阵为一个对角线值为0的对称矩阵。为减少存储空间，采用一维数组存储上三角矩阵的值，数组元素个数减少一半。

2.2.2对关键帧之间的属性距离进行阈值聚类，即对于给定的阈值α，(α的取值范围为[0，1]，实验证明α＝0.1时具有最佳结果)，若d_ij＜α，则代表关键帧k_i和关键帧k_j属于同一类，这样把镜头代表帧集S分为若干个类。播音员镜头因为具有相似属性，被分入其中的一类，然而，包含播音员镜头的分类中也可能包括少量其它镜头的关键帧，需要进一步获得准确的播音员镜头。因为一段视频中播音员通常衣着和局部背景相同，通过局部区域的颜色特征提取可以获得准确的播音员镜头。

2.2.3基于人物和人物边缘区域颜色进行特征提取，方法是：

2.2.3.1将每个镜头代表帧k_i分割为e小块(实验证明e＝6×6时在效率和时间上获得最优化结果)，每一小块使用HSV颜色模型的12维直方图表示其视觉特征。

2.2.3.2实验证明播音员镜头中只有一个人脸时，人脸尺寸的大小在e＝36时覆盖了其中的4块，人脸下部临近的4块区域是人物躯干，对这8块区域计算相似度：设聚类处理的结果中某一示例图像为Q₁，Q₁的第m个分块的直方图特征矢量为HQ_1，m(hq₀，hq₁，..，hq₁₁)，聚类中的某一图像为Q₂，Q₂对应第m个分块的直方图特征矢量为HQ_2，m(hs₀，hs₁，...，hs₁₁)，其中，0≤hq_1，t≤1，0≤hq_2，t≤1(t∈[0，1，…，11])为归一化的比例值。利用直方图交算法对Q₁和Q₂进行局部颜色相似性度量：

$\mathrm{Sim}(Q_1,Q_2)=\underset{m=1}{\overset{8}{\Sigma }}\mathrm{sim}({\mathrm{HQ}}_{1,m},{\mathrm{HQ}}_{2,m})/8=\underset{m=1}{\overset{8}{\Sigma }}\left(\underset{t=0}{\overset{11}{\Sigma }}\min ({\mathrm{hq}}_{1,i},{\mathrm{hs}}_{2,i})\right)/8---\left(4\right)$

公式(4)中m∈[1，2，…，8]，表示对应的8个分块。

当播音员镜头中出现两个人脸时，每个人脸尺寸的大小在e＝36时覆盖了2个分块，人脸下部临近的1块区域是人物躯干，对这3块区域利用直方图交算法计算局部颜色相似度，其中每个人脸的相似度计算如下：

$\mathrm{Sim}(Q_1,Q_2)=\underset{m=1}{\overset{3}{\Sigma }}\mathrm{sim}({\mathrm{HQ}}_{1,m},{\mathrm{HQ}}_{2,m})/3=\underset{m=1}{\overset{3}{\Sigma }}\left(\underset{i=0}{\overset{11}{\Sigma }}\min ({\mathrm{hq}}_{1,i},{\mathrm{hs}}_{2,i})\right)/3---\left(5\right)$

公式(5)中m∈[1，2，3]，表示对应的3个分块。

2.2.3.3对于不同的情况，分别利用公式(4)和(5)，对于基于阈值聚类处理所得每一个类型，基于人物和人物边缘背景的区域的HSV颜色特征按照局部颜色距离进行阈值聚类，将各个类型分成更小的的子类。

2.2.3.4一段视频中播音员镜头数量较多，分布相对均匀，故对通过局部颜色相似性分析所得的子类选择包含镜头数量大于3的子类，方法是选择同时满足以下三个条件的包括播音员镜头的子类：(1)子类中镜头总时间长度之和最长；(2)子类中镜头的时间分布比较均匀；(3)子类中镜头之间最大时间跨度覆盖视频的始末。

2.2.3.5子数据库中包括的播音员镜头对于故事单元关联没有帮助，因此将播音员镜头的关键帧从子数据库中去除。

2.3、对子数据库中的新闻播报关键帧进行场景分类，并设定匹配分析关键帧的类型选择规则。

除播音员镜头之外，包含人脸的镜头可以再分成两类：新闻评论员和新闻人物。在播音员镜头探测时，已经对关键帧进行e＝6×6的分块，完成了人脸探测，并获得了人脸属性，因此直接利用这些信息，利用人脸位置上的显著差异来分类：人脸位置处于最左侧或最右侧两列分块中的作为新闻评论员类型，人脸出现在其他位置的作为新闻人物类型。

这样可以将新闻播报中的视频关键帧分类为：新闻评论员、新闻人物、事件场景三种类型。新闻评论员类型的关键帧通常是对事件场景的关键帧进行编辑所得，与相关事件的场景关键帧之间具有很强的局部相似性，可以将这种类型的关键帧作为一种特殊的事件场景信息，与事件场景类型的关键帧一起进行识别来发现内在联系。新闻人物类型在一定的时间区间内即使是相同人物也可能对应于多个新闻事件，因此这种类型的关键帧作为一个单独的识别类型，只对同属这种类型的关键帧进行识别处理，其识别结果不作为关联分析的依据。

完成上述分类之后，设定关键帧匹配分析类型选择的规则为：属于新闻人物类型的关键帧只与新闻人物类型的关键帧进行匹配；新闻评论员类型与事件场景类型的关键帧可以相互匹配。

这样不仅可以减少每次分析的关键帧数量，还减少了对故事单元关联分析结果的影响。

对子数据库中的关键帧进行场景分类，并设定匹配分析的规则，可以提高相似关键帧识别的时间效率。

第三步，利用高斯差分(Difference of Gaussian，DOG)局部关键点探测方法和SIFT特征描述方法探测和描述局部关键点，得到局部关键点集。为提高关键帧匹配分析的速度，可以做以下处理：当局部关键点集中局部关键点的个数大于N时对局部关键点集进行精减，精减方法是对局部关键点集按对比度进行排序，选择对比度最高的前N个关键点。N为自然数，实验证明N＝100时在速度和准确率之间取得最佳平衡。

第四步，采用层次过滤方法进行相似关键帧识别，得到相似关键帧。

具体方法为：

4.1、通过“熵”进行第一层过滤，获取相似关键帧候选集。

4.1.1依次对一幅关键帧中的每一个局部关键点与另一幅关键帧所有局部关键点进行匹配计算，得到关键帧之间所有的匹配关键点。具体方法为：

计算关键帧k₁中的局部关键点A与关键帧k₂中所有局部关键点之间的SIFT特征的距离，计算最小距离和次小距离之间的比率，当关键帧k₂中的局部关键点A′与k₁中的局部关键点A之间最小距离和次小距离的比率小于一个阈值β(实验证明β＝0.75时最佳)时，则判定关键帧k₁中的局部关键点A与关键帧k₂中的最小距离点A′为匹配点。

4.1.2计算关键帧之间的匹配点的连接线(也叫匹配线)AA′与垂直轴h之间的夹角θ，建立角度直方图。方法是：

将关键帧k₁和关键帧k₂中的匹配点A和A′的坐标分别记为：(x₀，y₀)和(x₁，y₁)，则夹角计算如下：

$\theta =\arccos \left(\frac{y_1-y_0}{\sqrt{{(x_1+w-x_0)}^2+{(y_1-y_0)}^2}}\right)---\left(6\right)$

w为关键帧的像素宽度(w取值与视频采集分辨率设置有关，若采集的视频关键帧分辨率为240×320，则w＝320)，θ的范围为(0°，180°)。

4.1.3将0至180度的角度范围进行分划，建立角度直方图(实验证明在0至180度之间每5度作为一个单位分划，将整个区间量化为36维的直方图效果最佳)。将通过公式(6)计算得到的所有匹配线的角度θ投影到直方图中进行相似关键帧候选集判断。

令P＝[p₁，p₂，…，p_z]，其中1≤z≤36，p_u是直方图中各个非空的维度。Num(P)为全部匹配线的数量，Num(p_u)为各个维度内的匹配线数量，且Num(p_u)≥1，MaxNum为Num(p_u)的最大值，1≤u≤36。采用如下流程进行相似关键帧候选集判断：

4.1.3.1如果Num(P)小于阈值η(实验证明η＝3最佳)，则将匹配关键帧识别为不相似关键帧；否则，执行步骤4.1.2。

4.1.3.2为消除相似关键帧匹配中的噪声干扰，采用如下方法：对各非空的维度，求Num(P_u)与Maxnum的商D：

$D=\frac{\mathrm{Num}\left(p_u\right)}{\mathrm{MaxNum}}---\left(7\right)$

因为噪声点数量很少，因此如果D小于设定的阈值γ(实验证明γ＝0.1)，则判定维度中包含的匹配线为噪声干扰，对判断为噪声的维度进行过滤，即将直方图中该维度的值修改为零，即首先令Num(P)＝Num(P)-Num(P_i)，然后令Num(p_i)＝0。

4.1.3.3如果非空的维度数大于1，判断数值最大的维度和第二大的维度的分布位置，如果二者位置相邻或者只相差一个维度，则执行步骤4.1.3.4，如果数值最大的维度和第二大的维度的分布位置相差多个维度，则将两幅关键帧判断成不相似关键帧。

4.1.3.4采用“熵”的判别方法对相似关键帧候选集进行识别，方法是：

模式熵定义为：

$\mathrm{PE}=-\underset{u=1}{\overset{z}{\Sigma }}\frac{\mathrm{Num}\left(p_u\right)}{\mathrm{Num}\left(P\right)}\times \log \left(\frac{\mathrm{Num}\left(p_u\right)}{\mathrm{Num}\left(P\right)}\right)---\left(8\right)$

模式熵PE的值分布在区间[0，1]上，两种极端的情况为：PE为0时，表示P包含唯一子集，所有匹配线近似平行；当PE为1时，表示匹配线均匀分布在P子集中。因此设定阈值λ(λ可能的取值范围为(0，0.5)，实验证明λ＝0.05时最佳)，若PE＜λ，判定k₁和k₂为相似关键帧候选对象，反之为不相似关键帧。

通过第一层过滤处理所得的相似关键帧候选集中可能有部分的误判，为去除这些误判的关键帧，需要对相似关键帧候选集执行第二层过滤处理。

4.2对相似关键帧候选集基于对称性匹配进行第二层过滤，获得最终相似关键帧。过滤方法如下：

如果按照k₁到k₂的顺序进行相似关键帧匹配后，判断k₁和k₂是一对相似关键帧候选对象，则按照k₂到k₁的顺序进行相似关键帧匹配，如果判断结果为k₂和k₁也是相似关键帧，则k₁和k₂是一对可信的相似关键帧；如果判断结果为k₂和k₁不是相似关键帧，则k₁和k₂是不相似的关键帧。

第五步，对故事单元之间的关联关系进行判断，方法如下：

5.1、对子数据库中的故事单元之间关联关系进行判断：

5.1.1在一个子数据库内，依次对所有的故事单元两两进行判断，看是否出现相似关键帧，若两个故事单元之间出现相似关键帧，则判定这样的故事单元之间具有直接关联关系。完成上述处理之后，对于没有出现相似关键帧的故事单元，则转5.1.2

5.1.2在一个子数据库内，对于没有直接关联关系的故事单元，利用故事单元关联关系的传递性判断是否存在关联，如果存在关联关系，则判定故事单元之间存在间接的关联关系。故事单元关联关系的传递性定义如下：

对于两对故事单元(S₁，S₂)和(S₂，S₃)，如果S₁和S₂是具有关联关系的故事单元，S₂和S₃是具有关联关系的故事单元，则可以推断S₁和S₃也是具有关联关系的故事单元。

5.2、对时间相邻的不同子数据库之间的故事单元的关联关系进行判断，方法如下：

子数据库按照时间选择策略来构建，因此相邻的子数据库在时间区间上具有重叠性，使得子数据库之间存在共有的故事单元，这些故事单元是子数据库之间的交集，交集中的故事单元与各个子数据库中其它故事单元存在关联关系。因此以交集中故事单元在各个子数据库中的关联关系为依据，利用故事单元关联关系的传递性，对相邻的子数据库中故事单元得到间接的关联关系。循环这个过程直到所有相邻的子数据库之间故事单元关联关系都判断完毕，得到视频数据库中比较完整的故事单元关联结果。

采用本发明可以达到以下技术效果：

1、与当前研究中基于局部关键点匹配的相似关键帧识别方法相比，通过建立子数据库减少了每次处理的视频关键帧数据量，通过第二步精减局部关键点减少了每幅关键帧的数据量，使得进行匹配运算的数据量大大减少，大幅度提高了计算速度。

2、第三步中的层次化过滤方法只需要对候选集中的关键帧进行两次对称的匹配运算即可完成对于匹配点和关键帧匹配结果的识别和过滤处理，而当前研究中匹配点的过滤方法需要对全部关键点进行对称的两次遍历，相似关键帧识别处理则需要对全部关键帧在水平和垂直两个方向分别执行关键帧匹配处理，本发明处理速度有较大提高；通过在哥伦比亚大学数字视频多媒体(Digital video multimedia，DVMM)实验室在Trecvid数据基础上建立的相似图像识别测试数据库中的实验表明，与当前研究相比，本发明提高速度的同时，识别的准确率并未受到影响。

3、因为存在关联关系的故事单元之间可能没有出现相似关键帧，因此本发明的故事单元关联关系的传递性相比背景技术中采用的相似关键帧的传递性在定义上更加严谨，判断的新闻视频故事单元关联关系很准确。

附图说明

图1为背景技术中介绍的相似关键帧示意图。

图2为本发明总体流程图。

图3为第二步关键帧分块和播音员人脸分布示意图。

图4为第四步关键帧匹配模式示意图。

图5为第四步匹配线夹角计算示意图。

图6为第四步关键帧之间局部关键点匹配线角度直方图分布模式示意图。

图7为第四步关键帧对称匹配过滤示意图。

图8为第五步相似关键帧和故事单元之间直接关联关系的示意图。

图9为第五步在一个子数据库中利用故事单元传递性判断间接关联关系示意图。

图10为第五步中相邻子数据库之间故事单元的关联处理示意图。

具体实施方式

图1为背景技术中介绍的相似关键帧示意图，图中(a)的两幅关键帧分别来自BBC和CNN两个不同电视台的新闻视频，描述的是同一个场景的相同事件，但是因为拍摄时间略有不同，在视觉感官上具有一定的差异。图中(b)为不同时间和焦距拍摄所得的关键帧，视觉上具有比较明显的差异，图中(c)为素材重复利用时采用了不同编辑效果导致视觉上出现差异。此图说明了要识别相似关键帧具有一定的难度。

图2为本发明总体流程图，本发明包括以下五个步骤：

第一步，对采集的待处理新闻视频进行预处理，即提取新闻视频的镜头结构、故事单元结构和关键帧特征，并将相关信息存储到已有的视频数据库中；

第二步，按照时间选择策略构建子数据库，去除子数据库中播音员镜头，并进行关键帧的场景分类；

第三步，利用DOG局部关键点探测方法和SIFT特征描述方法探测和描述局部关键点，并对局部关键点进行精减；

第四步，采用层次过滤方法进行相似关键帧识别，先利用信息论中“熵”的方法对关键帧进行过滤，得到相似关键帧候选集，然后利用相似关键帧的对称性对相似关键帧候选集再次进行过滤处理，得到最终的相似关键帧；

第五步，故事单元之间关联关系的判断。在子数据库中通过相似关键帧获得直接关联关系，通过故事单元关联关系的传递性，获得间接关联关系；对不同的子数据库，利用相邻子数据库的交集和故事单元的传递性判断完整数据库中故事单元的关联关系。

图3为第二步关键帧分块和播音员人脸分布示意图，当e＝36时，即关键帧被分割为相等的36块，通过Open CV算法进行人脸探测，记录人脸出现的分块，并进行扩展。当只有一个播音员出现时(如图3(a)和3(b))，不论播音员出现在中央还是两侧，播音员人脸分布在其中的4块，躯干为人脸下方相邻的4块，完整的播音员区域为白色边框包围的8块区域；当出现两个播音员时(如图3(c))，每个播音员的人脸覆盖其中的2块，躯干区域向下方扩展1块，完整的播音员区域为白色边框包围的3块。

图4为第四步关键帧匹配模式示意图。相似关键帧间正确匹配点数量较多，并且正确匹配点之间的匹配线通常具有一定的规律性：近似平行或者呈现规则的放射状，如图4(a)所示；而不相似关键帧之间往往匹配点数量较少，且匹配点之间的连接线分布具有随机性，如图4(b)所示。

图5为第四步匹配线夹角计算示意图。图中将关键帧k₁和关键帧k₂中的匹配点A和A′的坐标分别记为：(x₀，y₀)和(x₁，y₁)，匹配线与垂直轴之间夹角为θ。

图6为图4中不同模式的匹配线在第四步中的匹配线分布模式示意图。在0至180度之间每5度作为一个单位分划，将整个区间量化为36维的直方图。将匹配线与垂直轴之间夹角θ投影到这个36维的直方图之后，图4(a)中相似关键帧的匹配线平行或者近似平行，匹配线角度直方图分布模式如图中6(a)所示，在直方图中匹配线数量较多，并且主要落在一个维度或者相邻的两个维度内；而图4(b)中不相似关键帧匹配线表现为分布的随机性，匹配线角度直方图分布模式如图中6(b)所示，在直方图中匹配线数量较少，且出现更多的、分布比较均匀的非空维度。

图7为第四步关键帧对称匹配过滤示意图。图7(a)、7(b)、7(c)、7(d)中均有一对关键帧。在执行第一层次的过滤之后，匹配线分布模式为图7(a)和7(c)的两种分布情况，这两种情况都被判断为相似关键帧；按照第二层过滤方法执行对称匹配时，图7(a)对称匹配的匹配线分布模式如图7(b)所示仍然保持基本平行，即两次对称匹配的判断结果一致，因此7(a)、7(b)中的关键帧是一对可信的相似关键帧；而7(c)所示的两幅关键帧进行对称匹配时，如图7(d)所示没有得到任何匹配点，即两次对称匹配判断结果不一致，因此7(c)、7(d)的关键帧不是相似关键帧。

图8为视频的故事单元之间利用相似关键帧建立直接关联关系示意图。图8(a)中显示了一个星期内来自BBC和CNN关于“联合国在黎巴嫩的维和行动”不同故事单元，故事单元之间有相似关键帧。图中“故事单元1”(简称S₁)与“故事单元2”(简称S₂)、“故事单元4”(简称S₄)之间分别出现相似关键帧(以不同颜色和黑色箭头标出相似关键帧的联系)，从而可知S₁与S₂具有直接关联关系，S₁与S₄具有直接关联关系。因为S₂与S₄之间没有出现相似关键帧，按照本发明第五步中的5.1.1，此时不能判断S₂与S₄之间是否具有关联关系。S₂与“故事单元3”(简称S₃)之间出现相似关键帧，可以得到S₂与S₃之间具有直接关联关系。因S₃与S₁之间、S₃与S₄之间没有出现相似关键帧，按照本发明第五步中的5.1.1，不能判断S₃与S₁之间、S₃与S₄之间是否具有关联关系。如图8(b)所示，粗的虚线表示了故事单元之间直接的关联关系。

图9为在一个子数据库中利用故事单元传递性判断间接关联关系示意图。图9表示图8中的故事单元之间利用关联关系的传递性判断S₂与S₄、S₃与S₁之间、S₃与S₄之间存在间接的关联关系。这种间接的关联关系图9中使用细的实线表示。按照本发明第五步中的5.1.2，因S₁与S₂、S₁与S₄之间分别具有直接关联关系，虽然S₂与S₄之间没有出现相似关键帧，利用关联关系的传递性仍然可以判断S₂与S₄之间存在间接的关联关系；同样可以判断S₃与S₁之间、S₃与S₄之间存在间接的关联关系。

图10为第四步中不同子数据库之间故事单元的关联处理示意图。新闻视频数据库中时间上邻近的不同子数据库之间因为时间区间的重叠性产生了交集“故事单元6”(简称S₆)，交集中公共的故事单元S₆与不同子数据库中的故事单元“故事单元5”(简称S₅)和“故事单元7”(简称S₇)之间分别具有关联关系，而S₅和S₇分别属于不同的子数据库，利用第五步的5.1.1和5.1.2，不能判断二者是否具有关联关系；因此按照本发明第五步中的5.2，可以获得不同子数据库的故事单元S₅和S₇之间存在间接的关联关系，在不同子数据库之间循环，直到所有相邻的子数据库之间故事单元关联关系都判断完毕，得到完整新闻视频数据库中故事单元的关联处理结果。图中两个椭圆的区域表示按时间建立的两个邻近的子数据库，重叠部分表示交集，虚线表示在子数据库内部故事单元之间的关联关系，实线表示通过关联关系的传递性所得不同子数据库的故事单元之间的间接关联关系。