In the above titled paper (ibid., vol. 13, no. 4, pp. 639-652, Aug. 2011), the first author's name appears incorrectly in the byline as "Xinmie Tian" instead of "Xinmei Tian." The name appears correctly in the biography section.

Visual reranking has been proven effective to refine text-based video and image search results. It utilizes visual information to recover “true” ranking list from the noisy one generated by text-based search, by incorporating both textual and visual information. In this paper, we model the textual and visual information from the probabilistic perspective and formulate visual reranking as an optimization problem in the Bayesian framework, termed Bayesian visual reranking. In this method, the textual information is modeled as a likelihood, to reflect the disagreement between reranked results and text-based search results which is called ranking distance. The visual information is modeled as a conditional prior, to indicate the ranking score consistency among visually similar samples which is called visual consistency. Bayesian visual reranking derives the best reranking results by maximizing visual consistency while minimizing ranking distance. To model the ranking distance more precisely, we propose a novel pair-wise method which measure the ranking distance based on the disagreement in terms of pair-wise orders. For visual consistency, we study three different regularizers to mine the best way for its modeling. We conduct extensive experiments on both video and image search datasets. Experimental results demonstrate the effectiveness of our proposed Bayesian visual reranking.

Most existing approaches to visual search reranking predominantly focus on mining information only from the initial ranking order on the basis of pseudo-relevance feedback. However, the initial ranking order cannot always provide enough cues for reranking by itself due to an unsatisfying visual search performance. This letter presents a novel approach to visual search reranking by selectingtypicalexamples to build the reranking model. Observing that typical examples are mostly clearly visible, fill the majority of the visual documents or appear in one of several common poses, by using these examples informed classifiers would generally be more robust to noisy testing cases that may include occlusions, illumination changes or other factors. We first define thetypicalityon the basis of data distribution, and then theoretically formalize the example selection as an optimization problem on the basis of the example typicality and propose a close-form solution. Based on the selected examples, we build the reranking model by using a support vector machine. Empirically, we conduct extensive experiments on a real-world image set and a benchmark video set, and shows significant and consistent improvements over the state-of-the-art works.

Image search reranking methods usually fail to capture the user's intention when the query term is ambiguous. Therefore, reranking with user interactions, or active reranking, is highly demanded to effectively improve the search performance. The essential problem in active reranking is how to target the user's intention. To complete this goal, this paper presents a structural information based sample selection strategy to reduce the user's labeling efforts. Furthermore, to localize the user's intention in the visual feature space, a novel local-global discriminative dimension reduction algorithm is proposed. In this algorithm, a submanifold is learned by transferring the local geometry and the discriminative information from the labelled images to the whole (global) image database. Experiments on both synthetic datasets and a real Web image search dataset demonstrate the effectiveness of the proposed active reranking scheme, including both the structural information based active sample selection strategy and the local-global discriminative dimension reduction algorithm.

There are about 8% of men and 0.8% of women suffering from colorblindness. These viewers have difficulty in discriminating several colors, and thus many colorful images and videos that have high qualities for normal viewers may not be readily perceptible for them. In this paper, we propose an efficient re-coloring approach which can modify the colors of images and videos to enhance their perceptibility for colorblind users. Given an image, the re-coloring is accomplished by two color rotation steps in CIELAB color space. We first perform a local color rotation such that information of b*axis can be enhanced, and then adopt a global color rotation to refine the results. We will show that this method is simple yet effective, and it is able to outperform the traditional re-coloring algorithms in both performance and computational efficiency. We apply the method to process video frames and adopt several strategies to further reduce computational cost to realize real-time video re-coloring. We also explore the structure information of video data to avoid the color inconsistency problem. Specifically, we enforce the color mapping function to be identical in each shot and vary smoothly in adjacent shots. We conduct experiments on real-world images and videos with diverse content, and empirical results demonstrate the effectiveness of the proposed methods.

