Bridge the Points: Graph-based Few-shot Segment Anything Semantically

Authors: anqi  zhang
guangyu  gao
jianbo  jiao
chi harold liu
yunchao  wei
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 11:50:31

Abstract: The recent advancements in large-scale pre-training techniques have significantly enhanced the capabilities of vision foundation models, notably the Segment Anything Model (SAM), which can generate precise masks based on point and box prompts. Recent studies extend SAM to Few-shot Semantic Segmentation (FSS), focusing on prompt generation for SAM-based automatic semantic segmentation. However, these methods struggle with selecting suitable prompts, require specific hyperparameter settings for different scenarios, and experience prolonged one-shot inference times due to the overuse of SAM, resulting in low efficiency and limited automation ability. To address these issues, we propose a simple yet effective approach based on graph analysis. In particular, a Positive-Negative Alignment module dynamically selects the point prompts for generating masks, especially uncovering the potential of the background context as the negative reference. Another subsequent Point-Mask Clustering module aligns the granularity of masks and selected points as a directed graph, based on mask coverage over points. These points are then aggregated by decomposing the weakly connected components of the directed graph in an efficient manner, constructing distinct natural clusters. Finally, the positive and overshooting gating, benefiting from graph-based granularity alignment, aggregates high-confident masks and filters the false-positive masks for final prediction, reducing the usage of additional hyperparameters and redundant mask generation. Extensive experimental analysis across standard FSS, One-shot Part Segmentation, and Cross Domain FSS datasets validate the effectiveness and efficiency of the proposed approach, surpassing state-of-the-art generalist models with a mIoU of 58.7% on COCO-20i and 35.2% on LVIS-92i. The project page of this work is https://andyzaq.github.io/GF-SAM/.

Main paper: 
 introduction: 
 Previous semantic segmentation methods [1] [2] [3] [4] [5] [6] [7] [8] , which rely on the pixel-level classification, often struggle with generalization and overfitting due to limited labeled data. In addition, recent approaches, such as MaskFormer [9] , have shifted the paradigm to mask-based classification, offering a more flexible approach to improving the segmentation performance by exploiting the consistency and completeness of generated class-agnostic masks. The Segment Anything Model (SAM) [10] further marks a significant advancement by utilizing extensive pre-training on huge-scale dataset SA-1B to achieve more robust, class-agnostic segmentation capabilities. SAM excels in producing precise masks across various domains using simple prompts such as points, boxes, and coarse masks. While the boundaries of these masks can closely align with object boundaries, the lack of semantic Figure 1 : Performance comparisons of our approach against previous state-of-the-art methods regarding efficiency and generalized capabilities in Few-shot Semantic Segmentation. Figure 1(a) illustrates our approach's superior performance in efficiency and effectiveness across various model sizes. Figure 1 (b) demonstrates the generalizability of our approach across different domains.understanding and the requirement for manual prompts prevent SAM from being used in automatic semantic segmentation applications.Recent studies have attempted to automate this process in the Few-shot Semantic Segmentation (FSS), using a few reference images and a fine-grained external backbone network (e.g., DINOv2 [11] ) to guide SAM in segmenting target semantic objects. However, these methods face two main challenges: achieving suitable points for precise and full coverage of the target object, and handling the ambiguity of SAM-generated masks, from partial to complete coverage. Specifically, they either utilize the most similar candidate point prompts for iterative mask generation and refinement [12] , or build a restrictively selected set of point prompts for heuristically weighted mask merging based on manually designed metrics [13] , outperforming both previous specialist methods [ [14] [15] [16] [17] [18] [19] and generalist methods without SAM [20, 21] . However, these methods overlooked the underlying relationships between points (derived from fine-grained features) and masks (generated by SAM in a coarse-grained manner). This oversight led to low efficiency (as indicated in Fig. 1(a) ) and limited automation capabilities. Alignment between these two types of granularity could uncover the potential of simple decision-making on masks, which can eliminate redundant refinement and manual hyperparameter selection for complicated metrics.In this paper, we explicitly explore the relationship between point prompts and corresponding masks from SAM, and present a simple yet effective parameter-free framework with only one-time mask generation to segment anything semantically, in a graph-based few-shot manner. We first introduce a Positive-Negative Alignment (PNA) module to dynamically select point prompts using foreground and background references from reference images. Unlike existing methods, our approach combines different granularity by constructing a directed graph according to mask coverage over points. Then, we perform connectivity analysis on the constructed graph to obtain several weakly connected components as automatic clustering of point prompts, which bridges points and masks as well as fine-grained and coarse-grained features. To mitigate the inevitable introduction of false positives in the PNA module, we further leverage weakly connected component clusters and limited semantic information in selected points, to more accurately filter and merge masks that mismatch in different granularities. In particular, our proposed method involves two post-gating based on weakly connected clusters: the positive gating retains masks capturing a greater proportion of potential target areas, while the overshooting gating screens out outlier points near object boundary, with coverage self-consistency consideration.Extensive experimental analysis on Few-shot Semantic Segmentation demonstrates both the efficiency and effectiveness of our approach, as shown in Fig. 1(b) . We first conduct the experiments on generalized FSS datasets, including Pascal-5 i [22] , COCO-20 i [23] , FSS-1000 [24] and LVIS-92 i [13] . Our approach surpasses existing state-of-the-art approaches on these datasets, with 5.8% and 2.2% of improvement respectively on more challenging COCO-20 i and LVIS-92 i . As for the challenging One-shot Part Segmentation, our approach still exceeds previous methods with 1.6% of mIoU on both PACO-Part and PASCAL-Part. Furthermore, to demonstrate the ability of our approach across different domains, we perform an evaluation on several specific datasets, including Deepglobe [25] , ISIC [26] , and iSAID-5 i [27] . The proposed approach establishes new state-of-the-art performance on mIoU with 49.5% on Deepglobe, 48.7% on ISIC, and 47.3% on iSAID-5 i .Overall, our contributions are summarized as follows:• We present, to our knowledge, the first graph-based approach for SAM-based few-shot semantic segmentation, modeling the relationship of SAM-generated masks in an automatic clustering manner. • We propose a positive-negative alignment module and a post-gating strategy based on the weakly connected graph components, enabling a hyperparameter-free pipeline. • Extensive experimental comparisons and analysis across several datasets over various settings show the effectiveness and efficiency of the proposed method. 
