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

# DAGDatabase.cpp

Go to the documentation of this file.

    00001
    00042 #include <stdio.h>
    00043 #include <time.h>
    00044 #include "DAG.h"
    00045 #include "SmartArray.h"
    00046 #include "Exceptions.h"
    00047 #include "Debug.h"
    00048 #include "DirWalker.h"
    00049 #include <LEDA/h_array.h>
    00050 #include "DAGDatabase.h"
    00051 #include "VoteCounter.h"
    00052
    00053 struct DBGINFO
    00054 {
    00055         fstream         os;
    00056
    00057         const DAG*      pDag;
    00058         double          KorRange;
    00059         double          modelSimWeight;
    00060
    00061         leda_node       imgNode;
    00062         double          imgNodeNorm;
    00063         double          imgNodeTotalNorm;
    00064
    00065         int                     modelID;
    00066         int                     modelNode;
    00067         double          modelNodeNorm;
    00068         double          modelNodeTotalNorm;
    00069
    00070         double          diffNorm;
    00071         double          vote;
    00072         double          maxVote;
    00073         double          currVote;
    00074
    00075         void SetCommonData(const DAG* p, double k, double w) {
    00076                 pDag = p; KorRange = k; modelSimWeight = w;
    00077         }
    00078
    00079         void SetImgNodeInfo(leda_node v, double n, double t) {
    00080                 imgNode = v; imgNodeNorm = n; imgNodeTotalNorm = t;
    00081         }
    00082
    00083         void SetModelNodeInfo(int id, int v, double n, double t) {
    00084                 modelID = id; modelNode = v; modelNodeNorm = n; modelNodeTotalNorm = t;
    00085         }
    00086
    00087         void SetVoteInfo(double d, double v, double cv) {
    00088                 diffNorm = d; vote = v; currVote = cv;
    00089                 maxVote = (1 - modelSimWeight) * imgNodeNorm / imgNodeTotalNorm +
    00090                         modelSimWeight * modelNodeNorm / modelNodeTotalNorm;
    00091         }
    00092
    00093         void Print();
    00094 } dbg;
    00095
    00096 void DBGINFO::Print()
    00097 {
    00098         static bool bFirstTime = true;
    00099
    00100         if (bFirstTime)
    00101         {
    00102                 bFirstTime = false;
    00103
    00104                 os.open("voting.log", ios::trunc | ios::out);
    00105
    00106                 os << pDag->GetDAGLbl() << endl
    00107                         << "k or range = " << KorRange << endl
    00108                         << "weight of model similarity = " << modelSimWeight << endl;
    00109         }
    00110
    00111         os  << "\nModel ID: " << modelID
    00112                 << "\nImg node: " <<  pDag->GetNodeLbl(imgNode) << ", norm: " << imgNodeNorm << ", total norm: " << imgNodeTotalNorm
    00113                 << "\nMod node: " <<  modelNode << ", norm: " << modelNodeNorm << ", total norm: " << modelNodeTotalNorm
    00114                 << "\nDiff norm: " << diffNorm
    00115                 << "\nVote: " << vote << ", max vote: " << maxVote << ", curr max vote: " << currVote
    00116                 << endl << flush;
    00117 }
    00118
    00120 int compare(const MatchInfo& a, const MatchInfo& b)
    00121 {
    00122         if (a.dSimilarity > b.dSimilarity)
    00123                 return -1;
    00124         else if(a.dSimilarity < b.dSimilarity)
    00125                 return 1;
    00126         else if (a.nDAGOffset < b.nDAGOffset)
    00127                 return -1;
    00128         else if (a.nDAGOffset > b.nDAGOffset)
    00129                 return 1;
    00130         else
    00131                 return 0;
    00132 }
    00133
    00134 void VoteList::AddVote(Vote& newVote)
    00135 {
    00136         //leda_list_item it;
    00137
    00138         if (dagId == -1)
    00139                 dagId = newVote.dagId;
    00140
    00141         ASSERT(dagId == newVote.dagId);
    00142
    00143         if (newVote.vote < 0.001)
    00144                 return;
    00145
    00146         int imgNode = index(newVote.imgNode);
    00147         leda_seq_item itu = modelNodes.lookup(newVote.modelNode);
    00148         leda_seq_item itv = imgNodes.lookup(imgNode);
    00149
    00150         leda_node u, v;
    00151
    00152         if (itu == nil) {
    00153                 u = bipGraph.new_node(newVote.modelNode);
    00154                 modelNodes.insert(newVote.modelNode, u);
    00155                 modelNodeSet.push(u);
    00156         }
    00157         else
    00158                 u = modelNodes[itu];
    00159
    00160         if (itv == nil) {
    00161                 v = bipGraph.new_node(imgNode);
    00162                 imgNodes.insert(imgNode, v);
    00163                 imgNodeSet.push(v);
    00164         }
    00165         else
    00166                 v = imgNodes[itv];
    00167
    00168         /* The array access operator A[e] checks its precondition (A must be valid for e).
    00169                 The check can be turned off by compiling with the flag -DLEDA_CHECKING_OFF. */
    00170
    00171         votes[bipGraph.new_edge(u, v, 1.0)] = newVote.vote;
    00172
    00173         totalVote += newVote.vote;
    00174 }
    00175
    00176 double VoteList::GetTotalVote(const DAG& dag, const double& minTotalVote)
    00177 {
    00178         if (totalVote < minTotalVote)
    00179                 return 0;
    00180
    00181         leda_list_item it;
    00182         double total = 0;
    00183
    00184         //ASSERT(Is_Bipartite(bipGraph, modelNodeSet, imgNodeSet));
    00185
    00186         MWA_SCALE_WEIGHTS(bipGraph, votes);
    00187
    00188         //leda_list<leda_edge> bestVotes = MWMCB_MATCHING(bipGraph, modelNodeSet, imgNodeSet, votes);
    00189         leda_list<leda_edge> bestVotes = MAX_WEIGHT_BIPARTITE_MATCHING(bipGraph, votes);
    00190
    00191         forall_items(it, bestVotes)
    00192                 total += votes[bestVotes[it]];
    00193
    00194         return (total >= minTotalVote) ? total:0.0;
    00195 }
    00196
    00197 bool DAGDatabase::Open(const char* szName, ios_base::openmode nMode)
    00198 {
    00199         m_bIndexOpened = false;
    00200         m_dagFile.clear();
    00201         m_dagFile.open(szName, nMode);
    00202
    00203         return !m_dagFile.fail();
    00204 }
    00205
    00206 bool DAGDatabase::OpenIndex()
    00207 {
    00208         char szIdxFileName[MAX_PATH];
    00209
    00210         DirWalker::ChangeFileExt(GetFileName(), "idx", szIdxFileName);
    00211
    00212         m_bIndexOpened = m_index.Open(szIdxFileName);
    00213
    00214         if (m_bIndexOpened)
    00215         {
    00216                 int dif = DirWalker::CompareLastModifDate(GetFileName(), szIdxFileName);
    00217
    00218                 if (dif > 0)
    00219                 {
    00220                         m_index.Close();
    00221                         remove(szIdxFileName);
    00222                         m_bIndexOpened = false;
    00223                 }
    00224         }
    00225
    00226         if (!m_bIndexOpened)
    00227         {
    00228                 DAGPtr ptrDag;
    00229                 int i, nMaxDim = 0;
    00230                 int nDAGCount = GetDAGCount();
    00231
    00232                 nMaxDim = m_dagFile.GetMaxTSVDimension();
    00233                 m_bIndexOpened = m_index.Create(szIdxFileName, nMaxDim);
    00234
    00235                 // Create index
    00236                 if (m_bIndexOpened && nMaxDim > 0)
    00237                 {
    00238                         cout << "Creating index of " << nMaxDim << " dimensions... " << flush;
    00239
    00240                         try {
    00241                                 for (i = 0; i < nDAGCount; i++)
    00242                                 {
    00243                                         ptrDag = m_dagFile.ReadDAG(i, true);
    00244                                         m_index.Add(ptrDag->GetDAGId(), ptrDag);
    00245                                 }
    00246                         } catch(ExceptionInfo e) {
    00247                                 e.Print();
    00248                                 return false;
    00249                         }
    00250
    00251                         cout << "The DB index has beed created!" << endl;
    00252                 }
    00253                 else
    00254                         cerr << "\nERROR: Cannot create index (max dim: " << nMaxDim << ")\n";
    00255         }
    00256
    00257         return m_bIndexOpened;
    00258 }
    00259
    00260 /*bool DAGDatabase::ReadObjClass(DAG* pDAGReader, const char* szObjName)
    00261 {
    00262         String strLbl;
    00263
    00264         MoveToBeg();
    00265
    00266         while (Next(pDAGReader))
    00267         {
    00268                 if (pDAGReader->GetObjName() == szObjName)
    00269                 {
    00270                         DAGPtr ptr = pDAGReader->CreateObject();
    00271                         *ptr = *pDAGReader;
    00272                         m_dagList.Append(ptr);
    00273                 }
    00274                 else if (m_dagList.GetSize() > 0)
    00275                         break;
    00276         }
    00277
    00278         return true;
    00279 }*/
    00280
    00281 /*bool DAGDatabase::ReadAll(DAG* pDAGReader, int nMaxCount)
    00282 {
    00283         MoveToBeg();
    00284
    00285         while (nMaxCount-- && Next(pDAGReader))
    00286         {
    00287                 DAGPtr ptr = pDAGReader->CreateObject();
    00288                 *ptr = *pDAGReader;
    00289                 m_dagList.Append(ptr);
    00290         }
    00291
    00292         return true;
    00293 }*/
    00294
    00295
    00296 int DAGDatabase::GetSimilar(const DAG& dag, leda_array<MatchInfo>& matched,
    00297                                                         double range, const double& w, const double& minSimilarity)
    00298 {
    00299         ASSERT(m_bIndexOpened);
    00300         ASSERT(w >= 0 && w <= 1);
    00301         ASSERT(minSimilarity >= 0);
    00302
    00303         if (DAG::IsDbgMode())
    00304                 dbg.SetCommonData(&dag, range, w);
    00305
    00306         // Range is used to choose the method to compute the votes
    00307         // If it is negative, we use the old method. In turn, if abs(range)
    00308         // is greater that 1, we use a K NN-search instead of a range search.
    00309         if (range < 0)
    00310         {
    00311                 range = -range; // we use the absolute value
    00312
    00313         TSV nodeTSV;
    00314         double nodeTSVL2, targetNodeSim, modelNodeSim, dagTotalVote, diffNorm;
    00315         leda_node v;
    00316         int id, offset, i, size, nodeLbl, lbl;
    00317         SmartArray<DAGSearchRecordEx> kClosest;
    00318         leda_h_array<int, VoteList> viewBins(0, 1024);
    00319         Vote nodeVote(&dag);
    00320
    00321         // Compute max total vote for the given dag
    00322         dagTotalVote = dag.GetTotalTSVSum();
    00323
    00324         forall_nodes(v, dag)
    00325         {
    00326                 nodeTSVL2 = dag.GetNodeTSVNorm(v);
    00327
    00328                 if (nodeTSVL2 == 0)
    00329                         continue;
    00330
    00331                 nodeTSV = dag.GetNodeTSV(v, m_index.GetDim());
    00332                 nodeLbl = dag.NodeType(v);
    00333
    00334                 // Get the closest neighbours of the node
    00335                 if (range >= 1)
    00336                         kClosest = m_index.GetKClosest(dag, v, (int)range);
    00337                 else
    00338                         kClosest = m_index.GetClosest(dag, v, range);
    00339
    00340                 size = kClosest.GetSize();
    00341
    00342                 //For each neighbour perform object model count
    00343                 for(i = 0; i < size; i++)
    00344                 {
    00345                         lbl = kClosest[i].nodeLbl;
    00346
    00347                         if (nodeLbl != lbl)
    00348                                 continue;
    00349
    00350                         id = kClosest[i].id;
    00351                         offset = kClosest[i].offset;
    00352
    00353                         // Must weight each vote...
    00354
    00355                         if (DAG::GetMatchParams().nUseNewVoteWeightFunc)
    00356                         {
    00357                                 // NEW VOTE WEIGHTING FUNCTION
    00358                                 targetNodeSim = (1 - w) * nodeTSVL2 / dagTotalVote;
    00359                                 modelNodeSim = w * kClosest[i].nodeTSV.Norm2() / kClosest[i].totalVote;
    00360                                 diffNorm = Norm2(nodeTSV - kClosest[i].nodeTSV);
    00361
    00362                                 nodeVote.vote = (targetNodeSim + modelNodeSim) / (1 + diffNorm);
    00363                         }
    00364                         else
    00365                         {
    00366                                 // OLD VOTE WEIGHTING FUNCTION
    00367                                 nodeVote.vote = nodeTSVL2 / (1 + Norm2(nodeTSV - kClosest[i].nodeTSV));
    00368                         }
    00369
    00370                         // Save the weighted vote
    00371
    00372                         if (nodeVote.vote > 0)
    00373                         {
    00374                                 nodeVote.dagId = id;
    00375                                 nodeVote.dagOffset = offset;
    00376                                 nodeVote.imgNode = v;
    00377                                 nodeVote.modelNode = kClosest[i].node;
    00378                                 viewBins[id].AddVote(nodeVote);
    00379                         }
    00380
    00381                         if (DAG::IsDbgMode())
    00382                         {
    00383                                 dbg.SetImgNodeInfo(v, nodeTSVL2, dagTotalVote);
    00384                                 dbg.SetModelNodeInfo(id, kClosest[i].node, kClosest[i].nodeTSV.Norm2(), kClosest[i].totalVote);
    00385                                 dbg.SetVoteInfo(diffNorm, nodeVote.vote, 0.0);
    00386
    00387                                 dbg.Print();
    00388                         }
    00389                 }
    00390         }
    00391
    00392         // Discard the prototypes that aren't similar enough
    00393         i = viewBins.size();
    00394         double sim;
    00395
    00396         matched.resize(i);
    00397
    00398         if (i > 0)
    00399         {
    00400                 // Return prototypes ordered by number of votes
    00401                 i = 0;
    00402
    00403                 forall_defined(id, viewBins)
    00404                 {
    00405                         VoteList& vl = viewBins[id];
    00406                         // Use one-to-one mapping or the old bad idea of summing all the votes?
    00407                         sim = (DAG::GetMatchParams().nUseMOOVC) ? vl.GetTotalVote(dag, minSimilarity):vl.SumAllVotes();
    00408                         offset = vl.GetDAGFileOffset();
    00409                         matched[i++].Set(id, offset, sim);
    00410                 }
    00411
    00412                 matched.sort();
    00413         }
    00414     }
    00415     else
    00416     {
    00417                 QueryRange rangeVector(range, dag.GetMaxTSVDimension());
    00418
    00419                 NNVoteArray votes = ComputeVotesForModelGraphs(&dag, *this, rangeVector, w, minSimilarity);
    00420                 matched.resize(votes.GetSize());
    00421
    00422                 // Copy the result to the matched array
    00423                 for (int i = 0; i < votes.GetSize(); i++)
    00424                         matched[i].Set(votes[i].nModelGraph, 0, votes[i].dWeight);
    00425         }
    00426
    00427         return matched.size();
    00428 }
    00429
    00430 const DAGPtr DAGDatabase::ChooseDAG() const
    00431 {
    00432         // Choose a random dag
    00433         srand( (unsigned)time( NULL ));
    00434         int nTarget = rand() % m_dagList.size();
    00435
    00436         const DAGPtr pTargetDag = m_dagList[m_dagList.get_item(nTarget)];
    00437
    00438         return pTargetDag;
    00439 }
    00440
    00441 void DAGDatabase::ShowDAGList(ostream& os)
    00442 {
    00443         const int DAGID = 15;
    00444         const int OBJNAME = 45;
    00445         leda_list_item it;
    00446
    00447         os.flags(ios::left);
    00448         os << endl << setw(DAGID) << "DAG ID" << setw(OBJNAME) << "DAG Label" << endl;
    00449
    00450         forall_items(it, m_dagList)
    00451         {
    00452                 os << endl;
    00453                 os << setw(DAGID)   << m_dagList[it]->GetDAGId();
    00454                 os << setw(OBJNAME) << m_dagList[it]->GetDAGLbl();
    00455         }
    00456
    00457         os << endl << flush;
    00458 }
    00459
    00460 void DAGDatabase::ListDAGs(ostream& os)
    00461 {
    00462         const int DAGID = 15;
    00463         const int OBJNAME = 25;
    00464         const int VIEWNUM = 10;
    00465         const int MAXTSVD = 10;
    00466         int nDAGCount = GetDAGCount();
    00467         DAGPtr ptrDag;
    00468
    00469         os.flags(ios::left);
    00470         os << endl << setw(DAGID) << "DAG ID" << setw(OBJNAME)
    00471                 << "Obj Name" << setw(VIEWNUM) << "View" << setw(MAXTSVD) << "Max TSV Dim" << endl;
    00472
    00473         for (int i = 0; i < nDAGCount; i++)
    00474         {
    00475                 ptrDag = m_dagFile.ReadDAG(i);
    00476
    00477                 os << endl;
    00478                 os << setw(DAGID)   << i;
    00479                 os << setw(OBJNAME) << ptrDag->GetObjName();
    00480                 os << setw(VIEWNUM) << ptrDag->GetViewNumber();
    00481                 os << setw(MAXTSVD) << ptrDag->GetMaxTSVDimension();
    00482         }
    00483
    00484         os << endl << "Total number of objects and views: " << nDAGCount << endl << flush;
    00485 }
    00486
    00487