Image similarity is a key issue for many multimedia applications. Video summarization is no exception. We have recently proposed a number of methodologies for creating visually significant summaries of videos. Our approach relies heavily on the metric which decides on whether two video key-frames are similar or not. In this paper, we compare a number of histogram representations and possible distance measures with the objective of improving the quality of video summaries.