ReSCue - Retrieval System for Curves

---

         

---

sampling_matcher.h

#ifndef SAMPLING_MATCHER_H
#define SAMPLING_MATCHER_H

#include "polygonal_curve.h"
#include "rescutil.h"

namespace rescue
{


// ==========================================================================================
// ==========================================================================================
template<class fs_graph>
class sampling_matcher
{

public:

    typedef fs_graph::transporter_edge_class transporter_edge;
    typedef fs_graph::motion motion;
    typedef fs_graph::arithmetic_t arithmetic;
    typedef arithmetic arithmetic_t;
    typedef fs_graph::index_t index_t;
    typedef fs_graph::point point;
        typedef fs_graph::discrete_reparametrization_pair discrete_reparametrization_pair;

    typedef polygonal_curve<point> curve;
    typedef curve::vertex vertex;
    typedef curve::edge edge;

protected:
    
    index_t m;

    index_t n;

    index_t* kappa;

    index_t* lambda;
    
    point* P;

    point* Q;

    arithmetic eps; 

    arithmetic delta;

    bool matched;

    bool match_found;

        bool parametrizations_available;
    
        fs_graph Gamma;

    motion match_motion;

        
        discrete_reparametrization_pair match_kappa_lambda;

    static inline arithmetic dist(const point& x, const point& y);

public:

        bool get_reparametrizations(discrete_reparametrization_pair&);


    sampling_matcher(curve& P, curve& Q, const arithmetic& ee);
    
    sampling_matcher(curve& cP, curve& cQ, const arithmetic& ee, const arithmetic& dd);

    sampling_matcher();

    ~sampling_matcher();

    bool match();

    motion get_match();

    bool get_reparametrized_curves(curve& P_kappa, curve& Q_lambda);