related work: 
 Few-shot semantic segmentation. Few-shot Semantic Segmentation (FSS) [22] aims to segment the target object using only a limited number of annotated reference samples for guidance. Previous FSS methods are mainly categorized into two types, namely the methods based on prototype matching [28] [29] [30] [31] [32] [33] [34] and methods based on pixel-wise matching [35] [36] [37] [38] [39] [40] . The methods based on prototype matching, e.g. PFENet [31] , BAM [41] , SSP [42] , use the Mask Average Pooling operation from SGOne [43] to generate a prototype as a global representation of the reference features, and compare the target features with the prototypes. The methods based on pixel-wise matching compute the correlation of all pixels between target and reference features. Then different methods address the correlations through distinct mechanisms, such as 4D Convolution (e.g., HSNet [14] ) and Transformer (e.g., HDMNet [44] , AMFormer [45] ). Although these specialist models perform significantly on specific tasks, they are prone to overfitting the training samples and often struggle to adapt to domain shifts.SAM-based semantic segmentation. Recently, Segment Anything Model (SAM) [10] has shown remarkable zero-shot class-agnostic segmentation capabilities using prompts like points, boxes, and coarse masks. However, the coarse-grained feature representation of SAM limits its effectiveness for fine-grained semantic segmentation tasks. Several approaches have been proposed to extend SAM for semantic segmentation. For example, Semantic-SAM [46] jointly train the model on SA-1B and other semantic aware segmentation datasets to enhance granularity. OV-SAM [47] combines SAM and CLIP [48] for open-vocabulary semantic segmentation. Moreover, some methods introduce SAM into FSS tasks. PerSAM and PerSAM-F [12] leverage SAM for personalized segmentation with one-shot guidance. Matcher [13] uses a SAM-based training-free structure, achieving impressive performance in both FSS and One-shot Part Segmentation. VRP-SAM [49] trains an external Visual Reference Prompt Encoder to automatically generate prompts from reference images using points, scribble, box, or masks. However, previous training-free methods struggled to balance performance and efficiency, often relying on excessive external manual hyperparameters. 
