Structural, Syntactic, and Statistical Pattern Recognition

We consider how continuous-time quantum walks can be used for graph matching. We focus in detail on both exact and inexact graph matching, and consider in depth the problem of measuring graph similarity. We commence by constructing an auxiliary graph, in which the two graph to be matched are co-joined by a layer of indicator nodes (one for each potential correspondence between a pair of nodes). We simulate a continuous time quantum walk in parallel on the two graphs. The layer of connecting indicator nodes in the auxiliary graph allow quantum interference to take place between the two walks. The interference amplitudes on the indicator nodes are determined by differences in the two walks. We show how these interference amplitudes can be used to compute graph edit distances without explicitly determining node correspondences.

Given a set of graphs, the median graph is defined as the graph which has the smallest sum of distances (SOD) to all the graphs in the set. It has been proposed as a tool to obtain the representative of such a set. In spite of its potential applications, the existing algorithms are computationally complex and have a very limited applicability. In this paper we propose a new approach for the exact computation of the median graph based on graph embedding in vector spaces. Graphs are embedded into a vector space and the median is computed in the vector domain. After that, the median graph is recovered from this median vector. Experiments on a synthetic database show that our approach outperforms the previous existing exact algorithms both on computation time and number of SOD computations.

Delaunay tessellation describes a set of arbitrarily distributed points as unique triangular graphs which preserves most local point configuration called a clique regardless of noise addition and partial occlusion. In this paper, this structure is utilised in a matching method and proposed a clique-based Hausdorff Distance (HD) to address point pattern matching problems. Since the proposed distance exploits similarity invariant features extracted from a clique, it is invariant to rotation, translation and scaling. Furthermore, it inherits noise robustness from HD and has partial matching ability because matching performs on local entities. Experimental results show that the proposed method performs better than the existing variants of the general HD.

In graph comparison, the use of (dis)similarity measurements between graphs is an important topic. In this work, we propose an eigendecomposition based approach for measuring dissimilarities between graphs in the

joint

eigenspace (JoEig). We will compare our JoEig approach with two other eigendecomposition based methods that compare graphs in

different

eigenspaces. To calculate the dissimilarity between graphs of different sizes and perform inexact graph comparison, we further develop three different ways to resize the eigenspectra and study their performance in different situations.

This article presents a vectorial representation of structured data to reduce the complexity of dissimilarity computations in an information retrieval context. This representation enables, via a computation of an adapted measure, to approximate the distance between structural representations in both context of distance between graphs and searching occurrences of subgraphs. Preliminary results show that the proposed representation offers comparable performance with those of the literature.

Music genre meta-data is of paramount importance for the organization of music repositories. People use genre in a natural way when entering a music store or looking into music collections. Automatic genre classification has become a popular topic in music information retrieval research. This work brings to symbolic music recognition some technologies, like the stochastic language models, already successfully applied to text categorization. In this work we model chord progressions and melodies as

n

-grams and strings and then apply perplexity and naïve Bayes classifiers, respectively, in order to assess how often those structures are found in the target genres. Also a combination of the different techniques as an ensemble of classifiers is proposed. Some genres and sub-genres among popular, jazz, and academic music have been considered. The results show that the ensemble is a good trade-off approach able to perform well without the risk of choosing the wrong classifier.

Applications of probabilistic grammatical inference are limited due to time and space consuming constraints. In statistical language modeling, for example, large corpora are now available and lead to managing automata with millions of states. We propose in this article a method for pruning automata (when restricted to tree based structures) which is not only efficient (sub-quadratic) but that allows to dramatically reduce the size of the automaton with a small impact on the underlying distribution. Results are evaluated on a language modeling task.

In statistical language modelling the classic model used is

n

-gram. This model is not able however to capture long term dependencies,

i.e.

dependencies larger than

n

. An alternative to this model is the probabilistic automaton. Unfortunately, it appears that preliminary experiments on the use of this model in language modelling is not yet competitive, partly because it tries to model too long term dependencies. We propose here to improve the use of this model by restricting the dependency to a more reasonable value. Experiments shows an improvement of 45% reduction in the perplexity obtained on the Wall Street Journal language modeling task.

In a music recognition task, the classification of a new melody is often achieved by looking for the closest piece in a set of already known prototypes. The definition of a relevant similarity measure becomes then a crucial point. So far, the edit distance approach with a-priori fixed operation costs has been one of the most used to accomplish the task. In this paper, the application of a probabilistic learning model to both string and tree edit distances is proposed and is compared to a genetic algorithm cost fitting approach. The results show that both learning models outperform fixed-costs systems, and that the probabilistic approach is able to describe consistently the underlying melodic similarity model.

We propose a probabilistic model that captures contextual information in the form of typical spatial relationships between regions of an image. We represent a region’s local context as a combination of the identity of neighbouring regions as well as the geometry of the neighbourhood. We subsequently cluster all the neighbourhood configurations with the same label at the focal region to obtain, for each label, a set of configuration

prototypes

. We propose an iterative procedure based on belief propagation to infer the labels of regions of a new image given only the observed spatial relationships between the regions and the hitherto learnt prototypes. We validate our approach on a dataset of hand segmented and labelled images of buildings. Performance compares favourably with that of a boosted, non-contextual classifier.

Video surveillance of large facilities, such as airports, rail stations and casinos, is developing rapidly. Cameras installed at such locations often overlook large crowds, which makes problems such as activity and scene understanding very challenging. Traditional activity recognition methods which rely on input from lower level processing units dealing with background subtraction and tracking, are unable to cope with frequent occlusions in such scenes. In this paper, we propose a novel activity representation and recognition method that bypasses these commonly used low level modules. We model each local spatio-temporal patch as a dynamic texture. Using a Martin distance metric to compare two patches based on their estimated dynamic texture parameters, we present a method to temporally stitch together local regions to form activity streamlines and represent each streamline by its constituent dynamic textures. This allows us to seamlessly perform activity recognition without explicitly detecting individuals in the scene. We demonstrate our method on multiple real data sets and show promising results.

Local invariant feature-based methods such as SIFT have been proven highly effective for object recognition. However, they have made either relatively little use or too complex use of geometric constraints and are confounded when the detected features are superabundant. Here we make two contributions aimed at overcoming these problems. First, we rank the SIFT points (R-SIFT) using visual saliency. Second, we use the reduced set of R-SIFT features to construct a class specific hyper graph (CSHG) which comprehensively utilizes local SIFT and global geometric constraints. Moreover, it efficiently captures multiple object appearance instances. We show how the CSHG can be learned from example images for objects of a particular class. Experiments reveal that the method gives excellent recognition performance, with a low false-positive rate.

Template matching is widely used in machine vision, digital photogrammetry, and multimedia data mining to search for a target object by similarity between its prototype image (template) and a sensed image of a natural scene containing the target. In the real-world environment, similarity scores are frequently affected by contrast / offset deviations between the template and target signals. Most of the popular least-squares scores presume only simple smooth deviations that can be approximated with a low-order polynomial. This paper proposes an alternative and more general quadratic programming based matching score that extends the conventional least-squares framework onto both smooth and non-smooth signal deviations.

Holistic representations of natural scenes is an effective and powerful source of information for semantic classification and analysis of arbitrary images. Recently, the frequency domain has been successfully exploited to holistically encode the content of natural scenes in order to obtain a robust representation for scene classification. In this paper, we present a new approach to

naturalness

