Research On Optimization And Parallelization Of Best Neighborhood Matching Image Restoration Algorithm

In the practical communication link, transmission errors may occur which results in the image content damaged or lost. Image restoration can use the Error concealment technique to restores the visual integrity of image that has been damaged due to a bad network transmission. Best Neighborhood Matching algorithm is an effective method which can achieve high quality image restoration. BNM exploits the information redundancy and block wise similarity to find similar content which then uses to repair the damaged piexls. But the BNM algorithm has high computation cost and requires a relatively long time and so is not suitable for real-time or high volume processing. In this thesis, we optimize the BNM algorithm in both of sequential and parallel implementation in order to improve the efficiency.In this thesis, we analyze the characteristics s of BNM algorithm and then propose a Rotate-based BNM algorithm. According to the analysis, we find that most of best matching blocks can be found in a small range around the damaged block. R_BNM searches the best matching block from the damaged block to the outside in a rotating style, so that the best matching block can be searched earlier. The R_BNM also uses a dynamically threshold in order to fit differernt image content. At 15% block miss rate, our approach can speed up BNM nineteen times without any obvious loss of accuracy. If at a lower miss rate, the speedup is much higher.We exploit two different platform, cluster system and GPU to speedup the execution through a parallel implementation. The parallel BNM algorithm on the cluster system does not reduce the PSNR value of the restoration image with muliti processes. We exploit CUDA on the GPU platform to speedup the execution through a parallel implementation, then compare and combine several different GPU optimization methods, such as coalesced global memory access, shared memory and so on. The parallel implementation on GPU can speed up BNM about 22 times without any change of the restoration process. Combine with a smaller search range, the approach on GPU can speed up BNM more than sixty times without any obvious loss of accuracy. Experiment results show that both the sequential optimization and the parallel implementation of BNM decrease the running time and keep the high restoration quality.