Similar image search using an image

Question

I am working on a project in which the two images will be checked for similarity like 'Google Image Search by image'.

I searched through Google and also on various sites including stackoverflow and learnt about various techniques like histogram, sift, fourier transform, pixel grabbing, etc.

The things are too complex for me to understand being a beginner in this field.

My questions are:

1. From where can i get started?? Is there any book available or a site which give tutorials for learning about how to actually use these techniques?

2. Are there new techniques which can be implemented for this purpose??

I want to start searching images via color then if possible other attributes later.

Language preferred is Java.

There is a similar thread on this topic but it was written years ago.

Codify

Answer 1

I've made a tool named Images similarities searcher for this purpose as free software available at http://sourceforge.net/projects/imgndxr/

It use two libraries:

• LIRE : http://www.semanticmetadata.net/lire/

The LIRE (Lucene Image REtrieval) library provides a simple way to retrieve images and photos based on their color and texture characteristics. LIRE creates a Lucene index of image features for content based image retrieval (CBIR). Several different low level features are available, such as MPEG-7 ScalableColor, ColorLayout, and EdgeHistogram, Auto Color Correlogram, PHOG, CEDD, JCD, FCTH, and many more. Furthermore simple and extended methods for searching the index and result browsing are provided by LIRE. LIRE scales well up to millions of images with hash based approximate indexing. The LIRE library and the LIRE Demo application as well as all the source are available under the Gnu GPL license.

• LUCENE : http://lucene.apache.org/core/

Apache LuceneTM is a high-performance, full-featured text search engine library written entirely in Java. It is a technology suitable for nearly any application that requires full-text search, especially cross-platform.

Apache Lucene is an open source project available for free download. Please use the links on the right to access Lucene.

Discountenance

Your work is impressive but i want to work on the algorithms themselves, libraries provide predefined methods which might not be a good idea to use in my project – Codify

Thanks. :-) Do you think it's coherent with "The things are too complex for me to understand being a beginner in this field."? – Discountenance

Probably yes, i am just a beginner in this field. That's the whole reason for asking the question. – Codify

I'm interested by your future work. I you want to contribute to imgndxr, you're welcome! The first thing to do is a smaller, simpler replacement of LIRE. LUCENE is a facility to index a very large set of images like a database. – Discountenance

imgndxr is in bad shape, missing dependencies, etc, so I had to create my own solution (see below) – Moonshot

Answer 2

I got satisfactory results by resizing images to an 8x8 thumbnail and then taking the Mean Square Error of the 8-bit RGB color differences between the corresponding pixel in each image.

Step 1. Create thumbnails:

        BufferedImage img = ImageIO.read(src);
        Image thumbnail = img.getScaledInstance(8, 8, Image.SCALE_AREA_AVERAGING);

Check https://community.oracle.com/docs/DOC-983611 to understand why I chose the slower SCALE_AREA_AVERAGING over newer, faster methods.

Step 2. Convert Image thumbnails to BufferedImage by using the toBufferedImage method from Java converting Image to BufferedImage. Place the result into a List<BufferedImage>.

Step 3. Calculate the Mean Squared Error

This method takes two thumbnail-sized images of identical size and returns the difference. Zero means the images are very very similar:

public static double compare(BufferedImage img1, BufferedImage img2) {
    int width1 = img1.getWidth();
    int width2 = img2.getWidth();
    int height1 = img1.getHeight();
    int height2 = img2.getHeight();
    if ((width1 != width2) || (height1 != height2)) {
        throw new IllegalArgumentException("Error: Images dimensions mismatch");
    }

    int diff2 = 0;

    for (int i = 0; i < height1; i++) {
        for (int j = 0; j < width1; j++) {
            int rgb1 = img1.getRGB(j, i);
            int rgb2 = img2.getRGB(j, i);
            int r1 = (rgb1 >> 16) & 0xff;
            int g1 = (rgb1 >> 8) & 0xff;
            int b1 = (rgb1) & 0xff;
            int r2 = (rgb2 >> 16) & 0xff;
            int g2 = (rgb2 >> 8) & 0xff;
            int b2 = (rgb2) & 0xff;

            diff2 += Math.pow(r1 - r2, 2) + Math.pow(g1 - g2, 2) + Math.pow(b1 - b2, 2); 
        }
    }
    return diff2 * 1.0 / (height1*width1);
}

Step 4. Implement Search

This works by simply finding the image with the smallest difference. Depending on your use-case you may also want to set a threshold above which no image is returned. In my application the best match is always shown to the user so the user can decide if it is the correct image or not, so a hard-coded threshold is not necessary.

public BufferedImage findImage(List<BufferedImage> haystack, BufferedImage needle) {

    double lastDiff = Double.MAX_VALUE;
    BufferedImage winner = null;

    for(BufferedImage candidate: haystack) {
        double diff = compare(candidate, needle);
        if(diff < lastDiff) {
            lastDiff = diff;
            winner = candidate;
        }
    }
    return winner;
}

Moonshot

Answer 3

I just take reference of @Alex code and add some few more methods to take all specific files from location and process images one by one.

import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import javax.imageio.ImageIO;

public class ImageSearch {

    static HashMap<String, BufferedImage> imgMap = new HashMap<>();

