∎

11institutetext: F. Çalışır, Ö. Ulusoy, U. Güdükbay 22institutetext: Bilkent
University, Department of Computer Engineering, Bilkent 06800 Ankara, Turkey
Tel.: +90-312-2901386; Fax: +90-312-2664047
22email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>33institutetext: M. Baştan 44institutetext: Turgut
Özal University, Department of Computer Engineering, Etlik, Keçiören 06010,
Ankara, Turkey
44email<EMAIL_ADDRESS>
# Mobile Multi-View Object Image Search

Fatih Çalışır  Özgür Ulusoy  Uğur Güdükbay  Muhammet Baştan

###### Abstract

High user interaction capability of mobile devices can help improve the
accuracy of mobile visual search systems. At query time, it is possible to
capture multiple views of an object from different viewing angles and at
different scales with the mobile device camera to obtain richer information
about the object compared to a single view and hence return more accurate
results. Motivated by this, we developed a mobile multi-view object image
search system, using a client-server architecture. Multi-view images of
objects acquired by the mobile clients are processed and local features are
sent to the server, which combines the query image representations with
early/late fusion methods based on bag-of-visual-words and sends back the
query results. We performed a comprehensive analysis of early and late fusion
approaches using various similarity functions, on an existing single view and
a new multi-view object image database. The experimental results show that
multi-view search provides significantly better retrieval accuracy compared to
single view search.

##  1 Introduction

Smart mobile devices have become ubiquitous. They are changing the way people
access information. One traditional way to access information is via text
search, by entering a few keywords as query (query-by-keyword); but this is
usually cumbersome and slow, considering the small screen size of mobile
devices. As a convenience, it is also possible to initiate text queries via
speech, if automatic speech recognition is available. Sometimes, it is very
difficult to express a query using only keywords. For instance, when a user at
a shoe store wants to know more about a specific type of shoe (e.g., cheaper
prices elsewhere, customer reviews), she cannot easily formulate a text query
to express her intent. It is much easier to take a photo of the shoe with the
mobile device camera, initiate a visual search and retrieve visually similar
results. This is now possible, owing to the recent hardware/software
developments in mobile device technology, which turned the smart phones with
high-resolution cameras, image processing capabilities and Internet connection
into indispensable personal assistants. This in turn triggered research
interest in mobile visual search and recognition 7 ; 14 ; 15 , and motivated
the industry to develop mobile visual search applications, such as Google
Goggles 16 , CamFind 4 , Nokia Point and Find 37 , Amazon Flow AmazonFlow ,
Kooaba image recognition Kooaba .

Mobile devices have some advantages and disadvantages, compared to regular
PCs. The advantages are higher accessibility, easier user interaction and the
ability to provide context information (e.g., location) using extra sensors,
like GPS and compass. The disadvantages are limited computational power,
storage, battery life and network bandwidth 39 , although these are constantly
being improved and will be less of an issue in the future.

Figure 1: Multi-view images of two different shoes. Online stores typically
contain multi-view images of the objects. Figure 2: Client-server architecture
of our mobile multi-view visual search system.

The main focus of this work is to leverage the user interaction potential of
mobile devices to achieve higher visual search performance, and hence, provide
the users with easier access to richer information. When the user wants to
search for a specific object, she can take a photo of the object to initiate a
visual search. Additionally, she can easily tap on the screen to mark the
object-of-interest and provide extra information to the search system to
suppress the influence of background in matching tapTell . More importantly,
the user can take multiple photos of the object-of-interest from different
viewing angles and/or at different scales, thereby providing much more
information about the query object. We refer to multi-view object image search
as providing multiple query images of an object from various viewing angles
and at various scales and combining the query images using early/late fusion
strategies to achieve higher retrieval precision on single– and/or multi-view
object image databases. High precision on mobile retrieval is especially
critical because the screen is too small to display many results, and more
importantly, the user usually does not have much time and patience to check
more than $10-20$ results.

To illustrate the benefits of multi-view object image search, consider the
multi-view images of two different shoes in Figure 1, taken from four
different viewing angles at the same scale. Such images are typical on online
stores, i.e., multi-view images on clean backgrounds. Assuming the database
contains such multi-view images for each object, when a user performs a search
using a photo that is close to one of the available views, the results she
will get will be better than when the query image has a completely different
view. Intuitively, if the user takes multiple photos of the object from
different viewing angles, the chance that the query images are similar to the
ones in the database will increase. This is still valid when the database
contains single view images of each object. The effect of multiple scales is
similar. In summary, at query time, the user does not know the view and scale
of the object images in the database; by taking multiple photos from different
views and at different scales, she can increase the chance of capturing views
similar to the database images. This is enabled by the interactivity of the
mobile device.

In this work, we investigate the benefits of multi-view object queries and
databases, and best ways to fuse the information coming from multi-view
images. Multi-view queries need special treatment to combine multiple
query/database images using early/late fusion strategies EarlyLateFusion ;
Fusion . We show through experiments that multi-view images in query and/or
database improve retrieval precision significantly, at a cost of modest
increase in computation time due to the increase in the number of images to be
processed.

