Thank you very much for your valuable comments. We have revised the manuscript based on your feedback, and also provide responses here. All the revisions have been marked in red in the manuscript.

Q. There is a concern regarding the Linear Programming (LP) formulation, as opposed to some aspects of my statements in strengths, which, while crucial, seems to necessitate significant memory, especially when handling large datasets with extensive semantic classes. This could potentially hinder the algorithm’s efficiency and applicability in broader contexts. We agree that larger datasets with extensive semantic classes will necessitate more memory. We propose two techniques to address this challenge:

(1) Apply an uncertainty criterion to select a subset of images with the highest uncertainties. Then, apply the LP based selection only on the selected subset of images. Since the uncertainty of an image can be easily computed using entropy, this can substantially reduce the memory and computational overhead. Such a strategy has been used in previous AL research to deal with large datasets [1].

(2) GPU-based parallel algorithms have been proposed to solve large-scale LP problems [2]. This can greatly reduce the computation time and is an effective way to solve large scale LP problems.

Both of these will be investigated as part of future research.

[1] S. Chakraborty, V. Balasubramanian, Q. Sun, S. Panchanathan, J. Ye. Active Batch Selection via Convex Relaxations with Guaranteed Solution Bounds. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) 2015

[2] J. Li, R. Lv, X. Hu, Z. Jiang. A GPU-Based Parallel Algorithm for Large Scale Linear Programming Problem. Intelligent Decision Technologies, 2011

We have mentioned this in the future work section of the revised paper.

Q. The theoretical foundation of the proposed framework seems somewhat lacking. Since the formulations primarily rely on heuristics-based LP formulation, there’s an inherent uncertainty regarding the algorithm’s reliability and the specific conditions under which it might fail. A more robust theoretical backing would enhance the algorithm’s credibility and predictability. We agree that the solution to the LP problem may sometimes fail (if the problem is infeasible / unbounded). However, in our wide range of experiments (across different datasets, query budgets, backbone network architectures and different initial training set sizes) we never encountered a situation where the solution to the LP problem failed.

In case the solution to the LP problem fails in a particular AL iteration, a possible strategy is to use the class presence uncertainty matrix $H$ (in Equation 1) and query the $B$ image-class pairs with the highest class presence uncertainty; that is, for that AL iteration, we will be querying samples based on only the uncertainty criterion and not the redundancy criterion.

Deriving the specific conditions under which the LP might fail is a topic of theoretical optimization research, and is outside the scope of this paper. Linear programming (LP) and quadratic programming (QP) solvers have been extensively used in AL research [3 ,4, 5].

[3] Rita Chattopadhyay, Wei Fan, Ian Davidson, Sethuraman Panchanathan, and Jieping Ye. Joint transfer and batch-mode active learning. In International Conference on Machine Learning (ICML), 2013.

[4] Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013.

[5] Rita Chattopadhyay, Zheng Wang, Wei Fan, Ian Davidson, Sethuraman Panchanathan, and Jieping Ye. Batch Mode Active Sampling Based on Marginal Probability Distribution Matching. ACM Transactions on Knowledge Discovery from Data, 7(3), 2013.

Q. It’s essential to highlight the algorithm’s pronounced dependence on a considerable initial dataset for optimal functionality. This dependency could limit its utility in scenarios where access to such extensive initial data is restricted or impractical. We agree this is a very valid concern. To address this, we have conducted two experiments on the Cityscapes dataset, where we reduced the size of the initial training set to 300 and 500 images with pixel-level annotations. The results are presented in Figure 11 in Section G of the Appendix. The results depict a very similar trend as Figure 2 in the paper. From the results we note that the mIoU furnished by our binary query based AL method is still very much competitive to the pixel-level and region-level annotation methods, and it outperforms the other binary level annotation methods. Thus, our method is still effective when the size of the initial training set is much smaller.

