实际问题中用到的算法——递归算法确定插帧顺序

问题:

现在需要给一个视频序列插帧,插帧算法要求每次只能由两帧输入插值得到其中间帧。如果现在需要给一个视频做 4 倍(或者更高的 8,16 倍等类似)的插帧,则一个插帧的思路是当前视频每相邻帧之间插入 3 帧,即:假设插帧前视频帧序号是 0,4,8,12…,则插帧时补充相邻帧跨过的 3 个序号,得到插帧后的视频帧序号为 0,1,2,3,4,5,6,.. 即可。具体顺序为 由 0,4 插帧得 2,再由 0,2 插帧得到 1、由 2,4 插帧得到 3。

现在要解决的问题,简单来说就是,需要编写一个确定插帧顺序的代码,要求 (1)新的帧只能由原有的或者已生成帧插值得到。(2)插帧只能得到给定两帧的中间帧。

方案:

这个问题其实本质上用到的算法是递归,因为满足“原来的问题,可以转化为更小的同一问题”,即“由 0,4 插帧得 2” 和 后续的 “由 0,2 插帧得到 1、由 2,4 插帧得到 3” 本质都是从外往内找中点。

算法代码如下,输入是原视频相邻帧的序号,输出是插帧顺序,如 end_index=4, start_index=0 时,输出为 [[0, 4, 2], [0, 2, 1], [2, 4, 3]] 内层list代表 [已有帧1,已有帧2,新生成帧]

def interpIndexOrder(end_index, start_index=0):
    """
    determine the interpolate index generating order for a given start_index and end_index
    the rule is: the new interpolate index can only be generated as the middle point of the existing indexes
    for example: start_index=0 and end_index=4, the interpolate index generating order is: [0, 4->2], [0, 2->1], [2, 4->3]
    return: [[existing_index1, existing_index2, generated_new_index], ...
    """
    x = []

    def recur_interp(start_index, end_index):
        if end_index-start_index == 1:
            return # stop criterion
        assert (start_index +
                end_index) % 2 == 0, 'start_index + end_index should be even'
        
        mid_index = (start_index + end_index) // 2
        x.append([start_index, end_index, mid_index])
        
        # sub-problem
        recur_interp(start_index, mid_index)
        recur_interp(mid_index, end_index)
    
    recur_interp(start_index, end_index)
    return x

另外需要注意的是,为了在递归的时候把插帧次序记录下来,下面的函数使用了两层,第一层主函数里面的变量 x 对于子函数 recur_interp() 是处于嵌套作用域,可以被访问。

参考:

  • 这个问题的来源和最终应用完整代码 link

热门相关:地球第一剑   霸皇纪   寂静王冠   寂静王冠   霸皇纪