bluuebunny/crossref_metadata_2025 huggingface dataset:
Three‐dimensional object recognition using spherical correlation
Authors: Okada Takashi , Sano Mutsuo , Kaneko Hiroshi
Published: July 2007

Most research in 3‐D object recognition has concentrated on feature extraction and paid much less attention to the computation and evaluation of matching metric for feature comparison. Many existing algorithms for object recognition have problems with noisy data and incomplete (partial) input data.

This paper proposes a similarity metric based on extensive exploitation of 3‐D features and characteristics of objects to solve the shortcomings of existing algorithms. Simulation and experimental results indicate that the proposed matching metric ranks the similarities among objects consistent with human intuition. It also is robust to noise and can even predict the outcome for a given noise level. Furthermore, in occlusion cases, the proposed algorithm is capable of recognizing objects using partial (incomplete) input data. It can also be used to evaluate the reliability and the contribution of a subset of the data relative to the overall object recognition task.
Description and tracking of moving articulated objects
Authors: Kurakake Shoji , Nevatia Ramakant
Published: July 2007

This paper discusses the problem of deriving a description for an articulated object from images taken in the real environment. Sometimes with the articulated object, the detection of the articulation is difficult depending on the deformation or the direction of the view line. Also, the false articulation is detected due to the disconnection of the object contour derived from the image or due to the noise.

To cope with such difficulties, a method is proposed for the moving articulated object, where the articulation is detected with a high reliability, and the description as well as the segmentation of the articulated object are derived by processing a series of images containing different outblocks and deformations of the object. In this method, the ribbon, which is the two‐dimensional version of the generalized cylinder, is used as the basic representation for the part. The initial description is derived from each frame image, and the initial descriptions of various frames are compared by ribbon matching to detect the articulation position with a high reliability. Based on the detected positions, the initial descriptions are integrated selectively and the final description is obtained. As a by‐product of the ribbon matching, the tracking of parts also is realized. By an experiment using a human walking scene, the usefulness of the proposed method is demonstrated.
Route description by 3D objects in panoramic representation
Authors: Li Shigang , Tsuji Saburo
Published: July 2007

Finding landmarks autonomously for guiding longdistance navigation by a mobile robot is explored. In a trial navigation, the robot continuously views and memorizes scenes along the route. When the same route is subsequently pursued again, the robot locates and orients itself based on the memorized scene. Since the stream of images is highly redundant, it is transformed into an intermediate 2(1/2)D representation, called panoramic representation, with much less data.

Although the panoramic representation can be used for guidance of the autonomous navigation, it still contains a huge amount of data for a very long route. A human memorizes only very imposing objects along the route such as an old church or a very high tower, and uses them as landmarks. The author's robot also finds distinctive objects along the route and memorizes their features as well as spatial relationships for navigation guidance. The 3D objects along the route are segmented in the panoramic representation by fusing range estimates and color attributes, and then a structure map representing their arrangement in space is yielded. To find distinctive objects used for the landmarks, the spatial relationships, shapes and color attributes of the objects are examined.
Estimating the performance of multiple functional unit and pipelined processor using statistical instruction dependencies
Authors: Kinouchi Yasuo , Hoshiko Takayuki , Inamori Kouichi
Published: July 2007

This paper considers the processor with the parallel operation and lookahead control functions based on the real‐time system program. The relation between the logical dependencies among instructions and the performance improvement is analyzed. With respect to the dependency, the number of dynamic steps that are processed between logically dependent instructions is considered, and the histogram is examined in the program actually run.

A method is devised wherein the behavior of the processor executing the instructions following the written order is represented in terms of the probability based on the statistical data. The effects of the dependency and the number of functional units on the processor also is evaluated by a simulation. The validity of the proposed method is verified and the effect is evaluated of performance improvement when the order of instruction execution is made variable.
FISH: Flexible information sharing and handling system
Authors: Seki Yoshiaki , Yamakami Toshihiko , Shimizu Akihiro
Published: July 2007

With the progress of network technology and workstation technology as the background, there has been progress in the exchange/transmission of information as well as document sharing by electronic means in the office environment. At present, however, techniques have not been developed to the stage where such fragmented information as knowhow is stored/retrieved/managed in the distributed environment.

From such a viewpoint, the authors have constructed the knowhow storage system FISH (flexible information sharing and handling system), which can store the knowhow in the text format. In FISH, the minimum unit decomposition of the information and the flexible structurization are realized by decomposing the knowhow into multiple virtual cards to be stored in the computer. Knowhow, which is difficult to be given a systematic structure, is managed by automatically providing links among the card based on the keywords attached to the individual cards.

