|| || || || || || || ||

---

RadiusClusteror.h

Go to the documentation of this file.

#ifndef Impala_Core_Feature_RadiusClusteror_h
#define Impala_Core_Feature_RadiusClusteror_h

#include <vector>
#include "Core/Feature/Clusteror.h"
#include "Core/Vector/MinimumSimilarity.h"
#include "Core/Vector/AverageSimilarity.h"
#include "Core/Vector/RadiusSimilarity.h"
#include "Core/Table/RemoveRow.h"

namespace Impala
{
namespace Core
{
namespace Feature
{


template <class SimFunc>
class RadiusClusteror : public Clusteror
{
public:

    typedef Core::Vector::VectorTem<Real64> VectorReal64;

    static const int MODE_ORG = 1;
    static const int MODE_NEW = 2;
    static const int MODE_COUNT = 3;

    RadiusClusteror(int pixelFeatureSet, int regionFeatureSet, Real64 radius,
                    int nrSamplesAtime, int nrWantedClusters,
                    int minElemsInCluster, SimFunc simFunc) :
        Clusteror(pixelFeatureSet, regionFeatureSet, nrWantedClusters,
                  minElemsInCluster)
    {
        mMode = MODE_COUNT;
        mRadius = radius;
        mAllowOverlap = true;
        mAllowSlack = false;
        mSlack = 1.0;
        mSlackStart = -1;
        mNrSamplesAtime = nrSamplesAtime;
        mNrConsidered = 0;
        mCanProcess = true;
        mProcessEnded = -1;
        mSimFunc = simFunc;

        mClusterVec = 0;
        mBuffer = 0;
    }

    virtual String
    GetClusterType() const
    {
        return "radius";
    }

    virtual String
    GetClusterVal() const
    {
        return MakeString(mRadius);
    }

    virtual void
    InitClusterVec(FeatureTable* clusters, String mode, int val)
    {
        CheckFeatureLen(clusters->GetFeatureVectorLength());
        for (int i=0 ; i<clusters->Size() ; i++)
        {
            mClusterVec->Add(clusters->Get1(i), clusters->Get2(i));
            mClusterCount.push_back(0);
        }
        PrintStatus();
    }

    virtual void
    ProcessBuffer()
    {
        ILOG_VAR(Impala.Core.Feature.RadiusClusteror.ProcessBuffer);
        if (!mCanProcess)
        {
            ILOG_ERROR("cannot process, do not call");
            return;
        }

        String dot = (GetRegionFeatureSet() == 0) ? ":" : ".";
        std::cout << dot << std::flush;

        // find the 'best' point for a new cluster
        int bestPoint = -1;
        Real64 maxSim = -1;
        for (int j=0 ; j<mBuffer->Size() ; j++)
        {
            VectorReal64 vec = mBuffer->Get2(j);
            /*
            Real64 sim;
            if (mMode == MODE_ORG)
                sim = Vector::MinimumSimilarity(vec, mBuffer->GetColumn2(),
                                                mBuffer->Size(), mSimFunc);
            if (mMode == MODE_NEW)
                sim = Vector::AverageSimilarity(vec, mBuffer->GetColumn2(),
                                                mBuffer->Size(), mSimFunc);
            if (mMode == MODE_COUNT)
                sim = Vector::RadiusSimilarity(vec, mBuffer->GetColumn2(),
                                               mRadius, mBuffer->Size(),
                                               mSimFunc);
            */
            Real64 sim = Vector::RadiusSimilarity(vec, mBuffer->GetColumn2(),
                                                  mRadius / mSlack,
                                                  mBuffer->Size(), mSimFunc);

            if (sim > maxSim)
            {
                maxSim = sim;  // keep the point with the largest sim
                bestPoint = j;
            }
        }
        std::cout << maxSim << dot << std::flush;
        if (maxSim < 2)
        {   // no sensible candidate found in current buffer
            if (mAllowSlack && (mSlack < 2))
            {
                mSlack *= 2;
                mSlackStart = mNrConsidered;
                return ProcessBuffer();
            }
            mCanProcess = false;
            mProcessEnded = mNrConsidered;
            return;
        }

        mClusterVec->Add(mBuffer->Get1(bestPoint), mBuffer->Get2(bestPoint));

        // remove points within range of the new cluster
        bool* filter = new bool[mBuffer->Size()];
        VectorReal64 bestVec = mBuffer->Get2(bestPoint);
        int count = 0;
        maxSim = -1;
        Real64 radThres = mRadius * ((mAllowOverlap) ? 1.0 : 0.5);
        for (int i=0 ; i<mBuffer->Size() ; i++)
        {
            Real64 sim = mSimFunc.DoIt(bestVec, mBuffer->Get2(i));
            filter[i] = (sim >= radThres);
            if (sim >= mRadius)
                count++;
            if (sim > maxSim)
                maxSim = sim;
        }
        //if (count == 0)
        //    ILOG_INFO("Similarity too high: max = " << maxSim);
        Table::RemoveRow(mBuffer, filter);
        delete filter;

        mClusterCount.push_back(count);
    }

