Search

In this paper, the authors propose a robust background estimation algorithm, which is a technique for adaptively estimating background in response to changes in the environment based on robust statistics, and a technique for automatically adjusting the adaptation rate in response to changes in the environment. In monitoring systems and the like using stationary cameras, it is necessary to detect moving objects from the captured image series, and recognize and identify the detected subject. The most simple and representative method for moving object detection, which is used in many fields, is the background subtraction method for detecting moving objects by the difference between the background image and the current scene. This method requires a background image which does not include a moving object. However, it is difficult to acquire a background image under conditions in which moving objects are continually included in the scene. Also, when the environment changes, adaptive revision must be performed in response to the changes in the background image. Furthermore, in an environment where sections of the background change over time in different ways, it is important to determine the appropriate number of frames needed to estimate the background. In this paper, therefore, the authors propose a method for adaptive background estimation using M-estimation, a known robust statistics technique. Also, the authors propose a technique for adjusting the number of frames necessary for background estimation by varying the adaptation rate to the environment using robust template matching. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(7): 98– 108, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10612 [ABSTRACT FROM AUTHOR]

If two algorithms of Fresnel transformation are used with suitable parameters, the expansion of images modeled after multiresolution analysis (FREBAS transformation) is possible. This paper proposes a denoising technique of natural images using FREBAS transformation. Constrained least square filter applying in FREBAS transformed space removes noise superimposed on signals very well, however, that noise with specific patterns might remain on the images when processing images have small SN ratio. In this paper we focus our attention on this noise that exhibits isolationism in FREBAS transformed space and propose a new denoising technique that introduces non-linear noise processing in FREBAS transformed space. It was shown that the noises with specific patterns were favorably removed in simulation experiment. In addition, we applied the proposed technique to natural images which contain noise to and compare the method with other denoising techniques from the viewpoint of SNR improvement, image degradation, remained noises. As a result, the proposed technique could remove noise while controlling image degradation and also obtain significant improvements in the SNR on average. In particular, we confirmed that the proposed technique had excellent denoising performance for images with large variations in amplitude. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(3): 1–11, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20675 [ABSTRACT FROM AUTHOR]

A set of autonomous distributed robots is a group of robots that each function independently but cooperatively. In this paper we treat the pattern formation problem for a set of autonomous distributed robots. The pattern formation problem involves having a set of robots take up a certain pattern (a formation) given that their initial states place them in arbitrary locations. The robots used in this research function in an asynchronous manner iterating through a cycle of four modes of behavior: wait, observe, compute, and move. The robots cannot record information relating to the previous cycle (the results of observations or computations). In addition, the robots cannot be distinguished by their external appearance and all of the robots execute the same algorithm. In Ref. 1 it was shown that a pattern formation algorithm could be constructed for an odd number of robots with agreement on one axis if an observational constraint assumption was fulfilled. In this paper we show that a pattern formation algorithm can be constructed even when this observational constraint assumption does not hold. © 2006 Wiley Periodicals, Inc. Syst Comp Jpn, 37(10): 89–100, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20331 [ABSTRACT FROM AUTHOR]

One of the issues of autonomous Web services is that precise business protocols across systems are not always predefined. A likely solution to this problem is to dynamically generate business protocols by matching external interface definitions and relating information exposed by each system. The current Web services have a feature called a portType that describes an external interface of a system. This paper proposes to add a new concept called “behavior pattern” to the portType, then provides an algorithm to dynamically generate business protocols. The algorithm compares the portTypes of the concerned system and the opposite system, verifies the possibility of their interaction, and automatically reduces the behavior patterns within executable range. The paper also evaluates this algorithm by applying it to some use cases and shows that the method provides useful early results for realization of autonomous Web services. © 2006 Wiley Periodicals, Inc. Syst Comp Jpn, 37(2): 37–45, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20352 [ABSTRACT FROM AUTHOR]

This paper presents a systematic overview of our work for more than a decade on image-processing algorithms for lung cancer screening by CT. Most of the images handled at the mass-screening level are normal cases, and the rate of detection of lung tumors is no more than a few percent. In order to detect such rare tumors with high accuracy, there must be a technique that can correctly detect small changes in the image. On the other hand, the problem can arise that a large number of normal tissues are incorrectly detected. This paper outlines the image-processing algorithm developed by us to correctly detect tumors while reducing overdetection. In particular, we describe in detail the principles and properties of quoit filtering, which was devised for accurate detection of tumors in the first stage. © 2005 Wiley Periodicals, Inc. Syst Comp Jpn, 36(7): 40–53, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20156 [ABSTRACT FROM AUTHOR]

This paper is concerned with the application of the parameter-free genetic algorithm (PfGA) proposed by Sawai and colleagues and the parallel distributed PfGA, to the fixed channel assignment problem. The results of the investigation are presented. The PfGA does not include parameters such as the population size, the crossover rate, and the mutation rate, which have been indispensable in the conventional genetic algorithm (GA). This eliminates parameter tuning for each problem, which is a very useful property in practice. Although the applications of PfGA to function optimization in 5 to 10 dimensions have been reported, there has been no report on the performance when it is applied to combinatorial optimization with a larger search space, and it remains a practically important problem to examine the performance in such a case. This paper considers the application of the PfGA to the fixed channel assignment problem, which is a combinatorial optimization problem. The sequence representation by the random keys is investigated, and it is shown that the PfGA and the parallel distributed PfGA have as high a performance in the fixed channel assignment problem as in the function optimization problem. © 2005 Wiley Periodicals, Inc. Syst Comp Jpn, 36(4): 71–81, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10328 [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]