This paper describes first the management method for the knowhow which is the basic design of FISH. Then the features, the functions that can be used, and the implementation of the system are discussed. The result of the one‐year operation experiment of the system in the office of the authors is presented, together with discussions. Using FISH, it is made possible to store the knowhow and share the use in the distributed environment.
Built‐in current testing for CMOS logic circuits using random patterns
Authors: Yokoyama Hiroshi , Tamamoto Hideo , Narita Yuichi
Published: July 2007

With respect to CMOS logic circuits, it is reported that a fault can occur cannot be covered by conventional classical fault model, and the current testing is considered to be interesting as a testing method to detect such a fault.

This paper proposes a fault‐detection method for the CMOS logic circuit which can detect the stuck‐at fault and the stuck‐open fault based on the dynamic power supply current observed when a pseudorandom pattern is applied as the input. A built‐in testing circuit for realizing the principle is shown. The feature of the current testing is that the fault can be detected by observing the power supply current as long as the fault in the circuit is activated, and it is not required to propagate the fault information to the output. Based on that property, a random pattern with a small test generation cost is used as the test pattern.

As the test pattern, the pseudorandom pattern is generated autonomously by utilizing the output signal of the circuit under test. The fault detection is made easier by this pattern generation since the effect of the fault on the power supply current is enhanced. In determining whether or not the power supply current is that of the normal circuit, a method based on the time‐course of the power supply current is used, with the power supply currents for various test patterns as the feature parameter. The proposed procedure is evaluated by a simulation, and the usefulness of the proposed method is demonstrated.
Realtime parallel and cooperative recognition of human face for a naturalistic visual human interface
Authors: Hasegawa Osamu , Ishizuka Mitsuru , Yokosawa Kazuhiko
Published: July 2007

The concept of a Visual Software Agent (VSA), i.e., an anthropomorphic agent possessing a realistic human form and communication functions that create an interface with the user, is proposed. Research is proceeding on its implementation on a parallel computer. In this paper, we describe a method that is effective as the visual input function of the anthropomorphic agent. This method recognizes and extracts only one person (user) directly facing the camera in a moving image in which several people occasionally enter and leave. The recognition method can be executed in real time in a typical indoor environment. The background and the lighting do not have to be restricted and recognition can be achieved in real time by a parallel computer. In addition, this technique simulates the initial stage of human visual functions and is based on the parallel extraction and integration of multiple image features. The movements of visual attention of cognitive psychology can also be simulated. An anthropomorphic agent derived from this approach successively looks at multiple human faces, fixes its gaze only on a specific person, and synthesizes agent behavior that approximate that of humans. These moving image recognition and synthesis processes were implemented on a newly designed parallel computer.
Shape, surface reflectance, illuminant direction and illuminant intensity from images with shading
Authors: Hayakawa Hideki
Published: July 2007

A method is proposed for estimating shape, surface reflectance, illuminant direction and illuminant intensity from images with shading. First, ann x mimage data matrixIis constructed fromnpixel image inten‐sity data throughmframes by moving a light source arbitrarily. Using the Lambertian assumption, the image data matrixIcan be written as the product of two matricesNandS; Nrepresents the surface normal and surface reflectance, andSrepresents the illuminant direction and illuminant intensity. Based on this for‐mulation, a singular value decomposition technique is employed and one of the following two constraints is used to factorize the image data matrix.

One is the constraint of surface reflectance which can be used when there are at least 6 pixels in the images, where the surface reflectance is constant. The other is the constraint of illuminant intensity which can be used when there are at least 6 frames among the images, where the illuminant intensity is constant.

As the number of images with shading increases, the estimation errors become smaller even if the images are taken in a noisy environment. The proposed method can also treat self shadows and cast shadows without assumptions. The effectiveness of the proposed method is demonstrated through computer simulation, performance analysis and laboratory experiment.
High‐speed match algorithm of a production system
Authors: Kimura Haruhiko , Kobayashi Shin‐Ya , Takebe Tsuyoshi , Sumiyoshi Kazuyuki
Published: July 2007

The production system is suited to representing the miscellaneous pieces of human knowledge, and is used most widely in constructing the expert system. A problem is that a tremendous amount of time is required for the condition match, and an efficient condition match algorithm is desired.

This paper considers the expert system which has been designed for the inference based on the semantic network, and aims at the realization of the high‐speed condition match in the expert system rewritten by OPS5. The working memory elements which are the objects of investigation are mostly the knowledge of two‐term relations, and the number of attributes usually is 2.

