The Four Color Theorem for Cell Instance Segmentation

We sincerely thank the reviewer for the thorough evaluation of our manuscript and the many constructive comments provided. We are also profoundly grateful for your recognition of our proposed method's innovation, theoretical contributions, and experimental design. According to your metioned several minor concerns, we have summarized these into following five points and made one-by-one responses below. We hope our responses further reinforce your confidence in our approach. For your convenience, we have prepared supplementary materials to assist with your review: Supp.

1. Generalizability to Diverse Imaging Modalities

Thank you for your valuable suggestions to improve our experimental comparsions, hence we conducted additional experiments on three challenging cell segmentation datasets to demonstrate broader applicability, including fluorescence image, bright-field image and phase-contrast image, and one natural-scene dataset (PerSense). These four datasets contain many complex, low-contrast, and densely packed objects, as shown in Supp.RG-Fig.1.

At the same time, we add extensive comparison experiments, and the quantitative results are shown in Supp.RG-Tab.1. From the table, we can see that our method shows comparable results across these diverse scenarios. Notably, it achieves AJI scores of 0.834 and 0.822 on the Yeaz-BF and Yeaz-PC datasets. On the PerSense dataset, our method outperforms the second-best method by more than 2%, demonstrating excellent generalization beyond biomedical domains and reinforcing robustness and scalability. Besides, the visualization results in Supp.RG-Fig.2–6 further indicates our FCIS can tackle complex scenario cell segmentation and densely distributed objects segmentation.

2. Effect of Non-Uniqueness in Encoding

As detailed in the main paper and further illustrated in Supp.R1-Fig. 6 and Fig.7, inconsistent color assignments across training batches can cause unstable optimization and fragmented predictions. To resolve this, we introduce an encoding transformation mechanism that includes a "buffer region" in the prediction space. This mechanism maps all variant encodings to a canonical and stable representation. As shown in Supp.R1-Fig.7(a), this transformation significantly improves training convergence.

To further support this claim, we provide visual comparisons in Supp.R1-Fig.7(b). The segmentation results clearly demonstrate that the encoding transformation mechanism eliminates fragmented predictions, which confirms its effectiveness in stabilizing training and enhancing model robustness.

3. Computational Efficiency and Hardware Benchmarks

Thank you for your valuable suggestion regarding hardware dependency in our computational complexity analysis. In the initial submission, we used an NVIDIA A100 GPU to compute parameter quantification and FLOPs. We will clearly state this hardware configuration in the revised manuscript.

4. Theoretical Assumptions and Real-World Applicability

As you rightly pointed out, our method is based on certain assumptions about cell distribution characteristics—such as local clustering and global dispersion, which imply planar distribution and non-cross instances. These assumptions hold in our current setting and ensure the feasibility of constructing a valid four-color adjacency graph. However, as you suggested, extending our method to more complex scenarios that do not meet these assumptions would require further theoretical analysis and algorithmic adaptation. We will continue to explore and refine this direction in our future work.

Thank you again for your insightful and constructive suggestion.

5. Summary and Pseudocode Placement

Thank you for noting the brevity of the summary section. However, due to it is currently not allow to update the main text, we promise to expand the conclusion to better highlight the key contributions, main results, and limitations in a future version.

Meantime, we also appreciate your suggestion to move the pseudocode to the supplementary material to improve the structure and readability of the main paper, and we will revise it accordingly. We appreciate this suggestion, which will help improve the overall presentation of the paper.

Once again, we sincerely thank you for your thoughtful feedback and positive evaluation. We hope the additional experiments, theoretical clarifications, and manuscript revisions have addressed your concerns.

We sincerely thank you for your valuable feedback and the time dedicated to reviewing our manuscript. To better convey our motivations and address your concerns, we have organized our response into five key areas: (1) theoretical contributions, (2) experimental analysis, (3) comparison with recent literature, (4) presentation and minor issues, and (5) other clarifications. For ease of reference, we kindly refer you to our response file: Supp.

