# A multimodal deep learning framework for scalable content based visual media
retrieval

Ambareesh Ravi  Dept. of Electrical and Computer Engineering
University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>Amith Nandakumar  Dept. of Electrical and
Computer Engineering
University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>
###### Abstract

We propose a novel, efficient, modular and scalable framework for content
based visual media retrieval systems by leveraging the power of Deep Learning
which is flexible to work both for images and videos conjointly and we also
introduce an efficient comparison and filtering metric for retrieval. We put
forward our findings from critical performance tests comparing our method to
the predominant conventional approach to demonstrate the feasibility and
efficiency of the proposed solution with best practices, possible improvements
that may further augment ability of retrieval architectures.

###### Index Terms:

Convolutional Neural network (2D CNN), 3D Convolutions (3D CNN), Long Short
Term Memory networks (LSTMs), Content Based Image Retrieval (CBIR), Content
Based Video Retrieval (CBVR).

##  I Introduction

Recent developments in the field of digital media have led to an abundance of
visual data around us. Organizing, managing and gaining insights out of the
visual data has become more difficult owing to the sheer volume of the data.
Hence, tasks like visual search, reverse search, retrieval, captioning,
indexing have become more crucial over the past years. The need for an
automated and efficient approach to index, categorize and organize visual
media with little to no human intervention is growing in multiple fields like
medicine, satellite imagery, remote sensing, forensics, historical search,
media recommendations, Video on Demand, online shopping, security and digital
libraries etc.

The advent and recent popularity of content based retrieval techniques are due
to the short-comings of text-query based retrieval methods. Query based
techniques need comprehensive metadata tagging by humans involving a lot of
effort in terms of annotations and tagging. They also function satisfactorily
only when the input query matches the tags available in the data repository.
Whereas in content based methods, the information from the input image is
directly correlated with that of the ones in the database.

Deep Learning has evolved over the years and has shown compelling performance
at complex vision and natural language tasks than the conventional approaches
[36] with the potential to close the semantic gap between the low-level
features such as color, shape, texture, edges, orientation etc., that is
apparent to the learning algorithm and the high level context as perceived by
humans through abstraction. In tasks like retrieval, the embedded features of
the data are often compared and so the key emphasis is often on the ability of
the model to produce a feature representation that can relate the similarities
and discriminate the differences in the content.

The advances in the space of content-based video retrieval tasks has been less
due to computational limitations, efficacy of algorithms and poor scalability
due to the amount of data to be used, as videos contain temporal information
in addition to spatial information. These limitations are taken into
consideration and are mitigated considerably in our proposed framework which
is scalable, flexible and efficient by nature. Accuracy and speed of the
application is a critical element that draws the attention of the user and
would be overlooked if one of the two is missing.

We propose a light, cogent and end-to-end content based retrieval architecture
that works conjointly for both images and videos that uses Convolutional
Neural Networks (CNNs) for spatial learning and Recurrent Neural Networks
(RNNs) for learning the temporal relation that associates a sequence of frames
into a video. We also provide substantiating evidence for the effectiveness of
the proposed architecture in comparison with the traditional and prevalent
approaches that are generally used for retrieval tasks. We also discuss the
results of important experiments and the best practices that can further
improve the performance, since the main focus of this work is to improve
scalability of retrieval tasks. We concentrate primarily on the ability of our
architecture to retrieve video as image retrieval is addressed adequately in
other works.

##  II Related works

In this section, we discuss a few important literature in the field of media
retrieval. The three main areas of development are feature representation,
ranking of retrieved results and faster comparison techniques.

Ladahke et al. [37] provide a review of different retrieval tasks with their
applications and early approaches which led to the development in the field as
of now. The authors also illustrate the basic technique for CBIR tasks. In
[4], Csurka et al., compare classifiers for visual categorization which is one
of the field’s earliest works after which improved methods emerged which led
to the current popularity. After the advent of deep learning and the
performance gains that come with it, several methods adopting deep learning
techniques emerged .

Both traditional methods and deep learning methods have their advantages and
disadvantages. We focus on the facts as to why deep learning (DL) is the
better option for content based retrieval tasks. DL is better at learning both
local and global features where as traditional methods need separate modules
to learn/identify local features such as shapes, texture, colour, edges,
objects, orientation etc and they perform poorly in learning global features
by association. DL models can be designed to be scale, spatial and colour
invariant and can perform well in such cases subject to training on diverse
data. Traditional image processing modules need separate pre-processing
pertaining to their design and the features from different modules of
traditional methods have to be aggregated to a fixed length and it is very
difficult to maintain the correlation where as deep learning models readily
output feature representations of fixed dimension.

In spite of several attractive features, deep learning models suffer from two
major disadvantages – computational requirement and huge data necessity. But
fortunately for retrieval tasks, the data is available in abundance and given
that most of these tasks are hosted in cloud platforms which have high
computational capabilities, deep learning is the most viable option given its
performance.

In his thesis [36], the author A.V. Singh elaborates on the differences
between traditional and deep learning based approaches and proves that the
latter perform well over the traditional ones with their ability to bridge the
semantic gap considerably. [42] provides a comprehensive study on deep
learning for image retrieval tasks by putting forward some compelling
arguments on the sub-par performance of traditional methods over learning
based methods. Traditional methods have several shortcomings in terms of
complexity, inefficient operation and inability to represent a global generic
solution etc which makes deep learning a favorable solution as they can be
flexible, end-to-end and generalize over a wide range of data for various
applications. In [8], A. Gordo et al., propose an approach to learn global
representation for instance level retrieval using deep learning. [28],[1],[9],
[2] provide the best practices for content based retrieval tasks which are
very helpful and insightful. Other favorable properties of deep learning are
discussed in the next sections.

Since, the need for deep learning techniques was established in the previous
sections, the popular works in the field are discussed in this section. There
are several works on image retrieval and a very few notable ones on video
retrieval. The main factor that decides the performance of any content based
retrieval method is the feature representation or description of the input.
There are many other works reflecting on the nature of feature representations
and [13] presents a detailed survey on the same.

The preliminary works in the field were based on visual cues such as shape,
color, texture, edge and spatial features [19] after which feature detection
techniques such as SIFT, SURF, CENSURE and their variants were employed for
better performance [48]. Later, these paved way for the use of local features
using sparse representations and bag of visual words (BoVW) [19]. Performances
of all these methods were surpassed by deep learning techniques. The seminal
work [17] uses autoencoders to abstract and learn the representations of
images for content based retrieval tasks by mapping input images into concise
28-bit binary codes. [3] proposes to use the visual representations derived
from the top layers of trained neural network to be used as visual encodings
for retrieval. In [49], the authors propose to use unsupervised deep learning
methods to semantically hash images for retrieval by extracting vital
information to improve the efficiency of visual hashing. [45], [32] present
few other methods on hashing methods for image retrieval using deep learning.
[22] proposes to use ImageNet [5] pre-trained models as feature extractors for
image retrieval tasks and compares the performance against other contemporary
methods. [44] propose a deep ranking model to capture inter and intra class
differences to improve the discerning ability of the model using triplet
sampling. [7] offers a comprehensive survey on the progression of deep
learning based methods employed for CBIR over the decade with detailed
analysis on the performance of the state of the art models.

Though there are numerous works on CBIR and text query-based video retrieval,
there are only a few on content based video retrieval. The survey in [25]
elaborates on video retrieval methods based on conventional low-level feature
descriptors and nature of the features with best set of features to select
from. [35] and [29] deal with employing Support Vector Machines (SVM) for
video retrieval and relevance feedback mechanism for the retrieved results.
[21] use CNNs for feature extraction from video frames and PCA to reduce the
feature dimension for retrieval of public cultural videos. [26] leverage the
power of CNNs and use the extracted features as frame descriptors with several
similarity metrics for retrieving results for endoscopic medical database.
[47] uses frame-level features extracted from CNNs with bag of visual words
(BoVW) and clustering to retrieve videos based on visual content. The task of
action recognition in video is closely related to retrieval as it also
involves learning the content of the video based on visual information [23]
employs discriminative clustering technique with a slightly modified version
of Block-Coordinate Frank-Wolfe algorithm to recognize actions in videos. In
[24], the same authors offer an end-to-end self supervised method to learn
meaningful representations from videos for the tasks of action localization
and segmentation. [50] offers an efficient way of using CNNs by capturing
temporal dependencies among neighboring frames using late fusion that can be
used on different video tasks.

Most of the works on video related tasks using deep learning was completely
dominated by 3D convolutional neural network (3D CNNs) [41] and its variants
with optical flow information. 3D CNNs by nature, use typically small 3D
kernels to learn saptial and temporal features jointly by operating on spatial
dimensions of the frame and temporal dimension which is across the frames.
Though they perform well on standard tasks, they suffer from computational
complexity, inability to learn specific attributes of objects in the videos as
they learn spatio-temporal information cohesively which restricts them to be
used in retrieval applications.

Later, [6] introduced LRCN, the usage of recurrent networks with CNNs for
video caption generation task and J. Y. Ng et al. [46] came up with an
architecture to use 2D CNNs and RNNs with optical flow for video
classification. The two aforementioned works proved the potential and
effectiveness of coupling CNNs and RNNs together for video related tasks like
classification and captioning. Later [10] proposed a method using 2D CNNs and
RNNs for video retrieval by calculating the embedding loss between two
different input to the network. The variants of using 2D CNNs with RNNs can
over come the computational complexity of being light weight in nature. RNNs
are inherently capable of learning temporal sequences well and videos are
constituted by actions of objects under focus. The motion in the videos are
learnt well by RNN and CNNs are proven over the years to perform on image
related tasks.

