Label-efficient Segmentation via Affinity Propagation
Authors: Wentong Li
Yuqian Yuan
Song Wang
Wenyu Liu
Dongqi Tang
Jian liu
Jianke Zhu
Lei Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Computer Vision
Segmentation
Weakly-supervised Learning
TL;DR: A novel universal component for weakly-supervised segmentation.

Abstract: Weakly-supervised segmentation with label-efficient sparse annotations has attracted increasing research attention to reduce the cost of laborious pixel-wise labeling process, while the pairwise affinity modeling techniques play an essential role in this task. Most of the existing approaches focus on using the local appearance kernel to model the neighboring pairwise potentials. However, such a local operation fails to capture the long-range dependencies and ignores the  topology of objects. In this work, we formulate the affinity modeling as an affinity propagation process, and propose a local and a global pairwise affinity terms to generate accurate soft pseudo labels. An efficient algorithm is also developed to reduce significantly the computational cost. The proposed approach can be conveniently plugged into existing segmentation networks. Experiments on three typical label-efficient segmentation tasks, i.e. box-supervised instance segmentation, point/scribble-supervised semantic segmentation and CLIP-guided semantic segmentation, demonstrate the superior performance of the proposed approach.

Label-efficient Segmentation via Affinity Propagation
Wentong Li Yugian Yuan' Song Wang', Wenyu Liu',
Dongqi Tang?, Jian Jianke Zhu'; Lhi Lei Zhang² IZhejiang University Ant Group Thhe Hong Kong Polytechnical University
https://LiWentonet github. io/ so/apro/
Abstract
Weakly-supervised segmentation with label-efficient sparse annotations has at- tracted increasing research attention reduce the cost of laborious pixel-wise labeling process, while the pairwise affinity modeling techniques play an essen- tial role in this task. Most of the existing approaches focus on using the local appearance kernel to model the neighboring pairwise potentials. However, such local operation fails capture the long-range dependencies and ignores the topology of objects. In this work, we formulate the affinity modeling as an affinity propagation process, and propose a local and a global pairwise affinity terms generate accurate soft pseudo labels. An efficient algorithm is also developed to reduce significantly the computational cost. The proposed approach can be conveniently plugged into existing segmentation networks. Experiments on three typical label-efficient segmentation tasks, i.e. box-supervised instance segmenta- tion, point/scribble-suervee semantic segmentation and CLIP- CL.IP-guided semantic segmentation, demonstrate the superior performance of the proposed approach.
Introduction
Segmentation a widely studied problem in computer vision, aiming at generating a mask prediction for given image, e.g., grouping each pixel to object instance (instance segmentation) assigning each pixel a category label (semantic segmentation). While having achieved promising performance, most of the existing approaches the pixel-wise mask annotations, incurring tedious labeling costs [1]. Weakky-suuprrvsee methods have been proposed to reduce the dependency on dense pixel-wise labels with label-efficient sparse annotations, such as points [2-4], scribbles [5-7], bounding boxes [8-11] and image-level labels [12- 15]. Such methods make dense segmentation more accessible with less annotation costs for new categories or scene types.
trained in fully supervised manner, which heavily depend
Most of the existing weakly-superrvve appearance kernel to model the neighboring pairwise affinities, where spatially nearby pixels with similar color (i.g., LAB color space [8, 3] or RGB color space [13, 16, 17, 10]) are likely to be in the same class. Though having proved to be effective, these methods suffer from two main limitations. First, the local operation cannot capture global context cues and capture long-range affinity dependencies. Second, the appearance kernel fails to take the intrinsic topology of objects into account, and lacks capability of detail preservation.
segmentation methods [16, 13, 8, 17, 10] adopt the local
To address the first issue, one can directly enlarge the kernel size to obtain large receptive filed. However, this will make the segmentation model insensitive to local details and increase the com- putational cost greatly. Some methods [14, 12] model the long-range affinity via random walk [18], but they cannot model the fine-grained semantic affinities. As for the second issue, the baseb
Equul contribution Correspondence author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

box-supervisdd instance segmmmtation
pointscribale supersised semantic sequenlation
annolation-f free semantic segmentation
prodiction
pundittion
pocudoo label
pocvado labe
relined
APro
supervise
input Image
Input image
input image
prodiction
supervise
(b)
supervise
(c)
Figure 1: The proposed approach upon the typical weakly segmentation tasks with label-efficient annotations, including (a) sox-supervised instance segmentation, (b) point/scribble- supervised semantic segmentation and (c) annotation-free semantic segmentation with CLIP pre- trained model.
approaches [7. 19] are able to preserve the geometric structures of objects, and employ the minimum spanning tree [20] to capture the pairwise relationship. However, the affinity interactions with distant nodes will decay rapidly as the distance increases along the spanning tree, which still focuses on the local nearby regions. LTF-V2 [21] enables the long-range tree-based interactions but it fails model the valid pairwise affinities for label-efficient segmentation task.
With the above considerations, we propose a novel component, named Affinity Propagation (APro), which can easily embedded in existing methods for label-efficient segmentation. Firstly, we define the weakly-superviser segmentation from a new perspective, and formulate it as uniform affinity propagation process. The modelled pairwise term propagates the unary term to other nearby and distant pixels and updates the soft pscudo labels progressively. Then, introduce the global affinity propagation, which leverages the topology-awes tree-based graph and relaxes the geometric constraints of spanning tree to capture the long-range pairwise affinity. With the efficient design, the (N2) complexity of brute force implementation is reduced to O(N log N), and the global be performed with much less resource consumption for practical applica- tions. Although the long-range pairwise affinity captured, it inevitably brings in noises based on numerous pixels in a global view. To this end, introduce local affinity propagation encourage the piece-wise smoothness with spatial consistency. The formulated APro can be embedded into the existing segmentation networks to generate accurate soft pseudo labels online for unlabeled regions. As shown in Fig. I, it can be seamlessly plugged into the existing segmentation networks for various tasks to achieve reakly-supervisee segmentation with label-efficient sparse annotations.
propagation approach
We perform experiments on three typical label-efficient segmentation tasks, i.e. box-supervised semantic segmentation and annotation-fres semantic
instance segmentation, point/scribble-suervviii segmentation with pretrained CLIP model, and the results demonstrated the superior performance of our proposed universal label-efficient approach.
2 Related Work
Label-efficient Segmentation. Label-efficient segmentation, which is based on the weak supervi- sion from partial or sparse labels, has been widely explored [1]. Different from semi-supervised settings [22, 23], this paper mainly focuses on the segmentation with sparse labels. In earlier litera- ture [24-28], it primarily pertained image-level labels. Recently, diverse sparse annotations have been employed, including point, scribble, bounding box, image-level label and the combinations of them. We briefly review the suuel-supee instance segmentation, semantic segmentation and panoptic segmentation tasks in the following.
For wcakly-supervised instance segmentation, box-supervised methods [16, 8, 17, 9, 29, 30, 11, 10, 31] are dominant and perform on par with fully-supervised segmentation approaches. Besides, the "points + bounding box" annotation can also achieve competitive performance [32, 33]. As for supkkly-uperrviee semantic segmentation, previous works mainly focus on the point-level supervision [2, 34, 6] and scribble-level supervision [5, 35, 36], which utilize the spatial and color information of the input image and are trained with two stages. Liang et al. [7] introduced an effective tree energy loss based on the low-level and high-level features for point/scribble/bloek- supervised semantic segmentation. For semantic segmentation, the supervision of image-level labels has been well explored [12, 37, 15, 14]. Recently, some works have been proposed make use of the large-scale pretrained CLIP model [38] to achieve weakly-supervised or annotation free semantic

---

