Search

Cross-media retrieval (CMR) offers a flexible retrieval experience across multiple modalities. Existing CMR approaches are constrained by the assumption that the paired modalities are available in training, and they leverage the data of all modalities to obtain a common representation. However, as dealing with the data from new modality, the previous all modalities need to be re-trained, compromising the flexibility and practicality of CMR. In this paper, we propose an approach termed learning Modality-Agnostic Representation for Scalable cross-media retrieval (MARS), which allows each modality to be trained independently. To be specific, MARS treats the label information as a distinct modality, and introduces a label parsing module LabNet to generate semantic representation for correlating different modalities. Meanwhile, MARS constructs the modality-specific representation module DataNet to obtain the modality-shared representation and modality-exclusive representation equipped with unbiased semantic classification. Technically, for the first modality, we jointly train the LabNet and its DataNet to preserve the semantic similarity between the Label-derived representation and the modality-shared representation. For new modalities, MARS employs the well-learned LabNet to extract the representation in labels, and then such representation is served as the privilege to guide the associated DataNet training via the same objective. Furthermore, we assign the same classifier to the representation module of all modalities for better semantic alignment. With the above schema, the obtained modality-shared representation is considered to be modality-agnostic. Extensive experiments on several benchmark multi-modality datasets demonstrate that the proposed MARS achieves better results than existing methods. [ABSTRACT FROM AUTHOR]

With the rapid growth of multimedia data on the Internet, there has been a rapid rise in the demand for visual–textual cross-media retrieval between images and sentences. However, the heterogeneous property of visual and textual data brings huge challenges to measure the cross-media similarity for retrieval. Although existing methods have achieved great progress with the strong learning ability of the deep neural network, they rely heavily on the scale of training data with manual annotation, that is, either pairwise image–sentence annotation or category annotation as supervised information for visual–textual correlation learning, which are extremely labor and time consuming to collect. Without any pairwise or category annotation, it is highly challenging to construct a correlation between images and sentences due to their inconsistent distributions and representations. But people can naturally understand the correlation between visual and textual data in high-level semantic, and those images and sentences containing the same group of semantic concepts can be easily matched in human brain. Inspired by the above human cognitive process, this article proposes an unsupervised visual–textual correlation learning (UVCL) approach to construct correlations without any manual annotation. The contributions are summarized as follows: 1) unsupervised semantic-guided cross-media correlation mining is proposed to bridge the heterogeneous gap between visual and textual data. We measure the semantic matching degree between images and sentences, and generate descriptive sentences according to the concepts extracted from images to further augment the training data in an unsupervised manner. Therefore, the approach can exploit the semantic knowledge within both visual and textual data to reduce the gap between them for further correlation learning and 2) unsupervised visual–textual fine-grained semantic alignment is proposed to learn cross-media correlation by aligning the fine-grained visual local patches and textual keywords with fine-grained soft attention as well as semantic-guided hard attention, and the results can effectively highlight the fine-grained semantic information within both images and sentences to boost visual–textual alignment. Extensive experiments are conducted to perform visual–textual cross-media retrieval in unsupervised setting without any manual annotation on two widely used datasets, namely, Flickr-30K and MS-COCO, which verify the effectiveness of our proposed UVCL approach. [ABSTRACT FROM AUTHOR]

Reasoning is one of the central topics in artificial intelligence. As an important reasoning paradigm, entailment recognition has attracted much research interest, which judges if a hypothesis can be inferred from given premises. However, existing research mainly focuses on text-based analysis, that is, recognizing textual entailment (RTE), which limits its depth and width. Actually, the knowledge and inference process of human are across different sensory organs like language and vision, with unique perspectives to represent complementary reasoning cues. It is significant to extend existing entailment recognition research to cross-media scenarios, that is, recognizing cross-media entailment (RCE). Therefore, this article focuses on one representative RCE task: visual–textual reasoning, and proposes the visual–textual hybrid sequence matching (VHSM) approach. VHSM can reason from image-text premises to text hypotheses, whose contributions are: 1) visual–textual hybrid multicontext inference is proposed to address RCE via matching with hybrid context embeddings, along with adaptive gated aggregation to obtain the final prediction results. It can fully exploit complementary visual–textual cue interaction during joint reasoning; 2) memory attention-based context embedding is proposed to sequentially encode hybrid context embeddings, with the memory attention networks to compare neighboring time–steps. This can capture the important memory dimensions by coefficient assignment, which fully exploits the visual–textual context correlation; and 3) cross-task and visual–textual transfer strategy is further proposed to enrich correlation training information for boosting reasoning accuracy, which transfers knowledge not only from cross-media retrieval task to RCE but also between corresponding text and image premises. The experimental results of recognizing visual–textual entailment task on the SNLI dataset verify the effectiveness of VHSM. [ABSTRACT FROM AUTHOR]