Though many methods addressed throughout the paper are able to operate with
great accuracy of retrieval, they often suffer from inefficiency in terms of
time of retrieval due to their heavy and complex nature which hinders them to
be used in real-world, practical applications. Several works offer intuitive
techniques for optimization and scalability of retrieval tasks such applying
PCA for dimensionality reduction [14] of feature representation for faster
comparison, faster indexing in retrieval tasks [33], applying different
clustering methods [30] for easier matching, retrieval and approximation of
user input queries etc [39]. These modular improvements can help in designing
a retrieval framework which can work effectively in practical applications
where precise and instantaneous extraction of results is of primary focus.

##  III Datasets

The datasets that were used for this study are discussed in this section. For
evaluating the capabilities of our proposed hybrid architecture and for the
results of the discussed experiments, we use both image and video datasets.

###  III-A Image dataset

For the experiment to analyse the effect of color on retrieval, we use CIFAR10
[16] which consists of 10 classes of labelled 6000 tiny color images of size
32x32 per class. CIFAR10 is a widely used dataset to benchmark deep learning
models on various image related tasks. We also use Oxford5k Buildings Dataset
[27], a buildings dataset which is popular for image retrieval tasks with 5062
images pertaining to 11 different landmarks with relevant text queries.

###  III-B Video datasets

Since there are enough works on image retrieval in the field and it is
implicit that our architecture can well handle images, we focus on the
retrieval capacity of our method on videos.

For bench-marking the effectiveness of our model in comparison with the
conventionally use C3D for video retrieval, we use four different video
datasets. KTH Recognition of Human Actions dataset KTH-RHA [34] in short,
consists of 6 classes of human actions with about 150 grayscale videos per
class. Human Motion DataBase 51 or HMDB51 [18] contains 7000 clips of human
actions distributed across 51 class collected from various sources. UCF50 [31]
and UCF101 [38] are action recognition datasets collected from youtube
containing 50 and 101 classes respectively with around 100 clips per class.

To mimic a large video repository as seen in practical retrieval applications,
the models were trained on UCF50 dataset and were tested on other 3 datasets
containing about 4000 videos. This conglomerate of different datasets is
essential as practical scenarios often involve a diverse range of visual input
to the retrieval system demanding it to be reliable and robust. So, testing on
organized, homogeneous data won’t reflect the true ability of the solution to
work in the real-world.

To ensure consistency of results, it is made sure that there is no overlap
between video classes in train and test sets. During the testing process, the
videos are segmented into two main categories - seen and unseen. The seen
category contains classes similar to which the model was trained on and the
unseen category contains classes which are completely unrelated to the videos
the model has been exposed to.

##  IV Methodology

We elaborate our proposed methods, their effectiveness, the intuition behind
choosing them with the significance of employing them in practical
applications.

Content Based Media Retrieval (CBMR) can generally be defined as the computer
vision technique of retrieving media that is relevant to the content of the
input from a large database. In general, any content based retrieval task can
be denoted by a simple block diagram as shown in Figure 1

The architecture we propose consists of the following novel properties:

  1. 1.

Our hybrid framework works for both images and videos in tandem.

  2. 2.

It is modular in nature hence enabling every part of it to be replaced by an
appropriate alternative.

  3. 3.

Our architecture is light, fast and efficient, thus making it a scalable
alternative over the other heavy architectures.

  4. 4.

Our new re-ranking method is simple yet scrupulous and could be extended to
any retrieval task not restricted to images and videos.

Figure 1: General Overview of CBIR

###  IV-A Proposed architecture

We introduce our novel hybrid architecture for content based visual media
retrieval that works on both images and videos conjointly in this section.
This architecture consists of co-existing plug-and-play models that the user
can readily select and deploy depending on the application and data. The
proposed fused recurrent convolutional architecture which is inspired by 2D
CNN + LSTM architecture [11] is described in Figure 2.

Figure 2: Proposed recurrent convolutional architecture (2D CNN + LSTM).

The text marked in red shows the conditional flow of data. As seen, an image
is directly preprocesed, feature extracted and is sent to comparison. The
video frames are sampled, preprocessed, feature extracted, processed through
LSTM that generates final feature representation for comparison with other
videos

A video is a collection of strongly correlated frames or images that are
connected temporally and coherently holding information about an action. The
architecture is primarily built around video operation as image is considered
as a subset of a video. The architecture consists of an image feature
extractor that can output the features based on the visual and abstract
content in the input image. Any type of feature extractor -traditional
extractors like SIFT, SURF, CENSURE etc. or CNN architectures like VGG16,
MobileNet, ResNet, InceptionNet can be used depending on the nature and
criticality of the application. We selected an ImageNet [5] pre-trained
MobileNet model as the feature extractor because of its best performance.
ImageNet [5] is by far the largest (1.2 million images) and most comprehensive
image dataset covering a variety of images. This large corpus improves
generalization in the feature extractor and since MobileNet V1 [12] is known
for its best performance with a small memory footprint which is important for
fast operation. The output of the feature extractor is a feature embedding or
representation of size d that encapsulates the content of the input image.
This feature representation is made use for comparison with that of the other
indexed images (or videos) in the database in case the input of the retrieval
system is an image and the retrieved results are ranked using our similarity
metric and are rendered.

If the input of the retrieval system is a video, the video is first segmented
into smaller chunks of clips of short duration. By heuristics, an average of
15 frames is sufficient to represent a video of 10 seconds duration at 30fps.
Frame sampling rate is critical factor determining the performance of video
retrieval system in terms of speed of operation and accuracy. Often, a
sampling rate is selected so that a fine balance between both is achieved.
Each of the chunks are then passed to a frame sampler which samples the frames
at a rate as required by the LSTM [11] model. Our model operates on 16 frames
per video. The sampled frames are pre-processed and passed to the
aforementioned image feature extraction model. The set of feature
representations (16 x d) is passed to the LSTM model that is trained to learn
the temporal attribution in videos in the similar fashion. The number of
frames sampled (16)/ the number of time steps in the LSTM model regulates
unrolling with one frame feature at a LSTM time step.

LSTM [11] is capable of learning the temporal correlation between frames from
the input image’s latent representation and preservation of this information
in the LSTM’s cell state is vital to produce the best generalized video
representation for retrieval purposes. The hidden state representation of the
final time step after unrolling is taken as the video’s final feature
representation. This can be substituted by many other strategies like
aggregating the hidden state at every time step as a feature representation,
combining the cell state and hidden state from the final time step etc.
depending on the performance of each configuration and the necessity for the
application. The final representation is compared with the other indexed data
from the repository using our efficient ranking algorithm based on which the
retrieved results are rendered.

It can be easily seen that each and every module of the architecture is vital
towards the overall performance. Also, a careful and strategical selection of
the parameters can result in the best solution possible.

###  IV-B Classifiers

A classifier is a simple yet efficient solution to learn the content of the
image and hence was chosen for our primary study. An image classifier has many
attractive properties one of which is preserving generalized feature maps in
the first few layers. MobileNet is a small yet efficient neural network
architecture that can predict with high accuracy and speed. ImageNet contains
around 1000 classes of images with objects which is required for the model
generalization. Intuitively, an ImageNet trained model would have covered most
of the common objects seen in videos. Transference of the learnt knowledge
from models trained on large datasets can help in generalization since they
preserve optimal weights from receptive fields learnt on a variety of images
in a large corpus. This feature representation transfer can help in minimizing
domain divergence and providing robust feature representations. After an input
image is sent to the pretrained MobileNet, the activation of global average
pooling layer of dimension 1024 is used as image feature representation.

We use a single layer LSTM network as found it to be performing almost similar
to having multi-layer LSTM. LSTM is also trained as a video classifier whose
input is a set of 16 frame level features and a softmax probability
distribution over the number of classes as its output. We snip the LSTM model
to obtain the final hidden representation as the feature embedding for the
video. This dimension depends on the number of LSTM units which is 256 in our
case.

Alternatively, if the retrieval process is on a confined data space for the
application, the 2D CNN and the LSTM architecture enables end-to-end training
as a classifier as shown in Figure 3. It should be noted that the end-to-end
training works only for the data whose distribution or nature is known prior
to training and it is similar to the 3D CNN in terms of operation and the
generalization ability to learn the objects in the frames is low.

Figure 3: End to end training of the proposed architecture.

b is batch size which we will ignore for now, n is the number of frames per
video / LSTM time steps , w,h is the resolution of the frames and c is the
number of channels. The dotted enclosure shows the part of the architecture
that will be used for retrieval in the final stages.

###  IV-C Training configuration

We train the 2D CNN + LSTM model and the 3D CNN model on the same dataset to
benchmark the performance against each other. For training, we take a subset
of UCF50 with 38 classes which have almost equal distribution of videos i.e.
more than 120 videos per class. The dataset consists of 4557 videos and we use
90% of it for training and 10% of it for validation. For ensuring the best
performance, we augment the data using random sampling and central cropping of
videos.

We use almost the same hyperparameters for training both 2D CNN + LSTM and 3D
CNN models. Adam optimizer is used as it is a better alternative over gradient
descent for faster convergence and adaptive learning. We use dropout of 25%
after the fully-connected layers in each of the networks as regularization
helps in generalization, and ReLU activation function is used as it reduces
training time. We use categorical cross-entropy loss to train the classifiers.
The details of training111Models trained on Intel Xeon CPU, 12GB RAM, 16GB
Tesla P100 GPU on inputs of size $16\times 224\times 224\times 3$ are given in
Table I.

TABLE I: Training information of models Hyperparameter | 3D CNN | 2D CNN + LSTM
---|---|---
Epochs | 75 | 100
Batch Size | 4 | 64
ADAM - Learning Rate | 0.005 | 0.001
Feature representation dimension | 256 | 256

###  IV-D Results ranking

For retrieval tasks, euclidean distance and cosine similarity are the most
used comparison metrics. Euclidean distance / L2 Norm calculates the distance
between two points in the euclidean space and is given by the equation 1

$ED\left(p,q\right)=\sqrt{\sum_{i=1}^{n}\left(q_{i}-p_{i}\right)^{2}}$ (1)