1. Theoretical Contributions

Our paper introduces a novel instance segmentation framework based on the four-color theorem, which reformulates the traditionally complex instance segmentation problem as a four-class semantic segmentation task. This simplification leads to more efficient optimization and significantly faster inference than conventional instance-aware methods.

In the submitted manuscript, we present two key theoretical contributions:

• Global Optimality Theory (Line 210): We demonstrate that the greedy algorithm for four-color encoding yields globally optimal results under the constraint of instance non-adjacency.
• Compatibility Theory (Line 291): We prove that any valid four-color encoding can be transformed into a canonical form, ensuring training stability through an encoding transformation mechanism.

Meantime, the full theoretical derivations and proofs are also included in the supplementary material.

In addition, we believe our approach can potentially reshape traditional thinking in instance segmentation. Drawing a parallel to the U-Net architecture, initially proposed for cell tracking and later widely adopted in general computer vision—we envision that our FCIS framework, backed by solid theoretical grounding and practical efficiency, can also generalize to a wide range of high-density instance segmentation tasks beyond the biomedical domain.

2. Experimental Validation and Broader Applicability

We fully agree with your suggestion to demonstrate the broader applicability of our method. To that end, we conduct additional experiments on three challenging cell segmentation datasets and one natural scene dataset. These datasets include various challenging scenarios—irregular shapes, low contrast, and densely packed objects as illustrated in Supp.RG-Fig.1.

From the quantitative results in Supp.RG-Tab.1 and visualizations results in Supp.RG-Figs.2–6, we can see our FCIS consistently delivers strong and competitive performance across all scenarios. For instance, on the Yeaz-BF and Yeaz-PC datasets, we achieve AJI scores of 0.834 and 0.822, respectively, highlighting the model's superior ability to differentiate instances. Moreover, on the PerSense dataset, our method outperforms the second-best approach by more than 2%, clearly demonstrating its robustness and generalization capabilities beyond the medical imaging domain.

3. Comparison with Recent Methods (Un-SAM)

Thank you for highlighting the recent work Un-SAM. Following your suggestion, we included Un-SAM as a baseline in our supplementary experiments shown in Supp.R2-Tab.2. The results show that Un-SAM performs competitively across several datasets and significantly beyond DCAN and DoNet at least 2% in Dice metrics. Besides, we also update the Un-SAM to our manuscript and added proper citations to acknowledge Un-SAM as a significant contribution.

4. Presentation and Minor Issues

We appreciate your thorough reading regarding typographical errors. In response, we carefully revised the manuscript as follows:

• Equation Clarity: All relevant equations have been reviewed and revised for clarity.
• Index Definitions: The roles and ranges of index variables such as $i$ and $j$ have been clearly defined to remove ambiguity.
• Grammar and Style: We corrected all minor grammatical and formatting issues to improve overall readability.

Additionally, we restructuct the performance and complexity tables of the manuscript to enhance readability and facilitate comparisons, which also can be seen from Supp.R2-Tab.2.

5. Clarification on FLOPs vs. FLOPS

To convenience you understand the use of our FLOPs, we explain it as follows:

• FLOPs (floating-point operations) measure the total number of computations required by a model and are used to evaluate algorithmic complexity.
• FLOPS (floating-point operations per second) refer to the computational throughput of the hardware.

In our paper, we specifically use FLOPs as a metric for comparing model inference efficiency. Hence, a lower FLOPs value indicates reduced computational cost and improved efficiency.

Once again, we sincerely appreciate your detailed feedback. We hope the revised results can thoroughly address your concerns about our FCIS. If you have any further questions, we would be more than happy to provide additional clarifications.

We sincerely appreciate the reviewer’s thoughtful and thorough evaluation of our work and your recognition of its methodological and theoretical contributions. To address your concerns regarding real-world applicability, baseline completeness, and so on, we summarize these issues into five points and provide detailed responses as follows. For ease of reference, we kindly refer you to our response file: Supp.

