Recur, Attend or Convolve? On Whether Temporal Modeling Matters for Cross-Domain Robustness in Action Recognition

Most action recognition models today are highly parameterized, and evaluated on datasets with appearance-wise distinct classes. It has also been shown that 2D Convolutional Neural Networks (CNNs) tend to be biased toward texture rather than shape in still image recognition tasks, in contrast to humans. Taken together, this raises suspicion that large video models partly learn spurious spatial texture correlations rather than to track relevant shapes over time to infer generalizable semantics from their movement. A natural way to avoid parameter explosion when learning visual patterns over time is to make use of recurrence. Biological vision consists of abundant recurrent circuitry, and is superior to computer vision in terms of domain shift generalization. In this article, we empirically study whether the choice of low-level temporal modeling has consequences for texture bias and cross-domain robustness. In order to enable a light-weight and systematic assessment of the ability to capture temporal structure, not revealed from single frames, we provide the Temporal Shape (TS) dataset, as well as modified domains of Diving48 allowing for the investigation of spatial texture bias in video models. The combined results of our experiments indicate that sound physical inductive bias such as recurrence in temporal modeling may be advantageous when robustness to domain shift is important for the task.

Introduction
One of the most fundamental questions when it comes to video understanding is how to model the dependency between frames in such a way that temporal relationships relevant to the activity in the video can be learned. A robust action recognition system should be able to figure out how frames relate to each other, and which shapes and objects have changed or persisted over time. With this knowledge, it can start to infer relationships at a higher level, such as object-object or agent-object relationships.
Three principally different approaches to frame dependency are 3D convolutions, self-attention and recurrence.
These methods model the world (the visual sequence) in principally different manners: linearly, non-linearly, and non-linearly with a time-causal direction, meaning that they each use different inductive biases for the temporal modeling (Fig. A). In spite of its essentiality, the frame dependency question has almost disappeared from action recognition articles, possibly in the race to improve on the classification benchmarks. Emphasis is instead placed on other aspects of deep video models, such as advanced architectural superstructures, regularization or training schemes. A shift toward attention-based video models has recently taken place, but without a discussion of the physical interpretation of its underlying temporal model.
Humans are still significantly stronger at generalization than artificial neural networks in vision tasks [20,46]. Recurrent models are critical in the only visual system that has been 'solved' to date -biological vision [1,10,12,13,15,32,34,44,52]. Based on the observation that feedback connections are abundant in biological but not computer vision [32,56], in this article, we hypothesize that the lack of recurrence when learning spatiotemporal features may be one reason for this discrepancy. We therefore investigate the following research question empirically in extensive and systematic experiments: does the principally different mathematical natures of 3D convolutions, self-attention and recurrence affect cross-domain robustness in video modelsand in particular, does recurrence bring about an advantage?
Video models lack robustness to domain shift [8,61,62], and it has been repeatedly shown [8,25,35,60] that the datasets most frequently cited during the 2010s (UCF-101 [51], HMDB [33], Kinetics [29]) exhibit significant spatial biases. This is a plausible reason for the poor cross-domain robustness in action recognition, since overly relying on spatial rather than motion cues intuitively results in overfitting to one domain (e.g., certain backgrounds, viewpoints or similar actor appearances).
Contemporary state-of-the-art approaches to action recognition are predominantly either fully convolutional [5,17,18,21,60], combine convolutions with temporal sampling and fusion strategies [58,59,63], or, more recently, attention-based Video Transformers (VTs) [4, 23, Less texture More texture S1 S2 T Figure 1. Animated figure, displayed on click in Adobe Reader. Example clip showing our three modified domains of Diving48 enabling the investigation of texture bias in video models: S1 (segmented divers over a blurred background), S2, (cropped bounding boxes of divers over a blurred background), and T (masked boxes of divers, and the original background). 31,45,53]. The sheer size of the models, typically more than 50M trainable parameters, gives them a strong capacity to learn in-domain patterns. As models grow larger, ever more resources are spent to train them. State-of-the-art models should display competitive benchmarking numbers on large-scale datasets, such as Kinetics-400 and Kinetics-600. It is questionable whether these benchmarks are suitable for temporal modeling, or rather for how large amounts of YouTube clips efficiently can be stored as weight representations. At the same time, the reciprocal dependency between the hardware and software of standard graphics processing units (GPUs), on the one hand, and models requiring massive parallel computation for their training, on the other hand, is becoming ever more intertwined [30,41]. The question looms whether we have cornered ourselves in action recognition, in the expectancy to work on ever larger models, in industry as well as in academia. Theoretical works [2,39,50] have indicated that overparametrization helps generalization, in that local minima of the loss landscape for such models often are thought to be global. These studies are made on held-out data, but never on data with significant domain shift, to the best of our knowledge.
Although less efficient to train on GPUs, recurrent video models have a more parameter-efficient approach per timestep, which may hinder over-reliance on texture cues, and promote learning the temporally relevant motion cues. The need to be economical with the use of trainable parameters, we hypothesize, creates incitement to learn better shape representations instead of texture representations. In turn, this allows for better generalization across datasets and in the wild. For contour detection, it was found that a model with recurrent dynamics was more sample-efficient and generalized better than a feed-forward model [37,38].
The primary contributions of our paper are as follows: • We present the first empirical results from systematic experiments on how the choice of frame dependency modeling in action recognition can affect crossdomain robustness.
• We introduce a lightweight dataset allowing for investigation of both temporal shape modeling ability and domain generalization, called the Temporal Shape dataset.
• We provide the first discussion and experiments on shape vs. texture bias (following Geirhos et al. [19]) in deep video models.
• We make segmentation-based shape and texture versions of the Diving48 dataset public (as well as 303 instance-segmented frames), allowing studies on whether a video model has learned to rely more on (temporal) shape or on texture.

Related Work
Domain shift in action recognition. In [7,61], crossdomain datasets are introduced to study methods for video domain adaptation. [7] proposes to align the temporal features where the domain shift is most notable, whereas [61] proposes to improve the generalizability of so-called local features instead of global features, and use a novel augmentation scheme. Strikingly, however, all experiments in [7,61] are based on features extracted frame-by-frame, by a 2D ResNet [26], and aggregated after-the-fact, meaning that they in effect do not handle spatiotemporal features. Using frame-wise features saves large amounts of time and computation, but it avoids an essential aspect of video modeling. Different from the field of Domain adaptation, we are not proposing methods on top of base architectures to reduce domain shift, but rather study empirically which types of fundamental video models inherently seem to be more robust to it. In an important work by Yi et al. [62], benchmarks are introduced to study robustness against common video corruptions, evaluated for spatiotemporal attentionand convolution-based models. Different from our work, the domain shift is restricted to data corruptions rather than the same classification task in a new domain, and recurrent models are not evaluated.
Emphasis on temporality in action recognition. Many works emphasize the importance of temporal modeling, as the field of video understanding is growing, e.g., [14,22,40,43,47,49,60,63]. [22] and [40] compare temporal model-ing abilities between principally different architectures, but without explicitly investigating domain shift generalization. [49] examines video architectures and datasets for human activity understanding on a number of qualitative attributes such as pose variability, brevity and density of the actions. [28] investigates how much the motion contributes to the classification performance of the C3D architecture [54]. Both [6] and [55] perform large-scale studies of the features of different variants of 2D and 3D CNNs in action recognition. Last, we are connected to [47], which discusses the risk that models with strong image modeling abilities may prioritize those cues over the temporal modeling cues. Reminiscent of the findings of [19], the authors of [47] find that inflated convolutions tend to learn classes better where motion is less important, and that generalization can be helped by training on more temporally focused data (in analogy to training on shape-based data in [19]). Different from our work, however, only fully convolutional models are studied and the focus is not on comparing models with fundamentally different approaches to frame dependency modeling.

Experiment design
In this section, we describe the experiment design for the two datasets: Temporal Shape and Diving48.
Main idea. In all experiments, we begin by training on a specific domain, and validating on a held-out dataset from the same domain. We save the model checkpoint which performed the best on the validation set, and then proceed to evaluate it on other domains that are different in some respects but share the same task. Following [7], the domain we train on will be referred to as the source, and the unseen domains that we evaluate on as the target. To measure crossdomain robustness, we define the robustness ratio (rr.) as the ratio between a model's accuracy on a target domain and its best validation accuracy on the source domain. When the target task corresponds to the source task, this number should ideally be close to one (higher is better). It can be noted that the rr. is a heuristic metric, which builds on the assumption that the performance on the in-domain validation set typically is higher than on other domains. If the performance on the validation set is poor to begin with, the rr. is less informative.
Method common to all experiments. In our study, we are purposefully comparing the basic functionality of models. No pre-training, dropout, or data augmentation is applied in our experiments, except for 50% chance of horizontal flipping of the clips on Diving48. Sequences are uniformly sub-sampled into equal length (a fixed input size is required for the input to both 3D CNNs and attention-based models). There are non-uniform frame sampling methods, which can be used as augmentation, or as informed priors (e.g., the TimeSformer only samples the middle frames during inference in [4]); these are thus not used in our study, in order to study the bare bones of the models. Code related to neural networks was written in PyTorch [42] using Lightning [16]. Further implementation details and code can be found in the corresponding repositories ( Temporal Shape experiments, Diving48 experiments and diver segmentation). The datasets are available for download on Harvard Dataverse and linked to from the repositories.

