REGION ENCODING DIAGRAM FOR FULLY SYMBOLIC VERIFICATION OF REAL-TIME SYSTEMS
FARN WANG
RED (Region Encoding Diagram), first reported in TACAS'2000, is a BDD-like data-structure for fully symbolic verification of symmetric real-time systems with single clock per process We propose to extend RED for asymmetric real-time systems with unrestricted number of global or local clocks. Unlike in DBM which records differences between pairs of clock readings, we records the ordering among fractional parts of clock readings into integer sequences encoded in RED's. Like BDD, the new RED is also a minimal canonical form for its target system state-space representations. The number of variables used in RED is $O(|X|\log |X|)$ when $X$ is the clock set in the input system description. Experiment has been carried out to show the possible verification efficiency through the intense data-sharing nature of RED.
MULTIPURPOSE WATERMARKING FOR IMAGE AUTHENTICATION AND PROTECTION
CHUN-SHIEN LU AND HONG-YUAN MARK LIAO
We propose a novel multipurpose watermarking scheme, in which robust and fragile watermarks are simultaneously embedded, for copyright protection and content authentication. By quantizing a host image's wavelet coefficients as masking threshold units (MTUs), two complementary watermarks are embedded using cocktail watermarking and they can be blindly extracted without access to the host image. For the purpose of image protection, the new scheme guarantees that, no matter what kind of attack is encountered, at least one watermark can survive well. On the other hand, for the purpose of image authentication, our approach can locate the part of the image that has been changed and tolerate some incidental processes that have been executed. Experimental results show that the performance of our multipurpose watermarking scheme is indeed superb in terms of robustness and fragility.
RETRIEVING INFORMATION FROM DOCUMENT IMAGES: PROBLEMS AND SOLUTIONS
FU CHANG
An information retrieval system that captures both visual and textual contents from paper documents
can derive maximal benefits out of DAR techniques while demanding little human assistance for achieving
its goals. This article discusses the technical problems, solution methods and integration of them into a
well-performing system. Focus of the discussion is on very hard applications, for example, to Chinese and
Japanese documents.
In addition to large group of potential readers, the latter types of documents create many technical issues
that deserve experts’attention. The complicated Chinese or Kanji characters, for example, impose serious
problem for image binarization. The coexistence of vertical and horizontal textlines on the same page renders
document segmentation difficult. The large number of characters also challenges the way textual contents are
recognized and retrieved.
Problems discussed in this article will be centered on these issues. Solution methods will also be highlighted
, with the emphasis placed upon some new ideas, including window-based binarization using scale measures,
document layout analysis as solving multiple constraint problem, and full-text searching technique capable of
evading machine recognition errors.
ROBUST EZW IMAGE COMPRESSION USING RATE-DISTORTION ANALYSIS
Jen-Chang Liu, Wen-Liang Hwang, Wen-Jyi Hwang, and Ming-Syan Chen
The EZW(Embedded Zerotree Wavelet)-like image compression algorithms lack
the error-resilience ability in noisy transmission environments. We propose the channel-
optimized source coding scheme to improve the robustness of them. First, a block-based
method is adopted to localize the error effects. Then we assign bits to each block by
applying dynamic bit allocation to the block-based EZW algorithm based on the rate-
distortion functions computed from the channel noise models. The performance of
our method was evaluated on both the binary symmetric channel and burst noise channel
models.
ELLIPSOIDAL MODELING FOR ARTICULATED ROBOT MANIPULATORS FOR INTERACTIVE MOTION PLANNING
Ming-Yi Ju, Jing-Sin Liu and Kao-Shing Hwang
The report presents an enclosing and enclosed ellipsoids based solid modeling technique for serial links of articulated robot manipulators. This modeling allows the collision detection for interactive robot motion planning in a graphical simulation environment or in a telerobotic simulator be performed efficiently and precisely. A systematic way of determining the kinematic transformation matrices between links and its associated ellipsoids model is presented. An example, a PUMA560 manipulator, is shown in details to demonstrate the proposed modeling technique.
MATCHING PURSUIT LOW-BIT RATE VIDEO CODING WITH DICTIONARY OPTIMIZED BY SHAPE-GAIN VECTOR QUANTIZER
Yao-Tang Chou, Wen-Liang Hwang, Chung-Lin Huang
We show that the techniques of the shape-gain product vector quantizer(VQ) can be used to optimize the dictionary of the matching pursuit codec and produce good results. We start with an initial dictionary and obtain a dictionary that is wellz adapted to the training sequences. The performance is evaluated based on a comparison of our method with other methods.
SINGULARITY DETECTION AND CHARACTERIZATION WITH COMPLEX-VALUED WAVELETS AND THEIR APPLICATIONS
Chun-Liang Du and Wen-Liang Hwang
We prove that the wavelet modulus maxima with a complex-valued wavelet
can detect and characterize singularities. This can be regarded as an extension
of the previous wavelet modulus work with a real wavelet. The ridges
of wavelet transforms are the places in the time-frequency plane where the local
energies of a signal are mostly concentrated. We show that based on the ridges
of the wavelet transforms, the osciallating singularities are better located and
their oscillating components are better characterized than they are based on the
general maxima of real-valued wavelet transforms. We demonstrate potential
applications of these techniques.
FAST AND ACCURATE COLLISION DETECTION BASED ON ENCLOSED ELLIPSOID
Ming-Yi Ju*,**, Jing-Sin Liu*, Shen-Po Shiang*, Yuh-Ren Chien*, Kao-Shing Hwang** and Wan-Chi Lee *
A fast and accurate method for detecting the collisions of convex polyhedra
in a graphical simulation environment based on a newly developed method of
distance estimate is presented. By the use of the enclosing and the enclosed
ellipsoids of convex polyhedra, potential collisions can be detected more
accurate than those methods using only bounding volume for object
representation, and more efficient than the polyhedral methods. An approach
for computing the enclosed ellipsoid of a convex polyhedron by compressing,
stretching and scaling operations on its best-fit enclosing ellipsoid is
introduced. Graphical simulations of moving objects in three-dimensional
space and multiple robot arm system applications are conducted to
demonstrate the accuracy of the proposed algorithm for collision detection
and minimum separating distance computation.
MEAN QUANTIZATION-BASED FRAGILE WATERMARKING FOR IMAGE AUTHENTICATION
Gwo-Jong Yu*, Chun-Shien Lu**, Hong-Yuan Mark Liao**
The existing digital image editing tools have made the authentication of digital
images an important issue. The objective of this paper is to propose an image
authentication scheme, which is able to detect malicious tampering while tolerating some
incidental distortions. By modeling the magnitude changes caused by incidental distortion
and malicious tampering as Gaussian distributions with small and large variances,
respectively, we propose to embed a watermark by using a mean quantization technique
in the wavelet domain. The proposed scheme is superior to the conventional quantization-
based approaches in terms of the credibility of authentication. Statistical analysis is conducted
to show that the probabilities of watermark errors caused by malicious tampering and
incidental distortion will be, respectively, maximized and minimized when our new scheme
is applied. Experimental results demonstrate that the credibility of our method is superior to
that of the conventional quantization-based methods under malicious attack followed by an
incidental modification, such as JPEG compression, sharpening or blurring.
STRUCTURAL DIGITAL SIGNATURE FOR IMAGE AUTHENTICATION: AN INCIDENTAL DISTORTION RESISTANT SCHEME
Chun-Shien Lu and Hong-Yuan Mark Liao
The existing digital data verification methods are able to detect regions that have been tampered with,
but are too fragile to resist incidental manipulations. This paper proposes a new digital signature
scheme which makes use of an image's contents (in the wavelet transform domain) to construct a
structural digital signature (SDS) for image authentication. The characteristic of the SDS is that it
can tolerate content-preserving modifications while detecting content-changing modifications. Many
incidental manipulations, which were detected as malicious modifications in the previous digital signature
verification or fragile watermarking schemes, can be bypassed in the proposed scheme. Performance
analysis is conducted and experimental results show that the new scheme is indeed superb for image
authentication.
OPTIMAL PROCESSOR MAPPING FOR LINEAR-COMPLEMENT COMMUNICATION ON HYPERCUBES AND THEIR VARIATIONS
Yomin Hou, Chien-Min Wang, Chiu-Yu Ku, Lih-Hsing Hsu
In this technical report, we address the problem of minimizing channel contention of
linear-complement communication on wormhole-routed hypercubes. Our research reveals
that, for traditional routing algorithms, the degree of channel contention of a linear-
complement communication can be quite large. To solve this problem, we propose an
alternative approach, which applies processor mapping at compile time. In this compiler
approach, processors are logically reordered according to the given communication(s) so
that the new communication(s) can be efficiently realized on the hypercube network. It is
proved that, for any linear-complement communication, there exists a reordering mapping
such that the new communication has minimum channel contention. An O(n3) algorithm is
proposed to find such a mapping for an n-dimensional hypercube. An algorithm based on
dynamic programming is also proposed to find an optimal reordering mapping for a set of
linear-complement communications. Several computer simulations have been conducted, and
the results clearly show the advantage of the proposed approach.
OSC: OPTIMAL SELECTIVE CACHING FOR VIDEO TRANSMISSION WITH PROXY SERVERS
Ray-I Chang, Shin-Hung Chang, Jan-Ming Ho
Proxylib servers have been successfully used in reducing playback latency and network bandwidth required for delivering VBR videos. By storing portions of video programs in local video proxies and the rests in remote servers, the peak and variability of network bandwidth requirements can be reduced. Regarding to which portion of video frames should be cached at higher priority, let's consider an MPEG video in which an I-frame is referenced by all the other frames in the same GOP. Obviously, losing a packet belonging to an I-frame makes it difficult to recover all the frames of the same GOP. In this paper, based on the video proxy problem introduced by [1], we present the Optimal Caching (OC) algorithm to minimize cache size required for delivering a specific video program subject to network bandwidth and client buffer size constraints, and the Optimal Selective Caching (OSC) algorithm to further select the most appropriate portions of a video program for caching in the video proxy. In our experiments, it is shown that our algorithm is more effective than the previous algorithm. Our OC and OSC algorithms reduce cache size by 50% as compared with the algorithm presented in [1]. Furthermore, the ratio of I-frames cached in the video proxy is 5 times larger than the result of applying the algorithm presented by [1]
