3.2.1 Feature-Space Density-Field Estimation

To begin, we first introduce the definition of density field, which estimates the density of each SIFT point in the SIFT feature space as a discrete approximation. The density of a SIFT point in 128-dimensional SIFT feature space is defined by

$\begin{array}{l}\hfill D(i)=\frac{1}{n}{\sum }_{j=1}^n{e}^{-||x_i-x_j|{|}_{L_2}},\end{array}$

where D(i) is the point density of the i^th SIFT point, n is the total number of SIFT points in this dataset, and x_j is the j^th SIFT point. We adopt L2 distance to evaluate the distance between two SIFT points.

To make it efficient, we resort to estimating the density of each SIFT point using only its local neighbors as an approximation as follows:

$\begin{array}{l}\hfill \tilde{D}(i,m)=\frac{1}{m}{\sum }_{k=1}^m{e}^{-||x_i-x_j|{|}_{L_2}},\end{array}$

where $\tilde{D}(i,m)$ is the point density of the i^th SIFT feature in its m neighborhood. We only need to calculate the local neighbors of SIFT by: (1) Cluster database features into k clusters: O(k * h * l), with h iterations to l points; and (2) nearest neighbor search in each cluster: O(l2/k). By a large k (e.g., 2000), our DML would be very efficient. Using a heap structure, it could be even faster.

3.2.2 Learning a Metric for Quantization

From the above step, point-based density is estimated by neighborhood approximation. Subsequently, the similarity metric in hierarchical k-means are refined by density-based adaption as:

$\begin{array}{l}\hfill Similarity(c,i)=AveDen(c)\times Dis(C_{Center},i).\end{array}$

Similarity(c,i) is the similarity metric in DML-based k-means, which is the similarity between the c^th cluster and the i^th point; AveDen(c) is the average density of the SIFT points in the c^th cluster; and Dis(c_center,i) is the distance between the center SIFT point of cluster c and the i^th SIFT point.

We explain this operation as follows: From the viewpoint of information theory, the generation of a “visual word” would cause information loss in the hierarchical quantization process. In particular, hierarchical k-means quantizes the sparser points with larger steps than the denser points. Therefore, the information loss is much more severe in the “probable informative” points (less likely to appear in most images) than the “probable uninformative” points (more likely to appear in most images). The proposed DML method decreases the overall quantization error by shortening the quantization steps for sparser regions to represent the “meaningful” points more precisely. Similar to textual words, the sparser regions in the SIFT feature space could be analogized to more meaningful textual words while the denser regions could be compared to less meaningful textual words, or even “stop words”. We demonstrate our inference by investigating the feature-word frequency in Figure 3.2. Our method can be also analogized to asymmetry quantization in signal processing.

To see how the DML-based method reduces the overall quantization error, we view the information loss of quantization using its weighted quantization error, in which the weight means the informative degree of the quantized word, which is evaluated by its IDF value. We denote the quantization error of the i^th word as QA(i) (QA(i) > 0):

$\begin{array}{l}\hfill QA(i)={\sum }_{j=1}^{m_i}{\sum }_{k=1}^{128}({F_{ij}^k}^2-{({\tilde{F}}_i^k)}^2),\end{array}$

where $F_{ji}^k$ is the k^th feature dimension in the j^th SIFT point of the i^th cluster, ${\tilde{F}}_i^k$ is the k^th feature dimension of the i^th cluster center, m_i is the number of SIFT points in this cluster, and n is the number of words.

To evaluate the weighted quantization errors between the DML method and the original method, we compare their weighted signal-ratio rates as follows:

$\begin{array}{ll}\hfill \frac{SN{R}_{DML}}{SN{R}_{Org}}& =\frac{P_{Signal}^{DML}}{P_{Noise}^{DML}}/\frac{P_{Signal}^{Org}}{P_{Noise}^{Org}}=\frac{\int x^2{p}_x(x)dx}{\int {[{\mathrm{\Delta }}_{n_{DML}}(x)]}^2{p}_x(x)dx}/\frac{\int x^2{p}_x(x)dx}{\int {[{\mathrm{\Delta }}_{n_{Org}}(x)]}^2{p}_x(x)dx}\hfill \\ \hfill & =\frac{\int {[{\mathrm{\Delta }}_{n_{Org}}(x)]}^2{p}_x(x)dx}{\int {[{\mathrm{\Delta }}_{n_{DML}}(x)]}^2{p}_x(x)dx},\hfill \end{array}$

