Class to remember recently assigned clusters This class will remember the current and the last pixel row to allow fast finding of the correct cluster a pixel belongs to. More...

#include <ClusterCache.h>

Public Types
enum	{ c_defaultNumberColumns = 250 }

typedef std::deque< ClusterCandidate >::iterator	iterator
	Define iterator type.

typedef std::deque< ClusterCandidate >::const_iterator	const_iterator
	Define const iterator type.

Public Member Functions
	ClusterCache (unsigned int maxU=c_defaultNumberColumns)
	Create a new cache.

	ClusterCache (const ClusterCache &)=delete
	No copy construction.

ClusterCache &	operator= (const ClusterCache &)=delete
	No operator=.

	~ClusterCache ()
	Delete the cache and free the memory.

void	clear ()
	Clear the cache structure.

ClusterCandidate &	findCluster (unsigned int u, unsigned int v)
	Find a cluster adjacent to the given coordinates.

std::deque< ClusterCandidate >::iterator	begin ()
	Return iterator to the begin of of created clusters.

std::deque< ClusterCandidate >::iterator	end ()
	Return iterator to the end of created clusters.

bool	empty () const
	Check if there are any clusters.

Private Member Functions
ClusterCandidate *	mergeCluster (ClusterCandidate cls1, ClusterCandidate cls2)
	Merge two cluster and update the list of cached clusters.

void	switchRow (unsigned int v)
	Switch the internal rows.

Private Attributes
const unsigned int	m_maxU
	number of columns of the cache.

unsigned int	m_curV
	current v coordinate, needed to switch top row

ClusterCandidate **	m_clsTop
	cache of the top row

ClusterCandidate **	m_clsCur
	cache of the current row

std::deque< ClusterCandidate >	m_clusters
	list of all the clusters created so far

std::deque< ClusterCandidate >::iterator	m_currCluster
	iterator to the next free cluster to be used if a new cluster is needed.

Detailed Description

Class to remember recently assigned clusters This class will remember the current and the last pixel row to allow fast finding of the correct cluster a pixel belongs to.

All hit pixels above noise threshold will be processed sorted, row wise with increasing u (column) and v (row) ids. For each pixel we look at the left neighbor in the same row and the three direct neighbors in the last row. If at least one cluster is found in any of these pixels, all those clusters will be merged and the pixel gets assigned to the existing cluster. Otherwise a new cluster is created. At the end, all clusters will be checked if they satisfy the requirements for a valid cluster (seed and cluster charge) and only valid clusters are kept

Lets assume that we have a hit in the pixel marked with X. If we process the pixels in a sorted way, than we only have to check the pixels marked O to see if this pixel belongs to a cluster. To do this, we cache the top row and the current row. For each pixel, we just have to check the left cluster and three elements of the top row. If we already found a valid left cluster we only have to check the top right position in addition as we are sure that top left and top are already pointing to the same cluster as the left position due to the sorted processing. If we find more than one adjoining cluster (like the clusters 1 and 2 when looking at 3), all those clusters will be merged. After this step the pixels belonging to 2 and 3 will all belong to cluster 1.

We save the row we are currently looking at. Once the v coordinate of the next hit changes we either switch the current row to top row or erase it if the v coordinate changed by more than one (complete row without an hit).

With this algorithm we only have to look at each pixel once and otherwise just update the list of clusters. To further improve performance the number of free/malloc calls is kept to a minimum: The list of clusters is kept in a std::deque (to keep pointer valid at all times) and not cleared between events but reused. Each new cluster keeps the pixel information in a std::vector is constructed with a capacity of 10 pixels so that relocation should only occur in rare cases and the current and top row pointers are kept and reused over the lifetime of the Cache.

*   u → → → → → → → → → →
* v┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
* ↓│ │ │O│O│O│ │ │ │ │ │ │
*  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
* ↓│ │ │O│X│ │ │ │ │ │ │ │
*  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
* ↓│ │ │ │ │ │ │ │ │ │ │ │
*  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
* ↓│ │ │1│ │2│2│ │ │ │ │ │
*  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
* ↓│ │ │ │3│ │ │ │ │ │ │ │
*  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
* ↓│ │ │ │ │ │ │ │ │ │ │ │
*  └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
*