Turbo codes are known as a class of error-correcting codes which have high error-correcting performance with efficient decoding algorithm. Characteristics of the iterative decoding algorithm have been studied in detail through a variety of numerical experiments, but theoretical results are still insufficient. In this paper, this issue is addressed from the information geometrical viewpoint. As a result, a mathematical framework for analyzing turbo codes is obtained, and some of the fundamental properties of turbo decoding are elucidated based on this framework. Recently, it has been pointed out that the turbo decoding algorithm is related to the decoding algorithm of low-density parity check codes, the computation method of Bethe approximation in statistical physics, and the belief propagation algorithm of Bayesian networks. The mathematical framework given in the present paper can also be used to analyze these wide classes of iterative computation methods, and hence represent a new analysis tool. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 36(1): 79–87, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10359 [ABSTRACT FROM AUTHOR]

While the original SVM seeks the discriminative plane that maximizes the margin in the feature space (the Hilbert space), this paper investigates the framework that maximizes the margin in the input space. This framework is considered to be effective for cases in which a priori knowledge is embedded as input space estimates. In the approach taken in this paper, approximating the margin in the input space by Taylor expansion is essential. The algorithm obtained is a kind of alternating optimization comprising the step of obtaining projections onto the discriminative plane from sample points by Newton's method and the step of determining parameters of the discriminative plane by convex quadratic programming. The algorithm converges to a stably local optimal solution under comparatively lenient conditions. In addition, the optimization problem to be solved includes the original SVM as a special case. However, since the amount of computation increases as the dimensions of the input space increase in the proposed algorithm, this paper proposes a simplified algorithm obtained by combining the original SVM and the abridged proposed algorithm. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 35(14): 78–86, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10631 [ABSTRACT FROM AUTHOR]

For the set S = {1,2,…,n}, a permutation π:S → S such that π(i)≠i is called a complete permutation, and the string π(1)π(2)…π(n) is called a derangement. In this paper, the authors consider the generation of a list that contains one instance of every derangement. Sequential generation, which sequentially generates a string by interchanging characters in the string, can generate the list more efficiently when fewer characters are interchanged. If 𝒫(S) denotes the list of derangements and deg(𝒫(S)) denotes the maximum value of the numbers of characters that are interchanged, no list of derangements such that deg(𝒫(S)) = O(1) is known as of today. In this paper, the authors notice that a derangement can be decomposed into mutually disjoint cycles to show that there exists no list of derangements such that deg(𝒫(S)) = 2. Also, in the second half of this paper, they consider an algorithm for generating a list for which deg(𝒫(S)) = 4 for |S|≥4. According to this algorithm, the average number of characters that are interchanged is roughly 2.980. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 35(12): 25–31, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10531 [ABSTRACT FROM AUTHOR]

In this paper the authors report on a new algorithm used to separate an object from its background using a background image. In the past, simple background subtraction has been used because of its low processing costs and ease of implementation. However, because this method depends solely on brightness patterns in the object and shadows, it has problems such as an inability to deal with poor lighting conditions and an inability to detect regions in which the brightness levels of the object and shadows are similar. In order to resolve these problems, in this paper the authors propose a new filter process called a Radial Reach Filter (RRF). The authors define a new statistic called a Radial Reach Correlation (RRC) used to determine on a pixel-by-pixel basis the similar and dissimilar areas between a background image and a current scene. They then evaluate the local texture at pixel-level resolution while reducing the effects of variations in lighting. In addition, by introducing a mechanism to adjust the defined region adaptively based on local characteristics of the background image, the authors are able to work with various shadows and objects in the scene. The authors perform a theoretical evaluation and experiments using real images to demonstrate the validity of their proposed method. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 35(10): 63–73, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10590 [ABSTRACT FROM AUTHOR]

This paper proposes a scheme for generating multiple flight routes using genetic algorithms (GAs). In obtaining multiple routes or multiroutes by GAs simultaneously, there is a problem of collisions or near-misses occurring due to interference between the routes (closeness or intersecting of the routes) when similar routes are generated. The proposed scheme realizes a scheme for searching multiple flight routes without interference by incorporating a method for correcting their fitness on the basis of the neighborhood density for maintaining the variety and the degree of interference or the interference degree for obtaining routes that do not come close to or intersect one another. In addition, this paper proposes a priority candidate preserving strategy that preserves superior multiple individuals for each generation in order to improve the search performance. Computer simulation results confirm that the scheme proposed generates multiple flight routes without interference, indicating its efficacy. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 35(2): 39–48, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10428 [ABSTRACT FROM AUTHOR]