Cosine similarity measures the similarity between two vectors using inner
product in multidimensional space. Cosine similarity is given by equation 2,

$\cos{\theta}=cos(p,q)=\frac{p\cdot q}{||p||\cdot||q||}$ (2)

The euclidean distance measures how two vectors are far apart and the cosine
similarity measures the orientation between two vectors. Usually only one of
the two metrics are used for retrieval until [40] used L2 norm to approximate
cosine similarity for faster calculation. [43] came up with a solution to
integrate distance and rotation of features in multidimensional space to match
and compare them.

Inspired by these two works, we devised a simple and novel ranking and
filtering approach called the proximal affinity re-ranking (PAR) by using a
combination of euclidean distance / L2 Norm and cosine similarity based
ranking method. The top k results are first extracted based on euclidean
distances from closest to farthest among the data in the repository. This
process aggregates the closest feature representations in the latent space. We
then threshold $\delta_{t}$ and short-list s results based on the value of
cosine similarity which selects the feature representations that have similar
orientation from the origin in latent space. The algorithm for proximal
affinity re-ranking is shown below in Algorithm 1.

The intuition behind this process is that similar representations are ideally
concentrated in the same direction in parts of the latent space. To render the
best results, the closer ones with similar orientations to that of the input
data are selected as they represent the similarity in terms of content
provided that the representations are robust and from a generalized model. The
value of the threshold $\delta_{t}$ is chosen empirically depending on the
nature of the model’s output representations and performance on a sample test
set. This threshold helps in filtering out irrelevant results among the
retrieved ones.

1

Input: Query data $x_{i}$

Feature extraction model $f$

Indexed features of n data samples in the repository
$Y_{DR}=[y_{1},y_{2},..y_{n}]$

2

Output: Indices of retrieved data samples, $R_{indices}$

3 $y_{i}=f(x_{i})$ $\triangleright$ # Feature representation of input

4 $E=[]$ $\triangleright$ # Array of euclidean n distances

5 for  _j = 1,2,..n_ do

6 $E[j]=ED(y_{i},y_{j})$

7 end for

8$E_{s}=sort\\_k(E,k)$ $\triangleright$ # Sorts and returns closest k samples

9 $E_{si}=indices(E_{s})$ $\triangleright$ # Returns indices of the values

10 $R_{indices}$ = [] $\triangleright$ # Indices of the retrieved samples

11 add_count = 0

12 for  _l = 1,2,..k_ do

13 $c_{l}=cos(y_{i},y_{l})$

14 if  _$c_{l} >\delta_{t}$_ then

15 $R_{indices}$[add_count] = $E_{si}[l]$

16 add_count = add_count + 1

17 end if

18

19 end for

Algorithm 1 Proximal affinity re-ranking

##  V Experiments

We describe the experiments involved in our work in this section.

###  V-A Effect of color on retrieval

Though, it is established that CNNs benefit from learning colors resulting in
better performance on classification tasks, the exact dependence on color for
retrieval tasks has not been studied in detail. We were curious on how much
color in images can make a difference in terms of performance of retrieval in
comparison to grayscale images. For this experiment, we shallow trained two
instances of the same MobileNet V1 [12] classifiers with exactly the same
parameters except for only the number of channels – 3 for color and 1 for
grayscale on the same train data and tested them on unseen data till the
validation accuracy reaches about 70%. The train (seen) and test (unseen) sets
were selected randomly with each about half of the number of classes in
respective datasets.

###  V-B Video Retrieval

Our experiments on video retrieval was two-fold as shown below.

  1. 1.

Testing the efficiency of our proposed framework, 2D CNN + LSTM against the
conventional 3D CNN.

  2. 2.

Checking the performance difference between the proposed proximal affinity re-
ranking method and euclidean distance, the conventionally used metric.

The models were trained and tested in the same environment. All the critical
hyper-parameters were kept the same between the models to accurately benchmark
the results against one another. Testing a retrieval system on data similar to
the train data will reduce to a classification problem. The potential of the
system can be measured only on unseen and irrelevant data. Also, to mimic the
environment containing new or unseen videos which can be considered as samples
out of the train data distribution, we have created a test environment in
which there are two different sets of data - seen and unseen. Since we had
multiple datasets for our utilization, we created a conglomerate of the test
data but making sure that no video from the training dataset was reused in
anyway for testing. The data in the test pool from different datasets was
segregated into two sets - one with classes of video samples similar to the
ones available in the train data as seen and the unseen set consisted of all
the other data that were completely irrelevant to the data that was used for
training to check the generalization of models and the robustness in
representations. The unseen data resembles operating in the real world where
one can’t expect the models to only perform on the data they are familiar
with. The basic code for our work is available at
https://github.com/ambareeshravi/media_retrieval

##  VI Results

The results of our experiment on the effect of color on retrieval performance
is given in the Table II below. The MobileNet color and grayscale
classification models were trained and tested on CIFAR10 after which the
fully-connected layers responsible for classification were discarded to get
the feature representations. Models trained for 50 epochs on 32x32 images with
validation accuracy of 74% and Oxford 5K dataset with validation accuracy 69%
for classification. It is apparent from the Table II that the difference in
accuracy between the grayscale model and the color model on untrained classes
is meagre. This permits the grayscale models to be used in retrieval tasks in
which computation efficiency is critical as using grayscale inputs ensures
faster computation as it has 4% lesser number of parameters (in MobileNet V1)
and performance almost similar to color images. This parameter reduction will
aggregate to a much larger number for videos while operating at scale on huge
data repositories.

TABLE II:  Image retrieval accuracy of color and grayscale models Dataset | Retrieval accuracy in % - top 100
---|---
Color model |  Grayscale model
CIFAR10 (untrained classes) |  81.62 |  80.03

The retrieval performance of the proposed 2D CNN + LSTM framework was compared
with the conventional 3D CNN architecture on seen and unseen data which were
segregated in 90% and 10% proportion for test videos to be retrieved and input
seed videos respectively. Each seed video had about 100 similar videos to be
retrieved. The salient features of our proposed framework against the
conventionally used 3D CNN model is shown in Table III.

TABLE III:  Notable attributes of the proposed architecture Parameter |  2D CNN + LSTM [ours] |  3D CNN
---|---|---
Total training time on 4500 videos |  2.7 hours |  16 hours
Total number of parameters |  4.5 Million |  46 Million
Feature extraction time for a 16x224x224x3 video on CPU |  0.8 seconds |  1.2 seconds
Total model size |  22.5MB |  305.17MB

The metrics which are most commonly used for retrieval tasks are accuracy,
precision, recall and F1 score which are given by the equations 3, 4, 5, 6
respectively. The correctness of the retrieved result is decided based on the
category of retrieval and the input seed video.

$Accuracy=\frac{TruePositives+TrueNegatives}{Total}$ (3)
$Precision=\frac{TruePositives}{TruePositives+FalsePositives}$ (4)
$Recall=\frac{TruePositives}{TruePositives+FalseNegatives}$ (5)
$F1Score=\frac{2*Precision*Recall}{Precision+Recall}$ (6)

The performance metrics for top 5 retrieved results are shown in Table IV and
the overall performance for the proposed 2D CNN + LSTM model with respect to
the conventionally used 3D CNN model on both L2 Norm and the proposed proximal
affinity re-ranking as metric are shown in the Figure 4. It can be seen that
the proposed 2D CNN + LSTM consistently outperforms the conventional 3D CNN in
all configurations indicating its ability to better generalize over the data.
Also, our proposed re-ranking metric significantly boosts the performance of
models as it filters out irrelevant results thereby choosing quality over
quantity. The other performance metrics showing the effectiveness of the
proposed approach 2D CNN + LSTM with PAR is shown in Fig 4. It can also be
seen from Table III that our approach is lighter and faster when compared to
3D CNN which makes it the favorable option for video retrieval.

TABLE IV:  Top 5 performance comparison of the Conv2D LSTM model and 3D CNN model- trained on UCF50 and tested on KTH-RHA, UCF101 and HMDB50 Metric | Seen data | Unseen data
---|---|---
3D CNN | 2D CNN + LSTM | 3D CNN | 2D CNN + LSTM
EU |  PAR |  EU |  PAR |  EU |  PAR |  EU |  PAR
Accuracy |  0.6578 |  0.7316 |  0.7644 |  0.8575 |  0.5983 |  0.6414 |  0.7113 |  0.914
Precision |  0.5933 |  0.6675 |  0.7481 |  0.8656 |  0.4984 |  0.5462 |  0.6225 |  0.8793
Recall |  0.4983 |  0.6015 |  0.6644 |  0.7984 |  0.3759 |  0.4303 |  0.5225 |  0.842
F1-score |  0.5261 |  0.6222 |  0.6866 |  0.8165 |  0.4141 |  0.467 |  0.5566 |  0.8555
Figure 4:  Performance comparison of the Conv2D LSTM model with the prevalent
method - trained on UCF50 and tested on KTH-RHA, UCF101 and HMDB50

##  VII Best practices

The number of frames has a critical role in determining the learning and in
turn the performance of retrieval. We suggest using PCA [14] on the feature
representations to reduce the dimension for faster comparison as we verified
that there wasn’t any significant drop in accuracy after reducing the feature
dimension to a lower dimension with a greater than or equal to Proportion of
Variance of 90%. We also found that picking a decently trained model
performing better than the best trained model which would have considerable
bias towards the train data. Also, the right length of the feature
representation is to be chosen while modelling which might impact computation
and the performance.

There are several options to optimize the deep learning models like filter
pruning, replacing fully-connected layers with 1D convolution layers etc. For
applications with speed of retrieval as primary goal, one obvious option is to
use clustering on the media in the database and use only the centroid feature
vectors for comparison. But if the application requires precision, clustering
may not be a good option as it is approximate, doesn’t work well on new data
samples and since one has to update the centroid every time a data point is
added.

##  VIII Future scope

