基于局部流形重构的半监督多视图图像分类

为了在半监督情境下利用多视图特征中的信息提升分类性能,通过最小化输入特征向量的局部重构误差为以输入特征向量为顶点构建的图学习合适的边权重,将其用于半监督学习。通过将最小化输入特征向量的局部重构误差捕获到的输入数据的流形结构应用于半监督学习,有利于提升半监督学习中标签预测的准确性。对于训练样本图像的多视图特征的使用问题,借助于改进的典型相关分析技术学习更具鉴别性的多视图特征,将其有效融合并用于图像分类任务。实验结果表明,该方法能够在半监督情境下充分地挖掘训练样本的多视图特征表示的鉴别信息,有效地完成鉴别任务。     

Joint auto-weighted graph fusion and scalable semi-supervised learning

Graph carries out a key role in graph-based semi-supervised label propagation, as it clarifies the structure of the data manifold. The performance of label propagation methods depends on the adopted graph and can be enhanced by merging different graphs that are obtained from multiple sources of information. While there exist algorithms that perform graph fusion they have several weaknesses. Most of these algorithms define graph fusion and label propagation as two separate tasks. Moreover, when the number of data expands, these strategies are not well-suited due to the use of transductive learning in the label propagation phase which makes the label prediction for unseen samples difficult. Furthermore, very few algorithms extract the information contained in the label space. Additionally, most of the graph fusion techniques adopt equal or static weights for different views, which is not the best choice as distinctive features (hence different graphs) contain various information. To overcome these shortcomings, we propose an Auto-weighted Multi-view Semi-Supervised Learning method (AMSSL), which is based on an inductive learning algorithm (i.e., Flexible Manifold Embedding) and profited a projection matrix for predicting the labels of out-of-sample data. The proposed AMSSL method represents a unified framework that dynamically fuses various information obtained from different features and also from the label space and adaptively designates appropriate weights according to the usefulness of each view. Our experimental results on seven small and large image datasets demonstrate the superiority of the proposed method compared to the use of one single feature and other state-of-the-art graph fusion methods.     

Global Feature Tracking and Similarity Estimation in Time‐Dependent Scalar Fields

We present an algorithm for tracking regions in time‐dependent scalar fields that uses global knowledge from all time steps for determining the tracks. The regions are defined using merge trees, thereby representing a hierarchical segmentation of the data in each time step. The similarity of regions of two consecutive time steps is measured using their volumetric overlap and a histogram difference. The main ingredient of our method is a directed acyclic graph that records all relevant similarity information as follows: the regions of all time steps are the nodes of the graph, the edges represent possible short feature tracks between consecutive time steps, and the edge weights are given by the similarity of the connected regions. We compute a feature track as the global solution of a shortest path problem in the graph. We use these results to steer the – to the best of our knowledge – first algorithm for spatio‐temporal feature similarity estimation. Our algorithm works for 2D and 3D time‐dependent scalar fields. We compare our results to previous work, showcase its robustness to noise, and exemplify its utility using several real‐world data sets.     

Bidirectional Label Propagation over Graphs

Graph-Based label propagation algorithms are popular in the state-of-the-art semi-supervised learning research. The key idea underlying this algorithmic family is to enforce labeling consistency between any two examples with a positive similarity. However, negative similarities or dissimilarities are equivalently valuable in practice. To this end, we simultaneously leverage similarities and dissimilarities in our proposed semi-supervised learning algorithm which we term Bidirectional Label Propagation (BLP). Different from previous label propagation mechanisms that proceed along a single direction of graph edges, the BLP algorithm can propagate labels along not only positive but also negative edge directions. By using an initial neighborhood graph and class assignment constraints inherent among the labeled examples, a set of class-specific graphs are learned, which include both positive and negative edges and thus reveal discriminative cues. Over the learned graphs, a convex propagation criterion is carried out to ensure consistent labelings along the positive edges and inconsistent labelings along the negative edges. Experimental evidence discovered in synthetic and real-world datasets validates excellent performance of the proposed BLP algorithm.     

