Learning Compact Visual Representation with Canonical Views for Robust Mobile Landmark Search

1 Introduction

With the rapid growth of social multimedia and mobile devices, tremendous amount of landmark images have been generated and disseminated in popular social networks. Mobile Landmark Search (MLS) is gaining its importance and increasingly becomes one of the most important techniques to pervasively and intelligently access knowledge about the landmarks of interest [Ji et al., 2012; Chen et al., 2014; Cheng and Shen, 2016].

Mobile devices generally suffer from limited computational power, short battery lifetime, and inefficient or less reliable wireless communication channel. Consequently, a client-server structure is one of the most popular architecture paradigms in existing MLS systems, where query is captured and submitted by mobile devices, computationintensive search is performed on remote sever with rich computing resources. Since wireless bandwidth is limited, how to generate a compact signature for query to achieve low bit consumption data transmission becomes vital important. On the other hand, visual splendour of a landmark can be photographed by multiple tourists under various circumstances (e.g. a wide sampling of positions, viewpoints, focal lengths, various weather conditions or illuminations.). Besides, landmarks could be comprised of a wide range of regions. In this case, the images taken for different sub-spots in these landmarks may appear with more visual diversity [Zhu et al., 2015a]. All the characteristics of landmark inevitably make the visual appearances of query images very diverse, thus posing great challenges on MLS search system.

⇤ Jialie Shen is corresponding author.

Hashing [Wang et al., 2016; Zhu et al., 2015c; Xie et al., 2016b] aims at learning compact binary codes with Hamming distance computation. Thus, it can significantly reduce transmission cost and speedup the search process. Hence, hashing is a promising scheme to support large scale landmark image indexing and retrieval. However, the most existing hashing strategies developed for MLS are based on unimodal visualwords based features and generally suffer from 1) limited discriminative capability and 2) poor robustness against visual variations [Chen et al., 2014; Zhou et al., 2014]. Although general multimodal hashing techniques [Kim and Choi, 2013; Song et al., 2013; Liu et al., 2014; Shen et al., 2015] improve discriminative capability with multimodal fusion [Zhu et al., 2015b; Xie et al., 2016a], they are based on simple low-level feature fusion and enjoy less robustness against visual variations of the query landmark images captured by mobile devices.

This paper proposes a Canonical View based Compact Visual Representation (2CVR) to support efficient and robust MLS. We also develop canonical views as the views which capture key visual appearances of landmark with limited redundancy. Based on them, an arbitrary image can be robustly represented using a specific canonical view or the cross-scenery of multiple particular canonical views. Accordingly, varied visual contents of landmark can be effectively characterized using their visual correlations to only fixed canonical views. Through encoding these relations into the binary codes, visual variations of queries can be robustly modeled. Furthermore, the low-cost query transmission and fast search can be well supported.

The contributions of this paper are summarized as follows:

1. A submodular function is designed to measure visual representativeness and redundancy of a view set. With it, an iterative mining strategy is proposed to efficiently identify canonical views of landmarks using multiple modalities. Theoretical analysis demonstrates that it can achieve nearoptimal solutions.
2. A novel intermediate representation generated by multimodal sparse coding is proposed to robustly characterize the visual contents of varied landmark images. It provides a natural and effective connection between the canonical views and binary embedding model.
3. A binary embedding model tailored for canonical views is proposed to preserve visual relations of images into binary codes and thus support efficient MLS with great robustness.

2 RelatedWork

2.1 Mobile Landmark Search

Ji et al. [2012] present a Location Discriminative Vocabulary Coding (LDVC) to compress Bag-of-Visual-Words (BoVW) with location awareness. Duan et al. [2013] explore multiple information sources to extract compact landmark image descriptor. Chen et al. [2014] develop a soft Bag-of-Visual Phrase (BoVP) to learn category-dependent visual phrases, by capturing co-occurrence features of neighbouring visualwords. Zhou et al. [2014] propose Scalable Cascaded Hashing (SCH) to achieve codebook-free large-scale MLS.

All the techniques mentioned above learn compact binary codes from only visual-words based features, without considering complement information from other visual modalities. This limitation makes the generated codes less discriminative.

2.2 Multimodal Hashing

