J Philbin

J Sivic

A Zisserman

Keywords: Object discovery, large-scale retrieval, topic/generative models

using standard clustering techniques. The gLDA model can then be applied to generate a more nuanced representation of the data. We also discuss how "hub images" (images representative of an object or landmark) can easily be extracted from our matching graph representation.

We evaluate our techniques on the publicly available Oxford buildings dataset (5K images) and show some examples of automatically mined objects. The methods are evaluated quantitatively on this dataset using a ground truth labelling for a number of Oxford landmarks. To demonstrate the scalability of the matching graph method, we show qualitative results on two larger datasets of images taken of the Statue of Liberty (37K images) and Rome (1M+ images).

Geometric Latent Dirichlet Allocation on a Matching Graph for Large-Scale Image Datasets James Philbin • Josef Sivic • Andrew Zisserman the date of receipt and acceptance should be inserted later Abstract Given a large-scale collection of images our aim is to efficiently associate images which contain the same entity, for example a building or object, and to discover the significant entities. To achieve this, we introduce the Geometric Latent Dirichlet Allocation (gLDA) model for unsupervised discovery of particular objects in unordered image collections. This explicitly represents images as mixtures of particular objects or facades, and builds rich latent topic models which incorporate the identity and locations of visual words specific to the topic in a geometrically consistent way. Applying standard inference techniques to this model enables images likely to contain the same object to be probabilistically grouped and ranked.

Additionally, to reduce the computational cost of applying the gLDA model to large datasets, we propose a scalable method that first computes a matching graph over all the images in a dataset. This matching graph connects images that contain the same object, and rough image groups can be mined from this graph 1 Introduction

In image collections, and especially in collections of tourist photographs collected from sites such as Flickr, certain scenes and objects tend to be photographed much more frequently than others. Our objective in this work is to obtain an association based not on the entire image, but on the objects contained in the images -we want to associate a set of images containing the same objects, even if a particular pair of images is quite dissimilar. The objects may vary significantly in scale, viewpoint, illumination or even be partially occluded. The extreme variation in imaging conditions presents serious challenges to the current state of the art in image-based data mining.

The ability to associate images based on common objects has many potential applications: the frequently Fig. 1 The g LDA generative model. The two topic models (above) generate the visual words and their layout in the three images (below). Each topic model can be thought of as a virtual pinboard, with the words pinned at their mapped location. Image (a) is generated only from topic 1 with a single affine transformation, and image (c) from topic 2, again with a single transformation. Image (b) is a composite of topic 1 under one homography (for the rear building) and topic 2 under a different homography (for the front building). This is a small subset of the images and topics learnt from the set of images shown in figure 9. The lines show the inliers to each topic model. The gLDA model correctly identified the Georgian facade (topic 1) and cloisters (topic 2) as being separate objects (topics), despite the linking image (b), and has correctly localised these two objects in all three images.

occurring objects in a large collection can quickly be perused to form a visual summary; the clusters can provide an access mechanism to the collection; imagebased particular object retrieval could use such methods as a filter to reduce data requirements and so reduce search complexity at query time; and techniques such as automatic 3D reconstruction which take as an input multiple views of the same object can then be applied to these image collections [START_REF] Agarwal | Building rome in a day[END_REF][START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?[END_REF][START_REF] Snavely | Photo tourism: exploring photo collections in 3D[END_REF], and can discover canonical views [START_REF] Simon | Scene summarization for online image collections[END_REF].

This work presents two contributions towards this objective: firstly, we introduce a geometrically consistent latent topic model, that can discover significant objects over an image corpus; secondly we propose methods for efficiently computing a matching graph over the images, where the images are the nodes and the edge strength is given by the overlap in visual content between the images. Using this matching graph together with inexpensive graph-based clustering techniques allows us to partition the corpus into smaller sets of images where our more expensive geometric latent topic model can then be learnt. This makes the entire process scalable to large datasets.

Latent topic models such as probabilistic Latent Semantic Analysis (pLSA) [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF] and Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF] have had significant impact as methods for "semantic" clustering in the statistical text community. Given a collection of documents such as scientific abstracts, with each document represented by a bag-of-words vector, the models are able to learn common topics such as "biology" or "astronomy". The models can then be used to associate relevant documents, even though the documents themselves may have few words in common.

Given the success of these models, several vision papers [START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF][START_REF] Quelhas | Modeling scenes with local descriptors and latent aspects[END_REF][START_REF] Russell | Using multiple segmentations to discover objects and their extent in image collections[END_REF][START_REF] Sivic | Discovering object categories in image collections[END_REF] have applied them to the visual domain, replacing text words with visual words [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF]. The discovered topics then correspond to discovered visual categories, such as cars or bikes in the image collection. However, in the visual domain, there are strong geometric relations between images which do not exist in the text domain. There has been only a limited exploration of these relations in visual latent models: for incorporating segmentation [START_REF] Cao | Spatially coherent latent topic model for concurrent object segmentation and classification[END_REF][START_REF] Russell | Using multiple segmentations to discover objects and their extent in image collections[END_REF][START_REF] Wang | Spatial latent dirichlet allocation[END_REF][START_REF] Winn | Locus: Learning object classes with unsupervised segmentation[END_REF]; or for a gridbased layout of images and objects [START_REF] Bosch | Scene classification using a hybrid generative/discriminative approach[END_REF][START_REF] Fergus | Learning object categories from google's image search[END_REF][START_REF] Fritz | Decomposition, discovery and detection of visual categories using topic models[END_REF][START_REF] Li | Optimol: automatic online picture collection via incremental model learning[END_REF][START_REF] Sivic | Unsupervised discovery of visual object class hierarchies[END_REF].

In this paper we develop a generative latent model with geometric relations at its core. It is an extension of LDA, with a geometric relation (an affine homography) built into the generative process. We term the model gLDA for "Geometric Latent Dirichlet Allocation". The latent topics represent objects as a distribution over visual word identities and their positions on a planar facet, like a pinboard or bulletin board (we will use the term "pinboard" from now on). The visual words in an image (including location and shape) are then generated by an affine geometric transformation which projects words from the pinboard topic models. The generative process is illustrated in figure 1. We show that this model can be learnt in an unsupervised manner by a modification of the standard LDA learning procedure which proposes homography hypotheses using a ransac-like procedure. The results demonstrate that this model is able to cluster significant objects in an image collection despite large changes in scale, viewpoint, lighting and occlusions. Additionally, by representing images as a mixture, the method effortlessly handles the presence of multiple distinct objects. It is similar in spirit to Simon and Seitz [START_REF] Simon | Scene segmentation using the wisdom of crowds[END_REF]'s use of pLSA for inferring object segmentations from large image collections, though we do not require the full 3D scene reconstruction of their method, which is found by performing an expensive bundle adjustment.

Our second contribution is a method to efficiently generate a sparse matching graph over a large image corpus. Each image is a node in the graph, and the graph edges represent the spatial consistency between sub-areas of the pairs of images linked by the edgeif the images contain a common object then the edge strength will reflect this. The graph is used to reduce the computational complexity of learning the gLDA model on large datasets. We can generate this graph using efficient text-based query mechanisms [START_REF] Nister | Scalable recognition with a vocabulary tree[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF] coupled with accurate spatial verification, using each image in turn as a query. Given this graph, standard clustering methods can be applied to find images containing the same object. We are then able to efficiently learn a gLDA model using only subsets of images which are known to share a common object.

