# Simple Copy-Paste is a Strong Data Augmentation Method
for Instance Segmentation

Golnaz Ghiasi 1 Yin Cui11footnotemark: 1 1 Aravind Srinivas11footnotemark: 1
1,2
Rui Qian22footnotemark: 2 1,3 Tsung-Yi Lin1 Ekin D. Cubuk1 Quoc V. Le1 Barret
Zoph1

1Google Research Equal contribution. Correspondence to:
<EMAIL_ADDRESS>done during an internship at Google Research. Brain
Team 2 UC Berkeley 3 Cornell University

###### Abstract

Building instance segmentation models that are data-efficient and can handle
rare object categories is an important challenge in computer vision.
Leveraging data augmentations is a promising direction towards addressing this
challenge. Here, we perform a systematic study of the Copy-Paste augmentation
(, [13, 12]) for instance segmentation where we randomly paste objects onto an
image. Prior studies on Copy-Paste relied on modeling the surrounding visual
context for pasting the objects. However, we find that the simple mechanism of
pasting objects randomly is good enough and can provide solid gains on top of
strong baselines. Furthermore, we show Copy-Paste is additive with semi-
supervised methods that leverage extra data through pseudo labeling (self-
training). On COCO instance segmentation, we achieve 49.1 mask AP and 57.3 box
AP, an improvement of +0.6 mask AP and +1.5 box AP over the previous state-of-
the-art. We further demonstrate that Copy-Paste can lead to significant
improvements on the LVIS benchmark. Our baseline model outperforms the LVIS
2020 Challenge winning entry by +3.6 mask AP on rare categories.

##  1 Introduction

Figure 1: Data-efficiency on the COCO benchmark: Combining the Copy-Paste
augmentation along with Strong Aug. (large scale jittering) allows us to train
models that are up to 2$\times$ more data-efficient than Standard Aug.
(standard scale jittering). The augmentations are highly effective and provide
gains of +10 AP in the low data regime (10% of data) while still being
effective in the high data regime with a gain of +5 AP. Results are for Mask
R-CNN EfficientNet-B7 FPN trained on an image size of 640$\times$640\.

Instance segmentation [22, 10] is an important task in computer vision with
many real world applications. Instance segmentation models based on state-of-
the-art convolutional networks [11, 56, 66] are often data-hungry. At the same
time, annotating large datasets for instance segmentation [40, 21] is usually
expensive and time-consuming. For example, 22 worker hours were spent per 1000
instance masks for COCO [40]. It is therefore imperative to develop new
methods to improve the data-efficiency of state-of-the-art instance
segmentation models.

Figure 2: We use a simple copy and paste method to create new images for
training instance segmentation models. We apply random scale jittering on two
random training images and then randomly select a subset of instances from one
image to paste onto the other image.

Here, we focus on data augmentation [49] as a simple way to significantly
improve the data-efficiency of instance segmentation models. Although many
augmentation methods such as scale jittering and random resizing have been
widely used [26, 25, 20], they are more general-purpose in nature and have not
been designed specifically for instance segmentation. An augmentation
procedure that is more _object-aware_ , both in terms of category and shape,
is likely to be useful for instance segmentation. The Copy-Paste augmentation
[13, 12, 15] is well suited for this need. By pasting diverse objects of
various scales to new background images, Copy-Paste has the potential to
create challenging and novel training data for free.

The key idea behind the Copy-Paste augmentation is to paste objects from one
image to another image. This can lead to a combinatorial number of new
training data, with multiple possibilities for: (1) choices of the pair of
source image from which instances are copied, and the target image on which
they are pasted; (2) choices of object instances to copy from the source
image; (3) choices of where to paste the copied instances on the target image.
The large variety of options when utilizing this data augmentation method
allows for lots of exploration on how to use the technique most effectively.
Prior work [12, 15] adopts methods for deciding where to paste the additional
objects by modeling the surrounding visual context. In contrast, we find that
a simple strategy of randomly picking objects and pasting them at random
locations on the target image provides a significant boost on top of baselines
across multiple settings. Specifically, it gives solid improvements across a
wide range of settings with variability in backbone architecture, extent of
scale jittering, training schedule and image size.

In combination with large scale jittering, we show that the Copy-Paste
augmentation results in significant gains in the data-efficiency on COCO
(Figure 1). In particular, we see a data-efficiency improvement of 2$\times$
over the commonly used standard scale jittering data augmentation. We also
observe a gain of +10 Box AP on the low-data regime when using only 10% of the
COCO training data.

We then show that the Copy-Paste augmentation strategy provides additional
gains with self-training [44, 72] wherein we extract instances from ground-
truth data and paste them onto unlabeled data annotated with pseudo-labels.
Using an EfficientNet-B7 [55] backbone and NAS-FPN [17] architecture, we
achieve 57.3 Box AP and 49.1 Mask AP on COCO test-dev without test-time
augmentations. This result surpasses the previous state-of-the-art instance
segmentation models such as SpineNet [11] (46.3 mask AP) and DetectoRS
ResNeXt-101-64x4d with test time augmentation [43] (48.5 mask AP). The
performance also surpasses state-of-the-art bounding box detection results of
EfficientDet-D7x-1536 [56] (55.1 box AP) and YOLOv4-P7-1536 [60] (55.8 box AP)
despite using a smaller image size of 1280 instead of 1536.

Finally, we show that the Copy-Paste augmentation results in better features
for the two-stage training procedure typically used in the LVIS benchmark
[21]. Using Copy-Paste we get improvements of 6.1 and 3.7 mask AP on the rare
and common categories, respectively.

The Copy-Paste augmentation strategy is easy to plug into any instance
segmentation codebase, can utilize unlabeled images effectively and does not
create training or inference overheads. For example, our experiments with
Mask-RCNN show that we can drop Copy-Paste into its training, and without any
changes, the results can be easily improved, , by +1.0 AP for 48 epochs.

##  2 Related Work

#### Data Augmentations.

Compared to the volume of work on backbone architectures [35, 50, 52, 27, 55]
and detection/segmentation frameworks [19, 18, 46, 38, 26, 39], relatively
less attention is paid to data augmentations [49] in the computer vision
community. Data augmentations such as random crop [36, 35, 50, 52], color
jittering [52], Auto/RandAugment [6, 7] have played a big role in achieving
state-of-the-art results on image classification [27, 55], self-supervised
learning [28, 24, 5] and semi-supervised learning [63] on the ImageNet [47]
benchmark. These augmentations are more general purpose in nature and are
mainly used for encoding invariances to data transformations, a principle well
suited for image classification [47].

#### Mixing Image Augmentations.

In contrast to augmentations that encode invariances to data transformations,
there exists a class of augmentations that mix the information contained in
different images with appropriate changes to groundtruth labels. A classic
example is the mixup data augmentation [65] method which creates new data
points for free from convex combinations of the input pixels and the output
labels. There have been adaptations of mixup such as CutMix [64] that pastes
rectangular crops of an image instead of mixing all pixels. There have also
been applications of mixup and CutMix to object detection [68]. The Mosaic
data augmentation method employed in YOLO-v4 [1] is related to CutMix in the
sense that one creates a new compound image that is a rectangular grid of
multiple individual images along with their ground truths. While mixup, CutMix
and Mosaic are useful in combining multiple images or their cropped versions
to create new training data, they are still not object-aware and have not been
designed specifically for the task of instance segmentation.

#### Copy-Paste Augmentation.

A simple way to combine information from multiple images in an object-aware
manner is to copy instances of objects from one image and paste them onto
another image. Copy-Paste is akin to mixup and CutMix but only copying the
exact pixels corresponding to an object as opposed to all pixels in the
object’s bounding box. One key difference in our work compared to Contextual
Copy-Paste [12] and InstaBoost [15] is that we do not need to model
surrounding visual context to place the copied object instances. A simple
random placement strategy works well and yields solid improvements on strong
baseline models. Instaboost [15] differs from prior work on Copy-Paste [12] by
not pasting instances from other images but rather by jiterring instances that
already exist on the image. Cut-Paste-and-Learn [13] proposes to extract
object instances, blend and paste them on diverse backgrounds and train on the
augmented images in addition to the original dataset. Our work uses the same
method with some differences: (1) We do not use geometric transformations
(rotation), and find Gaussian blurring of the pasted instances not beneficial;
(2) We study Copy-Paste in the context of pasting objects contained in one
image into another image already populated with instances where [13] studies
Copy-Paste in the context of having a bank of object instances and background
scenes to improve performance; (3) We study the efficacy of Copy-Paste in the
semi-supervised learning setting by using it in conjunction with self-
training. (4) We benchmark and thoroughly study Copy-Paste on the widely used
COCO and LVIS datasets while Cut-Paste-and-Learn uses the GMU dataset [16]. A
key contribution is that our paper shows the use of Copy-Paste in improving
state-of-the-art instance segmentation models on COCO and LVIS.

#### Instance Segmentation.