This paper also proposes a data structure for the working memory, which can derive directly all working memory elements satisfying the condition, from the condition elements with 2 or less attributes. Using the proposed data structure, an algorithm is shown that can realize a high‐speed condition match. It is shown for the considered expert system that the proposed algorithm can realize a higher speed than the conventional condition match algorithm.
A multimodule neural network model and the estimate of its nature as associative memory
Authors: Ozawa Seichi , Tsutsumi Kazuyoshi
Published: July 2007

A modular neural network model, “Cross‐Coupled Hopfield Nets with Many‐to‐Many Mapping Internetworks (CCHN‐MMMI),” in which the total consumed energy is defined as a linear sum of energy functions for subnetworks and their interactions, is proposed herein. This model can be applied to cases in which many‐to‐many mappings are necessary to mutually relate states of modules. The network dynamics are derived first, and then through computer simulations, the characteristics of the 2‐module CCHN‐MMMI are studied as associative memory. In one simulation, the effects of the introduction of explicitly modular architecture and a comparison of the results to those produced by conventional autocorrelation associative memory models.

Another simulation shows that the model can store and recall pairs of character patterns successfully even if many‐to‐many mapping relations are necessary to relate the pairs to each other. A quantitative investigation as to how the recall dynamics deteriorate with an increasing number of randomly chosen fundamental memories is made in order to access the model as associative. The results indicate that internetworks between modules function effectively to prevent the entire network from recalling spurious memories. When multilayered networks with nonlinear hidden units are employed as internetworks in the model, the association performance is even more greatly improved as compared with conventional autocorrelation associative memory model.
A study of network logic for wafer‐scale parallel‐access memory and a yield analysis
Authors: Yamashita Koichi , Ikehara Shohei
Published: July 2007

The paper describes wafer‐scale memory design with network logic based on switching register circuit (SW‐REG), and defect tolerance schemes. Such a wafer‐scale memory is an array of chips, each consisting of a memory core and SW‐REG. The SW‐REG links neighboring chips of the same column, and each column is independently accessible from the outside. Monte Carlo simulation demonstrated that addition of driver transistors and spare lines to common signals, and bypass lines to SW‐REG are optimum defect tolerance schemes. When using 64 Mbit DRAM memory core on an 8‐inch wafer, wafer‐scale memory gives higher memory capacity than corresponding discrete chip system: for 5 percent memory core yield, 13 times higher memory capacity is achieved.
Multiple fault diagnosis in combinational circuits using sensitizing input‐pairs
Authors: Yanagida Nobuhiro , Takahashi Hiroshi , Takamatsu Yuzo
Published: July 2007

This paper presents a new method for multiple fault diagnosis of combinational circuits using sensitizing input‐pairs. A partition of a circuit under test into subtree circuits and a generation method for diagnostic test are described. The set of diagnostic tests used in this paper is one of sensitizing input‐pairs that generate sensitizing paths including checkpoints on them.

By studying the relation between a sensitizing path generated by a sensitizing input‐pair and a subtree circuit, a method is presented for multiple fault diagnosis in the subtree circuit based on the fault‐free and the faulty responses observed at primary outputs. A deduction algorithm is described for a value at an output of a subtree circuit which does not have a primary output. The proposed method is applied to benchmark circuits having double faults, triple faults, and fourfold faults. Experimental results show that suspected faults are identified within 8 to 30 percent of all stuck‐at 0 and 1 faults on all lines in the circuit.
Discriminative efficiency methodology for validating software quality classification models
Authors: Takahashi Ryouei , Wakayama Hirofumi
Published: July 2007

The use of discriminant analysis for controlling software quality using complexity metrics is explored. One of the main problems in discriminant analysis involves selecting the principal components among complexity metrics that affect the classification of software modules into several groups based on quality.

This paper focuses on the use of Akaike information criterion (AIC) procedures for selecting these principal components. These procedures are based on the residual sum of squares obtained from the maximum likelihood estimation and the number of complexity metrics. The validity of using AIC procedures is confirmed by Wilks A ‐criterion procedures, taking the discriminant efficiencies (i.e., F‐test values) of models and those of complexity measures into account. Experiments show that AIC procedures can identify the model that has the highest discriminant efficiency with a low misclassification ratio and that the maximum F‐test value model is an approximate solution of the minimum AIC estimated model.
Data‐driven segmentation of textured images using hierarchical markov random fields
Authors: Noda Hideki , Shirazi Mehdi N.
Published: July 2007