Until recently the two most convincing examples for data-mining employing some spatial consistency were [START_REF] Quack | Video mining with frequent itemset configurations[END_REF][START_REF] Sivic | Video data mining using configurations of viewpoint invariant regions[END_REF] where the methods were applied in video to cluster particular objects (such as people or scenes). However, since 2008, four papers [START_REF] Chum | Web scale image clustering: Large scale discovery of spatially related images[END_REF][START_REF] Crandall | Mapping the world's photos[END_REF][START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF][START_REF] Quack | World-scale mining of objects and events from community photo collections[END_REF] have appeared with differing approaches to the large scale mining problem, all using Flickr image collections.

Chum and Matas [START_REF] Chum | Web scale image clustering: Large scale discovery of spatially related images[END_REF] explore random sampling for clusters on a 100K corpus using the min-hash method of [START_REF] Chum | Scalable near identical image and shot detection[END_REF]. This is a very efficient first step, and avoids the more costly building of a complete matching graph employed here. However, as the number of visual words in common between images decreases, the chance of discovering a cluster "seed" in [START_REF] Chum | Web scale image clustering: Large scale discovery of spatially related images[END_REF] decreases, so that potential clusters mined in the complete graph can be missed.

Quack et al. [START_REF] Quack | World-scale mining of objects and events from community photo collections[END_REF] mine a large Flickr corpus of 200K photos, but as a first step use geo-tagging information to decimate the corpus into sets no larger than 4K. The set is then partitioned into clusters using a combination of spatial consistency (as here) and textual similarity. Crandall et al. [START_REF] Crandall | Mapping the world's photos[END_REF] use an extremely large collection (33M) of Flickr images, but as a first step partition the data using mean shift clustering on the GPS location, similarly to [START_REF] Quack | World-scale mining of objects and events from community photo collections[END_REF]. They then define a "matching graph" of images within a cluster using text and visual features, but not spatial consistency between images, and extract canonical or representative images for particular landmarks by spectral clustering.

Li et al. [START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF] mine a 45K Statue of Liberty Flickr photo collection (the corpus differs from the one used here). Their approach is to first cluster the images using the GIST descriptor. Again, this decimates the problem, and spatially consistent clustering can then proceed efficiently within a cluster. As in [START_REF] Chum | Web scale image clustering: Large scale discovery of spatially related images[END_REF] this first step avoids the expense of building a complete matching graph, but because images are matched, rather than objects, the risk is that images with more extreme changes in viewpoint will not be assigned to the same cluster, and will not be associated in subsequent cluster merging. There is clearly an interesting comparison to be made on the measures of speed vs what is missed, between the method presented here and the methods of [START_REF] Chum | Web scale image clustering: Large scale discovery of spatially related images[END_REF][START_REF] Li | Modeling and recognition of landmark image collections using iconic scene graphs[END_REF].

The remainder of the paper is arranged as follows: Section 2 describes the three datasets used for evaluation; section 3 describes our procedure for building a complete matching graph of an image dataset including a brief review of the image retrieval methods used; section 4 describes the gLDA model and the inference procedure; finally, section 5 demonstrates the methods on the three datasets.

The work presented in this paper was originally published in [START_REF] Philbin | Geometric LDA: A generative model for particular object discovery[END_REF][START_REF] Philbin | Object mining using a matching graph on very large image collections[END_REF]. It has been expanded here to include a full description of the gLDA model and its implementation together with additional examples.

Datasets

We use three datasets of varying sizes, all collected automatically from Flickr by searching for images with particular text tags. However, many of the images retrieved bear no relation to the tag initially searched for, as the manual annotation on Flickr tends to be extremely noisy.

Oxford buildings dataset (5K images) For groundtruth evaluation, we use the Oxford Buildings dataset available from [1]. This consists of 5,062 high resolution (1024 × 768) images automatically retrieved from Flickr by searching on particular Oxford landmark tags, such as "Ashmolean". The dataset also provides groundtruth for the occurrences of 11 different Oxford landmarks. A sample of 5 landmark images is shown in figure 2. Note that the dataset contains many images of other buildings and non-buildings (a random sample is shown in figure 3).

Statue of Liberty dataset (37K images)

This is a larger dataset of 37,034 images downloaded from Flickr containing a tag for the "Statue of Liberty". Although all of these images were tagged with the Statue of Liberty, the annotations are extremely noisy and the dataset contains a large number of other, unrelated scenes. The images were provided by the authors of [START_REF] Simon | Scene summarization for online image collections[END_REF].

Rome dataset (1M images) This is a much larger dataset of 1,021,986 images collected from Flickr tagged with "Rome". The dataset contains a large number of tourist and other sites generally taken in Rome, including sites such as the Sistine Chapel and the Colosseum. Again, the images were provided by the authors of [START_REF] Simon | Scene summarization for online image collections[END_REF].

Building a Matching Graph

In this section we explore using a cheap clustering step, which partitions the dataset into a number of disjoint sets of images. The aim is to associate all images that might possibly contain the same object into the same cluster whilst discarding images which definitely have no object in common. We achieve this using a 'matching graph' -a graph of the entire dataset with a node for each image and an edge connecting nodes i and j when images i and j share some common, spatially verified sub-region. Once this cheap clustering step has completed, we can go onto apply more expensive models to each subset in turn.

The process of building the graph relies for its efficiency on a visual words representation and inverted index, as reviewed in section 3.1. In overview, the graph is built in the following way: Initially the graph is empty. For each image of the dataset in turn, we query using the whole image over the entire corpus. The top 400 results from the inverted index are spatially verified as described in section 3.2. Images retrieved with more than a threshold number of verified inliers (we use 20 inliers in the following) to the query image contribute a new edge to the graph linking the query image to the retrieved image. This is repeated for each image in the corpus. The weights on the edges are given by N Im (Nq+Nr)/2 , where N Im is the number of spatially verified inliers and N q , N r are the number of visual words in the query and result respectively. This normalises for the effect of variation in the number of detected visual words in each image.

The graph generated is generally very sparse -for example, the matching graph for the 5K Oxford set contains 24,561 edges (a thousand times less than if every image matched to every other).

Particular Object Retrieval

The search engine uses the vector-space model [START_REF] Baeza-Yates | Modern Information Retrieval[END_REF] common in information retrieval. The query and each document (image) in the corpus is represented as a sparse vector of term (visual word) occurrences and search proceeds by calculating the similarity between the query vector and each document vector, using an L 2 dis- tance. The document vectors are weighted using the simple tf-idf weighting scheme used in text retrieval. This downplays the contribution from commonly occurring, and therefore uninformative, words.

For computational speed, the word occurrences are stored in an inverted index which maps individual visual words (i.e. from 1 to K) to a list of the documents in which they occur. Only words which occur in the query need to be considered and generally this is a small percentage of the total (words not in common do not contribute to the distance). In the worst case, the computational complexity of querying the index is linear in the corpus size, but in practice it is close to linear in the number of documents which match a given query, which can provide a substantial saving. Note also that this method is trivially scalable as the corpus can be distributed to many computing nodes where each node can query in parallel and the result vectors concatenated.

