Optimization routines

---

Detailed Description

The functions in this section deal specifically with optimizing a decision tree detector for repeatability.

The code in learn_detector() is a direct implementation of the algorithm described in section V of the accompanying paper.

The manipulation of the tree is necessarily tied to the internal representation which is described in the tree representation.

Functions
tree_element *	random_tree (int d, bool is_eq_branch=1)
double	compute_temperature (int i, int imax)
tree_element *	learn_detector (const vector< Image< byte > > &images, const vector< vector< Image< array< float, 2 > > > > &warps)
void	run_learn_detector (int argc, char **argv)
int	main (int argc, char **argv)

---

Function Documentation

tree_element* random_tree	(	int	d,
		bool	is_eq_branch = 1
	)

Generate a random tree, as part of a stochastic optimization scheme.

Parameters:

	d	Depth of tree to generate
	is_eq_branch	Whether eq-branch constraints should be applied. This should always be true when the function is called.

Definition at line 218 of file learn_detector.cc.

References num_offsets.

Referenced by learn_detector().

{
    //Recursively generate a tree of depth d
    //
    //Generated trees respect invariant 1
    if(d== 0)
        if(is_eq_branch)
            return new tree_element(0);
        else
            return new tree_element(rand()%2);
    else
        return new tree_element(random_tree(d-1, 0), random_tree(d-1, 1), random_tree(d-1, 0), rand()%num_offsets );
}

double compute_temperature	(	int	i,
		int	imax
	)

Compute the current temperature from parameters in the configuration file.

Parameters:

	i	The current iteration.
	imax	The maximum number of iterations.

Returns:

The temperature.

Definition at line 241 of file learn_detector.cc.

Referenced by learn_detector().

{
    double scale=GV3::get<double>("Temperature.expo.scale");
    double alpha = GV3::get<double>("Temperature.expo.alpha");

    return scale * exp(-alpha * i / imax);
}

tree_element* learn_detector	(	const vector< Image< byte > > &	images,
		const vector< vector< Image< array< float, 2 > > > > &	warps
	)

Generate an optimized corner detector.

Parameters:

	images	The training images
	warps	Warps for evaluating the performance on the training images.

Returns:

An optimized detector.

Definition at line 258 of file learn_detector.cc.

References compute_repeatability(), compute_temperature(), tree_element::copy(), tree_element::eq, tree_element::gt, tree_element::is_corner, tree_element::is_leaf(), tree_element::lt, tree_element::nth_element(), tree_element::num_nodes(), num_offsets, tree_element::offset_index, tree_element::print(), random_tree(), sq(), and tree_detect_corners().

Referenced by run_learn_detector().

