💻 computer science

Coupled Optimal Transport with Landmark Constraints

This paper proposes a novel coupled optimal transport framework that integrates landmark-guided deformation fields with cost-driven transport plans through a mutual-consistency constraint, enabling the recovery of geometrically meaningful transformations from sparse annotations while establishing theoretical well-definedness and providing a convergent numerical algorithm for shape matching.

Original authors: Xiang Gu, Jian Sun, Zongben Xu

Published 2026-08-21

📖 4 min read☕ Coffee break read

CC0 1.0

Original authors: Xiang Gu, Jian Sun, Zongben Xu

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine trying to move a pile of sand from one shape to another, like reshaping a mound of sand into a perfect sphere. In the world of mathematics and computer science, this is known as optimal transport. It is a powerful tool used to compare and connect different distributions of data, finding the most efficient way to move mass from a starting point to a destination. Traditionally, this process relies on a simple rule: move the sand along the shortest possible path to minimize the effort or cost. While this works well for simple tasks, it often fails when the shapes represent complex objects, like a human face or a biological organ. In these cases, the shortest geometric path might lead to a semantically wrong result, such as moving the tip of a nose to the tip of an ear because they happen to be close together in space, even though they are completely different parts of the body. The standard method sees only distance, missing the deeper meaning of how the object actually deforms.

To solve this, researchers Xiang Gu, Jian Sun, and Zongben Xu have developed a new framework that combines the efficiency of optimal transport with the precision of human guidance. Their approach, called coupled optimal transport, introduces a small number of annotated landmarks—specific points that a human has marked to show how one part of an object should correspond to another part of a different object. Think of these landmarks as a few trusted signposts that tell the computer, "This point on the left shape must move to this specific point on the right shape." By weaving these few signposts into the mathematical model, the researchers guide the system to find a transformation that is not just the shortest path, but a geometrically meaningful one that respects the true structure of the objects.

The core of their work is a unified model that simultaneously calculates two things: the plan for moving the mass and the field of deformation that describes how the entire shape bends and stretches. In previous methods, these were often treated separately or ignored. Here, the model forces the two to agree with each other. The movement plan must match the overall distribution of mass, while the deformation field must honor the specific landmarks. These two elements are locked together by a consistency rule: if the plan says to move a piece of mass, the deformation field must show that piece moving in a way that matches the landmarks. This creates a feedback loop where the global goal of matching the shapes and the local goal of respecting the landmarks refine each other until a single, coherent solution emerges.

The authors proved that this new model is mathematically sound and that a solution always exists under reasonable conditions. They also showed that the model behaves correctly at the extremes: if the landmarks are ignored, the system reverts to the standard cost-minimizing method, and if the cost is ignored, it relies entirely on the landmarks. To test their theory, they built a numerical algorithm based on finite elements, a technique that breaks a continuous shape into a grid of small pieces to solve complex equations. They ran extensive simulations using synthetic fish-shaped distributions where the true deformation was known. In these tests, their method consistently outperformed existing approaches. When only a few landmarks were available, the new method recovered the deformation field with high accuracy, whereas methods relying solely on landmarks failed to capture the global shape, and methods relying solely on distance failed to respect the local details.

The researchers further validated their approach with real-world data, using images of handwritten digits. In these experiments, they manually marked just two pairs of points to guide the transformation between different numbers. The results showed that their coupled method produced smooth, logical deformation fields that preserved the structure of the digits, while other methods produced warped or irregular results that did not make sense visually. The study demonstrates that by integrating sparse geometric supervision with global distribution matching, it is possible to recover complex transformations that were previously difficult to identify. This work offers a principled way to bridge the gap between simple distance-based matching and the need for semantically correct shape transformations, providing a robust tool for applications in image registration, shape analysis, and biological modeling.

Technical Summary: Coupled Optimal Transport with Landmark Constraints

Problem Statement
Existing Optimal Transport (OT) models primarily seek a transport map or plan that minimizes a prescribed transport cost or distortion between two probability distributions. While effective for distributional matching, minimizing cost alone often fails to identify geometrically meaningful transformations. For instance, in image or shape registration, a cost-driven map may move mass along geometrically short paths that are semantically incorrect (e.g., matching different anatomical parts). Conversely, methods relying solely on sparse annotated landmarks often fail to capture the global distributional transition or the underlying deformation field governing the change. The paper addresses the challenge of recovering a coherent deformation field that satisfies both global distributional alignment and local geometric constraints provided by sparse landmarks.

Methodology
The authors propose a novel Coupled Optimal Transport (COT) framework that unifies the optimization of the transport plan and the estimation of a deformation field.

