figuret

# Any-Shot Object Detection

Shafin Rahman∗†§, Salman Khan‡, Nick Barnes∗, Fahad Shahbaz Khan‡
∗Australian National University, †North South University, §Data61-CSIRO
‡Inception Institute of Artificial Intelligence
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Previous work on novel object detection considers zero or few-shot settings
where none or few examples of each category are available for training. In
real world scenarios, it is less practical to expect that ‘ _all_ ’ the novel
classes are either unseen or have few-examples. Here, we propose a more
realistic setting termed ‘ _Any-shot detection_ ’, where totally unseen and
few-shot categories can simultaneously co-occur during inference. Any-shot
detection offers unique challenges compared to conventional novel object
detection such as, a high imbalance between unseen, few-shot and seen object
classes, susceptibility to forget base-training while learning novel classes
and distinguishing novel classes from the background. To address these
challenges, we propose a unified any-shot detection model, that can
concurrently learn to detect both zero-shot and few-shot object classes. Our
core idea is to use class semantics as prototypes for object detection, a
formulation that naturally minimizes knowledge forgetting and mitigates the
class-imbalance in the label space. Besides, we propose a rebalanced loss
function that emphasizes difficult few-shot cases but avoids overfitting on
the novel classes to allow detection of totally unseen classes. Without bells
and whistles, our framework can also be used solely for Zero-shot detection
and Few-shot detection tasks. We report extensive experiments on Pascal VOC
and MS-COCO datasets where our approach is shown to provide significant
improvements.

##  1 Introduction

Traditional object detectors are designed to detect the categories on which
they were originally trained. In several applications, such as self-driving
cars, it is important to extend the base object detector with novel categories
that were never seen before. The current ‘novel’ object detection models
proposed in the literature target either of the two distinct settings, _Zero-
shot detection_ (ZSD) and _Few-shot detection_ (FSD). In the former setting,
it is assumed that totally unseen objects appear during inference and a model
must learn to adapt for novel categories using only their class description
(semantics). In the latter setting, a small and fixed-number of novel class
samples are available for model adaptation. However, in a practical scenario,
restricting the novel classes to be always unseen (with zero visual examples)
or always with few-shot examples can limit the generality of the model.

Figure 1: (a) A traditional object detection method only detects seen objects.
In the same vein, zero and few-shot object detection methods can detect (b)
unseen or (c) few-shot objects. (d) Our proposed Any-shot detection method can
_simultaneously_ detect seen, unseen and few-shot objects.

In a real-world scenario, both unseen and few-shot classes can be
simultaneously of interest. Moreover, we may encounter a few examples of a
novel class that was previously supposed to be unseen. In such a case, an
adaptive model must leverage from new information to improve its performance
in an online fashion. To address these requirements, we introduce a new ‘
_Any-shot Detection_ ’ (ASD) protocol where a novel class can have zero or a
few training examples. Since, the existing object detection models can either
work for zero-shot or few-shot settings, we develop a unified framework to
address the ASD problem (see Fig. 1). Remarkably, since the ASD task sits at
the continuum between ZSD and FSD, our model can be directly applied to both
these problems as well.

The ASD task poses new challenges for novel object detection. First, a high
data imbalance between unseen, few-shot and seen classes can lead to a biased
detection model. Additionally, the fine-tuning performed on few-shot examples
can lead to forgetting previously acquired knowledge, thereby deteriorating
model performance on seen and unseen classes. To overcome these challenges, we
propose to learn a mapping from the visual space to the semantic space where
class descriptors serve as fixed prototypes. The semantic prototypes in our
approach encode inherent class relationships (thus enabling knowledge transfer
from the seen to the unseen), helps us disentangle totally unseen concepts
from the background and can be automatically updated to align well with the
visual information. Besides, we introduce a novel rebalancing loss function
for the fine-tuning stage that functions on few-shot examples. This loss
serves two objectives, i.e., to focus on the errors made for few-shot classes
and at the same time avoid overfitting them so that it remains generalizable
to totally unseen categories.

Our main contributions are:

  * •

A unified framework that can accommodate ZSD, FSD, ASD and their generalized
settings.

  * •

Learning with semantic class-prototypes that are well aligned with visual
information and help minimize forgetting old concepts.

  * •

An end-to-end solution with a novel loss function that rebalances errors to
penalize difficult cases yet remains generalizable to unseen objects.

  * •

Extensive experiments with new ASD setup, as well as comparisons with
traditional FSD and ZSD frameworks demonstrating significant improvements.

##  2 Related Work

N-shot recognition: There exist three categories of methods for n-shot
recognition. The first body of work targets only zero-shot recognition (ZSR)
tasks [39]. They perform training with seen data and test on unseen (or
unseen+seen) data. To relate seen and unseen classes, they use semantic
embeddings e.g., attributes [11] or word vectors [21, 22]. The ZSR task has
been investigated under popular themes such as transduction [35, 42], domain
adaptation [16, 42], adversarial learning [40] and class-attribute association
[2, 1]. The second body of work targets only few-shot recognition (FSR) task
[7]. This task leverages few labeled examples to classify novel classes. Most
popular methods to solve FSR are based on meta-learning where approaches
perform metric learning to measure the similarity between input and novel
classes [37, 34, 28], adapt the meta-learner by calculating gradient updates
for novel classes [28] or predict the classifier weights for novel classes
[23]. The third body of work addresses both zero and few-shot learning tasks
together [32, 41, 26, 36]. These approaches are the extended version of ZSR or
FSR methods that consider word vectors to accommodate both problems within a
single framework. Our current work belongs to the third category, but instead
of a recognition task, we focus on the detection problem, that is
significantly more challenging.

Zero-shot detection: Different from traditional object detection (where only
seen objects are detected), ZSD aims to detect both seen and/or unseen
objects. Pioneering works on ZSD attempt to extend established object
detection methods to enable ZSD. For example, [3], [9, 43] and [27] employ
pre-computed object proposals [44], YOLOv2 [29] and Faster-RCNN [30] based
methods for ZSD, respectively. Recent methods for ZSD employ specialized
polarity loss [24], explore transductive settings [25] and use raw textual
description instead of only class-names [18]. All the above methods focus on
only ZSD and Generalized ZSD tasks but cannot accommodate FSD scenario when
new instances of unseen images become available. In this paper, we propose a
method that can perform ZSD, FSD, and ASD tasks seamlessly, including their
generalized cases.

Figure 2: The any-shot object detection (ASD) problem has not been addressed
in the literature before. Importantly, an ASD system can automatically perform
both ZSD and FSD, which no prior approach can simultaneously offer.

Few-shot detection: FSD methods attempt to detect novel classes for which only
a few instances (1-10) are available during the inference stage [10, 38].
Among the early attempts of FSD, [5] proposed a regularizer that works on
standard object detection models to detect novel classes. Later, [15] proposed
a distant metric learning-based approach that learned representative vectors
to facilitate FSD. The drawback of the above FSD methods is that they cannot
handle seen/base classes during test time. Recently, [14] proposed to train a
base network with seen data and then fine-tune it by meta-network learning
that predicts scores for both seen and novel classes by re-weighing the base
network features. This approach can perform generalized FSD but cannot
accommodate ZSD or ASD scenario. In this paper, we address the mentioned gap
in the literature.

##  3 Novel Object Detection

Novel object detection refers to enhancing the ability of a traditional object
detector model to detect a new set of classes that were not present during
training. We propose a unified Any-shot Detection (ASD) setting111Our any-shot
detection setting is different from [41], which considers zero and few-shot
problems _separately_ for a simpler _classification_ task. where novel classes
include both few-shot and unseen (zero-shot) classes. This is in contrast to
the existing works on novel object detection that treat zero and few-shot
detection in an isolated manner. In the absence of the unseen class and few-
shot classes, our problem becomes identical to a conventional FSD and ZSD
problem, respectively. In this way, our proposed ASD settings unifies ZSD and
FSD in a _single_ framework.

###  3.1 Problem Formulation

Assume a total of ${{C}}$ object classes are present in a given test set that
need to be detected. Out of these, ${{S}}(>0)$ seen classes have many,
${{Q}}(\geq 0)$ few-shot classes have few and ${{U}}(\geq 0)$ unseen classes
has no examples available in the training dataset and
${{C}}={{S}}{+}{{Q}}{+}{{U}}$. Here, ${{T}}={{Q}}{+}{{U}}$ represents the
total number of novel classes that become available during the inference
stage. For each class, a semantic description is available as a
$d$-dimensional embedding vector. The semantic embeddings of all classes are
denoted by
$\bm{W}=[\bm{W}_{s},\bm{W}_{f},\bm{W}_{u}]\in\mathbb{R}^{d\times{{C}}}$, where
$\bm{W}_{s}\in\mathbb{R}^{d\times{{S}}}$,
$\bm{W}_{f}\in\mathbb{R}^{d\times{{Q}}}$ and
$\bm{W}_{u}\in\mathbb{R}^{d\times{{U}}}$ are semantic vectors for seen, few-
shot and unseen classes, respectively.

The base training set ($\mathcal{D}_{tr}$) contains $N_{tr}$ images with
instances from ${{S}}$ seen classes. Each training image $\bm{I}$ is provided
with a set of bounding boxes, where each box $\textbf{b}_{tr}$ is provided
with a seen label $\textbf{y}_{tr}\in\\{0,1\\}^{S}$. Similarly, when
${{Q}}{>}0$, we have a fine-tuning dataset ($\mathcal{D}_{ft}$) with $N_{ft}$
images containing instances from both seen and few-shot classes for which
bounding box $\textbf{b}_{ft}$ and class label
$\textbf{y}_{ft}\in\\{0,1\\}^{C}$ annotations are present. During inference,
we have a testing dataset $\mathcal{D}_{ts}$ with $N_{ts}$ images where each
image can contain any number of seen and novel class objects (see Fig. 3).

Our task is to perform any-shot detection, defined as:

######  Definition 3.1.

_Any-shot detection:_ When ${{Q}}{>}0$ and ${{U}}{>}0$, predict object labels
and associated bounding boxes for ${{T}}$ novel classes, that include both
zero and few-shot classes.

In comparison, the traditional zero and few-shot problems can be defined as:
(a) Few-shot detection: When ${{Q}}{>}0$ but ${{U}}{=}0$, predict object
labels and associated bounding boxes for all ${{Q}}$ classes. (b) Zero-shot
detection: When ${{Q}}{=}0$ but ${{U}}{>}0$, predict object labels and
associated boxes for all ${{U}}$ classes. Note, if ${{Q}}{=}{{U}}{=}0$ then
the problem becomes equivalent to a traditional detection task.

Figure 3: An overview of Any-shot Detection setting.

We also study the generalized ASD problem defines as:

######  Definition 3.2.

_Generalized any-shot detection:_ When
$\\{{{S}},{{Q}},{{U}}\\}{\subset}\mathbb{Z}^{+}$, predict object labels and
box locations for all ${{C}}$ classes, that include seen, zero and few-shot
classes.

In the same vein, generalized zero and few-shot detection problems aim to
detect seen classes in addition to novel ones. Next, we describe our approach
for ASD and GASD.

###  3.2 Method

Our goal is to design a model that can _simultaneously_ perform zero, few, and
many-shot detection. This model is trained with seen classes, and is quickly
adapted during inference for zero-shot and few-shot classes. This problem set-
up has the following major challenges: _(a) Adaptability:_ A trained model
must be flexible enough to incorporate new classes (with no or few examples)
on the go, _(b) Learning without Forgetting:_ While the model is adapted for
new classes, it must not forget the previous knowledge acquired on seen
classes, and _(c) Class Imbalance:_ The classes representations are highly
imbalanced: some with many instances, some with none and others with only a
few. Therefore, the learning regime must be robust against the inherent
imbalance in the ASD setting.

At a high-level, our proposed approach has two main components that address
the above mentioned problems. First, we consider the semantic class prototypes
to serve as anchors in the prediction space, thereby providing the flexibility
to extend to any number of novel classes without the need to retrain network
parameters. We show that such a representation also helps in avoiding
catastrophic forgetting that is likely to occur otherwise. Furthermore, we
propose a new loss formulation to address the class imbalance problem, that
specifically focuses on difficult cases and minimizes model’s bias against
rare classes. We elaborate the novel aspects of our approach below.

Figure 4: (a) Network architecture. The visual-semantic alignment is performed
using (b) seen semantics during base training and with (c) seen and novel
semantics during fine-tuning. The visual features from the classification and
regression units are separately used for visual-semantic alignment and
subsequent loss calculation.

####  3.2.1 Learning without Forgetting

Traditional object detection models are static approaches that cannot
dynamically adapt to novel classes. The flexibility to introduce novel object
classes, after the base model training, requires special consideration, e.g.,
by posing it as an incremental learning problem [17, 4, 33]. In such cases,
since classifier weights for novel categories are learned from scratch, the
knowledge distillation concept [13] is applied to avoid forgetting the old
learning. Such a strategy is not useful in our case because unlike previous
approaches, we do not have access to many examples of the new task and a
subset of novel classes has no training examples available.

To allow adding novel classes without forgetting old concepts, our approach
seeks to disentangle the feature learning and classification stages.
Precisely, we develop a training mechanism in which adding new classes does
not require re-training base-network’s parameters. This is achieved by
defining the output decision space in the form of semantic class prototypes.
These semantic class representatives are obtained in an unsupervised manner
using a large text corpus, such as the Wikipedia, and encode class-specific
attributes as well as the inter-class relationships [21, 22].

During base-model training, the model learns to map visual features to
semantic space. At the same time, the semantic space is well-aligned with the
visual concepts using a learnable projection. Note that only seen class
semantics are used during the training stage. Once the base-model is trained,
novel classes (both zero and few-shot) can be accommodated at inference time
taking advantage of the semantic class descriptions of the new classes. For
novel classes whose new few-examples are available during inference, we fine-
tune the model to adapt semantic space, but keeping the base-model’s
architecture unchanged. Essentially, this means that adding new classes does
not demand any changes to the architecture of the base-network. Still, the
model is capable of generating predictions for novel classes since it has
learned to relate visual information with semantic space during training (see
Fig. 4).

.

