degate  0.1.2
ViaMatching.cc
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 #include <ViaMatching.h>
00023 #include <BoundingBox.h>
00024 #include <MedianFilter.h>
00025 #include <EdgeDetection.h>
00026 #include <LogicModelHelper.h>
00027 #include <boost/foreach.hpp>
00028 
00029 using namespace degate;
00030 
00031 ViaMatching::ViaMatching() :
00032   threshold_match(0.9) {
00033 }
00034 
00035 
00036 void ViaMatching::init(BoundingBox const& bounding_box, Project_shptr project) {
00037 
00038   this->bounding_box = bounding_box;
00039 
00040   if(project == NULL)
00041     throw InvalidPointerException("Invalid pointer for parameter project.");
00042 
00043   lmodel = project->get_logic_model();
00044   assert(lmodel != NULL); // always has a logic model
00045 
00046   layer = lmodel->get_current_layer();
00047   if(layer == NULL)
00048     throw DegateRuntimeException("No current layer in project.");
00049 
00050 
00051   ScalingManager_shptr sm = layer->get_scaling_manager();
00052   assert(sm != NULL);
00053 
00054   img = sm->get_image(1).second;
00055   assert(img != NULL);
00056 
00057   reset_progress();
00058 }
00059 
00060 
00061 void ViaMatching::set_diameter(unsigned int diameter) {
00062   via_diameter = diameter;
00063 }
00064 
00065 void ViaMatching::set_threshold_match(double threshold_match) {
00066   this->threshold_match = threshold_match;
00067 }
00068 
00069 void ViaMatching::set_merge_n_vias(unsigned int merge_n_vias) {
00070   this->merge_n_vias = merge_n_vias;
00071 }
00072 
00073 double ViaMatching::get_threshold_match() const {
00074   return threshold_match;
00075 }
00076 
00077 unsigned int ViaMatching::get_merge_n_vias() const {
00078   return merge_n_vias;
00079 }
00080 
00081 void ViaMatching::run() {
00082 
00083   if(via_diameter == 0) throw DegateLogicException("Parameter via diameter was not set.");
00084 
00085   unsigned int max_r = 0;
00086 
00087   // lists for images of vias on the current layer
00088   std::list<MemoryImage_shptr> vias_up, vias_down;
00089 
00090   // iterate over all placed vias (current layer) and determine their size
00091   for(LogicModel::via_collection::iterator viter = lmodel->vias_begin();
00092       viter != lmodel->vias_end(); ++viter) {
00093     Via_shptr via = viter->second;
00094     if(via->get_layer() == layer && via->get_diameter() > max_r) 
00095       max_r = via->get_diameter();
00096   }
00097   
00098   debug(TM, "via matching: max diameter for image averaging: %d", max_r);
00099   
00100   int max_count_up = merge_n_vias, max_count_down = merge_n_vias;
00101   max_r = (max_r + 1) / 2;
00102 
00103   // iterate over all placed vias (current layer) and calculate a mean-image
00104   for(LogicModel::via_collection::iterator viter = lmodel->vias_begin();
00105       viter != lmodel->vias_end(); ++viter) {
00106     Via_shptr via = viter->second;
00107 
00108     if(via->get_layer() == layer) {
00109       
00110       // calculate new bounding box
00111       BoundingBox bb(via->get_x() - max_r, via->get_x() + max_r,
00112                      via->get_y() - max_r, via->get_y() + max_r);
00113 
00114       if(layer->get_bounding_box().complete_within(bb)) {
00115 
00116         // grab via's image
00117         MemoryImage_shptr img = grab_image<MemoryImage>(lmodel, layer, bb);
00118         assert(img != NULL);
00119         
00120         // insert image into one of the lists
00121         if(via->get_direction() == Via::DIRECTION_UP && 
00122            (merge_n_vias == 0 ? true : max_count_up-- > 0)) {
00123           vias_up.push_back(img);
00124         }
00125         else if(via->get_direction() == Via::DIRECTION_DOWN && 
00126                 (merge_n_vias == 0 ? true : max_count_down-- > 0))
00127           vias_down.push_back(img);
00128       }
00129       else debug(TM, "via out of region");
00130     }
00131   }
00132 
00133   debug(TM, "via matching: size of vias_down=%d vias_up=%d", vias_down.size(), vias_up.size());
00134 
00135   // calculate the mean-image
00136   MemoryImage_shptr via_up = merge_images(vias_up);
00137   MemoryImage_shptr via_down = merge_images(vias_down);
00138 
00139   // save images for debugging
00140   if(via_up) save_image(join_pathes("/tmp", "01_via_up_merged.tif"), via_up);
00141   if(via_down) save_image(join_pathes("/tmp", "01_via_down_merged.tif"), via_down);
00142 
00143   // convert to greyscale
00144   MemoryImage_GS_BYTE_shptr via_up_gs, via_down_gs;
00145 
00146   if(via_up) {
00147     via_up_gs = MemoryImage_GS_BYTE_shptr(new MemoryImage_GS_BYTE(via_up->get_width(), via_up->get_height()));
00148     copy_image(via_up_gs, via_up);
00149   }
00150 
00151   if(via_down) {
00152     via_down_gs = MemoryImage_GS_BYTE_shptr(new MemoryImage_GS_BYTE(via_down->get_width(), via_down->get_height()));
00153     copy_image(via_down_gs, via_down);
00154   }
00155 
00156   // save images for debugging
00157   if(via_up_gs) save_image(join_pathes("/tmp", "02_via_up_gs.tif"), via_up_gs);
00158   if(via_down_gs) save_image(join_pathes("/tmp", "02_via_down_gs.tif"), via_down_gs);
00159 
00160   // set progress step size
00161   int substeps = 0;
00162   if(via_up_gs) substeps++;
00163   if(via_down_gs) substeps++;
00164   if(substeps > 0) set_progress_step_size(1.0/( substeps * (bounding_box.get_height()-max_r*2) ));
00165 
00166   // run via matching
00167   if(via_up_gs) scan(bounding_box, img, via_up_gs, Via::DIRECTION_UP);
00168   if(via_down_gs) scan(bounding_box, img, via_down_gs, Via::DIRECTION_DOWN);
00169 
00170 }
00171 
00172 template<class BGImageType, class TemplateImageType>
00173 double calc_xcorr(unsigned int start_x, unsigned int start_y,
00174                   std::shared_ptr<BGImageType> bg_img, double f_avg, double sigma_f,
00175                   std::shared_ptr<TemplateImageType> tmpl_img, double t_avg, double sigma_t) {
00176 
00177   double sum = 0;
00178   double n = tmpl_img->get_width() * tmpl_img->get_height();
00179 
00180   for(unsigned int y = 0; y < tmpl_img->get_height(); y++) {
00181     for(unsigned int x = 0; x < tmpl_img->get_width(); x++) {
00182       double f_xy = bg_img->template get_pixel_as<double>(start_x + x, start_y + y);
00183       double t_xy = tmpl_img->template get_pixel_as<double>(x, y);
00184       
00185       sum += (f_xy - f_avg) * (t_xy - t_avg) / (sigma_f * sigma_t); // extract commons
00186     }
00187   }
00188 
00189   sum *= 1/(n - 1);
00190 
00191 
00192   return sum;
00193 }
00194 
00195 
00196 bool compare_correlation(ViaMatching::match_found const& lhs,
00197                          ViaMatching::match_found const& rhs) {
00198   return lhs.correlation > rhs.correlation;
00199 }
00200 
00201 bool ViaMatching::add_via(unsigned int x, unsigned int y,
00202                           unsigned int diameter,
00203                           Via::DIRECTION direction,
00204                           double corr_val, double threshold_hc) {
00205 
00206   if(!layer->exists_type_in_region<Via>(x, x + diameter,
00207                                         y, y + diameter)) {
00208 
00209     Via_shptr via(new Via(x + diameter/2, y + diameter/2, diameter, direction));
00210 
00211     char dsc[100];
00212     snprintf(dsc, sizeof(dsc), "matched with corr=%.2f t_hc=%.2f", corr_val, threshold_hc);
00213     via->set_description(dsc);
00214 
00215     lmodel->add_object(layer, via);
00216     return true;
00217   }
00218   return false;
00219 }
00220 
00221 void ViaMatching::scan(BoundingBox const& bbox, BackgroundImage_shptr bg_img,
00222                        MemoryImage_GS_BYTE_shptr tmpl_img, Via::DIRECTION direction) {
00223 
00224   std::list<match_found> matches;
00225   
00226   debug(TM, "run scanning");
00227   double f_avg, sigma_f;
00228   double t_avg, sigma_t;
00229   average_and_stddev(tmpl_img, 0, 0, 
00230                      tmpl_img->get_width(), tmpl_img->get_height(), 
00231                      &t_avg, &sigma_t);
00232 
00233   assert(bbox.get_max_x() >= 0);
00234   assert(bbox.get_max_y() >= 0);
00235 
00236   int max_x = static_cast<unsigned int>(bbox.get_max_x()) > tmpl_img->get_width() ? 
00237     bbox.get_max_x() - tmpl_img->get_width() : bbox.get_min_x();
00238   int max_y = static_cast<unsigned int>(bbox.get_max_y()) > tmpl_img->get_height() ? 
00239     bbox.get_max_y() - tmpl_img->get_height() : bbox.get_min_y();
00240 
00241   for(int y = bbox.get_min_y(); y < max_y; y++) {
00242     for(int x = bbox.get_min_x(); x < max_x; x++) {
00243 
00244       average_and_stddev(bg_img, x, y, 
00245                          tmpl_img->get_width(), tmpl_img->get_height(), 
00246                          &f_avg, &sigma_f);
00247 
00248       double xcorr = calc_xcorr(x, y,
00249                                 bg_img, f_avg, sigma_f,
00250                                 tmpl_img, t_avg, sigma_t);
00251 
00252       if(xcorr > threshold_match) {
00253         match_found m;
00254         m.x = x;
00255         m.y = y;
00256         m.correlation = xcorr;
00257 
00258         matches.push_back(m);
00259         //debug(TM, "%d,%d -> %f sigma-f=%f sigma-t=%f f_avg=%f t_avg=%f", x, y, xcorr, sigma_f,sigma_t, f_avg, sigma_f);       
00260       }
00261     }
00262 
00263     // update progress
00264     progress_step_done();
00265 
00266     // check if scanning was canceled
00267     if(is_canceled()) {
00268       reset_progress();
00269       return;
00270     }
00271 
00272   }
00273 
00274   matches.sort(compare_correlation);
00275   BOOST_FOREACH(match_found const& m, matches) {
00276     add_via(m.x, m.y, via_diameter, direction, m.correlation, threshold_match);
00277   }
00278 
00279 }
00280