# SeeSaw: interactive ad-hoc search over image databases

Oscar Moll<EMAIL_ADDRESS>MIT CSAIL Cambridge MA USA ,  Manuel Favela
<EMAIL_ADDRESS>MIT Cambridge MA USA ,  Sam Madden<EMAIL_ADDRESS>MIT
CSAIL USA and  Vijay Gadepally<EMAIL_ADDRESS>MIT Lincoln Laboratory USA

###### Abstract.

As image datasets become ubiquitous, the problem of ad-hoc searches over image
data is increasingly important. In particular, many tasks, such as
constructing datasets for training and testing object detectors, require
finding ad-hoc objects or scenes within large image datasets. Existing
approaches for searching image datasets rely on rigid categories or assume
fully accurate models trained on the data are available ahead of time. In
contrast, SeeSaw is a system for interactive ad-hoc searches in image datasets
that does not assume a pre-defined set of categories in advance. SeeSaw users
can start a search using text, and then provide feedback to SeeSaw in the form
of box annotations on previous results. Using this input, SeeSaw refines the
results it returns to help users locate images of interest in their data.
Behind the scenes, SeeSaw uses several optimizations to transform the user’s
feedback into better results. We evaluate SeeSaw against a state of the art
baseline that does not take advantage of user feedback and find SeeSaw can
increase search quality metrics up 4x for the harder search queries, and
significantly on almost all queries, even those where the baseline performs
well.

PVLDB Reference Format:
PVLDB, 14(1): XXX-XXX, 2023.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/orm011/seesaw.

##  1\. Introduction

Increasingly inexpensive cameras and storage make it ever easier to collect
images and video. In addition to dedicated cameras, video and images are now
captured from mobile phones, vehicle cameras and drones. At the same time,
machine learning based computer vision techniques continue improving
significantly – enabling better automation of tasks involving image content
understanding. Nevertheless, the ability of an engineer or team to explore
their own data and discover ad-hoc items of interest lags far behind their
ability to collect that data. For example: an engineer at an autonomous
vehicle company with a large repository of data may wish to find examples of
bikes in the snow to test and improve an existing bike detector; a mobile app
developer may want to develop a hot-air balloon detector as part of a new app
feature; or an ornithology expert may want to search their camera archives to
know which of all their camera locations seem to show more sightings of a
particular bird. For any of these scenarios, whether training or extending a
computer vision model on one’s own data or improving testing for an existing
model, the first step is finding at least a few tens of images within the data
that contain examples of interest. Depending on the dataset, bikes in the snow
and hot air balloons may be quite rare, perhaps appearing in only one in a
thousand images or less. In such scenarios, random sampling is unlikely to
help these users, and pre-trained object detectors are unlikely to be
available due to the rare nature of the query and to differences between the
user’s data and the data used to train existing object detectors. Existing
consumer image search tools such as Google could be helpful in principle but
are not able to carry out searches in the user’s own datasets. Other services
such as Google Photos and Apple Photos help users search their own datasets,
but are limited in the types of searches they support, and provide recourse
for users to fine-tune results when they fail.

To address these challenges, we built SeeSaw. SeeSaw comprises a graphical
search UI and server backend that enables users to carry out ad-hoc
interactive image searches within their own datasets starting from a text
query. SeeSaw does not require any data labelling ahead of time, only a pre-
processing step done once over the data to compute image embeddings. Then,
given an input query, SeeSaw uses a state of the art visual-semantic embedding
model (CLIP (Radford et al., [n.d.])) produce an initial set of images. Users
can provide SeeSaw with localized feedback about those results which SeeSaw
uses to refine query results in real-time and produce a better next batch,
which the user can provide feedback on again, etc.

SeeSaw is especially helpful for situations where state of the art approaches
like CLIP fall short for any reason: Such situations are unfortunately
inevitable and frequent in the ad-hoc search contexts we described because
each dataset is different, and each search need is different as well. Instead,
the user and SeeSaw can work in a loop to refine the search online. User
feedback in SeeSaw takes the form of box annotations around regions of
interest within images, which SeeSaw uses to adapt the next result batch to
both the user’s intentions and to the dataset. SeeSaw implements ad-hoc
searches by leveraging state of the art visual-semantic embedding models
coupled with a novel interactive improvement technique which we call
interactive concept refinement and a time-tested adaptive resolution
optimization that requires no training: pyramid representations.

Interactive concept refinement consists of incrementally improving an internal
vector SeeSaw uses to represent the ongoing query. This vector is used by
SeeSaw to index into the pre-processed images, stored internally as a feature
vector, and includes information both from strings used to describe the search
and from image examples from user feedback. The pyramid representation encodes
images as bundles of feature vectors (as opposed to a single vector). Each
vector within that bundle corresponds to a square box within its image. The
pyramid representation assembles vectors of different sizes centered at
different spatial locations within the image, allowing SeeSaw to return
results where the object of interest occupies only a small portion of the
image, as is the case in many domain-specific search tasks (e.g., snowy bikes
or birds in a forest scene.). While image-pyramid representations in general
are a well known technique, one of SeeSaw’s contributions is integrating
Interactive concept refinement with a vector pyramid representation.

In summary, the contributions of this paper are:

  1. (1)

We introduce SeeSaw, a human-in-the-loop system and interface to enable ad-hoc
searches over image data. SeeSaw leverages CLIP as a starting point and works
with users to improve results interactively without imposing onerous pre-
requisites in terms of labeled data or the availability of models pre-trained
specifically on the user’s data.

  2. (2)

We introduce vector refinement, a way to implement interactive feedback that
works well with pre-trained models such as CLIP.

  3. (3)

We design and integrate a vector pyramid representation for images, which
helps SeeSaw locate objects of interest at different scales at the cost of
increasing database size. We leverage a vector store to keep latencies
interactive and derive the payoffs.

  4. (4)

We evaluate SeeSaw in a randomized user study against a baseline system
without optimizations, showing the extra time burden on users is low, but the
gains in time and results can be large (3x) especially for rarer or more
complex situations.

  5. (5)

We demonstrate SeeSaw adds substantial value to state of the art models such
as CLIP when used for image search over several well known datasets such as
COCO, LVIS and BDD. Our benchmarks show improvements of 3.1x in NDCG score (a
retrieval metric) on cases where the model performs poorly, while not hurting
accuracy when it performs well on its own. We show substantial improvements
across all data sets.

##  2\. Visual-Semantic Embeddings

Before describing SeeSaw in detail, we introduce visual-semantic embedding
models, a special kind of embedding used as a building block for SeeSaw. A
visual-semantic embedding model consists of two models, one for a visual data
modality and one for textual modality. A visual embedding model that converts
images to vectors, and a language embedding model that converts sentences to
vectors. In a visual-semantic embedding model, the two constituent models are
jointly trained on a corpus of captioned images so that corresponding images
and captions are mapped by the image embedding and language embedding
respectively into two vectors with high cosine similarity, while non-
corresponding image, vector pairs should map to two vectors with low cosine
similarity. In this way, both images and text are mapped into a common
‘semantic’ vector space which is useful as a high-level representation. For
image search tasks, the visual part of the visual-semantic embedding can be
used without needing any text just like a pure image embedding, the text was
only used during training. The advantage now is that at query time the user
can convert their a search query string into a vector using the language
model, and use that vector to locate image vectors with a high cosine
similarity from a database. One example of an openly available state-of-the-
art visual-semantic embedding is CLIP(Radford et al., [n.d.]). CLIP is pre-
trained on a large corpora of web images and captions.

Frameworks such as (Singh et al., 2020) help users potentially build their own
embeddings. Training your own multi-modal embedding requires a captioned
corpus for training, requiring users to caption their data would impose the
kind of barrier to getting started that we want SeeSaw to avoid. Luckily, pre-
trained visual-semantic embedding on large language-image datasets from a web
crawl have been shown to have competitive predictive performance on datasets
they were not trained on (Radford et al., [n.d.]), raising the possibility
that such models could be used even in custom domains. However, (Radford et
al., [n.d.]) also find performance can lag behind domain-specific pre-trained
models, and performance can drop for other domains. Nevertheless, models such
as CLIP provide a better search starting point than random search or object
detectors, making ad-hoc searches more feasible.

Using a single model as a standalone solution suffers from multiple drawbacks.
The first three are due to model limitations and the fourth is an interface
limitation. Model limitations are that accuracy of searches using CLIP can
vary dramatically depending on the queries and datasets: some queries in some
datasets perform almost perfectly, returning mostly positive results in the
top 10, some others can perform quite poorly. The second is that search
accuracy is somewhat sensitive to the precise search terms used: language
models are not magical, and changing the wording can change the top results
even if the meaning should be about the same. The third is that models can be
somewhat sensitive to changes in object sizes across datasets. This a big deal
if image sizes also change. It is not clear ahead of time for which queries
and datasets these issues will be significant. The interface limitation is
that even if we have access to a ‘perfect’ visual-semantic embedding, a search
string is only able to capture part of what the user has in mind. The human-
in-the-loop approach embodied in SeeSaw helps users get started with their
searches immediately and address these types of problems if and when they
arise, and only for use cases important to them. In cases where model
performance alone is already high, SeeSaw does not harm result quality. In
section §5 we compare SeeSaw against a baseline built using the pre-trained
embedding alone. We now explain how SeeSaw is implemented and where visual
semantic embedding models are used within SeeSaw.

