Two Models for Surface Segmentation using the Total Variation of the Normal Vector

This paper proposes a variational approach for surface segmentation on triangular meshes that compares two total variation regularizers, demonstrating that a label-space regularizer yields superior noise removal at the cost of higher computation, which is mitigated by introducing a manifold Newton scheme to efficiently solve the associated Riemannian center of mass problem.

The Gist

Imagine you have a beautiful, complex 3D sculpture made of thousands of tiny triangular tiles (like a digital mosaic). Your goal is to paint this sculpture, but with a twist: you want to group the tiles into smooth, distinct regions based on which way they are facing.

If a tile faces North, it belongs to the "North Group." If it faces East, it belongs to the "East Group." But real-world data is messy. The surface might be bumpy, or the sensors measuring the angles might be slightly off (noise). Some tiles might be pointing slightly North-North-East, making it hard to decide if they belong to the North group or the East group.

This paper is about finding the best way to "paint" these tiles so the final image is clean, smooth, and makes sense, even when the input data is noisy. The authors compare two different "rules" for how to do this painting.

The Two Rules: The "Strict Manager" vs. The "Flexible Guide"

The authors propose two mathematical approaches to solve this problem. Let's call them Rule A and Rule B.

Rule A: The Strict Manager (Assignment Space Total Variation)

Think of this rule as a strict manager who only cares about the labels you give the tiles.

• How it works: The manager has a list of 22 possible colors (labels). If a tile is assigned "Color 1" and its neighbor is "Color 2," the manager charges a penalty. If the neighbor is "Color 3," the manager charges the exact same penalty.
• The Flaw: To the manager, jumping from Color 1 to Color 2 is just as "expensive" as jumping from Color 1 to Color 100. It doesn't matter that Color 1 and Color 2 are actually very similar (like North and North-North-East), while Color 1 and Color 100 are opposites.
• The Result: To save money (minimize the penalty), the manager might skip intermediate colors entirely. It might force a tile to jump straight from "North" to "South" just to avoid the "cost" of using a middle-ground color, even if that middle ground is physically accurate. This can lead to choppy, unnatural boundaries.

Rule B: The Flexible Guide (Label Space Total Variation)

This rule is like a flexible guide who understands the geometry of the world.

• How it works: This guide knows that the labels aren't just a list; they are points on a sphere (like the Earth). The guide measures the actual distance between the directions.
• The Magic: If a tile is pointing North and its neighbor is pointing North-North-East, the guide sees they are very close together. The "penalty" for this small step is tiny. If the neighbor is pointing South, the penalty is huge because the distance is large.
• The Benefit: This allows the guide to use "in-between" colors naturally. It creates smooth transitions in curved areas (like the curve of a sphere) because it doesn't punish small, logical steps. It effectively "smooths out" the noise without erasing the actual shape.

The Catch: It's Harder to Calculate

While Rule B (the Flexible Guide) produces much prettier and more accurate results, it is much harder to compute.

• The Problem: In Rule A, mixing colors is like mixing paint in a bucket (simple math). In Rule B, because the labels are on a sphere, mixing them is like finding the "center of gravity" of a group of people standing on a globe. You can't just add their coordinates; you have to do complex geometry to find the true center point.
• The Solution: The authors realized that calculating this "center of gravity" on a sphere was the slowest part of their computer program. To fix this, they invented a new, super-fast mathematical shortcut (a "Manifold Newton scheme").
  • Analogy: Imagine trying to find the center of a crowd of people on a hill. The old way was to ask everyone to walk a little bit, check the center, and repeat (slow). The new way is like having a GPS that instantly calculates the exact center based on their current positions, skipping the walking around.

What Did They Find?

They tested these rules on two types of 3D shapes: a perfect sphere and a complex mechanical part called a "fandisk."

1. Better Results: Rule B (the Flexible Guide) consistently produced smoother, more accurate segmentation. It was much better at removing "noise" (bumps) in areas where the surface curves smoothly, without losing the details.
2. Robustness: Rule B was less sensitive to the settings. Even if you didn't tune the parameters perfectly, it still worked well. Rule A often failed or produced weird results if the settings weren't perfect.
3. Speed: Initially, Rule B was very slow because of the "center of gravity" math. However, once they applied their new "GPS shortcut" (the Newton scheme), the speed improved dramatically, making it practical for real-world use.

The Bottom Line

If you want to segment a 3D surface based on its direction, don't just treat the directions as a simple list of options. Treat them as points on a sphere.

The authors showed that by respecting the geometry of the directions (Rule B) and using a smart new algorithm to speed up the math, you can get much cleaner, more natural-looking results than the old, simpler methods. It's the difference between a rigid, choppy drawing and a smooth, flowing painting.

Technical Summary

1. Problem Statement

The paper addresses the problem of surface segmentation for 3D surfaces represented by triangular meshes. The goal is to partition a mesh $\Gamma$ into disjoint regions based on the similarity of the surface's unit outer normal vector field ($n$) to a predefined set of label vectors ($g_1, \dots, g_L$) located on the unit sphere $S$.

The segmentation is formulated as a variational problem where an assignment function $\phi: \mathcal{T} \to \Delta$ (mapping triangles to the probability simplex) is optimized. The objective function consists of:

1. Fidelity Term: Measures the geodesic distance (angle) between the triangle's normal and the label vectors.
2. Regularization Term ($R$): Penalizes discontinuities in the assignment to smooth the segmentation and remove noise.