Q. The algorithm presented in this paper aims to reduce human labeling efforts, enhancing ease and efficiency in the data annotation process. However, it appears that this simplification comes at a cost, with the algorithm showing a certain level of compromised performance according to Figure 2 and Figure 3. The effort to make the labeling process more user-friendly and less labor-intensive seems to inadvertently lead to a trade-off, affecting the overall efficacy of the algorithm. This aspect suggests a delicate balance between facilitating human involvement and optimizing algorithm performance. Thank you for this insightful comment. As you have correctly pointed out, the main goal of this research is to study the trade-off between the human labeling effort and the overall efficiency of the algorithm. It is expected that, as we attempt to develop novel query mechanisms to reduce the labeling burden on the human oracles, we have to compromise on the performance of the algorithm. Since an AL algorithm with binary annotation did not exist, this trade-off could not be studied for image segmentation applications; to our knowledge, the proposed framework is the first of its kind to develop a binary query based annotation mechanism for AL in image segmentation, which enables us to study this trade-off. Our analysis revealed that we can often save substantial amounts of human annotation effort, in exchange for a minor loss in accuracy. For instance, from the results in Figure 3, we note that the final mIoU achieved by our binary query method is very close to that achieved by Coreset (less than 0.5% difference), which requires pixel-level annotations for the queried images; however, from Table 3, we note that the total annotation time required by Coreset is $134.89$ times greater than our method. We believe that the study of such a trade-off can provide valuable insights during the design and development of image segmentation applications.

Q. The paper appears to omit consideration of recent advancements in active learning techniques. Notably, very few pixel annotation strategies, such as “PixelPick” [1], which emphasizes minimal pixel-based annotations in each image, and “BADGE” [2], “Balanced Entropy” [3], or “PowerBALD/PowerEntropy” [4], potentially offering a more effective approach than CoreSet, are overlooked. These examples, while not exhaustive, underscore the breadth of contemporary methodologies that could be instrumental in enriching the algorithm’s framework and applicability. By integrating these current developments, the paper could ensure a comprehensive alignment with the evolving landscape of the field, thereby bolstering the algorithm’s relevance and efficacy in the context of modern active learning paradigms. Thank you for this suggestion. We have added the mentioned references in the revised version of the paper. AL techniques like BADGE, BALD and Balanced Entropy require all the pixels to be annotated in the queried images. Since our annotation mechanism is fundamentally different (binary annotation), we did not perform an exhaustive comparison with state-of-the-art AL techniques. Rather, we selected our comparison baselines to cover a wide variety of annotation strategies: pixel-level annotation, region-level annotation and binary level annotation. Within the first category, we used Coreset (a state-of-the-art AL technique) and Entropy (a widely used AL technique) as our comparison baselines. Since our main contribution is a novel annotation mechanism for AL in image segmentation, we selected the comparison baselines to cover different types of annotation strategies, rather than only the state-of-the-art AL methods, which require pixel-level annotation.

Q. Entropy equation Thank you very much for pointing this out. We have corrected Equation (1) in the revised version of the paper.

Q. Image Redundancy computation We agree that there may be better ways to handle the situation where the cosine similarity produces a negative value. We assign a value of $0$ to entries where the cosine similarity is negative, so that the matrix $R$ does not contain any negative entries; this is critical in the proof of Theorem 1.

An alternative idea may be to compute the redundancy matrix R and normalize all the values to be within a given range (say, $0$ to $1$) by applying an appropriate transformation. This will be investigated as part of our ongoing work.

Q. Generalizability to object detection We agree with your concern and have removed this statement from the future work section.

We hope these answer your questions. If you have any additional questions, we will be happy to answer.

Thank you very much for your valuable comments.

Q1. Algorithm 1 does not include all the details of the method, that is, Algorithm 1 only introduces the method of selecting the unlabeled images and the corresponding semantic classes, but does not mention how the annotator answers yes/no, nor does it mention how to achieve higher precision pixel level annotation iteratively after obtaining M

Q2. How to annotate an image at the pixel level only by determining the classes of the objects in the image? In other words, if all the classes of the objects in the image are correct, how to accurately locate these objects and achieve pixel level annotation?