This paper proposed a method of generating seamless textures by means of a genetic algorithm (GA). When the texture of a large region is built up from textures in regions of finite size, textural discontinuities usually arise at the boundaries between these regions. A seamless texture is one in which such discontinuities do not occur. A fractal method has been proposed for the generation of seamless textures, but in that method it is difficult to predict what seamless texture will be generated. Pattern generation cannot be controlled in such a way that a texture similar to an already generated seamless texture will be produced. In this paper an attempt is made to solve this problem by applying the GA to texture generation, yielding seamless textures that are similar to seamless textures previously generated. This method can also be used to generate multiple seamless textures. By using the proposed method, a texture with a user-selected pattern can be generated from simultaneously displayed seamless textures. In addition, to avoid monotonous behavior due to the arrangement of textures of a single kind, a method of generating seamless textures with the same boundary but with different internal pattern (group texture) is proposed. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 35(2): 91–99, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1229 [ABSTRACT FROM AUTHOR]

This paper discusses an algorithm that recognizes multiparty speech with complex turn taking. In recognition of the conversation of multiple speakers, it is necessary to know not only what is spoken, as in the conventional system, but also who spoke up to what point. The purpose of this paper is to find a method to solve this problem. The representation of the likelihood of turn taking is included in the language model in the continuous speech recognition system, and the speech properties of each speaker are represented by a statistical model. Using this approach, two algorithms are proposed that estimate simultaneously and in parallel the speaker and the speech content. Recognition experiments using conversation in TV sports news show that the proposed method can correct a maximum of 29.5% of the errors in the recognition of speech content and 93.0% of the errors in recognition of the speaker. © 2003 Wiley Periodicals, Inc. Syst Comp Jpn, 34(13): 103–111, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1223 [ABSTRACT FROM AUTHOR]

In this paper, we propose parallel algorithms to solve the selection problem on the Bulk-Synchronous Parallel (BSP) model and the BSP* model. The BSP and BSP* models are recently proposed parallel computation models. They can represent the communication cost, a vital element in the latest parallel computations, in terms of the parameters of the synchronization period L, the reciprocal g of the communication network bandwidth, and the packet size it B. In this paper, we propose a parallel algorithm having an internal computation time O[(n/p) + dlogploglogn + L(logploglogn)/(logd)] and a communication time O[g(n/p) + (gd + L)(logploglogn)/(logd)], on the BSP model, and a parallel algorithm having an internal computation time O[(n/p) + dlogploglogn + L(logploglogn)/(logd)] and a communication time O[g(n/(pB)) + (n/p)1/7(logp)6/7) + (gd + L)(logploglogn)/(logd)] on the BSP* model for any integer d(1 ≤ d ≤ logn) to solve the problem of selecting n data with p processors. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(12): 97–107, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1170 [ABSTRACT FROM AUTHOR]

The paper proposes an improvement of coding performance for a color image compression scheme based on the adaptive orthogonalized transform (AOT). The paper proposes that the performance of the coder will be accelerated by reducing the dictionary size to 25% and by maintaining the approximation gain of the LBG algorithm by virtue of the fact that the AOT increases the approximation gain of the dictionary. The effectiveness of the proposal is confirmed by numerical experiments. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(8): 1–8, 2002; Published online in Wiley InterScience (www.interscience. wiley.com). DOI 10.1002/scj.10218 [ABSTRACT FROM AUTHOR]

In this paper, we propose a method for non-scan design for testability of controllers that are logically synthesized from a finite state machine (FSM), which provides complete fault efficiency. In the previously used scan method, a test pattern for the combinational circuits of a controller was generated to achieve complete fault efficiency and was applied by using a scan flip-flop. However, in the scan method, the test sequence becomes large and various problems prevent the test from being performed at the actual operating speed. In this paper, the test pattern of the combinational circuits of the controller does not use scan flip-flops, but instead uses the state transitions of an FSM. The proposed method allows performance of the test at the actual operating speed of the circuit, thus reducing the testing time compared to the conventional methods. Moreover, experimental results using benchmarks show that the area overhead is small. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(5): 64–75, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1128 [ABSTRACT FROM AUTHOR]

