# Towards Image Semantics and Syntax Sequence Learning

Chun Tao
School of Electrical and Computer Engineering
Purdue University
465 Northwestern Ave, West Lafayette, IN 47907
<EMAIL_ADDRESS>Timur Ibrayev
School of Electrical and Computer Engineering
Purdue University
West Lafayette, IN 47907
<EMAIL_ADDRESS>Kaushik Roy
School of Electrical and Computer Engineering
Purdue University
465 Northwestern Ave, West Lafayette, IN 47907
<EMAIL_ADDRESS>
###### Abstract

Convolutional neural networks and vision transformers have achieved
outstanding performance in machine perception, particularly for image
classification. Although these image classifiers excel at predicting image-
level class labels, they may not discriminate missing or shifted parts within
an object. As a result, they may fail to detect corrupted images that involve
missing or disarrayed semantic information in the object composition. On the
contrary, human perception easily distinguishes such corruptions. To mitigate
this gap, we introduce the concept of ”image grammar”, consisting of ”image
semantics” and ”image syntax”, to denote the semantics of parts or patches of
an image and the order in which these parts are arranged to create a
meaningful object. To learn the image grammar relative to a class of visual
objects/scenes, we propose a weakly supervised two-stage approach. In the
first stage, we use a deep clustering framework that relies on iterative
clustering and feature refinement to produce part-semantic segmentation. In
the second stage, we incorporate a recurrent bi-LSTM module to process a
sequence of semantic segmentation patches to capture the image syntax. Our
framework is trained to reason over patch semantics and detect faulty syntax.
We benchmark the performance of several grammar learning models in detecting
patch corruptions. Finally, we verify the capabilities of our framework in
Celeb and SUN-RGBD datasets and demonstrate that it can achieve a grammar
validation accuracy of 70 to 90% in a wide variety of semantic and syntactical
corruption scenarios.

##  1 Introduction

Figure 1: ViT-B/16,224 tested on corrupted dog images. Corruptions from left
to right: 1) permutation type I 2) permutation type II 3) 1-patch blackout 4)
2-patch Gaussian blurring, kernel size$=(7,7)$, sigma$=3$. All top-5
predictions are dog breeds, shown as softmax-ed probabilities

Current image classification techniques involve training Deep Neural Networks
(DNN) to extract high-dimensional features from the entire image and then
decode the features to produce class predictions. For such classification
tasks, Convolutional Neural Networks (CNNs) [31, 45, 22] and Vision
Transformers (ViTs) [13, 38] are state-of-the-art (SoTA) models. CNNs learn
the distribution of images belonging to different object classes by extracting
low- and high-level semantic information from images and encoding them in
hidden features of different layers [24, 40]. They can also be trained to
effectively detect out-of-distribution (OOD) anomalies [8, 55]. Different from
OOD anomalies, samples with syntactical anomalies (corruptions) do not
introduce new semantics, but are noisy in-distribution (ID) samples [54, 40].
CNNs have been shown to consistently produce high confidence in the
classification of these samples [1, 63]. Although research have shown that
ViTs tend to make better predictions on these samples than CNNs [47, 65, 14],
they may still not be able to identify in-distribution corruptions. Fig.1
shows the test results of a vit-base-patch16-224 model pretrained on ImageNet
[11] on 2 random dog images from the Stanford Dogs dataset [29]. For the
semantically and (or) syntactically corrupted images (in-distribution
samples), the top 5 most probable classes predicted by the ViT model are
always dog breeds, out of 1000 classes in ImageNet. We further verified this
result on all 8580 test set images. The results indicate that current image
classifiers are vulnerable to object-level semantic and syntactical in-
distribution corruptions. In this work, we tackle noisy in-distribution
samples that involve object- and scene-centric [44] semantic corruptions such
as patch shuffling, blackout, blurring, etc.

To address the above issues, a ”grammar” analysis of the image is necessary.
The concept of image grammar consists of image semantics and image syntax,
analogous to their counterparts in the language domain [17, 50]. While ”image
semantics” refers to individual meaning and significance of parts that compose
a valid object [43], ”image syntax” defines the spatial positioning and
arrangement of these part semantics that reside in an object to align with the
well-formed object composition of a given class [5]. An effective machine
learning (ML) system capable of recognizing part-level image corruptions will
then need to be trained to 1) extract pixel-wise semantics from the content of
the input image and 2) sequentially visit the learned semantics patch by patch
to verify whether the relative positioning of these patches is correct with
respect to the object class of interest. We illustrate syntax learning with
part semantic information in Fig.2. In glimpse 1 of Fig.2, we show a patch of
the human face on the left and its semantic components belonging to the
”face”, ”nose”, and ”mouth” classes on the right. The semantic segmentation of
the patch is called part semantics. When the model shifts up from the current
patch to glimpse 2, new part semantics belonging to the ”eyes”, ”eyebrow”, and
”hair” classes appear. The transition from the part semantics of glimpse 1 to
that of glimpse 2 represents an episode of the syntax sequence of the ”human
face” object class.

We propose a weakly-supervised two-stage deep learning framework that
successively learns part semantics and image syntax as described above. In the
first stage, we utilize a feature extractor network (Feature Pyramid Network
(FPN) with CNN backbone) to produce pixel-wise semantic features. The FPN is
fine-tuned on a small number of semantic segmentation masks, generated using
deep clustering technique [6], a visual representation learning tool. The idea
is to iteratively 1) cluster pixel-wise features 2) minimize distance between
these features and the centroid vectors they are assigned to. The latter step
ensures that the feature extractor network learns to produce features that
align better with the existing bank of centroids, each representing a semantic
concept, in the next iteration. Pixel-level features become cluster-friendly
throughout training iterations and are mapped to their corresponding
semantics. We further adopt augmentation to enhance color invariance and
geometric equivariance in clustering results [9]. The first stage helps divide
the object in an image into segmentations of semantically rich parts. In the
second stage, we first fine-tune the feature extractor on the semantic masks
of the parts. Then, we define a patch traversal sequence for all images
containing the same object. Patch traversal iterates through image part
patches in a fixed order in order to construct a sequence of part semantic
masks. For each image, we feed the sequence of part semantic masks to a
recurrent bi-LSTM module, following the traversal rules we have defined
(Fig.3). In a bi-LSTM, we utilize the long-short-term memory to handle bi-
directional dependencies in the sequence of image part semantics and,
consequently, to learn image syntax. Finally, during the test phase, agnostic
to the corrupt state of the input image, the bi-LSTM module traverses the part
semantics of patches in the same order defined earlier and aggregates its
prediction error. For each image, the total prediction error is thresholded to
detect potential corruptions. Note that we do not train our pipeline on any of
the noisy in-distribution samples described above but only on samples with
correct grammar. However, the pipeline utilizes its knowledge of the semantics
of the parts of the image and the syntax of the image to check the grammar
correctness of the test images.

Our key contributions include:

  1. 1.

Image grammar analyses to verify class label integrity of noisy in-
distribution samples;

  2. 2.

A weakly-supervised two-stage learning system that combines pixel-wise
semantic extraction and syntax sequence learning to capture image grammar with
respect to an object/scene class; Testing the capability of the system in
detecting in-distribution anomaly samples;

  3. 3.

Benchmarking the effectiveness of several image grammar validation methods on
two datasets.

##  2 Related Work

Performing image grammar analysis for visual objects requires a combination of
visual semantic perception and understanding and reasoning in the context.
Below, we investigate perspectives around the capabilities of CNNs and ViTs in
handling the above functionalities.

Figure 2: Illustration of a transition in patch sequence and its consistent
shift in semantic segmentation

#### Self-Supervised Visual Representation Learning and Feature Clustering

To extract semantics from an image, visual representation learning is
required, in which meaningful and compact features are extracted from raw
visual data. A number of early works have combined layers of weights to
produce deep supervised predictors, including neural networks [3, 4]. Since
then, convolutional neural networks (CNNs) [31, 45, 22] have been extensively
applied for the extraction of vision features. CNNs are capable of learning
hierarchical features. As a result of their ability to capture both low-level
and high-level features, they enable better generalization. More recently,
ViTs encode representation of fine and coarse structures in patch embeddings.
[12]. They effectively capture long-range dependencies across patches through
the self-attention mechanism [34, 38]. In view of the arduous nature of data
labeling, researchers have developed methods of unsupervised and self-
supervised learning (SSL) [53, 23, 51, 58, 61]. To enhance semantic learning
with CNN, ViT, and Autoencoder(AE) models, these contrastive learning methods
ensure full use of correlations between features across views or patches.
Additionally, contrastive learning is often coupled with clustering and
pseudo-labeling in SSL approaches [6, 7, 15]. Authors in [59, 56, 18] first
integrated image clustering and representation learning into a single model.
DeepCluster [6] iteratively groups features with K-means clustering algorithm
and uses the subsequent assignments as a supervision for updating the feature
extractor network. Deep clustering makes feature representation learning
suitable for clustering tasks [62, 18, 52].

#### Weakly-supervised Part Semantic Segmentation