Figure 5: Loss visualization. The colored dotted lines represent
$\beta$-controlled penalty function, $h(.)$ and the solid lines represent loss
functions. (a) The red line represents cross entropy (CE) which is compared to
our loss with $\beta=1,2$ and $5$ shown as black, green and blue lines,
respectively. (b) Our loss (green line) with fixed $p_{*}{=}0.5$. Here, our
loss can be less than CE (red line) for the expected case. (c) Our loss curve
(green line) with dynamic $p_{*}$. Here, our loss calculates the same value as
CE (red line) for the expected case. The red shaded region represents extreme
case since $p{<}p_{*}$ and blue shaded region represents expected or moderate
case $p{\geq}p_{*}$. (d) Derivatives of CE and our loss for different $\beta$.
See the appendix for the gradient analysis.

Formally, a training image $\bm{X}$ is fed to a deep network $f(\cdot)$, that
produces a visual feature vector $f(\bm{X})\in\mathbb{R}^{n}$ corresponding to
a particular box location. In a parallel stream, seen word vectors
$\bm{W}_{s}$, are passed through a light-weight subnet denoted by $g(\cdot)$,
producing the transformed word vectors $g(\bm{W}_{s})$. Then, we connect the
visual and semantic streams via a trainable layer,
$\bm{U}\in\mathbb{R}^{n\times d}$. Finally, a set of seen scores $\bm{p}_{s}$
is obtained by applying a sigmoid activation function ($\sigma$). The overall
computation is given by,

$\bm{p}_{s}=\sigma\big{(}f(\bm{X})^{T}\bm{U}g(\bm{W}_{s})\big{)}.$ (1)

The mapping layer $\bm{U}$ can be understood as the bridge between semantic
and visual domains. Given the visual and semantic mappings, $f(\bm{X})$ and
$g(\bm{W}_{s})$ respectively, $\bm{U}$ seeks to maximize the alignment between
the visual feature and its corresponding semantic class such that the
prediction $\bm{p}_{s}$ is maximized. In a way, $\bm{p}_{s}$ is the alignment
compatibility scores where a higher score means more compatibility between
feature and semantics. The function $f(\cdot)$ can be implemented with a
convolutional network backbone (e.g. ResNet [12]) and $g(\cdot)$ can be
implemented as a fixed or trainable layer. In the fixed case, fixed word
vectors can be directly used for alignment i.e., $g(\bm{W}_{s})=\bm{W}_{s}$.
In the trainable case, $\bm{W}_{s}$ can be updated using a trainable metric
$\bm{M}\in\mathbb{R}^{d\times v}$ and a word vocabulary
$\bm{D}\in\mathbb{R}^{v\times d}$, resulting in
$g(\bm{W}_{s})=\delta(\bm{W}_{s}\bm{M}\bm{D})$ where, $v$ is the size of the
word vocabulary and $\delta$ is a $\tanh$ activation. In our experiments, we
find a trainable $g(\bm{W}_{s})$ achieves better performance.

We propose a two step training procedure. The first step involves training the
base model, where Eq. 1 is trained with only images and semantics of seen
classes. In the second step of fine-tuning, when novel class information
becomes available, we replace $\bm{W}_{s}$ by $\bm{W}$ and train it with few-
shot examples. Eq. 1 then becomes
$\bm{p}=\sigma\big{(}f(\bm{X})^{T}\bm{U}g(\bm{W})\big{)}$, where, $\bm{p}$
contains scores of both seen and novel classes. In this manner, model is
quickly adapted for novel classes.

Notably, although our network can predict scores for all classes, no new
tunable weights are added. In both steps, our network tries to align the
feature with its corresponding semantics. From the network’s perspective it
does not matter how many classes are present. It only cares how compatible a
feature is with the corresponding class semantics. This is why our network
does not forget the seen classes as these semantic prototypes serve as an
anchor to retain previous knowledge. Adding new classes is therefore not a new
task for the network. During fine-tuning, the model still performs the same
old task of aligning feature and semantics.

####  3.2.2 Learning with Imbalance Data

After base training on seen classes, novel classes information becomes
available during inference stage i.e., few-shot images and the word vectors of
both zero and few-shot classes. Here, the few-shot image may contain seen
instances as well. In this way, the fine-tuning stage contains an imbalanced
data distribution and the model must minimize bias towards the already seen
classes. To this end, we propose a rebalancing loss for the fine-tuning stage.

Suppose, $p\in\bm{p}$ is the alignment score for a visual feature and the
corresponding class semantics. As the fine-tuning is done on rare data, we
need to penalize the cross-entropy (CE) loss based on the quality of
alignment. If the network makes a mistake, we increase the penalty and if the
network is already performing well, we employ a low or negative penalty.
Suppose, the penalty $h(\cdot)$ is a function of $p$ and $p_{*}$ where $p_{*}$
determines the penalization level, then the loss is,

$L(p)=-\log p+\beta\,h(p,p_{*}),$ (2)

where, $\beta$ is a hyper-parameter. Here, $h(p,p_{*})$ is given by,

$h(p,p_{*})=\log(1+p_{*}-p),$ (3)

where $(p_{*}{-}p)$ represents the violation of the expected alignment that
controls the margin of the penalty function. We explore two alternatives for
selecting $p_{*}$, a fixed value in range $0{<}p_{*}{\leq}1$ and a dynamically
adjusted value based on $p_{*}=\max_{i\in C}p_{i}$. We can get the following
scenarios based on the choice of $p_{*}$ and positive alignment quality $p$:

  * •

_Expected case, $p{>}p_{*}$:_ Negative penalty to calculate lower loss
compared to CE (lower bounded by 0).

  * •

_Moderate case, $p{=}p_{*}$:_ Zero penalty and the calculated loss is equal to
regular CE.

  * •

_Extreme case, $p{<}p_{*}$:_ High penalty in comparison to regular CE loss.

Plugging the penalty definition from Eq. 3 to Eq. 2 and enforcing positive
loss values $L(p)\in\mathbb{R}^{+}$, we obtain,

$\displaystyle L(p)=\max\Bigg{[}0,-\log\frac{p}{(1+p_{*}-p)^{\beta}}\Bigg{]}.$
(4)

After adding an $\alpha$-balanced modulating factor from focal loss [19], we
have,

$\displaystyle{L(p)}=\max\Big{[}0,-\alpha_{t}(1-p_{t})^{\gamma}\log
p_{t}\Big{]},$ (5) $\displaystyle\text{where
}p_{t}=\begin{cases}\frac{p}{(1+p_{*}-p)^{\beta}},&\text{if $y=1$}\\\
1-p,&\text{otherwise}.\end{cases}$

Here, $\beta$ is the focusing parameter that focuses on hard cases and $y$ is
the corresponding value from the one-hot encoded ground-truth vector. With
$\beta{=}0$, Eq. 5 becomes equivalent to focal loss and with $\beta{=}0$,
$\gamma{=}0$, $\alpha{=}1$, Eq. 5 becomes cross-entropy loss.

Since several objects can co-occur in the same scene, the fine-tuning data can
have seen instances. To emphasise rare classes more than the seen ones, we
apply our rebalancing loss only on the novel class examples. For a seen
anchor, only the focal loss is calculated. Thus, the final loss is,

$\displaystyle L=\lambda L(s)+(1-\lambda)L(n).$ (6)

For the case of $L(s)$ and $L(n)$, $\beta{=}0$ and $\beta{>}0$ respectively.
$L(s)$ and $L(n)$ represent the compatibility scores of seen and novel (few-
shot and unseen) classes i.e., $s\in\\{1,2,..,S\\}$ and $n\in\\{1,2,..,T\\}$.

During inference when a test image is presented, a simple forward pass
provides compatibility scores of seen, few-shot and unseen classes for each
bounding box. If the score is higher than a threshold, we consider it a
correct detection.

Analysis: Based on the quality of alignment, our proposed loss penalizes
positive anchors. This scenario helps in the class imbalance problem.
Especially, in the extreme case, when the network fails to detect a positive
few-shot anchor, we highly penalize our network predictions. It gives extra
supervision to the network that it must not make errors on the few-shot
classes. In contrast, for the expected and moderate cases, we reduce the loss
which avoids the network becoming too confident on few-shot examples. Since,
unseen objects are more related to the seen objects as compared to background,
a low penalty on confident cases implicitly promotes discovering unseen
classes. In effect, this leads to low overfitting on the few-shot classes that
helps in achieving good performance on totally unseen classes.

Loss shape analysis: In Fig. 5, we visualize the loss. Fig. 5 (a) shows how
the shape of binary cross entropy (CE) changes with different values of
$\beta$. $\beta$ controls the penalty $h(.)$ which modifies CE loss. For a
fixed $p_{*}{=}1$, increasing $\beta$ calculates a higher penalty for any
mistake in the prediction. For a fixed margin penalty $p_{*}{=}0.5$ in Fig. 5
(b), a network can predict a lower, equal and higher score than $p_{*}$.
Correspondingly, it enables the network to calculate a less, equal and higher
penalty for expected, moderate and extreme cases, respectively. In contrast,
for the dynamic margin penalty case Fig. 5 (c), the predicted score can be at
best $p_{*}=\max_{i\in C}p_{i}$. Therefore, the extreme case works similarly
to the fixed $p_{*}$ scenario but for the other cases, the network calculates
a loss equal to CE/Focal loss. The dynamic $p_{*}$ estimates the quality of
predicted scores based on the current anchor specific situation. For example,
for a given anchor, a small predicted score (e.g., $0.1$) for the ground-truth
class can be considered as good prediction if all other predictions are
$<0.1$. It helps to make a good balance between seen, few-shot and unseen
predictions because the loss does not unnecessarily tries to maximize the
ground-truth class score and thus avoids over-fitting.

###  3.3 Implementation Details

We implement our framework with a modified version of the RetinaNet
architecture proposed in [24] (see Fig. 4(a)). It incorporates the word
vectors at the penultimate layers of classification and regression subnets.
While performing the base training with focal loss at the first step, we
follow the recommended process in [24], where only seen word vectors are used
in word processing network, $g(.)$ (see Fig. 4(b)). During the fine-tuning
step, we update the base model with newly available data and our proposed loss
function. As shown in Fig. 4(c), fine-tuning uses both seen and novel word
vectors inside $g(.)$. Note that, in addition to novel class data, the small
dataset used for fine-tuning includes some seen instances as well. We train
our model for 10 epochs during the fine-tuning stage. After the fine-tuning is
finished, our framework can detect seen, few-shot, and unseen classes
simultaneously. We use the Adam optimizer for each training stage.

Table 1: ASD performance.

#- | Method | ASD | GASD
---|---|---|---
Shot | unseen | FS | HM | seen | unseen | FS | HM
1 | Baseline-I | 3.74 | 1.60 | 2.25 | 54.11 | 2.04 | 0.73 | 1.60
Baseline-II | 8.57 | 21.39 | 12.23 | 51.89 | 3.79 | 9.62 | 7.74
Ours | 16.57 | 23.50 | 19.44 | 51.70 | 10.75 | 11.83 | 15.23
5 | Baseline-I | 4.16 | 2.69 | 3.27 | 54.15 | 2.35 | 1.20 | 2.35
Baseline-II | 8.69 | 26.19 | 13.05 | 51.67 | 4.85 | 18.20 | 10.70
Ours | 18.22 | 26.31 | 21.53 | 51.18 | 12.70 | 18.34 | 19.63
10 | Baseline-I | 3.45 | 2.95 | 3.18 | 54.25 | 1.89 | 1.56 | 2.53
Baseline-II | 7.26 | 31.14 | 11.78 | 51.00 | 4.12 | 25.00 | 9.91
Ours | 13.21 | 33.52 | 18.95 | 51.18 | 9.71 | 26.96 | 18.79

Table 2: Ablation study with 5-shot case.

Method | ASD | GASD
---|---|---
unseen | FS | HM | seen | unseen | FS | HM
Baseline-I | 4.16 | 2.69 | 3.27 | 54.15 | 2.35 | 1.20 | 2.35
Baseline-II | 8.69 | 26.19 | 13.05 | 51.67 | 4.85 | 18.20 | 10.70
Ours with FL | 13.69 | 23.81 | 16.61 | 51.20 | 9.21 | 16.34 | 15.85
Ours with AL | 7.03 | 24.17 | 10.89 | 50.74 | 5.94 | 17.46 | 12.23
Ours ($p_{*}=0.3$) | 17.20 | 26.85 | 20.97 | 51.48 | 11.84 | 19.21 | 19.24
Ours ($p_{*}=0.5$) | 15.24 | 24.02 | 18.65 | 50.65 | 10.38 | 17.06 | 17.17
Ours ($p_{*}=1.0$) | 16.17 | 27.17 | 20.27 | 50.58 | 11.29 | 19.83 | 18.90
Ours* | 16.60 | 24.05 | 19.64 | 51.32 | 11.09 | 16.71 | 17.70
Ours | 18.22 | 26.31 | 21.53 | 51.18 | 12.70 | 18.34 | 19.63

Figure 6: FSD performance. (a) 1-, 5- and 10-shot detection mAP, (b), (c) and
(d) seen, unseen and harmonic mean (HM) of GFSD. (e) 10-shot detection mAP
with MSCOCO to PASCAL

##  4 Experiments

Datasets: We evaluate our work on the MSCOCO-2014 [20] and PASCAL VOC 2007/12
datasets. For the MSCOCO experiment, we adopt the 65/15 seen/unseen split
setting used in [24, 25]. In both ZSD and FSD experiments, we consider unseen
classes as the novel ones. However, in ASD experiments, we further split 15
novel classes into 8 few-shot and 7 unseen classes. We use the same $62300$
images during training where no single instance of novel classes is present.
For testing ASD, we use $10098$ images where each image contains at least one
novel object. However for GASD testing, we use the entire validation set of
$40504$ images. For the PASCAL VOC 2007/12 experiment, we adopt 15/5
seen/novel split settings from [14]. As recommended, we use train$+$val sets
from PASCAL VOC 2007 and 2012 as training data and test-set from PASCAL VOC
2007 for evaluation. For FSD/ASD, we randomly choose additional images with a
few (1/5/10) annotated bounding boxes for each novel category. These images
may contain some seen objects as well. For both MSCOCO and PASCAL VOC classes
and vocabulary texts, we use 300-dimensional and $\ell_{2}$ normalized
word2vec vectors [21]. We have used same set of $4717$ vocabulary atoms as
used in [24] which are originally taken from [8].

