contrib/brl/bbas/bsol/bsol_hough_line

Hough transform for fast queries on line sets. More...

#include <vcl_vector.h>
#include <vbl/vbl_ref_count.h>
#include <vbl/vbl_bounding_box.h>
#include <vbl/vbl_array_2d.h>
#include <vsol/vsol_line_2d_sptr.h>

Go to the source code of this file.

Classes
class	bsol_hough_line_index

Detailed Description

Hough transform for fast queries on line sets.

bsol_hough_line_index is a class for indexing 2-d lines and tangent vectors in the space of orientation and distance to the origin.

The line index space is defined as follows:

                              o
                             /
                   line --> /\                  .
                           /  |theta
      <-------------------o--/----------------->

The angle, theta, corresponding to the line tangent direction ranges from 0 to 180 degrees. The perpendicular distance to the origin, r, is defined as:

                     .           /
                         .      / Line
                   Line /   .  /
                   Normal     /^ .
                             /      r
                            /           .
                                           x Origin

r can be expressed as r = N.(M - O) where N is the line normal, O is the origin position vector and M is the line midpoint. Note that N = (-Sin(theta), Cos(theta)). The values of theta and r for a vsol_line_2d are computed by the method ::array_loc(..). If the line is translated by (tx, ty), then the r for the translated line is given by r' = r - Sin(theta)tx + Cos(theta)ty. The value of r for a given translation is computed by ::trans_loc(..).

The lines are stored in a two dimensional array of r_dim_ by th_dim_ bins of vector<vsol_line_2d_sptr>. The theta dimension of the array is typically 180/5, or 36. The r dimension is defined by the diagonal of the bounding box of the space containing the lines. The resolution in r is assumed to be 1. It is necessary to specify the bounding box of the line coordinate space at construction time, so that new lines entered into the index do not exceed array bounds.

Internally, the r space is defined on an origin at the center of the bounding box diagonal. This choice minimizes the error in normal distance due to variations in line orientation.

Typical usage:

Create a new index for a 100x100 coordinate space with 5 degree angular res.

      index = new bsol_hough_line_index(0.0, 0.0, 100.0, 100.0, 180.0, 5.0)

Add a line to the index

      ...
      vsol_line_2d_sptr l(p1, p2);
      index->index(l);

find collinear lines (lines in a 2-d region in Hough space centered on the parameters defined by line l)

      ...
      vcl_vector<vsol_line_2d_sptr> lines;
      index->lines_in_interval(lines, l, 1.0, 5.0);//dr = 1.0, dtheta = 5.0
                                                   //i.e. +- 1.0 and +- 5.0

find lines at a particular orientation

      index->parallel_lines(lines, 45.0, 5.0); //Lines parallel to 45 deg.
                                               //+- 5 deg.

Author:: J.L. Mundy December 1997

Date:: ported to VXL April 11, 2003

    Modifications
     10-sep-2004 Peter Vanroose Added copy ctor with explicit vbl_ref_count init

Definition in file bsol_hough_line_index.h.

Classes

Detailed Description