# Image Annotation via Reconstitution Graph Learning Model

Authors: Shi Chen; Meng Wang; Xuan Chen
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

With great developments of computing technologies and data mining methods, image annotation has attracted much attraction in smart agriculture. However, the semantic gap between labels and images poses great challenges on image annotation in agriculture, due to the label imbalance and difficulties in understanding obscure relationships of images and labels. In this paper, an image annotation method based on graph learning is proposed to accurately annotate images. Specifically, inspired by nearest neighbors, the semantic neighbor graph is introduced to generate preannotation, balancing unbalanced labels. Then, the correlations between labels and images are modeled by the random dot product graph, to deeply mine semantics. Finally, we perform experiments on two image sets. The experimental results show that our method is much better than the previous method, which verifies the effectiveness of our model and the proposed method.


---

## Body

## 1. Introduction

With great developments of computing technologies and data mining methods, smart agriculture has attracted much attraction since it can greatly increase crop yields by effectively recommending methods to control pests [1, 2]. For example, the internet of vehicles with task scheduling [3, 4] can help formers to harvest crops automatically, and content-based crop image retrieval can help producers to keep track of plant growth in real time, which contributes to developing disease control and production plans. Meanwhile, with the technological advancement, the form of crop monitoring is also undergoing tremendous changes, posing great challenges to the current machine learning-based methods [5–9], due to the collected data that are of high volume, high velocity, high value, and high variety [10, 11]. Thus, to mine patterns of data in smart agriculture requires novel methods.Image annotation, as a typical method for images analysis in agricultural big data, predicts labels for a given image, which can well match the image content [12]. In recent years, a large number of researchers have done extensive research on image annotation [13, 14]. For example, to reduce the semantic gap between visual features and text features, some researchers have proposed the generative model, which models image annotation as a joint likelihood distribution between images and labels. Nevertheless, the generative method only uses the image-label correlations, ignoring the relation over images. To use the relation over images, the discriminant model is proposed, focusing on finding the difference between images. Typically, this method trains a classifier to predict image labels, but the balance of sample labels has a large impact on the model performance. At the same time, some researchers proposed a graph model that utilizes all the data to build the intrinsic structure of unlabeled images and annotated images. Also, the nearest neighbor model is used to construct the label propagation graph, based on the theory that similar images share common labels [15, 16]. However, this method pays too much attention to the correlation between images, ignoring the image differences.To solve those problems, a nearest neighbor graph model is proposed in this paper, which combining superiorities of graph andK nearest theories. Specifically, the semantic neighbors of test image under each label are firstly searched to the semantic neighbor graph. Then, a preannotation score is obtained by graph learning of the semantic neighbor graph, considering relationships between images. The preannotation of the semantic neighbor graph can effectively solve the label imbalance problem, increasing the annotation probability of the rare labels and suppressing the high-frequency labels.Next, the relationships between labels are used to improve the accuracy of the image annotation. The previous work was simply to calculate the cooccurrence probability between labels without considering the imbalance of cooccurrence between labels. For example, “Sea” and “Ship” are likely to appear in the same picture, and the two labels are strongly related. However, the possibility of “sea” in “ship” images may be greater than that of “ship” in “sea” images. This is because the “sea” is associated with more things, such as “fish” and “coral.” To solve this imbalance of labels, the random dot product graph is used to mine the deep associations of labels. After that, visual differences that lead to lower similarity between similar images are used to further improve the performance of the proposed method. Finally, the naive Bayes nearest neighbor (NBNN) classifier is used to establish a joint likelihood between images and labels because of its simplicity and efficiency. Finally, the proposed method is conducted on Corel 5K and IAPR TC12. And results show that the proposed method has obvious improvement in terms of label recall. The main contributions of this paper are as follows:(i)
To effectively solves the label imbalance problem, the semantic neighbor graph learning is proposed to generate preannotation based on the nearest neighbor where all the labels are included in the initial label candidate(ii)
To mine the deep associations of labels, the random dot product graph is proposed, balancing the distributions of cooccurrence of paired labelsThe remaining content structure of the thesis is as follows: in Section2, we introduce the related work of image annotation. Then, in Section 3, we present our image annotation framework and concrete implementation of the framework. The datasets, experimental, settings, and results are illustrated in Section 4. The paper is concluded in Section 5.


## 2. Related Work

Image annotation has been a research hotspot which attracts increasing attention. Many fields are related to it, and they can benefit from the progress of each other. For example, the internet of vehicles [17, 18] can provide a lot of images to be annotated, and the better annotated images can be used to train the distinguishing model for better driving vehicles. Thus, a large number of researchers have introduced many kinds of methods to image annotation in recent years. They can be divided into four classes: the generating model, discriminating model, graph learning model, and nearest neighbor model.


### 2.1. Generating Model