Models
We will compare ConvLSTMs, 3D CNNs and VTs, since these present three principally different temporal modeling approaches with varying types and degrees of inductive bias. As VT, we will use the TimeSformer [4], because it recently achieved state-of-the-art results on a number of action recognition benchmarks.
It is a challenging task to compare neural network models which have principally different architectures. In our work, we decided on controlling for three different factors: the performance on a particular dataset, the number of trainable parameter and the layer structure (i.e., the number and expressivity of hierarchical abstractions). The experiments were designed prior to running them, to keep the process as unbiased as possible. The experiments are further completely reproducible as they were run on five fixed random seeds throughout the study.
Convolutional LSTMs. The ConvLSTM [48] layer functions like an LSTM layer [27], but with matrix multiplication replaced with 2D convolutions. This crucially means that they allow for the input to maintain its spatial structure, contrary to classical recurrent layers which require a flattened input. Frame dependency is modeled using recurrence, which introduces non-linearities between timesteps. Further, time can only flow in the causal direction. A Con-vLSTM video model, in this work, is a model fully based on these types of layers, with a classification head on top.
TimeSformer. The TimeSformer (hereon, TimeSf) [4] is a VT, relying entirely on self-attention mechanisms to model frame dependency. As in [11], each frame is first divided into patches, which are flattened. We use the TimeSformer-PyTorch library [57], mainly with the standard settings unless otherwise specified (divided space-time attention). Self-attention is applied both among the patches of one frame (spatial attention) and across patches located in the same positions across the temporal axis (temporal attention). Two variants are used in the TS experiments, with the number of heads A set to either 1 or 8 (TimeSf-1 and TimeSf-8). TimeSf-1 is closer to the ConvLSTM and 3D CNN in terms of parameter count, whereas TimeSf-8 is the standard setting. We note again that in order to study the fundamental behavior of the models, we do not use pretraining, advanced data augmentation, nor averaging over multiple predictions. This results in a lower performance on Diving48 for TimeSf than its state-of-the-art results. In order to control for layer structure or number of parameters which requires architectural modifications, it is not possible to use a pre-trained checkpoint. It is well-known that VTs, or Vision Transformers (ViTs) in general, require a lot of training data due to their minimal inductive bias. We therefore stress that we are not questioning the overall performance of these models -a pre-trained version would have performed better on the Diving48 task than in our experiments, but we are investigating the fundamental behavior of models in our experiments, prior to more advanced or large-scale training schemes.
3D CNNs. In a 3D CNN, time is treated as space, and thus the input video as a volume, across which we convolve local filter volumes. Convolution is a linear operation, meaning that the order of frames that the 3D filter traverses does not matter. Instead, all non-linearities are applied hierarchically, between layers, which is how this model still can learn the arrow of time. Its layer structure is typically similar to a 2D CNN, including batch normalization and pooling. This is also the case for the instances used in our study.

Experiments on the Temporal Shape dataset
Our proposed TS dataset is a synthetically created dataset for classification of short clips showing either a square dot or a random MNIST digit tracing shapes with their trajectories over time (Fig. 2). The dataset has five different trajectory classes (i.e., temporal shapes): circle, line, arc, spiral and rectangle. The task is to recognize which class was drawn by the moving entity across the frames of the sequence. The spatial appearance of the moving object is not correlated with the class, and can thus not be employed in the recognition. In the 2Dot, 5Dot and MNIST domains, the background is black, and in MNIST-bg, the background contains white Perlin noise. The Perlin noise can be more or less fine-grained; scale is regulated by a random parameter σ ∈ [1,10]. The dataset can be thought of as a heavily scaled-down version of an action template dataset, such as 20BN-Something-something-v2 [24], stripped of appearance cues.
The sequences consist of 20 64x64 frames, in grey scale. Each of the five classes has different amounts of possible variation in their states. The shapes can have varying starting positions, starting angles, direction, size and speeds. In the experiments, 4000 clips were used for training and 1000 for validation (model selection), and 500 clips for evaluation only. The classes are sampled so as to obtain class balance.
Since the dataset is small, we use lightweight models. We control for layer structure by letting the compared mod-els have three layers each of analogous blocks with the same number of hidden units in each. One block for the ConvL-STM and 3D CNN consists of a model-specific layer, max pooling, followed by batch normalization. These two models used the same convolutional kernel sizes in all three layers (3×3). For the TimeSformer, we used one TimeSformer layer as one block, and the latent dimension for each attention head, D h , as the number of hidden units, since these were similar in scale.
We run experiments for different numbers of hidden units per layer, h ∈ {2, 4, 6, 8, 10, 12, 16, 24, 32, 48}. For each of the ten experiments of varying model sizes, we train the models on the five-class task on the source domain for 100 epochs, with ten epochs of early stopping patience, repeated under five different random seeds set from the beginning of the study. For TimeSf-1 and TimeSf-8, the maximum number of epochs is 300 (100 for early stopping) because they demand more epochs to converge than the other two types of models, due to their minimal inductive bias. We then evaluate the best model checkpoint from the source domain on different target domains with the same classification task. Experiments were conducted in two 'directions', training on 2Dot and evaluating on the other domains, or training on MNIST-bg and evaluating on the other domains, since these represent two extremes on the continuum of less to more spatial noise.
Training on the TS data is light-weight compared to real video data, and runs fast (in the minutes-range, up to an hour, for the model sizes we evaluated) on one GPU card. We train with a batch size of 64 in all TS experiments.

Experiments on Diving48
Diving48 [35] is a well-known dataset for fine-grained and time-critical action recognition. It consists of 18k short clips with dives from 48 classes. Successfully classifying these dives requires temporal modeling, since one needs to keep track of the movements of the divers and their order. The dataset is varied appearance-wise, in terms of both backgrounds and viewpoints, which may contain unknown biases. The same competition sites can be present in both the training and test split, "to avoid biases for certain competitions", according to the authors [35]. Instead, in our view, this in fact increases the risk for bias, since the ability to recognize a dive at an unseen site is never tested. It would have been preferable to separate competition locations entirely between training and test set. Thus, even though the dataset presents a very challenging classification task from a temporal modeling perspective, it is likely not free from spatial biases (as will be demonstrated by our experiments). Modified domains of Diving48. We always train on the original dataset, but evaluate our trained models on slightly modified domains of the original test set. We modify the test set into three new domains: two based on shape and 2Dot 5Dot MNIST MNIST-bg Figure 2. The videos can be displayed on click in Adobe Reader. Example clip showing the four domains of the TS dataset, for the class circle. In 2Dot and 5Dot, the circle is drawn with a square of width 2 and 5 pixels. In MNIST and MNIST-bg, the circle is drawn with a MNIST digit, w/ and w/o a Perlin noise background.
To do this, we extend the concepts of shape and texture bias from [19] to the temporal domain in the following way. In the shape domains, we blur the background and only maintain the segmented diver(s) (S1), or the divers and their bounding boxes (S2). In the texture domain (T), we conversely mask bounding boxes where the diver(s) are in each frame, and only keep the background. The masked boxes are filled with the average Imagenet [9] pixel value, following [8]. The class evidence should lie only in the divers' movement; hence, the texture version should not contain any relevant signal, and the accuracy should ideally drop to random performance. In this way, we can study how different models drop in score when tested on the shape or texture domain, indicating both cross-domain robustness (for S1 and S2) and texture bias (for T).
Instance Segmentation of Diving48. The segmentation of divers in Diving48 is detailed in the supplemental. We release 303 manually labeled frames with instance segmentation (single or double dives), since off-the-shelf COCOtrained [36] networks fail at this task for the class Person, presumably because of the unusual shapes assumed in the air by the diver, or include people in the audience.
Training. Just as for TS, we deliberately avoid bells and whistles when training models on Diving48, to study their fundamental behavior. All three models are trained with the same SGD optimizer, cross-entropy loss, and a constant learning rate of 0.001. Each model is trained for 500 epochs maximally, with an early stopping patience of 30 epochs if the validation performance does not improve. The only data augmentation used is horizontal flipping of 50% probability for the entire clip. The models are trained using PyTorch Lightning's ddp parallelization scheme across eight A100 GPUs, with a batch size of 8 and a clip length of 32 uniformly sampled frames, at 224×224. Given that the purpose of our experiments is not to optimize classification performance, we evaluate the models at different levels of performance, ranging from 30% to 50% accuracy. Some of the advanced state-of-the-art methods today, including pre-training and heavy data augmentation, obtain up to 80% performance on Diving48, but when the dataset was introduced in 2018, and standard video methods were tested off-the-shelf on it, the best result was 27% ac-curacy [35]. Thus, the range of 30-50% is reasonably wellperforming, and well above random (which is at 2.1%).
Experiments. We conduct three different kinds of experiments on Diving48, namely control for: layer structure and performance (a-c), performance of the best performing variants (d), and number of parameters and performance (e-h). ConvLSTM has four blocks of 128 hidden ConvL-STM units each (14.3M params.) in all experiments.
a-c. Controlling for layer structure and performance. In this experiment, we let the models have four layers, with h = 128 in each. We again treat D h as the hidden unit analogy for TimeSf. We evaluate model checkpoints at different performance levels: 30%, 35%, and 38.3% accuracy. The last accuracy, was chosen because it was the limiting, highest performance by the 3D CNN in this experiment. Having the same layer structure gives rise to a varying number of parameters for each type of model. Here, the 3D CNN has 10.6M params., and TimeSf 85M.
d. Controlling for performance only. Here, we compare models at their best performance, after hyperparameter search. Since it was not possible to train TimeSf to a higher accuracy than 39.7% in all variants we tried, this experiment was only conducted with the 3D CNN and ConvLSTM. 1 The 3D CNN was an 11-layer VGG-style model (23.3M params.). The checkpoints used were both at exactly 50.07% validation accuracy. e-h. Controlling for number of parameters and performance. Here, we have chosen models with a similar amount of trainable parameters, in this case 14M. To arrive at this number of parameters for TimeSf, its depth was reduced from 12 to 11, and D h and D were halved, to 32 and 256, respectively, relative to the default model. The 3D CNN has six blocks with 128 units in each.

Results and discussion
Having presented the experimental design for both datasets, next, we discuss our empirical findings, first on TS, and then on Diving48 and its modified domains.

