# Single-Stage Open-world Instance Segmentation with Cross-task Consistency
Regularization

Xizhe Xue This work was done when Xizhe Xue visited National University of
Singapore. Email<EMAIL_ADDRESS>Northwestern Polytechnical
University  Show Lab, National University of Singapore  Dongdong Yu  ByteDance
Inc.  Lingqiao Liu  University of Adelaide  Yu Liu  ByteDance Inc.  Satoshi
Tsutsui  Show Lab, National University of Singapore  Ying Li Corresponding
author Northwestern Polytechnical University  Zehuan Yuan  ByteDance Inc.
Ping Song  ByteDance Inc.  Mike Zheng Shou  Show Lab, National University of
Singapore

###### Abstract

Open-World Instance Segmentation (OWIS) is an emerging research topic that
aims to segment class-agnostic object instances from images. The mainstream
approaches use a two-stage segmentation framework, which first locates the
candidate object bounding boxes and then performs instance segmentation. In
this work, we instead promote a single-stage framework for OWIS. We argue that
the end-to-end training process in the single-stage framework can be more
convenient for directly regularizing the localization of class-agnostic object
pixels. Based on the single-stage instance segmentation framework, we propose
a regularization model to predict foreground pixels and use its relation to
instance segmentation to construct a cross-task consistency loss. We show that
such a consistency loss could alleviate the problem of incomplete instance
annotation – a common problem in the existing OWIS datasets. We also show that
the proposed loss lends itself to an effective solution to semi-supervised
OWIS that could be considered an extreme case that all object annotations are
absent for some images. Our extensive experiments demonstrate that the
proposed method achieves impressive results in both fully-supervised and semi-
supervised settings. Compared to SOTA methods, the proposed method
significantly improves the $AP_{100}$ score by 4.75% in UVO$\rightarrow$UVO
setting and 4.05% in COCO$\rightarrow$UVO setting. In the case of semi-
supervised learning, our model learned with only 30% labeled data, even
outperforms its fully-supervised counterpart with 50% labeled data. The code
will be released soon at: https://github.com/showlab/SOIS.

##  1 Introduction

Traditional instance segmentation [1, 2] methods often assume that objects in
images can be categorized into a finite set of predefined classes (i.e.,
closed-world). Such an assumption, however, can be easily violated in many
real-world applications, where models will encounter many new object classes
that never appeared in the training data. Therefore, researchers recently
attempted to tackle the problem of Open-World Instance Segmentation (OWIS)
[3], which targets class-agnostic segmentation of all objects in the image.

Prior to this paper, most existing methods for OWIS are of two-stage [4, 5],
which detects bounding boxes of objects and then segments them. Despite their
promising performances, such a paradigm cannot handle and recover if object
bounding boxes are not detected. In contrast, a single-stage approach called
Mask2Former [6] has recently been introduced, yet only for closed-world
instance segmentation. By extending it to open-world, we are the first to
develop a novel detection-free Single-stage Open-world Instance Segmentation
method, dubbed as SOIS.

Note that our work is not just a straightforward adaptation of Mask2Former
from close-world to open-world. This is because unlike closed-world
segmentation, where the object categories can be clearly defined before
annotation, the open-world scenario makes it challenging for annotators to
label all instances completely or ensure annotation consistency across
different images because they cannot have a well-defined finite set of object
categories. As shown in Figure 1(a), annotators miss some instances. It still
remains challenging that how to handle such incomplete annotations (i.e. some
instances missed).

Recent work LDET [5] addresses this problem by generating synthetic data with
a plain background, but it based on a decoupled training strategy that can
only be used in the two-stage method while our method is of single-stage.
Another work called GGN [4] handles such incomplete instance-level annotation
issue by training a pairwise affinity predictor for generating pseudo labels.
But training such an additional predictor is complicated and time-consuming.

In contrast, our proposed SOIS method is end-to-end and simpler. We address
this incomplete annotation issue via a novel regularization module, which is
simple yet effective. Specifically, it is convenient to concurrently predict
not only (1) instance masks but also a (2) foreground map. Ideally, as shown
in Figure 1(b), the foreground region should be consistent with the union of
all instance masks. To penalize their inconsistency, we devise a cross-task
consistency loss, which can down-weight the adverse effects caused by
incomplete annotation. This is because when an instance is missed in
annotation, as long as it is captured by both our predictions of instance
masks and foreground map, the consistency loss would be low and hence
encourage such prediction. Experiments in Figure 1(g) show that such
consistency loss is effective even when annotations miss many instances.

Figure 1:  (a). Instances missing annotations in COCO and UVO datasets. The
regions in red boxes are mistakenly annotated as background. (b). Motivation
of our novel reg module (The consistency relationship between instance mask
and foreground map). (c). Visualization results of our SOIS on UVO dataset.
Here, the proposed SOIS is trained on COCO dataset and tested on UVO dataset.
Our methods correctly segments many objects that are not labeled in COCO. (d -
f). The $AP_{100}$% of our SOIS vs.SOTA methods on COCO$\rightarrow$UVO,
Cityscpes$\rightarrow$Mapillary, COCO$\rightarrow$UVO. (g). The $AR_{100}$% of
our SOIS vs. baseline Mask2Former on COCO. From right to left, with the total
number of classes decreases (i.e. more instance annotations missed), the gain
of our SOIS over baseline becomes larger, thanks to the capability of our
model to handle incomplete annotations.

So far, like most existing methods, we focus on the fully-supervised OWIS. In
this paper, we further extend OWIS to the semi-supervised setting, where some
training images do not have any annotations at all. This is of great interest
because annotating segmentation map is very costly. Notably, our proposed
regularization module can also benefit semi-supervised OWIS – consider an
unlabeled image as an extreme case of incomplete annotation where all of the
instance annotations are missed. Specifically, we perform semi-supervised OWIS
by first warming up the network on the labeled set and then continuing
training it with the cross-task consistency loss on the mixture of labeled and
unlabeled images.

Contributions. In a nutshell, our main contributions could be summarized as:

  1. 1.

We propose a Singe-stage Open-world Instance Segmentation (SOIS) for the first
time while most OWIS methods are of two-stage.

  2. 2.

We propose a novel cross-task consistency loss that mitigate the issue of
incomplete mask annotations.

  3. 3.

We further extend the proposed method into a semi-supervised OWIS model, which
effectively makes use of the unlabeled images to help the OWIS model training
.

  4. 4.

Our extensive experiments demonstrate that the proposed method reaches the
leading OWIS performance in the fully-supervised learning. (Figure 1(d-f)),
and that our semi-supervised extension can achieve remarkable performance with
a much smaller amount of labeled data.

##  2 Related Work

#### Closed-world instance segmentation (CWIS)

[7, 8, 9, 10, 11] requires the approaches to assign a class label and instance
ID to every pixel. Two-stage CWIS approaches, such as MaskRCNN, always include
a bounding box estimation branch and a FCN-based mask segmentation branch,
working in a ’detect-then-segment’ way. To improve efficiency, one-stage
methods such as CenterMask [9], YOLACT [10] and BlendMask [8] have been
proposed, which remove the proposal generation and feature grouping process.
To further free the CWIS from the local box detection, Wang et.al [11]
proposed SOLO and obtained on par results to the above methods. In recent
years, the methods [12, 13], following DETR [14], consider the instance
segmentation task as an ensemble prediction problem. In addition, Cheng et al.
proposed an universal segmentation framework MaskFormer [15] and its upgrade
version Mask2Former [6], which even outperforms the state-of-the-art
architectures specifically designed for the CWIS task.

Notably, two-stage method CenterMask preserves pixel alignment and separates
the object simultaneously by integrating the local and global branch. Although
introducing the global information in this way helps improve the mask quality
in CWIS, it can not handle the open-world task very well. Because CenterMask
multiplies the local shape and the cropped saliency map to form the final mask
for each instance. There is no separate loss for the local shape and global
saliency. When such method faces the incomplete annotations in OWIS tasks, the
generated mask predictions corresponding to the unlabeled instances would
still be punished during training, making it difficult to discover novel
object at inference. The efficient way to jointly take advantages of global
and local information in OWIS tasks deserves to be explored.

#### Open-world instance segmentation

OWIS task [3] here focuses on the following aspects: (1) All instances
(without stuff) have to be segmented; (2) Class-agnostic pixel-level results
should be predicted with only instance ID and incremental learning ability is
unnecessary. Several OWIS works have recently been developed. Yu et al. [16]
proposed a two-stage segmentation algorithm, which decoupled the segmentation
and detection modules during training and testing. This algorithm achieves
competitive results on the UVO dataset thanks to the abundant training data
and the introduction of effective modules such as cascade RPN [17], SimOTA
[18], etc. Another work named LDET [5] attempts to solve the instance-level
incomplete annotation problem. Specifically, LDET first generates the
background of the synthesized image by taking a small piece of background in
the original image and enlarging it to the same size as the original image.
The instance is then matted to the foreground of the synthesized image. The
synthesized data is used only to train the mask prediction branch, and the
rest of the branches are still trained with the original data. Meanwhile, Wang
et al. proposed GGN [4], an algorithm that combines top-down and bottom-up
segmentation ideas to improve prediction accuracy by generating high-quality
pseudo-labels. Specifically, a Pairwise Affinity (PA) predictor is trained
first and a grouping module is used to extract and rank segments from
predicted PA to generate pseudo-labels, which would be fused with groundtruth
to train the segmentation model.