To solve the problem in image annotation, some scholars proposed the mixture model, which is one of the generating model. For example, Jeon et al. proposed a cross-media relevance model (CMRM) [19]. In this method, image is segmented into several blobs, which can be clustered. Then, they calculate the probability between words and images by establishing maximum likelihood estimation. However, this method is affected by clustering of the image feature. Therefore, a continuous relevance model (CRM) [20] was proposed by Lavrenko et al., which used a continuous image feature. The method calculates the probability of labeling the word using polynomial distribution. But this method needs to store a large kernel matrix, resulting in a computational burden.In order to solve the hybrid model’s “visual ambiguity” problem, that visual similarities do not mean semantic similarities, researchers proposed the topic model. The topic model can be thought as a hybrid model with a particular topic used to portray the relationship between the image and the label. For example, Barnard et al. proposed a method with modeling multimodal cooccurrence [21]. This method imports several topic variables and attempts to find the relation between labels and visual features through probability. But this method is affected by model initialization. Blei et al. presented the LDA method [22], which used the Dirichlet distribution in the stage of choosing topics and words. However, the topic model is complex and has too many parameters. Thus, it is not suitable for large-scale datasets.


### 2.2. Discriminating Model

To solve the problem of the generating model, some researchers proposed the discriminating model. The discriminating model uses multilabel classification to solve the problem of image annotation. This method trains a classifier for each label, then determines which label the image belongs to by the classifier. For instance, Carneiro et al. proposed SML [23], which established a relationship between semantic labels and semantic classes. This method does not need to segment the image in advance, but it requires a high balance of classes and does not consider the relationship between labels. Sun et al. [24] used sparse factor representation to come up with sparse structure based on label dependency for weakening the negative effect caused by the unbalance of labels. But this method does not consider the potential relationship between images with labels and the lack of high-quality image dataset.


### 2.3. Graph-Based Learning Model

To address the issue of insufficient labeled images, some investigators put forward the graph learning model. The graph learning model is a semisupervised learning model, which uses labeled and unlabeled images to create the graph, then uses the Laplacian matrix for transferring labels. Liu et al. proposed the nearest spanning chain (NSC) [25]. In this method, they use a graph algorithm to transfer labels, but they do not take into account the relationship between images and labels. So Su and Xue proposed GLKNN [26]. In the stage of initializing graph weights, the cooccurrence relationship between labels is considered. However, they discount that the cooccurrence relationship is unbalance. This graph model only considers visual features and has no regard for problem of “visual ambiguity.” Meanwhile, in the condition of a big image dataset, this model has high time complexity and poor annotation performance.


### 2.4. Nearest Neighbor Model

Because the nearest neighbor model performs better under big data conditions, this method has attracted more and more researchers. This model transfers the image annotation problem into the image retrieval problem. First, this method needs to search images which are highly similar to unlabeled images, then labels unlabeled images by means of label transmission. For example, Guillaumin et al. proposed a method based on weighted KNN called TagProp [27]. In this case, the labeled probability of lower frequency labels is increased and the labeled probability of higher frequency labels is suppressed. And Verma and Jawahar put forward 2PKNN [28], in which image distance metric learning was used. They adjust the weights of different visual features in order to make the relationship between visual features more consistent with the relationship between image semantics. In CCAKNN [29], the aim is to get the image subset of each semantic label. They map two features to the same subspace and model the visual features by using the Bayesian probability model. However, the nearest neighbor model only uses the similarity between images and ignores the difference between the image samples.


## 2.1. Generating Model

To solve the problem in image annotation, some scholars proposed the mixture model, which is one of the generating model. For example, Jeon et al. proposed a cross-media relevance model (CMRM) [19]. In this method, image is segmented into several blobs, which can be clustered. Then, they calculate the probability between words and images by establishing maximum likelihood estimation. However, this method is affected by clustering of the image feature. Therefore, a continuous relevance model (CRM) [20] was proposed by Lavrenko et al., which used a continuous image feature. The method calculates the probability of labeling the word using polynomial distribution. But this method needs to store a large kernel matrix, resulting in a computational burden.In order to solve the hybrid model’s “visual ambiguity” problem, that visual similarities do not mean semantic similarities, researchers proposed the topic model. The topic model can be thought as a hybrid model with a particular topic used to portray the relationship between the image and the label. For example, Barnard et al. proposed a method with modeling multimodal cooccurrence [21]. This method imports several topic variables and attempts to find the relation between labels and visual features through probability. But this method is affected by model initialization. Blei et al. presented the LDA method [22], which used the Dirichlet distribution in the stage of choosing topics and words. However, the topic model is complex and has too many parameters. Thus, it is not suitable for large-scale datasets.


## 2.2. Discriminating Model

To solve the problem of the generating model, some researchers proposed the discriminating model. The discriminating model uses multilabel classification to solve the problem of image annotation. This method trains a classifier for each label, then determines which label the image belongs to by the classifier. For instance, Carneiro et al. proposed SML [23], which established a relationship between semantic labels and semantic classes. This method does not need to segment the image in advance, but it requires a high balance of classes and does not consider the relationship between labels. Sun et al. [24] used sparse factor representation to come up with sparse structure based on label dependency for weakening the negative effect caused by the unbalance of labels. But this method does not consider the potential relationship between images with labels and the lack of high-quality image dataset.


