Letter inside a letter, pattern recognition

Question

I would like to discover this pattern

As you can see mainly the letter C, inside another, with different orientations. My template can have multiple Cs inside each other, the one I submit using 2 C is just a sample. I would like to determine how much C is, and the orientation of each of them. At the moment, I managed to find the center of such a pattern, basically I managed to find the center of the innermost C. Could you give me any ideas about the various algorithms that I could use?

Answer 1

And here we go! High Level Overview This approach can be described as the sequential execution of the following steps:

• Download the input image ;
• Convert it to shades of gray ;
• Threshold for binary image generation;
• Use binary image to find outlines ;
• Fill each contour area with a different color (so that we can extract each letter separately);
• Create a mask for each letter found to isolate them in separate images ;
• Crop images to the smallest possible size ;
• Highlight the center of the image;
• Define the width of the border of the letter to determine the exact center of the border;
• Scan along the border (in a circular manner) to break;
• Print the approximate angle of the gap, thus determining the amount of rotation of the letter.

I don't want to go into details because I use the source code, so feel free to test and modify it in any way. Let it begin, winter is coming:

#include <iostream> #include <vector> #include <cmath> #include <opencv2/highgui/highgui.hpp> #include <opencv2/imgproc/imgproc.hpp> cv::RNG rng(12345); float PI = std::atan(1) * 4; void isolate_object(const cv::Mat& input, cv::Mat& output) { if (input.channels() != 1) { std::cout << "isolate_object: !!! input must be grayscale" << std::endl; return; } // Store the set of points in the image before assembling the bounding box std::vector<cv::Point> points; cv::Mat_<uchar>::const_iterator it = input.begin<uchar>(); cv::Mat_<uchar>::const_iterator end = input.end<uchar>(); for (; it != end; ++it) { if (*it) points.push_back(it.pos()); } // Compute minimal bounding box cv::RotatedRect box = cv::minAreaRect(cv::Mat(points)); // Set Region of Interest to the area defined by the box cv::Rect roi; roi.x = box.center.x - (box.size.width / 2); roi.y = box.center.y - (box.size.height / 2); roi.width = box.size.width; roi.height = box.size.height; // Crop the original image to the defined ROI output = input(roi); } 

