The Four Color Theorem for Cell Instance Segmentation
Authors: Ye Zhang
Yu Zhou
Yifeng Wang
Jun Xiao
Ziyue Wang
Yongbing Zhang
Jianxu Chen
Venue: ICML 2025 poster (2025)
Keywords: Cell instance segmentation
Four color theorem
Primary area: applications->computer_vision

Abstract: Cell instance segmentation is critical to analyzing biomedical images, yet accurately distinguishing tightly touching cells remains a persistent challenge. Existing instance segmentation frameworks, including detection-based, contour-based, and distance mapping-based approaches, have made significant progress, but balancing model performance with computational efficiency remains an open problem. In this paper, we propose a novel cell instance segmentation method inspired by the four-color theorem. By conceptualizing cells as countries and tissues as oceans, we introduce a four-color encoding scheme that ensures adjacent instances receive distinct labels. This reformulation transforms instance segmentation into a constrained semantic segmentation problem with only four predicted classes, substantially simplifying the instance differentiation process. To solve the training instability caused by the non-uniqueness of four-color encoding, we design an asymptotic training strategy and encoding transformation method. Extensive experiments on various modes demonstrate our approach achieves state-of-the-art performance. The code is available at https://github.com/zhangye-zoe/FCIS.

The Four Color Theorem for Cell Instance Segmentation
Ye Zhang"
Yu Zhou Yifeng Wang?,
Jun Xiao
Ziyue Wang*
Yongbing Zhang
Jianxu Chen
Abstract
Microscope
Detection
Segmentation
GT Label
Non- Non-maxima
Cell instance segmentation is critical to analyz- ing biomedical images, yet accurately distinguish- ing tightly touching cells remains a persistent challenge. Existing instance segmentation frame- works, including detection-based contour-based, and distance mapping-based approaches, have made significant progress, but balancing model performance with computational efficiency re- mains open problem. In this paper, we pro- pose novel cell instance segmentation method inspired by the four-color theorem. By concep- tualizing cells as countries and tissues as oceans, we introduce four-color encoding scheme that ensures adjacent instances receive distinct labels. This reformulation transforms instance segmen- tation into a constrained semantic segmentation problem with only four predicted classes, sub- stantially simplifying the instance differentiation process. To solve the training instability caused by the non-uniqueness of four-color encoding, we de- sign an asymptotic training strategy and encoding transformation method. Extensive experiments on various modes demonstrate our approach achieves -fate-of-the--e of-thh---ttttttt performance. The code is avail- able at
Suppressio
(a) Detection- bbsed Method
Pathology
Prob
Contour Prediction
true con.
LD
Probability
p-0.5
p=0.6
0.0
(b) Contour Prediction Method
Fluorescence Hor. distance
Edge gradient
Prediction
Post
Precessing
(c) Distance Mapping Method
Figure I. Existing cell instance segmentation frameworks. (a) rep- resents the detection- based method, which cannot tackle elongated cells. (b) represents the contour prediction methods influenced by threshold value choice. (c) represents the distance mapping meth- ods, which contains multiple tasks and relies on a post-processing process. The Red "x" indicates the segmentation mistakes.
(Cords et al., 2023; Zhang et al., 2025b), and cell track- ing (Merryweather et al., 2021), but also underpins critical applications in clinical diagnostics, such as immune mi- croenvironment analysis (Barkley et al., 2022; Kao et al., 2022) and biomarker discovery (Mann et al., 2021).
At present, cell instance segmentation models can be cate- gorized into three primary approaches: (a) detection based methods (Jiang et al., 2023), which rely on object detection frameworks (Ren al., 2016) to localize and delineate in- dividual cells; (b) contour prediction methods (Chen et al., 2016), which explicitly predict cell boundaries to achieve instance differentiation; and (c) distance mapping methods (Graham et al., 2019; He et al., 2021), which encode spatial relationships or distance information to separate adjacent cells. Despite their demonstrated success in cell instance segmentation tasks, existing methods face critical limita- tions due the inherent diversity of cell morphologies and image characteristies across different scenarios, which im- pose stringent demands model generalization.
1. Introduction
Cell-level analysis tasks hold broad application prospects in the biomedical field. Accurate cell segmentation (Petukhov al., 2022; Zhang al., 2025a: Chen al., 2024) not only provides necessary foundation for downstream tasks such cell counting (Falk al., 2019), cell classification
Schooo of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), China J.cibniz-Institut für Analytis- che Wissenschaften - ISAS V. Germany "School of Science, Harbin Institute of Technology (Shenzhen). China 'Department of Electrical and Computer Engineering, National University of Singapore, Singapore. Correspondence to: Yongbing Zhang <ybzhang08@ @ hit.edu.cn.>, Jianxu Chen <jjanxu.chenee @ de?.
For different segmentation methods, their problems include the following aspects, as shown in Figure 1. First, detection- based methods often struggle with complex cases such as
Proceedings of the 4 International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Four Color Theorem for Cell Instance Segmentation
Map
Cell Image
Non-unique Encoding
color representation, ensuring consistency by removing am- biguity in encoding variations. In addition, we provide theoretical analysis to prove the reasonability of the designs.
In summary, the contributions of this paper are five folds:
Figure 2. Our proposed cell encoding method is based on the four- color theorem. In the method, each cell is viewed as "country," " and the encoding ensures that adjacent cells have different colors.
We propose an innovative cell segmentation method based on the four-color theorem, which transforms in- stance segmentation into a semantic segmentation task, eliminating complex instance differentiation designs.
elongated fibroblasts or overlapping cells, leading to fre- quently missed detections. Second, contour prediction meth- ods attempt to achieve instance separation by introducing an additional contour category. However, their performance heavily depends on the contour threshold setting. Lastly, distance mapping methods rely on highly intricate network architectures and sophisticated post-procs proteprocsssing workflows, which significantly increase computational overhead and model complexity. Therefore, it is imperative to develop an innovative approach that can address the shorteomings of current methods by enhancing robustness, reducing computational complexity, and improving generalization across diverse biomedical image modes.
We design an asymptotic training strategy incorporat- ing foreground prediction transformation module, greatly enhancing training stability and robustness.
We systematically summarize the characteristies of cell distributions in medical images, demonstrating that cell coloring is inherently simpler than map coloring.
We provide a rigorous theoretical analysis to justify the rationale and feasibility of the proposed model design.
We validate the effectiveness of our method on three distinct types of medical image datasets. The results show that our method successfully balances perfor- mance and model complexity.
The four-color theorem (Fritsch et al., 1998) offers a novel perspective on cell instance segmentation. As shown map in Figure 2, the theorem states that only four colors are suf- ficient to ensure that adjacent regions are assigned distinct colors (Gonthier et al., 2008). By drawing analogy to cell images, we conceptualize each cell instance as a "coun- try," while the background corresponds to the "ocean." " This enables the development of a four-color encoding scheme that assigns unique encodings to adjacent cells. Under this framework, the instance segmentation task reformulated as a four-class semantic segmentation problem, simplify- ing instance differentiation. However, the inherent non- uniqueness of four-color encodings and the class imbalance introduced by the encoding strategy pose significant chal- lenges for model training. Directly using these encodings as supervision can lead to training instability and hinder optimization. Therefore, a well-designed training strategy essential address the training problem effectively.
2. Complexity Analysis of Model Training
The advancement of deep learning revolutionizes automated cell segmentation, significantly reducing the time and effort required for manual annotation (Stringer et al., 2021; Pa- chitariu & Stringer, 2022; Zhang et al., 2025c). Although existing approaches show impressive performance, they are difficult to fit in various segmentation scenes and face chal- lenges regarding training complexity and post-processing requirements. To facilitate comprehensive comparison of existing methods, we summarize the computational com- plexity of the above three types of models. At the same time, the Supplementary Material provides more extensive research of related works.
Detection- Methods
To address the above challenges, we propose an asymptotic training architecture. Different from traditional semantic segmentation methods (Wang et al., 2018; Zhou et al., 2022), which adopt simultaneous multi-class, multi-channel out- put strategies, our method adopts a step-by-step approach: first distinguish foreground and background and then make category prediction within the foreground region. Our ap- proach prioritizes high-level spatial information over fine- grained semantic details by imposing orthogonal constraints on adjacent cells, effectively solving the class imbalance problem. To mitigate the training instability caused by the non-uniqueness of the encoding, we introduce an encoding transformation method that maps the output to a minimum
The overlapping boundaries of cells remain a critical chal- lenge in cell segmentation. Detection- methods ad- dress this issue through a two-stage strategy: first a detec- tion network (Ren et al., 2016; Redmon & Farhadi, 2017) localizes cell positions; then, segmentation predictions are generated based on the detection results. Representative methods include IRNet (Zhou et al., 2020), and DoNet (Jiang et al., 2023). To enhance localization accuracy, these methods commonly incorporate non- maximum suppression (NMS) to merge highly overlapping detection boxes, thereby reducing over per-prreittion. However, this strategy can result in missed detections, particularly for small or irregularly
2

---