##  3 Methodology

In this section, we first define the OWIS problem with both fully and semi-
supervised learning. Then the architecture of our SOIS and the proposed cross-
task consistency loss are introduced in Section 3.3 and 3.4, respectively.
Finally, Section 3.4 and 3.5 show how to optimize the SOIS in fully and semi-
supervised way, respectively.

###  3.1 Problem Definition of OWIS

The open-world instance segmentation (OWIS) aims to segment all the object
instances (things) of any class including those that did not appear in the
training phase. Technically, OWIS is a task to produce a set of binary masks,
where each mask corresponds to a class-agnostic instance. The pixel value of
$1$ in the mask indicates a part of an object instance while $0$ indicates
not.

###  3.2 Model Architecture

Figure 2:  Overall framework of the proposed SOIS. The mask prediction branch
generates the predicted masks, while the objectness prediction branch computes
the objectness score for each mask. The foreground prediction branch segments
a foreground region to guide the optimization of other two branches.

Our proposed SOIS framework consists of three branches to alleviate the
incomplete annotating, as shown in Figure 6. Basically, we follow the design
of one-stage Mask2Former [6]. The objectness prediction branch estimates the
weighting score for each mask by applying a sequential Transformer decoder and
MLP. The mask prediction branch predicts the binary mask for each instance. It
first generates $N$ binary masks with $N$ ideally larger than the actual
instance number $K_{i}$. Each mask is multiplied by a weighting score with a
value between $0$ and $1$, indicating if a mask should be selected as an
instance mask. This process generates the mask in an end to end way, which
avoids to miss the instance because of poor detection bounding boxes and
meanwhile reduces the redundant segmentation cost for each proposal. We refer
to [15, 6] for more details including the training procedure.

The foreground prediction branch is a light-weight fully convolutional network
to estimate the foreground regions that belong to any object instance.The more
detailed design of the foreground prediction branch is in the Appendix. This
guides the training of the mask branch through our cross-task consistency loss
proposed in the following Sec. 3.3. Once training is done, we discard this
branch and only use the objectness and mask prediction branch at inference
time. Therefore, we would not introduce any additional parameter or
computational redundancy, which benefits the running efficiency.

###  3.3 Learning with the cross-task consistency regularization

A critical limitation of the OWIS is the never-perfect annotations due to the
difficulties in annotating class-agnostic object instances. Towards
alleviating this issue, we propose a regularization to provide extra
supervision to guide the OWIS model training under incomplete annotations.

We construct a branch to predict the foreground regions that belong to any of
the object instance. Formally we create the the foreground annotation $G(x,y)$
calculated by

$\displaystyle{G}(x,y)=\begin{cases}\text{ 0,
}\>\;\text{if}\>\;\sum_{i=1}^{K}{g^{i}}(x,y)==0\\\ \text{
1,}\>\;\text{otherwise,}\end{cases}$ (1)

where $g^{i}(x,y)$ is one of the $K$ annotated object instances for the
current image and the union of $g^{i}$ defines the foreground object regions.
Here $(x,y)$ denotes a coordinate of a pixel in the an image. We use $G(x,y)$
as labels to train the foreground prediction branch.

Our consistency loss encourages the model outputs to have the relationship
indicated in Eq 1, which states that the the foreground prediction should be
the union of instance predictions. To do so, we use the following equation as
an estimate of the foreground from the instance prediction:

$\displaystyle\hat{G}(x,y)=\Phi\left(\sum_{j=1}^{K}{m^{j}}(x,y)\right),$ (2)

where $m^{j}$ means the confidence of pixels in j-th predicted mask, and
$\Phi$ represents the Sigmoid function. Then, let the foreground prediction
from the foreground prediction branch be $F$, our cross-task consistency loss
is to make $F$ and $\hat{G}(x,y)$ consistent, which finally leads to the
following loss function.

$\displaystyle L_{c}=\text{DICE}_{(\hat{G},F)}+\text{BCE}_{(\hat{G},F)},$ (3)

where DICE and BCE denote the dice-coefficient loss [19] and binary cross-
entropy loss, respectively.

Figure 3: Working principle of consistency loss.

Consistency loss enjoys the following appealing properties. It is self-
calibrated and independent with the incompleteness level of labels. As shown
in Figure 3, for a instance mistakenly annotated as background, but the
foreground prediction branch and mask prediction branch both correctly find
it, the model would be punished through mask loss and foreground loss.
However, the consistency loss think this prediction is correct. In this way,
consistency loss down-weights the adverse effects caused by other unreliable
segmentation loss. The mitigation and the compensation factor synergize to
relieve the overwhelming punishments on unlabeled instances.

###  3.4 Fully-supervised learning

The overall fully-supervised optimization of the proposed SOIS is carried out
by minimizing the following joint loss formulation $L_{f}$,

$\displaystyle L_{f}=\alpha L_{m}+\beta L_{p}+\gamma L_{c}+\omega L_{o},$ (4)
where $\displaystyle L_{m}=\text{BCE}_{(m,g)}+\text{DICE}_{(m,g)},$ (7)
$\displaystyle L_{p}=\text{BCE}_{(F,G)}+\text{DICE}_{(F,G)},$ $\displaystyle
L_{o}=\text{BCE}_{(s,v)},$

where $L_{m}$, $L_{p}$ and $L_{o}$ denote the loss terms for mask prediction,
foreground prediction, and objectness scoring, respectively. $\alpha$,
$\beta$, $\gamma$ and $\omega$ are the weights of the corresponding losses.
$m$ and $g$ represent the predicted masks and corresponding groundtruth,
respectively. $F$ and $G$ is the foreground prediction result and the
generated foreground groundtruth, while the estimated objectness score is
denoted with $s$. $v$ is a set of binary values that indicate whether each
mask is an instance. Before computing the $L_{m}$, matching between the set of
predicted masks and groundtruth has been done via the bipartite matching
algorithm defined in [6].

###  3.5 Extension to semi-supervised learning

Due to the ambiguity of the instance definition in OWIS, it is much harder for
the annotators to follow the annotation instruction, and this could make the
annotations for OWIS expensive. It is desirable if we can use unlabeled data
to help train OWIS models. In this regard, our proposed cross-task consistency
loss only requires the outputs of both predictors to have a consistent
relationship indicated in 1, and does not always need ground truth
annotations. Thus, we apply this loss to unlabeled data, which becomes semi-
supervised learning. Specifically, the easier-to-learn foreground prediction
branch is able to learn well through a few labeled images in the warm-up
stage. Then the resulted foreground map can serve as a constraint to optimize
the open-world mask predictions with the help of our cross-task consistency
loss, when the labels do not exist. In this way, our Semi-SOIS achieves a good
trade-off between the annotation cost and model accuracy.

Semi-supervised learning process. Given a labeled set
$D_{l}=\left\\{(x_{i},y_{i})\right\\}_{i=1}^{N_{l}}$ and an unlabeled set
$D_{u}=\left\\{x_{i}\right\\}_{i=1}^{N_{u}}$, our goal is to train an OWIS
model by leveraging both a large amount of unlabeled data and a smaller set of
labeled data. Specifically, we initially use $D_{l}$ to train the SOIS as a
warm-up stage, giving a good initialization for the model. We then jointly
train the OWIS model on the both labeled and unlabeled data. For the labeled
data, we employ the loss function defined in Eq 4. For the unlabeled data, we
apply only the cross-task consistency loss $L_{c}$.

##  4 Experiments

For demonstrating the effectiveness of our proposed SOIS, we compared it with
other fully-supervised methods through intra-dataset and cross-dataset
evaluations. We also performed ablation studies in these two settings to show
the effect of each component. Moreover, we apply the proposed cross-task
consistency loss for semi-supervised learning and test our method on the UVO
validation set.

###  4.1 Implementation details and evaluation metrics

#### Implementation details

Detectron2 [20] is used to implement the proposed SOIS framework, multi-scale
feature maps are extracted from the ResNet-50 [21] or Swin Transformer [22]
model pre-trained on ImageNet [23]. Our transformer encoder-decoder design
follows the same architecture as in Mask2Former [6]. The number of object
queries $M$ is set to 100. Both the ResNet and Swin backbones use an initial
learning rate of 0.0001 and a weight decay of 0.05. A simple data augmentation
method, Cutout [24], is applied to the training data. All the experiments have
been done on 8 NVIDIA V100 GPU cards with 32G memory.

#### Pseudo-labeling for COCO train set