Joint clustering and feature learning methods are naturally suitable for
unsupervised semantic segmentation tasks, especially for datasets that are
semantically homogeneous. The segmentation result depends on the scale and
granularity of the homogeneous semantic concepts within the dataset. When the
dataset is object-centric such as CelebA with aligned faces, the semantic
segmentation task reduces to clustering pixel-level features, resulting in
object-part (face parts) segmentation; whereas when the dataset is scene-
centric, like SUN-RGBD with different room layouts, adopting the same pixel-
level semantic segmentation results in common stuff (floor, wall, ceiling,
etc.) and things (desk, table, chair, etc.) segmentation. A few unsupervised
semantic segmentation approaches involving clustering have emerged in past
years. The authors in [42, 26, 2] iteratively refine their model weight with
deep clustering, spatial consistency, and contrastive learning. For our
semantics-learning purpose, we chose to implement a modified version of PiCIE
[9], thanks to the adjustable granularity of its pixel segmentation and
universality to segment both ”stuff” and ”things”. Similar to distilled
feature correspondence in [20] and mask proposals in [49], in our experiments
on CelebA we add a visual prior to our pixel-level features by finetuning the
feature extractor model on coarse CelebAHQ [32] masks, before deep clustering
training. This leads to human-recognizable semantic masks of face parts as
shown in Fig.3.

#### Image Grammar Validation with Sequential Models

There is evidence that CNNs and ViTs do not tend to alter their
classifications when images are naturally corrupted[64, 48, 19, 16]. Whie CNNs
may not distinguish positional disruptions among patches due to its
translational invariance [64, 48], this trend is more pronounced for ViTs, as
the attention mechanism ignores patch corruptions while focusing on the main
foreground for prediction [19, 16]. As shown in Fig.1, we verified this
behavior of ViTs. This means that these image classifiers are unable to reason
over patch semantics, construct proper grammar, and detect in-distribution
grammar corruptions. The use of recurrent neural networks (RNNs) appears an
ideal solution to this problem. Previously, RNNs have been used to process
image patches sequentially. The RAM [39] takes into account fixations around
different locations within the image one at a time, and combines the
information into a more dynamic scene representation. Other works used LSTM
models to selectively attend to parts of the image while performing retrival
tasks [57, 36]. Our work involves encoding sequential image syntax learning in
a bi-LSTM model based on an individual object or scene class. During training,
it learns to predict patch semantics based on neighboring semantics in the
syntactical sequence, and during testing, it detects in-distribution anomalies
based on its predictions.

##  3 Method

In this section, we describe the training and test methods adopted in our
grammar validation pipelines, illustrated in Fig.3, 4. To begin with, we
assume that the objects inside input images are localized with techniques such
as [10, 25]. Such an assumption matches the requirement that the dataset needs
to be semantically homogeneous: it only contains images that consist of a
single uniform class (either a class of objects or scenes). Aligned CelebA and
SUN-RGBD both meet this criterion. Once localized images are obtained, we
propose 2 stages of processing: 1) part semantic clustering and 2) image
syntax learning. The realization of each stage is discussed below.

Figure 3: Training pipeline Figure 4: Test methods for grammar validation

###  3.1 Stage 1: Part Semantic Clustering

To fully understand the semantics of parts inside an image containing a
localized object, the unlabeled input images are mapped to their semantic
segmentation at the pixel level. To automate semantic learning and train these
visual features with little supervision, deep clustering [6, 9] is used:
alternately cluster the most recent features and then use cluster assignments
as pseudo-labels to refine the feature extractor model. Despite the appeal of
an unsupervised setting, semantic richness on the part level cannot be
guaranteed. In our empirical study, deep clustering results in segmentation
that only separates the entire object from the background (e.g., in CelebA,
the entire face is rendered as a single cluster). This is due to greater
variation in color between the object and the background than among parts
within the object itself. In order to extract part semantics from the DNN
feature extractor, we fine-tune it under weak supervision from a subset of
pixel-level segmentation masks. We map ground truth (GT) masks to coarse
classes to represent part semantics.

Suppose that we have input images $x_{i},i=1,...,N$ and a subset of them has
pixel-level annotations $m_{jp},j=1,...,M,M\ll N$. Let us assume that we have
$C$ semantic classes in the preprocessed ground-truth (GT) annotations and
$\forall j,p,m_{jp}\in[0,1,...C-1]$. The feature extractor has an embedding
function $f_{\theta}$, which produces pixel-level feature vectors
$z_{ip}=f_{\theta}(x_{i})[p],z_{ip}\in\mathbb{R}^{d}$.

During the fine-tuning phase, we feed pixel-level embedding features to a
parametric linear classifier $g_{\omega},\omega\in\mathbb{R}^{d\times C}$, so
that the feature dimensions are projected onto the number of semantic classes
$C$. For all images $x_{j}$ that have GT masks, the resulting pixel-level
prediction becomes $g_{\omega}(z_{jp})$. To fine-tune the feature extractor to
have a part semantics visual prior, we minimize the cross entropy loss between
pixel-level prediction $g_{\omega}(z_{jp})$ and GT segmentation mask $m_{jp}$,
we optimize the following:

$\displaystyle\min_{\theta,\omega}{\mathcal{L}_{CE}(g_{\omega}(f_{\theta}(x_{j})[p]),m_{jp})}\quad\text{where}$
$\displaystyle\mathcal{L}_{CE}=-\log{\frac{\exp(g_{\omega}(z_{jp})[m_{jp}])}{\sum\limits_{k=0}^{C-1}{\exp(g_{\omega}(z_{jp})[k])}}}$
(1)

We can discard the classifier once the feature extractor has been fine-tuned
and improved by part semantics prior. Now, we begin DeepCluster training with
practices outlined in [9] so that the model can automatically distinguish the
most reasonable part semantics.

To get a semantic grouping of pixels, in PiCIE training [9] inductive biases
are added in the form of photometric invariance and geometric equivariance.
Photometric transformations include color jittering and are denoted $P$, while
geometric transformations refer to random cropping and flipping, denoted $G$.
As demonstrated in Fig.3, trained images are sampled into 2 transformation
streams. First, for an input image $x_{i}$, photometric transformations
$P^{(1)}_{i}$ and $P^{(2)}_{i}$ are applied in each of the streams. An
additional geometric transform $G^{(2)}_{i}$ is applied in the bottom stream.
Afterward, both $P^{(1)}_{i}(x_{i})$ and $G^{(2)}_{i}(P^{(2)}_{i}(x_{i}))$ are
fed to the fine-tuned feature extractor before the scaled geometric
transformation $G^{(1)}_{i}$ is applied to feature map in the top stream in
Fig.3.

Because the feature map is reduced in width and height compared to the
original image, the cropping transform in $G^{(2)}_{i}$ is scaled with the
same ratio to obtain $G^{(1)}_{i}$. We then have pixel-level features ready to
cluster in top and bottom streams denoted as,

$\displaystyle z^{(1)}_{ip}=G^{(1)}_{i}(f_{\theta}(P^{(1)}_{i}(x_{i})))[p]$
(2) $\displaystyle
z^{(2)}_{ip}=f_{\theta}(G^{(2)}_{i}(P^{(2)}_{i}(x_{i})))[p]$ (3)

The pixel-level features in each stream are clustered with K-means algorithm.
We apply overclustering and determine the number of clusters $K$. The K-means
clustering loss becomes,

$\displaystyle\mathcal{L}_{Kmeans}=\sum\limits_{i=1}^{N}\sum\limits_{p}\sum\limits_{k=1}^{K}{\lVert
z_{ipk}-\mu_{k}\lVert^{2}}$ (4)

where $\mu_{k}$ is the $k-th$ centroid. By optimizing the loss in 4 until it
converges, we have cluster assignments $\mathbf{y^{\prime}}$ and a centroid
matrix $\boldsymbol{\mu}$ for each stream,

$\displaystyle\mathbf{y^{\prime}}^{(1)},\boldsymbol{\mu}^{(1)}=\arg\min_{\mathbf{y^{\prime}},\boldsymbol{\mu}}\sum\limits_{i=1}^{N}\sum\limits_{p}{\lVert
z^{(1)}_{ip}-\mu^{(1)}_{y^{\prime}_{ip}}\lVert^{2}}$ (5)
$\displaystyle\mathbf{y^{\prime}}^{(2)},\boldsymbol{\mu}^{(2)}=\arg\min_{\mathbf{y^{\prime}},\boldsymbol{\mu}}\sum\limits_{i=1}^{N}\sum\limits_{p}{\lVert
z^{(2)}_{ip}-\mu^{(2)}_{y^{\prime}_{ip}}\lVert^{2}}$ (6)

We follow the same mechanism for computing cluster losses as specified in
PiCIE [9]. To avoid insufficiently trained classifiers and their noisy
gradients, we abandon the parametric classifier $g_{\omega}$ and instead
compute the distance between the pixel-level features $z_{ip}$ and the
centroids $\boldsymbol{\mu}$ as a DeepCluster loss. We train the feature
extractor model with the following DeepCluster (DC) objective,

$\displaystyle\min_{\theta}{\sum\limits_{i=1}^{N}\sum\limits_{p}{\mathcal{L}_{DC}(z_{ip},y^{\prime}_{ip},\boldsymbol{\mu})}}\quad\text{where}$
$\displaystyle\mathcal{L}_{DC}(z_{ip},m_{ip},\boldsymbol{\mu})=-\log{\frac{\exp(-d(z_{ip},\mu_{y^{\prime}_{ip}}))}{\sum\limits_{k=1}^{K}{\exp(-d(z_{ip},\mu_{k}))}}}$
(7)

$d(\cdot,\cdot)$ is the cosine distance. The total PiCIE [9] loss is composed
of 2 parts. 1) in each of the top and bottom streams, the feature vectors are
expected to adhere to their clustering labels, so that they can encode the
same semantic concepts in each of the banks of clusters. That loss is called
the ”within” loss. 2) to ensure that the clustering result is invariant to $P$
and equivariant to $G$, feature vectors from one stream are expected to match
cluster assignments and centroids of the other; thus a ”cross” loss is
incurred. The total loss
$\mathcal{L}_{total}=\mathcal{L}_{within}+\mathcal{L}_{cross}$, where