1. Generalization in Complex Scenarios

You are right that cell segmentation models should adapt to real-world challenges. To validate the generalization of FCIS, we conducted additional evaluations on complex cell segmentation datasets (recommended in CellPose 3.0) and natural scenes as shown in Supp.RG-Tab.1, which covers: (1) Irregularly shaped cells (MP6843); (2) Low contrast, densely packed cells (Yeaz-BF, Yeaz-PC), and (3) Natural scenes with dense objects (PerSense).

The quantitative results in Supp.RG-Tab.1 and qualitative visualizations in Fig.2–6 show that our method performs robustly across these datasets, maintaining competitive AJI and DQ scores. For instance, on the Yeaz-BF and Yeaz-PC datasets, we achieve AJI scores of 0.834 and 0.822, respectively, highlighting the model's superior ability to fit complex scenarios.

2. Motivation and Practical Relevance of FCIS

The initial motivation behind our model may differ somewhat from that of CellPose. As a general-purpose cell segmentation model, CellPose has demonstrated remarkable segmentation performance and proven its strong generalization capability. However, when initially employing cell segmentation approach specifically for pathology, we found some new challenges that need to be solved.

• Inference efficiency is critical: As shown in Supp.R3-Fig.8, WSIs comprise tens of thousands of patches. A classical pathology segmentation model, HoVerNet, heavily relies on post-processing and causes computationally expensive (4.59s per patch). In contrast, our method achieves a significantly faster inference speed (0.29s per patch) than HoVerNet.

• Annotation scalability: Expert-annotated cell are costly to scale, hence some semi-supervised (SS) or domain-adaptive (DA) training strategies are necessary to simplify the manual annotation. However, present SS [MMT-PSM, MICCAI] or DA [PDAM, CVPR] frameworks are very complicated shown in Fig.9-10 due to the multi-branch or detection frameworks. Therefore, our method reformulates instance segmentation as a semantic task, which can provide new training paradigm and makes instance segmentation elegant, similar to semantic segmentation.

3. Inclusion of CellPose as a Baseline

We sincerely thank you for pointing out the omission of CellPose. In response,

• We have included CellPose in our experiments (Supp.R3-Tab.3). Results show that while CellPose performs well across many scenarios, significantly beyond previous cell segmentation model, such as DCAN and NucleiSegNet.
• In the revised manuscript, we will explicitly cite the latest version of CellPose (2025, Nature Methods) and expand the Introduction to include a more detailed discussion of its contributions.

4. Clarification on Handling Overlaps and Graph Construction

• Overlapping Instances: In datasets with single-instance-per-pixel annotations (e.g., most cell datasets), our four-color encoding is directly applicable. For datasets where pixels belong to multiple instances (e.g., cervical smear images), a multi-channel prediction mechanism may be more appropriate. This is a promising direction for future work.

• Node Definition in Algorithm 1: In our method, the cell graph is built from ground truth instance annotations, where each connected region (cell) is assigned a unique ID. The vertex set $V$ consists of these labeled cells, and adjacency is determined via edge contact. In scenarios where only binary masks are available, morphological processing (e.g., erosion) can be applied to approximate instance separation before applying our encoding scheme.

5. Literature Citation

To our knowledge, our work is the first to apply four-color encoding to cell instance segmentation in deep learning. While previous image processing works may use coloring heuristics, our method introduces:

• A greedy coloring algorithm with theoretical guarantees
• An encoding transformation strategy that addresses non-uniqueness
• A training pipeline that converts instance segmentation into semantic prediction

Hence, We will enrich the Related Work section to include broader references from graph theory for segmentation.

Once again, we thank you for your valuable feedback and for encouraging us to improve the completeness and clarity of our work. We hope these clarifications and additional results have addressed your concerns, and we welcome any further questions.

