---

Matching.cpp

Go to the documentation of this file.

#include "Main.h"
#include "viewpoints.h"

//#define TIMEOUT (60 * 3)

pid_t   g_pid;          
fstream g_logFile;      
int g_nTimeout;   

// Function definitions

double OccludeDAG(DAGPtr& ptrDag, double dMaxOcclusionRate)
{
        leda_node v;
        double dOcclusionRate = 0;
        double nNodeMass, nTotalMass = ptrDag->GetNodeCount(); //must be double for division
        int i = 0;

        if (nTotalMass <= 3)
                return 0;
        
        do {
                v = ptrDag->choose_node();
                ASSERT(v != nil);
                
                // ptrDag->GetNodeMass(v) is really cummulative mass now
                nNodeMass = ptrDag->GetTransClosMat().RowSum(ptrDag->GetNodeDFSIndex(v));
                dOcclusionRate = nNodeMass / nTotalMass;
                
        } while (dOcclusionRate > dMaxOcclusionRate && i++ < nTotalMass * 2);

        if (dOcclusionRate > dMaxOcclusionRate)
                return 0;

        ptrDag->DeleteSubDAG(v);
        ptrDag->ComputeDerivedValues();
                
        return dOcclusionRate;
}

int AsyncIndexDAG(const DAG* pQueryDag, DAGDatabase& dagDB, MATCHINFO& info, STATINFO& idxSt)
{
        int* pnCount = new int(0);
        
        if ((g_pid = fork()) != 0)
        {
                int status;     
                waitpid(g_pid, &status, 0);

                if (!(WIFEXITED(status)))
                {
                        cerr << "\nSegmentation fault when indexing " << pQueryDag->GetDAGLbl() << endl;
                        *pnCount = 0;
                }
                        
                int count = *pnCount;
                delete pnCount;
                DBG_MSG1("At parent", count)
                // Parent process is done, function returns normaly
                return count;
        }
        
        // Child process starts here
        *pnCount = dagDB.GetSimilar(*pQueryDag, idxSt.matchList, info.idxrange,
                info.modelSimWeight, info.idxtau);
        DBG_MSG1("At child", *pnCount)  
        _exit(0);
}

double AsyncMatchDAG(const DAG* pQueryDag, const DAG* pModelDag, DAGNodeMap& nodeMap)
{
        double* pdSim = new double(0);
        
        if ((g_pid = fork()) != 0)
        {
                int status;     
                waitpid(g_pid, &status, 0);

                if (!(WIFEXITED(status)))
                {
                        cerr << "\nSegmentation fault when matching " << pQueryDag->GetDAGLbl()
                                << " against " << pModelDag->GetDAGLbl() << endl;
                                
                        *pdSim = 0;
                }
                        
                double sim = *pdSim;
                delete pdSim;
                
                // Parent process is done, function returns normaly
                return sim;
        }
        
        // Child process starts here
        *pdSim = pQueryDag->Similarity(*pModelDag, nodeMap);
        _exit(0);
}


time_t MatchDAG(const DAG* pTargetDag, DAGDatabase& dagDB, MATCHINFO& info, 
                          STATINFO& idxSt, STATINFO& matSt)
{
        double dSim;
        DAGNodeMap nodeMap;
        DAGPtr ptrDag;
        int i;
        time_t startTime, endTime;

        startTime = time(NULL);

        // Index with target DAG
        int count;
        
        /*if (info.asyncCompu)
                count = AsyncIndexDAG(pTargetDag, dagDB, info, idxSt);
        else*/
                count = dagDB.GetSimilar(*pTargetDag, idxSt.matchList, info.idxrange,
                        info.modelSimWeight, info.idxtau);

        matSt.matchList.resize(count);

        // Match DAGs returned by the index
        for (i = 0; i < count; i++)
        {
                dSim = idxSt.matchList[i].dSimilarity;
                
                if (dSim < info.idxtau)
                        break;

                // Only retrive the K best allowing multiplicity of the last k one.

                if (i > info.idxKBest && dSim < idxSt.matchList[info.idxKBest].dSimilarity)
                        break;

                ptrDag = dagDB.ReadDAG(idxSt.matchList[i].nDAGId, true);

                if (ptrDag.IsNull())
                {
                        cerr << "Can't read DAG" << idxSt.matchList[i].nDAGId << endl;
                        break;
                }

                /*if (info.asyncCompu)
                        dSim = AsyncMatchDAG(pTargetDag, ptrDag, nodeMap);
                else*/
                        dSim = pTargetDag->Similarity(ptrDag, nodeMap);

                if (dSim >= info.matchtau)
                        matSt.matchList[i].Set(ptrDag, dSim);
                
                idxSt.matchList[i].ptrDAG = ptrDag;
        }

        // Sort best matches
        matSt.matchList.sort();

        endTime = time(NULL);

        if (info.computeStats)
        {
                idxSt.ComputeStats(pTargetDag);
                matSt.ComputeStats(pTargetDag);
                idxSt.ComputeCrossRankingIdxStats(matSt);
        }

        return endTime - startTime;
}


void MatchDAG(const DAG* pImgDag, DAGDatabase& dagDB, MATCHINFO& info, 
                          streamoff nModelDagOffset, STATINFO& matSt)
{
        double dSim;
        DAGNodeMap nodeMap;
        DAGPtr ptrDag;

        matSt.matchList.resize(1);

        // Match model DAG
        ptrDag = dagDB.ReadDAG(nModelDagOffset, pImgDag->ClassName());

        if (ptrDag.IsNull())
        {
                cerr << "Can't read DAG with offset " << nModelDagOffset << endl << flush;
                return;
        }

        dSim = pImgDag->Similarity(*ptrDag, nodeMap);

        matSt.matchList[0].Set(ptrDag, dSim);
}

void SaveResults(const DAG* pTarget, DAGDatabase& dagDB, 
                                 STATINFO& idxSt, STATINFO& matSt, ostream& os)
{
        const int RANK = 8;
        const int DAGID = 15;
        const int OBJNAME = 25;
        const int VIEWNUM = 10;
        const int SIMIL = 10;
        int i;
        
        os.flags(ios::left);

        os << "\nChoosen graph: " << pTarget->GetDAGLbl();
        os << "\nDAG ID: " << pTarget->GetDAGId() << endl;

        os << "\nINDEXING RESULTS\n\n";
        os << setw(RANK) << "Rank" << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "Object Name" 
                << setw(VIEWNUM) << "View #" << setw(SIMIL) << "Similarity" << endl;
        
        for(i = 0; i < idxSt.matchList.size() && i < matSt.matchList.size(); i++)
        {
                const MatchInfo& info = idxSt.matchList[i];
                
                if (info.dSimilarity == 0.0)
                        break;

                const DAGPtr ptrDAG = (info.ptrDAG.IsNull()) ? dagDB.ReadDAG(info.nDAGId, true):info.ptrDAG;

                os << endl; 
                os << setw(RANK)    << i;
                os << setw(DAGID)   << ptrDAG->GetDAGId();
                os << setw(OBJNAME) << ptrDAG->GetObjName();
                os << setw(VIEWNUM) << ptrDAG->GetViewNumber();
                os << setw(SIMIL)   << info.dSimilarity;
        }

        os << "\n\nMATCHING RESULTS\n\n";
        os << setw(RANK) << "Rank" << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "Object Name" 
                << setw(VIEWNUM) << "View #" << setw(SIMIL) << "Similarity" << endl;

        for(i = 0; i < matSt.matchList.size(); i++)
        {
                const MatchInfo& info = matSt.matchList[i];

                if (info.dSimilarity == 0.0)
                        break;

                os << endl;
                os << setw(RANK)    << i;
                os << setw(DAGID)   << info.ptrDAG->GetDAGId();
                os << setw(OBJNAME) << info.ptrDAG->GetObjName();
                os << setw(VIEWNUM) << info.ptrDAG->GetViewNumber();
                os << setw(SIMIL)   << info.dSimilarity;
        }

        if (matSt.bCompViewStats)
        {
                int v1 = 0, v2 = 0, v3 = 0;
                GetClosestViews(pTarget->GetViewNumber(), 3, v1, v2, v3);
                
                SmartArray<int> secLevClosViews(0, 9);
                GetClosestViews2(pTarget->GetViewNumber(), 3, secLevClosViews, false);

                os << endl;
                os << "\n\nStatistics:\n";
                os << "\n\nClosest views: " << v1 << ' ' << v2 << ' ' << v3;
                os << "\n\nClosest 2nd level views: ";
                secLevClosViews.Print(os);
                os << endl;
        }
}

bool ShowResults(const DAG* pTarget, STATINFO& matSt, 
        DAGDatabase& queryDB, DAGDatabase& modelDB, int nTgtID /*=-1*/) 
{
        int i;

        cout << endl << "Query DAG: " << pTarget->GetDAGLbl() << endl;

        for (i = 0; i < matSt.matchList.size() && AskBool("\nShow next matching result"); i++)
                if (matSt.matchList[i].dSimilarity > 0.0)
                {
                        if (nTgtID == -1)
                                ShowMatch(pTarget, matSt.matchList[i].ptrDAG);
                        else
                                ShowMatch(queryDB, nTgtID, modelDB, matSt.matchList[i].nDAGId);
                }

        // If answered NO...
        if (i < matSt.matchList.size()) 
                return AskBool("\nKeep showing matches for other queries");
}

void AddSubsamplingInfo(ViewSubsampler& vs, const DAG* pTarget, STATINFO& matSt, int kBest)
{       
        SmartArray<int> closestViews(0, 9);
        
        GetClosestViews2(pTarget->GetViewNumber(), 3, closestViews, true);
        vs.AddViewWeights(128, pTarget, matSt.matchList, closestViews, kBest);  
}

void SaveSubsamplingInfo(ViewSubsampler& vs, String strDBFileName)
{
        char szFileName[MAX_PATH];
        
        DirWalker::ChangeFileExt(strDBFileName, NULL, szFileName);
        strcat(szFileName, "_subsampling.inf");

        vs.SaveViewWeights(szFileName);
}

void ShowMatch(DAGDatabase& dagDB1, int nDag1Id, DAGDatabase& dagDB2, int nDag2Id) 
{
        ShowMatch(dagDB1.ReadDAG(nDag1Id), dagDB2.ReadDAG(nDag2Id));
}

void ShowMatch(const DAG* pDag1, const DAG* pDag2)
{
        DAGNodeMap nodeMap;

        pDag1->Similarity(*pDag2, nodeMap);

        /*DAGPtr ptrCpDag1 = pDag1->CreateObject();
        DAGPtr ptrCpDag2 = pDag2->CreateObject();

        ShowGraph(*ptrCpDag1 = *pDag1);
        ShowGraph(*ptrCpDag2 = *pDag2);*/

        ShowSkeletonMatch(pDag1, pDag2, nodeMap);
}

void ShowSkeletonMatch(const DAG* pDag1, const DAG* pDag2, DAGNodeMap& nodeMap)
{
        const ShockGraph* pSG1 = dynamic_cast<const ShockGraph*>(pDag1);
        const ShockGraph* pSG2 = dynamic_cast<const ShockGraph*>(pDag2);

        if (pSG1 && pSG2)
        {
                SGMatchWnd wnd;
                wnd.SetMatchMap(nodeMap);
                wnd.Create(pSG1, pSG2);
        }
}

void ShowSkeleton(const DAG* pDag)
{
        const ShockGraph* pSG = dynamic_cast<const ShockGraph*>(pDag);

        if (pSG)
        {
                ShockGraph dummy;
                SGMatchWnd wnd;
                wnd.Create(pSG, &dummy);
        }
}

/*double SGNodeDistance(const SGNode& n1, const SGNode& n2)
{
        int i, j;
        double total = 0, subtotal, d;

        for (i = 0; i < n1.GetShockCount(); i++)
        {
                subtotal = 1000000;

                for (j = 0; j < n2.GetShockCount(); j++)
                {
                        d = abs(abs(n1.m_shocks[i].dr_ds) - abs(n2.m_shocks[j].dr_ds));

                        if (d < subtotal)
                                subtotal = d;
                }

                total += subtotal;
        }

        return total;
}*/

/* 
        @brief Computes a shock graph from the given ppm file.

        @param szFileName PPM file name
        @param outFile The SG will be written into this file
        @logFil Log info will be written in this file
        @info Parameters for the SG computation code
        @bAsyncProcessing Whether a TIME OUT must be used to control the SG computation

        Since the SG computation used to fail, the async processing was necessary to
        avoid a batch processing of files getting stuck in a particular file.
*/
void ProcessFile(const char* szFileName, DAGDatabase& dagDB, fstream& logFile,
                                 SGRECINFO& info, bool bAsyncProcessing)
{
        int status;

        logFile << endl << '\t' << szFileName << "... ";
        logFile.flush();

        if (bAsyncProcessing)
        {
                if ((g_pid = fork()) != 0)
                {       
                        signal(SIGALRM, OnAlarm);
                        g_nTimeout = info.timeout;
                        alarm(info.timeout);
                        waitpid(g_pid, &status, 0);

                        if (!(WIFEXITED(status)))
                                logFile << "ERROR: Seg. Fault";

                        // Parent process is done, function returns normaly
                        return; 
                }
        }
        
        // Child process executes the following code...
        DAGPtr pDag;
        bool bIsRead;
        const char* szFileExt;

        szFileExt = DirWalker::FindFileExtention(szFileName);

        if (!strcmp(szFileExt, "ppm") || !strcmp(szFileExt, "pgm"))
        {
                ShockGraph* pSG = new ShockGraph;
                pDag = pSG;

                // Do we use the new SG code or the old one?

                if (info.usenewcode)
                        bIsRead = pSG->ComputeFromPPMFile2(szFileName, info.sgparams);
                else {
                        // The SG code seems to require square images to work properly
                        //MakeSquare(szFileName);
                        //bIsRead = pSG->ComputeFromPPMFile(szFileName, info.cutoff, info.sigma, info.range);
                        bIsRead = false;
                        cerr << "\nSG old code is not available anymore!!!\n";
                }
        }
        else if (!strcmp(szFileExt, "gg"))
        {
                GestureGraph* pGG = new GestureGraph;
                pDag = pGG;

                bIsRead = pGG->Read(szFileName);
        }
        else
        {
                cerr << "\nUnknown file extension: " << szFileExt << endl;
                bIsRead = false;
        }

        if(bIsRead)
        {
                logFile << "DONE! (" << pDag->GetNodeCount() << " nodes)... " << flush;
                
                dagDB.AddDAG(pDag, true);

                logFile << "WRITTEN!" << flush;
        }
        else
                logFile << "ERROR: Can't read dag." << flush;


        // If bAsyncProcessing, the child process must finish
        if (bAsyncProcessing)
        {
                dagDB.Close();
                _exit(0); // Warning exit() with no '_' flushes the buffer and we don't want that.
        }
}

void OnAlarm(int param)
{
        kill(g_pid, SIGKILL);
        cerr << "\nTIMEOUT (" << g_nTimeout << " sec)" << endl;
        g_logFile << "TIMEOUT (" << g_nTimeout << " sec)";
}

void MakeSquare(const char* szPPMFileName)
{
        pixel** img;
        FILE* fp = fopen(szPPMFileName, "r+");
        int rows, cols, row, col, n, i;
        pixval maxval;
        int format;

        if (fp == NULL)
        {
                cerr << "\nERROR: Can't open " << szPPMFileName 
                        << ". Missing or read-only file.\n PPM might not be square." << endl;

                return;
        }

        ppm_readppminit(fp, &cols, &rows, &maxval, &format);

        // If img is already square, there is nothing to do
        if (cols == rows)
                return;

        n = (cols > rows) ? cols:rows;

        img = ppm_allocarray(n, n);

        // Set all the pixels in the new image to white
        for (i = 0; i < n; i++)
                memset(img[i], maxval, sizeof(pixel) * n);

        // Add the old image in the center of the new one
        if (cols > rows)
                for (i = 0, row = (cols - rows) / 2; i < rows; i++, row++)
                        ppm_readppmrow(fp, img[row], cols, maxval, format);
        else
                for (i = 0, col = (rows - cols) / 2; i < rows; i++)
                        ppm_readppmrow(fp, img[i] + col, cols, maxval, format);

        // Write down the new image
        fseek(fp, 0, SEEK_SET);
        ppm_writeppm(fp, img, n, n, maxval, 0/*forceplain?*/);

        fclose(fp);
}

bool AskBool(const char* szQuestion)
{
        char cAnswer;
        
        cout << szQuestion << "?[y/n]: ";
        cin >> cAnswer;

        return (cAnswer == 'y' || cAnswer == 'Y');
}

int AskInt(const char* szQuestion)
{
        int nAnswer;
        
        cout << szQuestion << "?: ";
        cin >> nAnswer;

        return nAnswer;
}

---