Graph embedding in vector spaces by node attribute statistics

Graph-based representations are of broad use and applicability in pattern recognition. They exhibit, however, a major drawback with regards to the processing tools that are available in their domain. Graph embedding into vector spaces is a growing field among the structural pattern recognition community which aims at providing a feature vector representation for every graph, and thus enables classical statistical learning machinery to be used on graph-based input patterns. In this work, we propose a novel embedding methodology for graphs with continuous node attributes and unattributed edges. The approach presented in this paper is based on statistics of the node labels and the edges between them, based on their similarity to a set of representatives. We specifically deal with an important issue of this methodology, namely, the selection of a suitable set of representatives. In an experimental evaluation, we empirically show the advantages of this novel approach in the context of different classification problems using several databases of graphs.     

三维图匹配算法

目的 现有的图匹配算法大多应用于二维图像,对三维图像的特征点匹配存在匹配准确率低和计算速度慢等问题。为解决这些问题,本文将分解图匹配算法扩展应用在了三维图像上。方法 首先将需要匹配的两个三维图像的特征点作为图的节点集;再通过Delaunay三角剖分算法,将三维特征点相连,则相连得到的边就作为图的边集,从而建立有向图;然后,根据三维图像的特征点构建相应的三维有向图及其邻接矩阵;再根据有向图中的节点特征和边特征分别构建节点特征相似矩阵和边特征相似矩阵;最后根据这两个特征矩阵将节点匹配问题转化为求极值问题并求解。结果 实验表明,在手工选取特征点的情况下,本文算法对相同三维图像的特征点匹配有97.56%的平均准确率;对不同三维图像特征点匹配有76.39%的平均准确率;在三维图像有旋转的情况下,有90%以上的平均准确率;在特征点部分缺失的情况下,平均匹配准确率也能达到80%。在通过三维尺度不变特征变换（SIFT）算法得到特征点的情况下,本文算法对9个三维模型的特征点的平均匹配准确率为98.78%。结论 本文提出的基于图论的三维图像特征点匹配算法,经实验结果验证,可以取得较好的匹配效果。     

融合结构与属性相似性的加权图聚集算法

图聚集技术是将一个大规模图用简洁的小规模图来表示,同时保留原始图的结构和属性信息的技术。现有算法未同时考虑节点的属性信息与边的权重信息,导致图聚集后与原始图存在较大差异。因此,提出一种同时考虑节点属性信息与边权重信息的图聚集算法,使得聚集图既保留了节点属性相似度又保留了边权重信息。该算法首先定义了闭邻域结构相似度,通过一种剪枝策略来计算节点之间的结构相似度;其次使用最小哈希(MinHash)技术计算节点之间的属性相似度,并调节结构相似与属性相似所占的比例;最后,根据2方面相似度的大小对加权图进行聚集。实验表明了该算法可行且有效。     

基于图的半监督关系抽取

提出利用基于图的半监督学习算法,即标注传递算法,指导计算机从非结构化的文本中自动识别出实体之间的关系.该方法首先利用图策略来建立关系抽取的模型.在这个图模型中,各个有标签和未标签的样本被表示成图上的各个节点,而样本间的距离则作为图上各边的权重.然后,关系抽取的任务就转化成在这个图上估计出一个满足全局一致性假设的标注函数通过对ACE(automatic content extraction)语料库的评测,结果显示,当只有少量的标签样本时,采用该标注传递的方法可以获得比基于SVM(support vector machine)的有监督关系抽取更好的性能,同时也明显优于基于Bootstrapping的半监督关系抽取的方法.     

Salient object detection method using random graph

