一种对镜头进行基于内容的视频检索的方法

1、一种对镜头进行基于内容的视频检索的方法，其特征在于该方法包括 以下步骤：
(1)首先对视频数据库进行镜头分割，以镜头作为视频的基本结构单元 和检索单元；
(2)计算两个帧图像之间的相似度，按下面的方法建立模糊相似矩阵R： 当i＝j时，令rij为1；当i≠j时，令rij为xi与yj之间的相似度；
(3)利用传递闭包方法计算模糊相似矩阵R的等价矩阵 计算模糊 相似矩阵R的等价矩阵 的传递闭包方法采用平方法： $R\to R^2{\left(R^2\right)}^2\to ···\to R^{2^k}=\hat{R},$ 它的时间复杂度为O(n3log2n)，如果n值特别大， 势必会影响总的计算时间，所以采用基于图连通分支计算的模糊聚类最佳算 法计算矩阵的合成运算，递推如下：
$r_{\mathrm{ij}}^{\left(0\right)}=r_{\mathrm{ij}}0\le i,j\le n$
$r_{\mathrm{ij}}^{\left(k\right)}=\max \{r_{\mathrm{ij}}^{(k-1)},\min [r_{\mathrm{ik}}^{(k-1)},r_{\mathrm{kj}}^{(k-1)}\left]\right\}0\le i,j\le n;0\le k\le n$
这种算法的时间复杂度T(n)满足O(n)≤T(n)≤O(n2)；
(4)设置阈值λ确定截集，对R矩阵的传递闭包矩阵 进行模糊聚类， 计算 $\left[x\right]=\left\{y\right|\hat{R}(x,y)\ge \lambda \},$ 集合[x]即为模糊聚类的等价类，每个等价类集合中各帧 是相似的，取每个集合中任一帧图像作为关键帧；
对 进行模糊聚类的方法如下：
(a)确定n个样本X＝(X1，...，Xn)上的模糊相似关系R和一个截集阈值α；
(b)将R按下面计算改造为一个等价矩阵
RоR＝R2
R2оR2＝R4
...

直到存在一个k满足 $R^{2^k}=R^{2^{(k+1)}}$
上述式子中，RоR为模糊关系的合成运算，在R是相似矩阵的假设下， 已证明必有这样的k存在，满足k≤log n；
(c)计算集合 $\left[x\right]=\left\{y\right|\hat{R}(x,y)\ge \alpha \},$ [x]即为模糊聚类，算法结束；
对n个样本空间进行模糊聚类分析后，得到等价类，在每个等价类中选 取一个样本作为关键帧，这样两个镜头之间的相似度度量就变为关键帧集合 之间的相似性度量；
(5)用关键帧{ri1，ri2，...，rik}表示镜头si，关键帧集合来度量两个镜头之间的 相似性。
2、如权利要求1所述的一种对镜头进行基于内容的视频检索的方法，其 特征在于：步骤(1)中，对视频数据库进行镜头分割的方法为时空切片算法。
3、如权利要求1所述的一种对镜头进行基于内容的视频检索的方法，其 特征在于：步骤(2)中，计算xi与yj之间的相似度用两个图像直方图的交来 计算：
$\mathrm{Inter}\sec t(x_i,y_j)=\frac{1}{A(x_i,y_j)}\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min \{H_i(h,s,v),H_j(h,s,v)\}$
$A(x_i,y_j)=\min \{\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min H_i(h,s,v),\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_j(h,s,v)\}$
Hi(h，s，v)是HSV颜色空间的直方图，用H，S，V分量在18×3×3的三维空间中 统计直方图，以归一化后的162个数值作为颜色特征值，Intersect(xi，yj)表示两个直 方图的交，用它来判断两个关键帧的相似性，使用A(xi，yj)归一化到0，1之间。
4、如权利要求1或2或3所述的一种对镜头进行基于内容的视频检索的 方法，其特征在于：把镜头si和sj的相似度定义为 $\mathrm{Sim}(s_i,s_j)=\frac{1}{2}\{M(s_i,s_j)+\hat{M}(s_i,s_j)\},$ M表 示关键帧相似的最大值， 表示关键帧相似的第二大值，其中，
$M(s_i,s_j)=\underset{p=\{\mathrm{1,2},...\}}{\max }\underset{q=\{\mathrm{1,2},...\}}{\max }\left\{\mathrm{Inter}\sec t(r_{\mathrm{ip}},r_{\mathrm{jq}})\right\}$
$\hat{M}(s_i,s_j)=\underset{p=\{\mathrm{1,2},...\}}{\hat{\max }}\underset{q=\{\mathrm{1,2},...\}}{\max }\left\{\mathrm{Inter}\sec t(r_{\mathrm{ip}},r_{\mathrm{jq}})\right\}$
$\mathrm{Inter}\sec t(r_i,r_j)=\frac{1}{A(r_i,r_j)}\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min \{H_i(h,s,v),H_j(h,s,v)\}$
$A(r_i,r_j)=\min \{\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min H_i(h,s,v),\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_j(h,s,v)\}.$

