bluuebunny/crossref_metadata_2025 huggingface dataset:
Adaptive Character Segmentation Method Based on Minimum Variance Criterion
Authors: Tsuji Yositake , Asai Ko
Published: July 2007

Character segmentation is a technique which separates individual characters from character line image. It is one of the most important prerequisites for character recognition. In the past, segmentation of individual characters from a general object, such as mailing address and existing document, had strong constraints imposed on the character segmentation. These included contact between adjacent characters and separation of a single character, thereby preventing the segmentation technique from being a systematic approach. This paper discusses character segmentation, an indispensable means of pre‐processing in character recognition which has been considered to cope with the individual cases. A character segmentation method is proposed which is based on the clustering for the character cluster interval histogram by linear square‐error function, and on the dynamic programming using the minimum variance criterion for separation between character sectioning candidate positions in a line image. The first method is applied to the estimation of the character pitch, i.e., estimating the statistically best character pitch. It also extracts the parameters representing the placement properties for a series of characters. The second method is used to determine in a stable way a series of character sectioning positions. In the experiment, the method is applied to English language mail addresses, containing fixed and unspecified character pitches as well as contact between adjacent characters. A 99.2% correct segmentation rate was obtained for characters and 98.0% was obtained for words, indicating the effectiveness of the method.
Relationships of accepting powers between cellular space with bounded number of state‐changes and other automata
Authors: Ito Akira , Inoue Katsushi , Takanami Itsuo , Taniguchi Hiroshi
Published: July 2007

Previously, we proposed the state‐change‐bounded rectangular‐array cellular‐space acceptor, which is a rectangular‐array cellular‐space acceptor with cells of bounded state‐changes. At that time, we also discussed its basic properties. The major purpose of this paper is to describe the relations among the accepting power of the state‐change‐bounded rectangular‐array cellular‐space acceptor with square pattern as the input and those of other various kinds of two‐dimensional automata. It is shown, for example, that the deterministic rectangular‐array cellular‐space acceptor with the state‐change bounded by a constant, can be simulated by the two‐dimensional alternating finite automaton. At the end of this paper, a family of sets of square tapes which are accepted by the state‐change‐bounded rectangular‐array cellular‐space acceptor, is considered. Also, the closure properties of the operations, such as union, intersection, and projection, are discussed.
Improvement of efficiency of captioning video pictures for the deaf by use of a japanese word processor
Authors: Nishikawa Satoshi , Takahashi Hidechika , Kobayashi Masayuki
Published: July 2007

Video pictures and voice information play an important role in the present‐day social life. Captioned video tapes are one of the most important sources of information for hearing‐impaired people. In Japan, however, the usual method of captioning uses telop cards because of the complexity of the Japanese language. Moreover, this method requires considerable time and money. We developed a video information processor that superimposes the printout of a Japanese word processor on the images of video devices. As a result, anyone (not necessarily a professional operator) can make captioned video tapes easier, faster, and cheaper than by the usual method. In particular, the captioning process speeds up the usual method by about ten times. This enables captioning on video pictures faithful to speech and hence is effective for enriching information in video pictures.
Recognition of human kidney ultrasonic organ images by two‐dimensional dp matching method
Authors: Yamada Hiromitsu , Yamamoto Kazuhiko , Matsuura Masahiko
Published: July 2007

This paper discusses the application of two‐dimensional dynamic programming (DP) matching to ultrasonic kidney images. By introducing the model‐matching technique, feature extraction of the object organ is achieved. It is also possible to reconstruct the three‐dimensional structure of the organ. The proposed technique has the following features. (1) Unlike the monotone continuous condition employed in speech recognition, the two‐dimensional DP method has no time‐sequence constraints. (2) The recognition performance is improved by utilizing the edge information. (3) Hierarchical construction of DP from coarse to fine grids improves the processing speed. (4) The method allows man‐machine interaction by fixing a point on the contour of the object. (5) The method can be applied to time‐series and/or three‐dimensional consecutive images and the speed is improved by using the object from the previous image.
An efficient algorithm for the dot generation of arbitrary ellipses
Authors: Koda Goro , Shimizu Kensuke
Published: July 2007

