Browsing by Author "Tang, CY"

Now showing 1 - 9 of 9

A 3D predictive visual tracker for tracking multiple moving objects with a stereo vision system
(1995)
Hung, YP
;
Tang, CY
;
Shih, SW
;
Chen, Z
;
Lin, WS
This paper presents a 3D feature-based visual tracker for tracking multiple moving objects by using a predictor that first partitions 3D features into different common-motion clusters and then predicts the motion of each cluster with Kalman filters. The 3D features are computed from a sequence of stereo images by combining two 2D temporal matching modules and one stereo correspondence module. To partition the 3D features into different common-motion clusters, we propose a RANSAC-based clustering method by using rigid body consensus which assumes that all the extracted 3D features on a rigid body have the same 3D motion. By using the motion estimates obtained with the RANSAC-based method as the measurements, we are able to use linear Kalman filters to predict the motion of each cluster, and then, to predict the next position of each 3D feature. Preliminary experiments showed that the proposed 3D predictive visual tracker can serve as a robust 3D feature tracker for an active stereo vision system.
An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species
(2005)
Lin, YC
;
Lu, CL
;
Chang, HY
;
Tang, CY
;
生物科技學系
In the study of genome rearrangement, the block-interchanges have been proposed recently as a new kind of global rearrangement events affecting a genome by swapping two nonintersecting segments of any length. The so-called block-interchange distance problem, which is equivalent to the sorting by block-interchange problem, is to find a minimum series of block-interchanges for transforming one chromosome into another. In this paper, we study this problem by considering the circular chromosomes and propose a O(deltan) time algorithm for solving it by making use of permutation groups in algebra, where n is the length of the circular chromosome and 3 is the minimum number of block-interchanges required for the transformation, which can be calculated in O(n) time in advance. Moreover, we obtain analogous results by extending our algorithm to linear chromosomes. Finally, we have implemented our algorithm and applied it to the circular genomic sequences of three human vibrio pathogens for predicting their evolutionary relationships. Consequently, our experimental results coincide with the previous ones obtained by others using a different comparative genomics approach, which implies that the block-interchange events seem to play a significant role in the evolution of vibrio species.
Automatic detection and tracking of human heads using an active stereo vision system
(2000-03-01)
Tang, CY
;
Chen, Z
;
Hung, YP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
A new head tracking algorithm for automatically detecting and tracking human heads in complex backgrounds is proposed. By using an elliptical model for the human head, our Maximum Likelihood (ML) head detector can reliably locate human heads in images having complex backgrounds and is relatively insensitive to illumination and rotation of the human heads. Our head detector consists of two channels: the horizontal and the vertical channels. Each channel is implemented by multiscale template matching. Using a hierarchical structure in implementing our head detector, the execution time for detecting the human heads in a 512 x 512 image is about 0.02 second in a Spare 20 workstation (not including the time for image acquisition). Based on the ellipse-based ML head detector, we have developed a head tracking method that can monitor the entrance of a person, detect and track the person's head, and then control the stereo cameras to focus their gaze on this person's head. In this method, the ML head detector and the mutually-supported constraint are used to extract the corresponding ellipses in a stereo image pair. To implement a practical and reliable face detection and tracking system, further verification using facial features, such as eyes, mouth and nostrils, may be essential. The 3D position computed from the centers of the two corresponding ellipses is then used for fixation. An active stereo head has been used to perform the experiments and has demonstrated that the proposed approach is feasible and promising for practical uses.
Efficient minus and signed domination in graphs
(2003-05-14)
Lu, CL
;
Peng, SL
;
Tang, CY
;
生物科技學系
;
Department of Biological Science and Technology
An efficient minus (respectively, signed) dominating function of a graph G = (V,E) is a function f:V --> {-1,0,1} (respectively, {-1,1}) such that Sigma(uis an element ofN[nu]) f(u) = I for all nu is an element of V, where N [nu] = {nu} boolean OR {u (u, nu) is an element of E}. The efficient minus (respectively, signed) domination problem is to find an efficient minus (respectively, signed) dominating function of G. In this paper, we show that the efficient minus (respectively, signed) domination problem is NP-complete on chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (respectively, on chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (respectively, every graph with no vertex of odd degree) has an efficient minus (respectively, signed) dominating function. We also give linear-time algorithms to find these functions. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees. (C) 2002 Elsevier Science B.V. All rights reserved.
Numerical performance and throughput benchmark for electronic structure calculations in PC-Linux systems with new architectures, updated compilers, and libraries
(2004-03-01)
Yu, JSK
;
Hwang, JK
;
Tang, CY
;
Yu, CH
;
生物科技學系
A number of recently released numerical libraries including Automatically Tuned Linear Algebra Subroutines (ATLAS) library, Intel Math Kernel Library (MKL), GOTO numerical library, and AMD Core Math Library (ACML) for AMD Opteron processors, are linked against the executables of the Gaussian 98 electronic structure calculation package, which is compiled by updated versions of Fortran compilers such as Intel Fortran compiler (ifc/efc) 7.1 and PGI Fortran compiler (pgf77/pgf90) 5.0. The We 7.1 delivers about 3% of improvement on 32-bit machines compared to the former version 6.0. Performance improved from pgf77 3.3 to 5.0 is also around 3% when utilizing the original unmodified optimization options of the compiler enclosed in the software. Nevertheless, if extensive compiler tuning options are used, the speed can be further accelerated to about 25%. The performances of these fully optimized numerical libraries are similar. The double-precision floating-point (FP) instruction sets (SSE2) are also functional on AMD Opteron processors operated in 32-bit compilation, and Intel Fortran compiler has performed better optimization. Hardware-level tuning is able to improve memory bandwidth by adjusting the DRAM timing, and the efficiency in the CL2 mode is further accelerated by 2.6% compared to that of the CL2.5 mode. The FP throughput is measured by simultaneous execution of two identical copies of each of the test jobs. Resultant performance impact suggests that IA64 and AMD64 architectures are able to fulfill significantly higher throughput than the IA32, which is consistent with the SpecFPrate2000 benchmarks.
On the full and bottleneck full Steiner tree problems
(2003)
Chen, YH
;
Lu, CL
;
Tang, CY
;
生物科技學系
;
Department of Biological Science and Technology
Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree problem is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. In this paper, we present a new approximation algorithm with performance ratio 2p for the full Steiner tree problem, where p is the best-known performance ratio for the Steiner tree problem. Moreover, we give an exact algorithm of O(E log E) time to solve the bottleneck full Steiner tree problem.
ROBIN: a tool for genome rearrangement of block-interchanges
(2005-06-01)
Lu, CL
;
Wang, TC
;
Lin, YC
;
Tang, CY
;
生物科技學系
ROBIN is a web server for analyzing genome rearrangement of block-interchanges between two chromosomal genomes. It takes two or more linear/circular chromosomes as its input, and computes the number of minimum block-interchange rearrangements between any two input chromosomes for transforming one chromosome into another and also determines an optimal scenario taking this number of rearrangements. The input can be either bacterial-size sequence data or landmark-order data. If the input is sequence data, ROBIN will automatically search for the identical landmarks that are the homologous/conserved regions shared by all the input sequences.
The full Steiner tree problem
(2003-09-05)
Lu, CL
;
Tang, CY
;
Lee, RCT
;
生物科技學系
;
Department of Biological Science and Technology
Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R subset of V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either I or 2. For the instances with lengths either I or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem. (C) 2003 Elsevier B.V. All rights reserved.
Updated numerical performance and throughput benchmark for electronic structure calculations in PC-LINUX systems.
(2004-03-28)
Yu, JSK
;
Hwang, JK
;
Tang, CY
;
Yu, CH
;
生物科技學系