Simple and fast method to compare images for similarity

Image ProcessingOpencvComputer Vision

Image Processing Problem Overview

I need a simple and fast way to compare two images for similarity. I.e. I want to get a high value if they contain exactly the same thing but may have some slightly different background and may be moved / resized by a few pixel.

(More concrete, if that matters: The one picture is an icon and the other picture is a subarea of a screenshot and I want to know if that subarea is exactly the icon or not.)

I have OpenCV at hand but I am still not that used to it.

One possibility I thought about so far: Divide both pictures into 10x10 cells and for each of those 100 cells, compare the color histogram. Then I can set some made up threshold value and if the value I get is above that threshold, I assume that they are similar.

I haven't tried it yet how well that works but I guess it would be good enough. The images are already pretty much similar (in my use case), so I can use a pretty high threshold value.

I guess there are dozens of other possible solutions for this which would work more or less (as the task itself is quite simple as I only want to detect similarity if they are really very similar). What would you suggest?

There are a few very related / similar questions about obtaining a signature/fingerprint/hash from an image:

Also, I stumbled upon these implementations which have such functions to obtain a fingerprint:

Some discussions about perceptual image hashes: here

A bit offtopic: There exists many methods to create audio fingerprints. MusicBrainz, a web-service which provides fingerprint-based lookup for songs, has a good overview in their wiki. They are using AcoustID now. This is for finding exact (or mostly exact) matches. For finding similar matches (or if you only have some snippets or high noise), take a look at Echoprint. A related SO question is here. So it seems like this is solved for audio. All these solutions work quite good.

A somewhat more generic question about fuzzy search in general is here. E.g. there is locality-sensitive hashing and nearest neighbor search.

Image Processing Solutions

Solution 1 - Image Processing

Can the screenshot or icon be transformed (scaled, rotated, skewed ...)? There are quite a few methods on top of my head that could possibly help you:

Most of these are already implemented in OpenCV - see for example the cvMatchTemplate method (uses histogram matching): http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html. The salient point/area detectors are also available - see http://opencv.willowgarage.com/documentation/cpp/feature_detection.html">OpenCV Feature Detection.

Solution 2 - Image Processing

I face the same issues recently, to solve this problem(simple and fast algorithm to compare two images) once and for all, I contribute an img_hash module to opencv_contrib, you can find the details from this link.

img_hash module provide six image hash algorithms, quite easy to use.

Codes example

origin lenaorigin lena

blur lenablur lena

resize lenaresize lena

shift lenashift lena

#include <opencv2/core.hpp>
#include <opencv2/core/ocl.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/img_hash.hpp>
#include <opencv2/imgproc.hpp>

#include <iostream>

void compute(cv::Ptr<cv::img_hash::ImgHashBase> algo)
{
    auto input = cv::imread("lena.png");
    cv::Mat similar_img;

    //detect similiar image after blur attack
    cv::GaussianBlur(input, similar_img, {7,7}, 2, 2);
    cv::imwrite("lena_blur.png", similar_img);
    cv::Mat hash_input, hash_similar;
    algo->compute(input, hash_input);
    algo->compute(similar_img, hash_similar);
    std::cout<<"gaussian blur attack : "<<
               algo->compare(hash_input, hash_similar)<<std::endl;

    //detect similar image after shift attack
    similar_img.setTo(0);
    input(cv::Rect(0,10, input.cols,input.rows-10)).
            copyTo(similar_img(cv::Rect(0,0,input.cols,input.rows-10)));
    cv::imwrite("lena_shift.png", similar_img);
    algo->compute(similar_img, hash_similar);
    std::cout<<"shift attack : "<<
               algo->compare(hash_input, hash_similar)<<std::endl;

    //detect similar image after resize
    cv::resize(input, similar_img, {120, 40});
    cv::imwrite("lena_resize.png", similar_img);
    algo->compute(similar_img, hash_similar);
    std::cout<<"resize attack : "<<
               algo->compare(hash_input, hash_similar)<<std::endl;
}

int main()
{
    using namespace cv::img_hash;

    //disable opencl acceleration may(or may not) boost up speed of img_hash
    cv::ocl::setUseOpenCL(false);

    //if the value after compare <= 8, that means the images
    //very similar to each other
    compute(ColorMomentHash::create());

    //there are other algorithms you can try out
    //every algorithms have their pros and cons
    compute(AverageHash::create());
    compute(PHash::create());
    compute(MarrHildrethHash::create());
    compute(RadialVarianceHash::create());
    //BlockMeanHash support mode 0 and mode 1, they associate to
    //mode 1 and mode 2 of PHash library
    compute(BlockMeanHash::create(0));
    compute(BlockMeanHash::create(1));
}