Network
Cg
Y
f (I) Y
Painwise Affinity Propagation
Global affinity propagation
Local affinity propagation
(a)
Figure 2: Overview of our APro approach. (a) The general weakly supervised segmentation frame- work with the proposed pairwise affinity propagation. (b) The proposed approach consists of global affinity propagation (GP) and local affinity propagation (LP) to generate accurate pseudo labels.
segmentation [39, 40]. In addition, with single and multiple points annotation have been proposed. In this paper, we aim to develop universal component for various segmentation tasks, which can be easily plugged into the existing segmentation networks.
panoptic segmentation methods [3, 41, 4]
Pairwise Affinity Modeling. Pairwise affinity modeling plays important role in many computer vision tasks. Classical methods, like CRF [42], make full use of the color and spatial information to model the pairwise relations in the semantic labeling space. Some works it as post-processing module [43], while others integrate it as jointly-triied part into the deep neural network [44, 45]. Inspired by CRF, some recent approaches explore the local appearance kernel tap the neighboring pairwise affimities, where spatially nearby pixels with similar colors are more likely to fall into the same class. Tian et al. [8] proposed the local pairwise loss, which models the neighboring relationship in LAB color space. Some works [10, 16, 17] focus on the pixel relation in RGB color space directly, and achieve competitive performance. However, the local operation fails to capture global context cues and lacks the long-range affinity dependencies. Furthermore, the appearance kernel cannot reflect the topology of objects, missing the details of semantic objects. To model the structural pair-wise relationship, tree-based approaches [7, 19] leverage the minimum spanning tree [20] to capture the topology of objects in the image. However, the affinity interactions with distant nodes decay rapidly as the distance increases along the spanning tree. Besides, Zhang al. [35] proposed an affinity network to convert an image to weighted graph, and model the node affinities by the graph neural network (GNN). Different from these methods, in this work we model the pairwise affinity from a new affinity propagation perspective both globally and locally.
3 Methodology
In this section, introduce our proposed affinity propagation (APro) approach to label-efficient segmentation. First, we define the problem and model the APro framework in Section 3.1. Then, we describe the detailed pairwise affinity propagation method in Section 3.2. Finally, we provide an efficient implementation of our method in Section 3.3.
3.1 Problem Definition and Modeling
Given an input image - { with N pixels and its available sparse ground truth labeling Y (i.e. points, scribble, or bounding box), and let (I) be the output of a segmentation network with the learnalle parameters f, the whole segmentation network can be regarded as a neural network optimization problem as follows:
min è
where Ly is ground truth loss the set of labeled pixels Ωy with Y and C. is a loss the unlabeled regions Q2 with the pseudo label Y. As shown in Fig. 2-(a), our goal is to obtain the accurate pseudo label Y by leveraging the image pixel affinities for unlabeled regions.
As in the classic MRF/CRF model [46, 42), the unary term reflects the per-pixel confidence of assigning labels, while pairwise term captures the inter-pixel constraints. We define the generation of
3

---

pseudo label Y as an affinity propagation process, which can be formulated as follows:
V/ Σ o(z;))((;; JET
(2)
where o(x; denotes the unary potential term, which is used align yjj and the corresponding network prediction based on the available sparse labels. (b;;; indicates the pairwise potential, which models the inter-pixel relationships constrain the predictions and produce accurate pseudo labels. I is the region with different receptive fields. 2j is the summation of pairwise affinity ( Xz)) along with j normalize the response.
Notably, we unify both global and local pairwise potentials in an affinity propagation process formulated in Eq. 2. As shown in Fig. 2-(b), the global affinity propagation (GP) can capture the pairwise affimities with topological consistency in global view, while the local affinity propagation (LP) can obtain the pairwise affinities with local spatial consistency. Through the proposed component, the soft pseudo labels Y can be obtained. We assign each y; from GP and LP with the network prediction p: and directly employ the distance measurement function as the objective for unlabeled regions S2. Simple L1 distance is empirically adopted in our implementation.
3.2 Pairwise Affinity Propagation
3.2.1 Global Affinity Propagation
We firstly provide a solution to model the global affinity efficiently based on the input image. Specifically, we represent an input image as 4-connected planar graph G. where each node is adjacent to up to 4 neighbors. The weight of the edge measures the image pixel distance between adjacent nodes. Inspired by tree-based approaches [47, 19], we employ the minimum spanning tree (MST) algorithm [20] to remove the edge with large distance to obtain the tree-based sparse graph Gr. i.e., 9r t- GS) and Gr = (V, where = {V.) N the set of nodes and = (E. J denotes the set of edges.
Then, we model the global pairwise potential by iterating over each node. To be specific, we take the current node as the root of the spanning tree Gr and propagate the long-range affinities to other nodes. While the distant nodes along the spanning tree need to pass through nearby nodes along the path of spanning tree, the distance-insensitive max affinity function can alleviate this geometric constraint and relax the affinity decay for long-ran oangrange nodes. Hence, we define the global pairwise potential V as follows:
Wk. C
S ( x;) = 1,) =
max ((R.)EE,
AjEV
where T denotes the global tree. EE, is the set of edges in the path of T from node j to node i. Wx, indicates the edge weight between the adjacent nodes A and 4, which is represented as the Euclidean distance between pixel values of two adjacent nodes, i.e., Wxg1 14g 41 Cg controls the degree of similarity with the long-range pixels. In this way, the global affinity propagation (GP) process to obtain the soft label y can be formulated as follows:
Σ ((L)) JEV
=- -E (xi,
9
JEV
where interactions with distant nodes are performed over tree-based topology. In addition to utilizing low-level image, we empirically employ high-level feature as input to propagate semantic affinity.
3.2.2 Local Affinity Propagation
The long-range pairwise affinity is inevitably noisy since it is computed based on the susceptible image features in a global view. The spatially nearby pixels are more likely to have the same label, while they have certain difference in color and intensity, eíc. Hence, we further introduce the local affinity propagation (LP) to promote the piece-wise smoothness. The Gaussian kernel is widely used to capture the local relationship among the neighbouring pixels in previous works [45, 8, 10]. Different from these works, we define the local pairwise affinity via the formulated affinity propagation process. The local pairwise term vh, is defined as:
I J1,-18 1,1
(1,,, = KCI,,,,) = exp
(5)
C
JEN(1)

---

where K. denotes the Gaussian kernel, (()) is the set containing all local neighbor pixels. The degree of similarity controlled by parameter S.- Then the pseudo label y can be obtained via the following affinity propagation:
1
Σ (z))),(())))) 4- Σ 2x1,, JEN())
(6)
JEN(()
where the local spatial consistency is maintained based on high-contrast neighbors. To obtain a robust segmentation performance, multiple iterations required. Notably, our L.P process ensures fast convergence, which is 5x faster than McanField-based method [10, 42]. The details can be found in the experimental section 4.4.
3.3 Efficient Implementation
Given a tree-based graph Gr = {VVE) in the GP process, we define the maximum w value of the path through any two vertices the transmission cost C. One straightforward approach to get uf of vertex i is to traverse each vertex j by Depth First Search or Breadth First Search to get the transmission cost Ct, accordingly. Consequently, the computational complexity required to acquire the entire output 1 is O(N²), making it prohibitive in real-world applications.
Instead of calculating and updating the transmission cost of any two vertices, we design lazy update algorithm to accelerate the GP process. Initially, each node is treated as a distinct union, represented by U. Unions are subsequently connected based on each edge WK, ascending order of w. We show that when connecting two unions Us and Ui, wx.t is equivalent to the transmission cost for all nodes within Ut and Un This proved in the supplementary material.
To efficiently update values, we introduce Lazy Propagation scheme. We only update the value of the root node and postpone the update of its descendants. The update information is retained in lazy tag Z and is updated as follows:
rank > Ug.ank, 2(8) = 2(0) + expp(-wu.//G, S)(()) ()) 2()), otherwise,
/x S)(())
where S(8)+ =E matrix A. k² /1" denotes the root node of node k/1.
Ejeu. dj. means different inputs, including the dense prediction ((z) and all-one
Once all unions are connected, the lazy tags can be propagated downward from the root node to its descendants. For the descendants, the global affinity propagation term is presented as follows:
LProp(o); +
Σ
3(0),,
rEAsooy (QU())
where Asegy (i) represents the ascendants of node i the tree Gr. As shown Algorithm 1, the disjoint-set data structure is employed to implement the proposed algorithm. In our implementation, a Path Compression strategy is applied, connecting each node on the path directly to the root node. Consequently, it is sufficient to consider the node itself and its parent node to obtain LProp.
Time complexity. For each channel of the input, the average time complexity of sorting is O(N log N). In the merge step, we utilize the Path Compression and Union-by-Rand strategies, which have complexity of (({(N))48). After merging all the concatenated blocks, the lazy tags can be propagated in (NN) time. Hence, the overall complexity is O(N log N). Note that the batches and channels are independent of each other. Thus, the algorithm can be executed parallel for both batches and channels for practical implementations. As a result, the proposed algorithm reduces the computational complexity dramatically.
Experiments
4.1 Weakly-supervised Instance Segmentation
Datasets. in prior arts [8, 9, 16, 17], we conduct experiments on two widely used datasets for the weakly box-supervised instance segmentation task:
COCO [49], which has 80 classes with 115K train2017 images and 5K va12017 images.
5

---

Algorithm 1: Algorithm for GP process
Input: Tree Gr E Nex2; Pairwise distance w E IR,; Dense predictions x(x) E R Vertex num N; Edge num N 1; Set of vertices V.
Output: y E R
A 1 ERN
F N0,,
Initialize each vertex as a connected block Quick Sort
Sort (9r, w) in ascending order of w.
for (k, E Gr. w, E w do
- find(k), t find(!)
Find the root node with Path Compression > Add lazy tag
Update 2 (()). (())a (()).. (A))))
S. < So then L swap(a, b)
D Merge by Rank
Fb +
> Merge two connected blocks
for E V do
p find(v)
for ā E A} do
p = u then if
LProp( 2(0). 8, else
LProp(0) 2(0), + 2()) + 6,
30
[Pro
LProp(o]s
> Normalization
return y
Pascal VOC [43] augmented by SBD [50] based on the original Pascal VOC 2012 [51], which has 20 classes with 10,582 trainaug images and 1,449 val images.
Base Architectures and Competing Methods. In the evaluation, we apply our proposed APro to Iwo representative instance segmentation architectures, SOLOv2 [52] and Mask2Former [53], with different backbones (i.e., ResNet [54],
[55]) following Box2Mask [11]. We compare our approach with its counterparts that model the pairwise affinity based on the image pixels without modifying the base segmentation network for box- superridd setting. Specifically, the compared methods include Pairwise Loss [8]. TreeEnergy Loss [7] and CRF Loss [10]. For fairness, we re-implement these models using the default setting in MMDetection [56].
Implementation Details. We follow the commonly used training settings each dataset in MMDetection [56]. All models are initialized with ImageNet [57] pretrained backbone. For SOLOv2 framework [52], the scale jitter is used, where the shorter image side is randomly sampled from 640 to 800 pixels. For Mask2Former framework [53], the large-scale jittering augmentation scheme [58] employed with random scale sampled within range 10.1, 2.0], followed by fixed size crop to 1024x1024. The initial learning rate is set to 10-4 and the weight decay is 0.05 with 16 images per mini-batch. The box projection loss [8, 9] is employed to constrain the network prediction within the bounding box label as the unary term Ø. COCO-style mask AP (%) is adopted for evaluation.
Quantitative Results. Table shows the quantitative results. We compare the approaches with the same architecture for fair comparison. The sfate-of-the-art methods are listed for reference. One can that our APro method outperforms its counterparts across Pascal VOC and COCO datasets.
Pascal VOC [43] val. Under the SOLOv2 framework, our approach achieves 37.1% % AP and 38.4 18.4% AP with 12 epochs and 36 epochs, respectively, outperforming other methods by 1.4%-2.5% mask AP with ResNet-50. With the Mask2Former framework, our approach also outperforms its counterparts. Furthermore, with the Swin-L backbone [55], our proposed approach achieves very promising performance, 49.6% mask AP with 50 epochs.
COCO [49] val. Under the SOLOv2 framework, our approach achieves 32.0% AP and 32.9% AP with 12 epochs and 36 epochs, and surpasses its best counterpart by 1.0% AP and 0.4% AP using ResNet-50, respectively. Under the Mask2Former framework, our method still achieves the best performance with ResNet-50 backbone. Furthermore, equipped with stronger backbones, our approach obtains more robust performance, achieving 38.0% mask AP with ResNet- 101, and 41.0% mask AP using Swin-L backbone.

---