We sincerely appreciate your thoughtful feedback, recognition of the novelty of our proposed FCIS based on the four-color theorem, and positive feedback regarding our experimental design and theoretical contributions. According to your mentioned several issues in the Weaknesses, Comments, and Questions sections, we summarize these into the following four points and provide detailed responses one by one. For ease of reference, we kindly refer you to our response file: Supp.

1. How Non-Uniqueness of Encoding Affect Training Convergence

In medical images, cells often form similar spatial patterns, such as chain-like structures. However, due to the non-uniqueness of the four-color (FC) encoding, structurally similar regions may be assigned inconsistent color configurations across different training batches.

As illustrated in Supp.R1 Fig.6, a specific arrangement of adjacent cells may be encoded as “red-green” in batch n. In contrast, in batch n+1, it may appear as “red-blue.” This variation causes the model to receive conflicting signals during training: it may first learn that red borders green, then later that red borders blue. These inconsistencies disrupt the learning process, leading to unstable optimization and even fragmented segmentations during inference.

To resolve this, we introduce an encoding transformation mechanism that includes a " buffer region" in the prediction space. This mechanism maps all variant encodings to a canonical and stable representation, i.e., the greedy FC encoding. As shown in Supp.R1 Fig.7(a), this transformation significantly improves training convergence. Additionally, we provide theoretical support in the main text that the FC encoding is compatible with any other valid encoding strategy, ensuring the stability and correctness of this transformation process.

To further support this claim, we provide visual comparisons in Supp.R1 Fig.7(b). The segmentation results clearly demonstrate that the encoding transformation mechanism eliminates fragmented predictions, which confirms its effectiveness in enhancing model robustness.

2. Extending the Method to More Complex Scenarios

We sincerely appreciate your suggestion to evaluate our method under more complex scenarios. In response, we conduct extensive experiments on four additional datasets that cover challenging conditions: irregular shapes, low-contrast boundaries, and densely packed regions, along with a natural scene dataset, PerSense, containing many tightly clustered objects as shown in Supp.RG-Fig.1.

The quantitative comparisons are shown in Supp.RG-Tab.1, and the corresponding visualization results are presented in Supp.RG-Figs.2–6. From the table, our FCIS achieves the best performance in DQ and PQ metrics across nearly all datasets. This demonstrate that our method generalizes well to diverse and challenging scenarios, maintaining high segmentation accuracy. In addition, the excellent segmentation performance from visualization results can further support the conclusions.

3. Future Directions for Improvement

As you emphasized, evaluating robustness under more complex scenarios is crucial. In response, our new experiments on four diverse datasets further demonstrate the reliability of our approach. Beyond performance, our work is also driven by a practical motivation: reducing inference time complexity.

As discussed in our main text and Supp.R3-Fig.8, while distance-based methods often perform well, they require complex post-processing, making them computationally expensive. This becomes a bottleneck for applications such as whole-slide image (WSI)-level cell segmentation, where a single WSI may contain tens of thousands of patches. Our method eliminates this bottleneck, achieving inference speeds comparable to semantic segmentation—0.29s per patch, versus 0.94s for CellPose and 4.59s for HoverNet. Therefore, in the future, we will expand the method to pathological field to accelerate the analysis efficiency.

Besides, we also note that high-density instance segmentation is a common challenge in domains beyond biomedicine, e.g., natural scene parsing and remote sensing. However, existing methods in these fields often rely on heavy Mask R-CNN architectures. In contrast, our work offers a lightweight and scalable alternative, which will be our explored direction.

4. Other Minor Questions

We thank you for highlighting recent Transformer-based segmentation methods. We will incorporate these works into the related work section of our revised manuscript. Additionally, we will further explore the integration of Transformer modules into our framework to further enhance model performance.

We hope that our responses and the newly added experiments have addressed your concerns. Once again, we sincerely thank you for your thoughtful feedback.