Tree-based clustering is an effective method for sharing the state of an HMM in which clustering is applied to a set of context-dependent models with the phoneme context as the splitting condition. In past papers, the method has been restricted to the single Gaussian HMM. The single Gaussian HMM, however, is insufficient for representing the acoustic features, and an adequate topology (sharing of HMM state) will not necessarily be realized. Furthermore, in order to arrive at a state-sharing model with the desired number of mixtures, the process of doubling the number of mixtures and the embedded training must be iterated after the tree-based clustering, which increases the time for training. Consequently, this paper proposes a method in which the tree-based clustering algorithm for the single Gaussian HMM is extended to the clustering of the mixed Gaussian HMM. The proposed method reduces the training time to approximately one-third that of the conventional method of handling the single Gaussian HMM. A recognition experiment using a phone typewriter and a recognition experiment for continuous word demonstrate that the recognition rate is improved by one to two points. © 2002 Wiley Periodicals, Inc. Syst Comp Jpn, 33(4): 40–49, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.1118 [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm that automatically acquires a new recognition primitive by splitting the training sample so that the likeness of the whole training sample to the model is maximized. The primitive obtained by the proposed method is a primitive integrating several time-continuous phonemes. It is called an acoustic similarity-based primitive (ASP). The algorithm proposed in this paper performs in parallel ASP acquisition and ASP modeling by HMnet. The two are simultaneously optimized. In phoneme recognition experiments for six specified speakers, the recognition rate was improved by approximately 3.5% on the average, compared to the conventional phoneme HMnet, by increasing the number of candidates by approximately 14.6% on the average. A method is also proposed in which an ASP is built in a large-vocabulary continuous speech recognition system. In a recognition experiment with eight specified speakers, the accuracy of word recognition was improved by approximately 2.6%, compared to the phoneme HMnet. © 2001 Scripta Technica, Syst Comp Jpn, 33(1): 8–17, 2002 [ABSTRACT FROM AUTHOR]

In this paper, we will propose a causal broadcast protocol for distributed mobile systems. Since the mobile hosts are in general unspecified majority, and the computational capability and communication capability are considerably inferior to the static hosts, an algorithm is desired whose computational effort and traffic executed by the mobile hosts are small and the complexity will not depend on the number of mobile hosts if possible. Moreover, an algorithm is desired in which the processing for dealing with handoff accompanying the movements of the mobile hosts is smaller. This paper proposes an efficient causal broadcast protocol which pays attention to the hierarchical structure of the mobile hosts and mobile support stations. In the proposed technique, the message overhead (information content added to each message) does not depend on the number of mobile hosts. Moreover, the message overhead is smaller than in known techniques and this technique is excellent in the respect that both the delay time for dealing with handoff at the time of movements of the mobile terminals and the number of messages are small. © 2001 Scripta Technica, Syst Comp Jpn, 32(3): 65–75, 2001 [ABSTRACT FROM AUTHOR]

The problem in which an image containing moving objects is to be segmented into multiple subimages, each of which follows a single set of motion parameters, is called the global motion segmentation problem. The segmentation and the estimation of the motion parameters are mutually dependent, and consequently, it is difficult to solve independently the segmentation problem and the estimation problem for the motion parameters. This paper proposes a new algorithm for global motion segmentation. The proposed method directly processes the input image sequence, and the segmentation and the motion parameters are simultaneously estimated. This paper presents the detailed procedure for the computation and the application of the proposed method to the conversion from interlaced scanning to progressive scanning. © 2000 Scripta Technica, Syst Comp Jpn, 31(11): 92–100, 2000 [ABSTRACT FROM AUTHOR]

In this paper the authors describe a load balancing algorithm and its validity in a scalable tape archiver consisting of a small-scale tape archiver used as a single element and a tape migration device connected to these elements which enables the physical transfer of tapes. With the rapid development of small-scale archivers for multimedia applications in recent years, such archivers are expected to become commercial products in the near future. By connecting an arbitrary number of such inexpensive element archivers together, an archiver system of the desired scale can be created in a flexible and cost-efficient fashion. In this paper the authors describe their load balancing algorithm for use among the element archivers and then demonstrate its validity through simulations. By balancing any biases in the access frequency through the use of the tape migration mechanism, the authors show that considerable performance improvements can be obtained. In addition, they also show that the tape migration mechanism is useful for tape drive failures, as well as demonstrating that performance improvements can be obtained even when using file striping. Finally, the authors perform simulations using the access history for a satellite image database and show that the tape migration mechanism is useful for real-world applications as well. © 2000 Scripta Technica, Syst Comp Jpn, 31(5): 31–47, 2000 [ABSTRACT FROM AUTHOR]

This paper proposes a method of constructing 3D models from multiple range data which have no information on position. This method can combine data of an arbitrarily curved surface sampled from an arbitrary direction, without preliminary knowledge of viewpoints and extraction of features. The procedures are: an object is represented by discrete meshes; a Gaussian curvature at each node of the mesh is calculated; the meshes are mapped on a unit sphere; and matching of viewpoints is carried out by comparing the unit sphere. The discrete meshes are repeatedly re-formed until they are sufficiently close to the surface of the object. The transformation matrix for range data is calculated based on the correspondence of nodes of the discrete meshes obtained from the results of matching of the unit sphere. This paper describes the matching algorithm, and examples of applications of the algorithm to the construction of a “complete model” from multiple range images. © 1998 Scripta Technica, Syst Comp Jpn, 29(6): 82–90, 1998 [ABSTRACT FROM AUTHOR]

This paper presents a method for designing neural networks using a genetic algorithm (GA) with deterministic mutation (DM) based on learning. The GA presented in this paper has a large framework including DM, which is performed on the basis of the results from neural network learning. It can achieve better convergence properties than traditional GAs. This framework is an evolutional system based on mutual interaction between DM and traditional genetic operators including stochastic mutation. It is also a model of transcription and reverse transcription in DNA. We show that the present method is better than conventional GAs with respect to convergence in learning. © 1998 Scripta Technica. Syst. Comp Jpn, 29(3): 10–17, 1998 [ABSTRACT FROM AUTHOR]

In this paper a simple and efficient branch and bound algorithm to extract a maximum clique from an undirected graph is proposed. In this method the crucial point for improving the efficiency of the algorithm is how to make the search space small using a tighter bound. However, the processing time to implement that bound must be kept small. Thus, in this paper a very simple and clever sequential approximate coloring-arranging method is developed considering trade-offs between these two factors. Using this, an upper bound on the maximum clique size at each search step is computed and branches are pruned based on this bound. The total computation time has been successfully reduced using this method. It has been verified either by computational experiments or by comparing published experimental results that this algorithm is faster than other major algorithms on a wide range of random graphs with 600 or less vertices and on a number of random graphs with 1,000 vertices. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(5): 60–67, 1997 [ABSTRACT FROM AUTHOR]

In binocular stereo vision, since color and distance information can be obtained simultaneously by a passive method which will not affect the environment, it is expected to be commonly used in the vision of future mobile robots. However, it is necessary to solve difficult problems such as finding corresponding points in the right and left images. Many stereo algorithms dealing with this problem have been proposed so far, all with their own weaknesses. This paper considers the position reversal problem, in which the positions of the corresponding points change places on the right and left scan lines. This is a subject in which there has been little progress despite its importance in obstacle detection by mobile robots. It has been considered that the position reversal problem cannot be processed correctly in plain dynamic programming for global matching unless the assumption that the positions of the corresponding points do not change places is forced. In the method proposed in this paper, four states are set in the search for the corresponding points. The search using dynamic programming is performed in two stages so that the position reversal problem can be solved while the above assumption is maintained. Then, matching also becomes possible in the case of objects for which the positions of the corresponding points change places. The proposed method is experimentally applied to the search problem in which the positions of the corresponding points change places inside scan lines, and its effectiveness is verified. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(4): 25–35, 1997 [ABSTRACT FROM AUTHOR]

In this paper, a scheduling algorithm for multi-processor real-time systems with relative timing constraints and resource constraints is proposed. The proposed algorithm has the capability to satisfy any timing constraints expressed as inequalities in two variables and a constant. This implies that scheduling problems imposed on various timing constraints such as end-to-end timing constraints and/or relative timing constraints, which are known to be difficult to handle, can be solved. Since the problem addressed in this paper is a generalization of some NP-complete problems, it is difficult to solve efficiently. Thus, the goal of the authors is to derive a heuristic algorithm which performs well on many instances of the problem, although in some cases it will take enormous space and time. Experimental results show that the proposed algorithm achieves a success rate of 80% in 3 minutes of computation time. © 1997 Scripta Technica, Inc. Syst Comp Jpn, 28(3): 52–61, 1997 [ABSTRACT FROM AUTHOR]

Finding connected components of a digital image is a fundamental problem in image processing and image understanding. Although many applications must deal with gray-scale or color images, most parallel algorithms presented to date consider the problem only for binary images. This paper considers the problem related to the k-valid connected component of gray-scale images, which is a generalized concept of the connected component in binary images. This paper presents algorithms for the problem of n × n gray-scale images. An Exclusive Read Exclusive Write (EREW) PRAM algorithm that finds a maximal k-valid connected component in O(log k log n) time using n2/log n processors is shown here. We also show an Arbitrary Concurrent Read Concurrent Write (CRCW) PRAM algorithm and an EREW PRAM algorithm that find a maximal k-valid segmentation in a time of order O((log k + log*n)log n) and respectively, O(log2n) using n2 processors in both cases. © 1997 Scripta Technica, Inc. Syst Comp Jpn. 28 (1): 74–86, 1997 [ABSTRACT FROM AUTHOR]

This paper describes a mathematical model of dust particles having complex shapes, and an algorithm to identify them, aiming mainly at categorizing types of dust on an LSI wafer surface. Fractal dimension is used to represent the dust features. A conventional fractal dimension applied to specimens as a whole, however, does not sufficiently represent the shape of dust in each category of the model. This paper introduces a local fractal dimension into a global fractal dimension so that feature of a mathematical model can be represented. Also proposed is method based on mahalanobis' distance using a fractal characteristic valuable to categorize the data. The proposed method has been tested successively by using real data. [ABSTRACT FROM AUTHOR]

A self-stabilizing algorithm is a distributed algorithm that achieves its intended behavior regardless of the initial configuration. This paper discusses the self-stabilizing algorithm for the ring orientation problem (ROP). ROP is a problem where all processors on a ring network are to be oriented either clockwise or counter clockwise. It is known up to now for the network composed of an even number of processors that there does not exist a deterministic self-stabilizing algorithm to solve ROP under the D-daemon or the R/W daemon. On the other hand, a probabilistic self-stabilizing algorithm is known for ROP on a ring network with an arbitrary size under the D-daemon. This paper also presents a self-stabilizing algorithm for ROP on a ring network with an arbitrary size under the C-daemon. The result indicates that the classes of problems that can be solved by the C-daemon and the D-daemon, respectively, are substantially different. [ABSTRACT FROM AUTHOR]

In this paper an optimum algorithm to translate control flow graphs to dataflow graphs is proposed for dataflow execution of sequential programs. Some of the existing analysis methods restrict the specification of a program to be processes while others require a very high analysis cost. The algorithm proposed in this paper (CD translation algorithm), (1) with a very low cost, and (2) for any control structure that can be described by a control flow graph, (3) can generate dataflow programs that give an optimum dataflow execution. Furthermore, this proposed analysis algorithm is designed to handle task level control flow graphs as well as instruction level control flow graphs, which are accepted by the existing methods, so that optimum control is possible for task level dataflow execution. [ABSTRACT FROM AUTHOR]

This paper presents a neural network algorithm called SOLAR (Supervised One-shot Learning Algorithm for Real-valued inputs) that can complete learning by a single presentation of the real-valued inputs. The similarity matrix is introduced in SOLAR, which can measure the Euclidean distance between training instances represented by a real number. Based on the geometrical structure of the similarity matrix, the structure of the network, the connection weights, the learning parameters and the linear disciminant function are determined. Then, the learning is executed by a single presentation of the training set. The nonlinearly separable case by decomposing the set of supervisor signals into linearly separable sets. The main contribution of this paper is that SOLAR realizes a high-speed learning by a single presentation of the input data composed of real values and a large-scale complex set of data can be learned. This has been difficult in previous models. In addition, since the number of hidden units and the parameters are determined by the algorithm, there is no problem such as trial and error. [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 presents a new method for multiple fault diagnosis of combinational circuits using sensitizing input-pairs. A partition of a circuit under test into subtree circuits and a generation method for diagnostic test are described. The set of diagnostic tests used in this paper is one of sensitizing input-pairs that generate sensitizing paths including checkpoints on them. By studying the relation between a sensitizing path generated by a sensitizing input-pair and a subtree circuit, a method is presented for multiple fault diagnosis in the subtree circuit based on the fault-free and the faulty response observed at primary outputs. A deduction algorithm is described for a value at an output of a subtree circuit which does not have a primary output. The proposed method is applied to benchmark circuits having double faults, triple faults, and fourfold faults. Experimental results show that suspected faults are identified within 8 to 30 percent of all stuck-at 0 and 1 faults on all lines in the circuit. [ABSTRACT FROM AUTHOR]

The production system is suited to representing the miscellaneous pieces of human knowledge, and is used most widely in constructing the expert system. A problem is that a tremendous amount of time is required for the condition match, and an efficient condition match algorithm is desired. This paper considers the expert system which has been designed for the inference based on the semantic network, and aims at the realization of the high-speed condition match in the expert system rewritten by OPS5. The working memory elements which are the objects of investigation are mostly the knowledge of two-term relations, and the number of attributes usually is 2. This paper also proposes a data structure for the working memory, which can derive directly all working memory elements satisfying the condition, from the condition elements with 2 or less attributes. Using the proposed data structure, an algorithm is shown that can realize a high-speed condition match. It is shown for the considered expert system that the proposed algorithm can realize a higher speed than the conventional condition match algorithm [ABSTRACT FROM AUTHOR]

A self-stabilizing algorithm is a distributed algorithm that can solve problems, even when started in any arbitrary network configuration. This paper describes a self-stabilizing algorithm that solves mutual exclusion problems for three networks and complete networks. In a tree network or in a complete network, because of their symmetrical nature, mutual exclusion problems cannot be solved by uniform deterministic algorithms (all processors execute the same programs and do not assume the existence of mutually distinct identifiers). Thus, the algorithms introduced in this paper are superior to the existing ones in the following respects: (1) uniformity of algorithms; (2) forwardness of little atomic action of processor (read/write domain); and (3) finiteness of the state number of the processors. [ABSTRACT FROM AUTHOR]

This paper proposes a parallel mean-field approximation algorithm based on the mean-field theory. In the parallel mean-field algorithm, a stable configuration at each temperature is obtained by applying the mean-field approximation to each element in the state space of a system, so that an actual state is replaced with a mean state, and by sequentially updating the mean field. This makes the convergence of a learning process faster than those in the simulated annealing algorithm and the Boltzmann machine. This paper examines Peterson's idea from the viewpoint of the mean learning algorithm and constructs a parallel learning algorithm confirming the existence of its stable distribution. To improve the processing speed of the proposed method further, this paper introduces a new temperature scheduling method (maximum entropy cooling schedule) by reexamining the temperature schedule of the Monte Carlo process and analyzing changes of the maximum entropy at a transition of a mean field of the system. Computer simulations show that the proposed method produces the same results as the conventional method but with shorter computation time, and also that the proposed maximum-entropy cooling schedule agrees with a thermodynamic analogy. [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 presents a distributed algorithm for the single-source shortest-paths problem in a network with nonnegative integral link weights. Its message complexity is O(√nDe + e), where n is the number of processors, e is the number of links, and D is the maximum distance from the root. The known shortest-paths algorithm with the distance-dependent message complexity requires O(min(Dn + e, n²)) messages. The algorithm of this paper is more efficient for networks with D = o(n³/e) and D = ω(e/n). Moreover, the breadth-first search tree problem is considered. [ABSTRACT FROM AUTHOR]

The color image processing based on the color information is not concerned with the accuracy of the color information in the original image. The color representation transformation and the processing algorithm assume that the accuracy of the input image is sufficiently high. This paper considers the input of the RGB color image, and discusses the image input system, emphasizing the accuracy of the color information. Here, each pixel is inputted with sufficient intensity without saturation, independently of the brightness of the object, by the multistep exposure control. The obtained image is called the adaptive exposure color image since each pixel is inputted with an adequate exposure. This paper discusses also the exposure control using the variable electronic shutter function of the CCD camera, the pixel selection/storage algorithm for the time-series images with different exposure times, and the reduction of the input time by reducing the number of exposures. By an input experiment, it is verified that a stable input of the color image is realized for the scene with a high contrast, containing multiple colors and shadows. The region segmentation based on the chromatic component is considered, and it is shown that the adaptive exposure color image realizes satisfactory colors over the whole image compared to the ordinary color image. Thus the method is shown to be useful in improving the accuracy from the viewpoint of color discrimination and other applications. [ABSTRACT FROM AUTHOR]

This paper considers the case where the geometrical model for a 3-D object is given, and discusses the solution of the problem to cover the rotation of the object from a single (monocular) view image. The rigid body is represented by a set of vectors and the joint is represented by a unit vector corresponding to the rotational axis. For each rigid object, the connecting joint is included. The inner product between unit vectors as well as the scalar triple product are assumed as known. Using such a model, not only the rigid body which has widely been discussed, but also the object composed of rigid bodies and joints with the rotational degree of freedom can be handled by the same framework. In the previous paper, it was shown that such a problem to determine the rotational posture of the object can be represented by a graph, and the solvability of the problem is discussed. The basic problem represented by the tree structure is formulated. This paper defines anew the concept of connection index, and classifies the tree-structure basic problems. For the basic problem with the connection index being 0 and 1, an algorithm is proposed which can estimate the rotations of the rigid subobject. The algorithms have the common structure for each connection index, and can be easily be constructed by defining the geometrical inference inherent to each basic problem. The usefulness of the algorithm is demonstrated through the individual experiments. [ABSTRACT FROM AUTHOR]

Conventional optical flow estimation algorithms were based on fundamental constraint equations that assume the existence of a single-flow vector at each point in the image. However, since these fundamental constraint equations are not satisfied in certain regions, correct flow estimation can become impossible. Such regions include those where multiple flows arise due to objects with reflective surfaces and transparency or in regions where the flows become discontinuous at the boundaries of an object. This paper derives first extensions of the conventional fundamental constraint equations for optical flow in the real and frequency domains that are satisfied when n flow vectors exist at each point in the image. Algorithms are also given for solving the fundamental constraint equations in the general n-fold flow case. Then for the double-flow case, an algorithm is derived by computing two sets of flow parameters in closed-form equations from the time-varying image Gabor expansion. Next, margin energy is defined as the index for representing how well the optimization problem is posed for each degree of multiplicity ("well-posedness"), and a criterion is obtained to determine the number of flow vectors at each image point. Finally, the effectiveness of the algorithm is verified for synthesized images containing motion transparency and motion boundaries. This papers proposes fundamental constraint equations for multiple optical flow as the basic equations for extending the various conventional motion vision models and time-varying image analysis algorithms so that they can handle multiple motion transparency, and motion boundaries. [ABSTRACT FROM AUTHOR]

Various optimization methods are considered in image processing and pattern recognition. These methods have hitherto been considered independently; the purpose of this study is to systematize them, despite their difficult natures, and to indicate clearly what features they have in common and where they diverge. As a first step toward this goal, this paper proposes a method called the "extended relaxation matching method," which is an extension of ordinary relaxation matching. It is shown that dynamic-programming (DP) matching can be treated as a special case of the extended method. The DP matching method is transformed in this paper into an equivalent form called product-type DP matching. The relationship between the extended relaxation matching and the DP matching is discussed on the basis of this equivalent form. It is shown that DP matching constitutes a special case of the extended relaxation matching method. As a consequence, the recurrence formula that is the core of processing by DP matching corresponds to the procedures used in all algorithms extended relaxation matching. [ABSTRACT FROM AUTHOR]

This paper proposes a new join processing algorithm for the KD-tree indexed relations. The processing is evaluated by a simulation and the effectiveness is demonstrated. The KD-tree index is one of the typical multidimensional clustering data structures. A flexible database can be constructed which provides uniform access characteristics in regard to the multiple attributes. On the other hand, the data structure is made complex, and the traditional join processing technique for the ordinary one-dimensional clustering relation, which maintains the physical order, cannot be applied. Also, there has not been proposed a join technique for the KD-tree indexed relations. This paper introduces anew the concepts called "wave" and "join range," and proposes an efficient join algorithm for the KD-tree indexed relations. Then an extended algorithm is proposed by introducing the garbage collection function into the forementioned basic algorithm, where the unnecessary tuples on the main memory can be eliminated dynamically. Each of those algorithms is evaluated by a simulation, and the effectiveness is verified. When the order of the join attribute is not preserved, the join processing by the hash-based algorithm, which at present is considered the fastest, requires two read scannings and one write scanning, while the best algorithm proposed in this paper can execute the processing by almost one read scanning. Thus, a drastic improvement of the performance can be expected for the join processing by the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a new method in which the speech recognition processing is executed framewise on the time axis by local parallel operations using the Markov random fields (MRF). There have not been many studies presented concerning the parallel execution of the speech processing. On the hand, it is anticipated that parallel processing algorithms for the recognition process proposed in this paper will be very useful in high-performance continuous speech recognition systems, for example, where a strong computational power is required. The essence of parallel execution is to estimate the optimal state sequence by a parallel process based on the iterated conditional modes (ICM) for the given model parameters and the sequence of observed values. The local probability for the state sequence is indispensable for this purpose. It is shown that the local probability can be derived by representing the generation probability of the state sequence in a HMM (hidden Markov model) as a Gibbs distribution and calculating its conditional distribution. The foregoing property implies that the one-sided Markov chain used in HMM can be converted into a two-sided Markov chain in the one-dimensional MRF. Through the speaker-independent digit speech recognition experiment, it is shown that the proposed parallel processing algorithm has recognition performance comparable to that of the Viterbi algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we examine the restoration of degraded images using an iterative method. The following two problems arise in conventional iterative image restoration methods. The first is that most restoration methods are derived on the assumption that the noise is Gaussian. Restoration methods that assume Poisson noise, which is important in applications to resonance and microscopy images, have been previously discussed. The second problem is that the parameters that represent the stochastic model of the image are generally assumed to be known beforehand. But in actual image restoration, the parameters of that image model must be estimated from a degraded image. In this paper, we solve these problems by means of a new image restoration method, which is based on the following idea. Additive noise is assumed to be uncorrelated in both Gaussian and Poisson noise cases. The parameters of the image model are determined by means of the maximum-likelihood (ML) estimation from the degraded image, and image restoration is achieved by the maximum a posteriori (MAP) estimation. In order to link these two estimation problems and treat them as one continuous estimation problem, an evaluation criterion, called MAP-ML estimation, is introduced Then, in order to construct a restoration method that gives the optimum MAP-ML estimate, we derive a generalized expectation-maximization (GEM) algorithm, which is an extension of the expectation-maximization (EM) algorithm for calculating maximum likelihood estimate. [ABSTRACT FROM AUTHOR]

It has been shown that the Hough transform is effective in extracting straight lines and circles from an engineering drawing. However, this requires a 3-D parameter space and considerable computation time. It also requires repeated scanning to extract both the straight lines and circles by using separate algorithms. To overcome these difficulties, this paper proposes a new method which requires no space for accumulators and both the straight lines and circular arcs are extracted by using a single scanning and transform with the same algorithm. In this method, the straight lines and circular arcs on an x-y plane are extracted by transforming them into straight lines on a u-v complex plane and by detecting them. This paper describes the proposed algorithm and some applications of the method to architecture drawings. This method can be applied to drawings which contain no region where the same color is painted. [ABSTRACT FROM AUTHOR]

Kohomen's model as the self-organizing model for the neural network can be considered as a kind of adaptive vector quantization algorithm. Numerous reports have been presented on the application of the model to practical problems. Although some results have been presented for the theoretical properties of Kohonen's model, many properties remain to be clarified. Among various properties of Kohonen's model as an adaptive vector quantization algorithm, this paper considers the problem of how the reference vectors are placed according to the probability distribution of the input signal. Considering the limit where the number of reference vectors is increased to infinity, this problem can be discussed theoretically as the distribution of the reference vectors. Due to the effect of the "learning by neighborhood," which is the feature of Kohonen's model, the property of the Kohonen model differs quantitatively from the property of the ordinary vector quantization algorithm. This paper discusses quantitatively the properties of Kohonen's model using the average learning equation. [ABSTRACT FROM AUTHOR]

This paper considers a lattice represented by integer coordinates in n-dimensional space (digital lattice). On the digital lattice, and automorphism is constructed by a newly proposed theory and algorithm, to enable the approximation of the arbitrarily given equivolume affine transformation. The equivolume affine transformation is a general affine transformation that satisfies the condition of volume invariance, and is characterized by the determinant of the representation matrix having an absolute value of 1. An equivolume affine transformation of reflection, rotation, equivolume expansion/contraction and skew deformation. These transformations often are employed as fundamental transformations in the handling of geometrical information in computers. This paper discusses first the geometrical characters of equivolume affine transformations. It then defines the fundamental reflection, skew and translations. It is shown that the equivolume affine transformations in n-dimensional space can be decomposed into the produce of (n²-1) fundamental skew transformations, n fundamental translations and a finite number of fundamental reflections. For the fundamental transformations, one-to-one integer approximation is defined, and a systematic method is proposed to evaluate the upper bound of the approximation error. With the proposed error estimation method, an algorithm is proposed to determine the decomposition suppressing the error in the overall system. One advantage of this theory is that it is no longer necessary to preserve the geometrical information before transformation in the computer, which has been commonplace up to now in computer programming. [ABSTRACT FROM AUTHOR]