Pseudo-labeling is a common way to handle incomplete annotations. To explore
the compatibility of our method and the pseudo-labeling operation, we employ a
simple strategy to generate pseudo-labels for unannotated instances in the
COCO train set [1] in our experiments. Specifically, we follow a typical self-
training framework, introducing the teacher model and student model framework
to generate pseudo-labels. These two models have the same architecture, as
shown in Figure 6, but are different in model weights. The weights of the
student model are optimized by the common back-propagation, while the weight
of the teacher model is updated by computing the exponential moving averages
(EMA) of the student model. During training, the image $i$ is first fed into
the teacher model to generate some mask predictions. The prediction whose
confidence is higher than a certain value would be taken as a pseudo-proposal.
The state $S_{ij}$ of the pseudo-proposal $p_{ij}$ is determined according to
Equation (8).

$\displaystyle S_{ij}=\begin{cases}\text{ True,
}\>\;\text{if}\>\;\text{argmax}(\varphi(p_{ij},g_{i}))\leqslant\varepsilon,\\\
\text{ False,}\>\;\text{otherwise,}\end{cases}$ (8)

in which $g_{i}$ means any ground truth instance in the image $i$. $\varphi$
denotes the IOU calculating function, and $\varepsilon$ is a threshold to
further filter the unreliable pseudo-proposals. Finally, pseudo-proposals with
states $True$ would be considered as reliable pseudo-labels. Here, the
confidence and IOU threshold $\varepsilon$ for selecting pseudo-labels are set
to 0.8 and 0.2, respectively. Then, we jointly use the ground truth and the
pseudo-labels to form the training data annotations. If a region is identified
as belonging to an instance in the pseudo-label, it will be considered as a
positive sample during training.

Table 1: Results of UVO-train $\rightarrow$ UVO-val intra-dataset evaluation.

Metric | Backbone | AP${}_{100}(\%)$ | APs(%) | APm(%) | APl(%) | AR100(%) | AR10(%)
---|---|---|---|---|---|---|---
MaskRCNN | R-50 | 13.41 | 4.91 | 12.33 | 17.45 | 22.77 | 20.01
LDET | R-50 | 16.25 | 3.27 | 13.58 | 22.93 | 35.64 | 23.73
Mask2Former | R-50 | 21.85 | 6.16 | 16.82 | 31.65 | 41.18 | 28.26
SOIS (Ours) | R-50 | 23.38 | 6.59 | 17.35 | 34.23 | 41.94 | 29.24
Mask2Former | Swin-B | 33.27 | 9.34 | 25.21 | 47.80 | 50.81 | 37.49
SOIS (Ours) | Swin-B | 38.02 | 12.31 | 28.64 | 53.22 | 54.74 | 41.78

#### Evaluation metrics

The Mean Average Recall (AR) and Mean Average Precision (AP) [1] are utilized
to measure the performance of approaches in a class-agnostic way.

###  4.2 Fully-supervised experimental setting

Table 2: Results of COCO2017-train(VOC) $\rightarrow$ COCO2017-val(none-VOC)
intra-set evaluation.

Metrics | AR100 | ARs | ARm | ARl
---|---|---|---|---
Mask2Former | 9.21 | 4.56 | 8.79 | 19.30
SOIS | 11.03 | 4.87 | 9.24 | 26.81

#### Intra-dataset evaluation

UVO is the largest open-world instance segmentation dataset. Its training and
test images are selected from the same domain, while they do not have any
overlap. Here, we perform the leaning process of SOIS on the UVO-train subset
and conduct the test experiments on the UVO-val subset. Besides, we split the
COCO dataset into 20 seen (VOC) classes and 60 unseen (none-VOC) classes. We
train a model only on the annotation of 20 VOC classes and test it on the 60
none-VOC class, evaluating its ability of discovering novel objects.

#### Cross-dataset evaluation

Open-world setting assumes that the instance can be novel classes in the
target domain. Therefore, it is essential for the OWIS method to handle the
potential domain gap with excellent generalization ability. Cross-dataset
evaluation, in which training and test data come from different domains, is
necessary to be conducted. Here, we first train the proposed SOIS model and
compared methods on the COCO-train subset, while testing them on the UVO-val
dataset to evaluate their generalizability. Then we extend the experiments to
an autonomous driving scenario, training the models on the Cityscapes [2]
dataset and evaluating them on the Mapillary [25].Cityscape have 8 foreground
classes , while Mapillary contains 35 foreground classes including vehicles,
animals, trash can, mailbox, etc.

Table 3: Results of COCO2017-train $\rightarrow$ UVO-val cross-dataset
evaluation.

Metric | Backbone | AR100 | AP100 | APs | APm | APl
---|---|---|---|---|---|---
MaskRCNN | R-50 | 38.17 | 19.05 | 6.27 | 13.15 | 28.05
LDET | R-50 | 42.63 | 21.27 | 5.66 | 17.52 | 18.38
GGN | R-50 | 43.30 | 20.30 | 8.70 | 18.20 | 27.30
Mask2Former | R50 | 48.71 | 25.24 | 6.46 | 16.09 | 40.37
SOIS (Ours) | R-50 | 51.28 | 27.62 | 7.80 | 18.61 | 43.42
Mask2Former | Swin-B | 51.38 | 28.16 | 7.29 | 18.91 | 45.48
SOIS(Ours) | Swin-B | 54.86 | 32.21 | 9.03 | 21.92 | 50.69

###  4.3 Fully-supervised experimental results

#### Intra-dataset evaluation

The results are illustrated in Table 1. The single-stage approaches based on
the mask classification framework perform better than other two-stage methods.
Among them, our proposed SOIS achieves a significant performance improvement
over the Mask2Former baseline, which is 4.75% in $AP_{100}$ and 3.93% in
$AR_{100}$ when using the Swin-B backbone. For VOC$\rightarrow$none-VOC
setting, the experimental results are shown in Table 2, which verified that
our proposed method can improve the performance for all instances, especially
large ones.

Table 4: Results of SOIS with SOLOV2 structure ( UVO-train$\rightarrow$ UVO-
val).

Metric | Backbone | AR100 | AP100 | APs | APm | APl
---|---|---|---|---|---|---
SOLO V2 | R-50 | 39.41 | 22.25 | 5.56 | 14.18 | 34.12
SOLO V2SOIS | R-50 | 42.52 | 25.04 | 6.77 | 16.90 | 38.33

#### Cross-dataset evaluation

For the COCO$\rightarrow$UVO task, according to Table 3, it is clear that the
proposed SOIS outperforms all previous methods, achieving a new state-of-the-
art $AR_{100}$ at 54.86% which is 11.56% higher than previous state-of-the-art
method GGN [4]. We also applied the proposed techniques to another classic
one-stage method SOLO V2 [26]. The experimental results in Table 4 show that
it improves $AR_{100}$ and $AP_{100}$ by 3.11% and 2.79% compared to SOLO V2.
For the Cityscape$\rightarrow$ Mapillary task, the overall $AP$ and $AR$ of
SOIS still surpass the performance of other state-of-the-art methods(in Table
8), which demonstrates the effectiveness of our proposed techniques. We show
some of the COCO$\rightarrow$UVO visualization results in Figure 7 to
qualitatively demonstrate the superiority of our method. Please refer to the
supplementary material for more qualitative examples.

(a) Groundtruth

(b) MaskRCNN

(c) LDET

(d) Mask2Former

(e) SOIS (Ours)

Figure 4: Visualization results of COCO$\rightarrow$UVO cross-dataset
evaluation. The predicted boxes of two-stage methods MaskRCNN and LDET are
also drawn. Proposed SOIS can discover both unlabeled object (first row) and
unseen class of instances (second row) as shown in red boxes.

###  4.4 Ablation study

We perform cross-dataset and intra-dataset ablation studies to analyze the
effectiveness of each component in the proposed SOIS, including the foreground
prediction branch and the cross-task consistency loss. We also try
combinations of the pseudo-label generation strategy and our cross-task
consistency loss to investigate the individual and synergetic effects of them.
Using the SwinB backbone, these models are trained on the COCO-train subset
and the UVO-train subset, respectively. The metrics reported in Table 5 are
tested on the UVO-val dataset.

Table 5: Ablation results of the proposed components by cross-dataset and
intra-dataset evaluations. Foreground prediction (FP), Cross-task consistency
(CTC) loss, Pseudo label (PL).

Component | Train on COCO | Train on UVO
---|---|---
FP | CTC loss | PL | AP100(%) | AR100(%) | AP100(%) | AR100(%)
|  |  | 28.65 | 51.54 | 35.12 | 51.39
✓ |  |  | 29.02 | 51.60 | 35.55 | 51.73
|  | ✓ | 30.09 | 52.97 | 32.94 | 51.64
✓ | ✓ |  | 31.39 | 53.83 | 38.02 | 54.74
✓ |  | ✓ | 30.17 | 52.98 | 33.35 | 50.90
✓ | ✓ | ✓ | 32.21 | 54.86 | 37.71 | 52.27

#### Effectiveness foreground prediction branch