classification of scenes using frequency domain. The proposed method is based on the ordering of the Discrete Fourier Power Spectra. Features extracted from this ordering are shown sufficient to build a robust holistic representation for

Natural

vs.

Artificial

scene classification. Experiments show that the proposed frequency domain method matches the accuracy of other state-of-the-art solutions.

The use of Fuzzy Adaptive Resonance Theory (FA) is explored for the unsupervised color quantization of a color image. The red, green and blue color component values of a given color image are passed as input instances into FA which then groups similar colors into the same class. The average of all of the colors in a given class then replaces the pixel values whose original colors belonged to that class. The FA unsupervised clustering is capable of realizing color quantization with competitive accuracy and arguably low computation time.

This paper explores whether facial expressions can be recognised by using the distribution of surface normal directions in the extended Gaussian image (EGI). We work with range images and extract surface normals using a mesh fitting technique. Our representation of the surface normals is based on the co-efficients of spherical harmonics extracted from the EGI. We explore whether the co-efficients can be used to construct shape-spaces that capture variations in facial expression using a number of manifold learning techniques. Based on a comparison of various alternatives, the best results are given by the diffusion map.

Adjacency and Laplacian matrices are popular structures to use as representations of shape graphs, because their sorted sets of eigenvalues (spectra) can be used as signatures for shape retrieval. Unfortunately, the descriptiveness of these spectra is limited, and handling graphs of different size remains a challenge. In this work, we propose a new framework in which the shapes (3D models in our test corpus) are represented by multi-labeled graphs. A Hermitian matrix is associated to each graph, in which the entries are defined such that they contain all information stored in the graph edges. Additional constraints ensure that this Hermitian matrix mimics the well-studied spectral behaviour of the Laplcian matrix. We therefore use the Hermitian Fiedler vector as shape signature during retrieval. To deal with graphs of different size, we efficiently reuse the calculated Fiedler vector to decompose the graph into a limited number of non-overlapping, meaningful subgraphs. Retrieval results are based on both complete matching and subgraph matching.

We propose a combination of shape prior models with Markov Random Fields. The model allows to integrate multiple shape priors and appearance models into MRF-models for segmentation. We discuss a recognition task and introduce a general learning scheme. Both tasks are solved in the scope of the model and verified experimentally.

Sensors such as video surveillance and weather monitoring systems record a significant amount of dynamic data which are represented by vector fields. We present a novel algorithm to measure the similarity of vector fields using global distributions that capture both vector field properties (e.g., vector orientation) and relational geometric information (e.g., the relative positions of two vectors in the field). We show that such global distributions are capable of distinguishing between vector fields of varying complexity and can be used to quantitatively compare similar fields.

Finding the most relevant symmetry planes for an object is a key step in many computer vision and object recognition tasks. In fact such information can be effectively used as a starting point for object segmentation, noise reduction, alignment and recognition. Some of these applications are strongly affected by the accuracy of symmetry planes estimation, thus the use of a technique that is both accurate and robust to noise is critical. In this paper we introduce a new weighted association graph which relates the main symmetry planes of 3D objects to large sets of tightly coupled vertices. This technique allows us to cast symmetry detection to a classical pairwise clustering problem, which we solve using the very effective Dominant Sets framework. The improvement of our approach over other well known techniques is shown with several tests over both synthetic data and sampled point clouds.

In this paper we explore how to characterise graphs using the Gauss-Bonnet theorem. Using the Gaussian curvatures estimated from first-order cycles we compute a global estimate of the Euler index using the Gauss-Bonnet theorem. We commence by embedding the nodes of a graph in a manifold using the heat-kernel mapping. From this mapping we are able to compute the geodesic and Euclidean distance between nodes, and these can be used to estimate the sectional curvatures of edges. Assuming that edges reside on hyper-spheres, we use Gauss’s theorem to estimate the Gaussian curvature from the interior angles of geodesic triangles formed by first-order cycles in the graph. From the Gaussian curvatures we make a global estimate of the Euler index of the manifold using the Gauss-Bonnet theorem. Experiments show how the Gaussian curvatures and the Euler characteristics can be used to cluster Delaunay triangulations extracted from real world images.

The Laplacian spectrum has proved useful for pattern analysis tasks, and one of its important properties is its close relationship with the heat equation. In this paper, we first show how permutation invariants computed from the trace of the heat kernel can be used to characterize graphs for the purposes of measuring similarity and clustering. We explore three different approaches to characterize the heat kernel trace as a function of time. These are the heat kernel trace moments, heat content invariants and symmetric polynomials with Laplacian eigenvalues as inputs. We then use synthetic and real world datasets to give a quantitative evaluation of these feature invariants deduced from heat kernel analysis. We compare their performance with traditional spectrum invariants.

Graph kernels methods are based on an implicit embedding of graphs within a vector space of large dimension. This implicit embedding allows to apply to graphs methods which where until recently solely reserved to numerical data. Within the shape classification framework, graphs are often produced by a skeletonization step which is sensitive to noise. We propose in this paper to integrate the robustness to structural noise by using a kernel based on a bag of path where each path is associated to a hierarchy encoding successive simplifications of the path. Several experiments prove the robustness and the flexibility of our approach compared to alternative shape classification methods.

In this paper, we show how to quantify graph complexity in terms of the normalized entropies of convex Birkhoff combinations. We commence by demonstrating how the heat kernel of a graph can be decomposed in terms of Birkhoff polytopes. Drawing on the work of Birkhoff and von Neuman, we next show how to characterise the complexity of the heat kernel. Finally, we provide connections with the permanent of a matrix, and in particular those that are doubly stochastic. We also include graph embedding experiments based on polytopal complexity, mainly in the context of Bioinformatics (like the clustering of protein-protein interaction networks) and image-based planar graphs.

Current feature-based gesture recognition systems use human-chosen features to perform recognition. Effective features for classification can also be automatically learned and chosen by the computer. In other recognition domains, such as face recognition, manifold learning methods have been found to be good nonlinear feature extractors. Few manifold learning algorithms, however, have been applied to gesture recognition. Current manifold learning techniques focus only on spatial information, making them undesirable for use in the domain of gesture recognition where stroke timing data can provide helpful insight into the recognition of hand-drawn symbols. In this paper, we develop a new algorithm for multi-stroke gesture recognition, which integrates timing data into a manifold learning algorithm based on a kernel Isomap. Experimental results show it to perform better than traditional human-chosen feature-based systems.

This paper shows how to extract permutation invariant graph characteristics from the Ihara zeta function. In a previous paper, we have shown that the Ihara zeta function leads to a polynomial characterization of graph structure, and we have shown empirically that the coefficients of the polynomial can be used as to cluster graphs. The aim in this paper is to take this study further by showing how to select the most significant coefficients and how these can be used to gauge graph similarity. Experiments on real-world datasets reveal that the selected coefficients give results that are significantly better than those obtained with the Laplacian spectrum.

In this paper we describe our 3D object signature for 3D object classification. The signature is based on a learning approach that finds salient points on a 3D object and represent these points in a 2D spatial map based on a longitude-latitude transformation. Experimental results show high classification rates on both pose-normalized and rotated objects and include a study on classification accuracy as a function of number of rotations in the training set.

