Best Neighborhood Matching (BNM) has been shown to be an effective technique to recover a broken image due to a failed network transmission. For high definition image, the time of recovering using BNM algorithm is relative too long and not suitable for real time processing. And the original BNM only targets at gray scale image, and not considers the color image case. In this paper, we extend the BNM algorithm to color image area and use PC clusters to parallelly recover the image and improve the processing speed dramatically. The experiment result from a four nodes cluster system shows that our parallel BNM implementation improves the processing speed up to 7.52 times without any obvious recover quality decrease.