bluuebunny/crossref_metadata_2025 huggingface dataset:
The “pattern associative memory” and its use in logic programming language processors
Authors: Yasuda Takuya , Igarashi Satoshi , Atoda Oichi , Saito Nobuo
Published: July 2007

The traditional speed improvement of the logic language processing system has been based on the parallelism of clauses, and aimed at speeding up of the unification. However, there can be another approach. By introducing a specific function to the memory hardware, the database can be managed independently of the host CPU. Then the speed is improved by minimizing the data traffic through the von Neumann bottleneck in the retrieval of candidate clauses. This paper proposes a pattern associative memory (PAM) which maintains the clauses by the structural representation in it and retrieves them by pattern matching with a high speed. To make use of argument parallelism of clauses, parallel hashing is adopted in PAM. The individual hash table employs some local search algorithms in combination with the open addressing scheme of hashing to improve the efficiency of managing records within clusters. It was verified by simulation that the compound hash algorithm is sufficiently useful for the load factor of 60 percent or less. A PAM hardware is implemented and applied in Prolog processing to demonstrate the feasibility and usefulness of the proposed method.
Determining the viewing points for 3—D objects in a dynamic retrieval system
Authors: Hamano Teruo , Ishibashi Satoshi , Ogura Kenji
Published: July 2007

The dynamic retrieval system is considered as a means to construct a database for actual three‐dimensional (3—D) objects, such as commercial goods, art works, animals and plants. In the dynamic retrieval system, the image data are given as the input continuously along the virtual semisphere covering the object. Since a large amount of image data is produced in this way, only N representative image data are extracted and stored. Apart from those representative image data, dynamical image data are prepared for rotation and display of the object in the partial area of the terminal screen. The user rotates the object displayed on the partial screen in an interactive way using a joy stick or other device.

The outline of the object is examined and the next viewpoint to observe the object is determined. Then the representative image data corresponding to that viewpoint is displayed on the terminal. A problem in this dynamic retrieval is how to select the N representative image data from the continuously observed image data.

For this problem, this paper proposes the following algorithm. Two images are taken by viewing the object from two different viewpoints. The variety of object sampling points is defined as an objective measure to represent the difference of information as sensed substantially by the human observer. Then, using that variety of object sampling points, the viewpoint for the representative image data is determined. A result of experiment is presented where the proposed method is applied to determine the representative viewpoint.
A transmission delay analysis of multilink hdlc procedure
Authors: Zhang Ai‐Ying , Saito Tadao
Published: July 2007

This paper proposes a performance evaluation model to analyze the transmission delay time in the multilink HDLC procedure, which is a standard data link layer protocol in the OSI reference model to realize an effective and reliable transmission protocol on standard HDLC procedure. This paper proposes a delay time model consisting of three submodels, i.e., the send station model, the transmission line model, and the receive station model. In an asynchronous balance mode over a point‐to‐point configuration, the total delay time of the system is composed of delay time from departure time of an information frame at the send station to arrival at the receive station and time consumed for frame sequence number rearrangement at the receive station. Characteristics of the multilink HDLC procedure are evaluated in numerical examples.
Time‐event driven scheme for distributed simulation with advance processing
Authors: Takashi  , Hizuka Sadao , Hidehiko  , Yoshikazu
Published: July 2007

As a method of fast simulation of queueing networks by parallel processing there is D‐SSQ which uses the limited‐advance processing scheme. The processing capability of the limited‐advance processing scheme has been shown to increase linearly as the concurrency of the model increases. However, on the other hand, if the updating of the maximum logical time requires considerable time after which no processor backtracks (confirmed time), its performance is degraded considerably. Also, the optimal limit of advance must be estimated from the simulation model. In this paper, to improve on these shortcomings, a time‐event driven scheme is proposed. In this scheme the system clock is managed by a central processor and each processor performs the limited‐advance processing within a certain logical time (clock) of the system time. Second, an adaptive time‐event driven method is presented. In this scheme the optimal limit need not be estimated prior to execution and the global clock is changed dynamically to achieve the maximum performance. The processing capabilities of these two methods are measured by experiments and simulations on a main frame.
Construction of a protocol synthesis environment and its implementation
Authors: Norio  , Yao‐Xue Zhang,  , Kaoru  , Noguchi Shoichi
Published: July 2007

A software environment for interactively synthesizing communication protocols without logical errors has been developed. It contains a synthesis algorithm which eliminates the logical errors, and a human interface which has a multiwindow environment, a graphical interface, colors and texts utilities. Moreover, it not only expresses the synthesized protocol as labeled directed graphs, but also provides advices on how to give the input for the protocol designer by using the colors and the texts utilities. Consequently, the protocol design has been facilitated. As an example, a call‐establish phase of X.25 has been synthesized by using the software environment.
Optimum feature selection for decision functions
Authors: Manabu
Published: July 2007