For both these questions, we would request the reviewer to kindly refer to Sections F.1 and F.2 in the Appendix, where we have explained in detail how we locate the objects in a given image and achieve pixel level predictions with binary feedback. We also have a couple of visual illustrations in Section F.2, where we have demonstrated how an object gradually shifts to its correct location in a particular test image, as the model receives more and more binary feedback through the AL iterations.

We hope these answer your questions. If you have any additional questions, we will be happy to answer.

Thank you very much for your valuable comments. We have revised the manuscript based on your feedback, and also provide responses here. All the revisions have been marked in red in the manuscript.

Q. Both metrics of uncertainty and diversity are lack of novelty. Besides, in computing class presence uncertainty, the calculation of the probability that image i contains the semantic class j remains unclear. Is it the average probability of pixels belonging to the semantic class j within image i? We agree that the uncertainty and diversity metrics have been explored in AL research before and are not novel. Our primary novelty in this research is the formulation of an AL technique for image segmentation which poses only binary queries to the human annotators. To the best of our knowledge, such a query technique has not been explored before in the context of image segmentation. Since our main contribution is not the development of an active sampling criterion, rather it is the development of a novel query strategy, we used an existing criterion based on uncertainty and diversity in our work.

You are absolutely correct. The probability that image i contains the semantic class $j$ is the average probability of pixels belonging to the semantic class $j$ within image $i$. We have clarified this in the revised version of our paper, just before Equation (1).

Q. The rationale of selecting informative image-class pairs through an optimization problem, rather than designing a sampling strategy, lacks clarity. Our objective was to select a batch of image-class pairs that are both informative individually, and mutually diverse (non-redundant). It may be a little challenging to design a sampling strategy to simultaneously optimize two criteria. A possible sampling strategy may be to first select $K$ (where $K > B$, the actual batch size) image-class pairs based on the informativeness criterion only, and then select the $B$ most diverse image-class pairs from the selected subset. This would be a two-step solution process.

In contrast, in our algorithm, we devise two separate terms for the informativeness and redundancy criteria and formulate an optimization problem to optimize them simultaneously. Solving the optimization problem directly gives us the $B$ image-class pairs that are both informative and non-redundant, in a single step.

Q. The authors employed 1,500 images with pixel-wise annotations to construct the initial training set. Despite the efficiency gains from binary queries in subsequent AL rounds, the annotation cost for the initial training set remains substantial. Moreover, I have reservations about the impact of the initial training set size on AL performance. In other words, if there are fewer pixel-wise annotated samples in the initial training set, will the binary-query-based AL still yield effective results? We agree that this is a very valid concern. We have conducted two experiments on the Cityscapes dataset, where we reduced the size of the initial training set to 300 and 500 images with pixel-level annotations. The results are presented in Figure 11 in Section G of the Appendix. The results depict a very similar trend as Figure 2 in the paper. From the results we note that the mIoU furnished by our binary query based AL method is still very much competitive to the pixel-level and region-level annotation methods, and it outperforms the other binary level annotation methods. Thus, our method is still effective when the size of the initial training set is much smaller.

Q. The authors did not investigate recent advancements in active learning (AL), and the related work section should be updated accordingly. Besides, the authors did not compare with state-of-the-art AL methods. We have updated the related work section to include a few recent references on active learning.

State-of-the-art AL methods require the human annotators to annotate all the pixels in the queried images. Since our annotation mechanism is fundamentally different (binary annotation), we did not perform an exhaustive comparison with state-of-the-art AL techniques. Rather, we selected our comparison baselines to cover a wide variety of annotation strategies: pixel-level annotation, region-level annotation and binary level annotation. Within the first category, we used Coreset (a state-of-the-art AL technique) and Entropy (a widely used AL technique) as our comparison baselines. Since our main contribution is a novel annotation mechanism for AL in image segmentation, we selected the comparison baselines to cover different types of annotation strategies, rather than only the state-of-the-art AL methods, which require pixel-level annotation.

We hope these answer your questions. If you have any additional questions, we will be happy to answer.

Dear Reviewer cBzD,

We wanted to check back with you to see if you got a chance to review our rebuttal and the revised version of the paper, and whether you had any further questions. If not, we would like to request you to kindly consider increasing your score.

