Parallel Best Neighborhood Matching Algorithm Implementation on GPU Platform

Error concealment restores the visual integrity of image content that has been damaged due to a bad network transmission. Best neighborhood matching (BNM) is an effective image recovery method that exploits the information redundancy in a block-coded broken image to find similar content which it then uses to repair or conceal errors. On a high definition image BNM is traditionally implemented sequentially, which requires a relatively long time and so is not suitable for real-time or high volume use. In this paper, we analyze the data access patterns of the BNM algorithm, and exploit a GPU platform to speedup the execution through a parallel implementation. We compare and combine several different GPU optimization methods (coalesced global memory access, shared memory, register files, etc.), and propose an improvement to the parallel BNM algorithm. Experiment results show that our approach can speed up BNM twenty-one times over the sequential approach without any obvious loss of accuracy.