Feature selection is one of the most important processes in the design of pattern classifiers. This paper presents an optimum feature selection method which is applicable to arbitrary (nonlinear) decision functions. It is assumed that a finite number of training samples (training set) is given for each pattern class, and the decision function is designed based on the training sets. The training sets are edited by removing the samples which are classified incorrectly by the decision function. Then the feature selection problem is transformed to a modified zero‐one integer program. In this method, under a chosen permissible error, a minimum feature subset can be found which is combinationally optimum. Numerical examples of feature selection for a linear and a quadratic decision function are presented.
Identity‐based conference key distribution systems
Authors: Kenji  , Kazuo
Published: July 2007

This paper proposes identity‐based key distribution systems for generating a common secret conference key for two or more users. Users are connected in a ring, a complete graph, or a star network. Messages among them are authenticated using each user's identification information. The security of the proposed systems is based on the difficulty of both factoring large numbers and computing discrete logarithms over large finite fields.
Highly accurate segment detection using hough transformation
Authors: Junji  , Ikuo  , Hideo  , Toshinori
Published: July 2007

Although the Hough transformation is a powerful method to detect segments in an image, it requires not only a vast amount of memory but also a long processing time when a highly accurate detection is demanded. This paper proposes a new method of detecting segments with high accuracy using the Hough transformation without increasing the amount of memory. Unlike the conventional segment detection method in which the detection process is based on the parameter plane, this new method feeds the process back to the image plane from the parameter plane. Another feature of the method is the elimination in the parameter plane of Hough curves which are derived from pixels in the image plane constituting already detected segments. Experiments show that this method detects segments with a high accuracy from “noisy” images including many long and short segments.
A Learning method based on partial structures of explanations
Authors: Masayuki Numao,  , Masamichi
Published: July 2007

The learning process of macro‐operators is efficient since it is guided by given operators. By extending this method, a learning method of macro‐operators is proposed based on partial structures of explanations. Although until now macro‐operators have been used only for deductive learning that improves execution speed, the proposed method also acquires new knowledge by using hypothesis generators, i.e., it uses the explanations involving hypothesis generators to carry out induction. We demonstrate deductive and inductive aspects of our method by an example of logic circuit design and English‐Japanese translation.
A multiple‐window display
Authors: Taichi Nakamura  , Tsukasa Maejima  , Syouhei
Published: July 2007

A hardware‐controlled multiwindow display is one multiwindow display scheme which makes high‐speed display possible. However, the locations of the windows for an overlapping display are restricted due to limits on the access speed of the window buffer which is storing the window image. In order to deal with this problem, this paper considers a system with a buffer for speed adjustment. A display device was constructed based on the proposed concept, and its performance was evaluated. As a result, for the cases of one and nine windows, 21 times and 147 times faster manipulation rates, respectively, were realized in manipulations such as window shifting, as compared with a software‐controlled window display. In order to examine the effect of window manipulation on drawing performance, the drawing time was measured for cases with window manipulation and without it. As a result, it was shown that there is no significant difference in the processing time, and it was verified that the drawing performance is not degraded by window manipulation.
Component image filing system for image synthesis
Authors: Inoue Seiki , Members Masahiro Shibata , Nonmember Eisuke Nakasu
Published: July 2007

It is necessary that a database systematically store and manage various kinds of images and quickly synthesize a new image using the stored images. This paper describes a new method to manage material image data which are suitable for image synthesis and the synthesized images. The method uses “component images for synthesis,” each of which is based on its meaning such as “flower” or “person.” These are stored and managed to synthesize an image. Unlike conventional methods, this method allows a stored synthesized image to be altered easily. The usefulness of the method was confirmed by an experimental system. The system can store standard TV images and high‐resolution images (for High‐Vision images and print images) which can be used for the synthesis of an image.
Mobile robot control by neural networks
Authors: Member Shigemi Nagata , Watanabe Nobuo , Nonmembers Kazuo Asakawa
Published: July 2007