$\displaystyle\mathcal{L}_{within}$
$\displaystyle=\sum\limits_{i=1}^{N}\sum\limits_{p}{\mathcal{L}_{DC}(z^{(1)}_{ip},{y^{\prime}}^{(1)}_{ip},\boldsymbol{\mu}^{(1)})}$
(8)
$\displaystyle+{\mathcal{L}_{DC}(z^{(2)}_{ip},{y^{\prime}}^{(2)}_{ip},\boldsymbol{\mu}^{(2)})}$
$\displaystyle\mathcal{L}_{cross}$
$\displaystyle=\sum\limits_{i=1}^{N}\sum\limits_{p}{\mathcal{L}_{DC}(z^{(1)}_{ip},{y^{\prime}}^{(2)}_{ip},\boldsymbol{\mu}^{(2)})}$
(9)
$\displaystyle+{\mathcal{L}_{DC}(z^{(2)}_{ip},{y^{\prime}}^{(1)}_{ip},\boldsymbol{\mu}^{(1)})}$

###  3.2 Stage 2: Image Syntax Learning

In this stage, we learn image syntax, which is the arrangement of parts that
create a meaningful image. Analogous to syntax in the language domain, we
expect certain semantic patterns to display sequentiality within an image.
Depending on how the image is traversed and the size of the image patches, the
semantics sequence may be too diverse to be learned in an image syntax study.
Hence, it is necessary to determine the traversal rules for a particular class
of objects before learning the image syntax.

Shown in Fig.5 and 8 are the traversal rules we decided for faces and for room
layouts. Because faces are localized in aligned CelebA (object-centric), we
apply five crops around the center point of the image, and circularly transit
among these patches. For room layouts in the SUN-RGBD dataset (scene-centric),
we zig-zag through the image patches from top to bottom, left to right.

Having established the traversal scheme, we begin constructing the image
syntax. Note that the syntax-learning system learns sequences of part
semantics from natural images and generalizes that knowledge to detect
anomalies in wild images. In training, we do not include any corrupted images.
For image $x^{(i)},i=1,...,N$ and patch id $t,t=1,...,G$, where $G$ refers to
the number of patches, we resize and crop an image patch $x^{(i)}_{t}$ and its
corresponding semantic segmentation at the pixel level $m^{(i)}_{t}$. The
$p^{th}$ pixel has the semantic class $m^{(i)}_{tp}$. For each $m^{(i)}_{t}$,
we prepare its semantic vector $s^{(i)}_{t}$ by computing the proportion of
each semantic class in its flattened form.

To process image part semantics sequentially and learn image syntax, we employ
a recurrent neural network (RNN). Specifically, as both directions in the
traversal of part semantics are valid sequences to be learned, we use a bi-
directional Long Short-Term Memory (bi-LSTM), parameterized by
$\mathbf{W}=\\{W_{i},W_{f},W_{g},W_{o}\\}$ and
$\mathbf{b}=\\{b_{i},b_{f},b_{g},b_{o}\\}$. For an input image $x_{i}$, we
traverse each of its crop masks $m^{(i)}_{t},t=1,...G$. The input
$\hat{x}^{(i)}_{t}$ in timestep $t$ is the concatenation of the encoded part
semantic mask $m^{(i)}_{t}$ (positional and semantic cues) and a semantics
vector $s^{(i)}_{t}$ (semantic cue). At timestep $t$, the bi-LSTM model has 2
predictions,
$p^{(i,for)}_{t}=L_{\mathbf{W,b}}(\hat{x}^{(i)}_{t},h^{(i,for)}_{t})$ for the
next semantics $s^{(i)}_{t+1}$ and
$p^{(i,back)}_{t}=L_{\mathbf{W,b}}(\hat{x}^{(i)}_{t},h^{(i,back)}_{t})$ for
the previous semantics $s^{(i)}_{t-1}$. Across the set of train images
$\mathbf{x}$, the learning goal of bi-LSTM is to capture the transition
patterns between image part semantics by increasing the probability of the set
of semantic vectors $\boldsymbol{s_{t}}$ to appear in the timestep $t$, based
on neighboring patch inputs $\boldsymbol{\hat{x}_{t-1}}$ and
$\boldsymbol{\hat{x}_{t+1}}$, and neighboring hidden states
$\boldsymbol{h^{for}_{t-1}}$ and $\boldsymbol{h^{back}_{t+1}}$ that include
information in all inputs $\boldsymbol{\hat{x}_{j},\forall j\neq t}$.
Throughout the dataset, we try to model the conditional probability assuming a
Gaussian distribution on the set of semantic vectors $\mathbf{s_{t}}$ in the
timestep $t$.

$\displaystyle\mathbb{P}(\mathbf{s_{t}}|\mathbf{\hat{x}_{t-1}},\mathbf{\hat{x}_{t+1}},\mathbf{h^{for}_{t-1}},\mathbf{h^{back}_{t+1}})$
(10) $\displaystyle=\mathbb{P}(\mathbf{s_{t}}|\mathbf{\hat{x}_{j},\forall
j\neq t})$
$\displaystyle=\mathcal{N}(\mathbf{s_{t}};\mathbf{p_{t}}(\mathbf{\hat{x}_{j},\forall
j\neq t};\mathbf{W},\mathbf{b}),{\sigma_{t}}^{2})$

In Eq.10 $\mathbf{p_{t}}$ is the model’s prediction of the vector mean of the
distribution of $\mathbf{s_{t}}$. The Gaussian distribution in Eq.10 has a
probability density function (PDF)
$p(s^{(i)}_{t};p^{(i)}_{t},{\sigma_{t}}^{2})=\frac{1}{\sqrt{2\pi{\sigma_{t}}^{2}}}\exp(-\frac{1}{2}\frac{(s^{(i)}_{t}-p^{(i)}_{t})^{2}}{{\sigma_{t}}^{2}})$.
We transform the conditional probability in Eq.10 to log-likelihood by
replacing it with the aforementioned Gaussian PDF and using properties of the
logarithm,

$\displaystyle\sum\limits_{i=1}^{N}{\log{\mathbb{P}(s^{(i)}_{t}|\hat{x}^{(i)}_{j},\forall
j\neq t;\mathbf{W},\mathbf{b})}}$ (11)
$\displaystyle=-N\log{\sigma_{t}}-\frac{N}{2}\log(2\pi)-\sum\limits_{i=1}^{N}{\frac{\lVert
p^{(i)}_{t}-s^{(i)}_{t}\rVert^{2}}{2\sigma^{2}}}$

If we adopt maximum log-likelihood estimation (MLE) on Eq.11, it’s equivalent
to minimizing the MSE loss between the model’s prediction at timestep $t$,
$p_{t}$, and the actual semantics $s_{t}$. We thus have the following
optimization objective for the bi-LSTM model,

$\displaystyle\min_{\mathbf{W},\mathbf{b}}{\sum\limits_{i=1}^{N}\sum\limits_{t=1}^{G}{\lVert
p^{(i)}_{t}-s^{(i)}_{t}\rVert^{2}}}$ (12)
$\displaystyle=\min_{\mathbf{W},\mathbf{b}}{\sum\limits_{i=1}^{N}\bigl{(}\sum\limits_{t=2}^{G}{\lVert
p^{(i,for)}_{t}-s^{(i)}_{t}\rVert^{2}}+\sum\limits_{t=1}^{G-1}{\lVert
p^{(i,back)}_{t}-s^{(i)}_{t}\rVert^{2}}}\bigr{)}$

where $p^{(i,for)}_{t}$ and $p^{(i,back)}_{t}$ are the bi-LSTM predictions in
forward and backward-direction streams.

During test, both correct and corrupted images are used as input. For any
input image patch, pixel-wise semantic segmentation must be produced
faithfully. In Fig.3, we include fine-tuning of the feature extractor
$f_{\theta}$ and classifier $g_{\omega}$ on resized image patch crops
$x_{ig},i=1,...N,t=1,...G$. We use resized patch masks cropped from the output
of stage 1, $m_{itp}$, as supervision. Thus, we have the following pixel-level
cross-entropy loss minimization:

$\displaystyle\min_{\theta,\omega}{\mathcal{L}_{CE}(g_{\omega}(f_{\theta}(x_{it})[p]),\hat{y}_{itp})}\quad\text{where}$
$\displaystyle\mathcal{L}_{CE}=-\log{\frac{\exp(g_{\omega}(z_{itp})[\hat{y}_{itp}])}{\sum\limits_{k=0}^{C-1}{\exp(g_{\omega}(z_{itp})[k])}}}$
(13)

We present 3 test methods for grammar validation in Fig.4. We first prepare
averaged part semantic masks and vectors $m_{avg,t}$ and $s_{avg,t},t=1,...G$:
each pixel is assigned the most popular semantic class from trainset. For each
input image $i$ at patch step $t$, $m^{i}_{t}$ and $s^{i}_{t}$ are extracted
and fed to Bi-LSTM to predict $p^{i,for}_{t}$ and $p^{i,back}_{t}$. The total
prediction error $e_{pred}$ for the patch sequence is computed using methods
listed in Fig.4. It is threshold-ed to determine whether in-distribution
anomalies exist in the input image $x_{i}$.

##  4 Results and Analysis

The entire framework was implemented using the PyTorch framework [41]. The
models were trained and evaluated using 4 NVIDIA GeForce GTX 2080 Ti GPU
cards.

#### CelebA