In this section, we identify the future research that can be carried out to
potentially improve on our current work in terms of optimization and better
implementation. First, we focus on better implementation, for better accuracy
of retrieval the changes that can be imparted into a system. Due to the
modular nature of our proposed architecture, an inclusion of an application
specific feature extractor is feasible. It is important to replace the
classifier with AutoEncoders, Siamese Networks and GANs and study their
performance on retrieval tasks. Since RNN plays a vital role in our
architecture, implementing other configurations of RNNs like GRU,
bidirectional RNNs, multilayered/stacked RNNs instead of LSTMs and studying
their effect on performance is necessary. Increasing the number of time steps
of the RNN [11], experimenting with the optimal number hidden units for the
best results, implementing dynamic, bidirectional, multilayered LSTMs can also
be done to potentially improve the performance. Due to the modular nature of
our proposed architecture, using fast comparison libraries like FAIR’s FAISS
[15], Spotify’s modification of approximate nearest neighbors ANNOY index [20]
will help in improving the processing time when it comes to large databases as
they have the ability to use GPU for large scale computation to speed up the
retrieval process.

##  IX Conclusion

Performance and computational constraints of the prevalent algorithms have
been prohibiting their use in video retrieval tasks and to address the issue,
we offer a novel, fused framework for conjoint image and video retrieval with
a new simple re-ranking method called proximal affinity re-ranking. We also
present substantial results to enunciate the effectiveness of our approach.
The experimental results exhibit the overall ability of our approach in terms
of accuracy and speed, over the widely used ones. This proposed architecture
is flexible and can potentially be extended to other forms of retrieval like
audio, document retrieval etc. We also discuss our experiments, best practices
that can help in improving existing architectures and the future scope to
augment our current research.

## References

  * [1] Relja Arandjelović and Andrew Zisserman.  Three things everyone should know to improve object retrieval.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 2911–2918. IEEE, 2012.
  * [2] Artem Babenko and Victor Lempitsky.  Aggregating local deep features for image retrieval.  In Proceedings of the IEEE international conference on computer vision, pages 1269–1277, 2015.
  * [3] Artem Babenko, Anton Slesarev, Alexandr Chigorin, and Victor Lempitsky.  Neural codes for image retrieval.  In European conference on computer vision, pages 584–599. Springer, 2014.
  * [4] Gabriella Csurka, Christopher Dance, Lixin Fan, Jutta Willamowski, and Cédric Bray.  Visual categorization with bags of keypoints.  In Workshop on statistical learning in computer vision, ECCV, volume 1, pages 1–2. Prague, 2004.
  * [5] 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.
  * [6] Jeffrey Donahue, Lisa Anne Hendricks, Sergio Guadarrama, Marcus Rohrbach, Subhashini Venugopalan, Kate Saenko, and Trevor Darrell.  Long-term recurrent convolutional networks for visual recognition and description.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2625–2634, 2015.
  * [7] Shiv Ram Dubey.  A decade survey of content based image retrieval using deep learning.  arXiv preprint arXiv:2012.00641, 2020.
  * [8] Albert Gordo, Jon Almazán, Jerome Revaud, and Diane Larlus.  Deep image retrieval: Learning global representations for image search.  In European conference on computer vision, pages 241–257. Springer, 2016.
  * [9] Albert Gordo, Jon Almazan, Jerome Revaud, and Diane Larlus.  End-to-end learning of deep visual representations for image retrieval.  International Journal of Computer Vision, 124(2):237–254, 2017\.
  * [10] Yun Gu, Chao Ma, and Jie Yang.  Supervised recurrent hashing for large scale video retrieval.  In Proceedings of the 24th ACM international conference on Multimedia, pages 272–276, 2016.
  * [11] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural computation, 9(8):1735–1780, 1997.
  * [12] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  arXiv preprint arXiv:1704.04861, 2017.
  * [13] Mohamed Maher Ben Ismail.  A survey on content-based image retrieval.  (IJACSA) International Journal of Advanced Computer Science and Applications, 8(5):159–170, 2017.
  * [14] Hervé Jégou and Ondřej Chum.  Negative evidences and co-occurences in image retrieval: The benefit of pca and whitening.  In European conference on computer vision, pages 774–787. Springer, 2012.
  * [15] Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  IEEE Transactions on Big Data, 2019.
  * [16] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  University of Toronto, 2009.
  * [17] Alex Krizhevsky and Geoffrey E Hinton.  Using very deep autoencoders for content-based image retrieval.  In ESANN, volume 1, page 2. Citeseer, 2011.
  * [18] Hildegard Kuehne, Hueihan Jhuang, Estíbaliz Garrote, Tomaso Poggio, and Thomas Serre.  Hmdb: a large video database for human motion recognition.  In 2011 International Conference on Computer Vision, pages 2556–2563. IEEE, 2011.
  * [19] Afshan Latif, Aqsa Rasheed, Umer Sajid, Jameel Ahmed, Nouman Ali, Naeem Iqbal Ratyal, Bushra Zafar, Saadat Hanif Dar, Muhammad Sajid, and Tehmina Khalil.  Content-based image retrieval and feature extraction: a comprehensive review.  Mathematical Problems in Engineering, 2019, 2019.
  * [20] W Li, Y Zhang, Y Sun, W Wang, and W Zhang.  Lin x. approximate nearest neighbor search on high dir mensional data―experiments, analyses, and improvement.  arXiv preprint arxiv:1610.02455, 8, 2016.
  * [21] Yumeng Liu and Aina Sui.  Research on feature dimensionality reduction in content based public cultural video retrieval.  In 2018 IEEE/ACIS 17th International Conference on Computer and Information Science (ICIS), pages 718–722. IEEE, 2018.
  * [22] Subhadip Maji and Smarajit Bose.  Cbir using features derived by deep learning.  arXiv preprint arXiv:2002.07877, 2020.
  * [23] Antoine Miech, Jean-Baptiste Alayrac, Piotr Bojanowski, Ivan Laptev, and Josef Sivic.  Learning from video and text via large-scale discriminative clustering.  In Proceedings of the IEEE international conference on computer vision, pages 5257–5266, 2017.
  * [24] Antoine Miech, Jean-Baptiste Alayrac, Lucas Smaira, Ivan Laptev, Josef Sivic, and Andrew Zisserman.  End-to-end learning of visual representations from uncurated instructional videos.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9879–9889, 2020.
  * [25] BV Patel and BB Meshram.  Content based video retrieval systems.  arXiv preprint arXiv:1205.1641, 2012.
  * [26] Stefan Petscharnig and Klaus Schöffmann.  Binary convolutional neural network features off-the-shelf for image to video linking in endoscopic multimedia databases.  Multimedia Tools and Applications, 77(21):28817–28842, 2018.
  * [27] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman.  Object retrieval with large vocabularies and fast spatial matching.  In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8, 2007.
  * [28] Alexey Potapov, Innokentii Zhdanov, Oleg Scherbakov, Nikolai Skorobogatko, Hugo Latapie, and Enzo Fenoglio.  Semantic image retrieval by uniting deep neural networks and cognitive architectures.  In International Conference on Artificial General Intelligence, pages 196–206. Springer, 2018.
  * [29] Mohsen Ramezani and Farzin Yaghmaee.  Retrieving human action by fusing the motion information of interest points.  International Journal on Artificial Intelligence Tools, 27(03):1850008, 2018.
  * [30] Siddheswar Ray and Rose H Turi.  Determination of number of clusters in k-means clustering and application in colour image segmentation.  In Proceedings of the 4th international conference on advances in pattern recognition and digital techniques, pages 137–143. Calcutta, India, 1999.
  * [31] Kishore K Reddy and Mubarak Shah.  Recognizing 50 human action categories of web videos.  Machine vision and applications, 24(5):971–981, 2013.
  * [32] Josiane Rodrigues, Marco Cristo, and Juan G Colonna.  Deep hashing for multi-label image retrieval: a survey.  Artificial Intelligence Review, pages 1–47, 2020.
  * [33] Pouria Sadeghi-Tehran, Plamen Angelov, Nicolas Virlet, and Malcolm J Hawkesford.  Scalable database indexing and fast image retrieval based on deep learning and hierarchically nested structure applied to remote sensing and plant biology.  Journal of Imaging, 5(3):33, 2019.
  * [34] Christian Schuldt, Ivan Laptev, and Barbara Caputo.  Recognizing human actions: a local svm approach.  In Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004., volume 3, pages 32–36. IEEE, 2004.
  * [35] Ling Shao, Simon Jones, and Xuelong Li.  Efficient search and localization of human actions in video databases.  IEEE Transactions on Circuits and Systems for Video Technology, 24(3):504–512, 2013.
  * [36] Anshuman Vikram Singh.  Content-based image retrieval using deep learning.  Rochester Institute of Technology, 2015.
  * [37] Ms Anchal A Solio and Siddharth A Ladhake.  A review of query image in content based image retrieval.  International Journal of Advanced Research in Computer Engineering & Technology (IJARCET), 2(4):1619–1622, 2013.
  * [38] Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah.  Ucf101: A dataset of 101 human actions classes from videos in the wild.  arXiv preprint arXiv:1212.0402, 2012.
  * [39] Abhijit Suprem and Polo Chau.  Approximate query matching for image retrieval.  arXiv preprint arXiv:1803.05401, 2018.
  * [40] Hiroki Tanioka.  A fast content-based image retrieval method using deep visual features.  In 2019 International Conference on Document Analysis and Recognition Workshops (ICDARW), volume 5, pages 20–23. IEEE, 2019.
  * [41] Du Tran, Lubomir Bourdev, Rob Fergus, Lorenzo Torresani, and Manohar Paluri.  Learning spatiotemporal features with 3d convolutional networks.  In Proceedings of the IEEE international conference on computer vision, pages 4489–4497, 2015.
  * [42] Ji Wan, Dayong Wang, Steven Chu Hong Hoi, Pengcheng Wu, Jianke Zhu, Yongdong Zhang, and Jintao Li.  Deep learning for content-based image retrieval: A comprehensive study.  In Proceedings of the 22nd ACM international conference on Multimedia, pages 157–166, 2014.
  * [43] Jianfeng Wang and Xiaorong Zhao.  A new approach for image retrieval with integrated euclidean distance and rotational correlation.  In 2010 IEEE International Conference on Wireless Communications, Networking and Information Security, pages 391–395. IEEE, 2010\.
  * [44] Jiang Wang, Yang Song, Thomas Leung, Chuck Rosenberg, Jingbin Wang, James Philbin, Bo Chen, and Ying Wu.  Learning fine-grained image similarity with deep ranking.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1386–1393, 2014.
  * [45] Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al.  A survey on learning to hash.  IEEE transactions on pattern analysis and machine intelligence, 40(4):769–790, 2017.
  * [46] Joe Yue-Hei Ng, Matthew Hausknecht, Sudheendra Vijayanarasimhan, Oriol Vinyals, Rajat Monga, and George Toderici.  Beyond short snippets: Deep networks for video classification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4694–4702, 2015.
  * [47] Chengyuan Zhang, Yunwu Lin, Lei Zhu, Anfeng Liu, Zuping Zhang, and Fang Huang.  Cnn-vwii: An efficient approach for large-scale video retrieval by image queries.  Pattern Recognition Letters, 123:82–88, 2019.
  * [48] Wengang Zhou, Houqiang Li, Jian Sun, and Qi Tian.  Collaborative index embedding for image retrieval.  IEEE transactions on pattern analysis and machine intelligence, 40(5):1154–1166, 2017.
  * [49] Lei Zhu, Jialie Shen, Liang Xie, and Zhiyong Cheng.  Unsupervised visual hashing with semantic assistant for content-based image retrieval.  IEEE Transactions on Knowledge and Data Engineering, 29(2):472–486, 2016.
  * [50] Mohammadreza Zolfaghari, Kamaljeet Singh, and Thomas Brox.  Eco: Efficient convolutional network for online video understanding.  In Proceedings of the European conference on computer vision (ECCV), pages 695–712, 2018.