Evaluation criteria: For FSD and ASD, we evaluate our method with mean average
precision (mAP). To report GFSD and GASD, we calculate the harmonic mean of
the individual seen and novel class mAP. For ZSD, we report recall@100 results
as recommended in [3].

Validation experiment: $\alpha,\beta,\gamma$ and $\lambda$ are the hyper-
parameter of our model. Among them, $\alpha$ and $\gamma$ are spefici to focal
loss. Thus, we fix the recommend value $\alpha=0.25$ and $\gamma=2$ following
[19]. We validate $\beta$ and $\lambda$ by creating a validation dataset based
on splitting 65 seen classes into 55 seen and 10 novel classes. From the
validation experiment, we select $\beta=5$ and $\lambda=0.1$. Detailed
validation results are presented in the appendix.

Baseline methods: Here, we introduce the baseline methods used for comparison
in this work.
$\bullet$ _Baseline-I:_ A RetinaNet architecture where fixed semantics are
used in semantic processing pipeline i.e. $g(\bm{W}_{s})=\bm{W}_{s}$ and the
training is done with the basic focal loss. The fine-tuning step uses all seen
and novel class data together.
$\bullet$ _Baseline-II:_ The second baseline approach is identical to
Baseline-I, except that the fine-tuning step uses novel class data and a few
examples of seen.
Finally, _Ours_ denote the complete approach where the RetinaNet architecture
is trained with adaptive prototypes in the semantic processing pipeline i.e.
$g(\bm{W}_{s})=\delta(\bm{W}_{s}\bm{M}\bm{D})$ and the training is done with
our proposed loss.

Table 3: FSD mAP on Pascal VOC 2007 test set.

| Base | Novel
---|---|---
# shot |  Method |  aero |  bike |  boat |  bottle |  car |  cat |  chair |  table |  dog |  horse |  person |  plant |  sheep |  train |  tv |  mean |  bird |  bus |  cow |  mbike |  sofa |  mean
3 | LSTD [6] | 74.8 | 68.7 | 57.1 | 44.1 | 78.0 | 83.4 | 46.9 | 64.0 | 78.7 | 79.1 | 70.1 | 39.2 | 58.1 | 79.8 | 71.9 | 66.3 | 23.1 | 22.6 | 15.9 | 0.4 | 0.0 | 12.4
Kang _et al_. [14] | 73.6 | 73.1 | 56.7 | 41.6 | 76.1 | 78.7 | 42.6 | 66.8 | 72.0 | 77.7 | 68.5 | 42.0 | 57.1 | 74.7 | 70.7 | 64.8 | 26.1 | 19.1 | 40.7 | 20.4 | 27.1 | 26.7
Ours | 80.4 | 52.8 | 50.2 | 55.9 | 76.9 | 85.1 | 49.8 | 54.0 | 76.8 | 72.7 | 81.1 | 44.8 | 61.7 | 79.0 | 76.8 | 66.5 | 28.6 | 18.7 | 15.5 | 55.5 | 17.4 | 27.1
5 | LSTD [6] | 70.9 | 71.3 | 59.8 | 41.1 | 77.1 | 81.9 | 45.1 | 67.2 | 78.0 | 78.9 | 70.7 | 41.6 | 63.8 | 79.7 | 66.8 | 66.3 | 22.8 | 52.5 | 31.3 | 45.6 | 40.3 | 38.5
Kang _et al_. [14] | 65.3 | 73.5 | 54.7 | 39.5 | 75.7 | 81.1 | 35.3 | 62.5 | 72.8 | 78.8 | 68.6 | 41.5 | 59.2 | 76.2 | 69.2 | 63.6 | 30.0 | 62.7 | 43.2 | 60.6 | 39.6 | 47.2
Ours | 78.8 | 50.2 | 56.5 | 59.7 | 75.8 | 85.4 | 52.1 | 54.0 | 78.9 | 72.4 | 81.8 | 47.1 | 64.1 | 73.5 | 76.6 | 67.1 | 47.3 | 50.3 | 39.6 | 68.9 | 39.9 | 49.2

###  4.1 ASD Performance

Here, we discuss the ASD and GASD performance with the 65/8/7 split of MSCOCO.
For ASD, we show the performance of novel classes (i.e. unseen and few-shot
classes) and the harmonic mean of individual performances. For GASD, we report
separate seen, few-shot, unseen mAP and their harmonic mean mAP to show the
overall performance.

Main results: In Table 2, we report the our main results and comparisons with
the baselines. Our observations are as follows: (1) Using more few-shot
examples generally helps. However the effect of higher shots on the unseen
performance is not always positive since more instances of few-shot classes
can bias the model towards them. (2) Except Baseline-1, few-shot mAP is always
better than unseen mAP because few-shot examples with our proposed loss
improve the alignment with respective class semantics. In the Baseline-I case,
as all seen and few-shot data is used together, the network overfits to seen
classes. (3) Our seen class performance in GASD remains good across different
shots. This denotes that the network does not forget seen classes when trained
on novel ones. Seen classes get the maximum performance for the Baseline-I due
to overfitting, thereby giving poor performance on novel classes. (4) Across
different shots, Baseline-II beats the Baseline-I method as it is less prone
to overfitting. With the proposed adaptive semantic prototypes and our loss
function, we beat Baseline-II. (5) The improvement for unseen mAP is greater
than few-shot or seen mAP irrespective of the number of shots, ASD, or GASD
tasks. It tells us that our loss formulation not only tackles the class
imbalance of few-shot classes but also promotes detection of unseen classes.
In Fig. 7 and 8, we show qualitative results for GASD.

Ablation studies: In Table 2, we report ablation experiments with with
alternate versions of our approach. Baseline-I and Baseline-II operate with
fixed semantics. For the rest of the cases, we use our adaptive semantic-
prototype approach (Sec. 3.2.1) to update the word vectors. Here, we first use
a basic focal loss [19] (FL) to train the network. This approach outperforms
both baselines because of the adaptable semantic prototypes. Then, we try two
variants of FL: Anchor Loss [31] (AL) and a modified anchor loss with our loss
penalty definition for few-shot classes. We notice that these variations do
not work well in both ASD and GASD cases because AL penalizes negative anchors
that network confuses with positive ones. This idea is beneficial for
traditional recognition cases, but unsuitable for ZSD/FSD/ASD scenarios. This
is because a negative anchor may contain an unseen object which is closely
related to seen or few-shot semantics, and we do not want to suppress the
anchor even though it predicts similar scores as the positive ones. Next, we
apply our loss by fixing $p_{*}$ to a constant value e.g., 0.3, 0.5, and 1.
These trials outperform both baselines and FL based methods since the network
emphasizes few-shot examples based on the quality of the visual-semantic
alignment. Finally, alongside the adaptive semantics, we apply our final loss
formulation which dynamically selects $p_{*}$. Our loss beats all previously
described settings because it brings better emphasis on novel classes.
Notably, we also experiment with the Our* case that applies our loss to all
predictions (instead of just the novel scores) i.e., $\beta>0$ for all
classes. However, it does not perform as well as Ours potentially because the
representations suitable for seen classes are already learnt well.

###  4.2 FSD Performance

If ${{U}}{=}0$, our proposed ASD framework becomes a few-shot detection
problem. In this paper, we experiment on FSD with the following three
different dataset setups.

MSCOCO: Here we consider all 15 novel classes of the MSCOCO split [24] as few-
shot classes. We report mAP results of 1, 5 and 10-shot detection tasks of
Baseline-I, Baseline-II, and Ours model in Fig. 6 (a-d). Besides, we report
generalized FSD results. Overall, FSD performance improves with more examples.
When trained with the adaptive semantic prototypes and rebalancing loss, our
model successfully outperforms both baselines.

MSCOCO to PASCAL: It is a cross-dataset experiment. Following [14], we use 20
PASCAL VOC classes (overlapped with MSCOCO) as the few-shot classes and the
remaining 60 MSCOCO classes as seen. This setting performs base training on
MSCOCO seen classes and fine-tunes the base model using the 10-shot examples
of the PASCAL VOC dataset. Finally, the PASCAL VOC 2007 test set is used to
evaluate FSD. In Fig. 6(e), our method outperforms others including a recent
approach [14].

PASCAL VOC 2007/12: Using the 15/5 novel-split-1 proposed in [14], we compare
FSD performance of our work with Kang _et al_. [14] and LSTD [6] in Table 3.
We achieve better performance than them in both novel and base class detection
with 3- and 10-shot detection settings.

Figure 7: Qualitative results for Generalized ASD. Yellow, blue and pink boxes
represent seen, few-shot and unseen objects, respectively. _(best viewed with
zoom)_ Figure 8: Qualitative comparison with [27], [24] and Our method. Object
bounding boxes: Yellow (seen), blue (few-shot) and pink (unseen). _(best
viewed with zoom)_ Table 4: Recall scores for ZSD and GZSD tasks on MSCOCO
dataset.

Method | ZSD | GZSD
---|---|---
Seen | Unseen | HM
SB [3] | 24.39 | - | - | -
DSES [3] | 27.19 | 15.02 | 15.32 | 15.17
SAN [27] | 12.27 | - | - | -
Baseline | 18.67 | 42.21 | 17.60 | 24.84
Ours | 32.83 | 41.66 | 27.34 | 33.01

###  4.3 ZSD Performance

For ZSD case, after the first step of base training, we do not have any more
data to fine-tune. Thus, we perform the second step of fine-tuning with the
same data used in the first step but apply our loss instead of the focal loss.
As ${{Q}}{=}0$, we consider each seen class as a few-shot class during the
second step. It emphasizes all seen classes in the same way. But, based on the
dynamic choice of $p_{*}$, the network penalizes a bad prediction by
calculating high loss and compensates a good prediction with no penalty. We
notice that it helps to improve ZSD performance. We apply this process with
the 48/17 split setting of [3] on MSCOCO. We report the result of this
experiment in Table 4. As recommended in [3], we compare our work using recall
measure where it outperforms other methods.

##  5 Conclusion

In this paper, we propose a unified any-shot detection approach where novel
classes include both unseen and few-shot objects. Traditional approaches
consider solving zero and few-shot tasks separately, whereas our approach
encapsulates both tasks into a common framework. This approach does not forget
the base training while learning novel classes, which helps to perform
generalized ASD. Moreover, we propose a new loss function to learn new tasks.
This loss penalizes the wrong prediction of a novel class more than the seen
classes. We evaluate the proposed ASD tasks on the challenging MSCOCO and
PASCAL VOC datasets. Besides, we compare ZSD and FSD performance of our
approach with established state-of-the-art methods. Our first ASD framework
delivers strong performance in ZSD, FSD, and ASD tasks compared to previous
methods.