The Four Color Theorem for Cell Instance Segmentation
shaped cells. Additionally, detection-basee approaches of- ten exhibit high computational complexity due to the intri- cate detection and segmentation network designs. As shown in Table 1, these methods typically have higher parameter complexity and computational overhead regarding FLOPPs.
Methods
Paras
#FLOPs
Publication
Detection based methods
Mack-RCNN (He al., 2017)
44.66
411.61
ICCV
DoNet (Jiang et al., 2023)
67.71
221.64
CVPR
Contour prediction methods
UNet (Roaneberger et al., 2015)
32.14
64.27 G
MICCAL
Contour Prediction Methods
DCAN (Chen al., 2016)
41.16 M
77,82 G
CVPR
CNN? (Kumar et al., 2017)
65.46
1.06
Contour prediction-basee methods achieve instance differ- entiation by introducing contour semantic categories into the model's predictions. However, due to the few pixels in the contour, the segmentation for contours is often inferior to that for the background and foreground. To address this issue, two solutions are proposed. The first solution, rep- resented by UNet (Ronneberger et al., 2015; Zhou et al., 2018), increases the loss weight of boundary to guide the model to focus more on contour. With relatively simple structural designs, these methods typically have lower pa- rameter counts and computational complexity, as shown in Table 1. However, their performance remains suboptimal, constrained by the limited effectiveness of the loss weight- ing strategy. The second solution, represented by Micro-Net (Raza et al., 2019), enhances contextual perception by in- troducing complex network structures (Zhou et al., 2019), such multi-scale feature fusion (Srivastava et al., 2021) and attention mechanisms (Prangemeier et al., 2020; Hörst et al., 2024). While this approach significantly improves performance compared to the former, including complex modules substantially increases model complexity, resulting in longer training times and higher computational costs.
UNet++ (Zhou et al., 2018)
9.28 M
35.61 G
MICCAL
FullNet (Qu al., 2019)
112.60 M
G16.92
MICCAL
Micro Net (Raza et al., 2019)
89.64
72.96 G
MIA
NucleiSegNet (Lal al., 2021)
12.40
G
CBM
TSFD-Net (Ilyas ot al., 2022)
21.96
12.10
GeNSey Net (Xu et al., 2024)
87.11 M
86.84 G
MM
Distance mapping methods
StarDist (Schmidt et al., 2018)
21.43 M
92.40 G
MICCAI
HoverNet((rahann al., 2019)
49.70
192.70
CDNet (He et al., 2021)
70.55 M
G
ICCV
SONNET (Doan al., 2022)
63.87
166.75
JBHT
TransUNNet (He et al., 2023)
112.21 M
37.67 G
MICCAL
CPP-Net (Chen al., 2023)
80.75 M
163.10
TIP
SMILE (Pan et al., 2023)
53.85
68.58 G
NuSEA (Meng et al., 2024)
55.26 M
74.20 G
JBHI
CellVIT (Hoest et al., 2024)
96.81
124.25
MIA
RepSNet (Xiong et al., 2025)
28.20 M
137.11
UCC
Our four-color theorem based method
FCIS (Ours)
39.75 M
58.03 G
Table 1. The computational complexity and number of parameters comparisons. All the methods are reported for 256 256 inputs.
Distance Mapping Methods
proach achieves substantial advantages in both parameter efficiency and computational cost compared detection- based and distance- segmentation methods.
Distance-based cell segmentation methods, such StarDist (Schmidt et al., 2018), CelIViT (Hörst et al., 2024), and RepSNet (Xiong et al., 2025), utilize distance maps to en- hance instance differentiation, especially in cases involving irregular cell shapes or densely packed regions. While these methods have shown significant success, they typically rely on multiple decoding branches that require post- post-procsssing (Graham et al., 2019; Chen et al., 2023; Meng et al., 2024) to merge the results into accurate instance segmentations. This multi-branch design increases model complexity, as the net- work must simultaneously handle various tasks, including distance map prediction and semantic category classifica- tion. As shown in Table I, distance-based methods generally exhibit higher parameter complexity and computational cost than detection- baased and contour prediction methods, limit- ing their efficiency for large-scale applications.
3. Cell Encoding by Four Color Theorem
3.1. Greedy Algorithm for Encoding
The four-color theorem illustrates the minimum color num- ber required to label adjacent regions without overlap, pro- viding a novel approach to the cell instance segmentation problem. Unlike traditional instance segmentation work- flows, this method transforms the instance segmentation task into multi-class semantic segmentation problem. Based on this theory, we designed greedy algorithm to gener- ate four-class encoded representations for the foreground regions. The encoding process is illustrated in Algorithm 1.
We first preprocess the input image and its corresponding labels (X, Y) construct cell graph G = (V, E),, where the node set V {u; i 1.... N) represents the cells in the image, and the edge set E = (ei.j) represents the adjacency relationships between cells. The label Y contains instance-level annotations, with each instance uniquely iden- tified by an identification, while ei, indicates that cells v; and fy are adjacent. Next, we assign color encodings to
The tou-collr-theorem introduces a novel cell instance seg- mentation paradigm that eliminates the dedicated instance differentiation modules. This method significantly reduces training complexity by reformulating the instance segmenta- tion task semantic segmentation problem. Furthermore, experimental results in Table demonstrate that this ap-
3

---

The Four Color Theorem for Cell Instance Segmentation
n=1
n=2
n=3
n=4
(a) Substitution:
The color of a cell is replaced with another color while maintaining the same number of colors.
Idi1
id:1
id:2
id:2
id:1
id:1
idi3
18:3
id:2
(b) Exchange: The color assignments between two or more cells are swapped, preserving the overall color count.
Graph relation:
(c) Rule Modification: Certain cells are assigned new col- ors, resulting in an increase in the total number of colors.
Cell encoding:
Algorithm Cell Encoding by Greedy Algorithm
1: Input: Cell graph G = (V. where V is the set of cells and E represents adjacency relation.
Substitution
(b) Exchange
[c) modification
Figure 3.
The non-uniqueness of four color encoding can sum- marized as the following three cases: (a) Encoding substitution;
2: Output: Four-color encoded mask C(v).
3: Initialize color set C = {1, 3, 43.
(b) Encoding exchange, and (c) Encoding rule modification.
4: Initialize mask C(v) + 0, Vu V.
the nodes V E V using a greedy algorithm. Specifically, for each node v, we first compute its set of neighboring nodes (N))= = {u (v, u) E} and collect the colors Cased already assigned to these neighboring nodes follows:
for each nucleus E do
Get the set of neighbors: N(e) {u (v, u) E E}.
7: Collect used colors: Cused (C(u)
N (v), C(u) * 0}.
8: Assign the smallest available color:
Cused {C(u) u N()), C(u) + 0}
(1)
9: C(v) 4 min(C \ Cueed).
10: end for
We assign the smallest available color from the four color set C {1, 2, 3, 4] to the current node v, ensuring that it does not conflict with the colors of its neighboring nodes:
11: Generate segmentation mask M:
12: for each pixel p in the image do
13: Assign pixel p to the color of the cell it belongs to:
14: MP) + C(u), where is the cell containing p.
C(v)= = min(C)) \\ Cusea).
(2)
15: end for
16: Return M (Four-color annotation mask)
This process guarantees that two adjacent nodes o; and vy are assigned different colors, i.e., C(u,) # C(u,). After encoding all cells, generate the final segmentation mask M. For each pixel p in the image, if the pixel belongs specific nucleus v, it is assigned the color encoding C(u) corresponding to that nucleus. The final output segmenta- tion mask M provides a four class semantic segmentation representation based on the four color theorem.
Segmentation networks typically learn semantic categories based on the object's 's morphological and textural features (Jain et al., 2023), while four-color encoding emphasizes the spatial relationships between cells. When faced with the issue of encoding non-uniqueness, conventional networks often struggle to converge stably (Ronneberger et al., 2015). To propose reasonable solution, we further analyze the characteristics of the greedy algorithm in the next section.
3.2. Non-uniqueness Property of Encoding
While four-color encoding ensures heterogeneity of adja- cent cell colors, its non non-uniqueness may lead to convergence issues during model training. To illustrate the potential prob- lems of this encoding more intuitively, Figure presents the differences in cell encoding under various distribution sce- narios. The first row shows the spatial relationships between cells, and the second row represents the corresponding cell graph structures, which cover the most common cell distri- bution scenarios. Combinations of these basic patterns can represent more complex cell distributions. Moreover, the third row illustrates encoding representations. In detail, the cells marked in red represent the initial encoding generated by the greedy algorithm. In contrast, the cells marked in black correspond to the equivalent encoding that satisfies the four-color theorem. The differences between the greedy algorithm's ' results and the equivalent encoding contain the following three cases:
3.3. Low-rank Property of Greedy Encoding
Greedy algorithms (GAs), as heuristic methods, are com- monly used to generate locally optimal solutions. However, in the cell coloring problem, GAs achieve globally opti- mal solutions. The reasons for this are twofold: First, the cells usually exhibit global dispersion and local aggregation, with a relatively small number of cells each cluster, which differs from the distribution of countries. Second, adjacent cells in the image usually follow a chain-like or rectangular arrangement. Hence, each cell has much fewer neighbors. These structural properties render the cell coloring problem more straightforward than the map coloring problem.
To clarify the above fact, we statistics the number of colors distributed on each image under four-color encoding in Figure 4. The scatter plot on the left corresponds to each sample, and the box plot shows the distribution of encoding

---