preliminaries: 
 Few-shot Semantic Segmentation (FSS) aims to segment target objects in an image with a few annotated reference images. Consider a scenario where each group of samples contains a target image x t and a reference image set R = {x r k , y r k } K k=1 with the size of H × W , where x r k and y r k mean the k th reference image and its corresponding mask. Focusing on the 1-shot case, where K = 1, it begins with a feature extraction backbone network f B (•), which encodes both x t and x r into semantic features F t and F r in R hw×c , where h and w denote the height and width of the feature maps, and c is the feature dimension. Subsequent few-shot processes utilize these feature maps to generate a predicted segmentation ỹ ∈ R H×W for x t . This prediction is then compared to the Ground Truth (GT) y t for evaluation. a core architecture that includes an image encoder, a prompt encoder, and a mask decoder, SAM effectively processes input images x t and prompts P to produce detailed segmentation masks ŷ. These masks accurately delineate specific objects or regions within the images, based on the guidance provided by the prompts. 
method: 
 Diverging from traditional methods, we use a directed graph to exploit the natural relationships between points and their corresponding masks, representing fine-grained and coarse-grained features, respectively. As shown in Fig. 2 , our approach mainly comprises the Positive-Negative Alignment (PNA) module, Point-Mask Clustering (PMC) module, and Post-Gating strategy. The PNA module leverages semantic features from the backbone network to sort pixel-wise correlations into similarity maps, enabling precise point selection. The PMC module then clusters masks based on these selected points, while Post-Gating strategy refines the selection, enhancing the accuracy and reliability of the final prediction.The PNA module efficiently selects point prompts to balance the number of points and coverage of target objects. Using the semantic features F r and F t from the reference and target images respectively (with e.g., DINOv2 [11] ), we get the pixel-wise correlation matrix C ∈ R hw×hw :EQUATIONwhere C(i, j) represents the similarity between the i-th pixel of target features F t (i) and the j-th pixel of reference features F r (j).To minimize hyperparameter reliance, we leverage background features typically overlooked in FSS, indicated by the negative mask y r = ¬y r of the reference image. According to y r and y r , we divide C into C + and C -in R hw×hw for foreground and background features, respectively. We then introduce two positive similarity maps in mean and max aspects respectively:EQUATIONwhere I resizes y r to the same resolution as F r and then flatten it into a vector, max(•) finds the maximum value in the i-th row of C + . The mean positive similarity map S + mean ∈ R hw captures global similarity towards the reference object but may blur distinct internal features, reducing accuracy for complex objects. In contrast, the max positive similarity map S + max ∈ R hw focuses on the most similar regions, enhancing recall but also increasing noise. To maintain distinctiveness while reducing noise, we introduce the mixture similarity map S + mix = S + mean ⊙ S + max using the Hadamard product. This method boosts target region distinctiveness by merging the strengths of both maps, while diminishing noise through the more stable global similarity.To select prompt points, we also use the mean negative similarity map S - mean , which reflects background similarity, noting that similar objects typically share higher background similarity values. We then align S + mix and S - mean by min-max normalization M to get:EQUATIONwhere S p ∈ R hw is the filtered map for point selection, and 1 {•} is 1 if the condition is true and 0 otherwise. Although we minimize false negatives, noise points remain. To select suitable points from S p without hyperparameters, we define the sum of elements in S p as the number N of points to be selected. We then pick the N highest-value points from S p as the point prompt set P = {P l } N l=1 .We utilize point prompts from P to generate masks with SAM. Each point P l in P corresponds to a unique mask ŷl ∈ R H×W . As our point selection strategy prioritizes the coverage of objects, false-negative masks are unavoidable. Moreover, mask coverage can vary significantly within the same region, ranging from partial to full object coverage. This necessitates understanding the internal relationships among coarse-grained masks and points from fine-grained feature comparison to ensure those covering the same target are accurately gathered.To address this, we design the Point-Mask Clustering (PMC) module, which clusters points and their corresponding masks based on mask coverage over points. Following the principles of efficiency and automation, the PMC module is based on a directed graph G = (V, E) with the vertex v l in V representing point P l and its corresponding mask ŷl . Edges in E are established based on mask coverage over other points; an edge e l,m exists if mask ŷl covers points P m (with m ̸ = l). Specifically, we do not establish edges for masks covering their corresponding points to avoid creating loops.The graph G is a directed simple graph, allowing us to cluster vertices by identifying weakly connected components. This clustering process is hyperparameter-free, ensuring that every pair of vertices u, v ∈ V within the same component has a directed path between them. Each weakly connected component encompasses a set of points Pp (with P = { Pp }) that are all covered by the union of their masks in Mp , where p indexes the clusters.The advanced SAM plays a crucial role in maintaining the precision of the generated masks. The precision of high-quality masks typically ensures non-overlapping between masks and prompting points of adjacent regions, especially those of different categories. This is the precondition for the efficacy of our PMC module, as even slight errors could significantly impact the clustering accuracy.Our PNA module, while efficient in selecting points, inadvertently includes false positives, as detailed in Sec. 4.1. To mitigate this, we further develop two gating strategies targeting distinct types of false positives based on clusters formed from weakly connected components.Positive gating. Despite the method in Sec. 4.1 diminishing the noise points outside the target region, there are still a few remaining noise points. These issues may have minimal impact on traditional segmentation methods, but under the SAM framework, masks derived from these noise points can significantly degrade accuracy. Moreover, some clusters of masks may extend beyond their intended target regions due to inaccuracies in SAM-generated masks or because the targeted object is part of a larger entity. Thus, we propose a Positive Gating strategy to address these issues.This strategy prioritizes mask effectiveness by assessing whether a mask contains more positive than negative pixels, thereby facilitating a specialized designed mask growth for final prediction. The focus of mask growth is to enhance coverage of the target area rather than multiple objects, while minimizing background inclusion. Firstly, this method utilizes a parameter-free gating mechanism that discriminates between pixel polarities, based on the positive and negative similarity maps, S + mean and S - mean , as described in Sec. 4.1. To achieve this, we utilize S + mean and S - mean , along with the median of S + mean (i.e., the midpoint between the maximum and minimum values of S + mean ), to constructs the polarity map R as follows:EQUATIONThen, using the polarity map R, we calculate the number of positive pixels of the l th mask as follows:EQUATIONwhere I resizes and flattens ŷl to the feature map dimensions. Subsequently, for each cluster Mp of weakly connected components, we sort the masks according to the ratio of positive pixel numbers to their areas. The indices of these sorted masks are denoted by Q. We then initialize a blank pseudo mask ÿp ∈ R H×W and a set of positive points P + . Following this, we apply a Mask Growth algorithm as outlined in Sec. A.1 and Alg. 1 for maintaining positive masks. This algorithm iteratively evaluates whether the region of ŷq outside the pseudo mask ÿp is positive, updates ÿp with the identified positive mask, and adds its corresponding point into P + .Overshooting gating. The fine-grained semantic features from f (•) are reliable for locating target objects, yet the point coverage of the target areas varies, leading to both under-coverage and overcoverage. SAM effectively addresses under-coverage; however, over-coverage, which extends beyond target boundaries, often produces false-positive masks. These overshooting points, while semantically similar to the target areas in F t , typically derive masks that cover areas outside the target, resulting in a mismatch of representations between the granularity of points and masks. Thus, these points cannot be clustered with points inside the target areas.Hence, we devise an overshooting gating strategy with consideration of self-consistency to eliminate overshooting points and their associated masks. As shown in Fig. 3 , We assess the similarity between the features of each point P l and the union mask ŷp ∈ R H×W from each mask cluster Mp . The similarity computation for estimating self-consistency is performed as follows:EQUATIONwhere Sim(•, •) refers to the correlation calculation mentioned in Eq. 1. We introduce an external function dist(•, •) to measure the distance in F t between each point P l and the nearest selected point in Pp . This measure helps confine comparison to neighboring clusters, minimizing interference from other instances. We then identify the cluster most similar to the points and retain those in the point set P sc that are more similar to their respective clusters. Mask Merging. Finally, we obtain two distinct sets of points, namely P + and P sc . We then union the masks corresponding to points that are common to both P + and P sc . The merged masks form the final prediction, denoted as ỹ.5 Experimental Results 