## 2.3. Graph-Based Learning Model

To address the issue of insufficient labeled images, some investigators put forward the graph learning model. The graph learning model is a semisupervised learning model, which uses labeled and unlabeled images to create the graph, then uses the Laplacian matrix for transferring labels. Liu et al. proposed the nearest spanning chain (NSC) [25]. In this method, they use a graph algorithm to transfer labels, but they do not take into account the relationship between images and labels. So Su and Xue proposed GLKNN [26]. In the stage of initializing graph weights, the cooccurrence relationship between labels is considered. However, they discount that the cooccurrence relationship is unbalance. This graph model only considers visual features and has no regard for problem of “visual ambiguity.” Meanwhile, in the condition of a big image dataset, this model has high time complexity and poor annotation performance.


## 2.4. Nearest Neighbor Model

Because the nearest neighbor model performs better under big data conditions, this method has attracted more and more researchers. This model transfers the image annotation problem into the image retrieval problem. First, this method needs to search images which are highly similar to unlabeled images, then labels unlabeled images by means of label transmission. For example, Guillaumin et al. proposed a method based on weighted KNN called TagProp [27]. In this case, the labeled probability of lower frequency labels is increased and the labeled probability of higher frequency labels is suppressed. And Verma and Jawahar put forward 2PKNN [28], in which image distance metric learning was used. They adjust the weights of different visual features in order to make the relationship between visual features more consistent with the relationship between image semantics. In CCAKNN [29], the aim is to get the image subset of each semantic label. They map two features to the same subspace and model the visual features by using the Bayesian probability model. However, the nearest neighbor model only uses the similarity between images and ignores the difference between the image samples.


## 3. Our Approach

A new image annotation framework is proposed on the basis of graph learning, which is composed of three steps. First, we propose the nearest neighbor graph based on the principle that similar images share labels, to obtain preannotation results. Next, the association between labels is used to improve the accuracy of image annotation by the random dot product graph, which deeply mines the internal association of labels to increase probabilities of labeling weak labels. Finally, the naive Bayes nearest neighbor classifier is used to calculate the distance between images and labels. The main process of the proposed method is shown in Algorithm1:Algorithm 1.
Framework of the proposed method.Input: imagesOutput: predicted labels1: Find the best nearest neighbor images by improving the nearest neighbors.2: Construct a similar matrixW through Wij=exp−DISxi,xj/σ2.3: Mine the deep relationship between images, using random dot product graph (RDPG) for refactoring,PXG=∏i≠jxi⋅xjaij1−xi⋅xj1−aij.4: Iterate to convergence throughR∗t+1=αI⋅Rt+1−αY.5: Build a semantic matrix throughPvm∣vi=summ,i/sumi6: Consider the effect of the association between labels on the results of the annotations,R′t+1=αI⋅R∗t+1−αP.7: Consider the relationship between images and labels,DisM,i=log1/n∑K∈NM.iKdM,dK.8: Return the final score of the label,ScoreM,i=σRM,i+ωRM,i∗+ξDisM,i.


### 3.1. RPDG-Based Image Graph for Image Annotation

