Detecting All Occurrences of Subimage Within Image

Question

Recently, I've been developing a small side project that needs the ability to find the X & Y coordinates of a subimage within another image. The images might be in different resolutions, but overall the image resolutions will be similar and the colors should be the same. I have looked into OpenCV, but it seems that OpenCV only returns a single match. I need to find all occurrences/instances of the subimage inside of the super-image. I already have all of the subimages to search for, so I am only in need of a way to find the coordinates of the subimages within the super-image.

Here's an example of what I mean:

If we have red_circle.png:

and shapes.png:

I need to get the X & Y coordinates for all of the red circles (red_circle.png; subimage) within the picture of various shapes (shapes.png; super-image).

Ideally, I would like to be able to do something like this:

/* code to read in red_cirlce.png and shapes.png as BufferedImages */
ArrayList<Point> instancesOfRedCircle = new ArrayList<>();
findAllSubimageInstances( shapesObj, // Super-Image
                          redCircleObj, // Subimage
                          instancesOfRedCircle // ArrayList to put points in
                        );

Does anybody know of a way to do this (eg, a library, a function, etcetera)?

Answer 1

I could not sleep that nigth..

I have written the code from the tuorial in java and build a little gui around it.

package opencv.test;

import java.awt.image.BufferedImage;
import java.io.ByteArrayInputStream;
import java.io.File;
import java.io.InputStream;

import javax.imageio.ImageIO;

import org.opencv.core.Core;
import org.opencv.core.Mat;
import org.opencv.core.MatOfByte;
import org.opencv.core.MatOfDMatch;
import org.opencv.core.MatOfKeyPoint;
import org.opencv.core.Scalar;
import org.opencv.features2d.DMatch;
import org.opencv.features2d.DescriptorExtractor;
import org.opencv.features2d.DescriptorMatcher;
import org.opencv.features2d.FeatureDetector;
import org.opencv.features2d.Features2d;
import org.opencv.highgui.Highgui;

public class MatchDetection {

    public static BufferedImage detectMatches(File file, File file2) {

        System.loadLibrary(Core.NATIVE_LIBRARY_NAME);

        Mat img_1 = Highgui.imread(file.getAbsolutePath(), Highgui.CV_LOAD_IMAGE_GRAYSCALE);
        Mat img_2 = Highgui.imread(file2.getAbsolutePath(), Highgui.CV_LOAD_IMAGE_GRAYSCALE);

        if (img_1.empty() || img_2.empty()) {
            System.out.println(" --(!) Error reading images ");
            return null;
        }

        // -- Step 1: Detect the keypoints using SURF Detector
        //I am not sure where to use it
        int minHessian = 400;

        FeatureDetector detector = FeatureDetector.create(FeatureDetector.SURF);

        MatOfKeyPoint keypoints_1 = new MatOfKeyPoint();
        MatOfKeyPoint keypoints_2 = new MatOfKeyPoint();

        detector.detect(img_1, keypoints_1);
        detector.detect(img_2, keypoints_2);

        // -- Step 2: Calculate descriptors (feature vectors)
        DescriptorExtractor extractor = DescriptorExtractor
                .create(DescriptorExtractor.SURF);

        Mat descriptors_1 = new Mat();
        Mat descriptors_2 = new Mat();

        extractor.compute(img_1, keypoints_1, descriptors_1);
        extractor.compute(img_2, keypoints_2, descriptors_2);

        // -- Step 3: Matching descriptor vectors using FLANN matcher
        DescriptorMatcher matcher = DescriptorMatcher
                .create(DescriptorExtractor.SURF);
        MatOfDMatch matches = new MatOfDMatch();
        matcher.match(descriptors_1, descriptors_2, matches);
        DMatch[] matchesArr = matches.toArray();

        double max_dist = 0;
        double min_dist = 100;

        // -- Quick calculation of max and min distances between keypoints
        for (int i = 0; i < matchesArr.length; i++) {
            double dist = matchesArr[i].distance;
            if (dist < min_dist)
                min_dist = dist;
            if (dist > max_dist)
                max_dist = dist;
        }

        System.out.printf("-- Max dist : %f \n", max_dist);
        System.out.printf("-- Min dist : %f \n", min_dist);

        // -- Draw only "good" matches (i.e. whose distance is less than
        // 2*min_dist,
        // -- or a small arbitary value ( 0.02 ) in the event that min_dist is
        // very
        // -- small)
        // -- PS.- radiusMatch can also be used here.
        MatOfDMatch good_matches = new MatOfDMatch();

        for (int i = 0; i < matchesArr.length; i++) {
            if (matchesArr[i].distance <= Math.max(2 * min_dist, 0.02)) {
                good_matches.push_back(matches.row(i));
            }
        }

        // -- Draw only "good" matches
        Mat img_matches = new Mat();
        Features2d.drawMatches(img_1, keypoints_1, img_2, keypoints_2,
                good_matches, img_matches);//, Scalar.all(-1), Scalar.all(-1),
                //null, Features2d.NOT_DRAW_SINGLE_POINTS);

        // ----Here i had to Patch around a little----
        MatOfByte matOfByte = new MatOfByte();

        Highgui.imencode(".jpg", img_matches, matOfByte);

        byte[] byteArray = matOfByte.toArray();
        BufferedImage bufImage = null;
        try {

            InputStream in = new ByteArrayInputStream(byteArray);
            bufImage = ImageIO.read(in);
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }

        for (int i = 0; i < (int) good_matches.rows(); i++) {
            System.out.printf(
                    "-- Good Match [%d] Keypoint 1: %d  -- Keypoint 2: %d  \n",
                    i, good_matches.toArray()[i].queryIdx,
                    good_matches.toArray()[i].trainIdx);
        }

        return bufImage;

    }
}