This paper presents a novel approach for visual object classification. Based on Gestalt theory, we propose to extract features from coarse regions carrying visually significant information such as line segments and/or color and to include neighborhood information in them. We also introduce a new classification method based on the polynomial modeling of feature distribution which avoids some drawbacks of a popular approach, namely “bag of keypoints”. Moreover we show that by separating features extracted from different sources in different “channels”, which are then combined using a late fusion strategy, we can limit the impact of feature dimensionality and actually improve classification accuracy. Using this classifier, experiments reveal that our features lead to better results than the popular SIFT descriptors, but also that they can be combined with SIFT features to reinforce performance, suggesting that our features managed to extract information which is complementary to the one of SIFT features.

In recent years the use of graph based representation has gained popularity in pattern recognition and machine learning. As a matter of fact, object representation by means of graphs has a number of advantages over feature vectors. Therefore, various algorithms for graph based machine learning have been proposed in the literature. However, in contrast with the emerging interest in graph based representation, a lack of standardized graph data sets for benchmarking can be observed. Common practice is that researchers use their own data sets, and this behavior cumbers the objective evaluation of the proposed methods. In order to make the different approaches in graph based machine learning better comparable, the present paper aims at introducing a repository of graph data sets and corresponding benchmarks, covering a wide spectrum of different applications.

Typically, graphs generated via skeletonization of shape images are small and present low structural constraints. This fact constitutes a source of ambiguities for structural matching methods. Hybrid Genetic Algorithms have been effectively used for graph matching. This paper presents a new method which combines Hybrid Genetic Search with an enhanced model for graph matching. This enhanced model is based on the cliques model by Wilson and Hancock but introduces Procrustes Analysis over positional information in order to eliminate ambiguities. Comparative results are presented of the performance of the Hybrid Genetic algorithm with both the original cliques model and the enhanced model.

In this paper we investigate how to establish a hypergraph model for characterizing object structures and how to embed this model into a low-dimensional pattern space. Each hyperedge of the hypergraph model is derived from a seed feature point of the object and embodies those neighbouring feature points that satisfy a similarity constraint. We show how to construct the Laplacian matrix of the hypergraph. We adopt the spectral method to construct pattern vectors from the hypergraph Laplacian. We apply principal component analysis (PCA) to the pattern vectors to embed them into a low-dimensional space. Experimental results show that the proposed scheme yields good clusters of distinct objects viewed from different directions.

The aim in this paper is to develop a method for clustering together image views of the same object class. Local invariant feature methods, such as SIFT, have been proven effective for image clustering. However, they have made either relatively little use or too complex use of geometric constraints and are confounded when the detected features are superabundant. Here we make two contributions aimed at overcoming these problems. First, we rank the SIFT points (R-SIFT) using visual saliency. Second, we use the reduced set of R-SIFT features to construct a specific hyper graph (CSHG) model of holistic-structure. Based on the CSHG model, a two stage clustering method is proposed. In which, images are clustered according to the pairwise similarity of the graphs, which is a combination of the traditional similarity of local invariant feature vectors and the geometric similarity between two graphs. This method comprehensively utilizes both SIFT and geometric constraints, and hence combines both global and local information. Experiments reveal that the method gives excellent clustering performance.

The problem of learning the class identity of visual objects has received considerable attention recently. With rare exception, all of the work to date assumes low variation in appearance, which limits them to a single depictive style usually photographic. The same object depicted in other styles — as a drawing, perhaps — cannot be identified reliably. Yet humans are able to name the object no matter how it is depicted, and even recognise a real object having previously seen only a drawing.

This paper describes a classifier which is unique in being able to learn class identity no matter how the class instances are depicted. The key to this is our proposition that topological structure is a class invariant. Practically, we depend on spectral graph analysis of a hierarchical description of an image to construct a feature vector of fixed dimension. Hence structure is transformed to a feature vector, which can be classified using standard methods. We demonstrate the classifier on several diverse classes.

This paper presents a novel approximate nearest neighbor classification scheme,

Local Fisher Discriminant Component Hashing

(LFDCH). Nearest neighbor (NN) classification is a popular technique in the field of pattern recognition but has poor classification speed particularly in high-dimensional space. To achieve fast NN classification, Principal Component Hashing (PCH) has been proposed, which searches the NN patterns in low-dimensional eigenspace using a hash algorithm. It is, however, difficult to achieve accuracy and computational efficiency simultaneously because the eigenspace is not necessarily the optimal subspace for classification. Our scheme, LFDCH, introduces Local Fisher Discriminant Analysis (LFDA) for constructing a discriminative subspace for achieving both accuracy and computational efficiency in NN classification. Through experiments, we confirmed that LFDCH achieved faster and more accurate classification than classification methods using PCH or ordinary NN.

Region matching - finding conjugate regions on a pair of images - plays a fundamental role in computer vision. Indeed, such methods have numerous applications such as indexation, motion estimation or tracking. In the vast literature on the subject, several dissimilarity measures have been proposed in order to determine the true match for each region. In this paper, under statistical hypothesis of similarity, we provide an improved decision rule for patch matching based on significance tests and the statistical inequality of McDiarmid. The proposed decision rule allows to validate or not the similarity hypothesis and so to automatically detect matching outliers. The approach is applied to motion estimation and object tracking on noisy video sequences. Note that the proposed framework is robust against noise, avoids the use of statistical tests and may be related to the

a contrario

approach.

Given a 3D binary voxel-based digital object

V

, an algorithm for computing homological information for

V

via a polyhedral cell complex is designed. By homological information we understand not only Betti numbers, representative cycles of homology classes and homological classification of cycles but also the computation of homology numbers related additional algebraic structures defined on homology (coproduct in homology, product in cohomology, (co)homology operations,...). The algorithm is mainly based on the following facts: a) a local 3D-polyhedrization of any 2×2×2 configuration of mutually 26-adjacent black voxels providing a coherent cell complex at global level; b) a description of the homology of a digital volume as an algebraic-gradient vector field on the cell complex (see Discrete Morse Theory [5], AT-model method [7,5]). Saving this vector field, we go further obtaining homological information at no extra time processing cost.

Watching athletes allows coaches to provide both vital feedback on how well they are performing and on ways to improve their technique without causing or aggravating injuries. The thoroughness and accuracy of this traditional observation method are limited by human ability and availability. Supplementing coaches with sensor systems that generate accurate feedback on any technical aspect of the performance gives athletes a fall back if they do not have enough confidence in their coach’s assessment.

A system is presented to model the quality of arbitrary aspects of rowing technique found to be inconsistently well performed by a set of novice rowers when using an ergometer. Using only the motion of the handle, tracked using a high-fidelity motion capture system, a coach trains the system with their idea of the skill-level exhibited during each performance, by labeling example trajectories. Misclassification of unseen performances is encouragingly low, even for unknown performers.

In this paper, we address the problem of photometric invariance in multispectral imaging making use of an optimisation approach based upon the dichromatic model. In this manner, we can cast the problem of recovering the spectra of the illuminant, the surface reflectance and the shading and specular factors in a structural optimisation setting. Making use of the additional information provided by multispectral imaging and the structure of image patches, we recover the dichromatic parameters of the scene. Thus, we formulate a target cost function combining the dichromatic error and the smoothness priors for surfaces with uniform reflectance. The dichromatic parameters are recovered through minimising this cost function in a coordinate descent manner. To this end, we make use of regular albedo patches in the scene selected automatically. The algorithm is shown to be robust, and since the cost function is convex in nature, the resulting solution is globally optimal. We illustrate the effectiveness of our method for purposes of illuminant spectrum recovery and skin recognition. We also compare our results to a number of alternatives.

