您的瀏覽器不支援JavaScript語法，網站的部份功能在JavaScript沒有啟用的狀態下無法正常使用。

Institute of Information Science, Academia Sinica

Library

Print

Press Ctrl+P to print from browser

1997 Technical Report

Code

Subject / Author / Abstract

View

Code

TR-IIS-97-001

Subject / Author / Abstract

FAST FACE DETECTION VIA MORPHOLOGY-BASED PRE-PROCESSING
CHIN-CHUAN HAN, HONG-YUAN MARK LIAO, KUO-CHUNG YU AND LIANG-HUA CHEN.

An efficient face detection algorithm which can detect multiple faces in cluttered environment is proposed. The proposed system consists of three main steps. In the first step, a morphology-based technique is devised to perform eye-analogue segmentation. Morphological operations are applied to locate eye-analogue pixels in the original image. Then, a labeling process is executed to generate the eye-analogue segments. In the second step, the previously located eye-analogue segments are used as guides to search for potential face regions. The last step of the proposed system is to perform face verification. In this step, every face candidate obtained from the previous step is normalized to a standard size. Then, each of these normalized potential face images is fed into a trained backpropagation neural network for identification. After all the true faces are identified, their corresponding poses are located based on the guidance of optimizing a cost function. The proposed face detection technique may locate multiple faces oriented in any directions. Besides, the morphology-based eye-analogue segmentation process is able to reduce the background part of a cluttered image up to 95\%. This process significantly speeds up the subsequent face detection procedure because only 5-10% regions of the original image are left for further processing. Experiments demonstrate that an approximately 94% success rate is reached and the relative false detection rate is very low.

View

Code

TR-IIS-97-002

Subject / Author / Abstract

DISPARITY MORPHING AND AUTOMATIC GENERATION OF STEREO PANORAMAS FOR PHOTO-REALISTIC VIRTUAL REALITY SYSTEMS
HO-CHAO HUANG AND YI-PING HUNG.

Stereo perception is important for a truly immersive virtual reality (VR) system. Recent improvements in computer and video technology have made stereoscopic display systems more prevalent than ever. However, most panoramic imaging systems which can display photo-realistic VR world still have difficulties in automatic production of high-quality stereo panoramas. This paper presents a stereo panoramic imaging system (SPISY) that can automatically generate high-quality photo-realistic stereo panoramas. The major difficulty of generating a stereo panorama from a sequence of stereo images taken by two cameras comes from the image disparity between the two adjacent images to be stitched together, which is caused by the inherent restriction that only one of the two cameras can have its lens center passed by the rotation axis. In this paper, we first analyze the image disparity problem caused by the dislocation of the lens center from the vertical rotation axis, and then propose a disparity morphing algorithm to solve it. Other characteristics of the SPISY include the capability of generating complete-focus views and balanced-exposure views, and of correcting the effect caused by camera tilt and epipolar line inconsistency. With the stereo and automatic correction features, the SPISY can easily provide realistic 360-degree panoramic stereo views for image-based VR systems.

View

Code

TR-IIS-97-003

Subject / Author / Abstract

GRAPH SEARCHING ON CHORDAL GRAPHS
Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu and Chuan-Yi Tang

In the graph searching problem, initially a graph with all edges contaminated is presented. We would like to obtain a state of the graph in which all edges are simultaneously clear by a sequence of moves using searchers. The objective is to achieve the desired state by using the least number of searchers. Two variations of the graph searching problem are considered in this paper. One is the edge searching, in which the clearing of an edge is accomplished by moving a searcher along the edge, and the other is the node searching, in which an edge is cleared by concurrently having searchers on both of its endpoints. In this paper, we present a uniform approach to solve the above two graph searching problems on several classes of chordal graphs. For edge searching problem, we give an O(mn^2)-time algorithm on split graphs, an O(m+n) -time algorithm on interval graphs, and an O(mn^k)-time algorithm on k-starlike graphs (a generalization of split graphs), for a fixed k>= 2, where m and n are the numbers of edges and vertices in the input graph, respectively. There are no polynomial algorithms known previously for any of the above problems. As a by-product, we also show that the edge searching problem remains NP-complete on chordal graphs. For node searching problem, we give an O(mn^k)-time algorithm on k-starlike graphs for a fixed k. This result implies that the pathwidth problem on k-starlike graphs is also in this time bound which greatly improves the previous results.

