This paper describes User Attribute with Validity Period extension field of public key certificate and Certificate Verification Service with Time Stamp. The field and service solve the problems of unavailability of the latest revoked certificate information, large size of the revocation information and lack of non-repudiation mechanism of the X. 509 Authentication Framework. The proposed extension field is useful to reduce the revoked certificate information sent from CA of an organization where there are periodical personnel changes. The Certificate Verification Service with Time Stamp is an on-line service providing certificate status and non-repudiation service. The paper shows how the combination of the field and service solves the problems and that the server can serve hundreds of thousands of messaging system users, and the security of the service is also discussed.

In this paper we deal with the problem of calibrating a rotating and zooming camera, without 3D pattern, whose internal calibration parameters change frame by frame. First, we theoretically show the existence of the calibration parameters up to an orthogonal transformation under the assumption that the skew of the camera is zero. Auto-calibration becomes possible by analyzing inter-image homographies which can be obtained from the matches in images of the same scene, or through direct nonlinear iteration. In general, at least four homographies are needed for auto-calibration. When we further assume that the aspect ratio is known and the principal point is fixed during the sequence then one homography yields camera parameters, and when the aspect ratio is assumed to be unknown with fixed principal point then two homographies are enough. In the case of a fixed principal point, we suggest a method for obtaining the calibration parameters by searching the space of the principal point. If this is not the case, then nonlinear iteration is applied. The algorithm is implemented and validated on several sets of synthetic data. Also experimental results for real images are given.

This letter proposes an initial frame synchronization algorithm for orthogonal frequency division multiplexing (OFDM) systems. Since the proposed scheme utilizes only the cyclic prefix and the phase shift of the demodulated data without the aid of any known signals, it can be applied not only at the beginning of data transmission but also at any instant during transmission. The performance of the proposed algorithm is confirmed by computer simulation for QPSK, 8-PSK, and 16-QAM systems.

We present two estimation methods for camera rotation from two images obtained by the active camera before and after rotation. Based on the representation of the projected rotation group, quasi moment features are constructed. Camera rotation can be estimated by applying the singular value decomposition (SVD) or Newton's method to tensor quasi moment features. In both cases, we can estimate 3D rotation of the active camera from only two projected images. We also give some experiments for the estimation of the actual active camera rotation to show the effectiveness of these methods.

An optimum representative-frames (r-frames) selection method using step-wise function approximation has been developed to provide automatic indexing for a video-query-agent (VQA) system. It uses dynamic programming to simultaneously select the r-frames and corresponding segment boundaries. Experiments showed that the approximation error of the selected r-frames was less than that of two conventional methods. Retrieval experiments using a feature-based image-search engine showed that the proposed method is more robust and effective than the two conventional methods. The proposed method was implemented in a VQA system and processing time was evaluated. The results showed that the processing time for indexing was shorter than that of the conventional method.

IC interconnect transmission line effects due to the characteristics of a silicon substrate and current return path impedances are physically investigated and experimentally characterized. With the investigation, a novel transmission line model is developed, taking these effects into account. Then an accurate signal delay on the IC interconnect lines is analyzed by using the transmission line model. The transmission line effects of the metal-insulator-semiconductor IC interconnect structure are experimentally verified with s-parameter-based wafer level signal-transient characterizations for various test patterns. They are designed and fabricated with a 0.35 µm CMOS process technology. Throughout this work, it is demonstrated that the conventional ideal RC- or RLC-model of the IC interconnects without considering these detailed physical phenomena is not accurate enough to verify the pico-second level timing of high-performance VLSI circuits.

