Learning Compact Visual Descriptor for Low Bit Rate Mobile Landmark Search

1 Introduction

With the popularization of mobile embedded cameras, there is a great potential for mobile landmark search with a wide range of applications, such as location recognition, scene retrieval, and photographing recommendation. In general, most existing mobile landmark search systems are deployed under a client-server architecture: In the server end, a visual search system is maintained, typically based on scalable BoW models [Nister et al., 2006][Irschara et al., 2009][Schindler et al., 2007], where landmark photos, as well as their geographically tags like GPS, are inverted indexed into a visual vocabulary. In online search, a landmark query is sent through the wireless network to the server, where near-duplicated search is conducted to identify its best matched landmark, and subsequently returns its geographical location and touristic information to the mobile user.

In a typical scenario, the query photo transmission is over a bandwidth-constrained wireless network. With the ever growing computational power in the mobile devices, while sending the entire query is often unnecessary and time consuming, we propose to perform the visual descriptor extraction directly on the mobile end. In this scenario, the expected visual descriptor should be compact, discriminative, and meanwhile efficient for extraction to tackle the wireless query transmission latency, which also receives dedicated efforts in industry standards like MPEG [Yuri et al., 2010].

Towards low bit rate mobile landmark search, previous local descriptors, e.g. SIFT [Lowe 2004], SURF [Bay et al., 2006], and PCA-SIFT [Ke et al., 2004] cannot work well due to their descriptor lengths. We also argue that recent works in compact visual descriptors [Chen et al., 2009][Chen et al., 2010][Chandrasekhar et al., 2009a][Chandrasekhar et al., 2009b] are still not compact enough towards zerolatency wireless transmission, which is quantitatively proven later. This paper proposes to achieve descriptor compactness through "contextual learning", with additional attentions of the mobile end extraction efficiency.

Our Contribution: We explore this "contextual learning" in combination with the visual statistics in each specific landmark region to learn a compact descriptor from geo-tagged reference photo collections: First, we propose a geographical segmentation scheme based on Gaussian Mixture Model [Stauffer et al., 2000]; Second, we introduce a vocabulary boosting scheme to learn a compact descriptor in each specific region, which simulates a set of landmark queries from this region and learns a compact codebook to maintain the ranking precision from an original visual vocabulary [Sivic et al., 2003][Nister et al., 2006]. With this codebook, a compact BoW descriptor is generated for a given query. However, due to imprecise segmentation, learning compact descriptors respectively in each individual region cannot guarantee a global optimum (as discussed in Section 3). Hence, we propose to further iterate the content aware geographical segmentation and the vocabulary boosting to reinforce each other. Figure 2 shows the mobile visual landmark search system, embedded with contextual learning based compact visual descriptors.

Application Scenarios: Once a mobile user enters a given region, the server transmits a downstream supervision (i.e. a compact codeword boosting vector) to "teach" the mobile device by linearly projecting the original high-dim vocabulary into a compact codebook via this boosting vector. Then, given a query, instead of high-dimensional codeword histogram, an extremely compact histogram is redirected to transmit via 3G or WLAN wireless network.

Paper Outlines: We review related work in visual vocabulary and compact visual descriptors in Section 2. Then, our contextual learning based descriptor extraction is given in Section 3. Section 4 introduces our descriptor implementation in mobile visual search system, covers typical areas like Beijing, New York City, and Barcelona (see snapshot in Figure 1), with quantitative comparisons with the state-of-theart compact visual descriptors [Chen et al., 2009][Chen et al., 2010][Chandrasekhar et al., 2009a][Chandrasekhar et al., 2009b].

2 RelatedWork