##  3\. System

SeeSaw consists of the following components: 1) a graphical user interface
(GUI), 2) a visual semantic embedding, 3) a vector store, and 4) an optimizer
layer.

Before using SeeSaw, we require a one-time pre-processing pass over the user
data. Pre-processing in SeeSaw consists of converting raw image data into
semantic feature vectors using a pre-trained visual embedding. For SeeSaw, the
runtime of this preprocessing pipeline depends on four variables: the number
of images in the dataset, the pixel sizes of the images in the dataset, the
inference cost of the embedding, and the number and type of GPUs available. On
COCO, a dataset of 120000 images, SeeSaw preprocessing in our unoptimized
single GPU pipeline took less than 3 hours.

After preprocessing, users interact with SeeSaw through the SeeSaw GUI. A user
wishing to make a model to detect hot-air balloons can begin the search
process with SeeSaw through text by typing ‘hot-air balloon’ into the search
box. SeeSaw translates this ‘hot-air balloon’ string into a semantic vector
representation $w$ suitable for lookup into a vector store holding the feature
vectors computed during preprocessing. One of SeeSaw’s contributions is its
optimizer: a layer that generates better and better $w$ as the search
progresses. We explain the optimizer in full detail in §4. Given the optimized
vector $w$ SeeSaw queries the vector store for high scoring vectors. Scoring
vectors is done via dot product: a vector $v$ in the database is considered
relevant if $w\cdot v$ is large. The vector store returns a list of high
scoring vectors, and the SeeSaw optimizer applies some modifications to this
list. The user then sees the corresponding images in the UI.

The user can continue the search by providing feedback on the results offered
so far. The flow of data for both preprocessing and interaction is show in
Figure 1.

Figure 1. SeeSaw component diagram. Top: preprocessing steps; Bottom: dataflow
during interaction loop.

The optimizer layer encapsulates the main research contributions of SeeSaw,
and we explain it in detail in §4. The remainder of this section describes the
other SeeSaw components briefly.

###  3.1. User interface

Figure 1, bottom left, shows a screenshot of the SeeSaw UI for the hot air
balloon query as one of the components of SeeSaw. The UI receives user input
in the form of text or an example image (which could be from outside the
database). The UI displays search output images, and accepts further user
feedback in the form of bounding box annotations to highlight relevant parts
of an image.

###  3.2. CLIP

SeeSaw employs CLIP(Radford et al., [n.d.]), a pre-trained visual semantic
embedding during both preprocessing and during querying. CLIP was used off-
the-shelf, without any access to the data used for the evaluation, because we
are interested in the common scenario of lacking labelled data (in this case,
lacking a set of captioned images). During pre-processing SeeSaw uses the
visual component of CLIP to convert unlabelled images into vectors. During
querying, SeeSaw uses the text component of CLIP to handle translation of
string inputs from the user.

The vectors produced by the text embedding could be used directly to query the
vector store, but SeeSaw instead inputs them to the vector optimizer, which
allows SeeSaw to improve the quality of lookups into the vector store.
Similarly, SeeSaw does not use a single-vector representation as suggested
above, instead uses a multi-vector representation described later.

###  3.3. Vector store

After data is preprocessed, the vector store provides a key-value lookup
interface. The vector store takes a vector $w$ as the key for a lookup and a
number of desired results $h$, and its outputs are $h$ vector ids for vectors
$v$ found within the database such that $w\cdot v$ are the $h$ highest. In
SeeSaw, the vectors in the store correspond to images in the dataset, but not
in a one image-to-one vector manner. Instead, as we explain in §4.2, SeeSaw
stores multiple vectors per image corresponding to different image patches at
different scales. The vector store does not need to be exact, and for the
current implementation we use the Annoy vector store (Bernhardsson, [n.d.]).

##  4\. Optimizer

The optimizer encapsulates the core contributions of SeeSaw. It integrates
interactive concept refinement and vector pyramid representation. At a high
level, interactive concept refinement enables SeeSaw to improve the quality of
results during the course of a user search by leveraging interactive user
feedback. The vector pyramid representation enables SeeSaw to greatly increase
accuracy on queries of objects that show up at different scales across images,
as well as handle images of different sizes. Both optimizations can be
deployed independently of each other, but they also can be adapted to work
well together. We explain interactive concept refinement in §4.1 and the
vector pyramid representation in §4.2.

###  4.1. Interactive concept refinement

Before describing the concept refinement optimization we first define more
clearly what we mean by concept. A concept is meant to represent a scene type,
an object type, or a situation that can be recognized by a user within an
image. For example, a hot-air balloon is a concept, and so is partially cloudy
weather, and so is a person riding a bicycle. To allow maximum flexibility in
our definition of concept we define a concept formally to simply be a subset
of images within our database. For a hot-air balloon, the concept is the set
of images containing a hot-air balloon somewhere. We will use $S$ to denote
the set of images corresponding to a concept. Note that in this discussion we
make a distinction between the concept $S$, and the text input ‘hot-air
balloon’. $S$ is the result set, while the text ‘hot-air balloon’ is just a
string we can feed into SeeSaw. We can also use the text ‘hot air balloon’
without a dash, etc. We assume the universe of images is the set of images in
the database. A user search involves SeeSaw working with the user to find
images in $S$. Concept refinement is the process of using user inputs and
feedback to find elements of $S$.

Once images are converted into vectors during preprocessing and loaded into a
vector store, we can think of the concept $S$ as a set of vectors or as a set
of images interchangeably. For the purposes of our exposition of concept
refinement in this section we will make a simplifying assumption and treat
images and feature vectors as corresponding one-to-one with each other. This
one-to-one assumption will be relaxed in section §4.2 when we explain the
vector pyramid representation that associates multiple vectors with a picture,
and we will address the system-wide changes needed then. In the following
discussion, assume all vectors are normalized to length 1.

In order to support search operationally over a database of vectors, we rely
on finding a function $F_{S}$ such that
$F_{S}(v)>F_{S}(v^{\prime})\forall(v\in S,v^{\prime}\notin S)$. The ideal
function $F_{S}$ ranks database elements so that all images in the concept set
$S$ appear before all images not in the set. SeeSaw aims to help the user
approximate $F_{S}$ interactively. In principle we could approximate $S$
better by using a complex scoring function. SeeSaw opts for assuming there is
a good linear model approximation: for every concept $S$ there exists some
vector $w^{*}$ such that for all $v$ in the database, $F_{S}(v)\approx
w^{*}\cdot v$. We can think of this vector $w^{*}$ as a weighting of embedding
features, as a linear classifier without the bias term (since we only care
about relative ordering) or even as an archetype of elements of $S$ because it
exists in the same vector space as the database elements. Operationally, all
interpretations of $w^{*}$ mean we can make use of vector stores such as
(Bernhardsson, [n.d.]), which enable us to approximately find vectors $v$
within the database such that $w^{*}\cdot v$ is large, without requiring a
full database scan. This is important because SeeSaw has no access to the true
$w^{*}$, instead SeeSaw refines an estimate $w$ of $w^{*}$ and this
interactive refinement requires multiple look-ups into the database within a
single user search session.

So, for a given concept $S$, we want to find $w$ such $w\cdot v$ is largest
for $v\in S$ and lowest for $v^{\prime}\notin S$. We would like in fact for
$w\cdot v>w\cdot v^{\prime}\forall v\in S,\forall v^{\prime}\notin S$ but this
ideal vector is not guaranteed to exist: it depends on both the quality of the
vector representation (which depends on the pre-trained embedding model) and
the distribution of elements concept $S$ within the database, as well as the
distribution of its complement set. However, some $w$’s will be better than
others. For instance, there is always at least some $w$ that minimizes the
number of out-of-order pairs in the sort order implied by scores. This number
is given by the function:

(1) $L_{\mathrm{inversions}}(w)=\sum_{(v\in S,v^{\prime}\notin S)}\llbracket
w\cdot v\leq w\cdot v^{\prime}\rrbracket$

where $\llbracket\rrbracket$ is an indicator function with value 0 when the
enclosed condition is false and value 1 when it holds true. For a given $S$,
SeeSaw helps the user approximate $w$ by allowing them to provide string
descriptions, image hints, and interactive feedback from previous results. The
process of improving $w$ interactively is what we call interactive concept
refinement and one of the main objectives of the optimizer layer in SeeSaw. We
now introduce the techniques SeeSaw provides for interactive concept
refinement.

####  4.1.1. Estimating $w^{*}$

In principle, given a random sample of labeled vectors from the database we
could estimate $w^{*}$ much like learning a linear classifier. We can use many
continuous loss functions to approximate the number of order-inversions of
Equation 1 (which has a discontinuity at 0); for SeeSaw we used a hinge-loss
based function as in (Joachims, 2002):

(2) $L(w)=\sum_{v\in S,v^{\prime}\notin S}\mathrm{relu}(wv^{\prime}-wv)$