# Color Aesthetics: Fuzzy based User-driven Method for Harmony and Preference
Prediction

Pakizar Shamoi  Department of Information Systems Management,
Kazakh-British Technical University
Almaty, Kazakhstan
Email<EMAIL_ADDRESS>Atsushi Inoue  Department of Computer Science,
Eastern Washington University
Washington, USA
Email<EMAIL_ADDRESS>Hiroharu Kawanaka  Graduate School of
Engineering,
Mie University
Tsu, Japan
Email<EMAIL_ADDRESS>
###### Abstract

Color is the most important intrinsic sensory feature that has a powerful
impact on product sales. Color is even responsible for raising the aesthetic
senses in our brains. Account for individual differences is crucial in color
aesthetics. It requires user-driven mechanisms for various e-commerce
applications. We propose a method for quantitative evaluation of all types of
perceptual responses to color(s): distinct color preference, color harmony,
and color combination preference . Preference for color schemes can be
predicted combining preferences for the basic colors and ratings of color
harmony. Harmonious pallets are extracted from big data set using comparison
algorithms based on fuzzy similarity and grouping.The proposed model results
in useful predictions of harmony and preference of multicolored images. For
example, in the context of apparel coordination, it allows predicting a
preference for a look based on clothing colors. Our approach differs from
standard aesthetic models, since in accounts for a personal variation. In
addition, it can process not only lower-order color pairs, but also groups of
several colors.

##  I Introduction

Understanding human aesthetic preference is a challenging task that can be
highly useful for a number of industries, including design [1], marketing, and
fashion (e.g., refined user-driven results for visual search engines). Fashion
aesthetics involves many aspects, including the color, various styles (e.g.,
sleeves types), materials, spatial compositions, etc. However, consumers
usually judge an item within 90 seconds of viewing and initial assessments are
mostly driven by colors (i.e. when a human perceives colors, a rich network of
associations gets activated). So, we pay a lot of attention to color
aesthetics in particular, for making personalized recommendations for images.
But we need to remember that preference for harmonious color stimuli is just
one factor underlying aesthetic response.

Color aesthetics involves studying of visually appealing color combinations
hidden in the interior, fashion look or even some piece of art. So that a user
sees a composition (of any items) and gets the aesthetic pleasure. Color is
generally considered to be one of the most important and distinguishing visual
features. Additionally, it is often treated as an aesthetic issue, having a
significant impact on product sales, accounting for 85% of the reason why
consumer purchases a product. How? By creating an impression and raising the
aesthetic senses, color influences decision-making (buy or not to buy)
processes in our brains.

Humans have different levels of visual sensitivity and different color
perception abilities. Differentiating between millions of colors, wherein
describing a whole image by only using a few colors is a challenging task.
That is why the majority of shopping portals, like Amazon and eBay use TBIR,
have limitations like subjectivity, manual image tagging and incompleteness.
So, we need a human-consistent way to represent color images.

By adopting fuzzy set based representations and the necessary calculus for
them we can solve the problem of semantic gap between low-level color visual
features and high-level concepts. In our previous works [2], [3], we discuss
how we use fuzzy sets to deal with the uncertainty linked to apparels images
for the online shopping coordination. Color channels distributions in our
space are expressed with fuzzy membership functions [2].

We claim that color theories must be shaped by aesthetic norms, including
taste (preference for single colors) and trends (context-aware harmonious
palettes). We propose a technique to predict the aesthetic preference for
color combinations by introducing the new variables, color harmony and color
preference. Aesthetic responses to colors are highly influenced by harmony
between colors, since the same color can create different impression when
viewed together with different colors. We believe that concepts of preference
and harmony and their relationship can serve as a tool for future
investigations in aesthetics across multiple domains.

Difference between preference and harmony is crucial. Aesthetic preference for
color combinations is mostly driven by color harmony and there are some common
tendencies in defining them. However, there are also small differences in the
degree to which people prefer harmony, with correlations in the range from
0.03 to 0.75. [4], [5]. In the context of e-commerce shopping, there are two
main related questions:

  1. 1.

How do colors of apparels influence preference and harmony judgements?

  2. 2.

How to predict a preference for a look based on colors of apparels?

In this paper, we try to answer the above questions by predicting combination
preference from components preference and harmony. We use results of
experiments of Berkeley Color Project [6], [4], [5], and claim that higher
individual preference for distinct colors and higher harmony ratings imply
higher preference.

We extract harmonious pallets from big data sets, test them by conducting a
questionnaire and then use comparison algorithms based on fuzzy similarity.
Our previous method just gave us true/false response on a harmony of a
particular combination. In this work we propose the method to quantify the
harmony and add the phenomenon of preference.

##  II Motivation

In our previous works [2], [3] we proposed an approach based on fuzzy sets and
logic towards the creation of a perceptual color space (FHSI, fuzzy HSI). FHSI
colors are modelled by means of fuzzy sets defined on an HSI color space and a
fuzzy partition is defined in the corresponding color feature domain (fuzzy
color space). There are 92 colors in FHSI. The soft boundaries between the
color categories were derived experimentally through an online survey based on
human color categorization. We also defined methods for finding the perceptual
difference between colors and the degree of similarity between images based on
FHSI system [2], [3].

Currently we are working on developing a human-consistent image retrieval
system for apparel coordination based on the FHSI perceptual color space. We
faced the problem of quantitative evaluation of a color combination harmony.

Humans often experience colors not in an isolation, but in a combination. The
aesthetic perception of a color group is strongly influenced by its overall
harmony. Hence, it is essential to consider the congruency of chromatic
compositions, rather than how much people like single colors[4].

Throughout history, it has been the contradiction in research works of color
theorists studying harmony. In [7] Chevreul defined the law of simultaneous
contrast of colors and proposed harmonies of analogous and contrasting colors.
Another great color theorist, Itten, stated that “harmonious” color
combinations are composed of closely similar chromos (e.g. tones, tints and
shades), or else of different colors of the same nuance[8]. In essence, his
theory defines harmonious colors as colors producing neutral gray when mixed.
Furthermore, Munsell and Ostwald put ahead the idea that colors are harmonious
if they have some relation in the given color space (e.g., if colors are
similar in hue) [4].

As we see, the color literature is full of discrepancies. If we unite these
theories into one system we will obtain that nearly every color combination
can be considered as harmonious [4]. The source of this contradiction lies in
the fact that there is still neither human consistent color space nor single
best representation of color. There are multiple spaces that characterize the
color features from different perspectives instead. Therefore, it is a very
challenging task to represent, measure and process colors and their harmony.

##  III Evaluation of Color Harmony and Preference

Preference and harmony are often used interchangeably. However, these two
phenomenon are similar only in case an observer likes the colors in the
combination. To avoid a confusion we need to accurately define and measure
them.

###  III-A Typology of Color Judgements

In order to better customize the system for each user, we need to define and
carefully understand the difference between Single Color Preference (SCP),
Color Scheme Harmony (CSH), and Color scheme preference (CSP). They are all
three distinct types of judgments and different ways of evaluation of
perceptual responses to color schemes.

####  III-A1 Single Color Preference

SCP reflects the contextless preference ratings. Usually, people tend to
prefer some colors over others, and nearly everyone has its favourite color.

SCP measures can be obtained during or after the registration in the system.
We just offer a small survey with simple visual content (colors) with
questions (e.g., How much do you like the display?) and collect the responses
using a rating scale (e.g., Not at all , Good, Very much, etc.). An example of
Single Color Ratings can be seen in Fig. 1. The idea is to account for basic
colors without a considerable loss in precision.

Figure 1: Example of Single Color Ratings.

####  III-A2 Color Scheme Harmony

In contrast, a CSH reflects how strongly the colors in the combination are
going well together, regardless of whether an individual likes the given
combination or not. In other words, CSH indicates the harmony of the color
combination as a whole.

