How to extract different shapes from an Image

Question

I am a newbie in Image processing world and I have a problem statement which I need a head start to solve it.

Problem Statement:

I have an image which consist of a pattern. This pattern is created using different individual shapes. Below is the pattern and the individual shape used to form the pattern.

Detailed problem statement:

I have 15 unique shapes(image below) using which I can draw different patterns(one example is given already). I have more than 400 patterns. I want to use image processing to find out different shapes (and its position in the pattern) used to generate a particular pattern.

All unique shapes: Some more pattern images:

What I want to achieve:

I want to input the pattern image and find out the individual shapes which are used to form the pattern and the position the shapes are placed in the pattern ?:

Note: I have not included all the individual shapes as the question was becoming too big.

Pattern Image:

Individual Shapes:

Answer 1

To know which reference shapes compose your images, you can

1. localize the central dot which is present in all your shapes
2. knowing where the dot is, find the correct shape.

---

For the scope of this answer I use these images which are already preprocessed. The first image is simply thresholded, for the second I used this snippet.

---

Find the central dots is pretty easy on the preprocessed images. You can use cv::connectedComponentsWithStats to retrieve all black components, and then remove the ones that are too big. You can find the code in the function getCenterPoints below.

Then you can easily get the outlines (needed later) with a simple combination of this image and the original one:

Now we are able to find the dots, but we need also a way to say which shape compose the final image. We can use the geometry of the shape to build a simple descriptor for each shape: we save in a Mat 4 values representing the distance of the center from the outline in vertical and horizontal direction:

This uniquely identifies all your reference shapes. Then we normalize this 4 element vector so it becomes scale-invariant. Using this descriptor allow us to avoid tedious "multiscale template matching" like stuff, and is also much faster and extendible. You can find the code for this in the function computeShapeDescriptor below.

In order to compute the shape descriptor we need also the correct position of the shape center, which is simply the centroid of the blob we found earlier. We basically use again cv::connectedComponentWithStats. See getCentroids below.

---

Now we know how to find the dots to localize all shapes, and know how to describe them. To find the corresponding reference shape in the image simply compare the descriptors. The one most similar would be the correct one!

Full code for reference:

#include <opencv2\opencv.hpp>
#include <vector>

void computeShapeDescriptor(const cv::Mat1b shape_outline, cv::Point center, cv::Mat1d& desc)
{
    desc = cv::Mat1d(1, 4, 0.0);

    // Go up until I find a outline pixel
    for (int i = center.y; i >= 0; --i) {
        if (shape_outline(i, center.x) > 0) {
            desc(0) = std::abs(i - center.y);
            break;
        }
    }
    // Go right until I find a outline pixel
    for (int i = center.x; i < shape_outline.cols; ++i) {
        if (shape_outline(center.y, i) > 0) {
            desc(1) = std::abs(i - center.x);
            break;
        }
    }
    // Go down until I find a outline pixel
    for (int i = center.y; i < shape_outline.rows; ++i) {
        if (shape_outline(i, center.x) > 0) {
            desc(2) = std::abs(i - center.y);
            break;
        }
    }
    // Go left until I find a outline pixel
    for (int i = center.x; i >= 0; --i) {
        if (shape_outline(center.y, i) > 0) {
            desc(3) = std::abs(i - center.x);
            break;
        }
    }

    desc /= cv::norm(desc, cv::NORM_L1);
}

void getCenterPoints(const cv::Mat1b& src, cv::Mat1b& dst)
{
    dst = cv::Mat1b(src.rows, src.cols, uchar(0));

    cv::Mat1i labels;
    cv::Mat1i stats;
    cv::Mat1d centroids;
    int n_labels = cv::connectedComponentsWithStats(~src, labels, stats, centroids);
    for (int i = 1; i < n_labels; ++i) {
        if (stats(i, cv::CC_STAT_AREA) < 100)
        {
            dst.setTo(255, labels == i);
        }
    }
}

void getCentroids(const cv::Mat1b& src, cv::Mat1d& centroids)
{
    // Find the central pixel
    cv::Mat1i labels;
    cv::Mat1i stats;

    cv::connectedComponentsWithStats(src, labels, stats, centroids);
    // 'centroids' contains in each row x,y coordinates of the centroid
}


