As biomedical data in 3D space collected increasingly, there is a pressing need for efficient and accurate applications in the field of bioinformation analysis. For biomedical purpose, mesh subdivision techniques are commonly used to generate adaptive multi-resolution meshes for fast or accurate algorithms. However, current smoothing methods for each subdivision algorithm will moderate edge and vertex features from the original mesh. In this paper, we propose a feature preserved mesh subdivision framework, which generates a visually sensitive and a more precise result compared with commonly used subdivision methods, to preserve edge and vertex geometrical features of biomedical data.

Drosophila embryonic images provide valuable spatial and temporal information of gene expression. Extraction of the contour of a targeting embryo in an embryonic image is a fundamental step of a computational system for the study of gene-gene interaction on Drosophila. In this paper, we propose a shape model for contour extraction of Drosophila embryos. The shape model is built on connected components of edge pixels. It approximates a connected component of edge pixels by a polygon that can be either convex or concave. The main contribution of the proposed shape model is its ability of segmenting embryos touching each other. Moreover, the proposed shape model is adaptable to a wide range of applications on contour extraction.

In this paper, we propose a leg-driven physiology framework for pedestrian detection. The framework is introduced to reduce the search space of candidate regions of pedestrians. Given a set of vertical line segments, we can generate a space of rectangular candidate regions, based on a model of body proportions. The proposed framework can be either integrated with or without learning-based pedestrian detection methods to validate the candidate regions. A symmetry constraint is then applied to validate each candidate region to decrease the false positive rate. The experiment demonstrates the promising results of the proposed method by comparing it with Dalal & Triggs method. For example, rectangular regions detected by the proposed method has much similar area to the ground truth than regions detected by Dalal & Triggs method.

Rectangular shape detection has a wide range of applications, such as license plate detection, vehicle detection and building detection. In this paper, we propose a robust framework for rectangular shape detection based on the channel-scale space of RGB images. The framework consists of algorithms developed to address two issues of a shape attention (i.e., a connected component of edge points), including: i) openness and ii) fragmentation. Furthermore, we propose an interestness measure for rectangular shapes by integrating interest points Our case study on license plate detection shows the promise of the proposed framework.

Contour extraction of Drosophila (fruit fly) embryos is an important step to build a computational system for matching expression pattern of embryonic images to assist the discovery of the nature of genes. Automatic contour extraction of embryos is challenging due to severe image variations, including 1) the size, orientation, shape, and appearance of an embryo of interest; 2) the neighboring context of an embryo of interest (such as nontouching and touching neighboring embryos); and 3) illumination circumstance. In this paper, we propose an automatic framework for contour extraction of the embryo of interest in an embryonic image. The proposed framework contains three components. Its first component applies a mixture model of quadratic curves, with statistical features, to initialize the contour of the embryo of interest. An efficient method based on imbalanced image points is proposed to compute model parameters. The second component applies active contour model to refine embryo contours. The third component applies eigen-shape modeling to smooth jaggy contours caused by blurred embryo boundaries. We test the proposed framework on a data set of 8,000 embryonic images, and achieve promising accuracy (88 percent), that is, substantially higher than the-state-of-the-art results.

Contour extraction of Drosophila (fruit fly) embryos is an important step to build a computational system for matching expression pattern of embryonic images to assist the discovery of the nature of genes. Automatic contour extraction of embryos is challenging due to severe image variations, including i) the size, orientation, shape and appearance of an embryo of interest; ii) the neighboring context of an embryo of interest (such as non-touching and touching neighboring embryos); and iii) illumination circumstance. In this paper, we propose an automatic framework for contour extraction of the embryo of interest in an embryonic image. The proposed framework contains three components. Its first component applies a mixture model of quadratic curves, with statistical features, to initialize the contour of the embryo of interest. An efficient method based on imbalanced image points is proposed to compute model parameters. The second component applies active contour model to refine embryo contours. The third component applies eigen-shape modeling to smooth jaggy contours caused by blur embryo boundaries. We test the proposed framework on a dataset of 8000 embryonic images, and achieve promising accuracy (88%) that is substantially higher than the-state-of-the-art results.