Most of the existing learning-based methods for video search take query examples as ¿positive¿ and build a model for each query. These methods, referred to as query-dependent, only achieve limited success as users are mostly reluctant to provide enough query examples. To address this problem, we propose a novel query-independent learning approach based on multigraph to video search, which learns the relevance information existing in the query-shot pairs. The proposed approach, named MG-QIL, is more general and suitable for a real-world video search system as the learned relevance is independent of any queries. Specifically, MG-QIL constructs multiple graphs, including a main-graph covering all the pairs and a set of subgraphs covering the pairs within the same query. The pairs in the main-graph are connected in terms ofrelational similarity, while the pairs in the subgraphs for the same query are connected in terms ofattributional similarity. The relevance labels are then propagated in the multiple graphs until convergence. We conducted extensive experiments on automatic search tasks over the TRECVID 2005-2007 benchmark and the results show a superior performance to state-of-the-art approaches to video search. Furthermore, when applied to video search reranking, MG-QIL can also achieve significant and consistent improvement over a text search baseline.

Recently, graph-based semisupervised learning methods have been widely applied in multimedia research area. However, for the application of video semantic annotation in multilabel setting, these methods neglect an important characteristic of video data: The semantic concepts appear correlatively and interact naturally with each other rather than exist in isolation. In this paper, we adapt this semantic correlation into graph-based semisupervised learning and propose a novel method named correlative linear neighborhood propagation to improve annotation performance. Experiments conducted on the Text REtrieval Conference VIDeo retrieval evaluation data set have demonstrated its effectiveness and efficiency.

Recently, there has been growing interest in mining co-location visual patterns from a collection of images. To find a proper usage of visual patterns in near-duplicate image retrieval systems, we study a TF-IDF weighting function for visual patterns. We show usage of TF and IDF respectively in this weighting function. Experiments demonstrate that 1) visual patterns and words should be weighted separately; 2) visual patterns consist of more frequent visual words would be more important; 3) visual patterns should be given lower weight values than visual words in near-duplicate image retrieval tasks.

Conventional approaches to video search reranking only care whether search results are relevant or irrelevant to the given query, while the ranking order of these results indicating the level of relevance or typicality are usually neglected. This paper presents a novel learning-based approach to video search reranking by investigating the ranking order information. The proposed approach, called pseudo preference feedback (PPF), automatically discovers an optimal set of pseudo preference pairs from the initial ranked list and learns a reranking model by ranking support vector machines (ranking SVM) based on the selected pairs. We have proved that PPF can be used for any reranking purpose such as video search and concept detection. We conducted comprehensive experiments for both automatic search and concept detection tasks over TRECVID 2006-2007 benchmark, and showed that PPF could gain significant improvements over the baselines.

Most of existing learning-based methods for query-by-example take the query examples as ldquopositiverdquo and build a model for each query. These methods, referred to as query-dependent, only achieved limited success as they can hardly be applied to real-world applications, in which an arbitrary query is usually given. To address this problem, we propose to learn a query-independent model by exploiting the relevance information which exists in the pair of query-document. The proposed approach takes a query-document pair as a sample and extracts a set of query-independent textual and visual features from each pair. It is general and suitable for a real-world video search system since the learned relevance relation is independent on any query. We conducted extensive experiments over TRECVID 2005-2007 corpus and shown superior performance (+37% in Mean Average Precision) to the query-dependent learning approaches.

One crucial problem in transductive video annotation is how to estimate the label from the neighboring samples. Existing methods such as graph-based Gaussian random filed only considered the pair-wise similarity and then propagated the labels based on it. In this paper, we propose a new method from the perspective of local learning, which formulate the prediction of labels from the neighbors into a learning problem. Our contributions lie in two-fold: (1) we propose a new transductive video annotation method based on local kernel classifier; (2) local learnable is proposed to measure whether a sample can be learned from the neighbors well and we employ this measure into the optimization objective. Experiments on TRECVID 2005 dataset prove that the proposed method is effective and the local learning perspective is promising for video annotation.

