The insufficiency of labeled training samples is a major obstacle in automatic semantic analysis of large scale image/video database. Semi-supervised learning, which attempts to learn from both labeled and unlabeled data, is a promising approach to tackle this problem. As a major family of semi-supervised learning, graph-based methods have attracted more and more recent research. In this chapter, a brief introduction is given on popular semi-supervised learning methods, especially the graph-based methods, as well as their applications in the area of image annotation, video annotation, and image retrieval. It is well known that the pair-wise similarity is an essential factor in graph propagation based semisupervised learning methods. A novel graph-based semi-supervised learning method, named Structure- Sensitive Anisotropic Manifold Ranking (SSAniMR), is derived from a PDE based anisotropic diffusion framework. Instead of using Euclidean distance only, SSAniMR further takes local structural difference into account to more accurately measure pair-wise similarity. Finally some future directions of using semi-supervised learning to analyze the multimedia content are discussed.
TopIntroduction
Digital image and video collections are growing rapidly in recent years, accompanied with the decreased cost of storage devices, high transmission rates and improved compression techniques. The demand for solutions to manage image/video database is increasing tremendously. It is a common theme to develop automatic analysis techniques for deriving metadata to describe the visual content at semantic level (Smith & Schirling, 2006). Thus, automatically annotating image and video at the semantic concept level has emerged as an important topic in the multimedia research community as it is an elementary step for obtaining these metadata. The concepts of interest include a wide range of categories such as scenes (e.g., urban, sky, mountain.), objects (e.g., airplane, car, face, etc.), events (e.g., explosion-fire, people-marching, etc.) and certain named entities (e.g. person, place, etc.) (Naphade, et al., 2006; Snoek, et al., 2006). As manually annotating large image or video archive is labor-intensive and time-consuming, efficient automatic annotation methods are highly desired. To this end, generally statistical models are built from manually pre-labeled samples, and then the labels are automatically assigned to the unlabeled samples using these models. However, this process has a major obstacle: frequently the labeled data is limited so that the distribution of the labeled data typically cannot well represent the distribution of the entire data set (including labeled and unlabeled), which usually leads to inaccurate annotation results.
Semi-supervised learning, which attempts to learn from both labeled and unlabeled data, is a promising approach to deal with the above issue. As a major family of semi-supervised learning, graph based method is becoming one of the most active research area in semi-supervised learning community in recent years. Many works on this topic are reported in the literature of machine learning community (Carreira-Perpinan & Zemel, 2005; Seeger, 2001) and some of them have been applied to multimedia semantic analysis.
In Section II, we briefly introduce several semi-supervised learning techniques, including self-training, co-training and transductive SVM, and then we focus on graph-based methods (Zhu, 2005a). The graph-based methods define a graph with each vertex corresponding to each sample in the dataset, and the weighted edges reflect the similarity between neighboring samples. The objective of most graph-based methods is estimating a prediction function on the graph. Zhu, Ghahramani, & Lafferty (2003) have made two assumptions for this function: (1) the predicted scores on the unlabeled data should be close to the given labels of the unlabeled data; (2) the function should be smooth on the whole graph. These two assumptions directly lead to the Gaussian random field method, in which the graph combinatorial Laplacian is used as a regularizer. Besides these two assumptions, Zhou, Bousquet, Lal, Weston, & Scholkopf (2003) further made the structural assumption: points on the same structure (typically referred to as a cluster or a manifold) are likely to have the same label. This leads to the local and global consistency method, which uses the normalized Laplacian as the regularizer. Some more sophisticated regularization frameworks are also briefly introduced in this section, e.g., local learning regularization (Wu & Scholkopf, 2007), Tikhonov regularization (Belkin, Matveeva, & Niyogi, 2004) and manifold regularization (Belkin, Niyogi, & Sindhwani, 2006). In Section III, we present some applications of semi-supervised learning in video/image semantic analysis.