####  III-A3 Color Scheme Preference

A color palette (combination, scheme, group) preference is defined as how much
an individual likes a given combination of colors. So, it reflects an
aesthetic preference for a given palette as a whole

SCP ratings are not enough to predict CSP. To better define palette preference
we need a relational factor like harmony. The problem is how to derive it?
Conventional methods are no longer valid to meet current requirements [3].

###  III-B Harmonious Palettes Derivation

In [6], [4], [5] it was concluded that color harmony is a function of color
similarity. What is more, people tend to prefer color combinations, which
contain colors that are similar in hue, cool, and desaturated. However, we
believe that harmony is a very complex phenomenon and it is nearly impossible
to purely define it in terms of strict rules.

We want to extract harmonious, fuzzy color-based pallets from data set. This
is done by forming groups containing looks with similar color compositions. To
achieve this, we use the fuzzy model we developed, formulas for fuzzy color
difference, palettes similarity (described in [2], [3]).

As a data set we took 10000 images with fashion looks from various sources,
including the most popular fashion sites , like polyvore.com, lookbook.nu,
instyle.com, dailylook.com and various style communities in SNS (instagram,
VK, Facebook). The preference was given to looks having more likes.

For each image M in a data set we perform the following:

  1. 1.

Compute the fuzzy dominant color histogram of M

  2. 2.

Compute the mean average perceptual difference $Dp_{avg}$ between $CH$ and
members of each harmonious groups.

  3. 3.

If minimal $Dp_{avg}$ is more than difference threshold, form a new group and
add M to it. Otherwise, add M to a group with which M has minimal $Dp_{avg.}$

  4. 4.

Choose groups having at least 100 similar looks falling into a similar fuzzy
color scheme.

Processing of data set took almost 7 hours (1-2 seconds for each image,
depending on resolution, current number of groups, etc.). On 8nd thousand the
convergence was achieved, since almost all new coming images were falling into
existing groups and very few new palettes were added during the processing of
the last 2000 images.

As a result, we got 139 groups in total, 59 of them contained more than 100
images. For each group we took averaged harmonious fuzzy color palette. Some
of the schemes we extracted were similar to Analogous, Contrasting, Triadic,
etc. (classified by Itten [8]), but there were also schemes which are out of
any rules. Examples of harmonious groups with more than 100 similar images can
be seen in Fig. 2.

Figure 2: Examples of Derived Harmonious Palettes.

It needs to be emphasized that color preferences may change depending on
semantic context [6]. Therefore, derived palettes provide context-aware
harmony. We can perform palettes derivation for other domains - art or
interior design, for example. The very essence of this generation process is
that it is becoming possible due to FHSI space.

###  III-C User Preference Prediction in Fashion Industry

How to predict a preference for a look based on colors of apparels? As
mentioned before, a preference for color schemes is influenced by preferences
for the component basic colors and ratings of color harmony [6]. Let’s combine
preferences for the single component colors and ratings of color harmony:

$Pref(A,B)=\frac{Pref(A)\times w_{A}+Pref(B)\times
w_{B}}{w_{A}+w_{B}}+Harm(A,B)$ (1)

In Eq. (1) $w$ is a weight importance of an apparel, $Pref(A),Pref(B)$ are
user preferences for single colors $A$ and $B$. Eq. (1) also works for three,
four, five colors as well.

Generally, aesthetic judgements of fashion looks are influenced by dominance
order. For example, dress or skirts usually make more impact on an overall
impression rather than accessories. That is why we need to take into account
$w$, apparel weight parameter:

  * •

For dresses/costumes $w=1$.

  * •

For up & down clothes (e.g.,skirts, blouses.) $w=0.75$.

  * •

For shoes and bags $w=0.5$.

  * •

For accessories (e.g., glasses, watches) $w=0.25$.

Now we can find $Harm(A,B)$ between two fuzzy colors $A$ and $B$. If there is
a palette containing both $A$ and $B$, then $Harm(A,B)=1$. Otherwise we take
the most similar color harmonious palette and find the similarity value (which
will serve as a harmony value too in this case). Harmony of a group of fuzzy
colors which is not in a knowledge base is equal to its similarity with the
closest harmonious group. We use similarity measure defined in [2].

##  IV Results

###  IV-A Application

The proposed model results in useful predictions of perceived harmony and
preference of multi-colored images.

In a popular application Polyvore, users create looks by dragging items from
the menu. It is clear that the color of the new object you add needs to
harmonize well with colors of other existing objects, but it is very difficult
for a majority of people to choose an object considering such things.

Using FHSI model [2], [3] we can index the apparels database. Furthermore, the
preference formula Eq. (1) allows us to sort all the commodity images
according to its harmony to the given apparel or look, i.e., the more
harmonious items (suiting the whole look) will be ranked more ahead. Some of
the features include:

Figure 3: Shopping Advisor Application Mockup.

  * •

Having measures for harmony and preference, we can sort the apparels on the
right by harmony to the apparels on the left. The suggested apparels will be
unique for each user, since single color ratings allow us to refine color
harmony to individual color scheme preference.

  * •

Some of the pallets have style names like modern, classic, retro, romantic,
elegant, formal, etc. User can choose several styles and see the corresponding
apparels only.

  * •

User can input several favourite colors and the system selects colors which
are in a harmony and we get many finished looks by the system and also use
these harmonious colors to filter the apparels in the menu.

The method can also be applied to automatic labelling in large image databases
[9] and customized services. One example for this is furniture coordination
(e.g., a user uploads a room image and requests sofas fitting perfectly the
interior).

###  IV-B Preliminary Experiments

Example 1. Predict the preference of user $X$ for the look in Fig. 8. As we
defined, $w_{dress}=1$ , $w_{bag}=0.5$

Since the apparels were preprocessed, we know the ids of fuzzy dominant colors
of the dress (A, 12) and the bag (B, 1). Next, suppose the single color
ratings of user $X$ areas represented in Fig. 1. So, $Pref(A)=0.8$ and
$Pref(B)=0.5$. $Harm(A,B)=1$, since fuzzy colors $1$ and $12$ are both in a
color harmony palette 27 , see Fig. 8. Finally, according to our preference
formula Eq. (1), $Pref(A,B)$ for User $X$ is $0.83$ (value is normalized to a
scale [0; 1] ). Note that for an unregistered user (e.g. for a guest)
$Pref(A,B)=Harm(A,B)=1$.

Figure 4: Look for Example 1.

Figure 5: Harmonious Palette 27.

Example 2. Predict the preference of user $Y$ for the look in Fig. 7. Apparels
weights for this example: $w_{up}=w_{down}=0.75$, $w_{bag}=w_{shoes}=0.5$, and
$w_{acc}=0.25$.

Suppose Eq. (6) depicts single color ratings of user $Y$. There is no such
color harmony group containing all the fuzzy colors in the look, but there is
a group $14$ which is the most similar, similarity is equal to 83%, so as
harmony. According to Eq. (1), $Pref(A,B)$ for User $Y$ normalized to a scale
$[0;1]\approx 0.8$.

Figure 6: Single Color Ratings of User $Y$.

Figure 7: Look for Example 2.

Figure 8: Fuzzy Dominant Color
Descriptor for Example 2.

Figure 9: Harmonious Palette 14.

##  V Conclusions and Future Work

Current work presents an overview of the findings in current research focusing
on quantification of the harmony and preference phenomena. The intended
application is apparel online shopping coordination system.

The research shown in this paper describes our preliminary results and there
are a number of next steps to take in the future. First, we plan to analyse
the correlation between preference and harmony ratings through regression
analysis. Specifically, the model can be validated by an experiment, where
human observers are judging fashion images: whether they are harmonious or
disharmonious, and whether they are liked or disliked. We can provide various
samples of stimuli and explain the pattern of variation in scheme preferences.
Second, we plan to perform the system evaluation by measuring the precision
and recall for $\sim$20 queries (Eq. (2)).

$P_{T}=\dfrac{\sum_{i=1}^{T}P_{i}}{T},R_{T}=\dfrac{\sum_{i=1}^{T}R_{i}}{T},Relevance=\dfrac{P_{T}}{R_{T}}$
(2)

$T$ is the number of selected queries, $P_{i}$ = the number of relevant
apparels retrieved divided by the number of apparels retrieved, $R_{i}$ = the
number of relevant apparels retrieved divided by the number of relevant
apparels in DB.

Next, for each user we can compute the average difference score as the
absolute value of the difference between his real preference ratings and
predicted preference. Note that $T$ is a number of looks offered to a survey
participant.

$D=\dfrac{\sum_{i=1}^{T}|Pref_{real}-Pref_{pred.}|}{T}$ (3)

Finally, knowing how to measure preference and harmony properly, we are
particularly interested in how much such aesthetic preferences might covary
across different semantic contexts. We need to check the palettes relevance in
the different aesthetic domains in order to find out whether preferences for
harmony are correlated across various domains or not. This will also be the
subject of future work.

## References

  * [1] M. Tokumaru, N. Muranaka, and S. Imanishi, _Color Design Support System Considering Color Harmony_ , Fuzzy Systems, 2002.
  * [2] P Shamoi, A Inoue, and H Kawanaka, _FHSI: Toward More Human-Consistent Color Representation_ , JACIII 20 (3), 393-401, 2016.
  * [3] P Shamoi, A Inoue, and H Kawanaka, _Fuzzy Model for Human Color Perception and Its Application in E-Commerce_ , IJUFKS 24, 47-70, 2016.
  * [4] S. Palmer and K. Schloss, _Aesthetic response to color combinations: preference, harmony, and similarity_ , Att-n, Perc. & Psychoph., 2011.
  * [5] S. Palmer and W.S. Griscom, _Accounting for taste: Individual differences in preference for harmony_ , W.S. Psychon Bull Rev., 20: 453, 2013.
  * [6] S. Palmer, K. Schloss and M. Heinemann, _Semantic Effects on Aesthetic Preference for Color Harmony in Visual Displays_ , J. of Vision, 2012.
  * [7] M. Chevreul, _The Law of Simultaneous Color Contrast_ , 1839.
  * [8] J. Itten, _The Art of Color: the subjective experience and objective rationale of color_ , New York: Van Nostrand Reinhold , 1973.
  * [9] M. Solli and R. Lenz, _Color harmony for image indexing_ , IEEE 12th Intern. Conf. on Computer Vision, 2009.


