c++ - Template Matching for Coins with OpenCV -

i undertaking project automatically count values of coins input image. far have segmented coins using pre-processing edge detection , using hough-transform.

my question how proceed here? need template matching on segmented images based on stored features. how can go doing this.

i have read called k-nearest neighbours , feel should using. not sure how go using it.

research articles have followed:

• coin detector

• coin recognition

one way of doing pattern matching using cv::matchtemplate.

this takes input image , smaller image acts template. compares template against overlapped image regions computing similarity of template overlapped region. several methods computing comparision available.
methods not directly support scale or orientation invariance. possible overcome scaling candidates reference size , testing against several rotated templates.

a detailed example of technique shown detect pressence , location of 50c coins. same procedure can applied other coins.
2 programs built. 1 create templates big image template 50c coin. , 1 take input templates image coins , output image 50c coin(s) labelled.

template maker

#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 load image used construct our templates.
segment create mask.
locate center of masses of said mask.
, rescale , copy mask , coin ocupy square of fixed size edges of square touching circunference of mask , coin. is, side of square has same lenght in pixels diameter of scaled mask or coin image.
save scaled , centered image of coin. , save further copies of rotated in fixed angle increments.

cv::mat loadimage(const char* name) {     cv::mat image;     image = cv::imread(name);     if ( image.data==null || image.channels()!=3 )     {         std::cout << name << " not read or not correct." << std::endl;         exit(1);     }     return image; } 

loadimage uses cv::imread read image. verifies data has been read , image has 3 channels , returns 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 );      /// next 3 lines debugging, may removed     cv::mat filtered;     image.copyto( filtered, compositemask );     cv::imwrite( "filtered.jpg", filtered);      return compositemask; } 

createmask segmentation of template. binarizes each of bgr channels, , of 3 binarized images , performs close morphologic operation produce mask.
3 debug lines copy original image black 1 using computed mask mask copy operation. helped in chosing proper values threshold.

here can see 50c image filtered mask created in createmask