where w_i is the IDF of the i^th cluster as its word weight and p_x(x) and Δ_n(x) are the sampling probability and squared input-output difference of x, respectively. In its discrete case, Equation (3.5) can be replaced as Equation (3.6), in which we denote the DML case by superscript′ (such as n′, j″, and w_i′):

$\begin{array}{l}\hfill \frac{SN{R}_{DML}}{SN{R}_{Org}}=\frac{\sum _{i=1}^n(w_i\sum _{j=1}^{m_i}\sum _{k=1}^{128}{(F_{ij}^k-{\tilde{F}}_i^k)}^2)}{\sum _{i^{\prime }=1}^{n^{\prime }}(w_i^{\prime }\sum _{j^{\prime }=1}^{m_i^{\prime }}\sum _{k=1}^{128}{(F_{i^{\prime }{j}^{\prime }}^k-{\tilde{F}}_{i^{\prime }}^k)}^2)}\end{array}$

$\begin{array}{l}\hfill Constrainedby:{\sum }_{i=1}^n{w}_i={\sum }_{i^{\prime }=1}^{n^{\prime }}{w}_{i^{\prime }}\end{array}$

The above equation can be further rewritten as follows:

$\begin{array}{ll}\hfill \frac{SN{R}_{DML}}{SN{R}_{Org}}& =\frac{\sum _{k=1}^{128}\sum _{i=1}^n(w_i(\sum _{j=1}^{m_i}{F}_{ij}^{k^2}-\sum _{j=1}^{m_i}2F_{ij}^k{\tilde{F}}_i^k+m_i{({\tilde{F}}_i^k)}^2))}{\sum _{k=1}^{128}{A}_{i^{\prime }=1}^{n^{\prime }}(w_{i^{\prime }}(\sum _{j^{\prime }=1}^{m_{i^{\prime }}}{F}_{i^{\prime }{j}^{\prime }}^{k^2}-\sum _{j^{\prime }=1}^{m_{i^{\prime }}}2F_{i^{\prime }{j}^{\prime }}^k{\tilde{F}}_{i^{\prime }}^k+m_{i^{\prime }}{({\tilde{F}}_{i^{\prime }}^k)}^2))}\hfill \\ \hfill & =\frac{\sum _{k=1}^{128}\sum _{i=1}^n(w_i(\sum _{j=1}^{m_i}{F}_{ij}^{k^2}-2m_i{({\tilde{F}}_i^k)}^2+m_i{({\tilde{F}}_i^k)}^2))}{\sum _{k=1}^{128}\sum _{i^{\prime }=1}^{n^{\prime }}(w_{i^{\prime }}(\sum _{j^{\prime }=1}^{m_{i^{\prime }}}{F}_{i^{\prime }{j}^{\prime }}^{k^2}-2m_{i^{\prime }}{({\tilde{F}}_{i^{\prime }}^k)}^2+m_{i^{\prime }}{({\tilde{F}}_{i^{\prime }}^k)}^2))}\hfill \\ \hfill & =\frac{(\sum _{i=1}^n(w_i\sum _{k=1}^{128}(\sum _{j=1}^{m_i}{F}_{ij}^{k^2}-m_i{({\tilde{F}}_i^k)}^2)))}{\sum _{i^{\prime }=1}^{n^{\prime }}(w_{i^{\prime }}\sum _{k=1}^{128}(\sum _{j^{\prime }=1}^{m^{i^{\prime }}}{(F_{i^{\prime }{j}^{\prime }}^k)}^2-m_{i^{\prime }}{({\tilde{F}}_{i^{\prime }}^k)}^2)).}\hfill \end{array}$

The SIFT space is quantized into equal-numbered words, hence n = n′. Indeed, in Equation (3.8), ${\sum }_{k=1}^{128}({}_{j=1}^{m_i}{F_{ij}^k}^2-m_i{({\tilde{F}}_i^k)}^2)$ is the quantization error in the i^th cluster with m_i points, identical to QA(i). Therefore, Equation (3.8) can be viewed as:

$\begin{array}{ll}\hfill \frac{SN{R}_{DML}}{SN{R}_{Org}}& =\frac{\sum _{i=1}^n(w_i\sum _{j=1}^{m_i}\sum _{k=1}^{128}({F_{ij}^k}^2-{({\tilde{F}}_i^k)}^2))}{\sum _{i^{\prime }=1}^n(w_{i^{\prime }}\sum _{j^{\prime }=1}^{m_{i^{\prime }}}\sum _{k=1}^{128}({F_{i^{\prime }{j}^{\prime }}^k}^2-{({\tilde{F}}_{i^{\prime }}^k)}^2))}\hfill \\ \hfill & =\frac{\sum _{i=1}^n(w_{i}QA(i))}{\sum _{i^{\prime }=1}^{n^{\prime }}(w_{i^{\prime }}QA(i^{\prime }))}.\hfill \end{array}$