Table 5 shows that although a separate foreground prediction branch can guide
the method to optimize towards the direction of discovering foreground pixels,
it only slightly boosts the performance.

#### Effectiveness of cross-task consistency loss

Cross-task consistency loss has a positive effect on both sparse annotated
(COCO) and dense annotated (UVO) training dataset. The values of $AP_{100}$
and $AR_{100}$ increase significantly ( 2.74% $\uparrow$ and 2.49% $\uparrow$
on COCO while 2.90% $\uparrow$ and 3.35%$\uparrow$ on UVO) after applying the
cross-task consistency loss as well as the foreground prediction branches
together. This result outperforms the SOIS counterpart with only pseudo-
labeling, showing our effectiveness. In addition, jointly utilizing our cross-
task consistency loss as well as the pseudo-labeling strategy leads to
performance improvements on two settings, which demonstrates the synergistic
effect of both approaches.

#### Effectiveness of pseudo-labeling

Pseudo-labeling is not always necessary and powerful for any types of
datasets. As shown in Table 5, the $AP_{100}$ and $AR_{100}$ of the COCO
trained model increase by 1.35% and 0.78%, respectively, after applying the
pseudo-label generation. However, pseudo-labeling causes a performance
degradation (e.g. 2.18%$\downarrow$ in $AP_{100}$) to a model trained in the
UVO dataset. Compared with COCO, the UVO dataset is annotated more densely. We
conjecture that the background annotations of UVO are more reliable than those
of COCO, where carefully selected pseudo-labels are more likely to represent
unlabeled objects. The generated pseudo-labels of UVO contain higher noises
than those of COCO. These additional noisy labels mislead the model training.

###  4.5 Semi-supervised learning experiment

Table 6: Results of our SOIS and classic semi-supervised method on UVO-val.

Training Data | UVO-train with 30% annotation
---|---
Method | Fully-SOIS30 | Mean Teacher | Pseudo Labeling | Semi-SOIS30
AP100(%) | 21.67 | 21.95 | 22.77 | 25.03
AR100(%) | 40.09 | 40.82 | 41.56 | 45.42

Table 7: Results of our SOIS and recent end to end method on UVO-val.

Training Data | UVO-train with 50% annotation
---|---
Method | LDET50 | Mask2Former50 | Fully-SOIS50 | Semi-SOIS50
AP100(%) | 10.61 | 19.49 | 22.86 | 25.22
AR100(%) | 25.08 | 38.08 | 41.44 | 47.56

#### Experimental setting

We have divided the UVO-train dataset into the labeled subset $D_{l}$ and the
unlabeled subset $D_{u}$. Semi-supervised model Semi-SOIS is optimized as
described in Section 3.6 on $D_{l}\cup D_{U}$, while the fully-supervised
method Fully-SOIS is trained merely on the $D_{L}$. To ensure the
comprehensiveness of the experiment, two different data division settings are
included in our experiments:{$D_{L}$=30%, $D_{u}$=70%} and {$D_{L}$=50%,
$D_{u}$=50%}. The backbone applied here is Swin-B. We also implemented the
classic Mean teacher model and a simple pseudo-label method based on the
Mask2Former to perform comparison.

Figure 5: Comparison between fully-SOIS and semi-SOIS

#### Results and analysis

As presented in Figure 5, the Semi-$SOIS_{50}$ model trained on the UVO with
50% annotated data outperforms the Semi-$SOIS_{30}$ model leaning with 30%
labeled training images. However, the performance increase between the
Semi-$SOIS_{30}$ and Semi-$SOIS_{50}$ is slight. In addition, Semi-$SOIS_{30}$
improves Fully-$SOIS_{30}$ by 3.36% and 5.33% in $AP_{100}$ and $AR_{100}$,
respectively. Compared to Fully-$SOIS_{50}$, Semi-$SOIS_{50}$ still achieves
significant advantages (2.36% in $AP_{100}$ and 6.12% in $AR_{100}$). These
results reflect that cross-task consistency loss has the ability to extract
information from unlabeled data and facilitates model optimization in the
semi-supervised setting. It is notable that the results of Semi-$SOIS_{30}$
are even better than those of Fully-$SOIS_{50}$. This illustrates that the
information dug out by the cross-task consistency loss from the remaining 70%
unlabeled data is more abundant than that included in 20% fully-labeled data.
Therefore, our algorithm can achieve better performance with fewer
annotations. This characteristic is promising in solving the OWIS problem. In
addition, we also compared the semi-$SOIS$ with classic semi-supervised method
and recent end to end segmentation method. The results in Table 4.5 and 4.5
show our advantages over the compared methods.

Table 8: Cross-set evaluation on autonomous driving scenes. Results of
Cityscapes $\rightarrow$ Mapillary.

Method | MaskRCNN | LDET | Mask2Former | OSIS(Ours)
---|---|---|---|---
AP(%) | 7.3 | 7.8 | 7.6 | 8.4
AR10(%) | 6.1 | 5.5 | 7.0 | 7.5

##  5 Conclusion

This paper proposes the first single-stage framework (SOIS) for the open-world
instance segmentation task. Apart from predicting the instance mask and
objectness score, our framework introduces a foreground prediction branch to
segment the regions belonging to any instance. Utilizing the outputs of this
branch, we propose a novel cross-task consistency loss to enforce the
foreground prediction to be consistent with the prediction of the instance
masks. We experimentally demonstrate that this mechanism alleviates the
problem of incomplete annotation, which is a critical issue for open-world
segmentation. Our extensive experiments demonstrate that SOIS outperforms
state-of-the-art methods by a large margin on typical datasets. We further
demonstrate that our cross-task consistency loss can utilize unlabeled images
to obtain some performance gains for a semi-supervised instance segmentation.
This is an important step toward reducing laborious and expensive human
annotation.

## Acknowledgments and Disclosure of Funding

Mike Zheng Shou is supported only by the National Research Foundation,
Singapore under its NRFF award NRF-NRFF13-2021-0008.

##  Appendix A Appendix

In this appendix, we provide the architecture of the foreground prediction
branch (in Figure 6) and detailed experimental settings first. Then some
annotations in UVO dataset are visualized in Figure 7 to show the challenges
of open world instance segmentation. Finally, additional visualization results
of proposed SOIS are shown in Figure 8.

Figure 6: Architecture of foreground prediction branch. Multi-scale features
extracted from backbone are fed into the feature fusing module to exchange and
fuse the multi-scale information. Then a fused feature is sent to the
prediction head to predict the final foreground map. Considering the
efficiency, we follow [27] to introduce the gOctConv [27] and PallMSBlock [27]
to perform feature fusing.

###  A.1 Detailed experimental settings

#### Implementation details

For feature extracting, we obtain the multi-scale features through a
sequential backbone network [22, 21], and FPN [28]. The multi-scale features
contain D-dimensional feature maps with resolutions of 1/4, 1/8, 1/16, and
1/32. In the pixel decoder module, six MSDeformAttn layers are employed, while
the transformer decoder have three layers with 100 queries by default.

In fully-supervised learning, the total loss $L_{f}$ can be formulated as:
$L_{f}=\alpha L_{m}+\beta L_{p}+\gamma L_{c}+\omega L_{o}$. We set the weight
$\alpha$ of mask loss ($L_{m}$) to 5.0, the weight $\beta$ of foreground loss
($L_{p}$) to 1.0, the weight $\gamma$ of cross-task consistency loss ($L_{c}$)
to 1.0 and the weight $\omega$ of objectness loss ($L_{o}$) to 2.0.

#### Training settings

Specifically, AdamW [29] optimizer and the step learning rate schedule are
applied to optimize our model. An initial learning rate of 0.0001 and a weight
decay of 0.05 are utilized for all backbones. We set a learning rate
multiplier of the backbone to 0.1 and we decay the learning rate at 0.9 and
0.95 fractions of the total number of training steps by a factor of 10. For
data augmentation, we use the large-scale jittering (LSJ) augmentation with a
random scale sampled from range 0.1 to 2.0 followed by a fixed size crop to
1024$\times$1024 on COCO dataset and 640$\times$640 on UVO dataset. Besides, a
Cutout [30] strategy that randomly cuts out a region of size [1/8$\cdot$w,
1/8$\cdot$h] to [1/3$\cdot$w, 1/3$\cdot$h] is introduced during training. On
COCO dataset, we train our models for $38\times 10^{4}$ iterations with a
batch size of 16, while on UVO dataset, we train our models for $12\times
10^{4}$ iterations with the same batch size.

SOIS training process with pseudo-labeling on COCO dataset

Data: Image dataset

Result: Proposed SOIS Model $M_{u}$

1 initialization the student model $M_{u}$, and teacher model
$M_{t}$=$M_{u}$.copy();

2 while  _Image $i$ $\notin$ $\varnothing$_ do

3 read image $i$ and corresponding groundtruth $gt_{i}$;

4 extract backbone feature $X_{i}$;

5 pred_masks $\leftarrow$ $M_{t}$.predictor($X_{i}$);

