Word Image Retrieval Using Bag of Visual words

by

Ravi Shekhar, C V Jawahar

in

IWDAS
(International Workshop on Document Analysis Systems)

Report No: IIIT/TR/2012/-1

Centre for Visual Information Technology

International Institute of Information Technology
Hyderabad - 500 032, INDIA
March 2012
 2012 10th IAPR International Workshop on Document Analysis Systems

Word Image Retrieval using Bag of Visual Words

Ravi Shekhar and C.V. Jawahar

Center for Visual Information Technology, IIIT Hyderabad, India
Email: [Link]@[Link], jawahar@[Link]

Abstract—This paper presents a Bag of Visual Words approximately one second to compare two word images [3].
(BoVW) based approach to retrieve similar word images This makes it practically infeasible in case of large database,
from a large database, efficiently and accurately. We show where millions of word images are present.
that a text retrieval system can be adapted to build a word
image retrieval solution. This helps in achieving scalability. With the success of document image retrieval, scalability
We demonstrate the method on more than 1 Million word issues have surfaced. In [5], 10M pages are indexed, and
images with a sub-second retrieval time. We validate the the retrieval process takes only 38ms. This is achieved with
method on four Indian languages, and report a mean average the help of a memory intensive hashing scheme. The focus
precision of more than 0.75. We represent the word images of their work is in retrieving similar pages with the help of
as histogram of visual words present in the image. Visual
words are quantized representation of local regions, and for this an invariant descriptor. Such representations are too coarse
work, SIFT descriptors at interest points are used as feature for describing word images for the content level access.
vectors. To address the lack of spatial structure in the BoVW Methods like approximate nearest neighbor search [6] are
representation, we re-rank the retrieved list. This significantly also used to compare word images using a vector space
improves the performance. representation. However such methods are also memory
Keywords-Word Image Retrieval, Bag of Visual Words, intensive. At the same time, we notice that text search
Scalability engines are scalable to billions of documents comfortably.
This motivates us to explore an alternative approach to word
I. I NTRODUCTION image retrieval.
Retrieval of relevant word images from a database of We use BoVW representation for retrieval of word images.
word images is a challenging problem. There are three This is motivated by multiple factors (i) Bag of Words
primary dimensions to this problem: (i) How to represent (BoW) representation has been the most popular representa-
the word images? (ii) How to match/compare two word tion for document (text) retrieval. There are scalable (and
image representations? and (iii) How to retrieve efficiently even distributed software) solutions available. (ii) BoVW
and accurately when the size of the database grows?. All method has shown to perform excellently for recognition
these problems are relatively easy when the representation and retrieval tasks in images and videos [7], [8]. (iii) Being
is text, which can be obtained using an Optical Character a loose representation, BoVW representation can retrieve
Recognition (OCR) system. However for many languages subwords, which is difficult with the popular vector space
(especially for Indian Languages) reliable and robust OCR models. However, this paper does not exploit the full power
systems are still not available [1]. Many of these languages of this flexibility in retrieving partial matches. In BoVW,
have rich heritage, and large quantity of printed material an image is represented by an unordered set of nondis-
exist in them. They are now getting digitized and archived, tinctive discrete visual words. In retrieval phase, an image
but handicapped with the content level access to the collec- is retrieved by computing the histogram of visual word
tion [2]. frequencies, and returning the word image, with the closest
Word spotting [3] has emerged as a promising method for (measured by the cosine of the angles) histogram. This can
recognition free retrieval. Here, word images are represented also be used to rank the returned word images. A benefit of
using some features, and comparison is done with the this approach is that, matches can be effectively computed.
help of an appropriate distance metric. Due to appearance Therefore, images can be retrieved with no delay.
based nature of the matching, word spotting has the ad- We argue that our method is highly language independent.
vantage that it does not require prior learning. Such word The same visual vocabulary works well for multiple lan-
matching schemes have been popularly used in document guages. We verify our method on more than 100K annotated
image retrieval. For example, accessing historic handwritten word images in four different Indian languages. In order to
manuscripts [3], searching documents in a collection of demonstrate the scalability of the method further, we conduct
printed documents [4] etc. In traditional word spotting, word experiment on a database of more than 1 Million words in
images are often represented using a sequence of feature Hindi. We measure the quantitative performance using mean
vectors and compared using Dynamic Time Warping (DTW). Average Precision (mAP), and obtain an mAP of more than
Word spotting with DTW works well. However it takes 0.75 across the entire collection.

978-0-7695-4661-2/12 $26.00 © 2012 IEEE 297

DOI 10.1109/DAS.2012.96
Figure 1. Bag of Visual Words Representation. Left: Input Images. Middle: Feature Extraction. Right Upper: Code Book Generation. Right Lower:
Histogram Computation.

