摘要:

AbstractThe measurement of three‐dimensional objects has been conducted by various methods such as by projection of a slit light pattern. One problem in previous methods is the time‐consuming procedure of inputting the image. In order to solve the time problem in image input this paper proposes a method which provides stereotaxic vision with two cameras by projecting a relatively complex pattern light on the object, revealing the three‐dimensional information of the object. The measurement method proposed in this paper has the advantage that correspondence between images can be made by repeating the same procedure, based on a virtual projection line called the epipolar line, without using heuristic information. Utilizing the projected pattern and two input images, unique correspondence can be established for a fairly complex projection pattern. Experiments are performed by projecting a slit pattern or a grid pattern and it is found that false correspondence is rarely generated by the grid pattern and a large number of points can be ma

ISSN:0882-1666    

DOI:10.1002/scj.4690170601

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractAn important problem in the design of a VLSI chip is that of determining how much area is taken to embed a graph G into a planar grid when the VLSI chip is modeled using a graph called a planar grid and a circuit is expressed by a graph G representing wiring connections between elements. Discussed for various graphs will be the upper and lower bounds on the planar grid area into which a graph is embedded. In this paper we consider the problem of embedding ad‐way shuffle graph into a planar grid, using a model which has been extended so that a graph with degree five or more can be embedded.d‐way shuffle graphs are also of theoretical interest since data exchange can be done in high speed like a shuffle exchange graph and a CCC. By using a relationship between the number of crossings of a graph and its area, we show that for the infinite number ofdandkan area proportional todk+1/k)2is required to embed adk‐vertex,d‐way shuffle graph. Using this result, the previous lower bound of the area can be improved. Further, for an embedding of a graph G we present an embedding method of G which uses a graph with a known embedding area. By using this result we show that ifdis a power of 2, adk‐vertex,d‐way shuffle graph can be embedded in an area proportional t

ISSN:0882-1666    

DOI:10.1002/scj.4690170602

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThe self‐testing method using a multiple‐input signature register (MISR) has been proposed as a means of testing logic LSI. This paper analyzes the error‐detecting ability when the MISR is used as a pattern compression circuit. Coding theory technique is applied in the analysis. As the first step, assuming that a Hamming code generating polynomial (primitive polynomial) is used as the polynomial in MISR, the error‐detection rates are determined theoretically for single through quadruple errors. Then the error‐detecting rates for single through quadruple errors are calculated for the modified Hamming code generating polynomial. It is indicated as a result that the multiple error‐detection rate, especially the rate for the double error, does not reach 100%. In order to improve the multiple error‐detection rate, a reversely dual MISR is proposed in which a pair of MISRs is used with opposite shift directions. When the Hamming code generating polynomial is employed as the polynomial in the reversely dual MISR, it is shown that single and double errors are always detected. The rate of triple error detection is calculated. It is also shown that if the modified Hamming code generating polynominal is used, all single, double and triple errors

ISSN:0882-1666    

DOI:10.1002/scj.4690170603

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThis paper discusses noise elimination and restoration of the ridge structure of fingerprints in preprocessing for automatic fingerprint identification. The basic idea is as follows. The object image is partitioned into 64 × 64 unit regions with 8 pixels as edge. After estimating the locations of the ridges and valleys the restoration is performed by gray‐scale correction with different weights for each location. The processing is roughly divided as follows: (1) separation of background; (2) detection of ridge direction (quantized in 8 directions); (3) detection of ridge and valley locations; and (4) correction of gray‐scale value. Processing (2) greatly affects the later accuracy of detection and correction and requires high accuracy. In this paper the direction of the ridges is estimated hierarchically both from the local and global views and then is corrected by applying stochastic relaxation. As a result of experiment for 28 fingers (75903 unit regions) 99.00% of the estimates were within direction error of 0 and ±1. Considering that true correspondence of feature points was achieved for more than 73% between the later processed result and the original image, the above value is quite satisfactory for identification, verifying the usefulness of the proposed m

ISSN:0882-1666    

DOI:10.1002/scj.4690170604

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractTree‐type protocols achieve stable throughput even under heavy channel traffic compared with random access protocols such as the ALOHA types which show bistable behavior. Various binary tree‐type protocols have been studied extensively for channel stability and the improvement of throughput performance. In this paper, closed‐form solutions of the collision resolution time of severald‐ary tree type protocols are obtained, and the effect of the degree value of their protocols on the throughput performance is discussed. Asd‐ary tree‐type protocols, we consider the tree protocol, improved tree protocol, adaptive tree protocol and tree protocol with control mini‐slot, and compare their performance. Further, by comparing the stability of the binary tree protocol with that of three ALOHA schemes with different backoff algorithms, we show that the binary tree protocol exhibits very stable behavior even for a heavy