On the aligned-and-cropped CelebA [37] dataset, 202599 RGB images are resized
to size $256\times 256$. First, we use Feature Pyramid Network (FPN) [35] with
backbone on Resnet-18 [22], pre-trained on ImageNet [11] to extract $128\times
64\times 64$ pixel-level features (downsampled). The FPN is finetuned with
30,000 CelebAHQ [32] face part segmentation masks. We perform mini-batch
K-means clustering every 20 batches before one centroid update. The number of
clusters is set to 20. More deep clustering details can be found in the
appendix. By merging clusters, the resulting part semantic masks contain 7
classes. For image syntax learning, a 1-layer bi-LSTM model is trained. Input
and hidden vectors are 135-d (128-d encoded mask concatted with 7-d
semantics), and the projected outputs are 7-d. Fig.5 shows the correct and
corrupted images during the test, the 5 cropped patches in the traversal
sequence, and their predicted part semantic masks.

#### Baseline: Bi-LSTM+next semantics

The baseline method we used is described in Sec.3. In Fig.6 the left 3 sub-
figures show the forward, backward, bi-directional and total prediction error
(residual) across patch iterations in the part semantic sequence. The
prediction error is the $l2$ distance between the bi-LSTM’s prediction and the
actual part semantics in a particular patch. In Fig.6 the solid lines are mean
values over correct and corrupted samples, at each patch iteration; whereas
the shaded region is covers between 25% and 75% percentiles. In all 3 sub-
figures, we confirm a clear separation between correct (blue) and corrupted
(red) samples. The last sub-figure is the histogram plotting the distribution
of total error (residual) over 5 patches for all test images. The cutoff
threshold is determined from the validation set. For example, in the
demonstrated scenario in Fig.5 (patch size=30, 5-patch shuffling),
threshold=2.0, the binary classification accuracy is
$\frac{TruePositive(TP)+TrueNegative(TN)}{FalseNegative(FN)+TP+FalsePositive(FP)+TN}=91.72\%$.
We further calculate the anomaly detection rate (recall) as
$\frac{TP}{FN+TP}=96.06\%$. We complete Table 1 covering selected corruption
scenarios of shuffling, permuting, blackout, and blurring patches around 5
landmark locations [37]. We tabulate first the detection accuracy and then the
ID anomaly detection rates in parentheses. For puzzle solving tasks, copies of
fake patch permutations along with the correct image are simultaneously fed to
our framework, and we try to pick out the single copy that has the lowest
total prediction error $e_{pred}$. Success rate of solving the puzzle is
shown.

#### Use of averaged semantic masks

On CelebA using ResNet18+FPN segmentation, we compare the effectiveness of all
3 grammar validation methods in Fig.7(a) and Table 1. In the tasks of patch
shuffling, blackening, and blurring, ”Bi-LSTM+avg. semantics” incurs higher
anomaly detection rate of 0-10% over the baseline method. This indicates that
ID anomaly detection works better when comparing LSTM’s prediction to averaged
part semantics instead of GT counterparts. The averaged part semantics
sequence extracted from the trainset (shown in Fig.4) serve as a syntactical
guideline for test patches to follow during each patch traversal. Similarly,
in the task of puzzle solving, directly observing mIoU value between predicted
and trainset-averaged part semantic masks results in a solving rate close to
100%. ID anomalies are easier to discern when the semantics are compared with
a universal semantic representation summarized from correct samples of the
object.

Figure 5: CelebA: sequences of image patch masks Figure 6: CelebA: forward,
backward, and bi-directional LSTM prediction errors, histogram of total error
(residual) over test samples (from left to right)

(a) CelebA, ResNet18+FPN

(b) CelebA, SemanticGAN [33]

Figure 7: CelebA: comparison of detection rate by 3 test methods

Dataset | Seg Model | $GrammarValidationMethod$ |  Shuffle 2 20x20 | Shuffle 2 30x30 |  Black 1 20x20 |  Blur 1 20x20 |  4 Puzzles, 20x20 |  4 Puzzles, 30x30
---|---|---|---|---|---|---|---|---
CelebA | ResNet18+FPN (ours) | $Bi-LSTM+nextsemantics(Baseline)$ |  65.66 (68.67) | 76.22 (79.72) |  70.91 (67.04) |  56.53 (61.19) |  86.74 |  92.51
CelebA | ResNet18+FPN (ours) | $Bi-LSTM+avg.semantics$ |  61.53 (71.72) | 68.89 (80.48) |  65.84 (72.38) |  58.05 (71.50) |  85.62 |  91.15
CelebA | ResNet18+FPN (ours) | $mIoUw./avg.semantics$ |  60.04 (56.16) | 69.59 (59.60) |  60.90 (61.87) |  53.69 (50.18) |  99.25 |  99.58
CelebA | SemanticsGAN [33] (2021) | $Bi-LSTM+nextsemantics(Baseline)$ |  61.35 (69.87) | 70.20 (73.68) |  68.98 (71.04) |  63.93 (65.32) |  82.37 |  88.09
CelebA | SemanticsGAN [33] (2021) | $Bi-LSTM+avg.semantics$ |  58.26 (67.91) | 63.57 (71.49) |  61.28 (65.78) |  59.63 (60.17) |  81.23 |  86.79
CelebA | SemanticsGAN [33] (2021) | $mIoUw./avg.semantics$ |  56.76 (58.34) | 62.75 (64.25) |  62.13 (61.87) |  57.91 (58.72) |  98.60 |  99.12

Table 1: CelebA: benchmarking grammar validation with different segmentation
and test methods

Dataset | Seg Model | $GrammarValidationMethod$ |  Shuffle 4 160x160 | Shuffle 16 80x80 |  Black 4 160x160 |  Blur 4 160x160 |  4 Puzzles, 160x160 |  16 Puzzles, 80x80
---|---|---|---|---|---|---|---|---
SUN-RGBD (13-cls.) | ResNet50+Encoder-Decoder (ours) | $Bi-LSTM+nextsemantics(Baseline)$ |  60.57 (72.04) | 76.57 (73.37) |  66.55 (67.21) |  55.33 (59.07) |  72.89 |  91.17
SUN-RGBD (13-cls.) | ResNet50+Encoder-Decoder (ours) | $Bi-LSTM+avg.semantics$ |  54.97 (65.36) | 61.52 (64.09) |  58.46 (59.65) |  52.83 (55.72) |  62.47 |  75.48
SUN-RGBD (13-cls.) | ResNet50+Encoder-Decoder (ours) | $mIoUw./avg.semantics$ |  57.98 (68.04) | 58.98 (62.24) |  56.32 (57.19) |  53.38 (52.53) |  97.09 |  98.20
SUN-RGBD (13-cls.) | Dformer-S [60] (2023) | $Bi-LSTM+nextsemantics(Baseline)$ |  62.16 (73.47) | 74.23 (72.80) |  68.86 (71.23) |  59.25 (61.22) |  76.61 |  92.84
SUN-RGBD (13-cls.) | Dformer-S [60] (2023) | $Bi-LSTM+avg.semantics$ |  53.77 (67.23) | 62.45 (69.09) |  61.98 (62.45) |  56.22 (58.74) |  61.97 |  74.78
SUN-RGBD (13-cls.) | Dformer-S [60] (2023) | $mIoUw./avg.semantics$ |  53.24 (63.38) | 60.46 (66.21) |  59.79 (61.80) |  55.67 (56.65) |  98.13 |  98.62

Table 2: SUN-RGBD: benchmarking grammar validation with different segmentation
and test methods

Dataset | Seg Model | $SegMethod$ |  SSL? | mIoU
---|---|---|---|---
CelebA | ResNet18+FPN | $DeepCluster\cite[cite]{[\@@bibref{Number}{Caron_2018_ECCV}{}{}]}$ |  | 0.523
CelebA | SemanticGAN | $StyleGAN2\cite[cite]{[\@@bibref{Number}{Karras2019stylegan2}{}{}]}$ |  | 0.781
SUNRGBD | ResNet50 | $Autoencoder\cite[cite]{[\@@bibref{Number}{jiang2018rednet}{}{}]}$ |  | 0.498
SUNRGBD | Dformer-S | $RGBD\cite[cite]{[\@@bibref{Number}{yin2023dformer}{}{}]}$ |  | 0.500

Table 3: Segmentation Models

#### SUN-RGBD

Figure 8: SUN-RGBD (number of classes=13, patch size=160): sequences of image
patch masks Figure 9: SUN-RGBD, patch size=160: forward, backward, and bi-
directional LSTM prediction errors, histogram of total error (residual) over
test samples (from left to right)

On the SUN-RGBD[46] dataset that contains 10,335 room layout RGB and depth
images, we implement a pre-trained Residual Encoder-Decoder Architecture
(RedNet)[27] to retrieve part semantic masks from $640\times 480$ sized
images. On 2 granularity levels, 37-class (appendix) and 13-class [21]
semantic masks are produced. For syntax learning, we use the same bi-LSTM
model as in CelebA. We define zig-zag traversal rules on sequences of patches
of sizes 160 and 80. 13-class patch mask traversal with patch size 160 on
correct and corrupted images is shown in Fig.8. The prediction errors and
test-set histogram are shown in Fig.9. Detection accuracy and anomaly
detection rates are shown in Table 2. On the coarser 13-class segmentation,
the performance is marginally better.

#### Effect of Segmentation Granularity

On both datasets, we compare a few self- and fully-supervised segmentation
models that produce coarser and finer semantic masks (Table 3). From test
results in Table 1, 2, we conclude that finer semantic masks don’t always lead
to higher ID anomaly detection rate, especially on object-centric datasets.
The relationship between semantic granularity and grammar detection
performance is worthy of exploring.

##  5 Conclusion