View

Code

TR-IIS-97-004

Subject / Author / Abstract

ESTIMATION OF FRACTIONAL BROWNIAN MOTION EMBEDDED IN A NOISY ENVIRONMENT USING NON-ORTHOGONAL WAVELETS
WEN-LIANG HWANG.

We show that non-orthogonal wavelets can characterize the fractional Brownian motion (fBm) that is in white noise. We demonstrate the point that discriminating the parameter of a fBm from that of noise is equivalent to discriminating the composite singularity formed by superimposing a peak singularity upon a Dirac singularity. We characterize the composite singularity by formalizing this problem as a nonlinear optimization problem. This yields our parameter estimation algorithm. For fractal signal estimation, Wiener filtering is explicitly formulated as a function of the signal and noise parameters and the wavelets. We show that the estimated signal is an $\frac{1}{f}$ process. Comparative studies of our methods with those of Wornell and Oppenheim are shown in numerical simulations.

View

Code

TR-IIS-97-005

Subject / Author / Abstract

ROBUST ESTIMATION OF PLANAR SURFACE ORIENTATION WITH CONTINUOUS WAVELET TRANSFORM
CHUN-SHIEN LU, WEN-LIANG HWANG AND PAU-CHOO CHUNG.

We propose a new method to estimate the surface orientation of a planar texture under perspective projection based on the ridge surface of 2D continuous wavelet transform (CWT) with rotations. We show that textural information giving the perception of surface orientation can be characterized from ridge surfaces in the space/frequency space. Three variants of ridge detection algorithm are presented. In order to deal with the weakly-ordered and disordered textures, robust regression method (RANSAC) is introduced to solve the problem. A closed-form solution is derived to determine surface orientation. The effectiveness of our method are demonstrated on several real-world textured images.

View

Code

TR-IIS-97-006

Subject / Author / Abstract

OPTIMIZATIONS OF STORED VBR VIDEO TRANSMISSION ON CBR CHANNEL
Ray-I Chang, Meng Chang Chen, Jan-Ming Ho and Ming-Tat Ko

In this paper, a new method is proposed to optimize stored VBR (variable-bit-rate) video transmission on CBR (constant-bit-rate) channel. The proposed method can minimize both the buffer requirement and work-ahead for a given peak transmission rate. Besides, the network utilization is maximized with the minimum service connection time. These problem parameters are not optimized at the same time in the conventional approaches. In this paper, we at first present the Lazy scheme to determine the minimum buffer and work-ahead required for a given peak transmission rate. Then, the Aggressive scheme is applied to maximize the system resource utilization (e.g., network bandwidth). The proposed schemes can be easily extended to transmit the VBR video with the minimum rate variability, or to resolve the buffer-constrained transmission problem with the minimum peak transmission rate for a given buffer size. Experiments to many well-known benchmark video traces show that the proposed method can obtain better network utilization and requires less memory buffer than the conventional approaches.

View

Code

TR-IIS-97-007

Subject / Author / Abstract

FACE＋HAIR＋SHOULDERS＋BACKGROUND≠FACE
HONG-YUAN MARK LIAO, CHIN-CHUAN HAN AND GWO-JONG YU.

Face recognition, by definition, should be a recognition process in which recognition is based on the content of a face. The problem is: what is a ``face'' ? Goudail et al. and Swets and Weng have recently proposed state-of-the-art face recognition systems. Through careful implementation, the results have shown that both methods are valid and efficient. However, we have a question about the ``face'' images they have adopted. They used ``face'' images that included hair, shoulders, face and background. Our intuition tells us that only a recognition process based on a ``pure'' face portion can be called face recognition. From a series of experiments, we have shown that the ``real'' face portion in their face recognition process did not play a key role at all. Instead, the combination of hair, shoulder and background dominated the whole recognition process. We suggest that future research on face recognition should use a face-only database, not a face combined with other irrelevant portions.

View

Code

TR-IIS-97-008

Subject / Author / Abstract