cv::mat locate( const cv::mat& mask ) {   // compute center , 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 computes center of mass of mask , radius. returning 3 values in single row mat in form { x, y, radius }.
uses cv::moments calculates of the moments up third order of polygon or rasterized shape. rasterized shape in our case. not interested in of moments. 3 of them useful here. m00 area of mask. , centroid can calculated m00, m10 , 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 centroid , radius computed locate region of interest of input image , region of interest of mask such center of such regions center of coin , mask , side length of regions equal diameter of coin/mask.
these regions later scaled fixed template_size. scaled region our reference template. when later on in matching program want check if detected candidate coin coin take region of candidate coin, center , scale candidate coin in same way before performing template matching. way 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 );     ( 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 previous computed template.
saves several copies of it, each 1 rotated angle, defined in angle_step. goal of provide orientation invariance. lower define stepangle better orientation invariance implies higher computational cost.

you may download whole template maker program here.
when run angle_step 30 following 12 templates :

template 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 );     (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 here read templates , image examined , determine location of coins match our template.

first read vector of images template images produced in previous program.
read image examined.
binarize image examined using same function in template maker.
getcandidates locates groups of points toghether forming polygon. each of these polygons candidate coin. , of them rescaled , centered in square of size equal of our templates can perform matching in way invariant scale.
save candidate images obtained debugging , tuning purposes.
matchcandidates matches each candidate templates storing each result of best match. since have templates several orientations provides invariance orientation.
scores of each candidate printed can decide on threshold separate 50c coins non 50c coins.
labelcoins copies original image , draws label on ones have score greater (or lesser methods) threshold defined in match_threshold.
, save result in .bmp

void loadtemplates(vector<cv::mat>& templates, int anglestep) {     templates.clear( );     (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 similar loadimage. loads several images instead of 1 , stores them in std::vector.

loadimage same in template maker.

createmask same in tempate maker. time apply image several coins. should noted binarization thresholds chosen binarize 50c , not work binarize coins in image. of no consequence since program objective identify 50c coins. long segmented fine. works in our favour if coins lost in segmentation since save time evaluating them (as long lose coins 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;     /// find contours     cv::mat maskcopy;     mask.copyto( maskcopy );     cv::findcontours( maskcopy, contours, hierarchy, cv_retr_tree, cv_chain_approx_simple, cv::point( 0, 0 ) );     cv::mat maskcs;     cv::mat imagecs;     cv::scalar white = cv::scalar( 255 );     (int ncontour = 0; ncontour < contours.size( ); ++ncontour)     {         /// draw contour         cv::mat drawing = cv::mat::zeros( mask.size( ), cv_8uc1 );         cv::drawcontours( drawing, contours, ncontour, white, -1, 8, hierarchy, 0, cv::point( ) );          // compute center , radius , area.         // discard small areas.         cv::moments moments = cv::moments( drawing, true );         float area = moments.m00;         if (area < candidates_min_area)             continue;         candidate candidate;         candidate.radius = sqrt( area / m_pi );         candidate.x = moments.m10 / moments.m00;         candidate.y = moments.m01 / moments.m00;         float m[1][3] = {             { candidate.x, candidate.y, candidate.radius}         };         cv::mat characteristics( 1, 3, cv_32f, m );         centerandscale( image, drawing, characteristics, imagecs, maskcs );         imagecs.copyto( candidate.image );         candidates.push_back( candidate );     } } 

the heart of getcandidates cv::findcontours finds contours of areas present in input image. here mask computed.
findcontours returns vector of contours. each contour being vector of points form outer line of detected polygon.
each polygon delimites region of each candidate coin.
each contour use cv::drawcontours draw filled polygon on black image.
drawn image use same procedure earlier explained compute centroid , radius of polygon.
, use centerandscale, same function used in template maker, center , scale image contained in poligon in image have same size our templates. way later on able perform proper matching coins photos of different scales.
each of these candidate coins copied in candidate structure contains :

• candidate image
• x , y centroid
• radius
• score

getcandidates computes these values except score.
after composing candidate put in vector of candidates result getcandidates.

these 4 candidates obtained :

void savecandidates(const vector<candidate>& candidates) {     (int n = 0; n < candidates.size( ); ++n)     {         char name[1000];         sprintf( name, "candidate-%03d.bmp", n );         cv::imwrite( name, candidates[n].image );     } } 

savecandidates saves computed candidates debugging purpouses. , may post images here.

void matchcandidates(const vector<cv::mat>& templates,         vector<candidate>& candidates) {     (auto = candidates.begin( ); != candidates.end( ); ++it)         matchcandidate( templates, *it ); } 

matchcandidates calls matchcandidate each candidate. after completion have score candidates computed.

void matchcandidate(const vector<cv::mat>& templates, candidate& candidate) {     /// sqdiff , sqdiff_normed, best matches lower values. other methods, higher better     candidate.score;     if (match_method == cv_tm_sqdiff || match_method == cv_tm_sqdiff_normed)         candidate.score = flt_max;     else         candidate.score = 0;     (auto = templates.begin( ); != templates.end( ); ++it)     {         float score = singletemplatematch( *it, candidate.image );         if (match_method == cv_tm_sqdiff || match_method == cv_tm_sqdiff_normed)         {             if (score < candidate.score)                 candidate.score = score;         }         else         {             if (score > candidate.score)                 candidate.score = score;         }     } } 

matchcandidate has input single candidate , templates. it's goal match each template against candidate. work delegated singletemplatematch.
store best score obtained, cv_tm_sqdiff , cv_tm_sqdiff_normed smallest 1 , other matching methods biggest one.

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 peforms matching.
cv::matchtemplate uses 2 imput images, second smaller or equal in size first one.
common use case small template (2nd parameter) matched against larger image (1st parameter) , result bidimensional mat of floats matching of template along image. locating maximun (or minimun depending on method) of mat of floats best candidate position our template in image of 1st parameter.
not interested in locating our template in image, have coordinates of our candidates.
want measure of similitude between our candidate , template. why use cv::matchtemplate in way less usual; 1st parameter image of size equal 2nd parameter template. in situation result mat of size 1x1. , single value in mat our score of similitude (or dissimilitude).

for (int n = 0; n < candidates.size( ); ++n)     std::cout << candidates[n].score << std::endl; 

we print scores obtained each of our candidates.
in table can see scores each of methods available cv::matchtemplate. best score in green.

ccorr , ccoeff give wrong result, 2 discarded. of remaining 4 methods 2 sqdiff methods ones higher relative difference between best match (which 50c) , 2nd best (which not 50c). why have choosen them.
have chosen sqdiff_normed there no strong reason that. in order chose method should test higher ammount of samples, not one.
method working threshold 0.065. selection of proper threshold requires many samples.

bool selected(const candidate& candidate, float threshold) {     /// sqdiff , sqdiff_normed, best matches lower values. other methods, higher better     if (match_method == cv_tm_sqdiff || match_method == cv_tm_sqdiff_normed)         return candidate.score <= threshold;     else         return candidate.score>threshold; }  void drawlabel(const candidate& candidate, const char* label, cv::mat image) {     int x = candidate.x - candidate.radius;     int y = candidate.y;     cv::point point( x, y );     cv::scalar blue( 255, 128, 128 );     cv::puttext( image, label, point, cv_font_hershey_simplex, 1.5f, blue, 2 ); }  cv::mat labelcoins(const cv::mat& image, const vector<candidate>& candidates,         float threshold, bool inversethreshold, const char* label) {     cv::mat imagelabeled;     image.copyto( imagelabeled );      (auto = candidates.begin( ); != candidates.end( ); ++it)     {         if (selected( *it, threshold ))             drawlabel( *it, label, imagelabeled );     }      return imagelabeled; } 

labelcoins draws label string @ location of candidates score bigger ( or lesser depending on method) threshold. , result of labelcoins saved

cv::imwrite( labeled_image, labeledimg ); 

the result being :

the whole code coin matcher can downloaded here.

is method?

hard tell.
method consistent. correctly detects 50c coin sample , input image provided.
have no idea if method robust because has not been tested proper sample size. , more important test against samples not available when program being coded, true measure of robustness when done large enough sample size.
rather confident in method not having false positives silver coins. not sure other copper coins 20c. can see scores obtained 20c coin gets score similar 50c.
quite possible false negatives happen under varying lighting conditions. can , should avoided if have control on lighting conditions such when designing machine take photos of coins , count them.

if method works same method can repeated each type of coin leading full detection of coins.