Multimodal hashing has been emerging as a promising technique to generate compact binary code based on multiple features. The earliest study on this topic is Composite Hashing with Multiple Information Sources (CHMIS) [Zhang et al., 2011]. It just post-integrates linear output of features and fails to fully exploit their correlations. Kim et al. [2013] present Multi-View Anchor Graph Hashing (MVAGH) by extending Anchor Graph Hashing (AGH) [Liu et al., 2011] to gain robust representation cross multiple images. Song et al. [2013] develop Multiple Feature Hashing (MFH). By using the learned hashing hyper-plane, MFH concatenates all the features into a single vector and then maps it into binary codes. Liu et al. [2014] propose Compact Kernel Hashing (CKH) by formulating the similarity preserving problem with optimal linearly-combined multiple kernels corresponding to different features. More recently, Multi-View Latent Hashing (MVLH) [Shen et al., 2015] is proposed to incorporate multimodal features in binary representation learning by discovering the latent factors shared by multiple views. Further, distinguished from the existing methods, 2CVR aims to learn informative canonical views by capturing key characteristics of landmarks. Consequently, the generated binary codes can enjoy desirable robustness.

3 The ProposedMethod

3.1 Overview

Figure 1 illustrates the basic framework of 2CVR learning. Given a set of landmark images, the computation of compact representation 2CVR, consists of three major steps: Firstly, multimodal canonical view mining is proposed in order to efficiently discover a compact but informative canonical view set from noisy landmark image collections to capture key visual appearances. Then, in order to robustly model diverse visual contents, an intermediate representation is generated by computing multimodal sparse reconstruction coefficients between image and canonical view. Finally, compact binary codes are learned by preserving the discovered visual relations measured on canonical views.

3.2 Multimodal Canonical ViewMining

It is common that, in practice, several sceneries of landmarks are frequently photographed and disseminated by different tourists. These views of landmarks are considered as canonical views in this work and applied to cope with visual variations of query images captured by mobile devices. In this subsection, we first formally define mathematical properties of canonical view set, and then give an efficient submodular function based mining algorithm for discovery.

Definition 1. Let I denote image space, I = ¶In♦Nn=1 , N is the number of database images. Let L denote landmark space, L = ¶Lm♦Mm=1 , M is the number of landmarks in database. Lm is defined as a set of images which are recorded at the nearby position of the mth landmark. Let V denote a view set of L. It is defined as a set of images ¶vi♦♣V♣ i=1 belonging to I, V ✓ I, ♣V♣ ⌧ ♣I♣.

Definition 2. Let Rep(V) denote the visual representativeness of view set V over L. It is defined as Rep(V) = Pvi2V Rep(vi) = Pvi2V Pvj2I↪i6=j gij, g is the function which measures the feature similarity of two image views, gij is short for g(vi↪ vj). Let Red(V) denote the visual redundancy of view set V. It is defined as Red(V) = Pvi2V Red(vi) = Pvi↪vj2V↪i6=j gij.

Definition 3. Let C denote the canonical view set of L. The views involved in C can comprehensively represent diverse visual contents of landmark, and meanwhile, have less visual redundancy. In this paper, it is defined as C = argmaxV✓I↪♣V♣=T h(V)↪ h(V) = Rep(V) - Red(V), T is cardinality of canonical view set.