Existing cross-media retrieval methods are usually conducted under the supervised setting, which need lots of annotated training data. Generally, it is extremely labor-consuming to annotate cross-media data. So unsupervised cross-media retrieval is highly demanded, which is very challenging because it has to handle heterogeneous distributions across different media types without any annotated information. To address the above challenge, this paper proposes Domain Adaptation with Scene Graph (DASG) approach, which transfers knowledge from the source domain to improve cross-media retrieval in the target domain. Our DASG approach takes Visual Genome as the source domain, which contains image knowledge in the form of scene graph. The main contributions of this paper are as follows: First, we propose to address unsupervised cross-media retrieval by domain adaptation. Instead of using the labor-consuming annotated information of cross-media data in the training stage, our DASG approach learns cross-media correlation knowledge from Visual Genome, and then transfers the knowledge to cross-media retrieval through media alignment and distribution alignment. Second, our DASG approach utilizes fine-grained information via scene graph representation to enhance generalization capability across domains. The generated scene graph representation builds (subject $\rightarrow $ relationship $\rightarrow $ object) triplets by exploiting objects and relationships within image and text, which makes the cross-media correlation more precise and promotes unsupervised cross-media retrieval. Third, we exploit the related tasks including object and relationship detection for learning more discriminative features across domains. Leveraging the semantic information of objects and relationships improves cross-media correlation learning for retrieval. Experiments on two widely-used cross-media retrieval datasets, namely Flickr-30K and MS-COCO, show the effectiveness of our DASG approach. [ABSTRACT FROM AUTHOR]

Multi-media data including image, video, text, audio, and 3D model, has been fast emerging on the Internet. Jointly correlating the data of various media types is a challenging task. With the considerable learning ability of deep network, existing works mainly construct multi-pathway network to learn cross-media correlation, where each pathway is for one media type. However, with number of media types increasing, existing methods face the problems of high repetition and complexity, leading to overfitting and poor generalization ability, which makes adverse effect on correlation learning. For addressing the above issues, we propose cross-media deep compression and regularization (CDCR) approach for quintuple-media joint correlation learning: 1) cross-media partial weight-sharing networks is proposed, where a part of parameters are commonly shared among multiple pathways, to exploit common characteristics across different media types for capturing intrinsic cross-media correlation; 2) we propose media-adaptive network pruning to drop connections between weakly-correlated neurons, which can emphasize media-specific characteristics adaptively; and 3) cross-media network regularization is proposed to utilize relationships among quintuple-media data, which can guarantee generalization ability and enhance intra-media and inter-media correlation. The experiments verify the effectiveness of our approach, which outperforms the state-of-the-art methods on two very challenging datasets, including a large-scale dataset PKU XMediaNet with more than 100 000 quintuple-media instances. [ABSTRACT FROM AUTHOR]

Deep hashing methods have received much attention recently, which achieve promising results by taking advantage of the strong representation power of deep networks. However, most existing deep hashing methods learn a whole set of hashing functions independently, while ignore the correlations between different hashing functions that can promote the retrieval accuracy greatly. Inspired by the sequential decision ability of deep reinforcement learning, we propose a new Deep Reinforcement Learning approach for Image Hashing (DRLIH). Our proposed DRLIH approach models the hashing learning problem as a sequential decision process, which learns each hashing function by correcting the errors imposed by previous ones and promotes retrieval accuracy. To the best of our knowledge, this is the first work to address hashing problem from deep reinforcement learning perspective. The main contributions of our proposed DRLIH approach can be summarized as follows: (1) We propose a deep reinforcement learning hashing network. In the proposed network, we utilize recurrent neural network (RNN) as agents to model the hashing functions, which take actions of projecting images into binary codes sequentially, so that the current hashing function learning can take previous hashing functions’ error into account. (2) We propose a sequential learning strategy based on proposed DRLIH. We define the state as a tuple of internal features of RNN's hidden layers and image features, which can reflect history decisions made by the agents. We also propose an action group method to enhance the correlation of hash functions in the same group. Experiments on three widely-used datasets demonstrate the effectiveness of our proposed DRLIH approach. [ABSTRACT FROM AUTHOR]

