5.2.1 The Proposed Mining Scheme

3D sphere coding. Formally speaking, for each reference image I_i(i ∈ [1,n_t]) of the tth ToI (t ∈ [1,M]), suppose there are J local descriptors L(i) = [L₁(i),…,L_J(i)] extracted from I_i, which is quantized into an m-dimensional bag-of-words histogram V(i) = [V₁(i),…,V_m(i)]. We denote the spatial positions of L(i) as S(i) = [S₁(i),…,S_J(i)], where each S_j(i) (j ∈ [1,J]) is the 2D or 3D spatial position of the jth local descriptor. For each S_j(i), we scan its spatial k-nearest neighborhood to identify all concurrent words

$\begin{array}{l}\hfill {\mathbf{T}}_j(i)=\left\{\right.L_{j^{\prime }}(i)|L_{j^{\prime }}(i)\in \mathbf{L}(i),S_{j^{\prime }}(i)\in \mathrm{kNN}\left(\right.S_j(i)\left)\right.\left\}\right.\end{array}$

where T_j(i) (if any) is called an “transaction” built for S_j(i) in I_i. We denote all transactions in I_i with order K as:

$\begin{array}{l}\hfill {\mathbf{T}}^k(i)=\left\{\right.{\mathbf{T}}_j(i){\left\}\right.}_{j\in [1,J]}\end{array}$

All k-order transactions found for images $[I_1,\dots ,I_{n_t}]$ in the tth ToI is defined as T^k(ToI_t) = {T^k(1),…,T^k(n_t)}. The goal of pattern mining is to mine n_t patterns from $\left\{\right.{\mathbf{T}}^k({\mathrm{ToI}}_t){\left\}\right.}_{k=1}^K$, i.e., ${\mathbf{P}}_t=\left\{\right.P_1,\dots ,P_{n_t}\left\}\right.$ form each tth ToI and ensemble them together as $\left\{\right.{\mathbf{P}}_t{\left\}\right.}_{t=1}^M$.³

While the traditional pattern candidates are built based on the coding the 2D concurrences of visual words within individual reference images, we propose to search the k-nearest neighbors in the 3D point cloud of each tth ToI. Such a point cloud is constructed by structure-from-motion over the reference images with bundle adjustment [121]. Figure 5.3 shows several 3D sphere coding examples in the 3D point clouds of representative landmarks as detailed in Section 5.4.

Distance-based pattern mining. Previous works in visual pattern mining mainly resort to Transaction-based Colocation pattern Mining (TCM). For instance, works in [69–71] built transaction features by coding the k-nearest words in 2D.⁴ A transaction in TCM can be defined by coding the 2D spatial layouts of neighborhood words. Then frequent itemset mining algorithms like a Priori [122] are deployed to discover meaningful word combinations as patterns, which typically check the pattern candidates from orders 1 to K.

TCM can be formulated as follows: Let {V₁,V₂,…,V_m} be the set of all potential items, each of which corresponds to a visual word in our case. Let D = {T₁,T₂,…,T_n} be all possible transactions extracted as above, each is a possible combination of several items within V after spatial coding. Here for simplification, we use i ∈ [1,n] to denote all transactions discovered with orders 1 to K and in ToIs 1 to M. Let A be an “itemset” for the a given transaction T, we define the support of an itemset as

$\begin{array}{l}\hfill \mathrm{support}(\mathbf{A})=\frac{\left|\right.\{\mathbf{T}\in \mathbf{D}|\mathbf{A}\subseteq \mathbf{T}\}\left|\right.}{|\mathbf{D}|},\end{array}$

If and only if support(A) ≥ s, the itemset A is defined as a frequent itemset of D, where s is the threshold to restrict the minimal support rate. Note that any two T_i and T_j are induplicated.

We then define the confidence of each frequent itemset as:

$\begin{array}{ll}\hfill \mathrm{condifence}(\mathbf{A}\to \mathbf{B})& =\frac{\mathrm{support}(\mathbf{A}\cup \mathbf{B})}{\mathrm{support}(\mathbf{A})}\hfill \\ \hfill & =\frac{\left|\left\{\mathbf{T}\in \mathbf{D}|(\mathbf{A}\cup \mathbf{B})\subseteq \mathbf{T}\right\}\right|}{\left|\{\mathbf{T}\in \mathbf{D}\right|\mathbf{A}\subseteq \mathbf{T}\}|},\hfill \end{array}$

where A and B are two itemsets. The confidence in Equation (5.4) is defined as the maximal likelihood that B is correct in the case that A is also correct. Confidence-based restriction is to guarantee that the found patterns can discover the minimal item subsets, which are most helpful in representing the visual features at order k ∈ [2,K].

To give a minimal association hyperplane to bound A, an Association Hyperedge of each A is defined as:

$\begin{array}{l}\hfill \mathrm{AH}(\mathbf{A})=\frac{1}{N}\mathrm{confidence}\left((\mathbf{A}-\{V_i\})\to V_i\right).\end{array}$

Finally, by checking all possible itemset combinations in D from order 2 to K, the itemsets with support() ≥ s and AH ≥ γ are defined as frequent patterns.

One crucial issue lies in TCM would generate repeated patterns in texture regions containing dense words. To address this issue, distance-based Colocation pattern mining (DCM) is proposed with two new measures named participation ratio (pr) and participation index (pi).

First, a R-reachable measure is introduced as the basis of both pi and pr: Two words V_i and V_j are R-reachable when

$\begin{array}{l}\hfill \mathrm{dis}(V_i,V_j)<d_{\mathrm{thres}},\end{array}$

where dis() is the distance metric such as Euclidean and d_thres is the distance threshold. Subsequently, for a given word V_i, we define its partition rate pr(V,V_i) as the percentage of subset V −{V_i} that are R-reachable:

$\begin{array}{l}\hfill \mathrm{pr}(\mathbf{V},V_i)=\pi \frac{\left(\right.\left|\right.\mathrm{instance}(\mathbf{V})\left|\right.\left)\right.}{\left|\right.\mathrm{instance}(V_i)\left|\right.},\end{array}$

where π is the relational projection operation with deduplication. The participation index pi is defined as:

$\begin{array}{l}\hfill \mathrm{pi}(\mathbf{V},V_i)={\min }_{i=1}^m\{\mathrm{pr}(\mathbf{V},V_i)\},\end{array}$

where pi describes the frequency of subset V − V_i in the neighborhood. Note that only item subsets with pi larger than a give threshold is defined as patterns in DCM.

Gravity distance R-reachable: In many cases, the Euclidean distance cannot discriminatively describe the colocation visual patterns, which is due to it ignores the word discriminability and scale in building items. Intuitively, words from the same scale tend to share more commonsense in building items, and more discriminative words also produce more meaningful items. We then proposed a novel gravity distance R-reachable (GD R-reachable) to incorporate both cues. Two words V_i and V_j are GD R-reachable once R_i,j < Cr_ir_j in the traditional DCM model, where r_i and r_j are the local feature scales of V_i and V_j, respectively, C is the fixed parameter, and R_i,j = dis(V_i,V_j) is the Euclidean distance of two words.

For interpretation, we can image that every word has a certain “gravity” to the other words, which is proportional to the square of its local feature scale. If this gravity is larger than a minimal threshold F_min, we denote these two words as GD R-reachable:

$\begin{array}{l}\hfill \begin{array}{ll}{F}^{i,j}& =\epsilon \frac{\pi {(r_i)}^2\pi {(r_j)}^2}{{(R_{i,j})}^2},\epsilon \text{is a constant}\\ F_{i,j}>F_{\min }& \to \epsilon \frac{\pi {(r_i)}^2\pi {(r_j)}^2}{{(R_{i,j})}^2}>F_{\min }\to R_{i,j}<C{r}_i{r}_j.\end{array}\end{array}$