Instance segmentation [22, 23] is a challenging computer vision problem that
attempts to both detect object instances and segment the pixels corresponding
to each instance. Mask-RCNN [26] is a widely used framework with most state-
of-the-art methods [66, 11, 43] adopting that approach. The COCO dataset is
the widely used benchmark for measuring progress. We report state-of-the-
art111Based on the entries in https://paperswithcode.com/sota/instance-
segmentation-on-coco. results on the COCO benchmark surpassing SpineNet [11]
by 2.8 AP and DetectoRS [43] by 0.6 AP.222We note that better mask / box AP on
COCO have been reported in COCO competitions in 2019 -
https://cocodataset.org/workshop/coco-mapillary-iccv-2019.html.

#### Long-Tail Visual Recognition.

Recently, the computer vision community has begun to focus on the long-tail
nature of object categories present in natural images [58, 21], where many of
the different object categories have very few labeled images. Modern
approaches for addressing long-tail data when training deep networks can be
mainly divided into two groups: data re-sampling [41, 21, 61] and loss re-
weighting [30, 8, 3, 53, 37, 45]. Other more complicated learning methods (,
meta-learning [62, 29, 32], causal inference [57], Bayesian methods [34], )
are also used to deal with long-tail data. Recent work [9, 3, 33, 70, 37] has
pointed out the effectiveness of two-stage training strategies by separating
the feature learning and the re-balancing stage, as end-to-end training with
re-balancing strategies could be detrimental to feature learning. A more
comprehensive summary of data imbalance in object detection can be found in
Oksuz et al. [42]. Our work demonstrates simple Copy-Paste data augmentation
yields significant gains in both single-stage and two-stage training on the
LVIS benchmark, especially for rare object categories.

(a) Standard Scale Jittering (SSJ) (b) Large Scale Jittering (LSJ)

Figure 3: Notation and visualization of the two scale jittering augmentation
methods used throughout the paper. Standard Scale Jittering (SSJ) resizes and
crops an image with a resize range of 0.8 to 1.25 of the original image size.
The resize range in Large Scale Jittering (LSJ) is from 0.1 to 2.0 of the
original image size. If images are made smaller than their original size, then
the images are padded with gray pixel values. Both scale jittering methods
also use horizontal flips.

##  3 Method

Our approach for generating new data using Copy-Paste is very simple. We
randomly select two images and apply random scale jittering and random
horizontal flipping on each of them. Then we select a random subset of objects
from one of the images and paste them onto the other image. Lastly, we adjust
the ground-truth annotations accordingly: we remove fully occluded objects and
update the masks and bounding boxes of partially occluded objects.

Unlike [15, 12], we do not model the surrounding context and, as a result,
generated images can look very different from real images in terms of co-
occurrences of objects or related scales of objects. For example, giraffes and
soccer players with very different scales can appear next to each other (see
Figure 2).

#### Blending Pasted Objects.

For composing new objects into an image, we compute the binary mask ($\alpha$)
of pasted objects using ground-truth annotations and compute the new image as
$I_{1}\times\alpha+I_{2}\times(1-\alpha)$ where $I_{1}$ is the pasted image
and $I_{2}$ is the main image. To smooth out the edges of the pasted objects
we apply a Gaussian filter to $\alpha$ similar to “blending” in [13]. But
unlike [13], we also found that simply composing without any blending has
similar performance.

#### Large Scale Jittering.

We use two different types of augmentation methods in conjunction with Copy-
Paste throughout the text: standard scale jittering (SSJ) and large scale
jittering (LSJ). These methods randomly resize and crop images. See Figure 3
for a graphical illustration of the two methods. In our experiments we observe
that the large scale jittering yields significant performance improvements
over the standard scale jittering used in most prior works.

#### Self-training Copy-Paste.

In addition to studying Copy-Paste on supervised data, we also experiment with
it as a way of incorporating additional unlabeled images. Our self-training
Copy-Paste procedure is as follows: (1) train a supervised model with Copy-
Paste augmentation on labeled data, (2) generate pseudo labels on unlabeled
data, (3) paste ground-truth instances into pseudo labeled and supervised
labeled images and train a model on this new data.

##  4 Experiments

###  4.1 Experimental Settings

#### Architecture.

We use Mask R-CNN [26] with EfficientNet [55] or ResNet [27] as the backbone
architecture. We also employ feature pyramid networks [38] for multi-scale
feature fusion. We use pyramid levels from $P_{2}$ to $P_{6}$, with an anchor
size of $8\times 2^{l}$ and 3 anchors per pixel. Our strongest model uses
Cascade R-CNN [2], EfficientNet-B7 as the backbone and NAS-FPN [17] as the
feature pyramid with levels from $P_{3}$ to $P_{7}$. The anchor size is
$4\times 2^{l}$ and we have 9 anchors per pixel. Our NAS-FPN model uses 5
repeats and we replace convolution layers with ResNet bottleneck blocks [27].

#### Training Parameters.

All models are trained using synchronous batch normalization [31, 20] using a
batch size of 256 and weight decay of 4e-5. We use a learning rate of 0.32 and
a step learning rate decay [25]. At the beginning of training the learning
rate is linearly increased over the first 1000 steps from 0.0032 to 0.32. We
decay the learning rate at 0.9, 0.95 and 0.975 fractions of the total number
of training steps. We initialize the backbone of our largest model from an
ImageNet checkpoint pre-trained with self-training [63] to speed up the
training. All other results are from models with random initialization unless
otherwise stated. Also, we use large scale jittering augmentation for training
the models unless otherwise stated. For all different augmentations and
dataset sizes in our experiments we allow each model to train until it
converges (, the validation set performance no longer improves). For example,
training a model from scratch with large scale jittering and Copy-Paste
augmentation requires 576 epochs while training with only standard scale
jittering takes 96 epochs. For the self-training experiments we double the
batch size to 512 while we keep all the other hyper-parameters the same with
the exception of our largest model where we retain the batch size of 256 due
to memory constraints.

#### Dataset.

We use the COCO dataset [40] which has 118k training images. For self-training
experiments, we use the unlabeled COCO dataset (120k images) and the
Objects365 dataset [48] (610k images) as unlabeled images. For transfer
learning experiments, we pre-train our models on the COCO dataset and then
fine-tune on the Pascal VOC dataset [14]. For semantic segmentation, we train
our models on the train set (1.5k images) of the PASCAL VOC 2012 segmentation
dataset. For detection, we train on the trainval set of PASCAL VOC 2007 and
PASCAL VOC 2012. We also benchmark Copy-Paste on the LVIS v1.0 (100k training
images) and report results on LVIS v1.0 val (20k images). LVIS has 1203
classes to simulate the long-tail distribution of classes in natural images.

Figure 4: Copy-Paste provides gains that are robust to training
configurations. We train Mask R-CNN (ResNet-50 FPN) on 1024$\times$1024 image
size for varying numbers of epochs. Left Figure: Copy-Paste with and without
initializing the backbone. Right Figure: Copy-Paste with standard and large
scale jittering. Across all of the configurations training with Copy-Paste is
helpful.

###  4.2 Copy-Paste is robust to training configurations

In this section we show that Copy-Paste is a strong data augmentation method
that is robust across a variety of training iterations, models and training
hyperparameters.

#### Robustness to backbone initialization.

Common practice for training Mask R-CNN is to initialize the backbone with an
ImageNet pre-trained checkpoint. However He et al. [25] and Zoph et al. [72]
show that a model trained from random initialization has similar or better
performance with longer training. Training models from ImageNet pre-training
with strong data-augmentation (RandAugment [7]) was shown to hurt the
performance by up to 1 AP on COCO. Figure 4 (left) demonstrates that Copy-
Paste is additive in both setups and we get the best result using Copy-Paste
augmentation and random initialization.

#### Robustness to training schedules.

A typical training schedule for Mask R-CNN in the literature is only 24
(2$\times$) or 36 epochs (3$\times$) [25, 26, 15]. However, recent work with
state-of-the-art results show that longer training is helpful in training
object detection models on COCO [72, 56, 11]. Figure 4 shows that we get gains
from Copy-Paste for the typical training schedule of 2$\times$ or 3$\times$
and as we increase training epochs the gain increases. This shows that Copy-
Paste is a very practical data augmentation since we do not need a longer
training schedule to see the benefit.

#### Copy-Paste is additive to large scale jittering augmentation.

Random scale jittering is a powerful data augmentation that has been used
widely in training computer vision models. The standard range of scale
jittering in the literature is 0.8 to 1.25 [39, 25, 6, 15]. However,
augmenting data with larger scale jittering with a range of 0.1 to 2.0 [56,
11] and longer training significantly improves performance (see Figure 4,
right plot). Figure 5 demonstrates that Copy-Paste is additive to both
standard and large scale jittering augmentation and we get a higher boost on
top of standard scale jittering. On the other hand, as it is shown in Figure
5, mixup [65, 68] data augmentation does not help when it is used with large
scale jittering.