Motivated by the gap between human and computer vision in recognizing part
corruptions in object-centric and scene-centric images, we propose a 2-stream
deep learning framework that 1) extracts semantically-rich part segmentation
from images through deep clustering and 2) iterates through the part semantic
masks following a traversal rule to learn image syntax with respect to the
object/scene class concept. We evaluate the performance of the framework in
various in-distribution corruption scenarios (Table 1, 2) and achieve 70-90%
part anomaly detection rate on CelebA face images and over 60-80% on SUN-RGBD
room layout images. Through the novel analysis of part-level image grammar,
this work tackles the challenge of in-distribution anomaly detection faced by
machine vision research.

## References

  * Albert et al. [2022] Paul Albert, Eric Arazo, Noel E. O’Connor, and Kevin McGuinness.  Embedding contrastive unsupervised features to cluster in- and out-of-distribution noise in corrupted image datasets.  In _Computer Vision – ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXXI_ , page 402–419, Berlin, Heidelberg, 2022. Springer-Verlag.
  * Asano et al. [2020] Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi.  Self-labelling via simultaneous clustering and representation learning.  In _ICLR_. OpenReview.net, 2020.
  * Bengio [2009] Yoshua Bengio.  Learning deep architectures for ai.  _Found. Trends Mach. Learn._ , 2(1):1–127, 2009.
  * Bengio et al. [2013] Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Representation learning: A review and new perspectives.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 35(8):1798–1828, 2013.
  * Cappa [2012] Stefano F. Cappa.  Imaging semantics and syntax.  _NeuroImage_ , 61(2):427–431, 2012.  NEUROIMAGING: THEN, NOW AND THE FUTURE.
  * Caron et al. [2018] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.  Deep clustering for unsupervised learning of visual features.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018.
  * Caron et al. [2021] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Emerging properties in self-supervised vision transformers, 2021.
  * Chandola et al. [2009] Varun Chandola, Arindam Banerjee, and Vipin Kumar.  Anomaly detection: A survey.  _ACM Comput. Surv._ , 41(3), 2009.
  * Cho et al. [2021] Jang Hyun Cho, Utkarsh Mall, Kavita Bala, and Bharath Hariharan.  Picie: Unsupervised semantic segmentation using invariance and equivariance in clustering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 16794–16804, 2021.
  * Choe et al. [2020] Junsuk Choe, Seong Joon Oh, Seungho Lee, Sanghyuk Chun, Zeynep Akata, and Hyunjung Shim.  Evaluating weakly supervised object localization methods right.  In _CVPR_ , pages 3130–3139. IEEE, 2020.
  * Deng et al. [2009] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , pages 248–255. Ieee, 2009.
  * Dosovitskiy et al. [2020] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _CoRR_ , abs/2010.11929, 2020.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  _ICLR_ , 2021.
  * Ghosal et al. [2022] Soumya Suvra Ghosal, Yifei Ming, and Yixuan Li.  Are vision transformers robust to spurious correlations?, 2022.
  * Grill et al. [2020] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko.  Bootstrap your own latent a new approach to self-supervised learning.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , Red Hook, NY, USA, 2020. Curran Associates Inc.
  * Gu et al. [2022] Jindong Gu, Volker Tresp, and Yao Qin.  Are vision transformers robust to patch perturbations?, 2022.
  * GUNTER et al. [1997] THOMAS C. GUNTER, LAURIE A. STOWE, and GUSBERTUS MULDER.  When syntax meets semantics.  _Psychophysiology_ , 34(6):660–676, 1997.
  * Guo et al. [2017] Xifeng Guo, Xinwang Liu, En Zhu, and Jianping Yin.  Deep clustering with convolutional autoencoders.  In _ICONIP (2)_ , pages 373–382. Springer, 2017.
  * Guo et al. [2023] Yong Guo, David Stutz, and Bernt Schiele.  Improving robustness of vision transformers by reducing sensitivity to patch corruptions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4108–4118, 2023.
  * Hamilton et al. [2022] Mark Hamilton, Zhoutong Zhang, Bharath Hariharan, Noah Snavely, and William T. Freeman.  Unsupervised semantic segmentation by distilling feature correspondences, 2022.
  * Handa et al. [2016] Ankur Handa, Viorica Pătrăucean, Simon Stent, and Roberto Cipolla.  Scenenet: an annotated model generator for indoor scene understanding.  In _ICRA_ , 2016.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, 2016.
  * He et al. [2019] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning, 2019.  cite arxiv:1911.05722Comment: CVPR 2020 camera-ready. Code: https://github.com/facebookresearch/moco.
  * Hua et al. [2018] Yuansheng Hua, Lichao Mou, and Xiao Xiang Zhu.  Lahnet: A convolutional neural network fusing low- and high-level features for aerial scene classification.  In _IGARSS 2018 - 2018 IEEE International Geoscience and Remote Sensing Symposium_ , pages 4728–4731, 2018.
  * Ibrayev et al. [2023] Timur Ibrayev, Manish Nagaraj, Amitangshu Mukherjee, and Kaushik Roy.  Exploring foveation and saccade for improved weakly-supervised localization.  In _NeuRIPS 2023 Workshop on Gaze Meets ML_ , 2023.
  * Ji et al. [2019] Xu Ji, Andrea Vedaldi, and João F. Henriques.  Invariant information clustering for unsupervised image classification and segmentation.  In _ICCV_ , pages 9864–9873. IEEE, 2019.
  * Jiang et al. [2018] Jindong Jiang, Lunan Zheng, Fei Luo, and Zhijun Zhang.  Rednet: Residual encoder-decoder network for indoor rgb-d semantic segmentation.  _arXiv preprint arXiv:1806.01054_ , 2018.
  * Karras et al. [2020] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of StyleGAN.  In _Proc. CVPR_ , 2020.
  * Khosla et al. [2011] Aditya Khosla, Nityananda Jayadevaprakash, Bangpeng Yao, and Li Fei-Fei.  Novel dataset for fine-grained image categorization.  In _First Workshop on Fine-Grained Visual Categorization, IEEE Conference on Computer Vision and Pattern Recognition_ , Colorado Springs, CO, 2011.
  * Kirillov et al. [2019] Alexander Kirillov, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Panoptic feature pyramid networks.  In _CVPR_ , pages 6399–6408. Computer Vision Foundation / IEEE, 2019.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In _Advances in neural information processing systems_ , pages 1097–1105, 2012.
  * Lee et al. [2020] Cheng-Han Lee, Ziwei Liu, Lingyun Wu, and Ping Luo.  Maskgan: Towards diverse and interactive facial image manipulation.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Li et al. [2021] Daiqing Li, Junlin Yang, Karsten Kreis, Antonio Torralba, and Sanja Fidler.  Semantic segmentation with generative models: Semi-supervised learning and strong out-of-domain generalization.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Li et al. [2022] Kunchang Li, Yali Wang, Peng Gao, Guanglu Song, Yu Liu, Hongsheng Li, and Yu Qiao.  Uniformer: Unified transformer for efficient spatiotemporal representation learning.  _CoRR_ , abs/2201.04676, 2022.
  * Lin et al. [2017] Tsung-Yi Lin, Piotr Dollár, Ross B. Girshick, Kaiming He, Bharath Hariharan, and Serge J. Belongie.  Feature pyramid networks for object detection.  In _CVPR_ , pages 936–944. IEEE Computer Society, 2017.
  * Liu et al. [2017] Chenxi Liu, Zhe Lin, Xiaohui Shen, Jimei Yang, Xin Lu, and Alan L. Yuille.  Recurrent multimodal interaction for referring image segmentation.  In _ICCV_ , pages 1280–1289. IEEE Computer Society, 2017.
  * Liu et al. [2015] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In _Proceedings of International Conference on Computer Vision (ICCV)_ , 2015.
  * Liu et al. [2021] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 9992–10002, 2021.
  * Mnih et al. [2014] Volodymyr Mnih, Nicolas Heess, Alex Graves, and Koray Kavukcuoglu.  Recurrent models of visual attention.  In _NIPS_ , pages 2204–2212, 2014.
  * Ortego et al. [2021] Diego Ortego, Eric Arazo, Paul Albert, Noel E. O’Connor, and Kevin McGuinness.  Towards robust learning with different label noise distributions.  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , pages 7020–7027, 2021.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.
  * Saha et al. [2022] Sudipan Saha, Muhammad Shahzad, Lichao Mou, Qian Song, and Xiao Xiang Zhu.  Unsupervised single-scene semantic segmentation for earth observation.  _IEEE Transactions on Geoscience and Remote Sensing_ , 60:1–11, 2022.
  * Schettini et al. [2009] Raimondo Schettini, Gianluigi Ciocca, and Isabella Gagliardi.  _Feature Extraction for Content-Based Image Retrieval_ , pages 1115–1119.  Springer US, Boston, MA, 2009.
  * Shen et al. [2019] Zong-Ying Shen, Shiang-Yu Han, Li-Chen Fu, Pei-Yung Hsiao, Yo-Chung Lau, and Sheng-Jen Chang.  Deep convolution neural network with scene-centric and object-centric information for object detection.  _Image and Vision Computing_ , 85:14–25, 2019.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In _ICLR_ , 2015.
  * Song et al. [2015] Shuran Song, Samuel P. Lichtenberg, and Jianxiong Xiao.  Sun rgb-d: A rgb-d scene understanding benchmark suite.  In _CVPR_ , pages 567–576. IEEE Computer Society, 2015.
  * Steiner et al. [2022] Andreas Peter Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer.  How to train your vit? data, augmentation, and regularization in vision transformers.  _Transactions on Machine Learning Research_ , 2022.
  * Tian et al. [2022] Rui Tian, Zuxuan Wu, Qi Dai, Han Hu, and Yu-Gang Jiang.  Deeper insights into the robustness of vits towards common corruptions, 2022.
  * Van Gansbeke et al. [2021] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, and Luc Van Gool.  Unsupervised semantic segmentation by contrasting object mask proposals.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 10052–10062, 2021.
  * von Stechow [2019] Arnim von Stechow.  Syntax and semantics: an overview.  _Semantics-Interfaces_ , page 169, 2019.
  * Wang et al. [2022] Guangrun Wang, Yansong Tang, Liang Lin, and Philip H.S. Torr.  Semantic-aware auto-encoders for self-supervised representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 9664–9675, 2022.
  * Wang et al. [2013] Hua Wang, Feiping Nie, and Heng Huang.  Multi-view clustering and feature learning via structured sparsity.  In _Proceedings of the 30th International Conference on Machine Learning_ , pages 352–360, Atlanta, Georgia, USA, 2013. PMLR.
  * Wu et al. [2020] Mike Wu, Milan Mosse, Chengxu Zhuang, Daniel Yamins, and Noah D. Goodman.  Conditional negative sampling for contrastive learning of visual representations.  _CoRR_ , abs/2010.02037, 2020.
  * Wu et al. [2021] Zhi-Fan Wu, Tong Wei, Jianwen Jiang, Chaojie Mao, Mingqian Tang, and Yu-Feng Li.  Ngc: A unified framework for learning with open-world noisy data.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 62–71, 2021.
  * Xia et al. [2022] Xuan Xia, Xizhou Pan, Nan Li, Xing He, Lin Ma, Xiaoguang Zhang, and Ning Ding.  Gan-based anomaly detection: A review.  _Neurocomput._ , 493(C):497–535, 2022.
  * Xie et al. [2016] Junyuan Xie, Ross B. Girshick, and Ali Farhadi.  Unsupervised deep embedding for clustering analysis.  In _ICML_ , pages 478–487. JMLR.org, 2016.
  * Xu et al. [2015] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  In _Proceedings of the 32nd International Conference on Machine Learning_ , pages 2048–2057, Lille, France, 2015. PMLR.
  * Xu et al. [2022] Minghao Xu, Yuanfan Guo, Xuanyu Zhu, Jiawen Li, Zhenbang Sun, Jian Tang, Yi Xu, and Bingbing Ni.  Hirl: A general framework for hierarchical image representation learning, 2022.
  * Yang et al. [2016] Jianwei Yang, Devi Parikh, and Dhruv Batra.  Joint unsupervised learning of deep representations and image clusters.  In _CVPR_ , pages 5147–5156. IEEE Computer Society, 2016.
  * Yin et al. [2023] Bowen Yin, Xuying Zhang, Zhongyu Li, Li Liu, Ming-Ming Cheng, and Qibin Hou.  Dformer: Rethinking rgbd representation learning for semantic segmentation.  _arXiv preprint arXiv:2309.09668_ , 2023.
  * Yun et al. [2022] Sukmin Yun, Hankook Lee, Jaehyung Kim, and Jinwoo Shin.  Patch-level representation learning for self-supervised vision transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 8354–8363, 2022.
  * Zhan et al. [2020] Xiaohang Zhan, Jiahao Xie, Ziwei Liu, Yew-Soon Ong, and Chen Change Loy.  Online deep clustering for unsupervised representation learning.  In _CVPR_ , pages 6687–6696. IEEE, 2020.
  * Zhang et al. [2021] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Commun. ACM_ , 64(3):107–115, 2021.
  * Zhang [2019] Richard Zhang.  Making convolutional networks shift-invariant again.  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 7324–7334. PMLR, 2019.
  * Zhou et al. [2022] Daquan Zhou, Zhiding Yu, Enze Xie, Chaowei Xiao, Animashree Anandkumar, Jiashi Feng, and Jose M. Alvarez.  Understanding the robustness in vision transformers.  In _Proceedings of the 39th International Conference on Machine Learning_ , pages 27378–27394. PMLR, 2022.

