I have two group images for cat and dog. And each group contain 2000 images for cat and dog respectively.

My goal is try to cluster the images by using k-means.

Assume image1 is x, and image2 is y.Here we need to measure the similarity between any two images. what is the common way to measure between two images?

  • $\begingroup$ You can use Siamese Networks -> “Face Recognition from Scratch using Siamese Networks and TensorFlow” by Shubham Panchal link.medium.com/HT66TqDdCV . They output a similarity score which is binary. $\endgroup$ – Shubham Panchal Apr 5 '19 at 2:15
  • $\begingroup$ Thanks, that is real cool method. any other traditional machine learning method? like no use neural network. $\endgroup$ – jason Apr 5 '19 at 2:31

Check this handout!

Well, there a few so... lets go:

Given two images $J[x,y]$ and $I[x,y]$ with $(x,y) \in N^{N \times M}$...

A - Used in template matching:

Template Matching is linear and is not invariant to rotation (actually not even robust to it) but it is pretty simple and robust to noise such as the ones in photography taken with low illumination.

You can easily implement these using OpenCV Template Matching. Bellow there are mathematical equations defining some of the similarity measures (adapted for comparing 2 equal sized images) used by cv2.matchTemplate:

1 - Sum Square Difference

$$ S_{sq} = \sum_{(n,m) \in N^{M \times N}} \bigr(J[n,m] - I[n,m]\bigl)^2$$

This can be normalized as $$ \frac{S_{sq}}{\sqrt{\sum J[n,m]^2 \times \sum I[n,m]^2}} $$

2 - Cross-Correlation

$$ C_{crr} = \sum_{(n,m) \in N^{M \times N}} \bigr(J[n,m] \times I[n,m]\bigl)^2$$

This can be normalized as $$ \frac{C_{crr}}{\sqrt{\sum J[n,m]^2 \times \sum I[n,m]^2}} $$

B - Image descriptors/feature detectors:

Many descriptors were developed for images, their main use is to register images/objects and search for them in other scenes. But, still they offer a lot of information about the image and were used in pupil detection (A joint cascaded framework for simultaneous eye detection and eye state estimation) and even seem it used for lip reading (can't direct you to it since I am not sure it was already published)

They detect points that can be considered as features in images (relevant points) the local texture of these points or even their geometrical position to each other can be used as features.

You can learn more about it in Stanford's Image Processing Classes (check handouts for classes 12,13 and 14, if you want to keep research on Computer vision I recomend you check the whole course and maybe Rich Radke classes on Digital Image Processing and Computer Vision for Visual Effects, there is a lot of information there that can be useful for this hard working computer vision style you're trying to take)

1 - SIFT and SURF:

These are Scale Invariant methods, SURF is a speed-up and open version of SIFT, SIFT is proprietary.


These are binary descriptors and are really fast (mainly on processors with a pop_count instruction) and can be used in a similar way to SIFT and SURF. Also, I've used BRIEF features as substitutes on template matching for Facial Landmark Detection with high gain on speed and no loss on accuracy for both the IPD and the KIPD classifiers, although I didn't publish any of it yet (and this is just an incremental observation on the future articles so I don't think there is harm in sharing).

3 - Histogram of Oriented Gradients (HoG):

This is rotation invariant and is used for face detection...

C - Convolutional Neural Networks:

I know you don't want to used NN's but I think it is fair to point they are REALLY POWERFULL, training a CNN with Triplet Loss can be really nice for learning a representative feature space for clustering (and classification).

Check Wesley's GitHub for a example of it's power in facial recognition using Triplet Loss to get features and then SVM to classify.

Also, if your problem with Deep Learning is computational cost, you can easily find pre-trained layers with cats and dogs around.

D - Check on previous work:

This cats and dogs fight has been going on for a long time... you can check solutions on Kaggle Competitions (Forum and Kernels), there were 2 on cats and dogs This One and That One

E - Famous Measures:

  • SSIM Structural similarity Index
  • L2 Norm (Or Euclidean Distance)
  • Mahalanobis Distance

F - Check on other kind of features

  • Cats and dogs can be a easy to identify by their ears and nose... size too but I had cats as big as dogs... so not really that safe to use size.

  • But you can try segmenting the images into animals and background and then try to do region property analisys...

  • Also, check on this image similarity metrics toolkit page it is in C but...

  • Check this paper on image similarity

  • Take a look on this Stack Overflow question and this Research Gate one

  • If you have the time, this book here: Feature Extraction & Image Processing for Computer Vision from Mark S. Nixon have much information on this kind of procedure

  • You can try Fisher Discriminant Analysis and PCA to create a mapping and the evaluate with Mahalanobis Distance or L2 Norm

| improve this answer | |
  • $\begingroup$ can hamming distance be part of the CNN binarized feature vectors? $\endgroup$ – Färid Alijani Feb 14 at 13:02
  • $\begingroup$ @FäridAlijani you mean creating a CNN where we use hamming distance instead of common dot products to measure similarity (actually a distance would measure dissimilarity, but I think you get what I mean)? If so: that would be great if you consider memory and processor usage, but how to create that? I had that idea before but never seen a way to train a network like that since binary feature vectors wouldn't work well with gradient descent and the hamming distance has (to the best of my knowledge) no derivatives. $\endgroup$ – Pedro Henrique Monforte Feb 18 at 15:21
  • $\begingroup$ For the simple cross-correlation of outputs from a deep learning (convolutional neural network) model, it may be an idea to consider scaling the x and y before the cross-correlation. In "Inferring visual semantic similarity with deeplearning and Wikidata: Introducingimagesim-353" at ceur-ws.org/Vol-2106/paper7.pdf we considered that. There are number of ways the scaling could be done, - not just logarithmic. $\endgroup$ – Finn Årup Nielsen Jul 27 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.