1. An image processing device, comprising: a degree-of-similarity calculation unit which uses a dictionary for storing data of plural pairs associating deteriorated patches which are patches from a deteriorated image formed by deteriorating a prescribed image, and restoration patches which are patches from said prescribed image, and calculating, as a degree of similarity between plural input patches generated by dividing an input image which is input and said deteriorated patches, a weighted degree-of-similarity which is a degree-of-similarity between weighted deteriorated patches and weighted input patches in which forms of said deteriorated patches and said input patches are reconfigured using a patch weight which is continuous weight; a selection unit which selects, on the basis of said weighted degree-of-similarity, a restoration patch for each input patch; and a combination unit which combines said restoration patches, each of which is selected for each input patch, to generate a restored image.