技术领域\n本发明属于视频检索技术领域，具体涉及一种对镜头进行基于内容的视 频检索的方法。\n背景技术\n随着在多媒体数据制造、存储与传播方面取得的重大技术进步，数字视 频已经成为人们日常生活中不可或缺的一部分。人们面临的问题不再是缺少 多媒体内容，而是如何在浩如烟海的多媒体世界中找到自己所需要的信息。 从目前来看，传统的基于关键词描述的视频检索因为描述能力有限，主观性强， 手工标注等原因，已经不能满足海量视频检索的需求。为了能够方便人们寻找 多媒体数据，上世纪90年代开始，基于内容的视频分析和检索技术成为研究 的热点问题，多媒体内容描述接口MPEG-7的逐步制定和完善，更加推动了 基于内容的视频检索技术的发展。\n现有技术中，如文献“A New Approach to Retrieval Video by Example Video Clip”[X.M.Liu，Y.T.Zhuang，and Y.H.Pan，ACM Multimedia，pp. 41-44，1999]所述，视频检索的一般方法是首先进行镜头边界检测，以镜头作 为视频序列的基本结构单元和检索单元；然后在每个镜头内部提取关键帧来 代表该镜头的内容，从关键帧提取出颜色和纹理等低级特征，用于镜头的索 引和检索。这样，就把基于内容的镜头检索转化为基于内容的图像检索来解 决。这类方法存在的问题是，镜头是图像在时间上的连续序列，没有对存在 于视频中的时间信息和运动信息充分进行利用。另外在2002年在IEEE Trans. Circuits and Systems for Video Technology发表的文献“An efficient algorithm for video sequence matching using the modified Hausdorff distance and the directed divergence”(该文献作者是s.H.Kim and R.-H.Park，vol.CSVT-12，no.7，页 码592-595)用积累的定向发散(Cumulative Directed Divergence)方法抽取 关键帧，用改进的豪斯多夫距离(Modified Hausdorff Distance)方法得到两 个镜头之间的相似程度，抽取关键帧和定义镜头相似性时使用了YUV颜色 空间直方图。由于抽取关键帧时设定了两个阈值：前后帧相似值的阈值和当 前帧与前一个关键帧之间相似值的阈值，必须同时满足这两个条件才能出现 一个关键帧，这样将会影响关键帧提取的准确性，最终势必会影响查询的正 确性；另外，使用了视频中常用的YUV颜色空间作为视觉特征，它与HSV 颜色空间相比，和人们的视觉感知并不大一致。\n发明内容\n针对现有的镜头检索方法所存在的缺陷，本发明的目的是提出一种对镜 头进行基于内容的视频检索的方法，该方法能在现有技术的基础上大大提高 基于内容的镜头检索的准确率，同时保持很快的检索速度，从而更加充分地 发挥镜头检索技术在当今网络信息社会中的巨大作用。\n本发明的目的是这样实现的：一种对镜头进行基于内容的视频检索的方 法，包括以下步骤：\n(1)首先对视频数据库进行镜头分割，以镜头作为视频的基本结构单元 和检索单元；\n(2)计算两个帧图像之间的相似度，按下面的方法建立模糊相似矩阵R： 当i＝j时，令rij为1；当i≠j时，令rij为xi与yj之间的相似度；\n(3)利用传递闭包方法计算模糊相似矩阵R的等价矩阵\n(4)设置阈值λ确定截集，对R矩阵的传递闭包矩阵 进行模糊聚类， 计算 $\left[x\right]=\left\{y\right|\hat{R}(x,y)\ge \lambda \},$ 集合[x]即为模糊聚类的等价类，每个等价类集合中各帧 是相似的，所以我们可以取每个集合中任一帧作为关键帧；\n(5)用关键帧{ri1，ri2，...，rik}表示镜头si，用关键帧集合来度量两个镜头之间的 相似性。\n进一步来说，步骤(1)中对视频数据库进行镜头分割的方法最好为时空 切片算法。步骤(2)中计算xi与yj之间的相似度可以用两个图像直方图的交 来计算：\n$\mathrm{Inter}\sec t(x_i,x_j)=\frac{1}{A(x_i,x_j)}\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min \{H_i(h,s,v),H_j(h,s,v)\}$\n$A(x_j,y_j)=\min \{\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_i(h,s,v),\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_j(h,s,v)\}$\nHi(h，s，v)是HSV颜色空间的直方图，我们用H，S，V分量在18×3×3的三维 空间中统计直方图，以归一化后的162个数值作为颜色特征值，Intersect(xi，yj)表 示两个直方图的交，用它来判断两个关键帧的相似性，使用A(xi，yj)归一化到 0，1之间。\n再进一步，步骤(3)中，计算模糊相似矩阵R的等价矩阵 的传递闭包 方法可采用平方法： $R\to R^2\to {\left(R^2\right)}^2\to ···\to R^{2^k}=\hat{R},$ 它的时间复杂度为O(n3log2n)， 如果n值特别大，势必会影响总的计算时间，所以采用基于图连通分支计算的 模糊聚类最佳算法计算矩阵的合成运算，递推如下：\n$r_{\mathrm{ij}}^{\left(0\right)}=r_{\mathrm{ij}}$ 0≤i，j≤n\n$r_{\mathrm{ij}}^{\left(k\right)}=\max \{r_{\mathrm{ij}}^{(k-1)},\min [r_{\mathrm{ik}}^{(k-1)},r_{\mathrm{kj}}^{(k-1)}\left]\right\}$ 0≤i，j≤n；0≤k≤n\n这种算法的时间复杂度T(n)满足O(n)≤T(n)≤O(n2)。\n为了更好地实现本发明的目的，在进行镜头检索时，对 进行模糊聚类 的方法如下：\n(1)确定n个样本X＝(X1，...，Xn)上的模糊相似关系R和一个截集闽值α；\n(2)将R按下面计算改造为一个等价矩阵；\nRοR＝R2\nR2οR2＝R4\n...\n\n直到存在一个k满足 $R^{2^k}=R^{2^{(k+1)}}$\n上述式子中，RοR为模糊关系的合成运算，在R是相似矩阵的假设下， 已证明必有这样的k存在，满足k≤log n；\n(3)计算集合 $\left[x\right]=\left\{y\right|\hat{R}(x,y)\ge \alpha \},$ [x]即为模糊聚类，算法结束；\n对n个样本空间进行模糊聚类分析后，得到若干个等价类，在每个等价 类中选取一个样本作为关键帧。这样两个镜头之间的相似度度量就变为关键 帧集合之间的相似性度量。\n在本方法的步骤(5)中，可以把镜头si和sj的相似度定义为 $\mathrm{Sim}(s_i,s_j)=\frac{1}{2}\{M(s_i,s_j)+\hat{M}(s_i,s_j)\},$ M表示关键帧相似的最大值， 表示关键帧相似的第二 大值，其中，\n$M(s_i,s_j)=\underset{p=\{\mathrm{1,2},...\}}{\max }\underset{q=\{\mathrm{1,2},...\}}{\max }\left\{\mathrm{Inter}\sec t(r_{\mathrm{ip}},r_{\mathrm{jq}})\right\}$\n$\hat{M}(s_i,s_j)=\underset{p=\{\mathrm{1,2},...\}}{\overset{^}{\max }}\underset{q=\{\mathrm{1,2},...\}}{\max }\left\{\mathrm{Inter}\sec t(r_{\mathrm{ip}},r_{\mathrm{jq}})\right\}$\n$\mathrm{Inter}\sec t(r_i,r_j)=\frac{1}{A(r_i,r_j)}\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min \{H_i(h,s,v),H_j(h,s,v)\}$\n$A(r_i,r_j)=\min \{\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_i(h,s,v),\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_j(h,s,v)\}.$\n本发明的效果在于：采用本发明所述的对镜头进行基于内容的视频检索 的方法，可以取得更高的准确率，同时保持很快的检索速度。\n本发明之所以具有如此显著的技术效果，其原因在于：运用模糊聚类分 析的方法，把镜头内容划分为多个等价类，这些等价类很好的描述了镜头内 容的变化，而镜头之间的相似性则表现为关键帧结合之间的相似性。镜头之 间相似性度量考虑了使用HSV颜色直方图表示关键帧的缺点：如果两个关键 帧有相似的颜色分布，即使它们的内容不一样，也会认为这两个关键帧相似。 因此使用最大相似值和第二大相似值的平均值来加强算法的鲁棒性。对比实 验结果证实了本发明提出方法的有效性。\n附图说明\n图1是对镜头进行基于内容的视频检索的方法的流程示意图；\n图2是实验对比中镜头检索的7个语义类例子示意图；\n图3是本发明的方法对游泳镜头的检索结果示意图。\n具体实施方式\n图1是本发明的总体框架，是本发明中各步方法的流程示意图。如图1 所示，一种基于模糊聚类分析的镜头检索方法，包括以下步骤：\n1、镜头分割\n首先使用时空切片算法(spatio-temporal slice)，对视频数据库进 行镜头分割，以镜头作为视频的基本结构单元和检索单元，关于时空切片算 法的详细描述可以参考文献“Video Partitioning by Temporal Slice Coherency” [C.W.Ngo，T.C.Pong，and R.T.Chin，IEEE Transactions on Circuits and Systems for Video Technology，Vol.11，No.8，pp.941-953，August，2001]。\n2、建立模糊相似矩阵R\n建立镜头内部图像之间的建立模糊相似矩阵R方法如下：当i＝j时，令 rij为1，当i≠j时，令rij为xi与yj之间的相似度，相似度则采用如下方法来 计算：\n$\begin{array}{c}\mathrm{Inter}\sec t(x_i,y_j)=\frac{1}{A(x_i,y_j)}\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min \{H_i(h,s,v),H_j(h,s,v)\}\\ A(x_i,y_j)=\min \{\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_i(h,s,v),\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_j(h,s,v)\}\end{array}$\nHi(h，s，v)是HSV颜色空间的直方图，我们用H，S，V分量在18×3×3的三维 空间中统计直方图，以归一化后的162个数值作为颜色特征值。Intersect(xi，yj)表 示两个直方图的交，用它来判断两个关键帧的相似性，使用A(xi，yj)归一化到 0，1之间。\n3、求相似矩阵R的传递闭包，得到等价矩阵\n本实施例中，求相似矩阵的传递闭包采用平方法：\n$R\to R^2\to {\left(R^2\right)}^2\to ···\to R^{2^k}=\hat{R}$\n它的时间复杂度为O(n3log2n)，如果n值特别大，势必会影响总的计算时 间。所以采用基于图连通分支计算的模糊聚类最佳算法计算矩阵的合成运算， 递推如下：\n$r_{\mathrm{ij}}^{\left(0\right)}=r_{\mathrm{ij}}$ 0≤i，j≤n\n$r_{\mathrm{ij}}^{\left(k\right)}=\max \{r_{\mathrm{ij}}^{(k-1)},\min [r_{\mathrm{ik}}^{(k-1)},r_{\mathrm{kj}}^{(k-1)}\left]\right\}$ 0≤i，j≤n；0≤k≤n.\n这种算法的时间复杂度T(n)满足O(n)≤T(n)≤O(n2)。\n4、设置阈值λ确定截集，对R矩阵的传递闭包矩阵 进行模糊聚类。\n本实施例中，具体方法如下：\n(1)确定n个样本X＝(X1，...，Xn)上的模糊相似关系R和一个截集阈值α；\n(2)将R按下面计算改造为一个等价矩阵；\nRοR＝R2\nR2οR2＝R4\n...\n\n直到存在一个k满足 $R^{2^k}{=R}^{2^{(k+1)}}$\n上述式子中，RοR为模糊关系的合成运算，在R是相似矩阵的假设下， 已证明必有这样的k存在，满足k≤log n；\n(3)计算集合 $\left[x\right]=\left\{y\right|\hat{R}(x,y)\ge \alpha \},$ [x]即为模糊聚类，算法结束\n5、用模糊聚类分析方法得到镜头关键帧后，然后基于这些关键帧进行镜 头检索。在此基础上，用关键帧{ri1，ri2，...，rik}表示镜头，si把镜头si和sj的相似度 定义为\n$\mathrm{Sim}(s_i,s_j)=\frac{1}{2}\{M(s_i,s_j)+\hat{M}(s_i,s_j)\}$\n其中，\n$M(s_i,s_j)=\underset{p=\{\mathrm{1,2},...\}}{\max }\underset{q=\{\mathrm{1,2},...\}}{\max }\left\{\mathrm{Inter}\sec t(r_{\mathrm{ip}},r_{\mathrm{jq}})\right\}$\n$\hat{M}(s_i,s_j)=\underset{p=\{\mathrm{1,2},...\}}{\overset{^}{\max }}\underset{q=\{\mathrm{1,2},...\}}{\max }\left\{\mathrm{Inter}\sec t(r_{\mathrm{ip}},r_{\mathrm{jq}})\right\}$\n$\mathrm{Inter}\sec t(r_i,r_j)=\frac{1}{A(r_i,r_j)}\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }\min \{H_i(h,s,v),H_j(h,s,v)\}$\n$A(r_i,r_j)=\min \{\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_i(h,s,v),\underset{h}{\Sigma }\underset{s}{\Sigma }\underset{v}{\Sigma }{H}_j(h,s,v)\}$\n表示第二大的值，使用 是因为本文使用HSV颜色直方图来表示 关键帧，它的缺点是如果两个关键帧有相似的颜色分布，即使它们的内容不 一样，也会认为这两个关键帧相似，为了克服这种缺陷，使用M和 的平均 值来加强算法的鲁棒性。Hi(h，s，v)是HSV颜色空间的直方图，本文用H，S，V 分量在18×3×3的三维空间中统计直方图，以归一化后的162个数值作为颜色 特征值。Intersect(ri，rj)表示两个直方图的交，本文用它来判断两个关键帧的相 似性。\n下面的实验结果表明，本发明取得了比现有方法更好的效果，同时检索 速度很快，证实了模糊聚类分析算法在镜头检索中的有效性。\n镜头检索的实验数据是从电视录制的2002年亚运会节目，总共有41分 钟，777个镜头，62132帧图像。它包含多种体育项目，如各种球类运动、举 重、游泳以及插播的广告节目等。我们选了7个语义类作为查询镜头，它们 是举重、排球、游泳、柔道、划船、体操、足球，如图2所示。\n为了验证本发明的有效性，我们测试了以下3种方法做实验对比：\n(1)常用的使用每个镜头的首帧做关键帧的镜头检索算法；\n(2)2002年在IEEE Trans.Circuits and Systems for Video Technology发表的 文献“An efficient algorithm for video sequence matching using the modified Hausdorff distance and the directed divergence”(该文献作者是s.H.Kim and R.-H. Park，vol.CSVT-12，no.7，页码592-595)中描述的算法；\n(3)使用模糊聚类分析算法得到关键帧进行镜头检索(只用颜色特征)；\n上述前3种方法，都仅仅使用了颜色特征，因此最后的实验结果能够从 镜头相似度的度量方法上证明本发明所公开方法的优越性。图3给出了实验 程序的用户界面，右边上面一行是查询视频的浏览区域，显示视频中每个镜 头的第1个关键帧，用来表示每个镜头，用户可以从中选择想要进行查询的 镜头进行检索，右边下面是查询结果区域。图3是选择上面一行的第1个镜 头，它是一个游泳镜头，由该镜头第一帧图像022430.bmp来表示，按照本 发明的方法计算出的相似度最大权，从大到小排列查询结果(从左到右，从 上到下排列)。左边下方为一个简易播放期，双击检索结果图像可以播放相 应镜头对应的那段视频。\n实验采用了两种在MPEG-7标准化活动中的评价指标：平均归一化调整 后的检索秩ANMRR(average normalized modified retrieval rank)和平均查全 率AR(average recall)。AR类似于传统的查全率(recall)，而ANMRR与传统 的查准率(precision)相比，不仅能够反映出正确的检索结果比例，而且能够反 映出正确结果的排列序号。ANMRR值越小，意味着检索得到的正确镜头的 排名越靠前；AR值越大，意味着在前K(K是检索结果的截断值)个查询 结果中相似镜头占所有相似镜头的比例越大。表1是上述3种方法对7个语 义镜头类的AR和ANMRR比较。\n        表1  本发明与现有两种方法的对比实验结果   分类           方法1           方法2           方法3   AR   ANMRR   AR   ANMRR   AR   ANMRR   举重   0.8824   0.3098   0.8824   0.1539   0.9412   0.2186   排球   0.6333   0.4974   0.7895   0.3264   0.8556   0.3279   游泳   0.8400   0.2676   0.8250   0.3164   0.9200   0.2175   柔道   0.7000   0.4310   0.8214   0.2393   0.8000   0.3093   划船   0.8750   0.3407   0.6875   0.3570   0.8125   0.2223   体操   0.7857   0.3445   0.9600   0.1759   0.7857   0.2056   足球   0.5789   0.4883   0.6889   0.2815   0.8421   0.2614   均值   0.7565   0.3827   0.8078   0.2642   0.8510   0.2518\n从表1可以看出，采用本发明的方法，无论是AR，还是ANMRR，都 取得了比现有的两种算法更好的效果，证实了本发明把模糊聚类分析方法方 法用于镜头检索的有效性。本发明的方法运用模糊聚类分析的方法，把镜头 内容划分为多个等价类，这些等价类很好的描述了镜头内容的变化，而镜头 之间的相似性则表现为关键帧结合之间的相似性。镜头之间相似性度量考虑 了使用HSV颜色直方图表示关键帧的缺点：如果两个关键帧有相似的颜色分 布，即使它们的内容不一样，也会认为这两个关键帧相似。因此使用最大相 似值和第二大相似值的平均值来加强算法的鲁棒性。对比实验结果证实了本 发明提出方法的有效性。另外，在CPU 500M PIII，256M内存的PC机上， 本发明的算法平均检索时间为22.557秒，对于777个镜头的视频库来说，本 发明两种算法的检索速度都是很快的。