To demonstrate the benefits of multi-view search, we built a mobile visual
search system based on client-server architecture (cf. Figure 2) and using the
well-known bag-of-visual-words (BoW) approach 14 ; 15 . We performed extensive
experiments on both single and multi-view object image databases with single
and multi-view queries using various fusion strategies and various similarity
functions. The major contributions of this work can be summarized as follows:

  * •

We compare various similarity functions for single view queries on a publicly
available single view object image dataset Caltech256 .

  * •

We provide a comprehensive analysis of early and late fusion strategies for
multi-image and multi-view queries on the single view object image dataset,
and compare their performance with the single view queries.

  * •

We compare the performance of multi-view and single view queries on a new,
multi-view object image dataset, in which each object has multi-view images.
We also compare the running times of single and multi-view queries.

##  2 Related Work

Due to the recent developments in mobile devices with cameras, there has been
a growing interest in mobile visual search, and research works investigate
different aspects of it, such as architectures, power efficiency, speed, and
user interaction. Chen and Girod 7  describe a mobile product recognition
system where the products are CDs, DVDs and books that have printed labels.
The system is local feature based, and Compressed Histogram of Gradients
(CHOG) and Scale-Invariant Feature Transform (SIFT) are used as local
features. Two client-server architectures are implemented and compared in
terms of response time: one is sending images, the other one is extracting
features on the client and sending the features. Sending features took five
seconds, sending images took ten seconds to respond. This means that over slow
connections like 3G it is faster to extract and send features.

Storage space and retrieval speed are important in mobile visual search. Girod
et al. 15  describe a mobile visual search system that adopts the client-
server architecture in which the database is stored on the phone. The system
uses the Bag-of-Words (BoW) approach, and 4 different compact database methods
are experimented and their performances are compared. Li et al. emod  propose
an on-device mobile visual search system. The system uses the BoW approach
with a small visual dictionary due to the memory limitation. Additionally, the
most useful visual words are selected to decrease the retrieval time
considering the processor limitation. Guan et al. efficientBOF  describe an
on-device mobile image search system, which is based on bag-of-features (BoF)
approach. The system uses approximate nearest neighbor search to use high
dimensional BoF descriptors on the mobile device with less memory usage. The
search system also utilizes the GPS data from the mobile device to reduce the
number of images to be compared. Zhou et al. codebookFree  describe a mobile
image search system that does not use a codebook, and hence, decreases the
memory usage and quantization errors. The system makes use of SIFT
descriptors, and the dimensionality of the descriptors is reduced using
Principal Component Analysis (PCA).

Mobile devices have high user interaction potential; this has been utilized
for better retrieval. Joint Search with Image Speech and Words (JIGSAW) 45  is
a mobile visual search system that provides multimodal queries. This system
allows user to speak a sentence and performs text-based image search. The user
selects one or more images from the result set to construct a visual query for
content-based image search. In 34 , a mobile product image search system that
automatically extracts the object in the query image is proposed. From the top
n images that have a clean background, object masks are found. The object in
the query image is then extracted by using a weighted mask approach and its
background is cleaned. The cleaned query image is finally used to perform
image search. Extracting the object-of-interest and performing the query with
a clean background is shown to work better. Similarly, TapTell tapTell  is an
interactive mobile visual search system, in which users take a photo and
indicate an object-of-interest within the photo using various drawing
patterns.

There are several mobile image search applications available on the mobile
market. Point&Find 31  allows the users point the camera to the scene or
object and get information about it. Kooaba is a domain-specific search system
whose target domains are books, DVD and game covers Kooaba . Digimarc Discover
8  is similar to Point&Find; the user points the camera to an object and gets
information about it. PlinkArt 47  is another domain-specific mobile search
system whose target domain is well-known artworks. The user takes a photo of a
well-known artwork and gets information about it. One of the latest mobile
search application is CamFind 4 , which is a general object search system.
When the user takes a photo of a scene, products are identified and similar
objects are listed as a result. Another recent mobile search application is
Amazon Flow AmazonFlow ; the user points the camera to the object and receives
information about it.

Multi-image queries have been used to improve image retrieval. Arandjelovic
and Zisserman 1  propose an object retrieval system using multiple image
queries. The user enters a textual query and Google image search is performed
using this textual query. The top eight images are then retrieved and used as
query images. Early and late fusion methods are applied. Tang and Acton 41
propose a system that extracts different features from different query images.
These extracted features are then combined and used as the features of the
final query image. Another system is proposed in 29 , which allows users to
select different regions of interest in the image. Then each region is treated
as queries and results are combined. Zhang et al. 51  describe a similar
system, which also uses regions; however, these regions are extracted
automatically and users select regions from the extracted parts. Xue et al. 49
propose a system that uses multiple image queries to reduce the distracting
features by using a hierarchical vocabulary tree. The system focuses on the
parts that are common in all the query images. The multi query system
described in 24  uses early fusion; each database image is compared with each
query image and each query image gets a weight according to the similarity
between the query image and the database image.