6 pseudo_proposals$\leftarrow$ filter_masks_with_confidence(pred_masks,
confidence_threshold);

7 pseudo labels $\leftarrow$ filter_masks_with_IOU(pseudo_proposals,
IOU_threshold);

8 training labels $\leftarrow$ merge($gt_{i}$, pseudo labels);

9 aug_data$\leftarrow$ Cutout($X_{i}$, training labels);

10 $M_{u}$ $\leftarrow$ $M_{u}$.training(aug_data);

11 $M_{t}$ $\leftarrow$ $M_{t}$.EMA_update($M_{t}$,$M_{u}$)

12 end while

Algorithm 1 SOIS training process with pseudo-labeling

Figure 7:  Visualizations of UVO annotations. It is notable that the same
class of object may be labeled as an instance or as background in different
images. (as shown in the area highlighted by the ellipse). This inconsistency
of annotations pose a great challenge to the algorithms.

Figure 8:  Visualizations results of our proposed SOIS in UVO dataset. SOIS
can discover many novel objects, as shown in regions in red boxes.

###  A.2 Visualization of annotations and our results on UVO dataset

Unlike in closed-world instance segmentation, where the object categories have
been clearly defined, instance definition in OWIS is much more ambiguous and
harder for annotators to follow. Inevitably, the instance annotation could
become inconsistent across images, as shown in Figure LABEL:fig:fig2. Our
method is motivated by this observation that the instance annotation in the
existing datasets is very noisy. Our solution to this issue is to introduce a
self-correcting mechanism to combat erroneous annotations, which provides
additional guidance to both prediction tasks when the noisy annotations fail
to provide correct supervision. The visualization results in Figure 7
demonstrate that our proposed SOIS can segment many novel objects that have
not been unseen in the training set.

## References

  * [1] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in European conference on computer vision, pp. 740–755, Springer, 2014.
  * [2] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and B. Schiele, “The cityscapes dataset for semantic urban scene understanding,” in Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
  * [3] W. Wang, M. Feiszli, H. Wang, and D. Tran, “Unidentified video objects: A benchmark for dense, open-world segmentation,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 10776–10785, 2021\.
  * [4] W. Wang, M. Feiszli, H. Wang, J. Malik, and D. Tran, “Open-world instance segmentation: Exploiting pseudo ground truth from learned pairwise affinity,” CVPR, 2022.
  * [5] K. Saito, P. Hu, T. Darrell, and K. Saenko, “Learning to detect every thing in an open world,” arXiv preprint arXiv:2112.01698, 2021.
  * [6] B. Cheng, I. Misra, A. G. Schwing, A. Kirillov, and R. Girdhar, “Masked-attention mask transformer for universal image segmentation,” 2022.
  * [7] K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-cnn,” in Proceedings of the IEEE international conference on computer vision, pp. 2961–2969, 2017.
  * [8] H. Chen, K. Sun, Z. Tian, C. Shen, Y. Huang, and Y. Yan, “Blendmask: Top-down meets bottom-up for instance segmentation,” in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 8573–8581, 2020.
  * [9] J. Dai, K. He, and J. Sun, “Instance-aware semantic segmentation via multi-task network cascades,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3150–3158, 2016.
  * [10] D. Bolya, C. Zhou, F. Xiao, and Y. J. Lee, “Yolact: Real-time instance segmentation,” in Proceedings of the IEEE/CVF international conference on computer vision, pp. 9157–9166, 2019.
  * [11] X. Wang, T. Kong, C. Shen, Y. Jiang, and L. Li, “Solo: Segmenting objects by locations,” in European Conference on Computer Vision, pp. 649–665, Springer, 2020.
  * [12] Y. Fang, S. Yang, X. Wang, Y. Li, C. Fang, Y. Shan, B. Feng, and W. Liu, “Instances as queries,” in Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6910–6919, 2021.
  * [13] B. Dong, F. Zeng, T. Wang, X. Zhang, and Y. Wei, “Solq: Segmenting objects by learning queries,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [14] N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko, “End-to-end object detection with transformers,” in European conference on computer vision, pp. 213–229, Springer, 2020.
  * [15] B. Cheng, A. Schwing, and A. Kirillov, “Per-pixel classification is not all you need for semantic segmentation,” Advances in Neural Information Processing Systems, vol. 34, 2021.
  * [16] Y. Du, W. Guo, Y. Xiao, and V. Lepetit, “1st place solution for the uvo challenge on video-based open-world segmentation 2021,” arXiv preprint arXiv:2110.11661, 2021.
  * [17] T. Vu, H. Jang, T. X. Pham, and C. Yoo, “Cascade rpn: Delving into high-quality region proposal network with adaptive convolution,” Advances in neural information processing systems, vol. 32, 2019.
  * [18] Z. Ge, S. Liu, F. Wang, Z. Li, and J. Sun, “Yolox: Exceeding yolo series in 2021,” arXiv preprint arXiv:2107.08430, 2021.
  * [19] F. Milletari, N. Navab, and S.-A. Ahmadi, “V-net: Fully convolutional neural networks for volumetric medical image segmentation,” in 2016 fourth international conference on 3D vision (3DV), pp. 565–571, IEEE, 2016.
  * [20] Y. Wu, A. Kirillov, F. Massa, W.-Y. Lo, and R. Girshick, “Detectron2,” https://github. com/facebookresearch/detectron2, 2019.
  * [21] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [22] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin transformer: Hierarchical vision transformer using shifted windows,” in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
  * [23] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in 2009 IEEE conference on computer vision and pattern recognition, pp. 248–255, Ieee, 2009.
  * [24] T. DeVries and G. W. Taylor, “Improved regularization of convolutional neural networks with cutout,” arXiv preprint arXiv:1708.04552, 2017.
  * [25] G. Neuhold, T. Ollmann, S. Rota Bulo, and P. Kontschieder, “The mapillary vistas dataset for semantic understanding of street scenes,” in Proceedings of the IEEE international conference on computer vision, pp. 4990–4999, 2017.
  * [26] X. Wang, R. Zhang, T. Kong, L. Li, and C. Shen, “Solov2: Dynamic and fast instance segmentation,” Proc. Advances in Neural Information Processing Systems (NeurIPS), 2020.
  * [27] S.-H. Gao, Y.-Q. Tan, M.-M. Cheng, C. Lu, Y. Chen, and S. Yan, “Highly efficient salient object detection with 100k parameters,” in European Conference on Computer Vision, pp. 702–721, Springer, 2020.
  * [28] T.-Y. Lin, P. Dollár, R. Girshick, K. He, B. Hariharan, and S. Belongie, “Feature pyramid networks for object detection,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2117–2125, 2017\.
  * [29] I. Loshchilov and F. Hutter, “Decoupled weight decay regularization,” arXiv preprint arXiv:1711.05101, 2017.
  * [30] T. DeVries and G. W. Taylor, “Improved regularization of convolutional neural networks with cutout,” arXiv preprint arXiv:1708.04552, 2017.


# On matrices potentially useful for tree codes
preliminary version

Pavel Pudlák Institute of Mathematics, Czech Academy of Sciences, Prague. The
author is supported by the project EPAC, funded by the Grant Agency of the
Czech Republic under the grant agreement no. 19-27871X, and the institute
grant RVO: 67985840.

###### Abstract

Motivated by a concept studied in [1], we consider a property of matrices over
finite fields that generalizes triangular totally nonsingular matrices to
block matrices. We show that (1) matrices with this property suffice to
construct good tree codes and (2) a random block-triangular matrix over a
field of quadratic size satisfies this property. We will also show that a
generalization of this randomized construction yields codes over quadratic
size fields for which the sum of the rate and minimum relative distance gets
arbitrarily close to 1.

##  1 Introduction

The problem of an explicit construction of good tree codes is an interesting
longstanding open problem. In [5] we showed that a good tree code can be
constructed from a triangular totally nonsingular matrix over a filed of
polynomial size. A _triangular totally nonsingular matrix_ 111Throughout this
note triangular means lower triangular. is a matrix $M$ such that every square
submatrix of $M$ whose main diagonal is in the lower triangle (we call such
submatrices _admissible_) is nonsingular. Note that only those minors can be
nonzero. Whether or not such matrices exist over polynomial size fields is an
open problem. In contrast, examples of such matrices over exponentially large
fields and fields of characteristic zero are well-known. The triangular Pascal
matrix is triangular totally nonsingular over rationals, in fact it is
triangular totally positive. Since the minors are at most exponentially large,
one can take the Pascal matrix modulo an exponentially large prime a get a
triangular totally nonsingular matrix over the corresponding prime field.
These matrices have been used in the so far best construction of tree codes
[3]. In [1] Ben Yaakov, Cohen and Narayanan report on computer experiments
that strongly suggest that subexponential primes do not suffice, which is also
conjectured in [4]. Therefore Ben Yaacov et. al [1] considered a weaker
property that Pascal matrices over small finite fields could satisfy and
proved that this property is sufficient for constructing good tree codes. They
conjectured that Pascal matrices have this property over polynomial size
fields and supported the conjecture by computing the smallest prime for
several small instances of the Pascal matrix.

