Learning images representations plays an important role in many real-world applications due to the overwhelming amount of images and videos nowadays brought by modern technologies. Recently, image representation techniques using semi-local, or patch-based, features, such as SIFT and geometric blur, have demonstrated some of the best performance in image retrieval and object recognition applications. These algorithms choose a set of patches in an image, and for each patch compute a fixed-length feature vector. This gives a set of vectors per image, where the size of the set can vary from image to image. Armed with these patch-based features, image categorization and retrieval are recently formulated as a multi-instance learning (MIL) problem with improved retrieval, indexing and annotation performances [19,3,40,30,28,31]. Under the framework of MIL, an image is viewed as a bag, which contains a number of instances corresponding to the patches in the image. For example, in the image in Figure 1 there exist a total of four patches (surrounded by the yellow bounding boxes) that represent a set of four different objects, including a car, a bicycle, and two persons (one person is riding the bicycle and the other one is standing aside). The image thereby is a bag and each of the four patches, represented as a vector, in the image is consider as an instance. If any of these instances is related to a semantic concept, the entire image will be annotated with the corresponding semantic label.
Despite a number of successes in applying MIL in image learning, there exist two critical challenges that prevent one from effectively using available visual information in an image as much as possible.
First, most, if not all, existing MIL methods only use the instances of an input image to model the semantic concepts, but not the entire image. For example, when a MIL method [19,3,40,30,28,31,24,35,38] is used to study the image in Figure 1, only the four instances are associated with some semantic concepts. However, these four patches only occupy a small percent of the area of the entire image, while the remained areas of the image that are outside of the yellow bounding boxes are completely dis- carded, which, though, could potentially convey valuable semantic information. For instance, a large area of this picture is "ground", which is closely correlated to "automobiles" and "bicycles" and could be used to improve the image categorization accuracy [25,26,27]. Indeed, recent studies have already demonstrated that holistic image representations based upon global features are a necessity to decode scene contents [10,37]. Therefore, it is desirable to learn an image representation that is able to capture both instance-wise and holistic information of an input image.
Second, in MIL an image is represented as a set of vectors and the numbers of the vectors in the images of a data set are different in general. Although the multiple-vector representation could describe the image details with better granularity, varied data sizes make it infeasible to use traditional machine learning models that can only deal with data represented by single-vectors, i.e., one vector per data sample. Therefore, it would be beneficial to learn a singlevector representation for an image that can integrate the information from both its instances and its entire context.
To address the above two challenges in multi-instance image learning, in this paper we present a novel image representation learning method. It first learns a projection from the instances of an input image. Then it projects its holistic image representation into the learned subspace. A schematic illustration of our new method is shown in Figure 1. Through these procedures, the learned image representation simultaneously captures the information from both multi-instance image patches and the holistic summarization of the entire image. In the proposed objective to learn the projection from the instances of an input image, we aim to preserve both global and local consistencies of the instances in the projected subspace, which leads to an optimization problem that maximizes the ratio of matrix traces. By further recognizing the variations of the content and visual characterization in natural scenes and photos, we further develop the proposed objective by replacing the squared ℓ 2 -norm distances by the ℓ 1 -norm distances in our formulation, such that the robustness of the learned image representations against outlying samples and features is promoted [2,4,9,15,16,36,20,34].
Despite its clear motivations to integrate the information of an input image from both its local instances and its holistic representation, the proposed objective ends up to be an optimization problem that simultaneously maximizes and minimizes the summations of a number of ℓ 1 -norm distances, which is difficult to solve in general. To solve this challenging optimization problem, we derived an efficient iterative algorithm with theoretically guaranteed convergence. It is worth noting that, different from many previous works, our new solution algorithm is a non-greedy algorithm, such that it has better chance to find the global optima. To the best of our knowledge, our new algorithm solves the general optimization problem that maximizes the ratio of the summations of the ℓ 1 -norm distances in a non-greedy way for the first time in literature, which can find many applications to improve a number of machine learning models.
Finally, we performed extensive experiments on three benchmark multi-instance image data sets, the promising experimental results have demonstrated the effectiveness of our new method in image learning applications.
In this section, first we formalize the representation learning problem for images with semantic patches, where we introduce the notations used in this paper. Then we gradually develop the proposed objective to learn a single-vector representation of an input image that captures both global and local consistencies of the image patches and integrates the holistic information conveyed by the entire image.
Throughout this paper, we write matrices as bold uppercase letters and vectors as bold lowercase letters. The trace of the matrix M = [𝑚 𝑖𝑗 ] is defined as tr (M) =
𝑖 𝑚 𝑖𝑖 , and the ℓ 1 -norm of M is defined as
√ ∑ 𝑖 𝑣 2 𝑖 . In image retrieval and annotation tasks, we study a set of images and every image contains a collection of semantically meaningful patches. For a given image, we represent it as 𝒳 = {x, X}, where x ∈ ℜ 𝑑 denotes the holistic representation of the entire image and X = [x 1 , . . . , x 𝑛 ] ∈ ℜ 𝑑×𝑛 denotes a collection of 𝑛 semantic patches, respectively. Here x 𝑖 ∈ ℜ 𝑑 (for 𝑖 = 1, 2, . . . , 𝑛) represents a patch of the input image, which can be illustrated as a yellow box in the image in Figure 1. Under this framework, every image is considered as a bag of instances (patches). In general, the numbers of the semantic patches in the images of a data are different from one to another. In order to tackle the two critical challenges analyzed before in Section 1, different from existing MIL studies that model the associations between the instances of input images and the predictive targets directly, in this paper we aim to learn from an input image 𝒳 a single-vector representation of y = 𝑓 (𝒳 ) that captures the information in both local patches and the entire image. Because the new representations of the images in a data set are of the same length, they can be readily used by traditional learning models in various image learning tasks. In the following, we use instance and image patches interchangeably when there is no risk of ambiguity.
In this subsection, we will develop the proposed objective to learn a new single-vector representation for an input image from its holistic representation and its semantic instances. When we integrate the holistic representation and the semantic instances of the input image, we aim to preserve both global and local consistencies among the semantic instances in the learned projected subspace.
Learning with global consistency via PCA. With recent advances in digital imaging techniques, one can easily have a camera with very high resolution. As a result, the derived visual descriptors from a raw picture are usually of high dimensionality. When the image dimensionality grows, most image retrieval and annotation methods will fail due to "the curse of dimensionality" [8] and intractable computational costs. Thus, learning a lower-dimensional image representation while maintaining the original geometrical structures of the input image is valuable for practical use. To achieve this goal, principal component analysis (PCA) [14] is the right tool to preserve as much information as possible by learning a projection W ∈ ℜ 𝑑×𝑟 (usually 𝑟 ≪ 𝑑) from the semantic instances X of the input image 𝒳 , which maps x 𝑖 in the high 𝑑-dimensional space into a vector y 𝑖 in a lower 𝑟-dimensional space by computing y 𝑖 = W 𝑇 x 𝑖 , such that the overall variance of the input data in the projected space ℜ 𝑟 is maximized. Formally, let the global mean vector of the input data X as x = 1 𝑛 ∑ 𝑛 𝑖=1 x 𝑖 , PCA seeks the projection W by maximizing the following objective:
where
𝑇 is the covariance matrix of X and the constant factor 1 𝑛 is omitted for brevity. Because 𝒥 Global maximizes the global variance of the instances of the input image in the projected subspace, the projected instances via the learned projection W are globally consistent in terms of information preservation.
Besides taking advantage of the global consistency of the semantic instances of the input image, we further take into account the local geometric structures of these semantic instances in the projected subspace and consider their local consistency. Ideally, in the learned subspace the instances with similar semantic labels should be close to each other, while those with different semantic labels should be far away from each other. In other words, in contrast to maximizing the projected global variance, we also want to minimize the local variance around every instance in the projected subspace. Mathematically, denoting the 𝐾-nearest neighbors of x 𝑖 as 𝒩 𝑖 and the local mean vector of x 𝑖 as x𝑖 = 1
x𝑗 ∈{𝒩𝑖∪{x𝑖}} x 𝑗 , we can achieve the overall local consistency by minimizing the following objective:
where, following our previous work [33], we define:
Obviously, S 𝐿𝑖 computes the local covariance matrix of the data points around x 𝑖 . Thus minimizing tr ( W 𝑇 S 𝐿𝑖 W )
ensures the local consistency around x 𝑖 and minimizing 𝒥 Local in Eq. ( 2) ensures the overall local consistency around all the instances in a bag. Here, again the constant factor 1 𝐾+1 is omitted for brevity.
Our objective to integrate the global and local consistencies of the semantic instances. Armed with the objectives that can capture the global and local consistencies of the semantic instances of an input image separately, we can develop a combined objective to capture both of them simultaneously. Among several possible ways to combine the two objectives in Eqs. (1-2), we can formulate our new objective using the trace ratio of matrices [12], which maximizes the following objective:
A critical problem of 𝒥 ℓ2 in Eq. ( 3) lies in that it computes the ratio of the summations of a number of squared ℓ 2 -norm distances, which are notoriously known to be sensitive to both outlying sample and outlying features [4,34]. Many images from natural scenes and photos often have clustered objects. This is particularly true when there exist a crowd of people in a picture, where each individual people may not characterize the the semantic category of "person" appropriately and many instances have to be considered as outlying samples. Similarly, due to cropped objects and (partially) shaded objects in pictures, such as the car in the image in Figure 1, outlying features also inevitably exist in real image data sets. Following many previous works [2,4,9,15,16,36,29,32,21,34], to deal with the feature and content variances in natural images, we propose to learn the projection by maximizing the following objective:
in which we compute the summations of the ℓ 1 -norm distances, because the ℓ 1 -norm distance can promote the robustness against both outlier samples and outlier features. Upon solving the optimization problem in Eq. ( 4), the learned W not only the global variance of the semantic instances of an input image, but also rewards the local geometric structures of the semantic instances, which thereby is both globally and locally consistent in the learned subspace. Then we enrich the holistic representation x of the input image 𝒳 by computing y = W 𝑇 x, which is a fixed-length single-vector representation and can be readily used by any traditional single-instance machine learning models. This indeed is the main contribution of this paper.
Our new objective in Eq. ( 4) maximizes the ratio of the summations of a number of the ℓ 1 -norm distances, which is obviously not smooth and thus difficult to solve in general. To solve the general problem that maximizes the ratio of the summations of the ℓ 1 -norm distances, such as our objective in Eq. ( 4), in this section we will derive an efficient iterative algorithm that is non-greedy. We will also prove the convergence of our new solution algorithm.
We first generalize the objectives in Eq. (3) and Eq. ( 4) into the following general optimization problem and then derive its solution algorithm:
where Ω is the feasible domain. Motivated by our previous works [34,33,24], we propose a simple, yet efficient, iterative framework in Algorithm 1 to solve the objective in Eq. ( 5), whose convergence is rigorously guaranteed by Theorems 1.
Algorithm 1: Algorithm to solve Eq. ( 5).
Theorem 1. In Algorithm 1, for each iteration we have (1)
𝑚(𝑣 𝑘-1 ) ; and (2) ∀𝛿, there exists a k such that ∀𝑘 > k ℎ(𝑣 𝑘 ) 𝑚(𝑣 𝑘 ) -ℎ(𝑣 𝑘-1 ) 𝑚(𝑣 𝑘-1 ) < 𝛿.
Proof. In Algorithm 1, from step 3, we have ℎ(𝑣 𝑘 ) -𝜆 𝑘 𝑚(𝑣 𝑘 ) > 0. Because ∀𝑣 ∈ Ω 𝑚(𝑣) > 0, we can get
𝑚(𝑣 𝑘-1 ) , which completes the proof of the first statement of Theorem 1.
Suppose that for the 𝑘-th iteration, there exists a 𝑐 𝑘 such that ℎ(𝑣 𝑘 ) -𝜆 𝑘 𝑚(𝑣 𝑘 ) = 𝑐 𝑘 > 0. We have:
by which we can derive:
From Eq. ( 7), we can derive:
Suppose that there exist a positive constant 𝐶 such that lim 𝑘→∞ ∑ 𝑘 𝑖=1 𝑐 𝑖 = 𝐶. If this is not true, we have lim 𝑘→∞ ∑ 𝑘 𝑖=1 𝑐 𝑖 = ∞, by which, together with Eq. ( 8), we can derive lim 𝑘→∞ ∑ 𝑘 𝑖=1 ℎ(𝑣 𝑘 ) 𝑚(𝑣 𝑘 ) = ∞. This, however, contradicts the fact that ℎ(𝑣 𝑘 ) 𝑚(𝑣 𝑘 ) is bounded as defined in Eq. ( 5), which means that lim 𝑘→∞ ∑ 𝑘 𝑖=1 𝑐 𝑖 = 𝐶 holds. Thus, we have lim 𝑘→∞ 𝑐 𝑘 = 0, i.e., lim 𝑘→∞ 𝑐 𝑘 𝑚(𝑣 𝑘 ) = 0, which indicates that ∀𝛿 > 0, there must exist a k such that:
by which and Eq. ( 6), we have:
which indicates that Algorithm 1 converges to a local optimum and completes the proof of the second statement of Theorem 1.
To solve our objective in Eq. ( 4), according to Step 3 in Algorithm 1, we need find a solution that satisfy the constraint of W 𝑇 W = I and the following inequality:
where 𝜆 𝑘 is computed by
and W 𝑘-1 denotes the projection matrix in the (𝑘 -1)-th iteration, which is already known in the 𝑘-th iteration. Here, for notation brevity, we define:
Now we need solve the problem in Eq. ( 11), for which we first introduce the following two lemmas.
First, motivated by Lemma 1 and Lemma 2, we construct the following objective:
where 𝐾(W) and 𝑁 (W) are defined as:
Here w 𝑔 and w 𝑘-1 𝑔 denote the 𝑔-th column of matrices W and W 𝑘-1 , respectively; B and A 𝑔 for 𝑔 = 1, 2, ⋅ ⋅ ⋅ , 𝑟 are defined as follows:
and sign(𝑥) is the sign function.
Then, using the definition of 𝐿(W, W 𝑘-1 ) in Eq. ( 15) and Lemmas 1-2, we can prove the following theorem.
Theorem 2. For any W ∈ ℜ 𝑑×𝑟 , we have
The equality holds on if and only if W = W 𝑘-1 .
Proof. First, according to Lemma 1 we can compute:
Then, according to Lemma 2 we have:
which indicates that:
Combining Eq. ( 21) and Eq. ( 23), we can derive:
According to Lemma 1 and Lemma 2, it is easy to verify that equality holds in Eq. ( 21) and Eq. ( 23) if and only if W = W 𝑘-1 . Thus, equality holds in Eq. ( 24) if and only if W = W 𝑘-1 . This completes the proof of Theorem 2. Now we continue to solve our objective. Let W = W 𝑘-1 , by substituting it into the objective, we have:
In the 𝑘-th iteration in solving the objective in Eq. ( 4), W ★ satisfies:
Then, we have:
Theorem 2 and Eq. ( 27) indicate that the solution of the objective function in Eq. ( 11) can be transformed to solve the objective function 𝐿(W, W 𝑘-1 ) ≥ 0, which can be easily solved by the projected subgradient method with Armijo line search [23]. The subgradient of 𝐿(W, W 𝑘-1 ) at W is computed as:
Note that, for any matrix W the operator 𝑃 (W) = W ( W 𝑇 W ) -1 2 can project it onto an orthogonal cone.
Input: W 𝑘-1 and Armijo parameter 0 < 𝛽 < 1.
1. Calculate 𝜆 𝑘 by Eq. ( 12) the subgradient G 𝑘-1 = ∂𝐿(W 𝑘-1 , W 𝑘-1 ) by Eq. ( 28) and set 𝑚 = 1.
while not 𝐹 (W 𝑘 ) > 𝐹 (W 𝑘-1 ) = 0 do 2. Calculate W 𝑘 = 𝑃 (W 𝑘-1 + 𝛽 𝑚 G 𝑘-1 ).
Calculate 𝐹 (W 𝑘 ) by Eq. ( 11). 4. 𝑚 = 𝑚 + 1.
Output:
This guarantees the orthogonality constraint of the projection matrix, i.e. ( W 𝑘 ) 𝑇 ( W 𝑘 ) = I. Algorithm 2 summarizes the algorithm to maximize 𝐹 (W) in Eq. (11).
Finally, based on Algorithm 2, we can derive a simple yet efficient iterative algorithm as summarized in Algorithm 3 to solve ratio maximization problem for the ℓ 1 -norm distances, i.e., our objective in Eq. ( 4). Algorithm 3: Algorithm for non-greedy ratio maximization of the ℓ 1 -norm distances.
1. Randomly initialize W 0 satisfying ( W 0 ) 𝑇 W 0 = I and set 𝑘 = 1. while not converge do 2. Calculate 𝜆 𝑘 by Eq. ( 12).
3. Find a W 𝑘 satisfying 𝐹 (W 𝑘 ) > 𝐹 (W 𝑘-1 ) = 0 by Algorithm 2. 4. 𝑘 = 𝑘 + 1. Output: W.
Theorem 3. If W 𝑘 is the solution of the objective function in Eq. (11) and satisfies
Proof. Since W 𝑘 is the solution of the objective function in Eq. ( 11), we have
from which we can easily derive:
Now by substituting Eq. ( 12) into Eq. ( 30), we have
which completes the proof of Theorem 3.
Theorem 4. The objective in Eq. ( 4) is upper bounded.
Proof. First, using Cauchy-Schwarz inequality we have the following for the numerator of our objective in Eq. ( 4):
Obviously, given an input data set, ∑ 𝑛 𝑖=1 𝑟 ∥(x 𝑖 -x)∥ 2 is a constant, which indicates that the numerator of our objective in Eq. ( 4) is upper bounded for a given data set.
Second, it can be verified that 1 , by which we can derive the following for the denominator of our objective in Eq. ( 4):
where 𝜆 𝑖 (𝑖 = 1, . . . , 𝑟), ordered by 𝜆 1 ≤ ⋅ ⋅ ⋅ ≤ 𝜆 𝑟 , are the eigenvalues of S 𝐿 . The last inequality in Eq. ( 33) is obtained by the Ky Fan's inequality [7], which states that tr ( W 𝑇 S 𝐿 W ) ≥ ∑ 𝑟 𝑖=1 𝜆 𝑖 . Again, given an input data set, S 𝐿 is an constant matrix thereby ∑ 𝑟 𝑖=1 𝜆 𝑖 is a constant. Thus the denominator of our objective in Eq. ( 4) is lower bounded.
The two bounds in Eq. ( 32) and Eq. ( 33) together indicate that our objective in Eq. ( 4) is upper bounded. Theorem 3 indicates that our proposed Algorithm 3 monotonically increase the objective function value in each iteration. Theorem 4 indicates that the objective function is upper bounded, which, together with Theorem 3, indicates that Algorithm 3 converges to a local optimum.
In this section, we experimentally evaluate the proposed image representation method in an automatic image annotation task, where we use the following three multi-instance image data sets: the PASCAL VOC 2010 data set [6], the Corel5K data set [5], and the Scene data set [40]. We perform our evaluations using standard 5-fold cross-validation and report the average performances over the 5 trials.
The proposed image representation learning method has two parameters, the number of neighborhoods 𝐾 of an instance and the dimensionality 𝑟 of the projected subspace. In our experiments, the performance of the proposed method is very stable with respect to these two parameters in considerably large value ranges. Empirically, in all our experiments we select 𝐾 = min {3, 𝑛} where 𝑛 is the number of instances in an image bag and 𝑟 = 𝑑/10 where 𝑑 is the dimensionality of the instance vectors.
Experimental settings. We first compare our method to two baseline classification methods including support vector machine (SVM) method and the transductive support vector machine (TSVM) [13] method. The former is the most broadly used supervised classification method in statistical learning, while the latter is an extension of the former one and is a semi-supervised classification method. Because both of these two methods are designed for single-instance data, they are not able to deal with data with representations of varied sizes. Therefore, we train and classify images using the holistic representations of the experimental images. Specifically, for each class we train a one-vs.-others classier using the images in the training data set, and classify the images in the test data set. Gaussian kernel is used in the both methods, i.e., 𝒦 (x 𝑖 , x 𝑗 ) = exp
, where 𝛽 and the regularization box parameter 𝐶 are fine tuned by searching the grid of { 10 -5 , . . . , 10 -1 , 1, 10, . . . , 10 5 } via an internal 5-fold cross-validation using the training data of each of the 5 trails. The both methods are implemented using SVM 𝑙𝑖𝑔ℎ𝑡 software package [1].
We also compare our method against two very recent MIL methods including the miGraph [39] method and the MIMLSVM+ [17] method. Because miGraph method is a single-label classification method, one-vs.-others strategy is used to conduct classification, one class at a time. We implement these two methods using the codes published by the respective authors. Because the both methods are multiinstance classification methods, we perform classification using the semantic instances of the input images. For our method, once the multi-instance enriched representations of the input images are learned, they can be directly fed into any traditional single-instance classifiers. Thus we evaluate our new image representation learning method using two most broadly used classifiers: the 𝐾nearest neighbour (KNN) classifier and the SVM. In our experiments, we select 𝐾 = 3 in KNN classifiers and use the same settings as detailed above the SVM classifiers.
Experimental results. Because the three experimental image data sets are all multi-label data sets, we evaluate the classification performances of the compared methods using five broadly used multi-label evaluation metrics as in Table 1, where "↓" indicates "the smaller is the better", while "↑" indicates "the bigger is the better". We refer readers to [22] for detailed definitions of these evaluation metrics.
The average classification performances (mean ± standard deviation) of the compared methods over the 5 trials of the experiments are reported in Table 1, from which we can see a number of interesting observations as following. First, the proposed method is consistently better than the other four competing methods, sometimes very significantly. Second, the MIL methods are generally better than the two baseline classification methods that only use the holistic image representations. This observation is reasonable in that the two baseline methods are both single-instance classification methods, which only use the holistic image representations. As a result, the important structural information contained in image patches with semantic meanings are not exploited, which leads to inferior performance. Last, but not least, the SVMs using the raw holistic image representa-tions perform drastically worse than those using the learned image representations by our new method, i.e., the holistic image representation with multi-instance enrichments. This observation firmly confirms that our proposed method can improve the image representations in terms of image annotation. To summarize, the experimental results in Table 1 clearly demonstrate the effectiveness of the proposed methods in multi-instance multi-label image classification.
In this paper, we have presented a novel image representation learning method that is able integrates the information conveyed by both local image patches and the holistic representation of the entire image. Our new method first learns a projection to preserve both global and local consistencies of the instances of the input image in a projected subspace, then it projects the holistic representation of the entire image into the learned subspace for information enrichment. Taking into account the content and characterization variations in pictures for nature scenes and photos, we developed an objective that simultaneously maximizes and minimizes the summations of a number of ℓ 1norm distances, which is difficult to solve in general. Thus, we derived an efficient iterative solution algorithm that is non-greedy and theoretically proved to converge. Our new method has been validated in extensive experiments to simulate the real-world applications.