Definition at line 77 of file ClusterCache.h.

Member Typedef Documentation

◆ const_iterator

typedef std::deque<ClusterCandidate>::const_iterator const_iterator

Define const iterator type.

Definition at line 82 of file ClusterCache.h.

◆ iterator

typedef std::deque<ClusterCandidate>::iterator iterator

Define iterator type.

Definition at line 80 of file ClusterCache.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum

Enumerator
c_defaultNumberColumns	Default maximum number of PIXEL columns the cache can handle.

Definition at line 84 of file ClusterCache.h.

           {
        c_defaultNumberColumns = 250
      };

Constructor & Destructor Documentation

◆ ClusterCache()

ClusterCache ( unsigned int maxU = c_defaultNumberColumns )

explicit

Create a new cache.

Definition at line 19 of file ClusterCache.cc.

                                               : m_maxU(maxU + 2)
    {
      m_clsTop = new ClusterCandidate*[m_maxU];
      m_clsCur = new ClusterCandidate*[m_maxU];
      clear();
    }

◆ ~ClusterCache()

~ClusterCache ( )

Delete the cache and free the memory.

Definition at line 26 of file ClusterCache.cc.

    {
      delete[] m_clsTop;
      delete[] m_clsCur;
    }

Member Function Documentation

◆ begin()

std::deque< ClusterCandidate >::iterator begin ( )

inline

Return iterator to the begin of of created clusters.

This list also contains clusters which were already merged with other clusters so one has to check that the cluster size is >0 To loop over all cluster candidates use something like

for(ClusterCandidate &cls: cache){
  //...
}

Definition at line 121 of file ClusterCache.h.

121{ return m_clusters.begin(); }

Belle2::PXD::ClusterCache::m_clusters

std::deque< ClusterCandidate > m_clusters

list of all the clusters created so far

Definition: ClusterCache.h:149

◆ clear()

void clear ( )

Clear the cache structure.

clear the Cache

Definition at line 33 of file ClusterCache.cc.

    {
      memset(m_clsTop, 0, m_maxU * sizeof(ClusterCandidate*));
      memset(m_clsCur, 0, m_maxU * sizeof(ClusterCandidate*));
      m_curV = 0;
      m_currCluster = m_clusters.begin();
    }

◆ empty()

bool empty ( ) const

inline

Check if there are any clusters.

Definition at line 126 of file ClusterCache.h.

126{ return m_clusters.begin() == m_currCluster; }

◆ end()

std::deque< ClusterCandidate >::iterator end ( )

inline

Return iterator to the end of created clusters.

Definition at line 123 of file ClusterCache.h.

123{ return m_currCluster; }

◆ findCluster()

ClusterCandidate & findCluster	(	unsigned int	u,
		unsigned int	v
	)

Find a cluster adjacent to the given coordinates.

If no adjacent cluster is found, a new cluster is returned.

Parameters

u	column id to look for a adjacent clusters
v	row id to look for adjacent clusters

Returns: cluster reference, either existing, adjacent cluster or empty cluster

If no cluster is found, 0 is returned