Content-based video search reranking can be regarded as a process that uses visual content to recover the "true" ranking list from the noisy one generated based on textual information. This paper explicitly formulates this problem in the Bayesian framework, i.e., maximizing the ranking score consistency among visually similar video shots while minimizing the ranking distance, which represents the disagreement between the objective ranking list and the initial text-based. Different from existing point-wise ranking distance measures, which compute the distance in terms of the individual scores, two new methods are proposed in this paper to measure the ranking distance based on the disagreement in terms of pair-wise orders. Specifically, hinge distance penalizes the pairs with reversed order according to the degree of the reverse, while preference strength distance further considers the preference degree. By incorporating the proposed distances into the optimization objective, two reranking methods are developed which are solved using quadratic programming and matrix computation respectively. Evaluation on TRECVID video search benchmark shows that the performance improvement up to 21% on TRECVID 2006 and 61.11% on TRECVID 2007 are achieved relative to text search baseline.

This paper presents a novel learning-based method, called “multi-layer multi-instance (MLMI) learning,” for video concept detection. Most of existing methods have treated video as a flat data sequence and have not investigated theintrinsic hierarchy structureof the video content deeply. However, video is essentially a kind of media with ML structure. For example, a video can be represented by a hierarchical structure including, from large to small,shot,frame, andregion, where each pair of contiguous layers fits the typical MI setting. We call such a ML structure and the MI relations embedded in the structure as the MLMI setting. In this paper, we systematically study both ML structure and MI relations embedded in video content by formulating video concept detection as a MLMI learning problem. Specifically, we first construct a MLMI kernel to simultaneously model such ML structure and MI relations. To deal with theambiguity propagationproblem which is introduced by weak labeling and ML structure, we then propose a regularization framework which takeshyper-bagprediction error, sublayer prediction error, inter-layer inconsistency measure, and classifier complexity into consideration. We have applied the proposed MLMI learning method to concept detection task over TRECVid 2005 development corpus, and report better performance to vector-based and the state-of-the-art MI learning methods.

The insufficiency of labeled training data for representing the distribution of the entire dataset is a major obstacle in automatic semantic annotation of large-scale video database. Semi-supervised learning algorithms, which attempt to learn from both labeled and unlabeled data, are promising to solve this problem. In this paper, a novel graph-based semi-supervised learning method namedkernellinearneighborhoodpropagation(KLNP) is proposed and applied to video annotation. This approach combines theconsistencyassumption, which is the basic assumption in semi-supervised learning, and thelocallinearembedding(LLE) method in a nonlinear kernel-mapped space. KLNP improves a recently proposed methodlinearneighborhoodpropagation(LNP) by tackling the limitation of its local linear assumption on the distribution of semantics. Experiments conducted on the TRECVID data set demonstrate that this approach outperforms other popular graph-based semi-supervised learning methods for video semantic annotation.

As a major family of semi-supervised learning, graph based semi-supervised learning methods have attracted lots of interests in the machine learning community as well as many application areas recently. However, for the application of video semantic annotation, these methods only consider the relations among samples in the feature space and neglect an intrinsic property of video data: the temporally adjacent video segments (e.g., shots) usually have similar semantic concept. In this paper, we adapt this temporal consistency property of video data into graph based semi-supervised learning and propose a novel method named temporally consistent Gaussian random field (TCGRF) to improve the annotation results. Experiments conducted on the TREC VID data set have demonstrated its effectiveness.

Automatic image annotation is a promising solution to enable more effective image retrieval by keywords. Traditionally, statistical models for image auto-annotation predicate each annotated keyword independently without considering the correlation of words. In this paper, we propose a novel probability model, in which the correspondence between keywords and image visual tokens/regions and the word-to-word correlation are well combined. We employ the conditional probability to express two kinds of correlation uniformly and obtain the correspondence between keyword and visual feature with the cross-media relevance model (CMRM). Experiments conducted on standard Corel dataset demonstrate the effectiveness of the proposed method for image automatic annotation.

This paper proposes a novel energy minimization based approach to video scene segmentation. In video content analysis, scene is defined as a set of adjacent shots related to a particular setting or a continuous action in one place. This indicates that not only the global distribution of time and content, but also the local temporal continuity should be taken into account for scene segmentation. Motivated from this fact, we formulate the segmentation procedure as a unified energy minimization framework, in which the global and local constraint is represented by content and context energy, respectively. This energy minimization problem is optimized by two steps in an iterative fashion: first find an initial estimation of scene label for content energy by a generative model; and then iterated conditional modes (ICM) is used for context energy to find the global optimization. Furthermore, a boundary voting procedure is devised to decide the optimal scene boundaries. We apply EMS on an extensive set of home videos and feature movies, and report superior performance compared with several existing key approaches to scene segmentation.