## References

  * [1] Ziad Al-Halah and Rainer Stiefelhagen.  Automatic discovery, association estimation and learning of semantic attributes for a thousand categories.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [2] Ziad Al-Halah, Makarand Tapaswi, and Rainer Stiefelhagen.  Recovering the missing link: Predicting class-attribute associations for unsupervised zero-shot learning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [3] Ankan Bansal, Karan Sikka, Gaurav Sharma, Rama Chellappa, and Ajay Divakaran.  Zero-shot object detection.  In The European Conference on Computer Vision (ECCV), September 2018\.
  * [4] Guobin Chen, Wongun Choi, Xiang Yu, Tony Han, and Manmohan Chandraker.  Learning efficient object detection models with knowledge distillation.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, pages 742–751, USA, 2017. Curran Associates Inc.
  * [5] Hao Chen, Yali Wang, Guoyou Wang, and Yu Qiao.  Lstd: A low-shot transfer detector for object detection.  2018\.
  * [6] Hao Chen, Yali Wang, Guoyou Wang, and Yu Qiao.  Lstd: A low-shot transfer detector for object detection.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [7] Wei-Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Wang, and Jia-Bin Huang.  A closer look at few-shot classification.  In International Conference on Learning Representations, 2019.
  * [8] Tat-Seng Chua, Jinhui Tang, Richang Hong, Haojie Li, Zhiping Luo, and Yan-Tao Zheng.  Nus-wide: A real-world web image database from national university of singapore.  In CIVR, Santorini, Greece., July 8-10, 2009.
  * [9] Berkan Demirel, Ramazan Gokberk Cinbis, and Nazli Ikizler-Cinbis.  Zero-shot object detection by hybrid region embedding.  In British Machine Vision Conference (BMVC), Sep. 2018.
  * [10] Xuanyi Dong, Liang Zheng, Fan Ma, Yi Yang, and Deyu Meng.  Few-example object detection with model communication.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(7):1641–1654, July 2019.
  * [11] Ali Farhadi, Ian Endres, Derek Hoiem, and David Forsyth.  Describing objects by their attributes.  In CVPR, pages 1778–1785. IEEE, 2009.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [13] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [14] Bingyi Kang, Zhuang Liu, Xin Wang, Fisher Yu, Jiashi Feng, and Trevor Darrell.  Few-shot object detection via feature reweighting.  In The IEEE International Conference on Computer Vision (ICCV), October 2019.
  * [15] Leonid Karlinsky, Joseph Shtok, Sivan Harary, Eli Schwartz, Amit Aides, Rogerio Feris, Raja Giryes, and Alex M. Bronstein.  Repmet: Representative-based metric learning for classification and few-shot object detection.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [16] Elyor Kodirov, Tao Xiang, Zhenyong Fu, and Shaogang Gong.  Unsupervised domain adaptation for zero-shot learning.  In The IEEE International Conference on Computer Vision (ICCV), December 2015.
  * [17] Zhizhong Li and Derek Hoiem.  Learning without forgetting.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(12):2935–2947, 2018.
  * [18] Zhihui Li, Lina Yao, Xiaoqin Zhang, Xianzhi Wang, Salil Kanhere, and Huaxiang Zhang.  Zero-shot object detection with textual descriptions.  Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):8690–8697, Jul. 2019.
  * [19] Tsung-Yi Lin, Priyal Goyal, Ross Girshick, Kaiming He, and Piotr Dollar.  Focal loss for dense object detection.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018\.
  * [20] 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, pages 740–755. Springer, 2014.
  * [21] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean.  Distributed representations of words and phrases and their compositionality.  In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, NIPS’13, pages 3111–3119, USA, 2013\. Curran Associates Inc.
  * [22] Jeffrey Pennington, Richard Socher, and Christopher D. Manning.  Glove: Global vectors for word representation.  In EMNLP, pages 1532–1543, 2014.
  * [23] Hang Qi, Matthew Brown, and David G. Lowe.  Low-shot learning with imprinted weights.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [24] Shafin Rahman, Salman Khan, and Nick Barnes.  Polarity loss for zero-shot object detection.  arXiv preprint arXiv:1811.08982, 2018.
  * [25] Shafin Rahman, Salman Khan, and Nick Barnes.  Transductive learning for zero-shot object detection.  In The IEEE International Conference on Computer Vision (ICCV), October 2019.
  * [26] Shafin Rahman, Salman Khan, and Fatih Porikli.  A unified approach for conventional zero-shot, generalized zero-shot, and few-shot learning.  IEEE Transactions on Image Processing, 27(11):5652–5667, Nov 2018\.
  * [27] Shafin Rahman, Salman Khan, and Fatih Porikli.  Zero-shot object detection: Learning to simultaneously recognize and localize novel concepts.  In Computer Vision – ACCV 2018, pages 547–563, Cham, 2019. Springer International Publishing.
  * [28] Sachin Ravi and Hugo Larochelle.  Optimization as a model for few-shot learning.  In In International Conference on Learning Representations (ICLR), 2017.
  * [29] Joseph Redmon and Ali Farhadi.  Yolo9000: Better, faster, stronger.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
  * [30] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(6):1137–1149, June 2017.
  * [31] Serim Ryou, Seong-Gyun Jeong, and Pietro Perona.  Anchor loss: Modulating loss scale based on prediction difficulty.  In The IEEE International Conference on Computer Vision (ICCV), October 2019.
  * [32] Edgar Schonfeld, Sayna Ebrahimi, Samarth Sinha, Trevor Darrell, and Zeynep Akata.  Generalized zero- and few-shot learning via aligned variational autoencoders.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [33] Konstantin Shmelkov, Cordelia Schmid, and Karteek Alahari.  Incremental learning of object detectors without catastrophic forgetting.  In Proceedings of the IEEE International Conference on Computer Vision, pages 3400–3409, 2017.
  * [34] Jake Snell, Kevin Swersky, and Richard Zemel.  Prototypical networks for few-shot learning.  In Advances in Neural Information Processing Systems, pages 4077–4087, 2017.
  * [35] Jie Song, Chengchao Shen, Yezhou Yang, Yang Liu, and Mingli Song.  Transductive unbiased embedding for zero-shot learning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [36] Yao-Hung Hubert Tsai, Liang-Kang Huang, and Ruslan Salakhutdinov.  Learning robust visual-semantic embeddings.  In The IEEE International Conference on Computer Vision (ICCV), Oct 2017.
  * [37] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.  Matching networks for one shot learning.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, pages 3637–3645, USA, 2016. Curran Associates Inc.
  * [38] Yu-Xiong Wang and Martial Hebert.  Model recommendation: Generating object detectors from few samples.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
  * [39] Yongqin Xian, Christoph H. Lampert, Bernt Schiele, and Zeynep Akata.  Zero-shot learning—a comprehensive evaluation of the good, the bad and the ugly.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(9):2251–2265, Sep. 2019.
  * [40] Yongqin Xian, Tobias Lorenz, Bernt Schiele, and Zeynep Akata.  Feature generating networks for zero-shot learning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [41] Yongqin Xian, Saurabh Sharma, Bernt Schiele, and Zeynep Akata.  F-vaegan-d2: A feature generating framework for any-shot learning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [42] An Zhao, Mingyu Ding, Jiechao Guan, Zhiwu Lu, Tao Xiang, and Ji-Rong Wen.  Domain-invariant projection learning for zero-shot recognition.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 1019–1030. Curran Associates, Inc., 2018.
  * [43] Pengkai Zhu, Hanxiao Wang, and Venkatesh Saligrama.  Zero shot detection.  IEEE Transactions on Circuits and Systems for Video Technology, pages 1–1, 2019.
  * [44] Charles Lawrence Zitnick and Piotr Dollár.  Edge boxes: Locating object proposals from edges.  In David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars, editors, ECCV, pages 391–405, Cham, 2014. Springer International Publishing.

##  6 Appendix A

This appendix material provides additional qualitative results, gradient
analysis for the proposed loss function and validation experiments for the
hyper-parameters.

Figure 9: More qualitative results for generalized ASD. Yellow, blue and pink
boxes represent seen, few-shot and unseen objects, respectively. The proposed
approach can detect classes from all the three categories.

###  6.1 Qualitative Results

In Fig. 9, we show additional qualitative results of our approach on the ASD
task. All visual results are generated with a single ASD model that can detect
seen, unseen and few-shot classes, simultaneously.

###  6.2 Gradient analysis

In this section, we derive the gradients of our proposed loss w.r.t $p$. For
simplicity, we only focus on the predictions corresponding to the ground-truth
class. We show the gradient curve in Fig. 4(d) of the main paper.

$\displaystyle\frac{\partial L}{\partial
p}=\begin{cases}\dfrac{1}{p\left(p-p_{*}-1\right)\left(p-\left(1-p+p_{*}\right)^{\beta}\right)}\Big{[}\alpha_{t}\big{(}\left(\beta-1\right)p\\\
\qquad\qquad+p_{*}+1\big{)}\left(1-\frac{p}{\left(1-p+p_{*}\right)^{\beta}}\right)^{\gamma}\big{(}\gamma
p\log\left(p\right)\\\
\qquad\qquad+\left(1-\beta{\gamma}\log\left(1-p+p_{*}\right)\right)p-\left(1-p+p_{*}\right)^{\beta}\big{)}\Big{]}\\\
\qquad\quad\text{if
}\;\big{(}\alpha_{t}\beta\left(1-\frac{p}{(1-p+p_{*})^{\beta}}\right)^{\gamma}\log\left(1-p+p_{*}\right)\\\
\qquad\qquad-\alpha_{t}\left(1-\frac{p}{(1-p+p_{*})^{\beta}}\right)^{\gamma}\log(p)\big{)}>0\text{
and }y=1\\\
\dfrac{\alpha_{t}p^{\gamma}}{1-p}-\alpha_{t}\gamma\log\left(1-p\right)p^{\gamma-1}\\\
\qquad\quad\text{if }\;\big{(}\alpha_{t}p^{\gamma}\log(1-p)\big{)}<0\text{ and
}y=0\\\ 0\qquad\;\,\text{otherwise}.\end{cases}$

###  6.3 Validation Set Experiments

Note that $\alpha,\beta,\gamma$ and $\lambda$ are the hyper-parameter of our
model. Among them, $\alpha$ and $\gamma$ are focal loss hyper-parameter. Thus,
we fix the recommended value of $\alpha=0.25$ and $\gamma=2$ as per the
original RetinaNet model [19]. $\beta$ and $\lambda$ are the hyper-parameters
proposed in our loss formulation. Therefore, we validate $\beta$ and $\lambda$
by further splitting 65 seen classes into 55 seen and 10 novel classes to
create a validation set. Then, we perform a 5-shot detection task on this
validation split. We report the validation results in Table 5. From our
validation study, we select $\beta=5$ and $\lambda=0.1$ and use this value in
all of our experiments.

$\beta$ $\lambda$ | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.7 | 0.9 | 1.0
---|---|---|---|---|---|---|---|---
0.5 | 30.90 | 30.22 | 28.70 | 26.92 | 24.84 | 22.53 | 17.23 | 0.23
1 | 29.70 | 28.82 | 29.25 | 28.06 | 26.96 | 23.73 | 16.83 | 0.24
2 | 30.04 | 29.78 | 29.07 | 29.93 | 27.05 | 23.99 | 18.42 | 0.13
5 | 31.54 | 31.54 | 30.50 | 29.52 | 27.64 | 25.83 | 17.14 | 0.26
Table 5: Validation studies with 5-shot detection performance


# On the Structure of the Linear Codes with a Given Automorphism

Stefka Bouyuklieva  Faculty of Mathematics and Informatics, St. Cyril and St.
Methodius University of Veliko Tarnovo, BULGARIA<EMAIL_ADDRESS>
###### Abstract.

The purpose of this paper is to present the structure of the linear codes over
a finite field with $q$ elements that have a permutation automorphism of order
$m$. These codes can be considered as generalized quasi-cyclic codes. Quasi-
cyclic codes and almost quasi-cyclic codes are discussed in detail, presenting
necessary and sufficient conditions for which linear codes with such an
automorphism are self-orthogonal, self-dual, or linear complementary dual.

###### Key words and phrases:

linear codes, automorphisms, quasi-cyclic codes

###### 2010 Mathematics Subject Classification:

Primary 94B05,20B25

The research is partially supported by the Bulgarian National Science Fund
under Contract No KP-06-H62/2/13.12.2022

##  1\. Introduction

Linear codes invariant under a given permutation have been studied for a long
time, and this is most evident for cyclic codes (we refer to [29] and [32] for
more information), and also for group codes (see [4, 28]). The idea of using
automorphisms in the construction of combinatorial structures is not new. In
[1], the authors used automorphisms in the search for a projective plane of
order 10. The research of W. C. Huffman is devoted to the study of linear and
more precisely self-dual codes over various finite fields and even rings
having an automorphism of a given order (preferably prime) [20, 21, 23, 24].
We would like to mention also the works of V. Yorgov, G. Nebe, M. Borello and
W. Willems on the linear codes and their automorphisms (for example [6, 30,
35]).

Studying the structure of linear codes invariant under a given permutation is
important not only from the point of view of obtaining useful information
about the properties and parameters of these codes, but also for presenting
efficient methods for constructing codes with given parameters and preset
properties such as self-orthogonal or linear complementary dual (LCD) codes.
Codes that have such an automorphism, have some symmetric structure and useful
algebraic properties. As a disadvantage of these methods, we can point out the
lack of comprehensiveness, i.e. we are not sure whether we have obtained all
codes with the requested properties and parameters, we cannot prove the
nonexistence of codes with given parameters unless we combine the research
with other techniques. On the other hand, codes with a large group of
automorphisms have a rich algebraic structure, very useful properties,
practical applications, and therefore they are the most studied codes.

In this paper, we present a study on linear codes over a finite field with $q$
elements ($q$ is a prime power) having as an automorphism a permutation
$\sigma$ of a given order $m$ (not necessarily prime), focusing in particular
on the case where $\sigma$ has $c$ disjoint cycles of length $m$ and $f\geq 0$
fixed points. Our idea is to combine:

  * (1)

the works by Huffman (see for example [20, 23]) and Yorgov [35], mostly on
binary, ternary and Hermitian quaternary self-dual codes,

  * (2)

our own research on binary self-dual, self-orthogonal and LCD codes having an
automorphism of prime order [9, 10, 11, 12], and

  * (3)

the algebraic approach to quasi-cyclic codes of Patrick Solé and San Ling [26,
27].

We present some general conditions according to which the considered linear
codes are self-dual, self-orthogonal, or LCD, respectively.

The paper is organized as follows. In the next section we present the needed
definitions and general statements. Section 3 is devoted to permutations of
order $m$, relatively prime to the characteristic of the considered finite
field. The term _almost quasi-cyclic code_ is introduced for generalized
quasi-cyclic (GQC) codes of block lengths $(m,\ldots,m,1,\ldots,1)$. These are
linear codes invariant under a permutation of order $m$ with $c$ disjoint
cycles of length $m$ and $f\geq 1$ cycles of length 1 (fixed points) in its
decomposition. In Section 4 we study codes with a permutation automorphism of
order $m$ divisible by the characteristic of the field. We present some
examples in Section 5. We end the paper with a conclusion.

##  2\. Preliminaries

A linear $[n,k]$ code $C$ is a $k$-dimensional subspace of the vector space
$\mathbb{F}_{q}^{n}$, where $\mathbb{F}_{q}$ is the finite field of $q$
elements, $q=p^{\ell}$ for a prime $p$ and positive integer $\ell$. Let
$(u,v):\mathbb{F}_{q}^{n}\times\mathbb{F}_{q}^{n}\to\mathbb{F}_{q}$ be an
inner product in $\mathbb{F}_{q}^{n}$. If $C$ is an $[n,k]$ linear code, then
its orthogonal complement $C^{\perp}=\\{u\in\mathbb{F}_{q}^{n}:(u,v)=0$
$\forall v\in C\\}$ is a linear $[n,n-k]$ code called the dual code of $C$. We
consider three types of linear codes depending on the intersection with their
duals:

  * •

If $C=C^{\perp}$, $C$ is termed self-dual. If the length of a self-dual code
is $n$ then its dimension must be $n/2$.

  * •

If $C\subseteq C^{\perp}$, the code is self-orthogonal. A self-orthogonal code
is also self-dual iff its dimension is a half of its length. Self-orthogonal
codes with $k>n/2$ do not exist.

  * •

If $C\cap C^{\perp}$ consists only of the zero vector, the code is called LCD
(linear complementary dual). If $C$ is an LCD code so is its dual code
$C^{\perp}$.

In this paper, we consider inner products of two types:

  * •

Euclidean inner product, defined by

$u\cdot
v=\sum_{i=1}^{n}u_{i}v_{i}\in\mathbb{F}_{q},\;u=(u_{1},\ldots,u_{n}),v=(v_{1},\ldots,v_{n})\in\mathbb{F}_{q}^{n}.$

  * •

Hermitian inner product

$(u,v)=\sum_{i=1}^{n}u_{i}\overline{v}_{i}\in\mathbb{F}_{q},$

where $\overline{a}=a^{\sqrt{q}}$ if $q$ is a square.

