FaSTMatch.zip

// // FAsTMatch.cpp // FAsT-Match // // Created by Saburo Okita on 23/05/14. // Copyright (c) 2014 Saburo Okita. All rights reserved. // #define _USE_MATH_DEFINES #define WITHIN( val, top_left, bottom_right ) (\ val.x > top_left.x && val.y > top_left.y && \ val.x < bottom_right.x && val.y < bottom_right.y ) #include "FAsTMatch.h" #include <iomanip> #include<numeric> #include <random> #include <tbb/tbb.h> #include<math.h> namespace fast_match { FAsTMatch::FAsTMatch() { init(); } void FAsTMatch::init( float epsilon, float delta, bool photometric_invariance, float min_scale, float max_scale ) { this->epsilon = epsilon; this->delta = delta; this->photometricInvariance = photometric_invariance; this->minScale = min_scale; this->maxScale = max_scale; } /** * Apply Fast Template Matching algorithm */ vector<Point2f> FAsTMatch::apply(Mat& original_image, Mat& original_template ) { /* Preprocess the image and template first */ image = preprocessImage( original_image ); templ = preprocessImage( original_template ); int r1x = 0.5 * (templ.cols - 1), r1y = 0.5 * (templ.rows - 1), r2x = 0.5 * (image.cols - 1), r2y = 0.5 * (image.rows - 1); float min_trans_x = -(r2x - r1x * minScale), max_trans_x = -min_trans_x, min_trans_y = -(r2y - r1y * minScale), max_trans_y = -min_trans_y, min_rotation = -M_PI, max_rotation = M_PI; /* Create the matching grid / net */ MatchNet net( templ.cols, templ.rows, delta, min_trans_x, max_trans_x, min_trans_y, max_trans_y, min_rotation, max_rotation, minScale, maxScale ); /* Smooth our images */ GaussianBlur( templ, templ, Size(0, 0), 2.0, 2.0 ); GaussianBlur( image, image, Size(0, 0), 2.0, 2.0 ); int no_of_points = round( 10 / (epsilon * epsilon) ); /* Randomly sample points */ Mat xs( 1, no_of_points, CV_32SC1 ), ys( 1, no_of_points, CV_32SC1 ); rng.fill( xs, RNG::UNIFORM, 1, templ.cols ); rng.fill( ys, RNG::UNIFORM, 1, templ.rows ); int level = 0; float delta_fact = 1.511f; float new_delta = delta; MatchConfig best_config; Mat best_trans; vector<double> best_distances(20, 0.0); double best_distance; vector<double> distances; vector<bool> insiders; while( true ) { level++; /* First create configurations based on our net */ vector<MatchConfig> configs = createListOfConfigs( net, templ.size(), image.size() ); int configs_count = static_cast<int>(configs.size()); /* Convert the configurations into affine matrices */ vector<Mat> affines = configsToAffine( configs, insiders ); /* Filter out configurations that fall outside of the boundaries */ /* the internal logic of configsToAffine has more information */ vector<MatchConfig> temp_configs; for( int i = 0; i < insiders.size(); i++ ) if( insiders[i] == true ) temp_configs.push_back( configs[i] ); configs = temp_configs; /* For the configs, calculate the scores / distances */ distances = evaluateConfigs( image, templ, affines, xs, ys, photometricInvariance ); /* Find the minimum distance */ auto min_itr = min_element( distances.begin(), distances.end() ); int min_index = static_cast<int>(min_itr - distances.begin()); best_distance = distances[min_index]; best_distances[level] = best_distance; best_config = configs[min_index]; best_trans = best_config.getAffineMatrix(); /* Conditions to exit the loop */ if( (best_distance < 0.005) || ((level > 2) && (best_distance < 0.015)) || level >= 20 ) break; if( level > 3 ) { float mean_value = std::accumulate( best_distances.begin() + level - 3, best_distances.begin() + level - 1, 0 ) * 1.0 / distances.size(); if( best_distance > mean_value * 0.97 ) break; } float thresh; bool too_high_percentage; /* Get the good configurations that falls between certain thresholds */ vector<MatchConfig> good_configs = getGoodConfigsByDistance( configs, best_distance, new_delta, distances, thresh, too_high_percentage ); if ((too_high_percentage && (best_distance > 0.05) && ((level==1) && (configs_count < 7.5e6)) ) || ((best_distance > 0.1) && ((level==1) && (configs_count < 5e6)) ) ) { static float factor = 0.9; new_delta = new_delta * factor; level = 0; net = net * factor; configs = createListOfConfigs( net, templ.size(), image.size() ); } else { new_delta = new_delta / delta_fact; vector<MatchConfig> expanded_configs = randomExpandConfigs( good_configs, net, level, 80, delta_fact ); configs.clear(); configs.insert( configs.end(), good_configs.begin(), good_configs.end() ); configs.insert( configs.end(), expanded_configs.begin(), expanded_configs.end() ); } /* Randomly sample points again */ rng.fill( xs, RNG::UNIFORM, 1, templ.cols ); rng.fill( ys, RNG::UNIFORM, 1, templ.rows ); } /* Return the rectangle corners based on the best affine transformation */ return calcCorners( image.size(), templ.size(), best_trans ); } /** * Given our grid / net, create a list of matching configurations */ vector<MatchConfig> FAsTMatch::createListOfConfigs( MatchNet& net, Size templ_size, Size image_size ) { /* Creating the steps for all the parameters (i.e. translation, rotation, and scaling) */ vector<float> tx_steps = net.getXTranslationSteps(), ty_steps = net.getYTranslationSteps(), r_steps = net.getRotationSteps(), s_steps = net.getScaleSteps(); /* Getting the proper number of steps for each configuration parameters */ int ntx_steps = static_cast<int>( tx_steps.size() ), nty_steps = static_cast<int>( ty_steps.size() ), ns_steps = static_cast<int>( s_steps.size() ), nr_steps = static_cast<int>( r_steps.size() ), nr2_steps = nr_steps; /* Refine the number of steps for the 2nd rotation parameter */ if( fabs((net.boundsRotate.second - net.boundsRotate.first) - (2 * M_PI)) < 0.1 ) { nr2_steps = (int) count_if( r_steps.begin(), r_steps.end(), [&]( float r ){ return r < (-M_PI / 2 + net.stepsRotate / 2); }); } int grid_size = ntx_steps * nty_steps * ns_steps * ns_steps * nr_steps * nr2_steps; vector<MatchConfig> configs( grid_size ); /* Iterate thru each possible affine configuration steps */ tbb::parallel_for( 0, ntx_steps, 1, [&](int tx_index) { float tx = tx_steps[tx_index]; for(int ty_i