Surface reconstruction and visualization from sparse and incomplete surface data is a fundamental problem and has received growing attention in both computer vision and graphics. This paper presents a computational scheme for realistic visualization of free-formed surfaces from 3D range images. The novelty of this scheme is that by integrating computer vision and computer graphics techniques, we dynamically construct a mesh representation of the arbitrary view of the surfaces, from a view-invariant shape description obtained from 3D range images. We outline the principle of this scheme and describle the frame work of a graphical reconstruction model, we call arbitrarily oriented meshes', which is developed based on differential geometry. The experimental results on real range data of human faces are shown.

We describe an approach to describe moving pictures in terms of their structural properties for video editing, video indexing, and video coding. The description contains 2D shape, motion, spatial relation, and relative depth of each region. To obtain the description, we develop the incremental segmentation scheme which includes dynamic occlusion analysis to determine relative depths of several objects. The scheme has been designed along the analysis-by-synthesis" approach, and uses a sequence of images to estimate object boundaries and motion information successively/incrementally. The scheme consists of three components: motion estimation, prediction with dynamic occlusion analysis, and update of the segmentation results. By combining the information from extended (longer) image sequences, and also by treating the segmentation and dynamic occlusion analysis simultaneously, the scheme attempts to improve successively over time the accuracy of the object boundary and motion estimation.

An efficient technique for expressing document image is required as part of a unified approach to document image processing. This paper presents a new method, Minimum Covering Run (MCR), for expressing binary images. The name being adapted from horizontal or vertical run representation. The proposed technique uses some horizontal and vertical runs together to represent binary images in which the total number of representative runs is minimized. Considering the characteristic of above run types precisely, it is shown that horizontal and vertical runs of any binary image could be thought of as partite sets of a bipartite graph. Consequently, the MCR expression that corresponds to the construction of one of the most interesting problems in graphs; i.e., maximum matching, is analogously found by using an algorithm which solves this problem in a corresponding graph. The most efficient algorithm takes at most O(n5/2) computations for solving the problem where n is the sum of cardinalities of both partite sets. However, some patterns in images like tables or line drowings, generally, have a large number of runs representing them which results in a long processing time. Therefore, we provide the Rectangular Segment Analysis (RSA) as a pre-processing to define runs representing such patterns beforehand. We also show that horizontal and vertical covering parts of the proposed expression are able to represent stroke components of characters in document images. As an implementation, an efficient algorithm including arrangement for run data structure of the MCR expression is presented. The experimental results show the possibility of stroke extraction of characters in document images. As an application, some patterns such as tables can be extracted from document images.

This paper describes a method for describing a three-dimensional (3-D) scene by integrating color and range data. Range data is obtained by a feature-based stereo method developed in our laboratory. A color image is segmented into uniform color regions. A plane is fitted to the range data inside a segmented region. Regions are classified into three types based on the range data. A certain types of regions are merged and the others remain unless the region type is modified. The region type is modified if the range data on a plane are selected by removing of the some range data. As a result, the scene is represented by planar surfaces with homogeneous colors. Experimental results for real scenes are shown.

Practical linewidth measurement accuracy better than 0.02 µm 3 sigma that meets the production requirement for devices with sub-half micron features, was achieved in a field emission scanning electron-beam metrology system (Hitachi S-7000). In order to establish high accuracy linewidth measurement, it was found in the study that reduction of electron-beam diameter and precise control of operating conditions are significantly effective. For the purpose of reducing electron-beam diameter, a novel electron optical system was adopted to minimize the chromatic aberration which defines electron-beam profile. As a result the electron beam diameter was reduced from 20 nm to 16 nm. In order to reduce measurement uncertainties associated with actual operating conditions, a field emission electron gun geometry and an objective lens current monitor were investigated. Then the measurement uncertainties due to operating conditions was reduced from 0.016 µm to 0.004 µm.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).