Supplementary Material

##  6 Experiment details

###  6.1 DNN architectures

#### On CelebA

Figure 10: DNN architectures: Feature Pyramid Network (FPN) backbone on
ResNet-18 Figure 11: DNN architectures: bi-directional Long Short-Term Memory
(bi-LSTM)

In Fig.10 we illustrate the feature pyramid network (FPN) [35] that we used
for part semantics clustering and segmentation of CelebA [37] images. The
Panoptic FPN [30] we used is backboned on ResNet-18 [22]. It encodes multi-
scale feature representation in a top-down fashion. Then from the bottom-up,
we use $1\times 1$ Convolutional (Conv) layers to project pixel-wise features
to 128-dimensional. The projected features of different spatial sizes are
bilinearly-upsampled to $1/4$ height and width of the original image and then
element-wise summed. The pixel-wise representations thus have shape $128\times
h\times w$ ($128\times 64\times 64$ for input images of shape $3\times
256\times 256$). The extracted pixel-wise features are used for the
DeepClustering method [9]. We record the resulting clustering centroids as a
final 1x1 Conv layer to project these features to the dimension of the number
of semantic classes, $7$ in the case of face images.

In Fig.11 is the structure of the bi-directional Long Short-Term Memory (bi-
LSTM). We use it for image syntax learning. For each patch in the traversal
sequence of length $5$, the predicted mask is first flattened before being fed
to a fully-connected (FC) encoder layer. The encoder projects the semantic
mask to a 128-d vector, which is concatenated with the 7-d semantics vector.
The resulting 135-d vector contains both spatial and semantic information
about each patch’s composition, and it is used as the input to 2 LSTM layers
in forward and backward directions. After projection layers, the outputs
include a 7-d forward prediction of the next semantics in the sequence and a
7-d backward prediction of the previous semantics. For the first and last
patches, only forward and backward predictions are made, respectively.

#### On SUN-RGBD

We use a Residual Encoder-Decoder Network (RedNet) [27] with backbone on
ResNet-50 for segmentation on SUN-RGBD [46] images. It is a state-of-the-art
room scene parsing architecture that achieved $47.8\%$ mIoU accuracy on
37-class SUN-RGBD. Similar to FPN, the RedNet extracts multi-scale feature
maps from the input image with its encoder residual layers. However, each
projected feature map is skip-connected with the output of upsampling residual
units in a decoder [27] before being summed with the next level in the feature
pyramid. An additional depth branch is fused with the RGB branch. We performed
13-class (merged from 37-class) semantic segmentation with a trained RedNet.
The RedNet produces the same-resolution ($640\times 480$) segmentation from
the original image. Patch semantic masks of sizes $160\times 160$ and
$80\times 80$ are cropped and used for preparing patch semantic vectors. At
each stage of patch sequences, patch semantic masks are flattened and
projected to 128-d vectors before concatenating with a 13-d semantics vector.
The resulting 141-d vectors are passed to LSTM blocks for forward and backward
predictions (both 13-d).

###  6.2 Datasets

Figure 12: Segmentation Classes. Left: CelebA; Right: SUN-RGBD

CelebA [37] contains 202,599 celebrity images. We used the aligned-and-cropped
version where faces are localized. Images are divided into a train set of size
162,770, a validation set of size 19,867, and a test set of size 19,962.
First, the FPN network is finetuned on 30,000 CelebAHQ [32] images selected
from CelebA. CelebAHQ images and pixel-wise labels are center-cropped
(size=$160$) and resized to $256\times 256$. After fine-tuning, DeepCluster
PiCIE [9] training is accomplished on train set images resized to $256\times
256$ and validated on the validation set. $64\times 64$ patches are cropped
from segmentation and are bi-linearly-interpolated to $256\times 256$. The
part mask detector again produces $64\times 64$ patch semantic masks. The $7$
semantic classes and their names are illustrated in Fig.12 on the left. During
the test, we add corruption to half of the test images around $5$ facial part
landmark locations (left eye, right eye, nose, left mouth, right mouth).

SUN-RGBD [46] contains 10335 RGB images and corresponding depth images, split
into a train set of size 4785, a validation set of size 1000, and a test set
of size 5050. RGB and depth images are resized to $640\times 480$ and
normalized. The pre-trained RedNet [27] also produces $640\times 480$ semantic
masks. From each segmentation, $160\times 160$ and $80\times 80$ patch
semantic masks are cropped. The segmentation contains 37 semantic classes, but
we merge them into 13 classes with the same mapping in [21]. The 13 semantic
classes are shown in Fig.12 on the right. During the test, we add corruptions
to image patches.

###  6.3 Train and test configurations

#### On CelebA

During fine-tuning of the FPN network pre-trained on ImageNet [11], CelebAHQ
[32] masks are pre-processed to contain only 7 coarse semantic classes.
$batch\\_size\\_train=128$. $Adam$ optimizer is used with
$start\\_lr=1e^{-4}$. We trained for $num\\_epochs=20$ with a constant
learning rate. The fine-tuned model is used for DeepCluster PiCIE [9]
training. $batch\\_size\\_train=256$. We adopted over-clustering and set the
number of clusters, $K\\_train=20$, as that results in better clusters
compared to $KM\\_num=10$ and $KM\\_num=30$. Mini-batch K-means clustering is
performed. $KM\\_init=20$ is the number of batches we collect before the first
K-means clustering. $KM\\_num=20$ is the interval of batches between
consecutive clustering. $KM\\_iter=100$ is the number of K-means clustering
iterations before convergence. After each clustering, the total PiCIE loss is
back-propagated to optimize FPN model parameters. We use $Adam$ optimizer with
$start\\_lr=1e^{-4}$. Although PiCIE loss is computing-intensive, PiCIE
training converges fast in $num\\_epochs=10$ with a constant learning rate. To
get semantic segmentation masks, we initiate a $1\times 1$ Conv layer whose
weights are loaded as the trained centroid matrix, and append it to the
trained FPN network. $batch\\_size\\_test=256$. We post-process pixel-wise
class assignments to merge semantically-similar clusters and obtain 7-class
face part masks. Further, we tune the FPN network on $64\times 64$ patches,
using crops on the saved face masks as supervision. The part mask detector is
trained with $batch\\_size\\_train=128$, $start\\_lr=1e^{-4}$, and
$num\\_epochs=20$. We chose the $num\\_epochs=20$ model over the
$num\\_epochs=40$ model because the smooth boundaries in the semantic masks
help with syntax learning.