#### Copy-Paste works across backbone architectures and image sizes.

Finally, we demonstrate Copy-Paste helps models with standard backbone
architectures of ResNet-50 and ResNet-101 [27] as well the more recent
architecture of EfficientNet-B7 [55]. We train models with these backbones on
the image size of 640$\times$640, 1024$\times$1024 or 1280$\times$1280\. Table
1 shows that we get significant improvements over the strong baselines trained
with large scale jittering for all the models. Across 6 models with different
backbones and images sizes Copy-Paste gives on average a 1.3 box AP and 0.8
mask AP improvement on top of large scale jittering.

Figure 5: Copy-Paste is additive to large scale jittering augmentation. Improvement from mixup and Copy-Paste data augmentation on top of standard scale jittering (Left Figure) and large scale jittering (Right Figure). All results are from training Mask R-CNN EfficientNetB7-FPN on the image size of 640$\times$640. Model | FLOPs | Box AP | Mask AP
---|---|---|---
Res50-FPN (1024) | 431 B | 47.2 | 41.8
w/ Copy-Paste | 431 B |  (+1.0) 48.2 |  (+0.6) 42.4
Res101-FPN (1024) | 509 B | 48.4 | 42.8
w/ Copy-Paste | 509 B |  (+1.4) 49.8 |  (+0.8) 43.6
Res101-FPN (1280) | 595 B | 49.1 | 43.1
w/ Copy-Paste | 595 B |  (+1.2) 50.3 |  (+1.1) 44.2
Eff-B7 FPN (640) | 286 B | 48.5 | 42.7
w/ Copy-Paste | 286 B |  (+1.5) 50.0 |  (+1.0) 43.7
Eff-B7 FPN (1024) | 447 B | 50.8 | 44.7
w/ Copy-Paste | 447 B |  (+1.1) 51.9 |  (+0.5) 45.2
Eff-B7 FPN (1280) | 595 B | 51.1 | 44.8
w/ Copy-Paste | 595 B |  (+1.5) 52.6 |  (+1.1) 45.9
Table 1: Copy-paste works well across a variety of different model architectures, model sizes and image resolutions. Setup | Box AP | Mask AP
---|---|---
Eff-B7 FPN (640) | 48.5 | 42.7
w/ self-training |  (+1.5) 50.0 |  (+1.3) 44.0
w/ Copy-Paste |  (+1.5) 50.0 |  (+1.0) 43.7
w/ self-training Copy-Paste |  (+2.9) 51.4 |  (+2.3) 45.0
Table 2: Copy-Paste and self-training are additive for utilizing extra
unlabeled data. We get significant improvement of 2.9 box AP and 2.3 mask AP
by combining self-training and Copy-Paste.

###  4.3 Copy-Paste helps data-efficiency

In this section, we show Copy-Paste is helpful across a variety of dataset
sizes and helps data efficiency. Figure 5 reveals that Copy-Paste augmentation
is always helpful across all fractions of COCO. Copy-Paste is most helpful in
the low data regime (10% of COCO) yielding a 6.9 box AP improvement on top of
SSJ and a 4.8 box AP improvement on top of LSJ. On the other hand, mixup is
only helpful in low data regime. Copy-Paste also greatly helps with data-
efficiency: a model trained on $75\%$ of COCO with Copy-Paste and LSJ has
similar AP to a model trained on $100\%$ of COCO with LSJ.

###  4.4 Copy-Paste and self-training are additive

In this section, we demonstrate that a standard self-training method similar
to [63, 72] and Copy-Paste can be combined together to leverage unlabeled
data. Copy-Paste and self-training individually have similar gains of 1.5 box
AP over the baseline with 48.5 Box AP (see Table 2).

To combine self-training and Copy-Paste we first use a supervised teacher
model trained with Copy-Paste to generate pseudo labels on unlabeled data.
Next we take ground truth objects from COCO and paste them into pseudo labeled
images and COCO images. Finally, we train the student model on all these
images. With this setup we achieve 51.4 box AP, an improvement of 2.9 AP over
the baseline.

#### Data to Paste on.

In our self-training setup, half of the batch is from supervised COCO data
(120k images) and the other half is from pseudo labeled data (110k images from
unlabeled COCO and 610k from Objects365). Table 3 presents results when we
paste COCO instances on different portions of the training images. Pasting
into pseudo labeled data yields larger improvements compared to pasting into
COCO. Since the number of images in the pseudo labeled set is larger, using
images with more variety as background helps Copy-Paste. We get the maximum
gain over self-training (+1.4 box AP and +1.0 mask AP) when we paste COCO
instances on both COCO and pseudo labeled images.

#### Data to Copy from.

We also explore an alternative way to use Copy-Paste to incorporate extra data
by pasting pseudo labeled objects from an unlabeled dataset directly into the
COCO labeled dataset. Unfortunately, this setup shows no additional AP
improvements compared with pasting COCO ground-truth objects.

Setup |  Pasting into | Box AP | Mask AP
---|---|---|---
self-training |  - | 50.0 | 44.0
+Copy-Paste |  COCO |  (+0.4) 50.4 | 44.0
+Copy-Paste |  Pseudo data |  (+0.8) 50.8 |  (+0.5) 44.5
+Copy-Paste |  COCO &
Pseudo data |  (+1.4) 51.4 |  (+1.0) 45.0
Table 3: Pasting ground-truth COCO objects into both COCO and pseudo labeled data gives higher gain in comparison to doing either on its own. Model | FLOPs | # Params | AP${}_{\text{val}}$ | AP${}_{\text{test-dev}}$ | Mask AP${}_{\text{val}}$ | Mask AP${}_{\text{test-dev}}$
---|---|---|---|---|---|---
SpineNet-190 (1536) [11] | 2076B | 176.2M | 52.2 | 52.5 | 46.1 | 46.3
DetectoRS ResNeXt-101-64x4d [43] | — | — | — |  55.7† | — |  48.5 †
SpineNet-190 (1280) [11] | 1885B | 164M | 52.6 | 52.8 | — | —
SpineNet-190 (1280) w/ self-training [71] | 1885B | 164M | 54.2 | 54.3 | — | —
EfficientDet-D7x (1536) [56] | 410B | 77M | 54.4 | 55.1 | — | —
YOLOv4-P7 (1536) [60] | — | — | — |  55.8† | — | —
Cascade Eff-B7 NAS-FPN (1280) | 1440B | 185M | 54.5 | 54.8 | 46.8 | 46.9
w/ Copy-Paste | 1440B | 185M |  (+1.4) 55.9 |  (+1.2) 56.0 |  (+0.4) 47.2 |  (+0.5) 47.4
w/ self-training Copy-Paste | 1440B | 185M |  (+2.5) 57.0 |  (+2.5) 57.3 |  (+2.1) 48.9 |  (+2.2) 49.1
Table 4: Comparison with the state-of-the-art models on COCO object detection
and instance segmentation. Parentheses next to the model name denote the input
image size. † indicates results are with test time augmentation.

###  4.5 Copy-Paste improves COCO state-of-the-art

Next we study if Copy-Paste can improve state-of-the-art instance segmentation
methods on COCO. Table 4 shows the results of applying Copy-Paste on top of a
strong 54.8 box AP COCO model. This table is meant to serve as a reference for
state-of-the-art performance.333https://paperswithcode.com/sota/object-
detection-on-coco For rigorous comparisons, we note that models need to be
evaluated with the same codebase, training data, and training settings such as
learning rate schedule, weight decay, data pre-processing and augmentations,
controlling for parameters and FLOPs, architectural regularization [59],
training and inference speeds, The goal of the table is to show the benefits
of the Copy-Paste augmentation and its additive gains with self-training. Our
baseline model is a Cascade Mask-RCNN with EfficientNet-B7 backbone and NAS-
FPN. We observe an improvement of +1.2 box AP and +0.5 mask AP using Copy-
Paste. When combined with self-training using unlabeled COCO and unlabeled
Objects365 [48] for pseudo-labeling, we see a further improvement of 2.5 box
AP and 2.2 mask AP, resulting in a model with a strong performance of 57.3 box
AP and 49.1 mask AP on COCO test-dev without test-time augmentations and model
ensembling.

Model | AP50
---|---
RefineDet512+ [67] | 83.8
SNIPER [51] | 86.9
Cascade Eff-B7 NAS-FPN | 88.4
w/ Copy-Paste pre-training |  (+0.7) 89.1
Table 5: PASCAL VOC 2007 detection result on test set. We present results of
our EfficientNet-B7 NAS-FPN model pre-trained with and without Copy-Paste on
COCO.

###  4.6 Copy-Paste produces better representations for PASCAL detection and
segmentation