other 2 programs, the reason USP-Quad is unable to succeed is because those
examples perform integer division in a situation in which no round-off occurs.
In these programs this property is essentially encoded with an exponential
invariant, which is outside the capabilities of USP-Quad. From the results of
Table 2 we conclude that while the class of loops for which our technique is
complete is a subset of Aligators, we can still generate most of the
invariants needed to prove correctness.

##  8\. Related work

#### Polynomial absractions of loops

The algorithm in Section 4 for computing the solvable reflection of a
transition ideal can be seen as both a refinement of POPL:KCBR2018’s algorithm
for extracting a solvable polynomial map from a transition formula and a
generalization of CAV:ZK2021’s algorithm for computing deterministic affine
reflections. Contrasting with (POPL:KCBR2018), our algorithm is guaranteed to
find a best abstraction as a solvable transition ideal, which is essential to
prove monotonicity of our analysis. Contrasting with (CAV:ZK2021), our
algorithm consumes and produces transition ideals, which generalize affine
relations.

SAS:ABKKMS2022 considers the problem of abstracting polynomial endomorphisms
by solvable polynomial maps. The technique presented in Section 4 is more
general in the sense that it operates on transition ideals rather than
polynomial endomorphisms. A polynomial endomorphism
$p:\mathbb{Q}[X]\rightarrow\mathbb{Q}[X]$ can be encoded as a transition
ideal, generated by the polynomials $\left\\{x^{\prime}-p(x):x\in X\right\\}$,
in which case the algorithm in Section 4.1 computes a solvable transition
ideal (from which we may recover a solvable polynomial map—that is, our
procedure serves the same purpose as of SAS:ABKKMS2022 for the inputs
considered in that work). Moreover, our procedure provides a precision
guarantee: it finds solvable reflections of transition ideals.

For example, consider the loop below (left) along with its solvable reflection
(right)

$\textbf{while}*\textbf{do }\left\\{\begin{array}[]{l}x:=x+z^{2}+1;\\\
y:=y-z^{2};\\\ z:=z+(x+y)^{2}\end{array}\right\\}\hskip
28.45274pt\underbrace{\left\langle\left\\{a\mapsto x+y,b\mapsto
z\right\\},\left\langle
a^{\prime}-a-1,b^{\prime}-b-a\right\rangle\right\rangle}_{\text{Solvable
reflection}}$

While the technique in (SAS:ABKKMS2022) is able to identify the first
polynomial in the reflection (corresponding to the update $(x+y):=(x+y)+1$) it
cannot find the second ($z^{\prime}:=z+(x+y)^{2}$), since there is a non-
linear dependence of $z$ upon the “defective” variables $x$ and $y$ whose
dynamics cannot be described by a solvable polynomial map.

SAS:FHG2021 considers another related problem: given a polynomial endomorphism
$p$, is there a polynomial automorphism $f$ such that $f^{-1}\circ p\circ f$
is solvable? The procedure in Section 4 can also be used to solve this
problem: if $\left\langle t,T\right\rangle$ is the solvable reflection of $p$,
then such an $f$ exists (namely, $t$) exactly when the ambient dimension of
$T$ is equal to that of $p$ (and $T$ has real eigenvalues). Section 4
generalizes this result in the sense that, (1) we operate on transition ideals
rather than polynomial endomorphisms and (2) should the answer to the decision
problem be “no”, we may still compute an abstraction of $p$.

#### Complete polynomial invariant generation

TACAS:Kovacs2008; VMCAI:HJK2018; JACM:EOPW2023; LICS:HOPW2018; ISAAC:RCK2004
are complete methods for generating polynomial invariants on limited program
structures. Our method matches the completeness results of these works on
single loops whose bodies are described by solvable polynomial maps; however,
the completeness result of each of these works extend beyond simple loops
whose bodies are described by a solvable polynomial map.

LICS:HOPW2018; JACM:EOPW2023 present a method that is complete for generating
polynomial invariants for affine programs where all branching represents non-
deterministic choice. Our methods have no issue analyzing such programs.
Moreover, our method can also reason about programs with polynomial
assignments as well as branching with conditionals. However, even though our
method can reason about general affine programs, we can only guarantee
completeness in the case of a loop whose body is described by a solvable
polynomial map.

TACAS:Kovacs2008 presents complete polynomial invariant generation for _P-
solvable_ loops. These are loops, with no branching, whose bodies have either
Gosper-summable or c-finite assignments. As stated in Section 3.3 c-finite
sequences are equivalent to solvable polynomial maps, and so our technique
matches TACAS:Kovacs2008 in that regard. However, while we always extract a
solvable transition ideal from a loop, solvable transition ideals are not
powerful enough to capture certain Gosper-summable examples. Thus, while our
method is monotone on such examples, it does not guarantee completeness.
VMCAI:HJK2018 extends TACAS:Kovacs2008 to the case of multi-path loops where
each branch has a body with Gosper-summable or c-finite recurrence
assignments. In the Gosper-summable case the comparison is the same as
TACAS:Kovacs2008. In the c-finite case we are also not complete; however, we
experimentally compare with VMCAI:HJK2018 in this case in Section 7.3. In
either the case of TACAS:Kovacs2008 or VMCAI:HJK2018 they cannot make a
completeness guarantee for programs having branching with conditionals or
programs with arbitrary loop nesting.

ISAAC:RCK2004; JSC:RCK2007 present a complete method for the case of a single
multi-path loop where each branch has a body described by a c-finite
recurrence. This matches the c-finite case of VMCAI:HJK2018, except
ISAAC:RCK2004; JSC:RCK2007 have an additional restriction on the eigenvalues
of the c-finite recurrences (corresponding to the $\Theta_{i}$ variables of
Eq. 2). For ISAAC:RCK2004; JSC:RCK2007 the eigenvalues are required to be
positive and rational. We have no such restriction and so our method
generalizes ISAAC:RCK2004; JSC:RCK2007 in the case of a simple loop where the
body is described by a c-finite recurrence. However, their completeness result
goes beyond our capability in the case of a multi-path loop with positive
rational eigenvalues.

#### Template Based Methods

Another method for generating polynomial invariants is to reduce the problem
to constraint solving by supposing that the invariant takes the form of some
parameterized template, and solving for the parameters (KOJIMA201833;
ATVA:OBP16; POPL:SSM2004; SAS:CJJK2012; MULLEROLM2004; PLDI:CFGG2020;
GHMM2023). These methods have the benefit of being able to handle problems
with arbitrary control flow. Furthermore, they are often complete for
generating invariants that fit the given template. Many template methods
consider all polynomials up to some bounded degree. In such cases when the
desired polynomial is within the degree bound, template based methods have the
potential to generate invariants for general programs that our method would
theoretically miss. In contrast, our method does not require a degree bound.
Even for linear simulations, there is no bound on the degree of the invariant
our method calculates.

#### Monotone algebraic program analysis

There has been a recent line of work that uses the framework of algebraic
program analysis to develop program analyses with monotonicity guarantees
(CAV:SK2019; PLDI:ZK2021; CAV:ZK2021; POPL:KKZ2023). In particular,
POPL:KKZ2023 proposes a monotone loop summarization algorithm based on the
theory of linear integer/real rings. Our technique is complementary, in the
sense that our method computes stronger invariant polynomial equations than
(POPL:KKZ2023), but cannot synthesize invariant polynomial inequalities.

###### Acknowledgements.

We would like to thank Tom Reps for his contributions to the discussions that
lead to this paper. This work was supported, in part, by a gift from Rajiv and
Ritu Batra, a Google PhD fellowship, and by the NSF under grant number
1942537. Any opinions, findings, and conclusions or recommendations expressed
in this publication are those of the authors, and do not necessarily reflect
the views of the sponsoring entities.