After we obtain 7-class patch semantic masks for each patch in the traversal
sequence, we feed the concatenation of encoded mask (128-d) and semantics
vector (7-d) into a bi-LSTM model. $input\\_size=135$, $hidden\\_size=135$,
$num\\_layers=1$, $bidirectional=True$, $proj\\_size=7$. We use $Adam$
optimizer with $start\\_lr=1e^{-4}$. $num\\_epochs=40$ and the learning rate
changes to $1e^{-5}$ after $20$ epochs. During the test, we apply the same
settings to the bi-LSTM model and use a threshold on total prediction error to
distinguish part semantic anomalies in patch sequences.

#### On SUN-RGBD

On SUN-RGBD, the pre-trained RedNet network [27] produces 37 segmentation
classes. We merge these classes into 13-class stuff and things as shown in
Fig.12. When the patches are shuffled, the pre-trained network is able to
produce precise patch semantics, so that a part mask detector is not needed as
in CelebA. We start with image syntax training with two configurations,
$patch\\_size=160$ and $patch\\_size=80$. In both configurations, the patch
semantic masks are encoded as 128-d vectors, while the semantics vector is
13-d. Thus, the bi-LSTM model has configurations $input\\_size=141$,
$hidden\\_size=141$, $num\\_layers=1$, $bidirectional=True$, $proj\\_size=13$.
We use $Adam$ optimizer with $start\\_lr=1e^{-4}$. $num\\_epochs=40$. A multi-
step learning rate scheduler is used with $gamma=0.8$ and
$milestones=[5,10,15,20,25,30,35]$. Same bi-LSTM model is used during test.

##  7 Quantitative results

In Table 4 and 5 we add more results for the task of in-distribution anomaly
detection, on CelebA (7 classes) and SUN-RGBD (13 classes), respectively.

#### CelebA

The segmentation model is ResNet18+FPN. The input images have sizes 256
$\times$ 256\. All results are reported using the baseline test method ”Bi-
LSTM+next semantics”. From Table 4, we observe that the grammar detection
framework exhibits reliable performance when the size of the corrupted patch
exceeds 30 $\times$ 30: ¿80% on patch shuffling tasks, 92.51% on puzzle
solving with 4 permutations, ¿80% on patch blackout tasks, and ¿60% on patch
blurring tasks.

#### SUN-RGBD

The segmentation model is ResNet50 encoder-decoder (RedNet). The input images
have sizes 640 $\times$ 480\. All results are reported using the baseline test
method ”Bi-LSTM+next semantics”. Two segmentation granularities are used,
13-class coarse segmentation merged from 37-classes, and the original 37-class
fine segmentation. From Table 5, we observe corruption detection performance
for the two levels of granularity. In tasks such as patch shuffling, puzzle
solving, and patch blurring, using coarser 13-class semantic masks boosts
syntax sequence reasoning and improves grammar validation performance. This is
due to the better sequential reasoning capability that the Bi-LSTM learns from
coarse patch masks. Meanwhile, in the task of patch blackout, using finer
37-class semantic masks has an edge. The blackened patch semantics is easier
to discern when the segmentation is finer, leading to a longer syntax sequence
and higher variations in the predicted semantic values.

Corruption: landmark shuffling |  |  |  |
---|---|---|---|---
Test Accuracy (%) | Patch size: 10 | Patch size: 20 | Patch size: 30 | Patch size: 40 | Patch size:50
shuffle 2 patches | 53.86 (75.58) | 65.66 (68.67) | 76.22 (79.72) | 83.89 (86.33) | 88.22 (93.04)
shuffle 3 patches | 55.67 (75.16) | 73.16 (78.97) | 85.68 (91.08) | 90.96 (95.22) | 93.05 (97.42)
shuffle 4 patches | 57.33 (74.73) | 78.40 (82.29) | 89.79 (94.57) | 93.00 (97.34) | 94.34 (98.07)
shuffle 5 patches | 59.13 (70.93) | 82.88 (88.15) | 91.72 (96.06) | 93.93 (97.25) | 94.69 (97.39)
Corruption: landmark puzzle |  |  |  |
Test Accuracy (%) | Patch size: 10 | Patch size: 20 | Patch size: 30 | Patch size: 40 | Patch size:50
1 real, 3 fake | 57.84 | 86.74 | 92.51 | 93.97 | 94.81
1 real, 119 fake (all perm) | 8.39 | 37.43 | 66.15 | 80.37 | 87.23
Corruption: landmark blackout |  |  |  |
Test Accuracy (%) | Patch size: 10 | Patch size: 20 | Patch size: 30 | Patch size: 40 | Patch size:50
blacken 1 patch | 54.73 (55.36) | 70.91 (67.04) | 81.25 (81.08) | 87.37 (88.04) | 91.25 (95.12)
blacken 2 patches | 60.43 (63.78) | 83.83 (85.22) | 91.77 (93.43) | 95.41 (97.41) | 95.78 (97.58)
blacken 3 patches | 65.79 (68.94) | 90.60 (93.83) | 96.48 (98.49) | 97.83 (98.57) | 98.50 (99.14)
blacken 4 patches | 71.85 (74.34) | 94.56 (97.14) | 98.08 (98.88) | 98.86 (99.36) | 99.05 (99.49)
blacken 5 patches | 77.32 (85.28) | 97.22 (98.20) | 98.87 (99.48) | 98.95 (99.29) | 99.13 (99.64)
Corruption: landmark blurring |  |  |  |
Test Accuracy (%) | Patch size: 10 | Patch size: 20 | Patch size: 30 | Patch size: 40 | Patch size:50
blur 1 patch | 52.31 (80.28) | 56.84 (56.31) | 62.12 (64.41) | 66.83 (66.33) | 72.64 (77.95)
blur 2 patches | 54.00 (71.81) | 63.21 (63.78) | 72.47 (77.61) | 78.53 (80.87) | 83.09 (89.99)
blur 3 patches | 55.88 (64.42) | 69.40 (71.47) | 81.03 (84.44) | 86.92 (90.42) | 89.66 (92.61)
blur 4 patches | 57.44 (78.69) | 74.61 (81.90) | 87.89 (92.37) | 91.32 (95.27) | 92.85 (97.04)
blur 5 patches | 59.65 (65.18) | 78.75 (84.54) | 91.34 (95.98) | 93.02 (97.36) | 94.03 (97.46)

Table 4: Grammar validation accuracy on CelebA (Image size: 256x256)

(a) 13 segmentation classes

Corruption: patch shuffling
---
Test Accuracy (%) | Patch size: 160 | Test Accuracy (%) | Patch size: 80
shuffle 4 patches | 60.57 (72.04) | shuffle 16 patches | 76.57 (73.37)
shuffle 8 patches | 69.31 (72.59) | shuffle 32 patches | 86.63 (82.38)
shuffle 12 patches |  73.47 (77.50) | shuffle 48 patches |  87.09 (82.97)
Corruption: patch puzzle
Test Accuracy (%) | Patch size: 160 |  | Patch Size: 80
1 real, 3 fake | 72.89 |  | 91.17
1 real, 99 fake | 28.95 |  | 69.67
Corruption: patch blackout
Test Accuracy (%) | Patch size: 160 | Test Accuracy (%) | Patch size: 80
blacken 4 patches | 66.55 (67.21) | blacken 16 patches | 67.43 (65.53)
blacken 8 patches | 66.59 (67.17) | blacken 32 patches | 75.68 (70.22)
blacken 12 patches | 66.75 (67.49) | blacken 48 patches | 73.66 (74.81)
Corruption: patch blurring
Test Accuracy (%) | Patch size: 160 | Test Accuracy (%) | Patch size: 80
blur 4 patches | 55.33 (59.07) | blur 16 patches | 54.42 (63.37)
blur 6 patches | 56.57 (70.22) | blur 24 patches | 55.42 (65.58)

(b) 37 segmentation classes

Corruption: patch shuffling
---
Test Accuracy (%) | Patch size: 160 | Test Accuracy (%) | Patch size: 80
shuffle 4 patches | 62.32 (74.57) | shuffle 16 patches | 67.74 (74.77)
shuffle 8 patches | 71.53 (76.99) | shuffle 32 patches | 78.04 (76.20)
shuffle 12 patches |  74.93 (77.43) | shuffle 48 patches |  79.84 (78.69)
Corruption: patch puzzle
Test Accuracy (%) | Patch size: 160 |  | Patch Size: 80
1 real, 3 fake | 76.10 |  | 81.23
1 real, 99 fake | 33.85 |  | 55.99
Corruption: patch blackout
Test Accuracy (%) | Patch size: 160 | Test Accuracy (%) | Patch size: 80
blacken 4 patches | 61.58 (71.37) | blacken 16 patches | 61.41 (71.25)
blacken 8 patches | 67.53 (72.20) | blacken 32 patches | 69.07 (71.80)
blacken 12 patches | 66.18 (76.00) | blacken 48 patches | 64.59 (72.24)
Corruption: patch blurring
Test Accuracy (%) | Patch size: 160 | Test Accuracy (%) | Patch size: 80
blur 4 patches | 54.00 (52.81) | blur 16 patches | 50.91 (54.10)
blur 6 patches | 54.06 (58.81) | blur 24 patches | 52.88 (57.15)