This paper presents an algorithm which provides a high‐speed dot representation of an ellipse on the raster‐scan graphic display device. In the usual graphic display, straight‐lines and circles are used as the graphic primitives. In the three‐dimensional graphics, a projection on the two‐dimensional plane is often employed where a circle is in general projected as an ellipse. When a curve with rapidly varying curvature is to be represented, the approximation can be effected by a fewer number of components if ellipses are used instead of circles. From such viewpoints, an efficient generation algorithm for the ellipse is required. The ellipse considered in this paper need not have the long or short axis parallel to the coordinate axis. The lengths of the long and the short axis are arbitrary, and the correct dot generation is observed for an extremely oblong ellipse. The location of each dot is determined so that the deviation from the ellipse is small. Sometimes the past method does not work due to the fact that the ellipse is a two‐valued function. By contrast, this paper contains a simple scheme to convert the ellipse into a single‐valued function. To improve the speed of the algorithm, only addition‐subtraction and conditional test are used in the internal loop determining the dot location.
Relationship between the accepting powers of (k, l)‐neighborhood template δ‐type one‐dimensional bounded cellular acceptors and other types of two‐dimensional automata
Authors: Taniguchi Hiroshi , Inoue Katsushi , Takanami Itsuo , Seki Shigeko
Published: July 2007

Previously, we proposed a (k, l)‐neighborhood template δ‐type bounded cellular acceptor (abbreviated as δ‐‐BCA (k, l)), which is composed of a pair of converters and a configuration‐reader and operates on a two‐dimensional tape. Its basic properties have already been discussed. δ‐BCA (k, l) is a parallel automaton, which, in a sense, is a generalization of the one‐dimensional bounded cellular acceptor. This paper attempts a more detailed examination of the properties of δ‐BCA (k, l), and compares its accepting power with those of other automata operating on the two‐dimensional tape. The objects of comparison are the various kinds of two‐dimensional finite automata and various kinds of parallel sequential array acceptors. It is known that there exists an equivalent tape‐bounded Turing machine for each of these automata in the sense of the accepting power. Consequently, the comparison of the accepting power of δ‐BCA (k, l) and those of two‐dimensional automata amounts in a sense to the evaluation of the accepting power of δ‐BCA (k, l) in terms of the tape complexity of the tape‐bounded Turing machine.
The emptiness problem for indexed language is exponential‐time complete
Authors: Tanaka Shinichi , Kasai Takumi
Published: July 2007

The class of indexed languages properly includes the class of context‐free languages and is properly included in the class of context‐dependent languages [1]. The emptiness problem (the problem of determining whether or not the given language is empty) is polynomial‐time complete for the class of context‐free languages and is undecidable for the class of context‐dependent languages. The recognition problem (the problem, given a language L and word w, of determining whether or not w belongs to L) is polynomial‐time complete for the class of context‐free languages and is polynomialspace complete for the class of contextdependent languages. This paper shows that both the emptiness and recognition problems are exponential‐time complete for the class of indexed languages. It is known in the pebble game [2] that the problem of determining whether or not the first player has the winning strategy is exponential‐time complete. This paper reduces the problem to the emptiness problem for the class of indexed languages in the logarithmic space, indicating the exponential‐time difficulty of the emptiness problem for the indexed language. Since Aho has shown that the problem can be answered in exponential time, the exponential‐time completeness is shown. The exponential‐time difficulty is also directly indicated from the fact that the emptiness problem is exponential‐time complete. Consequently, the recognition problem is also exponential‐time complete.
A distributed algorithm for maximum flow on processor‐arrays
Authors: Onaga Kenji , Marumoto Satoshi
Published: July 2007

This paper considers the maximum flow computation of a network N = (V, E, C), and presents a design of its hardware algorithm which executes the computation in a distributed and MIMD way by a processor array of the same structure as N. The node of N corresponds to a node processor and the edge to a communication link carrying the computational information. The computation of the flow is performed on the flow table FTABLE established on each node. Each node processor performs distributed and MIMD instructions indicated by tokens which are generated in particular nodes (host, input and output nodes) modified and transferred through adjacent nodes. The proposed algorithm can be readily utilized in hardware simulation of traffic and communication networks.
A design of real‐time systolic convolvers
Authors: Umeo Hiroshi
Published: July 2007