II. BAG OF V ISUAL W ORDS not scalable. We use a computationally efficient Hierarchical
K Means [10] for this purpose. This algorithm clusters the
The BoVW model is inspired by the success of using data into C clusters first (where C is typically ≤ 10) and
BoW in text classification and retrieval. In BoW model, then samples in each of these clusters are clustered again
each document is represented by an unordered set of nondis- recursively. This process is continued until we obtain the
tinctive words present in the document, regardless of the required number (in our case 10000) clusters. This can give
grammar and word order. Document is formally represented more than 1000 times speedup in practice.
with the help of frequency of occurrences (histogram) of the This visual vocabulary is then used to quantize the ex-
words in the vocabulary. These histograms are then used to tracted features by simply assigning the label of the closest
perform document classification and retrieval. Analogously, cluster centroid. This is carried out by rolling down the sam-
an image is represented by an unordered set of nondistinctive ple from the root to the leaf of the vocabulary tree [10]. The
discrete visual features. The set of these discrete visual final representation for an image is the frequency counts or
features is called vocabulary. In the case of a document histogram of the quantized SIFT features [f1 , f2 , ...fi , ..., fk ]
image, one can think of the glyphs as the vocabulary where fi is the number of occurrences of ith visual word in
and a word can be defined as a bag of these glyphs. By the image and k is the vocabulary size. To account for the
representing an image as a histogram of visual words, one difference in the number of interest points between images
can obtain certain level of invariance to the spatial location (due to size etc.), the BoVW histogram is normalized to
of objects in the image. However, this creates certain issues have unit L1 norm.
in document image representation. For example, the word Interest points are computed on word images using Harris
‘DAS’ and ‘SAD’ are same for this representation due to corners. Harris corner detector is a popular interest point
the lack of order/structure in the representation. This reduces detector due to its strong invariance to rotation, scale and
the precision in a retrieval task. We address this issue, image noise. We also tried extracting the Maximally Stable
while exploiting the computational advantages of the BoVW Extremal Regions (MSER) [11] from the word images.
representation as explained in the next section. However, that did not help much in our case. At each of the
Robustly segmenting a word image into the corresponding interest points, SIFT [9] descriptors were extracted. In SIFT,
glyphs is practically impossible, specially for Indian lan- a neighborhood is described by a histogram of weighted
guages where a single character (or connected component) gradients within a window to yield a 128 dimensional vector.
can be composed of multiple glyphs. Moreover, in case of
degraded documents, even extraction of characters become III. R ETRIEVAL S YSTEM
very difficult. Therefore, we represent the characters with In this section we describe our retrieval system. Figure 2
the help of “interest points” like corners and blobs. At shows the overview of the system. The system is divided
each of these interest points, we extract a Scale Invariant into two parts i.e., indexing and retrieval. This is in addition
Feature Transform (SIFT) [9] descriptor to describe the to the one time computation of the vocabulary. Indexing
local information as a vector of gradients. Space of SIFT comprises of three steps as follows: (i) Features are extracted
descriptors is continuous, and we discretize the space by from word images, (ii) Histograms are created by vector
clustering SIFT vectors (often with K means) obtained from quantization, and (iii) Database is created by indexing word
a small collection of documents. We use a vocabulary of images using an inverted file index. In retrieval process, first
10000, and a clustering solution based on K(=1000) means is two steps are similar to the indexing. Then histogram is

