Topograph: An Efficient Graph-Based Framework for Strictly Topology Preserving Image Segmentation

Authors: Laurin Lux, Alexander H Berger, Alexander Weers, Nico Stucki, Daniel Rueckert, Ulrich Bauer, Johannes C. Paetzold
Primary area: learning on graphs and other geometries & topologies
Keywords: Image Segmentation, Topology, Graph

Abstract:
Topological correctness plays a critical role in many image segmentation tasks, yet most networks are trained using pixel-wise loss functions, such as Dice, neglecting topological accuracy. Existing topology-aware methods often lack robust topological guarantees, are limited to specific use cases, or impose high computational costs. 
In this work, we propose a novel, graph-based framework for topologically accurate image segmentation that is both computationally efficient and generally applicable. Our method constructs a component graph that fully encodes the topological information of both the prediction and ground truth, allowing us to efficiently identify topologically critical regions and aggregate a loss based on local neighborhood information. Furthermore, we introduce a strict topological metric capturing the homotopy equivalence between the union and intersection of prediction-label pairs. We formally prove the topological guarantees of our approach and empirically validate its effectiveness on binary and multi-class datasets, demonstrating state-of-the-art performance with up to fivefold faster loss computation compared to persistent homology methods.

Decision: accept (spotlight)
Reviewer scores: 8, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1730641566984

thread_type:
official_review

<thread_object>
creator: reviewer_qvyt

<content>
summary:
The authors present a novel loss and a novel error metric for topology-aware image segmentation. The loss reflects homotopy equivalence between union and intersection of predicted and ground truth-segmentation. It is computed by establishing a component graph on (thickened/thinned) TP, FP, TN and FN components, and identifying "regular" vs non-regular nodes in the graph, where non-regular nodes point to topology-critical, spatially meaningful pixels in the prediction which are then penalised by the loss. Computation is 3-6 times faster than for related works on persistent homology-based losses.

strengths:
The work provides an efficient loss that is nevertheless formally grounded, with strong topological guarantees. A comprehensive evaluation shows its strengths over existing approaches. Rich figures (also in the supplement) greatly facilitate the read.

weaknesses:
-- Some definitions are not comprehensive and some Figures appear to be not in line with the text, making the work hard to grasp (see Questions)
--> fixed post-rebuttal

-- A more thorough discussion of some related work might render the work significantly more insightful (see Questions)
--> fixed post-rebuttal

-- The authors do discuss the 2d nature of the presented approach as a limitation. However, to clearly convey the significance of this limitation, it should be mentioned in this context that their evaluation features some 3d data (evaluated as 2d slices) -- here, imposing a 2d topological loss on slices appears unsuitable / overly strict.

questions:
Re clarity:

-- "Nontrivial" intersection of closures (p. 4 l. 190) needs to be precisely defined (i.e., please provide a formal definition) -- I guess it has to mean "not finite", otherwise there could be edges between TP and TN and the component graph would not be bipartite? This confusion is furthered by Fig. 2 (see below) where such edge is actually present (so does "nontrivial" mean non-empty after all? but how is the comp. graph bipartite then?); Also, the respective edge is not present in Fig. 3. Please clarify.

-- In Fig. 2 (bottom right) the prediction foreground appears double-thickened, while later you settle for double-thickening of ground truth foreground; this causes an edge between intersection and background in Fig. 2 which should not be there and causes confusion; The same edge is also present in Fig. 7.3 -- I do not understand why; Same holds for the edge from the rightmost (thin) FN component to the spurious component in Fig. 7.3, I do not understand why this is there -- shouldn't it go from the FN component directly to the background node? 

Re rel. work:

-- E.g., how is the DIU metric related to the common practice of counting "false split" and "false merge" errors, as commonly done for segmentation problems (cf [1] for one out of many examples where these are evaluated)? Could it be that DIU is the sum of false splits and false merges (at least for dim. 0 features?)? If not, do you see any other relation?

-- A discussion of [1] as related work appears warranted

-- Funke et al. (2018) is listed in rel. work as having a PH-based loss function, but this is not correct? Please discuss in more detail the relation of your work to their loss, which also focuses on topologically critical regions that are spatially correct

[1] https://doi.org/10.1016/j.ymeth.2016.12.013

Minor: 

-- A pointer to Fig. 11 earlier in the text would be very helpful, latest on page 6 line 297 (in addition to pointing to Fig. 3)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745166989

thread_type:
official_review

<thread_object>
creator: reviewer_cmv9

<content>
summary:
This paper presents a method that improves the topological consistency of segmentation while preserving overall performance, like IoU. Besides, a more topologically precise metric is also introduced in this paper.

strengths:
1. The method proposed in this paper demonstrates a better solution for tasks emphasizing topological accuracy. 
2. Besides, a new metric aims at topology consistency is also presented showing it's advantage over previous ones.
3. With a lower asymptotic complexity, the loss introduced in this paper can be computed in linear time which make the loss easy to implement.

weaknesses:
1. The proposed method works well with relatively small datasets and UNet with fewer parameters. My concern is that if we have a larger dataset, can we achieve similar performance with a larger model without the implementation of Topograph?
2. In terms of binarization, this paper suggests that introducing a small random value would be helpful. But could it be beneficial if applied automatic thresholding like Otsu method?
3. In terms of DICE, Topograph seems to have similar performance with other methods. Is that indicating a tradeoff between topological critical pixels and topological irrelevant pixels?

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731136102725