In this paper, a bottom-up salient object detection method is proposed by modeling image as a random graph. The proposed method starts with portioning input image into superpixels and extracting color and spatial features for each superpixel. Then, a complete graph is constructed by employing superpixels as nodes. A high edge weight is assigned into a pair of superpixels if they have high similarity. Next, a random walk prior on nodes is assumed to generate the probability distribution on edges. On the other hand, a complete directed graph is created that each edge weight represents the probability for transmitting random walker from current node to next node. By considering a threshold and eliminating edges with higher probability than the threshold, a random graph is created to model input image. The inbound degree vector of a random graph is computed to determine the most salient nodes (regions). Finally, a propagation technique is used to form saliency map. Experimental results on two challenging datasets: MSRA10K and SED2 demonstrate the efficiency of the proposed unsupervised RG method in comparison with the state-of-the-art unsupervised methods.     

Graph-based semi-supervised learning

Recent years have witnessed a surge of interest in graph-based semi-supervised learning. However, two of the major problems in graph-based semi-supervised learning are: (1) how to set the hyperparameter in the Gaussian similarity; and (2) how to make the algorithm scalable. In this article, we introduce a general framework for graphbased learning. First, we propose a method called linear neighborhood propagation, which can automatically construct the optimal graph. Then we introduce a novel multilevel scheme to make our algorithm scalable for large data sets. The applications of our algorithm to various real-world problems are also demonstrated.     

Discriminative graph regularized broad learning system for image recognition

Broad learning system (BLS) has been proposed as an alternative method of deep learning. The architecture of BLS is that the input is randomly mapped into series of feature spaces which form the feature nodes, and the output of the feature nodes are expanded broadly to form the enhancement nodes, and then the output weights of the network can be determined analytically. The most advantage of BLS is that it can be learned incrementally without a retraining process when there comes new input data or neural nodes. It has been proven that BLS can overcome the inadequacies caused by training a large number of parameters in gradient-based deep learning algorithms. In this paper, a novel variant graph regularized broad learning system (GBLS) is proposed. Taking account of the locally invariant property of data, which means the similar images may share similar properties, the manifold learning is incorporated into the objective function of the standard BLS. In GBLS, the output weights are constrained to learn more discriminative information, and the classification ability can be further enhanced. Several experiments are carried out to verify that our proposed GBLS model can outperform the standard BLS. What is more, the GBLS also performs better compared with other state-of-the-art image recognition methods in several image databases.     

基于图论的边缘提取方法

针对传统边缘方法提取的边缘具有不连续、不完整、倾斜、抖动和缺口等问题,提出基于图论的边缘提取方法。该方法视像素为节点,在水平或垂直方向上连接两个相邻的节点构成一个边,从而将图像看作无向图。它包括三个阶段：在像素相似性计算阶段,无向图的边上被赋予权值,权值代表了像素间的相似性;在阈值确定阶段,将所有权值的均值（整幅图像的相似度）确定为阈值;在边缘确定阶段,只保留权值小于阈值的水平边的左边节点与垂直边的上边节点,从而获得了图像的边缘。实验表明,该方法适用于具有明显目标与背景的图像的边缘提取,能够克服不连续、不完整、倾斜、抖动和缺口等缺陷,并且对Speckle噪声和高斯噪声具有抗噪性能。     

基于随机游走的流形学习与可视化

现有的全局流形学习算法都敏感于邻域大小这一难以高效选取的参数,它们都采用了基于欧氏距离的邻域图创建方法,从而使邻域图容易产生“短路”边。本文提出了一种基于随机游走模型的全局 流形学习算法(Random walk-based isometric mapping,RW-ISOMAP)。和欧氏距离相比,由随机游走模型得到的通勤时间距离是由给定两点间的所有通路以概率为权组合而成的,不但鲁棒性更高,而且还能在一定程度上度量具有非线性几何结构的数据之间的相似性。因此采用通勤时间距离来创建邻域图的RW-ISOMAP算法将不再敏感于邻域大小参数,从而可以更容易地选取邻域大小参数,同时还具有更高的鲁棒性。最后的实验结果证实了该算法的有效性。     

基于局部尺度转换的拉普拉斯核方法

采用数据点的结构信息可以提高半监督学习的性能。为此,提出一种基于图的半监督学习方法。利用局部尺度转换对不同密度区域中的边权重设置不同的尺度参数,在此基础上构造图的拉普拉斯核分类器进行分类学习。在多个数据集上的实验显示该方法优于其他基于核的半监督分类方法。     

