[ GAMB | Source | Keywords | Summary | Ancestors | All Members | Descendants ]
public: | |
ClusterList(); | |
void | addNeighbors(const Data& data1, const Data& data2); |
void | addNeighbors(const Data& data1, const Data& data2, float dist); |
iterator | addCluster(const Data& data); |
iterator | addCluster(const Data& data, const Cluster& cluster); |
void | cluster(float maxDist); |
void | fastCluster(float maxDist); |
const_iterator | getCluster(const Data& data) const; |
iterator | getCluster(const Data& data); |
// Container Methods | |
const_iterator | begin() const; |
iterator | begin(); |
const_iterator | end() const; |
iterator | end(); |
size_type | size() const; |
protected: |
Back to the top of ClusterList
Copyright: SAMBA group, Tel-Aviv Univ. Israel, 1997.
Back to the top of ClusterList
Back to the top of ClusterList
Back to the top of ClusterList
float dist(const Cluster&);b. A join method capable of joining two clusters. The join method receives a single argument of type Cluster and should join the given Cluster object with the parent object (this).
void join(const Cluster&);c. The updates() method. Under normal circumstances the updates() method should return the number of times the method join was called on the given class instance. The updates method is used as a signature for the Cluster instance whether it has been updated. If two Cluster instances have not been updated then the distance between them need not be recalculated. The updates function may be used to minimize the calls to the dist method when calculating the distance between two Cluster objects is time consuming. For example if the user has the updates() method return a constant 0, the distances between the Cluster objects will never be calculated and the distance between the Cluster elements will be used. (This is good for nearest neighbor clustering).
unsigned int updates() const;d. An explicit constructor that constructs a Cluster object from a Data object. This constructor is needed only if the single argument addCluster method will be used.
explicit Cluster(const Data&);
For Data elements a function object must be defined. The function object template hash<> is used by the STL hash implementation. Therefore hash<> must be specialized for Data i.e. hash with operator() must be defined. It is recommended that the Data elements be light-weight. For example, if user wishes to cluster Vector3 objects then he should define the Data class parameter to be Vector3* and use pointers.
The following is an example of a class named Transformation used to cluster 3-dimensional rigid transformations using 3 rotational parameter and 3 translational parameters. The transformations are clustered (joined) using a weighted average. The Data elements are defined to be Transformation*.
class Transformation { public: Transformation(const ReferenceFrame& rt, const float transScore) : trans(rt), scr(transScore), joins(0) {} float dist(const Transformation& t) const { return (trans.rotation().dist(t.trans.rotation()) + trans.translation().dist(t.trans.translation())/5); } void join(const Transformation& t) { float sum = scr + t.scr; const Rotation3& rot = trans.rotation(); const Rotation3& trot = t.trans.rotation(); trans = ReferenceFrame(Rotation3(rot[0]*scr + trot[0]*t.scr, rot[1]*scr + trot[1]*t.scr, rot[2]*scr + trot[2]*t.scr, rot[3]*scr + trot[3]*t.scr), (trans.translation()*scr + t.trans.translation()*t.scr) / sum); scr = sum; ++joins; } unsigned int updates() const { return joins; } private: ReferenceFrame trans; float scr; int joins; };
For the Transformation class a hash
__STL_TEMPLATE_NULL struct hash<const Transformation*> { size_t operator()(const Transformation* const t) const { return ((size_t)t/sizeof(Transformation)); } };
To use the ClusterList class, the user adds a list of possible neighboring elements and calls the cluster or the fastCluster methods. At any point the user may use ClusterList as an STL-like container to inspect what clusters are present.
The clustering algorithms used by the ClusterList keep the neighbor pairs sorted by their distance. When cluster or fastCluster are called, neighbor pairs with shorter distances are accessed first. Each such pair is a associated with a Cluster. If the distance between the two Cluster objects does not exceed a given threshold they are joined. In the fastCluster version of the algorithm neighbors are processed in the order in which they are found. In the cluster version, neighbor pairs may be repositioned in the distance sorted list if the clusters are changed via previous join operations. Both versions are quite efficient although putting an upper bound on the complexity of cluster method seems difficult.
A function that uses Transformation class to cluster 3-D rigid transformations may look something like the following:
typedef ClusterList<int, Transformation> TransCluster; TransCluster clusterList; for (int i=0; i<count; ++i) clusterList.addCluster(i, transformation[i]); for (int i=0; i<count; ++i) for (int j=i+1; j<count; ++j) if (transformation[i].dist(transformation[j]) < maxDist*2) clusterList.addNeighbors(i, j); clusterList.cluster(maxDist); for (TransCluster::iterator it = clusterList.begin(); it != clusterList.end(); ++it) { cout << (*it);This example assumes the existence of an array of Transformation objects. Also a maxDist parameter sets an upper-bound on the inter-cluster distance for clusters that may be joined. It is assumed that operator<< was defined.
Back to the top of ClusterList
ClusterList();
Back to the top of ClusterList
void addNeighbors(const Data& data1, const Data& data2);
Back to the top of ClusterList
void addNeighbors(const Data& data1, const Data& data2, float dist);
Back to the top of ClusterList
iterator addCluster(const Data& data);
Back to the top of ClusterList
iterator addCluster(const Data& data, const Cluster& cluster);
Back to the top of ClusterList
void cluster(float maxDist);
Back to the top of ClusterList
void fastCluster(float maxDist);
Back to the top of ClusterList
const_iterator getCluster(const Data& data) const;
Back to the top of ClusterList
iterator getCluster(const Data& data);
Back to the top of ClusterList
const_iterator begin() const;
Back to the top of ClusterList
iterator begin();
Back to the top of ClusterList
const_iterator end() const;
Back to the top of ClusterList
iterator end();
Back to the top of ClusterList
size_type size() const;
Back to the top of ClusterList
public: | ||
---|---|---|
void | addNeighbors(const Data& data1, const Data& data2); | |
void | addNeighbors(const Data& data1, const Data& data2, float dist); | |
iterator | addCluster(const Data& data); | |
iterator | addCluster(const Data& data, const Cluster& cluster); | |
void | cluster(float maxDist); | |
void | fastCluster(float maxDist); | |
const_iterator | getCluster(const Data& data) const; | |
iterator | getCluster(const Data& data); | |
// Container Methods | ||
const_iterator | begin() const; | |
iterator | begin(); | |
const_iterator | end() const; | |
iterator | end(); | |
size_type | size() const; | |
protected: |
Back to the top of ClusterList
Back to the top of ClusterList
Back to the top of ClusterList
Report problems to jkotula@unimax.com