2.2.1 Local Interest-Point Detection

For a target image, we first define the scale space L at scale δ by applying a Gaussian convolution kernel to the intensity component in its HSI color space. As shown in Equation (2.1), I(x,y) stands for the Intensity of pixel (x,y) and G(x,y,δ) is a Gaussian kernel applied to (x,y) with scale parameter δ:

$\begin{array}{l}\hfill L(x,y,\delta )=G(x,y,\delta )*I(x,y).\end{array}$

Then, we calculate the difference of Gaussians at the kth scale by subtracting the Gaussian convolutions between the kth scale kδ and the original scale δ (which produce scale spaces L(x,y,kδ) and L(x,y,δ), respectively):

$\begin{array}{l}\hfill \begin{array}{ll}D(x,y,\delta )& =(G(x,y,k\delta )-G(x,y,\delta ))*I(x,y)\\ & =L(x,y,k\delta )-L(x,y,\delta ).\end{array}\end{array}$

Finally, we identify the local feature candidates as the local maxima within their space and scale neighbors. For a given (x,y) location, there are 3 × 9 − 1 neighbors in total. For each candidate, we construct a Hessian matrix to investigate the ratio between its trace square and determinant. This ratio removes candidates coming from edge points with only signal changes in one dimension. We use the SIFT [9] descriptor to describe each remaining candidate as a 128-dimension local feature vector S. Similarly, other current descriptors [10] can be also adopted.

2.2.2 Accumulating Contextual Gaussian Difference

Then, the distribution of local feature context is quantitatively measured using a proposed difference of contextual Gaussians DoCG field: Our main idea is to estimate the contextual intensity of local features (named contextual Gaussian) based on their spatial distributions with other Gaussian kernel smoothing at different scales. The differences between contextual Gaussian at different scales are then aggregated to produce the DoCG field to quantize the local feature context.

Based upon the above principle, we give detailed formulation as follows: For a given local feature at location (x,y), its contextual Gaussian response is estimated using its neighborhood local feature distributions with Gaussian smoothing at “contextual” scale δ_context:

$\begin{array}{l}\hfill \begin{array}{l}{\mathit{S}}_{\mathit{CL}}(x,y,{\delta }_{\text{context}})\\ =\frac{1}{n}{\sum }_{i=1}^n\frac{1}{2\pi {{\delta }_{\text{context}}}^2}{e}^{-\frac{{(x-x_i)}^2+{(y-y_i)}^2}{2{{\delta }_{\text{context}}}^2}}{\mathit{S}}_i,\\ \end{array}\end{array}$

where S_CL(x,y,δ_context) is the estimated contextual Gaussian density at location (x,y) with contextual scale δ_context; i = 1 to n represents the n local features falling within δ_context of (x,y); and S_i is the feature vector of the ith neighborhood local feature descriptor.

We then calculate the difference of contextual Gaussians (S_DoCG) at the kth scale (kδ_context) by subtracting S_CL(x,y,kδ_context) and S_CL(x,y,δ_context) between the kδ_context and the δ_context contextual scales:

$\begin{array}{l}\hfill \begin{array}{l}{\mathit{S}}_{\mathbf{DoCG}}(x,y,k{\delta }_{\text{context}})\\ =\frac{1}{n^{\prime }}{\sum }_{j=1}^{n^{\prime }}\frac{1}{2\pi {(k{\delta }_{\text{context}})}^2}{e}^{-\frac{({(x-x_j)}^2+{(y-y_j)}^2)}{2{(k{\delta }_{\text{context}})}^2}}{\mathit{S}}_{\mathit{j}}\\ -\frac{1}{n}{\sum }_{i=1}^n\frac{1}{2\pi {{\delta }_{\text{context}}}^2}{e}^{-\frac{({(x-x_i)}^2+{(y-y_i)}^2)}{2{{\delta }_{\text{context}}}^2}}{\mathit{S}}_{\mathit{i}}\\ ={\mathit{S}}_{\mathit{CL}}(x,y,k{\delta }_{\text{context}})-{\mathit{S}}_{\mathit{CL}}(x,y,{\delta }_{\text{context}}).\\ \end{array}\end{array}$

Note that the above operation differs from the traditional DoG operation [8] which seeks the neighborhood local peaks within the consecutive scales. In contrast, we accumulate the difference of contextual Gaussians between different scales¹ additively to produce a final DoCG field, denoted as S_DoCG(x,y):