Similar to DCM, the input of the gravity distance-based mining is all instances of visual words. Each instance contains the following attributes: original local features, visual word ID, location, and scale of this local feature (word instance). To unify the description, we embed the word ID of each feature with its corresponding location into the mining. Then, we run the similar procedure as in DCM to mine colocation patterns. Algorithm 5.1 outlines the workflow of our gravity distance-based visual pattern mining. Figure 5.4 shows some case studies of the mined patterns between the gravity-based pattern mining and the Euclidean distance-based pattern mining.

5.2.2 Sparse Pattern Coding

Sparse coding formulation. Given the mined pattern collection P, not all patterns are equivalently important and discriminative in terms of feature representation. Indeed, there are typically redundancy and noise in this initial pattern mining results. However, how to come up with a compact yet discriminative pattern-level features are left unexploited in the literature. In this section, we formulate the pattern-level representation as a sparse pattern coding problem, aiming to maximally reconstruct the original bag-of-words histogram using a minimal number of patterns.

Formally speaking, let P = {P₁,…,P_L} be the mined patterns with maximal order K. In online coding, given the bag-of-words histogram V(q) = [V₁(q),…,V_m(q)] extracted from image I_q, we aim to encode V(q) by using a compact yet discriminative subset of patterns, say $\mathbf{P}(q)\subset \mathbf{P}$. We formulate this target as seeking an optimal tradeoff between the maximal reconstruction capability and the minimal coding length:

$\begin{array}{l}\hfill arg\underset{\mathbf{w}}{min}\sum _{i=1}^N||\mathbf{V}(i)-{\mathbf{w}}^T\mathbf{P}(i)|{|}_2+\alpha ||\mathbf{w}|{|}_1,\end{array}$

where P is the patterns mined previously, from which a minimal set is selected to lossy reconstruct each bag-of-words histogram V(i) as close as possible. w serves as a weighted linear combination of all nonzero patterns in P, which pools patterns to encode each V(i) as:

$\begin{array}{l}\hfill f_{\mathbf{P}}(i)=w_1{P}_1+w_2{P}_2+,\cdots ,w_m{P}_m,\end{array}$

where [w₁,,w_m] is the weighted vector learned to reconstruct V(i) in Equation (5.10). Each w_j is assigned either 0 or 1, performing a binary pattern selection.

Learning with respect to Equations (5.10) and (5.13) are achieved by spare coding over the pattern pool P. While guaranteeing the real sparsity through $\mathcal{L}$ is intractable, we approximate a sparse solution for the coefficients w using $\mathcal{L}$ penalty, which results in a Lasso-based effective solution [124].

Finally, we denote the selected pattern subset as Q_selected, which contains n_selected patterns as $[Q_1,\dots ,Q_{n_{\mathrm{selected}}}]$. n_selected is typically very small, say 100. Therefore, each reference or query image is represented as an n_selected-bin pattern histogram.

Supervised coding. Once the supervised labels ${\{L_i\}}_{i=1}^N$ (e.g., category label or prediction from a compensative source) for reference image ${\{I_i\}}_{i=1}^N$ are also available, we can further incorporate L_i to refine the coding of Equation (5.10) as:

$\begin{array}{l}\hfill arg\underset{\mathbf{w}}{min}\sum _{i=1}^N||\mathbf{V}(i)-{({\mathbf{w}}^T\mathbf{u})}^T\mathbf{P}(i)|{|}_2+\alpha ||\mathbf{w}|{|}_1,\end{array}$

where we integrate the supervised label ${\{L_i\}}_{i=1}^N$ into the coding function of P for I(i) as:

$\begin{array}{l}\hfill {({\mathbf{w}}^T\mathbf{u})}^T\mathbf{P}(i)=w_1{u}_1{P}_1+w_2{u}_2{P}_2+,\cdots ,w_m{u}_m{P}_m.\end{array}$