Table Quantitative results ($4.1) on Pascal VOC [43] and COCO val [49] with mask AP(%).
Pascal VOC
COCO
Method
Backbone
#Epoch
AP
AP
AP
AP50
AP
BBTP (Nodiesig) [16]
Res
12
23.1
54.1
17.1
21.1
45.5
17.2
BoxInst (eVeR2))
ResNet-50
36
34.3
58.6
31.8
54.4
322.5"
DiscoBox pocv21 [17]
ResNet-50
35.5
31.4
52.6
32.2
BoxLevelset (BCCV23) []]
ResNet-50
36.3
64.2
35.9
31.4
53.7
31.8
SOLOv2 Framework
Pairwise Loss (CVPR2)) [8]
ResNet-50
12
35.7
64.3
35.1
31.0
52.8
31.5
TreeEnergy Loss (CVPR22) [7]
ResNet-50
12
35.0
64.4
34.7
30.9
52.9
31.3
CRF Loss (evises] [10]
ResNet-500
12
35.0
64.7
34.9
30.9
53.1
31.4
(Pur()ura)
ResNet-50
12
37.1
65.1
37.0
32.0
53.4
32.9
Pairwise (CVPR2))
[8]
ResNet-50
36
36.3
63.4
38.1
32.4
$4.5
33.4
TreeLnerry Loss (CVPR22)
ResNet-50
36
36.1
63.5
36.1
31.4
54.0
31.2
CRF Loss (CV1623)
[10]
ResNet-50
36
35.9
64.0
35.7
32.5
54.9
33.2
APro(Durs)
ResNet-50
38.4
39.8
32.9
55.2
33.6
APro(Durs)
ResNet-101
40.5
42.6
34.3
57.0
35.3
Fask2Former Framework
Pairwise Loss (CVои)) [8]
ResNet-50
12
35.2
62.9
33.9
33.8
57.1
34.0
TreeEnergy Loss (cVPи))
[7]
ResNet-50
12
36.0
65.0
34.3
33.5
56.7
33.7
CRP Loss (CV1623) [10]
ResNet-50
12
35.7
64.3
35.2
33.5
57.5
33.8
APro(Dura)
ResNet-50
12
37.0
65.1
37.0
34.4
57.7
35.3
APro(Dura)
ResNet-50
50
42.3
70.6
44.5
36.1
62.0
36.7
APro(Durs)
ResNet-101
50
43.6
72.0
45.7
38.0
63.6
38.7
APro(Durs)
Swin-L
50
49.6
77.6
53.1
41.0
68.3
41.9
Qualitative Results. Fig. illustrates the visual comparisons on affinity maps of our APro and other approaches, and Fig. 4 compares the segmentation results. One can clearly see that our method captures accurate pairwise affinity with object's topology and yields more fine-grained predictions.
4.2 Weakly-supervised Semantic Segmentation
Datasets. We conduct experiments on the widely-used Pascal VOC2012 dataset [51], which contains 20 object categories and background class. As in [6, 7], the augmented Pascal VOC dataset is adopted here. The point [2] and scribble [5] annotations are employed for weakly point-supervised and scritbleesuueervieed setrings, respectively.
Implementation Details. As in [7], we adopt LTF [19]
Table 2: Quantitative results ($4.2) on Pascal VOC2012 [51] val with mean loU(%).
the base segmentation model.
Method
Backbone
Supervision
CRF Post.
mloU
The input size is 512 x 512.
KernelCut Loss (ecevis] [6]
DeepLabV2
57.0
The SGD optimizer with mo- mentum of 0.9 and weight de- cay of 10-4 used. The ini- tial learning rate is 0.001, and there are 80k training iterations. The same data augmentations in [7] are utilized. We employ the partial cross-entropy loss Faddopiing multi-stage training, *cour re-implementation.
"TEL (CVPR22) [7]
LTF
Point
66.8
APro(Durs)
I.TF
67.7
NormCut Loss jovmuss [59]
Dae2
74.5
DDenseCRF Loss (errvis [6]
Dee2
V
75.0
KernelCut Loss (ecevis) [6]
DeepLabV2
/
75.0
Scribble
*GridCRF Loss poexis) [36]
DeepLabV2
72.8
PSI poevi1) [36]
DeepLabV3
74.9
"TEL (CVPR22) [7]
LTF
76.2
APro(Durs)
LTF
X
76.6
make full use of the available point/scribble labels and constrain the unary term. ResNet-10) [54] pretrained on ImageNet [57] is adopted as backbone network for all methods.
Quantitative Results. As shown in Table 2, compare APro approach with the state-of-the-art methods on point-supervised and scribble-supervised semantic segmentation, respectively.
Point-wise supervision. With DeepLabV2 [43], KernelCut Loss [6] achieves 57.0% mloU. Equipped with LTF [19], TEL [7] achieves 66.8% mloU. Our APro achieves 67.7% mloU, outper- forming the previous best method TEL [7] by 0.9% mloU.
Scribble-wise supervision. The seribble-superrised approaches are popular in weakly supervised semantic segmentation. We apply the proposed approach under the single-stage training framework without calling for CRF post-processing during testing. Compared with the state-of-the-an methods, our approach achieves better performance with 76.6% mloU.

---