Previously we have demonstrated the improved performance that the simple Copy-
Paste augmentation provides on instance segmentation. In this section we study
the transfer learning performance of the pre-trained instance segmentation
models that were trained with Copy-Paste on COCO. Here we perform transfer
learning experiments on the PASCAL VOC 2007 dataset. Table 5 shows how the
learned Copy-Paste models transfer compared to baseline models on PASCAL
detection. Table 6 shows the transfer learning results on PASCAL semantic
segmentation as well. On both PASCAL detection and PASCAL semantic
segmentation we find our models trained with Copy-Paste transfer better for
fine-tuning than the baseline models.

Model | mIOU
---|---
DeepLabv3+ † [4] | 84.6
ExFuse † [69] | 85.8
Eff-B7 [72] | 85.2
Eff-L2 [72] | 88.7
Eff-B7 NAS-FPN | 83.9
w/ Copy-Paste pre-training |  (+2.7) 86.6
Table 6: PASCAL VOC 2012 semantic segmentation results on val set. We present results of our EfficientNet-B7 NAS-FPN model pre-trained with and without Copy-Paste on COCO. † indicates multi-scale/flip ensembling inference.  | Mask AP |  Mask AP${}_{\text{r}}$ |  Mask AP${}_{\text{c}}$ |  Mask AP${}_{\text{f}}$ | Box AP
---|---|---|---|---|---
cRT (ResNeXt-101-32$\times$8d) [33] | 27.2 | 19.6 | 26.0 | 31.9 | —
LVIS Challenge Winner† [54] | 38.8 | 28.5 | 39.5 | 42.7 | 41.1
ResNet50-FPN (1024) | 30.3 | 22.2 | 29.5 | 34.7 | 31.5
w/ Copy-Paste |  (+2.0) 32.3 |  (+4.3) 26.5 |  (+2.3) 31.8 |  (+0.6) 35.3 |  (+2.8) 34.3
ResNet101-FPN (1024) | 31.9 | 24.7 | 30.5 | 36.3 | 33.3
w/ Copy-Paste |  (+2.1) 34.0 |  (+2.7) 27.4 |  (+3.4) 33.9 |  (+0.9) 37.2 |  (+3.1) 36.4
Eff-B7 FPN (1024) | 33.7 | 26.4 | 33.1 | 37.6 | 35.5
w/ Copy-Paste |  (+2.3) 36.0 |  (+3.3) 29.7 |  (+2.7) 35.8 |  (+1.3) 38.9 |  (+3.7) 39.2
Eff-B7 NAS-FPN (1280) | 34.7 | 26.0 | 33.4 | 39.8 | 37.2
w/ Copy-Paste |  (+3.4) 38.1 |  (+6.1) 32.1 |  (+3.7) 37.1 |  (+2.1) 41.9 |  (+4.4) 41.6
Table 7: Comparison with the state-of-the-art models on LVIS v1.0 object
detection and instance segmentation. Parentheses next to our models denote the
input image size. † We report the 2020 winning entry’s results without test-
time augmentations.

###  4.7 Copy-Paste provides strong gains on LVIS

We benchmark Copy-Paste on the LVIS dataset to see how it performs on a
dataset with a long-tail distribution of 1203 classes. There are two different
training paradigms typically used for the LVIS benchmark: (1) single-stage
where a detector is trained directly on the LVIS dataset, (2) two-stage where
the model from the first stage is fine-tuned with class re-balancing losses to
help handle the class imbalance.

#### Copy-Paste improves single-stage LVIS training.

The single-stage training paradigm is quite similar to our Copy-Paste setup on
COCO. In addition to the standard training setup certain methods are used to
handle the class imblance problem on LVIS. One common method is Repeat Factor
Sampling (RFS) from [21], with $t=0.001$. This method aims at helping the
large class imbalance problem on LVIS by over-sampling images that contain
rare classes. Table 8 shows the results of applying Copy-Paste on a strong
single-stage LVIS baseline. We use EfficientNet-B7 FPN with 640$\times$640
input size, and train the model from scratch with random initialization for
180k steps using 256 batch size. As suggested by [21], we increase the number
of detections per image to 300 and reduce the score threshold to 0. We observe
that Copy-Paste augmentation outperforms RFS on AP, AP${}_{\text{c}}$ and
AP${}_{\text{f}}$, but under-performs on AP${}_{\text{r}}$ (the AP for rare
classes). The best overall result comes from combining RFS and Copy-Paste
augmentation, achieving a boost of +2.4 AP and +8.7 AP${}_{\text{r}}$.

Setup (single-stage) | AP |  AP${}_{\text{r}}$ |  AP${}_{\text{c}}$ |  AP${}_{\text{f}}$
---|---|---|---|---
Eff-B7 FPN (640) | 27.7 | 9.7 | 28.1 | 35.1
w/ RFS | 28.2 | 15.4 | 27.8 | 34.3
w/ Copy-Paste | 29.3 | 12.8 | 30.1 | 35.7
w/ RFS w/ Copy-Paste | 30.1 | 18.4 | 30.0 | 35.4
Table 8: Single-stage training results (mask AP) on LVIS.

#### Copy-Paste improves two-stage LVIS training.

Two-stage training is widely adopted to address data imbalance and obtain good
performance on LVIS [37, 45, 54]. We aim to study the efficacy of Copy-Paste
in this two-stage setup. Our two-stage training is as follows: first we train
the object detector with standard training techniques (, same as our single-
stage training) and then we fine-tune the model trained in the first stage
using the Class-Balanced Loss [8]. The weight for a class is calculated by
$(1-\beta)/(1-\beta^{n})$, where $n$ is the number of instances of the class
and $\beta=0.999$.444We scale class weights by dividing the mean and then clip
their values to $[0.01,5]$, as suggested by [37]. During the second stage
fine-tuning, we train the model with 3$\times$ schedule and only update the
final classification layer in Mask R-CNN using the classification loss. From
mask AP results in Table 9, we can see models trained with Copy-Paste learn
better features for low-shot classes (+2.3 on AP${}_{\text{r}}$ and +2.6 on
AP${}_{\text{c}}$). Interestingly, we find RFS, which is quite helpful and
additive with Copy-Paste in single-stage training, hurts the performance in
two-stage training. A possible explanation for this finding is that features
learned with RFS are worse than those learned with the original LVIS dataset.
We leave a more detailed investigation of the tradeoffs between RFS and data
augmentations in two stage training for future work.

Setup (two-stage) | AP |  AP${}_{\text{r}}$ |  AP${}_{\text{c}}$ |  AP${}_{\text{f}}$
---|---|---|---|---
Eff-B7 FPN (640) | 31.3 | 25.0 | 30.6 | 34.9
w/ RFS | 30.1 | 21.8 | 29.7 | 34.1
w/ Copy-Paste | 33.0 | 27.3 | 33.2 | 35.7
w/ RFS w/ Copy-Paste | 32.0 | 26.3 | 31.8 | 34.7
Table 9: Two-stage training results (mask AP) on LVIS.

#### Comparison with the state-of-the-art.

Furthermore, we compare our two-stage models with state-of-the-art methods for
LVIS555https://www.lvisdataset.org/challenge_2020 in Table 7. Surprisingly,
our smallest model, ResNet50-FPN, trained with Copy-Paste outperforms a strong
baseline cRT [33] with ResNeXt-101-32$\times$8d backbone.

EfficientNetB7 NAS-FPN model (without Cascade 666We find using Cascade in our
experiments improves AP${}_{\text{f}}$ but hurts AP${}_{\text{r}}$.) trained
with Copy-Paste has comparable results to LVIS challenge 2020 winner on
overall Mask AP and Box AP without test-time augmentations. Also, it achieves
32.1 mask AP${}_{\text{r}}$ for rare categories outperforming the LVIS
Challenge winning entry by +3.6 mask AP${}_{\text{r}}$.

##  5 Conclusion

Data augmentation is at the heart of many vision systems. In this paper, we
rigorously studied the Copy-Paste data augmentation method, and found that it
is very effective and robust. Copy-Paste performs well across multiple
experimental settings and provides significant improvements on top of strong
baselines, both on the COCO and LVIS instance segmentation benchmarks.

The Copy-Paste augmentation strategy is simple, easy to plug into any instance
segmentation codebase, and does not increase the training cost or inference
time. We also showed that Copy-Paste is useful for incorporating extra
unlabeled images during training and is additive on top of successful self-
training techniques. We hope that the convincing empirical evidence of its
benefits make Copy-Paste augmentation a standard augmentation procedure when
training instance segmentation models.