Unsupervised image segmentation is of essential relevance for many computer vision applications and remains a difficult task despite of decades of intensive research. In particular, the parameter selection problem has not received the due attention in the past. Researchers typically claim to have empirically fixed the parameter values or train in advance based on manual ground truth. These approaches are not optimal and lack an adaptive behavior in dealing with a particular image. In this work we adopt the ensemble combination principle to solve the parameter selection problem in image segmentation. It explores the parameter space without the need of ground truth. The experimental results including a comparison with ground truth based training demonstrate the effectiveness of our framework.

We describe an annotation and retrieval framework that uses a semantic image representation by contextual modeling of images using occurrence probabilities of concepts and objects. First, images are segmented into regions using clustering of color features and line structures. Next, each image is modeled using the histogram of the types of its regions, and Bayesian classifiers are used to obtain the occurrence probabilities of concepts and objects using these histograms. Given the observation that a single class with the highest probability is not sufficient to model image content in an unconstrained data set with a large number of semantically overlapping classes, we use the concept/object probabilities as a new representation, and perform retrieval in the semantic space for further improvement of the categorization accuracy. Experiments on the TRECVID and Corel data sets show good performance.

We constructed a multi-angle view, illumination and cosmetic facial image database (MaVIC) for quantitative characterization of facial appearance. The facial images in the database are captured from various angles of view and of illumination with a multi-angle image capturing system (MICS). In MaVIC, there are 170 Japanese female’s natural facial images and 250 Japanese female’s cosmetic facial images. Each subject was photographed in 13 different view-directions under 14 illuminations. Quantitative analysis has been done for the images in MaVIC by the use of principal component analysis (PCA).

We propose a powerful shape representation to recognize sketches drawn on a pen-based input device. The proposed method is robust to the sketching order by using the combination of distance map and direction histogram. A distance map created after normalizing a freehand sketch represents a spatial feature of shape regardless of the writing order. Moreover, a distance map which acts a spatial feature is more robust to shape variation than chamfer distance. Direction histogram is also able to extract a directional feature unrelated to the drawing order by using the alignment of the spatial location between two neighboring points of the stroke. The combination of these two features represents rich information to recognize an input sketch. The experiment result demonstrates the superiority of the proposed method more than previous works. It shows 96% recognition performance for the experimental database, which consists of 28 freehand sketches and 10 on-line handwritten digits.

Due to its robustness to outliers, many Pattern Recognition algorithms use the

median

as a representative of a set of points. A special case arises in Syntactical Pattern Recognition when the points (prototypes) are represented by strings. However, when the edit distance is used, finding the median becomes a NP-Hard problem. Then, either the search is restricted to strings in the data (

set-median

) or some heuristic approach is applied. In this work we use the (conditional) stochastic edit distance instead of the plain edit distance. It is not yet known if in this case the problem is also NP-Hard so an approximation algorithm is described. The algorithm is based on the extension of the string structure to multistrings (strings of stochastic vectors where each element represents the probability of each symbol) to allow the use of the Expectation Maximization technique. We carry out some experiments over a chromosomes corpus to check the efficiency of the algorithm.

Tracking of spatially extended targets with variable shape, pose and appearance is a highly challenging task. In this work we propose a novel tracking approach using an incrementally generated part-based description to obtain a specific representation of target structure. The hierarchical part-based representation is learned in a generative manner from a large set of simple local features. The spatial and temporal density of observed part combinations is estimated by performing statistics over temporally aggregated data. Detected stable combinations consisting of multiple simpler parts encompass local, specific structures, which can efficiently guide a spatio-temporal association step of coherently moving image regions, which are part of the same target. The concept of our approach is proved and evaluated in several experiments.

Dynamic weather effects such as rain cause rapid, distracting motion in a video sequence. This paper aims to remove rain and similar effects from video footage using a multi-step approach; Regions are identified as being potentially affected by rain if they exhibit a short-duration intensity spike. Falling rain drops are imaged by a video camera in a predictable way, as a streak with a consistent range of possible aspect ratios. To preserve scene motion, regions identified by this criterion are investigated, and those that do not fit into the expected range of aspect ratios are ignored. Information about the direction of rainfall is also used to reduce false detections. The effectiveness of this technique is shown on a number of video sequences. The method presented provides advantages over existing techniques.

Error correcting output coding is a well known technique to decompose a multi-class classification problem into a group of two-class problems which can be faced by using a combination of binary classifiers. Each of them is trained on a different dichotomy of the classes. The way the set of classes is mapped on this set of dichotomies may essentially influence the obtained performance. In this paper we present a new tool, the

k

-NN lookup table to optimize this mapping in a fast way and a fast procedure to change the dichotomies in a proper way. Experiments on artificial and public data sets show that the proposed procedure may significantly improve the ECOC performance in multi-class problems.

We propose a novel algorithm to improve the ensemble performance of AdaBoost. The main contribution in our algorithm includes two aspects: (1) we aim to generate a distribution at each step that has less correlation with the previous classifiers so as to enhance the searching efficiency for new classifiers; (2) the classifiers weights can be iteratively modified along with the training process. In the proposed algorithm, the distribution is required to be corrective to some previous classifiers or some previous classifiers’ linear combinations. Experiments on UCI Repository have validated the new algorithm’s effectiveness.

In this paper, we address the problem of selecting and fusing similarity measures based classifiers in LDA face space. The performance of a face verification system in an LDA feature space using different similarity measure based classifiers is experimentally studied first. The study is performed for both manually and automatically registered face images. A sequential search approach which is in principle similar to the ”plus L and take away R” algorithm is then applied in order to find an optimum subset of the adopted classifiers. The selected classifiers are combined using the SVM classifier. We show that although, individually, one of the adopted scoring functions, the Gradient Direction distance outperforms the other metrics, by fusing different similarity measures using the proposed method, the resulting decision making scheme improves the performance of the system in different conditions.

In this paper, we propose a new method for training mixtures of linear SVM classifiers for purposes of non-linear data classification. We do this by packaging linear SVMs into a probabilistic formulation and embedding them in the mixture of experts model. The weights of the mixture model are generated by the gating network dependent on the input data. The new mixture of linear SVMs can be then trained efficiently using the EM algorithm. Unlike previous SVM-based mixture of expert models, which use a divide-and-conquer strategy to reduce the burden of training for large scale data sets, the main purpose of our approach is to improve the efficiency for testing. Experimental results show that our proposed model can achieve the efficiency of linear classifiers in the prediction phase while still maintaining the classification performance of nonlinear classifiers.

In many security applications a pattern recognition system faces an

adversarial classification

problem, in which an intelligent, adaptive adversary modifies patterns to evade the classifier. Several strategies have been recently proposed to make a classifier harder to evade, but they are based only on qualitative and intuitive arguments. In this work, we consider a strategy consisting in hiding information about the classifier to the adversary through the introduction of some randomness in the decision function. We focus on an implementation of this strategy in a multiple classifier system, which is a classification architecture widely used in security applications. We provide a formal support to this strategy, based on an analytical framework for adversarial classification problems recently proposed by other authors, and give an experimental evaluation on a spam filtering task to illustrate our findings.