Image TF L#
GP
Init.
Soft pseudo
Visual comparisons of pairwise affinity maps based on the RGB image for a specific position (green star), including TreeFilter (TF) [19], local kernels with full image size (L#), and our presented LP and GP processes. The GP process can capture the long-range pairwise affinity with object's 's topology. while LP retrieves the local similarities. Our APro approach smooths the noisy initial network predictions (init.) to obtain cleaner soft pscudo labels.
Figure 3:
4.3
CLIP- Semantic Segmentation
Datasets, To more comprehensively evaluate our proposed approach, we conduct experiments on CLIP- Luided annotation-free semantic segmentation with three widely used datasets:
Pascal VOC 2012 [51] introduced in Section 4.2.
Pascal Context [60], which contains 59 foreground classes and background class with 4,996
train images and 5,104 val images.
COCO-Sto Stuff [61], which has 171 common semantic object/stuff classes 164K images, containing 118,287 train images and 5,000 val images.
Base Architectures and Backbones. We employ MaskCLIP+ [40] base architecture, which leverages the semantic priors of pretrained CLIP [38] model to achieve the annotation-free dense semantic segmentation. In the experiments, we couple MaskCLIP+ with our APro approach under ResNet-50, ResNet-50x 16 and ViT-B/16 [62]. The dense semantic predictions of MaskCLIP [40] are used as the unary term, and our proposed method can refine it and generate more accurate pseudo labels for training target networks.
Implementation Details. For fair comparison, we keep the same settings as MaskCLIP+ [40]. We keep the text encoder of CLIP unchanged and take prompts with target classes as the input. For text embedding, we feed prompt engineered texts into the text encoder of CLIP with 85 prompt templates, and average the results with the same class. For ViT-B/16, the bicubic interpolation adopted for the pretrained positional embeddings. The initial learning rate is set 10-4 We train all models with is used as the backbone.
batch size 32 and 2k/4k/8k iterations. DeepLabv2-ResNe
Quantitative Results. Ta- ble 3 compares our approach with MaskCLIP+ [40] for annotaion- free semantic seg- mentation. We have the fol- lowing observations.
Table 3: Quantitative results ($4.3) on Pascal VOC2012 [51] val, Pascal Context [60] val, and COCO-Sur [61] val with mean IoU (%).
Method
CLIP Model
VOC2012
Context
COCO.
MaskCLIP+
(ecov22
ResNet-50
58.0
23.9
13.6
APro(Cura)
61.6:36
25.4:1.5
14.6:10
Pascal VOC2012 [51] val. With ResNet-50 as the im- age encoder in pretrained CLIP model, our approach outperforms MaskCLIP+ by 3.6% mloU. With ResNet-50x and ViT-B/16 as the image encoders, method surpasses MaskCLIP+ by 2.9% and 1.5% mloU, respectively.
MaskCLIP+ (ecevit) [40]
ResNet-50x
67.5
25.2
17.3
APro(Durs)
70.4
26.5
18.2
M&SECLIP4 (eceis [40]
73.6
31.1"
"8800"
ViT-B/16
APro(Uurs)
75.1
32.611
19.5
Pascal Context [60] val. Our proposed method outperforms MaskCLIP+ consistently with different image encoders (about + +1.5% mloU).
COCO-Stuff [61] val. COCO-Stuff consists of hundreds of semantic categories. Our method still brings +1. 1.0% +0.9% and +1.5% performance gains over MaskCLIP+ with ResNet-50, ResNet- 50x 16 and ViT-B/16 image encoders, respectively.

---

only GP
only LP
APro
Figure 4: Qualitative results with different pairwise affinity terms weakly supervised instance segmentation. Our method only with GP process preserves details without local consistency, while the model with only LP process encourages the local smoothness without topology-wise details. Our APro approach yields high-quality predictions with fine-grained details.
4.4 Diagnostic Experiments
For in-depth analysis, we conduct ablation studies on Pascal VOC [51] upon the weakly box- supervised instance segmentation task.
Unary and Pairwise Terms.
Table 4 shows
Table 4: Effects of unary and pairwise terms.
the evaluation results with different unary and pairwise terms. When using the unary term only, our method achieves 25.9% AP. When the global pairwise term is employed, our method achieves a much better performance of 36.3% AP. Using the local pairwise term only, our method obtains 36.0% AP. When both the
Unury Global Pairwise Local Pairwise
AP
APsa
Aprs
25.9
57.0
20.4
36.3
63.9
37.0
36.0
64.3
35.6
38.4
65.4
39.8
global and local pairwise terms are adopted, our method achieves the best performance of 38.4% AP.
Trsed Long-range Affinity Modeling. The previous works [19, 7] explore tree- based filters for pairwise relationship model- method with them. TreeFilter can capture the relationship with dis- tant nodes to a certain extent (see Fig. 3). Directly using TreeFilter as the pairwise term leads to 36.19 % AP. By combining TreeFilter with our local pairwise term, the model obtains AP.8%AP. In comparison, our proposed approach achieves 38.4% AP.
Table 5: Comparisons with tree-based methods.
Method
AP
APsa
AP75
TreeFilter [19]
36.1
63.5
36.1
ing. Table 5 compares
TreeFilter [19] + Local Pairwise
36.8
64.4
36.5
Global Local Pairwise (Ours)
38.4
65.4
39,8
Iterated Local Affinity Modeling, We evaluate our local affinity propagation (LP) with different iterations, and compare it with the classical MeanField method [10, 42]. Table 6 reports the compar- ison results. Our APro with the IP process achieves 36.0% AP after 20 iterations. However, replacing our local affinity propa- gation with MeanFiled-basee method [10] costs 100 iterations to obtain 35.90 5%.% AP. This indicates that our LP method possesses the attribute of fast convergence.
Table 6: Comparisons on local
pairwise affinity modeling.
LP(Oure)
MeanField [0]
Iteration AP
Iteration AP
35.8
35.2
20
36.0
35.5
30
35.7
35.5
50
35.6
100
35.9
Soft Pseudo-label Generation. With the formulated GP and LP methods, study how integrate them to generate the soft pseudo- labels in Table 7. We can cascade GP and LP sequentially to refine the pseudo labels. Putting GP before I.P (denoted GP-LP-C) achieves 36.8% AP, and putting L. before GP (denoted as LP- GP-C) performs better with 37.7% AP. In addition,
Table 7: Generation of soft
pseudo labels.
Method
AP
AP3o
AP7s
GP-LP-C
36.8
63.7
37.8
LP-GP-C
37.7
6
39.1
GP-LP-P
38.4
65.4
39,8
GP and LP in parallel (denoted as GP-LP-P) to produce two pseudo labels, and employ both of them to optimize the segmentation network with L, distance. Notably, GP-LP-P achieves the best performance with 38.4% mask AP. This indicates that our proposed affinity propagation in global and local views are complementary for optimizing the segmentation network.

---

Runtime Analysis. We report the average runtime of our method in Table 8. The experiment is conducted on single GeForce RTX 3090 with batch size 1. Here we report the average runtime for one GP process duration of epoch on the Pascal VOC dataset. When directly using Breadth First Search for each node with N times, the runtime 4.3x 10 ms with ( time complexity. While employing the proposed efficient implementation, the runtime is only 0.8 ms with O(N log N) time complexity. This demonstrates that the proposed efficient implementation reduces the computational complexity dramatically.
Table 8: Average runtime (ms) with and without the ef- ficient implementation. Effic. Imple.
Ave. Runtime
4.3x 10"
0.8
5 Conclusion
In this work, we proposed novel universal component for weakly-supervised segmentation by formulating it as an affinity propagation process. A global and a local pairwise affinity term were introduced to generate the accurate soft pseudo labels. An efficient implementation with the light computational overhead was developed. The proposed approach, termed as APro, can be embedded into the existing segmentation networks for label-efficient segmentation. Experiments on three typical label-efficient segmentation tasks, i.., box-supervised instance segmentation, point/scribble- supervised semantic segmentation and CLIP-guided annotation -fre semantic segmentation, proved the effectiveness of proposed method.
Acknowledgments
This work supported by National Natural Science Foundation of China under Grants (61831015). It is also supported by the Information Technology Center and State Key Lab of CAD&CG, Zhejiang University.
References
[1] Wei Shen, Zelin Peng. Xuehui Wang, Huayu Wang. Jiazhong Cen, Dongsheng Jiang, Lingxi Xie, Xiaokang Yang, and Q Tian. A survey on label-efficient deep image segmentation: Bridging the gap between weak supervision and dense prediction. TPAMI, 2023. 1,2
[2] Amy Bearman, Olga Russakovsky, Vittorio Ferrari, and Li Fei-Fei. What's the point: Semantic segmenta- tion with point supervision. In ECCV, pages 549-565, 2016. 2,
[3] Junsong Fan, Zhaoxiang Zhang, and Tieniu Tan. Pointly-uuerrised panoptic segmentation. In ECCV, pages 319-336, 2022. 3,3
[4] Wentong Li. Yuqian Yuan, Song Wang, Jianke Zhu, Jianshu Li, Jian Liu, and Lei Zhang. Point2mask: Point-supervised panoptic segmentation via optimal transport. In ICCV, pages 572-581, 2023. 1,
[5] Di Lin, Jifeng Dai, Jiaya Jia, Kaiming He, and Jian Sun. Scribblesup: Scribble-supervised convolutional networks for semantic segmentation. In CVPR, pages 3159-3167, 2016. 1,
[6] Meng Tang, Federico Perazzi, Abdelaziz Djelouah, Ismail Ben Ayed, Christopher Schroers, and Yuri Boykov. On regularized losses for weakly-supervised enn segmentation. In ECCV, pages 507-522, 2018. 2,
[7] Zhiyuan Liang, Tiancai Wang, Xiangyu Zhang. Jian Sun, and Jianbing Shen. Tree energy loss: Towards 2022. 2, 3, 6, 7,9
sparsely annotated semantic segmentation. In CVPR, pages
[8] Zhi Tian, Chunhua Shen, Xinlong Wang, and Hao Chen. Boxinst: High-performance instance segmentation with box annotations. In CVPR, pages 5443-54444 14443-552,,445 2021. 2, 2, 3, 6,
Wentong Li, Wenyu Liu, Jianke Zhu, Miaomiao Cui, Xian-Sheng Hua, and Lei Zhang. Box-supervised instance segmentation with level set evolution. In ECCV, pages 1-18, 2022. 2, 5, 6,
[10] Shiyi Lan, Xitong Yang, Zhiding Yu, Zuxuan Wu, Jose M Alvarez, and Anima Anandkumar. Vision transformers are good mask labe-la In CVPR, 2023. 1, 2. 5.
[11] Wentong Li. Wenyu Liu, Jianke Zhu, Miaomiao Cui, Risheng Yu, Xiansheng Hua, and Lei Zhang Box2mask: Box-supervisee instance segmentation via level-set evolution. arXiv preprint 22Xiv22112.0111 2022. 1.2.
10

---

[12] Jiwoon Ahn and Suha Kwak. Learning pixel-level semantic affinity with image-level supervision for weakly supervised semantic segmentation. In CVPR. pages 4981-4990, 2018. 1,2
[13] Jiwoon Ahn, Sunghyun Cho, and Suha Kwak. Weakly supervised learning of instance segmentation with inter-pixel relations. CVPR, pages 2209-2218, 2019.
[14] Lixiang Ru, Yibing Zhan, Baosheng Yu, and Bo Du. Learning affinity from attention: end-to snd-to-end weakly- supervised semantic segmentation with transformers. In CVPR, pages 16846-1688 16855, 2022. 1,2
[15] Jinlong Li, Zequn Jic, Xu Wang. Xiaolin Wei, and Lin Ma. Expansion and shrinkage of localization for weakly-supervised semantic segmentation. In NeurIPS, 2022. 1,2
[16] Cheng Chun Hsu, Kuang-Jui Hsu, Chung- Chi Tsai, Yen- Yu Lin, and Yung- Yu Chuang. Weakly supervised instance segmentation using the bounding box tightness prior. In NeurIPS, volume 32, 2019. 1, 2, 3,
[17] Shiyi Lan. Zhiding Yu, Christopher Choy, Subhashree Radhakrishnan, Guilin Liu, Yuke Zhu, Larry S Davis, and Anima Anandkumar. Discobox: Weakly supervised instance segmentation and semantic correspondence from box supervision. In ICCV, pages 3406-3416, 2021. 1, 3,
[18] Paul Vernaza and Manmohan Chandraker. Learning sandom-wall label propagation for semantic segmentation. In CVPR, pages 7158-7166, 2017.
[19] Lin Song, Yanwei Li, Zeming Li, Gang Yu. Hongbin Sun, Jian Sun, and Nanning Zheng. Learnable tree filter for structure-presse preserving feature transform. In NeurlPS, volume 32, 2019. 2. 4, 7, 8,
[20] Joseph B Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1):48-50, 1956. 3,4
[21] Lin Song. Yanwei Li, Zhengkai Jiang, Zeming Li, Xiangyu Zhang, Hongbin Sun, Jian Sun, Nanning Zheng. Rethinking learnable tree filter for generic feature transform. In NeurlPS, volume 33, pages 3991-4002, 2020. 2
[22] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervise learning using gaussian fields and harmonic functions. In ICML, pages 912-919, 2003. 2
[23] Xiaojin Zhu. Semi-supervised learning literature survey. 2005.
[24] Alexander Vezhnevets and Joachim M Buhmann. Towards weakly supervised semantic segmentation by means of multiple instance and multitask learning. In CVPR, pages 3249-3256, 2010. 2
[25] Deepak Pathak, Evan Shelhamer, Jonathan Long, and Trevor Darrell. Fully convolutional multi-class multiple instance learning. arXiv preprint 1412::442..7444 2014.
[26] Deepak Pathak, Philipp Krahenbubl, and Trevor Darrell. Constrained convolutional neural networks for weakly supervised segmentation. ICCV, pages 1796-1804, 2015.
[27] Pedro O Pinheiro and Ronan Collobert. From image-level to pixel-level labeling with convolutional networks. In CVPR, pages 1713-1721, 2015.
[28] George Papandreou, Liang-Chieh Chieh Chen, Kevin P Murphy, and Alan L Yuille. Weakly-and semi semi-supervised learning of a deep convolutional network for semantic image segmentation. In ICCV, pages 1742 1750.
2015. 2
[29] Ruihuang Li. Chenhang He, Yabin Zhang, Shuai Li, Liyi Chen, and Zhang, Sim: Semantic-aware instance mask generation for box-supervised instance segmentation. In CVPR, 2023. 2
[30] Tianheng Cheng, Xinggang Wang, Shaoyu Chen, Qian Zhang, and Wenyu Liu. Boxteacher: Exploring high-quality pseudo labels for weakly supervised instance segmentation. In CVPR, 2023. 2
[31] Rui Yang. Lin Song, Yixiao Ge and Xiu Li. Boxsnake: Polygonal instance segmentation with box supervision. In ICCV, 2023.
[32] Bowen Cheng, Omkar Parkhi, and Alexander Kinillov. Pointly-supervised instance segmentation. In CVPR,
pages 2617-2626, 2022. 2
[33] Chufeng Tang, Lingxi Xie, Gang Zhang, Xiaopeng Zhang, Qi Tian, and Xiaolin Hu. Active pointly- supervised instance segmentation. In ECCV, pages 606 623, 2022.

---

[34] Hongjun Chen, Jinbao Wang. Hong Cai Chen, Xiantong Zhen, Feng Zheng, Rongrong Ji, and Ling Shao. Seminar learning for click-level weakly supervised semantic segmentation. In ICCV, pages 6920-6929.
2021. 2
[35] Bingfeng Zhang. Jimin Xiao, Jianbo Jiao, Yunchao Wei, and Yao Zhao. Affinity attention graph neural
network for weakly supervised semantic segmentation. TPAMI, 44(11)8062-8096 2021. 2,
[36] Dmitrii Marin, Meng Tang. Ismail Ben Ayed, and Yuri Boykov. Beyond gradient descent for regularized segmentation losses. In CVPR, pages 10187-10196, 2019. 2,7
[37] Yun Liu, Yu-Huan Wu, Peisong Wen, Yujun Shi, Yu Qiu, and Ming-Ming Cheng. Leveraging instance- image-and dataset-level information for weakly supervised instance segmentation. TPAMI, 44(3):1415- 1428, 2020. 2
[38] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In JCML, pages 8748 8763, 2021. 2,
[39] Yuqi Lin, Minghao Chen, Wenxiao Wang. Boxi Wu, Ke Li, Binbin Lin, Haifeng Liu, and Xiaofei He. Clip is also efficient segmenter: A text-driven approach for weakly supervised semantic segmentation. In CVPR, 2023.
[40] Chong Zhou, Chen Change Loy, and Bo Dai. Extract free dense labels from clip. In ECCV, pages 696-712, 2022. 3,8
[41] Yanwei Li, Hengshuang Zhao, Xiaojuan Qi, Yukang Chen, Lu Qi, Liwei Wang. Zeming Li, Jian Sun, and Jiaya Jia. Fully convolutional networks for panoptic segmentation with point-based supervision. TPAMI, 2022. 3
[42] Philipp Krähenbühl and Vladlen Koltun. Efficient inference in fully connected erfs with gaussian edge potentials. In NeurlPS, volume 24, 2011. 5,
[43] Liang-Chied Chieh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected erfs. TPAMI, 40(4))834-848, 2017. 3, 6,
[44] Shuai Zheng. Sadeep Jayasumana, Bernardino Romera- Romera-Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang. and Philip HS Torr. Conditional random fields as recurrent neural networks. In ICCV, pages 1529-1537, 2015.
[45] Anton Obukhov, Stamatios Georgoulis, Dengxin Dai, and Luc Van Gool. Gated orf loss for weakly supervised semantic image segmentation. In NeurlPS, 2019. 3,4
[46] William T Freeman, Egon C Pasztor, and Owen T Carmichael. Learning low-level vision. IJCV, 40:25-4:4444 47, 2000. 3
[47] Qingxiong Yang. Stereo matching using tree filtering. JEEE TPAMI, 37(4):334-866, 2014. 4
[48] Robert Endre Tarjan. A class of algorithms which require nonlincar time to maintain disjoint sets. Journal of computer and system sciences, 18(2):1 10-127, 1979. 5
[49] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In ECCV, pages 740-755, 2014. 5,
6.7
[50] Bharath Hariharan, Pablo Arbeláez, Lubomir Bourdev, Subhransu Maji, and Jitendra Malik. Semantic contours from inverse detectors. In ICCV, pages 991-998, 2011. 6
[51] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. IJCV, 883))303-338, 2010. 6, 7, 8,9
[52] Xinlong Wang, Rufeng Zhang, Tao Kong, Lei Li, and Chunhua Shen. Solov2: Dynamic and fast instance segmentation. In NeurlPS, volume 33, pages 17721-17732, 2020. 6
[53] Bowen Cheng, Ishan Misra, Alexander G Schwing, Alexander Kirillov, and Rohit Girdhar. Masked- attention mask transformer for universal image segmentation. In CVPR, pages 1299, 2022. 6
[54] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 778-778, 2016. 6.7
12

