用于块匹配运动估值的正方形-菱形搜索算法

运动估值在视频图像编码中占有重要地位，该文首先研究了运动估值中的经典搜索算法并重点分析了菱形（DS）算法；然后设计了一种新的综合模板（SDP），它体现了粗定位和准确定位并行处理的思想，在此基础上提出了一种新的用于块匹配的运动估值搜索算法－－正方形－菱形搜索（SDS）算法。最后通过实验验证了该算法的有效性。

A Square-Diamond Search Algorithm for Block Motion Estimation

This paper firstly analyzes some typical search algorithms in motion estimation, especially the Diamond Search(DS)algorithm. It is found that these algorithms are all based on serial processing ideas, since their search steps can only be changed degressively, in other words, first coarse location and second accurate orientation, which make the search blindness. Secondly, aimed at questions existing in these algorithms, the authors design a new integrative pattern-Square Diamond Pattern(SDP), which is composed of a diamond and a square. The SDP can realize content based search for following three possibilities when it performs matching computation. If the minimum block distortion (MBD) point in the middle of the pattern, it shows that image is still and completes search by one step, if the MBD point is at one of the diamond's four corners, it shows there is small motion in the image, if the MBD point is at one of the square's four corners, it shows there is large motion in the image. The next step of search will adaptively use different pattern according to motion types. Therefore, SDP is based on parallel processing idea of coarse location and accurate orientation determined by its structure. Thirdly, authors present a new Square Diamond Search(SDS)Algorithm for block matching motion estimation with SDP. Finally, the results of experiments show that not only the new SDS is much faster than traditional algorithms, but also its PSNR and visual quality of the retrieval images are better than those of other algorithms, and as nearly good as that of FS.