datasets: 
 To illustrate the Few-shot Semantic Segmentation ability and generalization capacity, we conduct three types of sub-tasks, i.e. standard Few-shot Semantic Segmentation, One-shot Part Segmentation, and Cross Domain Few-shot Semantic Segmentation. The datasets for these tasks are as follows:Pascal-5 i , COCO-20 i , FSS-1000, and LVIS-92 i are standard FSS datasets. Pascal-5 i [22] is based on the Pascal VOC 2012 [53] and SDS [54] . The 20 classes are separated into 4 folds of 5 classes. COCO-20 i [23] is an 80-class dataset from MSCOCO [55] , which has 4 folds with each fold containing 20 classes. FSS-1000 [24] contains 1000 classes. The training, validation, and testing folds contain 520, 240, and 240 classes, respectively. LVIS-92 i [13] is more challenging for evaluating generalist models, which select 920 classes with more than 2 images and divide these classes into 10 folds.PASCAL-Part and PACO-Part [13] are One-shot Part Segmentation datasets. PASCAL-Part [56, 57] contains 56 different object parts in 4 superclasses. PACO-Part is built based on the PACO dataset [58] , which has 456 object part classes. The 303 classes with at least 2 samples in PACO-Part are divided into four folds following Matcher [13] .Deepglobe, ISIC2018, and iSAID-5 i are Cross Domain FSS datasets. The Deepglobe [25] contains satellite images of geographic categories including urban, agriculture, rangeland, forest, water, and barren. The ISIC2018 [26] is a skin lesion analysis dataset with three classes. The iSAID-5 i [27] evenly split 3 folds for 15 classes based on the remote sensing dataset iSAID [59] .Following the settings of PerSAM [12] and Matcher [13] for a fair comparison, we use DINOv2 [11] with a ViT-L/14 [60] as our feature extraction backbone, and SAM [10] with ViT-H as the mask generator. The input image sizes are set to 518×518 for DINOv2 and 1024×1024 for SAM following Matcher [13] . Except for the default hyperparameters of SAM and DINOv2, our approach does not have any external hyperparameter. We apply the mean Intersection over Union (mIoU) metric for evaluating the performance. All experiments are conducted on a single NVIDIA RTX2080Ti.Comparison on the standard FSS datasets. We compared our approach with other state-of-the-art specialist and generalist models. As shown in Tab. 1, our approach achieves 72.1% mIoU on the Pascal-5 i dataset and 58.7% mIoU on COCO-20 i dataset, which surpasses all previous specialist and generalist state-of-the-art models. Our approach reaches 35.2% mIoU in the more challenging dataset of LVIS-92 i , with 2.2% of improvement compared to the previous training-free method Matcher. The performance remains competitive on the FSS-1000 compared with specialist models. The 5-shot result of Pascal-5 i , COCO-20 i , and LVIS-92 i further extends the lead, which shows that our approach can effectively handle the few-shot scenario.Comparison on the One-shot Part Segmentation datasets. The One-shot Part Segmentation tasks evaluate the ability to fetch the target part from the whole object. The results in Tab. 2 show that our approach achieves the mIoU of 44.5% and 36.3% on both datasets of PASCAL-Part and PACO-Part, respectively. Our approach outperforms the state-of-the-art generalist model Matcher with 1.6% on both datasets. Given that Matcher employs specific hyperparameters to enhance part segmentation, our superior performance demonstrates the adaptability of our approach across both object and part segmentation contexts.Comparison on the Cross Domain FSS datasets. The Cross Domain FSS tasks validate the performance on different domains. Our approach achieves state-of-the-art performance in datasets of Deepglobe, ISIC, and iSAID-5 i among other specialist domain models and generalist models. Especially within the context of the skin lesion analysis dataset ISIC and remote sensing dataset iSAID-5 i , our approach outperforms Matcher by margins of 10.1% and 13.8% respectively. Point selection. We evaluate the impact of various similarity maps and the parameter-free selection of top N points on performance, as detailed in Sec. 4.1. As shown in Tab. 3, using either S + mean or S + max alone leads to a performance drop of up to 5.6% compared to using both. This decline is due to the inherent limitations of S + mean and S + max discussed in Sec 4.1. Additionally, the evaluation confirms that picking the top-N points based on similarity, which is parameter-free and requires no additional settings, simplifies the process and increases accuracy by 2.1%.Clustering method. We compare our PMC module using weakly connected components with the PMC module using strong connected components, which provides finer clustering results. According to our experiment results in Tab. 4, the clusters from weakly connected components provide better performance on COCO-20 i and LVIS-92 i for both gating, as these clusters of masks have ideal coverage of the objects. Simply filtering the masks without clustering-based gating can only achieve 44.0% mIoU on COCO-20 i and 24.2% mIoU on LVIS-92 i , which is significantly lower than the performance achieved with clustering-based gating. Furthermore, our dynamic hyperparameter-free clustering method outperforms the k-means++ with 1.2% on both datasets. Note that k of k-means++ is set to 10 following Matcher [13] .Positive gating. Our approach compares the number of positive points and negative points in Ŝ+ (Num) to judge whether the mask is positive. We conduct experiments for the strategy of comparing the sum of positive and negative values (Sum). The results in Tab. 5 demonstrate the Num strategy yields better performance, as comparing the number of pixels mitigates the influence of a few excessively high similarity values. Furthermore, the utilization of the Mask Growth algorithm improves both FSS and Part Segmentation performance by carefully retaining the positive regions. However, it weakens the improvement of Num due to their similar effects.Overshooting gating. Our Overshooting gating aims to filter out the overshooting points closely neighboring to target regions, thus having a less remarkable improvement of 1.6% compared to Positive Gating, as shown in Tab. 6. This performance still surpasses the mean similarity of com-paring points with regions of clustered points (Point Sim.) or the prototypes from Masked Average Pooling [43] with union masks (MAP Sim.). More importantly, the distance function avoids the gating from 9.6% of performance decline. It ensures each cluster only affects its neighboring points.Here we present the qualitative results of Matcher, Baseline (1 st row in Tab. 4), Baseline+PG (2 nd row in Tab. 4) and our approach in Fig. 4 . The bipartite matching of Matcher has a negative influence when the areas of the target object in reference and target images have significant differences, as shown in the 1 st and 3 rd rows. The positive gating with clustering filters out the noise masks in the 3 rd row, while the Overshooting Gating further removes the masks belonging to overshooting points in the 2 nd and 4 th rows. More qualitative analyses please refer to the appendix. 