Kernel methods have been applied successfully in many data mining tasks. Subspace kernel learning was recently proposed to discover an effective low-dimensional subspace of a kernel feature space for improved classification. In this paper, we propose to construct a subspace kernel using the Hilbert-Schmidt Independence Criterion (HSIC). We show that the optimal subspace kernel can be obtained efficiently by solving an eigenvalue problem. One limitation of the existing subspace kernel learning formulations is that the kernel learning and classification are independent and the subspace kernel may not be optimally adapted for classification. To overcome this limitation, we propose a joint optimization framework, in which we learn the subspace kernel and subsequent classifiers simultaneously. In addition, we propose a novel learning formulation that extracts an uncorrelated subspace kernel to reduce the redundant information in a subspace kernel. Following the idea from multiple kernel learning, we extend the proposed formulations to the case when multiple kernels are available and need to be combined. We show that the integration of subspace kernels can be formulated as a semidefinite program (SDP) which is computationally expensive. To improve the efficiency of the SDP formulation, we propose an equivalent semi-infinite linear program (SILP) formulation which can be solved efficiently by the column generation technique. Experimental results on a collection of benchmark data sets demonstrate the effectiveness of the proposed algorithms.

Linear discriminant analysis (LDA) is a popular statistical approach for dimensionality reduction. LDA captures the global geometric structure of the data by simultaneously maximizing the between-class distance and minimizing the within-class distance. However, local geometric structure has recently been shown to be effective for dimensionality reduction. In this paper, a novel dimensionality reduction algorithm is proposed, which integrates both global and local structures. The main contributions of this paper include: (1) We present a least squares formulation for dimensionality reduction, which facilities the integration of global and local structures; (2) We design an efficient model selection scheme for the optimal integration, which balances the tradeoff between the global and local structures; and (3) We present a detailed theoretical analysis on the intrinsic relationship between the proposed framework and LDA. Our extensive experimental studies on benchmark data sets show that the proposed integration framework is competitive with traditional dimensionality reduction algorithms, which use global or local structure only.

Classical Linear Discriminant Analysis (LDA) is not applicable for small sample size problems due to the singularity of the scatter matrices involved. Regularized LDA (RLDA) provides a simple strategy to overcome the singularity problem by applying a regularization term, which is commonly estimated via cross-validation from a set of candidates. However, cross-validation may be computationally prohibitive when the candidate set is large. An efficient algorithm for RLDA is presented that computes the optimal transformation of RLDA for a large set of parameter candidates, with approximately the same cost as running RLDA a small number of times. Thus it facilitates efficient model selection for RLDA. An intrinsic relationship between RLDA and Uncorrelated LDA (ULDA), which was recently proposed for dimension

The study on how to represent appearance instances was the focus in most previous work in face recognition. Little attention, however, was given to the problem of how to select "good" instances for a gallery, which may be called the facial identity representation problem. This paper gives an evaluation of the identity representability of facial expressions. The identity representability of an expression is measured by the recognition accuracy achieved by using its samples as the gallery data. We use feature pixel distributions to represent appearance instances. A feature pixel distribution of an image is based on the number of occurrence of detected feature pixels (corners) in regular grids of an image plane. We propose imbalance oriented redundancy reduction for feature pixel detection. Our experimental evaluation indicates that certain facial expressions, such as the neutral, have stronger identity representability than other expressions, in various feature pixel distributions

In this paper, we present an adaptive appearance based face recognition framework that combines the efficiency of global approaches and the robustness of local approaches together. The framework uses a novel eye locator to select an appropriate scheme for appearance based recognition. The eye locator first locates eye candidates via a new strength assignment, determined by the dissimilarity between the local appearance of an image point and the appearance of its neighboring points. Then the eye locator applies a simple but flexible model (half-circle snake) to the local context of the eye candidates in order to either refine the location of an eye candidate or discard non-eye candidates. We show the performance of our framework by testing on challenging face datasets containing extreme expressions, severe occlusions, and varied lighting conditions

