Improvement Research Of GPM Block Matching Algorithm

Under the background of Big Data, batch processing of images and video has become a norm. So people's speed requirements on image and video processing algorithm is higher. Block matching algorithm is the basis of many algorithms of image and video processing applications. However, block matching algorithm often becomes the bottleneck of the performance of image processing applications. The traditional way to solve the block matching problem is full search, although this method can guarantee a good processing effect, but it is linear, when dealing with large-scale high-dimensional data will appear to be powerless. Therefore, researchers have put forward a lot of improved methods to solve the block matching problem. For example: three steps method, four steps method and other fast search algorithms;method for efficient data structure based on KD-Trees, VP-Trees; Patch Match algorithm, GPM(Generalized Patch Match) algorithm and other methods based on local consistency. All of these methods can ensure the accuracy of matching, at the same time, a certain degree of acceleration matching process. In particular, the two algorithms based on local consistency, greatly utilize the characteristics of the image itself, increase the block matching speed to a new level and has been well applied.The speed and precision of block matching have been the unremitting pursuit of researchers. Although the GPM algorithm has obtained a very good degree of interaction, there is still room for improvement. GPM is a block matching algorithm calculated in offset, scale and angle space, which consists of two steps: initialization and iteration, and the iteration also contains the two operations of the propagation and random search. We find that the GPM algorithm has some redundant computation in the position where the matching results are better. This affects the speed of matching a certain extent. And random search stage, lateral offset, vertical offset, angle and scale simultaneous contraction will lose some useful information that has been obtained by matching, it will affect the precision of matching algorithm.Therefore, aiming at these problems, this paper proposes an improved algorithm based on GPM algorithm. In this paper, the Patch Match algorithm is used to initialize the GPM algorithm, so that the algorithm can get better offset information in the initialization stage. And then in the random search phase, we add two thresholds,according to the location of the current matching error of the specific circumstances to take three different processing methods:(1) if the current matching error is larger than the average error, the random search method of offset, scale and angle simultaneouscontraction is adopted;(2) if the current matching error is less than the average error,but greater than 1/2 of the average error, then fixed offset, only contraction angle and scale;(3) if the current matching error is less than 1/2 of the average error, the position does not carry out random search operation. In this way, we can make full use of the available information, and reduce the redundant computation, so as to improve the matching precision and the interaction of the algorithm. Experiments show that the algorithm can improve the matching speed and the matching accuracy when handling most of the input.