This paper discusses the systolic algorithm where the input and output are serial and the processing is performed in parallel (called serial‐I/0, 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 time. 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‐time systolic convolution algorithm.
Longitudinal ECT imaging using Y‐ray camera
Authors: Iwata Satoshi , Nakajima Masato , Yuta Shinichi , Ogawa Koichi
Published: July 2007

Single‐photon emission CT is one of the most useful techniques in nuclear medicine, wherein a radioisotope material is injected into the body and by external detection of the radiated y‐ray the RI distribution on an arbitrary layer (slice) is reconstructed from the data, permitting visual representation of physiological information. Longitudinal imaging is one of such techniques. The object is regarded as composed of layered RI distributions. From the y‐ray projection data obtained by y‐ray detectors placed parallel to the layer, the RI distribution at each slice is reconstructed. In longitudinal imaging, however, the projection data are observed only along a particular direction and the working range of the detector is restricted, leading to blur and degradation of the reconstructed image. This paper discusses the quality degradation inherent in longitudinal imaging and proposes a reconstruction algorithm which employs the contour information of the object in the reconstruction computation to make correction for the quality. The result of numerical simulation is also reported.
Distance transformation and reconstructable skeleton of three‐dimensional digital binary images
Authors: Sun Wei‐Dong , Tayama Norio , Otawara Isao
Published: July 2007

This paper considers the filled three‐dimensional image, such as the one obtained by superposing several CT images, and discusses the distance transformation and the skeleton for the three‐dimensional filled object. From the viewpoint that the internal structure of the three‐dimensional object should easily be understood, there has been devised a distance transformation, where the distances from all points inside of the three‐dimensional object to the surface are determined. There has not been presented, however, a method which is applicable to the general situation. From such a viewpoint, this paper introduces a new notion of fundamental neighbor set, and proposes a general parallel and serial algorithms for the distance transformation. As an example, the notion of the reconstruetable skeleton for the three‐dimensional object is proposed, and the parallel and serial algorithms are presented, which can reconstruct accurately the original three‐dimensional object from the skeleton. The reconstructable skeleton will be useful as a means of information compression for the three‐dimensional image, which requires especially a large amount of data for the representation. The validity of the proposed algorithms is verified by computer simulation.
Software testing system supported by a computer architecture
Authors: Baba Takanobu , Suzuki Shinzi , Yamazaki Katsuhiro , Okuda Kenzo , Sano Toshiyuki
Published: July 2007

Based on the development of hardware, various computer architectures have been proposed to support software. However, most of them have not been implemented and evaluated. We have realized a software testing system on a machine developed at our laboratory. Utilizing its architectural features, we proved the effect experimentally. The supporting functions include the following: display of memory contents according to the data type, step‐run in the units of statement and procedure, specification of type and range of variables, checking of assign/refer relationship, and measurement of execution frequencies. The user can specify these functions explicitly by interactively using various commands. A tagged architecture and data descriptor have been utilized to implement the functions efficiently. Experimental results show that 86 percent of program errors were detected by the supporting functions, and the overhead was less than 2 percent of the total execution time.
Hardware algorithms for computing exponentials and logarithms using redundant binary representation
Authors: Takagi Naofumi , Yajima Shuzo
Published: July 2007

In this paper, we propose hardware algorithms for computing exponentials and logarithms utilizing the redundant binary representation for internal computation. The algorithms proposed in this paper are improved versions of modified STL methods which were improved by Specker and by Chen and are known as methods suited for the dedicated circuits for computing exponentials and logarithms. The algorithms by Specker and by Chen compute exponentials and logarithms by repeating a simple procedure composed of an additional subtraction, a shift and a table look‐up. In the proposed algorithms, by using the redundant binary representation, each digit at which is an element of {0, 1, ‐1} for the internal computation, we eliminate carry (borrow) propagation from addition (subtraction) and improve the speed of computation. Using the traditional methods, because of carry (borrow) propagation addition (subtraction), combinational circuits for computing n‐bit exponentials and logarithms require at least a computation time proportional to n log n and the number of elements proportional to n2. Using the proposed algorithms, the computation time is improved to be proportional to n, and the number of elements is proportional to n2 using traditional methods.
A tree‐structured parallel processing system for image generation by ray tracing
Authors: Deguchi Hiroshi , Shirakawa Isao , Omura Koichi , Nishida Masato , Nishimura Hitoshi , Kawata Toru
Published: July 2007

An image generation system by ray tracing was implemented on a distributed parallel processing system composed of loosely coupled multimicrocomputers. An improvement was made by extending the architecture from the star structure to the hierarchical tree structure. This improvement makes it possible for an animated image to be generated at high speed with shading which can represent the shape and texture of three‐dimensional objects with high quality. This paper outlines the hierarchical tree‐structured image generation system, discussing the parallel processing mechanisms of the system, such as data transfer and hierarchical load distribution schemes. Experiments were made to evaluate the performance. Problems in the tree‐structured system are pointed out, and remedies are proposed (area redistribution, and area subdivision). Experiments are made to evaluate the effectiveness of these methods. Thus, it is demonstrated that the tree‐structured system is useful in the image generation using ray tracing.
A fast image filtering processor using the fermat number transform
Authors: Yamane Nobumoto , Morikawa Yoshitaka , Hamada Hiroshi
Published: July 2007

This paper discusses a newly developed high‐speed image filtering processor, aiming at high‐accuracy and high‐speed isotropic filtering. The isotropic filtering is made efficient by the following features.

(1) The image is sampled over the triangular lattice and processed by the hexagonal finite‐impulse response (FIR) filter. (2) The filter is realized by the Fermat number transform (FNT) with hexagonal sectioning procedure.

The high‐speed hardware has the following features: (1) FNT‐butterfly circuit using 3‐input adders; and (2) multiple processing by the memory structure with three‐level hierarchies. By those features, the proposed system executes the filtering in approximately 0.5 s for an image composed of 512 × 512 pixels in triangular lattice (512 × 591 pixels in square lattice) by a hexagonal FIR filter with edge distance of 15 (17 × 17 in square lattice‐square FIR filter). This paper describes the features, architecture and operation of the proposed system. Then the result of correcting the isotropic blur is presented, indicating that a practically sufficient accuracy is obtained.
A module structure real‐time operating system for microcomputers
Authors: Tsuda Junji , Tsutsui Shigeyoshi , Maeda Takao , Yokohata Shizuo , Ishikawa Tomo
Published: July 2007

With the advent of large‐scale and complicated microcomputer application systems, the role of OS is becoming more important. An OS which can cope with various application requirements is strongly desired. This paper aims at the construction of OS which can be made optimum for various real‐time applications. A construction of real‐time modular structure OS using the microcomputer 68000 is proposed. The message‐passing and procedure‐call schemes are combined to connect the modules. A two‐layered hierarchy module structure is proposed, suppressing the increase of the overhead due to modular implementation, and also providing the flexibility for replacing modules. By this scheme, operating systems with capacity from 10 KB to 150 KB can be constructed, covering a wide range of applications from a small‐scale system with hardware built‐in structure to the relatively large‐scale system requiring programming functions, by simply modifying the combination of modules. To utilize commercial softwares or general‐purpose OS in the real‐time environment, a scheme is proposed in which the general‐purpose OS is executed as the secondary OS with the real‐time kernel. As a result of evaluation, when a general‐purpose OS, CP/M‐68K, is executed as the secondary OS, the processing time is increased by 12.7% compared with CP/M‐68K directly implemented on the 68000.
Description and verification of input constraints and input‐output specifications of logic circuits
Authors: Kimura Shinji , Yajima Shuzo
Published: July 2007

The input constraints and the input‐output specifications of the logic circuit are assertions to be satisfied in the operation of the logic circuit. Most of the timing constraints such as the set‐up time of the clocked flip‐flop can be regarded as the input constraint or the input‐output specification. In this paper, the time is considered as discrete with sufficiently small steps, and the input and output of the logic circuit are treated as sequences. The method to describe the set of sequences satisfying the input constraints or the input‐output specifications and the method to verify these assertions are proposed anew; # expression and the first # form are proposed as the description methods. The # expression is obtained by adding the newly proposed # concatenation and # closure to the regular expression. The first # form is a restricted # expression, where the number of states of the deterministic finite automaton accepting the set of sequences represented by the expression does not exceed twice the length of the description. In this paper, the logic circuit is regarded as a converter for the set of sequences and the verification of the input constraint or the input‐output specification is reduced to the examination of the inclusive relation among the sets of sequences. Consequently, when the set of sequences satisfying the input constraint or the input‐output specification is described in the first # form, the verification can be performed efficiently. The proposed method is applied to several actual problems, and is shown to be useful.
A character recognition system with learning dictionary for handwritten drawings
Authors: Ishii Mitsuo , Iwasaki Michiko , Yamada Masahiro
Published: July 2007

This paper discusses the character recognition system used in the automatic input of drawings. The character considered is of small size, 2 to 5 mm, which is sampled with a low resolution such as 5 lines/mm. The recognition is performed by a kind of pattern matching. The input pattern is superposed on the dictionary pattern. The distance distortion measure is introduced which represents the degree of mismatch with the closest pixels as the corresponding pair. To reflect the structural feature of the character, the weighted distortion measure is proposed which considers the environment of the corresponding pixels. By this elaboration, the misrecognition rate was decreased by 45 percent. To cope with the problem arising from representing the two‐dimensional pattern distortion by a single number, dictionary patterns are increased. The generation and the structure of the dictionary are discussed. A hierarchical dictionary with learning pointer is constructed which records the mistakes made in the course of training. The feature of the method is that mistakes made in the past can be utilized and the processing time does not increase so rapidly in proportion to the number of dictionary patterns. Approximately 30,000 characters were learned, and the practical recognition performance was verified through the recognition experiment for the drawings.
A concurrent pattern operation algorithm for VLSI mask data
Authors: Tsukizoe Akira , Kozawa Tokinori , Sakemi Jun'Ya , Miura Chihei , Ishii Tatsuki
Published: July 2007

With the advance of scale and integrity of LSIs, several kinds of CAD systems are being developed and introduced to design verification and mask pattern generation for mask pattern data as a means of shortening the design time. The processings common to these CAD systems are pattern logical operations. This paper proposes effective and fast pattern operation algorithms for large‐scale data containing patterns of any angle: the virtual slit method and limited searching algorithm. The virtual slit method is a logical operation algorithm performing concurrently the three processings, intersection‐point calculation, slit division, and logical processing which have been done independently in old algorithms. The limited searching algorithm is a highspeed intersection‐point calculation algorithm indispensable for diagonal figures. The time complexity of both methods is theoretically O(Nv) log Nv) where Nv is the number of input vectors. For manufactured LSI mask data, we obtained the result for the time complexity based on estimation by program execution which can be approximated by O(Nv).
Matching of distorted central symmetry image—An application to seal impression collation
Authors: Takeda Haruo , Tabata Kuniaki , Hananoi Toshihiro
Published: July 2007