[u₁,…,u_m] adds the prior distribution of patterns to bias the selection of [w₁,…,w_m], where u_j is the discriminability of the jth pattern based on its information gain to L_i:

$\begin{array}{l}\hfill u_j=H(L_i)-H(L_i|P_j)\end{array}$

Here, H(L_i) is the prior of label L_i given I_i, H(L_i|P_j) is the conditional entropy of label L_i given P_j, which is obtained by averaging the intraclass observation of P_j divided by the interclass distribution of P_j:

$\begin{array}{l}\hfill H(L_i|P_j)=\frac{p(P_j|L_j)}{\sum _{l}p(P_j|L_l)}.\end{array}$

In this sense, the definition of supervised label L_i is quite flexible, e.g., category labels or positive/negative tags, which also allows the case of missing labels.

In terms of compact visual descriptor, CBoP preserves the higher order statistics comparing to the transitional nonzero coding scheme [112] as well as the state-of-the-art boosting-based codeword selection scheme [120]. Different from all previous unsupervised descriptor learning schemes [69–72, 112], CBoP further provides a supervised coding alternative as an optional choice, which yet differs from the work in [120] that demands online side information from the query.

PhotoTourism. First, we validate on the image patch correspondence benchmark. It contains over 100,000 image patches with correspondence labels generated from the point clouds of Trevi Fountain (Rome), Notre Dame (Paris), and Half Dome (Yosemite), all of which are produced by the PhotoTourism system [121]. Each patch correspondence consists of a set of local patches, which is obtained by projecting a given 3D point from the point cloud back to multiple reference images and cropping the corresponding salienct regions.⁶ Some exemplar patches obtained through the above procedure are shown in Figure 5.6.

10M landmark photos. To validate our CBoP descriptor in the scalable image retrieval application, we have also collected over 10 million geo-tagged photos from both Flickr and Panoramio websites. We crawled photos tagged within five cities, i.e., Beijing, New York City, Lhasa, Singapore, and Florence. This dataset is named as 10M landmarks. Some exemplar photos are shown in Figure 5.7.

We use k-means clustering to partition photos of each city into multiple regions based on their geographical tags. For each city, we select the top 30 densest regions as well as 30 random regions. We then ask a group of volunteers to identify one or more dominant landmark views for each of these 60 regions. For an identified dominant view, all their near-duplicate photos are manually labeled in its belonged region and nearby regions. Eventually, we have 300 queries as well as their ground truth labels (corrected matched photos) as our test set.

PKUBench. We also evaluate on several typical mobile visual search scenario using PKUBench, which is a public available mobile visual search benchmark. This benchmark contains 13,179 scene photos organized into 198 landmark locations, captured by both digital and phone cameras. There are in total 6193 photos captured from digital cameras and 6986 from phone cameras respectively. We recruited 20 volunteers in data acquisition. Each landmark is captured by a pair of volunteers with a portable GPS device (one using digital camera and the other using phone camera). Especially, this benchmark includes four groups of exemplar mobile query scenarios (in total 118 images):

• Occlusive query set: 20 mobile queries and 20 corresponding digital camera queries, occluded by foreground cars, people, and buildings.

• Background cluttered query set: 20 mobile queries and 20 corresponding digital camera queries, captured far away from a landmark, where GPS search yields worse results due to the signal bias of nearby buildings.

• Night query set: 9 mobile phone queries and 9 digital camera queries, where the photo quality heavily depends on the lighting conditions.

• Blurring and shaking query set: 20 mobile queries with blurring or shaking and 20 corresponding digital camera queries without any blurring or shaking.

5.4.2 Evaluation Criteria

Effectiveness: We use mean Average Precision (mAP) to evaluate our performance, which is also widely used in the state-of-the-art works [24, 27, 30, 113, 125]. mAP reveals the position-sensitive ranking precision by the returning list:

$\begin{array}{l}\hfill MAP@N=\frac{1}{N_q}\sum _{i=1}^{N_q}\left(\frac{\sum _{r=1}^{N}P(r)rel(r)}{\min (N,\#-relevant-images)}\right)\end{array}$

where N_q is the number of queries, r is the rank, N is the number of related images for query i, rel(r) is a binary function on the relevance of r, and P(r) is the precision at the cut-off rank of r.

Note that here we have a min operation between the top N returning and #-relevant-images. In a large-scale search system, there are always over hundreds of ground truth relevant images to each query. Therefore, dividing by #-relevant-images would result in a very small MAP. Alternatively, a better choice is the division by the number of returning images. We use min(N, #-relevant-images) to calculate MAP@N.⁷

Efficiency: We use the descriptor compactness, i.e., the size of the descriptor stored in the memory or hard disk (for instance 1KB per descriptor etc.).

5.4.3 Baselines

• Bag-of-words: Transmitting the entire BoW has the lowest compression rate. However, it provides an mAP upper bound to the other BoW compression strategies.

• 2D patterns: Instead of obtaining the initial pattern candidates through 3D sphere coding, using the point cloud, we adopt the traditional 2D spatial coding from individual reference images as initially proposed in [72]. This baseline validates the effectiveness of our proposed 3D sphere coding strategy.

• LDA [115]: One straightforward alternative in abstracting compact features from the bag-of-words histogram is the topic model features [78, 114, 115]. In this paper, we implement the well-used Latent Direchellet Allocation (LDA)-based feature in [115] as our baseline.

• CHoG [113]: We also compare our CBoP descriptor to the CHoG local descriptor, which is a state-of-the-art alternative as introduced in [113].

• Tree histogram coding [112]: In terms of image-level compact descriptor, we further implement the tree histogram coding scheme proposed by Chen et al. [112], which is a lossless BoW compression that uses residual coding to compress the BoW histogram.

• LDVC [120]: Finally, we compare our CBoP descriptor with the state-of-the-art compact descriptor to the best of our knowledge [120], which adopts location discriminative coding to boost a very compact subset of words. To compare to our unsupervised CBoP, we used reference images from the entire dataset (i.e., landmark photos from the entire city) to train the LDVC descriptor. To compare to our supervised CBoP, we adopt the location label to train a location sensitive descriptor as in [120].

5.4.4 Quantitative Performance

Efficiency analysis. We deploy the low bit rate mobile visual search prototype on HTC Desire G7 as a software application. The HTC DESIRE G7 is equipped with an embedded camera with maximal 2592 × 1944 resolution, a Qualcomm MSM7201A processor at 528 MHz, a 512M ROM + 576M RAM memory, 8G extended storage and an embedded GPS. Table 5.1 shows the time cost with comparisons to state-of-the-arts in [112, 120, 125]. In our CBoP descriptor extraction, the most time-consuming part is the local feature extraction, which can be further accelerated by random sampling, instead of using the interest point detectors [9, 113].

Rate distortion analysis. To compare our CBoP descriptors to the baselines [112, 113, 125], we give the rate distortion analysis in Figure 5.9, where the compression rates correspond to the descriptor lengths of our CBoP descriptor and the alternatives, while the search distortions correspond to the mAP drops of different methods, respectively. As shown in Figure 5.9, our CBoP descriptor has achieved the best tradeoff in the rate distortion evaluation. It reports the highest compression rate with a comparable distortion (by viewing Figure 5.9 horizontally), as well as the highest ranking performance with a comparable compression rate (by viewing Figure 5.9 vertically). In addition, without supervised learning, our CBoP descriptor can still achieve better performance comparing to all alternatives and state-of-the-arts [112, 113, 125]. Figure 5.8 shows some examples in the extreme mobile query scenarios for more intuitive understanding.