LetX=x1,x2,⋯,xn be a collection of n images, V=v1,⋯,vl be a set of labels, and the training set be denoted by T=x1,y1,⋯,xn,yn, which is composed of each marked image xi and corresponding label set yi which is presented as a binary vector. For example, if the nth image is labeled by mth label, ynm=1; otherwise, ynm=0. To solve the problem of label imbalance, the nearest neighbor graph is constructed based on the neighbor image sets.For a given imageM to be labeled, its neighbor image set NeiM constitutes a set SM. We select a set of k nearest neighbor images to form a set T for each label based on the visual distance of images. The main idea of this method is that similar images have a high probability of passing labels. The traditional approach finds the semantic nearest neighbor by using the weighted multiple vision distance, without considering the probability that two images are neighbors to each other is different. As a result, the nearest neighbors of unlabeled images would have some noise images, which brings noise labeled and decreases the image annotation accuracy. Due to the complex distribution of visual features in images, some images in the image dataset have a higher probability of being selected as neighbor images, some images are less likely to be selected, and others may not even be selected. But in practice, the nearest neighbor relationship between images is not symmetric. For example, the image M is a nearest neighbor image of the image N, but the image N is not a nearest neighbor image of the image M, which degrades the accuracy of the conventional methods in selecting nearest neighbor images. Therefore, we propose a novel way to select the nearest neighbor images.We propose a novel method based on the common neighbor images. We use this improved method to select the nearest neighbors of the test image, reducing the noise labels. Our method first sorts images of each label according to the visual distance and selects the first2k images. Then, our method selects the nearest neighbors for each of these 2k images. Sorting according to the number of their common neighbor images, the top K images are selected as the neighbor images of image M. The nearest neighbor images selected in this way are more consistent with the image similarity under actual conditions. And the number of images which are related to the test image in semantic is also increased. As a result, the possibility of introducing a noise image is reduced and the accuracy of the annotation improves.We assume a simple graphG=V,E, where V is the vertex set representing images in SM. The edge set is denoted as E representing a relationship between two images. The weight W of the edge is the similarity of two images.The principle of the graph-based learning method is semisupervised learning. This method uses the image features and annotation information of the training data. Then, it iterates the similarity matrix of the training data and passes the appropriate semantic label from the labeled images to the unlabeled images based on this similarity, which is a preliminary result of the first step.The detail of this method is as follows:(Step 1)
Construct a similar matrixWk×k of SM set as(1)Wij=exp−DISxi,xjσ2,where DIS is a measure of distance. And Wii=0, because there is no self-loop in the graph
(Step 2)
Symmetrically normalizeW by(2)I=D1/2WD1/2,where D is a diagonal matrix and Dii=∑j=1lWij(Step 3)
Iterate according to the Eq. (3) until convergence(3)Rt+1=αI⋅Rt+1−αY,R0=Y,where t is the number of iteration until convergence and α is the propagation parameter
(Step 4)
Label the unlabeled images according to the convergence matrixR∗Through the above steps, we finally get the tag score and ranking. On the basis of the above discussion, there are two key parts of the graph-based learning method: a similarity graphI and an initial state representation L. I describes the similarity between the test image and its nearest neighbor images, which provides a basis for the label transmission.Thus, the construction of a similarity graphI is very important. In constructing a graph in the traditional graph-based image annotation methods, the weight of the edge between the vertices (images) directly uses the visual distance. However, because of the existence of the “visual ambiguity,” this method may ignore the hidden relationships of the images. So different from the previous work, we use the random dot product graph to discover hidden relationships.The random dot product graph is a point-edge random graph model. For each nodevi,i=1,⋯,n in the node set V, a d-dimensional vector xi is randomly and uniformly selected from the d-dimensional unit space as the assignment of vi. The probability of the edge between each pair of nodes vi, vj is
(4)pij=fxi⋅xj.This probability is used for generating a random dot product graph as the assignmentX=x1,x2,⋯,xnd×n.The two main properties of random dot product graph are as follows:Property 1.
Clustering: the edges of random dot product graph appear with incompletely equal probability, with obvious clustering characteristics.Property 2.
Transitivity: if two nodes have strong connections with the third node at the same time, then the two nodes should also have a great correlation directly. Conversely, if two nodes have no other associated third node, then the probability that the two nodes are related should be small.Each edge in the random graph appears randomly and independently. According to the Bernoulli distribution, the random dot product graphGxV,E generates the edge set E according to the probability pij to obtain an observation graph. If the observation graph G=V,E is an undirected weighted graph and its adjacency matrix is A=aijn×n,aij∈0,1, then
(5)PXG=∏i≠jxi⋅xjaij1−xi⋅xj1−aij.Its log likelihood function is(6)LXG=∑i≠jaijlnxi⋅xj+1−aijln1−xi⋅xj.In the observation, the probability of the edge reflects the correlation between the nodes. It can be seen from Equation (6) that when LXG is maximum, the probability of the edge corresponds to the weight as much as possible. According to the principle of duality, we have
(7)maxLXG=minFZX,where FZX=∑i≠jxi⋅xj−aij2.Therefore, the objective function is expressed as(8)minFZX=min∑i≠jxi⋅xj−aij2where X=x1,x2,⋯,xn is a random assignment of n nodes, the probability of the edge is the inner product form, and the right side of Equation (8) is the Frobenius norm of the matrix, so it can be written as A≈XTX.Based on the above principles, we have the following algorithm.Algorithm 2.
Random dot product method for simple graphs.Input: the weight matrixW of the image data graph.Output: the weight matrix of random point product.1: Take an all-zero matrixD.2: Find spectral decomposition ofW+diagD.3:U is a matrix of d largest eigenvectors, U∈Rn×d. Λ~ is a d×d diagonal matrix composed of d largest eigenvalues, where each negative eigenvalue is changed to 0.4:X=UΛ~,D=diagX′X5: Return 2 untilD converges.6: CalculateLXG, return 1 until converges. T is the edge probability matrix after random reconstruction, where T=XX′.Based on the above method, for given nodesi and j, the Wij′ weighted distance is expressed as
(9)Wij′=Wij+ωTij.The random dot product graph improves the weight of the similar matrix. With the improvement of the nearest neighbor graph, we pay more attention to the internal relations between images. By this method, the weak label problem can be effectively solved.


### 3.2. Word-Based Graph Learning

