2D-3D视频转换中的非关键帧排序方法

摘要

本发明提出了一种2D‑3D视频转换中基于相似度的非关键帧排序方法。首先对需要处理的视频所有帧进行K均值聚类，之后将每一类中与类中心之间距离最小的帧设置为关键帧。然后对每一类非关键帧，根据两帧之间的相似性进行排序，确保深度传播过程中，深度传播的两帧之间的相似度最高，深度传播误差最小。

权利要求

1.一种2D-3D视频转换中的非关键帧排序方法，其特征在于：首先对需要处理的视频所有帧进行K均值聚类，之后将每一类中与类中心之间距离最小的帧设置为关键帧，然后对每一类非关键帧根据两帧之间的相似性进行排序，确保深度传播过程中，深度传播的两帧之间的相似度最高，深度传播误差最小，具体包括以下步骤：(1)根据视频帧数量，将输入视频分成若干个视频片段；

(2)确定每一视频片段所需关键帧的数量，进而确定对每一片段视频帧聚类的类数，并进行K均值聚类；

(3)聚类完成后，将每一类与类中心距离最小的视频帧设为关键帧，并根据距离大小对非关键帧进行排序；

(4)得到关键帧的深度图，由关键帧向最近的一个非关键帧传播深度，然后根据得到的非关键帧排列顺序进行深度传播。

2.根据权利要求1所述的方法，其特征在于：所述步骤(1)中，通过采用平均分段、固定长度分段、基于运动量累计分段或镜头分割的方式实现视频分段。

3.根据权利要求1所述的方法，其特征在于：所述步骤(2)中，确定每一视频片段所需关键帧的数量时，可采用如下可选方式：规定每一视频片段中关键帧的个数、规定平均一定数量的视频帧中有一个关键帧、根据每一视频片段中场景变化的程度确定关键帧的数量。

4.根据权利要求1所述的方法，其特征在于：所述步骤(2)中，在进行K均值聚类时，初始类中心的选择可采用如下可选方式：按照随机选择、按照时间等间隔选择、采用现有的关键帧提取方法选择。

5.根据权利要求1所述的方法，其特征在于：所述步骤(2)中，在进行K均值聚类过程中，计算两帧之间的距离时，可采用如下可选方式：灰度直方图、颜色直方图、特征点匹配度。

6.根据权利要求1所述的方法，其特征在于：所述步骤(3)的具体实现步骤：A聚类完成后，将每一类与类中心距离最小的视频帧设为关键帧；

B找到每一类中与关键帧相似度最高也就是距离最小的非关键帧，标记为第一个非关键帧；

C找到每一类中剩余视频帧与关键帧和已标记序号的非关键帧的距离，距离最小的标记为第二个非关键帧，并记录与其距离最小的帧的序号；

D重复C的步骤，按顺序标记序号，将所有非关键帧排序，同时记录距每一非关键帧距离最小的帧的序号。

7.根据权利要求1所述的方法，其特征在于：所述步骤(4)的具体实现步骤为：A关键帧的深度图由人工辅助分配得到，或者利用深度线索自动估计关键帧的深度图，所述深度线索包括消失线、几何透视、运动视差或散聚焦；

B由关键帧向第一个非关键帧传播深度；

C第一个非关键帧获得深度后，从第一个非关键帧开始根据步骤(3)获得的非关键帧排列顺序，每一非关键帧得到与其距离最小的帧传播的深度。

说明书

2D-3D视频转换中的非关键帧排序方法

技术领域

[0001] 本发明涉及一种2D-3D视频转换中的非关键帧排序方法，属于视频、多媒体信号处理和三维显示技术领域。

背景技术

[0002] 3D显示越来越受到观众的喜爱。2D-3D视频转换技术可以将普通的2D视频转换为3D视频，极大缓解3D资源缺乏的问题，近年来受到了越来越多的关注。2D-3D视频转换主要分为以下几个步骤：1)关键帧选取，2)分配关键帧深度，3)向非关键帧传播深度，4)利用DIBR算法生成左右视图。其中，关键帧选取和深度传播是影响立体视频质量的重要步骤。目前，关键帧选取方面，绝大多数方法主要依据时间顺序对视频帧进行等间隔采样得到关键帧，在深度传播方面，也主要是依据时间顺序，在时间相近的视频帧之间进行深度传播。这样的方式虽然简单易行，但忽视了时间相近的视频帧在内容和结构上的不连续性和不相似性，影响了帧间深度传播的质量。

[0003] 已经有人将聚类的思想运用到关键帧选取中，把聚类中心作为关键帧。然而，对于除关键帧之外的其它的帧，即非关键帧，并未有进一步的研究。各个非关键帧与关键帧之间在内容和结构上的相似程度是各不相同的，现有方法并未考虑到这一点，而是在用聚类选取关键帧之后，仍然按照时间顺序进行深度传播，从而使帧间深度传播的质量仍存在改进的空间。

