Scale-Space Feature extraction on Digital Surfaces

Jérémy Levallois1,2, David Coeurjolly1,
and Jacques-Olivier Lachaud2

1-Université de Lyon, CNRS/LIRIS, UMR5205, F-69621, France
2-Université de Savoie, CNRS/LAMA, UMR5127, F-73776, France

\( %%%% If you see this, MathJax wasn't loaded ... \definecolor{myred}{RGB}{231,76,60} \definecolor{mygreen}{RGB}{38,166,115} \definecolor{myblue}{RGB}{38,89,166} \definecolor{mygrey}{RGB}{101,123,131} \definecolor{mynormal}{RGB}{41,128,185} \)

Feature extraction on 3D geometrical objects

Huge litterature... but various definitions.

We will focus on detecting singularities...
... that must be preserved regardless of scale or noise.

Digital data

Snow sans couleur
  • isothetic surface
    (set of pixels/voxels)
  • arithmetical noise

Why digital data ?

→ Direct result of scanners (e.g. X-ray tomography)
Snow mean curv
→ multigrid convergence of estimated quantity

Objectives


Feature extraction :

  • Working on digital data
  • Scale-space approach:
    - robustness to noise
    - scale independent features
  • With geometrical/theoretical interpretation of features

(Selected) State of the Art

Name Technique Selection Classification Scale-Space Usability for digital data

Moment Analysis[1]

(Clarenz et al.)

Threshold

VCM[2][3]

(Mérigot et al.)

\[\frac{\lambda'_2}{\lambda'_1 + \lambda'_2 + \lambda'_3} \] Threshold

Sphere Fitting[4]

(Mellado et al.)

Threshold

Surface Variation[5]

(Pauly et al.)

\[\frac{\lambda_2}{\lambda_1 + \lambda_2 + \lambda_3} \] Threshold

Tensor Voting[6]

(Park et al.)

\[\frac{\lambda_3+\lambda_2}{\lambda_1} \] Threshold

Integral Invariant

Scale-Space Curvature $\frac{d k}{d r}$ Fitting

Spectral approaches[7]

(Song et al.)

Laplacian eigenvalues Threshold

Previously... Digital Curvature Estimators


x
\(x\)
\(A_R(x)\)

x
\(x\)
\(\hat{x}\)
\(\partial\Shape\)
\(\hBd{h} X\)
\(h\)
\(\sharp_n\)
\(\Proj(\hat{x})\)
\(B_{R_d}(\hat{x})\)

Continuous : $ \tilde{\kappa}_{{{R}}}(x) := \frac{3\pi}{2{{R}}} - \frac{3 {\color{myred}A_R(x)}}{{{R}}^3} $

Digital : $\PCurvHat{{{R_d}}}(\hat{x}) := \frac{1}{h} ( \frac{3\pi}{2{{R_d}}} - \frac{3 {\color{myred}\sharp_n}}{{{R_d}}^3})$

Previously... Uniform multigrid convergence of Digital Curvature Estimators

Dimension With radius parameter
($R=kh^{1/3}$)
2d $O(h^{1/3})$
3d mean $O(h^{1/3})$
3d principal $O(h^{1/3})$

⇨ Radius as Scale-Space parameter

$R=4$ $R=7$ $R=10$ $R=12$

$R=14$ $R=17$ $R=20$ $R=25$

$x$
$\Shape$
$R{}_n$
$R_1$
$\ddots$
$R_0$

Scale-Space Curvature based Feature Estimator

Curvature Plot (in logscale)
$\begin{eqnarray} G_{X,x}(R) & := & {\color{myblue}\frac{3 \pi}{2 R} - \frac{3 A(R,x)}{R^3}} + {\color{mygrey}O(R)} \\ & := & {\color{myblue}\kappa_0} + {\color{mygrey}O(R)} \end{eqnarray}$

Intercept : $\kappa_0$

Slope : $0$

$\begin{eqnarray} G_{X,x}(R) & = & {\color{myred}\frac{3}{2} \frac{1}{R} ( \pi - \alpha_0 )}\\ & & + {\color{mygreen}\frac{\kappa_{-} + \kappa_{+}}{6}} + {\color{mygrey}O(R)} \end{eqnarray}$

Intercept : depending to $\alpha_0$

Slope : $-1$

Influence of digitization

For a constant radius $R$, there exists an infinity of curves which lead to the same digitization of $B_R(x)\cap \Shape$:


$\tilde{\kappa}(R) = 0$
$h$
$R$
$1/\kappa{}_{max}$
\[ {\color{myred}\kappa_{max} = \frac{2h}{R^2 + h^2}} \]
For fixed $h$, estimated values $\hat{\kappa}_R \le \kappa_{max}$ are considered as flat zone, or outliers (in the sense that doesn't capture the feature with current radius).

Influence of digitization

Slope : $-2$

Scale-Space Analysis

For each point, for a range of radii:
  1. Plot the scale-space curvature (abs: log of kernel radius, ord: log of mean curvature).
  2. Remove all data is below $\kappa_{max}$ (we can't determine if it is a flat region or too small radius to detect a feature).
  3. Compute the distance to models[1].
  4. We classify the point by choosing the minimal distance. Here we have a smooth surface...


[1]- with Least Square Linear Fitting

Experiments

Smooth
Edge
Flat

Comparisons

Moment Analysis VCM Sphere
Fitting
Surface
Variation
Tensor
Voting
Our
$R_1$ $R_2$ $R_1$ $R_2$

Comparisons

Moment Analysis Our
$R_1$ $R_2$

Conclusion

  • Robust / Stable feature estimation
  • Classification into linear/smooth/singularities parts
  • ... with some theoretical tools and geometrical interpretation

Perspectives

  • Post-treatment
  • Theoretical proofs behind transitions of models

Thank you for your attention.

Web: http://liris.cnrs.fr/jeremy.levallois

GitHub: jlevallois

Twitter: @Karganys


This work will be available (soon) in the open-source library DGtal

Spectral Approaches

Two problems with digital data:
- Huge computational costs
# Surfels : 1 740 509
Matrix size : 1 740 509 x 1 740 509
- We need to correct the metric embedding
Ellipsoidal effect with heat diffusion