The Four Color Theorem for Cell Instance Segmentation
Binary Classification Semantic Prediction
enc-1
80
enc=1
enc-2
enc=2
60
enc-3
Given an input image X,, encoder-decoder network is employed to generate five-channel feature map Y; E R where H and W are the height and width of input. Among these channels, the first represents the back- ground probability, and the remaining four represent the prediction of the four-color encoding, Hence, the probabil- ity map of background Yú is extracted follows:
20
0
(a) DSB2018
(b) PanNuke
Figure 4. Statistics of the number of cells with different color in the DSB2018 and PanNuke datasets.
y8 Y, 0},
numbers. The results demonstrate that only a tiny proportion of images require more than two colors and almost no image requires four colors. Based on these, we will present the global optimal theory of greedy algorithm coloring.
where Yi 0] denotes the first channel of the prediction fea- ture map. For obtaining the foreground probability, convolution operation transform the last four channels into single-channel foreground probability:
Theorem 1. Global Optimality of Greedy Coloring: Let == EV, be an undirected graph; among them, V is the set of vertices, and E is the set of edges. Suppose G satisfies the following conditions:
Yj Conv Conv(Vi(: 1 5)),
(6)
where Conv(.) represents convolutional layers. Combined the probility maps of background Y, and foreground Y,, the binary semantic prediction can be formulated as:
(I) G is planar, meaning it can be embedded in the plane without any edges crossing each other.
Yo.i = CoCCat 8,),
(2) The maximum degree of G, denoted AG)), satisfies:
where Concat(-;) denotes the concatenation operation along the channel dimension. To optimize the binary seman- tic predictions, we define the semantic loss as:
A(G) S k. where $ 4.
(3)
(3) The vertex distribution of G follows specific structure, either a chain structure (vertices are ordered linearly) or a rectangular structure (vertices are arranged in grid pattern).
Lyem CE(Ý,,,. b. Y,) + Dice YJ),
(8)
where CE(.,)) represents the cross-entropy loss, and Dice(.,-) is the Dice coefficient loss. Where Y, denotes the ground truth labels for binary segmentation.
Then, the chromatic number with the greedy algorithm is equal to the chromatic number:
Four-Color Category Prediction
To accurately identify foreground regions and ensure dis- tinct encodings for adjacent cells, we propose a negative sampling constraint method, as shown in Figure (b). This method enforces heterogeneity for adjacent cells while pre- serving the accuracy of four-color encoding.
Xgreedy (G) = X()).
(4)
Where X(G) denote the chromatic number, which is the mini- mum number of colors, and Xgreed denote the chromatic number obtained by applying the greedy coloring algorithm. Some related definitions and proofs are included in the Sup- plementary Material.
First, based cell connectivity relationships, sample features from the adjacent cell pairs (vi, Uz). Meantime, the sampled feature sets can be formulated as follows:
4. Method Designs
F, = {ffe a L...,,,, M}.
(9)
4.1. Asymptotic Training Strategy
FJ 115 11
(10)
Previous research primarily focused on designing power- ful feature extractors (Liu al., 2022: Yu et al., 2024) or
where M and are the number of sampling obtained from cells v, and Uj. respectively, and f denotes the feature vector of the a-th pixel in cell 24.
context-aware modules (Liu et al., 2021: Li al., 2024) enhance the network classification ability. However, in the scenario of four-color encoding, the model not only quires learning semantic features to distinguish foreground and background but also needs to learn positional informa- tion, ensuring adjacent cells are assigned distinct colors. To address the dual requirements, we propose an asymptotic training strategy illustrated in Figure (a).
To ensure that the feature representations of adjacent cells exhibit sufficient heterogeneity, we impose an orthogonality constraint in the feature space. This constraint is formulated using a cosine similarity loss:
Lon
Σ (D,R))E
Cos(F,,
(1I)
E
5

---

The Four Color Theorem for Cell Instance Segmentation
(a) Asymptotic Training
(b) Negative Sampling
(c) Transformation
Trans.
x
Lats
FC Pred
FC GT
Samp.
Fi
U
Lort
Conv
Input
Conv
sem
G (
Output
Sem. Pred
Sem. GT
Seg. Segmentation
Trans.:
Transformation
Sem. Semantic
FC: Four-color
Samp. Sampling
0: 0 channel
Sampled feature
Figure 5.
The training framework of proposed FCIS. (a) represents the asymptotic training method, (b) represents the negative sampling learning for adjacent cells, and (c) represents the encoding transformation method.
where Cos(,,) denotes the cosine similarity function, E is the set of all edges representing adjacent cell pairs, and [E] is the total number of edges. By minimizing Lon, the similarity of feature representations is suppressed, thereby enhancing the model's ability to distinguish cells.
improving the model's overall performance and accelerating its convergence during training. Employing the transformed prediction, we compute a classification loss specific to the foreground as follows:
Lat = CE(V, Vr) + Dice (9, Vÿ),
(14)
4.2. Encoding Transformation
Where Y, and Y, represent the predicted and ground truth foreground regions, respectively. In the optimization objec- tive, we only calculate the loss of the foreground region.
Although the orthogonality constraint ensures heteroge- ncous encoding, this sampling-buss supervision remains weak and may not effectively guide model training. To provide stronger supervision, we introduce four-color en- coding as the target label. However, the non-um non-uniquene con-uniqueeess of the encoding can lead to inconsistencies in supervision, potentially hindering model convergence. To mitigate this is- sue, we propose an encoding transformation method, whose mechanism is established in the following theorem.
Total Loss Function
The overall loss function integrates the semantic, orthogo- nality, and classification losses and is formulated as follows:
Lixal
Luem + X Con + X Lets-
(15)
where A and A2 are hyperparameters that control the im- portance of the orthogonality and classification losses. In the paper, set d 2 and A2 1. More experiment comparisons are added in Supplementary Material.
Theorem 2. Greedy Coloring Compatibility: In the cell instance segmentation task, let the encoding matrix gener- ated by the greedy algorithm be:
CER 4).
(12)
5. Experiments
And the encoding matrix predicted by the network is:
5.1. Datasets
PERUX
(13)
We evaluated our proposed method on multiple types of cell images, including pathological images, fluorescence- stained images, bright-field images and phase-contrass im- ages. Specifically, the datasets used include BBBC006v1 (Ljosa et al., 2012), DSB2018 (Caicedo et al., 2019), Pan- Nuke (Gamper et al., 2020) and YeaZ (Dietler et al., 2020).
represents the number of cells, l is the number of col- ors used in the greedy algorithm, and k is the number of
predicted encodings.
If the predicted encoding matrix P has one of the relations with the greedy encoding C. i.e., substitution, exchange, rule modification. Then there exists mapping function: f P + C, such that the network's predicted result can be transformed into the four-color encoding result. The detailed proof is shown in Supplementary Material.
The BBBC006y1 consists of 768 Hoechst 33342 marker- stained images, each with a resolution of 696x520 pixels. Following the dataset split used by CPP-Net (Chen et al., 2023), we divide the dataset into 462 training, 153 valida- tion, and 153 testing images.
Based on the above theory, we propose an encoding trans- formation method consisting of two convolutional layers, which maps the network's predicted output Y, into the op- timal encoding Y, as shown in Figure (c). This transfor- mation ensures adherence to the four-color encoding rules,
The DSB2018 source from the Data Science Bowl 2018 competition, contains 670 fluorescence-staine images with resolutions ranging from 256x to 520 696 pixels using DAPI and Hoechst stains. We split the dataset into 380 training, 67 validation, and 50 testing images.
6

---

The Four Color Theorem for Cell Instance Segmentation
Input
HoverNet
CPP-Net
GeNSeg-Net
FC Pred (ours)
GT
Inst Pred (ours)
Inst GT
Figure 6. The visualization comparisons between different methods.
Metries
Metries
Methods
Methods
DICE
A))
DQ)
SQ
(1)
DICE
ATI
DQ
SQ
PQ
DCAN (Chen et 2016)
0.795
0.676
0.743
0.780
0.626
DCAN 2016)
0
0.875
0.850
0.773
HoverNet (Graham al., 2019)
0.762
0,863
0.762
HoverNet (Gmhhmm al., 2019)
0.941
0.911
NucleiSogNet (Lal et al., 2021)
0.904
0.671
0.784
0.843
0.682
NucleiSegNet (Lal at. 2021)
0.939
0.671
0.809
0.844
0.719
DoNet Oliang et sl., 2023)
0.823
0,716
0.787
0.829
0.673
DoNet (Jiang et al., 2023)
0.933
0.836
0.882
0.871
0.794
CPP-Net (Chen et al., 2023)
0,914
0.813
0.866
0.879
0.758
CPP-Net (Chen et al., 2023)
0.944
0.914
0.917
0.914
0.898
GaNSeg (Xu al., 2024)
0.856
0.781
0,843
0.791
0.759
GeNSeg Net (Xu et al., 2024)
0.934
0.907
0.913
0.911
0.915
Un SAM (Chen et al., 2025)
0,902
0.786
0,826
0.834
0.747
Un-SAM (Chen et al., 2025)
0.933
0.912
0.909
0.911
0.904
CellPose (Stringer, 2025)
0.923
0.824
0.862
0.871
0.764
CollPose (Stinger, 2025)
0.949
0.917
0.912
0.922
0.914
FCIS (Ours)
0.939
0.828
0.875
0.878
0.770
FCIS (Ours)
0.954
0.921
0.926
0.948
0.935
Table The comparison performances DSB2018 dataset.
Table 4. The comparison performances on BBBC006v1 dataset.
Metrics
Mothods
DICE
A"I
(1)
SQ(
(1)
Methods
DICE (f)
AJl (t)
DQ (t)
SQ)
PQ (f)
DCAN (Chen et al., 2016)
0.778
0.587
0.659
0.721
0.506
DCAN (Chen et al., 2016)
0.881
0.772
0.571
0.736
0.446
HoverNet (Graham et al., 2019)
0.798
0.646
0.218
0.782
0.595
HoverNet (Graham et ol., 2019)
0.907
0.814
0.602
0.739
0.445
NucleiSegNet (Lal et al., 2)21)
0.752
0.544
0.618
0.689
0.457
NucleiSegNet (I.al et 2021)
0.874
0.788
0.583
0.734
0.439
DoNet (liang al., 2023)
0,781
0.612
0.684
0,750
0.544
DoNet (Jiang et al., 2023)
0.878
0.754
0.577
0.720
0.431
CPP-Net (Chen al., 2023)
0.814
0.638
0.711
0,776
0,583
GeNSeg-Nee (Xu
2024)
0,869
0.747
0.572
0.722
0.433
Un SAM (Chen 2025)
0.501
0.629
0.704
0.767
0.570
Un-SAM (Chen al,, 2025)
0.904
0. 0.808
0.597
0.734
0.442
ColiPese (Stringer, 2025)
0.703
CellPose (Stringer, 2025)
0.911
0.740
0.451
FCIS (Ours)
0.721
0.610
PCIS (Oun))
0.922
0.819
0.741
Table The comparison performances on PanNuke dataset.
Table 5. The comparison performances on YeaZ dataset.
momentum of 0.9, and weight decay of 0.0005. The net- work is trained for 200 epochs. Segmentation performance is evaluated using the DICE coefficient, Aggregated Jac- card Index (AJI) (Kumar et al., 2017), Detection Quality (DQ) (Kirillov et al., 2019), Segmentation Quality (SQ), and Panoptic Quality (PQ) metrics. In all tables presented in this paper, the highest performance scores are highlighted in bold, while the second-best scores are underlined.
The PanNuke dataset includes 7901 H&E-stained images, each 256x256 pixels, originating from 19 organs, with a total of 189,744 annotated nuclei. We divide this dataset into 2656 training, 2523 validation, and 2722 testing images.
The YeaZ comprises 306 bright-field (BF) images with resolutions ranging from 301 3301 to 1463x1311 pixels, and 43 phase-contrast (PC) images with resolutions ranging from 256x 256 to x988x 2000 pixels. Due to the limited number of PC images, we merge the BF and PC datasets to train a unified model, resulting in 300 training, 20 validation, and 29 testing images.
5.3. Main Experiments
We evaluate the performance of our proposed method against eight state-of- -ottte--rttttttt models across three bench- mark datasets. The compared methods include the detection- based DoNet (Jiang et al., 2023); contour prediction- approaches such as DCAN (Chen et al., 2016), NucleiSeg- Net (Lal et al., 2021), and GeSegNet (Xu et al., 2024); distance mapping- based methods including HoverNet (Gra-
5.2. Implementation Details and Evaluation Metrics
Our all experiments are conducted using Py PyTorc on an NVIDIA A100 GPU. We employ stochastic gradient de- scent (SGD) as the optimizer, with learning rate of 0.01,
7

---

The Four Color Theorem for Cell Instance Segmentation
DSB2018
PanNuke
Settings
Settings
DX)
PQ
[XQ
5Q
PQ
Baxeline
0.876
0.751
0.847
0,856
0.746
Baseline
0,786
0.627
0.703
0.778
0.380
Four volor
0.43(33.3
0.7256-2.6)
0.805(-4.2)
0.877-2.9)
0.67(-7.2)
Four-color
0, 0.666-2.0
0.617(-1.0) 1.00
0.686(-199
0.752(2266
0.599k-2.1)
Asyap.
Trans.
Samp.
DICE
AJI
DX
SQ
PQ
Asymp.
Trans.
Samp.
DICE
AJ1
[X
sQ
P4
0.862
0.740
0.773
0.624
0.601
0.763
0.565
0883
0.756
0.829
0.844
0.761
0.787
0.630
0.710
0.774
0.572
0,910
0.785
0.846
0.863
0.741
0,803
0.642
0.714
0,776
0.598
0,939
0.828
0.875
0.878
0.770
0,816
0.653
0.721
0.796
0,610
Table Ablation studies on the DSB2018 and PanNuke datasets. Baseline denotes the binary semantic segmentation model based on U-Net (Ronneberger et al., 2015). w. Four-color increases the number of channels from two to five by directly employing four-color encoding in Algorithm as ground truth. Asymp. represents the asymptotic training method, Trans, applies the encoding transformation method, and Samp. introduces negative sampling constraint for adjacent cells.
(a) Input
(b) Baseline
(c) FC
(d) Sem
w/o Trans Trans
Lo6s
w/o Trans
8
W Trans
2000
4002
2000
2000
<002
3000
(e) Asymptotic
(f) Ours
(g) FC
(h) Inst GT
Figure 7. Convergence analysis of the training loss and AJI on val- idation set before and after applying the encoding transformation.
ham et al., 2019), CPP-Net (Chen al., 2023), and CellPose (Stringer, 2025); well as based foundation model Un-SAM (Chen et al., 2025). Quantitative results are sum- marized in Tables 2-5. It is worth noting that GeSegNet, which was not designed for pathological image segmenta- tion and performs poorly on the PanNuke dataset, is ex- cluded from comparisons on that dataset.
Figure 8. The visualization comparisons between different settings. The blue hox indicates that the binary semantic prediction cannot distinguish adjacent cells. The red hoxes indicate the four-color encoding lacks effective supervision for adjacent cells. The white boxes indicate our FCIS encodes adjacent cells with distinct colors.
ensuring that adjacent cells are assigned distinct colors, en- hancing instance differentiation. By comparing the cell mor- phologies produced by different methods, we also observe that our segmentation results align more closely with the ground truth. This improvement can be attributed to incor- porating the negative sampling learning method, effectively enhancing the boundary delineation. Additionally, due to page constraints, more visualization results are provided in the Supplementary Material.
From the results, can see that FCIS consistently out- performs existing methods across all datasets. It achieves the highest DICE and AJI scores, demonstrating superior segmentation accuracy and instance-level consistency. In the DSB2018 dataset, our model achieves a DICE score of 0.939, surpassing Un-SAM and CellPose, among the performin prior methods. The PQ metric of 0.770 further indicates our model's ability to maintain segmenta- tion quality and object-level distinction. In BBBC006V1, we can observe similar trends. While segmenting in the more challenging PanNuke, FCIS achieves 0.610 on the PQ. outperforming all previous methods and confirming its generalization capabilities. Although HoverNet achieves comparable performance to our method but incurs signifi- cantly higher parameter counts and computational complex- ity, shown in Table 1. Therefore, considering the trade-off between model performance and computational cost, our method demonstrates a more pronounced overall advantage.
5.4. Ablation Studies
Effectiveness Analysis of the Method Designs
We conduct an ablation study to evaluate the module's performance under various configurations. The ablation methods include employing an asymptotic training strat- egy, applying encoding transformations to the network's predictions, and introducing sampling constraint for adja- cent cells. The experimental results are presented in Table 6. From the table, we observe the following: (1) When using the four-color encoding as supervision, the model performance decreases significantly, indicating the inherent
Furthermore, we visually compare different models in Fig- ure 6. First, the results from "FC Pred" demonstrate that our method strictly adheres to the four-color encoding rule,
8

---

The Four Color Theorem for Cell Instance Segmentation
challenges of directly employing this encoding as training signal. (2) Adding the asymptotic training strategy or encod- ing transformation methods leads to slight performance im- provements, suggesting that these techniques provide some regularization benefits to the learning process. (3) Introduc- ing the sampling constraint for adjacent cells results in a substantial performance boost, highlighting the effective- ness of this design enforeing spatial consistency among predictions. These findings demonstrate that the proposed designs contribute positively to model performance.
sistently achieves superior segmentation aceuracy and effi- ciency compared to state-of-the-art approaches. Future work will explore adaptive encoding strategies that dynamically respond to varying tissue architectures and cell densities, further improving generalization across datasets. Addition- ally, extending the proposed framework to downstream tasks such as cell nucleus classification represents promising research direction.
A Acknowledgments
Analysis of Training Convergence
This research was supported by the National Key R&D Pro- gram of China (No. 2023YFC300500), the Federal Min- istry of Education and Research in Germany under funding reference 161L.272,, and the Ministry of Culture and Sci- ence of the State of North Rhine- Weatne--esppalla, The authors would like to thank the anonymous reviewers for their valu- able comments and suggestions, which greatly improved the quality of this paper.
We analyze the model's 's convergence behavior by comparing the training loss and the validation AJI before and after ap- plying the encoding transformation, illustrated in Figure The results indicate that incorporating the encoding trans- formation accelerates the convergence of the training loss, leading to faster stabilization with lower loss. Additionally, the AJI metric shows a significant improvement after apply- ing the transformation, demonstrating the effectiveness of this design in enhancing model performance.
Impact Statement
Visualization of Different Settings
This paper introduces novel cell instance segmentation method based four color theorem that significantly im- proves the accuracy and computational efficiency. By sim- plifying the segmentation task, this approach has the poten- tial to enhance automated biomedical image analysis and accelerate clinical diagnostics.
Based on the experimental results in Table 6, we conduct the visualization comparisons as shown in Figure 8. The red annotations represent the binary semantic segmenta- tion ground truth (GT), the four-color encoding GT, and the instance segmentation GT, respectively. First, from the baseline results (b), is evident that using only dual- channel predictions fails to distinguish adjacent cells effec- tively. Second, when directly using four-color encoding (b) as a supervision, the model lacks awareness of encoding inconsistency for adjacent cells, resulting in not only in- distinguishable instances, but also fragmented predictions. By incorporating the asymptotic training (c) strategy, these issues are partially alleviated; however, distinguishing ad- jacent cells remains challenging. In contrast, our proposed method (f) demonstrates that the predicted results ensure not only that adjacent cells are encoded with different colors but also that the structural integrity of each instance.
6. Conclusions
We present novel approach to cell instance segmentation by leveraging the four-color theorem, which reformulates the instance segmentation problem as a four-class semantic segmentation task. This transformation significantly reduces computational overhead and simplifies model design. To address challenges arising from the non-uniqueness of color encodings, we propose an asymptotic training strategy and an encoding transformation mechanism that ensure stable optimization. Extensive experiments on diverse biomedi- cal imaging modalities, including fluorescence, H&E, and bright-field microscopy, demonstrate that our method con-
9

---

The Four Color Theorem for Cell Instance Segmentation
References
Fritsch, R., Fritsch, R., Fritsch, G., and Fritsch, G. Four- Color Theorem. Springer, 1998.
Barkley, D., Moncada, R., Pour, M., Liberman, D. A., Dryg, I., Werba, G., Wang, W., Baron, M., Rao, A., Xia, B., et al. Cancer cell states recur across tumor types and form specific interactions with the tumor microenvironment. Nature genetics, 54(8):1192-1201 2022.
Gamper, J., Koohbanani, N. A., Benes, K., Graham, S., Jahanifar, M.. Khurram, S. A., Azam, A., Hewitt, K., and Rajpoot, N. Pannuke dataset extension, insights and baselines. arXiv preprint arXiv:2003 2020.
Caicedo, J. C., Goodman, A., Karhohs, K. W., Cimini, B. A., Ackerman, J., Haghighi, M., Heng, C., Becker, T., Doan, M.. McQuin, C., et al. Nucleus segmentation across imaging experiments: the 2018 data science bowl, Nature methods, 16(12):1277-1553 2019.
Gonthier, G. et al. Formal proof-the four-color theorem. Notices of the AMS, 55(11): 2008.
Graham, S., Vu, Q. D., Raza, S. E. A., Azam, A., Tsang, Y. W., Kwak, J. T., and Rajpoot, N. Hover-net: Simulta- neous segmentation and classification of nuclei in multi- tissue histology images. Medical image analysis, 58: 101563, 2019.
Chen, H., Qi, X., Yu, L., and Heng. P.-A. Dean: deep contour-aware networks for accurate gland segmentation. In Proceedings of the IEEE conference on Computer Vision and Pullern Recognition, pp. 2487-2496, 2016.
He, H., Huang. Z., Ding, Y., Song, G., Wang, L.,, Ren, Q. Wei, P., Gao, Z., and Chen, Cdnet: Centripetal direction network for nuclear instance segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1026-4033, 2021.
Chen, J., Mei, J., Li, X., Lu, Y., Yu, Q. Wei, Q. Luo, X., Xie, Y., Adeli, E., Wang, Y., et al. Transunet: Rethinking the u-net architecture design for medical image segmen- tation through the lens of transformers. Medical Image Analysis, 97:1 03:203 2024.
He, K., Gkioxari, G., Dollár, P., and Girshick, R. Mask r- cnn. In Proceedings of the IEEE international conference on computer vision, pp. 2961-2969, 2017.
Chen, S., Ding, C., Liu, M., Cheng, J., and Tao, D. Cpp- net: Context-aware polygon proposal network for nucleus segmentation. IEEE Transactions on Image Processing, 32:980-994, 2023.
He, Z., Unberath, M., Ke, J., and Shen, Y. Transnuseg: A lightweight multi-task transformer for nuclei segmen- tation. In International Conference on Medical Image Computing and Computer-Assisee Intervention, pp. 206- 215. Springer, 2023.
Chen, Z., Xu, Q., Liu, X., and Yuan, Y. Un-sam: Domain- adaptive self-prompt segmentation for universal nuclei images. Medical Image Analysis, pp. 103607, 2025.
Hörst, F., Rempe, M., Heine, L., Seibold, C., Keyl, J., Bal- dini, G., Ugurel, S., Siveke, J., Grünwald, B., Egger, J.. et al. Cellvit: Vision transformers for precise cell seg- mentation and classification. Medical Image Analysis, 94: 103143, 2024.
Cords, I.., Tietscher, S., Anzeneder, T., Langwieder, C.,, Rees, M. de Souza, N., and Bodenmiller, B. Cancer- associated fibroblast classification in single-cell and spa- tial proteomics data. Nature communications, 14(1)44 2023.
Ilyas, T., Mannan, Z. I., Khan, A., Azam, S., Kim, H., and De Boer, F. Tsfd-net: Tissue specific feature distilla- tion network for nuclei segmentation and classification. Neural Networks, 151:1-15, 2022.
Dietler, N., Minder, M., Gligorovski, V., Economou, A. M., Joly, D. A. H. L., Sadeghi, A., Chan, C. H. M., Koziński, M., Weigert, M., Bitbol, A.-F., et al. A convolutional neu- ral network segments yeast microscopy images with high accuracy. Nature communications, 11(1):5723, 2020.
Jain, J., Singh, A., Orlov, N., Huang, Z., Ji, Walton, S., and Shi, H. Semask: Semantically masked transform- ers for semantic segmentation. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 752-761, 2023.
Doan, T. N., Song, B., Vuong, T. T., Kim, K., and Kwak, J. T. Sonnet: A self- self-guided ordinal regression neural network for segmentation and classification of nuclei in large-scale multi-tissue histology images. IEEE Journal of Biomedical and Health Informatics, 26(7):3218-322) 2022.
Jiang H., Zhang, R., Zhou, Y., Wang, Y., and Chen, H. Donet: Deep de-overlapping network for cytology in- stance segmentation. In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 15641-15650, 2023.
Falk, T. Mai, D.,, Bensch, R., Çişek, Ö., Abdulkadir, A., Marrakchi, Y., Böhm, A., Deubner, J., Jäckel, Z., Seiwald, K., et al. U-net: deep learning for cell counting, detection, and morphometry. Nature methods, 16(1):67-70, 2019.
Kao, K.C Vilbois, S., Tsai, C.-H., and Ho, P.-C. Metabolic communication in the tumour tumour-immune immune microenviron- ment. Nature cell biology, 24(11):1574-- 2022.
10