This paper considers the pattern matching of images in which, originally, the boundary has central symmetry which is made incomplete by defects and noises. A detection method for the centroid of symmetry is proposed. In the proposed method, the boundary is rotated by 180° to match itself (self‐matching of the boundary), thereby detecting the centroid by utilizing all position information of the pixels on the boundary. When the defects are assumed, methods such as tracing cannot be applied directly to the extraction of the boundary, and a simple scheme is employed which scans the image in parallel to the coordinate axis. The effect of the spurious information produced by the scanning is eliminated by using the histogram as the measure of the boundary matching. The effect of the missing information is eliminated by superposing the histogram, which is obtained by scanning in the direction perpendicular to the original scanning, to the original histogram. The proposed method is applied to collation of seal impressions. It was verified that the positioning is performed within the error of one pixel for the ordinary defect of the impression frame and the partial defect of the frame due to the noise by background and fibrous padding material. It was also verified that a processing with practically sufficient speed can be realized. The proposed method will also be applied effectively to the positioning of the images with partial central symmetry, such as a circular component with a protrusion.
A method of document‐image segmentation based on projection profiles, stroke densities and circumscribed rectangles
Authors: Akiyama Teruo , Masuda Isao
Published: July 2007

A method is proposed wherein printed documents are segmented into the following three areas: headline area, textline area, and attached area. Then the character lines constituting headline and textline are extracted. This paper describes: 1) the combination of the global features of the document such as projection profiles and stroke densities, and the local features of the document such as circumscribed rectangles are used; 2) the basic features of document elements such as character line periodicity in the textline area, so that a single method can be applied to segment document elements in differently formatted documents.