298
finally given to the index structure and images are retrieved information using a graph-like structure is computation-
in a ranked manner. We have used Lucene [12], a popular, ally prohibitive. We use the the Spatial Pyramid Match-
reliable and open source search engine, for indexing. ing (SPM) [8] for this purpose. In this method, image
Histogram computation (Figure 1) is carried out with is repeatedly subdivided and histograms of local features
the help of a precomputed vocabulary. For constructing are computed at increasingly fine resolutions. In our case,
the vocabulary, features are extracted from a subset of we divide the image into three parts along columns only
database images. Images are selected such that it covers all as shown in Figure 3. It was observed that, if image is
possible alphabets of the languages of interest. Clustering is divided into more than three parts, there is no significant
done on the feature vectors extracted out of these images. improvement in the performance. The spatial order of the
Collection of centers obtained from this clustering is called characters is thus enforced by considering the sub regions.
the vocabulary as shown in Figure 1. Thus the first part of a query image can match only with
the first part of a database image. Similarly for other parts.
C. Re-ranking
The initial retrieved results are then reranked explicitly
to improve the overall performance of the system. Retrieved
word images using BoVW and query word image are divided
into three parts as explained earlier. SIFT matching is done
for the corresponding parts i.e., original and three parts of
both the query image and the top-k (in our implementation
k = 250) retrieved images. We match the SIFT vectors by
computing the distance between the SIFT vectors as well
as the ratio of the best match to the second best match
as in [9]. For two images (I1 & I2 ), score is given by the
normalization of the number of unique match points with
Figure 2. Overview of the indexing and retrieval. respect to the sum of number of features in both the images.
#M atch P oints
Score = (1)
#SIF T in I1 + #SIF T in I2
A. Use of Search Engines
Total score for a retrieved image is determined by weighted
An inverted index is one of the popular and efficient sum of scores of all parts.
indexing structures for BoW histograms. These index struc-
3
tures are implemented in many search engines. We use 1
T otal Score = Scoreoriginal + Scorei (2)
Lucene [12], a popular open source search engine for the 3 i=1
present work. Each visual word (term) points to a list of
word images (document) that contain it. where Scoreoriginal is score for entire image and Scorei
Internally, Lucene creates frequency file that contains the is score for ith part of the image. Retrieved images are re-
list of documents along with the term frequencies. If Lucene ranked according to Total Score. Images with high score are
finds a term that matches with the search word in the term kept at the top of the list.
information file, it will visit the list in the frequency file to IV. R ESULTS AND D ISCUSSIONS
find which documents contain the term.
In retrieval phase, Lucene does a phrase (collection of In this section, we present results to demonstrate the utility
terms) scoring. For a given phrase, approximate phrase idf is and scalability of the proposed system. To demonstrate the
calculated with sum of terms. Then it calculates actual tf of utility across languages, we use a large data set of 100K
phrase. Similarity between query and document is calculated words. Datasets contain four different Indian languages
by dot product of two histograms. (Hindi, Malayalam, Telugu and Bangla) with significant
change in structure. Two of them have a headline and the
other two do not have. Two of them Aryan languages and
B. Enhancements
the other two are Dravidian languages. Details of the data
One of main limitations of BoVW is that it ignores set are given in Table II. All the books are annotated at the
the spatial relationships between visual words, i.e. it does word level and ground truth was created using [13].
not consider the order of the visual words. Therefore, the To evaluate the quantitative performance, multiple query
retrieved word images from the Lucene have poor precision. images were generated. The query images are selected such
To overcome these limitations, we need to consider the that (i) They have multiple occurrences in the database,
order of the visual words. An elaborate storage of spatial (ii) They are mostly functional words and (iii) They have

299
 Table I
P ERFORMANCE S TATISTICS .

Prec@10 mAP Prec@10 mAP

Language #Images #Query Prec@10 mAP after after after after
Re-ranking Re-ranking Spatial Verification Spatial Verification
Hindi 112677 138 0.8437 0.6808 0.8719 0.7820 0.8770 0.7865
Hindi 1008138 138 0.8059 0.5894 0.8509 0.7022 0.8543 0.7062
Malayalam 108767 101 0.7668 0.6962 0.8328 0.7991 0.8581 0.8188
Telugu 131156 131 0.8507 0.6483 0.8668 0.7328 0.8830 0.7495
Bangla 124584 125 0.8498 0.7806 0.9022 0.8766 0.9182 0.8947

Table II Image Its Parts

B OOKS U SED FOR THE E XPERIMENTS .

Languages Dataset Type #Books #Pages #Words

Hindi Large 4 427 112677
Malayalam Large 6 610 108767
Telugu Large 5 742 131156
Bangla Large 3 363 124584
Hindi Huge 32 3992 1008138

no stop words. The performance is measured by precision Figure 3. Spatial Verification.

at 10 (Prec@10) and mean Average Precision (mAP). The
Prec@10 shows how accurate top 10 retrieved results are.
Our method is giving 0.8543 Prec@10, even in the case of
huge dataset (see Table I). The mAP is the mean of the area
under the precision-recall curve for all the queries. A direct
BoVW solution gave only a mAP of around 0.65. With our
enhancements based on reranking and spatial verification,
mAP increases to more than 0.75 as shown in Table I. (see
columns 5 and 9). Some of the example queries and retrieved
words are shown in Figure 4, where one can observe the
print variations and degradations (like cuts and merges). It
is also observed that, if the length of the query increases, Figure 5. mAP Vs Query length. Also see the effect of re-ranking.
the performance (mAP) also improves. This is shown in
Figure 5. This is natural because, longer words have richer
histogram and more discriminative power. In the case of more occurrences (more than 250) in the database and a
shorter query words we were obtaining results where query complete recall can not be obtained in the present setting.
is a substring of the retrieved word. We also analyzed the However, this can be easily improved by increasing the list
maximum possible mAP for the same retrieved list, that can from 250. Applicability of the method on a huge dataset
be achieved with the help of an ideal re-ranking (i.e., all verifies our claim that the proposed system is scalable to a
the correct images according to ground truth will be on the huge dataset.
top of retrieved list). As it can be seen in Figure 5, our How good is our system?: To benchmark our results,
reranking method is quite comparable to the ideal re-ranking, we also considered a dataset of English words which are
especially for longer words. “visually” similar in quality. This is done by annotating En-
To show the scalability, we use a huge dataset of 1M glish books from a public digital library. Using our method,
words in Hindi (see Table II). The retrieval time from Lucene we obtained an mAP of 0.77 for English. This validates
required for this dataset is summarized in the Table III, on
a system with 2 GB RAM and Intel Core TM 2 Duo CPU Table III
with 2.93 GHz processor. Further the mAP for this dataset R ETRIEVAL T IME .
is comparable to that of huge dataset (see second and third
#Images Retrieval Time Index Size
rows of Table I). The drop in performance is of the order of 25K 50ms 28 MB
0.08, which can be attributed to the fact that the list retrieved 100K 209ms 130 MB
by the Lucene is of the same size (in our size 250) in both 0.5M 411ms 550 MB
the cases. It is natural that with huge dataset, we will have 1M 700ms 1.2 GB