---

The Four Color Theorem for Cell Instance Segmentation
Kirillov, A., He, K., Girshick, R., Rother, C., and Dollár, Panoptic segmentation. In Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pp. 9404-941111 2019.
Pan, X., Cheng, J., Hou, F., Lan, R., Lu, C., Li, L.,, Feng, Z., Wang. H., Liang, C., Liu, Z.,, et al. Smile: Cost- sensitive multi-task learning for nuclear segmentation and classification with imbalanced annotations. Medical Image Analysis, 88: 102867, 2023.
Kumar, N., Verma, R., Sharma, S., Bhargava, S., Vahadane, A., and Sethi, A. A dataset and a technique for general- ized nuclear segmentation for computational pathology. IEFE transactions on medical imaging, 36(7):1550-1560, 2017.
Petukhov, V., Xu, R. J., Soldatov, R. A.,, Cadinu, P., Kho- dosevich, K., Moffitt, J. R., and Kharchenko, P. V. Cell segmentation in imaging- based spatial transcriptomics. Nature biotechnology, 40(3):345-354 2022.
Lal, S.. Das, D., Alabhya, K., Kanfade, A., Kumar, A., and Kini, J. Nucleisegnet: Robust deep learning architecture for the nuclei segmentation of liver cancer histopathology images. Computers in Biology and Medicine, 128:104075, 2021.
Prangemeier, T., Reich, C.,, and Keeppi, H. Attention-based transformers for instance segmentation of cells in mi- crostructures. In 2020 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pp. 700-707. IEEE, 2020.
Li, H., Zhang, D., Dai, Y., Liu, N., Cheng, L., Li, J., Wang, J. and Han, J. Gp-nerf: Generalized perception nerf for context- 3d scene understanding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 21708-21718, 2024.
Qu, H., Yan, Z., Riedlinger, G. M., De, S., and Metaxas, D. N. Improving nuclei/gland instance segmentation in histopathology images by full resolution neural network and spatial constrained loss. In Medical Image Comput- ing and Computer Assisted Intervention- 2019: 22nd International Conference, Shenzhen, China, Octo- ber 13-17, 2019, Proceedings, Part I 22, pp. 378-386. Springer, 2019.
Liu, Z.,, Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang. Z., Lin, S., and Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 10012-10022, 2021.
Raza, S. E. A., Cheung, I.., Shaban, M., Graham, S., Epstein, D., Pelengaris, S., Khan, M., and Rajpoot, N. M. Micro- A unified model for segmentation of various objects in microscopy images. Medical image analysis, 52:160- 173, 2019.
Liu, Z., Mao, H., Wu, C.-Y., Feichtenhofer, C., Darrell, T., and Xie, S. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11976-11986, 2022.
Redmon, and Farhadi, A. Yolo9000: better, faster, stronger. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7263-7271, 2017.
Ljosa, V., Sokolnicki, K. L., and Carpenter, A. E. Annotated high-throughput microscopy image sets for validation. Nature methods, 9(7):337-677, 2012.
Ren, S., He, K., Girshick, R., and Sun, Faster r-enn: Towards real-time object detection with region proposal networks. IEEE transactions pattern analysis and machine intelligence, 396)::137-11199 2016.
Mann, M., Kumar, C., Zeng, W.-F,, and Strauss, M. Artifi- cial intelligence for proteomies and biomarker discovery. Cell systems, 1288)759-770, 2021.
Meng, Z., Dong, J., Zhang, B., Li, S., Wu, R., Su, F., Wang. G., Guo, I.., and Zhao, Z.. Nusea: Nuclei segmentation with ellipse annotations. IEEE Journal of Biomedical and Health Informatics, 2024.
Ronneberger, O., Fischer, P., and Brox, T. U-net: Con- volutional networks for biomedical image segmenta- tion. In Medical image computing and computer-assisted intervention-MICCAl 2015: 18th international confer- ence, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pp. 241. Springer, 2015.
Merryweather, A. J., Schnedermann, C., Jacquet, Q., Grey, C. P., and Rao, A. Operando optical tracking of single- particle ion dynamics in batteries. Nature, 594(7864); 522-528, 2021.
Schmidt, U., Weigert, M., Broaddus, C., and Myers, G. Cell detection with star-convex polygons. In Medical Image Computing and Computer Assisted Intervention- MICCAI 2018: 2 International Conference, Granada, Spain. September 16-20, 2018, Proceedings, Part II 11, pp. 263-273. Springer, 2018
Pachitariu, M. and Stringer, C. Cellpose 2.0: how to train your own model. Nature methods, 19344111644,164, 2022.