Since denser regions appear in a larger portion of the images and hence would be assigned a very low IDF, it can be ignored in Equation (3.9), because its IDF is almost 0 due to the IDF’s log-like nature. On the contrary, in the sparser region, the quantization step is much more finite compared to the original method. Such a region has a much larger IDF and contributes more to the weighted quantization error. Based on Equation (3.8), QA(i) depends on: (1) point count m_i and (2) distance between each point j and its word center. By DML construction, in sparser regions, both (1) and (2) are smaller than they were in the original k-means, which leads to smaller quantization error QA(i). In other words, our method quantizes “meaningful” regions with more finite steps, and “meaningless” regions with more coarse steps. Based on DML, we multiply the larger w with the smaller QA in Equation (3.9), while the larger QA corresponds to almost zero IDF weights. Evaluating the overall quantization error, it is straightforward that ${\sum }_{i=1}^n(w_{i}QA(i))\ge {\sum }_{i^{\prime }=1}^{n^{\prime }}(w_{i^{\prime }}QA(i^{\prime }))$ and SNR_DML ≥ SNR_Org. In other words, regardless of the quantization errors in meaningless words such as “a” and “the” (such words can be disregarded in similarity ranking as “stop words”), there are fewer weighted quantization errors in the DML-based tree.

3.3.1 Chain Recognition in Dictionary Hierarchy

First, by expanding the TF-IDF term weighting procedure to hierarchical levels in the DML-based tree, the middle-level nodes are introduced into similarity ranking, which rectifies the magnified quantization errors in the leaves. In each hierarchical level, the IDF of the middle-node is calculated and recorded for middle-level matching. If the SIFT points are matched on a deeper level, their higher hierarchy would be hit by nature, meanwhile the ranking error of the leaf nodes caused by hierarchical quantization would be rectified in their higher hierarchy. Comparing to the GNP [27] method, our method offers an advantage in efficient computational cost, while maintaining comparable performance (see the subsequent Experimental section in this chapter).

Secondly, we have discovered that the integration of visual words in VT hierarchy is a natural analogy to boosting chain classification [84, 102], which brings us to a new perspective on [16] how to leverage tree hierarchy. (In [16], middle levels are simply combined as a unified weighted BoW vector in similarity ranking, which is similar to adopted pyramid matching for high-dimensional input data as a Mercer kernel for image categorization.) In a hierarchical tree structure, by treating each level as a classifier, the upper level has higher recall, while the lower level has higher precision. This is straightforward because the higher level represents the abstract of category representation and is more uniform, in which the similarity comparison is coarser. On the contrary, in the finest level, the features are very limited and specified, leading to higher precision. In addition, the ranking results in each level being different due to their different quantization steps. Combining such hierarchical classifiers using a boosting chain manner can further improve retrieval.

As presented in Figure 3.4, each level is treated as an “If...Else...” classifier that discards the least confident categories out of a vertical-ordered boosting chain for multi-evidence similarity ranking. In implementation, SIFT points belonging to the same query image are parallel, put in this hierarchical recognition chain, level by level, to incrementally reject most categories, as presented in Algorithm 3.2:

For each retrieved scene or object, the overwhelming majority of samples available are negative. Consequently it is natural to adopt simple classifiers to reject most of the negatives and then use complex classifiers to classify the promising samples. In our proposed algorithm, the vocabulary tree is considered as a hierarchical decision tree, based on which the cascade decision process is made at each hierarchy. A positive result past the higher level triggers the evaluation of the deeper level. Compared with a boosting chain that usually adopts boosting feature selection, our method utilizes each hierarchical level as a “visual word” feature for rejection due to its coarse-to-fine inherence.

3.4.1 Cross-database Case

First, the SIFT features of the new database are sent through the original VT model, based on which the term weightings of the words are updated. The feature frequency of each leaf node reveals its rationality of existence and necessity of further expansion or removal. Leaf nodes that are either over-weighted or over-lightened would be adaptively re-assigned. Algorithm 3.2 presents our proposed VT shift algorithm.

Three operations are defined to iteratively refine the VT model to fit the new database:

1. Leaf Delete: If the feature frequency of a leaf is lower than a pre-defined minimum threshold, its features are reassigned back to its parent. Subsequently, this parent uses its sub-tree (with this parent as the root node) to assign the above features to their nearest leaves, except the deleted leaf.

2. Parent Withdrawal: If a leaf is the only child of its parent, and its feature frequency is lower than the minimum threshold, we withdraw this leaf and degrade its parent as a new leaf.

3. Leaf Split: If the feature frequency of a leaf is higher than the maximum threshold, we regrow this node into a sub-tree with the same branch factor in construction.

3.4.2 Incremental Transfer

We further leverage our proposed VT shift algorithm for incremental indexing in the SCity database. In our “Photo2Search” system-level implementation, we need a preliminary question about the genesis of new data. Algorithm 3.3 presents the details of the proposed VT Shift algorithm. Generally speaking, our system collects incremental scene images as well as their GPS locations from the three following sources:

1. Scene images uploaded by system administrators, which are directly sent into the database as a new data batch.

2. Query images sent by users to the server-end computer and images periodically crawled from Flickr API (we use both scene name and city name as crawling criterion), which are considered as Under Evaluated. For such data, pre-processing is conducted to further filter irrelevance: We treat each new image as a query example, for scene retrieval, if the cosine distance between this query and the best matched image is lower than T_max (i.e., they are similar enough), we add this image into the new data batch in our database.

To provide consistent service along with the process of incremental indexing, our system maintains two central computers on the server side. Each maintains a location recognition system that is set to be identical after finishing one round of adaption. Initially, the status of one system is set as active while the other as inactive. Active means this server program is now utilized to provide service; inactive means this server program is now utilized for incremental indexing. Once the inactive program receives a new batch of scene images, we first investigate whether it is necessary to activate the incremental indexing process. If so, we conduct incremental indexing and switch its inactive status to active, and vice versa; otherwise, these images are temporarily stored and added into subsequent new image batches.

Facing a new image batch, it is not always necessary to activate the incremental indexing process in the inactive server. If the distribution of the new data is almost identical to that of the original dataset, adaption could be postponed for the subsequent images. Hence, to reduce the computational cost in large data corpora, we conduct model adaption once either of following cases is true: (1) the volume of the new images is large enough or (2) the distribution of the new images is extremely diverse from that of the original database. We present an adaption trigger criterion using Kullback-Leibler (KL) diversity-based relative entropy estimation as in Figure 3.3 and explained in detail as follows.

First, data distribution is measured by its sample density, which is identical to the density field in DML-based tree construction. Facing a new data batch, we evaluate the data dissimilarity Diver_Accu between the original database and the new data batch by their density-based KL-like relative entropy estimation:

$\begin{array}{l}\hfill Dive{r}_{Accu}=\sum _{i=i}^n{\tilde{D}}_{new}(i,m)log\frac{{\tilde{D}}_{new}(i,m)}{{\tilde{D}}_{org}(Nearest(i),m)},\end{array}$

in which ${\tilde{D}}_{new}(i,m)$ is the density of the new data at the i^th data point in the m^th neighborhood; D_org(Nearest(i),m) is the density of the old data at the nearest old point of the i^th new data in the m^th neighborhood. It can be observed from the above equation that data diversity increases as: (1) the volume of the new data batch increases; (2) the distribution of the original database and new data batch are more diverse. Consequently, we control the incremental indexing process by trigger criterion as follows: When fusing a new data batch into the original database, the point density in the original database need not be updated. Indeed, their former density estimations can be partially preserved and only need to be modified by new data (Algorithm 3.4):

$\begin{array}{l}\hfill {\tilde{D}}_{Update}(i,m)={\tilde{D}}_{Org}(i,k)+{\tilde{D}}_{new}(i,m-k),\end{array}$

where k is the number of remaining original points in m nearest neighbors, which is achieved by comparing the new data with the former-stored m nearest neighbors of each point.

3.5.1 Quantitative results

Figure 3.7 presents the SR@N in UKBench before and after DML, both of which conduct three comparisons: (1) leaf comparison, in which only leaf nodes are used in similarity ranking; (2) hierarchical chain, in which we adopt the hierarchical recognition chain for multi-evidence recognition; and (3) hierarchical chain + IDF, in which each level of the hierarchical recognition chain is combined with the IDF weights of their nodes in similarity ranking.

It is obvious that before DML learning, the real powers of the hierarchical recognition chain as well as the hierarchical IDF cannot be revealed well. But combinational performance enhancements of both methods after DML learning are significant, almost 20% over leaf-level baseline. Comparing Figure 3.7 with Figure 3.8, it is easy to see that the DML-based tree performs fairly better than the original tree, almost 20% enhancement to the best results. The same result holds in Scity as shown in Figures 3.9–3.10.