The core challenge is comparing two different approaches to defining this regularization term: one based on the geometry of the assignment space and one based on the geometry of the label space.

2. Methodology

The authors propose and compare two Total Variation (TV) regularizers:

A. Assignment Space Total Variation (A-TV)

• Concept: This is a direct adaptation of image segmentation models (e.g., Lellmann et al., 2009) to surfaces. It penalizes the total variation of the assignment function $\phi$ directly within the probability simplex $\Delta$.
• Metric: Uses the $L_1$ norm distance between assignment vectors on neighboring triangles.
• Limitation: It treats all transitions between labels equally, regardless of the geometric distance between the corresponding label vectors on the sphere. It does not account for the metric structure of the label space.

B. Label Space Total Variation (L-TV)

• Concept: A novel approach for surface segmentation that penalizes the total variation of the Riemannian center of mass of the labels, mapped back to the unit sphere $S$.
• Mechanism:
  • The assignment $\phi_T$ on a triangle represents a mixture of labels.
  • Instead of treating this as a convex combination, the model computes the Riemannian center of mass $m(\phi_T)$ on the sphere $S$ (the point minimizing the sum of squared geodesic distances to the labels weighted by $\phi$).
  • The regularization term penalizes the geodesic distance between the centers of mass of neighboring triangles.
• Advantage: It incorporates the metric structure of the label space. Transitions between "close" labels on the sphere are penalized less than transitions between "distant" labels, allowing for smoother assignments in regions of constant curvature.

C. Numerical Algorithms

To solve the resulting non-smooth optimization problems, the authors employ Split Bregman / ADMM (Alternating Direction Method of Multipliers) iterations.

• For A-TV: The problem is convex and can be solved efficiently using the Chambolle-Pock algorithm, which involves simple projection steps onto the simplex.
• For L-TV: The problem is more complex because the mapping from $\phi$ to the Riemannian center of mass $m(\phi)$ is non-linear. The ADMM scheme introduces auxiliary variables to split the problem into subproblems:
  1. $\phi$-subproblem: A quadratic program (QP) constrained to the simplex. Solved using a specialized two-stage method (Riemannian gradient descent followed by solving a KKT system).
  2. $m$-subproblem: The most computationally expensive step, involving the minimization of a function on the manifold of the sphere.
     • Standard Approach: Riemannian Gradient Descent.
     • Novel Approach: A Manifold Newton Scheme. The authors propose a new Newton method based on vector bundles and dual connections (following Weigl & Schiela, 2024) to solve the Riemannian center of mass subproblem. This method utilizes second-order derivatives of the logarithmic map on the sphere and converges significantly faster than gradient descent.

3. Key Contributions

1. Proposal of L-TV: Introduction of the Label Space Total Variation regularizer for surface segmentation, which explicitly accounts for the Riemannian geometry of the normal vector space (the sphere).
2. Theoretical Comparison: Demonstration that A-TV penalizes "intermediate" label assignments unnecessarily, causing the model to "skip" labels to minimize cost. L-TV avoids this by measuring distance in the label space.
3. Algorithmic Innovation: Development of a Manifold Newton method for solving the Riemannian center of mass subproblem within the ADMM loop. This significantly reduces the computational bottleneck associated with the L-TV model.
4. Comprehensive Numerical Evaluation: A rigorous comparison of A-TV and L-TV on noisy meshes (Unit Sphere and Fandisk) using various label distributions and regularization parameters.

4. Results

The authors tested both models on triangulated surfaces with added Gaussian noise to vertex positions.

• Accuracy: The L-TV model consistently outperformed A-TV in terms of the percentage of correctly labeled triangles and the Rand Index (RI).
  • Unit Sphere Example: L-TV achieved 85.2% correct labeling (RI 0.973) vs. A-TV's 69.4% (RI 0.953) at optimal parameters.
  • Fandisk Example: L-TV achieved 91.4% correct labeling vs. A-TV's 89.6% for non-uniform labels.
• Robustness: L-TV was found to be more robust to the choice of the regularization parameter $\beta$.
  • A-TV tended to "skip" labels (using fewer labels than available) when $\beta$ was large, leading to under-segmentation.
  • L-TV utilized the full set of available labels even with higher regularization, producing smoother and more detailed segmentations in curved regions.
• Computational Cost:
  • L-TV is computationally more expensive than A-TV due to the non-linear subproblems.
  • However, the proposed Manifold Newton method reduced the runtime for the L-TV $m$-subproblem by approximately 50% compared to the Riemannian gradient descent approach (e.g., 1661s vs. 3400s for the sphere mesh).

5. Significance

This paper makes a significant contribution to the field of geometric data analysis and computer vision by:

• Bridging Geometry and Segmentation: It demonstrates that ignoring the metric structure of the feature space (the sphere of normal vectors) leads to suboptimal segmentation results. By respecting the geometry of the label space, L-TV produces more physically meaningful segmentations.
• Advancing Optimization on Manifolds: The development and application of the Manifold Newton scheme for the Riemannian center of mass problem offers a powerful tool for solving similar non-linear optimization problems on manifolds, potentially applicable beyond surface segmentation.
• Practical Utility: The results suggest that for applications requiring high-fidelity segmentation of smooth surfaces (e.g., medical imaging, CAD analysis), the L-TV model, despite higher computational costs, provides superior noise removal and boundary preservation compared to standard assignment-space approaches.