Visual Vocabulary Construction: The standard approach to building visual vocabulary usually resorts to unsupervised vector quantization such as K-means [Sivic et al., 2003], which subdivides local feature space into codeword regions. An image is then represented as a BoW histogram, where each bin counts how many local features of this image fall into its corresponding codeword. In recent years, there are many vector quantization based vocabularies, such as Vocabulary Tree [Nister et al., 2006], Approximate K-means [Philbin et al., 2007], Hamming Embedding [Jegou et al., 2008], and [Jurie et al., 2005][Jiang et al., 2007][Philbin et al., 2007][Jegou et al., 2010] et al. Hashing based approach is another solution, such as Locality Sensitive Hashing and its kernelized version [Kulis et al., 2009]. The works in [Jiang et al., 2007][Jegou et al., 2008][Philbin et al., 2007][Gemert et al., 2009] also handles codeword uncertainty and ambiguity, e.g. Hamming Embedding [Jegou et al., 2008], Soft Assignments [Philbin et al., 2007], and kernelized codebook [Gemert et al., 2009]. Recent works in [Moosmann et al., 2006][Mairal et al., 2008][Lazebnik et al., 2009] made use of semantics or category labels to supervise the vocabulary construction.

Compact Visual Descriptors for Mobile Visual Search: Comparing with previous works in compact local descriptors, e.g. SURF [Bay et al., 2006] and PCA-SIFT [Ke et al., 2004], more recent works [Chen et al., 2009][Chen et al., 2010][Chandrasekhar et al., 2009a][Chandrasekhar et al., 2009b] aimed to achieve desirable compression rates that suffice for 3G wireless transmission in mobile visual search scenarios.

The first group comes from direct compression of local visual descriptors. For instance, Chandrasekhar et al. proposed a Compressed Histogram of Gradient (CHoG) [Chandrasekhar et al., 2009a] for compressive local feature description, which adopted both Huffman Tree and Gagie Tree to describe each interest point using approximate 50 bits. The work in [Chandrasekhar et al., 2009b] compressed the SIFT descriptor with Karhunen-Loeve Transform, which yielded approximate 2 bits per SIFT dimension. Tsai et al. [Tsai et al., 2010] proposed to transmit the spatial layouts of interest points to improve the discriminability of CHoG descriptors. Considering the the successive but order insensitive delivery among local features, recent work in [Chen et al., 2011] also proposed to sort the local features the inter-feature compression in addition to the intra-feature compression.

The second group transmits the BoW [Chen et al., 2009][Chen et al., 2010] instead of the original local descriptors to gain much higher compression rate without serious loss of discriminability. Chen et al. [Chen et al., 2009] proposed to compress the sparse bag-of-features by encoding position difference of non-zero bins. It produced an approximate 2KB code per image for a vocabulary with 1M words. The work in [Chen et al., 2010] further compressed the inverted indices of vocabulary tree [Nister et al., 2006] with arithmetic coding to reduce the memory cost in a mobile device. Recent work in [Ji et al., 2011] also proposed to compress the visual vocabulary within the entire city for city-scale mobile landmark search.

3 Learning Compact Landmark Descriptor

Problem Formulation: We denote scalars as italic letters, e.g. v; denote vectors as bold italic letters, e.g. v; denote instance spaces for n instances as Rn; and denote the inner product between u and v as u · v = ∑ni=1 uivi.

Given database images I = {Ii}ni=1 , we offline extract n Bag-of-Words histograms [Nister et al., 2006][Sivic et al., 2003] V = {Vi}ni=1 , which are typically high-dimensional, say 0.1-1 million in state-of-the-art settlings [Nister et al., 2006]. In addition, all images are bounded with corresponding GPS coordinates as G = {Lati, Longi}ni=1 .

Learning Goal: We aim to (1) learn a geographical segmentation S = {Sj}mj=1 to partition I = {Ii}ni=1 into m regions, which attempts to represent the local context to achieve descriptor compactness to an extreme. (2) learn a codebook Uj ∈ Rk for compact descriptor extraction in each Sj from V ∈ Rn such that k ≪ n, which is online updated into the mobile device once the mobile user enters Sj .

Chicken and Egg Problem: On one hand, we expect the Uj is as compact as possible in each Sj. On the other hand, under such circumstance, the compactness depends on how properly an image subset in I is segmented into Sj. However, such segmentation is naturally imprecise, especially in the context of learning compact visual descriptors. While we may learn an optimal descriptor in each region, the overall compactness of all regions may not be guaranteed well. In other words, the optimization towards descriptor compactness is local in each region, rather than among all the regions over the entire image database.

Ideally, we aim to learn both the optimal region segmentation and more compact description in each region to minimize:

where |Ui| denotes the descriptor length of the ith sampled query image (in total n′ ) falling into region Sj; the constraints denote the retrieval precision loss (Loss(PSj )) in each region, which would be revisited in Section 3.2. Obviously, we cannot carry out both geographical segmentation S = {Sj}mj=1 and descriptor learning Uj ∈ Rk in each Sj simultaneously. Hence, we expect an iterative learning to optimize Equation 1 in the entire city.

3.1 Geographical Map Segmentation

We adopt the Gaussian Mixture Model (GMM) [Stauffer et al., 2000] to segment I into S. We assume that the geographical photo distribution is drawn from m landmark regions, and denote the ith component as wi, with mean vector μi. We then regard photos belonging to the ith component as generated from the ith Gaussian with mean μi and covariance matrix ∑i , followed a normalized distribution N(μi, ∑i ).

Therefore, assigning each photo x into the ith region is to infer its Bayesian posterior probability:

where p(x|y = i) is the probability that the region label y of photo x belongs to the ith component, following a normalized distribution:

As neither the component parameters nor the region assignments is known, we adopt an expectation maximization to perform segmentation: First, we estimate Gaussian Mixture Model at the tth iteration (denoted by (t)) as:

The Expectation Step computes the "expected" segmentation label for each database image x as:

The Maximization Step computes the maximal likelihood of each component, given the segmentation membership of x:

The probability of the ith component Pi specifies its priori in geographical segmentation, which is updated as follows:

We revisit Pi in our iterative co-optimization (Section 3.3) to learn geographical segmentation and compact descriptors in a joint manner.

3.2 Descriptor Learning via Vocabulary Boosting

SVT Model for Scalable Search: Towards efficient landmark search in a million scale database, the Scalable Vocabulary Tree (SVT) [Nister et al., 2006] is well exploited in previous works [Chen et al., 2009][Chen et al., 2010][Irschara et al., 2009][Schindler et al., 2007]. SVT uses hierarchical Kmeans to partition local descriptors into quantized codewords. An H-depth SVT with B-branch produces M = BH codewords, and the scalable search typically settles H = 5 and B = 10 [Nister et al., 2006]. Given a query photo Iq with J local descriptors L(q) = [L1(q), ..., LJ(q)], SVT quantizes L(q) by traversing in the vocabulary hierarchy to find out the nearest codeword, which converts L(q) to a BoW histogram V(q) = [V1(q), ..., VM(q)]. In search, the optimal ranking is supposed to minimize the following loss function with respect to the ranking position R(x) of each Ix (BoW feature V(x)):

where TF-IDF weighting is calculated in a way similar to its original form [Salton et al., 1988] in document retrieval:

where nx denotes the number of local descriptors in Ix; nVi (x) denotes the number of local descriptors in Ix quantized into Vi; n denotes the total number of images in the database; nVi denotes the number of images containing Vi; nxi nx serves as the term frequency of Vi in Ix; and log( n nVi ) serves as the inverted document frequency of Vi in the database.

Simulating User Query for Training: For a given region containing n′ landmark photos [I1, I2, ..., In′ ], we randomly sample a set of geo-tagged photos [I ′1 , I ′2 , ..., I ′nsample ] as pseudo queries, which output the following ranking list:

where Aji is the ith returning of the jth query. We expect to maintain the original ranking list [Aj1 ,Aj2 , ...,AjR ] for the jth query using a more compact vocabulary. Therefore, above queries and results are dealt with as ground truth in our subsequent boosting training.

Location Aware Vocabulary Boosting: We deal with descriptor learning as an AdaBoost based codeword selection: The weak learner is each single codeword, and learning is to minimize the ranking discriminability loss with a minimized coding length. We first define [w1, ...,wnsample ] as an error weighting vector to the nsample query images in region Sj, which measures the ranking consistency loss in the current word selection. We then define the encoded vocabulary as Uj ∈ RK for Sj, which is obtained from V ∈ RM via Uj = MT V, whereMM×K is a dimension reduction transform fromRM to RK. In boosting,MMT is a diagonal matrix, where non-zero diagonal position defines a codeword selection. At the tth iteration, we get the current (t-1) non-zero diagonal elements inMMT . To select the tth discriminative codeword, we first estimate the ranking preservation of the current setting of MMT :