The rapidly developing information technology leads to a fast growth of visual and textual contents, and it comes with huge challenges to make correlation and perform cross-media retrieval between images and sentences. Existing methods mainly explore cross-media correlation from either global-level instances as the whole images and sentences, or local-level fine-grained patches as the discriminative image regions and key words, which ignore the complementary information from the relation between local-level fine-grained patches. Naturally, relation understanding is highly important for learning cross-media correlation. People focus on not only the alignment between discriminative image regions and key words, but also their relations lying in the visual and textual context. Therefore, in this paper, we propose Multi-level Adaptive Visual-textual Alignment (MAVA) approach with the following contributions. First, we propose cross-media multi-pathway fine-grained network to extract not only the local fine-grained patches as discriminative image regions and key words, but also visual relations between image regions as well as textual relations from the context of sentences, which contain complementary information to exploit fine-grained characteristics within different media types. Second, we propose visual-textual bi-attention mechanism to distinguish the fine-grained information with different saliency from both local and relation levels, which can provide more discriminative hints for correlation learning. Third, we propose cross-media multi-level adaptive alignment to explore global, local and relation alignments. An adaptive alignment strategy is further proposed to enhance the matched pairs of different media types, and discard those misalignments adaptively to learn more precise cross-media correlation. Extensive experiments are conducted to perform image-sentence matching on 2 widely-used cross-media datasets, namely Flickr-30K and MS-COCO, comparing with 10 state-of-the-art methods, which can fully verify the effectiveness of our proposed MAVA approach. [ABSTRACT FROM AUTHOR]

The heterogeneity gap leads to inconsistent distributions and representations between image and text, which rises a challenging task to measure their similarities and construct cross-media correlation between them. The existing works mainly model the cross-media correlation in a common subspace, which causes insufficient correlation modeling in such third-party subspace with intermediate unidirectional transformation. Inspired by the recent advances of neural machine translation, which aims to establish a corresponding relationship between two entirely different languages, we can naturally discover that it has striking common characteristic with cross-media correlation learning to consider image and text as bilingual pairs, where the image is treated as a special kind of language to provide visual description, so that bidirectional transformation can be conducted between image and text to effectively explore cross-media correlation in the feature space of each media type. Thus, we propose a reinforced cross-media bidirectional translation (RCBT) approach to model the correlation between visual and textual descriptions. First, cross-media bidirectional translation mechanism is proposed to conduct direct transformation between the bilingual pairs of visual and textual descriptions bidirectionally, where the cross-media correlation can be effectively captured in both feature spaces of image and text through bidirectional translation training. Second, cross-media context-aware network with residual attention is proposed to exploit the rich spatial and temporal context hints with cross-media convolutional recurrent neural network, which can lead to more precise correlation learning for promoting bidirectional translation process. Third, cross-media reinforcement learning is proposed to perform a two-agent communication game played as a round between image and text to boost the bidirectional translation process, and we further extract inter-media and intra-media reward signals to provide complementary clues for learning cross-media correlation. Extensive experiments are conducted on cross-media retrieval to verify the effectiveness of our proposed RCBT approach, compared with 11 state-of-the-art methods on three cross-media datasets. [ABSTRACT FROM AUTHOR]

Existing cross-media retrieval methods are mainly based on the condition where the training set covers all the categories in the testing set, which lack extensibility to retrieve data of new categories. Thus, zero-shot cross-media retrieval has been a promising direction in practical application, aiming to retrieve data of new categories (unseen categories), only with data of limited known categories (seen categories) for training. It is challenging for not only the heterogeneous distributions across different media types, but also the inconsistent semantics across seen and unseen categories need to be handled. To address the above issues, we propose dual adversarial distribution network (DADN), to learn common embeddings and explore the knowledge from word-embeddings of different categories. The main contributions are as follows. First, zero-shot cross-media dual generative adversarial networks architecture is proposed, in which two kinds of generative adversarial networks (GANs) for common embedding generation and representation reconstruction form dual processes. The dual GANs mutually promote to model semantic and underlying structure information, which generalizes across different categories on heterogeneous distributions and boosts correlation learning. Second, distribution matching with maximum mean discrepancy criterion is proposed to combine with dual GANs, which enhances distribution matching between common embeddings and category word-embeddings. Finally, adversarial inter-media metric constraint is proposed with an inter-media loss and a quadruplet loss, which further model the inter-media correlation information and improve semantic ranking ability. The experiments on four widely used cross-media datasets demonstrate the effectiveness of our DADN approach. [ABSTRACT FROM AUTHOR]