[0004] 另外，现有方法大都是将关键帧选取和深度传播这两个步骤分别进行设计，缺少将两者放在统一的方法框架中，采用同样的模型和思想进行协同设计的方法，这也在一定程度上限制了深度传播质量的进一步提升。

发明内容

[0005] 根据深度传播的机制可知，帧间深度传播质量的主要影响因素是两帧在内容和结构上的相似性。本发明使用帧间距离来量化视频帧的相似性，将关键帧选取和深度传播统一起来，充分利用关键帧与各非关键帧之间的关系，使视频帧得到的深度图质量更好，进而提升了立体视频的视觉效果。

[0006] 为实现上述目的，本发明采用如下技术方案：

[0007] 一种2D-3D视频转换中的非关键帧排序方法，其特征在于：首先对需要处理的视频所有帧进行K均值聚类，之后将每一类中与类中心之间距离最小的帧设置为关键帧，然后对每一类非关键帧根据两帧之间的相似性进行排序，确保深度传播过程中，深度传播的两帧之间的相似度最高，深度传播误差最小，具体包括以下步骤：

[0008] (1)根据视频帧数量，将输入视频分成若干个视频片段；

[0009] (2)确定每一视频片段所需关键帧的数量，进而确定对每一片段视频帧聚类的类数，并进行K均值聚类；

[0010] (3)聚类完成后，将每一类与类中心距离最小的视频帧设为关键帧，并根据距离大小对非关键帧进行排序；

[0011] (4)得到关键帧的深度图，由关键帧向最近的一个非关键帧传播深度，然后根据得到的非关键帧排列顺序进行深度传播。

[0012] 所述步骤(1)中，通过采用平均分段、固定长度分段、基于运动量累计分段或镜头分割的方式实现视频分段。

[0013] 所述步骤(2)中，确定每一视频片段所需关键帧的数量时，可采用如下可选方式：规定每一视频片段中关键帧的个数、规定平均一定数量的视频帧中有一个关键帧、根据每一视频片段中场景变化的程度确定关键帧的数量。

[0014] 所述步骤(2)中，在进行K均值聚类时，初始类中心的选择可采用如下可选方式：按照随机选择、按照时间等间隔选择、采用现有的关键帧提取方法选择。

[0015] 所述步骤(2)中，在进行K均值聚类过程中，计算两帧之间的距离时，可采用如下可选方式：灰度直方图、颜色直方图、特征点匹配度。

[0016] 所述步骤(3)的具体实现步骤：

[0017] A聚类完成后，将每一类与类中心距离最小的视频帧设为关键帧；

[0018] B找到每一类中与关键帧相似度最高也就是距离最小的非关键帧，标记为第一个非关键帧；

[0019] C找到每一类中剩余视频帧与关键帧和已标记序号的非关键帧的距离，距离最小的标记为第二个非关键帧，并记录与其距离最小的帧的序号；

[0020] D重复C的步骤，按顺序标记序号，将所有非关键帧排序，同时记录距每一非关键帧距离最小的帧的序号。

[0021] 所述步骤(4)的具体实现步骤为：

[0022] A关键帧的深度图可以由人工辅助分配得到，也可以利用消失线、几何透视、运动视差、散聚焦等深度线索自动估计关键帧的深度图；

[0023] B由关键帧向第一个非关键帧传播深度；

[0024] C第一个非关键帧获得深度后，从第一个非关键帧开始根据步骤(3)获得的非关键帧排列顺序，每一非关键帧得到与其距离最小的帧传播的深度。

[0025] 本发明方法的优势在于考虑到在深度传播过程中，关键帧的选取和非关键帧的深度传播顺序都影响着传播得到的深度图效果。特别是在深度传播中，利用视频帧的相似度来决定非关键帧的深度传播次序，而不是通常使用的时间顺序。传播与被传播深度的两帧相似度最大，保证了传播误差最小。因为在每一类视频帧深度传播过程中，误差是累计增大的，所以利用相似度传播保证了累计误差最小，使得视频的深度图整体效果上优于利用时间顺序传播得到的深度图。

附图说明

[0026] 图1是本发明方法的框架图；

[0027] 图2是“Kendo”视频的某一帧；

[0028] 图3是“Kendo”视频某一帧的512bin颜色直方图；

[0029] 图4是“Breakdancer”视频的聚类结果；

[0030] 图5是“Kendo”视频某一关键帧的深度图；

[0031] 图6是本发明与等间隔选取关键帧方法的均方误差(MSE)分布的结果比较；

[0032] 图7是本发明与基于深度估计选取关键帧方法的均方误差(MSE)分布的结果比较；

[0033] 图8是本发明与基于累计直方图选取关键帧方法的均方误差(MSE)分布的结果比较；

[0034] 图9是本发明与基于重投影误差选取关键帧方法的均方误差(MSE)分布的结果比较。

具体实施方式

[0035] 下面结合附图与实施例对本发明作进一步说明。

[0036] 图1给出了本发明一种半自动2D-3D视频转换中基于相似度的非关键帧排序算法的流程图，以2D-3D视频转换中的通用视频“Kendo”和“Breakdancer”为例，本发明的具体步骤如下：