A structured hierarchical network model that enables time‐series pattern processing for robot control also is proposed. The network is divided into two types of subnetworks connected by special units called short‐term memory units. The short‐term memory unit holds its state for a certain period of time. The effectiveness of these developments was verified by applying them to the control of a mobile robot equipped with many sensors. Neurocomputers, which are based on the brain, are flexible information processors composed of a network of many interconnected neuron‐like elements (neurons or units), and are capable of advanced parallel distributed processing and learning. This paper describes first a multilayered neural network model based on the layered structure of the brain and the principle of its operation. Then a fast learning algorithm called pseudoimpedance control is proposed. The algorithm handles behavior in the learning process of the multilayered network as a second‐order forced vibration system.
An extraction method for same figure using polar features
Authors: Nagao Tomoharu , Agui Takeshi , Nakajima Masayuki
Published: July 2007

Image recognition technology using computers has been active recently. In image recognition, it is necessary to automatically extract elements such as straight lines, circles, numerical letters, and symbols from a picture. There are many cases in which the extraction of such elements is not easy because some elements overlap. This paper describes a method for extracting individual overlapping elements from a binary image. This method can extract an element which has a constant shape with arbitrary size or rotation angle, or with both an arbitrary size and an arbitrary angle. The method uses a single key point and several feature points on the model element to be extracted. The extraction is carried out by checking if the pixels corresponding to the feature points are present, with each pixel regarded as a key point of the model. This paper describes the algorithm, a method of extracting some important straight lines and circles in the picture using the algorithm, and experimental applications of the method to mechanical drawings. The results of the experiments demonstrate the successful extraction of straight lines, circles, arrows, and alphanumerics, and this confirms the usefulness of the proposed method.
A Motion Detection Method on Video Image by Using Hierarchical Pixels
Authors: Tominaga Hideyoshi , Komatsu Naohisa , Miyashita Takeshi , Member Tsuyoshi Hanamura, Associate
Published: July 2007

It is not easy to extract significant information from image data concerning the motion and the structure of an object, but this technique is indispensable to the future development of video coding and recognition of a moving object. The block matching method [1] is employed widely as a motion detection method in the motion‐compensated interframe coding. However, it has a problem in that the motion is estimated by the prediction error power minimization condition, which may lead to an instability in accurate motion detection. This paper proposes a new block matching method that has the following features: the motion is estimated and detected by stepwise switching from larger block size to smaller block size; by this scheme, the motion detection accuracy and the spatial resolution can be improved, and the processing complexity can also be reduced without degrading the detection accuracy.
Design of a recognition dictionary using artificially distorted characters
Authors: Ishii Kenichiro
Published: July 2007

One of the serious problems in developing an optical character reader (OCR) is designing a dictionary of handprinted characters which requires a tremendous amount of character data for training. This paper considers training by artificially distorted characters instead of handprinted ones in the design of a dictionary. The feasibility and the usefulness of the scheme are examined. In the experiment, 26 alphabetical characters are employed. The characteristic loci proposed by Glucksman are used as the features, and the nearest‐neighbor method is used in the classification. The recognition result of test data indicated that the dictionary designed by artificially distorted characters has almost the same performance as the dictionary designed by handprinted characters. The correct recognition rates are 98.6 percent for the former and 98.9 percent for the latter. By the training where a part of the handprinted characters are replaced by the artificially distorted characters, a performance exceeding that of the training using only handprinted characters is realized, with the correct recognition rate of 99.2 percent. Thus, it is verified that the proposed method is a useful substitute to the method by collecting handprinted characters. It is shown also that by observing the distorted characters in the feature space, the stability of the features against distortion can be evaluated.
Precise Visual Inspection of LSI Wafer Patterns by Local Perturbation Pattern Matching Algorithm
Authors: Matsuyama Yukio , Iwata Hisafumi , Kubota Hitoshi , Nonmembers Yasuo Nakagawa,
Published: July 2007

A new defect detection algorithm that compares grayscale images of actual patterns and an automatic visual inspection system implementing this algorithm have been developed. The objective is to detect defects reliably down to 0.3 μm in LSI photoresist patterns on a silicon wafer. To detect defects reliably while remaining uninfluenced by tiny differences between two images of satisfactory patterns, the images are matched in local windows by perturbing one image in the x‐y plane and in the brightness direction against the other image. The resulting unmatched regions are recognized as defects. One unique feature of the algorithm is its utilization of polarity changes in the subtracted images during the perturbation for deleting tiny differences between two images. All processing can be done in real time by local, one‐pass operators. The developed automatic visual inspection system has achieved a 100 percent detection rate for defects down to 0.3 μm.
An algorithm for determining shape descriptors based on video‐rate one‐pass image processing techniques
Authors: Yoda Haruo
Published: July 2007