We propose a strategy for updating the learning rate parameter of online linear classifiers for streaming data with concept drift. The change in the learning rate is guided by the change in a running estimate of the classification error. In addition, we propose an online version of the standard linear discriminant classifier (O-LDC) in which the inverse of the common covariance matrix is updated using the Sherman-Morrison-Woodbury formula. The adaptive learning rate was applied to four online linear classifier models on generated and real streaming data with concept drift. O-LDC was found to be better than balanced Winnow, the perceptron and a recently proposed online linear discriminant analysis.

Any change in the classification problem in the course of online classification is termed changing environments. Examples of changing environments include change in the underlying data distribution, change in the class definition, adding or removing a feature. The two general strategies for handling changing environments are (i) constant update of the classifier and (ii) re-training of the classifier after change detection. The former strategy is useful with gradual changes while the latter is useful with abrupt changes. If the type of changes is not known in advance, a combination of the two strategies may be advantageous. We propose a classifier ensemble using Winnow. For the constant-update strategy we used the nearest neighbour with a fixed size window and two methods with a learning rate: the online perceptron and an online version of the linear discriminant classifier (LDC). For the detect-and-retrain strategy we used the nearest neighbour classifier and the online LDC. Experiments were carried out on 28 data sets and 3 different scenarios: no change, gradual change and abrupt change. The results indicate that the combination works better than each strategy on its own.

Learning based on kernel machines is widely known as a powerful tool for various fields of information science such as pattern recognition and regression estimation. One of central topics of kernel machines is model selection, especially selection of a kernel or its parameters. In this paper, we consider a class of kernels that forms a monotonic classes of reproducing kernel Hilbert spaces with an invariant metric and show that the kernel corresponding to the smallest reproducing kernel Hilbert space including an unknown true function gives the optimal model for the unknown true function.

Chaotic Pattern Recognition (PR) is a relatively new sub-field of PR in which a system, which demonstrates chaotic behavior under normal conditions, resonates when it is presented with a pattern that it is trained with. The Adachi Neural Network (AdNN) is a classic neural structure which has been proven to demonstrate the phenomenon of Associative Memory (AM). In their pioneering paper [1,2] , Adachi and his co-authors showed that the AdNN also emanates periodic outputs on being exposed to trained patterns. This was later utilized by Calitoiu

et al

[4,5] to design systems which possibly possessed PR capabilities. In this paper, we show that the previously reported properties of the AdNN do not adequately describe the dynamics of the system. Rather, although it possesses far more powerful PR and AM properties than was earlier known, it goes through a spectrum of characteristics as one of its crucial parameters,

α

, changes. As

α

increases, the AdNN which is first an AM become

quasi

-chaotic. The system is then distinguished by two phases which really do not have clear boundaries of demarcation. In the former of these phases it is

quasi

-chaotic for some patterns and periodic for others. In the latter of these, it exhibits properties that have been unknown (or rather, unreported) till now, namely, a PR capability (which even recognizes masked or occluded patterns) in which the network resonates sympathetically for trained patterns while it is

quasi

-chaotic for untrained patterns. Finally, the system becomes completely periodic. All these results are, to the best of our knowledge, novel.

Non-Euclidean dissimilarity measures can be well suited for building representation spaces that are more beneficial for pattern classification systems than the related Euclidean ones [1,2]. A non-Euclidean representation space is however cumbersome for training classifiers, as many statistical techniques rely on the Euclidean inner product that is missing there. In this paper we report our findings on the applicability of corrections that transform a non-Euclidean representation space into a Euclidean one in which similar or better classifiers can be trained. In a case-study based on four principally different classifiers we find out that standard correction procedures fail to construct an appropriate Euclidean space, equivalent to the original non-Euclidean one.

Feature selection is an important technique in pattern recognition. By removing features that have little or no discriminative information, it is possible to improve the predictive performance of classifiers and to reduce the measuring cost of features. In general, feature selection algorithms choose a common feature subset useful for all classes. However, in general, the most contributory feature subsets vary depending on classes relatively to the other classes. In this study, we propose a classifier as a decision tree in which each leaf corresponds to one class and an internal node classifies a sample to one of two class subsets. We also discuss classifier selection in each node.

Proposed is a histogram approach for feature selection and classification. The axes are divided into equally-spaced intervals, but the division numbers are different among axes. The main difference from similar approaches is that feature selection mechanism is embedded in the method. The optimal division is determined by an MDL criterion, so that the classifier is guaranteed to converge to the Bayes optimal classifier. We also introduce the concept of “soft feature selection” that is carried out by this method as an extension of traditional “feature selection.”

We describe a dimensionality reduction method based on data point projection in an output space obtained by embedding the Growing Hierarchical Self Organizing Maps (GHSOM) computed from a training data-set. The dimensionality reduction is used in a similarity search framework whose aim is to efficiently retrieve similar objects on the basis of the Euclidean distance among high dimensional feature vectors projected in the reduced space. This research is motivated by applications aimed at performing Document Image Retrieval in Digital Libraries. In this paper we compare the proposed method with other dimensionality reduction techniques evaluating the retrieval performance on three data-sets.

In this paper, we present a novel incremental algorithm for principal component analysis (PCA). The proposed algorithm is a kind of covariance-free type algorithm which requires less computation and storage space in finding out the eigenvectors, than other incremental PCA methods using a covariance matrix. The major contribution of this paper is to explicitly deal with the changing mean and to use a Gram-Schmidt Orthogonalization (GSO) for enforcing the orthogonality of the eigenvectors. As a result, more accurate eigenvectors can be found with this algorithm than other algorithms. The performance of the proposed algorithm is evaluated by experiments on the data sets with various properties and it is shown that the proposed method can find out the eigenvectors more closer to those of batch algorithm than the others.

Optimal

multilevel thresholding is a quite important problem in image segmentation and pattern recognition. Although efficient algorithms have been proposed recently, they do not address the issue of irregularly sampled histograms. A

polynomial-time

algorithm for multilevel thresholding of irregularly sampled histograms is proposed. The algorithm is polynomial not just on the number of bins of the histogram,

n

, but also on the number of thresholds,

k

, i.e. it runs in

Θ

(

kn

2

). The proposed algorithm is general enough for a wide range of thresholding and clustering criteria, and has the capability of dealing with irregularly sampled histograms. This implies important consequences on pattern recognition, since optimal clustering in the one-dimensional space can be obtained in polynomial time. Experiments on synthetic and real-life histograms show that for typical cases, the proposed algorithm can find the optimal thresholds in a fraction of a second.

Clustering is one of the most important task in pattern recognition. For most of partitional clustering algorithms, a partition that represents as much as possible the structure of the data is generated. In this paper, we adress the problem of finding the optimal number of clusters from data. This can be done by introducing an index which evaluates the validity of the generated fuzzy

c

-partition. We propose to use a criterion based on the fuzzy combination of membership values which quantifies the

l

-order overlap and the intercluster separation of a given pattern.

When patterns are represented as histograms, the

earth mover’s distance

,

EMD

has been considered an excellent metric between two distributions. EMD is formulated as the transportation problem which is a hard optimization problem. In similarity based pattern retrieval problems, computing

EMD

s for all histograms in the database against a query histogram would take too long time for users to wait for the output. Hence, the candidate selection technique is presented to speed up the

EMD

based multivariate ordinal type histogram retrieval problem. It guarantees to find all similar histograms while achieving significant speed up. Theoretical relationships between other metrics for multivariate histograms and their usages are presented as well.

Comparing two distributions is of fundamental importance to statistics and pattern recognition. The

earth mover’s distance

