Tree representation.

Classes
class	tree_element
	This struct represents a node of the tree, and has pointers to other structs, thereby representing a branch or the entire tree. More...
struct	ParseError
	A named symbol to throw in the case that tree deserialization fails with a parse error. More...
Functions
vector< ImageRef >	tree_detect_corners_all (const Image< byte > &im, const tree_element *detector, int threshold)
vector< ImageRef >	tree_detect_corners (const Image< byte > &im, const tree_element *detector, int threshold, Image< int > scores)
tree_element *	load_a_tree (istream &i, bool eq_branch)
tree_element *	load_a_tree (istream &i)
vector< ImageRef >	transform_offsets (const vector< ImageRef > &offsets, int angle, bool r)
void	create_offsets ()
Variables
vector< vector < ImageRef > >	offsets
int	num_offsets
pair< ImageRef, ImageRef >	offsets_bbox

---

Function Documentation

vector<ImageRef> tree_detect_corners_all	(	const Image< byte > &	im,
		const tree_element *	detector,
		int	threshold
	)

Detect corners without nonmaximal suppression in an image.

This contains a large amount of configurable debugging code to verify the correctness of the detector by comparing different implementations. High speed is achieved by converting the detector in to bytecode and JIT-compiling if possible.

The function recognises the following GVars:

• debug.verify_detections Veryify JIT or bytecode detected corners using tree_element::detect_corner

Parameters:

	im	The image to detect corners in.
	detector	The corner detector.
	threshold	The detector threshold.

Definition at line 45 of file faster_tree.cc.

References tree_element::bbox(), block_bytecode::detect(), tree_element::detect_corner(), and tree_element::make_fast_detector().

{
    ImageRef tl, br, s;
    rpair(tl,br) = detector->bbox();
    s = im.size();

    int ymin = 1 - tl.y, ymax = s.y - 1 - br.y;
    int xmin = 1 - tl.x, xmax = s.x - 1 - br.x;

    ImageRef pos;
    
    vector<int> corners;
    
    block_bytecode f2 = detector->make_fast_detector(im.size().x);

    f2.detect(im, corners, threshold, xmin, xmax, ymin, ymax);
    

    if(GV3::get<bool>("debug.verify_detections"))
    {
        //Detect corners using slowest, but most obvious detector, since it's most likely to 
        //be correct.
        vector<ImageRef> t;
        for(pos.y = ymin; pos.y < ymax; pos.y++)
        {
            for(pos.x = xmin; pos.x < xmax; pos.x++)
                if(detector->detect_corner(im, pos, threshold))
                    t.push_back(pos);
        }

        //Verify detected corners against this result
        if(t.size() == corners.size())
        {
            for(unsigned int i=0; i < corners.size(); i++)
                if(im.data() + corners[i] != & im[t[i]])
                {
                    cerr << "Fatal error: standard and fast detectors do not match!\n";
                    cerr << "Same number of corners, but different positions.\n";
                    exit(1);
                }
        }
        else
        {
            cerr << "Fatal error: standard and fast detectors do not match!\n";
            cerr << "Different number of corners detected.\n";
            cerr << corners.size() << " " << t.size() << endl;
            exit(1);
        }
    }

    vector<ImageRef> ret;

    int d = im.size().x;
    for(unsigned int i=0; i < corners.size(); i++)
    {
        int o = corners[i];
        ret.push_back(ImageRef(o %d, o/d));
    }

    return ret;
}

vector<ImageRef> tree_detect_corners	(	const Image< byte > &	im,
		const tree_element *	detector,
		int	threshold,
		Image< int >	scores
	)

Detect corners with nonmaximal suppression in an image.

This contains a large amount of configurable debugging code to verify the correctness of the detector by comparing different implementations. High speed is achieved by converting the detector in to bytecode and JIT-compiling if possible.

The function recognises the following GVars:

• debug.verify_detections Veryify JIT or bytecode detected corners using tree_element::detect_corner
• debug.verify_scores Veryify bytecode computed scores using tree_element::detect_corner

Parameters:

	im	The image to detect corners in.
	detector	The corner detector.
	threshold	The detector threshold.
	scores	This image will be used to store the corner scores for nonmaximal suppression and is the same size as im. It is passed as a parameter since allocation of an image of this size is a significant expense.

Definition at line 125 of file faster_tree.cc.

References tree_element::bbox(), block_bytecode::detect(), tree_element::detect_corner(), and tree_element::make_fast_detector().

Referenced by learn_detector(), and faster_learn::operator()().