where i ∈ [1, nsample]; R(Air ) is the returning position of the originally rth returning for query I ′ i ; [wt-1 1 , ...,wt-1 nsample ] is the (t-1)th error weighting, measuring the loss of the jth query. Then, the overall loss in ranking is:

The best new codeword Ut is selected by minimizing:

where [0, ..., pos(j), .., 0]M is an M × 1 selection vector to select the jth column to the linear projection; and

Algorithm 1: Location Aware Vocabulary Boosting

• 1 Input: Bag-of-Words V = {V(i)}n′ i=1 for region Sj; simulated query logs {I ′ i }nSample i=1 ; Boosting threshold τ ; initial error weighting vector [w1, w2, ..., wnsample ]; and boosting iteration t = 0. 2 Pre-Computing: Calculate LossRank in each region using Equation 13; Calculate ∑nsample i=1 wt i . 3 while {∑nsample i=1 wt i ≤ τ} do 4 Loss Estimation: Calculate LossRank by Equation 13. 5 Codeword Selection: Select Ut by Equation 14. 6 ErrorWeighting: Update [w1, ..., wnsample ] by Equation 15; 7 Transformation Renew: UpdateMt-1 by Equation 16. 8 t + +; 9 end
• 10 Output: Compressed codebook Uj =MT V for region Sj.

[0, ..., pos(t), .., 0]K is a K × 1 position vector to map Vj to the new codeword Ut. We then update the error weighting of each wt-1 i :

Also, theMat the tth round is updated as follows:

The codebook boosting is stopped at ∑nsample i=1 wt i ≤ τ. We summarize our Vocabulary Boosting in Algorithm 1.

3.3 Iterative Co-Optimization

Since there is a tradeoff between the downstream vocabulary adaption and the upstream descriptor delivery, we aim to subdivide the geographical regions, which would yield more compact descriptors and meanwhile aim to merge nearby regions towards less compact descriptors. We fulfill these two joint goals by iterative co-optimization, through the process of geographical segmentation as well as descriptors learnings.

We estimate the necessity of using longer or shorter descriptor length of each region with an uncertainty measurement (like "entropy"), which is dealt with as a feedback to the prior probability Pi in Equation 2 (for the ith region) to refine geographical segmentation at the Tth iteration:

Figure 3 further visualizes the city-scale descriptor minimization procedure with the segmentation-learning iteration (T = 1 to 20). It is intuitive to find out that the overall descriptor length minimization is gradually reduced. In other words, when the mobile users travel in this city and visit multiple landmarks, or multiple travelers visit multiple landmark regions, the overall downstream descriptor adaption and upstream wireless query transmission, is minimized in a more global manner.

4 Implementations and Quantitative Comparison Results

Data Collection and Ground Truth Labeling: We collect over one million geographical tagged photos from both Flickr and Panoramio photo sharing websites, which cover typical areas including Beijing, New York City, and Barcelona. From the geographical map of each city, we choose 30 most dense regions and 30 random regions. Since manually identifying all related photos of a landmark is intensive, for each of these 60 regions, we ask volunteers to manually identify one or more dominant views. Then, all near-duplicated landmark photos to a given view are labeled in its belonging and nearby regions. We then sample 5 images from each region as the query, which forms 300 queries in each city.

Parameters and Evaluations: We extract SIFT [Lowe 2004] features from each photo. We build a Scalable Vocabulary Tree [Nister et al., 2006] to generate the initial vocabulary V, which outputs a Bag-of-Words signature V(i) for each database photo Ii. We use the identical vocabulary generated in Beijing to conduct search in other cities. For each region in a city, the boosting is conducted to offline learnM. We denote the hierarchical level as H and the branching factor as B. In a typical settlement, we have H = 5 and B = 10, producing approximate 0.1 million words. We use mean Average Precision (mAP) to evaluate performance, which reveals its position-sensitive ranking precision in top 10 positions.

