Update 05/07/2011: Normals Fix & Radius Learning

Introduction

Normals fixes page 1. r radius estimation page 6.

Unify Normals

BSP is very fast but has a percentage of failed unifications at sharper regions, and required
tuning the r radii by remapping the per point r. MST ran for 2 hours but could
not finish. The following explain each improvement to minimize failed
unification.

r limits

nn.r has been scaled down by 0.5, and min
clamped by distance to the kth neighbor (set as degrees=6). Remap changes are
fairly unstable, because larger r unifies irrelevant neighbors. If nn.r is
minimized to 1st neighbor distance, it effectively becomes MST. But distance similarity
alone does not correctly unify neighbors.

k limits

Each unifier can only affect k nearest
ununified neighbors (set as degrees=6). Where k=1 models MST, k limit is a
tradeoff between normals propagation speed versus accuracy. Because corner
points have highly varied neighbors distances, k limit is more stable than r
limits. This also prevents unifiers unifying across two nearby parallel
surfaces (Figure k limits).

Figure k limits. k=Inf (left). k=6 (right). Although BSP takes the same iterations (44), maximum branching unifiers increased from 471 to 515.

 

3.5 Normals Artifact Fix

3.5  Normals Artifact Fix

Under following
tests, parameters are uniform with k=50, r=0.2, and Gaussian distance kernel
(images in folder nn_anisotropic). Figures show a progressive improvement
extended from the randomized anisotropic feature planes [Li10].

Figure norm1. High precision but accuracy shows normals skewing artifact toward any nearby features.	Figure ani3. Processes half the points, but corrupts too many good points because poor confidence points are not the majority, and neighbor points available to fix problematic points should be more than problematic points. Otherwise unstable poor fixes are made.

Figure ani4: Only the 25% quartile fixes only points near corners of poor planar fit. Some normals have less or no skew effect. Due to the fix via neighbor planes, stability is poor.

ani5_nj moved: The residual of pi to plane nj is changed. nj originally is at the mean of the pj neighborhood, however curvature can cause mean to shift off the surface (as used to find kappa), so nj is moved to pj to approximate the surface. Then residuals become more accurate, yielding marked stability without skew. Stability is also due to large k=50. In most papers ([Mitra03],[Kobbelt04]) as curvature increases, k or r is decreased to fit the local feature better. This figure shows uncertainty at corners, because multiple low-residual planes join at pi to compete for best plane, besides the original uncertainty from norm1.

ani6 degree12 (Left), ani6 degree24 (Right): Changing from degree 6,12, to 24 progressively show better stability: more points find an improved plane so the random normals are cleaned. More plane samples, similar with Li10, will logarithmically increase the probability of selecting a suitable candidate. P = 1 – (1-(1-ε)d)M     [Li10], d = 3 dimensions P = 1 – εM           this method Given ε is the portion of outliers in the pi neighborhood with the wrong plane. Assuming ε=0.7, then choosing degrees 6, 12, & 24 yields 0.8824, 0.9862, & 0.9998 respectively. Due to different probability setup and algorithm, Li10 requires a much higher M (200) to reach 0.9958. An apparent issue is ε increases near corner points when including points on neighboring features. If ε=0.99. 400 planes must be tested to reach 0.9820 probability.

ani6 degree24 farnn k 50, ani7 degree48 CU: Previously pj’s are chosen by the farthest points from k=100. Choosing closer pj’s from k=50 respects smaller features, and shows stabililty remains. The few near-corner instability, for example point 418, is due to propagating a point 425 with the best p_confidence and residual_j, with unfortunately the ε=0.99 case. 418 has only neighbors from the worst 25% confidence planes, thus matches are coincidental. There are multiple neighborhood sizes for different uses. Because skewing is caused by outliers in the neighborhood k during normals estimation step, it is inferred a corner feature is r (assume r and k are linked) away from the last skewed normal. Then for a point in the feature to guarantee existence of skewless (only to this feature) neighbors, the anisotropic fix must use r2 > r. For point 418 with 100% skewed neighbors, ε=1.0. To reach ε=0.99, r2 must be at least (100/99)^.5 = 1.0050 times r. A safer goal is set ε=0.7, 30% neighbors may be able to fix pi, then r*(100/70)^.5 = r*1.1952. For k=50 of mean r=0.2324, need to increase at least to k=72 of r=0.2778. An alternative is to iteratively propagate corrected normals toward corners, and update p_confidence and residual_i. This allows smaller k, which may yield more relevant planes. For the single pass method, both low confidence neighbor removal and high degree (sampling) were tested, but removing the worst 25% yielded some wrong normals due lack of relevant planes, and higher degree (eg. 48) only stabilizes more. Also, higher degree that includes nearer noisy points again destabilize normals.

The propagation
derived from [Li10], copies normal from plane to pi directly, so only works if
the surface spanning pi & pj is nearly planar. [Li10] method works because
each pi have M=200 unique random planes. But with residuals calculation of N
neighbors in S point set, the cost is at least O(N*M*S). Residual weighted
normals may be more stable, but requires normals to be unified beforehand.

3.6  Normals Artifact Fix
post-unification

Pre-unified
normals brings relevant normals closer, with 3 significant advantages: allows
the anisotropic fix to adjust normals gradually via weighted residual,
iteration, and smaller neighborhoods, instead of single plane selection (as
limited in [Li10]). Iterative nj, residual, and p_confidence updating converges
the normals in otherwise unstable regions as the very sharp corner shows.

arcs Orig, arcs exact 48 0.01: Original still shows skewing artifact toward features. Exact (1 best plane) is less stable due to copying 1 high-quality but randomly chosen plane nj to ni. Note corner point splays since points are positioned with noise, thus slight changes in neighbors significantly change possible plane selection.

Sigma weight: nj residuals weighted by sigma 0.2, 0.05, 0.01. Wide sigmas are similar to the original, as sigma sharpens the Gaussian kernel (Right), it blends ni more toward the nj’s with best residuals.

Iterations: 0, 1st, 4th iterations show better stability while converging towards the weighted “popular vote” of each pi neighborhood. For the first time the sharp corner (left side) has correct normals propagated in.

Weighted residual, plus distance, & plus normal (all at 4th iteration): Each additional weight type is modulated by respective Gaussian kernels, then the three are combined to maximize inliers for pi. All calculations and iterative updates are done without recalculating SVD planes. New planes for pi are interpolated, as are residuals and confidence values.

The equation, based on the bilateral
filtering concept, combines the three types of pairwise similarities:

α,β,γ Gaussian weighted kernel functions.

a, b constants determine importance of
distance versus residual (both spatial similarities).

Normal can remove
outliers by angular dissimilarity, and prevent sudden pop due to rotating
toward an very different angle. Notice the one minus especially penalizes nj’s
very similar to ni but pointing in opposite direction, since the normals
unification step has already unified relevant points.

Conclusion
& Future Work

        Future
investigations include more robust estimator of neighborhood radius, more
accurate curvature estimator, and possibly geometry segmentation based on these
surface properties. Efficiency and parallelism can also be improved to suit
real-time processing and visualization.

Normals estimation (Left), unification (Right): Even though most normals point outward, detecting suitable local feature size as the small foot and ear tip remain challenges.