Formal Statement of the FHT Plane Fitting Algorithm

- A set of disparity points
, .
- An array of weights , , one for each
disparity point
.
- Parameter space , restricted to the box with centre
and side lengths , and .
is the centre of the disparity search range.
- A vote threshold , being the total weight of
the edges in the square patch.
- A minimum level of subdivision (e.g. 3), and a maximum level (e.g. 10).

**begin**

- Declare new variables:
- An array of distances , .
An array of boolean flags where each either takes the value or .

Integer variables and , initialised to zero.

Variables , and making up a point in space.

Another array of boolean flags .

The variables , , , , and array are used to keep track of the best fit as the algorithm proceeds.

Set all the to .

For each disparity point :

**begin**- Calculate the plane parameters for
space:

where .Calculate the normalised perpendicular distance from the plane to the centre of the root cube:

If the plane passes through the root cube's circumscribing sphere: set to .

**end**Call the procedure with arguments as follows:

- Array of boolean flags .
- Array of normalised distances.
- Initial level of subdivision 0.
- Initial accumulator value 0.
- Empty line of descent list.

Procedure ( array of flags , array of normalised distances , subdivision level , accumulator value , line of descent list ):

**begin**

- Declare new variables:
- Eight boolean flags arrays
, one for
each , where
is a child cube index triplet
and each is
either -1 or 1. All the elements of the flag arrays are initialised
to .
Eight arrays of normalised distances.

Accumulators for each , initialised to zero.

Boolean flag , initialised to .

**begin**- For each child cube with index
**b**:**begin**- Calculate the normalised distance from plane
to the centre of the child cube:

(The values can be efficiently calculated by storing them in eight arrays, one for each .)If then

**begin**- Add weight to
Set flag to .

**end**

**end**

**end**Subdivide child cubes receiving greater than or equal to votes: If :

**begin**- For each child cube with index
**b**:**begin**- If
recursively subdivide child cube:
**begin**- Add to original line of descent.
Call with arguments , , , and extended line of descent.

Set flag to .

**end**

**end**

**end**If is still (i.e. no further subdivision of this cube), test for best fit so far:

- If
or if
and
:
**begin**- Set to .
Set to .

Calculate centre of cube in space by calling procedure with the line of descent as argument. The results are copied into , and .

Copy array of flags into array .

**end**

Procedure ( line of descent list ):
**begin**

- Declare new variables:
- Three arrays , and , each of three elements with indices -1, 0 and 1, so that and similarly for and . The zero (middle) elements of each array are not used.

Set , and to zero.

While line of descent not traversed (i.e. root cube not yet reached):

**begin**- Take next triplet of indices on line of descent.
Replace old values of , and :

**end**Add centre -coordinate of root cube to ( and coordinates of root are zero):

At the end of the algorithm is the highest level of subdivision reached. This must be greater than or equal to for the fit to be used. is the highest accumulator value of a cube at subdivision level , the cube has centre and these are the best fit plane parameters. The flags are if the 'th disparity point voted for the winning cube, and those disparity points constitute the subset of all the points which best fit a plane, given that the total weight of the points must exceed . They and the values of and can stored for use. More precise estimates of the plane parameters can be calculated using orthogonal regression.