Spectral clustering: A semi-supervised approach

Recently, graph-based spectral clustering algorithms have been developing rapidly, which are proposed as discrete combinatorial optimization problems and approximately solved by relaxing them into tractable eigenvalue decomposition problems. In this paper, we first review the current existing spectral clustering algorithms in a unified-framework way and give a straightforward explanation about spectral clustering. We also present a novel model for generalizing the unsupervised spectral clustering to semi-supervised spectral clustering. Under this model, prior information given by some instance-level constraints can be generalized to space-level constraints. We find that (undirected) graph built on the enlarged prior information is more meaningful, hence the boundaries of the clusters are more correct. Experimental results based on toy data, real-world data and image segmentation demonstrate the advantages of the proposed model.     

A second order cone programming approach for semi-supervised learning

Semi-supervised learning (SSL) involves the training of a decision rule from both labeled and unlabeled data. In this paper, we propose a novel SSL algorithm based on the multiple clusters per class assumption. The proposed algorithm consists of two stages. In the first stage, we aim to capture the local cluster structure of the training data by using the k-nearest-neighbor (kNN) algorithm to split the data into a number of disjoint subsets. In the second stage, a maximal margin classifier based on the second order cone programming (SOCP) is introduced to learn an inductive decision function from the obtained subsets globally. For linear classification problems, once the kNN algorithm has been performed, the proposed algorithm trains a classifier using only the first and second order moments of the subsets without considering individual data points. Since the number of subsets is usually much smaller than the number of training points, the proposed algorithm is efficient for handling big data sets with a large amount of unlabeled data. Despite its simplicity, the classification performance of the proposed algorithm is guaranteed by the maximal margin classifier. We demonstrate the efficiency and effectiveness of the proposed algorithm on both synthetic and real-world data sets.     

Polygonal space carving with geometric anti-aliasing

This paper proposes an algorithm that solves the shape recovery problem from N arbitrary images. By introducing a polygonal carving technique, the proposed algorithm can reconstruct the image-consistent polygonal shape that is patched by input images. This algorithm eliminates the invalid vertices and polygons from the initial polygonal grid space according to the color variance that represents their image consistency. The carved shape is refined by moving the outlier vertices on the boundary of each image. The final reconstructed shape faithfully accounts for the input images, and its textured appearance reflects the similar color property of the target object.     

Exploiting constraint inconsistence for dimension selection in subspace clustering: A semi-supervised approach

Selecting correct dimensions is very important to subspace clustering and is a challenging issue. This paper studies semi-supervised approach to the problem. In this setting, limited domain knowledge in the form of space level pair-wise constraints, i.e., must-links and cannot-links, are available. We propose a semi-supervised subspace clustering (S³C) algorithm that exploits constraint inconsistence for dimension selection. Our algorithm firstly correlates globally inconsistent constraints to dimensions in which they are consistent, then unites constraints with common correlating dimensions, and finally forms the subspaces according to the constraint unions. Experimental results show that S³C is superior to the typical unsupervised subspace clustering algorithm FINDIT, and the other constraint based semi-supervised subspace clustering algorithm SC-MINER.     

Integrative 3D modelling of complex carving surface

Modelling of a complex carving surface is the most important process for digitization of art carving such as Chinese classical furniture carving, and it is difficult to be fulfilled. However, a complex 2D curve flower pattern can be easily acquired or drawn by handcraft or a drawing software. This paper presents a quick integrative 3D modeling method of complex carving surface based on a 2D curve flower pattern. The proposed method uses a scanning analysis algorithm, a normal distribution function and a distance function to model and create carving tracks. In this paper, the delamination, combination and interpolation of modelling process are described as well. The provided research method will make the modelling of complex carving surface more intelligent, agile, and will meet the requirement of integrative 3D modelling of digital art carving. Experimental results show that this method is of quick modelling and multi-model effective characteristics with realizable interactive designing and excellent practicability.     

A multi-manifold semi-supervised Gaussian mixture model for pattern classification

Semi-supervised Gaussian mixture model (SGMM) has been successfully applied to a wide range of engineering and scientific fields, including text classification, image retrieval, and biometric identification. Recently, many studies have shown that naturally occurring data may reside on or near manifold structures in ambient space. In this paper, we study the use of SGMM for data sets containing multiple separated or intersecting manifold structures. We propose a new multi-manifold regularized, semi-supervised Gaussian mixture model (M2SGMM) for classifying multiple manifolds. Specifically, we model the data manifold using a similarity graph with local and geometrical consistency properties. The geometrical similarity is measured by a novel application of local tangent space. We regularize the model parameters of the SGMM by incorporating the enhanced Laplacian of the graph. Experiments demonstrate the effectiveness of the proposed approach.     

A fast approach to deformable surface 3D tracking