    void clear();

};
// ==========================================================================================
// ==========================================================================================



// ==========================================================================================
template<class fs_graph>
sampling_matcher<fs_graph>::sampling_matcher()
// ==========================================================================================
{

    m = 0;
    n = 0;

    kappa = NULL;
    lambda = NULL;
    
    P = NULL;
    Q = NULL;

    eps = 0.0;
    delta = 0.0;

        parametrizations_available = false;
        matched = false;
        match_found = false;
}


// ==========================================================================================
template<class fs_graph>
sampling_matcher<fs_graph>::sampling_matcher(curve& cP, curve& cQ, const arithmetic& ee, const arithmetic& dd)
// ==========================================================================================
{

        parametrizations_available = false;
        matched = false;
        match_found = false;

    if (cP.length()<0 || cQ.length()<0)
    {
        // matching curves without vertices does not make sense...
        m = -1;
        n = -1;

        kappa = NULL;
        lambda = NULL;
    
        P = NULL;
        Q = NULL;

        eps = 0.0;
        delta = 0.0;

        return;
    }

    eps = ee;
    delta = dd;
    
    kappa = new index_t[m+n+2];
    lambda = new index_t[m+n+2];

    // Construct delta-Samplings

        curve::vertex_iterator v_it, v_end;
    v_it = cP.vertex_begin();
    v_end = cP.vertex_end();
        
        std::list<point> P_cp;
        point P0,P1;
        P1 = (*v_it).pos;
    P_cp.push_back(P1);
        v_it++;

        for (; v_it!=v_end; v_it++)
    {

        // sample the line segment of <p_i,p_{i+1}>
        P0 = P1;
        P1 = (*v_it).pos;

        arithmetic length = sqrt((P0.x-P1.x)*(P0.x-P1.x)+(P0.y-P1.y)*(P0.y-P1.y));
        arithmetic Dx = 2.0*delta*(P1.x-P0.x)/length;
        arithmetic Dy = 2.0*delta*(P1.y-P0.y)/length;

        arithmetic covered = 2.0*delta;

        while (covered<=length)
        {
            P0.x += Dx;
            P0.y += Dy;
            P_cp.push_back(P0);
            covered += 2.0*delta;
        }

        P_cp.push_back(P1);        

    }

    m = P_cp.size()-1;
    P = new point[P_cp.size()];
    std::list<point>::iterator p_it = P_cp.begin();
    index_t i=0;

    for (; p_it!=P_cp.end(); p_it++)
    {
        P[i]=*p_it;
        i++;
    }

    std::list<point> Q_cp;
    v_it = cQ.vertex_begin();
    v_end = cQ.vertex_end();
        point Q0,Q1;
        Q1 = (*v_it).pos;
    Q_cp.push_back(Q1);
        v_it++;

        for (; v_it!=v_end; v_it++)
    {

        // sample the line segment of <p_i,p_{i+1}>
        Q0 = Q1;
        Q1 = (*v_it).pos;

        arithmetic length = sqrt((Q0.x-Q1.x)*(Q0.x-Q1.x)+(Q0.y-Q1.y)*(Q0.y-Q1.y));
        arithmetic Dx = 2.0*delta*(Q1.x-Q0.x)/length;
        arithmetic Dy = 2.0*delta*(Q1.y-Q0.y)/length;

        arithmetic covered = 2.0*delta;

        while (covered<=length)
        {
            Q0.x += Dx;
            Q0.y += Dy;
            Q_cp.push_back(Q0);
            covered += 2.0*delta;
        }

        Q_cp.push_back(Q1);        

    }

    n = Q_cp.size()-1;
    Q = new point[Q_cp.size()];
    std::list<point>::iterator q_it = Q_cp.begin();
    index_t j=0;

    for (; q_it!=Q_cp.end(); q_it++)
    {
        Q[j]=*q_it;
        j++;
    }

}


// ==========================================================================================
template<class fs_graph>
sampling_matcher<fs_graph>::sampling_matcher(curve& cP, curve& cQ, const arithmetic& ee)
// ==========================================================================================
{

        parametrizations_available = false;
        matched = false;
        match_found = false;

    if (cP.length()<0 || cQ.length()<0)
    {
        // matching curves without vertices does not make sense...
        m = -1;
        n = -1;

        kappa = NULL;
        lambda = NULL;
    
        P = NULL;
        Q = NULL;

        eps = 0.0;
        delta = 0.0;

        return;
    }

    eps = ee;
    delta = 0.0;
    
    kappa = new index_t[m+n+2];
    lambda = new index_t[m+n+2];

    m = cP.length();
    P = new point[cP.length()+1];
    Curve::vertex_iterator p_it = cP.vertex_begin();
    index_t i=0;

    for (; p_it!=cP.vertex_end(); p_it++)
    {
        P[i]=(*p_it).pos;
        i++;
    }

    n = cQ.length();
    Q = new point[cQ.length()+1];
    Curve::vertex_iterator q_it = cQ.vertex_begin();
    i=0;

    for (; q_it!=cQ.vertex_end(); q_it++)
    {
        Q[i]=(*q_it).pos;
        i++;
    }

}

// ==========================================================================================
template<class fs_graph>
bool sampling_matcher<fs_graph>::match()
// ==========================================================================================
{

    if (m<0 || n<0)
        return false;

        Gamma.build(P,Q,m,n,eps,delta);

    // We treat the case that both P and Q are points as an exception
    if (m==0 && n==0)
    {
        match_motion = Gamma.get_match();
        return true;
    }

        fs_graph::border_iterator b_it = Gamma.border_begin();
        fs_graph::border_iterator b_end = Gamma.border_end();

    int upd_cnt = 0;
        for (; b_it!=b_end; b_it++)
        {
        upd_cnt++;

                if (Gamma.update(*b_it))
        {
            match_motion = Gamma.get_match();
            parametrizations_available = Gamma.get_reparametrizations(match_kappa_lambda);
                        return true;
        }

        }

    Gamma.clear();

    return false;

}


// ==========================================================================================
template<class fs_graph>
sampling_matcher<fs_graph>::motion sampling_matcher<fs_graph>::get_match()
// ==========================================================================================
{
    return match_motion;
}

// ==========================================================================================
template<class fs_graph>
void sampling_matcher<fs_graph>::clear()
// ==========================================================================================
{
    if (P!=NULL)
        delete[] P;
    if (Q!=NULL)
        delete[] Q;
    if (kappa!=NULL)
        delete[] kappa;
    if (lambda!=NULL)
        delete[] lambda;

    P = NULL;
    Q = NULL;
    kappa = NULL;
    lambda = NULL;

    m = 0;
    n = 0;

    eps = 0.0;
    delta = 0.0;

    Gamma.clear();

}
    
// ==========================================================================================
template<class fs_graph>
sampling_matcher<fs_graph>::~sampling_matcher()
// ==========================================================================================
{
    clear();
}
    

// ==========================================================================================
template<class fs_graph>
inline sampling_matcher<fs_graph>::arithmetic sampling_matcher<fs_graph>::dist(const point& P, const point& Q)
// ==========================================================================================
{
    return sqrt(sqr<arithmetic>(P.x-Q.x)+sqr<arithmetic>(P.y-Q.y));
}

// ==========================================================================================
template<class fs_graph>
bool sampling_matcher<fs_graph>::get_reparametrizations(sampling_matcher<fs_graph>::discrete_reparametrization_pair& d)
// ==========================================================================================
{
        if (!reparametrizations_available)
                return false;
    kappa_lambda = match_kappa_lambda;
        return true;
}


// ==========================================================================================
template<class fs_graph>
bool sampling_matcher<fs_graph>::
    get_reparametrized_curves(curve& P_kappa, curve& Q_lambda)
// ==========================================================================================
{
    P_kappa.clear();
    Q_lambda.clear();

    if (parametrizations_available==false)
        return false;

    typename fs_graph::discrete_reparametrization_pair::iterator kl_pos = match_kappa_lambda.begin();
    typename fs_graph::discrete_reparametrization_pair::iterator kl_end = match_kappa_lambda.end();

    for (; kl_pos!=kl_end; kl_pos++)
    {
        P_kappa.push_back(new polygon_vertex<point>(P[kl_pos->first]));
        point gQ = Q[kl_pos->second];
        gQ *= match_motion;
        Q_lambda.push_back(new polygon_vertex<point>(gQ));
    }

    return true;

}



// ==========================================================================================
// ==========================================================================================

// end of namespace rescue
}

#endif

ReSCue - Retrieval System for Curves
Universität Bonn, Institut für Informatik III, 2001