conclusion: 
 In this paper, we proposed an efficient, training-free SAM-based FSS approach that requires no external hyperparameters. As an automatic SAM-based semantic segmentation pipeline, our approach balanced candidate points and object coverage in the Positive-Negative Alignment (PNA) module, then used SAM-generated masks in the Point-Mask Clustering (PMC) module to enhance Post Gating. Extensive experiments validated the superior performance of our approach, advancing semantic segmentation without extensive parameter tuning or training. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper has no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The existing assets used in our paper, i.e., SAM and DINOv2, are released on GitHub under Apache License 2.0.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: We mention the Mask Growth algorithm in Sec. 4.3. The Mask Growth algorithm is designed for each cluster of masks Mweak,p . The details of the algorithm are shown in Alg. 1. We first initialize an empty set P + and a blank pseudo mask ÿp . Then, we start an iterative process and get the current mask ŷq based on the sorted sequence of indices Q. The parts of the current mask ŷq overlapping with ÿp are removed. We compute the positive value s + q of the remaining parts. If s + q is positive, the mask ŷq is updated into the ÿp and its corresponding point P q is added into P + . As soon as the iterative process finishes, the set of positive points P + is established.Input: Mp , ÿp , Q, P + for n = 1 to |Q| do q ← Q(n) ŷq ← Mp (q) ŷq = ŷq & ∼ ÿp s + q ← hw i=1 Ŝ+ (i) ⊙ I(ŷ q )(i)if s + q > 0 then Add P q to P + . ÿp = ŷq ∨ ÿp end if end for Output: P +Our approach has impressive performance on Few-shot Semantic Segmentation tasks. However, due to the resolution of features F t from DINOv2 not aligning with the required resolution for prompting the SAM, we directly map the coordinates of points in F t to coordinates for prompting. This results in coordinate bias for small objects, as the gap between neighboring points can reach approximately 28 pixels. Our future work will focus on locating small objects.As a completely automatic SAM-based few-shot semantic segmentation approach without external hyperparameters, our method is capable of handling various scenarios of semantic segmentation, as demonstrated by our extensive experiments. The efficiency and generalizability of our method ensure a wide range of applications. Furthermore, since our training-free method is constructed upon the widely used open-source foundation models, we have not identified the negative societal impact to date.Our approach aims to address several issues present in previous SAM-based FSS methods to achieve an automatic SAM-based model. These issues include the requirement of excessive external hyperparameters, overusing the mask generator of SAM, prolonged inference times, etc. The Tab. 7 shows the difference between our approach and previous SAM-based FSS methods. Fig. 5 shows the difference in using SAM as the mask generator between our approach and previous methods. Fig. 5 (a) presents the iterative refinement of PerSAM, which involves generating masks from SAM 3 times. Fig. 5 (b) exhibits that Matcher introduces an external Automatic Mask Generator, which automatically prompts for generating all mask proposals in the image. Our approach in Fig. 5(c ) only utilizes the standard Mask Generator of SAM and generates the masks with our prompts only once. ViT encoder of SAM, for fine-grained features. We visualize the representative samples of Pascal-5 i in Fig. 6 . The 3 rd column of maps represents the self-similarity of the F t SAM . We introduce the 3 × 3 average pooling for F t SAM followed by computing the cosine similarity between the pooled features and F t SAM . The maps illustrate that F t SAM can accurately identify the regions of objects within the image, where the features within each object region are nearly identical, while features between neighboring different objects are distinct.Although the characteristics of F t SAM ensure the generation of high-quality masks, the coarse-grained features are not suitable for locating the objects, as shown in the 4 th column. The similarity between F t SAM and F r SAM cannot effectively distinguish the target object well compared to S + mean from DINOv2. Therefore, we follow the previous methods using DINOv2 for fine-grained features.Our Point-Mask Clustering module introduces a parameter-free clustering method by constructing a graph of coverage. The effectiveness of the method primarily relies on the high-quality masks, whose boundaries mostly align with the object boundaries. We roughly analyze the coverage of masks generated from the points in the ground truth foreground region using 4000 samples from Pascal-5 i . In particular, we get the union of masks from the foreground points as ŷfore , and visualize three distributions, including the distribution of IoU between ŷfore and union of masks from background points ŷback in Fig. 7 , the ratio between the number of background points and all points covered by the ŷfore in Fig. 8 , the number of background points covered by ŷfore in Fig. 9 . The distribution charts demonstrate that most of the samples have acceptable coverage on the error points for Point-Mask Clustering. Given the limited precision of ground truth annotations, the analysis is for reference only. The effectiveness of our Point-Mask Clustering is validated in our ablation study in Tab. 4. In Sec. 4.3 and Sec. A.1, we introduce the Mask Growth algorithm as our strategy for judging whether the mask is positive. We compare the strategy to separately judging each mask in Tab. 5 and judging the union mask of each cluster in Tab. 15. While simply judging the union mask shows better performance on COCO-20 i and LVIS-92 i that require complete coverage of objects, its performance on One-shot Part Segmentation has a significant decline. Considering the generalizability of our approach, we select the Mask Growth algorithm as our strategy.We conduct additional qualitative analysis to better present the result of our approach. Fig. 11 further compare the Matcher, Baseline, B+PJ, and B+PJ+OJ (Ours) following Sec. 5.5. Fig. 12 illustrate the intermediate contents in the Post Gating. Moreover, we provide additional visualization results of standard FSS in Fig. 13 , One-shot Part Segmentation in Fig. 14 , and Cross Domain FSS in Fig. 15 . These qualitative results demonstrate the effectiveness of our approach. Notably, some of the results are even better than the corresponding annotations. Justification: We discuss both potential positive societal impacts and negative societal impacts of our work in the appendix. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: All reviewers land on the positive side. They all enjoy the significance of the problem explored in the paper, the comprehensive and convincing experimental results as well as good practicability of the proposed method, i.e., it is hyperparameter-free. The AC suggests acceptance and encourages the authors to include the discussion in the rebuttal into the final version.