FACE RECOGNITION USING A FACE-ONLY DATABASE : A NEW APPROACH
Hong-Yuan Mark Liao, Chin-Chuan Han, Gwo-Jong Yu, Hsiao-Rong Tyan, Meng Chang Chen and Liang-Hua Chen

In this paper, a coarse-to-fine, LDA-based face recognition system is proposed. Through careful implementation, we found that the databases adopted by two state-of-the-art face recognition systems [4, 5] were incorrect because they mistakenly use some none-face portions for face recognition. Hence, a face-only database is used in the proposed system. Since the facial organs on a human face only differ slightly from person to person, the decision-boundary determination process is tougher in this system than it is in conventional approaches. Therefore, in order to avoid the above mentioned ambiguity problem, we propose to retrieve a closest subset of database samples instead of retrieving a single sample. The proposed face recognition system has several advantages. First, the system is able to deal with a very large database and can thus provide a basis for efficient search. Second, due to its design nature, the system can handle the defocus and noise problems. Third, the system is faster than the autocorrelation plus LDA approach [4] and the PCA plus LDA approach [5], which are believed to be two statistics-based, state-of-the-art face recognition systems. Experimental results prove that the proposed method is better than traditional methods in terms of efficiency and accuracy.

View

Code

TR-IIS-97-009

Subject / Author / Abstract

HIGH-LEVEL EXECUTION TIME ANALYSIS
FARN WANG.

A compositional algebra, called mMCAN, for the execution time analysis of high-level software processes is introduced. In mMCAN, processes can be concatenated, concurrently executed, and recursively invoked. We show that the set of execution times of an mMCAN is semilinear. We then propose and analyze an algorithm which calcuates the execution time sets of an mMCAN in semilinear forms. Finally, we consider several interesting variations of mMCAN whose execution time sets can be computed with algorithms.

View

Code

TR-IIS-97-010

Subject / Author / Abstract

PARAMETRIC ANALYSIS OF COMPUTER SYSTEMS
FARN WANG AND PAO-ANN HSIUNG.

A general parametric analysis problem which allows the usage of parameter variables in both the real-time automata and the specifications is proposed and solved. The solutions come in the forms of linear conditions on the parameter variables.

View

Code

TR-IIS-97-011

Subject / Author / Abstract

LINE SWEEP THINNING ALGORITHM : A COMPLETE TECHNICAL REPORT
FU CHANG, YA-CHING LU AND THEO PAVLIDIS.

In this article, we propose a new thinning algorithm based on line sweep operation. A line sweep is a process where the plane figure is divided into parallel slabs by lines passing through certain "events" and items are then processed according to an order of the slabs. Assuming that the contour of the figure to be thinned have been approximated by polygons, the "events" are then the vertices of the polygons and the line sweep algorithm looks for pairs of edges that lie within each slab. The pairing of edges are useful for detecting both regular and intersection regions. The regular regions can be found at the site where pairings between edges exist. Intersection regions, on the other hand, are where such relations would cease to exist, due to the fact that pair relations between edges of wide distance were canceled. A salient feature of our approach is to find simultaneously the set of regular regions that attach to the same intersection region. Such a set is thus called an intersection set. The output of our algorithm consists of skeletons as well as intersection sets. Both of them can be used as features for subsequent character recognition. Moreover, the line sweep thinning algorithm is efficient in computation as compared with a pixelbased thinning algorithm which outputs skeletons only.

View

Code

TR-IIS-97-012

Subject / Author / Abstract

NEW TEMPORAL FEATURES FOR ROBUST SPEECH RECOGNITION WITH EMPHASIS ON MICROPHONE VARIATIONS
JIA-LIN SHEN AND WEN L. HWANG.

Although the delta and RASTA methods have been widely used in extracting the temporal properties of stationary features for robust speech recognition, there is still a need to investigate new temporal features for better performance. In this paper, we present two new temporal features for robust processing of speech signals with emphasis on microphone variations. First, the temporal feature is derived from a bank of RASTA-like filters, in where the parameters of each filter in this bank are estimated according to the statistical properties of the speech signals. Secondly, a parameterized temporal filter (called PTF) is proposed. The filter can be described by four parameters, the passband, the beginning transition, the ending transition, and the smoothness of the magnitude of the filter response. These parameters altogether determine the magnitude of the frequency response of the PTF, and a transformation algorithm is then used to derive the temporal coefficients with real and causal characteristics. The discriminative ability of PTF features can be further enhanced using the minimum classification error (MCE) algorithm. Experimental results show that the RASTA features is inferior to the PTF features both in quiet condition and in the presence of microphone variations