300
 Query Image Retrieved Images

Figure 4. Results of Retrieval: First column shows the query images. Their retrieved images are shown in decreasing order, from left-to-right.

Delhi.
(a) Query Image (b) Rank: 63. (c) Rank: 68. R EFERENCES
(#Occurrence: 400).
[1] S. Setlur and V. Govindaraju(editors), “Guide to OCR for
indic scripts,” in Springer, 2009.
(d) Rank: 76. (e) Rank: 121. (f) Rank: 274. [2] K. P. Sankar, V. Ambati, L. Pratha, and C. V. Jawahar, “Dig-
itizing a million books: Challenges for document analysis,”
Figure 6. Sample results for degraded Images, with rank.
in DAS, 2006, pp. 425–436.

[3] T. M. Rath and R. Manmatha, “Word spotting for historical

that the results on Indian languages are quite comparable to documents,” IJDAR, pp. 139–152, 2007.
those of English. To know the limits of degradation which
our representation can handle, we created a set of degraded [4] A. Balasubramanian, M. Meshesha, and C. V. Jawahar, “Re-
trieval from document image collections,” in DAS, 2006, pp.
English words. Commercial OCRs failed to recognize these
1–12.
words. We indexed these words along with the dataset. We
see that our retrieval system retrieves these words from the [5] K. Takeda, K. Kise, and M. Iwamura, “Real-time document
100K database of English words. Some of the retrieved image retrieval for a 10 million pages database with a memory
degraded words are shown in Figure 6 along with the rank. efficient and stability improved llah,” in ICDAR, 2011.
Note that there are 400 occurrences for this word in the
[6] K. P. Sankar, C. V. Jawahar, and R. Manmatha, “Nearest
database and the AP for this word is 0.7943. In general, neighbor based collection OCR.” in DAS, 2010, pp. 207–214.
we observe that our retrieval system is reasonably robust to
cuts and merges in word images. SIFT descriptors are argued [7] J. Sivic and A. Zisserman, “Video Google: A text retrieval
to be not robust to all possible document degradations. An approach to object matching in videos,” in ICCV, vol. 2, 2003,
pp. 1470–1477.
improved descriptor can make our system compatible with
a wide variety of document degradations. [8] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond bags of
features: Spatial pyramid matching for recognizing natural
V. C ONCLUSIONS AND F UTURE W ORK scene categories,” in CVPR, 2006, pp. 2169–2178.
In this paper, we have presented a document retrieval
system based on BoVW. Our method is highly language [9] D. G. Lowe, “Distinctive image features from scale-invariant
keypoints,” IJCV, vol. 60, no. 2, pp. 91–110, 2004.
independent and scalable. The efficiency of proposed method
is shown experimentally on four Indian languages. We [10] D. Nistr and H. Stewnius, “Scalable recognition with a
have demonstrated the scalability of the method using 1 vocabulary tree,” in CVPR, 2006, pp. 2161–2168.
Million word images. Our future work includes (i) Learning
document-specific local descriptors (ii) Use of better solu- [11] J. Matas, O. Chum, M. Urban, and T. Pajdla, “Robust wide
tions than Lucene (iii) Use of noisy OCR outputs along with baseline stereo from maximally stable extremal regions,” in
BMVC, 2002.
the BoVW representation (iv) Removing the re-ranking step,
which is relatively time consuming. [12] “Lucene,” [Link]
ACKNOWLEDGEMENTS [13] C. V. Jawahar and A. Kumar, “Content-level annotation of
This work is supported by Ministry of Communication large collection of printed document images,” in ICDAR,
and Information Technology, Government of India, New 2007, pp. 799–803.

301