PDF《相似顺序图用于视频镜头的组织》

2 (最优相似顺序, 最优相似顺序图). 已知内容描述空间中的点集{P i, i= 0, 1,. . . ,N }, 根据给定相似 距离定义, 计算一条遍历非封闭路径 P i0P i1 . . . P in , 使得相应的 n 阶相似距离L n= ∑ n m =

1 W m ・∑ n l= m P il- m P il 最短. 顺序 i0 i1 . . . in 称为此点集在此相似距离定义下的最优相似顺序, 对应的代表帧序列图称为最优相似顺序图. 最优相似顺序的计算是一个比较复杂的问题. 但由于镜头组织的目的是提供一个方便用户交互组织的界 面, 因而并不要求得到的必须是最优相似顺序, 往往次优相似顺序(次短路径对应的顺序) 就已给出了相当好的 组织结果. 基于这个原因, 我们将在下面的讨论中用相似顺序和相似顺序图来笼统地称呼所得到的排列顺序和 代表帧序列图. ―

5 0

9 ―

9 期 白雪生等: 相似顺序图用于视频镜头的组织 ? 1994-2006 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 2.

2 求取相似顺序图遗传算法的基本思想 通过上述分析, 序列重排转化为一个优化问题. 我们采用遗传算法来进行求解, 每个解直接用其路径对应 的序列来表示. 对于群体中新个体的产生方法, 我们除了采用传统的重组和杂交之外, 还提出了根据知识的染 色体片段迁移的方法. 下面我们将对这

3 种方法进行详细说明. (1) 重组 本算法引入了两种重组方式. (a) 定位重组 从染色体

1 中随机选择一些片段(点数和位置随机) , 复制到其子染色体的对应位置. 从染 色体

2 中去除已选中的点, 将剩余点按其在染色体

2 中的顺序依次填入子染色体中. 图1给出了片段中包含

3 点(B, E, F) 的定位重组示意图. 图1定位重组示意图 (b) 定位连续重组 从染色体 ........