Queries using multiple images have been utilized in several existing works to
improve the performance of visual search systems. In this work, we take this
one step further and leverage the interaction capability of mobile devices to
perform more informative visual object queries by taking multi-view images of
the query object. We performed comprehensive analysis of various similarity
functions and early/late fusion methods in terms of retrieval precision and
running time. Furthermore, we collected a new multi-view object image dataset
to perform single and multi-view query experiments.

##  3 Proposed Mobile Visual Search System

The proposed mobile multi-view visual search system is based on the well-known
BoW approach: the images are represented as a histogram of quantized local
features, called the BoW histogram. First, interest points are detected on
images; the points are described with local descriptors computed around the
points. Then, a vocabulary (dictionary) is constructed with a set of
descriptors from the database, typically using the k-means clustering
algorithm. Finally, images are represented as a histogram of local interest
point descriptors quantized on the vocabulary. When a query image is received
by the search system, local features are extracted and BoW histogram is
computed. The query histogram is compared with the histograms stored in the
database, and the best k results are returned to the user (cf. Figure 2).

Local features are key to the performance of the search system. In a mobile
system, they should also be efficiently computable. To this end, we employed
two fast local feature detectors: Harris and Speeded Up Robust Features (SURF)
SurfPaper ; LocalFeatureSurvey . They detect two types of complementary local
structures on images: corners and blobs. Using complementary interest points
are useful for improving the expressive power of features and hence the
retrieval precision. The detected points are represented with the SIFT
descriptor. The BoW histograms are computed for Harris and SURF separately,
and then they are concatenated to obtain the BoW histogram of an image.

For ranking the database images, they need to be compared with the query
image, based on the BoW histograms. It is crucial to select the right
similarity functions for high retrieval precision and low computational cost.
There are various similarity functions that can be used to compare histograms
20 ; 22 ; 27 . We experimented with the similarity functions given in Table 1
and presented a comparison in terms of retrieval precision and running time in
Section 5. In the table, $h^{q}$ and $h^{d}$ represent the histogram of the
query and database images, respectively. In the formulas, $q_{i}$ and $d_{i}$
are the $i^{th}$ histogram bin of query and database histograms, respectively.

Table 1: Similarity functions used for comparing the BoW histograms. Similarity Function | Symbol | Formula
---|---|---
Dot Product 22  |  dot$(h^{q},h^{d})$ | $\sum_{i}q_{i}d_{i}$
Histogram Intersection 27  |  HI$(h^{q},h^{d})$ | $\dfrac{\sum_{i}min(q_{i},d_{i})}{min(|h^{q}|,|h^{d}|)}$
Normalized Histogram |  |
Intersection 22  |  NHI$(h^{q},h^{d})$ | $\sum_{i}min\bigg{(}\dfrac{q_{i}}{\sum_{i}q_{i}},\dfrac{d_{i}}{\sum_{i}d_{i}}\bigg{)}$
Normalized Correlation 27  |  NC$(h^{q},h^{d})$ | $\dfrac{\sum_{i}{q_{i}}{d_{i}}}{{\sqrt{{\sum_{i}}{q_{i}^{2}}}}\times{\sqrt{{\sum_{i}}{d_{i}^{2}}}}}$
Min-Max Ratio MinMaxRatio  |  MinMax$(h^{q},h^{d})$ | $\dfrac{\sum_{i}min(q_{i},d_{i})}{\sum_{i}max(q_{i},d_{i})}$

###  3.1 Multi-View Search

Image databases typically contain single view images of objects or scenes, as
in Figure 3. At query time, if the user captures and uses a view close to the
one in the database, she will retrieve the relevant image, but the user does
not have any idea about the view stored in the database. If the query image
has a slightly different view or scale, the invariancy of local features can
handle such view/scale changes; but if the view/scale change is significant,
the system will most probably fail. As a solution, the user may take multiple
photos from different viewing angles and at different scales to increase the
chance of providing query images similar to the database images. Moreover, if
the database images are also multi-view, we can expect to get even better
results. Hence, both the query and database images can be multi-view, each
object/scene having multi-view images, as in Figure 4. In the most general
case, the query may contain $M\geq 1$ images of an object and the database may
consist of $N\geq 1$ images of each object.

Figure 3: Single view images: each image is a typical, single view of an
object. Figure 4: Multi-view images: each object has multiple images from
different viewing angles (and/or at different scales).

•

Single-view query and single-view database ($M=1$, $N=1$): Both the query and
database objects have a single image that represents a specific view of the
object, as in Figure 3. During retrieval, the query image is compared to every
database image using a similarity function (cf. Table 1) to find best k
matches.

•

Single-view query and multi-view database ($M=1$, $N\geq 1$): The query has
single-view (cf. Figure 3) and database objects have multi-view images (cf.
Figure 4). During retrieval, early/late fusion methods (cf. Sections 3.1.1 and
3.1.2) are employed to find and return best k matching database objects.

