The Hilbert curve is one of the simplest curves which pass through all points in a space. Many researchers have worked on this curve from the engineering point of view, such as for an expression of two-dimensional patterns, for data compression in an image or in color space, for pseudo color image displays, etc. A computation algorithm of this curve is usually based on a look-up table instead of a recursive algorithm. In such algorithm, a large memory is required for the path look-up table, and the memory size becomes proportional to the image size. In this paper, we present an implementation of a fast sequential algorithm that requires little memory for two and three dimensional Hilbert curves. Our method is based on some rules of quad-tree traversal in two dimensional space, and octtree traversal in three dimensional space. The two dimensional Hilbert curve is similar to the scanning of a DF (Depth First) expression, which is a quad-tree expression of an image. The important feature is that it scans continuously from one quadrant, which is obtained by quad tree splitting, to the next adjacent one in two dimensional space. From this point, if we consider run-lengths of black and white pixels during the scan, the run-lengths of the Hilbert scan tend to be longer than those of the raster scan and the DF expression scanning. We discuss the application to data compression using binary images and three dimensional data.

We propose a design method for a two-channel perfect reconstruction FIR filter banks employing linear-phase filters. This type of filter bank is especially important in splitting image signals into frequency bands for subband image cording. Because in such an application, it is necessary to use the combination of linear-phase filters and symmetric image signal, namely linear phase signal to avoid the increase in image size caused by filtering. In this paper, first we summarize the design conditions for two-channel filter banks. Next, we show that the design problem is reduced to a very simple linear equation, by using a half-band filter as a lowpass filter. Also the proposed method is available to lead filters with fewer complexity, which enable us to use simple arithmetic operations. For subband coding, the property is important because it reduces hardware complexity.

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.

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.

A new redundancy technique especially suitable for ultra-high-speed static RAMs (SRAMs) has been developed. This technique is based on a decoding-method that uses two kinds of fuses without introducing any additional delay time. One fuse is initially ON and can be turned OFF afterwards, if necessary, by a cutting process using a focused ion beam (FIB). The other is initially OFF and can be turned ON afterwards by a connecting process using laser chemical vapor deposition (L-CVD). This technique is applied to a 64 kbit SRAM having a 1.5-ns access time. The experimental results obtained through an SRAM chip repaired using this redundancy technique show that this technique does not introduce any increase in the access time and does not reduce the operational margin of the SRAM.

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 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.

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.

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.

This paper describes a novel but simple method of implementing waveform relaxation technique for bipolar circuits involving ECL gates. This method performs gate level partitioning of ECL circuits not only during the cutoff state of the input transistor but also when the input transistor is in its active state. Partitioning at all times has become possible due to the favorable property of input and output stages of ECL gates. It is shown that this method is faster than direct method even when the circuits containing only few gates is simulated. Further, it is shown that the present method is applicable to the case where the interconnections between the ECL gates is treated as lossy transmission lines.

This paper focuses on methodology underlying the application to fault tolerant computer systems with "no down communication" capability of stochastic Petri nets with general firing times. Based on a formal specification of the stochastic Petri net, we provide criteria for the marking process to be a regenerative process in continuous time with finite cycle-length moments. These results lead to strongly consistent point estimates and asymptotic confidence intervals for limiting system availability indices. We also show how the building blocks of stochastic Petri nets with general firing times facilitate the modeling of non-deterministic transition firing and illustrate the use of "interrupter input places" for graphical representation of transition interruptions.

Selective epitaxial growth technology has been extended to the base formation of a transistor on the basis of the SATURN (Self-Alignment Technology Utilizing Reserved Nitride) process, a high-speed bipolar LSI processing technology. The formation of a self-aligned base contact, coupled with SIC (Selective Ion-implanted Collector) fabricated by lowenergy ion implantation, has not only narrowed the transistor active regions but has drastically reduced the base width. A final base width of 800 and a maximum cut-off frequency of 31 GHz were achieved.

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).

This paper describes the novel relaxation-based algorithm for the harmonic analysis of nonlinear circuits. First, we present Iterated Spectrum Analysis based on harmonic balance method, where the harmonic balance method is applied to every node independently. As a result, we can avoid dealing with large scale Jacobian matrices and reduce the total simulation time, compared with the conventional method based on Galerkin's procedure or the harmonic balance method. Next, we define the frequency domain latency. Furthermore, we refer to the possibility for exploitation of three types of latency, i.e., relaxation iteration latency, frequency domain latency and Newton iteration latency. And we propose the multirate-sampling technique based on the consideration of the frequency domain latency. Finally, we apply the present technique to the simple analog circuit simulation and verify its availability for the harmonic analysis.

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.

A speech analysis/synthesis system that relies on a time-varying Auto Regressive Moving Average (ARMA) process and the Short-Time Fourier Transform (STFT) is proposed. The narrowband components in speech are represented in the frequency domain by a set of harmonic components, while the broadband random components are represented by a time-varying ARMA process. The time-varying ARMA model has a dual function, namely, it creates a spectral envelope that fits accurately the harmonic STFT components, and provides for the spectral representation of the broadband components of speech. The proposed model essentially combines the features of waveform coders by employing the STFT and the features of traditional vocoders by incorporating an appropriately shaped noise sequence.

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 minimum transferable linewidth by X-ray is derived using waveguide analysis. The minimum width is determined by the refractive index of the absorber and does not depend on the X-ray wavelength. Therefore there is an optimum mask aperture size which provides the minimum linewidth. By using Au as the absorber, 8 nm linewidth is attainable.

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.

Correspondence based on regions rather than lines seems to be effective, as regions are usually fewer than other image features and provide global information such as size, color, adjacency, etc. In this paper, we present a region matching approach for solving the correspondence problem. Images are segmented into regions and are individually described by classification tables using region adjacencies. From the structural description of the two images, the region matching process based on color and structural similarity is carried out. First, a small number of significant regions are selected and matched by using color, and then they are used as handles for constraint propagation to match the remaining regions by using structures. Our technique was implemented by using an efficient selection and propagation algorithm and was tested with a variety of scenes.