Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach
Authors: Ahmed Abbas
Paul Swoboda
Venue: NeurIPS 2021 Poster (2021)
Keywords: Combinatorial optimization
Backpropagation
Panoptic segmentation
end-to-end learning
CNNs
Gradient estimation
Fully differentiable

Abstract: We propose a fully differentiable architecture for simultaneous semantic and instance segmentation (a.k.a. panoptic segmentation) consisting of a convolutional neural network and an asymmetric multiway cut problem solver. The latter solves a combinatorial optimization problem that elegantly incorporates semantic and boundary predictions to produce a panoptic labeling. Our formulation allows to directly maximize a smooth surrogate of the panoptic quality metric by backpropagating the gradient through the optimization problem. 
Experimental evaluation shows improvement by backpropagating through the optimization problem w.r.t. comparable approaches on Cityscapes and COCO datasets. Overall, our approach of combinatorial optimization for panoptic segmentation (COPS) shows the utility of using optimization in tandem with deep learning in a challenging large scale real-world problem and showcases benefits and insights into training such an architecture.

Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach
Ahmed Abbas
Paul Swoboda
MPI for Informatics
Saarland Informatics Campus
Abstract
We propose fully differentiable architecture for simultaneous semantic and in- stance segmentation (a.k.a. panoptic segmentation) consisting of convolutional neural network and an asymmetric multiway cut problem solver. The latter solves a combinatorial optimization problem that elegantly incorporates semantic and boundary predictions to produce panoptic labeling. Our formulation allows directly maximize a smooth surrogate of the panoptic quality metric by backprop- agating the gradient through the optimization problem. Experimental evaluation shows improvement by backpropagating through the optimization problem w.r.t. comparable approaches on Cityscapes and COCO datasets. Overall, our approach of combinatorial optimization for panoptic segmentation (COPS) shows the utility of using optimization tandem with deep learning in a challenging large scale real-world problem and showcases benefits and insights into training such an architecture.
Introduction
Panoptic segmentation is the task of simultaneously segmenting different semantic classes and instances of the same class (37). Panoptic segmentation is challenging since neural networks (NN) may produce conflicting predictions (i.e. boundaries separating instances that are not closed contours, instance voting schemes with multiple maxima per instance etc.). Therefore most approaches combine NNs with a post-processing step to compute a final panoptic segmentation that resolves the conflicting evidence produced by NNs. In general, joint training of NNs with pest-processing algorithms is an active research area. In our work we propose fully differentiable approach for panoptic segmentation, our post-processing being combinatorial optimization problem.
In this work we pursue the bottom-up approach building segmentations directly from pixels and combine CNNs with the asymmetric multiway cut problem (AMWC) [42. The latter is an elegant combinatorial optimization problem that combines semantic and affinity predictions and directly produces panoptic labeling. We train CNN and AMWC jointly so that the supervisory signal for training the CNN is influenced by the computations of the combinatorial optimization stage. The loss we propose use for this training differs from common lower-level CNN losses and is smooth surrogate closely corresponding to the final panoptic quality metric [37]. We show in this work how conceptual contributions, i.e. using AMWC panoptic quality loss can be made to work together and yield performance improvements.
differentiable module and training on surrogate
The general idea of combining optimization and neural networks and train them jointly has recently enjoyed resurgent interest. The fundamental problem for the specific task of combinatorial optimiza- tion is that the output of combinatorial problem is 0-1 valued, hence the loss landscape becomes piecewise constant and simply differentiating through a solver is not possible anymore. Several
methods have been proposed to address this problem [0 24 26 work is the first to utilize the perturbation techniques
To our knowledge on large-scale setting with scalable
31 56 64
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

but suboptimal heuristic solvers. We give evidence that training works in this setting and gives perfor- mance benefits. To this end we propose a robust extension of the backpropagation technique [64] that gives better empirical convergence.
Our architecture is inspired by 14 16 and consists of ResNet-50 backbone, a semantic segmen- tation branch for computing class costs and an affinity branch for boundary predictions. Semantic and affinity costs are taken as input by the AMWC solver that returns panoptic labeling. We first pre-train semantic and affinity branches with simple cross-entropy losses obtaining a strong baseline
that achieves performance similar or better than other bottom-up approaches finetune subsequently with the AMWC solver and the panoptic surrogate loss via our new robust backpropagation approach and show further performance improvements.
[16 27 69 We
Current state-of-the-are approaches use very large networks (e.g. Max-Deepl Lab 65 uses transformers containing more parameters than ResNet- 101). This might lead to the impression that advances in panoptic segmentation require deeper and more sophisticated architecture. We show that our simpler model can be significantly improved by a fully differentiable approach and argue that simpler models have not yet reached their full potential. Also, our simpler architecture allows for more controlled setting and makes it easier identify crucial components and measure to which extent performance improvements can be achieved.
Contributions
Optimization for segmentation: We propose AMWC 42 as expressive and tractable combi- natorial optimization formulation to be used in an fully differentiable architecture for panoptic segmentation. We also propose scalable heuristic for its solution.
Panoptic loss surrogate: We propose a surrogate loss function that approximates the panoptic loss metric and can be used in training setup.
Backpropagation: We give an extension of the perturbation technique [64 for backpropagating
gradients through combinatorial solvers, improving training with suboptimal heuristic solvers.
Experimental validation: We conduct experiments on Cityscapes [19] and COCO (47 and show the benefits of fully differentiable training against comparable approaches.
Our code is available at wtthtps://// htat::://github.coo.. wtt.ttb..co/aaaaaaa///////////ee
2
Related Work
2.1 Panoptic segmentation
We categorize panoptic segmentation approaches into three categories: (i) bottom-up methods predict information on the pixel-level and then use post-processing to produce segmentation, (ii) top-down methods proceed by first identifying regions of interest (ROI) and subsequently basing segmentation on them and (iii) hybrid methods combine bottom-up and top-down ideas. For general overview of recent segmentation methods we refer to 51. Here we will restrict to panoptic segmentation tasks.
This principle has also been used with weak supervision 45). As drawback, top-down approaches use ROIs which are mostly axis-aligned and so they can be in-efficient for scenarios containing deformable objects [3]
Top-down: Recent works include 12 36
43
52 58
59
73 75).
Panoptic-Deepe Le 16 based on 74 proposes single-stage neural network architec- ture which combines instance center of mass scores with semantic segmentation to compute panoptic segmentation. They use post-processing similar to Hough-voting (6), obtaining great results and reducing the gap to top-down approaches. Subsequently, xiialDeepLab [66] made improvements using an attention mechanism to enlarge the receptive field using the post-processing scheme of [74].
Bottom-up:
The methods SSAP [27] and SMW [69 are most similar to our as they also use semantic and affinity scores with a graph partitioning algorithm. SMW (69 additionally uses Mask-RCNN [29] and SSAP
solves multiple graph partitioning problems in coarse-to-fine manner. Older works such as [38 48
use graph partitioning schemes but only for the instance segmentation task.
The approaches [46 69 use both bottom-up (affinity scores) and top-down (bounding boxes) sources of information. Conditional convolution 63 was used in 655. Transformers are used in [12] and combined with Max-Deeplaab a sophisticated architecture, achieving remarkable results. They used surrogate for the panoptic quality metric along with an instance discrimination
Hybrid:

---

loss similar to [71. However, Max- Max-DeepLab imposes an upper bound on the maximum number of instances in an image and requires thresholding low confidence predictions.
In summary, bottom-up methods are generally simpler than top-down ones and require fewer hyper- parameters. However, they lack global context and are generally outperformed by top-down ap- proaches. As a solution Axial-DeepLab [66] reduce this gap by incorporating long range context.
Almost all of the above-mentioned approaches use multiple loss functions (see [33 for possible solution), need thresholds for getting rid of low confidence predictions or assume an upper bound on the number of instances and therefore require hyperparameter tuning. To achieve end-to training, approaches of [12 46 65] design mechanisms embedded in the NNs which can compute panoptic segmentations directly but still have test-time hyperparameters (such maximum number of instances, probability thresholding) and need more complicated architectures. Except for the above works, other approaches delegate this task to a post-processing module which does not participate in training. The motivation of our work is based on prioritizing ease-of-use and simplicity. Therefore we have chosen bottom-up approach and propose a fully differentiable method for training with only one loss and no ad-hoc downstream refinements of the segmentation.
2.2 Algorithms as layer in neural networks
Recently there has been great interest in training neural networks with additional layers for problem- specific constraints and prior knowledge. The works [28 provide an extensive survey and insights. An excellent overview of multiple approaches for learning graphical model parameters is given in [25]. The focus of our work is on using an optimization problem as a layer in neural networks. Hence, we will mainly cover approaches for this scenario. They can be categorized follows:
Unrolling: For training NNs together with cheap and differentiable iterative algorithms (or for
algorithms that can be made differentiable e.g. by smoothing). straightforwardly computing gradients the most simple approach. This has been done for K-means (68) bipartite matching (76), conditional
random fields 4 24, 62 (77), non-linear diffusion for image restoration [15] and ranking and
sorting (21). The interesting study [8] shows that under some stability conditions backpropagation through the last few steps of iterative procedures is enough to get good estimates of gradients.
Implicit Function Theorem: In case solutions satisfy fixed point conditions (e.g. KKT conditions)
the implicit function theorem can be used to compute gradients. This was done for quadratic programs in (2). embedding MaxSAT in neural networks [67]. a large class of convex optimization problems [.
smoothed top-k selection via optimal transport 772 and deep equilibrium models [
Problem-speeifie methods: Specialized approaches for backpropagating for specific problems
were investigated for submodularity [3 (c.g. using a graph-cut layer), belief propagation (40).
dynamic programming (50, markov random fields B 39 and nearest neighbor selection 57
Gradient Estimation by Perturbation: Perturbing the objective of an optimization problem for
learning has been proposed in (9, 44 (33 for graphical model parameters. In [10 20 551
perturbation used in the forward pass to get a differentiable estimate of the solution. Perturbing the objective in
the direction of loss decrease has been proposed in [24] for backpropagating through graphical model
inference, in 49 to estimate gradients through a structured loss and in [64] to backpropagate through
combinatorial optimization problems. The latter was used for ranking 60 and graph matching [61]
3 Method
Our architecture shown in Figure 2 is comprised of two stages: (i) a CNN to compute semantic class and affinities for boundary predictions followed by (ii) an AMWC optimization layer producing the final panoptic labeling. We describe below our CNN architecture, the AMWC problem and finally the approach for backpropagting through the AMWC solver to optimize panoptic surrogate loss.
3.1 CNN Architecture
Our CNN architecture (see Figure 2 is comprised of the following parts: a shared ResNet-50 backbone pre-trained on ImageNet 22 producing feature maps for the subsequent semantic and affinity branch. Our CNN architecture corresponds to Panoptic-Deeplab [66 with the exception of modified instance segmentation branch due to different post-proesssing (Hough voting for vs.
3

---

Semuntic iubelt
seg. branch
top-k
Panopiic labels
(a) MWC
Asymmetric multiway cut
Punoptic quality lass
ResNet-50
BCE loss top-k
Decoder
Classifiers
Wellor Edge labels
Affinity
(b) AMWC
Overview of our architecture: Image features computed through ResNet-50 backbone (30] are fed into semantic segmenta- tion branch to predict class scores and to an affinity branch to predict object boundaries. Costs from both branches solver for computing a panoptic labeling. Pre-training of the seman- tic and affinity branch is done with top-k cross-entropy losses (74] (dotted arrows). For backpropagation through AMWC solver we the panoptic quality loss (dashed arrows). The computation flow marked by solid lines is for panoptic segmentation, dotted arrow for pre-training and dashed arrows for fully differentiable training.
Figure 2:
Figure 1: Exemplary MWC and AMWC problems with 4 classes (K" = 4). MWC a special case AMWC when P
used in the AMWC
For P {3) we get an AMWC problem where class 3 is partitioned into subclusters (instances) 3,, 3g and 3c.
AMWC in our work). We also use DeepLabv3+ decoders for both semantic and affinity branch similar to [16]. This allows for fair comparison with [16].
Affinity predictor:
The affinity branch predicts for given pairs of pixels whether they belong to the same instance. It takes two sources of inputs: (i) features from the affinity decoder and (ii) semantic segmentation costs which makes finding boundaries between different classes easier. Gradients of segmentation costs computed from affinity predictors are not backpropagated during training to preclude the affinity branch from influencing the semantic branch.
We take horizontal and vertical edges varying distances d. For COCO use d {1,4, 16, 32, 64) and for Cityscapes d E {1,4, 16, 32, 64, 128). For each d all corresponding edges are sampled and affinity scores are computed by a dedicated predictor for each distance. For long range edges with > we compute edge features by taking the difference of affinity features of the edge endpoints before sending them the predictor. This helps in capturing long-range context. Additional architectural details can be found in the appendix.
3.2 (Asymmetric) Multiway Cut
Multiway cut (MWC) I1] is a combinatorial optimization problem for graph partitioning defined on graph. In MWC pre-defined number of classes is given and each node is assigned one. The cost of a class assignment given by node and edge affinity costs that give the preference of a node belonging to certain class and endpoints of the edge to belong the same class respectively. Hence, the multiway cut can be straightforwardly used to formulate semantic segmentation, each MWC class corresponding to semantic class.
The AMWC problem was introduced in 42 as an extension of MWC. AMWC additionally allows to subdivide some classes into arbitrary number of sub-clusters. This allows to model segmenting a given semantic class into multiple instances for panoptic segmentation.
Mathematically, MWC and AMWC are defined CF + IR and node costs cv V x (1...., , K) + IR, where K the number of classes. The edge affinities eæ indicate preference of edge endpoints to belong to the same cluster, while the node costs ev indicate preference of assigning nodes to classes. A set P C [K] contains classes that can
graph G (V, E) together with edge weights
be partitioned. For MWC we have P while for AMWC P. C []] Let B be the set of valid

---

boundaries, i.e. edge indicator vectors of partitions of V
B (y E (0. 1) ECU.... CMs s.t. y(ii) + #1 and i C.j Cr} (I) where the number of clusters M is arbitrary and Ö is the disjoint union. The MWC and AMWC optimization problems can be written as
min KEBB s.t.
Σiev cv (i, (i,x((i) + EijerCE(1) s(1))
u(ij) = 0. if if x(j) E u(i)) = if # x())
(2)
The above constraints stipulate that y produces valid clustering of the graph compatible with the node labeling x, i.. boundaries implied by y align with class boundaries defined by x and non- partitionable classes not in P do possess internal boundaries. The AMWC can be thought of as special case of InstanceCut 38 that has class-dependent edge affinities, which, however, makes less scalable. Illustrations of MWC and AMWC are given in F
Given a feasible solution (z, y) satisfying the constraints in 2). the panoptic labeling 2 : + {l....,J} J} is computed by connected components w.r.t y, i.c. z(i) 2()) + y(ū 0, Vij E E.
Optimization algorithms for efficiently computing possibly suboptimal solutions for 2 are given in the appendix. Note that, contrary to other approaches for panoptic segmentation such as [63 65 73 AMWC neither has an upper bound on the number of instances M (which is automatically decided by the optimization problem) nor suffers from computational bottlenecks in this regard. It also does not require thresholding get rid of low confidence predictions.
3.3 Fully differentiable training
To train our architecture along with the AMWC solver we first introduce a new robust variant of the perturbation technique for backpropagation [64] which works well for our setting of large-scale problem and suboptimal solver. Second, we introduce a smooth panoptic loss surrogate. Last, we show how backpropagate gradients for the panoptic loss surrogate through a MWC layer.
3.3.1 Robust Perturbation for Backpropagation:
The fundamental difficulty of backpropagating through a combinatorial optimization problem is that the loss landscape is piecewise constant, since the output of the combinatorial problem integer valued. To handle this difficulty, generally applicable perturbation techniques 7 24
31
49 64 have
been proposed. They work by taking finite differences of solutions with perturbations of the original problem. The work (64) interprets this as creating a continuous interpolation of the non-continuous original loss landscape.
The second difficulty is that, due to large size and NP-hardness of AMWC, we use a heuristic suboptimal solver that does not in general deliver optimal solutions. Therefore, we propose multi-scale extension of [64] for increased robustness that works well in our setting.
Assume binary integer linear optimization layer W takes a cost vector network i.e. W: R. >> {0, ]", e - arg min 2) where S C {0, 1]"h the set of constraints. Afterwards the minimizer of W is fed into loss function T. [0,1]" - R. For backpropagation
input from neural
we need to compute the gradient gradient is zero almost everywhere continuous interpolation (L W)) is proposed in (64] where is an interpolation range. The gradient w.r.t. the interpolation computed by perturbation of the cost vector by incoming gradient as follows
(LoW) where L W the composition of and W. Since, this de
Ø W)x
1 [ [[ WCC+WVL(WC)) - w(c) X
(3)
dc
while (64] report that a large interval of interpolation ranges À work well on their test problems with optimal solvers, we have not been able to confirm this for our suboptimal heuristic that only gives approximately good solutions W. Therefore, we propose to use multi-scale loss and its gradient
N
{ o W)avg
N
a(L o W),,
(L o W)aug = N
Σ Lo W)x,
(4)
dc
N
dc
5

---

where X; are sampled uniformly in an interval. While the robust backpropagation formula ④ needs multiple calls to the optimization oracle W. they can be computed in parallel. In practice the computation time for a backward pass will hence not increase.
3.3.2 Panoptic Quality Surrogate Loss:
Panoptic quality (PQ) [37] is a size-invariant evaluation metric defined between set of predicted masks and ground-truth masks for each semantic class / E [K]. For each class, it requires to match predicted and object masks to each other w.r.t intersection-over-uiion (loU) since instance labels are permutation invariant. A pair of predicted and ground truth binary masks and 9 of the same class / is matched (i.c. truc-posii pus-iioie if LoU (p, g) 2 0.5. We write (p. g) E TPp For the unmatched masks, each prediction (ground-trutte is marked as false positive FP (false negative FNN).. Since at most one match exists per ground truth mask, this matching process is well-defined [37. The PQ metric is defined as the mean of class specific PQ scores
EIPYERR (p.(p.)) g) PQ: [TP] + 0.5(IFP: + (FN))
(5)
Note that the PQ score (5) can be arbitrarily low just by the presence small sized false predic- tions [66 58 73 A common practice to avoid such issue is to reject small predictions before computing the PQ score with some dataset specific size thresholds, before evaluation. However, this rejection mechanism is not incorporated during training.
The PQ metric (5) cannot be straightforwardly used for training due to the discontinuity of the hard threshold based matching and the rejection mechanism. Therefore we replace the hard threshold matching process for each class by computing correspondences via a maximum weighted bipartite matching with ToU as weights. The corresponding matches are TPt, the unmatched prediction masks FPt and the unmatched ground truth masks FN,, The hard thresholding smoothed via soft thresholding function h(u)- (1) centered around 0.5. The small prediction rejection mechanism for mask p is smoothed via (p) = [1 + exp(-0.1(1"p 44)) centered area threshold I for class I. The overall surrogate PQ for class / is
o²
E(p.) E1pooeeT,hh(OOO00 ()) 01(p) IoU (oU(p:))
PQ:
66)
Σ (pgg)ETP, (IIoU(p.9) (p) 0.51E,eFF, (t)) + |FN
where the term h(LoU g)) models the probability of a predicted mask p being true positive.
3.3.3 Transformation to Multiway Cut:
In order to directly train with the panoptic loss surrogate 66) via the backpropagation formula (4) propose a transformation of the AMWC problem to a lifted MWC problem the backward pass for computing gradients. The AMWC optimization oracle W can be written as
(x", ",y,,," = arg min x) + (CE, y) 3.y.2
(7)
s.t. 2(1) z(j), if y(j) =0 2(1) * 2(j), y(j) =
(x. y) E S, 2 E Z+
where S describes the constraint listed in ( and the loss is calculated w.r.t panoptic labels 2" i.c. W(cv, cgg) z². To compute the gradients as per (3) we need perturb the cost vector associated with in (7. However, AMWC only takes semantic costs and affinity costs as input not the panoptic costs. In other words, the gradient of (6) affects node costs of individual instances separately (i.e. they work on panoptic labels), but assumss node costs are equal for all instances of one semantic class (i.e. it works on class labels). Therefore we transform the AMWC problem into a lifted MWC problem that has class for each panoptic label in the ground truth. This allows to optimize directly in panoptic label space and compute gradient w.r.t semantic and affinity costs which can then be backpropagated to corresponding branches.
assumes

---

Algorithm 1: BACKWARD PASS
Cv
Input @L. "Øg Cv, CR, solution z; y. m,
AMWC
Loss
2
Output: ăcv dex
OL al
Transform node costs panoptic and perturb:
BL Dey aL Scp
& 8
e (1) (m))) + az (?), vI e [J]
Zp
Multiway cut on panoptic label space:
Grad, comp.
MWC
Pan.
(zp. Up) = MWC(c..ce)
Mp
Perturbed class labels:
(i) (1)x vie V
Figure 3: Gradient computation for cv, cg for fully differentiable learning: AMWC produces semantic, edge, panoptic labels 2, V. resp. Perturbations of panoptic label costs cy are computed and sent the MWC solver together with the original edge costs CÆ- Results are used compute and return the gradients.
Compute node cost gradients: OL
x (Ip - x)
dev
Compute edge cost gradients:
(Up - v)
Beg
return 8L 8L
Dey deg
For the backward pass described in Algorithm | we define the following notation: Let J be the number of classes for the lifted MWC problem and [J] [K] the mapping from panoptic labels onto the corresponding semantic class. Algorithm| computes the gradient w.r.t. the simple backpropagation formula (3) For the robust backprop (4) the algorithm has be called multiple times with the corresponding interpolation ranges X. An illustration of the gradient computation is given in Figure
Line iin Alg. merges two sources of information i.e. preference of the loss L on panoptic labels and current class costs cv. Note that the edge costs cg not perturbed. Afterwards, the perturbed panoptic labels žp are converted back to class labels Tp on line compute the gradients. Ablation study w.r. using simpler losses on the output of AMWC i.e. class labels and edge labels y solver is shown in the appendix. Intuitively. applying a loss directly on edge labels does not work because small and large localization errors in edge labels treated equally. This issue was also observed in for 3D instance segmentation.
Experiments
All baselines are trained on NVIDIA Quadro RTX 8000 GPUs with 48GB memory each. For fully differentiable training we use Tesla P40 with 24GB memory and 32 core CPU to solve all AMWC problems in the batch in parallel.
4.1 Datasets
We train and evaluate COPS on the Cityscapes 19 and COCO [47] panoptic segmentation datasets. We test on the validation and test sets provided by the two datasets. For evaluation on the test set we do not use validation set for training.
Contains traffic related images of resolution 1024 2048 where training, validation and testing splits have 2975, 500, and 1525 images for training, validation, and testing, respectively. It contains 8 'thing' and 11 'stuff" classes. During training we use random scale augmentation and crop to 512 x 1024 resolution as done sent at original resolution. The values of small segment rejection thresholds (used during both training and inference) are 200, 2048 for "thing" and 'stuff' class resp. Lastly, to handle larger occlusions we additionally use affinities at distance of 128.
Cityscapes:
Sanoptic-Deepl.e.
During evaluation the input images are
Is more diverse and contains 1 118k, 5k, and 20k images for training, validation, and testing, resp. The dataset has 'thing' and 53 'stuff" classes. During training random scale augmentation also used with crop size of 640 640 resolution as in [16]. The values of small segment rejection thresholds (used during both training and inference) are 200, 4096 for 'thing and 'stuff'clan resp. During evaluation the input images resized to 640 640 resolution.
COCO:

---

4.2 Training
We closely follow the implementation of Panoptic-DeepLab in 77] (based on Pytorch [54) ). use
the provided ImageNet pre-trained ResNet-50 backbone and the same learning rate parameters for training our baseline model. The Adam optimizer [35] is used for all our experiments.
Resolution:
The CNNs produce an output with 1/ 4-thh the resolution in every dimension w.r.t input images, similar to Panoptic-DeepLaa of upsampled) to reduce computation time during full training and evaluation. The panoptic labels computed by the AMWC solver are upsampled during evaluation. Since these labels are discrete, upsampling may misalign object boundaries and small ground-truth objects can potentially be missed as well. While this can put our method at disadvantage, our full training scheme offsets this by achieving panoptic quality even better than the performance at finest resolution of comparable methods.
This reduced input size is maintained for AMWC (instead
Baseline pre-training: We pre-train the CNN architecture baseline model and for achieving a good initialization for the subsequent fully differentiable training. This also allows us to measure the additional gain by full training. In pre-training we apply the weighted top-k cross-entropy loss [74] to each affinity predictor separately and also to the semantic segmentation branch. Since the main objective of the affinity classifier should be to predict instance boundaries we increase the loss by factor of for edges where at least one endpoint belongs to 'thing" class. Additionally, we also increase the semantic and affinity loss weights of small objects by factor of 3 following [16).
We train Cityscapes on one GPU with batch-size 12 for 250k iterations, with initial learning rate 0.001 and the decay strategies of Panoptic-Deeple Lab. Training takes around 8 days. COCO is trained on four GPUs with a total batch-size of 48 for 240k iterations using the same learning rate parameters as above. Training takes around 11 days.
Full training: For training COPS through AMWC solver we use only the panoptic quality surrogate loss (6) and fine-tune the semantic and affinity classifiers along with the last layer of each semantic and affinity decoder. The ResNet50 backbone and all batch normalization parameters [32] are frozen. We train with batch size of 24 until training loss convergences which amounts to 3000 iterations for Cityscapes and 10000 iterations for COCO. To approximate the gradient (4) we use relatively large values of X compared to [64] since in-exact optimization might not react to small perturbations correctly (for example the backward pass solution might not even be equal to the one from the forward
pass for À + 0). We also observed more stable training curves for larger values of N and use N = in our experiments.
4.3 Results
We compare panoptic quality (in terms of percentage) on both testing Potest and validation PQ splits of Cityscapes and COCO datasets, see Table T For the testing splits evaluation requires submission to an online server. We also show performance on 'thing' classes PQth and stuff classes PQst separately. To allow fair comparison, we restrict ourselves to results of competing approaches which are closest to our setting i.e., without test-time augmentation, similar number of parameters in the network, not utilizing other sources of training data etc. For an overall comparison, we also consider at least one state-of-the-arr work from each other type of method (top-down, hybrid etc.).
First, our fully trained model improves by more than 3 and 4 points in panoptic quality for Cityscapes and COCO resp. in comparison our baseline model. This is evidence our panoptic loss surrogate and training in conjunction with the combinatorial solver works. Especially, performance on the "thing" classes improves which have internal boundaries. We argue this is mainly due better training of the affinity branch, which benefits more from the AMWC supervisory signal. A sample qualitative comparison between baseline and fully trained model can be seen in Figure D where full training shows clear visible improvements. The methods SSAP 27. SMW 69 are closest to ours in-terms of the post-processing, and Panoptic- Deeppaa in-terms of architecture resp. Our fully trained model outperforms SSAP even in a setting where SSAP uses test-time augmentation and a larger backbone. SMW reports results only on Cityscapes using two independent DeepLabb33+ models and a Mask-RCNN. We outperform it with our approach while still using a simpler model. While Panoptic- Deeplab outperforms our baseline model, our full training scheme outperforms on both datasets.
8

---

Table 1: Results on Cityscapes (above) and COCO (below) validation and testing splits. We divide the methods into two groups where lower half for each dataset contains the approaches which are comparable to COPS with bold numbers representing the best performance in this category. R-X: ResNet-X, X-71: Xception-71, t: Mask selection (e.g. by Mask-RCNN), *; Uses test-time augmentation. (-) Marks the results which are not reported for that setting.
Method
Backbone Potest
POlest
PO
Po
Po
PO
Cityscapes
Axial-DL [66
Axial-L
62.7
53.4
69.5
63.9
EfficientPS [2]
Custom
63.9
66.2
60.7
Panoptic-DL. 16
X-71
60.7
63.0
Unify. PS [46
R-50
61.0
52.7
67.1
61.4
54.7
66.3
UPSNet 73
R-50
59.3
54.6
62.7
Panoptic-FPN 136
R-101
58.1
52.0
62.5
SSAP
R-101
58.9
48.4
66.5
61.1
55.0
Panoptic-DI. 16
R-50
58.0
60.3
51.1
66.9
SMW 66
Multiple
59.3
50.6
65.7
Unify. PS [46
R-50
59.0
50.2
65.3
SSAP 27
R-50
56.6
49.2
COPS baseline
R-50
56.7
46.0
64.5
58.5
48.3
66.0
COPS full
R-50
60.0
51.8
65.9
62.1
55.1
67.2
COCO
Max-DeepLab 665
MaX-S
49
54
41.6
Unify. PS [46]
R-50
43.6
48.9
35.6
43.4
48.6
35.5
UPSNet 73
R-50
42.5
48.5
33.4
Axial-DL [66]
Axial-S
42.2
46.5
35.7
41.8
46.1
35.2
Panoptic-FPN [36]]
R-101
40.9
48.3
29.7
40.3
47.5
29.5
Panoptic-DL 16
X-71
38.8
39.7
43.9
33.2
SSAP 27
R-101
36.9
40.1
32
36.5
Panoptic-DI.
16
R-50
35.2
35.5
37.8
32.0
COPS baseline
R-50
34.2
35.2
32.8
34.3
34.9
33.4
COPS full
R-50
38.5
41.0
34.8
38.4
40.5
35.2
N =
N =
PQ PQrain
PQ
PQ
60
75
Panoptic Quality
50
(Q()
70
40
-8--8--8--
48
72
Wall clock time (hours)
Wall clock time (hours)
Figure 4: Comparison of panoptic quality sur- rogate loss Cityscapes for different values of loss interpolation parameter in (4). With N convergence reached faster, even- though we do not parallelize over N.
Figure 5: Train, eval. logs COCO dataset during fully differentiable training. PQ train and PQtrain (5) are computed during training. PQ (5) is reported on the whole COCO vali- dation set after every 1000 iterations.

---

(a) Our baseline: all 3 bicycles not detected, false detections above the right car and near left person.
(b) After full training: better localization and bicycles are correctly detected
Figure 6: Comparison of panoptic labels Cityscapes test set. (Best viewed digitally).
In Figure 4 we plot the PQ surrogate (6) during fully differentiable training using different numbers of interpolation parameter N in 4 Our proposed improvement in the backpropagation scheme of [64] trains faster and achieves better panoptic quality. In Figure(5) we compare our differentiable PQ surrogate (6) with the exact PQ metric 5 during training. Note that PQ surrogate overestimates exact PQ because we smooth hard thresholding operators. Lastly, we see significant improvement in PQ on evaluation set already after only 24 hours of training with batch-size of 24 (baseline training took 1l days with 48 batch-size).
4.4 Limitations
Inference times: Although parallelization can be simply done during training. approach lacks real-time performance during inference requiring around seconds per image from Cityscapes and 0.3 seconds for COCO.
Two stage training: Our training procedure two steps. First pre-train the network using simpler losses and then finetune with panoptic quality surrogate loss by backpropagating through AMWC. We follow this approach due to computational efficiency, since the combinatorial part takes significant amount of time. We hope that with better and faster AMWC solvers training can be converted to single stage in the future. Moreover, we avoid finetuning the whole model with panoptic quality surrogate because IoU based metrics are not separable under expectations w.r.t. different images [ To get good estimates of the loss we therefore require larger batch sizes than for simpler losses used in pre-training. This restriction makes it difficult to train all layers due to GPU memory limitations. would interesting to train all parameters by backpropagation through the combinatorial solver and forego the need for pre-training possibly on applications with simpler losses and fast combinatorial solvers.
5 Conclusion
We have proposed a fully differentiable approach for panoptic segmentation incorporating combina- torial optimization layer for post-prone post-processing and directly minimizing panoptic quality surrogate loss. Our choice has lead simple and elegant formulation with a minimal number of hyperparameters. We argue that learning through combinatorial optimization layers is possible and leads to improved performance even with simple and suboptimal solvers. However, backpropagation schemes should be suitably augmented for robustness in this case.
While our work suggests that combinatorial optimization is helpful in neural networks, most solvers (including the ones we used) are sequential and executed on CPU, which limits their applicability. For combinatorial optimization become more commonly used layer in neural networks, solvers must be designed that are inherently parallel and executable on GPUs.
Broader Impact
This work introduces new fully differentiable architecture for panoptic segmentation, fundamental task computer vision used in down-stream tasks. The broader impact our work depends on the concrete downstream task.
10

---

Acknowledgements
We would like to thank Michal Rolínek for his valuable suggestions regarding backpropagation through optimization problems.
References
[1] Akshay Agrawal, Shane Barratt, and Stephen Boyd. learning convex optimization models, arXiv preprint 04X24 2020.
[2] Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference Muchine Learning, pages 136-145, PMLR, 2017.
[3] Ignacio Arganda-Carreraa Srinivas C. Turaga, Daniel Berger, Dan Cireşan, Alessandro Giusti, Luca M. Gambardella, Jürgen Schmidhuber, Dmitry Laptev, Sarvesh Dwivedi, Joachim M. Buhmann, Ting Liu, Mojtaba Seyedhosseini, Tolga Tasdizen, Lee Kamentsky, Radim Burget, Vaclav Uher, Xiao Tan, Chang- ming Sun, Tuan D. Pham. Erhan Bas, Mustafa G. Uzunbas, Albert Cardona, Johannes Schindelin, and H. Schastian Seung. Crowdsourcing the creation of image segmentation algorithms for connectomics. Frontiers in Neuroanatomy, 9: 142, 2015.
[4] Anurag Arna,, Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes, Mäns Larsson, Alexander Kirillov, Bogdan Savchyaskyy. Carsten Rother, Fredrik Kahl, and Philip HIS Torr. Conditional random fields meet deep neural networks for semantic segmentation: Combining probabilistic graphical models with deep learning for structured prediction. IEEE Signal Processing Magazine, 35(1):37-52, 2018.
[5] Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep equilibrium models. arXiv preprint arXiv: 2019.
[6] Dana H Ballard. Generalizing the hough transform detect arbitrary shapes. Pattern recognition. 1312):11--22, 1981.
[7] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 1.r.ivi1308...... 3432, 2013.
[8] Maxim Berman, Amal Rannen Triki, and Matthew B Blaschko. The lovász softmax loss: A tractable surrogate for the optimization of the intersection-over--ne measure in neural networks. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pages 4413-4421, 2018.
[9] Gedas Bertasius, Qiang Liu, Lorenzo Torresani, and Jianbo Shi. Local porturb-and-man for structured prediction. In Artificial Intelligence and Statistics, pages 585-594, PMLR, 2017.
[10] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vent, and Francis Bach. Learning with differentiable perturbed optimizers. arXiv preprint M.X.iv:0002.0667 2020.
[11] Gruia Calinescu. Multiway Cut, pages 567-569. Springer US, Boston, MA, 2008
[12] Nicolas Carion, Francisco Massa, Gabriel Synnaeve. Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European Conference Computer Vision, pages 213-229. Springer, 2020.
[13] Liang- Chich Chen, Alexander G. Schwing, Alan L. Yuille, and Raquel Urtasun. Leamning deep structured models, 2015.
Liang-Chich
[14] Liang-Chich Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam. Encoder-decoder with atrous separable convolution for semantic image segmentation. In Proceedings of the European conference on computer vision (ECCV), pages 801-818, 2018
[15] Yunjin Chen and Thomas Pock. Trainable nonlinear reaction diffusion: A flexible framework for fast and effective image restoration. IEEE transactions on pattern analysis and machine intelligence, 39(6): 1256- 1272, 2016.
[16] Bowen Cheng, Maxwell Collins, Yukun Zhu, Ting Liu, Thomas S Huang. Hartwig Adam, and Liang- Chich Chen. Panoptic-deeps A simple, strong, and fast baseline for bottom-up panoptic segmentation. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12475
12485, 2020.
11

---

[17] Bowen Cheng, Ross Girshick. Piotr Dollár, Alexander C Berg, and Alexander Kirillov. Boundary iou: Improving object-centric image segmentation evaluation. In Proceedings the IEEE/CVF Conference on Computer Vision and Puttern Recoggition, pages 15334-15342, 2021.
[18] Bruce Christianson, Reverse accumulation and attractive fixed points. Optimization Methods and Software, 1-326,, 1994.
[19] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bertt Schiele. The cityscapes dataset for semantic urban scene understanding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213-3224
2016.
[20] Caio Corro and Ivan Titov, Differentiable perturb-and -nd-parse: Semi-supervised parsing with a structured variational autoencoder. In International Conference on Learning Representations, 2019.
[21] Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. 2019.
[22] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hicrarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. lece, 2009.
[23] Josip Djolonga and Andreas Krause. Differentiable learning of submodular models. Advances in Neural Information Processing Systems, 00:1003-1023, 2017.
[24] Justin Domke. Implicit diffcrentiation by perturbation. Advances in Neural Information Processing Systems, 23:523- 531, 2010.
[25] Justin Domke. Learning graphical model parameters with approximate marginal inference. IEEE transac- tions on patiern analysis and machine intelligence, 35(10):2454 2467,
[26] Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1504-1511, 2020.
[27] Naiyu Gao, Yanhu Shan, Yupei Wang, Xin Zhao, Yinan Yu, Ming Yang. and Kaiqi Huang. Ssap: Single-shot instance segmentation with affinity pyramid. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 642-651, 2019.
[28] Stephen Gould, Richard Hartley, and Dylan Campbell, Deep declarative networks: A new hope. arXiv preprint arXiv: 049664 2019.
[29] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE international conference computer vision, pages 2961 121122999,200 2017.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[31] Hedda Cohen Indelman and Tamir Hazan. Learning randomly perturbed structured predictors for direct loss minimization. arXiv preprint arXiv:2007.0572 2020.
[32] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference machine learning, pages 448 456. PMLR, 2015.
[33] Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty weigh losses for scene geometry and semanties, In Proceedings of the IEEE conference on computer vision and pattern recogmition, pages 7482-7491, 2018
[34] Margret Keuper, Evgeny Levinkov, Nicolas Bonneel, Guillaume Lavoué, Thomas Brox, and Bjorn Andres. Efficient decomposition of image and mesh graphs by lifted multicuts. In Proceedings of the IEFF International Conference on Computer Vision, pages 175 1-55-1 2015.
[35] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
[36] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Dollár. Panoptic feature pyramid networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2019.
12

---

[37] Alexander Kirillov, Kaiming He, Ross Girshick. Carsten Rother, and Piotr Dollár. Panoptic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9404-9413, 2019.
[38] Alexander Kirillov, Evgeny Levinkov, Bjoem Andres, Bogdan Savchynskyy, and Carsten Rother. Instance- cut: from edges to instances with multicut. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5008-5017, 2017.
[39] Alexander Kirillov, Dmitrij Schlesinger, Shuai Zheng, Bogdan Savchynskyy, Philip H. S. Torr, and Carsten Rother. Joint training of generic enn-crf models with stochastic optimization, 2016.
[40] Patrick Knobelreiter, Christian Sormann, Alexander Shekhovtsov, Friedrich Fraundorfer, and Thomas Pock. Belief propagation reloaded: Learning bp-layers for labeling problems. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 7900-7909, 2020.
[41] James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck. and Bryan Wilder. End-to-end constrained optimization learning: survey. arXiv preprint arXiv:2103.16376. 2021.
[42] Thorben Kroeger, Jörg H Kappes, Thorsten Beier, Ullrich Koethe, and Fred Hamprecht. Asymmetric cuts: Joint image labeling and partitioning. In German Conference on Pattern Recognition, pages 199-211. Springer, 2014.
[43] Jie Li, Allan Raventos, Arjun Bhargava, Takaaki Tagawa, and Adrien Gaidon. Learning to fuse things and stuff. arXiv preprint 18/2.0//9 2018.
[44] Ke Li, Kevin Swersky, and Richard Zemel. Efficient feature learning using perturb-and-map. 2013.
[45] Qizhu Li, Anurag Amab, and Philip HS Torr. Weakly-and semi suni-supee panoptic segmentation. In Proceedings of the European conference on computer vision (ECCV), pages 102- 102-118, 2018
[46] Qizhu Li, Xiaojuan Qi. and Philip HS Torr Unifying training and inference for panoptic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13320- 13328, 2020.
[47] 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 European conference on computer vision, pages 740-755. Springer, 2G014.
[48] Yiding Liu, Siyu Yang, Bin Li, Wengang Zhou, Jizheng Xu, Houqiang Li, and Yan Lu. Affinity derivation and graph merge for instance segmentation. In Proceedings of the European Conference on Computer Vision (ECCV), pages 286-703, 2018.
[49] David A McAllester, Tamir Hazan, and Joseph Keshet. Direct loss minimization for structured prediction. In NIPS, volume 1, page 3. Citeseer, 2010.
[50] Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In International Conference Machine Learning, pages 3462-34624 3471. PMLR, 2018.
[51] Shervin Minace, Yuri Y Boykov, Fatih Porikli, Antonio J Plaza, Nasser Kehtamnvaz, and Demetri Terzopoulos. Image segmentation using deep learning: A survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[52] Rohit Mohan and Abhinav Valada. Efficientps: Efficient panoptic segmentation. International Journal of Computer Vision, pages 1-29, 2021.
[53] George Papandreou and Alan L Yuille. Perturb-and-may random fields: Using discrete optimization to learn and sample from energy models. In 2 International Conference on Computer Vision, pages 193-200. IEEE, 2011.
[54] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan. Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjic Bai, and Soumith Chintala. Pytorch: An imperative style, high- tigg--erformacc deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8035. Curran Associates, Inc., 2019.
[55] Max B Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris J Maddison. Gradient estimation with stochastic softmax tricks. arXiv preprint arXiv:2006. 08063, 2020.
13

---

[56] Hao Peng. Sam Thomson, and Noah A Smith. Backpropagating through structured argmax using spigot. arXiv preprint urXiv:1805.04656 2018.
[57] Tobias Plötz and Stefan Roth. Neural nearest neighbors networks. Advances in Neural Information Processing Systems, 1089000-1 2018.
[58] Lorenzo Porzi, Samuel Rota Bulo, Aleksander Colovic, and Peter Kontschieder. Seamless seene segmenta- tion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8277-8288 2277-886, 2019.
[59] Siyuan Qiao, Liang-Chich Chich Chen, and Alan Yuille. Detectors: Detecting objects with recursive feature pyramid and switchable atrous convolution. arXiv preprint arXiv:2006. 02334, 2020.
[60] Michal Rolinek. Vit Musil, Anselm Paulus, Marin Vlastelica, Claudio Michaelis. and Georg Martius. Optimizing aunk-based metrics with blackbox differeatiation. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages 7620-7630, 2020.
[61] Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius. Deep graph matching via blackbox diffcrentiation of combinatorial solvers. In European Conference on Computer Vision, pages 407 424. Springer, 2020.
[62] Song, Bjoern Andres, Michael Black. Oumar Hilliges, and Siyu Tang. End-to-end learning for graph decomposition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10093-10102, 2019.
[63] Zhi Tian, Chunhua Shen, and Hao Chen. Conditional convolutions for instance segmentation. arXiv preprint arXiv:003300566,, 2020.
[64] Marin Vlastelica, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
[65] Huiyu Wang, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang- Chen. Max-deeplab; End-to-end panoptic segmentation with mask transformers. arXiv preprint arXiv:2012.00759, 2020.
[66] Huiyu Wang, Yukun Zhu, Bradley Green, Hartwig Adam, Alan Yuille, and Liang Chich Chen. Axial- deeplab: Stand- -itentnttnttion for panoptic segmentation. In European Conference Computer Vision, pages 108-126. Springer, 2020.
[67] Po- Rei Wang. Priya Donti, Bryan Wilder. and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, pages 6545 6554, PMLR, 2019.
[68] Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. End to end learning and optimization on graphs. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[69] Steffen Wolf, Yuyan Li, Constantin Pape, Alberto Bailoni, Anna Kreshuk, and Fred A Hamprecht. The semantic mutex watershed for efficient bottom-up semantic instance segmentation. In European Conference on Computer Vision, pages 208- 224. Springer, 2020.
[70] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick. Detectron2. https //github. h//.thub.ccm//acceccccceeoeo hwtp:////w..ooooeeeeerreeetttto. 2019.
[71] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3733-3742, 2018
[72] Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiahle top-k operator with optimal transport. arXiv preprint arXiv:2002.06550 06504, 2020.
[73] Yuwen Xiong, Renjie Liao, Hengshuang Zhao, Rui Hu, Min Bai, Ersin Yumer, and Raquel Urtasun. Upsnet: A unified panoptic segmentation network. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8818-881888 2019.
[74] Tien-Ju Yang, Maxwell D Collins, Yukun Zhu. Jyh-Jing Hwang. Ting Liu, Xiao Zhang, Vivienne Sze, George Papandreou. and Liang-Chiel Chen. Deeperlab: Single-shot image parser. arXiv preprint 190.:1992.05093 2019.
14

---

[75] Yibo Yang. Hongyang Li, Xia Li, Qijie Zhao, Jianlong Wu, and Zhouchen Lin. Sognet: Scene overlap graph network for panoptic segmentation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 12637-12644, 2020.
[76] Xiaohui Zeng. Renjie Liao, Li Gu, Yuwen Xiong, Sanja Fidler. and Raquel Urtasun. Dmm-net: Dif- ferentiable mask matching network for video object segmentation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3929-39229 2019.
[77] Shuai Zheng. Sadeep Jayasumana, Bemaardino Romera-Paredes, Vibhav Vineet, Zhizhong Su, Dalong Chang Huang, and Philip HS Torr Conditional random fields as recurrent neural networks. Proceedings of the IEEE international conference on computer vision, pages 1529-1537, 2015.
15


Reviews:
[{"review_id": "lWQEHgzpaKw", "reviewer": "Reviewer_aCGb", "summary": "This paper proposed a new architecture for panoptic segmentation consisting of a convolutional neural network and an asymmetric multiway cut problem solver.\nTheir formulation allows to directly maximize a smooth surrogate of the panoptic quality metric by backpropagating the gradient through the optimization problem.", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-- Overclaim. The paper claims the proposed method is 'An End-to-End Trainable Approach', however, it requires a pre-training for semantic and affinity branches, which is followed by fine-tuning the overall model.\n\n-- Performance. The proposed approach is complex and does not achieve the state-of-the-art results.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-- It is unclear what is the advantages of the proposed method.\n-- There is not ablation study of the new modules.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "eZuju4R_I7c", "reviewer": "Reviewer_G2zw", "summary": "This paper formulates panoptic segmentation as a combinatorial optimization problem that uses an asymmetric multiway cut problem (AMWC) solver. The authors propose a bottom-up approach that builds segmentations by combining CNNs and AMWC which is inspired by the idea of combing optimization and neural network. The model is trained with surrogate loss that optimizes directly the final panoptic quality metric, making the model end-to-end trainable.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper brings up an interesting idea of formulating panoptic segmentation as multiway cut problem and embed the optimization problem into the network and results show the effectiveness of the model. I only have a few concerns/questions to the authors:\n\n1. According to L318-320, the AMWC solver requires 2 seconds per image, making the proposed method not very practically useful. This is probably the biggest limitation of the proposed approach (other models with extremely large backbone probably don't need 2 seconds to process an image). What is the benefit of using AMWC compared to existing methods like [13]? Is there anything AMWC can achieve but [13] cannot achieve? I suggest the author to make a more detailed error mode analysis between their methods and [13].\n\n2. Boundary quality issue. From visualization in Figure 5, the boundary quality is not very good. I understand this is due to the nearest neighbor upsampling on discrete grid. Is it possible to solve AMWC after upsampling the intermediate features (like semantic segmentation and affinity prediction)? I don't see any discussion on the mask quality other than L273. PQ improvement comes from both recognition (RQ) and segmentation (SQ) qualities and according to Figure 5 the proposed method mainly improves recognition quality? I suggest also do a thorough analysis of mask quality with [13] as the mask predictions in [13] seems to be smoother. Recently, Boundary PQ is proposed in [A] to measure the boundary quality which could be a useful metric. I think it would be good to point out the possible limitation by comparing Boundary PQ.\n\n3. According to 4.2, the end-to-end training is actually finetuning from some pre-trained weights. Is it possible to remove the necessity of this two-stage training?\n\n[A] Cheng, Bowen, et al. \"Boundary IoU: Improving Object-Centric Image Segmentation Evaluation.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "dLyT-Sc-A7K", "reviewer": "Reviewer_UruC", "summary": "This paper proposes a new model architecture for panoptic segmentation which is end-to-end trainable and requires less hyperparameters than existing methods. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes a new model architecture for panoptic segmentation.  The proposed architecture produces semantic segmentations and edge affinity scores from every pixel to its neighboring pixels. The edge affinities help determine whether two pixels belong to the same instance. The segmentations along with the edges allow us to view the image as a graph (V, E) where the vertices are pixel with weighted edge connections to neighboring pixels. The authors then formulate panoptic segmentation as a graph cutting problem. \nTo solve the graph cutting problem, the authors use an algorithm called asymmetric multi-way cut (AMWC). The authors use work from [1] to backpropagate through the AMWC layer, and thus making their architecture end-to-end trainable. \nFinally, the authors propose a new differentiable loss function based on the panoptic quality metric.\n\nOverall, the paper is well written and the authors do a good job discussing the limitations and benefits of their work. \n\nMajor Cons (please address this in your rebuttal):\nThe authors did not include any code with their submission, they claim they will release their code upon acceptance. \n\n1) In figure 2 what exactly is the decoder in the affinity branch? This is neither explained in the main body of the paper nor the appendix. \n\n2) What happens when applying work in [1] directly without the averaging trick used in section 3.3.? Also when averaging what values of lambda are considered? I see you mention N=5 on line 293 but it would be nice to have a more in-depth study of this averaging somewhere, since you claim it's one of the major contributions of the paper. \n\n3) The training routine is not well explained. Are you freezing the ResNet params or are they also trained? Does the end-to-end training happen after the baseline pre-training or are those two separate things? I think the answer is they're not separate but it was slightly unclear to me. \n\n-----------------\nMinor Cons (do not address in rebuttal):\n1) The function total_edge_similarity(ij) on line 25 of algo 2 in the appendix is a little hard to find. Maybe move it to a separate \"algo\" or move it up to line 3 of algo 2 (before it is first used). \n2) Fix sentence on line 222: \"also allows one to also \"\n\n---------------\n\n[1] Marin Vlastelica Poganciˇ c, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors clearly show the results of their method and the compute time necessary to train and run inference. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "TNqU77CpBRO", "reviewer": "Reviewer_8yaS", "summary": "This paper introduces to use combinatorial optimization method to solve the panoptic segmentation problem. The perturbation technique is used for training with the Asymmetric Multiway Cut (AMWC) solver. Furthermore, a surrogate panoptic loss is introduced and works together with the proposed framework. Experiments are performed on public COCO and Cityscapes panoptic segmentation datasets.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1. Given the challenge of panoptic segmentation, using the combinatorial optimization method for the panoptic segmentation is novel, although this kind of method has been explored earlier in Instance Segmentation.\n\n2. The proposed panoptic loss is meaningful since it optimizes the model directly towards the evaluation metric.\n\nCons:\n\n1. The presentation of this paper is poor. Readers may have a hard time following the proposed method.\n\n    a. The meaning of the symbols is not clearly explained and confusing. For instance, there are no explanations of $l$, $i$, $j$, $C$ in Equation (1), $x$ in Equation (2), $L$ in Line-173 (while in Line-193, $L$ is used again for representing a loss function). Readers would have to guess the meaning of the symbols or refer to the referenced papers so as to understand the equations. The statements \"$\\mathcal{X}$ is some constraint set\", \"$\\lambda$ are sampled uniformly on some interval. \" are vague and unclear. \n    \n    Besides, in Line-219 to Line 220, the funtions $h(u) = \\frac{u^4}{u^4 + (1 - u)^4}$ and function $\\sigma_l(p) = [1 + e^{-0.1(1^{T}p - t_l)}]^{-1}$ seem to be very ad-hoc. How are they derived?\n\n    b. Section 2.2 only categorized a few related works. How does this work connect with each category of the mentioned works? \n\n    c. It is said in the paper: \"We cross-validate our method on the validation split and evaluate the same model on the testing split\". However, in Table 1, validation results are also used to compare with other methods, which may cause confusion. \n\n2. The claims of this paper are not well supported in the experiments. There are nearly no detailed ablations over each part of the proposed method. It is hard to tell why the proposed method works since there are only comparisons with other methods and the baseline. For instance, does the proposed Combinatorial Optimization solver need to be tightly coupled with the panoptic surrogate loss? If not, how does it perform compared with baseline when training without the panoptic surrogate loss? How would it perform when using the panoptic surrogate loss on Panoptic-Deeplab? \n\nFurthermore, the paper claims it is an end-to-end training approach. However, from my point of view, it is not end-to-end, but using stage-wise training. It needs to pretrain the baseline and then fix the network to train the solver.\n\n3. Besides, I have further questions about some unclear details:\n\n    a. In Figure 4, it only shows the comparison based on $\\bar{PQ}$ rather than $PQ$, why? Would $\\bar{PQ}$ perfectly track the $PQ$ evaluation? \n\n    b. Why only train 4000 iterations on COCO in the so-called \"end-to-end training\" phase? It seems too short (less than 1 epoch). Would more training lead to worse results?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed to some extent, such as the inference time of the proposed method. The method requires heavy hyper-parameter tuning from my view, which could also be a limitation. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "HEgPZixbUP2", "reviewer": "Reviewer_upv8", "summary": "This paper proposes an approximated (smoothed) end-to-end training method for panoptic segmentation with combinatorial optimization. Panoptic segmentation is obtained by AMWC, and the gradients are estimated with robust perturbation. Positive experimental results are achieved on two panoptic segmentation datasets, compared with the baselines.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality\nTo the best of my knowledge, the proposed AMWC approach for panoptic segmentation is original and novel.\n\n## Strength\n1. The neural network architecture is simple, with a semantic head and an intuitive affinity head.\n2. Overall presentation and experiment settings are clear, although a few details and ablation experiments are in the appendix.\n3. Optimizing directly on panoptic quality does not seem to overfit PQ. The method works well on other metrics (mask AP, mIoU).\n4. The experiments show a comfortable margin on top of the baselines. And the control experiments are fair. \n\n## Weakness\n1. The inference speed is bottlenecked by AMWC solver, limiting the application of the proposed method in real world. The authors claim the training time AMWC/MWC is computed in parallel, but it is not clear how much more time is spent on them.\n2. The proposed method may be limited to hard assignment problems only. It may not generalize to more flexible cases such as COCO instance segmentation with potentially overlapping output masks.\n3. Baselines are relatively weak, with resent-50 and panoptic-deeplab. It is not clear if the end-to-end training still leads to a good margin on top of other strong methods, e.g. max-deeplab.\n4. Two stage training is required, possibly because of the slow AMWC/MWC CPU solver which limits the scaling to more GPUs training in parallel.\n5. Training time approximated PQ might still be very different from real PQ probably because of the different matching strategies (bipartite vs. IoU thresholding). This might make the validation PQ a less good indicator of the real PQ.\n\n———————————————— Post Rebuttal ——————————————\n\nI thank the authors for the responses. The rebuttal partially resolves my concern (weakness 5, and part of weakness 1). The authors and most of the reviewers seem to agree on other limitations (e.g. the limited efficiency and thus the two-stage training problem). I think these limitations are acceptable at the first attempt, so I will raise my rating to 7 (accept).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work introduces a fully differentiable method for training a model for panoptic image segmentation. This method consists of two parts: (1) constructing and training an approximate proxy metric for PQ (panoptic quality), (2) posing the problem in terms of affinity prediction between adjacent pixels and subsequently using an asymmetric multiway cut solver (AMWC) to arrive at differentiable prediction of panoptic segmentation. The model is trained in 2 stages: first the model is pre-trained using the proxy metric, second the model is fine-tuned using the AMWC solver. The quality of the model is subsequently evaluated on COCO and Cityscapes datasets and compares favorably to several baselines.

Although there was some notable spread across the reviews, in general the reviewers commented positively on the novelty of the proposed combinatorial optimization and panoptic proxy loss. Although the inference speed of the optimization method is quite slow, the method does replace lots of hand-crafted heuristics. Otherwise, the reviewers did raise significant concerns about the presentation quality of the paper, the need for providing additional ablations, and questions about the comparison to baselines. In my read of the paper I was surprised how unfavorably the proposed method performs with respect to some of the reported baselines (e.g. Table 1, Axial-DL [60] 42.2 vs. 36.6); likewise, I saw instances of heuristics that made me question whether hand-crafted heuristics were removed (e.g. line 256). Finally, I was additionally concerned whether the paper was fully self-contained as important ablations are contained within the Appendix. All of these issues appear substantial and raise the general concern that the amount of updates necessary for acceptance would be quite significant and require further review.

One item of note that the reviewers highlighted was the claim that the model was "end-to-end trained" and whether this claim matches the fact that the model requires a pre-training step followed by fine tuning. The necessity of the two-stage training procedure is due to the slow inference time of the proposed AMWC solver, and thus fundamental to the proposed method. Although there is some slight confusion in the literature about the strictness of using the term "end-to-end training", I do concur with the reviewers that the term "end-to-end" is intended to imply that a single optimization/training stage is sufficient for training. Furthermore, after having consulted with multiple colleagues, I believe that this is the general sentiment of the larger deep learning community. I would suggest that the authors employ their suggestion of "fully differentiable" in subsequent revisions as many reviewers would find the current title inappropriate for describing the methodology.

In summary, the work offers a promising idea that presents a novel method for training a model to perform panoptic segmentation. That said, the reviewers still offer several strong concerns about the presentation and the baselines that require substantial revisions by the authors. In sum, this work is borderline, and given that there is no strong champion for this work to be accepted, this paper will not be accepted at NeurIPS. I strongly suggest that the authors heavily revise their manuscript and resubmit to the next available conference, potentially with a computer vision focus.

Decision: Accept (Poster)