LArSoft  v10_04_05
Liquid Argon Software toolkit - https://larsoft.org/
HoughSeedFinderAlg.cxx
Go to the documentation of this file.
1 
13 // The main include
15 
16 // Framework Includes
18 
19 // LArSoft includes
23 
24 // ROOT includes
25 #include "TCanvas.h"
26 #include "TDecompSVD.h"
27 #include "TFrame.h"
28 #include "TH2D.h"
29 #include "TMatrixD.h"
30 #include "TVectorD.h"
31 
32 // std includes
33 #include <memory>
34 
35 //------------------------------------------------------------------------------------------------------------------------------------------
36 
37 //------------------------------------------------------------------------------------------------------------------------------------------
38 // implementation follows
39 
40 namespace lar_cluster3d {
41 
43  : m_minimum3DHits(5)
44  , m_thetaBins(360)
45  , m_rhoBins(75)
46  , m_hiThresholdMin(5)
47  , m_hiThresholdFrac(.05)
48  , m_loThresholdFrac(0.85)
49  , m_numSeed2DHits(80)
50  , m_numAveDocas(6.)
51  , m_numSkippedHits(10)
52  , m_maxLoopsPerCluster(3)
53  , m_maximumGap(5.)
54  , m_pcaAlg(pset.get<fhicl::ParameterSet>("PrincipalComponentsAlg"))
55  , m_displayHist(false)
56  {
57  m_minimum3DHits = pset.get<size_t>("Minimum3DHits", 5);
58  m_thetaBins = pset.get<int>("ThetaBins", 360);
59  m_rhoBins = pset.get<int>("HalfRhoBins", 75);
60  m_hiThresholdMin = pset.get<size_t>("HiThresholdMin", 5);
61  m_hiThresholdFrac = pset.get<double>("HiThresholdFrac", 0.05);
62  m_loThresholdFrac = pset.get<double>("LoThresholdFrac", 0.85);
63  m_numSeed2DHits = pset.get<size_t>("NumSeed2DHits", 80);
64  m_numAveDocas = pset.get<double>("NumAveDocas", 6.);
65  m_numSkippedHits = pset.get<int>("NumSkippedHits", 10);
66  m_maxLoopsPerCluster = pset.get<int>("MaxLoopsPerCluster", 3);
67  m_maximumGap = pset.get<double>("MaximumGap", 5.);
68  m_displayHist = pset.get<bool>("DisplayHoughHist", false);
70  }
71 
72  //------------------------------------------------------------------------------------------------------------------------------------------
73 
82  public:
83  AccumulatorValues() : m_position(0., 0., 0.) {}
84  AccumulatorValues(const Eigen::Vector3f& position,
86  : m_position(position), m_hit3DIterator(itr)
87  {}
88 
89  const Eigen::Vector3f& getPosition() const { return m_position; }
90  reco::HitPairListPtr::const_iterator getHitIterator() const { return m_hit3DIterator; }
91 
92  private:
93  Eigen::Vector3f
97  };
98 
99  typedef std::vector<AccumulatorValues> AccumulatorValuesVec;
100 
108  public:
109  AccumulatorBin() : m_visited(false), m_noise(false), m_inCluster(false) {}
110  AccumulatorBin(AccumulatorValues& values) : m_visited(false), m_noise(false), m_inCluster(false)
111  {
112  m_accumulatorValuesVec.push_back(values);
113  }
114 
115  void setVisited() { m_visited = true; }
116  void setNoise() { m_noise = true; }
117  void setInCluster() { m_inCluster = true; }
118 
119  void addAccumulatorValue(AccumulatorValues& value) { m_accumulatorValuesVec.push_back(value); }
120 
121  bool isVisited() const { return m_visited; }
122  bool isNoise() const { return m_noise; }
123  bool isInCluster() const { return m_inCluster; }
124 
125  const AccumulatorValuesVec& getAccumulatorValues() const { return m_accumulatorValuesVec; }
126 
127  private:
128  bool m_visited;
129  bool m_noise;
131  AccumulatorValuesVec m_accumulatorValuesVec;
132  };
133 
138  public:
140  {}
141 
144  {
145  size_t peakCountLeft(0);
146  size_t peakCountRight(0);
147 
148  for (const auto& binIndex : left)
149  peakCountLeft = std::max(peakCountLeft, m_accMap[binIndex].getAccumulatorValues().size());
150  for (const auto& binIndex : right)
151  peakCountRight = std::max(peakCountRight, m_accMap[binIndex].getAccumulatorValues().size());
152 
153  return peakCountLeft > peakCountRight;
154  }
155 
156  private:
158  };
159 
166  {
167  size_t leftSize = left->second.getAccumulatorValues().size();
168  size_t rightSize = right->second.getAccumulatorValues().size();
169 
170  return leftSize > rightSize;
171  }
172  };
173 
175  RhoThetaAccumulatorBinMap& rhoThetaAccumulatorBinMap,
176  HoughCluster& neighborPts,
177  size_t threshold) const
178  {
183  // We simply loop over the nearest indices and see if we have any friends over threshold
184  for (int rhoIdx = curBin.first - 1; rhoIdx <= curBin.first + 1; rhoIdx++) {
185  for (int jdx = curBin.second - 1; jdx <= curBin.second + 1; jdx++) {
186  // Skip the self reference
187  if (rhoIdx == curBin.first && jdx == curBin.second) continue;
188 
189  // Theta bin needs to handle the wrap.
190  int thetaIdx(jdx);
191 
192  if (thetaIdx < 0)
193  thetaIdx = m_thetaBins - 1;
194  else if (thetaIdx > m_thetaBins - 1)
195  thetaIdx = 0;
196 
197  BinIndex binIndex(rhoIdx, thetaIdx);
198  RhoThetaAccumulatorBinMap::iterator mapItr = rhoThetaAccumulatorBinMap.find(binIndex);
199 
200  if (mapItr != rhoThetaAccumulatorBinMap.end()) {
201  if (mapItr->second.getAccumulatorValues().size() >= threshold)
202  neighborPts.push_back(binIndex);
203  }
204  }
205  }
206 
207  return;
208  }
209 
211  HoughCluster& neighborPts,
212  HoughCluster& houghCluster,
213  RhoThetaAccumulatorBinMap& rhoThetaAccumulatorBinMap,
214  size_t threshold) const
215  {
220  // Start by adding the input point to our Hough Cluster
221  houghCluster.push_back(curBin);
222 
223  for (auto& binIndex : neighborPts) {
224  AccumulatorBin& accBin = rhoThetaAccumulatorBinMap[binIndex];
225 
226  if (!accBin.isVisited()) {
227  accBin.setVisited();
228 
229  HoughCluster nextNeighborPts;
230 
231  HoughRegionQuery(binIndex, rhoThetaAccumulatorBinMap, nextNeighborPts, threshold);
232 
233  if (!nextNeighborPts.empty()) {
234  for (auto& neighborIdx : nextNeighborPts) {
235  neighborPts.push_back(neighborIdx);
236  }
237  }
238  }
239 
240  if (!accBin.isInCluster()) {
241  houghCluster.push_back(binIndex);
242  accBin.setInCluster();
243  }
244  }
245 
246  return;
247  }
248 
250  {
251  return *left < *right;
252  }
253 
256  {
257  return Hit3DCompare(left, right);
258  }
259  };
260 
262  public:
263  OrderHitsAlongWire(int plane = 0) : m_plane(plane) {}
264 
266  {
267  int planeToCheck = (m_plane + 1) % 3;
268 
269  return left->getHits()[planeToCheck]->WireID().Wire <
270  right->getHits()[planeToCheck]->WireID().Wire;
271  }
272 
273  private:
274  int m_plane;
275  };
276 
278  bool operator()(const std::pair<size_t, size_t>& left, const std::pair<size_t, size_t>& right)
279  {
280  return left.second < right.second;
281  }
282  };
283 
285  reco::HitPairListPtr& outputList) const
286  {
287  // Intention is to try to find the largest "contiguous" block of hits in the input list
288  // In a nutshell, the idea is to order input hits according to the pca, then
289  // loop through the hits and store them in a new hit list. If a gap is detected then
290  // we terminate the previous list, create a new one and continue. After the loop over
291  // hits is complete then simply pick the biggest list.
292  // Step I is to run the pca and order the hits
294 
295  m_pcaAlg.PCAAnalysis_3D(inputHitList, pca, true);
296 
297  // It would seem that the analysis can fail!
298  if (!pca.getSvdOK()) {
299  outputList = inputHitList;
300  return;
301  }
302 
303  m_pcaAlg.PCAAnalysis_calc3DDocas(inputHitList, pca);
304 
305  inputHitList.sort(SeedFinderAlgBase::Sort3DHitsByArcLen3D());
306  outputList.clear();
307 
308  // Create containers to hold our hit lists
309  reco::HitPairListPtr continuousHitList;
310 
311  std::map<size_t, reco::HitPairListPtr> gapHitListMap;
312 
313  // Remember the distance arc length of the last hit
314  double arcLenLastHit = inputHitList.front()->getArclenToPoca();
315 
316  // Loop through the input hits
317  for (const auto& hit3D : inputHitList) {
318  // Hits in order, delta arclength should always be positive
319  double arcLen = hit3D->getArclenToPoca();
320  double deltaArcLen = arcLen - arcLenLastHit;
321 
322  if (deltaArcLen > m_maximumGap) {
323  gapHitListMap[continuousHitList.size()] = continuousHitList;
324  continuousHitList.clear();
325  }
326 
327  continuousHitList.emplace_back(hit3D);
328 
329  arcLenLastHit = arcLen;
330  }
331 
332  if (!continuousHitList.empty()) gapHitListMap[continuousHitList.size()] = continuousHitList;
333 
334  // Get the largest list of hits
335  std::map<size_t, reco::HitPairListPtr>::reverse_iterator longestListItr =
336  gapHitListMap.rbegin();
337 
338  if (longestListItr != gapHitListMap.rend()) {
339  size_t nContinuousHits = longestListItr->first;
340  reco::HitPairListPtr longestList = longestListItr->second;
341 
342  outputList.resize(nContinuousHits);
343  std::copy(longestList.begin(), longestList.end(), outputList.begin());
344  }
345 
346  return;
347  }
348 
351  RhoThetaAccumulatorBinMap& rhoThetaAccumulatorBinMap,
352  HoughClusterList& houghClusters) const
353  {
354  // The goal of this function is to do a basic Hough Transform on the input list of 3D hits.
355  // In order to transform this to a 2D problem, the 3D hits are projected to the plane of the two
356  // largest eigen values from the input principal components analysis axis.
357  // There are two basic steps to the job here:
358  // 1) Build and accumlate a rho-theta map
359  // 2) Go through that rho-theta map and find candidate Hough "clusters"
360  // Unfortunately, the following may not be suitable viewing for those who may be feint of heart
361  //
362  // Define some constants
363  static int histCount(0);
364  const double maxTheta(M_PI); // Obviously, 180 degrees
365  const double thetaBinSize(maxTheta / double(m_thetaBins)); // around 4 degrees (45 bins)
366  const double rhoBinSizeMin(
367  m_wireReadoutGeom->Plane({0, 0, 0}).WirePitch()); // Wire spacing gives a natural bin size?
368 
369  // Recover the parameters from the Principal Components Analysis that we need to project and accumulate
370  Eigen::Vector3f pcaCenter(
371  pca.getAvePosition()[0], pca.getAvePosition()[1], pca.getAvePosition()[2]);
372  Eigen::Vector3f planeVec0(pca.getEigenVectors().row(2));
373  Eigen::Vector3f planeVec1(pca.getEigenVectors().row(1));
374  Eigen::Vector3f pcaPlaneNrml(pca.getEigenVectors().row(0));
375  double eigenVal0 = 3. * sqrt(pca.getEigenValues()[2]);
376  double eigenVal1 = 3. * sqrt(pca.getEigenValues()[1]);
377  double maxRho = std::sqrt(eigenVal0 * eigenVal0 + eigenVal1 * eigenVal1) * 2. / 3.;
378  double rhoBinSize = maxRho / double(m_rhoBins);
379 
380  if (rhoBinSize < rhoBinSizeMin) rhoBinSize = rhoBinSizeMin;
381 
382  // **********************************************************************
383  // Part I: Accumulate values in the rho-theta map
384  // **********************************************************************
385 
386  size_t maxBinCount(0);
387  int nAccepted3DHits(0);
388 
389  // Commence looping over the input 3D hits and fill our accumulator bins
390  for (reco::HitPairListPtr::const_iterator hit3DItr = hitPairListPtr.begin();
391  hit3DItr != hitPairListPtr.end();
392  hit3DItr++) {
393  // Recover the hit
394  const reco::ClusterHit3D* hit3D(*hit3DItr);
395 
396  // Skip hits which are not skeleton points
397  if (!(hit3D->getStatusBits() & 0x10000000)) continue;
398 
399  nAccepted3DHits++;
400 
401  Eigen::Vector3f hit3DPosition(
402  hit3D->getPosition()[0], hit3D->getPosition()[1], hit3D->getPosition()[2]);
403  Eigen::Vector3f pcaToHitVec = hit3DPosition - pcaCenter;
404  Eigen::Vector3f pcaToHitPlaneVec(pcaToHitVec.dot(planeVec0), pcaToHitVec.dot(planeVec1), 0.);
405  double xPcaToHit = pcaToHitPlaneVec[0];
406  double yPcaToHit = pcaToHitPlaneVec[1];
407 
408  // Create an accumulator value
409  AccumulatorValues accValue(pcaToHitPlaneVec, hit3DItr);
410 
411  // Commence loop over theta to fill accumulator bins
412  // Note that with theta in the range 0-pi then we can have negative values for rho
413  for (int thetaIdx = 0; thetaIdx < m_thetaBins; thetaIdx++) {
414  // We need to convert our theta index to an angle
415  double theta = thetaBinSize * double(thetaIdx);
416 
417  // calculate rho for this angle
418  double rho = xPcaToHit * std::cos(theta) + yPcaToHit * std::sin(theta);
419 
420  // Get the rho index
421  int rhoIdx = std::round(rho / rhoBinSize);
422 
423  // Accumulate
424  BinIndex binIndex(rhoIdx, thetaIdx);
425 
426  rhoThetaAccumulatorBinMap[binIndex].addAccumulatorValue(accValue);
427 
428  if (rhoThetaAccumulatorBinMap[binIndex].getAccumulatorValues().size() > maxBinCount)
429  maxBinCount = rhoThetaAccumulatorBinMap[binIndex].getAccumulatorValues().size();
430  }
431  }
432 
433  // Accumulation done, if asked now display the hist
434  if (m_displayHist) {
435  std::ostringstream ostr;
436  ostr << "Hough Histogram " << histCount++;
437  m_Canvases.emplace_back(new TCanvas(ostr.str().c_str(), ostr.str().c_str(), 1000, 1000));
438 
439  std::ostringstream ostr2;
440  ostr2 << "Plane";
441 
442  m_Canvases.back()->GetFrame()->SetFillColor(46);
443  m_Canvases.back()->SetFillColor(19);
444  m_Canvases.back()->SetBorderMode(19);
445  m_Canvases.back()->cd(1);
446 
447  double zmin = 0.06;
448  double zmax = 0.94;
449  double xmin = 0.04;
450  double xmax = 0.95;
451  TPad* p = new TPad(ostr2.str().c_str(), ostr2.str().c_str(), zmin, xmin, zmax, xmax);
452  p->SetBit(kCanDelete); // Give away ownership.
453  p->Range(zmin, xmin, zmax, xmax);
454  p->SetFillStyle(4000); // Transparent.
455  p->Draw();
456  m_Pads.push_back(p);
457 
458  TH2D* houghHist = new TH2D("HoughHist",
459  "Hough Space",
460  2 * m_rhoBins,
461  -m_rhoBins + 0.5,
462  m_rhoBins + 0.5,
463  m_thetaBins,
464  0.,
465  m_thetaBins);
466 
467  for (const auto& rhoThetaMap : rhoThetaAccumulatorBinMap) {
468  houghHist->Fill(rhoThetaMap.first.first,
469  rhoThetaMap.first.second + 0.5,
470  rhoThetaMap.second.getAccumulatorValues().size());
471  }
472 
473  houghHist->SetBit(kCanDelete);
474  houghHist->Draw();
475  m_Canvases.back()->Update();
476  }
477 
478  // **********************************************************************
479  // Part II: Use DBScan (or a slight variation) to find clusters of bins
480  // **********************************************************************
481 
482  size_t thresholdLo = std::max(size_t(m_hiThresholdFrac * nAccepted3DHits), m_hiThresholdMin);
483  size_t thresholdHi = m_loThresholdFrac * maxBinCount;
484 
485  std::list<RhoThetaAccumulatorBinMap::iterator> binIndexList;
486 
487  for (RhoThetaAccumulatorBinMap::iterator mapItr = rhoThetaAccumulatorBinMap.begin();
488  mapItr != rhoThetaAccumulatorBinMap.end();
489  mapItr++)
490  binIndexList.push_back(mapItr);
491 
492  binIndexList.sort(SortBinIndexList());
493 
494  for (auto& mapItr : binIndexList) {
495  // If we have been here before we skip
496  //if (mapItr.second.isVisited()) continue;
497  if (mapItr->second.isInCluster()) continue;
498 
499  // Mark this bin as visited
500  // Actually, don't mark it since we are double thresholding and don't want it missed
501  //mapItr.second.setVisited();
502 
503  // Make sure over threshold
504  if (mapItr->second.getAccumulatorValues().size() < thresholdLo) {
505  mapItr->second.setNoise();
506  continue;
507  }
508 
509  // Set the low threshold to make sure we merge bins that might be either side of a boundary trajectory
510  thresholdHi = std::max(
511  size_t(m_loThresholdFrac * mapItr->second.getAccumulatorValues().size()), m_hiThresholdMin);
512 
513  // Recover our neighborhood
514  HoughCluster neighborhood;
515  BinIndex curBin(mapItr->first);
516 
517  HoughRegionQuery(curBin, rhoThetaAccumulatorBinMap, neighborhood, thresholdHi);
518 
519  houghClusters.push_back(HoughCluster());
520 
521  HoughCluster& houghCluster = houghClusters.back();
522 
524  curBin, neighborhood, houghCluster, rhoThetaAccumulatorBinMap, thresholdHi);
525  }
526 
527  // Sort the clusters using the SortHoughClusterList metric
528  if (!houghClusters.empty()) houghClusters.sort(SortHoughClusterList(rhoThetaAccumulatorBinMap));
529 
530  return;
531  }
532 
534  SeedHitPairListPair& seedHitPair) const
535  {
536  if (seed3DHits.size() < m_minimum3DHits) return false;
537 
538  reco::PrincipalComponents seedFullPca;
539 
540  m_pcaAlg.PCAAnalysis_3D(seed3DHits, seedFullPca, true);
541 
542  if (!seedFullPca.getSvdOK()) return false;
543 
544  // Use the following to set the 3D doca and arclength for each hit
545  m_pcaAlg.PCAAnalysis_calc3DDocas(seed3DHits, seedFullPca);
546 
547  // Use this info to sort the hits along the principle axis
548  //seed3DHits.sort(SeedFinderAlgBase::Sort3DHitsByArcLen3D());
550 
551  // The idea here is to search for the first hit that lies "close" to the principle axis
552  // At that point we count out n hits to use as the seed
553  reco::HitPairListPtr seedHit3DList;
554  std::set<const reco::ClusterHit2D*> seedHitSet;
555  double aveDocaToAxis = seedFullPca.getAveHitDoca();
556  int gapCount(0);
557 
558  // Now loop through hits to search for a "continuous" block of at least m_numSeed2DHits
559  // We'll arrive at that number by collecting 2D hits in an stl set which will keep track of unique occurances
560  for (reco::HitPairListPtr::iterator peakBinItr = seed3DHits.begin();
561  peakBinItr != seed3DHits.end();
562  peakBinItr++) {
563  const reco::ClusterHit3D* hit3D = *peakBinItr;
564 
565  if (hit3D->getDocaToAxis() < m_numAveDocas * aveDocaToAxis) {
566  // Check if we need to reset because of gap count
567  if (gapCount > m_numSkippedHits) {
568  seedHit3DList.clear();
569  seedHitSet.clear();
570  }
571 
572  seedHit3DList.push_back(hit3D);
573 
574  for (const auto& hit : hit3D->getHits())
575  seedHitSet.insert(hit);
576 
577  gapCount = 0;
578  }
579  else
580  gapCount++;
581 
582  if (seedHitSet.size() > m_numSeed2DHits) break;
583  }
584 
585  // If not enough hits then we are done
586  if (seedHit3DList.size() < m_minimum3DHits) return false;
587 
589 
590  // Use only the "seed" 3D hits to get new PCA axes
591  m_pcaAlg.PCAAnalysis_3D(seedHit3DList, seedPca, true);
592 
593  if (!seedPca.getSvdOK()) return false;
594 
595  m_pcaAlg.PCAAnalysis_calc3DDocas(seedHit3DList, seedPca);
596  //seedHit3DList.sort(SeedFinderAlgBase::Sort3DHitsByAbsArcLen3D());
597  seedHit3DList.sort(SeedFinderAlgBase::Sort3DHitsByArcLen3D());
598 
599  // Now translate the seedCenter by the arc len to the first hit
600  double seedCenter[3] = {
601  seedPca.getAvePosition()[0], seedPca.getAvePosition()[1], seedPca.getAvePosition()[2]};
602  double seedDir[3] = {seedPca.getEigenVectors().row(2)[0],
603  seedPca.getEigenVectors().row(2)[1],
604  seedPca.getEigenVectors().row(2)[2]};
605 
606  double arcLen = seedHit3DList.front()->getArclenToPoca();
607  double seedStart[3] = {seedCenter[0] + arcLen * seedDir[0],
608  seedCenter[1] + arcLen * seedDir[1],
609  seedCenter[2] + arcLen * seedDir[2]};
610 
611  //seedStart[0] = seedHit3DList.front()->getX();
612  //seedStart[1] = seedHit3DList.front()->getY();
613  //seedStart[2] = seedHit3DList.front()->getZ();
614 
615  if (seedHitSet.size() >= 10) {
616  TVector3 newSeedPos;
617  TVector3 newSeedDir;
618  double chiDOF;
619 
620  LineFit2DHits(seedHitSet, seedStart[0], newSeedPos, newSeedDir, chiDOF);
621 
622  if (chiDOF > 0.) {
623  // check angles between new/old directions
624  double cosAng =
625  seedDir[0] * newSeedDir[0] + seedDir[1] * newSeedDir[1] + seedDir[2] * newSeedDir[2];
626 
627  if (cosAng < 0.) newSeedDir *= -1.;
628 
629  seedStart[0] = newSeedPos[0];
630  seedStart[1] = newSeedPos[1];
631  seedStart[2] = newSeedPos[2];
632  seedDir[0] = newSeedDir[0];
633  seedDir[1] = newSeedDir[1];
634  seedDir[2] = newSeedDir[2];
635  }
636  }
637 
638  // Keep track of this seed and the 3D hits that make it up
639  seedHitPair = SeedHitPairListPair(recob::Seed(seedStart, seedDir), seedHit3DList);
640 
641  // We are going to drop a few hits off the ends in the hope this facilitates finding more track like objects, provided there are enough hits
642  if (seed3DHits.size() > 100) {
643  // Need to reset the doca/arclen first
644  m_pcaAlg.PCAAnalysis_calc3DDocas(seed3DHits, seedFullPca);
645 
646  // Now resort the hits
648 
649  size_t numToKeep = seed3DHits.size() - 10;
650 
651  reco::HitPairListPtr::iterator endItr = seed3DHits.begin();
652 
653  std::advance(endItr, numToKeep);
654 
655  seed3DHits.erase(endItr, seed3DHits.end());
656  }
657 
658  return true;
659  }
660 
662  reco::PrincipalComponents& inputPCA,
663  SeedHitPairListPairVec& seedHitPairVec) const
664  {
665  // This will be a busy routine... the basic tasks are:
666  // 1) loop through hits and project to the plane defined by the two largest eigen values, accumulate in Hough space
667  // 2) "Cluster" the Hough space to associate hits which are common to a line
668  // 3) Process these clusters (still to be defined exactly)
669 
670  // Create an interim data structure which will allow us to sort our seeds by "best"
671  // before we return them in the seedHitPairVec
672  typedef std::map<size_t, SeedHitPairListPairVec> SizeToSeedToHitMap;
673 
674  SizeToSeedToHitMap seedHitPairMap;
675  SeedHitPairListPair seedHitPair;
676 
677  // Make sure we are using the right pca
678  reco::HitPairListPtr hitPairListPtr = inputHitPairListPtr;
679 
680  int nLoops(0);
681 
682  // Make a local copy of the input PCA
683  reco::PrincipalComponents pca = inputPCA;
684 
685  // We loop over hits in our list until there are no more
686  while (!hitPairListPtr.empty()) {
687  // We also require that there be some spread in the data, otherwise not worth running?
688  double eigenVal0 = 3. * sqrt(pca.getEigenValues()[2]);
689  double eigenVal1 = 3. * sqrt(pca.getEigenValues()[1]);
690 
691  if (eigenVal0 > 5. && eigenVal1 > 0.001) {
692  // **********************************************************************
693  // Part I: Build Hough space and find Hough clusters
694  // **********************************************************************
695  RhoThetaAccumulatorBinMap rhoThetaAccumulatorBinMap;
696  HoughClusterList houghClusters;
697 
698  findHoughClusters(hitPairListPtr, pca, rhoThetaAccumulatorBinMap, houghClusters);
699 
700  // If no clusters then done
701  if (houghClusters.empty()) break;
702 
703  // **********************************************************************
704  // Part II: Go through the clusters to find the peak bins
705  // **********************************************************************
706 
707  // We need to use a set so we can be sure to have unique hits
708  reco::HitPairListPtr clusterHitsList;
709  std::set<const reco::ClusterHit3D*> masterHitPtrList;
710  std::set<const reco::ClusterHit3D*> peakBinPtrList;
711 
712  size_t firstPeakCount(0);
713 
714  // Loop through the list of all clusters found above
715  for (auto& houghCluster : houghClusters) {
716  BinIndex peakBin = houghCluster.front();
717  size_t peakCount = 0;
718 
719  // Make a local (to this cluster) set of of hits
720  std::set<const reco::ClusterHit3D*> localHitPtrList;
721 
722  // Now loop through the bins that were attached to this cluster
723  for (auto& binIndex : houghCluster) {
724  // An even more local list so we can keep track of peak values
725  std::set<const reco::ClusterHit3D*> tempHitPtrList;
726 
727  // Recover the hits associated to this cluster
728  for (auto& hitItr : rhoThetaAccumulatorBinMap[binIndex].getAccumulatorValues()) {
729  reco::HitPairListPtr::const_iterator hit3DItr = hitItr.getHitIterator();
730 
731  tempHitPtrList.insert(*hit3DItr);
732  }
733 
734  // Trim out any hits already used by a bigger/better cluster
735  std::set<const reco::ClusterHit3D*> tempHit3DSet;
736 
737  std::set_difference(tempHitPtrList.begin(),
738  tempHitPtrList.end(),
739  masterHitPtrList.begin(),
740  masterHitPtrList.end(),
741  std::inserter(tempHit3DSet, tempHit3DSet.end()));
742 
743  tempHitPtrList = tempHit3DSet;
744 
745  size_t binCount = tempHitPtrList.size();
746 
747  if (peakCount < binCount) {
748  peakCount = binCount;
749  peakBin = binIndex;
750  peakBinPtrList = tempHitPtrList;
751  }
752 
753  // Add this to our local list
754  localHitPtrList.insert(tempHitPtrList.begin(), tempHitPtrList.end());
755  }
756 
757  if (localHitPtrList.size() < m_minimum3DHits) continue;
758 
759  if (!firstPeakCount) firstPeakCount = peakCount;
760 
761  // If the peak counts are significantly less than the first cluster's peak then skip
762  if (peakCount < firstPeakCount / 10) continue;
763 
764  // **********************************************************************
765  // Part III: Make a Seed from the peak bin hits
766  // **********************************************************************
767 
768  reco::HitPairListPtr allPeakBinHits;
769 
770  for (const auto& hit3D : localHitPtrList)
771  allPeakBinHits.push_back(hit3D);
772 
773  reco::HitPairListPtr peakBinHits;
774 
775  // Find longest "continuous" set of hits and use these for the seed
776  findHitGaps(allPeakBinHits, peakBinHits);
777 
778  if (peakBinHits.size() < m_minimum3DHits) continue;
779 
780  // We now build the actual seed.
781  if (buildSeed(peakBinHits, seedHitPair)) {
782  // Keep track of this in our map (which will do ordering for us)
783  seedHitPairMap[peakBinHits.size()].push_back(seedHitPair);
784 
785  // For visual testing in event display, mark all the hits in the first seed so we can see them
786  if (seedHitPairMap.size() == 1) {
787  for (const auto& hit3D : peakBinHits)
788  hit3D->setStatusBit(0x40000000);
789  }
790 
791  // for(const auto& hit3D : seedHitPair.second) hit3D->setStatusBit(0x40000000);
792  }
793 
794  // Our peakBinHits collection will most likely be a subset of the localHitPtrList collection
795  // We want to remove only the "pure" hits which are those in the peakBinHits collection
796  // So, sort them and then add to our master list
797  peakBinHits.sort();
798 
799  masterHitPtrList.insert(peakBinHits.begin(), peakBinHits.end());
800 
801  if (hitPairListPtr.size() - masterHitPtrList.size() < m_minimum3DHits) break;
802  } // end loop over hough clusters
803 
804  // If the masterHitPtrList is empty then nothing happened and we're done
805  if (masterHitPtrList.empty()) break;
806 
807  // **********************************************************************
808  // Part IV: Remove remaining peak bin hits from HitPairPtrList
809  // **********************************************************************
810 
811  hitPairListPtr.sort();
812 
813  reco::HitPairListPtr::iterator newListEnd = std::set_difference(hitPairListPtr.begin(),
814  hitPairListPtr.end(),
815  masterHitPtrList.begin(),
816  masterHitPtrList.end(),
817  hitPairListPtr.begin());
818 
819  hitPairListPtr.erase(newListEnd, hitPairListPtr.end());
820 
821  if (hitPairListPtr.size() < m_minimum3DHits) break;
822 
823  if (nLoops++ > m_maxLoopsPerCluster) break;
824 
825  // ********************************************************
826  }
827  else
828  break; // eigen values not in range
829 
830  // At this point run the PCA on the remaining hits
831  m_pcaAlg.PCAAnalysis_3D(hitPairListPtr, pca, true);
832 
833  if (!pca.getSvdOK()) break;
834  }
835 
836  // The final task before returning is to transfer the stored seeds into the output seed vector
837  // What we want to do is make sure the first seeds are the "best" seeds which is defined as the
838  // seeds which were associated to the most hits by the Hough Transform. Our seed map will have
839  // the reverse of this ordering so we simply iterate through it "backwards"
840  for (SizeToSeedToHitMap::reverse_iterator seedMapItr = seedHitPairMap.rbegin();
841  seedMapItr != seedHitPairMap.rend();
842  seedMapItr++) {
843  for (const auto& seedHitPair : seedMapItr->second) {
844  seedHitPairVec.emplace_back(seedHitPair);
845  }
846  }
847 
848  return true;
849  }
850 
852  reco::PrincipalComponents& inputPCA,
853  reco::HitPairListPtrList& hitPairListPtrList) const
854  {
855  // The goal of this routine is run the Hough Transform on the input set of hits
856  // and then to return a list of lists of hits which are associated to a given line
857 
858  // Make sure we are using the right pca
859  reco::HitPairListPtr hitPairListPtr = inputHitPairListPtr;
860 
861  // Make a local copy of the input PCA
862  reco::PrincipalComponents pca = inputPCA;
863 
864  // We also require that there be some spread in the data, otherwise not worth running?
865  double eigenVal0 = 3. * sqrt(pca.getEigenValues()[2]);
866  double eigenVal1 = 3. * sqrt(pca.getEigenValues()[1]);
867 
868  if (eigenVal0 > 5. && eigenVal1 > 0.001) {
869  // **********************************************************************
870  // Part I: Build Hough space and find Hough clusters
871  // **********************************************************************
872  RhoThetaAccumulatorBinMap rhoThetaAccumulatorBinMap;
873  HoughClusterList houghClusters;
874 
875  findHoughClusters(hitPairListPtr, pca, rhoThetaAccumulatorBinMap, houghClusters);
876 
877  // **********************************************************************
878  // Part II: Go through the clusters to find the peak bins
879  // **********************************************************************
880 
881  // We need to use a set so we can be sure to have unique hits
882  reco::HitPairListPtr clusterHitsList;
883  std::set<const reco::ClusterHit3D*> masterHitPtrList;
884  std::set<const reco::ClusterHit3D*> peakBinPtrList;
885 
886  size_t firstPeakCount(0);
887 
888  // Loop through the list of all clusters found above
889  for (auto& houghCluster : houghClusters) {
890  BinIndex peakBin = houghCluster.front();
891  size_t peakCount = 0;
892 
893  // Make a local (to this cluster) set of of hits
894  std::set<const reco::ClusterHit3D*> localHitPtrList;
895 
896  // Now loop through the bins that were attached to this cluster
897  for (auto& binIndex : houghCluster) {
898  // An even more local list so we can keep track of peak values
899  std::set<const reco::ClusterHit3D*> tempHitPtrList;
900 
901  // Recover the hits associated to this cluster
902  for (auto& hitItr : rhoThetaAccumulatorBinMap[binIndex].getAccumulatorValues()) {
903  reco::HitPairListPtr::const_iterator hit3DItr = hitItr.getHitIterator();
904 
905  tempHitPtrList.insert(*hit3DItr);
906  }
907 
908  // Trim out any hits already used by a bigger/better cluster
909  std::set<const reco::ClusterHit3D*> tempHit3DSet;
910 
911  std::set_difference(tempHitPtrList.begin(),
912  tempHitPtrList.end(),
913  masterHitPtrList.begin(),
914  masterHitPtrList.end(),
915  std::inserter(tempHit3DSet, tempHit3DSet.end()));
916 
917  tempHitPtrList = tempHit3DSet;
918 
919  size_t binCount = tempHitPtrList.size();
920 
921  if (peakCount < binCount) {
922  peakCount = binCount;
923  peakBin = binIndex;
924  peakBinPtrList = tempHitPtrList;
925  }
926 
927  // Add this to our local list
928  localHitPtrList.insert(tempHitPtrList.begin(), tempHitPtrList.end());
929  }
930 
931  if (localHitPtrList.size() < m_minimum3DHits) continue;
932 
933  if (!firstPeakCount) firstPeakCount = peakCount;
934 
935  // If the peak counts are significantly less than the first cluster's peak then skip
936  if (peakCount < firstPeakCount / 10) continue;
937 
938  // **********************************************************************
939  // Part III: Make a list of hits from the total number associated
940  // **********************************************************************
941 
942  hitPairListPtrList.push_back(reco::HitPairListPtr());
943 
944  hitPairListPtrList.back().resize(localHitPtrList.size());
945  std::copy(
946  localHitPtrList.begin(), localHitPtrList.end(), hitPairListPtrList.back().begin());
947 
948  // We want to remove the hits which have been used from further contention
949  masterHitPtrList.insert(localHitPtrList.begin(), localHitPtrList.end());
950 
951  if (hitPairListPtr.size() - masterHitPtrList.size() < m_minimum3DHits) break;
952  } // end loop over hough clusters
953  }
954 
955  return true;
956  }
957 
958  //------------------------------------------------------------------------------
959  void HoughSeedFinderAlg::LineFit2DHits(std::set<const reco::ClusterHit2D*>& hit2DSet,
960  double XOrigin,
961  TVector3& Pos,
962  TVector3& Dir,
963  double& ChiDOF) const
964  {
965  // The following is lifted from Bruce Baller to try to get better
966  // initial parameters for a candidate Seed. It is slightly reworked
967  // which is why it is included here instead of used as is.
968  //
969  // Linear fit using X as the independent variable. Hits to be fitted
970  // are passed in the hits vector in a pair form (X, WireID). The
971  // fitted track position at XOrigin is returned in the Pos vector.
972  // The direction cosines are returned in the Dir vector.
973  //
974  // SVD fit adapted from $ROOTSYS/tutorials/matrix/solveLinear.C
975  // Fit equation is w = A(X)v, where w is a vector of hit wires, A is
976  // a matrix to calculate a track projected to a point at X, and v is
977  // a vector (Yo, Zo, dY/dX, dZ/dX).
978  //
979  // Note: The covariance matrix should also be returned
980  // B. Baller August 2014
981 
982  // assume failure
983  ChiDOF = -1;
984 
985  if (hit2DSet.size() < 4) return;
986 
987  const unsigned int nvars = 4;
988  unsigned int npts = hit2DSet.size();
989 
990  TMatrixD A(npts, nvars);
991  // vector holding the Wire number
992  TVectorD w(npts);
993  unsigned short ninpl[3] = {0};
994  unsigned short nok = 0;
995  unsigned short iht(0);
996 
997  // Loop over unique 2D hits from the input list of 3D hits
998  for (const auto& hit : hit2DSet) {
999  geo::WireID const& wireID = hit->WireID();
1000  auto const& plane = m_wireReadoutGeom->Plane(wireID);
1001  unsigned int const ipl = wireID.Plane;
1002 
1003  // get the wire plane offset
1004  double const off = plane.WireCoordinate(geo::Point_t{});
1005 
1006  // get the "cosine-like" component
1007  double const cw = plane.WireCoordinate(geo::Point_t{0., 1., 0.}) - off;
1008 
1009  // the "sine-like" component
1010  double const sw = plane.WireCoordinate(geo::Point_t{0., 0., 1.}) - off;
1011 
1012  double const x = hit->getXPosition() - XOrigin;
1013 
1014  A[iht][0] = cw;
1015  A[iht][1] = sw;
1016  A[iht][2] = cw * x;
1017  A[iht][3] = sw * x;
1018  w[iht] = wireID.Wire - off;
1019 
1020  ++ninpl[ipl];
1021 
1022  // need at least two points in a plane
1023  if (ninpl[ipl] == 2) ++nok;
1024 
1025  ++iht;
1026  }
1027 
1028  // need at least 2 planes with at least two points
1029  if (nok < 2) return;
1030 
1031  TDecompSVD svd(A);
1032  bool ok;
1033  TVectorD tVec = svd.Solve(w, ok);
1034 
1035  ChiDOF = 0;
1036 
1037  // not enough points to calculate Chisq
1038  if (npts <= 4) return;
1039 
1040  for (const auto& hit : hit2DSet) {
1041  geo::WireID const& wireID = hit->WireID();
1042  auto const& plane = m_wireReadoutGeom->Plane(wireID);
1043  double const off = plane.WireCoordinate(geo::Point_t{0., 0., 0.});
1044  double const cw = plane.WireCoordinate(geo::Point_t{0., 1., 0.}) - off;
1045  double const sw = plane.WireCoordinate(geo::Point_t{0., 0., 1.}) - off;
1046  double const x = hit->getXPosition() - XOrigin;
1047  double const ypr = tVec[0] + tVec[2] * x;
1048  double const zpr = tVec[1] + tVec[3] * x;
1049  double const diff = ypr * cw + zpr * sw - (wireID.Wire - off);
1050  ChiDOF += diff * diff;
1051  }
1052 
1053  auto const& plane = m_wireReadoutGeom->Plane({0, 0, 0});
1054  float werr2 = plane.WirePitch() * plane.WirePitch();
1055  ChiDOF /= werr2;
1056  ChiDOF /= (float)(npts - 4);
1057 
1058  double norm = sqrt(1 + tVec[2] * tVec[2] + tVec[3] * tVec[3]);
1059  Dir[0] = 1 / norm;
1060  Dir[1] = tVec[2] / norm;
1061  Dir[2] = tVec[3] / norm;
1062 
1063  Pos[0] = XOrigin;
1064  Pos[1] = tVec[0];
1065  Pos[2] = tVec[1];
1066 
1067  } // TrkLineFit()
1068 
1069 } // namespace lar_cluster3d
Float_t x
Definition: compare.C:6
void LineFit2DHits(std::set< const reco::ClusterHit2D * > &hitList, double XOrigin, TVector3 &Pos, TVector3 &Dir, double &ChiDOF) const
intermediate_table::iterator iterator
Define a comparator which will sort hits by arc length along a PCA axis.
void PCAAnalysis_calc3DDocas(const reco::HitPairListPtr &hitPairVector, const reco::PrincipalComponents &pca) const
void findHitGaps(reco::HitPairListPtr &inputHitList, reco::HitPairListPtr &outputList) const
Using Principal Components Axis, look for gaps in a list of 3D hits.
bool getSvdOK() const
Definition: Cluster3D.h:240
constexpr auto const & right(const_AssnsIter< L, R, D, Dir > const &a, const_AssnsIter< L, R, D, Dir > const &b)
Definition: AssnsIter.h:102
void PCAAnalysis_3D(const reco::HitPairListPtr &hitPairList, reco::PrincipalComponents &pca, bool skeletonOnly=false) const
void findHoughClusters(const reco::HitPairListPtr &inputHits, reco::PrincipalComponents &pca, RhoThetaAccumulatorBinMap &rhoThetaMap, HoughClusterList &clusterList) const
std::vector< TVirtualPad * > m_Pads
View pads in current canvas.
double WireCoordinate(Point_t const &point) const
Returns the coordinate of the point on the plane, in wire units.
Definition: PlaneGeo.h:704
const Eigen::Vector3f getPosition() const
Definition: Cluster3D.h:155
std::vector< AccumulatorValues > AccumulatorValuesVec
bool findTrackSeeds(reco::HitPairListPtr &hitPairListPtr, reco::PrincipalComponents &inputPCA, SeedHitPairListPairVec &seedHitPairVec) const override
Given the list of hits this will search for candidate Seed objects and return them.
cout<< "Opened file "<< fin<< " ixs= "<< ixs<< endl;if(ixs==0) hhh=(TH1F *) fff-> Get("h1")
Definition: AddMC.C:8
HoughSeedFinderAlg(fhicl::ParameterSet const &pset)
Constructor.
WireID_t Wire
Index of the wire within its plane.
Definition: geo_types.h:430
intermediate_table::const_iterator const_iterator
std::list< HitPairListPtr > HitPairListPtrList
Definition: Cluster3D.h:328
bool operator()(const reco::ClusterHit3D *left, const reco::ClusterHit3D *right) const
unsigned int getStatusBits() const
Definition: Cluster3D.h:154
float getDocaToAxis() const
Definition: Cluster3D.h:166
Define a comparator which will sort hits by the absolute value of arc length so hits are ordered clos...
decltype(auto) constexpr size(T &&obj)
ADL-aware version of std::size.
Definition: StdUtils.h:101
float getAveHitDoca() const
Definition: Cluster3D.h:245
void expandHoughCluster(BinIndex &curBin, HoughCluster &neighborPts, HoughCluster &houghCluster, RhoThetaAccumulatorBinMap &rhoThetaAccumulatorBinMap, size_t threshold) const
HoughSeedFinderAlg::RhoThetaAccumulatorBinMap & m_accMap
const EigenValues & getEigenValues() const
Definition: Cluster3D.h:242
This is an algorithm for finding recob::Seed objects in 3D clusters.
void HoughRegionQuery(BinIndex &curBin, RhoThetaAccumulatorBinMap &rhoThetaAccumulatorBinMap, HoughCluster &neighborPts, size_t threshold) const
decltype(auto) values(Coll &&coll)
Range-for loop helper iterating across the values of the specified collection.
parameter set interface
T get(std::string const &key) const
Definition: ParameterSet.h:314
const Eigen::Vector3f & getAvePosition() const
Definition: Cluster3D.h:244
const AccumulatorValuesVec & getAccumulatorValues() const
std::list< HoughCluster > HoughClusterList
std::list< const reco::ClusterHit3D * > HitPairListPtr
Definition: Cluster3D.h:326
bool operator()(const HoughSeedFinderAlg::HoughCluster &left, const HoughSeedFinderAlg::HoughCluster &right)
bool operator()(const reco::ClusterHit3D *left, const reco::ClusterHit3D *right)
PlaneID_t Plane
Index of the plane within its TPC.
Definition: geo_types.h:373
bool buildSeed(reco::HitPairListPtr &seed3DHits, SeedHitPairListPair &seedHitPair) const
Given a list of candidate "seed" 3D hits, build the seed and get associated unique 2D hits...
bool operator()(const HoughSeedFinderAlg::RhoThetaAccumulatorBinMap::iterator &left, const HoughSeedFinderAlg::RhoThetaAccumulatorBinMap::iterator &right)
This is used to sort bins in Hough Space.
std::map< BinIndex, AccumulatorBin > RhoThetaAccumulatorBinMap
double value
Definition: spectrum.C:18
Detector simulation of raw signals on wires.
reco::HitPairListPtr::const_iterator m_hit3DIterator
This will be used to take us back to our 3D hit.
bool findTrackHits(reco::HitPairListPtr &hitPairListPtr, reco::PrincipalComponents &inputPCA, reco::HitPairListPtrList &hitPairListPtrList) const
Given the list of hits this will return the sets of hits which belong on the same line...
ROOT::Math::PositionVector3D< ROOT::Math::Cartesian3D< double >, ROOT::Math::GlobalCoordinateSystemTag > Point_t
Type for representation of position in physical 3D space.
Definition: geo_vectors.h:180
constexpr auto const & left(const_AssnsIter< L, R, D, Dir > const &a, const_AssnsIter< L, R, D, Dir > const &b)
Definition: AssnsIter.h:94
Float_t sw
Definition: plot.C:20
const Eigen::Vector3f & getPosition() const
decltype(auto) get(T &&obj)
ADL-aware version of std::to_string.
Definition: StdUtils.h:120
bool operator()(const std::pair< size_t, size_t > &left, const std::pair< size_t, size_t > &right)
Float_t norm
Encapsulate the construction of a single detector plane .
std::vector< SeedHitPairListPair > SeedHitPairListPairVec
Eigen::Vector3f m_position
We really only need the x,y coordinates here but keep all three for now.
std::pair< recob::Seed, reco::HitPairListPtr > SeedHitPairListPair
SortHoughClusterList(HoughSeedFinderAlg::RhoThetaAccumulatorBinMap &accMap)
This is used to sort "Hough Clusters" by the maximum entries in a bin.
PlaneGeo const & Plane(TPCID const &tpcid, View_t view) const
Returns the specified wire.
AccumulatorValues()
A utility class to contain the values of a given "bin" in Hough Space.
AccumulatorBin()
A utility class used to accumulate the above values.
std::vector< std::unique_ptr< TCanvas > > m_Canvases
Graphical trace canvases.
Float_t w
Definition: plot.C:20
const ClusterHit2DVec & getHits() const
Definition: Cluster3D.h:168
AccumulatorValues(const Eigen::Vector3f &position, const reco::HitPairListPtr::const_iterator &itr)
bool Hit3DCompare(const reco::ClusterHit3D *left, const reco::ClusterHit3D *right)
reco::HitPairListPtr::const_iterator getHitIterator() const
double WirePitch() const
Return the wire pitch (in centimeters). It is assumed constant.
Definition: PlaneGeo.h:312
const EigenVectors & getEigenVectors() const
Definition: Cluster3D.h:243
geo::WireReadoutGeom const * m_wireReadoutGeom