This paper proposes an intelligent image interpolation method based on Cubic Hermite procedure for improving digital images. Image interpolation has been used to create high-resolution effects in digitized image data, providing sharpness in high frequency image data and smoothness in low frequency image data. Most interpolation techniques proposed in the past are centered on determining pixel values using the relationship between neighboring points. As one of the more prevalent interpolation techniques, Cubic Hermite procedure attains the interpolation with a 3rd order polynomial fit using derivatives of points and adaptive smoothness parameters. Cubic Hermite features many forms of a curved shape, which effectively reduce the problems inherent in interpolations. This paper focuses on a method that intelligently determines the derivatives and adaptive smoothness parameters to effectively contain the interpolation error, achieving significantly improved images. Derivatives are determined by taking a weighted sum of the neighboring points whose weighting function decreases as the intensity difference of neighboring points increases. Smoothness parameter is obtained by training an exemplar image to fit into the Cubic Hermite function such that the interpolation error is minimized at each interpolating point. The simulations indicate that the proposed method achieves improved image results over that of conventional methods in terms of error and image quality performance.

The construction of photo-realistic 3D scenes from video data is an active and competitive area of research in the fields of computer vision, image processing and computer graphics. In this paper we address our recent work in this area. Unlike most methods of 3D scene construction, we consider the generation of virtual environments from video sequence with a video-cam's forward motion. Each frame is decomposed into sub-images, which are registered correspondingly using the Levenberg-Marquardt iterative algorithm to estimate motion parameters. The registered sub-images are correspondingly pasted together to form a pseudo-3D space. By controlling the position and direction, the virtual camera can walk through this virtual space to generate novel 2D views to acquire an immersive impression. Even if the virtual camera goes deep into this virtual environment, it can still obtain a novel view while maintaining relatively high resolution.

Designing a protocol to exchange a secret key is one of the most fundamental subjects in cryptography. Using a random deal of cards, pairs of card players (agents) can share secret keys that are information-theoretically secure against an eavesdropper. A key set protocol, which uses a random deal of cards, can perform an Eulerian secret key exchange, in which the pairs of players sharing secret keys form an Eulerian circuit passing through all players. Along the Eulerian circuit any designated player can send a message to the rest of players and the message can be finally sent back to the sender. Checking the returned message with the original one, the sender can know whether the message circulation has not been influenced by a possible single transmission error or false alteration. It has been known that any Eulerian circuit formed by the protocol has length at most 3/2k, where k is the number of players. Note that the length corresponds to the time required to send the message to all players and acknowledge the secure receipt. In this paper, we show that the average length of Eulerian circuits is approximately k+ln k.

The classical game of peg solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. One of the classical problems concerning peg solitaire is the feasibility issue. An early tool used to show the infeasibility of various peg games is the rule-of-three [Suremain de Missery 1841]. In the 1960s the description of the solitaire cone [Boardman and Conway] provides necessary conditions: valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper, we recall these necessary conditions and present new developments: the lattice criterion, which generalizes the rule-of-three; and results on the strongest pagoda functions, the facets of the solitaire cone.

In this letter we propose a new Shape from Focus (SFF) method using piecewise curved search windows for accurate 3-D shape recovery. The new method uses piecewise curved windows to compute focus measure and to search for Focus Image Surface (FIS) in image space. The experimental result shows that our new method gives more accurate result than the previous SFF methods.

Given a combinatorial problem on a set of weighted elements, if we change the weight using a parameter, we obtain a parametric version of the problem, which is often used as a tool for solving mathematical programming problems. One interesting question is how to describe and analyze the trajectory of the solution. If we consider the trajectory of each weight function as a curve in a plane, we have a set of curves from the problem instance. The curves induces a cell complex called an arrangement, which is a popular research target in computational geometry. Especially, for the parametric version of the problem of computing the minimum weight base of a matroid or polymatroid, the trajectory of the solution becomes a subcomplex in an arrangement. We introduce the interaction between the two research areas, combinatorial optimization and computational geometry, through this bridge.

A reliable and automatic parameter extraction technique for DFB lasers is developed. The parameter extraction program which is named "LAPAREX" is able to determine many device parameters from a measured sub-threshold spectrum only, including gain- and index-coupling coefficients, and spatial phases of the grating at front and rear facets. Injection current dependence of coupling coefficients in a gain-coupled DFBlaser is observed, for the first time, by making use of it.

This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.

This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

