A new search algorithm for fast block-matching motion estimation
Cai Jian-rong · High Power Laser and Particle Beams · 2007
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.