Our aim in this note is, first, to show that a property slightly weaker than
the one considered in [1] suffices for constructing good tree codes and,
second, to prove that a random matrix having a certain pattern of zero and
nonzero elements over a field of quadratic size satisfies this property. Our
point is that one should not focus only on the Pascal matrix. The Pascal
matrix may have the required property but it may be very difficult to prove
it. Once we know that there are other matrices that satisfy our weaker
property, we can look for different constructions. E.g., constructions of
totally nonsingular matrices over linear size fields are well-known and we may
try to use them to construct matrices with the property that we propose here.

The concept that we propose in this note is a natural generalization of
triangular totally nonsingular matrices to block matrices. We only need
matrices consisting of blocks that are $2\times 1$ matrices (or, if you
prefer, column vectors of length 2). So $(2,1)$-block triangular matrices have
dimensions $2n\times n$. The property that we need is that all admissible
$(2,1)$-block triangular submatrices have full rank. In this note we only show
how to construct from these matrices tree codes with rate $1/3$ and minimum
relative distance $1/2$ with _polynomial size_ input and output alphabets, but
it is well-known that from any such code one can construct a tree code with
_constant size_ alphabets and positive rate and minimum distance.

The property studied in [1] can also be stated in terms of $(2,1)$-block
triangular matrices. Ben Yaacov et al. take the matrix of odd columns of the
triangular Pascal matrix. This matrix can be viewed as a $(2,1)$-block
triangular matrix. They conjecture that in this matrix all admissible
$(2,1)$-block triangular submatrices have a slightly stronger property than
full rank, possibly with some small exceptions.

In Section 4 we generalize the construction and show that there are linear
codes over quadratic fields such that the sum of the rate and relative minimum
distance is arbitrarily close to 1 (the Singleton bound). Whether or not one
can actually achieve the bound 1 with codes over subexponential size fields
remains an open problem.

In [4] Karingula and Lovett studied a somewhat related topic. They estimated
the probability that a random _integer_ matrix with entries in
$\\{-m,\dots,m\\}$ is singular. They conjectured that for $m$ bounded from
below by a sufficiently large polynomial in the dimension of the matrix, a
random triangular integer matrix is triangular totally nonsingular. In the
last section we propose a conjecture about certain random matrices that
implies the conjecture of Karingula and Lovett.222After we finished a draft of
this note we learned that Karingula and Lovett tried a similar approach.

##  2 Definitions and basic facts

###  2.1 Patterns

We will call a _pattern_ any matrix with entries $0$ and $*$. We say that a
matrix $M$ over a field is _consistent with a pattern_ $P$, if $M$ and $P$
have the same dimensions and $M$ has nonzero elements only where $P$ has
stars. We will only consider _left-bottom patterns_ (abbreviated by lb-
patterns) which are patterns in which every entry before or below an
occurrence of $*$ is also $*$. E.g., lower triangular matrices are matrices
that are consistent with the _triangular lb-patterns,_ which are the lb-
patterns consisting of a triangle of stars delimited by the main diagonal with
the rest filled with zeros. Triangular lb-patterns are, by definition, square
matrices. We will denote by $T_{n}$ the $n\times n$ triangular lb-pattern. Two
more important examples are _all-star patterns_ and _all-zero patterns_ which
are matrices where all entries are stars, respectively zeros

A _subpattern_ $P^{\prime}$ of a pattern $P$ is a submatrix of $P$; if $P$ is
an lb-pattern, then, clearly, $P^{\prime}$ is also an lb-pattern. We call an
lb-pattern $P$ _admissible_ , if it is a square matrix and has stars on the
main diagonal.

###### Fact 1

Let $P$ be a triangular lb-pattern and
$P^{\prime}=P[i_{1},\dots,i_{k}|j_{1},\dots,j_{k}]$ be the subpattern given by
rows $i_{1},\dots,i_{k}$ and columns $j_{1},\dots,j_{k}$. Then $P^{\prime}$ is
admissible iff $i_{1}\geq j_{1},\dots,i_{k}\geq j_{k}$.

###### Fact 2

Let $P$ be a square lb-pattern with $*$ in the upper left corner. Then either
$P$ is admissible, or $P$ can be decomposed into blocks

$P=\left[\begin{array}[]{c}\begin{array}[]{l|r}A{}&~{}O\end{array}\\\
\hline\cr Z\end{array}\right]$

where $A$ is an admissible pattern and $O$ is a zero pattern.

  * Proof.

Let $P$ be an $n\times n$ lb-pattern with $P_{1,1}=*$. If $P$ is not
admissible, take the largest $m$ such that $P[1,\dots,m|1,\dots,m]$ is
admissible. Such an $m$ exists, because the $P_{1,1}=*$. For this $m$,
$P_{m+1,m+1}=0$, hence $P[1,\dots,m+1|m+1,\dots,n]$ is a zero matrix (which is
a little bit more than what is stated in Fact).

###  2.2 Matrices

Given a matrix $M$ and a pattern $P$ defined on rows $i_{1},\dots,i_{k}$ and
columns $j_{1},\dots,j_{l}$, we will denote by
$M[P]:=M[i_{1},\dots,i_{k}|j_{1},\dots,j_{l}]$.

We say that an $n\times n$ matrix $M$ is _triangular totally nonsingular_ , if
for every admissible subpattern of the $T_{n}$ the corresponding submatrix of
$M$ is nonsingular. Since only those square matrices that are induced by
admissible patterns can be nonsingular, one often says “all submatrices of $M$
that _can be_ nonsingular _are_ nonsingular”.

We will now generalize the introduced concepts to block matrices. An
$(a,b)$-block matrix is a matrix $M$ whose entries are $a\times b$ matrices.
If $M$ is an $m\times n$ $(a,b)$-block matrix, we can forget the blocks and
view $M$ as an $am\times bn$ ordinary matrix; we will denote this matrix by
$M^{\flat}$. We will say that the _block dimensions of_ $M$ are $m\times n$.

We say that a block matrix is consistent with a pattern $P$, if all blocks
corresponding to zeros of $P$ are zero matrices. E.g., a lower triangular
block matrix of dimension $n$ is a matrix is matrix consistent with $T_{n}$.

We want to generalize triangular totally nonsingular matrices to block
matrices. In this note we only need it for matrices with blocks $2\times 1$.
The generalization is straightforward except that we have to decide what to
use instead of nonsingularity. We will use full rank.

###### Definition 1

We say that a triangular $(2,1)$-block matrix $M$ is a _totally full rank_
block matrix, if for every admissible $(2,1)$-block submatrix $N$, $N^{\flat}$
is a full rank matrix.

In [1] the authors considered a stronger condition: from each pair of
consecutive rows (odd and even) of $N^{\flat}$ one can choose one row so that
the resulting matrix is nonsingular.

###  2.3 Linear tree codes

We consider _truncated tree codes_ , which means that the code-words have some
fixed finite length called the length of the code. We will omit the
specification “truncated” in the sequel.

Linear tree codes have generating matrices that are of the form $M^{\flat}$
for some $(a,b)$-block triangular matrix $M$ with $a>b$, see [5]. Here we
consider lower triangular matrices, so the code is generated by the columns of
$M^{\flat}$. In Section 3 we will use $(3,1)$-block triangular generating
matrices which define codes of rate $1/3$. We will view the code-words also as
$(3,1)$-block matrices, or more precisely, $(3,1)$-block column vectors. The
_block length_ of these vectors is the number of blocks.

Let $C$ be a code of block-length $n$. The _minimum relative distance_ is
defined as follows. Take a nonzero vector $\vec{c}\in C$ and let $k$ be the
index of the first nonzero block. The relative weight of $C$ is

$\min_{0\leq l\leq n-k}\frac{\mbox{the number of nonzero blocks between $k$
and $k+l$}}{l+1}.$

The minimum relative distance of $C$ is the minimum of the relative weights of
nonzero code-words.

##  3 Two observations

###### Proposition 3.1

Given a triangular totally full rank $(2,1)$-block matrix $M$ of block-
dimension $n$ over a field $F$, one can construct a linear tree code $C$ over
$F$ such that

  1. 1.

$C$ has block length $n$;

  2. 2.

the blocks of code-words have length $3$, thus the rate of the code is $1/3$;

  3. 3.

the minimum relative distance is $>1/2$.

  * Proof.

The proof uses an idea of [2] by which Bhandari and Harsha proved that
triangular totally nonsingular matrices can be used to construct tree codes
that match the Singleton bound.333Our original proof in [5] was different and
gave a stronger result. The difference is that we proved a bound on the
relative number of nonzero _entries_ in a nonzero code word, which in general
may be much smaller than the relative number of nonzero _blocks_.