Cross-modal retrieval has drawn wide interest for retrieval across different modalities (such as text, image, video, audio, and 3-D model). However, existing methods based on a deep neural network often face the challenge of insufficient cross-modal training data, which limits the training effectiveness and easily leads to overfitting. Transfer learning is usually adopted for relieving the problem of insufficient training data, but it mainly focuses on knowledge transfer only from large-scale datasets as a single-modal source domain (such as ImageNet) to a single-modal target domain. In fact, such large-scale single-modal datasets also contain rich modal-independent semantic knowledge that can be shared across different modalities. Besides, large-scale cross-modal datasets are very labor-consuming to collect and label, so it is significant to fully exploit the knowledge in single-modal datasets for boosting cross-modal retrieval. To achieve the above goal, this paper proposes a modal-adversarial hybrid transfer network (MHTN), which aims to realize knowledge transfer from a single-modal source domain to a cross-modal target domain and learn cross-modal common representation. It is an end-to-end architecture with two subnetworks. First, a modal-sharing knowledge transfer subnetwork is proposed to jointly transfer knowledge from a single modality in the source domain to all modalities in the target domain with a star network structure, which distills modal-independent supplementary knowledge for promoting cross-modal common representation learning. Second, a modal-adversarial semantic learning subnetwork is proposed to construct an adversarial training mechanism between the common representation generator and modality discriminator, making the common representation discriminative for semantics but indiscriminative for modalities to enhance cross-modal semantic consistency during the transfer process. Comprehensive experiments on four widely used datasets show the effectiveness of MHTN. [ABSTRACT FROM AUTHOR]

Cross-modal hashing maps heterogeneous multimedia data into a common Hamming space to realize fast and flexible cross-modal retrieval. Supervised cross-modal hashing methods have achieved considerable progress by incorporating semantic side information. However, they heavily rely on large-scale labeled cross-modal training data which are hard to obtain, since multiple modalities are involved. They also ignore the rich information contained in the large amount of unlabeled data across different modalities, which can help to model the correlations between different modalities. To address these problems, in this paper, we propose a novel semi-supervised cross-modal hashing approach by generative adversarial network (SCH-GAN). The main contributions can be summarized as follows: 1) we propose a novel generative adversarial network for cross-modal hashing, in which the generative model tries to select margin examples of one modality from unlabeled data when given a query of another modality (e.g., giving a text query to retrieve images and vice versa). The discriminative model tries to distinguish the selected examples and true positive examples of the query. These two models play a minimax game so that the generative model can promote the hashing performance of the discriminative model and 2) we propose a reinforcement learning-based algorithm to drive the training of proposed SCH-GAN. The generative model takes the correlation score predicted by discriminative model as a reward, and tries to select the examples close to the margin to promote a discriminative model. Extensive experiments verify the effectiveness of our proposed approach, compared with nine state-of-the-art methods on three widely used datasets. [ABSTRACT FROM AUTHOR]

Cross-modal hashing aims to map heterogeneous cross-modal data into a common Hamming space, which can realize fast and flexible retrieval across different modalities. Unsupervised cross-modal hashing is more flexible and applicable than supervised methods, since no intensive labeling work is involved. However, existing unsupervised methods learn the hashing functions by preserving inter- and intra-correlations while ignoring the underlying manifold structure across different modalities, which is extremely helpful in capturing the meaningful nearest neighbors of different modalities for cross-modal retrieval. Furthermore, existing works mainly focus on pairwise relation modeling while ignoring the correlations within multiple modalities. To address the above-mentioned problems, in this paper, we propose a multi-pathway generative adversarial hashing approach for unsupervised cross-modal retrieval, which makes full use of a generative adversarial network's ability for unsupervised representation learning to exploit the underlying manifold structure of cross-modal data. The main contributions can be summarized as follows: First, we propose a multi-pathway generative adversarial network to model cross-modal hashing in an unsupervised fashion. In the proposed network, given the data of one modality, the generative model tries to fit the distribution over the manifold structure and selects informative data of other modalities to challenge the discriminative model. The discriminative model learns to distinguish the generated data and the true positive data sampled from the correlation graph to achieve better retrieval accuracy. These two models are trained in an adversarial way to improve each other and promote hashing function learning. Second, we propose a correlation graph-based approach to capture the underlying manifold structure across different modalities so that data of different modalities but within the same manifold can have a smaller Hamming distance to promote retrieval accuracy. Extensive experiments compared with state-of-the-art methods on three widely used datasets verify the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

