Surface--Normal Estimation with Neighbourhood Reorganization for 3D Reconstruction

Felix Calderon1, Ubaldo Ruiz1 and Mariano Rivera2

1Universidad Michoacana de San Nicoláss deHidalgo. División de Estudios de Posgrado.

Facultad de Ingeniería Eléctrica. Santiago Tapia 403 Centro. Morelia, Michoacán, México. CP 58000.2Centro de Investigacion en Matematicas A.C.Apdo. Postal 402, Guanajuato, Gto. Mexico. CP 36000.

ABSTRACT. Our proposal changes the characteristics of theneighborhood in places with corners or edges by assuming a locallyplane piecewise surface. The results obtained by NENR improve thequality of the normal with respect to the state of the artalgorithms. The new neighborhood computed by NENR, use only thosepoints that belong to the same plane and they are the nearestneighbors.

1. Introduction

The estimation of surface-normals from a point cloud is usuallydone in two stages, as proposed Hoppe et al. in[1] (NE--Hoppe). In the first stage the Tangent Plane(TP) is estimated at each point. Thus the Orthogonal unitaryvector to the Tangent Plane (OTP) will be used as an approximationof the normal at such point. In the second stage the orientationof the OTP, spatially coherent, is computed.

In general given set of pointsP={p1, … , pN}and let be Vi the set of knearest neighbours (neighbourhood) of thepoint pi. Then the TP at pi is obtained byfitting a plane,Api,x+ Bpi,y+ Cpi_z + D =0,for all the points pjin Vi by using a least-squaresprocedure or some robust estimator, then the surface-normal, ni, is the normalto the TP. Hoppe et al. [1] proposed to compute,ni, as the third eigenvector (associated with thesmallest eigenvalue if 123 then ni = -3 o 3) of the local covariance matrix given by equation (1):

(1)

The RANSAC algorithm [2] is an algorithm for robustfitting of models in the presence of many data outliers. RANSAC can not distinguish between noise and information,for instance, in case of a corner with three points (see figures1), RANSAC randomly can find three different planesusing only two point and the three solutions satisfy the same stopcriteria and only two points. Figure 1a representsthe worst solutionwhich is equivalent to the plane using three points and figure 1b the best solution.

The Oriented OTP (OOTP) is computed such that nearby planes areconsistently oriented (remember that ni = -3 o 3). The NE-Hoppe algorithm, proposed in[1], considered the state of the art, resolves the ambiguity between normals in the same neighbourhood building a minimum spanning tree with cost 1-|ninj|. We use this part of NE-Hoppe algorithm in our procedure in order to resolve the ambiguity (for details see [1]).

Although the previous algorithms [1,2] work wellin the presence of smooth regions and moderate noise, they performpoorly in those regions near corners or edges. If the neighbourhood at each points has a fixed size and it is constructed usingonly the Euclidean distance then it is possible that pointsconsidered as outliers for a certain region be used in thecomputation of the normal. Figure 2 shows thenormal estimation by different approaches for a step function intwo dimensions. Figure 2a shows the groundtruth and Fig. 2b shows the normalcomputed using neighbourhoods based only in a proximity measure, note theeffect in corners of the step function. On the other hand, Fig.2c, shows the results applying our approach(that will be introduced in next section).

Fig. 1. Different plane estimations using three points on a corner. (a) Plane over the three points and (b) plane over points pi and ph when pj is not included.

Fig.2. Step function normal estimation. (a) Ground Truth, (b) NE-Hoppe algorithm and (c) NENR algorithm

2. Our Approach

In case of a piecewise constant surface, for a given neighborhood,we approximate this surface by TPs and it is desirable to get outpoints of the cloud belonging to different TPs. So a newneighborhood is computed, considering only the nearest neighborswho belong to the same TP. Figure 1a shows thestandard plane estimation, for the case of three points on acorner, and Fig. 1b shows the plane estimation whena point is rejected, a desirable condition in those cases. Wepropose a HQR cost function for this purpose and the indicatorvariable in our case, is used as non-membership term, lij=1 means that the j-th point, in the original neighborhood, it is not in the same TP that i-th point. The OOTP smoothness iscontrolled with the parameters  and. We proposedto compute the surface-normal as the minimization of a constrainedHRQ cost function given by equation (2). The additional constraint imposes a unitary norm to the flat piecewise normal vector mi:

(2)

where ni is the normal vector computed with the NE-Hoppefor someneighborhood size. Then by using the Lagrange multipliers,, we include the constraint in the Lagrangian given by (3):

(3)

Then the solution is computed solving the Karush-Khun-Tucker. Wepropose to use the Gauss-Seidel algorithm, for solving this linearsystem of equation, due the fact that the system of equation has abanded, diagonally dominant and semi-positive defined matrix, sothe t-th Gauss-Seidel Iteration is given by the equations (4)

(4)

3. EXPERIMENTS

We perform experiments in both synthetic and real data, forcomparing NE-Hoppe, Ransac and NENR algorithms for normal estimation. The syntheticdata corresponds to a step function (fig 1),a corner model in 3D,and a 3D model (fig 3), while the real data corresponds to 3D models widely used in the literature (fig 4). All the 3D models were reconstructed using theOhtake's MPUI implementation available at [3].

Table 1 shows the average angle between the ground truth and the normal computed for synthetic data. For this table you can see that NERN up perform the normal estimation by NE-Hoppe and RANSAC. RANSAC presents a variable result due its random nature, in some cases de normal estimation is the worst and in some case is better than NERN.

Figure 3 show the final reconstruction using MPUI. The final reconstruction for NERN is very similar that the ground truth and NE-Hoppe presents some artifacts in borders and corners. Finally figure 4 show a reconstruction using real models NERN and MPUI.

Table 1.Normal estimation angle between ground truth normals and the estimated normals.

Algorithm / Step Function / 3D corner / Synthetic Model
NE-Hoppe / 5.6278 / 8.8843 / 7.65258
NERN / 0.0055 / 3.0548 / 3.1935
RANSAC (best) / 0.0000 / 3.7999 / 2.9032
RANSAC (worst) / 5.6249 / 6.1976 / 6.3870

Fig. 3. Surface reconstruction using MPUI and different

Surface--Normal Estimations

Fig. 4. Surface reconstruction using MPUI and NERN

3. CONCLUSIONS

The NENR algorithm produces a reduction in the neighborhood size,rejecting the neighbors that have large differences. Thiscondition warranties that the neighbors have the same smoothness degree between them. The NERN algorithm was tested using syntheticexamples building with shape discontinuities. The experimentspresented better quantitative and qualitative results using NENRthan NE—Hoppe and RANSAC.

REFERENCES

[1] Hugues Hoppe and Tony DeRose and Tom Duchamp and John McDonald and Werner Stuetzle, “Surface reconstruction from unorganized points”, SIGGRAPH '92: Proceedings of the 19th annual conference on Computer graphics and interactive techniques, (1992).71-78.

[2] M. A. Fischler, R. C. Bolles,“Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography”, Comm. of the ACM, 24, 381-395, (1981)

[3] Yutaka Ohtake and Alexander Belyaev and Marc Alexa and Greg Turk and Hans-Peter Seidel, “Multi-level partition of unity implicits”, SIGGRAPH '03: ACM SIGGRAPH 2003 Papers, (2003), 463-470.