This paper proposes a hardware‐oriented method of computation for determining the shape descriptors of individual figures and which processes in real‐time at the video rate the input signal obtained by raster scanning. The method consists in the following techniques: (1) The connectivity of the figure on a raster is represented by a sequence of attribute symbols; (2) the attribute symbol sequence of an arbitrary raster is generated automatically; (3) the descriptors of the figure are calculated cumulatively by referring to the attribute symbol sequence. By the proposed method, an accurate and complete representation is obtained for any complex figure with intricate placements.
Performance Evaluation of the Clustered Multiprocessor System
Authors: Takaki Yasushi , Horiguchi Susumu , Kawazoe Yoshiyuki , Shigei Yoshiharu
Published: July 2007

A multiprocessor system with bus connections has a throughput which may be reduced significantly due to the bus conflict. One approach to ease this conflict is to group processors into a few clusters. This paper presents a clustered multiprocessor prototype called “MUGEN” and the systems software implemented. Its performance also is disusssed. As for the systems software, ext‐C and para‐C languages are introduced that are developed to express parallelism explicitly. Also, the par‐C preprocessor (P3C) that translates a standard C program into a parallel program written in para‐C is introduced. Finally, the Livermore loop results are presented to measure the performance.
Evaluation of pointing efficiency influenced by the difference of bit‐map resolution
Authors: Nishinaka Yoshiyuki , Tsujino Yoshihiro , Tokura Nobuki
Published: July 2007

The authors have proposed several pointing methods (a combination of pointing device and the controlling software), aiming at the improvement of the user interface using the pointing device. Experiments have been made to evaluate the effect of those techniques on the pointing efficiency, such as the time for pointing, the work area and the ratio of unsuccessful pointing. This paper assumes the high‐resolution display, which will be developed in the future, together with the progress in the computer performance. The pointing by a mouse is considered, and the effect of the screen resolution on the pointing efficiency is examined. As a result, it is seen in the case of the high‐resolution display that the nonlinear technique, where the cursor moves as a nonlinear function of the speed of the mouse, is useful in reducing the working area on the desk and the time required for pointing.
Trademark: Multimedia image database system with intelligent human interface
Authors: Kato Toshikazu , Fujimura Koreaki , Nonmember Hiroyuki Shimogaki,
Published: July 2007

An experimental multimedia database system TRADEMARK is being developed. This system includes image processing facilities as the primitive data operations. It provides (a) automatic image data registration and automatic indexing by abstracted image representation, (b) similarity retrieval from actual visual examples, and (c) multimedia document formatting of retrieved data. Similarity retrieval in this system also permits handwritten and rough sketches as visual examples. Its ability in similarity operations is also evaluated experimentally. The design principle proposed here is based on a hyperobject‐oriented model which has the following features: (i) knowledge base‐like representation of object world, (ii) extensive architecture by deduction of logic database, and (iii) AI‐oriented human interface.
A model of visual motion perception for movements on a background
Authors: Yoshida Chiaki , Watanabe Akira
Published: July 2007

This paper proposes a new model for the human visual motion perception mechanism. The model can detect in a pertinent way the direction of motion of the object, even if the object moves in a background with a complex luminance distribution. When the object has such a background, the information concerning the object motion inevitably contains the disturbances due to the luminance distribution of the background. In the model for the motion perception mechanism up to now, however, this point has not been considered at all. This paper takes the view that the perception of the motion with such a background is essential in understanding the motion perception mechanism. Psychophysical experiments are presented to provide an insight into the motion perception mechanism for movement with a background.
The result of the experiment suggests that there exist two processing stages in the motion perception. The first stage is to fix the position of the moving object at a particular position in the visual field, and the second stage is to detect the movement of that position. Using a spatio‐temporal filter simulating the receptive field, a model composed of two such stages is constructed. A computer simulation is conducted to examine the validity of the method, and a result agreeing well with the human psychophysical characteristic is obtained.
Three‐dimensional tomographic image reconstruction from cone beam projections by single scanning method
Authors: Kudo Hiroyuki , Saito Tsuneo
Published: July 2007

The single‐scanning method has been proposed as a data acquisition method for reconstructing the three‐dimensional CT image, where a confronting pair of the cone beam X‐ray source and the planar detector are rotated on a circle surrounding the object. This paper discusses the problem of reconstructing the three‐dimensional image from the cone beam projection obtained by such a method. The traditional method of image reconstruction for this method is an approximation based on the two‐dimensional CT image reconstruction, and has a problem in that the quality of the reconstructed image is deteriorated when the circle on which the X‐ray source is moved has a small radius. First, a method is presented by which the problem of image reconstruction by the cone beam projection is reduced to the reconstruction problem by the three‐dimensional Radon transform. It is shown that the information required for the image reconstruction by the inverse three‐dimensional Radon transform cannot be obtained completely by the single‐scanning method. Then the image reconstruction by the two‐dimensional incomplete Radon transform is extended to the three‐dimensional case, and then applied to the image reconstruction by the cone beam projection. By this method, a mathematical strict image reconstruction can be achieved even by the single‐scanning method. The forementioned problem in the traditional method is now solved.
A method for threshold selection using minimum filtering
Authors: Toriu Takashi , Iwase Hiromichi , Gotoh Toshiyuki
Published: July 2007