•

Multi-view query and single-view database ($M\geq 1$, $N=1$): The query has
multi-view images, the database has a single image for each object. During
retrieval, early/late fusion methods are employed to find and return best k
matching database images.

•

Multi-view query and multi-view database ($M\geq 1$, $N\geq 1$): Both the
query and database objects have multi-view images. This is the most general
case and comprises the previous three cases. During retrieval, early/late
fusion methods are employed to find and return best k matching database
objects. We expect to get the best retrieval precision, but at an increased
computational cost.

When the query or database objects have multiple images, we must employ fusion
methods to process the queries and find best k matching database objects. This
is one of the crucial steps to achieve high retrieval performance. There are
mainly two types of fusion methods: early fusion and late fusion. We performed
comprehensive experimental analysis of several early and late fusion methods.

####  3.1.1 Early Fusion

Early fusion, also referred to as fusion in feature space, is the approach in
which the BoW histograms of multiple images are combined into a single
histogram and the similarity function is applied on the combined histograms.
We used the early fusion methods given in Table 2 1 . In the table, the
histograms for $M$ images are combined into ${h^{c}}$; ${h^{j}_{i}}$ is the
$i^{th}$ bin of histogram $h^{j}$ of image $j$.

Table 2: Early fusion methods. Method | Formula
---|---
Sum Histogram | $h^{c}_{i}=\sum_{j=1}^{M}h^{j}_{i}$
Average Histogram | $h^{c}_{i}=\dfrac{\sum_{j=1}^{M}h^{j}_{i}}{M}$
Maximum Histogram | $h^{c}_{i}=max(h^{1}_{i},\ldots,h^{M}_{i})$

####  3.1.2 Late Fusion

Late fusion, also referred to as decision level fusion, considers each query
and database image separately to obtain similarity scores between the query
and database images using their BoW histograms; the final result list is
obtained by combining the individual similarity scores. This can be done in
two ways: (1) image similarity and ranking and (2) image set similarity and
ranking.

Image similarity and ranking. The image histograms in the query are compared
to all the image histograms of all the objects in the database; a single
result list is obtained by ranking the database objects based on similarity
scores or ranking. We used the following methods 24 ; 52 .

  * •

Max Similarity (MAX SIM). Each database image is compared with the query
images and the similarity is taken as the maximum of the similarities.

  * •

Weighted Similarity. Each database image is ranked according to a weighted
similarity to the query images.

  * •

Count. For multiple query images, multiple result lists are obtained. Then,
for each image, a counter is incremented if it is in a list. Finally, the
counter value is used to rank the database images (higher value, higher rank).

  * •

Highest Rank. For multiple query images, multiple result lists are obtained
and the highest rank is taken for each database image.

  * •

Rank Sum. For multiple query images, multiple result lists are obtained and
the ranking of each image in every list is summed and the resulting values are
used to rank the database images.

Image set similarity and ranking. First, the similarity scores between $M$
images of the query object and $N$ database images of each object are
computed, resulting in $M\times N$ similarity scores, as shown in Figure 5.
Then, an image set similarity score between the query object and each database
object is computed, and finally, database objects are ranked according to the
image set similarity scores.

Figure 5: Similarity computation between image sets. The query has $M$ images,
the database object has $N$ images. A similarity score $S_{ij}$ is computed
between every query image i and every database object image j, resulting in
$M\times N$ similarity scores.

The image set similarity scores between $M$ query images and $N$ database
object images are computed in one of the following ways, based on the
individual similarity scores between the query and database images (cf. Figure
5).

  * •

Maximum Similarity (MAX). The similarity score is the maximum of all $M\times
N$ similarity scores.

$\displaystyle Similarity=max(S_{ij})$

If at least one of the query images is very similar to one of the database
object images, this measure will return good results.

  * •

Average Similarity (AVERAGE). The similarity score is computed as the average
of all $M\times N$ similarity scores.

$\displaystyle
Similarity=\dfrac{{\displaystyle\sum^{M}_{i=1}}~{}{\displaystyle\sum^{N}_{j=1}}~{}{S_{ij}}}{M\times
N}$

The average operator reduces the effects of outliers, but it also reduces the
effects of good matches with high similarity scores.

  * •

Weighted Average Similarity (WEIGHTED AVERAGE). To promote the influence of
good matches with high similarity scores, a weight is assigned to each score.

$\displaystyle\begin{split}W_{ij}&=\dfrac{S_{ij}}{{\displaystyle\sum^{M}_{i=1}}~{}{\displaystyle\sum^{N}_{j=1}}~{}{S_{ij}}}\\\
Similarity&={\sum^{M}_{i}}~{}{\sum^{N}_{j}}~{}{S_{ij}}\times{W_{ij}}\end{split}$

  * •