    void
    Cluster(VectorReal64 vec, Quid quid)
    {
        CheckFeatureLen(vec.Size());
        mNrConsidered++;

        // check if a new point is a candidate for a new cluster
        bool isCandidate = true;
        int i = 0;
        Real64 radThres = mRadius * ((mAllowOverlap) ? 1.0 : 0.5);
        while (isCandidate && i<mClusterVec->Size())
        {
            Real64 sim = mSimFunc.DoIt(mClusterVec->Get2(i), vec);
            if (sim >= radThres)
            {
                isCandidate = false;
                if (sim >= mRadius)
                    mClusterCount[i]++;
            }
            i++;
        }
        if (!mCanProcess || HadEnough())
            return;

        // if point is a candidate, add the point to the todo list
        if (isCandidate)
            mBuffer->Add(quid, vec);

        // if buffer large enough, process it
        while ((mBuffer->Size() > mNrSamplesAtime)
               && mCanProcess && (!HadEnough()))
        {
            ProcessBuffer();
        }
    }

    virtual void
    Cluster(FeatureTable* tab)
    {
        for (int i=0 ; i<tab->Size() ; i++)
            Cluster(tab->Get2(i), tab->Get1(i));
    }

    virtual bool
    HadEnough()
    {
        //return CountClusters() >= mNrWantedClusters;
        return mClusterVec->Size() >= mNrWantedClusters;
    }

    virtual void
    FinishBuffer()
    {
        PrintStatus();
        while ((!IsBufferEmpty()) && mCanProcess && (!HadEnough()))
        {
            ProcessBuffer();
        }
        PrintStatus();
    }

    virtual void
    Clusters2FeatureTable(FeatureTable* table)
    {
        PrintStatus();

        bool done = false;
        while (!done)
        {
            int idx = -1;
            //int max = mMinElemsInCluster; // discard clusters with less elems
            int max = -1; // export all clusters
            for (int i=0 ; i<mClusterVec->Size() ; i++)
            {
                if (mClusterCount[i] > max)
                {
                    max = mClusterCount[i];
                    idx = i;
                }
            }
            if (idx != -1)
            {
                table->Add(mClusterVec->Get1(idx), mClusterVec->Get2(idx));
                mClusterCount[idx] = -1;
            }
            else
            {
                done = true;
            }
        }
    }

    virtual void
    PrintStatus()
    {
        int cov = 0;
        int covOK = 0;
        for (int i=0 ; i<mClusterCount.size() ; i++)
        {
            cov += mClusterCount[i];
            if (mClusterCount[i] >= mMinElemsInCluster)
                covOK += mClusterCount[i];
        }

        std::cout << "Clusteror: " << " clusters=" << mClusterVec->Size()
                  << ", ok=" << CountClusters() << ", covered " << cov << "/"
                  << covOK << " of " << mNrConsidered
                  << "  - " << mPixelFeatureSet
                  << "," << mRegionFeatureSet << " - r=" << mRadius << " ("
                  << mRadius / mSlack << "/" << mSlackStart << ")"
                  << " ended=" << mProcessEnded << std::endl;
    }

private:

    void
    CheckFeatureLen(int vecLen)
    {
        if (!mBuffer)
        {
            mClusterVec = new FeatureTable(FeatureDefinition("clusters"),
                                           100, vecLen);
            mBuffer = new FeatureTable(FeatureDefinition("buf"),
                                       mNrSamplesAtime, vecLen);
        }
    }

    // the nr. of clusters for which holds: #elems > mMinElemsInCluster
    int
    CountClusters()
    {
        int nrClusters = 0;
        for (int i=0 ; i<mClusterCount.size() ; i++)
            if (mClusterCount[i] >= mMinElemsInCluster)
                nrClusters++;
        return nrClusters;
    }

    bool
    IsBufferEmpty()
    {
        return (mBuffer->Size() == 0);
    }


    int    mMode;
    Real64 mRadius;
    bool   mAllowOverlap;   // indicates clusters should be 1 or 2 radius apart
    bool   mAllowSlack;     // are we allowed to decrease radius
    Real64 mSlack;
    int    mSlackStart;     // nr considered when adding slack
    int    mNrSamplesAtime; // threshold to start processing buffer
    int    mNrConsidered;   // total nr of points considered for clustering
    bool   mCanProcess;     // does it make sense to consider more features?
    int    mProcessEnded;   // nr considered when stopped processing

    FeatureTable*    mClusterVec;   // the clusters (representative vectors)
    std::vector<int> mClusterCount; // nr. of points belonging to each cluster

    FeatureTable* mBuffer; // list of vectors still to be assigned to a cluster

    SimFunc mSimFunc;

};

} // namespace Feature
} // namespace Core
} // namespace Impala

#endif

---