As multimedia data have been the main form of big data, cross-media retrieval becomes a research hotspot. It provides a flexible retrieval paradigm across different media types, such as using an image query to retrieve the relevant text, video, and audio. An effective model to establish cross-media correlation is indispensable for retrieval. Existing methods usually rely on labeled data for model training, but it is extremely labor consuming to collect and label cross-media data. Under this situation, it is a key issue toward the real application to transfer knowledge from existing data to new data, for reducing the human labor. However, little attention has been paid to knowledge transfer between two cross-media domains. Therefore, this paper proposes the approach of two-level progressive cross-media knowledge transfer (TPCKT), which transfers knowledge from large-scale cross-media data, to boost the retrieval accuracy on cross-media data of another domain. Its contributions are: First, two-level adversarial transfer architecture is proposed with domain discriminators in media-specific level and media-shared level, which have partially shared parameters to preserve cross-media consistency of transfer. The domain discrepancy between cross-media domains is fully reduced for boosting the retrieval accuracy. Second, progressive semantic transfer mechanism is proposed to iteratively select semantically related categories in two cross-media domains for transfer. This drives the transfer process with ascending difficulties, for addressing the difficulty from different label spaces, and ensuring the robustness of transfer. For the experiment, the large-scale cross-media dataset PKU XMediaNet serves as the source domain, and three widely used small-scale datasets are adopted as the target domains to perform retrieval. Experimental results show the promising improvement gained by the proposed TPCKT. [ABSTRACT FROM AUTHOR]

Multimedia data with various modalities, such as image and text, are huge in quantity but have inconsistent distribution and representation. Many works have been done to break the boundary between image and text to measure their correlation. However, they focus on either the transformation to common subspace or the unidirectional generation from one to another individually, which cannot fully explore their interactions. It is noted that the bidirectional generation between image and text not only can provide complementary hints and mutually boost to learn cross-modal correlation but also cross-modal correlation learning can feed back to give comprehensive clues for promoting the cross-modal generation process. Therefore, we have the motivation that information transmission between image and text should be treated as a circular process, which aims to fully understand their latent correlation, and further realize cross-modal generation to produce both realistic images and text descriptions in a unified framework. In this paper, we propose the cross-modal circular correlation learning approach to perform both cross-modal correlation learning and generation simultaneously through an efficient circular learning training procedure. First, we propose the cross-modal circular learning model to perform an image-to-text caption and text-to-image synthesis circularly and learn common representation as a round-trip bridge, which can realize efficient interactions to fully exploit latent cross-modal correlations. Second, a unified bidirectional framework is proposed to conduct cross-modal mutual generation and is trained in an efficient circular process to enhance the generative ability of common representation, which can feed back circularly to further promote cross-modal correlation learning. In summary, we simultaneously perform cross-modal retrieval, image-to-text caption, and text-to-image synthesis in a unified framework with the circular learning process, which has high scalability and generality to realize universal cognition on the cross-modal data. We conduct extensive experiments to not only evaluate the correlation performance by cross-modal retrieval but also to show the generation effectiveness of both image caption and synthesis on the MS-COCO dataset. [ABSTRACT FROM AUTHOR]

Cross-modal retrieval has become a highlighted research topic for retrieval across multimedia data such as image and text. A two-stage learning framework is widely adopted by most existing methods based on deep neural network (DNN): The first learning stage is to generate separate representation for each modality and the second learning stage is to get the cross-modal common representation. However the existing methods have three limitations: 1) In the first learning stage they only model intramodality correlation but ignore intermodality correlation with rich complementary context. 2) In the second learning stage they only adopt shallow networks with single-loss regularization but ignore the intrinsic relevance of intramodality and intermodality correlation. 3) Only original instances are considered while the complementary fine-grained clues provided by their patches are ignored. For addressing the above problems this paper proposes a cross-modal correlation learning (CCL) approach with multigrained fusion by hierarchical network and the contributions are as follows: 1) In the first learning stage CCL exploits multilevel association with joint optimization to preserve the complementary context from intramodality and intermodality correlation simultaneously. 2) In the second learning stage a multitask learning strategy is designed to adaptively balance the intramodality semantic category constraints and intermodality pairwise similarity constraints. 3) CCL adopts multigrained modeling which fuses the coarse-grained instances and fine-grained patches to make cross-modal correlation more precise. Comparing with 13 state-of-the-art methods on 6 widely-used cross-modal datasets the experimental results show our CCL approach achieves the best performance. [ABSTRACT FROM PUBLISHER]

