问题：
现在需要给一个视频序列插帧，插帧算法要求每次只能由两帧输入插值得到其中间帧。如果现在需要给一个视频做 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])
recur_interp(start_index, mid_index)
recur_interp(mid_index, end_index)
recur_interp(start_index, end_index)
return x
参考：
- 这个问题的来源和最终应用完整代码 link