(

EMD

) has been considered an excellent distance measure between two distributions. It is defined to minimize the cost using a given cost matrix and formulated as the transportation problem which is a hard optimization problem. There are three special type cost matrices where efficient algorithms are known: nominal, ordinal, and modulo. Here the problem of identifying whether a given cost matrix has the shuffled ordinal property is considered and if so, the linear time complexity algorithm can be applied to compute the

EMD

efficiently.

This work faces the problem of 3D shape clustering when the whole surface information is available. The key of our method is to use a flexible feature, called Cone-Curvature, which provides local and extended information around every node of the mesh that represents the object. Thus as we increase the region around a node a new order of CC can be calculated. This feature, which was originally defined on spherical representation, has been adapted to work with standard triangular meshes and it is used for defining a similarity measure between shapes. Through a PCA technique, the dimensionality of the shape representation is drastically reduced and the hierarchical grouping can be efficiently carried out. This method has been tested under real conditions for a wide set of free shapes yielding promising results. We present a discussion of the clustering comparing human and computer results.

The aim of this paper is to present a dissimilarity measure strategy by which a new philosophy for pattern classification pertaining to dissimilarity-based classifiers (DBCs) can be efficiently implemented. Proposed by Duin and his co-authors, DBCs are a way of defining classifiers among classes; they are not based on the feature measurements of individual patterns, but rather on a suitable dissimilarity measure among the patterns. The problem with this strategy is that we need to measure the inter-pattern dissimilarities for all the training samples to ensure there is no zero distance between objects of different classes. Consequently, the classes do not overlap, and therefore, the lower error bound is zero. In image classification tasks, such as face recognition, one of the most intractable problems is the distortion and lack of information caused by the differences in face directions and sizes. To overcome the above problem, in this paper, we propose a new method of measuring the dissimilarity distance between two images of an object when the images have different directions and sizes and there is no direct feature correspondence. In the proposed method, a dynamic programming technique, such as dynamic time warping, is used to overcome the limitation of one-to-one mapping. Furthermore, when determining the matching templates of two images in dynamic time warping, we use a correlation coefficient-based method. With this method, we can find an optimal warping path by surveying the images in a one-dimensional or two-dimensional way (that is, with vertical-only scanning or vertical-horizontal scanning). Our experimental results demonstrate that the proposed mechanism can improve the classification accuracy of conventional approaches for an artificial data set and two real-life benchmark databases.

In this paper, we perform gender classification based on facial surface normals (facial needle-maps). We improve our previous work in [6] by using a non-Lambertian Shape-from-Shading (SFS) method to recover the surface normals, and develop a novel supervised principal geodesic analysis (PGA) to parameterize the facial needle-maps. Experimental results demonstrate the feasibility of gender classification based on facial needle-maps, and shows that incorporating pairwise relationships between the labeled data improves the gender discriminating powers in the leading PGA eigenvectors and gender classification accuracy.

Biometric systems are automated methods based on physical or behavioral characteristics of an individual for determining her/his identity. An important aspect of these systems is the reliability against forgery that is surely improved when using multiple sources of biometric information. In such cases combination rules can be applied to fuse the different scores thus obtaining a

multibiometric system

.

In this paper we analyze a method based on margin maximization for building a linear combination of biometric scores. The margin is a central concept in machine learning research and several theoretical results exist which show that improving the margin on the training set is beneficial for the generalization error of an ensemble of classifiers. Experiments performed on real biometric data and comparisons with other commonly employed fusion rules show that a combination based on margin maximization is particularly effective with respect to other established fusion methods.

Current methods for automatic template update are aimed at capturing large intra-class variations of input data and at the same time restricting the probability of impostor’s introduction in client’s galleries. These automatic methods avoid the costs of supervised update methods, which are due to repeated enrollment sessions and manual assignment of identity labels. Most of state-of-the-art template update approaches add input patterns to the claimed identity’s gallery on the basis of their matching score with the existing templates, which must be above a very high “updating” threshold. However, regardless of the value of such updating threshold, update errors do exist and impact strongly on the effectiveness of update procedures. The introduction of impostors into the galleries may degrade the performance quickly. This effect has not been studied in the literature so far. Therefore, a first experimental investigation is the goal of this paper, with a case study on a face verification system.

This paper addresses the problem of fully automatic matching two triangulated surface meshes. In this paper, a similarity measurement is constructed to measure the consistency of the constraints among the correspondent landmarks, which is rigid transformation immune and robust to nonrigid deformations. The matching problem is then solved by directly finding correspondence between the landmarks of the two surfaces by graphical model based Bayesian inference. In order to reduce the computational complexity and to accelerate the convergence, a hierarchical graphical model is constructed which enables mutual registration and information exchange between the two surfaces during registration. Experiments on randomly generated instances from a PCA based statistical model of proximal femurs verified the proposed approach.

We consider the problem of automatically classifying videos into predefined categories based on the analysis of their audio contents. In detail, given a set of labeled videos (such as news, sitcoms, sports, etc.), our objective is to classify a new video into one of these categories. To solve this problem, a novel audio features based video classification method combining an unsupervised generative model named probabilistic Latent Semantic Analysis (pLSA) with a multi-class discriminative classifier is proposed. Since general audio signals usually show complicated distribution in the feature space, k-means clustering method is firstly used to group temporal signal segments with similar low-level features into natural clusters, which are adopted as “audio words”. Then, the audio stream of a video is decomposed into a bag of “audio words”. To classify those bags of “audio words” which extracted from videos, latent “topics” are discovered by pLSA, and subsequently, training a multi-class classifier on the “topic” distribution vector for each video. Encouraging classification results have been achieved in our experiments.

Various forms of additive modeling techniques have been popularly used in many pattern recognition and machine learning related applications. The efficiency of any additive modeling technique relies significantly on the choice of the weak learner and the form of the loss function. In this paper, we propose a novel scale-space kernel based approach for additive modeling. Our method applies a few insights from the well-studied scale-space theory for choosing the optimal learners during different iterations of the boosting algorithms, which are simple yet powerful additive modeling methods. For each iteration of the additive modeling, weak learners that can best fit the current resolution of the data are chosen and then increase the resolution systematically. We demonstrate the results of the proposed framework on both synthetic and real datasets taken from the UCI machine learning repository. Though demonstrated specifically in the context of boosting algorithms, our approach is generic enough to be accommodated in general additive modeling techniques. Similarities and distinctions of the proposed algorithm with the popularly used radial basis function networks and wavelet decomposition method are also discussed.

In Multiple Instance Learning (MIL) problems, objects are represented by a

set

of feature vectors, in contrast to the standard pattern recognition problems, where objects are represented by a single feature vector. Numerous classifiers have been proposed to solve this type of MIL classification problem. Unfortunately only two datasets are standard in this field (MUSK-1 and MUSK-2), and all classifiers are evaluated on these datasets using the standard classification error. In practice it is very informative to investigate their learning curves, i.e. the performance on train and test set for varying number of training objects. This paper offers an evaluation of several classifiers on the standard datasets MUSK-1 and MUSK-2 as a function of the training size. This suggests that for smaller datasets a Parzen density estimator may be preferrer over the other ’optimal’ classifiers given in the literature.