---

The Four Color Theorem for Cell Instance Segmentation
Srivastava, A., Jha, D., Chanda, S., Pal, U., Johansen, H. D., Johansen, D., Riegler, M. A., Ali, S., and Halvorsen, P. Msrf-net: multi-scale residual fusion network for biomedical image segmentation. IEEE Journal of Biomed- ical and Health Informatics, 2665) 2021.
Zhou, Y., Onder, O. F., Dou, Q.. Tsougenis, E., Chen, H., and Heng, P.-.. Cia-net: Robust nuclei instance seg- mentation with contour-aware information aggregation. In Information Processing in Medical Imaging: 26th In- ternational Conference, IPMI 2019, Hong Kong, China, June 2-7, 2019, Proceedings 26, pp. 682-693, Springer, 2019.
Stringer, C. Cellpose3: one-click image restoration for improved cellular segmentation. Nature Methods, pp. 1-8, 2025.
Zhou, Y., Chen, H., Lin, H., and Heng, P.-A. Deep semi- supervised knowledge distillation for overlapping cervi- cal cell instance segmentation. In Medical Image Comput- ing and Computer Assisted Eneevention-MICCO 2020:
Stringer, C., Wang, T., Michaelos, M., and Pachitariu, M. Cellpose: a generalist algorithm for cellular segmentation. Nature methods,
2021.
23rd International Conference, Lima, Peru, October 4- 8, 2020, Proceedings, Part 23, pp. 521-53111111 Springer, 2020.
Wang, P., Chen, P., Yuan, Y., Liu, D., Huang, Z., Hou, X., and Cottrell, G. Understanding convolution for semantic segmentation. In 2018 IEEE winter conference appli- cations of computer vision (WACV), pp. 1451-1460. leee, 2018.
Zhou, Z., Rahman Siddiquee, M. M., Tajbakhsh, N., and Liang. J. Unet++: A nested u-net architecture for medical image segmentation. In Deep Learning Medical Image Analysis and Multimodal Learning for Clinical Decision Support: 4th International Workshop. DLMIA 2018, and 8th International Workshop, ML-CDS 2018, Held in Con- junction with MICCAI 2018, Granada, Spain, September 20, 2018, Proceedings 4, pp. 3-11. Springer, 2018
Xiong, S., Li, X., Zhong, Y., and Peng, W. Repsnet: A nucleus instance segmentation model based on boundary regression and structural re-parameterization. Interna- tional Journal of Computer Vision, pp. 1-20, 2025.
Xu, S., Li, G., Song, H., Wang, J., Wang, Y., and Li, Q. Genseg-nee net: A general segmentation framework for any nucleus in inmunohistochemistry images. Proceedings of the 32nd ACM International Conference on Multime- dia, pp. 4475-4484 2024.
Yu, W., Zhou, P., Yan, S., and Wang. X. Inceptionnext: When inception meets convnext. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5672-5683, 2024.
Zhang, Y., Cai, L., Wang. Z., and Zhang, Y. Seine: Struc- ture encoding and interaction network for nuclei instance segmentation. IEEE Journal of Biomedical and Health Informatics, 2025a.
Zhang, Y., Fang, Z., Wang, Y., Zhang, L., Guan, X., and Zhang, Y. Category prompt mamba network for nuclei segmentation and classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 10284-10292, 2025b.
Zhang, Y., Wang, Y., Fang, Z., Bian, H., Cai, L.,, Wang, Z., and Zhang, Y. Dawn: Domain- adaative weakly su- pervised nuclei segmentation via cross-task interactions. IEEE Transactions on Circuits and Systems for Video Technology, 35(5):455344777 2025c.
Zhou, T., Wang, W., Konukoglu, E., and Van Gool, L. Re- thinking semantic segmentation: A prototype view. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 2582-2593, 2022.
12

---

The Four Color Theorem for Cell Instance Segmentation
Supplementary Material
A. Data Splitting
We applied an overlapping cropping method to the DSB2018, BBBC006V1, 1, and YeaZ datasets during the data preprocessing stage. Specifically, we used a sliding window with stride of 128 to extract 256x256 patches. Since the original image size in the PanNuke dataset already x no additional processing was required. The number of samples in the training, validation, and test sets is shown in Table 7.
Datasets
No. Traing
No. Valiadation
No. Testing
DSB2018
602
109
89
PanNuke
2656
2522
2722
BBBC006v1
1848
612
612
YeaZ
1000
140
200
Table 7. The number of samples in the training, validation, and test datascts.
B. Related Work
B.1. Detection-Baser Cell Segmentation
The challenge of distinguishing individual cells in overlapping regions has long been critical issue in instance segmentation. With the introduction of Faster R-CNN Ren et al. (2016), Mask R-CNN He et al. (2017) extended this detection framework by incorporating an instance segmentation module. This two-stage approach first generates bounding boxes to locate individual instances and then performs segmentation within these regions. Mask R-CNN's inherent ability to separate instances without requiring complex post-processing has made it widely adopted framework for semi-supervised cell instance segmentation tasks Zhou et al. (2020).
B.2. Contour Prediction-Based Cell Segmentation
Contour-based segmentation methods focus on explicitly predicting cell boundaries to achieve instance separation. Early works, such as U-Net Ronneberger et al. (2015), facilitated boundary learning by assigning higher pixel-wise weights to cell edges, followed by post-processing techniques like watershed or contour detection to delineate individual instances. This architecture significantly influenced deep learning-based segmentation, particularly in medical imaging. Subsequent advancements introduced explicit contour prediction to improve instance separation. DCAN Chen et al. (2016) incorporated additional semantic categories for boundary pixels, enabling clearer differentiation between cells and the background. UNet++ Zhou et al. (2018) refined U-Net's performance by employing nested skip connections, while FullNet Qu et al. (2019) and CIA-Net Zhou et al. (2019) leveraged multi-scale
13

---

The Four Color Theorem for Cell Instance Segmentation
context aggregation to enhance boundary delineation. More recent models, such TSFD-Net Ilyas et al. (2022) and GeNSeg-Net Xu et al. (2024), continue to advance the field by integrating sophisticated architectures designed improve boundary prediction accuracy.
B.3. Distance-Based Cell Segmentation
Distance-based segmentation approaches predict spatial relationships between pixels and their corre- sponding cell instances, facilitating robust separation of adjacent cells. StarDist Schmidt et al. (2018), one of the pioneering methods in this category, introduced radial distance predictions, which proved effective for segmenting cells with irregular shapes. HoverNet Graham et al. (2019) extended this con- cept by simultaneously predicting a distance map and a classification map, enabling accurate instance separation in densely packed regions. CDNet He et al. (2021) further improved generalization across datasets by employing multi-task learning. Recent advancements have explored more sophisticated architectures to enhance both segmentation accuracy and computational efficiency. SONNET Doan et al. (2022) introduced a self-organizing network to model complex spatial relationships, while TransUNet He et al. (2023) combined transformer-basee architectures with distance prediction to enhance feature representation. CPP-Net Chen et al. (2023) and SMILE Pan et al. (2023) incorporated context-aware modules to improve adaptability to diverse cell morphologies. Emerging models such as CellViT Hörst et al. (2024) and RepSNet Xiong et al. (2025) integrate vision transformers with structural priors, further advancing distance-based segmentation techniques for challenging datasets.
BBBC006V1
PanNuke
DSB2018
Figure 9. Visualization of four-color encoding results.
C. The Analysis of Four-color Encoding
The four-color encoding method highlights the feasibility of transforming cell instance segmentation into semantic segmentation task. To better understand the characteristics of four-color encoding, we present visualizations of encoded images from multiple datasets, as shown in Figure 9. In this figure, we randomly selected images from three different datasets and applied four-color encoding. The results reveal the following patterns:
14

---