High-dimensional data appear in many applications of data mining, machine learning, and bioinformatics. Feature reduction is commonly applied as a preprocessing step to overcome the curse of dimensionality. Uncorrelated Linear Discriminant Analysis (ULDA) was recently proposed for feature reduction. The extracted features via ULDA were shown to be statistically uncorrelated, which is desirable for many applications. In this paper, an algorithm called ULDA/QR is proposed to simplify the previous implementation of ULDA. Then, the ULDA/GSVD algorithm is proposed, based on a novel optimization criterion, to address the singularity problem which occurs in undersampled problems, where the data dimension is larger than the sample size. The criterion used is the regularized version of the one in ULDA/QR. Surprisingly, our theoretical result shows that the solution to ULDA/GSVD is independent of the value of the regularization parameter. Experimental results on various types of data sets are reported to show the effectiveness of the proposed algorithm and to compare it with other commonly used feature reduction algorithms.

Linear Discriminant Analysis (LDA) is a well-known method for feature extraction and dimension reduction. It has been used widely in many applications involving high-dimensional data, such as image and text classification. An intrinsic limitation of classical LDA is the so-called singularity problems; that is, it fails when all scatter matrices are singular. Many LDA extensions were proposed in the past to overcome the singularity problems. Among these extensions, PCA+LDA, a two-stage method, received relatively more attention. In PCA+LDA, the LDA stage is preceded by an intermediate dimension reduction stage using Principal Component Analysis (PCA). Most previous LDA extensions are computationally expensive, and not scalable, due to the use of Singular Value Decomposition or Generalized Singular Value Decomposition. In this paper, we propose a two-stage LDA method, namely LDA/QR, which aims to overcome the singularity problems of classical LDA, while achieving efficiency and scalability simultaneously. The key difference between LDA/QR and PCA+LDA lies in the first stage, where LDA/QR applies QR decomposition to a small matrix involving the class centroids, while PCA+LDA applies PCA to the total scatter matrix involving all training data points. We further justify the proposed algorithm by showing the relationship among LDA/QR and previous LDA methods. Extensive experiments on face images and text documents are presented to show the effectiveness of the proposed algorithm.

Dimension reduction is a critical data preprocessing step for many database and data mining applications, such as efficient storage and retrieval of high-dimensional data. In the literature, a well-known dimension reduction algorithm is linear discriminant analysis (LDA). The common aspect of previously proposed LDA-based algorithms is the use of singular value decomposition (SVD). Due to the difficulty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in LDA, there has been little work on designing incremental LDA algorithms that can efficiently incorporate new data items as they become available. In this paper, we propose an LDA-based incremental dimension reduction algorithm, called IDR/QR, which applies QR decomposition rather than SVD. Unlike other LDA-based algorithms, this algorithm does not require the whole data matrix in main memory. This is desirable for large data sets. More importantly, with the insertion of new data items, the IDR/QR algorithm can constrain the computational cost by applying efficient QR-updating techniques. Finally, we evaluate the effectiveness of the IDR/QR algorithm in terms of classification error rate on the reduced dimensional space. Our experiments on several real-world data sets reveal that the classification error rate achieved by the IDR/QR algorithm is very close to the best possible one achieved by other LDA-based algorithms. However, the IDR/QR algorithm has much less computational cost, especially when new data items are inserted dynamically.

Feature extraction is important in many applications, such as text and image retrieval, because of high dimensionality. Uncorrelated Linear Discriminant Analysis (ULDA) was recently proposed for feature extraction. The extracted features via ULDA were shown to be statistically uncorrelated, which is desirable for many applications. In this paper, we will first propose the ULDA/QR algorithm to simplify the previous implementation of ULDA. Then we propose the ULDA/GSVD algorithm, based on a novel optimization criterion, to address the singularity problem. It is applicable for undersampled problem, where the data dimension is much larger than the data size, such as text and image retrieval. The novel criterion used in ULDA/GSVD is the perturbed version of the one from ULDA/QR, while surprisingly, the solution to ULDA/GSVD is shown to be independent of the amount of perturbation applied. We did extensive experiments on text and face image data to show the effectiveness of ULDA/GSVD and compare with other popular feature extraction algorithms.

