一种新的快速运动估计算法

A new search algorithm for fast block-matching motion estimation

数字化战场的发展使得红外图像信息的传输量迅速增加,因此必须对图像信息进行压缩处理,运动估计是图像压缩的关键部分。针对运动矢量的分布特点,提出了一种新的运动估计搜索算法,该算法先按照菱形搜索模板进行粗搜索,产生当前步的搜索点,并计算出各点的SAD值,根据最小SAD值是否在菱形搜索模板中心点,确定下一步的搜索方式,直到最小SAD值对应的点为菱形中心点,然后以方形搜索模板搜索,则最小SAD值对应的点即为最佳匹配点,最后得出运动矢量。测试结果表明,本算法比FS算法每帧的搜索速度提高了近20倍,与DS算法相比,搜索速度亦可以提高近20%,有效地节省了搜索时间,且基本上保持了全搜索FSA的性能,适合实时应用的要求。

The development of digital war field brings on the increasing of infrared image transmission, thus image compression is needed to meet the requirement, and motion estimation is the key section of the image compression. In this paper, a new search algorithm, diamond and square search（DSS） is proposed by analyzing the motion vector distribution. The algorithm employs two search patterns the diamond search（DS） pattern and the square search pattern. In the first search step, the diamond search pattern is centered at the origin of the search window, and 5 checking points are tested. If the point with the minimum sum of absolute difference（SAD） is not located at the center, the diamond search pattern is repeated, until the minimum SAD point is located at the center of the diamond, then the search pattern is switched from the diamond search pattern to the square one. Compared with the DS algorithm, the new algorithm requires less checking points and 20% less computation. The results of simulation demonstrate that the new algorithm achieves a performance close to that of full search（FS） algorithm but 20 times faster on average, meeting the need of real-time search.