43431226
Wavelet-based optical flow estimation
A new algorithm for accurate optical flow (OF) estimation using discrete wavelet approximation is proposed. The computation of OF depends on minimizing the image and smoothness constraints. The proposed method takes advantages of the nature of wavelet theory, which can efficiently and accurately approximate any function. OF vectors and image functions are represented by means of linear combinations of scaling basis functions. Based on such wavelet-based approximation, the leading coefficients of these basis functions carry global information about the approximated functions. The proposed method can successfully convert the problem of minimizing a constraint function into that of solving a linear system of a quadratic and convex function of scaling coefficients. Once all the corresponding coefficients are determined, the flow vectors can be obtained accordingly. Experiments have been conducted on both synthetic and real image sequences. In terms of accuracy, the results show that our approach outperforms the existing methods which adopted the same objective function as ours.
21848565
Discrete signal matching using coarse-to-fine wavelet basis functions
In this paper, we propose a matching algorithm to estimate accurate and dense displacements between two signals. The displacements are characterized by a coarse-to-fine wavelet representation, which is a linear combination of hierarchical basis functions developed by Cai and Wang (SIAM Numer. Anal. 33(3) (1996) 937). The coarser-scale basis function has larger support while the finer-scale basis function has smaller support. During the iterative minimization process, the basis functions are utilized as large-to-small windows in selecting global-to-local regions for signal matching. The estimated wavelet coefficients are then used to reconstruct the signal in a coarse-to-fine manner. Two sets of synthetic examples, one with small displacement and the other with large displacements, have been employed to illustrate the advantages of the wavelet-based method. This method has been applied to estimate the dense disparity between stereo images in several real examples and the results demonstrate its effectiveness.
10243856
A new LDA-based face recognition system which can solve the small sample size problem
A new LDA-based face recognition system is presented in this paper. Linear discriminant analysis (LDA) is one of the most popular linear projection techniques for feature extraction. The major drawback of applying LDA is that it may encounter the small sample size problem. In this paper, we propose a new LDA-based technique which can solve the small sample size problem. We also prove that the most expressive vectors derived in the null space of the within-class scatter matrix using principal component analysis (PCA) are equal to the optimal discriminant vectors derived in the original space using LDA. The experimental results show that the new LDA process improves the performance of a face recognition system signi"cantly. ( 2000 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
120801
Recognition of Motor Imagery Electroencephalography Using Independent Component Analysis and Machine Classifiers
Motor imagery electroencephalography (EEG), which embodies cortical potentials during mental simulation of left or right finger lifting tasks, can be used to provide neural input signals to activate a brain computer interface (BCI). The effectiveness of such an EEG-based BCI system relies on two indispensable components: distinguishable patterns of brain signals and accurate classifiers. This work aims to extract two reliable neural features, termed contralateral and ipsilateral rebound maps, by removing artifacts from motor imagery EEG based on independent component analysis (ICA), and to employ four classifiers to investigate the efficacy of rebound maps. Results demonstrate that, with the use of ICA, recognition rates for four classifiers (fisher linear discriminant (FLD), back-propagation neural network (BP-NN), radial-basis function neural network (RBF-NN), and support vector machine (SVM)) improved significantly, from 54%, 54%, 57% and 55% to 70.5%, 75.5%, 76.5% and 77.3%, respectively. In addition, the areas under the receiver operating characteristics (ROC) curve, which assess the quality of classification over a wide range of misclassification costs, also improved from .65, .60, .62, and .64 to .74, .76, .80 and .81, respectively.
9822806
Wavelet-based optical flow estimation
In this paper, a new algorithm for accurate optical flow estimation using discrete wavelet approximation is proposed. The proposed method takes advantages of the nature of wavelet theory, which can efficiently and accurately represent "things", to model optical flow vectors and image related functions. Each flow vector and image function are represented by linear combinations of wavelet basis functions. From such wavelet-based approximation, the leading coefficients of these basis functions carry the global information of the approximated "things". The proposed method can successfully convert the problem of minimizing a constraint function into that of solving a linear system of a quadratic and convex function of wavelet coefficients. Once all the corresponding coefficients are decided, the flow vectors can be determined accordingly. Experiments conducted on both synthetic and real image sequences show that our approach outperformed the existing methods in terms of accuracy.
7065561
Partitioning Graphs Into Hamiltonian Ones
Abstract In this paper, we present an (optimal) linear-time algorithm that decides whether a bipartite permutation graph can be partitioned into one or more induced Hamiltonian subgraphs each of which contains at least k vertices for a given k , and if so, obtains such a partition. We then give an efficient parallelization of the algorithm. We also investigate the problem of partitioning arbitrary directed graphs into Hamiltonian ones.
4784687
SERF: ODMG-based generic re-structuring facility
The age of information management and with it the advent of increasingly sophisticated technologies have kindled a need in the database community and others to re-structure existing systems and move forward to make use of these new technologies. Legacy application systems are being transformed to newer state-of-the-art systems, information sources are being mapped from one data model to another, a diversity of data sources are being transformed to load, cleanse and consolidate data into modern data-warehouses [CR99].
Re-structuring is thus a critical task for a variety of applications. For this reason, most object-oriented database systems (OODB) today support some form of re-structuring support [Tec94, Obj93, BKKK87]. This existing support of current OODBs [BKKK87, Tec94, Obj93] is limited to a pre-defined taxonomy of simple fixed-semantic schema evolution operations. However, such simple changes, typically to individual types only, are not sufficient for many advanced applications [Bré96]. More radical changes, such as combining two types of redefining the relationship between two types, are either very difficult or even impossible to achieve with current commercial database technology [Tec94, Obj93]. In fact, most OODBs would typically require the user to write ad-hoc programs to accomplish such transformations. Research that has begun to look into the issue of complex changes [Bré96, Ler96] is still limited by providing a fixed set of some selected (even if now more complex) operations.
To address these limitations of the current restructuring technology, we have proposed the SERF framework which aims at providing a rich environment for doing complex user-defined transformations flexibly, easily and correctly [CJR98b]. The goal of our work is to increase the usability and utility of the SERF framework and its applicability to re-structuring problems beyond OODB evolution. Towards that end, we provide re-usable transformations via the notion of SERF Templates that can be packaged into libraries, thereby increasing the portability of these transformations. We also now have a first cut at providing an assurance of consistency for the users of this system, a semantic optimizer that provides some performance improvements via enhanced query optimization techniques with emphasis on the re-structuring primitives [CNR99]. In this demo we give an overview of the SERF framework, its current status and the enhancements that are planned for the future. We also present an example of the application of SERF to a domain other than schema evolution, i.e., the web restructuring.
335267
VLSI implementation of shape-adaptive discrete wavelet transform
In this paper, several VLSI architectures and implementations of Shape-Adaptive Discrete Wavelet Transform (SA-DWT) with odd symmetric biorthogonal filters are presented. The hardware implementation issues of SA-DWT algorithm are first addressed, and one lifting scheme together with some appropriate shape information processing units is introduced for the 1-D SA-DWT architectures. These architectures can efficiently perform 1-D length-adaptive DWT on continuous line segments and solve the corresponding boundary extension and subsampling problems without any overhead. In addition to 1-D architectures, two 2-D SA-DWT architectures are also proposed. One is the direct method, which uses the 1-D SA-DWT architectures as basis to extend to 2-D SA-DWT by direct row-column approach. The other is the line-based method, which is an efficient and feasible architecture that uses internal line buffers rather than external frame memory. These two 2-D SA-DWT architectures are both VLSI implemented by using cell-based chip design flow. The Daubechies (9,7) filter is used for the implementation by direct method, and the Daubechies (9,3) filter is used for the line-based implementation. The proposed architectures can be applied both in arbitrarily shaped visual objects coding such as MPEG-4 still texture coding and rectangular region image coding such as JPEG2000 still image coding.
12814139
A partitioning based algorithm to fuzzy co-cluster documents and words
In this paper, a new algorithm fuzzy co-clustering with Ruspini's condition (FCR) is proposed for co-clustering documents and words. Compared to most existing fuzzy co-clustering algorithms, FCR is able to generate fuzzy word clusters that capture the natural distribution of words, which may be beneficial for information retrieval. We discuss the principle behind the algorithm through some theoretical discussions and illustrations. These, together with experiments on two standard datasets show that FCR can discover the naturally existing document-word co-clusters.
1469255
Approximation algorithms for data distribution with load balancing of web servers
Given the increasing traffic on the World Wide Web (Web), it is difficult for a single popular Web server to handle the demand from its many clients. By clustering a group of Web servers, it is possible to reduce the origin Web server's load significantly and reduce user's response time when accessing a Web document. A fundamental question is how to allocate Web documents among these servers in order to achieve load balancing? In this paper, we are given a collection of documents to be stored on a cluster of Web servers. Each of the servers is associated with resource limits in its memory and its number of HTTP connections. Each document has an associated size and access cost. The problem is to allocate the documents among the servers so that no server's memory size is exceeded, and the load is balanced as equally as possible. In this paper, we show that most simple formulations of this problem are NP-hard, we establish lower bounds on the value of the optimal load, and we show that if there are no memory constraints for all the servers, then there is an allocation algorithm, that is within a factor 2 of the optimal solution. We show that if all servers have the same number of HTTP connections and the same memory size, then a feasible allocation is achieved within a factor 4 of the optimal solution using at most 4 times the optimal memory size. We also provide improved approximation results for the case where documents are relatively small.