Where $\mathrm{relu}$ is the rectified linear function and
$\mathrm{relu}(wv^{\prime}-wv)$ is a hinge loss approximating the inversion
indicator function used in Equation 1: $\llbracket wv^{\prime}\geq
wv\rrbracket=\llbracket wv^{\prime}-wv\geq 0\rrbracket$.

We can minimize $L$ to find an estimate $\hat{w}$:

(3) $\hat{w}=\operatorname*{arg\,min}_{w}L(w)$

The formulation of Equation 3 using loss Equation 2 can only be used directly
with a sample containing at least one labeled positive and one labeled
negative example. However, in SeeSaw we do not have any examples at the start,
and finding the first positive example is itself not expected to happen within
several tens of pictures if we use random sampling: the cases for which search
is most useful are those for which examples occur rarely in the database,
those for which random sampling would not work very well. For example, in our
evaluation we include some classes with examples appearing in 1/1000 of the
images. We want SeeSaw to be useful even when concepts do not appear often in
the data.

####  4.1.2. Finding the first positive example

SeeSaw lets users start their searches with a string description of what they
are looking for. SeeSaw relies on the pre-trained visual semantic embedding
model to map the search string into a vector $w_{s}$. $w_{s}$ is used as an
initial approximation of $w^{*}$ and SeeSaw queries the vector database with
it. The quality of $w_{s}$ as an approximation of $w^{*}$ depends on several
factors: the embedding model, the dataset, the exact string $s$ used to make
the query (‘hot-air balloon’ vs ‘hot air balloon’ without a dash). In our
experiments we find using $w_{s}$ is generally better or than random sampling
even though the visual-semantic embedding was not trained on the datasets used
in the evaluation.

####  4.1.3. Finding the second positive example

Suppose the user looking for hot-air balloons and searches with string ‘hot-
air balloon’, the string is converted to a vector $w_{s}$ by the visual
semantic embedding and matched against the vector store. The top 20 results
include 1 image with a hot-air balloon with vector $u$ in it and 19 without
it. There are less than 5 hot-air balloons in the dataset per 1000 images
(something the user does not know) so $w_{s}$ was already much more effective
than random sampling. The user provides feedback about this positive example
to SeeSaw by marking the hot-air balloon image as a positive. The rest are
marked negative.

How should SeeSaw search for the next 10 results? SeeSaw could ignore the
feedback and query the vector store with $w_{s}$ again. After all, $w_{s}$
already worked once. Alternatively, SeeSaw could use the example $u$ as a
query vector now. Alternatively, SeeSaw could use both the positive and
negative examples from this first round to generate a third option $\hat{w}$
by solving the optimization problem in Equation 3 with vectors from this first
batch of results. The right choice depends on which is more accurate, which we
do not know ahead of time.

Empirical results in (Radford et al., [n.d.]) and elsewhere, and also in the
datasets used in our evaluation show linear models trained on even just one or
two positive examples can achieve high accuracy (compared to random). This
suggests $\hat{w}$ is a good candidate to use despite a small number of
training examples. However, switching from $w_{s}$ to $\hat{w}$ after we find
our first result can result in large accuracy drops on subsequent rounds
because while the accuracy of $\hat{w}$ increases quickly as we observe more
examples, the accuracy of $w_{s}$ can be already quite high at the start.

SeeSaw approaches this dilemma with the following principle: 1) we improve $w$
iteratively using gradient descent steps guided by the loss function of
Equation 3 2) we incorporate prior information such as the string hint $w_{s}$
as a starting value in our iterative update. A gradient descent step is
defined as:

(4) ${\small w^{\prime}=w-\eta\nabla_{w}L}$

Where $\eta$ is a learning rate hyper-parameter which we will address later
on. To apply a gradient step we require a starting $w$. For a convex function
of $w$ (which the loss $L$ defined in Equation 2 is) this point can be picked
at random and the algorithm will eventually converge to the optimum. In
SeeSaw, we will use $w_{s}$ not only to find the first examples, but also as
our starting point for taking gradient steps, treating $w_{s}$ as a good
starting guess. This choice does not affect the eventual convergence but in
cases where $w_{s}$ is better than random we start the search closer to the
optimum. We should note that in practice we expect SeeSaw users to care most
about whether SeeSaw improves results within the first handful of iterations,
so the eventual convergence is not the main goal. In our evaluation we only
consider the first 10 iterations of the update algorithm and we find this
update rule shows substantial improvements to the quality of results compared
to using only $w_{s}$ even within that short number of steps.

We can derive an explicit update rule for $w$ by applying the definition of
gradient to the loss $L$ from Equation 2 with respect to $w$, which yields:

${\small\nabla_{w}L=\sum_{v\in S,v^{\prime}\notin S}\llbracket
w^{\top}v^{\prime}\geq w^{\top}v\rrbracket(v^{\prime}-v)}$

Where $\llbracket\rrbracket$ is an indicator function as explained before.
Using that formula we can rewrite the gradient step to:

(5) $\begin{split}\small w^{\prime}&=w-\eta\sum_{v\in S,v^{\prime}\notin
S}\llbracket wv^{\prime}\geq wv\rrbracket(v^{\prime}-v)\\\ &=w+\sum_{v\in
S}\eta\lvert\\{v^{\prime}|v^{\prime}\geq_{w}v\\}\rvert\cdot
v-\sum_{v^{\prime}\notin S}\eta\lvert\\{v|v^{\prime}\geq_{w}v\\}\rvert\cdot
v^{\prime}\end{split}$

$\lvert\\{v^{\prime}|v^{\prime}\geq_{w}v\\}\rvert$ is the number of negative
vectors $v^{\prime}$ appearing higher in the ranking than the positive vector
$v$. This update rule has two intuitively desirable properties: 1) the updated
vector $w^{\prime}$ is a weighted sum of the previous query vector $w$ and the
observations so far. The new vector $w^{\prime}$ moves closer to observed
positive examples $v$ and away from the negative ones $v^{\prime}$. The
relative weights of each example in this sum are based on the amount of error
in the current ranking quantified by the number of mis-ranked examples
relative to each vector. When the initial search vector $w_{s}$ turns out to
be a good approximation for our concept $S$, $w$ will not change much. When
SeeSaw finds a positive example $v$ buried late in the results, SeeSaw gives
that example a higher weight making the value of the next $w$ be more similar
to $v$ than if it were placed earlier in the results.

Now we move on to our choice for hyper-parameter $\eta$. We tuned $\eta$ to a
value of 0.005, and we normalize the vectors $v$ and $w_{s}$ to unit length.
Intuitively we know low $\eta$ results in very little change on each iteration
(performing much like $w_{s}$), while a high $\eta$ results in quickly
forgetting the original $w_{s}$. We do not propose a theoretically justified
method of setting this parameter even with a fixed $\eta$ picked once, the
loss derived weights of Equation 5 adapt naturally to the data and the initial
guess.

By integrating both the initial guess from the visual semantic embedding and
user feedback SeeSaw results are consistently higher in quality than either
using only the visual semantic embedding or using only a trained model based
on feedback. We now move on to the pyramid representation optimizations in
SeeSaw.

###  4.2. Vector pyramid representation

In this section we describe the vector pyramid representation, the second
important optimization in SeeSaw. By pyramid representation we refer to the
way we represent images in the system: instead of using a single vector per
image, we represent an image with multiple vectors, where each vector
corresponds to features extracted at different spatial locations within the
image and at a range of different size scales. Pyramid representation causes
cross-cutting changes in SeeSaw: it affects not only preprocessing but also
the processing of queries and results, and it enables SeeSaw to take advantage
of finer grained user feedback through the UI, such as box annotations around
regions of interest.

The motivation for this pyramid representation is that state of the art
convolutional models are sensitive to pixel sizes of objects within images.
During training, most convolutional models learn to recognize objects of a
given range of pixel sizes within images of a given pixel size. For example,
ImageNet pre-trained feature extractors typically train on square images of
size 224x224. The CLIP image-text embedding itself is trained on 224x224
images as well (plus captions). ImageNet images contain objects that fit
neatly within that 224x224 box, and which are not much smaller than their
containing image. Changes in these statistical properties affect feature
extractors: a small decrease in the relative size of objects within that
224x224 pixel window, even if the dataset is otherwise the same, is known to
affect ImageNet classifier accuracy (Touvron et al., 2019). Size decreases are
not the only potential problem; for examples (Chin et al., [n.d.]) points out
that for object detectors sometimes it is better to decrease input image size
prior to running a pre-trained model, i.e., larger images are not always
better.

For datasets in the wild, object sizes and image sizes vary drastically. For
example, among the datasets we use in our evaluation, images in the BDD
dataset are around 800x1200 pixels. Some objects interest only span a less
than 100 pixels, such as dogs, while objects such as Trucks can take almost
the full frame. Without requiring annotations ahead of time, SeeSaw does not
have a way to know the sizes of objects that will be queried, The pyramid
representation is a scale agnostic preprocessing and query processing
strategy, and SeeSaw uses this principle to be able to work on ad-hoc queries
over different datasets. We explain how we compute the pyramid representation
next in §4.2.1, and then in §4.3 explain how the optimizer integrates with it.