View

Code

TR-IIS-97-013

Subject / Author / Abstract

CHARACTER EXTRACTION FROM DOCUMENTS USING WAVELET MAXIMA
WEN L. HWANG AND FU CHANG.

The extraction of character images is an important front-end processing task in optical character recognition (OCR) and other applications. This process is extremely important because OCR applications usually extract salient features and process them. The existence of noise not only destroys features of characters, but also introduces unwanted features. We propose a new algorithm which removes unwanted background noise from a textual image. Our algorithm is based on the observation that the magnitude of the intensity variation of character boundaries differs from that of noise at various scales of their wavelet transform. Therefore, most of the edges corresponding to the character boundaries at each scale can be extracted using a thresholding method. The internal region of a character is determined by a voting procedure, which uses the arguments of the remaining edges. The interior of the recovered characters is solid, containing no holes. The recovered characters tend to become fattened because of the smoothness applied in the calculation of the wavelet transform. To obtain a quality restoration of the character image, the precise locations of characters in the original image are then estimated using a Bayesian criterion. We also present some experimental results that suggest the effectiveness of our method.

View

Code

TR-IIS-97-014

Subject / Author / Abstract

A SCSI DISK MODEL FOR MULTIMEDIA STORAGE SYSTEMS
Meng Chang Chen, Jan-Ming Ho, Ming-Tat Ko and Shie-Yuan Wang

Modern magnetic disks support advanced mechanisms, such as read-ahead and caching, to optimize disk access performance. However, most of the proposed disk models in the literature of multimedia storage systems are too simplified to include the advanced feature that result in inaccurate performance prediction. In this paper, we propose an accurate, detailed SCSI disk model customized for multimedia storage systems. The methodologies of extracting the parameters of the proposed model are presented. Disk throughput is analyzed and verified by experiments under various contexts. The model and methodologies proposed in the paper can benefit the design of multimedia storage system in many ways, such as performance prediction, file layout design and disk I/O scheduling policy.

View

Code

TR-IIS-97-015

Subject / Author / Abstract

NON-INTRUSIVE OBJECT INTROSPECTION IN C++ : ARCHITECTURE AND APPLICATION
TYNG-RUEY CHUANG, Y. S. KUO AND CHIEN-MIN WANG.

We describe the design and implementation of system architecture to support object introspection in C++. An introspective object permits observation and change to its own state by a general mechanism that is applicable to objects of all classes. This general mechanism allows the construction of applications where objects are late-binding and the interactions between them are highly dynamic. Unlike Java, which provides full support for object introspection, C++ has limited built-in introspective capability via its Run-Time Type Information (RTTI) and related facilities. For example, in C++ one cannot query an object for methods that can be applied to it. We show how such introspective information can be collected at compile-time by parsing class declarations, and be used to build a supporting environment for object introspection at run-time. Our approach is non-intrusive because it requires no change to the original class declarations and libraries, and it guarantees compatibility between objects before and after the addition of introspective capability. This is important if one wants to integrate third-party class libraries, which are often supplied as black boxes and allow no modification, into highly dynamic applications. We show two applications that are built on top of our introspective environment. The first is a generic facility for automatic I/O support of complex C++ objects. The other is a class exerciser that allows interactive execution of dynamically loaded C++ class libraries.

View

Code

TR-IIS-97-016

Subject / Author / Abstract

GENERATING GLOBAL NAME-SPACE COMMUNICATION SETS FOR ARRAY ASSIGNMENT STATEMENTS
PEIZONG lEE AND WEN-YAO CHEN.