$\begin{array}{l}\hfill {\mathit{S}}_{\mathbf{DoCG}}(x,y)={\sum }_{k=1}^K{\mathit{S}}_{\mathbf{DoCG}}(x,y,k{\delta }_{\text{context}}).\end{array}$

Similar to DoG, this accumulated response S_DoCG(x,y) among all scales can indicate the robustness of location (x,y) to the variances caused by scale variances.

We further detect the semi-local salient regions over the local detector context. This detection is achieved by mean shift search [37] over the DoCG field to discover semi-local contextual peaks. The mean shift vector for each location (x,y) is calculated as:

$\begin{array}{l}\hfill \begin{array}{ll}& M({\mathit{S}}_{\mathbf{DoCG}}(x,y))\\ & =\frac{{\sum }_{i=1}^n{G}_H({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})w({\mathit{S}}_{\mathbf{DoCG}}^i)({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})}{{\sum }_{i=1}^n{G}_H({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})w({\mathit{S}}_{\mathbf{DoCG}}^i)}.\end{array}\end{array}$

In Equation (2.6), $w({\mathit{S}}_{\mathbf{DoCG}}^i)\ge 0$ is the weight given to the ith local feature, i = 1 to n denotes the n local features that fall within G_H() of (x,y), and G_H() is a Gaussian kernel that differentiates contributions of different local features based on their distances from (x,y). We denote G_H(S_DoCG−S_DoCG) as:

$\begin{array}{l}\hfill \begin{array}{ll}& G_H({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})\\ ={|H|}^{-1/2}& G(|H{|}^{-1/2}({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})).\\ \end{array}\end{array}$

H is a positive definite d × d bandwidth matrix. We simplify H as a diagonal matrix ($diag[h_1^2,\dots ,h_d^2]$).

Equation (2.6) can be further converted into:

$\begin{array}{l}\hfill \begin{array}{ll}& M_h({\mathit{S}}_{\mathbf{DoCG}}(x,y))\\ & =\frac{{\sum }_{i=1}^n{G}_H({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})w({\mathit{S}}_{\mathbf{DoCG}}^i){\mathit{S}}_{\mathbf{DoCG}}^i}{{\sum }_{i=1}^n{G}_H({\mathit{S}}_{\mathbf{DoCG}}^i-{\mathit{S}}_{\mathbf{DoCG}})w({\mathit{S}}_{\mathbf{DoCG}}^i)}-{\mathit{S}}_{\mathbf{DoCG}}\\ & =m_h({\mathit{S}}_{\mathbf{DoCG}}(x,y))-{\mathit{S}}_{\mathbf{DoCG}}.\\ \end{array}\end{array}$

We denote the first term in the second line of Equation (2.8) as m_h(S_DoCG(x,y)), which represents the gradient of the DoCG field at the point (x,y) are conducted. Subsequently, the mean shift search for contextual peaks over the DoCG field are conducted as:

• Step 1: Compute m_h(S_DoCG(x,y)) to offer certain robustness to ensure feature locating precision.