## References

  * (1)
  * Afzal et al. (2019) Mohammad Afzal, A. Asia, Avriti Chauhan, Bharti Chimdyalwar, Priyanka Darke, Advaita Datar, Shrawan Kumar, and R. Venkatesh. 2019\.  VeriAbs : Verification by Abstraction and Test Generation. In _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. 1138–1141.  https://doi.org/10.1109/ASE.2019.00121
  * Amrollahi et al. (2022) Daneshvar Amrollahi, Ezio Bartocci, George Kenison, Laura Kovács, Marcel Moosbrugger, and Miroslav Stankovič. 2022.  Solving Invariant Generation for Unsolvable Loops. In _Static Analysis_ , Gagandeep Singh and Caterina Urban (Eds.). Springer Nature Switzerland, Cham, 19–43.
  * Beyer (2023) Dirk Beyer. 2023\.  Competition on Software Verification and Witness Validation: SV-COMP 2023. In _Tools and Algorithms for the Construction and Analysis of Systems_ , Sriram Sankaranarayanan and Natasha Sharygina (Eds.). Springer Nature Switzerland, Cham.
  * Buchberger (1976) B. Buchberger. 1976\.  A Theoretical Basis for the Reduction of Polynomials to Canonical Forms.  _SIGSAM Bull._ 10, 3 (Aug. 1976), 19–29.
  * Cachera et al. (2012) David Cachera, Thomas Jensen, Arnaud Jobin, and Florent Kirchner. 2012.  Inference of Polynomial Invariants for Imperative Programs: A Farewell to Gröbner Bases. In _Static Analysis_ , Antoine Miné and David Schmidt (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 58–74.
  * Chatterjee et al. (2020) Krishnendu Chatterjee, Hongfei Fu, Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady. 2020\.  Polynomial Invariant Generation for Non-Deterministic Recursive Programs. In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_ (London, UK) _(PLDI 2020)_. Association for Computing Machinery, New York, NY, USA, 672–687.  https://doi.org/10.1145/3385412.3385969
  * Cox et al. (2015) D. A. Cox, J. Little, and D. O’Shea. 2015.  _Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra_ (4th ed.).  Springer Publishing Company, Incorporated.
  * Cyphert et al. (2019) John Cyphert, Jason Breck, Zachary Kincaid, and Thomas W. Reps. 2019.  Refinement of path expressions for static analysis.  _Proc. ACM Program. Lang._ 3, POPL (2019), 45:1–45:29.  https://doi.org/10.1145/3290358
  * Everest et al. (2003) Graham Everest, Alfred J van der Poorten, Igor Shparlinski, Thomas Ward, et al. 2003\.  _Recurrence sequences_. Vol. 104.  American Mathematical Society Providence, RI.
  * Farzan and Kincaid (2015) Azadeh Farzan and Zachary Kincaid. 2015.  Compositional Recurrence Analysis. In _Proceedings of the 15th Conference on Formal Methods in Computer-Aided Design_ (Austin, Texas) _(FMCAD ’15)_. FMCAD Inc, Austin, Texas, 57–64.
  * Faugère (1999) Jean-Charles Faugère. 1999\.  A new efficient algorithm for computing Gröbner bases (F4).  _Journal of Pure and Applied Algebra_ 139, 1 (1999), 61–88.  https://doi.org/10.1016/S0022-4049(99)00005-5
  * Faugère (2010) Jean-Charles Faugère. 2010\.  FGb: A Library for Computing Gröbner Bases. In _Mathematical Software – ICMS 2010_.  https://www-polsys.lip6.fr/~jcf/FGb/index.html
  * Frohn et al. (2020) Florian Frohn, Marcel Hark, and Jürgen Giesl. 2020\.  Termination of Polynomial Loops. In _Static Analysis_ , David Pichardie and Mihaela Sighireanu (Eds.). Springer International Publishing, Cham, 89–112.
  * Ge (1993) Guoqiang Ge. 1993\.  _Algorithms Related to Multiplicative Representations of Algebraic Numbers_.  Ph. D. Dissertation. Mathematics Department, University of California at Berkeley, Berkeley, CA.
  * Goharshady et al. (2023) Amir Kafshdar Goharshady, S. Hitarth, Fatemeh Mohammadi, and Harshit Jitendra Motwani. 2023.  Algebro-Geometric Algorithms for Template-Based Synthesis of Polynomial Programs.  _Proc. ACM Program. Lang._ 7, OOPSLA1, Article 100 (apr 2023), 30 pages.  https://doi.org/10.1145/3586052
  * Heizmann et al. (2009) Matthias Heizmann, Jochen Hoenicke, and Andreas Podelski. 2009\.  Refinement of Trace Abstraction. In _Static Analysis, 16th International Symposium, SAS 2009, Los Angeles, CA, USA, August 9-11, 2009. Proceedings_ _(Lecture Notes in Computer Science, Vol. 5673)_ , Jens Palsberg and Zhendong Su (Eds.). Springer, 69–85.  https://doi.org/10.1007/978-3-642-03237-0_7
  * Hrushovski et al. (2018) Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. 2018.  Polynomial Invariants for Affine Programs. In _Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science_ (Oxford, United Kingdom) _(LICS ’18)_. Association for Computing Machinery, New York, NY, USA, 530–539.  https://doi.org/10.1145/3209108.3209142
  * Hrushovski et al. (2023) Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. 2023.  On Strongest Algebraic Program Invariants.  _J. ACM_ 70, 5, Article 29 (oct 2023), 22 pages.  https://doi.org/10.1145/3614319
  * Humenberger et al. (2018) Andreas Humenberger, Maximilian Jaroschek, and Laura Kovács. 2018.  Invariant Generation for Multi-Path Loops with Polynomial Assignments. In _Verification, Model Checking, and Abstract Interpretation_ , Isil Dillig and Jens Palsberg (Eds.). Springer International Publishing, Cham, 226–246.
  * Johansson (2017) F. Johansson. 2017\.  Arb: efficient arbitrary-precision midpoint-radius interval arithmetic.  _IEEE Trans. Comput._ 66 (2017), 1281–1292.  Issue 8. https://doi.org/10.1109/TC.2017.2690633
  * Kauers and Zimmermann (2008) Manuel Kauers and Burkhard Zimmermann. 2008.  Computing the algebraic relations of C-finite sequences and multisequences.  _Journal of Symbolic Computation_ 43, 11 (2008), 787–803.  https://doi.org/10.1016/j.jsc.2008.03.002
  * Kincaid et al. (2018) Zachary Kincaid, John Cyphert, Jason Breck, and Thomas Reps. 2018.  Non-Linear Reasoning for Invariant Synthesis.  _Proc. ACM Program. Lang._ 2, POPL, Article 54 (dec 2018), 33 pages.  https://doi.org/10.1145/3158142
  * Kincaid et al. (2023) Zachary Kincaid, Nicolas Koh, and Shaowei Zhu. 2023.  When Less Is More: Consequence-Finding in a Weak Theory of Arithmetic.  _Proc. ACM Program. Lang._ 7, POPL, Article 44 (jan 2023), 33 pages.  https://doi.org/10.1145/3571237
  * Kincaid et al. (2021) Zachary Kincaid, Thomas Reps, and John Cyphert. 2021\.  Algebraic Program Analysis. In _Computer Aided Verification_ , Alexandra Silva and K. Rustan M. Leino (Eds.). Springer International Publishing, Cham, 46–83.
  * Kojima et al. (2018) Kensuke Kojima, Minoru Kinoshita, and Kohei Suenaga. 2018\.  Generalized homogeneous polynomials for efficient template-based nonlinear invariant synthesis.  _Theoretical Computer Science_ 747 (2018), 33–47.  https://doi.org/10.1016/j.tcs.2018.06.005
  * Kovács (2008) Laura Kovács. 2008\.  Reasoning Algebraically About P-Solvable Loops. In _Tools and Algorithms for the Construction and Analysis of Systems_ , C. R. Ramakrishnan and Jakob Rehof (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 249–264.
  * Müller-Olm and Seidl (2004) Markus Müller-Olm and Helmut Seidl. 2004.  A Note on Karr’s Algorithm. In _Automata, Languages and Programming_ , Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 1016–1028.
  * Müller-Olm and Seidl (2004) Markus Müller-Olm and Helmut Seidl. 2004.  Computing polynomial program invariants.  _Inform. Process. Lett._ 91, 5 (2004), 233–244.  https://doi.org/10.1016/j.ipl.2004.05.004
  * Oliveira et al. (2016) S. De Oliveira, S. Bensalem, and V. Prevosto. 2016\.  Polynomial invariants by linear algebra.  _Lecture Notes in Computer Science_ 9938 LNCS (2016), 479–494.  https://doi.org/10.1007/978-3-319-46520-3_30 Conference of 14th International Symposium on Automated Technology for Verification and Analysis, ATVA 2016 ; Conference Date: 17 October 2016 Through 20 October 2016; Conference Code:185289.
  * Rodríguez-Carbonell and Kapur (2004) Enric Rodríguez-Carbonell and Deepak Kapur. 2004.  Automatic Generation of Polynomial Loop Invariants: Algebraic Foundations. In _Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation_ (Santander, Spain) _(ISSAC ’04)_. Association for Computing Machinery, New York, NY, USA, 266–273.  https://doi.org/10.1145/1005285.1005324
  * Rodríguez-Carbonell and Kapur (2007) E. Rodríguez-Carbonell and D. Kapur. 2007.  Generating all polynomial invariants in simple loops.  _Journal of Symbolic Computation_ 42, 4 (2007), 443–476.  https://doi.org/10.1016/j.jsc.2007.01.002
  * Sankaranarayanan et al. (2004) Sriram Sankaranarayanan, Henny B. Sipma, and Zohar Manna. 2004\.  Non-Linear Loop Invariant Generation Using GröBner Bases. In _Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (Venice, Italy) _(POPL ’04)_. Association for Computing Machinery, New York, NY, USA, 318–329.  https://doi.org/10.1145/964001.964028
  * Silverman and Kincaid (2019) Jake Silverman and Zachary Kincaid. 2019.  Loop Summarization with Rational Vector Addition Systems. In _Computer Aided Verification_ , Isil Dillig and Serdar Tasiran (Eds.). Springer International Publishing, Cham, 97–115.
  * The FLINT team (2023) The FLINT team. 2023\.  _FLINT: Fast Library for Number Theory_.  Version 2.9.0, https://flintlib.org.
  * Ulam and von Neumann (1947) S. M. Ulam and John von Neumann. 1947.  On combination of stochastic and deterministic processes.  Summer meeting of the American Mathematical Society.
  * Wendler and Beyer (2023) Philipp Wendler and Dirk Beyer. 2023.  Bench Exec 3.16.  https://github.com/sosy-lab/benchexec.
  * Zhu and Kincaid (2021a) Shaowei Zhu and Zachary Kincaid. 2021a.  Reflections on Termination of Linear Loops. In _Computer Aided Verification: 33rd International Conference, CAV 2021, Virtual Event, July 20–23, 2021, Proceedings, Part II_. Springer-Verlag, Berlin, Heidelberg, 51–74.  https://doi.org/10.1007/978-3-030-81688-9_3
  * Zhu and Kincaid (2021b) Shaowei Zhu and Zachary Kincaid. 2021b.  Termination Analysis without the Tears. In _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ (Virtual, Canada) _(PLDI 2021)_. Association for Computing Machinery, New York, NY, USA, 1296–1311.  https://doi.org/10.1145/3453483.3454110