With the rapid growth of multimedia data such as text, image, video, audio, and 3-D model, cross-media retrieval has become increasingly important, because users can retrieve the results with various types of media by submitting a query of any media type. Comparing with single-media retrieval such as image retrieval and text retrieval, cross-media retrieval is better because it provides the retrieval results with all kinds of media at the same time. In this paper, we focus on how to learn cross-media features for different media types, which is a key challenge for cross-media retrieval. Existing methods either model different media types separately or only exploit the labeled multimedia data. Actually, the data from different media types with the same semantic category are complementary to each other, and jointly modeling them is able to improve the accuracy of cross-media retrieval. In addition, although the labeled data are accurate, they require a lot of human labor and thus are very scarce. To address the above problems, we propose a semi-supervised cross-media feature learning algorithm with unified patch graph regularization (S ^2 UPG). Our motivation and contribution mainly lie in the following three aspects. First, existing methods only model different media types in different graphs, while we employ one joint graph to simultaneously model all the media types. The joint graph is able to fully exploit the semantic correlations among various media types, which are complementary to provide the rich hint for cross-media correlation. Second, existing methods only consider the original media instances (such as images, videos, texts, audios, and 3-D models) but ignore their patches, while we make full use of both the media instances and their patches in one graph. Cross-media patches could emphasize the important parts and make cross-media correlations more precise. Third, traditional semi-supervised learning methods only exploit single-media unlabeled instances, while our approach fully exploits cross-media unlabeled instances and their patches, which can increase the diversity of training data and boost the accuracy of cross-media retrieval. Comparing with the current state-of-the-art methods on three datasets, including the challenging XMedia dataset with five media types, the comprehensive experimental results show that our proposed approach performs better. [ABSTRACT FROM AUTHOR]

Cross-media retrieval has become a key problem in both research and application, in which users can search results across all of the media types (text, image, audio, video, and 3-D) by submitting a query of any media type. How to measure the content similarity among different media is the key challenge. Existing cross-media retrieval methods usually focus on modeling the pairwise correlation or semantic information separately. In fact, these two kinds of information are complementary to each other and optimizing them simultaneously can further improve the accuracy. In this paper, we propose a novel feature learning algorithm for cross-media data, called joint representation learning (JRL), which is able to explore jointly the correlation and semantic information in a unified optimization framework. JRL integrates the sparse and semisupervised regularization for different media types into one unified optimization problem, while existing feature learning methods generally focus on a single media type. On one hand, JRL learns sparse projection matrix for different media simultaneously, so different media can align with each other, which is robust to the noise. On the other hand, both the labeled data and unlabeled data of different media types are explored. Unlabeled examples of different media types increase the diversity of training data and boost the performance of joint representation learning. Furthermore, JRL can not only reduce the dimension of the original features, but also incorporate the cross-media correlation into the final representation, which further improves the performance of both cross-media retrieval and single-media retrieval. Experiments on two datasets with up to five media types show the effectiveness of our proposed approach, as compared with the state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

This paper presents contextual kernel and spectral methods for learning the semantics of images that allow us to automatically annotate an image with keywords. First, to exploit the context of visual words within images for automatic image annotation, we define a novel spatial string kernel to quantify the similarity between images. Specifically, we represent each image as a 2-D sequence of visual words and measure the similarity between two 2-D sequences using the shared occurrences of s-length 1-D subsequences by decomposing each 2-D sequence into two orthogonal 1-D sequences. Based on our proposed spatial string kernel, we further formulate automatic image annotation as a contextual keyword propagation problem, which can be solved very efficiently by linear programming. Unlike the traditional relevance models that treat each keyword independently, the proposed contextual kernel method for keyword propagation takes into account the semantic context of annotation keywords and propagates multiple keywords simultaneously. Significantly, this type of semantic context can also be incorporated into spectral embedding for refining the annotations of images predicted by keyword propagation. Experiments on three standard image datasets demonstrate that our contextual kernel and spectral methods can achieve significantly better results than the state of the art. [ABSTRACT FROM AUTHOR]