KDTree.C

Go to the documentation of this file.
00001 /*!@file SIFT/KDTree.C k-d tree implementation */
00002 
00003 // //////////////////////////////////////////////////////////////////// //
00004 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2001 by the //
00005 // University of Southern California (USC) and the iLab at USC.         //
00006 // See http://iLab.usc.edu for information about this project.          //
00007 // //////////////////////////////////////////////////////////////////// //
00008 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
00009 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
00010 // in Visual Environments, and Applications'' by Christof Koch and      //
00011 // Laurent Itti, California Institute of Technology, 2001 (patent       //
00012 // pending; application number 09/912,225 filed July 23, 2001; see      //
00013 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
00014 // //////////////////////////////////////////////////////////////////// //
00015 // This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
00016 //                                                                      //
00017 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
00018 // redistribute it and/or modify it under the terms of the GNU General  //
00019 // Public License as published by the Free Software Foundation; either  //
00020 // version 2 of the License, or (at your option) any later version.     //
00021 //                                                                      //
00022 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
00023 // that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
00024 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
00025 // PURPOSE.  See the GNU General Public License for more details.       //
00026 //                                                                      //
00027 // You should have received a copy of the GNU General Public License    //
00028 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
00029 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
00030 // Boston, MA 02111-1307 USA.                                           //
00031 // //////////////////////////////////////////////////////////////////// //
00032 //
00033 // Primary maintainer for this file: James Bonaiuto <bonaiuto@usc.edu>
00034 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/SIFT/KDTree.C $
00035 // $Id: KDTree.C 6990 2006-08-11 18:13:51Z rjpeters $
00036 //
00037 
00038 #include "SIFT/KDTree.H"
00039 #include "Util/log.H"
00040 
00041 // #######################################################################
00042 KDTree::KDTree(const std::vector< rutz::shared_ptr<Keypoint> >& keys,
00043                const std::vector<uint>& objindices) :
00044   itsPivot(), itsSplitDim(0U), itsPivotIndex(0U), itsObjIndex(0U),
00045   itsLeftSubTree(), itsRightSubTree()
00046 {
00047   const uint numkeys = keys.size();
00048 
00049   // NOTE: a leaf tree contains a Pivot but no splitting dimension and
00050   // no left or right trees.
00051 
00052   // if we are given an empty set of keys, bail out:
00053   if (numkeys == 0)
00054     { LFATAL("Given list of keys is empty! -- ABORT"); return; }
00055 
00056   // if we are given object indices, make sure the number of correct:
00057   if (objindices.empty() == false) ASSERT(objindices.size() == keys.size());
00058 
00059   // if we have only one key, we are a leaf:
00060   if (numkeys == 1)
00061     {
00062       itsPivot = keys[0];
00063       if (objindices.empty() == false) itsObjIndex = objindices[0];
00064       return;
00065     }
00066 
00067   // ok, we have more than one keys. Find a splitting point and dimension:
00068   itsPivotIndex = goodCandidate(keys, itsSplitDim);
00069   itsPivot = keys[itsPivotIndex]; // keep a copy of the key for later matching
00070 
00071   // split the exemplar set into left/right elements relative to the
00072   // splitting dimension:
00073   byte bound = itsPivot->getFVelement(itsSplitDim);
00074   std::vector< rutz::shared_ptr<Keypoint> > leftElems, rightElems;
00075   std::vector<uint> leftInd, rightInd;
00076   std::vector<uint> leftObjInd, rightObjInd;
00077 
00078   for (uint i = 0; i < numkeys; i++)
00079     {
00080       if (i == itsPivotIndex) continue; // ignore the splitting element (pivot)
00081 
00082       rutz::shared_ptr<Keypoint> dom = keys[i];
00083 
00084       if (dom->getFVelement(itsSplitDim) <= bound)
00085         {
00086           leftElems.push_back(dom);
00087           leftInd.push_back(i);
00088           if (objindices.empty() == false)
00089             leftObjInd.push_back(objindices[i]);
00090         }
00091       else
00092         {
00093           rightElems.push_back(dom);
00094           rightInd.push_back(i);
00095           if (objindices.empty() == false)
00096             rightObjInd.push_back(objindices[i]);
00097         }
00098     }
00099 
00100   // recurse:
00101   if (leftElems.size())
00102     itsLeftSubTree.reset(new KDTree(leftElems, leftInd, leftObjInd));
00103   if (rightElems.size())
00104     itsRightSubTree.reset(new KDTree(rightElems, rightInd, rightObjInd));
00105 }
00106 
00107 // #######################################################################
00108 KDTree::KDTree(const std::vector< rutz::shared_ptr<Keypoint> >& keys,
00109                const std::vector<uint>& indices,
00110                const std::vector<uint>& objindices) :
00111   itsPivot(), itsSplitDim(0U), itsPivotIndex(0U), itsObjIndex(0U),
00112   itsLeftSubTree(), itsRightSubTree()
00113 {
00114   const uint numkeys = keys.size();
00115 
00116   // NOTE: a leaf tree contains a Pivot but no splitting dimension and
00117   // no left or right trees.
00118 
00119   // if we are given an empty set of keys, bail out:
00120   if (numkeys == 0)
00121     { LFATAL("Given list of keys is empty! -- ABORT"); return; }
00122 
00123   // if we are given object indices, make sure the number of correct:
00124   if (objindices.empty() == false) ASSERT(objindices.size() == keys.size());
00125 
00126   // if we have only one key, we are a leaf:
00127   if (numkeys == 1)
00128     {
00129       itsPivot = keys[0];
00130       itsPivotIndex = indices[0];
00131       if (objindices.empty() == false) itsObjIndex = objindices[0];
00132       return;
00133     }
00134 
00135   // ok, we have more than one keys. Find a splitting point and dimension:
00136   uint idx = goodCandidate(keys, itsSplitDim);
00137   itsPivotIndex = indices[idx]; // index in the original array of keys
00138   itsPivot = keys[idx];         // keep a copy of the key for later matching
00139 
00140   // split the exemplar set into left/right elements relative to the
00141   // splitting dimension:
00142   byte bound = itsPivot->getFVelement(itsSplitDim);
00143   std::vector< rutz::shared_ptr<Keypoint> > leftElems, rightElems;
00144   std::vector<uint> leftInd, rightInd;
00145   std::vector<uint> leftObjInd, rightObjInd;
00146 
00147   for (uint i = 0; i < numkeys; i++)
00148     {
00149       if (i == idx) continue; // ignore the splitting element (pivot)
00150 
00151       rutz::shared_ptr<Keypoint> dom = keys[i];
00152 
00153       if (dom->getFVelement(itsSplitDim) <= bound)
00154         {
00155           leftElems.push_back(dom);
00156           leftInd.push_back(indices[i]);
00157           if (objindices.empty() == false)
00158             leftObjInd.push_back(objindices[i]);
00159         }
00160       else
00161         {
00162           rightElems.push_back(dom);
00163           rightInd.push_back(indices[i]);
00164           if (objindices.empty() == false)
00165             rightObjInd.push_back(objindices[i]);
00166         }
00167     }
00168 
00169   // recurse:
00170   if (leftElems.size())
00171     itsLeftSubTree.reset(new KDTree(leftElems, leftInd, leftObjInd));
00172   if (rightElems.size())
00173     itsRightSubTree.reset(new KDTree(rightElems, rightInd, rightObjInd));
00174 }
00175 
00176 // ######################################################################
00177 KDTree::~KDTree()
00178 { }
00179 
00180 // #######################################################################
00181 uint KDTree::nearestNeighbor(const rutz::shared_ptr<Keypoint>& target,
00182                              int& distsq1, int& distsq2) const
00183 {
00184   HyperRectangle hr(target->getFVlength(), 0, 255);
00185   const int maxdsq = target->maxDistSquared();
00186   uint objidx = 0U; // used internally to enforce second-best in same obj
00187   return nearestNeighborI(target, hr, maxdsq, distsq1, distsq2,
00188                           maxdsq, objidx);
00189 }
00190 
00191 // ######################################################################
00192 uint KDTree::nearestNeighborBBF(const rutz::shared_ptr<Keypoint>& target,
00193                                 const int searchSteps, int& distsq1,
00194                                 int& distsq2) const
00195 {
00196   HyperRectangle hr(target->getFVlength(), 0, 255);
00197   const int maxdsq = target->maxDistSquared();
00198   std::priority_queue<BBFdata> bbfq;
00199   int ssteps = searchSteps;
00200   uint objidx = 0U; // used internally to enforce second-best in same obj
00201   return nearestNeighborBBFI(target, hr, ssteps, maxdsq,
00202                              distsq1, distsq2, maxdsq, bbfq, objidx);
00203 }
00204 
00205 // ######################################################################
00206 uint KDTree::nearestNeighborI(const rutz::shared_ptr<Keypoint>& target,
00207                               const HyperRectangle& hr, int maxDistSq,
00208                               int& distsq1, int& distsq2,
00209                               const int maxdsq, uint& objidx) const
00210 {
00211   // if we are a leaf, just return our pivot and its distance to the target:
00212   if (isLeaf())
00213     {
00214       distsq1 = itsPivot->distSquared(target);
00215       distsq2 = maxdsq;
00216       objidx = itsObjIndex;
00217       return itsPivotIndex;
00218     }
00219 
00220   // ok, we are not empty nor a leaf. So let's check out what's going
00221   // on in our left and right subtrees:
00222   const byte splitval = itsPivot->getFVelement(itsSplitDim);
00223   const uint numdims = target->getFVlength();
00224 
00225   // Assign the nearer and further HRs and associated subtrees (steps 5-7):
00226   HyperRectangle nearerHr(numdims), furtherHr(numdims);
00227   rutz::shared_ptr<KDTree> nearerKd, furtherKd;
00228 
00229   if (target->getFVelement(itsSplitDim) <= splitval)
00230     {
00231       nearerKd = itsLeftSubTree;
00232       furtherKd = itsRightSubTree;
00233       nearerHr = hr;
00234       furtherHr = nearerHr.splitAt(itsSplitDim, splitval);
00235     }
00236   else
00237     {
00238       nearerKd = itsRightSubTree;
00239       furtherKd = itsLeftSubTree;
00240       furtherHr = hr;
00241       nearerHr = furtherHr.splitAt(itsSplitDim, splitval);
00242     }
00243 
00244   // Recursively get the nearest neighbor which could lie in the
00245   // nearer half tree (step 8):
00246   int distSq1 = maxdsq, distSq2 = maxdsq; uint nearest = 0U, nobjidx = 0U;
00247   if (nearerKd.is_valid())
00248     nearest = nearerKd->nearestNeighborI(target, nearerHr, maxDistSq,
00249                                          distSq1, distSq2, maxdsq, nobjidx);
00250 
00251   // If the second best match we just found is nearer than maxDistSq,
00252   // then reduce maxDistSq (modified step 9). Note: in the original
00253   // algorithm (which does not consider second-best matches), this
00254   // test would be done on distSq1 instead. So here we have a
00255   // performance impact for wanting to know the exact distance to the
00256   // second best match:
00257 
00258   //  if (distSq2 < maxDistSq) maxDistSq = distSq2;
00259 
00260   // NOTE2: the overhead is really too high. By using distSq1 as in
00261   // the original algo we sacrifice some accuracy on our estimation of
00262   // the second best distance, but accelerate the overall search a lot:
00263   if (distSq1 < maxDistSq) maxDistSq = distSq1;
00264 
00265   // If the further HR is too far away, it will be hopeless and we
00266   // don't even need to look at it (step 10):
00267   if (furtherHr.isInReach(target, maxDistSq))
00268     {
00269       // ok the further HR may contain a better (or second better)
00270       // match. First let's check how close our pivot is to the
00271       // target (modified steps 10.1.1 to 10.1.3):
00272       int ptDistSq = itsPivot->distSquared(target);
00273 
00274       if (ptDistSq < distSq1)
00275         {
00276           // our pivot is closer than our nearest, so make the pivot
00277           // our new nearest:
00278           nearest = itsPivotIndex;
00279 
00280           // if our pivot is in the same object than our previous
00281           // nearest, then just slide the distances; otherwise, make
00282           // distsq2 maximal:
00283           if (nobjidx == itsObjIndex)
00284             { distSq2 = distSq1; distSq1 = ptDistSq; }
00285           else
00286             { distSq1 = ptDistSq; distSq2 = maxdsq; nobjidx = itsObjIndex; }
00287 
00288           // update the max distance for further search:
00289           maxDistSq = distSq1;
00290         }
00291       else if (ptDistSq < distSq2)
00292         {
00293           // our pivot is farther than the nearest but closer than the
00294           // second nearest, so just update the second nearest
00295           // distance and max distance, but only if our pivot is in
00296           // the same object as our nearest:
00297           if (nobjidx == itsObjIndex)
00298             { distSq2 = ptDistSq; maxDistSq = distSq2; }
00299         }
00300 
00301       // Recursively explore the further HR (modified step 10.2):
00302       int tempDistSq1 = maxdsq, tempDistSq2 = maxdsq;
00303       uint tempNearest = 0U, tempobjidx = 0U;
00304       if (furtherKd.is_valid())
00305         tempNearest =
00306           furtherKd->nearestNeighborI(target, furtherHr, maxDistSq,
00307                                       tempDistSq1, tempDistSq2, maxdsq,
00308                                       tempobjidx);
00309 
00310       // If we found a better nearest or second nearest, update
00311       // accordingly (modified step 10.3):
00312       if (tempDistSq1 < distSq1)
00313         {
00314           // tempNearest is better than nearest, so use tempNearest:
00315           nearest = tempNearest;
00316 
00317           // now, who is the second best?
00318           if (tempobjidx == nobjidx)
00319             {
00320               // temp is in the same object as nearest used to be. So
00321               // let's just slide the second-best distances:
00322               if (tempDistSq2 < distSq1) distSq2 = tempDistSq2;
00323               else distSq2 = distSq1;
00324             }
00325           else
00326             {
00327               // temp in different object from old nearest:
00328               distSq2 = maxdsq;
00329               nobjidx = tempobjidx;
00330             }
00331 
00332           // also update our best distance:
00333           distSq1 = tempDistSq1;
00334         }
00335       else if (tempDistSq1 < distSq2)
00336         {
00337           // tempNearest is worse than nearest but better than our
00338           // second nearest, so just update our second nearest
00339           // distance, but only if in same object:
00340           if (tempobjidx == nobjidx)
00341             distSq2 = tempDistSq1;
00342         }
00343     }
00344 
00345   // return the best we have found. Note: nearest may be empty if we
00346   // did not find anything:
00347   distsq1 = distSq1; distsq2 = distSq2; objidx = nobjidx;
00348   return nearest;
00349 }
00350 
00351 // ######################################################################
00352 uint KDTree::nearestNeighborBBFI(const rutz::shared_ptr<Keypoint>& target,
00353                                  const HyperRectangle& hr, int& searchSteps,
00354                                  int maxDistSq, int& distsq1, int& distsq2,
00355                                  const int maxdsq,
00356                                  std::priority_queue<BBFdata>& bbfq,
00357                                  uint& objidx) const
00358 {
00359   // if we are a leaf, just return our pivot and its distance to the target:
00360   if (isLeaf())
00361     {
00362       distsq1 = itsPivot->distSquared(target);
00363       distsq2 = maxdsq;
00364       objidx = itsObjIndex;
00365       return itsPivotIndex;
00366     }
00367 
00368   // ok, we are not empty nor a leaf. So let's check out what's going
00369   // on in our left and right subtrees:
00370   const byte splitval = itsPivot->getFVelement(itsSplitDim);
00371   const uint numdims = target->getFVlength();
00372 
00373   // Assign the nearer and further HRs and associated subtrees (steps 5-7):
00374   HyperRectangle nearerHr(numdims), furtherHr(numdims);
00375   rutz::shared_ptr<KDTree> nearerKd, furtherKd;
00376 
00377   if (target->getFVelement(itsSplitDim) <= splitval)
00378     {
00379       nearerKd = itsLeftSubTree;
00380       furtherKd = itsRightSubTree;
00381       nearerHr = hr;
00382       furtherHr = nearerHr.splitAt(itsSplitDim, splitval);
00383     }
00384   else
00385     {
00386       nearerKd = itsRightSubTree;
00387       furtherKd = itsLeftSubTree;
00388       furtherHr = hr;
00389       nearerHr = furtherHr.splitAt(itsSplitDim, splitval);
00390     }
00391 
00392   // store the further guys into our priority queue:
00393   BBFdata fu(furtherHr, furtherKd, itsPivotIndex, itsObjIndex, itsPivot,
00394              furtherHr.distSq(target));
00395   bbfq.push(fu);
00396 
00397   // Recursively get the nearest neighbor which could lie in the
00398   // nearer half tree (step 8):
00399   int distSq1 = maxdsq, distSq2 = maxdsq; uint nearest = 0U, nobjidx = 0U;
00400   if (nearerKd.is_valid())
00401     nearest = nearerKd->
00402       nearestNeighborBBFI(target, nearerHr, searchSteps, maxDistSq,
00403                           distSq1, distSq2, maxdsq, bbfq, nobjidx);
00404 
00405   // If the second best match we just found is nearer than maxDistSq,
00406   // then reduce maxDistSq (modified step 9). Note: in the original
00407   // algorithm (which does not consider second-best matches), this
00408   // test would be done on distSq1 instead. So here we have a
00409   // performance impact for wanting to know the exact distance to the
00410   // second best match:
00411 
00412   //  if (distSq2 < maxDistSq) maxDistSq = distSq2;
00413 
00414   // NOTE2: the overhead is really too high. By using distSq1 as in
00415   // the original algo we sacrifice some accuracy on our estimation of
00416   // the second best distance, but accelerate the overall search a lot:
00417   if (distSq1 < maxDistSq) maxDistSq = distSq1;
00418 
00419   // before we even think about checking out the further HR, let's see
00420   // if we have one in our BBF queue:
00421   rutz::shared_ptr<Keypoint> pivot; uint pividx, pivobji;
00422   if (bbfq.size() > 0)
00423     {
00424       BBFdata fu = bbfq.top(); bbfq.pop();
00425       furtherHr = fu.hr; furtherKd = fu.tree; pividx = fu.pividx;
00426       pivot = fu.pivot; pivobji = fu.pivobji;
00427     }
00428   else
00429     { pivot = itsPivot; pividx = itsPivotIndex; pivobji = itsObjIndex; }
00430 
00431   // decrement our search count anf forget about further exploration
00432   // if we have reached 0:
00433   -- searchSteps;
00434 
00435   // If the further HR is too far away, it will be hopeless and we
00436   // don't even need to look at it (step 10):
00437   if (searchSteps > 0 && furtherHr.isInReach(target, maxDistSq))
00438     {
00439       // ok the further HR may contain a better (or second better)
00440       // match. First let's check how close our pivot is to the
00441       // target (modified steps 10.1.1 to 10.1.3):
00442       int ptDistSq = pivot->distSquared(target);
00443       if (ptDistSq < distSq1)
00444         {
00445           // our pivot is closer than our nearest, so make the pivot
00446           // our new nearest:
00447           nearest = pividx;
00448 
00449           // if our pivot is in the same object than our previous
00450           // nearest, then just slide the distances; otherwise, make
00451           // distsq2 maximal:
00452           if (nobjidx == pivobji)
00453             { distSq2 = distSq1; distSq1 = ptDistSq; }
00454           else
00455             { distSq1 = ptDistSq; distSq2 = maxdsq; nobjidx = pivobji; }
00456 
00457           // update the max distance for further search:
00458           maxDistSq = distSq1;
00459         }
00460       else if (ptDistSq < distSq2)
00461         {
00462           // our pivot is farther than the nearest but closer than the
00463           // second nearest, so just update the second nearest
00464           // distance and max distance, but only if our pivot is in
00465           // the same object as our nearest:
00466           if (nobjidx == pivobji)
00467             { distSq2 = ptDistSq; maxDistSq = distSq2; }
00468         }
00469 
00470       // Recursively explore the further HR (modified step 10.2):
00471       int tempDistSq1 = maxdsq, tempDistSq2 = maxdsq;
00472       uint tempNearest = 0U, tempobjidx = 0U;
00473       if (furtherKd.is_valid())
00474         tempNearest = furtherKd->
00475           nearestNeighborBBFI(target, furtherHr, searchSteps, maxDistSq,
00476                               tempDistSq1, tempDistSq2, maxdsq,
00477                               bbfq, tempobjidx);
00478 
00479       // If we found a better nearest or second nearest, update
00480       // accordingly (modified step 10.3):
00481       if (tempDistSq1 < distSq1)
00482         {
00483           // tempNearest is better than nearest, so use tempNearest:
00484           nearest = tempNearest;
00485 
00486           // now, who is the second best?
00487           if (tempobjidx == nobjidx)
00488             {
00489               // temp is in the same object as nearest used to be. So
00490               // let's just slide the second-best distances:
00491               if (tempDistSq2 < distSq1) distSq2 = tempDistSq2;
00492               else distSq2 = distSq1;
00493             }
00494           else
00495             {
00496               // temp in different object from old nearest:
00497               distSq2 = maxdsq;
00498               nobjidx = tempobjidx;
00499             }
00500 
00501           // also update our best distance:
00502           distSq1 = tempDistSq1;
00503         }
00504       else if (tempDistSq1 < distSq2)
00505         {
00506           // tempNearest is worse than nearest but better than our
00507           // second nearest, so just update our second nearest
00508           // distance, but only if in same object:
00509           if (tempobjidx == nobjidx)
00510             distSq2 = tempDistSq1;
00511         }
00512     }
00513 
00514   // return the best we have found. Note: nearest may be empty if we
00515   // did not find anything:
00516   distsq1 = distSq1; distsq2 = distSq2; objidx = nobjidx;
00517   return nearest;
00518 }
00519 
00520 // ######################################################################
00521 uint KDTree::goodCandidate(const std::vector< rutz::shared_ptr<Keypoint> >& exset,
00522                            uint& splitDim)
00523 {
00524   const uint numkeys = exset.size();
00525   if (numkeys == 0) { LFATAL("Keypoint list given is empty!"); return 0; }
00526 
00527   // get the dimensionality of our keypoints:
00528   uint dim = exset[0]->getFVlength();
00529 
00530   // initialize temporary hr search min/max values:
00531   std::vector<byte> minHr(dim, 255), maxHr(dim, 0);
00532 
00533   // go over the examplar set and adjust min/max HR:
00534   for (uint i = 0; i < numkeys; i++)
00535     {
00536       rutz::shared_ptr<Keypoint> dom = exset[i];
00537       for (uint k = 0; k < dim; k++)
00538         {
00539           const byte val = dom->getFVelement(k);
00540           if (val < minHr[k]) minHr[k] = val;
00541           if (val > maxHr[k]) maxHr[k] = val;
00542         }
00543     }
00544 
00545   // find the dim with maximum range; will be our splitting dimension:
00546   int maxDiff = 0;
00547   for (uint k = 0; k < dim; k++)
00548     {
00549       const int diffHr = int(maxHr[k]) - int(minHr[k]);
00550       if (diffHr > maxDiff) { maxDiff = diffHr; splitDim = k; }
00551     }
00552 
00553   // the splitting dimension is splitDim. Now find an exemplar as
00554   // close to the arithmetic middle as possible:
00555   const int middle = (maxDiff >> 1) + int(minHr[splitDim]);
00556   int exemMinDiff = 256; uint middleidx = 0;
00557 
00558   for (uint i = 0; i < numkeys; i++)
00559     {
00560       const int curDiff = std::abs(exset[i]->getFVelement(splitDim) - middle);
00561       if (curDiff < exemMinDiff) { exemMinDiff = curDiff; middleidx = i; }
00562     }
00563 
00564   // return the middle exemplar (and splitDim):
00565   return middleidx;
00566 }
00567 
00568 // ######################################################################
00569 /* So things look consistent in everyone's emacs... */
00570 /* Local Variables: */
00571 /* indent-tabs-mode: nil */
00572 /* End: */
Generated on Sun May 8 08:42:16 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3