int main()
{
    // Load the reference shapes
    cv::Mat1b reference = cv::imread("path_to_reference_shapes", cv::IMREAD_GRAYSCALE);

    // -------------------------
    // Compute descriptor for each reference shape
    // -------------------------

    // Get the centers
    cv::Mat1b reference_centers;
    getCenterPoints(reference, reference_centers);

    // Get the centroids
    cv::Mat1d shape_centroids;
    getCentroids(reference_centers, shape_centroids);

    // Find the outline
    cv::Mat1b reference_outline = ~(reference | reference_centers);

    // Prepare output image
    cv::Mat3b reference_output;
    cv::cvtColor(reference, reference_output, cv::COLOR_GRAY2BGR);

    // Compute the descriptor for each shape
    std::vector<cv::Mat1f> shape_descriptors;
    for (int i = 1; i < shape_centroids.rows; ++i)
    {
        cv::Point center;
        center.x = std::round(shape_centroids(i, 0));
        center.y = std::round(shape_centroids(i, 1));

        cv::Mat1d desc;
        computeShapeDescriptor(reference_outline, center, desc);

        shape_descriptors.push_back(desc.clone());

        // Draw the ID of the shape
        cv::putText(reference_output, cv::String(std::to_string(i)), center, cv::FONT_HERSHEY_PLAIN, 1, cv::Scalar(0, 0, 255));
    }

    // -------------------------
    // Find shapes in image
    // -------------------------

    cv::Mat1b img = cv::imread("path_to_image", cv::IMREAD_GRAYSCALE);

    // Get the centers
    cv::Mat1b img_centers;
    getCenterPoints(img, img_centers);

    // Get the centroids
    cv::Mat1d img_centroids;
    getCentroids(img_centers, img_centroids);

    // Find the outline
    cv::Mat1b img_outline = ~(img | img_centers);

    // Prepare output image
    cv::Mat3b img_output;
    cv::cvtColor(img, img_output, cv::COLOR_GRAY2BGR);

    // Compute the descriptor for each found shape, and assign to nearest descriptor among reference shapes
    for (int i = 1; i < img_centroids.rows; ++i)
    {
        cv::Point center;
        center.x = std::round(img_centroids(i, 0));
        center.y = std::round(img_centroids(i, 1));

        cv::Mat1d desc;
        computeShapeDescriptor(img_outline, center, desc);

        // Compute the distance with all reference descriptors
        double minDist = 1e10;
        int minIdx = 0;
        for (size_t j = 0; j < shape_descriptors.size(); ++j)
        {
            // Actual distance computation
            double dist = 0.0;
            for (int c = 0; c < desc.cols; ++c) {
                dist += std::abs(desc(c) - shape_descriptors[j](c));
            }

            if (minDist > dist) {
                minDist = dist;
                minIdx = j;
            }
        }

        // Draw the ID of the shape
        cv::putText(img_output, cv::String(std::to_string(minIdx + 1)), center, cv::FONT_HERSHEY_PLAIN, 1, cv::Scalar(0, 0, 255, 255));
    }


    return 0;
}

Answer 2

You can use the dots to locate the individual shapes (binarization + connected components labeling).

Then it is an easy matter to detect the absence/presence of square corners, for instance by means of small windows between pairs of neighboring shapes. This will give you a binary code that you can use to distinguish your patterns.

Answer 3

Considering you have a dictionary of shapes, you could template matching to find which shape is where in your image. Template matching is fairly simple: you compute a "goodness of fit" measure such as correlation, mean squared error, etc. for the shape and the image, with the shape positioned at every point in your image. See for example these lecture notes. If you use correlation (which makes sense in this case), you can use the FFT to speed up computation significantly. Look for example at this OpenCV tutorial.

The above assumes that the templates are at the same scale and orientation as shown in the image. If the sizes can differ, you need to use a multi-scale template matching approach, which I is slightly more involved but not difficult. Simply try to match each shape multiple times, at different scales and orientations. Or rotate and scale your image. I presume that, given your examples, you only need to test 4 orientations and 1 scale, so this is a reasonable approach.

The more flexible approach is to detect the dots (use e.g. template matching for that), flood-fill around the dots to fill the shape (assuming that they are all simple polygons), and extract the boundary of the detected area. That boundary can then be matched to the ones in your dictionary using e.g. Fourier descriptors. This would allow you to detect the shapes at arbitrary scales and orientations.