Temporal Shape
Condensed results: TimeSf and ConvLSTM are more cross-domain robust than the 3D CNN in the absence of spatial texture bias. Training on 2Dot. Fig. 3a shows that although the 3D CNN generally obtains higher results on the source validation set and the nearby 5Dot domain, the ConvLSTM and TimeSf drop less compared to their original results when tested on MNIST (further from the source domain). ConvL-STM in fact outperforms the 3D CNN in absolute numbers on the MNIST domain. The inductive bias of a 3D CNN is highly local in space and time, which might impede learning of these temporal shapes. Generalization to the MNIST-bg domain proves too challenging for all three models.
Robustness ratio vs. model size. In Fig. 10, we have plotted the rr. for the three target domains when training on 2Dot. For 5Dot, the rr. for ConvLSTM decreases slightly with model size, whereas the 3D CNN and TimeSf, in contrast, increase the rr. with increased model size. For MNIST, which is further from the validation domain, the upward trend for the 3D CNN is broken, and less pronounced for TimeSf. For the most challenging domain, MNIST-bg, the rr. becomes very low for all three models with increased size. The trends in Figs. 10 a-c point to how a larger model size with promising performance in a nearby domain can potentially be an obstacle in domains that are further from the source for TimeSf and the 3D CNN.
Training on MNIST-bg. In this experiment, TimeSf-8 and TimeSf-1 were the most robust (Fig. 3 b). A VT is an excellent model when it comes to learning sparse, long-term dependencies in space and time. We hypothesize that this allowed TimeSf to to fully disregard the Perlin noise (which is highly stochastic and demanding to model) and learn the true temporal shapes, and that this, in turn, allowed it to be unbiased in the other domains, since the training data was designed to exclude spatial bias. In real-world data, however, there will always be biases, and it is therefore best to construct models which inherently encode as little bias as possible, regardless of the training data.

Diving48: Sensitivity to shape and texture
Condensed results: ConvLSTM exhibits less texture bias and is more cross-domain robust than TimeSf and 3D CNN.  Table 1 shows the average results for the Diving48 experiments. We note that ConvLSTM drops the most for T, both relative to the validation (T/V) and to the S1 (T/S1) accuracies. ConvLSTM is also most robust to the S2 domain, whereas the 3D CNN is most robust to the S1 domain. Experiments a-d. In experiments a-c (Fig. 5), where we vary the validation accuracy on the source domain between 30% and 38.3%, both TimeSf and the 3D CNN perform better on T than on S1 and S2, even if only the two latter contain class evidence. This suggests that spatial bias is indeed present in Diving48, and that these models are more prone to encode it than ConvLSTM. Tables 2-4 show that T/S1 > 1 for these two models, also visible in Fig. 5 a-c. 2  Table 3. Results for experiment b: 4x128, 35% validation accuracy. * when a low T/V result is not accompanied by T/S1 < 1.
Model  Table 4. Results for experiment c: 4x128, 38.3% validation accuracy. * when a low T/V result is not accompanied by T/S1 < 1.
In contrast, ConvLSTM clearly drops for T. TimeSf is large here, at 85M params., whereas the 3D CNN is interestingly quite small at 10.6M params. This suggests that 2 In Tables 3-4, TimeSf drops the most for T relative to the validation set (T/V). This can be explained by its overall large drops, rather than being robust to texture bias, most clearly visible in Fig. 5 a-c. For T/V to be a meaningful metric, T/S1 should be < 1. Therefore, we have put asterisks on the lowest T/V results which are not accompanied by T/S1 < 1. not only the parameter count causes susceptibility for overfitting, but that there may be innate tendencies to overfitting in the choice of spatiotemporal modeling. A recurrent model necessarily takes each timestep into account as it traverses the sequence in the time-causal direction, since each timestep is non-linearly registered in the hidden state. We hypothesize that this enables it to register motion changes over time more in detail, and count these as salient, when that is the case (as it should be for Diving48).
Model  In experiment d, where we compare a ConvLSTM and a 3D CNN at 50.07% validation accuracy -the best results on Diving48, the 3D CNN does not longer improve on the texture dataset relative to S1 and S2, but the drop on T is S1 S2 T markedly larger for ConvLSTM (Table 5).
Qualitative examples and diving attributes. Table 6 shows a breakdown of the models' predictions on five randomly selected clips from a randomly chosen class (34). The models instances used here are from experiment c (38.3% acc.). Top-1 acc. for these five clips being equal for all models at 0.4, we note that ConvLSTM has 100% top-5 acc. for both S1 and S2, whereas the 3D CNN has 80% and 60% (40% and 40% for TimeSf). As for the texture (T) results, the top-5 acc. of the 3D CNN remains at 80% relative to S1 and even improves from 60% to 80% relative to S2, whereas ConvLSTM drops by 40% and TimeSf drops by 50%. Thus, so far ConvLSTM and TimeSf display sound dropping on T. Next, we study the predictions made by the models in detail to observe that there is a qualitative difference between the predictions of ConvLSTM and TimeSf. Each label of Diving48 has four attributes: takeoff, somersault, twist and flight position. Among the top-1 predictions for both S1 and S2 (Table 7), we study how many attributes are correct in the misclassifications for each model.  (32,35) obtain three correct attributes, and for TimeSf, the best misclassification has only two correct attributes. This suggests that the 3D CNN and TimeSf have modeled the classes in terms of the true attributes to a lesser extent than ConvLSTM, i.e., ConvLSTM has learned more relevant temporal patterns, at the same global validation performance. Observing the three lower sections of Table  7 for further randomly selected classes 12, 22 and 45, the ConvLSTM still achieves the largest proportion of correct attributes in the misclassifications. Just as for class 34, the  Table 7. Examples of predictions and misclassifications. Each class has four attributes, and the Correct attr. column shows how many attributes were correct among the set of misclassifications.
Bv. S1 S2 T Experiments e-h. The results for experiments e-h, where the number of trainable parameters and performance are fixed, are shown in Fig. 6 (tabulated results in the supplemental). Here, the 3D CNN is the most robust out of the three, although ConvLSTM approaches the 3D CNN and drops more steeply for T in g-h, where the performance is higher (40% and 45% acc.). In these experiments, although least robust, TimeSf does not improve on T relative to S1 and S2 any more. This suggests that TimeSf is more likely to display texture bias when it has a larger amount of parameters, as it does in experiments a-c.

Conclusions and discussion
We have studied cross-domain robustness for three models that are principally different in terms of temporal modeling, in their bare-bones settings. A 3D CNN treats frames as a linear volume, a VT lets frames have non-linear but timesymmetric relationships, and a ConvLSTM models frame dependency non-linearly in a time-causal direction. Recently, a discrepancy in terms of feedback connections between biological and computer vision has been discussed [32,56], and in our work we have hypothesized that the lack of feedback connections is one reason for the similarly lacking generalization abilities in computer vision.
Our experiments were carried out on two very different datasets, one synthetic, without bias, and one with natural data, thus with more noise and potential spatial bias. The combined results (Figs. 3-5, Tables 1 and 7) on these datasets indicated that convolutional-recurrent temporal modeling is more robust to domain shift than selfattention and 3D convolutions in terms of bare-bones behavior, presumably owing to its lesser encoding of texture bias. Our results are fully reproducible with public seeds, code and data. The fact that our observations regarding texture bias are made for a fine-grained dataset such as Div-ing48, constructed to contain as little bias as possible, suggests that the issue may be worse when it comes to more spatially biased datasets such as Kinetics, which is left for future work. It is furthermore left for future work whether ImageNet pre-trained VTs display more or less texture bias than their trained-from-scratch counterparts. Another observation from our study is that when the parameter count was kept equal (experiments e-h), these trends were less pronounced.
Moreover, qualitative random examples consistently showed that the ConvLSTM learned more relevant diving patterns than the two others, when scrutinizing the three models' misclassifications -which emphasizes the texture bias tendency of TimeSf and the 3D CNN. Sharing parameters across timesteps, as recurrent models do, narrows the parameter space, possibly incentivizing these models to prioritize which patterns to learn. Another reason to use smaller models is that they require less data to train, which is ethically desirable, both in that the data can be inspected more easily, and from a sustainability perspective [3].
Our study indicates that sound physical inductive bias such as recurrence in temporal modeling may be advantageous when robustness to domain shift is important for the task. In action recognition, benchmarking has thus far mainly been conducted for in-domain-tasks where large models perform well. We encourage the video understanding community to increasingly conduct evaluation on tasks involving domain shift. We hope that our proposed datasets and framework for evaluation can help such future domain shift robustness investigations of spatiotemporal features. Figure A highlights the conceptual differences between 3D convolution, self-attention and recurrence in terms of temporal modeling.

B. Plots for each model size on the Temporal Shape dataset
In the main article (Figure 3), the shaded area of standard error is across both model sizes and repeated runs with different seeds (meaning 10 * 5 = 50 runs per model and domain). Detailed plots for each model size with five repeated runs each are shown in Figures 8-9.  Table 9. Results for experiment (f): 14M parameters, 35% validation accuracy. Model

C. Robustness ratios for training both on 2Dot and MNIST-bg
In the main article, robustness ratios vs. model size are only plotted when training on 2Dot. In Figure 10, we include results when training on MNIST-bg as well. We show the two plots next to each other for comparison. Tables 8-11 show tabularized results corresponding to Figure 6 in the main article (experiments e-h).

E. Qualitative examples on Diving48
Here, we include the top-1 and top-5 accuracies tables corresponding to the qualitative examples of classes 12, 22 and 45 shown in Table 7 in the main article. In Tables 12,  13 and 14, the trends regarding the top-1 and top-5 accuracy on the different datasets are slightly less clear. We observe that in Tables 12 and 14, ConvLSTM and TimeSf drop the clearest in top-5 performance on T relative to S1 and S2. On the other hand, in Table 13 (Class 22), the top-5 accuracy is relatively improved on T compared to S1 and S2 for ConvL-STM and the 3D CNN, whereas TimeSf is unchanged. We inspected these clips, to verify that the segmentation had not failed, which it had not. However, the ConvLSTM is still the only one out of the three to have 20% in top-1 accuracy both for S1 and S2 on class 22, dropping to 0 in top-1 on T (Table 13). Last, for class 45, the ConvLSTM has the best results on S1 and S2 (20% top-5 accuracy) out of the three   table structure as Table 12.  In the experiments, 4000 clips were used for training and 1000 for validation. The number of samples was chosen so as to be able to sample randomly with replacement, while still keeping the risk low that an identical clip occurs in both the training and the validation set. For the 2Dotdomain, each class has more than 30k possible variations (lower bounds: 31k circle, 34k line, 51k rectangle, 150k arc), except the spiral class which has 7200 as a lower bound on the possible variations. When the training set consists of 5000 samples in total, we generate around 1000 samples per class. For the spiral class, a frequentist estimation gives that 800/7200 = 0.11 of the 200 spiral validation samples might be present in the training split (22 clips). However, this is still an over-estimation, since the spirals sometimes bounce against the sides of the frame which gives rise to extra variation. We decided to consider this as acceptable noise of the dataset. Some amount of data leakage can be considered interesting since this may occur in standard datasets as well.