Reviews: review: paper_summary: paper_summary: This paper extends SAM to few-shot semantic segmentation tasks by proposing an approach based on graph analysis and representation learning. The contributions include a Positive-Negative Alignment module to generate the initial points prompt using DINOv2 features, as well as Point-Mask Clustering and Post Gating modules to filter the proper points based on the SAM generated masks. The proposed method exhibits efficiency and performance advantages over previous work such as PerSAM and Matcher.
strength_weakness: strength_weakness: (1)	The proposed method is specifically tailored for DINOv2 and SAM, is it possible to apply it to other foundation models? This could broaden the impact of the method. 

(2)	In Figure 1(b), the scales of the axes are unclear. Are the starting points of the nine axes all 0?

(3)	On the FSS-1000 dataset, the performance of the proposed method is comparable to Matcher, which deserves a discussion. For example, what factors may have contributed to this result.
questions: questions: See weakness.
limitations: limitations: The limitations have been discussed.
paper_summary: paper_summary: The paper first proposes graph-based approach for SAM-based few-shot semantic segmentation, modeling the relationship of SAM-generated masks in an automatic clustering manner. A positive-negative alignment module and a post-gating strategy based on the weakly connected graph components, enabling a hyper parameter-free pipeline. Extensive experimental comparisons and analysis across several datasets over various settings show the effectiveness and efficiency of the proposed method.
strength_weakness: strength_weakness: 1. The captions are not detailed, especially in Figure I and 2.
2. The overall organisation and presentation of the article are poor and need improvement.
Some details:
① On the left side of the first line of Figure 2, the images are ‘reference on top and target on bottom, but the features become ‘reference on bottom target on top’; it's not consistent.
② In my understanding, in Figure 2，positive-negative alignment should be conducted on the target image using the foreground and background features of the reference's image, but the part is very unclear and not informative and does not show the above content.
③Point-Mask Clustering part in Figure 2 can be understood that it wants to express the cluster of the points to different targets in the images, but the drawing is very casual, and there is no mark or expression.
3. How to conduct mask merging? Is each point used to generate a mask and then merge, or is the cluster of points used together to SAM to generate mask prediction, or are there other ways? Give the details.
questions: questions: See the weakness part.
limitations: limitations: The author provides the limitations in the appendix. They say the coordinates of points will miss the small objects. This is a real problem and is suitable for further study.
paper_summary: paper_summary: This paper proposes a graph-based approach for Few-shot Semantic Segmentation (FSS) based on the Segment Anything Model (SAM).
The authors propose a Positive-Negative Alignment module to select point prompts and a Point-Mask Clustering module to align the granularity of masks and selected points.
The proposed method surpasses state-of-the-art generalist models on COCO-20i and LVIS-92i datasets, and also performs well on One-shot Part Segmentation and Cross Domain FSS datasets.
Moreover, the proposed method is hyperparameter-free and efficient.
strength_weakness: strength_weakness: 1. In L173, "This is the precondition for the 
efficacy of our PMC module, as even slight errors could significantly impact the clustering accuracy"
The authors should provide some visualization examples or experiments to verify this statement.