Recent years have witnessed a dramatic increase in the quantity of image data collected, due to advances in fields such as medical imaging, reconnaissance, surveillance, astronomy, multimedia etc. With this increase has come the need to be able to store, transmit, and query large volumes of image data efficiently. A common operation on image databases is the retrieval of all images that are similar to a query image. For this, the images in the database are often represented as vectors in a high-dimensional space and a query is answered by retrieving all image vectors that are proximal to the query image in this space, under a suitable similarity metric. To overcome problems associated with high dimensionality, such as high storage and retrieval times, a dimension reduction step is usually applied to the vectors to concentrate relevant information in a small number of dimensions. Principal Component Analysis (PCA) is a well-known dimension reduction scheme. However, since it works with vectorized representations of images, PCA does not take into account the spatial locality of pixels in images. In this paper, a new dimension reduction scheme, called Generalized Principal Component Analysis (GPCA), is presented. This scheme works directly with images in their native state, as two-dimensional matrices, by projecting the images to a vector space that is the tensor product of two lower-dimensional vector spaces. Experiments on databases of face images show that, for the same amount of storage, GPCA is superior to PCA in terms of quality of the compressed images, query precision, and computational cost.

Dimension reduction is critical for many database and data mining applications, such as efficient storage and retrieval of high-dimensional data. In the literature, a well-known dimension reduction scheme is Linear Discriminant Analysis (LDA). The common aspect of previously proposed LDA based algorithms is the use of Singular Value Decomposition (SVD). Due to the difficulty of designing an incremental solution for the eigenvalue problem on the product of scatter matrices in LDA, there is little work on designing incremental LDA algorithms. In this paper, we propose an LDA based incremental dimension reduction algorithm, called IDR/QR, which applies QR Decomposition rather than SVD. Unlike other LDA based algorithms, this algorithm does not require the whole data matrix in main memory. This is desirable for large data sets. More importantly, with the insertion of new data items, the IDR/QR algorithm can constrain the computational cost by applying efficient QR-updating techniques. Finally, we evaluate the effectiveness of the IDR/QR algorithm in terms of classification accuracy on the reduced dimensional space. Our experiments on several real-world data sets reveal that the accuracy achieved by the IDR/QR algorithm is very close to the best possible accuracy achieved by other LDA based algorithms. However, the IDR/QR algorithm has much less computational cost, especially when new data items are dynamically inserted.

Linear Discriminant Analysis (LDA) is a well-known method for fea- ture extraction and dimension reduction. It has been used widely in many applications such as face recognition. Recently, a novel LDA algo- rithm based on QR Decomposition, namely LDA/QR, has been proposed, which is competitive in terms of classification accuracy with other LDA algorithms, but it has much lower costs in time and space. However, LDA/QR is based on linear projection, which may not be suitable for data with nonlinear structure. This paper first proposes an algorithm called KDA/QR, which extends the LDA/QR algorithm to deal with nonlin- ear data by using the kernel operator. Then an efficient approximation of KDA/QR called AKDA/QR is proposed. Experiments on face image data show that the classification accuracy of both KDA/QR and AKDA/QR are competitive with Generalized Discriminant Analysis (GDA), a gen- eral kernel discriminant analysis algorithm, while AKDA/QR has much lower time and space costs. 1 Introduction Linear Discriminant Analysis [3] is a wellknown method for dimension reduction. It has been used widely in many applications such as face recognition [2]. Classical LDA aims to find optimal transformation by minimizing the within-class distance and maximizing the between-class distance simultaneously, thus achieving maximum discrimination. The optimal transformation can be readily computed by computing the eigen-decomposition on the scatter matrices. Although LDA works well for linear problems, it may be less effective when severe non- linearity is involved. To deal with such a limitation, nonlinear extensions through kernel functions have been proposed. The main idea of kernel-based methods is to map the input data to a feature space through a nonlinear mapping, where the inner products in the feature space can be computed by a kernel function without knowing the nonlinear mapping explic- itly [9]. Kernel Principal Component Analysis (KPCA) [10], Kernel Fisher Discriminant Analysis (KFDA) [7] and Generalized Discriminant Analysis (GDA) [1] are, respectively, kernel-based nonlinear extensions of the well known PCA, FDA and LDA methods. To our knowledge, there are few efficient algorithms for general kernel based discriminant algorithms -- most known algorithms effectively scale as O(n3) where n is the sample size. In [6, 8], S. Mika et al. made a first attempt to speed up KFDA through a greedy approximation technique. However the algorithm was developed to handle the binary clas- sification problem. For multi-class problem, the authors suggested the one against the rest scheme by considering all two-class problems. Recently, an efficient variant of LDA, namely LDA/QR, was proposed in [11, 12]. The essence of LDA/QR is the utilization of QR-decomposition on a small size matrix. The time complexity of LDA/QR is linear in the size of the training data, as well as the number of dimensions of the data. Moreover, experiments in [11, 12] show that the classification accuracy of LDA/QR is competitive with other LDA algorithms. In this paper, we first propose an algorithm, namely KDA/QR1, which is a nonlinear exten- sion of LDA/QR. Since KDA/QR involves the whole kernel matrix, which is not scalable for large datasets, we also propose an approximation of KDA/QR, namely AKDA/QR. A distinct property of AKDA/QR is that it scales as O(ndc), where n is the size of the data, d is the dimension of the data, and c is the number of classes. We apply the proposed algorithms on face image datasets and compare them with LDA/QR, and Generalized Discriminant Analysis (GDA) [1], a general method for kernel discrim- inant analysis. Experiments show that: (1) AKDA/QR is competitive with KDA/QR and GDA in classification; (2) both KDA/QR and AKDA/QR outperform LDA/QR in classifi- cation; and (3) AKDA/QR has much lower costs in time and space than GDA.