F.2. Instance Segmentation of Diving48
To segment divers, it did not suffice to apply a pretrained network and use the class "Person", which we first attempted (DeeplabV3 pre-trained on MS-COCO, provided by PyTorch). First of all, the off-the-shelf model could often not recognize the divers in the air as the "Person" class -they can be up-side down, or assume strange shapes in the air. Secondly, the model would often detect pixels of the "Person" class in the audience, when there was audience visible, which we, naturally, did not want to include.
Thus, we resorted to labelling our own segmented frames from the dataset (no segmentation masks were available online). We manually labelled 303 frames from the dataset containing one or two divers, picked from 303 randomly chosen videos of the training split. When there were two Best val. Best val. MNIST 5Dot 2Dot h=48 Figure 9. Average results (% acc.) across ten trials with varying numbers of hidden units per layer, repeated five times each. Training and validation on the MNIST-bg domain. The shaded area corresponds to standard deviation across the trials. divers, we segmented each as its own instance. The segmentation masks will be made public.
We fine-tuned a MaskRCNN on our labeled dataset, using a random split of 290 frames as training set and 13 frames to validate, and monitored the bounding box IoU on the validation set. The best model achieved 93% validation bounding box IoU, which we used to segment the frames of the entire dataset (at 32 frames per clip). We used the confidence of the mask predictions as a threshold. The nonzero predictions were mostly confined to a bounding box surrounding the diver(s). When the threshold was t = 0, bounding boxes around the divers were used as crops (S2). When increased to t = 0.4, we obtained proper segments of the diver shape (S1). The frames contain a lot of motion blur which made the segmentation more challenging, and the segmentation at t = 0.4 is not perfect -sometimes parts of for example an arm or foot is missing. The performance of the segmentation at t = 0.4 was deemed sufficient after manual inspection of 100 randomly chosen videos, where all videos had enough evidence to recognize the development of the dive. The segmentation at t = 0 (bounding boxes, S2) was satisfactory in all 100 clips inspected.  Table 17 lists the different variants we tested when training on Diving48 from scratch. In all variants, the number of heads was 8 (A = 8), the patch size was 16 × 16, the learning rate was fixed at 0.001, and the weight decay was 0.00001. When SGD was used, the momentum was always 0.9. Table 16 lists the different model specifications for each of the eight experiments a-h on Diving48 in the main article. For further details on the models, this is described in the main article and in the code repository.


FAWA: Fast Adversarial Watermark Attack on Optical Character Recognition (OCR) Systems

Deep neural networks (DNNs) significantly improved the accuracy of optical character recognition (OCR) and inspired many important applications. Unfortunately, OCRs also inherit the vulnerabilities of DNNs under adversarial examples. Different from colorful vanilla images, text images usually have clear backgrounds. Adversarial examples generated by most existing adversarial attacks are unnatural and pollute the background severely. To address this issue, we propose the Fast Adversarial Watermark Attack (FAWA) against sequence-based OCR models in the white-box manner. By disguising the perturbations as watermarks, we can make the resulting adversarial images appear natural to human eyes and achieve a perfect attack success rate. FAWA works with either gradient-based or optimization-based perturbation generation. In both letter-level and word-level attacks, our experiments show that in addition to natural appearance, FAWA achieves a 100% attack success rate with 60% less perturbations and 78% fewer iterations on average. In addition, we further extend FAWA to support full-color watermarks, other languages, and even the OCR accuracy-enhancing mechanism.

Introduction
Optical Character Recognition (OCR) has been an important component in text processing applications, such as license-plate recognition, street sign recognition and financial data analysis. Deep neural networks (DNNs) significantly improve OCR's performance. Unfortunately, OCR inherits all counter-intuitive security problems of DNNs. OCR models are also vulnerable to adversarial examples, which are crafted by making human-imperceptible perturbations on original images to mislead the models. The wide application of OCR provides incentives for adversaries to attack OCR models, thus damaging downstream applications, resulting in fake ID information, incorrect metrics readings and financial data.
Prior works have shown that we can change the prediction of DNNs in image classification tasks only by applying carefully-designed perturbations [8,19,20,22], or adding a small patch [3,13] to original images. But these methods are not directly applicable to OCR attacks. 1) Most text images are on white backgrounds. Perturbations added by existing methods appear too evident for human eyes to hide, and pollute clean backgrounds. 2) Instead of classifying characters individually, modern OCR models are segmentation-free, inputting entire variable-sized image and outputting a sequence of labels. It is called the sequential labeling task [9]. Since modern OCR models use the CNN [15] and the LSTM [12] as feature extractors, the internal feature representation also relies on contexts (i.e., nearby characters). Therefore, besides perturbing the target character, we also need to perturb its context, resulting in more perturbations. 3) Since text images are usually dense, there is no open space to add a patch.
In this paper, we propose a new attack method, Fast Adversarial Watermark Attack (FAWA), against modern OCR models. Watermarks are images or patterns commonly used in documents as backgrounds to identify things, such as marking a document proprietary, urgent, or merely for decoration. Human readers are so used to the watermark that they naturally ignore it. We generate natural watermark-style adversarial perturbations in text images. Such images appear natural to human eyes but misguide OCR models. Watermark perturbations are similar to patch-based attacks [3,13] where perturbations are confined to a region. Different from patches occupying a separate region, watermarks overlay on texts but not hinder the text readability. Laplace attack [10] and HAAM [11] try to generate seemingly smooth perturbations, which work well on colored photos. However, they do not solve the problem of background pollution.
FAWA is a white-box and targeted attack. We assume adversaries have perfect knowledge of the DNN architecture and parameters (white-box model) and generate specific recognition results (targeted). There are three steps in the perturbation generation. 1) We find a good position over the target character to add an initial watermark. 2) We generate perturbations inside the watermark. 3) Optionally, we convert the gray watermark into a colored one. To generate perturbations, we leverage either gradient-based or optimization-based methods. We evaluate FAWA on a state-of-the-art open-source OCR model, Calamari-OCR [26] for English texts with five fonts. FAWA generates adversarial images with 60% less perturbations and 78% fewer iterations than existing methods, while maintaining a 100% attack success rate. Our adversarial images also look quite similar to natural watermarked images. We evaluate the effects of colored watermarks and other languages under real-world application settings. Last, we propose a positive application of the FAWA, i.e., using the perturbations to enhance the accuracy of OCR models. The contributions of this paper include: 1. We propose an attack method, FAWA, of hiding adversarial perturbations in watermarks from human eyes. We implemented FAWA as the efficient adversarial attacks against the DNN-based OCR in sequential labeling tasks; 2. Extensive experiments show that FAWA performs targeted attacks perfectly, and generate natural watermarked images with imperceptible perturbations; 3. We demonstrate several applications of FAWA, such as colored watermarks as an attack mechanism, using FAWA as an accuracy-enhancing mechanism.

Background and Related Work
Optical Character Recognition (OCR). We can roughly categorize existing OCR models into character-based models and end-to-end models. Characterbased recognition models segment the image into character images first, before passing them into the recognition engine. Obviously, the OCR performance heavily relies on the character segmentation. End-to-end recognition models apply an unsegmented recognition engine, which recognizes the entire sequence of characters in a variable-sized image. [1,7] adopt sequential models such as Markov models and [2,24] utilize DNNs as feature extractors for sequential recognition.
[9] introduces a segmentation-free approach, connectionist temporal classification (CTC), which provides a sort of loss function of enabling us to recognize variable-length sequences without explicit segmentation while training DNN models. Thus, many state-of-the-art OCR models use CTC as the loss function.
Attacking DNN-based Computer Vision Models. Attacking DNN-based models is a popular topic in both computer vision and security fields. Existing attack methods use the following two ways to generate perturbations. 1) Making perturbations small enough for evading human perception. For example, many projects aim at generating minor L p -norm perturbations for the purpose of making them visually imperceptible. FGSM [8], L-BFGS [22], DeepFool [18], C&W L 2 /L ∞ [4], PGD [17] and EAD [5], all perform modifications at the pixel level by a small amount bounded by . 2) Making perturbations in a small region of an image. For example, JSMA [20], C&W L 0 [4], Adversarial Patch [3] and LaVAN [13], all perturb a small region of pixels in an image, but their perturbations are not limited by at the pixel level. Though FAWA is similar to patches, in the text images, watermarks overlay on the text instead of covering the text.
Generating minimal adversarial perturbations. FAWA generates adversarial perturbations using the either gradient-based or optimization-based methods. Gradient-based methods add perturbations generated from gradient against input pixels. FGSM [8] is a L ∞ -norm one-step attack. It is efficient but only provides a coarse approximation of the optimal perturbations. BIM [16] takes multiple smaller steps and the resulting image is clipped by the same bound . Thus BIM produces superior results to FGSM. MI-FGSM [6] extends BIM with momentum. MI-FGSM can not only stabilize update directions but also escape from poor local maxima during iterations, and thus generates more transferable adversarial examples. Considering the efficiency, we adopt MI-FGSM in FAWA.
Optimization-based methods directly solve the box-constrained optimization problem to minimize the L p -norm distance between the original and adversarial image, while yielding the targeted result. Box-constraint L-BFGS [22] seeks adversarial examples with L-BFGS. Though L-BFGS constructs subtle perturbations, it is inefficient. Instead of applying cross-entropy as loss function, C&W L 2 attack [4] constructs a new loss function and solves it with gradient descent. OCR attack [21] is the only available work of attacking sequence-based OCRs as far as we know, which generates adversarial examples using the CTC loss for sequential labeling tasks. In FAWA, we use the same setting as OCR attack.
Perturbations with other optimization goals. Besides minimizing the perturbation level, many works make efforts to produce smooth and natural perturbations. Laplace attack [10] smooths perturbations relying on Laplacian smoothing. HAAM [11] creates edge-free perturbations using harmonic functions for disguising natural shadows or lighting. However, the smoothing and disguising are for photos but not for text images. Instead of manipulating pixel values directly, [27] produces perceptually realistic perturbations with spatial transformation. Though avoiding background pollution, it cannot guarantee the readability of text when the attack needs large deformation. [23] also utilizes the watermark idea but performs attacks only by scaling and rotating plain watermarks. Without adding pixel-level perturbations, it does not offer a high attack success rate.

