Hiroyuki DEGUCHI Masanori MASUDA Takashi EBISUI Yutaka SHIMAWAKI Nobuharu UKITA Katsunori M. SHIBATA Masato ISHIGURO
A best-fit panel model in the radio holographic metrology taking into account locations and sizes of actual surface panels in a large reflector antenna is presented. A displacement and tilt of each panel can be estimated by introducing the best-fit panel model. It was confirmed by simulations that the distinction can be drawn between a continuous surface error and a discontinuous one. Errors due to truncation of the radiation pattern were calculated by simulations. It was found that a measurement of a 128128 map is optimum for the 45-m telescope. The reliability of the measurements using this model was examined by experiments with panel displacements. Panel adjustments using the best-fit panel model successfully improved the surface accuracy of the antenna from 138µm rms to 84µm rms (/D=210-6).
In this paper, we propose a polynomial time algorithm for computing the expected maximum number of vertex-disjoint s-t paths in a probabilistic basically series-parallel directed graph and a probabilistic series-parallel undirected graph with distinguished source s and sink t(st), where each edge has a mutually independent failure probability and each vertex is assumed to be failure-free.
Sailing HE Rasmus HELLBERG Vaughan H. WESTON
The invariant imbedding method combined with the time domain wave splitting technique is applied to the inverse problem for the telegraph equation t2u=(1/r)(pu)-btu+qu in a stratified half-space. The zeroth, second and fourth moments of the 3-D fields are used to reduce the three-dimensional problem to a set of one-dimensional problems. The imbedding equations for R0, R2 and R4, respectively the zeroth, second and fourth moments of the reflection operator, are derived. Numerical results for the reconstruction are presented using the reflection data on the surface.
Sin-ichi FUKUZAWA Hiroshi YOSHINO Shinji ISHIDA Kenji KONDOH Tsuyoshi YOSHII Naoaki AIZAKI
256 MbDRAM chips have been fabricated by mix-and-match method using high NA KrF excimer laser stepper and i-line stepper. In the case of KrF stepper, the negative siloxane resist is used for rectangular and wiring patterns and the positive novolak-resin resist is used for hole patterns. Both of these two kinds of resist produce accurate pattern shape, allow-able pattern profile, satisfactory depth of focus and sufficient overlay accuracy for device fabrication in 0.25 µm design rule.
Makoto HIRAYAMA Eric Vatikiotis-BATESON Mitsuo KAWATO
This paper focuses on two areas in our effort to synthesize speech from neuromotor input using neural network models that effect transforms between cognitive intentions to speak, their physiological effects on vocal tract structures, and subsequent realization as acoustic signals. The first area concerns the biomechanical transform between motor commands to muscles and the ensuing articulator behavior. Using physiological data of muscle EMG (electromyography) and articulator movements during natural English speech utterances, three articulator-specific neural networks learn the forward dynamics that relate motor commands to the muscles and motion of the tongue, jaw, ant lips. Compared to a fully-connected network, mapping muscle EMG and motion for all three sets of articulators at once, this modular approach has improved performance by reducing network complexity and has eliminated some of the confounding influence of functional coupling among articulators. Network independence has also allowed us to identify and assess the effects of technical and empirical limitations on an articulator-by-articulator basis. This is particularly important for modeling the tongue whose complex structure is very difficult to examine empirically. The second area of progress concerns the transform between articulator motion and the speech acoustics. From the articulatory movement trajectories, a second neural network generates PARCOR (partial correlation) coefficients which are then used to synthesize the speech acoustics. In the current implementation, articulator velocities have been added as the inputs to the network. As a result, the model now follows the fast changes of the coefficients for consonants generated by relatively slow articulatory movements during natural English utterances. Although much work still needs to be done, progress in these areas brings us closer to our goal of emulating speech production processes computationally.
Yoichi NAGAO Hironobu URABE Shinichi NAKANO Sadatoshi KUMAGAI
We describe K-NET, a support system for development of sequence control programs. The K-NET description model is based on the colored Petri net and timed Petri net. K-NET concisely expresses sequence control flow including synchronization, interlock and concurrence, and provides high-level data processing by being combined with a conventional procedural language. K-NET has an editor, simulator, generator, reporter and monitor to support the control program development procedure ranging from basic and detail design to programming and testing. We have added a new function to K-NET so it assists development of control programs for programmable controllers, and have applied it to an automatic bolt supplying system. The operation results are satisfactory.
Naozo SUGIMOTO Chikao UYAMA Tetsuo SUGAHARA Yoshio YANAGIHARA
To derive blood flow dynamics from cineangiograms (CAG), we have developed an image processing algorithm to estimate a two-dimensional blood fiow velocity map projected on CAG. Each image area of CAG is diveded into blocks, and it is assumed that the movement of the contrast medium between two serial frames is restricted only to adjacent blocks. By this assumption, a fundamental equation" and the maximum flow constraints" are derived. The equation and constraints state the relationship between the volume of contrast medium in each block and the flow components" that are the volumes of contrast medium flowing from/to its adjacent blocks. The initial guess" that is a set of approximately obtained flow components is corrected using these relationships. The corrected flow components are then transformed into blood flow velocities, which are illustrated in the form of a needle diagram. In numerical experiments, the estimation error between the real flow velocity generated artificially and the flow velocity estimated with our algorithm was evaluated under one of the worst conditions. Although the maximum error was fairly large, the estimated flow velocity map was still acceptable for visual inspection of flow velocity pattern. We then applied our algorithm to an abdominal CAG (clinical data). The results showed flow stagnation and reverse flow in the abdominal aneurysm, which are consistent with the presence of a thrombus in the aneurysm. This algorithm may be a useful diagnostic tool in the assessment of vascular disease.
Shoichiro YAMADA Shunichi NAKAYAMA
We propose a new multiple folding algorithm for the gate matrix layout, and apply it to generation of rectangular blocks with flexible size. The algorithm consists of two phases, the net partitioning and the gate arangement, and both algorithms are based on the multi-way mini-cut technique. In the first and second phases, the width and height of the multiple folded gate matrix block are directly minimized, resperctively, such that the area is minimized and desired aspect ratio of the block is obtained. The features of the present algorithm are as hollows: (1) Dead space on the gate matrix block can be minimized, (2) the aspect ratio can be controlled finely, (3) since polar graphs are successfully used in the second phase, the efficiency of the algorithm can be much improved. The experimental results show the effectiveness of our algorithm.
Kiyoshi MIKAMI Hiroshi TAMURA Masakazu SENGOKU Yoshio YAMAGUCHI
The synchronic distance is a fundamental concept in a Petri net. Marked graphs form a subclass of Petri nets. Given a matrix D, we are interested in the problem of finding a marked graph whose synchronic distance matrix is D. It is wellknown that the synchronic disrance matrix of a marked graph is a distance matrix. In this letter, we give a matrix D such that D is a distance matrix and there does not exist a marked graph whose synchronic distance matrix is D.
This paper describes fundamental system of borehole radars and its recent progress in Japan. Early development of borehole radars were carried out for detection of cracks in crystallized rock, however, the fields of applications are expanding to other various objects such as soil and sedimental rocks. Conventionally developed radar systems are not necessarily suitable for these applications and they must be modified. New technologies such as radar polarimetry and radar tomography were also introduced.
This paper considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. By the way, a graph is called an almost tree if E(B)V(B)+ K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K0 if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem.
A hardware algorithm for modular inversion is proposed. It is based on the extended Euclidean algorithm. All intermediate results are represented in a redundant binary representation with a digit set {0, 1,1}. All addition/subtractions are performed without carry propagation. A modular inversion is carried out in O (n) clock cycles where n is the word length of the modulus. The length of each clock cycle is constant independent of n. A modular inverter based on the algorithm has a regular cellular array structure with a bit slice feature and is very suitable for VLSI implementation. Its amount of hardware is proportional to n.
Takanori NAGAE Takeshi AGUI Hiroshi NAGAHASHI
An algorithm interpolating parallel cross-sections between CT slices is described. Contours of equiscalar or constant-density surfaces on cross-sections are directly obtained as non-intersecting loops from grayscale slice images. This algorithm is based on a general algorithm that the authors have proposed earlier, constructing triangulated orientable closed surfaces from grayscale volumes and is particularly suited for a new technique, called laser stereolithography, which creates real 3D plastic objects using UV laser to scan and harden liquid polymer. The process of laser stereolithography is executed slice by slice, and this technique really requires some interpolation of intermediate cross-sections between slices. For visualizing, surfaces are only expected to be shaded almost continuously. The local defects are invisible and not cared about if the picture resolution is rather poor. On the contrary, topological faults are fatal to construct solid models by laser stereolithography, i.e., every contour line on cross-sections must be closed with no intersection. Not a single break of a contour line is tolerated. We already have many algorithms available for equiscalar surface construction, and it seems that if we cut the surfaces, then contour lines could be obtained. However, few of them are directly applicable to solid modeling. Marching cubes algorithm, for example, does not ensure the consistency of surface topology. Our algorithm guarantee an adequate topology of contour lines.
Dong Su SEONG Ho Sung KIM Kyu Ho PARK
In this paper, we define an attributed random graph, which can be considered as a generalization of conventional ones, to include multiple attributes as well as numeric attribute instead of a single nominal attribute in random vertices and edges. Then we derive the probability equations for an attributed graph to be an outcome graph of the attributed random graph, and the equations for the entropy calculation of the attributed random graph. Finally, we propose the application areas to computer vision and machine learning using these concepts.
Takanobu BABA Akehito GUNJI Yoshifumi IWAMOTO
A network-topology-independent static task allocation strategy has been designed and implemented for massively parallel computers. For mapping a task graph to a processor graph, this strategy evaluates several functions that represent some intuitively feasible properties or the graphs. They include the connectivity with the allocated nodes, distance from the median of a graph, connectivity with candidate nodes, and the number of candidate nodes within a distance. Several greedy strategies are defined to guide the mapping process, utilizing the indicated function values. An allocation system has been designed and implemented based on the allocation strategy. In experiments we have defined about 1000 nodes in task graphs with regular and irregular topologies, and the same order of processors with mesh, tree, and hypercube topologies. The results are summarized as follows. 1) The system can yield 4.0 times better total communication costs than an arbitrary allocation. 2) It is difficult to select a single strategy capable of providing the best solutions for a wide range of task-processor combinations. 3) Comparison with hypercube-topology-dependent research indicates that our topology-independent allocator produces better results than the dependent ones. 4) The order of computaion time of the allocator is experimentally proved to be O (n2) where n represents the number of tasks.
Du-Yih TSAI Hiroshi FUJITA Katsuhei HORITA Tokiko ENDO Choichiro KIDO Sadayuki SAKUMA
We applied an artificial neural network approach identify possible tumors into benign and malignant ones in mammograms. A sequential-dependence technique, which calculates the degree of redundancy or patterning in a sequence, was employed to extract image features from mammographic images. The extracted vectors were then used as input to the network. Our preliminary results show that the neural network can correctly classify benign and malignant tumors at an average rate of 85%. This accuracy rate indicates that the neural network approach with the proposed feature-extraction technique has potential utility in the computer-aided diagnosis of breast cancer.
Kazuhiko HAMAMOTO Tsuyoshi SHIINA
Reflection mode diffraction tomography is expected to reconstruct a higher resolution image than transmission mode. Its image reconstruction problem, however, in the many cases of practical uses becomes ill-posed one. In this paper, a new reconstruction method of limited angle reflection mode diffraction tomography using maximum entropy method is proposed. Results of simulation showed that the method was able to reconstruct the better quality images than IR method poposed by Kak, et al.
Masanari TANIGUCHI Junichi FUKUDA Tasuku TAKAGI Isamu AKASAKI
The authors developed new measuring system (Holographic Pattern Measuring System [HPMS]), which is composed of both techniques of holography and graphic image processing, was used to measure the vibrations of a printed circuit board (PCB) due to operation of a mounted electromagnetic relay on it. The clear vibration patterns were obtained. By using pattern analysis processor, quantitative vibration patterns of the PCB surface were observed. Both the vibration patterns and displacements were changed by edge fixing way of the PCB.
Tatsuya AKUTSU Satoshi KOBAYASHI Koichi HORI Setsuo OHSUGA
This paper presents efficient algorithms for finding the largest tree S such that there are vertex disjoint subtrees S1, , S (k1) of T each of which is isomorphic to S and every leaf of T is a leaf of some Si. The algorithms are useful for learning a macro table.
Masaki TAKAKUWA Kazuhito FURUYA
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.