Subjective quality tests have proven that embedded adaptive differential PCM (ADPCM), known to tolerate information loss through bit dropping, does not maintain sufficient speech quality when directly applied to asynchronous transfer mode (ATM) due to the fixed-length cell transmission scheme unique to ATM. We propose a coding and transmission scheme which enhances the performance by adjusting the embedded ADPCM coding rate according to input speech characteristics, thereby taking advantage of the ATM environment, where the transmission of variable rate sources is feasible. By varying the number of code bits of an embedded ADPCM coder from 6bits per sample, or 48kbps, for blocks of speech with a high prediction gain, to 2bits, or 16kbps, for silent blocks, a good compromise between coding bit rate and speech quality with gradual degradation due to information loss is achieved. The results of subjective evaluation tests showed the speech quality of the proposed scheme to be over 3.5 mean opinion score (MOS) on a scale of 1 to 5 at a cell loss rate of 10%. A prototype of the codec and the ATM cell assembly/disassembly functions were also fabricated using 3 conventional digital signal processors (DSPs) for real-time conversation tests.

The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).

The path diversity improvement inherent in direct sequence spread spectrum (DS/SS) signalling under multi-path propagation environments is investigated for mobile/personal radio communications systems that employ DPSK modulation. The bit error rate (BER) performance of post-demodulation selection diversity reception is theoretically analyzed in the presence of noise-only-paths in the time window for diversity combining. Results of laboratory experiments conducted to evaluate the BER performance are also presented. It is shown that the experimental results agree well with the theoretical BER.

Optical soliton transmissions at 10 and 20Gbit/s over 1000km with the use of erbium-doped fiber amplifiers are described in detail. For the 10Gbit/s experiment, a bit error rate (BER) of below 110-13 was obtained with 220-1 pseudorandom patterns and the power penalty was less than 0.1dB. In the 20Gbit/s experiment optical multiplexing and demultiplexing techniques were used and a BER of below 110-12 was obtained with 223-1 pseudorandom patterns under a penalty-free condition. A new technique for sending soliton pulses over ultralong distances is presented which incorporates synchronous shaping and retiming using a high speed optical modulator. Some experimental results over 1 million km at 7.210Gbit/s are described. This technique enables us to overcome the Gordon-Haus limit, the accumulation of amplified spontaneous emission (ASE), and the effect of interaction forces between adjacent solitons. It is also shown by computer runs and a simple analysis that a one hundred million km soliton transmission is possible by means of soliton transmission controls in the time and frequency domains. This means that limit-free transmission is possible.

We have proposed a new omnidirectional image sensor COPIS (COnic Projection Image Sensor) for guiding navigation of a mobile robot. Its feature is passive sensing of the omnidirectional image of the environment in real-time (at the frame rate of a TV camera) using a conic mirror. COPIS is a suitable sensor for visual navigation in real world environment with moving objects. This paper describes a method for estimating the location and the motion of the robot by detecting the azimuth of each object in the omnidirectional image. In this method, the azimuth is matched with the given environmental map. The robot can always estimate its own location and motion precisely because COPIS observes a 360 degree view around the robot even if all edges are not extracted correctly from the omnidirectional image. We also present a method to avoid collision against unknown obstacles and estimate their locations by detecting their azimuth changes while the robot is moving in the environment. Using the COPIS system, we performed several experiments in the real world.

It is shown from a computer analysis that there exists a resonant mode of a surface wave which propagates along Goubau line, and that the attenuation of such a mode is very low. The approximate formula for obtaining the resonant frequency is also given.

The transmission of HDTV signals on digital networks requires adoption of sophisticated compression techniques to limit the bit-rate requirements and to provide a high-quality and reliable services to customers. This paper describes system design and transmission characteristics of an adaptive subband DCT codec that can encode original 1.2Gb/s HDTV signals at 156Mb/s. The performance of the codec was evaluated using motion picture signals. The characteristics obtained with the codec was found to maintain good picture quality.

This paper studies a method for a parallel implementation of digital half toning technique, which converts continuous tone images into monotone one without losing fidelity of images. A new modified algorithm for half toning is proposed, which is able to be implemented on a rectangular or one dimensional parallel multi-processor array as a part of extensions of space partitioning image processings. The purpose of this paper is primarily to apply space partitioning local image processing technique to nonlinear recursive algorithms. The target is to achieve a fast half toning with high quality. For that propose, local directional error diffusion techniques will be introduced, which enable original recursive error diffusion half toning to be converted into a local processing algorithm without losing its original advantages of producing high quality images. The characteristics of proposed methods will be analyzed and the advantages of our algorithm of high speed processing and high quality will be demonstrated by showing the results of simulations for typical examples.