An experimental result of this method applied to eight Japanese and English printed documents of both horizontal and vertical lines showed that 98.4 percent of the headlines in headline area, 99.9 percent of the textlines in textline area, and 83.3 percent of diagrams in the attached area were segmented successfully.

The result confirms that this method is effective in segmenting document elements, and applicable to a variety of documents. Part of document processing is implemented in the experiment by special hardware for speed.
Properties of personal identification systems using question‐answer technique
Authors: Masuyama Hiroshi
Published: July 2007

This paper considers various personal identification systems based on questions and answers concerning knowledge inherent to the individual, and discusses the personal identification probability. Assume a personal identification system which contains N knowledge items and assume that a solver has forgotten the correct answers for M items after the registration. The behavior of the system is as follows: Q knowledge items for questions are selected randomly from N items. For each of the selected items, R selection keys are presented which include a correct answer and the solver is requested to select one. When the solver forgets the correct answer, the probability of correct answer is 1/R; otherwise it is 1. The following three systems are considered under such conditions. System I decides the solver as correct if all answers to the extracted Q items are correct. System II decides the solver as correct if there are fewer than K incorrect answers. System III decides the solver as correct unless k or more consecutive answers are incorrect. It is seen that the probability of personal identification increases in the order of I, II and III. It is not always true that the probability of excluding an incorrect solver is low if the probability of personal identification is high. Each of the considered systems is suited to particular applications, depending on the environment.
Performance of a simulated dataflow computer DFNDR‐2
Authors: Sowa Masahiro , Kamimura Akitoshi
Published: July 2007

An architecture is proposed for the dataflow computer and an experimental system is constructed. However, since the emphasis has been on the realization of the computer, it has been difficult to estimate the general performance of the dataflow computer from the performance of the experimental system. This paper describes the result of simulation to estimate the general performance.
Principles of algebraic language ASL
Authors: Kasami Tadao , Taniguchi Kenichi , Sugiyama Yuji , Seki Hiroyuki
Published: July 2007