This paper proposes an algorithm for a data‐driven segmentation of an image consisting of multiple textures. The method uses hierarchical Markov random fields (MRF) consisting of two layers: the first layer MRF representing invisible regional images; and the second layer MRF representing a different texture in each region. This method is based on the EM algorithm for estimating the maximum likelihood of incomplete data, to treat invisible regional processes. The algorithm repeats an estimation of the MRF parameters and a segmentation (estimation of region processes). The former is carried out by maximizing a pseu‐dolikelihood function; the latter is carried out by applying [the deterministic iterative relaxation algorithm] (developed by the authors) to the textured images. The proposed algorithm has been confirmed successfully by computer simulations using artificially composed textures.
Analysis of the error back‐propagation learning algorithms with gain
Authors: Jia Qi , Hagiwara Katsuyuki , Usui Shiro , Toda Naohiro
Published: July 2007

As the method to accelerate the learning by error back‐propagation, several studies have been proposed in which the parameter called gain is introduced. In those studies, however, the acceleration effect is evaluated only numerically, and there is no theoretical analysis of the effect of the gain on the learning process.

This paper points out that those studies can also be realized by methods without introducing the gain, and presents a detailed analysis of the effect of the gain from a unified viewpoint. The following properties are revealed as a result. The error back‐propagation method, in which a constant gain is introduced, can be reduced to the ordinary error back‐propagation method without introducing the gain. When the dynamic gain is introduced, the method cannot be reduced to the steepest descent method, as well as the momentum method, without introducing the gain. Furthermore, it is shown that there exists a characteristic superellipse that determines the behavior of the gain.

By analyzing the characteristic superellipse, a theoretical basis is provided for the instability of the method introducing the dynamic gain. This paper presents a unified treatment of the method introducing the gain and the method not introducing the gain from a unified viewpoint which have been considered independently. The effect of the gain on the learning process is analyzed, which will help in developing a new learning method in the future.
A method of motion analysis using spatiotemporal image‐directional temporal plane transform
Authors: Taniguchi Hiroyasu , Seki Akinobu , Kuroda Shin‐Ichi , Ikebata Shigeki , Furusawa Haruki
Published: July 2007

Some of the recent image processing methods proposed for detecting object moving in 3‐D space form a spatiotemporal image by placing consecutive camera images side by side in temporal order. This paper presents one such method, the directional temporal plane transform method (DTT), an image processing method that is not influenced by environmental changes. Assuming that the objects are moving on a nearly constant path, DTT first extracts significant data about these objects from each image, and then makes a 1‐D data stream by projecting the data long a directional axis parallel to the moving loci. After that, by placing the 1‐D data from individual frames side by side in temporal order, the spatiotemporal image is transformed into a 2‐D image on a directional temporal plane. Since the object motion is represented by regions of this 2‐D image, moving objects can be detected by simple 2‐D image processing. This method was used on an experimental basis to detect vehicles running along a road. Experimental results show the effectiveness of the method. An advantage of this method is its ability to detect vehicles using the same processing during both daytime and nighttime—a feature that has not been achieved with conventional methods.
Evaluation of a causal order protocol in broadcast channel
Authors: Fujii Akihiro , Nemoto Yoshiaki
Published: July 2007

Group and multicast communication provide basic functions for many applications in distributed computing. In such a communication, the causal ordering property among messages should hold throughout distributed sites. Several communication protocols for this purpose have been designed so far. They are designed mostly under the strong assumptions: there is no loss of messages in the communication channel or the order of the messages is preserved or both.

However, in WAN environment, it is desirable to design such a protocol without assuming these conditions from the efficiency point of view.

In this paper, a protocol which provides the causal ordered broadcast in a non‐FIFO network is investigated. The non‐FIFO network is defined as the network in which there exists possibilities of loss and disorder of messages. The purpose of this paper is to perform experimental evaluations to a causal ordering protocol which is specially designed for a non‐FIFO network.

The protocol is implemented as a software system, and the performance evaluation of the system is done by experiments. In addition, a simple approximation of the queue length of the system is proposed. The applicability of the approximation also is investigated.
Three‐dimensional object recognition from appearance—Parametric eigenspace method
Authors: Murase Hiroshi , Nayar Shree K.
Published: July 2007

Technology of recognizing a 3‐dimensional object and finding its direction from a 2‐dimensional image is important in practical applications such as classification of industrial products. A typical conventional method for this purpose uses the 3‐dimensional structure of the object such as its edges and surface shapes. However, extraction of a 3‐dimensional structure with a high accuracy, notably that of an arbitrary shaped object, is difficult.

This paper proposes a method of recognizing a 3‐dimensional object by using a 2‐dimensional collation. A 2‐dimensional collation which requires no 3‐dimensional feature has never seriously been examined, because it has been considered that the amounts of computation and a memory for learning the 2‐dimensional image data (which are very complex due to the variations of viewing and lighting angles) are not acceptable. The proposed method can learn a 3‐dimensional object as a set of 2‐dimensional images by using a new parametric eigenspace approach with a small memory capacity. The proposed method can easily learn a 3‐dimensional object from its 2‐dimensional image, and can recognize the object and estimate its pose. This paper includes experimental comparisons between the proposed method and other 2‐dimensional collation methods.
Competitive and selective learning method for vector quantizer design—Equidistortion principle and its algorithm
Authors: Ueda Naonori , Nakano Ryohei
Published: July 2007