Model Formulation: The framework introduces a deformation-based view of transport. Let $u: \Omega \to \mathbb{R}^p$ be a deformation field and $T_u = \text{Id} + u$ be the associated transport map. Given a set of annotated landmark pairs $S = \{(x_i, y_i)\}_{i=1}^m$ , the model minimizes a functional $F(\pi, u)$ over the set of couplings $\Pi(\mu, \nu)$ and a Sobolev space of deformation fields $U$ :
$\inf_{\pi \in \Pi(\mu, \nu), u \in U} F(\pi, u)$
The functional consists of three main components:
1. Coupled Transport Cost: A weighted combination of the classical transport cost $c(x, y)$ and a deformation-consistency penalty $h(T_u(x) - y)$ . This term ensures that the transport plan $\pi$ is consistent with the deformation field $u$ .
2. Landmark Supervision: A term $\sum w_i \rho(A_i^r(u) - \Delta_i^{lm})$ that penalizes the discrepancy between the observed landmark displacements and the deformation field's local average (via an observation operator $A_i^r$ ).
3. Regularization: An elastic energy term $E_{el}(u)$ (linear elastic energy) to promote spatial coherence and smoothness of the deformation field, facilitating the propagation of sparse landmark information across the domain.
Theoretical Properties:
- Well-posedness: The authors establish the existence of a minimizer $(\pi^\star, u^\star)$ under mild conditions (e.g., absolute continuity of $\mu$ , coercivity of the elastic energy).
- Limiting Behavior: The model is analyzed as the balancing parameter $\alpha \to 1$ (deformation-dominated) and $\alpha \to 0$ (cost-dominated). As $\alpha \to 0$ , the model recovers a decoupled problem where the transport plan minimizes cost and the deformation minimizes landmark loss independently, with the coupling term acting as a selection criterion among decoupled minimizers.
- Proposition 2.1: Under squared Euclidean cost, the coupled problem is shown to be equivalent to minimizing a functional involving the Wasserstein distance between the target measure and the pushforward of the source measure by a relaxed deformation map, plus regularization terms.
Numerical Algorithm:
- Discretization: The authors employ a finite-element method (FEM) for the deformation field using continuous tensor-product $Q_1$ elements. The measures are discretized as weighted atomic measures.
- Alternating Iteration: The solution is computed via an alternating scheme:
  1. Transport Update: Fixing $u$ , the transport plan is updated using a Sinkhorn-like iteration with an entropic or Bregman-type regularization (KL-divergence) to handle the marginal constraints.
  2. Deformation Update: Fixing $\pi$ , the deformation coefficients are updated by solving a linear system derived from the first-order optimality conditions (due to quadratic choices of $h$ and $\rho$ ).
- Convergence: Theoretical analysis proves that the sequence of iterates is bounded, the objective value decreases monotonically, and the differences between successive iterates vanish. For the entropy-regularized variant, the sequence is shown to converge to a constrained critical point.

Key Contributions

Novel Framework: The proposal of a unified coupled OT model that integrates transport plan optimization and deformation field estimation, bridging landmark-based registration and transport-based distribution matching.
Theoretical Foundation: Establishment of the well-definedness of the model in a general variational setting and characterization of its relationship to classical OT through limiting analysis.
Algorithmic Development: Development of a finite-element-based numerical algorithm with systematic convergence analysis, including both KL-proximal and entropy-regularized variants.
Sparse Supervision: Demonstration of the ability to recover dense, geometrically meaningful deformation fields from sparse landmark supervision combined with global distribution matching.

Experimental Results
The effectiveness of the proposed method was verified through two types of experiments:

Synthetic Experiments: Using fish-shaped distributions with known ground-truth deformation fields.
- Metrics: Deformation error ( $L_2$ ), held-out landmark error, and density error ( $L_1$ ).
- Findings: The COT method (both KL-proximal and entropy variants) consistently outperformed "OT (barycentric)" (which lacks landmark constraints) and "Landmark-only" (which lacks global distribution constraints), particularly in the sparse-landmark regime. The method successfully recovered the ground-truth deformation with lower error as the number of landmarks increased. Convergence of the objective function and iterates was observed, aligning with theoretical predictions.
Real Shape Matching: Applied to handwritten digit images (MNIST) with manually specified landmarks.
- Findings: Compared to baselines, COT produced deformation fields that were spatially coherent and consistent with the prescribed landmark correspondences. While "OT (barycentric)" captured global distribution but produced irregular fields, and "Landmark-only" produced smooth fields only near landmarks, COT successfully propagated both distributional and landmark information across the entire source support.

Significance and Claims
The paper claims that the proposed framework provides a principled connection between landmark-based registration and transport-based distribution matching. By coupling the transport plan and deformation field through a mutual-consistency constraint, the method enables the recovery of transport maps from sparse geometric supervision. The authors assert that this approach overcomes the limitations of minimizing transport cost alone (which may yield semantically incorrect paths) and relying solely on sparse landmarks (which may fail to capture global deformation). The work establishes the theoretical validity of the model and demonstrates its practical utility in shape matching tasks, offering a robust solution for applications requiring geometrically meaningful distribution transformations.

The authors modestly note that while the framework is general, the current numerical implementation is designed for low-dimensional spatial domains. They identify the development of methods for high-dimensional and large-scale problems (potentially using neural network parameterizations) as a direction for future research.

More like this