Search

Nonbinary information (m-ary symbol information) is often used in information input systems based on character recognition or keyboard entry. It is known that single-symbol errors and adjacent two-symbol transposition errors occur in such systems. This paper proposes a code construction method that can correct nonbinary single-symbol errors and also adjacent two-symbol transposition errors. The codes proposed in this paper consist of check symbols on integer rings and prime fields. These check symbols are converted to m-ary symbols and the code word is constructed by adding the result to the information symbol. The proposed code is better than the conventional code in terms of code length. When m=10, for example, the code length is more than twice that of the conventional code. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(8): 54– 60, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10516 Copyright © 2004 Wiley Periodicals, Inc. [ABSTRACT FROM AUTHOR]

In this paper, the environmental factors surrounding fruit trees are used as the explanatory variables, and the factors concerning the quality of the agricultural produce are used as the explained variables. The observed data are analyzed. The object of analysis is the Onshu orange (mandarin orange). The purposes of this paper are analysis of the effect of environmental factors on product quality, the target value settings for the controllable environmental factors in order to produce high-quality products, and evaluation of the cultivation environment for each item. A system for data analysis is proposed which extracts the useful information for the decision-making such as cultivation management, as well as harvest/shipping planning, from the observed data. The system uses a probabilistic neural network and learns the mapping from the describing variables consisting of observed data to the explained variables. By superposing the acquired knowledge, inverse modeling can be performed. It is shown that by using the proposed system, multivariate nonlinear inverse mapping can be realized instead of the linear inverse regression estimation used in conventional single regression analysis. © 2005 Wiley Periodicals, Inc. Syst Comp Jpn, 36(11): 102–110, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10577 [ABSTRACT FROM AUTHOR]

This paper proposes a matrix-multiplication algorithm suited to the distributed computer environment. The system is implemented using PVM and the execution time is evaluated. One of the conventional methods implemented using PVM is the systolic method. However, this method is limited with respect to the matrix size that can be calculated and the number of computers that can be used in the calculation. This paper first extends the algorithm so that these limitations are lifted. Then, an algorithm is proposed which can reduce the communication complexity, although the computational complexity is slightly increased. These two algorithms are implemented using PVM, and the execution time is measured. In either algorithm, an acceleration rate exceeding the number of computers is obtained. The effectiveness is found to be due to the effect of the cache memory, and the speed improvement obtained by using cache memory is investigated. The optimal number of matrix divisions from the viewpoint of cache memory size is also discussed. © 2005 Wiley Periodicals, Inc. Syst Comp Jpn, 36(4): 48–59, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10551 [ABSTRACT FROM AUTHOR]

In this paper, we present a method for implementing a Kansei (sensitivity) operator for an automatic metadata extraction method used for media data. The Kansei operator, which operates on metadata extracted from media data, performs mapping based on human sensitivity by applying a logarithmic function that reflects human sensitivity based on Fechner's law. The proposed method enables metadata that reflects human sensitivity to be extracted according to the Kansei operator for metadata that was obtained according to weighted word categories output by a conventional automatic metadata extraction method. In addition, using a semantic associative search method enables searching to be performed, which matches human intuition for the media data categories. In this paper, we combine the Kansei operator with an automatic metadata extraction method for music data to implement an automatic metadata extraction method having a Kansei operator for music data. In addition, they show the effectiveness of the proposed method experimentally. [ABSTRACT FROM AUTHOR]

This paper describes a time-triggered object-oriented model for embedded control systems and a control software development method based on that model. Conventional object-oriented models had been based on event-triggered actions. In contrast, we propose a time-triggered object-oriented model for real-time control. This model, which consists of a set of objects for calculating data values required for control, activates these objects cyclically to implement time-triggered actions. This paper also shows that a distributed control system having location transparency can be implemented efficiently according to this model. In addition, we propose a control software development method based on the proposed time-triggered object-oriented model. This development method can extract objects according to simple operations from control block diagrams used to describe control specifications. This paper also introduces an embedded system-oriented implementation method that does not consume much resource and presents an application example in a distributed control system for automobiles. © 2003 Wiley Periodicals, Inc. Syst Comp Jpn, 34(2): 43–54, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1189 [ABSTRACT FROM AUTHOR]

To improve software productivity, my colleagues and I pointed out in a previous paper that the state transition method is suitable as the functional description and implementation method. In that paper we proposed the distributed state transition method, which was derived from the model of distributed sequential machines and showed results obtained by applying it to an electronic switching system. In this paper, to enlarge the application range of the state transition method, I consider applying it to a PC management database system, and propose a new integrated design method derived from the single sequential machine model as being suitable. First I propose the “group-noted state transition method” by introducing the sequential machine model. Then I propose this design method as follows. Initially, the function of the outer world of the system is classified into several groups, and management jobs are then divided into the same number of groups corresponding to them. The database information can also be classified in the same way and can support the design of the database system. After that, the state transition description is defined from the input/output information to/from the groups of the outer world. Furthermore, the method of notation in which the status group is added to the status name is proposed by classifying statuses using the concept of the management cycle. I also propose a new method for designing the software structure in which state transition diagram information is stored in the database system by converting it to table format. Results clarify that it is possible to make an integrated management database system by using this state transition method. They also clarify how to make a more advanced system by cooperating with the workflow system. © 2001 Scripta Technica, Syst Comp Jpn, 32(10): 13–21, 2001 [ABSTRACT FROM AUTHOR]

