The Best Neighborhood Matching (BNM) algorithm is an error concealment algorithm to achieve high quality image restoration. Due to the high computation cost,BNM can not meet the realtime processing requirement at this time. In this paper,we extend the original BNM algorithm which only considers the grey scale images to color images,and use a parallel BNM algorithm for high definition images. Our experiment is done in a fournode Linux cluster system. The results show that the speedup of our parallel algorithm is 7.52 when the damage rate of the image is 15%. It improves the efficiency of BNM,and does not reduce the restoration quality.