As a binarization threshold selection method to utilize fully edge information, a method has been proposed to select the threshold so that the edge and boundary are as close to each other as possible. In such a method, the binarization actually is performed for various threshold values, and the degree of coincidence is calculated. Consequently, a very large processing time is required. The degree of coincidence is defined as the ratio between the number of boundary points in the edge region to the total number of boundary points in the image.

The authors have devised a method which can determine with a high speed the number of boundary points for each threshold without actually performing the binarization. In this method, the result of applying shrink filtering after binarization is the same as that of applying the binarization with the same threshold after applying the minimum filtering.

By utilizing this property, it is shown that the difference of the cumulative histograms between the original image and the result of processing by the minimum filter is the same as the number of boundary points for the threshold. Furthermore, the following property is shown by extending the method. The degree of coincidence between the edge and the boundary is defined as a two‐variable function of the threshold of edge detection and the threshold of binarization. Then it is shown that the degree of coincidence between the two can be calculated for any threshold without actually detecting the edges and boundaries.

By utilizing this property, not only the threshold for binarization of the original image but also the threshold for the differentiated image to detect the edge can be determined simultaneously in an optimal way without necessitating a large amount of computation.
An on‐line error‐detectable high‐speed array divider
Authors: Takagi Naofumi , Yajima Shuzo
Published: July 2007

This paper proposes an on‐line error‐detectable high‐speed array divider. The divider is based on the high‐speed division algorithm using the redundant binary representation. It can execute an n‐bit division in a computation time proportional to n, has a regular cellular array structure suited to LSI implementation, with the hardware complexity proportional to n2, and a feature that any error caused by a single cell fault can be detected during the normal operation. By utilizing the locality of the computation in the divider, the on‐line error detection is realized based on the check by the residue code for the dividend, divisor, quotient and the remainder, as well as some other additional checks.
Interpolation algorithm for unequally spaced image data with image quality correction capability
Authors: Seto Yoichi , Komura Fuminobu , Tsuboi Akira , Hamano Nobuo
Published: July 2007

An image interpolation algorithm considering the sensor aperture characteristics of unequally spaced image data is presented.

Recently, it has become possible to gather images by a high spatial resolution sensor on a satellite. Precision image processing is required to correct images which have blurs and geometric distortions due to the sensor characteristics.

To realize precision image processing, we propose an unequally spaced interpolation filter with image quality correction capability. It consists in a restoration filter, and equally and unequally spaced interpolation filters.

Image quality improves by about 15 percent in unequally spaced regions, and interpolation accuracy of less than 0.5 in gray levels is obtained. This is shown by evaluation experiments using thematic mapper sensor‐type simulation data.
A new neuron model “cone” with fast convergence rate and its application to pattern recognition
Authors: Fukumi Minoru , Omatu Sigeru , Teranishi Masaru
Published: July 2007

This paper proposes a new neuron model “analog coupled neuron (a‐CONE)” with two sigmoid functions which is applied to parity and pattern recognition problems to show its ability. Also, a digital‐CONE (d‐CONE) capable of providing a digital output is proposed and it is trained by using a back propagation (BP)‐type algorithm. Moreover, it is shown that its speed of convergence in learning was faster than that of the standard BP. The a‐CONE presented here has two kinds of sigmoid functions f1 and f2 mapping an input into an output. The function f1 provides an output response of the neuron while the derivative in learning is given by both f1′ and f2′, where f1′ refers to the derivative of f1 with respect to weighted sum of input signals. This allows a fast convergence rate to be obtained in learning. From simulation results, it is shown that the a‐CONE has a rapid convergence rate in learning compared with the conventional BP and the learning algorithm of d‐CONE networks, and produces a noise‐tolerant mapping in the pattern recognition.
Software reliability growth model for testing‐domain
Authors: Ohtera Hiroshi , Yamada Shigeru , Narihisa Hiroyuki
Published: July 2007

To evaluate the reliability of software quantitatively, a test is executed at the final stage of software development. Then errors existing in the software are corrected. In the testing phase, the functions and modules actually tested in the software are related closely to the quantity and quality of the imposed test case, and increase with the progress of the testing.