Range-free 3D node localization in anisotropic wireless sensor networks

In this paper, we propose two computationally efficient ‘range-free’ 3D node localization schemes using the application of hybrid-particle swarm optimization (HPSO) and biogeography based optimization (BBO). It is considered that nodes are deployed with constraints over three layer boundaries, in an anisotropic environment. The anchor nodes are randomly distributed over the top layer only and target nodes distributed over the middle and bottom layers. Radio irregularity factor, i.e., an anisotropic property of propagation media and heterogenous properties of the devices are considered. To overcome the non-linearity between received signal strength (RSS) and distance, edge weights between each target node and neighboring anchor nodes have been considered to compute the location of the target node. These edge weights are modeled using fuzzy logic system (FLS) to reduce the computational complexity. The edge weights are further optimized by HPSO and BBO separately to minimize the location error. Both the proposed applications of the two algorithms are compared with the earlier proposed range-free algorithms in literature, i.e., the simple centroid method and weighted centroid method. The results of our proposed applications of the two algorithms are better as compared to centroid and weighted centroid methods in terms of error and scalability.     

一种网页分类中基于图的半指导学习算法*

提出一种基于图的半指导学习算法用于网页分类.采用k近邻算法构建一个带权图,图中节点为已标志或未标志的网页,连接边的权重表示类的传播概率,将网页分类问题形式化为图中类的概率传播.为有效利用图中未标志节点辅助分类,结合网页的内容信息和链接信息计算网页间的链接权重,通过已标志节点,类别信息以一定概率从已标志节点推向未标志节点.实验表明,本文提出的算法能有效改进网页分类结果.     

结合显著性检测和中心分割算法的文本检测方法

针对复杂背景下的文本检测问题,提出了显著性检测与中心分割算法相结合的文本检测技术。对于输入的图像,首先分别使用前景与背景作为标准的显著性检测方法,背景检测时将图像的四边分别作为基准,前景检测时将背景检测中得到的非背景区域作为基准,最终可得到较准确的备选文本区。然后使用中心分割算法,得到精确的边缘图。由于显著性图备选区域准确边缘细节缺失,而边缘图边缘精确但无法得出备选文本区,因此将两者进行融合处理,得到最终文本区域。实验表明,所提出的方法有较好的检测效果。     

Multilabel Neighborhood Propagation for Region-Based Image Retrieval

Content-based image retrieval (CBIR) has been an active research topic in the last decade. As one of the promising approaches, graph-based semi-supervised learning has attracted many researchers. However, while the related work mainly focused on global visual features, little attention has been paid to region-based image retrieval (RBIR). In this paper, a framework based on multilabel neighborhood propagation is proposed for RBIR, which can be characterized by three key properties: 1) For graph construction, in order to determine the edge weights robustly and automatically, mixture distribution is introduced into the earth mover's distance (EMD) and a linear programming framework is involved. 2) Multiple low-level labels for each image can be obtained based on a generative model, and the correlations among different labels are explored when the labels are propagated simultaneously on the weighted graph. 3) By introducing multilayer semantic representation (MSR) and support vector machine (SVM) into the long-term learning, more exact weighted graph for label propagation and more meaningful high-level labels to describe the images can be calculated. Experimental results, including comparisons with the state-of-the-art retrieval systems, demonstrate the effectiveness of our proposal.      

Fast affinity propagation clustering: A multilevel approach

In this paper, we propose a novel Fast Affinity Propagation clustering approach (FAP). FAP simultaneously considers both local and global structure information contained in datasets, and is a high-quality multilevel graph partitioning method that can implement both vector-based and graph-based clustering. First, a new Fast Sampling algorithm (FS) is proposed to coarsen the input sparse graph and choose a small number of final representative exemplars. Then a density-weighted spectral clustering method is presented to partition those exemplars on the global underlying structure of data manifold. Finally, the cluster assignments of all data points can be achieved through their corresponding representative exemplars. Experimental results on two synthetic datasets and many real-world datasets show that our algorithm outperforms the state-of-the-art original affinity propagation and spectral clustering algorithms in terms of speed, memory usage, and quality on both vector-based and graph-based clustering.     