####  4.2.1. Preprocessing

During preprocessing we aim to extract multiple feature vectors at different
zoom levels from the same image. Figure 1 on the center top shows an
illustration of pyramid preprocessing. SeeSaw generates a vector for each
square ‘patch’ within the image defined by the grid we mentioned above. The
intuitive benefits of such a representation are that the vector store includes
vectors for patches of different sizes and centered on different points within
a single image. The intuitive motivation is that for any arbitrary logical
region of an image that turns out to be of user interest during a search,
there is at least one patch within the database with a good overlap with the
region. For example, the image in Figure 1 shows patches containing a clock as
well as a pig. These different patches will score more highly when searching
for a clock or a pig respectively than the full image with both objects
appearing far less prominently.

The preprocessing algorithm for a single image consists of a downscaling and a
tiling stage: In the downscaling stage, given an input image $I_{0}$ of size
$W\times H$ we generate a sequence of images $I_{0},I_{1},...$ by downscaling
each by a factor $r<1$ (for example $r=1/2$) successively. This type of image
sequence is known as an image pyramid(Adelson et al., 1983). $I_{1}$ has size
$rW\times rH$, $I_{k}$ has size $r^{k}W\times r^{k}H$. For SeeSaw, we stop the
sequence when the shorter side of $I$ reaches a minimum size $z$. The exact
minimum size limit depends on what the embedding can handle (which depends on
how it was trained). We use size $z=224$ because CLIP expects images of that
size. For our evaluation we use $r=1/2$ but it is possible a larger $r$ could
be a better choice.

For the tiling stage each image in the pyramid $I_{0},I_{1},\dots$ is
logically divided into tiles of size $z\times z$ and each tile is then mapped
to a vector using the embedding model. Instead of disjoint tiles we use a
strided tile pattern to have partial overlap between tiles: the next tile of
size $z$ starts at offset $z/2$ from the start the previous tile.

When tiled in this manner, each element of the pyramid generates multiple
vectors and each vector corresponds to a 224x224 tile in their respective
image $I_{i}$. This tile in $I_{i}$ logically corresponds to a larger tile of
side $224/r^{i}$ in the original image $I_{0}$. For each vector generated in
this stage we store the vector’s corresponding box metadata
$(x_{1},y_{1},x_{2},y_{2})$ in pixel coordinates with respect to $I_{0}$. This
box metadata will be helpful later on during query processing to understand
the relations between vectors on the same image.

An image of size $W\times H$ maps to approximately
$\frac{W}{z/2}\times\frac{H}{z/2}$ vectors after tiling. Because of the
multiplicative size decrease going from $I_{i}$ to $I_{i+1}$, for
$r<\sqrt{1/2}$ more than half of the vectors will come from patches in
$I_{0}$. We will refer to $I_{0}$ as the base or base level of the pyramid, as
it employs a larger image and produces the most vectors (much like the base of
a pyramid is the widest part). We will refer to the last $I_{k}$ in the
sequence as the top or top level of the pyramid. A 1200x800 pixel image maps
to around 100 vectors. As mentioned in §3, pyramid preprocessing for the 120k
image COCO dataset on an unoptimized 1-GPU pipeline takes less than 2 hours.
In our evaluation we find this overhead is compensated for in result quality.
We also note that the user can ultimately change the $r$ parameter, and could
decide to skip the lowest pyramid level if one is only interested in larger
areas. In principle, extra levels can also be added over time if desired.

We have described how preprocessing works in SeeSaw to generate the pyramid
feature representation, but changing this representation also involves
changing how we process queries, which we explain next.

###  4.3. Integrating vector pyramid with optimizer

This section explains how we integrate the pyramid representation computed
during pre-processing into the optimizer at query time. Upon receiving a user
string query to start a search, SeeSaw converts that query into an initial
query vector $w_{s}$ using the visual-semantic embedding. SeeSaw uses $w_{s}$
as a key to the vector store, and obtains a list of the top-$l$ vector ids
(those for which $w\cdot v$ is maximized). Unlike before, these vector ids no
longer correspond one-to-one with images. Instead, they correspond to
individual vectors within the pyramid representation of images. The most
immediate approach to convert a rank of vectors into a rank of images is to
rank image ids based on the maximum score from among all of the vectors in its
pyramid. This approach makes some intuitive sense because we want to return
results even if they do not occupy a large area within the images we are
searching: in those cases, we expect only some parts of the image will have
high scores while the unrelated parts of the image may not, and that should
not affect the overall score. This approach can be implemented using the
vector store to retrieve $l$ results, with $l$ large enough so that there are
vectors for at least $k$ different images. Then, we group these $l$ scores by
image and find the $\max$ per image. Indeed, we find that this strategy helps
improve quality for many queries. Unfortunately, we find this strategy also
hurts accuracy for many queries. The reason for this unexpected drop is that
max-scoring the pyramid representation increases scores for positives, but
also creates an increase in high-scoring negatives: the maximum numerical
scores for any lookup key $w$ tends to increase at the base level of the
pyramid regardless of actual relevance. There are multiple ‘failure modes’ we
notice in the data that explain this phenomenon, including:

:

Meaningless patches at base of the pyramid: or example the center top of
Figure 1 shows three base level patches for an image. Two of them include
recognizable objects but one includes a piece of wall. Such patches are hard
for humans to interpret without context, and seem to also be hard for the
embedding to interpret correctly.

:

‘Lookalike’ patches: shapes resembling objects being queried for that however
are clearly not the objects (for a human). Examples of these include parts of
wooden sticks being confused for baseball-bats, for example a patch with only
the leg of a wooden chair. We use these observations to address the accuracy
drop in the next section.

####  4.3.1. Multiscale averaging

How can we separate the good patch results from this type of noise we added?
SeeSaw addresses this problem by leveraging the redundancy built into the
pyramid patch scheme and using it to re-score each image. We find these hard-
negatives for many queries tend to score low when we score at them at
different scales, but happen to score high at the base scale of the pyramid.
In contrast, true positives for many queries tend to be more stable in scores
across at least a few of the scales. We leverage this empirical observation to
implement a type of multi-scale averaging: each of the $l$ vectors in the list
from the vector store corresponds to a patch in an image. Within a single
pyramid representation, for any given patch in the database there are multiple
overlapping patches at different scales that also have a view of a similar
area. We can use these other patches to judge the reliability of the vector
score. For each vector $v$ in the shortlist we retrieve other vectors from the
database purely based on the spatial overlap with $v$. In our current
implementation we use the box metadata for each vector to compute the list of
other vectors that maximally overlap with $v$ when measured using the
intersection over union of their corresponding boxes, and then we average the
scores of these overlapping vectors for the same $w$. Note that these
overlapping vectors need not be in the $l$ element shortlist. This new
adjusted score is used to re-rank the images we show the user: we show the $k$
images with the top adjusted scores. Because we rely on the re-ranking to move
hard-negatives to the bottom of the list and to surface $k$ positives, we want
$l$ to be multiple times larger. Currently we set $l=10\times k$. We find
multiscale averaging followed by reranking results helps improve accuracy for
most queries, including queries for small and for large types of objects.

####  4.3.2. Fine-grained feedback and refinement with a vector pyramid
representation

The pyramid representation also affects the way users provide feedback and the
way SeeSaw takes advantage of it. When SeeSaw shows a list of $k$ images to a
user, the user marks specific regions of interest within the image as positive
using a drawing tool built into the UI. SeeSaw integrates this fine grained
feedback by mapping back from user drawn regions onto all those vectors in the
multi-vector representation that correspond to high-overlap (high IoU) patches
(recall each vector in the multi-vector representation was computed from a
box-shaped region of the image, and that SeeSaw records this region for each
vector). Those vectors can be used as ‘positive’ examples for the refinement
introduced in §4.1, while zero overlap vectors are used as negatives.
Currently, SeeSaw uses vectors with high overlap with the marked region, and
whenever more than one vector from a given zoom level would qualify, we pick
the vector with the highest overlap.

Incidentally, because the search process could return more than one vector
(but at least one), this search process also provides a type of training-time
augmentation. Unlike typical augmentation techniques, this augmentation occurs
at low runtime cost, because all vectors have been pre-computed.

##  5\. Evaluation

The goal of our evaluation is threefold. The first goal is to demonstrate that
SeeSaw delivers high quality results across queries from very different
datasets spanning web images, aerial/overhead imagery, and vehicle camera
imagery and queries of many types of objects and scenes, including relatively
rare situations (§5.2). Second, we want to see how well real users can use
SeeSaw to perform image search (§5.3). Finally, our third goal is to break
down the contributions of the interactive refinement and pyramid
representation optimizations to SeeSaw performance (§5.4).

For the first goal, we simulate a SeeSaw interaction with user box annotations
for more than a thousand different queries and compare SeeSaw results against
a non-interactive baseline using a state of the art visual semantic embedding
(CLIP)(Radford et al., [n.d.]) on its own. Then, in in §5.3 we perform
experiments with real users searching with SeeSaw, in versions with and
without the refinement and pyramid optimizations.

