TDSlicer_module.cc
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 // \file MakeSlice_module.cc
3 // \brief This is based on a DBSCAN density based clustering algorithm
4 // found in "A Density-Based Algorithm for Discovering Clusters in
5 // Large Spatial Databases with Noise" by M.Ester et.al. (1996)
6 // \version $Id: MakeSlice_module.cc,v 1.0 2013-05-01 17:00:00 mbaird42 Exp $
7 // \authors mbaird42@fnal.gov, messier@indiana.edu
8 ///////////////////////////////////////////////////////////////////////////
9 
16 
17 #include "Calibrator/Calibrator.h"
18 #include "Geometry/Geometry.h"
19 #include "NovaDAQConventions/DAQConventions.h"
20 #include "RecoBase/CellHit.h"
21 #include "RecoBase/Cluster.h"
22 #include "Utilities/func/MathUtil.h"
23 
24 #include <cmath>
25 #include <string>
26 #include <algorithm>
27 
28 
29 
30 // TDSlicer header
31 namespace tdslicer {
32 
33  struct PtInfo
34  {
35  double tns;
36  double plane;
37  double cell;
38  double isol;
39  double dens;
40  int nn;
41  };
42 
44  {
45  template<class T> using Atom = fhicl::Atom<T>;
47  using Name = fhicl::Name;
48 
49  Atom<bool> calcDT2D
50  {
51  Name("CalcDT2D"),
52  Comment("calculate time difference between hits based only on planes (false) or planes and cells in 2D (true)")
53  };
54  Atom<double> timeScale
55  {
56  Name("TimeScale"),
57  Comment("Time scale for determining metric in ns")
58  };
59  Atom<double> planeScale
60  {
61  Name("PlaneScale"),
62  Comment("Plane distance scale")
63  };
64  Atom<double> cellScale
65  {
66  Name("CellScale"),
67  Comment("Cell distance scale")
68  };
69  Atom<double> minDens
70  {
71  Name("MinDens"),
72  Comment("Minimum density for determining cluster centroid")
73  };
74  Atom<double> minIsol
75  {
76  Name("MinIsol"),
77  Comment("Minimum isolation for determining cluster centroid")
78  };
79  Atom<double> minPrimDist
80  {
81  Name("MinPrimDist"),
82  Comment("Minimum linkage between nearest neighbors for Prim's")
83  };
84  Atom<double> minCell
85  {
86  Name("MinCell"),
87  Comment("Minimum NCells for making a single view slice")
88  };
89  Atom<int> maxEventHits
90  {
91  Name("MaxEventHits"),
92  Comment("If there are more than this many hits in the event, don't try to slice, just put them all in the noise slice. -1 to disable")
93  };
94  Atom<int> timeThreshold
95  {
96  Name("TimeThreshold"),
97  Comment("The threshold to attach hits to centroids in time clustering.")
98  };
99  };
100 
102  {
103  template<class T> using Atom = fhicl::Atom<T>;
104  template<class T> using Table = fhicl::Table<T>;
106  using Name = fhicl::Name;
107 
108  Atom<std::string> cellInput
109  {
110  Name("CellInput"),
111  Comment("Label for CellHit input")
112  };
113  Atom<double> speedOfLight
114  {
115  Name("SpeedOfLight"),
116  Comment("Speed of light in NOvA planes / ns")
117  };
118  Atom<double> planeLength
119  {
120  Name("PlaneLength"),
121  Comment("NOvA plane length in cm")
122  };
123  Atom<double> cellLength
124  {
125  Name("CellLength"),
126  Comment("NOvA cell length in cm")
127  };
129  {
130  Name("nd"),
131  Comment("Parameters for ND.")
132  };
134  {
135  Name("fd"),
136  Comment("Parameters for FD.")
137  };
139  {
140  Name("tb"),
141  Comment("Parameters for TB.")
142  };
143  };
144 
145  class TDSlicer : public art::EDProducer {
146  public:
147  // Allows 'nova --print-description' to work
149 
150  explicit TDSlicer(const Parameters& params);
151  virtual ~TDSlicer();
152 
153  void beginRun(art::Run& run);
154  void produce(art::Event& evt);
155  void endJob();
156 
157  double GetDist(double dt, double dp, double dc);
158 
159  std::vector<PtInfo> GetPtInfo(const std::vector<art::Ptr<rb::CellHit > >& hits);
160  std::vector<int> GetCentroids(const std::vector<PtInfo>& info);
161 
162  std::vector<rb::Cluster> DBSCAN(std::vector< art::Ptr<rb::CellHit> > hits);
163  void SortStuff(std::vector<double> &mindist, std::vector<art::Ptr<rb::CellHit> > &hits);
164  int GetPoint(const std::vector<double>& dist, const std::vector<bool>& isUsed);
165  void FillDists(std::vector< std::vector<double> > &dists,
166  const std::vector< art::Ptr<rb::CellHit> >& hits);
167  std::vector<double> Prims(const std::vector< art::Ptr<rb::CellHit> >& hits);
168 
169 
170  void TrimNoise(rb::Cluster *cNoise, std::vector<rb::Cluster> *c2D);
171  std::vector<rb::Cluster> CombineViews(rb::Cluster *cNoise,
172  std::vector<rb::Cluster> *cX,
173  std::vector<rb::Cluster> *cY);
174 
175  protected:
176 
177  // configuration settings
180  };
181 
182 }
183 
184 
185 
186 
187 
188 namespace tdslicer
189 {
190  //----------------------------------------------------------------------
192  : fParams(params())
193  {
194  produces< std::vector<rb::Cluster> >();
195  }
196 
197  //----------------------------------------------------------------------
199  { }
200 
201  //----------------------------------------------------------------------
203  {
205  switch (geom->DetId()) {
208  break;
211  break;
214  break;
215  default:
216  assert(0 && "Unknown detector");
217  }
218  }
219 
220  //----------------------------------------------------------------------
222  {
223  }
224 
225  double TDSlicer::GetDist(double dt, double dp, double dc)
226  {
227  if (fDetectorParams.calcDT2D()){
228  double R = util::pythag(fParams.planeLength()*dp,
229  fParams.cellLength()*dc);
231  }
232  else {
233  double R = dp*fParams.planeLength();
235  // We know in the ND, all our physics momentum is in the +z direction,
236  // Hits at higher planes, should also be at higher dt
237  }
238  }
239 
240  // Fills parameters for the Time-Density portion of slicing - finds the
241  // density and isolation of each hit
242  std::vector<PtInfo> TDSlicer::GetPtInfo(const std::vector<art::Ptr<rb::CellHit > >& hits)
243  {
244  std::vector<PtInfo> info(hits.size());
245 
246  double maxdist = 0;
247  for (int i = 0; i < (int)hits.size(); i++){
248  info[i].tns = hits[i]->TNS();
249  info[i].plane= hits[i]->Plane();
250  info[i].cell = hits[i]->Cell();
251  for (int j = i+1; j < (int)hits.size(); j++){
252  double dt = (hits[i]->TNS() - hits[j]->TNS());
253  double dp = (hits[i]->Plane() - hits[j]->Plane());
254  double dc = (hits[i]->Cell() - hits[j]->Cell());
255  double dist = GetDist(dt,dp,dc);
256  //double dist = fabs(sqrt(dt*dt+dp*dp/18/18));
257  if (dist > 10) break; // Tiny density contribution beyond this
258  if (dist > maxdist) maxdist = dist;
259  if (i != j){
260  const double ed2 = exp(-dist*dist);
261  info[i].dens += ed2;
262  info[j].dens += ed2;
263  }
264  }
265  for (int j = i-1; j >= 0; j--){
266  double dt = (hits[i]->TNS() - hits[j]->TNS());
267  double dp = (hits[i]->Plane() - hits[j]->Plane());
268  double dc = (hits[i]->Cell() - hits[j]->Cell());
269  double dist = GetDist(dt,dp,dc);
270  //double dist = fabs(sqrt(dt*dt+dp*dp/18/18));
271  if (dist > 10) break; // Tiny density contribution beyond this
272  if (dist > maxdist) maxdist = dist;
273  if (i != j){
274  const double ed2 = exp(-dist*dist);
275  info[i].dens += ed2;
276  info[j].dens += ed2;
277  }
278  }
279  }
280 
281  for (int i = 0; i < (int)hits.size(); i++){
282  double min = std::max(maxdist, fDetectorParams.minIsol());
283  info[i].nn = -1;
284 
285  // Need the closest point with higher density.
286  // Hits sorted by time, so start at i, find next higher dens point
287  for (int j = i+1; j < (int)hits.size(); j++){
288  if (info[j].dens > info[i].dens){
289  double dt = (info[i].tns - info[j].tns);
290  double dp = (info[i].plane - info[j].plane);
291  double dc = (hits[i]->Cell() - hits[j]->Cell());
292  double dist = GetDist(dt,dp,dc);
293  //double dist = fabs(sqrt(dt*dt+dp*dp/18/18));
294  if (dist < min){
295  info[i].nn = j;
296  min = dist;
297  }
298  // We've now found a higher density point.
299  break;
300  }
301  }
302  // Now, go backwards
303  for (int j = i-1; j >= 0; j--){
304  if (info[j].dens > info[i].dens){
305  double dt = (info[i].tns - info[j].tns);
306  double dp = (info[i].plane - info[j].plane);
307  double dc = (hits[i]->Cell() - hits[j]->Cell());
308  double dist = GetDist(dt,dp,dc);
309  //double dist = fabs(sqrt(dt*dt+dp*dp/18/18));
310  if (dist < min){
311  info[i].nn = j;
312  min = dist;
313  }
314  // We've now found a higher density point.
315  break;
316  }
317  }
318  info[i].isol = min;
319  }
320 
321 
322  return info;
323  }
324 
325  // Add hits from small clusters into noise slice and delete
327  std::vector<rb::Cluster> *c2D)
328  {
329  double counter = 0;
330  for (int i = c2D->size()-1; i >= 0; i--){
331  if (c2D->at(i).NXCell() < fDetectorParams.minCell() &&
332  c2D->at(i).NYCell() < fDetectorParams.minCell()){
333  for (int j = 0; j < (int)c2D->at(i).NCell(); j++){
334  cNoise->Add(c2D->at(i).Cell(j));
335  }
336  c2D->erase(c2D->begin()+i);
337  }
338  counter++;
339  }
340  }
341 
342  // Put all clusters in both views to one vector
343  std::vector<rb::Cluster> TDSlicer::CombineViews(rb::Cluster *cNoise,
344  std::vector<rb::Cluster> *cX,
345  std::vector<rb::Cluster> *cY)
346  {
347  TrimNoise(cNoise, cX);
348  TrimNoise(cNoise, cY);
349 
350  std::vector<rb::Cluster> clusts;
351  for (int i = 0; i < (int)cX->size(); i++)
352  clusts.push_back(cX->at(i));
353  for (int i = 0; i < (int)cY->size(); i++)
354  clusts.push_back(cY->at(i));
355  return clusts;
356  }
357 
358  // For TDSlicer's Algorithm Machinary
359  int TDSlicer::GetPoint(const std::vector<double>& dist,
360  const std::vector<bool>& isUsed)
361  {
362  double min = 1e6; // Infinity
363  int minIdx = -1;
364  for (int i = 0; i < (int)dist.size(); i++){
365  if (!isUsed[i] && dist[i]<min){
366  min = dist[i];
367  minIdx = i;
368  }
369  }
370  return minIdx;
371  }
372 
373  void TDSlicer::FillDists(std::vector< std::vector<double> > &dists,
374  const std::vector< art::Ptr<rb::CellHit> >& hits)
375  {
376  std::vector<double> ts(hits.size());
377  std::vector<double> ps(hits.size());
378  std::vector<double> cs(hits.size());
379 
380  for(unsigned int i = 0; i < hits.size(); ++i){
381  ts[i] = hits[i]->TNS()/fDetectorParams.timeScale();
382  ps[i] = hits[i]->Plane()/fDetectorParams.planeScale();
383  cs[i] = hits[i]->Cell()/fDetectorParams.cellScale();
384  }
385 
386  for (int i = 0; i < (int)hits.size(); i++){
387  for (int j = 0; j <= i; j++){
388  if(i == j){
389  dists[i][j] = 0;
390  continue;
391  }
392  double dp=util::sqr(ps[i]-ps[j]);
393  double dc=util::sqr(cs[i]-cs[j]);
394  double dt=util::sqr(ts[i]-ts[j]);
395  dists[i][j] = sqrt(dp+dc)
396  + sqrt(dt+dc)
397  + sqrt(dt+dp);
398  dists[j][i] = dists[i][j];
399  }
400  }
401  }
402 
403  // Preform TDSlicer's distance clustering
404  std::vector<double> TDSlicer::Prims(const std::vector< art::Ptr<rb::CellHit> >& hits)
405  {
406  int N = hits.size();
407  std::vector<double> mindist(N,1e6);
408  if (N==0) return mindist;
409  std::vector<bool> isUsed (N,false);
410 
411  std::vector< std::vector<double> > distmatrix(N, std::vector<double>(N));
412  FillDists(distmatrix,hits);
413 
414 
415  // Include the first point
416  mindist[0] = 0;
417 
418  for (int i = 0; i < N; i++){
419  int x = GetPoint(mindist,isUsed); // Get closest point
420  assert(x!=-1);//Do better than this
421  isUsed[x] = true;
422 
423  for (int j = 0; j < N; j++){
424  if (!isUsed[j] && distmatrix[x][j] < mindist[j])
425  mindist[j] = std::max(distmatrix[x][j],mindist[x]);
426  }
427  }
428  return mindist;
429  }
430 
431  void TDSlicer::SortStuff(std::vector<double> &mindist, std::vector<art::Ptr<rb::CellHit> > &hits){
432  std::vector<std::pair<double, art::Ptr<rb::CellHit>>> h2;
433  h2.reserve(hits.size());
434  for(unsigned int i = 0; i < hits.size(); ++i)
435  h2.emplace_back(mindist[i], hits[i]);
436  std::sort(h2.begin(), h2.end());
437  for(unsigned int i = 0; i < hits.size(); ++i){
438  mindist[i] = h2[i].first;
439  hits[i] = h2[i].second;
440  }
441  }
442 
443  std::vector<rb::Cluster> TDSlicer::DBSCAN(std::vector< art::Ptr<rb::CellHit> > hits)
444  {
445  std::vector<rb::Cluster> clusts(1);
446  std::vector<double> mindist = Prims(hits);
447 
448  SortStuff(mindist, hits);
449  while (hits.size()>0){
450  if (mindist[0] > fDetectorParams.minPrimDist()){
451  //if (mindist[0] > 150){
452  mindist = Prims(hits);
453  SortStuff(mindist, hits);
454  rb::Cluster clust;
455  clusts.push_back(clust);
456  }
457  clusts.back().Add(hits[0]);
458  hits.erase(hits.begin());
459  mindist.erase(mindist.begin());
460  }
461  return clusts;
462  }
463 
464 
465  std::vector<int> TDSlicer::GetCentroids(const std::vector<PtInfo>& info)
466  {
467  std::vector<int> centroids;
468  for (int i = 0; i < (int)info.size(); i++){
469  if (info[i].dens >= fDetectorParams.minDens() &&
470  info[i].isol >= fDetectorParams.minIsol()){
471  centroids.push_back(i);
472  }
473  }
474  return centroids;
475  }
476 
477  //----------------------------------------------------------------------
479  {
480  // NOTE: There is currently no requirement that a slice have hits in
481  // both views.
482 
484 
485  // Get the cell hits
487  evt.getByLabel(fParams.cellInput(), hitcol);
488 
489  // Load the cell hits into a vector for easy use
490  std::vector<art::Ptr<rb::CellHit > > hitlist;
491  hitlist.reserve(hitcol->size());
492  for(unsigned int i = 0; i < hitcol->size(); ++i){
493  art::Ptr<rb::CellHit> hit(hitcol, i);
494  hitlist.push_back(hit);
495  }
496 
497  // Safety in case of a very large number of hits in the event, which can
498  // take a long time to slice, and the results probably won't be useful for
499  // downstream modules anyway.
500  if(fDetectorParams.maxEventHits() > 0 &&
501  int(hitlist.size()) > fDetectorParams.maxEventHits()){
502  mf::LogWarning("TDSlicer") << "Very large number of hits ("
503  << hitlist.size()
504  << ") in event. Higher than configured limit ("
506  << "). Will put all hits in the noise slice.";
507  rb::Cluster noise;
508  for(art::Ptr<rb::CellHit> c: hitlist) noise.Add(c);
509  noise.SetNoise(true);
510  evt.put(std::make_unique<std::vector<rb::Cluster>>(1, noise));
511  return;
512  }
513 
514  rb::SortByTime(hitlist);
515 
516  std::vector<PtInfo> info = GetPtInfo(hitlist);
517  std::vector<int> centroids = GetCentroids(info);
518  std::sort(centroids.begin(), centroids.end());
519 
520  std::unique_ptr< std::vector<rb::Cluster> >
521  clustercol(new std::vector<rb::Cluster>);
522 
523 
524  std::vector<double> ts(hitlist.size());
525  std::vector<int> ps(hitlist.size());
526  std::vector<int> cs(hitlist.size());
527 
528  for(unsigned int i = 0; i < hitlist.size(); ++i){
529  ts[i] = hitlist[i]->TNS();
530  ps[i] = hitlist[i]->Plane();
531  cs[i] = hitlist[i]->Cell();
532  }
533 
534  //
535  // Construct the actual slices to be put into the event.
536  //
537  std::vector< std::vector< art::Ptr<rb::CellHit> > >
538  protoclustsX(centroids.size()+1);
539  std::vector< std::vector< art::Ptr<rb::CellHit> > >
540  protoclustsY(centroids.size()+1);
541  // int loweridx = 0; // lowest index recently assigned
542  for(unsigned int i = 0; i < hitlist.size(); ++i){
543  int idx = 0;
545  int nmatch = 0;
546  for (int j = 0; j < int(centroids.size()); j++){
547  // for (int j = loweridx-1; j <= loweridx+2; j++){
548  if (j < 0 || j >= int(centroids.size())) continue;
549  double dt = ts[centroids[j]] - ts[i];
550  double dp = ps[centroids[j]] - ps[i];
551  double dc = cs[centroids[j]] - cs[i];
552  double dist = GetDist(dt,dp,dc);
553  if (dist < close){
554  nmatch++;
555  close = dist;
556  idx = j+1;
557  }
558  }
559  hitlist[i]->View() == geo::kX ? protoclustsX[idx].push_back(hitlist[i])
560  : protoclustsY[idx].push_back(hitlist[i]);
561  }
562 
563  std::vector<rb::Cluster> clusters(1);
564  for (int i = 0; i < (int)protoclustsX[0].size(); i++)
565  clusters[0].Add(protoclustsX[0][i]);
566  for (int i = 0; i < (int)protoclustsY[0].size(); i++)
567  clusters[0].Add(protoclustsY[0][i]);
568 
569  for (int i = 1; i < (int)protoclustsX.size(); i++){
570  std::vector<rb::Cluster> curclustsX = DBSCAN(protoclustsX[i]);
571  std::vector<rb::Cluster> curclustsY = DBSCAN(protoclustsY[i]);
572  // We're not merging views here, just add x / y slices to same vector
573  std::vector<rb::Cluster> curclusts =
574  CombineViews(&clusters[0], &curclustsX, &curclustsY);
575  for (int j = 0; j < (int)curclusts.size(); j++){
576  clusters.push_back(curclusts[j]);
577  }
578  }
579 
580  // Tag the noise cluster as such.
581  clusters[0].SetNoise(true);
582 
583  // Always put in the noise cluster even if it is empty.
584  for (int i = 0; i < (int)clusters.size(); i++){
585  // if (clusters[i].NXCell() < 3) continue;
586  // if (clusters[i].NYCell() < 3) continue;
587  clustercol->push_back(clusters[i]);
588  }
589 
590  //
591  // Before saving the clusters, put the hits inside them into a
592  // standard order
593  //
594  for (unsigned int i=0; i<clustercol->size(); ++i) {
595  (*clustercol)[i].StandardSort();
596  }
597 
598  // put the slices into the event
599  evt.put(std::move(clustercol));
600 
601  } // end Produce function
602 
603 } // end namespace tdslicer
604 /////////////////////////////////////////////////////////////////////////
605 
606 namespace tdslicer
607 {
609 }
T max(const caf::Proxy< T > &a, T b)
const XML_Char XML_Encoding * info
Definition: expat.h:530
void produce(art::Event &evt)
fvar< T > fabs(const fvar< T > &x)
Definition: fabs.hpp:15
void SortStuff(std::vector< double > &mindist, std::vector< art::Ptr< rb::CellHit > > &hits)
void SetNoise(bool noise)
Declare the cluster to consist of noise hits or not.
Definition: Cluster.h:161
void TrimNoise(rb::Cluster *cNoise, std::vector< rb::Cluster > *c2D)
double GetDist(double dt, double dp, double dc)
TDSlicerParams fParams
void FillDists(std::vector< std::vector< double > > &dists, const std::vector< art::Ptr< rb::CellHit > > &hits)
std::vector< int > GetCentroids(const std::vector< PtInfo > &info)
T sqrt(T number)
Definition: d0nt_math.hpp:156
Vertical planes which measure X.
Definition: PlaneGeo.h:28
A collection of associated CellHits.
Definition: Cluster.h:47
Table< TDSlicerDetectorParams > tbParams
void SortByTime(std::vector< art::Ptr< rb::CellHit > > &c)
Sort c in time order (earliest to latest).
Definition: CellHit.cxx:134
std::vector< double > Prims(const std::vector< art::Ptr< rb::CellHit > > &hits)
Table< TDSlicerDetectorParams > fdParams
DEFINE_ART_MODULE(TestTMapFile)
std::vector< PtInfo > GetPtInfo(const std::vector< art::Ptr< rb::CellHit > > &hits)
T sqr(T x)
More efficient square function than pow(x,2)
Definition: MathUtil.h:23
Definition: Run.h:31
void beginRun(art::Run &run)
virtual void Add(const art::Ptr< rb::CellHit > &cell, double weight=1)
Definition: Cluster.cxx:84
double dist
Definition: runWimpSim.h:113
int GetPoint(const std::vector< double > &dist, const std::vector< bool > &isUsed)
ProductID put(std::unique_ptr< PROD > &&product)
Definition: Event.h:102
Definition: Cand.cxx:23
Far Detector at Ash River, MN.
void hits()
Definition: readHits.C:15
Table< TDSlicerDetectorParams > ndParams
Atom< std::string > cellInput
novadaq::cnv::DetId DetId() const
Prefer ds::DetectorService::DetId() instead.
Definition: GeometryBase.h:243
fvar< T > exp(const fvar< T > &x)
Definition: exp.hpp:10
TDSlicer(const Parameters &params)
Near Detector in the NuMI cavern.
#define R(x)
const double j
Definition: BetheBloch.cxx:29
Definition: run.py:1
TH1F * h2
Definition: plot.C:45
static float min(const float a, const float b, const float c)
Definition: absgeo.cxx:45
std::vector< rb::Cluster > DBSCAN(std::vector< art::Ptr< rb::CellHit > > hits)
bool getByLabel(std::string const &label, std::string const &productInstanceName, Handle< PROD > &result) const
Definition: DataViewImpl.h:344
double pythag(double x, double y)
2D Euclidean distance
Definition: MathUtil.h:29
Definition: event.h:1
MaybeLogger_< ELseverityLevel::ELsev_warning, false > LogWarning
void geom(int which=0)
Definition: geom.C:163
TDSlicerDetectorParams fDetectorParams
std::vector< rb::Cluster > CombineViews(rb::Cluster *cNoise, std::vector< rb::Cluster > *cX, std::vector< rb::Cluster > *cY)
assert(nhit_max >=nhit_nbins)
Encapsulate the geometry of one entire detector (near, far, ndos)
procfile close()