{
    ImageRef tl, br, s;
    rpair(tl,br) = detector->bbox();
    s = im.size();

    int ymin = 1 - tl.y, ymax = s.y - 1 - br.y;
    int xmin = 1 - tl.x, xmax = s.x - 1 - br.x;

    ImageRef pos;
    scores.zero();
    
    vector<int> corners;
    
    block_bytecode f2 = detector->make_fast_detector(im.size().x);

    f2.detect(im, corners, threshold, xmin, xmax, ymin, ymax);
    

    if(GV3::get<bool>("debug.verify_detections"))
    {
        //Detect corners using slowest, but most obvious detector, since it's most likely to 
        //be correct.
        vector<ImageRef> t;
        for(pos.y = ymin; pos.y < ymax; pos.y++)
        {
            for(pos.x = xmin; pos.x < xmax; pos.x++)
                if(detector->detect_corner(im, pos, threshold))
                    t.push_back(pos);
        }

        //Verify detected corners against this result
        if(t.size() == corners.size())
        {
            for(unsigned int i=0; i < corners.size(); i++)
                if(im.data() + corners[i] != & im[t[i]])
                {
                    cerr << "Fatal error: standard and fast detectors do not match!\n";
                    cerr << "Same number of corners, but different positions.\n";
                    exit(1);
                }
        }
        else
        {
            cerr << "Fatal error: standard and fast detectors do not match!\n";
            cerr << "Different number of corners detected.\n";
            cerr << corners.size() << " " << t.size() << endl;
            exit(1);
        }
    }



    //Compute scores
    for(unsigned int j=0; j < corners.size(); j++)
    {
        int i=threshold + 1;
        while(1)
        {
            int n = f2.detect(im.data() + corners[j], i);
            if(n != 0)
                i += n;
            else
                break;
        }
        scores.data()[corners[j]] = i-1;
    }

    if(GV3::get<bool>("debug.verify_scores"))
    {
        //Compute scores using the obvious, but slow recursive implementation.
        //This can be used to test the no obvious FAST implementation and the
        //non obviouser JIT implementation, if it ever exists.
        for(unsigned int j=0; j < corners.size(); j++)
        {
            int i=threshold + 1;
            ImageRef pos =  im.pos(im.data() + corners[j]);
            while(1)
            {
                int n = detector->detect_corner(im, pos, i);
                if(n != 0)
                    i += n;
                else
                    break;
            }

            if(scores.data()[corners[j]] != i-1)
            {
                cerr << "Fatal error: standard and fast scores do not match!\n";
                cerr << "Different score detected at  " << pos << endl;
                exit(1);
            }
        }
    }

    
    //Perform non-max suppression the simple way
    vector<ImageRef> nonmax;
    int d = im.size().x;
    for(unsigned int i=0; i < corners.size(); i++)
    {
        int o = corners[i];
        int v = scores.data()[o];

        if( v > *(scores.data() + o + 1    )  &&
            v > *(scores.data() + o - 1    )  &&
            v > *(scores.data() + o +d + 1 )  &&
            v > *(scores.data() + o +d     )  &&
            v > *(scores.data() + o +d - 1 )  &&
            v > *(scores.data() + o -d + 1 )  &&
            v > *(scores.data() + o -d     )  &&
            v > *(scores.data() + o -d - 1))
        {
            nonmax.push_back(ImageRef(o %d, o/d));
        }
    }

    return nonmax;
}

tree_element* load_a_tree	(	istream &	i,
		bool	eq_branch
	)

Parses a tree from an istream.

This will deserialize a tree serialized by tree_element::print(). On error, ParseError is thrown.

Parameters:

	i	The stream to parse
	eq_branch	Is it an EQ branch? Check the invariant.

Returns:

An allocated tree. Ownership is passed to the callee.

Definition at line 287 of file faster_tree.cc.

References is_corner(), and split().

Referenced by faster_learn::faster_learn(), load_a_tree(), and main().

{   
    string line;
    getline(i, line);

    vector<string> tok = split(line);

    if(tok.size() == 0)
        throw ParseError();

    if(tok[0] == "Is")
    {
        if(tok.size() != 7)
            throw ParseError();

        bool is_corner = ato<bool>(tok[2]);

        if(eq_branch && is_corner)
        {
            cerr << "Warning: Fixing invariant in tree\n";
            is_corner=0;
        }

        return new tree_element(is_corner);
    }
    else
    {
        if(tok.size() != 5)
            throw ParseError();

        int offset = ato<int>(tok[0]);

        auto_ptr<tree_element> t1(load_a_tree(i, false));
        auto_ptr<tree_element> t2(load_a_tree(i, true));
        auto_ptr<tree_element> t3(load_a_tree(i, false));
        auto_ptr<tree_element> ret(new tree_element(t1.release(), t2.release(), t3.release(), offset)); 

        return ret.release();

    }
}