---

[55] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei. Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In ICCV, pages 10012-10022, 2021.
[56] Kai Chen, Jiaqi Wang, Jiangmiao Pang. Yuhang Cao, Yu Xiong. Xiaoxiao Li, Shuyang Sun, Wansen Feng. Ziwei Liu, Jiarui Xu, et al. Mmdetection: Open mmlab detection toolbox and benchmark. arXiv preprint 1rXiv:190.00155,22222 2019. 6
[57] Olga Russakovsky, Jia Deng, Hao Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet: large scale visual recognition challenge. IJCV, 115:211-2 2221, 2015. 6,
[58] Golnaz Ghiasi, Yin Cui, Aravind Srinivas, Rui Qian, Tsung-Yi Yi Lin, Ekin Cubuk, Quoe V Le, and Barret Zoph. Simple copy-pat pay-- is strong data augmentation method for instance segmentation. In CVPR, pages 2918 2128, 2021.
[59] Meng Tang, Abdelaziz Djelouah, Federico Perazzi, Yuri Boykov, and Christopher Schroers. Normalized cut loss for weakly-supervised cnn segmentation. In CVPR, pages 1818-1827, 2018. 7
[60] Roozbeh Mottaghi, Xianjie Chen, Xiaobai Liu, Nam- Gyu Cho, Scong- Whan Lee, Sanja Fidler, Raquel Urtasun, and Alan Yuille. The role of context for object detection and semantic segmentation in the wild. In CVPR, pages 891 898. 2014.
[61] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari. Coco-stuff: Thing and stuff classes in context. In CVPR, 2018.
[62] Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold. Sylvain Gelly, et al. An image is worth 16x words: Transformers for image recognition scale. In ICLR, 2020. 8
13