This paper proposes a novel multi-focus image fusion algorithm. Different from traditional decision map based methods, our algorithm is based on salience preserving gradient, which can better emphasize the structure details of sources while preserving the color consistency. We firstly measure the salience map of the gradient from each source, and then use their saliency to modulate their contributions in computing the global statistics. Gradients with high saliency are properly highlighted in the target gradient, and thereby salient features in the sources are well preserved. Furthermore we extend it to color domain by proposing an importance-weight based trigonometric average method to merge the color components. Extensive experiments on several datasets have demonstrated the effectiveness of our approach.

In this paper, we address the issue of typicality ranking for video annotation and propose to use a novel criterion, average typicality precision (ATP), to replace the frequently used one, average precision (AP), for evaluating the performance of video annotation algorithms. General annotation methods just care the number of true-positive samples at the top of the ranked list; they actually do not care the order of these samples. We argue that it is more reasonable to rank "typical" true-positive samples higher than non-typical ones, which can be evaluated by our proposed ATP. However, generally the labels of the training data only differentiate true from false; that is to say, typical or non-typical training samples have the same contribution to the learning process. Therefore, the labels of the unlabeled data learned from these training data can not well measure the typicality. In this paper, we relax the labels of the training data to real-valued typicality scores by a pre-processing stage, which is accomplished by three approaches, including density estimation, user feedback and active learning. Then the typicality scores of the training data are propagated to unlabeled data using manifold-ranking. Experiments conducted on the TRECVID data set demonstrate that this typicality ranking scheme is more consistent with human perception than normal accuracy based ranking schemes.

Graph-based semi-supervised learning (SSL) has attracted lots of interests in machine learning community as well as many application areas including video annotation recently. However, one of the two basic assumptions, structure assumption, which is an essential point of graph-based SSL, is not embedded into the pairwise similarity measure. Accordingly, we propose a novel graph-based SSL method for video annotation, named anisotropic manifold ranking (AniMR), based on a structure-related similarity measure. This method takes the influence of the density difference between samples into account to improve the pairwise similarity. Furthermore, we will show that AniMR can also be deduced from partial differential equation (PDE) based anisotropic diffusion. It demonstrates that the label propagation in AniMR is anisotropic, which is intrinsically different from the isotropic label propagation process in general graph-based SSL methods. Experiments conducted on the TRECVID data set show this approach outperforms ordinary graph-based SSL methods and is effective for video semantic annotation.

In image retrieval, the concepts are usually in region-level but annotated in image-level, which leads to a major difficulty in learning the target concepts. In this paper, we formulate region-based image retrieval as a multiple-instance learning (MIL) problem, and propose an efficient and effective algorithm, named MI-AdaBoost, to solve it. The algorithm firstly maps each bag into a new bag feature space using a certain set of instance prototypes, and then adopts AdaBoost to select the bag features and build classifiers simultaneously. Experiments on both COREL and MUSK datasets show the proposed scheme is much more efficient than some typical existing MIL algorithms while has comparable results.

In video concept detection, most existing methods have not well studied the intrinsic hierarchical structure of video content. However, unlike flat attribute-value data used in many existing methods, video is essentially a structured media with multi-layer representation. For example, a video can be represented by a hierarchical structure including, from large to small, shot, key-frame, and region. Moreover, it fits the typical Multi-Instance (MI) setting in which the "bag-instance" correspondence is embedded among contiguous layers. We call such multi-layer structure and the "bag-instance" relation embedded in the structure as Multi-Layer Multi-Instance (MLMI) setting in this paper. We formulate video concept detection as an MLMI learning problem in which a rooted tree with MLMI nature embedded is devised to represent a video segment. Furthermore, by fusing the information from different layers, we construct a novel MLMI kernel to measure the similarities between the instances in the same and different layers. In contrast to traditional MI learning, both the Multi-Layer structure and Multi-Instance relations are leveraged simultaneously in the proposed kernel. We applied MLMI kernel to concept detection task on TRECVID 2005 corpus and reported superior performance (+25% in Mean Average Precision) to standard Support Vector Machine based approaches.

