关于视频剪辑算法的简单实现

前段时间看到一个有关视频剪辑的算法,主要用来剪辑那种循环播放的视频片断,关键就是开始和结束画面要非常的相似。思路是将每一帧看作很多象素点构成N维空间的一个点,然后寻找距离小于某一个阀值两个点。由于这种视频不能太长,所以只需要在某一帧的前面k帧寻找就可以，而不需要和其他所有对比。

直接编程比较很简单,但是耗时很大，因为一个1024*1024的画面就有10^6个像素点,如果是剪辑一个1小时的视频,那么一共有3600*24帧,要剪辑的视频片断在5s以内的话,那么最终的计算量是 1013的量级左右 。如果视频的画质,时间更长的话,运算时间还要多很多。

(a) 所以采取的一个解决思路就是利用平面几何的一些定理来减少运算。假设有f1,f2,f3三个帧,那么设它们之间的距离是 f12,f13,f23 ，则根据三角形的性质有:

f13>max(f12−f23,f23−f12) f13<min(f12+f23)

(b) 再计算每一个帧 fi 它的范式: di=∑ixi2−−−−−−√ ,则 fij≤di+dj,dij≥|di−dj| 可以计算出每一个帧之间距离的初始上下界,那么最终可以得到这个式子:

f13max=min(f13max,f23max+f12)

f13min=max(f13min,f12−f23max,f23min−f12)

(c) 上面这个式子有点复杂,需要自己好好理解。稍微说明一下, f13max 是f1和f3距离的上界,在确定了1，2的距离时,就可以来更新和1,2有关联的第三个点的距离的估计了。注意到, f13≤f12+f23 ，但是由于f_23本身的距离可能尚未确定,所以必须要确保这个等式的正确性,那么就应该取 f12+f23 的最大值才能确保。之后的min代表上界缩小了才能更新它。

(d): 利用上下界和阀值的比较可以省略很多不必要的计算。

return x def clip(video,k = 5): distance = 50 def test_near_far(l,u): nonlocal is_confirmed if l > distance:is_confirmed[f2][f1] = -1 elif u < distance:is_confirmed[f2][f1] = 1 def update_ul(f1,f2,f3,f21): nonlocal lower,upper upper[f3][f1] = min(upper[f3][f1],f21+upper[f2][f3]) lower[f3][f1] = max(lower[f3][f1],f21-upper[f2][f3],lower[f2][f3]-f21) n = len(video) upper,lower,ini = [[None]*n for i in range(n)]*n,[[None]*n for i in range(n)]*n,[0]*n is_confirmed = [[None]*n for i in range(n)] D = [[-1]*n for i in range(n)] for f1 in range(n): ini[f1] = (sum([i*i for i in video[f1]]))**(0.5) for f2 in range(0,f1): lower[f2][f1] = abs(ini[f1]-ini[f2]) upper[f2][f1] = ini[f1]+ini[f2] test_near_far(lower[f2][f1],upper[f2][f1]) for f1 in range(n): fra1 = video[f1] for f2 in range(max(f1-k,0),f1): fra2 = video[f2] if is_confirmed[f2][f1]!=None: if is_confirmed[f2][f1]==1:print(f2,f1,'near') continue d_12 = sum([(fra1[i]-fra2[i])**2 for i in range(len(fra1))])**0.5 upper[f2][f1],lower[f2][f1] = d_12,d_12 if d_12<distance:is_confirmed[f2][f1] = 1 else:is_confirmed[f2][f1]=-1 for f3 in range(f2+1,f1): update_ul(f1,f2,f3,d_12) test_near_far(lower[f3][f1],upper[f3][f1]) def createdata(): from random import randint n1,n2 = 50,1000 ans = [[randint(0,10) for i in range(n2)]] for i in range(n1): t = ans[-1] if i%3==0:ans.append([j+randint(-1,1) for j in t]) else:ans.append([j+randint(-3,3) for j in t]) return [ans] test(clip,randargs = createdata,case=10)