In this paper, the set of functions and modules affected by the test in the software is called testing‐domain. A software reliability growth model is discussed, where the increase/expansion of the testing‐domain is assumed to be related to the error detection of the software errors. A result is shown where the model is applied to the actual software error data. A comparison is made from the viewpoint of matching with other software reliability growth models.
Distributed collection of message exchange sequences in each process for efficient recovery from protocol errors
Authors: Kakuda Yoshiaki , Wakahara Yasushi
Published: July 2007

In the fault‐tolerance design of the communication system, one of the important techniques is the protocol error recovery which recovers the normal state from the abnormal state due to the protocol errors generated in the operation of the communication software. The protocol error recovery technique proposed up to now has the following problems: (1) messages are lost in the recovery process; and (2) a long recovery time is required from the error generation to the normal state.

This paper proposes a new method to solve those problems and which can realize an accurate and efficient error recovery. More precisely, the condition is derived for avoiding the message loss in the recovery process; and based on the condition, a new protocol error recovery process is formulated. Then another method is proposed in which each process collects the message exchange sequences executed by other processes, together with the ordinary message exchange. A principle of protocol error recovery based on the proposed collection method is shown, indicating that the forementioned problems can be solved.
An experimental evaluation of leader election algorithms for ring networks
Authors: Ikegawa Yukinori , Yamashita Masafumi , Ae Tadashi
Published: July 2007

The leader election problem is a problem of determining a unique leader, in the sense that the elected leader knows that it is elected and the processors which are not elected know that they are not elected. Under the assumption that the processors have unique identifiers, the problem can be regarded as the maximum (identifier) finding problem.

This paper considers ten typical leader election algorithms for the ring network and evaluates them in terms of the average number of messages exchanged during computation.
Learning and production of speech pattern using multilayer neural networks
Authors: Komura Mitsuo , Tanaka Akio
Published: July 2007

A new neural network and its learning algorithm are proposed. The neural network consists of four layers—input, hidden, output and final output layers. The hidden and output layers are multiple. The proposed learning algorithm is called the SICL (spread pattern information and cooperative learning) method and has the following features: (1) the singular points of back propagation errors in the BP method are removed; (2) a spread pattern information (SI) algorithm is proposed; and (3) a cooperative learning (CL) algorithm is proposed.

Using the SICL method, it is possible to learn analog data accurately and to obtain a stable output. Using this neural network, the authors developed a speech production system consisting of a phonemic symbol production subsystem and a speech parameter production subsystem. The system is applied to speech data and the system performance is examined. Especially, for the speech parameter production subsystem, the learning capacity and the optimal area for learning constants are studied. As a result, it is shown that it is possible to learn and produce speech data with high accuracy using the proposed neural network.
Bidirectional inference of mode information for logic programs
Authors: Zhou Neng‐Fa , Ushijima Kazuo , Takagi Toshihisa
Published: July 2007

Mode information (directional information concerning the arguments of predicates) is important in improving the speed of the execution of logic programs. This paper proposes a bidirectional inference algorithm for inferring precise mode information. Compared with the conventional inference algorithms, the proposed algorithm has the following two features: (1) the algorithm utilizes not only the modes of the predicates at the top level but also the modes of the built‐in predicates used in the program; and (2) by propagating the modes of the top level predicates top‐down and that of the built‐in predicates bottom‐up, more precise mode information can be inferred.
A highly reliable large scale computer complex
Authors: Turuho Seishiro , Nakatani Hajime , Gohara Juniti
Published: July 2007

To realize a highly reliable large‐scale distributed function system composed of a number of HOST and FEP, it is necessary that the fault detection of the HOST and FEP processors, as well as the switching to the back‐up processor, be conducted at a high speed.

This paper considers a hot standby system with N operating processors and 1 standby processor. A method of high‐speed recovery from the processor fault and the centralized monitoring by the system control processor (SCP) are described. In the proposed method, SCP detects the generation of fault in HOST or FEP, and instructs the switching to the standby processor. In the recovery from a fault in HOST, the communication path to the terminal is maintained by FEP, and the received message is kept in FEP until the switching of HOST is completed.

It is shown also that the recovery in approximately half the time needed in the conventional system realized in FEP fault, and the availability of FEP is improved by one order of magnitude, by floating the standby.

By these elaborations, the switching time to the standby in the fault of HOST and FEP is reduced drastically in a large‐scale function distributed system with several thousands of terminals. It is verified that in the fault of HOST, the response message can be returned to most of the terminals within the response monitoring time, and the system fault can be concealed from most terminal users.
Subclasses of Linear Context—Free Languages and Homomorphic Characterizations of Languages
Authors: Okawa Satoshi , Hirose Sadaki
Published: July 2007

