This paper presents a linear time algorithm for testing whether or not there is a path <v₁,・・・,v_m> of an undiercted tree T (|V(T)|n) that coincides with a string ss₁・・・s_m (i.e., label(v₁)・・・label(v_m)s₁・・・s_m). Since any path of the tree is allowed, linear time substring matching algorithms can not be directly applied and a new method is developed. In the algorithm, O(n/m) vertices are selected from V(T) such that any path pf length more than m 2 must contain at least one of the selected vertices. A search is performed using the selected vertices as 'bases' and two tables of size O(m) are constructed for each of the selected vertices. A suffix tree, which is a well-known-data structure in string matching, is used effectively in the algorithm. From each of the selected vertices, a search is performed with traversing the suffix tree associated with s. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to O(n log m).

In a distributed-memory parallel-processing system, the overhead of data transfer among the processors is so large that it is important to reduce the data transfer. We consider the data transfer in evaluating an expression consisting of data distributed among the processors. We propose some algorithms which assign the operators in the expression to the processors so as to minimize the number or the cost of data transfers, on the condition that the data allocation to the processors is given. The basic algorithm is given at first, followed by some variations.

As a generalization of the concept of pseudo-biorthogonal bases (PBOB), we already presented in Ref. [3] the theory of the so-called extended pseudo-biorthogonal bases (EPBOB). We introduce in this paper two special types of EPBOB called EPBOB's of type O and of type L. This paper discusses characterizations, construction methods, inherent properties, and mutual relations of these types of EPBOB.

A method of range image segmentation using four Markov random field(MRF)s is described in this paper. MRFs are used in depth smoothing, gradient smoothing, edge detection and surface type labeling stage. First, range and its gradient images are smoothed preserving jump and roof edges respectively using line process concept one after another. Then jump and roof edges are extracted, combined and refined using penalizing undesirable edge patterns. Finally, curvatures are computed and the surface types are labeled according to the signs of principal curvatures. The surface type labels are refined using winner-takes-all layers in the stage. The final output is a set of regions with its exact surface type. The energy function is used in order to represent constraints of each stage and the minimum energy state is found using iterative method. Several experimental results show the generality of our approach and the execution speed of the proposed method is faster than that of a typical region merging method. This promises practical applications of our method.

The Minimum Covering Run (MCR) expression used for representing binary images has been proposed [1]-[3]. The MCR expression is an adaptation from horizontal and vertical run expression. In the expression, some horizontal and vertical runs are used together for representing binary images in which total number of them is minimized. It was shown that, sets of horizontal and vertical runs representing any binary image could be viewed as partite sets of a bipartite graph, then the MCR expression of binary images was found analogously by constructing a maximum matching as well as a minimum covering in the corresponding graph. In the original algorithm, the most efficient algorithm, proposed by Hopcroft, solving the graph-theoretical problems mentioned above, associated with the Rectangular Segment Analysis (RSA) was used for finding the MCR expression. However, the original algorithm still suffers from a long processing time. In this paper, we propose two new efficient MCR algorithms that are beneficial to a practical implementation. The new algorithms are composed of two main procedures; i.e., Partial Segment Analysis (PSA) and construction of a maximum matching. It is shown in this paper that the first procedure which is directly an improvement to the RSA, appoints well a lot of representative runs of the MCR expression in regions of text and line drawing. Due to the PSA, the new algorithms reduce the number of runs used in the technique of solving the matching problem in corresponding graphs so that satisfactory processing time can be obtained. To clarify the validity of new algorithms proposed in this paper, the experimental results show the comparative performance of the original and new algorithms in terms of processing time.

A C¹ interpolation scheme for constructing surface patch on n-sided region (n5, 6) is presented. The constructed surface patch matches the given boundary curves and cross-boundary slopes on the sides of the n-sided region (n5, 6). This scheme has relatively simple construction, and offers one degree of freedom for adjusting interior shape of the constructed interpolation surface. The polynomial precision set of the scheme includes all the polynomials of degree three or less. The experiments for comparing the proposed scheme with two schemes proposed by Gregory and Varady respectively and also shown.

Although the perception of gloss is based on human visual perception, some methods for extracting glossiness, in contrast to human ability, have been proposed involving curved surfaces. Glossiness defined in these methods, however, does not correspond with psychological glossiness perceived by the human eye over the wide range from relatively low gloss to high gloss. In addition, the obtained glossiness in these methods changes remarkably when the curvature radius of the high-gloss object becomes larger than 10mm. In reality, psychological glossiness does not change. These methods, furthermore, are available only for spherical objects. A new method for extracting glossiness is proposed in this study. For the new definition of glossiness, a spatial filter which simulates human retina function is utilized. The light intensity distribution of the curved object is convoluted with the spatial filter. The maximum value H_max of the convoluted distribution has a high correlation with psychological glossiness G_ph. From the relationship between G_ph and H_max, new glossiness G_f is defined. The gloss-extraction equipment consists of a light source, TV camera, an image processor and a personal computer. Cylinders with the curvature radii of 3-30 mm are used as the specimens in addition to spherical balls. In all specimens, a strong correlation, with a correlation coefficient of more than 0.97, has been observed between G_f and G_ph over a wide range. New glossiness G_f conforms to G_ph even if the curvature radius in more than 10 mm. Based on these findings, it is found that this method for extracting glossiness is useful for the extraction of glossiness of spherical and cylindrical objects over a wide range from relatively low gloss to high gloss.

This paper describes a color segmentation method which is essential for automatic diagnosis of stained images. This method is applicable to the variance of input images using a three-layered neural network model. In this network, a back-propagation algorithm was used for learning, and the training data sets of RGB values were selected between the dark and bright images of normal mammary glands. Features of both normal mammary glands and breast cancer tissues stained with hematoxylin-eosin (HE) staining were segmented into three colors. Segmented results indicate that this network model can successfully extract features at various brightness levels and magnifications as long as HE staining is used. Thus, this color segmentation method can accommodate change in brightness levels as well as hue values of input images. Moreover, this method is effective to the variance of scaling and rotation of extracting targets.

This paper investigates the properties of synchronized alternating one-way multicounter machines (lsamcm's) which operate in real time (lsamcm-real's) and whose leaf-sizes are bounded by a constant or some function of the length of an input. Leaf-size reflects the number of processors which run in parallel in scanning a given input. We first consider the hieracrchies of lsamcm-real's based on the number of counters and constant leaf-sizes. We next show that lsamcm-real's are less powerful than lsamcm's which operate in linear time when the leaf-sizes of these machines are bounded by a function L(n) such that lim_n[L(n) log n/n]0 and L(n)2.

The main problem in statistical pattern recognition is to design a classifier. Many researchers point out that a finite number of training samples causes the practical difficulties and constraints in designing a classifier. However, very little is known about the performance of a classifier in small training sample size situations. In this paper, we compare the classification performance of the well-known classifiers (k-NN, Parzen, Fisher's linear, Quadratic, Modified quadratic, Euclidean distance classifiers) when the number of training samples is small.