This paper discusses the problems and basic principles in the design of the algebraic language ASL/. A text of ASL/ is composed of a context‐free grammar and a set of (conditional, in general) axioms, and specifies the set of expressions and the congruence relation on the set. The set of expressions and the syntax of each expression are specified by the context‐free grammar. The congruence relation on the set of expressions is defined as the minimal equivalence relation, which satisfies the axioms and is closed under the “operations,” i. e., the substitution into a “subexpression.” The value of an expression and the concept of the realization are defined based on the congruence relation. The “projection” is a special case of the conditional axiom, which is a facility to include only the expressions satisfying the specified syntactical condition. Projection is useful for including primitive functions and procedures with parameter passing of call‐by‐value in a text, and also for description of a specification of a realization in a simple way.
Arithmetic burst error correcting fire‐type cyclic ST‐AN codes
Authors: Shimada Ryosaku , Murakami Ryutaro , Sono Kazuharu , Ohkura Yoshiteru
Published: July 2007

The cyclic ST‐AN code is a cyclic AN code based on a ternary number system using numerals ‐1, 0, 1 (called symmetrical ternary number system). It is suited to the arithmetic operations handling positive and negative numbers in a symmetrical way as well as to the error‐correction. We have already presented some reports on the basic concept of the code and the error‐correcting ability for the random error. This paper proposes the cyclic ST‐AN code which can correct the burst error. The code is generated by the code generator A = (3c ‐ 1) A2, and is an extension of the algebraic Fire code. Because of this property, it has the features that the construction is very simple and the selection of the code is easy. A satisfactory result is also obtained for the code efficiency. This paper describes first the outline of the cyclic ST‐AN code and the concepts of arithmetic burst. Then it discusses the construction of the cyclic ST‐AN Fire‐type code and its error‐correcting ability. Finally, the decoding method is presented which uses the error‐trapping.
A random‐pattern testable design for programmable logic arrays
Authors: Fujiwara Hideo
Published: July 2007

Although the built‐in self‐test approaches by pseudo‐random patterns using LFSR are common, it is difficult to expect high fault coverage for high fan‐in circuits such as PLA. Thus, for the built‐in test of circuits like PLA we need to generate regular test patterns or to devise some counterplan even in the use of random patterns. This paper proposes a method for constructing random‐pattern‐testable PLAs for which we can achieve high fault coverage even by random patterns by adding mask arrays to conventional PLAs. To see how high fault coverage is achieved, fault detection probability by random patterns is analyzed for equivalent AND‐OR circuits of the form‐like trees for both stuck‐ and cross‐point type faults. Also a method for finding a mask that maximizes the probability of fault detection in the composition of random‐testable PLAs is studied.
Realization of computers using programmable logic units
Authors: Yamada Hidekazu , Nakamura Tadao , Shigei Yoshiharu , Murayama Takahiko , Yoshioka Yoshio
Published: July 2007

A key to speeding up the processing is how to realize the programmable hardware using both a pipelined processing scheme and a multiprocessor processing scheme for such special hardware as the fast Fourier transform (FFT) unit and the digital filter. This paper proposes a structure for the programmable logic unit (PLU) based on such an idea, where the computing program is mapped on the hardware, and the processing is performed by write/read of the operand data. For the computer using the proposed PLU, three kinds of conceivable processing algorithms are presented. On the other hand, considering the number of pins, the regularity of the circuits, and the recent progress in three‐dimensional VLSI technology, it is highly conceivable that the proposed PLU is realized by VLSI. Thus, from the viewpoint of program execution in the computer using PLU, the program is constructed of the instructions computed by the PLU and the control instructions executed by the main CPU, and the processing mechanism is described using a program example. A discussion is made on the processing time, and it is shown that the computer using the PLU can utilize the parallelism of the computation by PLU to reduce the processing time, compared with the computer not using PLU. Thus, the effectiveness of the computer using PLU is demonstrated.
Performance evaluation of a computer using programmable logic units
Authors: Murayama Takahiko , Yamada Hidekazu , Nakamura Tadao , Shigei Yoshiharu , Yoshioka Yoshio
Published: July 2007

The programmable logic unit (PLU) has been proposed to realize a high‐speed operation. The idea is to perform computation obtained by a static data flow scheme using the stepwise arithmetic logics distributed in the memory. This paper describes the configuration of the prototype PLU, the basic concepts of the computation and the synchronization between the PLU and the main control unit (CU). Then theoretical discussions are made on the computation time for the arithmetic and the iterative programs. It is shown that the high‐speed processing is realized by the effects of the parallel computation and of the pipelined computation, mapping many templates of a loop program on the PLU. Furthermore, the multiprogramming for the computer with PLU is proposed to utilize effectively the waiting time for the computation in the PLU. The throughput improvement is indicated by theoertical analysis, comparing the computer using PLU with the traditional sequential computer. Finally, the usefulness of the PLU is demonstrated.
A method for extracting marked regions from document images
Authors: Hase Masahiko , Suzuki Gen , Itoh Hisayasu
Published: July 2007