Deformable surface 3D tracking is a severely under-constrained problem and great efforts have been made to solve it. A recent state-of-the-art approach solves this problem by formulating it as a second order cone programming (SOCP) problem. However, one drawback of this approach is that it is time-consuming. In this paper, we propose an effective method for 3D deformable surface tracking. First, we formulate the deformable surface tracking problem as a linear programming (LP) problem. Then, we solve the LP problem with an algorithm which converges superlinearly rather than bisection algorithm whose convergence speed is linear. Our experimental studies on synthetic and real data have demonstrated the proposed method can not only reliably recover 3D structures of surfaces but also run faster than the state-of-the-art method.     

A global optimization method for semi-supervised clustering

In this paper, we adapt Tuy’s concave cutting plane method to the semi-supervised clustering. We also give properties of local optimal solutions of the semi-supervised clustering. Numerical examples show that this method can give a better solution than other semi-supervised clustering algorithms do.     

BASSUM: A Bayesian semi-supervised method for classification feature selection

Feature selection is an important preprocessing step for building efficient, generalizable and interpretable classifiers on high dimensional data sets. Given the assumption on the sufficient labelled samples, the Markov Blanket provides a complete and sound solution to the selection of optimal features, by exploring the conditional independence relationships among the features. In real-world applications, unfortunately, it is usually easy to get unlabelled samples, but expensive to obtain the corresponding accurate labels on the samples. This leads to the potential waste of valuable classification information buried in unlabelled samples.In this paper, we propose a new BAyesian Semi-SUpervised Method, or BASSUM in short, to exploit the values of unlabelled samples on classification feature selection problem. Generally speaking, the inclusion of unlabelled samples helps the feature selection algorithm on (1) pinpointing more specific conditional independence tests involving fewer variable features and (2) improving the robustness of individual conditional independence tests with additional statistical information. Our experimental results show that BASSUM enhances the efficiency of traditional feature selection methods and overcomes the difficulties on redundant features in existing semi-supervised solutions.     

A semi-supervised social relationships inferred model based on mobile phone data

Exploring the relationships of humans is an important study in the mobile communication network. But the relationship prediction accuracy is not good enough when the number of known relationship labels (e.g., “friend” and “colleague”) is small, especially when the number of different relation classes are imbalanced in the mobile communication network. To deal with issues, we present a semi-supervised social relationships inferred model. This model can infer the relationships based on a large amount of unlabeled data or a small amount of labeled data. The model is a co-training style semi-supervised model which is combined with the support vector machine and naive Bayes. The final relationship labels are decided by the two classifiers. The proposed model is evaluated by a real mobile communication network dataset and the experiment results show that the model is effective in relationship mining, especially when the relationship network is in a stable state.     

Interactive 3D reconstruction from multiple images: A primitive-based approach

This paper proposes a fast and stable image-based modeling method which generates 3D models with high-quality face textures in a semi-automatic way. The modeler guides untrained users to quickly obtain 3D model data via several steps of simple user interface operations using predefined 3D primitives. The proposed method contains an iterative non-linear error minimization technique in the model estimation step with an error function based on finite line segments instead of infinite lines. The error corresponds to the difference between the observed structure and the predicted structure from current model parameters. Experimental results on real images validate the robustness and the accuracy of the algorithm.     

From transport to diffusion through a space asymptotic approach

The spatially asymptotic theory is a useful approach to the neutron transport model for nuclear reactor physics applications. For steady-state problems the transport equation is taken in an infinite medium and it is treated by the Fourier transform. A formal solution is thus obtained for any assumption on the order of anisotropy, leading to the _BN$B_N$ formulation. In the case of isotropic emissions the Green function of the problem can be given an explicit expression by the inverse Fourier transformation, leading to the solution that can also be obtained by Case method.     

Feature-based approach to semi-supervised similarity learning

For the management of digital document collections, automatic database analysis still has difficulties to deal with semantic queries and abstract concepts that users are looking for. Whenever interactive learning strategies may improve the results of the search, system performances still depend on the representation of the document collection. We introduce in this paper a weakly supervised optimization of a feature vector set. According to an incomplete set of partial labels, the method improves the representation of the collection, even if the size, the number, and the structure of the concepts are unknown. Experiments have been carried out on synthetic and real data in order to validate our approach.     

A mathematical morphology approach to image based 3D particle shape analysis

Angularity is a critically important property in terms of the performance of natural particulate materials. It is also one of the most difficult to measure objectively using traditional methods. Here we present an innovative and efficient approach to the determination of particle angularity using image analysis. The direct use of three-dimensional data offers a more robust solution than the two-dimensional methods proposed previously. The algorithm is based on the application of mathematical morphological techniques to range imagery, and effectively simulates the natural wear processes by which rock particles become rounded. The analysis of simulated volume loss is used to provide a valuable measure of angularity that is geometrically commensurate with the traditional definitions. Experimental data obtained using real particle samples are presented and results correlated with existing methods in order to demonstrate the validity of the new approach. The implementation of technologies such as these has the potential to offer significant process optimisation and environmental benefits to the producers of aggregates and their composites. The technique is theoretically extendable to the quantification of surface texture.     