Baselines: (1) Original Bag-of-Words: Transmitting the entire BoW has the lowest compression rate. However, it provides the upper bound in mAP. (2) IDF Thresholding: As a straightforward scheme, we only transmit the IDs of codewords with the highest IDF values (Figure 5 tests 20% - 100%) as an alternative solution for vocabulary Compression. (3) Aggregating Local Descriptors [Jegou et al., 2010]: The work in [Jegou et al., 2010] adopted aggregate quantization to obtain compact signature. Its output is also a compressed codeword histogram produced by an initial vocabulary V. (4) Tree Histogram Coding [Chen et al., 2009]: Chen et al. used residual coding to compress the BoW histogram, which is the most related work. (5) Without Co-Optimization: To quantize our iterative co-optimization, we degenerate our approach without iterating between geographical segmentation and descriptor learning.

Efficiency Evaluation: We deployed our compact descriptor extraction into both HTC DESIRE G7 and iPhone4 (the upstream query transmission rate is given in Figure 5). Figure 4 gives a typical memory and time requirement in separate steps when embedding the complete descriptor extraction into the mobile phone.

Rate Distortion Analysis: We compare our rate distortion with state-of-the-art works [Nister et al., 2006][Chen et al., 2009][Chandrasekhar et al., 2009a][Jegou et al., 2010] in Figure 5. We achieve the highest compression rate with equalized distortions (horizontal view), or in other words, maintain the highest search mAP with equalized compression rates (vertical view).

Insights into Compact Descriptors: Descriptor Robustness and Matching Locations: We empirically collect quite a few real-world challenging queries happening at night, while some others occur in different scales (from nearby views or from distant views). There is also a commonsense that some queries are blurred due to mobile capturing. We also selected some suboptimal queries that contain occlusions (objects or persons), as well as photos of partial landmark views. Figure 6 shows that, the compact descriptor from our vocabulary boosting can still well preserve the ranking precision, with comparisons to the Baselines (1)(2)(4). Figure 6 also investigates where our compact descriptor matches from the query photo to the reference database images, where the circles overlapped on the query and the first row of images denote the matched words.

mAP with Respect to Different Region: Figure 7 further shows the mAP variances in different regions, which shows that we can incrementally optimize the mAP in regions containing larger amounts of photos. It is also interesting that mAP is higher in the regions with a descriptor length of 100200 bits, where indeed the majority of regions fall into this category of 100-200 bits. Our extensive empirical study has demonstrated the more optimal performance for landmark search and returning additional information, with this setting of 100-200 bits.

What Compact Codewords are Learnt to Transmit: The learnt codebook is supposed to represent the most discriminative patches for a given query. Figure 8 further investigates which codewords are transmitted during the query. By visualizing the word centroid in Figure 8, we can see that different queries produce different codewords, where the most discriminant words are determined based on the resulting compact codebook to represent the query's visual content.

5 Conclusions and Future Works

In this paper, we propose to learn a compact visual descriptor by combining both visual content and geographical context, which has been deployed for mobile landmark search. We focus on its compactness for a low bit rate wireless transmission, as well as its computational efficiency for embedded feature extraction in mobile devices. We achieve both goals in an iterative optimization framework between geographical segmentation and descriptor learning. Our descriptor has been developed in both HTC DESIRE G7 and iPhone4 mobile phones, which outperforms state-of-the-art works in [Nister et al., 2006][Chen et al., 2009][Chandrasekhar et al., 2009a][Jegou et al., 2010], using one million Web landmark images covering Beijing, New York City, and Barcelona.

We envision the promising usage of context aware compact descriptors in the state-of-the-art research efforts as well as the emerging mobile search applications in industry. The context aware descriptors possibly start more practical scenarios to achieve real world extremely low bit rate transmission in WLAN or 3G s network. In addition, our proposed compact descriptor would be at the very beginning of a significant and potentially huge activity in research, development, and sstandardization of mobile search as well as mobile reality augmentation applications.

In addition, our efforts are closely targeted at the emerging MPEG Compact Descriptor for Visual Search (CDVS) standard. We think that this standardization and relevant research may stand as one of typical examples that integrate intelligent AI technique into embedded mobile platform. Nowadays, MPEG CDVS activity has attracted arising industry interests from quite a few smartphone or imaging chip companies like Nokia, Qualcomm, Aptina, NEC, etc.

6 Acknowledgements

This work was supported in part by the National Basic Research Program of China under contract No. 2009CB320902, in part by grants from the Chinese National Natural Science Foundation under contract No. 60902057 and 61071180, and in part by the CADAL Project Program.