In this paper, we propose a holistic classification scheme for different room types, like office or meeting room, based on 3D features. Such a categorization of scenes provides a rich source of information about potential objects, object locations, and activities typically found in them. Scene categorization is a challenging task. While outdoor scenes can be sufficiently characterized by color and texture features, indoor scenes consist of human-made structures that vary in terms of color and texture across different individual rooms of the same category. Nevertheless, humans tend to have an immediate impression in which room type they are. We suggest that such a decision could be based on the coarse spatial layout of a scene. Therefore, we present a system that categorizes different room types based on 3D sensor data extracted by a Time-of-Flight (ToF) camera. We extract planar structures combining region growing and RANSAC approaches. Then, feature vectors are defined on statistics over the relative sizes of the planar patches, the angles between pairs of (close) patches, and the ratios between sizes of pairs of patches to train classifiers. Experiments in a mobile robot scenario study the performance in classifying a room based on a single percept.

In this paper, we consider the problem of template selection in biometric systems as analogous to the problem, called “editing”, of selecting representative prototypes when using the 1-Nearest Neighbour classifier (NN). Four editing algorithms are used and compared by experiments with state-of-the-art template selection algorithms. Experiments are performed on a benchmark face data set. Reported results show pros and cons of editing algorithms for template selection in biometric systems.

Indexing is the process of assigning a numerical value to a database entry in order to facilitate its rapid retrieval. Indexing a fingerprint database can reduce the search space and improve the response time of an identification system. We discuss a novel method for generating index codes for fingerprint images by using a small set of pre-determined

reference

fingerprints. In the proposed method, the match scores generated by comparing an input fingerprint with the reference fingerprints are subjected to a discretization function, which converts them into an index code. A search mechanism based on the Hamming distance identifies those index codes in the database that are similar to the code of the input image. The proposed technique has several advantages: it obviates the need to extract complex features from the fingerprint image; it utilizes the matcher that is already associated with a particular application; and it can be used to index any biometric database irrespective of the trait or matcher being used. Experimental results on two fingerprint databases (NIST-4 and WVU) indicate that the proposed encoding scheme generates index codes that are well-scattered thereby allowing noisy query images to be indexed correctly.

Template update in biometric recognition system is aimed to improve the representativeness of available templates in order to make them adaptive to the large intra-class variations characterizing biometrics (e.g. fingerprints and faces). Among others, semi-supervised approaches to template update have been recently proposed. Since the lack of representativeness is due to the impossibility of sampling all possible variations of a given client biometric, these approaches exploit samples submitted during the recognition phase by adding the “highly genuine” ones to the related client gallery. In particular, the template co-update algorithm, which uses the mutual help of two complementary biometric matchers, has shown promising experimental results. However, no theoretical model has been proposed to explain the behaviour of the co-update algorithm and support the experimental results. This is the goal of this paper. Experimental results show the correctness of the proposed theoretical model.

When locality preserving projection (LPP) method was originally proposed, it takes as the LPP solution the minimum eigenvalue solution of an eigenequation. After that, LPP has been used for image recognition problems such as face recognition. However, almost no researcher realizes that LPP usually encounters several difficulties when applied to the image recognition problem. For example, since image recognition problems are usually small sample size (SSS) problems, the corresponding eigenequation cannot be directly solved. In addition, it seems that even if one can obtain the solution of the eigenequation by using the numerical analysis approach, the obtained conventional LPP solution might produce the ‘presentation confusion’ problem for samples from different classes, which is disadvantageous for the classification to procedure a high accuracy. In this paper we first thoroughly investigate the characteristics and drawbacks of the conventional LPP solution in the small sample size (SSS) problem in which the sample number is smaller than the data dimension. In order to overcome these drawbacks, we propose a new LPP solution for the SSS problem, which has clear physical meaning and can be directly and easily worked out because it is generated from a non-singular eigenequation. Experimental results the proposed solution scheme can produce a much lower classification error rate than the conventional LPP solution.

High occupancy vehicles lanes (HOV) are highway lanes usually reserved to vehicles carrying at least two persons. They are designed to help move more people though congested areas. In this context, automatic passenger counting systems could be useful to grant access to or to control vehicles in those lanes.

In this work, we propose a real-time passenger detection system based on the analysis of visual images. Each person is detected by mixing the information from different types of classifiers in order to make the detection process faster and more robust.

A new approach for the automatic detection of drug-induced organ toxicities based on Nuclear Magnetic Resonance Spectroscopy data from biofluids is presented in this paper. Spectral data from biofluids contain information on the concentration of various substances, but the combination of only a small subset of these cues is putatively useful for classification of new samples. We propose to divide the spectra into several short regions and train classifiers on them, using only a limited amount of information for class discrimination. These

local experts

are combined in an ensemble classification system and the subset of experts for the final classification is optimized automatically. Thus, only local experts for relevant spectral regions are used for the final ensemble classification. The proposed approach has been evaluated on a real data-set from industrial pharmacology, showing an improvement in classification accuracy and indicating relevant spectral regions for classification.

In recent years, many approaches for achieving high performance by combining some classifiers have been proposed. We exploit many random replicates of samples in the bagging, and randomly chosen feature subsets in the random subspace method. In this paper, we introduce a method for selecting both samples and features at the same time and demonstrate the effectiveness of the method. This method includes a parametric bagging and a parametric random subspace method as special cases. In some experiments, this method and the parametric random subspace method showed the best performance.

In Pattern Recognition, there are problems where distinct representations can be obtained for the same pattern, and depending on the type of classifiers (statistical or structural) one type of representation is preferred versus the others. In the last years, different approaches to combining classifiers have been proposed to improve the performance of individual classifiers. However, few works investigated the use of structured pattern representations. In this paper combination of classifiers has been applied using tree pattern representation in combination with strings and vectors for a handwritten character classification task. In order to save computational cost, some proposals based on the use of both embedding structured data and refine and filter framework are provided.

The combination of different experts is largely used to improve the performance of a pattern recognition system. In the case of experts whose output is a similarity score, different methods had been developed. In this paper, the combination is performed by building a similarity score space made up of the scores produced by the experts, and training a classifier into it. Different techniques based on the use of classifiers trained on the similarity score space are proposed and compared. In particular, they are used in the framework of Dynamic Score Selection mechanisms, recently proposed by the authors. Reported results on two biometric datasets show the effectiveness of the proposed approach.

This paper reports about the development of a NER system in Bengali by combining outputs of the classifiers such as Maximum Entropy (ME), Conditional Random Field (CRF) and Support Vector Machine (SVM). The training set consists of approximately 250K wordforms and has been manually annotated with the four major named entity (NE) tags such as

Person

,

Location

,

Organization

and

Miscellaneous

tags. The classifiers make use of the different contextual information of the words along with the variety of features that are helpful in predicting the various NE classes. Lexical context patterns, which are generated from an unlabeled corpus of 1 million wordforms in a semi-automatic way, have been used as the features of the classifiers in order to improve their performance. In addition, we have used the second best tags of the classifiers and applied several heuristics to improve the performance. Finally, the classifiers are combined using a majority voting approach. Experimental results show the effectiveness of the proposed approach with the overall average recall, precision, and f-score values of 90.78%, 87.35%, and 89.03%, respectively, which shows an improvement of 11.8% in f-score over the best performing SVM based

baseline

system and an improvement of 15.11% in f-score over the least performing ME based

baseline

system. The proposed system also outperforms the other existing Bengali NER system.