Editorial of the Special Issue on Manifold Learning

In many information analysis tasks, one is often confronted with thousands to millions dimensional data, such as images, documents, videos, web data, bioinformatics data, etc. Conventional statistical and computational tools are severely inadequate for processing and analysing high-dimensional data due to the curse of dimensionality, where we often need to conduct inference with a limited number of samples. On the other hand, naturally occurring data may be generated by structured systems with possibly much fewer degrees of freedom than the ambient dimension would suggest. Recently, various works have considered the case when the data is sampled from a submanifold embedded in the much higher dimensional Euclidean space. Learning with full consideration of the low dimensional manifold structure, or specifically the intrinsic topological and geometrical properties of the data manifold is referred to as manifold learning, which has been receiving growing attention in our community in recent years. This special issue is to attract articles that (a) address the frontier problems in the scientific principles of manifold learning, and (b) report empirical studies and applications of manifold learning algorithms, including but not limited to pattern recognition, computer vision, web mining, image processing and so on. A total of 13 submissions were received. The papers included in this special issue are selected based on the reviews by experts in the subject area according to the journal''s procedure and quality standard. Each paper is reviewed by at least two reviewers and some of the papers were revised for two rounds according to the reviewers'' comments. The special issue includes 6 papers in total: 3 papers on the foundational theories of manifold learning, 2 papers on graph-based methods, and 1 paper on the application of manifold learning to video compression. The papers on the foundational theories of manifold learning cover the topics about the generalization ability of manifold learning, manifold ranking, and multi-manifold factorization. In the paper entitled ``Manifold Learning: Generalizing Ability and Tangential Proximity'', Bernstein and Kuleshov propose a tangential proximity based technique to address the generalized manifold learning problem. The proposed method ensures not only proximity between the points and their reconstructed values but also proximity between the corresponding tangent spaces. The traditional manifold ranking methods are based on the Laplacian regularization, which suffers from the issue that the solution is biased towards constant functions. To overcome this issue, in the paper entitled ``Manifold Ranking using Hessian Energy'', Guan et al. propose to use the second-order Hessian energy as regularization for manifold ranking. In the paper entitled ``Multi-Manifold Concept Factorization for Data Clustering'', Li et al. incorporate the multi-manifold ensemble learning into concept factorization to better preserve the local structure of the data, thus yielding more satisfactory clustering results. The papers on graph-based methods cover the topics about label propagation and graph-based dimensionality reduction. In the paper entitled ``Bidirectional Label Propagation over Graphs'', Liu et al. propose a novel label propagation algorithm to propagate labels along positive and negative edges in the graph. The construction of the graph is novel against the conventional approach by incorporating the dissimilarity among data points into the affinity matrix. In the paper entitled ``Locally Regressive Projections'', Lijun Zhang proposes a novel graph-based dimensionality reduction method that captures the local discriminative structure of the data space. The key idea is to fit a linear model locally around each data point, and then use the fitting error to measure the performance of dimensionality reduction. In the last paper entitled ``Combining Active and Semi-Supervised Learning for Video Compression'', motivated from manifold regularization, Zhang and Ji propose a machine learning approach for video compression. Active learning is used to select the most representative pixels in the encoding process, and semi-supervised learning is used to recover the color video in the decoding process. One remarking property of this approach is that the active learning algorithm shares the same loss function as the semi-supervised learning algorithm, providing a unified framework for video compression. Many people have been involved in making this special issue possible. The guest editor would like to express his gratitude to all the contributing authors for their insightful work on manifold learning. The guest editor would like to thank the reviewers for their comments and useful suggestions in order to improve the quality of the papers. The guest editor would also like to thank Prof. Ruqian Lu, the editor-in-chief of the International Journal of Software and Informatics, for providing the precious opportunity to publish this special issue. Finally, we hope the reader will enjoy this special issue and find it useful.