This paper defines the right‐longer (left‐longer) linear grammars with the property for every production rule as natural variants of even linear grammars defined

The relation is investigated among the language classes generated by those grammars, regular grammars, and linear context‐free grammars. Also investigated are the closure properties under some basic set operations.

Finally, new homomorphic characterizations are given as follows. For every recursively enumerable language L, we can find two languages L1, L2 from each pair of those language classes except a pair of even linear languages and a homomorphism h such that L=h(L1L2). For the remainder pair, a result that h(L1L2) is linear context‐free is obtained.
Detection of Broken Ellipses by the Hough Transforms and Multiresolutional Images
Authors: Watanabe Takashi , Shibata Toshihiro
Published: July 2007

This paper discusses the problem of separating and detecting ellipse patterns. The traditional ellipse detection methods have assumed contour lines to be connected. Thus, they have the disadvantage of not being able to detect ellipses whose contours are broken considerably due to noise and overlapping. Thus, a new ellipse detection algorithm is presented which can cope with images such that many ellipses of arbitrary shapes are mixed and connectivities of contours are missing completely due to noise, and that parts of contours are lost because of overlapping.

The proposed algorithm is based on the Merlin‐Farber method, a kind of Hough transforms, and the multiresolutional images and the least‐square method are incorporated. Good detection results were obtained in the experiments implemented to demonstrate the effectiveness of the proposed method.
Extracting depth‐information from dynamic image by spatio‐temporal correlation analysis
Authors: Nomura Atsushi , Miike Hidetoshi , Koga Kazutoshi
Published: July 2007

Optical flow‐field obtained by the analysis of a sequential scene derived by a relative motion between object and camera includes three‐dimensional information (depth and/or shape).

This paper develops a spatio‐temporal correlation method for determining optical flow and attempts to extract the depth information on the basis of the analyzed optical flow field and the principle of the “motion stereo.” The method herein is improved in two critical points: (1) analysis of the plane wave propagation; and (2) algorithms for rapid calculation. It is demonstrated that the improved method and the theory of “motion stereo” are available for extracting depth information from actual scenes.
Multiprocessor scheduling algorithm with communication time
Authors: Kitagawa Hideo , Matsuda Fumio , Uchikawa Yoshiki , Hattori Shuzo
Published: July 2007

This paper proposes an algorithm for multiprocessor scheduling which is needed to realize efficient parallel processing. In the traditional multiprocessor scheduling algorithms the time required for data communication was neglected to decrease the complexity of combinatorial computation.

In this paper, using a scheduling algorithm which incorporates elements of communication time into a suboptimal algorithm, divided tasks are assigned onto a multiprocessor system. The characteristics of this algorithm are two‐fold: first, since the time required for data communication between processors as a parameter is taken into consideration, scheduling conforming to practical systems is possible; second, since it is based on a suboptimal algorithm, it shortens the time required for scheduling. Furthermore, as examples of applications of this algorithm, it is described how it is applied to inverse kinematics and inverse dynamics problems.
A fault‐tolerant algorithm for election in complete networks with a sense of direction
Authors: Masuzawa Toshimitsu , Nishikawa Naoki , Hagihara Ken'Ichi , Tokura Nobuki
Published: July 2007

Consider a directed Hamilton cycle H on a complete network. If each processor can distinguish its incident links by the distance on H, the Hamilton cycle is said to have the sense of direction. It is known that the communication complexity of the leader election problem can be reduced by using the sense of direction when there exists no failure in the network.

This paper considers the complete network with the sense of direction where at most fp processors (fp < n/2, where n is the total number of processors in the network) are in the fail‐stop condition and presents an algorithm which solves the leader election problem with the communication complexity O(n + k.fp) (k is the number of initiating processors). The result implies that the sense of direction can be used to reduce the communication complexity of the leader election problem also in the complete network with fail‐stop processors. It is shown also that the communication complexity of the presented algorithm is optimal within a constant factor.
The complexity measure of program based on the inter‐module dependency
Authors: Yang Haesool , Tsujino Yoshihiro , Tokura Nobuki
Published: July 2007

The complexity of the program is one of the useful measures in the objective and quantitative evaluation of the software. However, in the past measures, the complexity is evaluated based only on a single factor, such as program size, flow of control or dataflow information. This paper aims at solution of the problems in the past measures and proposes a new measure for the complexity of the program, called MCM (module complexity metrics), which is obtained as a combination of the intermodule dependencies.