The most general definition for equivalence of linear codes of length $n$ over
the finite field $\mathbb{F}_{q}$ is based on the action of the semilinear
isometries group
$\mathcal{M}_{n}^{*}(q)=\mathrm{Mon}_{n}(\mathbb{F}_{q}^{\ast})\rtimes{\rm
Aut}(\mathbb{F}_{q})\leq\Gamma_{n}(\mathbb{F}_{q})$ on the vector space
$\mathbb{F}_{q}^{n}$, where $\Gamma_{n}(\mathbb{F}_{q})$ is the set of all
semilinear mappings, i.e. the general semilinear group,
$\mathrm{Mon}_{n}(\mathbb{F}_{q}^{\ast})$ is the group of all monomial
$n\times n$ matrices over $\mathbb{F}_{q}$, and ${\rm Aut}(\mathbb{F}_{q})$ is
the automorphisms group of the field $\mathbb{F}_{q}$. Linear $q$-ary codes
$C$ and $C^{\prime}$ of the same length $n$ are equivalent whenever
$C^{\prime}=CT$ for some $T\in\mathcal{M}_{n}^{*}(q)$. If $CT=C$ for an
element $T\in\mathcal{M}_{n}^{*}(q)$ then $T$ is called an automorphism of the
code. The set of all automorphisms of $C$ form a group denoted by
$\textrm{Aut}(C)$.

Any element $T\in\mathcal{M}_{n}^{*}(q)$ can be written as $T=PD\tau$ where
$P$ is a permutation matrix (permutation part), $D$ is a diagonal matrix
(diagonal part), and $\tau\in\mathrm{Aut}(\mathbb{F}_{q})$. Note that in the
case of prime $q$,
$\mathcal{M}_{n}^{*}(q)=\mathrm{Mon}_{n}(\mathbb{F}_{q}^{\ast})$, and if $q=2$
then $\mathcal{M}_{n}^{*}(q)\cong\textrm{Sym}(n)$ where $\textrm{Sym}(n)$ is
the symmetric group of degree $n$. We consider here only the permutation
automorphisms of a linear code.

Let $C$ be a linear $q$-ary code with a permutation automorphism
$\sigma\in\textrm{Sym}(n)$ of order $m$ (not necessarily prime). If $\sigma$
is a product of $s$ disjoint cycles, namely

(2.1) $\sigma=\Omega_{1}\Omega_{2}\cdots\Omega_{s},$

where the length of $\Omega_{i}$ is $l_{i}\geq 1$, $1\leq i\leq s$, then
$m=\mathrm{lcm}(l_{1},\ldots,l_{s})$.

To describe the structure of the considered codes, we need the factor rings
$\mathcal{R}_{l_{i}}=\mathbb{F}_{q}[x]/(x^{l_{i}}-1)$, where
$\mathbb{F}_{q}[x]$ is the ring of polynomials in the indeterminate $x$ with
coefficients in $\mathbb{F}_{q}$. Define the map
$\phi:\mathbb{F}_{q}^{n}\to\mathcal{R}_{l_{1}}\times\mathcal{R}_{l_{2}}\times\cdots\times\mathcal{R}_{l_{s}}$
by

$\displaystyle\phi(c)$ $\displaystyle=(c_{1}(x),\ldots,c_{s}(x))$
$\displaystyle=(c_{10}+c_{11}x+\cdots+c_{1,l_{1}-1}x^{l_{1}-1},\ldots,c_{s0}+c_{s1}x+\cdots+c_{s,l_{s}-1}x^{l_{s}-1})$

for
$c=(c_{10},c_{11},\ldots,c_{1,l_{1}-1},\ldots,c_{s0},c_{s1},\ldots,c_{s,l_{s}-1})\in\mathbb{F}_{q}^{n}$.

Any submodule of
$\mathcal{R}^{\prime}=\mathcal{R}_{l_{1}}\times\mathcal{R}_{l_{2}}\times\cdots\times\mathcal{R}_{l_{s}}$
is called a generalized quasi-cyclic (GQC) code of block lengths
$(l_{1},\ldots,l_{s})$, which is a linear code of length $l_{1}+\cdots+l_{s}$
over $\mathbb{F}_{q}$ [17, 33]. Decomposition into constituents for GQC codes
is given by Esmaeili and Yari in [15]. We will not consider this decomposition
here.

We define the subcodes of $C$

$F_{\sigma}(C):=\\{v\in C\mid v\sigma=v\\}$

and

$E_{\sigma}(C):=\\{v=(v_{1},\ldots,v_{n})\in
C:\sum_{i\in\Omega_{j}}v_{i}=0\;\mbox{in}\;\mathbb{F}_{q}\;\textrm{for
all}\;j=1,\ldots,s\\}.$

Note that $v\in F_{\sigma}(C)$ if and only if $v\in C$ and $v|_{\Omega_{j}}$
is constant for $j=1,\ldots,s$. Therefore, we define the map
$\pi:F_{\sigma}(C)\rightarrow\mathbb{F}_{q}^{s}$ by $(\pi(v))_{j}=v_{i}$ for
some $i\in\Omega_{j}$, $j=1,2,\ldots,s$, $v\in F_{\sigma}(C)$.

We use also the map $\psi:C\to\mathbb{F}_{q}^{s}$ defined by

$\psi(v)=(\sum_{i\in\Omega_{1}}v_{i},\ldots,\sum_{i\in\Omega_{s}}v_{i}),$

where $v_{i}$ are the coordinates of the vector $v\in\mathbb{F}_{q}^{n}$,
$i=1,\ldots,n$. This is a homomorphism and the kernel of $\psi$ is the subcode
$E_{\sigma}(C)$, or $\ker\psi=E_{\sigma}(C)$.

Instead of studying linear codes over rings that are Cartesian products of
different factor rings, we prefer to focus on some specific cases. Sylow’s
first theorem gives us a reason to narrow down the considered cases. More
precisely, we use the corollary, also known as Cauchy’s theorem.

######  Theorem 2.1.

(Cauchy) Given a finite group $G$ and a prime number $r$ dividing the order of
$G$, then there exists an element (and thus a cyclic subgroup generated by
this element) of order $r$ in $G$.

This means that if a linear code has a nontrivial automorphism group, it has
an automorphism of prime order. Therefore, if we need to classify all codes
with given parameters, having a nontrivial automorphism group, it is
sufficient to consider only the automorphisms of prime orders. However, one
can get many more results by combining automorphisms and from this point of
view study codes with automorphisms of composite order or codes invariant
under the action of a given group (see for example [5, 6, 30], as well as the
examples in Section 5).

In this work, we focus on one automorphism of a linear code without
considering its interaction with other automorphisms. The following lemma
gives us a partial motivation to consider only permutational automorphisms,
especially when their order is prime.

######  Lemma 2.2.

[23, W. C. Huffman] Let $C$ be a linear code over $\mathbb{F}_{q}$ with an
automorphism $T=PD\tau$ of prime order $r$ where $r\nmid(q-1)$ and
$r\nmid|{\rm Gal}(\mathbb{F}_{q})|$. Then there exists a code $C^{\prime}$
equivalent to $C$ where $P\in\mathrm{Aut}(C^{\prime})$.

By $\mathbf{1}$ and $\mathbf{0}$ we denote the all-ones vectors and the zero
vector of the corresponding length, respectively.

##  3\. Permutation automorphisms of order $m$ relatively prime to the
characteristic of the field

Let $\gcd(m,\textrm{char}(\mathbb{F}_{q}))=1$. The following theorem gives a
very important information about the structure of a linear code $C$ having a
permutation automorphism of order $m$.

######  Theorem 3.1.

Let $C\leq\mathbb{F}_{q}^{n}$ be a linear code with a permutation automorphism
$\sigma\in\textrm{Sym}(n)$ of order $m$ such that $\gcd(m,q)=1$. Then
$C=F_{\sigma}(C)\oplus E_{\sigma}(C)$. Both $F_{\sigma}(C)$ and
$E_{\sigma}(C)$ are $\sigma$-invariant and orthogonal to each other.

###### Proof.

Take an arbitrary codeword $v\in C$ and consider
$w=\sum_{i=0}^{m-1}v\sigma^{i}$. Since $v\sigma^{m}=v$, $w\sigma=w$ and so
$w\in F_{\sigma}(C)$. Let $x=v-\frac{1}{m}w$. If
$v|_{\Omega_{i}}=(v_{i1},\ldots,v_{il_{i}})$ then
$w|_{\Omega_{i}}=\frac{m}{l_{i}}(\sum_{j=1}^{l_{i}}v_{ij},\ldots,\sum_{j=1}^{l_{i}}v_{ij})$.
Hence

$x|_{\Omega_{i}}=(v_{i1}-\frac{1}{l_{i}}\sum_{j=1}^{l_{i}}v_{ij},\ldots,v_{il_{i}}-\frac{1}{l_{i}}\sum_{j=1}^{l_{i}}v_{ij})\;\Longrightarrow\;\sum_{j=1}^{l_{i}}x_{j}=\sum_{j=1}^{l_{i}}v_{ij}-\sum_{j=1}^{l_{i}}v_{ij}=0.$

It follows that $x\in E_{\sigma}(C)$ and so $v=\frac{1}{m}w+x\in
F_{\sigma}(C)+E_{\sigma}(C)$. This proves that
$C=F_{\sigma}(C)+E_{\sigma}(C)$.

If $v\in F_{\sigma}(C)\cap E_{\sigma}(C)$, then
$v|_{\Omega_{i}}=(\underbrace{\alpha,\ldots,\alpha}_{l_{i}})=\alpha\mathbf{1}$
and $\alpha(\underbrace{1+\cdots+1}_{l_{i}})=l_{i}\alpha=0$. Hence $\alpha=0$,
$v=\mathbf{0}$, $F_{\sigma}(C)\cap E_{\sigma}(C)=\\{\mathbf{0}\\}$ and
therefore $C=F_{\sigma}(C)\oplus E_{\sigma}(C)$. Obviously, both subcodes are
$\sigma$-invariant.

If $v\in E_{\sigma}(C)$ and $w\in F_{\sigma}(C)$,
$w|_{\Omega_{i}}=w_{i}\mathbf{1}$ for $i=1,\ldots,s$, then

$(v,w)=\sum_{i=1}^{s}(w_{i}^{\prime}\sum_{j\in\Omega_{i}}v_{j})=0,$

where $w_{i}^{\prime}=w_{i}$ in the case of Euclidean inner product, and
$w_{i}^{\prime}=\overline{w}_{i}$ if the inner product is Hermitian. Hence
both subcodes are orthogonal to each other. ∎

The following theorem proves important properties of the projection code
$C_{\pi}=\pi(F_{\sigma}(C))$ if $C$ is a self-dual or LCD code with respect to
the considered inner product.

######  Theorem 3.2.

Assume $l_{1}\equiv l_{2}\equiv\cdots\equiv l_{s}\equiv l\not\equiv
0\pmod{p}$. Then:

  * (1)

if $C$ is self-orthogonal so is $C_{\pi}$;

  * (2)

if $C$ is self-dual so is $C_{\pi}$;

  * (3)

if $C$ is LCD so is $C_{\pi}$.

###### Proof.

If $v=(v_{1},\ldots,v_{n})$, by $v^{\prime}$ we denote the vector $v$ if the
considered inner product is Euclidean, and the vector
$\overline{v}=(\overline{v}_{1},\ldots,\overline{v}_{n})$, if the inner
product is Hermitian.

Let
$v=(\underbrace{v_{1},\ldots,v_{1}}_{l_{1}},\ldots,\underbrace{v_{s},\ldots,v_{s}}_{l_{s}})$
and
$w=(\underbrace{w_{1},\ldots,w_{1}}_{l_{1}},\ldots,\underbrace{w_{s},\ldots,w_{s}}_{l_{s}})$
be codewords in $F_{\sigma}(C)$. Then

$(v,w)=\sum_{i=1}^{s}l_{i}v_{i}w_{i}^{\prime}=l\sum_{i=1}^{s}v_{i}w_{i}^{\prime}=l(\pi(v),\pi(w)).$

  * (1)

If $C$ is a self-orthogonal code, then $(v,w)=0$ for any two codewords $v,w\in
F_{\sigma}(C)$. Hence $(\pi(v),\pi(w))=0$ $\forall v,w\in F_{\sigma}(C)$ and
therefore $C_{\pi}$ is also self-orthogonal.

  * (2)

Let $C$ be a self-dual code. Hence $C$ is also self-orthogonal and therefore
$C_{\pi}$ is a self-orthogonal code, or $C_{\pi}\subseteq C_{\pi}^{\perp}$.
Take $w=(w_{1},\ldots,w_{s})\in C_{\pi}^{\perp}$, and
$w_{F}=(\underbrace{w_{1},\ldots,w_{1}}_{l_{1}},\ldots,\underbrace{w_{s},\ldots,w_{s}}_{l_{s}})\in\mathbb{F}_{q}^{n}$.
Then

$(v,w_{F})=l(\pi(v),w)=0\;\forall v\in F_{\sigma}(C).$

Furthermore,

$(u,w_{F})=\sum_{i=1}^{s}(w^{\prime}_{i}\sum_{j\in\Omega_{i}}u_{j})=0\;\forall
u\in E_{\sigma}(C).$

Hence, $w_{F}\perp C$ and so $w_{F}\in C^{\perp}=C$. It follows that $w_{F}\in
F_{\sigma}(C)$ and $w\in C_{\pi}$. This proves that $C_{\pi}^{\perp}=C_{\pi}$
and so $C_{\pi}$ is a self-dual code.

  * (3)

Consider now the case of an LCD code $C$. Take $w=(w_{1},\ldots,w_{s})\in
C_{\pi}\cap C_{\pi}^{\perp}$, and
$w_{F}=\pi^{-1}(w)=(\underbrace{w_{1},\ldots,w_{1}}_{l_{1}},\ldots,\underbrace{w_{s},\ldots,w_{s}}_{l_{s}})$.
Then $w_{F}\in F_{\sigma}(C)$ and

$(v,w_{F})=l(\pi(v),w)=0\;\forall v\in F_{\sigma}(C).$