To generate visual features we detect Hessian interest points and fit affine covariant ellipses [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF]. For each of these affine regions, we compute a 128-dimensional SIFT descriptor [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. For the Oxford and Statue of Liberty datasets, a large discriminative vocabulary of 500K words is generated using an approximate k-means clustering method [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] on all the descriptors of all the images in the corpus. For the Rome dataset, a random subsample of 50M descriptors is used for clustering to 1M cluster centres. Each descriptor is assigned to a single cluster centre to give one visual word. On average, there are ∼3,300 regions detected per image. Once processed, each image in the dataset is represented as a set of visual words which include spatial location and the affine feature shape.

Spatial verification

We use a deterministic variant of ransac [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF], which involves generating hypotheses of a restricted (affine) transformation [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] and then iteratively re-evaluating promising hypotheses using the full transformation, similar in spirit to [START_REF] Chum | Locally optimized RANSAC[END_REF]. By selecting a restricted class of transformations for the hypothesis generation stage and by exploiting shape information in the affine-invariant image regions, we are able to generate hypotheses from only a single feature correspondence. Each feature in the image is represented as an ellipse -therefore, each pair of matched features can define a 5 degree-of-freedom transformation between the two images. By including an "upness" constraint (that images are taken upright) we can define a restricted affine transformation (see figure 4). We enumerate all such hypotheses, resulting in a deterministic procedure. The inliers for a given transformation are the set of words which approximately agree with that transformation. Note that although the initial homography does not allow in-plane rotation (due to the "upness" constraint), by iteratively computing the full transform the system can handle significant rotation between images.

The size of this inlier set for the best transformation is used in the matching graph to determine the edge strength, and in the gLDA model to score the support for a latent topic in an image.

Connected Components

One of the simplest operations for splitting the data is to find the connected components on the matching graph. This greatly reduces the complexity of any subsequent clustering step, as now much smaller groupings of images need to be considered. Finding the connected components of a graph can be computed in linear time in the number of graph nodes using depth-first search [START_REF] Cormen | Introduction to Algorithms[END_REF]. An example of the sub-graph automatically discovered for a connected component is shown in figure 7.

Even though the method is crude, it can be surprisingly effective at pulling out commonly occurring objects in photo datasets. It naturally achieves a "tran- sitive association" over the views of an object: views A and C may have no matches, even though they are of the same object. However, provided A links to B, and B links to C, then A and C will be transitively associated. This lack of matches (e.g. between A and C) may arise from detector drop out, SIFT descriptor instability, partial occlusion etc, and was the subject of the "Total Recall" method of [START_REF] Chum | Total recall: Automatic query expansion with a generative feature model for object retrieval[END_REF] where missed matches were corrected at run time by the additional overhead of a form of query expansion. More recently, Turcot and Lowe [START_REF] Turcot | Better matching with fewer features: The selection of useful features in large database recognition problems[END_REF] have used a matching graph to address this missed matches problem by off line processing, thus avoiding the run time cost. This transitive advantage is also a problem though, in that it joins too much together -a "connecting image" (one that contains multiple disjoint objects) pulls all images of these objects into a single connected component. Figure 6 shows some examples of connected components found on the Oxford dataset. Building the matching graph involves setting a threshold on the number of inliers which defines a pair of images as being connected, and this governs the number of connected components obtained. Setting this threshold too low links all images into a single component; too high and no image connects to any other (see figure 5). We compute connected components over this graph thresholding at a particular similarity level. This similarity is specified by the number of spatially consistent inliers between each image pair. In general, the connected components now contain images linked together by some chain of similarities within the cluster, but will not necessarily be of the same object. For example, "linking" images containing more than one object will join other images of these objects into a single cluster (see figure 9).

Hub images

Although not directly used in this work, we note here that one can rank the images within each connected component to pull out canonical or "hub" images. A simple but effective method is to rank images according to the number of spatially verified connections they make to other images within the component. This corresponds to the degree of each node within the graph. Figure 8 shows the three highest and three lowest ranked images according to degree. The images showing more common or canonical views of the object are ranked highly -those showing strong differences in imaging conditions are ranked lowly. Though not done here, simple extensions to this method might include using spectral clustering or computing pagerank [START_REF] Crandall | Mapping the world's photos[END_REF][START_REF] Kim | Unsupervised detection of regions of interest using iterative link analysis[END_REF][START_REF] Quack | World-scale mining of objects and events from community photo collections[END_REF].

Object Discovery

In this section, we review the standard LDA model [START_REF] Blei | Latent dirichlet allocation[END_REF], and then describe its extension to the gLDA model which incorporates geometric information.

Latent Dirichlet Allocation (LDA)

We will describe the LDA model with the original terms 'documents' and 'words' as used in the text literature.

Our visual application of these (as images and visual words) is given in the following sections. Suppose we have a corpus of M documents, w = {w 1 , w 2 , . . . w M }, containing words from a vocabulary of V terms, where w i is the frequency histogram of word ids for document i. A document is generated in the LDA model by picking a distribution over topics and then picking words from a topic dependent word distribution. Figure 10(a) shows the various components of this model. The document specific topic distribution φ is sampled from a Dirichlet prior with parameters α. Similarly the topic specific word distribution θ is sampled from a Dirichlet prior with parameters β. The z variable is a topic indicator variable, one for each observed word, w. The aim is to find the topic distributions which best describe the data by evaluating the posterior distribution P (z|w, α, β) ∝ P (z|α)P (w|z, β).

(1)

These last two terms can be found by integrating out θ and φ respectively. Inference can be performed over this model by using a Gibbs sampler [START_REF] Griffiths | Finding scientific topics[END_REF] with the following update formula:

P (z ij = k|z -ij , w) ∝ n i•k + α n i•• + T α × n •jk + β n ••k + V β (2)
In this equation, z ij is the topic assigned to the jth word in the ith document, n ijk is the number of words from document i, word id j assigned to topic k. A • denotes a summation over that parameter. T and V denote the number of topics and words respectively. z -ij denotes the current topic assignments for all words except the ijth. Note that in equation ( 2), the first term assigns higher probability to topics occurring more frequently in the particular document, and the second term assigns higher probability to words more frequently occurring in the particular topic.

Geometric LDA

In gLDA, the topics of the LDA model are augmented with the spatial position and shape of the visual words, and a geometric transformation between topics and documents is introduced. Given a set of such latent topics, which may be thought of as pin-boards (with the visual words pinned at their positions), an image is generated by first picking a distribution over the pinboards (topics) and sampling an affine homography, H, for each pinboard; and then forming the image as the composition of the visual words from each topic mapped under the corresponding homography. Note, as in LDA, an image will not contain all the words belonging to a topic. This is necessary in the visual domain because not all visual words will be detected -there are errors due to feature detection (such as drop out, or occlusions), feature description and quantization. Others have handled this situation by learning a sensor model [START_REF] Cummins | Probabilistic appearance based navigation and loop closing[END_REF].

The gLDA model is shown in figure 10(b). gLDA adds extra spatial transformation terms, H, to the LDA model and the word terms, w, contain both the identity and spatial position and shape of the visual word in the image. These image specific transformations, H, describe how the words for a particular topic occurring in an image are projected from the "pin-board" model for that topic. H are assumed to be affine transformations, so that the model can account for moderate changes in viewpoint between the topic and the image.

The joint probability of the gLDA model factors as follows P (w, z, H, θ, φ|α, β) = P (w|z, H, θ)P (z|φ)P (θ|β)P (φ|α)P (H)

The generative distributions could be further specified and inference on the model carried out in a similar manner to [START_REF] Sudderth | Describing visual scenes using transformed objects and parts[END_REF]. However, to avoid the expense of generatively sampling the transformation hypotheses, we instead approximate the joint as described next.

Approximate inference

The goal of the inference in the gLDA model is to estimate topic assignments z together with transformation hypotheses H given observed visual words w. For approximate inference, we use an iterative procedure, which alternates between (i) estimating H given the current estimate of z, and (ii) estimating z given the current estimate of H. In step (i), the transformations H between the image and the topic-pinboards are estimated from the words assigned to each topic z directly using efficient tools from multiview geometry. The outcome of this step are a set of inlier words for each homography H. These inliers, together with the associated homography are observed. In step (ii) the number of inliers for each topic-pinboard for each image influences (positively) the assignment of words to topic-pinboards z, as can be seen by glancing ahead to [START_REF] Chum | Locally optimized RANSAC[END_REF]. For these steps we need to book keep which words are inliers to which transformation/topic-pinboard. For this, we introduce indicator variables y, where y ij = k specifies that in image i word j is assigned to topicpinboard k. y is only defined for the inlier words and is not defined for those words that are not an inlier to any transformation. Note that, unlike for z where a word is only assigned to one topic, an inlier word can be assigned to multiple transformation/topic-pinboards. As will be seen, it is only the total number of inliers between an image and a topic-pinboard that is used by ( 9), and we denote this count as q i•k , in analogy with n i•k , for the number of inliers to topic-pinboard k in image i, where q i•k = |∀j : y ij = k|.

Given the now observed y and H, the gLDA model of figure 10(b) is approximated for step (ii) as in the graphical model of figure 10(c). In the approximation, the observed words no longer depend directly on H (in essence this ignores the shape and position of the visual words generated by the transformation from the pinboard-topic). Instead, it is assumed that the inlier indicators y depend on the topic proportions in each image, and these inliers are determined from H (as indicated by the dotted line, with the actual computation described in section 4.4).

We now work through the derivation of ( 9), starting from the graphical model of figure 10(c). The joint probability of the approximate model factors as P (w, z, y, θ, φ|α, β) = P (w|z, θ)P (θ|β)P (z, y|φ)P (φ|α) = P (w|z, θ)P (θ|β)P (z|φ)P (y|φ)P (φ|α) .

(4)

Note, we assume that y and z are conditionally independent given φ. However, when φ is not observed (as here), inlier indicators y influence topic assignments z through φ.

As in standard LDA, parameters φ and θ can be integrated out [START_REF] Griffiths | Finding scientific topics[END_REF]: P (w, y, z|α, β) = P (w|z, θ)P (θ|β)dθ P (z|φ)P (y|φ)P (φ|α)dφ = P (w|z, β)P (z, y|α)

The two integrals can be performed analytically. The first integration gives:

P (w|z, β) = Γ (V β) Γ (β) V T T k=1 j Γ (n •jk + β) Γ (n ••k + V β) , (6)
where Γ (•) is the standard Gamma function and n •jk is the number of visual words with id j assigned to pinboard-topic k over all images. Note that ( 6) is the same as in standard LDA [START_REF] Griffiths | Finding scientific topics[END_REF]. The second integration results in

P (z, y|α) = Γ (T α) Γ (α) T M M i=1 k Γ (n i•k + q i•k + α) Γ (n i•• + q i•• + T α) (7)
where n i•k is the number of words in document i assigned to pinboard-topic k, and q i•k is the number of inlier, i.e. spatially verified words in document i assigned to pinboard-topic k. Note that the observed inlier counts q i•k can be viewed as a document specific prior (virtual word counts) biasing the probability towards topics with a higher number of inliers. Similar to the standard LDA, evaluating the posterior distribution

P (z|y, w, α, β) ∝ P (z, y|α)P (w|z, β) (8)
is intractable. However, similar to [START_REF] Griffiths | Finding scientific topics[END_REF], we can sample from high probability regions of the z space using a Gibbs sampler with the following update formula:

P (z ij = k|z -ij , w, y) = n i•k + q i•k + α n i•• + q i•• + T α × n •jk + β n ••k + V β (9)
This defines a multinomial over topic assignments for a single word, z ij which is sampled to give the new topic assignment. By comparing this update formula to that of standard LDA given in equation ( 2), it is evident how the aggregate inlier counts q i•k influence re-sampling of the pinboard-topic indicators z ij by assigning a higher probability to topic-pinboards with a higher number of inliers. In summary, the approximate inference proceeds in the following iterative two stage procedure. Firstly, the pinboard assignments, z, are resampled with the Gibbs sampler [START_REF] Chum | Locally optimized RANSAC[END_REF]. This is a very simple change to the Gibbs update formula from LDA, but it makes the model much easier to learn than if the full coupling between w and H had been modelled (figure 10(b)). Secondly, given the current assignment of topic-pinboards, z, the transformation hypotheses H together with inlier indicators y are estimated using ransac (for details see section 4.4). The pinboard-topic assignments z depend in-directly on H through the (observed) inlier indicators y. Conversely, changing z by re-assigning a particular visual word to a different pinboard influences transformations H and inlier indicators y during the ransac procedure.

Note that the interleaved sampling of pinboard assignments z using (9) and inliers y with transformation hypothesis H using ransac can be viewed as data driven Markov Chain Monte Carlo in the spirit of [START_REF] Tu | Image parsing: Unifying segmentation, detection, and recognition[END_REF].

Spatial scoring using ransac

The discriminative gLDA model relies on being able to score the spatial consistency between two spatially distributed sets of visual words (e.g. between the pinboard model and an image) and return an approximate transformation between the two sets of visual words as well as a matching score. The score is based on how well the feature locations are predicted by the estimated transformation and is given by the number of inliers. The transformation is estimated using the deterministic variant of ransac described in section 3.2.

The pinboards are updated as follows -every word in the corpus with z ij = k is contained in the pinboard model for topic k projected from the original document i using the current transformation hypothesis, H ik . Terms projected into the pinboard need not be inliers under the current transformation but may become inliers in a further step of alternating Gibbs sampling. This is observed in practice.

gLDA implementation details

Topic initialization. For each connected component of the matching graph the topics are initialized by first obtaining T separate clusters (using agglomerative clustering with average linkage as the similarity score). For each cluster, we project each document's words to a normalized size in the pinboard models: a transformation is found that projects each image to a fixed size square in the topic model and these are used to initialize the locations and shapes of the visual words in the model. Although this is not strictly necessary for the gLDA model, it greatly improves convergence speed and generally leads to improved results.

Prior parameters. The gLDA model (section 4.3) includes priors for the per document topic distribution, α, and the per topic word distribution, β. Empirically we find that using α = 200.0, β = 1.0 gives reasonable results and we use these parameter values for all subsequent experiments.

Choosing the number of topics. To select the number of topics within each connected component, we run 100 iterations of the Gibbs sampler described in section 4.3 changing the number of topics from 1 to 8, then choose the Markov chain with the highest likelihood (see figure 11) [START_REF] Griffiths | Finding scientific topics[END_REF]. We note here that it is better to choose too many topics than too few as the model explicitly allows for documents to be a mixture of topics. In general, the optimal number of topics found will vary with the choice of hyper-parameters, α and β. Running the model. After the number of topics has been selected, we run the model for a further 100 iterations. We find that with the geometric information, the gLDA model tends to converge to a mode extremely quickly (< 50 iterations) and running it longer brings little appreciable benefit.

Scalability. The time taken to run the gLDA model on the Oxford dataset varies from a fraction of a second per iteration for a component of less than 5 images up to about 55s per iteration for the largest component of 396 images on a 2GHz machine.

Results

Matching graph

In this section we show results of building a matching graph over each of the three datasets.

For the Oxford dataset, clustering using connected components found 323 separate components (clusters of more than one image) using an inlier threshold of 20. The size of the largest component is 396 images (of the Radcliffe Camera, a popular Oxford tourist attraction). Scalability. To demonstrate the scalability of our matching graph method, figure 12 and figure 13 show samples from automatically discovered object clusters for the Statue of Liberty (37K images) and Rome (1M+ images) datasets, respectively. Searching for every image in the 37K Statue of Liberty dataset takes around 2 hours on a single 3GHz machine. The Rome data (1M+ images) was much more challenging -it took 1 day on 30 machines to generate the matching graph on this corpus. Though expensive, this demonstrates the ability of our methods to scale across multiple machines.

gLDA

In this section we examine the performance of the gLDA both qualitatively and quantitatively. For the quantitative evaluation we determine if the discovered topics coincide with any of the groundtruth labelled Oxford landmarks.

Evaluation on the Oxford dataset. Within each connected component, we use the document specific mixing weights P (z|d) to produce a ranked list of documents for each discovered topic. We then score this ranked list against the groundtruth landmarks from the Oxford dataset using the average precision measure from information retrieval. For each groundtruth landmark, we find the topic which gives the highest average precision -the results are listed in table 2. The component recall column refers to the maximum recall of the object over all connected components and so gives an upper bound on the possible improvement (as LDA and gLDA look within components).

The topic model often effectively picks out the particular landmarks from the Oxford dataset despite knowing nothing a priori about the objects contained in the groundtruth. Most of the gaps in performance are explained by the topic model including neighbouring facades to the landmark object which frequently co-occur with the object in question. The model knows nothing about the extents of the landmarks required and will include neighbouring objects when it is probabilistically beneficial to do so. We also note that sometimes the connected components don't contain all the images of the landmark -this is mainly due to failures in the initial feature matching.

Figure 18 shows a visualization of two topics discovered by gLDA. It is easy to see that gLDA has correctly found and localized these particular objects in the dataset images. Figure 17 shows three topics automatically discovered by gLDA.

Robustness to imaging conditions. Due to the richness of the pinboard models, the gLDA method is able to group images of a specific object despite large imaging variations (see figure 15). Standard LDA often struggles to cluster challenging images due to the absence of the extra spatial information.

In figure 16, we show the results of running the gLDA method on a 200 image sub-sample from one of the connected components of the Rome dataset, corresponding to the Trevi Fountain. We see that, by forcing a larger number of topics, the gLDA method can also pick out different views of a single object or facade. In this case the model has discovered a night-time view, and two daytime views of the fountain differing in viewpoint.

Comparison with standard LDA. In figure 14 we compare gLDA to standard LDA. The parameters were kept exactly the same between the two methods (except for the spatial term). LDA was initialized by uniformly sampling the topic for each word and run for 500 iterations to account for its slower Gibbs convergence. From the figure we can see that the LDA method has been unable to properly split the Ashmolean facade from an adjacent building.

For a quantitative comparison we use the landmarks from the Oxford dataset. This is an indirect test of performance, because it requires that the landmarks correspond to a discovered topic (and is not split between connected components). For each landmark the component that has highest average precision (AP) is selected. The AP is computed as the area under the precisionrecall curve for each landmark. The gLDA and LDA scores are then given for the best performing topic. Note, the AP for the component is an upper bound on the AP for the topics within that component. The results are given in Table 2. In all cases gLDA is superior (or at least equal) to LDA.

As well as being able to better discover different objects in the data, the gLDA method can localize the occurrence of particular topics in each image instead of just describing the mixture. This can be seen in figure 1 which displays three images from the Magdalen cluster with correspondences to two automatically discovered topics.

Conclusion and Future Work

We have introduced a new generative latent topic model for unsupervised discovery of particular objects and building facades in unordered image collections. In contrast to previous approaches, the model incorporates 2 The performance of gLDA on the Oxford dataset compared to LDA. The scores list the average precision (AP) of the best performing topic for each groundtruth landmark. gLDA always outperforms or does as well as standard LDA for object mining. The last column shows the recall for the component containing the best performing topic -the highest AP score either method could have returned. Figure 14 examines the differences in results for the Ashmolean landmark. strong geometric constraints in the form of affine maps between images and latent aspects. This allows the model to cluster images of particular objects despite significant changes in scale and camera viewpoint. We have shown that the gLDA model outperforms the standard LDA model for discovering particular objects in image datasets.

To make the model tractable we also introduced a matching graph clustered using connected component clustering, that can be used to quickly organize very large image collections, and demonstrated this on image collections of over 1M images.

The gLDA model can be generalized in several directions -for example using a fundamental matrix (epipolar geometry) as its spatial relation instead of an affine homography; or adding a background topic model in the manner of [START_REF] Chemuduguntu | Modeling general and specific aspects of documents with a probabilistic topic model[END_REF]. There is also room for improving the computational efficiency in order to apply the model to larger datasets.

Fig. 4

 4 Fig. 4 Spatial verification: a restricted affine homography of the form shown is computed for every elliptical match between two images.

Fig. 5

 5 Fig.5Examining the number of connected components found as a function of inlier threshold for the Oxford dataset.

Fig. 6

 6 Fig. 6 Examples of the connected components automatically found on the 5K Oxford dataset. Some components are already extremely accurate in isolating individual buildings/landmarks (see (a)-(c)). (d) & (e) show examples of components linking disjoint objects via connecting views. The number of images in each component is shown beneath the label. Note the significant variation of scale and viewpoint within each component.

  Figure 6(d) and (e) show examples of connected components joining disjoint objects via connecting images. We examine the scalability of the graph matching procedure in section 5.1.

Fig. 9 A

 9 Fig.9A sample of 10 images from a connected component associated with Magdalen college. The component contains two separate buildings: A Georgian building and a college cloisters, linked by the aerial photo shown (bottom right). Within the cloisters there are two distinct "facades", one of the wall, the other of a tower. Our full gLDA method is able to extract all three "objects" (cloisters, tower and building) completely automatically. The total size of the component is 42 images.

Fig. 7 A

 7 Fig.7A portion of the full Oxford matching graph for a single connected component. The images in the red and green regions contain the "Bridge of Sighs" and the "Ashmolean Theatre" respectively. Note the two connecting images which contain both objects.

Fig. 8

 8 Fig. 8 Examples of hub images. The three highest (a) and lowest (b) images ranked by degree for a connected component of Christ Church College. The three highest (c) and lowest (d) images ranked by degree for the Thom Tower, Oxford. The degree is listed beneath each image.

Fig. 10 (

 10 Fig. 10 (a) The standard LDA model. (b) The gLDA model. M , T and Nm are the number of documents, topics and words (in document m) respectively. (c) The simplified gLDA model used for one step of the approximate inference. Qm is the number of inlier visual words in document m. See text for details.

Fig. 11

 11 Fig. 11 Automatically choosing the number of topics. (a) the log likelihood of the gLDA model fitted to the connected component shown in figure 9 for different numbers of topics. (b) the top three documents (ranked by P (z|d) in columns) for each topic for different numbers of topics, T . In this case three topics are automatically chosen which separate the building, cloisters and tower.

Fig. 12 Fig. 13 2 Fig. 14 Fig. 15

 121321415 Fig. 12 Random samples of the three largest clusters automatically found from the Statue of Liberty dataset as connected components on the matching graph. Note the extreme variety of imaging conditions (changes in scale, viewpoint, lighting and occlusion) (i) -the Statue of Liberty (11170 images). (ii) -A lego Statue of Liberty (59 images). (iii) -A Ellis Island building (52 images).

Fig. 16 Fig. 17

 1617 Fig.[START_REF] Fei-Fei | A Bayesian hierarchical model for learning natural scene categories[END_REF] Results of running gLDA on a 200 image sub-sample of one of the connected components (corresponding to the Trevi fountain) for the Rome dataset. Here, the model predicted T = 1 using the likelihood method, but we forced T = 3. When this is done, the gLDA model tends to discover views differing in lighting or viewpoint. P (z|d) is listed beneath each image.

  Fig. 17Example images from three topics (one per row) automatically discovered by gLDA from a component of Hertford college, Oxford. The visual words are coloured according to the topic they belong to: 0 -red, 1 -yellow, 2 -blue, 3 -green (not shown). P (z|d) is listed beneath each image.

Fig. 18

 18 Fig.18Visualizing the topics discovered by gLDA. The image data underlying each word in the topic has been projected into the canonical frame for visualization. Here, two discovered topics are shown for different connected components in the Oxford matching graph. This topic visualizations have been generated from all the images in the respective connective components (56 images and 71 images).

  Some of the Oxford landmarks. The Oxford dataset includes 11 "landmarks" -common buildings/views of Oxford for which a manually generated groundtruth is available. Fig. 3 A random sample of images from the Oxford dataset.

	All Souls	Ashmolean	Hertford	Magdalen	Radcliffe Camera
	Fig. 2 Dataset		# images # descriptors
	Oxford		5,062	16,334,770
	Statue of Liberty		37,034	44,385,173
	Rome			1,021,986 1,702,818,841

Table 1

 1 Statistics for each image collection.

Acknowledgements. We are grateful for discussions with Michael Berry and Michael Isard, and for financial support from EPSRC, Microsoft, the Royal Academy of Engineering, ERC grant VisRec no. 228180 and ANR grant ANR-07-BLAN-0331-01.


Vibhor Goel

Anand Mishra

Karteek Alahari

C V Jawahar

Whole is Greater than Sum of Parts: Recognizing Scene Text Words

Recognizing text in images taken in the wild is a challenging problem that has received great attention in recent years. Previous methods addressed this problem by first detecting individual characters, and then forming them into words. Such approaches often suffer from weak character detections, due to large intra-class variations, even more so than characters from scanned documents. We take a different view of the problem and present a holistic word recognition framework. In this, we first represent the scene text image and synthetic images generated from lexicon words using gradient-based features. We then recognize the text in the image by matching the scene and synthetic image features with our novel weighted Dynamic Time Warping (wDTW) approach.

We perform experimental analysis on challenging public datasets, such as Street View Text and ICDAR 2003. Our proposed method significantly outperforms our earlier work in

I. INTRODUCTION

The document image analysis community has shown a huge interest in the problem of scene text understanding in recent years [START_REF] Coates | Text detection and character recognition in scene images with unsupervised feature learning[END_REF], [START_REF] Phan | A gradient vector flow-based method for video character segmentation[END_REF], [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF]. This problem involves various subtasks, such as text detection, isolated character recognition, word recognition. Due to recent works [START_REF] Chen | Detecting and reading text in natural scenes[END_REF], [START_REF] Epshtein | Detecting text in natural scenes with stroke width transform[END_REF], [START_REF] Neumann | Real-time scene text localization and recognition[END_REF], text detection accuracies have significantly improved. However, the success of methods for recognizing words still leaves a lot to be desired. We aim to address this issue in our work.

The problem of recognizing words has been looked at in two broads contexts -with and without the use of a lexicon [START_REF] Mishra | Scene text recognition using higher order langauge priors[END_REF], [START_REF] Mishra | Top-down and bottom-up cues for scene text recognition[END_REF], [START_REF] Wang | End-to-end scene text recognition[END_REF], [START_REF] Weinman | Scene text recognition using similarity and a lexicon with sparse belief propagation[END_REF]. In the case of lexicon-driven word recognition, a list of words is available for every scene text image. The problem of recognizing the word now reduces to that of finding the best match from the list. This is relevant in many applications, such as: [START_REF]Street View Text dataset[END_REF] recognizing certain text in a grocery store, where a list of grocery items can serve as a lexicon, (2) robotic vision in an indoor/outdoor environment.

Lexicon-driven scene text recognition may appear to be an easy task, but the best methods up until now have only achieved accuracies in the low 70s on this problem. Some of these recent methods can be summarized as follows. In [START_REF] Wang | End-to-end scene text recognition[END_REF], each word in the lexicon is matched to the detected set of character windows, and the one with the highest score is reported as the predicted word. This strongly top-down approach is prone to errors when characters are missed or detected with low confidence. In our earlier work [START_REF] Mishra | Top-down and bottom-up cues for scene text recognition[END_REF], we improved upon on this model by introducing a framework, which uses top-down as well as bottom-up cues. Rather than pre-selecting a set of character detections, we defined a global model that incorporates language priors (top-down) and all potential characters (bottom-up). In [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF], Wang et al. combined unsupervised feature learning and multi-layer neural networks for scene text detection and recognition. While both these recent methods improved the previous art significantly, they suffer from the following drawbacks: (i) The need for language-specific character training data. (ii) Do not use the entire visual appearance of the word. (iii) Prone to errors due to false or weak character detections.

In this paper, we choose an alternative path and propose a holistic word recognition method for scene text images. We address the problem in a recognition by retrieval framework. This is achieved by transforming the lexicon into a collection of synthetic word images, and then posing the recognition task as the problem of retrieving the best match from the lexicon image set. The retrieval framework introduced in our approach is similar in spirit to the influential work of [START_REF] Rath | Word image matching using dynamic time warping[END_REF] in the area of handwritten and printed word spotting. We, however, differ from their approach as follows. (1) Our matching score is based on a novel feature set, which shows better performance than the profile features in [START_REF] Rath | Word image matching using dynamic time warping[END_REF]. [START_REF]Robust word recognition dataset[END_REF] We formulate the problem of finding the best word match in a maximum likelihood framework and maximize the probability of two features sequences originating from same word class. [START_REF]ABBYY Finereader 9[END_REF] We propose a robust way to find the match for a word, where k in k-NN is not hand picked, rather dynamically decided based on the randomness of the top retrievals.

Motivation and Overview. The problem of recognizing text (including printed and handwritten text) has been addressed in many ways. Detecting characters and combining them to form a word is a popular approach as mentioned above [START_REF] Mishra | Top-down and bottom-up cues for scene text recognition[END_REF], [START_REF] Wang | End-to-end scene text recognition[END_REF]. Often these methods suffer from weak character detections as shown in Fig. 2(a). An alternative scheme is to learn a model for words [START_REF] Almazan | Efficient exemplar word spotting[END_REF]. There are also approaches that recognize a word by first binarizing the image, and then finding each connected component [START_REF] Kumar | Maps: midline analysis and propagation of segmentation[END_REF]. These methods inherently rely on finding a model to represent each character or word. In the context of scene text recognition, this creates the need for a large amount of training data to cover the variations in scene text. Examples of such variations are shown in Fig. 2(b). Our method is designed to overcome these issues.

We begin by generating synthetic images for the words from the lexicon with various fonts and styles. Then, we compute gradient-based features for all these images as well as the scene text (test) image. We then recognize the text in the image by matching the scene and synthetic image features with our novel weighted Dynamic Time Warping (DTW).

The weights in the DTW matching scores are learned from the synthetic images, and determine the discriminativeness of the features. We use the top k retrieved synthetic images to determine the word most likely to represent the scene text image (see Section II). An overview of our method is shown in Fig. 1.

We present results on two challenging public datasets, namely Street View Text (SVT) and ICDAR 2003 (see Section III). We experimentally show that popular features like profile features are not robust enough to deal with challenging scene text images. Our experiments also suggest that the proposed gradient at edges based features outperform profile features for the word matching task. In addition to being simple, the proposed method improves the accuracy by more than 5% over recent works [START_REF] Mishra | Top-down and bottom-up cues for scene text recognition[END_REF], [START_REF] Wang | End-to-end scene text recognition[END_REF], [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF].

The main contributions of our work are two fold: (i) We show that holistic word recognition for scene text images is possible with high accuracy, and achieve a significant improvement over prior art. (ii) The proposed method does not use any language-specific information, and thus can be easily adapted to any language. Additionally, the robust synthetic word retrieval for scene text queries also shows that our framework can be easily extended for text to image retrieval. However, this is beyond the scope of the paper.

II. WORD REPRESENTATION AND MATCHING

We propose a novel method to recognize the word contained in an image as a whole. We extract features from the image, and match them with those computed for each word in the lexicon. To this end, we present a gradient based feature set, and then a weighted Dynamic Time Warping scheme in the remainder of this section.

Gradient based features. Some of the previous approaches binarize a word image into character vs non-character regions before computing features [START_REF] Kumar | Maps: midline analysis and propagation of segmentation[END_REF]. While such pre-processing steps can be effective to reduce the dimensionality of the feature space, it comes with its disadvantages. The results of binarization are seldom perfect, contain noise, and this continues to be an unsolved problem in the context of scene text images. Thus, we look for other effective features, which do not rely on binarized images. Inspired by the success of Histogram of Oriented Gradient (HOG) features [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] in many vision tasks, we adapted them to the word recognition problem.

To compute the adapted HOG features, we begin by applying the Canny edge operator on the image. Note that we do not expect a clean edge map from this result. We then compute the orientation of gradient at each edge pixel. The gradient orientations are accumulated into histograms over vertical (overlapping) strips extracted from the image. The histograms are weighted by the magnitude of the gradient. An illustration of the feature computation process in shown in Fig. 3. At the end of this step, we have a representation of the image in terms of a set of histograms. In the experimental section we will show that these easy to compute features are robust for the word matching problem.

Matching words. Once words are represented using a set of features, we need a mechanism to match them. The problem is how to match the scene text and synthetic lexicon based images 1 . We formulate the problem of matching scene text and synthetic words in a maximum likelihood framework.

Let X = {x 1 , x 2 , . . . , x m } and Y = {y 1 , y 2 , . . . , y m } be the feature sequences from a given word and its candidate match respectively. Each vector x i and y i is a histogram of gradient features extracted from a vertical strip. Let ω = {ω 1 , ω 2 , . . . , ω K } represent a set of word images where K is the total number of lexicon words. Since we assume features at each vertical strips are independent, the joint probability that the feature sequences X and Y originate from the same word ω k , i.e. P (X, Y |ω k ) can be written as the multiplication of joint probabilities of features originating from the same strip, i.e., P (X,

Y |ω k ) = i P (x i , y i |ω k ). (1)
In a maximum likelihood framework, the problem of finding an optimal feature sequence Y for a given feature sequence X is equivalent to maximize i P (x i , y i |ω k ) over all possible Y s. This can be written as minimization of an objective function f , i.e., min Y i f (x i , y i |ω k ). Where f is the weighted squared l 2 -distance between feature sequences X and Y i.e.,f (x i , y i ) = (x iy j )w i (x iy j ). Here w i is the weight to feature x i . These weights are learned from the synthetic images, and are proportional to the discriminitiveness of features. In other words, given a feature sequence X and a set of candidate sequences Y s, the problem of finding the optimal matching sequence becomes as minimizing f over all candidate sequences Y . This leads to the problem of alignment of sequences. We propose a weighted dynamic programming based solution to solve this problem. Dynamic Time Warping [START_REF] Sankoff | Time warps, string edits, and macromolecules: the theory and practice of sequence comparison[END_REF] is used to compute a distance between two time series. The weighted DTW distance DT W (m, n) between the sequences X and Y can be recursively computed using dynamic programming as:

DT W (i, j) = min DT W (i -1, j) + D(i, j) DT W (i, j -1) + D(i, j) DT W (i -1, j -1) + D(i, j), (2)
where D(i, j) is the distance between features x i and y j , and the local distance matrix D is written as: D = (X -Y ) T W (X -Y ). The diagonal matrix W is learnt from synthetic images. For this we cluster all the feature vectors computed over vertical strips of synthetic images and entropy of each cluster as follows.

1 Details for generating the synthetic lexicon-based images are given in Section III.

H(cluster p ) = -K k=1 P r(y j ∈ ω k , y j ∈ cluster p ) × log K (P r(y j ∈ ω k , y j ∈ cluster p )),

where P r is the joint probability of feature y j originating from class ω k and falling in cluster p . High entropy of a cluster indicates that the features corresponding to that cluster are almost equally distributed in all the word classes. In other words, such features are less informative, and thus are assigned a low weight during matching. The weight w j associated with a feature vector y j is computed as: w j = 1 -H(cluster p ), if y j ∈ cluster p .

Warping path deviation based penalty. To give high penalty to those warping paths which deviate from the near diagonal paths we multiply them with a penalty function log 10 (wpwp o ), where wp and wp o are warping path of DTW matching and diagonal warping path respectively. This penalizes warping paths where a small portion in one word is matched with a large portion in another word.

Dynamic k-NN. Given a scene text and a ranked list of matched synthetic words (each corresponding to one of the lexicon words), our goal is to find the text label. To do so, we apply k-nearest neighbor. One of the issues with a nearest neighbor approach is finding a good k. This parameter is often set manually. To avoid this, we use dynamic k-NN. We start with an initial value of k and measure the randomness of the top k retrievals. Randomness is maximum when all the top k retrievals are different words, and is minimum (i.e. zero) when all the top k retrieval are same. We increment k by 1 until this randomness decreases. At this point we assign the label of the most frequently occurring synthetic word to a given scene text.

In summary, given a scene text word and a set of lexicon words, we transform each lexicon into a collection of synthetic images, and then represent each image as a sequence of features. We then pose the problem of finding candidate optimal matches for a scene text image in a maximum likelihood framework and solve it using weighted DTW. The weighted DTW scheme provides a set of candidate optimal matches. We then use dynamic k-NN to find the optimal word in a given scene text image.

III. EXPERIMENTS AND RESULTS

In this section we present implementation details of our approach, and its detailed evaluation, and compare it with the best performing methods for this task namely [START_REF] Mishra | Top-down and bottom-up cues for scene text recognition[END_REF], [START_REF] Novikova | Large-lexicon attribute-consistent text recognition in natural images[END_REF], [START_REF] Wang | End-to-end scene text recognition[END_REF], [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF].

A. Datasets

For the experimental analysis we used two datasets, namely Street View Text (SVT) [START_REF]Street View Text dataset[END_REF] and ICDAR 2003 robust word recognition [START_REF]Robust word recognition dataset[END_REF]. The SVT dataset contains images taken from Google Street View. We used the SVT-word dataset, which contains 647 images, relevant for the recognition task. A lexicon of 50 words is also provided with each image. The lexicon for the ICDAR dataset was obtained from [START_REF] Wang | End-to-end scene text recognition[END_REF]. Following the protocol of [START_REF] Wang | End-to-end scene text recognition[END_REF], we ignore words with less than two characters or with non-alphanumeric characters, which results in 863 words overall. Note that we could not use the ICDAR 2011 dataset since it has no associated lexicon. The icon in the right most column shows whether a word is correctly recognized or not. We observe that the proposed word matching method is robust to variations in fonts and character size. In the fourth row, despite the unseen style of word image "liquid" the top two retrievals are correct. (Note that following the experimental protocol of [START_REF] Wang | End-to-end scene text recognition[END_REF], we do case-insensitive recognition). The last two rows are failure cases of our method, mainly due to near edit distance words (like center and centers) or high degradations in the word image.

B. Implementation Details

Synthetic Word Generation. For every lexicon word we generated synthetic words with 20 different styles and fonts using ImageMagic. 2 We chose some of the most commonly occurring fonts, such as Arial, Times, Georgia. Our observations suggest that font selection is not a very crucial step for overall performance of our method. A five pixel-width padding was done for all the images. We noted that all the lexicon words were in uppercase, and that the scene text may contain lowercase letters. To account for these variations, we also generated word images where, (i) only the first character is in upper case; and (ii) all characters are in lower case. This results in 3 × lexicon size × 20 images in the synthetic database. For the SVT dataset, the synthetic dataset contains around 3000 images.

Preprocessing. Prior to feature computation, we resized all the word images to a width of 300 pixels, with the respective aspect ratio. We then applied the popular non-local means filter 2 www.imagemagick.org/ smoothing on scene text images. We also remove the stray edges pixels less than 20 in number. Empirically, we did not find this filtering step to be very critical in our approach.

Features. We used vertical strips of width 4 pixels and a 2-pixel horizontal shift to extract the histogram of gradient orientation features. We computed signed gradient orientation in this step. Each vertical strip was represented with a histogram of 9 bins. We evaluated the performance of these features in Table I, in comparison with that of profile features used in [START_REF] Rath | Word image matching using dynamic time warping[END_REF]. Profile features consist of: (1) projection profile, which counts the number of black pixels in each column.

(2) upper and lower profile, which measures the number of background pixels between the word and the word-boundary (3) transition profile, is calculated as the number of textbackground transitions per column. We used the binarization method in [START_REF] Mishra | An MRF model for binarization of natural scene text[END_REF] prior to computing the profile features. Profile features have shown noteworthy performance on tasks such as handwritten and printed word spotting, but fail to cope with the additional complexities in scene text (e.g., low contrast, noise, blur, large intra-class variations). Infact, our results show that gradient features substantially outperform profile based features for scene text recognition.

Weighted Dynamic Time Warping. In our experiments we used 30 clusters to compute the weights. Our analysis comparing various methods are shown in Table I. We observe that with wDTW, we achieve a high recognition accuracy on both the datasets.

Dynamic k-Nearest Neighbor. Given a scene text image to recognize, we retrieve word images from database of synthetic words. The retrieval is ranked based on similarity score. In other words, synthetic words more similar to the scene text word get a higher rank. We use dynamic k-NN with an initial value of k = 3 for all the experiments.

We estimate all the parameters on the train sets of respective datasets. Code for synthetic image generation and feature computation will be made available on our project page. 3

C. Comparison with Previous Work

We retrieve synthetic word images corresponding to lexicon words and use dynamic k-NN to assign text label to a given scene text image. We compared our method with the most recent previous works related to this task, and also the commercial OCR ABBYY in Table II. From the results, we see that the proposed holistic word matching based scheme outperforms not only our earlier work [START_REF] Mishra | Top-down and bottom-up cues for scene text recognition[END_REF], but also many recent works as [START_REF] Novikova | Large-lexicon attribute-consistent text recognition in natural images[END_REF], [START_REF] Wang | End-to-end scene text recognition[END_REF], [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF] on the SVT dataset. On the ICDAR dataset, we perform better than almost all the methods, except [START_REF] Wang | End-to-end text recognition with convolutional neural networks[END_REF]. This marginally inferior performance (of about 0.3%) is mainly because our synthetic database fails to model few of the fonts in ICDAR dataset (Fig. 5). These type of fonts are rare in the street view images. A specific preprocessing or more variations in the synthetic dataset may be needed to deal with such fonts. Fig. 4 shows the qualitative performance of the proposed method on sample images. We observe that the proposed method is robust to noise, blur, low contrast and background variations.

In addition to being simple, our method significantly improves the prior art. This gain in accuracy can be attributed to the robustness of our method, which (i) does not rely on character segmentation rather do holistic word recognition; and (ii) learns discriminitiveness of features in a principled way and use this information for robust matching using wDTW.

IV. CONCLUSION

In summary, we proposed an effective method to recognize scene text. Our method neither requires character segmentation 3 cvit.iiit.ac.in/projects/SceneTextUnderstanding/ nor relies on binarization, but instead performs holistic word recognition. We show a significantly improved performance over the most recent works from 2011 and 2012. We thus establish a new state-of-the-art on lexicon-driven scene text recognition. The robustness of our word matching approach shows that the natural extension of this work can be in direction of "text to scene image" retrieval. As a part of future work, we would explore the benefits of introducing a hidden Markov models for this problem.

Fig. 1 .

 1 Fig.1. Overview of the proposed system. We recognize the word in the test image by matching it with synthetic images corresponding to the lexicon words. A novel gradient based feature set is used to represent words. Matching is done with a weighted DTW scores computed with these features. We use the top k matches to determine the most likely word in the the scene text image.

  (a) Weak character detections due to high inter-class and intra-class confusion as noted in [12]. (b) Large intra-class variations in scene text words.

Fig. 2 .

 2 Fig. 2. (a) Character detection is a challenging problem in the context of scene text images. A couple of examples are shown, where weak character detections lead to incorrect word recognition. (b) Large intra-class variations in scene text images makes it challenging to learn models to represent words. Moreover, getting sufficient training data for each word is not trivial.

Fig. 3 .

 3 Fig. 3. An illustration of feature computation. We divide the word image into vertical strips. In each strip we compute histogram of gradient orientation at edges. These features are computed for overlapping vertical strips.

Fig. 4 .

 4 Fig. 4. Few sample results. Top-5 synthetic word retrieval results for scene text query. First column shows the test image. Top-5 retrieval for the test image are shown from left to right in each row.The icon in the right most column shows whether a word is correctly recognized or not. We observe that the proposed word matching method is robust to variations in fonts and character size. In the fourth row, despite the unseen style of word image "liquid" the top two retrievals are correct. (Note that following the experimental protocol of[START_REF] Wang | End-to-end scene text recognition[END_REF], we do case-insensitive recognition). The last two rows are failure cases of our method, mainly due to near edit distance words (like center and centers) or high degradations in the word image.

Fig. 5 .

 5 Fig. 5. Few images from ICDAR 2003 dataset where our method fails. This may be addressed with inclusion of more variations in our synthetic image database.

Test Image Overlap Window Shift Edge Image Histogram of Gradient Orientations

TABLE I .

 I Feature Comparison: We observe that gradient based features outperform profile features for the holistic word recognition task. This is primarily due to the robustness of gradient features in dealing with blur, noise, large intra-class variations. Non-local (NL) means filtering of scenetext images further improves recognition performance.

TABLE II .

 II Cropped Word Recognition Accuracy (in %): We show a comparison of the proposed method to the popular commercial OCR system ABBYY and many recent methods. We achieve a significant improvement over previous works on SVT and ICDAR.

Acknowledgments. This work is partly supported by MCIT, New Delhi. Anand Mishra is supported the Microsoft Research India PhD fellowship 2012 award. Karteek Alahari is partly supported by the Quaero programme funded by the OSEO.