tree_element* load_a_tree

(

istream &

i

)

Parses a tree from an istream.

This will deserialize a tree serialized by tree_element::print(). On error, ParseError is thrown.

Parameters:

i

The stream to parse

Returns:

An allocated tree. Ownership is passed to the callee.

Definition at line 334 of file faster_tree.cc.

References load_a_tree().

{
    return load_a_tree(i, true);
}

vector<ImageRef> transform_offsets	(	const vector< ImageRef > &	offsets,
		int	angle,
		bool	r
	)

Rotate a vector<ImageRef> by a given angle, with an optional reflection.

Parameters:

	offsets	Offsets to rotate.
	angle	Angle to rotate by.
	r	Whether to reflect.

Returns:

The rotated offsets.

Definition at line 66 of file offsets.cc.

References ir_rounded().

Referenced by create_offsets().

{
    double a = angle * M_PI / 2;    

    double R_[] = { cos(a), sin(a), -sin(a) , cos(a) };
    double F_[] = { 1, 0, 0, r?-1:1};

    Matrix<2> R(R_), F(F_);
    Matrix<2> T = R*F;

    vector<ImageRef> ret;

    for(unsigned int i=0; i < offsets.size(); i++)
    {
        Vector<2> v = vec(offsets[i]);
        ret.push_back(ir_rounded(T * v));
    }
    
    return ret;
}

void create_offsets

(

)

Create a list of offsets with various transformation to map the offset number (see Figure 7 in the accompanying paper) to a pixel coordinate, inclusing all combinations of rotation and reflection.

The function populates offsets, and must be called before anything uses this variable.

All possible offsets are selected in an annulus, which uses the following gvars:

• offsets.min_radius Minimum distance from (0,0) for offset
• offsets.max_radius Maximum distance from (0,0) for offset

Definition at line 156 of file offsets.cc.

Referenced by main(), and run_learn_detector().

{
    //Pixel offsets are represented as integer indices in to an array of
    //ImageRefs. That means that by choosing the array, the tree can be
    //rotated and/or reflected. Here, an annulus of possible offsets is 
    //created and rotated by all multiples of 90 degrees, and then reflected.
    //This gives a total of 8.
    offsets.resize(8);
    {   
        double min_r = GV3::get<double>("offsets.min_radius");
        double max_r = GV3::get<double>("offsets.max_radius");

        ImageRef max((int)ceil(max_r+1), (int)ceil(max_r+1));
        ImageRef min = -max, p = min;

        //cout << "Offsets: ";

        do
        {
            double d = vec(p) * vec(p);

            if(d >= min_r*min_r && d <= max_r * max_r)
            {
                offsets[0].push_back(p);
                //cout << offsets[0].back() << " ";
            }
        }
        while(p.next(min, max));

    //  cout << endl;

        offsets_bbox = make_pair(min, max);
    }
    offsets[1] = transform_offsets(offsets[0], 1, 0);
    offsets[2] = transform_offsets(offsets[0], 2, 0);
    offsets[3] = transform_offsets(offsets[0], 3, 0);
    offsets[4] = transform_offsets(offsets[0], 0, 1);
    offsets[5] = transform_offsets(offsets[0], 1, 1);
    offsets[6] = transform_offsets(offsets[0], 2, 1);
    offsets[7] = transform_offsets(offsets[0], 3, 1);
    num_offsets=offsets[0].size();
}

---

Variable Documentation

vector<vector<ImageRef> > offsets

Actual x,y offset of the offset numbers in the different available orientations.

Definition at line 49 of file offsets.cc.

Referenced by create_offsets(), tree_element::detect_corner(), tree_element::detect_corner_oriented(), draw_offsets(), extract_feature(), main(), tree_element::make_fast_detector(), and tree_element::make_fast_detector_o().

int num_offsets

The number of possible offsets.

Equivalent to offsets[x].size()

Definition at line 52 of file offsets.cc.

Referenced by create_offsets(), extract_feature(), learn_detector(), main(), and random_tree().

pair<ImageRef, ImageRef> offsets_bbox

Bounding box for offsets in all orientations.

This is therefore a bounding box for the detector.

Definition at line 55 of file offsets.cc.

Referenced by tree_element::bbox(), create_offsets(), and main().

---