ISSN:0882-1666    

DOI:10.1002/scj.4690170605

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractAs the social missions of computer systems increase, it becomes more important to develop high‐reliability software. For this reason software systems are tested repeatedly to remove latent errors in the testing phase during software development. One of the most interesting methods is to evaluate software reliability by using test data observed in the error‐detection process. In this paper we model the error‐detection process as a stochastic model and introduce several effective measures to evaluate software reliability. In modeling we use the number of test run trials as a unit of the error‐detection period and assume that the cumulative number of software errors detected in an arbitrary testing time interval is a nonhomogeneous Poisson process. Further, we consider the difficulty of error detection because the reliability of software is evaluated from the characteristics and frequency of the errors. Applying the model to the actual test data, we perform the goodness‐of‐fit test and infer the software reliability measures. Finally, we discuss an optimum software release problem based on the software reliab

ISSN:0882-1666    

DOI:10.1002/scj.4690170606

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThe relational database machine GRACE can execute heavy relational operations such as joins quite efficiently, thereby resolving the bottleneck in the relational database processing. A new bottleneck, however, is expected to appear at accesses to the secondary storage system. We can also eliminate this new bottleneck by partitioning the database into multidimensional cells adaptively to the access pattern to data. As a result, the average number of page accesses is reduced. We developed an adaptive multidimensional clustering technique called the generalized KD‐tree method. The method is fully adaptive to the access pattern to data and the distribution of tuples. It was shown that the generalized KD‐tree method can reduce the average number of page accesses considerably, even in comparison with other multidimensional clustering algorit

ISSN:0882-1666    

DOI:10.1002/scj.4690170607

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractIn the VLSI circuit, the area occupied by the circuit and the time required for computation are important measures of evaluation. Thompson, Brent and Kung have proposed a VLSI model to evaluate the VLSI circuit by the areaAand the computation timeT.It is an important problem to examine the change of the area and the computation time when a certain practical assumption is imposed on the VLSI model. This paper shows that when an assumption that the input and the output are connected at the boundary of the circuit (called boundary‐layout assumption) is imposed on the VLSI model, relationsAT= ω(max(n, m)) andATa= ω(max(n, m)[max(logN, logM)]a) (α>1) are produced for the nontrivial class ofn‐input,m‐output logic functions. Above,Nis the maximum ofN1, …,Nm, whereNiis the number of inputs on which theith output depends, andMjis the maximum ofM1, …,Mn, whereMjis the number of outputs which depends on thejth input. When the boundary‐layout assumption is not imposed,ATα = ω(max(n, m){max(logN, logM)}α‐1) (α ≥ 1) holds. Consequently, for this class of functions, the boundary‐layout assumption properly affectsATα (α ≥ 1). It is shown also by an actual example that there exist functions wh

ISSN:0882-1666    

DOI:10.1002/scj.4690170608

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractThis paper describes a design method of high‐speed digital signal processing systems suitable for LSI fabrication. It utilizes the pulse‐train residue arithmetic circuit as a basic building block. This circuit lends itself to parallel and pipeline operations suitable f o r high‐speed digital signal processing, and permits modular‐design of the systems. A new master‐slice LSI on which the pulse‐train residue arithmetic circuits are arranged regularly, is presented. A method of minimizing the chip‐area for NMOS fabrication of the master‐slice is discussed. The layout of the pulse train residue arithmetic circuits on the LSI chip, and several parameters of the master‐slice such as the number of channels are discussed. Some demonstrative examples are presented to show the application of the master‐slice in the design of digital filter. The design method using master‐slices is relatively simple; it minimizes the chip‐count and improv

ISSN:0882-1666    

DOI:10.1002/scj.4690170609

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY

摘要:

AbstractIn image pattern understanding, global and unspecific processing are required. Thus it is important to develop an asynchronous processing algorithm with high efficiency and MIMD type. This paper formulates and analyzes the determinacy problem on the newly introduced transformation model, as a basic theory for the asynchronous parallel processing algorithm for the pattern information processing. The major results are as follows: (i) a transformation model is introduced which can describe and analyze the mathematically parallel processing algorithm, into the content of the processing; (ii) the determinacy problem is formulated, arriving at a convergence theorem representing a sufficient condition; (iii) a discussion is made from the viewpoint of the determinacy problem on the possibility of asynchronous parallel processing of the relaxation method, which is already applied to the image processing. It is concluded that the asynchronous parallel processing is possible in the discrete and fuzzy relaxations, but is impossible in the linear and nonlinear stochastic relaxations.

ISSN:0882-1666    

DOI:10.1002/scj.4690170610

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1986

数据来源: WILEY