Definition at line 42 of file ClusterCache.cc.

    {
      if (u >= m_maxU - 2) {
        throw std::out_of_range("u cell id is outside of valid range");
      }
      switchRow(v);
      const unsigned int u1 = u + 1;
      //Look for cluster top of current pixel (0,0 at top left corner, rows going
      //down, columns going left) The ClusterCache is two columns wider than the
      //actual pixel sensor to get rid of edge effects. Column 0 is at index 1 so
      //the three neighbors of column u have the indices (u,u+1,u+2)
 
      //So the left neighbor has index u in the current row
      ClusterCandidate* cls = m_clsCur[u];
      //And the topleft, top and topright clusters have u+i, i in 0..2 But if we
      //already have a left neighbor we do not need to check topleft and top as
      //those are guaranteed to be already merged with the left one
      if (!cls) {
        cls = mergeCluster(cls, m_clsTop[u]);
        cls = mergeCluster(cls, m_clsTop[u1]);
      }
      cls = mergeCluster(cls, m_clsTop[u + 2]);
 
      //If no cluster was found create a new one
      if (!cls) {
        if (m_currCluster == m_clusters.end()) {
          //We already use all ClusterCandidates, create a new one
          m_clusters.emplace_front();
          cls = &m_clusters.front();
        } else {
          //There are some Candidates left, use them
          cls = &(*m_currCluster++);
          cls->clear();
        }
      }
      //Save the cluster and the current position in the cache
      m_curV = v;
      m_clsCur[u1] = cls;
      //Return the cluster
      return *cls;
    }

◆ mergeCluster()

ClusterCandidate * mergeCluster	(	ClusterCandidate *	cls1,
		ClusterCandidate *	cls2
	)

private

Merge two cluster and update the list of cached clusters.

Definition at line 85 of file ClusterCache.cc.

    {
      if (cls2) {
        if (!cls1 || cls1 == cls2) return cls2;
        return cls1->merge(*cls2);
      }
      return cls1;
    }

◆ switchRow()

void switchRow ( unsigned int v )

private

Switch the internal rows.

Switch current and top row or clear cache.

We always keep current and last row. This method switches these rows and resets the new current row

Parameters

v	current row id

Definition at line 95 of file ClusterCache.cc.

    {
      if (v == m_curV) return;
      //Clear top row
      std::memset(m_clsTop, 0, m_maxU * sizeof(ClusterCandidate*));
      //We skipped a row, forget current row, no need to switch rows, both got emptied
      if (v > m_curV + 1) {
        std::memset(m_clsCur, 0, m_maxU * sizeof(ClusterCandidate*));
      } else {
        //Switch rows, Current row will be top and we reuse memory of last top
        //row as new current row
        std::swap(m_clsTop, m_clsCur);
      }
      //save current row coordinate
      m_curV = v;
    }

Member Data Documentation

◆ m_clsCur

ClusterCandidate** m_clsCur

private

cache of the current row

Definition at line 147 of file ClusterCache.h.

◆ m_clsTop

ClusterCandidate** m_clsTop

private

cache of the top row

Definition at line 145 of file ClusterCache.h.

◆ m_clusters

std::deque<ClusterCandidate> m_clusters

private

list of all the clusters created so far

Definition at line 149 of file ClusterCache.h.

◆ m_currCluster

std::deque<ClusterCandidate>::iterator m_currCluster

private

iterator to the next free cluster to be used if a new cluster is needed.

The List of clusters is kept between clustering calls to save malloc/free calls. On clear, this iterator will point to the beginning of m_clusters and will be incremented every time a cluster is needed. Once it reaches m_clusters.end(), new clusters will be added to the front of the m_clusters container.

Definition at line 157 of file ClusterCache.h.

◆ m_curV

unsigned int m_curV

private

current v coordinate, needed to switch top row

Definition at line 143 of file ClusterCache.h.

◆ m_maxU

const unsigned int m_maxU

private

number of columns of the cache.

This is the actual number of columns + 2 to get rid of edge effects

Definition at line 141 of file ClusterCache.h.

The documentation for this class was generated from the following files:

pxd/reconstruction/include/ClusterCache.h
pxd/reconstruction/src/ClusterCache.cc

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ iterator

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ ClusterCache()

◆ ~ClusterCache()

Member Function Documentation

◆ begin()

◆ clear()

◆ empty()

◆ end()

◆ findCluster()

◆ mergeCluster()

◆ switchRow()

Member Data Documentation

◆ m_clsCur

◆ m_clsTop

◆ m_clusters

◆ m_currCluster

◆ m_curV

◆ m_maxU