Hence $w_{F}\perp F_{\sigma}(C)$ and $w_{F}\perp E_{\sigma}(C)$, which means
that $w_{F}\in C^{\perp}\cap C$. Since $C$ is an LCD code, $w_{F}=\mathbf{0}$
and so $w$ is the zero vector. It follows that $C_{\pi}\cap
C_{\pi}^{\perp}=\\{\mathbf{0}\\}$ and $C_{\pi}$ is an LCD code.

Thus the theorem is proved. ∎

Next, we focus on quasi-cyclic and almost quasi-cyclic codes.

###  3.1. Quasi-cyclic codes

This is the case when $l_{1}=l_{2}=\ldots=l_{s}=m$ and $n=sm$. Then for the
fixed subcode we have the following corollary, that follows from Theorem 3.2.

######  Corollary 3.3.

Let $C$ be a $q$-ary quasi-cyclic code of length $sm$ and index $s$, where
$\gcd(m,q)=1$. Then:

  * (1)

if $C$ is self-orthogonal so is $C_{\pi}$;

  * (2)

if $C$ is self-dual so is $C_{\pi}$;

  * (3)

if $C$ is LCD so is $C_{\pi}$.

If $m$ and $q$ are relatively prime, so $p\nmid m$, $x^{m}-1$ can be written
in the form [26]

(3.1) $x^{m}-1=\delta g_{0}(x)g_{1}(x)\cdots
g_{r}(x)h_{1}(x)h_{1}^{*}(x)\cdots h_{t}(x)h_{t}^{*}(x),$

where $\delta\in\mathbb{F}_{q}^{*}$, $g_{0}=x-1$, $g_{1},\ldots,g_{r}$ are
associated with their reciprocal polynomials, and $h_{i}^{*}(x)$ is the
reciprocal polynomial of $h(x)$, $i=1,\ldots,t$. Then