Average of Maximum Similarities (AVERAGE MAX). First, the maximum similarity
for each of $M$ query images to $N$ database object image is computed. Then,
the average of $M$ maximum similarity values is computed as the image set
similarity.

$\displaystyle Similarity=\dfrac{\sum^{M}_{i}{\max(S_{i1},\ldots,S_{iN})}}{M}$

  * •

Weighted Average of Maximum Similarities (WEIGHTED AVERAGE MAX). This is
similar to the previous method; this time, the average is weighted.

$\displaystyle\begin{split}S_{i}&=\max(S_{i1},\ldots,S_{iN})\\\
W_{i}&=\dfrac{S_{i}}{{\sum^{M}_{i}}{S_{i}}}\\\ \displaystyle
Similarity&={\sum^{M}_{i}}{W_{i}}\times{S_{i}}\end{split}$

###  3.2 Speeding up Multi-View Query Processing

Multi-view queries are inherently computationally more expensive than single
view queries. However, it is possible to speed up the multi-view search in a
mobile multi-view search setting. As the user is taking multiple photos of the
query object, the feature extraction and query processing can run in parallel
in the background. This is possible because current mobile devices usually
have multi-code processors. While one thread handles photo-taking, another
thread can extract and send features to the server, which can start query
processing as soon as it receives the features for the first query image.
Figure 6 shows the flow diagram of the whole process as implemented in our
mobile search system.

Figure 6: Workflow of our image search system using early and late fusion
methods.

##  4 Datasets

We used two different datasets to evaluate the performance of our mobile
search system: (i) an existing single view mobile product image search
dataset, Caltech-256 Mobile Product Search Dataset 34 , and (ii) a new multi-
view object image dataset we constructed for this work.

(i) Caltech-256 Mobile Product Search Dataset. This is a subset of the
Caltech-256 Object Category Dataset Caltech256 , which is used to evaluate the
performance of the mobile product search system described in 34 . The dataset
has $20$ categories and $844$ object images with clean background; objects are
positioned at the image center. There are $60$ query images from six
categories; query images contain background clutter. The original Caltech-256
dataset images were downloaded from Google Images. Figure 7 shows sample
images from the dataset. This is a single view object image dataset. Although
the dataset contains multiple images of each category, the images are not
multiple views of the same object, rather they are from different objects of
the same category.

Figure 7: Sample images from the Caltech-256 mobile product search dataset.

(ii) Multi-View Object Images Dataset. The main focus of this work is mobile
multi-view object image search; hence it is crucial to have a suitable multi-
view object image dataset to evaluate the performance of our system. To the
best of our knowledge, such a dataset is not available. We constructed a new
dataset from the Internet: Multi-view Object Image Dataset (MVOD). Each object
has at least two different images taken from different views. MVOD dataset has
six categories and $1664$ object images with a clean background; objects are
positioned at the image center. There are $30$ query images from four
categories, taken by a mobile phone (Samsung I9300 with 8MP built-in camera)..
The dataset is suitable for a mobile product search system, containing images
of daily life items sold on online stores, and hence, it is easy to generate
query images with a mobile device. Figure 8 shows sample images from the
dataset. The dataset is available at www.cs.bilkent.edu.tr/~bilmdg/mvod/.

Figure 8: Sample images from the MVOD dataset.

##  5 Experiments

We performed extensive experiments on the Caltech-256 and MVOD datasets and
evaluated the performance of various similarity functions and fusion methods.
We used the OpenCV library OpenCV  to extract the local features (Harris, SURF
detector with SIFT descriptor). The vocabulary size is $3000$.

We evaluated the proposed image search system in terms of average precision
(AveP) PrecisionPaper  and computational cost. The average precision is
calculated as shown below. In the equation, k represents the rank in the
sequence and N is the length of the result list.

$\begin{split}P(k)=\dfrac{\mbox{\it relevant images}{\;\cap\;}\mbox{\it
first\,k\,images}}{k}\\\ rel(k)=\begin{cases}1,&\mbox{if }\mbox{\it image
k\,is\,relevant}\\\ 0,&\mbox{otherwise}\end{cases}\\\ \displaystyle
AveP=\dfrac{{\sum_{k=1}^{N}}({P(k){\times}rel(k)})}{N}\end{split}$

###  5.1 Results on the Caltech-256 Dataset

As mentioned above, Caltech-256 mobile product search dataset is a single-view
dataset. On this dataset, we performed experiments with three types of
queries:

  * •

Single view queries. Each query is a single object image; the same query
images, as in 34 , are used (six categories, each having ten images). Queries
with clean and cluttered background are performed and evaluated separately. We
used clean background queries provided by 34 . They were obtained by
segmenting out the objects from the background.

  * •

Multi-image queries. Each query consists of multiple object images from the
same category, however, the images belong to different objects, they are not
multiple views of the same object. There are six queries for six categories,
and all ten images are used in each multi-image query.

  * •

Multi-view queries. Each query consists of multi-view images of an object; the
images were taken with a mobile phone and hence not from the Caltech-256
dataset. There are four multi-view queries for four categories, each having
five images.