Fast Adversarial Watermark Attack
In this section, we introduce fast adversarial watermark attacks (FAWA). FAWA consists of three steps. 1) We automatically determine a good position to add the initial watermark in the text image so that we can confine the perturbation generation to that region. 2) We generate the watermark-style perturbations with either the gradient-based method or optimization-based method. 3) Optionally, we convert gray watermarks into full-color ones to improve the text readability.

Preliminaries
Problem definition of adversarial image generation. Given a text image x = [x 1 , x 2 , ..., x n ] T for any x i ∈ [0, 1], where n is the number of pixels in the image, our goal is to generate an adversarial example x with minimum L p -norm perturbations x −x p against the white-box model f with intent to trick model f into outputting the targeted result t, f (x ) = t. Formally, the problem of adversarial image generation is min x x − x p s.t. f (x ) = t and x ∈ [0, 1] n . Also, we define the CTC loss function with respect to the image x as CTC (x, t) and the target labels t = [t 1 , t 2 , ..., t N ] for t i ∈ T , where T is the character set.
Saliency map. The saliency map [20] is a versatile tool that not only provides us valuable information to cause the targeted misclassification in the threat model but also assists us in intuitively explaining some attack behaviors as a visualization tool. The saliency map indicates the output sensitivity, relevant to the adversarial targets, to the input features. In the saliency map, a larger value indicates a higher likelihood of fooling the model f to output the target t instead of the ground-truth f (x). We can construct a saliency map of an image using the forward derivative with respect to each input component in the text image.
L p -norms. L p -norms are commonly-used metrics to measure the perceptual similarity between the clean image x and the adversarial image x , denoted by In gradient-based methods, we apply L p -norms to prune the saliency map for generating L p -norm perturbations. In optimization-based methods, L p -norms are usually as an optimization term in the objective function. Particularly, L 2 -norm is greatly useful to enhance the visual quality. L ∞ -norm is to measure the maximum variation of perturbations.

Finding the Position of Watermarks
To automatically determine a good position of watermarks, as shown in Fig. 1, we perform the following steps. 1) We produce adversarial perturbations of the basic attack (i.e., Grad-Basic or Opt-Basic in Section 3.3) in the text image. 2) We binarize such adversarial image, and get its perturbed regions r = [r 1 , r 2 , ..., r n ] T , where r i = 1 if x i = x i and 0 otherwise. 3) In order to find relatively complete perturbed regions r , we apply a combination of erosion ⊕ and dilation operations twice in the perturbed regions r, r = ((r ⊕ K) K) 2 , where we set the kernel K = 1 3×3 . 4) After sorting the perturbed regions in r by their area, we obtain the largest perturbed region in r . We can find that our target texts locate in the same position as the largest found region. 5) Last, in the text image, we place a watermark big enough to cover the found position, and obtain an initial watermarked image x 0 and a binary watermark mask Ω w with the same shape of x, where Ω w,i = 1 if the position i is inside the watermark and 0 otherwise.

Generating Adversarial Watermarks
After finding the position of watermarks, we need to generate the perturbations within the watermarks to mislead the OCR models to output target texts. Integrated with two popular methods, we use the following methods to attack. Gradient-based Watermark Attack (Grad-WM). Considering the high efficiency of MI-FGSM [6], we apply it as our gradient-based method (we refer to as Grad-Basic). Each iterative update of the Grad-Basic is to 1) get the saliency map normalized by L 1 -norm with the cross-entropy loss, 2) adjust the update direction in the saliency map and update the momentum, and 3) update a new L p -norm adversarial image x i+1 bounded by using the updated momentum.
There are two main differences between Grad-WM and Grad-Basic. 1) Different from off-the-shelf MI-FGSM, where it applies the cross-entropy as loss function in the image classification tasks, in our Grad-WM, we use the CTC loss function to compute the saliency map. CTC loss function fits better because it is widely used in OCR models to handle the sequential labeling tasks. 2) In Grad-WM, to hide perturbations in the watermarks, we confine the perturbations

Algorithm 1 Gradient-based Watermark Attack
Input: A text image x, OCR model f with CTC loss CTC, targeted text t, -bounded perturbation, attack step size α, # of maximum iterations I, decay factor µ. Output: An adversarial example x with x − x p ≤ or attack failure ⊥.
1: Initialization: g 0 = 0; x 0 = x0 2: for all each iteration i = 0 to I − 1 do 3: Input x i to f and obtain the saliency map ∇x CTC(x i , t) 4: Update g i+1 by accumulating g i in the saliency map normalized by L1-norm as 5: Update x i+1 by applying watermark-bounded Lp-norm perturbations as end if 9: end for 10: return attack failure ⊥ within the boundary of the watermark Ω w , rather than spreading perturbations over the entire image in the result of the background pollution like Grad-Basic.
Algorithm 1 summarizes the Grad-WM generation procedure. Notably, input images are the initial watermarked images x 0 created in Section 3.2. Then the saliency map is produced with the CTC loss function relevant to the adversarial targets t. Through element-wisely multiplying the watermark mask Ω w with the updated L p -norm g i+1 , we get rid of the perturbations outside the watermark to maintain the clean background. We gain a significant visual improvement in the Grad-WM than the Grad-Basic. Besides, for further improving the attack efficiency, we determine whether to stop the attacks in every few iterations.
Optimization-based Watermark Attack (Opt-WM). We employ OCR attack [21] as our basic optimization-based method (Opt-Basic). Opt-Basic solves the following optimization problem: min where c is a hyper-parameter. To improve the visual quality of adversarial images, Opt-Basic adopts L 2 -norm for penalizing perturbations. To eliminate the box-constraint [0, 1] of x , it reformulates the problem using the change of variables [4] as min ω c· CTC ( tanh(ω)+1 satisfies the box-constraint [0, 1] automatically. Intuitively, we treat the variable ω as the adversarial example x without the box-constraint.
Similar to Grad-WM, we first get the initial watermarked input image x 0 and the watermark mask Ω w . To confine perturbations in watermarks more conveniently, we separate the perturbation term from w, and rewrite the original w to w +x 0 that represents the adversarial image of combining the perturbation term w and the initial watermarked image term x 0 . The objective function changes to min ω c · CTC ( tanh(ω+x0)+1 To constrain the manipulation region in the watermark fashion, we perform the elementwisely multiplication between the perturbation variable ω and the watermark mask Ω w . Formally, we reformulate the optimization problem as We adopt the Adam optimizer [14] for both Opt-Basic and Opt-WM to seek the watermark-style adversarial images. We utilize the binary search to adapt the tradeoff hyper-parameter c between the loss function and the L 2 -norm distance.

Improving Efficiency
To improve attack efficiency, we employ batch attack and early stopping by increasing the number of parallel attacks and reducing redundant attack iterations. Batch attack. Because OCR models only support batch image processing with the same size, when we attack a large number of variable-size text images, it will be time-consuming to attack them one by one. To improve attack parallelism (i.e., attack multiple images simultaneously), we 1) resize the variable-size images into the same height, 2) pad them into the maximum width among these images, 3) put the same-size images into a matrix. After the preprocessing, we could perform batch adversarial attacks in a single matrix to improve attack efficiency. Early stopping. For avoiding redundant attack iterations, we insert the earlystop mechanism in the attack iterations. We evaluate attack success rate (ASR) every few iterations. We stop attack iteration once ASR achieves 100%, indicating that all adversarial images are misidentified as the targeted texts by the threat model. To a certain extent, early stopping reduces the attack efficiency as it takes time to check attack status during iterations. This is a basic tradeoff between the cycle of ASR evaluation and the maximum attack iteration setting.

Improving Readability
Sometimes the gray watermarks still hinder the readability of the text as it reduces the contrast. To achieve better readability of the text, we employ the following two effective strategies: adding text masks and full-color watermark. Adding Text Masks. When generating the initial watermarked image x 0 in Section 3.2, to prevent the text from being obscured by the watermarks, we add in watermarks outside the text. To achieve this, we binarize the text images x by a threshold τ to get text masks Ω t with the same size of x, where Ω t,i = 1 if x i > τ and 0 otherwise. Then we get the initial watermarked images Generate text images. After processing the corpus in the IMDB dataset, we generate a dataset with 97 paragraph, 1479 sentence and 1092 word images using the Text Recognition Data Generator 2 . We use five fonts to generate these images: Courier, Georgia, Helvetica, Times and Arial. We set the font size to 32 pixels. We verify the Calamari-OCR can achieve 100% accuracy on these images.
Generating letter-level attacks targets. We choose a target word that is 1) a valid word, and 2) with edit distance 1 from the original. We evaluate replacement, insertion and deletion. More similar the replacement target is to the original, the easier the attack is. For example, replacing letter t with letter f is easier than replacing t with letter j. We use the logit value from the output of the last hidden layer, as the similarity metric between a pair of letters. Given the logit value, we assign replacement attacks into easy, random and hard case.
Generating word-level attacks targets. In this task, we replace the entire word in word, sentence and paragraph images. Different from letter-level attacks, we randomly choose a word in the English dictionary which has the same length as the original. However, we don't constrain the edit distance between them.
Attack implementation and settings. We implemented Grad-WM and Opt-WM attacks 3   decay factor µ is 1.0. For the optimization-based methods, we use the Adam optimizer [14] for 1000 steps with mini-batch size 100 and learning rate 0.01. We choose c = 10 as the tradeoff between the targeted loss and perturbation level.
Evaluation metrics. We evaluate attack capability from the following aspects.
1) Perturbation level. We quantify the perturbation level with three metrics: MSE = 1 n x − x 2 2 , evaluates the difference between two images. PSNR = 10 log D 2 MSE , where D is the range of pixel intensities. SSIM [25] captures structural information and measures the similarity between two images. For these metrics, we take the average of all images in the following results. Smaller MSE, larger PSNR and SSIM closer to 1 indicate less perturbations.