Most of the existing methods for natural scene categorization only consider whether a sample is relevant or irrelevant to a particular concept. However, for the samples relevant to a certain concept, their typicalities or relevancy scores to the concept generally are different. Typicality measure should be taken into account to make the categorization results more consistent with human's perception. In this paper, we propose a novel typicality ranking scheme for categorizing natural scenes through a two-stage semi-supervised multiple-instance learning method. The first stage infers the typicalities of the underlying positive instances (i.e., regions in images) in the training dataset and the second one predicts the typicality of each bag (i.e., image) in a semi-supervised manner. Compared to existing typicality ranking approaches, the main advantages of the proposed method lie in twofold. First, it only needs image-level labels instead of region-level ones in the training stage. Second, it is fully automated and no human feedback is required. Experiments conducted on a COREL image dataset demonstrate the effectiveness of the proposed approach.

Pairwise similarity of samples is an essential factor in graph propagation based semi-supervised learning methods. Usually it is estimated based on Euclidean distance. However, the structural assumption, which is a basic assumption in these methods, has not been taken into consideration in the normal pairwise similarity measure. In this paper, we propose a novel graph-based learning approach, named Structure-Sensitive Manifold Ranking (SSMR),based on a structure-sensitive similarity measure. Instead of using distance only, SSMR takes local distribution differences into account to more accurately measure pairwise similarity. Furthermore, we show that SSMR can also be deduced from a partial differential equation based anisotropic diffusion. Experiments conducted on the TRECVID dataset show that this approach significantly outperforms existing graph-based semi-supervised learning methods for video semantic concept detection.

This paper presents an automatic video genre categorization scheme based on the hierarchical ontology on video genres. Ten computable spatio-temporal features are extracted to distinguish the different genres using a hierarchical support vector machines (SVM) classifier built by cross-validation, which consists of a series of SVM classifiers united in a binary-tree form. As the order and genre partition strategy of the SVM classifier series affect the over performance of the united classifier, two optimal SVM binary trees, local and global, are constructed aiming at finding the best categorization orders, i.e., the best tree structure, of the genre ontology. Experimental results show that the proposed scheme outperforms C4.5 decision tree, typical 1-vs-1 SVM scheme, as well as the hierarchical SVM built by K-means.

This paper exploits the criteria to optimize the training set construction for video annotation. Most existing learning-based semantic annotation approaches require a large training set to achieve good generalization capacity, in which a considerable amount of labor-intensively manual labeling is desirable. However, it is observed that the generalization capacity of a classifier highly depends on the geometrical distribution rather than the size of the training data. We argue that a training set which includes most temporal and spatial distribution of the whole data will achieve a satisfying performance even in the case of limited size of training set. In order to capture the geometrical distribution characteristics of a given video collection, we propose the following four metrics for constructing an optimal training set, including Salience Time Dispersiveness Spatial Dispersiveness and Diversity. Moreover, based on these metrics, we propose a set of optimization rules to capture the most distribution information of the whole data for a training set with a given size. Experimental results demonstrate that these rules are effective for training set construction for video annotation, and significantly outperform random training set selection as well.

In this paper we discuss a typical case in video concept detection: to learn target concept using only a small number of positive samples. A novel manifold-ranking based scheme is proposed, which consists of three major components: feature pool construction, pre-filtering, and manifold-ranking. First, as there are large variations in the effective features for different concepts, a large feature pool is constructed, from which the most effective features can be selected automatically or semi-automatically. Second, to tackle the issue of large computation cost for successive manifold-ranking process when large video database is incorporated, we employ a pre-filtering process to filter out the majority of irrelevant samples while retaining the most relevant ones. And last, the manifold-ranking algorithm is used to explore the relationship among all of the rest samples based on the selected features. This scheme is extensible and flexible in terms of adding new features into the feature pool, introducing human interactions on selecting features, and defining new concepts.