A new competitive learning approach for optimal vector quantizer is presented. First, it is shown that the original Competitive Learning (CL) algorithm can be derived from the two necessary conditions forming the basis of the traditional nonconnectionist vector quantizer (VQ) design algorithm called the LBG algorithm. It is then shown that the conventional conscience principle or equiprobable principle is not optimal from the standpoint of the minimization of the expected dis‐tortion. Next, a basic principle is introduced. Called the equidistortion principle (a necessary condition for optimal vector quantizers) it is derived by using Gersho's asymptotic theory. It is shown to be applicable to distributions consisting of disjoint clusters. Then a new competitive learning algorithm with a selection mechanism, called the competitive and selective learning (CSL) algorithm and based on the equidistortion principle, is proposed here. Since the selection mechanism enables the system to escape from local minima, the proposed algorithm can obtain better performance without a particular initialization procedure even when the input data clusters in a number of regions in the input vector space. In a synthetic one‐dimensional quantizer problem in which the optimum quantizer can be numerically obtained, less than 2% of the minimum distortion has been found which had not been obtained previously by con‐ventional algorithms.
A learning method for recurrent networks based on minimization of states of finite state machines
Authors: Noda Itsuki
Published: July 2007

A new learning method for simple recurrent networks (SRN) is proposed. The correspondence between SRNs and finite stage machines (FSM) is examined and then a learning method for FSMs is constructed based on the state‐minimization technique of FSMs. This method comprises three stages: (1) generating states according to input histories; (2) grouping states according to outputs and next states; and (3) combining states within the same groups and reconstructing state transitions. Then, three networks, each behaving in the same manner as each stage through learning, are considered. A unified model of these networks and its learning method are proposed. The effectiveness of the proposed model and the learning method are verified by experimental results.
The extended C language NCX for data‐parallel programming
Authors: Yuasa Taiichi , Kijima Toshiro , Konishi Yutaka
Published: July 2007

NCX is an extended C language for data‐parallelism, which is one of the most important computation models to support realistic applications of massively parallel computers. The design criteria of the language include easy shifting from C language, low‐cost implementation of efficient compilers, and high integrity as a programming language. The language is based on the concept of virtual processors, each being powerful enough to execute the full‐set C language. Several features for data‐parallel computation, such as interprocessor communication, are added to the language so that obey the design principles of the base language C. The language is intended to be used on various architectures and is now being implemented for some machines with different architectures. This paper overviews the major extended features of NCX, together with some programming examples, and shows that NCX provides sufficient expressive power for dataparallel computation while it is based on the simple and clear notion of virtual processors.
Test generation for sequential circuits using parallel fault simulation with random inputs
Authors: Takamatsu Yuzo , Higashi Isao , Kodama Tsuyoshi
Published: July 2007

This paper presents a simple test generation method for sequential circuits using a parallelesimulator with random inputs. The proposed test generation method generates sequences by simulating as many states as possible, without using a cost function for a target fault. To generate effective test sequences, dynamic switching is done between I‐Mode and S‐Mode parallel simulators. Here the I‐Mode simulates 32 patterns for one state in parallel and the S‐Mode simulates 32 patterns for 32 states in parallel. Experimental results for ISCAS'89 benchmark sequential circuits show that our method achieves test sequences with high coverage in acceptable CPU time.
Character recognition system with cooperation of pattern and symbolic processing
Authors: Niwa Hisao , Yamamoto Hiroshi , Kojima Yoshihiro , Shimeki Yasuharu , Maruno Susumu , Kayashima Kazuhiro
Published: July 2007

A newly developed character recognition method is proposed that can be applied to low quality printed documents. In this method, the cooperation of pattern processing with neural networks and symbolic processing with knowledge of language is adopted. If errors occur at one part, another part detects it and sends the error information to all parts. After successive iterations until no error is detected, a recognition result is obtained. A character recognition of 98.4 percent is obtained with this method. This rate is 2.8 percent higher than the result of a conventional method with no information exchange among processing parts.
Detection of moving objects with three‐level continuous modules
Authors: Nakai Hiroaki , Fukui Kazuhiro , Kuno Yoshinori
Published: July 2007

This paper proposes a method of dynamic image processing which can automatically detect a moving object from the image of a walking human. The system is composed of the three‐level functional modules, which are the detection of the changing region, tracking of the moving object and the interpretation of the motion. Those modules employ simple processing, and the precision of the individual processing is not high. The system as a whole, however, can realize a high reliability because of the error‐recovery among the modules.