The frequencies of the labels in the image dataset are different. The low-frequency labels are easily ignored during the annotating process, which leads to the accuracy decrease of the annotation. In the previous work, people usually used the semantic symbiosis between labels to solve this problem. However, there is a cooccurrence imbalance between the labels, which makes it impossible to significantly improve the label effect of the low-frequency label. By the transitive nature of the random dot product graph, we reconstruct the association graph of the label words and find the inherent hidden relationship between the labels. The random dot product graph can obtain the relationship between any annotated words. The probability of common semantic relations is large, and the probability of uncommon semantic relations is small, which is consistent with the real semantic relationship.In the label setV=v1,⋯,vl, we record the probability of label vi to label vm denoted by Pvm∣vi,
(10)Pvm∣vi=summ,isumi,m≠i,1,m=i,where summ,i represents the number of cooccurrences between labels vi and vm. In this paper, we abbreviate Pvm∣vi to Pim. Because of semantic cooccurrence imbalance, Pim is not equal to Pmi.We first get the transfer matrix between the labels according to Equation (10). P is reconstructed by random dot product to obtain P′. Bringing transfer matrix and the matrix R∗ obtained on the basis of graph learning into Equation (3), we iterate to get result R′.


### 3.3. Image to Word Relation

This relationship can be regarded as the possibility of having an image to produce a label. In most cases, the relationship can be estimated on a training set by some hypothetical distribution. In many methods, the image is clustered and divided into several “blob,” with each “blob” corresponding to a label word. However, in the process of clustering, problems will be caused due to that the underlying features are similar, but the actual contents are different, which makes the blob itself wrong. In this paper, the method used to calculate the image to word distance is the naive Bayes nearest neighbor (NBNN) classifier [30] for image classification. This method is simple and has good performance. At the same time, it calculates the association between the whole image and the annotated label, avoiding the wrong correspondence between the “blob” and the annotated label.The features of the image are recorded asf, and NM,i represents a collection of NeiM annotated as label vi. The definition of image to word distance is
(11)DisM,i=log1n∑k∈NM.iKfM,fk,where n is the figure for images in NeiI,k. K is the Gaussian kernel function:
(12)KfM,fk=exp−12σ2fM−fk2.


### 3.4. Combination of Three Scores

Finally, we combine the two scores based on the graph learning with the score of the image-to-label distance to get the final score, which is the basis for the final labels.(13)ScoreM,i=σRM,i+ωRM,i∗+ξDisM,i,where RM,i′ is a score based on the association between images and R∗M,i is the probability that the image M is labeled with the label vi based on an association between labels. In addition, σ+ω+ξ=1.


## 3.1. RPDG-Based Image Graph for Image Annotation