Figure 9 shows the average precision graphs for single view queries using
various similarity functions for our system. The similarity functions Min-Max
Ratio, Normalized Histogram Intersection and Normalized Correlation work much
better than Dot Product and Histogram Intersection on both clean and
background cluttered queries. As expected, the average precision is higher for
queries with a clean background. When we compare our results with those
presented in Figure 6 (b) of 34 , our average precision values are $0.1-0.15$
higher than 34 , probably due to the multiple complementary features
(Harris+SURF with SIFT) we used. Figure 10 shows single view query examples
with two different similarity functions.

Figure 9: Single view query average precision graphs on Caltech-256 dataset
with various similarity functions: (a) our results with background cluttered
queries and (b) our results with clean background queries.

Figure 10: Single view query examples on Caltech-256 dataset with two
similarity functions: (a) Min-Max Ratio and (b) Normalized Histogram
Intersection.

Figure 11 shows the average precision graphs for multi-image queries using
various fusion methods and the Min-Max Ratio similarity function. The late
fusion methods Rank Sum and Count work better than the other early and late
fusion methods. The average precision values are about 0.25 higher on
background cluttered queries, and 0.1 higher on clean background queries,
compared to the single view queries. Figures 12 and 13 show sample queries.

Figure 11: Multi-image query average precision graphs on Caltech-256 dataset
with various early and late fusion methods and the Min-Max Ratio similarity
function: (a) background cluttered queries, and (b) clean background queries.

Figure 12: Single view and multi-image query examples on Caltech-256 dataset:
(a) single view query, (b) multi-image query with Rank Sum late fusion method,
and (c) multi-image query with Count late fusion method. The Min-Max Ratio
similarity function is used.

Figure 13: Multi-image query examples on Caltech-256 dataset with early
fusion: (a) Average Histogram, and (b) Weighted Average Histogram. The Min-Max
Ratio similarity function is used.

Figures 14 and 15 show the average precision graphs and a sample query for
multi-view queries using various fusion methods and Min-Max Ratio similarity
function. As explained above, the multi-view query images of objects were
taken with a mobile phone on a clean background. The late fusion methods Rank
Sum, Weighted Similarity and Count work better than the other early and late
fusion methods. Multi-view queries improve the average precision performance
further compared to multi-image queries, since the query images are multiple
views of a single object, providing better representation for the query
object.

Figure 14: Multi-view query average precision graph on Caltech-256 dataset
with various early and late fusion methods. The Min-Max Ratio similarity
function is used. The multi-view query images were taken with a mobile phone.

Figure 15: Multi-view query example on Caltech-256 dataset with Rank Sum
fusion and Min-Max Ratio similarity function. The query images were taken with
a mobile phone.

###  5.2 Results on the MVOD Dataset

As mentioned above, MVOD is a multi-view dataset we prepared to evaluate the
performance of our mobile search system on multi-view object image databases.
Since this is a completely different dataset, the results are not directly
comparable to those of Caltech-256. On this dataset, we performed experiments
with two types of queries:

  * •

Single view queries. Each query is a single object image, selected from the
multi-view queries.

  * •

Multi-view queries. Each query consists of multi-view images of an object; the
images were taken with a mobile phone.

Figure 16 and 17 show the average precision graphs for single view and multi-
view queries, respectively. As expected, multi-view queries provide a
significant improvement in average precision (about $+0.2$) over single view
queries. The improvement is more on background cluttered queries, which is
important, since, in a real world setting, the query images will usually have
background clutter. On the other hand, the average precision for queries with
clean background is always higher than queries with cluttered backgroud. It is
possible to reduce the influence of background by segmenting out the objects
automatically, as in 34 , or semi-automatically if the user can quickly tap on
the screen and select the object of interest, as in tapTell .

Among the fusion methods, the late fusion methods, Weighted Average of Maximum
Similarities and Maximum Similarity, and the early fusion method, Maximum
Histogram, work better than the other methods. Sample queries in Figures 18,
19 and 20 demonstrate the improvement in the result lists. Multi-view queries
provide significant improvement over single-view queries, with both clean and
background cluttered query images.

Figure 16: Single view query average precision graphs on the MVOD dataset with
various similarity functions: (a) background cluttered queries and (b) clean
background queries. Figure 17: Multi-view query average precision graphs on
MVOD dataset with various early and late fusion methods: (a) background
cluttered queries, (b) clean background queries. The Min-Max Ratio similarity
function is used.

Figure 18: Single view and multi-view query examples on MVOD dataset: (a)
single view query, (b) multi-view query with Max late fusion method and (c)
multi-view query with the Weighted Average Max late fusion method.

Figure 19: Single view and multi-view query examples on MVOD dataset: (a)
single view query, (b) multi-view query with Max late fusion method and (c)
multi-view query with the Weighted Average Max late fusion method.

Figure 20: Single view and multi-view query examples on MVOD dataset: (a)
single view query, (b) multi-view query with Max late fusion method and (c)
multi-view query with the Weighted Average Max late fusion method.