The proposed method is implemented on the multiprocessor system, and a moving object detection system is constructed which can extract in real‐time the locus of the motion on the image. In the past moving object detection method, there must be imposed some constraints on the scene which is the object of processing. However, the proposed experimental system operates with stability in the general environment. An experiment was conducted using the experimental system to extract the loci of motion for the passersby in the general store, and the method is shown to be effective in the general environment.
Parallel database algorithms for solving planning problems on very large databases
Authors: Ohmori Tadashi , Matsumoto Yoshihiro
Published: July 2007

This paper discusses cooperative distributed planning problems using multiple agents that share a very large database. It is an important framework for planning by multiple agents with incomplete information, and for evaluating behavior strategies and negotiation manners. The specific issue involves distributed constraint‐satisfying problems on databases. The problem is described as concurrent execution and repetitive execution of transactions, where each agent is deemed as a transaction that operates on a very large database. Therefore, we propose a highly efficient parallel database processing algorithm for these two basic operations.
Automatic abstract generation based on document structure analysis and its evaluation as a document retrieval presentation function
Authors: Sumita Kazuo , Miike Seiji , Ono Kenji , Chino Tetsuro
Published: July 2007

An automatic abstract generation system including a document structure analyzer is described. From a document, the system extracts a text structure representing rhetorical relations among sentences and sentence chunks. The system evaluates sentence importance based on the analyzed structure and decides which sentence should be discarded from an abstract. It also attempts to generate an abstract consistent with the original text by replacing connective expressions.

Generated abstracts were evaluated from two points of view: the cover rate of key sentences; and the quality as document presentation media. Both experimental results proved the generated abstracts to be valid.
Evaluation of the maximum number of switching gates for CMOS circuits
Authors: Ueda Hiroaki , Kinoshita Kozo
Published: July 2007

This paper addresses the problem of evaluating the maximum number of switching gates. We propose both exact and approximate algorithms to evaluate the maximum or nearly maximum number of switching gates based on the branch‐and‐bound method. In these methods, iterations of partially exhaustive enumeration and information from circuit structure are used to prune the search space. These methods are implemented on Sun workstations and experiments for ISCAS'85 and ISCAS'89 benchmark circuits have been done. For small circuits, the maximum number of switching gates can be easily evaluated using the exact algorithm. For large circuits, results for the approximate algorithm are compared with results obtained by applying randomly generated vector pairs. It has been shown that the approximate method is better than the latter.
Architecture of a parallel machine: Cenju‐3
Authors: Maruyama Tsutomu , Kanoh Yasushi , Hirose Tetsuya , Muramatsu Kazuhiro , Nakata Toshiyuki , Asano Yoshihiro , Inamura Yu
Published: July 2007

Cenju‐3 is a parallel computer in which up to 256 processing elements (PEs) are connected by a highspeed multistage interconnection network. In designing the system, the architecture is tuned for up to a 256 processor system. A VR4400 with 1 MB of secondary cache memory is implemented on a multi‐chip‐module to realize a compact and high‐performance PE. The multistage network is implemented very compactly. The number of the cables is equal to the number of processors. The dedicated network interface hardware designed for the system achieves low latency and high throughput. This paper presents the machine architecture and its evaluation.
Application of verification method and a decomposition method to program modification
Authors: Ono Kouichi , Maruyama Katsuhisa , Fukuzawa Yoshiaki
Published: July 2007

This paper considers the case where the specification and the program are modified. A method is proposed that specifies the range which is affected by the modification using the verification method and decomposition technique. By the proposed technique, the points where the modification is required or the point which may contain an error can be estimated when the program is modified. The inductive assertion is used as the verification technique.

It is assumed that the specification before modification as well as the program are already verified for the correctness. The object of verification is simplified by the comparison and validation of the verification history and the object of correctness verification. The part which is left without being simplified is the range affected by the modification before the comparison and after the correctness verification, the rage which is affected by the modification as well as the range for which the validation is not satisfies can be specified.
Stereo matching by the combination of genetic algorithm and active net
Authors: Sakaue Katsuhiko
Published: July 2007

There have been proposed a large number of methods to extract the three‐dimensional information in image understanding. Among those, stereo‐imaging is considered interesting as a passive method that does not affect the object. The problem of stereo imaging can be reduced to the corresponding point search problem. An attempt is made to use the following method to arrive at high‐density distance information. The energy functional is defined for the disparity considering the smoothness constraint. Then, pointwise stereo matching is realized by minimizing the functional over the whole image.

