Microscopy volumes often contain hundreds of touching objects: nuclei in embryos, cells in plant tissue, bubbles in foam. One useful way to segment them is to give each object a center and a set of rays, and let the solver choose where each ray crosses the boundary. This builds in star-convexity, the assumption that every point of an object can be seen along a straight line from its center. The same objective also carries a physical rule: two objects may not occupy the same voxel. The ray part is easy to optimize exactly. The no-overlap rule is not. When three or more objects touch in a ring, which happens constantly in dense tissue, the problem becomes "frustrated": no single relabeling makes all the pairwise rules easy at once. Current graph-based methods hand this to QPBO, a relaxation that may leave some voxels undecided. Current deep methods skip the rule and clean up overlaps with heuristic suppression.
We propose a local solver that uses the structure of this particular problem. Flipping the meaning of "inside" for one object turns its no-overlap terms with every neighbor into easy (submodular) terms. At each iteration, we therefore pick a two-coloring of the objects that leaves as few touching pairs as possible on the same side. We flip one color class and solve exactly for everything that coloring makes easy. Only the few remaining same-side contacts are replaced by an upper bound that is tight at the current solution. Every iteration is one max-flow computation, the energy never increases, and every voxel always gets a definite label. Because the coloring changes between iterations, different frustrated contacts are handled exactly at different times. If the contact graph happens to have no odd cycles, the method finds the global optimum in a single cut.
Background and the gap
Some terms first. A binary energy has a pairwise term that is submodular when $E(0,0)+E(1,1)\le E(0,1)+E(1,0)$. Energies built only from such terms are minimized exactly by a single minimum cut (Energy Minimization with Graph Cuts). Local submodular approximation (LSA) handles energies that break this condition. At each step it replaces the offending terms with a tractable surrogate and solves that surrogate by graph cut. There are two versions. LSA-TR linearizes the bad terms inside a trust region, a limit on how many labels may change. LSA-AUX uses a submodular upper bound that touches the true energy at the current solution, which guarantees monotone descent (Submodularization for Binary Pairwise Energies). That paper supplies our core technique, but it studies generic pairwise energies with no geometric structure. The follow-up work showed that static bounds are often loose. It also showed that restricting moves to one direction makes the bound exact for those moves (Adaptive and Move Making Auxiliary Cuts for Binary Pairwise Energies). That is the precedent for our main design choice: choose the move so the surrogate is exact wherever possible. That work was tested on a few nested regions, a liver and its tumors, not on hundreds of touching instances.
Three papers motivate and constrain the proposal. The closest is Sparse Layered Graphs for Multi-Object Segmentation. It builds radial node columns from object centers, adds containment and exclusion constraints between columns, and solves the result with QPBO. It reports globally optimal labels for more than 99.99% of nodes on its nerve volume, with 432 objects segmented in 44 minutes. This result argues against the proposal, and we take it seriously. Axon–myelin nerve packing may simply be nearly bipartite. The contact structure in nuclei and cell tissue is not, and we ask whether QPBO's near-complete labeling survives there.
Multi-object Graph-based Segmentation with Non-overlapping Surfaces enforces non-overlap between deformable meshes through moving separating planes, again with QPBO. It shows that the constraint matters in practice: minimum Dice on simulated cells rose from 0.51 to 0.58. Its planar separators and relaxation solver leave the optimization question open.
K-convexity Shape Priors for Segmentation shows that expanding or contracting one star-convex part while the others stay fixed is a submodular move. That per-object move is the natural simpler competitor to ours, and we treat it as a central baseline rather than as prior art we simply extend.
On the deep-learning side, STARDIST-3D predicts radial distances for 3D star-convex shapes (Star-convex Polyhedra for 3D Object Detection and Segmentation in Microscopy). MultiStar adds an overlap map and overlap-aware suppression (Multistar). Neither method has a joint energy or a hard exclusion rule. We use their outputs to supply centers, per-ray data costs and initialization.
Core Claim
Let $x_{i,r,k}\in\{0,1\}$ indicate that step $k$ along ray $r$ of object $i$ lies inside object $i$. Star-convexity is the ordering $x_{i,r,k+1}\le x_{i,r,k}$, which is submodular. Exclusion adds a penalty $w\,x_a x_b$ whenever nodes $a$ and $b$ of two different objects cover the same voxel. This term is supermodular. Now substitute $y_b=1-x_b$ for every node of object $j$ (a flip). The term becomes $w\,x_a - w\,x_a y_b$, which is submodular, and object $j$'s ray ordering simply reverses direction, so it stays submodular. If both objects are flipped, the term becomes supermodular again.
So for a two-coloring $\sigma$ of the object contact graph, the only hard terms are exclusion terms between same-colored neighbors. We call these frustrated contacts. Each iteration does three things. It chooses $\sigma$ by an approximate weighted max-cut over contacts, weighted by how much each contact is currently "under tension." It flips one color class. It replaces each frustrated term $x_a x_b$ with whichever of $x_a$ or $x_b$ matches the current state, which is a valid upper bound tight at the current solution. The resulting surrogate $A_\sigma(\mathbf{x},\mathbf{x}^t)$ satisfies
$$E(\mathbf{x}^{t+1}) \le A_\sigma(\mathbf{x}^{t+1},\mathbf{x}^t) \le A_\sigma(\mathbf{x}^t,\mathbf{x}^t)=E(\mathbf{x}^t),$$
and it is exact on every contact $\sigma$ separates.
What is new is picking the flip pattern adaptively, per iteration, to minimize how many terms need approximating. Neither prior LSA work nor RC-SLG does this, and it exploits two facts specific to this problem. Star-convex columns stay submodular under flipping. Exclusion is the only source of frustration. As a result, the method searches a strictly larger exact neighborhood than moving one object at a time. Any stationary point of our method is also stationary for single-object moves, but not conversely.
Research Program
We will build the solver on radial column graphs of the RC-SLG type, in 2D and 3D. Data costs come from a STARDIST-style network: per-ray distance likelihoods and object probabilities. The initialization is the network's own polygons after the standard suppression step.
We will study three choices of coloring. The first is a fixed greedy coloring. The second is random bipartitions. The third is tension-weighted max-cut recomputed each iteration. Contact graphs are small, with objects rather than voxels as vertices, so max-cut heuristics cost almost nothing compared with the flow computation.
On the analysis side, we will prove the exactness statement for bipartite contact graphs and the neighborhood-dominance statement over single-object moves. We will then measure empirically how the fraction of frustrated contacts varies with packing density and dimension. A trust-region variant, which linearizes frustrated terms instead of bounding them, will be compared as well.
One extension is optional and secondary: replacing each object by a union of a few star parts, following k-convexity, to handle concave cells. The main claims do not depend on it.
Baselines
The naive reference point is the deep proposal alone. We will train STARDIST-3D on each dataset, apply its standard suppression, and resolve any remaining overlaps by assigning each contested voxel to the higher-probability object. This shows what the energy formulation adds at all. On PARHYALE, the reported accuracy at IoU 0.5 is 0.593 (Star-convex Polyhedra). We will retrain under the same splits rather than copy this number.
The strongest existing solver is QPBO on the identical radial graph with identical data costs, as in RC-SLG (Sparse Layered Graphs). Undecided nodes will be completed first by the default rounding and then by the stronger improve and probe variants, QPBO-I and QPBO-P. Its reported numbers are an F1 of 0.85 on BBBC038v1 and more than 99.99% of nodes labeled on the nerve volume. Beating it means two things: reaching strictly lower final energy at equal wall-clock time on instances where QPBO leaves more than a small fraction of nodes undecided, and matching its energy where it labels essentially everything.
The per-object move baseline expands or contracts one object at a time while all others are held fixed. This move is exact, since exclusion with fixed neighbors reduces to single-node costs, and it mirrors the per-part moves of k-convexity (K-convexity Shape Priors). It will be swept over all objects until convergence under the same time budget.
The generic LSA-AUX baseline applies the bounds of Submodularization for Binary Pairwise Energies, with the adaptive variants from Adaptive and Move Making Auxiliary Cuts, to every exclusion term with no flipping. This is the ablation that isolates our key ingredient: its only difference from our method is the coloring.
On small crops, we will also compute exact optima by exhaustive branch-and-bound. The file reports no MCBC result on these datasets, only its runtime above 2,000 seconds on dtf-chinesechar. This gives the optimality gap directly. All solvers share the graph, the data costs, the initialization and a single-core time budget. Any exclusion or smoothness weights are tuned once per dataset on a validation split and then frozen for every method.
Why not just…?
Why not just use QPBO, since it already labels 99.99% of nodes? On the nerve data this may well be enough. It is the most likely way the proposal fails, and we will not pretend otherwise. Roof duality undecides nodes because of frustrated cycles. Axon–myelin contact may be nearly bipartite, while packed nuclei, meristem cells and foam contain many triangles of touching objects. The synthetic packing sweep described below directly measures QPBO's undecided fraction as odd-cycle density rises. If that fraction stays negligible on real datasets, our contribution shrinks to guaranteed monotone descent and anytime complete labelings, and we will report it that way.
Why not just move one object at a time? This is a serious threat. Each such move is exact, simple and fast. Its weakness is coordination. Two neighbors that should both shift along their shared boundary cannot do so in one step, because each blocks the other. Our flip moves change them jointly and exactly. The per-object baseline under equal time settles whether that matters. If it reaches energy within about 1% of ours and equal segmentation scores across densities, the coloring machinery is not justified.
Why not just use MultiStar or StarDist with better suppression? Feed-forward regression with suppression cannot enforce exact non-overlap, and the non-overlapping-surfaces work shows that exclusion helps precisely where the image signal is weak (Multi-object Graph-based Segmentation). MultiStar reports AP 0.73 against StarDist's 0.62 at threshold 0.4 on DSB-OV (Multistar). But that benchmark contains true overlaps, so hard exclusion is the wrong model there. We use it as a negative control and expect our method to lose on it unless the exclusion is made soft.
Proposed Experiments
The first experiment isolates the optimization question with synthetic packings. We generate 2D and 3D star-convex cell tilings with controlled density and contact-graph odd-girth, plus controllable boundary noise. For every solver we record final energy against time, QPBO's undecided fraction, the gap to exact optima on small crops, and how many iterations our method spends on frustrated contacts.
The decisive check has two parts. As density rises, QPBO's undecided fraction should grow. In the same regime, our method should beat both QPBO with rounding and per-object moves on energy. If neither happens, the premise is wrong.
The second experiment tests whether energy gains become segmentation gains on real data. We use BBBC038v1 (instance F1, against RC-SLG's reported 0.85), PARHYALE and WORM (accuracy at IoU 0.5), the simulated-cell and foam data from the non-overlapping-surfaces work (minimum population Dice, against 0.58), and the Arabidopsis meristem stack. The meristem stack is the densest tiling in the file, and 3D Cellpose reports a mean Dice of 0.883 on its manual gold standard (Robust 3D Cell Segmentation). We will report per-dataset contact-graph statistics alongside accuracy. That way any gain, or its absence, can be traced to how frustrated the instance actually is, rather than to tuning.
References
- What Energy Functions Can Be Minimized via Graph Cuts?
- Submodularization for Binary Pairwise Energies
- Adaptive and Move Making Auxiliary Cuts for Binary Pairwise Energies
- Sparse Layered Graphs for Multi-Object Segmentation
- Multi-object Graph-based Segmentation with Non-overlapping Surfaces
- K-convexity Shape Priors for Segmentation
- Star-convex Polyhedra for 3D Object Detection and Segmentation in Microscopy
- MultiStar: Instance Segmentation of Overlapping Objects with Star-Convex Polygons
- Robust 3d Cell Segmentation: Extending The View Of Cellpose