thread_type:
official_review

<thread_object>
creator: reviewer_8zur

<content>
summary:
The authors present a method to address the segmentation problem with a focus on preserving the topology of segmented regions. They also introduce a metric for evaluating the accuracy of the predicted segmentation. The proposed approach consists of several stages: (1) The input image is binarized and overlapped with ground truth segments; (2) A graph is constructed based on this overlapped image; (3) Superpixels are created, with each node in the graph representing a superpixel; (4) A set of misclassified nodes is identified, and nodes that do not impact topological structure are removed; (5) Optimization is performed only on the nodes in this remaining set. The authors evaluate their method on multiple datasets using a range of metrics.

strengths:
The proposed method seems to preserve the topology of segmented regions, addressing a challenge in segmentation tasks.

weaknesses:
The minimization problem formulation is not well-defined (objective function, parameters, and regularization).

questions:
How does the method handle edge cases with the $\alpha$ parameter? Specifically, what is the outcome if $\alpha$ is set to 0 or to a very large value?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731142729036

thread_type:
official_review

<thread_object>
creator: reviewer_u2u3

<content>
summary:
This paper proposes a new loss function, called **Topograph**, for image segmentation, which aims to preserve the topological accuracy of predictions. The authors highlight the importance of **topological correction** in many segmentation tasks, especially in the medical domain where it is crucial for accurate diagnosis and functional analysis. The approach relies on the construction of a component graph that encodes the topological information of both the ground truth and the prediction. 

The main innovations are:
* **A DIU (Discrepancy between Intersection and Union) metric:** This new metric captures topological correctness with strict theoretical guarantees, notably by capturing the homotopy equivalence between the union and the intersection of a label/prediction pair. The DIU metric is more sensitive to fine-grained topological differences than existing metrics such as the Betti number error and the Betti matching error.
* **A graph-based loss function:** This general loss function preserves topology and can be used to train various segmentation networks. It is based on a component graph that combines topological information from the ground truth image and the prediction.
* **Computational Efficiency:** Topograph outperforms existing methods in terms of topological correction of predictions while being efficient in terms of time and resources due to its low asymptotic complexity (O(n α(n))).

strengths:
0. The paper is clearly written and easy to understand. 

1. The paper presents **theoretical guarantees** for Topograph, demonstrating that if their novel introduced loss is zero, then there is homotopy equivalence. This means that Topograph not only guarantees homotopy equivalence between the ground truth and the segmentation, but also between their union and intersection, thus capturing the spatial correspondence of their topological properties.

2. The approach has a lower complexity than persistent-homotopy (PH) based ones, and, experimentally, a faster running time.  

3. Experimental results show that Topograph improves topological accuracy compared to pixel-based loss functions and other topology-preserving approaches, as shown by the best scores on DIU and BM metrics. At the same time, it maintains pixel-level accuracy comparable to the best benchmarks, indicating that there is no trade-off between pixel-level accuracy and topological correctness.

weaknesses:
1. The binarization used in Topograph may result in a loss of topological information compared to PH-based methods. It might be possible to extend the construction of the component graph similarly to what is done with component trees (as defined in mathematical morphology), but it is not straightforward to do so. 

2. The method is currently limited to 2D images. Its extension to 3D images is considered, but I believe it is not obvious to do. The component graph as currently defined is difficult to extend to 3D.

questions:
Although the method demonstrates superior results in 2D, I am not convinced that it will be easy to extend to 3D, and I would like to understand the authors' intuition and thoughts about a 3D extension. The authors may want to discuss some specific challenges they anticipate in extending Topograph to 3D, and to outline potential strategies they are considering to address these challenges.

Regarding the binarization, I am wondering if it is possible to quantify or estimate how much topological information is lost through
the binarization approach compared to PH methods. Is it possible to suggest some strategy that mitigate this information loss while maintaining Topograph computational efficiency advantages?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732529479563

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

We would like to thank you all again for your thorough and helpful reviews; many interesting points were raised, and we genuinely believe our work has improved as a result of your suggestions. As the discussion period is ending soon, we would greatly appreciate the chance to discuss our changes with you and hope you find the time to respond to our rebuttal. If you believe we have already addressed your questions and concerns, we would, of course, appreciate an appropriate adjustment of your scores to reflect this.

Many thanks and best wishes,  
the authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a topology-preserving loss for binary and multi-label image segmentation. Another contribution of this paper is a new metric for topology correctness. All four reviewers gave positive ratings of acceptance for this paper. The loss is technically sound and theoretically justified with a strong guarantee for topology preserving. In practice, using this loss does not introduce much computational overhead and can be beneficial for many segmentation networks and datasets as shown in the experiments. The loss is particularly useful in low-data regimes such as for medical images.
However, qualitative results don't show a significant difference of segmentation between the proposed method and other baselines such as using Dice loss. The AC encourages the authors to identify examples with more obvious improvement in terms of topology in the final version, and also include a discussion of extension to 3D segmentation as mentioned by the reviewer.