Lemma 1. h(V) is submodular function. That is, 8V1 ✓ V2 ✓ V↪ 8vj ◁2 V, h(V1[vj)-h(V1) ≥ h(V2[vj)-h(V2).

Lemma 2. h(V) is monotonically nondecreasing function. That is, 8V1 ✓ V2 ✓ V, h(V1)  h(V2).

As indicated in Definition 3, to discover optimal canonical view set, the function h(V) should be maximized. However, since h(V) is submodular function, the maximization of it is a NP-complete optimization problem. Fortunately, h(V) is monotonically nondecreasing with a cardinality constraint. Canonical views can be discovered near optimally by greedy strategy as following steps

Step 1: Extract visual feature for all landmark images.

Step 2: Set canonical view set as empty, C = ;.

Step 3: Iterate the following two steps for T times.

• 3.1: Compute diff(In) = h(C [ In) - h(In) for each landmark image In 2 I.
• 3.2: Select the image with the maximum diff into C, I ⇤ = argmaxIn2I diff(In), and simultaneously remove it from I, C C [ I ⇤ , I I ∩ I ⇤ .

Theorem 1. [Nemhauser et al., 1978] Let S ⇤ denote the global optimal solution that solves the combinatorial optimization problem arg maxS✓L↪♣S♣=T h(S), S denote approximate solution found by the greedy algorithm. If h(S) is nondecreasing submodular function with h(;) = 0, we can have

where ⇣ refers to the natural exponential.

As validated by Theorem 1, this greedy algorithm can achieve a result that is no worse than a constant fraction ⇣-1 ⇣ away from the optimal value. The time complexity of canonical view mining is reduced to O(NT). The canonical view discovery process can be completed efficiently. To comprehensively cover visual appearances of landmarks, canonical view mining is performed in multiple modalities, obtaining canonical view set ¶C p ♦Pp=1 , P is number of modalities. We concatenate features of canonical views and construct a matrix Ep = [ep1 ↪ ▷▷▷↪ epT ] 2 Rdp⇥T in modality p, dp is the corresponding feature dimension.

3.3 Intermediate Representation Generation

With the discovered canonical views, an arbitrary recorded landmark image either describes a specific canonical view or the cross-scenery among several particular canonical views. In both cases, visual contents of the image can be principally represented with its relations to several particular canonical views. Motivated by the observations, we calculate multimodal sparse reconstruction coefficients between image and canonical views. And the auto-generated response coefficients construct the dimensions of intermediate representation. The concrete mathematical form is

where ↵ > 0 is a constant factor that adjusts the balance between terms, ⇢ is set to be the mean of pairwise distances, ⌦ denotes the element-wise product, 1T 2 RT denotes a column vector with all ones. Xp = [xp1 ↪ ▷▷▷↪ xpN ] 2 Rdp⇥N denotes features of database images in modality p. Y p = [yp 1 ↪ ▷▷▷↪ ypN ] 2 RT⇥N denotes modality-specific canonical view based intermediate representation. Each column has r non-zeros coding coefficients. dist(xpn ↪Ep ) = [dist(xpn ↪ ep1 )↪ ▷▷▷↪ dist(xpn ↪ epT )]. The problem in (1) can be efficiently solved by using the Alternating Direction Method of Multipliers (ADMM) [Elhamifar and Vidal, 2013]. After solving, we concatenate the calculated Y p and construct dimensions of intermediate representation

Remark. The intermediate representation can effectively characterize diverse visual contents by adaptively adjusting the response coefficients on canonical views. It lays the solid foundation for subsequent binary embedding.

3.4 Binary EmbeddingModel

Based on the intermediate representation, we design a binary embedding model to learn final binary representation.

Due to approximate canonical view mining and multimodal information integration, the intermediate representation generation inevitably brings about noises and redundancies. It is very important to remove them during binary embedding to avoid disturbance. To achieve this goal, matrix factorization is applied in this paper to decompose intermediate features into the latent binary bits and guarantee them to be orthogonal to each other. Besides, a graph regularizer is constructed to preserve visual relationships among images. That is, if two landmark images have similar visual distributions on canonical views, they are constrained to be projected to close points in hamming space. Moreover, since queries are out of database and continuously flowing into database when time passes by, we learn linear projection for out-ofsample extension. Therefore, by integrating the aforementioned considerations, the overall binary embedding is formulated as

where λ↪ β↪ γ > 0 adjust the balance of terms. ♣♣Y -UV ⇤ ♣♣2F is matrix factorization term, V ⇤ (V ⇤ )T = Ic is bit orthogonality constraint. Tr(V ⇤L(V ⇤ )T ) is graph regularizer which preserves visual relations of landmark images on canonical views. Tr(·) is trace operation, L is graph Laplacian matrix, which is constructed based on intermediate representation. It measures visual relations of images on canonical views. ♣♣V ⇤ -W TY ♣♣2F +γ♣♣W♣♣2F is binary projection learning term, W 2 RTP⇥c is linear projection matrix to be learned, c is binary code length, ♣♣V ⇤ -W TY ♣♣2F is to reduce the loss between binary codes and the projected values. It is worth noting that as linear projection is leveraged, the online mobile landmark search process can be efficient.

When directly imposing V ⇤ 2 ¶-1↪ 1♦c⇥N , problem (3) will become NP-hard. Thus we relax this discrete constraint to V 2 Rc⇥N and derive the following relaxed form

The optimal W↪U that solves Eq.(4) can be expressed in terms of Y and V . We can derive the following theorem.

Theorem 2. Let W↪U↪ V and Y be defined as before. Then the optimal W that solves learning problem in (4) is given by W = (Y Y T +γI)-1Y V T ↪ U = Y V T . The relaxed minimum problem in (4) is equivalent to the following simple problem

Proof. We calculate the derivation of the objective function in Eq.(4) w.r.t U and set it to be zero. Thus, we have

By replacing U into Eq.(4), we can derive that

Similarly, by calculating the derivation of the objective function in Eq.(4) w.r.t W and setting it to be zero, we can have

Let Q = (Y Y T + γI)-1 , then W = QY V T . By replacing W into Eq.(4), we can derive that

By summing three terms together, we find that the relaxed minimum problem in (4) is equivalent to

where A = L-λY TY +β(I -Y TQY )↪ Q = (Y Y T +γI)-1 . This completes the proof of the theorem.

It turns out that the problem in Eq.(4) has a close-form solution. The rows of optimal solution (We denote it as ˜ V ) are given as the c eigenvectors with minimal eigenvalues of the matrix A. After that, the optimal binary projection W can be calculated as Eq.(6).

However, solving continuous ˜ V will generate binary quantization error. Inspired by [Gong et al., 2013], we could apply orthogonal transformation to rotate ˜ V to align with hypercube ¶◦1♦c⇥N as close as possible, and thus reduce the quantization error. But, it would be feasible only if the rotation does not change the minimum of Eq.(5). Fortunately, it can be easily validated that, for an arbitrary orthogonal rotation matrix ˜R, we can have minV V T=Ic Tr(VAV T ) = minRV V TRT=Ic Tr(RVAV TRT ). Hence, it is possible to learn an orthogonal rotation matrix R which guarantees that R ˜ V can simultaneously achieve the minimum objective function value in Eq.(5) and binary embedding errors. Formally, R is learned by

This reduces to the Orthogonal Procrustes Problem (OPP) [Yu and Shi, 2003]. A local optimal solution can be obtained by alternating minimization between V ⇤ and R. Afterwards, the final binary projection matrix is adjusted as W = WR. Given a landmark image q, we first extract intermediate representation Yq as Eq.(2). Its binary codes are calculated as V ⇤ q = sgn(W TYq), where sgn(x) denotes the sign function. It returns 1 if x > 0 and -1 otherwise.

4 Experiments

Experimental Datasets and Setting. Three real landmark datasets are applied for empirical study: Oxford5K [Philbin et al., 2007], Paris6K [Philbin et al., 2008], and Paris500K [Weyand and Leibe, 2013] 1 . Oxford5K is comprised of 5,062 Oxford landmark images in 17 categories. Paris6K consists of 6,412 Paris landmark images in 12 categories. Paris500K contains 41,673 images with clustering ground truth which describe 79 landmarks. For Oxford5K and Paris6K, 10%, 20%, and 70% images are used as query images, training images, and database images, respectively. For Paris500K, the corresponding ratios are 10%, 10%, and 80%. Both query and database images appear with great visual diversity in three datasets. Each image is represented by features in 5 visual modalities: 81-D Color Moments (CM) [Yu et al., 2002], 58D Local Binary Pattern (LBP) [Wang et al., 2009], 80-D Edge Direction Histogram (EDH) [Park et al., 2000], and 1,000-D BoVW 2 [Sivic and Zisserman, 2003], 512-D GIST [Oliva and Torralba, 2001].

1 In this paper, the maximum number of images in each category is limited to 2000 to avoid bias.

Evaluation Metrics. In experimental study, mean Average Precision (mAP) [Liu et al., 2014; Shen et al., 2015] is adopted as main evaluation metric. The number of returned images is set as 100 to collect experimental results. Furthermore, Precision-Scope curve is also reported to demonstrate the retrieval performance variations with the number of retrieved images. Binary code length c on all datasets is varied in the range of ¶32↪ 48↪ 64↪ 128♦, and the search scope is ranged from 100 ⇠1000 with step size 100.

Competitors. Since 2CVR is learned by unsupervised learning on multiple visual modalities, we compare it with state-of-the-art unsupervised multimodal binary representation generation approaches. They include 3 : CHMIS [Zhang et al., 2011], MVAGH [Kim and Choi, 2013], MFH [Song et al., 2013], CMKH [Liu et al., 2014], and MVLH [Shen et al., 2015]. Besides, we also compare 2CVR with several state-of-the-art unimodal approaches: SPH [Weiss et al., 2008], PCAH [Wang et al., 2010], AGH [Liu et al., 2011], ITQ [Gong et al., 2013], and SGH [Jiang and Li, 2015]. For them, multimodal features are concatenated into a unified vector for subsequent learning. The involved parameters of the compared approaches are strictly adjusted to report the maximum performance according to the relevant literature. For 2CVR, the best performance is achieved when λ = 1↪ β = 104 ↪ γ = 104 . The best canonical view size T is set to 100 on Oxford5K and Paris6K, and 300 on Paris500K. The best number of nearest canonical views r in Eq.(1) is set to 70 on Oxford5K and Paris6K, and 200 on Paris500K. ↵ in Eq.(1) is set to 10-4 to maximize the performance.

2 128-D SIFT [Lowe, 2004] is employed as local descriptor.

3 For CHMIS, MFH, CMKH, SPH, PCAH, AGH, ITQ, and SGH, implementation codes of them are provided by the authors. For

Performance Comparison. We report mAP results and Precision-Scope curves on Paris500K of all approaches in Table 1 and Figure 2, respectively. From the presented results, we can easily find that 2CVR consistently outperforms the competitors on all code lengthes and datasets. It is interesting to find that, even with less binary bits, 2CVR can achieve higher mAP than many competitors with longer binary codes. Further, Figure 2 shows that, on Paris500K and 128 bits, the precision gain of 2CVR over the second best approach is more than 10%, and it becomes larger when more images are returned. Moreover, we observe that performance improvement on Paris500K is more than that obtained on Oxford5K and Paris6K. Since images in Paris500K have more diverse visual appearances, this experimental phenomenon validates the desirable property of 2CVR on accommodating the visual variations. Finally, we observe that the retrieval performance of 2CVR is steadily improved when binary code length increases. However, we don't gain similar observations for many approaches studied in this experimental study. This is because 2CVR ensures bit orthogonality constraint in binary code learning. The design guarantees the learned binary bits to achieve less information redundancy. More binary bits will enable 2CVR to gain higher discriminative capability.

MVAGH and MVLH, we implement them according to the relevant literature.

Canonical View or Not? To see how the canonical view mining can benefit compact representation learning, we first compare the performance of 2CVR with the one which performs binary embedding Eq.(3) directly on raw concatenated multiple low-level features. Table 2 presents the detailed comparative results. From it, we easily find that 2CVR can consistently yield better performance. On three datasets, the maximum search precision improvements reach about 3%, 4%, and 26%, respectively. The performance improvement is attributed to the fact that, canonical views capture key visual contents of landmarks, diverse visual contents can be robustly accommodated, and thus binary codes have better robustness.

Then, we investigate the effects of canonical view mining in multiple modalities. We compare the performance of 2CVR with the approaches that perform binary embedding Eq.(3) on only unimodal canonical view set. We denote them directly with the corresponding modality names: CM, LBP, EDH, BOVW, and GIST respectively. Table 3 presents the main results. It demonstrates that 2CVR can achieve the best performance. The reason is that, with multimodal learning, canonical view set can cover more visual variations and thus 2CVR can enjoy better robustness. All the above results clearly demonstrate that 2CVR adopts a reasonable strategy by employing canonical views for MLS.

Finally, we validate the effects of the proposed submodular function based canonical view selection approach. We compare the performance of 2CVR with two variants of method which discover canonical views by random selection and kmeans, respectively. The detailed comparison results are presented in Table 4. It can be easily observed that 2CVR can consistently achieve better performance. These results demonstrate the effectiveness of submodular function on discovering canonical views of landmarks.

Parameter Study. We investigate the performance variations of 2CVR with parameters. Due to the space limit, we observe the performance variations with λ, β, and γ. They are used in Eq.(3) to play trade-off between terms. We observe the performance variations with respect to two parameters while fixing the remaining one parameter. We report results on Oxford5K when binary code length is 128. Similar results can be found on other code lengths and datasets. Fig-

(a) λ is fixed to 1 (b) β is fixed to 104 (c) γ is fixed to 104

Figure 3: mAP variations with parameters on Oxford when binary code length is 128. This figure is best viewed with pdf magnification.

ure 3 presents results. From it, we can find the performance of 2CVR is stable on a range of parameters.

5 Conclusions

This paper proposes 2CVR to support efficient and robust mobile landmark search. The design of 2CVR has basis in reality that only canonical views are frequently photographed and disseminated by different tourists, and they naturally provide effective visual representation basis of landmarks. Experimental results on three real landmark datasets demonstrate that our proposed approach can achieve superior performance compared with several state-of-the-art approaches.

Acknowledgments

Lei Zhu and Jialie Shen are supported by the Singapore Ministry of Education Academic Research Fund Tier 2 (MOE Ref: MOE2013-T2-2-156)