Reconstruction
The following steps (and possibly others) will be done (in some order,
possibly iteratively) to reconstruct the scene.
Edgel Pairing
Edgels of similiar direction, position, and length
should be paired because their similarity indicates either a hinge of two facades
or two facades which should be knitted into a larger surface.
screen shot of satyan's surfaces and the paired edgels
Plane Estimation
The points and segments define planes. First the algorithm calculates
a best fit plane to these data elements (for now, it only fits to
points) as they are grouped by node in the tree structure.
Currently I am working with a least squares algorithm,
but since there is a lot of noise in the data, an iterative technique
(that rejected data which matched least well on the last fit)
would be more appropriate and statistically robust.
Once a plane has been estimated for each tree node having "enough"
data elements, a bounding box for the surface patch is found by taking
the convex hull of the elements in the tree node projected onto the
plane.
a group of points in close proximity to each other and the convex hull of
each point's projection onto the plane determined to be their best fit
planes estimated from a non axis-aligned dataset with both an evenly split
and randomly split tree structure
Surface Joining
Once the pieces of surfaces are created by the previous stage, they
need to be joined with neighboring surface patches to make larger
surfaces with the same normal (in the same plane) or "hinged" at
edgels.
surfaces that need to be trimmed and joined by surface extension and
edgel hinging
Surface Extension
Basically, per surface patch we need to analyze neighboring cells of
the tree. If there are data elements (points and segments) or planes
that fit to the current plane, extend the surface by extending
the convex hull to include this data.
Surface Trimming
Get rid of the noise around the edges, make the edges clean and straight.
Edgel Hinging
If edgels or segments suggest that a surface should fold along a
particular line or if two surface patches meet and have normals
that are distinct, we should make two separate surfaces
and join them with an edgel.
However, just because two planes have different normals, it doesn't
mean we should create a break in the surface. It could be an error
from noisy data (in this case we might want to increase the volume
of the region of space we choose points from to estimate the plane).
Or it could be a lousy plane match because the node contains two or
more distinct planes and the best fit algorithm computed a plane that
was an "average" of the two planes (in this case we want to split the
node of the tree further to separate the planes).
images with noisy planes that can be eliminated
by setting requirements on plane estimates and minimum pixels per
area of surface created
Overall, the surface patches should be analyzed with some sort of
correctness factor attached to their plane estimate. This is based
on the total number of data items contributing to the estimate and
how well the plane fits the data.
Block Finishing
This step will identify blocks in the scene and hypothesize surfaces to
"finish" off the blocks.