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": "pWYpGXKCjrm", "reviewer": "Reviewer_5rdz", "summary": "This paper focuses on the problem of panoptic segmentation. The author proposes an end-to-end trainable approach with a combinatorial optimization layer for post-processing. AMWC formulation and surrogate loss are utilized for panoptic segmentation. The experimental evaluations are conducted on both Cityscapes and COCO datasets, and the results seem promising.", "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": "Strengths:\n1. Use of an AMWC solver to address the problem of panoptic segmentation seems interesting.\n\nWeaknesses:\n1. Some of the experimental comparisons are missing. For example, what would the results be when given different backbones, as shown in Table 1?\n2. The results on the Cityscapes dataset seem good when compared to other methods. While on the COCO dataset, the results are much worse, e.g., when compared to the UPSNet. What would be the possible reason for that? Would the method not work well for complex scenes like COCO?\n3. The introduced computations, parameters, and the running time of the proposed module are not discussed in the manuscript.\n4. It is suggested to rerank the order of different approaches in Table 1 by their performance.\n5. Typos: 'CityScapes' should be 'Cityscapes'; two dots at line 97, etc. The paper needs more proofreading.", "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"}, "extra_text": {}}, {"review_id": "OhE_mw4Pip", "reviewer": "Reviewer_XpFH", "summary": "The paper designs an end-to-end panoptic segmentation pipeline with combinatorial optimization. The authors propose to use asymmetric multiway-cut to make the panoptic segmentation prediction, with a Panoptic Quality surrogate loss as a direct supervision signal and a perturbation-based gradient estimation technique to enable training.", "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": "---\n\n[+] The paper is well-written and easy to follow.\n\n[+] The idea in the paper sounds novel. The idea is followed by a simple and elegant panoptic segmentation pipeline. The proposed key algorithm, AMWC, greatly simplifies the panoptic prediction.\n\n[+] The paper contributes several techniques to implement the AMWC algorithm for large-scale training, including a surrogate loss and a multi-scale back-propagation technique. Particularly, the surrogate loss mitigates the existing gap between supervision signals and the evaluation metric.\n\n[+] The proposed solution outperforms SOTA, e.g., Panotptic-Deeplab and SSAP, in segmentation quality.\n\n--- \n\n[-] The perturbation-based gradient estimation might limit the scalability of the method. The gradient estimation might get inaccurate when we have more parameters to optimize, for example, when we optimize the whole model instead of only the classification layer as in the paper.\n\n[-] The solver (2 seconds per Cityscape image) is too slow for real-time applications.\n\n[-] Compared to the baseline, the PQ_stuff even dropped on COCO after fine-tuning. It would be better if the drop could be explained.\n\n[-] The experiment part is a little weak. It would be better if more ablation studies and analysis, e.g., on different backbones and training time memory consumption, can be provided.\n\n---\n\nIn summary, the main idea of the paper about using a combinatorial optimizer to simplify the notoriously complicated panoptic prediction task is interesting and novel. However, I have concerns about the scalability and the real-world impact of the method since the solver is currently too slow and a sophisticated optimization method has to be employed in training.\n\n---\n\nTypos:\n\nL97: \"architectures..\" -> \"architectures.\"\n\nFig 2. caption: \"to a affinity branch\" -> \"to an affinity branch\"\n\nL169: \"The AMWC can be though of as a\" -> \"The AMWC can be thought of as a\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HkUSMeCn5vj", "reviewer": "Reviewer_Zjn9", "summary": "The submission proposes a module for discrete labeling within panoptic segmentation models that can still be optimized end-to-end. The panoptic labels are discrete labels giving the class and instance of each pixel in the image. This paper considers labels produced by the asymmetric multiway cut problem (AMWC) [36] and uses a perturbation-based method for determining the gradients of this module. They can then be back-propagated into a neural network model that produces the potentials in the AMWC problem.", "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**\n\nCombining graphical models, including discrete optimization, with deep learning has a long history with deep learning for vision & segmentation:\n\n  * Chen et. al. \"Learning Deep Structured Models\" ICML 2015\n  * Kirillov et. al. \"Efficient Likelihood Learning of a Generic CNN-CRF Model for Semantic Segmentation\" ICLR 2016\n\nAnd the submission includes good discussion of the most closely related literature, citing [2, 62, 71] among others. Directly considering the discrete optimization problem as in the submission, rather than a continous model or a continuous relaxation, is a less common choice.\n\nIt's easy to anticipate this being applied to panoptic segmentation too. I am not aware of previous work taking this kind of approach for this particular segmentation subproblem.\n\nHow the models are combined, and the gradients calculated, is nontrivial, especially when the discrete problem is hard as in this case. Some complex and interesting design decisions made are here.\n\n**Quality**\n\n[36] is a very good choice of which discrete problem to use. It can explicitly handle instances for a subset of classes in a way that directly maps to the panoptic segmentation problem.\n\nA multi-way cut optimization is a very principled way to handle the discreteness of the panoptic labels. The original work proposing the panoptic segmentation problem [32] used discrete labels and a quality measure (PQ) that more or less assumes this (using their definition of IoU).\n\nThe core novel part of the method, the robust perturbation technique and how it's applied, all looks correct to me.\n\nThe experiments are simple but straightforward. The submission does not introduce much in the way of additional confounds or hyperparameters that need to be tuned, so the comparisons seem good. Experiments are done with multiple trials, and the source of the values of the hyperparameters that are present is specified.\n\nOne set of experiments, that I did not find but would ideally be present, are any showing the quality of the AMWC solutions or the gradients. Section A.1 in the supplementary material describes a heuristic greedy solver to the AMWC problem. How does this perform in practice in terms of the how close to optimal its solutions are, and how consistently? How much more accurate (by whatever measure) are the gradients for the robust perturbation than [52]? This or other questions, that directly measure how the discrete optimization step is performing, would provide some insight beyond the end-to-end PQ results.\n\n**Clarity**\n\nThe submission is very clear. The presentation style is simple and direct. Pseudocode and mathematical definitions are use well for more precise description of the optimization method.\n\n**Significance**\n\nThe overall method gets a lower score on panoptic quality (PQ) than the state-of-the art, but it does convincingly improved upon a bottom-up baseline. So it seems very likely that this kind of approach, at least generally considering discrete optimization within the training and inference, is a significant step forward in panoptic segmentation and image segmentation in general.\n\n**Minor Comments**\n\n* Double-checking: does the loss function L, specified in 193, take real-valued or binary labels as input?\n* Typo \"Trail\" in Table 5 in the supplement.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation of the core novel component of this method are probably primarily that the solutions to the asymmetric cut problem, and the gradients, not being computed exactly. The submission is clear that it is using approximations here, and discusses how they dealt with the drawbacks of their choice of approximation.\n\nSocietal impact is going to depend on application, as the authors state.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns directly arise from this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "0XDDo6cYYgg", "reviewer": "Reviewer_vDMJ", "summary": "This paper proposes an end-to-end trainable approach for panoptic segmentation incorporating a combinatorial optimization layer for post-processing and directly learning a panoptic surrogate loss. It solves the panoptic segmentation based on the bottom-up manner and views the instance separation as a multiway cut problem. Experiments prove the effectiveness.", "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 an end-to-end trainable approach for panoptic segmentation incorporating a combinatorial optimization layer for post-processing and directly learning a panoptic surrogate loss. It solves the panoptic segmentation based on the bottom-up manner and views the instance separation as a multiway cut problem. Overall, the method is elegant and experiments prove its effectiveness. Some detailed concerns are given below:\n\nSome concerns:\n1. This paper uses a pre-trained model as baseline and optimizes it with the proposed panoptic quality loss. I'm wondering if it is possible to optimize them simultaneously in an iterative manner? Because the pretrained manner actually brings more cost to the whole process and may lead to a suboptimal solution.\n2. The universality of the proposed method. Could the proposed loss function be viewed as a plug-and-play module in other methods for panoptic or instance segmentation? It could bring more technical value.\n3. The performance on the COCO dataset is not satisfactory. The suboptimal performance on the COCO dataset could be attributed to the complex scenarios compared with the Cityscapes dataset, especially in Thing categories. Is this brought by the drop in SQ or RQ? A detailed analysis is recommended to be given in the main paper or appendix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and potential negative societal impact are discussed and addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a method for simultaneous semantic and instance segmentation which can be optimized end-to-end. In particular, the authors make use of predictions obtained by solving the asymmetric multiway-cut problem, coupled with a surrogate loss whose gradient is estimated using a perturbation-based approach. Promising empirical results were presented on COCO and CityScapes datasets.
Reviewers appreciated the clarity of exposition and felt that the proposed approach was a rather elegant solution, notwithstanding the fact that the empirical results were not state-of-the-art. The rebuttals did a great job addressing most concerns, but scalability and practicality remain one of the key drawbacks. Nevertheless, the reviewers felt that the contribution is significant enough to merit acceptance. I agree and I would like to see the authors include a detailed limitations section to highlight the remaining issues.
Decision: Accept (Poster)