#(x)
, is the proportion of adversarial images of fooling OCR models to output targeted text.
3) Attack efficiency. I avg is average iterations of images to reach 100% ASR. Table 1 illustrates generated adversarial examples. We find that the perturbations of basic attacks are quite obvious, especially when we want to replace the entire word, while the watermarks help hide the perturbations from human eyes.

Letter-level Attack Performance
To intuitively analyze the effects of watermarks on our attacks, in Fig. 2, we first illustrate the saliency map that highlights the influence of each pixel on the target output t. In replacement cases, we observe that the white background needs more perturbations, both positive (+) and negative (-), while the gray background requires 72% less perturbations due to reduced contrast. Watermarks approximate the gray background and look more natural. Specifically, the attack of the white background also adds significant a-shaped negative perturbations to weaken the letter a, while the other two require negative perturbations less than 50% due to lower contrast. In addition, the attacks add perturbations to neighboring letters, as the sequence-based OCR models also consider them. Table 2 and Fig. 3 show the quantitative analysis of attack performance and use different targets in letter-level attacks. In Fig. 3 a higher efficiency, that reaches a higher ASR in a fixed number of iterations. ASRs of all attacks are 100%. We observe that: 1) MSEs of watermark attacks are only 40% of basic attacks' on average, confirming to the intuitive analysis above. 2) Watermark attacks only require 78% fewer I avg on average, and have around 3 to 8 times sharper slope than basic attacks, showing the significant improvement of attack efficiency. 3) Not surprisingly, hard cases require both more perturbations (higher MSE) and more iterations (larger I avg ) with lower efficiency (flatter slope), due to lack of similarity between two letters. 4) In addition, deletions are easier than insertions and replacements. This is because OCR models are sensitive to perturbations, and classify fuzzy letters into blank tokens that will be ignored by CTC in the output. Intuitively, in the saliency map of Fig. 2, perturbations of deletion are much slighter than other cases. Thus few perturbations can achieve deletion. 5) Courier font is easier to attack because it is thinner than other fonts. Thus it requires less perturbations. 6) Comparing gradient-based and optimization-based methods, the perturbation level is higher in gradient-based methods, no matter if they have watermarks or not. Because perturbations of optimization-based methods are not constrained by .

Word-Level Attack Performance
We can still achieve 100% ASR in the word-level attacks, but both MSE and I avg of word-level attacks are significantly higher than those of letter-level attacks. We perform word-level attacks in word, sentence and paragraph images. Table 3 and Fig. 3(c) summarize results in word-level attacks. Due to limited space, we only show results of gradient-based methods. The optimization-based methods have similar insights. In word-level attacks, we have similar observations as letter-level attacks. 1) Watermark attacks spend 50% less I avg with higher efficiency (sharper slope) generating adversarial images than basic attacks. 2) We observe 56% lower MSE with watermarks averagely. 3) It is easier to attack Table 2. Letter-level attacks using Grad-Basic, Grad-WM, Opt-Basic, Opt-WM attacks. Last line is the target output. We denote each font with their first letter.

Gradient-based
Optimization-based replacement insertion deletion replacement insertion deletion easy random hard easy random hard Courier font than other fonts for less MSE and I avg . 4) Due to a larger number of pixels in sentence and paragraph images, their MSEs are much lower than MSE of word images, but the absolute number of affected pixels stays the same.

Effects of Hyper-parameter Settings
To better understand these attacks, we evaluate the effects of hyper-parameter settings, such as tradeoff c, L p -norms, font-weight, position of watermarks, etc.
Effects of plain watermarks. First, we evaluate the effects of plain watermarks, i.e., initial watermarks without perturbations. The accuracy of Courier, Georgia, Helvetica, Times, Arial drop to 0.066, 0.768, 0.531, 0.753 and 0.715, respectively, showing that it is quite trivial to launch untargeted attacks on OCR. Also, it further confirms that thinner font, Courier, is highly sensitive to plain watermarks. In samples of incorrect recognition, we count the percentage of output text shorter than the ground-truth text, Courier(0.65), Georgia(0.12), Helvetica(0.08), Times(0.09), Arial(0.14). It's easy to induce that thinner font is more sensitive to perturbations resulting in losing letters like the deletion case.
Tradeoff between efficiency and visual quality. In both gradient-based and optimization-based methods, we need to set tradeoff parameters to balance between efficiency (I avg ) and visual quality (MSE). In Fig. 4, we plot the change of I avg and MSE along with distinct tradeoff settings. In gradient-based methods, we can reduce perturbation level with smaller step size α, at the cost of attack efficiency (raised I avg ). In optimization-based methods, the main quality-efficiency tradeoff parameter c balances the targeted loss and the L p -norm distance. We find that a smaller c makes the optimized objective function pay more attention to reduce the perturbation level with larger I avg . Thus we can use the binary search for c to find adversarial examples with a lower perturbation level under  the premise of maintaining perfect ASR. In addition, in various hyperparameter settings, the performance of watermark attacks is better than the basic attacks.
Setting L p -norms. L ∞ -norm for measuring the maximum variation of perturbations has the same perturbed value at each perturbed pixel, and thus significantly narrows down operation space. Even more, observing L ∞ -norm examples in Table 4, L ∞ -norm causes severe background noise. L 2 -norm yields perturbed values varying in perturbed pixels, and thus offers better flexibility to perform stronger adversarial attacks. Although L 2 -norm is lower efficient than L ∞ -norm in Fig. 3(c), L 2 -norm's image quality metrics, MSE, PSNR and SSIM, in Table 4, all are better than those of L ∞ -norm. Intuitively, L 2 -norm examples also have better visual quality. Therefore, we choose the L 2 -norm in our experiments.
Bold fonts settings. We also investigate the bold version of the five fonts. Table 4 shows most bold fonts require slightly more MSE and I avg to attack successfully, except for Courier requiring doubling MSE. This is not surprising, as bold fonts contain more useful pixels per letter. So they need more perturbations.  Attacking sequence-based OCRs. As OCR recognizes entire sequences rather than individual characters, we demonstrate that we can replace a letter even the watermark does not overlap with the letter, indicating we will not add perturbations over it. In this experiment, we shift the watermark about 10 pixels right to the target letter when generating initial watermarked images. Table 5 summarizes results that the attacks require 18 times MSE and 34 times I avg , and ASRs drop to less than 50% except for the simplest Courier case. It confirms the fact that in sequential-based OCRs, the influence around the letter is not as important as that overlaying the letter. Also, it reveals the necessity of finding the position of watermarks accurately to perform strong adversarial attacks.

Extensions and Applications of Watermark Attacks
Full-color watermarks. Sometimes adding gray watermarks still hurts human readability. We use the fact that modern OCR first transforms colored images into gray ones before recognition. Colored watermarks significantly improve overall readability when mixed with black texts. Fig. 5 shows a colored-watermark  Table 6. Protection mechanism. Acc and Acc* are the prediction accuracy with and without protection, respectively.
MSE Iavg Acc Acc* example Courier 0. 6   example of altering a positive movie review into a negative one by replacing and inserting words in it. Note that not all watermarks are malicious (e.g., the watermark on "I have ever seen" of Fig. 5 does not include adversarial perturbations). We evenly distribute watermarks over the paragraph image to make it look more similar to a naturally watermarked paragraph image in the real-world scenario.
Attacking Chinese Characters. In addition to English, we show that the method is applicable to other languages. Fig. 6 shows a Chinese example where we almost altered all important information, and its perturbation level is much larger than that in Fig. 5, because of the complex structure of Chinese characters.
Using FAWA to enhance the OCR readability of watermarked contents. Sometimes we want people to notice vital watermarks (e.g., urgent, confidential), but we do not want them to affect OCR's accuracy. In such case, we generate accuracy-enhancing watermarks by setting the ground-truth as the target. In Table 6, with few I avg and MSEs, Acc (accuracy with protection mechanism) increases to 1.0 compared with the low Acc* (accuracy of initial watermarked images). It works because protective perturbations strengthen the features of the ground-truth and boost the confidence of the original, making it more "similar" to the target (i.e., the ground-truth). As the target is the same as  the original, both MSE and I avg stay low. So we can use FAWA as a protection mechanism to produce both human-friendly images and OCR-friendly images.


extfieldsofstudy:
Medicine
Computer Science

text:
Two-Dimensional Quantum Genetic Algorithm: Application to Task Allocation Problem

This paper presents a Two-Dimensional Quantum Genetic Algorithm (2D-QGA), which is a new variety of QGA. This variety will allow the user to take the advantages of quantum computation while solving the problems which are suitable for two-dimensional (2D) representation or can be represented in tabular form. The performance of 2D-QGA is compared to two-dimensional GA (2D-GA), which is used to solve two-dimensional problems as well. The comparison study is performed by applying both the algorithm to the task allocation problem. The performance of 2D-QGA is better than 2D-GA while comparing execution time, convergence iteration, minimum cost generated, and population size.

