Speed Improvement to FHT Line Finder

      #include <gandalf/vision/modified_fht.h>

The Fast Hough Transform can be used to fit a line to points on a plane. However the modification to the FHT described here has proved to be slightly faster for the line fitting problem, and it requires less memory. It can readily be generalised and is applicable to the same class of Hough transform problems as standard FHT. However for higher dimensional parameter spaces (e.g. plane fitting) standard FHT takes over as the faster method. To simplify the notation the modified FHT (referred to henceforth as the MFHT) is described for line fitting only.

The FHT line fitter was described in section 5.11.1.3 and the notation used there will be followed. Points $(u_j , v_j )$, $j=1 \ldots n$ are scattered on the $(u,v)$ plane. A straight line in the plane is defined as

$$v=\alpha u + \beta$$

where $\alpha$ and $\beta$ are constant. Each point $(u_j , v_j )$ ``votes'' for a line in parameter space $(\alpha , \beta )$. Ranges for $\alpha$ and $\beta$ are specified, so $\alpha_1 \leq \alpha \leq \alpha_2$ and $\beta_1 \leq \beta \leq \beta_2$. Like the standard FHT, the MFHT proceeds by dividing this root rectangle (hypercube) into four ($2^k$) child rectangles and counting the lines (hyperplanes) passing through each child rectangle. If the number of such intersections for any child is greater than a threshold $T$, the child is subdivided. The MFHT differs in that the circumscribing hypersphere (in this case ellipse) approximation is not used. Intersections between line and rectangle are calculated exactly. Hence there is no need to normalise parameter space in order to transform the root rectangle into a square, as is required for standard FHT.

The line in $(\alpha , \beta )$ space defined by a point $(u_j , v_j )$ is

$$\beta = - u \alpha + v.$$

Intersection between line and rectangle is calculated by comparing the $\beta$ coordinate of the vertices of the rectangle with the points of intersection between the line and the constant $\alpha$ sides of the rectangle. This is illustrated in figure 5.6.

The ranges $[\alpha_{\rm low},\alpha_{\rm high}]$ and $[\beta_{\rm low},\beta_{\rm high}]$ define a rectangle in $(\alpha , \beta )$ space. Three lines $A$, $B$ and $C$ are shown. For each line, the $\beta$ values of the intersection points with the lines $\alpha = \alpha_{\rm low}$ and $\alpha = \alpha_{\rm high}$ (points $A_1$ and $A_2$, $B_1$ and $B_2$, $C_1$ and $C_2$ in figure 5.6) are compared with $\beta_{\rm low}$ and $\beta_{\rm high}$. The $\beta$ values can be thought of as intercept values of the line with the $\alpha = {\rm constant}$ lines. It is clear that line and rectangle miss each other if and only if if all four vertices are either below or above (i.e. their $\beta$ values are all $<$ or $>$) both intercepts. Obviously this is true for line $B$ but false for lines $A$ and $C$.

In practice it saves repeated computational effort if intersections between a parent's four child rectangles and the lines are calculated at the same time. Let us assume that enough lines intersect the rectangle in figure 5.6 for it to be subdivided. It is divided into four child rectangles $R_{00}$, $R_{01}$, $R_{10}$ and $R_{11}$ as shown in figure 5.7.

For each line such as line $A$ shown, there are three intercept $\beta$ values, at $\alpha_{\rm low}$, $\alpha_{\rm av}$ and $\alpha_{\rm high}$. Obviously $\alpha_{\rm av} = (\alpha_{\rm low} + \alpha_{\rm high})/2$. The intercepts are each to be compared with the three $\beta$ values $\beta_{\rm low}$, $\beta_{\rm av}$ and $\beta_{\rm high}$. A boolean flag is defined for each of the nine vertices ($V_{ll}$, $V_{la}$ etc. in figure 5.7) of the rectangular subdivision. Each flag is set to $false$ if the vertex lies below the line (i.e. if the $\beta$ value of the vertex is less than the corresponding intercept $\beta$ value of the line) and to $true$ if it lies above it. Label the flags $v_{ll}$, $v_{la}$ etc. Then it follows that:-

1. The line misses rectangle $R_{00}$ if and only if $v_{ll}$, $v_{la}$, $v_{al}$, $v_{aa}$ are all either $true$ or $false$.

2. The line misses rectangle $R_{01}$ if and only if $v_{la}$, $v_{lh}$, $v_{aa}$, $v_{ah}$ are all either $true$ or $false$.

3. The line misses rectangle $R_{10}$ if and only if $v_{al}$, $v_{aa}$, $v_{hl}$, $v_{ha}$ are all either $true$ or $false$.

4. The line misses rectangle $R_{11}$ if and only if $v_{aa}$, $v_{ah}$, $v_{ha}$, $v_{hh}$ are all either $true$ or $false$.

In the standard version of the FHT, the normalised distances from hyperplane to centre of child hypercubes are calculated from the normalised distance of the parent from the hyperplane. The child ``inherits'' the new normalised distances from the parent, and passes them on to its own offspring. The MFHT also passes information from parent to child, in this case the intercept $\beta$ values.