Tools for constructing pseudo-3D space on the WWW using images

Recently, due to advancements in virtual reality and computer graphics technologies, a virtual space that looks as real as a real space has been constructed. Accordingly, there are many studies that employ virtual spaces to support human communication and remote working. Until now, the virtual space employed by these studies has been composed of geometric models. Since the real space is very large and there are a lot of objects in the real world, the cost of modeling the real space is very high. In our previous paper,¹⁰⁾ we proposed a method for building a virtual space using image data, named theimage based non-rendering (IBNR), in order to cut down the cost. In this paper, we explain the design and implementation of the tools which we implemented to construct virtual spaces based on IBNR. With these tools, it is easy to construct and renew a large-scaled virtual space based on the real space. Takefumi Ogawa: He received his B.E. and M.E. degrees in Information Systems Engineering from Osaka University, Osaka, Japan, in 1997 and 1999, respectively. Currently, he is a Research Associate of the Infomedia Education Division, Cybermedia Center, Osaka University. He is a member of IEEE, IEICE, IPSJ, and VRSJ. His research interests include virtual reality systems and augmented reality systems. Masahiko Tsukamoto, Ph.D.: He received his B.E., M.E., and Dr.E. degrees from Kyoto University, Kyoto, Japan, in 1987, 1989, and 1994, respectively. From 1989 to February 1995, he was a research engineer of Sharp Corporation. Since March 1995, he has been an Assistant Professor in the Department of Information Systems Engineering of Osaka University and since October 1996, he has been an Associate Professor at the same department. He is a member of seven learned societies, including ACM and IEEE. His current research interests include database systems, knowledge-base systems, and distributed computing systems.     

A spectral approach to clustering numerical vectors as nodes in a network

We address the issue of clustering examples by integrating multiple data sources, particularly numerical vectors and nodes in a network. We propose a new, efficient spectral approach, which integrates the two costs for clustering numerical vectors and clustering nodes in a network into a matrix trace, reducing the issue to a trace optimization problem which can be solved by an eigenvalue decomposition. We empirically demonstrate the performance of the proposed approach through a variety of experiments, including both synthetic and real biological datasets.     

Semi-supervised fuzzy clustering: A kernel-based approach

Semi-supervised clustering algorithms aim to improve the clustering accuracy under the supervisions of a limited amount of labeled data. Since kernel-based approaches, such as kernel-based fuzzy c-means algorithm (KFCM), have been successfully used in classification and clustering problems, in this paper, we propose a novel semi-supervised clustering approach using the kernel-based method based on KFCM and denote it the semi-supervised kernel fuzzy c-mean algorithm (SSKFCM). The objective function of SSKFCM is defined by adding classification errors of both the labeled and the unlabeled data, and its global optimum has been obtained through repeatedly updating the fuzzy memberships and the optimized kernel parameter. The objective function may have more than one local optimum, so we employ a function transformation technique to reformulate the objective function after a local minimum has been obtained, and select the best optimum as the solution to the objective function. Experimental results on both the artificial and several real data sets show SSKFCM performs better than its conventional counterparts and it achieves the best accurate clustering results when the parameter is optimized.     

Multi-object reconstruction from dynamic scenes: An object-centered approach

In this paper, we present a new framework for three-dimensional (3D) reconstruction of multiple rigid objects from dynamic scenes. Conventional 3D reconstruction from multiple views is applicable to static scenes, in which the configuration of objects is fixed while the images are taken. In our framework, we aim to reconstruct the 3D models of multiple objects in a more general setting where the configuration of the objects varies among views. We solve this problem by object-centered decomposition of the dynamic scenes using unsupervised co-recognition approach. Unlike conventional motion segmentation algorithms that require small motion assumption between consecutive views, co-recognition method provides reliable accurate correspondences of a same object among unordered and wide-baseline views. In order to segment each object region, we benefit from the 3D sparse points obtained from the structure-from-motion. These points are reliable and serve as automatic seed points for a seeded-segmentation algorithm. Experiments on various real challenging image sequences demonstrate the effectiveness of our approach, especially in the presence of abrupt independent motions of objects.     

A new approach to 3D reconstruction without camera calibration

In this paper, we present a new approach for 3D scene reconstruction based on projective geometry without camera calibration. Previous works use at least six points to build two projective reference planes. Our contribution is to reduce the number of reference points to four by exploiting some geometrical shapes contained in the scene. The first implemented algorithm allows the reconstruction of a fourth point on each reference plane. The second algorithm is devoted to the 3D reconstruction. We obtained the expected good results and the proposed method is to equip a mobile robot moving in a structured environment.