###  5.1. Experimental Setup

In this section we summarize the datasets and metrics we use in our
experiments.

####  5.1.1. Datasets

We evaluated SeeSaw on the following 5 datasets:

BDD(Yu et al., 2018):

image frames from a vehicle mounted video camera dataset collected from
multiple cities and highways. It includes object annotations for about 12
objects. Frames are of size 1280x720. In addition to object labels, BDD
includes global scene attribute labels such as weather (‘cloudy’, ‘snowy’)
location (‘highway’, ‘city’, ‘tunnel’, ‘parking lot’) etc. These extend the
total number of queries that can be evaluated to around 30 categories. Some
objects such as bikes and motorcycles occupy only small pixel areas around 50
pixels in size. Some queries include finer grained attributes, such as ‘yellow
traffic light’ or ‘person riding bike’.

COCO(Lin et al., 2014):

a well known object detection dataset, used to train and evaluate state of the
art object detectors. COCO includes annotations for 80 classes of objects
including indoors and outdoor scenes. Images in COCO were originally pictures
collected from Flickr, and so their content, image sizes and aspect ratios
vary within the dataset, but most are in the 600-800 pixel range.

LVIS(Gupta et al., 2019):

shares the same underlying image set as COCO, but with a highly enriched label
set, including labels for a long tail of 1200 classes of objects not present
in the original COCO dataset. Most of these classes are much more rare and
specific, but not exhaustively labelled.

ObjectNet(Barbu et al., 2019):

an object classification dataset with 300 different categories of objects
taken deliberately in non-standard angles and backgrounds. Raw images vary in
size but the provided labels apply only to the 224x224 centered crop of the
image, so we use only that part of the image.

The datasets were chosen to show a range of domains: vehicle dashcam video
frames, web images and non-standard images. Additionally, objects in the
datasets range in how common they are. LVIS includes classes that appear only
up to a handful times in the dataset, so are only present in about .5% of
their labelled images and helps evaluate very ad-hoc searches that would be
hard to think of ahead of time. BDD includes images relevant to the autonomous
vehicle space. BDD images are different from COCO in that they are not taken
by a photographer biased to focus and center a specific object within the
scene. BDD also includes a lot more complex scenes: frames are relatively
large, and there are many instances of objects of different sizes on each
image. BDD also includes ‘full scene’ categories which are not just a type of
object.

We evaluate each dataset separately as its own database. Because of the large
number of categories they label, the LVIS dataset is not exhaustively
labelled. For each of the 1200 classes LVIS provides instead an explicitly
enumerated subset of images within the dataset where the class is either
labelled or confirmed to not be present. Each of these tends to be of around
1000-2000 images. For each of those classes we run a separate evaluation
limited to there corresponding subset of the LVIS image set.

##### Preprocessing:

We ran the SeeSaw preprocessing pipeline on each dataset, with the largest
datasets taking under 2 hours on a 2 Volta GPU machine. The largest vector
database (BDD) comes to 30GB, and about 100 vectors per image (due to the
relatively high resolution of the images), COCO sits in the middle, and
ObjectNet being an image classification dataset by design uses 1 vector per
image (because image dimensions are 224 x 224).

####  5.1.2. Benchmark

SeeSaw is meant to be an interactive system where a user begins a search with
a text string. Then, SeeSaw returns an initial batch of results of a
configurable length (we use size 10 in our experiments). Following that, the
user provides feedback on the results by marking those which are correct by
drawing boxes around the relevant results. The system uses the information
provided thus far to produce a new batch of results for the user to inspect.
For our evaluation we simulate this human-system loop by using human
annotations of the datasets introduced in §5.1.1. For the initial search
string we generally use the category names from each dataset. For the BDD
dataset we change category names such as ‘motor’ to a more appropriate textual
description: ‘motorcycle’. For LVIS and ObjectNet with 1200 and 300 categories
respectively, we programmatically change category names so that the
parenthesis and slashes are replaced with spaces. We apply some adjective
reordering as well, for example the category ‘book (closed)’ gets converted to
‘closed book’ for querying SeeSaw, ‘eraser (white board)’ is queried as ‘white
board eraser’, ‘tablet/ipad’ is queried as ‘tablet or iPad’. The full list of
modifications is provided with the source code.

For each query we simulate a loop with 10 search iterations, each showing 10
image results. SeeSaw does not repeat results, so this results in 100
different results for each query. The first iteration follows the initial
string search, the following 9 iterations include feedback on all the previous
batches. We use dataset provided bounding boxes to simulate user box feedback.
There are multiple ways to measure the quality of this sequence of 100 images,
which we explain in the next section.

####  5.1.3. Metric

We want the ranking metric to be sensitive to the ordering in which objects
appear in the results because we expect users may want to stop early, and
also, we presume users are less likely to continue searching if all initial
results are negative. A simple metric would just be to count the raw number of
positive results, $N$, but this lacks this order sensitivity property. The
closely related metric (for a fixed $k$) Precision@k simply divides $N$ by
$k$. This change by itself does not provide order sensitivity, and creates a
second problem. Categories such as hot-air balloon which only have a handful
of positive results (5 in total) will never score more than 5% Precision@k
even for a method that returns the 5 hot-air balloons in the dataset as the
top 5 results. One way to avoid this problem (and to add order sensitivity) is
to switch to the more complex metric AveragePrecision@k(Manning et al., 2008)
which averages the precision values at different points in the 100 results
(corresponding to points with a positive result), stopping the calculation at
100 results. Our hypothetical method that returns the five hot-air balloons as
the top 5 results would score an average precision of 1 because precision at
each recall point was 1. However AveragePrecision@k presents a new dilemma
when handling a different method that returns 4 hot-air balloons as the top 4
results and none after: how should the missing hot-air balloon affect the
score so that we can compare the two methods? If we ignore it and simply
average existing recall points (the first 4 results), we still get an average
precision of $4*1./4=1$, which would be misleading. If we consider the missing
example a complete miss, and give it a precision of 0, we get an average
precision of $(4\times 1.+1\times 0.)/5=.8$. This score seems reasonable, but
has other problems. If we apply this metric to a more common category such as
bikes for which there are say 200 positive results we will find that a method
with 100 positive results at the top 100 has AveragePrecision@100 using this
definition would be .5, which would also be quite misleading, since that
ranking is the best we could hope for if we only return 100 results.
NDCG(Manning et al., 2008) (normalized cumulative discounted gain) is an
commonly used metric in the information retrieval community that hat helps
address these dilemmas.

NDCG is defined in terms of DCG explained below and a normalization constant.
DCG is the weighted sum:

$\mathrm{DCG}(k)=\sum_{i=1}^{k}\frac{\mathrm{rel}_{i}}{\log_{2}{(i+1)}}$

Here, $\mathrm{rel}_{i}$ is 1 or 0 in our experiments, depending on whether
the result contains a relevant object or not. The denominator
$\log_{2}{(i+1)}$ is an increasing discount that weights earlier results
higher. The normalized $\mathrm{DCG}$, or $\mathrm{NDCG}$ is the above DCG
score divided by the score for the best possible ranking for that dataset and
the number of results shown to the user $k=100$ (i.e., the best possible DCG
score an oracle could obtain). The NDCG score is 1 for the hot-air balloon
example in the case of the top 5 images being the 5 hot-air balloons, and
would be slightly somewhere above .8 (later results are weighted less) if only
4 hot-air balloons. NDCG is 1 in the bike example when the top 100 results are
bikes. An NDCG score for a result list is 1 if and only if the dataset cannot
possibly be ranked better within those 100 results, and an NDCG score is 0 if
and only if there are no positives in the top 100 results. An NDCG score of .5
could be due to the total number of positives found being smaller the maximum
or the locations of positives not being first in the ranking. In our
evaluation we use scikit-learn’s (Pedregosa et al., 2011) implementation of
NDCG.

The normalization step in NDCG helps us handle situations where either the
number of true positive results is very low or very large compared to the
number of shown results, and lets us better compare across methods that return
different total numbers of results in the top $k$ across methods and across
different queries.

####  5.1.4. Baseline

To our knowledge there is currently no system offering the type of interface
we describe for image search that we can use as a baseline. Our baseline for
evaluation is to process the search using the same high quality pre-trained
visual semantic embedding (CLIP) used in SeeSaw to obtain 100 results without
user feedback or pyramid representation. Re-scaling and center-cropping images
to fit in a 224x224 box is one way to create a one-image-one-vector
representation. We found that some images are more of a rectangle than a
square, so the cropping sometimes leaves some objects out completely. We did
not want this cropping to affect result metrics, so we modify this process
slightly to cope with rectangular images. After the initial re-scaling the
shortest side has length 224, and we stride along the long side so that we
cover it. We normalize and average these few vectors into a single vector (we
normalize before averaging to avoid extraneous length differences affecting
scores). This baseline performs better in practice than the rescale-and-crop
one, and ensures any differences in results are not due to objects being
cropped out.

###  5.2. Evaluation with Simulated Interaction