The three layer neural network (TLNN) is treated, where the nonlinearity of a neuron is of signum. First we propose an expression of the discriminant function of the TLNN, which is called a linear-homogeneous expression. This expression allows the differentiation in spite of the signum property of the neuron. Subsequently a learning algorithm is proposed based on the linear-homogeneous form. The algorithm is an error-correction procedure, which gives a mathematical foundation to heuristic error-correction learnings described in various literatures.

This paper proposes an off-line text-independent writer identification method applicable to Japanese and Korean sentences. It is assumed that the writer of a writing in question exists in a certain group of people and that reference writings written by each person in the group can be used for identification. In the proposed method, relative frequencies of some model patterns are counted on the binary pattern of each writing and are used as the feature to measure the distance between two writings. Based on a modified Mahalanobis' distance for this feature, the person whose reference writing is nearest to the writing in question is judged as the writer. The effectiveness of the proposed method is examined through an experiment using Japanese and Korean writings. Error rates in the experiment were different depending on conditions such as volume of reference writings, dimension of adopted features, and number of people to be identified. In some cases, error rates as low as 0% were observed. Error rates tend to be lower in Korean writings probably because Hangul is composed of a smaller number of letters compared to Kanji and Hiragana in Japanese writing.

Mathematical morphology clarified geometrical properties of shape analysis algorithms for binary pictures. Results of labelling, distance transform, and adjacent numbering are, however, coded pictures. For full descriptions of shape analysis algorithms in the framework of mathematical morphology, it is necessary to extend morphological operations to code-labelled pictorial data. Nevertheless, extensions of morphology to code-labelled pictures have never discussed though the theory of gray morphology is well studied by several authors. Hence, this paper proposes a theory of the coded morphology which is based on the binary scaling of labels of pixels. The method uses n-layered binary sub-pictures for the processing of a picture with 2n labels. By introducing morphological operations for the coded point sets, we express some coding functions in the manner of the mathematical morphology. We also derive multidimensional array registers and gates which store and process coded pictures and morphological operations to them by proposing basic gates which compute parallelly logical operations for elements of Boolean layered arrays. These gates and registers are suitable for the implementation of the shape analysis processors on the three-dimensional VLSI and ULSI.

Periodic schedules are seldom treated in the theory but abound in practice (air flight schedule, train schedule, manufacturing schedule, etc). This paper introduces a Petri Net based perspective to periodic schedules. These are classified, according to the time interpretation into single-server and multiple-server semantics and, according to transitions firing periodicity constraints, into strict and general periodic schedules. Using a net transformation rule, the computation of the general schedule class can be done through techniques for the strict subclass. Introducing truncation error terms ε for the floor functions, a necessary and sufficient condition for the feasibility of a strict periodic schedule is given in terms of a large size system of nonlinear inequalities containing ε terms. Moreover averaging this condition on subperiods allows to get a small size linear system of inequalities as necessary conditions for speeding up iterative computation processes. This paper aims to present qualitative analysis of periodic schedules for deterministically timed Petri net systems, as a precursor to quantitative analysis that requires large-scale computational experiments and hence will be dealt in later work.

This paper presents an optimal constraint graph generation algorithm for graph-based one-dimensional layout compaction. The first published algorithm for this problem was the shadow-propagation algorithm. However, without sophisticated implementation of a shadow-front, complexity of the algorithm could fall into O(n2), where n is the number of layout objects. Although our algorithm, called the enhanced plane-sweep based graph generation algorithm, is an extension of the shadow-propagation algorithm, such a drawback is resolved by introducing an enhanced plane-sweep technique. The algorithm maintains multiple shadow-fronts simultaneously by storing them in a work-list called previous-boundary. Since a balanced search tree is selected for implementation of the worklist, total complexity of the algorithm is O(n log n) which is optimal. Experimental results show that the enhanced plane-sweep based graph generation algorithm runs in almost linear time with respect to the number of layout objects and is faster than the perpendicular plane-sweep algorithm which is also optimal in terms of time complexity.