For more information on the implementation of isolate_object() , please check this thread . cv::RNG used later to fill each path with a different color and PI , well ... you know PI .

 int main(int argc, char* argv[]) { // Load input (colored, 3-channel, BGR) cv::Mat input = cv::imread("test.jpg"); if (input.empty()) { std::cout << "!!! Failed imread() #1" << std::endl; return -1; } // Convert colored image to grayscale cv::Mat gray; cv::cvtColor(input, gray, CV_BGR2GRAY); // Execute a threshold operation to get a binary image from the grayscale cv::Mat binary; cv::threshold(gray, binary, 128, 255, cv::THRESH_BINARY); 

The binary image looks exactly the same as the input, because it only had 2 colors (B & W):

  // Find the contours of the C in the thresholded image std::vector<std::vector<cv::Point> > contours; cv::findContours(binary, contours, cv::RETR_LIST, cv::CHAIN_APPROX_SIMPLE); // Fill the contours found with unique colors to isolate them later cv::Mat colored_contours = input.clone(); std::vector<cv::Scalar> fill_colors; for (size_t i = 0; i < contours.size(); i++) { std::vector<cv::Point> cnt = contours[i]; double area = cv::contourArea(cv::Mat(cnt)); //std::cout << "* Area: " << area << std::endl; // Fill each C found with a different color. // If the area is larger than 100k it probably the white background, so we ignore it. if (area > 10000 && area < 100000) { cv::Scalar color = cv::Scalar(rng.uniform(0, 255), rng.uniform(0,255), rng.uniform(0,255)); cv::drawContours(colored_contours, contours, i, color, CV_FILLED, 8, std::vector<cv::Vec4i>(), 0, cv::Point()); fill_colors.push_back(color); //cv::imwrite("test_contours.jpg", colored_contours); } } 

What color_contours looks like :

  // Create a mask for each C found to isolate them from each other for (int i = 0; i < fill_colors.size(); i++) { // After inRange() single_color_mask stores a single C letter cv::Mat single_color_mask = cv::Mat::zeros(input.size(), CV_8UC1); cv::inRange(colored_contours, fill_colors[i], fill_colors[i], single_color_mask); //cv::imwrite("test_mask.jpg", single_color_mask); 

Since this for loop runs twice, one for each color that was used to fill the paths, I want you to see all the images created at this point. Thus, the following images are those that were saved by single_color_mask (one for each iteration of the loop):

  // Crop image to the area of the object cv::Mat cropped; isolate_object(single_color_mask, cropped); //cv::imwrite("test_cropped.jpg", cropped); cv::Mat orig_cropped = cropped.clone(); 

These are the ones that were kept trimmed (by the way, the smaller C looks thick because the image is rescaled by this page to have the same size as the larger C, no worries):

  // Figure out the center of the image cv::Point obj_center(cropped.cols/2, cropped.rows/2); //cv::circle(cropped, obj_center, 3, cv::Scalar(128, 128, 128)); //cv::imwrite("test_cropped_center.jpg", cropped); 

To better understand what obj_center is for , I drew a small gray circle for educational purposes in this place:

  // Figure out the exact center location of the border std::vector<cv::Point> border_points; for (int y = 0; y < cropped.cols; y++) { if (cropped.at<uchar>(obj_center.x, y) != 0) border_points.push_back(cv::Point(obj_center.x, y)); if (border_points.size() > 0 && cropped.at<uchar>(obj_center.x, y) == 0) break; } if (border_points.size() == 0) { std::cout << "!!! Oops! No border detected." << std::endl; return 0; } // Figure out the exact center location of the border cv::Point border_center = border_points[border_points.size() / 2]; //cv::circle(cropped, border_center, 3, cv::Scalar(128, 128, 128)); //cv::imwrite("test_border_center.jpg", cropped); 

The above procedure scans one vertical line at the top / in the middle of the image to find the borders of the circle in order to be able to calculate the width. Again, for educational purposes, I drew a small gray circle in the middle of the border. Here's what the cropped looks like:

  // Scan the border of the circle for discontinuities int radius = obj_center.y - border_center.y; if (radius < 0) radius *= -1; std::vector<cv::Point> discontinuity_points; std::vector<int> discontinuity_angles; for (int angle = 0; angle <= 360; angle++) { int x = obj_center.x + (radius * cos((angle+90) * (PI / 180.f))); int y = obj_center.y + (radius * sin((angle+90) * (PI / 180.f))); if (cropped.at<uchar>(x, y) < 128) { discontinuity_points.push_back(cv::Point(y, x)); discontinuity_angles.push_back(angle); //cv::circle(cropped, cv::Point(y, x), 1, cv::Scalar(128, 128, 128)); } } //std::cout << "Discontinuity size: " << discontinuity_points.size() << std::endl; if (discontinuity_points.size() == 0 && discontinuity_angles.size() == 0) { std::cout << "!!! Oops! No discontinuity detected. It a perfect circle, dang!" << std::endl; return 0; } 

Great, so the code above scans the middle of the circle border, looking for a gap. I am sharing a sample to illustrate what I mean. Each gray dot in the image represents a pixel that is being tested. When the pixel is black, it means that we have detected a gap:

  // Figure out the approximate angle of the discontinuity: // the first angle found will suffice for this demo. int approx_angle = discontinuity_angles[0]; std::cout << "#" << i << " letter C is rotated approximately at: " << approx_angle << " degrees" << std::endl; // Figure out the central point of the discontinuity cv::Point discontinuity_center; for (int a = 0; a < discontinuity_points.size(); a++) discontinuity_center += discontinuity_points[a]; discontinuity_center.x /= discontinuity_points.size(); discontinuity_center.y /= discontinuity_points.size(); cv::circle(orig_cropped, discontinuity_center, 2, cv::Scalar(128, 128, 128)); cv::imshow("Original crop", orig_cropped); cv::waitKey(0); } return 0; } 

Very good ... This last piece of code is responsible for determining the approximate angle of the gap, and also points to the center point of the gap. The following images are stored in orig_cropped . Once again, I added a gray dot to show the exact positions found as the center of the breaks:

When executed, this application displays the following information:

 #0 letter C is rotated approximately at: 49 degrees #1 letter C is rotated approximately at: 0 degrees 

Hope this helps.

Answer 2

For starters, you can use the Hough transform. This algorithm is not very fast, but it is quite robust. Especially if you have clear images.

General approach:

 1) preprocessing - suppress noise, convert to grayscale / binary 2) run edge detector 3) run Hough transform - IIRC it `cv::HoughCircles` in OpenCV 4) do some postprocessing - remove surplus circles, decide which ones correspond to shape of letter C, and so on 

My approach will give you two circles for the letter C. One on the inner border, one on the outer letter C. If you want only one circle for the letter, you can use the skeletonization algorithm. More details here http://homepages.inf.ed.ac.uk/rbf/HIPR2/skeleton.htm

Answer 3

Given that we have nested C-structures, and you know the Cs centers and want to evaluate the orientation, you just need to observe the distribution of pixels along the radius of concentric Cs in all directions.

This can be done by performing a simple morphological dilatation from the center. When we reach the right radius for the innermost C, we will reach the maximum number of pixels covered for the innermost C. The difference between the drive and C will give us a gap point in general, and you can perform erosion limits to get the centroid of the gap in C. The angle between the center and this point is the orientation of C. This step is repeated until all Cs are covered.

This can also be done quickly using the Cs center distance function .