电子学报 ›› 2006, Vol. 34 ›› Issue (10): 1911-1916.

• 论文 • 上一篇    下一篇

一种结合遗传算法和钻石搜索的多模式快速运动估计方法

郑 伟1, 刘文耀2, 王涌天1   

  1. 1. 北京理工大学光电工程系,北京 100081;2. 天津大学精密仪器与光电子工程学院,教育部光电信息重点实验室,天津 300072
  • 收稿日期:2005-02-17 修回日期:2006-03-20 出版日期:2006-10-25 发布日期:2006-10-25

A Fast Multi-Mode Search Algorithm Combining Genetic Algorithm with Diamond Search in Video Coding

ZHENG Wei1, LIU Wen-yao2, WANG Yong-tian1   

  1. 1. Department of Optic & Electronic Engineering,Beijing Institute of Technology,Beijing 100081,China;2. College of Precision Instruments and Opto-electronics Engineering,Tianjiin University, Key Laboratory of Opto-electronic Information Technical Science,EMC,Tianjin 300072,China
  • Received:2005-02-17 Revised:2006-03-20 Online:2006-10-25 Published:2006-10-25

摘要: 为了解决视频编码中运动矢量搜索精度与速度的矛盾,本文提出了一种基于遗传算法(GA)和钻石搜索(DS)的多模式快速运动估计方法——MMS算法.它以图像序列的时空预测矢量作为图像活动剧烈程度的判据,自适应选择搜索模式.针对平缓运动类型使用快速的DS搜索模式,针对剧烈运动类型使用GA/DS联合搜索模式.与现有的次优解快速算法相比,MMS有效地解决了在大运动矢量情况下编码器性能下降的问题,可以从整体上提升编码器的性能,接近理想的全搜索法的结果;与其它直接利用GA进行全局优化的方法相比,MMS利用DS配合GA实现加速收敛.此外,通过引入多模式处理的概念,在保证搜索精度的同时,充分发挥了次优解算法的效率,整体编码速度与DS等快速算法的结果十分接近.这一方法为有效地解决运动估计中的矛盾问题提供了一个新的处理框架.实验结果验证了算法的性能.

关键词: 视频编码, 运动估计, 遗传算法, 钻石搜索法, 多模式搜索法, 自适应, 时空相关

Abstract: In order to solve the conflicts between searching precision and searching speed of motion vectors in video coding,a fast MMS (Multi-Mode Search) algorithm based on GA (Genetic Algorithm) and DS (Diamond Search) is proposed in this paper.Its searching modes can be switched adaptively by the criterion of drastic level of the predictive motion vectors derived from the spatio-temporal coherence of the video sequences.In the mild motion mode,DS method is used directly;In the drastic motion mode,a combined GA/DS searching method is adopted.Comparing with nowadays fast sub-optimal searching methods,MMS can solve the performance falling problem in case of large motion vectors,which enhance the capability of video encoders thoroughly.Its performance is near to the results of ideal FS (Full Search) algorithm.Comparing with other searching methods using GA directly for obtaining global optimum,MMS combines DS with GA to achieve rapid convergence speed.Furthermore,by introducing multi-mode processing conception,the efficiency of sub-optimal searching methods is fully carried out.Its searching speed is nearly as fast as DS.And its searching precision is guaranteed simultaneously.This algorithm provides a new framework for solving the conflicts in motion estimation problems in video coding.The experimental results have rectified its effectiveness.

Key words: video coding, motion estimation, genetic algorithm (GA), diamond search(DS), multi-mode search(MMS), adaptive, spatio-temporal coherence

中图分类号: