Main Page Namespace List Class Hierarchy Compound List File List Namespace Members Compound Members File Members Related Pages

# Matching.cpp

Go to the documentation of this file.

    00001
    00051 #include "Main.h"
    00052 #include "viewpoints.h"
    00053
    00054 //#define TIMEOUT (60 * 3)
    00055
    00056 pid_t   g_pid;
    00057 fstream g_logFile;
    00058 int g_nTimeout;
    00059
    00060 // Function definitions
    00061
    00069 double OccludeDAG(DAGPtr& ptrDag, double dMaxOcclusionRate)
    00070 {
    00071         leda_node v;
    00072         double dOcclusionRate = 0;
    00073         double nNodeMass, nTotalMass = ptrDag->GetNodeCount(); //must be double for division
    00074         int i = 0;
    00075
    00076         if (nTotalMass <= 3)
    00077                 return 0;
    00078
    00079         do {
    00080                 v = ptrDag->choose_node();
    00081                 ASSERT(v != nil);
    00082
    00083                 // ptrDag->GetNodeMass(v) is really cummulative mass now
    00084                 nNodeMass = ptrDag->GetTransClosMat().RowSum(ptrDag->GetNodeDFSIndex(v));
    00085                 dOcclusionRate = nNodeMass / nTotalMass;
    00086
    00087         } while (dOcclusionRate > dMaxOcclusionRate && i++ < nTotalMass * 2);
    00088
    00089         if (dOcclusionRate > dMaxOcclusionRate)
    00090                 return 0;
    00091
    00092         ptrDag->DeleteSubDAG(v);
    00093         ptrDag->ComputeDerivedValues();
    00094
    00095         return dOcclusionRate;
    00096 }
    00097
    00098 int AsyncIndexDAG(const DAG* pQueryDag, DAGDatabase& dagDB, MATCHINFO& info, STATINFO& idxSt)
    00099 {
    00100         int* pnCount = new int(0);
    00101
    00102         if ((g_pid = fork()) != 0)
    00103         {
    00104                 int status;
    00105                 waitpid(g_pid, &status, 0);
    00106
    00107                 if (!(WIFEXITED(status)))
    00108                 {
    00109                         cerr << "\nSegmentation fault when indexing " << pQueryDag->GetDAGLbl() << endl;
    00110                         *pnCount = 0;
    00111                 }
    00112
    00113                 int count = *pnCount;
    00114                 delete pnCount;
    00115                 DBG_MSG1("At parent", count)
    00116                 // Parent process is done, function returns normaly
    00117                 return count;
    00118         }
    00119
    00120         // Child process starts here
    00121         *pnCount = dagDB.GetSimilar(*pQueryDag, idxSt.matchList, info.idxrange,
    00122                 info.modelSimWeight, info.idxtau);
    00123         DBG_MSG1("At child", *pnCount)
    00124         _exit(0);
    00125 }
    00126
    00127 double AsyncMatchDAG(const DAG* pQueryDag, const DAG* pModelDag, DAGNodeMap& nodeMap)
    00128 {
    00129         double* pdSim = new double(0);
    00130
    00131         if ((g_pid = fork()) != 0)
    00132         {
    00133                 int status;
    00134                 waitpid(g_pid, &status, 0);
    00135
    00136                 if (!(WIFEXITED(status)))
    00137                 {
    00138                         cerr << "\nSegmentation fault when matching " << pQueryDag->GetDAGLbl()
    00139                                 << " against " << pModelDag->GetDAGLbl() << endl;
    00140
    00141                         *pdSim = 0;
    00142                 }
    00143
    00144                 double sim = *pdSim;
    00145                 delete pdSim;
    00146
    00147                 // Parent process is done, function returns normaly
    00148                 return sim;
    00149         }
    00150
    00151         // Child process starts here
    00152         *pdSim = pQueryDag->Similarity(*pModelDag, nodeMap);
    00153         _exit(0);
    00154 }
    00155
    00157
    00158 time_t MatchDAG(const DAG* pTargetDag, DAGDatabase& dagDB, MATCHINFO& info,
    00159                           STATINFO& idxSt, STATINFO& matSt)
    00160 {
    00161         double dSim;
    00162         DAGNodeMap nodeMap;
    00163         DAGPtr ptrDag;
    00164         int i;
    00165         time_t startTime, endTime;
    00166
    00167         startTime = time(NULL);
    00168
    00169         // Index with target DAG
    00170         int count;
    00171
    00172         /*if (info.asyncCompu)
    00173                 count = AsyncIndexDAG(pTargetDag, dagDB, info, idxSt);
    00174         else*/
    00175                 count = dagDB.GetSimilar(*pTargetDag, idxSt.matchList, info.idxrange,
    00176                         info.modelSimWeight, info.idxtau);
    00177
    00178         matSt.matchList.resize(count);
    00179
    00180         // Match DAGs returned by the index
    00181         for (i = 0; i < count; i++)
    00182         {
    00183                 dSim = idxSt.matchList[i].dSimilarity;
    00184
    00185                 if (dSim < info.idxtau)
    00186                         break;
    00187
    00188                 // Only retrive the K best allowing multiplicity of the last k one.
    00189
    00190                 if (i > info.idxKBest && dSim < idxSt.matchList[info.idxKBest].dSimilarity)
    00191                         break;
    00192
    00193                 ptrDag = dagDB.ReadDAG(idxSt.matchList[i].nDAGId, true);
    00194
    00195                 if (ptrDag.IsNull())
    00196                 {
    00197                         cerr << "Can't read DAG" << idxSt.matchList[i].nDAGId << endl;
    00198                         break;
    00199                 }
    00200
    00201                 /*if (info.asyncCompu)
    00202                         dSim = AsyncMatchDAG(pTargetDag, ptrDag, nodeMap);
    00203                 else*/
    00204                         dSim = pTargetDag->Similarity(ptrDag, nodeMap);
    00205
    00206                 if (dSim >= info.matchtau)
    00207                         matSt.matchList[i].Set(ptrDag, dSim);
    00208
    00209                 idxSt.matchList[i].ptrDAG = ptrDag;
    00210         }
    00211
    00212         // Sort best matches
    00213         matSt.matchList.sort();
    00214
    00215         endTime = time(NULL);
    00216
    00217         if (info.computeStats)
    00218         {
    00219                 idxSt.ComputeStats(pTargetDag);
    00220                 matSt.ComputeStats(pTargetDag);
    00221                 idxSt.ComputeCrossRankingIdxStats(matSt);
    00222         }
    00223
    00224         return endTime - startTime;
    00225 }
    00226
    00228
    00229 void MatchDAG(const DAG* pImgDag, DAGDatabase& dagDB, MATCHINFO& info,
    00230                           streamoff nModelDagOffset, STATINFO& matSt)
    00231 {
    00232         double dSim;
    00233         DAGNodeMap nodeMap;
    00234         DAGPtr ptrDag;
    00235
    00236         matSt.matchList.resize(1);
    00237
    00238         // Match model DAG
    00239         ptrDag = dagDB.ReadDAG(nModelDagOffset, pImgDag->ClassName());
    00240
    00241         if (ptrDag.IsNull())
    00242         {
    00243                 cerr << "Can't read DAG with offset " << nModelDagOffset << endl << flush;
    00244                 return;
    00245         }
    00246
    00247         dSim = pImgDag->Similarity(*ptrDag, nodeMap);
    00248
    00249         matSt.matchList[0].Set(ptrDag, dSim);
    00250 }
    00251
    00252 void SaveResults(const DAG* pTarget, DAGDatabase& dagDB,
    00253                                  STATINFO& idxSt, STATINFO& matSt, ostream& os)
    00254 {
    00255         const int RANK = 8;
    00256         const int DAGID = 15;
    00257         const int OBJNAME = 25;
    00258         const int VIEWNUM = 10;
    00259         const int SIMIL = 10;
    00260         int i;
    00261
    00262         os.flags(ios::left);
    00263
    00264         os << "\nChoosen graph: " << pTarget->GetDAGLbl();
    00265         os << "\nDAG ID: " << pTarget->GetDAGId() << endl;
    00266
    00267         os << "\nINDEXING RESULTS\n\n";
    00268         os << setw(RANK) << "Rank" << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "Object Name"
    00269                 << setw(VIEWNUM) << "View #" << setw(SIMIL) << "Similarity" << endl;
    00270
    00271         for(i = 0; i < idxSt.matchList.size() && i < matSt.matchList.size(); i++)
    00272         {
    00273                 const MatchInfo& info = idxSt.matchList[i];
    00274
    00275                 if (info.dSimilarity == 0.0)
    00276                         break;
    00277
    00278                 const DAGPtr ptrDAG = (info.ptrDAG.IsNull()) ? dagDB.ReadDAG(info.nDAGId, true):info.ptrDAG;
    00279
    00280                 os << endl;
    00281                 os << setw(RANK)    << i;
    00282                 os << setw(DAGID)   << ptrDAG->GetDAGId();
    00283                 os << setw(OBJNAME) << ptrDAG->GetObjName();
    00284                 os << setw(VIEWNUM) << ptrDAG->GetViewNumber();
    00285                 os << setw(SIMIL)   << info.dSimilarity;
    00286         }
    00287
    00288         os << "\n\nMATCHING RESULTS\n\n";
    00289         os << setw(RANK) << "Rank" << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "Object Name"
    00290                 << setw(VIEWNUM) << "View #" << setw(SIMIL) << "Similarity" << endl;
    00291
    00292         for(i = 0; i < matSt.matchList.size(); i++)
    00293         {
    00294                 const MatchInfo& info = matSt.matchList[i];
    00295
    00296                 if (info.dSimilarity == 0.0)
    00297                         break;
    00298
    00299                 os << endl;
    00300                 os << setw(RANK)    << i;
    00301                 os << setw(DAGID)   << info.ptrDAG->GetDAGId();
    00302                 os << setw(OBJNAME) << info.ptrDAG->GetObjName();
    00303                 os << setw(VIEWNUM) << info.ptrDAG->GetViewNumber();
    00304                 os << setw(SIMIL)   << info.dSimilarity;
    00305         }
    00306
    00307         if (matSt.bCompViewStats)
    00308         {
    00309                 int v1 = 0, v2 = 0, v3 = 0;
    00310                 GetClosestViews(pTarget->GetViewNumber(), 3, v1, v2, v3);
    00311
    00312                 SmartArray<int> secLevClosViews(0, 9);
    00313                 GetClosestViews2(pTarget->GetViewNumber(), 3, secLevClosViews, false);
    00314
    00315                 os << endl;
    00316                 os << "\n\nStatistics:\n";
    00317                 os << "\n\nClosest views: " << v1 << ' ' << v2 << ' ' << v3;
    00318                 os << "\n\nClosest 2nd level views: ";
    00319                 secLevClosViews.Print(os);
    00320                 os << endl;
    00321         }
    00322 }
    00323
    00324 bool ShowResults(const DAG* pTarget, STATINFO& matSt,
    00325         DAGDatabase& queryDB, DAGDatabase& modelDB, int nTgtID /*=-1*/)
    00326 {
    00327         int i;
    00328
    00329         cout << endl << "Query DAG: " << pTarget->GetDAGLbl() << endl;
    00330
    00331         for (i = 0; i < matSt.matchList.size() && AskBool("\nShow next matching result"); i++)
    00332                 if (matSt.matchList[i].dSimilarity > 0.0)
    00333                 {
    00334                         if (nTgtID == -1)
    00335                                 ShowMatch(pTarget, matSt.matchList[i].ptrDAG);
    00336                         else
    00337                                 ShowMatch(queryDB, nTgtID, modelDB, matSt.matchList[i].nDAGId);
    00338                 }
    00339
    00340         // If answered NO...
    00341         if (i < matSt.matchList.size())
    00342                 return AskBool("\nKeep showing matches for other queries");
    00343 }
    00344
    00345 void AddSubsamplingInfo(ViewSubsampler& vs, const DAG* pTarget, STATINFO& matSt, int kBest)
    00346 {
    00347         SmartArray<int> closestViews(0, 9);
    00348
    00349         GetClosestViews2(pTarget->GetViewNumber(), 3, closestViews, true);
    00350         vs.AddViewWeights(128, pTarget, matSt.matchList, closestViews, kBest);
    00351 }
    00352
    00353 void SaveSubsamplingInfo(ViewSubsampler& vs, String strDBFileName)
    00354 {
    00355         char szFileName[MAX_PATH];
    00356
    00357         DirWalker::ChangeFileExt(strDBFileName, NULL, szFileName);
    00358         strcat(szFileName, "_subsampling.inf");
    00359
    00360         vs.SaveViewWeights(szFileName);
    00361 }
    00362
    00363 void ShowMatch(DAGDatabase& dagDB1, int nDag1Id, DAGDatabase& dagDB2, int nDag2Id)
    00364 {
    00365         ShowMatch(dagDB1.ReadDAG(nDag1Id), dagDB2.ReadDAG(nDag2Id));
    00366 }
    00367
    00368 void ShowMatch(const DAG* pDag1, const DAG* pDag2)
    00369 {
    00370         DAGNodeMap nodeMap;
    00371
    00372         pDag1->Similarity(*pDag2, nodeMap);
    00373
    00374         /*DAGPtr ptrCpDag1 = pDag1->CreateObject();
    00375         DAGPtr ptrCpDag2 = pDag2->CreateObject();
    00376
    00377         ShowGraph(*ptrCpDag1 = *pDag1);
    00378         ShowGraph(*ptrCpDag2 = *pDag2);*/
    00379
    00380         ShowSkeletonMatch(pDag1, pDag2, nodeMap);
    00381 }
    00382
    00383 void ShowSkeletonMatch(const DAG* pDag1, const DAG* pDag2, DAGNodeMap& nodeMap)
    00384 {
    00385         const ShockGraph* pSG1 = dynamic_cast<const ShockGraph*>(pDag1);
    00386         const ShockGraph* pSG2 = dynamic_cast<const ShockGraph*>(pDag2);
    00387
    00388         if (pSG1 && pSG2)
    00389         {
    00390                 SGMatchWnd wnd;
    00391                 wnd.SetMatchMap(nodeMap);
    00392                 wnd.Create(pSG1, pSG2);
    00393         }
    00394 }
    00395
    00396 void ShowSkeleton(const DAG* pDag)
    00397 {
    00398         const ShockGraph* pSG = dynamic_cast<const ShockGraph*>(pDag);
    00399
    00400         if (pSG)
    00401         {
    00402                 ShockGraph dummy;
    00403                 SGMatchWnd wnd;
    00404                 wnd.Create(pSG, &dummy);
    00405         }
    00406 }
    00407
    00408 /*double SGNodeDistance(const SGNode& n1, const SGNode& n2)
    00409 {
    00410         int i, j;
    00411         double total = 0, subtotal, d;
    00412
    00413         for (i = 0; i < n1.GetShockCount(); i++)
    00414         {
    00415                 subtotal = 1000000;
    00416
    00417                 for (j = 0; j < n2.GetShockCount(); j++)
    00418                 {
    00419                         d = abs(abs(n1.m_shocks[i].dr_ds) - abs(n2.m_shocks[j].dr_ds));
    00420
    00421                         if (d < subtotal)
    00422                                 subtotal = d;
    00423                 }
    00424
    00425                 total += subtotal;
    00426         }
    00427
    00428         return total;
    00429 }*/
    00430
    00431 /*
    00432         @brief Computes a shock graph from the given ppm file.
    00433
    00434         @param szFileName PPM file name
    00435         @param outFile The SG will be written into this file
    00436         @logFil Log info will be written in this file
    00437         @info Parameters for the SG computation code
    00438         @bAsyncProcessing Whether a TIME OUT must be used to control the SG computation
    00439
    00440         Since the SG computation used to fail, the async processing was necessary to
    00441         avoid a batch processing of files getting stuck in a particular file.
    00442 */
    00443 void ProcessFile(const char* szFileName, DAGDatabase& dagDB, fstream& logFile,
    00444                                  SGRECINFO& info, bool bAsyncProcessing)
    00445 {
    00446         int status;
    00447
    00448         logFile << endl << '\t' << szFileName << "... ";
    00449         logFile.flush();
    00450
    00451         if (bAsyncProcessing)
    00452         {
    00453                 if ((g_pid = fork()) != 0)
    00454                 {
    00455                         signal(SIGALRM, OnAlarm);
    00456                         g_nTimeout = info.timeout;
    00457                         alarm(info.timeout);
    00458                         waitpid(g_pid, &status, 0);
    00459
    00460                         if (!(WIFEXITED(status)))
    00461                                 logFile << "ERROR: Seg. Fault";
    00462
    00463                         // Parent process is done, function returns normaly
    00464                         return;
    00465                 }
    00466         }
    00467
    00468         // Child process executes the following code...
    00469         DAGPtr pDag;
    00470         bool bIsRead;
    00471         const char* szFileExt;
    00472
    00473         szFileExt = DirWalker::FindFileExtention(szFileName);
    00474
    00475         if (!strcmp(szFileExt, "ppm") || !strcmp(szFileExt, "pgm"))
    00476         {
    00477                 ShockGraph* pSG = new ShockGraph;
    00478                 pDag = pSG;
    00479
    00480                 // Do we use the new SG code or the old one?
    00481
    00482                 if (info.usenewcode)
    00483                         bIsRead = pSG->ComputeFromPPMFile2(szFileName, info.sgparams);
    00484                 else {
    00485                         // The SG code seems to require square images to work properly
    00486                         //MakeSquare(szFileName);
    00487                         //bIsRead = pSG->ComputeFromPPMFile(szFileName, info.cutoff, info.sigma, info.range);
    00488                         bIsRead = false;
    00489                         cerr << "\nSG old code is not available anymore!!!\n";
    00490                 }
    00491         }
    00492         else if (!strcmp(szFileExt, "gg"))
    00493         {
    00494                 GestureGraph* pGG = new GestureGraph;
    00495                 pDag = pGG;
    00496
    00497                 bIsRead = pGG->Read(szFileName);
    00498         }
    00499         else
    00500         {
    00501                 cerr << "\nUnknown file extension: " << szFileExt << endl;
    00502                 bIsRead = false;
    00503         }
    00504
    00505         if(bIsRead)
    00506         {
    00507                 logFile << "DONE! (" << pDag->GetNodeCount() << " nodes)... " << flush;
    00508
    00509                 dagDB.AddDAG(pDag, true);
    00510
    00511                 logFile << "WRITTEN!" << flush;
    00512         }
    00513         else
    00514                 logFile << "ERROR: Can't read dag." << flush;
    00515
    00516
    00517         // If bAsyncProcessing, the child process must finish
    00518         if (bAsyncProcessing)
    00519         {
    00520                 dagDB.Close();
    00521                 _exit(0); // Warning exit() with no '_' flushes the buffer and we don't want that.
    00522         }
    00523 }
    00524
    00525 void OnAlarm(int param)
    00526 {
    00527         kill(g_pid, SIGKILL);
    00528         cerr << "\nTIMEOUT (" << g_nTimeout << " sec)" << endl;
    00529         g_logFile << "TIMEOUT (" << g_nTimeout << " sec)";
    00530 }
    00531
    00537 void MakeSquare(const char* szPPMFileName)
    00538 {
    00539         pixel** img;
    00540         FILE* fp = fopen(szPPMFileName, "r+");
    00541         int rows, cols, row, col, n, i;
    00542         pixval maxval;
    00543         int format;
    00544
    00545         if (fp == NULL)
    00546         {
    00547                 cerr << "\nERROR: Can't open " << szPPMFileName
    00548                         << ". Missing or read-only file.\n PPM might not be square." << endl;
    00549
    00550                 return;
    00551         }
    00552
    00553         ppm_readppminit(fp, &cols, &rows, &maxval, &format);
    00554
    00555         // If img is already square, there is nothing to do
    00556         if (cols == rows)
    00557                 return;
    00558
    00559         n = (cols > rows) ? cols:rows;
    00560
    00561         img = ppm_allocarray(n, n);
    00562
    00563         // Set all the pixels in the new image to white
    00564         for (i = 0; i < n; i++)
    00565                 memset(img[i], maxval, sizeof(pixel) * n);
    00566
    00567         // Add the old image in the center of the new one
    00568         if (cols > rows)
    00569                 for (i = 0, row = (cols - rows) / 2; i < rows; i++, row++)
    00570                         ppm_readppmrow(fp, img[row], cols, maxval, format);
    00571         else
    00572                 for (i = 0, col = (rows - cols) / 2; i < rows; i++)
    00573                         ppm_readppmrow(fp, img[i] + col, cols, maxval, format);
    00574
    00575         // Write down the new image
    00576         fseek(fp, 0, SEEK_SET);
    00577         ppm_writeppm(fp, img, n, n, maxval, 0/*forceplain?*/);
    00578
    00579         fclose(fp);
    00580 }
    00581
    00582 bool AskBool(const char* szQuestion)
    00583 {
    00584         char cAnswer;
    00585
    00586         cout << szQuestion << "?[y/n]: ";
    00587         cin >> cAnswer;
    00588
    00589         return (cAnswer == 'y' || cAnswer == 'Y');
    00590 }
    00591
    00592 int AskInt(const char* szQuestion)
    00593 {
    00594         int nAnswer;
    00595
    00596         cout << szQuestion << "?: ";
    00597         cin >> nAnswer;
    00598
    00599         return nAnswer;
    00600 }
    00601
    00602
    00603
    00604