Signed distance function | EPFL Graph Search

In mathematics and its applications, the signed distance function (or oriented distance function) is the orthogonal distance of a given point x to the boundary of a set Ω in a metric space, with the sign determined by whether or not x is in the interior of Ω. The function has positive values at points x inside Ω, it decreases in value as x approaches the boundary of Ω where the signed distance function is zero, and it takes negative values outside of Ω. However, the alternative convention is also sometimes taken instead (i.e., negative inside Ω and positive outside). Definition If Ω is a subset of a metric space X with metric d, then the signed distance function f is defined by :f(x) = \begin{cases} d(x, \partial \Omega) & \mbox{if }, x \in \Omega \ -d(x, \partial \Omega) & \mbox{if }, x \in \Omega^c \end{cases} where \partial \Omega denotes the boundary of \Omega. For any

Differentiable Signed Distance Function Rendering

Wenzel Alban Jakob, Sébastien Nicolas Speierer, Delio Aleardo Vicini

Physically-based differentiable rendering has recently emerged as an attractive new technique for solving inverse problems that recover complete 3D scene representations from images. The inversion of shape parameters is of particular interest but also poses severe challenges: shapes are intertwined with visibility, whose discontinuous nature introduces severe bias in computed derivatives unless costly precautions are taken. Shape representations like triangle meshes suffer from additional difficulties, since the continuous optimization of mesh parameters cannot introduce topological changes. One common solution to these difficulties entails representing shapes using signed distance functions (SDFs) and gradually adapting their zero level set during optimization. Previous differentiable rendering of SDFs did not fully account for visibility gradients and required the use of mask or silhouette supervision, or discretization into a triangle mesh. In this article, we show how to extend the commonly used sphere tracing algorithm so that it additionally outputs a reparameterization that provides the means to compute accurate shape parameter derivatives. At a high level, this resembles techniques for differentiable mesh rendering, though we show that the SDF representation admits a particularly efficient reparameterization that outperforms prior work. Our experiments demonstrate the reconstruction of (synthetic) objects without complex regularization or priors, using only a per-pixel RGB loss.

ASSOC COMPUTING MACHINERY2022

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Lingxiao Huang, Jian Li

We study the problem of constructing epsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An epsilon-coreset is a weighted subset S subset of X with weight function w : S -> R->= 0, such that for any k-subset C is an element of X, it holds that Sigma(x is an element of S) w(x).d(z) (x, C) is an element of (1 +/- epsilon) . Sigma(x is an element of X) d(z) (x, C). We present an efficient algorithm that constructs an epsilon-coreset for the (k, z)-clustering problem in M(X, d), where the size of the coreset only depends on the parameters k, z, epsilon and the doubling dimension ddim(M). To the best of our knowledge, this is the first efficient epsilon-coreset construction of size independent of vertical bar X vertical bar for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of M(X, d) and the shattering dimension (or VC-dimension) of the range space induced by the distance d. Such a relation is not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small (1 +/- epsilon)-distortion of the distance function d (the distorted distance is called the smoothed distance function), the shattering dimension can be upper bounded by O(epsilon(-O(ddim(M)))). For the purpose of coreset construction, the above bound does not suffice as it only works for unweighted spaces. Therefore, we introduce the notion of tau-error probabilistic shattering dimension, and prove a (drastically better) upper bound of O(ddim(M).log(1/epsilon)+log log 1/tau) for the probabilistic shattering dimension for weighted doubling metrics. As it turns out, an upper bound for the probabilistic shattering dimension is enough for constructing a small coreset. We believe the new relation between doubling and shattering dimensions is of independent interest and may find other applications. Furthermore, we study robust coresets for (k, z)-clustering with outliers in a doubling metric. We show an improved connection between alpha-approximation and robust coresets. This also leads to improvement upon the previous best known bound of the size of robust coreset for Euclidean space [Feldman and Langberg, STOC 11]. The new bound entails a few new results in clustering and property testing. As another application, we show constant-sized (epsilon, k, z)-centroid sets in doubling metrics can be constructed by extending our coreset construction. Prior to our result, constant-sized centroid sets for general clustering problems were only known for Euclidean spaces. We can apply our centroid set to accelerate the local search algorithm (studied in [Friggstad et al., FOCS 2016]) for the (k, z)-clustering problem in doubling metrics.

IEEE COMPUTER SOC2018

Thalamic nuclei clustering on High Angular Resolution Diffusion Images

Leila Cammoun, Azzurra Grassi, Patric Hagmann, Reto Meuli, Jean-Philippe Thiran

Thalamic nuclei can be distinguished by their characteristic fiber orientations, which influence the diffusion. Fiber orientations are relatively aligned within a nucleus due to the fact that the cerebrocortical striations within a nucleus all target the same region of cortex. The number of thalamic nuclei reported with histological methods varies with the method employed, although most cyto/myeloarchitec stains identify 14 major nuclei. We present a new approach for thalamic nuclei segmentation on High Angular Diffusion Resolution Images (HARDI), performed with a constrained k-means clustering. As described by John D.Carew[1], it is possible to classify HARDI data based on the shape of the diffusion, thanks to the complex information coming from them. Mette R. Wiegell [2] proposed a thalamic nuclei clustering with k- means on diffusion tensor images, using a combination of a voxel distance and a diffusion tensor distance. In the same way, we use the k-mean algorithm with a weighted sum of two distances to cluster the thalamic nuclei on HARDI data.

2008

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Lingxiao Huang, Jian Li

IEEE COMPUTER SOC2018