{
    unsigned int  iterations=GV3::get<unsigned int>("iterations");       // Number of iterations of simulated annealing.
    int threshold = GV3::get<int>("FAST_threshold");                     // Threshold at which to perform detection
    int fuzz_radius=GV3::get<int>("fuzz");                               // A point must be this close to be repeated (\varepsilon)
    double repeatability_scale = GV3::get<double>("repeatability_scale");// w_r 
    double num_cost =   GV3::get<double>("num_cost");                    // w_n
    int max_nodes = GV3::get<int>("max_nodes");                          // w_s

    bool first_time = 1;
    double old_cost = HUGE_VAL;                                          //This will store the final score on the previous iteration: \hat{k}_{I-1}

    ImageRef image_size = images[0].size();

    set<int> debug_triggers = GV3::get<set<int> >("triggers");           //Allow artitrary GVars code to be executed at a given iteration.
    
    //Preallocated space for nonmax-suppression. See tree_detect_corners()
    Image<int> scratch_scores(image_size, 0);

    //Start with an initial random tree
    tree_element* tree = random_tree(GV3::get<int>("initial_tree_depth"));
    
    for(unsigned int itnum=0; itnum < iterations; itnum++)
    {
        if(debug_triggers.count(itnum))
            GUI.ParseLine(GV3::get<string>(sPrintf("trigger.%i", itnum)));

        /* Trees:

            Invariants:
                1:     eq->{0,0,0,(0,0),0}          //Leafs of an eq pointer must not be corners

            Operations:
                Leaves:
                    1: Splat on a random subtree of depth 1 (respect invariant 1)
                    2: Flip  class   (respect invariant 1)

                Nodes:
                    3: Copy one subtree to another subtree (no invariants need be respected)
                    4: Randomize offset (no invariants need be respected)
                    5: Splat a subtree in to a single node.


        Cost:
        
          (1 + (#nodes/max_nodes)^2) * (1 - repeatability)^2 * Sum_{frames} exp(- (fast_9_num-detected_num)^2/2sigma^2)
         
        */


        //Deep copy in to new_tree and work with the copy.
        tree_element* new_tree = tree->copy();

        cout << "\n\n-------------------------------------\n";
        cout << print << "Iteration" << itnum;

        if(GV3::get<bool>("debug.print_old_tree"))
        {
            cout << "Old tree is:" << endl;
            tree->print(cout);
        }
    
        //Skip tree modification first time so that the randomly generated
        //initial tree can be evaluated
        if(!first_time)
        {

            //Create a tree permutation
            tree_element* node;
            bool node_is_eq;
            

            //Select a random node
            int nnum = rand() % new_tree->num_nodes();
            rpair(node, node_is_eq) = new_tree->nth_element(nnum);

            cout << "Permuting tree at node " << nnum << endl;
            cout << print << "Node" << node << node_is_eq;
            

            //See section 4 in the paper.
            if(node->eq == NULL) //A leaf
            {
                if(rand() % 2 || node_is_eq)  //Operation 1, invariant 1
                {
                    cout << "Growing a subtree:\n";
                    //Grow a subtree
                    tree_element* stub = random_tree(1);

                    stub->print(cout);

                    //Splice it on manually (ick)
                    *node = *stub;
                    stub->lt = stub->eq = stub->gt = 0;
                    delete stub;

                }
                else //Operation 2
                {
                    cout << "Flipping the classification\n";
                    node->is_corner  = ! node->is_corner;
                }
            }
            else //A node
            {
                double d = rand_u();

                if(d < 1./3.) //Randomize the test
                {
                    cout << "Randomizing the test\n";
                    node->offset_index = rand() % num_offsets;
                }
                else if(d < 2./3.)
                {
                    //Select r, c \in {0, 1, 2} without replacement
                    int r = rand() % 3; //Remove
                    int c;              //Copy
                    while((c = rand()%3) == r){}

                    cout << "Copying branches " << c << " to " << r <<endl;

                    //Deep copy node c: it's a tree, not a graph.
                    tree_element* tmp;

                    if(c == 0)
                        tmp = node->lt->copy();
                    else if(c == 1)
                        tmp = node->eq->copy();
                    else
                        tmp = node->gt->copy();
                    
                    //Delete r and put the copy of c in its place
                    if(r == 0)
                    {
                        delete node->lt;
                        node->lt = tmp;
                    }
                    else if(r == 1)
                    {
                        delete node->eq;
                        node->eq = tmp;
                    }
                    else 
                    {
                        delete node->gt;
                        node->gt = tmp;
                    }

                    //NB BUG!!!
                    //At this point the invariant can be broken,
                    //since a "corner" leaf could have been copied
                    //to an "eq" branch.

                    //Oh dear. This bug made it in to the paper.
                    //Fortunately, the bytecode compiler ignores the tree
                    //when it can decuce its structure from the invariant.

                    //The following line should have been present in the paper:
                    if(node->eq->is_leaf())
                        node->eq->is_corner = 0;

                    //Happily, because the bytecode compiler deduces this
                    //it behaves as if this line was present, at evaluation time.
                    //Of course, the presense of this line will produce different
                    //results later if the node is subsequently copied back in one
                    //of these operations.
                }
                else //Splat!!! ie delete a subtree
                {
                    cout << "Splat!!!1\n";
                    delete node->lt;
                    delete node->eq;
                    delete node->gt;
                    node->lt = node->eq = node->gt = 0;

                    if(node_is_eq) //Maintain invariant 1
                        node->is_corner = 0;
                    else
                        node->is_corner = rand()%2;
                }
            }
        }
        first_time=0;

        if(GV3::get<bool>("debug.print_new_tree"))
        {
            cout << "New tree is: "<< endl;
            new_tree->print(cout);
        }
    
        
        //Detect all corners in all images
        vector<vector<ImageRef> > detected_corners;
        for(unsigned int i=0; i < images.size(); i++)
            detected_corners.push_back(tree_detect_corners(images[i], new_tree, threshold, scratch_scores));


        //Compute repeatability and assosciated cost
        double repeatability = compute_repeatability(warps, detected_corners, fuzz_radius, image_size);
        double repeatability_cost = 1 + sq(repeatability_scale/repeatability);

        //Compute cost associated with the total number of detected corners.
        float number_cost=0;
        for(unsigned int i=0; i < detected_corners.size(); i++)
        {
            double cost = sq(detected_corners[i].size() / num_cost);
            cout << print << "Image" << i << detected_corners[i].size()<< cost;
            number_cost += cost;
        }
        number_cost = 1 + number_cost / detected_corners.size();
        cout << print << "Number cost" << number_cost;

        //Cost associated with tree size
        double size_cost = 1 + sq(1.0 * new_tree->num_nodes()/max_nodes);
        
        //The overall cost function
        double cost = size_cost * repeatability_cost * number_cost;

        double temperature = compute_temperature(itnum,iterations);
        

        //The Boltzmann acceptance criterion:
        //If cost < old cost, then old_cost - cost > 0
        //so exp(.) > 1
        //so drand48() < exp(.) == 1
        double liklihood=exp((old_cost-cost) / temperature);

        
        cout << print << "Temperature" << temperature;
        cout << print << "Number cost" << number_cost;
        cout << print << "Repeatability" << repeatability << repeatability_cost;
        cout << print << "Nodes" << new_tree->num_nodes() << size_cost;
        cout << print << "Cost" << cost;
        cout << print << "Old cost" << old_cost;
        cout << print << "Liklihood" << liklihood;
        
        //Make the Boltzmann decision
        if(rand_u() < liklihood)
        {
            cout << "Keeping change" << endl;
            old_cost = cost;
            delete tree;
            tree = new_tree;
        }
        else
        {
            cout << "Rejecting change" << endl;
            delete new_tree;
        }
        
        cout << print << "Final cost" << old_cost;

    }


    return tree;
}