In this section we compare the baseline NDCG score with the SeeSaw NDCG score
across all queries. Our goal is to quantify SeeSaw search performance in both
an absolute and relative way. After running the experiment described in §5.1.2
for each query for both SeeSaw and the baseline, and computing NDCG as
described in §5.1.3, we plot a point for every query in our benchmark in
Figure 2. The $x$-coordinate corresponds to the NDCG score of the baseline and
the $y$-coordinate corresponds to the ratio
$\mathrm{NDCG}_{\mathrm{SeeSaw}}/\mathrm{NDCG}_{\mathrm{baseline}}$,
representing the improvement of SeeSaw over the baseline. We use log-scale for
both axes to manage the high variation in the $y$-axis.

Figure 2. Relative NDCG improvement with SeeSaw vs. baseline for each query in
our evaluation. Each point corresponds to a query. The $x$-axis encodes
baseline NDCG and the $y$-axis encodes
$\mathrm{NDCG}_{\mathrm{SeeSaw}}/\mathrm{NDCG}_{\mathrm{baseline}}$.
Horizontal dashed lines separate the three areas where
$\mathrm{NDCG}_{\mathrm{SeeSaw}}$ is better (top), about the same (within 10%
of $y=1$), or worse than $\mathrm{NDCG}_{\mathrm{baseline}}$ (bottom).
Vertical dashed lines separate areas where baseline NDC G is low (left),
medium (center) or high (right) initially. A baseline performance of $x$
bounds the maximum possible
$\mathrm{NDCG}_{\mathrm{SeeSaw}}/\mathrm{NDCG}_{\mathrm{baseline}}$ value to
$y=1/x$, which we display as a solid diagonal.

A scatter point with $y>1$ means SeeSaw delivered a better NDCG score than the
baseline. Conversely, a scatter point below the $y=1$ line means the baseline
performed better. We draw two horizontal dashed lines, one at $y=1.1$ and one
at $y=.9$ to separate the plot into three horizontal regions: one for queries
where SeeSaw performs better, one for queries where SeeSaw performs about
equally well as the baseline and one where SeeSaw does not perform as well.
Figure 2 visually shows that the overwhelming majority of queries show
improved performance with SeeSaw. We show the actual counts broken down by
dataset in Table 1. Table 1 shows out of around 1640 queries, only 40 queries
decrease in performance. These queries are spread across the datasets. In
every dataset the majority of queries either improved or remained the same.
Two of the datasets show no negatively affected queries. ObjectNet shows the
most queries remaining the same (relative to improved); part of the reason is
that the Pyramid Representation in ObjectNet is not used (all images are
already centered and cropped at 224x224). We break down the impact of the
different optimization in the next section §5.4.

| better | same | worse | total
---|---|---|---|---
dataset |  |  |  |
bdd | 13 | 13 | 3 | 29
coco | 23 | 57 | 0 | 80
lvis | 764 | 405 | 33 | 1202
objectnet | 226 | 84 | 3 | 313
total | 1026 | 559 | 39 | 1624
Table 1. Relative change in NDCG relative to the baseline (CLIP) for each
query in each dataset. ‘better’ means the NDCG increased for a category by a
factor of 1.1 or more and ‘worse’ means it decreased by a factor .9 or less.
SeeSaw rarely decreases search result accuracy, and overwhelmingly improves it
across each dataset.

The previous analysis quantified the number of queries that improve, but not
the magnitude of the improvement, which we discuss next. Figure 2 shows the
improvement ratio can exceed 10x on the top left side. The maximum observed
improvement decreases toward the right. The curve $y=1/x$ in Figure 2,
appearing as a straight line due to log-log scale, marks the upper bound for
possible relative increase in NDCG: if the baseline NDCG is .3 for example,
the maximum relative improvement possible is 3.3. The datasets used to
evaluate SeeSaw include many queries for which the baseline already performs
at levels above .3. SeeSaw’s goal is to help more easily conduct their
searches even when the pre-trained embedding model performs poorly initially
on their data without negatively impacting results when the pre-trained model
already performs well (we do not know which queries will perform well ahead of
time). In order to quantify improvements for these different scenarios, we
logically partition the $x$-axis into three vertical regions: those where the
baseline NDCG is less than .1, those where it is above .3, and those in
between. The areas correspond to ‘low’, ‘high’, and ‘medium’ baseline
performance on the query. Figure 2 shows the average improvement clearly
depends on this variable, and we quantify the average change in NDCG for each
region separately. For each of these vertical regions we average the NDCG
scores across all queries and all datasets that fall within the region. We
give each dataset equal overall weight in this aggregation, as otherwise LVIS
and ObjectNet datasets with 1200 queries and 300 queries respectively would
dominate the calculation.

Table 2 shows these average NDCG aggregate. The table also shows the number of
queries in each partition. The majority of queries have high NDCG scores, but
because we evaluate over 1500 queries, there are still more than 330 queries
represented in the low and medium baseline NDCG areas. Table 2 shows that for
those queries SeeSaw improves scores by 3.2 and 2.3 times respectively. For
the queries with high initial NDCG we still increase NDCG scores substantially
by 17%. Crucially, we do not worsen query results, as a result of the
optimizations described in §4 that take special care not to worsen performance
when the visual semantic model works well. Finally, we highlight how Figure 2
shows that a number of queries reach an NDCG close to the maximum possible.

Now we move on to breaking down the relative contributions of the two SeeSaw
optimizations.