Best regards,

• Authors of Paper 752.

Thank you very much for your comments. We have revised the manuscript based on your feedback, and also provide responses here. All the revisions have been marked in red in the manuscript.

General Comments

Q. “to induce a neural network” not sure what this formulation refers to, it is used at multiple places. We have updated this statement and have replaced “induce” with “train”.

Q. “which entails much lesser annotation effort” consider rephrasing We have updated this statement and have replaced “entails” with “requires”.

Q. “furnishing the highest prediction entropy” not sure 'furnishing' is an optimal choice of wording here We have updated this statement and have replaced “furnishing” with “producing”.

Related Work

We have included all the mentioned references in the revised version of the paper. We have removed the statement: "Active learning for image segmentation has been comparatively less explored than other applications."

Implementation Details

Q. Annotation tool used We used the LabelMe annotation tool for the user study. We have mentioned this in Section 4.5 of the revised version of the paper and have also included a reference.

Q. Proficiency of the annotators The annotators did not have any training specifically for the annotation task. This was done to mimic a real-world scenario where the annotators may not have specific knowledge / training about the application in question.

Q. Standard deviation of the values We have included the standard deviation values in Table 1 of the revised version.

Q. How was the train, test, pool split realized? Same strategy for the different datasets? Following the convention in AL research, a given dataset was split at random to generate the training, unlabeled and test sets. We repeated the experiment for three different random splits and averaged the results, to rule out any effects of randomness.

Q. Was there no validation set? We did not use any separate validation set. This is because, the main premise of AL is that we do not have a large amount of labeled data; using a separate validation set (besides the training set) will be contradictory to the conventional AL setup. During training the model, we randomly used 10% of the training set itself as the validation set.

Q. Cityscapes provides 20k weakly annotated frames, given, that the authors propose a AL + weak label scheme, those would be a prime candidate for more exhaustive experiments. We are aware that the Cityscapes dataset provides several frames that are weakly annotated. However, the annotation scheme that we proposed in this paper is binary; that is, annotators are asked whether a particular semantic class is present in a particular image, and they simply have to answer YES / NO. This form of annotation is much weaker than the weakly annotated frames.

Q. How were the parameters for the training of the DNN chosen? We followed the training parameter settings in the following papers in our work:

[1] L. Chen, G. Papandreou, F. Schroff, H. Adam. Rethinking Atrous Convolution for Semantic Image Segmentation. arXiv:1706.05587v3, 2017

[2] B. Kim, H. Choi, H. Jang, S. Kim. Resolution-Aware Design of Atrous Rates for Semantic Segmentation Networks. arXiv:2307.14179, 2023

[3] F. Lin, T. Wu, S. Wu, S. Tian, G. Guo. Feature Selective Transformer for Semantic Image Segmentation. arXiv:2203.14124v3, 2022

Q. Why is the test set rather small? The reported numbers do not seem to match the full size of e.g., Cityscapes, any reason to not using the full dataset for the experiments? No particular reason. We plan to conduct experiments on the full dataset as part of our ongoing research.

Q. How do the results compare to a random baseline? Random sampling was included as a comparison baseline in all our experiments; the method RR denotes the baseline where the images, as well as the semantic classes were selected at random for active query.

Q. How do the results compare to a baseline (same architecture) trained on the full set (train + pool) evaluated on the custom test split? We conducted an experiment to study the performance of our method compared to a fully supervised baseline (trained on the training set + the complete unlabeled pool). The results are presented in Figure 12 and Table 9 in Section H of the Appendix. These results further corroborate the usefulness of our framework in drastically reducing human annotation effort, with a minor loss in performance, for image segmentation applications. Please refer to section H of the Appendix for more details.

We hope these answer your questions. If you have any additional questions, we will be happy to answer.

Dear Reviewer nZpY,

We wanted to check back with you to see if you got a chance to review our rebuttal and the revised version of the paper, and whether you had any further questions. If not, we would like to request you to kindly consider increasing your score.

Best regards,

• Authors of Paper 752.