###  5.3 Running Time Analysis

Multi-view queries are inherently computationally expensive. In this section,
we compare the running times of single and multi-view query methods for
different similarity functions. To do so, we measured the time spent for
matching the images on the server side; this includes the vector quantization,
BoW histogram construction, similarity computation, fusion and ranking. The
measurement is done on the MVOD dataset, with five queries each having five
images, and the measured duration is the average of all queries in each
(query) category. Table 3 summarizes the results. According to the table, the
matching times for the similarity functions are close to each other. The
increase in running time in multi-view queries is not proportional to the
number of images in the query and database, it is lower (due to varying image
content and different numbers of interest points detected in each image).
Based on the running times and the average precision performances, the late
fusion methods, Weighted Average of Maximum Similarities and Maximum
Similarity, and the early fusion method, Maximum Histogram, can be employed
for multi-view object image search.

Table 3: Running times (ms) of similarity functions and fusion methods.

|  | Similarity Functions
---|---|---
|  |  | Normalized
---
Correlation
| Histogram
---
Intersection
| Normalized Histogram
---
Intersection
Dot Product | Min-Max Ratio
Fusion Methods |  | Single View Query
---
(No Fusion)
317 | 343 | 272 | 277 | 332
Sum Histogram | 1122 | 963 | 947 | 899 | 982
Average Histogram | 911 | 925 | 914 | 902 | 913
Maximum Histogram | 962 | 1126 | 965 | 988 | 1010
Average Similarity | 1069 | 1340 | 877 | 1242 | 1132
Weighted Average Similarity | 1080 | 1323 | 899 | 1248 | 1138
Maximum Similarity | 1092 | 1327 | 863 | 1232 | 1128
Average of Max Similarity | 1093 | 1346 | 858 | 1243 | 1136
Weighted Average of Max Similarity | 1118 | 1355 | 849 | 1299 | 1130

##  6 Conclusions

We investigated the performance of single view, multi-image and multi-view
object image queries on both single view and multi-view object image databases
using various similarity functions and early/late fusion methods. We conclude
that multiple view images, both in the queries and in the database,
significantly improve the retrieval precision. Mobile devices with built-in
cameras can leverage the user interaction capability to enable multi-view
queries. The performance can be further improved if the query objects are
isolated from the background. This can be done automatically as in 34  or the
user can tap on the screen and select the object-of-interest in the query
image tapTell . We developed a mobile search system and evaluated it on two
datasets, both suitable for mobile product search, which is one of the useful
application areas of such mobile interactive search systems.

##  7 Acknowledgements

The first author is supported by The Scientific and Technological Research
Council of Turkey (TÜBİTAK) under BİDEB 2228-A Graduate Scholarship.