baseline NDCG | low | medium | high
---|---|---|---
(# queries) | (86) | (250) | (1303)
CLIP | .05 | .18 | .72
this work | .15 | .41 | .84
ratio | 3.22 | 2.33 | 1.16
Table 2. Search result accuracy (measured as NDCG) for SeeSaw vs. the baseline
implementation. From left to right, each column restricts the evaluation to a
subset of queries based on their baseline performance: low means the baseline
score was less than .1, and high means the baseline score was greater than .3.
SeeSaw offers large NDCG gains on every slice, with the largest gains on those
queries for which the model fares poorly, while still improving scores
substantially for queries that score high initially.

###  5.3. User Study

The previous section showed that SeeSaw is able to substantially improve the
rate at which relevant objects are found versus a baseline that does not
receive feedback. We now present the results of our user study where we
evaluate how effective SeeSaw is when real users use our interface to perform
search. There are four goals for this user study:

  1. (1)

Measure the end-to-end time required to complete several example search tasks
using SeeSaw with real users providing feedback, which can be noisy.

  2. (2)

On the BDD dataset, demonstrate SeeSaw effectiveness on hard queries outside
the limited categories of BDD ground-truth data.

  3. (3)

Compare the extra time cost of providing box feedback and the time cost when
providing no feedback.

For this evaluation we picked 8 queries over the different datasets and
instructed users to conduct these searches. To carry out their searches, Users
were randomly assigned either to use SeeSaw or to use the baseline: a
stripped-down version of SeeSaw with the same UI, but without requiring or
allowing box annotations from them, and without the optimizations from the
SeeSaw back-end (§4). In either system users move through returned images
using the same keyboard controls. In the control version (the baseline), they
can mark a whole image as relevant without drawing a box around it, unlike
with SeeSaw.

We recruited 22 users for this study; 10 were research from our university,
which we trained and instructed verbally in person. The 12 remaining users
were recruited from Amazon Mechanical Turk, for whom we made a video
explaining how to carry out the study. Users were randomly assigned a version
of the system they would use. The first query was used to train the users in
both the task and the user interface and was omitted from the reported
results. In order to keep the user study 30 minutes, including instructions
and time between queries, we evaluated only 8 queries, and all users did all
queries.

We asked users to search for images containing: A - dogs (BDD), B -
wheelchairs (BDD), and C - cars with open doors (BDD), D - melon (COCO) and E
- spoons (COCO), the last two, F - dustpans and G - egg cartons were over
ObjectNet. Queries A,B, and C do not have labeled ground truth in the BDD
dataset, but exemplify more complex queries or rarer situations than available
in BDD. Queries D and E are not labeled exhaustively in COCO. Because of this
lack of ground truth, we inspected the images shown to the user and user
inputs visually after the session to verify results. These queries were
selected to be representative of the “low” (A,B,C) and “high” (D,E,F,G)
classes in the evaluation presented in Section 5.2, to compare SeeSaw performs
with real users on harder and easier objects.

In Figure 3 we show the number of results marked relevant by the user vs. time
elapsed for each query. The error bars represent the bootstrapped 95%
confidence interval of the median time, and the solid dots the median itself.
We highlight the following results: for the first 3 queries (in the BDD
dataset) SeeSaw outperforms the baseline by a wide margin. For example, for
dogs and wheelchairs, while the initial results are similar for both, it
becomes much harder to find them for the baseline (the baseline can find some
very prominent dogs, but then cannot find more, and cannot adjust based on the
ones found so far). In the case of wheelchairs, the baseline model confuses
wheelchair signs with wheelchairs, but the unfortunately the first are far
more common in a street setting, users of SeeSaw can help correct this through
feedback. For ’Car with open doors’, initial results are rare on both version
of the system, as there are far too many cars with doors, but not many with
open doors in the dataset. After finally locating some examples SeeSaw starts
picking up on the concept, whereas most users of the baseline failed to find
more than 4 examples. We cut off the experiment after 6 minutes and assigned
an time value of 6 minutes to users that did not complete it within that time
(but in reality this is a lower bound). Queries D, E, F, G, show situations
where results are more common; here both versions perform well. While SeeSaw
requires feedback, the overhead of the labeling is low enough that that SeeSaw
users take about as much time as baseline system users. Note that unlike an
object detection labeling task where users must separately label every
instance, users can use coarse labels enclosing most of the items of interest,
if there are several, which lowers the cost of feedback.

Under both scenarios users may fail to see some of the results. The effect of
omission-noise on SeeSaw (which relies on feedback) does not appear large: if
one misses the first example of a car with open doors, (which does happen, as
it takes around 60 images to get to the first), then the overall time it takes
to do the query is longer, but not longer than the baseline.

Latency. The times in Figure 3 include the combined effects of looking at
different numbers of images, annotating images, and waiting for the system to
return new results. Using the same data from the user study above we also
compute the per-frame user annotation latency, and show it in Table 3. Because
both interfaces require marking images as relevant (either by clicking and
drawing a box for SeeSaw or by pressing a key for the baseline), then the time
taken for negative images (2s) is shorter than for those marked positive. When
marked positive, drawing the box in SeeSaw takes (4.5 s), or 1.5x longer than
the baseline (3s), whereas the ratio of accepted to seen images was 1 to 5 in
the user study. Hence, when most results are positive for both systems, there
is a small added overhead for SeeSaw, which is consistent with Figure 3 for
queries F and G. In challenging situations where most results are negative,
however, SeeSaw more than compensates for the extra cost. In addition to user-
time, we also measured system-time, including vector refinement and lookup
times. For the multi-vector representation these costs were on average less
than 200 ms, which is not significant compared to user time.

| baseline | seesaw
---|---|---
not marked |  1.980 $\pm$ .100 |  2.400 $\pm$ .190
marked relevant |  3.000 $\pm$ .280 |  4.400 $\pm$ .450
Table 3. User annotation time (s) per image depends on whether the image is
marked relevant. (2s vs 3s). Localized feedback adds an overhead of about 1.5
seconds per image (4.5s) The $\pm$ denotes the 95% CI.  Figure 3. Summary of
user study time vs relevant results found for 7 queries. Error bars denote the
95% bootstrapped-CI of the median, and the solid dot is the actual median. We
stopped when finding 10 relevant results, or when we hit the 6 minute mark
(dashed line). If the error bar lies over the dashed line, it means at least
some people failed to find that number of results in the 6 minutes. If the
median for a given level lies over the dashed line, then most people failed to
reach that number of results.

###  5.4. Optimization breakdown

In this section we break down the individual contributions of the interactive
concept refinement§4.1 and pyramid representation §4.2 optimizations. Table 4
shows a breakdown of NDCG scores starting at the top row with a version SeeSaw
without either optimization, simply using a visual semantic embedding to
search through images (the same as the baseline in the previous section). As
in Table 2, we separate queries into the same three groups based on how the
visual semantic embedding performs in those groups. On the second row we show
how NDCG changes after adding the pyramid representation optimizations. The
largest NDCG changes from the pyramid optimization occur in the low and medium
tiers of initial performance. Part of the reason is that categories that
already do well initially are partially concepts whose corresponding images
are already biased to large instances, where results are reasonably easy to
spot even at the single image-single vector level, hence the pyramid
representation is not as useful and the baseline is already biased toward the
right answer by the way the datasets are designed. We highlight however that
switching to the pyramid representation does not harm this group despite the
noise introduced due to base level pyramid patches, as described in §4.3. and
still increases scores a significant amount.

The third row in Table 4 shows NDCG changes after applying concept refinement
on top of the pyramid representation optimization. We note both optimizations
have about equal contribution to NDCG improvements in all three baseline
groups, and that for the medium and low baseline groups, half or more of the
total NDCG is due to the combined effect of the optimizations in SeeSaw . In
the low baseline group especially, the baseline alone shows the visual
semantic embedding alone can score quite low, and the optimizations in SeeSaw
can help substantially improve these scores, enabling users to run searches
they would otherwise be unable to carry out.

part | .1 | .1 delta | .3 | .3 delta | 1. | 1\. delta
---|---|---|---|---|---|---
variant |  |  |  |  |  |
CLIP | .05 |  | .18 |  | .72 |
\+ vector pyramid | .08 | .03 | .35 | .17 | .76 | .05
\+ concept refine | .15 | .07 | .41 | .06 | .84 | .07
Table 4. Cumulative breakdown of contribution of different optimizations in
SeeSaw. Queries with low baseline NDCG are those for which the semantic
embedding alone has the lowest accuracy. Both the pyramid representation and
concept refinement contribute similar amounts of NDCG gain for each category.
For those queries with low and medium baseline NDCG, these optimizations
contribute the half or more of the NDCG average.

##  6\. Related work

In this section we review work related to SeeSaw. Image data present two
important challenges from a data management perspective: the first is what
interfaces to use to specify queries and the second is what techniques are
needed to mitigate the high computational demands of current vision
algorithms. Therefore, we organize this section starting with work in related
systems that help users specify queries on visual datasets including natural
language, domain specific languages, and interactive image search systems.
Then we describe ‘model-as-specification’ approaches, by which we mean data
management techniques that presuppose an accurate but expensive oracle model
with structured output and then help reduce the processing costs. Finally, we
review work related to the internal implementation of SeeSaw, including
existing work on learning to rank and on pyramid representations.

Specifying queries over image datasets There is a large amount of work on
image and multimedia search. We focus on recent work.

Rekall(Fu et al., 2019) provides a domain specific language and data model to
help users find custom temporal events in their video data. While targeting
video, it is conceivable similar approaches could help handle ad-hoc complex
scenes within single images such as ‘person kicking a ball’. Unlike SeeSaw,
Rekall’s implementation relies on extracting a representation ahead of time
consisting of object boxes and timestamps. Users rely on this base
representation to construct and execute ad-hoc queries, but these queries can
only specify object types the pre-trained object detector knows about. Thus,
an approach like SeeSaw could be used as a way to extend composition based
approaches like Rekall. There are other systems that rely on having a bounding
boxes available to then help process video queries, such as MIRIS(Bastani et
al., 2020).

Interactive Image Search and Content Based Image Retrieval. The information
retrieval community has worked on the problem of interactive image search, or
so-called content-based image retrieval (Liu et al., 2007; Zhou et al., 2017).
Early instances of this work were done in a web search setting, where search
is driven by the context in which an image appears, e.g., the words around the
image on a page, or by using simple image features such as color histograms.
More recent work from the computer vision community has looked at using
embeddings to find similar images, with great success in applications such as
facial recognition (Schroff et al., 2015). However, such work is not focused
on interactive search but on finding an image similar to a target image. More
recent work from the machine learning community has worked on interactive
search using user-feedback in the form of text (Tan et al., 2019), but has
assumed that images are pre-processed with an object detector trained to
detect a fixed taxonomy of objects, unlike SeeSaw which is designed to find
new, previously detected object types in an image database.

Model-as-specification approaches. One recent line of work related to image
data querying is based on assuming users can access an accurate but
potentially expensive model to answer a query, where the goal is to reduce the
cost and time of to answer queries over images. To do this, prior work has
developed many different learning-to-approximate techniques that use
lightweight models to approximate the reference model, using the reference
model as supervision. This includes work in (Kang et al., 2017),(Kang et al.,
2018), and more recently (Kang et al., 2020). This is quite different than
SeeSaw, where the goal is to optimize search queries only, without a reference
model at all (i.e., SeeSaw finds new classes of objects for which no reference
model is available.). Work such as Chameleon(Jiang et al., 2018) aims to
reduce model-inference costs as well, but also assumes there is a reference
model available.

###  6.1. Implementation related work

Learning to rank.  The pairwise hinge loss formulation of learning to rank
§4.1 dates back to at least (Joachims, 2002), done in the context of web-
search. Since then, this type of ranking loss function based on pairs has been
used widely for retrieval tasks, for example for face similarity
embeddings(Schroff et al., 2015). In SeeSaw we do not train a deep ranking
model or embedding from scratch. The specific problem in SeeSaw is developing
a coherent method to merge the initial search vector derived from a user
search string with the user feedback quickly on every batch. SeeSaw uses the
same loss function as a starting point to derive a formula for this update
because pairwise loss functions naturally handle different degrees of
imbalance between positive and negative examples, which are common in the use
cases SeeSaw handles and change from iteration to iteration.

Pyramid representations.  The idea of image representations consisting of
progressively downscaled versions of the same image goes back many
decades(Adelson et al., 1983). The current generation of object detectors such
as MaskRCNN(He et al., 2017) also incorporate some pyramid ideas in their
architectures but avoid processing multiple replicas of the same image like
SeeSaw does partly due to cost (Lin et al., 2016). Unlike SeeSaw however, they
can rely on training to help handle multiple scales and assume they will run
on very similar data. SeeSaw re-uses the pyramid representations across many
searches, so it is more feasible to use the full pyramid. Further, SeeSaw has
to manage the specific noise issues described in §4.3 without prior training.

Data augmentation.  Multiscale averaging of vectors §4.3.1 is related to test-
time augmentation. There are several key differences with typical test time
augmentation, the first is cost: SeeSaw already computed feature vectors at
the cost of employing patches that do not perfectly align around the region of
interest. This choice keeps the computation lightweight and lets us re-score a
potentially large short-list of hundreds of different images. For typical
test-time augmentation outside of SeeSaw, the full deep net is run on multiple
versions of the same image that was altered in multiple ad-hoc ways. This type
of augmentation increases costs substantially. The second difference is Multi-
scale averaging is not an ad-hoc optimization in SeeSaw but a fix that
addresses the extra false positives by the large number of fine-grained
vectors and their large score variance compared to those of coarser levels in
the pyramid. The underlying principle of of attempting to reduce the variance
component of error by averaging is similar in both situations.

##  7\. Conclusion

We presented SeeSaw, an interactive system for ad-hoc search over image
datasets. SeeSaw helps users specify and refine searches for objects or scenes
of interest within their image datasets. SeeSaw’s interface leverages natural
language and user annotations in the form of bounding boxes around regions of
interest. SeeSaw introduces two techniques to help translate this user
feedback into a better set of results in the next iteration: interactive
concept refinement and pyramid representation. These techniques enable users
and SeeSaw work in a loop to refine the query and to manage situations where
the embedding models SeeSaw relies on for search fall short in accuracy.
SeeSaw gives users a way to find results even for rare categories not served
well by available external models. We evaluated SeeSaw against a strong search
baseline based on CLIP, a state of the art visual-semantic embedding, and show
SeeSaw boosts search accuracy for most queries in a comprehensive benchmark of
thousands of different queries, boosting NDCG score by an average of 4.1x on a
the queries where the pre-trained embeddings perform poorly, and substantially
on almost all queries, even those where CLIP does well.

## References

  * (1)
  * Adelson et al. (1983) Edward Adelson, Charles Anderson, James Bergen, Peter Burt, and Joan Ogden. 1983.  Pyramid Methods in Image Processing.  _RCA Eng._ 29 (11 1983).
  * Barbu et al. (2019) Andrei Barbu, David Mayo, Julian Alverio, William Luo, Christopher Wang, Dan Gutfreund, Josh Tenenbaum, and Boris Katz. 2019\.  ObjectNet: A large-scale bias-controlled dataset for pushing the limits of object recognition models. In _Advances in Neural Information Processing Systems_ , H Wallach, H Larochelle, A Beygelzimer, F Alché-Buc, E Fox, and R Garnett (Eds.), Vol. 32. Curran Associates, Inc.
  * Bastani et al. (2020) Favyen Bastani, Songtao He, Arjun Balasingam, Karthik Gopalakrishnan, Mohammad Alizadeh, Hari Balakrishnan, Michael Cafarella, Tim Kraska, and Sam Madden. 2020\.  MIRIS: Fast Object Track Queries in Video. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ (Portland, OR, USA) _(SIGMOD ’20)_. Association for Computing Machinery, New York, NY, USA, 1907–1921.  https://doi.org/10.1145/3318464.3389692
  * Bernhardsson ([n.d.]) E. Bernhardsson. [n.d.].  ANNOY: Approximate Nearest Neighbors Oh Yeah.  https://github.com/spotify/annoy.  Accessed: 2021-05-20.
  * Chin et al. ([n.d.]) Ting-Wu Chin, 1. Ruizhou Ding, and 1. Diana Marculescu. [n.d.].  ADASCALE: TOWARDS REAL-TIME VIDEO OBJECT DETECTION USING ADAPTIVE SCALING.  ([n. d.]).
  * Fu et al. (2019) Daniel Y. Fu, Will Crichton, James Hong, Xinwei Yao, Haotian Zhang, Anh Truong, Avanika Narayan, Maneesh Agrawala, Christopher Ré, and Kayvon Fatahalian. 2019.  Rekall: Specifying Video Events using Compositions of Spatiotemporal Labels. (Oct 2019).  http://arxiv.org/abs/1910.02993
  * Gupta et al. (2019) Agrim Gupta, Piotr Dollár, and Ross Girshick. 2019\.  LVIS: A Dataset for Large Vocabulary Instance Segmentation.  _arXiv [cs.CV]_ (Aug 2019).  https://arxiv.org/abs/1908.03195
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross B. Girshick. 2017.  Mask R-CNN.  _CoRR_ abs/1703.06870 (2017).  arXiv:1703.06870 http://arxiv.org/abs/1703.06870
  * Jiang et al. (2018) Junchen Jiang, Ganesh Ananthanarayanan, Peter Bodik, Siddhartha Sen, and Ion Stoica. 2018.  Chameleon: scalable adaptation of video analytics. In _Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication_ , Vol. 4. ACM, 253–266.
  * Joachims (2002) Thorsten Joachims. 2002\.  Optimizing search engines using clickthrough data. In _Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’02_. ACM Press.  https://doi.org/10.1145/775066.775067
  * Kang et al. (2018) Daniel Kang, Peter Bailis, and Matei Zaharia. 2018\.  BlazeIt: Fast Exploratory Video Queries using Neural Networks.  _CoRR_ abs/1805.01046 (2018).  arXiv:1805.01046 http://arxiv.org/abs/1805.01046
  * Kang et al. (2017) Daniel Kang, John Emmons, Firas Abuzaid, Peter Bailis, and Matei Zaharia. 2017.  NoScope: Optimizing Neural Network Queries over Video at Scale.  _Proc. VLDB Endow._ 10, 11 (Aug. 2017), 1586–1597.  https://doi.org/10.14778/3137628.3137664
  * Kang et al. (2020) Daniel Kang, John Guibas, Peter Bailis, Tatsunori Hashimoto, and Matei Zaharia. 2020.  Task-agnostic Indexes for Deep Learning-based Queries over Unstructured Data. (Sep 2020).  http://arxiv.org/abs/2009.04540
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge J. Belongie, Lubomir D. Bourdev, Ross B. Girshick, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. 2014.  Microsoft COCO: Common Objects in Context.  _CoRR_ abs/1405.0312 (2014).  arXiv:1405.0312 http://arxiv.org/abs/1405.0312
  * Lin et al. (2016) Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie. 2016\.  Feature Pyramid Networks for Object Detection. (Dec 2016).  http://arxiv.org/abs/1612.03144
  * Liu et al. (2007) Ying Liu, Dengsheng Zhang, Guojun Lu, and Wei-Ying Ma. 2007\.  A survey of content-based image retrieval with high-level semantics.  _Pattern recognition_ 40, 1 (2007), 262–282.
  * Manning et al. (2008) C.D. Manning, P. Raghavan, and H. Schütze. 2008\.  _Introduction to Information Retrieval_.  Cambridge University Press.  https://books.google.com/books?id=t1PoSh4uwVcC
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ 12 (2011), 2825–2830.
  * Radford et al. ([n.d.]) Alec Radford, 1. Jong Wook Kim, 1. Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, and et al. [n.d.].  Learning transferable visual models from natural language supervision.  https://cdn.openai.com/papers/Learning_Transferable_Visual_Models_From_Natural_Language_Supervision.pdf
  * Schroff et al. (2015) Florian Schroff, Dmitry Kalenichenko, and James Philbin. 2015\.  FaceNet: A unified embedding for face recognition and clustering. In _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. 815–823.  https://doi.org/10.1109/CVPR.2015.7298682
  * Singh et al. (2020) Amanpreet Singh, Vedanuj Goswami, Vivek Natarajan, Yu Jiang, Xinlei Chen, Meet Shah, Marcus Rohrbach, Dhruv Batra, and Devi Parikh. 2020.  MMF: A multimodal framework for vision and language research.  https://github.com/facebookresearch/mmf.
  * Tan et al. (2019) Fuwen Tan, Paola Cascante-Bonilla, Xiaoxiao Guo, Hui Wu, Song Feng, and Vicente Ordonez. 2019\.  Drill-down: Interactive Retrieval of Complex Scenes using Natural Language Queries. In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett (Eds.). 2647–2657.
  * Touvron et al. (2019) Hugo Touvron, Andrea Vedaldi, Matthijs Douze, and Herve Jegou. 2019.  Fixing the train-test resolution discrepancy. In _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2019/file/d03a857a23b5285736c4d55e0bb067c8-Paper.pdf
  * Yu et al. (2018) Fisher Yu, Wenqi Xian, Yingying Chen, Fangchen Liu, Mike Liao, Vashisht Madhavan, and Trevor Darrell. 2018.  BDD100K: A Diverse Driving Video Database with Scalable Annotation Tooling.  _CoRR_ abs/1805.04687 (2018).  arXiv:1805.04687 http://arxiv.org/abs/1805.04687
  * Zhou et al. (2017) Wengang Zhou, Houqiang Li, and Qi Tian. 2017.  Recent advance in content-based image retrieval: A literature survey.  _arXiv preprint arXiv:1706.06064_ (2017).