In this paper, we present some results on multimodality implementation resulting from the VINSI (“Vérification d’Identité Numérique Sécurisée Itinérante” for Secured Mobile Digital Identity Verification) French project. The VINSI handheld terminal allows identity verification in mobile conditions (airport gates) using two biometrics usable in future biometric passports (fingerprint and face). We propose an incremental fusion strategy aiming at improving the global performance of the combined system over each individual recognizer while optimizing the cost resulting from the fusion. Indeed, in this kind of application, time and complexity optimization is essential. To this aim, we split the fingerprint scores’ range into different interest zones, on which we do not apply the same strategy depending on the relative quality of the modalities at hand. Results on a virtual database corresponding to VINSI applicative conditions (Combination of BIOMET fingerprints and FRGCv2 faces) show that this incremental fusion strategy allows the same improvement in performance as global fusion methods while significantly reducing the cost.

In the field of financial time series analysis it is widely accepted that the returns (price variations) are unpredictable in the long period [1]; nevertheless, this unappealing constraint could be somehow relaxed if

sufficiently short

time intervals are considered. In this paper this alternative scenario is investigated with a novel methodology, aimed at analyzing short (local) financial trends for predicting their sign (increase or decrease). This peculiar problem needs specific models – different from standard techniques used for estimating the volatility or the returns – able to capture the asymmetries between increase and decrease periods in the short time. This is achieved by modeling directly the signs of the local trends using

two

separate Hidden Markov models, one for positive and one for negative trends. The approach has been tested with different financial indexes, with encouraging results also in comparison with standard methods.

We first investigate the combined effect of data complexity, curse of dimensionality and the definition of the Euclidean distance on the distance measure between points. Then, based on the concepts underlying manifold learning algorithms and the minimum volume ellipsoid metric, we design an algorithm that learns a local metric on the lower dimensional manifold on which the data is lying. Experiments in the context of classification on standard benchmark data sets showed very promising results when compared to state of the art algorithms, and consistent improvements over the Euclidean distance in the context of query–based learning.

In these years, we often deal with an enormous amount of data or a data stream in a large variety of pattern recognition tasks. As a promising approach for economising the amount, we have previously defined

a volume prototype

as a geometric configuration that represents some data points inside and proposed a single-pass algorithm for finding them. In this paper, we analyze the convergence behavior of volume prototypes in high-dimensional cases. In addition, we show the applicability of volume prototypes to high-dimensional classification problems.

The assignment of an IP flow to a class, according to the application that generated it, is at the basis of any modern network management platform. However, classification techniques such as the ones based on the analysis of transport layer or application layer information are rapidly becoming ineffective. Moreover, in several network scenarios it is quite unrealistic to assume that all the classes an IP flow can belong to are

a priori

known. In these cases, in fact, some network protocols may be known, but novel protocols can appear so giving rise to

unknown

classes.

In this paper we propose to face the problem of classifying IP flows by means of different pattern recognition approaches. They have been explicitly devised in order to effectively address the problem of the

unknown

classes, too. An experimental evaluation of the various proposal on real traffic traces is also provided, by considering different network scenarios.

Gaussian process classifiers (GPCs) are a fully statistical model for kernel classification. We present a form of GPC which is robust to labeling errors in the data set. This model allows label noise not only near the class boundaries, but also far from the class boundaries which can result from mistakes in labelling or gross errors in measuring the input features. We derive an outlier robust algorithm for training this model which alternates iterations based on the EP approximation and hyperparameter updates until convergence. We show the usefulness of the proposed algorithm with model selection method through simulation results.

In this paper a novel approach to contour-based 2D shape recognition is proposed. The main idea is to characterize the contour of an object using the multifractional Brownian motion (mBm), a mathematical method able to capture the local self similarity and long-range dependence of a signal. The mBm estimation results in a sequence of Hurst coefficients, which we used to derive a fixed size feature vector. Preliminary experimental evaluations using simple classifiers with these feature vectors produce encouraging results, also in comparison with the state of the art.

In this paper, we introduce a new approach to evaluate and visualize the classifier performance in two-class imbalanced domains. This method defines a two-dimensional space by combining the geometric mean of class accuracies and a new metric that gives an indication of how balanced they are. A given point in this space represents a certain trade-off between those two measures, which will be expressed as a trapezoidal function. Besides, this evaluation function has the interesting property that it allows to emphasize the correct predictions on the minority class, which is often considered as the most important class. Experiments demonstrate the consistency and validity of the evaluation method here proposed.

Nearest neighbour search is a simple technique widely used in Pattern Recognition tasks. When the dataset is large and/or the dissimilarity computation is very time consuming the brute force approach is not practical. In such cases, some properties of the dissimilarity measure can be exploited in order to speed up the search. In particular, the metric properties of some dissimilarity measures have been used extensively in fast nearest neighbour search algorithms to avoid dissimilarity computations. Recently, a distance table based pruning rule to reduce the average number of distance computations in hierarchical search algorithms was proposed. In this work we show the effectiveness of this rule compared to other state of the art algorithms. Moreover, we propose some guidelines to reduce the space complexity of the rule.

In many vision problems, instead of having fully annotated training data, it is easier to obtain just a subset of data with annotations, because it is less restrictive for the user. For this reason, in this paper, we consider especially the problem of classifying weakly-annotated images, where just a small subset of the database is annotated with keywords. In this paper we present and evaluate a new method which improves the effectiveness of content-based image classification, by integrating semantic concepts extracted from text, and by automatically extending annotations to the images with missing keywords. Our model is inspired from the probabilistic graphical model theory: we propose a hierarchical mixture model which enables to handle missing values. Results of visual-textual classification, reported on a database of images collected from the Web, partially and manually annotated, show an improvement by 32.3% in terms of recognition rate against only visual information classification. Besides the automatic annotation extension with our model for images with missing keywords outperforms the visual-textual classification by 6.8%. Finally the proposed method is experimentally competitive with the state-of-art classifiers.

An approach to automatically extract pertinent subsets of soft output classifiers, assumed to decision rules, is presented in this paper. They are aggregated into a global decision scheme using the Choquet integral. A selection scheme is defined that discards weak or redundant decision rules, keeping only the most relevant subset. An experimental study, based on real world data attest the interest of our method.

Stability (robustness) of feature selection methods is a topic of recent interest. Unlike other known stability criteria, the new consistency measures proposed in this paper evaluate the overall occurrence of individual features in selected subsets of possibly varying cardinality. The new measures are compared to the generalized Kalousis measure which evaluates pairwise similarities between subsets. The new measures are computationally very effective and offer more than one type of insight into the stability problem. All considered measures have been used to compare two standard feature selection methods on a set of examples.

In many practical situations it is not feasible to collect labeled samples for all available classes in a domain. Especially in supervised classification of remotely sensed images it is impossible to collect ground truth information over large geographic regions for all thematic classes. As a result often analysts collect labels for aggregate classes. In this paper we present a novel learning scheme that automatically learns sub-classes from the user given aggregate classes. We model each aggregate class as finite Gaussian mixture instead of classical assumption of unimodal Gaussian per class. The number of components in each finite Gaussian mixture are automatically estimated. Experimental results on real remotely sensed image classification showed not only improved accuracy in aggregate class classification but the proposed method also recognized sub-classes.

An empirical evaluation of linear and kernel common vector based approaches has been considered in this work. Both versions are extended by considering directions (attributes) that carry out very little information as if they were null. Experiments on different kinds of data confirm that using this as a regularization parameter leads to usually better (and never worse) results than the basic algorithms.