The active net is one such approach. This technique often is combined with the iterative solution method based on the coarse‐to‐fine strategy using the multiple resolution, but it is not easy to achieve the matching for a wide range of disparity.

This paper proposes a new stereo‐matching method, where the far‐search power of the genetic algorithm and the local optimization power of the active net are combined. It is a method in which a large number of partially corresponding patterns are prepared and calculated using the active net. Then, the genetic manipulation is applied to the set of patterns, and the optimal correspondence is sought in a stable way by iterating the change of generation. The procedure has the feature that the inadequate parameters are sorted out, and the optimal parameters are selected adaptively.
A method of communication route switching by a distributed algorithm
Authors: Kawahara Hiroto
Published: July 2007

In the field of computer‐network routing methods, there has been less research on fixed routing systems than on adaptive ones. However, there are a great many fixed routing systems in use on actual networks because they are simple. In fixed routing, a principal issue is which method should be used for switching to alternate routes in cases where damage to links or nodes blocks off primary routes. In the majority of cases, routing is changed by switching the links over which the packets are sent (called outgoing links). However, the methods have not yet been perfected—ping pong, looping, and other erroneous‐routing phenomena arise occasionally. This paper presents a distributed algorithm to solve these problems. An algorithm will be given for restoring the original routes after recovery from damage. Finally, it will be proved that erroneous routing will not arise even when multiple chains of operations based on the algorithms presented are in progress at the same time.
A 3.84 gips integrated memory array processor
Authors: Fujita Yoshihiro , Yamashita Nobuyuki , Kimura Tohru , Nakamura Kazuyuki , Okazaki Shin'Ichi
Published: July 2007

An integrated memory array processor (IMAP) ULSI with 64 processing elements and a 2 Mb SRAM has been developed to build a compact real‐time image processing system. The chip attains a 3.84 GIPS peak performance through the use of SIMD parallel processing and 1.28 GByte/s on‐chip processor‐memory bandwidth. The IMAP is capable of parallel indexed addressing, which increases applications for parallel algorithms. Created using 0.55 μm BiCMOS double layer metal process technology, the IMAP contains 11 million translators in a 15.1 × 15.6 mm2die area.
Design and implementation of system software for the super database computer SDC‐II
Authors: Nakamura Minoru , Tamura Takayuki , Kitsuregawa Masaru , Takagi Mikio , Hirano Satoshi
Published: July 2007

The super database computer SDC‐II is a back‐end massively parallel SQL server, designed for superhigh‐speed processing of queries in relational database systems. The experimental system is composed of tightly coupled parallel processing modules, each containing up to seven CPUs, four disks and two data network interfaces, and a highly functional omega network connecting eight such modules.

This paper describes first the parallel relational database processing system, and then proposes a query execution model for its efficient realization. The execution model uses four basic primitives (getPage, putPage, getFree and putFree), which are functions. Processing is performed pagewise using these basic operations. GetPage fetches a page from the disk read buffer, followed by getFree to acquire a free page from the free page pool. The results are sent to a disk write buffer with putPage, and putFree frees the page fetched from the read buffer. In other words, the processing progresses with the page moving around the system. The dataflow control for the input/output processes in the secondary memory for the efficient query processing are discussed in detail later. The method for avoiding and recovering from deadlock are described. Finally, the software system implemented on the SDC‐II is considered describing its components and functions. Measurement results for the execution of the TPC‐D benchmark are shown, indicating that efficient operation is realized.
Study of unknown‐multiple signal‐source clustering problem using ergodic HMM
Authors: Murakami Jinichi , Watanabe Hideyuki , Sugiyama Masahide
Published: July 2007

The problem in which the input signal sequence is segmented into multiple signal sources and the signal source is estimated appear in a wide range of problems, such as speech information processing and language processing.

In this paper, this kind of problem is called the unknown‐multiple signal source clustering problem, and a solution method is proposed based on the ergodic HMM. In ergodic HMM, the state corresponds to the signal source and the symbol sequence output from the state corresponds to the signal sequence. Then, using the Viterbi decoding and the forward decoding, the segmentation point and the category can simultaneously be estimated. As an application of the problem, the classification of the utterances by multiple speakers is attempted. As a result of the experiment, it is shown that the initial parameter values are important in the ergodic HMM, and the LPC cepstrum with a long‐term window is useful as the feature vector reflecting the speaker individuality.
Set‐theoretic comparison of mappings of combinatorial optimization problems to hopfield neural networks
Authors: Matsuda Satoshi
Published: July 2007

In solving combinatorial optimization problems by Hopfield neural networks, mappings of the problems to the networks are not made so carefully. Although many mappings of, for example, the traveling salesman problems (TSP) have been proposed, their theoretical comparisons are not yet made.