Introduction
The Genetic algorithm (GA) [1] is a class of bio-inspired algorithms that can produce the optimal or near-optimal solution of complex optimization problems in a reasonable time. It was first proposed by Holland [2] inspired by Darwin's principle of survival of the fittest. The possible solution of an optimization problem is encoded in a chromosome which consists of an array of bits called genes. The individual chromosome is evaluated by a fitness function. A genetic population consists of a finite number of chromosomes. The chromosomes of the new population are generated by the application of genetic operations such as crossover, mutation, and reproduction on the present population. The new population optimizes the fitness function and thus provides an improved solution. The solution thus approaches the optimal solution over several generations. There exist many applications of GA viz. optimization [3,4], machine learning [5], neural networks [6], fuzzy logic controllers [7], identification [8], fault diagnosis [9], and financial market [10].
As quantum technology emerges as a powerful computational tool, there was an effort to combine quantum computation [11,12] with intelligent optimization algorithms. The first attempt to combine quantum mechanics principles and Genetic Algorithm was made by Narayanan and Moore to propose Quantum Genetic Algorithm (QGA) [13]. QGA is applicable to the category of problems which are solved using conventional genetic algorithm. Moreover, QGA speeds up the computation of genetic evolutionary process by exploiting the power of quantum computation. QGA has higher convergence rate, less execution time, less population size, and strong global search capability [14][15][16]. QGA has been proved to be efficient in solving various kind of problems such as combinatorial and functional optimization problems, engineering optimization problems, image processing and identification, and many others. A few example application can be found in [14,[17][18][19][20][21][22][23][24] and many more.
The GA and QGA discussed so far consider the chromosomes as a one-dimensional array. Obviously, these chromosomes cannot represent a possible solution for the problems which naturally have two-dimensional representation. Examples of such problems include Ising problem, Packing problem, Scheduling problem, Optimal topology in Multi-Agent 1. A novel 2D-QGA is proposed in this paper, which is a new algorithm in GA family.
Thus, the power of quantum computation can be used to solve problems having twodimensional representation. The quantum computation speeds up the computation and delivers optimal results in less time with a smaller population size.

New Qgate rotation technique for 2D chromosomes is proposed in this work. This
Qgate is the key factor to speed up the computation in 2D-QGA. 3. The proposed algorithm is implemented to multi-robot task allocation problem, which has the two-dimensional form and it is egarded as NP-hard. 4. A detailed analysis of the convergence time, iteration, cost, execution time of 2D-QGA is discussed. It also includes a detailed comparison with existing 2D-GA.
The rest of the paper is organized as follows. In Section 2, details of QGA is presented, which is the preliminary for two-dimensional QGA. In Section 3, 2D-QGA is introduced. An application of the algorithm is shown in Section 4. The comparison study is presented in Section 5. A brief conclusion is given in Section 6.

Quantum Genetic Algorithm (QGA)
In this section, the Quantum Genetic Algorithm is discussed, which is the preliminary for two-dimensional QGA. In quantum computation, 2 m independent states can be represented using m qubits. However, during the measurement of the qubits, a single state of the quantum state (i.e., |0 or |1 ) is obtained, which is similar to a conventional genetic algorithm, i.e., a chromosome's representation is defined as a string of m information units.

Qubit Representation
Qubit is the basic unit of information used in quantum computations. In a quantum system, the basic state is not deterministic; i.e., it does not have a fixed value. The basic state maybe |0 , |1 , or any complex value which is a linear combination or superposition of basis states. A qubit is represented in Equation (1) as where α and β are complex numbers which signify the magnitude of left and right vector respectively. α and β satisfy the condition given in Equation (2).
|α| 2 and |β| 2 provide the probabilities that the qubit can be found in the '0' state and '1' state, respectively. The pictorial representation of qubit is given in Figure 1. A chromosome is represented by a string of qubits (given in Equation (3)). The encoding length of the chromosome is n.

Quantum Gate Rotation (Qgate)
The operation for changing the state of the qubit is known as the quantum gate or Qgate. There exist several quantum gates. Examples of such gates are Not gate, controlled-NOT gate, rotation gate, Hadamard gate etc. One of the widely used gates is the rotation gate which is described as follows.
The rotation gate is operated on the present population to obtain the new one. It helps to maintain the diversity of the population, which is a key updating operation in quantum evolution algorithm. Rotation gate U(∆θ i ) is employed to update the probability amplitude of quantum states. The ith qubit (α i , β i ) is updated as follows. where where T is a rotation matrix and θ i = s(α i , β i )∆θ i is rotation angle. s(α i , β i ) is the sign of θ i and it determines the rotation direction. ∆θ i is the amount of rotation. The rotation sign and magnitude is determined in a look-up table which is shown in Table 1.
The rotation gate for qubit individuals in a polar plot is shown in Figure 2. The solution α i β i of current generation is rotated by an angle of ∆θ i anticlockwise to obtain possible best solution ᾱ ī β i . r i corresponds to the binary code of individual chromosome i. The binary code corresponding to the best individual is b i and f (.) denotes the fitness function to find the fitness value. α i β i > 0 signifies that they lie in the first or third quadrant. If α i β i < 0 then the individual i lies in the second or fourth quadrant. If the combination is 0-1, set the rotation angle to be 0.5π. If the combination is similar, i.e., 0-0 and 1-1, select a smaller rotation of angle 0.2π. If it is not possible to determine specific quadrant, then rotation is not preferred.

Initial Population Generation
The qubits present in the initial population have equal probability to be in the state of |0 and |1 . For such case, α = 1 , i.e., |q = 1 have string of such α and β. The encoding length of the chromosome is n and the population size is N. The algorithm for generation population is given in Algorithm 1.

Generate Binary String by Measuring Quantum Chromosome
The function for measuring the quantum chromosome measure_chrom() is shown in Algorithm 2. In this algorithm, a random number x ∈ (0, 1) is generated by MATLAB function rand() and it is compared to each α 2 j (denoted as Chrom(1, j) 2 ) of the chromosome.
Algorithm 2 Initial population of quantum chromosome measure_chrom()

end for
If x > α 2 ij the the (i, j)th element of a temporary matrix B is assigned as 0; otherwise assigned as 1. This matrix B is stacked in a 3D matrix binary.

QGA Algorithm
For better understanding, the QGA algorithm is shown in Algorithm 3. It includes the operations for QGA which are described so far.

Algorithm 3 QGA algorithm
Initialize QGA parameters Generate initial quantum population Q(t)

Two-Dimensional QGA (2D-QGA)
Two-dimensional QGA is a new algorithm which inherits the properties of QGA, and applicable to problems which can be represented by two-dimensional chromosome. The major works are done to present the idea of 2D quantum chromosome and its rotation technique. The description of the 2D quantum chromosome and Qgate rotation is given in the following sections.

Two-Dimensional Quantum Chromosome
In contrast to QGA, a two-dimensional quantum chromosome is a matrix. Each row of the matrix signifies a gene. A diagram of the quantum chromosome is shown in Figure 3. 'i = 1, 2, . . . , m' denotes the objects, and each of them is encoded by a string of qubits of length n. It can be mentioned that the quantum chromosomes encode the instants of all the objects together to represent a solution of a 2D problem. The number of rows is double the number of objects since each row is a string of qubits α and β. The quantum population consist of N two-dimensional quantum chromosomes Ch 1 , Ch 2 , . . . , Ch N as shown in Figure 4. The algorithm for the generation of the population is given in the following section.

Initial Population Generation
The initial population generation for 2D-QGA is slightly different from QGA. The method Init_Pop_2D() is shown in Algorithm 4.

end for
A common strategy is to initially populate the chromosome such that the qubits appear with equal probability i.e., α = β = 1 √ 2 and they change as the algorithm is executed.
Therefore, the initial values of qubits are assigned as 1 √ 2 = 0.7071. A sample quantum chromosome is shown in Figure 5. This is a chromosome generated using Algorithm 4.

Generation of Binary Population
The binary population is generated from quantum population using Algorithm 5. This algorithm is similar to the binary population generation for QGA. The modification is done to apply it for 2D chromosomes. An example of a binary chromosome generated is shown in Figure 6. It is the binary chromosome generated considering the quantum chromosome given in Figure 5.

Qgate Rotation for Two-Dimensional Chromosome
The rotation for 2D quantum chromosome is different because unlike the QGA (each chromosome dimension 2 × n) the chromosomes of 2D-QGA have the dimension of 2m × n. In this paper, two types of quantum gate rotation technique for two-dimensional quantum chromosome are presented. They are described in the following sections.
3.4.1. Qgate Rotation Type-I Each 2D quantum chromosome is a matrix, as shown in Figure 3. It can be noted that each row of this chromosome is similar to the chromosome of QGA (i.e.,1D array). In rotation type-I, the Qgate operation for 2D-QGA is performed for each row using the Qgate for QGA (shown in Table 1). The algorithm for implementing Qgate type-I operation for 2D quantum chromosome is shown in Algorithm 6.

Algorithm 6 Qgate rotation of 2D Quantum Chromosome
Perform checks and operation in Table 1 end for end for

Qgate Rotation Using N-dimensional Rotation Matrix (Qgate Type-II)
In this type, each column vector of the 2D chromosome is rotated. The length of the column vector is 2m. Therefore the rotation matrix should have the dimension 2m × 2m. Fortunately, there exists a well-defined method for such operation, which is known as 'Rodrigues' rotation formula'. The 2D quantum chromosomes are rotated using this method. The definition is given as follows.
Definition 1. If u and v are two orthonormal vectors, a matrix that rotates the span of u and v by angle θ is In every generation, each chromosome is rotated by an angle θ, i.e., all columns ( 2m ) of each 2D quantum chromosome are rotated by the same angle. Rotation angle at each generation is different, and it is selected in a random manner. The sign of the rotation is also random. The rotation process is shown in Algorithm 7.
The population size is N. The chromosomes are represented by Ch(:, :, i), i = 1, 2, . . . , N. The sign of the rotation i.e., s is selected in random manner. In the algorithm, x is assigned random number between 0 and 1 by MATLAB function rand(). if x > 0.5, then assign s = 1; otherwise assign s = −1. The value of θ is obtained by θ = s * rand() * (0.1π). Next, a random matrix M is generated. Then M is converted to orthonormal matrix M orth by MATLAB function orth(). Each rows of M are orthogonal. Two rows of M (for example, first and second row as shown in the algorithm) are selected as u and v. The rotation matrix R(θ, u, v) is calculated using values of θ, u, and v. Finally, the chromosomes are rotated using the rotation matrix. It can be mentioned that, for each chromosome the values of 's' and 'θ' are random. Therefore each chromosome is rotated with different rotation angle.
The flow diagram for implementing the steps of the proposed algorithm is shown in Figure 7.

Application to Task Allocation Problem
The problems which naturally have two-dimensional representation can be solved using 2D-QGA, which considers 2D quantum chromosome as a probable solution. It can be mentioned that the task assignment problem can be represented in two-dimension. In this paper, we will study the implementation of 2D-QGA to solve task assignment problem. It is important to note that the problem considered here is for demonstration purpose. The main focus of the work is to show the implementation of the algorithm to such a problem. The assumptions made for this problem are given as follows.
1. Each drone can perform one task at a time i.e., each drone is assigned to one task at a time. 2. At least one drone is required to finish each task 3. All drones should be assigned with a task 4. The task and drone positions are known The problem is formulated considering these assumptions and given in the following section. The allocation problem is given as follows.

Problem Formulation
x ij = 0, 1 Equations (6)-(8) defines a constrained optimization problem. The constraints in Equations (7) and (8) signifies the assumptions 1-3. The variable d ij is the distance between ith drone and jth task. x ij is a binary variable which takes a value of 1 if ith drone is assigned to jth task, i.e., x ij = 1, otherwise x ij = 0. This cost function is purely distancebased. The objective of the cost function is to minimize the overall distance between the drones and task positions i.e., assign tasks to the drones depending on their distance from them.

Simulation Study
The simulation study is performed considering ten drones (i.e., N D = 10; D = [D 1 D 2 . . . D N D ]) and four tasks (i.e., N T = 4; T = [T 1 T 2 T 3 T 4 ]). It can be mentioned that, this is an example problem. The user can increase the problem size as per the requirement. The task and drones positions are generated in a random manner in an area of length 1000 m and width 100 m using the MATLAB command 'randi'. The task allocation problem has been solved using both types of 2D-QGA, i.e., type-I and II. The simulation is performed on a PC with AMD Ryzen5 (2.3 GHz) processor and 8 Gb RAM. The results obtained using the proposed algorithm are discussed in the following sections.

Results Obtained Using 2D-QGA with Qgate Type-I
The results generated using 2D-QGA with Qgate type-I is shown here. The algorithm is executed for fifty generations. The cost (J) generated for all generations is shown in Figure 8. The algorithm has converged in fourteen generations to achieve minimum cost. The assignment matrix (optimal solution) is a 2D chromosome. This chromosome shows the optimal assignment of drones to the tasks, as shown in Figure 9. A particular task and the drones assigned to that task are marked with the same colour. The tasks T = [T 1 T 2 T 3 T 4 ] are shown in solid circles, and the drones are shown as empty circles. It can be noticed that each drone is assigned to one task. At least one drone is allocated to execute each task. Therefore the constraints are satisfied. The time consumed to execute each generation is shown in Figure 10. It can be observed that most of the generation consumed around 0.57 s. The Qgate type-I consumes around 0.11 s in most of the generations as shown in Figure 11.

Results Obtained Using 2D-QGA with Qgate Type-II
In this case, a different set of task and drone positions are generated. The results are generated using 2D-QGA with Qgate type-II. The cost for all generations is shown in Figure 12. The algorithm converged in 8 generations to produce minimum cost. The task allocation to the drones is shown in Figure 13. The tasks T 1 , T 2 , T 3 , T 4 and the drones assigned to the tasks are shown in the same colour as described in the previous case. Also, the tasks are shown in solid circles and drones in empty circles. Each drone is assigned to one task, and each task is allocated at least one drone. Therefore, the constraints are satisfied by the 2D-QGA type-II. The time consumed to execute each generation is shown in Figure 14. It can be observed that most of the generation consumed around 0.48 s. The time to execute Qgate type-II in each generation is shown in Figure 15. In most of the generations, Qgate type-II needs around 0.011-0.014 s for execution. The results generated using the proposed 2D-QGA algorithms (type-I and II) are discussed individually. However, the effect of quantum computation in 2D-QGA should be evaluated. The appropriate way should be to compare 2D-QGA with an algorithm which solves similar problems. It has been discussed in the introduction section that 2D-GA can solve the problems with two-dimensional representation. Therefore, the performance of 2D-QGA is compared to 2D-GA when they are used to solve the task allocation problem. The results obtained are discussed in the following section.

Comparison Study
The whole study is divided into three parts. In each part, two algorithms among 2D-GA, 2D-QGA type-I, and 2D-QGA type-II are compared. In the first part, the comparison between 2D-GA and 2D-QGA type-I is presented. In the second part, 2D-GA and 2D-QGA type-II are compared, and in the last part 2D-QGA, type-I and II are compared. The algorithms of each part are executed to solve the task allocation problem. It can be mentioned that the task and drone positions remain identical for each part. The comparison is performed by executing the pair of algorithms of each part for a finite number of iterations. In this study, the number of iterations considered to be 50. The general structure of the iteration is shown in Algorithm 8. In the algorithm, the iteration number N is set as 50, but the user can select a different number. In each iteration, the algorithms are allowed to evolve for fifty generations. The comparison between algorithms in each part is based on the points as follows. This measure shows how many times (or %) in a specific number of iterations one algorithm converges in fewer iterations compared to another one. 3. The percentage of iteration one algorithm of a pair takes less time compared to the other one. This is the time consumed by each algorithm of a pair to execute the maximum number of generation in one iteration. 4. The percentage of iteration one algorithm of a pair produces less cost compared to the other one.
These measures are essential to understand the importance of the features that 2D-QGA has. The results obtained for each part is discussed in the following sections.

Part 1: Comparison between 2D-GA and 2D-QGA Type-I
The comparison between 2D-GA and 2D-QGA type-I is given in this section. The population size of both 2D-GA and 2D-QGA type-I is considered to be 2000. The first comparison is about 'Average time consumed' by these algorithms. The comparison result is shown in Figure 16. It can be observed that 2D-GA consumed more time to execute each generation compared to 2D-QGA type-I. The operations involved in each generation for 2D-QGA type-I are designed by quantum computation. The next comparison is about the percentage of iteration the algorithms take fewer generations for convergence. The comparison is shown in Figure 17. It can be observed that 80% of iterations the 2D-QGA type-I takes fewer generations to converge.  Another important comparison is the total time taken by the algorithms to execute an equal number of generations. The result obtained is shown in Figure 18. It can be noticed that 2D-QGA type-I need lees execution time for all the iterations. The last and one of the most important comparison is the percentage of iterations the algorithms produce less cost. 2D-QGA type-I produces less cost for 100% of the iterations, as shown in Figure 19. The comparison is summarized in Table 2.   In this study, it is clear that 2D-QGA type-I is more efficient compared to 2D-GA. In the following section, the comparison between 2D-GA and 2D-QGA type-II is presented.

Part 2: Comparison between 2D-GA and 2D-QGA Type-II
The comparison between 2D-GA and 2D-QGA type-II is given in this section. The population size of both 2D-GA and 2D-QGA type-II are 2000. The average time consumed by 2D-GA and 2D-QGA type-II is shown in Figure 20. The time consumed to execute each generation by 2D-QGA type-II is less compared to 2D-GA. Figure 21 shows the percentage of iterations the algorithms converge with fewer generations. It is clear that 2D-QGA type-II converges with fewer generations for 60% of iterations.
The total time of execution of the same number of generations is compared in Figure 22. 2D-QGA type-II has consumed less execution time for 90% of iterations.   The comparison of percent of less cost generation is shown in Figure 23. It can be noticed that 2D-QGA type-II produces less cost for 90% of iterations. The comparison is summarized in Table 3.  The comparison between 2D-GA and 2D-QGA (type-I and II) is made in parts 1 and 2. Both types of 2D-QGA have performed much better compared to 2D-GA in terms of average execution time per generation, per cent of iterations each algorithm converges in fewer generations, consumes less execution time, and produces less cost. Moreover, the quantum computation helped the 2D-QGA to reduce the number of generations for convergence and overall execution time. Therefore the 2D-QGA speeds up the computation for the class of problems discussed in this paper.
It is clear that both types (I and II) of 2D-QGA are more efficient than 2D-GA. Also, there should be a similar comparison between them to identify the more efficient one. This comparison primarily reflects the influence of the Qgate operation involved in each type of 2D-QGA. In part 3, the comparison between 2D-QGA type-I and type-II is presented.

Part 3: Comparison between 2D-QGA Type-I and 2D-QGA Type-II
The comparison between 2D-QGA type-I and 2D-QGA type-II is given in this section. For a proper comparison, the population size of both 2D-QGA type-I and 2D-QGA type-II is considered to be 2000.
It can be observed that the average execution time per generation consumed by 2D-QGA type-II (around 0.47 s) is less than 2D-QGA type-I (around 0.55 s) as shown in Figure 24. The percentage of iteration each algorithm converges in fewer generations is shown in Figure 25. It can be observed that 78% of the iterations, 2D-QGA type-II converges in fewer generations compared to 2D-QGA type-I. In case of total execution time, 2D-QGA type-II consumes less for almost all of the iterations (97%) as shown in Figure 26.   Percent of iterations each algorithm produces less cost is shown in Figure 27. 2D-QGA type-II produces less cost for 80% of the iterations. The comparison is summarized in Table 4.  In addition to the comparison shown above, it is important to compare the execution time of 2D-QGA type-I and II for each generation in the same iteration. This comparison is shown in Figure 28. The execution time for each generation for type-I is more than type-II, i.e., type-II is faster. It can be observed that type-II takes around 0.1 s less time per generation compared to type-I and saves around 4-5 s over 50 generations. The saving of time increases if the number of generations is increased. The main reason behind type-II being faster is the time consumed by the Qgate process in type-II is much less than type-I.  The time consumed by Qgate of type-I and II is shown in Figure 29. The time consumed by Qgate type-I and II is around (average value) 0.12 s and 0.017 s respectively.
It is clear that 2D-QGA type-II has the advantage over type-I in terms of execution time per generation, total execution time, and convergence iterations. These advantages are important features of 2D-QGA type-II, which are useful for solving problems having two-dimensional representation. There are a few factors that can affect the performance of the proposed algorithm. The quality of optimal solution depends on the population size, the number of generations, formulation of appropriate cost function etc.

Conclusions
The simulation study showed that both types of 2D-QGA (type-I and II) had consumed less average execution time per generation compared to 2D-GA. This leads to less total execution time for 2D-QGA. Almost all the time (80-90%) the 2D-QGA produces less cost consuming fewer generations compared to 2D-GA. All of these improvements are achieved with population size much less than 2D-GA. The proposed Qgate type-I and II speeds up the computation. In particular, the type-II is faster between the two types. Therefore the 2D-QGA is a potential algorithm for solving problems with two-dimensional representation.

Conflicts of Interest:
The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.