The Four Color Theorem for Cell Instance Segmentation
(1) The majority of cells are encoded in red, while a smaller proportion are assigned green;
(2) Cells encoded in blue are scarce, appearing only in highly dense regions (highlighted by white box), typically with one or two occurrences;
(3) The fourth encoding category (represented by yellow) does not appear, indicating that cell encoding is more constrained and simplified than the traditional map-coloring problem.
Furthermore, the statistical analysis of the four-color encoding results, illustrated in Figure 10, aligns with the observed distribution of cell color assignments, further validating the characteristics of this encoding approach.
enc=1
enc=1
60
enc=2
enc=2
60
40
enc=3
enc=3
40
20
20
0
(a) DSB2018
(b) PanNuke
Figure 10. Statistics of different color encodings
D. Preliminaries
We provide essential definitions and concepts to establish the foundation for the proposed method. Definition 1. Undirected Graph. An undirected graph is represented as G (V, E), where V is the set of vertices, and E is the set of edges. An edge e (u, v) E E indicates that vertices u and are adjacent.
Definition 2. Coloring Number. The chromatic number of graph G, denoted XG),, is the minimum number of colors required to color the vertices of G such that no two adjacent vertices share the same color.
Definition 3. Maximum Degree. The degree of vertex v E V, denoted as d(v), is the number of vertices adjacent to v. The maximum degree of the graph G is defined as A(G) = max,ev d(v).
Definition 4. Chain Structure: A type of graph where the vertices are arranged in linear path, formally known as a path graph P,,. In the structure, each vertex is connected to at most two adjacent vertices, For instance, in the graph Pa with vertices, the coloring sequence can be described as:
U1 - color 1, U2 - color 2, Us - color 1, 04 color 2.
Definition 5. Rectangular Structure: A rectangular structure graph where vertices are arranged in regular rectangular grid. Such graphs are a specific type of planar graph, where each vertex typically
15

---

The Four Color Theorem for Cell Instance Segmentation
has degree of 2 or 4, satisfying ( S 4.
Definition 6. Planar Graph. A planar graph is a graph that can be embedded in the plane such that no edges intersect. According the Four-Color Theorem, the chromatic number of planar graph satisfies X(G) S 4.
E. Theorem and Proof
Theorem 1. Global Optimality of Greedy Coloring: Let G (V, F) be an undirected graph representing cell distribution, where V is the set of vertices (cells), and E is the set of edges representing adjacency relationships between cells. Suppose G satisfies the following conditions:
(1) G is a planar graph, meaning it can be embedded in plane such that no two edges intersect;
(2) The maximum degree of G, denoted by A(G), satisfies:
AG) S k, where k S 4;
(3) The vertex distribution of G follows either chain structure (a path graph Pr)) or rectangular structure (a grid-like planar graph).
Then, the chromatic number of G, defined as the minimum number of colors required to color the vertices such that no two adjacent vertices share the same color, satisfies:
Xgreedy = XGG).
Where Xgreedy (G) is the coloring number by applying the greedy algorithm with any arbitrary vertex ordering. This result demonstrates that the greedy algorithm produces globally optimal solution to the graph coloring problem.
Proof 1:
Definition and Properties of Greedy Algorithm: The greedy algorithm colors graph G as follows: Traverse all vertices in the order 11, .., Uni For each vertex V V, assign the smallest color that has not been used by any of its adjacent vertices; Each vertex checks at most A(G) adjacent vertices, and the number of colors needed is at most A(G) 1.
Thus, the chromatic number generated by the greedy algorithm satisfies:
Xgreedy (G) < A(G) +
Optimality Analysis under Special Structures:
(a) Chain Structure (Path Graph P,): For path graph Pn,, each vertex has degree A(P.) 2. -The chromatic number of a path graph is x(Pr) = 2; When the greedy algorithm colors in any vertex
16

---

The Four Color Theorem for Cell Instance Segmentation
order, it uses at most two colors:
Xgreedy (Pr) = x(P,) = 2
Therefore, the greedy algorithm is optimal for path graphs.
(b) Rectangular Structure: For cells arranged in rectangular grid, graph G planar, and A(G) < According to the Four Color Theorem:
X(G) S 4
The greedy algorithm, in each iteration, uses the smallest available color, and each vertex checks at most 4 adjacent vertices, Therefore, the chromatic number generated by the greedy algorithm satisfies:
Xgreedy (G) 4= X(G)
Thus, the greedy algorithm is also optimal for rectangular structures. Extending Local Optimality to Global Optimality:
Local Sparsity: Due to the distribution properties of graph G, in locally clustered regions, the number of vertices is limited and the maximum degree low. Hence, the greedy algorithm is optimal in local regions.
Global Sparsity of Planar Graphs: The global distribution of planar graphs is sparse, and edges connecting different regions are limited, causing little interference with the local optimal solution. As result, the local optimality of the greedy algorithm extends to global optimality.
Based on the above analysis, the chromatic number of graph G, which satisfies the given conditions, is equal to the minimum chromatic number: Xgreedy (C)=
= X()
Thus, the greedy algorithm is an effective method for generating the minimum color coding in this scenario.
Theorem 2. Greedy Coloring Compatibility: In the cell instance segmentation task, let the encoding matrix generated by the greedy algorithm be:
CERuK (k 4).
(16)
And the encoding matrix predicted by the network is:
P P Back
(17)
where n represents the number of cells, k is the number of colors used in the greedy algorithm, and k is the number of predicted encodings. If the predicted encoding matrix has one of the relations with
17

---