Let $M$ be given. Let $N$ be a $(3,1)$-block triangular matrix obtained from
$M$ by interleaving $M$ with the identity matrix. This means that we extend
every $(2,1)$-block of $M$ to a $(3,1)$-block by adding a $0$ or $1$ at the
top as follows. We add $1$s to blocks on the main diagonal and $0$s elsewhere.
Consider the tree code generated by the columns of $N$.

The added 0s and 1s ensure that the coding function is 1-1. We only need to
show the lower bound on the minimum distance. Let
$\vec{c}_{j_{1}},\dots,\vec{c}_{j_{k}}$ be columns of $N$ generating a nonzero
code-word $\vec{c}$ (a column vector) using some nonzero coefficients. The
condition that we have to verify depends on principal submatrices of $N$ which
have the same properties as $N$. Therefore we may assume w.l.o.g. that
$j_{1}=1$, i.e., $\vec{c}_{j_{1}}$ is the first column of $N$ and consider how
many nonzero elements has the entire vector $\vec{c}$.

We will consider two cases:

1\. $k>n/2$. Then we are done—the 1s of the identity matrix produce the $k$
nonzero blocks in $\vec{c}$.

2\. $k\leq n/2$. Let $S$ be the indices of the $(3\times 1)$-blocks of
$\vec{c}$ that are zero. We need to show $|S|<n/2$. So suppose this is not the
case. Then $|S|\geq n/2\geq k$. Consider the block submatrix $N[S|i_{1}\dots
i_{k}]$. Let $K$ be this matrix with rows corresponding to the identity matrix
omitted. Let $K^{\prime}$ be the submatrix of $K$ with only the first $2k$
rows. So $K^{\prime}$ is a $(2\times 1)$-block square submatrix of $M$.
$K^{\prime}$ itself may not be admissible, but we know that the elements in
the first column are nonzero and thus we may use Fact 2. According to this
fact some left upper part of $K^{\prime}$ is an admissible submatrix
$K^{\prime\prime}$ and there are zeros to the right of it. The columns of
$K^{\prime\prime}$ sum to a zero vector, because the columns of
$N[S|i_{1}\dots i_{k}]$ sum to a zero vector. But this is in contradiction
with the assumption that $M$ is a triangular totally full rank $(2,1)$-block
matrix. Hence $|S|<n/2$, which is the number of zero blocks in $\vec{c}$.

###### Proposition 3.2

For every $n\geq 1$ and every field $F$, if $|F|\geq 2n^{2}$, then there
exists a $(2,1)$-block-triangular totally full rank matrix $M$ over $F$ of
block-dimension $n$. Moreover, for finite fields, if $|F|\geq\omega(n^{2})$,
then the probability that a random matrix has this property tends to $1$ with
$n\to\infty$.

Proof. It is well-known that the triangular Pascal matrix is triangular
totally nonsingular in $\mathbb{R}$. From this, we get the desired matrix $M$
for fields of characteristic 0 by omitting even columns. So we only need to
consider finite fields.

Let $F$ be a finite field and $q=|F|$. We need to estimate probabilities of
random matrices consistent with $(2,1)$-block-admissible patterns. These are
patterns that arise from admissible patterns by duplicating the entries to get
$(2,1)$-blocks. In the rest of the proof, we will omit the specification
$(2,1)$ and simply say “block-admissible patterns”. The reader should keep in
mind that these patterns and matrices are now $2k\times k$ for some $k$. We
will denote by $E$ the elementary admissible pattern
$\left[\begin{array}[]{c}*\\\ \end{array}\right]$. For a block-admissible
pattern $P$ larger than $E$, we will denote by $P^{-}$ the pattern $P$ with
the first two rows and the first column omitted; thus $P^{-}$ has the block-
dimension one less than $P$. The pattern $P^{-}$ is, clearly, also block-
admissible. We will denote by $\phi$ the property that a matrix has full rank.

For a block-admissible pattern $P$ with some zeros, the probability that a
random matrix consistent with $P$ does not have full rank may not be
exponentially small; in fact, it may be as high as $q^{-2}$. Therefore we will
use conditional probabilities.

###### Claim 1

Let $P$ be a block-admissible pattern larger than $E$. The probability that a
random $2k\times k$ matrix $M$ consistent with $P$ does not have full rank
under the condition that $M[P^{-}]$ has full rank is $q^{-k-1}$.

  * Proof.

If the last $k-1$ columns are independent, then the matrix does not have full
rank iff the first column is dependent on the last ones. This probability is
equal to the probability that the first column is in the linear space spanned
by the last ones, which is $q^{k-1}/q^{2k}$.

###### Claim 2

Let $T^{2}_{n}$ be the $2n\times n$ block-triangular pattern. Let $M$ be a
random matrix over a finite field $F$ consistent with $T^{2}_{n}$. Then the
probability that for some block admissible subpattern $P$ of $T^{2}_{n}$, the
matrix $M[P]$ does not have full rank is bounded by

$\leq\sum_{E}\mathop{\rm Prob}\nolimits[\neg\phi(M[E])]+\sum_{P}\mathop{\rm
Prob}\nolimits[\neg\phi(M[P])\wedge\phi(M[P^{-}])],$ (1)

where the first sum is over all elementary admissible subpatterns $E$ of
$T^{2}_{n}$ and the second sum is over all block-admissible subpatterns $P$
larger than $E$.

  * Proof.

Suppose that there exists an admissible subpattern $P$ of $T^{2}_{n}$ such
that $M[P]$ does not have full rank. Consider such a $P$ with the least
dimension. Then $P$ is either $E$, or $P$ is larger than $E$ and $M[P^{-}]$
does not have full rank. Hence the bound follows by the union bound.

To prove the proposition, we need to show that for a finite field $F$ with
$|F|\geq 2n^{2}$, the probability that for some block admissible pattern $P$,
the matrix $M[P]$ is not full rank is less than 1. We observe that
$\mathop{\rm
Prob}\nolimits[\neg\phi(M[P])\wedge\phi(M[P^{\prime}])]\leq\mathop{\rm
Prob}\nolimits[\neg\phi(M[P])|\phi(M[P^{\prime}])]$. By Claim 1, the latter
probability is $q^{-k-1}$. We also have $\mathop{\rm
Prob}\nolimits[\neg\phi(M[E])]=q^{-2}$. To bound the sum in (1), we will
estimate the number of block-admissible patterns of dimensions $2k\times k$ by
$\leq\binom{n}{k}^{2}$ and use the assumption $q\geq 2n^{2}$. Thus we get

$\leq\sum_{k=1}^{n}\binom{n}{k}^{2}\cdot
q^{-k-1}\leq\sum_{k=1}^{n}\left(\frac{n^{2}}{q}\right)^{-k}\leq\sum_{k=1}^{n}2^{-k}<1.$

Clearly, the estimate goes to 0 when $q\geq\omega(n^{2})$.

##  4 A generalization

We will now generalize the randomized construction from the previous section
and show that the sum of the rate and relative minimum distance may be
arbitrarily close to 1 for fields of quadratic size. To this end we need to
consider more general linear codes.

Let $F$ be a field and let $s>t\geq 1$ be fixed constants. Let $N$ be an
$(s,t)$-block triangular matrix of block dimension $n$ (thus $N^{\flat}$,
which is $N$ with blocks forgotten, has dimensions $sn\times tn$). If $N$
satisfies a certain condition, we can use $N$ to define a tree code
$C:(F^{t})^{n}\to(F^{s})^{n}$ as follows. For an input $\vec{x}\in(F^{t})^{n}$
we take $\vec{x}^{\flat}$ (which is $\vec{x}$ with blocks forgotten), multiply
it by $N^{\flat}$, and then we introduce blocks of length $s$ on the vector
$N^{\flat}\vec{x}^{\flat}$. Deleting and introducing blocks may look as an
unnecessary complication, but the point is that the input alphabet are vectors
of length $t$ and the output alphabet are vectors of length $s$.

For the mapping $C$ to be a tree code, it is necessary and sufficient that the
blocks on the diagonal of $N$ are full rank matrices. Further, one can always
put the matrix into the _normal form_ in which blocks on the main diagonal are
matrices starting with the $s\times s$ identity matrix and the blocks outside
are matrices starting with $s\times s$ zero matrix. Thus in order to define
such a code we only need a suitable $(s-t,t)$-block triangular matrix. The
minimum distance will depend on the properties of this matrix; the rate is
always $t/s$. We will call codes defined above _$(s,t)$ -codes._

###### Proposition 4.1

For every numbers $t$ and $n$ and every field $F$, $|F|\geq 2n^{2}$, there
exists a linear $(2t+1,t)$-code with rate $\frac{t}{2t+1}$ and minimum
relative distance $\geq 1/2$. Thus the sum of the rate and relative minimum
distance is $\geq 1-\frac{1}{4t+2}$.

The bound on the size of the field does not depend on $t$, but note that the
sizes of the input and output alphabets increase with $t$.

  * Proof.

The proof follows the lines of of the proof of Proposition 3.2 with
appropriate changes. First we will show that a random $(t+1,t)$-block
triangular matrix over a field $F$, $|F|\geq 2n^{2}$ is totally full rank. To
this end we need to estimate:

    1. 1.