A method of document management in the electronic filing is considered, where the abstract is prepared, filed and retrieved for each document. This paper discusses a method of preparing an abstract from the document image. A method is proposed in which the region marked by the user with a felt‐tip color‐pen, etc., is extracted automatically and filed. The features of the method are as follows: (1) in the extraction of the marked region from the marked document image, the difference of reflectivities between the background (white) and the marked region in the document is utilized; (2) to determine the position of the mark, the algorithm based on the peripheral distribution using the integration of pixels is employed from the viewpoint of speed and accuracy; (3) in the compression to extract only the marked region, a processing to replace n n pixels by a pixel is applied, from the viewpoint of hardware implementation and speed.
Definition of gazing point for picture analysis and its applications
Authors: Yamada Mitsuho , Fukuda Tadahiko
Published: July 2007

The authors have been analyzing images by eye movement. For this purpose, it is necessary to decompose the eye movement into a component to accept information from a gazed object and a component to shift the gazing point. The point considered in the foregoing is called the gazing point, which is defined in this paper based on the property of the pursuit eye movement. Eye movement velocity of 5 deg/s is used as the threshold to separate the two components. As a result, it is made possible to separate clearly the eye movement into the gazing point component and the shift between the gazing point. A vision analyzer based on this definition of the gazing point was developed, which can analyze comprehensively the eye movement in real‐time. As an example of the application of the vision analyzer, the difference of the eye movement in watching the VDT image and the usual dynamic picture is analyzed. Furthermore, as an application to the analysis of art, an experiment was made as a reference material for the analysis of Sharaku's ukiyo‐e painting. The results of experiments are described, indicating that the definition of the gazing point is adequate.
A class of ambiguous linear term‐rewriting systems on which call‐by‐need is a normalizing reduction strategy
Authors: Naoi Tohru , Yamashita Masafumi , Ibaraki Toshihide , Honda Namio
Published: July 2007

The term‐rewriting system is of a recent concern, since there can be various applications, including the execution mechanism for the programming language based on the equality. However, in its application there must be a normalizing reduction strategy, which ensures that the normal form can always be reached if the given term has a normal form. Huet and Lévy proposed the call‐by‐need strategy as a normalizing reduction strategy for unambiguous linear term‐rewriting systems. This paper extends their result to the case containing ambiguity. A sufficient condition is shown first for the call‐by‐need in a linear term‐rewriting system containing ambiguity to be a normalizing reduction strategy. The condition properly includes the result of Huet and Lévy. Then considering an arbitrary linear term‐rewriting system, in which the call‐by‐need is a normalizing reduction strategy, a condition is presented under which a new rewriting rule can be added, while retaining the properties. Combining the result with the previous result, a wider class of ambiguous term‐rewriting system is obtained in which the call‐by‐need is a normalizing reduction strategy.
A method of constructing large‐scale program processor for 8‐bit system utilizing memory mapping feature
Authors: Tsuji Tatsuo , Kontani Kazuto , Watanabe Katsumasa , Sumiya Mitsuaki
Published: July 2007

There is a technique which executes efficiently multitask processing utilizing the memory‐mapping function of the memory management LSI (MMU). The technique is now being established even at the level of the 8‐bit processor. However, there exists a limitation on the size of the process in the 8‐bit processor. If a mid‐sized program is written by a high‐level language, this limit often is exceeded by the program size including the data area. To the best of the author's knowledge, there has not been presented a language processing system containing MMU, which can handle a large‐scale program without considering the limit for the address space, as far as the physical memory permits. The mapping function of MMU has been considered aiming largely at the mutual protection of the processes in the multitask processing. To utilize this function for the foregoing situation, a study is needed for new scheme both at the OS level and at the language processing level. This paper considers language C which has a high modularity among procedures (functions), and newly proposes a large‐scale program processing system overcoming the limitation of the address space. A measurement is made on the implemented system, and it is shown that the increase of the production code and the decrease of the execution speed is within the permissible range, compared with the usual processing system.
A generalized condition for designing a measuring system of color images and its application
Authors: Tominaga Shoji
Published: July 2007