LetX=x1,x2,⋯,xn be a collection of n images, V=v1,⋯,vl be a set of labels, and the training set be denoted by T=x1,y1,⋯,xn,yn, which is composed of each marked image xi and corresponding label set yi which is presented as a binary vector. For example, if the nth image is labeled by mth label, ynm=1; otherwise, ynm=0. To solve the problem of label imbalance, the nearest neighbor graph is constructed based on the neighbor image sets.For a given imageM to be labeled, its neighbor image set NeiM constitutes a set SM. We select a set of k nearest neighbor images to form a set T for each label based on the visual distance of images. The main idea of this method is that similar images have a high probability of passing labels. The traditional approach finds the semantic nearest neighbor by using the weighted multiple vision distance, without considering the probability that two images are neighbors to each other is different. As a result, the nearest neighbors of unlabeled images would have some noise images, which brings noise labeled and decreases the image annotation accuracy. Due to the complex distribution of visual features in images, some images in the image dataset have a higher probability of being selected as neighbor images, some images are less likely to be selected, and others may not even be selected. But in practice, the nearest neighbor relationship between images is not symmetric. For example, the image M is a nearest neighbor image of the image N, but the image N is not a nearest neighbor image of the image M, which degrades the accuracy of the conventional methods in selecting nearest neighbor images. Therefore, we propose a novel way to select the nearest neighbor images.We propose a novel method based on the common neighbor images. We use this improved method to select the nearest neighbors of the test image, reducing the noise labels. Our method first sorts images of each label according to the visual distance and selects the first2k images. Then, our method selects the nearest neighbors for each of these 2k images. Sorting according to the number of their common neighbor images, the top K images are selected as the neighbor images of image M. The nearest neighbor images selected in this way are more consistent with the image similarity under actual conditions. And the number of images which are related to the test image in semantic is also increased. As a result, the possibility of introducing a noise image is reduced and the accuracy of the annotation improves.We assume a simple graphG=V,E, where V is the vertex set representing images in SM. The edge set is denoted as E representing a relationship between two images. The weight W of the edge is the similarity of two images.The principle of the graph-based learning method is semisupervised learning. This method uses the image features and annotation information of the training data. Then, it iterates the similarity matrix of the training data and passes the appropriate semantic label from the labeled images to the unlabeled images based on this similarity, which is a preliminary result of the first step.The detail of this method is as follows:(Step 1)
Construct a similar matrixWk×k of SM set as(1)Wij=exp−DISxi,xjσ2,where DIS is a measure of distance. And Wii=0, because there is no self-loop in the graph
(Step 2)
Symmetrically normalizeW by(2)I=D1/2WD1/2,where D is a diagonal matrix and Dii=∑j=1lWij(Step 3)
Iterate according to the Eq. (3) until convergence(3)Rt+1=αI⋅Rt+1−αY,R0=Y,where t is the number of iteration until convergence and α is the propagation parameter
(Step 4)
Label the unlabeled images according to the convergence matrixR∗Through the above steps, we finally get the tag score and ranking. On the basis of the above discussion, there are two key parts of the graph-based learning method: a similarity graphI and an initial state representation L. I describes the similarity between the test image and its nearest neighbor images, which provides a basis for the label transmission.Thus, the construction of a similarity graphI is very important. In constructing a graph in the traditional graph-based image annotation methods, the weight of the edge between the vertices (images) directly uses the visual distance. However, because of the existence of the “visual ambiguity,” this method may ignore the hidden relationships of the images. So different from the previous work, we use the random dot product graph to discover hidden relationships.The random dot product graph is a point-edge random graph model. For each nodevi,i=1,⋯,n in the node set V, a d-dimensional vector xi is randomly and uniformly selected from the d-dimensional unit space as the assignment of vi. The probability of the edge between each pair of nodes vi, vj is
(4)pij=fxi⋅xj.This probability is used for generating a random dot product graph as the assignmentX=x1,x2,⋯,xnd×n.The two main properties of random dot product graph are as follows:Property 1.
Clustering: the edges of random dot product graph appear with incompletely equal probability, with obvious clustering characteristics.Property 2.
Transitivity: if two nodes have strong connections with the third node at the same time, then the two nodes should also have a great correlation directly. Conversely, if two nodes have no other associated third node, then the probability that the two nodes are related should be small.Each edge in the random graph appears randomly and independently. According to the Bernoulli distribution, the random dot product graphGxV,E generates the edge set E according to the probability pij to obtain an observation graph. If the observation graph G=V,E is an undirected weighted graph and its adjacency matrix is A=aijn×n,aij∈0,1, then
(5)PXG=∏i≠jxi⋅xjaij1−xi⋅xj1−aij.Its log likelihood function is(6)LXG=∑i≠jaijlnxi⋅xj+1−aijln1−xi⋅xj.In the observation, the probability of the edge reflects the correlation between the nodes. It can be seen from Equation (6) that when LXG is maximum, the probability of the edge corresponds to the weight as much as possible. According to the principle of duality, we have
(7)maxLXG=minFZX,where FZX=∑i≠jxi⋅xj−aij2.Therefore, the objective function is expressed as(8)minFZX=min∑i≠jxi⋅xj−aij2where X=x1,x2,⋯,xn is a random assignment of n nodes, the probability of the edge is the inner product form, and the right side of Equation (8) is the Frobenius norm of the matrix, so it can be written as A≈XTX.Based on the above principles, we have the following algorithm.Algorithm 2.
Random dot product method for simple graphs.Input: the weight matrixW of the image data graph.Output: the weight matrix of random point product.1: Take an all-zero matrixD.2: Find spectral decomposition ofW+diagD.3:U is a matrix of d largest eigenvectors, U∈Rn×d. Λ~ is a d×d diagonal matrix composed of d largest eigenvalues, where each negative eigenvalue is changed to 0.4:X=UΛ~,D=diagX′X5: Return 2 untilD converges.6: CalculateLXG, return 1 until converges. T is the edge probability matrix after random reconstruction, where T=XX′.Based on the above method, for given nodesi and j, the Wij′ weighted distance is expressed as
(9)Wij′=Wij+ωTij.The random dot product graph improves the weight of the similar matrix. With the improvement of the nearest neighbor graph, we pay more attention to the internal relations between images. By this method, the weak label problem can be effectively solved.


## 3.2. Word-Based Graph Learning

The frequencies of the labels in the image dataset are different. The low-frequency labels are easily ignored during the annotating process, which leads to the accuracy decrease of the annotation. In the previous work, people usually used the semantic symbiosis between labels to solve this problem. However, there is a cooccurrence imbalance between the labels, which makes it impossible to significantly improve the label effect of the low-frequency label. By the transitive nature of the random dot product graph, we reconstruct the association graph of the label words and find the inherent hidden relationship between the labels. The random dot product graph can obtain the relationship between any annotated words. The probability of common semantic relations is large, and the probability of uncommon semantic relations is small, which is consistent with the real semantic relationship.In the label setV=v1,⋯,vl, we record the probability of label vi to label vm denoted by Pvm∣vi,
(10)Pvm∣vi=summ,isumi,m≠i,1,m=i,where summ,i represents the number of cooccurrences between labels vi and vm. In this paper, we abbreviate Pvm∣vi to Pim. Because of semantic cooccurrence imbalance, Pim is not equal to Pmi.We first get the transfer matrix between the labels according to Equation (10). P is reconstructed by random dot product to obtain P′. Bringing transfer matrix and the matrix R∗ obtained on the basis of graph learning into Equation (3), we iterate to get result R′.


