Examples

The presented fitting and shape recognition approach has been tested on three different point cloud data sets.

Theseus Temple

The first data set is a model of the Theseus Temple in Vienna, Austria. The temple has been built between 1820 and 1823 by Peter Nobile as a smaller imitation of the Theseion Temple in Athens, Greece.

The temple is a photogrammetrical reconstruction generated by the EPOCH 3D web ser-vice (http://www.arc3d.be) and MeshLab (http://meshlab.sourceforge.net). Approximately 100 photos were taken with a consumer camera in an arc around the temple. The resulting point cloud contains many holes as large parts of the surface were hardly visible in the photos (e.g.

the floors). The data set consists of 2 million points.

To detect the columns, a row of vertical cylinders is used as the first generative model. The model’s parameters are

• two center points (start and end) on the xy-plane,

• the cylinder radius, and

• the number of columns.

The second model template is a stairway built out of quadrangles. The free parameters are

• starting point,

• direction of the stairway,

• riser height, and tread length.

In order to reduce the complexity of the fitting process this shape template uses less parameters than the simple implementation presented in the GML sidebar.

This example demonstrates the ability to fit elementary geometric shapes like columns, ap-proximated by cylinders, and generative descriptions such as stairs. The fitting works even for shapes which are only partly present in the data set: Parts of the columns surface and the stair-ways’ treads are not in the reconstructed point cloud as they are not visible in enough photos.

The number of steps and the width of the treads are considered to be infinite. In Figure3.5 these infinite structures have been cut manually along the bounding box of the relevant points near their surface.

This example reveals the problem of “over-fitting”. A good configurationx1for a cylinder of heighth₁with a small error value f₁:=fEX P(x₁)can always be improved (according to the objective function) by a cylinder at the same position and with the same radius but with a height h₂>h₁using additional points from other parts of the model. The second cylinder will always have more points near its surface thanx1, or at least the same number of points. Therefore, its error value will be smaller than or equal to f₁which leads to over-fitted columns.

Fig. 3.5 The presented algorithm is able to fit generative descriptions such as columns and stairways to the Theseus Temple point cloud. Even structures, which are not present in the input data set (e.g. the treads), are realized as they are part of the generative description.

Landhaus

The second data set is a photogrammetrical reconstruction of an inner courtyard. It is located in Graz, Austria, and belongs to the Landhaus. This Renaissance building has been constructed in 1557 by Domenico dell’Allio.

In this examples we tried to compensate the over-fitting effect of columns by adding top and ground geometry. For example, if the shape description does not only contain a column, but also some parts of the ground the column stands on, then an over-fitted column does not have a better rating per se, as the ground points will not belong to the over-fitted template any more.

The generative model to fit describes an arcade. It consists of columns with a quadratic profile. Its parameters are

• the center point(x,y,z)of the first column,

• the angleα to define the arcade’s orientation,

• the column widthw,

• the column heighth,

• the distancedbetween two columns, and

• the number of the columnsn.

Figure3.6illustrates an instance of the procedural description in horizontal projection.

(x,y,z)

w 2

α d

Fig. 3.6 The parametric description of the row-arcades model takes eight parameters: the three coordi-nates of the starting point(x,y,z), an offset angleαto define the arcade’s orientation, a column’s width wand heighth, the distancedbetween two columns, and the number of columnsn.

The results of the parameter extraction are shown in Figure3.7. The floors and arcs should have compensated the over-fitting of the columns. While it worked good for the column’s base, it failed for its height. The reason for this failure is mainly the poor quality of the data set.

The point cloud shown in Figure3.7has been reconstructed with only 4 sequences of photos.

The result has a very high level of noise. We started the fitting process withσ²=0.025_m¹2; i.e.

points up to±0.13maway from the surface are still regarded as part of the surface. As there are lots of noisy points from the wall above each arc, the algorithm determines the column height so that each arc crosses and intersects this wall. A data set with less noise could be processed with a smallerσ which would lead to better results.

Pisa Cathedral

The third example uses a point cloud with almost no noise. The data set of the Pisa Cathedral has been generated by the Visual Computing Laboratory at the Institute of Information Science and Technologies (ISTI) of the Italian National Research Council (CNR).

The Duomo is located on the Campo dei Miracoli in the center of Pisa, Italy. The architect Buscheto begun his masterpiece in 1064 and started the characteristic Pisan Romanesque style in architecture. Just like the whole building, the apse of the Duomo consists of many similar columns which are arranged in arcs and rows.

In this example the shape template describes an arcade that is arranged in an arc. It takes nine parameters and its horizontal and upright projection is shown in Figure3.8.

Two fitting processes have been started to detect the two arcades in the data set. Their results are visualized in Figure 3.9. Due to the low level of noise within the data set,σ² has been set to a rather small value. In this case the strategy to avoid over-fitting works. If the columns were higher, all points of the arc would not belong to the arc template any more and only a few additional points (located at the wall) would then belong to the shape description.

A closer look at statistical details of a fitting process gives an impression of the algorithm’s performance and exposes some technical aspects. The shape recognition of the circle-arcade model, which returned the parameters of the upper arcade in the laser scan data set (green visualization in Figure3.9) has been started with 444.991 points.

The shape template has nine free parameters: the center point x, y, z, the main radius R, the column radius r, the offset angleα, the opening angleβ, the number of columns n and

Fig. 3.7 The inner courtyard of the Landhaus in Graz consists of several arcades. Its point cloud model has a very high level of noise. A noisy data set requires a tolerant fitting configuration (large value of σ²). As a result the algorithm interprets the points above an arc as points belonging to an arc.

the column heighth. The fitting routine requires a bounded parameter domain. Therefore, the parameter intervals have roughly been estimated. The rangeδ of each parameter has been:

∆x=21.0m ∆y=21.0m ∆z=21.0m

∆R= 1.5m ∆r= 0.2m∆n= 0

∆ α = 14^◦ ∆ β = 14^◦ ∆h= 2.0m

Having set the parameter bounds/ranges the algorithm does not need any user interaction. It is able to handle an initial rough guess and converges to the global minimum with a precision in the scale of centimeters. Unfortunately, the number of columns had to be set manually. As the generative description does not check self-intersections or reasonability, a high number n of columns generates a “wall” of columns. In order to exclude such degenerated solutions, the number of columns has been fix. Consequently, the generative description had only eight free parameters.

h

(x,y,z) R r

α β

Fig. 3.8 The parametric description of the circle-arcades model takes nine parameters: the three coor-dinates of a center point(x,y,z), a main radiusR, a column radiusr, an offset angleα, an opening angle β, and the number of columnsn. These values define the ground construction in thexy plane which contains the center point. The last parameterhdefines the columns’ height. The height of the Roman arcs are determined by the column distances.