One way to do pattern matching is to use cv :: matchTemplate.
This takes an input image and a smaller image that acts as a template. It compares the template with areas with overlapping image, calculating the similarity of the template with the overlapping area. Several methods for calculating comparisons are available.
These methods do not directly support scale or orientation invariance. But you can overcome this by scaling the candidates to a control size and by testing against several rotating patterns.
A detailed example of this method is shown to determine the pressure and location of coins 50c. The same procedure can be applied to other coins.
Two programs will be built. One for creating templates from a large image template for a 50c coin. And one more that accepts those templates as input, as well as an image with coins and displays an image in which 50c coins are marked.
Template creator
#define TEMPLATE_IMG "50c.jpg" #define ANGLE_STEP 30 int main() { cv::Mat image = loadImage(TEMPLATE_IMG); cv::Mat mask = createMask( image ); cv::Mat loc = locate( mask ); cv::Mat imageCS; cv::Mat maskCS; centerAndScale( image, mask, loc, imageCS, maskCS); saveRotatedTemplates( imageCS, maskCS, ANGLE_STEP ); return 0; }
Here we upload an image that will be used to build our templates.
Separate it to create a mask.
Find the center of mass of the specified mask.
And we scale and copy this mask and coin so that they occupy a square of a fixed size, where the edges of the square touch the circumference of the mask and coin. That is, the side of the square has the same length in pixels, like the diameter of a scaled mask or image of a coin.
Finally, we save this scaled and centered image of the coin. And we save additional copies that it rotates in increments with a fixed angle.
cv::Mat loadImage(const char* name) { cv::Mat image; image = cv::imread(name); if ( image.data==NULL || image.channels()!=3 ) { std::cout << name << " could not be read or is not correct." << std::endl; exit(1); } return image; }
loadImage uses cv::imread to read the image. Checks that the data has been read and the image has three channels and returns the read image.
#define THRESHOLD_BLUE 130 #define THRESHOLD_TYPE_BLUE cv::THRESH_BINARY_INV #define THRESHOLD_GREEN 230 #define THRESHOLD_TYPE_GREEN cv::THRESH_BINARY_INV #define THRESHOLD_RED 140 #define THRESHOLD_TYPE_RED cv::THRESH_BINARY #define CLOSE_ITERATIONS 5 cv::Mat createMask(const cv::Mat& image) { cv::Mat channels[3]; cv::split( image, channels); cv::Mat mask[3]; cv::threshold( channels[0], mask[0], THRESHOLD_BLUE , 255, THRESHOLD_TYPE_BLUE ); cv::threshold( channels[1], mask[1], THRESHOLD_GREEN, 255, THRESHOLD_TYPE_GREEN ); cv::threshold( channels[2], mask[2], THRESHOLD_RED , 255, THRESHOLD_TYPE_RED ); cv::Mat compositeMask; cv::bitwise_and( mask[0], mask[1], compositeMask); cv::bitwise_and( compositeMask, mask[2], compositeMask); cv::morphologyEx(compositeMask, compositeMask, cv::MORPH_CLOSE, cv::Mat(), cv::Point(-1, -1), CLOSE_ITERATIONS );
createMask performs template segmentation. It binarizes each of the BGR channels, makes AND of these three binarized images, and performs the CLOSE morphological operation to create the mask.
Three lines of debugging copy the original image in black, using the calculated mask as a mask for the copy operation. This helped to select the correct threshold values.
Here we can see a 50c image filtered by a mask created in createMask
cv::Mat locate( const cv::Mat& mask ) { // Compute center and radius. cv::Moments moments = cv::moments( mask, true); float area = moments.m00; float radius = sqrt( area/M_PI ); float xCentroid = moments.m10/moments.m00; float yCentroid = moments.m01/moments.m00; float m[1][3] = {{ xCentroid, yCentroid, radius}}; return cv::Mat(1, 3, CV_32F, m); }
locate calculates the center of mass of the mask and its radius. Returning these 3 values in a single line match in the form {x, y, radius}.
It uses cv::moments , which calculates all moments up to the third order of a polygon or rasterized shape. Rasterized form in our case. We are not interested in all these points. But three of them are useful here. M00 is the area of the mask. And the centroid can be calculated from m00, m10 and m01.
void centerAndScale(const cv::Mat& image, const cv::Mat& mask, const cv::Mat& characteristics, cv::Mat& imageCS, cv::Mat& maskCS) { float radius = characteristics.at<float>(0,2); float xCenter = characteristics.at<float>(0,0); float yCenter = characteristics.at<float>(0,1); int diameter = round(radius*2); int xOrg = round(xCenter-radius); int yOrg = round(yCenter-radius); cv::Rect roiOrg = cv::Rect( xOrg, yOrg, diameter, diameter ); cv::Mat roiImg = image(roiOrg); cv::Mat roiMask = mask(roiOrg); cv::Mat centered = cv::Mat::zeros( diameter, diameter, CV_8UC3); roiImg.copyTo( centered, roiMask); cv::imwrite( "centered.bmp", centered); // debug imageCS.create( TEMPLATE_SIZE, TEMPLATE_SIZE, CV_8UC3); cv::resize( centered, imageCS, cv::Size(TEMPLATE_SIZE,TEMPLATE_SIZE), 0, 0 ); cv::imwrite( "scaled.bmp", imageCS); // debug roiMask.copyTo(centered); cv::resize( centered, maskCS, cv::Size(TEMPLATE_SIZE,TEMPLATE_SIZE), 0, 0 ); }
centerAndScale uses the centroid and radius calculated by locate to get the area of interest of the input image and the area of interest of the mask, so the center of such areas is also the center of the coin and the mask and the lateral length of the areas are equal to the diameter of the coin / mask.
These regions are subsequently scaled to a fixed TEMPLATE_SIZE. This scaled region will be our reference template. When later in the matching program we want to check whether the candidate coin detected is a coin, we also take the candidate coin area, center and scale this candidate coin in the same way as before template matching. Thus, we achieve scale invariance.
void saveRotatedTemplates( const cv::Mat& image, const cv::Mat& mask, int stepAngle ) { char name[1000]; cv::Mat rotated( TEMPLATE_SIZE, TEMPLATE_SIZE, CV_8UC3 ); for ( int angle=0; angle<360; angle+=stepAngle ) { cv::Point2f center( TEMPLATE_SIZE/2, TEMPLATE_SIZE/2); cv::Mat r = cv::getRotationMatrix2D(center, angle, 1.0); cv::warpAffine(image, rotated, r, cv::Size(TEMPLATE_SIZE, TEMPLATE_SIZE)); sprintf( name, "template-%03d.bmp", angle); cv::imwrite( name, rotated ); cv::warpAffine(mask, rotated, r, cv::Size(TEMPLATE_SIZE, TEMPLATE_SIZE)); sprintf( name, "templateMask-%03d.bmp", angle); cv::imwrite( name, rotated ); } }
saveRotatedTemplates saves the previous computed template.
But it saves several copies, each of which is rotated by the angle defined in ANGLE_STEP . The purpose of this is to ensure approximate invariance. The lower we define stepAngle the better orientation invariance we get, but also mean higher computational cost.
You can download the full template program here .
When starting with ANGLE_STEP as 30, I get the following 12 patterns:
Pattern matching.
#define INPUT_IMAGE "coins.jpg" #define LABELED_IMAGE "coins_with50cLabeled.bmp" #define LABEL "50c" #define MATCH_THRESHOLD 0.065 #define ANGLE_STEP 30 int main() { vector<cv::Mat> templates; loadTemplates( templates, ANGLE_STEP ); cv::Mat image = loadImage( INPUT_IMAGE ); cv::Mat mask = createMask( image ); vector<Candidate> candidates; getCandidates( image, mask, candidates ); saveCandidates( candidates ); // debug matchCandidates( templates, candidates ); for (int n = 0; n < candidates.size( ); ++n) std::cout << candidates[n].score << std::endl; cv::Mat labeledImg = labelCoins( image, candidates, MATCH_THRESHOLD, false, LABEL ); cv::imwrite( LABELED_IMAGE, labeledImg ); return 0; }
The goal is to read the patterns and the image that you need to study, and determine the location of the coins that match our pattern.
First, we read into the vector of images all the images of the patterns that we created in the previous program.
Then we read the image to be considered.
Then we expand the image, which will be checked using the same function as in the template creator.
getCandidates finds groups of points that should form a polygon. Each of these polygons is a candidate for coins. And they are all scaled and centered on a square equal to the size of our templates so that we can perform the comparison in a scale-invariant way.
We save candidate images obtained for debugging and tuning purposes.
matchCandidates matches each candidate with all templates stored for each best match result. Since we have patterns for multiple orientations, this ensures that the orientation remains the same.
The ratings of each candidate are printed, so we can choose a threshold to separate 50c coins from non-50c coins.
labelCoins copies the original image and draws a label over those whose metric is greater (or less than for some methods) of the threshold value defined in MATCH_THRESHOLD .
And finally, we save the result in .BMP
void loadTemplates(vector<cv::Mat>& templates, int angleStep) { templates.clear( ); for (int angle = 0; angle < 360; angle += angleStep) { char name[1000]; sprintf( name, "template-%03d.bmp", angle ); cv::Mat templateImg = cv::imread( name ); if (templateImg.data == NULL) { std::cout << "Could not read " << name << std::endl; exit( 1 ); } templates.push_back( templateImg ); } }
loadTemplates is similar to loadImage . But it loads several images instead of one and saves them in std::vector .
loadImage exactly the same as in the template creator.
createMask also exactly the same as the tempate manufacturer. This time we will apply it to the image with several coins. It should be noted that binarization thresholds were chosen for binarization 50c, and they will not work properly to binarize all coins in the image. But this does not matter, since the purpose of the program is only to identify coins 50c. As long as they are correctly segmented, we are fine. It really works in our favor if some coins are lost in this segmentation, since we will save time by rating them (so far we only lose coins that are not 50c).
typedef struct Candidate { cv::Mat image; float x; float y; float radius; float score; } Candidate; void getCandidates(const cv::Mat& image, const cv::Mat& mask, vector<Candidate>& candidates) { vector<vector<cv::Point> > contours; vector<cv::Vec4i> hierarchy;
The heart of getCandidates is cv::findContours , which finds the outlines of the areas present in the input image. What is the mask previously calculated.
findContours returns the findContours vector. Each contour itself is a vector of points that form the outer line of the detected polygon.
Each polygon limits the area of each potential coin.
For each path, we use cv::drawContours to draw a filled polygon over the black image.
Using this inverse image, we use the same procedure that was previously explained to calculate the centroid and radius of the polygon.
And we use centerAndScale , the same function that is used in the template creator, to center and scale the image contained in this polygon in an image that will have the same size as our templates. Thus, in the future we can make the correct match even for coins from photographs of different scales.
Each of these candidate coins is copied in the candidate structure, which contains:
- Candidate Image
- x and y for centroid
- radius
- assessment
getCandidates computes all of these values except for the estimate.
After compiling the candidate, it is placed in the candidate vector, the result of which we get from getCandidates .
These are 4 candidates:
void saveCandidates(const vector<Candidate>& candidates) { for (int n = 0; n < candidates.size( ); ++n) { char name[1000]; sprintf( name, "Candidate-%03d.bmp", n ); cv::imwrite( name, candidates[n].image ); } }
saveCandidates saves the computed candidates for debugging purpouses. And also so that I can post these images here.
void matchCandidates(const vector<cv::Mat>& templates, vector<Candidate>& candidates) { for (auto it = candidates.begin( ); it != candidates.end( ); ++it) matchCandidate( templates, *it ); }
matchCandidates simply calls matchCandidate for each candidate. Upon completion, we will receive an estimate for all selected candidates.
void matchCandidate(const vector<cv::Mat>& templates, Candidate& candidate) {
matchCandidate has as its input a single candidate and all templates. The goal is to match each template with a candidate. This work is delegated to singleTemplateMatch .
We maintain the best result, which is the smallest for CV_TM_SQDIFF and CV_TM_SQDIFF_NORMED , and the largest for other matching methods.
float singleTemplateMatch(const cv::Mat& templateImg, const cv::Mat& candidateImg) { cv::Mat result( 1, 1, CV_8UC1 ); cv::matchTemplate( candidateImg, templateImg, result, MATCH_METHOD ); return result.at<float>( 0, 0 ); }
singleTemplateMatch displays the match.
cv::matchTemplate uses two imput images, the second size is less than or equal to the size of the first. A common use case is for a small template (2nd parameter), which should be compared with a large image (1st parameter), and the result is a two-dimensional mat of floats with a matching pattern along the image. By positioning maximun (or minimun depending on the method) of this Mat of floats, we get the best candidate position for our template in the image of the first parameter.
But we are not interested in placing our template in the image, we already have the coordinates of our candidates.
We want a measure of similarity between our candidate and the template. This is why we use cv::matchTemplate in a way that is less common; we do this with the 1st parametric size image equal to the 2nd parametric pattern. In this situation, the result is a Mat of size 1x1. And the only meaning in this Mat is our assessment of similarity (or dissimiltality).
for (int n = 0; n < candidates.size( ); ++n) std::cout << candidates[n].score << std::endl;
We print the grades obtained for each of our candidates.
In this table, we can see the scores for each of the methods available for cv :: matchTemplate. The best result is green.
CCORR and CCOEFF give the wrong result, so the two are discarded. Of the remaining 4 methods, two SQDIFF methods are those that have a higher relative difference between the best match (50 s) and the second best (which is not 50 s). That's why I chose them. I chose SQDIFF_NORMED, but there is no good reason for this. To really choose a method, we need to test with a higher number of samples, not just using. For this method, the operating threshold may be 0.065. Choosing the right threshold also requires many samples.
bool selected(const Candidate& candidate, float threshold) {
labelCoins draws a label string at the location of the candidates with a score greater than (or less than, depending on the method) the threshold value. Finally, the result of labelCoins is saved using
cv::imwrite( LABELED_IMAGE, labeledImg );
Result:
All coins matching codes can be downloaded here .
Is this a good method?
It is hard to say. The method is consistent. It correctly detects a 50c coin for the sample and the input image.
But we do not know whether the method is reliable because it has not been tested with the correct sample size. And even more important, check it on samples that were not available when the program was encoded, this is a true measure of reliability when executed with a sufficiently large sample size.
I am pretty sure that the method has no false positives from silver coins. But I'm not so sure about other copper coins like 20c. As can be seen from the points obtained, the coin 20c receives a score very similar to 50c.
It is also possible that false negatives will occur under various lighting conditions. Something that can and should be avoided if we control the lighting conditions, for example, when we design a machine for photographing coins and counting them.
If the method works, the same method can be repeated for each type of coin, which leads to the complete detection of all coins.