## 3.3. Image to Word Relation

This relationship can be regarded as the possibility of having an image to produce a label. In most cases, the relationship can be estimated on a training set by some hypothetical distribution. In many methods, the image is clustered and divided into several “blob,” with each “blob” corresponding to a label word. However, in the process of clustering, problems will be caused due to that the underlying features are similar, but the actual contents are different, which makes the blob itself wrong. In this paper, the method used to calculate the image to word distance is the naive Bayes nearest neighbor (NBNN) classifier [30] for image classification. This method is simple and has good performance. At the same time, it calculates the association between the whole image and the annotated label, avoiding the wrong correspondence between the “blob” and the annotated label.The features of the image are recorded asf, and NM,i represents a collection of NeiM annotated as label vi. The definition of image to word distance is
(11)DisM,i=log1n∑k∈NM.iKfM,fk,where n is the figure for images in NeiI,k. K is the Gaussian kernel function:
(12)KfM,fk=exp−12σ2fM−fk2.


## 3.4. Combination of Three Scores

Finally, we combine the two scores based on the graph learning with the score of the image-to-label distance to get the final score, which is the basis for the final labels.(13)ScoreM,i=σRM,i+ωRM,i∗+ξDisM,i,where RM,i′ is a score based on the association between images and R∗M,i is the probability that the image M is labeled with the label vi based on an association between labels. In addition, σ+ω+ξ=1.


## 4. Experiment

In this section, we introduce two datasets used in the experiment and the extraction of features of two datasets. Also, the evaluation indicators of the image annotation methods are given.


### 4.1. Datasets

During the experiment, we used two datasets. Table1 shows the statistics of these datasets.Table 1
Details of the training set of the two datasets. The number of images and labels are given in the format mean/maximum.
DatasetCorel 5KIAPR TC12# of img.499919627Vocab. size260291Training img.450017665Testing img.4991962Labels per img.3.4/55.836/10.04Img. per label5.7/23347.7/4999Corel 5K [31]. This dataset contains 4,500 training images and 499 test images. It is divided into 50 themes, each with 100 images except the last. The dataset contains 260 labels. Each image is manually labeled with 1-5 different labels, and the average is 3.4.IAPR TC12 [32]. This dataset contains 19,627 images, where 17,665 are training images and 1962 are test images. This dataset contains a total of 291 tags, and each image in the dataset is averaged as 5.836 tags.


### 4.2. Feature

The first step in our approach is to extract features, which is a very important part. Feature extraction has a profound impact on the performance of image annotation systems. Recently, CNN has been widely applied to feature extraction of images. Compared with using 15 handcrafted features, it is not necessary to use metric learning to determine the optimal weight of each feature, so it is easier to determine the parameters. We use CNN to extract individual features instead of handcrafted features, which can effectively reduce the number of features and improve system accuracy.


### 4.3. Evaluation Metrics

In our experiments, we use the same evaluation method as [33] to effectively evaluate and compare our method with the previous methods. In our approach, we give each image five labels. Then, we calculate the labeling precision and recall for each label in each image of the test set. Suppose that a label vk marking n1 images in the ground truth, and the number of images marked as vk during the test is n2, in which the correct number of marks is recorded as n3. The method of calculating the precision of the label vk is p=n3/n2 and recall of the label vk is r=n3/n1. These values are obtained by calculating each label, and then, the mean value is calculated to get the average precision P and the average recall R. Define that F1 is the score for combining P and R, F1=2PR/P+R. And define that N+ represents the number of tags that have been correctly tagged at least once, which indicates the ability of our proposed method to solve class imbalance and weak label problems.


## 4.1. Datasets

During the experiment, we used two datasets. Table1 shows the statistics of these datasets.Table 1
Details of the training set of the two datasets. The number of images and labels are given in the format mean/maximum.
DatasetCorel 5KIAPR TC12# of img.499919627Vocab. size260291Training img.450017665Testing img.4991962Labels per img.3.4/55.836/10.04Img. per label5.7/23347.7/4999Corel 5K [31]. This dataset contains 4,500 training images and 499 test images. It is divided into 50 themes, each with 100 images except the last. The dataset contains 260 labels. Each image is manually labeled with 1-5 different labels, and the average is 3.4.IAPR TC12 [32]. This dataset contains 19,627 images, where 17,665 are training images and 1962 are test images. This dataset contains a total of 291 tags, and each image in the dataset is averaged as 5.836 tags.


## 4.2. Feature

The first step in our approach is to extract features, which is a very important part. Feature extraction has a profound impact on the performance of image annotation systems. Recently, CNN has been widely applied to feature extraction of images. Compared with using 15 handcrafted features, it is not necessary to use metric learning to determine the optimal weight of each feature, so it is easier to determine the parameters. We use CNN to extract individual features instead of handcrafted features, which can effectively reduce the number of features and improve system accuracy.


## 4.3. Evaluation Metrics