void run_learn_detector	(	int	argc,
		char **	argv
	)

Load configuration and data and learn a detector.

Parameters:

	argc	Number of command line arguments
	argv	Vector of command line arguments

Definition at line 522 of file learn_detector.cc.

References create_offsets(), draw_offsets(), learn_detector(), load_data(), tree_element::make_fast_detector(), block_bytecode::print(), tree_element::print(), and prune_warps().

Referenced by main().

{

    //Process configuration information
    GUI.LoadFile("learn_detector.cfg");
    GUI.parseArguments(argc, argv);

    
    //Load a ransom seed.
    if(GV3::get<int>("random_seed") != -1)
        srand(GV3::get<int>("random_seed"));

    //Initialize the global information for the tree    
    create_offsets();
    draw_offsets();

    
    //Load the training set
    string dir=GV3::get<string>("repeatability_dataset.directory");
    string format=GV3::get<string>("repeatability_dataset.format");
    int num=GV3::get<int>("repeatability_dataset.size");

    vector<Image<byte> > images;
    vector<vector<Image<array<float, 2> > > > warps;
    
    rpair(images, warps) = load_data(dir, num, format);

    prune_warps(warps, images[0].size());


    //Learn a detector
    tree_element* tree = learn_detector(images, warps);

    //Print out the results
    cout << "Final tree is:" << endl;
    tree->print(cout);
    cout << endl;

    cout << "Final block detector is:" << endl;
    {
        block_bytecode f = tree->make_fast_detector(9999);
        f.print(cout, 9999);
    }
}

int main	(	int	argc,
		char **	argv
	)

Driver wrapper.

Parameters:

	argc	Number of command line arguments
	argv	Vector of command line arguments

Definition at line 572 of file learn_detector.cc.

References run_learn_detector().

{
    try
    {   
        run_learn_detector(argc, argv);
    }
    catch(Exceptions::All w)
    {   
        cerr << "Error: " << w.what << endl;
    }
}

---