The feature of the proposed measure MCM is that various factors affecting the complexity of the module can be evaluated in an integrated way. Then the correlation between the proposed measure MCM and the conventional typical measures are analyzed, and it is shown that the complexity of the program can be evaluated more accurately by the proposed measure MCM, while maintaining the properties owned by the past measures.
A modification support system‐automatic correction of side effects caused by type modifications
Authors: Tenma Takao , Sato Yasuomi , Morimoto Yasuhiko , Tanaka Minoru , Ichikawa Tadao
Published: July 2007

A programmer modifies software for various reasons, e.g., a change of its requirements or bug correction. When a modification is made in the software, the effect of the modification propagates to various points of the software. Such side effects must be corrected. By automating the correction procedure for the effects produced by the modification, the productivity and the reliability of the software development will be improved. This paper discusses the software modification support and proposes an automatic method of correction for the type modification in the program. The modification support system developed based on the proposed idea is described.
Extraction of transformations to be tested from the structured external functional specification
Authors: Kaneko Takeshi , Nakajo Takeshi
Published: July 2007

The authors propose a software testing method for the detection of modification errors caused by functional specification changes. In the method, if inappropriate transformations are selected, the following problems may occur: (1) test cases cannot be obtained, (2) efficiency becomes worse, and (3) effectiveness declines.

This paper identifies the transformations that the method can most effectively apply, employing Hatley's model as a software functional specification description model. It introduces the concept “change level” based on the analysis of actual software defects and shows that: (1) the transformations used in the change level are optimal for testing, and (2) when there exist two transformations in the change level whose restrictions are complementary, only one must be tested. The effectiveness of the proposed method is demonstrated by applying the method to an actual software product. The proposed testing method detected 90 percent of the defects due to functional specification changes in a software product. It can readily produce test cases even without automated testing tools when the restrictions consist of simple inequalities or equalities of the input parameters.
Global states monitoring algorithm for distributed system
Authors: Moriyasu Kenji , Soneoka Terunao , Manabe Yoshifumi
Published: July 2007

In distributed systems, there are not only synchronization errors which stop the system but also errors in which each process behaves according to its process definition, yet the system as a whole behaves differently from the requirements. Since many synchronization errors cannot be detected by locally monitoring the state of each process, monitoring system global states is required. Stable global states are the global states with all channels empty, and monitoring them is known to be important for detecting loss of synchronization in distributed systems, i.e., the presence of unintended global states or the absence of intended ones.

This paper describes a method of monitoring stable global states during the operation of distributed systems. This paper first clarifies the lower bound of control information, which each process should record for detection of stable global states, under the assumption that all control information is piggybacked with ordinary system messages. A stable global state monitoring algorithm is then presented, whose control information is minimum and which has minimum‐order complexity.
A linear algorithm for motion of rigid objects using features of parallel lines and optical flow
Authors: Joko Takuto , Ito Koji , Tsuji Toshio , Terauchi Mutsuhiro
Published: July 2007

Various approaches have been proposed toward the problem of restoring three‐dimensional (3‐D) structures and motion of rigid bodies from image information. Ullman and Huang presented algorithms using point and line correspondences, in which they assume that the correspondence problems can be solved. Prazdny et al., on the other hand, presented an algorithm using optical flow, in which equations become nonlinear and thus the second derivative of velocity is required.

This paper proposes an algorithm which combines optical flow and edge information. First, considering segments consisting of edges in an image, we derive an equation for optical flow. Then, making use of parallelism of line segments, we show that 3‐D motion can be restored by using linear equations. To apply the algorithm there must exist two pairs of parallel line segments on an object. This paper presents an algorithm for extracting these pairs of parallel line segments. Finally, we verify the effectiveness of the algorithm by simulation.
Back‐propagation learning of neural networks for translation invariant pattern recognition
Authors: Yi Jianqiang , Kurogi Shuichi , Matsuoka Kiyotoshi
Published: July 2007

In many pattern recognition tasks (e.g., handwritten letters), it is essential to recognize a given pattern invariantly with translation, rotation, and other spatial transformations to which the pattern might be subjected. The Fourier transform method is a well‐known method for translation invariant pattern recognition in which the Fourier spectrum of an image is used as an invariant feature.

This paper shows experimentally that a three‐layer neural network learns to have a similar capability to that of the Fourier transform method by means of the back propagation learning, during which a set of random dot patterns are repeatedly presented with various positions. Specifically, each unit in the middle layer of the resultant network detects a particular frequency component contained in the given image; and, using the information, the output layer generates an output pattern which is invariant to translation of the image.