This paper derives a general condition for image sensors in the design of color image measuring systems. An application example to a drum scanner is presented. Heretofore, the measurement of color image has been restricted to the three‐sensor system for R, G and B. However, it is difficult, to realize a highly accurate color measurement using only three sensors, for such actual color input devices as a drum scanner. From such a viewpoint, this paper proposes an improvement of the color measuring performance by increasing the number of sensors. First, a theoretical analysis is presented for the color measuring system using the vector analysis technique, and the basic conditions for the image sensor are derived. The discussion starts from the formulation of the basic property of the color‐matching in the visual system. The problem is formulated by requesting that the measuring system should realize the equivalent characteristics. This viewpoint leads to a natural condition. In other words, the spectral response curves of the visual system should be represented as linear combinations of the spectral response curves of the image sensors. Then, a practical condition is presented using the CIE color‐matching function. The computation method for the determination of the spectral response curves of the sensors is presented based on the least‐square technique. As an application example, a drum scanner with four sensors for B/W, R, G and B is discussed. The spectral response curves are determined by adjusting the color filter, and the performance of the system is examined experimentally on the color specification system.
A method of recognizing three‐dimensional position of a rigid body using its shape‐formulation of the problem and its solution by an iteration method
Authors: Hayashi Toyohiko , Iijima Taizo
Published: July 2007

In the problem of estimating three‐dimensional positions of a rigid body from projection data of marked points fixed set to it onto a two‐dimensional plane. We propose a method using positional relations among the marked points.

To estimate the positions of the marked points by optical measurement, multiple projection data are generally used at each point. In measuring multiple points attached on a rigid body, it is possible to estimate three‐dimensional positions of the points from only a single projection datum at each point, if the position of each point on the rigid body is known. In this paper, the problem formulated is of three marked points (the least necessary number to estimate the position of a rigid body). The solution is given by an iterative approximation.

Furthermore, the relation between the measurement method and the convergence of the iterative approximation is analyzed. Observation is best obtained from this point of view. An instrument to measure three‐dimensional movement of the human jaw is introduced.
A method for recognizing three‐dimensional position of a rigid body using its shape. error analysis and an optimization of observation system
Authors: Hayashi Toyohiko , Iijima Taizo
Published: July 2007

In the problem of measuring three‐dimensional positions and motion of a rigid body, methods to determine the three‐dimensional position from its optical projection data on a two‐dimensional plane have been widely used. We have proposed a method using positional relations among the marked points and applied it to three‐dimensional movement measurement of the human law.

If the positions of three marked points on a rigid body are known, measuring these positions requires only one projection datum at each point to determine the three‐dimensional position of the points, since the degree of freedom of a rigid body is six. A previous paper presented formulation of the problem in general form, its solution and theoretical analysis of stability of solution, as well as observation method.

This paper analyzes the effect of error associated with measurement on estimating the position of marked points at implementation. Error propagation equations are derived effective for design of measuring instruments. The optimum measuring method is obtained from the viewpoint of error propagation using the result.
A method of reconstructing 3D mountainous shapes from contours
Authors: Agui Takeshi , Miyata Kazunori , Nakajima Masayuki
Published: July 2007

In general, the shapes of mountains, shore lines, clouds and other natural features are irregular and difficult to define. Furthermore, the conventional (noncompressed) method of storing 3‐dimensional (3D) data of such natural features requires a very large storage space. There is a need to automatically extract key features of natural figures for data compression and accurate reconstruction of the figures.

This paper proposes a reconstruction method for 3D mountainous shapes from feature points of contour lines. First, a method for extracting a model of mountainous shape will be described. Then a reconstruction method based on the model will be discussed. The proposed method is applicable for the generation of a database of background scene for computer animation.
Design of micropower CMOS quaternary memory circuits
Authors: Zukeran Chotei , Afuso Chushin , Kameyama Michitaka , Higuchi Tatsuo
Published: July 2007

In a previous paper the authors proposed a pass transistor network composed of PMOS and NMOS transistors with different threshold voltages, which were realized by a multilevel ion‐implant technique. As a result, any quaternary logic system could be implemented. In the quaternary CMOS make‐break operator circuit, which is the basic cell of the network, the steady‐state current is essentially zero and therefore micro‐power quaternary combinational circuits can be implemented.

In this paper, a micropower quaternary D‐latch circuit is designed using quaternary CMOS make‐break operator circuits. Then using the D‐latch circuit as a unit, a quaternary master‐slave flip‐flop and an up‐down T‐flip‐flop circuit are designed. Computer simulation for these circuits with SPICE‐2 confirmed their correct operation with low power dissipation. The power dissipation during the transient increases in proportion to the operating frequency. Also, a quaternary maximal‐length sequence generator is designed as an application.