This paper discusses the learning problem of obtaining good generalization capability from a given set of training examples when the space to which a target function belongs is known. One of the present authors, H. Ogawa, proposed the concepts of projection learning (PL), partial projection learning (PTPL), and averaged projection learning (APL). He also devised the concept of a family of projection learnings consisting of infinitely many kinds of learnings including PL, PTPL, and APL. It provides a framework to discuss infinite kinds of learnings in a unified way. Although a couple of definitions were given for the family of projection learnings, they are still unsatisfactory for further development of the theory. In this paper, we propose a more natural definition of the family of projection learnings and consolidate a foundation of the theory of a family of projection learnings. © 2001 Scripta Technica, Syst Comp Jpn, 32(5): 21–35, 2001 [ABSTRACT FROM AUTHOR]

Methods to transfer and store information efficiently are in demand due to developments in computer technology. Data compression technology has developed as a viable technology for data usage and is being used in various fields. One data compression method widely used at present is LZSS coding. LZSS coding is a data compression method that provides high compression ratios by eliminating the redundancies in coding expressions in LZ77 coding [4]. Speed is needed for the transfer of large amounts of data over networks, and dedicated hardware for data compression has been considered as a means to satisfy this need. In this paper the authors propose a high-speed LZSS coding and decoding parallel processing architecture, PAHL-LZSS, to achieve high-speed LZSS coding. PAHL-LZSS provides compression at a lower computational burden by actively using the statistical characteristics of generated coding and by using parallel processing architecture. Both coding and decoding are achieved in one circuit. In addition, the PAHL-LZSS architecture is described using a hardware description language, and its likely characteristics are clarified. In addition, in this paper the authors propose a packaging method using modules as a way to package PAHL-LZSS and PAHL more easily. © 2000 Scripta Technica, Syst Comp Jpn, 31(9): 49–59, 2000 [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of consensus formation of adaptive agents. We consider a group of adaptive agents required to make a group decision. The adaptive agents are modeled as having their own preference order as rational agents with different levels of adaptation. In order to make a consistent group decision, they are required to derive the group preference by aggregating their preference orders. Each agent, as both a rational and an autonomous agent, may behave to satisfy its own preference order. However, it may pose a difficult issue if priority is given to each agent's preference order. It is known that it is impossible to derive the consistent group preference order by summarizing individual preference orders. Therefore, in a group of humans, prior to a group decision, each member often changes his own views and modifies his own preference order. In this paper, we provide an adaptive model for consensus formation. Each agent modifies its own preference order by considering the others' preference orders and the status of the group decision. We also consider the heterogeneity of agents by reflecting different levels of adaptation. We show that a group of rational agents with different levels of adaptation enhances the possibility of reaching consensus. Heterogeneity among agents also affects the content of consensus formation. We develop a prototype model which is applied to the problem domain of allocating Internet resources. © 2000 Scripta Technica, Syst Comp Jpn, 31(7): 20–28, 2000 [ABSTRACT FROM AUTHOR]

This paper is intended to construct a system to support effective collaborative learning in a distributed environment. The paper describes the construction of a computer coordinator that identifies the progress status of a discussion and the participants' interaction status. It deals with a negotiation process to build a consensus among the participants. The process is formalized in this paper. The paper also describes a decision making structure and proposes a discussion supporting system. © 1998 Scripta Technica. Syst Comp Jpn, 28(14): 21–32, 1997 [ABSTRACT FROM AUTHOR]

This paper analyzes the effect of hardware needed for redundant interconnection lines and exchanging switches on the yield of VLSI with redundancy. As a defect distribution pattern, the Gamma distribution is assumed. Under this condition, the yields of areas on a VLSI correlate with each other. This paper presents the normalized chip expansibility as a figure of merit to evaluate the effect of introducing redundancy into VLSI. It is made clear that the normalized chip expansibility is effectively employed to represent the effect of the hardware redundant interconnection lines and exchanging switches on the yield of a VLSI. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(8): 8–16, 1997 [ABSTRACT FROM AUTHOR]

The purpose of this paper is to provide a realization of FFT processors capable of real time processing of image signals. All of the arithmetic operations in such FFT processors must be achieved with hardware technology, so that the chip size of the processor LSI is wafer scale. To realize such WSI processors, this paper introduces redundancy technology. A redundant system design is shown in which special emphasis is placed on the chip area of the interconnection lines between butterflies as follows: 1 In the design of the non-redundant FFT processor, the chip area of the interconnection lines is reduced as much as possible. 2 A redundant structure capable of recovering from defects in the interconnection lines is proposed. 3 A yield equation is derived in which the entire effect of interconnection area is considered. 4 In the redundant system design, the total redundant chip area, including the chip area for interconnection lines and multiplexing switches, is minimized. It is indicated that an FFT processor whose chip area is 120 times that of the standard LSI with 50% yield may be realized with a 6% increase in chip area but without decreasing the yield. © Scripta Technica, Inc. Syst Comp Jpn, 28(6): 18–29, 1997. [ABSTRACT FROM AUTHOR]

This paper considers cooperative and distributed problem-solving in an environment where similar problems are repeatedly posed, and discusses methods for plan reuse. In distributed planning including multiple agents, the agents generate the plan cooperatively from various viewpoints which results in a plan with high cost. The reuse of the plan realizes efficient planning by utilizing the plan for similar previous problems. The first feature to note in applying plan reuse to a multi-agent system is the problem similarity. Even if an agent decides that two problems are the same, another agent may consider a totally different goal or viewpoint. In this paper, it is shown that under certain conditions, the reuse of a plan is effective independently of the goals of other agents. A planning method including reuse is presented. Finally, it is shown experimentally that efficient planning can be realized. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(6): 60–67, 1997 [ABSTRACT FROM AUTHOR]

This paper proposes a method of identification of an individual by integrating multiple features, such as front facial image, walking image, and vocal features. This method improves the accuracy of identification and reduces the number of samples required in a practical operation, compared with conventional methods using a single feature. These three features are integrated at a similarity level in the proposed method. Identification experiments using 33 individuals show that the proposed method can identify 81% (maximum) of the individuals, compared with 60% (maximum) by a conventional method. This paper also shows that an integration of features based on a simple linear connection is more effective than the Dempster-Shafer probability model. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(6): 77–84, 1997 [ABSTRACT FROM AUTHOR]

This paper proposes a method for detecting delay faults of gates in a combinational logic circuit. Assuming that a gate of the circuit has a small delay (a unit delay), the generation of a test for the circuit is described. This paper also describes the generation of the timed seven-valued calculus used in the method. The method has been applied successfully to benchmark circuits having unit delay and a fanout weighted delay. The experimental results show that the method has high fault coverage in all the circuits, and that this can be applied to the detection of gross delay faults. The proposed test method is called the ‘SD test’. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(6): 68–76, 1997 [ABSTRACT FROM AUTHOR]

This paper is concerned with a high-speed, high-accuracy Hough transform which utilizes simultaneous recurrence formula. Existing methods of this kind still produce a small error in the ρ value calculation, and the ρ value does not agree well with the value calculated from the original Hough transform expression. Moreover, its form of expression is not adapted to parallel processing. The accuracy of the ρ value calculated by the new method provided in this paper is confirmed by computer simulation. The proposed method has also achieved very high calculation speed by replacing multiplication operations with the shift operations on the CPU registers. Because of its extremely simple configuration, it is easy to implement the algorithm in special hardware. It is suitable for parallel operation on the special hardware or a parallel processor. Thus, the newly proposed method assures a great progress in applying the Hough transform to real time processing. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(3): 24–33, 1997 [ABSTRACT FROM AUTHOR]

An evaluation distance function is one of the most important factors that influences the accuracy of a handwritten character recognition system. Various evaluation distance functions have been proposed and investigated theoretically. City block distance, Euclidean distance, weighted Euclidean distance, sub-space method, multiple similarity method, Bayes decision method and Mahalanobis distance are known typical distance functions. Although observing the performance of each evaluation function in a large-scale handwritten character recognition system is quite important, there has been little research reported on this topic. In this paper, because the emphasis is on how to improve the accuracy of a recognition system, comparison experiments are carried out. The experimental results show that the Mahalanobis distance is the most effective of the seven typical evaluation distance functions. Considering the foregoing result and the properties of distribution on each axis, a modified Mahalanobis distance is proposed to construct a more accurate and faster system. Using the proposed modified Mahalanobis distance as the evaluation function, a recognition rate of 98.24 percent has been achieved for ETL9B, the largest public database of handwritten characters in Japan. In this paper, the behavior of seven typical evaluation functions is studied and a new evaluation distance, called the modified Mahalanobis distance, is proposed based on these results. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28 (1): 46–55, 1997 [ABSTRACT FROM AUTHOR]

Overlearning in the neural network can cause a failure in the approximation of a function because of the limited generalization power of the neural network. To solve this problem, it is considered effective that the neural network learns the probability density function of the learning samples, and the result "answer is impossible" is obtained when an input is given in the region containing no learning sample. This paper proposes a method in which the probability density of the learning sample is reflected on the output for the function by alternately inputting the learning sample and the random value. It is reported in this paper through a simulation that the proposed method works correctly in the multilayered perception (MLP). When this method is applied, there is a close relation among the SN ratio, the output norm and the probability density of the learning samples. [ABSTRACT FROM AUTHOR]

There are many efforts being made toward the visual navigation system for the autonomous vehicle. When the highway road is considered, where the constrain for the road structure can be utilized, it is effective to extract the white line (lane marker), which is enforced to be drawn as the borderline of the lane. This paper considers the automatic extraction of the road edge from the white line in the road image taken by the vehicle camera. there is already proposed a technique which assumes that the road edge image is extracted from the white line, and estimates the horizontal curvature of the road and the vibration component of the vehicle (dynamic angle of the vehicle). It is adequate to use the break (end point) of the white dashed line as the feature point for estimation of the vehicle angle. To extract the road edge from the dashed line, however, it is required to trace the dashed line which moves between consecutive frames. From such a viewpoint, this paper utilizes the result obtained by the already proposed estimation method for the vehicle angle, and predicts the motion of the end-point of the dashed line on the image due to the motion of a vehicle. By restricting the range of search based on the result, the end-point is tracked. An experiment was conducted for the sequence of the image taken for the actual road. It is verified that a sufficient accuracy is obtained for the position prediction, so that the restricted range of search contains the end-point, which will help the automatic extraction of the road edge. Then, a system is constructed as a cooperative system, which estimates the vehicle angle the road shape from the real image, using the automatically extracted road edge. It is verified by an on-line experiment for the real image that the vehicle angle and the horizontal curvature of the road can effectively be estimated. Those results are reported in this paper. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper considers the high-speed execution of FORTRAN programs on parallel processing systems and proposes the parallelizing scheme of the program and execution based on the speculative execution over multiple conditional branches. Several techniques have been proposed that parallelize the program including conditional branches. A method which does not use the speculative executions is: (1) the method called earliest execution condition determination. As the methods which use the speculative execution are: (2) speculative evaluation scheme for a single conditional branch for the superscalar processor or VLIW computer; and (3) multiple speculative execution scheme assuming particular loops. There are the following problems: (1) sufficient parallelism is not extracted only by determining the earliest execution condition; (2) the speed improvement that can be realized by the speculative execution of a single conditional branch is at most twofold; and (3) the scheme can be applied only to particular loops. This paper divides the program into macrotasks, and defines the multiple stage speculative execution scheme between macrotasks on the general parallel processing system. Then, the macrotask executions control for the individual macrotask is proposed, using the execution start condition, the control establishment condition and the execution stop condition. [ABSTRACT FROM AUTHOR]

The neocognitron is a hierarchical neural network model with pattern recognition ability. The intermediate layers of the neocognitron contain various kinds of cells (feature-extracting cells) that extract partial features of the input patterns. The feature-extracting cells has modifiable input connections, with the connecting weights depending on the kind of feature to be extracted. The connecting weight is determined by an unsupervised learning. When a standard pattern is given as a stimulus, the connecting weights are adjusted so that the cell exhibits the maximum output. The tolerance in deformation of the feature to be extracted by the cell (that is, feature selectivity) can be adjusted by the thresholds of the cell. This paper discusses how the thresholds of the feature-extracting cell in the intermediate layers affect the recognition rate of the neocognitron. In the conventional neocognitron, the same threshold values were used in both learning and recognition phases. This paper shows also that the recognition rate can be improved greatly by using higher threshold values in the recognition phase than in the learning phase. [ABSTRACT FROM AUTHOR]

This paper describes a method of precisely and effectively visualizing a complex 3-dimensionally curved surface from a set of range data by using meshes (parallel hierarchical triangulation) which are adaptive to the degree of its complexity. The method can reconstruct the curved surface without cracks by approximating its intrinsic shape and discontinuity with a polygon. The algorithm used can be processes by fast parallel local calculations with an upper limit in time and space. This paper proposes a parallel recursive algorithm for generating an adaptive mesh using a D-curvature based on the intrinsic shape of an object, and another parallel recursive algorithm to avoid the formation of a crack which occurs between two subdivisions. Experimental results applied to range images of human faces are shown. The proposed method can be applied to general images (e.g., gray-level image and color images) other than range images so that the compression or reconstruction of an image can be carried out by adaptively using its geometrical features (e.g., the pixel value, its first-order differential, and second order differential). [ABSTRACT FROM AUTHOR]

Massively parallel computers are being realized for aiming at high performance. Bitonic sort is an efficient algorithm for network computers. But generally, it is impossible to use a bitonic sort algorithm on a network computer with a node failure. This paper presents a fault-tolerant scheme of bitonic sort algorithm for a network computer that makes it possible to tolerate a node failure without an additional hardware cost. The method does not have hardware redundancy but has software redundancy. The method does not depend on the network topology. However, the method takes about two times as many steps as that of original bitonic sort. This paper also shows that the method is applicable to a chordal ring connected computer as an example. [ABSTRACT FROM AUTHOR]

This paper discusses how a line segment and segment pair in a 3-dimensional space are constrained by an image obtained by their perspective projection. Also, it introduces the concept of polarity in the interpretation of a line-segment image obtained under perspective projection and gives a definition of a spherical PAT curve. In addition, the relationship is explained between a PAT constraint [5]. Which is of an angle formed by two line segments a plane, and the spherical PAT curve [7], which is a constraint of two line segments at an arbitrary position in a 3-dimensional space (an extended idea of the former). Although the spherical PAT curve an be obtained formally by projecting a plane PAT curve onto a sphere, and this is justified for a semisphere, the meaning of this on the opposite semisphere has not been clarified with a justification. This paper justifies the sphere PAT curve by discussing the polarity of the segment interpretation, and explains in accurate meaning. This paper also describes the characteristics of a spherical PAT curve. The idea will have many applications to image understanding. [ABSTRACT FROM AUTHOR]

This paper discusses an algorithm for detecting bubbles in a diver's bloodstream during decompression from submergence. A widely employed method at present for detecting bubbles is the ultrasonic Doppler method, which is based on aural sensation. However, a problem here is that the Doppler signal contains various kinds of noises such as cardiac motion signals. Thus, the observer is required to concentrate to detect the bubble sound from the noise when the number of bubbles are few, and to count the number when there are many. This is not an easy task, even for an expert. The authors discovered the features of the typical bubble sound with respect to the time waveform and the frequency spectrum, and developed a new bubble-detection algorithm based on linear predictive signal processing. An experiment for bubble detection is executed, using a material to demonstrate the bubble-detection Doppler method and data recorded in the simulated 300-m manned submergence. It is verified that the proposed method has nearly the same performance as that of an expert. Finally, this paper discusses the phenomenon where the frequency of the bubble decreases with the increase in bubble generation. [ABSTRACT FROM AUTHOR]

The ability to retrieve by similarity is one powerful way to improve the human interface in an image database. In this paper, graphic patterns constructed as a set of primitive patterns formed from closed regions are the target images. When recognizing this kind of graphic pattern, people perform grouping. The partial patterns formed by this grouping play a major role in the similari- ty between graphic patterns. Consequently, the partial patterns that result from grouping must be introduced into the image representation as search keys. Furthermore, it would be desirable to have this reputation automatically generated. In this paper, we propose a method where a representation in the part-of hierarchy of partial patterns is used as the graphic pattern representation; this representation is generated from the raw image of the graphic pattern. This method uses the rules for visual characteristics for grouping in humans. First, partial patterns are formed by bottom-up processing. Then, by comparing the stability of the final partial patterns, partial patterns that do not match human perception are deleted and missing partial patterns are searched for and added. A prototype system was built based on this method, and the method's adequacy was verified. [ABSTRACT FROM AUTHOR]

This paper considers the long instruction word (LIW) computer and proposes the concept of the delayed execution for each field instruction composing LIW. The introduction of this concept makes it possible to adjust the execution timing in a flexible way for the field instructions in the execution of LIW. The speed is mi' proved by the overlapped execution of the instances in the loop or the call of subroutines. It is also possible to eliminate the unused instruction field. This paper presents the basic structure for the LIW computer with such a delayed instruction-execution scheme. It is seen as a result of simulation that the speed of the LIW computer can be improved by 8 to 58 percent and the number of instruction words can be reduced by introducing the proposed delayed instruction-execution scheme. [ABSTRACT FROM AUTHOR]

Many human activities are based on visual recognition of a scene. Development of scene recognition capability on computer is essential to the development of an intelligent robot. This paper proposes a three-dimensional (3-D) object recognition system using functional models. In conventional geometric model-based recognition, one reference model must be provided for each possible object shape in the same category. This paper proposes a functional model that will allow flexibility in representation of objects belonging to the same category. Experiments were conducted to provide measurement data for demonstrating this functional model-based object recognition technique. Scene segmentation uses both gray scale image and range image to provide superior segmentation results. The performance of a functional model-based method for recognizing objects with different shapes that belong to the same functional category is demonstrated. [ABSTRACT FROM AUTHOR]

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 papers, 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 required for scheduling. Furthermore, as examples of application of this algorithm, it is described how it is applied to inverse kinematics and inverse dynamics problems. [ABSTRACT FROM AUTHOR]

This paper describes an automatic detection system which extracts pathological areas from double contrast stomach x-ray images developed for computer-assisted diagnosis of stomach x-ray images. This paper examines the image for stomach canter, especially the convergent fold pattern of the stomach wall which is inherent to the early stage of cancer, and extracts the pattern from the x-ray image. The actual processing procedure is divided largely into the following four stages: (1) extraction of the border of the fold region; (2) extraction of contrasted regions of the bowel; (3) evaluation of the fold convergence; and (4) extraction of the lesion candidates. In this paper, a new feature parameter called convergence index is defined to represent quantitatively the extent of convergence of the folds on the stomach wall. The detailed computation procedures for the convergence index are presented. Finally, an experiment is presented for the actual 25 examples of double contrast stomach x-ray images, and it is demonstrated that the proposed system has a fairly high detection performance for the cancer lesion with fold convergence. No study has been presented on the recognition of the pathological pattern for the stomach cancer in the double contrast stomach x-ray image, and the result in this paper is expected to provide an important clue to the realization of the future automatic diagnosis of the stomach x-ray images. [ABSTRACT FROM AUTHOR]

This paper discusses an organization of a parallel memory, in which any local area of a two-dimensional (2-D) array can be accessed. The proposed memory system is composed of a memory array, which is a 2-D array composed of memory modules and a 2-D interconnection network with a 2-D array of input/output terminals. It is used with a 2-D processor array for local parallel processing, realizing a parallel access to subarrays of the 2-D array stored in the memory array. This paper describes a method to store the 2-D array in the memory system, a method of address generation for the memory array to perform parallel access, and a control method for the interconnection network. It is shown that those ideas can be realized by a simple hardware, and the proposed memory system is useful in the computer executing the local parallel processing of 2-D arrays. [ABSTRACT FROM AUTHOR]

Labeling is a procedure by which labels are assigned separately to a number of con- netted components, and it is also one of the important functions in the image processing system. In the conventional raster-scanned labeling, labels are assigned temporarily in a small local area. Then a large number of temporary labels (pairs of connected labels) is generated for the same connected component, and a long processing time is required to unify and transform them into the final label. Prom such a viewpoint, this paper discusses the reduction of processing time for the unification of pairs of connected labels. As a result, it is concluded that the following two approaches are effective: (1) simplify the table structure for storing the pairs of connected labels; and (2) reduce the generation of the pairs of connected labels. The following MIN-MAX method is devised as a means to realize (1). In the table storing the pairs of connected labels, MAX of the two temporary labels forming the pair of connected labels is adopted as the address, and MIN is used as the content data. To realize (2), it is noted that the concave and indented connected components often produce the pair of connected labels. The pixel-embedding and the forward pixel referring methods are devised for such situations. This paper presents the algorithms for those methods, and reports on the result of evaluation. [ABSTRACT FROM AUTHOR]

This paper describes the outline and implementation of the declarative debugging system DDS. The purpose of DOS is to provide the following debugging system for the functional program without a side effect: (1) The programmer specifies the result of execution and the intermediate result expected to the program (defines in a declarative way, and the system detects the bug automatically based on that specification; (2) an efficient guide is provided to the programmer so that the required input is less and the input can easily be given; and (3) the system has an efficient bug detection mechanism in terms of the memory capacity and the computational complexity. It is an interactive system which can be applied to a wide range of programs. This paper proposes a mechanism called filter, which gives an efficient realization of DDS. The filter is a mechanism which realizes the tabulation technique by a small-capacity memory, by extending the technique from the viewpoint of the bug detection. The filter is a mechanism which selectively retains the instances needed in the bug detection and controls the function call of the program using the retained data. An experimental system of DDS is constructed on VAX/VMS using Common Lisp. Debugging examples are shown, indicating the usefulness of DDS. [ABSTRACT FROM AUTHOR]

This paper evaluates the EM-3, a data-driven machine with advanced control mechanism. The advanced control mechanism with pseudo-result concept has been introduced into the data-driven mechanism. To evaluate this mechanism on a parallel processing environment, the prototype machine has been developed. Five benchmark programs, which have different characteristics, are evaluated by both software simulator and a prototype machine. This paper presents the results of discussing the data-driven mechanism with advanced control in the list processing system. The profiles of parallelism for the five programs, dynamic execution rate of instructions, and the characteristics of waiting time in a matching store are described. Finally, the performance of the EM-3 prototype is shown as well as the effectiveness of introducing the advanced control mechanism. [ABSTRACT FROM AUTHOR]

The fractal theory proposed by Mandelbrot is applied primarily to computer graphics and related problems 88 a means to generate a pseudo-natural image. In contrast to those problems dealing with natural images, it is possible to apply the fractal theory as a means to approximate actual natural images. This paper considers such natural line-images as a coastline and the contour of a mountain, and presents a method to generate an image with apparently high resolution by applying the fractal theory based on a small amount of information. A feature of this method is the use of an algorithm called squig to generate the fractal curve, which is also proposed by Mandelbrot. The method recursively partitions the original image and generates the fractal curve by determining the internal path. It has several advantages such as the property that self-intersection is not produced in principle. In this paper, the properties of the squig are described first. Then the proposed algorithm is applied to the line-image composed of a coastline, and the result is presented. As a result of experiment, it is seen that the data for the chain code is compressed to some 1/10, resulting in a visually natural image. [ABSTRACT FROM AUTHOR]

This paper presents the basic idea in the design of the data-flow language DFC and problems and their solutions in its implementation on the data-flow computer SIGMA-1. DFC is a data-flow language designed with consideration of the compatibility to C language. In the first part of the paper, a design to integrate the functional properties while maintaining the compatibility to C language is shown for the conditional and loop sentences, which are the major components of DFC, as well as the data structure. Then the conversion procedure from DFC to the code of SIGMA-1 is described together with the problems and their solutions. Especially, the generation of a graph is discussed in detail, which enables the resource reclamation in execution with the data-flow computer SIGMA-1. [ABSTRACT FROM AUTHOR]

Various studies have been made on the construction of associative memory. This paper proposes a method of constructing an associative memory which exhibits almost the same associative ability as in the case where true information is given, even if an incomplete memorized information is given. The construction of the associative memory from the incomplete memorized information (leaning pattern) is an important problem related to the leaning function of the associative memory. The proposed method is to perform the singular-value decomposition of the space spanned by the leaning pattern, from which the space spanned by the memorized pattern is extracted. The difference of the singular values is utilized in the extraction of the space spanned by the memorized pattern. In the actual construction of the associative memory, it may frequently happen that only the incomplete memorized information disturbed by noise Is available. It is very important from the practical viewpoint to consider the construction of the associative memory in such a noisy environment. In the proposed method, it is not necessary to know to which memorized pattern each learning pattern belongs (i.e., supervisor). The method is thus a kind of learning without a supervisor. This paper discusses also the construction of the associative memory with a supervisor, together with the role of the supervisor in the associative memory. [ABSTRACT FROM AUTHOR]

An illusion is not simply a vision-produced error, but a phenomenon produced in the normal visual sensation. To clarify the visual perception process, various studies have been made concerning illusions, especially the geometrical illusion. This paper presents a model of the illusion process using figure transformation rules, and discusses the illusion using the model. The figure transformation rules used in this paper are as follows: 1. The acute angle is perceived to be larger, and the obtuse angle is perceived to be smaller. 2. The segment forming an acute angle is perceived to be shorter, and the segment forming an obtuse angle is perceived to be longer. 3. When two segments intersect, the segment is perceived to be longer if the point of intersection is close to the mid-point and the angle is close to the right angle. 4. The vertex shifts along the line of bisection of the angle at the vertex, in the direction corresponding to the larger perception of the acute angle and smaller perception of the obtuse angle. Applying these rules to typical figures of geometrical illusion, results corresponding to human illusion were obtained, indicating the validity of the transformation rules. [ABSTRACT FROM AUTHOR]

This paper discusses a logical verificational theory GQOT for concurrent processes which communicate and synchronize by asynchronous message passing. In concurrent processes, especially, in distributed systems, each process acts independently, and yet one operation is done as a whole by communicating and synchronizing. Thus, regarding each process as having its own local time, we formalize each by a temporal theory QOT. Then regarding all the concurrent processes as a complete graph with each process as a node, we formalize it as space G. GQOT is the merge of G and QOT. In this paper we define this GQOT and, moreover, to make it more suitable for concurrent processes, introduce a sort of action, concept of interval-time and an operator "next." Then, we show the description and verification of the concurrent processes and its properties. [ABSTRACT FROM AUTHOR]

This paper presents a vectorization processing method for circuit analyses using a vector computer. It had been difficult in circuit analyses to evaluate device models with an adequately long vector length, which is the most expensive task in the computation. Therefore use of a vector computer could improve the computation time only a few times. In the proposed method, the evaluation of device models is carried out at the level of a basic element and each evaluation is vectorized throughout the circuit matrix. It is shown that neither the forward nor backward substitutions can be ignored in solving a sparse matrix with the LU decomposition method. Therefore, the vectorization is applied to the whole matrix-solving process. These algorithms are realized in a user-defined model circuit analysis program FINAP-VP. As a result, all the main processes of the analysis loop are vectorized with the length of the order of a hundred to ten thousand so that the analysis time for the scalar mode was improved by a factor of more than 10. This paper describes the method of vectorization of the device-models evaluation and the circuit matrix solution (which are the main process in a circuit analysis). The results of the benchmark tests using the vector-computer FACOM-VP, are also described. [ABSTRACT FROM AUTHOR]

This paper considers distributed algorithms for solving the problem πp to test whether for any processor in a network, any one of the adjacent processors is faulty. First, we show that it is not solvable when processors are asynchronous or when there is no upper limit in the transmission delay along the link. Next, we define a network (PL-synchronized network) which assumes a certain kind of synchronicity in processors and their communication. Whether or not πp is solvable in a PL-synchronized network depends on knowledge of the network topology (for example, identifiers of adjacent processors, the number of processors in a network, and edge connectivity of a network) initially available at each processor. This paper examines how the knowledge available at each processor affects the conditions that πp is solvable (situation of faults of processors and links in the overall network). [ABSTRACT FROM AUTHOR]

This paper aims at a constructive description of which neural network model can represent the human problem-solving process and how the process is related to the various human memories by what context. From such a viewpoint, a neural network model is constructed for the representation of the problem-solving process. In this paper, a model for the addition process is constructed as the first step, using the associative memory model HASP (human associative processor) proposed by one of the present authors. The model is composed of the following components: the procedure memory, which stores and retrieves the procedures of the addition; semantics memory, which stores the knowledge about the addition such as 2 + 2 = 4; the working memory, which temporarily stores the external and internal information; and the goal memory, which stores the problem-solving process as a chain of subgoals, and manages the flow of procedures from one higher level in the control hierarchy. In this study, a computer simulation was performed for the addition processes for several numbers with multiple digits, and it is shown that the addition process can be represented. Then the computer simulation is made for the generation of four kinds of bugs in the addition. It is shown that the bug generation can be represented by the model. [ABSTRACT FROM AUTHOR]

This paper considers the communication protocol whose specification is described algebraically in a style of an "abstract sequential machine." A method is presented to verify the progress property of the protocol, such that the transmitted data will eventually be received. First, by the algebraic method, we verify some static properties (invariants) which hold in any state reachable by the execution of the state transitions permitted by the protocol. Also, we verify the relations which hold between the states before and after the execution of each state transition. These relations are transformed into the formulas of the temporal logic by using some transformation rules. At the same time, the formulas of the temporal logic are provided as the assumptions for the stations and communication lines, which are needed in the discussion of progress property of the protocol, such that the communication lines are not functionally cut off. Using these formulas and standard axioms in the temporal logic (inference rules), it is shown that the predicates representing the progress property of the protocol are true. The foregoing is the outline of the discussions in this paper. This paper applies the method to Stenning's data transfer protocol, and the progress property is verified. [ABSTRACT FROM AUTHOR]

A two-person perfect-information game is represented by a minimax game tree and, by solving the tree, we can obtain the result of the game when both players choose perfect moves at all the positions. To this end, various search procedures have been proposed. In this paper, these procedures are modified to implement them on a parallel computer consisting of in processors, and variations of the computation time are investigated with in being a parameter. As a theoretical result, we point out that the speedup ratio of the computation time of solving a game tree by in processors to that by 1 processor may become larger than in (acceleration anomaly) or smaller than 1 (detrimental anomaly) in general. Also, we show that the detrimental anomaly does not occur as long as the five search procedures investigated in this paper are used. Next, through simulation experiments, it is shown that the speedup ratio is considerably smaller than in, and its cause is discussed. The eligible search is considered to be the best among the search procedure investigated. [ABSTRACT FROM AUTHOR]

This paper discusses the conceptual design of a knowledge processing system. First, by means of knowledge processing technology, a new relationship is established between man and computers, and it becomes possible to adopt a new problem-solving style. The paper discusses also the need to analyze the types of problems man has to solve, the manner of problem solving, and the limit to the capability of knowledge processing to design an effective computer-aided problem-solving system. It is concluded that the new problem-solving system must be a knowledge processing system founded on the model-based method. Then the requirements for the knowledge processing system and, in particular, for the knowledge representation language, are discussed. Finally, an example is used to show that a system satisfying these requirements is possible. Here, the importance of the model building concept is stressed for establishing the new problem-solving style and the declarative language including data structure for realizing the knowledge processing system that can aid the process. In general, the real problems are very complex, and it is impossible to solve them by a simple procedure. However, we have to approach the solution through a trial sand-error process. The knowledge processing system must be able to aid man in this process very naturally and without any restrictions on man's capability. [ABSTRACT FROM AUTHOR]

With the recent widespread application of computer graphics, a management system for graphic data is required which is suited to interactive processing. This paper discusses the management structure for the line data, which can realize a retrieval in an efficient way according to the spatial relations. The dynamic data management structure called the BD time, which was developed by the authors for the multidimensional point data management, is employed. In the proposed system, the BD tree is modified into a form (nonpacket type) suited to high-speed processing, and is extended to suit the line data. In this system, the segment is managed by its centroid and the circumscribed quadrilateral. The BD tree is composed of a set of centroids, where each node has information concerning the circumscribed quadrilaterals for all segments in the subtree. The retrieval is made efficient by the information concerning the circumscribed quadrilateral. In this paper, the data structure for the line data management is discussed first. Then various retrieval algorithms which depend on the spatial relations according to each application are discussed in detail. Finally, the usefulness of the proposed data structure is demonstrated by a retrieval experiment of actual geographical data. [ABSTRACT FROM AUTHOR]

This paper proposes a square root hardware algorithm using the redundant binary representation in the internal computation. A discussion is made for the realization of a combinatorial square-rooter based on the algorithm. This paper considers the computation of the mantissa in square-rooting for the binary normalized floating-point representation. The proposed algorithm is a kind of subtract-and-shift square-root method. Partial reminders are represented by the redundant binary representation, where each digit is an element of (-1, 0, 1). Then each digit of the square root is determined from (-1, 0, 1), by examining the upper three digits of the partial remainder. The computation for the partial remainder is affected in the redundant binary number system. Finally, the square root determined in the redundant binary representation is converted into the ordinary binary representation. In the redundant binary representation, the addition of two numbers can be effected without carry propagation. Consequently, by using the combinational circuit, each digit of the square root can be determined in a constant time, independently of the number of digits of the operand. The computation time for the n-bit square rooter (number of stages) is proportional to n. The number of logic elements in the circuit is proportional to n². The hardware structure is a regular cellular array, which is suited for VLSI implementation. When the circuit is implemented on a VLSI chip, the chip is proportional to n². The proposed square rooter has nearly the same circuit structure and the hardware complexity, compared with the conventional subtract-and-shift square rooter using ripple carry adder. The computation time is approximately one-fifth for 32-bit and one-tenth for 64-bit, compared with earlier circuits. [ABSTRACT FROM AUTHOR]

The communication sequential processes (CSP) system proposed by Hoare is a model for parallel computation which has no shared variables and performs information exchange and synchronization among processes by means of communication commands. In this paper we first consider a set of states for the given CSP program. Using a binary relation on the set, we introduce a semantics representing only the input-output relations of the CSP program. Based on this semantics, we propose an axiom system which serves to verify the partial correctness of CSP. We prove the soundness of this axiom system. The axiom system proposed in this paper differs from the previously proposed in this paper differs from the previously proposed systems in the following aspects. In our system, the inferences proceed simultaneously over all processes. On the other hand, conventional methods adopt a procedure wherein a given property is first proved independently for each process and it is then shown that a certain condition holds among the processes. Our method of proof is a more direct representation of the actual execution of process. [ABSTRACT FROM AUTHOR]

This paper discusses the systolic algorithm where the input and output are serial and the processing is performed in parallel (called serial-I/O, parallel-processing scheme). This paper considers the following three kinds of parallel algorithms which have been known as the algorithms for different problems: the palindrome recognizer, multiplication of binary sequences, and the pattern-matching algorithm. Based on these algorithms, a new systolic convolver is proposed which computes the Convolution of two infinite sequences in real tine. As an application of the systolic convolver, a systolic pattern-matching algorithm is proposed which is the fastest and the optimum among the presently known algorithms considering the constant coefficients. By the data-routing proposed in this paper, a clear design principle is formulated for the real-time systolic convolver, which greatly simplifies the proof for the validity and provides an easy understanding of the real-tune systolic convolution algorithm. [ABSTRACT FROM AUTHOR]