Clustering for Surface Reconstruction

Clustering for Surface Reconstruction

Francesco Isgro

DISI - Universita di Genova

sgro@disi.unige.it

www.disi.unige.it/person/IsgroF

Francesca Odone

DISI - Universita di Genova

odone@disi.unige.it

www.disi.unige.it/person/OdoneF

Waqar Saleem

Max-Planck-Institut fЁur Informatik

wsaleem@mpi-sb.mpg.de

www.mpi-sb.mpg.de/?wsaleem

Oliver Schall

Max-Planck-Institut fЁur Informatik

schall@mpi-sb.mpg.de

www.mpi-sb.mpg.de/?schall

Abstract

We consider applications of clustering techniques,

Mean Shift and Self-Organizing

Maps, to surface reconstruction (meshing)

from scattered point data and review

a novel kernel-based clustering method.

Keywords: clustering, meshing, scattered

data

Introduction

Clustering of a set of objects consists of partitioning

the set into groups (clusters) of similar

objects. Clustering is one of the core data mining

techniques. This paper describes an ongoing

joint research between DISI and MPII teams

with AIM@SHAPE project framework 1 on using

clustering techniques for surface reconstruction

from scattered data. The paper consists of

two parts (clusters). In the rst part, we consider

applications of clustering to surface reconstruction

from scattered point data. In the second

part, we briey review an alternative clustering

method which we plan to employ for surface re-

1AIM@SHAPE is a Network of Excellence project

within EU's Sixth Framework Programme. The project

involves research groups from 14 institutions and is

aimed at basic and applied studies of digital shape

modeling.

construction in combination or as an alternative

to the two presented algorithms.

1 Clustering Techniques for

Meshing Scattered Data

While clustering has found successful use in

mesh decimation [20, 18], the predominant surface

applications where clustering is employed

are surface reconstruction [12, 19] and multiresolution

modeling [13, 14, 4]. In this section,

we present two applications of clustering techniques

for surface reconstruction. The rst [22]

is based on kernel density estimation and makes

use of the Mean Shift technique [6, 7, 11] while

the other [15, 21], inspired by Growing Cell

Structures (GCSs) [10], utilizes Self-Organizing

Maps (SOMs) [16] to identify sharp features in

a point cloud.

1.1 Clustering for sparse meshing

Schall et al. [22] propose a clustering method for

sparse surface reconstruction from dense, noisy

surface scattered data. Their approach is inspired

by the kernel density estimation method

(Parzen-window estimation method). The approach

computes for every input point 􀀀
of a

noisy point cloud  􀀀 



􀀀 a local

uncertainty function measuring the contribution

1

of 􀀀
to the smooth surface  which was sampled

by  . After the local functions are combined

to a global uncertainty function, their local

minima are determined using a procedure

similar to the Mean Shift technique [6, 7, 11].

Therefore, a subset of  is chosen as start points

for the gradient-descent like algorithm proposed

in [22]. After a small number of iterations,

the start points converge to local minima of the

global uncertainty function which are aligned on

a smooth surface.

This method can be considered as a clustering

approach as several start points converge to

the same local minimum of the dened global

uncertainty function. As it is not necessary that

several points represent one minimum, one approximation

center is calculated for them using

standard Mean Shift. The clustering starts by

centering