Reviews:
[{"review_id": "WzOU7KPRpZ", "reviewer": "Reviewer_bFj5", "summary": "This paper utilizes local and global pairwise affinity terms to generate accurate soft pseudo labels and incorporates an efficient algorithm to reduce computational costs. Experimental results demonstrate the approach's superior performance in various segmentation tasks.", "questions": "To make their contribution more apparent, the author should provide a comprehensive comparison of the proposed method's performance with previous approaches of the generated pseudo ground truth. This comparison would highlight the advantages and improvements of their approach over existing methods in terms of accuracy, efficiency, and other relevant metrics.\n\nBy including a thorough analysis of the pseudo ground truth performance, readers can better understand the strengths of the proposed approach and how it outperforms or complements existing techniques. ", "limitations": "See Weaknesses", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Experimental results demonstrate the approach's superior performance in various segmentation tasks.\nThe paper is easy to understand.", "weaknesses": "The affinity methods are commonly used in weakly supervised segmentation tasks, such as 'Learning Affinity from Attention: End-to-End Weakly-Supervised SemanticSegmentation with Transformers\nAffinity Attention Graph Neural Network for Weakly Supervised Semantic Segmentation.\nLearning Pixel-level Semantic Affinity with Image-level Supervision for Weakly Supervised Semantic Segmentation\nWeakly Supervised Learning of Instance Segmentation with Inter-pixel Relations.'\n\nThe novelty of their method might be limited compared to existing affinity-based approaches. To stand out, the author should clearly highlight the differences between their method and the mentioned ones. It could be in terms of the formulation of the affinity modeling task, the incorporation of local and global pairwise affinity terms, the generation of accurate soft pseudo labels, or the development of an efficient algorithm to reduce computational costs.\n\nProviding a thorough comparison with these existing methods would help readers understand the unique contributions of the proposed approach and its advantages over previous approaches. By highlighting these differences, the paper can demonstrate why their method is valuable and relevant in the context of weakly supervised segmentation tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the constructive comments. Please find what below our itemized responses.\n\n**Q1. The comprehensive analysis and comparisons with the existing affinity-based methods.**\n\nR:  Previous works [1-4] involve affinity modeling, and our proposed approach is largely different from them in formulation and pipeline.  Specifically,  [1] adopts the random walk and local pixel-adaptive refinement (PAR) to propagate the affinity. [2] introduces the Affinity CNN to convert images into graphs, using a GNN-based affinity attention module for affinity modeling. [3,4] leverage the random walk to capture long-range affinity with local operations. While they struggle with fine-grained global semantic affinity, hindering the generation of accurate pseudo-mask labels. As noted in [3], detailed global affinity modeling requires substantial computational costs. \n\nIn contrast, we present the unified affinity propagation formulation for both global and local affinity modeling. The global affinity utilizes the acyclic Minimum Spanning Tree to perform fine-grained affinity propagation, which considers all nodes for a comprehensive context understanding with object topology. On the other hand, the local term employs the kernel-based propagation in a complementary role, which focuses on the nearby area to attain spatial smoothness. To efficiently perform this procedure, we deliberately design a Lazy Propagation scheme for fast implementation, which avoids excessive computations.\n\nFurthermore, we devise a general plug-in module for various label-efficient segmentation tasks, which does not require any modification of the network itself. In comparison, the previous works[1][2][3][4] are mainly designed for single weakly-supervised segmentation tasks with some customized designs.\n\nTo demonstrate the effectiveness of our method, we further conduct detailed performance comparisons with the recent works [1][2].\nFirstly, we implement our method based on the AFA[1] framework for image-level supervised semantic segmentation on Pascal VOC 2012. The experimental settings are the same as [1] for fair comparison. The results are reported below.\n|&nbsp;&nbsp;&nbsp;Methods | dataset | $\\quad$&nbsp;&nbsp;&nbsp; mIoU |\n|:-:| :-: |:-:| \n|  AFA[1] | VOC2012 | 62.6 |\n| +APro(Ours) | VOC2012 | $\\qquad$64.1($\\uparrow$1.5) |\n\n\nWe notice that the local pixel-adaptive refinement (PAR) in AFA [1] is similar to our proposed local affinity term (LP). Both of them are kernel-based methods based on the input image, however, their formulations and implementations are different. In particular, we compare our method with PAR [1] in weakly box-supervised instance segmentation settings on VOC2012 and COCO. \n|  $\\qquad$ Methods | &nbsp;&nbsp;dataset | $\\quad$&nbsp;&nbsp;AP| $\\quad$AP_50 | $\\quad$AP_75  |\n|:--: | :--: | :--: | :--: | :--: | \n|Baseline +PAR[1]| VOC2012| 34.6 | 63.6| 33.9 |\n|Baseline + LP(Ours)| VOC2012| 36.0 ($\\uparrow$1.4) | 64.3($\\uparrow$0.7) | 35.6 ($\\uparrow$1.7)|\n|Baseline + APro(Ours)| VOC2012| 38.1 ($\\uparrow$3.5) | 66.1 ($\\uparrow$2.5)| 39.1 ($\\uparrow$5.2) |\n|Baseline + PAR[1] | COCO| 30.5 | 53.1 | 30.6 |\n|Baseline + LP(Ours) | COCO|  31.6 ($\\uparrow$1.1)  |  53.2 ($\\uparrow$0.1)  |   32.2 ($\\uparrow$1.6) |\n|Baseline + APro(Ours) | COCO| 33.0 ($\\uparrow$2.5)| 55.2 ($\\uparrow$2.1) | 33.6 ($\\uparrow$3.0)|\n\nCompared with PAR [1], our approach obtains consistent performance gains.\n\nSecondly, we compare our method with A$^2$GNN[2] under its designed point/scribble-supervised semantic segmentation and box-supervised instance segmentation settings.  \n\nMethods | backbone |Supervision|Multi-stage | CRF | mIOU |\n|:----: | :----: | :----: | :----: | :----: | :----: |\n|A$^2$GNN[2] | DeeplabV2 | Point| √  | √ | 66.8 | \n|APro(Ours)| Tree-FCN | Point| x  |  x  | 67.7 |    \n|A$^2$GNN[2]| Tree-FCN | Scrrible| √ |  √  | 76.2 | \n|APro(Ours)| Tree-FCN | Scrrible| x  |  x  | 76.6 |   \n\nThough A$^2$GNN has achieved competitive results, it needs multi-stage training and CRF refinement in the post-processing to yield accurate mask predictions. In contrast, our method is an end-to-end training framework without the CRF post-processing.\n\nRegarding the weakly box-supervised instance segmentation task,  our APro outperforms A$^2$GNN by a large margin, with +15.3\\% AP_75 on VOC2012 and +13.4\\% AP on the large-scale COCO dataset.\n| Methods | dataset | backbone | AP| AP_50 | AP_75  |\n|:----: | :----: | :----: | :----: | :----: | :----: | \n| A$^2$GNN[2] | VOC2012 | r101  |  -  |  59.1  | 27.4 |\n| APro(Ours) | VOC2012 | r50 |  38.1 | 66.1 | 39.1 |\n| APro(Ours) | VOC2012 |r101 |  **40.6** | **68.5**| **42.7** |                                \n| A$^2$GNN[2] | COCO |  r101 | 20.9|43.9 |17.8|\n| APro(Ours) | COCO |  r50 |33.0|55.2|33.6|\n| APro(Ours) | COCO |  r101 |**34.3**|**57.0**|**35.3**|\n\nThe above results indicate that our method is able to model the fine-grained affinity and obtain accurate mask predictions across different label-efficient segmentation tasks. \n\nWe will incorporate the above discussions in our revised manuscript.\n\n&emsp;\n\n[1] Learning Affinity from Attention: End-to-End Weakly-Supervised Semantic Segmentation with Transformers, CVPR2022. \n\n[2] Affinity Attention Graph Neural Network for Weakly Supervised Semantic Segmentation, TPAMI2021.\n\n[3] Learning Pixel-level Semantic Affinity with Image-level Supervision for Weakly Supervised Semantic Segmentation, CVPR2018.\n\n[4] Weakly Supervised Learning of Instance Segmentation with Inter-pixel Relations, CVPR2019."}, {"review_id": "XCX0Zj17Dw", "reviewer": "Reviewer_4J6P", "summary": "This paper proposes an affinity propagation method within local and global perspectives to improve the pseudo labels generated by the model for the parts without GT masks. Meanwhile, they then propose an efficient implementation to solve the heavy computation by graph modeling.  The authors conduct experiments on several benchmarks to showcase their improvements on point/scribble/bbox-level weakly-supervised semantic segmentation, acting as a plug-in module to enhance their segmentation performance. And competitive performances are obtained naturally.", "questions": "Please refer to the weakness part.", "limitations": "Despite the limited novelty in this phase, this paper can be stronger when the authors well address my questions above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The writing of this paper is easy to follow.\n2. Extensive experiments are studied and analyzed to present the proposed method.\n3. The final performances are competitive.", "weaknesses": "1. To my concern, affinity propagation exploration has been studied widely in the weakly-supervised learning community, such as [1]. The overall novelty of this paper sounds limited because their method has a lot of overlappings with previous method, though the author adapt a graph modeling to analyze and model the propagation procedure. It is important to demonstrate the main differences from the proposed method with others.\n\n    [1] Learning Affinity from Attention: End-to-End Weakly-Supervised Semantic Segmentation with Transformers, CVPR2022\n\n2. From the eq3 and eq5, it is hard to get the point, of how they define the global and local respectively since the main differences lie in that a max operation is performed in eq3 and the points-set in eq5 is local but not detailed clearly.\n\n3. The motivation for adapting Gaussian to model the local part in this paper should present more reasonably, for example, by giving some experiments directly to see that the Gaussian methods indeed capture the local receptive features.\n\n4. Despite the point/scribble/bbox-level weakly supervised semantic segmentation, how about the results when performing on semi-/image-level supervised semantic segmentation tasks to validate that the proposed method indeed helps to improve the soft-pseudo label for the unlabeled pixels?\n\n5. Some important references are missing below while these methods may discuss in the paper too.\n\n    [2] Reducing Information Bottleneck for Weakly Supervised Semantic Segmentation, NeurIPS 2021\n\n    [3] Expansion and Shrinkage of Localization for Weakly-Supervised Semantic Segmentation, NeurIPS 2022\n\n    [4] Revisiting Weak-to-Strong Consistency in Semi-Supervised Semantic Segmentation, CVPR2023\n\n    [5] Semi-Supervised Semantic Segmentation With Error Localization Network, CVPR2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the thoughtful comments.  Please find what below our itemized responses.\n\n**Q1. Main differences with the existing approaches.**\n\nR: Different from the existing approaches, our method considers object topology and captures fine-grained global affinity through an efficient implementation. Unfortunately, the existing methods fall short in achieving such an objective. \n\nBesides, our method is a general plug-in module for various label-efficient segmentation tasks, which does not require any modification on the network itself. Extensive experiments demonstrate the effectiveness of our approach in generating high-quality pseudo mask predictions across different tasks and datasets.\n\nPlease kindly refer to **our responses to reviewer bFj5** for more comprehensive analyses on the existing methods, including AFA [1].\n\n[1] Learning Affinity from Attention: End-to-End Weakly-Supervised Semantic Segmentation with Transformers, CVPR2022. \n\n**Q2. About the differences between the global and local  in Eq.3 and Eq.5.**\n\nR: The formulations of global (Eq.3) and local (Eq.5)  have the similar form, while they are defined in different scopes. In detail, their receptive fields for affinity propagation are totally different.\n\nThe global pairwise term contains all the nodes $ \\mathcal{V}$ through the tree-based graph $\\mathcal{G}_T$, which are implemented by the Minimum Spanning Tree. In contrast, the local pairwise term is limited to a local area, such as 3x3 or 5x5, which is implemented by the Gaussian kernel.\n\nTo better illustrate the detailed process of the global and local operations, we provide **Figure 1 in the PDF**. For visual comparisons of pairwise affinity maps, Figure 3 in the main paper also shows the global and local affinity maps, denoted as \"GP\" and \"LP\", respectively. \n\nIn calculating the global pairwise term, we present the distance-insensitive max affinity function to ensure that the similarity does not diminish abruptly with the increase of distance along the path of the spanning tree (see **Figure 2 in the PDF** for the details). \n\n**Q3. The motivation for adapting Gaussian to model the local part should present more reasonably. Giving some experiments directly to see.**\n\nR:  Spatially adjacent pixels are more likely to share the same label, which inspired us to define the local Gaussian kernel within a fixed window, such as 3x3 or 5x5. Such a neighboring receptive field allows the focus to be placed on local texture and shape features rather than global ones. Intuitively, we present the visualizations in **Figure 3 in the PDF** to demonstrate the effectiveness of this local pairwise term.\n\nOne can see that the predictions become smoother after local affinity propagation (LP), indicating an enhancement in local consistency by capturing the local receptive characteristics.\n\n**Q4. How about the performance on semi-/image-level supervised semantic segmentation?**\n\nR: Thanks for your suggestions. We have conducted the image-level semantic segmentation task on Pascal VOC2012 dataset based on the framework of AFA [1]. The comparison results are shown below. Our method can further obtain +1.5\\% mIoU gain over AFA[1].\n|&nbsp;&nbsp;&nbsp;Method | dataset | $\\quad$&nbsp;&nbsp;&nbsp; mIoU |\n|:-:| :-: |:-:| \n|  AFA[1] | VOC2012 | 62.6 |\n| +APro(Ours) | VOC2012 | $\\qquad$64.1($\\uparrow$1.5) |\n\nWe will perform more experiments on recent image-level methods, such as ESOL(NIPS2022) and ToCo(CVPR2023),  as well as semi-supervised approaches [4][5], and add the results into the revised manuscript to further show the effectiveness of our method.\n\n**Q5. Some important references are missing below while these methods may discuss in the paper too.**\n\nR: Thanks for your suggestions.  Methods [2] and [3] are about image-level supervised semantic segmentation methods, while [4] and [5] are related to semi-supervised semantic segmentation. Specifically, RIB [2] adopts the information bottleneck principle to interpret the partial localization issue in trained classifier. ESOL[3] proposed a new training pipeline,  with a \"Divide-and-Conquer\" manner to address the partial localization issue of the CAM method by introducing a deformable transformation operation. It is worth noting that we have already cited [3] in our manuscript. On the other hand, ELN [5] aims to deal with errors on pseudo labels and UniMatch [4] presents the weak-to-strong consistency regularization framework from FixMatch.\n\nWe will cite and discuss these works in our revised manuscript.\n\n&emsp;\n\n[2] Reducing Information Bottleneck for Weakly Supervised Semantic Segmentation, NeurIPS 2021.\n\n[3] Expansion and Shrinkage of Localization for Weakly-Supervised Semantic Segmentation, NeurIPS 2022.\n\n[4] Revisiting Weak-to-Strong Consistency in Semi-Supervised Semantic Segmentation, CVPR2023.\n\n[5] Semi-Supervised Semantic Segmentation With Error Localization Network, CVPR2022."}, {"review_id": "ZcC3jr918b", "reviewer": "Reviewer_acqT", "summary": "This paper develops a weakly-supervised segmentation framework based on affinity propagation. It overcomes the drawback of simply modeling neighboring pairwise potentials and proposes both global and local affinity terms to generate pseudo labels. The authors demonstrate the effectiveness of the proposed method in box-supervised instance segmentation, point/scribble-supervised semantic segmentation, and CLIP-guided semantic segmentation tasks. ", "questions": "It would be appreciated if the authors can kindly reply to my questions and concerns. I will consider raising my evaluation. \n\n- The whole framework of affination is defined on the classic CRF model, as cited in line 110. However, it is noted that in [33], the energy function is the sum of unaries and the sum of pairwise potentials. The CRF model in Equ. 2 turns out to be the sum of products between unary and pairwise terms. If understand correctly, this formulation can be interpreted as the weighted sum of unaries defined on neighbor pixels, with weights calculated from pairwise terms. I am wondering how the authors draw an equivalence between the two formulations. \n\n- What is the $\\mathcal{L}_{g}$ used in Equ. 1? is it a partial cross-entropy? how is it defined with non-annotated pixels? The unary used in Equ. 2 is then the output distribution of only labeled pixels or all pixels?\n\n- In 3.2.1, the node in line 127 is defined as a pixel right? why the set of edges can have N-1 elements, as defined in line 132\n\n- How do authors set the degree of similarity defined on line 143? is it unique for all nodes?\n\n- Can the authors explain why the tree-based model preserves topology?\n\n- For the local affinity propagation, I always consider Equ. 6 as a sum of neighbor pixels weighted by the intensities, similar to the conventional CRF model [33]. However, in [33], a spatial smoothness term is added. The authors want to explain how their method preserves spatial smoothness. \n\n- Based on Equ.6  I don't see any necessity of iterating it (there are even no iterative parameters inside). What does it mean by saying iterating local affinity leads to better performance? \n\n- what is the transmission cost? \n\n\n- In 3.2.1 and 3.2.1, the authors then obtain two sets of pseudo labels, $y^{g}$ and $y^{s}$. How do they exactly train the network with these two sets of labels? How to merge them when using them together?\n\n\n", "limitations": "The authors adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality: The paper proposes two kinds of pairwise affinity propagation which are novel for weakly-supervised image segmentation settings. The global affinity propagation employs a minimum spanning tree to remove the edge with a large distance to obtain the tree-based sparse graph, which explicitly captures long-range dependency, while local affinity propagation leverages the conventional Gaussian kernel.  The combination of the two enhances the performances based on Table 4. \n\nQuality: The paper itself is self-contained and includes sufficient experimental setup and details. \n\nClarity: The paper is well-written but it might be hard to follow. It would be hard to understand the context of the proposed method for my initial reading and still creates some confusion after repeated reading. Figures are suggested to enhance the clarity of certain concepts developed in this paper. \n\nSignificance: I give high significance to this paper, as it proposes an effective and convincing method for a well-known and challenging problem.  \n", "weaknesses": "Personally, the biggest concern of this paper is the clarification. Basically, the authors devised two affinity scheme to create long-range and short-distance dependencies and both of them uses the same framework as described in Equ. 2. However, it would be very hard to understand the details of the global one. Authors are suggested to make a graphical illustration to demonstrate the idea.  Also, it still remains confusion about the method, as will be asked in the next section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for acknowledging the strength of our method. We have tried our best to clarify each issue.  Please find what below our itemized responses.\n\n**Q1. The details of the global one and making a graphical illustration.**\n\nR: To facilitate comprehension, we provide a detailed graphical illustration **(Figure 2 in the PDF)** to describe our global affinity propagation process. \n\nInitially, an input image is represented as a 4-connected planar graph. Subsequently, the Minimum Spanning Tree (MST) is constructed based on the edge weights to obtain the tree-based graph $\\mathcal{G}\\_T$. $\\psi_g(x_i,x_j)$ is calculated as $exp(-d)$,  where $d$ is the maximum value along the path $E_{i,j}$ from node $x_i$ to node $x_j$. This pairwise similarity $\\psi_g(x_i,x_j)$  is then multiplied by the unary term $\\phi(x_j)$ to obtain soft pseudo predictions  $y_i^g$.\n\nNote that Figure 2 serves purely as a visual illustration to understand our method. In the implementation, it is unnecessary to compute $\\psi_g$ explicitly. As detailed in Section 3.3, we alternatively design a lazy propagation scheme to efficiently update these values.\n\n**Q2.  About the formulations of Equ.2 and the classic CRF model.**\n\nR: Yes, you are right. Our definition of the affinity propagation process does not strictly adhere to the classic CRF model[29]. The energy function in [29] consists of the sum of unary terms and pairwise potential; however, the problem solving process is rather complex. As our aim is to obtain a refined pseudo label, we adopt the general concept of unary and pairwise terms, with the intention of integrating their benefits in a more accessible and straightforward manner.\n\n**Q3.  About the  $\\mathcal{L}_g$ used in Equ.1 and the unary used in Equ.2.**\n\nR: The definition of $\\mathcal{L}_g$ depends on the form of supervision. For point or scribble forms, the sparsely labeled region lies in the object, which is suitable for partial cross-entropy loss. It has no impact on non-annotated pixels. While, for labeled bounding box supervision, it is uncertain whether the pixels within the box truly belong to the object. So we adopt box projection loss, which constraints the predictions within the labeled box. In our paper, we listed the loss function for each unary term in the section of Implementation Details (lines 210, 245-248) for different weakly-supervised tasks. \n\nMoreover, the unary term used in Equ. 2 is the network prediction of all pixels.\n\nWe will make our revision clearer.\n\n**Q4. About node in line 127 and N-1 edges.**\n\nR: Yes, the node corresponds to a pixel. The constructed MST is an acyclic subgraph of the original 4-connected planar graph that includes all vertices.  A spanning tree connects all nodes of an image, and there is a unique and simple path between any two nodes. Therefore, the MST-based graph with N vertices requires N-1 edges to maintain connectivity without cycles. **Figure 2 in the PDF** also gives a simple illustration of a constructed MST.\n\n**Q5. About the degree of similarity defined in line 143.**\n\nR: The degree of similarity $\\zeta_g$ is a hyper-parameter in our approach. We conduct ablation study on it in Table A1 of the supplementary material and select $\\zeta_g$ = 0.07, which remains constant for all nodes.\n\n**Q6. Explain why the tree-based model preserves topology.**\n\nR: Our approach initially represents an image as a 4-connected planar graph with pixel similarity measured via the edge weight of adjacent nodes. The MST is constructed by edge pruning, which preferentially preserves edges of smaller weight, i.e., adjacent vertices with higher pixel similarity.\n\nSimilar pixels are usually located inside or on the surface of an object, whereas larger pixel differences appear across distinct objects. In other words, there are more edges within an object and fewer edges connecting different objects.  Thus, the MST can capture an image's topological structure. For better comprehension, we provide two visual examples in **Figure 4 of the PDF**.\n\n**Q7.  How the local affinity propagation preserves spatial smoothness?**\n\nR: In the conventional CRF model, the pairwise potentials involve relationships between each pixel and all the other pixels, necessitating the inclusion of a spatial smoothness term to maintain spatial coherence. While our local affinity propagation method applies pairwise affinity within a local region surrounding each pixel, such as a 3x3 or 5x5 kernel. This consideration of local domain pixels implicitly signifies spatial smoothness, indicating that nearby pixels likely belong to the same class. The detailed experimental comparison is provided below. Incorporating Spatial Position into our LP yields no performance improvement while bringing an additional hyperparameter.\n\n|$\\qquad$Method|AP|\n|:-:|:-:| \n|LP|36.0| \n|LP + Spatial Position|34.8|\n\n**Q8. About the iteration of the local affinity.**\n\nR: Thanks for pointing out this issue. Upon obtaining the refined pseudo label $y_i^s$, we treat it as a new unary term $\\phi(x)$ to iterate it. Table 6 in the main paper demonstrates the effectiveness of the iterating process. \n\n**Q9. What is the transmission cost?**\n\nR: In Section 3.3, we define the maximum $w$ of the path through any two nodes in the tree-based graph as the transmission cost $C$.  For example, in the green dashed box of **Figure 2 in the PDF**, the transmission cost of $x_0$ and $x_3$ is 3*${\\zeta_g}^2$. Section A.1 in our Supplementary Material also provides detailed proof of transmission cost.\n\n**Q10. How to train the network with labels $y^g$ and $y^s$?**\n\nR:  We assign each $y_i$ from GP and LP to the network prediction $p_i$, and employ the distance measurement function as the objective for unlabeled regions $\\Omega _u$. Simple L1 distance is empirically adopted in our implementation.   \n\nWe described it in Section 3.1 (line122-line124) of the main paper. We will make it clearer in the revision. "}, {"review_id": "YIl8lEuwoh", "reviewer": "Reviewer_8pug", "summary": "This paper proposes an affinity propagation algorithm for weakly supervised segmentation. Given image segmentation data with only sparse box/point/scribbles annotations, the proposed method propagates these annotations to other pixels as pseudo masks for training. Global affinity and local affinity are proposed to capture global pairwise potential and local connectivity respectively. The authors propose an efficient implementation for the propagation of these two types of affinity which makes training practical. The final model performs better than prior works in PASCAL VOC and COCO with partial annotations. ", "questions": "- Will the code be released? I see no mention of this in the paper. It would help the community if an open-source version is available, especially for the non-trivial GPU implementation of affinity propagation.\n\n- When comparing speed with mean-field [29], are both algorithms running on GPU?\n", "limitations": "Limitations are mentioned in Section D in the supplementary material. The authors mention that the use of only image intensity to compute affinity is a limitation which I agree with.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed framework is simple and effective. Both global and local affinity propagation are intuitive, and the resultant method achieves strong performance compared to existing works without bells and whistles. This shows the effectiveness of the proposed affinity propagation mechanism.\n\n- The authors propose an efficient implementation for the affinity propagation algorithm which is crucial for making training with this method practical. The authors claim that it is five times faster than mean-field [29]. This fast algorithm is also potentially useful for future work in other directions.\n", "weaknesses": "- The affinities are defined on pixel intensity which can be limiting as it is sensitive to lighting and low-level noises. It might help to incorporate deep features from self-supervised, pre-trained networks (e.g., MAE).\n\n- Another direction for segmentation is open-vocabulary segmentation which can benefit from scaling and data engines (e.g., SAM). The proposed method does not seem to be scalable as the affinity is fixed to low-level color differences.\n\n- Missing related work and discussion: Learning Pixel-level Semantic Affinity with Image-level Supervision for Weakly Supervised Semantic Segmentation, CVPR 2018\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the constructive and insightful comments.  Please find what below our itemized responses.\n\n**Q1. About incorporating deep features from self-supervised, pre-trained networks (e.g. MAE).**\n\nR: We have tested the incorporation with the deep features of the network during training. It is unstable to achieve reasonable performance in our experiments. In the future work,  we will consider to incorporate deep features from the pre-trained MAE, DINO/DINO-V2  models, as you mentioned. These pre-trained models have exhibited strong generalization capability, and we believe they could make our method more powerful.\n\n**Q2. For open-vocabulary segmentation, the proposed method does not seem to be scalable as the affinity is fixed to low-level color differences.**\n\nR: Yes, our approach may not perform well in the task of open-vocabulary segmentation. As you suggested,  we could incorporate the pre-trained models such as DINO/DINOv2, MAE, CLIP or Stabel diffusion to improve the scalability of our method.\n\nIn addition, our method can be extended to multimodality-based affinities, i.e., between vision and language, to achieve more accurate vision-language alignment for VL tasks. This is an interesting research direction for our further work. \n\n**Q3. Missing related  work and discussion of the CVPR2018 work.**\n\nR: The work [1] (CVPR2018) also involves affinity modeling operations, while the formulations and pipelines of them are different from our approach. Especially, the work [1] adopts the sparse random walk for long-range operations, which relies on the affinity transition probability. Different from it, our method constructs the Minimum Spanning Tree (MST) on the whole image and performs the formulated affinity propagation process. To reduce the computation cost, we deliberately devise a Lazy Propagation scheme for fast implementation. Please kindly refer to our **responses to Reviewer bFj5** for more comprehensive analyses and comparisons with the other existing methods. \n\n[1]  Learning Pixel-level Semantic Affinity with Image-level Supervision for Weakly Supervised Semantic Segmentation, CVPR 2018.\n\n**Q4. Will the code be released?**  \n\nR: For sure, we will release our full source code to make contributions to the community, including the GPU implementation of affinity propagation and complete codes on each task, so that peers can easily reproduce our results.\n\n**Q5. When comparing speed with mean-filed, are both algorithms running on GPU.**\n\nR: Yes, both methods are performed on the GPU device. The original mean-field [29] is based on the pixels of the whole image, and we compare the GPU version [4] of mean-filed with local kernel under the same settings. We will make it clearer in the revision."}, {"review_id": "hgsP7j2rl1", "reviewer": "Reviewer_bNsh", "summary": "This paper proposes a novel universal component for weakly-supervised segmentation by formulating it as an affinity propagation process. It simultaneously utilizes a global and a local pairwise affinity term to generate soft pseudo labels. An efficient algorithm is also developed to reduce the computational cost. Experiments on three label-efficient segmentation tasks demonstrate the effectiveness of the proposed method.", "questions": "1. How to determine the number of iterations?\n2. The runtime details in Table 7 are not clear, such as iterations, batch size, device...\n3. In MaskCLIP, key smoothing and prompt denoising are proposed to refine the pseudo masks. The key smoothing also aims to realize global affinity propagation based on the similarity of key features (not used in the MaskCLIP+ setting). It would be helpful to explore their effects.\n", "limitations": "Please refer to the Weaknesses part.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed framework uses both global and local pairwise affinity term and achieves superior performance.\n2. The efficient implementation of global affinity propagation can greatly reduce computational cost.\n3. The proposed approach can be conveniently plugged into existing segmentation networks.\n4. The experiments are abundant, covering many label-efficient segmentation tasks.", "weaknesses": "1. This approach seems parameter-sensitive. The slight variation of $\\zeta_s$, $\\zeta_g$ may lead to notable fluctuation of segmentation performance. Is there consistency in the parameters used across different tasks and datasets?\n2. The efficiency of the whole framework is not intuitive. By introducing both global and local pairwise affinity term, is there a significant decrease in efficiency? It would be helpful if authors could present the change of training time with/without APro.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the careful and thoughtful reviews. Please find what below our itemized responses.\n\n**Q1.  Whether parameters ${\\zeta_s}$, ${\\zeta_g}$ are consistent across different tasks and datasets.**\n\nR: The parameters ${\\zeta_s}$ and ${\\zeta_g}$ control the sensitivity to variations in pixel values, and they will impact the segmentation performance. While meticulous tuning of these parameters on different datasets and tasks could lead to improved results, we utilize the same values of them across all tasks and datasets: ${\\zeta_s}$ = 0.15, ${\\zeta_g}$ = 0.07. The details are shown in Tables A1 and A2 in the Supplementary Material.\n\n**Q2. By introducing both global and local pairwise affinity terms, is there a significant decrease in efficiency?  Presenting the change of training time with/without APro.**\n\nR:  We report the detailed training time below. We conduct the ablation studies on the box-supervised instance segmentation on Pascal VOC. \n|$\\quad$Method | Training Time  | &nbsp;&nbsp;AP |\n|:----: | :----: | :----: | \n|Baseline | 3h | 25.9  |\n| +LP | 3.5h | 36.0 |\n| +GP | 4.5h | 37.0 | \n| APro (LP+GP) | 5.2h | 38.1 |\n\nThe baseline model without our APro method needs 3h to train. When adding the local operation LP and global operation GP individually,  0.5h and 1.5h additional training time are needed, respectively. When adding both of them, it costs 2.2h additional training time with our efficient implementation. However, without our efficient implementation, the training time would be unbearable.\n\nWe will make it clearer in our revision.\n\n**Q3. How to determine the number of iterations?**\n\nR: We perform ablation studies to determine the number of iterations. Our goal is to implement the formulated affinity propagation process efficiently with fewer iterations. The detailed ablation experiments on the impact of varying iteration is provided in Table 6 of our main paper.\n\n**Q4. The runtime details in Table 7 are not clear, such as iterations, batch size, device...**\n\nR: Thanks for your careful comments. The batch size is set to 1, and the experiment is conducted on a single GeForce RTX 3090. The reported runtime represents the average time for one GP process testing duration of an epoch on the Pascal VOC dataset. We perform the runtime comparison under the same settings. We will make it clearer in the revision.\n\n**Q5. Explore the effects of Key Smoothing and Prompt Denosing in MaskCLIP.**\n\nR: Yes, the  Key Smoothing (KS) also aims to realize the global affinity propagation. To better explore their efforts,  we conduct detailed comparisons between the KS and our APro method based on MaskCLIP. The experimental results are shown in the Table below. \n\n|  $\\qquad$Method   |  CLIP Model  | Context | COCO  |\n| :------------: | :----------: | :-----: | :---: |\n|    MaskCLIP    |  ResNet-50   |  18.46  | 10.17 |\n|      +KS       |  ResNet-50   |  21.0   | 12.42 |\n| **+APro(Ours)**   |  ResNet-50   |  **21.67**  | **12.70**  |\n|    MaskCLIP    | ResNet-50x16 |  21.57  | 13.55 |\n|      +KS       | ResNet-50x16 |  22.65  | 15.50  |\n|  **+APro(Ours)**   | ResNet-50x16 |  **24.03**  | **16.30**  |\n|    MaskCLIP    |    ViT16     |  21.68  | 12.51 |\n|      +KS       |    ViT16     |  23.87  | 13.79 |\n|     +KS+PD     |    ViT16     |  25.45  | 14.62 |\n|  **+APro(Ours)**   |    ViT16     |  **28.91**  | **16.69** |\n| **+APro(Ours)+PD** |    ViT16     |  **29.42**  | **16.71** |\n\nBoth KS and our APro method bring performance gains. Compared with KS, our APro achieves better performance with different CLIP-based models. Especially, for ViT16-based model, our approach outperforms KS by +5.04\\% mIoU on Pascal Context and +2.90\\% mIoU on COCO, repectively. Equipped with Prompt Denoising (PD),  the models could achieve further improvements.\n\nWe have the following further discussions:\nKey Smoothing relies on the calculation of key feature similarities, which predominantly stems from high-level features of CLIP and computes pairwise terms within each pair of patches. Compared with KeySmoothing of MaskCLIP,  our method is built on a tree-based graph derived from lower-level images, which is capable of reflecting finer topological details. Furthermore, we design an efficient implementation that eliminates the need to compute similarities individually, significantly reducing time complexity.\n\nWe will add the above discussions in our revision, and strengthen our introduction and experimental sections."}]

Author rebuttal:
**General Response**

We express our gratitude to all reviewers for their insightful comments, which significantly strengthen our paper. We will revise our manuscript accordingly. 

As three out of the five reviewers concern the differences between our work and some existing works[1-3], we'd like to first clarify that our formulation and process are different from them. The works in [1,3] are based on the random walk and local operation, and [2] utilizes the sparsely weighted graphs with a GNN-based affinity attention module. In contrast to them, our presented method models the semantic affinity through the formulated affinity propagation processes, which takes advantage of both the global affinity model using the Minimum Spanning Tree as well as the complementary local one with Gaussian kernel.  

Besides, our work aims to devise a general and efficient plug-in module for various label-efficient segmentation tasks without the need to modify the network itself.  Compared with the existing methods, our approach is able to capture fine-grained affinity to generate accurate mask labels. For a detailed discussion and performance comparisons, please kindly refer to our **Response to Reviewer bFj5**.

To reproduce our results, we will release the full source code of our presented affinity propagation with efficient implementation for each label-efficient task.

In the following, we address the specific concerns point by point. The corresponding figures and captions are included in **the submitted PDF file**. Please feel free to check. 

&emsp;

[1] Learning Affinity from Attention: End-to-End Weakly-Supervised Semantic Segmentation with Transformers, CVPR2022. 

[2] Affinity Attention Graph Neural Network for Weakly Supervised Semantic Segmentation, TPAMI2021.

[3] Learning Pixel-level Semantic Affinity with Image-level Supervision for Weakly Supervised Semantic Segmentation, CVPR2018.

Meta-review: This paper received four Borderline Accept recommendations and one Borderline Reject (no update after the initial rating).

This work presents a semi-supervised learning approach for image segmentation with efficient label propagation has been proposed.

One main concern is about the significance in novelty as label propagation has been widely adopted in semi-supervised learning. The authors claimed to have presented new algorithms with efficient global and local affinity maps.

From a historical view, the weakly-supervised setting typically refers to the setting where the image-level labels are given without the pixel-level supervision.

Vezhnevets, A., Buhmann, J.M., "Towards weakly supervised semantic segmentation by means of multiple instance and multitask learning", CVPR 2010.
D. Pathak, E. Shelhamer, J. Long, and T. Darrell, “Fully convolutional multi-class multiple instance learning,” arXiv:1412.7144, 2014.
D. Pathak, P. Kr€ahenbuhl, and T. Darrell, “Constrained convolutional neural networks for weakly supervised segmentation,” ICCV, 2015.
P. O. Pinheiro and R. Collobert, “From image-level to pixel-level labeling with convolutional networks,” ICCV 2015.
G. Papandreou, L.-C. Chen, K. Murphy, and A. L. Yuille, “Weakly- and semi-supervised learning of a DCNN for semantic image segmentation,”
ICCV, 2015.

Label propagation has been widely initiated in the semi-supervised learning setting. It is unfortunate that the many of the recent deep learning papers fail to trace back to origins of the literature. For example, the work by Xiaojin Zhu is important but has been ignored:
"Semi-supervised learning literature survey", Xiaojin Zhu.
"Semi-supervised learning using gaussian fields and harmonic functions", X Zhu, Z Ghahramani, JD Lafferty, ICML 2003.

In some of the related works, the term of "weak-supervised" has been extended to include what was traditionally considered as "semi-supervised". This creates confusion in the literature. The authors are recommended to make the definition clear in the revision by better connecting to the literature.
Decision: Accept (poster)