degate  0.1.2
TemplateMatching.h
Go to the documentation of this file.
00001 /* -*-c++-*-
00002 
00003   This file is part of the IC reverse engineering tool degate.
00004 
00005   Copyright 2008, 2009, 2010 by Martin Schobert
00006 
00007   Degate is free software: you can redistribute it and/or modify
00008   it under the terms of the GNU General Public License as published by
00009   the Free Software Foundation, either version 3 of the License, or
00010   any later version.
00011 
00012   Degate is distributed in the hope that it will be useful,
00013   but WITHOUT ANY WARRANTY; without even the implied warranty of
00014   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015   GNU General Public License for more details.
00016 
00017   You should have received a copy of the GNU General Public License
00018   along with degate. If not, see <http://www.gnu.org/licenses/>.
00019 
00020 */
00021 
00022 #ifndef __TEMPLATEMATCHING_H__
00023 #define __TEMPLATEMATCHING_H__
00024 
00025 #include <Image.h>
00026 #include <Project.h>
00027 #include <Layer.h>
00028 #include <ProgressControl.h>
00029 
00030 namespace degate {
00031 
00032   /**
00033    * Helper structure for the collection of statistical values.
00034    */
00035 
00036   struct TemplateMatchingStatistics {
00037 
00038     /** Number of template matches. */
00039     unsigned int hits;
00040 
00041     void reset() {
00042       hits = 0;
00043     }
00044   };
00045 
00046   /**
00047    * Base class for matching alorithms.
00048    */
00049   class Matching : public ProgressControl {
00050   public:
00051     virtual ~Matching() {}
00052     virtual void init(BoundingBox const& bounding_box, Project_shptr project) = 0;
00053     virtual void run() = 0;
00054   };
00055 
00056 
00057   /**
00058    * This class implements the matching of gate representing images on
00059    * a background image.
00060    */
00061 
00062   class TemplateMatching : public Matching {
00063   protected:
00064 
00065     struct prepared_template {
00066       TempImage_GS_BYTE_shptr tmpl_img_normal;
00067       TempImage_GS_BYTE_shptr tmpl_img_scaled;
00068 
00069       //TempImage_GS_BYTE_shptr zero_mean_template_normal; // GS_DOUBLE?
00070       //TempImage_GS_BYTE_shptr zero_mean_template_scaled;
00071 
00072       TempImage_GS_DOUBLE_shptr zero_mean_template_normal; // GS_DOUBLE?
00073       TempImage_GS_DOUBLE_shptr zero_mean_template_scaled;
00074 
00075       double sum_over_zero_mean_template_normal;
00076       double sum_over_zero_mean_template_scaled;
00077 
00078       Gate::ORIENTATION orientation;
00079       GateTemplate_shptr gate_template;
00080     };
00081 
00082 
00083     struct search_state {
00084 
00085       unsigned int x, y; // unscaled coordinates in the cropped image
00086       unsigned int step_size_search;
00087       BoundingBox search_area; // on unscaled uncropped image
00088 
00089       Grid_shptr grid; // pointer to grid
00090       Grid::grid_iter iter,  // current position
00091         iter_begin, // first grid offset that is larger than x or y
00092         iter_last, // last entry grid that is less than x+w or y+h
00093         iter_end;
00094     };
00095 
00096     struct TemplateMatchingStatistics stats;
00097 
00098   public:
00099 
00100     typedef struct {
00101       unsigned int x, y; // absolut coordinates of the left upper corner
00102       GateTemplate_shptr tmpl;
00103       Gate::ORIENTATION orientation;
00104       double correlation; // the correlation value
00105       double t_hc;
00106     } match_found;
00107 
00108   private:
00109 
00110     // params for the matching
00111     double threshold_hc;
00112     double threshold_detection;
00113     unsigned int max_step_size_search;
00114     unsigned int scale_down;
00115 
00116     // background images in greyscale
00117     TileImage_GS_BYTE_shptr gs_img_normal;
00118     TileImage_GS_BYTE_shptr gs_img_scaled;
00119 
00120     // summation tables
00121     TileImage_GS_DOUBLE_shptr sum_table_single_normal;
00122     TileImage_GS_DOUBLE_shptr sum_table_squared_normal;
00123     TileImage_GS_DOUBLE_shptr sum_table_single_scaled;
00124     TileImage_GS_DOUBLE_shptr sum_table_squared_scaled;
00125 
00126     BoundingBox bounding_box; // bounding box on original unscaled background image
00127 
00128     std::list<GateTemplate_shptr> tmpl_set; // templates to match
00129     std::list<Gate::ORIENTATION> tmpl_orientations; // template orientations to match
00130 
00131     clock_t start, finish;
00132 
00133     std::list<match_found> matches;
00134 
00135   protected:
00136 
00137     Project_shptr project;
00138 
00139     Layer_shptr layer_matching; // matching happens on this layer
00140     Layer_shptr layer_insert; // found gates are inserted here
00141 
00142   private:
00143 
00144 
00145 
00146     void prepare_sum_tables(TileImage_GS_BYTE_shptr gs_img_normal,
00147                             TileImage_GS_BYTE_shptr gs_img_scaled);
00148 
00149     void precalc_sum_tables(TileImage_GS_BYTE_shptr img,
00150                             TileImage_GS_DOUBLE_shptr summation_table_single,
00151                             TileImage_GS_DOUBLE_shptr summation_table_squared);
00152 
00153 
00154     BoundingBox get_scaled_bounding_box(BoundingBox const& bounding_box,
00155                                         double scale_down) const;
00156 
00157     void prepare_background_images(ScalingManager_shptr sm,
00158                                    BoundingBox const& bounding_box,
00159                                    unsigned int scaling_factor);
00160 
00161     struct prepared_template prepare_template(GateTemplate_shptr tmpl,
00162                                               Gate::ORIENTATION orientation);
00163 
00164 
00165     void hill_climbing(unsigned int start_x, unsigned int start_y, double xcorr_val,
00166                        unsigned int * max_corr_x_out,
00167                        unsigned int * max_corr_y_out,
00168                        double * max_xcorr_out,
00169                        const TileImage_GS_BYTE_shptr master,
00170                        const TempImage_GS_DOUBLE_shptr zero_mean_template,
00171                        double sum_over_zero_mean_template) const;
00172 
00173     /**
00174      * Adjust step size depending on correlation value.
00175      */
00176     void adjust_step_size(struct search_state & state, double corr_val) const;
00177 
00178     std::list<match_found> match_single_template(struct prepared_template & tmpl,
00179                                                  double threshold_hc,
00180                                                  double threshold_detection);
00181 
00182 
00183     /**
00184      * Calculate a zero mean image from an image and return
00185      * the variance(?).
00186      */
00187     double subtract_mean(TempImage_GS_BYTE_shptr img,
00188                          TempImage_GS_DOUBLE_shptr zero_mean_img) const;
00189 
00190     /**
00191      * Calculate correlation between template and background.
00192      *
00193      * @param master The image where we look for matchings.
00194      * @param summation_table_single
00195      * @param summation_table_squared
00196      * @param zero_mean_template
00197      * @param sum_over_zero_mean_template
00198      * @param local_x Coordinate within \p master.
00199      * @param local_y Coordinate within \p master.
00200      */
00201     double calc_single_xcorr(const TileImage_GS_BYTE_shptr master,
00202                              const TileImage_GS_DOUBLE_shptr summation_table_single,
00203                              const TileImage_GS_DOUBLE_shptr summation_table_squared,
00204                              const TempImage_GS_DOUBLE_shptr zero_mean_template,
00205                              double sum_over_zero_mean_template,
00206                              unsigned int local_x,
00207                              unsigned int local_y) const;
00208 
00209 
00210     bool add_gate(unsigned int x, unsigned int y,
00211                   GateTemplate_shptr tmpl,
00212                   Gate::ORIENTATION orientation,
00213                   double corr_val = 0, double t_hc = 0);
00214 
00215     match_found keep_gate_match(unsigned int x, unsigned int y,
00216                                 struct prepared_template & tmpl,
00217                                 double corr_val = 0, double t_hc = 0) const;
00218 
00219   protected:
00220 
00221     /**
00222      * Calculate the next position for a template to background matching.
00223      * @return Returns false if there is no further position.
00224      */
00225 
00226     virtual bool get_next_pos(struct search_state * state,
00227                               struct prepared_template const& tmpl) const = 0;
00228 
00229 
00230   public:
00231 
00232     TemplateMatching();
00233 
00234     virtual ~TemplateMatching();
00235 
00236     /**
00237      * Get the correlation threshold for the hill climbing start phase.
00238      */
00239 
00240     double get_threshold_hc() const { return threshold_hc; }
00241 
00242     /**
00243      * Set the correlation threshold for the hill climbing.
00244      */
00245 
00246     void set_threshold_hc(double t) { threshold_hc = t; }
00247 
00248     /**
00249      * Get the correlation threshold for acepting gate recognitions.
00250      */
00251     double get_threshold_detection() const { return threshold_detection; }
00252 
00253     /**
00254      * Set the correlation threshold for acepting gate recognitions.
00255      */
00256 
00257     void set_threshold_detection(double t) { threshold_detection = t; }
00258 
00259     /**
00260      * Get the pixel step size.
00261      *
00262      * The correlation is not calculated for all (x,y). Instead the algorithm
00263      * skips pixel. The skipping depends on the correalation values. In areas
00264      * of higher correlation the step size is decremented. Else in correlation
00265      * valleys the step size is incremented. It is incremented up to a limit.
00266      * With this method you can set the limit.
00267      *
00268      * The image might be scaled before. This step size limit is in the
00269      * scale of the background image after(!) scaling.
00270      */
00271 
00272     unsigned int get_max_step_size() const { return max_step_size_search; }
00273 
00274     /**
00275      * Set the pixel step size.
00276      */
00277 
00278     void set_max_step_size(unsigned int s) { max_step_size_search = s; }
00279 
00280     /**
00281      * Get the scaling factor.
00282      * @return Returns a value >= 1 that is the factor for the down scaling.
00283      */
00284 
00285     unsigned int get_scaling_factor() const { return scale_down; }
00286 
00287     /**
00288      * Set the scaling factor.
00289      */
00290 
00291     void set_scaling_factor(unsigned int factor) { scale_down = factor; }
00292 
00293 
00294     /**
00295      * Run the template matching.
00296      */
00297 
00298     virtual void init(BoundingBox const& bounding_box, Project_shptr project);
00299 
00300     /**
00301      * Run the template matching.
00302      */
00303 
00304     virtual void run();
00305 
00306     /**
00307      * Set templates that should be matched.
00308      * Templates become sorted, so that larger templates are matched first.
00309      */
00310 
00311     void set_templates(std::list<GateTemplate_shptr> tmpl_set);
00312 
00313 
00314     /**
00315      * Set orientations that should be tested.
00316      */
00317 
00318     void set_orientations(std::list<Gate::ORIENTATION> tmpl_orientations);
00319 
00320     /**
00321      * Set the layers.
00322      *
00323      */
00324 
00325     void set_layers(Layer_shptr layer_matching, Layer_shptr layer_insert) {
00326       this->layer_matching = layer_matching;
00327       this->layer_insert = layer_insert;
00328     }
00329 
00330     unsigned int get_number_of_hits() const {
00331       return stats.hits;
00332     }
00333 
00334   };
00335 
00336 
00337   typedef std::shared_ptr<TemplateMatching> TemplateMatching_shptr;
00338 
00339 
00340   /**
00341    * This class implements a template matching that basically scans line
00342    * by line to detect gate placements.
00343    */
00344   class TemplateMatchingNormal : public TemplateMatching {
00345   protected:
00346     bool get_next_pos(struct search_state * state,
00347                       struct prepared_template const& tmpl) const;
00348   public:
00349     TemplateMatchingNormal() {}
00350     ~TemplateMatchingNormal() {}
00351   };
00352 
00353   typedef std::shared_ptr<TemplateMatchingNormal> TemplateMatchingNormal_shptr;
00354 
00355 
00356   /**
00357    * This class is the base class for template matching along a grid.
00358    */
00359 
00360   class TemplateMatchingAlongGrid : public TemplateMatching {
00361 
00362   protected:
00363 
00364     bool initialize_state_struct(struct search_state * state,
00365                                  int offs_min,
00366                                  int offs_max,
00367                                  bool is_horizontal_grid) const;
00368 
00369     virtual bool get_next_pos(struct search_state * state,
00370                               struct prepared_template const& tmpl) const = 0;
00371 
00372   public:
00373 
00374     virtual ~TemplateMatchingAlongGrid() {}
00375 
00376   };
00377 
00378 
00379   /**
00380    * This class implements matching for gate template that are aligned in a row.
00381    */
00382   class TemplateMatchingInRows : public TemplateMatchingAlongGrid {
00383 
00384   protected:
00385 
00386     bool get_next_pos(struct search_state * state,
00387                       struct prepared_template const& tmpl) const;
00388 
00389 
00390   public:
00391     TemplateMatchingInRows() {}
00392     ~TemplateMatchingInRows() {}
00393   };
00394 
00395   typedef std::shared_ptr<TemplateMatchingInRows> TemplateMatchingInRows_shptr;
00396 
00397   /**
00398    * This class implements matching for gate template that are aligned in a column.
00399    */
00400   class TemplateMatchingInCols : public TemplateMatchingAlongGrid {
00401 
00402   protected:
00403 
00404     bool get_next_pos(struct search_state * state,
00405                       struct prepared_template const& tmpl) const;
00406   public:
00407 
00408     TemplateMatchingInCols() {}
00409     ~TemplateMatchingInCols() {}
00410   };
00411 
00412   typedef std::shared_ptr<TemplateMatchingInCols> TemplateMatchingInCols_shptr;
00413 
00414 }
00415 
00416 
00417 #endif