Model Refinement

Due to unprecise measurements or registration errors, the 3D data might be erroneous. These errors lead to inaccurate 3D models. The semantic interpretation enables us to refine the model. The planes are adjusted such that the planes explain the 3D data and the semantic constraints like parallelism or orthogonality are enforced. To enforce the semantic constraints the model is first simplified. A preprocessing step merges neighboring planes with equal labels, e.g., two ceiling planes. This simplification process increases the point to plane distance, which has to be reduced in the following main optimization process. This optimization uses an error function to enforce the parallelism or orthogonality constraints. The error function consists of two parts. The first part accumulates the point to plane distances and the second part accumulates the angle differences given through the constraints. The error function has the following form:

$$E(P)$$ (4)

$$end{tex2html_deferred}! =$$ (5)

$$end{tex2html_deferred}!$$ (6)

$$end{tex2html_deferred}! \sum_{p_i \in P} \sum_{\V x \in p_1}$$ (7)

$$end{tex2html_deferred}!$$ (8)

$$end{tex2html_deferred}! \norm { (\V x - {\V p_i}_1) \cdot \V n_i } + \gamma$$ (9)

$$end{tex2html_deferred}!$$ (10)

$$end{tex2html_deferred}! \sum_{p_i \in P} \sum_{p_j \in P} c_{i,j},$$ (11)

where $c_{i,j}$ expresses the parallelism (5) or orthogonality (6) constraints according to

$$c_{i,j} = \min$$ (12)

$$end{tex2html_deferred}{\vert \arccos (\V n_i \cdot \V n_j)\vert, \vert\pi - \arccos (\V n_i \cdot \V n_j) \vert$$ (13)

$$end{tex2html_deferred}}$$ (14)

and

$$c_{i,j} = \vert \frac{\pi}{2} - \arccos (\V n_i \cdot \V n_j) \vert.$$ (15)

Minimization of eq. (4) is a nonlinear optimization process. The time consumed for optimizing eq. (4) increases with the number of plane parameters. To speed up the process, the normal vectors $\V n$ of the planes are specified by spherical coordinates, i.e., two angles $\alpha, \beta$. The point $\V p_1$ of a plane is reduced to a fixed vector pointing from the origin of the coordinate system in the direction of $\V p_1$ and its distance $d$. The minimal description of all planes $P$ consists of the concatenation of $p_i$, with $p_i = (\alpha_i, \beta_i, d_i)$, i.e., a plane $p_i$ is defined by two angles and a distance. A suitable optimization algorithm for eq. (4) is Powell's method (16), because the optimal solution is close to the starting point. Powell's method finds search directions with a small number of error function evaluations of eq. (4). Gradient descent algorithms have difficulties, since no derivatives are available. Cantzler et al. use a time consuming genetic algorithm for the optimization (6). Powell's method computes directions for function minimization in one direction (16). From the starting point $P_0$ in the $n$-dimensional search space (the concatenation of the 3-vector descriptions of all planes) the error function (4) is optimized along a direction $\V i$ using a one dimensional minimization method, e.g., Brent's method (17). Conjugate directions are good search directions, while unit basis directions are inefficient in error functions with valleys. At the line minimum of a function along the direction $\V i$ the gradient is perpendicular to $\V i$. In addition, the n-dimensional function is approximated at point $P$ by a Taylor series using point $P_0$ as origin of the coordinate system. It is

$$$$ (16)

$$end{tex2html_deferred}!$$ (17)

$$end{tex2html_deferred}!$$ (18)

$$end{tex2html_deferred}!$$ (19)

$$end{tex2html_deferred}!$$ (20)

$$end{tex2html_deferred}!$$ (21)

$$end{tex2html_deferred}! E(P)$$ (22)

$$end{tex2html_deferred}!$$ (23)

$$end{tex2html_deferred}!$$ (24)

$$end{tex2html_deferred}!$$ (25)

$$end{tex2html_deferred}!$$ (26)

$$end{tex2html_deferred}! = $$ (27)

$$end{tex2html_deferred}!$$ (28)

$$end{tex2html_deferred}!$$ (29)

$$end{tex2html_deferred}!$$ (30)

$$end{tex2html_deferred}!$$ (31)

$$end{tex2html_deferred}! E(P_0) +$$ (32)

$$end{tex2html_deferred}! \sum_k \frac{\partial E}{\partial P_k}P_k +$$ (33)

$$end{tex2html_deferred}! \sum_{k,l} \frac{\partial^2 E}{\partial P_{k}\partial P_{l}}P_{k}P_{l} + \cdots$$ (34)

$$end{tex2html_deferred}$$ (35)

$$end{tex2html_deferred}[1.05ex] \approx c - \V b \cdot P + \frac{1}{2} P \cdot \M A \cdot P$$ (36)

with $c = E(P_0)$, $\V b = \nabla E \vert _{P_0}$ and $\M A$ the Hessian matrix of $E$ at point $P_0$. Given a direction $\V i$, the method of conjugate gradients is to select a new direction $\V j$ so that $\V i$ and $\V j$ are perpendicular. This selection prevents interference of minimization directions. For the approximation (8) the gradient of $E$ is $\nabla E = A \cdot P - \V b$. From the differentiation ( $\delta(\nabla E) = \M A (\delta P)$) it follows for directions $\V i$ and $\V j$ that

$$0 = \V i \cdot \delta (\nabla E) = \V i \cdot \M A \cdot \V j.$$ (37)

With the above equation conjugate directions are defined and Powell's method produces such directions, without computing derivatives. The following heuristic scheme is implemented for finding new directions. Starting point is the description of the planes and the initial directions $\V i_l$, $l = 1, \ldots, n$ are the unit basis directions. The algorithm repeats the following steps until the error function (4) reaches a minimum (17):

1. Save the starting position as $P_0$.
   
2. For $l = 1, \ldots, n$, minimize the error function (4) starting from $P_{l-1}$ along the direction $\V i_l$ and store the minimum as the next position $P_l$. After the loop, all $P_l$ are computed.
   
3. Let $\V i_l$ be the direction of the largest decrease. Now this direction $\V i_l$ is replaced with the direction given by $(P_n - P_0)$. The assumption of the heuristic is that the substituted direction includes the replaced direction so that the resulting set of directions remains linear independent.
   
4. The iteration process continues with the new starting position $P_0 = P_n$, until the minimum is reached.

Experimental evaluations for the environment test settings show that the minimization algorithm finds a local minimum of the error function (4) and the set of directions remains linear independent. The computed description of the planes fits the data and the semantic model. The semantic description, i.e., the ceiling and walls, enable to transform the orientation of the model along the coordinate axis. Therefore it is not necessary to transform the model interactively into a global coordinate system or to stay in the coordinates given by the first 3D scan.