I have a bunch of image patches extracted from two images.

I want to find a proper measure of similarity between each patch from first images to patches from second image.

I have made vectors from each patch to calculate distance/similarity. I have tried to use euclidean distance and closest vector by phase, but these two measures do not perform well when reconstructing first image by replacing each patch by the most similar patch of the second image.

Is there any well suited measure of similarity for small patches of two images?