the probability that a random $(t+1)\times t$ matrix is nonsingular, and

    2. 2.

for random $(t+1)k\times tk$ matrices $M$, where $k>1$, the conditional
probability

$\mathop{\rm Prob}\nolimits[M\mbox{ nonsingular }|\
M[t+2,\dots,(t+1)k|t+1,\dots,tk]\mbox{ nonsingular }].$

One can show using elementary calculations that the first probability is
$<q^{-1}$ and the second one is $<q^{-k}$, where $q=|F|$. Hence the same
computation as in the proof of Proposition 3.2 shows that $M$ is
$(t+1,t)$-block triangular totally nonsingular with positive probability.

From $M$ we get a generating matrix in the normal form by extending the
$(t+1,t)$-blocks with zero and identity $t\times t$ matrices. The resulting
$(2t+1,t)$-block matrix generates a tree code with rate $t/(2t+1)$. It remains
to show that the minimum relative distance of this code is $\geq 1/2$. The
proof of this bound is a literal translation of the proof of Proposition 3.1.

In order to see that the bound on the sum of the rate and minimum relative
distance approaches the best possible value, we will check _the Singleton
bound for linear tree codes._ It does not hold exactly, only _asymptotically_.

###### Proposition 4.2

For every $s>t>0$, there exists $c_{s,t}>0$ such that for every $n$ and every
linear $(s,t)$-code of length $n$ the sum of the rate $r$ and the minimum
relative distance $\delta$ satisfies

$r+\delta\leq 1+1/c_{s,t}n.$

  * Proof.

Let $M$ be a $(s,t)$ block matrix generating a code of block length $n$.
Assume that $M$ is in the normal form defined above. Take the first $k$ block
columns of $M$, where $k$ will be determined later, and $k+l$ block rows where
$l$ the largest integer such that $(s-t)l<kt$. From this $k+l\times k$ matrix
we only take the bottom $l$ block rows and denote this matrix by $N$. If we
forget the block structure, the resulting matrix $N^{\flat}$ has dimensions
$sl\times tk$. In $N$ every $(s,t)$-block is off-diagonal, hence starts with
$t$ rows of zeros. Thus $N^{\flat}$ has $tl$ rows of zeros and $(s-t)l$
possibly nonzero rows. For we assume that $(s-t)l<kt$, there exists a nonzero
vector $\vec{x}$ such that $N^{\flat}\vec{x}=\vec{0}$. Let $\vec{y}^{\
\flat}:=M^{\flat}\vec{x}$ and let $\vec{y}$ be the $s$-block vector obtained
from $\vec{y}^{\ \flat}$ by introducing the blocks. Since $\vec{x}$ is
nonzero, at least one of the first $k$ blocks of $\vec{y}$ are nonzero. On the
other hand, the last $l$ blocks are zero. Hence the relative weight
$\delta_{\vec{y}}$ of $\vec{y}$ is at most $k/(k+l)$. The condition
$(s-t)l<kt$ is equivalent to $(s-t)l\leq kt-1$. Thus we have

$\delta_{\vec{y}}\leq\frac{k}{k+\frac{kt-1}{s-t}}=\frac{1}{1+\frac{t-\frac{1}{k}}{s-t}}=\frac{s-t}{s-\frac{1}{k}}.$

This gives the upper bound

$r+\delta\leq\frac{t}{s}+\frac{s-t}{s-\frac{1}{k}}=1+\frac{1-\frac{t}{s}}{sk-1}.$

One can easily check that the largest $k$ that we can take, which is the
largest $k$ such that $k+l\leq n$, is a positive fraction of $n$.

##  5 Integer triangular totally nonsingular matrices

While probabilistic arguments seem to fail to prove the existence of
triangular totally nonsingular matrices over polynomially large fields, it is
possible that they may be used for triangular totally nonsingular matrices
over integers with polynomially large entries. Karingula and Lovett [4]
conjectured that for a sufficiently large polynomial $p(n)$, a random
triangular integer matrix with entries in $[-m,m]$, $m\geq p(n)$, is with high
probability totally nonsingular. (High probability only means $\geq
1-1/m^{\alpha}$ for some constant $\alpha>0$.) In this section we will state a
conjecture that implies the conjecture of Karingula and Lovett.

An $n\times n$ lb-pattern $P$ is called _reducible_ if for some $k$, $1\leq
k\leq n$, the subpattern $P[1,2,\dots,k|k+1,k+2,\dots,n]$ is an all-zero
pattern; otherwise it is called _irreducible_. Equivalently, an lb-pattern $P$
is irreducible iff $P_{i,i+1}=*$ for all $i=1,\dots,n-1$.

###### Conjecture 1

There exists an $\varepsilon>0$ and $c$ such that for every $n$, every $m\geq
n^{c}$, and every $n\times n$ irreducible lb-pattern $P$, random matrices $M$
with entries in $[-m,m]$ consistent with $P$ satisfy

$\mathop{\rm Prob}\nolimits[M\mbox{ is singular }|\
M[1,2,\dots,n-1|2,3,\dots,n]\mbox{ is nonsingular }]<m^{-\varepsilon n}.$

If the conjecture is not true, it will most likely fail on the minimal
irreducible lb-patterns. These are the patterns $P$ such that $P_{ij}=0$ iff
$i+1<j$. For a matrix $M$ consistent with such a pattern, the condition that
$M[1,2,\dots,n-1|2,3,\dots,n]$ is nonsingular is equivalent to the condition
that $M_{i,i+1}\neq 0$ for all $1\leq i\leq n-1$, because then the subpattern
$P[1,2,\dots,n-1|2,3,\dots,n]$ is triangular.

For an $n\times n$ pattern $P$, we will denote by
$P^{*}:=P[1,2,\dots,n-1|2,3,\dots,n]$. If $P$ is irreducible, then $P^{*}$ is
admissible. If $P$ is admissible, then the main diagonal can be covered by
disjoint irreducible principal subpatterns $P_{1},\dots,P_{m}$ (we allow
$m=1$). We will call $P_{1},\dots,P_{m}$ the _decomposition_ of $P$. We will
use the following fact.

###### Fact 3

Let $P$ be an admissible pattern and $P_{1},\dots,P_{m}$ its decomposition.
Then a matrix $M$ consistent with $P$ is nonsingular iff all submatrices
$M[P_{1}],\dots,M[P_{m}]$ are nonsingular.

###### Proposition 5.1

If the conjecture above holds true, then for some $c$, there exist $n\times n$
triangular totally nonsingular integer matrices with entries in
$[-n^{c},n^{c}]$ for every $n\geq 1$. Moreover, if $c$ is sufficiently large,
the probability that a random triangular matrix is totally nonsingular tends
to $1$ with $n\to\infty$.

  * Proof.

The proof is based on the same idea as the one of Proposition 3.2.

By Fact 3, a triangular matrix $M$ is totally nonsingular iff for every
irreducible subpattern $P$ of $T_{n}$, $M[P]$ is nonsingular. Suppose $M$ not
totally nonsingular and let $P$ be an irreducible subpattern of $T_{n}$ of the
smallest dimension such that $M[P]$ is singular. Then we there are two cases.

    1. 1.

$P$ is a pattern with a single entry, and $M[P]=0$, or

    2. 2.

$P$ is larger. In this case let $P^{*}_{1},\dots,P^{*}_{m}$ be the
decomposition of $P^{*}$ into irreducible patterns. Since
$P^{*}_{1},\dots,P^{*}_{m}$ are smaller than $P$, $M[P^{*}_{i}]$ are
nonsingular. Hence $P^{*}$ is also nonsingular.

Thus we can bound the probability that $M$ is not totally nonsingular by

$\sum_{i\geq j}\mathop{\rm Prob}\nolimits[M_{i,j}=0]+\sum_{P}\mathop{\rm
Prob}\nolimits[M[P]\mbox{ is singular }\wedge\ M[P^{*}]\mbox{ is nonsingular
}],$

where the second sum is over all irreducible subpatterns of $T_{n}$ of
dimensions $\geq 2$. The rest of the proof is a computation similar to the one
in the proof of Proposition 3.2, so we leave it to the reader.

## References

  * [1] I. Ben Yaacov, G. Cohen, and A. K. Narayanan: Candidate Tree Codes via Pascal Determinant Cubes. Electron. Colloquium Comput. Complex. 27: 141 (2020).
  * [2] S. Bhandari and P. Harsha: A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet. arXiv:2002.08231 (2020)
  * [3] G. Cohen, B. Haeupler, and L. J. Schulman: Explicit binary tree codes with polylogarithmic size alphabet. STOC 2018: 535-544
  * [4] S. R. Karingula and S. Lovett: Codes over integers, and the singularity of random matrices with large entries. arXiv:2010.12081 (2020).
  * [5] P. Pudlák: Linear tree codes and the problem of explicit constructions. Linear Algebra and its Applications 490, 2016, 124-144.