## References

  * [1] Alexey Bochkovskiy, Chien-Yao Wang, and Hong-Yuan Mark Liao.  Yolov4: Optimal speed and accuracy of object detection.  arXiv preprint arXiv:2004.10934, 2020.
  * [2] Zhaowei Cai and Nuno Vasconcelos.  Cascade r-cnn: Delving into high quality object detection.  In CVPR, 2018.
  * [3] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma.  Learning imbalanced datasets with label-distribution-aware margin loss.  In NeurIPS, 2019.
  * [4] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In ECCV, 2018.
  * [5] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In ICML, 2020.
  * [6] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le.  Autoaugment: Learning augmentation policies from data.  In CVPR, 2019.
  * [7] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In NeurIPS, 2020.
  * [8] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie.  Class-balanced loss based on effective number of samples.  In CVPR, 2019.
  * [9] Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge Belongie.  Large scale fine-grained categorization and domain-specific transfer learning.  In CVPR, 2018.
  * [10] Jifeng Dai, Kaiming He, and Jian Sun.  Instance-aware semantic segmentation via multi-task network cascades.  In CVPR, 2016.
  * [11] Xianzhi Du, Tsung-Yi Lin, Pengchong Jin, Golnaz Ghiasi, Mingxing Tan, Yin Cui, Quoc V Le, and Xiaodan Song.  Spinenet: Learning scale-permuted backbone for recognition and localization.  In CVPR, 2020.
  * [12] Nikita Dvornik, Julien Mairal, and Cordelia Schmid.  Modeling visual context is key to augmenting object detection datasets.  In ECCV, 2018.
  * [13] Debidatta Dwibedi, Ishan Misra, and Martial Hebert.  Cut, paste and learn: Surprisingly easy synthesis for instance detection.  In ICCV, 2017.
  * [14] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  IJCV, 2010.
  * [15] Hao-Shu Fang, Jianhua Sun, Runzhong Wang, Minghao Gou, Yong-Lu Li, and Cewu Lu.  Instaboost: Boosting instance segmentation via probability map guided copy-pasting.  In ICCV, 2019.
  * [16] Georgios Georgakis, Md Alimoor Reza, Arsalan Mousavian, Phi-Hung Le, and Jana Košecká.  Multiview rgb-d dataset for object instance detection.  In 3DV, 2016.
  * [17] Golnaz Ghiasi, Tsung-Yi Lin, and Quoc V Le.  Nas-fpn: Learning scalable feature pyramid architecture for object detection.  In CVPR, 2019.
  * [18] Ross Girshick.  Fast r-cnn.  In ICCV, 2015.
  * [19] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In CVPR, 2014.
  * [20] Ross Girshick, Ilija Radosavovic, Georgia Gkioxari, Piotr Dollár, and Kaiming He.  Detectron, 2018.
  * [21] Agrim Gupta, Piotr Dollar, and Ross Girshick.  Lvis: A dataset for large vocabulary instance segmentation.  In CVPR, 2019.
  * [22] Bharath Hariharan, Pablo Arbeláez, Ross Girshick, and Jitendra Malik.  Simultaneous detection and segmentation.  In ECCV, 2014.
  * [23] Bharath Hariharan, Pablo Arbeláez, Ross Girshick, and Jitendra Malik.  Hypercolumns for object segmentation and fine-grained localization.  In CVPR, 2015.
  * [24] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In CVPR, 2020.
  * [25] Kaiming He, Ross Girshick, and Piotr Dollár.  Rethinking imagenet pre-training.  In ICCV, 2019.
  * [26] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In ICCV, 2017.
  * [27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [28] Olivier J Hénaff, Aravind Srinivas, Jeffrey De Fauw, Ali Razavi, Carl Doersch, SM Eslami, and Aaron van den Oord.  Data-efficient image recognition with contrastive predictive coding.  arXiv preprint arXiv:1905.09272, 2019.
  * [29] Xinting Hu, Yi Jiang, Kaihua Tang, Jingyuan Chen, Chunyan Miao, and Hanwang Zhang.  Learning to segment the tail.  In CVPR, 2020.
  * [30] Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang.  Learning deep representation for imbalanced classification.  In CVPR, 2016.
  * [31] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In ICML, 2015.
  * [32] Muhammad Abdullah Jamal, Matthew Brown, Ming-Hsuan Yang, Liqiang Wang, and Boqing Gong.  Rethinking class-balanced methods for long-tailed visual recognition from a domain adaptation perspective.  In CVPR, 2020.
  * [33] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis.  Decoupling representation and classifier for long-tailed recognition.  In ICLR, 2020.
  * [34] Salman Khan, Munawar Hayat, Syed Waqas Zamir, Jianbing Shen, and Ling Shao.  Striking the right balance with uncertainty.  In CVPR, 2019.
  * [35] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In NeurIPS, 2012.
  * [36] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 1998.
  * [37] Yu Li, Tao Wang, Bingyi Kang, Sheng Tang, Chunfeng Wang, Jintao Li, and Jiashi Feng.  Overcoming classifier imbalance for long-tail object detection with balanced group softmax.  In CVPR, 2020.
  * [38] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In CVPR, 2017.
  * [39] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In ICCV, 2017.
  * [40] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [41] Dhruv Mahajan, Ross Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li, Ashwin Bharambe, and Laurens van der Maaten.  Exploring the limits of weakly supervised pretraining.  In ECCV, 2018.
  * [42] Kemal Oksuz, Baris Can Cam, Sinan Kalkan, and Emre Akbas.  Imbalance problems in object detection: A review.  TPAMI, 2020.
  * [43] Siyuan Qiao, Liang-Chieh Chen, and Alan Yuille.  Detectors: Detecting objects with recursive feature pyramid and switchable atrous convolution.  arXiv preprint arXiv:2006.02334, 2020.
  * [44] Ilija Radosavovic, Piotr Dollár, Ross Girshick, Georgia Gkioxari, and Kaiming He.  Data distillation: Towards omni-supervised learning.  In CVPR, 2018.
  * [45] Jiawei Ren, Cunjun Yu, Zhongang Cai, and Haiyu Zhao.  Balanced activation for long-tailed visual recognition.  In LVIS Challenge Workshop at ECCV, 2020.
  * [46] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In NeurIPS, 2015.
  * [47] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  IJCV, 2015.
  * [48] Shuai Shao, Zeming Li, Tianyuan Zhang, Chao Peng, Gang Yu, Xiangyu Zhang, Jing Li, and Jian Sun.  Objects365: A large-scale, high-quality dataset for object detection.  In ICCV, 2019.
  * [49] Connor Shorten and Taghi M Khoshgoftaar.  A survey on image data augmentation for deep learning.  Journal of Big Data, 2019.
  * [50] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In ICLR, 2015.
  * [51] Bharat Singh, Mahyar Najibi, and Larry S Davis.  Sniper: Efficient multi-scale training.  In NeurIPS, 2018.
  * [52] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  In CVPR, 2015.
  * [53] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan.  Equalization loss for long-tailed object recognition.  In CVPR, 2020.
  * [54] Jingru Tan, Gang Zhang, Hanming Deng, Changbao Wang, Lewei Lu, Quanquan Li, and Jifeng Dai.  1st place solution of lvis challenge 2020: A good box is not a guarantee of a good mask.  arXiv preprint arXiv:2009.01559, 2020.
  * [55] Mingxing Tan and Quoc V Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In ICML, 2019.
  * [56] Mingxing Tan, Ruoming Pang, and Quoc V Le.  Efficientdet: Scalable and efficient object detection.  In CVPR, 2020.
  * [57] Kaihua Tang, Jianqiang Huang, and Hanwang Zhang.  Long-tailed classification by keeping the good and removing the bad momentum causal effect.  NeurIPS, 2020.
  * [58] Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie.  The inaturalist species classification and detection dataset.  In CVPR, 2018.
  * [59] Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus.  Regularization of neural networks using dropconnect.  In ICML, 2013.
  * [60] Chien-Yao Wang, Alexey Bochkovskiy, and Hong-Yuan Mark Liao.  Scaled-yolov4: Scaling cross stage partial network.  arXiv preprint arXiv:2011.08036, 2020.
  * [61] Tao Wang, Yu Li, Bingyi Kang, Junnan Li, Junhao Liew, Sheng Tang, Steven Hoi, and Jiashi Feng.  The devil is in classification: A simple framework for long-tail object detection and instance segmentation.  In ECCV, 2020.
  * [62] Yu-Xiong Wang, Deva Ramanan, and Martial Hebert.  Meta-learning to detect rare objects.  In ICCV, 2019.
  * [63] Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le.  Self-training with noisy student improves imagenet classification.  In CVPR, 2020.
  * [64] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In ICCV, 2019.
  * [65] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In ICLR, 2018.
  * [66] Hang Zhang, Chongruo Wu, Zhongyue Zhang, Yi Zhu, Zhi Zhang, Haibin Lin, Yue Sun, Tong He, Jonas Mueller, R. Manmatha, Mu Li, and Alexander Smola.  Resnest: Split-attention networks.  In arXiv preprint arXiv:2004.08955, 2020.
  * [67] Shifeng Zhang, Longyin Wen, Xiao Bian, Zhen Lei, and Stan Z Li.  Single-shot refinement neural network for object detection.  In CVPR, 2018.
  * [68] Zhi Zhang, Tong He, Hang Zhang, Zhongyue Zhang, Junyuan Xie, and Mu Li.  Bag of freebies for training object detection neural networks.  arXiv preprint arXiv:1902.04103, 2019.
  * [69] Zhenli Zhang, Xiangyu Zhang, Chao Peng, Xiangyang Xue, and Jian Sun.  Exfuse: Enhancing feature fusion for semantic segmentation.  In ECCV, 2018.
  * [70] Boyan Zhou, Quan Cui, Xiu-Shen Wei, and Zhao-Min Chen.  Bbn: Bilateral-branch network with cumulative learning for long-tailed visual recognition.  In CVPR, 2020.
  * [71] Barret Zoph, Ekin D Cubuk, Golnaz Ghiasi, Tsung-Yi Lin, Jonathon Shlens, and Quoc V Le.  Learning data augmentation strategies for object detection.  In ECCV, 2020.
  * [72] Barret Zoph, Golnaz Ghiasi, Tsung-Yi Lin, Yin Cui, Hanxiao Liu, Ekin D. Cubuk, and Quoc V. Le.  Rethinking pre-training and self-training.  In NeurIPS, 2020.

##  Appendix A Ablation on the Copy-Paste method

In this section we present ablations for our Copy-Paste method. We use Mask
R-CNN EfficientNetB7-FPN architecture and image size of 640$\times$640 for our
experiments.

#### Subset of pasted objects.

In our method, we paste a random subset of objects from one image onto another
image. Table 10 shows that although we get improvements from pasting only one
random object or all the objects of one image into another image, we get the
best improvement by pasting a random subset of objects. This shows that the
added randomness introduced from pasting a subset of objects is helpful.

#### Blending.

In our experiments, we smooth out the edges of pasted objects using alpha
blending (see Section 3). Table 10 shows that this is not an important step
and we get same results without any blending in contrast to [13] who find
blending is crucial for strong performance.

Setup | Box AP | Mask AP
---|---|---
EfficientNetB7-FPN (640) | 48.5 | 42.7
w/ Copy-Paste (one object) |  (-0.9) 49.1 |  (-0.6) 43.1
w/ Copy-Paste (all objects) |  (-0.3) 49.7 |  (-0.4) 43.3
w/ Copy-Paste (no blending) | 50.0 | 43.7
w/ Copy-Paste | 50.0 | 43.7
Table 10: Ablation studies for the Copy-Paste method on COCO. We study the
value of applying blending to pasted objects along with how many objects to
paste from one image to another.

#### Scale jittering.

In this work, we show that by combining large scale jittering and Copy-Paste
we obtain a significant improvement over the baseline with standard scale
jittering (Figure 1). In the Copy-Paste method, we apply independent random
scale jittering on both the pasted image (image that pasted objects are being
copying from) and the main image. In Table 11 we study the importance of large
scale jittering on both the main and the pasted images. Table 11 shows that
most of the improvement from large scale jittering is coming from applying it
on the main image and we only get slight improvement (0.3 box AP and 0.2 Mask
AP) from increasing the scale jittering range for the pasted image.

Main Image | Pasted Image | Box AP | Mask AP
---|---|---|---
SSJ | SSJ |  (-1.9) 48.1 |  (-1.6) 42.1
SSJ | LSJ |  (-2.3) 47.7 |  (-1.9) 41.8
LSJ | SSJ |  (-0.3) 49.7 |  (-0.2) 43.5
LSJ | LSJ | 50.0 | 43.7
Table 11: Ablation study on scale jittering methods for the main image and the
pasted image.

##  Appendix B Copy-Paste provides more gain on harder categories of COCO

Figure 6 shows relative AP gain per category obtained from applying Copy-Paste
on the COCO dataset. Copy-Paste improves the AP of all the classes except hair
drier. In Figure 6, classes are sorted based on the baseline AP per category.
As it can be seen most of the classes with highest improvement are on the left
(lower baseline AP) which shows Copy-Paste helps the hardest classes the most.

Figure 6: Per category relative AP improvement from Copy-Paste on 80 classes
of COCO dataset. Numbers in the parentheses show the AP per category of the
baseline model (first number) and the model trained with Copy-Paste (second
number). Each number is the average over 5 runs. Classes are sorted based on
the baseline AP per class.


number of new elements. Moreover, by choice of $\varepsilon^{\prime}$, the
$\frac{\ell}{2}-$th neighborhood of $S$ contains at most
$\dfrac{\gamma^{\prime}n}{\Delta}$ vertices (that is, by Corollary 5.14 at
most half of the vertices of $C^{\prime}_{cm,max}$ a.a.s.), ensuring
concentration throughout the process. Thus, the conditions of Theorem 2.6 are
satisfied for $|\mathcal{C}(t)|$, $|\mathcal{V}_{1}(t)|$ and
$|\mathcal{V}_{\geq 2}(t)|$ as functions of $t$, and we deduce that all of
them are concentrated around their expected values in the end of the
exploration process. ∎

######  Corollary 5.26.

Asymptotically almost surely, for every small enough $\varepsilon^{\prime}>0$,
the number of $S-$chains of length $\ell$ of vertices participating in only
one $S-$chain of length $\ell$ is at least
$\dfrac{\delta^{2}\varepsilon^{\prime
2}n}{2M}\left(1+\dfrac{\gamma^{\prime}}{\Delta M}\right)^{\ell-1}$.

###### Proof.

By Lemma 5.24 and Observation 5.25 there is a constant $c_{\ell}$ such that
the number of vertices in $C^{\prime}_{max}$ in at least two $S-$chains is
a.a.s. at most $2c_{\ell}\varepsilon^{\prime 3}n$. On the other hand, by Lemma
5.22 and Observation 5.25 there are a.a.s. at least
$\dfrac{3}{4}\dfrac{\delta^{2}\varepsilon^{\prime
2}n}{M}\left(1+\dfrac{\gamma^{\prime}}{\Delta M}\right)^{\ell-1}$ $S-$chains
of length $\ell$. We conclude that a.a.s. for every small enough
$\varepsilon^{\prime}$ there are at least

$\dfrac{1}{2}\dfrac{\delta^{2}\varepsilon^{\prime
2}n}{M}\left(1+\dfrac{\gamma^{\prime}}{\Delta M}\right)^{\ell-1}$

$S-$chains of length $\ell$, each of which contains only vertices, which
participate in only one such chain. The lemma is proved. ∎

######  Lemma 5.27.

For every $C>0$, for every large enough $\ell$ and every small enough
$\varepsilon^{\prime}>0$ asymptotically almost surely

$\dfrac{e(A^{\prime}_{max})}{|A^{\prime}_{max}|}\geq
1+C\dfrac{|A^{\prime}_{max}|}{n}.$

###### Proof.

We fix a positive integer $\ell$ that we specify in the sequel. Fix also
$C>0$. By Corollary 5.26 there are a.a.s. at least
$\dfrac{\delta^{2}\varepsilon^{\prime
2}n}{2M}\left(1+\dfrac{\gamma^{\prime}}{\Delta M}\right)^{\ell-1}$ $S-$chains
of length at most $\ell$ with vertices in only one chain of this type. On the
other hand, $A^{\prime}_{max}$ contains a.a.s. at most
$\varepsilon^{\prime}n+c_{\ell}\varepsilon^{\prime 2}n$ vertices by Lemma 5.24
and Observation 5.25. We conclude that for $\varepsilon^{\prime}\to 0$, a.a.s.

$\dfrac{n(e(A^{\prime}_{max})-|A^{\prime}_{max}|)}{|A^{\prime}_{max}|^{2}}\geq\dfrac{\dfrac{\delta^{2}\varepsilon^{\prime
2}n^{2}}{2M}\left(1+\dfrac{\gamma^{\prime}}{\Delta
M}\right)^{\ell-1}}{(\varepsilon^{\prime}(1+O_{\varepsilon^{\prime}}(\varepsilon^{\prime}))^{2}n^{2}}.$

Now, taking the limits, first, with respect to $n\to+\infty$, and then, with
respect to $\varepsilon^{\prime}\to 0$, we conclude that it is sufficient to
choose $\ell$ such that
$\dfrac{\delta^{2}}{2M}\left(1+\dfrac{\gamma^{\prime}}{\Delta
M}\right)^{\ell-1}>C$. The lemma is proved. ∎

######  Corollary 5.28.

The conclusion of Lemma 5.27 holds asymptotically almost surely also when
replacing $C^{\prime}_{cm,max}$ by $C^{\prime}_{max}$.

###### Proof.

This is a direct consequence of Corollary 5.17. ∎

A smoothing of a vertex of degree two in a graph consists in deleting the
vertex and then joining its two neighbors by an edge. In particular, we might
obtain a multigraph: if the two neighbors are already connected by one or more
edges, the number of edges between them increases by one after the smoothing.
A contraction of an edge in a graph consists in deleting the edge and
identifying its endvertices. Remark that smoothing of a vertex $v$ of degree
two is equivalent to contracting any of the edges incident with $v$. Let
$G^{\prime}$ be a uniform random graph on $(d^{\prime}_{i})_{2\leq
i\leq\Delta}$ vertices of degree $(i)_{2\leq i\leq\Delta}$, respectively.

######  Lemma 5.29.

By sampling $G^{\prime}$, smoothing all vertices of degree two and deleting
isolated vertices incident to at most one loop, we generate a uniform random
graph $G^{\prime\prime}$ on $(d^{\prime}_{i})_{3\leq i\leq\Delta}$ vertices of
degree $(i)_{3\leq i\leq\Delta}$, respectively.

###### Proof.

Let $(Q_{s,t,j})_{1\leq s\leq j,1\leq t\leq d^{\prime}_{j},2\leq j\leq\Delta}$
be the points of the matching at the origin of the configuration model for
$G^{\prime}$. Let also $(R_{s,t,j})_{1\leq s\leq i,1\leq t\leq
d^{\prime}_{j},3\leq j\leq\Delta}$ be the points of the matching at the origin
of the configuration model for the random graph $G^{\prime\prime}$. We present
a coupling between the probability space of the matchings of
$(Q_{s,t,j})_{1\leq s\leq j,1\leq t\leq d^{\prime}_{j},2\leq j\leq\Delta}$ and
of $(R_{s,t,j})_{1\leq s\leq j,1\leq t\leq d^{\prime}_{j},3\leq j\leq\Delta}$.
We perform the following algorithm generating the graphs $G^{\prime}$ and
$G^{\prime\prime}$ at the same time.

  1. 1.

Choose an arbitrary point $Q_{s^{\prime},t^{\prime},j^{\prime}}$ with $1\leq
s^{\prime}\leq j,1\leq t^{\prime}\leq d^{\prime}_{j},3\leq
j^{\prime}\leq\Delta$ (if it exists, if not, go to point 5.) that has not been
matched yet. Prepare to match the point
$R_{s^{\prime},t^{\prime},j^{\prime}}$.

  2. 2.

Match $Q_{s^{\prime},t^{\prime},j^{\prime}}$ with some unmatched point
$Q=Q_{s^{\prime\prime},t^{\prime\prime},j^{\prime\prime}}$ among
$(Q_{s,t,j})_{1\leq s\leq j,1\leq t\leq d^{\prime}_{j},2\leq j\leq\Delta}$.

  3. 3.

If $j^{\prime\prime}\geq 3$, match $R_{s^{\prime},t^{\prime},j^{\prime}}$ and
$R_{s^{\prime\prime},t^{\prime\prime},j^{\prime\prime}}$. Then, return to 1.

  4. 4.

If $j^{\prime\prime}=2$, then keep the point
$R_{s^{\prime},t^{\prime},j^{\prime}}$ waiting and perform 2. with
$Q_{3-s^{\prime\prime},t^{\prime\prime},j^{\prime\prime}}$ instead of
$Q_{s^{\prime},t^{\prime},j^{\prime}}$.

  5. 5.

Match all points among $(Q_{s,t,j})_{1\leq s\leq j,1\leq t\leq
d^{\prime}_{j},2\leq j\leq\Delta}$ that remain unmatched uniformly at random.

∎

######  Lemma 5.30.

For every small enough $\varepsilon^{\prime}>0$ the following statement holds
asymptotically almost surely: there exists a constant $c>0$ such that the
graph $C^{\prime}_{cm,max}\setminus A^{\prime}_{max}$ contains at most
$c\varepsilon^{\prime 2}n$ connected components.

###### Proof.

By Lemma 2.9, $C^{\prime}_{cm,max}$ contains a giant connected component,
which contains all but at most $\log n$ vertices. Hence there are at most
$\log n+1$ connected components. Let $C^{\prime\prime}_{cm,max}$ be obtained
by smoothing $C^{\prime}_{cm,max}$ and deleting isolated vertices (that have
loops attached to them) and let $A^{\prime\prime}_{max}$ be the subgraph of
$C^{\prime\prime}_{cm,max}$ obtained from $A^{\prime}_{cm,max}$ by this
operation. Now, perform the following procedure:

  1. 1.

Expose all edges going out of $A^{\prime\prime}_{max}$.

  2. 2.

For every connected component on the set of vertices in
$C^{\prime\prime}_{cm,max}\setminus A^{\prime\prime}_{max}$, do the following:
if this component is incident to only one unexposed half-edge, expose this
half-edge. Repeat this procedure as long as such components on the set of
currently exposed edges exist (but do not add them to
$A^{\prime\prime}_{max}$; see Figure 8 for an illustration before the
smoothing).

  3. 3.

Delete the graph $A^{\prime\prime}_{max}$ and contract all connected
components on the set of exposed edges. The graph that remains consists of
only unexposed half-edges and all vertices are of degree different from one.

Here smoothing the graph $C^{\prime}_{cm,max}$ is done to avoid the
exploration of long paths of degree two and to a.a.s. ensure higher
connectivity of the $2-$core. Another reason is that random graphs of minimal
degree three are a.a.s. $3-$connected, which does not hold for random graphs
of minimal degree two.

Consider the set of non-isolated vertices in $C^{\prime\prime}_{cm,max}$.
Since the set of unexposed half-edges is matched according to the
configuration model on a graph of minimal degree two and a positive proportion
of vertices of degree at least three (this is ensured by Observation 5.18 by
choosing $\varepsilon^{\prime}$ small enough), $C^{\prime\prime}_{cm,max}$
contains at most $\log n$ connected components, different from the giant
component, by Lemma 2.9.

On the other hand, the set of isolated vertices in $C^{\prime\prime}_{cm,max}$
corresponds to connected components of exposed edges, which remain
disconnected from the rest of the graph $C^{\prime\prime}_{cm,max}$ after
deletion of $A^{\prime\prime}_{max}$. Note that any such component of
$C^{\prime\prime}_{cm,max}\setminus A^{\prime\prime}_{max}$ has to be
connected by at least $3$ edges to $A^{\prime\prime}_{max}$, since
$C^{\prime\prime}_{max}$ has minimum degree $3$, and by ([FR04], Theorem 5.1)
it is a.a.s. $3-$connected (note that our sequence is $2-$smooth in the
terminology of [FR04], since $\lim_{n\to\infty}d_{i}(n)/n=p_{i}$ with
$d_{i}(n)=0$ for every $i\geq\Delta+1$ and $n\in\mathbb{N}$ and this applies
then also to the degree sequence of $C^{\prime\prime}_{max}$).

Define $C^{\prime}_{del}$ to be the graph induced by
$E(C^{\prime}_{cm,max})\setminus E(A^{\prime}_{max})$, and define
$C^{\prime\prime}_{del}$ to be the graph induced by
$E(C^{\prime\prime}_{cm,max})\setminus E(A^{\prime\prime}_{max})$. Observe
that both $C^{\prime}_{del}$ and $C^{\prime\prime}_{del}$ follow a
configuration model. Set
$C_{\Delta}=\dfrac{\Delta^{\frac{\ell}{2}+1}-1}{\Delta-1}$.

  * •

We saw that at most $\log n$ vertices of $C^{\prime}_{cm,max}$ are not in the
connected component of $A^{\prime}_{max}$ a.a.s.

  * •

The connected components in $C^{\prime}_{del}$ are obtained from subdivisions
of connected components in $C^{\prime\prime}_{del}$. If one such connected
component contains a vertex of $C^{\prime\prime}_{cm,max}\setminus
A^{\prime\prime}_{max}$, by $3-$connectivity of $C^{\prime\prime}_{cm,max}$
(see [FR04], Theorem 5.1) it connects to $A^{\prime}_{max}$ using at least
three edges. The remaining analysis is therefore similar to the analysis given
in Subsection 5.1. In particular, we have:

    * –

the number of such components of order more than $\sqrt{\log n}$ is at most
$o(n)$;

    * –

as before, the number of components of order at most $\sqrt{\log n}$
containing a cycle is $o(n)$ by a first moment calculation similar to the one
in Lemma 5.5 for trees;

    * –

the expected number of acyclic components of order at most $\sqrt{\log n}$ is
$C_{1}\varepsilon^{\prime 3}n$ for some constant
$C_{1}=C_{1}(\boldsymbol{p},\Delta)>0$. Indeed, all components of this type
are connected by at least three edges to $A^{\prime}_{max}$ and the number of
open half-edges incident to $A^{\prime}_{max}$ is at most $\Delta
C_{\Delta}\varepsilon^{\prime}n$. Moreover, the number of such components is
concentrated around its expected value, which may be seen once again by a
second moment method applied analogously to the proof of Lemma 5.5 in the
subcritical case.

On the other hand, if the connected component of $C^{\prime}_{del}$ does not
contain a vertex from $C^{\prime\prime}_{cm,max}\setminus
A^{\prime\prime}_{max}$, we may obtain an $A^{\prime}_{max}$-chain. Summing
over all possible lengths of such $A^{\prime}_{max}-$chains and applying the
second moment method again analogously to the proof of Lemma 5.5 we obtain
that there is a constant $C_{2}=C_{2}(\boldsymbol{p},\Delta)>0$, such that the
number of $A^{\prime}_{max}-$chains is concentrated around its expected value,
which is $C_{2}\varepsilon^{\prime 2}n$. Indeed, as above, all chains of this
type are connected by exactly two edges to $A^{\prime}_{max}$ and the number
of open half-edges incident to $A^{\prime}_{max}$ is at most $\Delta
C_{\Delta}\varepsilon^{\prime}n$.

Thus, for every small enough $\varepsilon^{\prime}>0$ one may define
$c=2C_{2}$. This proves the lemma. ∎

$A^{\prime}_{max}$ Figure 8: The component $A^{\prime}_{max}$, the set of
explored vertices and edges in $C^{\prime}_{max}$ and a number of vertices,
non-explored throughout the construction of $A^{\prime}_{max}$ (these are
shown as isolated in the figure).

######  Corollary 5.31.

The conclusion of Lemma 5.30 holds for $C^{\prime}_{max}$ instead of
$C^{\prime}_{cm,max}$ as well.

###### Proof.

This follows directly from Corollary 5.17. ∎

###### Proof of Lemma 5.10.

If $p_{1}=0$, then $C_{max}=C^{\prime}_{max}$ and the claim is a direct
consequence of Lemma 5.27.

By Lemma 5.27 we have that for every positive constant $C$ there exists
$\varepsilon_{0}>0$, for which, for every
$\varepsilon^{\prime}\in(0,\varepsilon_{0})$, there is a set of vertices
$A^{\prime}_{max}$ of $C^{\prime}_{max}$, for which

$\dfrac{e(A^{\prime}_{max})}{|A^{\prime}_{max}|}\geq\left(1+\dfrac{C|A^{\prime}_{max}|}{n}\right).$

On the other hand, by Lemma 5.20, there exists $\alpha>1$, such that a.a.s.
$A_{max}$ has size at most $\alpha|A^{\prime}_{max}|$. Thus, a.a.s., the
density of $A_{max}$ satisfies

$\dfrac{e(A_{max})}{|A_{max}|}\geq\dfrac{e(A^{\prime}_{max})+(\alpha-1)|A^{\prime}_{max}|}{\alpha|A^{\prime}_{max}|}\geq\dfrac{\alpha+C\dfrac{|A^{\prime}_{max}|}{n}}{\alpha}\geq
1+\dfrac{C|A_{max}|}{\alpha^{2}n}.$

Now, up to the choice of small enough $\varepsilon^{\prime}>0$, one may choose
$C$ arbitrarily large. The conclusion of the first part of Lemma 5.10 is
satisfied. The conclusion of the second part of Lemma 5.10 follows directly by
Lemma 5.30. ∎

##  6 Discussion

On the one hand, we showed that in sparse random graphs coming from a
supercritical configuration model the modularity is strictly larger than the
trivial lower bound obtained by partitioning into connected components. On the
other hand, for random $3-$regular graphs we are more precise by quantifying
the gain over this trivial bound (which in this case is equal to $2/3$).
Without doubt, by adding more stages (that is, by considering longer chains)
in the analysis of the lower bound in the case of random $3-$regular graphs,
one could improve the lower bound given by Theorem 1.1 by a little bit. The
upper bound still being far, we opted for not pushing this to the limit.
Needless to say, it would be interesting to find the exact value of the
modularity of random $3-$regular graphs, but our methods are not strong enough
to determine this value.

## References

  * [Bag12] J.P. Bagrow.  Communities and bottlenecks: Trees and treelike networks have high modularity.  Physical Review E, 85(6):066118, 2012.
  * [BC78] E. A. Bender and E. R. Canfield.  The asymptotic number of labelled graphs with given degree sequences.  Journal of Combinatorial Theory (A), pages 296–307, 1978.
  * [BDG+07] U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner.  On finding graph clusterings with maximum modularity.  Graph-Theoretic Concepts in Computer Science, pages 121–132, 2007\.
  * [BDG+08] U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner.  On modularity clustering.  IEEE Transactions on Knowledge and Data Engineering, 20:172–188, 2008.
  * [Bol01] B. Bollobás.  Random Graphs.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2001.
  * [Cur18] N. Curien.  Random graphs - the local convergence point of view, 2018.
  * [DLT15] T. N. Dinh, X. Li, and M. T. Thai.  Network clustering via maximizing modularity: Approximation algorithms and theoretical limits.  2015 IEEE International Conference on Data Mining (ICDM), pages 101–110, 2015.
  * [FH16] S. Fortunato and D. Hric.  Community detection in networks: A user guide.  Physics Reports, 659, pages 1–44, 2016.
  * [For10] S. Fortunato.  Community detection in graphs.  Physics Reports, 486(3), 2010.
  * [FR04] D. Fernholz and V. Ramachandran.  Cores and connectivity in sparse random graphs.  UTCS Technical Report TR04-13, 2004.
  * [FvdH17] L. Federico and R. van der Hofstad.  Critical window for connectivity in the configuration model.  Combinatorics, Probability and Computing, 26(5):660–680, May 2017\.
  * [GSPA04] R. Guimerà, M. Sales-Pardo, and L. A. N. Amaral.  Modularity from fluctuations in random graphs and complex networks.  Physical Review E, 70:025101, 2004.
  * [Inca] OEIS Foundation Inc.  The on-line encyclopedia of integer sequences.  http://oeis.org/A001190.
  * [Incb] OEIS Foundation Inc.  The on-line encyclopedia of integer sequences.  http://oeis.org/A086317.
  * [Jan95] S. Janson.  Random regular graphs: asymptotic distributions and contiguity.  Combin. Probab. Comput., pages 369–405, 1995.
  * [JLR00] S. Janson, T. Łuczak, and A. Ruciński.  Random Graphs.  Wiley, 2000.
  * [Joh] P. Johnson.  Lecture 8: Prüfer code.  https://ptwiddle.github.io/MAS341-Graph-Theory-2017/lecturenotes/lecture8.html.
  * [LF11] A. Lancichinetti and S. Fortunato.  Limits of modularity maximization in community detection.  Physical Review E, 84(6):066122, 2011.
  * [MR95] M. Molloy and B. Reed.  A critical point for random graphs with a given degree sequence.  Random structures and Algorithms, 6(2-3):161–180, 1995.
  * [MS13] C. McDiarmid and F. Skerman.  Modularity in random regular graphs and lattices.  Electronic Notes in Discrete Mathematics, 43, 2013.
  * [MS18] C. McDiarmid and F. Skerman.  Modularity of regular and treelike graphs.  Oxford Journal of Complex Networks, 6 (4), 2018.
  * [MS20] C. McDiarmid and F. Skerman.  Modularity of Erdős-Rényi random graphs.  Random Structures and Algorithms, 2020.
  * [MSV11] F. De Montgolfier, M. Soto, and L. Viennot.  Asymptotic modularity of some graph classes.  Algorithms and Computation, pages 435–444, 2011.
  * [NG04] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Physical Review E, 69(2):026113, 2004.
  * [POM09] M. A. Porter, J.-P. Onnela, and P. J. Mucha.  Communities in networks.  Notices of the AMS, 56(9):1082–1097, 2009.
  * [PPR17] L. Ostroumova Prokhorenkova, P. Prałat, and A. Raigorodskii.  Modularity of complex networks models.  Internet Mathematics, 2017.
  * [RB06] J. Reichardt and S. Bornholdt.  Statistical mechanics of community detection.  Physical Review E, 74(1) 016110, 2006.
  * [Sal11] J. Salez.  Some implications of local weak convergence for sparse random graphs.  PhD thesis, DI-ENS - Département d’informatique de l’Ecole normale supérieure, Inria Paris-Rocquencourt, 2011.
  * [Warar] L. Warnke.  On Wormald’s differential equation method.  Combinatorics, Probability and Computing, to appear.
  * [Wor78] N. C. Wormald.  Some Problems in the Enumeration of Labelled Graphs.  PhD thesis, Newcastle University, 1978.
  * [Wor81] N. C. Wormald.  The asymptotic distribution of short cycles in random regular graphs.  Journal of Combinatorial Theory, Series B, 31(2):168 – 182, 1981\.
  * [Wor95] N. C. Wormald.  Differential equations for random processes and random graphs.  Annals of Applied Probability, 5:1217–1235, 1995.
  * [Wor99a] N. C. Wormald.  The differential equation method for random graph processes and greedy algorithms.  In M. Karoński and H. Prömel, Eds., Lectures on Approximation and Randomized Algorithms, pages 73–155, 1999.
  * [Wor99b] N. C. Wormald.  Models of random regular graphs.  In J.D. Lamb, D.A. Preece, Eds., Surveys in Combinatorics, volume 276 of London Mathematical Society Lecture Notes Series, pages 239–298, 1999.