Trjtdtk

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?

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
$$ fracS_sqsqrtsum 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
$$ fracC_crrsqrtsum 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.

2 - BRIEF, BRISK and FAST:

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