What Distance Measure Is Proper for Image Patches? 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?
Well, You're asking on one of the most researched topics.  

There is no 1 "Right" answer.
Many models have been suggested and many of them works pretty well.

In the Non Local Means they use Euclidean Distance.
Later revisions on the idea used Mahalanobis Distance.

Others are using different norm, other use Learned Dictionaries.  

Some use features or transformation of the data.

I think the best method depends on the image (Or set of images) and the usage (Denoising or something else).