This paper is concerned with the design of efficient algorithms for generating global name-space communication sets based on execution of array assignment statements on distributed-memory parallel computers. For general cases, although the communication sets can be represented by the union of a functional number of closed forms, these sets cannot be represented by a fixed number of closed forms. Closed-form expressions for communication sets would reduce the associated packing overhead at the sending processor and unpacking overhead at the receiving processor. In this paper, we will first present a method using row-wise block-to-block intersections and an integer lattice method to generate communication sets when data arrays are distributed in any arbitrary block-cyclic fashion. After that, we will show that compiler or run-time support itself is more suitable for determining the block sizes of the array distributions. We will also derive closed forms to represent communication sets when data arrays are distributed in a restricted block-cyclic fashion, which can be determined at compiling time. Our methods can be included in current compilers and used when programmers don't know how to use data distribution directives to assign suitable block sizes. Experimental studies on a 16-node nCUBE/2E parallel computer are also presented.

View

Code

TR-IIS-97-017

Subject / Author / Abstract

WAVELET-BASED OFF-LINE SIGNATURE VERIFICATION
Peter Shaohua Deng, Hong-Yuan Mark Liao, Chin Wen Ho and Hsiao-Rong Tyan

In this paper, a wavelet-based off-line signature verification system is proposed. The proposed system can automatically identify useful and common features which consistently exist within different signatures of the same person and, based on these features, verify whether a signature is a forgery or not. The system starts with a closed-contour tracing algorithm. The curvature data of the traced closed contours are decomposed into multiresolutional signals using wavelet transforms. Then the zero-crossings corresponding to the curvature data are extracted as features for matching. Moreover, a statistical measurement is devised to decide systematically which closed contours and their associated frequency data of a writer are most stable and discriminating. Based on these data, the optimal threshold value which controls the accuracy of the feature extraction process is calculated. The proposed approach can be applied to both on-line and off-line signature verification system. Experimental results shows that the average success rates for English signature and Chinese signatures are 91.71% and 93%, respectively.

View

Code

TR-IIS-97-018

Subject / Author / Abstract

AN O(N log N) R-B CURVE DRAWING ALGORITHM FOR THE ADMISSION CONTROL OF VBR VIDEO TRANSMISSION
Ming-Tat Ko, Jan-Ming Ho, Meng Chang Chen and Ray-I Chang

The available resources such as memory buffer and network bandwidth are limited and varying for different application systems. Given a VBR stream, we have already proposed an algorithm to construct a transmission schedule with minimum buffer, minimum workahead and maximum network utilization for the given transmission rate. Notably, there is a trade-off between the allocated buffer size and the obtained network utilization to playback a VBR stream. To facilitate resource management and admission control for QoS guarantees, we need to explore the relation of the required client buffer and the obtained network utilization for the allocated transmission rate. Having these relation functions, whenever a new request is presented, the admission control procedure can easily check the required resources against the available resources and decides to admit this new request or not. The session setup protocol is as simple as a request-reply. Note that, the allocated transmission rate turns out to be a piecewise linear decreasing function of the memory buffer size. A native algorithm takes $O(n^3)$ to compute the rate-buffer (R-B) function where $n$ is the number of video frames. In this paper, an $O(n \log n)$ R-B curve drawing algorithm is proposed. The same scheme can be extended to compute the relations between the transmission rate and the obtained network utilization.

View

Code

TR-IIS-97-019

Subject / Author / Abstract

RANSAC-BASED DARCES : A NEW APPROACH FOR FAST AUTOMATIC REGISTRATION OF PARTIALLY OVERLAPPING RANGE IMAGES
CHU-SONG CHEN, YI-PING HUNG AND JEN-BO CHENG.

A popular approach for 3D registration of partially-overlapping range images is the ICP (iterative closest point) method and many of its variations. The major drawback of this type of iterative approaches is that they require a good initial estimate to guarantee that the correct solution can always be found. In this paper, we propose a new method, the RANSAC-based DARCES (data-aligned rigidity-constrained exhaustive search) method, which can solve the partially-overlapping 3D registration problem efficiently and reliably without any initial estimation. Another important characteristic of our method is that it requires no local features in the 3D data set. An extra characteristic is that, for the noiseless case, the basic algorithm of our DARCES method can guarantee that the solution it finds is the true one, due to its exhaustive-search nature. Even with the nature of exhaustive search, its time complexity can be shown to be relatively low. Experiments have demonstrated that our method is efficient and reliable for registering partially-overlapping range images.

View

Code

IM-IIS-97-001

Subject / Author / Abstract

WWW 資訊設備運用管理系統
王秋鳳,張志維.

View

not for public 原文請洽圖書室