Linear Discriminant Analysis (LDA) is a well-known scheme for feature extraction and dimension reduction. It has been used widely in many ap- plications involving high-dimensional data, such as face recognition and image retrieval. An intrinsic limitation of classical LDA is the so-called singularity problem, that is, it fails when all scatter matrices are singu- lar. A well-known approach to deal with the singularity problem is to apply an intermediate dimension reduction stage using Principal Com- ponent Analysis (PCA) before LDA. The algorithm, called PCA+LDA, is used widely in face recognition. However, PCA+LDA has high costs in time and space, due to the need for an eigen-decomposition involving the scatter matrices. In this paper, we propose a novel LDA algorithm, namely 2DLDA, which stands for 2-Dimensional Linear Discriminant Analysis. 2DLDA over- comes the singularity problem implicitly, while achieving efficiency. The key difference between 2DLDA and classical LDA lies in the model for data representation. Classical LDA works with vectorized representa- tions of data, while the 2DLDA algorithm works with data in matrix representation. To further reduce the dimension by 2DLDA, the combi- nation of 2DLDA and classical LDA, namely 2DLDA+LDA, is studied, where LDA is preceded by 2DLDA. The proposed algorithms are ap- plied on face recognition and compared with PCA+LDA. Experiments show that 2DLDA and 2DLDA+LDA achieve competitive recognition accuracy, while being much more efficient.

Visual media data such as an image is the raw data representation for many important applications. The biggest challenge in using visual media data comes from the extremely high dimensionality. We present a comparative study on spatial interest pixels (SIPs), including eight-way (a novel SIP miner), Harris, and Lucas-Kanade, whose extraction is considered as an important step in reducing the dimensionality of visual media data. With extensive case studies, we have shown the usefulness of SIPs as the low-level features of visual media data. A class-preserving dimension reduction algorithm (using GSVD) is applied to further reduce the dimension of feature vectors based on SIPs. The experiments showed its superiority over PCA.

Content-based music genre classification is a fundamental component of music information retrieval systems and has been gaining importance and enjoying a growing amount of attention with the emergence of digital music on the Internet. Currently little work has been done on automatic music genre classification, and in addition, the reported classification accuracies are relatively low. This paper proposes a new feature extraction method for music genre classification, DWCHs. DWCHs stands for Daubechies Wavelet Coefficient Histograms. DWCHs capture the local and global information of music signals simultaneously by computing histograms on their Daubechies wavelet coefficients. Effectiveness of this new feature and of previously studied features are compared using various machine learning classification algorithms, including Support Vector Machines and Linear Discriminant Analysis. It is demonstrated that the use of DWCHs significantly improves the accuracy of music genre classification.

Many real-world datasets contain noise which could degrade the performances of learning algorithms. Motivated from the success of wavelet denoising techniques in image data, we explore a general solution to alleviate the effect of noisy data by wavelet preprocessing for medical/biological data classification. Our experiments are divided into two categories: one is of different classification algorithms on a specific database, and the other is of a specific classification algorithm (decision tree) on different databases. The experiment results show that the wavelet denoising of noisy data is able to improve the accuracies of those classification methods, if the localities of the attributes are strong enough.