Table 5: Grammar validation accuracy on SUN-RGBD (Image size: 640x480)

##  8 Qualitative results

###  8.1 Semantic clustering and segmentation

In the below Fig.13 and Fig.14 we show selected part-level semantic
segmentations on CelebA face images and SUN-RGBD room scene images,
respectively. All samples are in the trainsets. The segmentations displayed by
generated by trained ResNet18 and trained ResNet50 encoder-decoder,
respectively.

Figure 13: 7-class semantic segmentation on CelebA Figure 14: 13-class
semantic segmentation on SUN-RGBD

###  8.2 Syntactic sequences of part semantics

In Fig.15 we show the pixel-level part semantic masks and explicit semantics
in each mask, averaged over correct samples in the entire CelebA test set.
During training, we optimized MSE loss between bi-LSTM predictions and the
actual semantics inside each patch, in order to model the mean of the
semantics distribution in each patch iteration, as discussed in the method
Section. Hence, here we show the average traversal patterns learned. It’s
evidently shown that face-part semantic transitions and the face syntax in the
CelebA dataset are captured by the trained bi-LSTM model. For example, in the
first 2 patch iterations, the ”forehead” semantics is dominant. In the third
and fourth patches, ”mouth” semantics is dominant. While for the last patch,
”eyes” semantics is dominant. These part semantics along with transitions
among those semantics is key to identifying part anomalies.

Figure 15: Left: Averaged patch mask transitions over CelebA test set; Right:
Averaged patch semantics over CelebA test set

In Fig.16 we show the pixel-level part semantic masks and explicit semantics
in each mask, averaged over the entire SUN-RGBD test set. Here, each of the 13
semantic classes is either a stuff (e.g., ceiling, floor, wall, etc.) or a
thing (e.g., books, char, table, etc.) Within the traversal sequence, the
first few patches at the top of the image have ”wall” as dominant semantics,
while the last few patches at the bottom have ”floor” as dominant. Semantic
classes belonging to the thing category reside in the middle patches, such as
”chair” and ”table”. This reveals that our proposed framework is capable of
learning general stuff and thing layouts even from a complicated dataset SUN-
RGBD, that contains a wide variety of different room scenes.

Figure 16: Left: Averaged patch mask transitions over SUN-RGBD test set;
Right: Averaged patch semantics over SUN-RGBD test set

###  8.3 Corruption scenarios

In Fig.17 we made visualizations for all corruption scenarios on CelebA and
SUN-RGBD test images.

Figure 17: Demo of all types of corruptions

##  9 Image corruption algorithms

In Fig.18 and Fig.19 we display the algorithms we used to generate corruptions
to test images.

Algorithm 1 Patch shuffling

1:def shuffle(tensors, num_patch, ps):

2:$\textit{result}\leftarrow\text{[]}$

3:for $it,X$ in enumerate(tensors) do

4: $\textit{patches}\leftarrow\text{nnF.unfold({X}, {ps}, {ps}, 0)}$

5: $\textit{p}\leftarrow\text{{patches}.shape[-1]}$

6: if $\textit{it}==0$ then

7: $\textit{indices}\leftarrow$

8: sample(range(p), num_patch)

9: $\textit{orig}\leftarrow\text{tensor(range(p))}$

10: $\textit{perm}\leftarrow\text{tensor(range(p))}$

11: for $j$ in range(num_patch) do

12: $\textit{perm}[indices[j]]=$

13: $\textit{orig}[indices[(j+1)\%num\\_patch]]$

14: end for

15: end if

16: $\textit{patches}\leftarrow\text{concat({patch}[:, perm]}$

17: for patch in patches)

18: $\textit{X}\leftarrow\text{nnF.fold(patches, {X}.shape[-2:],}$

19: ps, ps, 0)

20: result.append(X)

21:end for

22:Return result

Algorithm 2 Patch blackout

1:def shuffle(tensors, num_patch, ps):

2:$\textit{result}\leftarrow\text{[]}$

3:for $it,X$ in enumerate(tensors) do

4: $\textit{patches}\leftarrow\text{nnF.unfold({X}, {ps}, {ps}, 0)}$

5: $\textit{p}\leftarrow\text{{patches}.shape[-1]}$

6: if $\textit{it}==0$ then

7: $\textit{indices}\leftarrow$

8: sample(range(p), num_patch)

9: end if

10: for $idx,X$ in enumerate(patches) do

11: $\textit{patches}[idx][:,\textit{indices}]\leftarrow 0$

12: end for

13: $\textit{X}\leftarrow\text{nnF.fold(patches, {X}.shape[-2:],}$

14: ps, ps, 0)

15: result.append(X)

16:end for

17:Return result

Figure 18: Patch shuffling and patch blackout algorithms

Algorithm 3 Patch blurring

1:def shuffle(tensors, num_patch, ps,

2: kernel_size, sigma):

3:$\textit{result}\leftarrow\text{[]}$

4:blurrer = T.GaussianBlur(kernel_size, sigma)

5:for $it,X$ in enumerate(tensors) do

6: $\textit{patches}\leftarrow\text{nnF.unfold({X}, {ps}, {ps}, 0)}$

7: $\textit{p}\leftarrow\text{{patches}.shape[-1]}$

8: if $\textit{it}==0$ then

9: $\textit{indices}\leftarrow$

10: sample(range(p), num_patch)

11: end if

12: for $idx,X$ in enumerate(patches) do

13: $\textit{patches}[idx][:,\textit{indices}]\leftarrow$

14: blurrer(reshape(patches[idx][:, indices))

15: end for

16: $\textit{X}\leftarrow\text{nnF.fold(patches, {X}.shape[-2:],}$

17: ps, ps, 0)

18: result.append(X)

19:end for

20:Return result

Algorithm 4 Create puzzles

1:def shuffle(tensors, num_perm, ps):

2:$\textit{result}\leftarrow\text{[]}$

3:for $it,X$ in enumerate(tensors) do

4: $\textit{patches}\leftarrow\text{nnF.unfold({X}, {ps}, {ps}, 0)}$

5: $\textit{p}\leftarrow\text{{patches}.shape[-1]}$

6: if $\textit{it}==0$ then

7: $\textit{perms}\leftarrow\text{[]}$

8: for $perm\\_id$ in range(num_perm) do

9: perms.append(randperm(p))

10: end for

11: end if

12: $\textit{res}\leftarrow\textit{X}\text{.clone()}$

13: for $perm$ in perms do

14: $\textit{new\\_patches}\leftarrow$

15: concat(patch[:, perm]

16: for patch in patches)

17: $\textit{new\\_X}\leftarrow$

18: nnF.fold(patches, X.shape[-2:],

19: ps, ps, 0)

20: $\textit{res}\leftarrow\text{concat({res}, {new\\_X})}$

21: end for

22: result.append(res)

23:end for

24:Return result

Figure 19: Patch blurring and creating puzzle algorithms

##  10 Additional results

###  10.1 SUN-RGBD, patch size=80

Fig.20, Fig.21, and Fig.22 are a continuation to Fig.8 that shows the
demonstrations of correct and corrupted image patch traversals and the
prediction errors across patch sequences, for $patch\\_size=80$ traversals on
$640\times 480$ SUN-RGBD images. In Fig.22, the red and blue solid lines are
mean values over all correct and corrupted samples, at each patch iteration.
The dashed lines are 25% and 75% percentiles. It is noted among each row of
patches, the prediction error gradually decreases, before rising again at the
corner patch in the zig-zagging traversal. Thus, each row of patches can be
deemed as a sub-sequence where sub-image level syntax can be learned.

Figure 20: SUN-RGBD, patch size=80: sequence of correct image patch masks
Figure 21: SUN-RGBD, patch size=80: sequences of corrupted image patch masks
Figure 22: SUN-RGBD, patch size=80: forward, backward, and bi-directional LSTM
prediction errors, histogram of total error (residual) over test samples (from
left to right)

##  11 Broader impacts

This work focuses on understanding part-level image grammar and using that
knowledge to detect in-distribution part anomalies inside images. With the
development of a computer vision system that is more intelligent and less
error-prone, people, particularly those with mental or physical disabilities
and the elderly, will be able to perceive the surrounding scene and objects
with greater accuracy and with a lesser degree of effort. For instance, cabin
vision systems can recognize dangerous behaviors by the drivers; home robots
equipped with such vision systems will recognize home objects and perform
housework more effectively, etc. In addition, the ability to detect part
anomalies provides an additional level of defense against malicious actors
trying to deceive modern-day machine vision algorithms. With a more powerful
object perception, computer vision is more versatile in serving humans and
adds convenience to everyday life.

However, we must be wary of the potential negative social consequences caused
by the sophistication of machine vision. One example is where mass data sets
for machine vision training can lead to information leaks and privacy issues.
It would be difficult to verify the source of the information. In addition,
people may improperly use high-performance machine systems for malicious
purposes, such as mass surveillance and cyber warfare. Finally, it is possible
that these machine vision systems are too trusted and put to applications too
soon without enough trial-and-error. In the event that these systems fail in
the real world, such acts could result in serious accidents.