    public static void main(String imgToFind, String...img2)throws IOException{
        System.out.println("---------------------Images is processing--------------------- ");
        search("path/to/images");
        System.out.println("----------------------Images processing is completed--------------------- ");
        System.out.println("----------------------Searching Images---------------------");
        System.out.println("Wiiner is :"+findImage(imgMap,getThumbnil(imgToFind)));
    }


    public static void search(String path) throws IOException{

        File file = new File(path);
        File[] fArray = file.listFiles();

        for (File f : fArray) {

            if (!f.isDirectory()) {
                if(f.getAbsolutePath().toUpperCase().endsWith(".JPG")){
                    BufferedImage bufImage = getThumbnil(f.getAbsolutePath());
                    imgMap.put(f.getAbsolutePath(), bufImage);
                }

            }

            if (f.isDirectory()) {
                search(f.getAbsolutePath());
            }

        }

    }


    public static BufferedImage getThumbnil(String imgSrc) throws IOException{
        BufferedImage img = ImageIO.read(new File(imgSrc));
        Image thumbnail = img.getScaledInstance(8, 8, Image.SCALE_AREA_AVERAGING);
        return toBufferedImage(thumbnail);
    }


    public static BufferedImage toBufferedImage(Image img)
    {
        if (img instanceof BufferedImage)
        {
            return (BufferedImage) img;
        }

        // Create a buffered image with transparency
        BufferedImage bimage = new BufferedImage(img.getWidth(null), img.getHeight(null), BufferedImage.TYPE_INT_ARGB);

        // Draw the image on to the buffered image
        Graphics2D bGr = bimage.createGraphics();
        bGr.drawImage(img, 0, 0, null);
        bGr.dispose();

        // Return the buffered image
        return bimage;
    }

    public static String findImage(HashMap<String, BufferedImage> imgMap, BufferedImage needle) {

        double lastDiff = Double.MAX_VALUE;
        BufferedImage winner = null;
        String winnerPath = "";

        for(Map.Entry<String, BufferedImage> candidate: imgMap.entrySet()) {

            String path = candidate.getKey();
            BufferedImage bufferedImage = candidate.getValue();

            double diff = compare(bufferedImage, needle);
            if(diff < lastDiff) {
                lastDiff = diff;
                winner = bufferedImage;
                System.out.println("path :"+path);
                winnerPath = path;
            }
        }
        return winnerPath;
    }

    public static double compare(BufferedImage img1, BufferedImage img2) {
        int width1 = img1.getWidth();
        int width2 = img2.getWidth();
        int height1 = img1.getHeight();
        int height2 = img2.getHeight();
        if ((width1 != width2) || (height1 != height2)) {
            throw new IllegalArgumentException("Error: Images dimensions mismatch");
        }

        int diff2 = 0;

        for (int i = 0; i < height1; i++) {
            for (int j = 0; j < width1; j++) {
                int rgb1 = img1.getRGB(j, i);
                int rgb2 = img2.getRGB(j, i);
                int r1 = (rgb1 >> 16) & 0xff;
                int g1 = (rgb1 >> 8) & 0xff;
                int b1 = (rgb1) & 0xff;
                int r2 = (rgb2 >> 16) & 0xff;
                int g2 = (rgb2 >> 8) & 0xff;
                int b2 = (rgb2) & 0xff;

                diff2 += Math.pow(r1 - r2, 2) + Math.pow(g1 - g2, 2) + Math.pow(b1 - b2, 2); 
            }
        }
        return diff2 * 1.0 / (height1*width1);
    }

}

Hope this will help.

Metrorrhagia

Answer 4

It depends on your use case. Are the images generic, or are they taken under similar lighting conditions and perspectives?

---

The approaches can be classified according to the complexity of the model. Essentially, we can distinguish direct vs feature-based approaches.

Direct (or intensity-based) methods attempt to (iteratively) estimate the similarity by minimizing an error function based on the intensity difference in the area of overlap. Each image must represent exactly the same scene with same scale, angle of view, etc. in order to overlap them. Similarity measurement can be achieved by computing the sum square difference (SSD) or ZSSD, the correlation coefficient (CC), the mutual information (MI) and the correlation ratio (RC).

Direct approaches can be useful e.g. to check just how well a new video compressing algorithms works. Take a look at the article below:

http://docs.opencv.org/trunk/doc/tutorials/highgui/video-input-psnr-ssim/video-input-psnr-ssim.html

---

On the other hand we can talk about feature-based approches. They try to establish correspondences between points, lines or other geometrical entities for estimating the camera parameters. They can be useful when the structural units of an image (pixels) does not contain sufficient information about its content. Hence, feature-based approaches try to represent image content in terms of mathematical features (n-dimensional vectors), and then use classifiers to compare these features in order to get a measure regarding their similarities.

Hollie

Tutorial is nice and helpful. For starter i want to compare two images by color and obtain results like Google Image Search finds(not that good maybe). Can PSNR and SSIM be used for this purpose?? Or are there any other algorithms for this? I'll check more about SSIM – Codify

PSNR and SSIM are just two very simple metric to measure similarity between two images. They will not work if you want to compare two image of sunflower, so that one of the images contains the sunflower in left-upper corner as well as the other one contains it in the right-bottom. The whole research field dealing with search-image-base-by-image is called Content Based Image Retrieval (CBIR). – Hollie

You should also have a look at to the followings: 1, 2, 3 – Hollie