In this paper, taking two typical mappings of TSP as examples, their theoretical comparisons are made to prove the superiority of one over the other by the asymptotical stability and unstability theory of the solutions shown by Matsuda [8, 9]. This theoretical comparison method could be applicable to mappings of many other combinatorial optimization problems.
Analysis of RISC performance in real‐time system
Authors: Sugimura Yasushi
Published: July 2007

The author has already proposed a method of analyzing the average instruction execution time for estimating the performance of CISC in a real‐time system (RTS) [1]. However, in [1] there was no mention of a method of analyzing the execution time when the CPU has a cache memory and an RISC architecture.

This paper presents a simulation method for solving that problem, and clarifies the relative processing power of the two architectures. The new method converts actual RTS CISC trace data in an RTS to RISC access state data and uses the data for input in simulations of cache operation, etc., to clarify the processing performance ratio between CISC and RISC in an RTS.

The results clarify that the 1‐level write‐through cache strategy (MIPS R3000) suffers from continuous writing, the two‐level write‐back cache strategy (MIPS R4000) depends strongly on the speed of the secondary cache, and that the overall RTS characteristics differ from the characteristics of application programs in a time‐sharing system (TSS), etc.

These techniques go beyond simply allowing the comparison of RISC and CISC performance. They also make it possible to clarify the factors of the performance characteristics of systems that include caches on the basis of an overall software model for actual RTS.
A human system learning model for solving the inverse kinematics problem by direct inverse modeling
Authors: Oyama Eimei , Maeda Taro , Tachi Susumu
Published: July 2007

The problem of computing a human arm posture that will take the hand to a desired hand position given by vision is called an inverse kinematics problem. To solve this problem, the human nervous system has a system for solving the inverse kinematics problem computing the proper joint angles from the desired hand position.

Although the direct inverse modeling method is popular for the acquisition of an inverse kinematics model, a sufficient inverse model cannot be obtained for such systems with many‐to‐one input‐output correspondence as a human arm system.

This paper, proposes a new model of a human inverse kinematics solver which uses the learned inverse model of the linearized model of the human arm. This inverse model transforms the hand position error to the update vector of the joint angles. The solver inverse kinematics problems by using the hand position error feedback. The performance of the solver is shown using numerical simulations.
StGA: An application of a genetic algorithm to stochastic learning automata
Authors: Munetomi Masaharu , Takai Yoshiaki , Sato Yoshiharu
Published: July 2007

Reinforcement learning algorithms such as stochastic learning automata are used to increase the probability that an action will succeed in a stochastic environment. Stochastic learning automata generally have the property of extremely slow convergence when they have a large number of feasible actions. This paper presents a novel reinforcement learning algorithm that employs a genetic algorithm to accelerate convergence. This learning algorithm, called a stochastic genetic algorithm (StGA) samples a small number of actions among all feasible ones. Procedures of stochastic learning automata and genetic operations are applied to a set of sampled actions in order to search effectively a feasible space of actions and find the best ones. Through theoretical investigations, a proof is given on convergence of the StGA by using an ε‐optimality of the stochastic learning automata. Moreover, empirical simulations demonstrate the effectiveness of the StGA when there is a large space of feasible actions.
A consistency verification method for design models in design environments
Authors: Arai Hiroshi , Fukazawa Yoshiaki
Published: July 2007

This paper considers the set of tools built in the design environment for digital hardware, and proposes a method to verify the consistency between the set of tools and the data model. In the design support environment which integrates the set of tools with different data models in general, the interchangeability of the design data is maintained through the common data format. In practice, however, semantic gaps are often produced between the data models.

In the proposed method, the data models of the tools and the data models to be presented by the whole environment to the hardware designer are formally defined using the semantic network. The difference between the data models is extracted by operations between the semantic networks. The method was applied to the design support environment based mostly on the netlist information, and the inconsistencies at the semantic level were detected, which has been difficult at the syntax level.
Query processing method for multiple databases with a different set of attributes
Authors: Nishizawa Itaru , Takasu Atsuhiro , Adachi Jun
Published: July 2007

This paper discusses a schema integration and query processing method that enables integrated access to the multiple autonomous databases in the distributed environment with schemata restricted to a set of attributes. This method is based on the construction of a virtual database (VDB) formed over physically distributed component databases. Although user queries are issued to this VDB, these queries are decomposed to the subqueries using the virtual functional dependency (VFD), which is defined on the VDB and issued to each actual component database. The VDB‐based method can obtain more answers that are logically valid than those gained from conventional query processing methods. When the VFD formed over a VDB is acyclic among the nodes to which the query refers, sound and complete answers can be efficiently calculated.