2. In Table 4, I notice weak or strong connected components are not clearly defined and the difference are also very small. The authors should provide more analysis to explain this.
And what is the hyperparameter for K-means++? Have you tried different hyperparameters for K-means++?

3. I notice the authors conduct ablation studies on different datasets for different components. I hope the authors can provide more experiments on part segmentation. Since previous SOTA Matcher require different hyperparameters for part segmentation. Conducting ablation on part segmentation can further prove the hyperparameter-free advantage of the proposed method.
questions: questions: Can this methods applied to other tasks such as video object segmentation or instance segmentation?
limitations: limitations: The authors have discussed the limitations of the proposed method in appendix.

Comments: title: Author-reviewer discussion
comment: After reading the author's response, most of my concerns have been addressed. I've decided to raise my score.
We thank the reviewer for taking the time to review our response. We’re pleased that our rebuttal has addressed the concerns and we sincerely appreciate the reviewer's positive score. We will incorporate the key points the reviewer raised as we work on the final version of the revised paper.
Dear reviewer DDH8 and zdFP,

Since the authors provided their responses, please read the responses, respond to them on in the discussion, and discuss points of disagreement if necessary by Aug 13.

Best regards,

AC
After reading the author's response, most of my concerns have been addressed. I've decided to maintain my current score.