• Step 2: Assign the nearest SIFT point as a new (x,y) position to m_h(S_DoCG(x,y) for the next-round iteration.

• Step 3: If ||m_h(S_DoCG(x,y)) −S_DoCG||≤ ε, stop its mean shift operation; otherwise, repeat Step 1.

The final convergence is achieved at local maximal or minimal locations in the DoCG field, which are defined as the detected locations of our CASL detector.

Figure 2.1 further shows the effect of tuning both contextual and mean shift scales (in each contextual scale, we settle the mean shift scale by adding 30 additional pixels) to achieve local-to-global context detections. Please note that tuning larger contextual and mean shift scales (e.g., to include all SIFT features into contextual representation) would result in focusing attention on viewing images. On the contrary, small contextual and mean shift scales degenerate CASL into a traditional local feature detector (e.g., SIFT [9]).

To further describe the detected feature, we follow the design of shape context: First, we provide a polar-grid division for context-aware description. A visualized example of our descriptor is shown in Figure 2.2. For each semi-local interest point, we include the local features in its δ_Context neighbor into its description. We subdivide these δ_Context neighbors into log-polar grids with 3 bins in radial directions (radius: 6, 11, and 15 pixels) and 6 in angular directions (angle: 0°, 60°, 120°, 180°, 240°, and 300°). It results in a 17-bin division. The central bin is not divided in angular directions to offer a certain robustness against feature locating precisions, which differs from GLOH [10]. In each grid, the gradient orientations of SIFT points are averaged and quantized in 8 bins. It produces a (3 × 6 × 8) 144-bin histogram for each CASE descriptor.

2.3.2 Comparison to Saliency

Different from the traditional local salient region detectors [8, 29, 80, 81], our semi-local detector can discover salient regions based on the DoCG field construction, which is a key advantage compared to the current works. Indeed, we have discovered that the high response locations for DoCG shares good similarity to visual saliency detection results. We explain this phenomenon from the construction process of the DoCG field: For a given location, our semi-local contextual measurement is derived by accumulating differences of co-occurrence strengths among K contextual scales. Similarly, the principle of a spatial saliency map [94] adopts a center-surround difference operation to discover highly contrasted points at different scales with Gaussian smoothing, which are then fused to evaluate point saliency. From another viewpoint, the DoCG field also shares certain similarity with the spectral saliency map [96] built by the Fourier transform, which retains the global spectrum phase to evaluate pixel saliency. In comparison, based on spatial convolution and difference accumulation, our DoCG field also preserves global character in general, for which the high-frequency fluctuations are discarded by spatial Gaussian convolutions over local feature densities, and the influences of frequency variances are further weakened by the different operations of contextual strengths. Notably, the “center-surround” operation is the basic and fundamental form of “context”, which is similar to many “center-surround” saliency detection operations [94].

2.5.1 Database and Evaluation Criteria

Despite detecting meaningful and discriminative salient regions, we should still ensure that our CASL detector can well retain the detector repeatability requirement [100], which is crucial for many computer vision applications, such as image matching and 3D scene modeling. We evaluated our detector repeatability in the INRIA detector evaluation sequences [100]. Using this database, we directly got the results reported in [100] as our baselines. In [100], the repeatability rate of detected regions among a test image t and the ith image in the test sequence are calculated as:

$\begin{array}{l}\hfill Repeatability(t,i)=\frac{|R_I(ϵ)|}{min(n_t,n_i)},\end{array}$

in which the |R_I()| denotes the number of _repeatable [100] salient regions between t and i and the n_t and n_i represents the number of salient regions detected in the common part of images t and i, respectively. Refer to [100] for detailed experimental setups.

We adopted the UKBench benchmark database [16] to evaluate the effectiveness of our CASL detector in the near-duplicated image retrieval task. The UKBench database contains 10,000 images with 2,500 objects. There are four images per object to offer sufficient variances in viewpoints, rotations, lighting conditions, scales, occlusions, and affine transforms.

We built our retrieval model over the entire UKBench database. Then we selected the first image per object to form a query set to test our performance. This experimental setup is identical to [16], which directly offers us the baseline performance of MSER + SIFT reported in [16]. Identical to [16], we ensured that the top returning photo would be the query itself, hence the performance depends on whether the system can return the remaining three photos of this object as early as possible. This criterion was measured as the “Correct Returning” in [16].

We selected a 10-category subset of Caltech101 database to evaluate our CASL detector in the object categorization task, including face, car side, snoopy, elephant, wheelchair, cellphone, motorbike, butterfly, pyramid, and buddha. Each image category contains approximately 60 to 90 images. We randomly selected 10 images from each category to form a test set, and used the rest of the images to train the classifiers.

We evaluated our categorization performance by measuring the percentage of corrected categorizations in each category (averaged hit/miss of its 10 test examples) to draw a categorization confused matrix.

There are five groups of baselines in our experimental comparisons.

1. Local Detectors: First, we offer four baselines of local detectors, including DoG [8], MSER [29], Harris-Affine [80], and Hessian-Affine [81].

2. Local Descriptors: Second, we offer two baselines of local descriptors, i.e., SIFT [9] and GLOH [10] (for comparison to the CASE descriptor).

3. Saliency Map Pre-Filtering: In both comparisons, we also compare with the saliency map pre-filtering [94] to select salient local features.

4. Integration of Category Learning: Third, we compare our learning-based CASL detector + SVM with two baselines of both CASL (without learning) + SVM and Bag-of-Visual-Words (SIFT) + SVM in the object categorization task.

5. Context-Aware Features: Finally, we compare our framework with two context-aware feature representations: (1) the “S1-C1-S2-C2” global contextual features [95] and (2) the Shape Context features [19] in both Caltech6 and Caltech101 recognition benchmark databases.

2.5.2 Detector Repeatability

Figure 2.6 shows the quantitative evaluations of the detector repeatability comparisons in the sequences of different scales, viewpoints, blurs, compressions, and illuminations. We can see that our CASL detector produces more repeatable detection results in the repeatability comparisons of compressions, illuminations, and blurs. And we obtain comparable performances in the repeatability comparisons of viewpoints and scales. Although our CASL detector produces generally fewer salient regions compared with the alterative approaches, we still achieve comparable performance by including semi-local spatial layouts in detection. Such spatial layout prevents unstable detections that are frequently found in traditional local feature detectors.

Figure 2.6 shows the quantitative evaluations of the detector repeatability comparisons in the sequences of different scales, viewpoints, blurs, compressions, and illuminations. We can see that, in many cases, our CASL detector produces more repeatable detection results in the repeatability comparisons of illuminations (fifth subfigure) and viewpoints (sixth subfigure); in all cases better in the repeatability comparisons of compressions (fourth subfigure); and in some cases better in the repeatability comparisons of blurs (third subfigure). However, we should note that we almost rank persistently worse than the Hessian-affine in viewpoints (first subfigure) and scales (second subfigure) (Hessian-affine is shown as one of the most effective detectors in the literature). One reason for this performance is that our CASL detector generally produces fewer salient regions, compared with the alternative approaches. In summary, our CASL detector achieves comparable performance to current detectors with generally fewer features per image. It could be due to including semi-local spatial layouts into detection. Such spatial layout prevents unstable detections that are frequently found in the traditional local features detectors. However, as shown in Figure 2.6, in some cases such as viewpoints or scales changes, Hessian-affine and MSER would be a better choice due to their simplicity.

We further compare the computational time cost of our CASL detector with respect to different contextual scales and mean shift scales in Table 2.1. One interesting observation here is that by increasing both contextual and mean shift scale, the overall computational cost will subsequently increase.

2.5.3 CASL for Image Search and Classification

Note that in all methods, the “correct returning” is larger than 1, since the query would definitely find itself in the database. This experimental setup is identical to [16], which directly offers us the baseline performance of MSER + SIFT reported in [16]. We provide three implementation approaches: CASL (local detector part: DoG + SIFT) + SIFT, CASL (local detector part: MSER + SIFT) + SIFT, CASL (local detector part: DoG + SIFT) + CASE, CASL (local detector part: MSER + SIFT) + CASE; CASL (local detector part: DoG + MOP) + CASE, CASL (local detector part: MSER + MOP) + CASE. The experimental results show that in the local feature building block of CASL, the DoG + SIFT is a better choice for the task of near-duplicated image retrieval.

We built a 10-branch, 4-layer dictionary tree (VT) [16] for the UKbench database, which produced approximately 10,000 visual words. Nearly 450,000 CASL features and nearly 1,370,000 MSER + SIFT features were extracted from the entire database to build two vocabulary tree models [16], respectively (with inverted document indexing), each of which gave a bag-of-visual-words (BoW) vector [16] for each image. In the vocabulary tree model, if features within a node were less than a given threshold (100 for CASL features, 250 for SIFT features), we stopped the k-means division of this node, whether it had reached the deepest level or not. For a a-branch VT with m words, the search time for one feature point is alog_a(m), which is proportional to the logarithm of branch number, and is independent of the database volume.

Figure 2.7 shows the performance of CASL + CASE in comparison with state-of-the-art local feature detectors (DoG, MSER), descriptors (SIFT), and the improvement based on saliency map pre-filtering:

1. DoG [8] + SIFT [9], a widely adopted approach to building a bag-of-visual-words model.

2. MSER [29] + SIFT [9], which is the implementation of a vocabulary tree model [16] in near-duplicated search.

3. Saliency map [94] + MSER [29] + SIFT [9], in which we maintain only salient local features (measured by pixel-level saliency for a detected local feature location) to build the subsequent dictionary.

4. CASL + SIFT [9], which quantize the performance of our CASE descriptor.

5. DoG + MOP [21] as an alternative approach for our implemental baseline of DoG + SIFT [9]. However, as shown in Figure 2.7, this is a suboptimal choice for our subsequent CASL feature construction.

6. MSER [29] + MOP [21] as another alternative approach for our implemental baseline of DoG + SIFT [9]. Similarly, as shown in Figure 2.7, this is also a suboptimal choice for our subsequent CASL feature construction.

All these methods are based on the bag-of-visual-words quantization in which we adopt an inverted document search to find the near-duplicated images of the query example (in our query set) on the UKBench database.

From Figure 2.7, it is obvious that our CASL feature outperforms baseline methods that are based solely on local features with saliency map pre-filtering. Meanwhile, comparing with MSER [29], DoG [8] performs much better in building our local feature context.

Higher precisions also indicate two merits of our CASL detector: (1) More repeatability over rotation, scale, and affine transformations, which are common in the UKBench database; and (2) more discrimination within different object appearances. The photos in UKBench usually contain different objects such as CD covers with identical or near duplicated backgrounds. Hence, the capability to discriminate a foreground object from background clutter is essential for high performance.

For the task of object recognition, we built a 2-layer, 30-branch vocabulary tree [16] for image indexing, which contains approximately 900 visual words for this categorization task. For each category, the bag-of-visual-words vectors (approximately 900 dimensions for each image) are extracted for training. We offline built a SVM for every two categories. In the online recognition, we adopted a one-vs-one strategy to vote for the category membership for a test image: If one category won a SVM between this category and another category, we increased the voting score for the winning category by one. The category with the highest scores was assigned to the test image as its final label. Since we aimed to compare CASL with other detectors, we simply adopted a one-vs-one SVM in the classifier phase, which can be easily replaced by other sophisticated methods, e.g., SVM-KNN. We used the same parameter tuning approach described for near-duplicated image retrieval to tune the best contextual and mean shift scales.

Figures 2.8–2.9 present the confused matrix of different combination schemes, including (1) Saliency map + MSER + SIFT + SVM, (2) CASL (local features: MSER + SIFT) + CASE + SVM, (3) CASL (local features: DoG + SIFT) + CASE + SVM, and (4) learning-based CASL (local features: DoG + SIFT) + CASE + SVM. Generally speaking, CASL features perform much better than the approach that adopted saliency map pre-filtering to integrate semi-local cues. Meanwhile, the integration of learning part into CASL detector can largely boost the categorization performance in our current settlement.

We give quantitative comparisons to the context-aware global features [95]. Identical to the settlement of [95], the Caltech5 is adopted in comparison. The performances of SIFT and C2 are directly from [95], the former of which adopted approximately 1,000-dimension features for categorization. To offer comparable evaluations, we built a CASL-based BoW vector containing about 900 visual words, and adopted linear SVM for classifier training. Note that we also used learning-based CASL in feature extraction.

Based on the comparison in the Caltech5 database (Table 2.2), our CASL detector achieved almost identical performance to the best performance reported in [95]. Since C2 +SVM already achieves very high (nearly 100 percent) performance, it is hard to obtain much better performance with a large margin. On the contrary, in addition to (slightly) better performance for C2 features, our CASL detector also shows much better results than SIFT + SVM with a large margin. Nevertheless, the C2 feature is better at higher computational cost. However, there are two major differences between our approach and the S1-C1-S2-C2 features [95]:

First, the S1-C1-S2-C2-like feature extraction and classification framework [95] produces one feature vector per image with fixed feature dimension. This is different from our CASL detector that outputs patch-based features to produce bag-of-(semi-local)-word representations.

Second, the S2-C2 part in [95] needs training for prototype learning, which is indispensable in feature construction. In contrast, our CASL feature can also perform in an unsupervised manner (the learning is an optional choice), which can be easily reapplied into other unsupervised scenarios, and can be further combined with more complicated classifiers in the subsequent categorization step.

Regarding the polar-bin division strategy, there exists similarity between our CASE descriptor and the shape context feature [19]. Hence, it is a natural to replace our CASE descriptor with the shape context descriptor. Table 2.3 presents the experimental comparisons of our CASL + CASE feature with the CASL + shape context feature [19]. We should note that the shape context is a feature descriptor, which is not competitive but comprehensive to our CASL detector. However, we have found that the direct replacement of the shape context feature to our CASE descriptor cannot achieve satisfactory results for our CASL detections. Its similarity matching mechanisms are originally designed for shape primitives (Table 2.4).

Based on the above three groups of experiments with comparisons to current technology, we have the following statements and guidelines about our application scenarios:

(1) What vision tasks are more suitable for CASL than traditional local feature detectors?

• The vision tasks emphasize discovering meaningful and discriminative features, rather than repeatable detection. For instance, generalized or specialized object recognition, image annotation, semantic understanding, and video concept detection.

• CASL is also suitable for the case where more attentional focus is needed, such as to describe images based solely on the most salient objects, or to discriminate foreground objects from backgrounds from a set of training images. In the latter case, we should also know their category labels beforehand to carry out our learning-based CASL.

(2) What scenarios are not as suitable for CASL instead of local feature detectors?

• When the vision tasks emphasize the repeatable detection more, rather than semantic or attentional discriminability, e.g., image matching and wide baseline matching.

• When the target image contains large amount of local features, and there are no demands to differentiate the foreground object from background clutter. For instance, scene matching and near-duplicated scene identification.