Indeed, this phenomenon can be expressed by Figure 3.11, after DML-based construction: the word distribution in the hierarchical level would follow Zipf’s Law better, which means not only middle-level nodes but also their IDF would be more discriminative and more meaningful.

Actually, without DML-based optimization, the hierarchical k-means would be biased to the denser regions and incorrectly divide them deeper and tighter rather than the sparse regions. This bias is hierarchically accumulated and wrongly assigns such regions with high IDF in recognition. This is why the use of IDF is not better in the original tree [30, 32], while it is better in the DML-based tree. Figure 3.12 further explains this enhancement in UKBench. On the left, the cluster diameter distribution in the 12^th level is ranked by feature frequency. By DML construction, the diameter distribution is more uniform, so feature-space division is more uniform; on the right, quantization error distribution is ranked by image counts of clusters. The quantization errors with more images are higher, but in clusters with fewer images they are much lower. An intuitive motivation of DML-based tree construction is to refine the original distance metric in k-means clustering, which is achieved by generating more clusters in denser regions and less clusters in sparser regions. Since VT hierarchy magnifies unbalanced space division, DML revises such bias to rectify such unbalance.

We further investigate the efficiency of the hierarchical recognition chain. Figure 3.13 presents a comparison between our method and GNP [27]. We also evaluate how the chain level affects the recognition performance in UKBench. The method from Nister [16] that combines middle levels into a unified BoW vector is also given (Fig. 3.14). Compared to [16], the proposed method can achieve better performance. When n > 14, performance begins to degenerate due to over-quantization. Compared to [16], VT has an advantage in efficient search in the large-scale case. Its cost is accuracy degeneration compared to solely SIFT matching. On the contrary, AKM in [10] merits in matching precision but it’s time-consuming: (1) It use float k-means; and (2) to ensure precision, the k-d forest is also slow.

We evaluate our proposed VT shift algorithm with the following experiments: Figures 3.15–3.16 present the VT shift performance between UKBench and Scity with different volumes (9K vs. 20K) and applications (scene vs. object). It is obvious that direct application of the dictionary across databases with different constitutions would cause severe performance degradation (Figure 3.17). However, the VT shift algorithm can well address the tree adaption problem. Table 3.2 presents the advantage of the DML-based tree in VT Shift operation over the original tree in both databases.

We further leverage our proposed VT shift algorithm for incremental indexing in the SCity database. In our “Photo2Search” system-level implementation, we should figure out a preliminary question about the genesis of new data (Figure 3.18). Generally speaking, our system collects incremental scene images as well as their GPS locations from the two following sources:

1. Scene images uploaded by system administrators, which are directly sent to the database as a new data batch.

2. Query images sent by users to the server-end computer and images periodically crawled from the Flickr API (we use both scene name and city name as crawling criterion), which are considered as under evaluated. For such data, pre-processing is conducted to further filter irrelevance: We treat each new image as a query example, for scene retrieval; if the cosine distance between this query and the best matched image is lower than T_max (i.e., they are similar enough), we add this image into a new data batch in our database.

To provide consistent service along with the process of incremental indexing, our system maintains two central computers on the server side. Each maintains a location recognition system that is set to be identical after finishing one round of adaption. Initially, the status of one system is set as active while the other as inactive. Active means this server program is now utilized to provide service; inactive means this server program is now utilized for incremental indexing. Once the inactive program receives a new batch of scene images, we first investigate whether it is necessary to activate the incremental indexing process. If so, we conduct incremental indexing and switch its inactive status to active and vice versa; otherwise, these images are temporally stored and added into consequent new image batches.

Figure 3.19 presents the performance comparison between our proposed method and methods (1) and (2). With the increase of database volume, the SR@1 performance is naturally decreased. Although reclustering performs better than our proposed method, its time cost is unacceptable compared to both incremental indexing and simply using original VT to generate new BoW vectors. Our method can maintain comparable performance (less than 10% degradation than comparing to reclustering), while requiring fairly limited computational cost (24% cost compared to reclustering).

We compare our proposed incremental indexing with method 1), reclustering of an entire renewed database (it has the best performance as the performance upper limit and 2), original VT that only regenerates BoW vectors for new images. It has no adaption in tree structure and is the performance baseline. We not only compare their recognition performance using SR@1 (Figure 3.18) but also compare their adaption computation cost using their computational costs in Figure 3.20.