[0037] 1.将输入的2D视频分割成若干个小片段,具体实施步骤如下：

[0038] (1)根据视频帧出现的先后顺序，采用平均分段方法，将视频帧按照每300帧为一个视频片段进行分割，余下不足300帧的单独作为一个视频片段，图2展示了视频片段“Kendo”的某一帧。

[0039] (2)对分割后的每个视频片段分别按照下面的方法逐步选择关键帧。

[0040] 2.对视频片段根据关键帧数量进行K均值聚类，具体步骤如下：

[0041] (1)对于300帧的视频片段，选取13帧作为关键帧；如果视频片段关键帧的数量为NK，则视频帧将被K均值聚类分为NK类，这里以300帧的视频片段为例进行介绍，NK为13。

[0042] (2)利用颜色直方图对视频帧进行聚类，将视频帧转化为512bin HSV颜色直方图，色调(H)，饱和度(S)，亮度(V)分别被分为8部分，具体取值范围如下：

[0043]

[0044] (3)所有参数转换为一个特征向量L＝64H+8S+V。根据特征向量L，得到每一帧的512bin颜色直方图,如图3所示。

[0045] (4)首先随机选择NK张颜色直方图作为聚类的初始类中心，计算其他颜色直方图与初始类中心的距离大小。这里距离被定义为直方图每一对应bin的值做差之后大于设定阈值TH的bin的数量d。d的值越大，则两张直方图距离越大，差异越大。伪代码如下：

[0046] d＝0；

[0047] For bin＝1:512

[0048] Difference＝每一对应bin的值做差；

[0049] If Difference>TH

[0050] d＝d+1；

[0051] End；

[0052] 公式如下：

[0053] dint＝0,

[0054]

[0055] 这里，dint为初始距离值，d为计算得到的距离值，bint(m)为第t张颜色直方图第mbin的值，bini(m)为第i张类中心颜色直方图第mbin的值。每一张颜色直方图与其聚类最小的类中心聚为一类。

[0056] (5)得到NK类颜色直方图后，计算每一类每一bin的平均值，作为新的类中心，重复上述步骤(4)的过程。当实验结果趋于稳定时或达到设定的迭代次数，迭代结束。图4展示了视频片段“Breakdancer”的聚类结果。

[0057] 3.对每一类视频帧进行排序，具体步骤如下：

[0058] (1)计算每一类颜色直方图与类中心的距离，将距离类中心最小的颜色直方图代表的视频帧设为关键帧，序号为f0，并且将此关键帧加到集合C中，C＝{f0}。

[0059] (2)计算非关键帧与关键帧的距离，将距离关键帧最小的非关键帧设序号为f1，并且将此非关键帧加到集合C中，C＝{f0,f1}，同时将(f0,f1)加入到有序数对集合M中，M＝{(f0,f1)}。

[0060] (3)计算未获得序号的非关键帧与集合C中所有帧的距离，某一未获得序号的非关键帧与集合C所有帧距离中的最小距离作为这一非关键帧的距离。找到距离最小的非关键帧，设序号为f2，并添加到集合C中，C＝{f0,f1,f2}。这里，如果f0到f2的距离最小，则将(f0,f2)加入到M中，则M＝{(f0,f1),(f0,f2)}，反之，将(f1,f2)加入到M中，则M＝{(f0,f1),(f1,f2)}。

[0061] (4)对未获得序号的非关键帧重复上述步骤(3)，即将获得序号的非关键帧添加到集合C，将与其距离最小的集合C中的帧和其本身组成数对，并添加到集合M中。直到一类中的所有帧都添加到集合C中，设一类所有帧的数目为N，则

[0062] C＝{f0,f1,...,fN-1,fN}，M中的数对个数为N-1。

[0063] 4.基于非关键帧的排列顺序，将关键帧的深度图传播到非关键帧的深度图，具体步骤如下：

[0064] (1)对关键帧分配深度，使用人工辅助分配，图5展示了视频片段“Kendo”中某一关键帧的深度图。

[0065] (2)利用位移双边滤波算法传播深度。

[0066] (3)根据上述步骤得到的有序数对集合M，对视频帧进行深度传播，由每一数对中的第一个序号代表的视频帧向第二个序号代表的视频帧进行传播。

[0067] 图6至9给出了本发明一种2D-3D视频转换中基于相似度的非关键帧排序方法同其它方法的MSE比较图。MSE通过计算传播得到的深度图与标准深度图之间的均方误差得到。从图6-9中可以看出本发明一种2D-3D视频转换中基于相似度的非关键帧排序方法较优。

[0068] 表1和表2给出了本发明一种2D-3D视频转换中非关键帧排序方法同其他关键帧选取及排序方法对于两种视频的平均MSE比较。从表中可以看出本发明一种2D-3D视频转换中基于相似度的非关键帧排序方法较优。

[0069] 表1

[0070]

[0071] 表2

[0072]