and the GUI

package opencv.test;

import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.event.FocusEvent;
import java.awt.event.FocusListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;
import javax.swing.JFileChooser;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.filechooser.FileNameExtensionFilter;
import java.awt.GridBagLayout;
import java.awt.GridBagConstraints;
import java.awt.Insets;

public class OpenCVMyGui {

    private JFrame frame;
    ImageResultPanel panel_bot;
    ImageChoosePanel panel_left;
    ImageChoosePanel panel_right;

    /**
     * Launch the application.
     */
    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {
            public void run() {
                try {
                    OpenCVMyGui window = new OpenCVMyGui();
                    window.frame.setVisible(true);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });
    }

    /**
     * Create the application.
     */
    public OpenCVMyGui() {
        initialize();
    }

    /**
     * Initialize the contents of the frame.
     */
    private void initialize() {
        frame = new JFrame();
        frame.setBounds(100, 100, 450, 300);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        GridBagLayout gridBagLayout = new GridBagLayout();
        gridBagLayout.columnWidths = new int[]{0, 0, 0};
        gridBagLayout.rowHeights = new int[]{0, 0, 0};
        gridBagLayout.columnWeights = new double[]{1.0, 1.0, Double.MIN_VALUE};
        gridBagLayout.rowWeights = new double[]{1.0, 1.0, Double.MIN_VALUE};
        frame.getContentPane().setLayout(gridBagLayout);

        panel_left = new ImageChoosePanel();
        GridBagConstraints gbc_panel_2 = new GridBagConstraints();
        gbc_panel_2.insets = new Insets(0, 0, 5, 5);
        gbc_panel_2.fill = GridBagConstraints.BOTH;
        gbc_panel_2.gridx = 0;
        gbc_panel_2.gridy = 0;
        frame.getContentPane().add(panel_left, gbc_panel_2);

        panel_right = new ImageChoosePanel();
        GridBagConstraints gbc_panel_1 = new GridBagConstraints();
        gbc_panel_1.insets = new Insets(0, 0, 5, 0);
        gbc_panel_1.fill = GridBagConstraints.BOTH;
        gbc_panel_1.gridx = 1;
        gbc_panel_1.gridy = 0;
        frame.getContentPane().add(panel_right, gbc_panel_1);

        panel_bot = new ImageResultPanel(this);
        GridBagConstraints gbc_panel = new GridBagConstraints();
        gbc_panel.gridwidth = 2;
        gbc_panel.fill = GridBagConstraints.BOTH;
        gbc_panel.gridx = 0;
        gbc_panel.gridy = 1;
        frame.getContentPane().add(panel_bot, gbc_panel);
    }

    private class ImageChoosePanel extends JPanel {

        /**
         * 
         */
        private static final long serialVersionUID = 2207576827793103205L;
        public BufferedImage image;
        public File file;

        public ImageChoosePanel() {
            setFocusable(true);
            addMouseListener(new MouseListener() {

                @Override
                public void mouseReleased(MouseEvent e) {
                }

                @Override
                public void mousePressed(MouseEvent e) {
                }

                @Override
                public void mouseExited(MouseEvent e) {
                }

                @Override
                public void mouseEntered(MouseEvent e) {
                }

                @Override
                public void mouseClicked(MouseEvent e) {
                    JFileChooser chooser = new JFileChooser();
                    chooser.setFileSelectionMode(JFileChooser.FILES_ONLY);
                    chooser.setFileFilter(new FileNameExtensionFilter("Images",
                            "jpg", "png")); // maybe more? dont know what OpenCV
                                            // likes
                    chooser.showOpenDialog(ImageChoosePanel.this);
                    ImageChoosePanel icp = ((ImageChoosePanel) e.getSource());
                    icp.file = chooser.getSelectedFile();
                    try {
                        image = ImageIO.read(icp.file);
                    } catch (IOException ex) {
                        ex.printStackTrace();
                    }
                }
            });
        }

        @Override
        public void paint(Graphics arg0) {

            if (image != null) {
                arg0.drawImage(image, 0, 0, null);
            } else{ 
                arg0.fillRect(0, 0, getWidth(), getHeight());
            }
        }
    }

    private class ImageResultPanel extends JPanel {

        /**
         * 
         */
        private static final long serialVersionUID = 8948107638933808175L;
        public BufferedImage image;
        OpenCVMyGui gui;

        public ImageResultPanel(OpenCVMyGui gui) {
            this.gui = gui;
            setFocusable(true);
            addMouseListener(new MouseListener() {

                @Override
                public void mouseReleased(MouseEvent arg0) {
                }

                @Override
                public void mousePressed(MouseEvent arg0) {
                }

                @Override
                public void mouseExited(MouseEvent arg0) {
                }

                @Override
                public void mouseEntered(MouseEvent arg0) {
                }

                @Override
                public void mouseClicked(MouseEvent arg0) {
                    try {
                        OpenCVMyGui gui = ((ImageResultPanel) arg0.getSource()).gui;
                        image = MatchDetection.detectMatches(
                                gui.panel_right.file, gui.panel_left.file);
                    } catch (Exception e2) {
                        e2.printStackTrace();
                    }
                }
            });
        }

        @Override
        public void paint(Graphics arg0) {
            if (image != null) {
                arg0.drawImage(image, 0, 0, null);
            }else{
                arg0.fillRect(0, 0, getWidth(), getHeight());
            }
        }
    }

}

You should definity play around with the algorithms... but the result atm should help you with your goals.

I might read over it again. Tomorrow.