## References

  * (1) A9.com, Inc.: Amazon Flow.  http://www.a9.com/whatwedo/mobile-technology/flow-powered-by-amazon (2015).  Accessed: 2015-07-27
  * (2) A9.com, Inc.: SnapTell.  http://www.snaptell.com (2015).  Accessed: 2015-05-29
  * (3) Arandjelovic, R., Zisserman, A.: Multiple queries for large scale specific object retrieval.  In: British Machine Vision Conference, pp. 92.1–92.11. BMVA Press (2012)
  * (4) Bay, H., Tuytelaars, T., Van Gool, L.: SURF: Speeded Up Robust Features.  In: European Conference on Computer Vision, Lecture Notes in Computer Science, vol. 3951, pp. 404–417. Springer Berlin Heidelberg (2006)
  * (5) CamFind: CamFind.  http://camfindapp.com (2015).  Accessed: 2015-05-29
  * (6) Cha, S.H.: Comprehensive survey on distance/similarity measures between probability density functions.  International Journal of Mathematical Models and Methods in Applied Sciences 1(4), 300–307 (2007)
  * (7) Chen, D.M., Girod, B.: Memory-Efficient Image Databases for Mobile Visual Search.  In: IEEE Multimedia, vol. 21, pp. 14–23 (2013)
  * (8) Cummins, M., Philbin, J.: PlinkArt.  http://www.androidtapp.com/plinkart (2015).  Accessed: 2015-07-27
  * (9) DigiMarc, Co.: Digimarc Discover.  http://www.digimarc.com/discover (2015).  Accessed: 2015-07-27
  * (10) Girod, B., Chandrasekhar, V., Chen, D.M., Cheung, N., Grzeszczuk, R., Reznik, Y.A., Takacs, G., Tsai, S.S., Vedantham, R.: Mobile Visual Search.  IEEE Signal Processing Magazine 28(4), 61–76 (2011)
  * (11) Girod, B., Chandrasekhar, V., Grzeszczuk, R., Reznik, Y.A.: Mobile visual search: Architectures, technologies, and the emerging MPEG standard.  IEEE MultiMedia 18(3), 86–94 (2011)
  * (12) Google, Inc.: Google Goggles.  http://www.google.com/mobile/goggles (2015).  Accessed: 2015-07-27
  * (13) Griffin, G., Holub, A., Perona, P.: Caltech-256 Object Category Dataset.  Tech. Rep. CNS-TR-2007-001, California Institute of Technology (2007)
  * (14) Guan, T., He, Y., Duan, L., Yang, J., Gao, J., Yu, J.: Efficient BOF Generation and Compression for On-Device Mobile Visual Location Recognition.  IEEE Multimedia 21(2), 32–41 (2014)
  * (15) Gunawardana, A., Shani, G.: A Survey of Accuracy Evaluation Metrics of Recommendation Tasks.  Journal of Machine Learning Research 10, 2935–2962 (2009)
  * (16) itseez: OpenCV.  http://opencv.org (2015).  Accessed: 2015-07-27
  * (17) Joseph, S., Balakrishnan, K.: Multi-Query Content Based Image Retrieval System using Local Binary Patterns.  International Journal of Computer Applications 17(7), 1–5 (2011)
  * (18) Lampert, C.H.: Detecting objects in large image collections and videos by efficient subimage retrieval.  In: International Conference on Computer Vision, pp. 987–994 (2009)
  * (19) Lee, C.H., Lin, M.F.: A Multi-query Strategy for Content-based Image Retrieval.  International Journal of Advanced Information Technologies 5(2), 266–275 (2012)
  * (20) Li, D., Chuah, M.C.: EMOD: An Efficient On-device Mobile Visual Search System.  In: ACM Multimedia Systems Conference, pp. 25–36 (2015)
  * (21) Mazloom, M., Habibian, A.H., Snoek, C.G.M.: Querying for video events by semantic signatures from few examples.  In: ACM Multimedia Conference, pp. 609–612 (2013)
  * (22) Moghaddam, B., Biermann, H., Margaritis, D.: Regions-of-interest and spatial layout for content-based image retrieval.  Multimedia Tools and Applications 14(2), 201–210 (2001)
  * (23) Niaz, U., Merialdo, B.: Fusion methods for multimodal indexing of web data.  In: International Workshop on Image and Audio Analysis for Multimedia Interactive Services. Paris, France (2013)
  * (24) Nokia: Point and Find.  http://www.pointandfind.nokia.com (2015).  Accessed: 2015-07-27
  * (25) Qualcomm Connected Experiences, Inc.: Kooaba: Image Recognition.  http://www.kooaba.com (2015).  Accessed: 2015-07-27
  * (26) Shen, X., Lin, Z., Brandt, J., Wu, Y.: Mobile Product Image Search by Automatic Query Object Extraction.  In: European Conference on Computer Vision, pp. 114–127 (2012)
  * (27) Su, Y., Chiu, T., Chen, Y., Yeh, C., Hsu, W.H.: Enabling low bitrate mobile visual recognition: a performance versus bandwidth evaluation.  In: ACM Multimedia Conference, pp. 73–82 (2013)
  * (28) Tang, J., Acton, S.: An image retrieval algorithm using multiple query images.  In: International Symposium on Signal Processing and Its Applications, vol. 1, pp. 193–196 (2003)
  * (29) Tuytelaars, T., Mikolajczyk, K.: Local invariant feature detectors: A survey.  Foundations and Trends in Computer Graphics and Vision pp. 177–280 (2008)
  * (30) Wang, Y., Mei, T., Wang, J., Li, H., Li, S.: JIGSAW: Interactive Mobile Visual Search with Multimodal Queries.  In: ACM International Conference on Multimedia, MM ’11, pp. 73–82 (2011)
  * (31) Xue, Y., Qian, X., Zhang, B.: Mobile image retrieval using multi-photos as query.  In: IEEE International Conference on Multimedia and Expo Workshops, pp. 1–4 (2013)
  * (32) Zhang, C., Chen, X., Chen, W.B.: An Online Multiple Instance Learning System for Semantic Image Retrieval.  In: IEEE International Symposium on Multimedia Workshops, pp. 83–84 (2007)
  * (33) Zhang, N., Mei, T., Hua, X.S., Guan, L., Li, S.: TapTell: Interactive visual search for mobile task recommendation.  Journal of Visual Communication and Image Representation 29(0), 114–124 (2015)
  * (34) Zhang, S., Yang, M., Cour, T., Yu, K., Metaxas, D.N.: Query specific fusion for image retrieval.  In: Computer Vision - ECCV 2012, _Lecture Notes in Computer Science_ , vol. 7573, pp. 660–673 (2012)
  * (35) Zhou, W., Yang, M., Li, H., Wang, X., Lin, Y., Tian, Q.: Towards codebook-free: Scalable cascaded hashing for mobile image search.  IEEE Transactions on Multimedia 16(3), 601–611 (2014)
  * (36) Zhu, L., Zhang, A.: Supporting Multi-Example Image Queries in Image Databases.  In: International Conference on Multimedia and Expo, pp. 697–700 (2000)