In this case, ColorMomentHash give us best result

  • gaussian blur attack : 0.567521
  • shift attack : 0.229728
  • resize attack : 0.229358

Pros and cons of each algorithm

Performance under different attacks

The performance of img_hash is good too

Speed comparison with PHash library(100 images from ukbench) compute performance comparison performance

If you want to know the recommend thresholds for these algorithms, please check this post(http://qtandopencv.blogspot.my/2016/06/introduction-to-image-hash-module-of.html). If you are interesting about how do I measure the performance of img_hash modules(include speed and different attacks), please check this link(http://qtandopencv.blogspot.my/2016/06/speed-up-image-hashing-of-opencvimghash.html).

Solution 3 - Image Processing

Does the screenshot contain only the icon? If so, the L2 distance of the two images might suffice. If the L2 distance doesn't work, the next step is to try something simple and well established, like: Lucas-Kanade. Which I'm sure is available in OpenCV.

Solution 4 - Image Processing

If you want to get an index about the similarity of the two pictures, I suggest you from the metrics the SSIM index. It is more consistent with the human eye. Here is an article about it: Structural Similarity Index

It is implemented in OpenCV too, and it can be accelerated with GPU: OpenCV SSIM with GPU

Solution 5 - Image Processing

If you can be sure to have precise alignment of your template (the icon) to the testing region, then any old sum of pixel differences will work.

If the alignment is only going to be a tiny bit off, then you can low-pass both images with cv::GaussianBlur before finding the sum of pixel differences.

If the quality of the alignment is potentially poor then I would recommend either a Histogram of Oriented Gradients or one of OpenCV's convenient keypoint detection/descriptor algorithms (such as SIFT or SURF).

Solution 6 - Image Processing

If for matching identical images - code for L2 distance

// Compare two images by getting the L2 error (square-root of sum of squared error).
double getSimilarity( const Mat A, const Mat B ) {
if ( A.rows > 0 && A.rows == B.rows && A.cols > 0 && A.cols == B.cols ) {
    // Calculate the L2 relative error between images.
    double errorL2 = norm( A, B, CV_L2 );
    // Convert to a reasonable scale, since L2 error is summed across all pixels of the image.
    double similarity = errorL2 / (double)( A.rows * A.cols );
    return similarity;
}
else {
    //Images have a different size
    return 100000000.0;  // Return a bad value
}

Fast. But not robust to changes in lighting/viewpoint etc. Source

Solution 7 - Image Processing

If you want to compare image for similarity,I suggest you to used OpenCV. In OpenCV, there are few feature matching and template matching. For feature matching, there are SURF, SIFT, FAST and so on detector. You can use this to detect, describe and then match the image. After that, you can use the specific index to find number of match between the two images.

Solution 8 - Image Processing

Hu invariant moments is very powerful tool to compare two images

Solution 9 - Image Processing

Hash functions are used in the undouble library to detect (near-)identical images (disclaimer: I am also the author). This is a simple and fast way to compare two or more images for similarity. It works using a multi-step process of pre-processing the images (grayscaling, normalizing, and scaling), computing the image hash, and the grouping of images based on a threshold value.

Categories
Recommended Image Processing Solutions
Recommended Opencv Solutions
Recommended Computer Vision Solutions

Previous Solution:

Fatal error: Class 'ZipArchive' not found in

PhpZipZiparchive

Next Solution:

Disable dragging an image from an HTML page

JavascriptJqueryHtmlCssImage

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionAlbertView Question on Stackoverflow
Solution 1 - Image ProcessingKarel PetranekView Answer on Stackoverflow
Solution 2 - Image ProcessingStereoMatchingView Answer on Stackoverflow
Solution 3 - Image ProcessingcarlosdcView Answer on Stackoverflow
Solution 4 - Image ProcessingMilan TenkView Answer on Stackoverflow
Solution 5 - Image ProcessingrcvView Answer on Stackoverflow
Solution 6 - Image ProcessingkiranpradeepView Answer on Stackoverflow
Solution 7 - Image ProcessingHua Er LimView Answer on Stackoverflow
Solution 8 - Image ProcessingLeoxView Answer on Stackoverflow
Solution 9 - Image ProcessingerdogantView Answer on Stackoverflow