In our experiments, we use the same evaluation method as [33] to effectively evaluate and compare our method with the previous methods. In our approach, we give each image five labels. Then, we calculate the labeling precision and recall for each label in each image of the test set. Suppose that a label vk marking n1 images in the ground truth, and the number of images marked as vk during the test is n2, in which the correct number of marks is recorded as n3. The method of calculating the precision of the label vk is p=n3/n2 and recall of the label vk is r=n3/n1. These values are obtained by calculating each label, and then, the mean value is calculated to get the average precision P and the average recall R. Define that F1 is the score for combining P and R, F1=2PR/P+R. And define that N+ represents the number of tags that have been correctly tagged at least once, which indicates the ability of our proposed method to solve class imbalance and weak label problems.


## 5. Result

In this subsection, we describe the performance of the proposed method compared with the previously proposed methods. Table2 gives the experimental results on the datasets Corel 5K and IAPR CT12. This table shows that our method outperforms the previous work. Among the Corel 5K, our accuracy is the second highest, and our tag recall number is the highest. Detailed results and analysis of the experiment will be presented in the following sections.Table 2
The performance of our proposed method is compared with the previous work on Corel 5K and IAPR TC12 datasets in detail.P: average precision; R: average recall; F: the combination of P and R; N+: number of labels with nonzero recall value.
MethodCorel 5KIAPR TC12P (%)R (%)F (%)N+P (%)R (%)F (%)N+CRM [20]161917107MBRM [34]2424241222423223SML [23]232926137JEC [35]2732291392928250TGLM [25]252927131TagPropσSD [27]2835311454130259TagProp ML [27]3137341464825227TagPropσML [27]3342371604635266KSVM-VT [33]3242361794726268FastTag [36]3243371664726280GLKNN [26]36474118441362822PKNN [28]3940391774932274LDMKL [37]294435179IDFRW [38]384943185493138275CCAKNN [29]414342185414041278RDPGKNN (this work)404540195403838283It is worth noting that we have selected several methods based on nearest neighbors as comparison methods. As shown in Table2, our method performs better than JEC in all aspects. Compared with 2PKNN, our recall value and N+ value is also much higher on the Corel 5K dataset. And our RDPGKNN is superior to TagProp. The comparison with these methods shows that the graph learning method also has unique advantages in the field of image annotation and proves the validity and rationality of the label using the graph learning method for propagation.We also compare RDPGKNN with graph-based learning algorithms, and the results show that our approach is generally better than previous work. Since most of the graph learning algorithms are applied to small vocabularies, there are few research methods on image annotation based on graph learning in Corel 5K and other datasets, so we mainly choose TGLM and GLKNN. In comparison with TGLM, the experimental results show that our method is obviously superior in Corel 5K. This shows the advantage of the nearest neighbor method, which effectively solves the label imbalance problem, so that each annotation word has the opportunity of being selected. At the same time, compared with GLKNN, ourN+ has a significant improvement, because we consider label cooccurrence asymmetry. Using graph-based learning to calculate the label transition probability can maximize the selected probability of low-frequency tags, provide more appropriate weights for the transfer between tags, and improve the performance of the image tagging system.On the IAPR CT12, our algorithm also has excellent performance. Compared with the previous work, the RDPGKNN method recalls the most labels. On this basis, our recall rate is second only to that of the CAAKNN method, and the recall rate is greatly improved on the premise that the accuracy does not drop too much. Compared to the GLKNN based on the graph, the recall rate of our method has also increased by 2%. This also confirms the need to consider the problem of cooccurrence imbalance between images. Figure1 shows some examples of the annotation of our method on two datasets. Among them, we use the black mark to indicate the labels annotated in ground truth and annotated with RDPGKNN, and the red mark does not appear in the ground truth. It should be noted that some images in the dataset have fewer than five labels annotated in ground truth, but our method must label five labels.Figure 1
The result of annotating some images in the Corel 5K dataset of our method. The figure shows the test image, the ground truth labels, and the predicted labels, where red indicates that the label is not present in the ground truth labels.After comparing with all methods, we find that our method effectively increased the value ofN+. This shows that compared with the traditional methods, our method has strong performance in recall, and the other performance is almost unchanged. Also, the problem that some labels cannot be selected due to the unbalanced label co-occurrence phenomenon is solved.


## 6. Conclusion

In this paper, a reconstitution graph learning model is proposed to for image annotation in smart agriculture. To solve the weak label problem, a nearest neighbor graph learning model is proposed to get the prelabels. Meanwhile, for the cooccurrence imbalance between labels, the random dot product graph is used to explore the intrinsic links between labels. Many experiments on the Corel 5K and IAPR TC12 are conducted, and the result shows that the recall of our method is much larger than that of the previous graph-based learning methods. At the same time, our accuracy and recall rate are basically the same as the latest methods. In the future, we will force on the computational complexity of the proposed method and the depth correlation between labels and images in the annotation process.



---

*Source: 8818616-2020-12-14.xml*