Abstract: Best neighborhood matching （BNM） is an error concealment algorithm to achieve high quality image restoration. However, BNM needs intensive computation, which restricts its real application. In this paper, a parallel BNM is proposed. Several critical techniques have been developed to obtain high performance. These techniques include overlap stripe data distribution, reading strategy, and communication strategy. Theoretical analysis and experimental results show that the parallel BNM has good speed up and scalability so that it can provide an efficient way for image restoration.