The Four Color Theorem for Cell Instance Segmentation
the greedy encoding, i.e., substitution, exchange, modification of rules. Then there exists a mapping
function:
f PP
(18)
such that the network's predicted result P can be transformed into the four-color encoding result C.
Proof 2:
The four-color encoding matrix C generated by the greedy algorithm satisfies the following properties:
(a) Sparsity: Each row has at most one nonzero element (C[i, {(, representing that the i-th
node uses the j-th color;
(b) Optimality: The number of colors used minimized, rank(C) k; and k S 4;
(c) Adjacency constraint: Any two adjacent nodes (ui, Uz) satisfy Ciú,: :| + C :] (i.e., they cannot use the same color).
These properties can be formally expressed as follows:
(1) Sparsity: Σラ=1 C[i,j] = 1, Vi. (2) Adjacency constraint: If eigj = =1 then C[i,:] : = 0.
The encoding matrix P R predicted by the network exhibit non-uniqueness due the following reasons:
(a) Substitution: Some rows of the encoding are replaced, introducing redundancy;
(b) Exchange: The order of the columns is changed;
(c) Rule modification: Additional colors are introduced, resulting in k' k.
Thus, the column rank of P satisfies:
rank(P) 2 k.
(19)
Hence, we need to construct a mapping function f P - to transform the predicted encoding matrix P into the four-color encoding matrix C' that satisfies the constraints.
(1) Column Redundancy Elimination
A linear transformation is applied to eliminate redundant columns in P, ensuring that the resulting matrix has rank k. Specifically: Define a column transformation matrix T E k where
T argmin PT PT C s.t. rank(PTT k.
T
The transformed matrix is
P'=PT.
18

---

The Four Color Theorem for Cell Instance Segmentation
where P' E Ra*k and rP') k.
(2) Column Order Adjustment
The columns of P' are reordered to align with the column order of C. Let the column permutation matrix be S E R then
= C
The matrix is a permutation matrix satisfying S I.
(3) Adjacency Constraint Verification
After the mapping, the adjacency constraint is verified to ensure that the resulting matrix satisfies the four-color encoding rule:
Cli,:] :] 0, Vei. = 1.
It can be seen that, for any predicted matrix P, the three-step mapping function f ensures that the transformed matrix C satisfies:
(1) The rank of the transformed matrix is k, i... rank(P') k;
(2) The column order is aligned with C;
(3) The adjacency constraint holds, making C valid four-color encoding result.
Therefore, we design encoding transformation and orthogonal constraints to ensure the rationality of four-color prediction.
F. Hyper-parameter Ablation Experiments
We conducted an ablation study on hyperparameter selection using the DSB2018 and BBBC006v] datasets, focusing on the impact of the sampling rate and the weight of the orthogonal constraint loss function. The experimental results are presented in Tables 8 and 9.
The results indicate that increasing the sampling rate generally improves model performance. However, the performance gain from 0.5 to 0.7 less significant than the improvement observed when increasing the sampling rate from 0.3 to 0.5. We set the sampling rate to 0.5 in the main experiments to balance model performance and computational efficiency.
Furthermore, we examined the effect of the orthogonal constraint loss weight on model performance. A significant performance drop is observed when the weight is set to 1. We hypothesize that this is due to the insufficient enforcement of the orthogonal constraint at lower weights, reducing the model's ability to distinguish adjacent instances and ultimately degrading segmentation performance effectively.
19

---

The Four Color Theorem for Cell Instance Segmentation
DSB2018
BBBC00661
Ratio
Ratio
DICE
AJI
DQ
SQ
PQ
DICE
AJ1
DQ
SQ
PQ
0.3
0.913
0.803
0.854
0.871
0.758
r 0.3
0.947
0.917
0.893
0.926
0.899
0.5
0.939
0.828
0.875
0.878
0.770
r 0.5
0.954
0.921
0.926
0.945
0.935
0.7
0.941
0.832
0.866
0.881
0.779
0.7
0.946
0.924
0.933
0.951
0.938
Table 8. Ablation studies of sampling ration DSB2018 and BBBC006vl datasets.
DSB2018
BBBC006v1
Weight
Weight
DICE
AJI
DQ
SQ
PQ
DICE
AJI
DQ
SQ
PQ
==1
0.908
0.798
0.832
0.825
0.716
À
0.922
0.898
0.891
0.904
0.880
A = 0.939
2
0.828
0.875
0.878
0.770
À 2
0.954
0.921
0.926
0.945
0.935
Table 9. Ablation studies of weight setting DSB2018 and BBBC0061 datasets.
G. More Visualization Results
We present the semantic and instance segmentation results, including error analysis, as shown below. Specifically, the subfigures include the input image, pixel-wise error analysis, four-class semantic ground truth, and instance segmentation labels (the last two subfigures can be ignored). The results in the DSB2018 and BBBC006v1 datasets demonstrate that our method not only achieves accurate instance segmentation but also excels in pixel-wise classification by significantly reducing false positive (FP) and false negative (FN) prediction errors. These results validate the effectiveness of our approach.
Image
Coer Anobyte
20

---

The Four Color Theorem for Cell Instance Segmentation
PARPIE
Level wildan
Semeati douad
Semu Lavel
Theeedas aeii Grand
Tate Achonn
Thee-dast Secaad
21

---

The Four Color Theorem for Cell Instance Segmentation
H. Others
To better demonstrate the rationality of our model's module design, plot the convergence curves of various loss functions during the training process on the PanNuke dataset, as shown in Figure 11. The results indicate that our method ensures stable model convergence.
mmh
wanvorrtoo.oo
3.
3.2
0.47
633
24
744
1ag: www.y/orr
teg Jf
teg www. Jedee
21.0
0.44
21.4
03
21.0
C12
012
78
008
21
25
Figure 11. The convergence of loss function and Dice in training process.
22


Reviews:
[{"review_id": "6jaBk7Gytk", "reviewer": "Reviewer_JTJc", "summary": "This paper proposes an innovative cell instance segmentation method based on the four-color theorem, aiming to simplify the instance differentiation process. By conceptualizing cells as \"countries\" and tissues as \"oceans,\" the authors introduce a four-color encoding scheme to ensure adjacent cell instances receive distinct labels, reformulating instance segmentation as a four-class semantic segmentation problem. To address training instability caused by the non-uniqueness of the four-color encoding, the authors design an asymptotic training strategy and encoding transformation method. Experimental results on multiple datasets demonstrate the method's advantages in segmentation performance and computational complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://drive.google.com/file/d/1dERoIrcnDklZhwcJDs5zXBBAFn7-I5u3/view?usp=sharing).\n\n **1. How Non-Uniqueness of Encoding Affect Training Convergence**\n\nIn 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.\n\nAs 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.\n\nTo 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.\n\nTo 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.\n\n**2. Extending the Method to More Complex Scenarios**\n\nWe 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**.\n\nThe 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.\n\n**3. Future Directions for Improvement**\n\nAs 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**.\n\nAs 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.\n\nBesides, 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.\n\n**4. Other Minor Questions**\n\nWe 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.\n\nWe hope that our responses and the newly added experiments have addressed your concerns. Once again, we sincerely thank you for your thoughtful feedback.", "claims_and_evidence": "The claims made in the paper are supported by clear experimental evidence, particularly from the results on various benchmark datasets. However, the issue of non-uniqueness in four-color encoding leads to instability during training, and the paper does not thoroughly explore how this issue impacts the model's performance. While the method shows great promise on several datasets, more experimental evidence is needed to prove its robustness under more complex and diverse cellular distributions.", "methods_and_evaluation_criteria": "The proposed four-color encoding method and evaluation criteria are reasonable and appropriate for the cell instance segmentation task. Through tests on multiple datasets, the paper demonstrates its method’s advantages in both performance and computational complexity. However, the experiments lack a thorough analysis of how the non-uniqueness of the four-color encoding impacts model training in more complex cellular distributions, which should be further explored.", "theoretical_claims": "The application of the four-color theorem in cell instance segmentation is innovative. However, the discussion on the non-uniqueness of the four-color encoding and its impact on training stability is insufficient. While the asymptotic training strategy is reasonable, more in-depth theoretical explanations are needed, especially on how the strategy performs on complex datasets.", "experimental_designs_or_analyses": "The experimental design is solid, covering multiple datasets and using ablation studies to validate the components of the method. However, the paper does not sufficiently investigate how the non-uniqueness of the encoding affects model training in more complex or densely packed cell distributions. The authors could also further demonstrate the generalization of the method to other types of cellular datasets.", "relation_to_broader_scientific_literature": "The paper clearly compares its approach with existing methods in cell instance segmentation, including detection-based, contour-based, and distance mapping approaches. While these comparisons are adequate, there is room for further discussion on newer related works, particularly Transformer-based segmentation methods, which might perform better on complex datasets.", "essential_references_not_discussed": "The paper overlooks some essential recent works in the field of cell instance segmentation, especially some Transformer-based methods. Discussing these approaches would provide a more comprehensive understanding of the context for the proposed method and suggest possible directions for future improvements.", "other_strengths_and_weaknesses": "The paper’s innovation is strong, and the proposed four-color theorem-based method offers practical value, especially in reducing computational complexity. The results show that the method can maintain good segmentation performance while reducing model complexity. However, the non-uniqueness of the four-color encoding remains a challenge, particularly in terms of training stability, which needs to be addressed in future work.", "other_comments_or_suggestions": "1) The authors could further optimize the training process, especially addressing the instability caused by the non-uniqueness of four-color encoding. More experiments on its robustness in complex cell images would be valuable.\n2) In future work, it would be beneficial for the authors to apply the method to more complex datasets and real-world biomedical application scenarios to further validate its broad applicability.", "questions_for_authors": "1) Regarding the non-uniqueness of four-color encoding: \nThe paper mentions that the non-uniqueness of four-color encoding may cause training instability. Could you provide more detailed experimental results on how this issue affects model convergence, especially in complex or dense cell distributions?\n2) Adaptability to complex cell distributions:\nGiven the strong performance on simpler datasets, could you discuss how the method performs on datasets with more complex or highly overlapping cell distributions? Are there any improvements or adaptations to handle such scenarios?\n3) Future improvements to the method:\nAre there any planned future improvements to handle the limitations of four-color encoding, particularly in cases where cell boundaries are irregular or cells are densely packed? How do you plan to address such edge cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ipg6x8qMb8", "reviewer": "Reviewer_aw3n", "summary": "This paper proposes an asymptotic training architecture for cell instance segmentation based on the four-color theorem. Unlike traditional multi-class, multi-channel segmentation methods, the proposed approach follows a step-by-step process: first distinguishing foreground from background, then classifying instances within the foreground region. To enhance training stability, the method imposes orthogonal constraints on adjacent cells to address class imbalance and introduces an encoding transformation technique that maps outputs to a minimum color representation, ensuring consistent segmentation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://drive.google.com/file/d/1dERoIrcnDklZhwcJDs5zXBBAFn7-I5u3/view?usp=sharing).\n\n **1. Theoretical Contributions**\n\nOur 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.\n\nIn the submitted manuscript, we present two key theoretical contributions:\n- **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.\n- **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.\n\nMeantime, the full theoretical derivations and proofs are also included in the supplementary material.\n\nIn 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.\n\n **2. Experimental Validation and Broader Applicability**\n\nWe 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**. \n\nFrom 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.\n\n**3. Comparison with Recent Methods (Un-SAM)**\n\nThank 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.\n\n **4. Presentation and Minor Issues**\n\nWe appreciate your thorough reading regarding typographical errors. In response, **we carefully revised the manuscript** as follows:\n\n- Equation Clarity: All relevant equations have been reviewed and revised for clarity.\n- Index Definitions: The roles and ranges of index variables such as \\(i\\) and \\(j\\) have been clearly defined to remove ambiguity.\n- Grammar and Style: We corrected all minor grammatical and formatting issues to improve overall readability.\n\nAdditionally, 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**.\n\n**5. Clarification on FLOPs vs. FLOPS**\n\nTo convenience you understand the use of our FLOPs, we explain it as follows:\n- **FLOPs** (floating-point operations) measure the total number of computations required by a model and are used to evaluate algorithmic complexity.\n- **FLOPS** (floating-point operations per second) refer to the computational throughput of the hardware.\n\nIn 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**.\n\nOnce 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.", "claims_and_evidence": "None", "methods_and_evaluation_criteria": "Sounds good", "theoretical_claims": "I did not find theoretical claims or analysis in this paper.", "experimental_designs_or_analyses": "It sounds. But I hope there is additional comparison as described in the second weakness that I wrote in the weakness section.", "relation_to_broader_scientific_literature": "This work can have a broader effect on the medical domain, but I am not sure in the machine learning field.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\nThe proposed method effectively applies the four-color theorem to cell instance segmentation, introducing a novel approach to the problem.\nThe authors provide an extensive ablation study across multiple datasets, demonstrating the robustness of their method.\nThe methodology is straightforward and easy to follow, making it accessible to readers.\n\nWeaknesses & Areas for Improvement:\n1. Introduction & Justification of Claims\nThe paper argues that distance mapping models significantly increase computational overhead and model complexity. However, there exist methods with fewer parameters or requiring fewer FLOPs. The authors should provide a clearer comparison to substantiate this claim.\n\n2. Comparison with Competitive Methods\nThe authors should compare their approach with the recent methods in [1]. Since the proposed method based on the four-color theorem is not inherently limited to cell instance segmentation, it would be beneficial to demonstrate its effectiveness on additional segmentation datasets.\nIf the proposed method cannot be validated on diverse datasets, this work may be more suitable for a specialized medical imaging conference such as MICCAI.\n\n3. Presentation of Complexity and Performance Metrics\nCurrently, the model complexity details are presented separately in Table 1, while performance metrics are distributed across Tables 2–4. Combining these into a single table would facilitate an easier comparison of performance and computational efficiency.\n\n4. Equation Clarity and Notation Issues\n\n- Equation (5) & (6): Does the index 𝑖 represent the image index {1,…,𝑁}?\n\n- Equation (5): It appears that 𝑏 represents the background and 𝑓 represents the foreground. However, the notation for 𝑓 is reused in \n- Equations (9) and (10), leading to potential confusion.\n\n- Equation (5): Is all 𝑌^𝑖[:,0] assigned to 𝑌^𝑏? Please clarify.\n\n- Equation (7): How does 𝑖 appear in 𝑌^{𝑏,𝑖} when there is no 𝑖 in the input?\n\n- Equations (9) & (10): There is no explanation of how the feature 𝑓 is obtained. This should be explicitly described.\n\n- Line 143: Given that 𝑖=1,…,𝑁 does this imply that 𝑖 and 𝑗 both range over {1,…,𝑁}? If so, how is 𝛽 again of size 𝑁? Additionally, the range of index 𝑗 should be explicitly defined.\n\n- Line 306: The function 𝑓 mapping 𝑃 to 𝐶 is introduced, but it shares the same notation as a previously defined feature. Consider renaming to avoid ambiguity.\n\n5. Minor Issues & Typographical Errors\n\n- Line 321: \"Where\" → \"where\"\n\n- Line 300: \"n represents\" → \"where 𝑛 represents\"\n\n- Equation (15): \"L_cls.\" → \"L_cls\"\n\n**Overall Assessment**\n\nThe proposed method presents a novel adaptation of the four-color theorem for cell instance segmentation and achieves significant performance improvements. However, there are multiple issues related to equation clarity, notation consistency, and typographical errors. Furthermore, the lack of validation on diverse datasets and absence of comparisons with recent works such as [1] raise concerns about the generalizability and competitiveness of the approach.\n\nGiven these limitations, I am inclined to take a negative stance on this submission.\n\nReference:\n[1] Chen, Zhen, et al. \"Un-SAM: Universal Prompt-Free Segmentation for Generalized Nuclei Images.\" arXiv preprint arXiv:2402.16663 (2024).", "other_comments_or_suggestions": "See the strength and weakness part.", "questions_for_authors": "See the strength and weakness part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pXwWtFUHka", "reviewer": "Reviewer_RU3q", "summary": "This paper introduces a new approach to cell instance segmentation based on the Four-Color Theorem from graph theory. The authors propose reformulating instance segmentation as a constrained semantic segmentation problem using only four classes. This method simplifies the task by ensuring that adjacent cells receive different labels, allowing instance differentiation without explicit instance segmentation. Evaluated on three biomedical image datasets\n\n## Update after rebuttal\nI have adjusted my score to reflect the improvements. Please see my reply to the rebuttal below.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://drive.google.com/file/d/1dERoIrcnDklZhwcJDs5zXBBAFn7-I5u3/view?usp=sharing).\n\n**1. Generalization in Complex Scenarios**\n\nYou 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). \n\nThe 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.\n\n **2. Motivation and Practical Relevance of FCIS**\n\nThe 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.\n\n- **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.\n\n- **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.\n\n**3. Inclusion of CellPose as a Baseline**\n\nWe sincerely thank you for pointing out the omission of CellPose. In response, \n- 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.\n- 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. \n\n**4. Clarification on Handling Overlaps and Graph Construction**\n\n- **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.\n\n- **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.\n\n **5. Literature Citation**\n\nTo 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:\n\n- A greedy coloring algorithm with theoretical guarantees\n- An encoding transformation strategy that addresses non-uniqueness\n- A training pipeline that converts instance segmentation into semantic prediction\n\nHence, We will enrich the Related Work section to include broader references from graph theory for segmentation.\n\nOnce 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.", "claims_and_evidence": "- Instead of detecting individual cell instances explicitly, the method treats segmentation as a semantic task where each foreground cell is assigned one of four colors to ensure instance differentiation. The authors present a greedy four-color encoding algorithm (Algorithm 1) that assigns colors while ensuring that adjacent cells have distinct labels. They demonstrate that this reduces model complexity compared to detection- and contour-based approaches.\n\n- Directly training on four-color encoding leads to instability due to class imbalance and non-unique encoding. Authors propose binary foreground-background segmentation and four-class label assignment within the foreground. An ablation study shows that using four-color encoding directly degrades performance. The asymptotic training method significantly improves performance metrics.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria generally make sense for the problem of cell instance segmentation in biomedical imaging. However, there are some important considerations regarding their real-world applicability. The method assumes that cells are adjacent but not significantly overlapping. In cases where cells heavily overlap (e.g., thick tissue slices, some fluorescence images) or foreground/background distinction is not clear (TEM images, brightfield microscopy etc.), adjacency might be unclear, leading to errors in differentiation. Competing models like Cellpose can explicitly model overlapping cells using shape priors, which this method does not. The greedy four-color algorithm assumes that cells behave like planar regions. In reality, cells can have irregular or elongated shapes, making adjacency more complex. Some image applications require segmenting cell bodies and extension (e.g. hepatocytes in cytotoxic assays). The method assumes compact cell regions.", "theoretical_claims": "- Any planar graph can be colored with at most four colors such that no two adjacent regions share the same color. The authors provide a proof sketch that shows how cell segmentation map can be transformed to a planar graph, where each cell is a node and each cell boundary defines an edge. \n\n- The four-color encoding is non-unique. This ambiguity can cause inconsistencies during training. A detailed proof is provided in the supplementary material (not checked) which shows that a mapping function that  transforms the predicted results to a four-color encoding does exist.", "experimental_designs_or_analyses": "- The experimental design is structured to compare the four-color method against existing cell segmentation approaches. However, some choices may bias the results or leave important questions unanswered. The datasets do not include highly overlapping cell populations. So, the methods generalizability is in question. \n\n- Cellpose, a leading generalist model for cell segmentation, is missing in the comparison. This is major gap since Cellpose is robust across various imaging conditions. \n\n- Ablations studies support the paper's claims and is a strong point of the experimental design.", "relation_to_broader_scientific_literature": "The paper falls into broader category of cell instance segmentation. The paper challenges the need for explicit instance detection by showing that cells can be differentiated purely via semantic segmentation with a constrained label space (four colors). \n\nNo prior work is cited on using four-color encoding for instance segmentation, leaving its connection to past literature vague. Similar theorems were previously used in image processing and graph coloring etc.", "essential_references_not_discussed": "The authors compare their model mostly against contour-based, detection-based, and distance-based methods (HoverNet, DoNet, CPP-Net, etc.). Although Cellpose may not fall into these categories, it is widely regarded as one of the most robust and generalist cell segmentation models, capable of handling touching and overlapping cells across diverse datasets. The fact that this paper only briefly mentions it and does not include it in the benchmarks raises serious concerns about completeness of experimental validation. It is very fast and works for any type of images (H&E, cryo-EM, TEM, confocal, bright field etc.). It is only cited once in this sentence \"The advancement of deep learning revolutionized automated cell segmentation ...\". There are three versions of CellPose already, most recent of which is recently published. The version cited is from 2021.", "other_strengths_and_weaknesses": "Strength:\nBy proving that any cell segmentation map can be represented as a planar graph where adjacent cells can be assigned different colors using at most four labels, the authors introduce a greedy four-coloring algorithm that enforces instance separation without requiring explicit instance segmentation masks. \n\nWeakness:\nThe approach makes instance differentiation emerge from the color constraints, but it’s not entirely clear how well this works for very crowded or irregularly shaped cells. As the method has no ways of incorporating expected size highly overlapping irregular shapes cell populations generate spurious cell instances (see Figure 9 in supplementary)", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Algorithm 1 starts with a cell graph where V is the set of cells. This algorithm does not discuss how V is obtained from the foreground. Does the algorithm assumes that each connected component in the foreground will be corresponding to a cell instance? If that is the case then why cell coloring is so important as identifying adjacent cells would be less relevant.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6ObRXKGdor", "reviewer": "Reviewer_YyUg", "summary": "The paper presents a novel cell instance segmentation method inspired by the four-color theorem, which simplifies the segmentation task by transforming it into a four-class semantic segmentation problem. The key contributions include:\n\nFour-Color Encoding Scheme: Cells are treated as \"countries\" and tissues as \"oceans,\" allowing the use of a four-color encoding to ensure adjacent cells receive distinct labels.\n\nAsymptotic Training Strategy: This step-by-step approach first distinguishes foreground and background, then predicts categories within the foreground, addressing class imbalance.\nEncoding Transformation Method: This method maps the predicted output to a consistent four-color representation, ensuring training stability.\n\nTheoretical Analysis: The authors prove the global optimality of the greedy algorithm for cell coloring under specific conditions.\nEmpirical Validation: The method achieves state-of-the-art performance on three datasets (BBBC006v1, DSB2018, PanNuke), demonstrating robustness and reduced computational complexity.\n\nThe proposed method effectively balances performance and efficiency, offering a promising solution for biomedical image segmentation.\n\n## update after rebuttal\nThe responses are satisfactory, and we acknowledge the improvements made in both theoretical and empirical aspects.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://drive.google.com/file/d/1dERoIrcnDklZhwcJDs5zXBBAFn7-I5u3/view?usp=sharing).\n\n**1. Generalizability to Diverse Imaging Modalities**\n\nThank 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**.\n\nAt 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.\n\n **2. Effect of Non-Uniqueness in Encoding**\n\nAs 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. \n\nTo 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.\n\n **3. Computational Efficiency and Hardware Benchmarks**\n\nThank 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.\n\n**4. Theoretical Assumptions and Real-World Applicability**\n\nAs 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. \n\nThank you again for your insightful and constructive suggestion.\n\n**5. Summary and Pseudocode Placement**\n\nThank 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.\n\nMeantime, 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.\n\nOnce 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.", "claims_and_evidence": "The claims made in the submission are largely supported by clear and convincing evidence. The authors present a novel approach to cell instance segmentation using the four-color theorem, which is well-explained and validated through extensive experiments. The four-color encoding scheme is effectively demonstrated to transform the segmentation task into a simpler semantic segmentation problem, and the asymptotic training strategy is shown to address class imbalance issues. The encoding transformation method is theoretically justified and empirically proven to enhance model convergence and performance. The state-of-the-art performance on three datasets (BBBC006v1, DSB2018, and PanNuke) further substantiates the effectiveness of the proposed method.\n\nHowever, there are certain aspects that could benefit from additional clarification. The generalizability of the method across diverse cell types and imaging modalities is not fully explored, and further discussion or experiments would be valuable to demonstrate its broader applicability. Additionally, while the impact of the non-uniqueness of encoding is addressed through the encoding transformation method, a more detailed analysis of its effect on model performance would strengthen the paper. The computational efficiency claims, though supported by a comparison of computational complexity, could be further bolstered by detailed benchmarks on standard hardware configurations. Lastly, the theoretical analysis of the global optimality of the greedy algorithm, while convincing, relies on specific assumptions about cell distribution and structure, which could be more thoroughly discussed in the context of real-world biomedical images. Overall, the submission presents a robust and innovative approach, with minor areas for enhancement to fully address potential limitations.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are well-suited for cell instance segmentation in biomedical images. The four-color encoding scheme simplifies segmentation by transforming it into a four-class semantic task, while the asymptotic training strategy addresses class imbalance. The encoding transformation method ensures training stability by handling non-uniqueness in encoding. The negative sampling constraint enhances the model's ability to distinguish adjacent cells. The evaluation on three diverse datasets (BBBC006v1, DSB2018, PanNuke) using standard metrics (DICE, AJI, DQ, SQ, PQ) validates the method's robustness and generalizability. Overall, the approach effectively addresses key challenges in cell segmentation with strong empirical support.", "theoretical_claims": "As a whole, there are no logical errors in the algorithm mentioned in the article, but I am concerned about the following:\nThis strategy relies on accurate initial segmentation. If there are errors in the initial segmentation (such as cell adhesion is not segmented correctly), the four-color strategy may not be able to effectively distinguish instances and affect the final result.\nOn large-scale high-resolution pathological images, the computational complexity of the four-color strategy is high, especially when constructing the adjacency graph and optimizing the coloring, which may affect the reasoning efficiency.", "experimental_designs_or_analyses": "The experimental designs and analyses in the paper are sound and appropriate for evaluating the proposed cell instance segmentation method. The authors used three diverse datasets and standard metrics to comprehensively assess performance, demonstrating robustness and superiority over state-of-the-art methods. Ablation studies and convergence analysis further validate the effectiveness of the proposed techniques.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-aligned with the broader scientific literature, particularly in biomedical image segmentation and graph theory. The use of the four-color theorem is a novel adaptation of a classic graph theory result to address the challenge of distinguishing adjacent cells in segmentation tasks. This approach simplifies the problem by converting it into a four-class semantic segmentation task, which is a significant departure from traditional methods that often struggle with computational complexity and accuracy in high-density cell environments.\n\nThe asymptotic training strategy and encoding transformation method build on existing deep learning techniques to address training instability and non-uniqueness of encoding, which are common issues in semantic segmentation. These strategies are innovative solutions that enhance model robustness and performance, aligning with ongoing research efforts to improve segmentation accuracy and efficiency.\n\nThe theoretical analysis provided in the paper, which proves the global optimality of the greedy algorithm under specific conditions, contributes to the understanding of graph coloring in biomedical images. This analysis is grounded in established principles of graph theory and combinatorial optimization, providing a rigorous foundation for the proposed method.\n\nOverall, the paper integrates well with the broader literature by offering a new perspective on a longstanding problem in biomedical imaging, leveraging both theoretical insights from graph theory and practical advancements in deep learning.", "essential_references_not_discussed": "In my opinion, there are no essential related works missing from the paper that would significantly alter the understanding of its key contributions. The authors have adequately covered the relevant literature in the fields of biomedical image segmentation, graph theory, and deep learning. The application of the four-color theorem is a unique approach that addresses specific challenges in cell segmentation, and the paper provides sufficient context for its contributions.", "other_strengths_and_weaknesses": "The paper presents an innovative application of the four-color theorem to cell instance segmentation, offering a novel perspective on a challenging problem in biomedical imaging. The transformation of the segmentation task into a four-class semantic segmentation problem is a significant contribution, simplifying the process and reducing computational complexity. The theoretical analysis and empirical validation on multiple datasets further strengthen the paper's credibility.\n\nHowever, the generalizability of the method to diverse imaging modalities and complex cell structures remains unexplored. The reliance on accurate initial segmentation and the need for post-processing to correct errors also pose limitations. Addressing these issues could enhance the robustness and applicability of the proposed approach. Overall, the paper's originality and potential impact are noteworthy, but further work is needed to address its limitations.", "other_comments_or_suggestions": "In my opinion, the summary part of the paper is relatively small, and the innovation, experiment, advantages and disadvantages of the paper should be sorted out. However, there does not seem to be enough room for this, and I suggest that the pseudocode be placed in additional material in order to expand the conclusions.", "questions_for_authors": "I have no other questions here.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a novel application of the four-color theorem to cell instance segmentation by reformulating the problem as a constrained four-class semantic segmentation task.  The method simplifies instance differentiation, improves efficiency, and is supported by strong theoretical grounding and experimental validation.

All reviewers seem to agree that the approach is innovative and has value to the community. Some concerns were raised about generalisability to more complex or overlapping cell structures, clarity of equations, and missing baselines like Cellpose. However, the authors addressed these in the rebuttal with additional experiments and clarifications, leading most of the reviewers to raise their scores.

The idea is original, the paper is technically sound, and the method has practical value for biomedical image analysis. It makes a meaningful contribution that fits well within the ICML program.
Decision: Accept (poster)