$\mathcal{R}_{m}=(\bigoplus_{i=0}^{r}\mathbb{F}_{q}[x]/(g_{i}))\oplus(\bigoplus_{i=1}^{t}(\mathbb{F}_{q}[x]/(h_{i})\oplus\mathbb{F}_{q}[x]/(h^{*}_{i})),$

and $\mathbb{F}_{q}[x]/(g_{i})$, $i=0,1,\ldots,r$, $\mathbb{F}_{q}[x]/(h_{i})$
and $\mathbb{F}_{q}[x]/(h^{*}_{i})$, $j=1,\ldots,t$, are fields (extensions of
$\mathbb{F}_{q}$). In some cases it is more suitable to consider these fields
as minimal ideals in $\mathcal{R}_{m}$, generated respectively by the
polynomials $\frac{x^{m}-1}{g_{i}(x)}$, $i=0,1,\ldots,r$,
$\frac{x^{m}-1}{h_{j}(x)}$ and $\frac{x^{m}-1}{h_{j}^{*}(x)}$, $j=1,\ldots,t$.
Denote these ideals by $G_{0},G_{1},\ldots,G_{r}$, $H_{1}^{\prime}$,
$H_{1}^{\prime\prime}$, $\ldots,H_{t}^{\prime}$, $H_{t}^{\prime\prime}$,
respectively, and so

$\mathcal{R}_{m}=(\bigoplus_{i=0}^{r}G_{i})\oplus(\bigoplus_{i=1}^{t}(H_{j}^{\prime}\oplus
H_{j}^{\prime\prime}).$

In this case the map $\phi$ is defined in the following way:

$\phi:\mathbb{F}_{q}^{ms}\to\mathcal{R}_{m}^{s},\;\phi(c)=(c_{1}(x),\ldots,c_{s}(x))$

######  Lemma 3.4.

[26, Lemma 3.1] The map $\phi$ induces a one-to-one correspondence between
quasi-cyclic codes over $\mathbb{F}_{q}$ of index $s$ and length $ms$ and
linear codes over $\mathcal{R}_{m}$ of length $s$.

Since

$\mathcal{R}_{m}^{s}=(\bigoplus_{i=0}^{r}G_{i}^{s})\oplus(\bigoplus_{i=1}^{t}(H_{j}^{\prime
s}\oplus H_{j}^{\prime\prime s}),$

then

$\phi(C)=(\bigoplus_{i=0}^{r}C_{i})\oplus(\bigoplus_{i=1}^{t}(C_{j}^{\prime}\oplus
C_{j}^{\prime\prime}),$

where $C_{i}$ is a linear code over $G_{i}$, $i=0,1,\ldots,r$,
$C_{j}^{\prime}$ and $C_{j}^{\prime\prime}$ are linear codes over
$H_{j}^{\prime}$ and $H_{j}^{\prime\prime}$, respectively, $j=1,\ldots,t$, all
of length $s$.

Since $G_{0}=(1+x+\cdots+x^{m-1})\lhd\mathcal{R}_{m}$,
$G_{0}\cong\mathbb{F}_{q}[x]/(x-1)\cong\mathbb{F}_{q}$, $\phi^{-1}(C_{0})$ is
actually the fixed subcode $F_{\sigma}(C)$, and

$\phi(E_{\sigma}(C))=(\bigoplus_{i=1}^{r}C_{i})\oplus(\bigoplus_{i=1}^{t}(C_{j}^{\prime}\oplus
C_{j}^{\prime\prime}).$

In $\mathcal{R}_{m}^{s}$, we use the Hermitian inner product, defined in [26],
namely

(3.2) $(u,v)=\sum_{i=1}^{s}u_{i}\overline{v_{i}}\ \ \mbox{for}\
u=(u_{1},\ldots,u_{s}),\ v=(v_{1},\ldots,u_{s}),$

where $\overline{v_{i}}=v_{i}(x^{-1})=v_{i}(x^{m-1}).$ Note that
$\overline{v_{i}}\in G_{j}$ if $v_{i}\in G_{j}$, $0\leq j\leq r$,
$\overline{v_{i}}\in H_{j}^{\prime\prime}$ if $v_{i}\in H_{j}^{\prime}$, and
$\overline{v_{i}}\in H_{j}^{\prime}$ if $v_{i}\in H_{j}^{\prime\prime}$,
$1\leq j\leq t$. Actually, this inner product is Euclidean over
$G_{0}\cong\mathbb{F}_{q}$.

The following theorem follows from [26, Theorem 4.2].

######  Theorem 3.5.

The linear code $C$ is Euclidean self-dual $q$-ary code if and only if
$C_{\pi}=C_{0}$ is Euclidean self-dual, $C_{i}$ for $i=1,\ldots,r$ are
Hermitian self-dual codes, and $C_{j}^{\prime\prime}=(C_{j}^{\prime})^{\perp}$
for $j=1,\ldots,t$ with respect to the Euclidean inner product.

This theorem gives us the following corollaries.

######  Corollary 3.6.

The linear code $C$ is Euclidean self-orthogonal $q$-ary code if and only if
$C_{\pi}=C_{0}$ is Euclidean self-orthogonal, $C_{i}$ for $i=1,\ldots,r$ are
Hermitian self-orthogonal codes, and
$C_{j}^{\prime\prime}\subseteq(C_{j}^{\prime})^{\perp}$ for $j=1,\ldots,t$
with respect to the Euclidean inner product.

######  Corollary 3.7.

The linear code $C$ is Euclidean LCD $q$-ary code if and only if
$C_{\pi}=C_{0}$ is Euclidean LCD code, $C_{i}$ for $i=1,\ldots,r$ are
Hermitian LCD codes,
$C_{j}^{\prime\prime}\cap(C_{j}^{\prime})^{\perp}=\\{\mathbf{0}\\}$ and
$C_{j}^{\prime}\cap(C_{j}^{\prime\prime})^{\perp}=\\{\mathbf{0}\\}$ for
$j=1,\ldots,t$ with respect to the Euclidean inner product.

###  3.2. Almost quasi-cyclic codes

Let $C$ be a linear code with a permutation automorphism
$\sigma\in\textrm{Sym}(n)$ of order $m$ (not necessarily prime) with $c$
cycles of length $m$ and $f$ fixed points. We call such code almost quasi-
cyclic. In this case, we say that $\sigma$ is of type $m$-$(c,f)$. Without
loss of generality we can assume that

(3.3) $\sigma=\Omega_{1}\dots\Omega_{c}\Omega_{c+1}\dots\Omega_{c+f}$

where $\Omega_{i}=((i-1)m+1,\dots,im),i=1,\dots,c$, are the cycles of length
$r$, and $\Omega_{c+i}=(cm+i),i=1,\dots,f$, are the fixed points. Obviously,
$cm+f=n$. Almost quasi-cyclic codes are a special case of generalized quasi-
cyclic codes, but we consider them separately because the decomposition given
above is not very useful, since the constituents that correspond to the fixed
points are codes of length 1. Therefore, in this subsection we focus on the
subcodes $F_{\sigma}(C)$ and $E_{\sigma}(C)$ in more detail here. Theorem 3.2
gives us the following statement.

######  Corollary 3.8.

Let $m\equiv 1\pmod{p}$. Then:

  * (1)

if $C$ is self-orthogonal so is $C_{\pi}$;

  * (2)

if $C$ is self-dual so is $C_{\pi}$;

  * (3)

if $C$ is LCD so is $C_{\pi}$.

If $v\in E_{\sigma}(C)$ then $v|_{\Omega_{j}}=0$ for $j=c+1,\ldots,c+f$.
Denote by $E_{\sigma}(C)^{*}$ the code obtained from $E_{\sigma}(C)$ by
deleting the last $f$ coordinates. Since $E_{\sigma}(C)^{*}$ is a quasi-cyclic
$q$-ary code of length $cm$ and index $c$, we can use the decomposition given
in the previous subsection. All codewords of $C$ that $\sigma$ preserves
belong to the subcode $F_{\sigma}(C)$, therefore for the code
$C_{\phi}=\phi(E_{\sigma}(C)^{*})$ we have

$C_{\phi}=(\bigoplus_{i=1}^{r}C_{i})\oplus(\bigoplus_{i=1}^{t}(C_{j}^{\prime}\oplus
C_{j}^{\prime\prime}),$

where $C_{i}$ is a linear code over $G_{i}$, $i=1,\ldots,r$, $C_{j}^{\prime}$
and $C_{j}^{\prime\prime}$ are linear codes over $H_{j}^{\prime}$ and
$H_{j}^{\prime\prime}$, respectively, $j=1,\ldots,t$, all of length $c$.
Theorem 3.1 gives us the following corollary.

######  Corollary 3.9.

The code $C$ having an automorphism $\sigma$ given in (3.3) is self-orthogonal
(resp. LCD) code if and only if $F_{\sigma}(C)$ and $E_{\sigma}(C)^{*}$ are
self-orthogonal (resp. LCD).

###### Proof.

Obviously, $E_{\sigma}(C)$ is an orthogonal (resp. LCD) code if and only if
the code $E_{\sigma}(C)^{*}$ is self-orthogonal (resp. LCD).

If $C$ is a self-orthogonal code, all its subcodes are also self-orthogonal.
Conversely, if $F_{\sigma}(C)$ and $E_{\sigma}(C)^{*}$ are self-orthogonal
codes then $E_{\sigma}(C)$ is also self-orthogonal, and since
$F_{\sigma}(C)\perp E_{\sigma}(C)$, the code $C=F_{\sigma}(C)\oplus
E_{\sigma}(C)$ is self-orthogonal.

In the case of LCD codes, we will prove that if $C=C_{1}\oplus C_{2}$ and
$C_{1}\perp C_{2}$, then $C$ is an LCD code if and only if both $C_{1}$ and
$C_{2}$ are LCD codes.

$\Rightarrow)$ Let $C$ be an LCD code. If $w=(w_{1},\ldots,w_{n})\in C_{1}\cap
C_{1}^{\perp}$ then $w\perp C_{1}$ and $w\perp C_{2}$. This gives us that
$w\perp C$ and so $w\in C\cap C^{\perp}$. Hence $w=0$ and $C_{1}$ is an LCD
code. The same holds for the code $C_{2}$.

$\Leftarrow)$ Let $C_{1}$ and $C_{2}$ be LCD codes, and $x\in C\cap
C^{\perp}$. Since $C=C_{1}\oplus C_{2}$ then $x=x_{1}+x_{2}$, $x_{i}\in
C_{i}$, $i=1,2$. Take $y_{i}\in C_{i}$, $i=1,2$. Then we have $x\cdot y_{i}=0$
and

$x_{i}\cdot y_{i}=(x_{1}+x_{2})\cdot y_{i}=x\cdot y_{i}=0\ \Rightarrow
x_{i}\perp C_{i}\ \Rightarrow x_{i}\in C_{i}\cap C_{i}^{\perp}\ \Rightarrow
x_{i}=0,\ i=1,2.$

This proves that $x=0$ and so $C$ is also an LCD code.

To complete the proof, we take $C_{1}=E_{\sigma}(C)$ and
$C_{2}=F_{\sigma}(C)$. ∎

Combining the corollary with Corollary 3.6 and Corollary 3.7, we prove the
following.

######  Corollary 3.10.

The linear code $C$ is Euclidean self-orthogonal $q$-ary code if and only if
$C_{\pi}$ is Euclidean self-orthogonal, $C_{i}$ for $i=1,\ldots,r$ are
Hermitian self-orthogonal codes, and
$C_{j}^{\prime\prime}\subseteq(C_{j}^{\prime})^{\perp}$ for $j=1,\ldots,t$
with respect to the Euclidean inner product.

######  Corollary 3.11.

The linear code $C$ is Euclidean LCD $q$-ary code if and only if $C_{\pi}$ is
Euclidean LCD code, $C_{i}$ for $i=1,\ldots,r$ are Hermitian LCD codes,
$C_{j}^{\prime\prime}\cap(C_{j}^{\prime})^{\perp}=\\{\mathbf{0}\\}$ and
$C_{j}^{\prime}\cap(C_{j}^{\prime\prime})^{\perp}=\\{\mathbf{0}\\}$ for
$j=1,\ldots,t$ with respect to the Euclidean inner product.

Self-dual almost quasi-cyclic codes was studied by Huffman in [19]. Methods
for construction and classification of self-dual codes with an automorphism of
prime order $m\neq p$ were given in [20, 35] for binary codes, [23] for
ternary codes, [21, 22] for Hermitian quaternary codes. More detailed list
with references on linear codes with automorphism of prime order can be seen
in [24]. Binary LCD codes having an automorphism of odd prime order are
studied in detail in [11]. Some classes of quasi-cyclic codes with
complementary duals are examined in [16].

##  4\. Permutation automorphisms of order $m$ not coprime with the
characteristic of the field

Let $C$ be a linear code over $\mathbb{F}_{q}$, where $q=p^{\ell}$ for a prime
$p$, $\ell\geq 1$, with a permutation automorphism $\sigma\in\textrm{Sym}(n)$
of order $m=p^{a}m^{\prime}$, $a\geq 1$. We again consider $\sigma$ as a
product of $s$ disjoint cycles as in (2.1).

Let us see what happens to the subcodes $F_{\sigma}(C)$ and $E_{\sigma}(C)$ in
this situation.

######  Theorem 4.1.

Let $l_{i}\equiv 0\pmod{p}$ for all $i=1,\ldots,s$. Then $F_{\sigma}(C)$ is a
self-orthogonal code and it is a subcode of $E_{\sigma}(C)$.

This theorem shows that we cannot use the same decomposition as in Section 3
in order to study self-orthogonal, self-dual and/or LCD codes having an
automorphism $\sigma$. We need something different here.

Next, we prove a theorem that holds for the quasi-cyclic codes of length $ms$
and index $s$ for all integers $m=p^{a}m^{\prime}$. A similar theorem for
binary self-dual codes of length $2k$ and index $k$ is proved in [9].

######  Theorem 4.2.

Let $C$ be a $q$-ary quasi-cyclic code of length $sm$ and index $s$. Let
$\psi:C\to\mathbb{F}_{q}^{s}$ be the map defined by

$\psi(c)=(\sum_{i\in\Omega_{1}}c_{i},\ldots,\sum_{i\in\Omega_{s}}c_{i}),$

where $c_{i}$ are the coordinates of the vector $c\in\mathbb{F}_{q}^{n}$,
$i=1,\ldots,n$. If $C$ is a self-orthogonal code then $C_{\psi}=\psi(C)$ is
also self-orthogonal, and $C_{\pi}=\pi(F_{\sigma}(C))\subset
C_{\psi}^{\perp}$. If $C$ is self-dual then $C_{\pi}=C_{\psi}^{\perp}$.

###### Proof.

Let
$c=(c_{11},\ldots,c_{1m},c_{21},\ldots,c_{2m},\ldots,c_{s1},\ldots,c_{sm})\in
C$. Then

$c\sigma=(c_{1m},c_{11},\ldots,c_{1,m-1},c_{2m},c_{21},\ldots,c_{2,m-1},\ldots,c_{sm},c_{s1},\ldots,C_{s,m-1})\in
C.$

For two codewords $u,v\in C$ we have

$(\psi(u),\psi(v))=\sum_{i=1}^{s}(u_{i1}+\cdots+u_{im})(v_{i1}^{\prime}+\cdots+v_{im}^{\prime})=(u,v)+(u,v\sigma)+\cdots+(u,v\sigma^{m-1}).$

If $C$ is a self-orthogonal code, then
$(u,v)=(u,v\sigma)=\cdots=(u,v\sigma^{m-1})=0\forall u,v\in C$. Hence
$(\psi(u),\psi(v))=0$ for all $u,v\in C$.

Furthermore,
$(\psi(u),\pi(v))=\sum_{i=1}^{s}(u_{i1}+\cdots+u_{im})v_{i}^{\prime}=(u,v)$.
Therefore, for a self-orthogonal code $C$, $(\psi(u),\pi(v))=0$ for $u\in C$,
$v\in F_{\sigma}(C)$ and so $C_{\pi}\subset C_{\psi}^{\perp}$.

Now let $C$ be a self-dual code, $v=(v_{1},\ldots,v_{s})\in C_{\psi}^{\perp}$
and

$w=\pi^{-1}(v)=(\underbrace{v_{1},\ldots,v_{1}}_{m},\ldots,\underbrace{v_{s},\ldots,v_{s}}_{m}).$

It follows that

$(u,w)=\sum_{i=1}^{s}(u_{i1}+\cdots+u_{im})v_{i}^{\prime}=(\psi(u),v)=0\;\forall
u\in C.$

Hence, $w\in C^{\perp}=C$ and so $w\in F_{\sigma}(C)$. This proves that $v\in
C_{\pi}$ and therefore $C_{\pi}=C_{\psi}^{\perp}$. ∎

######  Remark 4.3.

Theorem 4.1 holds for all $m\geq 2$ and for all prime powers $q$ (if
corresponding quasi-cyclic codes exist). If $\gcd(m,q)=1$ then the codes
$C_{\psi}$ and $C_{\pi}$ coincide.

Quasi-cyclic codes of length $ms$ and index $s$ in the case
$m=p^{a}m^{\prime}$, $a\geq 1$, $p\nmid m^{\prime}$, are extensively studied
in [27]. The factorization of the polynomial $x^{m}-1$ over $\mathbb{F}_{q}$
plays a key role in this case, too. Since $\gcd(m^{\prime},q)=1$, the
polynomial $x^{m^{\prime}}-1$ can be factorized as in (3.1), namely

$x^{m^{\prime}}-1=\delta g_{0}(x)g_{1}(x)\cdots
g_{r}(x)h_{1}(x)h_{1}^{*}(x)\cdots h_{t}(x)h_{t}^{*}(x).$

Since $x^{m}-1=x^{p^{a}m^{\prime}}-1=(x^{m^{\prime}}-1)^{p^{a}}$, we have

$x^{m}-1=\delta^{p^{a}}g_{0}^{p^{a}}g_{1}^{p^{a}}\cdots
g_{r}^{p^{a}}h_{1}^{p^{a}}(h_{1}^{*})^{p^{a}}\cdots
h_{t}^{p^{a}}(h_{t}^{*})^{p^{a}},$

where $\delta\in\mathbb{F}_{q}^{*}$, $g_{0}=x-1$, $g_{1},\ldots,g_{r}$ are
associated with their reciprocal polynomials, and $h_{i}^{*}(x)$ is the
reciprocal polynomial of $h(x)$, $i=1,\ldots,t$. Consequently, we may now
write

$\mathcal{R}_{m}=(\bigoplus_{i=0}^{r}\mathbb{F}_{q}[x]/(g_{i}^{p^{a}}))\oplus(\bigoplus_{i=1}^{t}(\mathbb{F}_{q}[x]/(h_{i}^{p^{a}})\oplus\mathbb{F}_{q}[x]/((h^{*}_{i})^{p^{a}})).$

If we denote these factor rings by $R_{i}$ for $i=0,1,\ldots,r$,
$R_{j}^{\prime}$ and $R_{j}^{\prime\prime}$ for $j=1,\ldots,t$, respectively,
then

$\mathcal{R}_{m}^{s}=(\bigoplus_{i=0}^{r}R_{i}^{s})\oplus(\bigoplus_{i=1}^{t}(R_{j}^{\prime
s}\oplus R_{j}^{\prime\prime s})).$

In particular, $\mathcal{R}_{m}$-linear code $\mathcal{A}$ of length $s$ can
be decomposed in a direct sum in the following way

$\mathcal{A}=(\bigoplus_{i=0}^{r}\mathcal{A}_{i})\oplus(\bigoplus_{i=1}^{t}(\mathcal{A}^{\prime}_{j}\oplus\mathcal{A}^{\prime\prime}_{j})),$

where $\mathcal{A}_{i}$, $\mathcal{A}_{j}^{\prime}$ and
$\mathcal{A}_{j}^{\prime\prime}$ are linear codes over the rings $R_{i}$,
$R_{j}^{\prime}$ and $R_{j}^{\prime\prime}$, respectively, $i=0,1,\ldots,r$,
$j=1,\ldots,t$. The rings $R_{i}$, $R_{j}^{\prime}$ and $R_{j}^{\prime\prime}$
are finite chain rings. This can be described in the following way (see [27]):
If $f$ is a monic irreducible factor of $x^{m^{\prime}}-1$ of degree $d$ then
the factor ring $\mathbb{F}_{q}[x]/(f^{p^{a}})$ can be identified with the
finite chain ring
$\mathbb{F}_{q^{k}}+u\mathbb{F}_{q^{k}}+\cdots+u^{p^{a}-1}\mathbb{F}_{q^{k}}$,
where $u^{p^{a}}=0$. The detailed description of quasi-cyclic codes in this
case, as well as some interesting examples, are presented in [27], so we will
not consider this theory in more detail, but for completeness we present [27,
Theorem 4.2].

######  Theorem 4.4.

A linear code $C$ over $\mathcal{R}_{m}=\mathbb{F}_{q}[x]/(x^{m}-1)$ of length
$s$ is self-dual with respect to the Hermitian inner product (or equivalently,
an $s$-quasi-cyclic code of length $sm$ over $\mathbb{F}_{q}$ is self-dual
with respect to the Euclidean inner product) if and only if

$C=(\bigoplus_{i=0}^{r}C_{i})\oplus(\bigoplus_{i=1}^{t}(C^{\prime}_{j}\oplus(C^{\prime}_{j})^{\perp})),$

where, for $0\leq i\leq r$, $C_{i}$ is a self-dual code over $R_{i}$ of length
$s$ (with respect to the Hermitian inner product) and, for $1\leq j\leq t$,
$C_{j}^{\prime}$ is a linear code of length $s$ over $R_{j}^{\prime}$ and
$(C^{\prime}_{j})^{\perp}$ is its dual with respect to the Euclidean inner
product.

The binary self-dual codes invariant under a permutation $\sigma$ of order 2
with $c$ independent cycles of length 2 and $f>0$ fixed points are studied in
[10]. A construction method for such codes is proposed which is used to obtain
optimal self-dual codes of different lengths. In [5], the authors prove that
the natural projection of the fixed code of an involution of a self-dual
binary linear code is self-dual under some (quite strong) conditions on the
codes. To prove that, they introduce the family of binary semi self-dual
codes.

##  5\. Examples

In this section, we give three examples of codes constructed using the
presented decomposition. We consider an almost quasi-cyclic binary self-dual
code with an automorphism of order 15, a quasi-cyclic binary self-dual code
with an automorphism of order 10, and an almost quasi-cyclic ternary LCD code
with an automorphism of order 5.

######  Example 5.1.

In the first example we present a binary self-dual almost quasi-cyclic code
$C$ with two 15-cycles and two fixed points. Now $C_{\pi}$ must be a binary
self-dual $[4,2,2]$ code and we take $C_{\pi}=\\{0000,1010,0101,1111\\}$. The
code $E_{\sigma}(C)^{*}$ is a binary quasi-cyclic code of length 30 and index
2, which is self-orthogonal code of dimension 14. Since

$x^{15}-1=(x-1)(x^{2}+x+1)(x^{4}+x^{3}+x^{2}+x+1)(x^{4}+x+1)(x^{4}+x^{3}+1),$

where $g_{1}(x)=x^{2}+x+1$ and $g_{2}(x)=x^{4}+x^{3}+x^{2}+x+1$ are self-
reciprocal polynomials, and $h(x)=x^{4}+x+1$ and $h^{*}(x)=x^{4}+x^{3}+1$ are
mutually reciprocal polynomials over $\mathbb{F}_{2}$. It follows that

$\mathcal{R}_{15}=\mathbb{F}_{2}[x]/(g_{0})\oplus\mathbb{F}_{2}[x]/(g_{1})\oplus\mathbb{F}_{2}[x]/(g_{2})\oplus\mathbb{F}_{2}[x]/(h)\oplus\mathbb{F}_{2}[x]/(h^{*}).$

Instead of the factor-rings in the above formula, we use the corresponding
ideals of ${\mathcal{R}}_{m}$:

$G_{1}=\langle\frac{x^{15}-1}{g_{1}(x)}\rangle\cong\mathbb{F}_{4},\;G_{2}=\langle\frac{x^{15}-1}{g_{2}(x)}\rangle\cong\mathbb{F}_{16},$
$H^{\prime}=\langle\frac{x^{15}-1}{h(x)}\rangle\cong\mathbb{F}_{16},\;H^{\prime\prime}=\langle\frac{x^{15}-1}{h^{*}(x)}\rangle\cong\mathbb{F}_{16}.$

The generating idempotents of these fields are
$e_{1}(x)=x^{14}+x^{13}+x^{11}+x^{10}+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x\in
G_{1}$,
$e_{2}(x)=x^{14}+x^{13}+x^{12}+x^{11}+x^{9}+x^{8}+x^{7}+x^{6}+x^{4}+x^{3}+x^{2}+x\in
G_{2}$, $e^{\prime}(x)=x^{12}+x^{9}+x^{8}+x^{6}+x^{4}+x^{3}+x^{2}+x\in
H^{\prime}$ and
$e^{\prime\prime}(x)=e^{\prime}(x^{-1})=x^{14}+x^{13}+x^{12}+x^{11}+x^{9}+x^{7}+x^{6}+x^{3}\in
H^{\prime\prime}$. For the code $C_{\phi}$ we have

$C_{\phi}=C_{1}\oplus C_{2}\oplus C^{\prime}\oplus C^{\prime\prime},$

where $C_{i}$ is a Hermitian self-dual code over $G_{i}$, $i=1,2$,
$C^{\prime}$ and $C^{\prime\prime}$ are mutually orthogonal linear codes over
$H^{\prime}$ and $H^{\prime\prime}$, respectively, with respect to the
Euclidean inner product. We take $C_{i}=\langle(e_{i}(x),e_{i}(x))\rangle$,
$i=1,2$, $C^{\prime}=(H^{\prime})^{2}$, and so $C^{\prime\prime}$ is the zero
code. The constructed binary code is doubly-even self-dual $[32,16,8]$ code
with a generator matrix $gen_{1}$, and its weight enumerator is
$1+620y^{8}+13888y^{12}+36518y^{16}+13888y^{20}+620y^{24}+y^{32}$.

$gen_{1}=\footnotesize{\begin{pmatrix}01101101101101101101101101101100\\\
10110110110110110110110110110100\\\ 01111011110111101111011110111100\\\
10111101111011110111101111011100\\\ 11011110111101111011110111101100\\\
11101111011110111101111011110100\\\ 01111010110010000000000000000000\\\
00111101011001000000000000000000\\\ 00011110101100100000000000000000\\\
10001111010110000000000000000000\\\ 00000000000000001111010110010000\\\
00000000000000000111101011001000\\\ 00000000000000000011110101100100\\\
00000000000000010001111010110000\\\ 11111111111111100000000000000010\\\
00000000000000011111111111111101\end{pmatrix}}$

######  Example 5.2.

We consider again a binary self-dual code $C$ but this time we use a
permutation automorphism $\sigma$ with four 10-cycles. Since

$x^{10}-1=(x-1)^{2}(x^{4}+x^{3}+x^{2}+x+1)^{2}$

over $\mathbb{F}_{2}$, for the ring $\mathcal{R}_{10}$ we have

$\mathcal{R}_{10}=\mathbb{F}_{2}[x]/((x-1)^{2})\oplus\mathbb{F}_{2}[x]/((x^{4}+x^{3}+x^{2}+x+1)^{2}).$

According to Theorem 4.4, $\phi(C)=C_{0}\oplus C_{1}$, where $C_{i}$ is a
linear Hermitian self-dual code over $G_{i}$, $i=0,1$,
$G_{0}=<(x^{4}+x^{3}+x^{2}+x+1)^{2}>\cong\mathbb{F}_{2}[x]/((x-1)^{2})$,
$G_{1}=<(x-1)^{2}>\cong\mathbb{F}_{2}[x]/((x^{4}+x^{3}+x^{2}+x+1)^{2})$. The
structure of the rings $G_{0}$ and $G_{1}$ is as follows:

$G_{0}=\\{0,e=1+x^{2}+x^{4}+x^{6}+x^{8},u=1+x+\cdots+x^{9},e+u\\}=\mathbb{F}_{2}+u\mathbb{F}_{2},$
$G_{1}=\mathbb{F}_{16}+u^{\prime}\mathbb{F}_{16},\;u^{\prime}=1+x^{4}+x^{5}+x^{9},\;\mathbb{F}_{16}^{*}=\\{\beta^{i}:\;\beta=1+x^{2},\;i=0,\ldots,14\\}.$

The identity element of $G_{1}$ is $e^{\prime}=x^{2}+x^{4}+x^{6}+x^{8}=1+e$.
The Euclidean and Hermitian inner products in $G_{0}$ are the same, as
$e(x^{-1})=e(x)$ and $u(x^{-1})=u(x)$. Taking the codes

$C_{0}=\langle\begin{pmatrix}e&0&e&u\\\ 0&e&u&e\end{pmatrix}\rangle\ \ \
\mbox{and}\ \ \
C_{1}=\langle\begin{pmatrix}e^{\prime}&e^{\prime}&u^{\prime}&0\\\
0&xu^{\prime}&e^{\prime}&e^{\prime}\\\ u^{\prime}&u^{\prime}&0&0\\\
0&0&u^{\prime}&u^{\prime}\end{pmatrix}\rangle,$

we obtain a binary quasi-cyclic self-dual $[40,20,8]$ doubly-even code whose
automorphism group has order 245760. The code $C_{0}$ is the only Type II code
over $\mathbb{F}_{2}+u\mathbb{F}_{2}$ up to equivalence [14].

The third example presents a ternary LCD code.

######  Example 5.3.

If $C$ is a ternary LCD code of length 18 having an automorphism of order 5
with three 5-cycles and three fixed points, its subcodes $F_{\sigma}(C)$ and
$E_{\sigma}(C)$ are also LCD codes, $C_{\pi}$ is a ternary code of length 6,
and $C_{\phi}$ is an LCD code of length 3 with respect to the Hermitian inner
product over the field $\mathbb{F}_{3}[x]/(x^{4}+x^{3}+x^{2}+x+1)$ with
$3^{4}$ elements. This field is described in detail in [23], where Huffman has
used it to construct ternary self-dual codes.

We take $C_{\pi}=\langle\begin{pmatrix}110011\\\ 001110\end{pmatrix}\rangle$
and $C_{\phi}=\langle\begin{pmatrix}e&e&0\\\ 0&\alpha&e\end{pmatrix}\rangle$,
where $e=2+x+x^{2}+x^{3}+x^{4}$, $\alpha=x^{3}+2x^{4}$. The constructed
$[18,10]$ code has minimum distance 4 and a generator matrix $gen_{3}$.

$gen_{3}=\footnotesize{\begin{pmatrix}111111111100000&011\\\
000000000011111&110\\\ 211112111100000&000\\\ 121111211100000&000\\\
112111121100000&000\\\ 111211112100000&000\\\ 000000001221111&000\\\
000002000112111&000\\\ 000001200011211&000\\\
000000120011121&000\end{pmatrix}}\ \ \ \
gen_{4}=\footnotesize{\begin{pmatrix}111111111100000&011\\\
000000000011111&111\\\ 211112111100000&000\\\ 121111211100000&000\\\
112111121100000&000\\\ 111211112100000&000\\\ 000000001221111&000\\\
000002000112111&000\\\ 000001200011211&000\\\
000000120011121&000\end{pmatrix}}$

It is worth noting that $5\not\equiv 1\pmod{3}$ and the code $C_{\pi}$ is not
necessarily LCD. For example, if we take
$C_{\pi}=\langle\begin{pmatrix}110011\\\ 001111\end{pmatrix}\rangle$, which is
not an LCD code, with the same $C_{\phi}$, we get another $[18,10,4]$ LCD
ternary code with a generator matrix $gen_{4}$. The first code contains 30
codewords of weight 4, while the second code has 40 codewords with minimum
weight. This example shows that the condition on $m$ in Corollary 3.8 is
important.

##  6\. Conclusion

The decomposition of the linear codes that have non-trivial permutation
automorphisms gives us a powerful construction for codes with optimal
parameters and important properties. Many optimal self-dual codes with
automorphisms of prime order over fields with 2, 3 or 4 elements are obtained
using their previously known structure [20, 23, 22, 35].

As a conclusion, we would like to present what is known so far about the
automorphisms of the putative binary self-dual $[72,36,16]$ code. The extremal
self-dual codes of length a multiple of $24$ are of particular interest, but
only two such codes are known so far - the extended Golay code $g_{24}$ and
the extended quadratic residue code $q_{48}$ (see [31, 18]). In 1973 Sloane
[34] posed a question which remains unresolved: is there a binary self-dual
doubly-even $[72,36,16]$ code? The automorphism group of the extended Golay
code is the 5-transitive Mathieu group $M_{24}$ of order $2^{10}\cdot
3^{3}\cdot 5\cdot 7\cdot 11\cdot 23$ (see [3]), as the automorphism group of
$q_{48}$ is only 2-transitive and is isomorphic to the projective special
linear group $\mathrm{PSL(2,47)}$ of order $2^{4}\cdot 3\cdot 23\cdot 47$
[25]. The first authors to study the automorphism group of the putative
$[72,26,16]$ code were Conway and Pless [13], in particular they focused on
the possible automorphisms of odd prime order. The last published result on
this group so far is given in [7] and we present it in the following theorem.

######  Theorem 6.1.

If $C$ be self-dual $[72,36,16]$ code, then $\mathrm{Aut}(C)$ is trivial or
isomorphic to $C_{2}$, $C_{3}$, $C_{2}\times C_{2}$ or $C_{5}$.

So, if such a code exists, it may be very difficult to find it by algebraic
techniques. Many authors have tried combinatorial methods to construct such a
code, also using its connections with combinatorial designs and Hadamard
matrices [2, 8], but all the resulting codes have minimum distance $d\leq 12$.
Although efforts to obtain such a code by permutation of a given order have so
far been unsuccessful, the method for constructing self-dual, self-orthogonal
and LCD codes has been used many times and many new codes have been introduced
through it. So studying the structure of linear codes with permutation
automorphisms provides a powerful method to investigate, construct and
classify codes with given properties and parameters.

## References

  * [1] R. Anstee, M.Hall Jr. and J.G.Thompson, Planes of order 10 do not have a collineation of order 5, _Journ. Combin. Theory_ , ser. A, 29 (1980), 39-58.
  * [2] E.F. Assmus and H.F. Mattson, New $5$-designs, J. Combin. Theory, 6 (1969), 122–151.
  * [3] E.R. Berlekamp, Coding theory and the Mathieu groups, Info. Control, 18 (1971), 40-64.
  * [4] Berman S.D. (1967). Semisimple cyclic and Abelian codes. II. Kibernetika (Kiev) no. 3, 21-30 (Russian).
  * [5] M. Borello and G. Nebe, On involutions in extremal self-dual codes and the dual distance of semi self-dual codes, _Finite Fields and Their Applications_ , 33 (2015), 80–89.
  * [6] M. Borello and W. Willems, Automorphisms of Order $2p$ in Binary Self-Dual Extremal Codes of Length a Multiple of 24, IEEE Trans. Inf. Theory, 59(6) (2013), 3378–3383.
  * [7] M. Borello, On automorphism groups of binary linear codes, in _Topics in Finite Fields_ , Contemporary Mathematics, 632 (2015), 29–42.
  * [8] I. Bouyukliev, V. Fack, J. Winne, $2-(31,15,7)$, $2-(35,17,8)$ and $2-(36,15,6)$ designs with automorphisms of odd prime order, and their related Hadamard matrices and codes, _Des. Codes Cryptogr._ , 51 (2009), 105–22.
  * [9] S.Buyuklieva, On the binary self-dual codes with an automorphism of order 2, Designs, Codes and Cryptography, 12 (1997), 39-48.
  * [10] S.Buyuklieva, A method for constructing self-dual codes with an automorphism of order 2, IEEE Trans. Inf. Theory, 46(2) (2000), 496–504.
  * [11] S. Bouyuklieva, J. de la Cruz, On the Structure of Binary LCD Codes having an Automorphism of Odd Prime Order, IEEE Trans. Inf. Theory, 68(10) (2022), 6426–6433.
  * [12] S. Bouyuklieva, A. Malevich and W. Willems, Automorphisms of extremal self-dual codes, _IEEE Trans. Inform. Theory_ , 56 (2010), 2091–2096.
  * [13] J.H. Conway and V. Pless, On primes dividing the group order of a doubly-even (72,36,16) code and the group order of a quaternary (24,12,10) code, Discrete Math., 38, pp. 143-156, 1982.
  * [14] S. T. Dougherty, P. Gaborit, M. Harada and P. Sole, Type II codes over $\mathbb{F}_{2}+u\mathbb{F}_{2}$, IEEE Trans. Inf. Theory, 45(1) (1999), 32–45.
  * [15] M. Esmaeili and S. Yari, Generalized quasi-cyclic codes: structural properties and code construction, _Appl. Algebra Eng. Commun. Comput._ , 20 (2009), pp. 159-173.
  * [16] M. Esmaeili and S. Yari, On complementary-dual quasi-cyclic codes, _Finite Fields and Their Applications_ , 15(3) (2009), 375–386.
  * [17] Cem Güneri, Ferruh Özbudak, Buket Özkaya, Elif Saçikara, Zahra Sepasdar, Patrick Solé, Structure and performance of generalized quasi-cyclic codes, _Finite Fields and Their Applications_ , 47 (2017), 183-202.
  * [18] S.H. Houghton, C.W.H. Lam, L.H. Thiel and J.A. Parker, The extended quadratic residue code is the only $[48,24,12]$ self-dual doubly-even code, IEEE Trans. Inform. Theory, 49 (2003), 53–59.
  * [19] W.C.Huffman, Decomposing and shortening codes using automorphisms, IEEE Trans. Inform. Theory 32 (1986), 833-836.
  * [20] W.C. Huffman, Automorphisms of Codes with Applications to Extremal Doubly Even Codes of Length 48, IEEE Trans. Inf. Theory, 28 (1982), 511-521.
  * [21] W.C. Huffman, On extremal self-dual quaternary codes of lengths 18 to 28, I, IEEE Trans. Inform. Theory, 36 (1990), 651-660.
  * [22] W.C. Huffman, On extremal self-dual quaternary codes of lengths 18 to 28, II, IEEE Trans. Inf. Theory, 37 (1991), 1206-1216.
  * [23] W. C. Huffman, On extremal self-dual ternary codes of lengths 28 to 40, IEEE Trans. Inf. Theory, 38(4) (1992), 1395-1400.
  * [24] W. C. Huffman, Self-dual $\mathbb{F}_{q}$-linear $\mathbb{F}_{q^{t}}$-codes with an automorphism of prime order, Advances in Mathematics of Communications, 7(1) (2013), 57-90.
  * [25] W. Knapp and P. Schmid, Codes with prescribed permutation group, J. Algebra, 67 (1980), 415-435.
  * [26] S. Ling and P. Solé, On the algebraic structure of quasi-cyclic codes I: Finite fields, IEEE Trans. Inform. Theory 47 (2001), 2751–2760.
  * [27] S. Ling, H. Niederreiter and P. Solé, On the Algebraic Structure of Quasi-cyclic Codes IV: Repeated Roots, Designs, Codes and Cryptography 38 (2006), 337–361.
  * [28] MacWilliams, F. J. (1969). Codes and ideals in group algebras. Combinatorial mathematics and its applications, 317, 328.
  * [29] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
  * [30] G. Nebe, On Extremal Self-Dual Ternary Codes of Length 48, International Journal of Combinatorics, 2012.
  * [31] V. Pless, On the uniqueness of the Golay codes, J. Combin. Theory, 5 (1968), 215-228.
  * [32] V.Pless, W. C. Huffman, Handbook of Coding Theory, Elsevier, Amsterdam, 1998.
  * [33] I. Siap and N. Kulhan, The structure of generalized quasi-cyclic codes, _Appl. Math. E-Notes_ , 5 (2005), 24-30.
  * [34] N.J.A. Sloane, Is there a (72,36), $d=16$ self-dual code? IEEE Trans. Info. Theory, 19, p. 251, 1973.
  * [35] V.Y. Yorgov, A method for Constructing Inequivalent Self-Dual Codes with Applications to Length 56, IEEE Trans. Inf. Theory, 33) (1987), 77-82.