- 2023
- 2022
- 2020
- 2019
- 2018
- 2017
- 2016
- 2015
- 2014
- 2013
- 2012
- 2011
- 2010
- 2009
- 2008
- 2007
- 2006
- 2005
- 2004
- 2003
- 2002
- 2001
- 2000
- 1999
- 1998
- 1997
- 1996
- 1995
- 1994
- 1993
- 1992
- 1991
- 1990
- 1989
- 1988
- 1987
- 1986
- 1985
- 1984
- 1983
- 1982
- 1981
- 1980
- 1979
Code
Subject / Author / Abstract
View
Code
TR-IIS-95-001
Subject / Author / Abstract
Wavelet-based shape from shading
Jun-Wei Hsieh, Hong-Yuan Mark Liao, Ming-Tat Ko and Kuo-Chin Fan
This report proposes a wavelet-based approach to solving the shape from shading (SFS) problem. The proposed method takes advantage of the nature of wavelet theory, which can be applied to efficiently and accurately represent ``things,'' to develop a faster algorithm for reconstructing better surfaces. To derive the algorithm, the formulation of Horn, which combines several constraints into an objective function, is adopted. In order to improve the robustness of the algorithm, two new constraints are introduced into the objective function to strengthen the relation between an estimated surface and its counterpart in the original image. Thus, solving the SFS problem becomes a constrained optimization process. Instead of solving the problem directly by using Euler equation or numerical techniques, the objective function is first converted into the wavelet format. Due to this format, the set of differential operators of different orders which is involved in the whole process can be approximated with connec tion coefficients of Daubechies bases. In each iteration of the optimization process, an appropriate step size which will result in maximum decrease of the objective function is determined. After finding correct iterative schemes, the solution of the SFS problem will finally be decided. Compared with conventional algorithms, the proposed scheme is a great improvement in the accuracy as well as the convergence speed of the SFS problem. Experimental results, using both synthetic and real images, prove that the proposed method is indeed better than traditional methods.
View
Code
TR-IIS-95-002
Subject / Author / Abstract
Undirected vertex-connectivity structure and smallest four-vertex- connectivity augmentation
Tsan-sheng Hsu.
In this paper, we study properties for the structure of an undirected graph that is not 4-vertex-connected. We also study the evolution of this structure when an edge is added to optimally increase the vertex-connectivity of the underlyinggraph. Several properties reported here can be extended to the case of a graph that is not $k$-vertex-connected, for an arbitrary $k$.
Using properties obtained here, we solve the problem of finding a smallest set of edges whose addition 4-vertex-connects an undirected graph. This is a fundamental problem in graph theory and has applications in network reliability and in statistical data security. We give an $O(n \cdot \log n + m)$-time algorithm for finding a set of edges with the smallest cardinality whose addition 4-vertex-connects an undirected graph, where $n$ and $m$ are the number of vertices and edges in the input graph, respectively. This is the first polynomial time algorithm for this problem when the input graph is not 3-vertex-connected. We also show a formula to compute this smallest number in $O(n \cdot \alpha(n, n) + m)$ time, where $\alpha$ is the inverse of the Ackermann function. This is also the first polynomial time algorithm for computing this number when the input graph is not 3-vertex-connected. Our algorithm can also be used to find a smallest $k$-vertex-connectivity augmentation, for any $k \leq 3$.
View
Code
TR-IIS-95-003
Subject / Author / Abstract
A new wavelet-based edge detector via constrained optimization
Hong-Yuan Mark Liao, Ming-Tat Ko, Jun-Wei Hsieh and Kuo-Chin Fan
This report proposes a new wavelet-based approach to solving the edge detection problem. The proposed scheme adopts Canny's three criteria as a guide to derive a wavelet-style edge filter such that the edge points of an image can be detected efficiently and accurately at different scales. Since Canny's criteria are suitable for those edge detectors that detect local extremes, the desired wavelet is therefore chosen to be anti-symmetric. In order to reconstruct the original image, the dual of the desired wavelet is also required. Basically, the pair of wavelets are represented as linear combinations of translations of a scaling function. By introducing a constrained optimization process, the set of expansion coefficients of the desired wavelet and its dual as well, can be determined. In order to implement the desired edge detector, a continuous wavelet has to be converted into the discrete form. For this purpose, the format of the discrete wavelet transform has to be developed. Since the propose d edge filter is wavelet-based, the inherent multiresolution nature of wavelet transform provides more flexibility in the analysis of images. Also, since an optimization process is introduced in the filter derivation process, the performance of the proposed filter is better than that of Mallat-Zhong's edge detector. In real implementation, the experimental results show that the proposed approach is indeed superb.
View
Code
TR-IIS-95-004
Subject / Author / Abstract
A 3D feature-based tracker for tracking multiple moving objects with a controlled binocular head
Yi-Ping Hung, Cheng-Yuan Tang, Sheng-Wen Shih, Zen Chen and Wei-Song Lin
Object tracking is an important task for active vision and robotics. This paper presents a 3D feature based tracker for tracking multiple moving objects with a computer-controlled binocular head. Our tracker operates in two phases: an initialization phase and a tracking phase. In the initialization phase, correspondence between 2D features in the first stereo image pair is determined reliably by using the epipolar line constraint and the mutually-supported consistency. In the tracking phase, the feedback loop is established by first predicting new 3D feature locations with the Kalman filters and then projecting them onto the 2D images to guide the extraction of 2D features in the new image pair. Here, we propose a RANSAC-based clustering method for motion segmentation and estima- tion by using the principle of rigid body consensus which states that all the extracted 3D features on a rigid body have the same 3D motion. This new method leads to a feature-clustering algorithm which provides a systematic way for managing splitting, merging, appearance and disappearance of multiple moving rigid objects -- including articulated objects, such as robot manipulators. By using the motion estimates obtained with the RANSAC-based method as the measurements for the Kalman filters, we are able to use linear Kalman filters for predictive visual tracking, instead of the extended Kalman filters which most people used for tracking. Experiments have shown that our tracking system does give good results and can serve as a robust 3D feature tracker for an active bin ocular vision system.
View
Code
TR-IIS-95-005
Subject / Author / Abstract
Image registration using a new edge-based approach
Jun-Wei Hsieh, Hong-Yuan Mark Liao, Kuo-Chin Fan, Ming-Tat Ko and Yi-Ping Hung
A new edge-based approach for efficient image registration is proposed. The proposed approach applies wavelet transform to extract a number of feature points as the basis for registration. Each selected feature point is an edge point whose edge response is the maximum within a neighborhood. By using a line-fitting model, all the edge directions of the feature points are estimated from the edge outputs of a transformed image. In order to estimate the orientation difference between two partially overlapping images, a so-called ``angle histogram'' is calculated. From the angle histogram, the rotation angle which can be used to compensate for the difference between two target images can be decided by seeking the angle that corresponds to the maximum peak in the histogram. Based on the rotation angle, an initial matching can be performed. During the real matching process, we check each candidate pair in advance to see if it can possibly become a correct matching pair. Due to this checking, many unnec essary calculations involving cross-correlations can be screened in advance. Therefore, the search time for obtaining correct matching pairs is reduced significantly. Finally, based on the set of correctly matched feature point pairs, the transformation between two partially overlapping images can be decided. The proposed method can tolerate roughly about 10% scaling variation and does not restrict the position and orientation of images. Further, since all the selected feature points are edge points, the restriction can significantly reduce the search space and, meanwhile, speed up the matching process. Compared with conventional algorithms, the proposed scheme is a great improvement in efficiency as well as reliability for the image registration problem.
View
Code
TR-IIS-95-006
Subject / Author / Abstract
Steiner problems on directed acyclic graphs
Tsan-sheng Hsu, Kuo-Hui Tsai, Da-Wei Wang and D. T. Lee
In this paper, we consider two variations of the minimum-cost Steiner problem on a directed acyclic graph $G(V,E)$ with a non-negative weight on each edge of $E$. The {\it minimum directed Steiner network} problem is defined as follows. Given a set of starting vertices $S \subset V$ and a set of terminating vertices $T \subset V$, find a subgraph with the minimum total edge weight such that for each starting vertex $s$ there exists a path from $s$ to a terminating vertex, and for each terminating vertex $t$, there exists a path from a starting vertex to $t$. The \mup problem is similar to the minimum directed Steiner network problem except that we are given a set of hitting vertices $H \subset V$, in addition to the sets of starting and terminating vertices and that we want to find a subgraph with the minimum total edge weight such that the subgraph satisfies not only the conditions above, but also that every hitting vertex is on a path from a starting vertex to a terminating vertex.
We present algorithms for finding {\it optimal} solutions to these two problems in time, respectively, $O(n \cdot m + 2^{|S| + |T|} \cdot \alpha^{3} \cdot (n^{\alpha - 2} + n^{\beta-1}))$ and $O(k! \cdot (8 \cdot k)^k \cdot k^3 \cdot n^{k-1} + n \cdot m)$, where $n$ and $m$ denote the number of vertices and edges of the graph, $\alpha = \max\{|S|, |T|\}$, $\beta = \min\{|S|, |T|\}$, and $k = |S| + |T| + |H|$. The algorithms can also enumerate all possible optimal solutions for both problems. Our algorithm for the {\it minimum directed Steiner network} problem can also be used on undirected graphs.
We also give linear time algorithms for some special cases.
View
Code
TR-IIS-95-007
Subject / Author / Abstract
Compiler techniques for determining data distribution and generating communication sets on distributed-memory multicomputers
PeiZong Lee and Wen-Yao Chen.
This presentation is concerned with designing efficient algorithms for determining data distribution and generating communication sets on distributed memory multicomputers. First, we propose a dynamic programming algorithm to automatically determine data distribution at compiling time. This approach is different from previous research works, which only allow programmers explicitly to specify the data distribution using language extensions. The proposed algorithm also can determine whether data redistribution is necessary between two consecutive DO-loop program fragments. Second, we propose closed forms to represent communication sets among processing elements for executing doall statements, when data arrays are distributed in a block-cyclic fashion. Our result contributes towards automatic compilation of sequential programs to message-passing version programs running on distributed memory parallel computers. Our methods also can be included in current compilers and used when programmers fail to provide any data distribution directives. Experimental studies on a nCUBE-2 multicomputer are also presented.
View
Code
TR-IIS-95-010
Subject / Author / Abstract
環境科學研究資訊系統八十四年度計畫報告
邵喻美,劉淑珍,張嘉祥,何建明
本文將介紹資訊所本年度在院方「環境科學整合研究計畫」項下的工作 成果。本子計畫的任務是協助其他各所建立資訊化的工作環境，以利資 料之整合利用，並進而透過網際網路推廣研究資訊。在這個目標之下， 我們的工作共分為整理電子地圖檔案與各子計畫提供的生態資訊；設計 製作觀測站資訊管理系統；資料庫的建立與維護；以及在全球資訊網（ World-Wide Web)上進行的推廣工作。
View
Code
TR-IIS-95-011
Subject / Author / Abstract
A probabilistic approach to the problem of automatic selection of data representations
Tyng-Ruey Chuang and Wen L. Hwang.
The design and implementation of efficient aggregate data structures has been an important issue in functional programming. It is not clear how to select a good representation for an aggregate when access patterns to the aggregate are highly variant, or even unpredictable. Previous approaches rely on compile--time analyses or programmer annotations. These methods can be unreliable because they try to predict program behaviors before they are executed.
We propose a probabilistic approach, which is based on Markov processes, for automatic selection of data representations. The selection is modeled as a random process moving in a graph with weighted edges. The proposed approach employs coin tossing at run-time to aid choosing suitable data representations. The transition probability function used by the coin tossing is constructed in a simple and common way from a measured cost function. We show that, under this setting, random selection of data representations can be quite effective. The probabilistic approach is applied to an simple example, and the results are compared to some deterministic selection algorithms.
View