It is important to establish the technology to accommodate best effort TCP/IP traffic over wide area ATM networks. The UBR (Unspecified Bit Rate) service category is the most typical service category for the best effort traffic, especially in the LAN environment. On the other hand, the VBR (Variable Bit Rate) service category with SCD (Selective Cell Discard) option is considered as the service category which is appropriate for wide area networks due to its fairness and minimum guarantee of the cell transmission using not only PCR (Peak Cell Rate) but SCR (Sustainable Cell Rate) and MBS (Maximum Burst Size). However, there is no actual evaluation for such service. We have, therefore, performed the experimental studies on TCP/IP over VBR with SCD along with UBR and VBR without SCD by VC (Virtual Channel) level policing when each TCP connection is mapped to a different VC. Through these experiments, we measured the link utilization of the effective data and the fairness between each obtained TCP throughput during the congestion of the ATM switch. From the results of the link utilization, the value is over 95% under the various conditions. Therefore, even in the case of the cell losses due to SCD or buffer overflow in ATM switch congestion, average throughput is almost the same as the value which equals the trunk line speed divided by the number of the accommodated TCP connections. From the results of the fairness, VBR with SCD per VC is better than UBR and also obtains better TCP throughput than VBR without SCD. Furthermore, to confirm those characteristics more generally, we adopt the accommodated TCP connections not only with the same TCP send/receive socket buffer size but with different sizes. Finally, we discuss the effectiveness between VBR with SCD and the other service categories, such as UBR and ABR (Available Bit Rate) and GFR (Guaranteed Frame Rate), and conclude that VBR with SCD is one of the most suitable ATM service categories for accommodating best effort traffic.

Muscle based face image synthesis is one of the most realistic approaches to the realization of a life-like agent in computers. A facial muscle model is composed of facial tissue elements and simulated muscles. In this model, forces are calculated effecting a facial tissue element by contraction of each muscle string, so the combination of each muscle contracting force decides a specific facial expression. This muscle parameter is determined on a trial and error basis by comparing the sample photograph and a generated image using our Muscle-Editor to generate a specific face image. In this paper, we propose the strategy of automatic estimation of facial muscle parameters from 2D markers'movements located on a face using a neural network. This corresponds to the non-realtime 3D facial motion capturing from 2D camera image under the physics based condition.

Various kinds of high bandwidth architecture using the embedded DRAM technology have been presented previously. In most cases, they use wide bus implementation and/or fast bus speed, that both have the penalty of die area and much power consumption at the same time. The proposing single-ended read-modify-write bus increases the bandwidth twice as high, while it maintains the same bus size and the same bus speed. The data-bus comprises 1 k-bit read-bus and 1 k-bit write-bus that each works concurrently, and has amplitude from 0 V to 1 V, hence the measured power consumption is only 0.3 W at a frequency of 166 MHz. A programmable page-size reduces the page miss-rate and efficiently improves the bandwidth that is comparable to the wide bus and fast speed approach. All the proposing features are implemented on a 3D frame-buffer to achieve 42.4 G-BPS bandwidth.

To provide QoS guarantees for each connection, efficient scheduling algorithms, such as WFQ, have been proposed. These algorithms assume a certain amount of buffer is allocated for each connection to provide loss free transmission of packets. This buffer allocation policy, however, requires much buffer space especially when many connections are sharing a link. In this paper we propose the use of partial buffer sharing (PBS) policy combined with usage parameter control (UPC) for efficient buffer management and flexible QoS control in ATM switches. We evaluate the feasibility of the proposed method by solving a Markov model. We also show that using the proposed method, we can control the cell loss ratio (CLR) independently of the delay. Numerical evaluations are presented, which indicates the PBS combined with UPC significantly reduces the buffer size required to satisfy given cell loss ratios.

This paper addresses output regulation for nonlinear systems driven by a time varying parameter. The derivative information of the time varying parameter is necessary for the improved regulation performance but it is not readily available in general. In this paper, we propose a velocity estimation of the time varying parameter for use in the control law without amplifying noise signals.