faster_tree.h

00001 /*
00002 
00003     This file is part of the FAST-ER machine learning system.
00004     Copyright (C) 2008  Edward Rosten and Los Alamos National Laboratory
00005 
00006     This program is free software; you can redistribute it and/or modify
00007     it under the terms of the GNU General Public License as published by
00008     the Free Software Foundation; either version 2 of the License, or
00009     (at your option) any later version.
00010 
00011     This program is distributed in the hope that it will be useful,
00012     but WITHOUT ANY WARRANTY; without even the implied warranty of
00013     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014     GNU General Public License for more details.
00015 
00016     You should have received a copy of the GNU General Public License along
00017     with this program; if not, write to the Free Software Foundation, Inc.,
00018     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00019 */
00020 #ifndef INC_FASTER_TREE_H
00021 #define INC_FASTER_TREE_H
00022 
00023 #include <iostream>
00024 #include <string>
00025 #include <utility>
00026 
00027 #include <cvd/image.h>
00028 #include <cvd/byte.h>
00029 
00030 #include <tag/stdpp.h>
00031 
00032 #include "offsets.h"
00033 #include "faster_bytecode.h"
00034 
00035 /// This struct represents a node of the tree, and has pointers to other 
00036 /// structs, thereby representing a branch or the entire tree.
00037 ///
00038 /// @ingroup gTree
00039 class tree_element
00040 {
00041     public:
00042         tree_element *lt; ///<Branch of the tree to take if the offset pixel is much darker than the centre.
00043         tree_element *eq; ///<Branch of the tree to take if the offset pixel is much brighter than the centre.
00044         tree_element *gt; ///<Branch of the tree to take otherwise.
00045         bool         is_corner; ///<If the node is a leaf, then this is its attribute.
00046         int          offset_index; ///<Offset number of the pixel to examine. This indexes offsets[x]
00047         
00048 
00049         /// This returns the bounding box of the detector
00050         std::pair<CVD::ImageRef, CVD::ImageRef> bbox() const
00051         {
00052             return offsets_bbox;
00053         }
00054         
00055         /// This returns the number of nodes in the tree
00056         int num_nodes() const
00057         {
00058             if(eq == NULL)
00059                 return 1;
00060             else
00061                 return 1 + lt->num_nodes() + eq->num_nodes() + gt->num_nodes();
00062         }
00063         
00064 
00065         ///Is the node a leaf?
00066         bool is_leaf() const
00067         {
00068             return eq == NULL;
00069         }
00070         
00071 
00072         ///Return a given numbered element of the tree. Elements are numbered by depth-first traversal.
00073         ///
00074         ///@param t Element number to return
00075         ///@return pointer to the t'th element, and a flag indicating whether it's the direct child of an eq branch.
00076         std::pair<tree_element*,bool> nth_element(int t) 
00077         {
00078             //The root node can not be a corner.
00079             //Otherwise the strength would be inf.
00080             int n=0;
00081             return nth_element(t, n, true);
00082         }
00083     
00084         ///Compile the detector to bytecode. The bytecode is not a tree, but a graph. This is
00085         ///because the detector is applied in all orientations: offsets are integers which are
00086         ///indices in to a list of (x,y) offsets and there are multiple lists of offsets. The
00087         ///tree is also applied with intensity inversion.
00088         ///
00089         ///@param xsize The width of the image.
00090         ///@return The bytecode compiled detector.
00091         ///@ingroup gFastTree
00092         block_bytecode make_fast_detector(int xsize) const
00093         {
00094             std::vector<block_bytecode::fast_detector_bit> f;
00095             
00096             for(int invert=0; invert < 2; invert++)
00097                 for(unsigned int i=0; i <  offsets.size(); i++)
00098                 {   
00099                     //Make a FAST detector at a certain orientation
00100                     std::vector<block_bytecode::fast_detector_bit> tmp(1);
00101                     make_fast_detector_o(tmp, 0, xsize, i, invert);
00102 
00103                     int endpos = f.size() + tmp.size();
00104                     int startpos = f.size();
00105 
00106                     //Append tmp on to f, filling in the non-corners (jumps to endpos)
00107                     //and correcting the intermediate jumps destinations
00108                     for(unsigned int i=0 ; i < tmp.size(); i++)
00109                     {
00110                         f.push_back(tmp[i]);
00111 
00112                         if(f.back().eq == -1)
00113                             f.back().eq = endpos;
00114                         else if(f.back().eq > 0)
00115                             f.back().eq += startpos;
00116 
00117                         if(f.back().gt == -1)
00118                             f.back().gt = endpos;
00119                         else if(f.back().gt > 0)
00120                             f.back().gt += startpos;
00121 
00122                         if(f.back().lt == -1)
00123                             f.back().lt = endpos;
00124                         else if(f.back().lt > 0)
00125                             f.back().lt += startpos;
00126 
00127                     }
00128                 }
00129 
00130             //We need a final endpoint for non-corners
00131             f.resize(f.size() + 1);
00132             f.back().offset = 0;
00133             f.back().lt = 0;
00134             f.back().gt = 0;
00135             f.back().eq = 0;
00136 
00137             //Now we need an extra endpoint for corners
00138             for(unsigned int i=0; i < f.size(); i++)
00139             {
00140                 //EQ is always non-corner
00141                 if(f[i].lt == -2)
00142                     f[i].lt = f.size();
00143                 if(f[i].gt == -2)
00144                     f[i].gt = f.size();
00145             }
00146 
00147             f.resize(f.size() + 1);
00148             f.back().offset = 0;
00149             f.back().lt = 0;
00150             f.back().gt = 1;
00151             f.back().eq = 0;
00152 
00153             block_bytecode r = {f};
00154             
00155             return r;
00156         }
00157 
00158 
00159 
00160 
00161 
00162         private:
00163 
00164         ///This compiles the tree in a single orientation and form to bytecode.
00165         ///This is called repeatedly by  make_fast_detector. A jump destination
00166         ///of -1 refers to a non corner and a destination of -2 refers to a 
00167         ///corner.
00168         ///
00169         ///@param v Bytecode storage
00170         ///@param n Position in v to compile the bytecode to
00171         ///@param xsize Width of the image
00172         ///@param N orientation of the tree
00173         ///@param invert whether or not to perform and intensity inversion.
00174         ///@ingroup gFastTree
00175         void make_fast_detector_o(std::vector<block_bytecode::fast_detector_bit>& v, int n,int xsize, int N, bool invert) const
00176         {
00177             //-1 for non-corner
00178             //-2 for corner
00179 
00180             if(eq == NULL)
00181             {
00182                 //If the tree is a single leaf, then we end up here. In this case, it must be 
00183                 //a non-corner, otherwise the strength would be inf.
00184                 v[n].offset = 0;
00185                 v[n].lt = -1;
00186                 v[n].gt = -1;
00187                 v[n].eq = -1;
00188             }
00189             else
00190             {
00191                 v[n].offset = offsets[N][offset_index].x + offsets[N][offset_index].y * xsize;
00192 
00193                 if(eq->is_leaf())
00194                     v[n].eq = -1; //Can only be non-corner!
00195                 else
00196                 {
00197                     v[n].eq = v.size();
00198                     v.resize(v.size() + 1);
00199                     eq->make_fast_detector_o(v, v[n].eq, xsize, N, invert);
00200                 }
00201 
00202                 const tree_element* llt = lt;
00203                 const tree_element* lgt = gt;
00204 
00205                 if(invert)
00206                     std::swap(llt, lgt);
00207 
00208                 if(llt->is_leaf())
00209                 {
00210                     v[n].lt = -1 - llt->is_corner;
00211                 }
00212                 else
00213                 {
00214                     v[n].lt = v.size();
00215                     v.resize(v.size() + 1);
00216                     llt->make_fast_detector_o(v, v[n].lt, xsize, N, invert);
00217                 }
00218 
00219 
00220                 if(lgt->is_leaf())
00221                     v[n].gt = -1 - lgt->is_corner;
00222                 else
00223                 {
00224                     v[n].gt = v.size();
00225                     v.resize(v.size() + 1);
00226                     lgt->make_fast_detector_o(v, v[n].gt, xsize, N, invert);
00227                 }
00228             }
00229         }
00230 
00231         ///Select the n'th elment of the tree.
00232         std::pair<tree_element*, bool> nth_element(int target, int& n, bool eq_branch)
00233         {
00234             using tag::operator<<;
00235             #ifndef NDEBUG
00236                 if(!( (eq==0 && lt == 0 && gt == 0) || (eq!=0 && lt!=0 &&gt != 0)))
00237                 {
00238                     std::clog << "Error: corrupted tree\n";
00239                     std::clog << tag::print << "lt" << lt;
00240                     std::clog << tag::print << "eq" << eq;
00241                     std::clog << tag::print << "gt" << gt;
00242                     
00243                     abort();
00244                 }
00245             #endif
00246 
00247             if(target == n)
00248                 return std::make_pair(this, eq_branch);
00249             else
00250             {
00251                 n++;
00252 
00253                 tree_element * r;
00254                 bool e;
00255 
00256                 if(eq == 0)
00257                     return std::make_pair(r=0,eq_branch);
00258                 else
00259                 {
00260                     tag::rpair(r, e) = lt->nth_element(target, n, false);
00261                     if(r != NULL)
00262                         return std::make_pair(r, e);
00263 
00264                     tag::rpair(r, e) = eq->nth_element(target, n, true);
00265                     if(r != NULL)
00266                         return std::make_pair(r, e);
00267 
00268                     return gt->nth_element(target, n, false);
00269                 }
00270             }
00271         }
00272         
00273 
00274         /// Apply the tree to detect a corner in a single form.
00275         ///
00276         /// @param im Image in which to detect corners
00277         /// @param pos position at which to perform detection
00278         /// @param b Threshold
00279         /// @param n tree orientation to use (index in to offsets)
00280         /// @param invert Whether to perform an intensity inversion
00281         /// @return 0 for no corner, otherwise smallet amount by which a test passed.
00282         int detect_corner_oriented(const CVD::Image<CVD::byte>& im, CVD::ImageRef pos, int b, int n, bool invert) const
00283         {
00284             //Return number that threshold would have to be increased to in
00285             //order to change the outcome
00286 
00287 
00288             if(eq== NULL)
00289                 return is_corner * INT_MAX;
00290             else
00291             {   
00292                 int c = im[pos];
00293                 int p = im[pos + offsets[n][offset_index]];
00294 
00295                 const tree_element* llt = lt;
00296                 const tree_element* lgt = gt;
00297 
00298                 if(invert)
00299                     std::swap(llt, lgt);
00300 
00301 
00302                 if(p > c+b)
00303                     return std::min(p-(c+b), lgt->detect_corner_oriented(im, pos, b, n, invert));
00304                 else if(p < c-b)
00305                     return std::min((c-b)-p, llt->detect_corner_oriented(im, pos, b, n, invert));
00306                 else
00307                     return eq->detect_corner_oriented(im, pos, b, n, invert);
00308             }
00309         }
00310 
00311         public:
00312         /// Apply the tree in all forms to detect a corner.
00313         ///
00314         /// @param im CVD::Image in which to detecto corners
00315         /// @param pos position at which to perform detection
00316         /// @param b Threshold
00317         /// @return 0 for no corner, otherwise smallet amount by which a test passed.
00318         int detect_corner(const CVD::Image<CVD::byte>& im, CVD::ImageRef pos, int b) const
00319         {
00320             for(int invert=0; invert <2; invert++)
00321                 for(unsigned int i=0; i < offsets.size(); i++)
00322                 {
00323                     int n = detect_corner_oriented(im, pos, b, i, invert);
00324                     if(n)
00325                         return n;
00326                 }
00327             return 0;
00328         }
00329 
00330         /// Deep copy the tree.
00331         tree_element* copy()
00332         {
00333             tree_element* t = new tree_element(*this);
00334             if(eq != NULL)
00335             {
00336                 t->lt = lt->copy();
00337                 t->gt = gt->copy();
00338                 t->eq = eq->copy();
00339             }
00340 
00341             return t;
00342         }
00343 
00344         ///Serialize the tree
00345         ///
00346         ///@param o Stream to serialize to.
00347         ///@param ind The indent level to use for the current branch.
00348         void print(std::ostream& o, std::string ind="  ") const
00349         {
00350             using tag::operator<<;
00351 
00352 
00353             if(eq == NULL)
00354                 o << ind << tag::print << "Is corner: " << is_corner << this << lt << eq << gt;
00355             else
00356             {
00357                 o << ind << tag::print << offset_index << this << lt << eq << gt;
00358                 lt->print(o, ind + "  ");
00359                 eq->print(o, ind + "  ");
00360                 gt->print(o, ind + "  ");
00361             }
00362         }
00363         
00364         ///Destruct the tree node. This destructs all child nodes,
00365         ///so deleting a tree a deep modification operation.
00366         ~tree_element()
00367         {   
00368             delete lt;
00369             delete eq;
00370             delete gt;
00371         }
00372         
00373         ///Construct a leaf-node
00374         ///@param b Class of the node
00375         tree_element(bool b)
00376         :lt(0),eq(0),gt(0),is_corner(b),offset_index(0)
00377         {}
00378         
00379         ///Construct a non-leaf tree node
00380         ///@param a Less-Than branch of tree
00381         ///@param b Equal branch of tree
00382         ///@param c Greater-Than branch of tree
00383         ///@param i Pixel number to examine.
00384         tree_element(tree_element*a, tree_element* b, tree_element* c, int i)
00385         :lt(a),eq(b),gt(c),is_corner(0),offset_index(i)
00386         {}
00387 };
00388 
00389 
00390 tree_element* load_a_tree(std::istream& i);
00391 std::vector<CVD::ImageRef> tree_detect_corners(const CVD::Image<CVD::byte>& im, const tree_element* detector, int threshold, CVD::Image<int> scores);
00392 std::vector<CVD::ImageRef> tree_detect_corners_all(const CVD::Image<CVD::byte>& im, const tree_element* detector, int threshold);
00393 
00394 
00395 ///A named symbol to throw in the case that 
00396 ///tree deserialization fails with a parse error.
00397 ///@ingroup gTree
00398 struct ParseError{};
00399 
00400 
00401 
00402 
00403 #endif

Generated on Mon Mar 2 12:47:12 2009 for FAST-ER by  doxygen 1.5.3